RegAllocGreedy.cpp Source File (original) (raw)

72#include

73#include

74#include

75#include

77using namespace llvm;

79#define DEBUG_TYPE "regalloc"

81 STATISTIC(NumGlobalSplits, "Number of split global live ranges");

82 STATISTIC(NumLocalSplits, "Number of split local live ranges");

83 STATISTIC(NumEvicted, "Number of interferences evicted");

87 cl::desc("Spill mode for splitting live ranges"),

95 cl::desc("Last chance recoloring max depth"),

100 cl::desc("Last chance recoloring maximum number of considered"

101 " interference at a time"),

103

106 cl::desc("Exhaustive Search for registers bypassing the depth "

107 "and interference cutoffs of last chance recoloring"),

109

110

113 cl::desc("Cost for first time use of callee-saved register."),

115

117 "grow-region-complexity-budget",

118 cl::desc("growRegion() does not scale with the number of BB edges, so "

119 "limit its budget and bail out once we reach the limit."),

121

123 "greedy-regclass-priority-trumps-globalness",

124 cl::desc("Change the greedy register allocator's live range priority "

125 "calculation to make the AllocationPriority of the register class "

126 "more important then whether the range is global"),

128

130 "greedy-reverse-local-assignment",

131 cl::desc("Reverse allocation order of local live ranges, such that "

132 "shorter local live ranges will tend to be allocated first"),

134

136 "split-threshold-for-reg-with-hint",

137 cl::desc("The threshold for splitting a virtual register with a hint, in "

138 "percentage"),

140

143

144namespace {

147

148public:

150

151 static char ID;

152

153 StringRef getPassName() const override { return "Greedy Register Allocator"; }

154

155

156 void getAnalysisUsage(AnalysisUsage &AU) const override;

157

158 bool runOnMachineFunction(MachineFunction &mf) override;

159

160 MachineFunctionProperties getRequiredProperties() const override {

161 return MachineFunctionProperties().setNoPHIs();

162 }

163

164 MachineFunctionProperties getClearedProperties() const override {

165 return MachineFunctionProperties().setIsSSA();

166 }

167};

168

169}

170

174}

175

199

205 Indexes = Analyses.Indexes;

206 MBFI = Analyses.MBFI;

207 DomTree = Analyses.DomTree;

208 Loops = Analyses.Loops;

209 ORE = Analyses.ORE;

210 Bundles = Analyses.Bundles;

213 LSS = Analyses.LSS;

216}

217

221 StringRef FilterName = Opts.FilterName.empty() ? "all" : Opts.FilterName;

222 OS << "greedy<" << FilterName << '>';

223}

224

243

247

249 RAGreedy Impl(Analyses, Opts.Filter);

250

251 bool Changed = Impl.run(MF);

263 return PA;

264}

265

284

285bool RAGreedyLegacy::runOnMachineFunction(MachineFunction &MF) {

288 return Impl.run(MF);

289}

290

291char RAGreedyLegacy::ID = 0;

293

295 false, false)

313

314#ifndef NDEBUG

315const char *const RAGreedy::StageName[] = {

316 "RS_New",

317 "RS_Assign",

318 "RS_Split",

319 "RS_Split2",

320 "RS_Spill",

321 "RS_Done"

322};

323#endif

324

325

326

327const float Hysteresis = (2007 / 2048.0f);

328

330 return new RAGreedyLegacy();

331}

332

334 return new RAGreedyLegacy(Ftor);

335}

336

337void RAGreedyLegacy::getAnalysisUsage(AnalysisUsage &AU) const {

363}

364

365

366

367

368

369bool RAGreedy::LRE_CanEraseVirtReg(Register VirtReg) {

370 LiveInterval &LI = LIS->getInterval(VirtReg);

371 if (VRM->hasPhys(VirtReg)) {

372 Matrix->unassign(LI);

374 return true;

375 }

376

377

378

379

381 return false;

382}

383

384void RAGreedy::LRE_WillShrinkVirtReg(Register VirtReg) {

385 if ( VRM ->hasPhys(VirtReg))

386 return;

387

388

389 LiveInterval &LI = LIS->getInterval(VirtReg);

390 Matrix->unassign(LI);

392}

393

394void RAGreedy::LRE_DidCloneVirtReg(Register New, Register Old) {

395 ExtraInfo->LRE_DidCloneVirtReg(New, Old);

396}

397

399

400 if (!Info.inBounds(Old))

401 return;

402

403

404

405

406

408 Info.grow(New.id());

409 Info[New] = Info[Old];

410}

411

413 SpillerInstance.reset();

414 GlobalCand.clear();

415}

416

418

419void RAGreedy::enqueue(PQueue &CurQueue, const LiveInterval *LI) {

420

421

423 assert(Reg.isVirtual() && "Can only enqueue virtual registers");

424

425 auto Stage = ExtraInfo->getOrInitStage(Reg);

426 if (Stage == RS_New) {

428 ExtraInfo->setStage(Reg, Stage);

429 }

430

431 unsigned Ret = PriorityAdvisor->getPriority(*LI);

432

433

434

435 CurQueue.push(std::make_pair(Ret, ~Reg.id()));

436}

437

438unsigned DefaultPriorityAdvisor::getPriority(const LiveInterval &LI) const {

441 unsigned Prio;

443

445

446

448 } else {

449

450

451 const TargetRegisterClass &RC = *MRI->getRegClass(Reg);

453 (!ReverseLocalAssignment &&

455 (2 * RegClassInfo.getNumAllocatableRegs(&RC)));

456 unsigned GlobalBit = 0;

457

458 if (Stage == RS_Assign && !ForceGlobal && !LI.empty() &&

459 LIS->intervalIsInOneMBB(LI)) {

460

461

462

463 if (!ReverseLocalAssignment)

465 else {

466

467

468

469 Prio = Indexes->getZeroIndex().getApproxInstrDistance(LI.endIndex());

470 }

471 } else {

472

473

474

476 GlobalBit = 1;

477 }

478

479

480

481

482

483

484

485

486

487

488

489

490

491 Prio = std::min(Prio, (unsigned)maxUIntN(24));

493

494 if (RegClassPriorityTrumpsGlobalness)

496 else

498

499

500 Prio |= (1u << 31);

501

502

503 if (VRM->hasKnownPreference(Reg))

504 Prio |= (1u << 30);

505 }

506

507 return Prio;

508}

509

510unsigned DummyPriorityAdvisor::getPriority(const LiveInterval &LI) const {

511

514}

515

517

519 if (CurQueue.empty())

520 return nullptr;

522 CurQueue.pop();

523 return LI;

524}

525

526

527

528

529

530

536 for (auto I = Order.begin(), E = Order.end(); I != E && !PhysReg; ++I) {

538 if ( Matrix ->checkInterference(VirtReg, *I)) {

539 if (I.isHint())

540 return *I;

541 else

542 PhysReg = *I;

543 }

544 }

546 return PhysReg;

547

548

549

550

551

552 if (Register Hint = MRI->getSimpleHint(VirtReg.reg()))

553 if (Order.isHint(Hint)) {

554 MCRegister PhysHint = Hint.asMCReg();

556

557 if (EvictAdvisor->canEvictHintInterference(VirtReg, PhysHint,

558 FixedRegisters)) {

559 evictInterference(VirtReg, PhysHint, NewVRegs);

560 return PhysHint;

561 }

562

563

564 if (trySplitAroundHintReg(PhysHint, VirtReg, NewVRegs, Order))

565 return MCRegister();

566

567

568

569 SetOfBrokenHints.insert(&VirtReg);

570 }

571

572

573 uint8_t Cost = RegCosts[PhysReg.id()];

574

575

577 return PhysReg;

578

580 << (unsigned)Cost << '\n');

581 MCRegister CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost, FixedRegisters);

582 return CheapReg ? CheapReg : PhysReg;

583}

584

585

586

587

588

591 auto HasRegUnitInterference = [&](MCRegUnit Unit) {

592

594 VirtReg, Matrix->getLiveUnions()[static_cast<unsigned>(Unit)]);

596 };

597

600 if (Reg == FromReg)

601 continue;

602

603 if (none_of(TRI->regunits(Reg), HasRegUnitInterference)) {

604 LLVM_DEBUG(dbgs() << "can reassign: " << VirtReg << " from "

607 return true;

608 }

609 }

610 return false;

611}

612

613

614

615

616void RAGreedy::evictInterference(const LiveInterval &VirtReg,

619

620

621

622 unsigned Cascade = ExtraInfo->getOrAssignNewCascade(VirtReg.reg());

623

625 << " interference: Cascade " << Cascade << '\n');

626

627

629 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {

631

632

633

634

637 }

638

639

641

643 continue;

644

645 Matrix->unassign(*Intf);

646 assert((ExtraInfo->getCascade(Intf->reg()) < Cascade ||

647 VirtReg.isSpillable() < Intf->isSpillable()) &&

648 "Cannot decrease cascade number, illegal eviction");

649 ExtraInfo->setCascade(Intf->reg(), Cascade);

650 ++NumEvicted;

652 }

653}

654

655

656

659 if (!CSR)

660 return false;

661

662 return Matrix ->isPhysRegUsed(PhysReg);

663}

664

665std::optional

668 unsigned CostPerUseLimit) const {

669 unsigned OrderLimit = Order.getOrder().size();

670

671 if (CostPerUseLimit < uint8_t(~0u)) {

672

675 if (MinCost >= CostPerUseLimit) {

676 LLVM_DEBUG(dbgs() << TRI->getRegClassName(RC) << " minimum cost = "

677 << MinCost << ", no cheaper registers to be found.\n");

678 return std::nullopt;

679 }

680

681

682

684 OrderLimit = RegClassInfo.getLastCostChange(RC);

685 LLVM_DEBUG(dbgs() << "Only trying the first " << OrderLimit

686 << " regs.\n");

687 }

688 }

689 return OrderLimit;

690}

691

694 if (RegCosts[PhysReg.id()] >= CostPerUseLimit)

695 return false;

696

697

700 dbgs() << printReg(PhysReg, TRI) << " would clobber CSR "

702 << '\n');

703 return false;

704 }

705 return true;

706}

707

708

709

710

711

719

720 MCRegister BestPhys = EvictAdvisor->tryFindEvictionCandidate(

721 VirtReg, Order, CostPerUseLimit, FixedRegisters);

723 evictInterference(VirtReg, BestPhys, NewVRegs);

724 return BestPhys;

725}

726

727

728

729

730

731

732

733

734

735

739

740

741 SplitConstraints.resize(UseBlocks.size());

743 for (unsigned I = 0; I != UseBlocks.size(); ++I) {

746

755

757 continue;

758

759

760 unsigned Ins = 0;

761

762

764 if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) {

766 ++Ins;

769 ++Ins;

771 ++Ins;

772 }

773

774

778 SA->getFirstSplitPoint(BC.Number)))

779 return false;

780 }

781

782

784 if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) {

786 ++Ins;

789 ++Ins;

791 ++Ins;

792 }

