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 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
51 const InstDefList &Defs = VMetadata->getDefinitions(Var); | 51 const InstDefList &Defs = VMetadata->getDefinitions(Var); |
52 for (size_t i = 0; i < Defs.size(); ++i) { | 52 for (size_t i = 0; i < Defs.size(); ++i) { |
53 if (i > 0) | 53 if (i > 0) |
54 Str << ","; | 54 Str << ","; |
55 Str << Defs[i]->getNumber(); | 55 Str << Defs[i]->getNumber(); |
56 } | 56 } |
57 Str << "\n"; | 57 Str << "\n"; |
58 } | 58 } |
59 } | 59 } |
60 | 60 |
| 61 bool compareRanges(const LiveRangeWrapper &L, const LiveRangeWrapper &R) { |
| 62 InstNumberT Lstart = L.Var->getLiveRange().getStart(); |
| 63 InstNumberT Rstart = R.Var->getLiveRange().getStart(); |
| 64 if (Lstart == Rstart) |
| 65 return L.Var->getIndex() < R.Var->getIndex(); |
| 66 return Lstart < Rstart; |
| 67 } |
| 68 |
61 } // end of anonymous namespace | 69 } // end of anonymous namespace |
62 | 70 |
63 // Implements the linear-scan algorithm. Based on "Linear Scan | 71 // Implements the linear-scan algorithm. Based on "Linear Scan |
64 // Register Allocation in the Context of SSA Form and Register | 72 // Register Allocation in the Context of SSA Form and Register |
65 // Constraints" by Hanspeter Mössenböck and Michael Pfeiffer, | 73 // Constraints" by Hanspeter Mössenböck and Michael Pfeiffer, |
66 // ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF . This | 74 // ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF . This |
67 // implementation is modified to take affinity into account and allow | 75 // implementation is modified to take affinity into account and allow |
68 // two interfering variables to share the same register in certain | 76 // two interfering variables to share the same register in certain |
69 // cases. | 77 // cases. |
70 // | 78 // |
71 // Requires running Cfg::liveness(Liveness_Intervals) in | 79 // Requires running Cfg::liveness(Liveness_Intervals) in |
72 // preparation. Results are assigned to Variable::RegNum for each | 80 // preparation. Results are assigned to Variable::RegNum for each |
73 // Variable. | 81 // Variable. |
74 void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) { | 82 void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) { |
75 TimerMarker T(TimerStack::TT_linearScan, Func); | 83 TimerMarker T(TimerStack::TT_linearScan, Func); |
76 assert(RegMaskFull.any()); // Sanity check | 84 assert(RegMaskFull.any()); // Sanity check |
77 Unhandled.clear(); | 85 Unhandled.clear(); |
78 UnhandledPrecolored.clear(); | 86 UnhandledPrecolored.clear(); |
79 Handled.clear(); | 87 Handled.clear(); |
80 Inactive.clear(); | 88 Inactive.clear(); |
81 Active.clear(); | 89 Active.clear(); |
82 Ostream &Str = Func->getContext()->getStrDump(); | 90 Ostream &Str = Func->getContext()->getStrDump(); |
83 bool Verbose = Func->getContext()->isVerbose(IceV_LinearScan); | 91 bool Verbose = Func->getContext()->isVerbose(IceV_LinearScan); |
84 Func->resetCurrentNode(); | 92 Func->resetCurrentNode(); |
85 VariablesMetadata *VMetadata = Func->getVMetadata(); | 93 VariablesMetadata *VMetadata = Func->getVMetadata(); |
86 | 94 |
87 // Gather the live ranges of all variables and add them to the | 95 // Gather the live ranges of all variables and add them to the |
88 // Unhandled set. TODO: Unhandled is a set<> which is based on a | 96 // Unhandled set. |
89 // balanced binary tree, so inserting live ranges for N variables is | |
90 // O(N log N) complexity. N may be proportional to the number of | |
91 // instructions, thanks to temporary generation during lowering. As | |
92 // a result, it may be useful to design a better data structure for | |
93 // storing Func->getVariables(). | |
94 const VarList &Vars = Func->getVariables(); | 97 const VarList &Vars = Func->getVariables(); |
95 { | 98 { |
96 TimerMarker T(TimerStack::TT_initUnhandled, Func); | 99 TimerMarker T(TimerStack::TT_initUnhandled, Func); |
| 100 Unhandled.reserve(Vars.size()); |
97 for (Variable *Var : Vars) { | 101 for (Variable *Var : Vars) { |
98 // Explicitly don't consider zero-weight variables, which are | 102 // Explicitly don't consider zero-weight variables, which are |
99 // meant to be spill slots. | 103 // meant to be spill slots. |
100 if (Var->getWeight() == RegWeight::Zero) | 104 if (Var->getWeight() == RegWeight::Zero) |
101 continue; | 105 continue; |
102 // Don't bother if the variable has a null live range, which means | 106 // Don't bother if the variable has a null live range, which means |
103 // it was never referenced. | 107 // it was never referenced. |
104 if (Var->getLiveRange().isEmpty()) | 108 if (Var->getLiveRange().isEmpty()) |
105 continue; | 109 continue; |
106 Var->untrimLiveRange(); | 110 Var->untrimLiveRange(); |
107 LiveRangeWrapper R(Var); | 111 LiveRangeWrapper R(Var); |
108 Unhandled.insert(R); | 112 Unhandled.push_back(R); |
109 if (Var->hasReg()) { | 113 if (Var->hasReg()) { |
110 Var->setRegNumTmp(Var->getRegNum()); | 114 Var->setRegNumTmp(Var->getRegNum()); |
111 Var->setLiveRangeInfiniteWeight(); | 115 Var->setLiveRangeInfiniteWeight(); |
112 UnhandledPrecolored.insert(R); | 116 UnhandledPrecolored.push_back(R); |
113 } | 117 } |
114 } | 118 } |
| 119 // Do a reverse sort so that erasing elements (from the end) is fast. |
| 120 std::sort(Unhandled.rbegin(), Unhandled.rend(), compareRanges); |
| 121 std::sort(UnhandledPrecolored.rbegin(), UnhandledPrecolored.rend(), |
| 122 compareRanges); |
115 } | 123 } |
116 | 124 |
117 // RegUses[I] is the number of live ranges (variables) that register | 125 // RegUses[I] is the number of live ranges (variables) that register |
118 // I is currently assigned to. It can be greater than 1 as a result | 126 // I is currently assigned to. It can be greater than 1 as a result |
119 // of AllowOverlap inference below. | 127 // of AllowOverlap inference below. |
120 std::vector<int> RegUses(RegMaskFull.size()); | 128 std::vector<int> RegUses(RegMaskFull.size()); |
121 // Unhandled is already set to all ranges in increasing order of | 129 // Unhandled is already set to all ranges in increasing order of |
122 // start points. | 130 // start points. |
123 assert(Active.empty()); | 131 assert(Active.empty()); |
124 assert(Inactive.empty()); | 132 assert(Inactive.empty()); |
125 assert(Handled.empty()); | 133 assert(Handled.empty()); |
126 UnorderedRanges::iterator Next; | 134 UnorderedRanges::iterator Next; |
127 | 135 |
128 while (!Unhandled.empty()) { | 136 while (!Unhandled.empty()) { |
129 LiveRangeWrapper Cur = *Unhandled.begin(); | 137 LiveRangeWrapper Cur = Unhandled.back(); |
130 Unhandled.erase(Unhandled.begin()); | 138 Unhandled.pop_back(); |
131 if (Verbose) { | 139 if (Verbose) { |
132 Str << "\nConsidering "; | 140 Str << "\nConsidering "; |
133 Cur.dump(Func); | 141 Cur.dump(Func); |
134 Str << "\n"; | 142 Str << "\n"; |
135 } | 143 } |
136 const llvm::SmallBitVector RegMask = | 144 const llvm::SmallBitVector RegMask = |
137 RegMaskFull & | 145 RegMaskFull & |
138 Func->getTarget()->getRegisterSetForType(Cur.Var->getType()); | 146 Func->getTarget()->getRegisterSetForType(Cur.Var->getType()); |
139 | 147 |
140 // Check for precolored ranges. If Cur is precolored, it | 148 // Check for precolored ranges. If Cur is precolored, it |
141 // definitely gets that register. Previously processed live | 149 // definitely gets that register. Previously processed live |
142 // ranges would have avoided that register due to it being | 150 // ranges would have avoided that register due to it being |
143 // precolored. Future processed live ranges won't evict that | 151 // precolored. Future processed live ranges won't evict that |
144 // register because the live range has infinite weight. | 152 // register because the live range has infinite weight. |
145 if (Cur.Var->hasReg()) { | 153 if (Cur.Var->hasReg()) { |
146 int32_t RegNum = Cur.Var->getRegNum(); | 154 int32_t RegNum = Cur.Var->getRegNum(); |
147 // RegNumTmp should have already been set above. | 155 // RegNumTmp should have already been set above. |
148 assert(Cur.Var->getRegNumTmp() == RegNum); | 156 assert(Cur.Var->getRegNumTmp() == RegNum); |
149 if (Verbose) { | 157 if (Verbose) { |
150 Str << "Precoloring "; | 158 Str << "Precoloring "; |
151 Cur.dump(Func); | 159 Cur.dump(Func); |
152 Str << "\n"; | 160 Str << "\n"; |
153 } | 161 } |
154 Active.push_back(Cur); | 162 Active.push_back(Cur); |
155 assert(RegUses[RegNum] >= 0); | 163 assert(RegUses[RegNum] >= 0); |
156 ++RegUses[RegNum]; | 164 ++RegUses[RegNum]; |
157 assert(!UnhandledPrecolored.empty()); | 165 assert(!UnhandledPrecolored.empty()); |
158 assert(UnhandledPrecolored.begin()->Var == Cur.Var); | 166 assert(UnhandledPrecolored.back().Var == Cur.Var); |
159 UnhandledPrecolored.erase(UnhandledPrecolored.begin()); | 167 UnhandledPrecolored.pop_back(); |
160 continue; | 168 continue; |
161 } | 169 } |
162 | 170 |
163 // Check for active ranges that have expired or become inactive. | 171 // Check for active ranges that have expired or become inactive. |
164 for (auto I = Active.begin(), E = Active.end(); I != E; I = Next) { | 172 for (auto I = Active.begin(), E = Active.end(); I != E; I = Next) { |
165 Next = I; | 173 Next = I; |
166 ++Next; | 174 ++Next; |
167 LiveRangeWrapper Item = *I; | 175 LiveRangeWrapper Item = *I; |
168 Item.Var->trimLiveRange(Cur.range().getStart()); | 176 Item.Var->trimLiveRange(Cur.range().getStart()); |
169 bool Moved = false; | 177 bool Moved = false; |
170 if (Item.endsBefore(Cur)) { | 178 if (Item.endsBefore(Cur)) { |
171 // Move Item from Active to Handled list. | 179 // Move Item from Active to Handled list. |
172 if (Verbose) { | 180 if (Verbose) { |
173 Str << "Expiring "; | 181 Str << "Expiring "; |
174 Item.dump(Func); | 182 Item.dump(Func); |
175 Str << "\n"; | 183 Str << "\n"; |
176 } | 184 } |
177 Active.erase(I); | 185 Handled.splice(Handled.end(), Active, I); |
178 Handled.push_back(Item); | |
179 Moved = true; | 186 Moved = true; |
180 } else if (!Item.overlapsStart(Cur)) { | 187 } else if (!Item.overlapsStart(Cur)) { |
181 // Move Item from Active to Inactive list. | 188 // Move Item from Active to Inactive list. |
182 if (Verbose) { | 189 if (Verbose) { |
183 Str << "Inactivating "; | 190 Str << "Inactivating "; |
184 Item.dump(Func); | 191 Item.dump(Func); |
185 Str << "\n"; | 192 Str << "\n"; |
186 } | 193 } |
187 Active.erase(I); | 194 Inactive.splice(Inactive.end(), Active, I); |
188 Inactive.push_back(Item); | |
189 Moved = true; | 195 Moved = true; |
190 } | 196 } |
191 if (Moved) { | 197 if (Moved) { |
192 // Decrement Item from RegUses[]. | 198 // Decrement Item from RegUses[]. |
193 assert(Item.Var->hasRegTmp()); | 199 assert(Item.Var->hasRegTmp()); |
194 int32_t RegNum = Item.Var->getRegNumTmp(); | 200 int32_t RegNum = Item.Var->getRegNumTmp(); |
195 --RegUses[RegNum]; | 201 --RegUses[RegNum]; |
196 assert(RegUses[RegNum] >= 0); | 202 assert(RegUses[RegNum] >= 0); |
197 } | 203 } |
198 } | 204 } |
(...skipping 13 matching lines...) Expand all Loading... |
212 // beginning of the function. | 218 // beginning of the function. |
213 if (!Item.range().isNonpoints()) | 219 if (!Item.range().isNonpoints()) |
214 continue; | 220 continue; |
215 if (Item.endsBefore(Cur)) { | 221 if (Item.endsBefore(Cur)) { |
216 // Move Item from Inactive to Handled list. | 222 // Move Item from Inactive to Handled list. |
217 if (Verbose) { | 223 if (Verbose) { |
218 Str << "Expiring "; | 224 Str << "Expiring "; |
219 Item.dump(Func); | 225 Item.dump(Func); |
220 Str << "\n"; | 226 Str << "\n"; |
221 } | 227 } |
222 Inactive.erase(I); | 228 Handled.splice(Handled.end(), Inactive, I); |
223 Handled.push_back(Item); | |
224 } else if (Item.overlapsStart(Cur)) { | 229 } else if (Item.overlapsStart(Cur)) { |
225 // Move Item from Inactive to Active list. | 230 // Move Item from Inactive to Active list. |
226 if (Verbose) { | 231 if (Verbose) { |
227 Str << "Reactivating "; | 232 Str << "Reactivating "; |
228 Item.dump(Func); | 233 Item.dump(Func); |
229 Str << "\n"; | 234 Str << "\n"; |
230 } | 235 } |
231 Inactive.erase(I); | 236 Active.splice(Active.end(), Inactive, I); |
232 Active.push_back(Item); | |
233 // Increment Item in RegUses[]. | 237 // Increment Item in RegUses[]. |
234 assert(Item.Var->hasRegTmp()); | 238 assert(Item.Var->hasRegTmp()); |
235 int32_t RegNum = Item.Var->getRegNumTmp(); | 239 int32_t RegNum = Item.Var->getRegNumTmp(); |
236 assert(RegUses[RegNum] >= 0); | 240 assert(RegUses[RegNum] >= 0); |
237 ++RegUses[RegNum]; | 241 ++RegUses[RegNum]; |
238 } | 242 } |
239 } | 243 } |
240 | 244 |
241 // Calculate available registers into Free[]. | 245 // Calculate available registers into Free[]. |
242 llvm::SmallBitVector Free = RegMask; | 246 llvm::SmallBitVector Free = RegMask; |
(...skipping 89 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
332 std::vector<RegWeight> Weights(RegMask.size()); | 336 std::vector<RegWeight> Weights(RegMask.size()); |
333 | 337 |
334 // Remove registers from the Free[] list where an Unhandled | 338 // Remove registers from the Free[] list where an Unhandled |
335 // precolored range overlaps with the current range, and set those | 339 // precolored range overlaps with the current range, and set those |
336 // registers to infinite weight so that they aren't candidates for | 340 // registers to infinite weight so that they aren't candidates for |
337 // eviction. Cur.endsBefore(Item) is an early exit check that | 341 // eviction. Cur.endsBefore(Item) is an early exit check that |
338 // turns a guaranteed O(N^2) algorithm into expected linear | 342 // turns a guaranteed O(N^2) algorithm into expected linear |
339 // complexity. | 343 // complexity. |
340 llvm::SmallBitVector PrecoloredUnhandledMask(RegMask.size()); | 344 llvm::SmallBitVector PrecoloredUnhandledMask(RegMask.size()); |
341 // Note: PrecoloredUnhandledMask is only used for dumping. | 345 // Note: PrecoloredUnhandledMask is only used for dumping. |
342 for (const LiveRangeWrapper &Item : UnhandledPrecolored) { | 346 for (auto I = UnhandledPrecolored.rbegin(), E = UnhandledPrecolored.rend(); |
| 347 I != E; ++I) { |
| 348 LiveRangeWrapper &Item = *I; |
343 assert(Item.Var->hasReg()); | 349 assert(Item.Var->hasReg()); |
344 if (Cur.endsBefore(Item)) | 350 if (Cur.endsBefore(Item)) |
345 break; | 351 break; |
346 if (Item.overlaps(Cur)) { | 352 if (Item.overlaps(Cur)) { |
347 int32_t ItemReg = Item.Var->getRegNum(); // Note: not getRegNumTmp() | 353 int32_t ItemReg = Item.Var->getRegNum(); // Note: not getRegNumTmp() |
348 Weights[ItemReg].setWeight(RegWeight::Inf); | 354 Weights[ItemReg].setWeight(RegWeight::Inf); |
349 Free[ItemReg] = false; | 355 Free[ItemReg] = false; |
350 PrecoloredUnhandledMask[ItemReg] = true; | 356 PrecoloredUnhandledMask[ItemReg] = true; |
351 // Disable AllowOverlap if the preferred register is one of | 357 // Disable AllowOverlap if the preferred register is one of |
352 // these precolored unhandled overlapping ranges. | 358 // these precolored unhandled overlapping ranges. |
(...skipping 89 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
442 LiveRangeWrapper Item = *I; | 448 LiveRangeWrapper Item = *I; |
443 if (Item.Var->getRegNumTmp() == MinWeightIndex) { | 449 if (Item.Var->getRegNumTmp() == MinWeightIndex) { |
444 if (Verbose) { | 450 if (Verbose) { |
445 Str << "Evicting "; | 451 Str << "Evicting "; |
446 Item.dump(Func); | 452 Item.dump(Func); |
447 Str << "\n"; | 453 Str << "\n"; |
448 } | 454 } |
449 --RegUses[MinWeightIndex]; | 455 --RegUses[MinWeightIndex]; |
450 assert(RegUses[MinWeightIndex] >= 0); | 456 assert(RegUses[MinWeightIndex] >= 0); |
451 Item.Var->setRegNumTmp(Variable::NoRegister); | 457 Item.Var->setRegNumTmp(Variable::NoRegister); |
452 Active.erase(I); | 458 Handled.splice(Handled.end(), Active, I); |
453 Handled.push_back(Item); | |
454 } | 459 } |
455 } | 460 } |
456 // Do the same for Inactive. | 461 // Do the same for Inactive. |
457 for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) { | 462 for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) { |
458 Next = I; | 463 Next = I; |
459 ++Next; | 464 ++Next; |
460 LiveRangeWrapper Item = *I; | 465 LiveRangeWrapper Item = *I; |
461 // Note: The Item.overlaps(Cur) clause is not part of the | 466 // Note: The Item.overlaps(Cur) clause is not part of the |
462 // description of AssignMemLoc() in the original paper. But | 467 // description of AssignMemLoc() in the original paper. But |
463 // there doesn't seem to be any need to evict an inactive | 468 // there doesn't seem to be any need to evict an inactive |
464 // live range that doesn't overlap with the live range | 469 // live range that doesn't overlap with the live range |
465 // currently being considered. It's especially bad if we | 470 // currently being considered. It's especially bad if we |
466 // would end up evicting an infinite-weight but | 471 // would end up evicting an infinite-weight but |
467 // currently-inactive live range. The most common situation | 472 // currently-inactive live range. The most common situation |
468 // for this would be a scratch register kill set for call | 473 // for this would be a scratch register kill set for call |
469 // instructions. | 474 // instructions. |
470 if (Item.Var->getRegNumTmp() == MinWeightIndex && | 475 if (Item.Var->getRegNumTmp() == MinWeightIndex && |
471 Item.overlaps(Cur)) { | 476 Item.overlaps(Cur)) { |
472 if (Verbose) { | 477 if (Verbose) { |
473 Str << "Evicting "; | 478 Str << "Evicting "; |
474 Item.dump(Func); | 479 Item.dump(Func); |
475 Str << "\n"; | 480 Str << "\n"; |
476 } | 481 } |
477 Item.Var->setRegNumTmp(Variable::NoRegister); | 482 Item.Var->setRegNumTmp(Variable::NoRegister); |
478 Inactive.erase(I); | 483 Handled.splice(Handled.end(), Inactive, I); |
479 Handled.push_back(Item); | |
480 } | 484 } |
481 } | 485 } |
482 // Assign the register to Cur. | 486 // Assign the register to Cur. |
483 Cur.Var->setRegNumTmp(MinWeightIndex); | 487 Cur.Var->setRegNumTmp(MinWeightIndex); |
484 assert(RegUses[MinWeightIndex] >= 0); | 488 assert(RegUses[MinWeightIndex] >= 0); |
485 ++RegUses[MinWeightIndex]; | 489 ++RegUses[MinWeightIndex]; |
486 Active.push_back(Cur); | 490 Active.push_back(Cur); |
487 if (Verbose) { | 491 if (Verbose) { |
488 Str << "Allocating "; | 492 Str << "Allocating "; |
489 Cur.dump(Func); | 493 Cur.dump(Func); |
(...skipping 60 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
550 if (!Func->getContext()->isVerbose(IceV_LinearScan)) | 554 if (!Func->getContext()->isVerbose(IceV_LinearScan)) |
551 return; | 555 return; |
552 Func->resetCurrentNode(); | 556 Func->resetCurrentNode(); |
553 Str << "**** Current regalloc state:\n"; | 557 Str << "**** Current regalloc state:\n"; |
554 Str << "++++++ Handled:\n"; | 558 Str << "++++++ Handled:\n"; |
555 for (const LiveRangeWrapper &Item : Handled) { | 559 for (const LiveRangeWrapper &Item : Handled) { |
556 Item.dump(Func); | 560 Item.dump(Func); |
557 Str << "\n"; | 561 Str << "\n"; |
558 } | 562 } |
559 Str << "++++++ Unhandled:\n"; | 563 Str << "++++++ Unhandled:\n"; |
560 for (const LiveRangeWrapper &Item : Unhandled) { | 564 for (auto I = Unhandled.rbegin(), E = Unhandled.rend(); I != E; ++I) { |
561 Item.dump(Func); | 565 I->dump(Func); |
562 Str << "\n"; | 566 Str << "\n"; |
563 } | 567 } |
564 Str << "++++++ Active:\n"; | 568 Str << "++++++ Active:\n"; |
565 for (const LiveRangeWrapper &Item : Active) { | 569 for (const LiveRangeWrapper &Item : Active) { |
566 Item.dump(Func); | 570 Item.dump(Func); |
567 Str << "\n"; | 571 Str << "\n"; |
568 } | 572 } |
569 Str << "++++++ Inactive:\n"; | 573 Str << "++++++ Inactive:\n"; |
570 for (const LiveRangeWrapper &Item : Inactive) { | 574 for (const LiveRangeWrapper &Item : Inactive) { |
571 Item.dump(Func); | 575 Item.dump(Func); |
572 Str << "\n"; | 576 Str << "\n"; |
573 } | 577 } |
574 } | 578 } |
575 | 579 |
576 } // end of namespace Ice | 580 } // end of namespace Ice |
OLD | NEW |