EarlyIfConversion.cpp Source File (original) (raw)

42using namespace llvm;

44#define DEBUG_TYPE "early-ifcvt"

50 cl::desc("Maximum number of instructions per speculated block."));

54 cl::desc("Turn all knobs to 11"));

56 STATISTIC(NumDiamondsSeen, "Number of diamonds");

57 STATISTIC(NumDiamondsConv, "Number of diamonds converted");

58 STATISTIC(NumTrianglesSeen, "Number of triangles");

59 STATISTIC(NumTrianglesConv, "Number of triangles converted");

82namespace {

83class SSAIfConv {

88public:

100

101

102

103 bool isTriangle() const { return TBB == Tail || FBB == Tail; }

104

105

107

108

110

111

112 struct PHIInfo {

114 unsigned TReg = 0, FReg = 0;

115

116 int CondCycles = 0, TCycles = 0, FCycles = 0;

117

119 };

120

122

123

125

126private:

127

128

130

131

133

134

136

137

138

140

141

142

144

145

146

148

149

150

151 bool InstrDependenciesAllowIfConv(MachineInstr *I);

152

153

154

156

157

158 bool findInsertionPoint();

159

160

161 void replacePHIInstrs();

162

163

164 void rewritePHIOperands();

165

166public:

167

174 ClobberedRegUnits.clear();

175 ClobberedRegUnits.resize(TRI->getNumRegUnits());

176 }

177

178

179

180

181

183

184

185

187 bool Predicate = false);

188};

189}

190

191

192

193

194

195

196

197

198

200

201

204 return false;

205 }

206

208

209

210

213 if (MI.isDebugInstr())

214 continue;

215

219 return false;

220 }

221

222

223 if (MI.isPHI()) {

225 return false;

226 }

227

228

229

230

231 if (MI.mayLoad()) {

233 return false;

234 }

235

236

237 bool DontMoveAcrossStore = true;

238 if (.isSafeToMove(DontMoveAcrossStore)) {

240 return false;

241 }

242

243

244 if (!InstrDependenciesAllowIfConv(&MI))

245 return false;

246 }

247 return true;

248}

249

250

251

252

253

254bool SSAIfConv::InstrDependenciesAllowIfConv(MachineInstr *I) {

256 if (MO.isRegMask()) {

258 return false;

259 }

260 if (!MO.isReg())

261 continue;

263

264

265 if (MO.isDef() && Reg.isPhysical())

267 ClobberedRegUnits.set(Unit);

268

269 if (!MO.readsReg() || Reg .isVirtual())

270 continue;

273 continue;

278 LLVM_DEBUG(dbgs() << "Can't insert instructions below terminator.\n");

279 return false;

280 }

281 }

282 return true;

283}

284

285

286

287

288

289

290

291

292

294

295

298 return false;

299 }

300

302

303

304

307 I != E; ++I) {

308 if (I->isDebugInstr())

309 continue;

310

314 return false;

315 }

316

317

318 if (I->isPHI()) {

320 return false;

321 }

322

323

326 return false;

327 }

328

329

332 return false;

333 }

334

335

336 if (!InstrDependenciesAllowIfConv(&(*I)))

337 return false;

338 }

339 return true;

340}

341

342

343void SSAIfConv::PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate) {

344 auto Condition = Cond;

345 if (ReversePredicate) {

347 assert(CanRevCond && "Reversed predicate is not supported");

348 (void)CanRevCond;

349 }

350

353 I != E; ++I) {

354 if (I->isDebugInstr())

355 continue;

357 }

358}

359

360

361

362

363

364

365

366

367

368

369

370bool SSAIfConv::findInsertionPoint() {

371

372

378 while (I != B) {

379 --I;

380

381 if (InsertAfter.count(&*I)) {

383 return false;

384 }

385

386

388

389 if (!MO.isReg())

390 continue;

392 if ( Reg .isPhysical())

393 continue;

394

395 if (MO.isDef())

398

399 if (MO.readsReg())

401 }

402

403 while (!Reads.empty())

405 if (ClobberedRegUnits.test(Unit))

407

408

409 if (I != FirstTerm && I->isTerminator())

410 continue;

411

412

413

416 dbgs() << "Would clobber";

419 dbgs() << " live before " << *I;

420 });

