LLVM 18.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
22#include "llvm/MC/LaneBitmask.h"
24#include <cassert>
25
26using namespace llvm;
27
28#define DEBUG_TYPE "regalloc"
29
30// Reserve an address that indicates a value that is known to be "undef".
31static VNInfo UndefVNI(0xbad, SlotIndex());
32
33static 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
43void LiveIntervalCalc::calculate(LiveInterval &LI, bool TrackSubRegs) {
45 SlotIndexes *Indexes = getIndexes();
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.
53 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
54 Register 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)) {
61 LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg)
62 : MRI->getMaxLaneMaskForVReg(Reg);
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()) {
66 LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg);
67 LI.createSubRangeFrom(*Alloc, ClassMask, LI);
68 }
69
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
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 {
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 }
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
136void LiveIntervalCalc::extendToUses(LiveRange &LR, Register Reg,
137 LaneBitmask Mask, LiveInterval *LI) {
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();
146 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
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) {
161 LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg);
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}
unsigned SubReg
unsigned const MachineRegisterInfo * MRI
IRTranslator LLVM IR MI
A common definition of LaneBitmask for use in TableGen and CodeGen.
static VNInfo UndefVNI(0xbad, SlotIndex())
static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc, LiveRange &LR, const MachineOperand &MO)
unsigned const TargetRegisterInfo * TRI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
void createDeadDefs(LiveRange &LR, Register Reg)
createDeadDefs - Create a dead def in LI for every def operand of Reg.
void calculate(LiveInterval &LI, bool TrackSubRegs)
Calculates liveness for the register specified in live interval LI.
void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range.
A live range for subregisters.
Definition: LiveInterval.h:693
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
Register reg() const
Definition: LiveInterval.h:717
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:803
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
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:775
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.
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 ...
SlotIndexes * getIndexes()
MachineDominatorTree * getDomTree()
void resetLiveOutMap()
Reset Map and Seen fields.
VNInfo::Allocator * getVNAlloc()
void reset(const MachineFunction *mf, SlotIndexes *SI, MachineDominatorTree *MDT, VNInfo::Allocator *VNIA)
reset - Prepare caches for a new set of non-overlapping live ranges.
const MachineFunction * getMachineFunction()
Some getters to expose in a read-only way some private fields to subclasses.
const MachineRegisterInfo * getRegInfo() const
void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, ArrayRef< SlotIndex > Undefs)
Extend the live range of LR to reach Use.
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
bool empty() const
Definition: LiveInterval.h:382
Segments segments
Definition: LiveInterval.h:203
VNInfoList valnos
Definition: LiveInterval.h:204
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Representation of each machine instruction.
Definition: MachineInstr.h:68
MachineOperand class - Representation of each machine instruction operand.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool isEarlyClobber() const
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:68
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:241
SlotIndexes pass.
Definition: SlotIndexes.h:301
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:463
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:372
bool empty() const
Definition: SmallVector.h:94
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
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
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:82