BranchFolding.cpp Source File (original) (raw)

58#include

59#include

60#include

61#include

63using namespace llvm;

65#define DEBUG_TYPE "branch-folder"

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

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

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

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

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

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

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

88namespace {

92 public:

93 static char ID;

105 }

106

109 MachineFunctionProperties::Property::NoPHIs);

110 }

111 };

112

113}

114

115char BranchFolderPass::ID = 0;

116

118

120 "Control Flow Optimizer", false, false)

121

123 if (skipFunction(MF.getFunction()))

124 return false;

125

126 TargetPassConfig *PassConfig = &getAnalysis();

127

128

129 bool EnableTailMerge = !MF.getTarget().requiresStructuredCFG() &&

132 getAnalysis().getMBFI());

134 EnableTailMerge, true, MBBFreqInfo,

135 getAnalysis().getMBPI(),

136 &getAnalysis().getPSI());

137 return Folder.OptimizeFunction(MF, MF.getSubtarget().getInstrInfo(),

138 MF.getSubtarget().getRegisterInfo());

139}

140

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

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

149 EnableTailMerge = DefaultEnableTailMerge;

150 break;

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

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

153 }

154}

155

159

161

164

165

166 TriedMerging.erase(MBB);

167

168

170 if (MI.shouldUpdateAdditionalCallInfo())

172

173

175 EHScopeMembership.erase(MBB);

176 if (MLI)

178}

179

184 if (!tii) return false;

185

186 TriedMerging.clear();

187

189 AfterBlockPlacement = AfterPlacement;

190 TII = tii;

191 TRI = tri;

192 MLI = mli;

193 this->MRI = &MRI;

194

195 if (MinCommonTailLength == 0) {

196 MinCommonTailLength = TailMergeSize.getNumOccurrences() > 0

199 }

200

202 if (!UpdateLiveIns)

203 MRI.invalidateLiveness();

204

205 bool MadeChange = false;

206

207

209

210 bool MadeChangeThisIteration = true;

211 while (MadeChangeThisIteration) {

212 MadeChangeThisIteration = TailMergeBlocks(MF);

213

214

215 if (!AfterBlockPlacement || MadeChangeThisIteration)

216 MadeChangeThisIteration |= OptimizeBranches(MF);

217 if (EnableHoistCommonCode)

218 MadeChangeThisIteration |= HoistCommonCode(MF);

219 MadeChange |= MadeChangeThisIteration;

220 }

221

222

223

225 if (!JTI)

226 return MadeChange;

227

228

233 if (.isJTI()) continue;

234

235

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

237 }

238 }

239

240

241

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

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

245 MadeChange = true;

246 }

247

248 return MadeChange;

249}

250

251

252

253

254

255

257 unsigned Hash = MI.getOpcode();

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

260

261

262

263

264 unsigned OperandHash = 0;

265 switch (Op.getType()) {

267 OperandHash = Op.getReg();

268 break;

270 OperandHash = Op.getImm();

271 break;

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

274 break;

278 OperandHash = Op.getIndex();

279 break;

282

283

284 OperandHash = Op.getOffset();

285 break;

286 default:

287 break;

288 }

289

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

291 }

292 return Hash;

293}

294

295

299 return 0;

300

302}

303

304

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

307}

308

309

310

311

316 --I;

318 return I;

319 }

321}

322

323

324

325

326

327

328

335

336 unsigned TailLen = 0;

337 while (true) {

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

341 break;

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

343

344

345

346

347

348 MBBI1->isInlineAsm()) {

349 break;

350 }

353 break;

354 ++TailLen;

355 I1 = MBBI1;

356 I2 = MBBI2;

357 }

358

359 return TailLen;

360}

361

364 if (UpdateLiveIns) {

365

367 LiveRegs.clear();

369

371 do {

372 --I;

374 } while (I != OldInst);

375

376

377

378

380

381

383 "Can only handle full register.");

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

386 continue;

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

389 }

390 }

391

393 ++NumTailMerge;

394}

395

400 return nullptr;

401

403

404

408

409

411

412

414

415

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

417

418

419 if (MLI)

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

422

423

425

426 if (UpdateLiveIns)

428

429

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

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

432 auto n = EHScopeI->second;

433 EHScopeMembership[NewMBB] = n;

434 }

435

436 return NewMBB;

437}

438

439

440

443 unsigned Time = 0;

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

