1 | //===- LiveRangeCalc.h - Calculate live ranges -----------------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // The LiveRangeCalc class can be used to implement the computation of |
10 | // live ranges from scratch. |
11 | // It caches information about values in the CFG to speed up repeated |
12 | // operations on the same live range. The cache can be shared by |
13 | // non-overlapping live ranges. SplitKit uses that when computing the live |
14 | // range of split products. |
15 | // |
16 | // A low-level interface is available to clients that know where a variable is |
17 | // live, but don't know which value it has as every point. LiveRangeCalc will |
18 | // propagate values down the dominator tree, and even insert PHI-defs where |
19 | // needed. SplitKit uses this faster interface when possible. |
20 | // |
21 | //===----------------------------------------------------------------------===// |
22 | |
23 | #ifndef LLVM_CODEGEN_LIVERANGECALC_H |
24 | #define LLVM_CODEGEN_LIVERANGECALC_H |
25 | |
26 | #include "llvm/ADT/ArrayRef.h" |
27 | #include "llvm/ADT/BitVector.h" |
28 | #include "llvm/ADT/DenseMap.h" |
29 | #include "llvm/ADT/IndexedMap.h" |
30 | #include "llvm/ADT/SmallVector.h" |
31 | #include "llvm/CodeGen/LiveInterval.h" |
32 | #include "llvm/CodeGen/MachineBasicBlock.h" |
33 | #include "llvm/CodeGen/SlotIndexes.h" |
34 | #include <utility> |
35 | |
36 | namespace llvm { |
37 | |
38 | template <class NodeT> class DomTreeNodeBase; |
39 | class MachineDominatorTree; |
40 | class MachineFunction; |
41 | class MachineRegisterInfo; |
42 | |
43 | using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>; |
44 | |
45 | class LiveRangeCalc { |
46 | const MachineFunction *MF = nullptr; |
47 | const MachineRegisterInfo *MRI = nullptr; |
48 | SlotIndexes *Indexes = nullptr; |
49 | MachineDominatorTree *DomTree = nullptr; |
50 | VNInfo::Allocator *Alloc = nullptr; |
51 | |
52 | /// LiveOutPair - A value and the block that defined it. The domtree node is |
53 | /// redundant, it can be computed as: MDT[Indexes.getMBBFromIndex(VNI->def)]. |
54 | using LiveOutPair = std::pair<VNInfo *, MachineDomTreeNode *>; |
55 | |
56 | /// LiveOutMap - Map basic blocks to the value leaving the block. |
57 | using LiveOutMap = IndexedMap<LiveOutPair, MBB2NumberFunctor>; |
58 | |
59 | /// Bit vector of active entries in LiveOut, also used as a visited set by |
60 | /// findReachingDefs. One entry per basic block, indexed by block number. |
61 | /// This is kept as a separate bit vector because it can be cleared quickly |
62 | /// when switching live ranges. |
63 | BitVector Seen; |
64 | |
65 | /// Map LiveRange to sets of blocks (represented by bit vectors) that |
66 | /// in the live range are defined on entry and undefined on entry. |
67 | /// A block is defined on entry if there is a path from at least one of |
68 | /// the defs in the live range to the entry of the block, and conversely, |
69 | /// a block is undefined on entry, if there is no such path (i.e. no |
70 | /// definition reaches the entry of the block). A single LiveRangeCalc |
71 | /// object is used to track live-out information for multiple registers |
72 | /// in live range splitting (which is ok, since the live ranges of these |
73 | /// registers do not overlap), but the defined/undefined information must |
74 | /// be kept separate for each individual range. |
75 | /// By convention, EntryInfoMap[&LR] = { Defined, Undefined }. |
76 | using EntryInfoMap = DenseMap<LiveRange *, std::pair<BitVector, BitVector>>; |
77 | EntryInfoMap EntryInfos; |
78 | |
79 | /// Map each basic block where a live range is live out to the live-out value |
80 | /// and its defining block. |
81 | /// |
82 | /// For every basic block, MBB, one of these conditions shall be true: |
83 | /// |
84 | /// 1. !Seen.count(MBB->getNumber()) |
85 | /// Blocks without a Seen bit are ignored. |
86 | /// 2. LiveOut[MBB].second.getNode() == MBB |
87 | /// The live-out value is defined in MBB. |
88 | /// 3. forall P in preds(MBB): LiveOut[P] == LiveOut[MBB] |
89 | /// The live-out value passses through MBB. All predecessors must carry |
90 | /// the same value. |
91 | /// |
92 | /// The domtree node may be null, it can be computed. |
93 | /// |
94 | /// The map can be shared by multiple live ranges as long as no two are |
95 | /// live-out of the same block. |
96 | LiveOutMap Map; |
97 | |
98 | /// LiveInBlock - Information about a basic block where a live range is known |
99 | /// to be live-in, but the value has not yet been determined. |
100 | struct LiveInBlock { |
101 | // The live range set that is live-in to this block. The algorithms can |
102 | // handle multiple non-overlapping live ranges simultaneously. |
103 | LiveRange &LR; |
104 | |
105 | // DomNode - Dominator tree node for the block. |
106 | // Cleared when the final value has been determined and LI has been updated. |
107 | MachineDomTreeNode *DomNode; |
108 | |
109 | // Position in block where the live-in range ends, or SlotIndex() if the |
110 | // range passes through the block. When the final value has been |
111 | // determined, the range from the block start to Kill will be added to LI. |
112 | SlotIndex Kill; |
113 | |
114 | // Live-in value filled in by updateSSA once it is known. |
115 | VNInfo *Value = nullptr; |
116 | |
117 | LiveInBlock(LiveRange &LR, MachineDomTreeNode *node, SlotIndex kill) |
118 | : LR(LR), DomNode(node), Kill(kill) {} |
119 | }; |
120 | |
121 | /// LiveIn - Work list of blocks where the live-in value has yet to be |
122 | /// determined. This list is typically computed by findReachingDefs() and |
123 | /// used as a work list by updateSSA(). The low-level interface may also be |
124 | /// used to add entries directly. |
125 | SmallVector<LiveInBlock, 16> LiveIn; |
126 | |
127 | /// Check if the entry to block @p MBB can be reached by any of the defs |
128 | /// in @p LR. Return true if none of the defs reach the entry to @p MBB. |
129 | bool isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs, |
130 | MachineBasicBlock &MBB, BitVector &DefOnEntry, |
131 | BitVector &UndefOnEntry); |
132 | |
133 | /// Find the set of defs that can reach @p Kill. @p Kill must belong to |
134 | /// @p UseMBB. |
135 | /// |
136 | /// If exactly one def can reach @p UseMBB, and the def dominates @p Kill, |
137 | /// all paths from the def to @p UseMBB are added to @p LR, and the function |
138 | /// returns true. |
139 | /// |
140 | /// If multiple values can reach @p UseMBB, the blocks that need @p LR to be |
141 | /// live in are added to the LiveIn array, and the function returns false. |
142 | /// |
143 | /// The array @p Undef provides the locations where the range @p LR becomes |
144 | /// undefined by <def,read-undef> operands on other subranges. If @p Undef |
145 | /// is non-empty and @p Kill is jointly dominated only by the entries of |
146 | /// @p Undef, the function returns false. |
147 | /// |
148 | /// PhysReg, when set, is used to verify live-in lists on basic blocks. |
149 | bool findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB, SlotIndex Use, |
150 | unsigned PhysReg, ArrayRef<SlotIndex> Undefs); |
151 | |
152 | /// updateSSA - Compute the values that will be live in to all requested |
153 | /// blocks in LiveIn. Create PHI-def values as required to preserve SSA form. |
154 | /// |
155 | /// Every live-in block must be jointly dominated by the added live-out |
156 | /// blocks. No values are read from the live ranges. |
157 | void updateSSA(); |
158 | |
159 | /// Transfer information from the LiveIn vector to the live ranges and update |
160 | /// the given @p LiveOuts. |
161 | void updateFromLiveIns(); |
162 | |
163 | protected: |
164 | /// Some getters to expose in a read-only way some private fields to |
165 | /// subclasses. |
166 | const MachineFunction *getMachineFunction() { return MF; } |
167 | const MachineRegisterInfo *getRegInfo() const { return MRI; } |
168 | SlotIndexes *getIndexes() { return Indexes; } |
169 | MachineDominatorTree *getDomTree() { return DomTree; } |
170 | VNInfo::Allocator *getVNAlloc() { return Alloc; } |
171 | |
172 | /// Reset Map and Seen fields. |
173 | void resetLiveOutMap(); |
174 | |
175 | public: |
176 | LiveRangeCalc() = default; |
177 | |
178 | //===--------------------------------------------------------------------===// |
179 | // High-level interface. |
180 | //===--------------------------------------------------------------------===// |
181 | // |
182 | // Calculate live ranges from scratch. |
183 | // |
184 | |
185 | /// reset - Prepare caches for a new set of non-overlapping live ranges. The |
186 | /// caches must be reset before attempting calculations with a live range |
187 | /// that may overlap a previously computed live range, and before the first |
188 | /// live range in a function. If live ranges are not known to be |
189 | /// non-overlapping, call reset before each. |
190 | void reset(const MachineFunction *mf, SlotIndexes *SI, |
191 | MachineDominatorTree *MDT, VNInfo::Allocator *VNIA); |
192 | |
193 | //===--------------------------------------------------------------------===// |
194 | // Mid-level interface. |
195 | //===--------------------------------------------------------------------===// |
196 | // |
197 | // Modify existing live ranges. |
198 | // |
199 | |
200 | /// Extend the live range of @p LR to reach @p Use. |
201 | /// |
202 | /// The existing values in @p LR must be live so they jointly dominate @p Use. |
203 | /// If @p Use is not dominated by a single existing value, PHI-defs are |
204 | /// inserted as required to preserve SSA form. |
205 | /// |
206 | /// PhysReg, when set, is used to verify live-in lists on basic blocks. |
207 | void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, |
208 | ArrayRef<SlotIndex> Undefs); |
209 | |
210 | //===--------------------------------------------------------------------===// |
211 | // Low-level interface. |
212 | //===--------------------------------------------------------------------===// |
213 | // |
214 | // These functions can be used to compute live ranges where the live-in and |
215 | // live-out blocks are already known, but the SSA value in each block is |
216 | // unknown. |
217 | // |
218 | // After calling reset(), add known live-out values and known live-in blocks. |
219 | // Then call calculateValues() to compute the actual value that is |
220 | // live-in to each block, and add liveness to the live ranges. |
221 | // |
222 | |
223 | /// setLiveOutValue - Indicate that VNI is live out from MBB. The |
224 | /// calculateValues() function will not add liveness for MBB, the caller |
225 | /// should take care of that. |
226 | /// |
227 | /// VNI may be null only if MBB is a live-through block also passed to |
228 | /// addLiveInBlock(). |
229 | void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI) { |
230 | Seen.set(MBB->getNumber()); |
231 | Map[MBB] = LiveOutPair(VNI, nullptr); |
232 | } |
233 | |
234 | /// addLiveInBlock - Add a block with an unknown live-in value. This |
235 | /// function can only be called once per basic block. Once the live-in value |
236 | /// has been determined, calculateValues() will add liveness to LI. |
237 | /// |
238 | /// @param LR The live range that is live-in to the block. |
239 | /// @param DomNode The domtree node for the block. |
240 | /// @param Kill Index in block where LI is killed. If the value is |
241 | /// live-through, set Kill = SLotIndex() and also call |
242 | /// setLiveOutValue(MBB, 0). |
243 | void addLiveInBlock(LiveRange &LR, MachineDomTreeNode *DomNode, |
244 | SlotIndex Kill = SlotIndex()) { |
245 | LiveIn.push_back(Elt: LiveInBlock(LR, DomNode, Kill)); |
246 | } |
247 | |
248 | /// calculateValues - Calculate the value that will be live-in to each block |
249 | /// added with addLiveInBlock. Add PHI-def values as needed to preserve SSA |
250 | /// form. Add liveness to all live-in blocks up to the Kill point, or the |
251 | /// whole block for live-through blocks. |
252 | /// |
253 | /// Every predecessor of a live-in block must have been given a value with |
254 | /// setLiveOutValue, the value may be null for live-trough blocks. |
255 | void calculateValues(); |
256 | |
257 | /// A diagnostic function to check if the end of the block @p MBB is |
258 | /// jointly dominated by the blocks corresponding to the slot indices |
259 | /// in @p Defs. This function is mainly for use in self-verification |
260 | /// checks. |
261 | LLVM_ATTRIBUTE_UNUSED |
262 | static bool isJointlyDominated(const MachineBasicBlock *MBB, |
263 | ArrayRef<SlotIndex> Defs, |
264 | const SlotIndexes &Indexes); |
265 | }; |
266 | |
267 | } // end namespace llvm |
268 | |
269 | #endif // LLVM_CODEGEN_LIVERANGECALC_H |
270 | |