RegAllocGreedy.cpp Source File (original) (raw)

69#include

70#include

71#include

72#include

74using namespace llvm;

76#define DEBUG_TYPE "regalloc"

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

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

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

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

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

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

98 " interference at a time"),

100

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

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

106

108 "enable-deferred-spilling", cl::Hidden,

109 cl::desc("Instead of spilling a variable right away, defer the actual "

110 "code insertion to the end of the allocation. That way the "

111 "allocator might still find a suitable coloring for this "

112 "variable because of other evicted variables."),

114

115

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

120

122 "grow-region-complexity-budget",

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

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

126

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

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

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

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

133

135 "greedy-reverse-local-assignment",

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

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

139

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

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

143 "percentage"),

145

148

151

153 "Greedy Register Allocator", false, false)

171

172#ifndef NDEBUG

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

174 "RS_New",

175 "RS_Assign",

176 "RS_Split",

177 "RS_Split2",

178 "RS_Spill",

179 "RS_Memory",

180 "RS_Done"

181};

182#endif

183

184

185

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

187

190}

191

194}

195

198

225}

226

227

228

229

230

231bool RAGreedy::LRE_CanEraseVirtReg(Register VirtReg) {

236 return true;

237 }

238

239

240

241

243 return false;

244}

245

246void RAGreedy::LRE_WillShrinkVirtReg(Register VirtReg) {

248 return;

249

250

254}

255

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

257 ExtraInfo->LRE_DidCloneVirtReg(New, Old);

258}

259

261

262 if (!Info.inBounds(Old))

263 return;

264

265

266

267

268

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

271 Info[New] = Info[Old];

272}

273

275 SpillerInstance.reset();

276 GlobalCand.clear();

277}

278

280

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

282

283

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

286

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

288 if (Stage == RS_New) {

290 ExtraInfo->setStage(Reg, Stage);

291 }

292

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

294

295

296

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

298}

299

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

303 unsigned Prio;

305

307

308

311

312

313

314

315 static unsigned MemOp = 0;

317 } else {

318

319

322 (!ReverseLocalAssignment &&

325 unsigned GlobalBit = 0;

326

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

329

330

331

332 if (!ReverseLocalAssignment)

334 else {

335

336

337

339 }

340 } else {

341

342

343

345 GlobalBit = 1;

346 }

347

348

349

350

351

352

353

354

355

356

357

358

359

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

362

363 if (RegClassPriorityTrumpsGlobalness)

365 else

367

368

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

370

371

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

374 }

375

376 return Prio;

377}

378

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

380

383}

384

386

388 if (CurQueue.empty())

389 return nullptr;

391 CurQueue.pop();

392 return LI;

393}

394

395

396

397

398

399

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

408 if (I.isHint())

409 return *I;

410 else

411 PhysReg = *I;

412 }

413 }

415 return PhysReg;

416

417

418

419

420

422 if (Order.isHint(Hint)) {

423 MCRegister PhysHint = Hint.asMCReg();

425

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

427 FixedRegisters)) {

428 evictInterference(VirtReg, PhysHint, NewVRegs);

429 return PhysHint;

430 }

431

432

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

434 return 0;

435

436

437

438 SetOfBrokenHints.insert(&VirtReg);

439 }

440

441

443

444

446 return PhysReg;

447

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

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

451 return CheapReg ? CheapReg : PhysReg;

452}

453

454

455

456

457

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

461

464 };

465

468 if (Reg == FromReg)

469 continue;

470

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

475 return true;

476 }

477 }

478 return false;

479}

480

481

482

483

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

487

488

489

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

491

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

494

495

499

500

501

502

505 }

506

507

509

511 continue;

512

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

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

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

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

518 ++NumEvicted;

520 }

521}

522

523

524

527 if (!CSR)

528 return false;

529

531}

532

533std::optional

536 unsigned CostPerUseLimit) const {

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

538

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

540

543 if (MinCost >= CostPerUseLimit) {

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

546 return std::nullopt;

547 }

548

549

550

551 if (RegCosts[Order.getOrder().back()] >= CostPerUseLimit) {

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

554 << " regs.\n");

555 }

556 }

557 return OrderLimit;

558}

559

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

563 return false;

564

565

566 if (CostPerUseLimit == 1 && isUnusedCalleeSavedReg(PhysReg)) {

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

570 << '\n');

571 return false;

572 }

573 return true;

574}

575

576

577

578

579

587

588 MCRegister BestPhys = EvictAdvisor->tryFindEvictionCandidate(

589 VirtReg, Order, CostPerUseLimit, FixedRegisters);

591 evictInterference(VirtReg, BestPhys, NewVRegs);

592 return BestPhys;

593}

594

595

596

597

598

599

600

601

602

603

607

608

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

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

614

623

625 continue;

626

627

628 unsigned Ins = 0;

629

630

634 ++Ins;

640 }

641

642

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

647 return false;

648 }

649

650

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

660 }

661 }

662

663

664 while (Ins--)

666 }

667 Cost = StaticCost;

668

669

670

673}

674

675

676

679 const unsigned GroupSize = 8;

681 unsigned TBS[GroupSize];

682 unsigned B = 0, T = 0;

683

686

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

690 if (++T == GroupSize) {

692 T = 0;

693 }

694 continue;

695 }

696

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

699

700

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

705 SA->getFirstSplitPoint(Number)))

706 return false;

707

710 else

712

713

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

716 else

718

719 if (++B == GroupSize) {

721 B = 0;

722 }

723 }

724

727 return true;

728}

729

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

731

732 BitVector Todo = SA->getThroughBlocks();

734 unsigned AddedTo = 0;

735#ifndef NDEBUG

736 unsigned Visited = 0;

737#endif

738

740 while (true) {

742

743 for (unsigned Bundle : NewBundles) {

744

746

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

748 return false;

749 Budget -= Blocks.size();

752 continue;

754

756#ifndef NDEBUG

757 ++Visited;

758#endif

759 }

760 }

761

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

763 break;

764

765

