LLVM 24.0.0git
LiveIntervals.h
Go to the documentation of this file.
1//===- LiveIntervals.h - Live Interval Analysis -----------------*- 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/// \file This file implements the LiveInterval analysis pass. Given some
10/// numbering of each the machine instructions (in this implemention depth-first
11/// order) an interval [i, j) is said to be a live interval for register v if
12/// there is no instruction with number j' > j such that v is live at j' and
13/// there is no instruction with number i' < i such that v is live at i'. In
14/// this implementation intervals can have holes, i.e. an interval might look
15/// like [1,20), [50,65), [1000,1001).
16//
17//===----------------------------------------------------------------------===//
18
19#ifndef LLVM_CODEGEN_LIVEINTERVALS_H
20#define LLVM_CODEGEN_LIVEINTERVALS_H
21
22#include "llvm/ADT/ArrayRef.h"
23#include "llvm/ADT/IndexedMap.h"
32#include "llvm/MC/LaneBitmask.h"
38#include <cassert>
39#include <cstdint>
40#include <utility>
41
42namespace llvm {
43
44class BitVector;
47class MachineFunction;
48class MachineInstr;
51class raw_ostream;
52class TargetInstrInfo;
53class VirtRegMap;
54
55class LiveIntervals {
58
59 MachineFunction *MF = nullptr;
60 MachineRegisterInfo *MRI = nullptr;
61 const TargetRegisterInfo *TRI = nullptr;
62 const TargetInstrInfo *TII = nullptr;
63 SlotIndexes *Indexes = nullptr;
64 MachineDominatorTree *DomTree = nullptr;
65 std::unique_ptr<LiveIntervalCalc> LICalc;
66
67 /// Special pool allocator for VNInfo's (LiveInterval val#).
68 VNInfo::Allocator VNInfoAllocator;
69
70 BumpPtrAllocator RangeAllocator;
71 Recycler<LiveInterval> IntervalRecycler;
72 Recycler<LiveRange> RegUnitRangeRecycler;
73
74 /// Live interval pointers for all the virtual registers.
76
77 /// Per-block state for the current extendSegmentsToUses call. A tag is
78 /// current iff it equals ShrinkTag.
79 struct ShrinkBlockState {
80 /// Current if the block has been queued as live-out.
81 unsigned LiveOutTag = 0;
82 /// Current if LiveIn is valid.
83 unsigned LiveInTag = 0;
84 /// Index of the block's pending live-in segment.
85 unsigned LiveIn = 0;
86 };
87
88 /// Indexed by block number.
90
91 /// Tag for the current extendSegmentsToUses call, incremented on each call
92 /// so stale ShrinkBlocks entries never need clearing.
93 unsigned ShrinkTag = 0;
94
95 /// Sorted list of instructions with register mask operands. Always use the
96 /// 'r' slot, RegMasks are normal clobbers, not early clobbers.
97 SmallVector<SlotIndex, 8> RegMaskSlots;
98
99 /// This vector is parallel to RegMaskSlots, it holds a pointer to the
100 /// corresponding register mask. This pointer can be recomputed as:
101 ///
102 /// MI = Indexes->getInstructionFromIndex(RegMaskSlot[N]);
103 /// unsigned OpNum = findRegMaskOperand(MI);
104 /// RegMaskBits[N] = MI->getOperand(OpNum).getRegMask();
105 ///
106 /// This is kept in a separate vector partly because some standard
107 /// libraries don't support lower_bound() with mixed objects, partly to
108 /// improve locality when searching in RegMaskSlots.
109 /// Also see the comment in LiveInterval::find().
111
112 /// For each basic block number, keep (begin, size) pairs indexing into the
113 /// RegMaskSlots and RegMaskBits arrays.
114 /// Note that basic block numbers may not be layout contiguous, that's why
115 /// we can't just keep track of the first register mask in each basic
116 /// block.
118
119 /// Keeps a live range set for each register unit to track fixed physreg
120 /// interference.
121 SmallVector<LiveRange *, 0> RegUnitRanges;
122
123 // Can only be created from pass manager.
124 LiveIntervals() = default;
126 : Indexes(&SI), DomTree(&DT) {
127 analyze(MF);
128 }
129
130 LLVM_ABI void analyze(MachineFunction &MF);
131
132 LLVM_ABI void clear();
133
134public:
135 LiveIntervals(LiveIntervals &&) = default;
137
139 MachineFunctionAnalysisManager::Invalidator &Inv);
140
141 /// Calculate the spill weight to assign to a single instruction.
142 /// If \p PSI is provided the calculation is altered for optsize functions.
143 LLVM_ABI static float getSpillWeight(bool isDef, bool isUse,
144 const MachineBlockFrequencyInfo *MBFI,
145 const MachineInstr &MI,
146 ProfileSummaryInfo *PSI = nullptr);
147
148 /// Calculate the spill weight to assign to a single instruction.
149 /// If \p PSI is provided the calculation is altered for optsize functions.
150 LLVM_ABI static float getSpillWeight(bool isDef, bool isUse,
151 const MachineBlockFrequencyInfo *MBFI,
152 const MachineBasicBlock *MBB,
153 ProfileSummaryInfo *PSI = nullptr);
154
155 /// Variants taking a precomputed \p OptForSize rather than deriving it from a
156 /// ProfileSummaryInfo.
157 LLVM_ABI static float getSpillWeight(bool isDef, bool isUse,
158 const MachineBlockFrequencyInfo *MBFI,
159 const MachineInstr &MI, bool OptForSize);
160
161 LLVM_ABI static float getSpillWeight(bool isDef, bool isUse,
162 const MachineBlockFrequencyInfo *MBFI,
163 const MachineBasicBlock *MBB,
164 bool OptForSize);
165
167 if (hasInterval(Reg))
168 return *VirtRegIntervals[Reg.id()];
169
171 }
172
174 return const_cast<LiveIntervals *>(this)->getInterval(Reg);
175 }
176
178 return VirtRegIntervals.inBounds(Reg.id()) && VirtRegIntervals[Reg.id()];
179 }
180
181 /// Interval creation.
183 assert(!hasInterval(Reg) && "Interval already exists!");
184 VirtRegIntervals.grow(Reg.id());
185 auto &Interval = VirtRegIntervals[Reg.id()];
186 Interval = createInterval(Reg);
187 return *Interval;
188 }
189
192 computeVirtRegInterval(LI);
193 return LI;
194 }
195
198 NeedSplit = computeVirtRegInterval(LI);
199 return LI;
200 }
201
202 /// Return an existing interval for \p Reg.
203 /// If \p Reg has no interval then this creates a new empty one instead.
204 /// Note: does not trigger interval computation.
208
209 /// Interval removal.
211 LiveInterval *&Interval = VirtRegIntervals[Reg];
212 assert(Interval && "removing a nonexistent interval");
213 Interval->~LiveInterval();
214 IntervalRecycler.Deallocate(RangeAllocator, Interval);
215 Interval = nullptr;
216 }
217
218 /// Given a register and an instruction, adds a live segment from that
219 /// instruction to the end of its MBB.
222
223 /// After removing some uses of a register, shrink its live range to just
224 /// the remaining uses. This method does not compute reaching defs for new
225 /// uses, and it doesn't remove dead defs.
226 /// Dead PHIDef values are marked as unused. New dead machine instructions
227 /// are added to the dead vector. Returns true if the interval may have been
228 /// separated into multiple connected components. Only the subranges
229 /// overlapping \p SubRangeMask are shrunk.
231 SmallVectorImpl<MachineInstr *> *dead = nullptr,
232 LaneBitmask SubRangeMask = LaneBitmask::getAll());
233
234 /// Specialized version of
235 /// shrinkToUses(LiveInterval *li, SmallVectorImpl<MachineInstr*> *dead)
236 /// that works on a subregister live range and only looks at uses matching
237 /// the lane mask of the subregister range.
238 /// This may leave the subrange empty which needs to be cleaned up with
239 /// LiveInterval::removeEmptySubranges() afterwards.
241
242 /// Extend the live range \p LR to reach all points in \p Indices. The
243 /// points in the \p Indices array must be jointly dominated by the union
244 /// of the existing defs in \p LR and points in \p Undefs.
245 ///
246 /// PHI-defs are added as needed to maintain SSA form.
247 ///
248 /// If a SlotIndex in \p Indices is the end index of a basic block, \p LR
249 /// will be extended to be live out of the basic block.
250 /// If a SlotIndex in \p Indices is jointy dominated only by points in
251 /// \p Undefs, the live range will not be extended to that point.
252 ///
253 /// See also LiveRangeCalc::extend().
255 ArrayRef<SlotIndex> Undefs);
256
258 extendToIndices(LR, Indices, /*Undefs=*/{});
259 }
260
261 /// If \p LR has a live value at \p Kill, prune its live range by removing
262 /// any liveness reachable from Kill. Add live range end points to
263 /// EndPoints such that extendToIndices(LI, EndPoints) will reconstruct the
264 /// value's live range.
265 ///
266 /// Calling pruneValue() and extendToIndices() can be used to reconstruct
267 /// SSA form after adding defs to a virtual register.
269 SmallVectorImpl<SlotIndex> *EndPoints);
270
271 /// This function should not be used. Its intent is to tell you that you are
272 /// doing something wrong if you call pruneValue directly on a
273 /// LiveInterval. Indeed, you are supposed to call pruneValue on the main
274 /// LiveRange and all the LiveRanges of the subranges if any.
275 [[maybe_unused]] void pruneValue(LiveInterval &, SlotIndex,
278 "Use pruneValue on the main LiveRange and on each subrange");
279 }
280
281 SlotIndexes *getSlotIndexes() const { return Indexes; }
282
283 /// Remove intervals for virtual registers no instruction refers to any
284 /// more. Their segments sit on erased indexes. Returns the number removed.
286
287 /// Returns true if the specified machine instr has been removed or was
288 /// never entered in the map.
289 bool isNotInMIMap(const MachineInstr &Instr) const {
290 return !Indexes->hasIndex(Instr);
291 }
292
293 /// Returns the base index of the given instruction.
295 return Indexes->getInstructionIndex(Instr);
296 }
297
298 /// Returns the instruction associated with the given index.
300 return Indexes->getInstructionFromIndex(index);
301 }
302
303 /// Return the first index in the given basic block.
305 return Indexes->getMBBStartIdx(mbb);
306 }
307
308 /// Return the last index in the given basic block.
310 return Indexes->getMBBEndIdx(mbb);
311 }
312
313 bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const {
314 return LR.liveAt(getMBBStartIdx(mbb));
315 }
316
317 bool isLiveOutOfMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const {
318 return LR.liveAt(getMBBEndIdx(mbb).getPrevSlot());
319 }
320
322 return Indexes->getMBBFromIndex(index);
323 }
324
325 /// Adds an empty block \p MBB to the SlotIndexes and regmask maps.
327 insertMBBInMapsImpl(MBB, /*AssumeRegMaskEmpty=*/true);
328 }
329
330 /// After the tail of \p Orig has been sliced into \p SplitBB, updates the
331 /// SlotIndexes and regmask maps and re-slices \p Orig's regmask table across
332 /// the two blocks.
334 insertMBBInMapsImpl(&SplitBB, /*AssumeRegMaskEmpty=*/false);
335 reassignRegMaskSlots(Orig, SplitBB);
336 }
337
339 return Indexes->insertMachineInstrInMaps(MI);
340 }
341
344 for (MachineBasicBlock::iterator I = B; I != E; ++I)
345 Indexes->insertMachineInstrInMaps(*I);
346 }
347
349 Indexes->removeMachineInstrFromMaps(MI);
350 }
351
353 return Indexes->replaceMachineInstrInMaps(MI, NewMI);
354 }
355
356 VNInfo::Allocator &getVNInfoAllocator() { return VNInfoAllocator; }
357
358 /// Implement the dump method.
359 LLVM_ABI void print(raw_ostream &O) const;
360 LLVM_ABI void dump() const;
361
362 // For legacy pass to recompute liveness.
364 clear();
365 analyze(MF);
366 }
367
368 MachineDominatorTree &getDomTree() { return *DomTree; }
369
370 /// If LI is confined to a single basic block, return a pointer to that
371 /// block. If LI is live in to or out of any block, return NULL.
373
374 /// Returns true if VNI is killed by any PHI-def values in LI.
375 /// This may conservatively return true to avoid expensive computations.
376 LLVM_ABI bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const;
377
378 /// Add kill flags to any instruction that kills a virtual register.
379 LLVM_ABI void addKillFlags(const VirtRegMap *);
380
381 /// Call this method to notify LiveIntervals that instruction \p MI has been
382 /// moved within a basic block. This will update the live intervals for all
383 /// operands of \p MI. Moves between basic blocks are not supported.
384 ///
385 /// \param UpdateFlags Update live intervals for nonallocatable physregs.
386 LLVM_ABI void handleMove(MachineInstr &MI, bool UpdateFlags = false);
387
388 /// Update intervals of operands of all instructions in the newly
389 /// created bundle specified by \p BundleStart.
390 ///
391 /// \param UpdateFlags Update live intervals for nonallocatable physregs.
392 ///
393 /// Assumes existing liveness is accurate.
394 /// \pre BundleStart should be the first instruction in the Bundle.
395 /// \pre BundleStart should not have a have SlotIndex as one will be assigned.
397 bool UpdateFlags = false);
398
399 /// Update live intervals for instructions in a range of iterators. It is
400 /// intended for use after target hooks that may insert or remove
401 /// instructions, and is only efficient for a small number of instructions.
402 ///
403 /// OrigRegs is a vector of registers that were originally used by the
404 /// instructions in the range between the two iterators.
405 ///
406 /// Currently, the only changes that are supported are simple removal
407 /// and addition of uses.
411 ArrayRef<Register> OrigRegs);
412
413 // Register mask functions.
414 //
415 // Machine instructions may use a register mask operand to indicate that a
416 // large number of registers are clobbered by the instruction. This is
417 // typically used for calls.
418 //
419 // For compile time performance reasons, these clobbers are not recorded in
420 // the live intervals for individual physical registers. Instead,
421 // LiveIntervalAnalysis maintains a sorted list of instructions with
422 // register mask operands.
423
424 /// Returns a sorted array of slot indices of all instructions with
425 /// register mask operands.
426 ArrayRef<SlotIndex> getRegMaskSlots() const { return RegMaskSlots; }
427
428 /// Returns a sorted array of slot indices of all instructions with register
429 /// mask operands in the basic block numbered \p MBBNum.
431 std::pair<unsigned, unsigned> P = RegMaskBlocks[MBBNum];
432 return getRegMaskSlots().slice(P.first, P.second);
433 }
434
435 /// Returns an array of register mask pointers corresponding to
436 /// getRegMaskSlots().
437 ArrayRef<const uint32_t *> getRegMaskBits() const { return RegMaskBits; }
438
439 /// Returns an array of mask pointers corresponding to
440 /// getRegMaskSlotsInBlock(MBBNum).
442 std::pair<unsigned, unsigned> P = RegMaskBlocks[MBBNum];
443 return getRegMaskBits().slice(P.first, P.second);
444 }
445
446 /// Test if \p LI is live across any register mask instructions, and
447 /// compute a bit mask of physical registers that are not clobbered by any
448 /// of them.
449 ///
450 /// Returns false if \p LI doesn't cross any register mask instructions. In
451 /// that case, the bit vector is not filled in.
453 BitVector &UsableRegs);
454
455 // Register unit functions.
456 //
457 // Fixed interference occurs when MachineInstrs use physregs directly
458 // instead of virtual registers. This typically happens when passing
459 // arguments to a function call, or when instructions require operands in
460 // fixed registers.
461 //
462 // Each physreg has one or more register units, see MCRegisterInfo. We
463 // track liveness per register unit to handle aliasing registers more
464 // efficiently.
465
466 /// Return the live range for register unit \p Unit. It will be computed if
467 /// it doesn't exist.
468 LiveRange &getRegUnit(MCRegUnit Unit) {
469 LiveRange *LR = RegUnitRanges[static_cast<unsigned>(Unit)];
470 if (!LR) {
471 // Compute missing ranges on demand.
472 RegUnitRanges[static_cast<unsigned>(Unit)] = LR = createRegUnitRange();
473 computeRegUnitRange(*LR, Unit);
474 }
475 return *LR;
476 }
477
478 /// Return the live range for register unit \p Unit if it has already been
479 /// computed, or nullptr if it hasn't been computed yet.
480 LiveRange *getCachedRegUnit(MCRegUnit Unit) {
481 return RegUnitRanges[static_cast<unsigned>(Unit)];
482 }
483
484 const LiveRange *getCachedRegUnit(MCRegUnit Unit) const {
485 return RegUnitRanges[static_cast<unsigned>(Unit)];
486 }
487
488 /// Remove computed live range for register unit \p Unit. Subsequent uses
489 /// should rely on on-demand recomputation.
490 void removeRegUnit(MCRegUnit Unit) {
491 LiveRange *&LR = RegUnitRanges[static_cast<unsigned>(Unit)];
492 if (!LR)
493 return;
494 LR->~LiveRange();
495 RegUnitRangeRecycler.Deallocate(RangeAllocator, LR);
496 LR = nullptr;
497 }
498
499 /// Remove associated live ranges for the register units associated with \p
500 /// Reg. Subsequent uses should rely on on-demand recomputation. \note This
501 /// method can result in inconsistent liveness tracking if multiple phyical
502 /// registers share a regunit, and should be used cautiously.
504 for (MCRegUnit Unit : TRI->regunits(Reg))
505 removeRegUnit(Unit);
506 }
507
508 /// Remove value numbers and related live segments starting at position
509 /// \p Pos that are part of any liverange of physical register \p Reg or one
510 /// of its subregisters.
512
513 /// Remove value number and related live segments of \p LI and its subranges
514 /// that start at position \p Pos.
516
517 /// Split separate components in LiveInterval \p LI into separate intervals.
518 LLVM_ABI void
521
522 /// For live interval \p LI with correct SubRanges construct matching
523 /// information for the main live range. Expects the main live range to not
524 /// have any segments or value numbers.
526
527private:
528 /// Compute live intervals for all virtual registers.
529 void computeVirtRegs();
530
531 /// Compute RegMaskSlots and RegMaskBits.
532 void computeRegMasks();
533
534 /// Implementation of insertMBBInMaps(). \p MBB must contain no regmask
535 /// operands when \p AssumeRegMaskEmpty is true.
536 LLVM_ABI void insertMBBInMapsImpl(MachineBasicBlock *MBB,
537 bool AssumeRegMaskEmpty);
538
539 /// Updates the regmask table for \p Orig's instructions that are moved into
540 /// \p SplitBB, so that the table is sliced across both blocks.
541 LLVM_ABI void reassignRegMaskSlots(MachineBasicBlock &Orig,
542 MachineBasicBlock &SplitBB);
543
544 /// Walk the values in \p LI and check for dead values:
545 /// - Dead PHIDef values are marked as unused.
546 /// - Dead operands are marked as such.
547 /// - Completely dead machine instructions are added to the \p dead vector
548 /// if it is not nullptr.
549 /// Returns true if any PHI value numbers have been removed which may
550 /// have separated the interval into multiple connected components.
551 bool computeDeadValues(LiveInterval &LI,
553
554 LLVM_ABI LiveInterval *createInterval(Register Reg);
555 LLVM_ABI LiveRange *createRegUnitRange();
556
557 void printInstrs(raw_ostream &O) const;
558 void dumpInstrs() const;
559
560 void computeLiveInRegUnits();
561 LLVM_ABI void computeRegUnitRange(LiveRange &, MCRegUnit Unit);
562 LLVM_ABI bool computeVirtRegInterval(LiveInterval &);
563
564 using ShrinkToUsesWorkList = SmallVector<std::pair<SlotIndex, VNInfo *>, 16>;
565 void extendSegmentsToUses(LiveRange &Segments, ShrinkToUsesWorkList &WorkList,
566 Register Reg, LaneBitmask LaneMask);
567
568 using SubRangeUse = std::pair<SlotIndex, LaneBitmask>;
569 using SubRangeUseList = SmallVector<SubRangeUse, 16>;
570 void collectSubRangeUses(Register Reg, SubRangeUseList &Uses) const;
571 void shrinkSubRangeToUses(LiveInterval::SubRange &SR, Register Reg,
573
574 /// Helper function for repairIntervalsInRange(), walks backwards and
575 /// creates/modifies live segments in \p LR to match the operands found.
576 /// Only full operands or operands with subregisters matching \p LaneMask
577 /// are considered.
578 void repairOldRegInRange(MachineBasicBlock::iterator Begin,
580 const SlotIndex endIdx, LiveRange &LR, Register Reg,
581 LaneBitmask LaneMask = LaneBitmask::getAll());
582
583 class HMEditor;
584};
585
586class LiveIntervalsAnalysis : public AnalysisInfoMixin<LiveIntervalsAnalysis> {
588 LLVM_ABI static AnalysisKey Key;
589
590public:
594};
595
597 : public RequiredPassInfoMixin<LiveIntervalsPrinterPass> {
598 raw_ostream &OS;
599
600public:
601 explicit LiveIntervalsPrinterPass(raw_ostream &OS) : OS(OS) {}
604};
605
607 LiveIntervals LIS;
608
609public:
610 static char ID;
611
613
614 void getAnalysisUsage(AnalysisUsage &AU) const override;
615 void releaseMemory() override { LIS.clear(); }
616
617 /// Pass entry point; Calculates LiveIntervals.
618 bool runOnMachineFunction(MachineFunction &) override;
619
620 /// Implement the dump method.
621 void print(raw_ostream &O, const Module * = nullptr) const override {
622 LIS.print(O);
623 }
624
625 LiveIntervals &getLIS() { return LIS; }
626};
627
628} // end namespace llvm
629
630#endif
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock & MBB
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_ABI
Definition Compiler.h:211
IRTranslator LLVM IR MI
This file implements an indexed map.
A common definition of LaneBitmask for use in TableGen and CodeGen.
#define I(x, y, z)
Definition MD5.cpp:57
Register Reg
std::pair< uint64_t, uint64_t > Interval
#define P(N)
Remove Loads Into Fake Uses
This file defines the SmallVector class.
Represent the analysis usage information of a pass.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
A live range for subregisters.
LiveInterval - This class represents the liveness of a register, or stack slot.
LLVM_ABI Result run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
LiveIntervalsPrinterPass(raw_ostream &OS)
void print(raw_ostream &O, const Module *=nullptr) const override
Implement the dump method.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
LLVM_ABI void repairIntervalsInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, ArrayRef< Register > OrigRegs)
Update live intervals for instructions in a range of iterators.
void removeAllRegUnitsForPhysReg(MCRegister Reg)
Remove associated live ranges for the register units associated with Reg.
bool hasInterval(Register Reg) const
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
LLVM_ABI bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const
Returns true if VNI is killed by any PHI-def values in LI.
SlotIndex InsertMachineInstrInMaps(MachineInstr &MI)
LLVM_ABI bool checkRegMaskInterference(const LiveInterval &LI, BitVector &UsableRegs)
Test if LI is live across any register mask instructions, and compute a bit mask of physical register...
LiveIntervals(LiveIntervals &&)=default
LLVM_ABI void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block.
void insertMBBInMaps(MachineBasicBlock *MBB)
Adds an empty block MBB to the SlotIndexes and regmask maps.
SlotIndexes * getSlotIndexes() const
LLVM_ABI unsigned removeUnreferencedIntervals()
Remove intervals for virtual registers no instruction refers to any more.
const LiveInterval & getInterval(Register Reg) const
ArrayRef< const uint32_t * > getRegMaskBits() const
Returns an array of register mask pointers corresponding to getRegMaskSlots().
LiveInterval & getOrCreateEmptyInterval(Register Reg)
Return an existing interval for Reg.
void reanalyze(MachineFunction &MF)
MachineDominatorTree & getDomTree()
LLVM_ABI void addKillFlags(const VirtRegMap *)
Add kill flags to any instruction that kills a virtual register.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
void removeRegUnit(MCRegUnit Unit)
Remove computed live range for register unit Unit.
LLVM_ABI bool invalidate(MachineFunction &MF, const PreservedAnalyses &PA, MachineFunctionAnalysisManager::Invalidator &Inv)
void RemoveMachineInstrFromMaps(MachineInstr &MI)
VNInfo::Allocator & getVNInfoAllocator()
ArrayRef< const uint32_t * > getRegMaskBitsInBlock(unsigned MBBNum) const
Returns an array of mask pointers corresponding to getRegMaskSlotsInBlock(MBBNum).
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Return the last index in the given basic block.
static LLVM_ABI float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI, ProfileSummaryInfo *PSI=nullptr)
Calculate the spill weight to assign to a single instruction.
ArrayRef< SlotIndex > getRegMaskSlots() const
Returns a sorted array of slot indices of all instructions with register mask operands.
friend class LiveIntervalsWrapperPass
ArrayRef< SlotIndex > getRegMaskSlotsInBlock(unsigned MBBNum) const
Returns a sorted array of slot indices of all instructions with register mask operands in the basic b...
LiveInterval & getInterval(Register Reg)
void InsertMachineInstrRangeInMaps(MachineBasicBlock::iterator B, MachineBasicBlock::iterator E)
friend class LiveIntervalsAnalysis
LLVM_ABI void pruneValue(LiveRange &LR, SlotIndex Kill, SmallVectorImpl< SlotIndex > *EndPoints)
If LR has a live value at Kill, prune its live range by removing any liveness reachable from Kill.
LiveInterval & createAndComputeVirtRegInterval(Register Reg, bool &NeedSplit)
void removeInterval(Register Reg)
Interval removal.
bool isNotInMIMap(const MachineInstr &Instr) const
Returns true if the specified machine instr has been removed or was never entered in the map.
LLVM_ABI void handleMoveIntoNewBundle(MachineInstr &BundleStart, bool UpdateFlags=false)
Update intervals of operands of all instructions in the newly created bundle specified by BundleStart...
void pruneValue(LiveInterval &, SlotIndex, SmallVectorImpl< SlotIndex > *)
This function should not be used.
LiveRange & getRegUnit(MCRegUnit Unit)
Return the live range for register unit Unit.
LLVM_ABI bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr * > *dead=nullptr, LaneBitmask SubRangeMask=LaneBitmask::getAll())
After removing some uses of a register, shrink its live range to just the remaining uses.
LLVM_ABI MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
const LiveRange * getCachedRegUnit(MCRegUnit Unit) const
LiveRange * getCachedRegUnit(MCRegUnit Unit)
Return the live range for register unit Unit if it has already been computed, or nullptr if it hasn't...
LLVM_ABI void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)
Remove value number and related live segments of LI and its subranges that start at position Pos.
LLVM_ABI LiveInterval::Segment addSegmentToEndOfBlock(Register Reg, MachineInstr &startInst)
Given a register and an instruction, adds a live segment from that instruction to the end of its MBB.
LLVM_ABI void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range.
LiveInterval & createEmptyInterval(Register Reg)
Interval creation.
LLVM_ABI void extendToIndices(LiveRange &LR, ArrayRef< SlotIndex > Indices, ArrayRef< SlotIndex > Undefs)
Extend the live range LR to reach all points in Indices.
LLVM_ABI void dump() const
void extendToIndices(LiveRange &LR, ArrayRef< SlotIndex > Indices)
bool isLiveOutOfMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const
LLVM_ABI void print(raw_ostream &O) const
Implement the dump method.
LLVM_ABI void removePhysRegDefAt(MCRegister Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
void splitAt(MachineBasicBlock &Orig, MachineBasicBlock &SplitBB)
After the tail of Orig has been sliced into SplitBB, updates the SlotIndexes and regmask maps and re-...
LLVM_ABI void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl< LiveInterval * > &SplitLIs)
Split separate components in LiveInterval LI into separate intervals.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const
LiveInterval & createAndComputeVirtRegInterval(Register Reg)
SlotIndex ReplaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI)
This class represents the liveness of a register, stack slot, etc.
bool liveAt(SlotIndex index) const
Wrapper class representing physical registers. Should be passed by value.
Definition MCRegister.h:41
MachineInstrBundleIterator< MachineInstr > iterator
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Representation of each machine instruction.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:68
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
Analysis providing profile information.
Recycler - This class manages a linked-list of deallocated nodes and facilitates reusing deallocated ...
Definition Recycler.h:37
Wrapper class representing virtual and physical registers.
Definition Register.h:20
SlotIndex - An opaque wrapper around machine indexes.
Definition SlotIndexes.h:70
SlotIndexes pass.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
VNInfo - Value Number Information.
BumpPtrAllocator Allocator
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
@ Kill
The last use of a register.
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
BumpPtrAllocatorImpl<> BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition Allocator.h:391
@ End
Run the machine verifier once, at the end of the pipeline.
Definition CodeGen.h:320
A CRTP mix-in that provides informational APIs needed for analysis passes.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition Analysis.h:29
static constexpr LaneBitmask getAll()
Definition LaneBitmask.h:82
This represents a simple continuous liveness interval for a value.
A CRTP mix-in for passes that should not be skipped.