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

Generated by: LCOV version 1.13