446 continue;

447 if (I->isCall())

448 Time += 10;

449 else if (I->mayLoadOrStore())

450 Time += 2;

451 else

452 ++Time;

453 }

454 return Time;

455}

456

457

458

459

460

468 if (!dl)

469 dl = BranchDL;

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

476 return;

477 }

478 }

479 }

482}

483

484bool

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

486 if (getHash() < o.getHash())

487 return true;

488 if (getHash() > o.getHash())

489 return false;

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

491 return true;

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

493 return false;

494 return false;

495}

496

497

498

499

503 unsigned NumTerms = 0;

504 while (true) {

507 break;

508 }

509 --I;

510 if (->isTerminator()) break;

511 ++NumTerms;

512 }

513 return NumTerms;

514}

515

516

517

518

521 return false;

523 return true;

525}

526

527

528

529

530

531

532

533

534

535

536

537

538

539

540

541

542

543static bool

545 unsigned MinCommonTailLength, unsigned &CommonTailLen,

550 bool AfterPlacement,

553

554 if (!EHScopeMembership.empty()) {

555 auto EHScope1 = EHScopeMembership.find(MBB1);

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

557 auto EHScope2 = EHScopeMembership.find(MBB2);

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

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

560 return false;

561 }

562

564 if (CommonTailLen == 0)

565 return false;

568 << CommonTailLen << '\n');

569

570

571

572

574 I1 = MBB1->begin();

576 I2 = MBB2->begin();

577

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

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

580

581

582

583

584

585

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

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

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

590 if (CommonTailLen > NumTerms)

591 return true;

592 }

593

594

595

596

597

598

599 if (FullBlockTail1 && FullBlockTail2 &&

601 return true;

602

603

604

605

606

608 return true;

610 return true;

611

612

613

614

615

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

619 return false;

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

623 };

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

625 return true;

626 }

627

628

629

630

631

632

633 unsigned EffectiveTailLen = CommonTailLen;

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

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

638 ++EffectiveTailLen;

639

640

641 if (EffectiveTailLen >= MinCommonTailLength)

642 return true;

643

644

645

646

647

650 return EffectiveTailLen >= 2 && OptForSize &&

651 (FullBlockTail1 || FullBlockTail2);

652}

653

654unsigned BranchFolder::ComputeSameTails(unsigned CurHash,

655 unsigned MinCommonTailLength,

658 unsigned maxCommonTailLength = 0U;

659 SameTails.clear();

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

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

663 B = MergePotentials.begin();

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

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

666 unsigned CommonTailLen;

668 MinCommonTailLength,

669 CommonTailLen, TrialBBI1, TrialBBI2,

670 SuccBB, PredBB,

671 EHScopeMembership,

672 AfterBlockPlacement, MBBFreqInfo, PSI)) {

673 if (CommonTailLen > maxCommonTailLength) {

674 SameTails.clear();

675 maxCommonTailLength = CommonTailLen;

676 HighestMPIter = CurMPIter;

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

678 }

679 if (HighestMPIter == CurMPIter &&

680 CommonTailLen == maxCommonTailLength)

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

682 }

683 if (I == B)

684 break;

685 }

686 }

687 return maxCommonTailLength;

688}

689

690void BranchFolder::RemoveBlocksWithHash(unsigned CurHash,

694 MPIterator CurMPIter, B;

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

696 B = MergePotentials.begin();

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

698

700 if (SuccBB && CurMBB != PredBB)

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

702 if (CurMPIter == B)

703 break;

704 }

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

706 CurMPIter++;

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

708}

709

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

712 unsigned maxCommonTailLength,

713 unsigned &commonTailIndex) {

714 commonTailIndex = 0;

715 unsigned TimeEstimate = ~0U;

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

717

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

719 commonTailIndex = i;

720 break;

721 }

722

723

725 SameTails[i].getTailStartPos());

726 if (t <= TimeEstimate) {

727 TimeEstimate = t;

728 commonTailIndex = i;

729 }

730 }

731

733 SameTails[commonTailIndex].getTailStartPos();

735

737 << maxCommonTailLength);

738

739

740

741

745 if (!newMBB) {

747 return false;

748 }

749

750 SameTails[commonTailIndex].setBlock(newMBB);

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

752

753

754 if (PredBB == MBB)

755 PredBB = newMBB;

756

757 return true;

758}

759

760static void

764

765

766

