MachineScheduler.cpp Source File (original) (raw)

52#include "llvm/Config/llvm-config.h"

63#include

64#include

65#include

66#include

67#include

68#include

69#include

70#include

71#include

72#include

74using namespace llvm;

76#define DEBUG_TYPE "machine-scheduler"

79 "Number of instructions in source order after pre-RA scheduling");

81 "Number of instructions in source order after post-RA scheduling");

83 "Number of instructions scheduled by pre-RA scheduler");

85 "Number of instructions scheduled by post-RA scheduler");

86 STATISTIC(NumClustered, "Number of load/store pairs clustered");

89 "Number of scheduling units chosen from top queue pre-RA");

91 "Number of scheduling units chosen from bottom queue pre-RA");

93 "Number of scheduling units chosen for NoCand heuristic pre-RA");

95 "Number of scheduling units chosen for Only1 heuristic pre-RA");

97 "Number of scheduling units chosen for PhysReg heuristic pre-RA");

99 "Number of scheduling units chosen for RegExcess heuristic pre-RA");

101 "Number of scheduling units chosen for RegCritical heuristic pre-RA");

103 "Number of scheduling units chosen for Stall heuristic pre-RA");

105 "Number of scheduling units chosen for Cluster heuristic pre-RA");

107 "Number of scheduling units chosen for Weak heuristic pre-RA");

109 "Number of scheduling units chosen for RegMax heuristic pre-RA");

111 NumResourceReducePreRA,

112 "Number of scheduling units chosen for ResourceReduce heuristic pre-RA");

114 NumResourceDemandPreRA,

115 "Number of scheduling units chosen for ResourceDemand heuristic pre-RA");

117 NumTopDepthReducePreRA,

118 "Number of scheduling units chosen for TopDepthReduce heuristic pre-RA");

120 NumTopPathReducePreRA,

121 "Number of scheduling units chosen for TopPathReduce heuristic pre-RA");

123 NumBotHeightReducePreRA,

124 "Number of scheduling units chosen for BotHeightReduce heuristic pre-RA");

126 NumBotPathReducePreRA,

127 "Number of scheduling units chosen for BotPathReduce heuristic pre-RA");

129 "Number of scheduling units chosen for NodeOrder heuristic pre-RA");

131 "Number of scheduling units chosen for FirstValid heuristic pre-RA");

132

134 "Number of scheduling units chosen from top queue post-RA");

136 "Number of scheduling units chosen from bottom queue post-RA");

138 "Number of scheduling units chosen for NoCand heuristic post-RA");

140 "Number of scheduling units chosen for Only1 heuristic post-RA");

142 "Number of scheduling units chosen for PhysReg heuristic post-RA");

144 "Number of scheduling units chosen for RegExcess heuristic post-RA");

146 NumRegCriticalPostRA,

147 "Number of scheduling units chosen for RegCritical heuristic post-RA");

149 "Number of scheduling units chosen for Stall heuristic post-RA");

151 "Number of scheduling units chosen for Cluster heuristic post-RA");

153 "Number of scheduling units chosen for Weak heuristic post-RA");

155 "Number of scheduling units chosen for RegMax heuristic post-RA");

157 NumResourceReducePostRA,

158 "Number of scheduling units chosen for ResourceReduce heuristic post-RA");

160 NumResourceDemandPostRA,

161 "Number of scheduling units chosen for ResourceDemand heuristic post-RA");

163 NumTopDepthReducePostRA,

164 "Number of scheduling units chosen for TopDepthReduce heuristic post-RA");

166 NumTopPathReducePostRA,

167 "Number of scheduling units chosen for TopPathReduce heuristic post-RA");

169 NumBotHeightReducePostRA,

170 "Number of scheduling units chosen for BotHeightReduce heuristic post-RA");

172 NumBotPathReducePostRA,

173 "Number of scheduling units chosen for BotPathReduce heuristic post-RA");

175 "Number of scheduling units chosen for NodeOrder heuristic post-RA");

177 "Number of scheduling units chosen for FirstValid heuristic post-RA");

178

180 "misched-prera-direction", cl::Hidden,

181 cl::desc("Pre reg-alloc list scheduling direction"),

185 "Force top-down pre reg-alloc list scheduling"),

187 "Force bottom-up pre reg-alloc list scheduling"),

189 "Force bidirectional pre reg-alloc list scheduling")));

190

192 "misched-postra-direction", cl::Hidden,

193 cl::desc("Post reg-alloc list scheduling direction"),

197 "Force top-down post reg-alloc list scheduling"),

199 "Force bottom-up post reg-alloc list scheduling"),

201 "Force bidirectional post reg-alloc list scheduling")));

202

205 cl::desc("Print critical path length to stdout"));

206

209 cl::desc("Verify machine instrs before and after machine scheduling"));

210

211#ifndef NDEBUG

214 cl::desc("Pop up a window to show MISched dags after they are processed"));

216 cl::desc("Print schedule DAGs"));

219 cl::desc("Dump resource usage at schedule boundary."));

222 cl::desc("Show details of invoking getNextResoufceCycle."));

223#else

227#ifdef LLVM_ENABLE_DUMP

229#endif

230#endif

231

232#ifndef NDEBUG

233

234

236 cl::desc("Hide nodes with more predecessor/successor than cutoff"));

237

239 cl::desc("Stop scheduling after N instructions"), cl::init(~0U));

240

242 cl::desc("Only schedule this function"));

244 cl::desc("Only schedule this MBB#"));

245#endif

246

247

248

250 cl::desc("Limit ready list to N instructions"), cl::init(256));

251

253 cl::desc("Enable register pressure scheduling."), cl::init(true));

254

256 cl::desc("Enable cyclic critical path analysis."), cl::init(true));

257

259 cl::desc("Enable memop clustering."),

263 cl::desc("Switch to fast cluster algorithm with the lost "

264 "of some fusion opportunities"),

268 cl::desc("The threshold for fast cluster"),

270

271#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

274 cl::desc("Dump resource usage at schedule boundary."));

277 cl::desc("Set width of the columns with "

278 "the resources and schedule units"),

282 cl::desc("Set width of the columns showing resource booking."),

286 cl::desc("Sort the resources printed in the dump trace"));

287#endif

288

292

293

295

296

297void MachineSchedStrategy::anchor() {}

298

299void ScheduleDAGMutation::anchor() {}

300

301

302

303

304

308

312

313namespace llvm {

315

316

321

322

324

325

328

329public:

336

338

341

343 const RequiredAnalyses &Analyses);

344

345protected:

347};

348

349

351

352

355

356public:

362

365

367 const RequiredAnalyses &Analyses);

368

369protected:

371};

372

373}

374}

375

379

380namespace {

381

383 MachineSchedulerImpl Impl;

384

385public:

386 MachineSchedulerLegacy();

387 void getAnalysisUsage(AnalysisUsage &AU) const override;

388 bool runOnMachineFunction(MachineFunction&) override;

389

390 static char ID;

391};

392

393

395 PostMachineSchedulerImpl Impl;

396

397public:

398 PostMachineSchedulerLegacy();

399 void getAnalysisUsage(AnalysisUsage &AU) const override;

400 bool runOnMachineFunction(MachineFunction &) override;

401

402 static char ID;

403};

404

405}

406

407char MachineSchedulerLegacy::ID = 0;

408

410

412 "Machine Instruction Scheduler", false, false)

420

423}

424

425void MachineSchedulerLegacy::getAnalysisUsage(AnalysisUsage &AU) const {

436}

437

438char PostMachineSchedulerLegacy::ID = 0;

439

441

443 "PostRA Machine Instruction Scheduler", false, false)

448 "PostRA Machine Instruction Scheduler", false, false)

449

450PostMachineSchedulerLegacy::PostMachineSchedulerLegacy()

453}

454

455void PostMachineSchedulerLegacy::getAnalysisUsage(AnalysisUsage &AU) const {

462}

463

466

467

468

472

473

478 cl::desc("Machine instruction scheduler to use"));

479

483

485 "enable-misched",

486 cl::desc("Enable the machine instruction scheduling pass."), cl::init(true),

488

490 "enable-post-misched",

491 cl::desc("Enable the post-ra machine instruction scheduling pass."),

493

494

498 assert(I != Beg && "reached the top of the region, cannot decrement");

499 while (--I != Beg) {

500 if (->isDebugOrPseudoInstr())

501 break;

502 }

503 return I;

504}

505

506

513

514

515

519 for(; I != End; ++I) {

520 if (->isDebugOrPseudoInstr())

521 break;

522 }

523 return I;

524}

525

526

533

534

536

539 return Ctor(this);

540

541

545

546

548}

549

552 MF = &Func;

555 this->TM = &TM;

556 AA = &Analyses.AA;

558

561 const char *MSchedBanner = "Before machine scheduling.";

562 if (P)

563 MF->verify(P, MSchedBanner, &errs());

564 else

565 MF->verify(*MFAM, MSchedBanner, &errs());

566 }

568

569

570

573

576 const char *MSchedBanner = "After machine scheduling.";

577 if (P)

578 MF->verify(P, MSchedBanner, &errs());

579 else

580 MF->verify(*MFAM, MSchedBanner, &errs());

581 }

582 return true;

583}

584

585

586

587

597

601 MF = &Func;

603 this->TM = &TM;

604 AA = &Analyses.AA;

605

607 const char *PostMSchedBanner = "Before post machine scheduling.";

608 if (P)

609 MF->verify(P, PostMSchedBanner, &errs());

610 else

611 MF->verify(*MFAM, PostMSchedBanner, &errs());

612 }

613

614

615

618

620 const char *PostMSchedBanner = "After post machine scheduling.";

621 if (P)

622 MF->verify(P, PostMSchedBanner, &errs());

623 else

624 MF->verify(*MFAM, PostMSchedBanner, &errs());

625 }

626 return true;

627}

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645bool MachineSchedulerLegacy::runOnMachineFunction(MachineFunction &MF) {

647 return false;

648

651 return false;

653 return false;

654 }

655

657

658 auto &MLI = getAnalysis().getLI();

659 auto &MDT = getAnalysis().getDomTree();

660 auto &TM = getAnalysis().getTM<TargetMachine>();

661 auto &AA = getAnalysis().getAAResults();

662 auto &LIS = getAnalysis().getLIS();

663 Impl.setLegacyPass(this);

664 return Impl.run(MF, TM, {MLI, MDT, AA, LIS});

665}

666

668 : Impl(std::make_unique()), TM(TM) {}

671 default;

672

674 : Impl(std::make_unique()), TM(TM) {}

678

687 }

688

693 .getManager();

696 Impl->setMFAM(&MFAM);

697 bool Changed = Impl->run(MF, *TM, {MLI, MDT, AA, LIS});

700

703 .preserve()

705}

706

707bool PostMachineSchedulerLegacy::runOnMachineFunction(MachineFunction &MF) {

709 return false;

710

713 return false;

715 LLVM_DEBUG(dbgs() << "Subtarget disables post-MI-sched.\n");

716 return false;

717 }

719 auto &MLI = getAnalysis().getLI();

720 auto &TM = getAnalysis().getTM<TargetMachine>();

721 auto &AA = getAnalysis().getAAResults();

722 Impl.setLegacyPass(this);

723 return Impl.run(MF, TM, {MLI, AA});

724}

725

733 LLVM_DEBUG(dbgs() << "Subtarget disables post-MI-sched.\n");

735 }

739 .getManager();

741

742 Impl->setMFAM(&MFAM);

743 bool Changed = Impl->run(MF, *TM, {MLI, AA});

746

749 return PA;

750}

751

752

753

754

755

756

757

758

759

760

761

766 return MI->isCall() || TII->isSchedulingBoundary(*MI, MBB, *MF) ||

767 MI->isFakeUse();

768}

769

771

772static void

775 bool RegionsTopDown) {

778

781 RegionEnd != MBB->begin(); RegionEnd = I) {

782

783

784 if (RegionEnd != MBB->end() ||

786 --RegionEnd;

787 }

788

789

790

791 unsigned NumRegionInstrs = 0;

792 I = RegionEnd;

793 for (;I != MBB->begin(); --I) {

796 break;

797 if (.isDebugOrPseudoInstr()) {

798

799

800 ++NumRegionInstrs;

801 }

802 }

803

804

805

806 if (NumRegionInstrs != 0)

808 }

809

810 if (RegionsTopDown)

811 std::reverse(Regions.begin(), Regions.end());

812}

813

814

816 bool FixKillFlags) {

817

818

819

820

822 MBB != MBBEnd; ++MBB) {

823

825

826#ifndef NDEBUG

828 continue;

831 continue;

832#endif

833

834

835

836

837

838

839

840

841

842

843

844

845

846

847

850 bool ScheduleSingleMI = Scheduler.shouldScheduleSingleMIRegions();

851 for (const SchedRegion &R : MBBRegions) {

854 unsigned NumRegionInstrs = R.NumRegionInstrs;

855

856

857

858 Scheduler.enterRegion(&*MBB, I, RegionEnd, NumRegionInstrs);

859

860

861

862 if (I == RegionEnd || (!ScheduleSingleMI && I == std::prev(RegionEnd))) {

863

864

866 continue;

867 }

868 LLVM_DEBUG(dbgs() << "********** MI Scheduling **********\n");

870 << " " << MBB->getName() << "\n From: " << *I

871 << " To: ";

872 if (RegionEnd != MBB->end()) dbgs() << *RegionEnd;

873 else dbgs() << "End\n";

874 dbgs() << " RegionInstrs: " << NumRegionInstrs << '\n');

876 errs() << MF->getName();

877 errs() << ":%bb. " << MBB->getNumber();

878 errs() << " " << MBB->getName() << " \n";

879 }

880

881

882

884

885

887 }

889

890

891

892 if (FixKillFlags)

894 }

896}

897

898#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

900 dbgs() << "Queue " << Name << ": ";

901 for (const SUnit *SU : Queue)

902 dbgs() << SU->NodeNum << " ";

903 dbgs() << "\n";

904}

905#endif

906

907

908

909

910

911

912

913

915

916

917

918

919

922

923 if (SuccEdge->isWeak()) {

925 return;

926 }

927#ifndef NDEBUG

929 dbgs() << "*** Scheduling failed! ***\n";

931 dbgs() << " has been released too many times!\n";

933 }

934#endif

935

936

939

942 SchedImpl->releaseTopNode(SuccSU);

943}

944

945

950

951

952

953

954

957

958 if (PredEdge->isWeak()) {

960 return;

961 }

962#ifndef NDEBUG

964 dbgs() << "*** Scheduling failed! ***\n";

966 dbgs() << " has been released too many times!\n";

968 }

969#endif

970

971

974

977 SchedImpl->releaseBottomNode(PredSU);

978}

979

980

985

990

995

996

997

998

999

1003 unsigned regioninstrs)

1004{

1006

1008

1009

1011 if (SchedImpl->getPolicy().OnlyTopDown)

1013 else if (SchedImpl->getPolicy().OnlyBottomUp)

1015 else

1018}

1019

1020

1021

1024

1027

1028

1029 BB->splice(InsertPos, BB, MI);

1030

1031

1032 if (LIS)

1033 LIS->handleMove(*MI, true);

1034

1035

1038}

1039

1041#if LLVM_ENABLE_ABI_BREAKING_CHECKS && !defined(NDEBUG)

1044 return false;

1045 }

1046 ++NumInstrsScheduled;

1047#endif

1048 return true;

1049}

1050

1051

1052

1053

1054

1056 LLVM_DEBUG(dbgs() << "ScheduleDAGMI::schedule starting\n");

1058

1059

1061

1063

1066

1070

1071

1072

1074

1075

1077

1078 bool IsTopNode = false;

1079 while (true) {

1081 break;

1082

1083 LLVM_DEBUG(dbgs() << "** ScheduleDAGMI::schedule picking next node\n");

1085 if (!SU) break;

1086

1088

1090 if (IsTopNode) {

1091 assert(SU->isTopReady() && "node still has unscheduled dependencies");

1094 else

1096 } else {

1097 assert(SU->isBottomReady() && "node still has unscheduled dependencies");

1100 if (&*priorII == MI)

1102 else {

1107 }

1108 }

1109

1110

1111

1112

1113 SchedImpl->schedNode(SU, IsTopNode);

1114

1116 }

1118

1120

1122 dbgs() << "*** Final schedule for "

1125 dbgs() << '\n';

1126 });

1127}

1128

1129

1132 m->apply(this);

1133}

1134

1139 assert(!SU.isBoundaryNode() && "Boundary node should not be in SUnits");

1140

1141

1142 SU.biasCriticalPath();

1143

1144

1145 if (!SU.NumPredsLeft)

1147

1148 if (!SU.NumSuccsLeft)

1150 }

1151 ExitSU.biasCriticalPath();

1152}

1153

1154

1157

1158

1159

1160

1161 for (SUnit *SU : TopRoots)

1163

1164

1165

1167 I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I) {

1169 }

1170

1173

1175

1176

1179}

1180

1181

1183

