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 /// \file | 10 /// \file |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
63 Str << "," << Defs[i]->getNumber(); | 63 Str << "," << Defs[i]->getNumber(); |
64 } | 64 } |
65 Str << "\n"; | 65 Str << "\n"; |
66 } | 66 } |
67 | 67 |
68 void dumpLiveRange(const Variable *Var, const Cfg *Func) { | 68 void dumpLiveRange(const Variable *Var, const Cfg *Func) { |
69 if (!BuildDefs::dump()) | 69 if (!BuildDefs::dump()) |
70 return; | 70 return; |
71 Ostream &Str = Func->getContext()->getStrDump(); | 71 Ostream &Str = Func->getContext()->getStrDump(); |
72 char buf[30]; | 72 char buf[30]; |
73 snprintf(buf, llvm::array_lengthof(buf), "%2d", Var->getRegNumTmp()); | 73 snprintf(buf, llvm::array_lengthof(buf), "%2u", |
| 74 unsigned(Var->getRegNumTmp())); |
74 Str << "R=" << buf << " V="; | 75 Str << "R=" << buf << " V="; |
75 Var->dump(Func); | 76 Var->dump(Func); |
76 Str << " Range=" << Var->getLiveRange(); | 77 Str << " Range=" << Var->getLiveRange(); |
77 } | 78 } |
78 | 79 |
79 int32_t findMinWeightIndex( | 80 int32_t findMinWeightIndex( |
80 const llvm::SmallBitVector &RegMask, | 81 const llvm::SmallBitVector &RegMask, |
81 const llvm::SmallVector<RegWeight, LinearScan::REGS_SIZE> &Weights) { | 82 const llvm::SmallVector<RegWeight, LinearScan::REGS_SIZE> &Weights) { |
82 int32_t MinWeightIndex = RegMask.find_first(); | 83 int MinWeightIndex = -1; |
83 assert(MinWeightIndex >= 0); | 84 for (RegNumT i : RegNumBVIter(RegMask)) { |
84 for (int32_t i = RegMask.find_next(MinWeightIndex); i != -1; | 85 if (MinWeightIndex < 0 || Weights[i] < Weights[MinWeightIndex]) |
85 i = RegMask.find_next(i)) { | |
86 if (Weights[i] < Weights[MinWeightIndex]) | |
87 MinWeightIndex = i; | 86 MinWeightIndex = i; |
88 } | 87 } |
| 88 assert(MinWeightIndex >= 0); |
89 return MinWeightIndex; | 89 return MinWeightIndex; |
90 } | 90 } |
91 | 91 |
92 } // end of anonymous namespace | 92 } // end of anonymous namespace |
93 | 93 |
94 LinearScan::LinearScan(Cfg *Func) | 94 LinearScan::LinearScan(Cfg *Func) |
95 : Func(Func), Ctx(Func->getContext()), Target(Func->getTarget()), | 95 : Func(Func), Ctx(Func->getContext()), Target(Func->getTarget()), |
96 Verbose(BuildDefs::dump() && Func->isVerbose(IceV_LinearScan)), | 96 Verbose(BuildDefs::dump() && Func->isVerbose(IceV_LinearScan)), |
97 UseReserve(Ctx->getFlags().getRegAllocReserve()) {} | 97 UseReserve(Ctx->getFlags().getRegAllocReserve()) {} |
98 | 98 |
(...skipping 226 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
325 this->Kind = Kind; | 325 this->Kind = Kind; |
326 Unhandled.clear(); | 326 Unhandled.clear(); |
327 UnhandledPrecolored.clear(); | 327 UnhandledPrecolored.clear(); |
328 Handled.clear(); | 328 Handled.clear(); |
329 Inactive.clear(); | 329 Inactive.clear(); |
330 Active.clear(); | 330 Active.clear(); |
331 | 331 |
332 SizeT NumRegs = Target->getNumRegisters(); | 332 SizeT NumRegs = Target->getNumRegisters(); |
333 RegAliases.resize(NumRegs); | 333 RegAliases.resize(NumRegs); |
334 for (SizeT Reg = 0; Reg < NumRegs; ++Reg) { | 334 for (SizeT Reg = 0; Reg < NumRegs; ++Reg) { |
335 RegAliases[Reg] = &Target->getAliasesForRegister(Reg); | 335 RegAliases[Reg] = &Target->getAliasesForRegister(RegNumT::fromInt(Reg)); |
336 } | 336 } |
337 | 337 |
338 switch (Kind) { | 338 switch (Kind) { |
339 case RAK_Unknown: | 339 case RAK_Unknown: |
340 llvm::report_fatal_error("Invalid RAK_Unknown"); | 340 llvm::report_fatal_error("Invalid RAK_Unknown"); |
341 break; | 341 break; |
342 case RAK_Global: | 342 case RAK_Global: |
343 case RAK_Phi: | 343 case RAK_Phi: |
344 initForGlobal(); | 344 initForGlobal(); |
345 break; | 345 break; |
(...skipping 61 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
407 if (I->getNumber() == End) | 407 if (I->getNumber() == End) |
408 FillPoint = I; | 408 FillPoint = I; |
409 if (SpillPoint != E) { | 409 if (SpillPoint != E) { |
410 // Remove from RegMask any physical registers referenced during Cur's live | 410 // Remove from RegMask any physical registers referenced during Cur's live |
411 // range. Start looking after SpillPoint gets set, i.e. once Cur's live | 411 // range. Start looking after SpillPoint gets set, i.e. once Cur's live |
412 // range begins. | 412 // range begins. |
413 FOREACH_VAR_IN_INST(Var, *I) { | 413 FOREACH_VAR_IN_INST(Var, *I) { |
414 if (!Var->hasRegTmp()) | 414 if (!Var->hasRegTmp()) |
415 continue; | 415 continue; |
416 const llvm::SmallBitVector &Aliases = *RegAliases[Var->getRegNumTmp()]; | 416 const llvm::SmallBitVector &Aliases = *RegAliases[Var->getRegNumTmp()]; |
417 for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; | 417 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
418 RegAlias = Aliases.find_next(RegAlias)) { | |
419 Iter.RegMask[RegAlias] = false; | 418 Iter.RegMask[RegAlias] = false; |
420 } | 419 } |
421 } | 420 } |
422 } | 421 } |
423 } | 422 } |
424 assert(SpillPoint != Insts.end()); | 423 assert(SpillPoint != Insts.end()); |
425 assert(FillPoint != Insts.end()); | 424 assert(FillPoint != Insts.end()); |
426 ++FillPoint; | 425 ++FillPoint; |
427 // TODO(stichnot): Randomize instead of find_first(). | 426 // TODO(stichnot): Randomize instead of *.begin() which maps to find_first(). |
428 int32_t RegNum = Iter.RegMask.find_first(); | 427 const RegNumT RegNum = *RegNumBVIter(Iter.RegMask).begin(); |
429 assert(RegNum != -1); | |
430 Iter.Cur->setRegNumTmp(RegNum); | 428 Iter.Cur->setRegNumTmp(RegNum); |
431 Variable *Preg = Target->getPhysicalRegister(RegNum, Iter.Cur->getType()); | 429 Variable *Preg = Target->getPhysicalRegister(RegNum, Iter.Cur->getType()); |
432 // TODO(stichnot): Add SpillLoc to VariablesMetadata tracking so that SpillLoc | 430 // TODO(stichnot): Add SpillLoc to VariablesMetadata tracking so that SpillLoc |
433 // is correctly identified as !isMultiBlock(), reducing stack frame size. | 431 // is correctly identified as !isMultiBlock(), reducing stack frame size. |
434 Variable *SpillLoc = Func->makeVariable(Iter.Cur->getType()); | 432 Variable *SpillLoc = Func->makeVariable(Iter.Cur->getType()); |
435 // Add "reg=FakeDef;spill=reg" before SpillPoint | 433 // Add "reg=FakeDef;spill=reg" before SpillPoint |
436 Target->lowerInst(Node, SpillPoint, InstFakeDef::create(Func, Preg)); | 434 Target->lowerInst(Node, SpillPoint, InstFakeDef::create(Func, Preg)); |
437 Target->lowerInst(Node, SpillPoint, InstAssign::create(Func, SpillLoc, Preg)); | 435 Target->lowerInst(Node, SpillPoint, InstAssign::create(Func, SpillLoc, Preg)); |
438 // add "reg=spill;FakeUse(reg)" before FillPoint | 436 // add "reg=spill;FakeUse(reg)" before FillPoint |
439 Target->lowerInst(Node, FillPoint, InstAssign::create(Func, Preg, SpillLoc)); | 437 Target->lowerInst(Node, FillPoint, InstAssign::create(Func, Preg, SpillLoc)); |
(...skipping 14 matching lines...) Expand all Loading... |
454 } else if (!Item->rangeOverlapsStart(Cur)) { | 452 } else if (!Item->rangeOverlapsStart(Cur)) { |
455 // Move Item from Active to Inactive list. | 453 // Move Item from Active to Inactive list. |
456 dumpLiveRangeTrace("Inactivating ", Item); | 454 dumpLiveRangeTrace("Inactivating ", Item); |
457 moveItem(Active, Index, Inactive); | 455 moveItem(Active, Index, Inactive); |
458 Moved = true; | 456 Moved = true; |
459 } | 457 } |
460 if (Moved) { | 458 if (Moved) { |
461 // Decrement Item from RegUses[]. | 459 // Decrement Item from RegUses[]. |
462 assert(Item->hasRegTmp()); | 460 assert(Item->hasRegTmp()); |
463 const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; | 461 const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; |
464 for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; | 462 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
465 RegAlias = Aliases.find_next(RegAlias)) { | |
466 --RegUses[RegAlias]; | 463 --RegUses[RegAlias]; |
467 assert(RegUses[RegAlias] >= 0); | 464 assert(RegUses[RegAlias] >= 0); |
468 } | 465 } |
469 } | 466 } |
470 } | 467 } |
471 } | 468 } |
472 | 469 |
473 void LinearScan::handleInactiveRangeExpiredOrReactivated(const Variable *Cur) { | 470 void LinearScan::handleInactiveRangeExpiredOrReactivated(const Variable *Cur) { |
474 for (SizeT I = Inactive.size(); I > 0; --I) { | 471 for (SizeT I = Inactive.size(); I > 0; --I) { |
475 const SizeT Index = I - 1; | 472 const SizeT Index = I - 1; |
476 Variable *Item = Inactive[Index]; | 473 Variable *Item = Inactive[Index]; |
477 Item->trimLiveRange(Cur->getLiveRange().getStart()); | 474 Item->trimLiveRange(Cur->getLiveRange().getStart()); |
478 if (Item->rangeEndsBefore(Cur)) { | 475 if (Item->rangeEndsBefore(Cur)) { |
479 // Move Item from Inactive to Handled list. | 476 // Move Item from Inactive to Handled list. |
480 dumpLiveRangeTrace("Expiring ", Item); | 477 dumpLiveRangeTrace("Expiring ", Item); |
481 moveItem(Inactive, Index, Handled); | 478 moveItem(Inactive, Index, Handled); |
482 } else if (Item->rangeOverlapsStart(Cur)) { | 479 } else if (Item->rangeOverlapsStart(Cur)) { |
483 // Move Item from Inactive to Active list. | 480 // Move Item from Inactive to Active list. |
484 dumpLiveRangeTrace("Reactivating ", Item); | 481 dumpLiveRangeTrace("Reactivating ", Item); |
485 moveItem(Inactive, Index, Active); | 482 moveItem(Inactive, Index, Active); |
486 // Increment Item in RegUses[]. | 483 // Increment Item in RegUses[]. |
487 assert(Item->hasRegTmp()); | 484 assert(Item->hasRegTmp()); |
488 const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; | 485 const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; |
489 for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; | 486 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
490 RegAlias = Aliases.find_next(RegAlias)) { | |
491 assert(RegUses[RegAlias] >= 0); | 487 assert(RegUses[RegAlias] >= 0); |
492 ++RegUses[RegAlias]; | 488 ++RegUses[RegAlias]; |
493 } | 489 } |
494 } | 490 } |
495 } | 491 } |
496 } | 492 } |
497 | 493 |
498 // Infer register preference and allowable overlap. Only form a preference when | 494 // Infer register preference and allowable overlap. Only form a preference when |
499 // the current Variable has an unambiguous "first" definition. The preference is | 495 // the current Variable has an unambiguous "first" definition. The preference is |
500 // some source Variable of the defining instruction that either is assigned a | 496 // some source Variable of the defining instruction that either is assigned a |
501 // register that is currently free, or that is assigned a register that is not | 497 // register that is currently free, or that is assigned a register that is not |
502 // free but overlap is allowed. Overlap is allowed when the Variable under | 498 // free but overlap is allowed. Overlap is allowed when the Variable under |
503 // consideration is single-definition, and its definition is a simple assignment | 499 // consideration is single-definition, and its definition is a simple assignment |
504 // - i.e., the register gets copied/aliased but is never modified. Furthermore, | 500 // - i.e., the register gets copied/aliased but is never modified. Furthermore, |
505 // overlap is only allowed when preferred Variable definition instructions do | 501 // overlap is only allowed when preferred Variable definition instructions do |
506 // not appear within the current Variable's live range. | 502 // not appear within the current Variable's live range. |
507 void LinearScan::findRegisterPreference(IterationState &Iter) { | 503 void LinearScan::findRegisterPreference(IterationState &Iter) { |
508 Iter.Prefer = nullptr; | 504 Iter.Prefer = nullptr; |
509 Iter.PreferReg = Variable::NoRegister; | 505 Iter.PreferReg = RegNumT::NoRegister; |
510 Iter.AllowOverlap = false; | 506 Iter.AllowOverlap = false; |
511 | 507 |
512 if (!FindPreference) | 508 if (!FindPreference) |
513 return; | 509 return; |
514 | 510 |
515 VariablesMetadata *VMetadata = Func->getVMetadata(); | 511 VariablesMetadata *VMetadata = Func->getVMetadata(); |
516 const Inst *DefInst = VMetadata->getFirstDefinitionSingleBlock(Iter.Cur); | 512 const Inst *DefInst = VMetadata->getFirstDefinitionSingleBlock(Iter.Cur); |
517 if (DefInst == nullptr) | 513 if (DefInst == nullptr) |
518 return; | 514 return; |
519 | 515 |
520 assert(DefInst->getDest() == Iter.Cur); | 516 assert(DefInst->getDest() == Iter.Cur); |
521 const bool IsSingleDefAssign = | 517 const bool IsSingleDefAssign = |
522 DefInst->isVarAssign() && !VMetadata->isMultiDef(Iter.Cur); | 518 DefInst->isVarAssign() && !VMetadata->isMultiDef(Iter.Cur); |
523 FOREACH_VAR_IN_INST(SrcVar, *DefInst) { | 519 FOREACH_VAR_IN_INST(SrcVar, *DefInst) { |
524 // Only consider source variables that have (so far) been assigned a | 520 // Only consider source variables that have (so far) been assigned a |
525 // register. | 521 // register. |
526 if (!SrcVar->hasRegTmp()) | 522 if (!SrcVar->hasRegTmp()) |
527 continue; | 523 continue; |
528 | 524 |
529 // That register must be one in the RegMask set, e.g. don't try to prefer | 525 // That register must be one in the RegMask set, e.g. don't try to prefer |
530 // the stack pointer as a result of the stacksave intrinsic. | 526 // the stack pointer as a result of the stacksave intrinsic. |
531 const llvm::SmallBitVector &Aliases = *RegAliases[SrcVar->getRegNumTmp()]; | 527 const llvm::SmallBitVector &Aliases = *RegAliases[SrcVar->getRegNumTmp()]; |
532 const int32_t SrcReg = (Iter.RegMask & Aliases).find_first(); | 528 const int SrcReg = (Iter.RegMask & Aliases).find_first(); |
533 if (SrcReg == -1) | 529 if (SrcReg == -1) |
534 continue; | 530 continue; |
535 | 531 |
536 if (FindOverlap && IsSingleDefAssign && !Iter.Free[SrcReg]) { | 532 if (FindOverlap && IsSingleDefAssign && !Iter.Free[SrcReg]) { |
537 // Don't bother trying to enable AllowOverlap if the register is already | 533 // Don't bother trying to enable AllowOverlap if the register is already |
538 // free (hence the test on Iter.Free[SrcReg]). | 534 // free (hence the test on Iter.Free[SrcReg]). |
539 Iter.AllowOverlap = !overlapsDefs(Func, Iter.Cur, SrcVar); | 535 Iter.AllowOverlap = !overlapsDefs(Func, Iter.Cur, SrcVar); |
540 } | 536 } |
541 if (Iter.AllowOverlap || Iter.Free[SrcReg]) { | 537 if (Iter.AllowOverlap || Iter.Free[SrcReg]) { |
542 Iter.Prefer = SrcVar; | 538 Iter.Prefer = SrcVar; |
543 Iter.PreferReg = SrcReg; | 539 Iter.PreferReg = RegNumT::fromInt(SrcReg); |
544 // Stop looking for a preference after the first valid preference is | 540 // Stop looking for a preference after the first valid preference is |
545 // found. One might think that we should look at all instruction | 541 // found. One might think that we should look at all instruction |
546 // variables to find the best <Prefer,AllowOverlap> combination, but note | 542 // variables to find the best <Prefer,AllowOverlap> combination, but note |
547 // that AllowOverlap can only be true for a simple assignment statement | 543 // that AllowOverlap can only be true for a simple assignment statement |
548 // which can have only one source operand, so it's not possible for | 544 // which can have only one source operand, so it's not possible for |
549 // AllowOverlap to be true beyond the first source operand. | 545 // AllowOverlap to be true beyond the first source operand. |
550 FOREACH_VAR_IN_INST_BREAK; | 546 FOREACH_VAR_IN_INST_BREAK; |
551 } | 547 } |
552 } | 548 } |
553 if (BuildDefs::dump() && Verbose && Iter.Prefer) { | 549 if (BuildDefs::dump() && Verbose && Iter.Prefer) { |
554 Ostream &Str = Ctx->getStrDump(); | 550 Ostream &Str = Ctx->getStrDump(); |
555 Str << "Initial Iter.Prefer="; | 551 Str << "Initial Iter.Prefer="; |
556 Iter.Prefer->dump(Func); | 552 Iter.Prefer->dump(Func); |
557 Str << " R=" << Iter.PreferReg << " LIVE=" << Iter.Prefer->getLiveRange() | 553 Str << " R=" << Iter.PreferReg << " LIVE=" << Iter.Prefer->getLiveRange() |
558 << " Overlap=" << Iter.AllowOverlap << "\n"; | 554 << " Overlap=" << Iter.AllowOverlap << "\n"; |
559 } | 555 } |
560 } | 556 } |
561 | 557 |
562 // Remove registers from the Iter.Free[] list where an Inactive range overlaps | 558 // Remove registers from the Iter.Free[] list where an Inactive range overlaps |
563 // with the current range. | 559 // with the current range. |
564 void LinearScan::filterFreeWithInactiveRanges(IterationState &Iter) { | 560 void LinearScan::filterFreeWithInactiveRanges(IterationState &Iter) { |
565 for (const Variable *Item : Inactive) { | 561 for (const Variable *Item : Inactive) { |
566 if (!Item->rangeOverlaps(Iter.Cur)) | 562 if (!Item->rangeOverlaps(Iter.Cur)) |
567 continue; | 563 continue; |
568 const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; | 564 const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; |
569 // TODO(stichnot): Do this with bitvector ops, not a loop, for efficiency. | 565 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
570 for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; | 566 // Don't assert(Iter.Free[RegAlias]) because in theory (though probably |
571 RegAlias = Aliases.find_next(RegAlias)) { | |
572 // Don't assert(Iter.Free[RegNum]) because in theory (though probably | |
573 // never in practice) there could be two inactive variables that were | 567 // never in practice) there could be two inactive variables that were |
574 // marked with AllowOverlap. | 568 // marked with AllowOverlap. |
575 Iter.Free[RegAlias] = false; | 569 Iter.Free[RegAlias] = false; |
576 Iter.FreeUnfiltered[RegAlias] = false; | 570 Iter.FreeUnfiltered[RegAlias] = false; |
577 // Disable AllowOverlap if an Inactive variable, which is not Prefer, | 571 // Disable AllowOverlap if an Inactive variable, which is not Prefer, |
578 // shares Prefer's register, and has a definition within Cur's live range. | 572 // shares Prefer's register, and has a definition within Cur's live range. |
579 if (Iter.AllowOverlap && Item != Iter.Prefer && | 573 if (Iter.AllowOverlap && Item != Iter.Prefer && |
580 RegAlias == Iter.PreferReg && overlapsDefs(Func, Iter.Cur, Item)) { | 574 RegAlias == Iter.PreferReg && overlapsDefs(Func, Iter.Cur, Item)) { |
581 Iter.AllowOverlap = false; | 575 Iter.AllowOverlap = false; |
582 dumpDisableOverlap(Func, Item, "Inactive"); | 576 dumpDisableOverlap(Func, Item, "Inactive"); |
(...skipping 11 matching lines...) Expand all Loading... |
594 // TODO(stichnot): Partition UnhandledPrecolored according to register class, | 588 // TODO(stichnot): Partition UnhandledPrecolored according to register class, |
595 // to restrict the number of overlap comparisons needed. | 589 // to restrict the number of overlap comparisons needed. |
596 for (Variable *Item : reverse_range(UnhandledPrecolored)) { | 590 for (Variable *Item : reverse_range(UnhandledPrecolored)) { |
597 assert(Item->hasReg()); | 591 assert(Item->hasReg()); |
598 if (Iter.Cur->rangeEndsBefore(Item)) | 592 if (Iter.Cur->rangeEndsBefore(Item)) |
599 break; | 593 break; |
600 if (!Item->rangeOverlaps(Iter.Cur)) | 594 if (!Item->rangeOverlaps(Iter.Cur)) |
601 continue; | 595 continue; |
602 const llvm::SmallBitVector &Aliases = | 596 const llvm::SmallBitVector &Aliases = |
603 *RegAliases[Item->getRegNum()]; // Note: not getRegNumTmp() | 597 *RegAliases[Item->getRegNum()]; // Note: not getRegNumTmp() |
604 for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; | 598 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
605 RegAlias = Aliases.find_next(RegAlias)) { | |
606 Iter.Weights[RegAlias].setWeight(RegWeight::Inf); | 599 Iter.Weights[RegAlias].setWeight(RegWeight::Inf); |
607 Iter.Free[RegAlias] = false; | 600 Iter.Free[RegAlias] = false; |
608 Iter.FreeUnfiltered[RegAlias] = false; | 601 Iter.FreeUnfiltered[RegAlias] = false; |
609 Iter.PrecoloredUnhandledMask[RegAlias] = true; | 602 Iter.PrecoloredUnhandledMask[RegAlias] = true; |
610 // Disable Iter.AllowOverlap if the preferred register is one of these | 603 // Disable Iter.AllowOverlap if the preferred register is one of these |
611 // pre-colored unhandled overlapping ranges. | 604 // pre-colored unhandled overlapping ranges. |
612 if (Iter.AllowOverlap && RegAlias == Iter.PreferReg) { | 605 if (Iter.AllowOverlap && RegAlias == Iter.PreferReg) { |
613 Iter.AllowOverlap = false; | 606 Iter.AllowOverlap = false; |
614 dumpDisableOverlap(Func, Item, "PrecoloredUnhandled"); | 607 dumpDisableOverlap(Func, Item, "PrecoloredUnhandled"); |
615 } | 608 } |
616 } | 609 } |
617 } | 610 } |
618 } | 611 } |
619 | 612 |
620 void LinearScan::allocatePrecoloredRegister(Variable *Cur) { | 613 void LinearScan::allocatePrecoloredRegister(Variable *Cur) { |
621 int32_t RegNum = Cur->getRegNum(); | 614 const auto RegNum = Cur->getRegNum(); |
622 // RegNumTmp should have already been set above. | 615 // RegNumTmp should have already been set above. |
623 assert(Cur->getRegNumTmp() == RegNum); | 616 assert(Cur->getRegNumTmp() == RegNum); |
624 dumpLiveRangeTrace("Precoloring ", Cur); | 617 dumpLiveRangeTrace("Precoloring ", Cur); |
625 Active.push_back(Cur); | 618 Active.push_back(Cur); |
626 const llvm::SmallBitVector &Aliases = *RegAliases[RegNum]; | 619 const llvm::SmallBitVector &Aliases = *RegAliases[RegNum]; |
627 for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; | 620 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
628 RegAlias = Aliases.find_next(RegAlias)) { | |
629 assert(RegUses[RegAlias] >= 0); | 621 assert(RegUses[RegAlias] >= 0); |
630 ++RegUses[RegAlias]; | 622 ++RegUses[RegAlias]; |
631 } | 623 } |
632 assert(!UnhandledPrecolored.empty()); | 624 assert(!UnhandledPrecolored.empty()); |
633 assert(UnhandledPrecolored.back() == Cur); | 625 assert(UnhandledPrecolored.back() == Cur); |
634 UnhandledPrecolored.pop_back(); | 626 UnhandledPrecolored.pop_back(); |
635 } | 627 } |
636 | 628 |
637 void LinearScan::allocatePreferredRegister(IterationState &Iter) { | 629 void LinearScan::allocatePreferredRegister(IterationState &Iter) { |
638 Iter.Cur->setRegNumTmp(Iter.PreferReg); | 630 Iter.Cur->setRegNumTmp(Iter.PreferReg); |
639 dumpLiveRangeTrace("Preferring ", Iter.Cur); | 631 dumpLiveRangeTrace("Preferring ", Iter.Cur); |
640 const llvm::SmallBitVector &Aliases = *RegAliases[Iter.PreferReg]; | 632 const llvm::SmallBitVector &Aliases = *RegAliases[Iter.PreferReg]; |
641 for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; | 633 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
642 RegAlias = Aliases.find_next(RegAlias)) { | |
643 assert(RegUses[RegAlias] >= 0); | 634 assert(RegUses[RegAlias] >= 0); |
644 ++RegUses[RegAlias]; | 635 ++RegUses[RegAlias]; |
645 } | 636 } |
646 Active.push_back(Iter.Cur); | 637 Active.push_back(Iter.Cur); |
647 } | 638 } |
648 | 639 |
649 void LinearScan::allocateFreeRegister(IterationState &Iter, bool Filtered) { | 640 void LinearScan::allocateFreeRegister(IterationState &Iter, bool Filtered) { |
650 const int32_t RegNum = | 641 const RegNumT RegNum = |
651 Filtered ? Iter.Free.find_first() : Iter.FreeUnfiltered.find_first(); | 642 *RegNumBVIter(Filtered ? Iter.Free : Iter.FreeUnfiltered).begin(); |
652 Iter.Cur->setRegNumTmp(RegNum); | 643 Iter.Cur->setRegNumTmp(RegNum); |
653 if (Filtered) | 644 if (Filtered) |
654 dumpLiveRangeTrace("Allocating ", Iter.Cur); | 645 dumpLiveRangeTrace("Allocating ", Iter.Cur); |
655 else | 646 else |
656 dumpLiveRangeTrace("Allocating X ", Iter.Cur); | 647 dumpLiveRangeTrace("Allocating X ", Iter.Cur); |
657 const llvm::SmallBitVector &Aliases = *RegAliases[RegNum]; | 648 const llvm::SmallBitVector &Aliases = *RegAliases[RegNum]; |
658 for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; | 649 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
659 RegAlias = Aliases.find_next(RegAlias)) { | |
660 assert(RegUses[RegAlias] >= 0); | 650 assert(RegUses[RegAlias] >= 0); |
661 ++RegUses[RegAlias]; | 651 ++RegUses[RegAlias]; |
662 } | 652 } |
663 Active.push_back(Iter.Cur); | 653 Active.push_back(Iter.Cur); |
664 } | 654 } |
665 | 655 |
666 void LinearScan::handleNoFreeRegisters(IterationState &Iter) { | 656 void LinearScan::handleNoFreeRegisters(IterationState &Iter) { |
667 // Check Active ranges. | 657 // Check Active ranges. |
668 for (const Variable *Item : Active) { | 658 for (const Variable *Item : Active) { |
669 assert(Item->rangeOverlaps(Iter.Cur)); | 659 assert(Item->rangeOverlaps(Iter.Cur)); |
670 assert(Item->hasRegTmp()); | 660 assert(Item->hasRegTmp()); |
671 const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; | 661 const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; |
672 // We add the Item's weight to each alias/subregister to represent that, | 662 // We add the Item's weight to each alias/subregister to represent that, |
673 // should we decide to pick any of them, then we would incur that many | 663 // should we decide to pick any of them, then we would incur that many |
674 // memory accesses. | 664 // memory accesses. |
675 RegWeight W = Item->getWeight(Func); | 665 RegWeight W = Item->getWeight(Func); |
676 for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; | 666 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
677 RegAlias = Aliases.find_next(RegAlias)) { | |
678 Iter.Weights[RegAlias].addWeight(W); | 667 Iter.Weights[RegAlias].addWeight(W); |
679 } | 668 } |
680 } | 669 } |
681 // Same as above, but check Inactive ranges instead of Active. | 670 // Same as above, but check Inactive ranges instead of Active. |
682 for (const Variable *Item : Inactive) { | 671 for (const Variable *Item : Inactive) { |
683 if (!Item->rangeOverlaps(Iter.Cur)) | 672 if (!Item->rangeOverlaps(Iter.Cur)) |
684 continue; | 673 continue; |
685 assert(Item->hasRegTmp()); | 674 assert(Item->hasRegTmp()); |
686 const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; | 675 const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; |
687 RegWeight W = Item->getWeight(Func); | 676 RegWeight W = Item->getWeight(Func); |
688 for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; | 677 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
689 RegAlias = Aliases.find_next(RegAlias)) { | |
690 Iter.Weights[RegAlias].addWeight(W); | 678 Iter.Weights[RegAlias].addWeight(W); |
691 } | 679 } |
692 } | 680 } |
693 | 681 |
694 // All the weights are now calculated. Find the register with smallest weight. | 682 // All the weights are now calculated. Find the register with smallest weight. |
695 int32_t MinWeightIndex = findMinWeightIndex(Iter.RegMask, Iter.Weights); | 683 int32_t MinWeightIndex = findMinWeightIndex(Iter.RegMask, Iter.Weights); |
696 | 684 |
697 if (Iter.Cur->getWeight(Func) <= Iter.Weights[MinWeightIndex]) { | 685 if (Iter.Cur->getWeight(Func) <= Iter.Weights[MinWeightIndex]) { |
698 if (!Iter.Cur->mustHaveReg()) { | 686 if (!Iter.Cur->mustHaveReg()) { |
699 // Iter.Cur doesn't have priority over any other live ranges, so don't | 687 // Iter.Cur doesn't have priority over any other live ranges, so don't |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
735 // At this point, MinWeightIndex points to a valid reserve register to | 723 // At this point, MinWeightIndex points to a valid reserve register to |
736 // reallocate to Iter.Cur, so drop into the eviction code. | 724 // reallocate to Iter.Cur, so drop into the eviction code. |
737 } | 725 } |
738 | 726 |
739 // Evict all live ranges in Active that register number MinWeightIndex is | 727 // Evict all live ranges in Active that register number MinWeightIndex is |
740 // assigned to. | 728 // assigned to. |
741 const llvm::SmallBitVector &Aliases = *RegAliases[MinWeightIndex]; | 729 const llvm::SmallBitVector &Aliases = *RegAliases[MinWeightIndex]; |
742 for (SizeT I = Active.size(); I > 0; --I) { | 730 for (SizeT I = Active.size(); I > 0; --I) { |
743 const SizeT Index = I - 1; | 731 const SizeT Index = I - 1; |
744 Variable *Item = Active[Index]; | 732 Variable *Item = Active[Index]; |
745 int32_t RegNum = Item->getRegNumTmp(); | 733 const auto RegNum = Item->getRegNumTmp(); |
746 if (Aliases[RegNum]) { | 734 if (Aliases[RegNum]) { |
747 dumpLiveRangeTrace("Evicting A ", Item); | 735 dumpLiveRangeTrace("Evicting A ", Item); |
748 const llvm::SmallBitVector &Aliases = *RegAliases[RegNum]; | 736 const llvm::SmallBitVector &Aliases = *RegAliases[RegNum]; |
749 for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; | 737 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
750 RegAlias = Aliases.find_next(RegAlias)) { | |
751 --RegUses[RegAlias]; | 738 --RegUses[RegAlias]; |
752 assert(RegUses[RegAlias] >= 0); | 739 assert(RegUses[RegAlias] >= 0); |
753 } | 740 } |
754 Item->setRegNumTmp(Variable::NoRegister); | 741 Item->setRegNumTmp(RegNumT::NoRegister); |
755 moveItem(Active, Index, Handled); | 742 moveItem(Active, Index, Handled); |
756 Evicted.push_back(Item); | 743 Evicted.push_back(Item); |
757 } | 744 } |
758 } | 745 } |
759 // Do the same for Inactive. | 746 // Do the same for Inactive. |
760 for (SizeT I = Inactive.size(); I > 0; --I) { | 747 for (SizeT I = Inactive.size(); I > 0; --I) { |
761 const SizeT Index = I - 1; | 748 const SizeT Index = I - 1; |
762 Variable *Item = Inactive[Index]; | 749 Variable *Item = Inactive[Index]; |
763 // Note: The Item->rangeOverlaps(Cur) clause is not part of the description | 750 // Note: The Item->rangeOverlaps(Cur) clause is not part of the description |
764 // of AssignMemLoc() in the original paper. But there doesn't seem to be any | 751 // of AssignMemLoc() in the original paper. But there doesn't seem to be any |
765 // need to evict an inactive live range that doesn't overlap with the live | 752 // need to evict an inactive live range that doesn't overlap with the live |
766 // range currently being considered. It's especially bad if we would end up | 753 // range currently being considered. It's especially bad if we would end up |
767 // evicting an infinite-weight but currently-inactive live range. The most | 754 // evicting an infinite-weight but currently-inactive live range. The most |
768 // common situation for this would be a scratch register kill set for call | 755 // common situation for this would be a scratch register kill set for call |
769 // instructions. | 756 // instructions. |
770 if (Aliases[Item->getRegNumTmp()] && Item->rangeOverlaps(Iter.Cur)) { | 757 if (Aliases[Item->getRegNumTmp()] && Item->rangeOverlaps(Iter.Cur)) { |
771 dumpLiveRangeTrace("Evicting I ", Item); | 758 dumpLiveRangeTrace("Evicting I ", Item); |
772 Item->setRegNumTmp(Variable::NoRegister); | 759 Item->setRegNumTmp(RegNumT::NoRegister); |
773 moveItem(Inactive, Index, Handled); | 760 moveItem(Inactive, Index, Handled); |
774 Evicted.push_back(Item); | 761 Evicted.push_back(Item); |
775 } | 762 } |
776 } | 763 } |
777 // Assign the register to Cur. | 764 // Assign the register to Cur. |
778 Iter.Cur->setRegNumTmp(MinWeightIndex); | 765 Iter.Cur->setRegNumTmp(RegNumT::fromInt(MinWeightIndex)); |
779 for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; | 766 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
780 RegAlias = Aliases.find_next(RegAlias)) { | |
781 assert(RegUses[RegAlias] >= 0); | 767 assert(RegUses[RegAlias] >= 0); |
782 ++RegUses[RegAlias]; | 768 ++RegUses[RegAlias]; |
783 } | 769 } |
784 Active.push_back(Iter.Cur); | 770 Active.push_back(Iter.Cur); |
785 dumpLiveRangeTrace("Allocating ", Iter.Cur); | 771 dumpLiveRangeTrace("Allocating ", Iter.Cur); |
786 } | 772 } |
787 | 773 |
788 void LinearScan::assignFinalRegisters( | 774 void LinearScan::assignFinalRegisters( |
789 const llvm::SmallBitVector &RegMaskFull, | 775 const llvm::SmallBitVector &RegMaskFull, |
790 const llvm::SmallBitVector &PreDefinedRegisters, bool Randomized) { | 776 const llvm::SmallBitVector &PreDefinedRegisters, bool Randomized) { |
791 const size_t NumRegisters = RegMaskFull.size(); | 777 const size_t NumRegisters = RegMaskFull.size(); |
792 llvm::SmallVector<int32_t, REGS_SIZE> Permutation(NumRegisters); | 778 llvm::SmallVector<RegNumT, REGS_SIZE> Permutation(NumRegisters); |
793 if (Randomized) { | 779 if (Randomized) { |
794 // Create a random number generator for regalloc randomization. Merge | 780 // Create a random number generator for regalloc randomization. Merge |
795 // function's sequence and Kind value as the Salt. Because regAlloc() is | 781 // function's sequence and Kind value as the Salt. Because regAlloc() is |
796 // called twice under O2, the second time with RAK_Phi, we check Kind == | 782 // called twice under O2, the second time with RAK_Phi, we check Kind == |
797 // RAK_Phi to determine the lowest-order bit to make sure the Salt is | 783 // RAK_Phi to determine the lowest-order bit to make sure the Salt is |
798 // different. | 784 // different. |
799 uint64_t Salt = | 785 uint64_t Salt = |
800 (Func->getSequenceNumber() << 1) ^ (Kind == RAK_Phi ? 0u : 1u); | 786 (Func->getSequenceNumber() << 1) ^ (Kind == RAK_Phi ? 0u : 1u); |
801 Target->makeRandomRegisterPermutation( | 787 Target->makeRandomRegisterPermutation( |
802 Permutation, PreDefinedRegisters | ~RegMaskFull, Salt); | 788 Permutation, PreDefinedRegisters | ~RegMaskFull, Salt); |
803 } | 789 } |
804 | 790 |
805 // Finish up by setting RegNum = RegNumTmp (or a random permutation thereof) | 791 // Finish up by setting RegNum = RegNumTmp (or a random permutation thereof) |
806 // for each Variable. | 792 // for each Variable. |
807 for (Variable *Item : Handled) { | 793 for (Variable *Item : Handled) { |
808 int32_t RegNum = Item->getRegNumTmp(); | 794 const auto RegNum = Item->getRegNumTmp(); |
809 int32_t AssignedRegNum = RegNum; | 795 auto AssignedRegNum = RegNum; |
810 | 796 |
811 if (Randomized && Item->hasRegTmp() && !Item->hasReg()) { | 797 if (Randomized && Item->hasRegTmp() && !Item->hasReg()) { |
812 AssignedRegNum = Permutation[RegNum]; | 798 AssignedRegNum = Permutation[RegNum]; |
813 } | 799 } |
814 if (BuildDefs::dump() && Verbose) { | 800 if (BuildDefs::dump() && Verbose) { |
815 Ostream &Str = Ctx->getStrDump(); | 801 Ostream &Str = Ctx->getStrDump(); |
816 if (!Item->hasRegTmp()) { | 802 if (!Item->hasRegTmp()) { |
817 Str << "Not assigning "; | 803 Str << "Not assigning "; |
818 Item->dump(Func); | 804 Item->dump(Func); |
819 Str << "\n"; | 805 Str << "\n"; |
(...skipping 90 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
910 } | 896 } |
911 | 897 |
912 findRegisterPreference(Iter); | 898 findRegisterPreference(Iter); |
913 filterFreeWithInactiveRanges(Iter); | 899 filterFreeWithInactiveRanges(Iter); |
914 | 900 |
915 // Disable AllowOverlap if an Active variable, which is not Prefer, shares | 901 // Disable AllowOverlap if an Active variable, which is not Prefer, shares |
916 // Prefer's register, and has a definition within Cur's live range. | 902 // Prefer's register, and has a definition within Cur's live range. |
917 if (Iter.AllowOverlap) { | 903 if (Iter.AllowOverlap) { |
918 const llvm::SmallBitVector &Aliases = *RegAliases[Iter.PreferReg]; | 904 const llvm::SmallBitVector &Aliases = *RegAliases[Iter.PreferReg]; |
919 for (const Variable *Item : Active) { | 905 for (const Variable *Item : Active) { |
920 int32_t RegNum = Item->getRegNumTmp(); | 906 const RegNumT RegNum = Item->getRegNumTmp(); |
921 if (Item != Iter.Prefer && Aliases[RegNum] && | 907 if (Item != Iter.Prefer && Aliases[RegNum] && |
922 overlapsDefs(Func, Iter.Cur, Item)) { | 908 overlapsDefs(Func, Iter.Cur, Item)) { |
923 Iter.AllowOverlap = false; | 909 Iter.AllowOverlap = false; |
924 dumpDisableOverlap(Func, Item, "Active"); | 910 dumpDisableOverlap(Func, Item, "Active"); |
925 } | 911 } |
926 } | 912 } |
927 } | 913 } |
928 | 914 |
929 Iter.Weights.resize(Iter.RegMask.size()); | 915 Iter.Weights.resize(Iter.RegMask.size()); |
930 std::fill(Iter.Weights.begin(), Iter.Weights.end(), RegWeight()); | 916 std::fill(Iter.Weights.begin(), Iter.Weights.end(), RegWeight()); |
931 | 917 |
932 Iter.PrecoloredUnhandledMask.resize(Iter.RegMask.size()); | 918 Iter.PrecoloredUnhandledMask.resize(Iter.RegMask.size()); |
933 Iter.PrecoloredUnhandledMask.reset(); | 919 Iter.PrecoloredUnhandledMask.reset(); |
934 | 920 |
935 filterFreeWithPrecoloredRanges(Iter); | 921 filterFreeWithPrecoloredRanges(Iter); |
936 | 922 |
937 // Remove scratch registers from the Iter.Free[] list, and mark their | 923 // Remove scratch registers from the Iter.Free[] list, and mark their |
938 // Iter.Weights[] as infinite, if KillsRange overlaps Cur's live range. | 924 // Iter.Weights[] as infinite, if KillsRange overlaps Cur's live range. |
939 constexpr bool UseTrimmed = true; | 925 constexpr bool UseTrimmed = true; |
940 if (Iter.Cur->getLiveRange().overlaps(KillsRange, UseTrimmed)) { | 926 if (Iter.Cur->getLiveRange().overlaps(KillsRange, UseTrimmed)) { |
941 Iter.Free.reset(KillsMask); | 927 Iter.Free.reset(KillsMask); |
942 Iter.FreeUnfiltered.reset(KillsMask); | 928 Iter.FreeUnfiltered.reset(KillsMask); |
943 for (int i = KillsMask.find_first(); i != -1; | 929 for (RegNumT i : RegNumBVIter(KillsMask)) { |
944 i = KillsMask.find_next(i)) { | |
945 Iter.Weights[i].setWeight(RegWeight::Inf); | 930 Iter.Weights[i].setWeight(RegWeight::Inf); |
946 if (Iter.PreferReg == i) | 931 if (Iter.PreferReg == i) |
947 Iter.AllowOverlap = false; | 932 Iter.AllowOverlap = false; |
948 } | 933 } |
949 } | 934 } |
950 | 935 |
951 // Print info about physical register availability. | 936 // Print info about physical register availability. |
952 if (BuildDefs::dump() && Verbose) { | 937 if (BuildDefs::dump() && Verbose) { |
953 Ostream &Str = Ctx->getStrDump(); | 938 Ostream &Str = Ctx->getStrDump(); |
954 for (SizeT i = 0; i < Iter.RegMask.size(); ++i) { | 939 for (RegNumT i : RegNumBVIter(Iter.RegMaskUnfiltered)) { |
955 if (Iter.RegMaskUnfiltered[i]) { | 940 Str << Target->getRegName(i, Iter.Cur->getType()) << "(U=" << RegUses[i] |
956 Str << Target->getRegName(i, Iter.Cur->getType()) | 941 << ",F=" << Iter.Free[i] << ",P=" << Iter.PrecoloredUnhandledMask[i] |
957 << "(U=" << RegUses[i] << ",F=" << Iter.Free[i] | 942 << ") "; |
958 << ",P=" << Iter.PrecoloredUnhandledMask[i] << ") "; | |
959 } | |
960 } | 943 } |
961 Str << "\n"; | 944 Str << "\n"; |
962 } | 945 } |
963 | 946 |
964 if (Iter.Prefer && (Iter.AllowOverlap || Iter.Free[Iter.PreferReg])) { | 947 if (Iter.Prefer && (Iter.AllowOverlap || Iter.Free[Iter.PreferReg])) { |
965 // First choice: a preferred register that is either free or is allowed to | 948 // First choice: a preferred register that is either free or is allowed to |
966 // overlap with its linked variable. | 949 // overlap with its linked variable. |
967 allocatePreferredRegister(Iter); | 950 allocatePreferredRegister(Iter); |
968 } else if (Iter.Free.any()) { | 951 } else if (Iter.Free.any()) { |
969 // Second choice: any free register. | 952 // Second choice: any free register. |
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1028 Str << "\n"; | 1011 Str << "\n"; |
1029 } | 1012 } |
1030 Str << "++++++ Inactive:\n"; | 1013 Str << "++++++ Inactive:\n"; |
1031 for (const Variable *Item : Inactive) { | 1014 for (const Variable *Item : Inactive) { |
1032 dumpLiveRange(Item, Func); | 1015 dumpLiveRange(Item, Func); |
1033 Str << "\n"; | 1016 Str << "\n"; |
1034 } | 1017 } |
1035 } | 1018 } |
1036 | 1019 |
1037 } // end of namespace Ice | 1020 } // end of namespace Ice |
OLD | NEW |