421 continue;

422 }

423

424

427 return true;

428 }

429 LLVM_DEBUG(dbgs() << "No legal insertion point found.\n");

430 return false;

431}

432

433

434

435

436

437

439 Head = MBB;

440 TBB = FBB = Tail = nullptr;

441

443 return false;

446

447

450

452 return false;

453

455

456

457 if (Tail != Succ1) {

458

461 return false;

466

467

468 if ( Tail ->livein_empty()) {

470 return false;

471 }

472 } else {

476 }

477

478

479

480

481 if (!Predicate && (Tail->empty() || Tail ->front().isPHI())) {

483 return false;

484 }

485

486

487 Cond.clear();

490 return false;

491 }

492

493

494 if ( TBB ) {

495 LLVM_DEBUG(dbgs() << "analyzeBranch didn't find conditional branch.\n");

496 return false;

497 }

498

499

500

501 if (Cond.empty()) {

502 LLVM_DEBUG(dbgs() << "analyzeBranch found an unconditional branch.\n");

503 return false;

504 }

505

506

507

508 FBB = TBB == Succ0 ? Succ1 : Succ0;

509

510

515 I != E && I->isPHI(); ++I) {

517 PHIInfo &PI = PHIs.back();

518

519 for (unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) {

520 if (PI.PHI->getOperand(i+1).getMBB() == TPred)

521 PI.TReg = PI.PHI->getOperand(i).getReg();

522 if (PI.PHI->getOperand(i+1).getMBB() == FPred)

523 PI.FReg = PI.PHI->getOperand(i).getReg();

524 }

527

528

529 if ( TII ->canInsertSelect(*Head, Cond, PI.PHI->getOperand(0).getReg(),

530 PI.TReg, PI.FReg, PI.CondCycles, PI.TCycles,

531 PI.FCycles)) {

533 return false;

534 }

535 }

536

537

538 InsertAfter.clear();

539 ClobberedRegUnits.reset();

540 if (Predicate) {

541 if (TBB != Tail && !canPredicateInstrs(TBB))

542 return false;

543 if (FBB != Tail && !canPredicateInstrs(FBB))

544 return false;

545 } else {

546 if (TBB != Tail && !canSpeculateInstrs(TBB))

547 return false;

548 if (FBB != Tail && !canSpeculateInstrs(FBB))

549 return false;

550 }

551

552

553

554 if (!findInsertionPoint())

555 return false;

556

557 if (isTriangle())

558 ++NumTrianglesSeen;

559 else

560 ++NumDiamondsSeen;

561 return true;

562}

563

564

568 if (TReg == FReg)

569 return true;

570

572 return false;

573

576 if (!TDef || !FDef)

577 return false;

578

579

581 return false;

582

583

584

586 return false;

587

588

589

590

591

593 return MO.isReg() && MO.getReg().isPhysical();

594 }))

595 return false;

596

597

598 if ( TII ->produceSameValue(*TDef, *FDef, &MRI))

599 return false;

600

601

604 if (TIdx == -1 || FIdx == -1)

605 return false;

606

607 return TIdx == FIdx;

608}

609

610

611

612

613void SSAIfConv::replacePHIInstrs() {

614 assert(Tail->pred_size() == 2 && "Cannot replace PHIs");

616 assert(FirstTerm != Head->end() && "No terminators");

617 DebugLoc HeadDL = FirstTerm->getDebugLoc();

618

619

620 for (PHIInfo &PI : PHIs) {

622 Register DstReg = PI.PHI->getOperand(0).getReg();

624

625

626 BuildMI(*Head, FirstTerm, HeadDL, TII->get(TargetOpcode::COPY), DstReg)

628 } else {

629 TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg,

630 PI.FReg);

631 }

632 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));

633 PI.PHI->eraseFromParent();

634 PI.PHI = nullptr;

635 }

636}

637

638

639

640

