MachineTraceMetrics.cpp Source File (original) (raw)

31#include

32#include

33#include

34#include

36using namespace llvm;

38#define DEBUG_TYPE "machine-trace-metrics"

40AnalysisKey MachineTraceMetricsAnalysis::Key;

46}

53}

60 "Machine Trace Metrics", false, true)

72}

76 MF = &Func;

78 TII = ST.getInstrInfo();

79 TRI = ST.getRegisterInfo();

81 Loops = &LI;

82 SchedModel.init(&ST);

86}

89 MTM.init(MF, getAnalysis().getLI());

90 return false;

91}

96 MF = nullptr;

97 BlockInfo.clear();

98 for (auto &E : Ensembles)

99 E.reset();

100}

101

102

103

104

105

106

107

108

109

115 return FBI;

116

117

120

121

124

125 for (const auto &MI : *MBB) {

126 if (MI.isTransient())

127 continue;

129 if (MI.isCall())

131

132

134 continue;

136 if (!SC->isValid())

137 continue;

138

142 assert(PI->ProcResourceIdx < PRKinds && "Bad processor resource kind");

143 PRCycles[PI->ProcResourceIdx] += PI->ReleaseAtCycle;

144 }

145 }

147

148

149 unsigned PROffset = MBB->getNumber() * PRKinds;

150 for (unsigned K = 0; K != PRKinds; ++K)

151 ProcReleaseAtCycles[PROffset + K] =

153

154 return FBI;

155}

156

159 assert(BlockInfo[MBBNum].hasResources() &&

160 "getResources() must be called before getProcReleaseAtCycles()");

162 assert((MBBNum+1) * PRKinds <= ProcReleaseAtCycles.size());

163 return ArrayRef(ProcReleaseAtCycles.data() + MBBNum * PRKinds, PRKinds);

164}

165

166

167

168

169

171 : MTM(*ct) {

172 BlockInfo.resize(MTM.BlockInfo.size());

174 ProcResourceDepths.resize(MTM.BlockInfo.size() * PRKinds);

175 ProcResourceHeights.resize(MTM.BlockInfo.size() * PRKinds);

176}

177

178

180

183 return MTM.Loops->getLoopFor(MBB);

184}

185

186

187

188void MachineTraceMetrics::Ensemble::

191 unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds();

192 unsigned PROffset = MBB->getNumber() * PRKinds;

193

194

195 if (!TBI->Pred) {

198 std::fill(ProcResourceDepths.begin() + PROffset,

199 ProcResourceDepths.begin() + PROffset + PRKinds, 0);

200 return;

201 }

202

203

204

206 TraceBlockInfo *PredTBI = &BlockInfo[PredNum];

207 assert(PredTBI->hasValidDepth() && "Trace above has not been computed yet");

208 const FixedBlockInfo *PredFBI = MTM.getResources(TBI->Pred);

209 TBI->InstrDepth = PredTBI->InstrDepth + PredFBI->InstrCount;

210 TBI->Head = PredTBI->Head;

211

212

214 ArrayRef PredPRCycles = MTM.getProcReleaseAtCycles(PredNum);

215 for (unsigned K = 0; K != PRKinds; ++K)

216 ProcResourceDepths[PROffset + K] = PredPRDepths[K] + PredPRCycles[K];

217}

218

219

220

221void MachineTraceMetrics::Ensemble::

223 TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];

224 unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds();

225 unsigned PROffset = MBB->getNumber() * PRKinds;

226

227

228 TBI->InstrHeight = MTM.getResources(MBB)->InstrCount;

230

231

232 if (!TBI->Succ) {

234 llvm::copy(PRCycles, ProcResourceHeights.begin() + PROffset);

235 return;

236 }

237

238

239

240 unsigned SuccNum = TBI->Succ->getNumber();

241 TraceBlockInfo *SuccTBI = &BlockInfo[SuccNum];

242 assert(SuccTBI->hasValidHeight() && "Trace below has not been computed yet");

243 TBI->InstrHeight += SuccTBI->InstrHeight;

244 TBI->Tail = SuccTBI->Tail;

245

246

248 for (unsigned K = 0; K != PRKinds; ++K)

249 ProcResourceHeights[PROffset + K] = SuccPRHeights[K] + PRCycles[K];

250}

251

252

253

259}

260

261

262

268}

269

270

271

272

273

274

275

279 unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds();

280 assert((MBBNum+1) * PRKinds <= ProcResourceDepths.size());

281 return ArrayRef(ProcResourceDepths.data() + MBBNum * PRKinds, PRKinds);

282}

283

284

285

286

287

288

292 unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds();

293 assert((MBBNum+1) * PRKinds <= ProcResourceHeights.size());

