BranchFolding.cpp Source File (original) (raw)

45#include "llvm/Config/llvm-config.h"

60#include

61#include

62#include

63#include

65using namespace llvm;

67#define DEBUG_TYPE "branch-folder"

69 STATISTIC(NumDeadBlocks, "Number of dead blocks removed");

70 STATISTIC(NumBranchOpts, "Number of branches optimized");

71 STATISTIC(NumTailMerge , "Number of block tails merged");

72 STATISTIC(NumHoist , "Number of times common instructions are hoisted");

73 STATISTIC(NumTailCalls, "Number of tail calls optimized");

81 cl::desc("Max number of predecessors to consider tail merging"),

87 cl::desc("Min number of instructions to consider tail merging"),

90namespace {

94public:

95 static char ID;

99 bool runOnMachineFunction(MachineFunction &MF) override;

100

101 void getAnalysisUsage(AnalysisUsage &AU) const override {

102 AU.addRequired();

103 AU.addRequired();

104 AU.addRequired();

107 }

108

109 MachineFunctionProperties getRequiredProperties() const override {

110 return MachineFunctionProperties().setNoPHIs();

111 }

112};

113

114}

115

116char BranchFolderLegacy::ID = 0;

117

119

121 false)

122

126 bool EnableTailMerge =

127 !MF.getTarget().requiresStructuredCFG() && this->EnableTailMerge;

128

131 .getCachedResult(

132 *MF.getFunction().getParent());

133 if (!PSI)

135 "ProfileSummaryAnalysis is required for BranchFoldingPass", false);

136

139 BranchFolder Folder(EnableTailMerge, true, MBBFreqInfo, MBPI,

140 PSI);

141 if (!Folder.OptimizeFunction(MF, MF.getSubtarget().getInstrInfo(),

142 MF.getSubtarget().getRegisterInfo()))

145}

146

147bool BranchFolderLegacy::runOnMachineFunction(MachineFunction &MF) {

149 return false;

150

151 TargetPassConfig *PassConfig = &getAnalysis();

152

153

156 MBFIWrapper MBBFreqInfo(

157 getAnalysis().getMBFI());

159 EnableTailMerge, true, MBBFreqInfo,

160 getAnalysis().getMBPI(),

161 &getAnalysis().getPSI());

164}

165

170 : EnableHoistCommonCode(CommonHoist), MinCommonTailLength(MinTailLength),

171 MBBFreqInfo(FreqInfo), MBPI(ProbInfo), PSI(PSI) {

174 EnableTailMerge = DefaultEnableTailMerge;

175 break;

176 case cl::BOU_TRUE: EnableTailMerge = true; break;

177 case cl::BOU_FALSE: EnableTailMerge = false; break;

178 }

179}

180

182 assert(MBB->pred_empty() && "MBB must be dead!");

184

186

187 while ( MBB ->succ_empty())

188 MBB->removeSuccessor(MBB->succ_end()-1);

189

190

191 TriedMerging.erase(MBB);

192

193

195 if (MI.shouldUpdateAdditionalCallInfo())

197

198

200 EHScopeMembership.erase(MBB);

201 if (MLI)

203}

204

209 if (!tii) return false;

210

211 TriedMerging.clear();

212

214 AfterBlockPlacement = AfterPlacement;

215 TII = tii;

216 TRI = tri;

217 MLI = mli;

218 this->MRI = &MRI;

219

220 if (MinCommonTailLength == 0) {

221 MinCommonTailLength = TailMergeSize.getNumOccurrences() > 0

223 : TII->getTailMergeSize(MF);

224 }

225

226 UpdateLiveIns = MRI.tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF);

227 if (!UpdateLiveIns)

228 MRI.invalidateLiveness();

229

230 bool MadeChange = false;

231

232

234

235 bool MadeChangeThisIteration = true;

236 while (MadeChangeThisIteration) {

237 MadeChangeThisIteration = TailMergeBlocks(MF);

238

239

240 if (!AfterBlockPlacement || MadeChangeThisIteration)

241 MadeChangeThisIteration |= OptimizeBranches(MF);

242 if (EnableHoistCommonCode)

243 MadeChangeThisIteration |= HoistCommonCode(MF);

244 MadeChange |= MadeChangeThisIteration;

245 }

246

247

248

250 if (!JTI)

251 return MadeChange;

252

253

258 if (.isJTI()) continue;

259

260

261 JTIsLive.set(Op.getIndex());

262 }

263 }

264

265

266

267 for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i)

268 if (!JTIsLive.test(i)) {

270 MadeChange = true;

271 }

272

273 return MadeChange;

274}

275

276

277

278

279

280

282 unsigned Hash = MI.getOpcode();

283 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {

285

286

287

288

289 unsigned OperandHash = 0;

290 switch (Op.getType()) {

292 OperandHash = Op.getReg().id();

293 break;

295 OperandHash = Op.getImm();

296 break;

298 OperandHash = Op.getMBB()->getNumber();

299 break;

303 OperandHash = Op.getIndex();

304 break;

307

308

309 OperandHash = Op.getOffset();

310 break;

311 default:

312 break;

313 }

314

315 Hash += ((OperandHash << 3) | Op.getType()) << (i & 31);

316 }

317 return Hash;

318}

319

320

323 if (I == MBB.end())

324 return 0;

325

327}

328

329

331 return !(MI.isDebugInstr() || MI.isCFIInstruction());

332}

333

334

335

336

340 while (I != MBB->begin()) {

341 --I;

343 return I;

344 }

345 return MBB->end();

346}

347

348

349

350

351

352

353

360

361 unsigned TailLen = 0;

362 while (true) {

365 if (MBBI1 == MBB1->end() || MBBI2 == MBB2->end())

366 break;

367 if (!MBBI1->isIdenticalTo(*MBBI2) ||

368

369

370

371

372

373 MBBI1->isInlineAsm()) {

374 break;

375 }

378 break;

379 ++TailLen;

380 I1 = MBBI1;

381 I2 = MBBI2;

382 }

383

384 return TailLen;

385}

386

389 if (UpdateLiveIns) {

390

391 MachineBasicBlock &OldMBB = *OldInst->getParent();

392 LiveRegs.clear();

393 LiveRegs.addLiveOuts(OldMBB);

394

396 do {

397 --I;

398 LiveRegs.stepBackward(*I);

399 } while (I != OldInst);

400

401

402

403

404 for (MachineBasicBlock::RegisterMaskPair P : NewDest.liveins()) {

405

406

408 "Can only handle full register.");

409 MCRegister Reg = P.PhysReg;

410 if (!LiveRegs.available(*MRI, Reg))

411 continue;

413 BuildMI(OldMBB, OldInst, DL, TII->get(TargetOpcode::IMPLICIT_DEF), Reg);

414 }

415 }

416

417 TII->ReplaceTailWithBranchTo(OldInst, &NewDest);

418 ++NumTailMerge;

419}

420

424 if (!TII->isLegalToSplitMBBAt(CurMBB, BBI1))

425 return nullptr;

426

427 MachineFunction &MF = *CurMBB.getParent();

428

429

433

434

436

437

439

440

441 NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end());

442

443

444 if (MLI)

445 if (MachineLoop *ML = MLI->getLoopFor(&CurMBB))

446 ML->addBasicBlockToLoop(NewMBB, *MLI);

447

