LLVM 20.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"
36#include <cassert>
37#include <cstdint>
38#include <utility>
39
40namespace llvm {
41
42extern cl::opt<bool> UseSegmentSetForPhysRegs;
43
44class BitVector;
45class MachineBlockFrequencyInfo;
46class MachineDominatorTree;
47class MachineFunction;
48class MachineInstr;
49class MachineRegisterInfo;
50class raw_ostream;
51class TargetInstrInfo;
52class VirtRegMap;
53
57
58 MachineFunction *MF = nullptr;
59 MachineRegisterInfo *MRI = nullptr;
60 const TargetRegisterInfo *TRI = nullptr;
61 const TargetInstrInfo *TII = nullptr;
62 SlotIndexes *Indexes = nullptr;
63 MachineDominatorTree *DomTree = nullptr;
64 std::unique_ptr<LiveIntervalCalc> LICalc;
65
66 /// Special pool allocator for VNInfo's (LiveInterval val#).
67 VNInfo::Allocator VNInfoAllocator;
68
69 /// Live interval pointers for all the virtual registers.
71
72 /// Sorted list of instructions with register mask operands. Always use the
73 /// 'r' slot, RegMasks are normal clobbers, not early clobbers.
74 SmallVector<SlotIndex, 8> RegMaskSlots;
75
76 /// This vector is parallel to RegMaskSlots, it holds a pointer to the
77 /// corresponding register mask. This pointer can be recomputed as:
78 ///
79 /// MI = Indexes->getInstructionFromIndex(RegMaskSlot[N]);
80 /// unsigned OpNum = findRegMaskOperand(MI);
81 /// RegMaskBits[N] = MI->getOperand(OpNum).getRegMask();
82 ///
83 /// This is kept in a separate vector partly because some standard
84 /// libraries don't support lower_bound() with mixed objects, partly to
85 /// improve locality when searching in RegMaskSlots.
86 /// Also see the comment in LiveInterval::find().
88
89 /// For each basic block number, keep (begin, size) pairs indexing into the
90 /// RegMaskSlots and RegMaskBits arrays.
91 /// Note that basic block numbers may not be layout contiguous, that's why
92 /// we can't just keep track of the first register mask in each basic
93 /// block.
95
96 /// Keeps a live range set for each register unit to track fixed physreg
97 /// interference.
98 SmallVector<LiveRange *, 0> RegUnitRanges;
99
100 // Can only be created from pass manager.
101 LiveIntervals() = default;
103 : Indexes(&SI), DomTree(&DT) {
104 analyze(MF);
105 }
106
107 void analyze(MachineFunction &MF);
108
109 void clear();
110
111public:
114
115 /// Calculate the spill weight to assign to a single instruction.
116 static float getSpillWeight(bool isDef, bool isUse,
117 const MachineBlockFrequencyInfo *MBFI,
118 const MachineInstr &MI);
119
120 /// Calculate the spill weight to assign to a single instruction.
121 static float getSpillWeight(bool isDef, bool isUse,
122 const MachineBlockFrequencyInfo *MBFI,
123 const MachineBasicBlock *MBB);
124
126 if (hasInterval(Reg))
127 return *VirtRegIntervals[Reg.id()];
128
130 }
131
133 return const_cast<LiveIntervals *>(this)->getInterval(Reg);
134 }
135
137 return VirtRegIntervals.inBounds(Reg.id()) && VirtRegIntervals[Reg.id()];
138 }
139
140 /// Interval creation.
142 assert(!hasInterval(Reg) && "Interval already exists!");
143 VirtRegIntervals.grow(Reg.id());
144 VirtRegIntervals[Reg.id()] = createInterval(Reg);
145 return *VirtRegIntervals[Reg.id()];
146 }
147
150 computeVirtRegInterval(LI);
151 return LI;
152 }
153
154 /// Return an existing interval for \p Reg.
155 /// If \p Reg has no interval then this creates a new empty one instead.
156 /// Note: does not trigger interval computation.
159 }
160
161 /// Interval removal.
163 delete VirtRegIntervals[Reg];
164 VirtRegIntervals[Reg] = nullptr;
165 }
166
167 /// Given a register and an instruction, adds a live segment from that
168 /// instruction to the end of its MBB.
170 MachineInstr &startInst);
171
172 /// After removing some uses of a register, shrink its live range to just
173 /// the remaining uses. This method does not compute reaching defs for new
174 /// uses, and it doesn't remove dead defs.
175 /// Dead PHIDef values are marked as unused. New dead machine instructions
176 /// are added to the dead vector. Returns true if the interval may have been
177 /// separated into multiple connected components.
178 bool shrinkToUses(LiveInterval *li,
179 SmallVectorImpl<MachineInstr *> *dead = nullptr);
180
181 /// Specialized version of
182 /// shrinkToUses(LiveInterval *li, SmallVectorImpl<MachineInstr*> *dead)
183 /// that works on a subregister live range and only looks at uses matching
184 /// the lane mask of the subregister range.
185 /// This may leave the subrange empty which needs to be cleaned up with
186 /// LiveInterval::removeEmptySubranges() afterwards.
188
189 /// Extend the live range \p LR to reach all points in \p Indices. The
190 /// points in the \p Indices array must be jointly dominated by the union
191 /// of the existing defs in \p LR and points in \p Undefs.
192 ///
193 /// PHI-defs are added as needed to maintain SSA form.
194 ///
195 /// If a SlotIndex in \p Indices is the end index of a basic block, \p LR
196 /// will be extended to be live out of the basic block.
197 /// If a SlotIndex in \p Indices is jointy dominated only by points in
198 /// \p Undefs, the live range will not be extended to that point.
199 ///
200 /// See also LiveRangeCalc::extend().
202 ArrayRef<SlotIndex> Undefs);
203
205 extendToIndices(LR, Indices, /*Undefs=*/{});
206 }
207
208 /// If \p LR has a live value at \p Kill, prune its live range by removing
209 /// any liveness reachable from Kill. Add live range end points to
210 /// EndPoints such that extendToIndices(LI, EndPoints) will reconstruct the
211 /// value's live range.
212 ///
213 /// Calling pruneValue() and extendToIndices() can be used to reconstruct
214 /// SSA form after adding defs to a virtual register.
215 void pruneValue(LiveRange &LR, SlotIndex Kill,
216 SmallVectorImpl<SlotIndex> *EndPoints);
217
218 /// This function should not be used. Its intent is to tell you that you are
219 /// doing something wrong if you call pruneValue directly on a
220 /// LiveInterval. Indeed, you are supposed to call pruneValue on the main
221 /// LiveRange and all the LiveRanges of the subranges if any.
225 "Use pruneValue on the main LiveRange and on each subrange");
226 }
227
228 SlotIndexes *getSlotIndexes() const { return Indexes; }
229
230 /// Returns true if the specified machine instr has been removed or was
231 /// never entered in the map.
232 bool isNotInMIMap(const MachineInstr &Instr) const {
233 return !Indexes->hasIndex(Instr);
234 }
235
236 /// Returns the base index of the given instruction.
238 return Indexes->getInstructionIndex(Instr);
239 }
240
241 /// Returns the instruction associated with the given index.
243 return Indexes->getInstructionFromIndex(index);
244 }
245
246 /// Return the first index in the given basic block.
248 return Indexes->getMBBStartIdx(mbb);
249 }
250
251 /// Return the last index in the given basic block.
253 return Indexes->getMBBEndIdx(mbb);
254 }
255
256 bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const {
257 return LR.liveAt(getMBBStartIdx(mbb));
258 }
259
260 bool isLiveOutOfMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const {
261 return LR.liveAt(getMBBEndIdx(mbb).getPrevSlot());
262 }
263
265 return Indexes->getMBBFromIndex(index);
266 }
267
269 Indexes->insertMBBInMaps(MBB);
270 assert(unsigned(MBB->getNumber()) == RegMaskBlocks.size() &&
271 "Blocks must be added in order.");
272 RegMaskBlocks.push_back(std::make_pair(RegMaskSlots.size(), 0));
273 }
274
276 return Indexes->insertMachineInstrInMaps(MI);
277 }
278
281 for (MachineBasicBlock::iterator I = B; I != E; ++I)
282 Indexes->insertMachineInstrInMaps(*I);
283 }
284
287 }
288
290 return Indexes->replaceMachineInstrInMaps(MI, NewMI);
291 }
292
293 VNInfo::Allocator &getVNInfoAllocator() { return VNInfoAllocator; }
294
295 /// Implement the dump method.
296 void print(raw_ostream &O) const;
297 void dump() const;
298
299 // For legacy pass to recompute liveness.
301 clear();
302 analyze(MF);
303 }
304
305 MachineDominatorTree &getDomTree() { return *DomTree; }
306
307 /// If LI is confined to a single basic block, return a pointer to that
308 /// block. If LI is live in to or out of any block, return NULL.
310
311 /// Returns true if VNI is killed by any PHI-def values in LI.
312 /// This may conservatively return true to avoid expensive computations.
313 bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const;
314
315 /// Add kill flags to any instruction that kills a virtual register.
316 void addKillFlags(const VirtRegMap *);
317
318 /// Call this method to notify LiveIntervals that instruction \p MI has been
319 /// moved within a basic block. This will update the live intervals for all
320 /// operands of \p MI. Moves between basic blocks are not supported.
321 ///
322 /// \param UpdateFlags Update live intervals for nonallocatable physregs.
323 void handleMove(MachineInstr &MI, bool UpdateFlags = false);
324
325 /// Update intervals of operands of all instructions in the newly
326 /// created bundle specified by \p BundleStart.
327 ///
328 /// \param UpdateFlags Update live intervals for nonallocatable physregs.
329 ///
330 /// Assumes existing liveness is accurate.
331 /// \pre BundleStart should be the first instruction in the Bundle.
332 /// \pre BundleStart should not have a have SlotIndex as one will be assigned.
333 void handleMoveIntoNewBundle(MachineInstr &BundleStart,
334 bool UpdateFlags = false);
335
336 /// Update live intervals for instructions in a range of iterators. It is
337 /// intended for use after target hooks that may insert or remove
338 /// instructions, and is only efficient for a small number of instructions.
339 ///
340 /// OrigRegs is a vector of registers that were originally used by the
341 /// instructions in the range between the two iterators.
342 ///
343 /// Currently, the only changes that are supported are simple removal
344 /// and addition of uses.
348 ArrayRef<Register> OrigRegs);
349
350 // Register mask functions.
351 //
352 // Machine instructions may use a register mask operand to indicate that a
353 // large number of registers are clobbered by the instruction. This is
354 // typically used for calls.
355 //
356 // For compile time performance reasons, these clobbers are not recorded in
357 // the live intervals for individual physical registers. Instead,
358 // LiveIntervalAnalysis maintains a sorted list of instructions with
359 // register mask operands.
360
361 /// Returns a sorted array of slot indices of all instructions with
362 /// register mask operands.
363 ArrayRef<SlotIndex> getRegMaskSlots() const { return RegMaskSlots; }
364
365 /// Returns a sorted array of slot indices of all instructions with register
366 /// mask operands in the basic block numbered \p MBBNum.
368 std::pair<unsigned, unsigned> P = RegMaskBlocks[MBBNum];
369 return getRegMaskSlots().slice(P.first, P.second);
370 }
371
372 /// Returns an array of register mask pointers corresponding to
373 /// getRegMaskSlots().
374 ArrayRef<const uint32_t *> getRegMaskBits() const { return RegMaskBits; }
375
376 /// Returns an array of mask pointers corresponding to
377 /// getRegMaskSlotsInBlock(MBBNum).
379 std::pair<unsigned, unsigned> P = RegMaskBlocks[MBBNum];
380 return getRegMaskBits().slice(P.first, P.second);
381 }
382
383 /// Test if \p LI is live across any register mask instructions, and
384 /// compute a bit mask of physical registers that are not clobbered by any
385 /// of them.
386 ///
387 /// Returns false if \p LI doesn't cross any register mask instructions. In
388 /// that case, the bit vector is not filled in.
389 bool checkRegMaskInterference(const LiveInterval &LI, BitVector &UsableRegs);
390
391 // Register unit functions.
392 //
393 // Fixed interference occurs when MachineInstrs use physregs directly
394 // instead of virtual registers. This typically happens when passing
395 // arguments to a function call, or when instructions require operands in
396 // fixed registers.
397 //
398 // Each physreg has one or more register units, see MCRegisterInfo. We
399 // track liveness per register unit to handle aliasing registers more
400 // efficiently.
401
402 /// Return the live range for register unit \p Unit. It will be computed if
403 /// it doesn't exist.
404 LiveRange &getRegUnit(unsigned Unit) {
405 LiveRange *LR = RegUnitRanges[Unit];
406 if (!LR) {
407 // Compute missing ranges on demand.
408 // Use segment set to speed-up initial computation of the live range.
409 RegUnitRanges[Unit] = LR = new LiveRange(UseSegmentSetForPhysRegs);
410 computeRegUnitRange(*LR, Unit);
411 }
412 return *LR;
413 }
414
415 /// Return the live range for register unit \p Unit if it has already been
416 /// computed, or nullptr if it hasn't been computed yet.
417 LiveRange *getCachedRegUnit(unsigned Unit) { return RegUnitRanges[Unit]; }
418
419 const LiveRange *getCachedRegUnit(unsigned Unit) const {
420 return RegUnitRanges[Unit];
421 }
422
423 /// Remove computed live range for register unit \p Unit. Subsequent uses
424 /// should rely on on-demand recomputation.
425 void removeRegUnit(unsigned Unit) {
426 delete RegUnitRanges[Unit];
427 RegUnitRanges[Unit] = nullptr;
428 }
429
430 /// Remove associated live ranges for the register units associated with \p
431 /// Reg. Subsequent uses should rely on on-demand recomputation. \note This
432 /// method can result in inconsistent liveness tracking if multiple phyical
433 /// registers share a regunit, and should be used cautiously.
435 for (MCRegUnit Unit : TRI->regunits(Reg))
436 removeRegUnit(Unit);
437 }
438
439 /// Remove value numbers and related live segments starting at position
440 /// \p Pos that are part of any liverange of physical register \p Reg or one
441 /// of its subregisters.
443
444 /// Remove value number and related live segments of \p LI and its subranges
445 /// that start at position \p Pos.
447
448 /// Split separate components in LiveInterval \p LI into separate intervals.
451
452 /// For live interval \p LI with correct SubRanges construct matching
453 /// information for the main live range. Expects the main live range to not
454 /// have any segments or value numbers.
456
457private:
458 /// Compute live intervals for all virtual registers.
459 void computeVirtRegs();
460
461 /// Compute RegMaskSlots and RegMaskBits.
462 void computeRegMasks();
463
464 /// Walk the values in \p LI and check for dead values:
465 /// - Dead PHIDef values are marked as unused.
466 /// - Dead operands are marked as such.
467 /// - Completely dead machine instructions are added to the \p dead vector
468 /// if it is not nullptr.
469 /// Returns true if any PHI value numbers have been removed which may
470 /// have separated the interval into multiple connected components.
471 bool computeDeadValues(LiveInterval &LI,
473
474 static LiveInterval *createInterval(Register Reg);
475
476 void printInstrs(raw_ostream &O) const;
477 void dumpInstrs() const;
478
479 void computeLiveInRegUnits();
480 void computeRegUnitRange(LiveRange &, unsigned Unit);
481 bool computeVirtRegInterval(LiveInterval &);
482
483 using ShrinkToUsesWorkList = SmallVector<std::pair<SlotIndex, VNInfo *>, 16>;
484 void extendSegmentsToUses(LiveRange &Segments, ShrinkToUsesWorkList &WorkList,
485 Register Reg, LaneBitmask LaneMask);
486
487 /// Helper function for repairIntervalsInRange(), walks backwards and
488 /// creates/modifies live segments in \p LR to match the operands found.
489 /// Only full operands or operands with subregisters matching \p LaneMask
490 /// are considered.
491 void repairOldRegInRange(MachineBasicBlock::iterator Begin,
493 const SlotIndex endIdx, LiveRange &LR, Register Reg,
494 LaneBitmask LaneMask = LaneBitmask::getAll());
495
496 class HMEditor;
497};
498
499class LiveIntervalsAnalysis : public AnalysisInfoMixin<LiveIntervalsAnalysis> {
501 static AnalysisKey Key;
502
503public:
506};
507
509 : public PassInfoMixin<LiveIntervalsPrinterPass> {
510 raw_ostream &OS;
511
512public:
516 static bool isRequired() { return true; }
517};
518
520 LiveIntervals LIS;
521
522public:
523 static char ID;
524
526
527 void getAnalysisUsage(AnalysisUsage &AU) const override;
528 void releaseMemory() override { LIS.clear(); }
529
530 /// Pass entry point; Calculates LiveIntervals.
531 bool runOnMachineFunction(MachineFunction &) override;
532
533 /// Implement the dump method.
534 void print(raw_ostream &O, const Module * = nullptr) const override {
535 LIS.print(O);
536 }
537
538 LiveIntervals &getLIS() { return LIS; }
539};
540
541} // end namespace llvm
542
543#endif
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:203
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:148
bool End
Definition: ELF_riscv.cpp:480
const HexagonInstrInfo * TII
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:58
unsigned const TargetRegisterInfo * TRI
unsigned Reg
#define P(N)
StandardInstrumentations SI(Mod->getContext(), Debug, VerifyEach)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI Optimize VGPR LiveRange
raw_pwrite_stream & OS
This file defines the SmallVector class.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
Represent the analysis usage information of a pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
void grow(IndexT n)
Definition: IndexedMap.h:69
bool inBounds(IndexT n) const
Definition: IndexedMap.h:75
A live range for subregisters.
Definition: LiveInterval.h:694
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:687
Result run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
LiveIntervalsPrinterPass(raw_ostream &OS)
bool runOnMachineFunction(MachineFunction &) override
Pass entry point; Calculates LiveIntervals.
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...
const LiveRange * getCachedRegUnit(unsigned Unit) const
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.
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)
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
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)
SlotIndexes * getSlotIndexes() const
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()
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 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.
ArrayRef< SlotIndex > getRegMaskSlots() const
Returns a sorted array of slot indices of all instructions with register mask operands.
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
ArrayRef< SlotIndex > getRegMaskSlotsInBlock(unsigned MBBNum) const
Returns a sorted array of slot indices of all instructions with register mask operands in the basic b...
LiveRange * getCachedRegUnit(unsigned Unit)
Return the live range for register unit Unit if it has already been computed, or nullptr if it hasn't...
LiveInterval & getInterval(Register Reg)
void InsertMachineInstrRangeInMaps(MachineBasicBlock::iterator B, MachineBasicBlock::iterator E)
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.
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.
void handleMoveIntoNewBundle(MachineInstr &BundleStart, bool UpdateFlags=false)
Update intervals of operands of all instructions in the newly created bundle specified by BundleStart...
MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)
Remove value number and related live segments of LI and its subranges that start at position Pos.
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.
void removeRegUnit(unsigned Unit)
Remove computed live range for register unit Unit.
bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr * > *dead=nullptr)
After removing some uses of a register, shrink its live range to just the remaining uses.
void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range.
static float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI)
Calculate the spill weight to assign to a single instruction.
LiveInterval & createEmptyInterval(Register Reg)
Interval creation.
void extendToIndices(LiveRange &LR, ArrayRef< SlotIndex > Indices, ArrayRef< SlotIndex > Undefs)
Extend the live range LR to reach all points in Indices.
void extendToIndices(LiveRange &LR, ArrayRef< SlotIndex > Indices)
bool isLiveOutOfMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const
void print(raw_ostream &O) const
Implement the dump method.
LLVM_ATTRIBUTE_UNUSED void pruneValue(LiveInterval &, SlotIndex, SmallVectorImpl< SlotIndex > *)
This function should not be used.
void removePhysRegDefAt(MCRegister Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
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.
Definition: LiveInterval.h:157
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:401
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:33
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Representation of each machine instruction.
Definition: MachineInstr.h:69
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:65
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:65
SlotIndexes pass.
Definition: SlotIndexes.h:297
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
Definition: SlotIndexes.h:531
void removeMachineInstrFromMaps(MachineInstr &MI, bool AllowBundled=false)
Removes machine instruction (bundle) MI from the mapping.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
Definition: SlotIndexes.h:515
void insertMBBInMaps(MachineBasicBlock *mbb)
Add the given MachineBasicBlock into the maps.
Definition: SlotIndexes.h:606
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:470
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:379
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:460
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
Definition: SlotIndexes.h:374
SlotIndex replaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI)
ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in maps used by register allocat...
Definition: SlotIndexes.h:588
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
Definition: SlotIndexes.h:397
size_t size() const
Definition: SmallVector.h:92
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:587
void push_back(const T &Elt)
Definition: SmallVector.h:427
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
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.
Definition: LiveInterval.h:53
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
#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.
Definition: AddressRanges.h:18
cl::opt< bool > UseSegmentSetForPhysRegs
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:92
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:28
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:82
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:69