/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/LiveRegMatrix.cpp
Line | Count | Source (jump to first uncovered line) |
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/LiveInterval.h" |
18 | | #include "llvm/CodeGen/LiveIntervalAnalysis.h" |
19 | | #include "llvm/CodeGen/LiveIntervalUnion.h" |
20 | | #include "llvm/CodeGen/MachineFunction.h" |
21 | | #include "llvm/CodeGen/VirtRegMap.h" |
22 | | #include "llvm/MC/LaneBitmask.h" |
23 | | #include "llvm/MC/MCRegisterInfo.h" |
24 | | #include "llvm/Pass.h" |
25 | | #include "llvm/Support/Debug.h" |
26 | | #include "llvm/Support/raw_ostream.h" |
27 | | #include "llvm/Target/TargetRegisterInfo.h" |
28 | | #include "llvm/Target/TargetSubtargetInfo.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 | 36.7k | INITIALIZE_PASS_BEGIN36.7k (LiveRegMatrix, "liveregmatrix",
|
40 | 36.7k | "Live Register Matrix", false, false) |
41 | 36.7k | INITIALIZE_PASS_DEPENDENCY(LiveIntervals) |
42 | 36.7k | INITIALIZE_PASS_DEPENDENCY(VirtRegMap) |
43 | 36.7k | INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix", |
44 | | "Live Register Matrix", false, false) |
45 | | |
46 | 31.7k | LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {} |
47 | | |
48 | 31.8k | void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const { |
49 | 31.8k | AU.setPreservesAll(); |
50 | 31.8k | AU.addRequiredTransitive<LiveIntervals>(); |
51 | 31.8k | AU.addRequiredTransitive<VirtRegMap>(); |
52 | 31.8k | MachineFunctionPass::getAnalysisUsage(AU); |
53 | 31.8k | } |
54 | | |
55 | 587k | bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) { |
56 | 587k | TRI = MF.getSubtarget().getRegisterInfo(); |
57 | 587k | LIS = &getAnalysis<LiveIntervals>(); |
58 | 587k | VRM = &getAnalysis<VirtRegMap>(); |
59 | 587k | |
60 | 587k | unsigned NumRegUnits = TRI->getNumRegUnits(); |
61 | 587k | if (NumRegUnits != Matrix.size()) |
62 | 30.8k | Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]); |
63 | 587k | Matrix.init(LIUAlloc, NumRegUnits); |
64 | 587k | |
65 | 587k | // Make sure no stale queries get reused. |
66 | 587k | invalidateVirtRegs(); |
67 | 587k | return false; |
68 | 587k | } |
69 | | |
70 | 587k | void LiveRegMatrix::releaseMemory() { |
71 | 76.1M | for (unsigned i = 0, e = Matrix.size(); i != e76.1M ; ++i75.6M ) { |
72 | 75.6M | Matrix[i].clear(); |
73 | 75.6M | // No need to clear Queries here, since LiveIntervalUnion::Query doesn't |
74 | 75.6M | // have anything important to clear and LiveRegMatrix's runOnFunction() |
75 | 75.6M | // does a std::unique_ptr::reset anyways. |
76 | 75.6M | } |
77 | 587k | } |
78 | | |
79 | | template <typename Callable> |
80 | | static bool foreachUnit(const TargetRegisterInfo *TRI, |
81 | | LiveInterval &VRegInterval, unsigned PhysReg, |
82 | 146M | Callable Func) { |
83 | 146M | if (VRegInterval.hasSubRanges()146M ) { |
84 | 4.52M | for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid()4.52M ; ++Units2.71M ) { |
85 | 3.75M | unsigned Unit = (*Units).first; |
86 | 3.75M | LaneBitmask Mask = (*Units).second; |
87 | 7.04M | for (LiveInterval::SubRange &S : VRegInterval.subranges()) { |
88 | 7.04M | if ((S.LaneMask & Mask).any()7.04M ) { |
89 | 3.74M | if (Func(Unit, S)) |
90 | 1.04M | return true; |
91 | 2.69M | break; |
92 | 2.69M | } |
93 | 7.04M | } |
94 | 3.75M | } |
95 | 146M | } else { |
96 | 233M | for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid()233M ; ++Units88.2M ) { |
97 | 146M | if (Func(*Units, VRegInterval)) |
98 | 57.9M | return true; |
99 | 146M | } |
100 | 145M | } |
101 | 87.9M | return false; |
102 | 146M | } LiveRegMatrix.cpp:bool foreachUnit<llvm::LiveRegMatrix::assign(llvm::LiveInterval&, unsigned int)::$_0>(llvm::TargetRegisterInfo const*, llvm::LiveInterval&, unsigned int, llvm::LiveRegMatrix::assign(llvm::LiveInterval&, unsigned int)::$_0) Line | Count | Source | 82 | 10.4M | Callable Func) { | 83 | 10.4M | if (VRegInterval.hasSubRanges()10.4M ) { | 84 | 198k | for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid()198k ; ++Units150k ) { | 85 | 150k | unsigned Unit = (*Units).first; | 86 | 150k | LaneBitmask Mask = (*Units).second; | 87 | 343k | for (LiveInterval::SubRange &S : VRegInterval.subranges()) { | 88 | 343k | if ((S.LaneMask & Mask).any()343k ) { | 89 | 147k | if (Func(Unit, S)) | 90 | 0 | return true; | 91 | 147k | break; | 92 | 147k | } | 93 | 343k | } | 94 | 150k | } | 95 | 10.4M | } else { | 96 | 21.0M | for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid()21.0M ; ++Units10.6M ) { | 97 | 10.6M | if (Func(*Units, VRegInterval)) | 98 | 0 | return true; | 99 | 10.6M | } | 100 | 10.4M | } | 101 | 10.4M | return false; | 102 | 10.4M | } |
LiveRegMatrix.cpp:bool foreachUnit<llvm::LiveRegMatrix::unassign(llvm::LiveInterval&)::$_1>(llvm::TargetRegisterInfo const*, llvm::LiveInterval&, unsigned int, llvm::LiveRegMatrix::unassign(llvm::LiveInterval&)::$_1) Line | Count | Source | 82 | 603k | Callable Func) { | 83 | 603k | if (VRegInterval.hasSubRanges()603k ) { | 84 | 3.93k | for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid()3.93k ; ++Units2.87k ) { | 85 | 2.87k | unsigned Unit = (*Units).first; | 86 | 2.87k | LaneBitmask Mask = (*Units).second; | 87 | 5.80k | for (LiveInterval::SubRange &S : VRegInterval.subranges()) { | 88 | 5.80k | if ((S.LaneMask & Mask).any()5.80k ) { | 89 | 2.86k | if (Func(Unit, S)) | 90 | 0 | return true; | 91 | 2.86k | break; | 92 | 2.86k | } | 93 | 5.80k | } | 94 | 2.87k | } | 95 | 603k | } else { | 96 | 1.22M | for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid()1.22M ; ++Units617k ) { | 97 | 617k | if (Func(*Units, VRegInterval)) | 98 | 0 | return true; | 99 | 617k | } | 100 | 602k | } | 101 | 603k | return false; | 102 | 603k | } |
LiveRegMatrix.cpp:bool foreachUnit<llvm::LiveRegMatrix::checkRegUnitInterference(llvm::LiveInterval&, unsigned int)::$_2>(llvm::TargetRegisterInfo const*, llvm::LiveInterval&, unsigned int, llvm::LiveRegMatrix::checkRegUnitInterference(llvm::LiveInterval&, unsigned int)::$_2) Line | Count | Source | 82 | 68.9M | Callable Func) { | 83 | 68.9M | if (VRegInterval.hasSubRanges()68.9M ) { | 84 | 3.48M | for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid()3.48M ; ++Units2.38M ) { | 85 | 2.81M | unsigned Unit = (*Units).first; | 86 | 2.81M | LaneBitmask Mask = (*Units).second; | 87 | 5.57M | for (LiveInterval::SubRange &S : VRegInterval.subranges()) { | 88 | 5.57M | if ((S.LaneMask & Mask).any()5.57M ) { | 89 | 2.79M | if (Func(Unit, S)) | 90 | 424k | return true; | 91 | 2.37M | break; | 92 | 2.37M | } | 93 | 5.57M | } | 94 | 2.81M | } | 95 | 68.9M | } else { | 96 | 134M | for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid()134M ; ++Units66.8M ) { | 97 | 68.5M | if (Func(*Units, VRegInterval)) | 98 | 1.64M | return true; | 99 | 68.5M | } | 100 | 67.8M | } | 101 | 66.8M | return false; | 102 | 68.9M | } |
LiveRegMatrix.cpp:bool foreachUnit<llvm::LiveRegMatrix::checkInterference(llvm::LiveInterval&, unsigned int)::$_3>(llvm::TargetRegisterInfo const*, llvm::LiveInterval&, unsigned int, llvm::LiveRegMatrix::checkInterference(llvm::LiveInterval&, unsigned int)::$_3) Line | Count | Source | 82 | 66.8M | Callable Func) { | 83 | 66.8M | if (VRegInterval.hasSubRanges()66.8M ) { | 84 | 843k | for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid()843k ; ++Units171k ) { | 85 | 796k | unsigned Unit = (*Units).first; | 86 | 796k | LaneBitmask Mask = (*Units).second; | 87 | 1.11M | for (LiveInterval::SubRange &S : VRegInterval.subranges()) { | 88 | 1.11M | if ((S.LaneMask & Mask).any()1.11M ) { | 89 | 793k | if (Func(Unit, S)) | 90 | 624k | return true; | 91 | 168k | break; | 92 | 168k | } | 93 | 1.11M | } | 94 | 796k | } | 95 | 66.8M | } else { | 96 | 76.3M | for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid()76.3M ; ++Units10.0M ) { | 97 | 66.4M | if (Func(*Units, VRegInterval)) | 98 | 56.3M | return true; | 99 | 66.4M | } | 100 | 66.2M | } | 101 | 9.93M | return false; | 102 | 66.8M | } |
|
103 | | |
104 | 10.4M | void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) { |
105 | 10.4M | DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) |
106 | 10.4M | << " to " << PrintReg(PhysReg, TRI) << ':'); |
107 | 10.4M | assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); |
108 | 10.4M | VRM->assignVirt2Phys(VirtReg.reg, PhysReg); |
109 | 10.4M | |
110 | 10.4M | foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit, |
111 | 10.7M | const LiveRange &Range) { |
112 | 10.7M | DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << ' ' << Range); |
113 | 10.7M | Matrix[Unit].unify(VirtReg, Range); |
114 | 10.7M | return false; |
115 | 10.7M | }); |
116 | 10.4M | |
117 | 10.4M | ++NumAssigned; |
118 | 10.4M | DEBUG(dbgs() << '\n'); |
119 | 10.4M | } |
120 | | |
121 | 603k | void LiveRegMatrix::unassign(LiveInterval &VirtReg) { |
122 | 603k | unsigned PhysReg = VRM->getPhys(VirtReg.reg); |
123 | 603k | DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI) |
124 | 603k | << " from " << PrintReg(PhysReg, TRI) << ':'); |
125 | 603k | VRM->clearVirt(VirtReg.reg); |
126 | 603k | |
127 | 603k | foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit, |
128 | 620k | const LiveRange &Range) { |
129 | 620k | DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI)); |
130 | 620k | Matrix[Unit].extract(VirtReg, Range); |
131 | 620k | return false; |
132 | 620k | }); |
133 | 603k | |
134 | 603k | ++NumUnassigned; |
135 | 603k | DEBUG(dbgs() << '\n'); |
136 | 603k | } |
137 | | |
138 | 1.84M | bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const { |
139 | 2.92M | for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid()2.92M ; ++Unit1.07M ) { |
140 | 1.85M | if (!Matrix[*Unit].empty()) |
141 | 781k | return true; |
142 | 1.85M | } |
143 | 1.06M | return false; |
144 | 1.84M | } |
145 | | |
146 | | bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg, |
147 | 124M | unsigned PhysReg) { |
148 | 124M | // Check if the cached information is valid. |
149 | 124M | // The same BitVector can be reused for all PhysRegs. |
150 | 124M | // We could cache multiple VirtRegs if it becomes necessary. |
151 | 124M | if (RegMaskVirtReg != VirtReg.reg || 124M RegMaskTag != UserTag113M ) { |
152 | 11.2M | RegMaskVirtReg = VirtReg.reg; |
153 | 11.2M | RegMaskTag = UserTag; |
154 | 11.2M | RegMaskUsable.clear(); |
155 | 11.2M | LIS->checkRegMaskInterference(VirtReg, RegMaskUsable); |
156 | 11.2M | } |
157 | 124M | |
158 | 124M | // The BitVector is indexed by PhysReg, not register unit. |
159 | 124M | // Regmask interference is more fine grained than regunits. |
160 | 124M | // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8. |
161 | 76.3M | return !RegMaskUsable.empty() && (!PhysReg || 76.3M !RegMaskUsable.test(PhysReg)76.3M ); |
162 | 124M | } |
163 | | |
164 | | bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg, |
165 | 68.9M | unsigned PhysReg) { |
166 | 68.9M | if (VirtReg.empty()) |
167 | 0 | return false; |
168 | 68.9M | CoalescerPair CP(VirtReg.reg, PhysReg, *TRI); |
169 | 68.9M | |
170 | 68.9M | bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit, |
171 | 71.3M | const LiveRange &Range) { |
172 | 71.3M | const LiveRange &UnitRange = LIS->getRegUnit(Unit); |
173 | 71.3M | return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes()); |
174 | 71.3M | }); |
175 | 68.9M | return Result; |
176 | 68.9M | } |
177 | | |
178 | | LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR, |
179 | 86.3M | unsigned RegUnit) { |
180 | 86.3M | LiveIntervalUnion::Query &Q = Queries[RegUnit]; |
181 | 86.3M | Q.init(UserTag, LR, Matrix[RegUnit]); |
182 | 86.3M | return Q; |
183 | 86.3M | } |
184 | | |
185 | | LiveRegMatrix::InterferenceKind |
186 | 124M | LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) { |
187 | 124M | if (VirtReg.empty()) |
188 | 6.09k | return IK_Free; |
189 | 124M | |
190 | 124M | // Regmask interference is the fastest check. |
191 | 124M | if (124M checkRegMaskInterference(VirtReg, PhysReg)124M ) |
192 | 55.2M | return IK_RegMask; |
193 | 68.9M | |
194 | 68.9M | // Check for fixed interference. |
195 | 68.9M | if (68.9M checkRegUnitInterference(VirtReg, PhysReg)68.9M ) |
196 | 2.06M | return IK_RegUnit; |
197 | 66.8M | |
198 | 66.8M | // Check the matrix for virtual register interference. |
199 | 66.8M | bool Interference = foreachUnit(TRI, VirtReg, PhysReg, |
200 | 67.2M | [&](unsigned Unit, const LiveRange &LR) { |
201 | 67.2M | return query(LR, Unit).checkInterference(); |
202 | 67.2M | }); |
203 | 66.8M | if (Interference) |
204 | 56.9M | return IK_VirtReg; |
205 | 9.93M | |
206 | 9.93M | return IK_Free; |
207 | 9.93M | } |