448

449 MBBFreqInfo.setBlockFreq(NewMBB, MBBFreqInfo.getBlockFreq(&CurMBB));

450

451 if (UpdateLiveIns)

453

454

455 const auto &EHScopeI = EHScopeMembership.find(&CurMBB);

456 if (EHScopeI != EHScopeMembership.end()) {

457 auto n = EHScopeI->second;

458 EHScopeMembership[NewMBB] = n;

459 }

460

461 return NewMBB;

462}

463

464

465

468 unsigned Time = 0;

469 for (; I != E; ++I) {

471 continue;

472 if (I->isCall())

473 Time += 10;

474 else if (I->mayLoadOrStore())

475 Time += 2;

476 else

477 ++Time;

478 }

479 return Time;

480}

481

482

483

484

485

493 if (!dl)

494 dl = BranchDL;

495 if (I != MF->end() && TII ->analyzeBranch(*CurMBB, TBB, FBB, Cond, true)) {

497 if (TBB == NextBB && Cond .empty() && !FBB) {

498 if ( TII ->reverseBranchCondition(Cond)) {

499 TII->removeBranch(*CurMBB);

500 TII->insertBranch(*CurMBB, SuccBB, nullptr, Cond, dl);

501 return;

502 }

503 }

504 }

505 TII->insertBranch(*CurMBB, SuccBB, nullptr,

507}

508

509bool

510BranchFolder::MergePotentialsElt::operator<(const MergePotentialsElt &o) const {

511 if (getHash() < o.getHash())

512 return true;

513 if (getHash() > o.getHash())

514 return false;

515 if (getBlock()->getNumber() < o.getBlock()->getNumber())

516 return true;

517 if (getBlock()->getNumber() > o.getBlock()->getNumber())

518 return false;

519 return false;

520}

521

522

523

524

527 I = MBB->end();

528 unsigned NumTerms = 0;

529 while (true) {

530 if (I == MBB->begin()) {

531 I = MBB->end();

532 break;

533 }

534 --I;

535 if (->isTerminator()) break;

536 ++NumTerms;

537 }

538 return NumTerms;

539}

540

541

542

543

545 if ( MBB ->succ_empty())

546 return false;

547 if (MBB->empty())

548 return true;

549 return !(MBB->back().isReturn() || MBB->back().isIndirectBranch());

550}

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568static bool

570 unsigned MinCommonTailLength, unsigned &CommonTailLen,

575 bool AfterPlacement,

578

579 if (!EHScopeMembership.empty()) {

580 auto EHScope1 = EHScopeMembership.find(MBB1);

581 assert(EHScope1 != EHScopeMembership.end());

582 auto EHScope2 = EHScopeMembership.find(MBB2);

583 assert(EHScope2 != EHScopeMembership.end());

584 if (EHScope1->second != EHScope2->second)

585 return false;

586 }

587

589 if (CommonTailLen == 0)

590 return false;

593 << CommonTailLen << '\n');

594

595

596

597

599 I1 = MBB1->begin();

601 I2 = MBB2->begin();

602

603 bool FullBlockTail1 = I1 == MBB1->begin();

604 bool FullBlockTail2 = I2 == MBB2->begin();

605

606

607

608

609

610

611 if ((MBB1 == PredBB || MBB2 == PredBB) &&

612 (!AfterPlacement || MBB1->succ_size() == 1)) {

614 unsigned NumTerms = CountTerminators(MBB1 == PredBB ? MBB2 : MBB1, I);

615 if (CommonTailLen > NumTerms)

616 return true;

617 }

618

619

620

621

622

623

624 if (FullBlockTail1 && FullBlockTail2 &&

626 return true;

627

628

629

630

631

633 return true;

635 return true;

636

637

638

639

640

641 if (AfterPlacement && FullBlockTail1 && FullBlockTail2) {

643 if ( MBB ->succ_empty() && MBB ->canFallThrough())

644 return false;

647 return (MBB != &*MF->begin()) && std::prev(I)->canFallThrough();

648 };

649 if (!BothFallThrough(MBB1) || !BothFallThrough(MBB2))

650 return true;

651 }

652

653

654

655

656

657

658 unsigned EffectiveTailLen = CommonTailLen;

659 if (SuccBB && MBB1 != PredBB && MBB2 != PredBB &&

660 (MBB1->succ_size() == 1 || !AfterPlacement) &&

663 ++EffectiveTailLen;

664

665

666 if (EffectiveTailLen >= MinCommonTailLength)

667 return true;

668

669

670

671

672

675 return EffectiveTailLen >= 2 && OptForSize &&

676 (FullBlockTail1 || FullBlockTail2);

677}

678

679unsigned BranchFolder::ComputeSameTails(unsigned CurHash,

680 unsigned MinCommonTailLength,

681 MachineBasicBlock *SuccBB,

682 MachineBasicBlock *PredBB) {

683 unsigned maxCommonTailLength = 0U;

684 SameTails.clear();

686 MPIterator HighestMPIter = std::prev(MergePotentials.end());

687 for (MPIterator CurMPIter = std::prev(MergePotentials.end()),

688 B = MergePotentials.begin();

689 CurMPIter != B && CurMPIter->getHash() == CurHash; --CurMPIter) {

690 for (MPIterator I = std::prev(CurMPIter); I->getHash() == CurHash; --I) {

691 unsigned CommonTailLen;

693 MinCommonTailLength,

694 CommonTailLen, TrialBBI1, TrialBBI2,

695 SuccBB, PredBB,

696 EHScopeMembership,

697 AfterBlockPlacement, MBBFreqInfo, PSI)) {

698 if (CommonTailLen > maxCommonTailLength) {

699 SameTails.clear();

700 maxCommonTailLength = CommonTailLen;

701 HighestMPIter = CurMPIter;

702 SameTails.push_back(SameTailElt(CurMPIter, TrialBBI1));

703 }

704 if (HighestMPIter == CurMPIter &&

705 CommonTailLen == maxCommonTailLength)

706 SameTails.push_back(SameTailElt(I, TrialBBI2));

707 }

708 if (I == B)

709 break;

710 }

711 }

712 return maxCommonTailLength;

713}

714

715void BranchFolder::RemoveBlocksWithHash(unsigned CurHash,

716 MachineBasicBlock *SuccBB,

717 MachineBasicBlock *PredBB,

719 MPIterator CurMPIter, B;

720 for (CurMPIter = std::prev(MergePotentials.end()),

721 B = MergePotentials.begin();

722 CurMPIter->getHash() == CurHash; --CurMPIter) {

723

724 MachineBasicBlock *CurMBB = CurMPIter->getBlock();

725 if (SuccBB && CurMBB != PredBB)

726 FixTail(CurMBB, SuccBB, TII, BranchDL);

727 if (CurMPIter == B)

728 break;

729 }

730 if (CurMPIter->getHash() != CurHash)

731 CurMPIter++;

732 MergePotentials.erase(CurMPIter, MergePotentials.end());

733}

734

735bool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,

736 MachineBasicBlock *SuccBB,

737 unsigned maxCommonTailLength,

738 unsigned &commonTailIndex) {

739 commonTailIndex = 0;

740 unsigned TimeEstimate = ~0U;

741 for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {

742

743 if (SameTails[i].getBlock() == PredBB) {

744 commonTailIndex = i;

745 break;

746 }

747

748

750 SameTails[i].getTailStartPos());

751 if (t <= TimeEstimate) {

752 TimeEstimate = t;

753 commonTailIndex = i;

754 }

755 }

