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