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 struct BBInfo {

132 bool IsDone : 1;

133 bool IsBeingAnalyzed : 1;

134 bool IsAnalyzed : 1;

135 bool IsEnqueued : 1;

136 bool IsBrAnalyzable : 1;

137 bool IsBrReversible : 1;

138 bool HasFallThrough : 1;

139 bool IsUnpredicable : 1;

140 bool CannotBeCopied : 1;

141 bool ClobbersPred : 1;

142 unsigned NonPredSize = 0;

143 unsigned ExtraCost = 0;

144 unsigned ExtraCost2 = 0;

150

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

152 IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false),

153 IsBrReversible(false), HasFallThrough(false),

154 IsUnpredicable(false), CannotBeCopied(false),

155 ClobbersPred(false) {}

156 };

157

158

159

160

161

162

163

164

165

166

167

168

169 struct IfcvtToken {

170 BBInfo &BBI;

171 IfcvtKind Kind;

172 unsigned NumDups;

173 unsigned NumDups2;

174 bool NeedSubsumption : 1;

175 bool TClobbersPred : 1;

176 bool FClobbersPred : 1;

177

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

179 bool tc = false, bool fc = false)

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

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

182 };

183

184

185

186 std::vector BBAnalysis;

188

194

196

197 bool PreRegAlloc = true;

198 bool MadeChange = false;

199 int FnNum = -1;

201

202 public:

203 static char ID;

204

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

208 }

209

215 }

216

218

221 MachineFunctionProperties::Property::NoVRegs);

222 }

223

224 private:

225 bool reverseBranchCondition(BBInfo &BBI) const;

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

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

229 bool FalseBranch, unsigned &Dups,

231 bool CountDuplicatedInstructions(

234 unsigned &Dups1, unsigned &Dups2,

236 bool SkipUnconditionalBranches) const;

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

238 unsigned &Dups1, unsigned &Dups2,

239 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const;

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

241 unsigned &Dups1, unsigned &Dups2,

242 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const;

243 void AnalyzeBranches(BBInfo &BBI);

244 void ScanInstructions(BBInfo &BBI,

247 bool BranchUnpredicable = false) const;

248 bool RescanInstructions(

251 BBInfo &TrueBBI, BBInfo &FalseBBI) const;

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

255 bool isTriangle = false, bool RevBranch = false,

256 bool hasCommonTail = false);

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

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

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

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

263 unsigned NumDups1, unsigned NumDups2,

264 bool TClobbersPred, bool FClobbersPred,

265 bool RemoveBranch, bool MergeAddEdges);

266 bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,

267 unsigned NumDups1, unsigned NumDups2,

268 bool TClobbers, bool FClobbers);

269 bool IfConvertForkedDiamond(BBInfo &BBI, IfcvtKind Kind,

270 unsigned NumDups1, unsigned NumDups2,

271 bool TClobbers, bool FClobbers);

272 void PredicateBlock(BBInfo &BBI,

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

278 bool IgnoreBr = false);

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

280

282 unsigned Cycle, unsigned Extra,

285 Prediction);

286 }

287

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

297

298 unsigned Dups1 = 0, Dups2 = 0;

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

300 *TBBInfo.BB, *FBBInfo.BB,

301 true))

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

303

304 unsigned BranchBytes = 0;

305 unsigned CommonBytes = 0;

306

307

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

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

311 }

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

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

315 }

316

317

318

319

320

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

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

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

325 } else {

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

328 }

329 }

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

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

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

334 } else {

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

337 }

338 }

340 if (I.isBranch()) {

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

343 }

344 }

345

346

347

348 CommonBytes /= 2;

349

350

351 unsigned NumPredicatedInstructions = 0;

353 if (.isDebugInstr()) {

355 NumPredicatedInstructions++;

356 }

357 }

359 if (.isDebugInstr()) {

361 NumPredicatedInstructions++;

362 }

363 }

364

365

366

367 if (NumPredicatedInstructions > 15)

368 return false;

369

370

371

372 unsigned ExtraPredicateBytes = TII->extraSizeToPredicateInstructions(

373 MF, NumPredicatedInstructions);

374

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

376 << ", CommonBytes=" << CommonBytes

377 << ", NumPredicatedInstructions="

378 << NumPredicatedInstructions

379 << ", ExtraPredicateBytes=" << ExtraPredicateBytes

380 << ")\n");

381 return (BranchBytes + CommonBytes) > ExtraPredicateBytes;

382 } else {

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

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

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

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

388 FCycle, FBBInfo.ExtraCost2, Prediction);

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

390 << ", FCycle=" << FCycle

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

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

393 return Res;

394 }

395 }

396

397

398 bool blockAlwaysFallThrough(BBInfo &BBI) const {

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

400 }

401

402

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

404 const std::unique_ptr &C2) {

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

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

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

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

409 if (Incr1 > Incr2)

410 return true;

411 else if (Incr1 == Incr2) {

412

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

414 return true;

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

416

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

418 return true;

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

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

421 }

422 }