766

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

768 if (Cand.PhysReg) {

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

770 return false;

771 } else {

772

773

774

775

776

777 bool PrefSpill = true;

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

779

780

781

782

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

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

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

787 }))

788 PrefSpill = false;

789 }

790 if (PrefSpill)

791 SpillPlacer->addPrefSpill(NewBlocks, true);

792 }

793 AddedTo = ActiveBlocks.size();

794

795

797 }

799 return true;

800}

801

802

803

804

805

806

807

808

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

810

811 if (!SA->getNumThroughBlocks())

812 return false;

813

814

816

818

819

820

821 SpillPlacer->prepare(Cand.LiveBundles);

822

823

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

827 return false;

828 }

829

830 if (!growRegion(Cand)) {

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

832 return false;

833 }

834

835 SpillPlacer->finish();

836

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

839 return false;

840 }

841

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

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

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

846 });

847 return true;

848}

849

850

851

857

859

860

863 }

865}

866

867

868

869

870

871BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,

874 const BitVector &LiveBundles = Cand.LiveBundles;

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

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

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

881 unsigned Ins = 0;

882

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

884

889 while (Ins--)

891 }

892

893 for (unsigned Number : Cand.ActiveBlocks) {

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

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

896 if (!RegIn && !RegOut)

897 continue;

898 if (RegIn && RegOut) {

899

900 Cand.Intf.moveToBlock(Number);

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

904 }

905 continue;

906 }

907

909 }

910 return GlobalCost;

911}

912

913

914

915

916

917

918

919

920

921

922

923

924

925void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit,

927

928

929 const unsigned NumGlobalIntvs = LREdit.size();

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

931 << " globals.\n");

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

933

934

935

936

939

940

944 unsigned IntvIn = 0, IntvOut = 0;

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

948 if (CandIn != NoCand) {

949 GlobalSplitCandidate &Cand = GlobalCand[CandIn];

950 IntvIn = Cand.IntvIdx;

951 Cand.Intf.moveToBlock(Number);

952 IntfIn = Cand.Intf.first();

953 }

954 }

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

957 if (CandOut != NoCand) {

958 GlobalSplitCandidate &Cand = GlobalCand[CandOut];

959 IntvOut = Cand.IntvIdx;

960 Cand.Intf.moveToBlock(Number);

961 IntfOut = Cand.Intf.last();

962 }

963 }

964

965

966 if (!IntvIn && !IntvOut) {

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

969 SE->splitSingleBlock(BI);

970 continue;

971 }

972

973 if (IntvIn && IntvOut)

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

975 else if (IntvIn)

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

977 else

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

979 }

980

981

982

983

984 BitVector Todo = SA->getThroughBlocks();

985 for (unsigned UsedCand : UsedCands) {

989 continue;

991

992 unsigned IntvIn = 0, IntvOut = 0;

994

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

996 if (CandIn != NoCand) {

997 GlobalSplitCandidate &Cand = GlobalCand[CandIn];

998 IntvIn = Cand.IntvIdx;

999 Cand.Intf.moveToBlock(Number);

1000 IntfIn = Cand.Intf.first();

1001 }

1002

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

1004 if (CandOut != NoCand) {

1005 GlobalSplitCandidate &Cand = GlobalCand[CandOut];

1006 IntvOut = Cand.IntvIdx;

1007 Cand.Intf.moveToBlock(Number);

1008 IntfOut = Cand.Intf.last();

1009 }

1010 if (!IntvIn && !IntvOut)

1011 continue;

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

1013 }

1014 }

1015

1016 ++NumGlobalSplits;

1017

1019 SE->finish(&IntvMap);

1021

1022 unsigned OrigBlocks = SA->getNumLiveBlocks();

1023

1024

1025

1026

1027

1028

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

1031

1032

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

1034 continue;

1035

1036

1037

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

1039 ExtraInfo->setStage(Reg, RS_Spill);

1040 continue;

1041 }

1042

1043

1044

1045 if (IntvMap[I] < NumGlobalIntvs) {

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

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

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

1049

1050 ExtraInfo->setStage(Reg, RS_Split2);

1051 }

1052 continue;

1053 }

1054

1055

1056

1057 }

1058

1060 MF->verify(this, "After splitting live range around region", &errs());

1061}

1062

1068 unsigned NumCands = 0;

1071

1072

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

1074 if (HasCompact) {

1075

1076 NumCands = 1;

1078 } else {

1079

1080

1081 BestCost = SpillCost;

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

1084 }

1085

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

1087 NumCands, false );

1088

1089

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

1092

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

1094}

1095

1096unsigned

1097RAGreedy::calculateRegionSplitCostAroundReg(MCPhysReg PhysReg,

1100 unsigned &NumCands,

1101 unsigned &BestCand) {

1102

1103

1105 unsigned WorstCount = ~0u;

1106 unsigned Worst = 0;

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

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

1109 continue;

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

1111 if (Count < WorstCount) {

1112 Worst = CandIndex;

1113 WorstCount = Count;

1114 }

1115 }

1116 --NumCands;

1117 GlobalCand[Worst] = GlobalCand[NumCands];

1118 if (BestCand == NumCands)

1119 BestCand = Worst;

1120 }

1121

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

1123 GlobalCand.resize(NumCands+1);

1124 GlobalSplitCandidate &Cand = GlobalCand[NumCands];

1125 Cand.reset(IntfCache, PhysReg);

1126

1127 SpillPlacer->prepare(Cand.LiveBundles);

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

1131 return BestCand;

1132 }

1135 if (Cost >= BestCost) {

1137 if (BestCand == NoCand)

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

1139 else

1140 dbgs() << " worse than "

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

1142 });

1143 return BestCand;

1144 }

1145 if (!growRegion(Cand)) {

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

1147 return BestCand;

1148 }

1149

1150 SpillPlacer->finish();

1151

1152

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

1155 return BestCand;

1156 }

1157

1158 Cost += calcGlobalSplitCost(Cand, Order);

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

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

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

1164 });

