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