294 return ArrayRef(ProcResourceHeights.data() + MBBNum * PRKinds, PRKinds);

295}

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

318 return From && From ->contains(To);

319}

320

321

322

323namespace {

324

326 const char *getName() const override { return "MinInstr"; }

329

330public:

333};

334

335

336

338 const char *getName() const override { return "Local"; }

340 return nullptr;

341 };

343 return nullptr;

344 };

345

346public:

349};

350}

351

352

356 return nullptr;

358

360 return nullptr;

361 unsigned CurCount = MTM.getResources(MBB)->InstrCount;

363 unsigned BestDepth = 0;

366 getDepthResources(Pred);

367

368 if (!PredTBI)

369 continue;

370

372 if (!Best || Depth < BestDepth) {

373 Best = Pred;

374 BestDepth = Depth;

375 }

376 }

377 return Best;

378}

379

380

384 return nullptr;

387 unsigned BestHeight = 0;

389

390 if (CurLoop && Succ == CurLoop->getHeader())

391 continue;

392

394 continue;

396 getHeightResources(Succ);

397

398 if (!SuccTBI)

399 continue;

400

402 if (!Best || Height < BestHeight) {

403 Best = Succ;

404 BestHeight = Height;

405 }

406 }

407 return Best;

408}

409

410

414 "Invalid trace strategy enum");

415 std::unique_ptrMachineTraceMetrics::Ensemble &E =

416 Ensembles[static_cast<size_t>(strategy)];

417 if (E)

418 return E.get();

419

420

421 switch (strategy) {

423 E = std::make_unique(MinInstrCountEnsemble(this));

424 break;

426 E = std::make_unique(LocalEnsemble(this));

427 break;

429 }

430 return E.get();

431}

432

435 << '\n');

437 for (auto &E : Ensembles)

438 if (E)

439 E->invalidate(MBB);

440}

441

445

446

448 return !PAC.preserved() &&

451}

452

454 if (!MF)

455 return;

456#ifndef NDEBUG

457 assert(BlockInfo.size() == MF->getNumBlockIDs() && "Outdated BlockInfo size");

458 for (auto &E : Ensembles)

459 if (E)

460 E->verify();

461#endif

462}

463

464

465

466

467

468

469

470

471

472namespace {

473

474struct LoopBounds {

478 bool Downward = false;

479

482};

483

484}

485

486

487

488namespace llvm {

489

490template<>

492 LoopBounds &LB;

493

494public:

496

498

501

504 return false;

505

507 if (const MachineLoop *FromLoop = LB.Loops->getLoopFor(*From)) {

508

509 if ((LB.Downward ? To : *From) == FromLoop->getHeader())

510 return false;

511

512 if (isExitingLoop(FromLoop, LB.Loops->getLoopFor(To)))

513 return false;

514 }

515 }

516

517

518 return LB.Visited.insert(To).second;

519 }

520};

521

522}

523

524

525void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) {

528

529 LoopBounds Bounds(BlockInfo, MTM.Loops);

530

531

532 Bounds.Downward = false;

533 Bounds.Visited.clear();

536 TraceBlockInfo &TBI = BlockInfo[I->getNumber()];

537

538 TBI.Pred = pickTracePred(I);

540 if (TBI.Pred)

542 else

543 dbgs() << "null\n";

544 });

545

546 computeDepthResources(I);

547 }

548

549

550 Bounds.Downward = true;

551 Bounds.Visited.clear();

554 TraceBlockInfo &TBI = BlockInfo[I->getNumber()];

555

556 TBI.Succ = pickTraceSucc(I);

558 if (TBI.Succ)

560 else

561 dbgs() << "null\n";

562 });

563

564 computeHeightResources(I);

565 }

566}

567

568

569void

573

574

578 do {

581 << getName() << " height.\n");

582

583

587 continue;

591 continue;

592 }

593

595 }

596 } while (!WorkList.empty());

597 }

598

599

603 do {

606 << getName() << " depth.\n");

607

608

612 continue;

616 continue;

617 }

618

620 }

621 } while (!WorkList.empty());

622 }

623

624

625

626

627

628

629 for (const auto &I : *BadMBB)

630 Cycles.erase(&I);

631}

632

634#ifndef NDEBUG

635 assert(BlockInfo.size() == MTM.MF->getNumBlockIDs() &&

636 "Outdated BlockInfo size");

637 for (unsigned Num = 0, e = BlockInfo.size(); Num != e; ++Num) {

643 "Trace is broken, depth should have been invalidated.");

646 }

651 "Trace is broken, height should have been invalidated.");

655 "Trace contains backedge");

656 }

657 }

658#endif