1165 if (Cost < BestCost) {

1166 BestCand = NumCands;

1167 BestCost = Cost;

1168 }

1169 ++NumCands;

1170

1171 return BestCand;

1172}

1173

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

1177 unsigned &NumCands,

1178 bool IgnoreCSR) {

1179 unsigned BestCand = NoCand;

1180 for (MCPhysReg PhysReg : Order) {

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

1183 continue;

1184

1185 calculateRegionSplitCostAroundReg(PhysReg, Order, BestCost, NumCands,

1186 BestCand);

1187 }

1188

1189 return BestCand;

1190}

1191

1192unsigned RAGreedy::doRegionSplit(const LiveInterval &VirtReg, unsigned BestCand,

1193 bool HasCompact,

1196

1199

1200

1202

1203

1204 if (BestCand != NoCand) {

1205 GlobalSplitCandidate &Cand = GlobalCand[BestCand];

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

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

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

1211 (void)B;

1212 }

1213 }

1214

1215

1216 if (HasCompact) {

1217 GlobalSplitCandidate &Cand = GlobalCand.front();

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

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

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

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

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

1224 (void)B;

1225 }

1226 }

1227

1228 splitAroundRegion(LREdit, UsedCands);

1229 return 0;

1230}

1231

1232

1233

1234bool RAGreedy::trySplitAroundHintReg(MCPhysReg Hint,

1238

1239

1240

1242 return false;

1243

1244

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

1246 return false;

1247

1250

1251

1252

1253

1256 continue;

1257 Register OtherReg = Instr.getOperand(1).getReg();

1258 if (OtherReg == Reg) {

1259 OtherReg = Instr.getOperand(0).getReg();

1260 if (OtherReg == Reg)

1261 continue;

1262

1264 continue;

1265 }

1268 if (OtherPhysReg == Hint)

1270 }

1271

1272

1274 Cost *= Threshold;

1276 return false;

1277

1278 unsigned NumCands = 0;

1279 unsigned BestCand = NoCand;

1280 SA->analyze(&VirtReg);

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

1282 if (BestCand == NoCand)

1283 return false;

1284

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

1286 return true;

1287}

1288

1289

1290

1291

1292

1293

1294

1295

1296unsigned RAGreedy::tryBlockSplit(const LiveInterval &VirtReg,

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

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

1307 SE->splitSingleBlock(BI);

1308 }

1309

1310 if (LREdit.empty())

1311 return 0;

1312

1313

1315 SE->finish(&IntvMap);

1316

1317

1319

1320

1321

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

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

1325 ExtraInfo->setStage(LI, RS_Spill);

1326 }

1327

1329 MF->verify(this, "After splitting live range around basic blocks", &errs());

1330 return 0;

1331}

1332

1333

1334

1335

1336

1337

1338

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

1344

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

1347 true);

1348 if (!ConstrainedRC)

1349 return 0;

1351}

1352

1360

1361 for (auto [MI, OpIdx] : Ops) {

1367 continue;

1369 }

1370

1372 if (MO.isDef()) {

1374 Mask |= ~SubRegMask;

1375 } else

1376 Mask |= SubRegMask;

1377 }

1378

1379 return Mask;

1380}

1381

1382

1383

1388

1389

1390

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

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

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

1394 return false;

1395

1396

1398

1401 if (S.liveAt(Use))

1402 LiveAtMask |= S.LaneMask;

1403 }

1404

1405

1406

1408}

1409

1410

1411

1412

1413

1414

1415

1416

1417unsigned RAGreedy::tryInstructionSplit(const LiveInterval &VirtReg,

1421

1422

1423 bool SplitSubClass = true;

1426 return 0;

1427 SplitSubClass = false;

1428 }

1429

1430

1431

1434

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

1437 return 0;

1438

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

1441

1444 unsigned SuperRCNumAllocatableRegs =

1446

1447

1448

1449

1453 (SplitSubClass &&

1454 SuperRCNumAllocatableRegs ==

1457

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

1461 continue;

1462 }

1463 }

1464 SE->openIntv();

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

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

1467 SE->useIntv(SegStart, SegStop);

1468 }

1469

1470 if (LREdit.empty()) {

1472 return 0;

1473 }

1474

1476 SE->finish(&IntvMap);

1478

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

1480 return 0;

1481}

1482

1483

1484

1485

1486

1487

1488

1489

1490

1491

1492void RAGreedy::calcGapWeights(MCRegister PhysReg,

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

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

1498

1499

1504

1505 GapWeight.assign(NumGaps, 0.0f);

1506

1507

1511 continue;

1512

1513

1514

1515

1516

1517

1518

1519

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

1523

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

1525 if (++Gap == NumGaps)

1526 break;

1527 if (Gap == NumGaps)

1528 break;

1529

1530

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

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

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

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

1535 break;

1536 }

1537 if (Gap == NumGaps)

1538 break;

1539 }

1540 }

1541

1542

1547

1548

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

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

1551 if (++Gap == NumGaps)

1552 break;

1553 if (Gap == NumGaps)

1554 break;

1555

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

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

1559 break;

1560 }

1561 if (Gap == NumGaps)

1562 break;

1563 }

1564 }

1565}

1566

1567

1568

1569

1570unsigned RAGreedy::tryLocalSplit(const LiveInterval &VirtReg,

1573

1574

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

1576 return 0;

1577

1579

1580

1581

1582

1583

1584

1585

1586

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

1589 return 0;

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

1591

1593 dbgs() << "tryLocalSplit: ";

1594 for (const auto &Use : Uses)

1596 dbgs() << '\n';

1597 });

1598

1599

1600

1603

1606

1607 unsigned RI =

1609 unsigned RE = RMS.size();

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

1611

1614 continue;

1615

1616

1618 break;

1620 << Uses[I + 1]);

1621 RegMaskGaps.push_back(I);

1622

1623

1625 ++RI;

1626 }

1628 }

1629

1630

1631

1632

1633

1634

1635

1636

1637

1638

1639

1640

1641

