LCOV - code coverage report
Current view: top level - lib/CodeGen - IfConversion.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 884 916 96.5 %
Date: 2017-09-14 15:23:50 Functions: 40 41 97.6 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===-- IfConversion.cpp - Machine code if conversion pass. ---------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file implements the machine instruction level if-conversion pass, which
      11             : // tries to convert conditional branches into predicated instructions.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #include "BranchFolding.h"
      16             : #include "llvm/ADT/STLExtras.h"
      17             : #include "llvm/ADT/ScopeExit.h"
      18             : #include "llvm/ADT/SmallSet.h"
      19             : #include "llvm/ADT/Statistic.h"
      20             : #include "llvm/CodeGen/LivePhysRegs.h"
      21             : #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
      22             : #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
      23             : #include "llvm/CodeGen/MachineFunctionPass.h"
      24             : #include "llvm/CodeGen/MachineInstrBuilder.h"
      25             : #include "llvm/CodeGen/MachineModuleInfo.h"
      26             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      27             : #include "llvm/CodeGen/Passes.h"
      28             : #include "llvm/CodeGen/TargetSchedule.h"
      29             : #include "llvm/Support/CommandLine.h"
      30             : #include "llvm/Support/Debug.h"
      31             : #include "llvm/Support/ErrorHandling.h"
      32             : #include "llvm/Support/raw_ostream.h"
      33             : #include "llvm/Target/TargetInstrInfo.h"
      34             : #include "llvm/Target/TargetLowering.h"
      35             : #include "llvm/Target/TargetRegisterInfo.h"
      36             : #include "llvm/Target/TargetSubtargetInfo.h"
      37             : #include <algorithm>
      38             : #include <utility>
      39             : 
      40             : using namespace llvm;
      41             : 
      42             : #define DEBUG_TYPE "if-converter"
      43             : 
      44             : // Hidden options for help debugging.
      45      144612 : static cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden);
      46      144612 : static cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden);
      47      144612 : static cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden);
      48       72306 : static cl::opt<bool> DisableSimple("disable-ifcvt-simple",
      49      144612 :                                    cl::init(false), cl::Hidden);
      50       72306 : static cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false",
      51      144612 :                                     cl::init(false), cl::Hidden);
      52       72306 : static cl::opt<bool> DisableTriangle("disable-ifcvt-triangle",
      53      144612 :                                      cl::init(false), cl::Hidden);
      54       72306 : static cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev",
      55      144612 :                                       cl::init(false), cl::Hidden);
      56       72306 : static cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false",
      57      144612 :                                       cl::init(false), cl::Hidden);
      58       72306 : static cl::opt<bool> DisableTriangleFR("disable-ifcvt-triangle-false-rev",
      59      144612 :                                        cl::init(false), cl::Hidden);
      60       72306 : static cl::opt<bool> DisableDiamond("disable-ifcvt-diamond",
      61      144612 :                                     cl::init(false), cl::Hidden);
      62       72306 : static cl::opt<bool> DisableForkedDiamond("disable-ifcvt-forked-diamond",
      63      144612 :                                         cl::init(false), cl::Hidden);
      64       72306 : static cl::opt<bool> IfCvtBranchFold("ifcvt-branch-fold",
      65      144612 :                                      cl::init(true), cl::Hidden);
      66             : 
      67             : STATISTIC(NumSimple,       "Number of simple if-conversions performed");
      68             : STATISTIC(NumSimpleFalse,  "Number of simple (F) if-conversions performed");
      69             : STATISTIC(NumTriangle,     "Number of triangle if-conversions performed");
      70             : STATISTIC(NumTriangleRev,  "Number of triangle (R) if-conversions performed");
      71             : STATISTIC(NumTriangleFalse,"Number of triangle (F) if-conversions performed");
      72             : STATISTIC(NumTriangleFRev, "Number of triangle (F/R) if-conversions performed");
      73             : STATISTIC(NumDiamonds,     "Number of diamond if-conversions performed");
      74             : STATISTIC(NumForkedDiamonds, "Number of forked-diamond if-conversions performed");
      75             : STATISTIC(NumIfConvBBs,    "Number of if-converted blocks");
      76             : STATISTIC(NumDupBBs,       "Number of duplicated blocks");
      77             : STATISTIC(NumUnpred,       "Number of true blocks of diamonds unpredicated");
      78             : 
      79             : namespace {
      80       29538 :   class IfConverter : public MachineFunctionPass {
      81             :     enum IfcvtKind {
      82             :       ICNotClassfied,  // BB data valid, but not classified.
      83             :       ICSimpleFalse,   // Same as ICSimple, but on the false path.
      84             :       ICSimple,        // BB is entry of an one split, no rejoin sub-CFG.
      85             :       ICTriangleFRev,  // Same as ICTriangleFalse, but false path rev condition.
      86             :       ICTriangleRev,   // Same as ICTriangle, but true path rev condition.
      87             :       ICTriangleFalse, // Same as ICTriangle, but on the false path.
      88             :       ICTriangle,      // BB is entry of a triangle sub-CFG.
      89             :       ICDiamond,       // BB is entry of a diamond sub-CFG.
      90             :       ICForkedDiamond  // BB is entry of an almost diamond sub-CFG, with a
      91             :                        // common tail that can be shared.
      92             :     };
      93             : 
      94             :     /// One per MachineBasicBlock, this is used to cache the result
      95             :     /// if-conversion feasibility analysis. This includes results from
      96             :     /// TargetInstrInfo::analyzeBranch() (i.e. TBB, FBB, and Cond), and its
      97             :     /// classification, and common tail block of its successors (if it's a
      98             :     /// diamond shape), its size, whether it's predicable, and whether any
      99             :     /// instruction can clobber the 'would-be' predicate.
     100             :     ///
     101             :     /// IsDone          - True if BB is not to be considered for ifcvt.
     102             :     /// IsBeingAnalyzed - True if BB is currently being analyzed.
     103             :     /// IsAnalyzed      - True if BB has been analyzed (info is still valid).
     104             :     /// IsEnqueued      - True if BB has been enqueued to be ifcvt'ed.
     105             :     /// IsBrAnalyzable  - True if analyzeBranch() returns false.
     106             :     /// HasFallThrough  - True if BB may fallthrough to the following BB.
     107             :     /// IsUnpredicable  - True if BB is known to be unpredicable.
     108             :     /// ClobbersPred    - True if BB could modify predicates (e.g. has
     109             :     ///                   cmp, call, etc.)
     110             :     /// NonPredSize     - Number of non-predicated instructions.
     111             :     /// ExtraCost       - Extra cost for multi-cycle instructions.
     112             :     /// ExtraCost2      - Some instructions are slower when predicated
     113             :     /// BB              - Corresponding MachineBasicBlock.
     114             :     /// TrueBB / FalseBB- See analyzeBranch().
     115             :     /// BrCond          - Conditions for end of block conditional branches.
     116             :     /// Predicate       - Predicate used in the BB.
     117      143019 :     struct BBInfo {
     118             :       bool IsDone          : 1;
     119             :       bool IsBeingAnalyzed : 1;
     120             :       bool IsAnalyzed      : 1;
     121             :       bool IsEnqueued      : 1;
     122             :       bool IsBrAnalyzable  : 1;
     123             :       bool IsBrReversible  : 1;
     124             :       bool HasFallThrough  : 1;
     125             :       bool IsUnpredicable  : 1;
     126             :       bool CannotBeCopied  : 1;
     127             :       bool ClobbersPred    : 1;
     128             :       unsigned NonPredSize;
     129             :       unsigned ExtraCost;
     130             :       unsigned ExtraCost2;
     131             :       MachineBasicBlock *BB;
     132             :       MachineBasicBlock *TrueBB;
     133             :       MachineBasicBlock *FalseBB;
     134             :       SmallVector<MachineOperand, 4> BrCond;
     135             :       SmallVector<MachineOperand, 4> Predicate;
     136       47673 :       BBInfo() : IsDone(false), IsBeingAnalyzed(false),
     137             :                  IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false),
     138             :                  IsBrReversible(false), HasFallThrough(false),
     139             :                  IsUnpredicable(false), CannotBeCopied(false),
     140             :                  ClobbersPred(false), NonPredSize(0), ExtraCost(0),
     141             :                  ExtraCost2(0), BB(nullptr), TrueBB(nullptr),
     142      143019 :                  FalseBB(nullptr) {}
     143             :     };
     144             : 
     145             :     /// Record information about pending if-conversions to attempt:
     146             :     /// BBI             - Corresponding BBInfo.
     147             :     /// Kind            - Type of block. See IfcvtKind.
     148             :     /// NeedSubsumption - True if the to-be-predicated BB has already been
     149             :     ///                   predicated.
     150             :     /// NumDups      - Number of instructions that would be duplicated due
     151             :     ///                   to this if-conversion. (For diamonds, the number of
     152             :     ///                   identical instructions at the beginnings of both
     153             :     ///                   paths).
     154             :     /// NumDups2     - For diamonds, the number of identical instructions
     155             :     ///                   at the ends of both paths.
     156             :     struct IfcvtToken {
     157             :       BBInfo &BBI;
     158             :       IfcvtKind Kind;
     159             :       unsigned NumDups;
     160             :       unsigned NumDups2;
     161             :       bool NeedSubsumption : 1;
     162             :       bool TClobbersPred : 1;
     163             :       bool FClobbersPred : 1;
     164             :       IfcvtToken(BBInfo &b, IfcvtKind k, bool s, unsigned d, unsigned d2 = 0,
     165             :                  bool tc = false, bool fc = false)
     166        1876 :         : BBI(b), Kind(k), NumDups(d), NumDups2(d2), NeedSubsumption(s),
     167        1876 :           TClobbersPred(tc), FClobbersPred(fc) {}
     168             :     };
     169             : 
     170             :     /// Results of if-conversion feasibility analysis indexed by basic block
     171             :     /// number.
     172             :     std::vector<BBInfo> BBAnalysis;
     173             :     TargetSchedModel SchedModel;
     174             : 
     175             :     const TargetLoweringBase *TLI;
     176             :     const TargetInstrInfo *TII;
     177             :     const TargetRegisterInfo *TRI;
     178             :     const MachineBranchProbabilityInfo *MBPI;
     179             :     MachineRegisterInfo *MRI;
     180             : 
     181             :     LivePhysRegs Redefs;
     182             :     LivePhysRegs DontKill;
     183             : 
     184             :     bool PreRegAlloc;
     185             :     bool MadeChange;
     186             :     int FnNum;
     187             :     std::function<bool(const MachineFunction &)> PredicateFtor;
     188             : 
     189             :   public:
     190             :     static char ID;
     191        4969 :     IfConverter(std::function<bool(const MachineFunction &)> Ftor = nullptr)
     192       24845 :         : MachineFunctionPass(ID), FnNum(-1), PredicateFtor(std::move(Ftor)) {
     193        4969 :       initializeIfConverterPass(*PassRegistry::getPassRegistry());
     194        4969 :     }
     195             : 
     196        4951 :     void getAnalysisUsage(AnalysisUsage &AU) const override {
     197        4951 :       AU.addRequired<MachineBlockFrequencyInfo>();
     198        4951 :       AU.addRequired<MachineBranchProbabilityInfo>();
     199        4951 :       MachineFunctionPass::getAnalysisUsage(AU);
     200        4951 :     }
     201             : 
     202             :     bool runOnMachineFunction(MachineFunction &MF) override;
     203             : 
     204        4953 :     MachineFunctionProperties getRequiredProperties() const override {
     205       14859 :       return MachineFunctionProperties().set(
     206       14859 :           MachineFunctionProperties::Property::NoVRegs);
     207             :     }
     208             : 
     209             :   private:
     210             :     bool reverseBranchCondition(BBInfo &BBI) const;
     211             :     bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups,
     212             :                      BranchProbability Prediction) const;
     213             :     bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
     214             :                        bool FalseBranch, unsigned &Dups,
     215             :                        BranchProbability Prediction) const;
     216             :     bool CountDuplicatedInstructions(
     217             :         MachineBasicBlock::iterator &TIB, MachineBasicBlock::iterator &FIB,
     218             :         MachineBasicBlock::iterator &TIE, MachineBasicBlock::iterator &FIE,
     219             :         unsigned &Dups1, unsigned &Dups2,
     220             :         MachineBasicBlock &TBB, MachineBasicBlock &FBB,
     221             :         bool SkipUnconditionalBranches) const;
     222             :     bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
     223             :                       unsigned &Dups1, unsigned &Dups2,
     224             :                       BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const;
     225             :     bool ValidForkedDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
     226             :                             unsigned &Dups1, unsigned &Dups2,
     227             :                             BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const;
     228             :     void AnalyzeBranches(BBInfo &BBI);
     229             :     void ScanInstructions(BBInfo &BBI,
     230             :                           MachineBasicBlock::iterator &Begin,
     231             :                           MachineBasicBlock::iterator &End,
     232             :                           bool BranchUnpredicable = false) const;
     233             :     bool RescanInstructions(
     234             :         MachineBasicBlock::iterator &TIB, MachineBasicBlock::iterator &FIB,
     235             :         MachineBasicBlock::iterator &TIE, MachineBasicBlock::iterator &FIE,
     236             :         BBInfo &TrueBBI, BBInfo &FalseBBI) const;
     237             :     void AnalyzeBlock(MachineBasicBlock &MBB,
     238             :                       std::vector<std::unique_ptr<IfcvtToken>> &Tokens);
     239             :     bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Cond,
     240             :                              bool isTriangle = false, bool RevBranch = false,
     241             :                              bool hasCommonTail = false);
     242             :     void AnalyzeBlocks(MachineFunction &MF,
     243             :                        std::vector<std::unique_ptr<IfcvtToken>> &Tokens);
     244             :     void InvalidatePreds(MachineBasicBlock &MBB);
     245             :     bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind);
     246             :     bool IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind);
     247             :     bool IfConvertDiamondCommon(BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,
     248             :                                 unsigned NumDups1, unsigned NumDups2,
     249             :                                 bool TClobbersPred, bool FClobbersPred,
     250             :                                 bool RemoveBranch, bool MergeAddEdges);
     251             :     bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
     252             :                           unsigned NumDups1, unsigned NumDups2,
     253             :                           bool TClobbers, bool FClobbers);
     254             :     bool IfConvertForkedDiamond(BBInfo &BBI, IfcvtKind Kind,
     255             :                               unsigned NumDups1, unsigned NumDups2,
     256             :                               bool TClobbers, bool FClobbers);
     257             :     void PredicateBlock(BBInfo &BBI,
     258             :                         MachineBasicBlock::iterator E,
     259             :                         SmallVectorImpl<MachineOperand> &Cond,
     260             :                         SmallSet<unsigned, 4> *LaterRedefs = nullptr);
     261             :     void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
     262             :                                SmallVectorImpl<MachineOperand> &Cond,
     263             :                                bool IgnoreBr = false);
     264             :     void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges = true);
     265             : 
     266             :     bool MeetIfcvtSizeLimit(MachineBasicBlock &BB,
     267             :                             unsigned Cycle, unsigned Extra,
     268             :                             BranchProbability Prediction) const {
     269       14256 :       return Cycle > 0 && TII->isProfitableToIfCvt(BB, Cycle, Extra,
     270        6974 :                                                    Prediction);
     271             :     }
     272             : 
     273             :     bool MeetIfcvtSizeLimit(MachineBasicBlock &TBB,
     274             :                             unsigned TCycle, unsigned TExtra,
     275             :                             MachineBasicBlock &FBB,
     276             :                             unsigned FCycle, unsigned FExtra,
     277             :                             BranchProbability Prediction) const {
     278         191 :       return TCycle > 0 && FCycle > 0 &&
     279         186 :         TII->isProfitableToIfCvt(TBB, TCycle, TExtra, FBB, FCycle, FExtra,
     280          93 :                                  Prediction);
     281             :     }
     282             : 
     283             :     /// Returns true if Block ends without a terminator.
     284             :     bool blockAlwaysFallThrough(BBInfo &BBI) const {
     285       18528 :       return BBI.IsBrAnalyzable && BBI.TrueBB == nullptr;
     286             :     }
     287             : 
     288             :     /// Used to sort if-conversion candidates.
     289         642 :     static bool IfcvtTokenCmp(const std::unique_ptr<IfcvtToken> &C1,
     290             :                               const std::unique_ptr<IfcvtToken> &C2) {
     291         642 :       int Incr1 = (C1->Kind == ICDiamond)
     292        1287 :         ? -(int)(C1->NumDups + C1->NumDups2) : (int)C1->NumDups;
     293         642 :       int Incr2 = (C2->Kind == ICDiamond)
     294        1345 :         ? -(int)(C2->NumDups + C2->NumDups2) : (int)C2->NumDups;
     295         642 :       if (Incr1 > Incr2)
     296             :         return true;
     297         590 :       else if (Incr1 == Incr2) {
     298             :         // Favors subsumption.
     299        1015 :         if (!C1->NeedSubsumption && C2->NeedSubsumption)
     300             :           return true;
     301        1016 :         else if (C1->NeedSubsumption == C2->NeedSubsumption) {
     302             :           // Favors diamond over triangle, etc.
     303        1016 :           if ((unsigned)C1->Kind < (unsigned)C2->Kind)
     304             :             return true;
     305         650 :           else if (C1->Kind == C2->Kind)
     306         324 :             return C1->BBI.BB->getNumber() < C2->BBI.BB->getNumber();
     307             :         }
     308             :       }
     309             :       return false;
     310             :     }
     311             :   };
     312             : 
     313             :   char IfConverter::ID = 0;
     314             : }
     315             : 
     316             : char &llvm::IfConverterID = IfConverter::ID;
     317             : 
     318       20212 : INITIALIZE_PASS_BEGIN(IfConverter, DEBUG_TYPE, "If Converter", false, false)
     319       20212 : INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
     320      166106 : INITIALIZE_PASS_END(IfConverter, DEBUG_TYPE, "If Converter", false, false)
     321             : 
     322       27090 : bool IfConverter::runOnMachineFunction(MachineFunction &MF) {
     323       65014 :   if (skipFunction(*MF.getFunction()) || (PredicateFtor && !PredicateFtor(MF)))
     324             :     return false;
     325             : 
     326       26187 :   const TargetSubtargetInfo &ST = MF.getSubtarget();
     327       26187 :   TLI = ST.getTargetLowering();
     328       26187 :   TII = ST.getInstrInfo();
     329       26187 :   TRI = ST.getRegisterInfo();
     330       52374 :   BranchFolder::MBFIWrapper MBFI(getAnalysis<MachineBlockFrequencyInfo>());
     331       26187 :   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
     332       26187 :   MRI = &MF.getRegInfo();
     333       26187 :   SchedModel.init(ST.getSchedModel(), &ST, TII);
     334             : 
     335       26187 :   if (!TII) return false;
     336             : 
     337       52374 :   PreRegAlloc = MRI->isSSA();
     338             : 
     339       26187 :   bool BFChange = false;
     340       26187 :   if (!PreRegAlloc) {
     341             :     // Tail merge tend to expose more if-conversion opportunities.
     342       52356 :     BranchFolder BF(true, false, MBFI, *MBPI);
     343       26178 :     BFChange = BF.OptimizeFunction(MF, TII, ST.getRegisterInfo(),
     344             :                                    getAnalysisIfAvailable<MachineModuleInfo>());
     345             :   }
     346             : 
     347             :   DEBUG(dbgs() << "\nIfcvt: function (" << ++FnNum <<  ") \'"
     348             :                << MF.getName() << "\'");
     349             : 
     350       78509 :   if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) {
     351             :     DEBUG(dbgs() << " skipped\n");
     352             :     return false;
     353             :   }
     354             :   DEBUG(dbgs() << "\n");
     355             : 
     356       26135 :   MF.RenumberBlocks();
     357       52270 :   BBAnalysis.resize(MF.getNumBlockIDs());
     358             : 
     359       52270 :   std::vector<std::unique_ptr<IfcvtToken>> Tokens;
     360       26135 :   MadeChange = false;
     361      104540 :   unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle +
     362      104540 :     NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds;
     363       29069 :   while (IfCvtLimit == -1 || (int)NumIfCvts < IfCvtLimit) {
     364             :     // Do an initial analysis for each basic block and find all the potential
     365             :     // candidates to perform if-conversion.
     366       27593 :     bool Change = false;
     367       27593 :     AnalyzeBlocks(MF, Tokens);
     368       29469 :     while (!Tokens.empty()) {
     369        5324 :       std::unique_ptr<IfcvtToken> Token = std::move(Tokens.back());
     370        3752 :       Tokens.pop_back();
     371        1876 :       BBInfo &BBI = Token->BBI;
     372        1876 :       IfcvtKind Kind = Token->Kind;
     373        1876 :       unsigned NumDups = Token->NumDups;
     374        1876 :       unsigned NumDups2 = Token->NumDups2;
     375             : 
     376             :       // If the block has been evicted out of the queue or it has already been
     377             :       // marked dead (due to it being predicated), then skip it.
     378        1876 :       if (BBI.IsDone)
     379          70 :         BBI.IsEnqueued = false;
     380        1876 :       if (!BBI.IsEnqueued)
     381         304 :         continue;
     382             : 
     383        1572 :       BBI.IsEnqueued = false;
     384             : 
     385        1572 :       bool RetVal = false;
     386        1572 :       switch (Kind) {
     387           0 :       default: llvm_unreachable("Unexpected!");
     388        1343 :       case ICSimple:
     389             :       case ICSimpleFalse: {
     390        1343 :         bool isFalse = Kind == ICSimpleFalse;
     391        2686 :         if ((isFalse && DisableSimpleF) || (!isFalse && DisableSimple)) break;
     392             :         DEBUG(dbgs() << "Ifcvt (Simple" << (Kind == ICSimpleFalse ?
     393             :                                             " false" : "")
     394             :                      << "): BB#" << BBI.BB->getNumber() << " ("
     395             :                      << ((Kind == ICSimpleFalse)
     396             :                          ? BBI.FalseBB->getNumber()
     397             :                          : BBI.TrueBB->getNumber()) << ") ");
     398        1343 :         RetVal = IfConvertSimple(BBI, Kind);
     399             :         DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
     400             :         if (RetVal) {
     401             :           if (isFalse) ++NumSimpleFalse;
     402             :           else         ++NumSimple;
     403             :         }
     404             :        break;
     405             :       }
     406         168 :       case ICTriangle:
     407             :       case ICTriangleRev:
     408             :       case ICTriangleFalse:
     409             :       case ICTriangleFRev: {
     410         168 :         bool isFalse = Kind == ICTriangleFalse;
     411         168 :         bool isRev   = (Kind == ICTriangleRev || Kind == ICTriangleFRev);
     412         168 :         if (DisableTriangle && !isFalse && !isRev) break;
     413         168 :         if (DisableTriangleR && !isFalse && isRev) break;
     414         168 :         if (DisableTriangleF && isFalse && !isRev) break;
     415         168 :         if (DisableTriangleFR && isFalse && isRev) break;
     416             :         DEBUG(dbgs() << "Ifcvt (Triangle");
     417             :         if (isFalse)
     418             :           DEBUG(dbgs() << " false");
     419             :         if (isRev)
     420             :           DEBUG(dbgs() << " rev");
     421             :         DEBUG(dbgs() << "): BB#" << BBI.BB->getNumber() << " (T:"
     422             :                      << BBI.TrueBB->getNumber() << ",F:"
     423             :                      << BBI.FalseBB->getNumber() << ") ");
     424         168 :         RetVal = IfConvertTriangle(BBI, Kind);
     425             :         DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
     426             :         if (RetVal) {
     427             :           if (isFalse) {
     428             :             if (isRev) ++NumTriangleFRev;
     429             :             else       ++NumTriangleFalse;
     430             :           } else {
     431             :             if (isRev) ++NumTriangleRev;
     432             :             else       ++NumTriangle;
     433             :           }
     434             :         }
     435             :         break;
     436             :       }
     437          60 :       case ICDiamond: {
     438          60 :         if (DisableDiamond) break;
     439             :         DEBUG(dbgs() << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:"
     440             :                      << BBI.TrueBB->getNumber() << ",F:"
     441             :                      << BBI.FalseBB->getNumber() << ") ");
     442         120 :         RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2,
     443          60 :                                   Token->TClobbersPred,
     444          60 :                                   Token->FClobbersPred);
     445             :         DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
     446             :         if (RetVal) ++NumDiamonds;
     447             :         break;
     448             :       }
     449           1 :       case ICForkedDiamond: {
     450           1 :         if (DisableForkedDiamond) break;
     451             :         DEBUG(dbgs() << "Ifcvt (Forked Diamond): BB#"
     452             :                      << BBI.BB->getNumber() << " (T:"
     453             :                      << BBI.TrueBB->getNumber() << ",F:"
     454             :                      << BBI.FalseBB->getNumber() << ") ");
     455           2 :         RetVal = IfConvertForkedDiamond(BBI, Kind, NumDups, NumDups2,
     456           1 :                                       Token->TClobbersPred,
     457           1 :                                       Token->FClobbersPred);
     458             :         DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
     459             :         if (RetVal) ++NumForkedDiamonds;
     460             :         break;
     461             :       }
     462             :       }
     463             : 
     464        1572 :       Change |= RetVal;
     465             : 
     466        9432 :       NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev +
     467        4716 :         NumTriangleFalse + NumTriangleFRev + NumDiamonds;
     468        1572 :       if (IfCvtLimit != -1 && (int)NumIfCvts >= IfCvtLimit)
     469             :         break;
     470             :     }
     471             : 
     472       27593 :     if (!Change)
     473             :       break;
     474        1464 :     MadeChange |= Change;
     475             :   }
     476             : 
     477       26135 :   Tokens.clear();
     478       52270 :   BBAnalysis.clear();
     479             : 
     480       27566 :   if (MadeChange && IfCvtBranchFold) {
     481        2862 :     BranchFolder BF(false, false, MBFI, *MBPI);
     482        1431 :     BF.OptimizeFunction(MF, TII, MF.getSubtarget().getRegisterInfo(),
     483             :                         getAnalysisIfAvailable<MachineModuleInfo>());
     484             :   }
     485             : 
     486       26135 :   MadeChange |= BFChange;
     487             :   return MadeChange;
     488             : }
     489             : 
     490             : /// BB has a fallthrough. Find its 'false' successor given its 'true' successor.
     491             : static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
     492             :                                          MachineBasicBlock *TrueBB) {
     493       16086 :   for (MachineBasicBlock *SuccBB : BB->successors()) {
     494        9936 :     if (SuccBB != TrueBB)
     495             :       return SuccBB;
     496             :   }
     497             :   return nullptr;
     498             : }
     499             : 
     500             : /// Reverse the condition of the end of the block branch. Swap block's 'true'
     501             : /// and 'false' successors.
     502          49 : bool IfConverter::reverseBranchCondition(BBInfo &BBI) const {
     503          98 :   DebugLoc dl;  // FIXME: this is nowhere
     504          49 :   if (!TII->reverseBranchCondition(BBI.BrCond)) {
     505          49 :     TII->removeBranch(*BBI.BB);
     506          98 :     TII->insertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond, dl);
     507          98 :     std::swap(BBI.TrueBB, BBI.FalseBB);
     508             :     return true;
     509             :   }
     510             :   return false;
     511             : }
     512             : 
     513             : /// Returns the next block in the function blocks ordering. If it is the end,
     514             : /// returns NULL.
     515             : static inline MachineBasicBlock *getNextBlock(MachineBasicBlock &MBB) {
     516        8898 :   MachineFunction::iterator I = MBB.getIterator();
     517        8898 :   MachineFunction::iterator E = MBB.getParent()->end();
     518        4449 :   if (++I == E)
     519             :     return nullptr;
     520        3154 :   return &*I;
     521             : }
     522             : 
     523             : /// Returns true if the 'true' block (along with its predecessor) forms a valid
     524             : /// simple shape for ifcvt. It also returns the number of instructions that the
     525             : /// ifcvt would need to duplicate if performed in Dups.
     526        9357 : bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups,
     527             :                               BranchProbability Prediction) const {
     528        9357 :   Dups = 0;
     529        9357 :   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
     530             :     return false;
     531             : 
     532        8653 :   if (TrueBBI.IsBrAnalyzable)
     533             :     return false;
     534             : 
     535        6962 :   if (TrueBBI.BB->pred_size() > 1) {
     536        4691 :     if (TrueBBI.CannotBeCopied ||
     537        4660 :         !TII->isProfitableToDupForIfCvt(*TrueBBI.BB, TrueBBI.NonPredSize,
     538        2330 :                                         Prediction))
     539             :       return false;
     540        2142 :     Dups = TrueBBI.NonPredSize;
     541             :   }
     542             : 
     543             :   return true;
     544             : }
     545             : 
     546             : /// Returns true if the 'true' and 'false' blocks (along with their common
     547             : /// predecessor) forms a valid triangle shape for ifcvt. If 'FalseBranch' is
     548             : /// true, it checks if 'true' block's false branch branches to the 'false' block
     549             : /// rather than the other way around. It also returns the number of instructions
     550             : /// that the ifcvt would need to duplicate if performed in 'Dups'.
     551       18714 : bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
     552             :                                 bool FalseBranch, unsigned &Dups,
     553             :                                 BranchProbability Prediction) const {
     554       18714 :   Dups = 0;
     555       18714 :   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
     556             :     return false;
     557             : 
     558       34612 :   if (TrueBBI.BB->pred_size() > 1) {
     559        6976 :     if (TrueBBI.CannotBeCopied)
     560             :       return false;
     561             : 
     562        6862 :     unsigned Size = TrueBBI.NonPredSize;
     563        6862 :     if (TrueBBI.IsBrAnalyzable) {
     564        2202 :       if (TrueBBI.TrueBB && TrueBBI.BrCond.empty())
     565             :         // Ends with an unconditional branch. It will be removed.
     566         244 :         --Size;
     567             :       else {
     568        1958 :         MachineBasicBlock *FExit = FalseBranch
     569        1958 :           ? TrueBBI.TrueBB : TrueBBI.FalseBB;
     570        1958 :         if (FExit)
     571             :           // Require a conditional branch
     572        1258 :           ++Size;
     573             :       }
     574             :     }
     575        6862 :     if (!TII->isProfitableToDupForIfCvt(*TrueBBI.BB, Size, Prediction))
     576             :       return false;
     577        5732 :     Dups = Size;
     578             :   }
     579             : 
     580       16062 :   MachineBasicBlock *TExit = FalseBranch ? TrueBBI.FalseBB : TrueBBI.TrueBB;
     581       21822 :   if (!TExit && blockAlwaysFallThrough(TrueBBI)) {
     582       11520 :     MachineFunction::iterator I = TrueBBI.BB->getIterator();
     583       17280 :     if (++I == TrueBBI.BB->getParent()->end())
     584             :       return false;
     585             :     TExit = &*I;
     586             :   }
     587       15776 :   return TExit && TExit == FalseBBI.BB;
     588             : }
     589             : 
     590             : /// Count duplicated instructions and move the iterators to show where they
     591             : /// are.
     592             : /// @param TIB True Iterator Begin
     593             : /// @param FIB False Iterator Begin
     594             : /// These two iterators initially point to the first instruction of the two
     595             : /// blocks, and finally point to the first non-shared instruction.
     596             : /// @param TIE True Iterator End
     597             : /// @param FIE False Iterator End
     598             : /// These two iterators initially point to End() for the two blocks() and
     599             : /// finally point to the first shared instruction in the tail.
     600             : /// Upon return [TIB, TIE), and [FIB, FIE) mark the un-duplicated portions of
     601             : /// two blocks.
     602             : /// @param Dups1 count of duplicated instructions at the beginning of the 2
     603             : /// blocks.
     604             : /// @param Dups2 count of duplicated instructions at the end of the 2 blocks.
     605             : /// @param SkipUnconditionalBranches if true, Don't make sure that
     606             : /// unconditional branches at the end of the blocks are the same. True is
     607             : /// passed when the blocks are analyzable to allow for fallthrough to be
     608             : /// handled.
     609             : /// @return false if the shared portion prevents if conversion.
     610         425 : bool IfConverter::CountDuplicatedInstructions(
     611             :     MachineBasicBlock::iterator &TIB,
     612             :     MachineBasicBlock::iterator &FIB,
     613             :     MachineBasicBlock::iterator &TIE,
     614             :     MachineBasicBlock::iterator &FIE,
     615             :     unsigned &Dups1, unsigned &Dups2,
     616             :     MachineBasicBlock &TBB, MachineBasicBlock &FBB,
     617             :     bool SkipUnconditionalBranches) const {
     618             : 
     619         887 :   while (TIB != TIE && FIB != FIE) {
     620             :     // Skip dbg_value instructions. These do not count.
     621         442 :     TIB = skipDebugInstructionsForward(TIB, TIE);
     622         442 :     FIB = skipDebugInstructionsForward(FIB, FIE);
     623         884 :     if (TIB == TIE || FIB == FIE)
     624             :       break;
     625         884 :     if (!TIB->isIdenticalTo(*FIB))
     626             :       break;
     627             :     // A pred-clobbering instruction in the shared portion prevents
     628             :     // if-conversion.
     629          47 :     std::vector<MachineOperand> PredDefs;
     630          54 :     if (TII->DefinesPredicate(*TIB, PredDefs))
     631          14 :       return false;
     632             :     // If we get all the way to the branch instructions, don't count them.
     633          40 :     if (!TIB->isBranch())
     634          18 :       ++Dups1;
     635          20 :     ++TIB;
     636          20 :     ++FIB;
     637             :   }
     638             : 
     639             :   // Check for already containing all of the block.
     640         833 :   if (TIB == TIE || FIB == FIE)
     641             :     return true;
     642             :   // Now, in preparation for counting duplicate instructions at the ends of the
     643             :   // blocks, switch to reverse_iterators. Note that getReverse() returns an
     644             :   // iterator that points to the same instruction, unlike std::reverse_iterator.
     645             :   // We have to do our own shifting so that we get the same range.
     646         830 :   MachineBasicBlock::reverse_iterator RTIE = std::next(TIE.getReverse());
     647         830 :   MachineBasicBlock::reverse_iterator RFIE = std::next(FIE.getReverse());
     648         830 :   const MachineBasicBlock::reverse_iterator RTIB = std::next(TIB.getReverse());
     649         830 :   const MachineBasicBlock::reverse_iterator RFIB = std::next(FIB.getReverse());
     650             : 
     651         679 :   if (!TBB.succ_empty() || !FBB.succ_empty()) {
     652         181 :     if (SkipUnconditionalBranches) {
     653         340 :       while (RTIE != RTIB && RTIE->isUnconditionalBranch())
     654             :         ++RTIE;
     655         524 :       while (RFIE != RFIB && RFIE->isUnconditionalBranch())
     656             :         ++RFIE;
     657             :     }
     658             :   }
     659             : 
     660             :   // Count duplicate instructions at the ends of the blocks.
     661        1162 :   while (RTIE != RTIB && RFIE != RFIB) {
     662             :     // Skip dbg_value instructions. These do not count.
     663             :     // Note that these are reverse iterators going forward.
     664         574 :     RTIE = skipDebugInstructionsForward(RTIE, RTIB);
     665         574 :     RFIE = skipDebugInstructionsForward(RFIE, RFIB);
     666        1148 :     if (RTIE == RTIB || RFIE == RFIB)
     667             :       break;
     668        1148 :     if (!RTIE->isIdenticalTo(*RFIE))
     669             :       break;
     670             :     // We have to verify that any branch instructions are the same, and then we
     671             :     // don't count them toward the # of duplicate instructions.
     672         332 :     if (!RTIE->isBranch())
     673         133 :       ++Dups2;
     674         166 :     ++RTIE;
     675             :     ++RFIE;
     676             :   }
     677         830 :   TIE = std::next(RTIE.getReverse());
     678         830 :   FIE = std::next(RFIE.getReverse());
     679         415 :   return true;
     680             : }
     681             : 
     682             : /// RescanInstructions - Run ScanInstructions on a pair of blocks.
     683             : /// @param TIB - True Iterator Begin, points to first non-shared instruction
     684             : /// @param FIB - False Iterator Begin, points to first non-shared instruction
     685             : /// @param TIE - True Iterator End, points past last non-shared instruction
     686             : /// @param FIE - False Iterator End, points past last non-shared instruction
     687             : /// @param TrueBBI  - BBInfo to update for the true block.
     688             : /// @param FalseBBI - BBInfo to update for the false block.
     689             : /// @returns - false if either block cannot be predicated or if both blocks end
     690             : ///   with a predicate-clobbering instruction.
     691         418 : bool IfConverter::RescanInstructions(
     692             :     MachineBasicBlock::iterator &TIB, MachineBasicBlock::iterator &FIB,
     693             :     MachineBasicBlock::iterator &TIE, MachineBasicBlock::iterator &FIE,
     694             :     BBInfo &TrueBBI, BBInfo &FalseBBI) const {
     695         418 :   bool BranchUnpredicable = true;
     696         418 :   TrueBBI.IsUnpredicable = FalseBBI.IsUnpredicable = false;
     697         418 :   ScanInstructions(TrueBBI, TIB, TIE, BranchUnpredicable);
     698         418 :   if (TrueBBI.IsUnpredicable)
     699             :     return false;
     700         190 :   ScanInstructions(FalseBBI, FIB, FIE, BranchUnpredicable);
     701         190 :   if (FalseBBI.IsUnpredicable)
     702             :     return false;
     703         105 :   if (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred)
     704             :     return false;
     705          98 :   return true;
     706             : }
     707             : 
     708             : #ifndef NDEBUG
     709             : static void verifySameBranchInstructions(
     710             :     MachineBasicBlock *MBB1,
     711             :     MachineBasicBlock *MBB2) {
     712             :   const MachineBasicBlock::reverse_iterator B1 = MBB1->rend();
     713             :   const MachineBasicBlock::reverse_iterator B2 = MBB2->rend();
     714             :   MachineBasicBlock::reverse_iterator E1 = MBB1->rbegin();
     715             :   MachineBasicBlock::reverse_iterator E2 = MBB2->rbegin();
     716             :   while (E1 != B1 && E2 != B2) {
     717             :     skipDebugInstructionsForward(E1, B1);
     718             :     skipDebugInstructionsForward(E2, B2);
     719             :     if (E1 == B1 && E2 == B2)
     720             :       break;
     721             : 
     722             :     if (E1 == B1) {
     723             :       assert(!E2->isBranch() && "Branch mis-match, one block is empty.");
     724             :       break;
     725             :     }
     726             :     if (E2 == B2) {
     727             :       assert(!E1->isBranch() && "Branch mis-match, one block is empty.");
     728             :       break;
     729             :     }
     730             : 
     731             :     if (E1->isBranch() || E2->isBranch())
     732             :       assert(E1->isIdenticalTo(*E2) &&
     733             :              "Branch mis-match, branch instructions don't match.");
     734             :     else
     735             :       break;
     736             :     ++E1;
     737             :     ++E2;
     738             :   }
     739             : }
     740             : #endif
     741             : 
     742             : /// ValidForkedDiamond - Returns true if the 'true' and 'false' blocks (along
     743             : /// with their common predecessor) form a diamond if a common tail block is
     744             : /// extracted.
     745             : /// While not strictly a diamond, this pattern would form a diamond if
     746             : /// tail-merging had merged the shared tails.
     747             : ///           EBB
     748             : ///         _/   \_
     749             : ///         |     |
     750             : ///        TBB   FBB
     751             : ///        /  \ /   \
     752             : ///  FalseBB TrueBB FalseBB
     753             : /// Currently only handles analyzable branches.
     754             : /// Specifically excludes actual diamonds to avoid overlap.
     755        4577 : bool IfConverter::ValidForkedDiamond(
     756             :     BBInfo &TrueBBI, BBInfo &FalseBBI,
     757             :     unsigned &Dups1, unsigned &Dups2,
     758             :     BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const {
     759        4577 :   Dups1 = Dups2 = 0;
     760        8569 :   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||
     761        7977 :       FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)
     762             :     return false;
     763             : 
     764        3879 :   if (!TrueBBI.IsBrAnalyzable || !FalseBBI.IsBrAnalyzable)
     765             :     return false;
     766             :   // Don't IfConvert blocks that can't be folded into their predecessor.
     767        3234 :   if  (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
     768             :     return false;
     769             : 
     770             :   // This function is specifically looking for conditional tails, as
     771             :   // unconditional tails are already handled by the standard diamond case.
     772        1274 :   if (TrueBBI.BrCond.size() == 0 ||
     773         388 :       FalseBBI.BrCond.size() == 0)
     774             :     return false;
     775             : 
     776          50 :   MachineBasicBlock *TT = TrueBBI.TrueBB;
     777          50 :   MachineBasicBlock *TF = TrueBBI.FalseBB;
     778          50 :   MachineBasicBlock *FT = FalseBBI.TrueBB;
     779          50 :   MachineBasicBlock *FF = FalseBBI.FalseBB;
     780             : 
     781          50 :   if (!TT)
     782           0 :     TT = getNextBlock(*TrueBBI.BB);
     783          50 :   if (!TF)
     784           0 :     TF = getNextBlock(*TrueBBI.BB);
     785          50 :   if (!FT)
     786           0 :     FT = getNextBlock(*FalseBBI.BB);
     787          50 :   if (!FF)
     788           0 :     FF = getNextBlock(*FalseBBI.BB);
     789             : 
     790          50 :   if (!TT || !TF)
     791             :     return false;
     792             : 
     793             :   // Check successors. If they don't match, bail.
     794          50 :   if (!((TT == FT && TF == FF) || (TF == FT && TT == FF)))
     795             :     return false;
     796             : 
     797          15 :   bool FalseReversed = false;
     798          15 :   if (TF == FT && TT == FF) {
     799             :     // If the branches are opposing, but we can't reverse, don't do it.
     800          12 :     if (!FalseBBI.IsBrReversible)
     801             :       return false;
     802          12 :     FalseReversed = true;
     803          12 :     reverseBranchCondition(FalseBBI);
     804             :   }
     805             :   auto UnReverseOnExit = make_scope_exit([&]() {
     806          15 :     if (FalseReversed)
     807          12 :       reverseBranchCondition(FalseBBI);
     808          30 :   });
     809             : 
     810             :   // Count duplicate instructions at the beginning of the true and false blocks.
     811          30 :   MachineBasicBlock::iterator TIB = TrueBBI.BB->begin();
     812          30 :   MachineBasicBlock::iterator FIB = FalseBBI.BB->begin();
     813          30 :   MachineBasicBlock::iterator TIE = TrueBBI.BB->end();
     814          30 :   MachineBasicBlock::iterator FIE = FalseBBI.BB->end();
     815          15 :   if(!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,
     816             :                                   *TrueBBI.BB, *FalseBBI.BB,
     817             :                                   /* SkipUnconditionalBranches */ true))
     818             :     return false;
     819             : 
     820          15 :   TrueBBICalc.BB = TrueBBI.BB;
     821          15 :   FalseBBICalc.BB = FalseBBI.BB;
     822          15 :   if (!RescanInstructions(TIB, FIB, TIE, FIE, TrueBBICalc, FalseBBICalc))
     823             :     return false;
     824             : 
     825             :   // The size is used to decide whether to if-convert, and the shared portions
     826             :   // are subtracted off. Because of the subtraction, we just use the size that
     827             :   // was calculated by the original ScanInstructions, as it is correct.
     828           1 :   TrueBBICalc.NonPredSize = TrueBBI.NonPredSize;
     829           1 :   FalseBBICalc.NonPredSize = FalseBBI.NonPredSize;
     830           1 :   return true;
     831             : }
     832             : 
     833             : /// ValidDiamond - Returns true if the 'true' and 'false' blocks (along
     834             : /// with their common predecessor) forms a valid diamond shape for ifcvt.
     835        4674 : bool IfConverter::ValidDiamond(
     836             :     BBInfo &TrueBBI, BBInfo &FalseBBI,
     837             :     unsigned &Dups1, unsigned &Dups2,
     838             :     BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const {
     839        4674 :   Dups1 = Dups2 = 0;
     840        8763 :   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||
     841        8171 :       FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)
     842             :     return false;
     843             : 
     844        3976 :   MachineBasicBlock *TT = TrueBBI.TrueBB;
     845        3976 :   MachineBasicBlock *FT = FalseBBI.TrueBB;
     846             : 
     847        4726 :   if (!TT && blockAlwaysFallThrough(TrueBBI))
     848         750 :     TT = getNextBlock(*TrueBBI.BB);
     849        6050 :   if (!FT && blockAlwaysFallThrough(FalseBBI))
     850        2074 :     FT = getNextBlock(*FalseBBI.BB);
     851        3976 :   if (TT != FT)
     852             :     return false;
     853         694 :   if (!TT && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))
     854             :     return false;
     855        1737 :   if  (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
     856             :     return false;
     857             : 
     858             :   // FIXME: Allow true block to have an early exit?
     859         485 :   if (TrueBBI.FalseBB || FalseBBI.FalseBB)
     860             :     return false;
     861             : 
     862             :   // Count duplicate instructions at the beginning and end of the true and
     863             :   // false blocks.
     864             :   // Skip unconditional branches only if we are considering an analyzable
     865             :   // diamond. Otherwise the branches must be the same.
     866         410 :   bool SkipUnconditionalBranches =
     867         410 :       TrueBBI.IsBrAnalyzable && FalseBBI.IsBrAnalyzable;
     868         820 :   MachineBasicBlock::iterator TIB = TrueBBI.BB->begin();
     869         820 :   MachineBasicBlock::iterator FIB = FalseBBI.BB->begin();
     870         820 :   MachineBasicBlock::iterator TIE = TrueBBI.BB->end();
     871         820 :   MachineBasicBlock::iterator FIE = FalseBBI.BB->end();
     872         410 :   if(!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,
     873             :                                   *TrueBBI.BB, *FalseBBI.BB,
     874             :                                   SkipUnconditionalBranches))
     875             :     return false;
     876             : 
     877         403 :   TrueBBICalc.BB = TrueBBI.BB;
     878         403 :   FalseBBICalc.BB = FalseBBI.BB;
     879         403 :   if (!RescanInstructions(TIB, FIB, TIE, FIE, TrueBBICalc, FalseBBICalc))
     880             :     return false;
     881             :   // The size is used to decide whether to if-convert, and the shared portions
     882             :   // are subtracted off. Because of the subtraction, we just use the size that
     883             :   // was calculated by the original ScanInstructions, as it is correct.
     884          97 :   TrueBBICalc.NonPredSize = TrueBBI.NonPredSize;
     885          97 :   FalseBBICalc.NonPredSize = FalseBBI.NonPredSize;
     886          97 :   return true;
     887             : }
     888             : 
     889             : /// AnalyzeBranches - Look at the branches at the end of a block to determine if
     890             : /// the block is predicable.
     891       40875 : void IfConverter::AnalyzeBranches(BBInfo &BBI) {
     892       40875 :   if (BBI.IsDone)
     893         791 :     return;
     894             : 
     895       40084 :   BBI.TrueBB = BBI.FalseBB = nullptr;
     896       80168 :   BBI.BrCond.clear();
     897       40084 :   BBI.IsBrAnalyzable =
     898       40084 :       !TII->analyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);
     899      200420 :   SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
     900       46503 :   BBI.IsBrReversible = (RevCond.size() == 0) ||
     901        6419 :       !TII->reverseBranchCondition(RevCond);
     902       40084 :   BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB == nullptr;
     903             : 
     904       80168 :   if (BBI.BrCond.size()) {
     905             :     // No false branch. This BB must end with a conditional branch and a
     906             :     // fallthrough.
     907        6419 :     if (!BBI.FalseBB)
     908       12296 :       BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB);
     909        6419 :     if (!BBI.FalseBB) {
     910             :       // Malformed bcc? True and false blocks are the same?
     911           2 :       BBI.IsUnpredicable = true;
     912             :     }
     913             :   }
     914             : }
     915             : 
     916             : /// ScanInstructions - Scan all the instructions in the block to determine if
     917             : /// the block is predicable. In most cases, that means all the instructions
     918             : /// in the block are isPredicable(). Also checks if the block contains any
     919             : /// instruction which can clobber a predicate (e.g. condition code register).
     920             : /// If so, the block is not predicable unless it's the last instruction.
     921       41483 : void IfConverter::ScanInstructions(BBInfo &BBI,
     922             :                                    MachineBasicBlock::iterator &Begin,
     923             :                                    MachineBasicBlock::iterator &End,
     924             :                                    bool BranchUnpredicable) const {
     925       41483 :   if (BBI.IsDone || BBI.IsUnpredicable)
     926             :     return;
     927             : 
     928       39363 :   bool AlreadyPredicated = !BBI.Predicate.empty();
     929             : 
     930       39363 :   BBI.NonPredSize = 0;
     931       39363 :   BBI.ExtraCost = 0;
     932       39363 :   BBI.ExtraCost2 = 0;
     933       39363 :   BBI.ClobbersPred = false;
     934      174117 :   for (MachineInstr &MI : make_range(Begin, End)) {
     935       62882 :     if (MI.isDebugValue())
     936        1507 :       continue;
     937             : 
     938             :     // It's unsafe to duplicate convergent instructions in this context, so set
     939             :     // BBI.CannotBeCopied to true if MI is convergent.  To see why, consider the
     940             :     // following CFG, which is subject to our "simple" transformation.
     941             :     //
     942             :     //    BB0     // if (c1) goto BB1; else goto BB2;
     943             :     //   /   \
     944             :     //  BB1   |
     945             :     //   |   BB2  // if (c2) goto TBB; else goto FBB;
     946             :     //   |   / |
     947             :     //   |  /  |
     948             :     //   TBB   |
     949             :     //    |    |
     950             :     //    |   FBB
     951             :     //    |
     952             :     //    exit
     953             :     //
     954             :     // Suppose we want to move TBB's contents up into BB1 and BB2 (in BB1 they'd
     955             :     // be unconditional, and in BB2, they'd be predicated upon c2), and suppose
     956             :     // TBB contains a convergent instruction.  This is safe iff doing so does
     957             :     // not add a control-flow dependency to the convergent instruction -- i.e.,
     958             :     // it's safe iff the set of control flows that leads us to the convergent
     959             :     // instruction does not get smaller after the transformation.
     960             :     //
     961             :     // Originally we executed TBB if c1 || c2.  After the transformation, there
     962             :     // are two copies of TBB's instructions.  We get to the first if c1, and we
     963             :     // get to the second if !c1 && c2.
     964             :     //
     965             :     // There are clearly fewer ways to satisfy the condition "c1" than
     966             :     // "c1 || c2".  Since we've shrunk the set of control flows which lead to
     967             :     // our convergent instruction, the transformation is unsafe.
     968       62838 :     if (MI.isNotDuplicable() || MI.isConvergent())
     969        3317 :       BBI.CannotBeCopied = true;
     970             : 
     971       62838 :     bool isPredicated = TII->isPredicated(MI);
     972       62838 :     bool isCondBr = BBI.IsBrAnalyzable && MI.isConditionalBranch();
     973             : 
     974       63646 :     if (BranchUnpredicable && MI.isBranch()) {
     975          13 :       BBI.IsUnpredicable = true;
     976       30386 :       return;
     977             :     }
     978             : 
     979             :     // A conditional branch is not predicable, but it may be eliminated.
     980       64244 :     if (isCondBr)
     981        1419 :       continue;
     982             : 
     983       61406 :     if (!isPredicated) {
     984       60634 :       BBI.NonPredSize++;
     985       60634 :       unsigned ExtraPredCost = TII->getPredicationCost(MI);
     986       60634 :       unsigned NumCycles = SchedModel.computeInstrLatency(&MI, false);
     987       60634 :       if (NumCycles > 1)
     988       14149 :         BBI.ExtraCost += NumCycles-1;
     989       60634 :       BBI.ExtraCost2 += ExtraPredCost;
     990         772 :     } else if (!AlreadyPredicated) {
     991             :       // FIXME: This instruction is already predicated before the
     992             :       // if-conversion pass. It's probably something like a conditional move.
     993             :       // Mark this block unpredicable for now.
     994         446 :       BBI.IsUnpredicable = true;
     995         446 :       return;
     996             :     }
     997             : 
     998       60960 :     if (BBI.ClobbersPred && !isPredicated) {
     999             :       // Predicate modification instruction should end the block (except for
    1000             :       // already predicated instructions and end of block branches).
    1001             :       // Predicate may have been modified, the subsequent (currently)
    1002             :       // unpredicated instructions cannot be correctly predicated.
    1003         636 :       BBI.IsUnpredicable = true;
    1004         636 :       return;
    1005             :     }
    1006             : 
    1007             :     // FIXME: Make use of PredDefs? e.g. ADDC, SUBC sets predicates but are
    1008             :     // still potentially predicable.
    1009       91370 :     std::vector<MachineOperand> PredDefs;
    1010       60324 :     if (TII->DefinesPredicate(MI, PredDefs))
    1011        4170 :       BBI.ClobbersPred = true;
    1012             : 
    1013       60324 :     if (!TII->isPredicable(MI)) {
    1014       29278 :       BBI.IsUnpredicable = true;
    1015             :       return;
    1016             :     }
    1017             :   }
    1018             : }
    1019             : 
    1020             : /// Determine if the block is a suitable candidate to be predicated by the
    1021             : /// specified predicate.
    1022             : /// @param BBI BBInfo for the block to check
    1023             : /// @param Pred Predicate array for the branch that leads to BBI
    1024             : /// @param isTriangle true if the Analysis is for a triangle
    1025             : /// @param RevBranch true if Reverse(Pred) leads to BBI (e.g. BBI is the false
    1026             : ///        case
    1027             : /// @param hasCommonTail true if BBI shares a tail with a sibling block that
    1028             : ///        contains any instruction that would make the block unpredicable.
    1029        6682 : bool IfConverter::FeasibilityAnalysis(BBInfo &BBI,
    1030             :                                       SmallVectorImpl<MachineOperand> &Pred,
    1031             :                                       bool isTriangle, bool RevBranch,
    1032             :                                       bool hasCommonTail) {
    1033             :   // If the block is dead or unpredicable, then it cannot be predicated.
    1034             :   // Two blocks may share a common unpredicable tail, but this doesn't prevent
    1035             :   // them from being if-converted. The non-shared portion is assumed to have
    1036             :   // been checked
    1037        6682 :   if (BBI.IsDone || (BBI.IsUnpredicable && !hasCommonTail))
    1038             :     return false;
    1039             : 
    1040             :   // If it is already predicated but we couldn't analyze its terminator, the
    1041             :   // latter might fallthrough, but we can't determine where to.
    1042             :   // Conservatively avoid if-converting again.
    1043        4120 :   if (BBI.Predicate.size() && !BBI.IsBrAnalyzable)
    1044             :     return false;
    1045             : 
    1046             :   // If it is already predicated, check if the new predicate subsumes
    1047             :   // its predicate.
    1048        4149 :   if (BBI.Predicate.size() && !TII->SubsumesPredicate(Pred, BBI.Predicate))
    1049             :     return false;
    1050             : 
    1051        5767 :   if (!hasCommonTail && BBI.BrCond.size()) {
    1052         103 :     if (!isTriangle)
    1053          42 :       return false;
    1054             : 
    1055             :     // Test predicate subsumption.
    1056         473 :     SmallVector<MachineOperand, 4> RevPred(Pred.begin(), Pred.end());
    1057         473 :     SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
    1058         103 :     if (RevBranch) {
    1059          36 :       if (TII->reverseBranchCondition(Cond))
    1060          42 :         return false;
    1061             :     }
    1062         200 :     if (TII->reverseBranchCondition(RevPred) ||
    1063         400 :         !TII->SubsumesPredicate(Cond, RevPred))
    1064             :       return false;
    1065             :   }
    1066             : 
    1067             :   return true;
    1068             : }
    1069             : 
    1070             : /// Analyze the structure of the sub-CFG starting from the specified block.
    1071             : /// Record its successors and whether it looks like an if-conversion candidate.
    1072       44217 : void IfConverter::AnalyzeBlock(
    1073             :     MachineBasicBlock &MBB, std::vector<std::unique_ptr<IfcvtToken>> &Tokens) {
    1074             :   struct BBState {
    1075       53595 :     BBState(MachineBasicBlock &MBB) : MBB(&MBB), SuccsAnalyzed(false) {}
    1076             :     MachineBasicBlock *MBB;
    1077             : 
    1078             :     /// This flag is true if MBB's successors have been analyzed.
    1079             :     bool SuccsAnalyzed;
    1080             :   };
    1081             : 
    1082             :   // Push MBB to the stack.
    1083      132651 :   SmallVector<BBState, 16> BBStack(1, MBB);
    1084             : 
    1085      102501 :   while (!BBStack.empty()) {
    1086      116568 :     BBState &State = BBStack.back();
    1087       58284 :     MachineBasicBlock *BB = State.MBB;
    1088      116568 :     BBInfo &BBI = BBAnalysis[BB->getNumber()];
    1089             : 
    1090       58284 :     if (!State.SuccsAnalyzed) {
    1091       66315 :       if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed) {
    1092       12720 :         BBStack.pop_back();
    1093       12720 :         continue;
    1094             :       }
    1095             : 
    1096       40875 :       BBI.BB = BB;
    1097       40875 :       BBI.IsBeingAnalyzed = true;
    1098             : 
    1099       40875 :       AnalyzeBranches(BBI);
    1100       81750 :       MachineBasicBlock::iterator Begin = BBI.BB->begin();
    1101       81750 :       MachineBasicBlock::iterator End = BBI.BB->end();
    1102       40875 :       ScanInstructions(BBI, Begin, End);
    1103             : 
    1104             :       // Unanalyzable or ends with fallthrough or unconditional branch, or if is
    1105             :       // not considered for ifcvt anymore.
    1106       75333 :       if (!BBI.IsBrAnalyzable || BBI.BrCond.empty() || BBI.IsDone) {
    1107       34458 :         BBI.IsBeingAnalyzed = false;
    1108       34458 :         BBI.IsAnalyzed = true;
    1109       34458 :         BBStack.pop_back();
    1110       34458 :         continue;
    1111             :       }
    1112             : 
    1113             :       // Do not ifcvt if either path is a back edge to the entry block.
    1114        8143 :       if (BBI.TrueBB == BB || BBI.FalseBB == BB) {
    1115        1726 :         BBI.IsBeingAnalyzed = false;
    1116        1726 :         BBI.IsAnalyzed = true;
    1117        1726 :         BBStack.pop_back();
    1118        1726 :         continue;
    1119             :       }
    1120             : 
    1121             :       // Do not ifcvt if true and false fallthrough blocks are the same.
    1122        4693 :       if (!BBI.FalseBB) {
    1123           2 :         BBI.IsBeingAnalyzed = false;
    1124           2 :         BBI.IsAnalyzed = true;
    1125           2 :         BBStack.pop_back();
    1126           2 :         continue;
    1127             :       }
    1128             : 
    1129             :       // Push the False and True blocks to the stack.
    1130        4689 :       State.SuccsAnalyzed = true;
    1131        9378 :       BBStack.push_back(*BBI.FalseBB);
    1132        9378 :       BBStack.push_back(*BBI.TrueBB);
    1133        4689 :       continue;
    1134             :     }
    1135             : 
    1136        9378 :     BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
    1137        9378 :     BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
    1138             : 
    1139        4695 :     if (TrueBBI.IsDone && FalseBBI.IsDone) {
    1140           6 :       BBI.IsBeingAnalyzed = false;
    1141           6 :       BBI.IsAnalyzed = true;
    1142           6 :       BBStack.pop_back();
    1143           6 :       continue;
    1144             :     }
    1145             : 
    1146             :     SmallVector<MachineOperand, 4>
    1147       23415 :         RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
    1148        4683 :     bool CanRevCond = !TII->reverseBranchCondition(RevCond);
    1149             : 
    1150        4683 :     unsigned Dups = 0;
    1151        4683 :     unsigned Dups2 = 0;
    1152        4683 :     bool TNeedSub = !TrueBBI.Predicate.empty();
    1153        4683 :     bool FNeedSub = !FalseBBI.Predicate.empty();
    1154        4683 :     bool Enqueued = false;
    1155             : 
    1156        4683 :     BranchProbability Prediction = MBPI->getEdgeProbability(BB, TrueBBI.BB);
    1157             : 
    1158        4683 :     if (CanRevCond) {
    1159       14022 :       BBInfo TrueBBICalc, FalseBBICalc;
    1160          98 :       auto feasibleDiamond = [&]() {
    1161         392 :         bool MeetsSize = MeetIfcvtSizeLimit(
    1162         588 :             *TrueBBI.BB, (TrueBBICalc.NonPredSize - (Dups + Dups2) +
    1163          98 :                           TrueBBICalc.ExtraCost), TrueBBICalc.ExtraCost2,
    1164         588 :             *FalseBBI.BB, (FalseBBICalc.NonPredSize - (Dups + Dups2) +
    1165          98 :                            FalseBBICalc.ExtraCost), FalseBBICalc.ExtraCost2,
    1166         392 :             Prediction);
    1167          98 :         bool TrueFeasible = FeasibilityAnalysis(TrueBBI, BBI.BrCond,
    1168             :                                                 /* IsTriangle */ false, /* RevCond */ false,
    1169          98 :                                                 /* hasCommonTail */ true);
    1170          98 :         bool FalseFeasible = FeasibilityAnalysis(FalseBBI, RevCond,
    1171             :                                                  /* IsTriangle */ false, /* RevCond */ false,
    1172          98 :                                                  /* hasCommonTail */ true);
    1173          98 :         return MeetsSize && TrueFeasible && FalseFeasible;
    1174        4674 :       };
    1175             : 
    1176        4674 :       if (ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2,
    1177             :                        TrueBBICalc, FalseBBICalc)) {
    1178          97 :         if (feasibleDiamond()) {
    1179             :           // Diamond:
    1180             :           //   EBB
    1181             :           //   / \_
    1182             :           //  |   |
    1183             :           // TBB FBB
    1184             :           //   \ /
    1185             :           //  TailBB
    1186             :           // Note TailBB can be empty.
    1187         240 :           Tokens.push_back(llvm::make_unique<IfcvtToken>(
    1188          60 :               BBI, ICDiamond, TNeedSub | FNeedSub, Dups, Dups2,
    1189          60 :               (bool) TrueBBICalc.ClobbersPred, (bool) FalseBBICalc.ClobbersPred));
    1190          60 :           Enqueued = true;
    1191             :         }
    1192        4577 :       } else if (ValidForkedDiamond(TrueBBI, FalseBBI, Dups, Dups2,
    1193             :                                     TrueBBICalc, FalseBBICalc)) {
    1194           1 :         if (feasibleDiamond()) {
    1195             :           // ForkedDiamond:
    1196             :           // if TBB and FBB have a common tail that includes their conditional
    1197             :           // branch instructions, then we can If Convert this pattern.
    1198             :           //          EBB
    1199             :           //         _/ \_
    1200             :           //         |   |
    1201             :           //        TBB  FBB
    1202             :           //        / \ /   \
    1203             :           //  FalseBB TrueBB FalseBB
    1204             :           //
    1205           4 :           Tokens.push_back(llvm::make_unique<IfcvtToken>(
    1206           1 :               BBI, ICForkedDiamond, TNeedSub | FNeedSub, Dups, Dups2,
    1207           1 :               (bool) TrueBBICalc.ClobbersPred, (bool) FalseBBICalc.ClobbersPred));
    1208           1 :           Enqueued = true;
    1209             :         }
    1210             :       }
    1211             :     }
    1212             : 
    1213        4683 :     if (ValidTriangle(TrueBBI, FalseBBI, false, Dups, Prediction) &&
    1214          88 :         MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
    1215        4723 :                            TrueBBI.ExtraCost2, Prediction) &&
    1216          40 :         FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) {
    1217             :       // Triangle:
    1218             :       //   EBB
    1219             :       //   | \_
    1220             :       //   |  |
    1221             :       //   | TBB
    1222             :       //   |  /
    1223             :       //   FBB
    1224           7 :       Tokens.push_back(
    1225          21 :           llvm::make_unique<IfcvtToken>(BBI, ICTriangle, TNeedSub, Dups));
    1226           7 :       Enqueued = true;
    1227             :     }
    1228             : 
    1229        4683 :     if (ValidTriangle(TrueBBI, FalseBBI, true, Dups, Prediction) &&
    1230          26 :         MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
    1231        4693 :                            TrueBBI.ExtraCost2, Prediction) &&
    1232          10 :         FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) {
    1233           1 :       Tokens.push_back(
    1234           3 :           llvm::make_unique<IfcvtToken>(BBI, ICTriangleRev, TNeedSub, Dups));
    1235           1 :       Enqueued = true;
    1236             :     }
    1237             : 
    1238        4683 :     if (ValidSimple(TrueBBI, Dups, Prediction) &&
    1239        4513 :         MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
    1240        6881 :                            TrueBBI.ExtraCost2, Prediction) &&
    1241        2198 :         FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {
    1242             :       // Simple (split, no rejoin):
    1243             :       //   EBB
    1244             :       //   | \_
    1245             :       //   |  |
    1246             :       //   | TBB---> exit
    1247             :       //   |
    1248             :       //   FBB
    1249        1284 :       Tokens.push_back(
    1250        3852 :           llvm::make_unique<IfcvtToken>(BBI, ICSimple, TNeedSub, Dups));
    1251        1284 :       Enqueued = true;
    1252             :     }
    1253             : 
    1254        4683 :     if (CanRevCond) {
    1255             :       // Try the other path...
    1256        4674 :       if (ValidTriangle(FalseBBI, TrueBBI, false, Dups,
    1257             :                         Prediction.getCompl()) &&
    1258        5442 :           MeetIfcvtSizeLimit(*FalseBBI.BB,
    1259        1902 :                              FalseBBI.NonPredSize + FalseBBI.ExtraCost,
    1260        6312 :                              FalseBBI.ExtraCost2, Prediction.getCompl()) &&
    1261        1638 :           FeasibilityAnalysis(FalseBBI, RevCond, true)) {
    1262         608 :         Tokens.push_back(llvm::make_unique<IfcvtToken>(BBI, ICTriangleFalse,
    1263             :                                                        FNeedSub, Dups));
    1264         152 :         Enqueued = true;
    1265             :       }
    1266             : 
    1267        4674 :       if (ValidTriangle(FalseBBI, TrueBBI, true, Dups,
    1268             :                         Prediction.getCompl()) &&
    1269        5871 :           MeetIfcvtSizeLimit(*FalseBBI.BB,
    1270        2054 :                              FalseBBI.NonPredSize + FalseBBI.ExtraCost,
    1271        6437 :                            FalseBBI.ExtraCost2, Prediction.getCompl()) &&
    1272        1763 :         FeasibilityAnalysis(FalseBBI, RevCond, true, true)) {
    1273         140 :         Tokens.push_back(
    1274         420 :             llvm::make_unique<IfcvtToken>(BBI, ICTriangleFRev, FNeedSub, Dups));
    1275         140 :         Enqueued = true;
    1276             :       }
    1277             : 
    1278        4674 :       if (ValidSimple(FalseBBI, Dups, Prediction.getCompl()) &&
    1279        2731 :           MeetIfcvtSizeLimit(*FalseBBI.BB,
    1280         947 :                              FalseBBI.NonPredSize + FalseBBI.ExtraCost,
    1281        5511 :                              FalseBBI.ExtraCost2, Prediction.getCompl()) &&
    1282         837 :           FeasibilityAnalysis(FalseBBI, RevCond)) {
    1283         231 :         Tokens.push_back(
    1284         693 :             llvm::make_unique<IfcvtToken>(BBI, ICSimpleFalse, FNeedSub, Dups));
    1285         231 :         Enqueued = true;
    1286             :       }
    1287             :     }
    1288             : 
    1289        4683 :     BBI.IsEnqueued = Enqueued;
    1290        4683 :     BBI.IsBeingAnalyzed = false;
    1291        4683 :     BBI.IsAnalyzed = true;
    1292        4683 :     BBStack.pop_back();
    1293             :   }
    1294       44217 : }
    1295             : 
    1296             : /// Analyze all blocks and find entries for all if-conversion candidates.
    1297       27593 : void IfConverter::AnalyzeBlocks(
    1298             :     MachineFunction &MF, std::vector<std::unique_ptr<IfcvtToken>> &Tokens) {
    1299      126996 :   for (MachineBasicBlock &MBB : MF)
    1300       44217 :     AnalyzeBlock(MBB, Tokens);
    1301             : 
    1302             :   // Sort to favor more complex ifcvt scheme.
    1303       82779 :   std::stable_sort(Tokens.begin(), Tokens.end(), IfcvtTokenCmp);
    1304       27593 : }
    1305             : 
    1306             : /// Returns true either if ToMBB is the next block after MBB or that all the
    1307             : /// intervening blocks are empty (given MBB can fall through to its next block).
    1308        1453 : static bool canFallThroughTo(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB) {
    1309        2906 :   MachineFunction::iterator PI = MBB.getIterator();
    1310        1453 :   MachineFunction::iterator I = std::next(PI);
    1311        2906 :   MachineFunction::iterator TI = ToMBB.getIterator();
    1312        2906 :   MachineFunction::iterator E = MBB.getParent()->end();
    1313        1455 :   while (I != TI) {
    1314             :     // Check isSuccessor to avoid case where the next block is empty, but
    1315             :     // it's not a successor.
    1316         380 :     if (I == E || !I->empty() || !PI->isSuccessor(&*I))
    1317             :       return false;
    1318           2 :     PI = I++;
    1319             :   }
    1320             :   // Finally see if the last I is indeed a successor to PI.
    1321        2700 :   return PI->isSuccessor(&*I);
    1322             : }
    1323             : 
    1324             : /// Invalidate predecessor BB info so it would be re-analyzed to determine if it
    1325             : /// can be if-converted. If predecessor is already enqueued, dequeue it!
    1326             : void IfConverter::InvalidatePreds(MachineBasicBlock &MBB) {
    1327        3438 :   for (const MachineBasicBlock *Predecessor : MBB.predecessors()) {
    1328         824 :     BBInfo &PBBI = BBAnalysis[Predecessor->getNumber()];
    1329         412 :     if (PBBI.IsDone || PBBI.BB == &MBB)
    1330             :       continue;
    1331         392 :     PBBI.IsAnalyzed = false;
    1332         392 :     PBBI.IsEnqueued = false;
    1333             :   }
    1334             : }
    1335             : 
    1336             : /// Inserts an unconditional branch from \p MBB to \p ToMBB.
    1337         132 : static void InsertUncondBranch(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB,
    1338             :                                const TargetInstrInfo *TII) {
    1339         264 :   DebugLoc dl;  // FIXME: this is nowhere
    1340         264 :   SmallVector<MachineOperand, 0> NoCond;
    1341         264 :   TII->insertBranch(MBB, &ToMBB, nullptr, NoCond, dl);
    1342         132 : }
    1343             : 
    1344             : /// Behaves like LiveRegUnits::StepForward() but also adds implicit uses to all
    1345             : /// values defined in MI which are also live/used by MI.
    1346        2066 : static void UpdatePredRedefs(MachineInstr &MI, LivePhysRegs &Redefs) {
    1347             :   const TargetRegisterInfo *TRI = MI.getParent()->getParent()
    1348        2066 :     ->getSubtarget().getRegisterInfo();
    1349             : 
    1350             :   // Before stepping forward past MI, remember which regs were live
    1351             :   // before MI. This is needed to set the Undef flag only when reg is
    1352             :   // dead.
    1353        4132 :   SparseSet<unsigned> LiveBeforeMI;
    1354        2066 :   LiveBeforeMI.setUniverse(TRI->getNumRegs());
    1355       86775 :   for (unsigned Reg : Redefs)
    1356       80577 :     LiveBeforeMI.insert(Reg);
    1357             : 
    1358        4132 :   SmallVector<std::pair<unsigned, const MachineOperand*>, 4> Clobbers;
    1359        2066 :   Redefs.stepForward(MI, Clobbers);
    1360             : 
    1361             :   // Now add the implicit uses for each of the clobbered values.
    1362        7584 :   for (auto Clobber : Clobbers) {
    1363             :     // FIXME: Const cast here is nasty, but better than making StepForward
    1364             :     // take a mutable instruction instead of const.
    1365        1386 :     unsigned Reg = Clobber.first;
    1366        1386 :     MachineOperand &Op = const_cast<MachineOperand&>(*Clobber.second);
    1367        1386 :     MachineInstr *OpMI = Op.getParent();
    1368        2772 :     MachineInstrBuilder MIB(*OpMI->getParent()->getParent(), OpMI);
    1369        1464 :     if (Op.isRegMask()) {
    1370             :       // First handle regmasks.  They clobber any entries in the mask which
    1371             :       // means that we need a def for those registers.
    1372         156 :       if (LiveBeforeMI.count(Reg))
    1373          78 :         MIB.addReg(Reg, RegState::Implicit);
    1374             : 
    1375             :       // We also need to add an implicit def of this register for the later
    1376             :       // use to read from.
    1377             :       // For the register allocator to have allocated a register clobbered
    1378             :       // by the call which is used later, it must be the case that
    1379             :       // the call doesn't return.
    1380          78 :       MIB.addReg(Reg, RegState::Implicit | RegState::Define);
    1381          78 :       continue;
    1382             :     }
    1383             :     assert(Op.isReg() && "Register operand required");
    1384        1308 :     if (Op.isDead()) {
    1385             :       // If we found a dead def, but it needs to be live, then remove the dead
    1386             :       // flag.
    1387         250 :       if (Redefs.contains(Op.getReg()))
    1388             :         Op.setIsDead(false);
    1389             :     }
    1390        2616 :     if (LiveBeforeMI.count(Reg))
    1391         313 :       MIB.addReg(Reg, RegState::Implicit);
    1392             :     else {
    1393         995 :       bool HasLiveSubReg = false;
    1394        2017 :       for (MCSubRegIterator S(Reg, TRI); S.isValid(); ++S) {
    1395          90 :         if (!LiveBeforeMI.count(*S))
    1396             :           continue;
    1397             :         HasLiveSubReg = true;
    1398             :         break;
    1399             :       }
    1400         995 :       if (HasLiveSubReg)
    1401           3 :         MIB.addReg(Reg, RegState::Implicit);
    1402             :     }
    1403             :   }
    1404        2066 : }
    1405             : 
    1406             : /// Remove kill flags from operands with a registers in the \p DontKill set.
    1407        1623 : static void RemoveKills(MachineInstr &MI, const LivePhysRegs &DontKill) {
    1408        8131 :   for (MIBundleOperands O(MI); O.isValid(); ++O) {
    1409       21466 :     if (!O->isReg() || !O->isKill())
    1410        6226 :       continue;
    1411         564 :     if (DontKill.contains(O->getReg()))
    1412          88 :       O->setIsKill(false);
    1413             :   }
    1414        1623 : }
    1415             : 
    1416             : /// Walks a range of machine instructions and removes kill flags for registers
    1417             : /// in the \p DontKill set.
    1418         369 : static void RemoveKills(MachineBasicBlock::iterator I,
    1419             :                         MachineBasicBlock::iterator E,
    1420             :                         const LivePhysRegs &DontKill,
    1421             :                         const MCRegisterInfo &MCRI) {
    1422        1986 :   for (MachineInstr &MI : make_range(I, E))
    1423         624 :     RemoveKills(MI, DontKill);
    1424         369 : }
    1425             : 
    1426             : /// If convert a simple (split, no rejoin) sub-CFG.
    1427        1343 : bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {
    1428        2686 :   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
    1429        2686 :   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
    1430        1343 :   BBInfo *CvtBBI = &TrueBBI;
    1431        1343 :   BBInfo *NextBBI = &FalseBBI;
    1432             : 
    1433        6715 :   SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
    1434        1343 :   if (Kind == ICSimpleFalse)
    1435             :     std::swap(CvtBBI, NextBBI);
    1436             : 
    1437        1343 :   MachineBasicBlock &CvtMBB = *CvtBBI->BB;
    1438        1343 :   MachineBasicBlock &NextMBB = *NextBBI->BB;
    1439        2632 :   if (CvtBBI->IsDone ||
    1440        1289 :       (CvtBBI->CannotBeCopied && CvtMBB.pred_size() > 1)) {
    1441             :     // Something has changed. It's no longer safe to predicate this block.
    1442          54 :     BBI.IsAnalyzed = false;
    1443          54 :     CvtBBI->IsAnalyzed = false;
    1444          54 :     return false;
    1445             :   }
    1446             : 
    1447        1289 :   if (CvtMBB.hasAddressTaken())
    1448             :     // Conservatively abort if-conversion if BB's address is taken.
    1449             :     return false;
    1450             : 
    1451        1288 :   if (Kind == ICSimpleFalse)
    1452         148 :     if (TII->reverseBranchCondition(Cond))
    1453           0 :       llvm_unreachable("Unable to reverse branch condition!");
    1454             : 
    1455        2576 :   Redefs.init(*TRI);
    1456        2576 :   DontKill.init(*TRI);
    1457             : 
    1458        2576 :   if (MRI->tracksLiveness()) {
    1459             :     // Initialize liveins to the first BB. These are potentiall redefined by
    1460             :     // predicated instructions.
    1461        1285 :     Redefs.addLiveIns(CvtMBB);
    1462        1285 :     Redefs.addLiveIns(NextMBB);
    1463             :     // Compute a set of registers which must not be killed by instructions in
    1464             :     // BB1: This is everything live-in to BB2.
    1465        1285 :     DontKill.addLiveIns(NextMBB);
    1466             :   }
    1467             : 
    1468             :   // Remove the branches from the entry so we can add the contents of the true
    1469             :   // block to it.
    1470        1288 :   BBI.NonPredSize -= TII->removeBranch(*BBI.BB);
    1471             : 
    1472        1288 :   if (CvtMBB.pred_size() > 1) {
    1473             :     // Copy instructions in the true block, predicate them, and add them to
    1474             :     // the entry block.
    1475         979 :     CopyAndPredicateBlock(BBI, *CvtBBI, Cond);
    1476             : 
    1477             :     // Keep the CFG updated.
    1478         979 :     BBI.BB->removeSuccessor(&CvtMBB, true);
    1479             :   } else {
    1480             :     // Predicate the instructions in the true block.
    1481         927 :     RemoveKills(CvtMBB.begin(), CvtMBB.end(), DontKill, *TRI);
    1482         309 :     PredicateBlock(*CvtBBI, CvtMBB.end(), Cond);
    1483             : 
    1484             :     // Merge converted block into entry block. The BB to Cvt edge is removed
    1485             :     // by MergeBlocks.
    1486         309 :     MergeBlocks(BBI, *CvtBBI);
    1487             :   }
    1488             : 
    1489        1288 :   bool IterIfcvt = true;
    1490        1288 :   if (!canFallThroughTo(*BBI.BB, NextMBB)) {
    1491          70 :     InsertUncondBranch(*BBI.BB, NextMBB, TII);
    1492          70 :     BBI.HasFallThrough = false;
    1493             :     // Now ifcvt'd block will look like this:
    1494             :     // BB:
    1495             :     // ...
    1496             :     // t, f = cmp
    1497             :     // if t op
    1498             :     // b BBf
    1499             :     //
    1500             :     // We cannot further ifcvt this block because the unconditional branch
    1501             :     // will have to be predicated on the new condition, that will not be
    1502             :     // available if cmp executes.
    1503          70 :     IterIfcvt = false;
    1504             :   }
    1505             : 
    1506             :   // Update block info. BB can be iteratively if-converted.
    1507             :   if (!IterIfcvt)
    1508          70 :     BBI.IsDone = true;
    1509        2576 :   InvalidatePreds(*BBI.BB);
    1510        1288 :   CvtBBI->IsDone = true;
    1511             : 
    1512             :   // FIXME: Must maintain LiveIns.
    1513        1288 :   return true;
    1514             : }
    1515             : 
    1516             : /// If convert a triangle sub-CFG.
    1517         168 : bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
    1518         336 :   BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
    1519         336 :   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
    1520         168 :   BBInfo *CvtBBI = &TrueBBI;
    1521         168 :   BBInfo *NextBBI = &FalseBBI;
    1522         336 :   DebugLoc dl;  // FIXME: this is nowhere
    1523             : 
    1524         840 :   SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
    1525         168 :   if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
    1526             :     std::swap(CvtBBI, NextBBI);
    1527             : 
    1528         168 :   MachineBasicBlock &CvtMBB = *CvtBBI->BB;
    1529         168 :   MachineBasicBlock &NextMBB = *NextBBI->BB;
    1530         336 :   if (CvtBBI->IsDone ||
    1531         168 :       (CvtBBI->CannotBeCopied && CvtMBB.pred_size() > 1)) {
    1532             :     // Something has changed. It's no longer safe to predicate this block.
    1533           0 :     BBI.IsAnalyzed = false;
    1534           0 :     CvtBBI->IsAnalyzed = false;
    1535           0 :     return false;
    1536             :   }
    1537             : 
    1538         168 :   if (CvtMBB.hasAddressTaken())
    1539             :     // Conservatively abort if-conversion if BB's address is taken.
    1540             :     return false;
    1541             : 
    1542         165 :   if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
    1543         158 :     if (TII->reverseBranchCondition(Cond))
    1544           0 :       llvm_unreachable("Unable to reverse branch condition!");
    1545             : 
    1546         165 :   if (Kind == ICTriangleRev || Kind == ICTriangleFRev) {
    1547          25 :     if (reverseBranchCondition(*CvtBBI)) {
    1548             :       // BB has been changed, modify its predecessors (except for this
    1549             :       // one) so they don't get ifcvt'ed based on bad intel.
    1550          75 :       for (MachineBasicBlock *PBB : CvtMBB.predecessors()) {
    1551          25 :         if (PBB == BBI.BB)
    1552          25 :           continue;
    1553           0 :         BBInfo &PBBI = BBAnalysis[PBB->getNumber()];
    1554           0 :         if (PBBI.IsEnqueued) {
    1555           0 :           PBBI.IsAnalyzed = false;
    1556           0 :           PBBI.IsEnqueued = false;
    1557             :         }
    1558             :       }
    1559             :     }
    1560             :   }
    1561             : 
    1562             :   // Initialize liveins to the first BB. These are potentially redefined by
    1563             :   // predicated instructions.
    1564         330 :   Redefs.init(*TRI);
    1565         330 :   if (MRI->tracksLiveness()) {
    1566         142 :     Redefs.addLiveIns(CvtMBB);
    1567         142 :     Redefs.addLiveIns(NextMBB);
    1568             :   }
    1569             : 
    1570         330 :   DontKill.clear();
    1571             : 
    1572         165 :   bool HasEarlyExit = CvtBBI->FalseBB != nullptr;
    1573         660 :   BranchProbability CvtNext, CvtFalse, BBNext, BBCvt;
    1574             : 
    1575         165 :   if (HasEarlyExit) {
    1576             :     // Get probabilities before modifying CvtMBB and BBI.BB.
    1577          53 :     CvtNext = MBPI->getEdgeProbability(&CvtMBB, &NextMBB);
    1578          53 :     CvtFalse = MBPI->getEdgeProbability(&CvtMBB, CvtBBI->FalseBB);
    1579          53 :     BBNext = MBPI->getEdgeProbability(BBI.BB, &NextMBB);
    1580          53 :     BBCvt = MBPI->getEdgeProbability(BBI.BB, &CvtMBB);
    1581             :   }
    1582             : 
    1583             :   // Remove the branches from the entry so we can add the contents of the true
    1584             :   // block to it.
    1585         165 :   BBI.NonPredSize -= TII->removeBranch(*BBI.BB);
    1586             : 
    1587         165 :   if (CvtMBB.pred_size() > 1) {
    1588             :     // Copy instructions in the true block, predicate them, and add them to
    1589             :     // the entry block.
    1590           4 :     CopyAndPredicateBlock(BBI, *CvtBBI, Cond, true);
    1591             :   } else {
    1592             :     // Predicate the 'true' block after removing its branch.
    1593         161 :     CvtBBI->NonPredSize -= TII->removeBranch(CvtMBB);
    1594         161 :     PredicateBlock(*CvtBBI, CvtMBB.end(), Cond);
    1595             : 
    1596             :     // Now merge the entry of the triangle with the true block.
    1597         161 :     MergeBlocks(BBI, *CvtBBI, false);
    1598             :   }
    1599             : 
    1600             :   // Keep the CFG updated.
    1601         165 :   BBI.BB->removeSuccessor(&CvtMBB, true);
    1602             : 
    1603             :   // If 'true' block has a 'false' successor, add an exit branch to it.
    1604         165 :   if (HasEarlyExit) {
    1605             :     SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(),
    1606         265 :                                            CvtBBI->BrCond.end());
    1607          53 :     if (TII->reverseBranchCondition(RevCond))
    1608           0 :       llvm_unreachable("Unable to reverse branch condition!");
    1609             : 
    1610             :     // Update the edge probability for both CvtBBI->FalseBB and NextBBI.
    1611             :     // NewNext = New_Prob(BBI.BB, NextMBB) =
    1612             :     //   Prob(BBI.BB, NextMBB) +
    1613             :     //   Prob(BBI.BB, CvtMBB) * Prob(CvtMBB, NextMBB)
    1614             :     // NewFalse = New_Prob(BBI.BB, CvtBBI->FalseBB) =
    1615             :     //   Prob(BBI.BB, CvtMBB) * Prob(CvtMBB, CvtBBI->FalseBB)
    1616         106 :     auto NewTrueBB = getNextBlock(*BBI.BB);
    1617         106 :     auto NewNext = BBNext + BBCvt * CvtNext;
    1618         159 :     auto NewTrueBBIter = find(BBI.BB->successors(), NewTrueBB);
    1619         159 :     if (NewTrueBBIter != BBI.BB->succ_end())
    1620          27 :       BBI.BB->setSuccProbability(NewTrueBBIter, NewNext);
    1621             : 
    1622          53 :     auto NewFalse = BBCvt * CvtFalse;
    1623         106 :     TII->insertBranch(*BBI.BB, CvtBBI->FalseBB, nullptr, RevCond, dl);
    1624          53 :     BBI.BB->addSuccessor(CvtBBI->FalseBB, NewFalse);
    1625             :   }
    1626             : 
    1627             :   // Merge in the 'false' block if the 'false' block has no other
    1628             :   // predecessors. Otherwise, add an unconditional branch to 'false'.
    1629         165 :   bool FalseBBDead = false;
    1630         165 :   bool IterIfcvt = true;
    1631         165 :   bool isFallThrough = canFallThroughTo(*BBI.BB, NextMBB);
    1632         165 :   if (!isFallThrough) {
    1633             :     // Only merge them if the true block does not fallthrough to the false
    1634             :     // block. By not merging them, we make it possible to iteratively
    1635             :     // ifcvt the blocks.
    1636           8 :     if (!HasEarlyExit &&
    1637          45 :         NextMBB.pred_size() == 1 && !NextBBI->HasFallThrough &&
    1638           0 :         !NextMBB.hasAddressTaken()) {
    1639           0 :       MergeBlocks(BBI, *NextBBI);
    1640           0 :       FalseBBDead = true;
    1641             :     } else {
    1642          34 :       InsertUncondBranch(*BBI.BB, NextMBB, TII);
    1643          34 :       BBI.HasFallThrough = false;
    1644             :     }
    1645             :     // Mixed predicated and unpredicated code. This cannot be iteratively
    1646             :     // predicated.
    1647             :     IterIfcvt = false;
    1648             :   }
    1649             : 
    1650             :   // Update block info. BB can be iteratively if-converted.
    1651         165 :   if (!IterIfcvt)
    1652          34 :     BBI.IsDone = true;
    1653         330 :   InvalidatePreds(*BBI.BB);
    1654         165 :   CvtBBI->IsDone = true;
    1655         165 :   if (FalseBBDead)
    1656           0 :     NextBBI->IsDone = true;
    1657             : 
    1658             :   // FIXME: Must maintain LiveIns.
    1659             :   return true;
    1660             : }
    1661             : 
    1662             : /// Common code shared between diamond conversions.
    1663             : /// \p BBI, \p TrueBBI, and \p FalseBBI form the diamond shape.
    1664             : /// \p NumDups1 - number of shared instructions at the beginning of \p TrueBBI
    1665             : ///               and FalseBBI
    1666             : /// \p NumDups2 - number of shared instructions at the end of \p TrueBBI
    1667             : ///               and \p FalseBBI
    1668             : /// \p RemoveBranch - Remove the common branch of the two blocks before
    1669             : ///                   predicating. Only false for unanalyzable fallthrough
    1670             : ///                   cases. The caller will replace the branch if necessary.
    1671             : /// \p MergeAddEdges - Add successor edges when merging blocks. Only false for
    1672             : ///                    unanalyzable fallthrough
    1673          61 : bool IfConverter::IfConvertDiamondCommon(
    1674             :     BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,
    1675             :     unsigned NumDups1, unsigned NumDups2,
    1676             :     bool TClobbersPred, bool FClobbersPred,
    1677             :     bool RemoveBranch, bool MergeAddEdges) {
    1678             : 
    1679         183 :   if (TrueBBI.IsDone || FalseBBI.IsDone ||
    1680         305 :       TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1) {
    1681             :     // Something has changed. It's no longer safe to predicate these blocks.
    1682           0 :     BBI.IsAnalyzed = false;
    1683           0 :     TrueBBI.IsAnalyzed = false;
    1684           0 :     FalseBBI.IsAnalyzed = false;
    1685           0 :     return false;
    1686             :   }
    1687             : 
    1688          61 :   if (TrueBBI.BB->hasAddressTaken() || FalseBBI.BB->hasAddressTaken())
    1689             :     // Conservatively abort if-conversion if either BB has its address taken.
    1690             :     return false;
    1691             : 
    1692             :   // Put the predicated instructions from the 'true' block before the
    1693             :   // instructions from the 'false' block, unless the true block would clobber
    1694             :   // the predicate, in which case, do the opposite.
    1695          60 :   BBInfo *BBI1 = &TrueBBI;
    1696          60 :   BBInfo *BBI2 = &FalseBBI;
    1697         240 :   SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
    1698          60 :   if (TII->reverseBranchCondition(RevCond))
    1699           0 :     llvm_unreachable("Unable to reverse branch condition!");
    1700          60 :   SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond;
    1701          60 :   SmallVector<MachineOperand, 4> *Cond2 = &RevCond;
    1702             : 
    1703             :   // Figure out the more profitable ordering.
    1704          60 :   bool DoSwap = false;
    1705          60 :   if (TClobbersPred && !FClobbersPred)
    1706             :     DoSwap = true;
    1707          60 :   else if (!TClobbersPred && !FClobbersPred) {
    1708          59 :     if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)
    1709          16 :       DoSwap = true;
    1710           1 :   } else if (TClobbersPred && FClobbersPred)
    1711           0 :     llvm_unreachable("Predicate info cannot be clobbered by both sides.");
    1712             :   if (DoSwap) {
    1713             :     std::swap(BBI1, BBI2);
    1714             :     std::swap(Cond1, Cond2);
    1715             :   }
    1716             : 
    1717             :   // Remove the conditional branch from entry to the blocks.
    1718          60 :   BBI.NonPredSize -= TII->removeBranch(*BBI.BB);
    1719             : 
    1720          60 :   MachineBasicBlock &MBB1 = *BBI1->BB;
    1721          60 :   MachineBasicBlock &MBB2 = *BBI2->BB;
    1722             : 
    1723             :   // Initialize the Redefs:
    1724             :   // - BB2 live-in regs need implicit uses before being redefined by BB1
    1725             :   //   instructions.
    1726             :   // - BB1 live-out regs need implicit uses before being redefined by BB2
    1727             :   //   instructions. We start with BB1 live-ins so we have the live-out regs
    1728             :   //   after tracking the BB1 instructions.
    1729         120 :   Redefs.init(*TRI);
    1730         120 :   if (MRI->tracksLiveness()) {
    1731          58 :     Redefs.addLiveIns(MBB1);
    1732          58 :     Redefs.addLiveIns(MBB2);
    1733             :   }
    1734             : 
    1735             :   // Remove the duplicated instructions at the beginnings of both paths.
    1736             :   // Skip dbg_value instructions
    1737          60 :   MachineBasicBlock::iterator DI1 = MBB1.getFirstNonDebugInstr();
    1738          60 :   MachineBasicBlock::iterator DI2 = MBB2.getFirstNonDebugInstr();
    1739          60 :   BBI1->NonPredSize -= NumDups1;
    1740          60 :   BBI2->NonPredSize -= NumDups1;
    1741             : 
    1742             :   // Skip past the dups on each side separately since there may be
    1743             :   // differing dbg_value entries.
    1744          60 :   for (unsigned i = 0; i < NumDups1; ++DI1) {
    1745          18 :     if (!DI1->isDebugValue())
    1746           9 :       ++i;
    1747             :   }
    1748          69 :   while (NumDups1 != 0) {
    1749           9 :     ++DI2;
    1750          18 :     if (!DI2->isDebugValue())
    1751           9 :       --NumDups1;
    1752             :   }
    1753             : 
    1754             :   // Compute a set of registers which must not be killed by instructions in BB1:
    1755             :   // This is everything used+live in BB2 after the duplicated instructions. We
    1756             :   // can compute this set by simulating liveness backwards from the end of BB2.
    1757         120 :   DontKill.init(*TRI);
    1758         120 :   if (MRI->tracksLiveness()) {
    1759         552 :     for (const MachineInstr &MI : make_range(MBB2.rbegin(), ++DI2.getReverse()))
    1760         131 :       DontKill.stepBackward(MI);
    1761             : 
    1762         192 :     for (const MachineInstr &MI : make_range(MBB1.begin(), DI1)) {
    1763          18 :       SmallVector<std::pair<unsigned, const MachineOperand*>, 4> Dummy;
    1764           9 :       Redefs.stepForward(MI, Dummy);
    1765             :     }
    1766             :   }
    1767             :   // Kill flags in the true block for registers living into the false block
    1768             :   // must be removed. This should be done before extracting the common
    1769             :   // instructions from the beginning of the MBB1, since these instructions
    1770             :   // can actually differ between MBB1 and MBB2 in terms of <kill> flags.
    1771         180 :   RemoveKills(MBB1.begin(), MBB1.end(), DontKill, *TRI);
    1772             : 
    1773         240 :   BBI.BB->splice(BBI.BB->end(), &MBB1, MBB1.begin(), DI1);
    1774         120 :   MBB2.erase(MBB2.begin(), DI2);
    1775             : 
    1776             :   // The branches have been checked to match, so it is safe to remove the branch
    1777             :   // in BB1 and rely on the copy in BB2
    1778             : #ifndef NDEBUG
    1779             :   // Unanalyzable branches must match exactly. Check that now.
    1780             :   if (!BBI1->IsBrAnalyzable)
    1781             :     verifySameBranchInstructions(&MBB1, &MBB2);
    1782             : #endif
    1783          60 :   BBI1->NonPredSize -= TII->removeBranch(*BBI1->BB);
    1784             :   // Remove duplicated instructions.
    1785          60 :   DI1 = MBB1.end();
    1786          60 :   for (unsigned i = 0; i != NumDups2; ) {
    1787             :     // NumDups2 only counted non-dbg_value instructions, so this won't
    1788             :     // run off the head of the list.
    1789             :     assert(DI1 != MBB1.begin());
    1790          23 :     --DI1;
    1791             :     // skip dbg_value instructions
    1792          46 :     if (!DI1->isDebugValue())
    1793          23 :       ++i;
    1794             :   }
    1795         120 :   MBB1.erase(DI1, MBB1.end());
    1796             : 
    1797         120 :   DI2 = BBI2->BB->end();
    1798             :   // The branches have been checked to match. Skip over the branch in the false
    1799             :   // block so that we don't try to predicate it.
    1800          60 :   if (RemoveBranch)
    1801          32 :     BBI2->NonPredSize -= TII->removeBranch(*BBI2->BB);
    1802             :   else {
    1803             :     do {
    1804             :       assert(DI2 != MBB2.begin());
    1805          72 :       DI2--;
    1806         128 :     } while (DI2->isBranch() || DI2->isDebugValue());
    1807          28 :     DI2++;
    1808             :   }
    1809          83 :   while (NumDups2 != 0) {
    1810             :     // NumDups2 only counted non-dbg_value instructions, so this won't
    1811             :     // run off the head of the list.
    1812             :     assert(DI2 != MBB2.begin());
    1813          23 :     --DI2;
    1814             :     // skip dbg_value instructions
    1815          46 :     if (!DI2->isDebugValue())
    1816          23 :       --NumDups2;
    1817             :   }
    1818             : 
    1819             :   // Remember which registers would later be defined by the false block.
    1820             :   // This allows us not to predicate instructions in the true block that would
    1821             :   // later be re-defined. That is, rather than
    1822             :   //   subeq  r0, r1, #1
    1823             :   //   addne  r0, r1, #1
    1824             :   // generate:
    1825             :   //   sub    r0, r1, #1
    1826             :   //   addne  r0, r1, #1
    1827         120 :   SmallSet<unsigned, 4> RedefsByFalse;
    1828         120 :   SmallSet<unsigned, 4> ExtUses;
    1829          60 :   if (TII->isProfitableToUnpredicate(MBB1, MBB2)) {
    1830           5 :     for (const MachineInstr &FI : make_range(MBB2.begin(), DI2)) {
    1831           1 :       if (FI.isDebugValue())
    1832           0 :         continue;
    1833           2 :       SmallVector<unsigned, 4> Defs;
    1834           7 :       for (const MachineOperand &MO : FI.operands()) {
    1835           6 :         if (!MO.isReg())
    1836           6 :           continue;
    1837           4 :         unsigned Reg = MO.getReg();
    1838           4 :         if (!Reg)
    1839           2 :           continue;
    1840           2 :         if (MO.isDef()) {
    1841           1 :           Defs.push_back(Reg);
    1842           1 :         } else if (!RedefsByFalse.count(Reg)) {
    1843             :           // These are defined before ctrl flow reach the 'false' instructions.
    1844             :           // They cannot be modified by the 'true' instructions.
    1845           1 :           for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
    1846           2 :                SubRegs.isValid(); ++SubRegs)
    1847           2 :             ExtUses.insert(*SubRegs);
    1848             :         }
    1849             :       }
    1850             : 
    1851           4 :       for (unsigned Reg : Defs) {
    1852           1 :         if (!ExtUses.count(Reg)) {
    1853           1 :           for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
    1854           2 :                SubRegs.isValid(); ++SubRegs)
    1855           2 :             RedefsByFalse.insert(*SubRegs);
    1856             :         }
    1857             :       }
    1858             :     }
    1859             :   }
    1860             : 
    1861             :   // Predicate the 'true' block.
    1862         120 :   PredicateBlock(*BBI1, MBB1.end(), *Cond1, &RedefsByFalse);
    1863             : 
    1864             :   // After predicating BBI1, if there is a predicated terminator in BBI1 and
    1865             :   // a non-predicated in BBI2, then we don't want to predicate the one from
    1866             :   // BBI2. The reason is that if we merged these blocks, we would end up with
    1867             :   // two predicated terminators in the same block.
    1868         180 :   if (!MBB2.empty() && (DI2 == MBB2.end())) {
    1869          31 :     MachineBasicBlock::iterator BBI1T = MBB1.getFirstTerminator();
    1870          31 :     MachineBasicBlock::iterator BBI2T = MBB2.getFirstTerminator();
    1871          65 :     if (BBI1T != MBB1.end() && TII->isPredicated(*BBI1T) &&
    1872          35 :         BBI2T != MBB2.end() && !TII->isPredicated(*BBI2T))
    1873             :       --DI2;
    1874             :   }
    1875             : 
    1876             :   // Predicate the 'false' block.
    1877          60 :   PredicateBlock(*BBI2, DI2, *Cond2);
    1878             : 
    1879             :   // Merge the true block into the entry of the diamond.
    1880          60 :   MergeBlocks(BBI, *BBI1, MergeAddEdges);
    1881          60 :   MergeBlocks(BBI, *BBI2, MergeAddEdges);
    1882             :   return true;
    1883             : }
    1884             : 
    1885             : /// If convert an almost-diamond sub-CFG where the true
    1886             : /// and false blocks share a common tail.
    1887           1 : bool IfConverter::IfConvertForkedDiamond(
    1888             :     BBInfo &BBI, IfcvtKind Kind,
    1889             :     unsigned NumDups1, unsigned NumDups2,
    1890             :     bool TClobbersPred, bool FClobbersPred) {
    1891           2 :   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
    1892           2 :   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
    1893             : 
    1894             :   // Save the debug location for later.
    1895           2 :   DebugLoc dl;
    1896           1 :   MachineBasicBlock::iterator TIE = TrueBBI.BB->getFirstTerminator();
    1897           3 :   if (TIE != TrueBBI.BB->end())
    1898           1 :     dl = TIE->getDebugLoc();
    1899             :   // Removing branches from both blocks is safe, because we have already
    1900             :   // determined that both blocks have the same branch instructions. The branch
    1901             :   // will be added back at the end, unpredicated.
    1902           1 :   if (!IfConvertDiamondCommon(
    1903             :       BBI, TrueBBI, FalseBBI,
    1904             :       NumDups1, NumDups2,
    1905             :       TClobbersPred, FClobbersPred,
    1906             :       /* RemoveBranch */ true, /* MergeAddEdges */ true))
    1907             :     return false;
    1908             : 
    1909             :   // Add back the branch.
    1910             :   // Debug location saved above when removing the branch from BBI2
    1911           3 :   TII->insertBranch(*BBI.BB, TrueBBI.TrueBB, TrueBBI.FalseBB,
    1912           1 :                     TrueBBI.BrCond, dl);
    1913             : 
    1914             :   // Update block info.
    1915           1 :   BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;
    1916           1 :   InvalidatePreds(*BBI.BB);
    1917             : 
    1918             :   // FIXME: Must maintain LiveIns.
    1919             :   return true;
    1920             : }
    1921             : 
    1922             : /// If convert a diamond sub-CFG.
    1923          60 : bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
    1924             :                                    unsigned NumDups1, unsigned NumDups2,
    1925             :                                    bool TClobbersPred, bool FClobbersPred) {
    1926         120 :   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
    1927         120 :   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
    1928          60 :   MachineBasicBlock *TailBB = TrueBBI.TrueBB;
    1929             : 
    1930             :   // True block must fall through or end with an unanalyzable terminator.
    1931          60 :   if (!TailBB) {
    1932          71 :     if (blockAlwaysFallThrough(TrueBBI))
    1933          21 :       TailBB = FalseBBI.TrueBB;
    1934             :     assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!");
    1935             :   }
    1936             : 
    1937         120 :   if (!IfConvertDiamondCommon(
    1938             :       BBI, TrueBBI, FalseBBI,
    1939             :       NumDups1, NumDups2,
    1940             :       TClobbersPred, FClobbersPred,
    1941          60 :       /* RemoveBranch */ TrueBBI.IsBrAnalyzable,
    1942             :       /* MergeAddEdges */ TailBB == nullptr))
    1943             :     return false;
    1944             : 
    1945             :   // If the if-converted block falls through or unconditionally branches into
    1946             :   // the tail block, and the tail block does not have other predecessors, then
    1947             :   // fold the tail block in as well. Otherwise, unless it falls through to the
    1948             :   // tail, add a unconditional branch to it.
    1949          59 :   if (TailBB) {
    1950             :     // We need to remove the edges to the true and false blocks manually since
    1951             :     // we didn't let IfConvertDiamondCommon update the CFG.
    1952          31 :     BBI.BB->removeSuccessor(TrueBBI.BB);
    1953          31 :     BBI.BB->removeSuccessor(FalseBBI.BB, true);
    1954             : 
    1955          62 :     BBInfo &TailBBI = BBAnalysis[TailBB->getNumber()];
    1956          46 :     bool CanMergeTail = !TailBBI.HasFallThrough &&
    1957          46 :       !TailBBI.BB->hasAddressTaken();
    1958             :     // The if-converted block can still have a predicated terminator
    1959             :     // (e.g. a predicated return). If that is the case, we cannot merge
    1960             :     // it with the tail block.
    1961          62 :     MachineBasicBlock::const_iterator TI = BBI.BB->getFirstTerminator();
    1962         124 :     if (TI != BBI.BB->end() && TII->isPredicated(*TI))
    1963             :       CanMergeTail = false;
    1964             :     // There may still be a fall-through edge from BBI1 or BBI2 to TailBB;
    1965             :     // check if there are any other predecessors besides those.
    1966          31 :     unsigned NumPreds = TailBB->pred_size();
    1967          31 :     if (NumPreds > 1)
    1968             :       CanMergeTail = false;
    1969          11 :     else if (NumPreds == 1 && CanMergeTail) {
    1970           3 :       MachineBasicBlock::pred_iterator PI = TailBB->pred_begin();
    1971           3 :       if (*PI != TrueBBI.BB && *PI != FalseBBI.BB)
    1972             :         CanMergeTail = false;
    1973             :     }
    1974          11 :     if (CanMergeTail) {
    1975           3 :       MergeBlocks(BBI, TailBBI);
    1976           3 :       TailBBI.IsDone = true;
    1977             :     } else {
    1978          56 :       BBI.BB->addSuccessor(TailBB, BranchProbability::getOne());
    1979          28 :       InsertUncondBranch(*BBI.BB, *TailBB, TII);
    1980          28 :       BBI.HasFallThrough = false;
    1981             :     }
    1982             :   }
    1983             : 
    1984             :   // Update block info.
    1985          59 :   BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;
    1986          59 :   InvalidatePreds(*BBI.BB);
    1987             : 
    1988             :   // FIXME: Must maintain LiveIns.
    1989             :   return true;
    1990             : }
    1991             : 
    1992          59 : static bool MaySpeculate(const MachineInstr &MI,
    1993             :                          SmallSet<unsigned, 4> &LaterRedefs) {
    1994          59 :   bool SawStore = true;
    1995          59 :   if (!MI.isSafeToMove(nullptr, SawStore))
    1996             :     return false;
    1997             : 
    1998          48 :   for (const MachineOperand &MO : MI.operands()) {
    1999          47 :     if (!MO.isReg())
    2000           6 :       continue;
    2001          45 :     unsigned Reg = MO.getReg();
    2002          45 :     if (!Reg)
    2003           2 :       continue;
    2004          43 :     if (MO.isDef() && !LaterRedefs.count(Reg))
    2005          41 :       return false;
    2006             :   }
    2007             : 
    2008             :   return true;
    2009             : }
    2010             : 
    2011             : /// Predicate instructions from the start of the block to the specified end with
    2012             : /// the specified condition.
    2013         590 : void IfConverter::PredicateBlock(BBInfo &BBI,
    2014             :                                  MachineBasicBlock::iterator E,
    2015             :                                  SmallVectorImpl<MachineOperand> &Cond,
    2016             :                                  SmallSet<unsigned, 4> *LaterRedefs) {
    2017         590 :   bool AnyUnpred = false;
    2018         590 :   bool MaySpec = LaterRedefs != nullptr;
    2019        4480 :   for (MachineInstr &I : make_range(BBI.BB->begin(), E)) {
    2020        1060 :     if (I.isDebugValue() || TII->isPredicated(I))
    2021           0 :       continue;
    2022             :     // It may be possible not to predicate an instruction if it's the 'true'
    2023             :     // side of a diamond and the 'false' side may re-define the instruction's
    2024             :     // defs.
    2025        1061 :     if (MaySpec && MaySpeculate(I, *LaterRedefs)) {
    2026           1 :       AnyUnpred = true;
    2027           1 :       continue;
    2028             :     }
    2029             :     // If any instruction is predicated, then every instruction after it must
    2030             :     // be predicated.
    2031        1059 :     MaySpec = false;
    2032        2118 :     if (!TII->PredicateInstruction(I, Cond)) {
    2033             : #ifndef NDEBUG
    2034             :       dbgs() << "Unable to predicate " << I << "!\n";
    2035             : #endif
    2036           0 :       llvm_unreachable(nullptr);
    2037             :     }
    2038             : 
    2039             :     // If the predicated instruction now redefines a register as the result of
    2040             :     // if-conversion, add an implicit kill.
    2041        1059 :     UpdatePredRedefs(I, Redefs);
    2042             :   }
    2043             : 
    2044        1770 :   BBI.Predicate.append(Cond.begin(), Cond.end());
    2045             : 
    2046         590 :   BBI.IsAnalyzed = false;
    2047         590 :   BBI.NonPredSize = 0;
    2048             : 
    2049         590 :   ++NumIfConvBBs;
    2050             :   if (AnyUnpred)
    2051             :     ++NumUnpred;
    2052         590 : }
    2053             : 
    2054             : /// Copy and predicate instructions from source BB to the destination block.
    2055             : /// Skip end of block branches if IgnoreBr is true.
    2056         983 : void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
    2057             :                                         SmallVectorImpl<MachineOperand> &Cond,
    2058             :                                         bool IgnoreBr) {
    2059         983 :   MachineFunction &MF = *ToBBI.BB->getParent();
    2060             : 
    2061         983 :   MachineBasicBlock &FromMBB = *FromBBI.BB;
    2062        5946 :   for (MachineInstr &I : FromMBB) {
    2063             :     // Do not copy the end of the block branches.
    2064        1014 :     if (IgnoreBr && I.isBranch())
    2065             :       break;
    2066             : 
    2067        1007 :     MachineInstr *MI = MF.CloneMachineInstr(&I);
    2068        3021 :     ToBBI.BB->insert(ToBBI.BB->end(), MI);
    2069        1007 :     ToBBI.NonPredSize++;
    2070        1007 :     unsigned ExtraPredCost = TII->getPredicationCost(I);
    2071        1007 :     unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
    2072        1007 :     if (NumCycles > 1)
    2073           8 :       ToBBI.ExtraCost += NumCycles-1;
    2074        1007 :     ToBBI.ExtraCost2 += ExtraPredCost;
    2075             : 
    2076        2011 :     if (!TII->isPredicated(I) && !MI->isDebugValue()) {
    2077        2008 :       if (!TII->PredicateInstruction(*MI, Cond)) {
    2078             : #ifndef NDEBUG
    2079             :         dbgs() << "Unable to predicate " << I << "!\n";
    2080             : #endif
    2081           0 :         llvm_unreachable(nullptr);
    2082             :       }
    2083             :     }
    2084             : 
    2085             :     // If the predicated instruction now redefines a register as the result of
    2086             :     // if-conversion, add an implicit kill.
    2087        1007 :     UpdatePredRedefs(*MI, Redefs);
    2088             : 
    2089             :     // Some kill flags may not be correct anymore.
    2090        2014 :     if (!DontKill.empty())
    2091         999 :       RemoveKills(*MI, DontKill);
    2092             :   }
    2093             : 
    2094         983 :   if (!IgnoreBr) {
    2095             :     std::vector<MachineBasicBlock *> Succs(FromMBB.succ_begin(),
    2096        5874 :                                            FromMBB.succ_end());
    2097         979 :     MachineBasicBlock *NBB = getNextBlock(FromMBB);
    2098         979 :     MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr;
    2099             : 
    2100        3916 :     for (MachineBasicBlock *Succ : Succs) {
    2101             :       // Fallthrough edge can't be transferred.
    2102           0 :       if (Succ == FallThrough)
    2103           0 :         continue;
    2104           0 :       ToBBI.BB->addSuccessor(Succ);
    2105             :     }
    2106             :   }
    2107             : 
    2108        2949 :   ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
    2109        2949 :   ToBBI.Predicate.append(Cond.begin(), Cond.end());
    2110             : 
    2111         983 :   ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
    2112         983 :   ToBBI.IsAnalyzed = false;
    2113             : 
    2114         983 :   ++NumDupBBs;
    2115         983 : }
    2116             : 
    2117             : /// Move all instructions from FromBB to the end of ToBB.  This will leave
    2118             : /// FromBB as an empty block, so remove all of its successor edges except for
    2119             : /// the fall-through edge.  If AddEdges is true, i.e., when FromBBI's branch is
    2120             : /// being moved, add those successor edges to ToBBI and remove the old edge
    2121             : /// from ToBBI to FromBBI.
    2122         593 : void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
    2123         593 :   MachineBasicBlock &FromMBB = *FromBBI.BB;
    2124             :   assert(!FromMBB.hasAddressTaken() &&
    2125             :          "Removing a BB whose address is taken!");
    2126             : 
    2127             :   // In case FromMBB contains terminators (e.g. return instruction),
    2128             :   // first move the non-terminator instructions, then the terminators.
    2129         593 :   MachineBasicBlock::iterator FromTI = FromMBB.getFirstTerminator();
    2130         593 :   MachineBasicBlock::iterator ToTI = ToBBI.BB->getFirstTerminator();
    2131        1779 :   ToBBI.BB->splice(ToTI, &FromMBB, FromMBB.begin(), FromTI);
    2132             : 
    2133             :   // If FromBB has non-predicated terminator we should copy it at the end.
    2134        1527 :   if (FromTI != FromMBB.end() && !TII->isPredicated(*FromTI))
    2135         250 :     ToTI = ToBBI.BB->end();
    2136        1779 :   ToBBI.BB->splice(ToTI, &FromMBB, FromTI, FromMBB.end());
    2137             : 
    2138             :   // Force normalizing the successors' probabilities of ToBBI.BB to convert all
    2139             :   // unknown probabilities into known ones.
    2140             :   // FIXME: This usage is too tricky and in the future we would like to
    2141             :   // eliminate all unknown probabilities in MBB.
    2142         593 :   if (ToBBI.IsBrAnalyzable)
    2143         593 :     ToBBI.BB->normalizeSuccProbs();
    2144             : 
    2145             :   SmallVector<MachineBasicBlock *, 4> FromSuccs(FromMBB.succ_begin(),
    2146        2372 :                                                 FromMBB.succ_end());
    2147         593 :   MachineBasicBlock *NBB = getNextBlock(FromMBB);
    2148         593 :   MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr;
    2149             :   // The edge probability from ToBBI.BB to FromMBB, which is only needed when
    2150             :   // AddEdges is true and FromMBB is a successor of ToBBI.BB.
    2151         593 :   auto To2FromProb = BranchProbability::getZero();
    2152         593 :   if (AddEdges && ToBBI.BB->isSuccessor(&FromMBB)) {
    2153             :     // Remove the old edge but remember the edge probability so we can calculate
    2154             :     // the correct weights on the new edges being added further down.
    2155         367 :     To2FromProb = MBPI->getEdgeProbability(ToBBI.BB, &FromMBB);
    2156         367 :     ToBBI.BB->removeSuccessor(&FromMBB);
    2157             :   }
    2158             : 
    2159        2052 :   for (MachineBasicBlock *Succ : FromSuccs) {
    2160             :     // Fallthrough edge can't be transferred.
    2161         273 :     if (Succ == FallThrough)
    2162         171 :       continue;
    2163             : 
    2164         102 :     auto NewProb = BranchProbability::getZero();
    2165         102 :     if (AddEdges) {
    2166             :       // Calculate the edge probability for the edge from ToBBI.BB to Succ,
    2167             :       // which is a portion of the edge probability from FromMBB to Succ. The
    2168             :       // portion ratio is the edge probability from ToBBI.BB to FromMBB (if
    2169             :       // FromBBI is a successor of ToBBI.BB. See comment below for excepion).
    2170          29 :       NewProb = MBPI->getEdgeProbability(&FromMBB, Succ);
    2171             : 
    2172             :       // To2FromProb is 0 when FromMBB is not a successor of ToBBI.BB. This
    2173             :       // only happens when if-converting a diamond CFG and FromMBB is the
    2174             :       // tail BB.  In this case FromMBB post-dominates ToBBI.BB and hence we
    2175             :       // could just use the probabilities on FromMBB's out-edges when adding
    2176             :       // new successors.
    2177          29 :       if (!To2FromProb.isZero())
    2178             :         NewProb *= To2FromProb;
    2179             :     }
    2180             : 
    2181         102 :     FromMBB.removeSuccessor(Succ);
    2182             : 
    2183         102 :     if (AddEdges) {
    2184             :       // If the edge from ToBBI.BB to Succ already exists, update the
    2185             :       // probability of this edge by adding NewProb to it. An example is shown
    2186             :       // below, in which A is ToBBI.BB and B is FromMBB. In this case we
    2187             :       // don't have to set C as A's successor as it already is. We only need to
    2188             :       // update the edge probability on A->C. Note that B will not be
    2189             :       // immediately removed from A's successors. It is possible that B->D is
    2190             :       // not removed either if D is a fallthrough of B. Later the edge A->D
    2191             :       // (generated here) and B->D will be combined into one edge. To maintain
    2192             :       // correct edge probability of this combined edge, we need to set the edge
    2193             :       // probability of A->B to zero, which is already done above. The edge
    2194             :       // probability on A->D is calculated by scaling the original probability
    2195             :       // on A->B by the probability of B->D.
    2196             :       //
    2197             :       // Before ifcvt:      After ifcvt (assume B->D is kept):
    2198             :       //
    2199             :       //       A                A
    2200             :       //      /|               /|\
    2201             :       //     / B              / B|
    2202             :       //    | /|             |  ||
    2203             :       //    |/ |             |  |/
    2204             :       //    C  D             C  D
    2205             :       //
    2206          29 :       if (ToBBI.BB->isSuccessor(Succ))
    2207           9 :         ToBBI.BB->setSuccProbability(
    2208           6 :             find(ToBBI.BB->successors(), Succ),
    2209           6 :             MBPI->getEdgeProbability(ToBBI.BB, Succ) + NewProb);
    2210             :       else
    2211          26 :         ToBBI.BB->addSuccessor(Succ, NewProb);
    2212             :     }
    2213             :   }
    2214             : 
    2215             :   // Move the now empty FromMBB out of the way to the end of the function so
    2216             :   // it doesn't interfere with fallthrough checks done by canFallThroughTo().
    2217        1779 :   MachineBasicBlock *Last = &*FromMBB.getParent()->rbegin();
    2218         593 :   if (Last != &FromMBB)
    2219         390 :     FromMBB.moveAfter(Last);
    2220             : 
    2221             :   // Normalize the probabilities of ToBBI.BB's successors with all adjustment
    2222             :   // we've done above.
    2223         593 :   if (ToBBI.IsBrAnalyzable && FromBBI.IsBrAnalyzable)
    2224         226 :     ToBBI.BB->normalizeSuccProbs();
    2225             : 
    2226        1779 :   ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
    2227        1186 :   FromBBI.Predicate.clear();
    2228             : 
    2229         593 :   ToBBI.NonPredSize += FromBBI.NonPredSize;
    2230         593 :   ToBBI.ExtraCost += FromBBI.ExtraCost;
    2231         593 :   ToBBI.ExtraCost2 += FromBBI.ExtraCost2;
    2232         593 :   FromBBI.NonPredSize = 0;
    2233         593 :   FromBBI.ExtraCost = 0;
    2234         593 :   FromBBI.ExtraCost2 = 0;
    2235             : 
    2236         593 :   ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
    2237         593 :   ToBBI.HasFallThrough = FromBBI.HasFallThrough;
    2238         593 :   ToBBI.IsAnalyzed = false;
    2239         593 :   FromBBI.IsAnalyzed = false;
    2240         593 : }
    2241             : 
    2242             : FunctionPass *
    2243        2322 : llvm::createIfConverter(std::function<bool(const MachineFunction &)> Ftor) {
    2244        6966 :   return new IfConverter(std::move(Ftor));
    2245      216918 : }

Generated by: LCOV version 1.13