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