EarlyIfConversion.cpp Source File (original) (raw)

44using namespace llvm;

46#define DEBUG_TYPE "early-ifcvt"

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

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

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

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

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

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

84namespace {

85class SSAIfConv {

90public:

100

102

103

104

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

106

107

108 MachineBasicBlock *getTPred() const { return TBB == Tail ? Head : TBB; }

109

110

111 MachineBasicBlock *getFPred() const { return FBB == Tail ? Head : FBB; }

112

113

114 struct PHIInfo {

115 MachineInstr *PHI;

117

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

119

120 PHIInfo(MachineInstr *phi) : PHI(phi) {}

121 };

122

124

125

127

128private:

129

130

131 SmallPtrSet<MachineInstr*, 8> InsertAfter;

132

133

134 BitVector ClobberedRegUnits;

135

136

137 SparseSet<MCRegUnit, MCRegUnit, MCRegUnitToIndex> LiveRegUnits;

138

139

140

142

143

144

145 bool canSpeculateInstrs(MachineBasicBlock *MBB);

146

147

148

149 bool canPredicateInstrs(MachineBasicBlock *MBB);

150

151

152

153 bool InstrDependenciesAllowIfConv(MachineInstr *I);

154

155

156

157 void PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate);

158

159

160 bool findInsertionPoint();

161

162

163 void replacePHIInstrs();

164

165

166 void rewritePHIOperands();

167

168

169

170 void clearRepeatedKillFlagsFromTBB(MachineBasicBlock *TBB,

171 MachineBasicBlock *FBB);

172

173public:

174

175 void init(MachineFunction &MF) {

179 LiveRegUnits.clear();

180 LiveRegUnits.setUniverse(TRI->getNumRegUnits());

181 ClobberedRegUnits.clear();

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

183 }

184

185

186

187

188

189 bool canConvertIf(MachineBasicBlock *MBB, bool Predicate = false);

190

191

192

193 void convertIf(SmallVectorImpl<MachineBasicBlock *> &RemoveBlocks,

194 bool Predicate = false);

195};

196}

197

198

199

200

201

202

203

204

205

207

208

211 return false;

212 }

213

215

216

217

218 for (MachineInstr &MI :

220 if (MI.isDebugInstr())

221 continue;

222

226 return false;

227 }

228

229

230 if (MI.isPHI()) {

232 return false;

233 }

234

235

236

237

238 if (MI.mayLoad()) {

240 return false;

241 }

242

243

244 bool DontMoveAcrossStore = true;

245 if (.isSafeToMove(DontMoveAcrossStore)) {

247 return false;

248 }

249

250

251 if (!InstrDependenciesAllowIfConv(&MI))

252 return false;

253 }

254 return true;

255}

256

257

258

259

260

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

262 for (const MachineOperand &MO : I->operands()) {

263 if (MO.isRegMask()) {

265 return false;

266 }

267 if (!MO.isReg())

268 continue;

270

271

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

274 ClobberedRegUnits.set(static_cast<unsigned>(Unit));

275

277 continue;

278 MachineInstr *DefMI = MRI->getVRegDef(Reg);

280 continue;

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

286 return false;

287 }

288 }

289 return true;

290}

291

292

293

294

295

296

297

298

299

300bool SSAIfConv::canPredicateInstrs(MachineBasicBlock *MBB) {

301

302

305 return false;

306 }

307

309

310

311

314 I != E; ++I) {

315 if (I->isDebugInstr())

316 continue;

317

321 return false;

322 }

323

324

325 if (I->isPHI()) {

327 return false;

328 }

329

330

333 return false;

334 }

335

336

339 return false;

340 }

341

342

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

344 return false;

345 }

346 return true;

347}

348

349

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

351 auto Condition = Cond;

352 if (ReversePredicate) {

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

355 (void)CanRevCond;

356 }

357

360 I != E; ++I) {

361 if (I->isDebugInstr())

362 continue;

364 }

365}

366

367

368

369

370

371

372

373

374

375

376

