LLVM  14.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/STLExtras.h"
15 #include "llvm/ADT/SetVector.h"
16 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/MC/LaneBitmask.h"
29 #include <algorithm>
30 #include <cassert>
31 #include <iterator>
32 #include <tuple>
33 #include <utility>
34 
35 using namespace llvm;
36 
37 #define DEBUG_TYPE "regalloc"
38 
39 // Reserve an address that indicates a value that is known to be "undef".
40 static VNInfo UndefVNI(0xbad, SlotIndex());
41 
42 static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc,
43  LiveRange &LR, const MachineOperand &MO) {
44  const MachineInstr &MI = *MO.getParent();
45  SlotIndex DefIdx =
47 
48  // Create the def in LR. This may find an existing def.
49  LR.createDeadDef(DefIdx, Alloc);
50 }
51 
52 void LiveIntervalCalc::calculate(LiveInterval &LI, bool TrackSubRegs) {
54  SlotIndexes *Indexes = getIndexes();
55  VNInfo::Allocator *Alloc = getVNAlloc();
56 
57  assert(MRI && Indexes && "call reset() first");
58 
59  // Step 1: Create minimal live segments for every definition of Reg.
60  // Visit all def operands. If the same instruction has multiple defs of Reg,
61  // createDeadDef() will deduplicate.
63  unsigned Reg = LI.reg();
64  for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
65  if (!MO.isDef() && !MO.readsReg())
66  continue;
67 
68  unsigned SubReg = MO.getSubReg();
69  if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
72  // If this is the first time we see a subregister def, initialize
73  // subranges by creating a copy of the main range.
74  if (!LI.hasSubRanges() && !LI.empty()) {
76  LI.createSubRangeFrom(*Alloc, ClassMask, LI);
77  }
78 
79  LI.refineSubRanges(
80  *Alloc, SubMask,
81  [&MO, Indexes, Alloc](LiveInterval::SubRange &SR) {
82  if (MO.isDef())
83  createDeadDef(*Indexes, *Alloc, SR, MO);
84  },
85  *Indexes, TRI);
86  }
87 
88  // Create the def in the main liverange. We do not have to do this if
89  // subranges are tracked as we recreate the main range later in this case.
90  if (MO.isDef() && !LI.hasSubRanges())
91  createDeadDef(*Indexes, *Alloc, LI, MO);
92  }
93 
94  // We may have created empty live ranges for partially undefined uses, we
95  // can't keep them because we won't find defs in them later.
97 
98  const MachineFunction *MF = getMachineFunction();
99  MachineDominatorTree *DomTree = getDomTree();
100  // Step 2: Extend live segments to all uses, constructing SSA form as
101  // necessary.
102  if (LI.hasSubRanges()) {
103  for (LiveInterval::SubRange &S : LI.subranges()) {
104  LiveIntervalCalc SubLIC;
105  SubLIC.reset(MF, Indexes, DomTree, Alloc);
106  SubLIC.extendToUses(S, Reg, S.LaneMask, &LI);
107  }
108  LI.clear();
110  } else {
111  resetLiveOutMap();
112  extendToUses(LI, Reg, LaneBitmask::getAll());
113  }
114 }
115 
117  // First create dead defs at all defs found in subranges.
118  LiveRange &MainRange = LI;
119  assert(MainRange.segments.empty() && MainRange.valnos.empty() &&
120  "Expect empty main liverange");
121 
122  VNInfo::Allocator *Alloc = getVNAlloc();
123  for (const LiveInterval::SubRange &SR : LI.subranges()) {
124  for (const VNInfo *VNI : SR.valnos) {
125  if (!VNI->isUnused() && !VNI->isPHIDef())
126  MainRange.createDeadDef(VNI->def, *Alloc);
127  }
128  }
129  resetLiveOutMap();
130  extendToUses(MainRange, LI.reg(), LaneBitmask::getAll(), &LI);
131 }
132 
135  SlotIndexes *Indexes = getIndexes();
136  VNInfo::Allocator *Alloc = getVNAlloc();
137  assert(MRI && Indexes && "call reset() first");
138 
139  // Visit all def operands. If the same instruction has multiple defs of Reg,
140  // LR.createDeadDef() will deduplicate.
141  for (MachineOperand &MO : MRI->def_operands(Reg))
142  createDeadDef(*Indexes, *Alloc, LR, MO);
143 }
144 
145 void LiveIntervalCalc::extendToUses(LiveRange &LR, Register Reg,
148  SlotIndexes *Indexes = getIndexes();
150  if (LI != nullptr)
151  LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes);
152 
153  // Visit all operands that read Reg. This may include partial defs.
154  bool IsSubRange = !Mask.all();
156  for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
157  // Clear all kill flags. They will be reinserted after register allocation
158  // by LiveIntervals::addKillFlags().
159  if (MO.isUse())
160  MO.setIsKill(false);
161  // MO::readsReg returns "true" for subregister defs. This is for keeping
162  // liveness of the entire register (i.e. for the main range of the live
163  // interval). For subranges, definitions of non-overlapping subregisters
164  // do not count as uses.
165  if (!MO.readsReg() || (IsSubRange && MO.isDef()))
166  continue;
167 
168  unsigned SubReg = MO.getSubReg();
169  if (SubReg != 0) {
171  if (MO.isDef())
172  SLM = ~SLM;
173  // Ignore uses not reading the current (sub)range.
174  if ((SLM & Mask).none())
175  continue;
176  }
177 
178  // Determine the actual place of the use.
179  const MachineInstr *MI = MO.getParent();
180  unsigned OpNo = (&MO - &MI->getOperand(0));
181  SlotIndex UseIdx;
182  if (MI->isPHI()) {
183  assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
184  // The actual place where a phi operand is used is the end of the pred
185  // MBB. PHI operands are paired: (Reg, PredMBB).
186  UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo + 1).getMBB());
187  } else {
188  // Check for early-clobber redefs.
189  bool isEarlyClobber = false;
190  unsigned DefIdx;
191  if (MO.isDef())
192  isEarlyClobber = MO.isEarlyClobber();
193  else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) {
194  // FIXME: This would be a lot easier if tied early-clobber uses also
195  // had an early-clobber flag.
196  isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
197  }
198  UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber);
199  }
200 
201  // MI is reading Reg. We may have visited MI before if it happens to be
202  // reading Reg multiple times. That is OK, extend() is idempotent.
203  extend(LR, UseIdx, Reg, Undefs);
204  }
205 }
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:976
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
MachineInstr.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::LiveRange::empty
bool empty() const
Definition: LiveInterval.h:374
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
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:89
llvm::MachineRegisterInfo::getTargetRegisterInfo
const TargetRegisterInfo * getTargetRegisterInfo() const
Definition: MachineRegisterInfo.h:153
MachineBasicBlock.h
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:233
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:229
llvm::SlotIndexes::getMBBEndIdx
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:476
STLExtras.h
createDeadDef
static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc, LiveRange &LR, const MachineOperand &MO)
Definition: LiveIntervalCalc.cpp:42
llvm::BitmaskEnumDetail::Mask
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
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
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:116
MachineRegisterInfo.h
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:377
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:133
llvm::LiveRangeCalc::resetLiveOutMap
void resetLiveOutMap()
Reset Map and Seen fields.
Definition: LiveRangeCalc.cpp:43
llvm::MachineRegisterInfo::reg_nodbg_operands
iterator_range< reg_nodbg_iterator > reg_nodbg_operands(Register Reg) const
Definition: MachineRegisterInfo.h:337
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
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:385
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:314
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:680
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
llvm::MachineOperand::getParent
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Definition: MachineOperand.h:238
LiveIntervalCalc.h
llvm::LiveRangeCalc::getRegInfo
const MachineRegisterInfo * getRegInfo() const
Definition: LiveRangeCalc.h:168
llvm::LiveInterval::removeEmptySubRanges
void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
Definition: LiveInterval.cpp:853
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:930
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::LiveIntervalCalc::calculate
void calculate(LiveInterval &LI, bool TrackSubRegs)
Calculates liveness for the register specified in live interval LI.
Definition: LiveIntervalCalc.cpp:52
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:67
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineOperand::isEarlyClobber
bool isEarlyClobber() const
Definition: MachineOperand.h:436
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:254
llvm::MachineFunction
Definition: MachineFunction.h:230
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:169
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:167
llvm::LiveInterval::SubRange
A live range for subregisters.
Definition: LiveInterval.h:687
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:389
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:493
llvm::VNInfo
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
LiveInterval.h
llvm::LiveRangeCalc::getVNAlloc
VNInfo::Allocator * getVNAlloc()
Definition: LiveRangeCalc.h:171
llvm::LiveRangeCalc::getDomTree
MachineDominatorTree * getDomTree()
Definition: LiveRangeCalc.h:170
SmallVector.h
llvm::LiveRange::segments
Segments segments
Definition: LiveInterval.h:203
llvm::LiveInterval::reg
Register reg() const
Definition: LiveInterval.h:711
llvm::LiveInterval::hasSubRanges
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:797
LaneBitmask.h
llvm::LiveRange::clear
void clear()
Definition: LiveInterval.h:292
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:51
MachineOperand.h
llvm::VNInfo::isUnused
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
SlotIndexes.h
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:45
MachineFunction.h
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:788
SetVector.h
MachineDominators.h
llvm::LiveInterval::subranges
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:769