IfConversion.cpp Source File (original) (raw)

47#include

48#include

49#include

50#include

51#include

52#include

53#include

55using namespace llvm;

57#define DEBUG_TYPE "if-converter"

80 STATISTIC(NumSimple, "Number of simple if-conversions performed");

81 STATISTIC(NumSimpleFalse, "Number of simple (F) if-conversions performed");

82 STATISTIC(NumTriangle, "Number of triangle if-conversions performed");

83 STATISTIC(NumTriangleRev, "Number of triangle (R) if-conversions performed");

84 STATISTIC(NumTriangleFalse,"Number of triangle (F) if-conversions performed");

85 STATISTIC(NumTriangleFRev, "Number of triangle (F/R) if-conversions performed");

86 STATISTIC(NumDiamonds, "Number of diamond if-conversions performed");

87 STATISTIC(NumForkedDiamonds, "Number of forked-diamond if-conversions performed");

88 STATISTIC(NumIfConvBBs, "Number of if-converted blocks");

89 STATISTIC(NumDupBBs, "Number of duplicated blocks");

90 STATISTIC(NumUnpred, "Number of true blocks of diamonds unpredicated");

92namespace {

95 enum IfcvtKind {

96 ICNotClassfied,

97 ICSimpleFalse,

98 ICSimple,

99 ICTriangleFRev,

100 ICTriangleRev,

101 ICTriangleFalse,

102 ICTriangle,

103 ICDiamond,

104 ICForkedDiamond

105

106 };

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138 struct BBInfo {

139 bool IsDone : 1;

140 bool IsBeingAnalyzed : 1;

141 bool IsAnalyzed : 1;

142 bool IsEnqueued : 1;

143 bool IsBrAnalyzable : 1;

144 bool IsBrReversible : 1;

145 bool HasFallThrough : 1;

146 bool IsUnpredicable : 1;

147 bool CannotBeCopied : 1;

148 bool ClobbersPred : 1;

149 unsigned NonPredSize = 0;

150 unsigned ExtraCost = 0;

151 unsigned ExtraCost2 = 0;

152 MachineBasicBlock *BB = nullptr;

153 MachineBasicBlock *TrueBB = nullptr;

154 MachineBasicBlock *FalseBB = nullptr;

157

158 BBInfo() : IsDone(false), IsBeingAnalyzed(false),

159 IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false),

160 IsBrReversible(false), HasFallThrough(false),

161 IsUnpredicable(false), CannotBeCopied(false),

162 ClobbersPred(false) {}

163 };

164

165

166

167

168

169

170

171

172

173

174

175

176 struct IfcvtToken {

177 BBInfo &BBI;

178 IfcvtKind Kind;

179 unsigned NumDups;

180 unsigned NumDups2;

181 bool NeedSubsumption : 1;

182 bool TClobbersPred : 1;

183 bool FClobbersPred : 1;

184

185 IfcvtToken(BBInfo &b, IfcvtKind k, bool s, unsigned d, unsigned d2 = 0,

186 bool tc = false, bool fc = false)

187 : BBI(b), Kind(k), NumDups(d), NumDups2(d2), NeedSubsumption(s),

188 TClobbersPred(tc), FClobbersPred(fc) {}

189 };

190

191

192

193 std::vector BBAnalysis;

194 TargetSchedModel SchedModel;

195

196 const TargetLoweringBase *TLI = nullptr;

197 const TargetInstrInfo *TII = nullptr;

198 const TargetRegisterInfo *TRI = nullptr;

199 const MachineBranchProbabilityInfo *MBPI = nullptr;

200 MachineRegisterInfo *MRI = nullptr;

201

202 LivePhysRegs Redefs;

203

204 bool PreRegAlloc = true;

205 bool MadeChange = false;

206 int FnNum = -1;

207 std::function<bool(const MachineFunction &)> PredicateFtor;

208

209 public:

210 static char ID;

211

212 IfConverter(std::function<bool(const MachineFunction &)> Ftor = nullptr)

213 : MachineFunctionPass(ID), PredicateFtor(std::move(Ftor)) {

215 }

216

217 void getAnalysisUsage(AnalysisUsage &AU) const override {

218 AU.addRequired();

219 AU.addRequired();

220 AU.addRequired();

222 }

223

224 bool runOnMachineFunction(MachineFunction &MF) override;

225

226 MachineFunctionProperties getRequiredProperties() const override {

227 return MachineFunctionProperties().setNoVRegs();

228 }

229

230 private:

231 bool reverseBranchCondition(BBInfo &BBI) const;

232 bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups,

233 BranchProbability Prediction) const;

234 bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,

235 bool FalseBranch, unsigned &Dups,

236 BranchProbability Prediction) const;

237 bool CountDuplicatedInstructions(

240 unsigned &Dups1, unsigned &Dups2,

241 MachineBasicBlock &TBB, MachineBasicBlock &FBB,

242 bool SkipUnconditionalBranches) const;

243 bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,

244 unsigned &Dups1, unsigned &Dups2,

245 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const;

246 bool ValidForkedDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,

247 unsigned &Dups1, unsigned &Dups2,

248 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const;

249 void AnalyzeBranches(BBInfo &BBI);

250 void ScanInstructions(BBInfo &BBI,

253 bool BranchUnpredicable = false) const;

254 bool RescanInstructions(

257 BBInfo &TrueBBI, BBInfo &FalseBBI) const;

258 void AnalyzeBlock(MachineBasicBlock &MBB,

259 std::vector<std::unique_ptr> &Tokens);

260 bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl &Pred,

261 bool isTriangle = false, bool RevBranch = false,

262 bool hasCommonTail = false);

263 void AnalyzeBlocks(MachineFunction &MF,

264 std::vector<std::unique_ptr> &Tokens);

265 void InvalidatePreds(MachineBasicBlock &MBB);

266 bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind);

267 bool IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind);

268 bool IfConvertDiamondCommon(BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,

269 unsigned NumDups1, unsigned NumDups2,

270 bool TClobbersPred, bool FClobbersPred,

271 bool RemoveBranch, bool MergeAddEdges);

272 bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,

273 unsigned NumDups1, unsigned NumDups2,

274 bool TClobbers, bool FClobbers);

275 bool IfConvertForkedDiamond(BBInfo &BBI, IfcvtKind Kind,

276 unsigned NumDups1, unsigned NumDups2,

277 bool TClobbers, bool FClobbers);

279 SmallVectorImpl &Cond,

280 SmallSet<MCRegister, 4> *LaterRedefs = nullptr);

281 void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,

282 SmallVectorImpl &Cond,

283 bool IgnoreBr = false);

284 void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges = true);

285

286 bool MeetIfcvtSizeLimit(MachineBasicBlock &BB,

287 unsigned Cycle, unsigned Extra,

288 BranchProbability Prediction) const {

289 return Cycle > 0 && TII->isProfitableToIfCvt(BB, Cycle, Extra,

290 Prediction);

291 }

292

293 bool MeetIfcvtSizeLimit(BBInfo &TBBInfo, BBInfo &FBBInfo,

294 MachineBasicBlock &CommBB, unsigned Dups,

295 BranchProbability Prediction, bool Forked) const {

296 const MachineFunction &MF = *TBBInfo.BB->getParent();

302

303 unsigned Dups1 = 0, Dups2 = 0;

304 if (!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,

305 *TBBInfo.BB, *FBBInfo.BB,

306 true))

307 llvm_unreachable("should already have been checked by ValidDiamond");

308

309 unsigned BranchBytes = 0;

310 unsigned CommonBytes = 0;

311

312

313 for (auto &I : make_range(TBBInfo.BB->begin(), TIB)) {

315 CommonBytes += TII->getInstSizeInBytes(I);

316 }

317 for (auto &I : make_range(FBBInfo.BB->begin(), FIB)) {

319 CommonBytes += TII->getInstSizeInBytes(I);

320 }

321

322

323

324

325

326 for (auto &I : make_range(TIE, TBBInfo.BB->end())) {

327 if (I.isBranch() && TBBInfo.IsBrAnalyzable && !Forked) {

329 BranchBytes += TII->predictBranchSizeForIfCvt(I);

330 } else {

332 CommonBytes += TII->getInstSizeInBytes(I);

333 }

334 }

335 for (auto &I : make_range(FIE, FBBInfo.BB->end())) {

336 if (I.isBranch() && FBBInfo.IsBrAnalyzable && !Forked) {

338 BranchBytes += TII->predictBranchSizeForIfCvt(I);

339 } else {

341 CommonBytes += TII->getInstSizeInBytes(I);

342 }

343 }