377bool SSAIfConv::findInsertionPoint() {

378

379

380 LiveRegUnits.clear();

385 while (I != B) {

386 --I;

387

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

390 return false;

391 }

392

393

394 for (const MachineOperand &MO : I->operands()) {

395

396 if (!MO.isReg())

397 continue;

400 continue;

401

402 if (MO.isDef())

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

404 LiveRegUnits.erase(Unit);

405

406 if (MO.readsReg())

408 }

409

410 while (!Reads.empty())

411 for (MCRegUnit Unit : TRI->regunits(Reads.pop_back_val()))

412 if (ClobberedRegUnits.test(static_cast<unsigned>(Unit)))

413 LiveRegUnits.insert(Unit);

414

415

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

417 continue;

418

419

420

421 if (!LiveRegUnits.empty()) {

423 dbgs() << "Would clobber";

424 for (MCRegUnit LRU : LiveRegUnits)

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

427 });

428 continue;

429 }

430

431

432 InsertionPoint = I;

434 return true;

435 }

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

437 return false;

438}

439

440

441

442

443

444

445bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB, bool Predicate) {

446 Head = MBB;

447 TBB = FBB = Tail = nullptr;

448

450 return false;

451 MachineBasicBlock *Succ0 = Head->succ_begin()[0];

452 MachineBasicBlock *Succ1 = Head->succ_begin()[1];

453

454

457

459 return false;

460

462

463

464 if (Tail != Succ1) {

465

468 return false;

473

474

475 if ( Tail ->livein_empty()) {

477 return false;

478 }

479 } else {

483 }

484

485

486

487

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

490 return false;

491 }

492

493

494 Cond.clear();

497 return false;

498 }

499

500

501 if ( TBB ) {

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

503 return false;

504 }

505

506

507

508 if (Cond.empty()) {

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

510 return false;

511 }

512

513

514

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

516

517

519 MachineBasicBlock *TPred = getTPred();

520 MachineBasicBlock *FPred = getFPred();

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

524 PHIInfo &PI = PHIs.back();

525

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

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

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

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

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

531 }

532 assert(PI.TReg.isVirtual() && "Bad PHI");

533 assert(PI.FReg.isVirtual() && "Bad PHI");

534

535

537 PI.TReg, PI.FReg, PI.CondCycles, PI.TCycles,

538 PI.FCycles)) {

540 return false;

541 }

542 }

543

544

545 InsertAfter.clear();

546 ClobberedRegUnits.reset();

547 if (Predicate) {

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

549 return false;

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

551 return false;

552 } else {

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

554 return false;

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

556 return false;

557 }

558

559

560

561 if (!findInsertionPoint())

562 return false;

563

564 if (isTriangle())

565 ++NumTrianglesSeen;

566 else

567 ++NumDiamondsSeen;

568 return true;

569}

570

571

575 if (TReg == FReg)

576 return true;

577

578 if (!TReg.isVirtual() || !FReg.isVirtual())

579 return false;

580

583 if (!TDef || !FDef)

584 return false;

585

586

588 return false;

589

590

591

593 return false;

594

595

596

597

598

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

601 }))

602 return false;

603

604

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

606 return false;

607

608

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

612 return false;

613

614 return TIdx == FIdx;

615}

616

617

618

619

620void SSAIfConv::replacePHIInstrs() {

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

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

624 DebugLoc HeadDL = FirstTerm->getDebugLoc();

625

626

627 for (PHIInfo &PI : PHIs) {

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

631

632

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

635 } else {

637 PI.FReg);

638 }

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

640 PI.PHI->eraseFromParent();

641 PI.PHI = nullptr;

642 }

643}

644

645

646

647

648void SSAIfConv::rewritePHIOperands() {

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

651 DebugLoc HeadDL = FirstTerm->getDebugLoc();

652

653

654 for (PHIInfo &PI : PHIs) {

656

659

660

661 DstReg = PI.TReg;

662 } else {

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

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

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

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

668 }

669

670

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

672 MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB();

673 if (MBB == getTPred()) {

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

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

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

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

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

679 }

680 }

682 }

683}

684