756

758 SameTails[commonTailIndex].getTailStartPos();

759 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();

760

762 << maxCommonTailLength);

763

764

765

766

769 MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI, BB);

770 if (!newMBB) {

772 return false;

773 }

774

775 SameTails[commonTailIndex].setBlock(newMBB);

776 SameTails[commonTailIndex].setTailStartPos(newMBB->begin());

777

778

779 if (PredBB == MBB)

780 PredBB = newMBB;

781

782 return true;

783}

784

785static void

789

790

791

792 unsigned CommonTailLen = 0;

793 for (auto E = MBB->end(); MBBIStartPos != E; ++MBBIStartPos)

794 ++CommonTailLen;

795

800

801 while (CommonTailLen--) {

802 assert(MBBI != MBBIE && "Reached BB end within common tail length!");

803 (void)MBBIE;

804

807 continue;

808 }

809

811 ++MBBICommon;

812

813 assert(MBBICommon != MBBIECommon &&

814 "Reached BB end within common tail length!");

815 assert(MBBICommon->isIdenticalTo(*MBBI) && "Expected matching MIIs!");

816

817

818 if (MBBICommon->mayLoadOrStore())

819 MBBICommon->cloneMergedMemRefs(*MBB->getParent(), {&*MBBICommon, &*MBBI});

820

821 for (unsigned I = 0, E = MBBICommon->getNumOperands(); I != E; ++I) {

827 }

828 }

829

831 ++MBBICommon;

832 }

833}

834

835void BranchFolder::mergeCommonTails(unsigned commonTailIndex) {

836 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();

837

838 std::vectorMachineBasicBlock::iterator NextCommonInsts(SameTails.size());

839 for (unsigned int i = 0 ; i != SameTails.size() ; ++i) {

840 if (i != commonTailIndex) {

841 NextCommonInsts[i] = SameTails[i].getTailStartPos();

843 } else {

844 assert(SameTails[i].getTailStartPos() == MBB->begin() &&

845 "MBB is not a common tail only block");

846 }

847 }

848

849 for (auto &MI : *MBB) {

851 continue;

853 for (unsigned int i = 0 ; i < NextCommonInsts.size() ; i++) {

854 if (i == commonTailIndex)

855 continue;

856

857 auto &Pos = NextCommonInsts[i];

858 assert(Pos != SameTails[i].getBlock()->end() &&

859 "Reached BB end within common tail");

861 ++Pos;

862 assert(Pos != SameTails[i].getBlock()->end() &&

863 "Reached BB end within common tail");

864 }

865 assert(MI.isIdenticalTo(*Pos) && "Expected matching MIIs!");

867 NextCommonInsts[i] = ++Pos;

868 }

869 MI.setDebugLoc(DL);

870 }

871

872 if (UpdateLiveIns) {

873 LivePhysRegs NewLiveIns(*TRI);

875 LiveRegs.init(*TRI);

876

877

878

880 LiveRegs.clear();

881 LiveRegs.addLiveOuts(*Pred);

884 if (!LiveRegs.available(*MRI, Reg))

885 continue;

886

887

888

890 return NewLiveIns.contains(SReg) && !MRI->isReserved(SReg);

891 }))

892 continue;

893

895 BuildMI(*Pred, InsertBefore, DL, TII->get(TargetOpcode::IMPLICIT_DEF),

897 }

898 }

899

902 }

903}

904

905

906

907

908

909

910

911

912

913

914bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB,

915 MachineBasicBlock *PredBB,

916 unsigned MinCommonTailLength) {

917 bool MadeChange = false;

918

920 dbgs() << "\nTryTailMergeBlocks: ";

921 for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i)

923 << (i == e - 1 ? "" : ", ");

924 dbgs() << "\n";

925 if (SuccBB) {

927 if (PredBB)

929 << "\n";

930 }

931 dbgs() << "Looking for common tails of at least " << MinCommonTailLength

932 << " instruction" << (MinCommonTailLength == 1 ? "" : "s") << '\n';

933 });

934

935

936

937#if LLVM_ENABLE_DEBUGLOC_TRACKING_ORIGIN

938

939

940 std::sort(MergePotentials.begin(), MergePotentials.end());

941#else

942 array_pod_sort(MergePotentials.begin(), MergePotentials.end());

943#endif

944

945

946 while (MergePotentials.size() > 1) {

947 unsigned CurHash = MergePotentials.back().getHash();

948 const DebugLoc &BranchDL = MergePotentials.back().getBranchDebugLoc();

949

950

951

952 unsigned maxCommonTailLength = ComputeSameTails(CurHash,

953 MinCommonTailLength,

954 SuccBB, PredBB);

955

956

957

958 if (SameTails.empty()) {

959 RemoveBlocksWithHash(CurHash, SuccBB, PredBB, BranchDL);

960 continue;

961 }

962

963

964

965

966

967 MachineBasicBlock *EntryBB =

968 &MergePotentials.front().getBlock()->getParent()->front();

969 unsigned commonTailIndex = SameTails.size();

970

971

972 if (SameTails.size() == 2 &&

973 SameTails[0].getBlock()->isLayoutSuccessor(SameTails[1].getBlock()) &&

974 SameTails[1].tailIsWholeBlock() && !SameTails[1].getBlock()->isEHPad())

975 commonTailIndex = 1;

976 else if (SameTails.size() == 2 &&

977 SameTails[1].getBlock()->isLayoutSuccessor(

978 SameTails[0].getBlock()) &&

979 SameTails[0].tailIsWholeBlock() &&

980 !SameTails[0].getBlock()->isEHPad())

981 commonTailIndex = 0;

982 else {

983

984

985 for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {

986 MachineBasicBlock *MBB = SameTails[i].getBlock();

988 SameTails[i].tailIsWholeBlock())

989 continue;

990 if (MBB == PredBB) {

991 commonTailIndex = i;

992 break;

993 }

994 if (SameTails[i].tailIsWholeBlock())

995 commonTailIndex = i;

996 }

997 }

998

999 if (commonTailIndex == SameTails.size() ||

1000 (SameTails[commonTailIndex].getBlock() == PredBB &&

1001 !SameTails[commonTailIndex].tailIsWholeBlock())) {

1002

1003

1004 if (!CreateCommonTailOnlyBlock(PredBB, SuccBB,

1005 maxCommonTailLength, commonTailIndex)) {

1006 RemoveBlocksWithHash(CurHash, SuccBB, PredBB, BranchDL);

1007 continue;

1008 }

1009 }

1010

1011 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();

1012

1013

1014 setCommonTailEdgeWeights(*MBB);

1015

1016

1017

1018 mergeCommonTails(commonTailIndex);

1019

1020

1021

1023 << " for ");

1024 for (unsigned int i=0, e = SameTails.size(); i != e; ++i) {

1025 if (commonTailIndex == i)

1026 continue;

1028 << (i == e - 1 ? "" : ", "));

1029

1030 replaceTailWithBranchTo(SameTails[i].getTailStartPos(), *MBB);

1031

1032 MergePotentials.erase(SameTails[i].getMPIter());

1033 }

1035

1036

1037 MadeChange = true;

1038 }