1184 if (IsTopNode)

1186 else

1188

1190}

1191

1192

1194

1198 }

1199

1200 for (std::vector<std::pair<MachineInstr *, MachineInstr *>>::iterator

1202 std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI);

1207 BB->splice(std::next(OrigPrevMI), BB, DbgValue);

1210 }

1211}

1212

1213#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

1215

1217

1218 if (.hasInstrSchedModel())

1219 return;

1220

1221

1222 if (BB->size() < 2)

1223 return;

1224

1225 dbgs() << " * Schedule table (TopDown):\n";

1231 if (!SU)

1232 continue;

1235 PE = SchedModel.getWriteProcResEnd(SC);

1236 PI != PE; ++PI) {

1237 if (SU->TopReadyCycle + PI->ReleaseAtCycle - 1 > LastCycle)

1238 LastCycle = SU->TopReadyCycle + PI->ReleaseAtCycle - 1;

1239 }

1240 }

1241

1243 for (unsigned C = FirstCycle; C <= LastCycle; ++C)

1245 dbgs() << "|\n";

1246

1249 if (!SU) {

1250 dbgs() << "Missing SUnit\n";

1251 continue;

1252 }

1253 std::string NodeName("SU(");

1254 NodeName += std::to_string(SU->NodeNum) + ")";

1256 unsigned C = FirstCycle;

1257 for (; C <= LastCycle; ++C) {

1260 else

1262 }

1263 dbgs() << "|\n";

1265

1268 SchedModel.getWriteProcResEnd(SC)));

1269

1272 ResourcesIt,

1275 return std::tie(LHS.AcquireAtCycle, LHS.ReleaseAtCycle) <

1276 std::tie(RHS.AcquireAtCycle, RHS.ReleaseAtCycle);

1277 });

1279 C = FirstCycle;

1280 const std::string ResName =

1281 SchedModel.getResourceName(PI.ProcResourceIdx);

1283 for (; C < SU->TopReadyCycle + PI.AcquireAtCycle; ++C) {

1285 }

1286 for (unsigned I = 0, E = PI.ReleaseAtCycle - PI.AcquireAtCycle; I != E;

1287 ++I, ++C)

1289 while (C++ <= LastCycle)

1291

1292 dbgs() << "| \n";

1293 }

1294 }

1295}

1296

1298

1299 if (.hasInstrSchedModel())

1300 return;

1301

1302

1303 if (BB->size() < 2)

1304 return;

1305

1306 dbgs() << " * Schedule table (BottomUp):\n";

1308

1313 if (!SU)

1314 continue;

1317 PE = SchedModel.getWriteProcResEnd(SC);

1318 PI != PE; ++PI) {

1319 if ((int)SU->BotReadyCycle - PI->ReleaseAtCycle + 1 < LastCycle)

1320 LastCycle = (int)SU->BotReadyCycle - PI->ReleaseAtCycle + 1;

1321 }

1322 }

1323

1325 for (int C = FirstCycle; C >= LastCycle; --C)

1327 dbgs() << "|\n";

1328

1331 if (!SU) {

1332 dbgs() << "Missing SUnit\n";

1333 continue;

1334 }

1335 std::string NodeName("SU(");

1336 NodeName += std::to_string(SU->NodeNum) + ")";

1338 int C = FirstCycle;

1339 for (; C >= LastCycle; --C) {

1342 else

1344 }

1345 dbgs() << "|\n";

1349 SchedModel.getWriteProcResEnd(SC)));

1350

1353 ResourcesIt,

1356 return std::tie(LHS.AcquireAtCycle, LHS.ReleaseAtCycle) <

1357 std::tie(RHS.AcquireAtCycle, RHS.ReleaseAtCycle);

1358 });

1360 C = FirstCycle;

1361 const std::string ResName =

1362 SchedModel.getResourceName(PI.ProcResourceIdx);

1364 for (; C > ((int)SU->BotReadyCycle - (int)PI.AcquireAtCycle); --C) {

1366 }

1367 for (unsigned I = 0, E = PI.ReleaseAtCycle - PI.AcquireAtCycle; I != E;

1368 ++I, --C)

1370 while (C-- >= LastCycle)

1372

1373 dbgs() << "| \n";

1374 }

1375 }

1376}

1377#endif

1378

1379#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

1387 dbgs() << "* Schedule table (Bidirectional): not implemented\n";

1388 } else {

1389 dbgs() << "* Schedule table: DumpDirection not set.\n";

1390 }

1391 }

1392

1396 else

1397 dbgs() << "Missing SUnit\n";

1398 }

1399}

1400#endif

1401

1402

1403

1404

1405

1406

1410

1414 if (!MO.isReg())

1415 continue;

1416 if (!MO.readsReg())

1417 continue;

1419 continue;

1420

1422 if (!Reg.isVirtual())

1423 continue;

1424

1425

1427 bool FoundDef = false;

1429 if (MO2.getReg() == Reg && !MO2.isDead()) {

1430 FoundDef = true;

1431 break;

1432 }

1433 }

1434 if (FoundDef)

1435 continue;

1436 }

1437

1438

1440 for (; UI != VRegUses.end(); ++UI) {

1441 if (UI->SU == &SU)

1442 break;

1443 }

1446 }

1447}

1448

1449

1450

1451

1452

1456 unsigned regioninstrs)

1457{

1458

1460

1461

1463

1465

1468

1470 "ShouldTrackLaneMasks requires ShouldTrackPressure");

1471}

1472

1473

1474

1477 VRegUses.setUniverse(MRI.getNumVirtRegs());

1480

1485

1486

1488

1490

1491

1494

1495

1496

1497

1500

1506 };

1507

1508

1509

1511

1512

1517 }

1518

1521 dbgs() << "Bottom Pressure: ";

1523

1527 "Can't find the region bottom");

1528

1529

1530

1533 RPTracker.getPressure().MaxSetPressure;

1534 for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) {

1535 unsigned Limit = RegClassInfo->getRegPressureSetLimit(i);

1537 LLVM_DEBUG(dbgs() << TRI->getRegPressureSetName(i) << " Limit " << Limit

1540 }

1541 }

1544 dbgs() << "Excess PSets: ";

1546 dbgs() << TRI->getRegPressureSetName(RCPS.getPSet()) << " ";

1547 dbgs() << "\n";

1548 }

1549 });

1550}

1551

1554 const std::vector &NewMaxPressure) {

1558 if (!PC.isValid())

1559 break;

1560 unsigned ID = PC.getPSet();

1562 ++CritIdx;

1565 && NewMaxPressure[ID] <= (unsigned)std::numeric_limits<int16_t>::max())

1567 }

1568 unsigned Limit = RegClassInfo->getRegPressureSetLimit(ID);

1569 if (NewMaxPressure[ID] >= Limit - 2) {

1571 << NewMaxPressure[ID]

1572 << ((NewMaxPressure[ID] > Limit) ? " > " : " <= ")

1574 << " livethru)\n");

1575 }

1576 }

1577}

1578

1579

1580

1583

1584 if (.VRegOrUnit.isVirtualReg())

1585 continue;

1586 Register Reg = P.VRegOrUnit.asVirtualReg();

1587

1589

1590

1591

1592

1593 bool Decrement = P.LaneMask.any();

1594

1597 SUnit &SU = *V2SU.SU;

1599 continue;

1600

1604 return Change.isValid();

1605 }))

1607 << " UpdateRegPressure: SU(" << SU.NodeNum << ") "

1611 }

1612 } else {

1613 assert(P.LaneMask.any());

1615

1616

1617

1618

1623 if (I == BB->end())

1625 else {

1628 }

1629

1630 assert(VNI && "No live value at use.");

1633 SUnit *SU = V2SU.SU;

1634

1635

1639 if (LRQ.valueIn() == VNI) {

1643 return Change.isValid();

1644 }))

1647 dbgs() << " to ";

1649 }

1650 }

1651 }

1652 }

1653 }

1654}

1655

1657#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

1658 if (EntrySU.getInstr() != nullptr)

1663 dbgs() << " Pressure Diff : ";

1665 }

1666 dbgs() << " Single Issue : ";

1667 if (SchedModel.mustBeginGroup(SU.getInstr()) &&

1668 SchedModel.mustEndGroup(SU.getInstr()))

1669 dbgs() << "true;";

1670 else

1671 dbgs() << "false;";

1672 dbgs() << '\n';

1673 }

1674 if (ExitSU.getInstr() != nullptr)

1676#endif

1677}

1678

1679

1680

1681

1682

1683

1684

1685

1686

1687

1688

1690 LLVM_DEBUG(dbgs() << "ScheduleDAGMILive::schedule starting\n");

1693

1695

1698

1699

1700

1702

1706

1707

1709

1710 bool IsTopNode = false;

1711 while (true) {

1713 break;

1714

1715 LLVM_DEBUG(dbgs() << "** ScheduleDAGMILive::schedule picking next node\n");

1717 if (!SU) break;

1718

1720

1722

1724 unsigned SubtreeID = DFSResult->getSubtreeID(SU);

1727 DFSResult->scheduleTree(SubtreeID);

1728 SchedImpl->scheduleTree(SubtreeID);

1729 }

1730 }

1731

1732

1733 SchedImpl->schedNode(SU, IsTopNode);

1734

1736 }

1738

1740

1742 dbgs() << "*** Final schedule for "

1745 dbgs() << '\n';

1746 });

1747}

1748

1749

1755 return;

1756 }

1757

1758

1761

1762

1765

1766

1768

1769

1771}

1772

1782

1783

1784

1785

1786

1787

1788

1789

1790

1791

1792

1793

1794

1795

1796

1797

1798

1799

1800

1801

1802

1803

1804

1805

1806

1807

1808

1810

1811 if (->isSuccessor(BB))

1812 return 0;

1813

1814 unsigned MaxCyclicLatency = 0;

1815

1817 if (.VRegOrUnit.isVirtualReg())

1818 continue;

1819 Register Reg = P.VRegOrUnit.asVirtualReg();

1822 if (!DefVNI)

1823 continue;

1824

1827 if (!DefSU)

1828 continue;

1829

1830 unsigned LiveOutHeight = DefSU->getHeight();

1831 unsigned LiveOutDepth = DefSU->getDepth() + DefSU->Latency;

1832

1835 SUnit *SU = V2SU.SU;

1837 continue;

1838

1839

1842 continue;

1843

1844

1845

1846

1847 unsigned CyclicLatency = 0;

1848 if (LiveOutDepth > SU->getDepth())

1849 CyclicLatency = LiveOutDepth - SU->getDepth();

1850

1852 if (LiveInHeight > LiveOutHeight) {

1853 if (LiveInHeight - LiveOutHeight < CyclicLatency)

1854 CyclicLatency = LiveInHeight - LiveOutHeight;

1855 } else

1856 CyclicLatency = 0;

1857

1859 << SU->NodeNum << ") = " << CyclicLatency << "c\n");

1860 if (CyclicLatency > MaxCyclicLatency)

1861 MaxCyclicLatency = CyclicLatency;

1862 }

1863 }

1864 LLVM_DEBUG(dbgs() << "Cyclic Critical Path: " << MaxCyclicLatency << "c\n");

1865 return MaxCyclicLatency;

1866}

1867

1868

1869

1878

1879

1881

1883

1884 if (IsTopNode) {

1885 assert(SU->isTopReady() && "node still has unscheduled dependencies");

1888 else {

1891 }

1892

1894

1897 false);

1899

1900 SlotIndex SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();

1902 } else {

1903

1905 }

1906

1911

1913 }

1914 } else {

1915 assert(SU->isBottomReady() && "node still has unscheduled dependencies");

1918 if (&*priorII == MI)

1920 else {

1924 }

1928 }

1932 false);

1934

1935 SlotIndex SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();

1937 } else {

1938

1940 }

1941

1949

1952 }

1953 }

1954}

1955

1956

1957

1958

1959

1960namespace {

1961

1962

1963

1965 struct MemOpInfo {

1970 bool OffsetIsScalable;

1971

1974 : SU(SU), BaseOps(BaseOps), Offset(Offset), Width(Width),

1975 OffsetIsScalable(OffsetIsScalable) {}

1976

1979 if (A->getType() != B->getType())

1980 return A->getType() < B->getType();

1981 if (A->isReg())

1982 return A->getReg() < B->getReg();

1983 if (A->isFI()) {

1984 const MachineFunction &MF = *A->getParent()->getParent()->getParent();

1988 return StackGrowsDown ? A->getIndex() > B->getIndex()

1989 : A->getIndex() < B->getIndex();

1990 }

1991

1992 llvm_unreachable("MemOpClusterMutation only supports register or frame "

1993 "index bases.");

1994 }

1995

1996 bool operator<(const MemOpInfo &RHS) const {

1997

1998

1999 if (std::lexicographical_compare(BaseOps.begin(), BaseOps.end(),

2000 RHS.BaseOps.begin(), RHS.BaseOps.end(),

2001 Compare))

2002 return true;

2003 if (std::lexicographical_compare(RHS.BaseOps.begin(), RHS.BaseOps.end(),

2004 BaseOps.begin(), BaseOps.end(), Compare))

2005 return false;

2008 return SU->NodeNum < RHS.SU->NodeNum;

2009 }

2010 };

2011

2012 const TargetInstrInfo *TII;

2013 const TargetRegisterInfo *TRI;

2014 bool IsLoad;

2015 bool ReorderWhileClustering;

2016

2017public:

2018 BaseMemOpClusterMutation(const TargetInstrInfo *tii,

2019 const TargetRegisterInfo *tri, bool IsLoad,

2020 bool ReorderWhileClustering)

2021 : TII(tii), TRI(tri), IsLoad(IsLoad),

2022 ReorderWhileClustering(ReorderWhileClustering) {}

2023

2024 void apply(ScheduleDAGInstrs *DAGInstrs) override;

2025

2026protected:

2027 void clusterNeighboringMemOps(ArrayRef MemOps, bool FastCluster,

2028 ScheduleDAGInstrs *DAG);

2029 void collectMemOpRecords(std::vector &SUnits,

2030 SmallVectorImpl &MemOpRecords);

2033};

2034

2035class StoreClusterMutation : public BaseMemOpClusterMutation {

2036public:

2037 StoreClusterMutation(const TargetInstrInfo *tii,

2038 const TargetRegisterInfo *tri,

2039 bool ReorderWhileClustering)

2040 : BaseMemOpClusterMutation(tii, tri, false, ReorderWhileClustering) {}

2041};

2042

2043class LoadClusterMutation : public BaseMemOpClusterMutation {

2044public:

2045 LoadClusterMutation(const TargetInstrInfo *tii, const TargetRegisterInfo *tri,

2046 bool ReorderWhileClustering)

2047 : BaseMemOpClusterMutation(tii, tri, true, ReorderWhileClustering) {}

2048};

2049

2050}

2051

2052std::unique_ptr

2055 bool ReorderWhileClustering) {

2057 TII, TRI, ReorderWhileClustering)

2058 : nullptr;

2059}

2060

2061std::unique_ptr

2064 bool ReorderWhileClustering) {

2066 TII, TRI, ReorderWhileClustering)

2067 : nullptr;

2068}

2069

2070

2071

2072

2073

2074

2075void BaseMemOpClusterMutation::clusterNeighboringMemOps(

2078

2081

2082

2083

2084 for (unsigned Idx = 0, End = MemOpRecords.size(); Idx < (End - 1); ++Idx) {

2085

2086 auto MemOpa = MemOpRecords[Idx];

2087

2088

2089 unsigned NextIdx = Idx + 1;

2090 for (; NextIdx < End; ++NextIdx)

2091

2092

2093 if (!SUnit2ClusterInfo.count(MemOpRecords[NextIdx].SU->NodeNum) &&

2094 (FastCluster ||

2095 (!DAG->IsReachable(MemOpRecords[NextIdx].SU, MemOpa.SU) &&

2096 !DAG->IsReachable(MemOpa.SU, MemOpRecords[NextIdx].SU))))

2097 break;

2098 if (NextIdx == End)

2099 continue;

2100

2101 auto MemOpb = MemOpRecords[NextIdx];

2102 unsigned ClusterLength = 2;

2103 unsigned CurrentClusterBytes = MemOpa.Width.getValue().getKnownMinValue() +

2104 MemOpb.Width.getValue().getKnownMinValue();

2105 auto It = SUnit2ClusterInfo.find(MemOpa.SU->NodeNum);

2106 if (It != SUnit2ClusterInfo.end()) {

2107 const auto &[Len, Bytes] = It->second;

2108 ClusterLength = Len + 1;

2109 CurrentClusterBytes = Bytes + MemOpb.Width.getValue().getKnownMinValue();

2110 }

2111

2113 MemOpa.OffsetIsScalable, MemOpb.BaseOps,

2114 MemOpb.Offset, MemOpb.OffsetIsScalable,

2115 ClusterLength, CurrentClusterBytes))

2116 continue;

2117

2118 SUnit *SUa = MemOpa.SU;

2119 SUnit *SUb = MemOpb.SU;