767 unsigned CommonTailLen = 0;

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

769 ++CommonTailLen;

770

775

776 while (CommonTailLen--) {

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

778 (void)MBBIE;

779

782 continue;

783 }

784

786 ++MBBICommon;

787

788 assert(MBBICommon != MBBIECommon &&

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

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

791

792

793 if (MBBICommon->mayLoadOrStore())

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

795

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

802 }

803 }

804

806 ++MBBICommon;

807 }

808}

809

810void BranchFolder::mergeCommonTails(unsigned commonTailIndex) {

812

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

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

815 if (i != commonTailIndex) {

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

818 } else {

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

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

821 }

822 }

823

824 for (auto &MI : *MBB) {

826 continue;

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

829 if (i == commonTailIndex)

830 continue;

831

832 auto &Pos = NextCommonInsts[i];

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

834 "Reached BB end within common tail");

836 ++Pos;

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

838 "Reached BB end within common tail");

839 }

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

842 NextCommonInsts[i] = ++Pos;

843 }

844 MI.setDebugLoc(DL);

845 }

846

847 if (UpdateLiveIns) {

850 LiveRegs.init(*TRI);

851

852

853

855 LiveRegs.clear();

858 for (Register Reg : NewLiveIns) {

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

860 continue;

861

862

863

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

866 }))

867 continue;

868

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

871 Reg);

872 }

873 }

874

877 }

878}

879

880

881

882

883

884

885

886

887

888

891 unsigned MinCommonTailLength) {

892 bool MadeChange = false;

893

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

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

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

899 dbgs() << "\n";

900 if (SuccBB) {

902 if (PredBB)

904 << "\n";

905 }

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

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

908 });

909

910

911

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

913

914

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

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

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

918

919

920

921 unsigned maxCommonTailLength = ComputeSameTails(CurHash,

922 MinCommonTailLength,

923 SuccBB, PredBB);

924

925

926

927 if (SameTails.empty()) {

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

929 continue;

930 }

931

932

933

934

935

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

938 unsigned commonTailIndex = SameTails.size();

939

940

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

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

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

944 commonTailIndex = 1;

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

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

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

948 SameTails[0].tailIsWholeBlock() &&

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

950 commonTailIndex = 0;

951 else {

952

953

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

957 SameTails[i].tailIsWholeBlock())

958 continue;

959 if (MBB == PredBB) {

960 commonTailIndex = i;

961 break;

962 }

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

964 commonTailIndex = i;

965 }

966 }

967

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

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

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

971

972

973 if (!CreateCommonTailOnlyBlock(PredBB, SuccBB,

974 maxCommonTailLength, commonTailIndex)) {

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

976 continue;

977 }

978 }

979

981

982

983 setCommonTailEdgeWeights(*MBB);

984

985

986

987 mergeCommonTails(commonTailIndex);

988

989

990

992 << " for ");

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

994 if (commonTailIndex == i)

995 continue;

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

998

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

1000

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

1002 }

1004

1005

1006 MadeChange = true;

1007 }

1008 return MadeChange;

1009}

1010

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

1012 bool MadeChange = false;

1013 if (!EnableTailMerge)

1014 return MadeChange;

1015

1016

1017

1018 MergePotentials.clear();

1021 break;

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

1025 }

1026

1027

1028

1030 for (const MergePotentialsElt &Elt : MergePotentials)

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

1032

1033

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

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

1036

1037

1038

1039

1040

1041

1042

1043

1044

1045

1046

1047

1048

1049

1050

1051

1052

1053

1054

1055

1057 I != E; ++I) {

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

1062 MergePotentials.clear();

1064

1065

1066

1067

1068

1069

1070

1071

1072

1073

1074

1075 if (AfterBlockPlacement && MLI) {

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

1078 continue;

1079 }

1080

1083 break;

1084

1085 if (TriedMerging.count(PBB))

1086 continue;

1087

1088

1089 if (PBB == IBB)

1090 continue;

1091

1092

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

1094 continue;

1095

1096

1097

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

1099 continue;

1100

1101

1102

1103

1104 if (AfterBlockPlacement && MLI)

1106 continue;

1107

1111

1112

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

1116 continue;

1117

1118 if (!FBB) {

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

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

1121 FBB = &*Next;

1122 }

1123 }

1124

1125

1126 DebugLoc dl = PBB->findBranchDebugLoc();

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

1129 if ( Cond .empty())

