MachineTraceMetrics.cpp Source File (original) (raw)

31#include

32#include

33#include

35using namespace llvm;

37#define DEBUG_TYPE "machine-trace-metrics"

39AnalysisKey MachineTraceMetricsAnalysis::Key;

59 "Machine Trace Metrics", false, true)

75 MF = &Func;

77 TII = ST.getInstrInfo();

78 TRI = ST.getRegisterInfo();

79 MRI = &MF->getRegInfo();

80 Loops = &LI;

81 SchedModel.init(&ST);

82 BlockInfo.resize(MF->getNumBlockIDs());

83 ProcReleaseAtCycles.resize(MF->getNumBlockIDs() *

84 SchedModel.getNumProcResourceKinds());

85}

95 MF = nullptr;

96 BlockInfo.clear();

97 for (auto &E : Ensembles)

98 E.reset();

99}

100

101

102

103

104

105

106

107

108

114 return FBI;

115

116

119

120

121 unsigned PRKinds = SchedModel.getNumProcResourceKinds();

123

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

125 if (MI.isTransient())

126 continue;

128 if (MI.isCall())

130

131

132 if (!SchedModel.hasInstrSchedModel())

133 continue;

136 continue;

137

139 PI = SchedModel.getWriteProcResBegin(SC),

140 PE = SchedModel.getWriteProcResEnd(SC); PI != PE; ++PI) {

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

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

143 }

144 }

146

147

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

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

150 ProcReleaseAtCycles[PROffset + K] =

151 PRCycles[K] * SchedModel.getResourceFactor(K);

152

153 return FBI;

154}

155

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

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

160 unsigned PRKinds = SchedModel.getNumProcResourceKinds();

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

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

163}

164

165

166

167

168

170 : MTM(*ct) {

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

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

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

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

175}

176

177

179

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

183}

184

185

186

187void MachineTraceMetrics::Ensemble::

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

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

192

193

194 if (!TBI->Pred) {

196 TBI->Head = MBB->getNumber();

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

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

199 return;

200 }

201

202

203

205 TraceBlockInfo *PredTBI = &BlockInfo[PredNum];

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

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

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

209 TBI->Head = PredTBI->Head;

210

211

213 ArrayRef PredPRCycles = MTM.getProcReleaseAtCycles(PredNum);

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

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

216}

217

218

219

220void MachineTraceMetrics::Ensemble::

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

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

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

225

226

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

229

230

231 if (!TBI->Succ) {

232 TBI->Tail = MBB->getNumber();

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

234 return;

235 }

236

237

238

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

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

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

243 TBI->Tail = SuccTBI->Tail;

244

245

246 ArrayRef SuccPRHeights = getProcResourceHeights(SuccNum);

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

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

249}

250

251

252

253const MachineTraceMetrics::TraceBlockInfo*

259

260

261

268

269

270

271

272

273

274

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

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

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

281}

282

283

284

285

286

287

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

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

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

294}

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

317 return From && !From->contains(To);

318}

319

320

321

322namespace {

323

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

326 const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) override;

327 const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) override;

328

329public:

330 MinInstrCountEnsemble(MachineTraceMetrics *mtm)

331 : MachineTraceMetrics::Ensemble(mtm) {}

332};

333

334

335

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

338 const MachineBasicBlock *pickTracePred(const MachineBasicBlock *) override {

339 return nullptr;

340 };

341 const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock *) override {

342 return nullptr;

343 };

344

345public:

346 LocalEnsemble(MachineTraceMetrics *MTM)

347 : MachineTraceMetrics::Ensemble(MTM) {}

348};

349}

350

351

352const MachineBasicBlock*

353MinInstrCountEnsemble::pickTracePred(const MachineBasicBlock *MBB) {

355 return nullptr;

356 const MachineLoop *CurLoop = getLoopFor(MBB);

357

359 return nullptr;

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

361 const MachineBasicBlock *Best = nullptr;

362 unsigned BestDepth = 0;

363 for (const MachineBasicBlock *Pred : MBB->predecessors()) {

364 const MachineTraceMetrics::TraceBlockInfo *PredTBI =

365 getDepthResources(Pred);

366

367 if (!PredTBI)

368 continue;

369

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

372 Best = Pred;

373 BestDepth = Depth;

374 }

375 }