685void SSAIfConv::clearRepeatedKillFlagsFromTBB(MachineBasicBlock *TBB,

686 MachineBasicBlock *FBB) {

688

689

690 SmallDenseSet FBBKilledRegs;

691 for (MachineInstr &MI : FBB->instrs()) {

692 for (MachineOperand &MO : MI.operands()) {

693 if (MO.isReg() && MO.isKill() && MO.getReg().isVirtual())

694 FBBKilledRegs.insert(MO.getReg());

695 }

696 }

697

698 if (FBBKilledRegs.empty())

699 return;

700

701

703 for (MachineOperand &MO : MI.operands()) {

704 if (MO.isReg() && MO.isKill() && FBBKilledRegs.contains(MO.getReg()))

705 MO.setIsKill(false);

706 }

707 }

708}

709

710

711

712

713

714

715void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock *> &RemoveBlocks,

716 bool Predicate) {

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

718

719

720 if (isTriangle())

721 ++NumTrianglesConv;

722 else

723 ++NumDiamondsConv;

724

725

726

727

728

730 clearRepeatedKillFlagsFromTBB(TBB, FBB);

731

732

734 if (Predicate)

735 PredicateBlock(TBB, false);

737 }

738 if (FBB != Tail) {

739 if (Predicate)

740 PredicateBlock(FBB, true);

742 }

743

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

745 if (ExtraPreds)

746 rewritePHIOperands();

747 else

748 replacePHIInstrs();

749

750

755 if (FBB != Tail)

757

758

759

762

763

764

765

770 }

771 if (FBB != Tail) {

775 }

776

779

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

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

788 } else {

789

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

794 }

796}

797

798

799

800

801

802namespace {

803class EarlyIfConverter {

804 const TargetInstrInfo *TII = nullptr;

805 const TargetRegisterInfo *TRI = nullptr;

806 MCSchedModel SchedModel;

807 MachineRegisterInfo *MRI = nullptr;

808 MachineDominatorTree *DomTree = nullptr;

809 MachineLoopInfo *Loops = nullptr;

810 MachineTraceMetrics *Traces = nullptr;

812 SSAIfConv IfConv;

813

814public:

815 EarlyIfConverter(MachineDominatorTree &DT, MachineLoopInfo &LI,

816 MachineTraceMetrics &MTM)

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

818 EarlyIfConverter() = delete;

819

820 bool run(MachineFunction &MF);

821

822private:

823 bool tryConvertIf(MachineBasicBlock *);

824 void invalidateTraces();

825 bool shouldConvertIf();

826};

827

828class EarlyIfConverterLegacy : public MachineFunctionPass {

829public:

830 static char ID;

831 EarlyIfConverterLegacy() : MachineFunctionPass(ID) {}

832 void getAnalysisUsage(AnalysisUsage &AU) const override;

833 bool runOnMachineFunction(MachineFunction &MF) override;

834 StringRef getPassName() const override { return "Early If-Conversion"; }

835};

836}

837

838char EarlyIfConverterLegacy::ID = 0;

840

842 false, false)

848

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

858}

859

860namespace {

861

862void updateDomTree(MachineDominatorTree *DomTree, const SSAIfConv &IfConv,

864

865

866

868 for (auto *B : Removed) {

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

871 while (Node->getNumChildren()) {

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

874 }

876 }

877}

878

879

880void updateLoops(MachineLoopInfo *Loops,

882

883

884 for (auto *B : Removed)

885 Loops->removeBlock(B);

886}

887}

888

889

890void EarlyIfConverter::invalidateTraces() {

897}

898

899

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

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

902 return 0;

903 return Cyc + Delta;

904}

905

906namespace {

907

908struct Cycles {

909 const char *Key;

911};

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

914}

915}

916

917

918

919

