LLVM  15.0.0git
LiveIntervalCalc.cpp
Go to the documentation of this file.
1 //===- LiveIntervalCalc.cpp - Calculate live interval --------------------===//
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 // Implementation of the LiveIntervalCalc class.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/MC/LaneBitmask.h"
24 #include <cassert>
25 
26 using namespace llvm;
27 
28 #define DEBUG_TYPE "regalloc"
29 
30 // Reserve an address that indicates a value that is known to be "undef".
31 static VNInfo UndefVNI(0xbad, SlotIndex());
32 
33 static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc,
34  LiveRange &LR, const MachineOperand &MO) {
35  const MachineInstr &MI = *MO.getParent();
36  SlotIndex DefIdx =
38 
39  // Create the def in LR. This may find an existing def.
40  LR.createDeadDef(DefIdx, Alloc);
41 }
42 
43 void LiveIntervalCalc::calculate(LiveInterval &LI, bool TrackSubRegs) {
45  SlotIndexes *Indexes = getIndexes();
46  VNInfo::Allocator *Alloc = getVNAlloc();
47 
48  assert(MRI && Indexes && "call reset() first");
49 
50  // Step 1: Create minimal live segments for every definition of Reg.
51  // Visit all def operands. If the same instruction has multiple defs of Reg,
52  // createDeadDef() will deduplicate.
54  unsigned Reg = LI.reg();
55  for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
56  if (!MO.isDef() && !MO.readsReg())
57  continue;
58 
59  unsigned SubReg = MO.getSubReg();
60  if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
63  // If this is the first time we see a subregister def, initialize
64  // subranges by creating a copy of the main range.
65  if (!LI.hasSubRanges() && !LI.empty()) {
67  LI.createSubRangeFrom(*Alloc, ClassMask, LI);
68  }
69 
70  LI.refineSubRanges(
71  *Alloc, SubMask,
72  [&MO, Indexes, Alloc](LiveInterval::SubRange &SR) {
73  if (MO.isDef())
74  createDeadDef(*Indexes, *Alloc, SR, MO);
75  },
76  *Indexes, TRI);
77  }
78 
79  // Create the def in the main liverange. We do not have to do this if
80  // subranges are tracked as we recreate the main range later in this case.
81  if (MO.isDef() && !LI.hasSubRanges())
82  createDeadDef(*Indexes, *Alloc, LI, MO);
83  }
84 
85  // We may have created empty live ranges for partially undefined uses, we
86  // can't keep them because we won't find defs in them later.
88 
89  const MachineFunction *MF = getMachineFunction();
90  MachineDominatorTree *DomTree = getDomTree();
91  // Step 2: Extend live segments to all uses, constructing SSA form as
92  // necessary.
93  if (LI.hasSubRanges()) {
94  for (LiveInterval::SubRange &S : LI.subranges()) {
95  LiveIntervalCalc SubLIC;
96  SubLIC.reset(MF, Indexes, DomTree, Alloc);
97  SubLIC.extendToUses(S, Reg, S.LaneMask, &LI);
98  }
99  LI.clear();
101  } else {
102  resetLiveOutMap();
103  extendToUses(LI, Reg, LaneBitmask::getAll());
104  }
105 }
106 
108  // First create dead defs at all defs found in subranges.
109  LiveRange &MainRange = LI;
110  assert(MainRange.segments.empty() && MainRange.valnos.empty() &&
111  "Expect empty main liverange");
112 
113  VNInfo::Allocator *Alloc = getVNAlloc();
114  for (const LiveInterval::SubRange &SR : LI.subranges()) {
115  for (const VNInfo *VNI : SR.valnos) {
116  if (!VNI->isUnused() && !VNI->isPHIDef())
117  MainRange.createDeadDef(VNI->def, *Alloc);
118  }
119  }
120  resetLiveOutMap();
121  extendToUses(MainRange, LI.reg(), LaneBitmask::getAll(), &LI);
122 }
123 
126  SlotIndexes *Indexes = getIndexes();
127  VNInfo::Allocator *Alloc = getVNAlloc();
128  assert(MRI && Indexes && "call reset() first");
129 
130  // Visit all def operands. If the same instruction has multiple defs of Reg,
131  // LR.createDeadDef() will deduplicate.
132  for (MachineOperand &MO : MRI->def_operands(Reg))
133  createDeadDef(*Indexes, *Alloc, LR, MO);
134 }
135 
136 void LiveIntervalCalc::extendToUses(LiveRange &LR, Register Reg,
139  SlotIndexes *Indexes = getIndexes();
141  if (LI != nullptr)
142  LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes);
143 
144  // Visit all operands that read Reg. This may include partial defs.
145  bool IsSubRange = !Mask.all();
147  for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
148  // Clear all kill flags. They will be reinserted after register allocation
149  // by LiveIntervals::addKillFlags().
150  if (MO.isUse())
151  MO.setIsKill(false);
152  // MO::readsReg returns "true" for subregister defs. This is for keeping
153  // liveness of the entire register (i.e. for the main range of the live
154  // interval). For subranges, definitions of non-overlapping subregisters
155  // do not count as uses.
156  if (!MO.readsReg() || (IsSubRange && MO.isDef()))
157  continue;
158 
159  unsigned SubReg = MO.getSubReg();
160  if (SubReg != 0) {
162  if (MO.isDef())
163  SLM = ~SLM;
164  // Ignore uses not reading the current (sub)range.
165  if ((SLM & Mask).none())
166  continue;
167  }
168 
169  // Determine the actual place of the use.
170  const MachineInstr *MI = MO.getParent();
171  unsigned OpNo = (&MO - &MI->getOperand(0));
172  SlotIndex UseIdx;
173  if (MI->isPHI()) {
174  assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
175  // The actual place where a phi operand is used is the end of the pred
176  // MBB. PHI operands are paired: (Reg, PredMBB).
177  UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo + 1).getMBB());
178  } else {
179  // Check for early-clobber redefs.
180  bool isEarlyClobber = false;
181  unsigned DefIdx;
182  if (MO.isDef())
183  isEarlyClobber = MO.isEarlyClobber();
184  else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) {
185  // FIXME: This would be a lot easier if tied early-clobber uses also
186  // had an early-clobber flag.
187  isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
188  }
189  UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber);
190  }
191 
192  // MI is reading Reg. We may have visited MI before if it happens to be
193  // reading Reg multiple times. That is OK, extend() is idempotent.
194  extend(LR, UseIdx, Reg, Undefs);
195  }
196 }
llvm::LaneBitmask
Definition: LaneBitmask.h:40
llvm::LiveInterval::computeSubRangeUndefs
void computeSubRangeUndefs(SmallVectorImpl< SlotIndex > &Undefs, LaneBitmask LaneMask, const MachineRegisterInfo &MRI, const SlotIndexes &Indexes) const
For a given lane mask LaneMask, compute indexes at which the lane is marked undefined by subregister ...
Definition: LiveInterval.cpp:977
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
MachineInstr.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::LiveRange::empty
bool empty() const
Definition: LiveInterval.h:382
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
ErrorHandling.h
llvm::LiveRangeCalc::extend
void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, ArrayRef< SlotIndex > Undefs)
Extend the live range of LR to reach Use.
Definition: LiveRangeCalc.cpp:87
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::MachineRegisterInfo::getTargetRegisterInfo
const TargetRegisterInfo * getTargetRegisterInfo() const
Definition: MachineRegisterInfo.h:151
llvm::VNInfo::def
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:234
UndefVNI
static VNInfo UndefVNI(0xbad, SlotIndex())
llvm::SlotIndex::isEarlyClobber
bool isEarlyClobber() const
isEarlyClobber - Returns true if this is an early-clobber slot.
Definition: SlotIndexes.h:228
llvm::SlotIndexes::getMBBEndIdx
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:475
createDeadDef
static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc, LiveRange &LR, const MachineOperand &MO)
Definition: LiveIntervalCalc.cpp:33
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1620
llvm::LiveIntervalCalc::constructMainRangeFromSubranges
void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range.
Definition: LiveIntervalCalc.cpp:107
MachineRegisterInfo.h
llvm::BitmaskEnumDetail::Mask
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
llvm::LiveIntervalCalc
Definition: LiveIntervalCalc.h:28
llvm::TargetRegisterInfo::getSubRegIndexLaneMask
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
Definition: TargetRegisterInfo.h:378
llvm::LiveIntervalCalc::createDeadDefs
void createDeadDefs(LiveRange &LR, Register Reg)
createDeadDefs - Create a dead def in LI for every def operand of Reg.
Definition: LiveIntervalCalc.cpp:124
llvm::LiveRangeCalc::resetLiveOutMap
void resetLiveOutMap()
Reset Map and Seen fields.
Definition: LiveRangeCalc.cpp:41
llvm::MachineRegisterInfo::reg_nodbg_operands
iterator_range< reg_nodbg_iterator > reg_nodbg_operands(Register Reg) const
Definition: MachineRegisterInfo.h:345
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::LiveRange::valnos
VNInfoList valnos
Definition: LiveInterval.h:204
llvm::SlotIndexes::getInstructionIndex
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:384
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:313
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
llvm::MachineOperand::getParent
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Definition: MachineOperand.h:237
LiveIntervalCalc.h
llvm::LiveRangeCalc::getRegInfo
const MachineRegisterInfo * getRegInfo() const
Definition: LiveRangeCalc.h:167
llvm::LiveInterval::removeEmptySubRanges
void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
Definition: LiveInterval.cpp:854
llvm::LiveInterval::refineSubRanges
void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, std::function< void(LiveInterval::SubRange &)> Apply, const SlotIndexes &Indexes, const TargetRegisterInfo &TRI, unsigned ComposeSubRegIdx=0)
Refines the subranges to support LaneMask.
Definition: LiveInterval.cpp:931
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::LiveIntervalCalc::calculate
void calculate(LiveInterval &LI, bool TrackSubRegs)
Calculates liveness for the register specified in live interval LI.
Definition: LiveIntervalCalc.cpp:43
llvm::LiveRange
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:63
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineOperand::isEarlyClobber
bool isEarlyClobber() const
Definition: MachineOperand.h:435
iterator_range.h
llvm::SlotIndex::getRegSlot
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
Definition: SlotIndexes.h:253
llvm::MachineFunction
Definition: MachineFunction.h:241
llvm::LiveRange::createDeadDef
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
Definition: LiveInterval.cpp:370
llvm::LiveRangeCalc::getIndexes
SlotIndexes * getIndexes()
Definition: LiveRangeCalc.h:168
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::LiveRangeCalc::getMachineFunction
const MachineFunction * getMachineFunction()
Some getters to expose in a read-only way some private fields to subclasses.
Definition: LiveRangeCalc.h:166
llvm::LiveInterval::SubRange
A live range for subregisters.
Definition: LiveInterval.h:693
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::VNInfo::isPHIDef
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
Definition: LiveInterval.h:78
llvm::MachineRegisterInfo::def_operands
iterator_range< def_iterator > def_operands(Register Reg) const
Definition: MachineRegisterInfo.h:397
llvm::MachineRegisterInfo::getMaxLaneMaskForVReg
LaneBitmask getMaxLaneMaskForVReg(Register Reg) const
Returns a mask covering all bits that can appear in lane masks of subregisters of the virtual registe...
Definition: MachineRegisterInfo.cpp:489
llvm::VNInfo
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
LiveInterval.h
llvm::LiveRangeCalc::getVNAlloc
VNInfo::Allocator * getVNAlloc()
Definition: LiveRangeCalc.h:170
llvm::LiveRangeCalc::getDomTree
MachineDominatorTree * getDomTree()
Definition: LiveRangeCalc.h:169
SmallVector.h
llvm::LiveRange::segments
Segments segments
Definition: LiveInterval.h:203
llvm::LiveInterval::reg
Register reg() const
Definition: LiveInterval.h:717
llvm::LiveInterval::hasSubRanges
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:803
LaneBitmask.h
llvm::LiveRange::clear
void clear()
Definition: LiveInterval.h:300
llvm::LiveRangeCalc::reset
void reset(const MachineFunction *mf, SlotIndexes *SI, MachineDominatorTree *MDT, VNInfo::Allocator *VNIA)
reset - Prepare caches for a new set of non-overlapping live ranges.
Definition: LiveRangeCalc.cpp:49
MachineOperand.h
llvm::VNInfo::isUnused
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
SlotIndexes.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
TargetRegisterInfo.h
llvm::LaneBitmask::getAll
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:84
SubReg
unsigned SubReg
Definition: AArch64AdvSIMDScalarPass.cpp:104
llvm::LiveInterval::createSubRangeFrom
SubRange * createSubRangeFrom(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, const LiveRange &CopyFrom)
Like createSubRange() but the new range is filled with a copy of the liveness information in CopyFrom...
Definition: LiveInterval.h:794
llvm::LiveInterval::subranges
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:775