641void SSAIfConv::rewritePHIOperands() {

643 assert(FirstTerm != Head->end() && "No terminators");

644 DebugLoc HeadDL = FirstTerm->getDebugLoc();

645

646

647 for (PHIInfo &PI : PHIs) {

648 unsigned DstReg = 0;

649

652

653

654 DstReg = PI.TReg;

655 } else {

656 Register PHIDst = PI.PHI->getOperand(0).getReg();

657 DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst));

658 TII->insertSelect(*Head, FirstTerm, HeadDL,

659 DstReg, Cond, PI.TReg, PI.FReg);

660 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));

661 }

662

663

664 for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) {

666 if (MBB == getTPred()) {

667 PI.PHI->getOperand(i-1).setMBB(Head);

668 PI.PHI->getOperand(i-2).setReg(DstReg);

669 } else if (MBB == getFPred()) {

670 PI.PHI->removeOperand(i-1);

671 PI.PHI->removeOperand(i-2);

672 }

673 }

675 }

676}

677

678

679

680

681

682

684 bool Predicate) {

685 assert(Head && Tail && TBB && FBB && "Call canConvertIf first.");

686

687

688 if (isTriangle())

689 ++NumTrianglesConv;

690 else

691 ++NumDiamondsConv;

692

693

695 if (Predicate)

696 PredicateBlock(TBB, false);

698 }

699 if (FBB != Tail) {

700 if (Predicate)

701 PredicateBlock(FBB, true);

703 }

704

705 bool ExtraPreds = Tail->pred_size() != 2;

706 if (ExtraPreds)

707 rewritePHIOperands();

708 else

709 replacePHIInstrs();

710

711

716 if (FBB != Tail)

718

719

720

723

724

725

726

731 }

732 if (FBB != Tail) {

736 }

737

740

747 if (Tail != &Tail->getParent()->back())

748 Tail->moveAfter(&Tail->getParent()->back());

749 } else {

750

751 LLVM_DEBUG(dbgs() << "Converting to unconditional branch.\n");

755 }

757}

758

759

760

761

762

763namespace {

764class EarlyIfConverter {

773 SSAIfConv IfConv;

774

775public:

778 : DomTree(&DT), Loops(&LI), Traces(&MTM) {}

779 EarlyIfConverter() = delete;

780

782

783private:

785 void invalidateTraces();

786 bool shouldConvertIf();

787};

788

790public:

791 static char ID;

796};

797}

798

799char EarlyIfConverterLegacy::ID = 0;

801

803 false, false)

809

810void EarlyIfConverterLegacy::getAnalysisUsage(AnalysisUsage &AU) const {

819}

820

821namespace {

822

825

826

827

829 for (auto *B : Removed) {

831 assert(Node != HeadNode && "Cannot erase the head node");

832 while (Node->getNumChildren()) {

833 assert(Node->getBlock() == IfConv.Tail && "Unexpected children");

835 }

837 }

838}

839

840

843

844

845 for (auto *B : Removed)

846 Loops->removeBlock(B);

847}

848}

849

850

851void EarlyIfConverter::invalidateTraces() {

852 Traces->verifyAnalysis();

853 Traces->invalidate(IfConv.Head);

854 Traces->invalidate(IfConv.Tail);

855 Traces->invalidate(IfConv.TBB);

856 Traces->invalidate(IfConv.FBB);

857 Traces->verifyAnalysis();

858}

859

860

861static unsigned adjCycles(unsigned Cyc, int Delta) {

862 if (Delta < 0 && Cyc + Delta > Cyc)

863 return 0;

864 return Cyc + Delta;

865}

866

867namespace {

868

869struct Cycles {

870 const char *Key;

872};

874 return R << ore::NV(C.Key, C.Value) << (C.Value == 1 ? " cycle" : " cycles");

875}

876}

877

878

879

880

881bool EarlyIfConverter::shouldConvertIf() {

882

884 return true;

885

886

887

889

890

891

892

893

895 if (!MO.isReg() || !MO.isUse())

896 return false;

897 Register Reg = MO.getReg();

898 if (Reg.isPhysical())

899 return false;

900

901 MachineInstr *Def = MRI->getVRegDef(Reg);

902 return CurrentLoop->isLoopInvariant(*Def) ||

903 all_of(Def->operands(), [&](MachineOperand &Op) {

904 if (Op.isImm())

905 return true;

906 if (!MO.isReg() || !MO.isUse())

907 return false;

908 Register Reg = MO.getReg();

909 if (Reg.isPhysical())

910 return false;

911

912 MachineInstr *Def = MRI->getVRegDef(Reg);

913 return CurrentLoop->isLoopInvariant(*Def);

914 });

915 }))

