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