1130

1132 NewCond, dl);

1133 }

1134

1135 MergePotentials.push_back(

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

1137 }

1138 }

1139

1140

1141

1143 for (MergePotentialsElt &Elt : MergePotentials)

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

1145

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

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

1148

1149

1150

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

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

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

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

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

1156 }

1157

1158 return MadeChange;

1159}

1160

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

1164

1165

1166

1167

1168 for (const auto &Src : SameTails) {

1171 AccumulatedMBBFreq += BlockFreq;

1172

1173

1174

1176 continue;

1177

1178 auto EdgeFreq = EdgeFreqLs.begin();

1179

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

1183 }

1184

1185 MBBFreqInfo.setBlockFreq(&TailMBB, AccumulatedMBBFreq);

1186

1188 return;

1189

1190 auto SumEdgeFreq =

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

1192 .getFrequency();

1193 auto EdgeFreq = EdgeFreqLs.begin();

1194

1195 if (SumEdgeFreq > 0) {

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

1199 EdgeFreq->getFrequency(), SumEdgeFreq);

1201 }

1202 }

1203}

1204

1205

1206

1207

1208

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

1210 bool MadeChange = false;

1211

1212

1214

1216

1219 MadeChange |= OptimizeBlock(&MBB);

1220

1221

1223 RemoveDeadBlock(&MBB);

1224 MadeChange = true;

1225 ++NumDeadBlocks;

1226 }

1227 }

1228

1229 return MadeChange;

1230}

1231

1232

1233

1236}

1237

1238

1239

1243 return I->isBranch();

1244}

1245

1246

1247

1248

1249

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

1253

1254

1255

1256

1257

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

1261 return false;

1262

1263

1264

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

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

1267

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

1269}

1270

1271

1272

1275 if (I != MBB.end() && I->isBranch())

1276 return I->getDebugLoc();

1278}

1279

1285 if (MI.isDebugInstr()) {

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

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

1288 << MI);

1289 }

1290}

1291

1297 if (MI.isDebugInstr()) {

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

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

1300 << MI);

1301 }

1302}

1303

1304

1305

1306

1307

1308

1309

1310

1314

1315

1319

1320

1321

1325}

1326

1328 bool MadeChange = false;

1330ReoptimizeBlock:

1331

1333 ++FallThrough;

1334

1335

1336 bool SameEHScope = true;

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

1338 auto MBBEHScope = EHScopeMembership.find(MBB);

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

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

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

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

1343 }

1344

1345

1346

1349 bool CurUnAnalyzable =

1351

1352

1353

1354

1355

1357 SameEHScope) {

1359

1361

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

1363

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

1365

1366

1367

1368

1370

1371

1375 }

1376

1377

1378

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

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

1382 FallThrough->copySuccessor(MBB, SI);

1383 }

1384

1385

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

1388 MadeChange = true;

1389 }

1390 return MadeChange;

1391 }

1392

1393

1394

1396

1399 bool PriorUnAnalyzable =

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

1401 if (!PriorUnAnalyzable) {

1402

1403

1404

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

1408 PriorCond.clear();

1409 if (PriorTBB != MBB)

1410 TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);

1411 MadeChange = true;

1412 ++NumBranchOpts;

1413 goto ReoptimizeBlock;

1414 }

1415

1416

1417

1418

1419

1420

1421

1422

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

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

1428

1429 if (!PrevBB.empty()) {

1431 --PrevBBIter;

1433

1434

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

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

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

1438 break;

1440 ++MBBIter; -- PrevBBIter;

1442 }

1443 }

1448 MadeChange = true;

1449 return MadeChange;

1450 }

1451

1452

1453

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

1456 MadeChange = true;

1457 ++NumBranchOpts;

1458 goto ReoptimizeBlock;

1459 }

1460

1461

1462

1463 if (PriorFBB == MBB) {

1466 TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);

1467 MadeChange = true;

1468 ++NumBranchOpts;

1469 goto ReoptimizeBlock;

1470 }

1471

1472

1473

1474

1475 if (PriorTBB == MBB) {

1480 TII->insertBranch(PrevBB, PriorFBB, nullptr, NewPriorCond, dl);

1481 MadeChange = true;

1482 ++NumBranchOpts;

1483 goto ReoptimizeBlock;

1484 }

1485 }

1486

1487

1488

1489

1490

1491

1492

1493

1494

