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