345 if (I.isBranch()) {

347 BranchBytes += TII->predictBranchSizeForIfCvt(I);

348 }

349 }

350

351

352

353 CommonBytes /= 2;

354

355

356 unsigned NumPredicatedInstructions = 0;

358 if (.isDebugInstr()) {

360 NumPredicatedInstructions++;

361 }

362 }

364 if (.isDebugInstr()) {

366 NumPredicatedInstructions++;

367 }

368 }

369

370

371

372 if (NumPredicatedInstructions > 15)

373 return false;

374

375

376

377 unsigned ExtraPredicateBytes = TII->extraSizeToPredicateInstructions(

378 MF, NumPredicatedInstructions);

379

380 LLVM_DEBUG(dbgs() << "MeetIfcvtSizeLimit(BranchBytes=" << BranchBytes

381 << ", CommonBytes=" << CommonBytes

382 << ", NumPredicatedInstructions="

383 << NumPredicatedInstructions

384 << ", ExtraPredicateBytes=" << ExtraPredicateBytes

385 << ")\n");

386 return (BranchBytes + CommonBytes) > ExtraPredicateBytes;

387 } else {

388 unsigned TCycle = TBBInfo.NonPredSize + TBBInfo.ExtraCost - Dups;

389 unsigned FCycle = FBBInfo.NonPredSize + FBBInfo.ExtraCost - Dups;

390 bool Res = TCycle > 0 && FCycle > 0 &&

391 TII->isProfitableToIfCvt(

392 *TBBInfo.BB, TCycle, TBBInfo.ExtraCost2, *FBBInfo.BB,

393 FCycle, FBBInfo.ExtraCost2, Prediction);

394 LLVM_DEBUG(dbgs() << "MeetIfcvtSizeLimit(TCycle=" << TCycle

395 << ", FCycle=" << FCycle

396 << ", TExtra=" << TBBInfo.ExtraCost2 << ", FExtra="

397 << FBBInfo.ExtraCost2 << ") = " << Res << "\n");

398 return Res;

399 }

400 }

401

402

403 bool blockAlwaysFallThrough(BBInfo &BBI) const {

404 return BBI.IsBrAnalyzable && BBI.TrueBB == nullptr;

405 }

406

407

408 bool blockNeverFallThrough(BBInfo &BBI) const {

409

410 if (BBI.IsBrAnalyzable)

411 return !BBI.HasFallThrough;

412

413

416 if (I == BBI.BB->getParent()->end() || !PI->isSuccessor(&*I))

417 return true;

418

419 return false;

420 }

421

422

423 static bool IfcvtTokenCmp(const std::unique_ptr &C1,

424 const std::unique_ptr &C2) {

425 int Incr1 = (C1->Kind == ICDiamond)

426 ? -(int)(C1->NumDups + C1->NumDups2) : (int)C1->NumDups;

427 int Incr2 = (C2->Kind == ICDiamond)

428 ? -(int)(C2->NumDups + C2->NumDups2) : (int)C2->NumDups;

429 if (Incr1 > Incr2)

430 return true;

431 else if (Incr1 == Incr2) {

432

433 if (!C1->NeedSubsumption && C2->NeedSubsumption)

434 return true;

435 else if (C1->NeedSubsumption == C2->NeedSubsumption) {

436

437 if ((unsigned)C1->Kind < (unsigned)C2->Kind)

438 return true;

439 else if (C1->Kind == C2->Kind)

440 return C1->BBI.BB->getNumber() < C2->BBI.BB->getNumber();

441 }

442 }

443 return false;

444 }

445 };

446

447}

448

449char IfConverter::ID = 0;

450

452

457

458bool IfConverter::runOnMachineFunction(MachineFunction &MF) {

459 if (skipFunction(MF.getFunction()) || (PredicateFtor && !PredicateFtor(MF)))

460 return false;

461

463 TLI = ST.getTargetLowering();

464 TII = ST.getInstrInfo();

465 TRI = ST.getRegisterInfo();

467 getAnalysis().getMBFI());

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

470 &getAnalysis().getPSI();

471 MRI = &MF.getRegInfo();

472 SchedModel.init(&ST);

473

474 if ( TII ) return false;

475

476 PreRegAlloc = MRI->isSSA();

477

478 bool BFChange = false;

479 if (!PreRegAlloc) {

480

481 BranchFolder BF(true, false, MBFI, *MBPI, PSI);

483 }

484

485 LLVM_DEBUG(dbgs() << "\nIfcvt: function (" << ++FnNum << ") \'"

486 << MF.getName() << "\'");

487

490 return false;

491 }

493

494 MF.RenumberBlocks();

495 BBAnalysis.resize(MF.getNumBlockIDs());

496

497 std::vector<std::unique_ptr> Tokens;

498 MadeChange = false;

499 unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle +

500 NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds;

502

503

504 bool Change = false;

505 AnalyzeBlocks(MF, Tokens);

506 while (!Tokens.empty()) {

507 std::unique_ptr Token = std::move(Tokens.back());

508 Tokens.pop_back();

509 BBInfo &BBI = Token->BBI;

510 IfcvtKind Kind = Token->Kind;

511 unsigned NumDups = Token->NumDups;

512 unsigned NumDups2 = Token->NumDups2;

513

514

515

516 if (BBI.IsDone)

517 BBI.IsEnqueued = false;

518 if (!BBI.IsEnqueued)

519 continue;

520

521 BBI.IsEnqueued = false;

522

523 bool RetVal = false;

524 switch (Kind) {

526 case ICSimple:

527 case ICSimpleFalse: {

528 bool isFalse = Kind == ICSimpleFalse;

531 << (Kind == ICSimpleFalse ? " false" : "")

533 << ((Kind == ICSimpleFalse) ? BBI.FalseBB->getNumber()

534 : BBI.TrueBB->getNumber())

535 << ") ");

536 RetVal = IfConvertSimple(BBI, Kind);

537 LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");

538 if (RetVal) {

539 if (isFalse) ++NumSimpleFalse;

540 else ++NumSimple;

541 }

542 break;

543 }

544 case ICTriangle:

545 case ICTriangleRev:

546 case ICTriangleFalse:

547 case ICTriangleFRev: {

548 bool isFalse = Kind == ICTriangleFalse;

549 bool isRev = (Kind == ICTriangleRev || Kind == ICTriangleFRev);

554 if (isFalse)

556 if (isRev)

559 << " (T:" << BBI.TrueBB->getNumber()

560 << ",F:" << BBI.FalseBB->getNumber() << ") ");

561 RetVal = IfConvertTriangle(BBI, Kind);

562 LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");

563 if (RetVal) {

564 if (isFalse)

565 ++NumTriangleFalse;

566 else if (isRev)

567 ++NumTriangleRev;

568 else

569 ++NumTriangle;

570 }

571 break;

572 }

573 case ICDiamond:

576 << " (T:" << BBI.TrueBB->getNumber()

577 << ",F:" << BBI.FalseBB->getNumber() << ") ");

578 RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2,

579 Token->TClobbersPred,

580 Token->FClobbersPred);

581 LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");

582 if (RetVal) ++NumDiamonds;

583 break;

584 case ICForkedDiamond:

588 << " (T:" << BBI.TrueBB->getNumber()

589 << ",F:" << BBI.FalseBB->getNumber() << ") ");

590 RetVal = IfConvertForkedDiamond(BBI, Kind, NumDups, NumDups2,

591 Token->TClobbersPred,

592 Token->FClobbersPred);

593 LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");

594 if (RetVal) ++NumForkedDiamonds;

595 break;

596 }

597

598 if (RetVal && MRI->tracksLiveness())

600

601 Change |= RetVal;

602

603 NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev +

604 NumTriangleFalse + NumTriangleFRev + NumDiamonds;

606 break;

607 }

608

609 if (!Change)

610 break;

611 MadeChange |= Change;

612 }

613

614 Tokens.clear();

615 BBAnalysis.clear();

616

618 BranchFolder BF(false, false, MBFI, *MBPI, PSI);

620 }

621

622 MadeChange |= BFChange;

623 return MadeChange;

624}

625

626

630 if (SuccBB != TrueBB)

631 return SuccBB;

632 }

633 return nullptr;

634}

635

636

637

638bool IfConverter::reverseBranchCondition(BBInfo &BBI) const {

639 DebugLoc dl;

642 TII->insertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond, dl);

643 std::swap(BBI.TrueBB, BBI.FalseBB);

