LLVM  6.0.0svn
LiveRegMatrix.cpp
Go to the documentation of this file.
1 //===- LiveRegMatrix.cpp - Track register interference --------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the LiveRegMatrix analysis pass.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "RegisterCoalescer.h"
16 #include "llvm/ADT/Statistic.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 
46 LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {}
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, unsigned 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 
104 void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
105  DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI)
106  << " to " << PrintReg(PhysReg, TRI) << ':');
107  assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
108  VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
109 
110  foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
111  const LiveRange &Range) {
112  DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << ' ' << Range);
113  Matrix[Unit].unify(VirtReg, Range);
114  return false;
115  });
116 
117  ++NumAssigned;
118  DEBUG(dbgs() << '\n');
119 }
120 
122  unsigned PhysReg = VRM->getPhys(VirtReg.reg);
123  DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI)
124  << " from " << PrintReg(PhysReg, TRI) << ':');
125  VRM->clearVirt(VirtReg.reg);
126 
127  foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
128  const LiveRange &Range) {
129  DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI));
130  Matrix[Unit].extract(VirtReg, Range);
131  return false;
132  });
133 
134  ++NumUnassigned;
135  DEBUG(dbgs() << '\n');
136 }
137 
138 bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const {
139  for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
140  if (!Matrix[*Unit].empty())
141  return true;
142  }
143  return false;
144 }
145 
147  unsigned 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  unsigned 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  unsigned RegUnit) {
180  LiveIntervalUnion::Query &Q = Queries[RegUnit];
181  Q.init(UserTag, LR, Matrix[RegUnit]);
182  return Q;
183 }
184 
186 LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
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  [&](unsigned Unit, const LiveRange &LR) {
201  return query(LR, Unit).checkInterference();
202  });
203  if (Interference)
204  return IK_VirtReg;
205 
206  return IK_Free;
207 }
bool empty() const
Definition: LiveInterval.h:370
A common definition of LaneBitmask for use in TableGen and CodeGen.
No interference, go ahead and assign.
Definition: LiveRegMatrix.h:86
const unsigned reg
Definition: LiveInterval.h:667
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
bool empty() const
empty - Tests whether there are no bits in this bitvector.
Definition: BitVector.h:167
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:638
bool test(unsigned Idx) const
Definition: BitVector.h:502
liveregmatrix
A live range for subregisters.
Definition: LiveInterval.h:645
STATISTIC(NumFunctions, "Total number of functions")
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:157
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
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:367
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:723
Register unit interference.
Definition: LiveRegMatrix.h:96
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:751
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.
void init(unsigned NewUserTag, const LiveRange &NewLR, const LiveIntervalUnion &NewLiveUnion)
RegMask interference.
Printable PrintReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
void invalidateVirtRegs()
Invalidate cached interference queries after modifying virtual register live ranges.
Definition: LiveRegMatrix.h:82
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.
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...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Printable PrintRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
void assignVirt2Phys(unsigned virtReg, MCPhysReg physReg)
creates a mapping for the specified virtual register to the specified physical register ...
Definition: VirtRegMap.cpp:83
bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg)
Check for regunit interference only.
void init(LiveIntervalUnion::Allocator &, unsigned Size)
Promote Memory to Register
Definition: Mem2Reg.cpp:110
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void clearVirt(unsigned virtReg)
clears the specified virtual register&#39;s, physical register mapping
Definition: VirtRegMap.h:112
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:436
bool hasPhys(unsigned virtReg) const
returns true if the specified virtual register is mapped to a physical register
Definition: VirtRegMap.h:95
AnalysisUsage & addRequiredTransitive()
unsigned getPhys(unsigned virtReg) const
returns the physical register mapped to the specified virtual register
Definition: VirtRegMap.h:101
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:81
#define DEBUG(X)
Definition: Debug.h:118
bool checkRegMaskInterference(LiveInterval &VirtReg, unsigned PhysReg=0)
Check for regmask interference only.
Virtual register interference.
Definition: LiveRegMatrix.h:91
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.