659}

660

661

662

663

664

665

666

667

668

669

670

671

672namespace {

673

674struct DataDep {

676 unsigned DefOp;

677 unsigned UseOp;

678

679 DataDep(const MachineInstr *DefMI, unsigned DefOp, unsigned UseOp)

680 : DefMI(DefMI), DefOp(DefOp), UseOp(UseOp) {}

681

682

684 : UseOp(UseOp) {

687 assert(DefMO && "Register does not have unique def");

690 }

691};

692

693}

694

695

696

700

701 if (UseMI.isDebugInstr())

702 return false;

703

704 bool HasPhysRegs = false;

706 if (!MO.isReg())

707 continue;

709 if (!Reg)

710 continue;

711 if (Reg.isPhysical()) {

712 HasPhysRegs = true;

713 continue;

714 }

715

716 if (MO.readsReg())

717 Deps.push_back(DataDep(MRI, Reg, MO.getOperandNo()));

718 }

719 return HasPhysRegs;

720}

721

722

723

724

729

730 if (!Pred)

731 return;

732 assert(UseMI.isPHI() && UseMI.getNumOperands() % 2 && "Bad PHI");

733 for (unsigned i = 1; i != UseMI.getNumOperands(); i += 2) {

734 if (UseMI.getOperand(i + 1).getMBB() == Pred) {

737 return;

738 }

739 }

740}

741

742

743

750

752 if (!MO.isReg() || !MO.getReg().isPhysical())

753 continue;

754 MCRegister Reg = MO.getReg().asMCReg();

755

756 if (MO.isDef()) {

757 if (MO.isDead())

759 else

760 LiveDefOps.push_back(MO.getOperandNo());

761 } else if (MO.isKill())

763

764 if (!MO.readsReg())

765 continue;

768 if (I == RegUnits.end())

769 continue;

770 Deps.push_back(DataDep(I->MI, I->Op, MO.getOperandNo()));

771 break;

772 }

773 }

774

775

776

779 RegUnits.erase(Unit);

780

781

782 for (unsigned DefOp : LiveDefOps) {

787 LRU.Op = DefOp;

788 }

789 }

790}

791

792

793

794

795

796

797

798

799

800

801

802

803unsigned MachineTraceMetrics::Ensemble::

804computeCrossBlockCriticalPath(const TraceBlockInfo &TBI) {

805 assert(TBI.HasValidInstrDepths && "Missing depth info");

806 assert(TBI.HasValidInstrHeights && "Missing height info");

807 unsigned MaxLen = 0;

808 for (const LiveInReg &LIR : TBI.LiveIns) {

809 if (!LIR.Reg.isVirtual())

810 continue;

812

814 if (!DefTBI.isUsefulDominator(TBI))

815 continue;

816 unsigned Len = LIR.Height + Cycles[DefMI].Depth;

817 MaxLen = std::max(MaxLen, Len);

818 }

819 return MaxLen;

820}

821

826

827 if (UseMI.isPHI())

831

832

833 unsigned Cycle = 0;

834 for (const DataDep &Dep : Deps) {

836 BlockInfo[Dep.DefMI->getParent()->getNumber()];

837

839 continue;

841 unsigned DepCycle = Cycles.lookup(Dep.DefMI).Depth;

842

843 if (!Dep.DefMI->isTransient())

844 DepCycle += MTM.SchedModel

845 .computeOperandLatency(Dep.DefMI, Dep.DefOp, &UseMI, Dep.UseOp);

847 }

848

851

853

856 } else {

858 }

859}

860

865}

866

871 for (; Start != End; Start++)

872 updateDepth(Start->getParent(), *Start, RegUnits);

873}

874

875

876

877void MachineTraceMetrics::Ensemble::

879

880

881

883 do {

887 break;

888 Stack.push_back(MBB);

890 } while (MBB);

891

892

893

894

895

897 RegUnits.setUniverse(MTM.TRI->getNumRegUnits());

898

899

900 while (!Stack.empty()) {

901 MBB = Stack.pop_back_val();

903 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];

904 TBI.HasValidInstrDepths = true;

905 TBI.CriticalPath = 0;

906

907

909 dbgs() << format("%7u Instructions\n", TBI.InstrDepth);

911 for (unsigned K = 0; K != PRDepths.size(); ++K)

912 if (PRDepths[K]) {

913 unsigned Factor = MTM.SchedModel.getResourceFactor(K);

914 dbgs() << format("%6uc @ ", MTM.getCycles(PRDepths[K]))

915 << MTM.SchedModel.getProcResource(K)->Name << " ("

916 << PRDepths[K]/Factor << " ops x" << Factor << ")\n";

917 }

918 });

919