793 }

794

795

796 while (Ins--)

797 StaticCost += SpillPlacer->getBlockFrequency(BC.Number);

798 }

799 Cost = StaticCost;

800

801

802

803 SpillPlacer->addConstraints(SplitConstraints);

804 return SpillPlacer->scanActiveBundles();

805}

806

807

808

809bool RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf,

810 ArrayRef Blocks) {

811 const unsigned GroupSize = 8;

812 SpillPlacement::BlockConstraint BCS[GroupSize];

813 unsigned TBS[GroupSize];

814 unsigned B = 0, T = 0;

815

816 for (unsigned Number : Blocks) {

818

820 assert(T < GroupSize && "Array overflow");

822 if (++T == GroupSize) {

823 SpillPlacer->addLinks(ArrayRef(TBS, T));

824 T = 0;

825 }

826 continue;

827 }

828

829 assert(B < GroupSize && "Array overflow");

831

832

833 MachineBasicBlock *MBB = MF->getBlockNumbered(Number);

835 if (FirstNonDebugInstr != MBB->end() &&

837 SA->getFirstSplitPoint(Number)))

838 return false;

839

840 if (Intf.first() <= Indexes->getMBBStartIdx(Number))

842 else

844

845

846 if (Intf.last() >= SA->getLastSplitPoint(Number))

848 else

850

851 if (++B == GroupSize) {

852 SpillPlacer->addConstraints(ArrayRef(BCS, B));

853 B = 0;

854 }

855 }

856

857 SpillPlacer->addConstraints(ArrayRef(BCS, B));

858 SpillPlacer->addLinks(ArrayRef(TBS, T));

859 return true;

860}

861

862bool RAGreedy::growRegion(GlobalSplitCandidate &Cand) {

863

864 BitVector Todo = SA->getThroughBlocks();

865 SmallVectorImpl &ActiveBlocks = Cand.ActiveBlocks;

866 unsigned AddedTo = 0;

867#ifndef NDEBUG

868 unsigned Visited = 0;

869#endif

870

872 while (true) {

873 ArrayRef NewBundles = SpillPlacer->getRecentPositive();

874

875 for (unsigned Bundle : NewBundles) {

876

877 ArrayRef Blocks = Bundles->getBlocks(Bundle);

878

879 if (Blocks.size() >= Budget)

880 return false;

881 Budget -= Blocks.size();

882 for (unsigned Block : Blocks) {

884 continue;

886

888#ifndef NDEBUG

889 ++Visited;

890#endif

891 }

892 }

893

894 if (ActiveBlocks.size() == AddedTo)

895 break;

896

897

898

899 auto NewBlocks = ArrayRef(ActiveBlocks).slice(AddedTo);

900 if (Cand.PhysReg) {

901 if (!addThroughConstraints(Cand.Intf, NewBlocks))

902 return false;

903 } else {

904

905

906

907

908

909 bool PrefSpill = true;

910 if (SA->looksLikeLoopIV() && NewBlocks.size() >= 2) {

911

912

913

914

915 MachineLoop *L = Loops->getLoopFor(MF->getBlockNumbered(NewBlocks[0]));

916 if (L && L->getHeader()->getNumber() == (int)NewBlocks[0] &&

917 all_of(NewBlocks.drop_front(), [&](unsigned Block) {

918 return L == Loops->getLoopFor(MF->getBlockNumbered(Block));

919 }))

920 PrefSpill = false;

921 }

922 if (PrefSpill)

923 SpillPlacer->addPrefSpill(NewBlocks, true);

924 }

925 AddedTo = ActiveBlocks.size();

926

927

928 SpillPlacer->iterate();

929 }

931 return true;

932}

933

934

935

936

937

938

939

940

941bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {

942

943 if (!SA->getNumThroughBlocks())

944 return false;

945

946

948

950

951

952

953 SpillPlacer->prepare(Cand.LiveBundles);

954

955

956 BlockFrequency Cost;

957 if (!addSplitConstraints(Cand.Intf, Cost)) {

959 return false;

960 }

961

962 if (!growRegion(Cand)) {

963 LLVM_DEBUG(dbgs() << ", cannot spill all interferences.\n");

964 return false;

965 }

966

967 SpillPlacer->finish();

968

969 if (!Cand.LiveBundles.any()) {

971 return false;

972 }

973

975 for (int I : Cand.LiveBundles.set_bits())

976 dbgs() << " EB#" << I;

977 dbgs() << ".\n";

978 });

979 return true;

980}

981

982

983

984BlockFrequency RAGreedy::calcSpillCost() {

985 BlockFrequency Cost = BlockFrequency(0);

987 for (const SplitAnalysis::BlockInfo &BI : UseBlocks) {

989

990 Cost += SpillPlacer->getBlockFrequency(Number);

991

992

994 Cost += SpillPlacer->getBlockFrequency(Number);

995 }

997}

998

999

1000

1001

1002

1003BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,

1004 const AllocationOrder &Order) {

1005 BlockFrequency GlobalCost = BlockFrequency(0);

1006 const BitVector &LiveBundles = Cand.LiveBundles;

1008 for (unsigned I = 0; I != UseBlocks.size(); ++I) {

1009 const SplitAnalysis::BlockInfo &BI = UseBlocks[I];

1010 SpillPlacement::BlockConstraint &BC = SplitConstraints[I];

1011 bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, false)];

1012 bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, true)];

1013 unsigned Ins = 0;

1014

1015 Cand.Intf.moveToBlock(BC.Number);

1016

1021 while (Ins--)

1022 GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);

1023 }

1024

1025 for (unsigned Number : Cand.ActiveBlocks) {

1026 bool RegIn = LiveBundles[Bundles->getBundle(Number, false)];

1027 bool RegOut = LiveBundles[Bundles->getBundle(Number, true)];

1028 if (!RegIn && !RegOut)

1029 continue;

1030 if (RegIn && RegOut) {

1031

1032 Cand.Intf.moveToBlock(Number);

1033 if (Cand.Intf.hasInterference()) {

1034 GlobalCost += SpillPlacer->getBlockFrequency(Number);

1035 GlobalCost += SpillPlacer->getBlockFrequency(Number);

1036 }

1037 continue;

1038 }

1039

1040 GlobalCost += SpillPlacer->getBlockFrequency(Number);

1041 }

1042 return GlobalCost;

1043}

1044

1045

1046

1047

1048

1049

1050

1051

1052

1053

1054

1055

1056

1057void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit,

1058 ArrayRef UsedCands) {

1059

1060

1061 const unsigned NumGlobalIntvs = LREdit.size();

1062 LLVM_DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs

1063 << " globals.\n");

1064 assert(NumGlobalIntvs && "No global intervals configured");

1065

1066

1067

1068

1070 bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));

1071

1072

1074 for (const SplitAnalysis::BlockInfo &BI : UseBlocks) {

1076 unsigned IntvIn = 0, IntvOut = 0;

1077 SlotIndex IntfIn, IntfOut;

1079 unsigned CandIn = BundleCand[Bundles->getBundle(Number, false)];

1080 if (CandIn != NoCand) {

1081 GlobalSplitCandidate &Cand = GlobalCand[CandIn];

1082 IntvIn = Cand.IntvIdx;

1083 Cand.Intf.moveToBlock(Number);

1084 IntfIn = Cand.Intf.first();

1085 }

1086 }

1088 unsigned CandOut = BundleCand[Bundles->getBundle(Number, true)];

1089 if (CandOut != NoCand) {

1090 GlobalSplitCandidate &Cand = GlobalCand[CandOut];

1091 IntvOut = Cand.IntvIdx;

1092 Cand.Intf.moveToBlock(Number);

1093 IntfOut = Cand.Intf.last();

1094 }

1095 }

1096

1097

1098 if (!IntvIn && !IntvOut) {

1100 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))

1101 SE->splitSingleBlock(BI);

1102 continue;

1103 }

1104

1105 if (IntvIn && IntvOut)

1106 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);

1107 else if (IntvIn)

1108 SE->splitRegInBlock(BI, IntvIn, IntfIn);

1109 else

1110 SE->splitRegOutBlock(BI, IntvOut, IntfOut);

1111 }

1112

1113

1114

1115

1116 BitVector Todo = SA->getThroughBlocks();

1117 for (unsigned UsedCand : UsedCands) {

1118 ArrayRef Blocks = GlobalCand[UsedCand].ActiveBlocks;

1119 for (unsigned Number : Blocks) {

1121 continue;

1123

1124 unsigned IntvIn = 0, IntvOut = 0;

1125 SlotIndex IntfIn, IntfOut;

1126

1127 unsigned CandIn = BundleCand[Bundles->getBundle(Number, false)];

1128 if (CandIn != NoCand) {

1129 GlobalSplitCandidate &Cand = GlobalCand[CandIn];

1130 IntvIn = Cand.IntvIdx;

1131 Cand.Intf.moveToBlock(Number);

1132 IntfIn = Cand.Intf.first();

1133 }

1134

1135 unsigned CandOut = BundleCand[Bundles->getBundle(Number, true)];

1136 if (CandOut != NoCand) {

1137 GlobalSplitCandidate &Cand = GlobalCand[CandOut];

1138 IntvOut = Cand.IntvIdx;

1139 Cand.Intf.moveToBlock(Number);

1140 IntfOut = Cand.Intf.last();

1141 }

1142 if (!IntvIn && !IntvOut)

1143 continue;

1144 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);

1145 }

1146 }

1147

1148 ++NumGlobalSplits;

1149

1150 SmallVector<unsigned, 8> IntvMap;

1151 SE->finish(&IntvMap);

1152 DebugVars->splitRegister(Reg, LREdit.regs(), *LIS);

1153

1154 unsigned OrigBlocks = SA->getNumLiveBlocks();

1155

1156

1157

1158

1159

1160

1161 for (unsigned I = 0, E = LREdit.size(); I != E; ++I) {

1162 const LiveInterval &Reg = LIS->getInterval(LREdit.get(I));

1163

1164

1165 if (ExtraInfo->getOrInitStage(Reg.reg()) != RS_New)

1166 continue;

1167

1168

1169

1170 if (IntvMap[I] == 0) {

1172 continue;

1173 }

1174

1175

1176

1177 if (IntvMap[I] < NumGlobalIntvs) {

1178 if (SA->countLiveBlocks(&Reg) >= OrigBlocks) {

1179 LLVM_DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks

1180 << " blocks as original.\n");

1181

1183 }

1184 continue;

1185 }

1186

1187

1188

1189 }

1190

1192 MF->verify(LIS, Indexes, "After splitting live range around region",

1194}

1195

