lib/CodeGen/IfConversion.cpp

   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.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "ifcvt"
  15 #include "llvm/CodeGen/Passes.h"
  16 #include "BranchFolding.h"
  17 #include "llvm/ADT/STLExtras.h"
  18 #include "llvm/ADT/SmallSet.h"
  19 #include "llvm/ADT/Statistic.h"
  20 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
  21 #include "llvm/CodeGen/MachineFunctionPass.h"
  22 #include "llvm/CodeGen/MachineInstrBuilder.h"
  23 #include "llvm/CodeGen/MachineModuleInfo.h"
  24 #include "llvm/CodeGen/MachineRegisterInfo.h"
  25 #include "llvm/MC/MCInstrItineraries.h"
  26 #include "llvm/Support/CommandLine.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/ErrorHandling.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 #include "llvm/Target/TargetInstrInfo.h"
  31 #include "llvm/Target/TargetLowering.h"
  32 #include "llvm/Target/TargetMachine.h"
  33 #include "llvm/Target/TargetRegisterInfo.h"
  34 using namespace llvm;
  35
  36 // Hidden options for help debugging.
  37 static cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden);
  38 static cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden);
  39 static cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden);
  40 static cl::opt<bool> DisableSimple("disable-ifcvt-simple",
  41                                    cl::init(false), cl::Hidden);
  42 static cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false",
  43                                     cl::init(false), cl::Hidden);
  44 static cl::opt<bool> DisableTriangle("disable-ifcvt-triangle",
  45                                      cl::init(false), cl::Hidden);
  46 static cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev",
  47                                       cl::init(false), cl::Hidden);
  48 static cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false",
  49                                       cl::init(false), cl::Hidden);
  50 static cl::opt<bool> DisableTriangleFR("disable-ifcvt-triangle-false-rev",
  51                                        cl::init(false), cl::Hidden);
  52 static cl::opt<bool> DisableDiamond("disable-ifcvt-diamond",
  53                                     cl::init(false), cl::Hidden);
  54 static cl::opt<bool> IfCvtBranchFold("ifcvt-branch-fold",
  55                                      cl::init(true), cl::Hidden);
  56
  57 STATISTIC(NumSimple,       "Number of simple if-conversions performed");
  58 STATISTIC(NumSimpleFalse,  "Number of simple (F) if-conversions performed");
  59 STATISTIC(NumTriangle,     "Number of triangle if-conversions performed");
  60 STATISTIC(NumTriangleRev,  "Number of triangle (R) if-conversions performed");
  61 STATISTIC(NumTriangleFalse,"Number of triangle (F) if-conversions performed");
  62 STATISTIC(NumTriangleFRev, "Number of triangle (F/R) if-conversions performed");
  63 STATISTIC(NumDiamonds,     "Number of diamond if-conversions performed");
  64 STATISTIC(NumIfConvBBs,    "Number of if-converted blocks");
  65 STATISTIC(NumDupBBs,       "Number of duplicated blocks");
  66 STATISTIC(NumUnpred,       "Number of true blocks of diamonds unpredicated");
  67
  68 namespace {
  69   class IfConverter : public MachineFunctionPass {
  70     enum IfcvtKind {
  71       ICNotClassfied,  // BB data valid, but not classified.
  72       ICSimpleFalse,   // Same as ICSimple, but on the false path.
  73       ICSimple,        // BB is entry of an one split, no rejoin sub-CFG.
  74       ICTriangleFRev,  // Same as ICTriangleFalse, but false path rev condition.
  75       ICTriangleRev,   // Same as ICTriangle, but true path rev condition.
  76       ICTriangleFalse, // Same as ICTriangle, but on the false path.
  77       ICTriangle,      // BB is entry of a triangle sub-CFG.
  78       ICDiamond        // BB is entry of a diamond sub-CFG.
  79     };
  80
  81     /// BBInfo - One per MachineBasicBlock, this is used to cache the result
  82     /// if-conversion feasibility analysis. This includes results from
  83     /// TargetInstrInfo::AnalyzeBranch() (i.e. TBB, FBB, and Cond), and its
  84     /// classification, and common tail block of its successors (if it's a
  85     /// diamond shape), its size, whether it's predicable, and whether any
  86     /// instruction can clobber the 'would-be' predicate.
  87     ///
  88     /// IsDone          - True if BB is not to be considered for ifcvt.
  89     /// IsBeingAnalyzed - True if BB is currently being analyzed.
  90     /// IsAnalyzed      - True if BB has been analyzed (info is still valid).
  91     /// IsEnqueued      - True if BB has been enqueued to be ifcvt'ed.
  92     /// IsBrAnalyzable  - True if AnalyzeBranch() returns false.
  93     /// HasFallThrough  - True if BB may fallthrough to the following BB.
  94     /// IsUnpredicable  - True if BB is known to be unpredicable.
  95     /// ClobbersPred    - True if BB could modify predicates (e.g. has
  96     ///                   cmp, call, etc.)
  97     /// NonPredSize     - Number of non-predicated instructions.
  98     /// ExtraCost       - Extra cost for multi-cycle instructions.
  99     /// ExtraCost2      - Some instructions are slower when predicated
 100     /// BB              - Corresponding MachineBasicBlock.
 101     /// TrueBB / FalseBB- See AnalyzeBranch().
 102     /// BrCond          - Conditions for end of block conditional branches.
 103     /// Predicate       - Predicate used in the BB.
 104     struct BBInfo {
 105       bool IsDone          : 1;
 106       bool IsBeingAnalyzed : 1;
 107       bool IsAnalyzed      : 1;
 108       bool IsEnqueued      : 1;
 109       bool IsBrAnalyzable  : 1;
 110       bool HasFallThrough  : 1;
 111       bool IsUnpredicable  : 1;
 112       bool CannotBeCopied  : 1;
 113       bool ClobbersPred    : 1;
 114       unsigned NonPredSize;
 115       unsigned ExtraCost;
 116       unsigned ExtraCost2;
 117       MachineBasicBlock *BB;
 118       MachineBasicBlock *TrueBB;
 119       MachineBasicBlock *FalseBB;
 120       SmallVector<MachineOperand, 4> BrCond;
 121       SmallVector<MachineOperand, 4> Predicate;
 122       BBInfo() : IsDone(false), IsBeingAnalyzed(false),
 123                  IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false),
 124                  HasFallThrough(false), IsUnpredicable(false),
 125                  CannotBeCopied(false), ClobbersPred(false), NonPredSize(0),
 126                  ExtraCost(0), ExtraCost2(0), BB(0), TrueBB(0), FalseBB(0) {}
 127     };
 128
 129     /// IfcvtToken - Record information about pending if-conversions to attempt:
 130     /// BBI             - Corresponding BBInfo.
 131     /// Kind            - Type of block. See IfcvtKind.
 132     /// NeedSubsumption - True if the to-be-predicated BB has already been
 133     ///                   predicated.
 134     /// NumDups      - Number of instructions that would be duplicated due
 135     ///                   to this if-conversion. (For diamonds, the number of
 136     ///                   identical instructions at the beginnings of both
 137     ///                   paths).
 138     /// NumDups2     - For diamonds, the number of identical instructions
 139     ///                   at the ends of both paths.
 140     struct IfcvtToken {
 141       BBInfo &BBI;
 142       IfcvtKind Kind;
 143       bool NeedSubsumption;
 144       unsigned NumDups;
 145       unsigned NumDups2;
 146       IfcvtToken(BBInfo &b, IfcvtKind k, bool s, unsigned d, unsigned d2 = 0)
 147         : BBI(b), Kind(k), NeedSubsumption(s), NumDups(d), NumDups2(d2) {}
 148     };
 149
 150     /// BBAnalysis - Results of if-conversion feasibility analysis indexed by
 151     /// basic block number.
 152     std::vector<BBInfo> BBAnalysis;
 153
 154     const TargetLoweringBase *TLI;
 155     const TargetInstrInfo *TII;
 156     const TargetRegisterInfo *TRI;
 157     const InstrItineraryData *InstrItins;
 158     const MachineBranchProbabilityInfo *MBPI;
 159     MachineRegisterInfo *MRI;
 160
 161     bool PreRegAlloc;
 162     bool MadeChange;
 163     int FnNum;
 164   public:
 165     static char ID;
 166     IfConverter() : MachineFunctionPass(ID), FnNum(-1) {
 167       initializeIfConverterPass(*PassRegistry::getPassRegistry());
 168     }
 169
 170     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 171       AU.addRequired<MachineBranchProbabilityInfo>();
 172       MachineFunctionPass::getAnalysisUsage(AU);
 173     }
 174
 175     virtual bool runOnMachineFunction(MachineFunction &MF);
 176
 177   private:
 178     bool ReverseBranchCondition(BBInfo &BBI);
 179     bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups,
 180                      const BranchProbability &Prediction) const;
 181     bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
 182                        bool FalseBranch, unsigned &Dups,
 183                        const BranchProbability &Prediction) const;
 184     bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
 185                       unsigned &Dups1, unsigned &Dups2) const;
 186     void ScanInstructions(BBInfo &BBI);
 187     BBInfo &AnalyzeBlock(MachineBasicBlock *BB,
 188                          std::vector<IfcvtToken*> &Tokens);
 189     bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Cond,
 190                              bool isTriangle = false, bool RevBranch = false);
 191     void AnalyzeBlocks(MachineFunction &MF, std::vector<IfcvtToken*> &Tokens);
 192     void InvalidatePreds(MachineBasicBlock *BB);
 193     void RemoveExtraEdges(BBInfo &BBI);
 194     bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind);
 195     bool IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind);
 196     bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
 197                           unsigned NumDups1, unsigned NumDups2);
 198     void PredicateBlock(BBInfo &BBI,
 199                         MachineBasicBlock::iterator E,
 200                         SmallVectorImpl<MachineOperand> &Cond,
 201                         SmallSet<unsigned, 4> &Redefs,
 202                         SmallSet<unsigned, 4> *LaterRedefs = 0);
 203     void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
 204                                SmallVectorImpl<MachineOperand> &Cond,
 205                                SmallSet<unsigned, 4> &Redefs,
 206                                bool IgnoreBr = false);
 207     void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges = true);
 208
 209     bool MeetIfcvtSizeLimit(MachineBasicBlock &BB,
 210                             unsigned Cycle, unsigned Extra,
 211                             const BranchProbability &Prediction) const {
 212       return Cycle > 0 && TII->isProfitableToIfCvt(BB, Cycle, Extra,
 213                                                    Prediction);
 214     }
 215
 216     bool MeetIfcvtSizeLimit(MachineBasicBlock &TBB,
 217                             unsigned TCycle, unsigned TExtra,
 218                             MachineBasicBlock &FBB,
 219                             unsigned FCycle, unsigned FExtra,
 220                             const BranchProbability &Prediction) const {
 221       return TCycle > 0 && FCycle > 0 &&
 222         TII->isProfitableToIfCvt(TBB, TCycle, TExtra, FBB, FCycle, FExtra,
 223                                  Prediction);
 224     }
 225
 226     // blockAlwaysFallThrough - Block ends without a terminator.
 227     bool blockAlwaysFallThrough(BBInfo &BBI) const {
 228       return BBI.IsBrAnalyzable && BBI.TrueBB == NULL;
 229     }
 230
 231     // IfcvtTokenCmp - Used to sort if-conversion candidates.
 232     static bool IfcvtTokenCmp(IfcvtToken *C1, IfcvtToken *C2) {
 233       int Incr1 = (C1->Kind == ICDiamond)
 234         ? -(int)(C1->NumDups + C1->NumDups2) : (int)C1->NumDups;
 235       int Incr2 = (C2->Kind == ICDiamond)
 236         ? -(int)(C2->NumDups + C2->NumDups2) : (int)C2->NumDups;
 237       if (Incr1 > Incr2)
 238         return true;
 239       else if (Incr1 == Incr2) {
 240         // Favors subsumption.
 241         if (C1->NeedSubsumption == false && C2->NeedSubsumption == true)
 242           return true;
 243         else if (C1->NeedSubsumption == C2->NeedSubsumption) {
 244           // Favors diamond over triangle, etc.
 245           if ((unsigned)C1->Kind < (unsigned)C2->Kind)
 246             return true;
 247           else if (C1->Kind == C2->Kind)
 248             return C1->BBI.BB->getNumber() < C2->BBI.BB->getNumber();
 249         }
 250       }
 251       return false;
 252     }
 253   };
 254
 255   char IfConverter::ID = 0;
 256 }
 257
 258 char &llvm::IfConverterID = IfConverter::ID;
 259
 260 INITIALIZE_PASS_BEGIN(IfConverter, "if-converter", "If Converter", false, false)
 261 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 262 INITIALIZE_PASS_END(IfConverter, "if-converter", "If Converter", false, false)
 263
 264 bool IfConverter::runOnMachineFunction(MachineFunction &MF) {
 265   TLI = MF.getTarget().getTargetLowering();
 266   TII = MF.getTarget().getInstrInfo();
 267   TRI = MF.getTarget().getRegisterInfo();
 268   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
 269   MRI = &MF.getRegInfo();
 270   InstrItins = MF.getTarget().getInstrItineraryData();
 271   if (!TII) return false;
 272
 273   PreRegAlloc = MRI->isSSA();
 274
 275   bool BFChange = false;
 276   if (!PreRegAlloc) {
 277     // Tail merge tend to expose more if-conversion opportunities.
 278     BranchFolder BF(true, false);
 279     BFChange = BF.OptimizeFunction(MF, TII,
 280                                    MF.getTarget().getRegisterInfo(),
 281                                    getAnalysisIfAvailable<MachineModuleInfo>());
 282   }
 283
 284   DEBUG(dbgs() << "\nIfcvt: function (" << ++FnNum <<  ") \'"
 285                << MF.getName() << "\'");
 286
 287   if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) {
 288     DEBUG(dbgs() << " skipped\n");
 289     return false;
 290   }
 291   DEBUG(dbgs() << "\n");
 292
 293   MF.RenumberBlocks();
 294   BBAnalysis.resize(MF.getNumBlockIDs());
 295
 296   std::vector<IfcvtToken*> Tokens;
 297   MadeChange = false;
 298   unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle +
 299     NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds;
 300   while (IfCvtLimit == -1 || (int)NumIfCvts < IfCvtLimit) {
 301     // Do an initial analysis for each basic block and find all the potential
 302     // candidates to perform if-conversion.
 303     bool Change = false;
 304     AnalyzeBlocks(MF, Tokens);
 305     while (!Tokens.empty()) {
 306       IfcvtToken *Token = Tokens.back();
 307       Tokens.pop_back();
 308       BBInfo &BBI = Token->BBI;
 309       IfcvtKind Kind = Token->Kind;
 310       unsigned NumDups = Token->NumDups;
 311       unsigned NumDups2 = Token->NumDups2;
 312
 313       delete Token;
 314
 315       // If the block has been evicted out of the queue or it has already been
 316       // marked dead (due to it being predicated), then skip it.
 317       if (BBI.IsDone)
 318         BBI.IsEnqueued = false;
 319       if (!BBI.IsEnqueued)
 320         continue;
 321
 322       BBI.IsEnqueued = false;
 323
 324       bool RetVal = false;
 325       switch (Kind) {
 326       default: llvm_unreachable("Unexpected!");
 327       case ICSimple:
 328       case ICSimpleFalse: {
 329         bool isFalse = Kind == ICSimpleFalse;
 330         if ((isFalse && DisableSimpleF) || (!isFalse && DisableSimple)) break;
 331         DEBUG(dbgs() << "Ifcvt (Simple" << (Kind == ICSimpleFalse ?
 332                                             " false" : "")
 333                      << "): BB#" << BBI.BB->getNumber() << " ("
 334                      << ((Kind == ICSimpleFalse)
 335                          ? BBI.FalseBB->getNumber()
 336                          : BBI.TrueBB->getNumber()) << ") ");
 337         RetVal = IfConvertSimple(BBI, Kind);
 338         DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
 339         if (RetVal) {
 340           if (isFalse) ++NumSimpleFalse;
 341           else         ++NumSimple;
 342         }
 343        break;
 344       }
 345       case ICTriangle:
 346       case ICTriangleRev:
 347       case ICTriangleFalse:
 348       case ICTriangleFRev: {
 349         bool isFalse = Kind == ICTriangleFalse;
 350         bool isRev   = (Kind == ICTriangleRev || Kind == ICTriangleFRev);
 351         if (DisableTriangle && !isFalse && !isRev) break;
 352         if (DisableTriangleR && !isFalse && isRev) break;
 353         if (DisableTriangleF && isFalse && !isRev) break;
 354         if (DisableTriangleFR && isFalse && isRev) break;
 355         DEBUG(dbgs() << "Ifcvt (Triangle");
 356         if (isFalse)
 357           DEBUG(dbgs() << " false");
 358         if (isRev)
 359           DEBUG(dbgs() << " rev");
 360         DEBUG(dbgs() << "): BB#" << BBI.BB->getNumber() << " (T:"
 361                      << BBI.TrueBB->getNumber() << ",F:"
 362                      << BBI.FalseBB->getNumber() << ") ");
 363         RetVal = IfConvertTriangle(BBI, Kind);
 364         DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
 365         if (RetVal) {
 366           if (isFalse) {
 367             if (isRev) ++NumTriangleFRev;
 368             else       ++NumTriangleFalse;
 369           } else {
 370             if (isRev) ++NumTriangleRev;
 371             else       ++NumTriangle;
 372           }
 373         }
 374         break;
 375       }
 376       case ICDiamond: {
 377         if (DisableDiamond) break;
 378         DEBUG(dbgs() << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:"
 379                      << BBI.TrueBB->getNumber() << ",F:"
 380                      << BBI.FalseBB->getNumber() << ") ");
 381         RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2);
 382         DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
 383         if (RetVal) ++NumDiamonds;
 384         break;
 385       }
 386       }
 387
 388       Change |= RetVal;
 389
 390       NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev +
 391         NumTriangleFalse + NumTriangleFRev + NumDiamonds;
 392       if (IfCvtLimit != -1 && (int)NumIfCvts >= IfCvtLimit)
 393         break;
 394     }
 395
 396     if (!Change)
 397       break;
 398     MadeChange |= Change;
 399   }
 400
 401   // Delete tokens in case of early exit.
 402   while (!Tokens.empty()) {
 403     IfcvtToken *Token = Tokens.back();
 404     Tokens.pop_back();
 405     delete Token;
 406   }
 407
 408   Tokens.clear();
 409   BBAnalysis.clear();
 410
 411   if (MadeChange && IfCvtBranchFold) {
 412     BranchFolder BF(false, false);
 413     BF.OptimizeFunction(MF, TII,
 414                         MF.getTarget().getRegisterInfo(),
 415                         getAnalysisIfAvailable<MachineModuleInfo>());
 416   }
 417
 418   MadeChange |= BFChange;
 419   return MadeChange;
 420 }
 421
 422 /// findFalseBlock - BB has a fallthrough. Find its 'false' successor given
 423 /// its 'true' successor.
 424 static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
 425                                          MachineBasicBlock *TrueBB) {
 426   for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
 427          E = BB->succ_end(); SI != E; ++SI) {
 428     MachineBasicBlock *SuccBB = *SI;
 429     if (SuccBB != TrueBB)
 430       return SuccBB;
 431   }
 432   return NULL;
 433 }
 434
 435 /// ReverseBranchCondition - Reverse the condition of the end of the block
 436 /// branch. Swap block's 'true' and 'false' successors.
 437 bool IfConverter::ReverseBranchCondition(BBInfo &BBI) {
 438   DebugLoc dl;  // FIXME: this is nowhere
 439   if (!TII->ReverseBranchCondition(BBI.BrCond)) {
 440     TII->RemoveBranch(*BBI.BB);
 441     TII->InsertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond, dl);
 442     std::swap(BBI.TrueBB, BBI.FalseBB);
 443     return true;
 444   }
 445   return false;
 446 }
 447
 448 /// getNextBlock - Returns the next block in the function blocks ordering. If
 449 /// it is the end, returns NULL.
 450 static inline MachineBasicBlock *getNextBlock(MachineBasicBlock *BB) {
 451   MachineFunction::iterator I = BB;
 452   MachineFunction::iterator E = BB->getParent()->end();
 453   if (++I == E)
 454     return NULL;
 455   return I;
 456 }
 457
 458 /// ValidSimple - Returns true if the 'true' block (along with its
 459 /// predecessor) forms a valid simple shape for ifcvt. It also returns the
 460 /// number of instructions that the ifcvt would need to duplicate if performed
 461 /// in Dups.
 462 bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups,
 463                               const BranchProbability &Prediction) const {
 464   Dups = 0;
 465   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
 466     return false;
 467
 468   if (TrueBBI.IsBrAnalyzable)
 469     return false;
 470
 471   if (TrueBBI.BB->pred_size() > 1) {
 472     if (TrueBBI.CannotBeCopied ||
 473         !TII->isProfitableToDupForIfCvt(*TrueBBI.BB, TrueBBI.NonPredSize,
 474                                         Prediction))
 475       return false;
 476     Dups = TrueBBI.NonPredSize;
 477   }
 478
 479   return true;
 480 }
 481
 482 /// ValidTriangle - Returns true if the 'true' and 'false' blocks (along
 483 /// with their common predecessor) forms a valid triangle shape for ifcvt.
 484 /// If 'FalseBranch' is true, it checks if 'true' block's false branch
 485 /// branches to the 'false' block rather than the other way around. It also
 486 /// returns the number of instructions that the ifcvt would need to duplicate
 487 /// if performed in 'Dups'.
 488 bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
 489                                 bool FalseBranch, unsigned &Dups,
 490                                 const BranchProbability &Prediction) const {
 491   Dups = 0;
 492   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
 493     return false;
 494
 495   if (TrueBBI.BB->pred_size() > 1) {
 496     if (TrueBBI.CannotBeCopied)
 497       return false;
 498
 499     unsigned Size = TrueBBI.NonPredSize;
 500     if (TrueBBI.IsBrAnalyzable) {
 501       if (TrueBBI.TrueBB && TrueBBI.BrCond.empty())
 502         // Ends with an unconditional branch. It will be removed.
 503         --Size;
 504       else {
 505         MachineBasicBlock *FExit = FalseBranch
 506           ? TrueBBI.TrueBB : TrueBBI.FalseBB;
 507         if (FExit)
 508           // Require a conditional branch
 509           ++Size;
 510       }
 511     }
 512     if (!TII->isProfitableToDupForIfCvt(*TrueBBI.BB, Size, Prediction))
 513       return false;
 514     Dups = Size;
 515   }
 516
 517   MachineBasicBlock *TExit = FalseBranch ? TrueBBI.FalseBB : TrueBBI.TrueBB;
 518   if (!TExit && blockAlwaysFallThrough(TrueBBI)) {
 519     MachineFunction::iterator I = TrueBBI.BB;
 520     if (++I == TrueBBI.BB->getParent()->end())
 521       return false;
 522     TExit = I;
 523   }
 524   return TExit && TExit == FalseBBI.BB;
 525 }
 526
 527 /// ValidDiamond - Returns true if the 'true' and 'false' blocks (along
 528 /// with their common predecessor) forms a valid diamond shape for ifcvt.
 529 bool IfConverter::ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
 530                                unsigned &Dups1, unsigned &Dups2) const {
 531   Dups1 = Dups2 = 0;
 532   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||
 533       FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)
 534     return false;
 535
 536   MachineBasicBlock *TT = TrueBBI.TrueBB;
 537   MachineBasicBlock *FT = FalseBBI.TrueBB;
 538
 539   if (!TT && blockAlwaysFallThrough(TrueBBI))
 540     TT = getNextBlock(TrueBBI.BB);
 541   if (!FT && blockAlwaysFallThrough(FalseBBI))
 542     FT = getNextBlock(FalseBBI.BB);
 543   if (TT != FT)
 544     return false;
 545   if (TT == NULL && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))
 546     return false;
 547   if  (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
 548     return false;
 549
 550   // FIXME: Allow true block to have an early exit?
 551   if (TrueBBI.FalseBB || FalseBBI.FalseBB ||
 552       (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred))
 553     return false;
 554
 555   // Count duplicate instructions at the beginning of the true and false blocks.
 556   MachineBasicBlock::iterator TIB = TrueBBI.BB->begin();
 557   MachineBasicBlock::iterator FIB = FalseBBI.BB->begin();
 558   MachineBasicBlock::iterator TIE = TrueBBI.BB->end();
 559   MachineBasicBlock::iterator FIE = FalseBBI.BB->end();
 560   while (TIB != TIE && FIB != FIE) {
 561     // Skip dbg_value instructions. These do not count.
 562     if (TIB->isDebugValue()) {
 563       while (TIB != TIE && TIB->isDebugValue())
 564         ++TIB;
 565       if (TIB == TIE)
 566         break;
 567     }
 568     if (FIB->isDebugValue()) {
 569       while (FIB != FIE && FIB->isDebugValue())
 570         ++FIB;
 571       if (FIB == FIE)
 572         break;
 573     }
 574     if (!TIB->isIdenticalTo(FIB))
 575       break;
 576     ++Dups1;
 577     ++TIB;
 578     ++FIB;
 579   }
 580
 581   // Now, in preparation for counting duplicate instructions at the ends of the
 582   // blocks, move the end iterators up past any branch instructions.
 583   while (TIE != TIB) {
 584     --TIE;
 585     if (!TIE->isBranch())
 586       break;
 587   }
 588   while (FIE != FIB) {
 589     --FIE;
 590     if (!FIE->isBranch())
 591       break;
 592   }
 593
 594   // If Dups1 includes all of a block, then don't count duplicate
 595   // instructions at the end of the blocks.
 596   if (TIB == TIE || FIB == FIE)
 597     return true;
 598
 599   // Count duplicate instructions at the ends of the blocks.
 600   while (TIE != TIB && FIE != FIB) {
 601     // Skip dbg_value instructions. These do not count.
 602     if (TIE->isDebugValue()) {
 603       while (TIE != TIB && TIE->isDebugValue())
 604         --TIE;
 605       if (TIE == TIB)
 606         break;
 607     }
 608     if (FIE->isDebugValue()) {
 609       while (FIE != FIB && FIE->isDebugValue())
 610         --FIE;
 611       if (FIE == FIB)
 612         break;
 613     }
 614     if (!TIE->isIdenticalTo(FIE))
 615       break;
 616     ++Dups2;
 617     --TIE;
 618     --FIE;
 619   }
 620
 621   return true;
 622 }
 623
 624 /// ScanInstructions - Scan all the instructions in the block to determine if
 625 /// the block is predicable. In most cases, that means all the instructions
 626 /// in the block are isPredicable(). Also checks if the block contains any
 627 /// instruction which can clobber a predicate (e.g. condition code register).
 628 /// If so, the block is not predicable unless it's the last instruction.
 629 void IfConverter::ScanInstructions(BBInfo &BBI) {
 630   if (BBI.IsDone)
 631     return;
 632
 633   bool AlreadyPredicated = !BBI.Predicate.empty();
 634   // First analyze the end of BB branches.
 635   BBI.TrueBB = BBI.FalseBB = NULL;
 636   BBI.BrCond.clear();
 637   BBI.IsBrAnalyzable =
 638     !TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);
 639   BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB == NULL;
 640
 641   if (BBI.BrCond.size()) {
 642     // No false branch. This BB must end with a conditional branch and a
 643     // fallthrough.
 644     if (!BBI.FalseBB)
 645       BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB);
 646     if (!BBI.FalseBB) {
 647       // Malformed bcc? True and false blocks are the same?
 648       BBI.IsUnpredicable = true;
 649       return;
 650     }
 651   }
 652
 653   // Then scan all the instructions.
 654   BBI.NonPredSize = 0;
 655   BBI.ExtraCost = 0;
 656   BBI.ExtraCost2 = 0;
 657   BBI.ClobbersPred = false;
 658   for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end();
 659        I != E; ++I) {
 660     if (I->isDebugValue())
 661       continue;
 662
 663     if (I->isNotDuplicable())
 664       BBI.CannotBeCopied = true;
 665
 666     bool isPredicated = TII->isPredicated(I);
 667     bool isCondBr = BBI.IsBrAnalyzable && I->isConditionalBranch();
 668
 669     // A conditional branch is not predicable, but it may be eliminated.
 670     if (isCondBr)
 671       continue;
 672
 673     if (!isPredicated) {
 674       BBI.NonPredSize++;
 675       unsigned ExtraPredCost = 0;
 676       unsigned NumCycles = TII->getInstrLatency(InstrItins, &*I,
 677                                                 &ExtraPredCost);
 678       if (NumCycles > 1)
 679         BBI.ExtraCost += NumCycles-1;
 680       BBI.ExtraCost2 += ExtraPredCost;
 681     } else if (!AlreadyPredicated) {
 682       // FIXME: This instruction is already predicated before the
 683       // if-conversion pass. It's probably something like a conditional move.
 684       // Mark this block unpredicable for now.
 685       BBI.IsUnpredicable = true;
 686       return;
 687     }
 688
 689     if (BBI.ClobbersPred && !isPredicated) {
 690       // Predicate modification instruction should end the block (except for
 691       // already predicated instructions and end of block branches).
 692       // Predicate may have been modified, the subsequent (currently)
 693       // unpredicated instructions cannot be correctly predicated.
 694       BBI.IsUnpredicable = true;
 695       return;
 696     }
 697
 698     // FIXME: Make use of PredDefs? e.g. ADDC, SUBC sets predicates but are
 699     // still potentially predicable.
 700     std::vector<MachineOperand> PredDefs;
 701     if (TII->DefinesPredicate(I, PredDefs))
 702       BBI.ClobbersPred = true;
 703
 704     if (!TII->isPredicable(I)) {
 705       BBI.IsUnpredicable = true;
 706       return;
 707     }
 708   }
 709 }
 710
 711 /// FeasibilityAnalysis - Determine if the block is a suitable candidate to be
 712 /// predicated by the specified predicate.
 713 bool IfConverter::FeasibilityAnalysis(BBInfo &BBI,
 714                                       SmallVectorImpl<MachineOperand> &Pred,
 715                                       bool isTriangle, bool RevBranch) {
 716   // If the block is dead or unpredicable, then it cannot be predicated.
 717   if (BBI.IsDone || BBI.IsUnpredicable)
 718     return false;
 719
 720   // If it is already predicated, check if the new predicate subsumes
 721   // its predicate.
 722   if (BBI.Predicate.size() && !TII->SubsumesPredicate(Pred, BBI.Predicate))
 723     return false;
 724
 725   if (BBI.BrCond.size()) {
 726     if (!isTriangle)
 727       return false;
 728
 729     // Test predicate subsumption.
 730     SmallVector<MachineOperand, 4> RevPred(Pred.begin(), Pred.end());
 731     SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
 732     if (RevBranch) {
 733       if (TII->ReverseBranchCondition(Cond))
 734         return false;
 735     }
 736     if (TII->ReverseBranchCondition(RevPred) ||
 737         !TII->SubsumesPredicate(Cond, RevPred))
 738       return false;
 739   }
 740
 741   return true;
 742 }
 743
 744 /// AnalyzeBlock - Analyze the structure of the sub-CFG starting from
 745 /// the specified block. Record its successors and whether it looks like an
 746 /// if-conversion candidate.
 747 IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB,
 748                                              std::vector<IfcvtToken*> &Tokens) {
 749   BBInfo &BBI = BBAnalysis[BB->getNumber()];
 750
 751   if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed)
 752     return BBI;
 753
 754   BBI.BB = BB;
 755   BBI.IsBeingAnalyzed = true;
 756
 757   ScanInstructions(BBI);
 758
 759   // Unanalyzable or ends with fallthrough or unconditional branch, or if is not
 760   // considered for ifcvt anymore.
 761   if (!BBI.IsBrAnalyzable || BBI.BrCond.empty() || BBI.IsDone) {
 762     BBI.IsBeingAnalyzed = false;
 763     BBI.IsAnalyzed = true;
 764     return BBI;
 765   }
 766
 767   // Do not ifcvt if either path is a back edge to the entry block.
 768   if (BBI.TrueBB == BB || BBI.FalseBB == BB) {
 769     BBI.IsBeingAnalyzed = false;
 770     BBI.IsAnalyzed = true;
 771     return BBI;
 772   }
 773
 774   // Do not ifcvt if true and false fallthrough blocks are the same.
 775   if (!BBI.FalseBB) {
 776     BBI.IsBeingAnalyzed = false;
 777     BBI.IsAnalyzed = true;
 778     return BBI;
 779   }
 780
 781   BBInfo &TrueBBI  = AnalyzeBlock(BBI.TrueBB, Tokens);
 782   BBInfo &FalseBBI = AnalyzeBlock(BBI.FalseBB, Tokens);
 783
 784   if (TrueBBI.IsDone && FalseBBI.IsDone) {
 785     BBI.IsBeingAnalyzed = false;
 786     BBI.IsAnalyzed = true;
 787     return BBI;
 788   }
 789
 790   SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
 791   bool CanRevCond = !TII->ReverseBranchCondition(RevCond);
 792
 793   unsigned Dups = 0;
 794   unsigned Dups2 = 0;
 795   bool TNeedSub = !TrueBBI.Predicate.empty();
 796   bool FNeedSub = !FalseBBI.Predicate.empty();
 797   bool Enqueued = false;
 798
 799   BranchProbability Prediction = MBPI->getEdgeProbability(BB, TrueBBI.BB);
 800
 801   if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2) &&
 802       MeetIfcvtSizeLimit(*TrueBBI.BB, (TrueBBI.NonPredSize - (Dups + Dups2) +
 803                                        TrueBBI.ExtraCost), TrueBBI.ExtraCost2,
 804                          *FalseBBI.BB, (FalseBBI.NonPredSize - (Dups + Dups2) +
 805                                         FalseBBI.ExtraCost),FalseBBI.ExtraCost2,
 806                          Prediction) &&
 807       FeasibilityAnalysis(TrueBBI, BBI.BrCond) &&
 808       FeasibilityAnalysis(FalseBBI, RevCond)) {
 809     // Diamond:
 810     //   EBB
 811     //   / \_
 812     //  |   |
 813     // TBB FBB
 814     //   \ /
 815     //  TailBB
 816     // Note TailBB can be empty.
 817     Tokens.push_back(new IfcvtToken(BBI, ICDiamond, TNeedSub|FNeedSub, Dups,
 818                                     Dups2));
 819     Enqueued = true;
 820   }
 821
 822   if (ValidTriangle(TrueBBI, FalseBBI, false, Dups, Prediction) &&
 823       MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
 824                          TrueBBI.ExtraCost2, Prediction) &&
 825       FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) {
 826     // Triangle:
 827     //   EBB
 828     //   | \_
 829     //   |  |
 830     //   | TBB
 831     //   |  /
 832     //   FBB
 833     Tokens.push_back(new IfcvtToken(BBI, ICTriangle, TNeedSub, Dups));
 834     Enqueued = true;
 835   }
 836
 837   if (ValidTriangle(TrueBBI, FalseBBI, true, Dups, Prediction) &&
 838       MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
 839                          TrueBBI.ExtraCost2, Prediction) &&
 840       FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) {
 841     Tokens.push_back(new IfcvtToken(BBI, ICTriangleRev, TNeedSub, Dups));
 842     Enqueued = true;
 843   }
 844
 845   if (ValidSimple(TrueBBI, Dups, Prediction) &&
 846       MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
 847                          TrueBBI.ExtraCost2, Prediction) &&
 848       FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {
 849     // Simple (split, no rejoin):
 850     //   EBB
 851     //   | \_
 852     //   |  |
 853     //   | TBB---> exit
 854     //   |
 855     //   FBB
 856     Tokens.push_back(new IfcvtToken(BBI, ICSimple, TNeedSub, Dups));
 857     Enqueued = true;
 858   }
 859
 860   if (CanRevCond) {
 861     // Try the other path...
 862     if (ValidTriangle(FalseBBI, TrueBBI, false, Dups,
 863                       Prediction.getCompl()) &&
 864         MeetIfcvtSizeLimit(*FalseBBI.BB,
 865                            FalseBBI.NonPredSize + FalseBBI.ExtraCost,
 866                            FalseBBI.ExtraCost2, Prediction.getCompl()) &&
 867         FeasibilityAnalysis(FalseBBI, RevCond, true)) {
 868       Tokens.push_back(new IfcvtToken(BBI, ICTriangleFalse, FNeedSub, Dups));
 869       Enqueued = true;
 870     }
 871
 872     if (ValidTriangle(FalseBBI, TrueBBI, true, Dups,
 873                       Prediction.getCompl()) &&
 874         MeetIfcvtSizeLimit(*FalseBBI.BB,
 875                            FalseBBI.NonPredSize + FalseBBI.ExtraCost,
 876                            FalseBBI.ExtraCost2, Prediction.getCompl()) &&
 877         FeasibilityAnalysis(FalseBBI, RevCond, true, true)) {
 878       Tokens.push_back(new IfcvtToken(BBI, ICTriangleFRev, FNeedSub, Dups));
 879       Enqueued = true;
 880     }
 881
 882     if (ValidSimple(FalseBBI, Dups, Prediction.getCompl()) &&
 883         MeetIfcvtSizeLimit(*FalseBBI.BB,
 884                            FalseBBI.NonPredSize + FalseBBI.ExtraCost,
 885                            FalseBBI.ExtraCost2, Prediction.getCompl()) &&
 886         FeasibilityAnalysis(FalseBBI, RevCond)) {
 887       Tokens.push_back(new IfcvtToken(BBI, ICSimpleFalse, FNeedSub, Dups));
 888       Enqueued = true;
 889     }
 890   }
 891
 892   BBI.IsEnqueued = Enqueued;
 893   BBI.IsBeingAnalyzed = false;
 894   BBI.IsAnalyzed = true;
 895   return BBI;
 896 }
 897
 898 /// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion
 899 /// candidates.
 900 void IfConverter::AnalyzeBlocks(MachineFunction &MF,
 901                                 std::vector<IfcvtToken*> &Tokens) {
 902   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
 903     MachineBasicBlock *BB = I;
 904     AnalyzeBlock(BB, Tokens);
 905   }
 906
 907   // Sort to favor more complex ifcvt scheme.
 908   std::stable_sort(Tokens.begin(), Tokens.end(), IfcvtTokenCmp);
 909 }
 910
 911 /// canFallThroughTo - Returns true either if ToBB is the next block after BB or
 912 /// that all the intervening blocks are empty (given BB can fall through to its
 913 /// next block).
 914 static bool canFallThroughTo(MachineBasicBlock *BB, MachineBasicBlock *ToBB) {
 915   MachineFunction::iterator PI = BB;
 916   MachineFunction::iterator I = llvm::next(PI);
 917   MachineFunction::iterator TI = ToBB;
 918   MachineFunction::iterator E = BB->getParent()->end();
 919   while (I != TI) {
 920     // Check isSuccessor to avoid case where the next block is empty, but
 921     // it's not a successor.
 922     if (I == E || !I->empty() || !PI->isSuccessor(I))
 923       return false;
 924     PI = I++;
 925   }
 926   return true;
 927 }
 928
 929 /// InvalidatePreds - Invalidate predecessor BB info so it would be re-analyzed
 930 /// to determine if it can be if-converted. If predecessor is already enqueued,
 931 /// dequeue it!
 932 void IfConverter::InvalidatePreds(MachineBasicBlock *BB) {
 933   for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
 934          E = BB->pred_end(); PI != E; ++PI) {
 935     BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()];
 936     if (PBBI.IsDone || PBBI.BB == BB)
 937       continue;
 938     PBBI.IsAnalyzed = false;
 939     PBBI.IsEnqueued = false;
 940   }
 941 }
 942
 943 /// InsertUncondBranch - Inserts an unconditional branch from BB to ToBB.
 944 ///
 945 static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB,
 946                                const TargetInstrInfo *TII) {
 947   DebugLoc dl;  // FIXME: this is nowhere
 948   SmallVector<MachineOperand, 0> NoCond;
 949   TII->InsertBranch(*BB, ToBB, NULL, NoCond, dl);
 950 }
 951
 952 /// RemoveExtraEdges - Remove true / false edges if either / both are no longer
 953 /// successors.
 954 void IfConverter::RemoveExtraEdges(BBInfo &BBI) {
 955   MachineBasicBlock *TBB = NULL, *FBB = NULL;
 956   SmallVector<MachineOperand, 4> Cond;
 957   if (!TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond))
 958     BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
 959 }
 960
 961 /// InitPredRedefs / UpdatePredRedefs - Defs by predicated instructions are
 962 /// modeled as read + write (sort like two-address instructions). These
 963 /// routines track register liveness and add implicit uses to if-converted
 964 /// instructions to conform to the model.
 965 static void InitPredRedefs(MachineBasicBlock *BB, SmallSet<unsigned,4> &Redefs,
 966                            const TargetRegisterInfo *TRI) {
 967   for (MachineBasicBlock::livein_iterator I = BB->livein_begin(),
 968          E = BB->livein_end(); I != E; ++I) {
 969     unsigned Reg = *I;
 970     for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
 971          SubRegs.isValid(); ++SubRegs)
 972       Redefs.insert(*SubRegs);
 973   }
 974 }
 975
 976 static void UpdatePredRedefs(MachineInstr *MI, SmallSet<unsigned,4> &Redefs,
 977                              const TargetRegisterInfo *TRI,
 978                              bool AddImpUse = false) {
 979   SmallVector<unsigned, 4> Defs;
 980   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 981     const MachineOperand &MO = MI->getOperand(i);
 982     if (!MO.isReg())
 983       continue;
 984     unsigned Reg = MO.getReg();
 985     if (!Reg)
 986       continue;
 987     if (MO.isDef())
 988       Defs.push_back(Reg);
 989     else if (MO.isKill()) {
 990       for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
 991            SubRegs.isValid(); ++SubRegs)
 992         Redefs.erase(*SubRegs);
 993     }
 994   }
 995   MachineInstrBuilder MIB(*MI->getParent()->getParent(), MI);
 996   for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
 997     unsigned Reg = Defs[i];
 998     if (!Redefs.insert(Reg)) {
 999       if (AddImpUse)
1000         // Treat predicated update as read + write.
1001         MIB.addReg(Reg, RegState::Implicit | RegState::Undef);
1002     } else {
1003       for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
1004         Redefs.insert(*SubRegs);
1005     }
1006   }
1007 }
1008
1009 static void UpdatePredRedefs(MachineBasicBlock::iterator I,
1010                              MachineBasicBlock::iterator E,
1011                              SmallSet<unsigned,4> &Redefs,
1012                              const TargetRegisterInfo *TRI) {
1013   while (I != E) {
1014     UpdatePredRedefs(I, Redefs, TRI);
1015     ++I;
1016   }
1017 }
1018
1019 /// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG.
1020 ///
1021 bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {
1022   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
1023   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1024   BBInfo *CvtBBI = &TrueBBI;
1025   BBInfo *NextBBI = &FalseBBI;
1026
1027   SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
1028   if (Kind == ICSimpleFalse)
1029     std::swap(CvtBBI, NextBBI);
1030
1031   if (CvtBBI->IsDone ||
1032       (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) {
1033     // Something has changed. It's no longer safe to predicate this block.
1034     BBI.IsAnalyzed = false;
1035     CvtBBI->IsAnalyzed = false;
1036     return false;
1037   }
1038
1039   if (CvtBBI->BB->hasAddressTaken())
1040     // Conservatively abort if-conversion if BB's address is taken.
1041     return false;
1042
1043   if (Kind == ICSimpleFalse)
1044     if (TII->ReverseBranchCondition(Cond))
1045       llvm_unreachable("Unable to reverse branch condition!");
1046
1047   // Initialize liveins to the first BB. These are potentiall redefined by
1048   // predicated instructions.
1049   SmallSet<unsigned, 4> Redefs;
1050   InitPredRedefs(CvtBBI->BB, Redefs, TRI);
1051   InitPredRedefs(NextBBI->BB, Redefs, TRI);
1052
1053   if (CvtBBI->BB->pred_size() > 1) {
1054     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1055     // Copy instructions in the true block, predicate them, and add them to
1056     // the entry block.
1057     CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs);
1058
1059     // RemoveExtraEdges won't work if the block has an unanalyzable branch, so
1060     // explicitly remove CvtBBI as a successor.
1061     BBI.BB->removeSuccessor(CvtBBI->BB);
1062   } else {
1063     PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond, Redefs);
1064
1065     // Merge converted block into entry block.
1066     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1067     MergeBlocks(BBI, *CvtBBI);
1068   }
1069
1070   bool IterIfcvt = true;
1071   if (!canFallThroughTo(BBI.BB, NextBBI->BB)) {
1072     InsertUncondBranch(BBI.BB, NextBBI->BB, TII);
1073     BBI.HasFallThrough = false;
1074     // Now ifcvt'd block will look like this:
1075     // BB:
1076     // ...
1077     // t, f = cmp
1078     // if t op
1079     // b BBf
1080     //
1081     // We cannot further ifcvt this block because the unconditional branch
1082     // will have to be predicated on the new condition, that will not be
1083     // available if cmp executes.
1084     IterIfcvt = false;
1085   }
1086
1087   RemoveExtraEdges(BBI);
1088
1089   // Update block info. BB can be iteratively if-converted.
1090   if (!IterIfcvt)
1091     BBI.IsDone = true;
1092   InvalidatePreds(BBI.BB);
1093   CvtBBI->IsDone = true;
1094
1095   // FIXME: Must maintain LiveIns.
1096   return true;
1097 }
1098
1099 /// IfConvertTriangle - If convert a triangle sub-CFG.
1100 ///
1101 bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
1102   BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
1103   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1104   BBInfo *CvtBBI = &TrueBBI;
1105   BBInfo *NextBBI = &FalseBBI;
1106   DebugLoc dl;  // FIXME: this is nowhere
1107
1108   SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
1109   if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
1110     std::swap(CvtBBI, NextBBI);
1111
1112   if (CvtBBI->IsDone ||
1113       (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) {
1114     // Something has changed. It's no longer safe to predicate this block.
1115     BBI.IsAnalyzed = false;
1116     CvtBBI->IsAnalyzed = false;
1117     return false;
1118   }
1119
1120   if (CvtBBI->BB->hasAddressTaken())
1121     // Conservatively abort if-conversion if BB's address is taken.
1122     return false;
1123
1124   if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
1125     if (TII->ReverseBranchCondition(Cond))
1126       llvm_unreachable("Unable to reverse branch condition!");
1127
1128   if (Kind == ICTriangleRev || Kind == ICTriangleFRev) {
1129     if (ReverseBranchCondition(*CvtBBI)) {
1130       // BB has been changed, modify its predecessors (except for this
1131       // one) so they don't get ifcvt'ed based on bad intel.
1132       for (MachineBasicBlock::pred_iterator PI = CvtBBI->BB->pred_begin(),
1133              E = CvtBBI->BB->pred_end(); PI != E; ++PI) {
1134         MachineBasicBlock *PBB = *PI;
1135         if (PBB == BBI.BB)
1136           continue;
1137         BBInfo &PBBI = BBAnalysis[PBB->getNumber()];
1138         if (PBBI.IsEnqueued) {
1139           PBBI.IsAnalyzed = false;
1140           PBBI.IsEnqueued = false;
1141         }
1142       }
1143     }
1144   }
1145
1146   // Initialize liveins to the first BB. These are potentially redefined by
1147   // predicated instructions.
1148   SmallSet<unsigned, 4> Redefs;
1149   InitPredRedefs(CvtBBI->BB, Redefs, TRI);
1150   InitPredRedefs(NextBBI->BB, Redefs, TRI);
1151
1152   bool HasEarlyExit = CvtBBI->FalseBB != NULL;
1153   if (CvtBBI->BB->pred_size() > 1) {
1154     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1155     // Copy instructions in the true block, predicate them, and add them to
1156     // the entry block.
1157     CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs, true);
1158
1159     // RemoveExtraEdges won't work if the block has an unanalyzable branch, so
1160     // explicitly remove CvtBBI as a successor.
1161     BBI.BB->removeSuccessor(CvtBBI->BB);
1162   } else {
1163     // Predicate the 'true' block after removing its branch.
1164     CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB);
1165     PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond, Redefs);
1166
1167     // Now merge the entry of the triangle with the true block.
1168     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1169     MergeBlocks(BBI, *CvtBBI, false);
1170   }
1171
1172   // If 'true' block has a 'false' successor, add an exit branch to it.
1173   if (HasEarlyExit) {
1174     SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(),
1175                                            CvtBBI->BrCond.end());
1176     if (TII->ReverseBranchCondition(RevCond))
1177       llvm_unreachable("Unable to reverse branch condition!");
1178     TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond, dl);
1179     BBI.BB->addSuccessor(CvtBBI->FalseBB);
1180   }
1181
1182   // Merge in the 'false' block if the 'false' block has no other
1183   // predecessors. Otherwise, add an unconditional branch to 'false'.
1184   bool FalseBBDead = false;
1185   bool IterIfcvt = true;
1186   bool isFallThrough = canFallThroughTo(BBI.BB, NextBBI->BB);
1187   if (!isFallThrough) {
1188     // Only merge them if the true block does not fallthrough to the false
1189     // block. By not merging them, we make it possible to iteratively
1190     // ifcvt the blocks.
1191     if (!HasEarlyExit &&
1192         NextBBI->BB->pred_size() == 1 && !NextBBI->HasFallThrough &&
1193         !NextBBI->BB->hasAddressTaken()) {
1194       MergeBlocks(BBI, *NextBBI);
1195       FalseBBDead = true;
1196     } else {
1197       InsertUncondBranch(BBI.BB, NextBBI->BB, TII);
1198       BBI.HasFallThrough = false;
1199     }
1200     // Mixed predicated and unpredicated code. This cannot be iteratively
1201     // predicated.
1202     IterIfcvt = false;
1203   }
1204
1205   RemoveExtraEdges(BBI);
1206
1207   // Update block info. BB can be iteratively if-converted.
1208   if (!IterIfcvt)
1209     BBI.IsDone = true;
1210   InvalidatePreds(BBI.BB);
1211   CvtBBI->IsDone = true;
1212   if (FalseBBDead)
1213     NextBBI->IsDone = true;
1214
1215   // FIXME: Must maintain LiveIns.
1216   return true;
1217 }
1218
1219 /// IfConvertDiamond - If convert a diamond sub-CFG.
1220 ///
1221 bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
1222                                    unsigned NumDups1, unsigned NumDups2) {
1223   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
1224   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1225   MachineBasicBlock *TailBB = TrueBBI.TrueBB;
1226   // True block must fall through or end with an unanalyzable terminator.
1227   if (!TailBB) {
1228     if (blockAlwaysFallThrough(TrueBBI))
1229       TailBB = FalseBBI.TrueBB;
1230     assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!");
1231   }
1232
1233   if (TrueBBI.IsDone || FalseBBI.IsDone ||
1234       TrueBBI.BB->pred_size() > 1 ||
1235       FalseBBI.BB->pred_size() > 1) {
1236     // Something has changed. It's no longer safe to predicate these blocks.
1237     BBI.IsAnalyzed = false;
1238     TrueBBI.IsAnalyzed = false;
1239     FalseBBI.IsAnalyzed = false;
1240     return false;
1241   }
1242
1243   if (TrueBBI.BB->hasAddressTaken() || FalseBBI.BB->hasAddressTaken())
1244     // Conservatively abort if-conversion if either BB has its address taken.
1245     return false;
1246
1247   // Put the predicated instructions from the 'true' block before the
1248   // instructions from the 'false' block, unless the true block would clobber
1249   // the predicate, in which case, do the opposite.
1250   BBInfo *BBI1 = &TrueBBI;
1251   BBInfo *BBI2 = &FalseBBI;
1252   SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
1253   if (TII->ReverseBranchCondition(RevCond))
1254     llvm_unreachable("Unable to reverse branch condition!");
1255   SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond;
1256   SmallVector<MachineOperand, 4> *Cond2 = &RevCond;
1257
1258   // Figure out the more profitable ordering.
1259   bool DoSwap = false;
1260   if (TrueBBI.ClobbersPred && !FalseBBI.ClobbersPred)
1261     DoSwap = true;
1262   else if (TrueBBI.ClobbersPred == FalseBBI.ClobbersPred) {
1263     if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)
1264       DoSwap = true;
1265   }
1266   if (DoSwap) {
1267     std::swap(BBI1, BBI2);
1268     std::swap(Cond1, Cond2);
1269   }
1270
1271   // Remove the conditional branch from entry to the blocks.
1272   BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1273
1274   // Initialize liveins to the first BB. These are potentially redefined by
1275   // predicated instructions.
1276   SmallSet<unsigned, 4> Redefs;
1277   InitPredRedefs(BBI1->BB, Redefs, TRI);
1278
1279   // Remove the duplicated instructions at the beginnings of both paths.
1280   MachineBasicBlock::iterator DI1 = BBI1->BB->begin();
1281   MachineBasicBlock::iterator DI2 = BBI2->BB->begin();
1282   MachineBasicBlock::iterator DIE1 = BBI1->BB->end();
1283   MachineBasicBlock::iterator DIE2 = BBI2->BB->end();
1284   // Skip dbg_value instructions
1285   while (DI1 != DIE1 && DI1->isDebugValue())
1286     ++DI1;
1287   while (DI2 != DIE2 && DI2->isDebugValue())
1288     ++DI2;
1289   BBI1->NonPredSize -= NumDups1;
1290   BBI2->NonPredSize -= NumDups1;
1291
1292   // Skip past the dups on each side separately since there may be
1293   // differing dbg_value entries.
1294   for (unsigned i = 0; i < NumDups1; ++DI1) {
1295     if (!DI1->isDebugValue())
1296       ++i;
1297   }
1298   while (NumDups1 != 0) {
1299     ++DI2;
1300     if (!DI2->isDebugValue())
1301       --NumDups1;
1302   }
1303
1304   UpdatePredRedefs(BBI1->BB->begin(), DI1, Redefs, TRI);
1305   BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1);
1306   BBI2->BB->erase(BBI2->BB->begin(), DI2);
1307
1308   // Remove branch from 'true' block and remove duplicated instructions.
1309   BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB);
1310   DI1 = BBI1->BB->end();
1311   for (unsigned i = 0; i != NumDups2; ) {
1312     // NumDups2 only counted non-dbg_value instructions, so this won't
1313     // run off the head of the list.
1314     assert (DI1 != BBI1->BB->begin());
1315     --DI1;
1316     // skip dbg_value instructions
1317     if (!DI1->isDebugValue())
1318       ++i;
1319   }
1320   BBI1->BB->erase(DI1, BBI1->BB->end());
1321
1322   // Remove 'false' block branch and find the last instruction to predicate.
1323   BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB);
1324   DI2 = BBI2->BB->end();
1325   while (NumDups2 != 0) {
1326     // NumDups2 only counted non-dbg_value instructions, so this won't
1327     // run off the head of the list.
1328     assert (DI2 != BBI2->BB->begin());
1329     --DI2;
1330     // skip dbg_value instructions
1331     if (!DI2->isDebugValue())
1332       --NumDups2;
1333   }
1334
1335   // Remember which registers would later be defined by the false block.
1336   // This allows us not to predicate instructions in the true block that would
1337   // later be re-defined. That is, rather than
1338   //   subeq  r0, r1, #1
1339   //   addne  r0, r1, #1
1340   // generate:
1341   //   sub    r0, r1, #1
1342   //   addne  r0, r1, #1
1343   SmallSet<unsigned, 4> RedefsByFalse;
1344   SmallSet<unsigned, 4> ExtUses;
1345   if (TII->isProfitableToUnpredicate(*BBI1->BB, *BBI2->BB)) {
1346     for (MachineBasicBlock::iterator FI = BBI2->BB->begin(); FI != DI2; ++FI) {
1347       if (FI->isDebugValue())
1348         continue;
1349       SmallVector<unsigned, 4> Defs;
1350       for (unsigned i = 0, e = FI->getNumOperands(); i != e; ++i) {
1351         const MachineOperand &MO = FI->getOperand(i);
1352         if (!MO.isReg())
1353           continue;
1354         unsigned Reg = MO.getReg();
1355         if (!Reg)
1356           continue;
1357         if (MO.isDef()) {
1358           Defs.push_back(Reg);
1359         } else if (!RedefsByFalse.count(Reg)) {
1360           // These are defined before ctrl flow reach the 'false' instructions.
1361           // They cannot be modified by the 'true' instructions.
1362           for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
1363                SubRegs.isValid(); ++SubRegs)
1364             ExtUses.insert(*SubRegs);
1365         }
1366       }
1367
1368       for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
1369         unsigned Reg = Defs[i];
1370         if (!ExtUses.count(Reg)) {
1371           for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
1372                SubRegs.isValid(); ++SubRegs)
1373             RedefsByFalse.insert(*SubRegs);
1374         }
1375       }
1376     }
1377   }
1378
1379   // Predicate the 'true' block.
1380   PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1, Redefs, &RedefsByFalse);
1381
1382   // Predicate the 'false' block.
1383   PredicateBlock(*BBI2, DI2, *Cond2, Redefs);
1384
1385   // Merge the true block into the entry of the diamond.
1386   MergeBlocks(BBI, *BBI1, TailBB == 0);
1387   MergeBlocks(BBI, *BBI2, TailBB == 0);
1388
1389   // If the if-converted block falls through or unconditionally branches into
1390   // the tail block, and the tail block does not have other predecessors, then
1391   // fold the tail block in as well. Otherwise, unless it falls through to the
1392   // tail, add a unconditional branch to it.
1393   if (TailBB) {
1394     BBInfo &TailBBI = BBAnalysis[TailBB->getNumber()];
1395     bool CanMergeTail = !TailBBI.HasFallThrough &&
1396       !TailBBI.BB->hasAddressTaken();
1397     // There may still be a fall-through edge from BBI1 or BBI2 to TailBB;
1398     // check if there are any other predecessors besides those.
1399     unsigned NumPreds = TailBB->pred_size();
1400     if (NumPreds > 1)
1401       CanMergeTail = false;
1402     else if (NumPreds == 1 && CanMergeTail) {
1403       MachineBasicBlock::pred_iterator PI = TailBB->pred_begin();
1404       if (*PI != BBI1->BB && *PI != BBI2->BB)
1405         CanMergeTail = false;
1406     }
1407     if (CanMergeTail) {
1408       MergeBlocks(BBI, TailBBI);
1409       TailBBI.IsDone = true;
1410     } else {
1411       BBI.BB->addSuccessor(TailBB);
1412       InsertUncondBranch(BBI.BB, TailBB, TII);
1413       BBI.HasFallThrough = false;
1414     }
1415   }
1416
1417   // RemoveExtraEdges won't work if the block has an unanalyzable branch,
1418   // which can happen here if TailBB is unanalyzable and is merged, so
1419   // explicitly remove BBI1 and BBI2 as successors.
1420   BBI.BB->removeSuccessor(BBI1->BB);
1421   BBI.BB->removeSuccessor(BBI2->BB);
1422   RemoveExtraEdges(BBI);
1423
1424   // Update block info.
1425   BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;
1426   InvalidatePreds(BBI.BB);
1427
1428   // FIXME: Must maintain LiveIns.
1429   return true;
1430 }
1431
1432 static bool MaySpeculate(const MachineInstr *MI,
1433                          SmallSet<unsigned, 4> &LaterRedefs,
1434                          const TargetInstrInfo *TII) {
1435   bool SawStore = true;
1436   if (!MI->isSafeToMove(TII, 0, SawStore))
1437     return false;
1438
1439   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1440     const MachineOperand &MO = MI->getOperand(i);
1441     if (!MO.isReg())
1442       continue;
1443     unsigned Reg = MO.getReg();
1444     if (!Reg)
1445       continue;
1446     if (MO.isDef() && !LaterRedefs.count(Reg))
1447       return false;
1448   }
1449
1450   return true;
1451 }
1452
1453 /// PredicateBlock - Predicate instructions from the start of the block to the
1454 /// specified end with the specified condition.
1455 void IfConverter::PredicateBlock(BBInfo &BBI,
1456                                  MachineBasicBlock::iterator E,
1457                                  SmallVectorImpl<MachineOperand> &Cond,
1458                                  SmallSet<unsigned, 4> &Redefs,
1459                                  SmallSet<unsigned, 4> *LaterRedefs) {
1460   bool AnyUnpred = false;
1461   bool MaySpec = LaterRedefs != 0;
1462   for (MachineBasicBlock::iterator I = BBI.BB->begin(); I != E; ++I) {
1463     if (I->isDebugValue() || TII->isPredicated(I))
1464       continue;
1465     // It may be possible not to predicate an instruction if it's the 'true'
1466     // side of a diamond and the 'false' side may re-define the instruction's
1467     // defs.
1468     if (MaySpec && MaySpeculate(I, *LaterRedefs, TII)) {
1469       AnyUnpred = true;
1470       continue;
1471     }
1472     // If any instruction is predicated, then every instruction after it must
1473     // be predicated.
1474     MaySpec = false;
1475     if (!TII->PredicateInstruction(I, Cond)) {
1476 #ifndef NDEBUG
1477       dbgs() << "Unable to predicate " << *I << "!\n";
1478 #endif
1479       llvm_unreachable(0);
1480     }
1481
1482     // If the predicated instruction now redefines a register as the result of
1483     // if-conversion, add an implicit kill.
1484     UpdatePredRedefs(I, Redefs, TRI, true);
1485   }
1486
1487   std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate));
1488
1489   BBI.IsAnalyzed = false;
1490   BBI.NonPredSize = 0;
1491
1492   ++NumIfConvBBs;
1493   if (AnyUnpred)
1494     ++NumUnpred;
1495 }
1496
1497 /// CopyAndPredicateBlock - Copy and predicate instructions from source BB to
1498 /// the destination block. Skip end of block branches if IgnoreBr is true.
1499 void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
1500                                         SmallVectorImpl<MachineOperand> &Cond,
1501                                         SmallSet<unsigned, 4> &Redefs,
1502                                         bool IgnoreBr) {
1503   MachineFunction &MF = *ToBBI.BB->getParent();
1504
1505   for (MachineBasicBlock::iterator I = FromBBI.BB->begin(),
1506          E = FromBBI.BB->end(); I != E; ++I) {
1507     // Do not copy the end of the block branches.
1508     if (IgnoreBr && I->isBranch())
1509       break;
1510
1511     MachineInstr *MI = MF.CloneMachineInstr(I);
1512     ToBBI.BB->insert(ToBBI.BB->end(), MI);
1513     ToBBI.NonPredSize++;
1514     unsigned ExtraPredCost = 0;
1515     unsigned NumCycles = TII->getInstrLatency(InstrItins, &*I, &ExtraPredCost);
1516     if (NumCycles > 1)
1517       ToBBI.ExtraCost += NumCycles-1;
1518     ToBBI.ExtraCost2 += ExtraPredCost;
1519
1520     if (!TII->isPredicated(I) && !MI->isDebugValue()) {
1521       if (!TII->PredicateInstruction(MI, Cond)) {
1522 #ifndef NDEBUG
1523         dbgs() << "Unable to predicate " << *I << "!\n";
1524 #endif
1525         llvm_unreachable(0);
1526       }
1527     }
1528
1529     // If the predicated instruction now redefines a register as the result of
1530     // if-conversion, add an implicit kill.
1531     UpdatePredRedefs(MI, Redefs, TRI, true);
1532   }
1533
1534   if (!IgnoreBr) {
1535     std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
1536                                            FromBBI.BB->succ_end());
1537     MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
1538     MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;
1539
1540     for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
1541       MachineBasicBlock *Succ = Succs[i];
1542       // Fallthrough edge can't be transferred.
1543       if (Succ == FallThrough)
1544         continue;
1545       ToBBI.BB->addSuccessor(Succ);
1546     }
1547   }
1548
1549   std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
1550             std::back_inserter(ToBBI.Predicate));
1551   std::copy(Cond.begin(), Cond.end(), std::back_inserter(ToBBI.Predicate));
1552
1553   ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
1554   ToBBI.IsAnalyzed = false;
1555
1556   ++NumDupBBs;
1557 }
1558
1559 /// MergeBlocks - Move all instructions from FromBB to the end of ToBB.
1560 /// This will leave FromBB as an empty block, so remove all of its
1561 /// successor edges except for the fall-through edge.  If AddEdges is true,
1562 /// i.e., when FromBBI's branch is being moved, add those successor edges to
1563 /// ToBBI.
1564 void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
1565   assert(!FromBBI.BB->hasAddressTaken() &&
1566          "Removing a BB whose address is taken!");
1567
1568   ToBBI.BB->splice(ToBBI.BB->end(),
1569                    FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end());
1570
1571   std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
1572                                          FromBBI.BB->succ_end());
1573   MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
1574   MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;
1575
1576   for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
1577     MachineBasicBlock *Succ = Succs[i];
1578     // Fallthrough edge can't be transferred.
1579     if (Succ == FallThrough)
1580       continue;
1581     FromBBI.BB->removeSuccessor(Succ);
1582     if (AddEdges && !ToBBI.BB->isSuccessor(Succ))
1583       ToBBI.BB->addSuccessor(Succ);
1584   }
1585
1586   // Now FromBBI always falls through to the next block!
1587   if (NBB && !FromBBI.BB->isSuccessor(NBB))
1588     FromBBI.BB->addSuccessor(NBB);
1589
1590   std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
1591             std::back_inserter(ToBBI.Predicate));
1592   FromBBI.Predicate.clear();
1593
1594   ToBBI.NonPredSize += FromBBI.NonPredSize;
1595   ToBBI.ExtraCost += FromBBI.ExtraCost;
1596   ToBBI.ExtraCost2 += FromBBI.ExtraCost2;
1597   FromBBI.NonPredSize = 0;
1598   FromBBI.ExtraCost = 0;
1599   FromBBI.ExtraCost2 = 0;
1600
1601   ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
1602   ToBBI.HasFallThrough = FromBBI.HasFallThrough;
1603   ToBBI.IsAnalyzed = false;
1604   FromBBI.IsAnalyzed = false;
1605 }