423 return false;

424 }

425 };

426

427}

428

429char IfConverter::ID = 0;

430

432

437

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

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

440 return false;

441

443 TLI = ST.getTargetLowering();

444 TII = ST.getInstrInfo();

445 TRI = ST.getRegisterInfo();

447 getAnalysis().getMBFI());

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

450 &getAnalysis().getPSI();

451 MRI = &MF.getRegInfo();

452 SchedModel.init(&ST);

453

454 if ( TII ) return false;

455

456 PreRegAlloc = MRI->isSSA();

457

458 bool BFChange = false;

459 if (!PreRegAlloc) {

460

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

463 }

464

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

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

467

470 return false;

471 }

473

474 MF.RenumberBlocks();

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

476

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

478 MadeChange = false;

479 unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle +

480 NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds;

482

483

484 bool Change = false;

485 AnalyzeBlocks(MF, Tokens);

486 while (!Tokens.empty()) {

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

488 Tokens.pop_back();

489 BBInfo &BBI = Token->BBI;

490 IfcvtKind Kind = Token->Kind;

491 unsigned NumDups = Token->NumDups;

492 unsigned NumDups2 = Token->NumDups2;

493

494

495

496 if (BBI.IsDone)

497 BBI.IsEnqueued = false;

498 if (!BBI.IsEnqueued)

499 continue;

500

501 BBI.IsEnqueued = false;

502

503 bool RetVal = false;

504 switch (Kind) {

506 case ICSimple:

507 case ICSimpleFalse: {

508 bool isFalse = Kind == ICSimpleFalse;

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

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

514 : BBI.TrueBB->getNumber())

515 << ") ");

516 RetVal = IfConvertSimple(BBI, Kind);

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

518 if (RetVal) {

519 if (isFalse) ++NumSimpleFalse;

520 else ++NumSimple;

521 }

522 break;

523 }

524 case ICTriangle:

525 case ICTriangleRev:

526 case ICTriangleFalse:

527 case ICTriangleFRev: {

528 bool isFalse = Kind == ICTriangleFalse;

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

534 if (isFalse)

536 if (isRev)

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

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

541 RetVal = IfConvertTriangle(BBI, Kind);

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

543 if (RetVal) {

544 if (isFalse)

545 ++NumTriangleFalse;

546 else if (isRev)

547 ++NumTriangleRev;

548 else

549 ++NumTriangle;

550 }

551 break;

552 }

553 case ICDiamond:

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

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

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

559 Token->TClobbersPred,

560 Token->FClobbersPred);

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

562 if (RetVal) ++NumDiamonds;

563 break;

564 case ICForkedDiamond:

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

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

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

571 Token->TClobbersPred,

572 Token->FClobbersPred);

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

574 if (RetVal) ++NumForkedDiamonds;

575 break;

576 }

577

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

580

581 Change |= RetVal;

582

583 NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev +

584 NumTriangleFalse + NumTriangleFRev + NumDiamonds;

586 break;

587 }

588

589 if (!Change)

590 break;

591 MadeChange |= Change;

592 }

593

594 Tokens.clear();

595 BBAnalysis.clear();

596

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

600 }

601

602 MadeChange |= BFChange;

603 return MadeChange;

604}

605

606

610 if (SuccBB != TrueBB)

611 return SuccBB;

612 }

613 return nullptr;

614}

615

616

617

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

619 DebugLoc dl;

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

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

624 return true;

625 }

626 return false;

627}

628

629

630

634 if (++I == E)

635 return nullptr;

636 return &*I;

637}

638

639

640

641

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

644 Dups = 0;

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

646 return false;

647

648 if (TrueBBI.IsBrAnalyzable)

649 return false;

650

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

652 if (TrueBBI.CannotBeCopied ||

654 Prediction))

655 return false;

656 Dups = TrueBBI.NonPredSize;

657 }

658

659 return true;

660}

661

662

663

664

665

666

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

668 bool FalseBranch, unsigned &Dups,

670 Dups = 0;

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

672 return false;

673

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

675 return false;

676

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

678 if (TrueBBI.CannotBeCopied)

679 return false;

680

681 unsigned Size = TrueBBI.NonPredSize;

682 if (TrueBBI.IsBrAnalyzable) {

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

684

686 else {

688 ? TrueBBI.TrueBB : TrueBBI.FalseBB;

689 if (FExit)

690

692 }

693 }

695 return false;

697 }

698

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

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

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

703 return false;

704 TExit = &*I;

705 }

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

707}

708

709

710

711

712

713

714

715

716

717

718

719

720

721

722

723

724

725

726

727

728

729bool IfConverter::CountDuplicatedInstructions(

734 unsigned &Dups1, unsigned &Dups2,

736 bool SkipUnconditionalBranches) const {

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

738

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

742 break;

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

744 break;

745

746

747 std::vector PredDefs;

749 return false;

750

751 if (!TIB->isBranch())

752 ++Dups1;

753 ++TIB;

754 ++FIB;

755 }