1642

1643

1644

1645

1646

1647

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

1649

1650

1651 unsigned BestBefore = NumGaps;

1652 unsigned BestAfter = 0;

1653 float BestDiff = 0;

1654

1655 const float blockFreq =

1659

1660 for (MCPhysReg PhysReg : Order) {

1662

1663

1664 calcGapWeights(PhysReg, GapWeight);

1665

1666

1668 for (unsigned Gap : RegMaskGaps)

1670

1671

1672

1673

1674

1675 unsigned SplitBefore = 0, SplitAfter = 1;

1676

1677

1678

1679 float MaxGap = GapWeight[0];

1680

1681 while (true) {

1682

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

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

1685

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

1688

1689

1690 if (!LiveBefore && !LiveAfter) {

1692 break;

1693 }

1694

1695 bool Shrink = true;

1696

1697

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

1699

1700

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

1702

1704

1705

1706

1707

1708

1710 blockFreq * (NewGaps + 1),

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

1713 1);

1714

1715

1717 if (EstWeight * Hysteresis >= MaxGap) {

1718 Shrink = false;

1719 float Diff = EstWeight - MaxGap;

1720 if (Diff > BestDiff) {

1723 BestBefore = SplitBefore;

1724 BestAfter = SplitAfter;

1725 }

1726 }

1727 }

1728

1729

1730 if (Shrink) {

1731 if (++SplitBefore < SplitAfter) {

1733

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

1735 MaxGap = GapWeight[SplitBefore];

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

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

1738 }

1739 continue;

1740 }

1741 MaxGap = 0;

1742 }

1743

1744

1745 if (SplitAfter >= NumGaps) {

1747 break;

1748 }

1749

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

1752 }

1753 }

1754

1755

1756 if (BestBefore == NumGaps)

1757 return 0;

1758

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

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

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

1762

1764 SE->reset(LREdit);

1765

1766 SE->openIntv();

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

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

1769 SE->useIntv(SegStart, SegStop);

1771 SE->finish(&IntvMap);

1773

1774

1775

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

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

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

1779 if (NewGaps >= NumGaps) {

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

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

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

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

1786 }

1788 }

1789 ++NumLocalSplits;

1790

1791 return 0;

1792}

1793

1794

1795

1796

1797

1798

1799

1800

1804

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

1806 return 0;

1807

1808

1812 SA->analyze(&VirtReg);

1813 Register PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs);

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

1815 return PhysReg;

1816 return tryInstructionSplit(VirtReg, Order, NewVRegs);

1817 }

1818

1821

1822 SA->analyze(&VirtReg);

1823

1824

1825

1826

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

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

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

1830 return PhysReg;

1831 }

1832

1833

1834 return tryBlockSplit(VirtReg, Order, NewVRegs);

1835}

1836

1837

1838

1839

1840

1841

1844 if (MO.isTied())

1845 return true;

1846

1847 return false;

1848}

1849

1850

1851

1857 if (PhysReg == AssignedReg)

1858 return false;

1860}

1861

1862

1863

1864

1865

1866

1867

1868

1869

1870bool RAGreedy::mayRecolorAllInterferences(

1872 SmallLISet &RecoloringCandidates, const SmallVirtRegSet &FixedRegisters) {

1874

1877

1878

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

1883 CutOffInfo |= CO_Interf;

1884 return false;

1885 }

1887

1888

1889

1890

1891

1892

1893

1894

1895

1896

1897

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

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

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

1906 return false;

1907 }

1908 RecoloringCandidates.insert(Intf);

1909 }

1910 }

1911 return true;

1912}

1913

1914

1915

1916

1917

1918

1919

1920

1921

1922

1923

1924

1925

1926

1927

1928

1929

1930

1931

1932

1933

1934

1935

1936

1937

1938

1939

1940

1941

1942

1943

1944

1945

1946

1947

1948

1949

1950

1951

1952

1953

1954

1955

1956

1957unsigned RAGreedy::tryLastChanceRecoloring(const LiveInterval &VirtReg,

1961 RecoloringStack &RecolorStack,

1962 unsigned Depth) {

1964 return ~0u;

1965

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

1967

1968 const ssize_t EntryStackSize = RecolorStack.size();

1969

1970

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

1973

1974

1975

1976

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

1979 CutOffInfo |= CO_Depth;

1980 return ~0u;

1981 }

1982

1983

1984 SmallLISet RecoloringCandidates;

1985

1986

1987

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

1991

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

1996 RecoloringCandidates.clear();

1997 CurrentNewVRegs.clear();

1998

1999

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

2004

2005 continue;

2006 }

2007

2008

2009

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

2011 FixedRegisters)) {

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

2013 continue;

2014 }

2015

2016

2017

2018

2019 PQueue RecoloringQueue;

2020 for (const LiveInterval *RC : RecoloringCandidates) {

2021 Register ItVirtReg = RC->reg();

2022 enqueue(RecoloringQueue, RC);

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

2025

2026

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

2028

2029

2031 }

2032

2033

2034

2035

2037

2038

2040

2041

2042

2043

2045 if (tryRecoloringCandidates(RecoloringQueue, CurrentNewVRegs,

2046 FixedRegisters, RecolorStack, Depth)) {

2047

2048 for (Register NewVReg : CurrentNewVRegs)

2050

2051

2054 return PhysReg;

2055 }

2056

2057

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

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

2060 FixedRegisters.erase(ThisVirtReg);

2061 return 0;

2062 }

2063

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

2066

2067

2068 FixedRegisters = SaveFixedRegisters;

2070

2071

2072

2073

2074

2075 for (Register R : CurrentNewVRegs) {

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

2077 continue;

2079 }

2080

2081

2082

2083

2084

2085

2086

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

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

2091

2094 }

2095

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

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

2102 }

2103

2104

2105 RecolorStack.resize(EntryStackSize);

2106 }

2107

2108

2109 return ~0u;

2110}

2111

2112

2113

2114

2115

2116

2117

2118

2119

2120bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,

