58#define DEBUG_TYPE "if-converter"
83STATISTIC(NumSimple,
"Number of simple if-conversions performed");
84STATISTIC(NumSimpleFalse,
"Number of simple (F) if-conversions performed");
85STATISTIC(NumTriangle,
"Number of triangle if-conversions performed");
86STATISTIC(NumTriangleRev,
"Number of triangle (R) if-conversions performed");
87STATISTIC(NumTriangleFalse,
"Number of triangle (F) if-conversions performed");
88STATISTIC(NumTriangleFRev,
"Number of triangle (F/R) if-conversions performed");
89STATISTIC(NumDiamonds,
"Number of diamond if-conversions performed");
90STATISTIC(NumForkedDiamonds,
"Number of forked-diamond if-conversions performed");
91STATISTIC(NumIfConvBBs,
"Number of if-converted blocks");
93STATISTIC(NumUnpred,
"Number of true blocks of diamonds unpredicated");
136 bool IsBeingAnalyzed : 1;
139 bool IsBrAnalyzable : 1;
140 bool IsBrReversible : 1;
141 bool HasFallThrough : 1;
142 bool IsUnpredicable : 1;
143 bool CannotBeCopied : 1;
144 bool ClobbersPred : 1;
145 unsigned NonPredSize = 0;
146 unsigned ExtraCost = 0;
147 unsigned ExtraCost2 = 0;
154 BBInfo() : IsDone(
false), IsBeingAnalyzed(
false),
158 ClobbersPred(
false) {}
177 bool NeedSubsumption : 1;
178 bool TClobbersPred : 1;
179 bool FClobbersPred : 1;
181 IfcvtToken(BBInfo &b, IfcvtKind k,
bool s,
unsigned d,
unsigned d2 = 0,
182 bool tc =
false,
bool fc =
false)
183 : BBI(
b),
Kind(
k), NumDups(d), NumDups2(d2), NeedSubsumption(s),
184 TClobbersPred(tc), FClobbersPred(fc) {}
189 std::vector<BBInfo> BBAnalysis;
208 IfConverter(std::function<
bool(
const MachineFunction &)> Ftor =
nullptr)
224 MachineFunctionProperties::Property::NoVRegs);
228 bool reverseBranchCondition(BBInfo &BBI)
const;
229 bool ValidSimple(BBInfo &TrueBBI,
unsigned &Dups,
231 bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
232 bool FalseBranch,
unsigned &Dups,
234 bool CountDuplicatedInstructions(
237 unsigned &Dups1,
unsigned &Dups2,
239 bool SkipUnconditionalBranches)
const;
240 bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
241 unsigned &Dups1,
unsigned &Dups2,
242 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc)
const;
243 bool ValidForkedDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
244 unsigned &Dups1,
unsigned &Dups2,
245 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc)
const;
246 void AnalyzeBranches(BBInfo &BBI);
247 void ScanInstructions(BBInfo &BBI,
250 bool BranchUnpredicable =
false)
const;
251 bool RescanInstructions(
254 BBInfo &TrueBBI, BBInfo &FalseBBI)
const;
256 std::vector<std::unique_ptr<IfcvtToken>> &Tokens);
258 bool isTriangle =
false,
bool RevBranch =
false,
259 bool hasCommonTail =
false);
261 std::vector<std::unique_ptr<IfcvtToken>> &Tokens);
263 bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind);
264 bool IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind);
265 bool IfConvertDiamondCommon(BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,
266 unsigned NumDups1,
unsigned NumDups2,
267 bool TClobbersPred,
bool FClobbersPred,
268 bool RemoveBranch,
bool MergeAddEdges);
269 bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
270 unsigned NumDups1,
unsigned NumDups2,
271 bool TClobbers,
bool FClobbers);
272 bool IfConvertForkedDiamond(BBInfo &BBI, IfcvtKind Kind,
273 unsigned NumDups1,
unsigned NumDups2,
274 bool TClobbers,
bool FClobbers);
275 void PredicateBlock(BBInfo &BBI,
279 void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
281 bool IgnoreBr =
false);
282 void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI,
bool AddEdges =
true);
285 unsigned Cycle,
unsigned Extra,
291 bool MeetIfcvtSizeLimit(BBInfo &TBBInfo, BBInfo &FBBInfo,
301 unsigned Dups1 = 0, Dups2 = 0;
302 if (!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,
303 *TBBInfo.BB, *FBBInfo.BB,
307 unsigned BranchBytes = 0;
308 unsigned CommonBytes = 0;
311 for (
auto &
I :
make_range(TBBInfo.BB->begin(), TIB)) {
313 CommonBytes +=
TII->getInstSizeInBytes(
I);
315 for (
auto &
I :
make_range(FBBInfo.BB->begin(), FIB)) {
317 CommonBytes +=
TII->getInstSizeInBytes(
I);
324 for (
auto &
I :
make_range(TIE, TBBInfo.BB->end())) {
325 if (
I.isBranch() && TBBInfo.IsBrAnalyzable && !Forked) {
327 BranchBytes +=
TII->predictBranchSizeForIfCvt(
I);
330 CommonBytes +=
TII->getInstSizeInBytes(
I);
333 for (
auto &
I :
make_range(FIE, FBBInfo.BB->end())) {
334 if (
I.isBranch() && FBBInfo.IsBrAnalyzable && !Forked) {
336 BranchBytes +=
TII->predictBranchSizeForIfCvt(
I);
339 CommonBytes +=
TII->getInstSizeInBytes(
I);
345 BranchBytes +=
TII->predictBranchSizeForIfCvt(
I);
354 unsigned NumPredicatedInstructions = 0;
356 if (!
I.isDebugInstr()) {
358 NumPredicatedInstructions++;
362 if (!
I.isDebugInstr()) {
364 NumPredicatedInstructions++;
370 if (NumPredicatedInstructions > 15)
375 unsigned ExtraPredicateBytes =
TII->extraSizeToPredicateInstructions(
376 MF, NumPredicatedInstructions);
378 LLVM_DEBUG(
dbgs() <<
"MeetIfcvtSizeLimit(BranchBytes=" << BranchBytes
379 <<
", CommonBytes=" << CommonBytes
380 <<
", NumPredicatedInstructions="
381 << NumPredicatedInstructions
382 <<
", ExtraPredicateBytes=" << ExtraPredicateBytes
384 return (BranchBytes + CommonBytes) > ExtraPredicateBytes;
386 unsigned TCycle = TBBInfo.NonPredSize + TBBInfo.ExtraCost - Dups;
387 unsigned FCycle = FBBInfo.NonPredSize + FBBInfo.ExtraCost - Dups;
388 bool Res = TCycle > 0 && FCycle > 0 &&
390 *TBBInfo.BB, TCycle, TBBInfo.ExtraCost2, *FBBInfo.BB,
391 FCycle, FBBInfo.ExtraCost2, Prediction);
393 <<
", FCycle=" << FCycle
394 <<
", TExtra=" << TBBInfo.ExtraCost2 <<
", FExtra="
395 << FBBInfo.ExtraCost2 <<
") = " << Res <<
"\n");
401 bool blockAlwaysFallThrough(BBInfo &BBI)
const {
402 return BBI.IsBrAnalyzable && BBI.TrueBB ==
nullptr;
406 static bool IfcvtTokenCmp(
const std::unique_ptr<IfcvtToken> &C1,
407 const std::unique_ptr<IfcvtToken> &C2) {
408 int Incr1 = (C1->Kind == ICDiamond)
409 ? -(
int)(C1->NumDups + C1->NumDups2) : (
int)C1->NumDups;
410 int Incr2 = (C2->Kind == ICDiamond)
411 ? -(
int)(C2->NumDups + C2->NumDups2) : (
int)C2->NumDups;
414 else if (Incr1 == Incr2) {
416 if (!C1->NeedSubsumption && C2->NeedSubsumption)
418 else if (C1->NeedSubsumption == C2->NeedSubsumption) {
420 if ((
unsigned)C1->Kind < (
unsigned)C2->Kind)
422 else if (C1->Kind == C2->Kind)
423 return C1->BBI.BB->getNumber() < C2->BBI.BB->getNumber();
432char IfConverter::ID = 0;
442 if (skipFunction(MF.getFunction()) || (PredicateFtor && !PredicateFtor(MF)))
446 TLI = ST.getTargetLowering();
447 TII = ST.getInstrInfo();
448 TRI = ST.getRegisterInfo();
449 MBFIWrapper MBFI(getAnalysis<MachineBlockFrequencyInfo>());
450 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
452 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
453 MRI = &MF.getRegInfo();
454 SchedModel.
init(&ST);
456 if (!
TII)
return false;
458 PreRegAlloc =
MRI->isSSA();
460 bool BFChange =
false;
468 << MF.getName() <<
"\'");
477 BBAnalysis.resize(MF.getNumBlockIDs());
479 std::vector<std::unique_ptr<IfcvtToken>> Tokens;
481 unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle +
482 NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds;
487 AnalyzeBlocks(MF, Tokens);
488 while (!Tokens.empty()) {
489 std::unique_ptr<IfcvtToken> Token = std::move(Tokens.back());
491 BBInfo &BBI = Token->BBI;
492 IfcvtKind Kind = Token->Kind;
493 unsigned NumDups = Token->NumDups;
494 unsigned NumDups2 = Token->NumDups2;
499 BBI.IsEnqueued =
false;
503 BBI.IsEnqueued =
false;
509 case ICSimpleFalse: {
510 bool isFalse = Kind == ICSimpleFalse;
513 << (Kind == ICSimpleFalse ?
" false" :
"")
515 << ((Kind == ICSimpleFalse) ? BBI.FalseBB->getNumber()
516 : BBI.TrueBB->getNumber())
518 RetVal = IfConvertSimple(BBI, Kind);
519 LLVM_DEBUG(
dbgs() << (RetVal ?
"succeeded!" :
"failed!") <<
"\n");
521 if (isFalse) ++NumSimpleFalse;
528 case ICTriangleFalse:
529 case ICTriangleFRev: {
530 bool isFalse = Kind == ICTriangleFalse;
531 bool isRev = (Kind == ICTriangleRev || Kind == ICTriangleFRev);
542 <<
" (T:" << BBI.TrueBB->getNumber()
543 <<
",F:" << BBI.FalseBB->getNumber() <<
") ");
544 RetVal = IfConvertTriangle(BBI, Kind);
545 LLVM_DEBUG(
dbgs() << (RetVal ?
"succeeded!" :
"failed!") <<
"\n");
548 if (isRev) ++NumTriangleFRev;
549 else ++NumTriangleFalse;
551 if (isRev) ++NumTriangleRev;
560 <<
" (T:" << BBI.TrueBB->getNumber()
561 <<
",F:" << BBI.FalseBB->getNumber() <<
") ");
562 RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2,
563 Token->TClobbersPred,
564 Token->FClobbersPred);
565 LLVM_DEBUG(
dbgs() << (RetVal ?
"succeeded!" :
"failed!") <<
"\n");
566 if (RetVal) ++NumDiamonds;
568 case ICForkedDiamond:
572 <<
" (T:" << BBI.TrueBB->getNumber()
573 <<
",F:" << BBI.FalseBB->getNumber() <<
") ");
574 RetVal = IfConvertForkedDiamond(BBI, Kind, NumDups, NumDups2,
575 Token->TClobbersPred,
576 Token->FClobbersPred);
577 LLVM_DEBUG(
dbgs() << (RetVal ?
"succeeded!" :
"failed!") <<
"\n");
578 if (RetVal) ++NumForkedDiamonds;
582 if (RetVal &&
MRI->tracksLiveness())
587 NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev +
588 NumTriangleFalse + NumTriangleFRev + NumDiamonds;
595 MadeChange |= Change;
606 MadeChange |= BFChange;
614 if (SuccBB != TrueBB)
622bool IfConverter::reverseBranchCondition(BBInfo &BBI)
const {
646bool IfConverter::ValidSimple(BBInfo &TrueBBI,
unsigned &Dups,
649 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
652 if (TrueBBI.IsBrAnalyzable)
655 if (TrueBBI.BB->pred_size() > 1) {
656 if (TrueBBI.CannotBeCopied ||
660 Dups = TrueBBI.NonPredSize;
671bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
672 bool FalseBranch,
unsigned &Dups,
675 if (TrueBBI.BB == FalseBBI.BB)
678 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
681 if (TrueBBI.BB->pred_size() > 1) {
682 if (TrueBBI.CannotBeCopied)
685 unsigned Size = TrueBBI.NonPredSize;
686 if (TrueBBI.IsBrAnalyzable) {
687 if (TrueBBI.TrueBB && TrueBBI.BrCond.empty())
692 ? TrueBBI.TrueBB : TrueBBI.FalseBB;
704 if (!TExit && blockAlwaysFallThrough(TrueBBI)) {
706 if (++
I == TrueBBI.BB->getParent()->end())
710 return TExit && TExit == FalseBBI.BB;
733bool IfConverter::CountDuplicatedInstructions(
738 unsigned &Dups1,
unsigned &Dups2,
740 bool SkipUnconditionalBranches)
const {
741 while (TIB != TIE && FIB != FIE) {
745 if (TIB == TIE || FIB == FIE)
747 if (!TIB->isIdenticalTo(*FIB))
751 std::vector<MachineOperand> PredDefs;
755 if (!TIB->isBranch())
762 if (TIB == TIE || FIB == FIE)
774 if (SkipUnconditionalBranches) {
775 while (RTIE != RTIB && RTIE->isUnconditionalBranch())
777 while (RFIE != RFIB && RFIE->isUnconditionalBranch())
783 while (RTIE != RTIB && RFIE != RFIB) {
788 if (RTIE == RTIB || RFIE == RFIB)
790 if (!RTIE->isIdenticalTo(*RFIE))
794 if (!RTIE->isBranch())
813bool IfConverter::RescanInstructions(
816 BBInfo &TrueBBI, BBInfo &FalseBBI)
const {
817 bool BranchUnpredicable =
true;
818 TrueBBI.IsUnpredicable = FalseBBI.IsUnpredicable =
false;
819 ScanInstructions(TrueBBI, TIB, TIE, BranchUnpredicable);
820 if (TrueBBI.IsUnpredicable)
822 ScanInstructions(FalseBBI, FIB, FIE, BranchUnpredicable);
823 if (FalseBBI.IsUnpredicable)
825 if (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred)
838 while (E1 != B1 && E2 != B2) {
841 if (E1 == B1 && E2 == B2)
845 assert(!E2->isBranch() &&
"Branch mis-match, one block is empty.");
849 assert(!E1->isBranch() &&
"Branch mis-match, one block is empty.");
853 if (E1->isBranch() || E2->isBranch())
854 assert(E1->isIdenticalTo(*E2) &&
855 "Branch mis-match, branch instructions don't match.");
877bool IfConverter::ValidForkedDiamond(
878 BBInfo &TrueBBI, BBInfo &FalseBBI,
879 unsigned &Dups1,
unsigned &Dups2,
880 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc)
const {
882 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||
883 FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)
886 if (!TrueBBI.IsBrAnalyzable || !FalseBBI.IsBrAnalyzable)
889 if (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
894 if (TrueBBI.BrCond.size() == 0 ||
895 FalseBBI.BrCond.size() == 0)
916 if (!((TT == FT && TF == FF) || (TF == FT && TT == FF)))
919 bool FalseReversed =
false;
920 if (TF == FT && TT == FF) {
922 if (!FalseBBI.IsBrReversible)
924 FalseReversed =
true;
925 reverseBranchCondition(FalseBBI);
929 reverseBranchCondition(FalseBBI);
937 if(!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,
938 *TrueBBI.BB, *FalseBBI.BB,
942 TrueBBICalc.BB = TrueBBI.BB;
943 FalseBBICalc.BB = FalseBBI.BB;
944 TrueBBICalc.IsBrAnalyzable = TrueBBI.IsBrAnalyzable;
945 FalseBBICalc.IsBrAnalyzable = FalseBBI.IsBrAnalyzable;
946 if (!RescanInstructions(TIB, FIB, TIE, FIE, TrueBBICalc, FalseBBICalc))
952 TrueBBICalc.NonPredSize = TrueBBI.NonPredSize;
953 FalseBBICalc.NonPredSize = FalseBBI.NonPredSize;
959bool IfConverter::ValidDiamond(
960 BBInfo &TrueBBI, BBInfo &FalseBBI,
961 unsigned &Dups1,
unsigned &Dups2,
962 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc)
const {
964 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||
965 FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)
970 if (TrueBBI.BB == FalseBBI.BB)
976 if (!TT && blockAlwaysFallThrough(TrueBBI))
978 if (!FT && blockAlwaysFallThrough(FalseBBI))
982 if (!TT && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))
984 if (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
988 if (TrueBBI.FalseBB || FalseBBI.FalseBB)
995 bool SkipUnconditionalBranches =
996 TrueBBI.IsBrAnalyzable && FalseBBI.IsBrAnalyzable;
1001 if(!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,
1002 *TrueBBI.BB, *FalseBBI.BB,
1003 SkipUnconditionalBranches))
1006 TrueBBICalc.BB = TrueBBI.BB;
1007 FalseBBICalc.BB = FalseBBI.BB;
1008 TrueBBICalc.IsBrAnalyzable = TrueBBI.IsBrAnalyzable;
1009 FalseBBICalc.IsBrAnalyzable = FalseBBI.IsBrAnalyzable;
1010 if (!RescanInstructions(TIB, FIB, TIE, FIE, TrueBBICalc, FalseBBICalc))
1015 TrueBBICalc.NonPredSize = TrueBBI.NonPredSize;
1016 FalseBBICalc.NonPredSize = FalseBBI.NonPredSize;
1022void IfConverter::AnalyzeBranches(BBInfo &BBI) {
1026 BBI.TrueBB = BBI.FalseBB =
nullptr;
1028 BBI.IsBrAnalyzable =
1030 if (!BBI.IsBrAnalyzable) {
1031 BBI.TrueBB =
nullptr;
1032 BBI.FalseBB =
nullptr;
1037 BBI.IsBrReversible = (RevCond.size() == 0) ||
1039 BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB ==
nullptr;
1041 if (BBI.BrCond.size()) {
1048 BBI.IsUnpredicable =
true;
1058void IfConverter::ScanInstructions(BBInfo &BBI,
1061 bool BranchUnpredicable)
const {
1062 if (BBI.IsDone || BBI.IsUnpredicable)
1065 bool AlreadyPredicated = !BBI.Predicate.empty();
1067 BBI.NonPredSize = 0;
1070 BBI.ClobbersPred =
false;
1072 if (
MI.isDebugInstr())
1105 if (
MI.isNotDuplicable() ||
MI.isConvergent())
1106 BBI.CannotBeCopied =
true;
1109 bool isCondBr = BBI.IsBrAnalyzable &&
MI.isConditionalBranch();
1111 if (BranchUnpredicable &&
MI.isBranch()) {
1112 BBI.IsUnpredicable =
true;
1120 if (!isPredicated) {
1122 unsigned ExtraPredCost =
TII->getPredicationCost(
MI);
1123 unsigned NumCycles = SchedModel.computeInstrLatency(&
MI,
false);
1125 BBI.ExtraCost += NumCycles-1;
1126 BBI.ExtraCost2 += ExtraPredCost;
1127 }
else if (!AlreadyPredicated) {
1131 BBI.IsUnpredicable =
true;
1135 if (BBI.ClobbersPred && !isPredicated) {
1140 BBI.IsUnpredicable =
true;
1146 std::vector<MachineOperand> PredDefs;
1148 BBI.ClobbersPred =
true;
1151 BBI.IsUnpredicable =
true;
1166bool IfConverter::FeasibilityAnalysis(BBInfo &BBI,
1168 bool isTriangle,
bool RevBranch,
1169 bool hasCommonTail) {
1174 if (BBI.IsDone || (BBI.IsUnpredicable && !hasCommonTail))
1180 if (BBI.Predicate.size() && !BBI.IsBrAnalyzable)
1188 if (!hasCommonTail && BBI.BrCond.size()) {
1209void IfConverter::AnalyzeBlock(
1216 bool SuccsAnalyzed =
false;
1222 while (!BBStack.empty()) {
1223 BBState &State = BBStack.back();
1225 BBInfo &BBI = BBAnalysis[BB->
getNumber()];
1227 if (!State.SuccsAnalyzed) {
1228 if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed) {
1234 BBI.IsBeingAnalyzed =
true;
1236 AnalyzeBranches(BBI);
1239 ScanInstructions(BBI, Begin, End);
1243 if (!BBI.IsBrAnalyzable || BBI.BrCond.empty() || BBI.IsDone) {
1244 BBI.IsBeingAnalyzed =
false;
1245 BBI.IsAnalyzed =
true;
1251 if (BBI.TrueBB == BB || BBI.FalseBB == BB) {
1252 BBI.IsBeingAnalyzed =
false;
1253 BBI.IsAnalyzed =
true;
1260 BBI.IsBeingAnalyzed =
false;
1261 BBI.IsAnalyzed =
true;
1267 State.SuccsAnalyzed =
true;
1268 BBStack.push_back(*BBI.FalseBB);
1269 BBStack.push_back(*BBI.TrueBB);
1273 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
1274 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1276 if (TrueBBI.IsDone && FalseBBI.IsDone) {
1277 BBI.IsBeingAnalyzed =
false;
1278 BBI.IsAnalyzed =
true;
1284 RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
1289 bool TNeedSub = !TrueBBI.Predicate.empty();
1290 bool FNeedSub = !FalseBBI.Predicate.empty();
1291 bool Enqueued =
false;
1296 BBInfo TrueBBICalc, FalseBBICalc;
1297 auto feasibleDiamond = [&](
bool Forked) {
1298 bool MeetsSize = MeetIfcvtSizeLimit(TrueBBICalc, FalseBBICalc, *BB,
1299 Dups + Dups2, Prediction, Forked);
1300 bool TrueFeasible = FeasibilityAnalysis(TrueBBI, BBI.BrCond,
1303 bool FalseFeasible = FeasibilityAnalysis(FalseBBI, RevCond,
1306 return MeetsSize && TrueFeasible && FalseFeasible;
1309 if (ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2,
1310 TrueBBICalc, FalseBBICalc)) {
1311 if (feasibleDiamond(
false)) {
1320 Tokens.push_back(std::make_unique<IfcvtToken>(
1321 BBI, ICDiamond, TNeedSub | FNeedSub, Dups, Dups2,
1322 (
bool) TrueBBICalc.ClobbersPred, (
bool) FalseBBICalc.ClobbersPred));
1325 }
else if (ValidForkedDiamond(TrueBBI, FalseBBI, Dups, Dups2,
1326 TrueBBICalc, FalseBBICalc)) {
1327 if (feasibleDiamond(
true)) {
1338 Tokens.push_back(std::make_unique<IfcvtToken>(
1339 BBI, ICForkedDiamond, TNeedSub | FNeedSub, Dups, Dups2,
1340 (
bool) TrueBBICalc.ClobbersPred, (
bool) FalseBBICalc.ClobbersPred));
1346 if (ValidTriangle(TrueBBI, FalseBBI,
false, Dups, Prediction) &&
1347 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
1348 TrueBBI.ExtraCost2, Prediction) &&
1349 FeasibilityAnalysis(TrueBBI, BBI.BrCond,
true)) {
1358 std::make_unique<IfcvtToken>(BBI, ICTriangle, TNeedSub, Dups));
1362 if (ValidTriangle(TrueBBI, FalseBBI,
true, Dups, Prediction) &&
1363 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
1364 TrueBBI.ExtraCost2, Prediction) &&
1365 FeasibilityAnalysis(TrueBBI, BBI.BrCond,
true,
true)) {
1367 std::make_unique<IfcvtToken>(BBI, ICTriangleRev, TNeedSub, Dups));
1371 if (ValidSimple(TrueBBI, Dups, Prediction) &&
1372 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
1373 TrueBBI.ExtraCost2, Prediction) &&
1374 FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {
1383 std::make_unique<IfcvtToken>(BBI, ICSimple, TNeedSub, Dups));
1389 if (ValidTriangle(FalseBBI, TrueBBI,
false, Dups,
1391 MeetIfcvtSizeLimit(*FalseBBI.BB,
1392 FalseBBI.NonPredSize + FalseBBI.ExtraCost,
1393 FalseBBI.ExtraCost2, Prediction.
getCompl()) &&
1394 FeasibilityAnalysis(FalseBBI, RevCond,
true)) {
1395 Tokens.push_back(std::make_unique<IfcvtToken>(BBI, ICTriangleFalse,
1400 if (ValidTriangle(FalseBBI, TrueBBI,
true, Dups,
1402 MeetIfcvtSizeLimit(*FalseBBI.BB,
1403 FalseBBI.NonPredSize + FalseBBI.ExtraCost,
1404 FalseBBI.ExtraCost2, Prediction.
getCompl()) &&
1405 FeasibilityAnalysis(FalseBBI, RevCond,
true,
true)) {
1407 std::make_unique<IfcvtToken>(BBI, ICTriangleFRev, FNeedSub, Dups));
1411 if (ValidSimple(FalseBBI, Dups, Prediction.
getCompl()) &&
1412 MeetIfcvtSizeLimit(*FalseBBI.BB,
1413 FalseBBI.NonPredSize + FalseBBI.ExtraCost,
1414 FalseBBI.ExtraCost2, Prediction.
getCompl()) &&
1415 FeasibilityAnalysis(FalseBBI, RevCond)) {
1417 std::make_unique<IfcvtToken>(BBI, ICSimpleFalse, FNeedSub, Dups));
1422 BBI.IsEnqueued = Enqueued;
1423 BBI.IsBeingAnalyzed =
false;
1424 BBI.IsAnalyzed =
true;
1430void IfConverter::AnalyzeBlocks(
1431 MachineFunction &MF, std::vector<std::unique_ptr<IfcvtToken>> &Tokens) {
1433 AnalyzeBlock(
MBB, Tokens);
1449 if (
I ==
E || !
I->empty() || !PI->isSuccessor(&*
I))
1454 return PI->isSuccessor(&*
I);
1461 BBInfo &PBBI = BBAnalysis[Predecessor->getNumber()];
1462 if (PBBI.IsDone || PBBI.BB == &
MBB)
1464 PBBI.IsAnalyzed =
false;
1465 PBBI.IsEnqueued =
false;
1487 for (
unsigned Reg : Redefs)
1488 LiveBeforeMI.
insert(Reg);
1494 for (
auto Clobber : Clobbers) {
1497 unsigned Reg = Clobber.first;
1501 if (Op.isRegMask()) {
1504 if (LiveBeforeMI.
count(Reg))
1515 if (LiveBeforeMI.
count(Reg))
1518 bool HasLiveSubReg =
false;
1520 if (!LiveBeforeMI.
count(*S))
1522 HasLiveSubReg =
true;
1532bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {
1533 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
1534 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1535 BBInfo *CvtBBI = &TrueBBI;
1536 BBInfo *NextBBI = &FalseBBI;
1539 if (Kind == ICSimpleFalse)
1544 if (CvtBBI->IsDone ||
1545 (CvtBBI->CannotBeCopied && CvtMBB.
pred_size() > 1)) {
1547 BBI.IsAnalyzed =
false;
1548 CvtBBI->IsAnalyzed =
false;
1556 if (Kind == ICSimpleFalse)
1562 if (
MRI->tracksLiveness()) {
1576 CopyAndPredicateBlock(BBI, *CvtBBI,
Cond);
1579 BBI.BB->removeSuccessor(&CvtMBB,
true);
1582 PredicateBlock(*CvtBBI, CvtMBB.
end(),
Cond);
1586 MergeBlocks(BBI, *CvtBBI);
1589 bool IterIfcvt =
true;
1592 BBI.HasFallThrough =
false;
1609 InvalidatePreds(*BBI.BB);
1610 CvtBBI->IsDone =
true;
1617bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
1618 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
1619 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1620 BBInfo *CvtBBI = &TrueBBI;
1621 BBInfo *NextBBI = &FalseBBI;
1625 if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
1630 if (CvtBBI->IsDone ||
1631 (CvtBBI->CannotBeCopied && CvtMBB.
pred_size() > 1)) {
1633 BBI.IsAnalyzed =
false;
1634 CvtBBI->IsAnalyzed =
false;
1642 if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
1646 if (Kind == ICTriangleRev || Kind == ICTriangleFRev) {
1647 if (reverseBranchCondition(*CvtBBI)) {
1653 BBInfo &PBBI = BBAnalysis[PBB->getNumber()];
1654 if (PBBI.IsEnqueued) {
1655 PBBI.IsAnalyzed =
false;
1656 PBBI.IsEnqueued =
false;
1665 if (
MRI->tracksLiveness()) {
1670 bool HasEarlyExit = CvtBBI->FalseBB !=
nullptr;
1688 CopyAndPredicateBlock(BBI, *CvtBBI,
Cond,
true);
1692 PredicateBlock(*CvtBBI, CvtMBB.
end(),
Cond);
1695 MergeBlocks(BBI, *CvtBBI,
false);
1699 BBI.BB->removeSuccessor(&CvtMBB,
true);
1704 CvtBBI->BrCond.end());
1715 auto NewNext = BBNext + BBCvt * CvtNext;
1716 auto NewTrueBBIter =
find(BBI.BB->successors(), NewTrueBB);
1717 if (NewTrueBBIter != BBI.BB->succ_end())
1718 BBI.BB->setSuccProbability(NewTrueBBIter, NewNext);
1720 auto NewFalse = BBCvt * CvtFalse;
1722 BBI.BB->addSuccessor(CvtBBI->FalseBB, NewFalse);
1727 bool FalseBBDead =
false;
1728 bool IterIfcvt =
true;
1730 if (!isFallThrough) {
1734 if (!HasEarlyExit &&
1735 NextMBB.
pred_size() == 1 && !NextBBI->HasFallThrough &&
1737 MergeBlocks(BBI, *NextBBI);
1741 BBI.HasFallThrough =
false;
1751 InvalidatePreds(*BBI.BB);
1752 CvtBBI->IsDone =
true;
1754 NextBBI->IsDone =
true;
1771bool IfConverter::IfConvertDiamondCommon(
1772 BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,
1773 unsigned NumDups1,
unsigned NumDups2,
1774 bool TClobbersPred,
bool FClobbersPred,
1775 bool RemoveBranch,
bool MergeAddEdges) {
1777 if (TrueBBI.IsDone || FalseBBI.IsDone ||
1778 TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1) {
1780 BBI.IsAnalyzed =
false;
1781 TrueBBI.IsAnalyzed =
false;
1782 FalseBBI.IsAnalyzed =
false;
1786 if (TrueBBI.BB->hasAddressTaken() || FalseBBI.BB->hasAddressTaken())
1793 BBInfo *BBI1 = &TrueBBI;
1794 BBInfo *BBI2 = &FalseBBI;
1802 bool DoSwap =
false;
1803 if (TClobbersPred && !FClobbersPred)
1805 else if (!TClobbersPred && !FClobbersPred) {
1806 if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)
1808 }
else if (TClobbersPred && FClobbersPred)
1828 if (
MRI->tracksLiveness()) {
1837 BBI1->NonPredSize -= NumDups1;
1838 BBI2->NonPredSize -= NumDups1;
1843 for (
unsigned i = 0; i < NumDups1; ++DI1) {
1844 if (DI1 == MBB1.
end())
1846 if (!DI1->isDebugInstr())
1849 while (NumDups1 != 0) {
1852 if (DI2->shouldUpdateCallSiteInfo())
1856 if (DI2 == MBB2.
end())
1858 if (!DI2->isDebugInstr())
1862 if (
MRI->tracksLiveness()) {
1869 BBI.BB->splice(BBI.BB->end(), &MBB1, MBB1.
begin(), DI1);
1880 if (!BBI1->IsBrAnalyzable)
1886 while (DI1 != MBB1.
begin()) {
1888 if (!Prev->isBranch() && !Prev->isDebugInstr())
1892 for (
unsigned i = 0; i != NumDups2; ) {
1901 if (DI1->shouldUpdateCallSiteInfo())
1905 if (!DI1->isDebugInstr())
1910 DI2 = BBI2->BB->end();
1918 while (DI2 != MBB2.
begin()) {
1920 if (!Prev->isBranch() && !Prev->isDebugInstr())
1925 while (NumDups2 != 0) {
1931 if (!DI2->isDebugInstr())
1945 if (
TII->isProfitableToUnpredicate(MBB1, MBB2)) {
1947 if (FI.isDebugInstr())
1958 }
else if (!RedefsByFalse.
count(Reg)) {
1963 ExtUses.
insert(*SubRegs);
1968 if (!ExtUses.
count(Reg)) {
1971 RedefsByFalse.
insert(*SubRegs);
1978 PredicateBlock(*BBI1, MBB1.
end(), *Cond1, &RedefsByFalse);
1987 if (!MBB2.
empty() && (DI2 == MBB2.
end())) {
1992 if (BB2NonPredicated && (BB1Predicated || !BBI2->IsBrAnalyzable))
1997 PredicateBlock(*BBI2, DI2, *Cond2);
2000 MergeBlocks(BBI, *BBI1, MergeAddEdges);
2001 MergeBlocks(BBI, *BBI2, MergeAddEdges);
2007bool IfConverter::IfConvertForkedDiamond(
2008 BBInfo &BBI, IfcvtKind Kind,
2009 unsigned NumDups1,
unsigned NumDups2,
2010 bool TClobbersPred,
bool FClobbersPred) {
2011 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
2012 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
2017 if (TIE != TrueBBI.BB->end())
2018 dl = TIE->getDebugLoc();
2022 if (!IfConvertDiamondCommon(
2023 BBI, TrueBBI, FalseBBI,
2025 TClobbersPred, FClobbersPred,
2032 TrueBBI.BrCond, dl);
2035 BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone =
true;
2036 InvalidatePreds(*BBI.BB);
2043bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
2044 unsigned NumDups1,
unsigned NumDups2,
2045 bool TClobbersPred,
bool FClobbersPred) {
2046 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
2047 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
2052 if (blockAlwaysFallThrough(TrueBBI))
2053 TailBB = FalseBBI.TrueBB;
2054 assert((TailBB || !TrueBBI.IsBrAnalyzable) &&
"Unexpected!");
2057 if (!IfConvertDiamondCommon(
2058 BBI, TrueBBI, FalseBBI,
2060 TClobbersPred, FClobbersPred,
2061 TrueBBI.IsBrAnalyzable,
2072 BBI.BB->removeSuccessor(TrueBBI.BB);
2073 BBI.BB->removeSuccessor(FalseBBI.BB,
true);
2075 BBInfo &TailBBI = BBAnalysis[TailBB->
getNumber()];
2076 bool CanMergeTail = !TailBBI.HasFallThrough &&
2077 !TailBBI.BB->hasAddressTaken();
2083 CanMergeTail =
false;
2086 unsigned NumPreds = TailBB->
pred_size();
2088 CanMergeTail =
false;
2089 else if (NumPreds == 1 && CanMergeTail) {
2091 if (*PI != TrueBBI.BB && *PI != FalseBBI.BB)
2092 CanMergeTail =
false;
2095 MergeBlocks(BBI, TailBBI);
2096 TailBBI.IsDone =
true;
2100 BBI.HasFallThrough =
false;
2105 BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone =
true;
2106 InvalidatePreds(*BBI.BB);
2114 bool SawStore =
true;
2115 if (!
MI.isSafeToMove(
nullptr, SawStore))
2124 if (MO.isDef() && !LaterRedefs.
count(Reg))
2133void IfConverter::PredicateBlock(BBInfo &BBI,
2137 bool AnyUnpred =
false;
2138 bool MaySpec = LaterRedefs !=
nullptr;
2154 dbgs() <<
"Unable to predicate " <<
I <<
"!\n";
2164 BBI.Predicate.append(
Cond.begin(),
Cond.end());
2166 BBI.IsAnalyzed =
false;
2167 BBI.NonPredSize = 0;
2176void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
2184 if (IgnoreBr &&
I.isBranch())
2189 if (
I.isCandidateForCallSiteEntry())
2192 ToBBI.BB->insert(ToBBI.BB->end(),
MI);
2193 ToBBI.NonPredSize++;
2194 unsigned ExtraPredCost =
TII->getPredicationCost(
I);
2195 unsigned NumCycles = SchedModel.computeInstrLatency(&
I,
false);
2197 ToBBI.ExtraCost += NumCycles-1;
2198 ToBBI.ExtraCost2 += ExtraPredCost;
2203 dbgs() <<
"Unable to predicate " <<
I <<
"!\n";
2215 std::vector<MachineBasicBlock *> Succs(FromMBB.succ_begin(),
2216 FromMBB.succ_end());
2222 if (Succ == FallThrough)
2224 ToBBI.BB->addSuccessor(Succ);
2228 ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
2229 ToBBI.Predicate.append(
Cond.begin(),
Cond.end());
2231 ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
2232 ToBBI.IsAnalyzed =
false;
2242void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI,
bool AddEdges) {
2245 "Removing a BB whose address is taken!");
2251 if (
MI.getOpcode() == TargetOpcode::INLINEASM_BR)
2253 if (MO.isMBB() && !ToBBI.BB->isSuccessor(MO.getMBB()))
2260 ToBBI.BB->splice(ToTI, &FromMBB, FromMBB.begin(), FromTI);
2264 ToTI = ToBBI.BB->end();
2265 ToBBI.BB->splice(ToTI, &FromMBB, FromTI, FromMBB.end());
2271 if (ToBBI.IsBrAnalyzable)
2272 ToBBI.BB->normalizeSuccProbs();
2280 if (AddEdges && ToBBI.BB->isSuccessor(&FromMBB)) {
2284 ToBBI.BB->removeSuccessor(&FromMBB);
2289 if (Succ == FallThrough) {
2290 FromMBB.removeSuccessor(Succ);
2307 if (!To2FromProb.isZero())
2308 NewProb *= To2FromProb;
2311 FromMBB.removeSuccessor(Succ);
2336 if (ToBBI.BB->isSuccessor(Succ))
2337 ToBBI.BB->setSuccProbability(
2338 find(ToBBI.BB->successors(), Succ),
2341 ToBBI.BB->addSuccessor(Succ, NewProb);
2348 if (
Last != &FromMBB)
2349 FromMBB.moveAfter(
Last);
2353 if (ToBBI.IsBrAnalyzable && FromBBI.IsBrAnalyzable)
2354 ToBBI.BB->normalizeSuccProbs();
2356 ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
2357 FromBBI.Predicate.clear();
2359 ToBBI.NonPredSize += FromBBI.NonPredSize;
2360 ToBBI.ExtraCost += FromBBI.ExtraCost;
2361 ToBBI.ExtraCost2 += FromBBI.ExtraCost2;
2362 FromBBI.NonPredSize = 0;
2363 FromBBI.ExtraCost = 0;
2364 FromBBI.ExtraCost2 = 0;
2366 ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
2367 ToBBI.HasFallThrough = FromBBI.HasFallThrough;
2368 ToBBI.IsAnalyzed =
false;
2369 FromBBI.IsAnalyzed =
false;
2374 return new IfConverter(std::move(Ftor));
unsigned const MachineRegisterInfo * MRI
SmallVector< MachineOperand, 4 > Cond
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const HexagonInstrInfo * TII
static cl::opt< bool > DisableTriangle("disable-ifcvt-triangle", cl::init(false), cl::Hidden)
static MachineBasicBlock * findFalseBlock(MachineBasicBlock *BB, MachineBasicBlock *TrueBB)
BB has a fallthrough. Find its 'false' successor given its 'true' successor.
static cl::opt< int > IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden)
static cl::opt< bool > IfCvtBranchFold("ifcvt-branch-fold", cl::init(true), cl::Hidden)
static cl::opt< bool > DisableTriangleF("disable-ifcvt-triangle-false", cl::init(false), cl::Hidden)
static cl::opt< int > IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden)
static void InsertUncondBranch(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB, const TargetInstrInfo *TII)
Inserts an unconditional branch from MBB to ToMBB.
static void verifySameBranchInstructions(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2)
static cl::opt< bool > DisableDiamond("disable-ifcvt-diamond", cl::init(false), cl::Hidden)
static cl::opt< bool > DisableTriangleR("disable-ifcvt-triangle-rev", cl::init(false), cl::Hidden)
static cl::opt< bool > DisableForkedDiamond("disable-ifcvt-forked-diamond", cl::init(false), cl::Hidden)
static MachineBasicBlock * getNextBlock(MachineBasicBlock &MBB)
Returns the next block in the function blocks ordering.
static void UpdatePredRedefs(MachineInstr &MI, LivePhysRegs &Redefs)
Behaves like LiveRegUnits::StepForward() but also adds implicit uses to all values defined in MI whic...
static cl::opt< bool > DisableSimpleF("disable-ifcvt-simple-false", cl::init(false), cl::Hidden)
static cl::opt< bool > DisableSimple("disable-ifcvt-simple", cl::init(false), cl::Hidden)
static cl::opt< bool > DisableTriangleFR("disable-ifcvt-triangle-false-rev", cl::init(false), cl::Hidden)
static bool canFallThroughTo(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB)
Returns true either if ToMBB is the next block after MBB or that all the intervening blocks are empty...
static cl::opt< int > IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden)
static bool MaySpeculate(const MachineInstr &MI, SmallSet< MCPhysReg, 4 > &LaterRedefs)
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the SparseSet class derived from the version described in Briggs,...
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
This file describes how to lower LLVM code to machine code.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii, const TargetRegisterInfo *tri, MachineLoopInfo *mli=nullptr, bool AfterPlacement=false)
Perhaps branch folding, tail merging and other CFG optimizations on the given function.
static BranchProbability getOne()
BranchProbability getCompl() const
static BranchProbability getZero()
FunctionPass class - This class is used to implement most global optimizations.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
A possibly irreducible generalization of a Loop.
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
bool isPredicated(const MachineInstr &MI) const override
Returns true if the instruction is already predicated.
bool ClobbersPredicate(MachineInstr &MI, std::vector< MachineOperand > &Pred, bool SkipDead) const override
If the specified instruction defines any predicate or condition code register(s) used for predication...
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const override
Reverses the branch condition of the specified condition list, returning false on success and true if...
unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override
Insert branch code into the end of the specified MachineBasicBlock.
bool isProfitableToIfCvt(MachineBasicBlock &MBB, unsigned NumCycles, unsigned ExtraPredCycles, BranchProbability Probability) const override
Return true if it's profitable to predicate instructions with accumulated instruction latency of "Num...
bool isProfitableToDupForIfCvt(MachineBasicBlock &MBB, unsigned NumCycles, BranchProbability Probability) const override
Return true if it's profitable for if-converter to duplicate instructions of specified accumulated in...
bool SubsumesPredicate(ArrayRef< MachineOperand > Pred1, ArrayRef< MachineOperand > Pred2) const override
Returns true if the first specified predicate subsumes the second, e.g.
bool PredicateInstruction(MachineInstr &MI, ArrayRef< MachineOperand > Cond) const override
Convert the instruction into a predicated instruction.
bool isPredicable(const MachineInstr &MI) const override
Return true if the specified instruction can be predicated.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
void stepForward(const MachineInstr &MI, SmallVectorImpl< std::pair< MCPhysReg, const MachineOperand * > > &Clobbers)
Simulates liveness when stepping forward over an instruction(bundle).
void init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
void addLiveInsNoPristines(const MachineBasicBlock &MBB)
Adds all live-in registers of basic block MBB but skips pristine registers.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
MCSubRegIterator enumerates all sub-registers of Reg.
unsigned pred_size() const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the first non-debug instruction in the basic block, or end().
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
bool hasAddressTaken() const
Test whether this block is used as as something other than the target of a terminator,...
pred_iterator pred_begin()
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
iterator_range< iterator > terminators()
iterator_range< succ_iterator > successors()
reverse_iterator rbegin()
iterator_range< pred_iterator > predecessors()
bool mayHaveInlineAsmBr() const
Returns true if this block may have an INLINEASM_BR (overestimate, by checking if any of the successo...
std::vector< MachineBasicBlock * >::iterator pred_iterator
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
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)
void copyCallSiteInfo(const MachineInstr *Old, const MachineInstr *New)
Copy the call site info from Old to \ New.
Function & getFunction()
Return the LLVM function that this machine code represents.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
void eraseCallSiteInfo(const MachineInstr *MI)
Following functions update call site info.
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
reverse_iterator getReverse() const
Get a reverse iterator to the same node.
Representation of each machine instruction.
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
MachineOperand class - Representation of each machine instruction operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Analysis providing profile information.
Wrapper class representing virtual and physical registers.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.
size_type count(const KeyT &Key) const
count - Returns 1 if this set contains an element identified by Key, 0 otherwise.
std::pair< iterator, bool > insert(const ValueT &Val)
insert - Attempts to insert a new element.
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
TargetInstrInfo - Interface to description of machine instruction set.
This base class for TargetLowering contains the SelectionDAG-independent parts that can be used from ...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Provide an instruction scheduling machine model to CodeGen passes.
void init(const TargetSubtargetInfo *TSInfo)
Initialize the machine model for instruction scheduling.
TargetSubtargetInfo - Generic base class for all target subtargets.
self_iterator getIterator()
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool isPredicated(const MCInst &MI, const MCInstrInfo *MCII)
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
@ Implicit
Not emitted register (e.g. carry, or temporary result).
@ Define
Register definition.
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
void stable_sort(R &&Range)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
FunctionPass * createIfConverter(std::function< bool(const MachineFunction &)> Ftor)
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
void initializeIfConverterPass(PassRegistry &)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=true)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void recomputeLivenessFlags(MachineBasicBlock &MBB)
Recomputes dead and kill flags in MBB.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
char & IfConverterID
IfConverter - This pass performs machine code if conversion.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.