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

Generated by: LCOV version 1.13