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     if (!isCondBr) {
 670       if (!isPredicated) {
 671         BBI.NonPredSize++;
 672         unsigned ExtraPredCost = 0;
 673         unsigned NumCycles = TII->getInstrLatency(InstrItins, &*I,
 674                                                   &ExtraPredCost);
 675         if (NumCycles > 1)
 676           BBI.ExtraCost += NumCycles-1;
 677         BBI.ExtraCost2 += ExtraPredCost;
 678       } else if (!AlreadyPredicated) {
 679         // FIXME: This instruction is already predicated before the
 680         // if-conversion pass. It's probably something like a conditional move.
 681         // Mark this block unpredicable for now.
 682         BBI.IsUnpredicable = true;
 683         return;
 684       }
 685     }
 686
 687     if (BBI.ClobbersPred && !isPredicated) {
 688       // Predicate modification instruction should end the block (except for
 689       // already predicated instructions and end of block branches).
 690       if (isCondBr) {
 691         // A conditional branch is not predicable, but it may be eliminated.
 692         continue;
 693       }
 694
 695       // Predicate may have been modified, the subsequent (currently)
 696       // unpredicated instructions cannot be correctly predicated.
 697       BBI.IsUnpredicable = true;
 698       return;
 699     }
 700
 701     // FIXME: Make use of PredDefs? e.g. ADDC, SUBC sets predicates but are
 702     // still potentially predicable.
 703     std::vector<MachineOperand> PredDefs;
 704     if (TII->DefinesPredicate(I, PredDefs))
 705       BBI.ClobbersPred = true;
 706
 707     if (!TII->isPredicable(I)) {
 708       BBI.IsUnpredicable = true;
 709       return;
 710     }
 711   }
 712 }
 713
 714 /// FeasibilityAnalysis - Determine if the block is a suitable candidate to be
 715 /// predicated by the specified predicate.
 716 bool IfConverter::FeasibilityAnalysis(BBInfo &BBI,
 717                                       SmallVectorImpl<MachineOperand> &Pred,
 718                                       bool isTriangle, bool RevBranch) {
 719   // If the block is dead or unpredicable, then it cannot be predicated.
 720   if (BBI.IsDone || BBI.IsUnpredicable)
 721     return false;
 722
 723   // If it is already predicated, check if its predicate subsumes the new
 724   // predicate.
 725   if (BBI.Predicate.size() && !TII->SubsumesPredicate(BBI.Predicate, Pred))
 726     return false;
 727
 728   if (BBI.BrCond.size()) {
 729     if (!isTriangle)
 730       return false;
 731
 732     // Test predicate subsumption.
 733     SmallVector<MachineOperand, 4> RevPred(Pred.begin(), Pred.end());
 734     SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
 735     if (RevBranch) {
 736       if (TII->ReverseBranchCondition(Cond))
 737         return false;
 738     }
 739     if (TII->ReverseBranchCondition(RevPred) ||
 740         !TII->SubsumesPredicate(Cond, RevPred))
 741       return false;
 742   }
 743
 744   return true;
 745 }
 746
 747 /// AnalyzeBlock - Analyze the structure of the sub-CFG starting from
 748 /// the specified block. Record its successors and whether it looks like an
 749 /// if-conversion candidate.
 750 IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB,
 751                                              std::vector<IfcvtToken*> &Tokens) {
 752   BBInfo &BBI = BBAnalysis[BB->getNumber()];
 753
 754   if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed)
 755     return BBI;
 756
 757   BBI.BB = BB;
 758   BBI.IsBeingAnalyzed = true;
 759
 760   ScanInstructions(BBI);
 761
 762   // Unanalyzable or ends with fallthrough or unconditional branch, or if is not
 763   // considered for ifcvt anymore.
 764   if (!BBI.IsBrAnalyzable || BBI.BrCond.empty() || BBI.IsDone) {
 765     BBI.IsBeingAnalyzed = false;
 766     BBI.IsAnalyzed = true;
 767     return BBI;
 768   }
 769
 770   // Do not ifcvt if either path is a back edge to the entry block.
 771   if (BBI.TrueBB == BB || BBI.FalseBB == BB) {
 772     BBI.IsBeingAnalyzed = false;
 773     BBI.IsAnalyzed = true;
 774     return BBI;
 775   }
 776
 777   // Do not ifcvt if true and false fallthrough blocks are the same.
 778   if (!BBI.FalseBB) {
 779     BBI.IsBeingAnalyzed = false;
 780     BBI.IsAnalyzed = true;
 781     return BBI;
 782   }
 783
 784   BBInfo &TrueBBI  = AnalyzeBlock(BBI.TrueBB, Tokens);
 785   BBInfo &FalseBBI = AnalyzeBlock(BBI.FalseBB, Tokens);
 786
 787   if (TrueBBI.IsDone && FalseBBI.IsDone) {
 788     BBI.IsBeingAnalyzed = false;
 789     BBI.IsAnalyzed = true;
 790     return BBI;
 791   }
 792
 793   SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
 794   bool CanRevCond = !TII->ReverseBranchCondition(RevCond);
 795
 796   unsigned Dups = 0;
 797   unsigned Dups2 = 0;
 798   bool TNeedSub = !TrueBBI.Predicate.empty();
 799   bool FNeedSub = !FalseBBI.Predicate.empty();
 800   bool Enqueued = false;
 801
 802   BranchProbability Prediction = MBPI->getEdgeProbability(BB, TrueBBI.BB);
 803
 804   if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2) &&
 805       MeetIfcvtSizeLimit(*TrueBBI.BB, (TrueBBI.NonPredSize - (Dups + Dups2) +
 806                                        TrueBBI.ExtraCost), TrueBBI.ExtraCost2,
 807                          *FalseBBI.BB, (FalseBBI.NonPredSize - (Dups + Dups2) +
 808                                         FalseBBI.ExtraCost),FalseBBI.ExtraCost2,
 809                          Prediction) &&
 810       FeasibilityAnalysis(TrueBBI, BBI.BrCond) &&
 811       FeasibilityAnalysis(FalseBBI, RevCond)) {
 812     // Diamond:
 813     //   EBB
 814     //   / \_
 815     //  |   |
 816     // TBB FBB
 817     //   \ /
 818     //  TailBB
 819     // Note TailBB can be empty.
 820     Tokens.push_back(new IfcvtToken(BBI, ICDiamond, TNeedSub|FNeedSub, Dups,
 821                                     Dups2));
 822     Enqueued = true;
 823   }
 824
 825   if (ValidTriangle(TrueBBI, FalseBBI, false, Dups, Prediction) &&
 826       MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
 827                          TrueBBI.ExtraCost2, Prediction) &&
 828       FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) {
 829     // Triangle:
 830     //   EBB
 831     //   | \_
 832     //   |  |
 833     //   | TBB
 834     //   |  /
 835     //   FBB
 836     Tokens.push_back(new IfcvtToken(BBI, ICTriangle, TNeedSub, Dups));
 837     Enqueued = true;
 838   }
 839
 840   if (ValidTriangle(TrueBBI, FalseBBI, true, Dups, Prediction) &&
 841       MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
 842                          TrueBBI.ExtraCost2, Prediction) &&
 843       FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) {
 844     Tokens.push_back(new IfcvtToken(BBI, ICTriangleRev, TNeedSub, Dups));
 845     Enqueued = true;
 846   }
 847
 848   if (ValidSimple(TrueBBI, Dups, Prediction) &&
 849       MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
 850                          TrueBBI.ExtraCost2, Prediction) &&
 851       FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {
 852     // Simple (split, no rejoin):
 853     //   EBB
 854     //   | \_
 855     //   |  |
 856     //   | TBB---> exit
 857     //   |
 858     //   FBB
 859     Tokens.push_back(new IfcvtToken(BBI, ICSimple, TNeedSub, Dups));
 860     Enqueued = true;
 861   }
 862
 863   if (CanRevCond) {
 864     // Try the other path...
 865     if (ValidTriangle(FalseBBI, TrueBBI, false, Dups,
 866                       Prediction.getCompl()) &&
 867         MeetIfcvtSizeLimit(*FalseBBI.BB,
 868                            FalseBBI.NonPredSize + FalseBBI.ExtraCost,
 869                            FalseBBI.ExtraCost2, Prediction.getCompl()) &&
 870         FeasibilityAnalysis(FalseBBI, RevCond, true)) {
 871       Tokens.push_back(new IfcvtToken(BBI, ICTriangleFalse, FNeedSub, Dups));
 872       Enqueued = true;
 873     }
 874
 875     if (ValidTriangle(FalseBBI, TrueBBI, true, Dups,
 876                       Prediction.getCompl()) &&
 877         MeetIfcvtSizeLimit(*FalseBBI.BB,
 878                            FalseBBI.NonPredSize + FalseBBI.ExtraCost,
 879                            FalseBBI.ExtraCost2, Prediction.getCompl()) &&
 880         FeasibilityAnalysis(FalseBBI, RevCond, true, true)) {
 881       Tokens.push_back(new IfcvtToken(BBI, ICTriangleFRev, FNeedSub, Dups));
 882       Enqueued = true;
 883     }
 884
 885     if (ValidSimple(FalseBBI, Dups, Prediction.getCompl()) &&
 886         MeetIfcvtSizeLimit(*FalseBBI.BB,
 887                            FalseBBI.NonPredSize + FalseBBI.ExtraCost,
 888                            FalseBBI.ExtraCost2, Prediction.getCompl()) &&
 889         FeasibilityAnalysis(FalseBBI, RevCond)) {
 890       Tokens.push_back(new IfcvtToken(BBI, ICSimpleFalse, FNeedSub, Dups));
 891       Enqueued = true;
 892     }
 893   }
 894
 895   BBI.IsEnqueued = Enqueued;
 896   BBI.IsBeingAnalyzed = false;
 897   BBI.IsAnalyzed = true;
 898   return BBI;
 899 }
 900
 901 /// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion
 902 /// candidates.
 903 void IfConverter::AnalyzeBlocks(MachineFunction &MF,
 904                                 std::vector<IfcvtToken*> &Tokens) {
 905   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
 906     MachineBasicBlock *BB = I;
 907     AnalyzeBlock(BB, Tokens);
 908   }
 909
 910   // Sort to favor more complex ifcvt scheme.
 911   std::stable_sort(Tokens.begin(), Tokens.end(), IfcvtTokenCmp);
 912 }
 913
 914 /// canFallThroughTo - Returns true either if ToBB is the next block after BB or
 915 /// that all the intervening blocks are empty (given BB can fall through to its
 916 /// next block).
 917 static bool canFallThroughTo(MachineBasicBlock *BB, MachineBasicBlock *ToBB) {
 918   MachineFunction::iterator PI = BB;
 919   MachineFunction::iterator I = llvm::next(PI);
 920   MachineFunction::iterator TI = ToBB;
 921   MachineFunction::iterator E = BB->getParent()->end();
 922   while (I != TI) {
 923     // Check isSuccessor to avoid case where the next block is empty, but
 924     // it's not a successor.
 925     if (I == E || !I->empty() || !PI->isSuccessor(I))
 926       return false;
 927     PI = I++;
 928   }
 929   return true;
 930 }
 931
 932 /// InvalidatePreds - Invalidate predecessor BB info so it would be re-analyzed
 933 /// to determine if it can be if-converted. If predecessor is already enqueued,
 934 /// dequeue it!
 935 void IfConverter::InvalidatePreds(MachineBasicBlock *BB) {
 936   for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
 937          E = BB->pred_end(); PI != E; ++PI) {
 938     BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()];
 939     if (PBBI.IsDone || PBBI.BB == BB)
 940       continue;
 941     PBBI.IsAnalyzed = false;
 942     PBBI.IsEnqueued = false;
 943   }
 944 }
 945
 946 /// InsertUncondBranch - Inserts an unconditional branch from BB to ToBB.
 947 ///
 948 static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB,
 949                                const TargetInstrInfo *TII) {
 950   DebugLoc dl;  // FIXME: this is nowhere
 951   SmallVector<MachineOperand, 0> NoCond;
 952   TII->InsertBranch(*BB, ToBB, NULL, NoCond, dl);
 953 }
 954
 955 /// RemoveExtraEdges - Remove true / false edges if either / both are no longer
 956 /// successors.
 957 void IfConverter::RemoveExtraEdges(BBInfo &BBI) {
 958   MachineBasicBlock *TBB = NULL, *FBB = NULL;
 959   SmallVector<MachineOperand, 4> Cond;
 960   if (!TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond))
 961     BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
 962 }
 963
 964 /// InitPredRedefs / UpdatePredRedefs - Defs by predicated instructions are
 965 /// modeled as read + write (sort like two-address instructions). These
 966 /// routines track register liveness and add implicit uses to if-converted
 967 /// instructions to conform to the model.
 968 static void InitPredRedefs(MachineBasicBlock *BB, SmallSet<unsigned,4> &Redefs,
 969                            const TargetRegisterInfo *TRI) {
 970   for (MachineBasicBlock::livein_iterator I = BB->livein_begin(),
 971          E = BB->livein_end(); I != E; ++I) {
 972     unsigned Reg = *I;
 973     Redefs.insert(Reg);
 974     for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
 975       Redefs.insert(*SubRegs);
 976   }
 977 }
 978
 979 static void UpdatePredRedefs(MachineInstr *MI, SmallSet<unsigned,4> &Redefs,
 980                              const TargetRegisterInfo *TRI,
 981                              bool AddImpUse = false) {
 982   SmallVector<unsigned, 4> Defs;
 983   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 984     const MachineOperand &MO = MI->getOperand(i);
 985     if (!MO.isReg())
 986       continue;
 987     unsigned Reg = MO.getReg();
 988     if (!Reg)
 989       continue;
 990     if (MO.isDef())
 991       Defs.push_back(Reg);
 992     else if (MO.isKill()) {
 993       Redefs.erase(Reg);
 994       for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
 995         Redefs.erase(*SubRegs);
 996     }
 997   }
 998   MachineInstrBuilder MIB(*MI->getParent()->getParent(), MI);
 999   for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
