/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/LiveRangeCalc.h
Line | Count | Source |
1 | | //===- LiveRangeCalc.h - Calculate live ranges ------------------*- C++ -*-===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | // The LiveRangeCalc class can be used to compute live ranges from scratch. It |
11 | | // caches information about values in the CFG to speed up repeated operations |
12 | | // on the same live range. The cache can be shared by non-overlapping live |
13 | | // ranges. SplitKit uses that when computing the live range of split products. |
14 | | // |
15 | | // A low-level interface is available to clients that know where a variable is |
16 | | // live, but don't know which value it has as every point. LiveRangeCalc will |
17 | | // propagate values down the dominator tree, and even insert PHI-defs where |
18 | | // needed. SplitKit uses this faster interface when possible. |
19 | | // |
20 | | //===----------------------------------------------------------------------===// |
21 | | |
22 | | #ifndef LLVM_LIB_CODEGEN_LIVERANGECALC_H |
23 | | #define LLVM_LIB_CODEGEN_LIVERANGECALC_H |
24 | | |
25 | | #include "llvm/ADT/ArrayRef.h" |
26 | | #include "llvm/ADT/BitVector.h" |
27 | | #include "llvm/ADT/DenseMap.h" |
28 | | #include "llvm/ADT/IndexedMap.h" |
29 | | #include "llvm/ADT/SmallVector.h" |
30 | | #include "llvm/CodeGen/LiveInterval.h" |
31 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
32 | | #include "llvm/CodeGen/SlotIndexes.h" |
33 | | #include "llvm/MC/LaneBitmask.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 | 2.48M | : 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, |
150 | | SlotIndex Kill, unsigned PhysReg, |
151 | | ArrayRef<SlotIndex> Undefs); |
152 | | |
153 | | /// updateSSA - Compute the values that will be live in to all requested |
154 | | /// blocks in LiveIn. Create PHI-def values as required to preserve SSA form. |
155 | | /// |
156 | | /// Every live-in block must be jointly dominated by the added live-out |
157 | | /// blocks. No values are read from the live ranges. |
158 | | void updateSSA(); |
159 | | |
160 | | /// Transfer information from the LiveIn vector to the live ranges and update |
161 | | /// the given @p LiveOuts. |
162 | | void updateFromLiveIns(); |
163 | | |
164 | | /// Extend the live range of @p LR to reach all uses of Reg. |
165 | | /// |
166 | | /// If @p LR is a main range, or if @p LI is null, then all uses must be |
167 | | /// jointly dominated by the definitions from @p LR. If @p LR is a subrange |
168 | | /// of the live interval @p LI, corresponding to lane mask @p LaneMask, |
169 | | /// all uses must be jointly dominated by the definitions from @p LR |
170 | | /// together with definitions of other lanes where @p LR becomes undefined |
171 | | /// (via <def,read-undef> operands). |
172 | | /// If @p LR is a main range, the @p LaneMask should be set to ~0, i.e. |
173 | | /// LaneBitmask::getAll(). |
174 | | void extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask, |
175 | | LiveInterval *LI = nullptr); |
176 | | |
177 | | /// Reset Map and Seen fields. |
178 | | void resetLiveOutMap(); |
179 | | |
180 | | public: |
181 | 1.52M | LiveRangeCalc() = default; |
182 | | |
183 | | //===--------------------------------------------------------------------===// |
184 | | // High-level interface. |
185 | | //===--------------------------------------------------------------------===// |
186 | | // |
187 | | // Calculate live ranges from scratch. |
188 | | // |
189 | | |
190 | | /// reset - Prepare caches for a new set of non-overlapping live ranges. The |
191 | | /// caches must be reset before attempting calculations with a live range |
192 | | /// that may overlap a previously computed live range, and before the first |
193 | | /// live range in a function. If live ranges are not known to be |
194 | | /// non-overlapping, call reset before each. |
195 | | void reset(const MachineFunction *mf, SlotIndexes *SI, |
196 | | MachineDominatorTree *MDT, VNInfo::Allocator *VNIA); |
197 | | |
198 | | //===--------------------------------------------------------------------===// |
199 | | // Mid-level interface. |
200 | | //===--------------------------------------------------------------------===// |
201 | | // |
202 | | // Modify existing live ranges. |
203 | | // |
204 | | |
205 | | /// Extend the live range of @p LR to reach @p Use. |
206 | | /// |
207 | | /// The existing values in @p LR must be live so they jointly dominate @p Use. |
208 | | /// If @p Use is not dominated by a single existing value, PHI-defs are |
209 | | /// inserted as required to preserve SSA form. |
210 | | /// |
211 | | /// PhysReg, when set, is used to verify live-in lists on basic blocks. |
212 | | void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, |
213 | | ArrayRef<SlotIndex> Undefs); |
214 | | |
215 | | /// createDeadDefs - Create a dead def in LI for every def operand of Reg. |
216 | | /// Each instruction defining Reg gets a new VNInfo with a corresponding |
217 | | /// minimal live range. |
218 | | void createDeadDefs(LiveRange &LR, unsigned Reg); |
219 | | |
220 | | /// Extend the live range of @p LR to reach all uses of Reg. |
221 | | /// |
222 | | /// All uses must be jointly dominated by existing liveness. PHI-defs are |
223 | | /// inserted as needed to preserve SSA form. |
224 | 2.03M | void extendToUses(LiveRange &LR, unsigned PhysReg) { |
225 | 2.03M | extendToUses(LR, PhysReg, LaneBitmask::getAll()); |
226 | 2.03M | } |
227 | | |
228 | | /// Calculates liveness for the register specified in live interval @p LI. |
229 | | /// Creates subregister live ranges as needed if subreg liveness tracking is |
230 | | /// enabled. |
231 | | void calculate(LiveInterval &LI, bool TrackSubRegs); |
232 | | |
233 | | /// For live interval \p LI with correct SubRanges construct matching |
234 | | /// information for the main live range. Expects the main live range to not |
235 | | /// have any segments or value numbers. |
236 | | void constructMainRangeFromSubranges(LiveInterval &LI); |
237 | | |
238 | | //===--------------------------------------------------------------------===// |
239 | | // Low-level interface. |
240 | | //===--------------------------------------------------------------------===// |
241 | | // |
242 | | // These functions can be used to compute live ranges where the live-in and |
243 | | // live-out blocks are already known, but the SSA value in each block is |
244 | | // unknown. |
245 | | // |
246 | | // After calling reset(), add known live-out values and known live-in blocks. |
247 | | // Then call calculateValues() to compute the actual value that is |
248 | | // live-in to each block, and add liveness to the live ranges. |
249 | | // |
250 | | |
251 | | /// setLiveOutValue - Indicate that VNI is live out from MBB. The |
252 | | /// calculateValues() function will not add liveness for MBB, the caller |
253 | | /// should take care of that. |
254 | | /// |
255 | | /// VNI may be null only if MBB is a live-through block also passed to |
256 | | /// addLiveInBlock(). |
257 | 39.7M | void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI) { |
258 | 39.7M | Seen.set(MBB->getNumber()); |
259 | 39.7M | Map[MBB] = LiveOutPair(VNI, nullptr); |
260 | 39.7M | } |
261 | | |
262 | | /// addLiveInBlock - Add a block with an unknown live-in value. This |
263 | | /// function can only be called once per basic block. Once the live-in value |
264 | | /// has been determined, calculateValues() will add liveness to LI. |
265 | | /// |
266 | | /// @param LR The live range that is live-in to the block. |
267 | | /// @param DomNode The domtree node for the block. |
268 | | /// @param Kill Index in block where LI is killed. If the value is |
269 | | /// live-through, set Kill = SLotIndex() and also call |
270 | | /// setLiveOutValue(MBB, 0). |
271 | | void addLiveInBlock(LiveRange &LR, |
272 | | MachineDomTreeNode *DomNode, |
273 | 2.48M | SlotIndex Kill = SlotIndex()) { |
274 | 2.48M | LiveIn.push_back(LiveInBlock(LR, DomNode, Kill)); |
275 | 2.48M | } |
276 | | |
277 | | /// calculateValues - Calculate the value that will be live-in to each block |
278 | | /// added with addLiveInBlock. Add PHI-def values as needed to preserve SSA |
279 | | /// form. Add liveness to all live-in blocks up to the Kill point, or the |
280 | | /// whole block for live-through blocks. |
281 | | /// |
282 | | /// Every predecessor of a live-in block must have been given a value with |
283 | | /// setLiveOutValue, the value may be null for live-trough blocks. |
284 | | void calculateValues(); |
285 | | }; |
286 | | |
287 | | } // end namespace llvm |
288 | | |
289 | | #endif // LLVM_LIB_CODEGEN_LIVERANGECALC_H |