756

757

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

759 return true;

760

761

762

763

768

770 if (SkipUnconditionalBranches) {

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

772 ++RTIE;

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

774 ++RFIE;

775 }

776 }

777

778

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

780

781

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

785 break;

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

787 break;

788

789

790 if (!RTIE->isBranch())

791 ++Dups2;

792 ++RTIE;

793 ++RFIE;

794 }

797 return true;

798}

799

800

801

802

803

804

805

806

807

808

809bool IfConverter::RescanInstructions(

812 BBInfo &TrueBBI, BBInfo &FalseBBI) const {

813 bool BranchUnpredicable = true;

814 TrueBBI.IsUnpredicable = FalseBBI.IsUnpredicable = false;

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

816 if (TrueBBI.IsUnpredicable)

817 return false;

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

819 if (FalseBBI.IsUnpredicable)

820 return false;

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

822 return false;

823 return true;

824}

825

826#ifndef NDEBUG

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

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

838 break;

839

840 if (E1 == B1) {

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

842 break;

843 }

844 if (E2 == B2) {

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

846 break;

847 }

848

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

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

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

852 else

853 break;

854 ++E1;

855 ++E2;

856 }

857}

858#endif

859

860

861

862

863

864

865

866

867

868

869

870

871

872

873bool IfConverter::ValidForkedDiamond(

874 BBInfo &TrueBBI, BBInfo &FalseBBI,

875 unsigned &Dups1, unsigned &Dups2,

876 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const {

877 Dups1 = Dups2 = 0;

878 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||

879 FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)

880 return false;

881

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

883 return false;

884

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

886 return false;

887

888

889

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

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

892 return false;

893

898

899 if (!TT)

901 if (!TF)

903 if (!FT)

905 if (!FF)

907

908 if (!TT || !TF)

909 return false;

910

911

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

913 return false;

914

915 bool FalseReversed = false;

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

917

918 if (!FalseBBI.IsBrReversible)

919 return false;

920 FalseReversed = true;

921 reverseBranchCondition(FalseBBI);

922 }

924 if (FalseReversed)

925 reverseBranchCondition(FalseBBI);

926 });

927

928

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

934 *TrueBBI.BB, *FalseBBI.BB,

935 true))

936 return false;

937

938 TrueBBICalc.BB = TrueBBI.BB;

939 FalseBBICalc.BB = FalseBBI.BB;

940 TrueBBICalc.IsBrAnalyzable = TrueBBI.IsBrAnalyzable;

941 FalseBBICalc.IsBrAnalyzable = FalseBBI.IsBrAnalyzable;

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

943 return false;

944

945

946

947

948 TrueBBICalc.NonPredSize = TrueBBI.NonPredSize;

949 FalseBBICalc.NonPredSize = FalseBBI.NonPredSize;

950 return true;

951}

952

953

954

955bool IfConverter::ValidDiamond(

956 BBInfo &TrueBBI, BBInfo &FalseBBI,

957 unsigned &Dups1, unsigned &Dups2,

958 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const {

959 Dups1 = Dups2 = 0;

960 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||

961 FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)

962 return false;

963

964

965

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

967 return false;

968

971

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

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

976 if (TT != FT)

977 return false;

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

979 return false;

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

981 return false;

982

983

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

985 return false;

986

987

988

989

990

991 bool SkipUnconditionalBranches =

992 TrueBBI.IsBrAnalyzable && FalseBBI.IsBrAnalyzable;

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

998 *TrueBBI.BB, *FalseBBI.BB,

999 SkipUnconditionalBranches))

1000 return false;

1001

1002 TrueBBICalc.BB = TrueBBI.BB;

1003 FalseBBICalc.BB = FalseBBI.BB;

1004 TrueBBICalc.IsBrAnalyzable = TrueBBI.IsBrAnalyzable;

1005 FalseBBICalc.IsBrAnalyzable = FalseBBI.IsBrAnalyzable;

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

1007 return false;

1008

1009

1010

1011 TrueBBICalc.NonPredSize = TrueBBI.NonPredSize;

1012 FalseBBICalc.NonPredSize = FalseBBI.NonPredSize;

1013 return true;

1014}

1015

1016

1017

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

1019 if (BBI.IsDone)

1020 return;

1021

1022 BBI.TrueBB = BBI.FalseBB = nullptr;

1023 BBI.BrCond.clear();

1024 BBI.IsBrAnalyzable =

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

1026 if (!BBI.IsBrAnalyzable) {

1027 BBI.TrueBB = nullptr;

1028 BBI.FalseBB = nullptr;

1029 BBI.BrCond.clear();

1030 }

1031

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

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

1036

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

1038

1039

1040 if (!BBI.FalseBB)

1042 if (!BBI.FalseBB) {

1043

1044 BBI.IsUnpredicable = true;

1045 }

