62#define DEBUG_TYPE "if-converter"
64STATISTIC(NumSimple,
"Number of simple if-conversions performed");
65STATISTIC(NumSimpleFalse,
"Number of simple (F) if-conversions performed");
66STATISTIC(NumTriangle,
"Number of triangle if-conversions performed");
67STATISTIC(NumTriangleRev,
"Number of triangle (R) if-conversions performed");
68STATISTIC(NumTriangleFalse,
"Number of triangle (F) if-conversions performed");
69STATISTIC(NumTriangleFRev,
"Number of triangle (F/R) if-conversions performed");
70STATISTIC(NumDiamonds,
"Number of diamond if-conversions performed");
71STATISTIC(NumForkedDiamonds,
"Number of forked-diamond if-conversions performed");
72STATISTIC(NumIfConvBBs,
"Number of if-converted blocks");
74STATISTIC(NumUnpred,
"Number of true blocks of diamonds unpredicated");
78class IfConverterImpl {
124 bool IsBeingAnalyzed : 1;
127 bool IsBrAnalyzable : 1;
128 bool IsBrReversible : 1;
129 bool HasFallThrough : 1;
130 bool IsUnpredicable : 1;
131 bool CannotBeCopied : 1;
132 bool ClobbersPred : 1;
133 unsigned NonPredSize = 0;
134 unsigned ExtraCost = 0;
135 unsigned ExtraCost2 = 0;
136 MachineBasicBlock *BB =
nullptr;
137 MachineBasicBlock *TrueBB =
nullptr;
138 MachineBasicBlock *FalseBB =
nullptr;
139 SmallVector<MachineOperand, 4> BrCond;
140 SmallVector<MachineOperand, 4> Predicate;
146 ClobbersPred(
false) {}
165 bool NeedSubsumption : 1;
166 bool TClobbersPred : 1;
167 bool FClobbersPred : 1;
169 IfcvtToken(BBInfo &b, IfcvtKind k,
bool s,
unsigned d,
unsigned d2 = 0,
170 bool tc =
false,
bool fc =
false)
171 : BBI(
b), Kind(
k), NumDups(d), NumDups2(d2), NeedSubsumption(s),
172 TClobbersPred(tc), FClobbersPred(fc) {}
177 std::vector<BBInfo> BBAnalysis;
178 TargetSchedModel SchedModel;
180 const TargetLoweringBase *TLI =
nullptr;
181 const TargetInstrInfo *TII =
nullptr;
182 const TargetRegisterInfo *TRI =
nullptr;
183 const MachineBranchProbabilityInfo *MBPI =
nullptr;
184 MachineRegisterInfo *MRI =
nullptr;
188 bool PreRegAlloc =
true;
189 bool MadeChange =
false;
192 bool reverseBranchCondition(BBInfo &BBI)
const;
193 bool ValidSimple(BBInfo &TrueBBI,
unsigned &Dups,
194 BranchProbability Prediction)
const;
195 bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
bool FalseBranch,
196 unsigned &Dups, BranchProbability Prediction)
const;
197 bool CountDuplicatedInstructions(
200 unsigned &Dups1,
unsigned &Dups2, MachineBasicBlock &
TBB,
201 MachineBasicBlock &FBB,
bool SkipUnconditionalBranches)
const;
202 bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
unsigned &Dups1,
203 unsigned &Dups2, BBInfo &TrueBBICalc,
204 BBInfo &FalseBBICalc)
const;
205 bool ValidForkedDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
unsigned &Dups1,
206 unsigned &Dups2, BBInfo &TrueBBICalc,
207 BBInfo &FalseBBICalc)
const;
208 void AnalyzeBranches(BBInfo &BBI);
211 bool BranchUnpredicable =
false)
const;
216 BBInfo &FalseBBI)
const;
217 void AnalyzeBlock(MachineBasicBlock &
MBB,
218 std::vector<std::unique_ptr<IfcvtToken>> &Tokens);
219 bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &
Pred,
220 bool isTriangle =
false,
bool RevBranch =
false,
221 bool hasCommonTail =
false);
223 std::vector<std::unique_ptr<IfcvtToken>> &Tokens);
224 void InvalidatePreds(MachineBasicBlock &
MBB);
225 bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind);
226 bool IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind);
227 bool IfConvertDiamondCommon(BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,
228 unsigned NumDups1,
unsigned NumDups2,
229 bool TClobbersPred,
bool FClobbersPred,
230 bool RemoveBranch,
bool MergeAddEdges);
231 bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
unsigned NumDups1,
232 unsigned NumDups2,
bool TClobbers,
bool FClobbers);
233 bool IfConvertForkedDiamond(BBInfo &BBI, IfcvtKind Kind,
unsigned NumDups1,
234 unsigned NumDups2,
bool TClobbers,
237 SmallVectorImpl<MachineOperand> &
Cond,
238 SmallSet<MCRegister, 4> *LaterRedefs =
nullptr);
239 void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
240 SmallVectorImpl<MachineOperand> &
Cond,
241 bool IgnoreBr =
false);
242 void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI,
bool AddEdges =
true);
244 bool MeetIfcvtSizeLimit(MachineBasicBlock &BB,
unsigned Cycle,
unsigned Extra,
245 BranchProbability Prediction)
const {
246 return Cycle > 0 && TII->isProfitableToIfCvt(BB, Cycle, Extra, Prediction);
249 bool MeetIfcvtSizeLimit(BBInfo &TBBInfo, BBInfo &FBBInfo,
250 MachineBasicBlock &CommBB,
unsigned Dups,
251 BranchProbability Prediction,
bool Forked)
const {
259 unsigned Dups1 = 0, Dups2 = 0;
260 if (!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,
261 *TBBInfo.BB, *FBBInfo.BB,
265 unsigned BranchBytes = 0;
266 unsigned CommonBytes = 0;
269 for (
auto &
I :
make_range(TBBInfo.BB->begin(), TIB)) {
271 CommonBytes += TII->getInstSizeInBytes(
I);
273 for (
auto &
I :
make_range(FBBInfo.BB->begin(), FIB)) {
275 CommonBytes += TII->getInstSizeInBytes(
I);
282 for (
auto &
I :
make_range(TIE, TBBInfo.BB->end())) {
283 if (
I.isBranch() && TBBInfo.IsBrAnalyzable && !Forked) {
285 BranchBytes += TII->predictBranchSizeForIfCvt(
I);
288 CommonBytes += TII->getInstSizeInBytes(
I);
291 for (
auto &
I :
make_range(FIE, FBBInfo.BB->end())) {
292 if (
I.isBranch() && FBBInfo.IsBrAnalyzable && !Forked) {
294 BranchBytes += TII->predictBranchSizeForIfCvt(
I);
297 CommonBytes += TII->getInstSizeInBytes(
I);
303 BranchBytes += TII->predictBranchSizeForIfCvt(
I);
312 unsigned NumPredicatedInstructions = 0;
314 if (!
I.isDebugInstr()) {
316 NumPredicatedInstructions++;
320 if (!
I.isDebugInstr()) {
322 NumPredicatedInstructions++;
328 if (NumPredicatedInstructions > 15)
333 unsigned ExtraPredicateBytes =
334 TII->extraSizeToPredicateInstructions(MF, NumPredicatedInstructions);
337 dbgs() <<
"MeetIfcvtSizeLimit(BranchBytes=" << BranchBytes
338 <<
", CommonBytes=" << CommonBytes
339 <<
", NumPredicatedInstructions=" << NumPredicatedInstructions
340 <<
", ExtraPredicateBytes=" << ExtraPredicateBytes <<
")\n");
341 return (BranchBytes + CommonBytes) > ExtraPredicateBytes;
343 unsigned TCycle = TBBInfo.NonPredSize + TBBInfo.ExtraCost - Dups;
344 unsigned FCycle = FBBInfo.NonPredSize + FBBInfo.ExtraCost - Dups;
345 bool Res = TCycle > 0 && FCycle > 0 &&
346 TII->isProfitableToIfCvt(
347 *TBBInfo.BB, TCycle, TBBInfo.ExtraCost2, *FBBInfo.BB,
348 FCycle, FBBInfo.ExtraCost2, Prediction);
349 LLVM_DEBUG(
dbgs() <<
"MeetIfcvtSizeLimit(TCycle=" << TCycle <<
", FCycle="
350 << FCycle <<
", TExtra=" << TBBInfo.ExtraCost2
351 <<
", FExtra=" << FBBInfo.ExtraCost2 <<
") = " << Res
358 bool blockAlwaysFallThrough(BBInfo &BBI)
const {
359 return BBI.IsBrAnalyzable && BBI.TrueBB ==
nullptr;
363 bool blockNeverFallThrough(BBInfo &BBI)
const {
365 if (BBI.IsBrAnalyzable)
366 return !BBI.HasFallThrough;
371 if (
I == BBI.BB->getParent()->end() || !PI->isSuccessor(&*
I))
378 static bool IfcvtTokenCmp(
const std::unique_ptr<IfcvtToken> &
C1,
379 const std::unique_ptr<IfcvtToken> &C2) {
380 int Incr1 = (
C1->Kind == ICDiamond) ? -(
int)(
C1->NumDups +
C1->NumDups2)
382 int Incr2 = (C2->Kind == ICDiamond) ? -(int)(C2->NumDups + C2->NumDups2)
386 else if (Incr1 == Incr2) {
388 if (!
C1->NeedSubsumption && C2->NeedSubsumption)
390 else if (
C1->NeedSubsumption == C2->NeedSubsumption) {
392 if ((
unsigned)
C1->Kind < (
unsigned)C2->Kind)
394 else if (
C1->Kind == C2->Kind)
395 return C1->BBI.BB->getNumber() < C2->BBI.BB->getNumber();
402 bool runOnMachineFunction(
403 MachineFunction &MF, function_ref<MachineBlockFrequencyInfo &()> GetMBFI,
404 function_ref<MachineBranchProbabilityInfo *()> GetMBPI,
405 function_ref<ProfileSummaryInfo *()> GetPSI,
415 IfConverterLegacy(std::function<
bool(
const MachineFunction &)> Ftor =
nullptr)
416 : MachineFunctionPass(ID), PredicateFtor(std::
move(Ftor)) {}
418 void getAnalysisUsage(AnalysisUsage &AU)
const override {
419 AU.
addRequired<MachineBlockFrequencyInfoWrapperPass>();
420 AU.
addRequired<MachineBranchProbabilityInfoWrapperPass>();
428 MachineFunctionProperties getRequiredProperties()
const override {
429 return MachineFunctionProperties().setNoVRegs();
435char IfConverterLegacy::ID = 0;
445bool IfConverterImpl::runOnMachineFunction(
450 if (PredicateFtor(MF))
455 TLI = ST.getTargetLowering();
456 TII = ST.getInstrInfo();
457 TRI = ST.getRegisterInfo();
461 MRI = &MF.getRegInfo();
462 SchedModel.
init(&ST);
464 if (!
TII)
return false;
466 PreRegAlloc =
MRI->isSSA();
468 bool BFChange =
false;
476 << MF.getName() <<
"\'");
478 if (FnNum < Opts.ifcvt_fn_start ||
479 (Opts.ifcvt_fn_stop != -1 && FnNum > Opts.ifcvt_fn_stop)) {
486 BBAnalysis.resize(MF.getNumBlockIDs());
488 std::vector<std::unique_ptr<IfcvtToken>> Tokens;
490 unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle +
491 NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds;
492 while (Opts.ifcvt_limit == -1 || (
int)NumIfCvts < Opts.ifcvt_limit) {
496 AnalyzeBlocks(MF, Tokens);
497 while (!Tokens.empty()) {
498 std::unique_ptr<IfcvtToken> Token = std::move(Tokens.back());
500 BBInfo &BBI = Token->BBI;
501 IfcvtKind Kind = Token->Kind;
502 unsigned NumDups = Token->NumDups;
503 unsigned NumDups2 = Token->NumDups2;
508 BBI.IsEnqueued =
false;
512 BBI.IsEnqueued =
false;
518 case ICSimpleFalse: {
519 bool isFalse = Kind == ICSimpleFalse;
520 if ((isFalse && !Opts.ifcvt_simple_false) ||
521 (!isFalse && !Opts.ifcvt_simple))
524 << (Kind == ICSimpleFalse ?
" false" :
"")
526 << ((Kind == ICSimpleFalse) ? BBI.FalseBB->getNumber()
527 : BBI.TrueBB->getNumber())
529 RetVal = IfConvertSimple(BBI, Kind);
530 LLVM_DEBUG(
dbgs() << (RetVal ?
"succeeded!" :
"failed!") <<
"\n");
532 if (isFalse) ++NumSimpleFalse;
539 case ICTriangleFalse:
540 case ICTriangleFRev: {
541 bool isFalse = Kind == ICTriangleFalse;
542 bool isRev = (Kind == ICTriangleRev || Kind == ICTriangleFRev);
543 if (!Opts.ifcvt_triangle && !isFalse && !isRev)
545 if (!Opts.ifcvt_triangle_rev && !isFalse && isRev)
547 if (!Opts.ifcvt_triangle_false && isFalse && !isRev)
555 <<
" (T:" << BBI.TrueBB->getNumber()
556 <<
",F:" << BBI.FalseBB->getNumber() <<
") ");
557 RetVal = IfConvertTriangle(BBI, Kind);
558 LLVM_DEBUG(
dbgs() << (RetVal ?
"succeeded!" :
"failed!") <<
"\n");
570 if (!Opts.ifcvt_diamond)
573 <<
" (T:" << BBI.TrueBB->getNumber()
574 <<
",F:" << BBI.FalseBB->getNumber() <<
") ");
575 RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2,
576 Token->TClobbersPred,
577 Token->FClobbersPred);
578 LLVM_DEBUG(
dbgs() << (RetVal ?
"succeeded!" :
"failed!") <<
"\n");
579 if (RetVal) ++NumDiamonds;
581 case ICForkedDiamond:
582 if (!Opts.ifcvt_forked_diamond)
586 <<
" (T:" << BBI.TrueBB->getNumber()
587 <<
",F:" << BBI.FalseBB->getNumber() <<
") ");
588 RetVal = IfConvertForkedDiamond(BBI, Kind, NumDups, NumDups2,
589 Token->TClobbersPred,
590 Token->FClobbersPred);
591 LLVM_DEBUG(
dbgs() << (RetVal ?
"succeeded!" :
"failed!") <<
"\n");
592 if (RetVal) ++NumForkedDiamonds;
596 if (RetVal &&
MRI->tracksLiveness())
601 NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev +
602 NumTriangleFalse + NumTriangleFRev + NumDiamonds;
603 if (Opts.ifcvt_limit != -1 && (
int)NumIfCvts >= Opts.ifcvt_limit)
609 MadeChange |= Change;
615 if (MadeChange && Opts.ifcvt_branch_fold) {
620 MadeChange |= BFChange;
628 if (SuccBB != TrueBB)
636bool IfConverterImpl::reverseBranchCondition(BBInfo &BBI)
const {
660bool IfConverterImpl::ValidSimple(BBInfo &TrueBBI,
unsigned &Dups,
661 BranchProbability Prediction)
const {
663 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
666 if (TrueBBI.IsBrAnalyzable)
669 if (TrueBBI.BB->pred_size() > 1) {
670 if (TrueBBI.CannotBeCopied ||
671 !
TII->isProfitableToDupForIfCvt(*TrueBBI.BB, TrueBBI.NonPredSize,
674 Dups = TrueBBI.NonPredSize;
685bool IfConverterImpl::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
686 bool FalseBranch,
unsigned &Dups,
687 BranchProbability Prediction)
const {
689 if (TrueBBI.BB == FalseBBI.BB)
692 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
695 if (TrueBBI.BB->pred_size() > 1) {
696 if (TrueBBI.CannotBeCopied)
699 unsigned Size = TrueBBI.NonPredSize;
700 if (TrueBBI.IsBrAnalyzable) {
701 if (TrueBBI.TrueBB && TrueBBI.BrCond.empty())
705 MachineBasicBlock *FExit = FalseBranch
706 ? TrueBBI.TrueBB : TrueBBI.FalseBB;
712 if (!
TII->isProfitableToDupForIfCvt(*TrueBBI.BB,
Size, Prediction))
717 MachineBasicBlock *TExit = FalseBranch ? TrueBBI.FalseBB : TrueBBI.TrueBB;
718 if (!TExit && blockAlwaysFallThrough(TrueBBI)) {
720 if (++
I == TrueBBI.BB->getParent()->end())
724 return TExit && TExit == FalseBBI.BB;
747bool IfConverterImpl::CountDuplicatedInstructions(
750 unsigned &Dups1,
unsigned &Dups2, MachineBasicBlock &
TBB,
751 MachineBasicBlock &FBB,
bool SkipUnconditionalBranches)
const {
752 while (TIB != TIE && FIB != FIE) {
756 if (TIB == TIE || FIB == FIE)
758 if (!TIB->isIdenticalTo(*FIB))
762 std::vector<MachineOperand> PredDefs;
763 if (
TII->ClobbersPredicate(*TIB, PredDefs,
false))
766 if (!TIB->isBranch())
773 if (TIB == TIE || FIB == FIE)
785 if (SkipUnconditionalBranches) {
786 while (RTIE != RTIB && RTIE->isUnconditionalBranch())
788 while (RFIE != RFIB && RFIE->isUnconditionalBranch())
794 while (RTIE != RTIB && RFIE != RFIB) {
799 if (RTIE == RTIB || RFIE == RFIB)
801 if (!RTIE->isIdenticalTo(*RFIE))
805 if (!RTIE->isBranch())
829 BBInfo &FalseBBI)
const {
830 bool BranchUnpredicable =
true;
831 TrueBBI.IsUnpredicable = FalseBBI.IsUnpredicable =
false;
832 ScanInstructions(TrueBBI, TIB, TIE, BranchUnpredicable);
833 if (TrueBBI.IsUnpredicable)
835 ScanInstructions(FalseBBI, FIB, FIE, BranchUnpredicable);
836 if (FalseBBI.IsUnpredicable)
838 if (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred)
851 while (E1 != B1 && E2 != B2) {
854 if (E1 == B1 && E2 == B2)
858 assert(!E2->isBranch() &&
"Branch mis-match, one block is empty.");
862 assert(!E1->isBranch() &&
"Branch mis-match, one block is empty.");
866 if (E1->isBranch() || E2->isBranch())
867 assert(E1->isIdenticalTo(*E2) &&
868 "Branch mis-match, branch instructions don't match.");
890bool IfConverterImpl::ValidForkedDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
891 unsigned &Dups1,
unsigned &Dups2,
893 BBInfo &FalseBBICalc)
const {
895 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||
896 FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)
899 if (!TrueBBI.IsBrAnalyzable || !FalseBBI.IsBrAnalyzable)
902 if (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
907 if (TrueBBI.BrCond.size() == 0 ||
908 FalseBBI.BrCond.size() == 0)
911 MachineBasicBlock *
TT = TrueBBI.TrueBB;
912 MachineBasicBlock *TF = TrueBBI.FalseBB;
913 MachineBasicBlock *FT = FalseBBI.TrueBB;
914 MachineBasicBlock *FF = FalseBBI.FalseBB;
929 if (!((TT == FT && TF == FF) || (TF == FT && TT == FF)))
932 bool FalseReversed =
false;
933 if (TF == FT && TT == FF) {
935 if (!FalseBBI.IsBrReversible)
937 FalseReversed =
true;
938 reverseBranchCondition(FalseBBI);
942 reverseBranchCondition(FalseBBI);
950 if(!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,
951 *TrueBBI.BB, *FalseBBI.BB,
955 TrueBBICalc.BB = TrueBBI.BB;
956 FalseBBICalc.BB = FalseBBI.BB;
957 TrueBBICalc.IsBrAnalyzable = TrueBBI.IsBrAnalyzable;
958 FalseBBICalc.IsBrAnalyzable = FalseBBI.IsBrAnalyzable;
959 if (!RescanInstructions(TIB, FIB, TIE, FIE, TrueBBICalc, FalseBBICalc))
965 TrueBBICalc.NonPredSize = TrueBBI.NonPredSize;
966 FalseBBICalc.NonPredSize = FalseBBI.NonPredSize;
972bool IfConverterImpl::ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
973 unsigned &Dups1,
unsigned &Dups2,
975 BBInfo &FalseBBICalc)
const {
977 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||
978 FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)
983 if (TrueBBI.BB == FalseBBI.BB)
986 MachineBasicBlock *
TT = TrueBBI.TrueBB;
987 MachineBasicBlock *FT = FalseBBI.TrueBB;
989 if (!TT && blockAlwaysFallThrough(TrueBBI))
991 if (!FT && blockAlwaysFallThrough(FalseBBI))
995 if (!TT && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))
997 if (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
1001 if (TrueBBI.FalseBB || FalseBBI.FalseBB)
1008 bool SkipUnconditionalBranches =
1009 TrueBBI.IsBrAnalyzable && FalseBBI.IsBrAnalyzable;
1014 if(!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,
1015 *TrueBBI.BB, *FalseBBI.BB,
1016 SkipUnconditionalBranches))
1019 TrueBBICalc.BB = TrueBBI.BB;
1020 FalseBBICalc.BB = FalseBBI.BB;
1021 TrueBBICalc.IsBrAnalyzable = TrueBBI.IsBrAnalyzable;
1022 FalseBBICalc.IsBrAnalyzable = FalseBBI.IsBrAnalyzable;
1023 if (!RescanInstructions(TIB, FIB, TIE, FIE, TrueBBICalc, FalseBBICalc))
1028 TrueBBICalc.NonPredSize = TrueBBI.NonPredSize;
1029 FalseBBICalc.NonPredSize = FalseBBI.NonPredSize;
1035void IfConverterImpl::AnalyzeBranches(BBInfo &BBI) {
1039 BBI.TrueBB = BBI.FalseBB =
nullptr;
1041 BBI.IsBrAnalyzable =
1043 if (!BBI.IsBrAnalyzable) {
1044 BBI.TrueBB =
nullptr;
1045 BBI.FalseBB =
nullptr;
1049 SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
1050 BBI.IsBrReversible = (RevCond.size() == 0) ||
1052 BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB ==
nullptr;
1054 if (BBI.BrCond.size()) {
1061 BBI.IsUnpredicable =
true;
1071void IfConverterImpl::ScanInstructions(BBInfo &BBI,
1074 bool BranchUnpredicable)
const {
1075 if (BBI.IsDone || BBI.IsUnpredicable)
1078 bool AlreadyPredicated = !BBI.Predicate.empty();
1080 BBI.NonPredSize = 0;
1083 BBI.ClobbersPred =
false;
1085 if (
MI.isDebugInstr())
1118 if (
MI.isNotDuplicable() ||
MI.isConvergent())
1119 BBI.CannotBeCopied =
true;
1122 bool isCondBr = BBI.IsBrAnalyzable &&
MI.isConditionalBranch();
1124 if (BranchUnpredicable &&
MI.isBranch()) {
1125 BBI.IsUnpredicable =
true;
1133 if (!isPredicated) {
1135 unsigned ExtraPredCost =
TII->getPredicationCost(
MI);
1136 unsigned NumCycles = SchedModel.computeInstrLatency(&
MI,
false);
1138 BBI.ExtraCost += NumCycles-1;
1139 BBI.ExtraCost2 += ExtraPredCost;
1140 }
else if (!AlreadyPredicated) {
1144 BBI.IsUnpredicable =
true;
1148 if (BBI.ClobbersPred && !isPredicated) {
1153 BBI.IsUnpredicable =
true;
1159 std::vector<MachineOperand> PredDefs;
1160 if (
TII->ClobbersPredicate(
MI, PredDefs,
true))
1161 BBI.ClobbersPred =
true;
1163 if (!
TII->isPredicable(
MI)) {
1164 BBI.IsUnpredicable =
true;
1179bool IfConverterImpl::FeasibilityAnalysis(BBInfo &BBI,
1180 SmallVectorImpl<MachineOperand> &
Pred,
1181 bool isTriangle,
bool RevBranch,
1182 bool hasCommonTail) {
1187 if (BBI.IsDone || (BBI.IsUnpredicable && !hasCommonTail))
1193 if (BBI.Predicate.size() && !BBI.IsBrAnalyzable)
1198 if (BBI.Predicate.size() && !
TII->SubsumesPredicate(
Pred, BBI.Predicate))
1201 if (!hasCommonTail && BBI.BrCond.size()) {
1206 SmallVector<MachineOperand, 4> RevPred(
Pred.begin(),
Pred.end());
1207 SmallVector<MachineOperand, 4>
Cond(BBI.BrCond.begin(), BBI.BrCond.end());
1213 !
TII->SubsumesPredicate(
Cond, RevPred))
1222void IfConverterImpl::AnalyzeBlock(
1223 MachineBasicBlock &
MBB, std::vector<std::unique_ptr<IfcvtToken>> &Tokens) {
1225 BBState(MachineBasicBlock &
MBB) :
MBB(&
MBB) {}
1226 MachineBasicBlock *
MBB;
1229 bool SuccsAnalyzed =
false;
1235 while (!BBStack.empty()) {
1236 BBState &State = BBStack.back();
1237 MachineBasicBlock *BB = State.MBB;
1238 BBInfo &BBI = BBAnalysis[BB->
getNumber()];
1240 if (!State.SuccsAnalyzed) {
1241 if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed) {
1247 BBI.IsBeingAnalyzed =
true;
1249 AnalyzeBranches(BBI);
1252 ScanInstructions(BBI, Begin,
End);
1256 if (!BBI.IsBrAnalyzable || BBI.BrCond.empty() || BBI.IsDone) {
1257 BBI.IsBeingAnalyzed =
false;
1258 BBI.IsAnalyzed =
true;
1264 if (BBI.TrueBB == BB || BBI.FalseBB == BB) {
1265 BBI.IsBeingAnalyzed =
false;
1266 BBI.IsAnalyzed =
true;
1273 BBI.IsBeingAnalyzed =
false;
1274 BBI.IsAnalyzed =
true;
1280 State.SuccsAnalyzed =
true;
1281 BBStack.push_back(*BBI.FalseBB);
1282 BBStack.push_back(*BBI.TrueBB);
1286 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
1287 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1289 if (TrueBBI.IsDone && FalseBBI.IsDone) {
1290 BBI.IsBeingAnalyzed =
false;
1291 BBI.IsAnalyzed =
true;
1296 SmallVector<MachineOperand, 4>
1297 RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
1302 bool TNeedSub = !TrueBBI.Predicate.empty();
1303 bool FNeedSub = !FalseBBI.Predicate.empty();
1304 bool Enqueued =
false;
1309 BBInfo TrueBBICalc, FalseBBICalc;
1310 auto feasibleDiamond = [&](
bool Forked) {
1311 bool MeetsSize = MeetIfcvtSizeLimit(TrueBBICalc, FalseBBICalc, *BB,
1312 Dups + Dups2, Prediction, Forked);
1313 bool TrueFeasible = FeasibilityAnalysis(TrueBBI, BBI.BrCond,
1316 bool FalseFeasible = FeasibilityAnalysis(FalseBBI, RevCond,
1319 return MeetsSize && TrueFeasible && FalseFeasible;
1322 if (ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2,
1323 TrueBBICalc, FalseBBICalc)) {
1324 if (feasibleDiamond(
false)) {
1333 Tokens.push_back(std::make_unique<IfcvtToken>(
1334 BBI, ICDiamond, TNeedSub | FNeedSub, Dups, Dups2,
1335 (
bool) TrueBBICalc.ClobbersPred, (
bool) FalseBBICalc.ClobbersPred));
1338 }
else if (ValidForkedDiamond(TrueBBI, FalseBBI, Dups, Dups2,
1339 TrueBBICalc, FalseBBICalc)) {
1340 if (feasibleDiamond(
true)) {
1351 Tokens.push_back(std::make_unique<IfcvtToken>(
1352 BBI, ICForkedDiamond, TNeedSub | FNeedSub, Dups, Dups2,
1353 (
bool) TrueBBICalc.ClobbersPred, (
bool) FalseBBICalc.ClobbersPred));
1359 if (ValidTriangle(TrueBBI, FalseBBI,
false, Dups, Prediction) &&
1360 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
1361 TrueBBI.ExtraCost2, Prediction) &&
1362 FeasibilityAnalysis(TrueBBI, BBI.BrCond,
true)) {
1371 std::make_unique<IfcvtToken>(BBI, ICTriangle, TNeedSub, Dups));
1375 if (ValidTriangle(TrueBBI, FalseBBI,
true, Dups, Prediction) &&
1376 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
1377 TrueBBI.ExtraCost2, Prediction) &&
1378 FeasibilityAnalysis(TrueBBI, BBI.BrCond,
true,
true)) {
1380 std::make_unique<IfcvtToken>(BBI, ICTriangleRev, TNeedSub, Dups));
1384 if (ValidSimple(TrueBBI, Dups, Prediction) &&
1385 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
1386 TrueBBI.ExtraCost2, Prediction) &&
1387 FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {
1396 std::make_unique<IfcvtToken>(BBI, ICSimple, TNeedSub, Dups));
1402 if (ValidTriangle(FalseBBI, TrueBBI,
false, Dups,
1404 MeetIfcvtSizeLimit(*FalseBBI.BB,
1405 FalseBBI.NonPredSize + FalseBBI.ExtraCost,
1406 FalseBBI.ExtraCost2, Prediction.
getCompl()) &&
1407 FeasibilityAnalysis(FalseBBI, RevCond,
true)) {
1408 Tokens.push_back(std::make_unique<IfcvtToken>(BBI, ICTriangleFalse,
1413 if (ValidTriangle(FalseBBI, TrueBBI,
true, Dups,
1415 MeetIfcvtSizeLimit(*FalseBBI.BB,
1416 FalseBBI.NonPredSize + FalseBBI.ExtraCost,
1417 FalseBBI.ExtraCost2, Prediction.
getCompl()) &&
1418 FeasibilityAnalysis(FalseBBI, RevCond,
true,
true)) {
1420 std::make_unique<IfcvtToken>(BBI, ICTriangleFRev, FNeedSub, Dups));
1424 if (ValidSimple(FalseBBI, Dups, Prediction.
getCompl()) &&
1425 MeetIfcvtSizeLimit(*FalseBBI.BB,
1426 FalseBBI.NonPredSize + FalseBBI.ExtraCost,
1427 FalseBBI.ExtraCost2, Prediction.
getCompl()) &&
1428 FeasibilityAnalysis(FalseBBI, RevCond)) {
1430 std::make_unique<IfcvtToken>(BBI, ICSimpleFalse, FNeedSub, Dups));
1435 BBI.IsEnqueued = Enqueued;
1436 BBI.IsBeingAnalyzed =
false;
1437 BBI.IsAnalyzed =
true;
1443void IfConverterImpl::AnalyzeBlocks(
1444 MachineFunction &MF, std::vector<std::unique_ptr<IfcvtToken>> &Tokens) {
1445 for (MachineBasicBlock &
MBB : MF)
1446 AnalyzeBlock(
MBB, Tokens);
1462 if (
I ==
E || !
I->empty() || !PI->isSuccessor(&*
I))
1467 return PI->isSuccessor(&*
I);
1472void IfConverterImpl::InvalidatePreds(MachineBasicBlock &
MBB) {
1474 BBInfo &PBBI = BBAnalysis[Predecessor->getNumber()];
1475 if (PBBI.IsDone || PBBI.BB == &
MBB)
1477 PBBI.IsAnalyzed =
false;
1478 PBBI.IsEnqueued =
false;
1487 TII->insertBranch(
MBB, &ToMBB,
nullptr, NoCond, dl);
1500 for (
unsigned Reg : Redefs)
1507 for (
auto Clobber : Clobbers) {
1510 unsigned Reg = Clobber.first;
1514 if (
Op.isRegMask()) {
1529 [&](
MCPhysReg S) { return LiveBeforeMI.count(S); }))
1535bool IfConverterImpl::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {
1536 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
1537 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1538 BBInfo *CvtBBI = &TrueBBI;
1539 BBInfo *NextBBI = &FalseBBI;
1541 SmallVector<MachineOperand, 4>
Cond(BBI.BrCond.begin(), BBI.BrCond.end());
1542 if (Kind == ICSimpleFalse)
1545 MachineBasicBlock &CvtMBB = *CvtBBI->BB;
1546 MachineBasicBlock &NextMBB = *NextBBI->BB;
1547 if (CvtBBI->IsDone ||
1548 (CvtBBI->CannotBeCopied && CvtMBB.
pred_size() > 1)) {
1550 BBI.IsAnalyzed =
false;
1551 CvtBBI->IsAnalyzed =
false;
1559 if (Kind == ICSimpleFalse)
1579 CopyAndPredicateBlock(BBI, *CvtBBI,
Cond);
1582 BBI.BB->removeSuccessor(&CvtMBB,
true);
1585 PredicateBlock(*CvtBBI, CvtMBB.
end(),
Cond);
1589 MergeBlocks(BBI, *CvtBBI);
1592 bool IterIfcvt =
true;
1595 BBI.HasFallThrough =
false;
1612 InvalidatePreds(*BBI.BB);
1613 CvtBBI->IsDone =
true;
1620bool IfConverterImpl::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
1621 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
1622 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1623 BBInfo *CvtBBI = &TrueBBI;
1624 BBInfo *NextBBI = &FalseBBI;
1627 SmallVector<MachineOperand, 4>
Cond(BBI.BrCond.begin(), BBI.BrCond.end());
1628 if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
1631 MachineBasicBlock &CvtMBB = *CvtBBI->BB;
1632 MachineBasicBlock &NextMBB = *NextBBI->BB;
1633 if (CvtBBI->IsDone ||
1634 (CvtBBI->CannotBeCopied && CvtMBB.
pred_size() > 1)) {
1636 BBI.IsAnalyzed =
false;
1637 CvtBBI->IsAnalyzed =
false;
1645 if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
1649 if (Kind == ICTriangleRev || Kind == ICTriangleFRev) {
1650 if (reverseBranchCondition(*CvtBBI)) {
1656 BBInfo &PBBI = BBAnalysis[PBB->getNumber()];
1657 if (PBBI.IsEnqueued) {
1658 PBBI.IsAnalyzed =
false;
1659 PBBI.IsEnqueued =
false;
1673 bool HasEarlyExit = CvtBBI->FalseBB !=
nullptr;
1674 BranchProbability CvtNext, CvtFalse, BBNext, BBCvt;
1691 CopyAndPredicateBlock(BBI, *CvtBBI,
Cond,
true);
1695 PredicateBlock(*CvtBBI, CvtMBB.
end(),
Cond);
1698 MergeBlocks(BBI, *CvtBBI,
false);
1702 BBI.BB->removeSuccessor(&CvtMBB,
true);
1706 SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(),
1707 CvtBBI->BrCond.end());
1718 auto NewNext = BBNext + BBCvt * CvtNext;
1719 auto NewTrueBBIter =
find(BBI.BB->successors(), NewTrueBB);
1720 if (NewTrueBBIter != BBI.BB->succ_end())
1721 BBI.BB->setSuccProbability(NewTrueBBIter, NewNext);
1723 auto NewFalse = BBCvt * CvtFalse;
1725 BBI.BB->addSuccessor(CvtBBI->FalseBB, NewFalse);
1730 bool FalseBBDead =
false;
1731 bool IterIfcvt =
true;
1733 if (!isFallThrough) {
1737 if (!HasEarlyExit && NextMBB.
pred_size() == 1 &&
1739 MergeBlocks(BBI, *NextBBI);
1743 BBI.HasFallThrough =
false;
1753 InvalidatePreds(*BBI.BB);
1754 CvtBBI->IsDone =
true;
1756 NextBBI->IsDone =
true;
1773bool IfConverterImpl::IfConvertDiamondCommon(
1774 BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,
unsigned NumDups1,
1775 unsigned NumDups2,
bool TClobbersPred,
bool FClobbersPred,
1776 bool RemoveBranch,
bool MergeAddEdges) {
1778 if (TrueBBI.IsDone || FalseBBI.IsDone ||
1779 TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1) {
1781 BBI.IsAnalyzed =
false;
1782 TrueBBI.IsAnalyzed =
false;
1783 FalseBBI.IsAnalyzed =
false;
1787 if (TrueBBI.BB->hasAddressTaken() || FalseBBI.BB->hasAddressTaken())
1794 BBInfo *BBI1 = &TrueBBI;
1795 BBInfo *BBI2 = &FalseBBI;
1796 SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
1799 SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond;
1800 SmallVector<MachineOperand, 4> *Cond2 = &RevCond;
1803 bool DoSwap =
false;
1804 if (TClobbersPred && !FClobbersPred)
1806 else if (!TClobbersPred && !FClobbersPred) {
1807 if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)
1809 }
else if (TClobbersPred && FClobbersPred)
1819 MachineBasicBlock &MBB1 = *BBI1->BB;
1820 MachineBasicBlock &MBB2 = *BBI2->BB;
1838 BBI1->NonPredSize -= NumDups1;
1839 BBI2->NonPredSize -= NumDups1;
1844 for (
unsigned i = 0; i < NumDups1; ++DI1) {
1845 if (DI1 == MBB1.
end())
1847 if (!DI1->isDebugInstr())
1850 while (NumDups1 != 0) {
1853 if (DI2->shouldUpdateAdditionalCallInfo())
1857 if (DI2 == MBB2.
end())
1859 if (!DI2->isDebugInstr())
1870 BBI.BB->splice(BBI.BB->end(), &MBB1, MBB1.
begin(), DI1);
1881 if (!BBI1->IsBrAnalyzable)
1887 while (DI1 != MBB1.
begin()) {
1889 if (!Prev->isBranch() && !Prev->isDebugInstr())
1893 for (
unsigned i = 0; i != NumDups2; ) {
1902 if (DI1->shouldUpdateAdditionalCallInfo())
1906 if (!DI1->isDebugInstr())
1911 DI2 = BBI2->BB->end();
1919 while (DI2 != MBB2.
begin()) {
1921 if (!Prev->isBranch() && !Prev->isDebugInstr())
1926 while (NumDups2 != 0) {
1932 if (!DI2->isDebugInstr())
1944 SmallSet<MCRegister, 4> RedefsByFalse;
1945 SmallSet<MCRegister, 4> ExtUses;
1946 if (
TII->isProfitableToUnpredicate(MBB1, MBB2)) {
1948 if (FI.isDebugInstr())
1951 for (
const MachineOperand &MO : FI.operands()) {
1959 }
else if (!RedefsByFalse.
count(
Reg)) {
1966 for (MCRegister
Reg : Defs) {
1974 PredicateBlock(*BBI1, MBB1.
end(), *Cond1, &RedefsByFalse);
1983 if (!MBB2.
empty() && (DI2 == MBB2.
end())) {
1986 bool BB1Predicated = BBI1T != MBB1.
end() &&
TII->isPredicated(*BBI1T);
1987 bool BB2NonPredicated = BBI2T != MBB2.
end() && !
TII->isPredicated(*BBI2T);
1988 if (BB2NonPredicated && (BB1Predicated || !BBI2->IsBrAnalyzable))
1993 PredicateBlock(*BBI2, DI2, *Cond2);
1996 MergeBlocks(BBI, *BBI1, MergeAddEdges);
1997 MergeBlocks(BBI, *BBI2, MergeAddEdges);
2003bool IfConverterImpl::IfConvertForkedDiamond(BBInfo &BBI, IfcvtKind Kind,
2007 bool FClobbersPred) {
2008 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
2009 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
2014 if (TIE != TrueBBI.BB->end())
2015 dl = TIE->getDebugLoc();
2019 if (!IfConvertDiamondCommon(
2020 BBI, TrueBBI, FalseBBI,
2022 TClobbersPred, FClobbersPred,
2029 TrueBBI.BrCond, dl);
2032 BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone =
true;
2033 InvalidatePreds(*BBI.BB);
2040bool IfConverterImpl::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
2041 unsigned NumDups1,
unsigned NumDups2,
2042 bool TClobbersPred,
bool FClobbersPred) {
2043 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
2044 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
2045 MachineBasicBlock *TailBB = TrueBBI.TrueBB;
2049 if (blockAlwaysFallThrough(TrueBBI))
2050 TailBB = FalseBBI.TrueBB;
2051 assert((TailBB || !TrueBBI.IsBrAnalyzable) &&
"Unexpected!");
2054 if (!IfConvertDiamondCommon(
2055 BBI, TrueBBI, FalseBBI,
2057 TClobbersPred, FClobbersPred,
2058 TrueBBI.IsBrAnalyzable,
2069 BBI.BB->removeSuccessor(TrueBBI.BB);
2070 BBI.BB->removeSuccessor(FalseBBI.BB,
true);
2072 BBInfo &TailBBI = BBAnalysis[TailBB->
getNumber()];
2074 blockNeverFallThrough(TailBBI) && !TailBBI.BB->hasAddressTaken();
2079 if (TI != BBI.BB->end() &&
TII->isPredicated(*TI))
2080 CanMergeTail =
false;
2083 unsigned NumPreds = TailBB->
pred_size();
2085 CanMergeTail =
false;
2086 else if (NumPreds == 1 && CanMergeTail) {
2088 if (*PI != TrueBBI.BB && *PI != FalseBBI.BB)
2089 CanMergeTail =
false;
2092 MergeBlocks(BBI, TailBBI);
2093 TailBBI.IsDone =
true;
2097 BBI.HasFallThrough =
false;
2102 BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone =
true;
2103 InvalidatePreds(*BBI.BB);
2111 bool SawStore =
true;
2112 if (!
MI.isSafeToMove(SawStore))
2121 if (MO.isDef() && !LaterRedefs.
count(
Reg))
2131 SmallVectorImpl<MachineOperand> &
Cond,
2132 SmallSet<MCRegister, 4> *LaterRedefs) {
2133 bool AnyUnpred =
false;
2134 bool MaySpec = LaterRedefs !=
nullptr;
2135 for (MachineInstr &
I :
make_range(BBI.BB->begin(),
E)) {
2136 if (
I.isDebugInstr() ||
TII->isPredicated(
I))
2148 if (!
TII->PredicateInstruction(
I,
Cond)) {
2150 dbgs() <<
"Unable to predicate " <<
I <<
"!\n";
2162 BBI.IsAnalyzed =
false;
2163 BBI.NonPredSize = 0;
2172void IfConverterImpl::CopyAndPredicateBlock(
2173 BBInfo &ToBBI, BBInfo &FromBBI, SmallVectorImpl<MachineOperand> &
Cond,
2177 MachineBasicBlock &FromMBB = *FromBBI.BB;
2178 for (MachineInstr &
I : FromMBB) {
2180 if (IgnoreBr &&
I.isBranch())
2183 MachineInstr *
MI = MF.CloneMachineInstr(&
I);
2185 if (
I.isCandidateForAdditionalCallInfo())
2188 ToBBI.BB->insert(ToBBI.BB->end(),
MI);
2189 ToBBI.NonPredSize++;
2190 unsigned ExtraPredCost =
TII->getPredicationCost(
I);
2191 unsigned NumCycles = SchedModel.computeInstrLatency(&
I,
false);
2193 ToBBI.ExtraCost += NumCycles-1;
2194 ToBBI.ExtraCost2 += ExtraPredCost;
2196 if (!
TII->isPredicated(
I) && !
MI->isDebugInstr()) {
2197 if (!
TII->PredicateInstruction(*
MI,
Cond)) {
2199 dbgs() <<
"Unable to predicate " <<
I <<
"!\n";
2211 std::vector<MachineBasicBlock *> Succs(FromMBB.succ_begin(),
2212 FromMBB.succ_end());
2214 MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB :
nullptr;
2216 for (MachineBasicBlock *Succ : Succs) {
2218 if (Succ == FallThrough)
2220 ToBBI.BB->addSuccessor(Succ);
2224 ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
2227 ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
2228 ToBBI.IsAnalyzed =
false;
2238void IfConverterImpl::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI,
2240 MachineBasicBlock &FromMBB = *FromBBI.BB;
2242 "Removing a BB whose address is taken!");
2247 for (MachineInstr &
MI : FromMBB)
2248 if (
MI.getOpcode() == TargetOpcode::INLINEASM_BR)
2249 for (MachineOperand &MO :
MI.operands())
2250 if (MO.isMBB() && !ToBBI.BB->isSuccessor(MO.getMBB()))
2257 ToBBI.BB->splice(ToTI, &FromMBB, FromMBB.begin(), FromTI);
2260 if (FromTI != FromMBB.end() && !
TII->isPredicated(*FromTI))
2261 ToTI = ToBBI.BB->end();
2262 ToBBI.BB->splice(ToTI, &FromMBB, FromTI, FromMBB.end());
2268 if (ToBBI.IsBrAnalyzable)
2269 ToBBI.BB->normalizeSuccProbs();
2271 SmallVector<MachineBasicBlock *, 4> FromSuccs(FromMBB.successors());
2273 MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB :
nullptr;
2277 if (AddEdges && ToBBI.BB->isSuccessor(&FromMBB)) {
2281 ToBBI.BB->removeSuccessor(&FromMBB);
2284 for (MachineBasicBlock *Succ : FromSuccs) {
2286 if (Succ == FallThrough) {
2287 FromMBB.removeSuccessor(Succ);
2304 if (!To2FromProb.isZero())
2305 NewProb *= To2FromProb;
2308 FromMBB.removeSuccessor(Succ);
2333 if (ToBBI.BB->isSuccessor(Succ))
2334 ToBBI.BB->setSuccProbability(
2335 find(ToBBI.BB->successors(), Succ),
2338 ToBBI.BB->addSuccessor(Succ, NewProb);
2344 MachineBasicBlock *
Last = &*FromMBB.getParent()->rbegin();
2345 if (
Last != &FromMBB)
2346 FromMBB.moveAfter(
Last);
2350 if (ToBBI.IsBrAnalyzable && FromBBI.IsBrAnalyzable)
2351 ToBBI.BB->normalizeSuccProbs();
2353 ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
2354 FromBBI.Predicate.clear();
2356 ToBBI.NonPredSize += FromBBI.NonPredSize;
2357 ToBBI.ExtraCost += FromBBI.ExtraCost;
2358 ToBBI.ExtraCost2 += FromBBI.ExtraCost2;
2359 FromBBI.NonPredSize = 0;
2360 FromBBI.ExtraCost = 0;
2361 FromBBI.ExtraCost2 = 0;
2363 ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
2364 ToBBI.HasFallThrough = FromBBI.HasFallThrough;
2365 ToBBI.IsAnalyzed =
false;
2366 FromBBI.IsAnalyzed =
false;
2371 return new IfConverterLegacy(std::move(Ftor));
2377 IfConverterImpl Impl;
2378 return Impl.runOnMachineFunction(
2381 return getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
2384 return &getAnalysis<MachineBranchProbabilityInfoWrapperPass>()
2387 [&]() {
return &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); },
2389 return PredicateFtor && !PredicateFtor(MF);
2395 IfConverterImpl Impl;
2396 bool Changed = Impl.runOnMachineFunction(
2405 .getCachedResult<ProfileSummaryAnalysis>(
2412 return PredicateFtor && !PredicateFtor(MF);
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
const AArch64InstrInfo & TII
Function Alias Analysis false
static MachineBasicBlock * findFalseBlock(MachineBasicBlock *BB, MachineBasicBlock *TrueBB)
findFalseBlock - BB has a fallthrough.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static MachineBasicBlock * findFalseBlock(MachineBasicBlock *BB, MachineBasicBlock *TrueBB)
BB has a fallthrough. Find its 'false' successor given its 'true' successor.
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 MachineBasicBlock * getNextBlock(MachineBasicBlock &MBB)
Returns the next block in the function blocks ordering.
static bool MaySpeculate(const MachineInstr &MI, SmallSet< MCRegister, 4 > &LaterRedefs)
static void UpdatePredRedefs(MachineInstr &MI, LivePhysRegs &Redefs)
Behaves like LivePhysRegs::stepForward() but also adds implicit uses to all values defined in MI whic...
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...
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
Register const TargetRegisterInfo * TRI
Promote Memory to Register
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
SmallVector< MachineOperand, 4 > Cond
MachineRegisterInfo & MRI
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
This file defines the scope_exit class, which executes user-defined cleanup logic at scope exit.
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.
bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const override
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify=false) const override
unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
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 constexpr BranchProbability getOne()
static constexpr BranchProbability getZero()
BranchProbability getCompl() const
FunctionPass class - This class is used to implement most global optimizations.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Module * getParent()
Get the module that this global value is contained inside of...
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
A set of physical registers with utility functions to track liveness when walking backward/forward th...
LLVM_ABI 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.
LLVM_ABI void addLiveInsNoPristines(const MachineBasicBlock &MBB)
Adds all live-in registers of basic block MBB but skips pristine registers.
unsigned pred_size() const
MachineInstrBundleIterator< const MachineInstr > const_iterator
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
LLVM_ABI iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the first non-debug instruction in the basic block, or end().
LLVM_ABI iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
bool hasAddressTaken() const
Test whether this block is used as something other than the target of a terminator,...
SmallVectorImpl< MachineBasicBlock * >::iterator pred_iterator
pred_iterator pred_begin()
MachineInstrBundleIterator< MachineInstr, true > reverse_iterator
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
LLVM_ABI instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
iterator_range< iterator > terminators()
iterator_range< succ_iterator > successors()
reverse_iterator rbegin()
iterator_range< pred_iterator > predecessors()
MachineInstrBundleIterator< MachineInstr > iterator
LLVM_ABI bool mayHaveInlineAsmBr() const
Returns true if this block may have an INLINEASM_BR (overestimate, by checking if any of the successo...
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
LLVM_ABI 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.
Function & getFunction()
Return the LLVM function that this machine code represents.
BasicBlockListType::iterator iterator
void eraseAdditionalCallInfo(const MachineInstr *MI)
Following functions update call site info.
void copyAdditionalCallInfo(const MachineInstr *Old, const MachineInstr *New)
Copy the call site info from Old to \ New.
const MachineInstrBuilder & addReg(Register RegNo, RegState Flags={}, 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.
LLVM_ABI 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.
bool tracksLiveness() const
tracksLiveness - Returns true when tracking register liveness accurately.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
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.
void insert_range(Range &&R)
bool contains(const T &V) const
Check if the SmallSet contains the given element.
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.
std::pair< iterator, bool > insert(const ValueT &Val)
insert - Attempts to insert a new element.
size_type count(const KeyT &Key) const
count - Returns 1 if this set contains an element identified by Key, 0 otherwise.
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.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
LLVM_ABI void init(const TargetSubtargetInfo *TSInfo, bool EnableSModel=true, bool EnableSItins=true)
Initialize the machine model for instruction scheduling.
TargetSubtargetInfo - Generic base class for all target subtargets.
An efficient, type-erasing, non-owning reference to a callable.
self_iterator getIterator()
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
Pass manager infrastructure for declaring and invalidating analyses.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool isPredicated(const MCInst &MI, const MCInstrInfo *MCII)
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.
OuterAnalysisManagerProxy< ModuleAnalysisManager, MachineFunction > ModuleAnalysisManagerMachineFunctionProxy
Provide the ModuleAnalysisManager to Function proxy.
@ Implicit
Not emitted register (e.g. carry, or temporary result).
@ Define
Register definition.
LLVM_ABI FunctionPass * createIfConverterLegacyPass(std::function< bool(const MachineFunction &)> Ftor)
scope_exit(Callable) -> scope_exit< Callable >
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=true)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI void recomputeLivenessFlags(MachineBasicBlock &MBB)
Recomputes dead and kill flags in MBB.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
DWARFExpression::Operation Op
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI char & IfConverterID
IfConverter - This pass performs machine code if conversion.
@ End
Run the machine verifier once, at the end of the pipeline.
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
LLVM_ABI void reportFatalUsageError(Error Err)
Report a fatal error that does not indicate a bug in LLVM.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.