376 return Best;

377}

378

379

380const MachineBasicBlock*

381MinInstrCountEnsemble::pickTraceSucc(const MachineBasicBlock *MBB) {

383 return nullptr;

384 const MachineLoop *CurLoop = getLoopFor(MBB);

385 const MachineBasicBlock *Best = nullptr;

386 unsigned BestHeight = 0;

387 for (const MachineBasicBlock *Succ : MBB->successors()) {

388

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

390 continue;

391

393 continue;

394 const MachineTraceMetrics::TraceBlockInfo *SuccTBI =

395 getHeightResources(Succ);

396

397 if (!SuccTBI)

398 continue;

399

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

402 Best = Succ;

403 BestHeight = Height;

404 }

405 }

406 return Best;

407}

408

409

413 "Invalid trace strategy enum");

414 std::unique_ptrMachineTraceMetrics::Ensemble &E =

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

416 if (E)

417 return E.get();

418

419

420 switch (strategy) {

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

423 break;

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

426 break;

428 }

429 return E.get();

430}

431

434 << '\n');

435 BlockInfo[MBB->getNumber()].invalidate();

436 for (auto &E : Ensembles)

437 if (E)

438 E->invalidate(MBB);

439}

440

443 MachineFunctionAnalysisManager::Invalidator &) {

444

445

447 return !PAC.preserved() &&

450}

451

453 if (!MF)

454 return;

455#ifndef NDEBUG

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

457 for (auto &E : Ensembles)

458 if (E)

459 E->verify();

460#endif

461}

462

463

464

465

466

467

468

469

470

471namespace {

472

473struct LoopBounds {

477 bool Downward = false;

478

481};

482

483}

484

485

486

488 LoopBounds &LB;

489

490public:

492

494

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

497

500 return false;

501

502 if (From) {

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

504

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

506 return false;

507

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

509 return false;

510 }

511 }

512

513

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

515 }

516};

517

518

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

522

523 LoopBounds Bounds(BlockInfo, MTM.Loops);

524

525

526 Bounds.Downward = false;

527 Bounds.Visited.clear();

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

531

532 TBI.Pred = pickTracePred(I);

534 if (TBI.Pred)

536 else

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

538 });

539

540 computeDepthResources(I);

541 }

542

543

544 Bounds.Downward = true;

545 Bounds.Visited.clear();

549

550 TBI.Succ = pickTraceSucc(I);

552 if (TBI.Succ)

554 else

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

556 });

557

558 computeHeightResources(I);

559 }

560}

561

562

563void

567

568

572 do {

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

576

577

581 continue;

585 continue;

586 }

587

589 }

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

591 }

592

593

597 do {

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

601

602

606 continue;

610 continue;

611 }

612

614 }

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

616 }

617

618

619

620

621

622

623 for (const auto &I : *BadMBB)

624 Cycles.erase(&I);

625}

626

628#ifndef NDEBUG

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

630 "Outdated BlockInfo size");

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

635 assert(MBB->isPredecessor(TBI.Pred) && "CFG doesn't match trace");

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

640 }

643 assert(MBB->isSuccessor(TBI.Succ) && "CFG doesn't match trace");

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

649 "Trace contains backedge");

650 }

651 }

652#endif

653}

654

655

656

657

658

659

660

661

662

663

664

665

666namespace {

667

668struct DataDep {

670 unsigned DefOp;

671 unsigned UseOp;

672

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

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

675

676

678 : UseOp(UseOp) {

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

684 }

685};

686

687}

688

689

690

694

695 if (UseMI.isDebugInstr())

696 return false;

697

698 bool HasPhysRegs = false;

700 if (!MO.isReg())

701 continue;

703 if ( Reg )

704 continue;

705 if (Reg.isPhysical()) {

706 HasPhysRegs = true;

707 continue;

708 }

709

710 if (MO.readsReg())

712 }

713 return HasPhysRegs;

714}

715

716

717

718

723

724 if (!Pred)

725 return;

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

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

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

731 return;

732 }

733 }

734}

735

736

737

744

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

747 continue;

749

