LLVM  mainline
LoopSimplify.cpp
Go to the documentation of this file.
00001 //===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===//
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 performs several transformations to transform natural loops into a
00011 // simpler form, which makes subsequent analyses and transformations simpler and
00012 // more effective.
00013 //
00014 // Loop pre-header insertion guarantees that there is a single, non-critical
00015 // entry edge from outside of the loop to the loop header.  This simplifies a
00016 // number of analyses and transformations, such as LICM.
00017 //
00018 // Loop exit-block insertion guarantees that all exit blocks from the loop
00019 // (blocks which are outside of the loop that have predecessors inside of the
00020 // loop) only have predecessors from inside of the loop (and are thus dominated
00021 // by the loop header).  This simplifies transformations such as store-sinking
00022 // that are built into LICM.
00023 //
00024 // This pass also guarantees that loops will have exactly one backedge.
00025 //
00026 // Indirectbr instructions introduce several complications. If the loop
00027 // contains or is entered by an indirectbr instruction, it may not be possible
00028 // to transform the loop and make these guarantees. Client code should check
00029 // that these conditions are true before relying on them.
00030 //
00031 // Note that the simplifycfg pass will clean up blocks which are split out but
00032 // end up being unnecessary, so usage of this pass should not pessimize
00033 // generated code.
00034 //
00035 // This pass obviously modifies the CFG, but updates loop information and
00036 // dominator information.
00037 //
00038 //===----------------------------------------------------------------------===//
00039 
00040 #include "llvm/Transforms/Scalar.h"
00041 #include "llvm/ADT/DepthFirstIterator.h"
00042 #include "llvm/ADT/SetOperations.h"
00043 #include "llvm/ADT/SetVector.h"
00044 #include "llvm/ADT/SmallVector.h"
00045 #include "llvm/ADT/Statistic.h"
00046 #include "llvm/Analysis/AliasAnalysis.h"
00047 #include "llvm/Analysis/BasicAliasAnalysis.h"
00048 #include "llvm/Analysis/AssumptionCache.h"
00049 #include "llvm/Analysis/DependenceAnalysis.h"
00050 #include "llvm/Analysis/GlobalsModRef.h"
00051 #include "llvm/Analysis/InstructionSimplify.h"
00052 #include "llvm/Analysis/LoopInfo.h"
00053 #include "llvm/Analysis/ScalarEvolution.h"
00054 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
00055 #include "llvm/IR/CFG.h"
00056 #include "llvm/IR/Constants.h"
00057 #include "llvm/IR/DataLayout.h"
00058 #include "llvm/IR/Dominators.h"
00059 #include "llvm/IR/Function.h"
00060 #include "llvm/IR/Instructions.h"
00061 #include "llvm/IR/IntrinsicInst.h"
00062 #include "llvm/IR/LLVMContext.h"
00063 #include "llvm/IR/Module.h"
00064 #include "llvm/IR/Type.h"
00065 #include "llvm/Support/Debug.h"
00066 #include "llvm/Support/raw_ostream.h"
00067 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00068 #include "llvm/Transforms/Utils/Local.h"
00069 #include "llvm/Transforms/Utils/LoopUtils.h"
00070 using namespace llvm;
00071 
00072 #define DEBUG_TYPE "loop-simplify"
00073 
00074 STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted");
00075 STATISTIC(NumNested  , "Number of nested loops split out");
00076 
00077 // If the block isn't already, move the new block to right after some 'outside
00078 // block' block.  This prevents the preheader from being placed inside the loop
00079 // body, e.g. when the loop hasn't been rotated.
00080 static void placeSplitBlockCarefully(BasicBlock *NewBB,
00081                                      SmallVectorImpl<BasicBlock *> &SplitPreds,
00082                                      Loop *L) {
00083   // Check to see if NewBB is already well placed.
00084   Function::iterator BBI = --NewBB->getIterator();
00085   for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) {
00086     if (&*BBI == SplitPreds[i])
00087       return;
00088   }
00089 
00090   // If it isn't already after an outside block, move it after one.  This is
00091   // always good as it makes the uncond branch from the outside block into a
00092   // fall-through.
00093 
00094   // Figure out *which* outside block to put this after.  Prefer an outside
00095   // block that neighbors a BB actually in the loop.
00096   BasicBlock *FoundBB = nullptr;
00097   for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) {
00098     Function::iterator BBI = SplitPreds[i]->getIterator();
00099     if (++BBI != NewBB->getParent()->end() && L->contains(&*BBI)) {
00100       FoundBB = SplitPreds[i];
00101       break;
00102     }
00103   }
00104 
00105   // If our heuristic for a *good* bb to place this after doesn't find
00106   // anything, just pick something.  It's likely better than leaving it within
00107   // the loop.
00108   if (!FoundBB)
00109     FoundBB = SplitPreds[0];
00110   NewBB->moveAfter(FoundBB);
00111 }
00112 
00113 /// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
00114 /// preheader, this method is called to insert one.  This method has two phases:
00115 /// preheader insertion and analysis updating.
00116 ///
00117 BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, DominatorTree *DT,
00118                                          LoopInfo *LI, bool PreserveLCSSA) {
00119   BasicBlock *Header = L->getHeader();
00120 
00121   // Compute the set of predecessors of the loop that are not in the loop.
00122   SmallVector<BasicBlock*, 8> OutsideBlocks;
00123   for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
00124        PI != PE; ++PI) {
00125     BasicBlock *P = *PI;
00126     if (!L->contains(P)) {         // Coming in from outside the loop?
00127       // If the loop is branched to from an indirect branch, we won't
00128       // be able to fully transform the loop, because it prohibits
00129       // edge splitting.
00130       if (isa<IndirectBrInst>(P->getTerminator())) return nullptr;
00131 
00132       // Keep track of it.
00133       OutsideBlocks.push_back(P);
00134     }
00135   }
00136 
00137   // Split out the loop pre-header.
00138   BasicBlock *PreheaderBB;
00139   PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", DT,
00140                                        LI, PreserveLCSSA);
00141   if (!PreheaderBB)
00142     return nullptr;
00143 
00144   DEBUG(dbgs() << "LoopSimplify: Creating pre-header "
00145                << PreheaderBB->getName() << "\n");
00146 
00147   // Make sure that NewBB is put someplace intelligent, which doesn't mess up
00148   // code layout too horribly.
00149   placeSplitBlockCarefully(PreheaderBB, OutsideBlocks, L);
00150 
00151   return PreheaderBB;
00152 }
00153 
00154 /// \brief Ensure that the loop preheader dominates all exit blocks.
00155 ///
00156 /// This method is used to split exit blocks that have predecessors outside of
00157 /// the loop.
00158 static BasicBlock *rewriteLoopExitBlock(Loop *L, BasicBlock *Exit,
00159                                         DominatorTree *DT, LoopInfo *LI,
00160                                         bool PreserveLCSSA) {
00161   SmallVector<BasicBlock*, 8> LoopBlocks;
00162   for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) {
00163     BasicBlock *P = *I;
00164     if (L->contains(P)) {
00165       // Don't do this if the loop is exited via an indirect branch.
00166       if (isa<IndirectBrInst>(P->getTerminator())) return nullptr;
00167 
00168       LoopBlocks.push_back(P);
00169     }
00170   }
00171 
00172   assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?");
00173   BasicBlock *NewExitBB = nullptr;
00174 
00175   NewExitBB = SplitBlockPredecessors(Exit, LoopBlocks, ".loopexit", DT, LI,
00176                                      PreserveLCSSA);
00177   if (!NewExitBB)
00178     return nullptr;
00179 
00180   DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
00181                << NewExitBB->getName() << "\n");
00182   return NewExitBB;
00183 }
00184 
00185 /// Add the specified block, and all of its predecessors, to the specified set,
00186 /// if it's not already in there.  Stop predecessor traversal when we reach
00187 /// StopBlock.
00188 static void addBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock,
00189                                   std::set<BasicBlock*> &Blocks) {
00190   SmallVector<BasicBlock *, 8> Worklist;
00191   Worklist.push_back(InputBB);
00192   do {
00193     BasicBlock *BB = Worklist.pop_back_val();
00194     if (Blocks.insert(BB).second && BB != StopBlock)
00195       // If BB is not already processed and it is not a stop block then
00196       // insert its predecessor in the work list
00197       for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
00198         BasicBlock *WBB = *I;
00199         Worklist.push_back(WBB);
00200       }
00201   } while (!Worklist.empty());
00202 }
00203 
00204 /// \brief The first part of loop-nestification is to find a PHI node that tells
00205 /// us how to partition the loops.
00206 static PHINode *findPHIToPartitionLoops(Loop *L, DominatorTree *DT,
00207                                         AssumptionCache *AC) {
00208   const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
00209   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
00210     PHINode *PN = cast<PHINode>(I);
00211     ++I;
00212     if (Value *V = SimplifyInstruction(PN, DL, nullptr, DT, AC)) {
00213       // This is a degenerate PHI already, don't modify it!
00214       PN->replaceAllUsesWith(V);
00215       PN->eraseFromParent();
00216       continue;
00217     }
00218 
00219     // Scan this PHI node looking for a use of the PHI node by itself.
00220     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00221       if (PN->getIncomingValue(i) == PN &&
00222           L->contains(PN->getIncomingBlock(i)))
00223         // We found something tasty to remove.
00224         return PN;
00225   }
00226   return nullptr;
00227 }
00228 
00229 /// \brief If this loop has multiple backedges, try to pull one of them out into
00230 /// a nested loop.
00231 ///
00232 /// This is important for code that looks like
00233 /// this:
00234 ///
00235 ///  Loop:
00236 ///     ...
00237 ///     br cond, Loop, Next
00238 ///     ...
00239 ///     br cond2, Loop, Out
00240 ///
00241 /// To identify this common case, we look at the PHI nodes in the header of the
00242 /// loop.  PHI nodes with unchanging values on one backedge correspond to values
00243 /// that change in the "outer" loop, but not in the "inner" loop.
00244 ///
00245 /// If we are able to separate out a loop, return the new outer loop that was
00246 /// created.
00247 ///
00248 static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
00249                                 DominatorTree *DT, LoopInfo *LI,
00250                                 ScalarEvolution *SE, bool PreserveLCSSA,
00251                                 AssumptionCache *AC) {
00252   // Don't try to separate loops without a preheader.
00253   if (!Preheader)
00254     return nullptr;
00255 
00256   // The header is not a landing pad; preheader insertion should ensure this.
00257   BasicBlock *Header = L->getHeader();
00258   assert(!Header->isEHPad() && "Can't insert backedge to EH pad");
00259 
00260   PHINode *PN = findPHIToPartitionLoops(L, DT, AC);
00261   if (!PN) return nullptr;  // No known way to partition.
00262 
00263   // Pull out all predecessors that have varying values in the loop.  This
00264   // handles the case when a PHI node has multiple instances of itself as
00265   // arguments.
00266   SmallVector<BasicBlock*, 8> OuterLoopPreds;
00267   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00268     if (PN->getIncomingValue(i) != PN ||
00269         !L->contains(PN->getIncomingBlock(i))) {
00270       // We can't split indirectbr edges.
00271       if (isa<IndirectBrInst>(PN->getIncomingBlock(i)->getTerminator()))
00272         return nullptr;
00273       OuterLoopPreds.push_back(PN->getIncomingBlock(i));
00274     }
00275   }
00276   DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n");
00277 
00278   // If ScalarEvolution is around and knows anything about values in
00279   // this loop, tell it to forget them, because we're about to
00280   // substantially change it.
00281   if (SE)
00282     SE->forgetLoop(L);
00283 
00284   BasicBlock *NewBB = SplitBlockPredecessors(Header, OuterLoopPreds, ".outer",
00285                                              DT, LI, PreserveLCSSA);
00286 
00287   // Make sure that NewBB is put someplace intelligent, which doesn't mess up
00288   // code layout too horribly.
00289   placeSplitBlockCarefully(NewBB, OuterLoopPreds, L);
00290 
00291   // Create the new outer loop.
00292   Loop *NewOuter = new Loop();
00293 
00294   // Change the parent loop to use the outer loop as its child now.
00295   if (Loop *Parent = L->getParentLoop())
00296     Parent->replaceChildLoopWith(L, NewOuter);
00297   else
00298     LI->changeTopLevelLoop(L, NewOuter);
00299 
00300   // L is now a subloop of our outer loop.
00301   NewOuter->addChildLoop(L);
00302 
00303   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
00304        I != E; ++I)
00305     NewOuter->addBlockEntry(*I);
00306 
00307   // Now reset the header in L, which had been moved by
00308   // SplitBlockPredecessors for the outer loop.
00309   L->moveToHeader(Header);
00310 
00311   // Determine which blocks should stay in L and which should be moved out to
00312   // the Outer loop now.
00313   std::set<BasicBlock*> BlocksInL;
00314   for (pred_iterator PI=pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) {
00315     BasicBlock *P = *PI;
00316     if (DT->dominates(Header, P))
00317       addBlockAndPredsToSet(P, Header, BlocksInL);
00318   }
00319 
00320   // Scan all of the loop children of L, moving them to OuterLoop if they are
00321   // not part of the inner loop.
00322   const std::vector<Loop*> &SubLoops = L->getSubLoops();
00323   for (size_t I = 0; I != SubLoops.size(); )
00324     if (BlocksInL.count(SubLoops[I]->getHeader()))
00325       ++I;   // Loop remains in L
00326     else
00327       NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I));
00328 
00329   // Now that we know which blocks are in L and which need to be moved to
00330   // OuterLoop, move any blocks that need it.
00331   for (unsigned i = 0; i != L->getBlocks().size(); ++i) {
00332     BasicBlock *BB = L->getBlocks()[i];
00333     if (!BlocksInL.count(BB)) {
00334       // Move this block to the parent, updating the exit blocks sets
00335       L->removeBlockFromLoop(BB);
00336       if ((*LI)[BB] == L)
00337         LI->changeLoopFor(BB, NewOuter);
00338       --i;
00339     }
00340   }
00341 
00342   return NewOuter;
00343 }
00344 
00345 /// \brief This method is called when the specified loop has more than one
00346 /// backedge in it.
00347 ///
00348 /// If this occurs, revector all of these backedges to target a new basic block
00349 /// and have that block branch to the loop header.  This ensures that loops
00350 /// have exactly one backedge.
00351 static BasicBlock *insertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader,
00352                                              DominatorTree *DT, LoopInfo *LI) {
00353   assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!");
00354 
00355   // Get information about the loop
00356   BasicBlock *Header = L->getHeader();
00357   Function *F = Header->getParent();
00358 
00359   // Unique backedge insertion currently depends on having a preheader.
00360   if (!Preheader)
00361     return nullptr;
00362 
00363   // The header is not an EH pad; preheader insertion should ensure this.
00364   assert(!Header->isEHPad() && "Can't insert backedge to EH pad");
00365 
00366   // Figure out which basic blocks contain back-edges to the loop header.
00367   std::vector<BasicBlock*> BackedgeBlocks;
00368   for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I){
00369     BasicBlock *P = *I;
00370 
00371     // Indirectbr edges cannot be split, so we must fail if we find one.
00372     if (isa<IndirectBrInst>(P->getTerminator()))
00373       return nullptr;
00374 
00375     if (P != Preheader) BackedgeBlocks.push_back(P);
00376   }
00377 
00378   // Create and insert the new backedge block...
00379   BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(),
00380                                            Header->getName() + ".backedge", F);
00381   BranchInst *BETerminator = BranchInst::Create(Header, BEBlock);
00382   BETerminator->setDebugLoc(Header->getFirstNonPHI()->getDebugLoc());
00383 
00384   DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block "
00385                << BEBlock->getName() << "\n");
00386 
00387   // Move the new backedge block to right after the last backedge block.
00388   Function::iterator InsertPos = ++BackedgeBlocks.back()->getIterator();
00389   F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock);
00390 
00391   // Now that the block has been inserted into the function, create PHI nodes in
00392   // the backedge block which correspond to any PHI nodes in the header block.
00393   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
00394     PHINode *PN = cast<PHINode>(I);
00395     PHINode *NewPN = PHINode::Create(PN->getType(), BackedgeBlocks.size(),
00396                                      PN->getName()+".be", BETerminator);
00397 
00398     // Loop over the PHI node, moving all entries except the one for the
00399     // preheader over to the new PHI node.
00400     unsigned PreheaderIdx = ~0U;
00401     bool HasUniqueIncomingValue = true;
00402     Value *UniqueValue = nullptr;
00403     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00404       BasicBlock *IBB = PN->getIncomingBlock(i);
00405       Value *IV = PN->getIncomingValue(i);
00406       if (IBB == Preheader) {
00407         PreheaderIdx = i;
00408       } else {
00409         NewPN->addIncoming(IV, IBB);
00410         if (HasUniqueIncomingValue) {
00411           if (!UniqueValue)
00412             UniqueValue = IV;
00413           else if (UniqueValue != IV)
00414             HasUniqueIncomingValue = false;
00415         }
00416       }
00417     }
00418 
00419     // Delete all of the incoming values from the old PN except the preheader's
00420     assert(PreheaderIdx != ~0U && "PHI has no preheader entry??");
00421     if (PreheaderIdx != 0) {
00422       PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx));
00423       PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx));
00424     }
00425     // Nuke all entries except the zero'th.
00426     for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i)
00427       PN->removeIncomingValue(e-i, false);
00428 
00429     // Finally, add the newly constructed PHI node as the entry for the BEBlock.
00430     PN->addIncoming(NewPN, BEBlock);
00431 
00432     // As an optimization, if all incoming values in the new PhiNode (which is a
00433     // subset of the incoming values of the old PHI node) have the same value,
00434     // eliminate the PHI Node.
00435     if (HasUniqueIncomingValue) {
00436       NewPN->replaceAllUsesWith(UniqueValue);
00437       BEBlock->getInstList().erase(NewPN);
00438     }
00439   }
00440 
00441   // Now that all of the PHI nodes have been inserted and adjusted, modify the
00442   // backedge blocks to just to the BEBlock instead of the header.
00443   for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) {
00444     TerminatorInst *TI = BackedgeBlocks[i]->getTerminator();
00445     for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op)
00446       if (TI->getSuccessor(Op) == Header)
00447         TI->setSuccessor(Op, BEBlock);
00448   }
00449 
00450   //===--- Update all analyses which we must preserve now -----------------===//
00451 
00452   // Update Loop Information - we know that this block is now in the current
00453   // loop and all parent loops.
00454   L->addBasicBlockToLoop(BEBlock, *LI);
00455 
00456   // Update dominator information
00457   DT->splitBlock(BEBlock);
00458 
00459   return BEBlock;
00460 }
00461 
00462 /// \brief Simplify one loop and queue further loops for simplification.
00463 static bool simplifyOneLoop(Loop *L, SmallVectorImpl<Loop *> &Worklist,
00464                             DominatorTree *DT, LoopInfo *LI,
00465                             ScalarEvolution *SE, AssumptionCache *AC,
00466                             bool PreserveLCSSA) {
00467   bool Changed = false;
00468 ReprocessLoop:
00469 
00470   // Check to see that no blocks (other than the header) in this loop have
00471   // predecessors that are not in the loop.  This is not valid for natural
00472   // loops, but can occur if the blocks are unreachable.  Since they are
00473   // unreachable we can just shamelessly delete those CFG edges!
00474   for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
00475        BB != E; ++BB) {
00476     if (*BB == L->getHeader()) continue;
00477 
00478     SmallPtrSet<BasicBlock*, 4> BadPreds;
00479     for (pred_iterator PI = pred_begin(*BB),
00480          PE = pred_end(*BB); PI != PE; ++PI) {
00481       BasicBlock *P = *PI;
00482       if (!L->contains(P))
00483         BadPreds.insert(P);
00484     }
00485 
00486     // Delete each unique out-of-loop (and thus dead) predecessor.
00487     for (BasicBlock *P : BadPreds) {
00488 
00489       DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor "
00490                    << P->getName() << "\n");
00491 
00492       // Zap the dead pred's terminator and replace it with unreachable.
00493       TerminatorInst *TI = P->getTerminator();
00494       changeToUnreachable(TI, /*UseLLVMTrap=*/false);
00495       Changed = true;
00496     }
00497   }
00498 
00499   // If there are exiting blocks with branches on undef, resolve the undef in
00500   // the direction which will exit the loop. This will help simplify loop
00501   // trip count computations.
00502   SmallVector<BasicBlock*, 8> ExitingBlocks;
00503   L->getExitingBlocks(ExitingBlocks);
00504   for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(),
00505        E = ExitingBlocks.end(); I != E; ++I)
00506     if (BranchInst *BI = dyn_cast<BranchInst>((*I)->getTerminator()))
00507       if (BI->isConditional()) {
00508         if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) {
00509 
00510           DEBUG(dbgs() << "LoopSimplify: Resolving \"br i1 undef\" to exit in "
00511                        << (*I)->getName() << "\n");
00512 
00513           BI->setCondition(ConstantInt::get(Cond->getType(),
00514                                             !L->contains(BI->getSuccessor(0))));
00515 
00516           // This may make the loop analyzable, force SCEV recomputation.
00517           if (SE)
00518             SE->forgetLoop(L);
00519 
00520           Changed = true;
00521         }
00522       }
00523 
00524   // Does the loop already have a preheader?  If so, don't insert one.
00525   BasicBlock *Preheader = L->getLoopPreheader();
00526   if (!Preheader) {
00527     Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA);
00528     if (Preheader) {
00529       ++NumInserted;
00530       Changed = true;
00531     }
00532   }
00533 
00534   // Next, check to make sure that all exit nodes of the loop only have
00535   // predecessors that are inside of the loop.  This check guarantees that the
00536   // loop preheader/header will dominate the exit blocks.  If the exit block has
00537   // predecessors from outside of the loop, split the edge now.
00538   SmallVector<BasicBlock*, 8> ExitBlocks;
00539   L->getExitBlocks(ExitBlocks);
00540 
00541   SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(),
00542                                                ExitBlocks.end());
00543   for (SmallSetVector<BasicBlock *, 8>::iterator I = ExitBlockSet.begin(),
00544          E = ExitBlockSet.end(); I != E; ++I) {
00545     BasicBlock *ExitBlock = *I;
00546     for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock);
00547          PI != PE; ++PI)
00548       // Must be exactly this loop: no subloops, parent loops, or non-loop preds
00549       // allowed.
00550       if (!L->contains(*PI)) {
00551         if (rewriteLoopExitBlock(L, ExitBlock, DT, LI, PreserveLCSSA)) {
00552           ++NumInserted;
00553           Changed = true;
00554         }
00555         break;
00556       }
00557   }
00558 
00559   // If the header has more than two predecessors at this point (from the
00560   // preheader and from multiple backedges), we must adjust the loop.
00561   BasicBlock *LoopLatch = L->getLoopLatch();
00562   if (!LoopLatch) {
00563     // If this is really a nested loop, rip it out into a child loop.  Don't do
00564     // this for loops with a giant number of backedges, just factor them into a
00565     // common backedge instead.
00566     if (L->getNumBackEdges() < 8) {
00567       if (Loop *OuterL =
00568               separateNestedLoop(L, Preheader, DT, LI, SE, PreserveLCSSA, AC)) {
00569         ++NumNested;
00570         // Enqueue the outer loop as it should be processed next in our
00571         // depth-first nest walk.
00572         Worklist.push_back(OuterL);
00573 
00574         // This is a big restructuring change, reprocess the whole loop.
00575         Changed = true;
00576         // GCC doesn't tail recursion eliminate this.
00577         // FIXME: It isn't clear we can't rely on LLVM to TRE this.
00578         goto ReprocessLoop;
00579       }
00580     }
00581 
00582     // If we either couldn't, or didn't want to, identify nesting of the loops,
00583     // insert a new block that all backedges target, then make it jump to the
00584     // loop header.
00585     LoopLatch = insertUniqueBackedgeBlock(L, Preheader, DT, LI);
00586     if (LoopLatch) {
00587       ++NumInserted;
00588       Changed = true;
00589     }
00590   }
00591 
00592   const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
00593 
00594   // Scan over the PHI nodes in the loop header.  Since they now have only two
00595   // incoming values (the loop is canonicalized), we may have simplified the PHI
00596   // down to 'X = phi [X, Y]', which should be replaced with 'Y'.
00597   PHINode *PN;
00598   for (BasicBlock::iterator I = L->getHeader()->begin();
00599        (PN = dyn_cast<PHINode>(I++)); )
00600     if (Value *V = SimplifyInstruction(PN, DL, nullptr, DT, AC)) {
00601       if (SE) SE->forgetValue(PN);
00602       PN->replaceAllUsesWith(V);
00603       PN->eraseFromParent();
00604     }
00605 
00606   // If this loop has multiple exits and the exits all go to the same
00607   // block, attempt to merge the exits. This helps several passes, such
00608   // as LoopRotation, which do not support loops with multiple exits.
00609   // SimplifyCFG also does this (and this code uses the same utility
00610   // function), however this code is loop-aware, where SimplifyCFG is
00611   // not. That gives it the advantage of being able to hoist
00612   // loop-invariant instructions out of the way to open up more
00613   // opportunities, and the disadvantage of having the responsibility
00614   // to preserve dominator information.
00615   bool UniqueExit = true;
00616   if (!ExitBlocks.empty())
00617     for (unsigned i = 1, e = ExitBlocks.size(); i != e; ++i)
00618       if (ExitBlocks[i] != ExitBlocks[0]) {
00619         UniqueExit = false;
00620         break;
00621       }
00622   if (UniqueExit) {
00623     for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
00624       BasicBlock *ExitingBlock = ExitingBlocks[i];
00625       if (!ExitingBlock->getSinglePredecessor()) continue;
00626       BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
00627       if (!BI || !BI->isConditional()) continue;
00628       CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
00629       if (!CI || CI->getParent() != ExitingBlock) continue;
00630 
00631       // Attempt to hoist out all instructions except for the
00632       // comparison and the branch.
00633       bool AllInvariant = true;
00634       bool AnyInvariant = false;
00635       for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) {
00636         Instruction *Inst = &*I++;
00637         // Skip debug info intrinsics.
00638         if (isa<DbgInfoIntrinsic>(Inst))
00639           continue;
00640         if (Inst == CI)
00641           continue;
00642         if (!L->makeLoopInvariant(Inst, AnyInvariant,
00643                                   Preheader ? Preheader->getTerminator()
00644                                             : nullptr)) {
00645           AllInvariant = false;
00646           break;
00647         }
00648       }
00649       if (AnyInvariant) {
00650         Changed = true;
00651         // The loop disposition of all SCEV expressions that depend on any
00652         // hoisted values have also changed.
00653         if (SE)
00654           SE->forgetLoopDispositions(L);
00655       }
00656       if (!AllInvariant) continue;
00657 
00658       // The block has now been cleared of all instructions except for
00659       // a comparison and a conditional branch. SimplifyCFG may be able
00660       // to fold it now.
00661       if (!FoldBranchToCommonDest(BI))
00662         continue;
00663 
00664       // Success. The block is now dead, so remove it from the loop,
00665       // update the dominator tree and delete it.
00666       DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block "
00667                    << ExitingBlock->getName() << "\n");
00668 
00669       // Notify ScalarEvolution before deleting this block. Currently assume the
00670       // parent loop doesn't change (spliting edges doesn't count). If blocks,
00671       // CFG edges, or other values in the parent loop change, then we need call
00672       // to forgetLoop() for the parent instead.
00673       if (SE)
00674         SE->forgetLoop(L);
00675 
00676       assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock));
00677       Changed = true;
00678       LI->removeBlock(ExitingBlock);
00679 
00680       DomTreeNode *Node = DT->getNode(ExitingBlock);
00681       const std::vector<DomTreeNodeBase<BasicBlock> *> &Children =
00682         Node->getChildren();
00683       while (!Children.empty()) {
00684         DomTreeNode *Child = Children.front();
00685         DT->changeImmediateDominator(Child, Node->getIDom());
00686       }
00687       DT->eraseNode(ExitingBlock);
00688 
00689       BI->getSuccessor(0)->removePredecessor(ExitingBlock);
00690       BI->getSuccessor(1)->removePredecessor(ExitingBlock);
00691       ExitingBlock->eraseFromParent();
00692     }
00693   }
00694 
00695   return Changed;
00696 }
00697 
00698 bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
00699                         ScalarEvolution *SE, AssumptionCache *AC,
00700                         bool PreserveLCSSA) {
00701   bool Changed = false;
00702 
00703   // Worklist maintains our depth-first queue of loops in this nest to process.
00704   SmallVector<Loop *, 4> Worklist;
00705   Worklist.push_back(L);
00706 
00707   // Walk the worklist from front to back, pushing newly found sub loops onto
00708   // the back. This will let us process loops from back to front in depth-first
00709   // order. We can use this simple process because loops form a tree.
00710   for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
00711     Loop *L2 = Worklist[Idx];
00712     Worklist.append(L2->begin(), L2->end());
00713   }
00714 
00715   while (!Worklist.empty())
00716     Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, DT, LI, SE,
00717                                AC, PreserveLCSSA);
00718 
00719   return Changed;
00720 }
00721 
00722 namespace {
00723   struct LoopSimplify : public FunctionPass {
00724     static char ID; // Pass identification, replacement for typeid
00725     LoopSimplify() : FunctionPass(ID) {
00726       initializeLoopSimplifyPass(*PassRegistry::getPassRegistry());
00727     }
00728 
00729     DominatorTree *DT;
00730     LoopInfo *LI;
00731     ScalarEvolution *SE;
00732     AssumptionCache *AC;
00733 
00734     bool runOnFunction(Function &F) override;
00735 
00736     void getAnalysisUsage(AnalysisUsage &AU) const override {
00737       AU.addRequired<AssumptionCacheTracker>();
00738 
00739       // We need loop information to identify the loops...
00740       AU.addRequired<DominatorTreeWrapperPass>();
00741       AU.addPreserved<DominatorTreeWrapperPass>();
00742 
00743       AU.addRequired<LoopInfoWrapperPass>();
00744       AU.addPreserved<LoopInfoWrapperPass>();
00745 
00746       AU.addPreserved<BasicAAWrapperPass>();
00747       AU.addPreserved<AAResultsWrapperPass>();
00748       AU.addPreserved<GlobalsAAWrapperPass>();
00749       AU.addPreserved<ScalarEvolutionWrapperPass>();
00750       AU.addPreserved<SCEVAAWrapperPass>();
00751       AU.addPreserved<DependenceAnalysis>();
00752       AU.addPreservedID(BreakCriticalEdgesID);  // No critical edges added.
00753     }
00754 
00755     /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees.
00756     void verifyAnalysis() const override;
00757   };
00758 }
00759 
00760 char LoopSimplify::ID = 0;
00761 INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify",
00762                 "Canonicalize natural loops", false, false)
00763 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
00764 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
00765 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
00766 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
00767 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
00768 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
00769 INITIALIZE_PASS_END(LoopSimplify, "loop-simplify",
00770                 "Canonicalize natural loops", false, false)
00771 
00772 // Publicly exposed interface to pass...
00773 char &llvm::LoopSimplifyID = LoopSimplify::ID;
00774 Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }
00775 
00776 /// runOnFunction - Run down all loops in the CFG (recursively, but we could do
00777 /// it in any convenient order) inserting preheaders...
00778 ///
00779 bool LoopSimplify::runOnFunction(Function &F) {
00780   bool Changed = false;
00781   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
00782   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
00783   auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
00784   SE = SEWP ? &SEWP->getSE() : nullptr;
00785   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
00786   bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
00787 
00788   // Simplify each loop nest in the function.
00789   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
00790     Changed |= simplifyLoop(*I, DT, LI, SE, AC, PreserveLCSSA);
00791 
00792   return Changed;
00793 }
00794 
00795 // FIXME: Restore this code when we re-enable verification in verifyAnalysis
00796 // below.
00797 #if 0
00798 static void verifyLoop(Loop *L) {
00799   // Verify subloops.
00800   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
00801     verifyLoop(*I);
00802 
00803   // It used to be possible to just assert L->isLoopSimplifyForm(), however
00804   // with the introduction of indirectbr, there are now cases where it's
00805   // not possible to transform a loop as necessary. We can at least check
00806   // that there is an indirectbr near any time there's trouble.
00807 
00808   // Indirectbr can interfere with preheader and unique backedge insertion.
00809   if (!L->getLoopPreheader() || !L->getLoopLatch()) {
00810     bool HasIndBrPred = false;
00811     for (pred_iterator PI = pred_begin(L->getHeader()),
00812          PE = pred_end(L->getHeader()); PI != PE; ++PI)
00813       if (isa<IndirectBrInst>((*PI)->getTerminator())) {
00814         HasIndBrPred = true;
00815         break;
00816       }
00817     assert(HasIndBrPred &&
00818            "LoopSimplify has no excuse for missing loop header info!");
00819     (void)HasIndBrPred;
00820   }
00821 
00822   // Indirectbr can interfere with exit block canonicalization.
00823   if (!L->hasDedicatedExits()) {
00824     bool HasIndBrExiting = false;
00825     SmallVector<BasicBlock*, 8> ExitingBlocks;
00826     L->getExitingBlocks(ExitingBlocks);
00827     for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
00828       if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) {
00829         HasIndBrExiting = true;
00830         break;
00831       }
00832     }
00833 
00834     assert(HasIndBrExiting &&
00835            "LoopSimplify has no excuse for missing exit block info!");
00836     (void)HasIndBrExiting;
00837   }
00838 }
00839 #endif
00840 
00841 void LoopSimplify::verifyAnalysis() const {
00842   // FIXME: This routine is being called mid-way through the loop pass manager
00843   // as loop passes destroy this analysis. That's actually fine, but we have no
00844   // way of expressing that here. Once all of the passes that destroy this are
00845   // hoisted out of the loop pass manager we can add back verification here.
00846 #if 0
00847   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
00848     verifyLoop(*I);
00849 #endif
00850 }