2120

2121 if (!ReorderWhileClustering && SUa->NodeNum > SUb->NodeNum)

2123

2124

2126 continue;

2127

2130 << SUb->NodeNum << ")\n");

2131 ++NumClustered;

2132

2133 if (IsLoad) {

2134

2135

2136

2137

2138 for (const SDep &Succ : SUa->Succs) {

2140 continue;

2142 << ")\n");

2144 }

2145 } else {

2146

2147

2148

2149

2150

2151

2152 for (const SDep &Pred : SUb->Preds) {

2154 continue;

2156 << ")\n");

2158 }

2159 }

2160

2161 SUnit2ClusterInfo[MemOpb.SU->NodeNum] = {ClusterLength,

2162 CurrentClusterBytes};

2163

2164 LLVM_DEBUG(dbgs() << " Curr cluster length: " << ClusterLength

2165 << ", Curr cluster bytes: " << CurrentClusterBytes

2166 << "\n");

2167 }

2168

2169

2170

2173 if (->isLeader())

2174 continue;

2176 unsigned ClusterIdx = AllClusters.size();

2178 MemberI->ParentClusterIdx = ClusterIdx;

2179 Group.insert(MemberI);

2180 }

2181 AllClusters.push_back(Group);

2182 }

2183}

2184

2185void BaseMemOpClusterMutation::collectMemOpRecords(

2187 for (auto &SU : SUnits) {

2190 continue;

2191

2195 bool OffsetIsScalable;

2198 OffsetIsScalable, Width, TRI)) {

2200 continue;

2201

2203 MemOpInfo(&SU, BaseOps, Offset, OffsetIsScalable, Width));

2204

2205 LLVM_DEBUG(dbgs() << "Num BaseOps: " << BaseOps.size() << ", Offset: "

2206 << Offset << ", OffsetIsScalable: " << OffsetIsScalable

2207 << ", Width: " << Width << "\n");

2208 }

2209#ifndef NDEBUG

2210 for (const auto *Op : BaseOps)

2212#endif

2213 }

2214}

2215

2216bool BaseMemOpClusterMutation::groupMemOps(

2219 bool FastCluster =

2222

2223 for (const auto &MemOp : MemOps) {

2224 unsigned ChainPredID = DAG->SUnits.size();

2225 if (FastCluster) {

2226 for (const SDep &Pred : MemOp.SU->Preds) {

2227

2228

2229

2230 if ((Pred.isCtrl() &&

2231 (IsLoad ||

2235 break;

2236 }

2237 }

2238 } else

2239 ChainPredID = 0;

2240

2242 }

2243 return FastCluster;

2244}

2245

2246

2248

2250 collectMemOpRecords(DAG->SUnits, MemOpRecords);

2251

2252 if (MemOpRecords.size() < 2)

2253 return;

2254

2255

2256

2257

2259 bool FastCluster = groupMemOps(MemOpRecords, DAG, Groups);

2260

2261 for (auto &Group : Groups) {

2262

2263

2265

2266

2267 clusterNeighboringMemOps(Group.second, FastCluster, DAG);

2268 }

2269}

2270

2271

2272

2273

2274

2275namespace {

2276

2277

2278

2279

2281

2282 SlotIndex RegionBeginIdx;

2283

2284

2285

2286 SlotIndex RegionEndIdx;

2287

2288public:

2289 CopyConstrain(const TargetInstrInfo *, const TargetRegisterInfo *) {}

2290

2291 void apply(ScheduleDAGInstrs *DAGInstrs) override;

2292

2293protected:

2294 void constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG);

2295};

2296

2297}

2298

2299std::unique_ptr

2302 return std::make_unique(TII, TRI);

2303}

2304

2305

2306

2307

2308

2309

2310

2311

2312

2313

2314

2315

2316

2317

2318

2319

2320

2321

2322

2323

2327

2328

2332 return;

2333

2337 return;

2338

2339

2340

2341

2342

2343

2344

2345 unsigned LocalReg = SrcReg;

2346 unsigned GlobalReg = DstReg;

2348 if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx)) {

2349 LocalReg = DstReg;

2350 GlobalReg = SrcReg;

2352 if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx))

2353 return;

2354 }

2356

2357

2359

2360

2361

2362

2363 if (GlobalSegment == GlobalLI->end())

2364 return;

2365

2366

2367

2368

2369

2370 if (GlobalSegment->contains(LocalLI->beginIndex()))

2371 ++GlobalSegment;

2372

2373 if (GlobalSegment == GlobalLI->end())

2374 return;

2375

2376

2377 if (GlobalSegment != GlobalLI->begin()) {

2378

2380 GlobalSegment->start)) {

2381 return;

2382 }

2383

2384

2387 return;

2388 }

2389

2390

2391 assert(std::prev(GlobalSegment)->start < LocalLI->beginIndex() &&

2392 "Disconnected LRG within the scheduling region.");

2393 }

2395 if (!GlobalDef)

2396 return;

2397

2399 if (!GlobalSU)

2400 return;

2401

2402

2403

2407 SUnit *LastLocalSU = DAG->getSUnit(LastLocalDef);

2408 for (const SDep &Succ : LastLocalSU->Succs) {

2410 continue;

2411 if (Succ.getSUnit() == GlobalSU)

2412 continue;

2414 return;

2416 }

2417

2418

2422 SUnit *FirstLocalSU = DAG->getSUnit(FirstLocalDef);

2423 for (const SDep &Pred : GlobalSU->Preds) {

2425 continue;

2426 if (Pred.getSUnit() == FirstLocalSU)

2427 continue;

2429 return;

2431 }

2433

2434 for (SUnit *LU : LocalUses) {

2435 LLVM_DEBUG(dbgs() << " Local use SU(" << LU->NodeNum << ") -> SU("

2436 << GlobalSU->NodeNum << ")\n");

2438 }

2439 for (SUnit *GU : GlobalUses) {

2440 LLVM_DEBUG(dbgs() << " Global use SU(" << GU->NodeNum << ") -> SU("

2441 << FirstLocalSU->NodeNum << ")\n");

2443 }

2444}

2445

2446

2447

2451

2453 if (FirstPos == DAG->end())

2454 return;

2458

2461 continue;

2462

2464 }

2465}

2466

2467

2468

2469

2470

2471

2473

2475

2476

2477

2478

2479

2481 unsigned Latency, bool AfterSchedNode) {

2482 int ResCntFactor = (int)(Count - (Latency * LFactor));

2483 if (AfterSchedNode)

2484 return ResCntFactor >= (int)LFactor;

2485 else

2486 return ResCntFactor > (int)LFactor;

2487}

2488

2490

2491

2492

2496 }

2499 CheckPending = false;

2500 CurrCycle = 0;

2501 CurrMOps = 0;

2502 MinReadyCycle = std::numeric_limits::max();

2503 ExpectedLatency = 0;

2504 DependentLatency = 0;

2505 RetiredMOps = 0;

2506 MaxExecutedResCount = 0;

2507 ZoneCritResIdx = 0;

2508 IsResourceLimited = false;

2509 ReservedCycles.clear();

2510 ReservedResourceSegments.clear();

2511 ReservedCyclesIndex.clear();

2512 ResourceGroupSubUnitMasks.clear();

2513#if LLVM_ENABLE_ABI_BREAKING_CHECKS

2514

2515

2516

2517 MaxObservedStall = 0;

2518#endif

2519

2520 ExecutedResCounts.resize(1);

2521 assert(!ExecutedResCounts[0] && "nonzero count for bad resource");

2522}

2523

2528 return;

2537 unsigned PIdx = PI->ProcResourceIdx;

2539 assert(PI->ReleaseAtCycle >= PI->AcquireAtCycle);

2541 (Factor * (PI->ReleaseAtCycle - PI->AcquireAtCycle));

2542 }

2543 }

2544}

2545

2549 DAG = dag;

2552 if (SchedModel->hasInstrSchedModel()) {

2553 unsigned ResourceCount = SchedModel->getNumProcResourceKinds();

2554 ReservedCyclesIndex.resize(ResourceCount);

2555 ExecutedResCounts.resize(ResourceCount);

2556 ResourceGroupSubUnitMasks.resize(ResourceCount, APInt(ResourceCount, 0));

2557 unsigned NumUnits = 0;

2558

2559 for (unsigned i = 0; i < ResourceCount; ++i) {

2560 ReservedCyclesIndex[i] = NumUnits;

2561 NumUnits += SchedModel->getProcResource(i)->NumUnits;

2563 auto SubUnits = SchedModel->getProcResource(i)->SubUnitsIdxBegin;

2564 for (unsigned U = 0, UE = SchedModel->getProcResource(i)->NumUnits;

2565 U != UE; ++U)

2566 ResourceGroupSubUnitMasks[i].setBit(SubUnits[U]);

2567 }

2568 }

2569

2570 ReservedCycles.resize(NumUnits, InvalidCycle);

2571 }

2572}

2573

2574

2575

2576

2577

2578

2579

2580

2583 return 0;

2584

2586 if (ReadyCycle > CurrCycle)

2587 return ReadyCycle - CurrCycle;

2588 return 0;

2589}

2590

2591

2592

2594 unsigned ReleaseAtCycle,

2595 unsigned AcquireAtCycle) {

2598 return ReservedResourceSegments[InstanceIdx].getFirstAvailableAtFromTop(

2599 CurrCycle, AcquireAtCycle, ReleaseAtCycle);

2600

2601 return ReservedResourceSegments[InstanceIdx].getFirstAvailableAtFromBottom(

2602 CurrCycle, AcquireAtCycle, ReleaseAtCycle);

2603 }

2604

2605 unsigned NextUnreserved = ReservedCycles[InstanceIdx];

2606

2608 return CurrCycle;

2609

2611 NextUnreserved = std::max(CurrCycle, NextUnreserved + ReleaseAtCycle);

2612 return NextUnreserved;

2613}

2614

2615

2616

2617

2618std::pair<unsigned, unsigned>

2620 unsigned ReleaseAtCycle,

2621 unsigned AcquireAtCycle) {

2623 LLVM_DEBUG(dbgs() << " Resource booking (@" << CurrCycle << "c): \n");

2625 LLVM_DEBUG(dbgs() << " getNextResourceCycle (@" << CurrCycle << "c): \n");

2626 }

2628 unsigned InstanceIdx = 0;

2629 unsigned StartIndex = ReservedCyclesIndex[PIdx];

2630 unsigned NumberOfInstances = SchedModel->getProcResource(PIdx)->NumUnits;

2631 assert(NumberOfInstances > 0 &&

2632 "Cannot have zero instances of a ProcResource");

2633

2635

2636

2637

2638

2639

2640

2641

2642

2643

2644

2645

2648 SchedModel->getWriteProcResEnd(SC)))

2649 if (ResourceGroupSubUnitMasks[PIdx][PE.ProcResourceIdx])

2651 StartIndex, ReleaseAtCycle, AcquireAtCycle),

2652 StartIndex);

2653

2654 auto SubUnits = SchedModel->getProcResource(PIdx)->SubUnitsIdxBegin;

2655 for (unsigned I = 0, End = NumberOfInstances; I < End; ++I) {

2656 unsigned NextUnreserved, NextInstanceIdx;

2657 std::tie(NextUnreserved, NextInstanceIdx) =

2659 if (MinNextUnreserved > NextUnreserved) {

2660 InstanceIdx = NextInstanceIdx;

2661 MinNextUnreserved = NextUnreserved;

2662 }

2663 }

2664 return std::make_pair(MinNextUnreserved, InstanceIdx);

2665 }

2666

2667 for (unsigned I = StartIndex, End = StartIndex + NumberOfInstances; I < End;

2668 ++I) {

2669 unsigned NextUnreserved =

2672 LLVM_DEBUG(dbgs() << " Instance " << I - StartIndex << " available @"

2673 << NextUnreserved << "c\n");

2674 if (MinNextUnreserved > NextUnreserved) {

2675 InstanceIdx = I;

2676 MinNextUnreserved = NextUnreserved;

2677 }

2678 }

2681 << "[" << InstanceIdx - StartIndex << "]"

2682 << " available @" << MinNextUnreserved << "c"

2683 << "\n");

2684 return std::make_pair(MinNextUnreserved, InstanceIdx);

2685}

2686

2687

2688

2689

2690

2691

2692

2693

2694

2695

2696

2697

2698

2699

2704 << "hazard: SU(" << SU->NodeNum << ") reported by HazardRec\n");

2705 return true;

2706 }

2707

2709 if ((CurrMOps > 0) && (CurrMOps + uops > SchedModel->getIssueWidth())) {

2711 << uops << ", CurrMOps = " << CurrMOps << ", "

2712 << "CurrMOps + uops > issue width of "

2713 << SchedModel->getIssueWidth() << "\n");

2714 return true;

2715 }

2716

2717 if (CurrMOps > 0 &&

2721 << (isTop() ? "begin" : "end") << " group\n");

2722 return true;

2723 }

2724

2729 SchedModel->getWriteProcResEnd(SC))) {

2730 unsigned ResIdx = PE.ProcResourceIdx;

2731 unsigned ReleaseAtCycle = PE.ReleaseAtCycle;

2732 unsigned AcquireAtCycle = PE.AcquireAtCycle;

2733 unsigned NRCycle, InstanceIdx;

2734 std::tie(NRCycle, InstanceIdx) =

2736 if (NRCycle > CurrCycle) {

2737#if LLVM_ENABLE_ABI_BREAKING_CHECKS

2738 MaxObservedStall = std::max(ReleaseAtCycle, MaxObservedStall);

2739#endif

2741 << "hazard: SU(" << SU->NodeNum << ") "

2742 << SchedModel->getResourceName(ResIdx) << '['

2743 << InstanceIdx - ReservedCyclesIndex[ResIdx] << ']' << "="

2744 << NRCycle << "c, is later than "

2745 << "CurrCycle = " << CurrCycle << "c\n");

2746 return true;

2747 }

2748 }

2749 }

2750 return false;

2751}

2752

2753

2756 SUnit *LateSU = nullptr;

2757 unsigned RemLatency = 0;

2758 for (SUnit *SU : ReadySUs) {

2760 if (L > RemLatency) {

2761 RemLatency = L;

2762 LateSU = SU;

2763 }

2764 }

2765 if (LateSU) {

2767 << LateSU->NodeNum << ") " << RemLatency << "c\n");

2768 }

2769 return RemLatency;

2770}

2771

2772

2773

2774

2777 OtherCritIdx = 0;

2778 if (->hasInstrSchedModel())

2779 return 0;

2780

2781 unsigned OtherCritCount = Rem->RemIssueCount

2782 + (RetiredMOps * SchedModel->getMicroOpFactor());

2784 << OtherCritCount / SchedModel->getMicroOpFactor() << '\n');

2785 for (unsigned PIdx = 1, PEnd = SchedModel->getNumProcResourceKinds();

2786 PIdx != PEnd; ++PIdx) {

2787 unsigned OtherCount = getResourceCount(PIdx) + Rem->RemainingCounts[PIdx];

2788 if (OtherCount > OtherCritCount) {

2789 OtherCritCount = OtherCount;

2790 OtherCritIdx = PIdx;

2791 }

2792 }

2793 if (OtherCritIdx) {

2795 dbgs() << " " << Available.getName() << " + Remain CritRes: "

2796 << OtherCritCount / SchedModel->getResourceFactor(OtherCritIdx)

2797 << " " << SchedModel->getResourceName(OtherCritIdx) << "\n");

2798 }

2799 return OtherCritCount;

2800}

2801

2803 unsigned Idx) {

2804 assert(SU->getInstr() && "Scheduled SUnit must have instr");

2805

2806#if LLVM_ENABLE_ABI_BREAKING_CHECKS

2807

2808

2809

2810 if (ReadyCycle > CurrCycle)

2811 MaxObservedStall = std::max(ReadyCycle - CurrCycle, MaxObservedStall);

2812#endif

2813

2814 if (ReadyCycle < MinReadyCycle)

2815 MinReadyCycle = ReadyCycle;

2816

2817

2818

2819 bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0;

2820 bool HazardDetected = !IsBuffered && ReadyCycle > CurrCycle;

2821 if (HazardDetected)

2823 << ") ReadyCycle = " << ReadyCycle

2824 << " is later than CurrCycle = " << CurrCycle

2825 << " on an unbuffered resource" << "\n");

2826 else

2828

2830 HazardDetected = true;

2833 }

2834

2835 if (!HazardDetected) {

2838 << "Move SU(" << SU->NodeNum << ") into Available Q\n");

2839

2840 if (InPQueue)

2842 return;

2843 }

2844

2845 if (!InPQueue)

2847}

2848

2849

2851 if (SchedModel->getMicroOpBufferSize() == 0) {

2852 assert(MinReadyCycle < std::numeric_limits::max() &&

2853 "MinReadyCycle uninitialized");

2854 if (MinReadyCycle > NextCycle)

2855 NextCycle = MinReadyCycle;

2856 }

2857

