LLVM  12.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.
62  const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
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)) {
70  LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg)
71  : MRI->getMaxLaneMaskForVReg(Reg);
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()) {
75  LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg);
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();
155  const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
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) {
170  LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg);
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 }
bool empty() const
Definition: LiveInterval.h:374
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
A common definition of LaneBitmask for use in TableGen and CodeGen.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:75
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:680
unsigned Reg
A live range for subregisters.
Definition: LiveInterval.h:687
unsigned const TargetRegisterInfo * TRI
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.
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
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
void resetLiveOutMap()
Reset Map and Seen fields.
bool isEarlyClobber() const
void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:769
unsigned SubReg
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:83
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:797
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
static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc, LiveRange &LR, const MachineOperand &MO)
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:385
SlotIndexes pass.
Definition: SlotIndexes.h:314
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
Segments segments
Definition: LiveInterval.h:203
void createDeadDefs(LiveRange &LR, Register Reg)
createDeadDefs - Create a dead def in LI for every def operand of Reg.
void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, ArrayRef< SlotIndex > Undefs)
Extend the live range of LR to reach Use.
void calculate(LiveInterval &LI, bool TrackSubRegs)
Calculates liveness for the register specified in live interval LI.
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
unsigned const MachineRegisterInfo * MRI
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
SlotIndexes * getIndexes()
const MachineFunction * getMachineFunction()
Some getters to expose in a read-only way some private fields to subclasses.
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:476
Register reg() const
Definition: LiveInterval.h:711
VNInfo::Allocator * getVNAlloc()
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
static VNInfo UndefVNI(0xbad, SlotIndex())
void reset(const MachineFunction *mf, SlotIndexes *SI, MachineDominatorTree *MDT, VNInfo::Allocator *VNIA)
reset - Prepare caches for a new set of non-overlapping live ranges.
MachineDominatorTree * getDomTree()
MachineOperand class - Representation of each machine instruction operand.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1116
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 ...
bool isEarlyClobber() const
isEarlyClobber - Returns true if this is an early-clobber slot.
Definition: SlotIndexes.h:229
VNInfoList valnos
Definition: LiveInterval.h:204
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Representation of each machine instruction.
Definition: MachineInstr.h:62
const MachineRegisterInfo * getRegInfo() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19