1046 }

1047}

1048

1049

1050

1051

1052

1053

1054void IfConverter::ScanInstructions(BBInfo &BBI,

1057 bool BranchUnpredicable) const {

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

1059 return;

1060

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

1062

1063 BBI.NonPredSize = 0;

1064 BBI.ExtraCost = 0;

1065 BBI.ExtraCost2 = 0;

1066 BBI.ClobbersPred = false;

1068 if (MI.isDebugInstr())

1069 continue;

1070

1071

1072

1073

1074

1075

1076

1077

1078

1079

1080

1081

1082

1083

1084

1085

1086

1087

1088

1089

1090

1091

1092

1093

1094

1095

1096

1097

1098

1099

1100

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

1102 BBI.CannotBeCopied = true;

1103

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

1106

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

1108 BBI.IsUnpredicable = true;

1109 return;

1110 }

1111

1112

1113 if (isCondBr)

1114 continue;

1115

1116 if (!isPredicated) {

1117 BBI.NonPredSize++;

1118 unsigned ExtraPredCost = TII->getPredicationCost(MI);

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

1120 if (NumCycles > 1)

1121 BBI.ExtraCost += NumCycles-1;

1122 BBI.ExtraCost2 += ExtraPredCost;

1123 } else if (!AlreadyPredicated) {

1124

1125

1126

1127 BBI.IsUnpredicable = true;

1128 return;

1129 }

1130

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

1132

1133

1134

1135

1136 BBI.IsUnpredicable = true;

1137 return;

1138 }

1139

1140

1141

1142 std::vector PredDefs;

1144 BBI.ClobbersPred = true;

1145

1147 BBI.IsUnpredicable = true;

1148 return;

1149 }

1150 }

1151}

1152

1153

1154

1155

1156

1157

1158

1159

1160

1161

1162bool IfConverter::FeasibilityAnalysis(BBInfo &BBI,

1164 bool isTriangle, bool RevBranch,

1165 bool hasCommonTail) {

1166

1167

1168

1169

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

1171 return false;

1172

1173

1174

1175

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

1177 return false;

1178

1179

1180

1182 return false;

1183

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

1185 if (!isTriangle)

1186 return false;

1187

1188

1191 if (RevBranch) {

1193 return false;

1194 }

1197 return false;

1198 }

1199

1200 return true;

1201}

1202

1203

1204

1205void IfConverter::AnalyzeBlock(

1207 struct BBState {

1210

1211

1212 bool SuccsAnalyzed = false;

1213 };

1214

1215

1217

1218 while (!BBStack.empty()) {

1219 BBState &State = BBStack.back();

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

1222

1223 if (!State.SuccsAnalyzed) {

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

1225 BBStack.pop_back();

1226 continue;

1227 }

1228

1229 BBI.BB = BB;

1230 BBI.IsBeingAnalyzed = true;

1231

1232 AnalyzeBranches(BBI);

1235 ScanInstructions(BBI, Begin, End);

1236

1237

1238

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

1240 BBI.IsBeingAnalyzed = false;

1241 BBI.IsAnalyzed = true;

1242 BBStack.pop_back();

1243 continue;

1244 }

1245

1246

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

1248 BBI.IsBeingAnalyzed = false;

1249 BBI.IsAnalyzed = true;

1250 BBStack.pop_back();

1251 continue;

1252 }

1253

1254

1255 if (!BBI.FalseBB) {

1256 BBI.IsBeingAnalyzed = false;

1257 BBI.IsAnalyzed = true;

1258 BBStack.pop_back();

1259 continue;

1260 }

1261

1262

1263 State.SuccsAnalyzed = true;

1264 BBStack.push_back(*BBI.FalseBB);

1265 BBStack.push_back(*BBI.TrueBB);

1266 continue;

1267 }

1268

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

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

1271

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

1273 BBI.IsBeingAnalyzed = false;

1274 BBI.IsAnalyzed = true;

1275 BBStack.pop_back();

1276 continue;

1277 }

1278

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

1282

1283 unsigned Dups = 0;

1284 unsigned Dups2 = 0;

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

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

1287 bool Enqueued = false;

1288

1290

1291 if (CanRevCond) {

1292 BBInfo TrueBBICalc, FalseBBICalc;

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

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

1295 Dups + Dups2, Prediction, Forked);

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

1297 false, false,

1298 true);

1299 bool FalseFeasible = FeasibilityAnalysis(FalseBBI, RevCond,

1300 false, false,

1301 true);

1302 return MeetsSize && TrueFeasible && FalseFeasible;

1303 };

1304

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