1196MCRegister RAGreedy::tryRegionSplit(const LiveInterval &VirtReg,

1197 AllocationOrder &Order,

1198 SmallVectorImpl &NewVRegs) {

1199 if ( TRI ->shouldRegionSplitForVirtReg(*MF, VirtReg))

1201 unsigned NumCands = 0;

1202 BlockFrequency SpillCost = calcSpillCost();

1203 BlockFrequency BestCost;

1204

1205

1206 bool HasCompact = calcCompactRegion(GlobalCand.front());

1207 if (HasCompact) {

1208

1209 NumCands = 1;

1211 } else {

1212

1213

1214 BestCost = SpillCost;

1215 LLVM_DEBUG(dbgs() << "Cost of isolating all blocks = "

1217 }

1218

1219 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,

1220 NumCands, false );

1221

1222

1223 if (!HasCompact && BestCand == NoCand)

1225

1226 return doRegionSplit(VirtReg, BestCand, HasCompact, NewVRegs);

1227}

1228

1229unsigned RAGreedy::calculateRegionSplitCostAroundReg(MCRegister PhysReg,

1230 AllocationOrder &Order,

1231 BlockFrequency &BestCost,

1232 unsigned &NumCands,

1233 unsigned &BestCand) {

1234

1235

1236 if (NumCands == IntfCache.getMaxCursors()) {

1237 unsigned WorstCount = ~0u;

1238 unsigned Worst = 0;

1239 for (unsigned CandIndex = 0; CandIndex != NumCands; ++CandIndex) {

1240 if (CandIndex == BestCand || !GlobalCand[CandIndex].PhysReg)

1241 continue;

1242 unsigned Count = GlobalCand[CandIndex].LiveBundles.count();

1243 if (Count < WorstCount) {

1244 Worst = CandIndex;

1245 WorstCount = Count;

1246 }

1247 }

1248 --NumCands;

1249 GlobalCand[Worst] = GlobalCand[NumCands];

1250 if (BestCand == NumCands)

1251 BestCand = Worst;

1252 }

1253

1254 if (GlobalCand.size() <= NumCands)

1255 GlobalCand.resize(NumCands+1);

1256 GlobalSplitCandidate &Cand = GlobalCand[NumCands];

1257 Cand.reset(IntfCache, PhysReg);

1258

1259 SpillPlacer->prepare(Cand.LiveBundles);

1260 BlockFrequency Cost;

1261 if (!addSplitConstraints(Cand.Intf, Cost)) {

1263 return BestCand;

1264 }

1267 if (Cost >= BestCost) {

1269 if (BestCand == NoCand)

1270 dbgs() << " worse than no bundles\n";

1271 else

1272 dbgs() << " worse than "

1273 << printReg(GlobalCand[BestCand].PhysReg, TRI) << '\n';

1274 });

1275 return BestCand;

1276 }

1277 if (!growRegion(Cand)) {

1278 LLVM_DEBUG(dbgs() << ", cannot spill all interferences.\n");

1279 return BestCand;

1280 }

1281

1282 SpillPlacer->finish();

1283

1284

1285 if (!Cand.LiveBundles.any()) {

1287 return BestCand;

1288 }

1289

1290 Cost += calcGlobalSplitCost(Cand, Order);

1293 for (int I : Cand.LiveBundles.set_bits())

1294 dbgs() << " EB#" << I;

1295 dbgs() << ".\n";

1296 });

1297 if (Cost < BestCost) {

1298 BestCand = NumCands;

1299 BestCost = Cost;

1300 }

1301 ++NumCands;

1302

1303 return BestCand;

1304}

1305

1306unsigned RAGreedy::calculateRegionSplitCost(const LiveInterval &VirtReg,

1307 AllocationOrder &Order,

1308 BlockFrequency &BestCost,

1309 unsigned &NumCands,

1310 bool IgnoreCSR) {

1311 unsigned BestCand = NoCand;

1312 for (MCRegister PhysReg : Order) {

1314 if (IgnoreCSR && EvictAdvisor->isUnusedCalleeSavedReg(PhysReg))

1315 continue;

1316

1317 calculateRegionSplitCostAroundReg(PhysReg, Order, BestCost, NumCands,

1318 BestCand);

1319 }

1320

1321 return BestCand;

1322}

1323

1324MCRegister RAGreedy::doRegionSplit(const LiveInterval &VirtReg,

1325 unsigned BestCand, bool HasCompact,

1326 SmallVectorImpl &NewVRegs) {

1327 SmallVector<unsigned, 8> UsedCands;

1328

1329 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);

1331

1332

1333 BundleCand.assign(Bundles->getNumBundles(), NoCand);

1334

1335

1336 if (BestCand != NoCand) {

1337 GlobalSplitCandidate &Cand = GlobalCand[BestCand];

1338 if (unsigned B = Cand.getBundles(BundleCand, BestCand)) {

1340 Cand.IntvIdx = SE->openIntv();

1342 << B << " bundles, intv " << Cand.IntvIdx << ".\n");

1343 (void)B;

1344 }

1345 }

1346

1347

1348 if (HasCompact) {

1349 GlobalSplitCandidate &Cand = GlobalCand.front();

1350 assert(!Cand.PhysReg && "Compact region has no physreg");

1351 if (unsigned B = Cand.getBundles(BundleCand, 0)) {

1353 Cand.IntvIdx = SE->openIntv();

1354 LLVM_DEBUG(dbgs() << "Split for compact region in " << B

1355 << " bundles, intv " << Cand.IntvIdx << ".\n");

1356 (void)B;

1357 }

1358 }

1359

1360 splitAroundRegion(LREdit, UsedCands);

1361 return MCRegister();

1362}

1363

1364

1365

1366bool RAGreedy::trySplitAroundHintReg(MCRegister Hint,

1367 const LiveInterval &VirtReg,

1368 SmallVectorImpl &NewVRegs,

1369 AllocationOrder &Order) {

1370

1371

1372

1373 if (MF->getFunction().hasOptSize())

1374 return false;

1375

1376

1377 if (ExtraInfo->getStage(VirtReg) >= RS_Split2)

1378 return false;

1379

1380 BlockFrequency Cost = BlockFrequency(0);

1382

1383

1384

1385

1386

1387

1388

1389

1390 for (const MachineOperand &Opnd : MRI->reg_nodbg_operands(Reg)) {

1391 const MachineInstr &Instr = *Opnd.getParent();

1392 if ( Instr .isCopy() || Opnd.isImplicit())

1393 continue;

1394

1395

1396 const bool IsDef = Opnd.isDef();

1397 const MachineOperand &OtherOpnd = Instr.getOperand(IsDef);

1400 if (OtherReg == Reg)

1401 continue;

1402

1403 unsigned SubReg = Opnd.getSubReg();

1404 unsigned OtherSubReg = OtherOpnd.getSubReg();

1405 if (SubReg && OtherSubReg && SubReg != OtherSubReg)

1406 continue;

1407

1408

1409 if (Opnd.readsReg()) {

1410 SlotIndex Index = LIS->getInstructionIndex(Instr).getRegSlot();

1411

1413 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);

1414 if (IsDef)

1415 Mask = ~Mask;

1416

1417 if (any_of(VirtReg.subranges(), [=](const LiveInterval::SubRange &S) {

1418 return (S.LaneMask & Mask).any() && S.liveAt(Index);

1419 })) {

1420 continue;

1421 }

1422 } else {

1423 if (VirtReg.liveAt(Index))

1424 continue;

1425 }

1426 }

1427

1428 MCRegister OtherPhysReg =

1431 if (OtherPhysReg == ThisHint)

1432 Cost += MBFI->getBlockFreq(Instr.getParent());

1433 }

1434

1435

1437 Cost *= Threshold;

1438 if (Cost == BlockFrequency(0))

1439 return false;

1440

1441 unsigned NumCands = 0;

1442 unsigned BestCand = NoCand;

1443 SA->analyze(&VirtReg);

1444 calculateRegionSplitCostAroundReg(Hint, Order, Cost, NumCands, BestCand);

1445 if (BestCand == NoCand)

1446 return false;

1447

1448 doRegionSplit(VirtReg, BestCand, false, NewVRegs);

1449 return true;

1450}

1451

1452

1453

1454

1455

1456

1457

1458

1459MCRegister RAGreedy::tryBlockSplit(const LiveInterval &VirtReg,

1460 AllocationOrder &Order,

1461 SmallVectorImpl &NewVRegs) {

1462 assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed");

1464 bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));

1465 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);

1468 for (const SplitAnalysis::BlockInfo &BI : UseBlocks) {

1469 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))

1470 SE->splitSingleBlock(BI);

1471 }

1472

1473 if (LREdit.empty())

1474 return MCRegister();

1475

1476

1477 SmallVector<unsigned, 8> IntvMap;

1478 SE->finish(&IntvMap);

1479

1480

1481 DebugVars->splitRegister(Reg, LREdit.regs(), *LIS);

1482

1483

1484

1485 for (unsigned I = 0, E = LREdit.size(); I != E; ++I) {

1486 const LiveInterval &LI = LIS->getInterval(LREdit.get(I));

1487 if (ExtraInfo->getOrInitStage(LI.reg()) == RS_New && IntvMap[I] == 0)

1488 ExtraInfo->setStage(LI, RS_Spill);

1489 }

1490

1492 MF->verify(LIS, Indexes, "After splitting live range around basic blocks",

1494 return MCRegister();

1495}

1496

1497

1498

1499

1500

1501

1502

1507 assert(SuperRC && "Invalid register class");

1508

1510 MI->getRegClassConstraintEffectForVReg(Reg, SuperRC, TII, TRI,

1511 true);

1512 if (!ConstrainedRC)

1513 return 0;

1515}

1516

1524

1531 continue;

1532 return MRI.getMaxLaneMaskForVReg(Reg);

1533 }

1534

1536 if (MO.isDef()) {

1538 Mask |= ~SubRegMask;

1539 } else

1540 Mask |= SubRegMask;

1541 }

1542

1543 return Mask;

1544}

1545

1546

1547

1552

1553

1554

1555 auto DestSrc = TII->isCopyInstr(*MI);

1556 if (DestSrc && ->isBundled() &&

1557 DestSrc->Destination->getSubReg() == DestSrc->Source->getSubReg())

1558 return false;

1559

1560

1562

1565 if (S.liveAt(Use))

1566 LiveAtMask |= S.LaneMask;

1567 }

1568

1569

1570

1571 return (ReadMask & ~(LiveAtMask & TRI->getCoveringLanes())).any();

1572}

1573

1574

1575

1576

1577

1578

1579

1580

1581MCRegister RAGreedy::tryInstructionSplit(const LiveInterval &VirtReg,

1582 AllocationOrder &Order,

1583 SmallVectorImpl &NewVRegs) {

1584 const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg());

1585

1586

1587 bool SplitSubClass = true;

1588 if ( RegClassInfo .isProperSubClass(CurRC)) {

1590 return MCRegister();

1591 SplitSubClass = false;

1592 }

1593

1594

1595

1596 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);

1598

1600 if (Uses.size() <= 1)

1601 return MCRegister();

1602

1604 << " individual instrs.\n");

1605

1606 const TargetRegisterClass *SuperRC =

1607 TRI->getLargestLegalSuperClass(CurRC, *MF);