2858 unsigned DecMOps = SchedModel->getIssueWidth() * (NextCycle - CurrCycle);

2859 CurrMOps = (CurrMOps <= DecMOps) ? 0 : CurrMOps - DecMOps;

2860

2861

2862 if ((NextCycle - CurrCycle) > DependentLatency)

2863 DependentLatency = 0;

2864 else

2865 DependentLatency -= (NextCycle - CurrCycle);

2866

2868

2869 CurrCycle = NextCycle;

2870 } else {

2871

2872 for (; CurrCycle != NextCycle; ++CurrCycle) {

2875 else

2877 }

2878 }

2879 CheckPending = true;

2880 IsResourceLimited =

2883

2885 << '\n');

2886}

2887

2889 ExecutedResCounts[PIdx] += Count;

2890 if (ExecutedResCounts[PIdx] > MaxExecutedResCount)

2891 MaxExecutedResCount = ExecutedResCounts[PIdx];

2892}

2893

2894

2895

2896

2897

2898

2899

2900

2901

2902

2903

2905 unsigned ReleaseAtCycle,

2906 unsigned NextCycle,

2907 unsigned AcquireAtCycle) {

2908 unsigned Factor = SchedModel->getResourceFactor(PIdx);

2909 unsigned Count = Factor * (ReleaseAtCycle- AcquireAtCycle);

2911 << ReleaseAtCycle << "x" << Factor << "u\n");

2912

2913

2915 assert(Rem->RemainingCounts[PIdx] >= Count && "resource double counted");

2916 Rem->RemainingCounts[PIdx] -= Count;

2917

2918

2919

2921 ZoneCritResIdx = PIdx;

2923 << SchedModel->getResourceName(PIdx) << ": "

2925 << "c\n");

2926 }

2927

2928 unsigned NextAvailable, InstanceIdx;

2929 std::tie(NextAvailable, InstanceIdx) =

2931 if (NextAvailable > CurrCycle) {

2933 << SchedModel->getResourceName(PIdx)

2934 << '[' << InstanceIdx - ReservedCyclesIndex[PIdx] << ']'

2935 << " reserved until @" << NextAvailable << "\n");

2936 }

2937 return NextAvailable;

2938}

2939

2940

2942

2945

2946

2948 }

2950

2951 CheckPending = true;

2952 }

2953

2954

2958 (CurrMOps == 0 || (CurrMOps + IncMOps) <= SchedModel->getIssueWidth()) &&

2959 "Cannot schedule this instruction's MicroOps in the current cycle.");

2960

2962 LLVM_DEBUG(dbgs() << " Ready @" << ReadyCycle << "c\n");

2963

2964 unsigned NextCycle = CurrCycle;

2965 switch (SchedModel->getMicroOpBufferSize()) {

2966 case 0:

2967 assert(ReadyCycle <= CurrCycle && "Broken PendingQueue");

2968 break;

2969 case 1:

2970 if (ReadyCycle > NextCycle) {

2971 NextCycle = ReadyCycle;

2972 LLVM_DEBUG(dbgs() << " *** Stall until: " << ReadyCycle << "\n");

2973 }

2974 break;

2975 default:

2976

2977

2978

2979

2980 if (SU->isUnbuffered && ReadyCycle > NextCycle)

2981 NextCycle = ReadyCycle;

2982 break;

2983 }

2984 RetiredMOps += IncMOps;

2985

2986

2987 if (SchedModel->hasInstrSchedModel()) {

2988 unsigned DecRemIssue = IncMOps * SchedModel->getMicroOpFactor();

2989 assert(Rem->RemIssueCount >= DecRemIssue && "MOps double counted");

2990 Rem->RemIssueCount -= DecRemIssue;

2991 if (ZoneCritResIdx) {

2992

2993 unsigned ScaledMOps =

2994 RetiredMOps * SchedModel->getMicroOpFactor();

2995

2996

2997

2999 >= (int)SchedModel->getLatencyFactor()) {

3000 ZoneCritResIdx = 0;

3001 LLVM_DEBUG(dbgs() << " *** Critical resource NumMicroOps: "

3002 << ScaledMOps / SchedModel->getLatencyFactor()

3003 << "c\n");

3004 }

3005 }

3007 PI = SchedModel->getWriteProcResBegin(SC),

3008 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {

3009 unsigned RCycle =

3010 countResource(SC, PI->ProcResourceIdx, PI->ReleaseAtCycle, NextCycle,

3011 PI->AcquireAtCycle);

3012 if (RCycle > NextCycle)

3013 NextCycle = RCycle;

3014 }

3016

3017

3018

3019

3021 PI = SchedModel->getWriteProcResBegin(SC),

3022 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {

3023 unsigned PIdx = PI->ProcResourceIdx;

3024 if (SchedModel->getProcResource(PIdx)->BufferSize == 0) {

3025

3027 unsigned ReservedUntil, InstanceIdx;

3029 SC, PIdx, PI->ReleaseAtCycle, PI->AcquireAtCycle);

3031 ReservedResourceSegments[InstanceIdx].add(

3033 NextCycle, PI->AcquireAtCycle, PI->ReleaseAtCycle),

3035 } else {

3036 ReservedResourceSegments[InstanceIdx].add(

3038 NextCycle, PI->AcquireAtCycle, PI->ReleaseAtCycle),

3040 }

3041 } else {

3042

3043 unsigned ReservedUntil, InstanceIdx;

3045 SC, PIdx, PI->ReleaseAtCycle, PI->AcquireAtCycle);

3047 ReservedCycles[InstanceIdx] =

3048 std::max(ReservedUntil, NextCycle + PI->ReleaseAtCycle);

3049 } else

3050 ReservedCycles[InstanceIdx] = NextCycle;

3051 }

3052 }

3053 }

3054 }

3055 }

3056

3057 unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency;

3058 unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency;

3059 if (SU->getDepth() > TopLatency) {

3060 TopLatency = SU->getDepth();

3062 << SU->NodeNum << ") " << TopLatency << "c\n");

3063 }

3064 if (SU->getHeight() > BotLatency) {

3067 << SU->NodeNum << ") " << BotLatency << "c\n");

3068 }

3069

3070 if (NextCycle > CurrCycle)

3072 else

3073

3074

3075 IsResourceLimited =

3078

3079

3080

3081

3082

3083 CurrMOps += IncMOps;

3084

3085

3086

3087

3088

3092 << " group\n");

3094 }

3095

3096 while (CurrMOps >= SchedModel->getIssueWidth()) {

3097 LLVM_DEBUG(dbgs() << " *** Max MOps " << CurrMOps << " at cycle "

3098 << CurrCycle << '\n');

3100 }

3102}

3103

3104

3105

3107

3109 MinReadyCycle = std::numeric_limits::max();

3110

3111

3112

3113 for (unsigned I = 0, E = Pending.size(); I < E; ++I) {

3116

3118

3119 if (ReadyCycle < MinReadyCycle)

3120 MinReadyCycle = ReadyCycle;

3121

3123 break;

3124

3126 if (E != Pending.size()) {

3127 --I;

3128 --E;

3129 }

3130 }

3131 CheckPending = false;

3132}

3133

3134

3138 else {

3139 assert(Pending.isInQueue(SU) && "bad ready count");

3141 }

3142}

3143

3144

3145

3146

3148 if (CheckPending)

3150

3151

3156 continue;

3157 }

3158 ++I;

3159 }

3160 for (unsigned i = 0; Available.empty(); ++i) {

3161

3162

3163

3164 (void)i;

3167 }

3168

3171

3174 return nullptr;

3175}

3176

3177#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

3178

3179

3180

3181

3183 if (->hasInstrSchedModel())

3184 return;

3185

3186 unsigned ResourceCount = SchedModel->getNumProcResourceKinds();

3187 unsigned StartIdx = 0;

3188

3189 for (unsigned ResIdx = 0; ResIdx < ResourceCount; ++ResIdx) {

3190 const unsigned NumUnits = SchedModel->getProcResource(ResIdx)->NumUnits;

3191 std::string ResName = SchedModel->getResourceName(ResIdx);

3192 for (unsigned UnitIdx = 0; UnitIdx < NumUnits; ++UnitIdx) {

3193 dbgs() << ResName << "(" << UnitIdx << ") = ";

3195 if (ReservedResourceSegments.count(StartIdx + UnitIdx))

3196 dbgs() << ReservedResourceSegments.at(StartIdx + UnitIdx);

3197 else

3198 dbgs() << "{ }\n";

3199 } else

3200 dbgs() << ReservedCycles[StartIdx + UnitIdx] << "\n";

3201 }

3202 StartIdx += NumUnits;

3203 }

3204}

3205

3206

3207

3209 unsigned ResFactor;

3210 unsigned ResCount;

3211 if (ZoneCritResIdx) {

3212 ResFactor = SchedModel->getResourceFactor(ZoneCritResIdx);

3214 } else {

3215 ResFactor = SchedModel->getMicroOpFactor();

3216 ResCount = RetiredMOps * ResFactor;

3217 }

3218 unsigned LFactor = SchedModel->getLatencyFactor();

3219 dbgs() << Available.getName() << " @" << CurrCycle << "c\n"

3220 << " Retired: " << RetiredMOps;

3222 dbgs() << "\n Critical: " << ResCount / LFactor << "c, "

3223 << ResCount / ResFactor << " "

3224 << SchedModel->getResourceName(ZoneCritResIdx)

3225 << "\n ExpectedLatency: " << ExpectedLatency << "c\n"

3226 << (IsResourceLimited ? " - Resource" : " - Latency")

3227 << " limited.\n";

3230}

3231#endif

3232

3233

3234

3235

3236

3240 if ( Policy .ReduceResIdx && Policy .DemandResIdx)

3241 return;

3242

3245 PI = SchedModel->getWriteProcResBegin(SC),

3246 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {

3247 if (PI->ProcResourceIdx == Policy.ReduceResIdx)

3248 ResDelta.CritResources += PI->ReleaseAtCycle;

3249 if (PI->ProcResourceIdx == Policy.DemandResIdx)

3250 ResDelta.DemandedResources += PI->ReleaseAtCycle;

3251 }

3252}

3253

3254

3255

3256

3257

3258

3259

3260

3261

3262

3263

3264

3265

3266

3267

3268

3269

3272 RemLatency = std::max(RemLatency,

3274 RemLatency = std::max(RemLatency,

3276 return RemLatency;

3277}

3278

3279

3280

3281bool GenericSchedulerBase::shouldReduceLatency(const CandPolicy &Policy,

3282 SchedBoundary &CurrZone,

3283 bool ComputeRemLatency,

3284 unsigned &RemLatency) const {

3285

3286

3288 return true;

3289

3290

3292 return false;

3293

3294 if (ComputeRemLatency)

3296

3297 return RemLatency + CurrZone.getCurrCycle() > Rem.CriticalPath;

3298}

3299

3300

3301

3305

3306

3307

3308

3309

3310 unsigned OtherCritIdx = 0;

3311 unsigned OtherCount =

3313

3314 bool OtherResLimited = false;

3315 unsigned RemLatency = 0;

3316 bool RemLatencyComputed = false;

3317 if (SchedModel->hasInstrSchedModel() && OtherCount != 0) {

3319 RemLatencyComputed = true;

3321 OtherCount, RemLatency, false);

3322 }

3323

3324

3325

3326

3327 if (!OtherResLimited &&

3328 (IsPostRA || shouldReduceLatency(Policy, CurrZone, !RemLatencyComputed,

3329 RemLatency))) {

3332 << " RemainingLatency " << RemLatency << " + "

3333 << CurrZone.getCurrCycle() << "c > CritPath "

3334 << Rem.CriticalPath << "\n");

3335 }

3336

3338 return;

3339

3341 dbgs() << " " << CurrZone.Available.getName() << " ResourceLimited: "

3342 << SchedModel->getResourceName(CurrZone.getZoneCritResIdx()) << "\n";

3343 } if (OtherResLimited) dbgs()

3344 << " RemainingLimit: "

3345 << SchedModel->getResourceName(OtherCritIdx) << "\n";

3347 << " Latency limited both directions.\n");

3348

3351

3352 if (OtherResLimited)

3354}

3355

3356#ifndef NDEBUG

3359

3360 switch (Reason) {

3361 case NoCand: return "NOCAND ";

3362 case Only1: return "ONLY1 ";

3363 case PhysReg: return "PHYS-REG ";

3364 case RegExcess: return "REG-EXCESS";

3366 case Stall: return "STALL ";

3367 case Cluster: return "CLUSTER ";

3368 case Weak: return "WEAK ";

3369 case RegMax: return "REG-MAX ";

3376 case NodeOrder: return "ORDER ";

3378 };

3379

3381}

3382

3385 unsigned ResIdx = 0;

3387 switch (Cand.Reason) {

3388 default:

3389 break;

3392 break;

3395 break;

3398 break;

3401 break;

3404 break;

3407 break;

3410 break;

3413 break;

3416 break;

3417 }

3419 if (P.isValid())

3420 dbgs() << " " << TRI->getRegPressureSetName(P.getPSet())

3421 << ":" << P.getUnitInc() << " ";

3422 else

3423 dbgs() << " ";

3424 if (ResIdx)

3425 dbgs() << " " << SchedModel->getProcResource(ResIdx)->Name << " ";

3426 else

3427 dbgs() << " ";

3430 else

3431 dbgs() << " ";

3432 dbgs() << '\n';

3433}

3434#endif

3435

3436

3437

3438

3443 if (TryVal < CandVal) {

3444 TryCand.Reason = Reason;

3445 return true;

3446 }

3447 if (TryVal > CandVal) {

3448 if (Cand.Reason > Reason)

3449 Cand.Reason = Reason;

3450 return true;

3451 }

3452 return false;

3453}

3454

3459 if (TryVal > CandVal) {

3460 TryCand.Reason = Reason;

3461 return true;

3462 }

3463 if (TryVal < CandVal) {

3464 if (Cand.Reason > Reason)

3465 Cand.Reason = Reason;

3466 return true;

3467 }

3468 return false;

3469}

3470

3474 if (Zone.isTop()) {

3475

3476

3477

3482 return true;

3483 }

3486 return true;

3487 } else {

3488

3489

3490

3495 return true;

3496 }

3499 return true;

3500 }

3501 return false;

3502}

3503

3505 bool IsPostRA = false) {

3506 LLVM_DEBUG(dbgs() << "Pick " << (IsTop ? "Top " : "Bot ")

3508 << (IsPostRA ? "post-RA" : "pre-RA") << "]\n");

3509

3510 if (IsPostRA) {

3511 if (IsTop)

3512 NumTopPostRA++;

3513 else

3514 NumBotPostRA++;

3515

3516 switch (Reason) {

3518 NumNoCandPostRA++;

3519 return;

3521 NumOnly1PostRA++;

3522 return;

3524 NumPhysRegPostRA++;

3525 return;

3527 NumRegExcessPostRA++;

3528 return;

3530 NumRegCriticalPostRA++;

3531 return;

3533 NumStallPostRA++;

3534 return;

3536 NumClusterPostRA++;

3537 return;

3539 NumWeakPostRA++;

3540 return;

3542 NumRegMaxPostRA++;

3543 return;

3545 NumResourceReducePostRA++;

3546 return;

3548 NumResourceDemandPostRA++;

3549 return;

3551 NumTopDepthReducePostRA++;

3552 return;

3554 NumTopPathReducePostRA++;

3555 return;

3557 NumBotHeightReducePostRA++;

3558 return;

3560 NumBotPathReducePostRA++;

3561 return;

3563 NumNodeOrderPostRA++;

3564 return;

3566 NumFirstValidPostRA++;

3567 return;

3568 };

3569 } else {

3570 if (IsTop)

3571 NumTopPreRA++;

3572 else

3573 NumBotPreRA++;

3574

3575 switch (Reason) {

3577 NumNoCandPreRA++;

3578 return;

3580 NumOnly1PreRA++;

3581 return;

3583 NumPhysRegPreRA++;

3584 return;

3586 NumRegExcessPreRA++;

3587 return;

3589 NumRegCriticalPreRA++;

3590 return;

3592 NumStallPreRA++;

3593 return;

3595 NumClusterPreRA++;

3596 return;

3598 NumWeakPreRA++;

3599 return;

3601 NumRegMaxPreRA++;

3602 return;

3604 NumResourceReducePreRA++;

3605 return;

3607 NumResourceDemandPreRA++;

3608 return;

3610 NumTopDepthReducePreRA++;

3611 return;

3613 NumTopPathReducePreRA++;

3614 return;

3616 NumBotHeightReducePreRA++;

3617 return;

3619 NumBotPathReducePreRA++;

3620 return;

3622 NumNodeOrderPreRA++;

3623 return;

3625 NumFirstValidPreRA++;

3626 return;

3627 };

3628 }

3630}

3631

3633 bool IsPostRA = false) {

3635}

3636

3639 "(PreRA)GenericScheduler needs vreg liveness");

3643

3645 DAG->computeDFSResult();

3646

3650

3651

3652

3653