920

921 if (TBI.HasValidInstrHeights)

922 TBI.CriticalPath = computeCrossBlockCriticalPath(TBI);

923

924 for (const auto &UseMI : *MBB) {

925 updateDepth(TBI, UseMI, RegUnits);

926 }

927 }

928}

929

930

931

932

939

941 if (!MO.isReg())

942 continue;

944 if (!Reg.isPhysical())

945 continue;

946 if (MO.readsReg())

947 ReadOps.push_back(MO.getOperandNo());

948 if (!MO.isDef())

949 continue;

950

951

952 for (MCRegUnit Unit : TRI->regunits(Reg.asMCReg())) {

954 if (I == RegUnits.end())

955 continue;

956 unsigned DepHeight = I->Cycle;

957 if (.isTransient()) {

958

959

961 I->MI, I->Op);

962 }

963 Height = std::max(Height, DepHeight);

964

966 }

967 }

968

969

970 for (unsigned Op : ReadOps) {

971 MCRegister Reg = MI.getOperand(Op).getReg().asMCReg();

974

975 if (LRU.Cycle <= Height && LRU.MI != &MI) {

976 LRU.Cycle = Height;

977 LRU.MI = &MI;

979 }

980 }

981 }

982

983 return Height;

984}

985

987

988

989

991 unsigned UseHeight, MIHeightMap &Heights,

994

995 if (!Dep.DefMI->isTransient())

997 Dep.UseOp);

998

999

1001 bool New;

1002 std::tie(I, New) = Heights.insert(std::make_pair(Dep.DefMI, UseHeight));

1003 if (New)

1004 return true;

1005

1006

1007 if (I->second < UseHeight)

1008 I->second = UseHeight;

1009 return false;

1010}

1011

1012

1013

1014

1015void MachineTraceMetrics::Ensemble::

1018 assert( Trace .empty() && "Trace should contain at least one block");

1022

1023

1025 if (MBB == DefMBB)

1026 return;

1027 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];

1028

1029 TBI.LiveIns.push_back(Reg);

1030 }

1031}

1032

1033

1034

1035

1036void MachineTraceMetrics::Ensemble::

1038

1039

1041 do {

1042 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];

1043 assert(TBI.hasValidHeight() && "Incomplete trace");

1044 if (TBI.HasValidInstrHeights)

1045 break;

1047 TBI.LiveIns.clear();

1048 MBB = TBI.Succ;

1049 } while (MBB);

1050

1051

1052

1054

1055

1056

1058 RegUnits.setUniverse(MTM.TRI->getNumRegUnits());

1059

1060

1061

1062

1063 if (MBB) {

1064 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];

1065 for (LiveInReg &LI : TBI.LiveIns) {

1066 if (LI.Reg.isVirtual()) {

1067

1068 unsigned &Height = Heights[MTM.MRI->getVRegDef(LI.Reg)];

1069 if (Height < LI.Height)

1070 Height = LI.Height;

1071 } else {

1072

1073

1074 RegUnits[LI.Reg].Cycle = LI.Height;

1075 }

1076 }

1077 }

1078

1079

1081 for (; Stack .empty(); Stack.pop_back()) {

1084 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];

1085 TBI.HasValidInstrHeights = true;

1086 TBI.CriticalPath = 0;

1087

1089 dbgs() << format("%7u Instructions\n", TBI.InstrHeight);

1091 for (unsigned K = 0; K != PRHeights.size(); ++K)

1092 if (PRHeights[K]) {

1093 unsigned Factor = MTM.SchedModel.getResourceFactor(K);

1094 dbgs() << format("%6uc @ ", MTM.getCycles(PRHeights[K]))

1095 << MTM.SchedModel.getProcResource(K)->Name << " ("

1096 << PRHeights[K]/Factor << " ops x" << Factor << ")\n";

1097 }

1098 });

1099

1100

1102

1103

1104

1105 if (!Succ)

1109

1110 if (Succ) {

1111 for (const auto &PHI : *Succ) {

1112 if ( PHI .isPHI())

1113 break;

1116 if (!Deps.empty()) {

1117

1118 unsigned Height = TBI.Succ ? Cycles.lookup(&PHI).Height : 0;

1121 MTM.TII))

1123 }

1124 }

1125 }

1126

1127

1129

1130

1131 unsigned Cycle = 0;

1133 if (HeightI != Heights.end()) {

1134 Cycle = HeightI->second;

1135

1136 Heights.erase(HeightI);

1137 }

1138

1139

1140

1142 bool HasPhysRegs = .isPHI() && getDataDeps(MI, Deps, MTM.MRI);

1143

1144

1145 if (HasPhysRegs)