916 return false;

917

918 if (!MinInstr)

919 MinInstr = Traces->getEnsemble(MachineTraceStrategy::TS_MinInstrCount);

920

923 LLVM_DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace);

926

927

928 unsigned CritLimit = SchedModel.MispredictPenalty/2;

929

932

933

934

935

937 if (IfConv.TBB != IfConv.Tail)

938 ExtraBlocks.push_back(IfConv.TBB);

941 << ", minimal critical path " << MinCrit << '\n');

942 if (ResLength > MinCrit + CritLimit) {

944 MORE.emit([&]() {

947 R << "did not if-convert branch: the resulting critical path ("

948 << Cycles{"ResLength", ResLength}

949 << ") would extend the shorter leg's critical path ("

950 << Cycles{"MinCrit", MinCrit} << ") by more than the threshold of "

951 << Cycles{"CritLimit", CritLimit}

952 << ", which cannot be hidden by available ILP.";

953 return R;

954 });

955 return false;

956 }

957

958

959

960

962 unsigned BranchDepth =

964 LLVM_DEBUG(dbgs() << "Branch depth: " << BranchDepth << '\n');

965

966

967

969 struct CriticalPathInfo {

970 unsigned Extra;

971 unsigned Depth;

972 };

973 CriticalPathInfo Cond{};

974 CriticalPathInfo TBlock{};

975 CriticalPathInfo FBlock{};

976 bool ShouldConvert = true;

977 for (SSAIfConv::PHIInfo &PI : IfConv.PHIs) {

978 unsigned Slack = TailTrace.getInstrSlack(*PI.PHI);

980 LLVM_DEBUG(dbgs() << "Slack " << Slack << ":\t" << *PI.PHI);

981

982

983 unsigned CondDepth = adjCycles(BranchDepth, PI.CondCycles);

984 if (CondDepth > MaxDepth) {

985 unsigned Extra = CondDepth - MaxDepth;

986 LLVM_DEBUG(dbgs() << "Condition adds " << Extra << " cycles.\n");

987 if (Extra > Cond.Extra)

988 Cond = {Extra, CondDepth};

989 if (Extra > CritLimit) {

990 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');

991 ShouldConvert = false;

992 }

993 }

994

995

997 if (TDepth > MaxDepth) {

998 unsigned Extra = TDepth - MaxDepth;

999 LLVM_DEBUG(dbgs() << "TBB data adds " << Extra << " cycles.\n");

1000 if (Extra > TBlock.Extra)

1001 TBlock = {Extra, TDepth};

1002 if (Extra > CritLimit) {

1003 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');

1004 ShouldConvert = false;

1005 }

1006 }

1007

1008

1010 if (FDepth > MaxDepth) {

1011 unsigned Extra = FDepth - MaxDepth;

1012 LLVM_DEBUG(dbgs() << "FBB data adds " << Extra << " cycles.\n");

1013 if (Extra > FBlock.Extra)

1014 FBlock = {Extra, FDepth};

1015 if (Extra > CritLimit) {

1016 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');

1017 ShouldConvert = false;

1018 }

1019 }

1020 }

1021

1022

1023

1024

1025 const CriticalPathInfo Short = TBlock.Extra > FBlock.Extra ? FBlock : TBlock;

1026 const CriticalPathInfo Long = TBlock.Extra > FBlock.Extra ? TBlock : FBlock;

1027

