LLVM API Documentation

LoopRotation.cpp

Go to the documentation of this file.
00001 //===- LoopRotation.cpp - Loop Rotation 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 file implements Loop Rotation Pass.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #define DEBUG_TYPE "loop-rotate"
00015 #include "llvm/Transforms/Scalar.h"
00016 #include "llvm/Function.h"
00017 #include "llvm/IntrinsicInst.h"
00018 #include "llvm/Analysis/LoopInfo.h"
00019 #include "llvm/Analysis/LoopPass.h"
00020 #include "llvm/Analysis/Dominators.h"
00021 #include "llvm/Analysis/ScalarEvolution.h"
00022 #include "llvm/Transforms/Utils/Local.h"
00023 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00024 #include "llvm/Support/CommandLine.h"
00025 #include "llvm/Support/Debug.h"
00026 #include "llvm/ADT/Statistic.h"
00027 #include "llvm/ADT/SmallVector.h"
00028 using namespace llvm;
00029 
00030 #define MAX_HEADER_SIZE 16
00031 
00032 STATISTIC(NumRotated, "Number of loops rotated");
00033 namespace {
00034 
00035   class VISIBILITY_HIDDEN RenameData {
00036   public:
00037     RenameData(Instruction *O, Value *P, Instruction *H) 
00038       : Original(O), PreHeader(P), Header(H) { }
00039   public:
00040     Instruction *Original; // Original instruction
00041     Value *PreHeader; // Original pre-header replacement
00042     Instruction *Header; // New header replacement
00043   };
00044   
00045   class VISIBILITY_HIDDEN LoopRotate : public LoopPass {
00046 
00047   public:
00048     static char ID; // Pass ID, replacement for typeid
00049     LoopRotate() : LoopPass(&ID) {}
00050 
00051     // Rotate Loop L as many times as possible. Return true if
00052     // loop is rotated at least once.
00053     bool runOnLoop(Loop *L, LPPassManager &LPM);
00054 
00055     // LCSSA form makes instruction renaming easier.
00056     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00057       AU.addRequiredID(LoopSimplifyID);
00058       AU.addPreservedID(LoopSimplifyID);
00059       AU.addRequiredID(LCSSAID);
00060       AU.addPreservedID(LCSSAID);
00061       AU.addPreserved<ScalarEvolution>();
00062       AU.addPreserved<LoopInfo>();
00063       AU.addPreserved<DominatorTree>();
00064       AU.addPreserved<DominanceFrontier>();
00065     }
00066 
00067     // Helper functions
00068 
00069     /// Do actual work
00070     bool rotateLoop(Loop *L, LPPassManager &LPM);
00071     
00072     /// Initialize local data
00073     void initialize();
00074 
00075     /// Make sure all Exit block PHINodes have required incoming values.
00076     /// If incoming value is constant or defined outside the loop then
00077     /// PHINode may not have an entry for original pre-header. 
00078     void  updateExitBlock();
00079 
00080     /// Return true if this instruction is used outside original header.
00081     bool usedOutsideOriginalHeader(Instruction *In);
00082 
00083     /// Find Replacement information for instruction. Return NULL if it is
00084     /// not available.
00085     const RenameData *findReplacementData(Instruction *I);
00086 
00087     /// After loop rotation, loop pre-header has multiple sucessors.
00088     /// Insert one forwarding basic block to ensure that loop pre-header
00089     /// has only one successor.
00090     void preserveCanonicalLoopForm(LPPassManager &LPM);
00091 
00092   private:
00093 
00094     Loop *L;
00095     BasicBlock *OrigHeader;
00096     BasicBlock *OrigPreHeader;
00097     BasicBlock *OrigLatch;
00098     BasicBlock *NewHeader;
00099     BasicBlock *Exit;
00100     LPPassManager *LPM_Ptr;
00101     SmallVector<RenameData, MAX_HEADER_SIZE> LoopHeaderInfo;
00102   };
00103 }
00104   
00105 char LoopRotate::ID = 0;
00106 static RegisterPass<LoopRotate> X("loop-rotate", "Rotate Loops");
00107 
00108 Pass *llvm::createLoopRotatePass() { return new LoopRotate(); }
00109 
00110 /// Rotate Loop L as many times as possible. Return true if
00111 /// the loop is rotated at least once.
00112 bool LoopRotate::runOnLoop(Loop *Lp, LPPassManager &LPM) {
00113 
00114   bool RotatedOneLoop = false;
00115   initialize();
00116   LPM_Ptr = &LPM;
00117 
00118   // One loop can be rotated multiple times.
00119   while (rotateLoop(Lp,LPM)) {
00120     RotatedOneLoop = true;
00121     initialize();
00122   }
00123 
00124   return RotatedOneLoop;
00125 }
00126 
00127 /// Rotate loop LP. Return true if the loop is rotated.
00128 bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) {
00129   L = Lp;
00130 
00131   OrigHeader =  L->getHeader();
00132   OrigPreHeader = L->getLoopPreheader();
00133   OrigLatch = L->getLoopLatch();
00134 
00135   // If the loop has only one block then there is not much to rotate.
00136   if (L->getBlocks().size() == 1)
00137     return false;
00138 
00139   assert(OrigHeader && OrigLatch && OrigPreHeader &&
00140          "Loop is not in canonical form");
00141 
00142   // If the loop header is not one of the loop exiting blocks then
00143   // either this loop is already rotated or it is not
00144   // suitable for loop rotation transformations.
00145   if (!L->isLoopExit(OrigHeader))
00146     return false;
00147 
00148   BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator());
00149   if (!BI)
00150     return false;
00151   assert(BI->isConditional() && "Branch Instruction is not conditional");
00152 
00153   // Updating PHInodes in loops with multiple exits adds complexity. 
00154   // Keep it simple, and restrict loop rotation to loops with one exit only.
00155   // In future, lift this restriction and support for multiple exits if
00156   // required.
00157   SmallVector<BasicBlock*, 8> ExitBlocks;
00158   L->getExitBlocks(ExitBlocks);
00159   if (ExitBlocks.size() > 1)
00160     return false;
00161 
00162   // Check size of original header and reject
00163   // loop if it is very big.
00164   unsigned Size = 0;
00165   
00166   // FIXME: Use common api to estimate size.
00167   for (BasicBlock::const_iterator OI = OrigHeader->begin(), 
00168          OE = OrigHeader->end(); OI != OE; ++OI) {
00169       if (isa<PHINode>(OI)) 
00170         continue;           // PHI nodes don't count.
00171       if (isa<DbgInfoIntrinsic>(OI))
00172         continue;  // Debug intrinsics don't count as size.
00173       Size++;
00174   }
00175 
00176   if (Size > MAX_HEADER_SIZE)
00177     return false;
00178 
00179   // Now, this loop is suitable for rotation.
00180 
00181   // Find new Loop header. NewHeader is a Header's one and only successor
00182   // that is inside loop.  Header's other successor is outside the
00183   // loop.  Otherwise loop is not suitable for rotation.
00184   Exit = BI->getSuccessor(0);
00185   NewHeader = BI->getSuccessor(1);
00186   if (L->contains(Exit))
00187     std::swap(Exit, NewHeader);
00188   assert(NewHeader && "Unable to determine new loop header");
00189   assert(L->contains(NewHeader) && !L->contains(Exit) && 
00190          "Unable to determine loop header and exit blocks");
00191   
00192   // This code assumes that the new header has exactly one predecessor.
00193   // Remove any single-entry PHI nodes in it.
00194   assert(NewHeader->getSinglePredecessor() &&
00195          "New header doesn't have one pred!");
00196   FoldSingleEntryPHINodes(NewHeader);
00197 
00198   // Copy PHI nodes and other instructions from the original header
00199   // into the original pre-header. Unlike the original header, the original
00200   // pre-header is not a member of the loop.
00201   //
00202   // The new loop header is the one and only successor of original header that
00203   // is inside the loop. All other original header successors are outside 
00204   // the loop. Copy PHI Nodes from the original header into the new loop header.
00205   // Add second incoming value, from original loop pre-header into these phi 
00206   // nodes. If a value defined in original header is used outside original 
00207   // header then new loop header will need new phi nodes with two incoming 
00208   // values, one definition from original header and second definition is 
00209   // from original loop pre-header.
00210 
00211   // Remove terminator from Original pre-header. Original pre-header will
00212   // receive a clone of original header terminator as a new terminator.
00213   OrigPreHeader->getInstList().pop_back();
00214   BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end();
00215   PHINode *PN = 0;
00216   for (; (PN = dyn_cast<PHINode>(I)); ++I) {
00217     // PHI nodes are not copied into original pre-header. Instead their values
00218     // are directly propagated.
00219     Value *NPV = PN->getIncomingValueForBlock(OrigPreHeader);
00220 
00221     // Create a new PHI node with two incoming values for NewHeader.
00222     // One incoming value is from OrigLatch (through OrigHeader) and the
00223     // second incoming value is from original pre-header.
00224     PHINode *NH = PHINode::Create(PN->getType(), PN->getName(),
00225                                   NewHeader->begin());
00226     NH->addIncoming(PN->getIncomingValueForBlock(OrigLatch), OrigHeader);
00227     NH->addIncoming(NPV, OrigPreHeader);
00228     
00229     // "In" can be replaced by NH at various places.
00230     LoopHeaderInfo.push_back(RenameData(PN, NPV, NH));
00231   }
00232 
00233   // Now, handle non-phi instructions.
00234   for (; I != E; ++I) {
00235     Instruction *In = I;
00236     assert(!isa<PHINode>(In) && "PHINode is not expected here");
00237     
00238     // This is not a PHI instruction. Insert its clone into original pre-header.
00239     // If this instruction is using a value from same basic block then
00240     // update it to use value from cloned instruction.
00241     Instruction *C = In->clone(In->getContext());
00242     C->setName(In->getName());
00243     OrigPreHeader->getInstList().push_back(C);
00244 
00245     for (unsigned opi = 0, e = In->getNumOperands(); opi != e; ++opi) {
00246       Instruction *OpInsn = dyn_cast<Instruction>(In->getOperand(opi));
00247       if (!OpInsn) continue;  // Ignore non-instruction values.
00248       if (const RenameData *D = findReplacementData(OpInsn))
00249         C->setOperand(opi, D->PreHeader);
00250     }
00251 
00252     // If this instruction is used outside this basic block then
00253     // create new PHINode for this instruction.
00254     Instruction *NewHeaderReplacement = NULL;
00255     if (usedOutsideOriginalHeader(In)) {
00256       PHINode *PN = PHINode::Create(In->getType(), In->getName(),
00257                                     NewHeader->begin());
00258       PN->addIncoming(In, OrigHeader);
00259       PN->addIncoming(C, OrigPreHeader);
00260       NewHeaderReplacement = PN;
00261     }
00262     LoopHeaderInfo.push_back(RenameData(In, C, NewHeaderReplacement));
00263   }
00264 
00265   // Rename uses of original header instructions to reflect their new
00266   // definitions (either from original pre-header node or from newly created
00267   // new header PHINodes.
00268   //
00269   // Original header instructions are used in
00270   // 1) Original header:
00271   //
00272   //    If instruction is used in non-phi instructions then it is using
00273   //    defintion from original heder iteself. Do not replace this use
00274   //    with definition from new header or original pre-header.
00275   //
00276   //    If instruction is used in phi node then it is an incoming 
00277   //    value. Rename its use to reflect new definition from new-preheader
00278   //    or new header.
00279   //
00280   // 2) Inside loop but not in original header
00281   //
00282   //    Replace this use to reflect definition from new header.
00283   for (unsigned LHI = 0, LHI_E = LoopHeaderInfo.size(); LHI != LHI_E; ++LHI) {
00284     const RenameData &ILoopHeaderInfo = LoopHeaderInfo[LHI];
00285 
00286     if (!ILoopHeaderInfo.Header)
00287       continue;
00288 
00289     Instruction *OldPhi = ILoopHeaderInfo.Original;
00290     Instruction *NewPhi = ILoopHeaderInfo.Header;
00291 
00292     // Before replacing uses, collect them first, so that iterator is
00293     // not invalidated.
00294     SmallVector<Instruction *, 16> AllUses;
00295     for (Value::use_iterator UI = OldPhi->use_begin(), UE = OldPhi->use_end();
00296          UI != UE; ++UI)
00297       AllUses.push_back(cast<Instruction>(UI));
00298 
00299     for (SmallVector<Instruction *, 16>::iterator UI = AllUses.begin(), 
00300            UE = AllUses.end(); UI != UE; ++UI) {
00301       Instruction *U = *UI;
00302       BasicBlock *Parent = U->getParent();
00303 
00304       // Used inside original header
00305       if (Parent == OrigHeader) {
00306         // Do not rename uses inside original header non-phi instructions.
00307         PHINode *PU = dyn_cast<PHINode>(U);
00308         if (!PU)
00309           continue;
00310 
00311         // Do not rename uses inside original header phi nodes, if the
00312         // incoming value is for new header.
00313         if (PU->getBasicBlockIndex(NewHeader) != -1
00314             && PU->getIncomingValueForBlock(NewHeader) == U)
00315           continue;
00316         
00317        U->replaceUsesOfWith(OldPhi, NewPhi);
00318        continue;
00319       }
00320 
00321       // Used inside loop, but not in original header.
00322       if (L->contains(U->getParent())) {
00323         if (U != NewPhi)
00324           U->replaceUsesOfWith(OldPhi, NewPhi);
00325         continue;
00326       }
00327       
00328       // Used inside Exit Block. Since we are in LCSSA form, U must be PHINode.
00329       if (U->getParent() == Exit) {
00330         assert(isa<PHINode>(U) && "Use in Exit Block that is not PHINode");
00331         
00332         PHINode *UPhi = cast<PHINode>(U);
00333         // UPhi already has one incoming argument from original header. 
00334         // Add second incoming argument from new Pre header.
00335         UPhi->addIncoming(ILoopHeaderInfo.PreHeader, OrigPreHeader);
00336       } else {
00337         // Used outside Exit block. Create a new PHI node in the exit block
00338         // to receive the value from the new header and pre-header.
00339         PHINode *PN = PHINode::Create(U->getType(), U->getName(),
00340                                       Exit->begin());
00341         PN->addIncoming(ILoopHeaderInfo.PreHeader, OrigPreHeader);
00342         PN->addIncoming(OldPhi, OrigHeader);
00343         U->replaceUsesOfWith(OldPhi, PN);
00344       }
00345     }
00346   }
00347   
00348   /// Make sure all Exit block PHINodes have required incoming values.
00349   updateExitBlock();
00350 
00351   // Update CFG
00352 
00353   // Removing incoming branch from loop preheader to original header.
00354   // Now original header is inside the loop.
00355   for (BasicBlock::iterator I = OrigHeader->begin();
00356        (PN = dyn_cast<PHINode>(I)); ++I)
00357     PN->removeIncomingValue(OrigPreHeader);
00358 
00359   // Make NewHeader as the new header for the loop.
00360   L->moveToHeader(NewHeader);
00361 
00362   preserveCanonicalLoopForm(LPM);
00363 
00364   NumRotated++;
00365   return true;
00366 }
00367 
00368 /// Make sure all Exit block PHINodes have required incoming values.
00369 /// If an incoming value is constant or defined outside the loop then
00370 /// PHINode may not have an entry for the original pre-header.
00371 void LoopRotate::updateExitBlock() {
00372 
00373   PHINode *PN;
00374   for (BasicBlock::iterator I = Exit->begin();
00375        (PN = dyn_cast<PHINode>(I)); ++I) {
00376 
00377     // There is already one incoming value from original pre-header block.
00378     if (PN->getBasicBlockIndex(OrigPreHeader) != -1)
00379       continue;
00380 
00381     const RenameData *ILoopHeaderInfo;
00382     Value *V = PN->getIncomingValueForBlock(OrigHeader);
00383     if (isa<Instruction>(V) &&
00384         (ILoopHeaderInfo = findReplacementData(cast<Instruction>(V)))) {
00385       assert(ILoopHeaderInfo->PreHeader && "Missing New Preheader Instruction");
00386       PN->addIncoming(ILoopHeaderInfo->PreHeader, OrigPreHeader);
00387     } else {
00388       PN->addIncoming(V, OrigPreHeader);
00389     }
00390   }
00391 }
00392 
00393 /// Initialize local data
00394 void LoopRotate::initialize() {
00395   L = NULL;
00396   OrigHeader = NULL;
00397   OrigPreHeader = NULL;
00398   NewHeader = NULL;
00399   Exit = NULL;
00400 
00401   LoopHeaderInfo.clear();
00402 }
00403 
00404 /// Return true if this instruction is used by any instructions in the loop that
00405 /// aren't in original header.
00406 bool LoopRotate::usedOutsideOriginalHeader(Instruction *In) {
00407   for (Value::use_iterator UI = In->use_begin(), UE = In->use_end();
00408        UI != UE; ++UI) {
00409     BasicBlock *UserBB = cast<Instruction>(UI)->getParent();
00410     if (UserBB != OrigHeader && L->contains(UserBB))
00411       return true;
00412   }
00413 
00414   return false;
00415 }
00416 
00417 /// Find Replacement information for instruction. Return NULL if it is
00418 /// not available.
00419 const RenameData *LoopRotate::findReplacementData(Instruction *In) {
00420 
00421   // Since LoopHeaderInfo is small, linear walk is OK.
00422   for (unsigned LHI = 0, LHI_E = LoopHeaderInfo.size(); LHI != LHI_E; ++LHI) {
00423     const RenameData &ILoopHeaderInfo = LoopHeaderInfo[LHI];
00424     if (ILoopHeaderInfo.Original == In)
00425       return &ILoopHeaderInfo;
00426   }
00427   return NULL;
00428 }
00429 
00430 /// After loop rotation, loop pre-header has multiple sucessors.
00431 /// Insert one forwarding basic block to ensure that loop pre-header
00432 /// has only one successor.
00433 void LoopRotate::preserveCanonicalLoopForm(LPPassManager &LPM) {
00434 
00435   // Right now original pre-header has two successors, new header and
00436   // exit block. Insert new block between original pre-header and
00437   // new header such that loop's new pre-header has only one successor.
00438   BasicBlock *NewPreHeader = BasicBlock::Create(OrigHeader->getContext(),
00439                                                 "bb.nph",
00440                                                 OrigHeader->getParent(), 
00441                                                 NewHeader);
00442   LoopInfo &LI = LPM.getAnalysis<LoopInfo>();
00443   if (Loop *PL = LI.getLoopFor(OrigPreHeader))
00444     PL->addBasicBlockToLoop(NewPreHeader, LI.getBase());
00445   BranchInst::Create(NewHeader, NewPreHeader);
00446   
00447   BranchInst *OrigPH_BI = cast<BranchInst>(OrigPreHeader->getTerminator());
00448   if (OrigPH_BI->getSuccessor(0) == NewHeader)
00449     OrigPH_BI->setSuccessor(0, NewPreHeader);
00450   else {
00451     assert(OrigPH_BI->getSuccessor(1) == NewHeader &&
00452            "Unexpected original pre-header terminator");
00453     OrigPH_BI->setSuccessor(1, NewPreHeader);
00454   }
00455 
00456   PHINode *PN;
00457   for (BasicBlock::iterator I = NewHeader->begin();
00458        (PN = dyn_cast<PHINode>(I)); ++I) {
00459     int index = PN->getBasicBlockIndex(OrigPreHeader);
00460     assert(index != -1 && "Expected incoming value from Original PreHeader");
00461     PN->setIncomingBlock(index, NewPreHeader);
00462     assert(PN->getBasicBlockIndex(OrigPreHeader) == -1 && 
00463            "Expected only one incoming value from Original PreHeader");
00464   }
00465 
00466   if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>()) {
00467     DT->addNewBlock(NewPreHeader, OrigPreHeader);
00468     DT->changeImmediateDominator(L->getHeader(), NewPreHeader);
00469     DT->changeImmediateDominator(Exit, OrigPreHeader);
00470     for (Loop::block_iterator BI = L->block_begin(), BE = L->block_end();
00471          BI != BE; ++BI) {
00472       BasicBlock *B = *BI;
00473       if (L->getHeader() != B) {
00474         DomTreeNode *Node = DT->getNode(B);
00475         if (Node && Node->getBlock() == OrigHeader)
00476           DT->changeImmediateDominator(*BI, L->getHeader());
00477       }
00478     }
00479     DT->changeImmediateDominator(OrigHeader, OrigLatch);
00480   }
00481 
00482   if (DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>()) {
00483     // New Preheader's dominance frontier is Exit block.
00484     DominanceFrontier::DomSetType NewPHSet;
00485     NewPHSet.insert(Exit);
00486     DF->addBasicBlock(NewPreHeader, NewPHSet);
00487 
00488     // New Header's dominance frontier now includes itself and Exit block
00489     DominanceFrontier::iterator HeadI = DF->find(L->getHeader());
00490     if (HeadI != DF->end()) {
00491       DominanceFrontier::DomSetType & HeaderSet = HeadI->second;
00492       HeaderSet.clear();
00493       HeaderSet.insert(L->getHeader());
00494       HeaderSet.insert(Exit);
00495     } else {
00496       DominanceFrontier::DomSetType HeaderSet;
00497       HeaderSet.insert(L->getHeader());
00498       HeaderSet.insert(Exit);
00499       DF->addBasicBlock(L->getHeader(), HeaderSet);
00500     }
00501 
00502     // Original header (new Loop Latch)'s dominance frontier is Exit.
00503     DominanceFrontier::iterator LatchI = DF->find(L->getLoopLatch());
00504     if (LatchI != DF->end()) {
00505       DominanceFrontier::DomSetType &LatchSet = LatchI->second;
00506       LatchSet = LatchI->second;
00507       LatchSet.clear();
00508       LatchSet.insert(Exit);
00509     } else {
00510       DominanceFrontier::DomSetType LatchSet;
00511       LatchSet.insert(Exit);
00512       DF->addBasicBlock(L->getHeader(), LatchSet);
00513     }
00514 
00515     // If a loop block dominates new loop latch then add to its frontiers
00516     // new header and Exit and remove new latch (which is equal to original
00517     // header).
00518     BasicBlock *NewLatch = L->getLoopLatch();
00519 
00520     assert(NewLatch == OrigHeader && "NewLatch is inequal to OrigHeader");
00521 
00522     if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>()) {
00523       for (Loop::block_iterator BI = L->block_begin(), BE = L->block_end();
00524            BI != BE; ++BI) {
00525         BasicBlock *B = *BI;
00526         if (DT->dominates(B, NewLatch)) {
00527           DominanceFrontier::iterator BDFI = DF->find(B);
00528           if (BDFI != DF->end()) {
00529             DominanceFrontier::DomSetType &BSet = BDFI->second;
00530             BSet.erase(NewLatch);
00531             BSet.insert(L->getHeader());
00532             BSet.insert(Exit);
00533           } else {
00534             DominanceFrontier::DomSetType BSet;
00535             BSet.insert(L->getHeader());
00536             BSet.insert(Exit);
00537             DF->addBasicBlock(B, BSet);
00538           }
00539         }
00540       }
00541     }
00542   }
00543 
00544   // Preserve canonical loop form, which means Exit block should
00545   // have only one predecessor.
00546   BasicBlock *NExit = SplitEdge(L->getLoopLatch(), Exit, this);
00547 
00548   // Preserve LCSSA.
00549   for (BasicBlock::iterator I = Exit->begin();
00550        (PN = dyn_cast<PHINode>(I)); ++I) {
00551     unsigned N = PN->getNumIncomingValues();
00552     for (unsigned index = 0; index != N; ++index)
00553       if (PN->getIncomingBlock(index) == NExit) {
00554         PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName(),
00555                                          NExit->begin());
00556         NewPN->addIncoming(PN->getIncomingValue(index), L->getLoopLatch());
00557         PN->setIncomingValue(index, NewPN);
00558         PN->setIncomingBlock(index, NExit);
00559         break;
00560       }
00561   }
00562 
00563   assert(NewHeader && L->getHeader() == NewHeader &&
00564          "Invalid loop header after loop rotation");
00565   assert(NewPreHeader && L->getLoopPreheader() == NewPreHeader &&
00566          "Invalid loop preheader after loop rotation");
00567   assert(L->getLoopLatch() &&
00568          "Invalid loop latch after loop rotation");
00569 }