1000     unsigned Reg = Defs[i];
1001     if (!Redefs.insert(Reg)) {
1002       if (AddImpUse)
1003         // Treat predicated update as read + write.
1004         MIB.addReg(Reg, RegState::Implicit | RegState::Undef);
1005     } else {
1006       for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
1007         Redefs.insert(*SubRegs);
1008     }
1009   }
1010 }
1011
1012 static void UpdatePredRedefs(MachineBasicBlock::iterator I,
1013                              MachineBasicBlock::iterator E,
1014                              SmallSet<unsigned,4> &Redefs,
1015                              const TargetRegisterInfo *TRI) {
1016   while (I != E) {
1017     UpdatePredRedefs(I, Redefs, TRI);
1018     ++I;
1019   }
1020 }
1021
1022 /// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG.
1023 ///
1024 bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {
1025   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
1026   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1027   BBInfo *CvtBBI = &TrueBBI;
1028   BBInfo *NextBBI = &FalseBBI;
1029
1030   SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
1031   if (Kind == ICSimpleFalse)
1032     std::swap(CvtBBI, NextBBI);
1033
1034   if (CvtBBI->IsDone ||
1035       (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) {
1036     // Something has changed. It's no longer safe to predicate this block.
1037     BBI.IsAnalyzed = false;
1038     CvtBBI->IsAnalyzed = false;
1039     return false;
1040   }
1041
1042   if (Kind == ICSimpleFalse)
1043     if (TII->ReverseBranchCondition(Cond))
1044       llvm_unreachable("Unable to reverse branch condition!");
1045
1046   // Initialize liveins to the first BB. These are potentiall redefined by
1047   // predicated instructions.
1048   SmallSet<unsigned, 4> Redefs;
1049   InitPredRedefs(CvtBBI->BB, Redefs, TRI);
1050   InitPredRedefs(NextBBI->BB, Redefs, TRI);
1051
1052   if (CvtBBI->BB->pred_size() > 1) {
1053     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1054     // Copy instructions in the true block, predicate them, and add them to
1055     // the entry block.
1056     CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs);
1057
1058     // RemoveExtraEdges won't work if the block has an unanalyzable branch, so
1059     // explicitly remove CvtBBI as a successor.
1060     BBI.BB->removeSuccessor(CvtBBI->BB);
1061   } else {
1062     PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond, Redefs);
1063
1064     // Merge converted block into entry block.
1065     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1066     MergeBlocks(BBI, *CvtBBI);
1067   }
1068
1069   bool IterIfcvt = true;
1070   if (!canFallThroughTo(BBI.BB, NextBBI->BB)) {
1071     InsertUncondBranch(BBI.BB, NextBBI->BB, TII);
1072     BBI.HasFallThrough = false;
1073     // Now ifcvt'd block will look like this:
1074     // BB:
1075     // ...
1076     // t, f = cmp
1077     // if t op
1078     // b BBf
1079     //
1080     // We cannot further ifcvt this block because the unconditional branch
1081     // will have to be predicated on the new condition, that will not be
1082     // available if cmp executes.
1083     IterIfcvt = false;
1084   }
1085
1086   RemoveExtraEdges(BBI);
1087
1088   // Update block info. BB can be iteratively if-converted.
1089   if (!IterIfcvt)
1090     BBI.IsDone = true;
1091   InvalidatePreds(BBI.BB);
1092   CvtBBI->IsDone = true;
1093
1094   // FIXME: Must maintain LiveIns.
1095   return true;
1096 }
1097
1098 /// IfConvertTriangle - If convert a triangle sub-CFG.
1099 ///
1100 bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
1101   BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
1102   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1103   BBInfo *CvtBBI = &TrueBBI;
1104   BBInfo *NextBBI = &FalseBBI;
1105   DebugLoc dl;  // FIXME: this is nowhere
1106
1107   SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
1108   if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
1109     std::swap(CvtBBI, NextBBI);
1110
1111   if (CvtBBI->IsDone ||
1112       (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) {
1113     // Something has changed. It's no longer safe to predicate this block.
1114     BBI.IsAnalyzed = false;
1115     CvtBBI->IsAnalyzed = false;
1116     return false;
1117   }
1118
1119   if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
1120     if (TII->ReverseBranchCondition(Cond))
1121       llvm_unreachable("Unable to reverse branch condition!");
1122
1123   if (Kind == ICTriangleRev || Kind == ICTriangleFRev) {
1124     if (ReverseBranchCondition(*CvtBBI)) {
1125       // BB has been changed, modify its predecessors (except for this
1126       // one) so they don't get ifcvt'ed based on bad intel.
1127       for (MachineBasicBlock::pred_iterator PI = CvtBBI->BB->pred_begin(),
1128              E = CvtBBI->BB->pred_end(); PI != E; ++PI) {
1129         MachineBasicBlock *PBB = *PI;
1130         if (PBB == BBI.BB)
1131           continue;
1132         BBInfo &PBBI = BBAnalysis[PBB->getNumber()];
1133         if (PBBI.IsEnqueued) {
1134           PBBI.IsAnalyzed = false;
1135           PBBI.IsEnqueued = false;
1136         }
1137       }
1138     }
1139   }
1140
1141   // Initialize liveins to the first BB. These are potentially redefined by
1142   // predicated instructions.
1143   SmallSet<unsigned, 4> Redefs;
1144   InitPredRedefs(CvtBBI->BB, Redefs, TRI);
1145   InitPredRedefs(NextBBI->BB, Redefs, TRI);
1146
1147   bool HasEarlyExit = CvtBBI->FalseBB != NULL;
1148   if (CvtBBI->BB->pred_size() > 1) {
1149     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1150     // Copy instructions in the true block, predicate them, and add them to
1151     // the entry block.
1152     CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs, true);
1153
1154     // RemoveExtraEdges won't work if the block has an unanalyzable branch, so
1155     // explicitly remove CvtBBI as a successor.
1156     BBI.BB->removeSuccessor(CvtBBI->BB);
1157   } else {
1158     // Predicate the 'true' block after removing its branch.
1159     CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB);
1160     PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond, Redefs);
1161
1162     // Now merge the entry of the triangle with the true block.
1163     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1164     MergeBlocks(BBI, *CvtBBI, false);
1165   }
1166
1167   // If 'true' block has a 'false' successor, add an exit branch to it.
1168   if (HasEarlyExit) {
1169     SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(),
1170                                            CvtBBI->BrCond.end());
1171     if (TII->ReverseBranchCondition(RevCond))
1172       llvm_unreachable("Unable to reverse branch condition!");
1173     TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond, dl);
1174     BBI.BB->addSuccessor(CvtBBI->FalseBB);
1175   }
1176
1177   // Merge in the 'false' block if the 'false' block has no other
1178   // predecessors. Otherwise, add an unconditional branch to 'false'.
1179   bool FalseBBDead = false;
1180   bool IterIfcvt = true;
1181   bool isFallThrough = canFallThroughTo(BBI.BB, NextBBI->BB);
1182   if (!isFallThrough) {
1183     // Only merge them if the true block does not fallthrough to the false
1184     // block. By not merging them, we make it possible to iteratively
1185     // ifcvt the blocks.
1186     if (!HasEarlyExit &&
1187         NextBBI->BB->pred_size() == 1 && !NextBBI->HasFallThrough) {
1188       MergeBlocks(BBI, *NextBBI);
1189       FalseBBDead = true;
1190     } else {
1191       InsertUncondBranch(BBI.BB, NextBBI->BB, TII);
1192       BBI.HasFallThrough = false;
1193     }
1194     // Mixed predicated and unpredicated code. This cannot be iteratively
1195     // predicated.
1196     IterIfcvt = false;
1197   }
1198
1199   RemoveExtraEdges(BBI);
1200
1201   // Update block info. BB can be iteratively if-converted.
1202   if (!IterIfcvt)
1203     BBI.IsDone = true;
1204   InvalidatePreds(BBI.BB);
1205   CvtBBI->IsDone = true;
1206   if (FalseBBDead)
1207     NextBBI->IsDone = true;
1208
1209   // FIXME: Must maintain LiveIns.
1210   return true;
1211 }
1212
1213 /// IfConvertDiamond - If convert a diamond sub-CFG.
1214 ///
1215 bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
1216                                    unsigned NumDups1, unsigned NumDups2) {
1217   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
1218   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1219   MachineBasicBlock *TailBB = TrueBBI.TrueBB;
1220   // True block must fall through or end with an unanalyzable terminator.
1221   if (!TailBB) {
1222     if (blockAlwaysFallThrough(TrueBBI))
1223       TailBB = FalseBBI.TrueBB;
1224     assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!");
1225   }
1226
1227   if (TrueBBI.IsDone || FalseBBI.IsDone ||
1228       TrueBBI.BB->pred_size() > 1 ||
1229       FalseBBI.BB->pred_size() > 1) {
1230     // Something has changed. It's no longer safe to predicate these blocks.
1231     BBI.IsAnalyzed = false;
1232     TrueBBI.IsAnalyzed = false;
1233     FalseBBI.IsAnalyzed = false;
1234     return false;
1235   }
1236
1237   // Put the predicated instructions from the 'true' block before the
1238   // instructions from the 'false' block, unless the true block would clobber
1239   // the predicate, in which case, do the opposite.
1240   BBInfo *BBI1 = &TrueBBI;
1241   BBInfo *BBI2 = &FalseBBI;
1242   SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
1243   if (TII->ReverseBranchCondition(RevCond))
1244     llvm_unreachable("Unable to reverse branch condition!");
1245   SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond;
1246   SmallVector<MachineOperand, 4> *Cond2 = &RevCond;
1247
1248   // Figure out the more profitable ordering.
1249   bool DoSwap = false;
1250   if (TrueBBI.ClobbersPred && !FalseBBI.ClobbersPred)
1251     DoSwap = true;
1252   else if (TrueBBI.ClobbersPred == FalseBBI.ClobbersPred) {
1253     if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)
1254       DoSwap = true;
1255   }
1256   if (DoSwap) {
1257     std::swap(BBI1, BBI2);
1258     std::swap(Cond1, Cond2);
1259   }
1260
1261   // Remove the conditional branch from entry to the blocks.
1262   BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1263
1264   // Initialize liveins to the first BB. These are potentially redefined by
1265   // predicated instructions.
1266   SmallSet<unsigned, 4> Redefs;
1267   InitPredRedefs(BBI1->BB, Redefs, TRI);
1268
1269   // Remove the duplicated instructions at the beginnings of both paths.
1270   MachineBasicBlock::iterator DI1 = BBI1->BB->begin();
1271   MachineBasicBlock::iterator DI2 = BBI2->BB->begin();
1272   MachineBasicBlock::iterator DIE1 = BBI1->BB->end();
1273   MachineBasicBlock::iterator DIE2 = BBI2->BB->end();
1274   // Skip dbg_value instructions
1275   while (DI1 != DIE1 && DI1->isDebugValue())
1276     ++DI1;
1277   while (DI2 != DIE2 && DI2->isDebugValue())
1278     ++DI2;
1279   BBI1->NonPredSize -= NumDups1;
1280   BBI2->NonPredSize -= NumDups1;
1281
1282   // Skip past the dups on each side separately since there may be
1283   // differing dbg_value entries.
1284   for (unsigned i = 0; i < NumDups1; ++DI1) {
1285     if (!DI1->isDebugValue())
1286       ++i;
1287   }
1288   while (NumDups1 != 0) {
1289     ++DI2;
1290     if (!DI2->isDebugValue())
1291       --NumDups1;
1292   }
1293
1294   UpdatePredRedefs(BBI1->BB->begin(), DI1, Redefs, TRI);
1295   BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1);
1296   BBI2->BB->erase(BBI2->BB->begin(), DI2);
1297
1298   // Remove branch from 'true' block and remove duplicated instructions.
1299   BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB);
1300   DI1 = BBI1->BB->end();
1301   for (unsigned i = 0; i != NumDups2; ) {
1302     // NumDups2 only counted non-dbg_value instructions, so this won't
1303     // run off the head of the list.
1304     assert (DI1 != BBI1->BB->begin());
1305     --DI1;
1306     // skip dbg_value instructions
1307     if (!DI1->isDebugValue())
1308       ++i;
1309   }
1310   BBI1->BB->erase(DI1, BBI1->BB->end());
1311
1312   // Remove 'false' block branch and find the last instruction to predicate.
1313   BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB);
1314   DI2 = BBI2->BB->end();
1315   while (NumDups2 != 0) {
1316     // NumDups2 only counted non-dbg_value instructions, so this won't
1317     // run off the head of the list.
1318     assert (DI2 != BBI2->BB->begin());
1319     --DI2;
1320     // skip dbg_value instructions
1321     if (!DI2->isDebugValue())
1322       --NumDups2;
1323   }
1324
1325   // Remember which registers would later be defined by the false block.
1326   // This allows us not to predicate instructions in the true block that would
1327   // later be re-defined. That is, rather than
1328   //   subeq  r0, r1, #1
1329   //   addne  r0, r1, #1
1330   // generate:
1331   //   sub    r0, r1, #1
1332   //   addne  r0, r1, #1
1333   SmallSet<unsigned, 4> RedefsByFalse;
1334   SmallSet<unsigned, 4> ExtUses;
1335   if (TII->isProfitableToUnpredicate(*BBI1->BB, *BBI2->BB)) {
1336     for (MachineBasicBlock::iterator FI = BBI2->BB->begin(); FI != DI2; ++FI) {
1337       if (FI->isDebugValue())
1338         continue;
1339       SmallVector<unsigned, 4> Defs;
1340       for (unsigned i = 0, e = FI->getNumOperands(); i != e; ++i) {
1341         const MachineOperand &MO = FI->getOperand(i);
1342         if (!MO.isReg())
1343           continue;
1344         unsigned Reg = MO.getReg();
1345         if (!Reg)
1346           continue;
1347         if (MO.isDef()) {
1348           Defs.push_back(Reg);
1349         } else if (!RedefsByFalse.count(Reg)) {
1350           // These are defined before ctrl flow reach the 'false' instructions.
1351           // They cannot be modified by the 'true' instructions.
1352           ExtUses.insert(Reg);
1353           for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
1354             ExtUses.insert(*SubRegs);
1355         }
1356       }
1357
1358       for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
1359         unsigned Reg = Defs[i];
1360         if (!ExtUses.count(Reg)) {
1361           RedefsByFalse.insert(Reg);
1362           for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
1363             RedefsByFalse.insert(*SubRegs);
1364         }
1365       }
1366     }
1367   }
1368
1369   // Predicate the 'true' block.
1370   PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1, Redefs, &RedefsByFalse);
1371
1372   // Predicate the 'false' block.
1373   PredicateBlock(*BBI2, DI2, *Cond2, Redefs);
1374
1375   // Merge the true block into the entry of the diamond.
1376   MergeBlocks(BBI, *BBI1, TailBB == 0);
1377   MergeBlocks(BBI, *BBI2, TailBB == 0);
1378
1379   // If the if-converted block falls through or unconditionally branches into
1380   // the tail block, and the tail block does not have other predecessors, then
1381   // fold the tail block in as well. Otherwise, unless it falls through to the
1382   // tail, add a unconditional branch to it.
1383   if (TailBB) {
1384     BBInfo &TailBBI = BBAnalysis[TailBB->getNumber()];
1385     bool CanMergeTail = !TailBBI.HasFallThrough;
1386     // There may still be a fall-through edge from BBI1 or BBI2 to TailBB;
1387     // check if there are any other predecessors besides those.
1388     unsigned NumPreds = TailBB->pred_size();
1389     if (NumPreds > 1)
1390       CanMergeTail = false;
1391     else if (NumPreds == 1 && CanMergeTail) {
1392       MachineBasicBlock::pred_iterator PI = TailBB->pred_begin();
1393       if (*PI != BBI1->BB && *PI != BBI2->BB)
1394         CanMergeTail = false;
1395     }
1396     if (CanMergeTail) {
1397       MergeBlocks(BBI, TailBBI);
1398       TailBBI.IsDone = true;
1399     } else {
1400       BBI.BB->addSuccessor(TailBB);
1401       InsertUncondBranch(BBI.BB, TailBB, TII);
1402       BBI.HasFallThrough = false;
1403     }
1404   }
1405
1406   // RemoveExtraEdges won't work if the block has an unanalyzable branch,
1407   // which can happen here if TailBB is unanalyzable and is merged, so
1408   // explicitly remove BBI1 and BBI2 as successors.
1409   BBI.BB->removeSuccessor(BBI1->BB);
1410   BBI.BB->removeSuccessor(BBI2->BB);
1411   RemoveExtraEdges(BBI);
1412
1413   // Update block info.
1414   BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;
1415   InvalidatePreds(BBI.BB);
1416
1417   // FIXME: Must maintain LiveIns.
1418   return true;
1419 }
1420
1421 static bool MaySpeculate(const MachineInstr *MI,
1422                          SmallSet<unsigned, 4> &LaterRedefs,
1423                          const TargetInstrInfo *TII) {
1424   bool SawStore = true;
1425   if (!MI->isSafeToMove(TII, 0, SawStore))
1426     return false;
1427
1428   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1429     const MachineOperand &MO = MI->getOperand(i);
1430     if (!MO.isReg())
1431       continue;
1432     unsigned Reg = MO.getReg();
1433     if (!Reg)
1434       continue;
1435     if (MO.isDef() && !LaterRedefs.count(Reg))
1436       return false;
1437   }
1438
1439   return true;
1440 }
1441
1442 /// PredicateBlock - Predicate instructions from the start of the block to the
1443 /// specified end with the specified condition.
1444 void IfConverter::PredicateBlock(BBInfo &BBI,
1445                                  MachineBasicBlock::iterator E,
1446                                  SmallVectorImpl<MachineOperand> &Cond,
1447                                  SmallSet<unsigned, 4> &Redefs,
1448                                  SmallSet<unsigned, 4> *LaterRedefs) {
1449   bool AnyUnpred = false;
1450   bool MaySpec = LaterRedefs != 0;
1451   for (MachineBasicBlock::iterator I = BBI.BB->begin(); I != E; ++I) {
1452     if (I->isDebugValue() || TII->isPredicated(I))
1453       continue;
1454     // It may be possible not to predicate an instruction if it's the 'true'
1455     // side of a diamond and the 'false' side may re-define the instruction's
1456     // defs.
1457     if (MaySpec && MaySpeculate(I, *LaterRedefs, TII)) {
1458       AnyUnpred = true;
1459       continue;
1460     }
1461     // If any instruction is predicated, then every instruction after it must
1462     // be predicated.
1463     MaySpec = false;
1464     if (!TII->PredicateInstruction(I, Cond)) {
1465 #ifndef NDEBUG
1466       dbgs() << "Unable to predicate " << *I << "!\n";
1467 #endif
1468       llvm_unreachable(0);
1469     }
1470
1471     // If the predicated instruction now redefines a register as the result of
1472     // if-conversion, add an implicit kill.
1473     UpdatePredRedefs(I, Redefs, TRI, true);
1474   }
1475
1476   std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate));
1477
1478   BBI.IsAnalyzed = false;
1479   BBI.NonPredSize = 0;
1480
1481   ++NumIfConvBBs;
1482   if (AnyUnpred)
1483     ++NumUnpred;
1484 }
1485
1486 /// CopyAndPredicateBlock - Copy and predicate instructions from source BB to
1487 /// the destination block. Skip end of block branches if IgnoreBr is true.
1488 void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
1489                                         SmallVectorImpl<MachineOperand> &Cond,
1490                                         SmallSet<unsigned, 4> &Redefs,
1491                                         bool IgnoreBr) {
1492   MachineFunction &MF = *ToBBI.BB->getParent();
1493
1494   for (MachineBasicBlock::iterator I = FromBBI.BB->begin(),
1495          E = FromBBI.BB->end(); I != E; ++I) {
1496     // Do not copy the end of the block branches.
1497     if (IgnoreBr && I->isBranch())
1498       break;
1499
1500     MachineInstr *MI = MF.CloneMachineInstr(I);
1501     ToBBI.BB->insert(ToBBI.BB->end(), MI);
1502     ToBBI.NonPredSize++;
1503     unsigned ExtraPredCost = 0;
1504     unsigned NumCycles = TII->getInstrLatency(InstrItins, &*I, &ExtraPredCost);
1505     if (NumCycles > 1)
1506       ToBBI.ExtraCost += NumCycles-1;
1507     ToBBI.ExtraCost2 += ExtraPredCost;
1508
1509     if (!TII->isPredicated(I) && !MI->isDebugValue()) {
1510       if (!TII->PredicateInstruction(MI, Cond)) {
1511 #ifndef NDEBUG
1512         dbgs() << "Unable to predicate " << *I << "!\n";
1513 #endif
1514         llvm_unreachable(0);
1515       }
1516     }
1517
1518     // If the predicated instruction now redefines a register as the result of
1519     // if-conversion, add an implicit kill.
1520     UpdatePredRedefs(MI, Redefs, TRI, true);
1521   }
1522
1523   if (!IgnoreBr) {
1524     std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
1525                                            FromBBI.BB->succ_end());
1526     MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
1527     MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;
1528
1529     for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
1530       MachineBasicBlock *Succ = Succs[i];
1531       // Fallthrough edge can't be transferred.
1532       if (Succ == FallThrough)
1533         continue;
1534       ToBBI.BB->addSuccessor(Succ);
1535     }
1536   }
1537
1538   std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
1539             std::back_inserter(ToBBI.Predicate));
1540   std::copy(Cond.begin(), Cond.end(), std::back_inserter(ToBBI.Predicate));
1541
1542   ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
1543   ToBBI.IsAnalyzed = false;
1544
1545   ++NumDupBBs;
1546 }
1547
1548 /// MergeBlocks - Move all instructions from FromBB to the end of ToBB.
1549 /// This will leave FromBB as an empty block, so remove all of its
1550 /// successor edges except for the fall-through edge.  If AddEdges is true,
1551 /// i.e., when FromBBI's branch is being moved, add those successor edges to
1552 /// ToBBI.
1553 void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
1554   ToBBI.BB->splice(ToBBI.BB->end(),
1555                    FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end());
1556
1557   std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
1558                                          FromBBI.BB->succ_end());
1559   MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
1560   MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;
1561
1562   for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
1563     MachineBasicBlock *Succ = Succs[i];
1564     // Fallthrough edge can't be transferred.
1565     if (Succ == FallThrough)
1566       continue;
1567     FromBBI.BB->removeSuccessor(Succ);
1568     if (AddEdges && !ToBBI.BB->isSuccessor(Succ))
1569       ToBBI.BB->addSuccessor(Succ);
1570   }
1571
1572   // Now FromBBI always falls through to the next block!
1573   if (NBB && !FromBBI.BB->isSuccessor(NBB))
1574     FromBBI.BB->addSuccessor(NBB);
1575
1576   std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
1577             std::back_inserter(ToBBI.Predicate));
1578   FromBBI.Predicate.clear();
1579
1580   ToBBI.NonPredSize += FromBBI.NonPredSize;
1581   ToBBI.ExtraCost += FromBBI.ExtraCost;
1582   ToBBI.ExtraCost2 += FromBBI.ExtraCost2;
1583   FromBBI.NonPredSize = 0;
1584   FromBBI.ExtraCost = 0;
1585   FromBBI.ExtraCost2 = 0;
1586
1587   ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
1588   ToBBI.HasFallThrough = FromBBI.HasFallThrough;
1589   ToBBI.IsAnalyzed = false;
1590   FromBBI.IsAnalyzed = false;
1591 }