1028 if (ShouldConvert) {

1029 MORE.emit([&]() {

1032 R << "performing if-conversion on branch: the condition adds "

1033 << Cycles{"CondCycles", Cond.Extra} << " to the critical path";

1034 if (Short.Extra > 0)

1035 R << ", and the short leg adds another "

1036 << Cycles{"ShortCycles", Short.Extra};

1037 if (Long.Extra > 0)

1038 R << ", and the long leg adds another "

1039 << Cycles{"LongCycles", Long.Extra};

1040 R << ", each staying under the threshold of "

1041 << Cycles{"CritLimit", CritLimit} << ".";

1042 return R;

1043 });

1044 } else {

1045 MORE.emit([&]() {

1048 R << "did not if-convert branch: the condition would add "

1049 << Cycles{"CondCycles", Cond.Extra} << " to the critical path";

1050 if (Cond.Extra > CritLimit)

1051 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};

1052 if (Short.Extra > 0) {

1053 R << ", and the short leg would add another "

1054 << Cycles{"ShortCycles", Short.Extra};

1055 if (Short.Extra > CritLimit)

1056 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};

1057 }

1058 if (Long.Extra > 0) {

1059 R << ", and the long leg would add another "

1060 << Cycles{"LongCycles", Long.Extra};

1061 if (Long.Extra > CritLimit)

1062 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit};

1063 }

1064 R << ".";

1065 return R;

1066 });

1067 }

1068

1069 return ShouldConvert;

1070}

1071

1072

1073

1075 bool Changed = false;

1076 while (IfConv.canConvertIf(MBB) && shouldConvertIf()) {

1077

1078 invalidateTraces();

1080 IfConv.convertIf(RemoveBlocks);

1081 Changed = true;

1082 updateDomTree(DomTree, IfConv, RemoveBlocks);

1085 updateLoops(Loops, RemoveBlocks);

1086 }

1087 return Changed;

1088}

1089

1091 LLVM_DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n"

1092 << "********** Function: " << MF.getName() << '\n');

1093

1094

1097 return false;

1098

1103 MinInstr = nullptr;

1104

1105 bool Changed = false;

1106 IfConv.init(MF);

1107

1108

1109

1110

1111

1112 for (auto *DomNode : post_order(DomTree))

1113 if (tryConvertIf(DomNode->getBlock()))

1114 Changed = true;

1115

1116 return Changed;

1117}

1118

1125

1126 EarlyIfConverter Impl(MDT, LI, MTM);

1127 bool Changed = Impl.run(MF);

1128 if (!Changed)

1130

1135 return PA;

1136}

1137

1138bool EarlyIfConverterLegacy::runOnMachineFunction(MachineFunction &MF) {

1140 return false;

1141

1143 getAnalysis().getDomTree();

1144 MachineLoopInfo &LI = getAnalysis().getLI();

1146 getAnalysis().getMTM();

1147

1148 return EarlyIfConverter(MDT, LI, MTM).run(MF);

1149}

1150

1151

1152

1153

1154

1155namespace {

1164 SSAIfConv IfConv;

1165

1166public:

1167 static char ID;

1169 void getAnalysisUsage(AnalysisUsage &AU) const override;

1170 bool runOnMachineFunction(MachineFunction &MF) override;

1171 StringRef getPassName() const override { return "Early If-predicator"; }

1172

1173protected:

1175 bool shouldConvertIf();

1176};

1177}

1178

1179#undef DEBUG_TYPE

1180#define DEBUG_TYPE "early-if-predicator"

1181

1182char EarlyIfPredicator::ID = 0;

1184

1186 false, false)

1191

1192void EarlyIfPredicator::getAnalysisUsage(AnalysisUsage &AU) const {

1199}

1200

1201

1202bool EarlyIfPredicator::shouldConvertIf() {

1203 auto TrueProbability = MBPI->getEdgeProbability(IfConv.Head, IfConv.TBB);

1204 if (IfConv.isTriangle()) {

1206 (IfConv.TBB == IfConv.Tail) ? *IfConv.FBB : *IfConv.TBB;

1207

1208 unsigned ExtraPredCost = 0;

1209 unsigned Cycles = 0;

1211 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);

1212 if (NumCycles > 1)

1213 Cycles += NumCycles - 1;

1214 ExtraPredCost += TII->getPredicationCost(I);

1215 }

1216

1218 TrueProbability);

1219 }

1220 unsigned TExtra = 0;

1221 unsigned FExtra = 0;

