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