1039 return MadeChange;

1040}

1041

1042bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {

1043 bool MadeChange = false;

1044 if (!EnableTailMerge)

1045 return MadeChange;

1046

1047

1048

1049 MergePotentials.clear();

1050 for (MachineBasicBlock &MBB : MF) {

1052 break;

1054 MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(MBB), &MBB,

1056 }

1057

1058

1059

1061 for (const MergePotentialsElt &Elt : MergePotentials)

1062 TriedMerging.insert(Elt.getBlock());

1063

1064

1065 if (MergePotentials.size() >= 2)

1066 MadeChange |= TryTailMergeBlocks(nullptr, nullptr, MinCommonTailLength);

1067

1068

1069

1070

1071

1072

1073

1074

1075

1076

1077

1078

1079

1080

1081

1082

1083

1084

1085

1086

1088 I != E; ++I) {

1089 if (I->pred_size() < 2) continue;

1090 SmallPtrSet<MachineBasicBlock *, 8> UniquePreds;

1091 MachineBasicBlock *IBB = &*I;

1092 MachineBasicBlock *PredBB = &*std::prev(I);

1093 MergePotentials.clear();

1094 MachineLoop *ML;

1095

1096

1097

1098

1099

1100

1101

1102

1103

1104

1105

1106 if (AfterBlockPlacement && MLI) {

1107 ML = MLI->getLoopFor(IBB);

1108 if (ML && IBB == ML->getHeader())

1109 continue;

1110 }

1111

1112 for (MachineBasicBlock *PBB : I->predecessors()) {

1114 break;

1115

1116 if (TriedMerging.count(PBB))

1117 continue;

1118

1119

1120 if (PBB == IBB)

1121 continue;

1122

1123

1124 if (!UniquePreds.insert(PBB).second)

1125 continue;

1126

1127

1128

1129 if (PBB->hasEHPadSuccessor() || PBB->mayHaveInlineAsmBr())

1130 continue;

1131

1132

1133

1134

1135 if (AfterBlockPlacement && MLI)

1136 if (ML != MLI->getLoopFor(PBB))

1137 continue;

1138

1139 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;

1141 if (!TII->analyzeBranch(*PBB, TBB, FBB, Cond, true)) {

1142

1143

1145 if ( Cond .empty() && TBB == IBB) {

1146 if (TII->reverseBranchCondition(NewCond))

1147 continue;

1148

1149 if (!FBB) {

1150 auto Next = ++PBB->getIterator();

1151 if (Next != MF.end())

1152 FBB = &*Next;

1153 }

1154 }

1155

1156

1157 DebugLoc dl = PBB->findBranchDebugLoc();

1158 if (TBB && (Cond.empty() || FBB)) {

1159 TII->removeBranch(*PBB);

1160 if ( Cond .empty())

1161

1162 TII->insertBranch(*PBB, (TBB == IBB) ? FBB : TBB, nullptr,

1163 NewCond, dl);

1164 }

1165

1166 MergePotentials.push_back(

1167 MergePotentialsElt(HashEndOfMBB(*PBB), PBB, dl));

1168 }

1169 }

1170

1171

1172

1174 for (MergePotentialsElt &Elt : MergePotentials)

1175 TriedMerging.insert(Elt.getBlock());

1176

1177 if (MergePotentials.size() >= 2)

1178 MadeChange |= TryTailMergeBlocks(IBB, PredBB, MinCommonTailLength);

1179

1180

1181

1182 PredBB = &*std::prev(I);

1183 if (MergePotentials.size() == 1 &&

1184 MergePotentials.begin()->getBlock() != PredBB)

1185 FixTail(MergePotentials.begin()->getBlock(), IBB, TII,

1186 MergePotentials.begin()->getBranchDebugLoc());

1187 }

1188

1189 return MadeChange;

1190}

1191

1192void BranchFolder::setCommonTailEdgeWeights(MachineBasicBlock &TailMBB) {

1194 BlockFrequency AccumulatedMBBFreq;

1195

1196

1197

1198

1199 for (const auto &Src : SameTails) {

1200 const MachineBasicBlock *SrcMBB = Src.getBlock();

1201 BlockFrequency BlockFreq = MBBFreqInfo.getBlockFreq(SrcMBB);

1202 AccumulatedMBBFreq += BlockFreq;

1203

1204

1205

1207 continue;

1208

1209 auto EdgeFreq = EdgeFreqLs.begin();

1210

1212 SuccI != SuccE; ++SuccI, ++EdgeFreq)

1213 *EdgeFreq += BlockFreq * MBPI.getEdgeProbability(SrcMBB, *SuccI);

1214 }

1215

1216 MBBFreqInfo.setBlockFreq(&TailMBB, AccumulatedMBBFreq);

1217

1219 return;

1220

1221 auto SumEdgeFreq =

1222 std::accumulate(EdgeFreqLs.begin(), EdgeFreqLs.end(), BlockFrequency(0))

1223 .getFrequency();

1224 auto EdgeFreq = EdgeFreqLs.begin();

1225

1226 if (SumEdgeFreq > 0) {

1228 SuccI != SuccE; ++SuccI, ++EdgeFreq) {

1230 EdgeFreq->getFrequency(), SumEdgeFreq);

1232 }

1233 }

1234}

1235

1236

1237

1238

1239

1240bool BranchFolder::OptimizeBranches(MachineFunction &MF) {

1241 bool MadeChange = false;

1242

1243

1245

1247

1248 for (MachineBasicBlock &MBB :

1250 MadeChange |= OptimizeBlock(&MBB);

1251

1252

1254 RemoveDeadBlock(&MBB);

1255 MadeChange = true;

1256 ++NumDeadBlocks;

1257 }

1258 }

1259

1260 return MadeChange;

1261}

1262

1263

1264

1266 return MBB->getFirstNonDebugInstr(true) == MBB->end();

1267}

1268

1269

1270

1273 assert(I != MBB->end() && "empty block!");

1274 return I->isBranch();

1275}

1276

1277

1278

1279

1280

1283 assert(MBB1 && MBB2 && "Unknown MachineBasicBlock");

1284

1285

1286

1287

1288

1291 if (MBB1I == MBB1->end() || MBB2I == MBB2->end())

1292 return false;

1293

1294

1295

1296 if (MBB1->isSuccessor(MBB2)) return true;

1297 if (MBB2->isSuccessor(MBB1)) return false;

1298

1299 return MBB2I->isCall() && !MBB1I->isCall();

1300}

1301

1307 if (MI.isDebugInstr()) {

1308 TII->duplicate(PredMBB, InsertBefore, MI);

1309 LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to pred: "

1310 << MI);

1311 }

1312}

1313

1319 if (MI.isDebugInstr()) {

1320 TII->duplicate(SuccMBB, InsertBefore, MI);

1321 LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to succ: "

1322 << MI);

1323 }

1324}

1325

1326

1327

1328

1329

1330

1331

1332

1336

1337

1341

1342

1343

1347}

1348