3654

3656 if ( Top .HazardRec) {

3657 Top.HazardRec = DAG->TII->CreateTargetMIHazardRecognizer(Itin, DAG);

3658 }

3659 if ( Bot .HazardRec) {

3660 Bot.HazardRec = DAG->TII->CreateTargetMIHazardRecognizer(Itin, DAG);

3661 }

3664

3667}

3668

3669

3675

3676

3677

3678

3679

3681 for (unsigned VT = MVT::i64; VT > (unsigned)MVT::i1; --VT) {

3684 unsigned NIntRegs = Context->RegClassInfo->getNumAllocatableRegs(

3687 break;

3688 }

3689 }

3690

3691

3692

3694

3695

3698

3699

3703 }

3704

3714 }

3715

3718}

3719

3721

3722#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

3723 dbgs() << "GenericScheduler RegionPolicy: "

3724 << " ShouldTrackPressure=" << RegionPolicy.ShouldTrackPressure

3725 << " OnlyTopDown=" << RegionPolicy.OnlyTopDown

3726 << " OnlyBottomUp=" << RegionPolicy.OnlyBottomUp

3727 << "\n";

3728#endif

3729}

3730

3731

3732

3733

3734

3735

3736

3737

3738

3739

3741 if (Rem.CyclicCritPath == 0 || Rem.CyclicCritPath >= Rem.CriticalPath)

3742 return;

3743

3744

3745 unsigned IterCount =

3746 std::max(Rem.CyclicCritPath * SchedModel->getLatencyFactor(),

3747 Rem.RemIssueCount);

3748

3749 unsigned AcyclicCount = Rem.CriticalPath * SchedModel->getLatencyFactor();

3750

3751 unsigned InFlightCount =

3752 (AcyclicCount * Rem.RemIssueCount + IterCount-1) / IterCount;

3753 unsigned BufferLimit =

3755

3756 Rem.IsAcyclicLatencyLimited = InFlightCount > BufferLimit;

3757

3759 dbgs() << "IssueCycles="

3760 << Rem.RemIssueCount / SchedModel->getLatencyFactor() << "c "

3761 << "IterCycles=" << IterCount / SchedModel->getLatencyFactor()

3762 << "c NumIters=" << (AcyclicCount + IterCount - 1) / IterCount

3763 << " InFlight=" << InFlightCount / SchedModel->getMicroOpFactor()

3764 << "m BufferLim=" << SchedModel->getMicroOpBufferSize() << "m\n";

3765 if (Rem.IsAcyclicLatencyLimited) dbgs() << " ACYCLIC LATENCY LIMIT\n");

3766}

3767

3769 Rem.CriticalPath = DAG->ExitSU.getDepth();

3770

3771

3772 for (const SUnit *SU : Bot.Available) {

3775 }

3776 LLVM_DEBUG(dbgs() << "Critical Path(GS-RR ): " << Rem.CriticalPath << '\n');

3778 errs() << "Critical Path(GS-RR ): " << Rem.CriticalPath << " \n";

3779 }

3780

3782 Rem.CyclicCritPath = DAG->computeCyclicCriticalPath();

3784 }

3785}

3786

3793

3794

3796 Reason)) {

3797 return true;

3798 }

3799

3800

3802 return false;

3803

3804

3805

3808 if (TryPSet == CandPSet) {

3810 Reason);

3811 }

3812

3813 int TryRank = TryP.isValid() ? TRI->getRegPressureSetScore(MF, TryPSet) :

3814 std::numeric_limits::max();

3815

3816 int CandRank = CandP.isValid() ? TRI->getRegPressureSetScore(MF, CandPSet) :

3817 std::numeric_limits::max();

3818

3819

3822 return tryGreater(TryRank, CandRank, TryCand, Cand, Reason);

3823}

3824

3828

3829

3830

3831

3832

3833

3834

3835

3838

3839 if (MI->isCopy()) {

3840 unsigned ScheduledOper = isTop ? 1 : 0;

3841 unsigned UnscheduledOper = isTop ? 0 : 1;

3842

3843

3844 if (MI->getOperand(ScheduledOper).getReg().isPhysical())

3845 return 1;

3846

3847

3849 if (MI->getOperand(UnscheduledOper).getReg().isPhysical())

3850 return AtBoundary ? -1 : 1;

3851 }

3852

3853 if (MI->isMoveImmediate()) {

3854

3855

3856

3857 bool DoBias = true;

3859 if (Op.isReg() && .getReg().isPhysical()) {

3860 DoBias = false;

3861 break;

3862 }

3863 }

3864

3865 if (DoBias)

3866 return isTop ? -1 : 1;

3867 }

3868

3869 return 0;

3870}

3871

3873 bool AtTop,

3876 Cand.SU = SU;

3877 Cand.AtTop = AtTop;

3878 if (DAG->isTrackingPressure()) {

3879 if (AtTop) {

3883 DAG->getRegionCriticalPSets(),

3884 DAG->getRegPressure().MaxSetPressure);

3885 } else {

3889 &DAG->getPressureDiff(Cand.SU),

3891 DAG->getRegionCriticalPSets(),

3892 DAG->getRegPressure().MaxSetPressure);

3893 } else {

3896 DAG->getPressureDiff(Cand.SU),

3898 DAG->getRegionCriticalPSets(),

3899 DAG->getRegPressure().MaxSetPressure);

3900 }

3901 }

3902 }

3904 << " Try SU(" << Cand.SU->NodeNum << ") "

3907}

3908

3909

3910

3911

3912

3913

3914

3915

3916

3917

3918

3919

3923

3926 return true;

3927 }

3928

3929

3933

3934

3938 DAG->MF))

3940

3941

3945 DAG->MF))

3947

3948

3949

3950

3951

3952

3953 bool SameBoundary = Zone != nullptr;

3954 if (SameBoundary) {

3955

3956

3957

3958 if (Rem.IsAcyclicLatencyLimited && !Zone->getCurrMOps() &&

3961

3962

3966 }

3967

3968

3969

3970

3971

3972

3973

3976 bool CandIsClusterSucc =

3978 bool TryCandIsClusterSucc =

3980

3981 if (tryGreater(TryCandIsClusterSucc, CandIsClusterSucc, TryCand, Cand,

3984

3985 if (SameBoundary) {

3986

3989 TryCand, Cand, Weak))

3991 }

3992

3993

3997 DAG->MF))

3999

4000 if (SameBoundary) {

4001

4010

4011

4012

4014 Rem .IsAcyclicLatencyLimited && tryLatency(TryCand, Cand, *Zone))

4016

4017

4021 return true;

4022 }

4023 }

4024

4025 return false;

4026}

4027

4028

4029

4030

4031

4032

4037

4039

4041 for (SUnit *SU : Q) {

4042

4045

4048

4053 }

4054 }

4055}

4056

4057

4059

4060

4061 if (SUnit *SU = Bot.pickOnlyChoice()) {

4062 IsTopNode = false;

4064 return SU;

4065 }

4066 if (SUnit *SU = Top.pickOnlyChoice()) {

4067 IsTopNode = true;

4069 return SU;

4070 }

4071

4072

4075

4076

4079

4080

4082 if ( BotCand .isValid() || BotCand.SU->isScheduled ||

4083 BotCand.Policy != BotPolicy) {

4086 assert(BotCand.Reason != NoCand && "failed to find the first candidate");

4087 } else {

4089#ifndef NDEBUG

4095 "Last pick result should correspond to re-picking right now");

4096 }

4097#endif

4098 }

4099

4100

4102 if ( TopCand .isValid() || TopCand.SU->isScheduled ||

4103 TopCand.Policy != TopPolicy) {

4106 assert(TopCand.Reason != NoCand && "failed to find the first candidate");

4107 } else {

4109#ifndef NDEBUG

4115 "Last pick result should correspond to re-picking right now");

4116 }

4117#endif

4118 }

4119

4120

4128 }

4129

4130 IsTopNode = Cand.AtTop;

4132 return Cand.SU;

4133}

4134

4135

4137 if (DAG->top() == DAG->bottom()) {

4138 assert(Top.Available.empty() && Top.Pending.empty() &&

4139 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");

4140 return nullptr;

4141 }

4144 SU = Top.pickOnlyChoice();

4145 if (!SU) {

4147 TopCand.reset(NoPolicy);

4152 }

4153 IsTopNode = true;

4155 SU = Bot.pickOnlyChoice();

4156 if (!SU) {

4158 BotCand.reset(NoPolicy);

4163 }

4164 IsTopNode = false;

4165 } else {

4167 }

4169

4170

4171

4172

4173

4174

4175

4176

4177

4178

4179

4180

4181

4182

4183

4184

4186 Top.removeReady(SU);

4188 Bot.removeReady(SU);

4189

4192

4193 if (IsTopNode) {

4195 ++NumInstrsInSourceOrderPreRA;

4196 } else {

4199 ++NumInstrsInSourceOrderPreRA;

4200 }

4201

4202 NumInstrsScheduledPreRA += 1;

4203

4204 return SU;

4205}

4206

4209 if (!isTop)

4210 ++InsertPos;

4212

4213

4214

4215 for (SDep &Dep : Deps) {

4216 if (Dep.getKind() != SDep::Data || !Dep.getReg().isPhysical())

4217 continue;

4218 SUnit *DepSU = Dep.getSUnit();

4219 if (isTop ? DepSU->Succs.size() > 1 : DepSU->Preds.size() > 1)

4220 continue;

4222 if (!Copy->isCopy() && !Copy->isMoveImmediate())

4223 continue;

4225 DAG->dumpNode(*Dep.getSUnit()));

4226 DAG->moveInstruction(Copy, InsertPos);

4227 }

4228}

4229

4230

4231

4232

4233

4234

4235

4236

4238 if (IsTopNode) {

4244 dbgs() << " Top Cluster: ";

4245 for (auto *N : *TopCluster)

4246 dbgs() << N->NodeNum << '\t';

4247 dbgs() << '\n';

4248 }

4249 });

4250 Top.bumpNode(SU);

4253 } else {

4259 dbgs() << " Bot Cluster: ";

4260 for (auto *N : *BotCluster)

4261 dbgs() << N->NodeNum << '\t';

4262 dbgs() << '\n';

4263 }

4264 });

4265 Bot.bumpNode(SU);

4268 }

4269}

4270

4274

4275static MachineSchedRegistry

4278

4279

4280

4281

4282

4284 DAG = Dag;

4287

4291

4292

4293

4295 if ( Top .HazardRec) {

4296 Top.HazardRec = DAG->TII->CreateTargetMIHazardRecognizer(Itin, DAG);

4297 }

4298 if ( Bot .HazardRec) {

4299 Bot.HazardRec = DAG->TII->CreateTargetMIHazardRecognizer(Itin, DAG);

4300 }

4303}

4304

4309

4310

4311

4314

4315

4318

4319

4329 }

4330

4333}

4334

4336 Rem.CriticalPath = DAG->ExitSU.getDepth();

4337

4338

4339 for (const SUnit *SU : Bot.Available) {

4342 }

4343 LLVM_DEBUG(dbgs() << "Critical Path: (PGS-RR) " << Rem.CriticalPath << '\n');

4345 errs() << "Critical Path(PGS-RR ): " << Rem.CriticalPath << " \n";

4346 }

4347}

4348

4349

4350

4351

4352

4353

4356

4359 return true;

4360 }

4361

4362

4363 if (tryLess(Top.getLatencyStallCycles(TryCand.SU),

4364 Top.getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))

4366

4367

4370 bool CandIsClusterSucc =

4372 bool TryCandIsClusterSucc =

4374

4375 if (tryGreater(TryCandIsClusterSucc, CandIsClusterSucc, TryCand, Cand,

4378

4386

4387

4388

4390

4394 }

4395

4396

4399 return true;

4400 }

4401

4402 return false;

4403}

4404

4408 for (SUnit *SU : Q) {

4410 TryCand.SU = SU;

4416 }

4417 }

4418}

4419

4420

4422

4423

4424

4425

4426

4427 if (SUnit *SU = Bot.pickOnlyChoice()) {

4428 IsTopNode = false;

4429 tracePick(Only1, false, true);

4430 return SU;

4431 }

4432 if (SUnit *SU = Top.pickOnlyChoice()) {

4433 IsTopNode = true;

4434 tracePick(Only1, true, true);

4435 return SU;

4436 }

4437

4438

4441

4442

4445

4446

4448 if ( BotCand .isValid() || BotCand.SU->isScheduled ||

4449 BotCand.Policy != BotPolicy) {

4452 assert(BotCand.Reason != NoCand && "failed to find the first candidate");

4453 } else {

4455#ifndef NDEBUG

4461 "Last pick result should correspond to re-picking right now");

4462 }

4463#endif

4464 }

4465

4466

4468 if ( TopCand .isValid() || TopCand.SU->isScheduled ||

4469 TopCand.Policy != TopPolicy) {

4472 assert(TopCand.Reason != NoCand && "failed to find the first candidate");

4473 } else {

4475#ifndef NDEBUG

4481 "Last pick result should correspond to re-picking right now");

4482 }

4483#endif

4484 }

4485

4486

4494 }

4495

4496 IsTopNode = Cand.AtTop;

4497 tracePick(Cand, true);

4498 return Cand.SU;

4499}

4500

4501

4503 if (DAG->top() == DAG->bottom()) {

4504 assert(Top.Available.empty() && Top.Pending.empty() &&

4505 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");

4506 return nullptr;

4507 }

4510 SU = Bot.pickOnlyChoice();

4511 if (SU) {

4512 tracePick(Only1, true, true);

4513 } else {

4515 BotCand.reset(NoPolicy);

4516

4517

4523 }

4524 IsTopNode = false;

4526 SU = Top.pickOnlyChoice();

4527 if (SU) {

4528 tracePick(Only1, true, true);

4529 } else {

4531 TopCand.reset(NoPolicy);

4532

4533

4539 }

4540 IsTopNode = true;

4541 } else {

4543 }

4545

4547 Top.removeReady(SU);

4549 Bot.removeReady(SU);

4550

4553

4554 if (IsTopNode) {

4556 ++NumInstrsInSourceOrderPostRA;

4557 } else {

4560 ++NumInstrsInSourceOrderPostRA;

4561 }

4562

4563 NumInstrsScheduledPostRA += 1;

4564

4565 return SU;

4566}

4567

4568

4569

4571 if (IsTopNode) {

4574 Top.bumpNode(SU);

4575 } else {

4578 Bot.bumpNode(SU);

4579 }

4580}

4581

4582

4583

4584

4585

4586namespace {

4587

4588

4589struct ILPOrder {

4591 const BitVector *ScheduledTrees = nullptr;

4592 bool MaximizeILP;

4593

4594 ILPOrder(bool MaxILP) : MaximizeILP(MaxILP) {}

4595

4596

4597

4598

4599 bool operator()(const SUnit *A, const SUnit *B) const {

4600 unsigned SchedTreeA = DFSResult->getSubtreeID(A);

4601 unsigned SchedTreeB = DFSResult->getSubtreeID(B);

4602 if (SchedTreeA != SchedTreeB) {

4603

4604 if (ScheduledTrees->test(SchedTreeA) != ScheduledTrees->test(SchedTreeB))

4605 return ScheduledTrees->test(SchedTreeB);

4606

4607

4612 }

4613 }

4614 if (MaximizeILP)

4616 else

4618 }

4619};

4620

4621

4622class ILPScheduler : public MachineSchedStrategy {

4623 ScheduleDAGMILive *DAG = nullptr;

4624 ILPOrder Cmp;

4625

4626 std::vector<SUnit*> ReadyQ;

4627

4628public:

4629 ILPScheduler(bool MaximizeILP) : Cmp(MaximizeILP) {}

4630

4631 void initialize(ScheduleDAGMI *dag) override {

4633 DAG = static_cast<ScheduleDAGMILive*>(dag);

4637 ReadyQ.clear();

4638 }

4639

4640 void registerRoots() override {

4641

4642 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);

4643 }

4644

4645

4646

4647

4648

4649 SUnit *pickNode(bool &IsTopNode) override {

4650 if (ReadyQ.empty()) return nullptr;

4651 std::pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);

4652 SUnit *SU = ReadyQ.back();

4653 ReadyQ.pop_back();

4654 IsTopNode = false;

4656 << "SU(" << SU->NodeNum << ") "

4659 << " @"

4662 << '\n'

4663 << "Scheduling " << *SU->getInstr());

4664 return SU;

4665 }

4666

4667

4668 void scheduleTree(unsigned SubtreeID) override {

4669 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);

4670 }

4671

4672

4673

4674 void schedNode(SUnit *SU, bool IsTopNode) override {

4675 assert(!IsTopNode && "SchedDFSResult needs bottom-up");

4676 }

4677

4678 void releaseTopNode(SUnit *) override { }

4679

4680 void releaseBottomNode(SUnit *SU) override {

4681 ReadyQ.push_back(SU);

4682 std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);

4683 }

4684};

4685

4686}

4687

4694

4699

4700

4701

4702