750 if (MO.isDef()) {

751 if (MO.isDead())

753 else

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

755 } else if (MO.isKill())

757

758 if (!MO.readsReg())

759 continue;

760 for (MCRegUnit Unit : TRI->regunits(Reg)) {

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

763 continue;

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

765 break;

766 }

767 }

768

769

770

772 for (MCRegUnit Unit : TRI->regunits(Kill))

773 RegUnits.erase(Unit);

774

775

776 for (unsigned DefOp : LiveDefOps) {

777 for (MCRegUnit Unit :

778 TRI->regunits(UseMI->getOperand(DefOp).getReg().asMCReg())) {

781 LRU.Op = DefOp;

782 }

783 }

784}

785

786

787

788

789

790

791

792

793

794

795

796

797unsigned MachineTraceMetrics::Ensemble::

798computeCrossBlockCriticalPath(const TraceBlockInfo &TBI) {

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

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

801 unsigned MaxLen = 0;

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

803 if (!LIR.VRegOrUnit.isVirtualReg())

804 continue;

805 const MachineInstr *DefMI =

806 MTM.MRI->getVRegDef(LIR.VRegOrUnit.asVirtualReg());

807

809 if (!DefTBI.isUsefulDominator(TBI))

810 continue;

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

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

813 }

814 return MaxLen;

815}

816

821

822 if (UseMI.isPHI())

826

827

828 unsigned Cycle = 0;

829 for (const DataDep &Dep : Deps) {

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

832

834 continue;

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

837

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

839 DepCycle += MTM.SchedModel

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

842 }

843

846

848

851 } else {

853 }

854}

855

861

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

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

867}

868

869

870

871void MachineTraceMetrics::Ensemble::

873

874

875

877 do {

881 break;

882 Stack.push_back(MBB);

884 } while (MBB);

885

886

887

888

889

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

892

893

894 while (!Stack.empty()) {

895 MBB = Stack.pop_back_val();

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

899 TBI.CriticalPath = 0;

900

901

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

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

906 if (PRDepths[K]) {

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

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

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

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

911 }

912 });

913

914

915 if (TBI.HasValidInstrHeights)

916 TBI.CriticalPath = computeCrossBlockCriticalPath(TBI);

917

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

919 updateDepth(TBI, UseMI, RegUnits);

920 }

921 }

922}

923

924

925

926

933

935 if (!MO.isReg())

936 continue;

938 if ( Reg .isPhysical())

939 continue;

940 if (MO.readsReg())

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

942 if (!MO.isDef())

943 continue;

944

945

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

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

949 continue;

950 unsigned DepHeight = I->Cycle;

951 if (.isTransient()) {

952

953

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

956 }

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

958

960 }

961 }

962

963

964 for (unsigned Op : ReadOps) {

966 for (MCRegUnit Unit : TRI->regunits(Reg)) {

968

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

970 LRU.Cycle = Height;

971 LRU.MI = &MI;

973 }

974 }

975 }

976

977 return Height;

978}

979

981

982

983

985 unsigned UseHeight, MIHeightMap &Heights,

988

991 Dep.UseOp);

992

993

995 bool New;

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

997 if (New)

998 return true;

999

1000

1001 if (I->second < UseHeight)

1002 I->second = UseHeight;

1003 return false;

1004}

1005

1006

1007

1008

1009void MachineTraceMetrics::Ensemble::

1010addLiveIns(const MachineInstr *DefMI, unsigned DefOp,

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

1015 const MachineBasicBlock *DefMBB = DefMI->getParent();

1016

1017

1019 if (MBB == DefMBB)

1020 return;

1022

1023 TBI.LiveIns.emplace_back(VirtRegOrUnit(Reg));

1024 }

1025}

1026

1027

1028

1029

1030void MachineTraceMetrics::Ensemble::