1349bool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {

1350 bool MadeChange = false;

1352ReoptimizeBlock:

1353

1355 ++FallThrough;

1356

1357

1358 bool SameEHScope = true;

1359 if (!EHScopeMembership.empty() && FallThrough != MF.end()) {

1360 auto MBBEHScope = EHScopeMembership.find(MBB);

1361 assert(MBBEHScope != EHScopeMembership.end());

1362 auto FallThroughEHScope = EHScopeMembership.find(&*FallThrough);

1363 assert(FallThroughEHScope != EHScopeMembership.end());

1364 SameEHScope = MBBEHScope->second == FallThroughEHScope->second;

1365 }

1366

1367

1368

1369 MachineBasicBlock *CurTBB = nullptr, *CurFBB = nullptr;

1371 bool CurUnAnalyzable =

1372 TII->analyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);

1373

1374

1375

1376

1377

1379 SameEHScope) {

1381

1383

1384 if (FallThrough == MF.end()) {

1385

1386 } else if (FallThrough->isEHPad()) {

1387

1388

1389

1390

1392

1393

1395 MachineBasicBlock *Pred = *(MBB->pred_end()-1);

1397 }

1398

1399

1400

1402 if (*SI != &*FallThrough && !FallThrough->isSuccessor(*SI)) {

1403 assert((*SI)->isEHPad() && "Bad CFG");

1404 FallThrough->copySuccessor(MBB, SI);

1405 }

1406

1407

1409 MJTI->ReplaceMBBInJumpTables(MBB, &*FallThrough);

1410 MadeChange = true;

1411 }

1412 return MadeChange;

1413 }

1414

1415

1416

1418

1419 MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;

1421 bool PriorUnAnalyzable =

1422 TII->analyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);

1423 if (!PriorUnAnalyzable) {

1424

1425

1426

1427 if (PriorTBB && PriorTBB == PriorFBB) {

1429 TII->removeBranch(PrevBB);

1430 PriorCond.clear();

1431 if (PriorTBB != MBB)

1432 TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, Dl);

1433 MadeChange = true;

1434 ++NumBranchOpts;

1435 goto ReoptimizeBlock;

1436 }

1437

1438

1439

1440

1441

1442

1443

1444

1448 LLVM_DEBUG(dbgs() << "\nMerging into block: " << PrevBB

1449 << "From MBB: " << *MBB);

1450

1451 if (!PrevBB.empty()) {

1453 --PrevBBIter;

1455

1456

1457 while (PrevBBIter != PrevBB.begin() && MBBIter != MBB->end()

1458 && PrevBBIter->isDebugInstr() && MBBIter->isDebugInstr()) {

1459 if (!MBBIter->isIdenticalTo(*PrevBBIter))

1460 break;

1461 MachineInstr &DuplicateDbg = *MBBIter;

1462 ++MBBIter; -- PrevBBIter;

1464 }

1465 }

1470 MadeChange = true;

1471 return MadeChange;

1472 }

1473

1474

1475

1476 if (PriorTBB == MBB && !PriorFBB) {

1477 TII->removeBranch(PrevBB);

1478 MadeChange = true;

1479 ++NumBranchOpts;

1480 goto ReoptimizeBlock;

1481 }

1482

1483

1484

1485 if (PriorFBB == MBB) {

1487 TII->removeBranch(PrevBB);

1488 TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, Dl);

1489 MadeChange = true;

1490 ++NumBranchOpts;

1491 goto ReoptimizeBlock;

1492 }

1493

1494

1495

1496

1497 if (PriorTBB == MBB) {

1499 if (!TII->reverseBranchCondition(NewPriorCond)) {

1501 TII->removeBranch(PrevBB);

1502 TII->insertBranch(PrevBB, PriorFBB, nullptr, NewPriorCond, Dl);

1503 MadeChange = true;

1504 ++NumBranchOpts;

1505 goto ReoptimizeBlock;

1506 }

1507 }

1508

1509

1510

1511

1512

1513

1514

1515

1516

1520 bool DoTransform = true;

1521

1522

1523

1524

1525

1526

1527 if (FallThrough == --MF.end() &&

1529 DoTransform = false;

1530

1531 if (DoTransform) {

1532

1534 if (!TII->reverseBranchCondition(NewPriorCond)) {

1536 << "To make fallthrough to: " << *PriorTBB << "\n");

1537

1539 TII->removeBranch(PrevBB);

1540 TII->insertBranch(PrevBB, MBB, nullptr, NewPriorCond, Dl);

1541

1542

1544 MadeChange = true;

1545 ++NumBranchOpts;

1546 return MadeChange;

1547 }

1548 }

1549 }

1550 }

1551

1554 if (TII->isUnconditionalTailCall(TailCall)) {

1557 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;

1559 bool PredAnalyzable =

1560 !TII->analyzeBranch(*Pred, PredTBB, PredFBB, PredCond, true);

1561

1562

1563 if (PredAnalyzable && !PredCond.empty() && PredTBB == MBB &&

1564 PredTBB != PredFBB) {

1565

1566

1567

1568 if (TII->canMakeTailCallConditional(PredCond, TailCall)) {

1569

1570

1571

1572 TII->replaceBranchWithTailCall(*Pred, PredCond, TailCall);

1574 }

1575 }

1576

1577

1578

1579

1580

1581 }

1582 if (!PredsChanged.empty()) {

1583 NumTailCalls += PredsChanged.size();

1584 for (auto &Pred : PredsChanged)

1586

1587 return true;

1588 }

1589 }

1590 }

1591

1592 if (!CurUnAnalyzable) {

1593

1594

1595

1596

1597

1598 if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) {

1600 if (!TII->reverseBranchCondition(NewCond)) {

1602 TII->removeBranch(*MBB);

1603 TII->insertBranch(*MBB, CurFBB, CurTBB, NewCond, Dl);

1604 MadeChange = true;

1605 ++NumBranchOpts;

1606 goto ReoptimizeBlock;

1607 }

1608 }

1609

1610

1611

1612 if (CurTBB && CurCond.empty() && !CurFBB &&

1616

1617

1618

1619 TII->removeBranch(*MBB);

1620

1621

1622

1624

1625

1627 }

1628

1629

1630

1631

1632

1634 bool PredHasNoFallThrough = !PrevBB.canFallThrough();

1635 if (PredHasNoFallThrough || !PriorUnAnalyzable ||

1637

1638

1639 if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) &&

1640 PriorTBB != MBB && PriorFBB != MBB) {

1641 if (!PriorTBB) {

1642 assert(PriorCond.empty() && !PriorFBB &&

1643 "Bad branch analysis");

1644 PriorTBB = MBB;

1645 } else {

1646 assert(!PriorFBB && "Machine CFG out of date!");

1647 PriorFBB = MBB;

1648 }

1650 TII->removeBranch(PrevBB);

1651 TII->insertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, PrevDl);

1652 }

1653

1654

1655 size_t PI = 0;

1656 bool DidChange = false;

1657 bool HasBranchToSelf = false;

1659 MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI);

1660 if (PMBB == MBB) {

1661

1662 ++PI;

1663 HasBranchToSelf = true;

1664 } else {

1665 DidChange = true;

1667

1668

1669

1671 ++SI)

1672 if (*SI != CurTBB && !CurTBB->isSuccessor(*SI)) {

1673 assert((*SI)->isEHPad() && "Bad CFG");

1675 }

1676

1677

1678

1679 MachineBasicBlock *NewCurTBB = nullptr, *NewCurFBB = nullptr;

1681 bool NewCurUnAnalyzable = TII->analyzeBranch(

1682 *PMBB, NewCurTBB, NewCurFBB, NewCurCond, true);