1147 MTM.TII, MTM.TRI);

1148

1149

1150 for (const DataDep &Dep : Deps)

1152 addLiveIns(Dep.DefMI, Dep.DefOp, Stack);

1153

1154 InstrCycles &MICycles = Cycles[&MI];

1155 MICycles.Height = Cycle;

1156 if (!TBI.HasValidInstrDepths) {

1158 continue;

1159 }

1160

1161 TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Depth);

1163 }

1164

1165

1166

1168 for (LiveInReg &LIR : TBI.LiveIns) {

1172 }

1173

1174

1175 for (const LiveRegUnit &RU : RegUnits) {

1176 TBI.LiveIns.push_back(LiveInReg(RU.RegUnit, RU.Cycle));

1178 << RU.Cycle);

1179 }

1181

1182 if (!TBI.HasValidInstrDepths)

1183 continue;

1184

1185 TBI.CriticalPath = std::max(TBI.CriticalPath,

1186 computeCrossBlockCriticalPath(TBI));

1187 LLVM_DEBUG(dbgs() << "Critical path: " << TBI.CriticalPath << '\n');

1188 }

1189}

1190

1194

1196 computeTrace(MBB);

1198 computeInstrDepths(MBB);

1200 computeInstrHeights(MBB);

1201

1202 return Trace(*this, TBI);

1203}

1204

1205unsigned

1207 assert(getBlockNum() == unsigned(MI.getParent()->getNumber()) &&

1208 "MI must be in the trace center block");

1210 return getCriticalPath() - (Cyc.Depth + Cyc.Height);

1211}

1212

1213unsigned

1218 assert(Deps.size() == 1 && "PHI doesn't have MBB as a predecessor");

1219 DataDep &Dep = Deps.front();

1220 unsigned DepCycle = getInstrCycles(*Dep.DefMI).Depth;

1221

1222 if (!Dep.DefMI->isTransient())

1223 DepCycle += TE.MTM.SchedModel.computeOperandLatency(Dep.DefMI, Dep.DefOp,

1224 &PHI, Dep.UseOp);

1225 return DepCycle;

1226}

1227

1228

1230

1231

1232 unsigned PRMax = 0;

1233 ArrayRef PRDepths = TE.getProcResourceDepths(getBlockNum());

1234 if (Bottom) {

1235 ArrayRef PRCycles = TE.MTM.getProcReleaseAtCycles(getBlockNum());

1236 for (unsigned K = 0; K != PRDepths.size(); ++K)

1237 PRMax = std::max(PRMax, PRDepths[K] + PRCycles[K]);

1238 } else {

1239 for (unsigned PRD : PRDepths)

1240 PRMax = std::max(PRMax, PRD);

1241 }

1242

1243 PRMax = TE.MTM.getCycles(PRMax);

1244

1245

1246 unsigned Instrs = TBI.InstrDepth;

1247

1248 if (Bottom)

1249 Instrs += TE.MTM.BlockInfo[getBlockNum()].InstrCount;

1250 if (unsigned IW = TE.MTM.SchedModel.getIssueWidth())

1251 Instrs /= IW;

1252

1253 return std::max(Instrs, PRMax);

1254}

1255

1260

1261 ArrayRef PRDepths = TE.getProcResourceDepths(getBlockNum());

1262 ArrayRef PRHeights = TE.getProcResourceHeights(getBlockNum());

1263 unsigned PRMax = 0;

1264

1265

1267 unsigned ResourceIdx)

1268 ->unsigned {

1269 unsigned Cycles = 0;

1271 if (!SC->isValid())

1272 continue;

1274 PI = TE.MTM.SchedModel.getWriteProcResBegin(SC),

1275 PE = TE.MTM.SchedModel.getWriteProcResEnd(SC);

1276 PI != PE; ++PI) {

1277 if (PI->ProcResourceIdx != ResourceIdx)

1278 continue;

1279 Cycles += (PI->ReleaseAtCycle *

1280 TE.MTM.SchedModel.getResourceFactor(ResourceIdx));

1281 }

1282 }

1283 return Cycles;

1284 };

1285

1286 for (unsigned K = 0; K != PRDepths.size(); ++K) {

1287 unsigned PRCycles = PRDepths[K] + PRHeights[K];

1289 PRCycles += TE.MTM.getProcReleaseAtCycles(MBB->getNumber())[K];

1290 PRCycles += extraCycles(ExtraInstrs, K);

1291 PRCycles -= extraCycles(RemoveInstrs, K);

1292 PRMax = std::max(PRMax, PRCycles);

1293 }

1294

1295 PRMax = TE.MTM.getCycles(PRMax);

1296

1297

1298 unsigned Instrs = TBI.InstrDepth + TBI.InstrHeight;