1031computeInstrHeights(const MachineBasicBlock *MBB) {

1032

1033

1035 do {

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

1038 if (TBI.HasValidInstrHeights)

1039 break;

1041 TBI.LiveIns.clear();

1042 MBB = TBI.Succ;

1043 } while (MBB);

1044

1045

1046

1048

1049

1050

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

1053

1054

1055

1056

1057 if (MBB) {

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

1060 if (LI.VRegOrUnit.isVirtualReg()) {

1061

1062 unsigned &Height =

1063 Heights[MTM.MRI->getVRegDef(LI.VRegOrUnit.asVirtualReg())];

1064 if (Height < LI.Height)

1065 Height = LI.Height;

1066 } else {

1067

1068

1069 RegUnits[LI.VRegOrUnit.asMCRegUnit()].Cycle = LI.Height;

1070 }

1071 }

1072 }

1073

1074

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

1081 TBI.CriticalPath = 0;

1082

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

1085 ArrayRef PRHeights = getProcResourceHeights(MBB->getNumber());

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

1087 if (PRHeights[K]) {

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

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

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

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

1092 }

1093 });

1094

1095

1096 const MachineBasicBlock *Succ = TBI.Succ;

1097

1098

1099

1100 if (!Succ)

1101 if (const MachineLoop *Loop = getLoopFor(MBB))

1103 Succ = Loop->getHeader();

1104

1105 if (Succ) {

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

1107 if ( PHI .isPHI())

1108 break;

1111 if (!Deps.empty()) {

1112

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

1116 MTM.TII))

1118 }

1119 }

1120 }

1121

1122

1123 for (const MachineInstr &MI : reverse(*MBB)) {

1124

1125

1126 unsigned Cycle = 0;

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

1129 Cycle = HeightI->second;

1130

1131 Heights.erase(HeightI);

1132 }

1133

1134

1135

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

1138

1139

1140 if (HasPhysRegs)

1142 MTM.TII, MTM.TRI);

1143

1144

1145 for (const DataDep &Dep : Deps)

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

1148

1151 if (!TBI.HasValidInstrDepths) {

1153 continue;

1154 }

1155

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

1158 }

1159

1160

1161

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

1164 Register Reg = LIR.VRegOrUnit.asVirtualReg();

1165 const MachineInstr *DefMI = MTM.MRI->getVRegDef(Reg);

1168 }

1169

1170

1171 for (const LiveRegUnit &RU : RegUnits) {

1172 TBI.LiveIns.emplace_back(VirtRegOrUnit(RU.RegUnit), RU.Cycle);

1174 << RU.Cycle);

1175 }

1177

1178 if (!TBI.HasValidInstrDepths)

1179 continue;

1180

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

1182 computeCrossBlockCriticalPath(TBI));

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

1184 }

1185}

1186

1190

1192 computeTrace(MBB);

1194 computeInstrDepths(MBB);

1196 computeInstrHeights(MBB);

1197

1198 return Trace(*this, TBI);

1199}

1200

1201unsigned

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

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

1207}

1208

1209unsigned

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

1215 DataDep &Dep = Deps.front();

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

1217

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

1220 &PHI, Dep.UseOp);

1221 return DepCycle;

1222}

1223

1224

1226

1227

1228 unsigned PRMax = 0;

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

1230 if (Bottom) {

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

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

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

1234 } else {

1235 for (unsigned PRD : PRDepths)

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

1237 }

1238

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

1240

1241

1242 unsigned Instrs = TBI.InstrDepth;

1243

1244 if (Bottom)

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

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

1247 Instrs /= IW;

1248

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

1250}

1251

1256

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

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

1259 unsigned PRMax = 0;

1260

1261

1263 unsigned ResourceIdx)

1264 ->unsigned {

1265 unsigned Cycles = 0;

1267 if (!SC->isValid())

1268 continue;

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

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

1272 PI != PE; ++PI) {

1273 if (PI->ProcResourceIdx != ResourceIdx)

1274 continue;

1275 Cycles += (PI->ReleaseAtCycle *

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

1277 }

1278 }

1279 return Cycles;

1280 };

1281

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

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

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

1286 PRCycles += extraCycles(ExtraInstrs, K);

1287 PRCycles -= extraCycles(RemoveInstrs, K);

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

1289 }

1290

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

1292

1293

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

1295

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

1298 Instrs += ExtraInstrs.size();

1299 Instrs -= RemoveInstrs.size();

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

1301 Instrs /= IW;

1302

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

1304}

1305

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

1309 return true;

1310

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

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

1313

1315}

1316

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

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

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

1321 BlockInfo[i].print(OS);