1683 if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) {

1685 TII->removeBranch(*PMBB);

1686 NewCurCond.clear();

1687 TII->insertBranch(*PMBB, NewCurTBB, nullptr, NewCurCond,

1688 PrevDl);

1689 MadeChange = true;

1690 ++NumBranchOpts;

1691 }

1692 }

1693 }

1694

1695

1697 MJTI->ReplaceMBBInJumpTables(MBB, CurTBB);

1698 if (DidChange) {

1699 ++NumBranchOpts;

1700 MadeChange = true;

1701 if (!HasBranchToSelf) return MadeChange;

1702 }

1703 }

1704 }

1705

1706

1707 TII->insertBranch(*MBB, CurTBB, nullptr, CurCond, Dl);

1708 }

1709 }

1710

1711

1712

1713

1715

1716

1718

1720

1721

1722

1724

1725 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;

1728 !TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true) &&

1729 (PredTBB == MBB || PredFBB == MBB) &&

1730 (!CurFallsThru || !CurTBB || !CurFBB) &&

1732

1733

1734

1735

1736

1737

1738

1739

1740

1741

1742 if (CurFallsThru) {

1743 MachineBasicBlock *NextBB = &*std::next(MBB->getIterator());

1744 CurCond.clear();

1745 TII->insertBranch(*MBB, NextBB, nullptr, CurCond, DebugLoc());

1746 }

1748 MadeChange = true;

1749 goto ReoptimizeBlock;

1750 }

1751 }

1752 }

1753

1754 if (!CurFallsThru) {

1755

1756

1757 if (!CurUnAnalyzable) {

1758 for (MachineBasicBlock *SuccBB : {CurFBB, CurTBB}) {

1759 if (!SuccBB)

1760 continue;

1761

1763

1764

1765

1766

1767 if (SuccBB != MBB && &*SuccPrev != MBB &&

1768 !SuccPrev->canFallThrough()) {

1770 MadeChange = true;

1771 goto ReoptimizeBlock;

1772 }

1773 }

1774 }

1775

1776

1777

1778

1779

1780

1781

1782

1783

1784

1785

1786

1787

1788

1789

1790

1791

1792

1793

1794

1795

1796

1797 MachineBasicBlock *PrevTBB = nullptr, *PrevFBB = nullptr;

1799

1800 if (FallThrough != MF.end() && !FallThrough->isEHPad() &&

1801 !FallThrough->isInlineAsmBrIndirectTarget() &&

1802 !TII->analyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&

1805 MadeChange = true;

1806 return MadeChange;

1807 }

1808 }

1809 }

1810

1811 return MadeChange;

1812}

1813

1814

1815

1816

1817

1818bool BranchFolder::HoistCommonCode(MachineFunction &MF) {

1819 bool MadeChange = false;

1821 MadeChange |= HoistCommonCodeInSuccs(&MBB);

1822

1823 return MadeChange;

1824}

1825

1826

1827

1831 if (SuccBB != TrueBB)

1832 return SuccBB;

1833 return nullptr;

1834}

1835

1836template

1838 Container &Set) {

1839 if (Reg.isPhysical()) {

1841 Set.insert(*AI);

1842 } else {

1843 Set.insert(Reg);

1844 }

1845}

1846

1847

1848

1849

1850

1851

1852

1853

1854static

1861 if ( TII ->isUnpredicatedTerminator(*Loc))

1862 return MBB->end();

1863

1865 if (!MO.isReg())

1866 continue;

1868 if ( Reg )

1869 continue;

1870 if (MO.isUse()) {

1872 } else {

1873 if (!MO.isDead())

1874

1875

1876 return MBB->end();

1877

1878

1879

1881 }

1882 }

1883

1884 if (Uses.empty())

1885 return Loc;

1886

1887

1888

1889

1890 if (Loc == MBB->begin())

1891 return Loc;

1892

1893

1894

1896

1897 bool IsDef = false;

1899

1900 if (MO.isRegMask())

1901 return Loc;

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

1903 continue;

1905 if ( Reg )

1906 continue;

1908 IsDef = true;

1909 break;

1910 }

1911 }

1912 if (!IsDef)

1913

1914

1915 return Loc;

1916

1917

1918

1919

1920

1921

1922

1923 bool DontMoveAcrossStore = true;

1924 if (!PI->isSafeToMove(DontMoveAcrossStore) || TII->isPredicated(*PI))

1925 return MBB->end();

1926

1927

1928

1930 if (!MO.isReg())

1931 continue;

1933 if ( Reg )

1934 continue;

1935 if (MO.isUse()) {

1937 } else {

1939 if (Reg.isPhysical()) {

1941 Uses.erase(SubReg);

1942 }

1943 }

1945 }

1946 }

1947

1948 return PI;

1949}

1950

1951bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) {

1952 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;

1955 return false;

1956

1958 if (!FBB)

1959

1960 return false;

1961

1962

1963

1964 if (TBB->pred_size() > 1 || FBB->pred_size() > 1)

1965 return false;

1966

1967

1968

1969

1970 SmallSet<Register, 4> Uses, Defs;

1973 if (Loc == MBB->end())

1974 return false;

1975

1976 bool HasDups = false;

1977 SmallSet<Register, 4> ActiveDefsSet, AllDefsSet;

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

1984

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

1988 break;

1989

1991 break;

1992

1993 if (TII->isPredicated(*TIB))

1994

1995 break;

1996

1997 if (!TII->isSafeToMove(*TIB, TBB, MF))

1998

1999 break;

2000

2001 bool IsSafe = true;

2002 for (MachineOperand &MO : TIB->operands()) {

2003

2004 if (MO.isRegMask()) {

2005 IsSafe = false;

2006 break;

2007 }

2008 if (!MO.isReg())

2009 continue;

2011 if ( Reg )

2012 continue;

2013 if (MO.isDef()) {

2015

2016

2017 IsSafe = false;

2018 break;

2019 }

2020

2021 if (Defs.count(Reg) && !MO.isDead()) {

2022

2023

2024

2025

2026

2027

2028

2029

2030

2031

2032

2033 IsSafe = false;

2034 break;

2035 }

2036 } else if (!ActiveDefsSet.count(Reg)) {

2038

2039 IsSafe = false;

2040 break;

2041 }

2042

2043 if (MO.isKill() && Uses.count(Reg))

2044

2045

2046 MO.setIsKill(false);

2047 }

2048 }

2049 if (!IsSafe)

2050 break;

2051

2052 bool DontMoveAcrossStore = true;

2053 if (!TIB->isSafeToMove(DontMoveAcrossStore))

2054 break;

2055

2056

2057 for (const MachineOperand &MO : TIB->all_uses()) {

2058 if (!MO.isKill())

2059 continue;

2061 if ( Reg )

2062 continue;

2063 if (!AllDefsSet.count(Reg)) {

2064 continue;

2065 }

2067 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)

2068 ActiveDefsSet.erase(*AI);

2069 } else {

2071 }

2072 }

2073

2074

2075 for (const MachineOperand &MO : TIB->all_defs()) {

2076 if (MO.isDead())

2077 continue;

2080 continue;

2083 }

2084

2085 HasDups = true;

2086 ++TIB;

2087 ++FIB;

2088 }

2089

2090 if (!HasDups)

2091 return false;

2092

2093

2094

2095

