Home | History | Annotate | Download | only in Scalar
      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 #include "llvm/Transforms/Scalar.h"
     30 #include "llvm/ADT/STLExtras.h"
     31 #include "llvm/ADT/SmallPtrSet.h"
     32 #include "llvm/ADT/Statistic.h"
     33 #include "llvm/Analysis/CodeMetrics.h"
     34 #include "llvm/Analysis/InstructionSimplify.h"
     35 #include "llvm/Analysis/LoopInfo.h"
     36 #include "llvm/Analysis/LoopPass.h"
     37 #include "llvm/Analysis/ScalarEvolution.h"
     38 #include "llvm/Analysis/TargetTransformInfo.h"
     39 #include "llvm/IR/Constants.h"
     40 #include "llvm/IR/DerivedTypes.h"
     41 #include "llvm/IR/Dominators.h"
     42 #include "llvm/IR/Function.h"
     43 #include "llvm/IR/Instructions.h"
     44 #include "llvm/Support/CommandLine.h"
     45 #include "llvm/Support/Debug.h"
     46 #include "llvm/Support/raw_ostream.h"
     47 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
     48 #include "llvm/Transforms/Utils/Cloning.h"
     49 #include "llvm/Transforms/Utils/Local.h"
     50 #include <algorithm>
     51 #include <map>
     52 #include <set>
     53 using namespace llvm;
     54 
     55 #define DEBUG_TYPE "loop-unswitch"
     56 
     57 STATISTIC(NumBranches, "Number of branches unswitched");
     58 STATISTIC(NumSwitches, "Number of switches unswitched");
     59 STATISTIC(NumSelects , "Number of selects unswitched");
     60 STATISTIC(NumTrivial , "Number of unswitches that are trivial");
     61 STATISTIC(NumSimplify, "Number of simplifications of unswitched code");
     62 STATISTIC(TotalInsts,  "Total number of instructions analyzed");
     63 
     64 // The specific value of 100 here was chosen based only on intuition and a
     65 // few specific examples.
     66 static cl::opt<unsigned>
     67 Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"),
     68           cl::init(100), cl::Hidden);
     69 
     70 namespace {
     71 
     72   class LUAnalysisCache {
     73 
     74     typedef DenseMap<const SwitchInst*, SmallPtrSet<const Value *, 8> >
     75       UnswitchedValsMap;
     76 
     77     typedef UnswitchedValsMap::iterator UnswitchedValsIt;
     78 
     79     struct LoopProperties {
     80       unsigned CanBeUnswitchedCount;
     81       unsigned SizeEstimation;
     82       UnswitchedValsMap UnswitchedVals;
     83     };
     84 
     85     // Here we use std::map instead of DenseMap, since we need to keep valid
     86     // LoopProperties pointer for current loop for better performance.
     87     typedef std::map<const Loop*, LoopProperties> LoopPropsMap;
     88     typedef LoopPropsMap::iterator LoopPropsMapIt;
     89 
     90     LoopPropsMap LoopsProperties;
     91     UnswitchedValsMap *CurLoopInstructions;
     92     LoopProperties *CurrentLoopProperties;
     93 
     94     // Max size of code we can produce on remained iterations.
     95     unsigned MaxSize;
     96 
     97     public:
     98 
     99       LUAnalysisCache() :
    100         CurLoopInstructions(nullptr), CurrentLoopProperties(nullptr),
    101         MaxSize(Threshold)
    102       {}
    103 
    104       // Analyze loop. Check its size, calculate is it possible to unswitch
    105       // it. Returns true if we can unswitch this loop.
    106       bool countLoop(const Loop *L, const TargetTransformInfo &TTI);
    107 
    108       // Clean all data related to given loop.
    109       void forgetLoop(const Loop *L);
    110 
    111       // Mark case value as unswitched.
    112       // Since SI instruction can be partly unswitched, in order to avoid
    113       // extra unswitching in cloned loops keep track all unswitched values.
    114       void setUnswitched(const SwitchInst *SI, const Value *V);
    115 
    116       // Check was this case value unswitched before or not.
    117       bool isUnswitched(const SwitchInst *SI, const Value *V);
    118 
    119       // Clone all loop-unswitch related loop properties.
    120       // Redistribute unswitching quotas.
    121       // Note, that new loop data is stored inside the VMap.
    122       void cloneData(const Loop *NewLoop, const Loop *OldLoop,
    123                      const ValueToValueMapTy &VMap);
    124   };
    125 
    126   class LoopUnswitch : public LoopPass {
    127     LoopInfo *LI;  // Loop information
    128     LPPassManager *LPM;
    129 
    130     // LoopProcessWorklist - Used to check if second loop needs processing
    131     // after RewriteLoopBodyWithConditionConstant rewrites first loop.
    132     std::vector<Loop*> LoopProcessWorklist;
    133 
    134     LUAnalysisCache BranchesInfo;
    135 
    136     bool OptimizeForSize;
    137     bool redoLoop;
    138 
    139     Loop *currentLoop;
    140     DominatorTree *DT;
    141     BasicBlock *loopHeader;
    142     BasicBlock *loopPreheader;
    143 
    144     // LoopBlocks contains all of the basic blocks of the loop, including the
    145     // preheader of the loop, the body of the loop, and the exit blocks of the
    146     // loop, in that order.
    147     std::vector<BasicBlock*> LoopBlocks;
    148     // NewBlocks contained cloned copy of basic blocks from LoopBlocks.
    149     std::vector<BasicBlock*> NewBlocks;
    150 
    151   public:
    152     static char ID; // Pass ID, replacement for typeid
    153     explicit LoopUnswitch(bool Os = false) :
    154       LoopPass(ID), OptimizeForSize(Os), redoLoop(false),
    155       currentLoop(nullptr), DT(nullptr), loopHeader(nullptr),
    156       loopPreheader(nullptr) {
    157         initializeLoopUnswitchPass(*PassRegistry::getPassRegistry());
    158       }
    159 
    160     bool runOnLoop(Loop *L, LPPassManager &LPM) override;
    161     bool processCurrentLoop();
    162 
    163     /// This transformation requires natural loop information & requires that
    164     /// loop preheaders be inserted into the CFG.
    165     ///
    166     void getAnalysisUsage(AnalysisUsage &AU) const override {
    167       AU.addRequiredID(LoopSimplifyID);
    168       AU.addPreservedID(LoopSimplifyID);
    169       AU.addRequired<LoopInfo>();
    170       AU.addPreserved<LoopInfo>();
    171       AU.addRequiredID(LCSSAID);
    172       AU.addPreservedID(LCSSAID);
    173       AU.addPreserved<DominatorTreeWrapperPass>();
    174       AU.addPreserved<ScalarEvolution>();
    175       AU.addRequired<TargetTransformInfo>();
    176     }
    177 
    178   private:
    179 
    180     void releaseMemory() override {
    181       BranchesInfo.forgetLoop(currentLoop);
    182     }
    183 
    184     void initLoopData() {
    185       loopHeader = currentLoop->getHeader();
    186       loopPreheader = currentLoop->getLoopPreheader();
    187     }
    188 
    189     /// Split all of the edges from inside the loop to their exit blocks.
    190     /// Update the appropriate Phi nodes as we do so.
    191     void SplitExitEdges(Loop *L, const SmallVectorImpl<BasicBlock *> &ExitBlocks);
    192 
    193     bool UnswitchIfProfitable(Value *LoopCond, Constant *Val);
    194     void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
    195                                   BasicBlock *ExitBlock);
    196     void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L);
    197 
    198     void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
    199                                               Constant *Val, bool isEqual);
    200 
    201     void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
    202                                         BasicBlock *TrueDest,
    203                                         BasicBlock *FalseDest,
    204                                         Instruction *InsertPt);
    205 
    206     void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L);
    207     bool IsTrivialUnswitchCondition(Value *Cond, Constant **Val = nullptr,
    208                                     BasicBlock **LoopExit = nullptr);
    209 
    210   };
    211 }
    212 
    213 // Analyze loop. Check its size, calculate is it possible to unswitch
    214 // it. Returns true if we can unswitch this loop.
    215 bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI) {
    216 
    217   LoopPropsMapIt PropsIt;
    218   bool Inserted;
    219   std::tie(PropsIt, Inserted) =
    220       LoopsProperties.insert(std::make_pair(L, LoopProperties()));
    221 
    222   LoopProperties &Props = PropsIt->second;
    223 
    224   if (Inserted) {
    225     // New loop.
    226 
    227     // Limit the number of instructions to avoid causing significant code
    228     // expansion, and the number of basic blocks, to avoid loops with
    229     // large numbers of branches which cause loop unswitching to go crazy.
    230     // This is a very ad-hoc heuristic.
    231 
    232     // FIXME: This is overly conservative because it does not take into
    233     // consideration code simplification opportunities and code that can
    234     // be shared by the resultant unswitched loops.
    235     CodeMetrics Metrics;
    236     for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
    237          I != E; ++I)
    238       Metrics.analyzeBasicBlock(*I, TTI);
    239 
    240     Props.SizeEstimation = std::min(Metrics.NumInsts, Metrics.NumBlocks * 5);
    241     Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation);
    242     MaxSize -= Props.SizeEstimation * Props.CanBeUnswitchedCount;
    243 
    244     if (Metrics.notDuplicatable) {
    245       DEBUG(dbgs() << "NOT unswitching loop %"
    246                    << L->getHeader()->getName() << ", contents cannot be "
    247                    << "duplicated!\n");
    248       return false;
    249     }
    250   }
    251 
    252   if (!Props.CanBeUnswitchedCount) {
    253     DEBUG(dbgs() << "NOT unswitching loop %"
    254                  << L->getHeader()->getName() << ", cost too high: "
    255                  << L->getBlocks().size() << "\n");
    256     return false;
    257   }
    258 
    259   // Be careful. This links are good only before new loop addition.
    260   CurrentLoopProperties = &Props;
    261   CurLoopInstructions = &Props.UnswitchedVals;
    262 
    263   return true;
    264 }
    265 
    266 // Clean all data related to given loop.
    267 void LUAnalysisCache::forgetLoop(const Loop *L) {
    268 
    269   LoopPropsMapIt LIt = LoopsProperties.find(L);
    270 
    271   if (LIt != LoopsProperties.end()) {
    272     LoopProperties &Props = LIt->second;
    273     MaxSize += Props.CanBeUnswitchedCount * Props.SizeEstimation;
    274     LoopsProperties.erase(LIt);
    275   }
    276 
    277   CurrentLoopProperties = nullptr;
    278   CurLoopInstructions = nullptr;
    279 }
    280 
    281 // Mark case value as unswitched.
    282 // Since SI instruction can be partly unswitched, in order to avoid
    283 // extra unswitching in cloned loops keep track all unswitched values.
    284 void LUAnalysisCache::setUnswitched(const SwitchInst *SI, const Value *V) {
    285   (*CurLoopInstructions)[SI].insert(V);
    286 }
    287 
    288 // Check was this case value unswitched before or not.
    289 bool LUAnalysisCache::isUnswitched(const SwitchInst *SI, const Value *V) {
    290   return (*CurLoopInstructions)[SI].count(V);
    291 }
    292 
    293 // Clone all loop-unswitch related loop properties.
    294 // Redistribute unswitching quotas.
    295 // Note, that new loop data is stored inside the VMap.
    296 void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop,
    297                                 const ValueToValueMapTy &VMap) {
    298 
    299   LoopProperties &NewLoopProps = LoopsProperties[NewLoop];
    300   LoopProperties &OldLoopProps = *CurrentLoopProperties;
    301   UnswitchedValsMap &Insts = OldLoopProps.UnswitchedVals;
    302 
    303   // Reallocate "can-be-unswitched quota"
    304 
    305   --OldLoopProps.CanBeUnswitchedCount;
    306   unsigned Quota = OldLoopProps.CanBeUnswitchedCount;
    307   NewLoopProps.CanBeUnswitchedCount = Quota / 2;
    308   OldLoopProps.CanBeUnswitchedCount = Quota - Quota / 2;
    309 
    310   NewLoopProps.SizeEstimation = OldLoopProps.SizeEstimation;
    311 
    312   // Clone unswitched values info:
    313   // for new loop switches we clone info about values that was
    314   // already unswitched and has redundant successors.
    315   for (UnswitchedValsIt I = Insts.begin(); I != Insts.end(); ++I) {
    316     const SwitchInst *OldInst = I->first;
    317     Value *NewI = VMap.lookup(OldInst);
    318     const SwitchInst *NewInst = cast_or_null<SwitchInst>(NewI);
    319     assert(NewInst && "All instructions that are in SrcBB must be in VMap.");
    320 
    321     NewLoopProps.UnswitchedVals[NewInst] = OldLoopProps.UnswitchedVals[OldInst];
    322   }
    323 }
    324 
    325 char LoopUnswitch::ID = 0;
    326 INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops",
    327                       false, false)
    328 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
    329 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
    330 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
    331 INITIALIZE_PASS_DEPENDENCY(LCSSA)
    332 INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops",
    333                       false, false)
    334 
    335 Pass *llvm::createLoopUnswitchPass(bool Os) {
    336   return new LoopUnswitch(Os);
    337 }
    338 
    339 /// FindLIVLoopCondition - Cond is a condition that occurs in L.  If it is
    340 /// invariant in the loop, or has an invariant piece, return the invariant.
    341 /// Otherwise, return null.
    342 static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) {
    343 
    344   // We started analyze new instruction, increment scanned instructions counter.
    345   ++TotalInsts;
    346 
    347   // We can never unswitch on vector conditions.
    348   if (Cond->getType()->isVectorTy())
    349     return nullptr;
    350 
    351   // Constants should be folded, not unswitched on!
    352   if (isa<Constant>(Cond)) return nullptr;
    353 
    354   // TODO: Handle: br (VARIANT|INVARIANT).
    355 
    356   // Hoist simple values out.
    357   if (L->makeLoopInvariant(Cond, Changed))
    358     return Cond;
    359 
    360   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond))
    361     if (BO->getOpcode() == Instruction::And ||
    362         BO->getOpcode() == Instruction::Or) {
    363       // If either the left or right side is invariant, we can unswitch on this,
    364       // which will cause the branch to go away in one loop and the condition to
    365       // simplify in the other one.
    366       if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed))
    367         return LHS;
    368       if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed))
    369         return RHS;
    370     }
    371 
    372   return nullptr;
    373 }
    374 
    375 bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
    376   if (skipOptnoneFunction(L))
    377     return false;
    378 
    379   LI = &getAnalysis<LoopInfo>();
    380   LPM = &LPM_Ref;
    381   DominatorTreeWrapperPass *DTWP =
    382       getAnalysisIfAvailable<DominatorTreeWrapperPass>();
    383   DT = DTWP ? &DTWP->getDomTree() : nullptr;
    384   currentLoop = L;
    385   Function *F = currentLoop->getHeader()->getParent();
    386   bool Changed = false;
    387   do {
    388     assert(currentLoop->isLCSSAForm(*DT));
    389     redoLoop = false;
    390     Changed |= processCurrentLoop();
    391   } while(redoLoop);
    392 
    393   if (Changed) {
    394     // FIXME: Reconstruct dom info, because it is not preserved properly.
    395     if (DT)
    396       DT->recalculate(*F);
    397   }
    398   return Changed;
    399 }
    400 
    401 /// processCurrentLoop - Do actual work and unswitch loop if possible
    402 /// and profitable.
    403 bool LoopUnswitch::processCurrentLoop() {
    404   bool Changed = false;
    405 
    406   initLoopData();
    407 
    408   // If LoopSimplify was unable to form a preheader, don't do any unswitching.
    409   if (!loopPreheader)
    410     return false;
    411 
    412   // Loops with indirectbr cannot be cloned.
    413   if (!currentLoop->isSafeToClone())
    414     return false;
    415 
    416   // Without dedicated exits, splitting the exit edge may fail.
    417   if (!currentLoop->hasDedicatedExits())
    418     return false;
    419 
    420   LLVMContext &Context = loopHeader->getContext();
    421 
    422   // Probably we reach the quota of branches for this loop. If so
    423   // stop unswitching.
    424   if (!BranchesInfo.countLoop(currentLoop, getAnalysis<TargetTransformInfo>()))
    425     return false;
    426 
    427   // Loop over all of the basic blocks in the loop.  If we find an interior
    428   // block that is branching on a loop-invariant condition, we can unswitch this
    429   // loop.
    430   for (Loop::block_iterator I = currentLoop->block_begin(),
    431          E = currentLoop->block_end(); I != E; ++I) {
    432     TerminatorInst *TI = (*I)->getTerminator();
    433     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
    434       // If this isn't branching on an invariant condition, we can't unswitch
    435       // it.
    436       if (BI->isConditional()) {
    437         // See if this, or some part of it, is loop invariant.  If so, we can
    438         // unswitch on it if we desire.
    439         Value *LoopCond = FindLIVLoopCondition(BI->getCondition(),
    440                                                currentLoop, Changed);
    441         if (LoopCond && UnswitchIfProfitable(LoopCond,
    442                                              ConstantInt::getTrue(Context))) {
    443           ++NumBranches;
    444           return true;
    445         }
    446       }
    447     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
    448       Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),
    449                                              currentLoop, Changed);
    450       unsigned NumCases = SI->getNumCases();
    451       if (LoopCond && NumCases) {
    452         // Find a value to unswitch on:
    453         // FIXME: this should chose the most expensive case!
    454         // FIXME: scan for a case with a non-critical edge?
    455         Constant *UnswitchVal = nullptr;
    456 
    457         // Do not process same value again and again.
    458         // At this point we have some cases already unswitched and
    459         // some not yet unswitched. Let's find the first not yet unswitched one.
    460         for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
    461              i != e; ++i) {
    462           Constant *UnswitchValCandidate = i.getCaseValue();
    463           if (!BranchesInfo.isUnswitched(SI, UnswitchValCandidate)) {
    464             UnswitchVal = UnswitchValCandidate;
    465             break;
    466           }
    467         }
    468 
    469         if (!UnswitchVal)
    470           continue;
    471 
    472         if (UnswitchIfProfitable(LoopCond, UnswitchVal)) {
    473           ++NumSwitches;
    474           return true;
    475         }
    476       }
    477     }
    478 
    479     // Scan the instructions to check for unswitchable values.
    480     for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end();
    481          BBI != E; ++BBI)
    482       if (SelectInst *SI = dyn_cast<SelectInst>(BBI)) {
    483         Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),
    484                                                currentLoop, Changed);
    485         if (LoopCond && UnswitchIfProfitable(LoopCond,
    486                                              ConstantInt::getTrue(Context))) {
    487           ++NumSelects;
    488           return true;
    489         }
    490       }
    491   }
    492   return Changed;
    493 }
    494 
    495 /// isTrivialLoopExitBlock - Check to see if all paths from BB exit the
    496 /// loop with no side effects (including infinite loops).
    497 ///
    498 /// If true, we return true and set ExitBB to the block we
    499 /// exit through.
    500 ///
    501 static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB,
    502                                          BasicBlock *&ExitBB,
    503                                          std::set<BasicBlock*> &Visited) {
    504   if (!Visited.insert(BB).second) {
    505     // Already visited. Without more analysis, this could indicate an infinite
    506     // loop.
    507     return false;
    508   }
    509   if (!L->contains(BB)) {
    510     // Otherwise, this is a loop exit, this is fine so long as this is the
    511     // first exit.
    512     if (ExitBB) return false;
    513     ExitBB = BB;
    514     return true;
    515   }
    516 
    517   // Otherwise, this is an unvisited intra-loop node.  Check all successors.
    518   for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) {
    519     // Check to see if the successor is a trivial loop exit.
    520     if (!isTrivialLoopExitBlockHelper(L, *SI, ExitBB, Visited))
    521       return false;
    522   }
    523 
    524   // Okay, everything after this looks good, check to make sure that this block
    525   // doesn't include any side effects.
    526   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
    527     if (I->mayHaveSideEffects())
    528       return false;
    529 
    530   return true;
    531 }
    532 
    533 /// isTrivialLoopExitBlock - Return true if the specified block unconditionally
    534 /// leads to an exit from the specified loop, and has no side-effects in the
    535 /// process.  If so, return the block that is exited to, otherwise return null.
    536 static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) {
    537   std::set<BasicBlock*> Visited;
    538   Visited.insert(L->getHeader());  // Branches to header make infinite loops.
    539   BasicBlock *ExitBB = nullptr;
    540   if (isTrivialLoopExitBlockHelper(L, BB, ExitBB, Visited))
    541     return ExitBB;
    542   return nullptr;
    543 }
    544 
    545 /// IsTrivialUnswitchCondition - Check to see if this unswitch condition is
    546 /// trivial: that is, that the condition controls whether or not the loop does
    547 /// anything at all.  If this is a trivial condition, unswitching produces no
    548 /// code duplications (equivalently, it produces a simpler loop and a new empty
    549 /// loop, which gets deleted).
    550 ///
    551 /// If this is a trivial condition, return true, otherwise return false.  When
    552 /// returning true, this sets Cond and Val to the condition that controls the
    553 /// trivial condition: when Cond dynamically equals Val, the loop is known to
    554 /// exit.  Finally, this sets LoopExit to the BB that the loop exits to when
    555 /// Cond == Val.
    556 ///
    557 bool LoopUnswitch::IsTrivialUnswitchCondition(Value *Cond, Constant **Val,
    558                                        BasicBlock **LoopExit) {
    559   BasicBlock *Header = currentLoop->getHeader();
    560   TerminatorInst *HeaderTerm = Header->getTerminator();
    561   LLVMContext &Context = Header->getContext();
    562 
    563   BasicBlock *LoopExitBB = nullptr;
    564   if (BranchInst *BI = dyn_cast<BranchInst>(HeaderTerm)) {
    565     // If the header block doesn't end with a conditional branch on Cond, we
    566     // can't handle it.
    567     if (!BI->isConditional() || BI->getCondition() != Cond)
    568       return false;
    569 
    570     // Check to see if a successor of the branch is guaranteed to
    571     // exit through a unique exit block without having any
    572     // side-effects.  If so, determine the value of Cond that causes it to do
    573     // this.
    574     if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,
    575                                              BI->getSuccessor(0)))) {
    576       if (Val) *Val = ConstantInt::getTrue(Context);
    577     } else if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,
    578                                                     BI->getSuccessor(1)))) {
    579       if (Val) *Val = ConstantInt::getFalse(Context);
    580     }
    581   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(HeaderTerm)) {
    582     // If this isn't a switch on Cond, we can't handle it.
    583     if (SI->getCondition() != Cond) return false;
    584 
    585     // Check to see if a successor of the switch is guaranteed to go to the
    586     // latch block or exit through a one exit block without having any
    587     // side-effects.  If so, determine the value of Cond that causes it to do
    588     // this.
    589     // Note that we can't trivially unswitch on the default case or
    590     // on already unswitched cases.
    591     for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
    592          i != e; ++i) {
    593       BasicBlock *LoopExitCandidate;
    594       if ((LoopExitCandidate = isTrivialLoopExitBlock(currentLoop,
    595                                                i.getCaseSuccessor()))) {
    596         // Okay, we found a trivial case, remember the value that is trivial.
    597         ConstantInt *CaseVal = i.getCaseValue();
    598 
    599         // Check that it was not unswitched before, since already unswitched
    600         // trivial vals are looks trivial too.
    601         if (BranchesInfo.isUnswitched(SI, CaseVal))
    602           continue;
    603         LoopExitBB = LoopExitCandidate;
    604         if (Val) *Val = CaseVal;
    605         break;
    606       }
    607     }
    608   }
    609 
    610   // If we didn't find a single unique LoopExit block, or if the loop exit block
    611   // contains phi nodes, this isn't trivial.
    612   if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
    613     return false;   // Can't handle this.
    614 
    615   if (LoopExit) *LoopExit = LoopExitBB;
    616 
    617   // We already know that nothing uses any scalar values defined inside of this
    618   // loop.  As such, we just have to check to see if this loop will execute any
    619   // side-effecting instructions (e.g. stores, calls, volatile loads) in the
    620   // part of the loop that the code *would* execute.  We already checked the
    621   // tail, check the header now.
    622   for (BasicBlock::iterator I = Header->begin(), E = Header->end(); I != E; ++I)
    623     if (I->mayHaveSideEffects())
    624       return false;
    625   return true;
    626 }
    627 
    628 /// UnswitchIfProfitable - We have found that we can unswitch currentLoop when
    629 /// LoopCond == Val to simplify the loop.  If we decide that this is profitable,
    630 /// unswitch the loop, reprocess the pieces, then return true.
    631 bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val) {
    632   Function *F = loopHeader->getParent();
    633   Constant *CondVal = nullptr;
    634   BasicBlock *ExitBlock = nullptr;
    635 
    636   if (IsTrivialUnswitchCondition(LoopCond, &CondVal, &ExitBlock)) {
    637     // If the condition is trivial, always unswitch. There is no code growth
    638     // for this case.
    639     UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, ExitBlock);
    640     return true;
    641   }
    642 
    643   // Check to see if it would be profitable to unswitch current loop.
    644 
    645   // Do not do non-trivial unswitch while optimizing for size.
    646   if (OptimizeForSize ||
    647       F->getAttributes().hasAttribute(AttributeSet::FunctionIndex,
    648                                       Attribute::OptimizeForSize))
    649     return false;
    650 
    651   UnswitchNontrivialCondition(LoopCond, Val, currentLoop);
    652   return true;
    653 }
    654 
    655 /// CloneLoop - Recursively clone the specified loop and all of its children,
    656 /// mapping the blocks with the specified map.
    657 static Loop *CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
    658                        LoopInfo *LI, LPPassManager *LPM) {
    659   Loop *New = new Loop();
    660   LPM->insertLoop(New, PL);
    661 
    662   // Add all of the blocks in L to the new loop.
    663   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
    664        I != E; ++I)
    665     if (LI->getLoopFor(*I) == L)
    666       New->addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), LI->getBase());
    667 
    668   // Add all of the subloops to the new loop.
    669   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
    670     CloneLoop(*I, New, VM, LI, LPM);
    671 
    672   return New;
    673 }
    674 
    675 /// EmitPreheaderBranchOnCondition - Emit a conditional branch on two values
    676 /// if LIC == Val, branch to TrueDst, otherwise branch to FalseDest.  Insert the
    677 /// code immediately before InsertPt.
    678 void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
    679                                                   BasicBlock *TrueDest,
    680                                                   BasicBlock *FalseDest,
    681                                                   Instruction *InsertPt) {
    682   // Insert a conditional branch on LIC to the two preheaders.  The original
    683   // code is the true version and the new code is the false version.
    684   Value *BranchVal = LIC;
    685   if (!isa<ConstantInt>(Val) ||
    686       Val->getType() != Type::getInt1Ty(LIC->getContext()))
    687     BranchVal = new ICmpInst(InsertPt, ICmpInst::ICMP_EQ, LIC, Val);
    688   else if (Val != ConstantInt::getTrue(Val->getContext()))
    689     // We want to enter the new loop when the condition is true.
    690     std::swap(TrueDest, FalseDest);
    691 
    692   // Insert the new branch.
    693   BranchInst *BI = BranchInst::Create(TrueDest, FalseDest, BranchVal, InsertPt);
    694 
    695   // If either edge is critical, split it. This helps preserve LoopSimplify
    696   // form for enclosing loops.
    697   SplitCriticalEdge(BI, 0, this, false, false, true);
    698   SplitCriticalEdge(BI, 1, this, false, false, true);
    699 }
    700 
    701 /// UnswitchTrivialCondition - Given a loop that has a trivial unswitchable
    702 /// condition in it (a cond branch from its header block to its latch block,
    703 /// where the path through the loop that doesn't execute its body has no
    704 /// side-effects), unswitch it.  This doesn't involve any code duplication, just
    705 /// moving the conditional branch outside of the loop and updating loop info.
    706 void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond,
    707                                             Constant *Val,
    708                                             BasicBlock *ExitBlock) {
    709   DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
    710         << loopHeader->getName() << " [" << L->getBlocks().size()
    711         << " blocks] in Function " << L->getHeader()->getParent()->getName()
    712         << " on cond: " << *Val << " == " << *Cond << "\n");
    713 
    714   // First step, split the preheader, so that we know that there is a safe place
    715   // to insert the conditional branch.  We will change loopPreheader to have a
    716   // conditional branch on Cond.
    717   BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, this);
    718 
    719   // Now that we have a place to insert the conditional branch, create a place
    720   // to branch to: this is the exit block out of the loop that we should
    721   // short-circuit to.
    722 
    723   // Split this block now, so that the loop maintains its exit block, and so
    724   // that the jump from the preheader can execute the contents of the exit block
    725   // without actually branching to it (the exit block should be dominated by the
    726   // loop header, not the preheader).
    727   assert(!L->contains(ExitBlock) && "Exit block is in the loop?");
    728   BasicBlock *NewExit = SplitBlock(ExitBlock, ExitBlock->begin(), this);
    729 
    730   // Okay, now we have a position to branch from and a position to branch to,
    731   // insert the new conditional branch.
    732   EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH,
    733                                  loopPreheader->getTerminator());
    734   LPM->deleteSimpleAnalysisValue(loopPreheader->getTerminator(), L);
    735   loopPreheader->getTerminator()->eraseFromParent();
    736 
    737   // We need to reprocess this loop, it could be unswitched again.
    738   redoLoop = true;
    739 
    740   // Now that we know that the loop is never entered when this condition is a
    741   // particular value, rewrite the loop with this info.  We know that this will
    742   // at least eliminate the old branch.
    743   RewriteLoopBodyWithConditionConstant(L, Cond, Val, false);
    744   ++NumTrivial;
    745 }
    746 
    747 /// SplitExitEdges - Split all of the edges from inside the loop to their exit
    748 /// blocks.  Update the appropriate Phi nodes as we do so.
    749 void LoopUnswitch::SplitExitEdges(Loop *L,
    750                                const SmallVectorImpl<BasicBlock *> &ExitBlocks){
    751 
    752   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
    753     BasicBlock *ExitBlock = ExitBlocks[i];
    754     SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock),
    755                                        pred_end(ExitBlock));
    756 
    757     // Although SplitBlockPredecessors doesn't preserve loop-simplify in
    758     // general, if we call it on all predecessors of all exits then it does.
    759     if (!ExitBlock->isLandingPad()) {
    760       SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", this);
    761     } else {
    762       SmallVector<BasicBlock*, 2> NewBBs;
    763       SplitLandingPadPredecessors(ExitBlock, Preds, ".us-lcssa", ".us-lcssa",
    764                                   this, NewBBs);
    765     }
    766   }
    767 }
    768 
    769 /// UnswitchNontrivialCondition - We determined that the loop is profitable
    770 /// to unswitch when LIC equal Val.  Split it into loop versions and test the
    771 /// condition outside of either loop.  Return the loops created as Out1/Out2.
    772 void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
    773                                                Loop *L) {
    774   Function *F = loopHeader->getParent();
    775   DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"
    776         << loopHeader->getName() << " [" << L->getBlocks().size()
    777         << " blocks] in Function " << F->getName()
    778         << " when '" << *Val << "' == " << *LIC << "\n");
    779 
    780   if (ScalarEvolution *SE = getAnalysisIfAvailable<ScalarEvolution>())
    781     SE->forgetLoop(L);
    782 
    783   LoopBlocks.clear();
    784   NewBlocks.clear();
    785 
    786   // First step, split the preheader and exit blocks, and add these blocks to
    787   // the LoopBlocks list.
    788   BasicBlock *NewPreheader = SplitEdge(loopPreheader, loopHeader, this);
    789   LoopBlocks.push_back(NewPreheader);
    790 
    791   // We want the loop to come after the preheader, but before the exit blocks.
    792   LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
    793 
    794   SmallVector<BasicBlock*, 8> ExitBlocks;
    795   L->getUniqueExitBlocks(ExitBlocks);
    796 
    797   // Split all of the edges from inside the loop to their exit blocks.  Update
    798   // the appropriate Phi nodes as we do so.
    799   SplitExitEdges(L, ExitBlocks);
    800 
    801   // The exit blocks may have been changed due to edge splitting, recompute.
    802   ExitBlocks.clear();
    803   L->getUniqueExitBlocks(ExitBlocks);
    804 
    805   // Add exit blocks to the loop blocks.
    806   LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end());
    807 
    808   // Next step, clone all of the basic blocks that make up the loop (including
    809   // the loop preheader and exit blocks), keeping track of the mapping between
    810   // the instructions and blocks.
    811   NewBlocks.reserve(LoopBlocks.size());
    812   ValueToValueMapTy VMap;
    813   for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) {
    814     BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[i], VMap, ".us", F);
    815 
    816     NewBlocks.push_back(NewBB);
    817     VMap[LoopBlocks[i]] = NewBB;  // Keep the BB mapping.
    818     LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], NewBB, L);
    819   }
    820 
    821   // Splice the newly inserted blocks into the function right before the
    822   // original preheader.
    823   F->getBasicBlockList().splice(NewPreheader, F->getBasicBlockList(),
    824                                 NewBlocks[0], F->end());
    825 
    826   // Now we create the new Loop object for the versioned loop.
    827   Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM);
    828 
    829   // Recalculate unswitching quota, inherit simplified switches info for NewBB,
    830   // Probably clone more loop-unswitch related loop properties.
    831   BranchesInfo.cloneData(NewLoop, L, VMap);
    832 
    833   Loop *ParentLoop = L->getParentLoop();
    834   if (ParentLoop) {
    835     // Make sure to add the cloned preheader and exit blocks to the parent loop
    836     // as well.
    837     ParentLoop->addBasicBlockToLoop(NewBlocks[0], LI->getBase());
    838   }
    839 
    840   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
    841     BasicBlock *NewExit = cast<BasicBlock>(VMap[ExitBlocks[i]]);
    842     // The new exit block should be in the same loop as the old one.
    843     if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i]))
    844       ExitBBLoop->addBasicBlockToLoop(NewExit, LI->getBase());
    845 
    846     assert(NewExit->getTerminator()->getNumSuccessors() == 1 &&
    847            "Exit block should have been split to have one successor!");
    848     BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
    849 
    850     // If the successor of the exit block had PHI nodes, add an entry for
    851     // NewExit.
    852     for (BasicBlock::iterator I = ExitSucc->begin();
    853          PHINode *PN = dyn_cast<PHINode>(I); ++I) {
    854       Value *V = PN->getIncomingValueForBlock(ExitBlocks[i]);
    855       ValueToValueMapTy::iterator It = VMap.find(V);
    856       if (It != VMap.end()) V = It->second;
    857       PN->addIncoming(V, NewExit);
    858     }
    859 
    860     if (LandingPadInst *LPad = NewExit->getLandingPadInst()) {
    861       PHINode *PN = PHINode::Create(LPad->getType(), 0, "",
    862                                     ExitSucc->getFirstInsertionPt());
    863 
    864       for (pred_iterator I = pred_begin(ExitSucc), E = pred_end(ExitSucc);
    865            I != E; ++I) {
    866         BasicBlock *BB = *I;
    867         LandingPadInst *LPI = BB->getLandingPadInst();
    868         LPI->replaceAllUsesWith(PN);
    869         PN->addIncoming(LPI, BB);
    870       }
    871     }
    872   }
    873 
    874   // Rewrite the code to refer to itself.
    875   for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i)
    876     for (BasicBlock::iterator I = NewBlocks[i]->begin(),
    877            E = NewBlocks[i]->end(); I != E; ++I)
    878       RemapInstruction(I, VMap,RF_NoModuleLevelChanges|RF_IgnoreMissingEntries);
    879 
    880   // Rewrite the original preheader to select between versions of the loop.
    881   BranchInst *OldBR = cast<BranchInst>(loopPreheader->getTerminator());
    882   assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] &&
    883          "Preheader splitting did not work correctly!");
    884 
    885   // Emit the new branch that selects between the two versions of this loop.
    886   EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR);
    887   LPM->deleteSimpleAnalysisValue(OldBR, L);
    888   OldBR->eraseFromParent();
    889 
    890   LoopProcessWorklist.push_back(NewLoop);
    891   redoLoop = true;
    892 
    893   // Keep a WeakVH holding onto LIC.  If the first call to RewriteLoopBody
    894   // deletes the instruction (for example by simplifying a PHI that feeds into
    895   // the condition that we're unswitching on), we don't rewrite the second
    896   // iteration.
    897   WeakVH LICHandle(LIC);
    898 
    899   // Now we rewrite the original code to know that the condition is true and the
    900   // new code to know that the condition is false.
    901   RewriteLoopBodyWithConditionConstant(L, LIC, Val, false);
    902 
    903   // It's possible that simplifying one loop could cause the other to be
    904   // changed to another value or a constant.  If its a constant, don't simplify
    905   // it.
    906   if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop &&
    907       LICHandle && !isa<Constant>(LICHandle))
    908     RewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, true);
    909 }
    910 
    911 /// RemoveFromWorklist - Remove all instances of I from the worklist vector
    912 /// specified.
    913 static void RemoveFromWorklist(Instruction *I,
    914                                std::vector<Instruction*> &Worklist) {
    915 
    916   Worklist.erase(std::remove(Worklist.begin(), Worklist.end(), I),
    917                  Worklist.end());
    918 }
    919 
    920 /// ReplaceUsesOfWith - When we find that I really equals V, remove I from the
    921 /// program, replacing all uses with V and update the worklist.
    922 static void ReplaceUsesOfWith(Instruction *I, Value *V,
    923                               std::vector<Instruction*> &Worklist,
    924                               Loop *L, LPPassManager *LPM) {
    925   DEBUG(dbgs() << "Replace with '" << *V << "': " << *I);
    926 
    927   // Add uses to the worklist, which may be dead now.
    928   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
    929     if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
    930       Worklist.push_back(Use);
    931 
    932   // Add users to the worklist which may be simplified now.
    933   for (User *U : I->users())
    934     Worklist.push_back(cast<Instruction>(U));
    935   LPM->deleteSimpleAnalysisValue(I, L);
    936   RemoveFromWorklist(I, Worklist);
    937   I->replaceAllUsesWith(V);
    938   I->eraseFromParent();
    939   ++NumSimplify;
    940 }
    941 
    942 // RewriteLoopBodyWithConditionConstant - We know either that the value LIC has
    943 // the value specified by Val in the specified loop, or we know it does NOT have
    944 // that value.  Rewrite any uses of LIC or of properties correlated to it.
    945 void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
    946                                                         Constant *Val,
    947                                                         bool IsEqual) {
    948   assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?");
    949 
    950   // FIXME: Support correlated properties, like:
    951   //  for (...)
    952   //    if (li1 < li2)
    953   //      ...
    954   //    if (li1 > li2)
    955   //      ...
    956 
    957   // FOLD boolean conditions (X|LIC), (X&LIC).  Fold conditional branches,
    958   // selects, switches.
    959   std::vector<Instruction*> Worklist;
    960   LLVMContext &Context = Val->getContext();
    961 
    962   // If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC
    963   // in the loop with the appropriate one directly.
    964   if (IsEqual || (isa<ConstantInt>(Val) &&
    965       Val->getType()->isIntegerTy(1))) {
    966     Value *Replacement;
    967     if (IsEqual)
    968       Replacement = Val;
    969     else
    970       Replacement = ConstantInt::get(Type::getInt1Ty(Val->getContext()),
    971                                      !cast<ConstantInt>(Val)->getZExtValue());
    972 
    973     for (User *U : LIC->users()) {
    974       Instruction *UI = dyn_cast<Instruction>(U);
    975       if (!UI || !L->contains(UI))
    976         continue;
    977       Worklist.push_back(UI);
    978     }
    979 
    980     for (std::vector<Instruction*>::iterator UI = Worklist.begin(),
    981          UE = Worklist.end(); UI != UE; ++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 (User *U : LIC->users()) {
    992     Instruction *UI = dyn_cast<Instruction>(U);
    993     if (!UI || !L->contains(UI))
    994       continue;
    995 
    996     Worklist.push_back(UI);
    997 
    998     // TODO: We could do other simplifications, for example, turning
    999     // 'icmp eq LIC, Val' -> false.
   1000 
   1001     // If we know that LIC is not Val, use this info to simplify code.
   1002     SwitchInst *SI = dyn_cast<SwitchInst>(UI);
   1003     if (!SI || !isa<ConstantInt>(Val)) continue;
   1004 
   1005     SwitchInst::CaseIt DeadCase = SI->findCaseValue(cast<ConstantInt>(Val));
   1006     // Default case is live for multiple values.
   1007     if (DeadCase == SI->case_default()) continue;
   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 = DeadCase.getCaseSuccessor();
   1015     BasicBlock *Latch = L->getLoopLatch();
   1016 
   1017     BranchesInfo.setUnswitched(SI, 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 = DeadCase.getCaseSuccessor();
   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'.  TODO: update the domtree properly so we can pass it here.
   1094     if (Value *V = SimplifyInstruction(I))
   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       continue;
   1138     }
   1139   }
   1140 }
   1141