1498 bool DoTransform = true;

1499

1500

1501

1502

1503

1504

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

1507 DoTransform = false;

1508

1509 if (DoTransform) {

1510

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

1515

1518 TII->insertBranch(PrevBB, MBB, nullptr, NewPriorCond, dl);

1519

1520

1522 MadeChange = true;

1523 ++NumBranchOpts;

1524 return MadeChange;

1525 }

1526 }

1527 }

1528 }

1529

1537 bool PredAnalyzable =

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

1539

1540

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

1542 PredTBB != PredFBB) {

1543

1544

1545

1547

1548

1549

1552 }

1553 }

1554

1555

1556

1557

1558

1559 }

1560 if (!PredsChanged.empty()) {

1561 NumTailCalls += PredsChanged.size();

1562 for (auto &Pred : PredsChanged)

1564

1565 return true;

1566 }

1567 }

1568 }

1569

1570 if (!CurUnAnalyzable) {

1571

1572

1573

1574

1575

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

1582 MadeChange = true;

1583 ++NumBranchOpts;

1584 goto ReoptimizeBlock;

1585 }

1586 }

1587

1588

1589

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

1594

1595

1596

1598

1599

1600

1602

1603

1605 }

1606

1607

1608

1609

1610

1612 bool PredHasNoFallThrough = !PrevBB.canFallThrough();

1613 if (PredHasNoFallThrough || !PriorUnAnalyzable ||

1615

1616

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

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

1619 if (!PriorTBB) {

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

1621 "Bad branch analysis");

1622 PriorTBB = MBB;

1623 } else {

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

1625 PriorFBB = MBB;

1626 }

1629 TII->insertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, pdl);

1630 }

1631

1632

1633 size_t PI = 0;

1634 bool DidChange = false;

1635 bool HasBranchToSelf = false;

1638 if (PMBB == MBB) {

1639

1640 ++PI;

1641 HasBranchToSelf = true;

1642 } else {

1643 DidChange = true;

1645

1646

1647

1649 ++SI)

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

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

1653 }

1654

1655

1656

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

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

1664 NewCurCond.clear();

1665 TII->insertBranch(*PMBB, NewCurTBB, nullptr, NewCurCond, pdl);

1666 MadeChange = true;

1667 ++NumBranchOpts;

1668 }

1669 }

1670 }

1671

1672

1674 MJTI->ReplaceMBBInJumpTables(MBB, CurTBB);

1675 if (DidChange) {

1676 ++NumBranchOpts;

1677 MadeChange = true;

1678 if (!HasBranchToSelf) return MadeChange;

1679 }

1680 }

1681 }

1682

1683

1685 }

1686 }

1687

1688

1689

1690

1692

1693

1695

1697

1698

1699

1701

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

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

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

1709

1710

1711

1712

1713

1714

1715

1716

1717

1718

1719 if (CurFallsThru) {

1721 CurCond.clear();

1723 }

1725 MadeChange = true;

1726 goto ReoptimizeBlock;

1727 }

1728 }

1729 }

1730

1731 if (!CurFallsThru) {

1732

1733

1734 if (!CurUnAnalyzable) {

1736 if (!SuccBB)

1737 continue;

1738

1740

1741

1742

1743

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

1745 !SuccPrev->canFallThrough()) {

1747 MadeChange = true;

1748 goto ReoptimizeBlock;

1749 }

1750 }

1751 }

1752

1753

1754

1755

1756

1757

1758

1759

1760

1761

1762

1763

1764

1765

1766

1769 if (FallThrough != MF.end() &&

1770 !FallThrough->isEHPad() &&

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

1774 MadeChange = true;

1775 return MadeChange;

1776 }

1777 }

1778 }

1779

1780 return MadeChange;

1781}

1782

1783

1784

1785

1786

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

1788 bool MadeChange = false;

1790 MadeChange |= HoistCommonCodeInSuccs(&MBB);

1791

1792 return MadeChange;

1793}

1794

1795

1796

1800 if (SuccBB != TrueBB)

1801 return SuccBB;

1802 return nullptr;

1803}

1804

1805template

1807 Container &Set) {

1808 if (Reg.isPhysical()) {

1810 Set.insert(*AI);

1811 } else {

1812 Set.insert(Reg);

1813 }

1814}

1815

1816

1817

1818

1819

1820

1821

1822

1823static

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

1832

1834 if (!MO.isReg())