1299

1301 Instrs += TE.MTM.getResources(MBB)->InstrCount;

1302 Instrs += ExtraInstrs.size();

1303 Instrs -= RemoveInstrs.size();

1304 if (unsigned IW = TE.MTM.SchedModel.getIssueWidth())

1305 Instrs /= IW;

1306

1307 return std::max(Instrs, PRMax);

1308}

1309

1312 if (DefMI.getParent() == UseMI.getParent())

1313 return true;

1314

1315 const TraceBlockInfo &DepTBI = TE.BlockInfo[DefMI.getParent()->getNumber()];

1316 const TraceBlockInfo &TBI = TE.BlockInfo[UseMI.getParent()->getNumber()];

1317

1319}

1320

1322 OS << getName() << " ensemble:\n";

1323 for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) {

1324 OS << " %bb." << i << '\t';

1325 BlockInfo[i].print(OS);

1326 OS << '\n';

1327 }

1328}

1329

1331 if (hasValidDepth()) {

1332 OS << "depth=" << InstrDepth;

1333 if (Pred)

1335 else

1336 OS << " pred=null";

1337 OS << " head=%bb." << Head;

1338 if (HasValidInstrDepths)

1339 OS << " +instrs";

1340 } else

1341 OS << "depth invalid";

1342 OS << ", ";

1343 if (hasValidHeight()) {

1344 OS << "height=" << InstrHeight;

1345 if (Succ)

1347 else

1348 OS << " succ=null";

1349 OS << " tail=%bb." << Tail;

1350 if (HasValidInstrHeights)

1351 OS << " +instrs";

1352 } else

1353 OS << "height invalid";

1354 if (HasValidInstrDepths && HasValidInstrHeights)

1355 OS << ", crit=" << CriticalPath;

1356}

1357

1359 unsigned MBBNum = &TBI - &TE.BlockInfo[0];

1360

1361 OS << TE.getName() << " trace %bb." << TBI.Head << " --> %bb." << MBBNum

1362 << " --> %bb." << TBI.Tail << ':';

1363 if (TBI.hasValidHeight() && TBI.hasValidDepth())

1364 OS << ' ' << getInstrCount() << " instrs.";

1365 if (TBI.HasValidInstrDepths && TBI.HasValidInstrHeights)

1366 OS << ' ' << TBI.CriticalPath << " cycles.";

1367

1369 OS << "\n%bb." << MBBNum;

1370 while (Block->hasValidDepth() && Block->Pred) {

1371 unsigned Num = Block->Pred->getNumber();

1373 Block = &TE.BlockInfo[Num];

1374 }

1375

1377 OS << "\n ";

1378 while (Block->hasValidHeight() && Block->Succ) {

1379 unsigned Num = Block->Succ->getNumber();

1381 Block = &TE.BlockInfo[Num];

1382 }

1383 OS << '\n';

1384}

unsigned const MachineRegisterInfo * MRI

MachineInstrBuilder & UseMI

MachineInstrBuilder MachineInstrBuilder & DefMI

bbsections Prepares for basic block by splitting functions into clusters of basic blocks

BlockVerifier::State From

COFF::MachineTypes Machine

static unsigned InstrCount

This file defines the DenseMap class.

DenseMap< Block *, BlockRelaxAux > Blocks

unsigned const TargetRegisterInfo * TRI

static bool pushDepHeight(const DataDep &Dep, const MachineInstr &UseMI, unsigned UseHeight, MIHeightMap &Heights, const TargetSchedModel &SchedModel, const TargetInstrInfo *TII)

static void getPHIDeps(const MachineInstr &UseMI, SmallVectorImpl< DataDep > &Deps, const MachineBasicBlock *Pred, const MachineRegisterInfo *MRI)

static bool getDataDeps(const MachineInstr &UseMI, SmallVectorImpl< DataDep > &Deps, const MachineRegisterInfo *MRI)

static void updatePhysDepsDownwards(const MachineInstr *UseMI, SmallVectorImpl< DataDep > &Deps, SparseSet< LiveRegUnit > &RegUnits, const TargetRegisterInfo *TRI)

static unsigned updatePhysDepsUpwards(const MachineInstr &MI, unsigned Height, SparseSet< LiveRegUnit > &RegUnits, const TargetSchedModel &SchedModel, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)

static bool isExitingLoop(const MachineLoop *From, const MachineLoop *To)

#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 builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.

static StringRef getName(Value *V)

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

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

This file defines the SparseSet class derived from the version described in Briggs,...