2096 if (TBB == FBB) {

2098 } else {

2099

2100

2101

2102 MachineInstrBuilder MIRBuilder(*MBB->getParent(), Loc);

2104 assert(DI->isDebugInstr() && "Expected a debug instruction");

2105 if (DI->isDebugRef()) {

2106 const TargetInstrInfo *TII =

2108 const MCInstrDesc &DBGV = TII->get(TargetOpcode::DBG_VALUE);

2110 DI->getDebugVariable(), DI->getDebugExpression());

2112 return;

2113 }

2114

2115 if (DI->isDebugPHI()) {

2116 DI->eraseFromParent();

2117 return;

2118 }

2119

2120 if (!DI->isDebugLabel())

2121 DI->setDebugValueUndef();

2122 DI->moveBefore(&*Loc);

2123 };

2124

2125

2126

2131

2132

2133

2134 while (FI != FE && FI->isDebugInstr())

2135 HoistAndKillDbgInstr(FI++);

2136

2137

2138 if (TI->isDebugInstr()) {

2139 HoistAndKillDbgInstr(TI);

2140 continue;

2141 }

2142

2143

2144 assert(FI != FE && "Unexpected end of FBB range");

2145

2146

2147 assert(!TI->isPseudoProbe() && "Unexpected pseudo probe in range");

2148

2149

2151 "Expected non-debug lockstep");

2152

2153

2154 TI->setDebugLoc(

2156 TI->moveBefore(&*Loc);

2157 ++FI;

2158 }

2159 }

2160

2161 FBB->erase(FBB->begin(), FIB);

2162

2163 if (UpdateLiveIns)

2165

2166 ++NumHoist;

2167 return true;

2168}

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

MachineBasicBlock MachineBasicBlock::iterator MBBI

This file implements the BitVector class.

static unsigned EstimateRuntime(MachineBasicBlock::iterator I, MachineBasicBlock::iterator E)

EstimateRuntime - Make a rough estimate for how long it will take to run the specified code.

Definition BranchFolding.cpp:466

static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2, MachineBasicBlock::iterator &I1, MachineBasicBlock::iterator &I2)

Given two machine basic blocks, return the number of instructions they actually have in common togeth...

Definition BranchFolding.cpp:354

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

findFalseBlock - BB has a fallthrough.

Definition BranchFolding.cpp:1828

static void copyDebugInfoToPredecessor(const TargetInstrInfo *TII, MachineBasicBlock &MBB, MachineBasicBlock &PredMBB)

Definition BranchFolding.cpp:1302

static unsigned HashMachineInstr(const MachineInstr &MI)

HashMachineInstr - Compute a hash value for MI and its operands.

Definition BranchFolding.cpp:281

static bool countsAsInstruction(const MachineInstr &MI)

Whether MI should be counted as an instruction when calculating common tail.

Definition BranchFolding.cpp:330

static unsigned CountTerminators(MachineBasicBlock *MBB, MachineBasicBlock::iterator &I)

CountTerminators - Count the number of terminators in the given block and set I to the position of th...

Definition BranchFolding.cpp:525

static bool blockEndsInUnreachable(const MachineBasicBlock *MBB)

A no successor, non-return block probably ends in unreachable and is cold.

Definition BranchFolding.cpp:544

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

Definition BranchFolding.cpp:1333

static MachineBasicBlock::iterator skipBackwardPastNonInstructions(MachineBasicBlock::iterator I, MachineBasicBlock *MBB)

Iterate backwards from the given iterator I, towards the beginning of the block.

Definition BranchFolding.cpp:338

static cl::opt< unsigned > TailMergeThreshold("tail-merge-threshold", cl::desc("Max number of predecessors to consider tail merging"), cl::init(150), cl::Hidden)

static void addRegAndItsAliases(Register Reg, const TargetRegisterInfo *TRI, Container &Set)

Definition BranchFolding.cpp:1837

static cl::opt< cl::boolOrDefault > FlagEnableTailMerge("enable-tail-merge", cl::init(cl::BOU_UNSET), cl::Hidden)

static cl::opt< unsigned > TailMergeSize("tail-merge-size", cl::desc("Min number of instructions to consider tail merging"), cl::init(3), cl::Hidden)

static bool IsEmptyBlock(MachineBasicBlock *MBB)

Definition BranchFolding.cpp:1265

static bool ProfitableToMerge(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2, unsigned MinCommonTailLength, unsigned &CommonTailLen, MachineBasicBlock::iterator &I1, MachineBasicBlock::iterator &I2, MachineBasicBlock *SuccBB, MachineBasicBlock *PredBB, DenseMap< const MachineBasicBlock *, int > &EHScopeMembership, bool AfterPlacement, MBFIWrapper &MBBFreqInfo, ProfileSummaryInfo *PSI)

ProfitableToMerge - Check if two machine basic blocks have a common tail and decide if it would be pr...

Definition BranchFolding.cpp:569

static void copyDebugInfoToSuccessor(const TargetInstrInfo *TII, MachineBasicBlock &MBB, MachineBasicBlock &SuccMBB)

Definition BranchFolding.cpp:1314

static bool IsBranchOnlyBlock(MachineBasicBlock *MBB)

Definition BranchFolding.cpp:1271

static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB, const TargetInstrInfo *TII, const DebugLoc &BranchDL)

Definition BranchFolding.cpp:486

static bool IsBetterFallthrough(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2)

IsBetterFallthrough - Return true if it would be clearly better to fall-through to MBB1 than to fall ...

Definition BranchFolding.cpp:1281

static unsigned HashEndOfMBB(const MachineBasicBlock &MBB)

HashEndOfMBB - Hash the last instruction in the MBB.

Definition BranchFolding.cpp:321

static void mergeOperations(MachineBasicBlock::iterator MBBIStartPos, MachineBasicBlock &MBBCommon)

Definition BranchFolding.cpp:786

static MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, SmallSet< Register, 4 > &Uses, SmallSet< Register, 4 > &Defs)

findHoistingInsertPosAndDeps - Find the location to move common instructions in successors to.

Definition BranchFolding.cpp:1855

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

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

const HexagonInstrInfo * TII

A common definition of LaneBitmask for use in TableGen and CodeGen.

Promote Memory to Register

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

const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB

const SmallVectorImpl< MachineOperand > & Cond

Remove Loads Into Fake Uses

This file defines the SmallSet class.

This file defines the SmallVector class.

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

#define STATISTIC(VARNAME, DESC)

Target-Independent Code Generator Pass Configuration Options pass.

AnalysisUsage & addRequired()

LLVM Basic Block Representation.

bool test(unsigned Idx) const

size_type size() const

size - Returns the number of bits in this bitvector.

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.

Definition BranchFolding.cpp:205

BranchFolder(bool DefaultEnableTailMerge, bool CommonHoist, MBFIWrapper &FreqInfo, const MachineBranchProbabilityInfo &ProbInfo, ProfileSummaryInfo *PSI, unsigned MinTailLength=0)

Definition BranchFolding.cpp:166

static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)

static LLVM_ABI DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)

Attempts to merge LocA and LocB into a single location; see DebugLoc::getMergedLocation for more deta...

static LLVM_ABI DebugLoc getMergedLocation(DebugLoc LocA, DebugLoc LocB)

When two instructions are combined into a single instruction we also need to combine the original loc...

