LLVM  14.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"
24 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/MC/LaneBitmask.h"
32 #include "llvm/Support/Compiler.h"
34 #include <cassert>
35 #include <cstdint>
36 #include <utility>
37 
38 namespace llvm {
39 
40 extern cl::opt<bool> UseSegmentSetForPhysRegs;
41 
42 class AAResults;
43 class BitVector;
44 class LiveIntervalCalc;
45 class MachineBlockFrequencyInfo;
46 class MachineDominatorTree;
47 class MachineFunction;
48 class MachineInstr;
49 class MachineRegisterInfo;
50 class raw_ostream;
51 class TargetInstrInfo;
52 class VirtRegMap;
53 
55  MachineFunction* MF;
57  const TargetRegisterInfo* TRI;
58  const TargetInstrInfo* TII;
59  AAResults *AA;
60  SlotIndexes* Indexes;
61  MachineDominatorTree *DomTree = nullptr;
62  LiveIntervalCalc *LICalc = nullptr;
63 
64  /// Special pool allocator for VNInfo's (LiveInterval val#).
65  VNInfo::Allocator VNInfoAllocator;
66 
67  /// Live interval pointers for all the virtual registers.
69 
70  /// Sorted list of instructions with register mask operands. Always use the
71  /// 'r' slot, RegMasks are normal clobbers, not early clobbers.
72  SmallVector<SlotIndex, 8> RegMaskSlots;
73 
74  /// This vector is parallel to RegMaskSlots, it holds a pointer to the
75  /// corresponding register mask. This pointer can be 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().
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.
93 
94  /// Keeps a live range set for each register unit to track fixed physreg
95  /// interference.
96  SmallVector<LiveRange*, 0> RegUnitRanges;
97 
98  public:
99  static char ID;
100 
101  LiveIntervals();
102  ~LiveIntervals() override;
103 
104  /// Calculate the spill weight to assign to a single instruction.
105  static float getSpillWeight(bool isDef, bool isUse,
106  const MachineBlockFrequencyInfo *MBFI,
107  const MachineInstr &MI);
108 
109  /// Calculate the spill weight to assign to a single instruction.
110  static float getSpillWeight(bool isDef, bool isUse,
111  const MachineBlockFrequencyInfo *MBFI,
112  const MachineBasicBlock *MBB);
113 
115  if (hasInterval(Reg))
116  return *VirtRegIntervals[Reg.id()];
117 
119  }
120 
122  return const_cast<LiveIntervals*>(this)->getInterval(Reg);
123  }
124 
125  bool hasInterval(Register Reg) const {
126  return VirtRegIntervals.inBounds(Reg.id()) &&
127  VirtRegIntervals[Reg.id()];
128  }
129 
130  /// Interval creation.
132  assert(!hasInterval(Reg) && "Interval already exists!");
133  VirtRegIntervals.grow(Reg.id());
134  VirtRegIntervals[Reg.id()] = createInterval(Reg);
135  return *VirtRegIntervals[Reg.id()];
136  }
137 
140  computeVirtRegInterval(LI);
141  return LI;
142  }
143 
144  /// Interval removal.
146  delete VirtRegIntervals[Reg];
147  VirtRegIntervals[Reg] = nullptr;
148  }
149 
150  /// Given a register and an instruction, adds a live segment from that
151  /// instruction to the end of its MBB.
153  MachineInstr &startInst);
154 
155  /// After removing some uses of a register, shrink its live range to just
156  /// the remaining uses. This method does not compute reaching defs for new
157  /// uses, and it doesn't remove dead defs.
158  /// Dead PHIDef values are marked as unused. New dead machine instructions
159  /// are added to the dead vector. Returns true if the interval may have been
160  /// separated into multiple connected components.
161  bool shrinkToUses(LiveInterval *li,
162  SmallVectorImpl<MachineInstr*> *dead = nullptr);
163 
164  /// Specialized version of
165  /// shrinkToUses(LiveInterval *li, SmallVectorImpl<MachineInstr*> *dead)
166  /// that works on a subregister live range and only looks at uses matching
167  /// the lane mask of the subregister range.
168  /// This may leave the subrange empty which needs to be cleaned up with
169  /// LiveInterval::removeEmptySubranges() afterwards.
171 
172  /// Extend the live range \p LR to reach all points in \p Indices. The
173  /// points in the \p Indices array must be jointly dominated by the union
174  /// of the existing defs in \p LR and points in \p Undefs.
175  ///
176  /// PHI-defs are added as needed to maintain SSA form.
177  ///
178  /// If a SlotIndex in \p Indices is the end index of a basic block, \p LR
179  /// will be extended to be live out of the basic block.
180  /// If a SlotIndex in \p Indices is jointy dominated only by points in
181  /// \p Undefs, the live range will not be extended to that point.
182  ///
183  /// See also LiveRangeCalc::extend().
185  ArrayRef<SlotIndex> Undefs);
186 
188  extendToIndices(LR, Indices, /*Undefs=*/{});
189  }
190 
191  /// If \p LR has a live value at \p Kill, prune its live range by removing
192  /// any liveness reachable from Kill. Add live range end points to
193  /// EndPoints such that extendToIndices(LI, EndPoints) will reconstruct the
194  /// value's live range.
195  ///
196  /// Calling pruneValue() and extendToIndices() can be used to reconstruct
197  /// SSA form after adding defs to a virtual register.
199  SmallVectorImpl<SlotIndex> *EndPoints);
200 
201  /// This function should not be used. Its intent is to tell you that you are
202  /// doing something wrong if you call pruneValue directly on a
203  /// LiveInterval. Indeed, you are supposed to call pruneValue on the main
204  /// LiveRange and all the LiveRanges of the subranges if any.
208  "Use pruneValue on the main LiveRange and on each subrange");
209  }
210 
212  return Indexes;
213  }
214 
216  return AA;
217  }
218 
219  /// Returns true if the specified machine instr has been removed or was
220  /// never entered in the map.
221  bool isNotInMIMap(const MachineInstr &Instr) const {
222  return !Indexes->hasIndex(Instr);
223  }
224 
225  /// Returns the base index of the given instruction.
227  return Indexes->getInstructionIndex(Instr);
228  }
229 
230  /// Returns the instruction associated with the given index.
232  return Indexes->getInstructionFromIndex(index);
233  }
234 
235  /// Return the first index in the given basic block.
237  return Indexes->getMBBStartIdx(mbb);
238  }
239 
240  /// Return the last index in the given basic block.
242  return Indexes->getMBBEndIdx(mbb);
243  }
244 
245  bool isLiveInToMBB(const LiveRange &LR,
246  const MachineBasicBlock *mbb) const {
247  return LR.liveAt(getMBBStartIdx(mbb));
248  }
249 
250  bool isLiveOutOfMBB(const LiveRange &LR,
251  const MachineBasicBlock *mbb) const {
252  return LR.liveAt(getMBBEndIdx(mbb).getPrevSlot());
253  }
254 
256  return Indexes->getMBBFromIndex(index);
257  }
258 
260  Indexes->insertMBBInMaps(MBB);
261  assert(unsigned(MBB->getNumber()) == RegMaskBlocks.size() &&
262  "Blocks must be added in order.");
263  RegMaskBlocks.push_back(std::make_pair(RegMaskSlots.size(), 0));
264  }
265 
267  return Indexes->insertMachineInstrInMaps(MI);
268  }
269 
272  for (MachineBasicBlock::iterator I = B; I != E; ++I)
273  Indexes->insertMachineInstrInMaps(*I);
274  }
275 
277  Indexes->removeMachineInstrFromMaps(MI);
278  }
279 
281  return Indexes->replaceMachineInstrInMaps(MI, NewMI);
282  }
283 
284  VNInfo::Allocator& getVNInfoAllocator() { return VNInfoAllocator; }
285 
286  void getAnalysisUsage(AnalysisUsage &AU) const override;
287  void releaseMemory() override;
288 
289  /// Pass entry point; Calculates LiveIntervals.
290  bool runOnMachineFunction(MachineFunction&) override;
291 
292  /// Implement the dump method.
293  void print(raw_ostream &O, const Module* = nullptr) const override;
294 
295  /// If LI is confined to a single basic block, return a pointer to that
296  /// block. If LI is live in to or out of any block, return NULL.
298 
299  /// Returns true if VNI is killed by any PHI-def values in LI.
300  /// This may conservatively return true to avoid expensive computations.
301  bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const;
302 
303  /// Add kill flags to any instruction that kills a virtual register.
304  void addKillFlags(const VirtRegMap*);
305 
306  /// Call this method to notify LiveIntervals that instruction \p MI has been
307  /// moved within a basic block. This will update the live intervals for all
308  /// operands of \p MI. Moves between basic blocks are not supported.
309  ///
310  /// \param UpdateFlags Update live intervals for nonallocatable physregs.
311  void handleMove(MachineInstr &MI, bool UpdateFlags = false);
312 
313  /// Update intervals of operands of all instructions in the newly
314  /// created bundle specified by \p BundleStart.
315  ///
316  /// \param UpdateFlags Update live intervals for nonallocatable physregs.
317  ///
318  /// Assumes existing liveness is accurate.
319  /// \pre BundleStart should be the first instruction in the Bundle.
320  /// \pre BundleStart should not have a have SlotIndex as one will be assigned.
321  void handleMoveIntoNewBundle(MachineInstr &BundleStart,
322  bool UpdateFlags = false);
323 
324  /// Update live intervals for instructions in a range of iterators. It is
325  /// intended for use after target hooks that may insert or remove
326  /// instructions, and is only efficient for a small number of instructions.
327  ///
328  /// OrigRegs is a vector of registers that were originally used by the
329  /// instructions in the range between the two iterators.
330  ///
331  /// Currently, the only only changes that are supported are simple removal
332  /// and addition of uses.
336  ArrayRef<Register> OrigRegs);
337 
338  // Register mask functions.
339  //
340  // Machine instructions may use a register mask operand to indicate that a
341  // large number of registers are clobbered by the instruction. This is
342  // typically used for calls.
343  //
344  // For compile time performance reasons, these clobbers are not recorded in
345  // the live intervals for individual physical registers. Instead,
346  // LiveIntervalAnalysis maintains a sorted list of instructions with
347  // register mask operands.
348 
349  /// Returns a sorted array of slot indices of all instructions with
350  /// register mask operands.
351  ArrayRef<SlotIndex> getRegMaskSlots() const { return RegMaskSlots; }
352 
353  /// Returns a sorted array of slot indices of all instructions with register
354  /// mask operands in the basic block numbered \p MBBNum.
356  std::pair<unsigned, unsigned> P = RegMaskBlocks[MBBNum];
357  return getRegMaskSlots().slice(P.first, P.second);
358  }
359 
360  /// Returns an array of register mask pointers corresponding to
361  /// getRegMaskSlots().
362  ArrayRef<const uint32_t*> getRegMaskBits() const { return RegMaskBits; }
363 
364  /// Returns an array of mask pointers corresponding to
365  /// getRegMaskSlotsInBlock(MBBNum).
367  std::pair<unsigned, unsigned> P = RegMaskBlocks[MBBNum];
368  return getRegMaskBits().slice(P.first, P.second);
369  }
370 
371  /// Test if \p LI is live across any register mask instructions, and
372  /// compute a bit mask of physical registers that are not clobbered by any
373  /// of them.
374  ///
375  /// Returns false if \p LI doesn't cross any register mask instructions. In
376  /// that case, the bit vector is not filled in.
378  BitVector &UsableRegs);
379 
380  // Register unit functions.
381  //
382  // Fixed interference occurs when MachineInstrs use physregs directly
383  // instead of virtual registers. This typically happens when passing
384  // arguments to a function call, or when instructions require operands in
385  // fixed registers.
386  //
387  // Each physreg has one or more register units, see MCRegisterInfo. We
388  // track liveness per register unit to handle aliasing registers more
389  // efficiently.
390 
391  /// Return the live range for register unit \p Unit. It will be computed if
392  /// it doesn't exist.
393  LiveRange &getRegUnit(unsigned Unit) {
394  LiveRange *LR = RegUnitRanges[Unit];
395  if (!LR) {
396  // Compute missing ranges on demand.
397  // Use segment set to speed-up initial computation of the live range.
398  RegUnitRanges[Unit] = LR = new LiveRange(UseSegmentSetForPhysRegs);
399  computeRegUnitRange(*LR, Unit);
400  }
401  return *LR;
402  }
403 
404  /// Return the live range for register unit \p Unit if it has already been
405  /// computed, or nullptr if it hasn't been computed yet.
406  LiveRange *getCachedRegUnit(unsigned Unit) {
407  return RegUnitRanges[Unit];
408  }
409 
410  const LiveRange *getCachedRegUnit(unsigned Unit) const {
411  return RegUnitRanges[Unit];
412  }
413 
414  /// Remove computed live range for register unit \p Unit. Subsequent uses
415  /// should rely on on-demand recomputation.
416  void removeRegUnit(unsigned Unit) {
417  delete RegUnitRanges[Unit];
418  RegUnitRanges[Unit] = nullptr;
419  }
420 
421  /// Remove associated live ranges for the register units associated with \p
422  /// Reg. Subsequent uses should rely on on-demand recomputation. \note This
423  /// method can result in inconsistent liveness tracking if multiple phyical
424  /// registers share a regunit, and should be used cautiously.
426  for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
427  removeRegUnit(*Units);
428  }
429 
430  /// Remove value numbers and related live segments starting at position
431  /// \p Pos that are part of any liverange of physical register \p Reg or one
432  /// of its subregisters.
434 
435  /// Remove value number and related live segments of \p LI and its subranges
436  /// that start at position \p Pos.
437  void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos);
438 
439  /// Split separate components in LiveInterval \p LI into separate intervals.
442 
443  /// For live interval \p LI with correct SubRanges construct matching
444  /// information for the main live range. Expects the main live range to not
445  /// have any segments or value numbers.
447 
448  private:
449  /// Compute live intervals for all virtual registers.
450  void computeVirtRegs();
451 
452  /// Compute RegMaskSlots and RegMaskBits.
453  void computeRegMasks();
454 
455  /// Walk the values in \p LI and check for dead values:
456  /// - Dead PHIDef values are marked as unused.
457  /// - Dead operands are marked as such.
458  /// - Completely dead machine instructions are added to the \p dead vector
459  /// if it is not nullptr.
460  /// Returns true if any PHI value numbers have been removed which may
461  /// have separated the interval into multiple connected components.
462  bool computeDeadValues(LiveInterval &LI,
464 
465  static LiveInterval *createInterval(Register Reg);
466 
467  void printInstrs(raw_ostream &O) const;
468  void dumpInstrs() const;
469 
470  void computeLiveInRegUnits();
471  void computeRegUnitRange(LiveRange&, unsigned Unit);
472  bool computeVirtRegInterval(LiveInterval&);
473 
474  using ShrinkToUsesWorkList = SmallVector<std::pair<SlotIndex, VNInfo*>, 16>;
475  void extendSegmentsToUses(LiveRange &Segments,
476  ShrinkToUsesWorkList &WorkList, Register Reg,
477  LaneBitmask LaneMask);
478 
479  /// Helper function for repairIntervalsInRange(), walks backwards and
480  /// creates/modifies live segments in \p LR to match the operands found.
481  /// Only full operands or operands with subregisters matching \p LaneMask
482  /// are considered.
483  void repairOldRegInRange(MachineBasicBlock::iterator Begin,
485  const SlotIndex endIdx, LiveRange &LR,
486  Register Reg,
487  LaneBitmask LaneMask = LaneBitmask::getAll());
488 
489  class HMEditor;
490  };
491 
492 } // end namespace llvm
493 
494 #endif
llvm::LaneBitmask
Definition: LaneBitmask.h:40
llvm::LiveIntervals::addSegmentToEndOfBlock
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.
Definition: LiveIntervals.cpp:881
IndexedMap.h
llvm::SlotIndexes::insertMBBInMaps
void insertMBBInMaps(MachineBasicBlock *mbb)
Add the given MachineBasicBlock into the maps.
Definition: SlotIndexes.h:610
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:102
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::LiveIntervals::getSlotIndexes
SlotIndexes * getSlotIndexes() const
Definition: LiveIntervals.h:211
llvm::LiveIntervals::isLiveInToMBB
bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const
Definition: LiveIntervals.h:245
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::LiveIntervals::isNotInMIMap
bool isNotInMIMap(const MachineInstr &Instr) const
Returns true if the specified machine instr has been removed or was never entered in the map.
Definition: LiveIntervals.h:221
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::LiveIntervals::getRegMaskSlotsInBlock
ArrayRef< SlotIndex > getRegMaskSlotsInBlock(unsigned MBBNum) const
Returns a sorted array of slot indices of all instructions with register mask operands in the basic b...
Definition: LiveIntervals.h:355
llvm::LiveIntervals::getInstructionFromIndex
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
Definition: LiveIntervals.h:231
ErrorHandling.h
llvm::VirtRegMap
Definition: VirtRegMap.h:33
llvm::LiveRange::Segment
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
llvm::LiveIntervals::intervalIsInOneMBB
MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
Definition: LiveIntervals.cpp:829
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::RegState::Kill
@ Kill
The last use of a register.
Definition: MachineInstrBuilder.h:48
llvm::LiveIntervals::addKillFlags
void addKillFlags(const VirtRegMap *)
Add kill flags to any instruction that kills a virtual register.
Definition: LiveIntervals.cpp:704
MachineBasicBlock.h
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:231
llvm::LiveIntervals::removeAllRegUnitsForPhysReg
void removeAllRegUnitsForPhysReg(MCRegister Reg)
Remove associated live ranges for the register units associated with Reg.
Definition: LiveIntervals.h:425
llvm::LiveIntervals::removeInterval
void removeInterval(Register Reg)
Interval removal.
Definition: LiveIntervals.h:145
llvm::LiveIntervals::getRegMaskSlots
ArrayRef< SlotIndex > getRegMaskSlots() const
Returns a sorted array of slot indices of all instructions with register mask operands.
Definition: LiveIntervals.h:351
llvm::SlotIndexes::getMBBEndIdx
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:476
llvm::LiveIntervals::getInterval
const LiveInterval & getInterval(Register Reg) const
Definition: LiveIntervals.h:121
LLVM_ATTRIBUTE_UNUSED
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:188
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
llvm::LiveIntervals::removeRegUnit
void removeRegUnit(unsigned Unit)
Remove computed live range for register unit Unit.
Definition: LiveIntervals.h:416
llvm::LiveIntervals::createAndComputeVirtRegInterval
LiveInterval & createAndComputeVirtRegInterval(Register Reg)
Definition: LiveIntervals.h:138
llvm::LiveIntervals::getMBBFromIndex
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Definition: LiveIntervals.h:255
llvm::LiveIntervals::getInstructionIndex
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
Definition: LiveIntervals.h:226
llvm::LiveIntervals::handleMove
void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block.
Definition: LiveIntervals.cpp:1512
llvm::LiveIntervals::print
void print(raw_ostream &O, const Module *=nullptr) const override
Implement the dump method.
Definition: LiveIntervals.cpp:155
CommandLine.h
llvm::SlotIndexes::hasIndex
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
Definition: SlotIndexes.h:380
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::LiveRange::liveAt
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:393
llvm::LiveIntervals::extendToIndices
void extendToIndices(LiveRange &LR, ArrayRef< SlotIndex > Indices)
Definition: LiveIntervals.h:187
llvm::LiveIntervalCalc
Definition: LiveIntervalCalc.h:28
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
llvm::AAResults
Definition: AliasAnalysis.h:456
llvm::LiveIntervals::getMBBStartIdx
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
Definition: LiveIntervals.h:236
llvm::LiveIntervals::getCachedRegUnit
LiveRange * getCachedRegUnit(unsigned Unit)
Return the live range for register unit Unit if it has already been computed, or nullptr if it hasn't...
Definition: LiveIntervals.h:406
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::LiveIntervals::ID
static char ID
Definition: LiveIntervals.h:99
llvm::LiveIntervals::hasPHIKill
bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const
Returns true if VNI is killed by any PHI-def values in LI.
Definition: LiveIntervals.cpp:853
llvm::LiveIntervals::InsertMachineInstrInMaps
SlotIndex InsertMachineInstrInMaps(MachineInstr &MI)
Definition: LiveIntervals.h:266
llvm::LiveIntervals::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &) override
Pass entry point; Calculates LiveIntervals.
Definition: LiveIntervals.cpp:126
llvm::IndexedMap
Definition: IndexedMap.h:29
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LiveIntervals::isLiveOutOfMBB
bool isLiveOutOfMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const
Definition: LiveIntervals.h:250
llvm::LiveIntervals::pruneValue
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.
Definition: LiveIntervals.cpp:642
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::LiveIntervals::checkRegMaskInterference
bool checkRegMaskInterference(LiveInterval &LI, BitVector &UsableRegs)
Test if LI is live across any register mask instructions, and compute a bit mask of physical register...
Definition: LiveIntervals.cpp:914
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::SlotIndexes::getInstructionIndex
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:385
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:314
llvm::BitVector
Definition: BitVector.h:74
llvm::LiveIntervals::LiveIntervals
LiveIntervals()
Definition: LiveIntervals.cpp:103
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:680
llvm::SlotIndexes::getInstructionFromIndex
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:403
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::LiveIntervals::handleMoveIntoNewBundle
void handleMoveIntoNewBundle(MachineInstr &BundleStart, bool UpdateFlags=false)
Update intervals of operands of all instructions in the newly created bundle specified by BundleStart...
Definition: LiveIntervals.cpp:1528
llvm::SlotIndexes::insertMachineInstrInMaps
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
Definition: SlotIndexes.h:535
llvm::LiveIntervals::insertMBBInMaps
void insertMBBInMaps(MachineBasicBlock *MBB)
Definition: LiveIntervals.h:259
llvm::LiveIntervals::removePhysRegDefAt
void removePhysRegDefAt(MCRegister Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
Definition: LiveIntervals.cpp:1712
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:179
llvm::SlotIndexes::getMBBStartIdx
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:466
llvm::LiveIntervals::ReplaceMachineInstrInMaps
SlotIndex ReplaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI)
Definition: LiveIntervals.h:280
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
index
splat index
Definition: README_ALTIVEC.txt:181
llvm::LiveIntervals::getRegMaskBitsInBlock
ArrayRef< const uint32_t * > getRegMaskBitsInBlock(unsigned MBBNum) const
Returns an array of mask pointers corresponding to getRegMaskSlotsInBlock(MBBNum).
Definition: LiveIntervals.h:366
llvm::LiveRange
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
llvm::LiveIntervals::getMBBEndIdx
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Return the last index in the given basic block.
Definition: LiveIntervals.h:241
llvm::SlotIndexes::replaceMachineInstrInMaps
SlotIndex replaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI)
ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in maps used by register allocat...
Definition: SlotIndexes.h:592
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::LiveIntervals::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: LiveIntervals.cpp:109
ArrayRef.h
MachineFunctionPass.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SlotIndexes::getMBBFromIndex
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
Definition: SlotIndexes.h:514
llvm::LiveIntervals::shrinkToUses
bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr * > *dead=nullptr)
After removing some uses of a register, shrink its live range to just the remaining uses.
Definition: LiveIntervals.cpp:456
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
LiveRange
SI Optimize VGPR LiveRange
Definition: SIOptimizeVGPRLiveRange.cpp:570
llvm::LiveIntervals::getInterval
LiveInterval & getInterval(Register Reg)
Definition: LiveIntervals.h:114
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::IndexedMap::grow
void grow(IndexT n)
Definition: IndexedMap.h:67
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LiveIntervals::getCachedRegUnit
const LiveRange * getCachedRegUnit(unsigned Unit) const
Definition: LiveIntervals.h:410
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
Compiler.h
llvm::LiveIntervals::createEmptyInterval
LiveInterval & createEmptyInterval(Register Reg)
Interval creation.
Definition: LiveIntervals.h:131
llvm::LiveInterval::SubRange
A live range for subregisters.
Definition: LiveInterval.h:687
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::LiveIntervals::getSpillWeight
static float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI)
Calculate the spill weight to assign to a single instruction.
Definition: LiveIntervals.cpp:868
llvm::LiveIntervals::pruneValue
LLVM_ATTRIBUTE_UNUSED void pruneValue(LiveInterval &, SlotIndex, SmallVectorImpl< SlotIndex > *)
This function should not be used.
Definition: LiveIntervals.h:205
llvm::LiveIntervals::extendToIndices
void extendToIndices(LiveRange &LR, ArrayRef< SlotIndex > Indices, ArrayRef< SlotIndex > Undefs)
Extend the live range LR to reach all points in Indices.
Definition: LiveIntervals.cpp:633
llvm::LiveIntervals::~LiveIntervals
~LiveIntervals() override
Definition: LiveIntervals.cpp:107
llvm::LiveIntervals::getAliasAnalysis
AAResults * getAliasAnalysis() const
Definition: LiveIntervals.h:215
llvm::LiveIntervals
Definition: LiveIntervals.h:54
llvm::VNInfo
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
llvm::LiveIntervals::getRegMaskBits
ArrayRef< const uint32_t * > getRegMaskBits() const
Returns an array of register mask pointers corresponding to getRegMaskSlots().
Definition: LiveIntervals.h:362
llvm::LiveIntervals::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: LiveIntervals.cpp:90
llvm::LiveIntervals::constructMainRangeFromSubranges
void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range.
Definition: LiveIntervals.cpp:1755
LiveInterval.h
llvm::MCRegUnitIterator
Definition: MCRegisterInfo.h:677
SmallVector.h
llvm::UseSegmentSetForPhysRegs
cl::opt< bool > UseSegmentSetForPhysRegs
llvm::IndexedMap::inBounds
bool inBounds(IndexT n) const
Definition: IndexedMap.h:73
llvm::MCRegisterInfo::DiffListIterator::isValid
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:224
llvm::LiveIntervals::RemoveMachineInstrFromMaps
void RemoveMachineInstrFromMaps(MachineInstr &MI)
Definition: LiveIntervals.h:276
llvm::LiveIntervals::splitSeparateComponents
void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl< LiveInterval * > &SplitLIs)
Split separate components in LiveInterval LI into separate intervals.
Definition: LiveIntervals.cpp:1738
llvm::LiveIntervals::InsertMachineInstrRangeInMaps
void InsertMachineInstrRangeInMaps(MachineBasicBlock::iterator B, MachineBasicBlock::iterator E)
Definition: LiveIntervals.h:270
LaneBitmask.h
llvm::SmallVectorImpl< MachineInstr * >
llvm::LiveIntervals::repairIntervalsInRange
void repairIntervalsInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, ArrayRef< Register > OrigRegs)
Update live intervals for instructions in a range of iterators.
Definition: LiveIntervals.cpp:1662
llvm::LiveIntervals::hasInterval
bool hasInterval(Register Reg) const
Definition: LiveIntervals.h:125
SlotIndexes.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:45
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::SlotIndexes::removeMachineInstrFromMaps
void removeMachineInstrFromMaps(MachineInstr &MI, bool AllowBundled=false)
Removes machine instruction (bundle) MI from the mapping.
Definition: SlotIndexes.cpp:115
llvm::LiveIntervals::removeVRegDefAt
void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)
Remove value number and related live segments of LI and its subranges that start at position Pos.
Definition: LiveIntervals.cpp:1720
TargetRegisterInfo.h
llvm::LaneBitmask::getAll
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:84
llvm::LiveIntervals::getVNInfoAllocator
VNInfo::Allocator & getVNInfoAllocator()
Definition: LiveIntervals.h:284
llvm::LiveIntervals::getRegUnit
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
Definition: LiveIntervals.h:393
llvm::MCRegister
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:23