1608 unsigned SuperRCNumAllocatableRegs =

1609 RegClassInfo.getNumAllocatableRegs(SuperRC);

1610

1611

1612

1613

1614 for (const SlotIndex Use : Uses) {

1615 if (const MachineInstr *MI = Indexes->getInstructionFromIndex(Use)) {

1616 if (TII->isFullCopyInstr(*MI) ||

1617 (SplitSubClass &&

1618 SuperRCNumAllocatableRegs ==

1621

1622 (!SplitSubClass && VirtReg.hasSubRanges() &&

1625 continue;

1626 }

1627 }

1628 SE->openIntv();

1629 SlotIndex SegStart = SE->enterIntvBefore(Use);

1630 SlotIndex SegStop = SE->leaveIntvAfter(Use);

1631 SE->useIntv(SegStart, SegStop);

1632 }

1633

1634 if (LREdit.empty()) {

1636 return MCRegister();

1637 }

1638

1639 SmallVector<unsigned, 8> IntvMap;

1640 SE->finish(&IntvMap);

1641 DebugVars->splitRegister(VirtReg.reg(), LREdit.regs(), *LIS);

1642

1643 ExtraInfo->setStage(LREdit.begin(), LREdit.end(), RS_Spill);

1644 return MCRegister();

1645}

1646

1647

1648

1649

1650

1651

1652

1653

1654

1655

1656void RAGreedy::calcGapWeights(MCRegister PhysReg,

1657 SmallVectorImpl &GapWeight) {

1658 assert(SA->getUseBlocks().size() == 1 && "Not a local interval");

1659 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();

1661 const unsigned NumGaps = Uses.size()-1;

1662

1663

1664 SlotIndex StartIdx =

1666 SlotIndex StopIdx =

1668

1669 GapWeight.assign(NumGaps, 0.0f);

1670

1671

1672 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {

1673 if ( Matrix ->query(const_cast<LiveInterval &>(SA->getParent()), Unit)

1674 .checkInterference())

1675 continue;

1676

1677

1678

1679

1680

1681

1682

1683

1685 Matrix->getLiveUnions()[static_cast<unsigned>(Unit)].find(StartIdx);

1686 for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {

1687

1688 while (Uses[Gap+1].getBoundaryIndex() < IntI.start())

1689 if (++Gap == NumGaps)

1690 break;

1691 if (Gap == NumGaps)

1692 break;

1693

1694

1695 const float weight = IntI.value()->weight();

1696 for (; Gap != NumGaps; ++Gap) {

1697 GapWeight[Gap] = std::max(GapWeight[Gap], weight);

1698 if (Uses[Gap+1].getBaseIndex() >= IntI.stop())

1699 break;

1700 }

1701 if (Gap == NumGaps)

1702 break;

1703 }

1704 }

1705

1706

1707 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {

1708 const LiveRange &LR = LIS->getRegUnit(Unit);

1711

1712

1713 for (unsigned Gap = 0; I != E && I->start < StopIdx; ++I) {

1714 while (Uses[Gap+1].getBoundaryIndex() < I->start)

1715 if (++Gap == NumGaps)

1716 break;

1717 if (Gap == NumGaps)

1718 break;

1719

1720 for (; Gap != NumGaps; ++Gap) {

1722 if (Uses[Gap+1].getBaseIndex() >= I->end)

1723 break;

1724 }

1725 if (Gap == NumGaps)

1726 break;

1727 }

1728 }

1729}

1730

1731

1732

1733

1734MCRegister RAGreedy::tryLocalSplit(const LiveInterval &VirtReg,

1735 AllocationOrder &Order,

1736 SmallVectorImpl &NewVRegs) {

1737

1738

1739 if (SA->getUseBlocks().size() != 1)

1740 return MCRegister();

1741

1742 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();

1743

1744

1745

1746

1747

1748

1749

1750

1752 if (Uses.size() <= 2)

1753 return MCRegister();

1754 const unsigned NumGaps = Uses.size()-1;

1755

1757 dbgs() << "tryLocalSplit: ";

1758 for (const auto &Use : Uses)

1760 dbgs() << '\n';

1761 });

1762

1763

1764

1765 SmallVector<unsigned, 8> RegMaskGaps;

1766 if (Matrix->checkRegMaskInterference(VirtReg)) {

1767

1770

1771 unsigned RI =

1773 unsigned RE = RMS.size();

1774 for (unsigned I = 0; I != NumGaps && RI != RE; ++I) {

1775

1778 continue;

1779

1780

1782 break;

1784 << Uses[I + 1]);

1785 RegMaskGaps.push_back(I);

1786

1787

1789 ++RI;

1790 }

1792 }

1793

1794

1795

1796

1797

1798

1799

1800

1801

1802

1803

1804

1805

1806

1807

1808

1809

1810

1811

1812 bool ProgressRequired = ExtraInfo->getStage(VirtReg) >= RS_Split2;

1813

1814

1815 unsigned BestBefore = NumGaps;

1816 unsigned BestAfter = 0;

1817 float BestDiff = 0;

1818

1819 const float blockFreq =

1820 SpillPlacer->getBlockFrequency(BI.MBB->getNumber()).getFrequency() *

1821 (1.0f / MBFI->getEntryFreq().getFrequency());

1823

1824 for (MCRegister PhysReg : Order) {

1826

1827

1828 calcGapWeights(PhysReg, GapWeight);

1829

1830

1831 if (Matrix->checkRegMaskInterference(VirtReg, PhysReg))

1832 for (unsigned Gap : RegMaskGaps)

1834

1835

1836

1837

1838

1839 unsigned SplitBefore = 0, SplitAfter = 1;

1840

1841

1842

1843 float MaxGap = GapWeight[0];

1844

1845 while (true) {

1846

1847 const bool LiveBefore = SplitBefore != 0 || BI.LiveIn;

1848 const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut;

1849

1851 << '-' << Uses[SplitAfter] << " I=" << MaxGap);

1852

1853

1854 if (!LiveBefore && !LiveAfter) {

1856 break;

1857 }

1858

1859 bool Shrink = true;

1860

1861

1862 unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter;

1863

1864

1865 bool Legal = !ProgressRequired || NewGaps < NumGaps;

1866

1868

1869

1870

1871

1872

1874 blockFreq * (NewGaps + 1),

1875 Uses[SplitBefore].distance(Uses[SplitAfter]) +

1877 1);

1878

1879

1881 if (EstWeight * Hysteresis >= MaxGap) {

1882 Shrink = false;

1883 float Diff = EstWeight - MaxGap;

1884 if (Diff > BestDiff) {

1887 BestBefore = SplitBefore;

1888 BestAfter = SplitAfter;

1889 }

1890 }

1891 }

1892

1893

1894 if (Shrink) {

1895 if (++SplitBefore < SplitAfter) {

1897

1898 if (GapWeight[SplitBefore - 1] >= MaxGap) {

1899 MaxGap = GapWeight[SplitBefore];

1900 for (unsigned I = SplitBefore + 1; I != SplitAfter; ++I)

1901 MaxGap = std::max(MaxGap, GapWeight[I]);

1902 }

1903 continue;

1904 }

1905 MaxGap = 0;

1906 }

1907

1908

1909 if (SplitAfter >= NumGaps) {

1911 break;

1912 }

1913

1915 MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]);

1916 }

1917 }

1918

1919

1920 if (BestBefore == NumGaps)

1921 return MCRegister();

1922

1923 LLVM_DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] << '-'

1924 << Uses[BestAfter] << ", " << BestDiff << ", "

1925 << (BestAfter - BestBefore + 1) << " instrs\n");

1926

1927 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);

1928 SE->reset(LREdit);

1929

1930 SE->openIntv();

1931 SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]);

1932 SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]);

1933 SE->useIntv(SegStart, SegStop);

1934 SmallVector<unsigned, 8> IntvMap;

1935 SE->finish(&IntvMap);

1936 DebugVars->splitRegister(VirtReg.reg(), LREdit.regs(), *LIS);

1937

1938

1939

1940 bool LiveBefore = BestBefore != 0 || BI.LiveIn;

1941 bool LiveAfter = BestAfter != NumGaps || BI.LiveOut;

1942 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;

1943 if (NewGaps >= NumGaps) {

1944 LLVM_DEBUG(dbgs() << "Tagging non-progress ranges:");

1945 assert(!ProgressRequired && "Didn't make progress when it was required.");

1946 for (unsigned I = 0, E = IntvMap.size(); I != E; ++I)

1947 if (IntvMap[I] == 1) {

1948 ExtraInfo->setStage(LIS->getInterval(LREdit.get(I)), RS_Split2);

1950 }

1952 }

1953 ++NumLocalSplits;

1954

1955 return MCRegister();

1956}

1957

1958

1959

1960

1961

1962

1963

1964

1965MCRegister RAGreedy::trySplit(const LiveInterval &VirtReg,

1966 AllocationOrder &Order,

1967 SmallVectorImpl &NewVRegs,

1969

1970 if (ExtraInfo->getStage(VirtReg) >= RS_Spill)

1971 return MCRegister();

1972

1973

1974 if (LIS->intervalIsInOneMBB(VirtReg)) {

1975 NamedRegionTimer T("local_split", "Local Splitting", TimerGroupName,

1977 SA->analyze(&VirtReg);

1978 MCRegister PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs);

1979 if (PhysReg || !NewVRegs.empty())

1980 return PhysReg;

1981 return tryInstructionSplit(VirtReg, Order, NewVRegs);

1982 }

1983

1984 NamedRegionTimer T("global_split", "Global Splitting", TimerGroupName,

1986

1987 SA->analyze(&VirtReg);

1988

1989

1990

1991

1992 if (ExtraInfo->getStage(VirtReg) < RS_Split2) {

1993 MCRegister PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);

1994 if (PhysReg || !NewVRegs.empty())

1995 return PhysReg;

1996 }

1997

1998

1999 return tryBlockSplit(VirtReg, Order, NewVRegs);

2000}

2001

2002

2003

2004

2005

2006

2009 if (MO.isTied())

2010 return true;

2011

2012 return false;

2013}

2014

2015

2016

2022 if (PhysReg == AssignedReg)

2023 return false;

2024 return TRI.regsOverlap(PhysReg, AssignedReg);

2025}

2026

2027

2028

2029

2030

2031

2032

2033

2034

2035bool RAGreedy::mayRecolorAllInterferences(

2036 MCRegister PhysReg, const LiveInterval &VirtReg,

2037 SmallLISet &RecoloringCandidates, const SmallVirtRegSet &FixedRegisters) {

2038 const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg());

2039

2040 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {

2041 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, Unit);

2042

2043

2047 LLVM_DEBUG(dbgs() << "Early abort: too many interferences.\n");

2048 CutOffInfo |= CO_Interf;

2049 return false;

2050 }

2052

2053

2054

2055

2056

2057

2058

2059

2060

2061

2062

