LoopRotation.cpp revision 6ccb3652933bcdede2b2a53cf76ddd56ce9592a2
1c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel//===- LoopRotation.cpp - Loop Rotation Pass ------------------------------===// 2c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel// 3c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel// The LLVM Compiler Infrastructure 4c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel// 8c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel//===----------------------------------------------------------------------===// 9c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel// 10c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel// This file implements Loop Rotation Pass. 11c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel// 12c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel//===----------------------------------------------------------------------===// 13c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 14322313376a9ccac86cbfc208684d84936d62322dDevang Patel#define DEBUG_TYPE "loop-rotate" 15c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#include "llvm/Transforms/Scalar.h" 16c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#include "llvm/Function.h" 17c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#include "llvm/Analysis/LoopPass.h" 189fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner#include "llvm/Analysis/DominanceFrontier.h" 19d9e079706e782c5f054322a0d15f063a1a683230Chris Lattner#include "llvm/Analysis/CodeMetrics.h" 20990e866deb158fd88377b5606c8d86603e93e533Devang Patel#include "llvm/Analysis/ScalarEvolution.h" 21c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#include "llvm/Transforms/Utils/Local.h" 22990e866deb158fd88377b5606c8d86603e93e533Devang Patel#include "llvm/Transforms/Utils/BasicBlockUtils.h" 23e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman#include "llvm/Transforms/Utils/SSAUpdater.h" 246ccb3652933bcdede2b2a53cf76ddd56ce9592a2Chris Lattner#include "llvm/Transforms/Utils/ValueMapper.h" 25c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#include "llvm/Support/CommandLine.h" 26c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#include "llvm/Support/Debug.h" 27c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#include "llvm/ADT/Statistic.h" 28c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patelusing namespace llvm; 29c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 30c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#define MAX_HEADER_SIZE 16 31c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 32c4625da483ff9e835aef886864e37dd68fb7a03cDevang PatelSTATISTIC(NumRotated, "Number of loops rotated"); 33c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patelnamespace { 34c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 353e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class LoopRotate : public LoopPass { 36c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel public: 371997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; // Pass ID, replacement for typeid 38081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson LoopRotate() : LoopPass(ID) { 39081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLoopRotatePass(*PassRegistry::getPassRegistry()); 40081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 41794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 42322313376a9ccac86cbfc208684d84936d62322dDevang Patel // Rotate Loop L as many times as possible. Return true if 43322313376a9ccac86cbfc208684d84936d62322dDevang Patel // loop is rotated at least once. 44c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel bool runOnLoop(Loop *L, LPPassManager &LPM); 45322313376a9ccac86cbfc208684d84936d62322dDevang Patel 46322313376a9ccac86cbfc208684d84936d62322dDevang Patel // LCSSA form makes instruction renaming easier. 47c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel virtual void getAnalysisUsage(AnalysisUsage &AU) const { 481e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addPreserved<DominatorTree>(); 491e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addPreserved<DominanceFrontier>(); 501e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addRequired<LoopInfo>(); 511e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addPreserved<LoopInfo>(); 529d9b204d6a155f4778a9009c643eed5bf59148e2Devang Patel AU.addRequiredID(LoopSimplifyID); 539d9b204d6a155f4778a9009c643eed5bf59148e2Devang Patel AU.addPreservedID(LoopSimplifyID); 54c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel AU.addRequiredID(LCSSAID); 55c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel AU.addPreservedID(LCSSAID); 56990e866deb158fd88377b5606c8d86603e93e533Devang Patel AU.addPreserved<ScalarEvolution>(); 57c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 58c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 59c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel // Helper functions 60c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 61c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel /// Do actual work 62c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel bool rotateLoop(Loop *L, LPPassManager &LPM); 63c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 64c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel /// Initialize local data 65c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel void initialize(); 66c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 675464b96073626f811d79d56fa37be230552d2264Devang Patel /// After loop rotation, loop pre-header has multiple sucessors. 685464b96073626f811d79d56fa37be230552d2264Devang Patel /// Insert one forwarding basic block to ensure that loop pre-header 695464b96073626f811d79d56fa37be230552d2264Devang Patel /// has only one successor. 705464b96073626f811d79d56fa37be230552d2264Devang Patel void preserveCanonicalLoopForm(LPPassManager &LPM); 715464b96073626f811d79d56fa37be230552d2264Devang Patel 72c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel private: 73c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel Loop *L; 74c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel BasicBlock *OrigHeader; 75c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel BasicBlock *OrigPreHeader; 76c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel BasicBlock *OrigLatch; 77c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel BasicBlock *NewHeader; 78c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel BasicBlock *Exit; 79990e866deb158fd88377b5606c8d86603e93e533Devang Patel LPPassManager *LPM_Ptr; 80c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel }; 81c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel} 82844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 83844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LoopRotate::ID = 0; 842ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(LoopRotate, "loop-rotate", "Rotate Loops", false, false) 852ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopInfo) 862ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopSimplify) 872ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LCSSA) 882ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(LoopRotate, "loop-rotate", "Rotate Loops", false, false) 89c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 90394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass *llvm::createLoopRotatePass() { return new LoopRotate(); } 91c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 92322313376a9ccac86cbfc208684d84936d62322dDevang Patel/// Rotate Loop L as many times as possible. Return true if 93cc4e605721e1144da8990edca64bf5799220e279Dan Gohman/// the loop is rotated at least once. 94c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patelbool LoopRotate::runOnLoop(Loop *Lp, LPPassManager &LPM) { 95990e866deb158fd88377b5606c8d86603e93e533Devang Patel 96c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel bool RotatedOneLoop = false; 97c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel initialize(); 98990e866deb158fd88377b5606c8d86603e93e533Devang Patel LPM_Ptr = &LPM; 99c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 100c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel // One loop can be rotated multiple times. 101c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel while (rotateLoop(Lp,LPM)) { 102c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel RotatedOneLoop = true; 103c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel initialize(); 104c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 105c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 106c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return RotatedOneLoop; 107c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel} 108c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 10923d9d27c265753da55a8ee7879820acb4d1e3a6dDan Gohman/// Rotate loop LP. Return true if the loop is rotated. 110c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patelbool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) { 111c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel L = Lp; 112c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 113c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel OrigPreHeader = L->getLoopPreheader(); 11403e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman if (!OrigPreHeader) return false; 11503e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman 116c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel OrigLatch = L->getLoopLatch(); 11703e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman if (!OrigLatch) return false; 11803e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman 11903e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman OrigHeader = L->getHeader(); 120c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 121cc4e605721e1144da8990edca64bf5799220e279Dan Gohman // If the loop has only one block then there is not much to rotate. 122322313376a9ccac86cbfc208684d84936d62322dDevang Patel if (L->getBlocks().size() == 1) 123c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return false; 124c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 125cc4e605721e1144da8990edca64bf5799220e279Dan Gohman // If the loop header is not one of the loop exiting blocks then 126cc4e605721e1144da8990edca64bf5799220e279Dan Gohman // either this loop is already rotated or it is not 127c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel // suitable for loop rotation transformations. 12832663b719b4996b3a735f22bba80d771d50f96e7Dan Gohman if (!L->isLoopExiting(OrigHeader)) 129c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return false; 130c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 131c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator()); 132c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel if (!BI) 133c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return false; 1342ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(BI->isConditional() && "Branch Instruction is not conditional"); 135c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 136322313376a9ccac86cbfc208684d84936d62322dDevang Patel // Updating PHInodes in loops with multiple exits adds complexity. 137322313376a9ccac86cbfc208684d84936d62322dDevang Patel // Keep it simple, and restrict loop rotation to loops with one exit only. 138322313376a9ccac86cbfc208684d84936d62322dDevang Patel // In future, lift this restriction and support for multiple exits if 139322313376a9ccac86cbfc208684d84936d62322dDevang Patel // required. 140b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 141c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel L->getExitBlocks(ExitBlocks); 142c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel if (ExitBlocks.size() > 1) 143c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return false; 144c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 145d9e079706e782c5f054322a0d15f063a1a683230Chris Lattner // Check size of original header and reject loop if it is very big. 146d9e079706e782c5f054322a0d15f063a1a683230Chris Lattner { 147d9e079706e782c5f054322a0d15f063a1a683230Chris Lattner CodeMetrics Metrics; 148d9e079706e782c5f054322a0d15f063a1a683230Chris Lattner Metrics.analyzeBasicBlock(OrigHeader); 149d9e079706e782c5f054322a0d15f063a1a683230Chris Lattner if (Metrics.NumInsts > MAX_HEADER_SIZE) 150d9e079706e782c5f054322a0d15f063a1a683230Chris Lattner return false; 1513f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel } 1523f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel 153990e866deb158fd88377b5606c8d86603e93e533Devang Patel // Now, this loop is suitable for rotation. 154990e866deb158fd88377b5606c8d86603e93e533Devang Patel 155e6fe67b2fb48b1f0f3c1ac8c1ce01e67c1f0bb1dDan Gohman // Anything ScalarEvolution may know about this loop or the PHI nodes 156e6fe67b2fb48b1f0f3c1ac8c1ce01e67c1f0bb1dDan Gohman // in its header will soon be invalidated. 157e6fe67b2fb48b1f0f3c1ac8c1ce01e67c1f0bb1dDan Gohman if (ScalarEvolution *SE = getAnalysisIfAvailable<ScalarEvolution>()) 1584c7279ac726e338400626fca5a09b5533426eb6aDan Gohman SE->forgetLoop(L); 159e6fe67b2fb48b1f0f3c1ac8c1ce01e67c1f0bb1dDan Gohman 160c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel // Find new Loop header. NewHeader is a Header's one and only successor 161f6784a326293941cd4ff6d25da64732760e993f3Chris Lattner // that is inside loop. Header's other successor is outside the 162f6784a326293941cd4ff6d25da64732760e993f3Chris Lattner // loop. Otherwise loop is not suitable for rotation. 163322313376a9ccac86cbfc208684d84936d62322dDevang Patel Exit = BI->getSuccessor(0); 164322313376a9ccac86cbfc208684d84936d62322dDevang Patel NewHeader = BI->getSuccessor(1); 165322313376a9ccac86cbfc208684d84936d62322dDevang Patel if (L->contains(Exit)) 166322313376a9ccac86cbfc208684d84936d62322dDevang Patel std::swap(Exit, NewHeader); 1672ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(NewHeader && "Unable to determine new loop header"); 168322313376a9ccac86cbfc208684d84936d62322dDevang Patel assert(L->contains(NewHeader) && !L->contains(Exit) && 169322313376a9ccac86cbfc208684d84936d62322dDevang Patel "Unable to determine loop header and exit blocks"); 1703796a262c50e0b04c1a5a9571f12bb9bc4936c25Chris Lattner 171cc4e605721e1144da8990edca64bf5799220e279Dan Gohman // This code assumes that the new header has exactly one predecessor. 172cc4e605721e1144da8990edca64bf5799220e279Dan Gohman // Remove any single-entry PHI nodes in it. 1733796a262c50e0b04c1a5a9571f12bb9bc4936c25Chris Lattner assert(NewHeader->getSinglePredecessor() && 1743796a262c50e0b04c1a5a9571f12bb9bc4936c25Chris Lattner "New header doesn't have one pred!"); 1753796a262c50e0b04c1a5a9571f12bb9bc4936c25Chris Lattner FoldSingleEntryPHINodes(NewHeader); 176c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 177e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Begin by walking OrigHeader and populating ValueMap with an entry for 178e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // each Instruction. 179322313376a9ccac86cbfc208684d84936d62322dDevang Patel BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end(); 1806ccb3652933bcdede2b2a53cf76ddd56ce9592a2Chris Lattner ValueToValueMapTy ValueMap; 181322313376a9ccac86cbfc208684d84936d62322dDevang Patel 182e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // For PHI nodes, the value available in OldPreHeader is just the 183e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // incoming value from OldPreHeader. 184e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (; PHINode *PN = dyn_cast<PHINode>(I); ++I) 185e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman ValueMap[PN] = PN->getIncomingValue(PN->getBasicBlockIndex(OrigPreHeader)); 186e98815469ccd2f1f1585abdc7c36042177bc26f0Devang Patel 18750fb46983ccae116bdbda64471f4861108766135Chris Lattner // For the rest of the instructions, either hoist to the OrigPreheader if 18850fb46983ccae116bdbda64471f4861108766135Chris Lattner // possible or create a clone in the OldPreHeader if not. 189e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman TerminatorInst *LoopEntryBranch = OrigPreHeader->getTerminator(); 19050fb46983ccae116bdbda64471f4861108766135Chris Lattner while (I != E) { 19150fb46983ccae116bdbda64471f4861108766135Chris Lattner Instruction *Inst = I++; 19250fb46983ccae116bdbda64471f4861108766135Chris Lattner 19350fb46983ccae116bdbda64471f4861108766135Chris Lattner // If the instruction's operands are invariant and it doesn't read or write 19450fb46983ccae116bdbda64471f4861108766135Chris Lattner // memory, then it is safe to hoist. Doing this doesn't change the order of 19550fb46983ccae116bdbda64471f4861108766135Chris Lattner // execution in the preheader, but does prevent the instruction from 19650fb46983ccae116bdbda64471f4861108766135Chris Lattner // executing in each iteration of the loop. This means it is safe to hoist 19750fb46983ccae116bdbda64471f4861108766135Chris Lattner // something that might trap, but isn't safe to hoist something that reads 19850fb46983ccae116bdbda64471f4861108766135Chris Lattner // memory (without proving that the loop doesn't write). 19950fb46983ccae116bdbda64471f4861108766135Chris Lattner if (L->hasLoopInvariantOperands(Inst) && 20050fb46983ccae116bdbda64471f4861108766135Chris Lattner !Inst->mayReadFromMemory() && !Inst->mayWriteToMemory() && 20150fb46983ccae116bdbda64471f4861108766135Chris Lattner !isa<TerminatorInst>(Inst)) { 20250fb46983ccae116bdbda64471f4861108766135Chris Lattner Inst->moveBefore(LoopEntryBranch); 20350fb46983ccae116bdbda64471f4861108766135Chris Lattner continue; 20450fb46983ccae116bdbda64471f4861108766135Chris Lattner } 20550fb46983ccae116bdbda64471f4861108766135Chris Lattner 20650fb46983ccae116bdbda64471f4861108766135Chris Lattner // Otherwise, create a duplicate of the instruction. 20750fb46983ccae116bdbda64471f4861108766135Chris Lattner Instruction *C = Inst->clone(); 20850fb46983ccae116bdbda64471f4861108766135Chris Lattner C->setName(Inst->getName()); 209e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman C->insertBefore(LoopEntryBranch); 21050fb46983ccae116bdbda64471f4861108766135Chris Lattner ValueMap[Inst] = C; 211c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 212c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 213e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Along with all the other instructions, we just cloned OrigHeader's 214e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's 215e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // successors by duplicating their incoming values for OrigHeader. 216e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman TerminatorInst *TI = OrigHeader->getTerminator(); 217e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 218e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (BasicBlock::iterator BI = TI->getSuccessor(i)->begin(); 219e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman PHINode *PN = dyn_cast<PHINode>(BI); ++BI) 220e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreHeader); 221e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 222e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove 223e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // OrigPreHeader's old terminator (the original branch into the loop), and 224e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // remove the corresponding incoming values from the PHI nodes in OrigHeader. 225e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman LoopEntryBranch->eraseFromParent(); 226e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I) 227e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreHeader)); 228e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 229440e251c75f98ebfbd994afd1de72a2d06aae51eDan Gohman // Now fix up users of the instructions in OrigHeader, inserting PHI nodes 230e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // as necessary. 231e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman SSAUpdater SSA; 232e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (I = OrigHeader->begin(); I != E; ++I) { 233e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman Value *OrigHeaderVal = I; 234e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman Value *OrigPreHeaderVal = ValueMap[OrigHeaderVal]; 235e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 2366ccb3652933bcdede2b2a53cf76ddd56ce9592a2Chris Lattner // If there are no uses of the value (e.g. because it returns void), there 2376ccb3652933bcdede2b2a53cf76ddd56ce9592a2Chris Lattner // is nothing to rewrite. 2386ccb3652933bcdede2b2a53cf76ddd56ce9592a2Chris Lattner if (OrigHeaderVal->use_empty() && OrigPreHeaderVal->use_empty()) 2396ccb3652933bcdede2b2a53cf76ddd56ce9592a2Chris Lattner continue; 2406ccb3652933bcdede2b2a53cf76ddd56ce9592a2Chris Lattner 241e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // The value now exits in two versions: the initial value in the preheader 242e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // and the loop "next" value in the original header. 243fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName()); 244e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman SSA.AddAvailableValue(OrigHeader, OrigHeaderVal); 245e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman SSA.AddAvailableValue(OrigPreHeader, OrigPreHeaderVal); 246e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 247e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Visit each use of the OrigHeader instruction. 248e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (Value::use_iterator UI = OrigHeaderVal->use_begin(), 249e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman UE = OrigHeaderVal->use_end(); UI != UE; ) { 250e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Grab the use before incrementing the iterator. 251e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman Use &U = UI.getUse(); 252e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 253e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Increment the iterator before removing the use from the list. 254e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman ++UI; 255e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 256e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // SSAUpdater can't handle a non-PHI use in the same block as an 257e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // earlier def. We can easily handle those cases manually. 258e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman Instruction *UserInst = cast<Instruction>(U.getUser()); 259e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman if (!isa<PHINode>(UserInst)) { 260e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman BasicBlock *UserBB = UserInst->getParent(); 261e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 262e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // The original users in the OrigHeader are already using the 263e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // original definitions. 264e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman if (UserBB == OrigHeader) 26524a1c49172b7572652492ca986d49715ac1435eaDevang Patel continue; 26624a1c49172b7572652492ca986d49715ac1435eaDevang Patel 267e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Users in the OrigPreHeader need to use the value to which the 268e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // original definitions are mapped. 269e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman if (UserBB == OrigPreHeader) { 270e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman U = OrigPreHeaderVal; 271c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel continue; 272e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman } 273c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 274c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 275e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Anything else can be handled by SSAUpdater. 276e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman SSA.RewriteUse(U); 277c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 278c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 279c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 280e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // NewHeader is now the header of the loop. 281c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel L->moveToHeader(NewHeader); 282c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 283fc8042a1225790b3a6de434546623babea08496fDan Gohman // Move the original header to the bottom of the loop, where it now more 284fc8042a1225790b3a6de434546623babea08496fDan Gohman // naturally belongs. This isn't necessary for correctness, and CodeGen can 285fc8042a1225790b3a6de434546623babea08496fDan Gohman // usually reorder blocks on its own to fix things like this up, but it's 286fc8042a1225790b3a6de434546623babea08496fDan Gohman // still nice to keep the IR readable. 287fc8042a1225790b3a6de434546623babea08496fDan Gohman // 288fc8042a1225790b3a6de434546623babea08496fDan Gohman // The original header should have only one predecessor at this point, since 289fc8042a1225790b3a6de434546623babea08496fDan Gohman // we checked that the loop had a proper preheader and unique backedge before 290fc8042a1225790b3a6de434546623babea08496fDan Gohman // we started. 291fc8042a1225790b3a6de434546623babea08496fDan Gohman assert(OrigHeader->getSinglePredecessor() && 292fc8042a1225790b3a6de434546623babea08496fDan Gohman "Original loop header has too many predecessors after loop rotation!"); 293fc8042a1225790b3a6de434546623babea08496fDan Gohman OrigHeader->moveAfter(OrigHeader->getSinglePredecessor()); 294fc8042a1225790b3a6de434546623babea08496fDan Gohman 295fc8042a1225790b3a6de434546623babea08496fDan Gohman // Also, since this original header only has one predecessor, zap its 296fc8042a1225790b3a6de434546623babea08496fDan Gohman // PHI nodes, which are now trivial. 297fc8042a1225790b3a6de434546623babea08496fDan Gohman FoldSingleEntryPHINodes(OrigHeader); 298fc8042a1225790b3a6de434546623babea08496fDan Gohman 299fc8042a1225790b3a6de434546623babea08496fDan Gohman // TODO: We could just go ahead and merge OrigHeader into its predecessor 300fc8042a1225790b3a6de434546623babea08496fDan Gohman // at this point, if we don't mind updating dominator info. 301fc8042a1225790b3a6de434546623babea08496fDan Gohman 302fc8042a1225790b3a6de434546623babea08496fDan Gohman // Establish a new preheader, update dominators, etc. 3035464b96073626f811d79d56fa37be230552d2264Devang Patel preserveCanonicalLoopForm(LPM); 3045464b96073626f811d79d56fa37be230552d2264Devang Patel 305fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumRotated; 306c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return true; 307c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel} 308c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 309c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel/// Initialize local data 310c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patelvoid LoopRotate::initialize() { 311c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel L = NULL; 312c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel OrigHeader = NULL; 313c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel OrigPreHeader = NULL; 314c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel NewHeader = NULL; 315c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel Exit = NULL; 316c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel} 3175464b96073626f811d79d56fa37be230552d2264Devang Patel 3185464b96073626f811d79d56fa37be230552d2264Devang Patel/// After loop rotation, loop pre-header has multiple sucessors. 3195464b96073626f811d79d56fa37be230552d2264Devang Patel/// Insert one forwarding basic block to ensure that loop pre-header 3205464b96073626f811d79d56fa37be230552d2264Devang Patel/// has only one successor. 3215464b96073626f811d79d56fa37be230552d2264Devang Patelvoid LoopRotate::preserveCanonicalLoopForm(LPPassManager &LPM) { 3225464b96073626f811d79d56fa37be230552d2264Devang Patel 3235464b96073626f811d79d56fa37be230552d2264Devang Patel // Right now original pre-header has two successors, new header and 3245464b96073626f811d79d56fa37be230552d2264Devang Patel // exit block. Insert new block between original pre-header and 3255464b96073626f811d79d56fa37be230552d2264Devang Patel // new header such that loop's new pre-header has only one successor. 3261d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *NewPreHeader = BasicBlock::Create(OrigHeader->getContext(), 3271d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson "bb.nph", 328b1dbcd886a4b5597a839f299054b78b33fb2d6dfGabor Greif OrigHeader->getParent(), 329051a950000e21935165db56695e35bade668193bGabor Greif NewHeader); 3306a02fc3070c83ad8d59f071c88782f0c366bb07eDan Gohman LoopInfo &LI = getAnalysis<LoopInfo>(); 3315464b96073626f811d79d56fa37be230552d2264Devang Patel if (Loop *PL = LI.getLoopFor(OrigPreHeader)) 332d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson PL->addBasicBlockToLoop(NewPreHeader, LI.getBase()); 333051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(NewHeader, NewPreHeader); 3345464b96073626f811d79d56fa37be230552d2264Devang Patel 3355464b96073626f811d79d56fa37be230552d2264Devang Patel BranchInst *OrigPH_BI = cast<BranchInst>(OrigPreHeader->getTerminator()); 3365464b96073626f811d79d56fa37be230552d2264Devang Patel if (OrigPH_BI->getSuccessor(0) == NewHeader) 3375464b96073626f811d79d56fa37be230552d2264Devang Patel OrigPH_BI->setSuccessor(0, NewPreHeader); 3385464b96073626f811d79d56fa37be230552d2264Devang Patel else { 3392ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(OrigPH_BI->getSuccessor(1) == NewHeader && 3402ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Unexpected original pre-header terminator"); 3415464b96073626f811d79d56fa37be230552d2264Devang Patel OrigPH_BI->setSuccessor(1, NewPreHeader); 3425464b96073626f811d79d56fa37be230552d2264Devang Patel } 3435464b96073626f811d79d56fa37be230552d2264Devang Patel 344cfb32203bceb0638db976fea5ce906b2a1010bacDan Gohman PHINode *PN; 345cfb32203bceb0638db976fea5ce906b2a1010bacDan Gohman for (BasicBlock::iterator I = NewHeader->begin(); 346cfb32203bceb0638db976fea5ce906b2a1010bacDan Gohman (PN = dyn_cast<PHINode>(I)); ++I) { 3475464b96073626f811d79d56fa37be230552d2264Devang Patel int index = PN->getBasicBlockIndex(OrigPreHeader); 3482ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(index != -1 && "Expected incoming value from Original PreHeader"); 3495464b96073626f811d79d56fa37be230552d2264Devang Patel PN->setIncomingBlock(index, NewPreHeader); 3502ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(PN->getBasicBlockIndex(OrigPreHeader) == -1 && 3512ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Expected only one incoming value from Original PreHeader"); 3525464b96073626f811d79d56fa37be230552d2264Devang Patel } 3535464b96073626f811d79d56fa37be230552d2264Devang Patel 3541465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>()) { 355990e866deb158fd88377b5606c8d86603e93e533Devang Patel DT->addNewBlock(NewPreHeader, OrigPreHeader); 356990e866deb158fd88377b5606c8d86603e93e533Devang Patel DT->changeImmediateDominator(L->getHeader(), NewPreHeader); 357990e866deb158fd88377b5606c8d86603e93e533Devang Patel DT->changeImmediateDominator(Exit, OrigPreHeader); 358990e866deb158fd88377b5606c8d86603e93e533Devang Patel for (Loop::block_iterator BI = L->block_begin(), BE = L->block_end(); 359990e866deb158fd88377b5606c8d86603e93e533Devang Patel BI != BE; ++BI) { 360990e866deb158fd88377b5606c8d86603e93e533Devang Patel BasicBlock *B = *BI; 361990e866deb158fd88377b5606c8d86603e93e533Devang Patel if (L->getHeader() != B) { 362990e866deb158fd88377b5606c8d86603e93e533Devang Patel DomTreeNode *Node = DT->getNode(B); 363990e866deb158fd88377b5606c8d86603e93e533Devang Patel if (Node && Node->getBlock() == OrigHeader) 364990e866deb158fd88377b5606c8d86603e93e533Devang Patel DT->changeImmediateDominator(*BI, L->getHeader()); 365990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 366990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 367990e866deb158fd88377b5606c8d86603e93e533Devang Patel DT->changeImmediateDominator(OrigHeader, OrigLatch); 368990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 369990e866deb158fd88377b5606c8d86603e93e533Devang Patel 3701465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands if (DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>()) { 371990e866deb158fd88377b5606c8d86603e93e533Devang Patel // New Preheader's dominance frontier is Exit block. 372990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::DomSetType NewPHSet; 373990e866deb158fd88377b5606c8d86603e93e533Devang Patel NewPHSet.insert(Exit); 374990e866deb158fd88377b5606c8d86603e93e533Devang Patel DF->addBasicBlock(NewPreHeader, NewPHSet); 375990e866deb158fd88377b5606c8d86603e93e533Devang Patel 376990e866deb158fd88377b5606c8d86603e93e533Devang Patel // New Header's dominance frontier now includes itself and Exit block 377990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::iterator HeadI = DF->find(L->getHeader()); 378990e866deb158fd88377b5606c8d86603e93e533Devang Patel if (HeadI != DF->end()) { 379990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::DomSetType & HeaderSet = HeadI->second; 380990e866deb158fd88377b5606c8d86603e93e533Devang Patel HeaderSet.clear(); 381990e866deb158fd88377b5606c8d86603e93e533Devang Patel HeaderSet.insert(L->getHeader()); 382990e866deb158fd88377b5606c8d86603e93e533Devang Patel HeaderSet.insert(Exit); 383990e866deb158fd88377b5606c8d86603e93e533Devang Patel } else { 384990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::DomSetType HeaderSet; 385990e866deb158fd88377b5606c8d86603e93e533Devang Patel HeaderSet.insert(L->getHeader()); 386990e866deb158fd88377b5606c8d86603e93e533Devang Patel HeaderSet.insert(Exit); 387990e866deb158fd88377b5606c8d86603e93e533Devang Patel DF->addBasicBlock(L->getHeader(), HeaderSet); 388990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 389990e866deb158fd88377b5606c8d86603e93e533Devang Patel 390990e866deb158fd88377b5606c8d86603e93e533Devang Patel // Original header (new Loop Latch)'s dominance frontier is Exit. 391990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::iterator LatchI = DF->find(L->getLoopLatch()); 392990e866deb158fd88377b5606c8d86603e93e533Devang Patel if (LatchI != DF->end()) { 393990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::DomSetType &LatchSet = LatchI->second; 394990e866deb158fd88377b5606c8d86603e93e533Devang Patel LatchSet = LatchI->second; 395990e866deb158fd88377b5606c8d86603e93e533Devang Patel LatchSet.clear(); 396990e866deb158fd88377b5606c8d86603e93e533Devang Patel LatchSet.insert(Exit); 397990e866deb158fd88377b5606c8d86603e93e533Devang Patel } else { 398990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::DomSetType LatchSet; 399990e866deb158fd88377b5606c8d86603e93e533Devang Patel LatchSet.insert(Exit); 400990e866deb158fd88377b5606c8d86603e93e533Devang Patel DF->addBasicBlock(L->getHeader(), LatchSet); 401990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 402990e866deb158fd88377b5606c8d86603e93e533Devang Patel 403b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel // If a loop block dominates new loop latch then add to its frontiers 404b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel // new header and Exit and remove new latch (which is equal to original 405b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel // header). 406990e866deb158fd88377b5606c8d86603e93e533Devang Patel BasicBlock *NewLatch = L->getLoopLatch(); 407b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel 408b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel assert(NewLatch == OrigHeader && "NewLatch is inequal to OrigHeader"); 409b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel 410b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>()) { 411b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel for (Loop::block_iterator BI = L->block_begin(), BE = L->block_end(); 412b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BI != BE; ++BI) { 413b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BasicBlock *B = *BI; 414b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel if (DT->dominates(B, NewLatch)) { 415b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel DominanceFrontier::iterator BDFI = DF->find(B); 416b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel if (BDFI != DF->end()) { 417b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel DominanceFrontier::DomSetType &BSet = BDFI->second; 418b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BSet.erase(NewLatch); 419b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BSet.insert(L->getHeader()); 420b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BSet.insert(Exit); 421b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel } else { 422b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel DominanceFrontier::DomSetType BSet; 423b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BSet.insert(L->getHeader()); 424b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BSet.insert(Exit); 425b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel DF->addBasicBlock(B, BSet); 426b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel } 427990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 428990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 429990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 430990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 431990e866deb158fd88377b5606c8d86603e93e533Devang Patel 432990e866deb158fd88377b5606c8d86603e93e533Devang Patel // Preserve canonical loop form, which means Exit block should 433990e866deb158fd88377b5606c8d86603e93e533Devang Patel // have only one predecessor. 434c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman SplitEdge(L->getLoopLatch(), Exit, this); 435990e866deb158fd88377b5606c8d86603e93e533Devang Patel 4362ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(NewHeader && L->getHeader() == NewHeader && 4372ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Invalid loop header after loop rotation"); 4382ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(NewPreHeader && L->getLoopPreheader() == NewPreHeader && 4392ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Invalid loop preheader after loop rotation"); 4402ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(L->getLoopLatch() && 4412ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Invalid loop latch after loop rotation"); 4425464b96073626f811d79d56fa37be230552d2264Devang Patel} 443