644 return true;

645 }

646 return false;

647}

648

649

650

654 if (++I == E)

655 return nullptr;

656 return &*I;

657}

658

659

660

661

662bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups,

663 BranchProbability Prediction) const {

664 Dups = 0;

665 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)

666 return false;

667

668 if (TrueBBI.IsBrAnalyzable)

669 return false;

670

671 if (TrueBBI.BB->pred_size() > 1) {

672 if (TrueBBI.CannotBeCopied ||

674 Prediction))

675 return false;

676 Dups = TrueBBI.NonPredSize;

677 }

678

679 return true;

680}

681

682

683

684

685

686

687bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,

688 bool FalseBranch, unsigned &Dups,

689 BranchProbability Prediction) const {

690 Dups = 0;

691 if (TrueBBI.BB == FalseBBI.BB)

692 return false;

693

694 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)

695 return false;

696

697 if (TrueBBI.BB->pred_size() > 1) {

698 if (TrueBBI.CannotBeCopied)

699 return false;

700

701 unsigned Size = TrueBBI.NonPredSize;

702 if (TrueBBI.IsBrAnalyzable) {

703 if (TrueBBI.TrueBB && TrueBBI.BrCond.empty())

704

706 else {

707 MachineBasicBlock *FExit = FalseBranch

708 ? TrueBBI.TrueBB : TrueBBI.FalseBB;

709 if (FExit)

710

712 }

713 }

715 return false;

717 }

718

719 MachineBasicBlock *TExit = FalseBranch ? TrueBBI.FalseBB : TrueBBI.TrueBB;

720 if (!TExit && blockAlwaysFallThrough(TrueBBI)) {

722 if (++I == TrueBBI.BB->getParent()->end())

723 return false;

724 TExit = &*I;

725 }

726 return TExit && TExit == FalseBBI.BB;

727}

728

729

730

731

732

733

734

735

736

737

738

739

740

741

742

743

744

745

746

747

748

749bool IfConverter::CountDuplicatedInstructions(

754 unsigned &Dups1, unsigned &Dups2,

755 MachineBasicBlock &TBB, MachineBasicBlock &FBB,

756 bool SkipUnconditionalBranches) const {

757 while (TIB != TIE && FIB != FIE) {

758

761 if (TIB == TIE || FIB == FIE)

762 break;

763 if (!TIB->isIdenticalTo(*FIB))

764 break;

765

766

767 std::vector PredDefs;

769 return false;

770

771 if (!TIB->isBranch())

772 ++Dups1;

773 ++TIB;

774 ++FIB;

775 }

776

777

778 if (TIB == TIE || FIB == FIE)

779 return true;

780

781

782

783

788

790 if (SkipUnconditionalBranches) {

791 while (RTIE != RTIB && RTIE->isUnconditionalBranch())

792 ++RTIE;

793 while (RFIE != RFIB && RFIE->isUnconditionalBranch())

794 ++RFIE;

795 }

796 }

797

798

799 while (RTIE != RTIB && RFIE != RFIB) {

800

801

804 if (RTIE == RTIB || RFIE == RFIB)

805 break;

806 if (!RTIE->isIdenticalTo(*RFIE))

807 break;

808

809

810 if (!RTIE->isBranch())

811 ++Dups2;

812 ++RTIE;

813 ++RFIE;

814 }

817 return true;

818}

819

820

821

822

823

824

825

826

827

828

829bool IfConverter::RescanInstructions(

832 BBInfo &TrueBBI, BBInfo &FalseBBI) const {

833 bool BranchUnpredicable = true;

834 TrueBBI.IsUnpredicable = FalseBBI.IsUnpredicable = false;

835 ScanInstructions(TrueBBI, TIB, TIE, BranchUnpredicable);

836 if (TrueBBI.IsUnpredicable)

837 return false;

838 ScanInstructions(FalseBBI, FIB, FIE, BranchUnpredicable);

839 if (FalseBBI.IsUnpredicable)

840 return false;

841 if (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred)

842 return false;

843 return true;

844}

845

846#ifndef NDEBUG

854 while (E1 != B1 && E2 != B2) {

857 if (E1 == B1 && E2 == B2)

858 break;

859

860 if (E1 == B1) {

861 assert(!E2->isBranch() && "Branch mis-match, one block is empty.");

862 break;

863 }

864 if (E2 == B2) {

865 assert(!E1->isBranch() && "Branch mis-match, one block is empty.");

866 break;

867 }

868

869 if (E1->isBranch() || E2->isBranch())

870 assert(E1->isIdenticalTo(*E2) &&

871 "Branch mis-match, branch instructions don't match.");

872 else

873 break;

874 ++E1;

875 ++E2;

876 }

877}

878#endif

879

880

881

882

883

884

885

886

887

888

889

890

891

892

893bool IfConverter::ValidForkedDiamond(

894 BBInfo &TrueBBI, BBInfo &FalseBBI,

895 unsigned &Dups1, unsigned &Dups2,

896 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const {

897 Dups1 = Dups2 = 0;

898 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||

899 FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)

900 return false;

901

902 if (!TrueBBI.IsBrAnalyzable || !FalseBBI.IsBrAnalyzable)

903 return false;

904

905 if (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)

906 return false;

907

908

909

910 if (TrueBBI.BrCond.size() == 0 ||

911 FalseBBI.BrCond.size() == 0)

912 return false;

913

914 MachineBasicBlock *TT = TrueBBI.TrueBB;

915 MachineBasicBlock *TF = TrueBBI.FalseBB;

916 MachineBasicBlock *FT = FalseBBI.TrueBB;

917 MachineBasicBlock *FF = FalseBBI.FalseBB;

918

919 if (!TT)

921 if (!TF)

923 if (!FT)

925 if (!FF)

927

928 if (!TT || !TF)

929 return false;

930

931

932 if (!((TT == FT && TF == FF) || (TF == FT && TT == FF)))

933 return false;

934

935 bool FalseReversed = false;

936 if (TF == FT && TT == FF) {

937

938 if (!FalseBBI.IsBrReversible)

939 return false;

940 FalseReversed = true;

941 reverseBranchCondition(FalseBBI);

942 }

944 if (FalseReversed)

945 reverseBranchCondition(FalseBBI);

946 });

947

948

953 if(!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,

954 *TrueBBI.BB, *FalseBBI.BB,

955 true))

956 return false;

957

958 TrueBBICalc.BB = TrueBBI.BB;

959 FalseBBICalc.BB = FalseBBI.BB;

960 TrueBBICalc.IsBrAnalyzable = TrueBBI.IsBrAnalyzable;

961 FalseBBICalc.IsBrAnalyzable = FalseBBI.IsBrAnalyzable;

962 if (!RescanInstructions(TIB, FIB, TIE, FIE, TrueBBICalc, FalseBBICalc))

963 return false;

964

965

966

967

968 TrueBBICalc.NonPredSize = TrueBBI.NonPredSize;

969 FalseBBICalc.NonPredSize = FalseBBI.NonPredSize;

970 return true;

971}

972

973

974

975bool IfConverter::ValidDiamond(

976 BBInfo &TrueBBI, BBInfo &FalseBBI,

977 unsigned &Dups1, unsigned &Dups2,

978 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const {

979 Dups1 = Dups2 = 0;

980 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||

981 FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)

982 return false;

983

984

985

986 if (TrueBBI.BB == FalseBBI.BB)

987 return false;

988

989 MachineBasicBlock *TT = TrueBBI.TrueBB;

990 MachineBasicBlock *FT = FalseBBI.TrueBB;

991

992 if (!TT && blockAlwaysFallThrough(TrueBBI))

994 if (!FT && blockAlwaysFallThrough(FalseBBI))

996 if (TT != FT)

997 return false;

998 if (!TT && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))

999 return false;

1000 if (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)

1001 return false;

1002

1003

1004 if (TrueBBI.FalseBB || FalseBBI.FalseBB)

1005 return false;

1006

1007

1008

1009

1010

1011 bool SkipUnconditionalBranches =

1012 TrueBBI.IsBrAnalyzable && FalseBBI.IsBrAnalyzable;

1017 if(!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,

1018 *TrueBBI.BB, *FalseBBI.BB,

1019 SkipUnconditionalBranches))

1020 return false;

1021

1022 TrueBBICalc.BB = TrueBBI.BB;

1023 FalseBBICalc.BB = FalseBBI.BB;

1024 TrueBBICalc.IsBrAnalyzable = TrueBBI.IsBrAnalyzable;