920bool EarlyIfConverter::shouldConvertIf() {

921

923 return true;

924

925

926

927 MachineLoop *CurrentLoop = Loops->getLoopFor(IfConv.Head);

928

929

930

931

932

933 if (CurrentLoop && any_of(IfConv.Cond, [&](MachineOperand &MO) {

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

935 return false;

936 Register Reg = MO.getReg();

937 if (Reg.isPhysical())

938 return false;

939

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

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

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

943 if (Op.isImm())

944 return true;

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

946 return false;

947 Register Reg = MO.getReg();

948 if (Reg.isPhysical())

949 return false;

950

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

952 return CurrentLoop->isLoopInvariant(*Def);

953 });

954 }))

955 return false;

956

957 if (!MinInstr)

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

959

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

965

966

967 unsigned CritLimit = SchedModel.MispredictPenalty/2;

968

969 MachineBasicBlock &MBB = *IfConv.Head;

970 MachineOptimizationRemarkEmitter MORE(*MBB.getParent(), nullptr);

971

972

973

974

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

977 ExtraBlocks.push_back(IfConv.TBB);

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

981 if (ResLength > MinCrit + CritLimit) {

983 MORE.emit([&]() {

984 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "IfConversion",

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

987 << Cycles{"ResLength", ResLength}

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

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

990 << Cycles{"CritLimit", CritLimit}

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

992 return R;

993 });

994 return false;

995 }

996

997

998

999

1001 unsigned BranchDepth =

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

1004

1005

1006

1008 struct CriticalPathInfo {

1009 unsigned Extra;

1010 unsigned Depth;

1011 };

1012 CriticalPathInfo Cond{};

1013 CriticalPathInfo TBlock{};

1014 CriticalPathInfo FBlock{};

1015 bool ShouldConvert = true;

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

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

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

1020

1021

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

1023 if (CondDepth > MaxDepth) {

1024 unsigned Extra = CondDepth - MaxDepth;

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

1026 if (Extra > Cond.Extra)

1027 Cond = {Extra, CondDepth};

1028 if (Extra > CritLimit) {

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

1030 ShouldConvert = false;

1031 }

1032 }

1033

1034

1036 if (TDepth > MaxDepth) {

1037 unsigned Extra = TDepth - MaxDepth;

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

1039 if (Extra > TBlock.Extra)

1040 TBlock = {Extra, TDepth};

1041 if (Extra > CritLimit) {

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

1043 ShouldConvert = false;

1044 }

1045 }

1046

1047

1049 if (FDepth > MaxDepth) {

1050 unsigned Extra = FDepth - MaxDepth;

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

1052 if (Extra > FBlock.Extra)

1053 FBlock = {Extra, FDepth};

1054 if (Extra > CritLimit) {

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

1056 ShouldConvert = false;

1057 }

1058 }

1059 }

1060

1061

1062

1063

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

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

1066

1067 if (ShouldConvert) {

1068 MORE.emit([&]() {

1069 MachineOptimizationRemark R(DEBUG_TYPE, "IfConversion",

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

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

1073 if (Short.Extra > 0)

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

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

1076 if (Long.Extra > 0)

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

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

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

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

1081 return R;

1082 });

1083 } else {

1084 MORE.emit([&]() {

1085 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "IfConversion",

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

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

1089 if (Cond.Extra > CritLimit)

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

1091 if (Short.Extra > 0) {

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

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

1094 if (Short.Extra > CritLimit)

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

1096 }

1097 if (Long.Extra > 0) {

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

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

1100 if (Long.Extra > CritLimit)

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

1102 }

1103 R << ".";

1104 return R;

1105 });

1106 }

1107

1108 return ShouldConvert;

1109}

1110

1111

1112

1113bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) {

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

1116

1117 invalidateTraces();

1118 SmallVector<MachineBasicBlock *, 4> RemoveBlocks;

1119 IfConv.convertIf(RemoveBlocks);

1121 updateDomTree(DomTree, IfConv, RemoveBlocks);

1122 for (MachineBasicBlock *MBB : RemoveBlocks)

1124 updateLoops(Loops, RemoveBlocks);

1125 }

1127}

1128

1129bool EarlyIfConverter::run(MachineFunction &MF) {

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

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

1132

1133

1134 const TargetSubtargetInfo &STI = MF.getSubtarget();

1136 return false;

1137

1142 MinInstr = nullptr;

1143

1145 IfConv.init(MF);

1146

1147

1148

1149

1150

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

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

1154

1156}