1322 OS << '\n';

1323 }

1324}

1325

1331 else

1332 OS << " pred=null";

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

1335 OS << " +instrs";

1336 } else

1337 OS << "depth invalid";

1338 OS << ", ";

1343 else

1344 OS << " succ=null";

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

1347 OS << " +instrs";

1348 } else

1349 OS << "height invalid";

1352}

1353

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

1356

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

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

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

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

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

1363

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

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

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

1369 Block = &TE.BlockInfo[Num];

1370 }

1371

1373 OS << "\n ";

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

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

1377 Block = &TE.BlockInfo[Num];

1378 }

1379 OS << '\n';

1380}

unsigned const MachineRegisterInfo * MRI

MachineInstrBuilder & UseMI

MachineInstrBuilder MachineInstrBuilder & DefMI

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

const TargetInstrInfo & TII

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

static unsigned InstrCount

This file defines the DenseMap class.

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

Definition MachineTraceMetrics.cpp:984

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

Definition MachineTraceMetrics.cpp:719

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

Definition MachineTraceMetrics.cpp:691

DenseMap< const MachineInstr *, unsigned > MIHeightMap

Definition MachineTraceMetrics.cpp:980

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

Definition MachineTraceMetrics.cpp:316

static unsigned updatePhysDepsUpwards(const MachineInstr &MI, unsigned Height, LiveRegUnitSet &RegUnits, const TargetSchedModel &SchedModel, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)

Definition MachineTraceMetrics.cpp:927

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

Definition MachineTraceMetrics.cpp:738

Promote Memory to Register

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

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

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.

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)

DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator

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

bool contains(const LoopT *L) const

Return true if the specified loop is contained within in this 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...

LLVM_ABI bool isPredecessor(const MachineBasicBlock *MBB) const

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

iterator_range< succ_iterator > successors()

LLVM_ABI bool isSuccessor(const MachineBasicBlock *MBB) const

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

iterator_range< pred_iterator > predecessors()

MachineInstrBundleIterator< MachineInstr > iterator

MachineFunctionPass(char &ID)

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

Representation of each machine instruction.

const MachineBasicBlock * getParent() const

bool isTransient() const

Return true if this is a transient instruction that is either very likely to be eliminated during reg...

const MachineOperand & getOperand(unsigned i) const

Analysis pass that exposes the MachineLoopInfo for a machine function.

MachineOperand class - Representation of each machine instruction operand.

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

Definition MachineTraceMetrics.cpp:42

MachineTraceMetrics Result

void getAnalysisUsage(AnalysisUsage &) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

Definition MachineTraceMetrics.cpp:67

bool runOnMachineFunction(MachineFunction &) override

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

Definition MachineTraceMetrics.cpp:87

MachineTraceMetricsWrapperPass()

Definition MachineTraceMetrics.cpp:64

void invalidate(const MachineBasicBlock *MBB)

Invalidate traces through BadMBB.

Definition MachineTraceMetrics.cpp:564

void verify() const

Definition MachineTraceMetrics.cpp:627

ArrayRef< unsigned > getProcResourceHeights(unsigned MBBNum) const

Get an array of processor resource heights for MBB.

Definition MachineTraceMetrics.cpp:290

void updateDepth(TraceBlockInfo &TBI, const MachineInstr &, LiveRegUnitSet &RegUnits)

Updates the depth of an machine instruction, given RegUnits.

Definition MachineTraceMetrics.cpp:817

const MachineLoop * getLoopFor(const MachineBasicBlock *) const

Definition MachineTraceMetrics.cpp:181

void updateDepths(MachineBasicBlock::iterator Start, MachineBasicBlock::iterator End, LiveRegUnitSet &RegUnits)

Updates the depth of the instructions from Start to End.

Definition MachineTraceMetrics.cpp:862

const TraceBlockInfo * getHeightResources(const MachineBasicBlock *) const

Definition MachineTraceMetrics.cpp:264

const TraceBlockInfo * getDepthResources(const MachineBasicBlock *) const

Definition MachineTraceMetrics.cpp:255

ArrayRef< unsigned > getProcResourceDepths(unsigned MBBNum) const

Get an array of processor resource depths for MBB.