2063 if (((ExtraInfo->getStage(*Intf) == RS_Done &&

2064 MRI->getRegClass(Intf->reg()) == CurRC &&

2068 FixedRegisters.count(Intf->reg())) {

2070 dbgs() << "Early abort: the interference is not recolorable.\n");

2071 return false;

2072 }

2073 RecoloringCandidates.insert(Intf);

2074 }

2075 }

2076 return true;

2077}

2078

2079

2080

2081

2082

2083

2084

2085

2086

2087

2088

2089

2090

2091

2092

2093

2094

2095

2096

2097

2098

2099

2100

2101

2102

2103

2104

2105

2106

2107

2108

2109

2110

2111

2112

2113

2114

2115

2116

2117

2118

2119

2120

2121

2122MCRegister RAGreedy::tryLastChanceRecoloring(

2123 const LiveInterval &VirtReg, AllocationOrder &Order,

2124 SmallVectorImpl &NewVRegs, SmallVirtRegSet &FixedRegisters,

2125 RecoloringStack &RecolorStack, unsigned Depth) {

2126 if ( TRI ->shouldUseLastChanceRecoloringForVirtReg(*MF, VirtReg))

2127 return ~0u;

2128

2129 LLVM_DEBUG(dbgs() << "Try last chance recoloring for " << VirtReg << '\n');

2130

2131 const ssize_t EntryStackSize = RecolorStack.size();

2132

2133

2135 "Last chance recoloring should really be last chance");

2136

2137

2138

2139

2141 LLVM_DEBUG(dbgs() << "Abort because max depth has been reached.\n");

2142 CutOffInfo |= CO_Depth;

2143 return ~0u;

2144 }

2145

2146

2147 SmallLISet RecoloringCandidates;

2148

2149

2150

2152 FixedRegisters.insert(VirtReg.reg());

2154

2155 for (MCRegister PhysReg : Order) {

2157 LLVM_DEBUG(dbgs() << "Try to assign: " << VirtReg << " to "

2159 RecoloringCandidates.clear();

2160 CurrentNewVRegs.clear();

2161

2162

2163 if (Matrix->checkInterference(VirtReg, PhysReg) >

2166 dbgs() << "Some interferences are not with virtual registers.\n");

2167

2168 continue;

2169 }

2170

2171

2172

2173 if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates,

2174 FixedRegisters)) {

2175 LLVM_DEBUG(dbgs() << "Some interferences cannot be recolored.\n");

2176 continue;

2177 }

2178

2179

2180

2181

2182 PQueue RecoloringQueue;

2183 for (const LiveInterval *RC : RecoloringCandidates) {

2184 Register ItVirtReg = RC->reg();

2185 enqueue(RecoloringQueue, RC);

2186 assert(VRM->hasPhys(ItVirtReg) &&

2187 "Interferences are supposed to be with allocated variables");

2188

2189

2190 RecolorStack.push_back(std::make_pair(RC, VRM->getPhys(ItVirtReg)));

2191

2192

2193 Matrix->unassign(*RC);

2194 }

2195

2196

2197

2198

2199 Matrix->assign(VirtReg, PhysReg);

2200

2201

2203

2204

2205

2206

2208 if (tryRecoloringCandidates(RecoloringQueue, CurrentNewVRegs,

2209 FixedRegisters, RecolorStack, Depth)) {

2210

2212

2213

2214 if (VRM->hasPhys(ThisVirtReg)) {

2215 Matrix->unassign(VirtReg);

2216 return PhysReg;

2217 }

2218

2219

2220 LLVM_DEBUG(dbgs() << "tryRecoloringCandidates deleted a fixed register "

2221 << printReg(ThisVirtReg) << '\n');

2222 FixedRegisters.erase(ThisVirtReg);

2223 return MCRegister();

2224 }

2225

2226 LLVM_DEBUG(dbgs() << "Fail to assign: " << VirtReg << " to "

2228

2229

2230 FixedRegisters = SaveFixedRegisters;

2231 Matrix->unassign(VirtReg);

2232

2233

2234

2235

2236

2237 for (Register R : CurrentNewVRegs) {

2238 if (RecoloringCandidates.count(&LIS->getInterval(R)))

2239 continue;

2241 }

2242

2243

2244

2245

2246

2247

2248

2249 for (ssize_t I = RecolorStack.size() - 1; I >= EntryStackSize; --I) {

2250 const LiveInterval *LI;

2251 MCRegister PhysReg;

2252 std::tie(LI, PhysReg) = RecolorStack[I];

2253

2254 if (VRM->hasPhys(LI->reg()))

2255 Matrix->unassign(*LI);

2256 }

2257

2258 for (size_t I = EntryStackSize; I != RecolorStack.size(); ++I) {

2259 const LiveInterval *LI;

2260 MCRegister PhysReg;

2261 std::tie(LI, PhysReg) = RecolorStack[I];

2262 if (!LI->empty() && MRI ->reg_nodbg_empty(LI->reg()))

2263 Matrix->assign(*LI, PhysReg);

2264 }

2265

2266

2267 RecolorStack.resize(EntryStackSize);

2268 }

2269

2270

2271 return ~0u;

2272}

2273

2274

2275

2276

2277

2278

2279

2280

2281

2282bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,

2283 SmallVectorImpl &NewVRegs,

2285 RecoloringStack &RecolorStack,

2286 unsigned Depth) {

2287 while (!RecoloringQueue.empty()) {

2288 const LiveInterval *LI = dequeue(RecoloringQueue);

2289 LLVM_DEBUG(dbgs() << "Try to recolor: " << *LI << '\n');

2290 MCRegister PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters,

2291 RecolorStack, Depth + 1);

2292

2293

2294

2295

2296 if (PhysReg == ~0u || (!PhysReg && !LI->empty()))

2297 return false;

2298

2299 if (!PhysReg) {

2300 assert(LI->empty() && "Only empty live-range do not require a register");

2302 << " succeeded. Empty LI.\n");

2303 continue;

2304 }

2306 << " succeeded with: " << printReg(PhysReg, TRI) << '\n');

2307

2308 Matrix->assign(*LI, PhysReg);

2309 FixedRegisters.insert(LI->reg());

2310 }

2311 return true;

2312}

2313

2314

2315

2316

2317

2320 CutOffInfo = CO_None;

2321 LLVMContext &Ctx = MF->getFunction().getContext();

2323 RecoloringStack RecolorStack;

2325 selectOrSplitImpl(VirtReg, NewVRegs, FixedRegisters, RecolorStack);

2326 if (Reg == ~0U && (CutOffInfo != CO_None)) {

2327 uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf);

2328 if (CutOffEncountered == CO_Depth)

2329 Ctx.emitError("register allocation failed: maximum depth for recoloring "

2330 "reached. Use -fexhaustive-register-search to skip "

2331 "cutoffs");

2332 else if (CutOffEncountered == CO_Interf)

2333 Ctx.emitError("register allocation failed: maximum interference for "

2334 "recoloring reached. Use -fexhaustive-register-search "

2335 "to skip cutoffs");

2336 else if (CutOffEncountered == (CO_Depth | CO_Interf))

2337 Ctx.emitError("register allocation failed: maximum interference and "

2338 "depth for recoloring reached. Use "

2339 "-fexhaustive-register-search to skip cutoffs");

2340 }

2341 return Reg;

2342}

2343

2344

2345

2346

2347

2348

2349

2350MCRegister RAGreedy::tryAssignCSRFirstTime(

2353 if (ExtraInfo->getStage(VirtReg) == RS_Spill && VirtReg.isSpillable()) {

2354

2355

2356 SA->analyze(&VirtReg);

2357 if (calcSpillCost() >= CSRCost)

2358 return PhysReg;

2359

2360

2361

2362 CostPerUseLimit = 1;

2364 }

2365 if (ExtraInfo->getStage(VirtReg) < RS_Split) {

2366

2367

2368 SA->analyze(&VirtReg);

2369 unsigned NumCands = 0;

2370 BlockFrequency BestCost = CSRCost;

2371 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,

2372 NumCands, true );

2373 if (BestCand == NoCand)

2374

2375 return PhysReg;

2376

2377

2378 doRegionSplit(VirtReg, BestCand, false, NewVRegs);

2380 }

2381 return PhysReg;

2382}

2383

2385

2386 SetOfBrokenHints.remove(&LI);

2387}

2388

2389void RAGreedy::initializeCSRCost() {

2390

2391

2396 if (!CSRCost.getFrequency())

2397 return;

2398

2399

2400 uint64_t ActualEntry = MBFI->getEntryFreq().getFrequency();

2401 if (!ActualEntry) {

2403 return;

2404 }

2405 uint64_t FixedEntry = 1 << 14;

2406 if (ActualEntry < FixedEntry)

2408 else if (ActualEntry <= UINT32_MAX)

2409

2411 else

2412

2413 CSRCost =

2414 BlockFrequency(CSRCost.getFrequency() * (ActualEntry / FixedEntry));

2415}

2416

2417

2418

2419

2420void RAGreedy::collectHintInfo(Register Reg, HintsInfo &Out) {

2421 const TargetRegisterClass *RC = MRI->getRegClass(Reg);

2422

2423 for (const MachineOperand &Opnd : MRI->reg_nodbg_operands(Reg)) {

2424 const MachineInstr &Instr = *Opnd.getParent();

2425 if ( Instr .isCopy() || Opnd.isImplicit())

2426 continue;

2427

2428

2429 const MachineOperand &OtherOpnd = Instr.getOperand(Opnd.isDef());

2431 if (OtherReg == Reg)

2432 continue;

2433 unsigned OtherSubReg = OtherOpnd.getSubReg();

2434 unsigned SubReg = Opnd.getSubReg();

2435

2436

2437 MCRegister OtherPhysReg;

2439 if (OtherSubReg)

2440 OtherPhysReg = TRI->getMatchingSuperReg(OtherReg, OtherSubReg, RC);

2442 OtherPhysReg = TRI->getMatchingSuperReg(OtherReg, SubReg, RC);

2443 else

2444 OtherPhysReg = OtherReg;

2445 } else {

2446 OtherPhysReg = VRM->getPhys(OtherReg);

2447

2448

2449

2450 if (SubReg && OtherSubReg && SubReg != OtherSubReg)

2451 continue;

2452 }

2453

2454

2455 if (OtherPhysReg) {

2456 Out.push_back(HintInfo(MBFI->getBlockFreq(Instr.getParent()), OtherReg,

2457 OtherPhysReg));

2458 }

2459 }

2460}

2461

2462

2463

2464

2465BlockFrequency RAGreedy::getBrokenHintFreq(const HintsInfo &List,

2466 MCRegister PhysReg) {

2467 BlockFrequency Cost = BlockFrequency(0);

2468 for (const HintInfo &Info : List) {

2469 if (Info.PhysReg != PhysReg)

2471 }

2472 return Cost;

2473}

2474

2475

2476

2477

2478

2479

2480

2481

2482