4703

4704#ifndef NDEBUG

4705namespace {

4706

4707

4708

4709template

4710struct SUnitOrder {

4712 if (IsReverse)

4713 return A->NodeNum > B->NodeNum;

4714 else

4715 return A->NodeNum < B->NodeNum;

4716 }

4717};

4718

4719

4720class InstructionShuffler : public MachineSchedStrategy {

4721 bool IsAlternating;

4722 bool IsTopDown;

4723

4724

4725

4726

4727 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder>

4728 TopQ;

4729

4730

4731 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder>

4732 BottomQ;

4733

4734public:

4735 InstructionShuffler(bool alternate, bool topdown)

4736 : IsAlternating(alternate), IsTopDown(topdown) {}

4737

4738 void initialize(ScheduleDAGMI*) override {

4740 BottomQ.clear();

4741 }

4742

4743

4744

4745

4746 SUnit *pickNode(bool &IsTopNode) override {

4747 SUnit *SU;

4748 if (IsTopDown) {

4749 do {

4750 if (TopQ.empty()) return nullptr;

4751 SU = TopQ.top();

4752 TopQ.pop();

4754 IsTopNode = true;

4755 } else {

4756 do {

4757 if (BottomQ.empty()) return nullptr;

4758 SU = BottomQ.top();

4759 BottomQ.pop();

4761 IsTopNode = false;

4762 }

4763 if (IsAlternating)

4764 IsTopDown = !IsTopDown;

4765 return SU;

4766 }

4767

4768 void schedNode(SUnit *SU, bool IsTopNode) override {}

4769

4770 void releaseTopNode(SUnit *SU) override {

4771 TopQ.push(SU);

4772 }

4773 void releaseBottomNode(SUnit *SU) override {

4774 BottomQ.push(SU);

4775 }

4776};

4777

4778}

4779

4781 bool Alternate =

4785 C, std::make_unique(Alternate, TopDown));

4786}

4787

4789 "shuffle", "Shuffle machine instructions alternating directions",

4791#endif

4792

4793

4794

4795

4796

4797#ifndef NDEBUG

4798

4799template <>

4802

4803template <>

4806

4808 return std::string(G->MF.getName());

4809 }

4810

4814

4817 return false;

4820 }

4821

4822

4823

4828 return "color=cyan,style=dashed";

4830 return "color=blue,style=dashed";

4831 return "";

4832 }

4833

4835 std::string Str;

4840 SS << "SU:" << SU->NodeNum;

4841 if (DFS)

4843 return Str;

4844 }

4845

4847 return G->getGraphNodeLabel(SU);

4848 }

4849

4851 std::string Str("shape=Mrecord");

4855 if (DFS) {

4856 Str += ",style=filled,fillcolor=\"#";

4858 Str += '"';

4859 }

4860 return Str;

4861 }

4862};

4863

4864#endif

4865

4866

4867

4869#ifndef NDEBUG

4870 ViewGraph(this, Name, false, Title);

4871#else

4872 errs() << "ScheduleDAGMI::viewGraph is only available in debug builds on "

4873 << "systems with Graphviz or gv!\n";

4874#endif

4875}

4876

4877

4881

4882

4883

4884

4885

4888 return A.first < B.first;

4889}

4890

4891unsigned ResourceSegments::getFirstAvailableAt(

4892 unsigned CurrCycle, unsigned AcquireAtCycle, unsigned ReleaseAtCycle,

4894 IntervalBuilder) const {

4896 "Cannot execute on an un-sorted set of intervals.");

4897

4898

4899

4900 if (AcquireAtCycle == ReleaseAtCycle)

4901 return CurrCycle;

4902

4903 unsigned RetCycle = CurrCycle;

4905 IntervalBuilder(RetCycle, AcquireAtCycle, ReleaseAtCycle);

4906 for (auto &Interval : _Intervals) {

4908 continue;

4909

4910

4911

4913 "Invalid intervals configuration.");

4914 RetCycle += (unsigned)Interval.second - (unsigned)NewInterval.first;

4915 NewInterval = IntervalBuilder(RetCycle, AcquireAtCycle, ReleaseAtCycle);

4916 }

4917 return RetCycle;

4918}

4919

4921 const unsigned CutOff) {

4922 assert(A.first <= A.second && "Cannot add negative resource usage");

4923 assert(CutOff > 0 && "0-size interval history has no use.");

4924

4925

4926

4927

4928

4929 if (A.first == A.second)

4930 return;

4931

4935 }) &&

4936 "A resource is being overwritten");

4937 _Intervals.push_back(A);

4938

4939 sortAndMerge();

4940

4941

4942

4943 while (_Intervals.size() > CutOff)

4944 _Intervals.pop_front();

4945}

4946

4949 assert(A.first <= A.second && "Invalid interval");

4950 assert(B.first <= B.second && "Invalid interval");

4951

4952

4953 if ((A.first == B.first) || (A.second == B.second))

4954 return true;

4955

4956

4957

4958 if ((A.first > B.first) && (A.second < B.second))

4959 return true;

4960

4961

4962

4963 if ((A.first > B.first) && (A.first < B.second) && (A.second > B.second))

4964 return true;

4965

4966

4967

4968 if ((A.first < B.first) && (B.first < A.second) && (B.second > B.first))

4969 return true;

4970

4971 return false;

4972}

4973

4974void ResourceSegments::sortAndMerge() {

4975 if (_Intervals.size() <= 1)

4976 return;

4977

4978

4980

4981

4982 auto next = std::next(std::begin(_Intervals));

4983 auto E = std::end(_Intervals);

4984 for (; next != E; ++next) {

4985 if (std::prev(next)->second >= next->first) {

4986 next->first = std::prev(next)->first;

4987 _Intervals.erase(std::prev(next));

4988 continue;

4989 }

4990 }

4991}

MachineInstrBuilder MachineInstrBuilder & DefMI

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

const TargetInstrInfo & TII

Function Alias Analysis false

static const Function * getParent(const Value *V)

This file implements the BitVector class.

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

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

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

#define clEnumValN(ENUMVAL, FLAGNAME, DESC)

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

static std::optional< ArrayRef< InsnRange >::iterator > intersects(const MachineInstr *StartMI, const MachineInstr *EndMI, ArrayRef< InsnRange > Ranges, const InstructionOrdering &Ordering)

Check if the instruction range [StartMI, EndMI] intersects any instruction range in Ranges.

This file defines the DenseMap class.

Generic implementation of equivalence classes through the use Tarjan's efficient union-find algorithm...

A common definition of LaneBitmask for use in TableGen and CodeGen.

static cl::opt< MISched::Direction > PostRADirection("misched-postra-direction", cl::Hidden, cl::desc("Post reg-alloc list scheduling direction"), cl::init(MISched::Unspecified), cl::values(clEnumValN(MISched::TopDown, "topdown", "Force top-down post reg-alloc list scheduling"), clEnumValN(MISched::BottomUp, "bottomup", "Force bottom-up post reg-alloc list scheduling"), clEnumValN(MISched::Bidirectional, "bidirectional", "Force bidirectional post reg-alloc list scheduling")))

static bool isSchedBoundary(MachineBasicBlock::iterator MI, MachineBasicBlock *MBB, MachineFunction *MF, const TargetInstrInfo *TII)

Return true of the given instruction should not be included in a scheduling region.

Definition MachineScheduler.cpp:762

static MachineSchedRegistry ILPMaxRegistry("ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler)

static cl::opt< bool > EnableMemOpCluster("misched-cluster", cl::Hidden, cl::desc("Enable memop clustering."), cl::init(true))

Machine Instruction Scheduler

Definition MachineScheduler.cpp:419

static MachineBasicBlock::const_iterator nextIfDebug(MachineBasicBlock::const_iterator I, MachineBasicBlock::const_iterator End)

If this iterator is a debug value, increment until reaching the End or a non-debug instruction.

Definition MachineScheduler.cpp:517

static const unsigned MinSubtreeSize

Definition MachineScheduler.cpp:294

static const unsigned InvalidCycle

Definition MachineScheduler.cpp:2472

static cl::opt< bool > MISchedSortResourcesInTrace("misched-sort-resources-in-trace", cl::Hidden, cl::init(true), cl::desc("Sort the resources printed in the dump trace"))

static cl::opt< bool > EnableCyclicPath("misched-cyclicpath", cl::Hidden, cl::desc("Enable cyclic critical path analysis."), cl::init(true))

static MachineBasicBlock::const_iterator priorNonDebug(MachineBasicBlock::const_iterator I, MachineBasicBlock::const_iterator Beg)

Decrement this iterator until reaching the top or a non-debug instr.

Definition MachineScheduler.cpp:496

static cl::opt< MachineSchedRegistry::ScheduleDAGCtor, false, RegisterPassParser< MachineSchedRegistry > > MachineSchedOpt("misched", cl::init(&useDefaultMachineSched), cl::Hidden, cl::desc("Machine instruction scheduler to use"))

MachineSchedOpt allows command line selection of the scheduler.

static cl::opt< bool > EnableMachineSched("enable-misched", cl::desc("Enable the machine instruction scheduling pass."), cl::init(true), cl::Hidden)

static unsigned computeRemLatency(SchedBoundary &CurrZone)

Compute remaining latency.

Definition MachineScheduler.cpp:3270

static cl::opt< unsigned > MISchedCutoff("misched-cutoff", cl::Hidden, cl::desc("Stop scheduling after N instructions"), cl::init(~0U))

static cl::opt< unsigned > SchedOnlyBlock("misched-only-block", cl::Hidden, cl::desc("Only schedule this MBB#"))

static cl::opt< bool > EnableRegPressure("misched-regpressure", cl::Hidden, cl::desc("Enable register pressure scheduling."), cl::init(true))

static void tracePick(GenericSchedulerBase::CandReason Reason, bool IsTop, bool IsPostRA=false)

Definition MachineScheduler.cpp:3504

static MachineSchedRegistry GenericSchedRegistry("converge", "Standard converging scheduler.", createConvergingSched)

static cl::opt< unsigned > HeaderColWidth("misched-dump-schedule-trace-col-header-width", cl::Hidden, cl::desc("Set width of the columns with " "the resources and schedule units"), cl::init(19))

static cl::opt< bool > ForceFastCluster("force-fast-cluster", cl::Hidden, cl::desc("Switch to fast cluster algorithm with the lost " "of some fusion opportunities"), cl::init(false))

static cl::opt< unsigned > FastClusterThreshold("fast-cluster-threshold", cl::Hidden, cl::desc("The threshold for fast cluster"), cl::init(1000))

static bool checkResourceLimit(unsigned LFactor, unsigned Count, unsigned Latency, bool AfterSchedNode)

Given a Count of resource usage and a Latency value, return true if a SchedBoundary becomes resource ...

Definition MachineScheduler.cpp:2480

static ScheduleDAGInstrs * createInstructionShuffler(MachineSchedContext *C)

Definition MachineScheduler.cpp:4780

static ScheduleDAGInstrs * useDefaultMachineSched(MachineSchedContext *C)

A dummy default scheduler factory indicates whether the scheduler is overridden on the command line.

Definition MachineScheduler.cpp:469

static bool sortIntervals(const ResourceSegments::IntervalTy &A, const ResourceSegments::IntervalTy &B)

Sort predicate for the intervals stored in an instance of ResourceSegments.

Definition MachineScheduler.cpp:4886

static cl::opt< unsigned > ColWidth("misched-dump-schedule-trace-col-width", cl::Hidden, cl::desc("Set width of the columns showing resource booking."), cl::init(5))

static MachineSchedRegistry DefaultSchedRegistry("default", "Use the target's default scheduler choice.", useDefaultMachineSched)

static cl::opt< std::string > SchedOnlyFunc("misched-only-func", cl::Hidden, cl::desc("Only schedule this function"))

static const char * scheduleTableLegend

Definition MachineScheduler.cpp:1214

static ScheduleDAGInstrs * createConvergingSched(MachineSchedContext *C)

Definition MachineScheduler.cpp:4271

static cl::opt< bool > MischedDetailResourceBooking("misched-detail-resource-booking", cl::Hidden, cl::init(false), cl::desc("Show details of invoking getNextResoufceCycle."))

static cl::opt< unsigned > ViewMISchedCutoff("view-misched-cutoff", cl::Hidden, cl::desc("Hide nodes with more predecessor/successor than cutoff"))

In some situations a few uninteresting nodes depend on nearly all other nodes in the graph,...

static MachineSchedRegistry ShufflerRegistry("shuffle", "Shuffle machine instructions alternating directions", createInstructionShuffler)

static cl::opt< bool > EnablePostRAMachineSched("enable-post-misched", cl::desc("Enable the post-ra machine instruction scheduling pass."), cl::init(true), cl::Hidden)

static void getSchedRegions(MachineBasicBlock *MBB, MBBRegionsVector &Regions, bool RegionsTopDown)

Definition MachineScheduler.cpp:773

static cl::opt< unsigned > MIResourceCutOff("misched-resource-cutoff", cl::Hidden, cl::desc("Number of intervals to track"), cl::init(10))

static ScheduleDAGInstrs * createILPMaxScheduler(MachineSchedContext *C)

Definition MachineScheduler.cpp:4688

SmallVector< SchedRegion, 16 > MBBRegionsVector

Definition MachineScheduler.cpp:770

static cl::opt< bool > MISchedDumpReservedCycles("misched-dump-reserved-cycles", cl::Hidden, cl::init(false), cl::desc("Dump resource usage at schedule boundary."))

static cl::opt< unsigned > ReadyListLimit("misched-limit", cl::Hidden, cl::desc("Limit ready list to N instructions"), cl::init(256))

Avoid quadratic complexity in unusually large basic blocks by limiting the size of the ready lists.

static cl::opt< bool > DumpCriticalPathLength("misched-dcpl", cl::Hidden, cl::desc("Print critical path length to stdout"))

static ScheduleDAGInstrs * createILPMinScheduler(MachineSchedContext *C)

Definition MachineScheduler.cpp:4691

static cl::opt< bool > MISchedDumpScheduleTrace("misched-dump-schedule-trace", cl::Hidden, cl::init(false), cl::desc("Dump resource usage at schedule boundary."))

static MachineSchedRegistry ILPMinRegistry("ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler)

std::pair< uint64_t, uint64_t > Interval

FunctionAnalysisManager FAM

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

This file defines the PriorityQueue 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)

static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, const llvm::StringTable &StandardNames, VectorLibrary VecLib)

Initialize the set of available library functions based on the specified target triple.

This file describes how to lower LLVM code to machine code.

Target-Independent Code Generator Pass Configuration Options pass.

static const X86InstrFMA3Group Groups[]

Class recording the (high level) value of a variable.

A manager for alias analyses.

A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.

Class for arbitrary precision integers.

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

reverse_iterator rend() const

size_t size() const

size - Get the array size.

reverse_iterator rbegin() const

bool test(unsigned Idx) const

Represents analyses that only rely on functions' control flow.

iterator find(const_arg_type_t< KeyT > Val)

size_type count(const_arg_type_t< KeyT > Val) const

Return 1 if the specified key is in the map, 0 otherwise.

ECValue - The EquivalenceClasses data structure is just a set of these.

EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...

iterator_range< member_iterator > members(const ECValue &ECV) const

member_iterator unionSets(const ElemTy &V1, const ElemTy &V2)

union - Merge the two equivalence sets for the specified values, inserting them if they do not alread...

void traceCandidate(const SchedCandidate &Cand)

Definition MachineScheduler.cpp:3383

LLVM_ABI void setPolicy(CandPolicy &Policy, bool IsPostRA, SchedBoundary &CurrZone, SchedBoundary *OtherZone)

Set the CandPolicy given a scheduling zone given the current resources and latencies inside and outsi...

Definition MachineScheduler.cpp:3302

MachineSchedPolicy RegionPolicy

const TargetSchedModel * SchedModel

static const char * getReasonStr(GenericSchedulerBase::CandReason Reason)

Definition MachineScheduler.cpp:3357

const MachineSchedContext * Context

CandReason

Represent the type of SchedCandidate found within a single queue.

const TargetRegisterInfo * TRI

void checkAcyclicLatency()

Set IsAcyclicLatencyLimited if the acyclic path is longer than the cyclic critical path by more cycle...

Definition MachineScheduler.cpp:3740

SchedCandidate BotCand

Candidate last picked from Bot boundary.

SchedCandidate TopCand

Candidate last picked from Top boundary.

virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand, SchedBoundary *Zone) const

Apply a set of heuristics to a new candidate.

Definition MachineScheduler.cpp:3920

void dumpPolicy() const override

Definition MachineScheduler.cpp:3720

void initialize(ScheduleDAGMI *dag) override

Initialize the strategy after building the DAG for a new region.

Definition MachineScheduler.cpp:3637

void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop, const RegPressureTracker &RPTracker, RegPressureTracker &TempTracker)

Definition MachineScheduler.cpp:3872

void registerRoots() override

