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