2483void RAGreedy::tryHintRecoloring(const LiveInterval &VirtReg) {

2484

2485

2486

2487 HintsInfo Info;

2489 MCRegister PhysReg = VRM->getPhys(Reg);

2490

2491

2492 SmallSet<Register, 4> Visited = {Reg};

2494

2496 << '(' << printReg(PhysReg, TRI) << ")\n");

2497

2498 do {

2500

2501 MCRegister CurrPhys = VRM->getPhys(Reg);

2502

2503

2504 if (!CurrPhys) {

2506 "We have an unallocated variable which should have been handled");

2507 continue;

2508 }

2509

2510

2511

2512 LiveInterval &LI = LIS->getInterval(Reg);

2513

2514

2515 if (CurrPhys != PhysReg && ( MRI ->getRegClass(Reg)->contains(PhysReg) ||

2516 Matrix->checkInterference(LI, PhysReg)))

2517 continue;

2518

2520 << ") is recolorable.\n");

2521

2522

2523 Info.clear();

2524 collectHintInfo(Reg, Info);

2525

2526

2527 if (CurrPhys != PhysReg) {

2529 BlockFrequency OldCopiesCost = getBrokenHintFreq(Info, CurrPhys);

2530 BlockFrequency NewCopiesCost = getBrokenHintFreq(Info, PhysReg);

2532 << "\nNew Cost: "

2534 if (OldCopiesCost < NewCopiesCost) {

2536 continue;

2537 }

2538

2539

2540

2542

2543 Matrix->unassign(LI);

2544 Matrix->assign(LI, PhysReg);

2545 }

2546

2547

2548 for (const HintInfo &HI : Info) {

2549

2550 if (HI.Reg.isVirtual() && Visited.insert(HI.Reg).second)

2552 }

2553 } while (!RecoloringCandidates.empty());

2554}

2555

2556

2557

2558

2559

2560

2561

2562

2563

2564

2565

2566

2567

2568

2569

2570

2571

2572

2573

2574

2575

2576

2577

2578

2579

2580

2581

2582

2583

2584

2585

2586

2587

2588

2589

2590

2591

2592void RAGreedy::tryHintsRecoloring() {

2593 for (const LiveInterval *LI : SetOfBrokenHints) {

2595 "Recoloring is possible only for virtual registers");

2596

2597

2598 if ( VRM ->hasPhys(LI->reg()))

2599 continue;

2600 tryHintRecoloring(*LI);

2601 }

2602}

2603

2604MCRegister RAGreedy::selectOrSplitImpl(const LiveInterval &VirtReg,

2605 SmallVectorImpl &NewVRegs,

2607 RecoloringStack &RecolorStack,

2608 unsigned Depth) {

2609 uint8_t CostPerUseLimit = uint8_t(~0u);

2610

2611 auto Order =

2613 if (MCRegister PhysReg =

2614 tryAssign(VirtReg, Order, NewVRegs, FixedRegisters)) {

2615

2616

2617

2618 if (CSRCost.getFrequency() &&

2619 EvictAdvisor->isUnusedCalleeSavedReg(PhysReg) && NewVRegs.empty()) {

2620 MCRegister CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,

2621 CostPerUseLimit, NewVRegs);

2622 if (CSRReg || !NewVRegs.empty())

2623

2624

2625 return CSRReg;

2626 } else

2627 return PhysReg;

2628 }

2629

2630 if (!NewVRegs.empty())

2631 return MCRegister();

2632

2633 LiveRangeStage Stage = ExtraInfo->getStage(VirtReg);

2634 LLVM_DEBUG(dbgs() << StageName[Stage] << " Cascade "

2635 << ExtraInfo->getCascade(VirtReg.reg()) << '\n');

2636

2637

2638

2639

2641 if (MCRegister PhysReg =

2642 tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit,

2643 FixedRegisters)) {

2645

2646

2647

2648

2649

2650 if (Hint && Hint != PhysReg)

2651 SetOfBrokenHints.insert(&VirtReg);

2652 return PhysReg;

2653 }

2654 }

2655

2656 assert((NewVRegs.empty() || Depth) && "Cannot append to existing NewVRegs");

2657

2658

2659

2660

2662 ExtraInfo->setStage(VirtReg, RS_Split);

2665 return MCRegister();

2666 }

2667

2669

2670 unsigned NewVRegSizeBefore = NewVRegs.size();

2671 MCRegister PhysReg = trySplit(VirtReg, Order, NewVRegs, FixedRegisters);

2672 if (PhysReg || (NewVRegs.size() - NewVRegSizeBefore))

2673 return PhysReg;

2674 }

2675

2676

2677

2679 return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,

2680 RecolorStack, Depth);

2681 }

2682

2683

2686 LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);

2688 ExtraInfo->setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done);

2689

2690

2691

2692

2694 DebugVars->splitRegister(r, LRE.regs(), *LIS);

2696 DebugVars->splitRegister(r, LRE.regs(), *LIS);

2697

2699 MF->verify(LIS, Indexes, "After spilling", &errs());

2700

2701

2702

2703 return MCRegister();

2704}

2705

2706void RAGreedy::RAGreedyStats::report(MachineOptimizationRemarkMissed &R) {

2707 using namespace ore;

2708 if (Spills) {

2709 R << NV("NumSpills", Spills) << " spills ";

2710 R << NV("TotalSpillsCost", SpillsCost) << " total spills cost ";

2711 }

2712 if (FoldedSpills) {

2713 R << NV("NumFoldedSpills", FoldedSpills) << " folded spills ";

2714 R << NV("TotalFoldedSpillsCost", FoldedSpillsCost)

2715 << " total folded spills cost ";

2716 }

2717 if (Reloads) {

2718 R << NV("NumReloads", Reloads) << " reloads ";

2719 R << NV("TotalReloadsCost", ReloadsCost) << " total reloads cost ";

2720 }

2721 if (FoldedReloads) {

2722 R << NV("NumFoldedReloads", FoldedReloads) << " folded reloads ";

2723 R << NV("TotalFoldedReloadsCost", FoldedReloadsCost)

2724 << " total folded reloads cost ";

2725 }

2726 if (ZeroCostFoldedReloads)

2727 R << NV("NumZeroCostFoldedReloads", ZeroCostFoldedReloads)

2728 << " zero cost folded reloads ";

2730 R << NV("NumVRCopies", Copies) << " virtual registers copies ";

2731 R << NV("TotalCopiesCost", CopiesCost) << " total copies cost ";

2732 }

2733}

2734

2735RAGreedy::RAGreedyStats RAGreedy::computeStats(MachineBasicBlock &MBB) {

2736 RAGreedyStats Stats;

2737 const MachineFrameInfo &MFI = MF->getFrameInfo();

2738 int FI;

2739

2740 auto isSpillSlotAccess = [&MFI](const MachineMemOperand *A) {

2742 A->getPseudoValue())->getFrameIndex());

2743 };

2744 auto isPatchpointInstr = [](const MachineInstr &MI) {

2745 return MI.getOpcode() == TargetOpcode::PATCHPOINT ||

2746 MI.getOpcode() == TargetOpcode::STACKMAP ||

2747 MI.getOpcode() == TargetOpcode::STATEPOINT;

2748 };

2749 for (MachineInstr &MI : MBB) {

2750 auto DestSrc = TII->isCopyInstr(MI);

2751 if (DestSrc) {

2752 const MachineOperand &Dest = *DestSrc->Destination;

2753 const MachineOperand &Src = *DestSrc->Source;

2754 Register SrcReg = Src.getReg();

2756

2759 SrcReg = VRM->getPhys(SrcReg);

2760 if (SrcReg && Src.getSubReg())

2761 SrcReg = TRI->getSubReg(SrcReg, Src.getSubReg());

2762 }

2764 DestReg = VRM->getPhys(DestReg);

2765 if (DestReg && Dest.getSubReg())

2766 DestReg = TRI->getSubReg(DestReg, Dest.getSubReg());

2767 }

2768 if (SrcReg != DestReg)

2770 }

2771 continue;

2772 }

2773

2774 SmallVector<const MachineMemOperand *, 2> Accesses;

2776 ++Stats.Reloads;

2777 continue;

2778 }

2781 continue;

2782 }

2783 if (TII->hasLoadFromStackSlot(MI, Accesses) &&

2785 if (!isPatchpointInstr(MI)) {

2787 continue;

2788 }

2789

2790 std::pair<unsigned, unsigned> NonZeroCostRange =

2791 TII->getPatchpointUnfoldableRange(MI);

2792 SmallSet<unsigned, 16> FoldedReloads;

2793 SmallSet<unsigned, 16> ZeroCostFoldedReloads;

2794 for (unsigned Idx = 0, E = MI.getNumOperands(); Idx < E; ++Idx) {

2795 MachineOperand &MO = MI.getOperand(Idx);

2797 continue;

2798 if (Idx >= NonZeroCostRange.first && Idx < NonZeroCostRange.second)

2800 else

2802 }

2803

2804 for (unsigned Slot : FoldedReloads)

2805 ZeroCostFoldedReloads.erase(Slot);

2806 Stats.FoldedReloads += FoldedReloads.size();

2807 Stats.ZeroCostFoldedReloads += ZeroCostFoldedReloads.size();

2808 continue;

2809 }

2811 if (TII->hasStoreToStackSlot(MI, Accesses) &&

2814 }

2815 }

2816

2817

2818 float RelFreq = MBFI->getBlockFreqRelativeToEntryBlock(&MBB);

2819 Stats.ReloadsCost = RelFreq * Stats.Reloads;

2820 Stats.FoldedReloadsCost = RelFreq * Stats.FoldedReloads;

2821 Stats.SpillsCost = RelFreq * Stats.Spills;

2822 Stats.FoldedSpillsCost = RelFreq * Stats.FoldedSpills;

2823 Stats.CopiesCost = RelFreq * Stats.Copies;

2825}

2826

2827RAGreedy::RAGreedyStats RAGreedy::reportStats(MachineLoop *L) {

2828 RAGreedyStats Stats;

2829

2830

2831 for (MachineLoop *SubLoop : *L)

2832 Stats.add(reportStats(SubLoop));

2833

2834 for (MachineBasicBlock *MBB : L->getBlocks())

2835

2836 if (Loops->getLoopFor(MBB) == L)

2837 Stats.add(computeStats(*MBB));

2838

2839 if ( Stats .isEmpty()) {

2840 using namespace ore;

2841

2842 ORE->emit([&]() {

2843 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "LoopSpillReloadCopies",

2844 L->getStartLoc(), L->getHeader());

2845 Stats.report(R);

2846 R << "generated in loop";

2847 return R;

2848 });

2849 }

2851}

2852

