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