58 #define DEBUG_TYPE "if-converter"
83 STATISTIC(NumSimple,
"Number of simple if-conversions performed");
84 STATISTIC(NumSimpleFalse,
"Number of simple (F) if-conversions performed");
85 STATISTIC(NumTriangle,
"Number of triangle if-conversions performed");
86 STATISTIC(NumTriangleRev,
"Number of triangle (R) if-conversions performed");
87 STATISTIC(NumTriangleFalse,
"Number of triangle (F) if-conversions performed");
88 STATISTIC(NumTriangleFRev,
"Number of triangle (F/R) if-conversions performed");
89 STATISTIC(NumDiamonds,
"Number of diamond if-conversions performed");
90 STATISTIC(NumForkedDiamonds,
"Number of forked-diamond if-conversions performed");
91 STATISTIC(NumIfConvBBs,
"Number of if-converted blocks");
92 STATISTIC(NumDupBBs,
"Number of duplicated blocks");
93 STATISTIC(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;
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();
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();
456 if (!
TII)
return false;
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;
587 NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev +
588 NumTriangleFalse + NumTriangleFRev + NumDiamonds;
595 MadeChange |= Change;
606 MadeChange |= BFChange;
614 if (SuccBB != TrueBB)
622 bool IfConverter::reverseBranchCondition(BBInfo &BBI)
const {
646 bool 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;
671 bool 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;
733 bool 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())
813 bool 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.");
877 bool 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;
959 bool 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;
1022 void 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;
1058 void 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;
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;
1140 BBI.IsUnpredicable =
true;
1146 std::vector<MachineOperand> PredDefs;
1148 BBI.ClobbersPred =
true;
1151 BBI.IsUnpredicable =
true;
1166 bool 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()) {
1209 void 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;
1430 void 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)
1491 Redefs.stepForward(
MI, Clobbers);
1494 for (
auto Clobber : Clobbers) {
1497 unsigned Reg = Clobber.first;
1501 if (
Op.isRegMask()) {
1518 bool HasLiveSubReg =
false;
1520 if (!LiveBeforeMI.
count(*
S))
1522 HasLiveSubReg =
true;
1532 bool 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)
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;
1617 bool 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;
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;
1771 bool 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)
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())
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())
1957 Defs.push_back(
Reg);
1958 }
else if (!RedefsByFalse.
count(
Reg)) {
1963 ExtUses.
insert(*SubRegs);
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);
2007 bool 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);
2043 bool 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))
2133 void 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;
2176 void 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;
2242 void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI,
bool AddEdges) {
2245 "Removing a BB whose address is taken!");
2251 ToBBI.BB->splice(ToTI, &FromMBB, FromMBB.
begin(), FromTI);
2255 ToTI = ToBBI.BB->end();
2256 ToBBI.BB->splice(ToTI, &FromMBB, FromTI, FromMBB.
end());
2262 if (ToBBI.IsBrAnalyzable)
2263 ToBBI.BB->normalizeSuccProbs();
2271 if (AddEdges && ToBBI.BB->isSuccessor(&FromMBB)) {
2275 ToBBI.BB->removeSuccessor(&FromMBB);
2280 if (Succ == FallThrough) {
2298 if (!To2FromProb.isZero())
2299 NewProb *= To2FromProb;
2327 if (ToBBI.BB->isSuccessor(Succ))
2328 ToBBI.BB->setSuccProbability(
2329 find(ToBBI.BB->successors(), Succ),
2332 ToBBI.BB->addSuccessor(Succ, NewProb);
2339 if (Last != &FromMBB)
2344 if (ToBBI.IsBrAnalyzable && FromBBI.IsBrAnalyzable)
2345 ToBBI.BB->normalizeSuccProbs();
2347 ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
2348 FromBBI.Predicate.clear();
2350 ToBBI.NonPredSize += FromBBI.NonPredSize;
2351 ToBBI.ExtraCost += FromBBI.ExtraCost;
2352 ToBBI.ExtraCost2 += FromBBI.ExtraCost2;
2353 FromBBI.NonPredSize = 0;
2354 FromBBI.ExtraCost = 0;
2355 FromBBI.ExtraCost2 = 0;
2357 ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
2358 ToBBI.HasFallThrough = FromBBI.HasFallThrough;
2359 ToBBI.IsAnalyzed =
false;
2360 FromBBI.IsAnalyzed =
false;
2365 return new IfConverter(
std::move(Ftor));