1025 FalseBBICalc.IsBrAnalyzable = FalseBBI.IsBrAnalyzable;

1026 if (!RescanInstructions(TIB, FIB, TIE, FIE, TrueBBICalc, FalseBBICalc))

1027 return false;

1028

1029

1030

1031 TrueBBICalc.NonPredSize = TrueBBI.NonPredSize;

1032 FalseBBICalc.NonPredSize = FalseBBI.NonPredSize;

1033 return true;

1034}

1035

1036

1037

1038void IfConverter::AnalyzeBranches(BBInfo &BBI) {

1039 if (BBI.IsDone)

1040 return;

1041

1042 BBI.TrueBB = BBI.FalseBB = nullptr;

1043 BBI.BrCond.clear();

1044 BBI.IsBrAnalyzable =

1045 TII ->analyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);

1046 if (!BBI.IsBrAnalyzable) {

1047 BBI.TrueBB = nullptr;

1048 BBI.FalseBB = nullptr;

1049 BBI.BrCond.clear();

1050 }

1051

1053 BBI.IsBrReversible = (RevCond.size() == 0) ||

1055 BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB == nullptr;

1056

1057 if (BBI.BrCond.size()) {

1058

1059

1060 if (!BBI.FalseBB)

1062 if (!BBI.FalseBB) {

1063

1064 BBI.IsUnpredicable = true;

1065 }

1066 }

1067}

1068

1069

1070

1071

1072

1073

1074void IfConverter::ScanInstructions(BBInfo &BBI,

1077 bool BranchUnpredicable) const {

1078 if (BBI.IsDone || BBI.IsUnpredicable)

1079 return;

1080

1081 bool AlreadyPredicated = !BBI.Predicate.empty();

1082

1083 BBI.NonPredSize = 0;

1084 BBI.ExtraCost = 0;

1085 BBI.ExtraCost2 = 0;

1086 BBI.ClobbersPred = false;

1087 for (MachineInstr &MI : make_range(Begin, End)) {

1088 if (MI.isDebugInstr())

1089 continue;

1090

1091

1092

1093

1094

1095

1096

1097

1098

1099

1100

1101

1102

1103

1104

1105

1106

1107

1108

1109

1110

1111

1112

1113

1114

1115

1116

1117

1118

1119

1120

1121 if (MI.isNotDuplicable() || MI.isConvergent())

1122 BBI.CannotBeCopied = true;

1123

1125 bool isCondBr = BBI.IsBrAnalyzable && MI.isConditionalBranch();

1126

1127 if (BranchUnpredicable && MI.isBranch()) {

1128 BBI.IsUnpredicable = true;

1129 return;

1130 }

1131

1132

1133 if (isCondBr)

1134 continue;

1135

1136 if (!isPredicated) {

1137 BBI.NonPredSize++;

1139 unsigned NumCycles = SchedModel.computeInstrLatency(&MI, false);

1140 if (NumCycles > 1)

1141 BBI.ExtraCost += NumCycles-1;

1142 BBI.ExtraCost2 += ExtraPredCost;

1143 } else if (!AlreadyPredicated) {

1144

1145

1146

1147 BBI.IsUnpredicable = true;

1148 return;

1149 }

1150

1151 if (BBI.ClobbersPred && !isPredicated) {

1152

1153

1154

1155

1156 BBI.IsUnpredicable = true;

1157 return;

1158 }

1159

1160

1161

1162 std::vector PredDefs;

1164 BBI.ClobbersPred = true;

1165

1167 BBI.IsUnpredicable = true;

1168 return;

1169 }

1170 }

1171}

1172

1173

1174

1175

1176

1177

1178

1179

1180

1181

1182bool IfConverter::FeasibilityAnalysis(BBInfo &BBI,

1183 SmallVectorImpl &Pred,

1184 bool isTriangle, bool RevBranch,

1185 bool hasCommonTail) {

1186

1187

1188

1189

1190 if (BBI.IsDone || (BBI.IsUnpredicable && !hasCommonTail))

1191 return false;

1192

1193

1194

1195

1196 if (BBI.Predicate.size() && !BBI.IsBrAnalyzable)

1197 return false;

1198

1199

1200

1202 return false;

1203

1204 if (!hasCommonTail && BBI.BrCond.size()) {

1205 if (!isTriangle)

1206 return false;

1207

1208

1211 if (RevBranch) {

1213 return false;

1214 }

1217 return false;

1218 }

1219

1220 return true;

1221}

1222

1223

1224

1225void IfConverter::AnalyzeBlock(

1226 MachineBasicBlock &MBB, std::vector<std::unique_ptr> &Tokens) {

1227 struct BBState {

1228 BBState(MachineBasicBlock &MBB) : MBB(&MBB) {}

1229 MachineBasicBlock *MBB;

1230

1231

1232 bool SuccsAnalyzed = false;

1233 };

1234

1235

1237

1238 while (!BBStack.empty()) {

1239 BBState &State = BBStack.back();

1240 MachineBasicBlock *BB = State.MBB;

1241 BBInfo &BBI = BBAnalysis[BB->getNumber()];

1242

1243 if (!State.SuccsAnalyzed) {

1244 if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed) {

1245 BBStack.pop_back();

1246 continue;

1247 }

1248

1249 BBI.BB = BB;

1250 BBI.IsBeingAnalyzed = true;

1251

1252 AnalyzeBranches(BBI);

1255 ScanInstructions(BBI, Begin, End);

1256

1257

1258

1259 if (!BBI.IsBrAnalyzable || BBI.BrCond.empty() || BBI.IsDone) {

1260 BBI.IsBeingAnalyzed = false;

1261 BBI.IsAnalyzed = true;

1262 BBStack.pop_back();

1263 continue;

1264 }

1265

1266

1267 if (BBI.TrueBB == BB || BBI.FalseBB == BB) {

1268 BBI.IsBeingAnalyzed = false;

1269 BBI.IsAnalyzed = true;

1270 BBStack.pop_back();

1271 continue;

1272 }

1273

1274

1275 if (!BBI.FalseBB) {

1276 BBI.IsBeingAnalyzed = false;

1277 BBI.IsAnalyzed = true;

1278 BBStack.pop_back();

1279 continue;

1280 }

1281

1282

1283 State.SuccsAnalyzed = true;

1284 BBStack.push_back(*BBI.FalseBB);

1285 BBStack.push_back(*BBI.TrueBB);

1286 continue;

1287 }

1288

1289 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];

1290 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];

1291

1292 if (TrueBBI.IsDone && FalseBBI.IsDone) {

1293 BBI.IsBeingAnalyzed = false;

1294 BBI.IsAnalyzed = true;

1295 BBStack.pop_back();

1296 continue;

1297 }

1298

1300 RevCond(BBI.BrCond.begin(), BBI.BrCond.end());

1302

1303 unsigned Dups = 0;

1304 unsigned Dups2 = 0;

1305 bool TNeedSub = !TrueBBI.Predicate.empty();

1306 bool FNeedSub = !FalseBBI.Predicate.empty();

1307 bool Enqueued = false;

1308

1309 BranchProbability Prediction = MBPI->getEdgeProbability(BB, TrueBBI.BB);

1310

1311 if (CanRevCond) {

1312 BBInfo TrueBBICalc, FalseBBICalc;

1313 auto feasibleDiamond = [&](bool Forked) {

1314 bool MeetsSize = MeetIfcvtSizeLimit(TrueBBICalc, FalseBBICalc, *BB,

1315 Dups + Dups2, Prediction, Forked);

1316 bool TrueFeasible = FeasibilityAnalysis(TrueBBI, BBI.BrCond,

1317 false, false,

1318 true);

1319 bool FalseFeasible = FeasibilityAnalysis(FalseBBI, RevCond,

1320 false, false,

1321 true);

1322 return MeetsSize && TrueFeasible && FalseFeasible;

1323 };

1324

1325 if (ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2,

1326 TrueBBICalc, FalseBBICalc)) {

1327 if (feasibleDiamond(false)) {

1328

1329

1330

1331

1332

1333

1334

1335

1336 Tokens.push_back(std::make_unique(

1337 BBI, ICDiamond, TNeedSub | FNeedSub, Dups, Dups2,

1338 (bool) TrueBBICalc.ClobbersPred, (bool) FalseBBICalc.ClobbersPred));

1339 Enqueued = true;

1340 }

1341 } else if (ValidForkedDiamond(TrueBBI, FalseBBI, Dups, Dups2,

1342 TrueBBICalc, FalseBBICalc)) {

1343 if (feasibleDiamond(true)) {

1344

1345

1346

1347

1348

1349

1350

1351

1352

1353

1354 Tokens.push_back(std::make_unique(

1355 BBI, ICForkedDiamond, TNeedSub | FNeedSub, Dups, Dups2,

1356 (bool) TrueBBICalc.ClobbersPred, (bool) FalseBBICalc.ClobbersPred));

1357 Enqueued = true;

1358 }

1359 }

