LLVM  10.0.0svn
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/MC/LaneBitmask.h"
24 #include "llvm/MC/MCRegisterInfo.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Support/Debug.h"
28 #include <cassert>
29 
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "regalloc"
33 
34 STATISTIC(NumAssigned , "Number of registers assigned");
35 STATISTIC(NumUnassigned , "Number of registers unassigned");
36 
37 char LiveRegMatrix::ID = 0;
38 INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
39  "Live Register Matrix", false, false)
43  "Live Register Matrix", false, false)
44 
45 LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {}
46 
47 void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
48  AU.setPreservesAll();
52 }
53 
54 bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
55  TRI = MF.getSubtarget().getRegisterInfo();
56  LIS = &getAnalysis<LiveIntervals>();
57  VRM = &getAnalysis<VirtRegMap>();
58 
59  unsigned NumRegUnits = TRI->getNumRegUnits();
60  if (NumRegUnits != Matrix.size())
61  Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
62  Matrix.init(LIUAlloc, NumRegUnits);
63 
64  // Make sure no stale queries get reused.
66  return false;
67 }
68 
69 void LiveRegMatrix::releaseMemory() {
70  for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
71  Matrix[i].clear();
72  // No need to clear Queries here, since LiveIntervalUnion::Query doesn't
73  // have anything important to clear and LiveRegMatrix's runOnFunction()
74  // does a std::unique_ptr::reset anyways.
75  }
76 }
77 
78 template <typename Callable>
79 static bool foreachUnit(const TargetRegisterInfo *TRI,
80  LiveInterval &VRegInterval, unsigned PhysReg,
81  Callable Func) {
82  if (VRegInterval.hasSubRanges()) {
83  for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
84  unsigned Unit = (*Units).first;
85  LaneBitmask Mask = (*Units).second;
86  for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
87  if ((S.LaneMask & Mask).any()) {
88  if (Func(Unit, S))
89  return true;
90  break;
91  }
92  }
93  }
94  } else {
95  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
96  if (Func(*Units, VRegInterval))
97  return true;
98  }
99  }
100  return false;
101 }
102 
103 void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
104  LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg, TRI) << " to "
105  << printReg(PhysReg, TRI) << ':');
106  assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
107  VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
108 
109  foreachUnit(
110  TRI, VirtReg, PhysReg, [&](unsigned Unit, const LiveRange &Range) {
111  LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range);
112  Matrix[Unit].unify(VirtReg, Range);
113  return false;
114  });
115 
116  ++NumAssigned;
117  LLVM_DEBUG(dbgs() << '\n');
118 }
119 
121  Register PhysReg = VRM->getPhys(VirtReg.reg);
122  LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg, TRI) << " from "
123  << printReg(PhysReg, TRI) << ':');
124  VRM->clearVirt(VirtReg.reg);
125 
126  foreachUnit(TRI, VirtReg, PhysReg,
127  [&](unsigned Unit, const LiveRange &Range) {
128  LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI));
129  Matrix[Unit].extract(VirtReg, Range);
130  return false;
131  });
132 
133  ++NumUnassigned;
134  LLVM_DEBUG(dbgs() << '\n');
135 }
136 
137 bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const {
138  for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
139  if (!Matrix[*Unit].empty())
140  return true;
141  }
142  return false;
143 }
144 
146  unsigned PhysReg) {
147  // Check if the cached information is valid.
148  // The same BitVector can be reused for all PhysRegs.
149  // We could cache multiple VirtRegs if it becomes necessary.
150  if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) {
151  RegMaskVirtReg = VirtReg.reg;
152  RegMaskTag = UserTag;
153  RegMaskUsable.clear();
154  LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
155  }
156 
157  // The BitVector is indexed by PhysReg, not register unit.
158  // Regmask interference is more fine grained than regunits.
159  // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
160  return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
161 }
162 
164  unsigned PhysReg) {
165  if (VirtReg.empty())
166  return false;
167  CoalescerPair CP(VirtReg.reg, PhysReg, *TRI);
168 
169  bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
170  const LiveRange &Range) {
171  const LiveRange &UnitRange = LIS->getRegUnit(Unit);
172  return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
173  });
174  return Result;
175 }
176 
178  unsigned RegUnit) {
179  LiveIntervalUnion::Query &Q = Queries[RegUnit];
180  Q.init(UserTag, LR, Matrix[RegUnit]);
181  return Q;
182 }
183 
185 LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
186  if (VirtReg.empty())
187  return IK_Free;
188 
189  // Regmask interference is the fastest check.
190  if (checkRegMaskInterference(VirtReg, PhysReg))
191  return IK_RegMask;
192 
193  // Check for fixed interference.
194  if (checkRegUnitInterference(VirtReg, PhysReg))
195  return IK_RegUnit;
196 
197  // Check the matrix for virtual register interference.
198  bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
199  [&](unsigned Unit, const LiveRange &LR) {
200  return query(LR, Unit).checkInterference();
201  });
202  if (Interference)
203  return IK_VirtReg;
204 
205  return IK_Free;
206 }
207 
209  unsigned PhysReg) {
210  // Construct artificial live range containing only one segment [Start, End).
211  VNInfo valno(0, Start);
212  LiveRange::Segment Seg(Start, End, &valno);
213  LiveRange LR;
214  LR.addSegment(Seg);
215 
216  // Check for interference with that segment
217  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
218  if (query(LR, *Units).checkInterference())
219  return true;
220  }
221  return false;
222 }
bool empty() const
Definition: LiveInterval.h:373
A common definition of LaneBitmask for use in TableGen and CodeGen.
No interference, go ahead and assign.
Definition: LiveRegMatrix.h:85
const unsigned reg
Definition: LiveInterval.h:708
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool empty() const
empty - Tests whether there are no bits in this bitvector.
Definition: BitVector.h:166
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
InterferenceKind checkInterference(LiveInterval &VirtReg, unsigned PhysReg)
Check for interference before assigning VirtReg to PhysReg.
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:679
bool test(unsigned Idx) const
Definition: BitVector.h:501
liveregmatrix
A live range for subregisters.
Definition: LiveInterval.h:686
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:161
STATISTIC(NumFunctions, "Total number of functions")
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.
bool hasPhys(Register virtReg) const
returns true if the specified virtual register is mapped to a physical register
Definition: VirtRegMap.h:96
VNInfo - Value Number Information.
Definition: LiveInterval.h:52
bool checkRegMaskInterference(LiveInterval &LI, BitVector &UsableRegs)
Test if LI is live across any register mask instructions, and compute a bit mask of physical register...
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
Live Register Matrix
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:156
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
bool isValid() const
Returns true if this iterator is not yet at the end.
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
Definition: BitVector.h:366
Query interferences between a single live virtual register and a live interval union.
MCRegUnitMaskIterator enumerates a list of register units and their associated lane masks for Reg...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
LiveIntervalUnion::Query & query(const LiveRange &LR, unsigned RegUnit)
Query a line of the assigned virtual register matrix directly.
A helper class for register coalescers.
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:764
Register unit interference.
Definition: LiveRegMatrix.h:95
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:792
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
bool isPhysRegUsed(unsigned PhysReg) const
Returns true if the given PhysReg has any live intervals assigned.
void assign(LiveInterval &VirtReg, unsigned PhysReg)
Assign VirtReg to PhysReg.
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
void init(unsigned NewUserTag, const LiveRange &NewLR, const LiveIntervalUnion &NewLiveUnion)
RegMask interference.
void invalidateVirtRegs()
Invalidate cached interference queries after modifying virtual register live ranges.
Definition: LiveRegMatrix.h:81
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Represent the analysis usage information of a pass.
void assignVirt2Phys(Register virtReg, MCPhysReg physReg)
creates a mapping for the specified virtual register to the specified physical register ...
Definition: VirtRegMap.cpp:83
INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix", "Live Register Matrix", false, false) INITIALIZE_PASS_END(LiveRegMatrix
void unassign(LiveInterval &VirtReg)
Unassign VirtReg from its PhysReg.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
void clearVirt(Register virtReg)
clears the specified virtual register&#39;s, physical register mapping
Definition: VirtRegMap.h:113
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:197
bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg)
Check for regunit interference only.
void init(LiveIntervalUnion::Allocator &, unsigned Size)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
void setPreservesAll()
Set by analyses that do not transform their input at all.
static bool foreachUnit(const TargetRegisterInfo *TRI, LiveInterval &VRegInterval, unsigned PhysReg, Callable Func)
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
Definition: LiveInterval.h:439
Register getPhys(Register virtReg) const
returns the physical register mapped to the specified virtual register
Definition: VirtRegMap.h:102
AnalysisUsage & addRequiredTransitive()
SlotIndexes * getSlotIndexes() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
bool checkRegMaskInterference(LiveInterval &VirtReg, unsigned PhysReg=0)
Check for regmask interference only.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
Virtual register interference.
Definition: LiveRegMatrix.h:90
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19