1157

1158PreservedAnalyses

1164

1165 EarlyIfConverter Impl(MDT, LI, MTM);

1166 bool Changed = Impl.run(MF);

1169

1174 return PA;

1175}

1176

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

1179 return false;

1180

1182 getAnalysis().getDomTree();

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

1185 getAnalysis().getMTM();

1186

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

1188}

1189

1190

1191

1192

1193

1194namespace {

1203 SSAIfConv IfConv;

1204

1205public:

1206 static char ID;

1208 void getAnalysisUsage(AnalysisUsage &AU) const override;

1209 bool runOnMachineFunction(MachineFunction &MF) override;

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

1211

1212protected:

1213 bool tryConvertIf(MachineBasicBlock *);

1214 bool shouldConvertIf();

1215};

1216}

1217

1218#undef DEBUG_TYPE

1219#define DEBUG_TYPE "early-if-predicator"

1220

1221char EarlyIfPredicator::ID = 0;

1223

1225 false, false)

1230

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

1238}

1239

1240

1241bool EarlyIfPredicator::shouldConvertIf() {

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

1243 if (IfConv.isTriangle()) {

1244 MachineBasicBlock &IfBlock =

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

1246

1247 unsigned ExtraPredCost = 0;

1248 unsigned Cycles = 0;

1249 for (MachineInstr &I : IfBlock) {

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

1251 if (NumCycles > 1)

1252 Cycles += NumCycles - 1;

1254 }

1255

1257 TrueProbability);

1258 }

1259 unsigned TExtra = 0;

1260 unsigned FExtra = 0;

1261 unsigned TCycle = 0;

1262 unsigned FCycle = 0;

1263 for (MachineInstr &I : *IfConv.TBB) {

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

1265 if (NumCycles > 1)

1266 TCycle += NumCycles - 1;

1268 }

1269 for (MachineInstr &I : *IfConv.FBB) {

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

1271 if (NumCycles > 1)

1272 FCycle += NumCycles - 1;

1274 }

1276 FCycle, FExtra, TrueProbability);

1277}

1278

1279

1280

1281bool EarlyIfPredicator::tryConvertIf(MachineBasicBlock *MBB) {

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

1284

1285 SmallVector<MachineBasicBlock *, 4> RemoveBlocks;

1286 IfConv.convertIf(RemoveBlocks, true);

1288 updateDomTree(DomTree, IfConv, RemoveBlocks);

1289 for (MachineBasicBlock *MBB : RemoveBlocks)

1291 updateLoops(Loops, RemoveBlocks);

1292 }

1294}

1295

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

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

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

1300 return false;

1301

1302 const TargetSubtargetInfo &STI = MF.getSubtarget();

1306 SchedModel.init(&STI);

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

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

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

1310

1312 IfConv.init(MF);

1313

1314

1315

1316

1317

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

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

1321

1323}

unsigned const MachineRegisterInfo * MRI

MachineInstrBuilder MachineInstrBuilder & DefMI

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

const TargetInstrInfo & TII

This file implements the BitVector class.

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

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

static unsigned InstrCount

This file defines the DenseSet and SmallDenseSet classes.

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

Definition EarlyIfConversion.cpp:572

static unsigned adjCycles(unsigned Cyc, int Delta)

Definition EarlyIfConversion.cpp:900

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

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.

const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB

const SmallVectorImpl< MachineOperand > & Cond

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)

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.

bool test(unsigned Idx) const

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)

Definition EarlyIfConversion.cpp:1159

const MCInstrDesc & get(unsigned Opcode) const

Return the machine instruction descriptor that corresponds to the specified instruction opcode.

const MCSchedModel & getSchedModel() const

Get the machine model for this subtarget's CPU.

unsigned pred_size() const

LLVM_ABI 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

LLVM_ABI iterator getFirstTerminator()

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

unsigned succ_size() const

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

Add Succ as a successor of this MachineBasicBlock.

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

Remove successor from the successors list of this MachineBasicBlock.

