lib/Transforms/Scalar/LoopUnswitch.cpp

   1 //===-- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop ------===//
   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 pass transforms loops that contain branches on loop-invariant conditions
  11 // to have multiple loops.  For example, it turns the left into the right code:
  12 //
  13 //  for (...)                  if (lic)
  14 //    A                          for (...)
  15 //    if (lic)                     A; B; C
  16 //      B                      else
  17 //    C                          for (...)
  18 //                                 A; C
  19 //
  20 // This can increase the size of the code exponentially (doubling it every time
  21 // a loop is unswitched) so we only unswitch if the resultant code will be
  22 // smaller than a threshold.
  23 //
  24 // This pass expects LICM to be run before it to hoist invariant conditions out
  25 // of the loop, to make the unswitching opportunity obvious.
  26 //
  27 //===----------------------------------------------------------------------===//
  28
  29 #define DEBUG_TYPE "loop-unswitch"
  30 #include "llvm/Transforms/Scalar.h"
  31 #include "llvm/Constants.h"
  32 #include "llvm/DerivedTypes.h"
  33 #include "llvm/Function.h"
  34 #include "llvm/Instructions.h"
  35 #include "llvm/Analysis/ConstantFolding.h"
  36 #include "llvm/Analysis/InlineCost.h"
  37 #include "llvm/Analysis/LoopInfo.h"
  38 #include "llvm/Analysis/LoopPass.h"
  39 #include "llvm/Analysis/Dominators.h"
  40 #include "llvm/Transforms/Utils/Cloning.h"
  41 #include "llvm/Transforms/Utils/Local.h"
  42 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  43 #include "llvm/ADT/Statistic.h"
  44 #include "llvm/ADT/SmallPtrSet.h"
  45 #include "llvm/ADT/STLExtras.h"
  46 #include "llvm/Support/CommandLine.h"
  47 #include "llvm/Support/Debug.h"
  48 #include "llvm/Support/raw_ostream.h"
  49 #include <algorithm>
  50 #include <set>
  51 using namespace llvm;
  52
  53 STATISTIC(NumBranches, "Number of branches unswitched");
  54 STATISTIC(NumSwitches, "Number of switches unswitched");
  55 STATISTIC(NumSelects , "Number of selects unswitched");
  56 STATISTIC(NumTrivial , "Number of unswitches that are trivial");
  57 STATISTIC(NumSimplify, "Number of simplifications of unswitched code");
  58
  59 // The specific value of 50 here was chosen based only on intuition and a
  60 // few specific examples.
  61 static cl::opt<unsigned>
  62 Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"),
  63           cl::init(50), cl::Hidden);
  64
  65 namespace {
  66   class LoopUnswitch : public LoopPass {
  67     LoopInfo *LI;  // Loop information
  68     LPPassManager *LPM;
  69
  70     // LoopProcessWorklist - Used to check if second loop needs processing
  71     // after RewriteLoopBodyWithConditionConstant rewrites first loop.
  72     std::vector<Loop*> LoopProcessWorklist;
  73     SmallPtrSet<Value *,8> UnswitchedVals;
  74
  75     bool OptimizeForSize;
  76     bool redoLoop;
  77
  78     Loop *currentLoop;
  79     DominanceFrontier *DF;
  80     DominatorTree *DT;
  81     BasicBlock *loopHeader;
  82     BasicBlock *loopPreheader;
  83
  84     // LoopBlocks contains all of the basic blocks of the loop, including the
  85     // preheader of the loop, the body of the loop, and the exit blocks of the
  86     // loop, in that order.
  87     std::vector<BasicBlock*> LoopBlocks;
  88     // NewBlocks contained cloned copy of basic blocks from LoopBlocks.
  89     std::vector<BasicBlock*> NewBlocks;
  90
  91   public:
  92     static char ID; // Pass ID, replacement for typeid
  93     explicit LoopUnswitch(bool Os = false) :
  94       LoopPass(&ID), OptimizeForSize(Os), redoLoop(false),
  95       currentLoop(NULL), DF(NULL), DT(NULL), loopHeader(NULL),
  96       loopPreheader(NULL) {}
  97
  98     bool runOnLoop(Loop *L, LPPassManager &LPM);
  99     bool processCurrentLoop();
 100
 101     /// This transformation requires natural loop information & requires that
 102     /// loop preheaders be inserted into the CFG...
 103     ///
 104     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 105       AU.addRequiredID(LoopSimplifyID);
 106       AU.addPreservedID(LoopSimplifyID);
 107       AU.addRequired<LoopInfo>();
 108       AU.addPreserved<LoopInfo>();
 109       AU.addRequiredID(LCSSAID);
 110       AU.addPreservedID(LCSSAID);
 111       AU.addPreserved<DominatorTree>();
 112       AU.addPreserved<DominanceFrontier>();
 113     }
 114
 115   private:
 116
 117     virtual void releaseMemory() {
 118       UnswitchedVals.clear();
 119     }
 120
 121     /// RemoveLoopFromWorklist - If the specified loop is on the loop worklist,
 122     /// remove it.
 123     void RemoveLoopFromWorklist(Loop *L) {
 124       std::vector<Loop*>::iterator I = std::find(LoopProcessWorklist.begin(),
 125                                                  LoopProcessWorklist.end(), L);
 126       if (I != LoopProcessWorklist.end())
 127         LoopProcessWorklist.erase(I);
 128     }
 129
 130     void initLoopData() {
 131       loopHeader = currentLoop->getHeader();
 132       loopPreheader = currentLoop->getLoopPreheader();
 133     }
 134
 135     /// Split all of the edges from inside the loop to their exit blocks.
 136     /// Update the appropriate Phi nodes as we do so.
 137     void SplitExitEdges(Loop *L, const SmallVector<BasicBlock *, 8> &ExitBlocks);
 138
 139     bool UnswitchIfProfitable(Value *LoopCond, Constant *Val);
 140     void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
 141                                   BasicBlock *ExitBlock);
 142     void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L);
 143
 144     void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
 145                                               Constant *Val, bool isEqual);
 146
 147     void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
 148                                         BasicBlock *TrueDest,
 149                                         BasicBlock *FalseDest,
 150                                         Instruction *InsertPt);
 151
 152     void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L);
 153     void RemoveBlockIfDead(BasicBlock *BB,
 154                            std::vector<Instruction*> &Worklist, Loop *l);
 155     void RemoveLoopFromHierarchy(Loop *L);
 156     bool IsTrivialUnswitchCondition(Value *Cond, Constant **Val = 0,
 157                                     BasicBlock **LoopExit = 0);
 158
 159   };
 160 }
 161 char LoopUnswitch::ID = 0;
 162 static RegisterPass<LoopUnswitch> X("loop-unswitch", "Unswitch loops");
 163
 164 Pass *llvm::createLoopUnswitchPass(bool Os) {
 165   return new LoopUnswitch(Os);
 166 }
 167
 168 /// FindLIVLoopCondition - Cond is a condition that occurs in L.  If it is
 169 /// invariant in the loop, or has an invariant piece, return the invariant.
 170 /// Otherwise, return null.
 171 static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) {
 172   // We can never unswitch on vector conditions.
 173   if (Cond->getType()->isVectorTy())
 174     return 0;
 175
 176   // Constants should be folded, not unswitched on!
 177   if (isa<Constant>(Cond)) return 0;
 178
 179   // TODO: Handle: br (VARIANT|INVARIANT).
 180
 181   // Hoist simple values out.
 182   if (L->makeLoopInvariant(Cond, Changed))
 183     return Cond;
 184
 185   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond))
 186     if (BO->getOpcode() == Instruction::And ||
 187         BO->getOpcode() == Instruction::Or) {
 188       // If either the left or right side is invariant, we can unswitch on this,
 189       // which will cause the branch to go away in one loop and the condition to
 190       // simplify in the other one.
 191       if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed))
 192         return LHS;
 193       if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed))
 194         return RHS;
 195     }
 196
 197   return 0;
 198 }
 199
 200 bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
 201   LI = &getAnalysis<LoopInfo>();
 202   LPM = &LPM_Ref;
 203   DF = getAnalysisIfAvailable<DominanceFrontier>();
 204   DT = getAnalysisIfAvailable<DominatorTree>();
 205   currentLoop = L;
 206   Function *F = currentLoop->getHeader()->getParent();
 207   bool Changed = false;
 208   do {
 209     assert(currentLoop->isLCSSAForm(*DT));
 210     redoLoop = false;
 211     Changed |= processCurrentLoop();
 212   } while(redoLoop);
 213
 214   if (Changed) {
 215     // FIXME: Reconstruct dom info, because it is not preserved properly.
 216     if (DT)
 217       DT->runOnFunction(*F);
 218     if (DF)
 219       DF->runOnFunction(*F);
 220   }
 221   return Changed;
 222 }
 223
 224 /// processCurrentLoop - Do actual work and unswitch loop if possible
 225 /// and profitable.
 226 bool LoopUnswitch::processCurrentLoop() {
 227   bool Changed = false;
 228   LLVMContext &Context = currentLoop->getHeader()->getContext();
 229
 230   // Loop over all of the basic blocks in the loop.  If we find an interior
 231   // block that is branching on a loop-invariant condition, we can unswitch this
 232   // loop.
 233   for (Loop::block_iterator I = currentLoop->block_begin(),
 234          E = currentLoop->block_end(); I != E; ++I) {
 235     TerminatorInst *TI = (*I)->getTerminator();
 236     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 237       // If this isn't branching on an invariant condition, we can't unswitch
 238       // it.
 239       if (BI->isConditional()) {
 240         // See if this, or some part of it, is loop invariant.  If so, we can
 241         // unswitch on it if we desire.
 242         Value *LoopCond = FindLIVLoopCondition(BI->getCondition(),
 243                                                currentLoop, Changed);
 244         if (LoopCond && UnswitchIfProfitable(LoopCond,
 245                                              ConstantInt::getTrue(Context))) {
 246           ++NumBranches;
 247           return true;
 248         }
 249       }
 250     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 251       Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),
 252                                              currentLoop, Changed);
 253       if (LoopCond && SI->getNumCases() > 1) {
 254         // Find a value to unswitch on:
 255         // FIXME: this should chose the most expensive case!
 256         Constant *UnswitchVal = SI->getCaseValue(1);
 257         // Do not process same value again and again.
 258         if (!UnswitchedVals.insert(UnswitchVal))
 259           continue;
 260
 261         if (UnswitchIfProfitable(LoopCond, UnswitchVal)) {
 262           ++NumSwitches;
 263           return true;
 264         }
 265       }
 266     }
 267
 268     // Scan the instructions to check for unswitchable values.
 269     for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end();
 270          BBI != E; ++BBI)
 271       if (SelectInst *SI = dyn_cast<SelectInst>(BBI)) {
 272         Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),
 273                                                currentLoop, Changed);
 274         if (LoopCond && UnswitchIfProfitable(LoopCond,
 275                                              ConstantInt::getTrue(Context))) {
 276           ++NumSelects;
 277           return true;
 278         }
 279       }
 280   }
 281   return Changed;
 282 }
 283
 284 /// isTrivialLoopExitBlock - Check to see if all paths from BB either:
 285 ///   1. Exit the loop with no side effects.
 286 ///   2. Branch to the latch block with no side-effects.
 287 ///
 288 /// If these conditions are true, we return true and set ExitBB to the block we
 289 /// exit through.
 290 ///
 291 static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB,
 292                                          BasicBlock *&ExitBB,
 293                                          std::set<BasicBlock*> &Visited) {
 294   if (!Visited.insert(BB).second) {
 295     // Already visited and Ok, end of recursion.
 296     return true;
 297   } else if (!L->contains(BB)) {
 298     // Otherwise, this is a loop exit, this is fine so long as this is the
 299     // first exit.
 300     if (ExitBB != 0) return false;
 301     ExitBB = BB;
 302     return true;
 303   }
 304
 305   // Otherwise, this is an unvisited intra-loop node.  Check all successors.
 306   for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) {
 307     // Check to see if the successor is a trivial loop exit.
 308     if (!isTrivialLoopExitBlockHelper(L, *SI, ExitBB, Visited))
 309       return false;
 310   }
 311
 312   // Okay, everything after this looks good, check to make sure that this block
 313   // doesn't include any side effects.
 314   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 315     if (I->mayHaveSideEffects())
 316       return false;
 317
 318   return true;
 319 }
 320
 321 /// isTrivialLoopExitBlock - Return true if the specified block unconditionally
 322 /// leads to an exit from the specified loop, and has no side-effects in the
 323 /// process.  If so, return the block that is exited to, otherwise return null.
 324 static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) {
 325   std::set<BasicBlock*> Visited;
 326   Visited.insert(L->getHeader());  // Branches to header are ok.
 327   BasicBlock *ExitBB = 0;
 328   if (isTrivialLoopExitBlockHelper(L, BB, ExitBB, Visited))
 329     return ExitBB;
 330   return 0;
 331 }
 332
 333 /// IsTrivialUnswitchCondition - Check to see if this unswitch condition is
 334 /// trivial: that is, that the condition controls whether or not the loop does
 335 /// anything at all.  If this is a trivial condition, unswitching produces no
 336 /// code duplications (equivalently, it produces a simpler loop and a new empty
 337 /// loop, which gets deleted).
 338 ///
 339 /// If this is a trivial condition, return true, otherwise return false.  When
 340 /// returning true, this sets Cond and Val to the condition that controls the
 341 /// trivial condition: when Cond dynamically equals Val, the loop is known to
 342 /// exit.  Finally, this sets LoopExit to the BB that the loop exits to when
 343 /// Cond == Val.
 344 ///
 345 bool LoopUnswitch::IsTrivialUnswitchCondition(Value *Cond, Constant **Val,
 346                                        BasicBlock **LoopExit) {
 347   BasicBlock *Header = currentLoop->getHeader();
 348   TerminatorInst *HeaderTerm = Header->getTerminator();
 349   LLVMContext &Context = Header->getContext();
 350
 351   BasicBlock *LoopExitBB = 0;
 352   if (BranchInst *BI = dyn_cast<BranchInst>(HeaderTerm)) {
 353     // If the header block doesn't end with a conditional branch on Cond, we
 354     // can't handle it.
 355     if (!BI->isConditional() || BI->getCondition() != Cond)
 356       return false;
 357
 358     // Check to see if a successor of the branch is guaranteed to go to the
 359     // latch block or exit through a one exit block without having any
 360     // side-effects.  If so, determine the value of Cond that causes it to do
 361     // this.
 362     if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,
 363                                              BI->getSuccessor(0)))) {
 364       if (Val) *Val = ConstantInt::getTrue(Context);
 365     } else if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,
 366                                                     BI->getSuccessor(1)))) {
 367       if (Val) *Val = ConstantInt::getFalse(Context);
 368     }
 369   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(HeaderTerm)) {
 370     // If this isn't a switch on Cond, we can't handle it.
 371     if (SI->getCondition() != Cond) return false;
 372
 373     // Check to see if a successor of the switch is guaranteed to go to the
 374     // latch block or exit through a one exit block without having any
 375     // side-effects.  If so, determine the value of Cond that causes it to do
 376     // this.  Note that we can't trivially unswitch on the default case.
 377     for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i)
 378       if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,
 379                                                SI->getSuccessor(i)))) {
 380         // Okay, we found a trivial case, remember the value that is trivial.
 381         if (Val) *Val = SI->getCaseValue(i);
 382         break;
 383       }
 384   }
 385
 386   // If we didn't find a single unique LoopExit block, or if the loop exit block
 387   // contains phi nodes, this isn't trivial.
 388   if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
 389     return false;   // Can't handle this.
 390
 391   if (LoopExit) *LoopExit = LoopExitBB;
 392
 393   // We already know that nothing uses any scalar values defined inside of this
 394   // loop.  As such, we just have to check to see if this loop will execute any
 395   // side-effecting instructions (e.g. stores, calls, volatile loads) in the
 396   // part of the loop that the code *would* execute.  We already checked the
 397   // tail, check the header now.
 398   for (BasicBlock::iterator I = Header->begin(), E = Header->end(); I != E; ++I)
 399     if (I->mayHaveSideEffects())
 400       return false;
 401   return true;
 402 }
 403
 404 /// UnswitchIfProfitable - We have found that we can unswitch currentLoop when
 405 /// LoopCond == Val to simplify the loop.  If we decide that this is profitable,
 406 /// unswitch the loop, reprocess the pieces, then return true.
 407 bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val) {
 408
 409   initLoopData();
 410
 411   // If LoopSimplify was unable to form a preheader, don't do any unswitching.
 412   if (!loopPreheader)
 413     return false;
 414
 415   Function *F = loopHeader->getParent();
 416
 417   Constant *CondVal = 0;
 418   BasicBlock *ExitBlock = 0;
 419   if (IsTrivialUnswitchCondition(LoopCond, &CondVal, &ExitBlock)) {
 420     // If the condition is trivial, always unswitch. There is no code growth
 421     // for this case.
 422     UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, ExitBlock);
 423     return true;
 424   }
 425
 426   // Check to see if it would be profitable to unswitch current loop.
 427
 428   // Do not do non-trivial unswitch while optimizing for size.
 429   if (OptimizeForSize || F->hasFnAttr(Attribute::OptimizeForSize))
 430     return false;
 431
 432   // FIXME: This is overly conservative because it does not take into
 433   // consideration code simplification opportunities and code that can
 434   // be shared by the resultant unswitched loops.
 435   CodeMetrics Metrics;
 436   for (Loop::block_iterator I = currentLoop->block_begin(),
 437          E = currentLoop->block_end();
 438        I != E; ++I)
 439     Metrics.analyzeBasicBlock(*I);
 440
 441   // Limit the number of instructions to avoid causing significant code
 442   // expansion, and the number of basic blocks, to avoid loops with
 443   // large numbers of branches which cause loop unswitching to go crazy.
 444   // This is a very ad-hoc heuristic.
 445   if (Metrics.NumInsts > Threshold ||
 446       Metrics.NumBlocks * 5 > Threshold ||
 447       Metrics.NeverInline) {
 448     DEBUG(dbgs() << "NOT unswitching loop %"
 449           << currentLoop->getHeader()->getName() << ", cost too high: "
 450           << currentLoop->getBlocks().size() << "\n");
 451     return false;
 452   }
 453
 454   UnswitchNontrivialCondition(LoopCond, Val, currentLoop);
 455   return true;
 456 }
 457
 458 // RemapInstruction - Convert the instruction operands from referencing the
 459 // current values into those specified by ValueMap.
 460 //
 461 static inline void RemapInstruction(Instruction *I,
 462                                     DenseMap<const Value *, Value*> &ValueMap) {
 463   for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) {
 464     Value *Op = I->getOperand(op);
 465     DenseMap<const Value *, Value*>::iterator It = ValueMap.find(Op);
 466     if (It != ValueMap.end()) Op = It->second;
 467     I->setOperand(op, Op);
 468   }
 469 }
 470
 471 /// CloneLoop - Recursively clone the specified loop and all of its children,
 472 /// mapping the blocks with the specified map.
 473 static Loop *CloneLoop(Loop *L, Loop *PL, DenseMap<const Value*, Value*> &VM,
 474                        LoopInfo *LI, LPPassManager *LPM) {
 475   Loop *New = new Loop();
 476   LPM->insertLoop(New, PL);
 477
 478   // Add all of the blocks in L to the new loop.
 479   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 480        I != E; ++I)
 481     if (LI->getLoopFor(*I) == L)
 482       New->addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), LI->getBase());
 483
 484   // Add all of the subloops to the new loop.
 485   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 486     CloneLoop(*I, New, VM, LI, LPM);
 487
 488   return New;
 489 }
 490
 491 /// EmitPreheaderBranchOnCondition - Emit a conditional branch on two values
 492 /// if LIC == Val, branch to TrueDst, otherwise branch to FalseDest.  Insert the
 493 /// code immediately before InsertPt.
 494 void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
 495                                                   BasicBlock *TrueDest,
 496                                                   BasicBlock *FalseDest,
 497                                                   Instruction *InsertPt) {
 498   // Insert a conditional branch on LIC to the two preheaders.  The original
 499   // code is the true version and the new code is the false version.
 500   Value *BranchVal = LIC;
 501   if (!isa<ConstantInt>(Val) ||
 502       Val->getType() != Type::getInt1Ty(LIC->getContext()))
 503     BranchVal = new ICmpInst(InsertPt, ICmpInst::ICMP_EQ, LIC, Val, "tmp");
 504   else if (Val != ConstantInt::getTrue(Val->getContext()))
 505     // We want to enter the new loop when the condition is true.
 506     std::swap(TrueDest, FalseDest);
 507
 508   // Insert the new branch.
 509   BranchInst *BI = BranchInst::Create(TrueDest, FalseDest, BranchVal, InsertPt);
 510
 511   // If either edge is critical, split it. This helps preserve LoopSimplify
 512   // form for enclosing loops.
 513   SplitCriticalEdge(BI, 0, this);
 514   SplitCriticalEdge(BI, 1, this);
 515 }
 516
 517 /// UnswitchTrivialCondition - Given a loop that has a trivial unswitchable
 518 /// condition in it (a cond branch from its header block to its latch block,
 519 /// where the path through the loop that doesn't execute its body has no
 520 /// side-effects), unswitch it.  This doesn't involve any code duplication, just
 521 /// moving the conditional branch outside of the loop and updating loop info.
 522 void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond,
 523                                             Constant *Val,
 524                                             BasicBlock *ExitBlock) {
 525   DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
 526         << loopHeader->getName() << " [" << L->getBlocks().size()
 527         << " blocks] in Function " << L->getHeader()->getParent()->getName()
 528         << " on cond: " << *Val << " == " << *Cond << "\n");
 529
 530   // First step, split the preheader, so that we know that there is a safe place
 531   // to insert the conditional branch.  We will change loopPreheader to have a
 532   // conditional branch on Cond.
 533   BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, this);
 534
 535   // Now that we have a place to insert the conditional branch, create a place
 536   // to branch to: this is the exit block out of the loop that we should
 537   // short-circuit to.
 538
 539   // Split this block now, so that the loop maintains its exit block, and so
 540   // that the jump from the preheader can execute the contents of the exit block
 541   // without actually branching to it (the exit block should be dominated by the
 542   // loop header, not the preheader).
 543   assert(!L->contains(ExitBlock) && "Exit block is in the loop?");
 544   BasicBlock *NewExit = SplitBlock(ExitBlock, ExitBlock->begin(), this);
 545
 546   // Okay, now we have a position to branch from and a position to branch to,
 547   // insert the new conditional branch.
 548   EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH,
 549                                  loopPreheader->getTerminator());
 550   LPM->deleteSimpleAnalysisValue(loopPreheader->getTerminator(), L);
 551   loopPreheader->getTerminator()->eraseFromParent();
 552
 553   // We need to reprocess this loop, it could be unswitched again.
 554   redoLoop = true;
 555
 556   // Now that we know that the loop is never entered when this condition is a
 557   // particular value, rewrite the loop with this info.  We know that this will
 558   // at least eliminate the old branch.
 559   RewriteLoopBodyWithConditionConstant(L, Cond, Val, false);
 560   ++NumTrivial;
 561 }
 562
 563 /// SplitExitEdges - Split all of the edges from inside the loop to their exit
 564 /// blocks.  Update the appropriate Phi nodes as we do so.
 565 void LoopUnswitch::SplitExitEdges(Loop *L,
 566                                 const SmallVector<BasicBlock *, 8> &ExitBlocks){
 567
 568   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
 569     BasicBlock *ExitBlock = ExitBlocks[i];
 570     SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock),
 571                                        pred_end(ExitBlock));
 572     SplitBlockPredecessors(ExitBlock, Preds.data(), Preds.size(),
 573                            ".us-lcssa", this);
 574   }
 575 }
 576
 577 /// UnswitchNontrivialCondition - We determined that the loop is profitable
 578 /// to unswitch when LIC equal Val.  Split it into loop versions and test the
 579 /// condition outside of either loop.  Return the loops created as Out1/Out2.
 580 void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
 581                                                Loop *L) {
 582   Function *F = loopHeader->getParent();
 583   DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"
 584         << loopHeader->getName() << " [" << L->getBlocks().size()
 585         << " blocks] in Function " << F->getName()
 586         << " when '" << *Val << "' == " << *LIC << "\n");
 587
 588   LoopBlocks.clear();
 589   NewBlocks.clear();
 590
 591   // First step, split the preheader and exit blocks, and add these blocks to
 592   // the LoopBlocks list.
 593   BasicBlock *NewPreheader = SplitEdge(loopPreheader, loopHeader, this);
 594   LoopBlocks.push_back(NewPreheader);
 595
 596   // We want the loop to come after the preheader, but before the exit blocks.
 597   LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
 598
 599   SmallVector<BasicBlock*, 8> ExitBlocks;
 600   L->getUniqueExitBlocks(ExitBlocks);
 601
 602   // Split all of the edges from inside the loop to their exit blocks.  Update
 603   // the appropriate Phi nodes as we do so.
 604   SplitExitEdges(L, ExitBlocks);
 605
 606   // The exit blocks may have been changed due to edge splitting, recompute.
 607   ExitBlocks.clear();
 608   L->getUniqueExitBlocks(ExitBlocks);
 609
 610   // Add exit blocks to the loop blocks.
 611   LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end());
 612
 613   // Next step, clone all of the basic blocks that make up the loop (including
 614   // the loop preheader and exit blocks), keeping track of the mapping between
 615   // the instructions and blocks.
 616   NewBlocks.reserve(LoopBlocks.size());
 617   DenseMap<const Value*, Value*> ValueMap;
 618   for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) {
 619     BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[i], ValueMap, ".us", F);
 620     NewBlocks.push_back(NewBB);
 621     ValueMap[LoopBlocks[i]] = NewBB;  // Keep the BB mapping.
 622     LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], NewBB, L);
 623   }
 624
 625   // Splice the newly inserted blocks into the function right before the
 626   // original preheader.
 627   F->getBasicBlockList().splice(NewPreheader, F->getBasicBlockList(),
 628                                 NewBlocks[0], F->end());
 629
 630   // Now we create the new Loop object for the versioned loop.
 631   Loop *NewLoop = CloneLoop(L, L->getParentLoop(), ValueMap, LI, LPM);
 632   Loop *ParentLoop = L->getParentLoop();
 633   if (ParentLoop) {
 634     // Make sure to add the cloned preheader and exit blocks to the parent loop
 635     // as well.
 636     ParentLoop->addBasicBlockToLoop(NewBlocks[0], LI->getBase());
 637   }
 638
 639   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
 640     BasicBlock *NewExit = cast<BasicBlock>(ValueMap[ExitBlocks[i]]);
 641     // The new exit block should be in the same loop as the old one.
 642     if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i]))
 643       ExitBBLoop->addBasicBlockToLoop(NewExit, LI->getBase());
 644
 645     assert(NewExit->getTerminator()->getNumSuccessors() == 1 &&
 646            "Exit block should have been split to have one successor!");
 647     BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
 648
 649     // If the successor of the exit block had PHI nodes, add an entry for
 650     // NewExit.
 651     PHINode *PN;
 652     for (BasicBlock::iterator I = ExitSucc->begin(); isa<PHINode>(I); ++I) {
 653       PN = cast<PHINode>(I);
 654       Value *V = PN->getIncomingValueForBlock(ExitBlocks[i]);
 655       DenseMap<const Value *, Value*>::iterator It = ValueMap.find(V);
 656       if (It != ValueMap.end()) V = It->second;
 657       PN->addIncoming(V, NewExit);
 658     }
 659   }
 660
 661   // Rewrite the code to refer to itself.
 662   for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i)
 663     for (BasicBlock::iterator I = NewBlocks[i]->begin(),
 664            E = NewBlocks[i]->end(); I != E; ++I)
 665       RemapInstruction(I, ValueMap);
 666
 667   // Rewrite the original preheader to select between versions of the loop.
 668   BranchInst *OldBR = cast<BranchInst>(loopPreheader->getTerminator());
 669   assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] &&
 670          "Preheader splitting did not work correctly!");
 671
 672   // Emit the new branch that selects between the two versions of this loop.
 673   EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR);
 674   LPM->deleteSimpleAnalysisValue(OldBR, L);
 675   OldBR->eraseFromParent();
 676
 677   LoopProcessWorklist.push_back(NewLoop);
 678   redoLoop = true;
 679
 680   // Keep a WeakVH holding onto LIC.  If the first call to RewriteLoopBody
 681   // deletes the instruction (for example by simplifying a PHI that feeds into
 682   // the condition that we're unswitching on), we don't rewrite the second
 683   // iteration.
 684   WeakVH LICHandle(LIC);
 685
 686   // Now we rewrite the original code to know that the condition is true and the
 687   // new code to know that the condition is false.
 688   RewriteLoopBodyWithConditionConstant(L, LIC, Val, false);
 689
 690   // It's possible that simplifying one loop could cause the other to be
 691   // changed to another value or a constant.  If its a constant, don't simplify
 692   // it.
 693   if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop &&
 694       LICHandle && !isa<Constant>(LICHandle))
 695     RewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, true);
 696 }
 697
 698 /// RemoveFromWorklist - Remove all instances of I from the worklist vector
 699 /// specified.
 700 static void RemoveFromWorklist(Instruction *I,
 701                                std::vector<Instruction*> &Worklist) {
 702   std::vector<Instruction*>::iterator WI = std::find(Worklist.begin(),
 703                                                      Worklist.end(), I);
 704   while (WI != Worklist.end()) {
 705     unsigned Offset = WI-Worklist.begin();
 706     Worklist.erase(WI);
 707     WI = std::find(Worklist.begin()+Offset, Worklist.end(), I);
 708   }
 709 }
 710
 711 /// ReplaceUsesOfWith - When we find that I really equals V, remove I from the
 712 /// program, replacing all uses with V and update the worklist.
 713 static void ReplaceUsesOfWith(Instruction *I, Value *V,
 714                               std::vector<Instruction*> &Worklist,
 715                               Loop *L, LPPassManager *LPM) {
 716   DEBUG(dbgs() << "Replace with '" << *V << "': " << *I);
 717
 718   // Add uses to the worklist, which may be dead now.
 719   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 720     if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
 721       Worklist.push_back(Use);
 722
 723   // Add users to the worklist which may be simplified now.
 724   for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
 725        UI != E; ++UI)
 726     Worklist.push_back(cast<Instruction>(*UI));
 727   LPM->deleteSimpleAnalysisValue(I, L);
 728   RemoveFromWorklist(I, Worklist);
 729   I->replaceAllUsesWith(V);
 730   I->eraseFromParent();
 731   ++NumSimplify;
 732 }
 733
 734 /// RemoveBlockIfDead - If the specified block is dead, remove it, update loop
 735 /// information, and remove any dead successors it has.
 736 ///
 737 void LoopUnswitch::RemoveBlockIfDead(BasicBlock *BB,
 738                                      std::vector<Instruction*> &Worklist,
 739                                      Loop *L) {
 740   if (pred_begin(BB) != pred_end(BB)) {
 741     // This block isn't dead, since an edge to BB was just removed, see if there
 742     // are any easy simplifications we can do now.
 743     if (BasicBlock *Pred = BB->getSinglePredecessor()) {
 744       // If it has one pred, fold phi nodes in BB.
 745       while (isa<PHINode>(BB->begin()))
 746         ReplaceUsesOfWith(BB->begin(),
 747                           cast<PHINode>(BB->begin())->getIncomingValue(0),
 748                           Worklist, L, LPM);
 749
 750       // If this is the header of a loop and the only pred is the latch, we now
 751       // have an unreachable loop.
 752       if (Loop *L = LI->getLoopFor(BB))
 753         if (loopHeader == BB && L->contains(Pred)) {
 754           // Remove the branch from the latch to the header block, this makes
 755           // the header dead, which will make the latch dead (because the header
 756           // dominates the latch).
 757           LPM->deleteSimpleAnalysisValue(Pred->getTerminator(), L);
 758           Pred->getTerminator()->eraseFromParent();
 759           new UnreachableInst(BB->getContext(), Pred);
 760
 761           // The loop is now broken, remove it from LI.
 762           RemoveLoopFromHierarchy(L);
 763
 764           // Reprocess the header, which now IS dead.
 765           RemoveBlockIfDead(BB, Worklist, L);
 766           return;
 767         }
 768
 769       // If pred ends in a uncond branch, add uncond branch to worklist so that
 770       // the two blocks will get merged.
 771       if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator()))
 772         if (BI->isUnconditional())
 773           Worklist.push_back(BI);
 774     }
 775     return;
 776   }
 777
 778   DEBUG(dbgs() << "Nuking dead block: " << *BB);
 779
 780   // Remove the instructions in the basic block from the worklist.
 781   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
 782     RemoveFromWorklist(I, Worklist);
 783
 784     // Anything that uses the instructions in this basic block should have their
 785     // uses replaced with undefs.
 786     // If I is not void type then replaceAllUsesWith undef.
 787     // This allows ValueHandlers and custom metadata to adjust itself.
 788     if (!I->getType()->isVoidTy())
 789       I->replaceAllUsesWith(UndefValue::get(I->getType()));
 790   }
 791
 792   // If this is the edge to the header block for a loop, remove the loop and
 793   // promote all subloops.
 794   if (Loop *BBLoop = LI->getLoopFor(BB)) {
 795     if (BBLoop->getLoopLatch() == BB)
 796       RemoveLoopFromHierarchy(BBLoop);
 797   }
 798
 799   // Remove the block from the loop info, which removes it from any loops it
 800   // was in.
 801   LI->removeBlock(BB);
 802
 803
 804   // Remove phi node entries in successors for this block.
 805   TerminatorInst *TI = BB->getTerminator();
 806   SmallVector<BasicBlock*, 4> Succs;
 807   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
 808     Succs.push_back(TI->getSuccessor(i));
 809     TI->getSuccessor(i)->removePredecessor(BB);
 810   }
 811
 812   // Unique the successors, remove anything with multiple uses.
 813   array_pod_sort(Succs.begin(), Succs.end());
 814   Succs.erase(std::unique(Succs.begin(), Succs.end()), Succs.end());
 815
 816   // Remove the basic block, including all of the instructions contained in it.
 817   LPM->deleteSimpleAnalysisValue(BB, L);
 818   BB->eraseFromParent();
 819   // Remove successor blocks here that are not dead, so that we know we only
 820   // have dead blocks in this list.  Nondead blocks have a way of becoming dead,
 821   // then getting removed before we revisit them, which is badness.
 822   //
 823   for (unsigned i = 0; i != Succs.size(); ++i)
 824     if (pred_begin(Succs[i]) != pred_end(Succs[i])) {
 825       // One exception is loop headers.  If this block was the preheader for a
 826       // loop, then we DO want to visit the loop so the loop gets deleted.
 827       // We know that if the successor is a loop header, that this loop had to
 828       // be the preheader: the case where this was the latch block was handled
 829       // above and headers can only have two predecessors.
 830       if (!LI->isLoopHeader(Succs[i])) {
 831         Succs.erase(Succs.begin()+i);
 832         --i;
 833       }
 834     }
 835
 836   for (unsigned i = 0, e = Succs.size(); i != e; ++i)
 837     RemoveBlockIfDead(Succs[i], Worklist, L);
 838 }
 839
 840 /// RemoveLoopFromHierarchy - We have discovered that the specified loop has
 841 /// become unwrapped, either because the backedge was deleted, or because the
 842 /// edge into the header was removed.  If the edge into the header from the
 843 /// latch block was removed, the loop is unwrapped but subloops are still alive,
 844 /// so they just reparent loops.  If the loops are actually dead, they will be
 845 /// removed later.
 846 void LoopUnswitch::RemoveLoopFromHierarchy(Loop *L) {
 847   LPM->deleteLoopFromQueue(L);
 848   RemoveLoopFromWorklist(L);
 849 }
 850
 851 // RewriteLoopBodyWithConditionConstant - We know either that the value LIC has
 852 // the value specified by Val in the specified loop, or we know it does NOT have
 853 // that value.  Rewrite any uses of LIC or of properties correlated to it.
 854 void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
 855                                                         Constant *Val,
 856                                                         bool IsEqual) {
 857   assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?");
 858
 859   // FIXME: Support correlated properties, like:
 860   //  for (...)
 861   //    if (li1 < li2)
 862   //      ...
 863   //    if (li1 > li2)
 864   //      ...
 865
 866   // FOLD boolean conditions (X|LIC), (X&LIC).  Fold conditional branches,
 867   // selects, switches.
 868   std::vector<User*> Users(LIC->use_begin(), LIC->use_end());
 869   std::vector<Instruction*> Worklist;
 870   LLVMContext &Context = Val->getContext();
 871
 872
 873   // If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC
 874   // in the loop with the appropriate one directly.
 875   if (IsEqual || (isa<ConstantInt>(Val) &&
 876       Val->getType()->isIntegerTy(1))) {
 877     Value *Replacement;
 878     if (IsEqual)
 879       Replacement = Val;
 880     else
 881       Replacement = ConstantInt::get(Type::getInt1Ty(Val->getContext()),
 882                                      !cast<ConstantInt>(Val)->getZExtValue());
 883
 884     for (unsigned i = 0, e = Users.size(); i != e; ++i)
 885       if (Instruction *U = cast<Instruction>(Users[i])) {
 886         if (!L->contains(U))
 887           continue;
 888         U->replaceUsesOfWith(LIC, Replacement);
 889         Worklist.push_back(U);
 890       }
 891     SimplifyCode(Worklist, L);
 892     return;
 893   }
 894
 895   // Otherwise, we don't know the precise value of LIC, but we do know that it
 896   // is certainly NOT "Val".  As such, simplify any uses in the loop that we
 897   // can.  This case occurs when we unswitch switch statements.
 898   for (unsigned i = 0, e = Users.size(); i != e; ++i) {
 899     Instruction *U = cast<Instruction>(Users[i]);
 900     if (!L->contains(U))
 901       continue;
 902
 903     Worklist.push_back(U);
 904
 905     // TODO: We could do other simplifications, for example, turning
 906     // 'icmp eq LIC, Val' -> false.
 907
 908     // If we know that LIC is not Val, use this info to simplify code.
 909     SwitchInst *SI = dyn_cast<SwitchInst>(U);
 910     if (SI == 0 || !isa<ConstantInt>(Val)) continue;
 911
 912     unsigned DeadCase = SI->findCaseValue(cast<ConstantInt>(Val));
 913     if (DeadCase == 0) continue;  // Default case is live for multiple values.
 914
 915     // Found a dead case value.  Don't remove PHI nodes in the
 916     // successor if they become single-entry, those PHI nodes may
 917     // be in the Users list.
 918
 919     // FIXME: This is a hack.  We need to keep the successor around
 920     // and hooked up so as to preserve the loop structure, because
 921     // trying to update it is complicated.  So instead we preserve the
 922     // loop structure and put the block on a dead code path.
 923     BasicBlock *Switch = SI->getParent();
 924     SplitEdge(Switch, SI->getSuccessor(DeadCase), this);
 925     // Compute the successors instead of relying on the return value
 926     // of SplitEdge, since it may have split the switch successor
 927     // after PHI nodes.
 928     BasicBlock *NewSISucc = SI->getSuccessor(DeadCase);
 929     BasicBlock *OldSISucc = *succ_begin(NewSISucc);
 930     // Create an "unreachable" destination.
 931     BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable",
 932                                            Switch->getParent(),
 933                                            OldSISucc);
 934     new UnreachableInst(Context, Abort);
 935     // Force the new case destination to branch to the "unreachable"
 936     // block while maintaining a (dead) CFG edge to the old block.
 937     NewSISucc->getTerminator()->eraseFromParent();
 938     BranchInst::Create(Abort, OldSISucc,
 939                        ConstantInt::getTrue(Context), NewSISucc);
 940     // Release the PHI operands for this edge.
 941     for (BasicBlock::iterator II = NewSISucc->begin();
 942          PHINode *PN = dyn_cast<PHINode>(II); ++II)
 943       PN->setIncomingValue(PN->getBasicBlockIndex(Switch),
 944                            UndefValue::get(PN->getType()));
 945     // Tell the domtree about the new block. We don't fully update the
 946     // domtree here -- instead we force it to do a full recomputation
 947     // after the pass is complete -- but we do need to inform it of
 948     // new blocks.
 949     if (DT)
 950       DT->addNewBlock(Abort, NewSISucc);
 951   }
 952
 953   SimplifyCode(Worklist, L);
 954 }
 955
 956 /// SimplifyCode - Okay, now that we have simplified some instructions in the
 957 /// loop, walk over it and constant prop, dce, and fold control flow where
 958 /// possible.  Note that this is effectively a very simple loop-structure-aware
 959 /// optimizer.  During processing of this loop, L could very well be deleted, so
 960 /// it must not be used.
 961 ///
 962 /// FIXME: When the loop optimizer is more mature, separate this out to a new
 963 /// pass.
 964 ///
 965 void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) {
 966   while (!Worklist.empty()) {
 967     Instruction *I = Worklist.back();
 968     Worklist.pop_back();
 969
 970     // Simple constant folding.
 971     if (Constant *C = ConstantFoldInstruction(I)) {
 972       ReplaceUsesOfWith(I, C, Worklist, L, LPM);
 973       continue;
 974     }
 975
 976     // Simple DCE.
 977     if (isInstructionTriviallyDead(I)) {
 978       DEBUG(dbgs() << "Remove dead instruction '" << *I);
 979
 980       // Add uses to the worklist, which may be dead now.
 981       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 982         if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
 983           Worklist.push_back(Use);
 984       LPM->deleteSimpleAnalysisValue(I, L);
 985       RemoveFromWorklist(I, Worklist);
 986       I->eraseFromParent();
 987       ++NumSimplify;
 988       continue;
 989     }
 990
 991     // FIXME: Change this to use instruction simplify interfaces!
 992
 993     // Special case hacks that appear commonly in unswitched code.
 994     switch (I->getOpcode()) {
 995     case Instruction::Select:
 996       if (ConstantInt *CB = dyn_cast<ConstantInt>(I->getOperand(0))) {
 997         ReplaceUsesOfWith(I, I->getOperand(!CB->getZExtValue()+1), Worklist, L,
 998                           LPM);
 999         continue;
1000       }
1001       break;
1002     case Instruction::And:
1003       if (isa<ConstantInt>(I->getOperand(0)) &&
1004           // constant -> RHS
1005           I->getOperand(0)->getType()->isIntegerTy(1))
1006         cast<BinaryOperator>(I)->swapOperands();
1007       if (ConstantInt *CB = dyn_cast<ConstantInt>(I->getOperand(1)))
1008         if (CB->getType()->isIntegerTy(1)) {
1009           if (CB->isOne())      // X & 1 -> X
1010             ReplaceUsesOfWith(I, I->getOperand(0), Worklist, L, LPM);
1011           else                  // X & 0 -> 0
1012             ReplaceUsesOfWith(I, I->getOperand(1), Worklist, L, LPM);
1013           continue;
1014         }
1015       break;
1016     case Instruction::Or:
1017       if (isa<ConstantInt>(I->getOperand(0)) &&
1018           // constant -> RHS
1019           I->getOperand(0)->getType()->isIntegerTy(1))
1020         cast<BinaryOperator>(I)->swapOperands();
1021       if (ConstantInt *CB = dyn_cast<ConstantInt>(I->getOperand(1)))
1022         if (CB->getType()->isIntegerTy(1)) {
1023           if (CB->isOne())   // X | 1 -> 1
1024             ReplaceUsesOfWith(I, I->getOperand(1), Worklist, L, LPM);
1025           else                  // X | 0 -> X
1026             ReplaceUsesOfWith(I, I->getOperand(0), Worklist, L, LPM);
1027           continue;
1028         }
1029       break;
1030     case Instruction::Br: {
1031       BranchInst *BI = cast<BranchInst>(I);
1032       if (BI->isUnconditional()) {
1033         // If BI's parent is the only pred of the successor, fold the two blocks
1034         // together.
1035         BasicBlock *Pred = BI->getParent();
1036         BasicBlock *Succ = BI->getSuccessor(0);
1037         BasicBlock *SinglePred = Succ->getSinglePredecessor();
1038         if (!SinglePred) continue;  // Nothing to do.
1039         assert(SinglePred == Pred && "CFG broken");
1040
1041         DEBUG(dbgs() << "Merging blocks: " << Pred->getName() << " <- "
1042               << Succ->getName() << "\n");
1043
1044         // Resolve any single entry PHI nodes in Succ.
1045         while (PHINode *PN = dyn_cast<PHINode>(Succ->begin()))
1046           ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist, L, LPM);
1047
1048         // Move all of the successor contents from Succ to Pred.
1049         Pred->getInstList().splice(BI, Succ->getInstList(), Succ->begin(),
1050                                    Succ->end());
1051         LPM->deleteSimpleAnalysisValue(BI, L);
1052         BI->eraseFromParent();
1053         RemoveFromWorklist(BI, Worklist);
1054
1055         // If Succ has any successors with PHI nodes, update them to have
1056         // entries coming from Pred instead of Succ.
1057         Succ->replaceAllUsesWith(Pred);
1058
1059         // Remove Succ from the loop tree.
1060         LI->removeBlock(Succ);
1061         LPM->deleteSimpleAnalysisValue(Succ, L);
1062         Succ->eraseFromParent();
1063         ++NumSimplify;
1064         break;
1065       }
1066
1067       if (ConstantInt *CB = dyn_cast<ConstantInt>(BI->getCondition())){
1068         // Conditional branch.  Turn it into an unconditional branch, then
1069         // remove dead blocks.
1070         break;  // FIXME: Enable.
1071
1072         DEBUG(dbgs() << "Folded branch: " << *BI);
1073         BasicBlock *DeadSucc = BI->getSuccessor(CB->getZExtValue());
1074         BasicBlock *LiveSucc = BI->getSuccessor(!CB->getZExtValue());
1075         DeadSucc->removePredecessor(BI->getParent(), true);
1076         Worklist.push_back(BranchInst::Create(LiveSucc, BI));
1077         LPM->deleteSimpleAnalysisValue(BI, L);
1078         BI->eraseFromParent();
1079         RemoveFromWorklist(BI, Worklist);
1080         ++NumSimplify;
1081
1082         RemoveBlockIfDead(DeadSucc, Worklist, L);
1083       }
1084       break;
1085     }
1086     }
1087   }
1088 }