1835 continue;

1837 if (!Reg)

1838 continue;

1839 if (MO.isUse()) {

1841 } else {

1842 if (!MO.isDead())

1843

1844

1846

1847

1848

1850 }

1851 }

1852

1853 if (Uses.empty())

1854 return Loc;

1855

1856

1857

1858

1860 return Loc;

1861

1862

1863

1865

1866 bool IsDef = false;

1868

1869 if (MO.isRegMask())

1870 return Loc;

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

1872 continue;

1874 if (!Reg)

1875 continue;

1876 if (Uses.count(Reg)) {

1877 IsDef = true;

1878 break;

1879 }

1880 }

1881 if (!IsDef)

1882

1883

1884 return Loc;

1885

1886

1887

1888

1889

1890

1891

1892 bool DontMoveAcrossStore = true;

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

1895

1896

1897

1899 if (!MO.isReg())

1900 continue;

1902 if (!Reg)

1903 continue;

1904 if (MO.isUse()) {

1906 } else {

1907 if (Uses.erase(Reg)) {

1908 if (Reg.isPhysical()) {

1910 Uses.erase(SubReg);

1911 }

1912 }

1914 }

1915 }

1916

1917 return PI;

1918}

1919

1924 return false;

1925

1927 if (!FBB)

1928

1929 return false;

1930

1931

1932

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

1934 return false;

1935

1936

1937

1938

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

1943 return false;

1944

1945 bool HasDups = false;

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

1952

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

1956 break;

1957

1959 break;

1960

1962

1963 break;

1964

1965 bool IsSafe = true;

1967

1968 if (MO.isRegMask()) {

1969 IsSafe = false;

1970 break;

1971 }

1972 if (!MO.isReg())

1973 continue;

1975 if (!Reg)

1976 continue;

1977 if (MO.isDef()) {

1978 if (Uses.count(Reg)) {

1979

1980

1981 IsSafe = false;

1982 break;

1983 }

1984

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

1986

1987

1988

1989

1990

1991

1992

1993

1994

1995

1996

1997 IsSafe = false;

1998 break;

1999 }

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

2001 if (Defs.count(Reg)) {

2002

2003 IsSafe = false;

2004 break;

2005 }

2006

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

2008

2009

2010 MO.setIsKill(false);

2011 }

2012 }

2013 if (!IsSafe)

2014 break;

2015

2016 bool DontMoveAcrossStore = true;

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

2018 break;

2019

2020

2022 if (!MO.isKill())

2023 continue;

2025 if (!Reg)

2026 continue;

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

2028 continue;

2029 }

2030 if (Reg.isPhysical()) {

2032 ActiveDefsSet.erase(*AI);

2033 } else {

2034 ActiveDefsSet.erase(Reg);

2035 }

2036 }

2037

2038

2040 if (MO.isDead())

2041 continue;

2043 if (!Reg || Reg.isVirtual())

2044 continue;

2047 }

2048

2049 HasDups = true;

2050 ++TIB;

2051 ++FIB;

2052 }

2053

2054 if (!HasDups)

2055 return false;

2056

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

2059

2060 if (UpdateLiveIns)

2062

2063 ++NumHoist;

2064 return true;

2065}

unsigned const MachineRegisterInfo * MRI

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.

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

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

findFalseBlock - BB has a fallthrough.

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

static unsigned HashMachineInstr(const MachineInstr &MI)

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

static bool countsAsInstruction(const MachineInstr &MI)

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

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

static bool blockEndsInUnreachable(const MachineBasicBlock *MBB)

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

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

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

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

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)

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)

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

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

static bool IsBranchOnlyBlock(MachineBasicBlock *MBB)

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

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

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

static unsigned HashEndOfMBB(const MachineBasicBlock &MBB)

HashEndOfMBB - Hash the last instruction in the MBB.

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

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.

static DebugLoc getBranchDebugLoc(MachineBasicBlock &MBB)

getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch instructions on the block.

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.

unsigned const TargetRegisterInfo * TRI

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

const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB

const SmallVectorImpl< MachineOperand > & Cond

Remove Loads Into Fake Uses

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

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.

Represent the analysis usage information of a 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.

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

static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)

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

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

This class represents an Operation in the Expression.

iterator find(const_arg_type_t< KeyT > Val)

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

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

bool isPredicated(const MachineInstr &MI) const override