This templated class represents "all analyses that operate over " (e....

API to communicate dependencies between analyses during invalidation.

A container for analyses that lazily runs them and caches their results.

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

void setPreservesAll()

Set by analyses that do not transform their input at all.

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

size_t size() const

size - Get the array size.

Represents analyses that only rely on functions' control flow.

This class represents an Operation in the Expression.

ValueT lookup(const_arg_type_t< KeyT > Val) const

lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...

iterator find(const_arg_type_t< KeyT > Val)

bool erase(const KeyT &Val)

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

A possibly irreducible generalization of a Loop.

BlockT * getHeader() const

Represents a single loop in the control flow graph.

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

int getNumber() const

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

bool isPredecessor(const MachineBasicBlock *MBB) const

Return true if the specified MBB is a predecessor of this block.

iterator_range< succ_iterator > successors()

bool isSuccessor(const MachineBasicBlock *MBB) const

Return true if the specified MBB is a successor of this block.

iterator_range< pred_iterator > predecessors()

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.

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

unsigned getNumBlockIDs() const

getNumBlockIDs - Return the number of MBB ID's allocated.

Get the register for the operand index.

Representation of each machine instruction.

const MachineBasicBlock * getParent() const

iterator_range< mop_iterator > operands()

const MachineOperand & getOperand(unsigned i) const

Analysis pass that exposes the MachineLoopInfo for a machine function.

MachineOperand class - Representation of each machine instruction operand.

unsigned getOperandNo() const

Returns the index of this operand in the instruction that it belongs to.

MachineInstr * getParent()

getParent - Return the instruction that this operand belongs to.

getReg - Returns the register number.

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

Result run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)

MachineTraceMetrics Result

void getAnalysisUsage(AnalysisUsage &) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

bool runOnMachineFunction(MachineFunction &) override

runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...

A trace ensemble is a collection of traces selected using the same strategy, for example 'minimum res...

void invalidate(const MachineBasicBlock *MBB)

Invalidate traces through BadMBB.

ArrayRef< unsigned > getProcResourceHeights(unsigned MBBNum) const

Get an array of processor resource heights for MBB.

void updateDepth(TraceBlockInfo &TBI, const MachineInstr &, SparseSet< LiveRegUnit > &RegUnits)

Updates the depth of an machine instruction, given RegUnits.

const MachineLoop * getLoopFor(const MachineBasicBlock *) const

const TraceBlockInfo * getHeightResources(const MachineBasicBlock *) const

void updateDepths(MachineBasicBlock::iterator Start, MachineBasicBlock::iterator End, SparseSet< LiveRegUnit > &RegUnits)

Updates the depth of the instructions from Start to End.

const TraceBlockInfo * getDepthResources(const MachineBasicBlock *) const

ArrayRef< unsigned > getProcResourceDepths(unsigned MBBNum) const

Get an array of processor resource depths for MBB.

Ensemble(MachineTraceMetrics *)

MachineTraceMetrics & MTM

void print(raw_ostream &) const

Trace getTrace(const MachineBasicBlock *MBB)

Get the trace that passes through MBB.

A trace represents a plausible sequence of executed basic blocks that passes through the current basi...

unsigned getResourceLength(ArrayRef< const MachineBasicBlock * > Extrablocks={}, ArrayRef< const MCSchedClassDesc * > ExtraInstrs={}, ArrayRef< const MCSchedClassDesc * > RemoveInstrs={}) const

Return the resource length of the trace.

unsigned getInstrSlack(const MachineInstr &MI) const

Return the slack of MI.

bool isDepInTrace(const MachineInstr &DefMI, const MachineInstr &UseMI) const

A dependence is useful if the basic block of the defining instruction is part of the trace of the use...

unsigned getPHIDepth(const MachineInstr &PHI) const

Return the Depth of a PHI instruction in a trace center block successor.

void print(raw_ostream &) const

unsigned getResourceDepth(bool Bottom) const

Return the resource depth of the top/bottom of the trace center block.

Ensemble * getEnsemble(MachineTraceStrategy)

Get the trace ensemble representing the given trace selection strategy.

void verifyAnalysis() const

void invalidate(const MachineBasicBlock *MBB)

Invalidate cached information about MBB.

const FixedBlockInfo * getResources(const MachineBasicBlock *)

Get the fixed resource information about MBB. Compute it on demand.

ArrayRef< unsigned > getProcReleaseAtCycles(unsigned MBBNum) const

Get the scaled number of cycles used per processor resource in MBB.

void init(MachineFunction &Func, const MachineLoopInfo &LI)

MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...

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.

PreservedAnalysisChecker getChecker() const

Build a checker for this PreservedAnalyses and the specified analysis type.

Wrapper class representing virtual and physical registers.

MCRegister asMCReg() const

Utility to check-convert this value to a MCRegister.