Definition MachineTraceMetrics.cpp:277

Ensemble(MachineTraceMetrics *)

Definition MachineTraceMetrics.cpp:169

MachineTraceMetrics & MTM

void print(raw_ostream &) const

Definition MachineTraceMetrics.cpp:1317

Trace getTrace(const MachineBasicBlock *MBB)

Get the trace that passes through MBB.

Definition MachineTraceMetrics.cpp:1188

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

unsigned getInstrCount() const

Compute the total number of instructions in the trace.

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

Return the resource length of the trace.

Definition MachineTraceMetrics.cpp:1252

InstrCycles getInstrCycles(const MachineInstr &MI) const

Return the depth and height of MI.

unsigned getInstrSlack(const MachineInstr &MI) const

Return the slack of MI.

Definition MachineTraceMetrics.cpp:1202

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

Definition MachineTraceMetrics.cpp:1306

unsigned getCriticalPath() const

Return the length of the (data dependency) critical path through the trace.

unsigned getPHIDepth(const MachineInstr &PHI) const

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

Definition MachineTraceMetrics.cpp:1210

void print(raw_ostream &) const

Definition MachineTraceMetrics.cpp:1354

unsigned getResourceDepth(bool Bottom) const

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

Definition MachineTraceMetrics.cpp:1225

void clear()

Definition MachineTraceMetrics.cpp:94

~MachineTraceMetrics()

Definition MachineTraceMetrics.cpp:92

MachineTraceMetrics()=default

Ensemble * getEnsemble(MachineTraceStrategy)

Get the trace ensemble representing the given trace selection strategy.

Definition MachineTraceMetrics.cpp:411

void verifyAnalysis() const

Definition MachineTraceMetrics.cpp:452

void invalidate(const MachineBasicBlock *MBB)

Invalidate cached information about MBB.

Definition MachineTraceMetrics.cpp:432

const FixedBlockInfo * getResources(const MachineBasicBlock *)

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

Definition MachineTraceMetrics.cpp:110

ArrayRef< unsigned > getProcReleaseAtCycles(unsigned MBBNum) const

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

Definition MachineTraceMetrics.cpp:157

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

Definition MachineTraceMetrics.cpp:73

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

AnalysisType & getAnalysis() const

getAnalysis() - This function is used by subclasses to get to the analysis information ...

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.

constexpr bool isVirtual() const

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)

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

iterator erase(iterator I)

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

const_iterator end() const

typename DenseT::iterator iterator

iterator find(const KeyT &Key)

find - Find an element by its key.

void setUniverse(unsigned U)

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

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.

const MCWriteProcResEntry * ProcResIter

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

Compute operand latency based on the available machine model.

TargetSubtargetInfo - Generic base class for all target subtargets.

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

Definition MachineTraceMetrics.cpp:495

void finishPostorder(const MachineBasicBlock *)

Definition MachineTraceMetrics.cpp:493

po_iterator_storage(LoopBounds &lb)

Definition MachineTraceMetrics.cpp:491

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.

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)

LLVM_ABI Printable printRegUnit(MCRegUnit Unit, const TargetRegisterInfo *TRI)

Create Printable object to print register units on a raw_ostream.

AnalysisManager< MachineFunction > MachineFunctionAnalysisManager

auto reverse(ContainerTy &&C)

LLVM_ABI raw_ostream & dbgs()

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

class LLVM_GSL_OWNER SmallVector

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

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

These are helper functions used to produce formatted output.

SparseSet< LiveRegUnit, MCRegUnit, MCRegUnitToIndex > LiveRegUnitSet

LLVM_ABI char & MachineTraceMetricsID

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

Definition MachineTraceMetrics.cpp:56

DWARFExpression::Operation Op

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

OutputIt copy(R &&Range, OutputIt Out)

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

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

LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

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.

PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)

Definition MachineTraceMetrics.cpp:48

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

A virtual register or regunit required by a basic block or its trace successors.

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.

SmallVector< LiveInReg, 4 > LiveIns

Live-in registers.

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

Definition MachineTraceMetrics.cpp:1326

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.

unsigned Tail

The block number of the tail of the trace. (When hasValidHeight()).

bool HasValidInstrHeights

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