1360 }

1361

1362 if (ValidTriangle(TrueBBI, FalseBBI, false, Dups, Prediction) &&

1363 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,

1364 TrueBBI.ExtraCost2, Prediction) &&

1365 FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) {

1366

1367

1368

1369

1370

1371

1372

1373 Tokens.push_back(

1374 std::make_unique(BBI, ICTriangle, TNeedSub, Dups));

1375 Enqueued = true;

1376 }

1377

1378 if (ValidTriangle(TrueBBI, FalseBBI, true, Dups, Prediction) &&

1379 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,

1380 TrueBBI.ExtraCost2, Prediction) &&

1381 FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) {

1382 Tokens.push_back(

1383 std::make_unique(BBI, ICTriangleRev, TNeedSub, Dups));

1384 Enqueued = true;

1385 }

1386

1387 if (ValidSimple(TrueBBI, Dups, Prediction) &&

1388 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,

1389 TrueBBI.ExtraCost2, Prediction) &&

1390 FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {

1391

1392

1393

1394

1395

1396

1397

1398 Tokens.push_back(

1399 std::make_unique(BBI, ICSimple, TNeedSub, Dups));

1400 Enqueued = true;

1401 }

1402

1403 if (CanRevCond) {

1404

1405 if (ValidTriangle(FalseBBI, TrueBBI, false, Dups,

1407 MeetIfcvtSizeLimit(*FalseBBI.BB,

1408 FalseBBI.NonPredSize + FalseBBI.ExtraCost,

1409 FalseBBI.ExtraCost2, Prediction.getCompl()) &&

1410 FeasibilityAnalysis(FalseBBI, RevCond, true)) {

1411 Tokens.push_back(std::make_unique(BBI, ICTriangleFalse,

1412 FNeedSub, Dups));

1413 Enqueued = true;

1414 }

1415

1416 if (ValidTriangle(FalseBBI, TrueBBI, true, Dups,

1418 MeetIfcvtSizeLimit(*FalseBBI.BB,

1419 FalseBBI.NonPredSize + FalseBBI.ExtraCost,

1420 FalseBBI.ExtraCost2, Prediction.getCompl()) &&

1421 FeasibilityAnalysis(FalseBBI, RevCond, true, true)) {

1422 Tokens.push_back(

1423 std::make_unique(BBI, ICTriangleFRev, FNeedSub, Dups));

1424 Enqueued = true;

1425 }

1426

1427 if (ValidSimple(FalseBBI, Dups, Prediction.getCompl()) &&

1428 MeetIfcvtSizeLimit(*FalseBBI.BB,

1429 FalseBBI.NonPredSize + FalseBBI.ExtraCost,

1430 FalseBBI.ExtraCost2, Prediction.getCompl()) &&

1431 FeasibilityAnalysis(FalseBBI, RevCond)) {

1432 Tokens.push_back(

1433 std::make_unique(BBI, ICSimpleFalse, FNeedSub, Dups));

1434 Enqueued = true;

1435 }

1436 }

1437

1438 BBI.IsEnqueued = Enqueued;

1439 BBI.IsBeingAnalyzed = false;

1440 BBI.IsAnalyzed = true;

1441 BBStack.pop_back();

1442 }

1443}

1444

1445

1446void IfConverter::AnalyzeBlocks(

1447 MachineFunction &MF, std::vector<std::unique_ptr> &Tokens) {

1448 for (MachineBasicBlock &MBB : MF)

1449 AnalyzeBlock(MBB, Tokens);

1450

1451

1453}

1454

1455

1456

1462 while (I != TI) {

1463

1464

1465 if (I == E || ->empty() || !PI->isSuccessor(&*I))

1466 return false;

1467 PI = I++;

1468 }

1469

1470 return PI->isSuccessor(&*I);

1471}

1472

1473

1474

1475void IfConverter::InvalidatePreds(MachineBasicBlock &MBB) {

1476 for (const MachineBasicBlock *Predecessor : MBB.predecessors()) {

1477 BBInfo &PBBI = BBAnalysis[Predecessor->getNumber()];

1478 if (PBBI.IsDone || PBBI.BB == &MBB)

1479 continue;

1480 PBBI.IsAnalyzed = false;

1481 PBBI.IsEnqueued = false;

1482 }

1483}

1484

1485

1488 DebugLoc dl;

1490 TII->insertBranch(MBB, &ToMBB, nullptr, NoCond, dl);

1491}

1492

1493

1494

1497

1498

1499

1500

1503 for (unsigned Reg : Redefs)

1505

1508

1509

1510 for (auto Clobber : Clobbers) {

1511

1512

1513 unsigned Reg = Clobber.first;

1517 if (Op.isRegMask()) {

1518

1519

1520 if (LiveBeforeMI.count(Reg))

1522

1523

1524

1525

1526

1527

1529 continue;

1530 }

1532 [&](MCPhysReg S) { return LiveBeforeMI.count(S); }))

1534 }

1535}

1536

1537

1538bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {

1539 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];

1540 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];

1541 BBInfo *CvtBBI = &TrueBBI;

1542 BBInfo *NextBBI = &FalseBBI;

1543

1545 if (Kind == ICSimpleFalse)

1547

1548 MachineBasicBlock &CvtMBB = *CvtBBI->BB;

1549 MachineBasicBlock &NextMBB = *NextBBI->BB;

1550 if (CvtBBI->IsDone ||

1551 (CvtBBI->CannotBeCopied && CvtMBB.pred_size() > 1)) {

1552

1553 BBI.IsAnalyzed = false;

1554 CvtBBI->IsAnalyzed = false;

1555 return false;

1556 }

1557

1559

1560 return false;

1561

1562 if (Kind == ICSimpleFalse)

1565

1567

1568 if (MRI->tracksLiveness()) {

1569

1570

1573 }

1574

1575

1576

1578

1580

1581

1582 CopyAndPredicateBlock(BBI, *CvtBBI, Cond);

1583

1584

1585 BBI.BB->removeSuccessor(&CvtMBB, true);

1586 } else {

1587

1588 PredicateBlock(*CvtBBI, CvtMBB.end(), Cond);

1589

1590

1591

1592 MergeBlocks(BBI, *CvtBBI);

1593 }

1594

1595 bool IterIfcvt = true;

1598 BBI.HasFallThrough = false;

1599

1600

1601

1602

1603

1604

1605

1606

1607

1608

1609 IterIfcvt = false;

1610 }

1611

1612

1613 if (!IterIfcvt)

1614 BBI.IsDone = true;

1615 InvalidatePreds(*BBI.BB);

1616 CvtBBI->IsDone = true;

1617

1618

1619 return true;

1620}

1621

1622

1623bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {

1624 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];

1625 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];

1626 BBInfo *CvtBBI = &TrueBBI;

1627 BBInfo *NextBBI = &FalseBBI;

1628 DebugLoc dl;

1629

1631 if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)

1633

1634 MachineBasicBlock &CvtMBB = *CvtBBI->BB;

1635 MachineBasicBlock &NextMBB = *NextBBI->BB;

1636 if (CvtBBI->IsDone ||

1637 (CvtBBI->CannotBeCopied && CvtMBB.pred_size() > 1)) {

1638

1639 BBI.IsAnalyzed = false;

1640 CvtBBI->IsAnalyzed = false;

1641 return false;

1642 }

1643

1645

1646 return false;

1647

1648 if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)

1651

1652 if (Kind == ICTriangleRev || Kind == ICTriangleFRev) {

1653 if (reverseBranchCondition(*CvtBBI)) {

1654

1655

1656 for (MachineBasicBlock *PBB : CvtMBB.predecessors()) {

1657 if (PBB == BBI.BB)

1658 continue;

1659 BBInfo &PBBI = BBAnalysis[PBB->getNumber()];

1660 if (PBBI.IsEnqueued) {

1661 PBBI.IsAnalyzed = false;

1662 PBBI.IsEnqueued = false;

1663 }

1664 }

1665 }

1666 }

1667

1668

1669

1671 if (MRI->tracksLiveness()) {

1674 }

1675