2123 RecoloringStack &RecolorStack,

2124 unsigned Depth) {

2125 while (!RecoloringQueue.empty()) {

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

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

2129 RecolorStack, Depth + 1);

2130

2131

2132

2133

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

2135 return false;

2136

2137 if (!PhysReg) {

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

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

2141 continue;

2142 }

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

2145

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

2148 }

2149 return true;

2150}

2151

2152

2153

2154

2155

2158 CutOffInfo = CO_None;

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

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

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

2166 if (CutOffEncountered == CO_Depth)

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

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

2169 "cutoffs");

2170 else if (CutOffEncountered == CO_Interf)

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

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

2173 "to skip cutoffs");

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

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

2176 "depth for recoloring reached. Use "

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

2178 }

2179 return Reg;

2180}

2181

2182

2183

2184

2185

2186

2187

2188MCRegister RAGreedy::tryAssignCSRFirstTime(

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

2192

2193

2194 SA->analyze(&VirtReg);

2195 if (calcSpillCost() >= CSRCost)

2196 return PhysReg;

2197

2198

2199

2200 CostPerUseLimit = 1;

2201 return 0;

2202 }

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

2204

2205

2206 SA->analyze(&VirtReg);

2207 unsigned NumCands = 0;

2208 BlockFrequency BestCost = CSRCost;

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

2210 NumCands, true );

2211 if (BestCand == NoCand)

2212

2213 return PhysReg;

2214

2215

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

2217 return 0;

2218 }

2219 return PhysReg;

2220}

2221

2223

2224 SetOfBrokenHints.remove(&LI);

2225}

2226

2227void RAGreedy::initializeCSRCost() {

2228

2229

2233 return;

2234

2235

2237 if (!ActualEntry) {

2239 return;

2240 }

2241 uint64_t FixedEntry = 1 << 14;

2242 if (ActualEntry < FixedEntry)

2244 else if (ActualEntry <= UINT32_MAX)

2245

2247 else

2248

2249 CSRCost =

2251}

2252

2253

2254

2255

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

2259 continue;

2260

2261 Register OtherReg = Instr.getOperand(0).getReg();

2262 if (OtherReg == Reg) {

2263 OtherReg = Instr.getOperand(1).getReg();

2264 if (OtherReg == Reg)

2265 continue;

2266 }

2267

2270

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

2272 OtherPhysReg));

2273 }

2274}

2275

2276

2277

2278

2282 for (const HintInfo &Info : List) {

2283 if (Info.PhysReg != PhysReg)

2285 }

2286 return Cost;

2287}

2288

2289

2290

2291

2292

2293

2294

2295

2296

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

2298

2299

2300

2303 HintsInfo Info;

2306

2307

2308 Visited.insert(Reg);

2309 RecoloringCandidates.push_back(Reg);

2310

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

2313

2314 do {

2316

2317

2318 if (Reg.isPhysical())

2319 continue;

2320

2321

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

2325 continue;

2326 }

2327

2328

2329

2332

2333

2336 continue;

2337

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

2340

2341

2342 Info.clear();

2343 collectHintInfo(Reg, Info);

2344

2345

2346 if (CurrPhys != PhysReg) {

2348 BlockFrequency OldCopiesCost = getBrokenHintFreq(Info, CurrPhys);

2349 BlockFrequency NewCopiesCost = getBrokenHintFreq(Info, PhysReg);

2351 << "\nNew Cost: "

2353 if (OldCopiesCost < NewCopiesCost) {

2355 continue;

2356 }

2357

2358

2359

2361

2364 }

2365

2366

2367 for (const HintInfo &HI : Info) {

2368 if (Visited.insert(HI.Reg).second)

2370 }

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

2372}

2373

2374

2375

2376

2377

2378

2379

2380

2381

2382

2383

2384

2385

2386

2387

2388

2389

2390

2391

2392

2393

2394

2395

2396

2397

2398

2399

2400

2401

2402

2403

2404

2405

2406

2407

2408

2409

2410void RAGreedy::tryHintsRecoloring() {

2411 for (const LiveInterval *LI : SetOfBrokenHints) {

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

2414

2415

2417 continue;

2418 tryHintRecoloring(*LI);

2419 }

2420}

2421

2425 RecoloringStack &RecolorStack,

2426 unsigned Depth) {

2428

2429 auto Order =

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

2433

2434

2435

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

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

2439 CostPerUseLimit, NewVRegs);

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

2441

2442

2443 return CSRReg;

2444 } else

2445 return PhysReg;

2446 }

2447

2448 if (!NewVRegs.empty())

2449 return 0;

2450

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

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

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

2454

2455

2456

2457

2460 tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit,

2461 FixedRegisters)) {

2463

2464

2465

2466

2467

2468 if (Hint && Hint != PhysReg)

2469 SetOfBrokenHints.insert(&VirtReg);

2470 return PhysReg;

2471 }

2472

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

2474

2475

2476

2477

2479 ExtraInfo->setStage(VirtReg, RS_Split);

2482 return 0;

2483 }

2484

2486

2487 unsigned NewVRegSizeBefore = NewVRegs.size();

2488 Register PhysReg = trySplit(VirtReg, Order, NewVRegs, FixedRegisters);

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

2490 return PhysReg;

2491 }

2492

2493

2494

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

2497 RecolorStack, Depth);

2498 }

2499

2500

2503 ExtraInfo->getStage(VirtReg) < RS_Memory) {

2504

2505

2506

2507

2508 ExtraInfo->setStage(VirtReg, RS_Memory);

2509 LLVM_DEBUG(dbgs() << "Do as if this register is in memory\n");

2511 } else {

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

2517

2518

2519

2520

2525

2527 MF->verify(this, "After spilling", &errs());

2528 }

2529

2530

2531

2532 return 0;

2533}

2534

2536 using namespace ore;

2537 if (Spills) {

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

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

2540 }

2541 if (FoldedSpills) {

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

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

2544 << " total folded spills cost ";

2545 }

2546 if (Reloads) {

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

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

2549 }

