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     for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
 974          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       for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
 994            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 (CvtBBI->BB->hasAddressTaken())
1043     // Conservatively abort if-conversion if BB's address is taken.
1044     return false;
1045
1046   if (Kind == ICSimpleFalse)
1047     if (TII->ReverseBranchCondition(Cond))
1048       llvm_unreachable("Unable to reverse branch condition!");
1049
1050   // Initialize liveins to the first BB. These are potentiall redefined by
1051   // predicated instructions.
1052   SmallSet<unsigned, 4> Redefs;
1053   InitPredRedefs(CvtBBI->BB, Redefs, TRI);
1054   InitPredRedefs(NextBBI->BB, Redefs, TRI);
1055
1056   if (CvtBBI->BB->pred_size() > 1) {
1057     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1058     // Copy instructions in the true block, predicate them, and add them to
1059     // the entry block.
1060     CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs);
1061
1062     // RemoveExtraEdges won't work if the block has an unanalyzable branch, so
1063     // explicitly remove CvtBBI as a successor.
1064     BBI.BB->removeSuccessor(CvtBBI->BB);
1065   } else {
1066     PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond, Redefs);
1067
1068     // Merge converted block into entry block.
1069     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1070     MergeBlocks(BBI, *CvtBBI);
1071   }
1072
1073   bool IterIfcvt = true;
1074   if (!canFallThroughTo(BBI.BB, NextBBI->BB)) {
1075     InsertUncondBranch(BBI.BB, NextBBI->BB, TII);
1076     BBI.HasFallThrough = false;
1077     // Now ifcvt'd block will look like this:
1078     // BB:
1079     // ...
1080     // t, f = cmp
1081     // if t op
1082     // b BBf
1083     //
1084     // We cannot further ifcvt this block because the unconditional branch
1085     // will have to be predicated on the new condition, that will not be
1086     // available if cmp executes.
1087     IterIfcvt = false;
1088   }
1089
1090   RemoveExtraEdges(BBI);
1091
1092   // Update block info. BB can be iteratively if-converted.
1093   if (!IterIfcvt)
1094     BBI.IsDone = true;
1095   InvalidatePreds(BBI.BB);
1096   CvtBBI->IsDone = true;
1097
1098   // FIXME: Must maintain LiveIns.
1099   return true;
1100 }
1101
1102 /// IfConvertTriangle - If convert a triangle sub-CFG.
1103 ///
1104 bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
1105   BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
1106   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1107   BBInfo *CvtBBI = &TrueBBI;
1108   BBInfo *NextBBI = &FalseBBI;
1109   DebugLoc dl;  // FIXME: this is nowhere
1110
1111   SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
1112   if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
1113     std::swap(CvtBBI, NextBBI);
1114
1115   if (CvtBBI->IsDone ||
1116       (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) {
1117     // Something has changed. It's no longer safe to predicate this block.
1118     BBI.IsAnalyzed = false;
1119     CvtBBI->IsAnalyzed = false;
1120     return false;
1121   }
1122
1123   if (CvtBBI->BB->hasAddressTaken())
1124     // Conservatively abort if-conversion if BB's address is taken.
1125     return false;
1126
1127   if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
1128     if (TII->ReverseBranchCondition(Cond))
1129       llvm_unreachable("Unable to reverse branch condition!");
1130
1131   if (Kind == ICTriangleRev || Kind == ICTriangleFRev) {
1132     if (ReverseBranchCondition(*CvtBBI)) {
1133       // BB has been changed, modify its predecessors (except for this
1134       // one) so they don't get ifcvt'ed based on bad intel.
1135       for (MachineBasicBlock::pred_iterator PI = CvtBBI->BB->pred_begin(),
1136              E = CvtBBI->BB->pred_end(); PI != E; ++PI) {
1137         MachineBasicBlock *PBB = *PI;
1138         if (PBB == BBI.BB)
1139           continue;
1140         BBInfo &PBBI = BBAnalysis[PBB->getNumber()];
1141         if (PBBI.IsEnqueued) {
1142           PBBI.IsAnalyzed = false;
1143           PBBI.IsEnqueued = false;
1144         }
1145       }
1146     }
1147   }
1148
1149   // Initialize liveins to the first BB. These are potentially redefined by
1150   // predicated instructions.
1151   SmallSet<unsigned, 4> Redefs;
1152   InitPredRedefs(CvtBBI->BB, Redefs, TRI);
1153   InitPredRedefs(NextBBI->BB, Redefs, TRI);
1154
1155   bool HasEarlyExit = CvtBBI->FalseBB != NULL;
1156   if (CvtBBI->BB->pred_size() > 1) {
1157     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1158     // Copy instructions in the true block, predicate them, and add them to
1159     // the entry block.
1160     CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs, true);
1161
1162     // RemoveExtraEdges won't work if the block has an unanalyzable branch, so
1163     // explicitly remove CvtBBI as a successor.
1164     BBI.BB->removeSuccessor(CvtBBI->BB);
1165   } else {
1166     // Predicate the 'true' block after removing its branch.
1167     CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB);
1168     PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond, Redefs);
1169
1170     // Now merge the entry of the triangle with the true block.
1171     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1172     MergeBlocks(BBI, *CvtBBI, false);
1173   }
1174
1175   // If 'true' block has a 'false' successor, add an exit branch to it.
1176   if (HasEarlyExit) {
1177     SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(),
1178                                            CvtBBI->BrCond.end());
1179     if (TII->ReverseBranchCondition(RevCond))
1180       llvm_unreachable("Unable to reverse branch condition!");
1181     TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond, dl);
1182     BBI.BB->addSuccessor(CvtBBI->FalseBB);
1183   }
1184
1185   // Merge in the 'false' block if the 'false' block has no other
1186   // predecessors. Otherwise, add an unconditional branch to 'false'.
1187   bool FalseBBDead = false;
1188   bool IterIfcvt = true;
1189   bool isFallThrough = canFallThroughTo(BBI.BB, NextBBI->BB);
1190   if (!isFallThrough) {
1191     // Only merge them if the true block does not fallthrough to the false
1192     // block. By not merging them, we make it possible to iteratively
1193     // ifcvt the blocks.
1194     if (!HasEarlyExit &&
1195         NextBBI->BB->pred_size() == 1 && !NextBBI->HasFallThrough &&
1196         !NextBBI->BB->hasAddressTaken()) {
1197       MergeBlocks(BBI, *NextBBI);
1198       FalseBBDead = true;
1199     } else {
1200       InsertUncondBranch(BBI.BB, NextBBI->BB, TII);
1201       BBI.HasFallThrough = false;
1202     }
1203     // Mixed predicated and unpredicated code. This cannot be iteratively
1204     // predicated.
1205     IterIfcvt = false;
1206   }
1207
1208   RemoveExtraEdges(BBI);
1209
1210   // Update block info. BB can be iteratively if-converted.
1211   if (!IterIfcvt)
1212     BBI.IsDone = true;
1213   InvalidatePreds(BBI.BB);
1214   CvtBBI->IsDone = true;
1215   if (FalseBBDead)
1216     NextBBI->IsDone = true;
1217
1218   // FIXME: Must maintain LiveIns.
1219   return true;
1220 }
1221
1222 /// IfConvertDiamond - If convert a diamond sub-CFG.
1223 ///
1224 bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
1225                                    unsigned NumDups1, unsigned NumDups2) {
1226   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
1227   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1228   MachineBasicBlock *TailBB = TrueBBI.TrueBB;
1229   // True block must fall through or end with an unanalyzable terminator.
1230   if (!TailBB) {
1231     if (blockAlwaysFallThrough(TrueBBI))
1232       TailBB = FalseBBI.TrueBB;
1233     assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!");
1234   }
1235
1236   if (TrueBBI.IsDone || FalseBBI.IsDone ||
1237       TrueBBI.BB->pred_size() > 1 ||
1238       FalseBBI.BB->pred_size() > 1) {
1239     // Something has changed. It's no longer safe to predicate these blocks.
1240     BBI.IsAnalyzed = false;
1241     TrueBBI.IsAnalyzed = false;
1242     FalseBBI.IsAnalyzed = false;
1243     return false;
1244   }
1245
1246   if (TrueBBI.BB->hasAddressTaken() || FalseBBI.BB->hasAddressTaken())
1247     // Conservatively abort if-conversion if either BB has its address taken.
1248     return false;
1249
1250   // Put the predicated instructions from the 'true' block before the
1251   // instructions from the 'false' block, unless the true block would clobber
1252   // the predicate, in which case, do the opposite.
1253   BBInfo *BBI1 = &TrueBBI;
1254   BBInfo *BBI2 = &FalseBBI;
1255   SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
1256   if (TII->ReverseBranchCondition(RevCond))
1257     llvm_unreachable("Unable to reverse branch condition!");
1258   SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond;
1259   SmallVector<MachineOperand, 4> *Cond2 = &RevCond;
1260
1261   // Figure out the more profitable ordering.
1262   bool DoSwap = false;
1263   if (TrueBBI.ClobbersPred && !FalseBBI.ClobbersPred)
1264     DoSwap = true;
1265   else if (TrueBBI.ClobbersPred == FalseBBI.ClobbersPred) {
1266     if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)
1267       DoSwap = true;
1268   }
1269   if (DoSwap) {
1270     std::swap(BBI1, BBI2);
1271     std::swap(Cond1, Cond2);
1272   }
1273
1274   // Remove the conditional branch from entry to the blocks.
1275   BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1276
1277   // Initialize liveins to the first BB. These are potentially redefined by
1278   // predicated instructions.
1279   SmallSet<unsigned, 4> Redefs;
1280   InitPredRedefs(BBI1->BB, Redefs, TRI);
1281
1282   // Remove the duplicated instructions at the beginnings of both paths.
1283   MachineBasicBlock::iterator DI1 = BBI1->BB->begin();
1284   MachineBasicBlock::iterator DI2 = BBI2->BB->begin();
1285   MachineBasicBlock::iterator DIE1 = BBI1->BB->end();
1286   MachineBasicBlock::iterator DIE2 = BBI2->BB->end();
1287   // Skip dbg_value instructions
1288   while (DI1 != DIE1 && DI1->isDebugValue())
1289     ++DI1;
1290   while (DI2 != DIE2 && DI2->isDebugValue())
1291     ++DI2;
1292   BBI1->NonPredSize -= NumDups1;
1293   BBI2->NonPredSize -= NumDups1;
1294
1295   // Skip past the dups on each side separately since there may be
1296   // differing dbg_value entries.
1297   for (unsigned i = 0; i < NumDups1; ++DI1) {
1298     if (!DI1->isDebugValue())
1299       ++i;
1300   }
1301   while (NumDups1 != 0) {
1302     ++DI2;
1303     if (!DI2->isDebugValue())
1304       --NumDups1;
1305   }
1306
1307   UpdatePredRedefs(BBI1->BB->begin(), DI1, Redefs, TRI);
1308   BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1);
1309   BBI2->BB->erase(BBI2->BB->begin(), DI2);
1310
1311   // Remove branch from 'true' block and remove duplicated instructions.
1312   BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB);
1313   DI1 = BBI1->BB->end();
1314   for (unsigned i = 0; i != NumDups2; ) {
1315     // NumDups2 only counted non-dbg_value instructions, so this won't
1316     // run off the head of the list.
1317     assert (DI1 != BBI1->BB->begin());
1318     --DI1;
1319     // skip dbg_value instructions
1320     if (!DI1->isDebugValue())
1321       ++i;
1322   }
1323   BBI1->BB->erase(DI1, BBI1->BB->end());
1324
1325   // Remove 'false' block branch and find the last instruction to predicate.
1326   BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB);
1327   DI2 = BBI2->BB->end();
1328   while (NumDups2 != 0) {
1329     // NumDups2 only counted non-dbg_value instructions, so this won't
1330     // run off the head of the list.
1331     assert (DI2 != BBI2->BB->begin());
1332     --DI2;
1333     // skip dbg_value instructions
1334     if (!DI2->isDebugValue())
1335       --NumDups2;
1336   }
1337
1338   // Remember which registers would later be defined by the false block.
1339   // This allows us not to predicate instructions in the true block that would
1340   // later be re-defined. That is, rather than
1341   //   subeq  r0, r1, #1
1342   //   addne  r0, r1, #1
1343   // generate:
1344   //   sub    r0, r1, #1
1345   //   addne  r0, r1, #1
1346   SmallSet<unsigned, 4> RedefsByFalse;
1347   SmallSet<unsigned, 4> ExtUses;
1348   if (TII->isProfitableToUnpredicate(*BBI1->BB, *BBI2->BB)) {
1349     for (MachineBasicBlock::iterator FI = BBI2->BB->begin(); FI != DI2; ++FI) {
1350       if (FI->isDebugValue())
1351         continue;
1352       SmallVector<unsigned, 4> Defs;
1353       for (unsigned i = 0, e = FI->getNumOperands(); i != e; ++i) {
1354         const MachineOperand &MO = FI->getOperand(i);
1355         if (!MO.isReg())
1356           continue;
1357         unsigned Reg = MO.getReg();
1358         if (!Reg)
1359           continue;
1360         if (MO.isDef()) {
1361           Defs.push_back(Reg);
1362         } else if (!RedefsByFalse.count(Reg)) {
1363           // These are defined before ctrl flow reach the 'false' instructions.
1364           // They cannot be modified by the 'true' instructions.
1365           for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
1366                SubRegs.isValid(); ++SubRegs)
1367             ExtUses.insert(*SubRegs);
1368         }
1369       }
1370
1371       for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
1372         unsigned Reg = Defs[i];
1373         if (!ExtUses.count(Reg)) {
1374           for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
1375                SubRegs.isValid(); ++SubRegs)
1376             RedefsByFalse.insert(*SubRegs);
1377         }
1378       }
1379     }
1380   }
1381
1382   // Predicate the 'true' block.
1383   PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1, Redefs, &RedefsByFalse);
1384
1385   // Predicate the 'false' block.
1386   PredicateBlock(*BBI2, DI2, *Cond2, Redefs);
1387
1388   // Merge the true block into the entry of the diamond.
1389   MergeBlocks(BBI, *BBI1, TailBB == 0);
1390   MergeBlocks(BBI, *BBI2, TailBB == 0);
1391
1392   // If the if-converted block falls through or unconditionally branches into
1393   // the tail block, and the tail block does not have other predecessors, then
1394   // fold the tail block in as well. Otherwise, unless it falls through to the
1395   // tail, add a unconditional branch to it.
1396   if (TailBB) {
1397     BBInfo &TailBBI = BBAnalysis[TailBB->getNumber()];
1398     bool CanMergeTail = !TailBBI.HasFallThrough &&
1399       !TailBBI.BB->hasAddressTaken();
1400     // There may still be a fall-through edge from BBI1 or BBI2 to TailBB;
1401     // check if there are any other predecessors besides those.
1402     unsigned NumPreds = TailBB->pred_size();
1403     if (NumPreds > 1)
1404       CanMergeTail = false;
1405     else if (NumPreds == 1 && CanMergeTail) {
1406       MachineBasicBlock::pred_iterator PI = TailBB->pred_begin();
1407       if (*PI != BBI1->BB && *PI != BBI2->BB)
1408         CanMergeTail = false;
1409     }
1410     if (CanMergeTail) {
1411       MergeBlocks(BBI, TailBBI);
1412       TailBBI.IsDone = true;
1413     } else {
1414       BBI.BB->addSuccessor(TailBB);
1415       InsertUncondBranch(BBI.BB, TailBB, TII);
1416       BBI.HasFallThrough = false;
1417     }
1418   }
1419
1420   // RemoveExtraEdges won't work if the block has an unanalyzable branch,
1421   // which can happen here if TailBB is unanalyzable and is merged, so
1422   // explicitly remove BBI1 and BBI2 as successors.
1423   BBI.BB->removeSuccessor(BBI1->BB);
1424   BBI.BB->removeSuccessor(BBI2->BB);
1425   RemoveExtraEdges(BBI);
1426
1427   // Update block info.
1428   BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;
1429   InvalidatePreds(BBI.BB);
1430
1431   // FIXME: Must maintain LiveIns.
1432   return true;
1433 }
1434
1435 static bool MaySpeculate(const MachineInstr *MI,
1436                          SmallSet<unsigned, 4> &LaterRedefs,
1437                          const TargetInstrInfo *TII) {
1438   bool SawStore = true;
1439   if (!MI->isSafeToMove(TII, 0, SawStore))
1440     return false;
1441
1442   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1443     const MachineOperand &MO = MI->getOperand(i);
1444     if (!MO.isReg())
1445       continue;
1446     unsigned Reg = MO.getReg();
1447     if (!Reg)
1448       continue;
1449     if (MO.isDef() && !LaterRedefs.count(Reg))
1450       return false;
1451   }
1452
1453   return true;
1454 }
1455
1456 /// PredicateBlock - Predicate instructions from the start of the block to the
1457 /// specified end with the specified condition.
1458 void IfConverter::PredicateBlock(BBInfo &BBI,
1459                                  MachineBasicBlock::iterator E,
1460                                  SmallVectorImpl<MachineOperand> &Cond,
1461                                  SmallSet<unsigned, 4> &Redefs,
1462                                  SmallSet<unsigned, 4> *LaterRedefs) {
1463   bool AnyUnpred = false;
1464   bool MaySpec = LaterRedefs != 0;
1465   for (MachineBasicBlock::iterator I = BBI.BB->begin(); I != E; ++I) {
1466     if (I->isDebugValue() || TII->isPredicated(I))
1467       continue;
1468     // It may be possible not to predicate an instruction if it's the 'true'
1469     // side of a diamond and the 'false' side may re-define the instruction's
1470     // defs.
1471     if (MaySpec && MaySpeculate(I, *LaterRedefs, TII)) {
1472       AnyUnpred = true;
1473       continue;
1474     }
1475     // If any instruction is predicated, then every instruction after it must
1476     // be predicated.
1477     MaySpec = false;
1478     if (!TII->PredicateInstruction(I, Cond)) {
1479 #ifndef NDEBUG
1480       dbgs() << "Unable to predicate " << *I << "!\n";
1481 #endif
1482       llvm_unreachable(0);
1483     }
1484
1485     // If the predicated instruction now redefines a register as the result of
1486     // if-conversion, add an implicit kill.
1487     UpdatePredRedefs(I, Redefs, TRI, true);
1488   }
1489
1490   std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate));
1491
1492   BBI.IsAnalyzed = false;
1493   BBI.NonPredSize = 0;
1494
1495   ++NumIfConvBBs;
1496   if (AnyUnpred)
1497     ++NumUnpred;
1498 }
1499
1500 /// CopyAndPredicateBlock - Copy and predicate instructions from source BB to
1501 /// the destination block. Skip end of block branches if IgnoreBr is true.
1502 void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
1503                                         SmallVectorImpl<MachineOperand> &Cond,
1504                                         SmallSet<unsigned, 4> &Redefs,
1505                                         bool IgnoreBr) {
1506   MachineFunction &MF = *ToBBI.BB->getParent();
1507
1508   for (MachineBasicBlock::iterator I = FromBBI.BB->begin(),
1509          E = FromBBI.BB->end(); I != E; ++I) {
1510     // Do not copy the end of the block branches.
1511     if (IgnoreBr && I->isBranch())
1512       break;
1513
1514     MachineInstr *MI = MF.CloneMachineInstr(I);
1515     ToBBI.BB->insert(ToBBI.BB->end(), MI);
1516     ToBBI.NonPredSize++;
1517     unsigned ExtraPredCost = 0;
1518     unsigned NumCycles = TII->getInstrLatency(InstrItins, &*I, &ExtraPredCost);
1519     if (NumCycles > 1)
1520       ToBBI.ExtraCost += NumCycles-1;
1521     ToBBI.ExtraCost2 += ExtraPredCost;
1522
1523     if (!TII->isPredicated(I) && !MI->isDebugValue()) {
1524       if (!TII->PredicateInstruction(MI, Cond)) {
1525 #ifndef NDEBUG
1526         dbgs() << "Unable to predicate " << *I << "!\n";
1527 #endif
1528         llvm_unreachable(0);
1529       }
1530     }
1531
1532     // If the predicated instruction now redefines a register as the result of
1533     // if-conversion, add an implicit kill.
1534     UpdatePredRedefs(MI, Redefs, TRI, true);
1535   }
1536
1537   if (!IgnoreBr) {
1538     std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
1539                                            FromBBI.BB->succ_end());
1540     MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
1541     MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;
1542
1543     for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
1544       MachineBasicBlock *Succ = Succs[i];
1545       // Fallthrough edge can't be transferred.
1546       if (Succ == FallThrough)
1547         continue;
1548       ToBBI.BB->addSuccessor(Succ);
1549     }
1550   }
1551
1552   std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
1553             std::back_inserter(ToBBI.Predicate));
1554   std::copy(Cond.begin(), Cond.end(), std::back_inserter(ToBBI.Predicate));
1555
1556   ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
1557   ToBBI.IsAnalyzed = false;
1558
1559   ++NumDupBBs;
1560 }
1561
1562 /// MergeBlocks - Move all instructions from FromBB to the end of ToBB.
1563 /// This will leave FromBB as an empty block, so remove all of its
1564 /// successor edges except for the fall-through edge.  If AddEdges is true,
1565 /// i.e., when FromBBI's branch is being moved, add those successor edges to
1566 /// ToBBI.
1567 void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
1568   assert(!FromBBI.BB->hasAddressTaken() &&
1569          "Removing a BB whose address is taken!");
1570
1571   ToBBI.BB->splice(ToBBI.BB->end(),
1572                    FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end());
1573
1574   std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
1575                                          FromBBI.BB->succ_end());
1576   MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
1577   MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;
1578
1579   for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
1580     MachineBasicBlock *Succ = Succs[i];
1581     // Fallthrough edge can't be transferred.
1582     if (Succ == FallThrough)
1583       continue;
1584     FromBBI.BB->removeSuccessor(Succ);
1585     if (AddEdges && !ToBBI.BB->isSuccessor(Succ))
1586       ToBBI.BB->addSuccessor(Succ);
1587   }
1588
1589   // Now FromBBI always falls through to the next block!
1590   if (NBB && !FromBBI.BB->isSuccessor(NBB))
1591     FromBBI.BB->addSuccessor(NBB);
1592
1593   std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
1594             std::back_inserter(ToBBI.Predicate));
1595   FromBBI.Predicate.clear();
1596
1597   ToBBI.NonPredSize += FromBBI.NonPredSize;
1598   ToBBI.ExtraCost += FromBBI.ExtraCost;
1599   ToBBI.ExtraCost2 += FromBBI.ExtraCost2;
1600   FromBBI.NonPredSize = 0;
1601   FromBBI.ExtraCost = 0;
1602   FromBBI.ExtraCost2 = 0;
1603
1604   ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
1605   ToBBI.HasFallThrough = FromBBI.HasFallThrough;
1606   ToBBI.IsAnalyzed = false;
1607   FromBBI.IsAnalyzed = false;
1608 }