]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===-- LiveIntervalAnalysis.h - Live Interval Analysis ---------*- 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 | // This file implements the LiveInterval analysis pass. Given some numbering of | |
11 | // each the machine instructions (in this implemention depth-first order) an | |
12 | // interval [i, j) is said to be a live interval for register v if there is no | |
13 | // instruction with number j' > j such that v is live at j' and there is no | |
14 | // instruction with number i' < i such that v is live at i'. In this | |
15 | // implementation intervals can have holes, i.e. an interval might look like | |
16 | // [1,20), [50,65), [1000,1001). | |
17 | // | |
18 | //===----------------------------------------------------------------------===// | |
19 | ||
1a4d82fc JJ |
20 | #ifndef LLVM_CODEGEN_LIVEINTERVALANALYSIS_H |
21 | #define LLVM_CODEGEN_LIVEINTERVALANALYSIS_H | |
223e47cc | 22 | |
223e47cc | 23 | #include "llvm/ADT/IndexedMap.h" |
223e47cc | 24 | #include "llvm/ADT/SmallVector.h" |
970d7e83 LB |
25 | #include "llvm/CodeGen/LiveInterval.h" |
26 | #include "llvm/CodeGen/MachineBasicBlock.h" | |
27 | #include "llvm/CodeGen/MachineFunctionPass.h" | |
28 | #include "llvm/CodeGen/SlotIndexes.h" | |
223e47cc | 29 | #include "llvm/Support/Allocator.h" |
970d7e83 | 30 | #include "llvm/Target/TargetRegisterInfo.h" |
223e47cc LB |
31 | #include <cmath> |
32 | #include <iterator> | |
33 | ||
34 | namespace llvm { | |
35 | ||
36 | class AliasAnalysis; | |
1a4d82fc JJ |
37 | class BitVector; |
38 | class BlockFrequency; | |
223e47cc LB |
39 | class LiveRangeCalc; |
40 | class LiveVariables; | |
41 | class MachineDominatorTree; | |
42 | class MachineLoopInfo; | |
43 | class TargetRegisterInfo; | |
44 | class MachineRegisterInfo; | |
45 | class TargetInstrInfo; | |
46 | class TargetRegisterClass; | |
47 | class VirtRegMap; | |
1a4d82fc | 48 | class MachineBlockFrequencyInfo; |
223e47cc LB |
49 | |
50 | class LiveIntervals : public MachineFunctionPass { | |
51 | MachineFunction* MF; | |
52 | MachineRegisterInfo* MRI; | |
223e47cc LB |
53 | const TargetRegisterInfo* TRI; |
54 | const TargetInstrInfo* TII; | |
55 | AliasAnalysis *AA; | |
223e47cc LB |
56 | SlotIndexes* Indexes; |
57 | MachineDominatorTree *DomTree; | |
58 | LiveRangeCalc *LRCalc; | |
59 | ||
60 | /// Special pool allocator for VNInfo's (LiveInterval val#). | |
61 | /// | |
62 | VNInfo::Allocator VNInfoAllocator; | |
63 | ||
64 | /// Live interval pointers for all the virtual registers. | |
65 | IndexedMap<LiveInterval*, VirtReg2IndexFunctor> VirtRegIntervals; | |
66 | ||
223e47cc LB |
67 | /// RegMaskSlots - Sorted list of instructions with register mask operands. |
68 | /// Always use the 'r' slot, RegMasks are normal clobbers, not early | |
69 | /// clobbers. | |
70 | SmallVector<SlotIndex, 8> RegMaskSlots; | |
71 | ||
72 | /// RegMaskBits - This vector is parallel to RegMaskSlots, it holds a | |
73 | /// pointer to the corresponding register mask. This pointer can be | |
74 | /// recomputed as: | |
75 | /// | |
76 | /// MI = Indexes->getInstructionFromIndex(RegMaskSlot[N]); | |
77 | /// unsigned OpNum = findRegMaskOperand(MI); | |
78 | /// RegMaskBits[N] = MI->getOperand(OpNum).getRegMask(); | |
79 | /// | |
80 | /// This is kept in a separate vector partly because some standard | |
81 | /// libraries don't support lower_bound() with mixed objects, partly to | |
82 | /// improve locality when searching in RegMaskSlots. | |
83 | /// Also see the comment in LiveInterval::find(). | |
84 | SmallVector<const uint32_t*, 8> RegMaskBits; | |
85 | ||
86 | /// For each basic block number, keep (begin, size) pairs indexing into the | |
87 | /// RegMaskSlots and RegMaskBits arrays. | |
88 | /// Note that basic block numbers may not be layout contiguous, that's why | |
89 | /// we can't just keep track of the first register mask in each basic | |
90 | /// block. | |
91 | SmallVector<std::pair<unsigned, unsigned>, 8> RegMaskBlocks; | |
92 | ||
1a4d82fc JJ |
93 | /// Keeps a live range set for each register unit to track fixed physreg |
94 | /// interference. | |
95 | SmallVector<LiveRange*, 0> RegUnitRanges; | |
223e47cc LB |
96 | |
97 | public: | |
98 | static char ID; // Pass identification, replacement for typeid | |
99 | LiveIntervals(); | |
100 | virtual ~LiveIntervals(); | |
101 | ||
102 | // Calculate the spill weight to assign to a single instruction. | |
1a4d82fc JJ |
103 | static float getSpillWeight(bool isDef, bool isUse, |
104 | const MachineBlockFrequencyInfo *MBFI, | |
105 | const MachineInstr *Instr); | |
223e47cc LB |
106 | |
107 | LiveInterval &getInterval(unsigned Reg) { | |
1a4d82fc JJ |
108 | if (hasInterval(Reg)) |
109 | return *VirtRegIntervals[Reg]; | |
110 | else | |
111 | return createAndComputeVirtRegInterval(Reg); | |
223e47cc LB |
112 | } |
113 | ||
114 | const LiveInterval &getInterval(unsigned Reg) const { | |
115 | return const_cast<LiveIntervals*>(this)->getInterval(Reg); | |
116 | } | |
117 | ||
118 | bool hasInterval(unsigned Reg) const { | |
119 | return VirtRegIntervals.inBounds(Reg) && VirtRegIntervals[Reg]; | |
120 | } | |
121 | ||
223e47cc | 122 | // Interval creation. |
1a4d82fc JJ |
123 | LiveInterval &createEmptyInterval(unsigned Reg) { |
124 | assert(!hasInterval(Reg) && "Interval already exists!"); | |
125 | VirtRegIntervals.grow(Reg); | |
126 | VirtRegIntervals[Reg] = createInterval(Reg); | |
127 | return *VirtRegIntervals[Reg]; | |
128 | } | |
129 | ||
130 | LiveInterval &createAndComputeVirtRegInterval(unsigned Reg) { | |
131 | LiveInterval &LI = createEmptyInterval(Reg); | |
132 | computeVirtRegInterval(LI); | |
133 | return LI; | |
223e47cc LB |
134 | } |
135 | ||
136 | // Interval removal. | |
137 | void removeInterval(unsigned Reg) { | |
138 | delete VirtRegIntervals[Reg]; | |
1a4d82fc | 139 | VirtRegIntervals[Reg] = nullptr; |
223e47cc LB |
140 | } |
141 | ||
1a4d82fc JJ |
142 | /// Given a register and an instruction, adds a live segment from that |
143 | /// instruction to the end of its MBB. | |
144 | LiveInterval::Segment addSegmentToEndOfBlock(unsigned reg, | |
145 | MachineInstr* startInst); | |
223e47cc LB |
146 | |
147 | /// shrinkToUses - After removing some uses of a register, shrink its live | |
148 | /// range to just the remaining uses. This method does not compute reaching | |
149 | /// defs for new uses, and it doesn't remove dead defs. | |
150 | /// Dead PHIDef values are marked as unused. | |
151 | /// New dead machine instructions are added to the dead vector. | |
152 | /// Return true if the interval may have been separated into multiple | |
153 | /// connected components. | |
154 | bool shrinkToUses(LiveInterval *li, | |
1a4d82fc JJ |
155 | SmallVectorImpl<MachineInstr*> *dead = nullptr); |
156 | ||
85aaf69f SL |
157 | /// Specialized version of |
158 | /// shrinkToUses(LiveInterval *li, SmallVectorImpl<MachineInstr*> *dead) | |
159 | /// that works on a subregister live range and only looks at uses matching | |
160 | /// the lane mask of the subregister range. | |
161 | void shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg); | |
223e47cc LB |
162 | |
163 | /// extendToIndices - Extend the live range of LI to reach all points in | |
164 | /// Indices. The points in the Indices array must be jointly dominated by | |
165 | /// existing defs in LI. PHI-defs are added as needed to maintain SSA form. | |
166 | /// | |
167 | /// If a SlotIndex in Indices is the end index of a basic block, LI will be | |
168 | /// extended to be live out of the basic block. | |
169 | /// | |
170 | /// See also LiveRangeCalc::extend(). | |
1a4d82fc | 171 | void extendToIndices(LiveRange &LR, ArrayRef<SlotIndex> Indices); |
223e47cc | 172 | |
85aaf69f SL |
173 | |
174 | /// If @p LR has a live value at @p Kill, prune its live range by removing | |
175 | /// any liveness reachable from Kill. Add live range end points to | |
223e47cc LB |
176 | /// EndPoints such that extendToIndices(LI, EndPoints) will reconstruct the |
177 | /// value's live range. | |
178 | /// | |
179 | /// Calling pruneValue() and extendToIndices() can be used to reconstruct | |
180 | /// SSA form after adding defs to a virtual register. | |
85aaf69f SL |
181 | void pruneValue(LiveRange &LR, SlotIndex Kill, |
182 | SmallVectorImpl<SlotIndex> *EndPoints); | |
183 | ||
184 | /// Subregister aware variant of pruneValue(LiveRange &LR, SlotIndex Kill, | |
185 | /// SmallVectorImpl<SlotIndex> &EndPoints). Prunes the value in the main | |
186 | /// range and all sub ranges. | |
187 | void pruneValue(LiveInterval &LI, SlotIndex Kill, | |
223e47cc LB |
188 | SmallVectorImpl<SlotIndex> *EndPoints); |
189 | ||
190 | SlotIndexes *getSlotIndexes() const { | |
191 | return Indexes; | |
192 | } | |
193 | ||
194 | AliasAnalysis *getAliasAnalysis() const { | |
195 | return AA; | |
196 | } | |
197 | ||
198 | /// isNotInMIMap - returns true if the specified machine instr has been | |
199 | /// removed or was never entered in the map. | |
200 | bool isNotInMIMap(const MachineInstr* Instr) const { | |
201 | return !Indexes->hasIndex(Instr); | |
202 | } | |
203 | ||
204 | /// Returns the base index of the given instruction. | |
205 | SlotIndex getInstructionIndex(const MachineInstr *instr) const { | |
206 | return Indexes->getInstructionIndex(instr); | |
207 | } | |
208 | ||
209 | /// Returns the instruction associated with the given index. | |
210 | MachineInstr* getInstructionFromIndex(SlotIndex index) const { | |
211 | return Indexes->getInstructionFromIndex(index); | |
212 | } | |
213 | ||
214 | /// Return the first index in the given basic block. | |
215 | SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { | |
216 | return Indexes->getMBBStartIdx(mbb); | |
217 | } | |
218 | ||
219 | /// Return the last index in the given basic block. | |
220 | SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { | |
221 | return Indexes->getMBBEndIdx(mbb); | |
222 | } | |
223 | ||
1a4d82fc | 224 | bool isLiveInToMBB(const LiveRange &LR, |
223e47cc | 225 | const MachineBasicBlock *mbb) const { |
1a4d82fc | 226 | return LR.liveAt(getMBBStartIdx(mbb)); |
223e47cc LB |
227 | } |
228 | ||
1a4d82fc | 229 | bool isLiveOutOfMBB(const LiveRange &LR, |
223e47cc | 230 | const MachineBasicBlock *mbb) const { |
1a4d82fc | 231 | return LR.liveAt(getMBBEndIdx(mbb).getPrevSlot()); |
223e47cc LB |
232 | } |
233 | ||
234 | MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { | |
235 | return Indexes->getMBBFromIndex(index); | |
236 | } | |
237 | ||
970d7e83 LB |
238 | void insertMBBInMaps(MachineBasicBlock *MBB) { |
239 | Indexes->insertMBBInMaps(MBB); | |
240 | assert(unsigned(MBB->getNumber()) == RegMaskBlocks.size() && | |
241 | "Blocks must be added in order."); | |
242 | RegMaskBlocks.push_back(std::make_pair(RegMaskSlots.size(), 0)); | |
243 | } | |
244 | ||
223e47cc LB |
245 | SlotIndex InsertMachineInstrInMaps(MachineInstr *MI) { |
246 | return Indexes->insertMachineInstrInMaps(MI); | |
247 | } | |
248 | ||
1a4d82fc JJ |
249 | void InsertMachineInstrRangeInMaps(MachineBasicBlock::iterator B, |
250 | MachineBasicBlock::iterator E) { | |
251 | for (MachineBasicBlock::iterator I = B; I != E; ++I) | |
252 | Indexes->insertMachineInstrInMaps(I); | |
253 | } | |
254 | ||
223e47cc LB |
255 | void RemoveMachineInstrFromMaps(MachineInstr *MI) { |
256 | Indexes->removeMachineInstrFromMaps(MI); | |
257 | } | |
258 | ||
259 | void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) { | |
260 | Indexes->replaceMachineInstrInMaps(MI, NewMI); | |
261 | } | |
262 | ||
263 | bool findLiveInMBBs(SlotIndex Start, SlotIndex End, | |
264 | SmallVectorImpl<MachineBasicBlock*> &MBBs) const { | |
265 | return Indexes->findLiveInMBBs(Start, End, MBBs); | |
266 | } | |
267 | ||
268 | VNInfo::Allocator& getVNInfoAllocator() { return VNInfoAllocator; } | |
269 | ||
1a4d82fc JJ |
270 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
271 | void releaseMemory() override; | |
223e47cc LB |
272 | |
273 | /// runOnMachineFunction - pass entry point | |
1a4d82fc | 274 | bool runOnMachineFunction(MachineFunction&) override; |
223e47cc LB |
275 | |
276 | /// print - Implement the dump method. | |
1a4d82fc | 277 | void print(raw_ostream &O, const Module* = nullptr) const override; |
223e47cc LB |
278 | |
279 | /// intervalIsInOneMBB - If LI is confined to a single basic block, return | |
280 | /// a pointer to that block. If LI is live in to or out of any block, | |
281 | /// return NULL. | |
282 | MachineBasicBlock *intervalIsInOneMBB(const LiveInterval &LI) const; | |
283 | ||
284 | /// Returns true if VNI is killed by any PHI-def values in LI. | |
285 | /// This may conservatively return true to avoid expensive computations. | |
286 | bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const; | |
287 | ||
288 | /// addKillFlags - Add kill flags to any instruction that kills a virtual | |
289 | /// register. | |
290 | void addKillFlags(const VirtRegMap*); | |
291 | ||
292 | /// handleMove - call this method to notify LiveIntervals that | |
293 | /// instruction 'mi' has been moved within a basic block. This will update | |
294 | /// the live intervals for all operands of mi. Moves between basic blocks | |
295 | /// are not supported. | |
970d7e83 LB |
296 | /// |
297 | /// \param UpdateFlags Update live intervals for nonallocatable physregs. | |
298 | void handleMove(MachineInstr* MI, bool UpdateFlags = false); | |
223e47cc LB |
299 | |
300 | /// moveIntoBundle - Update intervals for operands of MI so that they | |
301 | /// begin/end on the SlotIndex for BundleStart. | |
302 | /// | |
970d7e83 LB |
303 | /// \param UpdateFlags Update live intervals for nonallocatable physregs. |
304 | /// | |
223e47cc LB |
305 | /// Requires MI and BundleStart to have SlotIndexes, and assumes |
306 | /// existing liveness is accurate. BundleStart should be the first | |
307 | /// instruction in the Bundle. | |
970d7e83 LB |
308 | void handleMoveIntoBundle(MachineInstr* MI, MachineInstr* BundleStart, |
309 | bool UpdateFlags = false); | |
310 | ||
311 | /// repairIntervalsInRange - Update live intervals for instructions in a | |
312 | /// range of iterators. It is intended for use after target hooks that may | |
313 | /// insert or remove instructions, and is only efficient for a small number | |
314 | /// of instructions. | |
315 | /// | |
316 | /// OrigRegs is a vector of registers that were originally used by the | |
317 | /// instructions in the range between the two iterators. | |
318 | /// | |
319 | /// Currently, the only only changes that are supported are simple removal | |
320 | /// and addition of uses. | |
321 | void repairIntervalsInRange(MachineBasicBlock *MBB, | |
322 | MachineBasicBlock::iterator Begin, | |
323 | MachineBasicBlock::iterator End, | |
324 | ArrayRef<unsigned> OrigRegs); | |
223e47cc LB |
325 | |
326 | // Register mask functions. | |
327 | // | |
328 | // Machine instructions may use a register mask operand to indicate that a | |
329 | // large number of registers are clobbered by the instruction. This is | |
330 | // typically used for calls. | |
331 | // | |
332 | // For compile time performance reasons, these clobbers are not recorded in | |
333 | // the live intervals for individual physical registers. Instead, | |
334 | // LiveIntervalAnalysis maintains a sorted list of instructions with | |
335 | // register mask operands. | |
336 | ||
337 | /// getRegMaskSlots - Returns a sorted array of slot indices of all | |
338 | /// instructions with register mask operands. | |
339 | ArrayRef<SlotIndex> getRegMaskSlots() const { return RegMaskSlots; } | |
340 | ||
341 | /// getRegMaskSlotsInBlock - Returns a sorted array of slot indices of all | |
342 | /// instructions with register mask operands in the basic block numbered | |
343 | /// MBBNum. | |
344 | ArrayRef<SlotIndex> getRegMaskSlotsInBlock(unsigned MBBNum) const { | |
345 | std::pair<unsigned, unsigned> P = RegMaskBlocks[MBBNum]; | |
346 | return getRegMaskSlots().slice(P.first, P.second); | |
347 | } | |
348 | ||
349 | /// getRegMaskBits() - Returns an array of register mask pointers | |
350 | /// corresponding to getRegMaskSlots(). | |
351 | ArrayRef<const uint32_t*> getRegMaskBits() const { return RegMaskBits; } | |
352 | ||
353 | /// getRegMaskBitsInBlock - Returns an array of mask pointers corresponding | |
354 | /// to getRegMaskSlotsInBlock(MBBNum). | |
355 | ArrayRef<const uint32_t*> getRegMaskBitsInBlock(unsigned MBBNum) const { | |
356 | std::pair<unsigned, unsigned> P = RegMaskBlocks[MBBNum]; | |
357 | return getRegMaskBits().slice(P.first, P.second); | |
358 | } | |
359 | ||
360 | /// checkRegMaskInterference - Test if LI is live across any register mask | |
361 | /// instructions, and compute a bit mask of physical registers that are not | |
362 | /// clobbered by any of them. | |
363 | /// | |
364 | /// Returns false if LI doesn't cross any register mask instructions. In | |
365 | /// that case, the bit vector is not filled in. | |
366 | bool checkRegMaskInterference(LiveInterval &LI, | |
367 | BitVector &UsableRegs); | |
368 | ||
369 | // Register unit functions. | |
370 | // | |
371 | // Fixed interference occurs when MachineInstrs use physregs directly | |
372 | // instead of virtual registers. This typically happens when passing | |
373 | // arguments to a function call, or when instructions require operands in | |
374 | // fixed registers. | |
375 | // | |
376 | // Each physreg has one or more register units, see MCRegisterInfo. We | |
377 | // track liveness per register unit to handle aliasing registers more | |
378 | // efficiently. | |
379 | ||
380 | /// getRegUnit - Return the live range for Unit. | |
381 | /// It will be computed if it doesn't exist. | |
1a4d82fc JJ |
382 | LiveRange &getRegUnit(unsigned Unit) { |
383 | LiveRange *LR = RegUnitRanges[Unit]; | |
384 | if (!LR) { | |
223e47cc | 385 | // Compute missing ranges on demand. |
1a4d82fc JJ |
386 | RegUnitRanges[Unit] = LR = new LiveRange(); |
387 | computeRegUnitRange(*LR, Unit); | |
223e47cc | 388 | } |
1a4d82fc | 389 | return *LR; |
223e47cc LB |
390 | } |
391 | ||
392 | /// getCachedRegUnit - Return the live range for Unit if it has already | |
393 | /// been computed, or NULL if it hasn't been computed yet. | |
1a4d82fc JJ |
394 | LiveRange *getCachedRegUnit(unsigned Unit) { |
395 | return RegUnitRanges[Unit]; | |
223e47cc LB |
396 | } |
397 | ||
1a4d82fc JJ |
398 | const LiveRange *getCachedRegUnit(unsigned Unit) const { |
399 | return RegUnitRanges[Unit]; | |
970d7e83 | 400 | } |
223e47cc | 401 | |
970d7e83 | 402 | private: |
223e47cc LB |
403 | /// Compute live intervals for all virtual registers. |
404 | void computeVirtRegs(); | |
405 | ||
406 | /// Compute RegMaskSlots and RegMaskBits. | |
407 | void computeRegMasks(); | |
408 | ||
85aaf69f SL |
409 | /// Walk the values in @p LI and check for dead values: |
410 | /// - Dead PHIDef values are marked as unused. | |
411 | /// - Dead operands are marked as such. | |
412 | /// - Completely dead machine instructions are added to the @p dead vector | |
413 | /// if it is not nullptr. | |
414 | /// Returns true if any PHI value numbers have been removed which may | |
415 | /// have separated the interval into multiple connected components. | |
416 | bool computeDeadValues(LiveInterval &LI, | |
417 | SmallVectorImpl<MachineInstr*> *dead); | |
418 | ||
223e47cc LB |
419 | static LiveInterval* createInterval(unsigned Reg); |
420 | ||
421 | void printInstrs(raw_ostream &O) const; | |
422 | void dumpInstrs() const; | |
423 | ||
424 | void computeLiveInRegUnits(); | |
1a4d82fc JJ |
425 | void computeRegUnitRange(LiveRange&, unsigned Unit); |
426 | void computeVirtRegInterval(LiveInterval&); | |
223e47cc | 427 | |
85aaf69f SL |
428 | |
429 | /// Helper function for repairIntervalsInRange(), walks backwards and | |
430 | /// creates/modifies live segments in @p LR to match the operands found. | |
431 | /// Only full operands or operands with subregisters matching @p LaneMask | |
432 | /// are considered. | |
433 | void repairOldRegInRange(MachineBasicBlock::iterator Begin, | |
434 | MachineBasicBlock::iterator End, | |
435 | const SlotIndex endIdx, LiveRange &LR, | |
436 | unsigned Reg, unsigned LaneMask = ~0u); | |
437 | ||
223e47cc LB |
438 | class HMEditor; |
439 | }; | |
440 | } // End llvm namespace | |
441 | ||
442 | #endif |