2550 if (FoldedReloads) {

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

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

2553 << " total folded reloads cost ";

2554 }

2555 if (ZeroCostFoldedReloads)

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

2557 << " zero cost folded reloads ";

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

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

2561 }

2562}

2563

2565 RAGreedyStats Stats;

2567 int FI;

2568

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

2572 };

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

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

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

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

2577 };

2580 if (DestSrc) {

2583 Register SrcReg = Src.getReg();

2585

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

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

2591 }

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

2596 }

2597 if (SrcReg != DestReg)

2599 }

2600 continue;

2601 }

2602

2605 ++Stats.Reloads;

2606 continue;

2607 }

2610 continue;

2611 }

2613 llvm::any_of(Accesses, isSpillSlotAccess)) {

2614 if (!isPatchpointInstr(MI)) {

2615 Stats.FoldedReloads += Accesses.size();

2616 continue;

2617 }

2618

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

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

2626 continue;

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

2629 else

2631 }

2632

2633 for (unsigned Slot : FoldedReloads)

2634 ZeroCostFoldedReloads.erase(Slot);

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

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

2637 continue;

2638 }

2639 Accesses.clear();

2641 llvm::any_of(Accesses, isSpillSlotAccess)) {

2642 Stats.FoldedSpills += Accesses.size();

2643 }

2644 }

2645

2646

2648 Stats.ReloadsCost = RelFreq * Stats.Reloads;

2649 Stats.FoldedReloadsCost = RelFreq * Stats.FoldedReloads;

2650 Stats.SpillsCost = RelFreq * Stats.Spills;

2651 Stats.FoldedSpillsCost = RelFreq * Stats.FoldedSpills;

2652 Stats.CopiesCost = RelFreq * Stats.Copies;

2654}

2655

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

2657 RAGreedyStats Stats;

2658

2659

2661 Stats.add(reportStats(SubLoop));

2662

2664

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

2667

2668 if ( Stats .isEmpty()) {

2669 using namespace ore;

2670

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

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

2674 Stats.report(R);

2675 R << "generated in loop";

2676 return R;

2677 });

2678 }

2680}

2681

2682void RAGreedy::reportStats() {

2684 return;

2685 RAGreedyStats Stats;

2687 Stats.add(reportStats(L));

2688

2690 if ( Loops ->getLoopFor(&MBB))

2691 Stats.add(computeStats(MBB));

2692 if ( Stats .isEmpty()) {

2693 using namespace ore;

2694

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

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

2698 Loc = DILocation::get(SP->getContext(), SP->getLine(), 1, SP);

2700 &MF->front());

2701 Stats.report(R);

2702 R << "generated in function";

2703 return R;

2704 });

2705 }

2706}

2707

2708bool RAGreedy::hasVirtRegAlloc() {

2712 continue;

2714 if (!RC)

2715 continue;

2717 return true;

2718 }

2719

2720 return false;

2721}

2722

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

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

2726

2727 MF = &mf;

2728 TII = MF->getSubtarget().getInstrInfo();

2729

2731 MF->verify(this, "Before greedy register allocator", &errs());

2732

2734 getAnalysis().getLIS(),

2735 getAnalysis().getLRM());

2736

2737

2738

2739 if (!hasVirtRegAlloc())

2740 return false;

2741

2742 Indexes = &getAnalysis().getSI();

2743

2744

2746 MBFI = &getAnalysis().getMBFI();

2747 DomTree = &getAnalysis().getDomTree();

2748 ORE = &getAnalysis().getORE();

2749 Loops = &getAnalysis().getLI();

2750 Bundles = &getAnalysis().getEdgeBundles();

2751 SpillPlacer = &getAnalysis().getResult();

2752 DebugVars = &getAnalysis().getLDV();

2753 auto &LSS = getAnalysis().getLS();

2754

2755 initializeCSRCost();

2756

2758 RegClassPriorityTrumpsGlobalness =

2762

2766

2767 ExtraInfo.emplace();

2768 EvictAdvisor =

2769 getAnalysis().getAdvisor(*MF, *this);

2770 PriorityAdvisor =

2771 getAnalysis().getAdvisor(*MF, *this);

2772

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

2774 SpillerInstance.reset(

2776

2777 VRAI->calculateSpillWeightsAndHints();

2778

2780

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

2783

2785 GlobalCand.resize(32);

2786 SetOfBrokenHints.clear();

2787

2789 tryHintsRecoloring();

2790

2792 MF->verify(this, "Before post optimization", &errs());

2794 reportStats();

2795

2797 return true;

2798}

This file implements the BitVector class.

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

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

Analysis containing CSE Info

#define clEnumValN(ENUMVAL, FLAGNAME, DESC)

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

DenseMap< Block *, BlockRelaxAux > Blocks

const HexagonInstrInfo * TII

This file implements an indexed map.

block placement Basic Block Placement Stats

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

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)

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 hasTiedDef(MachineRegisterInfo *MRI, unsigned reg)

Return true if reg has any tied def operand.

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.

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.

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)

Greedy Register Allocator

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 ...

static cl::opt< bool > EnableDeferredSpilling("enable-deferred-spilling", cl::Hidden, cl::desc("Instead of spilling a variable right away, defer the actual " "code insertion to the end of the allocation. That way the " "allocator might still find a suitable coloring for this " "variable because of other evicted variables."), cl::init(false))

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)

Remove Loads Into Fake Uses

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

SI optimize exec mask operations pre RA

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)

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(unsigned VirtReg, const VirtRegMap &VRM, const RegisterClassInfo &RegClassInfo, const LiveRegMatrix *Matrix)

Create a new AllocationOrder for VirtReg.

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.

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.

ArrayRef< T > slice(size_t N, size_t M) const

slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array.

bool test(unsigned Idx) const

static BlockFrequency max()

Returns the maximum possible frequency, the saturation value.

uint64_t getFrequency() const

Returns the frequency as a fixpoint number scaled by the entry frequency.

ArrayRef< unsigned > getBlocks(unsigned Bundle) const