1222 unsigned TCycle = 0;

1223 unsigned FCycle = 0;

1225 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);

1226 if (NumCycles > 1)

1227 TCycle += NumCycles - 1;

1228 TExtra += TII->getPredicationCost(I);

1229 }

1231 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);

1232 if (NumCycles > 1)

1233 FCycle += NumCycles - 1;

1234 FExtra += TII->getPredicationCost(I);

1235 }

1237 FCycle, FExtra, TrueProbability);

1238}

1239

1240

1241

1243 bool Changed = false;

1244 while (IfConv.canConvertIf(MBB, true) && shouldConvertIf()) {

1245

1247 IfConv.convertIf(RemoveBlocks, true);

1248 Changed = true;

1249 updateDomTree(DomTree, IfConv, RemoveBlocks);

1252 updateLoops(Loops, RemoveBlocks);

1253 }

1254 return Changed;

1255}

1256

1257bool EarlyIfPredicator::runOnMachineFunction(MachineFunction &MF) {

1258 LLVM_DEBUG(dbgs() << "********** EARLY IF-PREDICATOR **********\n"

1259 << "********** Function: " << MF.getName() << '\n');

1261 return false;

1262

1267 SchedModel.init(&STI);

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

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

1270 MBPI = &getAnalysis().getMBPI();

1271

1272 bool Changed = false;

1273 IfConv.init(MF);

1274

1275

1276

1277

1278

1279 for (auto *DomNode : post_order(DomTree))

1280 if (tryConvertIf(DomNode->getBlock()))

1281 Changed = true;

1282

1283 return Changed;

1284}

unsigned const MachineRegisterInfo * MRI

for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))

MachineInstrBuilder MachineInstrBuilder & DefMI

This file implements the BitVector class.

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

static unsigned InstrCount

static bool hasSameValue(const MachineRegisterInfo &MRI, const TargetInstrInfo *TII, Register TReg, Register FReg)

static unsigned adjCycles(unsigned Cyc, int Delta)

static cl::opt< bool > Stress("stress-early-ifcvt", cl::Hidden, cl::desc("Turn all knobs to 11"))

static cl::opt< unsigned > BlockInstrLimit("early-ifcvt-limit", cl::init(30), cl::Hidden, cl::desc("Maximum number of instructions per speculated block."))

const HexagonInstrInfo * TII

unsigned const TargetRegisterInfo * TRI

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

const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB

const SmallVectorImpl< MachineOperand > & Cond

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

This file defines the SmallPtrSet class.

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

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

#define STATISTIC(VARNAME, DESC)

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.

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

bool test(unsigned Idx) const

void resize(unsigned N, bool t=false)

resize - Grow or shrink the bitvector.

void clear()

clear - Removes all bits from the bitvector.

Base class for the actual dominator tree node.

void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)

changeImmediateDominator - This method is used to update the dominator tree information when a node's...

void eraseNode(NodeT *BB)

eraseNode - Removes a node from the dominator tree.

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)

unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override

Remove the branching code at the end of the specific MBB.

bool isPredicated(const MachineInstr &MI) const override

Returns true if the instruction is already predicated.

bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override

Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....

bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const override

Reverses the branch condition of the specified condition list, returning false on success and true if...

unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override

Insert branch code into the end of the specified MachineBasicBlock.

bool isProfitableToIfCvt(MachineBasicBlock &MBB, unsigned NumCycles, unsigned ExtraPredCycles, BranchProbability Probability) const override

Return true if it's profitable to predicate instructions with accumulated instruction latency of "Num...

bool PredicateInstruction(MachineInstr &MI, ArrayRef< MachineOperand > Cond) const override

Convert the instruction into a predicated instruction.

bool isPredicable(const MachineInstr &MI) const override

Return true if the specified instruction can be predicated.

A set of register units used to track register liveness.

bool empty() const

Returns true if the set is empty.

void clear()

Clears the set.

const MCSchedModel & getSchedModel() const

Get the machine model for this subtarget's CPU.

unsigned pred_size() const

void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB)

Transfers all the successors, as in transferSuccessors, and update PHI operands in the successor bloc...