1306 TrueBBICalc, FalseBBICalc)) {

1307 if (feasibleDiamond(false)) {

1308

1309

1310

1311

1312

1313

1314

1315

1316 Tokens.push_back(std::make_unique(

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

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

1319 Enqueued = true;

1320 }

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

1322 TrueBBICalc, FalseBBICalc)) {

1323 if (feasibleDiamond(true)) {

1324

1325

1326

1327

1328

1329

1330

1331

1332

1333

1334 Tokens.push_back(std::make_unique(

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

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

1337 Enqueued = true;

1338 }

1339 }

1340 }

1341

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

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

1344 TrueBBI.ExtraCost2, Prediction) &&

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

1346

1347

1348

1349

1350

1351

1352

1353 Tokens.push_back(

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

1355 Enqueued = true;

1356 }

1357

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

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

1360 TrueBBI.ExtraCost2, Prediction) &&

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

1362 Tokens.push_back(

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

1364 Enqueued = true;

1365 }

1366

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

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

1369 TrueBBI.ExtraCost2, Prediction) &&

1370 FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {

1371

1372

1373

1374

1375

1376

1377

1378 Tokens.push_back(

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

1380 Enqueued = true;

1381 }

1382

1383 if (CanRevCond) {

1384

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

1387 MeetIfcvtSizeLimit(*FalseBBI.BB,

1388 FalseBBI.NonPredSize + FalseBBI.ExtraCost,

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

1390 FeasibilityAnalysis(FalseBBI, RevCond, true)) {

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

1392 FNeedSub, Dups));

1393 Enqueued = true;

1394 }

1395

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

1398 MeetIfcvtSizeLimit(*FalseBBI.BB,

1399 FalseBBI.NonPredSize + FalseBBI.ExtraCost,

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

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

1402 Tokens.push_back(

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

1404 Enqueued = true;

1405 }

1406

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

1408 MeetIfcvtSizeLimit(*FalseBBI.BB,

1409 FalseBBI.NonPredSize + FalseBBI.ExtraCost,

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

1411 FeasibilityAnalysis(FalseBBI, RevCond)) {

1412 Tokens.push_back(

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

1414 Enqueued = true;

1415 }

1416 }

1417

1418 BBI.IsEnqueued = Enqueued;

1419 BBI.IsBeingAnalyzed = false;

1420 BBI.IsAnalyzed = true;

1421 BBStack.pop_back();

1422 }

1423}

1424

1425

1426void IfConverter::AnalyzeBlocks(

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

1429 AnalyzeBlock(MBB, Tokens);

1430

1431

1433}

1434

1435

1436

1442 while (I != TI) {

1443

1444

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

1446 return false;

1447 PI = I++;

1448 }

1449

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

1451}

1452

1453

1454

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

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

1459 continue;

1460 PBBI.IsAnalyzed = false;

1461 PBBI.IsEnqueued = false;

1462 }

1463}

1464

1465

1468 DebugLoc dl;

1471}

1472

1473

1474

1477

1478

1479

1480

1483 for (unsigned Reg : Redefs)

1484 LiveBeforeMI.insert(Reg);

1485

1488

1489

1490 for (auto Clobber : Clobbers) {

1491

1492

1493 unsigned Reg = Clobber.first;

1497 if (Op.isRegMask()) {

1498

1499

1500 if (LiveBeforeMI.count(Reg))

1502

1503

1504

1505

1506

1507

1509 continue;

1510 }

1511 if (any_of(TRI->subregs_inclusive(Reg),

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

1514 }

1515}

1516

1517

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

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

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

1521 BBInfo *CvtBBI = &TrueBBI;

1522 BBInfo *NextBBI = &FalseBBI;

1523

1525 if (Kind == ICSimpleFalse)

1527

1530 if (CvtBBI->IsDone ||

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

1532

1533 BBI.IsAnalyzed = false;

1534 CvtBBI->IsAnalyzed = false;

1535 return false;

1536 }

1537

1539

1540 return false;

1541

1542 if (Kind == ICSimpleFalse)

1545

1547

1548 if (MRI->tracksLiveness()) {

1549

1550

1553 }

1554

1555

1556

1558

1560

1561

1562 CopyAndPredicateBlock(BBI, *CvtBBI, Cond);

1563

1564

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

1566 } else {

1567

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

1569

1570

1571

1572 MergeBlocks(BBI, *CvtBBI);

1573 }

1574

1575 bool IterIfcvt = true;

1578 BBI.HasFallThrough = false;

1579

1580

1581

1582

1583

1584

1585

1586

1587

1588

1589 IterIfcvt = false;

1590 }

1591

1592

1593 if (!IterIfcvt)

1594 BBI.IsDone = true;

1595 InvalidatePreds(*BBI.BB);

1596 CvtBBI->IsDone = true;

1597

1598

1599 return true;

1600}

1601

1602

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

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

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

1606 BBInfo *CvtBBI = &TrueBBI;

1607 BBInfo *NextBBI = &FalseBBI;

1608 DebugLoc dl;

1609

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

1613

1616 if (CvtBBI->IsDone ||

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

1618

1619 BBI.IsAnalyzed = false;

1620 CvtBBI->IsAnalyzed = false;

1621 return false;

1622 }

