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 |
11 /// \brief Implements the LinearScan class, which performs the linear-scan | 11 /// \brief Implements the LinearScan class, which performs the linear-scan |
12 /// register allocation after liveness analysis has been performed. | 12 /// register allocation after liveness analysis has been performed. |
13 /// | 13 /// |
14 //===----------------------------------------------------------------------===// | 14 //===----------------------------------------------------------------------===// |
15 | 15 |
16 #include "IceRegAlloc.h" | 16 #include "IceRegAlloc.h" |
17 | 17 |
| 18 #include "IceBitVector.h" |
18 #include "IceCfg.h" | 19 #include "IceCfg.h" |
19 #include "IceCfgNode.h" | 20 #include "IceCfgNode.h" |
20 #include "IceInst.h" | 21 #include "IceInst.h" |
21 #include "IceInstVarIter.h" | 22 #include "IceInstVarIter.h" |
22 #include "IceOperand.h" | 23 #include "IceOperand.h" |
23 #include "IceTargetLowering.h" | 24 #include "IceTargetLowering.h" |
24 | 25 |
25 namespace Ice { | 26 namespace Ice { |
26 | 27 |
27 namespace { | 28 namespace { |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
71 Ostream &Str = Func->getContext()->getStrDump(); | 72 Ostream &Str = Func->getContext()->getStrDump(); |
72 char buf[30]; | 73 char buf[30]; |
73 snprintf(buf, llvm::array_lengthof(buf), "%2u", | 74 snprintf(buf, llvm::array_lengthof(buf), "%2u", |
74 unsigned(Var->getRegNumTmp())); | 75 unsigned(Var->getRegNumTmp())); |
75 Str << "R=" << buf << " V="; | 76 Str << "R=" << buf << " V="; |
76 Var->dump(Func); | 77 Var->dump(Func); |
77 Str << " Range=" << Var->getLiveRange(); | 78 Str << " Range=" << Var->getLiveRange(); |
78 } | 79 } |
79 | 80 |
80 int32_t findMinWeightIndex( | 81 int32_t findMinWeightIndex( |
81 const llvm::SmallBitVector &RegMask, | 82 const SmallBitVector &RegMask, |
82 const llvm::SmallVector<RegWeight, LinearScan::REGS_SIZE> &Weights) { | 83 const llvm::SmallVector<RegWeight, LinearScan::REGS_SIZE> &Weights) { |
83 int MinWeightIndex = -1; | 84 int MinWeightIndex = -1; |
84 for (RegNumT i : RegNumBVIter(RegMask)) { | 85 for (RegNumT i : RegNumBVIter(RegMask)) { |
85 if (MinWeightIndex < 0 || Weights[i] < Weights[MinWeightIndex]) | 86 if (MinWeightIndex < 0 || Weights[i] < Weights[MinWeightIndex]) |
86 MinWeightIndex = i; | 87 MinWeightIndex = i; |
87 } | 88 } |
88 assert(MinWeightIndex >= 0); | 89 assert(MinWeightIndex >= 0); |
89 return MinWeightIndex; | 90 return MinWeightIndex; |
90 } | 91 } |
91 | 92 |
(...skipping 314 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
406 SpillPoint = I; | 407 SpillPoint = I; |
407 if (I->getNumber() == End) | 408 if (I->getNumber() == End) |
408 FillPoint = I; | 409 FillPoint = I; |
409 if (SpillPoint != E) { | 410 if (SpillPoint != E) { |
410 // Remove from RegMask any physical registers referenced during Cur's live | 411 // 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 | 412 // range. Start looking after SpillPoint gets set, i.e. once Cur's live |
412 // range begins. | 413 // range begins. |
413 FOREACH_VAR_IN_INST(Var, *I) { | 414 FOREACH_VAR_IN_INST(Var, *I) { |
414 if (!Var->hasRegTmp()) | 415 if (!Var->hasRegTmp()) |
415 continue; | 416 continue; |
416 const llvm::SmallBitVector &Aliases = *RegAliases[Var->getRegNumTmp()]; | 417 const auto &Aliases = *RegAliases[Var->getRegNumTmp()]; |
417 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { | 418 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
418 Iter.RegMask[RegAlias] = false; | 419 Iter.RegMask[RegAlias] = false; |
419 } | 420 } |
420 } | 421 } |
421 } | 422 } |
422 } | 423 } |
423 assert(SpillPoint != Insts.end()); | 424 assert(SpillPoint != Insts.end()); |
424 assert(FillPoint != Insts.end()); | 425 assert(FillPoint != Insts.end()); |
425 ++FillPoint; | 426 ++FillPoint; |
426 // TODO(stichnot): Randomize instead of *.begin() which maps to find_first(). | 427 // TODO(stichnot): Randomize instead of *.begin() which maps to find_first(). |
(...skipping 24 matching lines...) Expand all Loading... |
451 Moved = true; | 452 Moved = true; |
452 } else if (!Item->rangeOverlapsStart(Cur)) { | 453 } else if (!Item->rangeOverlapsStart(Cur)) { |
453 // Move Item from Active to Inactive list. | 454 // Move Item from Active to Inactive list. |
454 dumpLiveRangeTrace("Inactivating ", Item); | 455 dumpLiveRangeTrace("Inactivating ", Item); |
455 moveItem(Active, Index, Inactive); | 456 moveItem(Active, Index, Inactive); |
456 Moved = true; | 457 Moved = true; |
457 } | 458 } |
458 if (Moved) { | 459 if (Moved) { |
459 // Decrement Item from RegUses[]. | 460 // Decrement Item from RegUses[]. |
460 assert(Item->hasRegTmp()); | 461 assert(Item->hasRegTmp()); |
461 const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; | 462 const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; |
462 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { | 463 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
463 --RegUses[RegAlias]; | 464 --RegUses[RegAlias]; |
464 assert(RegUses[RegAlias] >= 0); | 465 assert(RegUses[RegAlias] >= 0); |
465 } | 466 } |
466 } | 467 } |
467 } | 468 } |
468 } | 469 } |
469 | 470 |
470 void LinearScan::handleInactiveRangeExpiredOrReactivated(const Variable *Cur) { | 471 void LinearScan::handleInactiveRangeExpiredOrReactivated(const Variable *Cur) { |
471 for (SizeT I = Inactive.size(); I > 0; --I) { | 472 for (SizeT I = Inactive.size(); I > 0; --I) { |
472 const SizeT Index = I - 1; | 473 const SizeT Index = I - 1; |
473 Variable *Item = Inactive[Index]; | 474 Variable *Item = Inactive[Index]; |
474 Item->trimLiveRange(Cur->getLiveRange().getStart()); | 475 Item->trimLiveRange(Cur->getLiveRange().getStart()); |
475 if (Item->rangeEndsBefore(Cur)) { | 476 if (Item->rangeEndsBefore(Cur)) { |
476 // Move Item from Inactive to Handled list. | 477 // Move Item from Inactive to Handled list. |
477 dumpLiveRangeTrace("Expiring ", Item); | 478 dumpLiveRangeTrace("Expiring ", Item); |
478 moveItem(Inactive, Index, Handled); | 479 moveItem(Inactive, Index, Handled); |
479 } else if (Item->rangeOverlapsStart(Cur)) { | 480 } else if (Item->rangeOverlapsStart(Cur)) { |
480 // Move Item from Inactive to Active list. | 481 // Move Item from Inactive to Active list. |
481 dumpLiveRangeTrace("Reactivating ", Item); | 482 dumpLiveRangeTrace("Reactivating ", Item); |
482 moveItem(Inactive, Index, Active); | 483 moveItem(Inactive, Index, Active); |
483 // Increment Item in RegUses[]. | 484 // Increment Item in RegUses[]. |
484 assert(Item->hasRegTmp()); | 485 assert(Item->hasRegTmp()); |
485 const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; | 486 const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; |
486 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { | 487 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
487 assert(RegUses[RegAlias] >= 0); | 488 assert(RegUses[RegAlias] >= 0); |
488 ++RegUses[RegAlias]; | 489 ++RegUses[RegAlias]; |
489 } | 490 } |
490 } | 491 } |
491 } | 492 } |
492 } | 493 } |
493 | 494 |
494 // Infer register preference and allowable overlap. Only form a preference when | 495 // Infer register preference and allowable overlap. Only form a preference when |
495 // the current Variable has an unambiguous "first" definition. The preference is | 496 // the current Variable has an unambiguous "first" definition. The preference is |
(...skipping 21 matching lines...) Expand all Loading... |
517 const bool IsSingleDefAssign = | 518 const bool IsSingleDefAssign = |
518 DefInst->isVarAssign() && !VMetadata->isMultiDef(Iter.Cur); | 519 DefInst->isVarAssign() && !VMetadata->isMultiDef(Iter.Cur); |
519 FOREACH_VAR_IN_INST(SrcVar, *DefInst) { | 520 FOREACH_VAR_IN_INST(SrcVar, *DefInst) { |
520 // Only consider source variables that have (so far) been assigned a | 521 // Only consider source variables that have (so far) been assigned a |
521 // register. | 522 // register. |
522 if (!SrcVar->hasRegTmp()) | 523 if (!SrcVar->hasRegTmp()) |
523 continue; | 524 continue; |
524 | 525 |
525 // That register must be one in the RegMask set, e.g. don't try to prefer | 526 // That register must be one in the RegMask set, e.g. don't try to prefer |
526 // the stack pointer as a result of the stacksave intrinsic. | 527 // the stack pointer as a result of the stacksave intrinsic. |
527 const llvm::SmallBitVector &Aliases = *RegAliases[SrcVar->getRegNumTmp()]; | 528 const auto &Aliases = *RegAliases[SrcVar->getRegNumTmp()]; |
528 const int SrcReg = (Iter.RegMask & Aliases).find_first(); | 529 const int SrcReg = (Iter.RegMask & Aliases).find_first(); |
529 if (SrcReg == -1) | 530 if (SrcReg == -1) |
530 continue; | 531 continue; |
531 | 532 |
532 if (FindOverlap && IsSingleDefAssign && !Iter.Free[SrcReg]) { | 533 if (FindOverlap && IsSingleDefAssign && !Iter.Free[SrcReg]) { |
533 // Don't bother trying to enable AllowOverlap if the register is already | 534 // Don't bother trying to enable AllowOverlap if the register is already |
534 // free (hence the test on Iter.Free[SrcReg]). | 535 // free (hence the test on Iter.Free[SrcReg]). |
535 Iter.AllowOverlap = !overlapsDefs(Func, Iter.Cur, SrcVar); | 536 Iter.AllowOverlap = !overlapsDefs(Func, Iter.Cur, SrcVar); |
536 } | 537 } |
537 if (Iter.AllowOverlap || Iter.Free[SrcReg]) { | 538 if (Iter.AllowOverlap || Iter.Free[SrcReg]) { |
(...skipping 16 matching lines...) Expand all Loading... |
554 << " Overlap=" << Iter.AllowOverlap << "\n"; | 555 << " Overlap=" << Iter.AllowOverlap << "\n"; |
555 } | 556 } |
556 } | 557 } |
557 | 558 |
558 // Remove registers from the Iter.Free[] list where an Inactive range overlaps | 559 // Remove registers from the Iter.Free[] list where an Inactive range overlaps |
559 // with the current range. | 560 // with the current range. |
560 void LinearScan::filterFreeWithInactiveRanges(IterationState &Iter) { | 561 void LinearScan::filterFreeWithInactiveRanges(IterationState &Iter) { |
561 for (const Variable *Item : Inactive) { | 562 for (const Variable *Item : Inactive) { |
562 if (!Item->rangeOverlaps(Iter.Cur)) | 563 if (!Item->rangeOverlaps(Iter.Cur)) |
563 continue; | 564 continue; |
564 const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; | 565 const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; |
565 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { | 566 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
566 // Don't assert(Iter.Free[RegAlias]) because in theory (though probably | 567 // Don't assert(Iter.Free[RegAlias]) because in theory (though probably |
567 // never in practice) there could be two inactive variables that were | 568 // never in practice) there could be two inactive variables that were |
568 // marked with AllowOverlap. | 569 // marked with AllowOverlap. |
569 Iter.Free[RegAlias] = false; | 570 Iter.Free[RegAlias] = false; |
570 Iter.FreeUnfiltered[RegAlias] = false; | 571 Iter.FreeUnfiltered[RegAlias] = false; |
571 // Disable AllowOverlap if an Inactive variable, which is not Prefer, | 572 // Disable AllowOverlap if an Inactive variable, which is not Prefer, |
572 // shares Prefer's register, and has a definition within Cur's live range. | 573 // shares Prefer's register, and has a definition within Cur's live range. |
573 if (Iter.AllowOverlap && Item != Iter.Prefer && | 574 if (Iter.AllowOverlap && Item != Iter.Prefer && |
574 RegAlias == Iter.PreferReg && overlapsDefs(Func, Iter.Cur, Item)) { | 575 RegAlias == Iter.PreferReg && overlapsDefs(Func, Iter.Cur, Item)) { |
(...skipping 11 matching lines...) Expand all Loading... |
586 // O(N^2) algorithm into expected linear complexity. | 587 // O(N^2) algorithm into expected linear complexity. |
587 void LinearScan::filterFreeWithPrecoloredRanges(IterationState &Iter) { | 588 void LinearScan::filterFreeWithPrecoloredRanges(IterationState &Iter) { |
588 // TODO(stichnot): Partition UnhandledPrecolored according to register class, | 589 // TODO(stichnot): Partition UnhandledPrecolored according to register class, |
589 // to restrict the number of overlap comparisons needed. | 590 // to restrict the number of overlap comparisons needed. |
590 for (Variable *Item : reverse_range(UnhandledPrecolored)) { | 591 for (Variable *Item : reverse_range(UnhandledPrecolored)) { |
591 assert(Item->hasReg()); | 592 assert(Item->hasReg()); |
592 if (Iter.Cur->rangeEndsBefore(Item)) | 593 if (Iter.Cur->rangeEndsBefore(Item)) |
593 break; | 594 break; |
594 if (!Item->rangeOverlaps(Iter.Cur)) | 595 if (!Item->rangeOverlaps(Iter.Cur)) |
595 continue; | 596 continue; |
596 const llvm::SmallBitVector &Aliases = | 597 const auto &Aliases = |
597 *RegAliases[Item->getRegNum()]; // Note: not getRegNumTmp() | 598 *RegAliases[Item->getRegNum()]; // Note: not getRegNumTmp() |
598 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { | 599 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
599 Iter.Weights[RegAlias].setWeight(RegWeight::Inf); | 600 Iter.Weights[RegAlias].setWeight(RegWeight::Inf); |
600 Iter.Free[RegAlias] = false; | 601 Iter.Free[RegAlias] = false; |
601 Iter.FreeUnfiltered[RegAlias] = false; | 602 Iter.FreeUnfiltered[RegAlias] = false; |
602 Iter.PrecoloredUnhandledMask[RegAlias] = true; | 603 Iter.PrecoloredUnhandledMask[RegAlias] = true; |
603 // Disable Iter.AllowOverlap if the preferred register is one of these | 604 // Disable Iter.AllowOverlap if the preferred register is one of these |
604 // pre-colored unhandled overlapping ranges. | 605 // pre-colored unhandled overlapping ranges. |
605 if (Iter.AllowOverlap && RegAlias == Iter.PreferReg) { | 606 if (Iter.AllowOverlap && RegAlias == Iter.PreferReg) { |
606 Iter.AllowOverlap = false; | 607 Iter.AllowOverlap = false; |
607 dumpDisableOverlap(Func, Item, "PrecoloredUnhandled"); | 608 dumpDisableOverlap(Func, Item, "PrecoloredUnhandled"); |
608 } | 609 } |
609 } | 610 } |
610 } | 611 } |
611 } | 612 } |
612 | 613 |
613 void LinearScan::allocatePrecoloredRegister(Variable *Cur) { | 614 void LinearScan::allocatePrecoloredRegister(Variable *Cur) { |
614 const auto RegNum = Cur->getRegNum(); | 615 const auto RegNum = Cur->getRegNum(); |
615 // RegNumTmp should have already been set above. | 616 // RegNumTmp should have already been set above. |
616 assert(Cur->getRegNumTmp() == RegNum); | 617 assert(Cur->getRegNumTmp() == RegNum); |
617 dumpLiveRangeTrace("Precoloring ", Cur); | 618 dumpLiveRangeTrace("Precoloring ", Cur); |
618 Active.push_back(Cur); | 619 Active.push_back(Cur); |
619 const llvm::SmallBitVector &Aliases = *RegAliases[RegNum]; | 620 const auto &Aliases = *RegAliases[RegNum]; |
620 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { | 621 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
621 assert(RegUses[RegAlias] >= 0); | 622 assert(RegUses[RegAlias] >= 0); |
622 ++RegUses[RegAlias]; | 623 ++RegUses[RegAlias]; |
623 } | 624 } |
624 assert(!UnhandledPrecolored.empty()); | 625 assert(!UnhandledPrecolored.empty()); |
625 assert(UnhandledPrecolored.back() == Cur); | 626 assert(UnhandledPrecolored.back() == Cur); |
626 UnhandledPrecolored.pop_back(); | 627 UnhandledPrecolored.pop_back(); |
627 } | 628 } |
628 | 629 |
629 void LinearScan::allocatePreferredRegister(IterationState &Iter) { | 630 void LinearScan::allocatePreferredRegister(IterationState &Iter) { |
630 Iter.Cur->setRegNumTmp(Iter.PreferReg); | 631 Iter.Cur->setRegNumTmp(Iter.PreferReg); |
631 dumpLiveRangeTrace("Preferring ", Iter.Cur); | 632 dumpLiveRangeTrace("Preferring ", Iter.Cur); |
632 const llvm::SmallBitVector &Aliases = *RegAliases[Iter.PreferReg]; | 633 const auto &Aliases = *RegAliases[Iter.PreferReg]; |
633 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { | 634 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
634 assert(RegUses[RegAlias] >= 0); | 635 assert(RegUses[RegAlias] >= 0); |
635 ++RegUses[RegAlias]; | 636 ++RegUses[RegAlias]; |
636 } | 637 } |
637 Active.push_back(Iter.Cur); | 638 Active.push_back(Iter.Cur); |
638 } | 639 } |
639 | 640 |
640 void LinearScan::allocateFreeRegister(IterationState &Iter, bool Filtered) { | 641 void LinearScan::allocateFreeRegister(IterationState &Iter, bool Filtered) { |
641 const RegNumT RegNum = | 642 const RegNumT RegNum = |
642 *RegNumBVIter(Filtered ? Iter.Free : Iter.FreeUnfiltered).begin(); | 643 *RegNumBVIter(Filtered ? Iter.Free : Iter.FreeUnfiltered).begin(); |
643 Iter.Cur->setRegNumTmp(RegNum); | 644 Iter.Cur->setRegNumTmp(RegNum); |
644 if (Filtered) | 645 if (Filtered) |
645 dumpLiveRangeTrace("Allocating Y ", Iter.Cur); | 646 dumpLiveRangeTrace("Allocating Y ", Iter.Cur); |
646 else | 647 else |
647 dumpLiveRangeTrace("Allocating X ", Iter.Cur); | 648 dumpLiveRangeTrace("Allocating X ", Iter.Cur); |
648 const llvm::SmallBitVector &Aliases = *RegAliases[RegNum]; | 649 const auto &Aliases = *RegAliases[RegNum]; |
649 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { | 650 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
650 assert(RegUses[RegAlias] >= 0); | 651 assert(RegUses[RegAlias] >= 0); |
651 ++RegUses[RegAlias]; | 652 ++RegUses[RegAlias]; |
652 } | 653 } |
653 Active.push_back(Iter.Cur); | 654 Active.push_back(Iter.Cur); |
654 } | 655 } |
655 | 656 |
656 void LinearScan::handleNoFreeRegisters(IterationState &Iter) { | 657 void LinearScan::handleNoFreeRegisters(IterationState &Iter) { |
657 // Check Active ranges. | 658 // Check Active ranges. |
658 for (const Variable *Item : Active) { | 659 for (const Variable *Item : Active) { |
659 assert(Item->rangeOverlaps(Iter.Cur)); | 660 assert(Item->rangeOverlaps(Iter.Cur)); |
660 assert(Item->hasRegTmp()); | 661 assert(Item->hasRegTmp()); |
661 const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; | 662 const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; |
662 // We add the Item's weight to each alias/subregister to represent that, | 663 // We add the Item's weight to each alias/subregister to represent that, |
663 // should we decide to pick any of them, then we would incur that many | 664 // should we decide to pick any of them, then we would incur that many |
664 // memory accesses. | 665 // memory accesses. |
665 RegWeight W = Item->getWeight(Func); | 666 RegWeight W = Item->getWeight(Func); |
666 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { | 667 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
667 Iter.Weights[RegAlias].addWeight(W); | 668 Iter.Weights[RegAlias].addWeight(W); |
668 } | 669 } |
669 } | 670 } |
670 // Same as above, but check Inactive ranges instead of Active. | 671 // Same as above, but check Inactive ranges instead of Active. |
671 for (const Variable *Item : Inactive) { | 672 for (const Variable *Item : Inactive) { |
672 if (!Item->rangeOverlaps(Iter.Cur)) | 673 if (!Item->rangeOverlaps(Iter.Cur)) |
673 continue; | 674 continue; |
674 assert(Item->hasRegTmp()); | 675 assert(Item->hasRegTmp()); |
675 const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; | 676 const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; |
676 RegWeight W = Item->getWeight(Func); | 677 RegWeight W = Item->getWeight(Func); |
677 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { | 678 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
678 Iter.Weights[RegAlias].addWeight(W); | 679 Iter.Weights[RegAlias].addWeight(W); |
679 } | 680 } |
680 } | 681 } |
681 | 682 |
682 // All the weights are now calculated. Find the register with smallest weight. | 683 // All the weights are now calculated. Find the register with smallest weight. |
683 int32_t MinWeightIndex = findMinWeightIndex(Iter.RegMask, Iter.Weights); | 684 int32_t MinWeightIndex = findMinWeightIndex(Iter.RegMask, Iter.Weights); |
684 | 685 |
685 if (Iter.Cur->getWeight(Func) <= Iter.Weights[MinWeightIndex]) { | 686 if (Iter.Cur->getWeight(Func) <= Iter.Weights[MinWeightIndex]) { |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
719 Iter.Cur->getName(Func)); | 720 Iter.Cur->getName(Func)); |
720 Handled.push_back(Iter.Cur); | 721 Handled.push_back(Iter.Cur); |
721 return; | 722 return; |
722 } | 723 } |
723 // At this point, MinWeightIndex points to a valid reserve register to | 724 // At this point, MinWeightIndex points to a valid reserve register to |
724 // reallocate to Iter.Cur, so drop into the eviction code. | 725 // reallocate to Iter.Cur, so drop into the eviction code. |
725 } | 726 } |
726 | 727 |
727 // Evict all live ranges in Active that register number MinWeightIndex is | 728 // Evict all live ranges in Active that register number MinWeightIndex is |
728 // assigned to. | 729 // assigned to. |
729 const llvm::SmallBitVector &Aliases = *RegAliases[MinWeightIndex]; | 730 const auto &Aliases = *RegAliases[MinWeightIndex]; |
730 for (SizeT I = Active.size(); I > 0; --I) { | 731 for (SizeT I = Active.size(); I > 0; --I) { |
731 const SizeT Index = I - 1; | 732 const SizeT Index = I - 1; |
732 Variable *Item = Active[Index]; | 733 Variable *Item = Active[Index]; |
733 const auto RegNum = Item->getRegNumTmp(); | 734 const auto RegNum = Item->getRegNumTmp(); |
734 if (Aliases[RegNum]) { | 735 if (Aliases[RegNum]) { |
735 dumpLiveRangeTrace("Evicting A ", Item); | 736 dumpLiveRangeTrace("Evicting A ", Item); |
736 const llvm::SmallBitVector &Aliases = *RegAliases[RegNum]; | 737 const auto &Aliases = *RegAliases[RegNum]; |
737 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { | 738 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
738 --RegUses[RegAlias]; | 739 --RegUses[RegAlias]; |
739 assert(RegUses[RegAlias] >= 0); | 740 assert(RegUses[RegAlias] >= 0); |
740 } | 741 } |
741 Item->setRegNumTmp(RegNumT()); | 742 Item->setRegNumTmp(RegNumT()); |
742 moveItem(Active, Index, Handled); | 743 moveItem(Active, Index, Handled); |
743 Evicted.push_back(Item); | 744 Evicted.push_back(Item); |
744 } | 745 } |
745 } | 746 } |
746 // Do the same for Inactive. | 747 // Do the same for Inactive. |
(...skipping 17 matching lines...) Expand all Loading... |
764 // Assign the register to Cur. | 765 // Assign the register to Cur. |
765 Iter.Cur->setRegNumTmp(RegNumT::fromInt(MinWeightIndex)); | 766 Iter.Cur->setRegNumTmp(RegNumT::fromInt(MinWeightIndex)); |
766 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { | 767 for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
767 assert(RegUses[RegAlias] >= 0); | 768 assert(RegUses[RegAlias] >= 0); |
768 ++RegUses[RegAlias]; | 769 ++RegUses[RegAlias]; |
769 } | 770 } |
770 Active.push_back(Iter.Cur); | 771 Active.push_back(Iter.Cur); |
771 dumpLiveRangeTrace("Allocating Z ", Iter.Cur); | 772 dumpLiveRangeTrace("Allocating Z ", Iter.Cur); |
772 } | 773 } |
773 | 774 |
774 void LinearScan::assignFinalRegisters( | 775 void LinearScan::assignFinalRegisters(const SmallBitVector &RegMaskFull, |
775 const llvm::SmallBitVector &RegMaskFull, | 776 const SmallBitVector &PreDefinedRegisters, |
776 const llvm::SmallBitVector &PreDefinedRegisters, bool Randomized) { | 777 bool Randomized) { |
777 const size_t NumRegisters = RegMaskFull.size(); | 778 const size_t NumRegisters = RegMaskFull.size(); |
778 llvm::SmallVector<RegNumT, REGS_SIZE> Permutation(NumRegisters); | 779 llvm::SmallVector<RegNumT, REGS_SIZE> Permutation(NumRegisters); |
779 if (Randomized) { | 780 if (Randomized) { |
780 // Create a random number generator for regalloc randomization. Merge | 781 // Create a random number generator for regalloc randomization. Merge |
781 // function's sequence and Kind value as the Salt. Because regAlloc() is | 782 // function's sequence and Kind value as the Salt. Because regAlloc() is |
782 // called twice under O2, the second time with RAK_Phi, we check Kind == | 783 // called twice under O2, the second time with RAK_Phi, we check Kind == |
783 // RAK_Phi to determine the lowest-order bit to make sure the Salt is | 784 // RAK_Phi to determine the lowest-order bit to make sure the Salt is |
784 // different. | 785 // different. |
785 uint64_t Salt = | 786 uint64_t Salt = |
786 (Func->getSequenceNumber() << 1) ^ (Kind == RAK_Phi ? 0u : 1u); | 787 (Func->getSequenceNumber() << 1) ^ (Kind == RAK_Phi ? 0u : 1u); |
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
818 | 819 |
819 // Implements the linear-scan algorithm. Based on "Linear Scan Register | 820 // Implements the linear-scan algorithm. Based on "Linear Scan Register |
820 // Allocation in the Context of SSA Form and Register Constraints" by Hanspeter | 821 // Allocation in the Context of SSA Form and Register Constraints" by Hanspeter |
821 // Mössenböck and Michael Pfeiffer, | 822 // Mössenböck and Michael Pfeiffer, |
822 // ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF. This implementation is | 823 // ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF. This implementation is |
823 // modified to take affinity into account and allow two interfering variables to | 824 // modified to take affinity into account and allow two interfering variables to |
824 // share the same register in certain cases. | 825 // share the same register in certain cases. |
825 // | 826 // |
826 // Requires running Cfg::liveness(Liveness_Intervals) in preparation. Results | 827 // Requires running Cfg::liveness(Liveness_Intervals) in preparation. Results |
827 // are assigned to Variable::RegNum for each Variable. | 828 // are assigned to Variable::RegNum for each Variable. |
828 void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull, | 829 void LinearScan::scan(const SmallBitVector &RegMaskFull, bool Randomized) { |
829 bool Randomized) { | |
830 TimerMarker T(TimerStack::TT_linearScan, Func); | 830 TimerMarker T(TimerStack::TT_linearScan, Func); |
831 assert(RegMaskFull.any()); // Sanity check | 831 assert(RegMaskFull.any()); // Sanity check |
832 if (Verbose) | 832 if (Verbose) |
833 Ctx->lockStr(); | 833 Ctx->lockStr(); |
834 Func->resetCurrentNode(); | 834 Func->resetCurrentNode(); |
835 const size_t NumRegisters = RegMaskFull.size(); | 835 const size_t NumRegisters = RegMaskFull.size(); |
836 llvm::SmallBitVector PreDefinedRegisters(NumRegisters); | 836 SmallBitVector PreDefinedRegisters(NumRegisters); |
837 if (Randomized) { | 837 if (Randomized) { |
838 for (Variable *Var : UnhandledPrecolored) { | 838 for (Variable *Var : UnhandledPrecolored) { |
839 PreDefinedRegisters[Var->getRegNum()] = true; | 839 PreDefinedRegisters[Var->getRegNum()] = true; |
840 } | 840 } |
841 } | 841 } |
842 | 842 |
843 // Build a LiveRange representing the Kills list. | 843 // Build a LiveRange representing the Kills list. |
844 LiveRange KillsRange(Kills); | 844 LiveRange KillsRange(Kills); |
845 KillsRange.untrim(); | 845 KillsRange.untrim(); |
846 | 846 |
847 // Reset the register use count. | 847 // Reset the register use count. |
848 RegUses.resize(NumRegisters); | 848 RegUses.resize(NumRegisters); |
849 std::fill(RegUses.begin(), RegUses.end(), 0); | 849 std::fill(RegUses.begin(), RegUses.end(), 0); |
850 | 850 |
851 // Unhandled is already set to all ranges in increasing order of start points. | 851 // Unhandled is already set to all ranges in increasing order of start points. |
852 assert(Active.empty()); | 852 assert(Active.empty()); |
853 assert(Inactive.empty()); | 853 assert(Inactive.empty()); |
854 assert(Handled.empty()); | 854 assert(Handled.empty()); |
855 const TargetLowering::RegSetMask RegsInclude = | 855 const TargetLowering::RegSetMask RegsInclude = |
856 TargetLowering::RegSet_CallerSave; | 856 TargetLowering::RegSet_CallerSave; |
857 const TargetLowering::RegSetMask RegsExclude = TargetLowering::RegSet_None; | 857 const TargetLowering::RegSetMask RegsExclude = TargetLowering::RegSet_None; |
858 const llvm::SmallBitVector KillsMask = | 858 const SmallBitVector KillsMask = |
859 Target->getRegisterSet(RegsInclude, RegsExclude); | 859 Target->getRegisterSet(RegsInclude, RegsExclude); |
860 | 860 |
861 // Allocate memory once outside the loop. | 861 // Allocate memory once outside the loop. |
862 IterationState Iter; | 862 IterationState Iter; |
863 Iter.Weights.reserve(NumRegisters); | 863 Iter.Weights.reserve(NumRegisters); |
864 Iter.PrecoloredUnhandledMask.reserve(NumRegisters); | 864 Iter.PrecoloredUnhandledMask.reserve(NumRegisters); |
865 | 865 |
866 while (!Unhandled.empty()) { | 866 while (!Unhandled.empty()) { |
867 Iter.Cur = Unhandled.back(); | 867 Iter.Cur = Unhandled.back(); |
868 Unhandled.pop_back(); | 868 Unhandled.pop_back(); |
(...skipping 25 matching lines...) Expand all Loading... |
894 Iter.FreeUnfiltered[i] = false; | 894 Iter.FreeUnfiltered[i] = false; |
895 } | 895 } |
896 } | 896 } |
897 | 897 |
898 findRegisterPreference(Iter); | 898 findRegisterPreference(Iter); |
899 filterFreeWithInactiveRanges(Iter); | 899 filterFreeWithInactiveRanges(Iter); |
900 | 900 |
901 // Disable AllowOverlap if an Active variable, which is not Prefer, shares | 901 // Disable AllowOverlap if an Active variable, which is not Prefer, shares |
902 // 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. |
903 if (Iter.AllowOverlap) { | 903 if (Iter.AllowOverlap) { |
904 const llvm::SmallBitVector &Aliases = *RegAliases[Iter.PreferReg]; | 904 const auto &Aliases = *RegAliases[Iter.PreferReg]; |
905 for (const Variable *Item : Active) { | 905 for (const Variable *Item : Active) { |
906 const RegNumT RegNum = Item->getRegNumTmp(); | 906 const RegNumT RegNum = Item->getRegNumTmp(); |
907 if (Item != Iter.Prefer && Aliases[RegNum] && | 907 if (Item != Iter.Prefer && Aliases[RegNum] && |
908 overlapsDefs(Func, Iter.Cur, Item)) { | 908 overlapsDefs(Func, Iter.Cur, Item)) { |
909 Iter.AllowOverlap = false; | 909 Iter.AllowOverlap = false; |
910 dumpDisableOverlap(Func, Item, "Active"); | 910 dumpDisableOverlap(Func, Item, "Active"); |
911 } | 911 } |
912 } | 912 } |
913 } | 913 } |
914 | 914 |
(...skipping 96 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1011 Str << "\n"; | 1011 Str << "\n"; |
1012 } | 1012 } |
1013 Str << "++++++ Inactive:\n"; | 1013 Str << "++++++ Inactive:\n"; |
1014 for (const Variable *Item : Inactive) { | 1014 for (const Variable *Item : Inactive) { |
1015 dumpLiveRange(Item, Func); | 1015 dumpLiveRange(Item, Func); |
1016 Str << "\n"; | 1016 Str << "\n"; |
1017 } | 1017 } |
1018 } | 1018 } |
1019 | 1019 |
1020 } // end of namespace Ice | 1020 } // end of namespace Ice |
OLD | NEW |