Notify this strategy that all roots have been released (including those that depend on EntrySU or Exi...

Definition MachineScheduler.cpp:3768

void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs) override

Initialize the per-region scheduling policy.

Definition MachineScheduler.cpp:3670

void reschedulePhysReg(SUnit *SU, bool isTop)

Definition MachineScheduler.cpp:4207

SUnit * pickNode(bool &IsTopNode) override

Pick the best node to balance the schedule. Implements MachineSchedStrategy.

Definition MachineScheduler.cpp:4136

void pickNodeFromQueue(SchedBoundary &Zone, const CandPolicy &ZonePolicy, const RegPressureTracker &RPTracker, SchedCandidate &Candidate)

Pick the best candidate from the queue.

Definition MachineScheduler.cpp:4033

void schedNode(SUnit *SU, bool IsTopNode) override

Update the scheduler's state after scheduling a node.

Definition MachineScheduler.cpp:4237

SUnit * pickNodeBidirectional(bool &IsTopNode)

Pick the best candidate node from either the top or bottom queue.

Definition MachineScheduler.cpp:4058

Itinerary data supplied by a subtarget to be used by a target.

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

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.

LiveInterval & getInterval(Register Reg)

Result of a LiveRange query.

VNInfo * valueIn() const

Return the value that is live-in to the instruction.

Segments::iterator iterator

LiveQueryResult Query(SlotIndex Idx) const

Query Liveness at Idx.

VNInfo * getVNInfoBefore(SlotIndex Idx) const

getVNInfoBefore - Return the VNInfo that is live up to but not necessarily including Idx,...

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.

bool isLocal(SlotIndex Start, SlotIndex End) const

True iff this segment is a single segment that lies between the specified boundaries,...

LLVM_ABI iterator find(SlotIndex Pos)

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

static LocationSize precise(uint64_t Value)

MachineInstrBundleIterator< const MachineInstr > const_iterator

MachineInstrBundleIterator< MachineInstr > iterator

Analysis pass which computes a MachineDominatorTree.

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

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.

Function & getFunction()

Return the LLVM function that this machine code represents.

BasicBlockListType::iterator iterator

void print(raw_ostream &OS, const SlotIndexes *=nullptr) const

print - Print out the MachineFunction in a format suitable for debugging to the specified stream.

nonconst_iterator getNonConstIterator() const

Representation of each machine instruction.

bool mayLoad(QueryType Type=AnyInBundle) const

Return true if this instruction could possibly read memory.

bool mayStore(QueryType Type=AnyInBundle) const

Return true if this instruction could possibly modify memory.

Analysis pass that exposes the MachineLoopInfo for a machine function.

MachineOperand class - Representation of each machine instruction operand.

MachinePassRegistry - Track the registration of machine passes.

MachineSchedRegistry provides a selection of available machine instruction schedulers.

static LLVM_ABI MachinePassRegistry< ScheduleDAGCtor > Registry

ScheduleDAGInstrs *(*)(MachineSchedContext *) ScheduleDAGCtor

LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)

Definition MachineScheduler.cpp:680

LLVM_ABI MachineSchedulerPass(const TargetMachine *TM)

Definition MachineScheduler.cpp:667

LLVM_ABI ~MachineSchedulerPass()

static LLVM_ABI PassRegistry * getPassRegistry()

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

void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs) override

Optionally override the per-region scheduling policy.

Definition MachineScheduler.cpp:4305

virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand)

Apply a set of heuristics to a new candidate for PostRA scheduling.

Definition MachineScheduler.cpp:4354

void schedNode(SUnit *SU, bool IsTopNode) override

Called after ScheduleDAGMI has scheduled an instruction and updated scheduled/remaining flags in the ...

Definition MachineScheduler.cpp:4570

SchedCandidate BotCand

Candidate last picked from Bot boundary.

void pickNodeFromQueue(SchedBoundary &Zone, SchedCandidate &Cand)

Definition MachineScheduler.cpp:4405

void initialize(ScheduleDAGMI *Dag) override

Initialize the strategy after building the DAG for a new region.

Definition MachineScheduler.cpp:4283

SchedCandidate TopCand

Candidate last picked from Top boundary.

SUnit * pickNodeBidirectional(bool &IsTopNode)

Pick the best candidate node from either the top or bottom queue.

Definition MachineScheduler.cpp:4421

void registerRoots() override

Notify this strategy that all roots have been released (including those that depend on EntrySU or Exi...

Definition MachineScheduler.cpp:4335

SUnit * pickNode(bool &IsTopNode) override

Pick the next node to schedule.

Definition MachineScheduler.cpp:4502

LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)

Definition MachineScheduler.cpp:727

LLVM_ABI PostMachineSchedulerPass(const TargetMachine *TM)

Definition MachineScheduler.cpp:673

LLVM_ABI ~PostMachineSchedulerPass()

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.

PreservedAnalyses & preserveSet()

Mark an analysis set as preserved.

Capture a change in pressure for a single pressure set.

unsigned getPSetOrMax() const

List of PressureChanges in order of increasing, unique PSetID.

LLVM_ABI void dump(const TargetRegisterInfo &TRI) const

LLVM_ABI void addPressureChange(VirtRegOrUnit VRegOrUnit, bool IsDec, const MachineRegisterInfo *MRI)

Add a change in pressure to the pressure diff of a given instruction.

void clear()

clear - Erase all elements from the queue.

Helpers for implementing custom MachineSchedStrategy classes.

ArrayRef< SUnit * > elements()

LLVM_ABI void dump() const

Definition MachineScheduler.cpp:899

std::vector< SUnit * >::iterator iterator

StringRef getName() const

Track the current register pressure at some position in the instruction stream, and remember the high...

LLVM_ABI void getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit)

Consider the pressure increase caused by traversing this instruction bottom-up.

LLVM_ABI void getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit)

Consider the pressure increase caused by traversing this instruction top-down.

LLVM_ABI void getUpwardPressureDelta(const MachineInstr *MI, PressureDiff &PDiff, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit) const

This is the fast version of querying register pressure that does not directly depend on current liven...

List of registers defined and used by a machine instruction.

LLVM_ABI void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI, bool TrackLaneMasks, bool IgnoreDead)

Analyze the given instruction MI and fill in the Uses, Defs and DeadDefs list based on the MachineOpe...

LLVM_ABI void adjustLaneLiveness(const LiveIntervals &LIS, const MachineRegisterInfo &MRI, SlotIndex Pos, MachineInstr *AddFlagsMI=nullptr)

Use liveness information to find out which uses/defs are partially undefined/dead and adjust the VReg...

LLVM_ABI void detectDeadDefs(const MachineInstr &MI, const LiveIntervals &LIS)

Use liveness information to find dead defs not marked with a dead flag and move them to the DeadDefs ...

RegisterPassParser class - Handle the addition of new machine passes.

Wrapper class representing virtual and physical registers.

constexpr bool isVirtual() const

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

LLVM_ABI void add(IntervalTy A, const unsigned CutOff=10)

Adds an interval [a, b) to the collection of the instance.

Definition MachineScheduler.cpp:4920

static IntervalTy getResourceIntervalBottom(unsigned C, unsigned AcquireAtCycle, unsigned ReleaseAtCycle)

These function return the interval used by a resource in bottom and top scheduling.

static LLVM_ABI bool intersects(IntervalTy A, IntervalTy B)

Checks whether intervals intersect.

Definition MachineScheduler.cpp:4947

std::pair< int64_t, int64_t > IntervalTy

Represents an interval of discrete integer values closed on the left and open on the right: [a,...

static IntervalTy getResourceIntervalTop(unsigned C, unsigned AcquireAtCycle, unsigned ReleaseAtCycle)

Kind getKind() const

Returns an enum value representing the kind of the dependence.

@ Anti

A register anti-dependence (aka WAR).

@ Data

Regular data dependence (aka true-dependence).

bool isWeak() const

Tests if this a weak dependence.

@ Cluster

Weak DAG edge linking a chain of clustered instrs.

@ Artificial

Arbitrary strong DAG edge (no real dependence).

@ Weak

Arbitrary weak DAG edge.

unsigned getLatency() const

Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...

bool isArtificial() const

Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...

bool isCtrl() const

Shorthand for getKind() != SDep::Data.

Returns the register associated with this edge.

bool isArtificialDep() const

bool isCtrlDep() const

Tests if this is not an SDep::Data dependence.

Scheduling unit. This is a node in the scheduling DAG.

bool isCall

Is a function call.

unsigned TopReadyCycle

Cycle relative to start when node is ready.

unsigned NodeNum

Entry # of node in the node vector.

bool isUnbuffered

Uses an unbuffered resource.

unsigned getHeight() const

Returns the height of this node, which is the length of the maximum path down to any node which has n...

unsigned short Latency

Node latency.

unsigned getDepth() const

Returns the depth of this node, which is the length of the maximum path up to any node which has no p...

bool isScheduled

True once scheduled.

unsigned ParentClusterIdx

The parent cluster id.

bool hasPhysRegDefs

Has physreg defs that are being used.

unsigned BotReadyCycle

Cycle relative to end when node is ready.

SmallVector< SDep, 4 > Succs

All sunit successors.

bool hasReservedResource

Uses a reserved resource.

bool isBottomReady() const

bool hasPhysRegUses

Has physreg uses.

SmallVector< SDep, 4 > Preds

All sunit predecessors.

MachineInstr * getInstr() const

Returns the representative MachineInstr for this SUnit.

Each Scheduling boundary is associated with ready queues.

LLVM_ABI unsigned getNextResourceCycleByInstance(unsigned InstanceIndex, unsigned ReleaseAtCycle, unsigned AcquireAtCycle)

Compute the next cycle at which the given processor resource unit can be scheduled.

Definition MachineScheduler.cpp:2593

LLVM_ABI void releasePending()

Release pending ready nodes in to the available queue.

Definition MachineScheduler.cpp:3106

unsigned getDependentLatency() const

bool isReservedGroup(unsigned PIdx) const

unsigned getScheduledLatency() const

Get the number of latency cycles "covered" by the scheduled instructions.

LLVM_ABI void incExecutedResources(unsigned PIdx, unsigned Count)

Definition MachineScheduler.cpp:2888

bool isResourceLimited() const

const TargetSchedModel * SchedModel

unsigned getExecutedCount() const

Get a scaled count for the minimum execution time of the scheduled micro-ops that are ready to execut...

LLVM_ABI unsigned getLatencyStallCycles(SUnit *SU)

Get the difference between the given SUnit's ready time and the current cycle.

Definition MachineScheduler.cpp:2581

LLVM_ABI unsigned findMaxLatency(ArrayRef< SUnit * > ReadySUs)

Definition MachineScheduler.cpp:2755

LLVM_ABI void dumpReservedCycles() const

Dump the state of the information that tracks resource usage.

Definition MachineScheduler.cpp:3182

LLVM_ABI unsigned getOtherResourceCount(unsigned &OtherCritIdx)

Definition MachineScheduler.cpp:2776

LLVM_ABI void bumpNode(SUnit *SU)

Move the boundary of scheduled code by one SUnit.

Definition MachineScheduler.cpp:2941

unsigned getCriticalCount() const

Get the scaled count of scheduled micro-ops and resources, including executed resources.

LLVM_ABI SUnit * pickOnlyChoice()

Call this before applying any other heuristics to the Available queue.

Definition MachineScheduler.cpp:3147

LLVM_ABI void releaseNode(SUnit *SU, unsigned ReadyCycle, bool InPQueue, unsigned Idx=0)

Release SU to make it ready.

Definition MachineScheduler.cpp:2802

LLVM_ABI unsigned countResource(const MCSchedClassDesc *SC, unsigned PIdx, unsigned Cycles, unsigned ReadyCycle, unsigned StartAtCycle)

Add the given processor resource to this scheduled zone.

Definition MachineScheduler.cpp:2904

LLVM_ABI ~SchedBoundary()

Definition MachineScheduler.cpp:2474

ScheduleHazardRecognizer * HazardRec

LLVM_ABI void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem)

Definition MachineScheduler.cpp:2547

unsigned getResourceCount(unsigned ResIdx) const

LLVM_ABI void bumpCycle(unsigned NextCycle)

Move the boundary of scheduled code by one cycle.

Definition MachineScheduler.cpp:2850

unsigned getCurrMOps() const

Micro-ops issued in the current cycle.

unsigned getCurrCycle() const

Number of cycles to issue the instructions scheduled in this zone.

LLVM_ABI void reset()

Definition MachineScheduler.cpp:2489

LLVM_ABI bool checkHazard(SUnit *SU)

Does this SU have a hazard within the current instruction group.

Definition MachineScheduler.cpp:2700

LLVM_ABI std::pair< unsigned, unsigned > getNextResourceCycle(const MCSchedClassDesc *SC, unsigned PIdx, unsigned ReleaseAtCycle, unsigned AcquireAtCycle)

Compute the next cycle at which the given processor resource can be scheduled.

Definition MachineScheduler.cpp:2619

LLVM_ABI void dumpScheduledState() const

Definition MachineScheduler.cpp:3208

LLVM_ABI void removeReady(SUnit *SU)

Remove SU from the ready set for this boundary.

Definition MachineScheduler.cpp:3135

unsigned getZoneCritResIdx() const

unsigned getUnscheduledLatency(SUnit *SU) const

Compute the values of each DAG node for various metrics during DFS.

unsigned getNumInstrs(const SUnit *SU) const

Get the number of instructions in the given subtree and its children.

unsigned getSubtreeID(const SUnit *SU) const

Get the ID of the subtree the given DAG node belongs to.

ILPValue getILP(const SUnit *SU) const

Get the ILP value for a DAG node.

unsigned getSubtreeLevel(unsigned SubtreeID) const

Get the connection level of a subtree.

A ScheduleDAG for scheduling lists of MachineInstr.

SmallVector< ClusterInfo > & getClusters()

Returns the array of the clusters.

virtual void finishBlock()

Cleans up after scheduling in the given block.

MachineBasicBlock::iterator end() const

Returns an iterator to the bottom of the current scheduling region.

std::string getDAGName() const override

Returns a label for the region of code covered by the DAG.

MachineBasicBlock * BB

The block in which to insert instructions.

MachineInstr * FirstDbgValue

virtual void startBlock(MachineBasicBlock *BB)

Prepares to perform scheduling in the given block.

MachineBasicBlock::iterator RegionEnd

The end of the range to be scheduled.

const MCSchedClassDesc * getSchedClass(SUnit *SU) const

Resolves and cache a resolved scheduling class for an SUnit.

DbgValueVector DbgValues

Remember instruction that precedes DBG_VALUE.

bool addEdge(SUnit *SuccSU, const SDep &PredDep)

Add a DAG edge to the given SU with the given predecessor dependence data.

DumpDirection

The direction that should be used to dump the scheduled Sequence.

bool TrackLaneMasks

Whether lane masks should get tracked.

void dumpNode(const SUnit &SU) const override

bool IsReachable(SUnit *SU, SUnit *TargetSU)

IsReachable - Checks if SU is reachable from TargetSU.

MachineBasicBlock::iterator begin() const

Returns an iterator to the top of the current scheduling region.

void buildSchedGraph(AAResults *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)

Builds SUnits for the current region.

SUnit * getSUnit(MachineInstr *MI) const

Returns an existing SUnit for this MI, or nullptr.

TargetSchedModel SchedModel

TargetSchedModel provides an interface to the machine model.

bool canAddEdge(SUnit *SuccSU, SUnit *PredSU)

True if an edge can be added from PredSU to SuccSU without creating a cycle.

MachineBasicBlock::iterator RegionBegin

The beginning of the range to be scheduled.

virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs)

Initialize the DAG and common scheduler state for a new scheduling region.

void dump() const override

void setDumpDirection(DumpDirection D)

ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules machine instructions while...

void scheduleMI(SUnit *SU, bool IsTopNode)

Move an instruction and update register pressure.

Definition MachineScheduler.cpp:1880

void schedule() override

Implement ScheduleDAGInstrs interface for scheduling a sequence of reorderable instructions.

Definition MachineScheduler.cpp:1689

VReg2SUnitMultiMap VRegUses

Maps vregs to the SUnits of their uses in the current scheduling region.

void computeDFSResult()

Compute a DFSResult after DAG building is complete, and before any queue comparisons.

Definition MachineScheduler.cpp:1773

PressureDiff & getPressureDiff(const SUnit *SU)

SchedDFSResult * DFSResult

Information about DAG subtrees.

void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs) override

Implement the ScheduleDAGInstrs interface for handling the next scheduling region.

Definition MachineScheduler.cpp:1453

void initQueues(ArrayRef< SUnit * > TopRoots, ArrayRef< SUnit * > BotRoots)

Release ExitSU predecessors and setup scheduler queues.

Definition MachineScheduler.cpp:1870

bool ShouldTrackLaneMasks

RegPressureTracker BotRPTracker

void buildDAGWithRegPressure()

Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking enabled.

Definition MachineScheduler.cpp:1750

std::vector< PressureChange > RegionCriticalPSets