getBlocks - Return an array of blocks that are connected to Bundle.

unsigned getBundle(unsigned N, bool Out) const

getBundle - Return the ingoing (Out = false) or outgoing (Out = true) bundle number for basic block N

unsigned getNumBundles() const

getNumBundles - Return the total number of bundles in the CFG.

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

bool hasOptSize() const

Optimize this function for size (-Os) or minimum size (-Oz).

LLVMContext & getContext() const

getContext - Return a reference to the LLVMContext associated with this function.

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.

void init(MachineFunction *mf, LiveIntervalUnion *liuarray, SlotIndexes *indexes, LiveIntervals *lis, const TargetRegisterInfo *tri)

init - Prepare cache for a new function.

unsigned getMaxCursors() const

getMaxCursors - Return the maximum number of concurrent cursors that can be supported.

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

void emitError(const Instruction *I, const Twine &ErrorStr)

emitError - Emit an error message to the currently installed error handler with optional location inf...

void splitRegister(Register OldReg, ArrayRef< Register > NewRegs, LiveIntervals &LIS)

splitRegister - Move any user variables in OldReg to the live ranges in NewRegs where they are live.

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())

SegmentIter find(SlotIndex x)

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.

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.

SlotIndex getInstructionIndex(const MachineInstr &Instr) const

Returns the base index of the given instruction.

LiveRange & getRegUnit(unsigned Unit)

Return the live range for register unit Unit.

ArrayRef< SlotIndex > getRegMaskSlotsInBlock(unsigned MBBNum) const

Returns a sorted array of slot indices of all instructions with register mask operands in the basic b...

LiveInterval & getInterval(Register Reg)

MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const

If LI is confined to a single basic block, return a pointer to that block.

ArrayRef< Register > regs() const

This class represents the liveness of a register, stack slot, etc.

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.

iterator find(SlotIndex Pos)

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

bool checkRegMaskInterference(const LiveInterval &VirtReg, MCRegister PhysReg=MCRegister::NoRegister)

Check for regmask interference only.

void unassign(const LiveInterval &VirtReg)

Unassign VirtReg from its PhysReg.

bool isPhysRegUsed(MCRegister PhysReg) const

Returns true if the given PhysReg has any live intervals assigned.

LiveIntervalUnion::Query & query(const LiveRange &LR, MCRegUnit RegUnit)

Query a line of the assigned virtual register matrix directly.

@ IK_VirtReg

Virtual register interference.

void assign(const LiveInterval &VirtReg, MCRegister PhysReg)

Assign VirtReg to PhysReg.

InterferenceKind checkInterference(const LiveInterval &VirtReg, MCRegister PhysReg)

Check for interference before assigning VirtReg to PhysReg.

LiveIntervalUnion * getLiveUnions()

Directly access the live interval unions per regunit.

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

iterator_range< MCRegUnitIterator > regunits(MCRegister Reg) const

Returns an iterator range over all regunits for Reg.

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)

int getNumber() const

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

iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)

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

BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const

getblockFreq - Return block frequency.

double getBlockFreqRelativeToEntryBlock(const MachineBasicBlock *MBB) const

Compute the frequency of the block, relative to the entry block.

BlockFrequency getEntryFreq() const

Divide a block's BlockFrequency::getFrequency() value by this value to obtain the entry block - relat...

Analysis pass which computes a MachineDominatorTree.

The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.

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.

StringRef getName() const

getName - Return the name of the corresponding LLVM function.

MachineFrameInfo & getFrameInfo()

getFrameInfo - Return the frame info object for the current function.

MachineBasicBlock * getBlockNumbered(unsigned N) const

getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...

bool verify(Pass *p=nullptr, const char *Banner=nullptr, raw_ostream *OS=nullptr, bool AbortOnError=true) const

Run the current MachineFunction through the machine code verifier, useful for debugger use.

Function & getFunction()

Return the LLVM function that this machine code represents.

Representation of each machine instruction.

bool isImplicitDef() const

A description of a memory reference used in the backend.

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,...

getSimpleHint - same as getRegAllocationHint except it will only return a target independent hint.

const TargetRegisterClass * getRegClass(Register Reg) const

Return the register class of the specified virtual register.

bool reg_nodbg_empty(Register RegNo) const

reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions.

iterator_range< def_iterator > def_operands(Register Reg) const

LaneBitmask getMaxLaneMaskForVReg(Register Reg) const

Returns a mask covering all bits that can appear in lane masks of subregisters of the virtual registe...

unsigned getNumVirtRegs() const

getNumVirtRegs - Return the number of virtual registers created.

iterator_range< reg_instr_nodbg_iterator > reg_nodbg_instructions(Register Reg) const

Spiller & spiller() override

void releaseMemory() override

releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...

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

bool runOnMachineFunction(MachineFunction &mf) override

Perform register allocation.

const LiveInterval * dequeue() override

dequeue - Return the next unassigned register, or NULL.

RAGreedy(const RegAllocFilterFunc F=nullptr)

void enqueueImpl(const LiveInterval *LI) override

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

void getAnalysisUsage(AnalysisUsage &AU) const override

RAGreedy analysis usage.

void aboutToRemoveInterval(const LiveInterval &) override

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

RegAllocBase provides the register allocation driver and interface that can be extended to add intere...

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.

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

bool isUnusedCalleeSavedReg(MCRegister PhysReg) const

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

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

bool canAllocatePhysReg(unsigned CostPerUseLimit, MCRegister PhysReg) const

unsigned getLastCostChange(const TargetRegisterClass *RC) const

Get the position of the last cost change in getOrder(RC).

bool isProperSubClass(const TargetRegisterClass *RC) const

isProperSubClass - Returns true if RC has a legal super-class with more allocatable registers.

unsigned getNumAllocatableRegs(const TargetRegisterClass *RC) const

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

uint8_t getMinCost(const TargetRegisterClass *RC) const

Get the minimum register cost in RC's allocation order.