2853void RAGreedy::reportStats() {

2854 if (!ORE->allowExtraAnalysis(DEBUG_TYPE))

2855 return;

2856 RAGreedyStats Stats;

2857 for (MachineLoop *L : *Loops)

2858 Stats.add(reportStats(L));

2859

2860 for (MachineBasicBlock &MBB : *MF)

2861 if (!Loops->getLoopFor(&MBB))

2862 Stats.add(computeStats(MBB));

2863 if ( Stats .isEmpty()) {

2864 using namespace ore;

2865

2866 ORE->emit([&]() {

2868 if (auto *SP = MF->getFunction().getSubprogram())

2870 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "SpillReloadCopies", Loc,

2871 &MF->front());

2872 Stats.report(R);

2873 R << "generated in function";

2874 return R;

2875 });

2876 }

2877}

2878

2879bool RAGreedy::hasVirtRegAlloc() {

2880 for (unsigned I = 0, E = MRI->getNumVirtRegs(); I != E; ++I) {

2882 if (MRI->reg_nodbg_empty(Reg))

2883 continue;

2885 return true;

2886 }

2887

2888 return false;

2889}

2890

2892 LLVM_DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"

2893 << "********** Function: " << mf.getName() << '\n');

2894

2895 MF = &mf;

2897

2899 MF->verify(LIS, Indexes, "Before greedy register allocator", &errs());

2900

2902

2903

2904

2905 if (!hasVirtRegAlloc())

2906 return false;

2907

2908

2909

2910 Indexes->packIndexes();

2911

2912 initializeCSRCost();

2913

2914 RegCosts = TRI->getRegisterCosts(*MF);

2915 RegClassPriorityTrumpsGlobalness =

2918 : TRI->regClassPriorityTrumpsGlobalness(*MF);

2919

2922 : TRI->reverseLocalAssignment();

2923

2924 ExtraInfo.emplace();

2925

2926 EvictAdvisor = EvictProvider->getAdvisor(*MF, *this, MBFI, Loops);

2927 PriorityAdvisor = PriorityProvider->getAdvisor(*MF, *this, *Indexes);

2928

2929 VRAI = std::make_unique(*MF, *LIS, *VRM, *Loops, *MBFI);

2932

2933 VRAI->calculateSpillWeightsAndHints();

2934

2936

2938 SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree, *MBFI, *VRAI));

2939

2940 IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI);

2941 GlobalCand.resize(32);

2942 SetOfBrokenHints.clear();

2943

2945 tryHintsRecoloring();

2946

2948 MF->verify(LIS, Indexes, "Before post optimization", &errs());

2950 reportStats();

2951

2953 return true;

2954}

unsigned const MachineRegisterInfo * MRI

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

const TargetInstrInfo & TII

This file implements the BitVector class.

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

Analysis containing CSE Info

#define clEnumValN(ENUMVAL, FLAGNAME, DESC)

DXIL Forward Handle Accesses

This file implements an indexed map.

const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]

block placement Basic Block Placement Stats

Promote Memory to Register

MachineInstr unsigned OpIdx

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

static bool hasTiedDef(MachineRegisterInfo *MRI, Register reg)

Return true if reg has any tied def operand.

Definition RegAllocGreedy.cpp:2007

static cl::opt< bool > GreedyRegClassPriorityTrumpsGlobalness("greedy-regclass-priority-trumps-globalness", cl::desc("Change the greedy register allocator's live range priority " "calculation to make the AllocationPriority of the register class " "more important then whether the range is global"), cl::Hidden)

static cl::opt< bool > ExhaustiveSearch("exhaustive-register-search", cl::NotHidden, cl::desc("Exhaustive Search for registers bypassing the depth " "and interference cutoffs of last chance recoloring"), cl::Hidden)

const float Hysteresis

Definition RegAllocGreedy.cpp:327

static cl::opt< unsigned > LastChanceRecoloringMaxInterference("lcr-max-interf", cl::Hidden, cl::desc("Last chance recoloring maximum number of considered" " interference at a time"), cl::init(8))

static bool readsLaneSubset(const MachineRegisterInfo &MRI, const MachineInstr *MI, const LiveInterval &VirtReg, const TargetRegisterInfo *TRI, SlotIndex Use, const TargetInstrInfo *TII)

Return true if MI at \P Use reads a subset of the lanes live in VirtReg.

Definition RegAllocGreedy.cpp:1548

static bool assignedRegPartiallyOverlaps(const TargetRegisterInfo &TRI, const VirtRegMap &VRM, MCRegister PhysReg, const LiveInterval &Intf)

Return true if the existing assignment of Intf overlaps, but is not the same, as PhysReg.

Definition RegAllocGreedy.cpp:2017

static cl::opt< unsigned > CSRFirstTimeCost("regalloc-csr-first-time-cost", cl::desc("Cost for first time use of callee-saved register."), cl::init(0), cl::Hidden)

static cl::opt< unsigned > LastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden, cl::desc("Last chance recoloring max depth"), cl::init(5))

static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", createGreedyRegisterAllocator)

static cl::opt< unsigned long > GrowRegionComplexityBudget("grow-region-complexity-budget", cl::desc("growRegion() does not scale with the number of BB edges, so " "limit its budget and bail out once we reach the limit."), cl::init(10000), cl::Hidden)

static cl::opt< unsigned > SplitThresholdForRegWithHint("split-threshold-for-reg-with-hint", cl::desc("The threshold for splitting a virtual register with a hint, in " "percentage"), cl::init(75), cl::Hidden)

static cl::opt< SplitEditor::ComplementSpillMode > SplitSpillMode("split-spill-mode", cl::Hidden, cl::desc("Spill mode for splitting live ranges"), cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"), clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"), clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed")), cl::init(SplitEditor::SM_Speed))

static unsigned getNumAllocatableRegsForConstraints(const MachineInstr *MI, Register Reg, const TargetRegisterClass *SuperRC, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, const RegisterClassInfo &RCI)

Get the number of allocatable registers that match the constraints of Reg on MI and that are also in ...

Definition RegAllocGreedy.cpp:1503

static cl::opt< bool > GreedyReverseLocalAssignment("greedy-reverse-local-assignment", cl::desc("Reverse allocation order of local live ranges, such that " "shorter local live ranges will tend to be allocated first"), cl::Hidden)

static LaneBitmask getInstReadLaneMask(const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, const MachineInstr &FirstMI, Register Reg)

Definition RegAllocGreedy.cpp:1517

Remove Loads Into Fake Uses

SI optimize exec mask operations pre RA

SI Optimize VGPR LiveRange

This file defines the SmallSet class.

This file defines the SmallVector class.

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName) const

Definition RegAllocGreedy.cpp:218

PreservedAnalyses run(MachineFunction &F, MachineFunctionAnalysisManager &AM)

Definition RegAllocGreedy.cpp:244

bool isHint(Register Reg) const

Return true if Reg is a preferred physical register.

ArrayRef< MCPhysReg > getOrder() const

Get the allocation order without reordered hints.

static AllocationOrder create(Register VirtReg, const VirtRegMap &VRM, const RegisterClassInfo &RegClassInfo, const LiveRegMatrix *Matrix)

Create a new AllocationOrder for VirtReg.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

Represent the analysis usage information of a pass.

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

LLVM_ABI void setPreservesCFG()

This function should be called by the pass, iff they do not:

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

size_t size() const

size - Get the array size.

bool test(unsigned Idx) const

static BlockFrequency max()

Returns the maximum possible frequency, the saturation value.

Represents analyses that only rely on functions' control flow.

FunctionPass class - This class is used to implement most global optimizations.

Cursor - The primary query interface for the block interference cache.

SlotIndex first()

first - Return the starting index of the first interfering range in the current block.

SlotIndex last()

last - Return the ending index of the last interfering range in the current block.

bool hasInterference()

hasInterference - Return true if the current block has any interference.

void moveToBlock(unsigned MBBNum)

moveTo - Move cursor to basic block MBBNum.

This is an important class for using LLVM in a threaded context.

Query interferences between a single live virtual register and a live interval union.

const SmallVectorImpl< const LiveInterval * > & interferingVRegs(unsigned MaxInterferingRegs=std::numeric_limits< unsigned >::max())

LiveSegments::iterator SegmentIter

A live range for subregisters.

LiveInterval - This class represents the liveness of a register, or stack slot.

bool isSpillable() const

isSpillable - Can this interval be spilled?

bool hasSubRanges() const

Returns true if subregister liveness information is available.

LLVM_ABI unsigned getSize() const

getSize - Returns the sum of sizes of all the LiveRange's.

iterator_range< subrange_iterator > subranges()

MachineInstr * getInstructionFromIndex(SlotIndex index) const

Returns the instruction associated with the given index.

LiveInterval & getInterval(Register Reg)

ArrayRef< Register > regs() const

Segments::const_iterator const_iterator

bool liveAt(SlotIndex index) const

SlotIndex beginIndex() const

beginIndex - Return the lowest numbered slot covered.

SlotIndex endIndex() const

endNumber - return the maximum point of the range of the whole, exclusive.

LLVM_ABI iterator find(SlotIndex Pos)

find - Return an iterator pointing to the first segment that ends after Pos, or end().

@ IK_VirtReg

Virtual register interference.

Wrapper class representing physical registers. Should be passed by value.

constexpr bool isValid() const

static constexpr unsigned NoRegister

constexpr unsigned id() const

static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)

An RAII based helper class to modify MachineFunctionProperties when running pass.

int getNumber() const

MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...

LLVM_ABI iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)

Returns an iterator to the first non-debug instruction in the basic block, or end().

MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...

Analysis pass which computes a MachineDominatorTree.

DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...

bool isSpillSlotObjectIndex(int ObjectIdx) const

Returns true if the specified index corresponds to a spill slot.

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

const TargetSubtargetInfo & getSubtarget() const

getSubtarget - Return the subtarget for which this machine code is being compiled.

StringRef getName() const

getName - Return the name of the corresponding LLVM function.

Representation of each machine instruction.

bool isImplicitDef() const

Analysis pass that exposes the MachineLoopInfo for a machine function.

MachineOperand class - Representation of each machine instruction operand.

unsigned getSubReg() const

bool isReg() const

isReg - Tests if this is a MO_Register operand.

getReg - Returns the register number.

bool isFI() const

isFI - Tests if this is a MO_FrameIndex operand.

MachineRegisterInfo - Keep track of information for virtual and physical registers,...

static LLVM_ABI PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

Pass interface - Implemented by all 'passes'.

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

bool run(MachineFunction &mf)

Perform register allocation.

Definition RegAllocGreedy.cpp:2891

Spiller & spiller() override

MCRegister selectOrSplit(const LiveInterval &, SmallVectorImpl< Register > &) override

Definition RegAllocGreedy.cpp:2318

RAGreedy(RequiredAnalyses &Analyses, const RegAllocFilterFunc F=nullptr)

Definition RegAllocGreedy.cpp:200

const LiveInterval * dequeue() override

dequeue - Return the next unassigned register, or NULL.

Definition RegAllocGreedy.cpp:516

void enqueueImpl(const LiveInterval *LI) override

enqueue - Add VirtReg to the priority queue of unassigned registers.

Definition RegAllocGreedy.cpp:417

void releaseMemory()

Definition RegAllocGreedy.cpp:412

