LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source 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 // Note that the simplifycfg pass will clean up blocks which are split out but
00027 // end up being unnecessary, so usage of this pass should not pessimize
00028 // generated code.
00029 //
00030 // This pass obviously modifies the CFG, but updates loop information and
00031 // dominator information.
00032 //
00033 //===----------------------------------------------------------------------===//
00034 
00035 #include "llvm/Transforms/Scalar.h"
00036 #include "llvm/Constant.h"
00037 #include "llvm/Instructions.h"
00038 #include "llvm/Function.h"
00039 #include "llvm/Type.h"
00040 #include "llvm/Analysis/Dominators.h"
00041 #include "llvm/Analysis/LoopInfo.h"
00042 #include "llvm/Support/CFG.h"
00043 #include "llvm/Transforms/Utils/Local.h"
00044 #include "llvm/ADT/SetOperations.h"
00045 #include "llvm/ADT/SetVector.h"
00046 #include "llvm/ADT/Statistic.h"
00047 #include "llvm/ADT/DepthFirstIterator.h"
00048 using namespace llvm;
00049 
00050 namespace {
00051   Statistic<>
00052   NumInserted("loopsimplify", "Number of pre-header or exit blocks inserted");
00053   Statistic<>
00054   NumNested("loopsimplify", "Number of nested loops split out");
00055 
00056   struct LoopSimplify : public FunctionPass {
00057     virtual bool runOnFunction(Function &F);
00058     
00059     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00060       // We need loop information to identify the loops...
00061       AU.addRequired<LoopInfo>();
00062       AU.addRequired<DominatorSet>();
00063       AU.addRequired<DominatorTree>();
00064 
00065       AU.addPreserved<LoopInfo>();
00066       AU.addPreserved<DominatorSet>();
00067       AU.addPreserved<ImmediateDominators>();
00068       AU.addPreserved<DominatorTree>();
00069       AU.addPreserved<DominanceFrontier>();
00070       AU.addPreservedID(BreakCriticalEdgesID);  // No crit edges added....
00071     }
00072   private:
00073     bool ProcessLoop(Loop *L);
00074     BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix,
00075                                        const std::vector<BasicBlock*> &Preds);
00076     BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit);
00077     void InsertPreheaderForLoop(Loop *L);
00078     Loop *SeparateNestedLoop(Loop *L);
00079     void InsertUniqueBackedgeBlock(Loop *L);
00080 
00081     void UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB,
00082                                          std::vector<BasicBlock*> &PredBlocks);
00083   };
00084 
00085   RegisterOpt<LoopSimplify>
00086   X("loopsimplify", "Canonicalize natural loops", true);
00087 }
00088 
00089 // Publically exposed interface to pass...
00090 const PassInfo *llvm::LoopSimplifyID = X.getPassInfo();
00091 FunctionPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }
00092 
00093 /// runOnFunction - Run down all loops in the CFG (recursively, but we could do
00094 /// it in any convenient order) inserting preheaders...
00095 ///
00096 bool LoopSimplify::runOnFunction(Function &F) {
00097   bool Changed = false;
00098   LoopInfo &LI = getAnalysis<LoopInfo>();
00099 
00100   for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I)
00101     Changed |= ProcessLoop(*I);
00102 
00103   return Changed;
00104 }
00105 
00106 
00107 /// ProcessLoop - Walk the loop structure in depth first order, ensuring that
00108 /// all loops have preheaders.
00109 ///
00110 bool LoopSimplify::ProcessLoop(Loop *L) {
00111   bool Changed = false;
00112 
00113   // Check to see that no blocks (other than the header) in the loop have
00114   // predecessors that are not in the loop.  This is not valid for natural
00115   // loops, but can occur if the blocks are unreachable.  Since they are
00116   // unreachable we can just shamelessly destroy their terminators to make them
00117   // not branch into the loop!
00118   assert(L->getBlocks()[0] == L->getHeader() &&
00119          "Header isn't first block in loop?");
00120   for (unsigned i = 1, e = L->getBlocks().size(); i != e; ++i) {
00121     BasicBlock *LoopBB = L->getBlocks()[i];
00122   Retry:
00123     for (pred_iterator PI = pred_begin(LoopBB), E = pred_end(LoopBB);
00124          PI != E; ++PI)
00125       if (!L->contains(*PI)) {
00126         // This predecessor is not in the loop.  Kill its terminator!
00127         BasicBlock *DeadBlock = *PI;
00128         for (succ_iterator SI = succ_begin(DeadBlock), E = succ_end(DeadBlock);
00129              SI != E; ++SI)
00130           (*SI)->removePredecessor(DeadBlock);  // Remove PHI node entries
00131 
00132         // Delete the dead terminator.
00133         DeadBlock->getInstList().pop_back();
00134 
00135         Value *RetVal = 0;
00136         if (LoopBB->getParent()->getReturnType() != Type::VoidTy)
00137           RetVal = Constant::getNullValue(LoopBB->getParent()->getReturnType());
00138         new ReturnInst(RetVal, DeadBlock);
00139         goto Retry;  // We just invalidated the pred_iterator.  Retry.
00140       }
00141   }
00142 
00143   // Does the loop already have a preheader?  If so, don't modify the loop...
00144   if (L->getLoopPreheader() == 0) {
00145     InsertPreheaderForLoop(L);
00146     NumInserted++;
00147     Changed = true;
00148   }
00149 
00150   // Next, check to make sure that all exit nodes of the loop only have
00151   // predecessors that are inside of the loop.  This check guarantees that the
00152   // loop preheader/header will dominate the exit blocks.  If the exit block has
00153   // predecessors from outside of the loop, split the edge now.
00154   std::vector<BasicBlock*> ExitBlocks;
00155   L->getExitBlocks(ExitBlocks);
00156 
00157   SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end());
00158   for (SetVector<BasicBlock*>::iterator I = ExitBlockSet.begin(),
00159          E = ExitBlockSet.end(); I != E; ++I) {
00160     BasicBlock *ExitBlock = *I;
00161     for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock);
00162          PI != PE; ++PI)
00163       if (!L->contains(*PI)) {
00164         RewriteLoopExitBlock(L, ExitBlock);
00165         NumInserted++;
00166         Changed = true;
00167         break;
00168       }
00169   }
00170 
00171   // If the header has more than two predecessors at this point (from the
00172   // preheader and from multiple backedges), we must adjust the loop.
00173   if (L->getNumBackEdges() != 1) {
00174     // If this is really a nested loop, rip it out into a child loop.
00175     if (Loop *NL = SeparateNestedLoop(L)) {
00176       ++NumNested;
00177       // This is a big restructuring change, reprocess the whole loop.
00178       ProcessLoop(NL);
00179       return true;
00180     }
00181 
00182     InsertUniqueBackedgeBlock(L);
00183     NumInserted++;
00184     Changed = true;
00185   }
00186 
00187   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
00188     Changed |= ProcessLoop(*I);
00189   return Changed;
00190 }
00191 
00192 /// SplitBlockPredecessors - Split the specified block into two blocks.  We want
00193 /// to move the predecessors specified in the Preds list to point to the new
00194 /// block, leaving the remaining predecessors pointing to BB.  This method
00195 /// updates the SSA PHINode's, but no other analyses.
00196 ///
00197 BasicBlock *LoopSimplify::SplitBlockPredecessors(BasicBlock *BB,
00198                                                  const char *Suffix,
00199                                        const std::vector<BasicBlock*> &Preds) {
00200   
00201   // Create new basic block, insert right before the original block...
00202   BasicBlock *NewBB = new BasicBlock(BB->getName()+Suffix, BB->getParent(), BB);
00203 
00204   // The preheader first gets an unconditional branch to the loop header...
00205   BranchInst *BI = new BranchInst(BB, NewBB);
00206   
00207   // For every PHI node in the block, insert a PHI node into NewBB where the
00208   // incoming values from the out of loop edges are moved to NewBB.  We have two
00209   // possible cases here.  If the loop is dead, we just insert dummy entries
00210   // into the PHI nodes for the new edge.  If the loop is not dead, we move the
00211   // incoming edges in BB into new PHI nodes in NewBB.
00212   //
00213   if (!Preds.empty()) {  // Is the loop not obviously dead?
00214     // Check to see if the values being merged into the new block need PHI
00215     // nodes.  If so, insert them.
00216     for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) {
00217       PHINode *PN = cast<PHINode>(I);
00218       ++I;
00219 
00220       // Check to see if all of the values coming in are the same.  If so, we
00221       // don't need to create a new PHI node.
00222       Value *InVal = PN->getIncomingValueForBlock(Preds[0]);
00223       for (unsigned i = 1, e = Preds.size(); i != e; ++i)
00224         if (InVal != PN->getIncomingValueForBlock(Preds[i])) {
00225           InVal = 0;
00226           break;
00227         }
00228       
00229       // If the values coming into the block are not the same, we need a PHI.
00230       if (InVal == 0) {
00231         // Create the new PHI node, insert it into NewBB at the end of the block
00232         PHINode *NewPHI = new PHINode(PN->getType(), PN->getName()+".ph", BI);
00233         
00234         // Move all of the edges from blocks outside the loop to the new PHI
00235         for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
00236           Value *V = PN->removeIncomingValue(Preds[i], false);
00237           NewPHI->addIncoming(V, Preds[i]);
00238         }
00239         InVal = NewPHI;
00240       } else {
00241         // Remove all of the edges coming into the PHI nodes from outside of the
00242         // block.
00243         for (unsigned i = 0, e = Preds.size(); i != e; ++i)
00244           PN->removeIncomingValue(Preds[i], false);
00245       }
00246 
00247       // Add an incoming value to the PHI node in the loop for the preheader
00248       // edge.
00249       PN->addIncoming(InVal, NewBB);
00250 
00251       // Can we eliminate this phi node now?
00252       if (Value *V = hasConstantValue(PN)) {
00253         if (!isa<Instruction>(V) ||
00254             getAnalysis<DominatorSet>().dominates(cast<Instruction>(V), PN)) {
00255           PN->replaceAllUsesWith(V);
00256           BB->getInstList().erase(PN);
00257         }
00258       }
00259     }
00260     
00261     // Now that the PHI nodes are updated, actually move the edges from
00262     // Preds to point to NewBB instead of BB.
00263     //
00264     for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
00265       TerminatorInst *TI = Preds[i]->getTerminator();
00266       for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s)
00267         if (TI->getSuccessor(s) == BB)
00268           TI->setSuccessor(s, NewBB);
00269     }
00270     
00271   } else {                       // Otherwise the loop is dead...
00272     for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) {
00273       PHINode *PN = cast<PHINode>(I);
00274       // Insert dummy values as the incoming value...
00275       PN->addIncoming(Constant::getNullValue(PN->getType()), NewBB);
00276     }
00277   }  
00278   return NewBB;
00279 }
00280 
00281 /// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
00282 /// preheader, this method is called to insert one.  This method has two phases:
00283 /// preheader insertion and analysis updating.
00284 ///
00285 void LoopSimplify::InsertPreheaderForLoop(Loop *L) {
00286   BasicBlock *Header = L->getHeader();
00287 
00288   // Compute the set of predecessors of the loop that are not in the loop.
00289   std::vector<BasicBlock*> OutsideBlocks;
00290   for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
00291        PI != PE; ++PI)
00292       if (!L->contains(*PI))           // Coming in from outside the loop?
00293         OutsideBlocks.push_back(*PI);  // Keep track of it...
00294   
00295   // Split out the loop pre-header
00296   BasicBlock *NewBB =
00297     SplitBlockPredecessors(Header, ".preheader", OutsideBlocks);
00298   
00299   //===--------------------------------------------------------------------===//
00300   //  Update analysis results now that we have performed the transformation
00301   //
00302   
00303   // We know that we have loop information to update... update it now.
00304   if (Loop *Parent = L->getParentLoop())
00305     Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>());
00306 
00307   // If the header for the loop used to be an exit node for another loop, then
00308   // we need to update this to know that the loop-preheader is now the exit
00309   // node.  Note that the only loop that could have our header as an exit node
00310   // is a sibling loop, ie, one with the same parent loop, or one if it's
00311   // children.
00312   //
00313   LoopInfo::iterator ParentLoops, ParentLoopsE;
00314   if (Loop *Parent = L->getParentLoop()) {
00315     ParentLoops = Parent->begin();
00316     ParentLoopsE = Parent->end();
00317   } else {      // Must check top-level loops...
00318     ParentLoops = getAnalysis<LoopInfo>().begin();
00319     ParentLoopsE = getAnalysis<LoopInfo>().end();
00320   }
00321 
00322   DominatorSet &DS = getAnalysis<DominatorSet>();  // Update dominator info
00323   DominatorTree &DT = getAnalysis<DominatorTree>();
00324     
00325 
00326   // Update the dominator tree information.
00327   // The immediate dominator of the preheader is the immediate dominator of
00328   // the old header.
00329   DominatorTree::Node *PHDomTreeNode =
00330     DT.createNewNode(NewBB, DT.getNode(Header)->getIDom());
00331 
00332   // Change the header node so that PNHode is the new immediate dominator
00333   DT.changeImmediateDominator(DT.getNode(Header), PHDomTreeNode);
00334 
00335   {
00336     // The blocks that dominate NewBB are the blocks that dominate Header,
00337     // minus Header, plus NewBB.
00338     DominatorSet::DomSetType DomSet = DS.getDominators(Header);
00339     DomSet.erase(Header);  // Header does not dominate us...
00340     DS.addBasicBlock(NewBB, DomSet);
00341 
00342     // The newly created basic block dominates all nodes dominated by Header.
00343     for (df_iterator<DominatorTree::Node*> DFI = df_begin(PHDomTreeNode),
00344            E = df_end(PHDomTreeNode); DFI != E; ++DFI)
00345       DS.addDominator((*DFI)->getBlock(), NewBB);
00346   }
00347   
00348   // Update immediate dominator information if we have it...
00349   if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) {
00350     // Whatever i-dominated the header node now immediately dominates NewBB
00351     ID->addNewBlock(NewBB, ID->get(Header));
00352     
00353     // The preheader now is the immediate dominator for the header node...
00354     ID->setImmediateDominator(Header, NewBB);
00355   }
00356   
00357   // Update dominance frontier information...
00358   if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) {
00359     // The DF(NewBB) is just (DF(Header)-Header), because NewBB dominates
00360     // everything that Header does, and it strictly dominates Header in
00361     // addition.
00362     assert(DF->find(Header) != DF->end() && "Header node doesn't have DF set?");
00363     DominanceFrontier::DomSetType NewDFSet = DF->find(Header)->second;
00364     NewDFSet.erase(Header);
00365     DF->addBasicBlock(NewBB, NewDFSet);
00366 
00367     // Now we must loop over all of the dominance frontiers in the function,
00368     // replacing occurrences of Header with NewBB in some cases.  If a block
00369     // dominates a (now) predecessor of NewBB, but did not strictly dominate
00370     // Header, it will have Header in it's DF set, but should now have NewBB in
00371     // its set.
00372     for (unsigned i = 0, e = OutsideBlocks.size(); i != e; ++i) {
00373       // Get all of the dominators of the predecessor...
00374       const DominatorSet::DomSetType &PredDoms =
00375         DS.getDominators(OutsideBlocks[i]);
00376       for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(),
00377              PDE = PredDoms.end(); PDI != PDE; ++PDI) {
00378         BasicBlock *PredDom = *PDI;
00379         // If the loop header is in DF(PredDom), then PredDom didn't dominate
00380         // the header but did dominate a predecessor outside of the loop.  Now
00381         // we change this entry to include the preheader in the DF instead of
00382         // the header.
00383         DominanceFrontier::iterator DFI = DF->find(PredDom);
00384         assert(DFI != DF->end() && "No dominance frontier for node?");
00385         if (DFI->second.count(Header)) {
00386           DF->removeFromFrontier(DFI, Header);
00387           DF->addToFrontier(DFI, NewBB);
00388         }
00389       }
00390     }
00391   }
00392 }
00393 
00394 /// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit
00395 /// blocks.  This method is used to split exit blocks that have predecessors
00396 /// outside of the loop.
00397 BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) {
00398   DominatorSet &DS = getAnalysis<DominatorSet>();
00399   
00400   std::vector<BasicBlock*> LoopBlocks;
00401   for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I)
00402     if (L->contains(*I))
00403       LoopBlocks.push_back(*I);
00404 
00405   assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?");
00406   BasicBlock *NewBB = SplitBlockPredecessors(Exit, ".loopexit", LoopBlocks);
00407 
00408   // Update Loop Information - we know that the new block will be in the parent
00409   // loop of L.
00410   if (Loop *Parent = L->getParentLoop())
00411     Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>());
00412 
00413   // Update dominator information (set, immdom, domtree, and domfrontier)
00414   UpdateDomInfoForRevectoredPreds(NewBB, LoopBlocks);
00415   return NewBB;
00416 }
00417 
00418 /// AddBlockAndPredsToSet - Add the specified block, and all of its
00419 /// predecessors, to the specified set, if it's not already in there.  Stop
00420 /// predecessor traversal when we reach StopBlock.
00421 static void AddBlockAndPredsToSet(BasicBlock *BB, BasicBlock *StopBlock,
00422                                   std::set<BasicBlock*> &Blocks) {
00423   if (!Blocks.insert(BB).second) return;  // already processed.
00424   if (BB == StopBlock) return;  // Stop here!
00425 
00426   for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I)
00427     AddBlockAndPredsToSet(*I, StopBlock, Blocks);
00428 }
00429 
00430 /// FindPHIToPartitionLoops - The first part of loop-nestification is to find a
00431 /// PHI node that tells us how to partition the loops.
00432 static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorSet &DS) {
00433   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
00434     PHINode *PN = cast<PHINode>(I);
00435     ++I;
00436     if (Value *V = hasConstantValue(PN))
00437       if (!isa<Instruction>(V) || DS.dominates(cast<Instruction>(V), PN)) {
00438         // This is a degenerate PHI already, don't modify it!
00439         PN->replaceAllUsesWith(V);
00440         PN->getParent()->getInstList().erase(PN);
00441         continue;
00442       }
00443 
00444     // Scan this PHI node looking for a use of the PHI node by itself.
00445     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00446       if (PN->getIncomingValue(i) == PN &&
00447           L->contains(PN->getIncomingBlock(i)))
00448         // We found something tasty to remove.
00449         return PN;
00450   }
00451   return 0;
00452 }
00453 
00454 /// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of
00455 /// them out into a nested loop.  This is important for code that looks like
00456 /// this:
00457 ///
00458 ///  Loop:
00459 ///     ...
00460 ///     br cond, Loop, Next
00461 ///     ...
00462 ///     br cond2, Loop, Out
00463 ///
00464 /// To identify this common case, we look at the PHI nodes in the header of the
00465 /// loop.  PHI nodes with unchanging values on one backedge correspond to values
00466 /// that change in the "outer" loop, but not in the "inner" loop.
00467 ///
00468 /// If we are able to separate out a loop, return the new outer loop that was
00469 /// created.
00470 ///
00471 Loop *LoopSimplify::SeparateNestedLoop(Loop *L) {
00472   PHINode *PN = FindPHIToPartitionLoops(L, getAnalysis<DominatorSet>());
00473   if (PN == 0) return 0;  // No known way to partition.
00474 
00475   // Pull out all predecessors that have varying values in the loop.  This
00476   // handles the case when a PHI node has multiple instances of itself as
00477   // arguments.
00478   std::vector<BasicBlock*> OuterLoopPreds;
00479   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00480     if (PN->getIncomingValue(i) != PN ||
00481         !L->contains(PN->getIncomingBlock(i)))
00482       OuterLoopPreds.push_back(PN->getIncomingBlock(i));
00483 
00484   BasicBlock *Header = L->getHeader();
00485   BasicBlock *NewBB = SplitBlockPredecessors(Header, ".outer", OuterLoopPreds);
00486 
00487   // Update dominator information (set, immdom, domtree, and domfrontier)
00488   UpdateDomInfoForRevectoredPreds(NewBB, OuterLoopPreds);
00489 
00490   // Create the new outer loop.
00491   Loop *NewOuter = new Loop();
00492 
00493   LoopInfo &LI = getAnalysis<LoopInfo>();
00494 
00495   // Change the parent loop to use the outer loop as its child now.
00496   if (Loop *Parent = L->getParentLoop())
00497     Parent->replaceChildLoopWith(L, NewOuter);
00498   else
00499     LI.changeTopLevelLoop(L, NewOuter);
00500 
00501   // This block is going to be our new header block: add it to this loop and all
00502   // parent loops.
00503   NewOuter->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>());
00504 
00505   // L is now a subloop of our outer loop.
00506   NewOuter->addChildLoop(L);
00507 
00508   for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i)
00509     NewOuter->addBlockEntry(L->getBlocks()[i]);
00510 
00511   // Determine which blocks should stay in L and which should be moved out to
00512   // the Outer loop now.
00513   DominatorSet &DS = getAnalysis<DominatorSet>();
00514   std::set<BasicBlock*> BlocksInL;
00515   for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI)
00516     if (DS.dominates(Header, *PI))
00517       AddBlockAndPredsToSet(*PI, Header, BlocksInL);
00518 
00519 
00520   // Scan all of the loop children of L, moving them to OuterLoop if they are
00521   // not part of the inner loop.
00522   for (Loop::iterator I = L->begin(); I != L->end(); )
00523     if (BlocksInL.count((*I)->getHeader()))
00524       ++I;   // Loop remains in L
00525     else
00526       NewOuter->addChildLoop(L->removeChildLoop(I));
00527 
00528   // Now that we know which blocks are in L and which need to be moved to
00529   // OuterLoop, move any blocks that need it.
00530   for (unsigned i = 0; i != L->getBlocks().size(); ++i) {
00531     BasicBlock *BB = L->getBlocks()[i];
00532     if (!BlocksInL.count(BB)) {
00533       // Move this block to the parent, updating the exit blocks sets
00534       L->removeBlockFromLoop(BB);
00535       if (LI[BB] == L)
00536         LI.changeLoopFor(BB, NewOuter);
00537       --i;
00538     }
00539   }
00540 
00541   return NewOuter;
00542 }
00543 
00544 
00545 
00546 /// InsertUniqueBackedgeBlock - This method is called when the specified loop
00547 /// has more than one backedge in it.  If this occurs, revector all of these
00548 /// backedges to target a new basic block and have that block branch to the loop
00549 /// header.  This ensures that loops have exactly one backedge.
00550 ///
00551 void LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) {
00552   assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!");
00553 
00554   // Get information about the loop
00555   BasicBlock *Preheader = L->getLoopPreheader();
00556   BasicBlock *Header = L->getHeader();
00557   Function *F = Header->getParent();
00558 
00559   // Figure out which basic blocks contain back-edges to the loop header.
00560   std::vector<BasicBlock*> BackedgeBlocks;
00561   for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I)
00562     if (*I != Preheader) BackedgeBlocks.push_back(*I);
00563 
00564   // Create and insert the new backedge block...
00565   BasicBlock *BEBlock = new BasicBlock(Header->getName()+".backedge", F);
00566   BranchInst *BETerminator = new BranchInst(Header, BEBlock);
00567 
00568   // Move the new backedge block to right after the last backedge block.
00569   Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos;
00570   F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock);
00571   
00572   // Now that the block has been inserted into the function, create PHI nodes in
00573   // the backedge block which correspond to any PHI nodes in the header block.
00574   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
00575     PHINode *PN = cast<PHINode>(I);
00576     PHINode *NewPN = new PHINode(PN->getType(), PN->getName()+".be",
00577                                  BETerminator);
00578     NewPN->op_reserve(2*BackedgeBlocks.size());
00579 
00580     // Loop over the PHI node, moving all entries except the one for the
00581     // preheader over to the new PHI node.
00582     unsigned PreheaderIdx = ~0U;
00583     bool HasUniqueIncomingValue = true;
00584     Value *UniqueValue = 0;
00585     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00586       BasicBlock *IBB = PN->getIncomingBlock(i);
00587       Value *IV = PN->getIncomingValue(i);
00588       if (IBB == Preheader) {
00589         PreheaderIdx = i;
00590       } else {
00591         NewPN->addIncoming(IV, IBB);
00592         if (HasUniqueIncomingValue) {
00593           if (UniqueValue == 0)
00594             UniqueValue = IV;
00595           else if (UniqueValue != IV)
00596             HasUniqueIncomingValue = false;
00597         }
00598       }
00599     }
00600       
00601     // Delete all of the incoming values from the old PN except the preheader's
00602     assert(PreheaderIdx != ~0U && "PHI has no preheader entry??");
00603     if (PreheaderIdx != 0) {
00604       PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx));
00605       PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx));
00606     }
00607     PN->op_erase(PN->op_begin()+2, PN->op_end());
00608 
00609     // Finally, add the newly constructed PHI node as the entry for the BEBlock.
00610     PN->addIncoming(NewPN, BEBlock);
00611 
00612     // As an optimization, if all incoming values in the new PhiNode (which is a
00613     // subset of the incoming values of the old PHI node) have the same value,
00614     // eliminate the PHI Node.
00615     if (HasUniqueIncomingValue) {
00616       NewPN->replaceAllUsesWith(UniqueValue);
00617       BEBlock->getInstList().erase(NewPN);
00618     }
00619   }
00620 
00621   // Now that all of the PHI nodes have been inserted and adjusted, modify the
00622   // backedge blocks to just to the BEBlock instead of the header.
00623   for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) {
00624     TerminatorInst *TI = BackedgeBlocks[i]->getTerminator();
00625     for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op)
00626       if (TI->getSuccessor(Op) == Header)
00627         TI->setSuccessor(Op, BEBlock);
00628   }
00629 
00630   //===--- Update all analyses which we must preserve now -----------------===//
00631 
00632   // Update Loop Information - we know that this block is now in the current
00633   // loop and all parent loops.
00634   L->addBasicBlockToLoop(BEBlock, getAnalysis<LoopInfo>());
00635 
00636   // Update dominator information (set, immdom, domtree, and domfrontier)
00637   UpdateDomInfoForRevectoredPreds(BEBlock, BackedgeBlocks);
00638 }
00639 
00640 /// UpdateDomInfoForRevectoredPreds - This method is used to update the four
00641 /// different kinds of dominator information (dominator sets, immediate
00642 /// dominators, dominator trees, and dominance frontiers) after a new block has
00643 /// been added to the CFG.
00644 ///
00645 /// This only supports the case when an existing block (known as "NewBBSucc"),
00646 /// had some of its predecessors factored into a new basic block.  This
00647 /// transformation inserts a new basic block ("NewBB"), with a single
00648 /// unconditional branch to NewBBSucc, and moves some predecessors of
00649 /// "NewBBSucc" to now branch to NewBB.  These predecessors are listed in
00650 /// PredBlocks, even though they are the same as
00651 /// pred_begin(NewBB)/pred_end(NewBB).
00652 ///
00653 void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB,
00654                                          std::vector<BasicBlock*> &PredBlocks) {
00655   assert(!PredBlocks.empty() && "No predblocks??");
00656   assert(succ_begin(NewBB) != succ_end(NewBB) &&
00657          ++succ_begin(NewBB) == succ_end(NewBB) &&
00658          "NewBB should have a single successor!");
00659   BasicBlock *NewBBSucc = *succ_begin(NewBB);
00660   DominatorSet &DS = getAnalysis<DominatorSet>();
00661 
00662   // Update dominator information...  The blocks that dominate NewBB are the
00663   // intersection of the dominators of predecessors, plus the block itself.
00664   //
00665   DominatorSet::DomSetType NewBBDomSet = DS.getDominators(PredBlocks[0]);
00666   for (unsigned i = 1, e = PredBlocks.size(); i != e; ++i)
00667     set_intersect(NewBBDomSet, DS.getDominators(PredBlocks[i]));
00668   NewBBDomSet.insert(NewBB);  // All blocks dominate themselves...
00669   DS.addBasicBlock(NewBB, NewBBDomSet);
00670 
00671   // The newly inserted basic block will dominate existing basic blocks iff the
00672   // PredBlocks dominate all of the non-pred blocks.  If all predblocks dominate
00673   // the non-pred blocks, then they all must be the same block!
00674   //
00675   bool NewBBDominatesNewBBSucc = true;
00676   {
00677     BasicBlock *OnePred = PredBlocks[0];
00678     for (unsigned i = 1, e = PredBlocks.size(); i != e; ++i)
00679       if (PredBlocks[i] != OnePred) {
00680         NewBBDominatesNewBBSucc = false;
00681         break;
00682       }
00683 
00684     if (NewBBDominatesNewBBSucc)
00685       for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc);
00686            PI != E; ++PI)
00687         if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) {
00688           NewBBDominatesNewBBSucc = false;
00689           break;
00690         }
00691   }
00692 
00693   // The other scenario where the new block can dominate its successors are when
00694   // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc
00695   // already.
00696   if (!NewBBDominatesNewBBSucc) {
00697     NewBBDominatesNewBBSucc = true;
00698     for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc);
00699          PI != E; ++PI)
00700       if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) {
00701         NewBBDominatesNewBBSucc = false;
00702         break;
00703       }
00704   }
00705 
00706   // If NewBB dominates some blocks, then it will dominate all blocks that
00707   // NewBBSucc does.
00708   if (NewBBDominatesNewBBSucc) {
00709     BasicBlock *PredBlock = PredBlocks[0];
00710     Function *F = NewBB->getParent();
00711     for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
00712       if (DS.dominates(NewBBSucc, I))
00713         DS.addDominator(I, NewBB);
00714   }
00715 
00716   // Update immediate dominator information if we have it...
00717   BasicBlock *NewBBIDom = 0;
00718   if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) {
00719     // To find the immediate dominator of the new exit node, we trace up the
00720     // immediate dominators of a predecessor until we find a basic block that
00721     // dominates the exit block.
00722     //
00723     BasicBlock *Dom = PredBlocks[0];  // Some random predecessor...
00724     while (!NewBBDomSet.count(Dom)) {  // Loop until we find a dominator...
00725       assert(Dom != 0 && "No shared dominator found???");
00726       Dom = ID->get(Dom);
00727     }
00728 
00729     // Set the immediate dominator now...
00730     ID->addNewBlock(NewBB, Dom);
00731     NewBBIDom = Dom;   // Reuse this if calculating DominatorTree info...
00732 
00733     // If NewBB strictly dominates other blocks, we need to update their idom's
00734     // now.  The only block that need adjustment is the NewBBSucc block, whose
00735     // idom should currently be set to PredBlocks[0].
00736     if (NewBBDominatesNewBBSucc)
00737       ID->setImmediateDominator(NewBBSucc, NewBB);
00738   }
00739 
00740   // Update DominatorTree information if it is active.
00741   if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) {
00742     // If we don't have ImmediateDominator info around, calculate the idom as
00743     // above.
00744     DominatorTree::Node *NewBBIDomNode;
00745     if (NewBBIDom) {
00746       NewBBIDomNode = DT->getNode(NewBBIDom);
00747     } else {
00748       NewBBIDomNode = DT->getNode(PredBlocks[0]); // Random pred
00749       while (!NewBBDomSet.count(NewBBIDomNode->getBlock())) {
00750         NewBBIDomNode = NewBBIDomNode->getIDom();
00751         assert(NewBBIDomNode && "No shared dominator found??");
00752       }
00753     }
00754 
00755     // Create the new dominator tree node... and set the idom of NewBB.
00756     DominatorTree::Node *NewBBNode = DT->createNewNode(NewBB, NewBBIDomNode);
00757 
00758     // If NewBB strictly dominates other blocks, then it is now the immediate
00759     // dominator of NewBBSucc.  Update the dominator tree as appropriate.
00760     if (NewBBDominatesNewBBSucc) {
00761       DominatorTree::Node *NewBBSuccNode = DT->getNode(NewBBSucc);
00762       DT->changeImmediateDominator(NewBBSuccNode, NewBBNode);
00763     }
00764   }
00765 
00766   // Update dominance frontier information...
00767   if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) {
00768     // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the
00769     // DF(PredBlocks[0]) without the stuff that the new block does not dominate
00770     // a predecessor of.
00771     if (NewBBDominatesNewBBSucc) {
00772       DominanceFrontier::iterator DFI = DF->find(PredBlocks[0]);
00773       if (DFI != DF->end()) {
00774         DominanceFrontier::DomSetType Set = DFI->second;
00775         // Filter out stuff in Set that we do not dominate a predecessor of.
00776         for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
00777                E = Set.end(); SetI != E;) {
00778           bool DominatesPred = false;
00779           for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI);
00780                PI != E; ++PI)
00781             if (DS.dominates(NewBB, *PI))
00782               DominatesPred = true;
00783           if (!DominatesPred)
00784             Set.erase(SetI++);
00785           else
00786             ++SetI;
00787         }
00788 
00789         DF->addBasicBlock(NewBB, Set);
00790       }
00791 
00792     } else {
00793       // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate
00794       // NewBBSucc, but it does dominate itself (and there is an edge (NewBB ->
00795       // NewBBSucc)).  NewBBSucc is the single successor of NewBB.
00796       DominanceFrontier::DomSetType NewDFSet;
00797       NewDFSet.insert(NewBBSucc);
00798       DF->addBasicBlock(NewBB, NewDFSet);
00799     }
00800 
00801     // Now we must loop over all of the dominance frontiers in the function,
00802     // replacing occurrences of NewBBSucc with NewBB in some cases.  All
00803     // blocks that dominate a block in PredBlocks and contained NewBBSucc in
00804     // their dominance frontier must be updated to contain NewBB instead.
00805     //
00806     for (unsigned i = 0, e = PredBlocks.size(); i != e; ++i) {
00807       BasicBlock *Pred = PredBlocks[i];
00808       // Get all of the dominators of the predecessor...
00809       const DominatorSet::DomSetType &PredDoms = DS.getDominators(Pred);
00810       for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(),
00811              PDE = PredDoms.end(); PDI != PDE; ++PDI) {
00812         BasicBlock *PredDom = *PDI;
00813         
00814         // If the NewBBSucc node is in DF(PredDom), then PredDom didn't
00815         // dominate NewBBSucc but did dominate a predecessor of it.  Now we
00816         // change this entry to include NewBB in the DF instead of NewBBSucc.
00817         DominanceFrontier::iterator DFI = DF->find(PredDom);
00818         assert(DFI != DF->end() && "No dominance frontier for node?");
00819         if (DFI->second.count(NewBBSucc)) {
00820           // If NewBBSucc should not stay in our dominator frontier, remove it.
00821           // We remove it unless there is a predecessor of NewBBSucc that we
00822           // dominate, but we don't strictly dominate NewBBSucc.
00823           bool ShouldRemove = true;
00824           if (PredDom == NewBBSucc || !DS.dominates(PredDom, NewBBSucc)) {
00825             // Okay, we know that PredDom does not strictly dominate NewBBSucc.
00826             // Check to see if it dominates any predecessors of NewBBSucc.
00827             for (pred_iterator PI = pred_begin(NewBBSucc),
00828                    E = pred_end(NewBBSucc); PI != E; ++PI)
00829               if (DS.dominates(PredDom, *PI)) {
00830                 ShouldRemove = false;
00831                 break;
00832               }
00833           }
00834             
00835           if (ShouldRemove)
00836             DF->removeFromFrontier(DFI, NewBBSucc);
00837           DF->addToFrontier(DFI, NewBB);
00838         }
00839       }
00840     }
00841   }
00842 }
00843