succ_iterator succ_begin()

bool livein_empty() const

iterator getFirstTerminator()

Returns an iterator to the first terminator instruction of this basic block.

unsigned succ_size() const

void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())

Add Succ as a successor of this MachineBasicBlock.

void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)

Remove successor from the successors list of this MachineBasicBlock.

DebugLoc findDebugLoc(instr_iterator MBBI)

Find the next valid DebugLoc starting at MBBI, skipping any debug instructions.

bool isLayoutSuccessor(const MachineBasicBlock *MBB) const

Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...

void eraseFromParent()

This method unlinks 'this' from the containing function and deletes it.

const MachineFunction * getParent() const

Return the MachineFunction containing this basic block.

void splice(iterator Where, MachineBasicBlock *Other, iterator From)

Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...

void moveAfter(MachineBasicBlock *NewBefore)

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.

virtual bool runOnMachineFunction(MachineFunction &MF)=0

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

const TargetSubtargetInfo & getSubtarget() const

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

StringRef getName() const

getName - Return the name of the corresponding LLVM function.

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

Function & getFunction()

Return the LLVM function that this machine code represents.

const MachineBasicBlock & back() const

const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const

Add a new virtual register operand.

Representation of each machine instruction.

bool isTerminator(QueryType Type=AnyInBundle) const

Returns true if this instruction part of the terminator for a basic block.

bool mayLoadOrStore(QueryType Type=AnyInBundle) const

Return true if this instruction could possibly read or modify memory.

const MachineBasicBlock * getParent() const

bool isDereferenceableInvariantLoad() const

Return true if this load instruction never traps and points to a memory location whose value doesn't ...

iterator_range< mop_iterator > uses()

Returns a range that includes all operands which may be register uses.

bool hasUnmodeledSideEffects() const

Return true if this instruction has side effects that are not modeled by mayLoad / mayStore,...

const DebugLoc & getDebugLoc() const

Returns the debug location id of this MachineInstr.

int findRegisterDefOperandIdx(Register Reg, const TargetRegisterInfo *TRI, bool isDead=false, bool Overlap=false) const

Returns the operand index that is a def of the specified register or -1 if it is not found.

Analysis pass that exposes the MachineLoopInfo for a machine function.

MachineOperand class - Representation of each machine instruction operand.

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

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

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.

InstrCycles getInstrCycles(const MachineInstr &MI) const

Return the depth and height of MI.

unsigned getInstrSlack(const MachineInstr &MI) const

Return the slack of MI.

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.

virtual StringRef getPassName() const

getPassName - Return a nice clean name for a pass.

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.

Wrapper class representing virtual and physical registers.

constexpr bool isVirtual() const

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

static constexpr bool isVirtualRegister(unsigned Reg)

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

size_type count(ConstPtrType Ptr) const

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

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

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

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.

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

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

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.

TargetSubtargetInfo - Generic base class for all target subtargets.

virtual const TargetRegisterInfo * getRegisterInfo() const

getRegisterInfo - If register information is available, return it.

virtual const TargetInstrInfo * getInstrInfo() const

virtual bool enableEarlyIfConversion() const

Enable the use of the early if conversion pass.

LLVM Value Representation.

@ Tail

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

@ C

The default llvm calling convention, compatible with C.

unsigned ID

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

Reg

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

initializer< Ty > init(const Ty &Val)

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

DiagnosticInfoOptimizationBase::Argument NV

This is an optimization pass for GlobalISel generic memory operations.

MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)

Builder interface. Specify how to create the initial instruction itself.

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

Convenience function for iterating over sub-ranges.

Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)

Create Printable object to print register units on a raw_ostream.

iterator_range< po_iterator< T > > post_order(const T &G)

char & EarlyIfConverterLegacyID

EarlyIfConverter - This pass performs if-conversion on SSA form by inserting cmov instructions.

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.

raw_ostream & dbgs()

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

char & EarlyIfPredicatorID

EarlyIfPredicator - This pass performs if-conversion on SSA form by predicating if/else block and ins...

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

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

Implement std::swap in terms of BitVector swap.

Machine model for scheduling, bundling, and heuristics.

unsigned Depth

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