LLVM 19.0.0git
LiveRegMatrix.cpp
Go to the documentation of this file.
1//===- LiveRegMatrix.cpp - Track register interference --------------------===//
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// This file defines the LiveRegMatrix analysis pass.
10//
11//===----------------------------------------------------------------------===//
12
14#include "RegisterCoalescer.h"
15#include "llvm/ADT/Statistic.h"
24#include "llvm/MC/LaneBitmask.h"
26#include "llvm/Pass.h"
27#include "llvm/Support/Debug.h"
29#include <cassert>
30
31using namespace llvm;
32
33#define DEBUG_TYPE "regalloc"
34
35STATISTIC(NumAssigned , "Number of registers assigned");
36STATISTIC(NumUnassigned , "Number of registers unassigned");
37
38char LiveRegMatrix::ID = 0;
40 "Live Register Matrix", false, false)
45
47
48void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
49 AU.setPreservesAll();
53}
54
55bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
56 TRI = MF.getSubtarget().getRegisterInfo();
57 LIS = &getAnalysis<LiveIntervals>();
58 VRM = &getAnalysis<VirtRegMap>();
59
60 unsigned NumRegUnits = TRI->getNumRegUnits();
61 if (NumRegUnits != Matrix.size())
62 Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
63 Matrix.init(LIUAlloc, NumRegUnits);
64
65 // Make sure no stale queries get reused.
67 return false;
68}
69
70void LiveRegMatrix::releaseMemory() {
71 for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
72 Matrix[i].clear();
73 // No need to clear Queries here, since LiveIntervalUnion::Query doesn't
74 // have anything important to clear and LiveRegMatrix's runOnFunction()
75 // does a std::unique_ptr::reset anyways.
76 }
77}
78
79template <typename Callable>
81 const LiveInterval &VRegInterval, MCRegister PhysReg,
82 Callable Func) {
83 if (VRegInterval.hasSubRanges()) {
84 for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
85 unsigned Unit = (*Units).first;
86 LaneBitmask Mask = (*Units).second;
87 for (const LiveInterval::SubRange &S : VRegInterval.subranges()) {
88 if ((S.LaneMask & Mask).any()) {
89 if (Func(Unit, S))
90 return true;
91 break;
92 }
93 }
94 }
95 } else {
96 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
97 if (Func(Unit, VRegInterval))
98 return true;
99 }
100 }
101 return false;
102}
103
104void LiveRegMatrix::assign(const LiveInterval &VirtReg, MCRegister PhysReg) {
105 LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg(), TRI) << " to "
106 << printReg(PhysReg, TRI) << ':');
107 assert(!VRM->hasPhys(VirtReg.reg()) && "Duplicate VirtReg assignment");
108 VRM->assignVirt2Phys(VirtReg.reg(), PhysReg);
109
111 TRI, VirtReg, PhysReg, [&](unsigned Unit, const LiveRange &Range) {
112 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range);
113 Matrix[Unit].unify(VirtReg, Range);
114 return false;
115 });
116
117 ++NumAssigned;
118 LLVM_DEBUG(dbgs() << '\n');
119}
120
122 Register PhysReg = VRM->getPhys(VirtReg.reg());
123 LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg(), TRI)
124 << " from " << printReg(PhysReg, TRI) << ':');
125 VRM->clearVirt(VirtReg.reg());
126
127 foreachUnit(TRI, VirtReg, PhysReg,
128 [&](unsigned Unit, const LiveRange &Range) {
129 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI));
130 Matrix[Unit].extract(VirtReg, Range);
131 return false;
132 });
133
134 ++NumUnassigned;
135 LLVM_DEBUG(dbgs() << '\n');
136}
137
139 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
140 if (!Matrix[Unit].empty())
141 return true;
142 }
143 return false;
144}
145
147 MCRegister PhysReg) {
148 // Check if the cached information is valid.
149 // The same BitVector can be reused for all PhysRegs.
150 // We could cache multiple VirtRegs if it becomes necessary.
151 if (RegMaskVirtReg != VirtReg.reg() || RegMaskTag != UserTag) {
152 RegMaskVirtReg = VirtReg.reg();
153 RegMaskTag = UserTag;
154 RegMaskUsable.clear();
155 LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
156 }
157
158 // The BitVector is indexed by PhysReg, not register unit.
159 // Regmask interference is more fine grained than regunits.
160 // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
161 return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
162}
163
165 MCRegister PhysReg) {
166 if (VirtReg.empty())
167 return false;
168 CoalescerPair CP(VirtReg.reg(), PhysReg, *TRI);
169
170 bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
171 const LiveRange &Range) {
172 const LiveRange &UnitRange = LIS->getRegUnit(Unit);
173 return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
174 });
175 return Result;
176}
177
179 MCRegister RegUnit) {
180 LiveIntervalUnion::Query &Q = Queries[RegUnit];
181 Q.init(UserTag, LR, Matrix[RegUnit]);
182 return Q;
183}
184
187 MCRegister PhysReg) {
188 if (VirtReg.empty())
189 return IK_Free;
190
191 // Regmask interference is the fastest check.
192 if (checkRegMaskInterference(VirtReg, PhysReg))
193 return IK_RegMask;
194
195 // Check for fixed interference.
196 if (checkRegUnitInterference(VirtReg, PhysReg))
197 return IK_RegUnit;
198
199 // Check the matrix for virtual register interference.
200 bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
201 [&](MCRegister Unit, const LiveRange &LR) {
202 return query(LR, Unit).checkInterference();
203 });
204 if (Interference)
205 return IK_VirtReg;
206
207 return IK_Free;
208}
209
211 MCRegister PhysReg) {
212 // Construct artificial live range containing only one segment [Start, End).
213 VNInfo valno(0, Start);
214 LiveRange::Segment Seg(Start, End, &valno);
215 LiveRange LR;
216 LR.addSegment(Seg);
217
218 // Check for interference with that segment
219 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
220 // LR is stack-allocated. LiveRegMatrix caches queries by a key that
221 // includes the address of the live range. If (for the same reg unit) this
222 // checkInterference overload is called twice, without any other query()
223 // calls in between (on heap-allocated LiveRanges) - which would invalidate
224 // the cached query - the LR address seen the second time may well be the
225 // same as that seen the first time, while the Start/End/valno may not - yet
226 // the same cached result would be fetched. To avoid that, we don't cache
227 // this query.
228 //
229 // FIXME: the usability of the Query API needs to be improved to avoid
230 // subtle bugs due to query identity. Avoiding caching, for example, would
231 // greatly simplify things.
233 Q.reset(UserTag, LR, Matrix[Unit]);
234 if (Q.checkInterference())
235 return true;
236 }
237 return false;
238}
239
240Register LiveRegMatrix::getOneVReg(unsigned PhysReg) const {
241 const LiveInterval *VRegInterval = nullptr;
242 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
243 if ((VRegInterval = Matrix[Unit].getOneVReg()))
244 return VRegInterval->reg();
245 }
246
248}
Looks at all the uses of the given value Returns the Liveness deduced from the uses of this value Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses If the result is Live
#define LLVM_DEBUG(X)
Definition: Debug.h:101
bool End
Definition: ELF_riscv.cpp:480
A common definition of LaneBitmask for use in TableGen and CodeGen.
Live Register Matrix
static bool foreachUnit(const TargetRegisterInfo *TRI, const LiveInterval &VRegInterval, MCRegister PhysReg, Callable Func)
liveregmatrix
unsigned const TargetRegisterInfo * TRI
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
bool test(unsigned Idx) const
Definition: BitVector.h:461
void clear()
clear - Removes all bits from the bitvector.
Definition: BitVector.h:335
bool empty() const
empty - Tests whether there are no bits in this bitvector.
Definition: BitVector.h:156
A helper class for register coalescers.
void init(LiveIntervalUnion::Allocator &, unsigned Size)
Query interferences between a single live virtual register and a live interval union.
void init(unsigned NewUserTag, const LiveRange &NewLR, const LiveIntervalUnion &NewLiveUnion)
void reset(unsigned NewUserTag, const LiveRange &NewLR, const LiveIntervalUnion &NewLiveUnion)
A live range for subregisters.
Definition: LiveInterval.h:694
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:687
Register reg() const
Definition: LiveInterval.h:718
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:810
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:782
bool checkRegMaskInterference(const LiveInterval &LI, BitVector &UsableRegs)
Test if LI is live across any register mask instructions, and compute a bit mask of physical register...
SlotIndexes * getSlotIndexes() const
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
bool empty() const
Definition: LiveInterval.h:382
bool checkRegMaskInterference(const LiveInterval &VirtReg, MCRegister PhysReg=MCRegister::NoRegister)
Check for regmask interference only.
void unassign(const LiveInterval &VirtReg)
Unassign VirtReg from its PhysReg.
LiveIntervalUnion::Query & query(const LiveRange &LR, MCRegister RegUnit)
Query a line of the assigned virtual register matrix directly.
bool isPhysRegUsed(MCRegister PhysReg) const
Returns true if the given PhysReg has any live intervals assigned.
void invalidateVirtRegs()
Invalidate cached interference queries after modifying virtual register live ranges.
Definition: LiveRegMatrix.h:81
Register getOneVReg(unsigned PhysReg) const
@ IK_VirtReg
Virtual register interference.
Definition: LiveRegMatrix.h:90
@ IK_RegUnit
Register unit interference.
Definition: LiveRegMatrix.h:95
@ IK_Free
No interference, go ahead and assign.
Definition: LiveRegMatrix.h:85
@ IK_RegMask
RegMask interference.
void assign(const LiveInterval &VirtReg, MCRegister PhysReg)
Assign VirtReg to PhysReg.
InterferenceKind checkInterference(const LiveInterval &VirtReg, MCRegister PhysReg)
Check for interference before assigning VirtReg to PhysReg.
bool checkRegUnitInterference(const LiveInterval &VirtReg, MCRegister PhysReg)
Check for regunit interference only.
MCRegUnitMaskIterator enumerates a list of register units and their associated lane masks for Reg.
bool isValid() const
Returns true if this iterator is not yet at the end.
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
iterator_range< MCRegUnitIterator > regunits(MCRegister Reg) const
Returns an iterator range over all regunits for Reg.
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:33
static constexpr unsigned NoRegister
Definition: MCRegister.h:52
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:68
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
void clearVirt(Register virtReg)
clears the specified virtual register's, physical register mapping
Definition: VirtRegMap.h:131
MCRegister getPhys(Register virtReg) const
returns the physical register mapped to the specified virtual register
Definition: VirtRegMap.h:105
bool hasPhys(Register virtReg) const
returns true if the specified virtual register is mapped to a physical register
Definition: VirtRegMap.h:99
void assignVirt2Phys(Register virtReg, MCPhysReg physReg)
creates a mapping for the specified virtual register to the specified physical register
Definition: VirtRegMap.cpp:85
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162