IceRegAlloc.cpp revision 9612d32c7e5eb2cb403686ef31172d42e075e460
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/// \file 11/// This file implements the LinearScan class, which performs the 12/// linear-scan register allocation after liveness analysis has been 13/// performed. 14/// 15//===----------------------------------------------------------------------===// 16 17#include "IceRegAlloc.h" 18 19#include "IceCfg.h" 20#include "IceCfgNode.h" 21#include "IceInst.h" 22#include "IceOperand.h" 23#include "IceTargetLowering.h" 24 25namespace Ice { 26 27namespace { 28 29// TODO(stichnot): Statically choose the size based on the target 30// being compiled. 31constexpr size_t REGS_SIZE = 32; 32 33// Returns true if Var has any definitions within Item's live range. 34// TODO(stichnot): Consider trimming the Definitions list similar to 35// how the live ranges are trimmed, since all the overlapsDefs() tests 36// are whether some variable's definitions overlap Cur, and trimming 37// is with respect Cur.start. Initial tests show no measurable 38// performance difference, so we'll keep the code simple for now. 39bool overlapsDefs(const Cfg *Func, const Variable *Item, const Variable *Var) { 40 const bool UseTrimmed = true; 41 VariablesMetadata *VMetadata = Func->getVMetadata(); 42 if (const Inst *FirstDef = VMetadata->getFirstDefinition(Var)) 43 if (Item->getLiveRange().overlapsInst(FirstDef->getNumber(), UseTrimmed)) 44 return true; 45 const InstDefList &Defs = VMetadata->getLatterDefinitions(Var); 46 for (size_t i = 0; i < Defs.size(); ++i) { 47 if (Item->getLiveRange().overlapsInst(Defs[i]->getNumber(), UseTrimmed)) 48 return true; 49 } 50 return false; 51} 52 53void dumpDisableOverlap(const Cfg *Func, const Variable *Var, 54 const char *Reason) { 55 if (!BuildDefs::dump()) 56 return; 57 if (Func->isVerbose(IceV_LinearScan)) { 58 VariablesMetadata *VMetadata = Func->getVMetadata(); 59 Ostream &Str = Func->getContext()->getStrDump(); 60 Str << "Disabling Overlap due to " << Reason << " " << *Var 61 << " LIVE=" << Var->getLiveRange() << " Defs="; 62 if (const Inst *FirstDef = VMetadata->getFirstDefinition(Var)) 63 Str << FirstDef->getNumber(); 64 const InstDefList &Defs = VMetadata->getLatterDefinitions(Var); 65 for (size_t i = 0; i < Defs.size(); ++i) { 66 Str << "," << Defs[i]->getNumber(); 67 } 68 Str << "\n"; 69 } 70} 71 72void dumpLiveRange(const Variable *Var, const Cfg *Func) { 73 if (!BuildDefs::dump()) 74 return; 75 Ostream &Str = Func->getContext()->getStrDump(); 76 const static size_t BufLen = 30; 77 char buf[BufLen]; 78 snprintf(buf, BufLen, "%2d", Var->getRegNumTmp()); 79 Str << "R=" << buf << " V="; 80 Var->dump(Func); 81 Str << " Range=" << Var->getLiveRange(); 82} 83 84} // end of anonymous namespace 85 86// Prepare for full register allocation of all variables. We depend 87// on liveness analysis to have calculated live ranges. 88void LinearScan::initForGlobal() { 89 TimerMarker T(TimerStack::TT_initUnhandled, Func); 90 FindPreference = true; 91 FindOverlap = true; 92 const VarList &Vars = Func->getVariables(); 93 Unhandled.reserve(Vars.size()); 94 UnhandledPrecolored.reserve(Vars.size()); 95 // Gather the live ranges of all variables and add them to the 96 // Unhandled set. 97 for (Variable *Var : Vars) { 98 // Explicitly don't consider zero-weight variables, which are 99 // meant to be spill slots. 100 if (Var->getWeight().isZero()) 101 continue; 102 // Don't bother if the variable has a null live range, which means 103 // it was never referenced. 104 if (Var->getLiveRange().isEmpty()) 105 continue; 106 Var->untrimLiveRange(); 107 Unhandled.push_back(Var); 108 if (Var->hasReg()) { 109 Var->setRegNumTmp(Var->getRegNum()); 110 Var->setLiveRangeInfiniteWeight(); 111 UnhandledPrecolored.push_back(Var); 112 } 113 } 114 115 // Build the (ordered) list of FakeKill instruction numbers. 116 Kills.clear(); 117 for (CfgNode *Node : Func->getNodes()) { 118 for (Inst &I : Node->getInsts()) { 119 if (auto Kill = llvm::dyn_cast<InstFakeKill>(&I)) { 120 if (!Kill->isDeleted() && !Kill->getLinked()->isDeleted()) 121 Kills.push_back(I.getNumber()); 122 } 123 } 124 } 125} 126 127// Prepare for very simple register allocation of only infinite-weight 128// Variables while respecting pre-colored Variables. Some properties 129// we take advantage of: 130// 131// * Live ranges of interest consist of a single segment. 132// 133// * Live ranges of interest never span a call instruction. 134// 135// * Phi instructions are not considered because either phis have 136// already been lowered, or they don't contain any pre-colored or 137// infinite-weight Variables. 138// 139// * We don't need to renumber instructions before computing live 140// ranges because all the high-level ICE instructions are deleted 141// prior to lowering, and the low-level instructions are added in 142// monotonically increasing order. 143// 144// * There are no opportunities for register preference or allowing 145// overlap. 146// 147// Some properties we aren't (yet) taking advantage of: 148// 149// * Because live ranges are a single segment, the Inactive set will 150// always be empty, and the live range trimming operation is 151// unnecessary. 152// 153// * Calculating overlap of single-segment live ranges could be 154// optimized a bit. 155void LinearScan::initForInfOnly() { 156 TimerMarker T(TimerStack::TT_initUnhandled, Func); 157 FindPreference = false; 158 FindOverlap = false; 159 SizeT NumVars = 0; 160 const VarList &Vars = Func->getVariables(); 161 162 // Iterate across all instructions and record the begin and end of 163 // the live range for each variable that is pre-colored or infinite 164 // weight. 165 std::vector<InstNumberT> LRBegin(Vars.size(), Inst::NumberSentinel); 166 std::vector<InstNumberT> LREnd(Vars.size(), Inst::NumberSentinel); 167 for (CfgNode *Node : Func->getNodes()) { 168 for (Inst &Inst : Node->getInsts()) { 169 if (Inst.isDeleted()) 170 continue; 171 if (const Variable *Var = Inst.getDest()) { 172 if (Var->hasReg() || Var->getWeight().isInf()) { 173 if (LRBegin[Var->getIndex()] == Inst::NumberSentinel) { 174 LRBegin[Var->getIndex()] = Inst.getNumber(); 175 ++NumVars; 176 } 177 } 178 } 179 for (SizeT I = 0; I < Inst.getSrcSize(); ++I) { 180 Operand *Src = Inst.getSrc(I); 181 SizeT NumVars = Src->getNumVars(); 182 for (SizeT J = 0; J < NumVars; ++J) { 183 const Variable *Var = Src->getVar(J); 184 if (Var->hasReg() || Var->getWeight().isInf()) 185 LREnd[Var->getIndex()] = Inst.getNumber(); 186 } 187 } 188 } 189 } 190 191 Unhandled.reserve(NumVars); 192 UnhandledPrecolored.reserve(NumVars); 193 for (SizeT i = 0; i < Vars.size(); ++i) { 194 Variable *Var = Vars[i]; 195 if (LRBegin[i] != Inst::NumberSentinel) { 196 assert(LREnd[i] != Inst::NumberSentinel); 197 Unhandled.push_back(Var); 198 Var->resetLiveRange(); 199 const uint32_t WeightDelta = 1; 200 Var->addLiveRange(LRBegin[i], LREnd[i], WeightDelta); 201 Var->untrimLiveRange(); 202 if (Var->hasReg()) { 203 Var->setRegNumTmp(Var->getRegNum()); 204 Var->setLiveRangeInfiniteWeight(); 205 UnhandledPrecolored.push_back(Var); 206 } 207 --NumVars; 208 } 209 } 210 // This isn't actually a fatal condition, but it would be nice to 211 // know if we somehow pre-calculated Unhandled's size wrong. 212 assert(NumVars == 0); 213 214 // Don't build up the list of Kills because we know that no 215 // infinite-weight Variable has a live range spanning a call. 216 Kills.clear(); 217} 218 219void LinearScan::init(RegAllocKind Kind) { 220 Unhandled.clear(); 221 UnhandledPrecolored.clear(); 222 Handled.clear(); 223 Inactive.clear(); 224 Active.clear(); 225 226 switch (Kind) { 227 case RAK_Global: 228 initForGlobal(); 229 break; 230 case RAK_InfOnly: 231 initForInfOnly(); 232 break; 233 } 234 235 struct CompareRanges { 236 bool operator()(const Variable *L, const Variable *R) { 237 InstNumberT Lstart = L->getLiveRange().getStart(); 238 InstNumberT Rstart = R->getLiveRange().getStart(); 239 if (Lstart == Rstart) 240 return L->getIndex() < R->getIndex(); 241 return Lstart < Rstart; 242 } 243 }; 244 // Do a reverse sort so that erasing elements (from the end) is fast. 245 std::sort(Unhandled.rbegin(), Unhandled.rend(), CompareRanges()); 246 std::sort(UnhandledPrecolored.rbegin(), UnhandledPrecolored.rend(), 247 CompareRanges()); 248 249 Handled.reserve(Unhandled.size()); 250 Inactive.reserve(Unhandled.size()); 251 Active.reserve(Unhandled.size()); 252} 253 254// Implements the linear-scan algorithm. Based on "Linear Scan 255// Register Allocation in the Context of SSA Form and Register 256// Constraints" by Hanspeter Mössenböck and Michael Pfeiffer, 257// ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF . This 258// implementation is modified to take affinity into account and allow 259// two interfering variables to share the same register in certain 260// cases. 261// 262// Requires running Cfg::liveness(Liveness_Intervals) in 263// preparation. Results are assigned to Variable::RegNum for each 264// Variable. 265void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull, 266 bool Randomized) { 267 TimerMarker T(TimerStack::TT_linearScan, Func); 268 assert(RegMaskFull.any()); // Sanity check 269 GlobalContext *Ctx = Func->getContext(); 270 const bool Verbose = BuildDefs::dump() && Func->isVerbose(IceV_LinearScan); 271 if (Verbose) 272 Ctx->lockStr(); 273 Func->resetCurrentNode(); 274 VariablesMetadata *VMetadata = Func->getVMetadata(); 275 const size_t NumRegisters = RegMaskFull.size(); 276 llvm::SmallBitVector PreDefinedRegisters(NumRegisters); 277 if (Randomized) { 278 for (Variable *Var : UnhandledPrecolored) { 279 PreDefinedRegisters[Var->getRegNum()] = true; 280 } 281 } 282 283 // Build a LiveRange representing the Kills list. 284 LiveRange KillsRange(Kills); 285 KillsRange.untrim(); 286 287 // RegUses[I] is the number of live ranges (variables) that register 288 // I is currently assigned to. It can be greater than 1 as a result 289 // of AllowOverlap inference below. 290 llvm::SmallVector<int, REGS_SIZE> RegUses(NumRegisters); 291 // Unhandled is already set to all ranges in increasing order of 292 // start points. 293 assert(Active.empty()); 294 assert(Inactive.empty()); 295 assert(Handled.empty()); 296 const TargetLowering::RegSetMask RegsInclude = 297 TargetLowering::RegSet_CallerSave; 298 const TargetLowering::RegSetMask RegsExclude = TargetLowering::RegSet_None; 299 const llvm::SmallBitVector KillsMask = 300 Func->getTarget()->getRegisterSet(RegsInclude, RegsExclude); 301 302 while (!Unhandled.empty()) { 303 Variable *Cur = Unhandled.back(); 304 Unhandled.pop_back(); 305 if (Verbose) { 306 Ostream &Str = Ctx->getStrDump(); 307 Str << "\nConsidering "; 308 dumpLiveRange(Cur, Func); 309 Str << "\n"; 310 } 311 const llvm::SmallBitVector RegMask = 312 RegMaskFull & Func->getTarget()->getRegisterSetForType(Cur->getType()); 313 KillsRange.trim(Cur->getLiveRange().getStart()); 314 315 // Check for precolored ranges. If Cur is precolored, it 316 // definitely gets that register. Previously processed live 317 // ranges would have avoided that register due to it being 318 // precolored. Future processed live ranges won't evict that 319 // register because the live range has infinite weight. 320 if (Cur->hasReg()) { 321 int32_t RegNum = Cur->getRegNum(); 322 // RegNumTmp should have already been set above. 323 assert(Cur->getRegNumTmp() == RegNum); 324 if (Verbose) { 325 Ostream &Str = Ctx->getStrDump(); 326 Str << "Precoloring "; 327 dumpLiveRange(Cur, Func); 328 Str << "\n"; 329 } 330 Active.push_back(Cur); 331 assert(RegUses[RegNum] >= 0); 332 ++RegUses[RegNum]; 333 assert(!UnhandledPrecolored.empty()); 334 assert(UnhandledPrecolored.back() == Cur); 335 UnhandledPrecolored.pop_back(); 336 continue; 337 } 338 339 // Check for active ranges that have expired or become inactive. 340 for (SizeT I = Active.size(); I > 0; --I) { 341 const SizeT Index = I - 1; 342 Variable *Item = Active[Index]; 343 Item->trimLiveRange(Cur->getLiveRange().getStart()); 344 bool Moved = false; 345 if (Item->rangeEndsBefore(Cur)) { 346 // Move Item from Active to Handled list. 347 if (Verbose) { 348 Ostream &Str = Ctx->getStrDump(); 349 Str << "Expiring "; 350 dumpLiveRange(Item, Func); 351 Str << "\n"; 352 } 353 moveItem(Active, Index, Handled); 354 Moved = true; 355 } else if (!Item->rangeOverlapsStart(Cur)) { 356 // Move Item from Active to Inactive list. 357 if (Verbose) { 358 Ostream &Str = Ctx->getStrDump(); 359 Str << "Inactivating "; 360 dumpLiveRange(Item, Func); 361 Str << "\n"; 362 } 363 moveItem(Active, Index, Inactive); 364 Moved = true; 365 } 366 if (Moved) { 367 // Decrement Item from RegUses[]. 368 assert(Item->hasRegTmp()); 369 int32_t RegNum = Item->getRegNumTmp(); 370 --RegUses[RegNum]; 371 assert(RegUses[RegNum] >= 0); 372 } 373 } 374 375 // Check for inactive ranges that have expired or reactivated. 376 for (SizeT I = Inactive.size(); I > 0; --I) { 377 const SizeT Index = I - 1; 378 Variable *Item = Inactive[Index]; 379 Item->trimLiveRange(Cur->getLiveRange().getStart()); 380 if (Item->rangeEndsBefore(Cur)) { 381 // Move Item from Inactive to Handled list. 382 if (Verbose) { 383 Ostream &Str = Ctx->getStrDump(); 384 Str << "Expiring "; 385 dumpLiveRange(Item, Func); 386 Str << "\n"; 387 } 388 moveItem(Inactive, Index, Handled); 389 } else if (Item->rangeOverlapsStart(Cur)) { 390 // Move Item from Inactive to Active list. 391 if (Verbose) { 392 Ostream &Str = Ctx->getStrDump(); 393 Str << "Reactivating "; 394 dumpLiveRange(Item, Func); 395 Str << "\n"; 396 } 397 moveItem(Inactive, Index, Active); 398 // Increment Item in RegUses[]. 399 assert(Item->hasRegTmp()); 400 int32_t RegNum = Item->getRegNumTmp(); 401 assert(RegUses[RegNum] >= 0); 402 ++RegUses[RegNum]; 403 } 404 } 405 406 // Calculate available registers into Free[]. 407 llvm::SmallBitVector Free = RegMask; 408 for (SizeT i = 0; i < RegMask.size(); ++i) { 409 if (RegUses[i] > 0) 410 Free[i] = false; 411 } 412 413 // Infer register preference and allowable overlap. Only form a 414 // preference when the current Variable has an unambiguous "first" 415 // definition. The preference is some source Variable of the 416 // defining instruction that either is assigned a register that is 417 // currently free, or that is assigned a register that is not free 418 // but overlap is allowed. Overlap is allowed when the Variable 419 // under consideration is single-definition, and its definition is 420 // a simple assignment - i.e., the register gets copied/aliased 421 // but is never modified. Furthermore, overlap is only allowed 422 // when preferred Variable definition instructions do not appear 423 // within the current Variable's live range. 424 Variable *Prefer = nullptr; 425 int32_t PreferReg = Variable::NoRegister; 426 bool AllowOverlap = false; 427 if (FindPreference) { 428 if (const Inst *DefInst = VMetadata->getFirstDefinition(Cur)) { 429 assert(DefInst->getDest() == Cur); 430 bool IsAssign = DefInst->isSimpleAssign(); 431 bool IsSingleDef = !VMetadata->isMultiDef(Cur); 432 for (SizeT i = 0; i < DefInst->getSrcSize(); ++i) { 433 // TODO(stichnot): Iterate through the actual Variables of the 434 // instruction, not just the source operands. This could 435 // capture Load instructions, including address mode 436 // optimization, for Prefer (but not for AllowOverlap). 437 if (Variable *SrcVar = llvm::dyn_cast<Variable>(DefInst->getSrc(i))) { 438 int32_t SrcReg = SrcVar->getRegNumTmp(); 439 // Only consider source variables that have (so far) been 440 // assigned a register. That register must be one in the 441 // RegMask set, e.g. don't try to prefer the stack pointer 442 // as a result of the stacksave intrinsic. 443 if (SrcVar->hasRegTmp() && RegMask[SrcReg]) { 444 if (FindOverlap && !Free[SrcReg]) { 445 // Don't bother trying to enable AllowOverlap if the 446 // register is already free. 447 AllowOverlap = 448 IsSingleDef && IsAssign && !overlapsDefs(Func, Cur, SrcVar); 449 } 450 if (AllowOverlap || Free[SrcReg]) { 451 Prefer = SrcVar; 452 PreferReg = SrcReg; 453 } 454 } 455 } 456 } 457 if (Verbose && Prefer) { 458 Ostream &Str = Ctx->getStrDump(); 459 Str << "Initial Prefer="; 460 Prefer->dump(Func); 461 Str << " R=" << PreferReg << " LIVE=" << Prefer->getLiveRange() 462 << " Overlap=" << AllowOverlap << "\n"; 463 } 464 } 465 } 466 467 // Remove registers from the Free[] list where an Inactive range 468 // overlaps with the current range. 469 for (const Variable *Item : Inactive) { 470 if (Item->rangeOverlaps(Cur)) { 471 int32_t RegNum = Item->getRegNumTmp(); 472 // Don't assert(Free[RegNum]) because in theory (though 473 // probably never in practice) there could be two inactive 474 // variables that were marked with AllowOverlap. 475 Free[RegNum] = false; 476 // Disable AllowOverlap if an Inactive variable, which is not 477 // Prefer, shares Prefer's register, and has a definition 478 // within Cur's live range. 479 if (AllowOverlap && Item != Prefer && RegNum == PreferReg && 480 overlapsDefs(Func, Cur, Item)) { 481 AllowOverlap = false; 482 dumpDisableOverlap(Func, Item, "Inactive"); 483 } 484 } 485 } 486 487 // Disable AllowOverlap if an Active variable, which is not 488 // Prefer, shares Prefer's register, and has a definition within 489 // Cur's live range. 490 if (AllowOverlap) { 491 for (const Variable *Item : Active) { 492 int32_t RegNum = Item->getRegNumTmp(); 493 if (Item != Prefer && RegNum == PreferReg && 494 overlapsDefs(Func, Cur, Item)) { 495 AllowOverlap = false; 496 dumpDisableOverlap(Func, Item, "Active"); 497 } 498 } 499 } 500 501 llvm::SmallVector<RegWeight, REGS_SIZE> Weights(RegMask.size()); 502 503 // Remove registers from the Free[] list where an Unhandled 504 // precolored range overlaps with the current range, and set those 505 // registers to infinite weight so that they aren't candidates for 506 // eviction. Cur->rangeEndsBefore(Item) is an early exit check 507 // that turns a guaranteed O(N^2) algorithm into expected linear 508 // complexity. 509 llvm::SmallBitVector PrecoloredUnhandledMask(RegMask.size()); 510 // Note: PrecoloredUnhandledMask is only used for dumping. 511 for (Variable *Item : reverse_range(UnhandledPrecolored)) { 512 assert(Item->hasReg()); 513 if (Cur->rangeEndsBefore(Item)) 514 break; 515 if (Item->rangeOverlaps(Cur)) { 516 int32_t ItemReg = Item->getRegNum(); // Note: not getRegNumTmp() 517 Weights[ItemReg].setWeight(RegWeight::Inf); 518 Free[ItemReg] = false; 519 PrecoloredUnhandledMask[ItemReg] = true; 520 // Disable AllowOverlap if the preferred register is one of 521 // these precolored unhandled overlapping ranges. 522 if (AllowOverlap && ItemReg == PreferReg) { 523 AllowOverlap = false; 524 dumpDisableOverlap(Func, Item, "PrecoloredUnhandled"); 525 } 526 } 527 } 528 529 // Remove scratch registers from the Free[] list, and mark their 530 // Weights[] as infinite, if KillsRange overlaps Cur's live range. 531 const bool UseTrimmed = true; 532 if (Cur->getLiveRange().overlaps(KillsRange, UseTrimmed)) { 533 Free.reset(KillsMask); 534 for (int i = KillsMask.find_first(); i != -1; 535 i = KillsMask.find_next(i)) { 536 Weights[i].setWeight(RegWeight::Inf); 537 if (PreferReg == i) 538 AllowOverlap = false; 539 } 540 } 541 542 // Print info about physical register availability. 543 if (Verbose) { 544 Ostream &Str = Ctx->getStrDump(); 545 for (SizeT i = 0; i < RegMask.size(); ++i) { 546 if (RegMask[i]) { 547 Str << Func->getTarget()->getRegName(i, IceType_i32) 548 << "(U=" << RegUses[i] << ",F=" << Free[i] 549 << ",P=" << PrecoloredUnhandledMask[i] << ") "; 550 } 551 } 552 Str << "\n"; 553 } 554 555 if (Prefer && (AllowOverlap || Free[PreferReg])) { 556 // First choice: a preferred register that is either free or is 557 // allowed to overlap with its linked variable. 558 Cur->setRegNumTmp(PreferReg); 559 if (Verbose) { 560 Ostream &Str = Ctx->getStrDump(); 561 Str << "Preferring "; 562 dumpLiveRange(Cur, Func); 563 Str << "\n"; 564 } 565 assert(RegUses[PreferReg] >= 0); 566 ++RegUses[PreferReg]; 567 Active.push_back(Cur); 568 } else if (Free.any()) { 569 // Second choice: any free register. TODO: After explicit 570 // affinity is considered, is there a strategy better than just 571 // picking the lowest-numbered available register? 572 int32_t RegNum = Free.find_first(); 573 Cur->setRegNumTmp(RegNum); 574 if (Verbose) { 575 Ostream &Str = Ctx->getStrDump(); 576 Str << "Allocating "; 577 dumpLiveRange(Cur, Func); 578 Str << "\n"; 579 } 580 assert(RegUses[RegNum] >= 0); 581 ++RegUses[RegNum]; 582 Active.push_back(Cur); 583 } else { 584 // Fallback: there are no free registers, so we look for the 585 // lowest-weight register and see if Cur has higher weight. 586 // Check Active ranges. 587 for (const Variable *Item : Active) { 588 assert(Item->rangeOverlaps(Cur)); 589 int32_t RegNum = Item->getRegNumTmp(); 590 assert(Item->hasRegTmp()); 591 Weights[RegNum].addWeight(Item->getLiveRange().getWeight()); 592 } 593 // Same as above, but check Inactive ranges instead of Active. 594 for (const Variable *Item : Inactive) { 595 int32_t RegNum = Item->getRegNumTmp(); 596 assert(Item->hasRegTmp()); 597 if (Item->rangeOverlaps(Cur)) 598 Weights[RegNum].addWeight(Item->getLiveRange().getWeight()); 599 } 600 601 // All the weights are now calculated. Find the register with 602 // smallest weight. 603 int32_t MinWeightIndex = RegMask.find_first(); 604 // MinWeightIndex must be valid because of the initial 605 // RegMask.any() test. 606 assert(MinWeightIndex >= 0); 607 for (SizeT i = MinWeightIndex + 1; i < Weights.size(); ++i) { 608 if (RegMask[i] && Weights[i] < Weights[MinWeightIndex]) 609 MinWeightIndex = i; 610 } 611 612 if (Cur->getLiveRange().getWeight() <= Weights[MinWeightIndex]) { 613 // Cur doesn't have priority over any other live ranges, so 614 // don't allocate any register to it, and move it to the 615 // Handled state. 616 Handled.push_back(Cur); 617 if (Cur->getLiveRange().getWeight().isInf()) { 618 Func->setError("Unable to find a physical register for an " 619 "infinite-weight live range"); 620 } 621 } else { 622 // Evict all live ranges in Active that register number 623 // MinWeightIndex is assigned to. 624 for (SizeT I = Active.size(); I > 0; --I) { 625 const SizeT Index = I - 1; 626 Variable *Item = Active[Index]; 627 if (Item->getRegNumTmp() == MinWeightIndex) { 628 if (Verbose) { 629 Ostream &Str = Ctx->getStrDump(); 630 Str << "Evicting "; 631 dumpLiveRange(Item, Func); 632 Str << "\n"; 633 } 634 --RegUses[MinWeightIndex]; 635 assert(RegUses[MinWeightIndex] >= 0); 636 Item->setRegNumTmp(Variable::NoRegister); 637 moveItem(Active, Index, Handled); 638 } 639 } 640 // Do the same for Inactive. 641 for (SizeT I = Inactive.size(); I > 0; --I) { 642 const SizeT Index = I - 1; 643 Variable *Item = Inactive[Index]; 644 // Note: The Item->rangeOverlaps(Cur) clause is not part of the 645 // description of AssignMemLoc() in the original paper. But 646 // there doesn't seem to be any need to evict an inactive 647 // live range that doesn't overlap with the live range 648 // currently being considered. It's especially bad if we 649 // would end up evicting an infinite-weight but 650 // currently-inactive live range. The most common situation 651 // for this would be a scratch register kill set for call 652 // instructions. 653 if (Item->getRegNumTmp() == MinWeightIndex && 654 Item->rangeOverlaps(Cur)) { 655 if (Verbose) { 656 Ostream &Str = Ctx->getStrDump(); 657 Str << "Evicting "; 658 dumpLiveRange(Item, Func); 659 Str << "\n"; 660 } 661 Item->setRegNumTmp(Variable::NoRegister); 662 moveItem(Inactive, Index, Handled); 663 } 664 } 665 // Assign the register to Cur. 666 Cur->setRegNumTmp(MinWeightIndex); 667 assert(RegUses[MinWeightIndex] >= 0); 668 ++RegUses[MinWeightIndex]; 669 Active.push_back(Cur); 670 if (Verbose) { 671 Ostream &Str = Ctx->getStrDump(); 672 Str << "Allocating "; 673 dumpLiveRange(Cur, Func); 674 Str << "\n"; 675 } 676 } 677 } 678 dump(Func); 679 } 680 // Move anything Active or Inactive to Handled for easier handling. 681 for (Variable *I : Active) 682 Handled.push_back(I); 683 Active.clear(); 684 for (Variable *I : Inactive) 685 Handled.push_back(I); 686 Inactive.clear(); 687 dump(Func); 688 689 llvm::SmallVector<int32_t, REGS_SIZE> Permutation(NumRegisters); 690 if (Randomized) { 691 Func->getTarget()->makeRandomRegisterPermutation( 692 Permutation, PreDefinedRegisters | ~RegMaskFull); 693 } 694 695 // Finish up by assigning RegNumTmp->RegNum (or a random permutation 696 // thereof) for each Variable. 697 for (Variable *Item : Handled) { 698 int32_t RegNum = Item->getRegNumTmp(); 699 int32_t AssignedRegNum = RegNum; 700 701 if (Randomized && Item->hasRegTmp() && !Item->hasReg()) { 702 AssignedRegNum = Permutation[RegNum]; 703 } 704 if (Verbose) { 705 Ostream &Str = Ctx->getStrDump(); 706 if (!Item->hasRegTmp()) { 707 Str << "Not assigning "; 708 Item->dump(Func); 709 Str << "\n"; 710 } else { 711 Str << (AssignedRegNum == Item->getRegNum() ? "Reassigning " 712 : "Assigning ") 713 << Func->getTarget()->getRegName(AssignedRegNum, IceType_i32) 714 << "(r" << AssignedRegNum << ") to "; 715 Item->dump(Func); 716 Str << "\n"; 717 } 718 } 719 Item->setRegNum(AssignedRegNum); 720 } 721 722 // TODO: Consider running register allocation one more time, with 723 // infinite registers, for two reasons. First, evicted live ranges 724 // get a second chance for a register. Second, it allows coalescing 725 // of stack slots. If there is no time budget for the second 726 // register allocation run, each unallocated variable just gets its 727 // own slot. 728 // 729 // Another idea for coalescing stack slots is to initialize the 730 // Unhandled list with just the unallocated variables, saving time 731 // but not offering second-chance opportunities. 732 733 if (Verbose) 734 Ctx->unlockStr(); 735} 736 737// ======================== Dump routines ======================== // 738 739void LinearScan::dump(Cfg *Func) const { 740 if (!BuildDefs::dump()) 741 return; 742 if (!Func->isVerbose(IceV_LinearScan)) 743 return; 744 Ostream &Str = Func->getContext()->getStrDump(); 745 Func->resetCurrentNode(); 746 Str << "**** Current regalloc state:\n"; 747 Str << "++++++ Handled:\n"; 748 for (const Variable *Item : Handled) { 749 dumpLiveRange(Item, Func); 750 Str << "\n"; 751 } 752 Str << "++++++ Unhandled:\n"; 753 for (const Variable *Item : reverse_range(Unhandled)) { 754 dumpLiveRange(Item, Func); 755 Str << "\n"; 756 } 757 Str << "++++++ Active:\n"; 758 for (const Variable *Item : Active) { 759 dumpLiveRange(Item, Func); 760 Str << "\n"; 761 } 762 Str << "++++++ Inactive:\n"; 763 for (const Variable *Item : Inactive) { 764 dumpLiveRange(Item, Func); 765 Str << "\n"; 766 } 767} 768 769} // end of namespace Ice 770