Returns true if the instruction is already predicated.

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

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

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

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

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

Insert branch code into the end of the specified MachineBasicBlock.

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

void clear()

Clears the set.

bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const

Returns true if register Reg and no aliasing register is in the set.

void stepBackward(const MachineInstr &MI)

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

void init(const TargetRegisterInfo &TRI)

(re-)initializes and clears the set.

void addLiveOuts(const MachineBasicBlock &MBB)

Adds all live-out registers of basic block MBB.

void removeBlock(BlockT *BB)

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

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const

void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F)

const MCInstrDesc & get(unsigned Opcode) const

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

MCRegAliasIterator enumerates all registers aliasing Reg.

iterator_range< MCSuperRegIterator > superregs(MCRegister Reg) const

Return an iterator range over all super-registers of Reg, excluding Reg.

unsigned pred_size() const

bool isEHPad() const

Returns true if the block is a landing pad.

void moveBefore(MachineBasicBlock *NewAfter)

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

void transferSuccessors(MachineBasicBlock *FromMBB)

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

iterator_range< livein_iterator > liveins() const

int getNumber() const

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

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.

bool canFallThrough()

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

void setSuccProbability(succ_iterator I, BranchProbability Prob)

Set successor probability of a given iterator.

iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)

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

succ_iterator succ_begin()

void clearLiveIns()

Clear live in list.

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

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

Add Succ as a successor of this MachineBasicBlock.

void copySuccessor(const MachineBasicBlock *Orig, succ_iterator I)

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

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

Remove successor from the successors list of this MachineBasicBlock.

pred_iterator pred_begin()

iterator getLastNonDebugInstr(bool SkipPseudoOp=true)

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

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

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.

instr_iterator erase(instr_iterator I)

Remove an instruction from the instruction list and delete it.

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

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

void moveAfter(MachineBasicBlock *NewBefore)

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)

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

const MachineBasicBlock & back() const

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)

CreateMachineBasicBlock - Allocate a new MachineBasicBlock.

void erase(iterator MBBI)

void insert(iterator MBBI, MachineBasicBlock *MBB)

Representation of each machine instruction.

bool isReturn(QueryType Type=AnyInBundle) const

bool isBarrier(QueryType Type=AnyInBundle) const

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

void eraseFromParent()

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

bool isIndirectBranch(QueryType Type=AnyInBundle) const

Return true if this is an indirect branch, such as a branch through a register.

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

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

Analysis providing profile information.

Wrapper class representing virtual and physical registers.

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

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

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

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.

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

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

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

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

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

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

virtual bool canMakeTailCallConditional(SmallVectorImpl< MachineOperand > &Cond, const MachineInstr &TailCall) const

Returns true if the tail call can be made conditional on BranchCond.

virtual void ReplaceTailWithBranchTo(MachineBasicBlock::iterator Tail, MachineBasicBlock *NewDest) const

Delete the instruction OldInst and everything after it, replacing it with an unconditional branch to ...

virtual bool isUnconditionalTailCall(const MachineInstr &MI) const

Returns true if MI is an unconditional tail call.

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

Insert branch code into the end of the specified MachineBasicBlock.

virtual unsigned getTailMergeSize(const MachineFunction &MF) const

Returns the target-specific default value for tail merging.

virtual bool isPredicated(const MachineInstr &MI) const

Returns true if the instruction is already predicated.

virtual void replaceBranchWithTailCall(MachineBasicBlock &MBB, SmallVectorImpl< MachineOperand > &Cond, const MachineInstr &TailCall) const

Replace the conditional branch in MBB with a conditional tail call.

virtual bool isLegalToSplitMBBAt(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI) const

Return true if it's legal to split the given basic block at the specified instruction (i....

Target-Independent Code Generator Pass Configuration Options.

bool getEnableTailMerge() const

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

virtual bool trackLivenessAfterRegAlloc(const MachineFunction &MF) const

Returns true if the live-ins should be tracked after register allocation.

self_iterator getIterator()

unsigned ID

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

Reg

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

initializer< Ty > init(const Ty &Val)

const_iterator begin(StringRef path LLVM_LIFETIME_BOUND, Style style=Style::native)

Get begin iterator over path.

const_iterator end(StringRef path LLVM_LIFETIME_BOUND)

Get end iterator over path.

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.

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

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

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

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

char & BranchFolderPassID

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

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.

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

Pair of physical register and lane mask.