static constexpr bool isVirtualRegister(unsigned Reg)

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

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

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

void push_back(const T &Elt)

pointer data()

Return a pointer to the vector's buffer, even if empty().

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

SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.

iterator erase(iterator I)

erase - Erases an existing element identified by a valid iterator.

typename DenseT::iterator iterator

const_iterator end() const

void setUniverse(unsigned U)

setUniverse - Set the universe size which determines the largest key the set can hold.

iterator find(const KeyT &Key)

find - Find an element by its key.

TargetInstrInfo - Interface to description of machine instruction set.

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

Provide an instruction scheduling machine model to CodeGen passes.

ProcResIter getWriteProcResEnd(const MCSchedClassDesc *SC) const

bool hasInstrSchedModel() const

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

unsigned getResourceFactor(unsigned ResIdx) const

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

const MCSchedClassDesc * resolveSchedClass(const MachineInstr *MI) const

Return the MCSchedClassDesc for this instruction.

void init(const TargetSubtargetInfo *TSInfo)

Initialize the machine model for instruction scheduling.

unsigned computeOperandLatency(const MachineInstr *DefMI, unsigned DefOperIdx, const MachineInstr *UseMI, unsigned UseOperIdx) const

Compute operand latency based on the available machine model.

unsigned getNumProcResourceKinds() const

Get the number of kinds of resources for this target.

ProcResIter getWriteProcResBegin(const MCSchedClassDesc *SC) const

TargetSubtargetInfo - Generic base class for all target subtargets.

bool insertEdge(std::optional< const MachineBasicBlock * > From, const MachineBasicBlock *To)

void finishPostorder(const MachineBasicBlock *)

po_iterator_storage(LoopBounds &lb)

Default po_iterator_storage implementation with an internal set object.

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

#define llvm_unreachable(msg)

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

@ Tail

Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...

Reg

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

This is an optimization pass for GlobalISel generic memory operations.

MachineTraceStrategy

Strategies for selecting traces.

@ TS_MinInstrCount

Select the trace through a block that has the fewest instructions.

@ TS_Local

Select the trace that contains only the current basic block.

iterator_range< po_ext_iterator< T, SetType > > post_order_ext(const T &G, SetType &S)

iterator_range< ipo_ext_iterator< T, SetType > > inverse_post_order_ext(const T &G, SetType &S)

Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)

Create Printable object to print register units on a raw_ostream.

auto reverse(ContainerTy &&C)

raw_ostream & dbgs()

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

format_object< Ts... > format(const char *Fmt, const Ts &... Vals)

These are helper functions used to produce formatted output.

char & MachineTraceMetricsID

MachineTraceMetrics - This pass computes critical path and CPU resource usage in an ensemble of trace...

DWARFExpression::Operation Op

OutputIt copy(R &&Range, OutputIt Out)

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

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

Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)

Adds registers contained in LiveRegs to the block live-in list of MBB.

A special type used by analysis passes to provide an address that identifies that particular analysis...

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

PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)

Per-basic block information that doesn't depend on the trace through the block.

bool hasResources() const

Returns true when resource information for this block has been computed.

unsigned InstrCount

The number of non-trivial instructions in the block.

bool HasCalls

True when the block contains calls.

InstrCycles represents the cycle height and depth of an instruction in a trace.

unsigned Height

Minimum number of cycles from this instruction is issued to the of the trace, as determined by data d...

unsigned Depth

Earliest issue cycle as determined by data dependencies and instruction latencies from the beginning ...

Per-basic block information that relates to a specific trace through the block.

unsigned InstrDepth

Accumulated number of instructions in the trace above this block.

void invalidateDepth()

Invalidate depth resources when some block above this one has changed.

const MachineBasicBlock * Pred

Trace predecessor, or NULL for the first block in the trace.

unsigned InstrHeight

Accumulated number of instructions in the trace below this block.

const MachineBasicBlock * Succ

Trace successor, or NULL for the last block in the trace.

bool hasValidDepth() const

Returns true if the depth resources have been computed from the trace above this block.

bool isUsefulDominator(const TraceBlockInfo &TBI) const

Assuming that this is a dominator of TBI, determine if it contains useful instruction depths.

void invalidateHeight()

Invalidate height resources when a block below this one has changed.

unsigned CriticalPath

Critical path length.

void print(raw_ostream &) const

unsigned Head

The block number of the head of the trace. (When hasValidDepth()).

bool HasValidInstrDepths

Instruction depths have been computed. This implies hasValidDepth().

bool hasValidHeight() const

Returns true if the height resources have been computed from the trace below this block.

bool HasValidInstrHeights

Instruction heights have been computed. This implies hasValidHeight().