Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(66)

Side by Side Diff: src/IceRegAlloc.cpp

Issue 1676123002: Subzero: Use a proper RegNumT type instead of int32_t/SizeT. (Closed) Base URL: https://chromium.googlesource.com/native_client/pnacl-subzero.git@master
Patch Set: Revert some method name changes Created 4 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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
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
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
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
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
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
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
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
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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698