MCRegister getLastCalleeSavedAlias(MCRegister PhysReg) const

getLastCalleeSavedAlias - Returns the last callee saved register that overlaps PhysReg,...

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.

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.

@ InstrDist

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

int getApproxInstrDistance(SlotIndex other) const

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

SlotIndex getRegSlot(bool EC=false) const

Returns the register use/def slot in the current instruction for a normal or early-clobber def.

SlotIndex getLastIndex()

Returns the base index of the last slot in this analysis.

SlotIndex getMBBStartIdx(unsigned Num) const

Returns the first index in the given basic block number.

void packIndexes()

Renumber all indexes using the default instruction distance.

SlotIndex getZeroIndex()

Returns the zero index for this analysis.

MachineInstr * getInstructionFromIndex(SlotIndex index) const

Returns the instruction for the given index, or null if the given index has no instruction associated...

SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...

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.

void addConstraints(ArrayRef< BlockConstraint > LiveBlocks)

addConstraints - Add constraints and biases.

bool finish()

finish - Compute the optimal spill code placement given the constraints.

void addPrefSpill(ArrayRef< unsigned > Blocks, bool Strong)

addPrefSpill - Add PrefSpill constraints to all blocks listed.

void prepare(BitVector &RegBundles)

prepare - Reset state and prepare for a new spill placement computation.

bool scanActiveBundles()

scanActiveBundles - Perform an initial scan of all bundles activated by addConstraints and addLinks,...

void addLinks(ArrayRef< unsigned > Links)

addLinks - Add transparent blocks with the given numbers.

void iterate()

iterate - Update the network iteratively until convergence, or new bundles are found.

@ 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.

ArrayRef< unsigned > getRecentPositive()

getRecentPositive - Return an array of bundles that became positive during the previous call to scanA...

BlockFrequency getBlockFrequency(unsigned Number) const

getBlockFrequency - Return the estimated block execution frequency per function invocation.

virtual void spill(LiveRangeEdit &LRE)=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.

TargetInstrInfo - Interface to description of machine instruction set.

virtual std::pair< unsigned, unsigned > getPatchpointUnfoldableRange(const MachineInstr &MI) const

For a patchpoint, stackmap, or statepoint intrinsic, return the range of operands which can't be fold...

bool isFullCopyInstr(const MachineInstr &MI) const

virtual bool hasStoreToStackSlot(const MachineInstr &MI, SmallVectorImpl< const MachineMemOperand * > &Accesses) const

If the specified machine instruction has a store to a stack slot, return true along with the FrameInd...

virtual Register isLoadFromStackSlot(const MachineInstr &MI, int &FrameIndex) const

If the specified machine instruction is a direct load from a stack slot, return the virtual or physic...

virtual Register isStoreToStackSlot(const MachineInstr &MI, int &FrameIndex) const

If the specified machine instruction is a direct store to a stack slot, return the virtual or physica...

std::optional< DestSourcePair > isCopyInstr(const MachineInstr &MI) const

If the specific machine instruction is a instruction that moves/copies value from one register to ano...

virtual bool hasLoadFromStackSlot(const MachineInstr &MI, SmallVectorImpl< const MachineMemOperand * > &Accesses) const

If the specified machine instruction has a load from a stack slot, return true along with the FrameIn...

bool contains(Register Reg) const

Return true if the specified register is included in this register class.

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 bool shouldUseDeferredSpillingForVirtReg(const MachineFunction &MF, const LiveInterval &VirtReg) const

Deferred spilling delays the spill insertion of a virtual register after every other allocation.

virtual bool shouldRegionSplitForVirtReg(const MachineFunction &MF, const LiveInterval &VirtReg) const

Region split has a high compile time cost especially for large live range.

virtual bool shouldUseLastChanceRecoloringForVirtReg(const MachineFunction &MF, const LiveInterval &VirtReg) const

Last chance recoloring has a high compile time cost especially for targets with a lot of registers.

virtual unsigned getCSRFirstUseCost() const

Allow the target to override the cost of using a callee-saved register for the first time.

LaneBitmask getCoveringLanes() const

The lane masks returned by getSubRegIndexLaneMask() above can only be used to determine if sub-regist...

ArrayRef< uint8_t > getRegisterCosts(const MachineFunction &MF) const

Get a list of cost values for all registers that correspond to the index returned by RegisterCostTabl...

virtual bool reverseLocalAssignment() const

Allow the target to reverse allocation order of local live ranges.

LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const

Return a bitmask representing the parts of a register that are covered by SubIdx.

virtual const TargetRegisterClass * getLargestLegalSuperClass(const TargetRegisterClass *RC, const MachineFunction &) const

Returns the largest super class of RC that is legal to use in the current sub-target and has the same...

MCRegister getSubReg(MCRegister Reg, unsigned Idx) const

Returns the physical register number of sub-register "Index" for physical register RegNo.

bool regsOverlap(Register RegA, Register RegB) const

Returns true if the two registers are equal or alias each other.

const char * getRegClassName(const TargetRegisterClass *Class) const

Returns the name of the register class.

virtual bool regClassPriorityTrumpsGlobalness(const MachineFunction &MF) const

When prioritizing live ranges in register allocation, if this hook returns true then the AllocationPr...

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

bool hasKnownPreference(Register VirtReg) const

returns true if VirtReg has a known preferred register.

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

int getNumOccurrences() const

Reg

All possible values of the reg field in the ModR/M byte.

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

This is an optimization pass for GlobalISel generic memory operations.

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.

FunctionPass * createGreedyRegisterAllocator()

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

bool TimePassesIsEnabled

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

char & RAGreedyID

Greedy register allocator.

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)

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.

@ RS_Memory

Live range is in memory.

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

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

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.

raw_fd_ostream & errs()

This returns a reference to a raw_ostream for standard error.

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...

Printable printBlockFreq(const BlockFrequencyInfo &BFI, BlockFrequency Freq)

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

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

Normalize the spill weight of a live interval.

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.

Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

uint64_t maxUIntN(uint64_t N)

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

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.