1676 bool HasEarlyExit = CvtBBI->FalseBB != nullptr;

1677 BranchProbability CvtNext, CvtFalse, BBNext, BBCvt;

1678

1679 if (HasEarlyExit) {

1680

1685 }

1686

1687

1688

1690

1692

1693

1694 CopyAndPredicateBlock(BBI, *CvtBBI, Cond, true);

1695 } else {

1696

1698 PredicateBlock(*CvtBBI, CvtMBB.end(), Cond);

1699

1700

1701 MergeBlocks(BBI, *CvtBBI, false);

1702 }

1703

1704

1705 BBI.BB->removeSuccessor(&CvtMBB, true);

1706

1707

1708 if (HasEarlyExit) {

1710 CvtBBI->BrCond.end());

1713

1714

1715

1716

1717

1718

1719

1721 auto NewNext = BBNext + BBCvt * CvtNext;

1722 auto NewTrueBBIter = find(BBI.BB->successors(), NewTrueBB);

1723 if (NewTrueBBIter != BBI.BB->succ_end())

1724 BBI.BB->setSuccProbability(NewTrueBBIter, NewNext);

1725

1726 auto NewFalse = BBCvt * CvtFalse;

1727 TII->insertBranch(*BBI.BB, CvtBBI->FalseBB, nullptr, RevCond, dl);

1728 BBI.BB->addSuccessor(CvtBBI->FalseBB, NewFalse);

1729 }

1730

1731

1732

1733 bool FalseBBDead = false;

1734 bool IterIfcvt = true;

1736 if (!isFallThrough) {

1737

1738

1739

1740 if (!HasEarlyExit && NextMBB.pred_size() == 1 &&

1741 blockNeverFallThrough(*NextBBI) && !NextMBB.hasAddressTaken()) {

1742 MergeBlocks(BBI, *NextBBI);

1743 FalseBBDead = true;

1744 } else {

1746 BBI.HasFallThrough = false;

1747 }

1748

1749

1750 IterIfcvt = false;

1751 }

1752

1753

1754 if (!IterIfcvt)

1755 BBI.IsDone = true;

1756 InvalidatePreds(*BBI.BB);

1757 CvtBBI->IsDone = true;

1758 if (FalseBBDead)

1759 NextBBI->IsDone = true;

1760

1761

1762 return true;

1763}

1764

1765

1766

1767

1768

1769

1770

1771

1772

1773

1774

1775

1776bool IfConverter::IfConvertDiamondCommon(

1777 BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,

1778 unsigned NumDups1, unsigned NumDups2,

1779 bool TClobbersPred, bool FClobbersPred,

1780 bool RemoveBranch, bool MergeAddEdges) {

1781

1782 if (TrueBBI.IsDone || FalseBBI.IsDone ||

1783 TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1) {

1784

1785 BBI.IsAnalyzed = false;

1786 TrueBBI.IsAnalyzed = false;

1787 FalseBBI.IsAnalyzed = false;

1788 return false;

1789 }

1790

1791 if (TrueBBI.BB->hasAddressTaken() || FalseBBI.BB->hasAddressTaken())

1792

1793 return false;

1794

1795

1796

1797

1798 BBInfo *BBI1 = &TrueBBI;

1799 BBInfo *BBI2 = &FalseBBI;

1805

1806

1807 bool DoSwap = false;

1808 if (TClobbersPred && !FClobbersPred)

1809 DoSwap = true;

1810 else if (!TClobbersPred && !FClobbersPred) {

1811 if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)

1812 DoSwap = true;

1813 } else if (TClobbersPred && FClobbersPred)

1814 llvm_unreachable("Predicate info cannot be clobbered by both sides.");

1815 if (DoSwap) {

1818 }

1819

1820

1822

1823 MachineBasicBlock &MBB1 = *BBI1->BB;

1824 MachineBasicBlock &MBB2 = *BBI2->BB;

1825

1826

1827

1828

1829

1830

1831

1833 if (MRI->tracksLiveness()) {

1836 }

1837

1838

1839

1842 BBI1->NonPredSize -= NumDups1;

1843 BBI2->NonPredSize -= NumDups1;

1844

1845

1846

1847

1848 for (unsigned i = 0; i < NumDups1; ++DI1) {

1849 if (DI1 == MBB1.end())

1850 break;

1851 if (!DI1->isDebugInstr())

1852 ++i;

1853 }

1854 while (NumDups1 != 0) {

1855

1856

1857 if (DI2->shouldUpdateAdditionalCallInfo())

1859

1860 ++DI2;

1861 if (DI2 == MBB2.end())

1862 break;

1863 if (!DI2->isDebugInstr())

1864 --NumDups1;

1865 }

1866

1867 if (MRI->tracksLiveness()) {

1871 }

1872 }

1873

1874 BBI.BB->splice(BBI.BB->end(), &MBB1, MBB1.begin(), DI1);

1876

1877

1878

1879

1880

1881

1882

1883#ifndef NDEBUG

1884

1885 if (!BBI1->IsBrAnalyzable)

1887#endif

1888

1889

1890 DI1 = MBB1.end();

1891 while (DI1 != MBB1.begin()) {

1893 if (!Prev->isBranch() && !Prev->isDebugInstr())

1894 break;

1895 DI1 = Prev;

1896 }

1897 for (unsigned i = 0; i != NumDups2; ) {

1898

1899

1901

1902 --DI1;

1903

1904

1905

1906 if (DI1->shouldUpdateAdditionalCallInfo())

1908

1909

1910 if (!DI1->isDebugInstr())

1911 ++i;

1912 }

1913 MBB1.erase(DI1, MBB1.end());

1914

1915 DI2 = BBI2->BB->end();

1916

1917

1918 if (RemoveBranch)

1920 else {

1921

1922

1923 while (DI2 != MBB2.begin()) {

1925 if (!Prev->isBranch() && !Prev->isDebugInstr())

1926 break;

1927 DI2 = Prev;

1928 }

1929 }

1930 while (NumDups2 != 0) {

1931

1932

1934 --DI2;

1935

1936 if (!DI2->isDebugInstr())

1937 --NumDups2;

1938 }

1939

1940

1941

1942

1943

1944

1945

1946

1947

1948 SmallSet<MCRegister, 4> RedefsByFalse;

1949 SmallSet<MCRegister, 4> ExtUses;

1951 for (const MachineInstr &FI : make_range(MBB2.begin(), DI2)) {

1952 if (FI.isDebugInstr())

1953 continue;

1955 for (const MachineOperand &MO : FI.operands()) {

1956 if (!MO.isReg())

1957 continue;

1959 if ( Reg )

1960 continue;

1961 if (MO.isDef()) {

1963 } else if (!RedefsByFalse.count(Reg)) {

1964

1965

1967 }

1968 }

1969

1970 for (MCRegister Reg : Defs) {

1973 }

1974 }

1975 }

1976

1977

1978 PredicateBlock(*BBI1, MBB1.end(), *Cond1, &RedefsByFalse);

1979

1980

1981

1982

1983

1984

1985

1986

1987 if (!MBB2.empty() && (DI2 == MBB2.end())) {

1990 bool BB1Predicated = BBI1T != MBB1.end() && TII->isPredicated(*BBI1T);

1991 bool BB2NonPredicated = BBI2T != MBB2.end() && TII ->isPredicated(*BBI2T);

1992 if (BB2NonPredicated && (BB1Predicated || !BBI2->IsBrAnalyzable))

1993 --DI2;

1994 }

1995

1996

1997 PredicateBlock(*BBI2, DI2, *Cond2);

1998

1999

2000 MergeBlocks(BBI, *BBI1, MergeAddEdges);

2001 MergeBlocks(BBI, *BBI2, MergeAddEdges);

2002 return true;

2003}

2004

2005

2006

2007bool IfConverter::IfConvertForkedDiamond(

2008 BBInfo &BBI, IfcvtKind Kind,

2009 unsigned NumDups1, unsigned NumDups2,

2010 bool TClobbersPred, bool FClobbersPred) {

2011 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];

2012 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];

2013

2014

2017 if (TIE != TrueBBI.BB->end())

2018 dl = TIE->getDebugLoc();

2019

2020

2021

2022 if (!IfConvertDiamondCommon(

2023 BBI, TrueBBI, FalseBBI,

2024 NumDups1, NumDups2,

2025 TClobbersPred, FClobbersPred,

2026 true, true))

2027 return false;

2028

2029

2030

2031 TII->insertBranch(*BBI.BB, TrueBBI.TrueBB, TrueBBI.FalseBB,

2032 TrueBBI.BrCond, dl);

