LLVM  14.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"
23 #include "llvm/InitializePasses.h"
24 #include "llvm/MC/LaneBitmask.h"
25 #include "llvm/MC/MCRegisterInfo.h"
26 #include "llvm/Pass.h"
27 #include "llvm/Support/Debug.h"
29 #include <cassert>
30 
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "regalloc"
34 
35 STATISTIC(NumAssigned , "Number of registers assigned");
36 STATISTIC(NumUnassigned , "Number of registers unassigned");
37 
38 char LiveRegMatrix::ID = 0;
39 INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
40  "Live Register Matrix", false, false)
44  "Live Register Matrix", false, false)
45 
47 
48 void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
49  AU.setPreservesAll();
53 }
54 
55 bool 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 
70 void 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 
79 template <typename Callable>
80 static bool foreachUnit(const TargetRegisterInfo *TRI,
81  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 (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 (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
97  if (Func(*Units, VRegInterval))
98  return true;
99  }
100  }
101  return false;
102 }
103 
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 
110  foreachUnit(
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 (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
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  if (VirtReg.empty())
188  return IK_Free;
189 
190  // Regmask interference is the fastest check.
191  if (checkRegMaskInterference(VirtReg, PhysReg))
192  return IK_RegMask;
193 
194  // Check for fixed interference.
195  if (checkRegUnitInterference(VirtReg, PhysReg))
196  return IK_RegUnit;
197 
198  // Check the matrix for virtual register interference.
199  bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
200  [&](MCRegister Unit, const LiveRange &LR) {
201  return query(LR, Unit).checkInterference();
202  });
203  if (Interference)
204  return IK_VirtReg;
205 
206  return IK_Free;
207 }
208 
210  MCRegister PhysReg) {
211  // Construct artificial live range containing only one segment [Start, End).
212  VNInfo valno(0, Start);
213  LiveRange::Segment Seg(Start, End, &valno);
214  LiveRange LR;
215  LR.addSegment(Seg);
216 
217  // Check for interference with that segment
218  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
219  // LR is stack-allocated. LiveRegMatrix caches queries by a key that
220  // includes the address of the live range. If (for the same reg unit) this
221  // checkInterference overload is called twice, without any other query()
222  // calls in between (on heap-allocated LiveRanges) - which would invalidate
223  // the cached query - the LR address seen the second time may well be the
224  // same as that seen the first time, while the Start/End/valno may not - yet
225  // the same cached result would be fetched. To avoid that, we don't cache
226  // this query.
227  //
228  // FIXME: the usability of the Query API needs to be improved to avoid
229  // subtle bugs due to query identity. Avoiding caching, for example, would
230  // greatly simplify things.
232  Q.reset(UserTag, LR, Matrix[*Units]);
233  if (Q.checkInterference())
234  return true;
235  }
236  return false;
237 }
238 
239 Register LiveRegMatrix::getOneVReg(unsigned PhysReg) const {
240  LiveInterval *VRegInterval = nullptr;
241  for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
242  if ((VRegInterval = Matrix[*Unit].getOneVReg()))
243  return VRegInterval->reg();
244  }
245 
246  return MCRegister::NoRegister;
247 }
llvm::LaneBitmask
Definition: LaneBitmask.h:40
i
i
Definition: README.txt:29
LiveRegMatrix.h
llvm::LiveRegMatrix::InterferenceKind
InterferenceKind
Definition: LiveRegMatrix.h:83
llvm::LiveIntervalUnion::Array::size
unsigned size() const
Definition: LiveIntervalUnion.h:184
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::LiveRange::empty
bool empty() const
Definition: LiveInterval.h:374
llvm::LiveIntervals::getSlotIndexes
SlotIndexes * getSlotIndexes() const
Definition: LiveIntervals.h:211
llvm::LiveRegMatrix::checkInterference
InterferenceKind checkInterference(LiveInterval &VirtReg, MCRegister PhysReg)
Check for interference before assigning VirtReg to PhysReg.
Definition: LiveRegMatrix.cpp:186
llvm::MCRegUnitMaskIterator::isValid
bool isValid() const
Returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:727
llvm::LiveRegMatrix::invalidateVirtRegs
void invalidateVirtRegs()
Invalidate cached interference queries after modifying virtual register live ranges.
Definition: LiveRegMatrix.h:81
Pass.h
llvm::BitVector::clear
void clear()
clear - Removes all bits from the bitvector.
Definition: BitVector.h:327
llvm::LiveIntervalUnion::Query::reset
void reset(unsigned NewUserTag, const LiveRange &NewLR, const LiveIntervalUnion &NewLiveUnion)
Definition: LiveIntervalUnion.h:130
Statistic.h
llvm::LiveIntervalUnion::Array::clear
void clear()
Definition: LiveIntervalUnion.cpp:207
llvm::VirtRegMap
Definition: VirtRegMap.h:33
llvm::LiveRange::Segment
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
llvm::VirtRegMap::assignVirt2Phys
void assignVirt2Phys(Register virtReg, MCPhysReg physReg)
creates a mapping for the specified virtual register to the specified physical register
Definition: VirtRegMap.cpp:85
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:124
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
llvm::LiveIntervalUnion::Query::init
void init(unsigned NewUserTag, const LiveRange &NewLR, const LiveIntervalUnion &NewLiveUnion)
Definition: LiveIntervalUnion.h:141
llvm::MCRegister::NoRegister
static constexpr unsigned NoRegister
Definition: MCRegister.h:43
llvm::MCRegisterInfo::getNumRegUnits
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
Definition: MCRegisterInfo.h:505
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::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::LiveRegMatrix::getOneVReg
Register getOneVReg(unsigned PhysReg) const
Definition: LiveRegMatrix.cpp:239
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix", "Live Register Matrix", false, false) INITIALIZE_PASS_END(LiveRegMatrix
llvm::LiveRegMatrix::IK_RegUnit
@ IK_RegUnit
Register unit interference.
Definition: LiveRegMatrix.h:95
llvm::LiveRegMatrix::IK_Free
@ IK_Free
No interference, go ahead and assign.
Definition: LiveRegMatrix.h:85
llvm::LiveRegMatrix::checkRegMaskInterference
bool checkRegMaskInterference(LiveInterval &VirtReg, MCRegister PhysReg=MCRegister::NoRegister)
Check for regmask interference only.
Definition: LiveRegMatrix.cpp:146
llvm::LiveRegMatrix::assign
void assign(LiveInterval &VirtReg, MCRegister PhysReg)
Assign VirtReg to PhysReg.
Definition: LiveRegMatrix.cpp:104
llvm::LiveRange::addSegment
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
Definition: LiveInterval.cpp:548
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:142
LiveIntervalUnion.h
llvm::LiveIntervals::checkRegMaskInterference
bool checkRegMaskInterference(LiveInterval &LI, BitVector &UsableRegs)
Test if LI is live across any register mask instructions, and compute a bit mask of physical register...
Definition: LiveIntervals.cpp:914
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::LiveRegMatrix::isPhysRegUsed
bool isPhysRegUsed(MCRegister PhysReg) const
Returns true if the given PhysReg has any live intervals assigned.
Definition: LiveRegMatrix.cpp:138
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
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::printRegUnit
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
Definition: TargetRegisterInfo.cpp:141
llvm::BitVector::empty
bool empty() const
empty - Tests whether there are no bits in this bitvector.
Definition: BitVector.h:148
llvm::VirtRegMap::hasPhys
bool hasPhys(Register virtReg) const
returns true if the specified virtual register is mapped to a physical register
Definition: VirtRegMap.h:100
llvm::LiveRegMatrix::query
LiveIntervalUnion::Query & query(const LiveRange &LR, MCRegister RegUnit)
Query a line of the assigned virtual register matrix directly.
Definition: LiveRegMatrix.cpp:178
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:630
llvm::LiveRegMatrix::unassign
void unassign(LiveInterval &VirtReg)
Unassign VirtReg from its PhysReg.
Definition: LiveRegMatrix.cpp:121
LiveIntervals.h
llvm::LiveRange
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
VirtRegMap.h
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::MCRegUnitMaskIterator
MCRegUnitMaskIterator enumerates a list of register units and their associated lane masks for Reg.
Definition: MCRegisterInfo.h:706
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::VirtRegMap::getPhys
MCRegister getPhys(Register virtReg) const
returns the physical register mapped to the specified virtual register
Definition: VirtRegMap.h:106
MCRegisterInfo.h
llvm::LiveRange::overlaps
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
Definition: LiveInterval.h:440
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::LiveRegMatrix::checkRegUnitInterference
bool checkRegUnitInterference(LiveInterval &VirtReg, MCRegister PhysReg)
Check for regunit interference only.
Definition: LiveRegMatrix.cpp:164
llvm::LiveIntervalUnion::Array::init
void init(LiveIntervalUnion::Allocator &, unsigned Size)
Definition: LiveIntervalUnion.cpp:194
llvm::MachineFunction
Definition: MachineFunction.h:234
llvm::LiveRegMatrix::IK_VirtReg
@ IK_VirtReg
Virtual register interference.
Definition: LiveRegMatrix.h:90
llvm::CoalescerPair
A helper class for register coalescers.
Definition: RegisterCoalescer.h:28
TargetSubtargetInfo.h
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
liveregmatrix
liveregmatrix
Definition: LiveRegMatrix.cpp:43
llvm::LiveInterval::SubRange
A live range for subregisters.
Definition: LiveInterval.h:687
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::HexagonISD::CP
@ CP
Definition: HexagonISelLowering.h:53
llvm::BitVector::test
bool test(unsigned Idx) const
Definition: BitVector.h:447
llvm::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:254
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::LiveRegMatrix::IK_RegMask
@ IK_RegMask
RegMask interference.
Definition: LiveRegMatrix.h:100
llvm::LiveIntervalUnion::Query::checkInterference
bool checkInterference()
Definition: LiveIntervalUnion.h:152
llvm::VirtRegMap::clearVirt
void clearVirt(Register virtReg)
clears the specified virtual register's, physical register mapping
Definition: VirtRegMap.h:132
foreachUnit
static bool foreachUnit(const TargetRegisterInfo *TRI, LiveInterval &VRegInterval, MCRegister PhysReg, Callable Func)
Definition: LiveRegMatrix.cpp:80
llvm::LiveIntervals
Definition: LiveIntervals.h:54
llvm::VNInfo
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
LiveInterval.h
llvm::MCRegUnitIterator
Definition: MCRegisterInfo.h:677
llvm::LiveIntervalUnion::Query
Query interferences between a single live virtual register and a live interval union.
Definition: LiveIntervalUnion.h:112
llvm::LiveRegMatrix::ID
static char ID
Definition: LiveRegMatrix.h:66
llvm::MCRegisterInfo::DiffListIterator::isValid
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:224
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::AnalysisUsage::addRequiredTransitive
AnalysisUsage & addRequiredTransitive()
Definition: PassAnalysisSupport.h:81
raw_ostream.h
MachineFunction.h
llvm::printReg
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.
Definition: TargetRegisterInfo.cpp:110
InitializePasses.h
TargetRegisterInfo.h
Debug.h
RegisterCoalescer.h
llvm::LiveIntervals::getRegUnit
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
Definition: LiveIntervals.h:393
llvm::MCRegister
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
llvm::LiveRegMatrix
Definition: LiveRegMatrix.h:40
llvm::LiveInterval::subranges
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:769