lib/CodeGen/IfConversion.cpp

   1 //===-- IfConversion.cpp - Machine code if conversion pass. ---------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the Evan Cheng and is distributed under
   6 // the University of Illinois Open Source 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 "ifconversion"
  15 #include "llvm/CodeGen/Passes.h"
  16 #include "llvm/CodeGen/MachineModuleInfo.h"
  17 #include "llvm/CodeGen/MachineFunctionPass.h"
  18 #include "llvm/Target/TargetInstrInfo.h"
  19 #include "llvm/Target/TargetLowering.h"
  20 #include "llvm/Target/TargetMachine.h"
  21 #include "llvm/Support/Debug.h"
  22 #include "llvm/ADT/DepthFirstIterator.h"
  23 #include "llvm/ADT/Statistic.h"
  24 using namespace llvm;
  25
  26 STATISTIC(NumIfConvBBs, "Number of if-converted blocks");
  27
  28 namespace {
  29   class IfConverter : public MachineFunctionPass {
  30     enum BBICKind {
  31       ICNotAnalyzed,   // BB has not been analyzed.
  32       ICReAnalyze,     // BB must be re-analyzed.
  33       ICNotClassfied,  // BB data valid, but not classified.
  34       ICEarlyExit,     // BB is entry of an early-exit sub-CFG.
  35       ICTriangle,      // BB is entry of a triangle sub-CFG.
  36       ICDiamond,       // BB is entry of a diamond sub-CFG.
  37       ICChild,         // BB is part of the sub-CFG that'll be predicated.
  38       ICDead           // BB has been converted and merged, it's now dead.
  39     };
  40
  41     /// BBInfo - One per MachineBasicBlock, this is used to cache the result
  42     /// if-conversion feasibility analysis. This includes results from
  43     /// TargetInstrInfo::AnalyzeBranch() (i.e. TBB, FBB, and Cond), and its
  44     /// classification, and common tail block of its successors (if it's a
  45     /// diamond shape), its size, whether it's predicable, and whether any
  46     /// instruction can clobber the 'would-be' predicate.
  47     ///
  48     /// Kind            - Type of block. See BBICKind.
  49     /// NonPredSize     - Number of non-predicated instructions.
  50     /// isPredicable    - Is it predicable. (FIXME: Remove.)
  51     /// hasEarlyExit    - Ends with a return, indirect jump or br to jumptable.
  52     /// ModifyPredicate - FIXME: Not used right now. True if BB would modify
  53     ///                   the predicate (e.g. has cmp, call, etc.)
  54     /// BB              - Corresponding MachineBasicBlock.
  55     /// TrueBB / FalseBB- See AnalyzeBranch().
  56     /// BrCond          - Conditions for end of block conditional branches.
  57     /// Predicate       - Predicate used in the BB.
  58     struct BBInfo {
  59       BBICKind Kind;
  60       unsigned NonPredSize;
  61       bool isPredicable;
  62       bool hasEarlyExit;
  63       bool ModifyPredicate;
  64       MachineBasicBlock *BB;
  65       MachineBasicBlock *TrueBB;
  66       MachineBasicBlock *FalseBB;
  67       MachineBasicBlock *TailBB;
  68       std::vector<MachineOperand> BrCond;
  69       std::vector<MachineOperand> Predicate;
  70       BBInfo() : Kind(ICNotAnalyzed), NonPredSize(0), isPredicable(false),
  71                  hasEarlyExit(false), ModifyPredicate(false),
  72                  BB(0), TrueBB(0), FalseBB(0), TailBB(0) {}
  73     };
  74
  75     /// Roots - Basic blocks that do not have successors. These are the starting
  76     /// points of Graph traversal.
  77     std::vector<MachineBasicBlock*> Roots;
  78
  79     /// BBAnalysis - Results of if-conversion feasibility analysis indexed by
  80     /// basic block number.
  81     std::vector<BBInfo> BBAnalysis;
  82
  83     const TargetLowering *TLI;
  84     const TargetInstrInfo *TII;
  85     bool MadeChange;
  86   public:
  87     static char ID;
  88     IfConverter() : MachineFunctionPass((intptr_t)&ID) {}
  89
  90     virtual bool runOnMachineFunction(MachineFunction &MF);
  91     virtual const char *getPassName() const { return "If converter"; }
  92
  93   private:
  94     void StructuralAnalysis(MachineBasicBlock *BB);
  95     void FeasibilityAnalysis(BBInfo &BBI,
  96                              std::vector<MachineOperand> &Cond);
  97     bool AttemptRestructuring(BBInfo &BBI);
  98     bool AnalyzeBlocks(MachineFunction &MF,
  99                        std::vector<BBInfo*> &Candidates);
 100     void ReTryPreds(MachineBasicBlock *BB);
 101     bool IfConvertEarlyExit(BBInfo &BBI);
 102     bool IfConvertTriangle(BBInfo &BBI);
 103     bool IfConvertDiamond(BBInfo &BBI);
 104     void PredicateBlock(BBInfo &BBI,
 105                         std::vector<MachineOperand> &Cond,
 106                         bool IgnoreTerm = false);
 107     void MergeBlocks(BBInfo &TrueBBI, BBInfo &FalseBBI);
 108   };
 109   char IfConverter::ID = 0;
 110 }
 111
 112 FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); }
 113
 114 bool IfConverter::runOnMachineFunction(MachineFunction &MF) {
 115   TLI = MF.getTarget().getTargetLowering();
 116   TII = MF.getTarget().getInstrInfo();
 117   if (!TII) return false;
 118
 119   MF.RenumberBlocks();
 120   unsigned NumBBs = MF.getNumBlockIDs();
 121   BBAnalysis.resize(NumBBs);
 122
 123   // Look for root nodes, i.e. blocks without successors.
 124   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
 125     if (I->succ_size() == 0)
 126       Roots.push_back(I);
 127
 128   std::vector<BBInfo*> Candidates;
 129   MadeChange = false;
 130   while (true) {
 131     bool Change = false;
 132
 133     // Do an intial analysis for each basic block and finding all the potential
 134     // candidates to perform if-convesion.
 135     Change |= AnalyzeBlocks(MF, Candidates);
 136     while (!Candidates.empty()) {
 137       BBInfo &BBI = *Candidates.back();
 138       Candidates.pop_back();
 139       switch (BBI.Kind) {
 140       default: assert(false && "Unexpected!");
 141         break;
 142       case ICEarlyExit:
 143         Change |= IfConvertEarlyExit(BBI);
 144         break;
 145       case ICTriangle:
 146         Change |= IfConvertTriangle(BBI);
 147         break;
 148       case ICDiamond:
 149         Change |= IfConvertDiamond(BBI);
 150         break;
 151       }
 152     }
 153
 154     MadeChange |= Change;
 155     if (!Change)
 156       break;
 157   }
 158
 159   Roots.clear();
 160   BBAnalysis.clear();
 161
 162   return MadeChange;
 163 }
 164
 165 static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
 166                                          MachineBasicBlock *TrueBB) {
 167   for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
 168          E = BB->succ_end(); SI != E; ++SI) {
 169     MachineBasicBlock *SuccBB = *SI;
 170     if (SuccBB != TrueBB)
 171       return SuccBB;
 172   }
 173   return NULL;
 174 }
 175
 176 /// StructuralAnalysis - Analyze the structure of the sub-CFG starting from
 177 /// the specified block. Record its successors and whether it looks like an
 178 /// if-conversion candidate.
 179 void IfConverter::StructuralAnalysis(MachineBasicBlock *BB) {
 180   BBInfo &BBI = BBAnalysis[BB->getNumber()];
 181
 182   if (BBI.Kind != ICReAnalyze) {
 183     if (BBI.Kind != ICNotAnalyzed)
 184       return;  // Already analyzed.
 185     BBI.BB = BB;
 186     BBI.NonPredSize = std::distance(BB->begin(), BB->end());
 187   }
 188
 189   // Look for 'root' of a simple (non-nested) triangle or diamond.
 190   BBI.Kind = ICNotClassfied;
 191   bool CanAnalyze = !TII->AnalyzeBranch(*BB, BBI.TrueBB, BBI.FalseBB,
 192                                         BBI.BrCond);
 193   // Does it end with a return, indirect jump, or jumptable branch?
 194   BBI.hasEarlyExit = TII->BlockHasNoFallThrough(*BB) && !BBI.TrueBB;
 195   if (!CanAnalyze || !BBI.TrueBB || BBI.BrCond.size() == 0)
 196     return;
 197
 198   // Not a candidate if 'true' block is going to be if-converted.
 199   StructuralAnalysis(BBI.TrueBB);
 200   BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
 201   if (TrueBBI.Kind != ICNotClassfied)
 202     return;
 203
 204   // TODO: Only handle very simple cases for now.
 205   if (TrueBBI.FalseBB || TrueBBI.BrCond.size())
 206     return;
 207
 208   // No false branch. This BB must end with a conditional branch and a
 209   // fallthrough.
 210   if (!BBI.FalseBB)
 211     BBI.FalseBB = findFalseBlock(BB, BBI.TrueBB);
 212   assert(BBI.FalseBB && "Expected to find the fallthrough block!");
 213
 214   // Not a candidate if 'false' block is going to be if-converted.
 215   StructuralAnalysis(BBI.FalseBB);
 216   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
 217   if (FalseBBI.Kind != ICNotClassfied)
 218     return;
 219
 220   // TODO: Only handle very simple cases for now.
 221   if (FalseBBI.FalseBB || FalseBBI.BrCond.size())
 222     return;
 223
 224   unsigned TrueNumPreds  = BBI.TrueBB->pred_size();
 225   unsigned FalseNumPreds = BBI.FalseBB->pred_size();
 226   if ((TrueBBI.hasEarlyExit && TrueNumPreds <= 1) &&
 227       !(FalseBBI.hasEarlyExit && FalseNumPreds <=1)) {
 228     BBI.Kind = ICEarlyExit;
 229     TrueBBI.Kind = ICChild;
 230   } else if (!(TrueBBI.hasEarlyExit && TrueNumPreds <= 1) &&
 231              (FalseBBI.hasEarlyExit && FalseNumPreds <=1)) {
 232     BBI.Kind = ICEarlyExit;
 233     FalseBBI.Kind = ICChild;
 234   } else if (TrueBBI.TrueBB && TrueBBI.TrueBB == BBI.FalseBB) {
 235     // Triangle:
 236     //   EBB
 237     //   | \_
 238     //   |  |
 239     //   | TBB
 240     //   |  /
 241     //   FBB
 242     BBI.Kind = ICTriangle;
 243     TrueBBI.Kind = FalseBBI.Kind = ICChild;
 244   } else if (TrueBBI.TrueBB == FalseBBI.TrueBB &&
 245              TrueNumPreds <= 1 && FalseNumPreds <= 1) {
 246     // Diamond:
 247     //   EBB
 248     //   / \_
 249     //  |   |
 250     // TBB FBB
 251     //   \ /
 252     //  TailBB
 253     // Note MBB can be empty in case both TBB and FBB are return blocks.
 254     BBI.Kind = ICDiamond;
 255     TrueBBI.Kind = FalseBBI.Kind = ICChild;
 256     BBI.TailBB = TrueBBI.TrueBB;
 257   }
 258   return;
 259 }
 260
 261 /// FeasibilityAnalysis - Determine if the block is predicable. In most
 262 /// cases, that means all the instructions in the block has M_PREDICABLE flag.
 263 /// Also checks if the block contains any instruction which can clobber a
 264 /// predicate (e.g. condition code register). If so, the block is not
 265 /// predicable unless it's the last instruction. Note, this function assumes
 266 /// all the terminator instructions can be converted or deleted so it ignore
 267 /// them.
 268 void IfConverter::FeasibilityAnalysis(BBInfo &BBI,
 269                                       std::vector<MachineOperand> &Cond) {
 270   if (BBI.NonPredSize == 0 || BBI.NonPredSize > TLI->getIfCvtBlockSizeLimit())
 271     return;
 272
 273   for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end();
 274        I != E; ++I) {
 275     // TODO: check if instruction clobbers predicate.
 276     if (TII->isTerminatorInstr(I->getOpcode()))
 277       break;
 278     if (!I->isPredicable())
 279       return;
 280   }
 281
 282   if (BBI.Predicate.size() && !TII->SubsumesPredicate(BBI.Predicate, Cond))
 283     return;
 284
 285   BBI.isPredicable = true;
 286 }
 287
 288 /// AttemptRestructuring - Restructure the sub-CFG rooted in the given block to
 289 /// expose more if-conversion opportunities. e.g.
 290 ///
 291 ///                cmp
 292 ///                b le BB1
 293 ///                /  \____
 294 ///               /        |
 295 ///             cmp        |
 296 ///             b eq BB1   |
 297 ///              /  \____  |
 298 ///             /        \ |
 299 ///                      BB1
 300 ///  ==>
 301 ///
 302 ///                cmp
 303 ///                b eq BB1
 304 ///                /  \____
 305 ///               /        |
 306 ///             cmp        |
 307 ///             b le BB1   |
 308 ///              /  \____  |
 309 ///             /        \ |
 310 ///                      BB1
 311 bool IfConverter::AttemptRestructuring(BBInfo &BBI) {
 312   return false;
 313 }
 314
 315 /// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion
 316 /// candidates. It returns true if any CFG restructuring is done to expose more
 317 /// if-conversion opportunities.
 318 bool IfConverter::AnalyzeBlocks(MachineFunction &MF,
 319                                 std::vector<BBInfo*> &Candidates) {
 320   bool Change = false;
 321   std::set<MachineBasicBlock*> Visited;
 322   for (unsigned i = 0, e = Roots.size(); i != e; ++i) {
 323     for (idf_ext_iterator<MachineBasicBlock*> I=idf_ext_begin(Roots[i],Visited),
 324            E = idf_ext_end(Roots[i], Visited); I != E; ++I) {
 325       MachineBasicBlock *BB = *I;
 326       StructuralAnalysis(BB);
 327       BBInfo &BBI = BBAnalysis[BB->getNumber()];
 328       switch (BBI.Kind) {
 329         case ICEarlyExit:
 330         case ICTriangle:
 331         case ICDiamond:
 332           Candidates.push_back(&BBI);
 333           break;
 334         default:
 335           Change |= AttemptRestructuring(BBI);
 336           break;
 337       }
 338     }
 339   }
 340
 341   return Change;
 342 }
 343
 344 /// TransferPreds - Transfer all the predecessors of FromBB to ToBB.
 345 ///
 346 static void TransferPreds(MachineBasicBlock *ToBB, MachineBasicBlock *FromBB) {
 347    std::vector<MachineBasicBlock*> Preds(FromBB->pred_begin(),
 348                                          FromBB->pred_end());
 349     for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
 350       MachineBasicBlock *Pred = Preds[i];
 351       Pred->removeSuccessor(FromBB);
 352       if (!Pred->isSuccessor(ToBB))
 353         Pred->addSuccessor(ToBB);
 354     }
 355 }
 356
 357 /// TransferSuccs - Transfer all the successors of FromBB to ToBB.
 358 ///
 359 static void TransferSuccs(MachineBasicBlock *ToBB, MachineBasicBlock *FromBB) {
 360    std::vector<MachineBasicBlock*> Succs(FromBB->succ_begin(),
 361                                          FromBB->succ_end());
 362     for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
 363       MachineBasicBlock *Succ = Succs[i];
 364       FromBB->removeSuccessor(Succ);
 365       if (!ToBB->isSuccessor(Succ))
 366         ToBB->addSuccessor(Succ);
 367     }
 368 }
 369
 370 /// isNextBlock - Returns true if ToBB the next basic block after BB.
 371 ///
 372 static bool isNextBlock(MachineBasicBlock *BB, MachineBasicBlock *ToBB) {
 373   MachineFunction::iterator Fallthrough = BB;
 374   return MachineFunction::iterator(ToBB) == ++Fallthrough;
 375 }
 376
 377 /// ReTryPreds - Invalidate predecessor BB info so it would be re-analyzed
 378 /// to determine if it can be if-converted.
 379 void IfConverter::ReTryPreds(MachineBasicBlock *BB) {
 380   for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
 381          E = BB->pred_end(); PI != E; ++PI) {
 382     BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()];
 383     PBBI.Kind = ICReAnalyze;
 384   }
 385 }
 386
 387 /// InsertUncondBranch - Inserts an unconditional branch from BB to ToBB.
 388 ///
 389 static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB,
 390                                const TargetInstrInfo *TII) {
 391   std::vector<MachineOperand> NoCond;
 392   TII->InsertBranch(*BB, ToBB, NULL, NoCond);
 393 }
 394
 395 /// IfConvertEarlyExit - If convert a early exit sub-CFG.
 396 ///
 397 bool IfConverter::IfConvertEarlyExit(BBInfo &BBI) {
 398   BBI.Kind = ICNotClassfied;
 399
 400   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
 401   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
 402   BBInfo *CvtBBI = &TrueBBI;
 403   BBInfo *NextBBI = &FalseBBI;
 404
 405   bool ReserveCond = false;
 406   if (TrueBBI.Kind != ICChild) {
 407     std::swap(CvtBBI, NextBBI);
 408     ReserveCond = true;
 409   }
 410
 411   std::vector<MachineOperand> NewCond(BBI.BrCond);
 412   if (ReserveCond)
 413     TII->ReverseBranchCondition(NewCond);
 414   FeasibilityAnalysis(*CvtBBI, NewCond);
 415   if (!CvtBBI->isPredicable)
 416     return false;
 417
 418   PredicateBlock(*CvtBBI, NewCond);
 419
 420   // Merge converted block into entry block. Also convert the end of the
 421   // block conditional branch (to the non-converted block) into an
 422   // unconditional one.
 423   BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
 424   MergeBlocks(BBI, *CvtBBI);
 425   if (!isNextBlock(BBI.BB, NextBBI->BB))
 426     InsertUncondBranch(BBI.BB, NextBBI->BB, TII);
 427   std::copy(NewCond.begin(), NewCond.end(), std::back_inserter(BBI.Predicate));
 428
 429   // Update block info. BB can be iteratively if-converted.
 430   BBI.Kind = ICNotAnalyzed;
 431   BBI.TrueBB = BBI.FalseBB = NULL;
 432   BBI.BrCond.clear();
 433   TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);
 434   ReTryPreds(BBI.BB);
 435   CvtBBI->Kind = ICDead;
 436
 437   // FIXME: Must maintain LiveIns.
 438   NumIfConvBBs++;
 439   return true;
 440 }
 441
 442 /// IfConvertTriangle - If convert a triangle sub-CFG.
 443 ///
 444 bool IfConverter::IfConvertTriangle(BBInfo &BBI) {
 445   BBI.Kind = ICNotClassfied;
 446
 447   BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
 448   FeasibilityAnalysis(TrueBBI, BBI.BrCond);
 449   if (!TrueBBI.isPredicable)
 450     return false;
 451
 452   // Predicate the 'true' block after removing its branch.
 453   TrueBBI.NonPredSize -= TII->RemoveBranch(*BBI.TrueBB);
 454   PredicateBlock(TrueBBI, BBI.BrCond);
 455
 456   // Join the 'true' and 'false' blocks by copying the instructions
 457   // from the 'false' block to the 'true' block.
 458   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
 459   MergeBlocks(TrueBBI, FalseBBI);
 460
 461   // Now merge the entry of the triangle with the true block.
 462   BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
 463   MergeBlocks(BBI, TrueBBI);
 464   std::copy(BBI.BrCond.begin(), BBI.BrCond.end(),
 465             std::back_inserter(BBI.Predicate));
 466
 467   // Update block info. BB can be iteratively if-converted.
 468   BBI.Kind = ICNotClassfied;
 469   BBI.TrueBB = BBI.FalseBB = NULL;
 470   BBI.BrCond.clear();
 471   TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);
 472   ReTryPreds(BBI.BB);
 473   TrueBBI.Kind = ICDead;
 474
 475   // FIXME: Must maintain LiveIns.
 476   NumIfConvBBs++;
 477   return true;
 478 }
 479
 480 /// IfConvertDiamond - If convert a diamond sub-CFG.
 481 ///
 482 bool IfConverter::IfConvertDiamond(BBInfo &BBI) {
 483   BBI.Kind = ICNotClassfied;
 484
 485   bool TrueNeedBr;
 486   bool FalseNeedBr;
 487   BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
 488   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
 489   FeasibilityAnalysis(TrueBBI, BBI.BrCond);
 490   std::vector<MachineOperand> RevCond(BBI.BrCond);
 491   TII->ReverseBranchCondition(RevCond);
 492   FeasibilityAnalysis(FalseBBI, RevCond);
 493
 494   SmallVector<MachineInstr*, 2> Dups;
 495   bool Proceed = TrueBBI.isPredicable && FalseBBI.isPredicable;
 496   if (Proceed) {
 497     // Check the 'true' and 'false' blocks if either isn't ended with a branch.
 498     // Either the block fallthrough to another block or it ends with a
 499     // return. If it's the former, add a branch to its successor.
 500     TrueNeedBr  = !TrueBBI.TrueBB && BBI.TrueBB->succ_size();
 501     FalseNeedBr = !FalseBBI.TrueBB && BBI.FalseBB->succ_size();
 502     if (TrueNeedBr && TrueBBI.ModifyPredicate) {
 503       TrueBBI.isPredicable = false;
 504       Proceed = false;
 505     }
 506     if (FalseNeedBr && FalseBBI.ModifyPredicate) {
 507       FalseBBI.isPredicable = false;
 508       Proceed = false;
 509     }
 510
 511     if (Proceed) {
 512       if (!BBI.TailBB) {
 513         // No common merge block. Check if the terminators (e.g. return) are
 514         // the same or predicable.
 515         MachineBasicBlock::iterator TT = BBI.TrueBB->getFirstTerminator();
 516         MachineBasicBlock::iterator FT = BBI.FalseBB->getFirstTerminator();
 517         while (TT != BBI.TrueBB->end() && FT != BBI.FalseBB->end()) {
 518           if (TT->isIdenticalTo(FT))
 519             Dups.push_back(TT);  // Will erase these later.
 520           else if (!TT->isPredicable() && !FT->isPredicable()) {
 521             Proceed = false;
 522             break; // Can't if-convert. Abort!
 523           }
 524           ++TT;
 525           ++FT;
 526         }
 527
 528         // One of the two pathes have more terminators, make sure they are
 529         // all predicable.
 530         while (Proceed && TT != BBI.TrueBB->end())
 531           if (!TT->isPredicable()) {
 532             Proceed = false;
 533             break; // Can't if-convert. Abort!
 534           }
 535         while (Proceed && FT != BBI.FalseBB->end())
 536           if (!FT->isPredicable()) {
 537             Proceed = false;
 538             break; // Can't if-convert. Abort!
 539           }
 540       }
 541     }
 542   }
 543
 544   if (!Proceed)
 545     return false;
 546
 547   // Remove the duplicated instructions from the 'true' block.
 548   for (unsigned i = 0, e = Dups.size(); i != e; ++i) {
 549     Dups[i]->eraseFromParent();
 550     --TrueBBI.NonPredSize;
 551   }
 552
 553   // Predicate the 'true' block after removing its branch.
 554   TrueBBI.NonPredSize -= TII->RemoveBranch(*BBI.TrueBB);
 555   PredicateBlock(TrueBBI, BBI.BrCond);
 556
 557   // Predicate the 'false' block.
 558   PredicateBlock(FalseBBI, RevCond, true);
 559
 560   // Merge the 'true' and 'false' blocks by copying the instructions
 561   // from the 'false' block to the 'true' block. That is, unless the true
 562   // block would clobber the predicate, in that case, do the opposite.
 563   BBInfo *CvtBBI;
 564   if (!TrueBBI.ModifyPredicate) {
 565     // Add a conditional branch from 'true' to 'true' successor if needed.
 566     if (TrueNeedBr)
 567       TII->InsertBranch(*BBI.TrueBB, *BBI.TrueBB->succ_begin(), NULL,
 568                         BBI.BrCond);
 569     // Add an unconditional branch from 'false' to to 'false' successor if it
 570     // will not be the fallthrough block.
 571     if (FalseNeedBr &&
 572         !isNextBlock(BBI.BB, *BBI.FalseBB->succ_begin()))
 573       InsertUncondBranch(BBI.FalseBB, *BBI.FalseBB->succ_begin(), TII);
 574     MergeBlocks(TrueBBI, FalseBBI);
 575     CvtBBI = &TrueBBI;
 576   } else {
 577     // Add a conditional branch from 'false' to 'false' successor if needed.
 578     if (FalseNeedBr)
 579       TII->InsertBranch(*BBI.FalseBB, *BBI.FalseBB->succ_begin(), NULL,
 580                         RevCond);
 581     // Add an unconditional branch from 'true' to to 'true' successor if it
 582     // will not be the fallthrough block.
 583     if (TrueNeedBr &&
 584         !isNextBlock(BBI.BB, *BBI.TrueBB->succ_begin()))
 585       InsertUncondBranch(BBI.TrueBB, *BBI.TrueBB->succ_begin(), TII);
 586     MergeBlocks(FalseBBI, TrueBBI);
 587     CvtBBI = &FalseBBI;
 588   }
 589
 590   // Remove the conditional branch from entry to the blocks.
 591   BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
 592
 593   bool OkToIfcvt = true;
 594   // Merge the combined block into the entry of the diamond if the entry
 595   // block is its only predecessor. Otherwise, insert an unconditional
 596   // branch from entry to the if-converted block.
 597   if (CvtBBI->BB->pred_size() == 1) {
 598     MergeBlocks(BBI, *CvtBBI);
 599     CvtBBI = &BBI;
 600     OkToIfcvt = false;
 601   } else
 602     InsertUncondBranch(BBI.BB, CvtBBI->BB, TII);
 603
 604   // If the if-converted block fallthrough or unconditionally branch into the
 605   // tail block, and the tail block does not have other predecessors, then
 606   // fold the tail block in as well.
 607   if (BBI.TailBB &&
 608       BBI.TailBB->pred_size() == 1 && CvtBBI->BB->succ_size() == 1) {
 609     CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB);
 610     BBInfo TailBBI = BBAnalysis[BBI.TailBB->getNumber()];
 611     MergeBlocks(*CvtBBI, TailBBI);
 612     TailBBI.Kind = ICDead;
 613   }
 614
 615   // Update block info. BB may be iteratively if-converted.
 616   if (OkToIfcvt) {
 617     BBI.Kind = ICNotClassfied;
 618     BBI.TrueBB = BBI.FalseBB = NULL;
 619     BBI.BrCond.clear();
 620     TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);
 621     ReTryPreds(BBI.BB);
 622   }
 623   TrueBBI.Kind = ICDead;
 624   FalseBBI.Kind = ICDead;
 625
 626   // FIXME: Must maintain LiveIns.
 627   NumIfConvBBs += 2;
 628   return true;
 629 }
 630
 631 /// PredicateBlock - Predicate every instruction in the block with the specified
 632 /// condition. If IgnoreTerm is true, skip over all terminator instructions.
 633 void IfConverter::PredicateBlock(BBInfo &BBI,
 634                                  std::vector<MachineOperand> &Cond,
 635                                  bool IgnoreTerm) {
 636   for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end();
 637        I != E; ++I) {
 638     MachineInstr *MI = I;
 639     if (IgnoreTerm && TII->isTerminatorInstr(MI->getOpcode()))
 640       continue;
 641     if (TII->isPredicated(MI))
 642       continue;
 643     if (!TII->PredicateInstruction(MI, Cond)) {
 644       cerr << "Unable to predication " << *I << "!\n";
 645       abort();
 646     }
 647   }
 648
 649   BBI.NonPredSize = 0;
 650 }
 651
 652 /// MergeBlocks - Move all instructions from FromBB to the end of ToBB.
 653 ///
 654 void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI) {
 655   ToBBI.BB->splice(ToBBI.BB->end(),
 656                    FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end());
 657
 658   // If FromBBI is previously a successor, remove it from ToBBI's successor
 659   // list and update its TrueBB / FalseBB field if needed.
 660   if (ToBBI.BB->isSuccessor(FromBBI.BB))
 661     ToBBI.BB->removeSuccessor(FromBBI.BB);
 662
 663   // Transfer preds / succs and update size.
 664   TransferPreds(ToBBI.BB, FromBBI.BB);
 665   TransferSuccs(ToBBI.BB, FromBBI.BB);
 666   ToBBI.NonPredSize += FromBBI.NonPredSize;
 667   FromBBI.NonPredSize = 0;
 668 }