2033

2034

2035 BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;

2036 InvalidatePreds(*BBI.BB);

2037

2038

2039 return true;

2040}

2041

2042

2043bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,

2044 unsigned NumDups1, unsigned NumDups2,

2045 bool TClobbersPred, bool FClobbersPred) {

2046 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];

2047 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];

2048 MachineBasicBlock *TailBB = TrueBBI.TrueBB;

2049

2050

2051 if (!TailBB) {

2052 if (blockAlwaysFallThrough(TrueBBI))

2053 TailBB = FalseBBI.TrueBB;

2054 assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!");

2055 }

2056

2057 if (!IfConvertDiamondCommon(

2058 BBI, TrueBBI, FalseBBI,

2059 NumDups1, NumDups2,

2060 TClobbersPred, FClobbersPred,

2061 TrueBBI.IsBrAnalyzable,

2062 TailBB == nullptr))

2063 return false;

2064

2065

2066

2067

2068

2069 if (TailBB) {

2070

2071

2072 BBI.BB->removeSuccessor(TrueBBI.BB);

2073 BBI.BB->removeSuccessor(FalseBBI.BB, true);

2074

2075 BBInfo &TailBBI = BBAnalysis[TailBB->getNumber()];

2076 bool CanMergeTail =

2077 blockNeverFallThrough(TailBBI) && !TailBBI.BB->hasAddressTaken();

2078

2079

2080

2083 CanMergeTail = false;

2084

2085

2086 unsigned NumPreds = TailBB->pred_size();

2087 if (NumPreds > 1)

2088 CanMergeTail = false;

2089 else if (NumPreds == 1 && CanMergeTail) {

2091 if (*PI != TrueBBI.BB && *PI != FalseBBI.BB)

2092 CanMergeTail = false;

2093 }

2094 if (CanMergeTail) {

2095 MergeBlocks(BBI, TailBBI);

2096 TailBBI.IsDone = true;

2097 } else {

2100 BBI.HasFallThrough = false;

2101 }

2102 }

2103

2104

2105 BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;

2106 InvalidatePreds(*BBI.BB);

2107

2108

2109 return true;

2110}

2111

2114 bool SawStore = true;

2115 if (.isSafeToMove(SawStore))

2116 return false;

2117

2119 if (!MO.isReg())

2120 continue;

2122 if ( Reg )

2123 continue;

2124 if (MO.isDef() && !LaterRedefs.count(Reg))

2125 return false;

2126 }

2127

2128 return true;

2129}

2130

2131

2132

2134 SmallVectorImpl &Cond,

2135 SmallSet<MCRegister, 4> *LaterRedefs) {

2136 bool AnyUnpred = false;

2137 bool MaySpec = LaterRedefs != nullptr;

2138 for (MachineInstr &I : make_range(BBI.BB->begin(), E)) {

2140 continue;

2141

2142

2143

2145 AnyUnpred = true;

2146 continue;

2147 }

2148

2149

2150 MaySpec = false;

2152#ifndef NDEBUG

2153 dbgs() << "Unable to predicate " << I << "!\n";

2154#endif

2156 }

2157

2158

2159

2161 }

2162

2163 BBI.Predicate.append(Cond.begin(), Cond.end());

2164

2165 BBI.IsAnalyzed = false;

2166 BBI.NonPredSize = 0;

2167

2168 ++NumIfConvBBs;

2169 if (AnyUnpred)

2170 ++NumUnpred;

2171}

2172

2173

2174

2175void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,

2176 SmallVectorImpl &Cond,

2177 bool IgnoreBr) {

2178 MachineFunction &MF = *ToBBI.BB->getParent();

2179

2180 MachineBasicBlock &FromMBB = *FromBBI.BB;

2181 for (MachineInstr &I : FromMBB) {

2182

2183 if (IgnoreBr && I.isBranch())

2184 break;

2185

2186 MachineInstr *MI = MF.CloneMachineInstr(&I);

2187

2188 if (I.isCandidateForAdditionalCallInfo())

2190

2191 ToBBI.BB->insert(ToBBI.BB->end(), MI);

2192 ToBBI.NonPredSize++;

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

2195 if (NumCycles > 1)

2196 ToBBI.ExtraCost += NumCycles-1;

2197 ToBBI.ExtraCost2 += ExtraPredCost;

2198

2201#ifndef NDEBUG

2202 dbgs() << "Unable to predicate " << I << "!\n";

2203#endif

2205 }

2206 }

2207

2208

2209

2211 }

2212

2213 if (!IgnoreBr) {

2214 std::vector<MachineBasicBlock *> Succs(FromMBB.succ_begin(),

2215 FromMBB.succ_end());

2216 MachineBasicBlock *NBB = getNextBlock(FromMBB);

2217 MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr;

2218

2219 for (MachineBasicBlock *Succ : Succs) {

2220

2221 if (Succ == FallThrough)

2222 continue;

2223 ToBBI.BB->addSuccessor(Succ);

2224 }

2225 }

2226

2227 ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());

2228 ToBBI.Predicate.append(Cond.begin(), Cond.end());

2229

2230 ToBBI.ClobbersPred |= FromBBI.ClobbersPred;

2231 ToBBI.IsAnalyzed = false;

2232

2233 ++NumDupBBs;

2234}

2235

2236

2237

2238

2239

2240

2241void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {

2242 MachineBasicBlock &FromMBB = *FromBBI.BB;

2244 "Removing a BB whose address is taken!");

2245

2246

2247

2249 for (MachineInstr &MI : FromMBB)

2250 if (MI.getOpcode() == TargetOpcode::INLINEASM_BR)

2251 for (MachineOperand &MO : MI.operands())

2252 if (MO.isMBB() && !ToBBI.BB->isSuccessor(MO.getMBB()))

2254

2255

2256

2259 ToBBI.BB->splice(ToTI, &FromMBB, FromMBB.begin(), FromTI);

2260

2261

2262 if (FromTI != FromMBB.end() && TII ->isPredicated(*FromTI))

2263 ToTI = ToBBI.BB->end();

2264 ToBBI.BB->splice(ToTI, &FromMBB, FromTI, FromMBB.end());

2265

2266

2267

2268

2269

2270 if (ToBBI.IsBrAnalyzable)

2271 ToBBI.BB->normalizeSuccProbs();

2272

2273 SmallVector<MachineBasicBlock *, 4> FromSuccs(FromMBB.successors());

2274 MachineBasicBlock *NBB = getNextBlock(FromMBB);

2275 MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr;

2276

2277

2279 if (AddEdges && ToBBI.BB->isSuccessor(&FromMBB)) {

2280

2281

2283 ToBBI.BB->removeSuccessor(&FromMBB);

2284 }

2285

2286 for (MachineBasicBlock *Succ : FromSuccs) {

2287

2288 if (Succ == FallThrough) {

2289 FromMBB.removeSuccessor(Succ);

2290 continue;

2291 }

2292

2294 if (AddEdges) {

2295

2296

2297

2298

2300

2301

2302

2303

2304

2305

2306 if (!To2FromProb.isZero())

2307 NewProb *= To2FromProb;

2308 }

2309

2310 FromMBB.removeSuccessor(Succ);

2311

2312 if (AddEdges) {

2313

2314

2315

2316

2317

2318

2319

2320

2321

2322

2323

2324

2325

2326

2327

2328

2329

2330

2331

2332

2333

2334

2335 if (ToBBI.BB->isSuccessor(Succ))

2336 ToBBI.BB->setSuccProbability(

2337 find(ToBBI.BB->successors(), Succ),

2339 else

2340 ToBBI.BB->addSuccessor(Succ, NewProb);

2341 }

2342 }

2343

2344

2345

2346 MachineBasicBlock *Last = &*FromMBB.getParent()->rbegin();

2347 if (Last != &FromMBB)

2348 FromMBB.moveAfter(Last);

2349

2350

2351

2352 if (ToBBI.IsBrAnalyzable && FromBBI.IsBrAnalyzable)

2353 ToBBI.BB->normalizeSuccProbs();

2354

2355 ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());

2356 FromBBI.Predicate.clear();

2357

2358 ToBBI.NonPredSize += FromBBI.NonPredSize;

2359 ToBBI.ExtraCost += FromBBI.ExtraCost;

2360 ToBBI.ExtraCost2 += FromBBI.ExtraCost2;

2361 FromBBI.NonPredSize = 0;

2362 FromBBI.ExtraCost = 0;

