OLD | NEW |
1 //===- subzero/src/IceRegAlloc.cpp - Linear-scan implementation -----------===// | 1 //===- subzero/src/IceRegAlloc.cpp - Linear-scan implementation -----------===// |
2 // | 2 // |
3 // The Subzero Code Generator | 3 // The Subzero Code Generator |
4 // | 4 // |
5 // This file is distributed under the University of Illinois Open Source | 5 // This file is distributed under the University of Illinois Open Source |
6 // License. See LICENSE.TXT for details. | 6 // License. See LICENSE.TXT for details. |
7 // | 7 // |
8 //===----------------------------------------------------------------------===// | 8 //===----------------------------------------------------------------------===// |
9 // | 9 // |
10 // This file implements the LinearScan class, which performs the | 10 // This file implements the LinearScan class, which performs the |
(...skipping 11 matching lines...) Expand all Loading... |
22 namespace Ice { | 22 namespace Ice { |
23 | 23 |
24 namespace { | 24 namespace { |
25 | 25 |
26 // Returns true if Var has any definitions within Item's live range. | 26 // Returns true if Var has any definitions within Item's live range. |
27 // TODO(stichnot): Consider trimming the Definitions list similar to | 27 // TODO(stichnot): Consider trimming the Definitions list similar to |
28 // how the live ranges are trimmed, since all the overlapsDefs() tests | 28 // how the live ranges are trimmed, since all the overlapsDefs() tests |
29 // are whether some variable's definitions overlap Cur, and trimming | 29 // are whether some variable's definitions overlap Cur, and trimming |
30 // is with respect Cur.start. Initial tests show no measurable | 30 // is with respect Cur.start. Initial tests show no measurable |
31 // performance difference, so we'll keep the code simple for now. | 31 // performance difference, so we'll keep the code simple for now. |
32 bool overlapsDefs(const Cfg *Func, const LiveRangeWrapper &Item, | 32 bool overlapsDefs(const Cfg *Func, const Variable *Item, const Variable *Var) { |
33 const Variable *Var) { | |
34 const bool UseTrimmed = true; | 33 const bool UseTrimmed = true; |
35 VariablesMetadata *VMetadata = Func->getVMetadata(); | 34 VariablesMetadata *VMetadata = Func->getVMetadata(); |
36 const InstDefList &Defs = VMetadata->getDefinitions(Var); | 35 const InstDefList &Defs = VMetadata->getDefinitions(Var); |
37 for (size_t i = 0; i < Defs.size(); ++i) { | 36 for (size_t i = 0; i < Defs.size(); ++i) { |
38 if (Item.range().overlapsInst(Defs[i]->getNumber(), UseTrimmed)) | 37 if (Item->getLiveRange().overlapsInst(Defs[i]->getNumber(), UseTrimmed)) |
39 return true; | 38 return true; |
40 } | 39 } |
41 return false; | 40 return false; |
42 } | 41 } |
43 | 42 |
44 void dumpDisableOverlap(const Cfg *Func, const Variable *Var, | 43 void dumpDisableOverlap(const Cfg *Func, const Variable *Var, |
45 const char *Reason) { | 44 const char *Reason) { |
46 if (Func->getContext()->isVerbose(IceV_LinearScan)) { | 45 if (Func->getContext()->isVerbose(IceV_LinearScan)) { |
47 VariablesMetadata *VMetadata = Func->getVMetadata(); | 46 VariablesMetadata *VMetadata = Func->getVMetadata(); |
48 Ostream &Str = Func->getContext()->getStrDump(); | 47 Ostream &Str = Func->getContext()->getStrDump(); |
49 Str << "Disabling Overlap due to " << Reason << " " << *Var | 48 Str << "Disabling Overlap due to " << Reason << " " << *Var |
50 << " LIVE=" << Var->getLiveRange() << " Defs="; | 49 << " LIVE=" << Var->getLiveRange() << " Defs="; |
51 const InstDefList &Defs = VMetadata->getDefinitions(Var); | 50 const InstDefList &Defs = VMetadata->getDefinitions(Var); |
52 for (size_t i = 0; i < Defs.size(); ++i) { | 51 for (size_t i = 0; i < Defs.size(); ++i) { |
53 if (i > 0) | 52 if (i > 0) |
54 Str << ","; | 53 Str << ","; |
55 Str << Defs[i]->getNumber(); | 54 Str << Defs[i]->getNumber(); |
56 } | 55 } |
57 Str << "\n"; | 56 Str << "\n"; |
58 } | 57 } |
59 } | 58 } |
60 | 59 |
61 bool compareRanges(const LiveRangeWrapper &L, const LiveRangeWrapper &R) { | 60 void dumpLiveRange(const Variable *Var, const Cfg *Func) { |
62 InstNumberT Lstart = L.Var->getLiveRange().getStart(); | 61 Ostream &Str = Func->getContext()->getStrDump(); |
63 InstNumberT Rstart = R.Var->getLiveRange().getStart(); | 62 const static size_t BufLen = 30; |
64 if (Lstart == Rstart) | 63 char buf[BufLen]; |
65 return L.Var->getIndex() < R.Var->getIndex(); | 64 snprintf(buf, BufLen, "%2d", Var->getRegNumTmp()); |
66 return Lstart < Rstart; | 65 Str << "R=" << buf << " V="; |
| 66 Var->dump(Func); |
| 67 Str << " Range=" << Var->getLiveRange(); |
67 } | 68 } |
68 | 69 |
69 } // end of anonymous namespace | 70 } // end of anonymous namespace |
70 | 71 |
71 // Implements the linear-scan algorithm. Based on "Linear Scan | 72 // Implements the linear-scan algorithm. Based on "Linear Scan |
72 // Register Allocation in the Context of SSA Form and Register | 73 // Register Allocation in the Context of SSA Form and Register |
73 // Constraints" by Hanspeter Mössenböck and Michael Pfeiffer, | 74 // Constraints" by Hanspeter Mössenböck and Michael Pfeiffer, |
74 // ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF . This | 75 // ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF . This |
75 // implementation is modified to take affinity into account and allow | 76 // implementation is modified to take affinity into account and allow |
76 // two interfering variables to share the same register in certain | 77 // two interfering variables to share the same register in certain |
(...skipping 24 matching lines...) Expand all Loading... |
101 for (Variable *Var : Vars) { | 102 for (Variable *Var : Vars) { |
102 // Explicitly don't consider zero-weight variables, which are | 103 // Explicitly don't consider zero-weight variables, which are |
103 // meant to be spill slots. | 104 // meant to be spill slots. |
104 if (Var->getWeight() == RegWeight::Zero) | 105 if (Var->getWeight() == RegWeight::Zero) |
105 continue; | 106 continue; |
106 // Don't bother if the variable has a null live range, which means | 107 // Don't bother if the variable has a null live range, which means |
107 // it was never referenced. | 108 // it was never referenced. |
108 if (Var->getLiveRange().isEmpty()) | 109 if (Var->getLiveRange().isEmpty()) |
109 continue; | 110 continue; |
110 Var->untrimLiveRange(); | 111 Var->untrimLiveRange(); |
111 LiveRangeWrapper R(Var); | 112 Unhandled.push_back(Var); |
112 Unhandled.push_back(R); | |
113 if (Var->hasReg()) { | 113 if (Var->hasReg()) { |
114 Var->setRegNumTmp(Var->getRegNum()); | 114 Var->setRegNumTmp(Var->getRegNum()); |
115 Var->setLiveRangeInfiniteWeight(); | 115 Var->setLiveRangeInfiniteWeight(); |
116 UnhandledPrecolored.push_back(R); | 116 UnhandledPrecolored.push_back(Var); |
117 } | 117 } |
118 } | 118 } |
| 119 struct CompareRanges { |
| 120 bool operator()(const Variable *L, const Variable *R) { |
| 121 InstNumberT Lstart = L->getLiveRange().getStart(); |
| 122 InstNumberT Rstart = R->getLiveRange().getStart(); |
| 123 if (Lstart == Rstart) |
| 124 return L->getIndex() < R->getIndex(); |
| 125 return Lstart < Rstart; |
| 126 } |
| 127 }; |
119 // Do a reverse sort so that erasing elements (from the end) is fast. | 128 // Do a reverse sort so that erasing elements (from the end) is fast. |
120 std::sort(Unhandled.rbegin(), Unhandled.rend(), compareRanges); | 129 std::sort(Unhandled.rbegin(), Unhandled.rend(), CompareRanges()); |
121 std::sort(UnhandledPrecolored.rbegin(), UnhandledPrecolored.rend(), | 130 std::sort(UnhandledPrecolored.rbegin(), UnhandledPrecolored.rend(), |
122 compareRanges); | 131 CompareRanges()); |
123 } | 132 } |
124 | 133 |
125 // RegUses[I] is the number of live ranges (variables) that register | 134 // RegUses[I] is the number of live ranges (variables) that register |
126 // I is currently assigned to. It can be greater than 1 as a result | 135 // I is currently assigned to. It can be greater than 1 as a result |
127 // of AllowOverlap inference below. | 136 // of AllowOverlap inference below. |
128 std::vector<int> RegUses(RegMaskFull.size()); | 137 std::vector<int> RegUses(RegMaskFull.size()); |
129 // Unhandled is already set to all ranges in increasing order of | 138 // Unhandled is already set to all ranges in increasing order of |
130 // start points. | 139 // start points. |
131 assert(Active.empty()); | 140 assert(Active.empty()); |
132 assert(Inactive.empty()); | 141 assert(Inactive.empty()); |
133 assert(Handled.empty()); | 142 assert(Handled.empty()); |
134 UnorderedRanges::iterator Next; | 143 UnorderedRanges::iterator Next; |
135 | 144 |
136 while (!Unhandled.empty()) { | 145 while (!Unhandled.empty()) { |
137 LiveRangeWrapper Cur = Unhandled.back(); | 146 Variable *Cur = Unhandled.back(); |
138 Unhandled.pop_back(); | 147 Unhandled.pop_back(); |
139 if (Verbose) { | 148 if (Verbose) { |
140 Str << "\nConsidering "; | 149 Str << "\nConsidering "; |
141 Cur.dump(Func); | 150 dumpLiveRange(Cur, Func); |
142 Str << "\n"; | 151 Str << "\n"; |
143 } | 152 } |
144 const llvm::SmallBitVector RegMask = | 153 const llvm::SmallBitVector RegMask = |
145 RegMaskFull & | 154 RegMaskFull & Func->getTarget()->getRegisterSetForType(Cur->getType()); |
146 Func->getTarget()->getRegisterSetForType(Cur.Var->getType()); | |
147 | 155 |
148 // Check for precolored ranges. If Cur is precolored, it | 156 // Check for precolored ranges. If Cur is precolored, it |
149 // definitely gets that register. Previously processed live | 157 // definitely gets that register. Previously processed live |
150 // ranges would have avoided that register due to it being | 158 // ranges would have avoided that register due to it being |
151 // precolored. Future processed live ranges won't evict that | 159 // precolored. Future processed live ranges won't evict that |
152 // register because the live range has infinite weight. | 160 // register because the live range has infinite weight. |
153 if (Cur.Var->hasReg()) { | 161 if (Cur->hasReg()) { |
154 int32_t RegNum = Cur.Var->getRegNum(); | 162 int32_t RegNum = Cur->getRegNum(); |
155 // RegNumTmp should have already been set above. | 163 // RegNumTmp should have already been set above. |
156 assert(Cur.Var->getRegNumTmp() == RegNum); | 164 assert(Cur->getRegNumTmp() == RegNum); |
157 if (Verbose) { | 165 if (Verbose) { |
158 Str << "Precoloring "; | 166 Str << "Precoloring "; |
159 Cur.dump(Func); | 167 dumpLiveRange(Cur, Func); |
160 Str << "\n"; | 168 Str << "\n"; |
161 } | 169 } |
162 Active.push_back(Cur); | 170 Active.push_back(Cur); |
163 assert(RegUses[RegNum] >= 0); | 171 assert(RegUses[RegNum] >= 0); |
164 ++RegUses[RegNum]; | 172 ++RegUses[RegNum]; |
165 assert(!UnhandledPrecolored.empty()); | 173 assert(!UnhandledPrecolored.empty()); |
166 assert(UnhandledPrecolored.back().Var == Cur.Var); | 174 assert(UnhandledPrecolored.back() == Cur); |
167 UnhandledPrecolored.pop_back(); | 175 UnhandledPrecolored.pop_back(); |
168 continue; | 176 continue; |
169 } | 177 } |
170 | 178 |
171 // Check for active ranges that have expired or become inactive. | 179 // Check for active ranges that have expired or become inactive. |
172 for (auto I = Active.begin(), E = Active.end(); I != E; I = Next) { | 180 for (auto I = Active.begin(), E = Active.end(); I != E; I = Next) { |
173 Next = I; | 181 Next = I; |
174 ++Next; | 182 ++Next; |
175 LiveRangeWrapper Item = *I; | 183 Variable *Item = *I; |
176 Item.Var->trimLiveRange(Cur.range().getStart()); | 184 Item->trimLiveRange(Cur->getLiveRange().getStart()); |
177 bool Moved = false; | 185 bool Moved = false; |
178 if (Item.endsBefore(Cur)) { | 186 if (Item->rangeEndsBefore(Cur)) { |
179 // Move Item from Active to Handled list. | 187 // Move Item from Active to Handled list. |
180 if (Verbose) { | 188 if (Verbose) { |
181 Str << "Expiring "; | 189 Str << "Expiring "; |
182 Item.dump(Func); | 190 dumpLiveRange(Item, Func); |
183 Str << "\n"; | 191 Str << "\n"; |
184 } | 192 } |
185 Handled.splice(Handled.end(), Active, I); | 193 Handled.splice(Handled.end(), Active, I); |
186 Moved = true; | 194 Moved = true; |
187 } else if (!Item.overlapsStart(Cur)) { | 195 } else if (!Item->rangeOverlapsStart(Cur)) { |
188 // Move Item from Active to Inactive list. | 196 // Move Item from Active to Inactive list. |
189 if (Verbose) { | 197 if (Verbose) { |
190 Str << "Inactivating "; | 198 Str << "Inactivating "; |
191 Item.dump(Func); | 199 dumpLiveRange(Item, Func); |
192 Str << "\n"; | 200 Str << "\n"; |
193 } | 201 } |
194 Inactive.splice(Inactive.end(), Active, I); | 202 Inactive.splice(Inactive.end(), Active, I); |
195 Moved = true; | 203 Moved = true; |
196 } | 204 } |
197 if (Moved) { | 205 if (Moved) { |
198 // Decrement Item from RegUses[]. | 206 // Decrement Item from RegUses[]. |
199 assert(Item.Var->hasRegTmp()); | 207 assert(Item->hasRegTmp()); |
200 int32_t RegNum = Item.Var->getRegNumTmp(); | 208 int32_t RegNum = Item->getRegNumTmp(); |
201 --RegUses[RegNum]; | 209 --RegUses[RegNum]; |
202 assert(RegUses[RegNum] >= 0); | 210 assert(RegUses[RegNum] >= 0); |
203 } | 211 } |
204 } | 212 } |
205 | 213 |
206 // Check for inactive ranges that have expired or reactivated. | 214 // Check for inactive ranges that have expired or reactivated. |
207 for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) { | 215 for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) { |
208 Next = I; | 216 Next = I; |
209 ++Next; | 217 ++Next; |
210 LiveRangeWrapper Item = *I; | 218 Variable *Item = *I; |
211 Item.Var->trimLiveRange(Cur.range().getStart()); | 219 Item->trimLiveRange(Cur->getLiveRange().getStart()); |
212 // As an optimization, don't bother checking pure point-valued | 220 // As an optimization, don't bother checking pure point-valued |
213 // Inactive ranges, because the overlapsStart() test will never | 221 // Inactive ranges, because the overlapsStart() test will never |
214 // succeed, and the endsBefore() test will generally only | 222 // succeed, and the rangeEndsBefore() test will generally only |
215 // succeed after the last call instruction, which statistically | 223 // succeed after the last call instruction, which statistically |
216 // happens near the end. TODO(stichnot): Consider suppressing | 224 // happens near the end. TODO(stichnot): Consider suppressing |
217 // this check every N iterations in case calls are only at the | 225 // this check every N iterations in case calls are only at the |
218 // beginning of the function. | 226 // beginning of the function. |
219 if (!Item.range().isNonpoints()) | 227 if (!Item->getLiveRange().isNonpoints()) |
220 continue; | 228 continue; |
221 if (Item.endsBefore(Cur)) { | 229 if (Item->rangeEndsBefore(Cur)) { |
222 // Move Item from Inactive to Handled list. | 230 // Move Item from Inactive to Handled list. |
223 if (Verbose) { | 231 if (Verbose) { |
224 Str << "Expiring "; | 232 Str << "Expiring "; |
225 Item.dump(Func); | 233 dumpLiveRange(Item, Func); |
226 Str << "\n"; | 234 Str << "\n"; |
227 } | 235 } |
228 Handled.splice(Handled.end(), Inactive, I); | 236 Handled.splice(Handled.end(), Inactive, I); |
229 } else if (Item.overlapsStart(Cur)) { | 237 } else if (Item->rangeOverlapsStart(Cur)) { |
230 // Move Item from Inactive to Active list. | 238 // Move Item from Inactive to Active list. |
231 if (Verbose) { | 239 if (Verbose) { |
232 Str << "Reactivating "; | 240 Str << "Reactivating "; |
233 Item.dump(Func); | 241 dumpLiveRange(Item, Func); |
234 Str << "\n"; | 242 Str << "\n"; |
235 } | 243 } |
236 Active.splice(Active.end(), Inactive, I); | 244 Active.splice(Active.end(), Inactive, I); |
237 // Increment Item in RegUses[]. | 245 // Increment Item in RegUses[]. |
238 assert(Item.Var->hasRegTmp()); | 246 assert(Item->hasRegTmp()); |
239 int32_t RegNum = Item.Var->getRegNumTmp(); | 247 int32_t RegNum = Item->getRegNumTmp(); |
240 assert(RegUses[RegNum] >= 0); | 248 assert(RegUses[RegNum] >= 0); |
241 ++RegUses[RegNum]; | 249 ++RegUses[RegNum]; |
242 } | 250 } |
243 } | 251 } |
244 | 252 |
245 // Calculate available registers into Free[]. | 253 // Calculate available registers into Free[]. |
246 llvm::SmallBitVector Free = RegMask; | 254 llvm::SmallBitVector Free = RegMask; |
247 for (SizeT i = 0; i < RegMask.size(); ++i) { | 255 for (SizeT i = 0; i < RegMask.size(); ++i) { |
248 if (RegUses[i] > 0) | 256 if (RegUses[i] > 0) |
249 Free[i] = false; | 257 Free[i] = false; |
250 } | 258 } |
251 | 259 |
252 // Infer register preference and allowable overlap. Only form a | 260 // Infer register preference and allowable overlap. Only form a |
253 // preference when the current Variable has an unambiguous "first" | 261 // preference when the current Variable has an unambiguous "first" |
254 // definition. The preference is some source Variable of the | 262 // definition. The preference is some source Variable of the |
255 // defining instruction that either is assigned a register that is | 263 // defining instruction that either is assigned a register that is |
256 // currently free, or that is assigned a register that is not free | 264 // currently free, or that is assigned a register that is not free |
257 // but overlap is allowed. Overlap is allowed when the Variable | 265 // but overlap is allowed. Overlap is allowed when the Variable |
258 // under consideration is single-definition, and its definition is | 266 // under consideration is single-definition, and its definition is |
259 // a simple assignment - i.e., the register gets copied/aliased | 267 // a simple assignment - i.e., the register gets copied/aliased |
260 // but is never modified. Furthermore, overlap is only allowed | 268 // but is never modified. Furthermore, overlap is only allowed |
261 // when preferred Variable definition instructions do not appear | 269 // when preferred Variable definition instructions do not appear |
262 // within the current Variable's live range. | 270 // within the current Variable's live range. |
263 Variable *Prefer = NULL; | 271 Variable *Prefer = NULL; |
264 int32_t PreferReg = Variable::NoRegister; | 272 int32_t PreferReg = Variable::NoRegister; |
265 bool AllowOverlap = false; | 273 bool AllowOverlap = false; |
266 if (const Inst *DefInst = VMetadata->getFirstDefinition(Cur.Var)) { | 274 if (const Inst *DefInst = VMetadata->getFirstDefinition(Cur)) { |
267 assert(DefInst->getDest() == Cur.Var); | 275 assert(DefInst->getDest() == Cur); |
268 bool IsAssign = DefInst->isSimpleAssign(); | 276 bool IsAssign = DefInst->isSimpleAssign(); |
269 bool IsSingleDef = !VMetadata->isMultiDef(Cur.Var); | 277 bool IsSingleDef = !VMetadata->isMultiDef(Cur); |
270 for (SizeT i = 0; i < DefInst->getSrcSize(); ++i) { | 278 for (SizeT i = 0; i < DefInst->getSrcSize(); ++i) { |
271 // TODO(stichnot): Iterate through the actual Variables of the | 279 // TODO(stichnot): Iterate through the actual Variables of the |
272 // instruction, not just the source operands. This could | 280 // instruction, not just the source operands. This could |
273 // capture Load instructions, including address mode | 281 // capture Load instructions, including address mode |
274 // optimization, for Prefer (but not for AllowOverlap). | 282 // optimization, for Prefer (but not for AllowOverlap). |
275 if (Variable *SrcVar = llvm::dyn_cast<Variable>(DefInst->getSrc(i))) { | 283 if (Variable *SrcVar = llvm::dyn_cast<Variable>(DefInst->getSrc(i))) { |
276 int32_t SrcReg = SrcVar->getRegNumTmp(); | 284 int32_t SrcReg = SrcVar->getRegNumTmp(); |
277 // Only consider source variables that have (so far) been | 285 // Only consider source variables that have (so far) been |
278 // assigned a register. That register must be one in the | 286 // assigned a register. That register must be one in the |
279 // RegMask set, e.g. don't try to prefer the stack pointer | 287 // RegMask set, e.g. don't try to prefer the stack pointer |
(...skipping 16 matching lines...) Expand all Loading... |
296 if (Verbose) { | 304 if (Verbose) { |
297 if (Prefer) { | 305 if (Prefer) { |
298 Str << "Initial Prefer=" << *Prefer << " R=" << PreferReg | 306 Str << "Initial Prefer=" << *Prefer << " R=" << PreferReg |
299 << " LIVE=" << Prefer->getLiveRange() << " Overlap=" << AllowOverlap | 307 << " LIVE=" << Prefer->getLiveRange() << " Overlap=" << AllowOverlap |
300 << "\n"; | 308 << "\n"; |
301 } | 309 } |
302 } | 310 } |
303 | 311 |
304 // Remove registers from the Free[] list where an Inactive range | 312 // Remove registers from the Free[] list where an Inactive range |
305 // overlaps with the current range. | 313 // overlaps with the current range. |
306 for (const LiveRangeWrapper &Item : Inactive) { | 314 for (const Variable *Item : Inactive) { |
307 if (Item.overlaps(Cur)) { | 315 if (Item->rangeOverlaps(Cur)) { |
308 int32_t RegNum = Item.Var->getRegNumTmp(); | 316 int32_t RegNum = Item->getRegNumTmp(); |
309 // Don't assert(Free[RegNum]) because in theory (though | 317 // Don't assert(Free[RegNum]) because in theory (though |
310 // probably never in practice) there could be two inactive | 318 // probably never in practice) there could be two inactive |
311 // variables that were marked with AllowOverlap. | 319 // variables that were marked with AllowOverlap. |
312 Free[RegNum] = false; | 320 Free[RegNum] = false; |
313 // Disable AllowOverlap if an Inactive variable, which is not | 321 // Disable AllowOverlap if an Inactive variable, which is not |
314 // Prefer, shares Prefer's register, and has a definition | 322 // Prefer, shares Prefer's register, and has a definition |
315 // within Cur's live range. | 323 // within Cur's live range. |
316 if (AllowOverlap && Item.Var != Prefer && RegNum == PreferReg && | 324 if (AllowOverlap && Item != Prefer && RegNum == PreferReg && |
317 overlapsDefs(Func, Cur, Item.Var)) { | 325 overlapsDefs(Func, Cur, Item)) { |
318 AllowOverlap = false; | 326 AllowOverlap = false; |
319 dumpDisableOverlap(Func, Item.Var, "Inactive"); | 327 dumpDisableOverlap(Func, Item, "Inactive"); |
320 } | 328 } |
321 } | 329 } |
322 } | 330 } |
323 | 331 |
324 // Disable AllowOverlap if an Active variable, which is not | 332 // Disable AllowOverlap if an Active variable, which is not |
325 // Prefer, shares Prefer's register, and has a definition within | 333 // Prefer, shares Prefer's register, and has a definition within |
326 // Cur's live range. | 334 // Cur's live range. |
327 for (const LiveRangeWrapper &Item : Active) { | 335 for (const Variable *Item : Active) { |
328 int32_t RegNum = Item.Var->getRegNumTmp(); | 336 int32_t RegNum = Item->getRegNumTmp(); |
329 if (Item.Var != Prefer && RegNum == PreferReg && | 337 if (Item != Prefer && RegNum == PreferReg && |
330 overlapsDefs(Func, Cur, Item.Var)) { | 338 overlapsDefs(Func, Cur, Item)) { |
331 AllowOverlap = false; | 339 AllowOverlap = false; |
332 dumpDisableOverlap(Func, Item.Var, "Active"); | 340 dumpDisableOverlap(Func, Item, "Active"); |
333 } | 341 } |
334 } | 342 } |
335 | 343 |
336 std::vector<RegWeight> Weights(RegMask.size()); | 344 std::vector<RegWeight> Weights(RegMask.size()); |
337 | 345 |
338 // Remove registers from the Free[] list where an Unhandled | 346 // Remove registers from the Free[] list where an Unhandled |
339 // precolored range overlaps with the current range, and set those | 347 // precolored range overlaps with the current range, and set those |
340 // registers to infinite weight so that they aren't candidates for | 348 // registers to infinite weight so that they aren't candidates for |
341 // eviction. Cur.endsBefore(Item) is an early exit check that | 349 // eviction. Cur->rangeEndsBefore(Item) is an early exit check |
342 // turns a guaranteed O(N^2) algorithm into expected linear | 350 // that turns a guaranteed O(N^2) algorithm into expected linear |
343 // complexity. | 351 // complexity. |
344 llvm::SmallBitVector PrecoloredUnhandledMask(RegMask.size()); | 352 llvm::SmallBitVector PrecoloredUnhandledMask(RegMask.size()); |
345 // Note: PrecoloredUnhandledMask is only used for dumping. | 353 // Note: PrecoloredUnhandledMask is only used for dumping. |
346 for (auto I = UnhandledPrecolored.rbegin(), E = UnhandledPrecolored.rend(); | 354 for (auto I = UnhandledPrecolored.rbegin(), E = UnhandledPrecolored.rend(); |
347 I != E; ++I) { | 355 I != E; ++I) { |
348 LiveRangeWrapper &Item = *I; | 356 Variable *Item = *I; |
349 assert(Item.Var->hasReg()); | 357 assert(Item->hasReg()); |
350 if (Cur.endsBefore(Item)) | 358 if (Cur->rangeEndsBefore(Item)) |
351 break; | 359 break; |
352 if (Item.overlaps(Cur)) { | 360 if (Item->rangeOverlaps(Cur)) { |
353 int32_t ItemReg = Item.Var->getRegNum(); // Note: not getRegNumTmp() | 361 int32_t ItemReg = Item->getRegNum(); // Note: not getRegNumTmp() |
354 Weights[ItemReg].setWeight(RegWeight::Inf); | 362 Weights[ItemReg].setWeight(RegWeight::Inf); |
355 Free[ItemReg] = false; | 363 Free[ItemReg] = false; |
356 PrecoloredUnhandledMask[ItemReg] = true; | 364 PrecoloredUnhandledMask[ItemReg] = true; |
357 // Disable AllowOverlap if the preferred register is one of | 365 // Disable AllowOverlap if the preferred register is one of |
358 // these precolored unhandled overlapping ranges. | 366 // these precolored unhandled overlapping ranges. |
359 if (AllowOverlap && ItemReg == PreferReg) { | 367 if (AllowOverlap && ItemReg == PreferReg) { |
360 AllowOverlap = false; | 368 AllowOverlap = false; |
361 dumpDisableOverlap(Func, Item.Var, "PrecoloredUnhandled"); | 369 dumpDisableOverlap(Func, Item, "PrecoloredUnhandled"); |
362 } | 370 } |
363 } | 371 } |
364 } | 372 } |
365 | 373 |
366 // Print info about physical register availability. | 374 // Print info about physical register availability. |
367 if (Verbose) { | 375 if (Verbose) { |
368 for (SizeT i = 0; i < RegMask.size(); ++i) { | 376 for (SizeT i = 0; i < RegMask.size(); ++i) { |
369 if (RegMask[i]) { | 377 if (RegMask[i]) { |
370 Str << Func->getTarget()->getRegName(i, IceType_i32) | 378 Str << Func->getTarget()->getRegName(i, IceType_i32) |
371 << "(U=" << RegUses[i] << ",F=" << Free[i] | 379 << "(U=" << RegUses[i] << ",F=" << Free[i] |
372 << ",P=" << PrecoloredUnhandledMask[i] << ") "; | 380 << ",P=" << PrecoloredUnhandledMask[i] << ") "; |
373 } | 381 } |
374 } | 382 } |
375 Str << "\n"; | 383 Str << "\n"; |
376 } | 384 } |
377 | 385 |
378 if (Prefer && (AllowOverlap || Free[PreferReg])) { | 386 if (Prefer && (AllowOverlap || Free[PreferReg])) { |
379 // First choice: a preferred register that is either free or is | 387 // First choice: a preferred register that is either free or is |
380 // allowed to overlap with its linked variable. | 388 // allowed to overlap with its linked variable. |
381 Cur.Var->setRegNumTmp(PreferReg); | 389 Cur->setRegNumTmp(PreferReg); |
382 if (Verbose) { | 390 if (Verbose) { |
383 Str << "Preferring "; | 391 Str << "Preferring "; |
384 Cur.dump(Func); | 392 dumpLiveRange(Cur, Func); |
385 Str << "\n"; | 393 Str << "\n"; |
386 } | 394 } |
387 assert(RegUses[PreferReg] >= 0); | 395 assert(RegUses[PreferReg] >= 0); |
388 ++RegUses[PreferReg]; | 396 ++RegUses[PreferReg]; |
389 Active.push_back(Cur); | 397 Active.push_back(Cur); |
390 } else if (Free.any()) { | 398 } else if (Free.any()) { |
391 // Second choice: any free register. TODO: After explicit | 399 // Second choice: any free register. TODO: After explicit |
392 // affinity is considered, is there a strategy better than just | 400 // affinity is considered, is there a strategy better than just |
393 // picking the lowest-numbered available register? | 401 // picking the lowest-numbered available register? |
394 int32_t RegNum = Free.find_first(); | 402 int32_t RegNum = Free.find_first(); |
395 Cur.Var->setRegNumTmp(RegNum); | 403 Cur->setRegNumTmp(RegNum); |
396 if (Verbose) { | 404 if (Verbose) { |
397 Str << "Allocating "; | 405 Str << "Allocating "; |
398 Cur.dump(Func); | 406 dumpLiveRange(Cur, Func); |
399 Str << "\n"; | 407 Str << "\n"; |
400 } | 408 } |
401 assert(RegUses[RegNum] >= 0); | 409 assert(RegUses[RegNum] >= 0); |
402 ++RegUses[RegNum]; | 410 ++RegUses[RegNum]; |
403 Active.push_back(Cur); | 411 Active.push_back(Cur); |
404 } else { | 412 } else { |
405 // Fallback: there are no free registers, so we look for the | 413 // Fallback: there are no free registers, so we look for the |
406 // lowest-weight register and see if Cur has higher weight. | 414 // lowest-weight register and see if Cur has higher weight. |
407 // Check Active ranges. | 415 // Check Active ranges. |
408 for (const LiveRangeWrapper &Item : Active) { | 416 for (const Variable *Item : Active) { |
409 assert(Item.overlaps(Cur)); | 417 assert(Item->rangeOverlaps(Cur)); |
410 int32_t RegNum = Item.Var->getRegNumTmp(); | 418 int32_t RegNum = Item->getRegNumTmp(); |
411 assert(Item.Var->hasRegTmp()); | 419 assert(Item->hasRegTmp()); |
412 Weights[RegNum].addWeight(Item.range().getWeight()); | 420 Weights[RegNum].addWeight(Item->getLiveRange().getWeight()); |
413 } | 421 } |
414 // Same as above, but check Inactive ranges instead of Active. | 422 // Same as above, but check Inactive ranges instead of Active. |
415 for (const LiveRangeWrapper &Item : Inactive) { | 423 for (const Variable *Item : Inactive) { |
416 int32_t RegNum = Item.Var->getRegNumTmp(); | 424 int32_t RegNum = Item->getRegNumTmp(); |
417 assert(Item.Var->hasRegTmp()); | 425 assert(Item->hasRegTmp()); |
418 if (Item.overlaps(Cur)) | 426 if (Item->rangeOverlaps(Cur)) |
419 Weights[RegNum].addWeight(Item.range().getWeight()); | 427 Weights[RegNum].addWeight(Item->getLiveRange().getWeight()); |
420 } | 428 } |
421 | 429 |
422 // All the weights are now calculated. Find the register with | 430 // All the weights are now calculated. Find the register with |
423 // smallest weight. | 431 // smallest weight. |
424 int32_t MinWeightIndex = RegMask.find_first(); | 432 int32_t MinWeightIndex = RegMask.find_first(); |
425 // MinWeightIndex must be valid because of the initial | 433 // MinWeightIndex must be valid because of the initial |
426 // RegMask.any() test. | 434 // RegMask.any() test. |
427 assert(MinWeightIndex >= 0); | 435 assert(MinWeightIndex >= 0); |
428 for (SizeT i = MinWeightIndex + 1; i < Weights.size(); ++i) { | 436 for (SizeT i = MinWeightIndex + 1; i < Weights.size(); ++i) { |
429 if (RegMask[i] && Weights[i] < Weights[MinWeightIndex]) | 437 if (RegMask[i] && Weights[i] < Weights[MinWeightIndex]) |
430 MinWeightIndex = i; | 438 MinWeightIndex = i; |
431 } | 439 } |
432 | 440 |
433 if (Cur.range().getWeight() <= Weights[MinWeightIndex]) { | 441 if (Cur->getLiveRange().getWeight() <= Weights[MinWeightIndex]) { |
434 // Cur doesn't have priority over any other live ranges, so | 442 // Cur doesn't have priority over any other live ranges, so |
435 // don't allocate any register to it, and move it to the | 443 // don't allocate any register to it, and move it to the |
436 // Handled state. | 444 // Handled state. |
437 Handled.push_back(Cur); | 445 Handled.push_back(Cur); |
438 if (Cur.range().getWeight().isInf()) { | 446 if (Cur->getLiveRange().getWeight().isInf()) { |
439 Func->setError("Unable to find a physical register for an " | 447 Func->setError("Unable to find a physical register for an " |
440 "infinite-weight live range"); | 448 "infinite-weight live range"); |
441 } | 449 } |
442 } else { | 450 } else { |
443 // Evict all live ranges in Active that register number | 451 // Evict all live ranges in Active that register number |
444 // MinWeightIndex is assigned to. | 452 // MinWeightIndex is assigned to. |
445 for (auto I = Active.begin(), E = Active.end(); I != E; I = Next) { | 453 for (auto I = Active.begin(), E = Active.end(); I != E; I = Next) { |
446 Next = I; | 454 Next = I; |
447 ++Next; | 455 ++Next; |
448 LiveRangeWrapper Item = *I; | 456 Variable *Item = *I; |
449 if (Item.Var->getRegNumTmp() == MinWeightIndex) { | 457 if (Item->getRegNumTmp() == MinWeightIndex) { |
450 if (Verbose) { | 458 if (Verbose) { |
451 Str << "Evicting "; | 459 Str << "Evicting "; |
452 Item.dump(Func); | 460 dumpLiveRange(Item, Func); |
453 Str << "\n"; | 461 Str << "\n"; |
454 } | 462 } |
455 --RegUses[MinWeightIndex]; | 463 --RegUses[MinWeightIndex]; |
456 assert(RegUses[MinWeightIndex] >= 0); | 464 assert(RegUses[MinWeightIndex] >= 0); |
457 Item.Var->setRegNumTmp(Variable::NoRegister); | 465 Item->setRegNumTmp(Variable::NoRegister); |
458 Handled.splice(Handled.end(), Active, I); | 466 Handled.splice(Handled.end(), Active, I); |
459 } | 467 } |
460 } | 468 } |
461 // Do the same for Inactive. | 469 // Do the same for Inactive. |
462 for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) { | 470 for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) { |
463 Next = I; | 471 Next = I; |
464 ++Next; | 472 ++Next; |
465 LiveRangeWrapper Item = *I; | 473 Variable *Item = *I; |
466 // Note: The Item.overlaps(Cur) clause is not part of the | 474 // Note: The Item->rangeOverlaps(Cur) clause is not part of the |
467 // description of AssignMemLoc() in the original paper. But | 475 // description of AssignMemLoc() in the original paper. But |
468 // there doesn't seem to be any need to evict an inactive | 476 // there doesn't seem to be any need to evict an inactive |
469 // live range that doesn't overlap with the live range | 477 // live range that doesn't overlap with the live range |
470 // currently being considered. It's especially bad if we | 478 // currently being considered. It's especially bad if we |
471 // would end up evicting an infinite-weight but | 479 // would end up evicting an infinite-weight but |
472 // currently-inactive live range. The most common situation | 480 // currently-inactive live range. The most common situation |
473 // for this would be a scratch register kill set for call | 481 // for this would be a scratch register kill set for call |
474 // instructions. | 482 // instructions. |
475 if (Item.Var->getRegNumTmp() == MinWeightIndex && | 483 if (Item->getRegNumTmp() == MinWeightIndex && |
476 Item.overlaps(Cur)) { | 484 Item->rangeOverlaps(Cur)) { |
477 if (Verbose) { | 485 if (Verbose) { |
478 Str << "Evicting "; | 486 Str << "Evicting "; |
479 Item.dump(Func); | 487 dumpLiveRange(Item, Func); |
480 Str << "\n"; | 488 Str << "\n"; |
481 } | 489 } |
482 Item.Var->setRegNumTmp(Variable::NoRegister); | 490 Item->setRegNumTmp(Variable::NoRegister); |
483 Handled.splice(Handled.end(), Inactive, I); | 491 Handled.splice(Handled.end(), Inactive, I); |
484 } | 492 } |
485 } | 493 } |
486 // Assign the register to Cur. | 494 // Assign the register to Cur. |
487 Cur.Var->setRegNumTmp(MinWeightIndex); | 495 Cur->setRegNumTmp(MinWeightIndex); |
488 assert(RegUses[MinWeightIndex] >= 0); | 496 assert(RegUses[MinWeightIndex] >= 0); |
489 ++RegUses[MinWeightIndex]; | 497 ++RegUses[MinWeightIndex]; |
490 Active.push_back(Cur); | 498 Active.push_back(Cur); |
491 if (Verbose) { | 499 if (Verbose) { |
492 Str << "Allocating "; | 500 Str << "Allocating "; |
493 Cur.dump(Func); | 501 dumpLiveRange(Cur, Func); |
494 Str << "\n"; | 502 Str << "\n"; |
495 } | 503 } |
496 } | 504 } |
497 } | 505 } |
498 dump(Func); | 506 dump(Func); |
499 } | 507 } |
500 // Move anything Active or Inactive to Handled for easier handling. | 508 // Move anything Active or Inactive to Handled for easier handling. |
501 for (const LiveRangeWrapper &I : Active) | 509 for (Variable *I : Active) |
502 Handled.push_back(I); | 510 Handled.push_back(I); |
503 Active.clear(); | 511 Active.clear(); |
504 for (const LiveRangeWrapper &I : Inactive) | 512 for (Variable *I : Inactive) |
505 Handled.push_back(I); | 513 Handled.push_back(I); |
506 Inactive.clear(); | 514 Inactive.clear(); |
507 dump(Func); | 515 dump(Func); |
508 | 516 |
509 // Finish up by assigning RegNumTmp->RegNum for each Variable. | 517 // Finish up by assigning RegNumTmp->RegNum for each Variable. |
510 for (const LiveRangeWrapper &Item : Handled) { | 518 for (Variable *Item : Handled) { |
511 int32_t RegNum = Item.Var->getRegNumTmp(); | 519 int32_t RegNum = Item->getRegNumTmp(); |
512 if (Verbose) { | 520 if (Verbose) { |
513 if (!Item.Var->hasRegTmp()) { | 521 if (!Item->hasRegTmp()) { |
514 Str << "Not assigning "; | 522 Str << "Not assigning "; |
515 Item.Var->dump(Func); | 523 Item->dump(Func); |
516 Str << "\n"; | 524 Str << "\n"; |
517 } else { | 525 } else { |
518 Str << (RegNum == Item.Var->getRegNum() ? "Reassigning " : "Assigning ") | 526 Str << (RegNum == Item->getRegNum() ? "Reassigning " : "Assigning ") |
519 << Func->getTarget()->getRegName(RegNum, IceType_i32) << "(r" | 527 << Func->getTarget()->getRegName(RegNum, IceType_i32) << "(r" |
520 << RegNum << ") to "; | 528 << RegNum << ") to "; |
521 Item.Var->dump(Func); | 529 Item->dump(Func); |
522 Str << "\n"; | 530 Str << "\n"; |
523 } | 531 } |
524 } | 532 } |
525 Item.Var->setRegNum(Item.Var->getRegNumTmp()); | 533 Item->setRegNum(Item->getRegNumTmp()); |
526 } | 534 } |
527 | 535 |
528 // TODO: Consider running register allocation one more time, with | 536 // TODO: Consider running register allocation one more time, with |
529 // infinite registers, for two reasons. First, evicted live ranges | 537 // infinite registers, for two reasons. First, evicted live ranges |
530 // get a second chance for a register. Second, it allows coalescing | 538 // get a second chance for a register. Second, it allows coalescing |
531 // of stack slots. If there is no time budget for the second | 539 // of stack slots. If there is no time budget for the second |
532 // register allocation run, each unallocated variable just gets its | 540 // register allocation run, each unallocated variable just gets its |
533 // own slot. | 541 // own slot. |
534 // | 542 // |
535 // Another idea for coalescing stack slots is to initialize the | 543 // Another idea for coalescing stack slots is to initialize the |
536 // Unhandled list with just the unallocated variables, saving time | 544 // Unhandled list with just the unallocated variables, saving time |
537 // but not offering second-chance opportunities. | 545 // but not offering second-chance opportunities. |
538 } | 546 } |
539 | 547 |
540 // ======================== Dump routines ======================== // | 548 // ======================== Dump routines ======================== // |
541 | 549 |
542 void LiveRangeWrapper::dump(const Cfg *Func) const { | |
543 Ostream &Str = Func->getContext()->getStrDump(); | |
544 const static size_t BufLen = 30; | |
545 char buf[BufLen]; | |
546 snprintf(buf, BufLen, "%2d", Var->getRegNumTmp()); | |
547 Str << "R=" << buf << " V="; | |
548 Var->dump(Func); | |
549 Str << " Range=" << range(); | |
550 } | |
551 | |
552 void LinearScan::dump(Cfg *Func) const { | 550 void LinearScan::dump(Cfg *Func) const { |
553 Ostream &Str = Func->getContext()->getStrDump(); | 551 Ostream &Str = Func->getContext()->getStrDump(); |
554 if (!Func->getContext()->isVerbose(IceV_LinearScan)) | 552 if (!Func->getContext()->isVerbose(IceV_LinearScan)) |
555 return; | 553 return; |
556 Func->resetCurrentNode(); | 554 Func->resetCurrentNode(); |
557 Str << "**** Current regalloc state:\n"; | 555 Str << "**** Current regalloc state:\n"; |
558 Str << "++++++ Handled:\n"; | 556 Str << "++++++ Handled:\n"; |
559 for (const LiveRangeWrapper &Item : Handled) { | 557 for (const Variable *Item : Handled) { |
560 Item.dump(Func); | 558 dumpLiveRange(Item, Func); |
561 Str << "\n"; | 559 Str << "\n"; |
562 } | 560 } |
563 Str << "++++++ Unhandled:\n"; | 561 Str << "++++++ Unhandled:\n"; |
564 for (auto I = Unhandled.rbegin(), E = Unhandled.rend(); I != E; ++I) { | 562 for (auto I = Unhandled.rbegin(), E = Unhandled.rend(); I != E; ++I) { |
565 I->dump(Func); | 563 dumpLiveRange(*I, Func); |
566 Str << "\n"; | 564 Str << "\n"; |
567 } | 565 } |
568 Str << "++++++ Active:\n"; | 566 Str << "++++++ Active:\n"; |
569 for (const LiveRangeWrapper &Item : Active) { | 567 for (const Variable *Item : Active) { |
570 Item.dump(Func); | 568 dumpLiveRange(Item, Func); |
571 Str << "\n"; | 569 Str << "\n"; |
572 } | 570 } |
573 Str << "++++++ Inactive:\n"; | 571 Str << "++++++ Inactive:\n"; |
574 for (const LiveRangeWrapper &Item : Inactive) { | 572 for (const Variable *Item : Inactive) { |
575 Item.dump(Func); | 573 dumpLiveRange(Item, Func); |
576 Str << "\n"; | 574 Str << "\n"; |
577 } | 575 } |
578 } | 576 } |
579 | 577 |
580 } // end of namespace Ice | 578 } // end of namespace Ice |
OLD | NEW |