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

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

Powered by Google App Engine
This is Rietveld 408576698