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
14 #include "llvm/CodeGen/LiveRegMatrix.h"
15 #include "RegisterCoalescer.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
18 #include "llvm/CodeGen/VirtRegMap.h"
19 #include "llvm/Support/Debug.h"
20 #include "llvm/Support/raw_ostream.h"
21 #include "llvm/Target/TargetRegisterInfo.h"
22 #include "llvm/Target/TargetSubtargetInfo.h"
23
24 using namespace llvm;
25
26 #define DEBUG_TYPE "regalloc"
27
28 STATISTIC(NumAssigned , "Number of registers assigned");
29 STATISTIC(NumUnassigned , "Number of registers unassigned");
30
31 char LiveRegMatrix::ID = 0;
32 INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
33 "Live Register Matrix", false, false)
INITIALIZE_PASS_DEPENDENCY(LiveIntervals)34 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
35 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
36 INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
37 "Live Register Matrix", false, false)
38
39 LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID),
40 UserTag(0), RegMaskTag(0), RegMaskVirtReg(0) {}
41
getAnalysisUsage(AnalysisUsage & AU) const42 void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
43 AU.setPreservesAll();
44 AU.addRequiredTransitive<LiveIntervals>();
45 AU.addRequiredTransitive<VirtRegMap>();
46 MachineFunctionPass::getAnalysisUsage(AU);
47 }
48
runOnMachineFunction(MachineFunction & MF)49 bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
50 TRI = MF.getSubtarget().getRegisterInfo();
51 LIS = &getAnalysis<LiveIntervals>();
52 VRM = &getAnalysis<VirtRegMap>();
53
54 unsigned NumRegUnits = TRI->getNumRegUnits();
55 if (NumRegUnits != Matrix.size())
56 Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
57 Matrix.init(LIUAlloc, NumRegUnits);
58
59 // Make sure no stale queries get reused.
60 invalidateVirtRegs();
61 return false;
62 }
63
releaseMemory()64 void LiveRegMatrix::releaseMemory() {
65 for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
66 Matrix[i].clear();
67 // No need to clear Queries here, since LiveIntervalUnion::Query doesn't
68 // have anything important to clear and LiveRegMatrix's runOnFunction()
69 // does a std::unique_ptr::reset anyways.
70 }
71 }
72
73 template<typename Callable>
foreachUnit(const TargetRegisterInfo * TRI,LiveInterval & VRegInterval,unsigned PhysReg,Callable Func)74 bool foreachUnit(const TargetRegisterInfo *TRI, LiveInterval &VRegInterval,
75 unsigned PhysReg, Callable Func) {
76 if (VRegInterval.hasSubRanges()) {
77 for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
78 unsigned Unit = (*Units).first;
79 LaneBitmask Mask = (*Units).second;
80 for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
81 if (S.LaneMask & Mask) {
82 if (Func(Unit, S))
83 return true;
84 break;
85 }
86 }
87 }
88 } else {
89 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
90 if (Func(*Units, VRegInterval))
91 return true;
92 }
93 }
94 return false;
95 }
96
assign(LiveInterval & VirtReg,unsigned PhysReg)97 void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
98 DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI)
99 << " to " << PrintReg(PhysReg, TRI) << ':');
100 assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
101 VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
102
103 foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
104 const LiveRange &Range) {
105 DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << ' ' << Range);
106 Matrix[Unit].unify(VirtReg, Range);
107 return false;
108 });
109
110 ++NumAssigned;
111 DEBUG(dbgs() << '\n');
112 }
113
unassign(LiveInterval & VirtReg)114 void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
115 unsigned PhysReg = VRM->getPhys(VirtReg.reg);
116 DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI)
117 << " from " << PrintReg(PhysReg, TRI) << ':');
118 VRM->clearVirt(VirtReg.reg);
119
120 foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
121 const LiveRange &Range) {
122 DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI));
123 Matrix[Unit].extract(VirtReg, Range);
124 return false;
125 });
126
127 ++NumUnassigned;
128 DEBUG(dbgs() << '\n');
129 }
130
isPhysRegUsed(unsigned PhysReg) const131 bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const {
132 for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
133 if (!Matrix[*Unit].empty())
134 return true;
135 }
136 return false;
137 }
138
checkRegMaskInterference(LiveInterval & VirtReg,unsigned PhysReg)139 bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
140 unsigned PhysReg) {
141 // Check if the cached information is valid.
142 // The same BitVector can be reused for all PhysRegs.
143 // We could cache multiple VirtRegs if it becomes necessary.
144 if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) {
145 RegMaskVirtReg = VirtReg.reg;
146 RegMaskTag = UserTag;
147 RegMaskUsable.clear();
148 LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
149 }
150
151 // The BitVector is indexed by PhysReg, not register unit.
152 // Regmask interference is more fine grained than regunits.
153 // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
154 return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
155 }
156
checkRegUnitInterference(LiveInterval & VirtReg,unsigned PhysReg)157 bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
158 unsigned PhysReg) {
159 if (VirtReg.empty())
160 return false;
161 CoalescerPair CP(VirtReg.reg, PhysReg, *TRI);
162
163 bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
164 const LiveRange &Range) {
165 const LiveRange &UnitRange = LIS->getRegUnit(Unit);
166 return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
167 });
168 return Result;
169 }
170
query(LiveInterval & VirtReg,unsigned RegUnit)171 LiveIntervalUnion::Query &LiveRegMatrix::query(LiveInterval &VirtReg,
172 unsigned RegUnit) {
173 LiveIntervalUnion::Query &Q = Queries[RegUnit];
174 Q.init(UserTag, &VirtReg, &Matrix[RegUnit]);
175 return Q;
176 }
177
178 LiveRegMatrix::InterferenceKind
checkInterference(LiveInterval & VirtReg,unsigned PhysReg)179 LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
180 if (VirtReg.empty())
181 return IK_Free;
182
183 // Regmask interference is the fastest check.
184 if (checkRegMaskInterference(VirtReg, PhysReg))
185 return IK_RegMask;
186
187 // Check for fixed interference.
188 if (checkRegUnitInterference(VirtReg, PhysReg))
189 return IK_RegUnit;
190
191 // Check the matrix for virtual register interference.
192 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
193 if (query(VirtReg, *Units).checkInterference())
194 return IK_VirtReg;
195
196 return IK_Free;
197 }
198