1623

1625

1626 return false;

1627

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

1631

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

1633 if (reverseBranchCondition(*CvtBBI)) {

1634

1635

1637 if (PBB == BBI.BB)

1638 continue;

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

1640 if (PBBI.IsEnqueued) {

1641 PBBI.IsAnalyzed = false;

1642 PBBI.IsEnqueued = false;

1643 }

1644 }

1645 }

1646 }

1647

1648

1649

1651 if (MRI->tracksLiveness()) {

1654 }

1655

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

1658

1659 if (HasEarlyExit) {

1660

1665 }

1666

1667

1668

1670

1672

1673

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

1675 } else {

1676

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

1679

1680

1681 MergeBlocks(BBI, *CvtBBI, false);

1682 }

1683

1684

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

1686

1687

1688 if (HasEarlyExit) {

1690 CvtBBI->BrCond.end());

1693

1694

1695

1696

1697

1698

1699

1701 auto NewNext = BBNext + BBCvt * CvtNext;

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

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

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

1705

1706 auto NewFalse = BBCvt * CvtFalse;

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

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

1709 }

1710

1711

1712

1713 bool FalseBBDead = false;

1714 bool IterIfcvt = true;

1716 if (!isFallThrough) {

1717

1718

1719

1720 if (!HasEarlyExit &&

1721 NextMBB.pred_size() == 1 && !NextBBI->HasFallThrough &&

1723 MergeBlocks(BBI, *NextBBI);

1724 FalseBBDead = true;

1725 } else {

1727 BBI.HasFallThrough = false;

1728 }

1729

1730

1731 IterIfcvt = false;

1732 }

1733

1734

1735 if (!IterIfcvt)

1736 BBI.IsDone = true;

1737 InvalidatePreds(*BBI.BB);

1738 CvtBBI->IsDone = true;

1739 if (FalseBBDead)

1740 NextBBI->IsDone = true;

1741

1742

1743 return true;

1744}

1745

1746

1747

1748

1749

1750

1751

1752

1753

1754

1755

1756

1757bool IfConverter::IfConvertDiamondCommon(

1758 BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,

1759 unsigned NumDups1, unsigned NumDups2,

1760 bool TClobbersPred, bool FClobbersPred,

1761 bool RemoveBranch, bool MergeAddEdges) {

1762

1763 if (TrueBBI.IsDone || FalseBBI.IsDone ||

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

1765

1766 BBI.IsAnalyzed = false;

1767 TrueBBI.IsAnalyzed = false;

1768 FalseBBI.IsAnalyzed = false;

1769 return false;

1770 }

1771

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

1773

1774 return false;

1775

1776

1777

1778

1779 BBInfo *BBI1 = &TrueBBI;

1780 BBInfo *BBI2 = &FalseBBI;

1786

1787

1788 bool DoSwap = false;

1789 if (TClobbersPred && !FClobbersPred)

1790 DoSwap = true;

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

1792 if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)

1793 DoSwap = true;

1794 } else if (TClobbersPred && FClobbersPred)

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

1796 if (DoSwap) {

1799 }

1800

1801

1803

1806

1807

1808

1809

1810

1811

1812

1814 if (MRI->tracksLiveness()) {

1817 }

1818

1819

1820

1823 BBI1->NonPredSize -= NumDups1;

1824 BBI2->NonPredSize -= NumDups1;

1825

1826

1827

1828

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

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

1831 break;

1832 if (!DI1->isDebugInstr())

1833 ++i;

1834 }

1835 while (NumDups1 != 0) {

1836

1837

1838 if (DI2->shouldUpdateAdditionalCallInfo())

1840

1841 ++DI2;

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

1843 break;

1844 if (!DI2->isDebugInstr())

1845 --NumDups1;

1846 }

1847

1848 if (MRI->tracksLiveness()) {

1852 }

1853 }

1854

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

1857

1858

1859

1860

1861

1862

1863

1864#ifndef NDEBUG

1865

1866 if (!BBI1->IsBrAnalyzable)

1868#endif

1869

1870

1871 DI1 = MBB1.end();

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

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

1875 break;

1876 DI1 = Prev;

1877 }

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

1879

1880

1882

1883 --DI1;

1884

1885

1886

1887 if (DI1->shouldUpdateAdditionalCallInfo())

1889

1890

1891 if (!DI1->isDebugInstr())

1892 ++i;

1893 }

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

1895

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

1897

1898

1899 if (RemoveBranch)

1901 else {

1902

1903

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

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

1907 break;

1908 DI2 = Prev;

1909 }

1910 }

1911 while (NumDups2 != 0) {

1912

1913

1915 --DI2;

1916

1917 if (!DI2->isDebugInstr())

1918 --NumDups2;

1919 }

1920

1921

1922

1923

1924

1925

1926

1927

1928