void aboutToRemoveInterval(const LiveInterval &) override

Method called when the allocator is about to remove a LiveInterval.

Definition RegAllocGreedy.cpp:2384

RegAllocBase(const RegAllocFilterFunc F=nullptr)

void enqueue(const LiveInterval *LI)

enqueue - Add VirtReg to the priority queue of unassigned registers.

void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat)

SmallPtrSet< MachineInstr *, 32 > DeadRemats

Inst which is a def of an original reg and whose defs are already all dead after remat is saved in De...

const TargetRegisterInfo * TRI

static const char TimerGroupName[]

static const char TimerGroupDescription[]

virtual void postOptimization()

RegisterClassInfo RegClassInfo

MachineRegisterInfo * MRI

bool shouldAllocateRegister(Register Reg)

Get whether a given register should be allocated.

static bool VerifyEnabled

VerifyEnabled - True when -verify-regalloc is given.

ImmutableAnalysis abstraction for fetching the Eviction Advisor.

A MachineFunction analysis for fetching the Eviction Advisor.

Common provider for legacy and new pass managers.

const TargetRegisterInfo *const TRI

std::optional< unsigned > getOrderLimit(const LiveInterval &VirtReg, const AllocationOrder &Order, unsigned CostPerUseLimit) const

Definition RegAllocGreedy.cpp:666

const ArrayRef< uint8_t > RegCosts

MachineRegisterInfo *const MRI

const RegisterClassInfo & RegClassInfo

bool isUnusedCalleeSavedReg(MCRegister PhysReg) const

Returns true if the given PhysReg is a callee saved register and has not been used for allocation yet...

Definition RegAllocGreedy.cpp:657

bool canReassign(const LiveInterval &VirtReg, MCRegister FromReg) const

Definition RegAllocGreedy.cpp:589

bool canAllocatePhysReg(unsigned CostPerUseLimit, MCRegister PhysReg) const

Definition RegAllocGreedy.cpp:692

LiveRegMatrix *const Matrix

Common provider for getting the priority advisor and logging rewards.

unsigned getNumAllocatableRegs(const TargetRegisterClass *RC) const

getNumAllocatableRegs - Returns the number of actually allocatable registers in RC in the current fun...

Wrapper class representing virtual and physical registers.

static Register index2VirtReg(unsigned Index)

Convert a 0-based index to a virtual register number.

MCRegister asMCReg() const

Utility to check-convert this value to a MCRegister.

unsigned virtRegIndex() const

Convert a virtual register number to a 0-based index.

constexpr bool isVirtual() const

Return true if the specified register number is in the virtual register namespace.

constexpr bool isPhysical() const

Return true if the specified register number is in the physical register namespace.

SlotIndex - An opaque wrapper around machine indexes.

static bool isSameInstr(SlotIndex A, SlotIndex B)

isSameInstr - Return true if A and B refer to the same instruction.

static bool isEarlierInstr(SlotIndex A, SlotIndex B)

isEarlierInstr - Return true if A refers to an instruction earlier than B.

@ InstrDist

The default distance between instructions as returned by distance().

bool isValid() const

Returns true if this is a valid index.

SlotIndex getBoundaryIndex() const

Returns the boundary index for associated with this index.

SlotIndex getBaseIndex() const

Returns the base index for associated with this index.

int getApproxInstrDistance(SlotIndex other) const

Return the scaled distance from this index to the given one, where all slots on the same instruction ...

size_type count(const T &V) const

count - Return 1 if the element is in the set, 0 otherwise.

std::pair< const_iterator, bool > insert(const T &V)

insert - Insert an element into the set if it isn't already there.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void assign(size_type NumElts, ValueParamT Elt)

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

@ MustSpill

A register is impossible, variable must be spilled.

@ DontCare

Block doesn't care / variable not live.

@ PrefReg

Block entry/exit prefers a register.

@ PrefSpill

Block entry/exit prefers a stack slot.

virtual void spill(LiveRangeEdit &LRE, AllocationOrder *Order=nullptr)=0

spill - Spill the LRE.getParent() live interval.

SplitAnalysis - Analyze a LiveInterval, looking for live range splitting opportunities.

SplitEditor - Edit machine code and LiveIntervals for live range splitting.

@ SM_Partition

SM_Partition(Default) - Try to create the complement interval so it doesn't overlap any other interva...

@ SM_Speed

SM_Speed - Overlap intervals to minimize the expected execution frequency of the inserted copies.

@ SM_Size

SM_Size - Overlap intervals to minimize the number of inserted COPY instructions.

StringRef - Represent a constant reference to a string, i.e.

constexpr bool empty() const

empty - Check if the string is empty.

TargetInstrInfo - Interface to description of machine instruction set.

const bool GlobalPriority

const uint8_t AllocationPriority

Classes with a higher priority value are assigned first by register allocators using a greedy heurist...

TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...

virtual const TargetInstrInfo * getInstrInfo() const

A Use represents the edge between a Value definition and its users.

MCRegister getPhys(Register virtReg) const

returns the physical register mapped to the specified virtual register

bool hasPhys(Register virtReg) const

returns true if the specified virtual register is mapped to a physical register

An efficient, type-erasing, non-owning reference to a callable.

This class implements an extremely fast bulk output stream that can only output to a stream.

Pass manager infrastructure for declaring and invalidating analyses.

constexpr std::underlying_type_t< E > Mask()

Get a bitmask with 1s in all places up to the high-order bit of E's largest value.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

ValuesClass values(OptsTy... Options)

Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...

initializer< Ty > init(const Ty &Val)

DiagnosticInfoOptimizationBase::Argument NV

NodeAddr< InstrNode * > Instr

NodeAddr< UseNode * > Use

This is an optimization pass for GlobalISel generic memory operations.

auto find(R &&Range, const T &Val)

Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.

std::function< bool(const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI, const Register Reg)> RegAllocFilterFunc

Filter function for register classes during regalloc.

bool all_of(R &&range, UnaryPredicate P)

Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.

constexpr uint64_t maxUIntN(uint64_t N)

Gets the maximum value for a N-bit unsigned integer.

SmallSet< Register, 16 > SmallVirtRegSet

LLVM_ABI FunctionPass * createGreedyRegisterAllocator()

Greedy register allocation pass - This pass implements a global register allocator for optimized buil...

Definition RegAllocGreedy.cpp:329

LLVM_ABI void initializeRAGreedyLegacyPass(PassRegistry &)

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

LLVM_ABI bool TimePassesIsEnabled

If the user specifies the -time-passes argument on an LLVM tool command line then the value of this b...

AnalysisManager< MachineFunction > MachineFunctionAnalysisManager

LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()

Returns the minimum set of Analyses that all machine function passes must preserve.

bool any_of(R &&range, UnaryPredicate P)

Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.

auto reverse(ContainerTy &&C)

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

bool none_of(R &&Range, UnaryPredicate P)

Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.

@ RS_Split2

Attempt more aggressive live range splitting that is guaranteed to make progress.

@ RS_Spill

Live range will be spilled. No more splitting will be attempted.

@ RS_Split

Attempt live range splitting if assignment is impossible.

@ RS_New

Newly created live range that has never been queued.

@ RS_Done

There is nothing more we can do to this live range.

@ RS_Assign

Only attempt assignment and eviction. Then requeue as RS_Split.

FunctionAddr VTableAddr Count

constexpr bool isUInt(uint64_t x)

Checks if an unsigned integer fits into the given bit width.

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

LLVM_ABI VirtRegInfo AnalyzeVirtRegInBundle(MachineInstr &MI, Register Reg, SmallVectorImpl< std::pair< MachineInstr *, unsigned > > *Ops=nullptr)

AnalyzeVirtRegInBundle - Analyze how the current instruction or bundle uses a virtual register.

LLVM_ABI raw_fd_ostream & errs()

This returns a reference to a raw_ostream for standard error.

LLVM_ABI const float huge_valf

Use this rather than HUGE_VALF; the latter causes warnings on MSVC.

auto lower_bound(R &&Range, T &&Value)

Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...

Spiller * createInlineSpiller(const Spiller::RequiredAnalyses &Analyses, MachineFunction &MF, VirtRegMap &VRM, VirtRegAuxInfo &VRAI, LiveRegMatrix *Matrix=nullptr)

Create and return a spiller that will insert spill code directly instead of deferring though VirtRegM...

ArrayRef(const T &OneElt) -> ArrayRef< T >

OutputIt move(R &&Range, OutputIt Out)

Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

LLVM_ABI Printable printBlockFreq(const BlockFrequencyInfo &BFI, BlockFrequency Freq)

Print the block frequency Freq relative to the current functions entry frequency.

LLVM_ABI char & RAGreedyLegacyID

Greedy register allocator.

Definition RegAllocGreedy.cpp:292

static float normalizeSpillWeight(float UseDefFreq, unsigned Size, unsigned NumInstr)

Normalize the spill weight of a live interval.

LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)

Prints virtual and physical registers with or without a TRI instance.

LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

Implement std::hash so that hash_code can be used in STL containers.

Definition RegAllocGreedy.cpp:176

EdgeBundles * Bundles

Definition RegAllocGreedy.cpp:185

LiveStacks * LSS

Definition RegAllocGreedy.cpp:190

VirtRegMap * VRM

Definition RegAllocGreedy.cpp:177

SlotIndexes * Indexes

Definition RegAllocGreedy.cpp:180

MachineBlockFrequencyInfo * MBFI

Definition RegAllocGreedy.cpp:181

LiveIntervals * LIS

Definition RegAllocGreedy.cpp:178

LiveRegMatrix * LRM

Definition RegAllocGreedy.cpp:179

RegAllocEvictionAdvisorProvider * EvictProvider

Definition RegAllocGreedy.cpp:192

MachineOptimizationRemarkEmitter * ORE

Definition RegAllocGreedy.cpp:184

LiveDebugVariables * DebugVars

Definition RegAllocGreedy.cpp:187

SpillPlacement * SpillPlacer

Definition RegAllocGreedy.cpp:186

RegAllocPriorityAdvisorProvider * PriorityProvider

Definition RegAllocGreedy.cpp:193

MachineDominatorTree * DomTree

Definition RegAllocGreedy.cpp:182

MachineLoopInfo * Loops

Definition RegAllocGreedy.cpp:183

RequiredAnalyses()=delete

constexpr bool any() const

This class is basically a combination of TimeRegion and Timer.

BlockConstraint - Entry and exit constraints for a basic block.

BorderConstraint Exit

Constraint on block exit.

bool ChangesValue

True when this block changes the value of the live range.

BorderConstraint Entry

Constraint on block entry.

unsigned Number

Basic block number (from MBB::getNumber()).

Additional information about basic blocks where the current variable is live.

SlotIndex FirstDef

First non-phi valno->def, or SlotIndex().

bool LiveOut

Current reg is live out.

bool LiveIn

Current reg is live in.

SlotIndex LastInstr

Last instr accessing current reg.

SlotIndex FirstInstr

First instr accessing current reg.