iterator find(const_arg_type_t< KeyT > Val)

void removeBlock(BlockT *BB)

This method completely removes BB from all data structures, including all of the Loop objects it is n...

const MCInstrDesc & get(unsigned Opcode) const

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

MCRegAliasIterator enumerates all registers aliasing Reg.

An RAII based helper class to modify MachineFunctionProperties when running pass.

unsigned pred_size() const

bool isEHPad() const

Returns true if the block is a landing pad.

MachineInstrBundleIterator< const MachineInstr > const_iterator

LLVM_ABI void moveBefore(MachineBasicBlock *NewAfter)

Move 'this' block before or after the specified block.

LLVM_ABI void transferSuccessors(MachineBasicBlock *FromMBB)

Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...

LLVM_ABI instr_iterator insert(instr_iterator I, MachineInstr *M)

Insert MI into the instruction list before I, possibly inside a bundle.

iterator_range< livein_iterator > liveins() const

int getNumber() const

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

LLVM_ABI iterator SkipPHIsAndLabels(iterator I)

Return the first instruction in MBB after I that is not a PHI or a label.

const BasicBlock * getBasicBlock() const

Return the LLVM basic block that this instance corresponded to originally.

LLVM_ABI bool canFallThrough()

Return true if the block can implicitly transfer control to the block after it by falling off the end...

LLVM_ABI void setSuccProbability(succ_iterator I, BranchProbability Prob)

Set successor probability of a given iterator.

LLVM_ABI iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)

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

succ_iterator succ_begin()

LLVM_ABI void clearLiveIns()

Clear live in list.

LLVM_ABI iterator getFirstTerminator()

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

unsigned succ_size() const

bool hasAddressTaken() const

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

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

Add Succ as a successor of this MachineBasicBlock.

LLVM_ABI void copySuccessor(const MachineBasicBlock *Orig, succ_iterator I)

Copy a successor (and any probability info) from original block to this block's.

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

Remove successor from the successors list of this MachineBasicBlock.

pred_iterator pred_begin()

LLVM_ABI iterator getLastNonDebugInstr(bool SkipPseudoOp=true)

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

LLVM_ABI void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New)

Given a machine basic block that branched to 'Old', change the code and CFG so that it branches to 'N...

MachineInstrBundleIterator< MachineInstr, true > reverse_iterator

LLVM_ABI bool isLayoutSuccessor(const MachineBasicBlock *MBB) const

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

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.

LLVM_ABI DebugLoc findBranchDebugLoc()

Find and return the merged DebugLoc of the branch instructions of the block.

iterator_range< succ_iterator > successors()

reverse_iterator rbegin()

bool isMachineBlockAddressTaken() const

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

LLVM_ABI bool isSuccessor(const MachineBasicBlock *MBB) const

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

iterator_range< pred_iterator > predecessors()

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

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

MachineInstrBundleIterator< MachineInstr > iterator

LLVM_ABI void moveAfter(MachineBasicBlock *NewBefore)

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

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

const TargetSubtargetInfo & getSubtarget() const

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

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

Function & getFunction()

Return the LLVM function that this machine code represents.

const MachineBasicBlock & back() const

BasicBlockListType::iterator iterator

void eraseAdditionalCallInfo(const MachineInstr *MI)

Following functions update call site info.

void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)

RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.

const MachineJumpTableInfo * getJumpTableInfo() const

getJumpTableInfo - Return the jump table info object for the current function.

MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)

CreateMachineInstr - Allocate a new MachineInstr.

void erase(iterator MBBI)

void insert(iterator MBBI, MachineBasicBlock *MBB)

const TargetMachine & getTarget() const

getTarget - Return the target machine this machine code is compiled with

Representation of each machine instruction.

bool isBarrier(QueryType Type=AnyInBundle) const

Returns true if the specified instruction stops control flow from executing the instruction immediate...

LLVM_ABI void eraseFromParent()

Unlink 'this' from the containing basic block and delete it.

void RemoveJumpTable(unsigned Idx)

RemoveJumpTable - Mark the specific index as being dead.

const std::vector< MachineJumpTableEntry > & getJumpTables() const

MachineOperand class - Representation of each machine instruction operand.

bool isReg() const

isReg - Tests if this is a MO_Register operand.

void setIsUndef(bool Val=true)

@ MO_Immediate

Immediate operand.

@ MO_ConstantPoolIndex

Address of indexed Constant in Constant Pool.

@ MO_GlobalAddress

Address of a global value.

@ MO_MachineBasicBlock

MachineBasicBlock reference.

@ MO_FrameIndex

Abstract Stack Frame Index.

@ MO_Register

@ MO_ExternalSymbol

Name of external global symbol.

@ MO_JumpTableIndex

Address of indexed Jump Table for switch.

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

bool tracksLiveness() const

tracksLiveness - Returns true when tracking register liveness accurately.

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Analysis providing profile information.

Wrapper class representing virtual and physical registers.

constexpr bool isVirtual() const

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

constexpr bool isPhysical() const

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

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

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

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 push_back(const T &Elt)

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

TargetInstrInfo - Interface to description of machine instruction set.

bool requiresStructuredCFG() const

bool getEnableTailMerge() const

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

virtual const TargetInstrInfo * getInstrInfo() const

virtual const TargetRegisterInfo * getRegisterInfo() const =0

Return the target's register information.

self_iterator getIterator()

unsigned ID

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

@ BasicBlock

Various leaf nodes.

initializer< Ty > init(const Ty &Val)

LLVM_ABI iterator begin() const

This is an optimization pass for GlobalISel generic memory operations.

auto drop_begin(T &&RangeOrContainer, size_t N=1)

Return a range covering RangeOrContainer with the first N elements excluded.

OuterAnalysisManagerProxy< ModuleAnalysisManager, MachineFunction > ModuleAnalysisManagerMachineFunctionProxy

Provide the ModuleAnalysisManager to Function proxy.

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

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

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

Convenience function for iterating over sub-ranges.

LLVM_ABI bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)

Returns true if machine function MF is suggested to be size-optimized based on the profile.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

AnalysisManager< MachineFunction > MachineFunctionAnalysisManager

LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()

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

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.

LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)

class LLVM_GSL_OWNER SmallVector

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

uint16_t MCPhysReg

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

FunctionAddr VTableAddr Next

DWARFExpression::Operation Op

void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)

Convenience function combining computeLiveIns() and addLiveIns().

void array_pod_sort(IteratorTy Start, IteratorTy End)

array_pod_sort - This sorts an array with the specified start and end extent.

void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB)

Computes registers live-in to MBB assuming all of its successors live-in lists are up-to-date.

LLVM_ABI char & BranchFolderPassID

BranchFolding - This pass performs machine code CFG based optimizations to delete branches to branche...

Definition BranchFolding.cpp:118

IterT prev_nodbg(IterT It, IterT Begin, bool SkipPseudoOp=true)

Decrement It, then continue decrementing it while it points to a debug instruction.

void fullyRecomputeLiveIns(ArrayRef< MachineBasicBlock * > MBBs)

Convenience function for recomputing live-in's for a set of MBBs until the computation converges.

LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)

Adds registers contained in LiveRegs to the block live-in list of MBB.

DenseMap< const MachineBasicBlock *, int > getEHScopeMembership(const MachineFunction &MF)

static constexpr LaneBitmask getAll()