1931 if (TII->isProfitableToUnpredicate(MBB1, MBB2)) {

1933 if (FI.isDebugInstr())

1934 continue;

1937 if (!MO.isReg())

1938 continue;

1940 if (!Reg)

1941 continue;

1942 if (MO.isDef()) {

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

1945

1946

1949 }

1950 }

1951

1953 if (!ExtUses.count(Reg)) {

1956 }

1957 }

1958 }

1959 }

1960

1961

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

1963

1964

1965

1966

1967

1968

1969

1970

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

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

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

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

1977 --DI2;

1978 }

1979

1980

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

1982

1983

1984 MergeBlocks(BBI, *BBI1, MergeAddEdges);

1985 MergeBlocks(BBI, *BBI2, MergeAddEdges);

1986 return true;

1987}

1988

1989

1990

1991bool IfConverter::IfConvertForkedDiamond(

1992 BBInfo &BBI, IfcvtKind Kind,

1993 unsigned NumDups1, unsigned NumDups2,

1994 bool TClobbersPred, bool FClobbersPred) {

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

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

1997

1998

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

2002 dl = TIE->getDebugLoc();

2003

2004

2005

2006 if (!IfConvertDiamondCommon(

2007 BBI, TrueBBI, FalseBBI,

2008 NumDups1, NumDups2,

2009 TClobbersPred, FClobbersPred,

2010 true, true))

2011 return false;

2012

2013

2014

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

2016 TrueBBI.BrCond, dl);

2017

2018

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

2020 InvalidatePreds(*BBI.BB);

2021

2022

2023 return true;

2024}

2025

2026

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

2028 unsigned NumDups1, unsigned NumDups2,

2029 bool TClobbersPred, bool FClobbersPred) {

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

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

2033

2034

2035 if (!TailBB) {

2036 if (blockAlwaysFallThrough(TrueBBI))

2037 TailBB = FalseBBI.TrueBB;

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

2039 }

2040

2041 if (!IfConvertDiamondCommon(

2042 BBI, TrueBBI, FalseBBI,

2043 NumDups1, NumDups2,

2044 TClobbersPred, FClobbersPred,

2045 TrueBBI.IsBrAnalyzable,

2046 TailBB == nullptr))

2047 return false;

2048

2049

2050

2051

2052

2053 if (TailBB) {

2054

2055

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

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

2058

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

2060 bool CanMergeTail = !TailBBI.HasFallThrough &&

2061 !TailBBI.BB->hasAddressTaken();

2062

2063

2064

2067 CanMergeTail = false;

2068

2069

2070 unsigned NumPreds = TailBB->pred_size();

2071 if (NumPreds > 1)

2072 CanMergeTail = false;

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

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

2076 CanMergeTail = false;

2077 }

2078 if (CanMergeTail) {

2079 MergeBlocks(BBI, TailBBI);

2080 TailBBI.IsDone = true;

2081 } else {

2084 BBI.HasFallThrough = false;

2085 }

2086 }

2087

2088

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

2090 InvalidatePreds(*BBI.BB);

2091

2092

2093 return true;

2094}

2095

2098 bool SawStore = true;

2099 if (.isSafeToMove(SawStore))

2100 return false;

2101

2103 if (!MO.isReg())

2104 continue;

2106 if (!Reg)

2107 continue;

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

2109 return false;

2110 }

2111

2112 return true;

2113}

2114

2115

2116

2117void IfConverter::PredicateBlock(BBInfo &BBI,

2121 bool AnyUnpred = false;

2122 bool MaySpec = LaterRedefs != nullptr;

2125 continue;

2126

2127

2128

2130 AnyUnpred = true;

2131 continue;

2132 }

2133

2134

2135 MaySpec = false;

2137#ifndef NDEBUG

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

2139#endif

2141 }

2142

2143

2144

2146 }

2147

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

2149

2150 BBI.IsAnalyzed = false;

2151 BBI.NonPredSize = 0;

2152

2153 ++NumIfConvBBs;

2154 if (AnyUnpred)

2155 ++NumUnpred;

2156}

2157

2158

2159

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

2162 bool IgnoreBr) {

2164

2167

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

2169 break;

2170

2172

2173 if (I.isCandidateForAdditionalCallInfo())

2175

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

2177 ToBBI.NonPredSize++;

2178 unsigned ExtraPredCost = TII->getPredicationCost(I);

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

2180 if (NumCycles > 1)

2181 ToBBI.ExtraCost += NumCycles-1;

2182 ToBBI.ExtraCost2 += ExtraPredCost;

2183

2186#ifndef NDEBUG

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

2188#endif

2190 }

2191 }

2192

2193

2194

2196 }

2197

2198 if (!IgnoreBr) {

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

2200 FromMBB.succ_end());

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

2203

2205

2206 if (Succ == FallThrough)

2207 continue;

2208 ToBBI.BB->addSuccessor(Succ);

2209 }

2210 }

2211

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

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

2214

2215 ToBBI.ClobbersPred |= FromBBI.ClobbersPred;