List of pressure sets that exceed the target's pressure limit before scheduling, listed in increasing...

void updateScheduledPressure(const SUnit *SU, const std::vector< unsigned > &NewMaxPressure)

Definition MachineScheduler.cpp:1553

PressureDiffs SUPressureDiffs

unsigned computeCyclicCriticalPath()

Compute the cyclic critical path through the DAG.

Definition MachineScheduler.cpp:1809

void initRegPressure()

Definition MachineScheduler.cpp:1475

void updatePressureDiffs(ArrayRef< VRegMaskOrUnit > LiveUses)

Update the PressureDiff array for liveness after scheduling this instruction.

Definition MachineScheduler.cpp:1581

void collectVRegUses(SUnit &SU)

Definition MachineScheduler.cpp:1411

RegisterClassInfo * RegClassInfo

const SchedDFSResult * getDFSResult() const

Return a non-null DFS result if the scheduling strategy initialized it.

RegPressureTracker RPTracker

bool ShouldTrackPressure

~ScheduleDAGMILive() override

Definition MachineScheduler.cpp:1407

void dump() const override

Definition MachineScheduler.cpp:1656

BitVector & getScheduledTrees()

MachineBasicBlock::iterator LiveRegionEnd

RegPressureTracker TopRPTracker

ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...

void dumpSchedule() const

dump the scheduled Sequence.

Definition MachineScheduler.cpp:1380

std::unique_ptr< MachineSchedStrategy > SchedImpl

void startBlock(MachineBasicBlock *bb) override

Prepares to perform scheduling in the given block.

Definition MachineScheduler.cpp:986

void releasePred(SUnit *SU, SDep *PredEdge)

ReleasePred - Decrement the NumSuccsLeft count of a predecessor.

Definition MachineScheduler.cpp:955

void initQueues(ArrayRef< SUnit * > TopRoots, ArrayRef< SUnit * > BotRoots)

Release ExitSU predecessors and setup scheduler queues.

Definition MachineScheduler.cpp:1155

void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos)

Change the position of an instruction within the basic block and update live ranges and region bounda...

Definition MachineScheduler.cpp:1022

void releasePredecessors(SUnit *SU)

releasePredecessors - Call releasePred on each of SU's predecessors.

Definition MachineScheduler.cpp:981

void postProcessDAG()

Apply each ScheduleDAGMutation step in order.

Definition MachineScheduler.cpp:1130

void dumpScheduleTraceTopDown() const

Print execution trace of the schedule top-down or bottom-up.

Definition MachineScheduler.cpp:1216

bool checkSchedLimit()

Definition MachineScheduler.cpp:1040

void schedule() override

Implement ScheduleDAGInstrs interface for scheduling a sequence of reorderable instructions.

Definition MachineScheduler.cpp:1055

void findRootsAndBiasEdges(SmallVectorImpl< SUnit * > &TopRoots, SmallVectorImpl< SUnit * > &BotRoots)

Definition MachineScheduler.cpp:1136

MachineBasicBlock::iterator CurrentBottom

The bottom of the unscheduled zone.

virtual bool hasVRegLiveness() const

Return true if this DAG supports VReg liveness and RegPressure.

void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs) override

Implement the ScheduleDAGInstrs interface for handling the next scheduling region.

Definition MachineScheduler.cpp:1000

LiveIntervals * getLIS() const

void viewGraph(const Twine &Name, const Twine &Title) override

viewGraph - Pop up a ghostview window with the reachable parts of the DAG rendered using 'dot'.

Definition MachineScheduler.cpp:4868

void viewGraph() override

Out-of-line implementation with no arguments is handy for gdb.

Definition MachineScheduler.cpp:4878

void releaseSucc(SUnit *SU, SDep *SuccEdge)

ReleaseSucc - Decrement the NumPredsLeft count of a successor.

Definition MachineScheduler.cpp:920

void dumpScheduleTraceBottomUp() const

Definition MachineScheduler.cpp:1297

~ScheduleDAGMI() override

void finishBlock() override

Cleans up after scheduling in the given block.

Definition MachineScheduler.cpp:991

void updateQueues(SUnit *SU, bool IsTopNode)

Update scheduler DAG and queues after scheduling an instruction.

Definition MachineScheduler.cpp:1182

void placeDebugValues()

Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.

Definition MachineScheduler.cpp:1193

MachineBasicBlock::iterator CurrentTop

The top of the unscheduled zone.

void releaseSuccessors(SUnit *SU)

releaseSuccessors - Call releaseSucc on each of SU's successors.

Definition MachineScheduler.cpp:946

std::vector< std::unique_ptr< ScheduleDAGMutation > > Mutations

Ordered list of DAG postprocessing steps.

Mutate the DAG as a postpass after normal DAG building.

MachineRegisterInfo & MRI

Virtual/real register map.

std::vector< SUnit > SUnits

The scheduling units.

const TargetRegisterInfo * TRI

Target processor register info.

SUnit EntrySU

Special node for the region entry.

MachineFunction & MF

Machine function.

void dumpNodeAll(const SUnit &SU) const

SUnit ExitSU

Special node for the region exit.

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.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

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

void push_back(const T &Elt)

std::reverse_iterator< const_iterator > const_reverse_iterator

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

iterator_base< SparseMultiSet * > iterator

Information about stack frame layout on the target.

StackDirection getStackGrowthDirection() const

getStackGrowthDirection - Return the direction the stack grows

TargetInstrInfo - Interface to description of machine instruction set.

virtual bool shouldClusterMemOps(ArrayRef< const MachineOperand * > BaseOps1, int64_t Offset1, bool OffsetIsScalable1, ArrayRef< const MachineOperand * > BaseOps2, int64_t Offset2, bool OffsetIsScalable2, unsigned ClusterSize, unsigned NumBytes) const

Returns true if the two given memory operations should be scheduled adjacent.

virtual bool getMemOperandsWithOffsetWidth(const MachineInstr &MI, SmallVectorImpl< const MachineOperand * > &BaseOps, int64_t &Offset, bool &OffsetIsScalable, LocationSize &Width, const TargetRegisterInfo *TRI) const

Get zero or more base operands and the byte offset of an instruction that reads/writes memory.

virtual const TargetRegisterClass * getRegClassFor(MVT VT, bool isDivergent=false) const

Return the register class that should be used for the specified value type.

bool isTypeLegal(EVT VT) const

Return true if the target has native support for the specified value type.

This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...

Primary interface to the complete machine description for the target machine.

Target-Independent Code Generator Pass Configuration Options.

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

Provide an instruction scheduling machine model to CodeGen passes.

unsigned getMicroOpFactor() const

Multiply number of micro-ops by this factor to normalize it relative to other resources.

ProcResIter getWriteProcResEnd(const MCSchedClassDesc *SC) const

LLVM_ABI bool hasInstrSchedModel() const

Return true if this machine model includes an instruction-level scheduling model.

const MCWriteProcResEntry * ProcResIter

unsigned getResourceFactor(unsigned ResIdx) const

Multiply the number of units consumed for a resource by this factor to normalize it relative to other...

LLVM_ABI unsigned getNumMicroOps(const MachineInstr *MI, const MCSchedClassDesc *SC=nullptr) const

Return the number of issue slots required for this MI.

unsigned getNumProcResourceKinds() const

Get the number of kinds of resources for this target.

ProcResIter getWriteProcResBegin(const MCSchedClassDesc *SC) const

virtual void overridePostRASchedPolicy(MachineSchedPolicy &Policy, const SchedRegion &Region) const

Override generic post-ra scheduling policy within a region.

virtual void overrideSchedPolicy(MachineSchedPolicy &Policy, const SchedRegion &Region) const

Override generic scheduling policy within a region.

virtual bool enableMachineScheduler() const

True if the subtarget should run MachineScheduler after aggressive coalescing.

virtual bool enablePostRAMachineScheduler() const

True if the subtarget should run a machine scheduler after register allocation.

virtual const TargetFrameLowering * getFrameLowering() const

virtual const TargetInstrInfo * getInstrInfo() const

virtual const TargetLowering * getTargetLowering() const

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

VNInfo - Value Number Information.

SlotIndex def

The index of the defining instruction.

bool isPHIDef() const

Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...

Wrapper class representing a virtual register or register unit.

Base class for the machine scheduler classes.

Definition MachineScheduler.cpp:317

void scheduleRegions(ScheduleDAGInstrs &Scheduler, bool FixKillFlags)

Main driver for both MachineScheduler and PostMachineScheduler.

Definition MachineScheduler.cpp:815

Impl class for MachineScheduler.

Definition MachineScheduler.cpp:323

void setMFAM(MachineFunctionAnalysisManager *MFAM)

Definition MachineScheduler.cpp:340

void setLegacyPass(MachineFunctionPass *P)

Definition MachineScheduler.cpp:339

bool run(MachineFunction &MF, const TargetMachine &TM, const RequiredAnalyses &Analyses)

Definition MachineScheduler.cpp:550

MachineSchedulerImpl()=default

ScheduleDAGInstrs * createMachineScheduler()

Instantiate a ScheduleDAGInstrs that will be owned by the caller.

Definition MachineScheduler.cpp:535

Impl class for PostMachineScheduler.

Definition MachineScheduler.cpp:350

bool run(MachineFunction &Func, const TargetMachine &TM, const RequiredAnalyses &Analyses)

Definition MachineScheduler.cpp:598

void setMFAM(MachineFunctionAnalysisManager *MFAM)

Definition MachineScheduler.cpp:364

ScheduleDAGInstrs * createPostMachineScheduler()

Instantiate a ScheduleDAGInstrs for PostRA scheduling that will be owned by the caller.

Definition MachineScheduler.cpp:588

void setLegacyPass(MachineFunctionPass *P)

Definition MachineScheduler.cpp:363

PostMachineSchedulerImpl()=default

A raw_ostream that writes to an std::string.

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

Abstract Attribute helper functions.

unsigned ID

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

@ C

The default llvm calling convention, compatible with C.

LLVM_ABI StringRef getColorString(unsigned NodeNumber)

Get a color string for this node number.

void apply(Opt *O, const Mod &M, const Mods &... Ms)

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)

This is an optimization pass for GlobalISel generic memory operations.

ScheduleDAGMILive * createSchedLive(MachineSchedContext *C)

Create the standard converging machine scheduler.

bool operator<(int64_t V1, const APSInt &V2)

void stable_sort(R &&Range)

bool all_of(R &&range, UnaryPredicate P)

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

LLVM_ABI unsigned getWeakLeft(const SUnit *SU, bool isTop)

Definition MachineScheduler.cpp:3825

FormattedString right_justify(StringRef Str, unsigned Width)

right_justify - add spaces before string so total output is Width characters.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

Printable PrintLaneMask(LaneBitmask LaneMask)

Create Printable object to print LaneBitmasks on a raw_ostream.

AnalysisManager< MachineFunction > MachineFunctionAnalysisManager

LLVM_ABI char & MachineSchedulerID

MachineScheduler - This pass schedules machine instructions.

Definition MachineScheduler.cpp:409

LLVM_ABI char & PostMachineSchedulerID

PostMachineScheduler - This pass schedules machine instructions postRA.

Definition MachineScheduler.cpp:440

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.

LLVM_ABI bool tryPressure(const PressureChange &TryP, const PressureChange &CandP, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason, const TargetRegisterInfo *TRI, const MachineFunction &MF)

Definition MachineScheduler.cpp:3787

ScheduleDAGMI * createSchedPostRA(MachineSchedContext *C)

Create a generic scheduler with no vreg liveness or DAG mutation passes.

void sort(IteratorTy Start, IteratorTy End)

cl::opt< bool > ViewMISchedDAGs

LLVM_ABI std::unique_ptr< ScheduleDAGMutation > createStoreClusterDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, bool ReorderWhileClustering=false)

If ReorderWhileClustering is set to true, no attempt will be made to reduce reordering due to store c...

Definition MachineScheduler.cpp:2062

LLVM_ABI raw_ostream & dbgs()

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

FunctionAddr VTableAddr Count

LLVM_ABI cl::opt< bool > VerifyScheduling

bool is_sorted(R &&Range, Compare C)

Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...

LLVM_ABI bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary &Zone)

Definition MachineScheduler.cpp:3471

class LLVM_GSL_OWNER SmallVector

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

LLVM_ABI raw_fd_ostream & errs()

This returns a reference to a raw_ostream for standard error.

constexpr unsigned InvalidClusterId

FormattedString left_justify(StringRef Str, unsigned Width)

left_justify - append spaces after string so total output is Width characters.

bool isTheSameCluster(unsigned A, unsigned B)

Return whether the input cluster ID's are the same and valid.

LLVM_ABI std::unique_ptr< ScheduleDAGMutation > createLoadClusterDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, bool ReorderWhileClustering=false)

If ReorderWhileClustering is set to true, no attempt will be made to reduce reordering due to store c...

Definition MachineScheduler.cpp:2053

DWARFExpression::Operation Op

LLVM_ABI bool tryGreater(int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)

Definition MachineScheduler.cpp:3455

SmallPtrSet< SUnit *, 8 > ClusterInfo

Keep record of which SUnit are in the same cluster group.

void ViewGraph(const GraphType &G, const Twine &Name, bool ShortNames=false, const Twine &Title="", GraphProgram::Name Program=GraphProgram::DOT)

ViewGraph - Emit a dot graph, run 'dot', run gv on the postscript file, then cleanup.

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

LLVM_ABI void initializeMachineSchedulerLegacyPass(PassRegistry &)

LLVM_ABI void dumpRegSetPressure(ArrayRef< unsigned > SetPressure, const TargetRegisterInfo *TRI)

LLVM_ABI bool tryLess(int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)

Return true if this heuristic determines order.

Definition MachineScheduler.cpp:3439

LLVM_ABI std::unique_ptr< ScheduleDAGMutation > createCopyConstrainDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)

Definition MachineScheduler.cpp:2300

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 cl::opt< MISched::Direction > PreRADirection

LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

LLVM_ABI void initializePostMachineSchedulerLegacyPass(PassRegistry &)

LLVM_ABI int biasPhysReg(const SUnit *SU, bool isTop)

Minimize physical register live ranges.

Definition MachineScheduler.cpp:3836

cl::opt< bool > PrintDAGs

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

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

static std::string getNodeDescription(const SUnit *SU, const ScheduleDAG *G)

Definition MachineScheduler.cpp:4846

static std::string getEdgeAttributes(const SUnit *Node, SUnitIterator EI, const ScheduleDAG *Graph)

If you want to override the dot attributes printed for a particular edge, override this method.

Definition MachineScheduler.cpp:4824

static std::string getGraphName(const ScheduleDAG *G)

Definition MachineScheduler.cpp:4807

static std::string getNodeLabel(const SUnit *SU, const ScheduleDAG *G)

Definition MachineScheduler.cpp:4834

static bool isNodeHidden(const SUnit *Node, const ScheduleDAG *G)

Definition MachineScheduler.cpp:4815

DOTGraphTraits(bool isSimple=false)

Definition MachineScheduler.cpp:4805

static std::string getNodeAttributes(const SUnit *N, const ScheduleDAG *G)

Definition MachineScheduler.cpp:4850

static bool renderGraphFromBottomUp()

Definition MachineScheduler.cpp:4811

DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...

DefaultDOTGraphTraits(bool simple=false)

Policy for scheduling the next instruction in the candidate's zone.

Store the state used by GenericScheduler heuristics, required for the lifetime of one invocation of p...

void setBest(SchedCandidate &Best)

void reset(const CandPolicy &NewPolicy)

LLVM_ABI void initResourceDelta(const ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel)

Definition MachineScheduler.cpp:3238

SchedResourceDelta ResDelta

Status of an instruction's critical resource consumption.

unsigned DemandedResources

static constexpr LaneBitmask getNone()

Summarize the scheduling resources required for an instruction of a particular scheduling class.

Identify one of the processor resource kinds consumed by a particular scheduling class for the specif...

MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...

const MachineDominatorTree * MDT

RegisterClassInfo * RegClassInfo

const MachineLoopInfo * MLI

virtual ~MachineSchedContext()

Definition MachineScheduler.cpp:309

MachineSchedContext()

Definition MachineScheduler.cpp:305

PressureChange CriticalMax

PressureChange CurrentMax

RegisterPressure computed within a region of instructions delimited by TopPos and BottomPos.

A region of an MBB for scheduling.

Summarize the unscheduled region.

LLVM_ABI void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel)

Definition MachineScheduler.cpp:2525

SmallVector< unsigned, 16 > RemainingCounts

An individual mapping from virtual register number to SUnit.

AAResults & AA

Definition MachineScheduler.cpp:333

MachineLoopInfo & MLI

Definition MachineScheduler.cpp:331

MachineDominatorTree & MDT

Definition MachineScheduler.cpp:332

LiveIntervals & LIS

Definition MachineScheduler.cpp:334

Definition MachineScheduler.cpp:357

AAResults & AA

Definition MachineScheduler.cpp:359

MachineLoopInfo & MLI

Definition MachineScheduler.cpp:358