LLVM_ABI DebugLoc findDebugLoc(instr_iterator MBBI)

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

LLVM_ABI bool isLayoutSuccessor(const MachineBasicBlock *MBB) const

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

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

MachineInstrBundleIterator< MachineInstr > iterator

LLVM_ABI void moveAfter(MachineBasicBlock *NewBefore)

BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const

Analysis pass which computes a MachineDominatorTree.

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

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

const TargetSubtargetInfo & getSubtarget() const

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

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

LLVM_ABI bool isDereferenceableInvariantLoad() const

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

LLVM_ABI bool hasUnmodeledSideEffects() const

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

mop_range uses()

Returns all operands which may be register uses.

const DebugLoc & getDebugLoc() const

Returns the debug location id of this MachineInstr.

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

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.

void verifyAnalysis() const

void invalidate(const MachineBasicBlock *MBB)

Invalidate cached information about MBB.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Wrapper class representing virtual and physical registers.

MCRegister asMCReg() const

Utility to check-convert this value to a MCRegister.

constexpr bool isVirtual() const

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

constexpr bool isPhysical() const

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

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.

void push_back(const T &Elt)

iterator erase(iterator I)

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

void clear()

clear - Clears the set.

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

insert - Attempts to insert a new element.

bool empty() const

empty - Returns true if the set is empty.

TargetInstrInfo - Interface to description of machine instruction set.

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

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

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

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

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

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

virtual bool canPredicatePredicatedInstr(const MachineInstr &MI) const

Assumes the instruction is already predicated and returns true if the instruction can be predicated a...

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

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

virtual bool PredicateInstruction(MachineInstr &MI, ArrayRef< MachineOperand > Pred) const

Convert the instruction into a predicated instruction.

virtual void insertSelect(MachineBasicBlock &MBB, MachineBasicBlock::iterator I, const DebugLoc &DL, Register DstReg, ArrayRef< MachineOperand > Cond, Register TrueReg, Register FalseReg) const

Insert a select instruction into MBB before I that will copy TrueReg to DstReg when Cond is true,...

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

Insert branch code into the end of the specified MachineBasicBlock.

virtual bool isPredicated(const MachineInstr &MI) const

Returns true if the instruction is already predicated.

virtual unsigned getPredicationCost(const MachineInstr &MI) const

virtual bool isPredicable(const MachineInstr &MI) const

Return true if the specified instruction can be predicated.

virtual bool canInsertSelect(const MachineBasicBlock &MBB, ArrayRef< MachineOperand > Cond, Register DstReg, Register TrueReg, Register FalseReg, int &CondCycles, int &TrueCycles, int &FalseCycles) const

Return true if it is possible to insert a select instruction that chooses between TrueReg and FalseRe...

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

Provide an instruction scheduling machine model to CodeGen passes.

LLVM_ABI void init(const TargetSubtargetInfo *TSInfo, bool EnableSModel=true, bool EnableSItins=true)

Initialize the machine model for instruction scheduling.

virtual const TargetInstrInfo * getInstrInfo() const

virtual const TargetRegisterInfo * getRegisterInfo() const =0

Return the target's register information.

virtual bool enableEarlyIfConversion() const

Enable the use of the early if conversion pass.

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

bool contains(const_arg_type_t< ValueT > V) const

Check if the set contains the given element.

unsigned ID

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

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

initializer< Ty > init(const Ty &Val)

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

DiagnosticInfoOptimizationBase::Argument NV

NodeAddr< NodeBase * > Node

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

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.

LLVM_ABI Printable printRegUnit(MCRegUnit 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)

AnalysisManager< MachineFunction > MachineFunctionAnalysisManager

LLVM_ABI char & EarlyIfConverterLegacyID

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

Definition EarlyIfConversion.cpp:839

LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()

Returns the minimum set of Analyses that all machine function passes must preserve.

bool any_of(R &&range, UnaryPredicate P)

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

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

LLVM_ABI char & EarlyIfPredicatorID

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

Definition EarlyIfConversion.cpp:1222

DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode

LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key

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

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

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

unsigned Depth

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