2216 ToBBI.IsAnalyzed = false;

2217

2218 ++NumDupBBs;

2219}

2220

2221

2222

2223

2224

2225

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

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

2230

2231

2232

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

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

2239

2240

2241

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

2245

2246

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

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

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

2250

2251

2252

2253

2254

2255 if (ToBBI.IsBrAnalyzable)

2256 ToBBI.BB->normalizeSuccProbs();

2257

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

2261

2262

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

2265

2266

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

2269 }

2270

2272

2273 if (Succ == FallThrough) {

2274 FromMBB.removeSuccessor(Succ);

2275 continue;

2276 }

2277

2279 if (AddEdges) {

2280

2281

2282

2283

2285

2286

2287

2288

2289

2290

2291 if (!To2FromProb.isZero())

2292 NewProb *= To2FromProb;

2293 }

2294

2295 FromMBB.removeSuccessor(Succ);

2296

2297 if (AddEdges) {

2298

2299

2300

2301

2302

2303

2304

2305

2306

2307

2308

2309

2310

2311

2312

2313

2314

2315

2316

2317

2318

2319

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

2321 ToBBI.BB->setSuccProbability(

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

2324 else

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

2326 }

2327 }

2328

2329

2330

2332 if (Last != &FromMBB)

2333 FromMBB.moveAfter(Last);

2334

2335

2336

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

2338 ToBBI.BB->normalizeSuccProbs();

2339

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

2341 FromBBI.Predicate.clear();

2342

2343 ToBBI.NonPredSize += FromBBI.NonPredSize;

2344 ToBBI.ExtraCost += FromBBI.ExtraCost;

2345 ToBBI.ExtraCost2 += FromBBI.ExtraCost2;

2346 FromBBI.NonPredSize = 0;

2347 FromBBI.ExtraCost = 0;

2348 FromBBI.ExtraCost2 = 0;

2349

2350 ToBBI.ClobbersPred |= FromBBI.ClobbersPred;

2351 ToBBI.HasFallThrough = FromBBI.HasFallThrough;

2352 ToBBI.IsAnalyzed = false;

2353 FromBBI.IsAnalyzed = false;

2354}

2355

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

2359}

unsigned const MachineRegisterInfo * MRI

const HexagonInstrInfo * TII

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.

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.

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

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.

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

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

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

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

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

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

unsigned const TargetRegisterInfo * TRI

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB

const SmallVectorImpl< MachineOperand > & Cond

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

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.

Represent the analysis usage information of a pass.

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

This class represents an Operation in the Expression.

FunctionPass class - This class is used to implement most global optimizations.

bool hasMinSize() const

Optimize this function for minimum size (-Oz).

A possibly irreducible generalization of a Loop.

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

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

bool isPredicated(const MachineInstr &MI) const override

Returns true if the instruction is already predicated.

bool ClobbersPredicate(MachineInstr &MI, std::vector< MachineOperand > &Pred, bool SkipDead) const override

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

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

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

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

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

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

Insert branch code into the end of the specified MachineBasicBlock.

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

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

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

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

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

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

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

Convert the instruction into a predicated instruction.

bool isPredicable(const MachineInstr &MI) const override

Return true if the specified instruction can be predicated.

A set of 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

int getNumber() const

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

iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)

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

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

const MachineFunction * getParent() const

Return the MachineFunction containing this basic block.

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

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.

virtual bool runOnMachineFunction(MachineFunction &MF)=0

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

virtual MachineFunctionProperties getRequiredProperties() const

Properties which a MachineFunction may have at a given point in time.

MachineFunctionProperties & set(Property P)

Function & getFunction()

Return the LLVM function that this machine code represents.

void eraseAdditionalCallInfo(const MachineInstr *MI)

Following functions update call site info.

MachineInstr * CloneMachineInstr(const MachineInstr *Orig)

Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...

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.

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.

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

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

std::pair< const_iterator, bool > insert(const T &V)

insert - Insert an element into the set if it isn't already there.

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

void push_back(const T &Elt)

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

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

size_type count(const KeyT &Key) const

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

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

insert - Attempts to insert a new element.

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.

This base class for TargetLowering contains the SelectionDAG-independent parts that can be used from ...

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

Provide an instruction scheduling machine model to CodeGen passes.

void init(const TargetSubtargetInfo *TSInfo)

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)

unsigned ID

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

Predicate

Predicate - These are "(BI << 5) | BO" for various predicates.

@ Implicit

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

@ Define

Reg

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

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.

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

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

void initializeIfConverterPass(PassRegistry &)

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.

raw_ostream & dbgs()

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

void recomputeLivenessFlags(MachineBasicBlock &MBB)

Recomputes dead and kill flags in MBB.

OutputIt move(R &&Range, OutputIt Out)

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

char & IfConverterID

IfConverter - This pass performs machine code if conversion.

Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

Implement std::hash so that hash_code can be used in STL containers.

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

Implement std::swap in terms of BitVector swap.