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