2363 FromBBI.ExtraCost2 = 0;

2364

2365 ToBBI.ClobbersPred |= FromBBI.ClobbersPred;

2366 ToBBI.HasFallThrough = FromBBI.HasFallThrough;

2367 ToBBI.IsAnalyzed = false;

2368 FromBBI.IsAnalyzed = false;

2369}

2370

2371FunctionPass *

2373 return new IfConverter(std::move(Ftor));

2374}

unsigned const MachineRegisterInfo * MRI

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

const TargetInstrInfo & TII

Function Alias Analysis false

static MachineBasicBlock * findFalseBlock(MachineBasicBlock *BB, MachineBasicBlock *TrueBB)

findFalseBlock - BB has a fallthrough.

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

static cl::opt< bool > DisableTriangle("disable-ifcvt-triangle", cl::init(false), cl::Hidden)

static MachineBasicBlock * findFalseBlock(MachineBasicBlock *BB, MachineBasicBlock *TrueBB)

BB has a fallthrough. Find its 'false' successor given its 'true' successor.

Definition IfConversion.cpp:627

static cl::opt< int > IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden)

static cl::opt< bool > IfCvtBranchFold("ifcvt-branch-fold", cl::init(true), cl::Hidden)

static cl::opt< bool > DisableTriangleF("disable-ifcvt-triangle-false", cl::init(false), cl::Hidden)

static cl::opt< int > IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden)

static void InsertUncondBranch(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB, const TargetInstrInfo *TII)

Inserts an unconditional branch from MBB to ToMBB.

Definition IfConversion.cpp:1486

static void verifySameBranchInstructions(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2)

Definition IfConversion.cpp:847

static cl::opt< bool > DisableDiamond("disable-ifcvt-diamond", cl::init(false), cl::Hidden)

static cl::opt< bool > DisableTriangleR("disable-ifcvt-triangle-rev", cl::init(false), cl::Hidden)

static cl::opt< bool > DisableForkedDiamond("disable-ifcvt-forked-diamond", cl::init(false), cl::Hidden)

static MachineBasicBlock * getNextBlock(MachineBasicBlock &MBB)

Returns the next block in the function blocks ordering.

Definition IfConversion.cpp:651

static bool MaySpeculate(const MachineInstr &MI, SmallSet< MCRegister, 4 > &LaterRedefs)

Definition IfConversion.cpp:2112

static void UpdatePredRedefs(MachineInstr &MI, LivePhysRegs &Redefs)

Behaves like LiveRegUnits::StepForward() but also adds implicit uses to all values defined in MI whic...

Definition IfConversion.cpp:1495

static cl::opt< bool > DisableSimpleF("disable-ifcvt-simple-false", cl::init(false), cl::Hidden)

static cl::opt< bool > DisableSimple("disable-ifcvt-simple", cl::init(false), cl::Hidden)

static bool canFallThroughTo(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB)

Returns true either if ToMBB is the next block after MBB or that all the intervening blocks are empty...

Definition IfConversion.cpp:1457

static cl::opt< int > IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden)

This file implements the LivePhysRegs utility for tracking liveness of physical registers.

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)

const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB

const SmallVectorImpl< MachineOperand > & Cond

This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...

This file defines the SmallSet class.

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

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

AnalysisUsage & addRequired()

bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii, const TargetRegisterInfo *tri, MachineLoopInfo *mli=nullptr, bool AfterPlacement=false)

Perhaps branch folding, tail merging and other CFG optimizations on the given function.

static BranchProbability getOne()

BranchProbability getCompl() const

static BranchProbability getZero()

bool hasMinSize() const

Optimize this function for minimum size (-Oz).

A set of physical registers with utility functions to track liveness when walking backward/forward th...

void stepForward(const MachineInstr &MI, SmallVectorImpl< std::pair< MCPhysReg, const MachineOperand * > > &Clobbers)

Simulates liveness when stepping forward over an instruction(bundle).

void init(const TargetRegisterInfo &TRI)

(re-)initializes and clears the set.

void addLiveInsNoPristines(const MachineBasicBlock &MBB)

Adds all live-in registers of basic block MBB but skips pristine registers.

unsigned pred_size() const

MachineInstrBundleIterator< const MachineInstr > const_iterator

int getNumber() const

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

LLVM_ABI iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)

Returns an iterator to the first non-debug instruction in the basic block, or end().

LLVM_ABI iterator getFirstTerminator()

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

bool hasAddressTaken() const

Test whether this block is used as something other than the target of a terminator,...

SmallVectorImpl< MachineBasicBlock * >::iterator pred_iterator

pred_iterator pred_begin()

MachineInstrBundleIterator< MachineInstr, true > reverse_iterator

const MachineFunction * getParent() const

Return the MachineFunction containing this basic block.

LLVM_ABI instr_iterator erase(instr_iterator I)

Remove an instruction from the instruction list and delete it.

iterator_range< iterator > terminators()

iterator_range< succ_iterator > successors()

reverse_iterator rbegin()

iterator_range< pred_iterator > predecessors()

MachineInstrBundleIterator< MachineInstr > iterator

LLVM_ABI bool mayHaveInlineAsmBr() const

Returns true if this block may have an INLINEASM_BR (overestimate, by checking if any of the successo...

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

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.

Function & getFunction()

Return the LLVM function that this machine code represents.

BasicBlockListType::iterator iterator

void eraseAdditionalCallInfo(const MachineInstr *MI)

Following functions update call site info.

void copyAdditionalCallInfo(const MachineInstr *Old, const MachineInstr *New)

Copy the call site info from Old to \ New.

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

Add a new virtual register operand.

reverse_iterator getReverse() const

Get a reverse iterator to the same node.

Representation of each machine instruction.

LLVM_ABI const MachineFunction * getMF() const

Return the function that contains the basic block that this instruction belongs to.

MachineOperand class - Representation of each machine instruction operand.

static LLVM_ABI PassRegistry * getPassRegistry()

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

An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.

Analysis providing profile information.

Wrapper class representing virtual and physical registers.

SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...

size_type count(const T &V) const

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

void insert_range(Range &&R)

bool contains(const T &V) const

Check if the SmallSet contains the given element.

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.

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

insert - Attempts to insert a new element.

size_type count(const KeyT &Key) const

count - Returns 1 if this set contains an element identified by Key, 0 otherwise.

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.

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 ClobbersPredicate(MachineInstr &MI, std::vector< MachineOperand > &Pred, bool SkipDead) const

If the specified instruction defines any predicate or condition code register(s) used for predication...

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 bool isProfitableToUnpredicate(MachineBasicBlock &TMBB, MachineBasicBlock &FMBB) const

Return true if it's profitable to unpredicate one side of a 'diamond', i.e.

virtual bool SubsumesPredicate(ArrayRef< MachineOperand > Pred1, ArrayRef< MachineOperand > Pred2) const

Returns true if the first specified predicate subsumes the second, e.g.

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 bool isProfitableToDupForIfCvt(MachineBasicBlock &MBB, unsigned NumCycles, BranchProbability Probability) const

Return true if it's profitable for if-converter to duplicate instructions of specified accumulated in...

virtual unsigned getPredicationCost(const MachineInstr &MI) const

virtual bool isPredicable(const MachineInstr &MI) const

Return true if the specified instruction can be predicated.

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

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

Initialize the machine model for instruction scheduling.

TargetSubtargetInfo - Generic base class for all target subtargets.

self_iterator getIterator()

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

#define llvm_unreachable(msg)

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

bool isPredicated(const MCInst &MI, const MCInstrInfo *MCII)

@ Implicit

Not emitted register (e.g. carry, or temporary result).

@ Define

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

void stable_sort(R &&Range)

auto find(R &&Range, const T &Val)

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

LLVM_ABI FunctionPass * createIfConverter(std::function< bool(const MachineFunction &)> Ftor)

Definition IfConversion.cpp:2372

detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)

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

Convenience function for iterating over sub-ranges.

IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=true)

Increment It until it points to a non-debug instruction or to End and return the resulting iterator.

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

void recomputeLivenessFlags(MachineBasicBlock &MBB)

Recomputes dead and kill flags in MBB.

uint16_t MCPhysReg

An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...

DWARFExpression::Operation Op

OutputIt move(R &&Range, OutputIt Out)

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

LLVM_ABI char & IfConverterID

IfConverter - This pass performs machine code if conversion.

Definition IfConversion.cpp:451

LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

LLVM_ABI void initializeIfConverterPass(PassRegistry &)

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

Implement std::swap in terms of BitVector swap.