LLVM API Documentation

LoopUnswitch.cpp
Go to the documentation of this file.
00001 //===-- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop ------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass transforms loops that contain branches on loop-invariant conditions
00011 // to have multiple loops.  For example, it turns the left into the right code:
00012 //
00013 //  for (...)                  if (lic)
00014 //    A                          for (...)
00015 //    if (lic)                     A; B; C
00016 //      B                      else
00017 //    C                          for (...)
00018 //                                 A; C
00019 //
00020 // This can increase the size of the code exponentially (doubling it every time
00021 // a loop is unswitched) so we only unswitch if the resultant code will be
00022 // smaller than a threshold.
00023 //
00024 // This pass expects LICM to be run before it to hoist invariant conditions out
00025 // of the loop, to make the unswitching opportunity obvious.
00026 //
00027 //===----------------------------------------------------------------------===//
00028 
00029 #include "llvm/Transforms/Scalar.h"
00030 #include "llvm/ADT/STLExtras.h"
00031 #include "llvm/ADT/SmallPtrSet.h"
00032 #include "llvm/ADT/Statistic.h"
00033 #include "llvm/Analysis/CodeMetrics.h"
00034 #include "llvm/Analysis/InstructionSimplify.h"
00035 #include "llvm/Analysis/LoopInfo.h"
00036 #include "llvm/Analysis/LoopPass.h"
00037 #include "llvm/Analysis/ScalarEvolution.h"
00038 #include "llvm/Analysis/TargetTransformInfo.h"
00039 #include "llvm/IR/Constants.h"
00040 #include "llvm/IR/DerivedTypes.h"
00041 #include "llvm/IR/Dominators.h"
00042 #include "llvm/IR/Function.h"
00043 #include "llvm/IR/Instructions.h"
00044 #include "llvm/Support/CommandLine.h"
00045 #include "llvm/Support/Debug.h"
00046 #include "llvm/Support/raw_ostream.h"
00047 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00048 #include "llvm/Transforms/Utils/Cloning.h"
00049 #include "llvm/Transforms/Utils/Local.h"
00050 #include <algorithm>
00051 #include <map>
00052 #include <set>
00053 using namespace llvm;
00054 
00055 #define DEBUG_TYPE "loop-unswitch"
00056 
00057 STATISTIC(NumBranches, "Number of branches unswitched");
00058 STATISTIC(NumSwitches, "Number of switches unswitched");
00059 STATISTIC(NumSelects , "Number of selects unswitched");
00060 STATISTIC(NumTrivial , "Number of unswitches that are trivial");
00061 STATISTIC(NumSimplify, "Number of simplifications of unswitched code");
00062 STATISTIC(TotalInsts,  "Total number of instructions analyzed");
00063 
00064 // The specific value of 100 here was chosen based only on intuition and a
00065 // few specific examples.
00066 static cl::opt<unsigned>
00067 Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"),
00068           cl::init(100), cl::Hidden);
00069 
00070 namespace {
00071 
00072   class LUAnalysisCache {
00073 
00074     typedef DenseMap<const SwitchInst*, SmallPtrSet<const Value *, 8> >
00075       UnswitchedValsMap;
00076 
00077     typedef UnswitchedValsMap::iterator UnswitchedValsIt;
00078 
00079     struct LoopProperties {
00080       unsigned CanBeUnswitchedCount;
00081       unsigned SizeEstimation;
00082       UnswitchedValsMap UnswitchedVals;
00083     };
00084 
00085     // Here we use std::map instead of DenseMap, since we need to keep valid
00086     // LoopProperties pointer for current loop for better performance.
00087     typedef std::map<const Loop*, LoopProperties> LoopPropsMap;
00088     typedef LoopPropsMap::iterator LoopPropsMapIt;
00089 
00090     LoopPropsMap LoopsProperties;
00091     UnswitchedValsMap *CurLoopInstructions;
00092     LoopProperties *CurrentLoopProperties;
00093 
00094     // Max size of code we can produce on remained iterations.
00095     unsigned MaxSize;
00096 
00097     public:
00098 
00099       LUAnalysisCache() :
00100         CurLoopInstructions(0), CurrentLoopProperties(0),
00101         MaxSize(Threshold)
00102       {}
00103 
00104       // Analyze loop. Check its size, calculate is it possible to unswitch
00105       // it. Returns true if we can unswitch this loop.
00106       bool countLoop(const Loop *L, const TargetTransformInfo &TTI);
00107 
00108       // Clean all data related to given loop.
00109       void forgetLoop(const Loop *L);
00110 
00111       // Mark case value as unswitched.
00112       // Since SI instruction can be partly unswitched, in order to avoid
00113       // extra unswitching in cloned loops keep track all unswitched values.
00114       void setUnswitched(const SwitchInst *SI, const Value *V);
00115 
00116       // Check was this case value unswitched before or not.
00117       bool isUnswitched(const SwitchInst *SI, const Value *V);
00118 
00119       // Clone all loop-unswitch related loop properties.
00120       // Redistribute unswitching quotas.
00121       // Note, that new loop data is stored inside the VMap.
00122       void cloneData(const Loop *NewLoop, const Loop *OldLoop,
00123                      const ValueToValueMapTy &VMap);
00124   };
00125 
00126   class LoopUnswitch : public LoopPass {
00127     LoopInfo *LI;  // Loop information
00128     LPPassManager *LPM;
00129 
00130     // LoopProcessWorklist - Used to check if second loop needs processing
00131     // after RewriteLoopBodyWithConditionConstant rewrites first loop.
00132     std::vector<Loop*> LoopProcessWorklist;
00133 
00134     LUAnalysisCache BranchesInfo;
00135 
00136     bool OptimizeForSize;
00137     bool redoLoop;
00138 
00139     Loop *currentLoop;
00140     DominatorTree *DT;
00141     BasicBlock *loopHeader;
00142     BasicBlock *loopPreheader;
00143 
00144     // LoopBlocks contains all of the basic blocks of the loop, including the
00145     // preheader of the loop, the body of the loop, and the exit blocks of the
00146     // loop, in that order.
00147     std::vector<BasicBlock*> LoopBlocks;
00148     // NewBlocks contained cloned copy of basic blocks from LoopBlocks.
00149     std::vector<BasicBlock*> NewBlocks;
00150 
00151   public:
00152     static char ID; // Pass ID, replacement for typeid
00153     explicit LoopUnswitch(bool Os = false) :
00154       LoopPass(ID), OptimizeForSize(Os), redoLoop(false),
00155       currentLoop(0), DT(0), loopHeader(0),
00156       loopPreheader(0) {
00157         initializeLoopUnswitchPass(*PassRegistry::getPassRegistry());
00158       }
00159 
00160     bool runOnLoop(Loop *L, LPPassManager &LPM) override;
00161     bool processCurrentLoop();
00162 
00163     /// This transformation requires natural loop information & requires that
00164     /// loop preheaders be inserted into the CFG.
00165     ///
00166     void getAnalysisUsage(AnalysisUsage &AU) const override {
00167       AU.addRequiredID(LoopSimplifyID);
00168       AU.addPreservedID(LoopSimplifyID);
00169       AU.addRequired<LoopInfo>();
00170       AU.addPreserved<LoopInfo>();
00171       AU.addRequiredID(LCSSAID);
00172       AU.addPreservedID(LCSSAID);
00173       AU.addPreserved<DominatorTreeWrapperPass>();
00174       AU.addPreserved<ScalarEvolution>();
00175       AU.addRequired<TargetTransformInfo>();
00176     }
00177 
00178   private:
00179 
00180     void releaseMemory() override {
00181       BranchesInfo.forgetLoop(currentLoop);
00182     }
00183 
00184     void initLoopData() {
00185       loopHeader = currentLoop->getHeader();
00186       loopPreheader = currentLoop->getLoopPreheader();
00187     }
00188 
00189     /// Split all of the edges from inside the loop to their exit blocks.
00190     /// Update the appropriate Phi nodes as we do so.
00191     void SplitExitEdges(Loop *L, const SmallVectorImpl<BasicBlock *> &ExitBlocks);
00192 
00193     bool UnswitchIfProfitable(Value *LoopCond, Constant *Val);
00194     void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
00195                                   BasicBlock *ExitBlock);
00196     void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L);
00197 
00198     void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
00199                                               Constant *Val, bool isEqual);
00200 
00201     void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
00202                                         BasicBlock *TrueDest,
00203                                         BasicBlock *FalseDest,
00204                                         Instruction *InsertPt);
00205 
00206     void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L);
00207     bool IsTrivialUnswitchCondition(Value *Cond, Constant **Val = 0,
00208                                     BasicBlock **LoopExit = 0);
00209 
00210   };
00211 }
00212 
00213 // Analyze loop. Check its size, calculate is it possible to unswitch
00214 // it. Returns true if we can unswitch this loop.
00215 bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI) {
00216 
00217   LoopPropsMapIt PropsIt;
00218   bool Inserted;
00219   std::tie(PropsIt, Inserted) =
00220       LoopsProperties.insert(std::make_pair(L, LoopProperties()));
00221 
00222   LoopProperties &Props = PropsIt->second;
00223 
00224   if (Inserted) {
00225     // New loop.
00226 
00227     // Limit the number of instructions to avoid causing significant code
00228     // expansion, and the number of basic blocks, to avoid loops with
00229     // large numbers of branches which cause loop unswitching to go crazy.
00230     // This is a very ad-hoc heuristic.
00231 
00232     // FIXME: This is overly conservative because it does not take into
00233     // consideration code simplification opportunities and code that can
00234     // be shared by the resultant unswitched loops.
00235     CodeMetrics Metrics;
00236     for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
00237          I != E; ++I)
00238       Metrics.analyzeBasicBlock(*I, TTI);
00239 
00240     Props.SizeEstimation = std::min(Metrics.NumInsts, Metrics.NumBlocks * 5);
00241     Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation);
00242     MaxSize -= Props.SizeEstimation * Props.CanBeUnswitchedCount;
00243 
00244     if (Metrics.notDuplicatable) {
00245       DEBUG(dbgs() << "NOT unswitching loop %"
00246                    << L->getHeader()->getName() << ", contents cannot be "
00247                    << "duplicated!\n");
00248       return false;
00249     }
00250   }
00251 
00252   if (!Props.CanBeUnswitchedCount) {
00253     DEBUG(dbgs() << "NOT unswitching loop %"
00254                  << L->getHeader()->getName() << ", cost too high: "
00255                  << L->getBlocks().size() << "\n");
00256     return false;
00257   }
00258 
00259   // Be careful. This links are good only before new loop addition.
00260   CurrentLoopProperties = &Props;
00261   CurLoopInstructions = &Props.UnswitchedVals;
00262 
00263   return true;
00264 }
00265 
00266 // Clean all data related to given loop.
00267 void LUAnalysisCache::forgetLoop(const Loop *L) {
00268 
00269   LoopPropsMapIt LIt = LoopsProperties.find(L);
00270 
00271   if (LIt != LoopsProperties.end()) {
00272     LoopProperties &Props = LIt->second;
00273     MaxSize += Props.CanBeUnswitchedCount * Props.SizeEstimation;
00274     LoopsProperties.erase(LIt);
00275   }
00276 
00277   CurrentLoopProperties = 0;
00278   CurLoopInstructions = 0;
00279 }
00280 
00281 // Mark case value as unswitched.
00282 // Since SI instruction can be partly unswitched, in order to avoid
00283 // extra unswitching in cloned loops keep track all unswitched values.
00284 void LUAnalysisCache::setUnswitched(const SwitchInst *SI, const Value *V) {
00285   (*CurLoopInstructions)[SI].insert(V);
00286 }
00287 
00288 // Check was this case value unswitched before or not.
00289 bool LUAnalysisCache::isUnswitched(const SwitchInst *SI, const Value *V) {
00290   return (*CurLoopInstructions)[SI].count(V);
00291 }
00292 
00293 // Clone all loop-unswitch related loop properties.
00294 // Redistribute unswitching quotas.
00295 // Note, that new loop data is stored inside the VMap.
00296 void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop,
00297                                 const ValueToValueMapTy &VMap) {
00298 
00299   LoopProperties &NewLoopProps = LoopsProperties[NewLoop];
00300   LoopProperties &OldLoopProps = *CurrentLoopProperties;
00301   UnswitchedValsMap &Insts = OldLoopProps.UnswitchedVals;
00302 
00303   // Reallocate "can-be-unswitched quota"
00304 
00305   --OldLoopProps.CanBeUnswitchedCount;
00306   unsigned Quota = OldLoopProps.CanBeUnswitchedCount;
00307   NewLoopProps.CanBeUnswitchedCount = Quota / 2;
00308   OldLoopProps.CanBeUnswitchedCount = Quota - Quota / 2;
00309 
00310   NewLoopProps.SizeEstimation = OldLoopProps.SizeEstimation;
00311 
00312   // Clone unswitched values info:
00313   // for new loop switches we clone info about values that was
00314   // already unswitched and has redundant successors.
00315   for (UnswitchedValsIt I = Insts.begin(); I != Insts.end(); ++I) {
00316     const SwitchInst *OldInst = I->first;
00317     Value *NewI = VMap.lookup(OldInst);
00318     const SwitchInst *NewInst = cast_or_null<SwitchInst>(NewI);
00319     assert(NewInst && "All instructions that are in SrcBB must be in VMap.");
00320 
00321     NewLoopProps.UnswitchedVals[NewInst] = OldLoopProps.UnswitchedVals[OldInst];
00322   }
00323 }
00324 
00325 char LoopUnswitch::ID = 0;
00326 INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops",
00327                       false, false)
00328 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
00329 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
00330 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
00331 INITIALIZE_PASS_DEPENDENCY(LCSSA)
00332 INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops",
00333                       false, false)
00334 
00335 Pass *llvm::createLoopUnswitchPass(bool Os) {
00336   return new LoopUnswitch(Os);
00337 }
00338 
00339 /// FindLIVLoopCondition - Cond is a condition that occurs in L.  If it is
00340 /// invariant in the loop, or has an invariant piece, return the invariant.
00341 /// Otherwise, return null.
00342 static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) {
00343 
00344   // We started analyze new instruction, increment scanned instructions counter.
00345   ++TotalInsts;
00346 
00347   // We can never unswitch on vector conditions.
00348   if (Cond->getType()->isVectorTy())
00349     return 0;
00350 
00351   // Constants should be folded, not unswitched on!
00352   if (isa<Constant>(Cond)) return 0;
00353 
00354   // TODO: Handle: br (VARIANT|INVARIANT).
00355 
00356   // Hoist simple values out.
00357   if (L->makeLoopInvariant(Cond, Changed))
00358     return Cond;
00359 
00360   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond))
00361     if (BO->getOpcode() == Instruction::And ||
00362         BO->getOpcode() == Instruction::Or) {
00363       // If either the left or right side is invariant, we can unswitch on this,
00364       // which will cause the branch to go away in one loop and the condition to
00365       // simplify in the other one.
00366       if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed))
00367         return LHS;
00368       if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed))
00369         return RHS;
00370     }
00371 
00372   return 0;
00373 }
00374 
00375 bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
00376   if (skipOptnoneFunction(L))
00377     return false;
00378 
00379   LI = &getAnalysis<LoopInfo>();
00380   LPM = &LPM_Ref;
00381   DominatorTreeWrapperPass *DTWP =
00382       getAnalysisIfAvailable<DominatorTreeWrapperPass>();
00383   DT = DTWP ? &DTWP->getDomTree() : 0;
00384   currentLoop = L;
00385   Function *F = currentLoop->getHeader()->getParent();
00386   bool Changed = false;
00387   do {
00388     assert(currentLoop->isLCSSAForm(*DT));
00389     redoLoop = false;
00390     Changed |= processCurrentLoop();
00391   } while(redoLoop);
00392 
00393   if (Changed) {
00394     // FIXME: Reconstruct dom info, because it is not preserved properly.
00395     if (DT)
00396       DT->recalculate(*F);
00397   }
00398   return Changed;
00399 }
00400 
00401 /// processCurrentLoop - Do actual work and unswitch loop if possible
00402 /// and profitable.
00403 bool LoopUnswitch::processCurrentLoop() {
00404   bool Changed = false;
00405 
00406   initLoopData();
00407 
00408   // If LoopSimplify was unable to form a preheader, don't do any unswitching.
00409   if (!loopPreheader)
00410     return false;
00411 
00412   // Loops with indirectbr cannot be cloned.
00413   if (!currentLoop->isSafeToClone())
00414     return false;
00415 
00416   // Without dedicated exits, splitting the exit edge may fail.
00417   if (!currentLoop->hasDedicatedExits())
00418     return false;
00419 
00420   LLVMContext &Context = loopHeader->getContext();
00421 
00422   // Probably we reach the quota of branches for this loop. If so
00423   // stop unswitching.
00424   if (!BranchesInfo.countLoop(currentLoop, getAnalysis<TargetTransformInfo>()))
00425     return false;
00426 
00427   // Loop over all of the basic blocks in the loop.  If we find an interior
00428   // block that is branching on a loop-invariant condition, we can unswitch this
00429   // loop.
00430   for (Loop::block_iterator I = currentLoop->block_begin(),
00431          E = currentLoop->block_end(); I != E; ++I) {
00432     TerminatorInst *TI = (*I)->getTerminator();
00433     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
00434       // If this isn't branching on an invariant condition, we can't unswitch
00435       // it.
00436       if (BI->isConditional()) {
00437         // See if this, or some part of it, is loop invariant.  If so, we can
00438         // unswitch on it if we desire.
00439         Value *LoopCond = FindLIVLoopCondition(BI->getCondition(),
00440                                                currentLoop, Changed);
00441         if (LoopCond && UnswitchIfProfitable(LoopCond,
00442                                              ConstantInt::getTrue(Context))) {
00443           ++NumBranches;
00444           return true;
00445         }
00446       }
00447     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
00448       Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),
00449                                              currentLoop, Changed);
00450       unsigned NumCases = SI->getNumCases();
00451       if (LoopCond && NumCases) {
00452         // Find a value to unswitch on:
00453         // FIXME: this should chose the most expensive case!
00454         // FIXME: scan for a case with a non-critical edge?
00455         Constant *UnswitchVal = 0;
00456 
00457         // Do not process same value again and again.
00458         // At this point we have some cases already unswitched and
00459         // some not yet unswitched. Let's find the first not yet unswitched one.
00460         for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
00461              i != e; ++i) {
00462           Constant *UnswitchValCandidate = i.getCaseValue();
00463           if (!BranchesInfo.isUnswitched(SI, UnswitchValCandidate)) {
00464             UnswitchVal = UnswitchValCandidate;
00465             break;
00466           }
00467         }
00468 
00469         if (!UnswitchVal)
00470           continue;
00471 
00472         if (UnswitchIfProfitable(LoopCond, UnswitchVal)) {
00473           ++NumSwitches;
00474           return true;
00475         }
00476       }
00477     }
00478 
00479     // Scan the instructions to check for unswitchable values.
00480     for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end();
00481          BBI != E; ++BBI)
00482       if (SelectInst *SI = dyn_cast<SelectInst>(BBI)) {
00483         Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),
00484                                                currentLoop, Changed);
00485         if (LoopCond && UnswitchIfProfitable(LoopCond,
00486                                              ConstantInt::getTrue(Context))) {
00487           ++NumSelects;
00488           return true;
00489         }
00490       }
00491   }
00492   return Changed;
00493 }
00494 
00495 /// isTrivialLoopExitBlock - Check to see if all paths from BB exit the
00496 /// loop with no side effects (including infinite loops).
00497 ///
00498 /// If true, we return true and set ExitBB to the block we
00499 /// exit through.
00500 ///
00501 static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB,
00502                                          BasicBlock *&ExitBB,
00503                                          std::set<BasicBlock*> &Visited) {
00504   if (!Visited.insert(BB).second) {
00505     // Already visited. Without more analysis, this could indicate an infinite
00506     // loop.
00507     return false;
00508   }
00509   if (!L->contains(BB)) {
00510     // Otherwise, this is a loop exit, this is fine so long as this is the
00511     // first exit.
00512     if (ExitBB != 0) return false;
00513     ExitBB = BB;
00514     return true;
00515   }
00516 
00517   // Otherwise, this is an unvisited intra-loop node.  Check all successors.
00518   for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) {
00519     // Check to see if the successor is a trivial loop exit.
00520     if (!isTrivialLoopExitBlockHelper(L, *SI, ExitBB, Visited))
00521       return false;
00522   }
00523 
00524   // Okay, everything after this looks good, check to make sure that this block
00525   // doesn't include any side effects.
00526   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
00527     if (I->mayHaveSideEffects())
00528       return false;
00529 
00530   return true;
00531 }
00532 
00533 /// isTrivialLoopExitBlock - Return true if the specified block unconditionally
00534 /// leads to an exit from the specified loop, and has no side-effects in the
00535 /// process.  If so, return the block that is exited to, otherwise return null.
00536 static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) {
00537   std::set<BasicBlock*> Visited;
00538   Visited.insert(L->getHeader());  // Branches to header make infinite loops.
00539   BasicBlock *ExitBB = 0;
00540   if (isTrivialLoopExitBlockHelper(L, BB, ExitBB, Visited))
00541     return ExitBB;
00542   return 0;
00543 }
00544 
00545 /// IsTrivialUnswitchCondition - Check to see if this unswitch condition is
00546 /// trivial: that is, that the condition controls whether or not the loop does
00547 /// anything at all.  If this is a trivial condition, unswitching produces no
00548 /// code duplications (equivalently, it produces a simpler loop and a new empty
00549 /// loop, which gets deleted).
00550 ///
00551 /// If this is a trivial condition, return true, otherwise return false.  When
00552 /// returning true, this sets Cond and Val to the condition that controls the
00553 /// trivial condition: when Cond dynamically equals Val, the loop is known to
00554 /// exit.  Finally, this sets LoopExit to the BB that the loop exits to when
00555 /// Cond == Val.
00556 ///
00557 bool LoopUnswitch::IsTrivialUnswitchCondition(Value *Cond, Constant **Val,
00558                                        BasicBlock **LoopExit) {
00559   BasicBlock *Header = currentLoop->getHeader();
00560   TerminatorInst *HeaderTerm = Header->getTerminator();
00561   LLVMContext &Context = Header->getContext();
00562 
00563   BasicBlock *LoopExitBB = 0;
00564   if (BranchInst *BI = dyn_cast<BranchInst>(HeaderTerm)) {
00565     // If the header block doesn't end with a conditional branch on Cond, we
00566     // can't handle it.
00567     if (!BI->isConditional() || BI->getCondition() != Cond)
00568       return false;
00569 
00570     // Check to see if a successor of the branch is guaranteed to
00571     // exit through a unique exit block without having any
00572     // side-effects.  If so, determine the value of Cond that causes it to do
00573     // this.
00574     if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,
00575                                              BI->getSuccessor(0)))) {
00576       if (Val) *Val = ConstantInt::getTrue(Context);
00577     } else if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,
00578                                                     BI->getSuccessor(1)))) {
00579       if (Val) *Val = ConstantInt::getFalse(Context);
00580     }
00581   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(HeaderTerm)) {
00582     // If this isn't a switch on Cond, we can't handle it.
00583     if (SI->getCondition() != Cond) return false;
00584 
00585     // Check to see if a successor of the switch is guaranteed to go to the
00586     // latch block or exit through a one exit block without having any
00587     // side-effects.  If so, determine the value of Cond that causes it to do
00588     // this.
00589     // Note that we can't trivially unswitch on the default case or
00590     // on already unswitched cases.
00591     for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
00592          i != e; ++i) {
00593       BasicBlock *LoopExitCandidate;
00594       if ((LoopExitCandidate = isTrivialLoopExitBlock(currentLoop,
00595                                                i.getCaseSuccessor()))) {
00596         // Okay, we found a trivial case, remember the value that is trivial.
00597         ConstantInt *CaseVal = i.getCaseValue();
00598 
00599         // Check that it was not unswitched before, since already unswitched
00600         // trivial vals are looks trivial too.
00601         if (BranchesInfo.isUnswitched(SI, CaseVal))
00602           continue;
00603         LoopExitBB = LoopExitCandidate;
00604         if (Val) *Val = CaseVal;
00605         break;
00606       }
00607     }
00608   }
00609 
00610   // If we didn't find a single unique LoopExit block, or if the loop exit block
00611   // contains phi nodes, this isn't trivial.
00612   if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
00613     return false;   // Can't handle this.
00614 
00615   if (LoopExit) *LoopExit = LoopExitBB;
00616 
00617   // We already know that nothing uses any scalar values defined inside of this
00618   // loop.  As such, we just have to check to see if this loop will execute any
00619   // side-effecting instructions (e.g. stores, calls, volatile loads) in the
00620   // part of the loop that the code *would* execute.  We already checked the
00621   // tail, check the header now.
00622   for (BasicBlock::iterator I = Header->begin(), E = Header->end(); I != E; ++I)
00623     if (I->mayHaveSideEffects())
00624       return false;
00625   return true;
00626 }
00627 
00628 /// UnswitchIfProfitable - We have found that we can unswitch currentLoop when
00629 /// LoopCond == Val to simplify the loop.  If we decide that this is profitable,
00630 /// unswitch the loop, reprocess the pieces, then return true.
00631 bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val) {
00632   Function *F = loopHeader->getParent();
00633   Constant *CondVal = 0;
00634   BasicBlock *ExitBlock = 0;
00635 
00636   if (IsTrivialUnswitchCondition(LoopCond, &CondVal, &ExitBlock)) {
00637     // If the condition is trivial, always unswitch. There is no code growth
00638     // for this case.
00639     UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, ExitBlock);
00640     return true;
00641   }
00642 
00643   // Check to see if it would be profitable to unswitch current loop.
00644 
00645   // Do not do non-trivial unswitch while optimizing for size.
00646   if (OptimizeForSize ||
00647       F->getAttributes().hasAttribute(AttributeSet::FunctionIndex,
00648                                       Attribute::OptimizeForSize))
00649     return false;
00650 
00651   UnswitchNontrivialCondition(LoopCond, Val, currentLoop);
00652   return true;
00653 }
00654 
00655 /// CloneLoop - Recursively clone the specified loop and all of its children,
00656 /// mapping the blocks with the specified map.
00657 static Loop *CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
00658                        LoopInfo *LI, LPPassManager *LPM) {
00659   Loop *New = new Loop();
00660   LPM->insertLoop(New, PL);
00661 
00662   // Add all of the blocks in L to the new loop.
00663   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
00664        I != E; ++I)
00665     if (LI->getLoopFor(*I) == L)
00666       New->addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), LI->getBase());
00667 
00668   // Add all of the subloops to the new loop.
00669   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
00670     CloneLoop(*I, New, VM, LI, LPM);
00671 
00672   return New;
00673 }
00674 
00675 /// EmitPreheaderBranchOnCondition - Emit a conditional branch on two values
00676 /// if LIC == Val, branch to TrueDst, otherwise branch to FalseDest.  Insert the
00677 /// code immediately before InsertPt.
00678 void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
00679                                                   BasicBlock *TrueDest,
00680                                                   BasicBlock *FalseDest,
00681                                                   Instruction *InsertPt) {
00682   // Insert a conditional branch on LIC to the two preheaders.  The original
00683   // code is the true version and the new code is the false version.
00684   Value *BranchVal = LIC;
00685   if (!isa<ConstantInt>(Val) ||
00686       Val->getType() != Type::getInt1Ty(LIC->getContext()))
00687     BranchVal = new ICmpInst(InsertPt, ICmpInst::ICMP_EQ, LIC, Val);
00688   else if (Val != ConstantInt::getTrue(Val->getContext()))
00689     // We want to enter the new loop when the condition is true.
00690     std::swap(TrueDest, FalseDest);
00691 
00692   // Insert the new branch.
00693   BranchInst *BI = BranchInst::Create(TrueDest, FalseDest, BranchVal, InsertPt);
00694 
00695   // If either edge is critical, split it. This helps preserve LoopSimplify
00696   // form for enclosing loops.
00697   SplitCriticalEdge(BI, 0, this, false, false, true);
00698   SplitCriticalEdge(BI, 1, this, false, false, true);
00699 }
00700 
00701 /// UnswitchTrivialCondition - Given a loop that has a trivial unswitchable
00702 /// condition in it (a cond branch from its header block to its latch block,
00703 /// where the path through the loop that doesn't execute its body has no
00704 /// side-effects), unswitch it.  This doesn't involve any code duplication, just
00705 /// moving the conditional branch outside of the loop and updating loop info.
00706 void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond,
00707                                             Constant *Val,
00708                                             BasicBlock *ExitBlock) {
00709   DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
00710         << loopHeader->getName() << " [" << L->getBlocks().size()
00711         << " blocks] in Function " << L->getHeader()->getParent()->getName()
00712         << " on cond: " << *Val << " == " << *Cond << "\n");
00713 
00714   // First step, split the preheader, so that we know that there is a safe place
00715   // to insert the conditional branch.  We will change loopPreheader to have a
00716   // conditional branch on Cond.
00717   BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, this);
00718 
00719   // Now that we have a place to insert the conditional branch, create a place
00720   // to branch to: this is the exit block out of the loop that we should
00721   // short-circuit to.
00722 
00723   // Split this block now, so that the loop maintains its exit block, and so
00724   // that the jump from the preheader can execute the contents of the exit block
00725   // without actually branching to it (the exit block should be dominated by the
00726   // loop header, not the preheader).
00727   assert(!L->contains(ExitBlock) && "Exit block is in the loop?");
00728   BasicBlock *NewExit = SplitBlock(ExitBlock, ExitBlock->begin(), this);
00729 
00730   // Okay, now we have a position to branch from and a position to branch to,
00731   // insert the new conditional branch.
00732   EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH,
00733                                  loopPreheader->getTerminator());
00734   LPM->deleteSimpleAnalysisValue(loopPreheader->getTerminator(), L);
00735   loopPreheader->getTerminator()->eraseFromParent();
00736 
00737   // We need to reprocess this loop, it could be unswitched again.
00738   redoLoop = true;
00739 
00740   // Now that we know that the loop is never entered when this condition is a
00741   // particular value, rewrite the loop with this info.  We know that this will
00742   // at least eliminate the old branch.
00743   RewriteLoopBodyWithConditionConstant(L, Cond, Val, false);
00744   ++NumTrivial;
00745 }
00746 
00747 /// SplitExitEdges - Split all of the edges from inside the loop to their exit
00748 /// blocks.  Update the appropriate Phi nodes as we do so.
00749 void LoopUnswitch::SplitExitEdges(Loop *L,
00750                                const SmallVectorImpl<BasicBlock *> &ExitBlocks){
00751 
00752   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
00753     BasicBlock *ExitBlock = ExitBlocks[i];
00754     SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock),
00755                                        pred_end(ExitBlock));
00756 
00757     // Although SplitBlockPredecessors doesn't preserve loop-simplify in
00758     // general, if we call it on all predecessors of all exits then it does.
00759     if (!ExitBlock->isLandingPad()) {
00760       SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", this);
00761     } else {
00762       SmallVector<BasicBlock*, 2> NewBBs;
00763       SplitLandingPadPredecessors(ExitBlock, Preds, ".us-lcssa", ".us-lcssa",
00764                                   this, NewBBs);
00765     }
00766   }
00767 }
00768 
00769 /// UnswitchNontrivialCondition - We determined that the loop is profitable
00770 /// to unswitch when LIC equal Val.  Split it into loop versions and test the
00771 /// condition outside of either loop.  Return the loops created as Out1/Out2.
00772 void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
00773                                                Loop *L) {
00774   Function *F = loopHeader->getParent();
00775   DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"
00776         << loopHeader->getName() << " [" << L->getBlocks().size()
00777         << " blocks] in Function " << F->getName()
00778         << " when '" << *Val << "' == " << *LIC << "\n");
00779 
00780   if (ScalarEvolution *SE = getAnalysisIfAvailable<ScalarEvolution>())
00781     SE->forgetLoop(L);
00782 
00783   LoopBlocks.clear();
00784   NewBlocks.clear();
00785 
00786   // First step, split the preheader and exit blocks, and add these blocks to
00787   // the LoopBlocks list.
00788   BasicBlock *NewPreheader = SplitEdge(loopPreheader, loopHeader, this);
00789   LoopBlocks.push_back(NewPreheader);
00790 
00791   // We want the loop to come after the preheader, but before the exit blocks.
00792   LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
00793 
00794   SmallVector<BasicBlock*, 8> ExitBlocks;
00795   L->getUniqueExitBlocks(ExitBlocks);
00796 
00797   // Split all of the edges from inside the loop to their exit blocks.  Update
00798   // the appropriate Phi nodes as we do so.
00799   SplitExitEdges(L, ExitBlocks);
00800 
00801   // The exit blocks may have been changed due to edge splitting, recompute.
00802   ExitBlocks.clear();
00803   L->getUniqueExitBlocks(ExitBlocks);
00804 
00805   // Add exit blocks to the loop blocks.
00806   LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end());
00807 
00808   // Next step, clone all of the basic blocks that make up the loop (including
00809   // the loop preheader and exit blocks), keeping track of the mapping between
00810   // the instructions and blocks.
00811   NewBlocks.reserve(LoopBlocks.size());
00812   ValueToValueMapTy VMap;
00813   for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) {
00814     BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[i], VMap, ".us", F);
00815 
00816     NewBlocks.push_back(NewBB);
00817     VMap[LoopBlocks[i]] = NewBB;  // Keep the BB mapping.
00818     LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], NewBB, L);
00819   }
00820 
00821   // Splice the newly inserted blocks into the function right before the
00822   // original preheader.
00823   F->getBasicBlockList().splice(NewPreheader, F->getBasicBlockList(),
00824                                 NewBlocks[0], F->end());
00825 
00826   // Now we create the new Loop object for the versioned loop.
00827   Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM);
00828 
00829   // Recalculate unswitching quota, inherit simplified switches info for NewBB,
00830   // Probably clone more loop-unswitch related loop properties.
00831   BranchesInfo.cloneData(NewLoop, L, VMap);
00832 
00833   Loop *ParentLoop = L->getParentLoop();
00834   if (ParentLoop) {
00835     // Make sure to add the cloned preheader and exit blocks to the parent loop
00836     // as well.
00837     ParentLoop->addBasicBlockToLoop(NewBlocks[0], LI->getBase());
00838   }
00839 
00840   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
00841     BasicBlock *NewExit = cast<BasicBlock>(VMap[ExitBlocks[i]]);
00842     // The new exit block should be in the same loop as the old one.
00843     if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i]))
00844       ExitBBLoop->addBasicBlockToLoop(NewExit, LI->getBase());
00845 
00846     assert(NewExit->getTerminator()->getNumSuccessors() == 1 &&
00847            "Exit block should have been split to have one successor!");
00848     BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
00849 
00850     // If the successor of the exit block had PHI nodes, add an entry for
00851     // NewExit.
00852     for (BasicBlock::iterator I = ExitSucc->begin();
00853          PHINode *PN = dyn_cast<PHINode>(I); ++I) {
00854       Value *V = PN->getIncomingValueForBlock(ExitBlocks[i]);
00855       ValueToValueMapTy::iterator It = VMap.find(V);
00856       if (It != VMap.end()) V = It->second;
00857       PN->addIncoming(V, NewExit);
00858     }
00859 
00860     if (LandingPadInst *LPad = NewExit->getLandingPadInst()) {
00861       PHINode *PN = PHINode::Create(LPad->getType(), 0, "",
00862                                     ExitSucc->getFirstInsertionPt());
00863 
00864       for (pred_iterator I = pred_begin(ExitSucc), E = pred_end(ExitSucc);
00865            I != E; ++I) {
00866         BasicBlock *BB = *I;
00867         LandingPadInst *LPI = BB->getLandingPadInst();
00868         LPI->replaceAllUsesWith(PN);
00869         PN->addIncoming(LPI, BB);
00870       }
00871     }
00872   }
00873 
00874   // Rewrite the code to refer to itself.
00875   for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i)
00876     for (BasicBlock::iterator I = NewBlocks[i]->begin(),
00877            E = NewBlocks[i]->end(); I != E; ++I)
00878       RemapInstruction(I, VMap,RF_NoModuleLevelChanges|RF_IgnoreMissingEntries);
00879 
00880   // Rewrite the original preheader to select between versions of the loop.
00881   BranchInst *OldBR = cast<BranchInst>(loopPreheader->getTerminator());
00882   assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] &&
00883          "Preheader splitting did not work correctly!");
00884 
00885   // Emit the new branch that selects between the two versions of this loop.
00886   EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR);
00887   LPM->deleteSimpleAnalysisValue(OldBR, L);
00888   OldBR->eraseFromParent();
00889 
00890   LoopProcessWorklist.push_back(NewLoop);
00891   redoLoop = true;
00892 
00893   // Keep a WeakVH holding onto LIC.  If the first call to RewriteLoopBody
00894   // deletes the instruction (for example by simplifying a PHI that feeds into
00895   // the condition that we're unswitching on), we don't rewrite the second
00896   // iteration.
00897   WeakVH LICHandle(LIC);
00898 
00899   // Now we rewrite the original code to know that the condition is true and the
00900   // new code to know that the condition is false.
00901   RewriteLoopBodyWithConditionConstant(L, LIC, Val, false);
00902 
00903   // It's possible that simplifying one loop could cause the other to be
00904   // changed to another value or a constant.  If its a constant, don't simplify
00905   // it.
00906   if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop &&
00907       LICHandle && !isa<Constant>(LICHandle))
00908     RewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, true);
00909 }
00910 
00911 /// RemoveFromWorklist - Remove all instances of I from the worklist vector
00912 /// specified.
00913 static void RemoveFromWorklist(Instruction *I,
00914                                std::vector<Instruction*> &Worklist) {
00915 
00916   Worklist.erase(std::remove(Worklist.begin(), Worklist.end(), I),
00917                  Worklist.end());
00918 }
00919 
00920 /// ReplaceUsesOfWith - When we find that I really equals V, remove I from the
00921 /// program, replacing all uses with V and update the worklist.
00922 static void ReplaceUsesOfWith(Instruction *I, Value *V,
00923                               std::vector<Instruction*> &Worklist,
00924                               Loop *L, LPPassManager *LPM) {
00925   DEBUG(dbgs() << "Replace with '" << *V << "': " << *I);
00926 
00927   // Add uses to the worklist, which may be dead now.
00928   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
00929     if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
00930       Worklist.push_back(Use);
00931 
00932   // Add users to the worklist which may be simplified now.
00933   for (User *U : I->users())
00934     Worklist.push_back(cast<Instruction>(U));
00935   LPM->deleteSimpleAnalysisValue(I, L);
00936   RemoveFromWorklist(I, Worklist);
00937   I->replaceAllUsesWith(V);
00938   I->eraseFromParent();
00939   ++NumSimplify;
00940 }
00941 
00942 // RewriteLoopBodyWithConditionConstant - We know either that the value LIC has
00943 // the value specified by Val in the specified loop, or we know it does NOT have
00944 // that value.  Rewrite any uses of LIC or of properties correlated to it.
00945 void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
00946                                                         Constant *Val,
00947                                                         bool IsEqual) {
00948   assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?");
00949 
00950   // FIXME: Support correlated properties, like:
00951   //  for (...)
00952   //    if (li1 < li2)
00953   //      ...
00954   //    if (li1 > li2)
00955   //      ...
00956 
00957   // FOLD boolean conditions (X|LIC), (X&LIC).  Fold conditional branches,
00958   // selects, switches.
00959   std::vector<Instruction*> Worklist;
00960   LLVMContext &Context = Val->getContext();
00961 
00962   // If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC
00963   // in the loop with the appropriate one directly.
00964   if (IsEqual || (isa<ConstantInt>(Val) &&
00965       Val->getType()->isIntegerTy(1))) {
00966     Value *Replacement;
00967     if (IsEqual)
00968       Replacement = Val;
00969     else
00970       Replacement = ConstantInt::get(Type::getInt1Ty(Val->getContext()),
00971                                      !cast<ConstantInt>(Val)->getZExtValue());
00972 
00973     for (User *U : LIC->users()) {
00974       Instruction *UI = dyn_cast<Instruction>(U);
00975       if (!UI || !L->contains(UI))
00976         continue;
00977       Worklist.push_back(UI);
00978     }
00979 
00980     for (std::vector<Instruction*>::iterator UI = Worklist.begin(),
00981          UE = Worklist.end(); UI != UE; ++UI)
00982       (*UI)->replaceUsesOfWith(LIC, Replacement);
00983 
00984     SimplifyCode(Worklist, L);
00985     return;
00986   }
00987 
00988   // Otherwise, we don't know the precise value of LIC, but we do know that it
00989   // is certainly NOT "Val".  As such, simplify any uses in the loop that we
00990   // can.  This case occurs when we unswitch switch statements.
00991   for (User *U : LIC->users()) {
00992     Instruction *UI = dyn_cast<Instruction>(U);
00993     if (!UI || !L->contains(UI))
00994       continue;
00995 
00996     Worklist.push_back(UI);
00997 
00998     // TODO: We could do other simplifications, for example, turning
00999     // 'icmp eq LIC, Val' -> false.
01000 
01001     // If we know that LIC is not Val, use this info to simplify code.
01002     SwitchInst *SI = dyn_cast<SwitchInst>(UI);
01003     if (SI == 0 || !isa<ConstantInt>(Val)) continue;
01004 
01005     SwitchInst::CaseIt DeadCase = SI->findCaseValue(cast<ConstantInt>(Val));
01006     // Default case is live for multiple values.
01007     if (DeadCase == SI->case_default()) continue;
01008 
01009     // Found a dead case value.  Don't remove PHI nodes in the
01010     // successor if they become single-entry, those PHI nodes may
01011     // be in the Users list.
01012 
01013     BasicBlock *Switch = SI->getParent();
01014     BasicBlock *SISucc = DeadCase.getCaseSuccessor();
01015     BasicBlock *Latch = L->getLoopLatch();
01016 
01017     BranchesInfo.setUnswitched(SI, Val);
01018 
01019     if (!SI->findCaseDest(SISucc)) continue;  // Edge is critical.
01020     // If the DeadCase successor dominates the loop latch, then the
01021     // transformation isn't safe since it will delete the sole predecessor edge
01022     // to the latch.
01023     if (Latch && DT->dominates(SISucc, Latch))
01024       continue;
01025 
01026     // FIXME: This is a hack.  We need to keep the successor around
01027     // and hooked up so as to preserve the loop structure, because
01028     // trying to update it is complicated.  So instead we preserve the
01029     // loop structure and put the block on a dead code path.
01030     SplitEdge(Switch, SISucc, this);
01031     // Compute the successors instead of relying on the return value
01032     // of SplitEdge, since it may have split the switch successor
01033     // after PHI nodes.
01034     BasicBlock *NewSISucc = DeadCase.getCaseSuccessor();
01035     BasicBlock *OldSISucc = *succ_begin(NewSISucc);
01036     // Create an "unreachable" destination.
01037     BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable",
01038                                            Switch->getParent(),
01039                                            OldSISucc);
01040     new UnreachableInst(Context, Abort);
01041     // Force the new case destination to branch to the "unreachable"
01042     // block while maintaining a (dead) CFG edge to the old block.
01043     NewSISucc->getTerminator()->eraseFromParent();
01044     BranchInst::Create(Abort, OldSISucc,
01045                        ConstantInt::getTrue(Context), NewSISucc);
01046     // Release the PHI operands for this edge.
01047     for (BasicBlock::iterator II = NewSISucc->begin();
01048          PHINode *PN = dyn_cast<PHINode>(II); ++II)
01049       PN->setIncomingValue(PN->getBasicBlockIndex(Switch),
01050                            UndefValue::get(PN->getType()));
01051     // Tell the domtree about the new block. We don't fully update the
01052     // domtree here -- instead we force it to do a full recomputation
01053     // after the pass is complete -- but we do need to inform it of
01054     // new blocks.
01055     if (DT)
01056       DT->addNewBlock(Abort, NewSISucc);
01057   }
01058 
01059   SimplifyCode(Worklist, L);
01060 }
01061 
01062 /// SimplifyCode - Okay, now that we have simplified some instructions in the
01063 /// loop, walk over it and constant prop, dce, and fold control flow where
01064 /// possible.  Note that this is effectively a very simple loop-structure-aware
01065 /// optimizer.  During processing of this loop, L could very well be deleted, so
01066 /// it must not be used.
01067 ///
01068 /// FIXME: When the loop optimizer is more mature, separate this out to a new
01069 /// pass.
01070 ///
01071 void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) {
01072   while (!Worklist.empty()) {
01073     Instruction *I = Worklist.back();
01074     Worklist.pop_back();
01075 
01076     // Simple DCE.
01077     if (isInstructionTriviallyDead(I)) {
01078       DEBUG(dbgs() << "Remove dead instruction '" << *I);
01079 
01080       // Add uses to the worklist, which may be dead now.
01081       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
01082         if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
01083           Worklist.push_back(Use);
01084       LPM->deleteSimpleAnalysisValue(I, L);
01085       RemoveFromWorklist(I, Worklist);
01086       I->eraseFromParent();
01087       ++NumSimplify;
01088       continue;
01089     }
01090 
01091     // See if instruction simplification can hack this up.  This is common for
01092     // things like "select false, X, Y" after unswitching made the condition be
01093     // 'false'.  TODO: update the domtree properly so we can pass it here.
01094     if (Value *V = SimplifyInstruction(I))
01095       if (LI->replacementPreservesLCSSAForm(I, V)) {
01096         ReplaceUsesOfWith(I, V, Worklist, L, LPM);
01097         continue;
01098       }
01099 
01100     // Special case hacks that appear commonly in unswitched code.
01101     if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
01102       if (BI->isUnconditional()) {
01103         // If BI's parent is the only pred of the successor, fold the two blocks
01104         // together.
01105         BasicBlock *Pred = BI->getParent();
01106         BasicBlock *Succ = BI->getSuccessor(0);
01107         BasicBlock *SinglePred = Succ->getSinglePredecessor();
01108         if (!SinglePred) continue;  // Nothing to do.
01109         assert(SinglePred == Pred && "CFG broken");
01110 
01111         DEBUG(dbgs() << "Merging blocks: " << Pred->getName() << " <- "
01112               << Succ->getName() << "\n");
01113 
01114         // Resolve any single entry PHI nodes in Succ.
01115         while (PHINode *PN = dyn_cast<PHINode>(Succ->begin()))
01116           ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist, L, LPM);
01117 
01118         // If Succ has any successors with PHI nodes, update them to have
01119         // entries coming from Pred instead of Succ.
01120         Succ->replaceAllUsesWith(Pred);
01121 
01122         // Move all of the successor contents from Succ to Pred.
01123         Pred->getInstList().splice(BI, Succ->getInstList(), Succ->begin(),
01124                                    Succ->end());
01125         LPM->deleteSimpleAnalysisValue(BI, L);
01126         BI->eraseFromParent();
01127         RemoveFromWorklist(BI, Worklist);
01128 
01129         // Remove Succ from the loop tree.
01130         LI->removeBlock(Succ);
01131         LPM->deleteSimpleAnalysisValue(Succ, L);
01132         Succ->eraseFromParent();
01133         ++NumSimplify;
01134         continue;
01135       }
01136 
01137       continue;
01138     }
01139   }
01140 }