OLD | NEW |
(Empty) | |
| 1 //===- subzero/src/IceRegAlloc.cpp - Linear-scan implementation -----------===// |
| 2 // |
| 3 // The Subzero Code Generator |
| 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 implements the LinearScan class, which performs the |
| 11 // linear-scan register allocation after liveness analysis has been |
| 12 // performed. |
| 13 // |
| 14 //===----------------------------------------------------------------------===// |
| 15 |
| 16 #include "IceCfg.h" |
| 17 #include "IceInst.h" |
| 18 #include "IceOperand.h" |
| 19 #include "IceRegAlloc.h" |
| 20 #include "IceTargetLowering.h" |
| 21 |
| 22 namespace Ice { |
| 23 |
| 24 // Implements the linear-scan algorithm. Based on "Linear Scan |
| 25 // Register Allocation in the Context of SSA Form and Register |
| 26 // Constraints" by Hanspeter Mössenböck and Michael Pfeiffer, |
| 27 // ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF . This |
| 28 // implementation is modified to take affinity into account and allow |
| 29 // two interfering variables to share the same register in certain |
| 30 // cases. |
| 31 // |
| 32 // Requires running Cfg::liveness(Liveness_RangesFull) in |
| 33 // preparation. Results are assigned to Variable::RegNum for each |
| 34 // Variable. |
| 35 void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) { |
| 36 assert(RegMaskFull.any()); // Sanity check |
| 37 Unhandled.clear(); |
| 38 Handled.clear(); |
| 39 Inactive.clear(); |
| 40 Active.clear(); |
| 41 Ostream &Str = Func->getContext()->getStrDump(); |
| 42 Func->setCurrentNode(NULL); |
| 43 |
| 44 // Gather the live ranges of all variables and add them to the |
| 45 // Unhandled set. TODO: Unhandled is a set<> which is based on a |
| 46 // balanced binary tree, so inserting live ranges for N variables is |
| 47 // O(N log N) complexity. N may be proportional to the number of |
| 48 // instructions, thanks to temporary generation during lowering. As |
| 49 // a result, it may be useful to design a better data structure for |
| 50 // storing Func->getVariables(). |
| 51 const VarList &Vars = Func->getVariables(); |
| 52 for (VarList::const_iterator I = Vars.begin(), E = Vars.end(); I != E; ++I) { |
| 53 Variable *Var = *I; |
| 54 // Explicitly don't consider zero-weight variables, which are |
| 55 // meant to be spill slots. |
| 56 if (Var->getWeight() == RegWeight::Zero) |
| 57 continue; |
| 58 // Don't bother if the variable has a null live range, which means |
| 59 // it was never referenced. |
| 60 if (Var->getLiveRange().isEmpty()) |
| 61 continue; |
| 62 Unhandled.insert(LiveRangeWrapper(Var)); |
| 63 if (Var->hasReg()) { |
| 64 Var->setRegNumTmp(Var->getRegNum()); |
| 65 Var->setLiveRangeInfiniteWeight(); |
| 66 } |
| 67 } |
| 68 |
| 69 // RegUses[I] is the number of live ranges (variables) that register |
| 70 // I is currently assigned to. It can be greater than 1 as a result |
| 71 // of Variable::AllowRegisterOverlap. |
| 72 std::vector<int> RegUses(RegMaskFull.size()); |
| 73 // Unhandled is already set to all ranges in increasing order of |
| 74 // start points. |
| 75 assert(Active.empty()); |
| 76 assert(Inactive.empty()); |
| 77 assert(Handled.empty()); |
| 78 UnorderedRanges::iterator Next; |
| 79 |
| 80 while (!Unhandled.empty()) { |
| 81 LiveRangeWrapper Cur = *Unhandled.begin(); |
| 82 Unhandled.erase(Unhandled.begin()); |
| 83 if (Func->getContext()->isVerbose(IceV_LinearScan)) { |
| 84 Str << "\nConsidering "; |
| 85 Cur.dump(Func); |
| 86 Str << "\n"; |
| 87 } |
| 88 const llvm::SmallBitVector RegMask = |
| 89 RegMaskFull & |
| 90 Func->getTarget()->getRegisterSetForType(Cur.Var->getType()); |
| 91 |
| 92 // Check for precolored ranges. If Cur is precolored, it |
| 93 // definitely gets that register. Previously processed live |
| 94 // ranges would have avoided that register due to it being |
| 95 // precolored. Future processed live ranges won't evict that |
| 96 // register because the live range has infinite weight. |
| 97 if (Cur.Var->hasReg()) { |
| 98 int32_t RegNum = Cur.Var->getRegNum(); |
| 99 // RegNumTmp should have already been set above. |
| 100 assert(Cur.Var->getRegNumTmp() == RegNum); |
| 101 if (Func->getContext()->isVerbose(IceV_LinearScan)) { |
| 102 Str << "Precoloring "; |
| 103 Cur.dump(Func); |
| 104 Str << "\n"; |
| 105 } |
| 106 Active.push_back(Cur); |
| 107 assert(RegUses[RegNum] >= 0); |
| 108 ++RegUses[RegNum]; |
| 109 continue; |
| 110 } |
| 111 |
| 112 // Check for active ranges that have expired or become inactive. |
| 113 for (UnorderedRanges::iterator I = Active.begin(), E = Active.end(); I != E; |
| 114 I = Next) { |
| 115 Next = I; |
| 116 ++Next; |
| 117 LiveRangeWrapper Item = *I; |
| 118 bool Moved = false; |
| 119 if (Item.endsBefore(Cur)) { |
| 120 // Move Item from Active to Handled list. |
| 121 if (Func->getContext()->isVerbose(IceV_LinearScan)) { |
| 122 Str << "Expiring "; |
| 123 Item.dump(Func); |
| 124 Str << "\n"; |
| 125 } |
| 126 Active.erase(I); |
| 127 Handled.push_back(Item); |
| 128 Moved = true; |
| 129 } else if (!Item.overlapsStart(Cur)) { |
| 130 // Move Item from Active to Inactive list. |
| 131 if (Func->getContext()->isVerbose(IceV_LinearScan)) { |
| 132 Str << "Inactivating "; |
| 133 Item.dump(Func); |
| 134 Str << "\n"; |
| 135 } |
| 136 Active.erase(I); |
| 137 Inactive.push_back(Item); |
| 138 Moved = true; |
| 139 } |
| 140 if (Moved) { |
| 141 // Decrement Item from RegUses[]. |
| 142 assert(Item.Var->hasRegTmp()); |
| 143 int32_t RegNum = Item.Var->getRegNumTmp(); |
| 144 --RegUses[RegNum]; |
| 145 assert(RegUses[RegNum] >= 0); |
| 146 } |
| 147 } |
| 148 |
| 149 // Check for inactive ranges that have expired or reactivated. |
| 150 for (UnorderedRanges::iterator I = Inactive.begin(), E = Inactive.end(); |
| 151 I != E; I = Next) { |
| 152 Next = I; |
| 153 ++Next; |
| 154 LiveRangeWrapper Item = *I; |
| 155 if (Item.endsBefore(Cur)) { |
| 156 // Move Item from Inactive to Handled list. |
| 157 if (Func->getContext()->isVerbose(IceV_LinearScan)) { |
| 158 Str << "Expiring "; |
| 159 Item.dump(Func); |
| 160 Str << "\n"; |
| 161 } |
| 162 Inactive.erase(I); |
| 163 Handled.push_back(Item); |
| 164 } else if (Item.overlapsStart(Cur)) { |
| 165 // Move Item from Inactive to Active list. |
| 166 if (Func->getContext()->isVerbose(IceV_LinearScan)) { |
| 167 Str << "Reactivating "; |
| 168 Item.dump(Func); |
| 169 Str << "\n"; |
| 170 } |
| 171 Inactive.erase(I); |
| 172 Active.push_back(Item); |
| 173 // Increment Item in RegUses[]. |
| 174 assert(Item.Var->hasRegTmp()); |
| 175 int32_t RegNum = Item.Var->getRegNumTmp(); |
| 176 assert(RegUses[RegNum] >= 0); |
| 177 ++RegUses[RegNum]; |
| 178 } |
| 179 } |
| 180 |
| 181 // Calculate available registers into Free[]. |
| 182 llvm::SmallBitVector Free = RegMask; |
| 183 for (SizeT i = 0; i < RegMask.size(); ++i) { |
| 184 if (RegUses[i] > 0) |
| 185 Free[i] = false; |
| 186 } |
| 187 |
| 188 // Remove registers from the Free[] list where an Inactive range |
| 189 // overlaps with the current range. |
| 190 for (UnorderedRanges::const_iterator I = Inactive.begin(), |
| 191 E = Inactive.end(); |
| 192 I != E; ++I) { |
| 193 LiveRangeWrapper Item = *I; |
| 194 if (Item.overlaps(Cur)) { |
| 195 int32_t RegNum = Item.Var->getRegNumTmp(); |
| 196 // Don't assert(Free[RegNum]) because in theory (though |
| 197 // probably never in practice) there could be two inactive |
| 198 // variables that were allowed marked with |
| 199 // AllowRegisterOverlap. |
| 200 Free[RegNum] = false; |
| 201 } |
| 202 } |
| 203 |
| 204 // Remove registers from the Free[] list where an Unhandled range |
| 205 // overlaps with the current range and is precolored. |
| 206 // Cur.endsBefore(*I) is an early exit check that turns a |
| 207 // guaranteed O(N^2) algorithm into expected linear complexity. |
| 208 for (OrderedRanges::const_iterator I = Unhandled.begin(), |
| 209 E = Unhandled.end(); |
| 210 I != E && !Cur.endsBefore(*I); ++I) { |
| 211 LiveRangeWrapper Item = *I; |
| 212 if (Item.Var->hasReg() && Item.overlaps(Cur)) { |
| 213 Free[Item.Var->getRegNum()] = false; // Note: getRegNum not getRegNumTmp |
| 214 } |
| 215 } |
| 216 |
| 217 // Print info about physical register availability. |
| 218 if (Func->getContext()->isVerbose(IceV_LinearScan)) { |
| 219 for (SizeT i = 0; i < RegMask.size(); ++i) { |
| 220 if (RegMask[i]) { |
| 221 Str << Func->getTarget()->getRegName(i, IceType_i32) |
| 222 << "(U=" << RegUses[i] << ",F=" << Free[i] << ") "; |
| 223 } |
| 224 } |
| 225 Str << "\n"; |
| 226 } |
| 227 |
| 228 Variable *Prefer = Cur.Var->getPreferredRegister(); |
| 229 int32_t PreferReg = Prefer && Prefer->hasRegTmp() ? Prefer->getRegNumTmp() |
| 230 : Variable::NoRegister; |
| 231 if (PreferReg != Variable::NoRegister && |
| 232 (Cur.Var->getRegisterOverlap() || Free[PreferReg])) { |
| 233 // First choice: a preferred register that is either free or is |
| 234 // allowed to overlap with its linked variable. |
| 235 Cur.Var->setRegNumTmp(PreferReg); |
| 236 if (Func->getContext()->isVerbose(IceV_LinearScan)) { |
| 237 Str << "Preferring "; |
| 238 Cur.dump(Func); |
| 239 Str << "\n"; |
| 240 } |
| 241 assert(RegUses[PreferReg] >= 0); |
| 242 ++RegUses[PreferReg]; |
| 243 Active.push_back(Cur); |
| 244 } else if (Free.any()) { |
| 245 // Second choice: any free register. TODO: After explicit |
| 246 // affinity is considered, is there a strategy better than just |
| 247 // picking the lowest-numbered available register? |
| 248 int32_t RegNum = Free.find_first(); |
| 249 Cur.Var->setRegNumTmp(RegNum); |
| 250 if (Func->getContext()->isVerbose(IceV_LinearScan)) { |
| 251 Str << "Allocating "; |
| 252 Cur.dump(Func); |
| 253 Str << "\n"; |
| 254 } |
| 255 assert(RegUses[RegNum] >= 0); |
| 256 ++RegUses[RegNum]; |
| 257 Active.push_back(Cur); |
| 258 } else { |
| 259 // Fallback: there are no free registers, so we look for the |
| 260 // lowest-weight register and see if Cur has higher weight. |
| 261 std::vector<RegWeight> Weights(RegMask.size()); |
| 262 // Check Active ranges. |
| 263 for (UnorderedRanges::const_iterator I = Active.begin(), E = Active.end(); |
| 264 I != E; ++I) { |
| 265 LiveRangeWrapper Item = *I; |
| 266 assert(Item.overlaps(Cur)); |
| 267 int32_t RegNum = Item.Var->getRegNumTmp(); |
| 268 assert(Item.Var->hasRegTmp()); |
| 269 Weights[RegNum].addWeight(Item.range().getWeight()); |
| 270 } |
| 271 // Same as above, but check Inactive ranges instead of Active. |
| 272 for (UnorderedRanges::const_iterator I = Inactive.begin(), |
| 273 E = Inactive.end(); |
| 274 I != E; ++I) { |
| 275 LiveRangeWrapper Item = *I; |
| 276 int32_t RegNum = Item.Var->getRegNumTmp(); |
| 277 assert(Item.Var->hasRegTmp()); |
| 278 if (Item.overlaps(Cur)) |
| 279 Weights[RegNum].addWeight(Item.range().getWeight()); |
| 280 } |
| 281 // Check Unhandled ranges that overlap Cur and are precolored. |
| 282 // Cur.endsBefore(*I) is an early exit check that turns a |
| 283 // guaranteed O(N^2) algorithm into expected linear complexity. |
| 284 for (OrderedRanges::const_iterator I = Unhandled.begin(), |
| 285 E = Unhandled.end(); |
| 286 I != E && !Cur.endsBefore(*I); ++I) { |
| 287 LiveRangeWrapper Item = *I; |
| 288 int32_t RegNum = Item.Var->getRegNumTmp(); |
| 289 if (RegNum < 0) |
| 290 continue; |
| 291 if (Item.overlaps(Cur)) |
| 292 Weights[RegNum].setWeight(RegWeight::Inf); |
| 293 } |
| 294 |
| 295 // All the weights are now calculated. Find the register with |
| 296 // smallest weight. |
| 297 int32_t MinWeightIndex = RegMask.find_first(); |
| 298 // MinWeightIndex must be valid because of the initial |
| 299 // RegMask.any() test. |
| 300 assert(MinWeightIndex >= 0); |
| 301 for (SizeT i = MinWeightIndex + 1; i < Weights.size(); ++i) { |
| 302 if (RegMask[i] && Weights[i] < Weights[MinWeightIndex]) |
| 303 MinWeightIndex = i; |
| 304 } |
| 305 |
| 306 if (Cur.range().getWeight() <= Weights[MinWeightIndex]) { |
| 307 // Cur doesn't have priority over any other live ranges, so |
| 308 // don't allocate any register to it, and move it to the |
| 309 // Handled state. |
| 310 Handled.push_back(Cur); |
| 311 if (Cur.range().getWeight().isInf()) { |
| 312 Func->setError("Unable to find a physical register for an " |
| 313 "infinite-weight live range"); |
| 314 } |
| 315 } else { |
| 316 // Evict all live ranges in Active that register number |
| 317 // MinWeightIndex is assigned to. |
| 318 for (UnorderedRanges::iterator I = Active.begin(), E = Active.end(); |
| 319 I != E; I = Next) { |
| 320 Next = I; |
| 321 ++Next; |
| 322 LiveRangeWrapper Item = *I; |
| 323 if (Item.Var->getRegNumTmp() == MinWeightIndex) { |
| 324 if (Func->getContext()->isVerbose(IceV_LinearScan)) { |
| 325 Str << "Evicting "; |
| 326 Item.dump(Func); |
| 327 Str << "\n"; |
| 328 } |
| 329 --RegUses[MinWeightIndex]; |
| 330 assert(RegUses[MinWeightIndex] >= 0); |
| 331 Item.Var->setRegNumTmp(Variable::NoRegister); |
| 332 Active.erase(I); |
| 333 Handled.push_back(Item); |
| 334 } |
| 335 } |
| 336 // Do the same for Inactive. |
| 337 for (UnorderedRanges::iterator I = Inactive.begin(), E = Inactive.end(); |
| 338 I != E; I = Next) { |
| 339 Next = I; |
| 340 ++Next; |
| 341 LiveRangeWrapper Item = *I; |
| 342 if (Item.Var->getRegNumTmp() == MinWeightIndex) { |
| 343 if (Func->getContext()->isVerbose(IceV_LinearScan)) { |
| 344 Str << "Evicting "; |
| 345 Item.dump(Func); |
| 346 Str << "\n"; |
| 347 } |
| 348 Item.Var->setRegNumTmp(Variable::NoRegister); |
| 349 Inactive.erase(I); |
| 350 Handled.push_back(Item); |
| 351 } |
| 352 } |
| 353 // Assign the register to Cur. |
| 354 Cur.Var->setRegNumTmp(MinWeightIndex); |
| 355 assert(RegUses[MinWeightIndex] >= 0); |
| 356 ++RegUses[MinWeightIndex]; |
| 357 Active.push_back(Cur); |
| 358 if (Func->getContext()->isVerbose(IceV_LinearScan)) { |
| 359 Str << "Allocating "; |
| 360 Cur.dump(Func); |
| 361 Str << "\n"; |
| 362 } |
| 363 } |
| 364 } |
| 365 dump(Func); |
| 366 } |
| 367 // Move anything Active or Inactive to Handled for easier handling. |
| 368 for (UnorderedRanges::iterator I = Active.begin(), E = Active.end(); I != E; |
| 369 I = Next) { |
| 370 Next = I; |
| 371 ++Next; |
| 372 Handled.push_back(*I); |
| 373 Active.erase(I); |
| 374 } |
| 375 for (UnorderedRanges::iterator I = Inactive.begin(), E = Inactive.end(); |
| 376 I != E; I = Next) { |
| 377 Next = I; |
| 378 ++Next; |
| 379 Handled.push_back(*I); |
| 380 Inactive.erase(I); |
| 381 } |
| 382 dump(Func); |
| 383 |
| 384 // Finish up by assigning RegNumTmp->RegNum for each Variable. |
| 385 for (UnorderedRanges::const_iterator I = Handled.begin(), E = Handled.end(); |
| 386 I != E; ++I) { |
| 387 LiveRangeWrapper Item = *I; |
| 388 int32_t RegNum = Item.Var->getRegNumTmp(); |
| 389 if (Func->getContext()->isVerbose(IceV_LinearScan)) { |
| 390 if (!Item.Var->hasRegTmp()) { |
| 391 Str << "Not assigning "; |
| 392 Item.Var->dump(Func); |
| 393 Str << "\n"; |
| 394 } else { |
| 395 Str << (RegNum == Item.Var->getRegNum() ? "Reassigning " : "Assigning ") |
| 396 << Func->getTarget()->getRegName(RegNum, IceType_i32) << "(r" |
| 397 << RegNum << ") to "; |
| 398 Item.Var->dump(Func); |
| 399 Str << "\n"; |
| 400 } |
| 401 } |
| 402 Item.Var->setRegNum(Item.Var->getRegNumTmp()); |
| 403 } |
| 404 |
| 405 // TODO: Consider running register allocation one more time, with |
| 406 // infinite registers, for two reasons. First, evicted live ranges |
| 407 // get a second chance for a register. Second, it allows coalescing |
| 408 // of stack slots. If there is no time budget for the second |
| 409 // register allocation run, each unallocated variable just gets its |
| 410 // own slot. |
| 411 // |
| 412 // Another idea for coalescing stack slots is to initialize the |
| 413 // Unhandled list with just the unallocated variables, saving time |
| 414 // but not offering second-chance opportunities. |
| 415 } |
| 416 |
| 417 // ======================== Dump routines ======================== // |
| 418 |
| 419 void LiveRangeWrapper::dump(const Cfg *Func) const { |
| 420 Ostream &Str = Func->getContext()->getStrDump(); |
| 421 const static size_t BufLen = 30; |
| 422 char buf[BufLen]; |
| 423 snprintf(buf, BufLen, "%2d", Var->getRegNumTmp()); |
| 424 Str << "R=" << buf << " V="; |
| 425 Var->dump(Func); |
| 426 Str << " Range=" << range(); |
| 427 } |
| 428 |
| 429 void LinearScan::dump(Cfg *Func) const { |
| 430 Ostream &Str = Func->getContext()->getStrDump(); |
| 431 if (!Func->getContext()->isVerbose(IceV_LinearScan)) |
| 432 return; |
| 433 Func->setCurrentNode(NULL); |
| 434 Str << "**** Current regalloc state:\n"; |
| 435 Str << "++++++ Handled:\n"; |
| 436 for (UnorderedRanges::const_iterator I = Handled.begin(), E = Handled.end(); |
| 437 I != E; ++I) { |
| 438 I->dump(Func); |
| 439 Str << "\n"; |
| 440 } |
| 441 Str << "++++++ Unhandled:\n"; |
| 442 for (OrderedRanges::const_iterator I = Unhandled.begin(), E = Unhandled.end(); |
| 443 I != E; ++I) { |
| 444 I->dump(Func); |
| 445 Str << "\n"; |
| 446 } |
| 447 Str << "++++++ Active:\n"; |
| 448 for (UnorderedRanges::const_iterator I = Active.begin(), E = Active.end(); |
| 449 I != E; ++I) { |
| 450 I->dump(Func); |
| 451 Str << "\n"; |
| 452 } |
| 453 Str << "++++++ Inactive:\n"; |
| 454 for (UnorderedRanges::const_iterator I = Inactive.begin(), E = Inactive.end(); |
| 455 I != E; ++I) { |
| 456 I->dump(Func); |
| 457 Str << "\n"; |
| 458 } |
| 459 } |
| 460 |
| 461 } // end of namespace Ice |
OLD | NEW |