LoopRotation.cpp revision d9ec3572f3d0997348361334446f942194522127
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" 17d9e079706e782c5f054322a0d15f063a1a683230Chris Lattner#include "llvm/Analysis/CodeMetrics.h" 18d9ec3572f3d0997348361334446f942194522127Chris Lattner#include "llvm/Analysis/DominanceFrontier.h" 19d9ec3572f3d0997348361334446f942194522127Chris Lattner#include "llvm/Analysis/LoopPass.h" 20d9ec3572f3d0997348361334446f942194522127Chris Lattner#include "llvm/Analysis/InstructionSimplify.h" 21990e866deb158fd88377b5606c8d86603e93e533Devang Patel#include "llvm/Analysis/ScalarEvolution.h" 22c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#include "llvm/Transforms/Utils/Local.h" 23990e866deb158fd88377b5606c8d86603e93e533Devang Patel#include "llvm/Transforms/Utils/BasicBlockUtils.h" 24e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman#include "llvm/Transforms/Utils/SSAUpdater.h" 256ccb3652933bcdede2b2a53cf76ddd56ce9592a2Chris Lattner#include "llvm/Transforms/Utils/ValueMapper.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(); 208b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner 209d9ec3572f3d0997348361334446f942194522127Chris Lattner // Eagerly remap the operands of the instruction. 210d9ec3572f3d0997348361334446f942194522127Chris Lattner RemapInstruction(C, ValueMap, 211d9ec3572f3d0997348361334446f942194522127Chris Lattner RF_NoModuleLevelChanges|RF_IgnoreMissingEntries); 212d9ec3572f3d0997348361334446f942194522127Chris Lattner 213d9ec3572f3d0997348361334446f942194522127Chris Lattner // With the operands remapped, see if the instruction constant folds or is 214d9ec3572f3d0997348361334446f942194522127Chris Lattner // otherwise simplifyable. This commonly occurs because the entry from PHI 215d9ec3572f3d0997348361334446f942194522127Chris Lattner // nodes allows icmps and other instructions to fold. 216d9ec3572f3d0997348361334446f942194522127Chris Lattner if (Value *V = SimplifyInstruction(C)) { 217d9ec3572f3d0997348361334446f942194522127Chris Lattner // If so, then delete the temporary instruction and stick the folded value 218d9ec3572f3d0997348361334446f942194522127Chris Lattner // in the map. 219d9ec3572f3d0997348361334446f942194522127Chris Lattner delete C; 220d9ec3572f3d0997348361334446f942194522127Chris Lattner ValueMap[Inst] = V; 221d9ec3572f3d0997348361334446f942194522127Chris Lattner } else { 222d9ec3572f3d0997348361334446f942194522127Chris Lattner // Otherwise, stick the new instruction into the new block! 223d9ec3572f3d0997348361334446f942194522127Chris Lattner C->setName(Inst->getName()); 224d9ec3572f3d0997348361334446f942194522127Chris Lattner C->insertBefore(LoopEntryBranch); 225d9ec3572f3d0997348361334446f942194522127Chris Lattner ValueMap[Inst] = C; 226d9ec3572f3d0997348361334446f942194522127Chris Lattner } 227c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 228c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 229e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Along with all the other instructions, we just cloned OrigHeader's 230e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's 231e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // successors by duplicating their incoming values for OrigHeader. 232e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman TerminatorInst *TI = OrigHeader->getTerminator(); 233e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 234e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (BasicBlock::iterator BI = TI->getSuccessor(i)->begin(); 235e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman PHINode *PN = dyn_cast<PHINode>(BI); ++BI) 236e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreHeader); 237e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 238e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove 239e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // OrigPreHeader's old terminator (the original branch into the loop), and 240e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // remove the corresponding incoming values from the PHI nodes in OrigHeader. 241e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman LoopEntryBranch->eraseFromParent(); 242e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I) 243e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreHeader)); 244e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 245440e251c75f98ebfbd994afd1de72a2d06aae51eDan Gohman // Now fix up users of the instructions in OrigHeader, inserting PHI nodes 246e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // as necessary. 247e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman SSAUpdater SSA; 248e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (I = OrigHeader->begin(); I != E; ++I) { 249e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman Value *OrigHeaderVal = I; 250e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman Value *OrigPreHeaderVal = ValueMap[OrigHeaderVal]; 251e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 2526ccb3652933bcdede2b2a53cf76ddd56ce9592a2Chris Lattner // If there are no uses of the value (e.g. because it returns void), there 2536ccb3652933bcdede2b2a53cf76ddd56ce9592a2Chris Lattner // is nothing to rewrite. 2546ccb3652933bcdede2b2a53cf76ddd56ce9592a2Chris Lattner if (OrigHeaderVal->use_empty() && OrigPreHeaderVal->use_empty()) 2556ccb3652933bcdede2b2a53cf76ddd56ce9592a2Chris Lattner continue; 2566ccb3652933bcdede2b2a53cf76ddd56ce9592a2Chris Lattner 257e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // The value now exits in two versions: the initial value in the preheader 258e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // and the loop "next" value in the original header. 259fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName()); 260e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman SSA.AddAvailableValue(OrigHeader, OrigHeaderVal); 261e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman SSA.AddAvailableValue(OrigPreHeader, OrigPreHeaderVal); 262e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 263e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Visit each use of the OrigHeader instruction. 264e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (Value::use_iterator UI = OrigHeaderVal->use_begin(), 265e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman UE = OrigHeaderVal->use_end(); UI != UE; ) { 266e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Grab the use before incrementing the iterator. 267e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman Use &U = UI.getUse(); 268e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 269e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Increment the iterator before removing the use from the list. 270e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman ++UI; 271e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 272e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // SSAUpdater can't handle a non-PHI use in the same block as an 273e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // earlier def. We can easily handle those cases manually. 274e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman Instruction *UserInst = cast<Instruction>(U.getUser()); 275e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman if (!isa<PHINode>(UserInst)) { 276e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman BasicBlock *UserBB = UserInst->getParent(); 277e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 278e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // The original users in the OrigHeader are already using the 279e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // original definitions. 280e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman if (UserBB == OrigHeader) 28124a1c49172b7572652492ca986d49715ac1435eaDevang Patel continue; 28224a1c49172b7572652492ca986d49715ac1435eaDevang Patel 283e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Users in the OrigPreHeader need to use the value to which the 284e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // original definitions are mapped. 285e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman if (UserBB == OrigPreHeader) { 286e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman U = OrigPreHeaderVal; 287c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel continue; 288e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman } 289c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 290c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 291e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Anything else can be handled by SSAUpdater. 292e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman SSA.RewriteUse(U); 293c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 294c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 295c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 296e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // NewHeader is now the header of the loop. 297c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel L->moveToHeader(NewHeader); 298c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 299fc8042a1225790b3a6de434546623babea08496fDan Gohman // Move the original header to the bottom of the loop, where it now more 300fc8042a1225790b3a6de434546623babea08496fDan Gohman // naturally belongs. This isn't necessary for correctness, and CodeGen can 301fc8042a1225790b3a6de434546623babea08496fDan Gohman // usually reorder blocks on its own to fix things like this up, but it's 302fc8042a1225790b3a6de434546623babea08496fDan Gohman // still nice to keep the IR readable. 303fc8042a1225790b3a6de434546623babea08496fDan Gohman // 304fc8042a1225790b3a6de434546623babea08496fDan Gohman // The original header should have only one predecessor at this point, since 305fc8042a1225790b3a6de434546623babea08496fDan Gohman // we checked that the loop had a proper preheader and unique backedge before 306fc8042a1225790b3a6de434546623babea08496fDan Gohman // we started. 307fc8042a1225790b3a6de434546623babea08496fDan Gohman assert(OrigHeader->getSinglePredecessor() && 308fc8042a1225790b3a6de434546623babea08496fDan Gohman "Original loop header has too many predecessors after loop rotation!"); 309fc8042a1225790b3a6de434546623babea08496fDan Gohman OrigHeader->moveAfter(OrigHeader->getSinglePredecessor()); 310fc8042a1225790b3a6de434546623babea08496fDan Gohman 311fc8042a1225790b3a6de434546623babea08496fDan Gohman // Also, since this original header only has one predecessor, zap its 312fc8042a1225790b3a6de434546623babea08496fDan Gohman // PHI nodes, which are now trivial. 313fc8042a1225790b3a6de434546623babea08496fDan Gohman FoldSingleEntryPHINodes(OrigHeader); 314fc8042a1225790b3a6de434546623babea08496fDan Gohman 315fc8042a1225790b3a6de434546623babea08496fDan Gohman // TODO: We could just go ahead and merge OrigHeader into its predecessor 316fc8042a1225790b3a6de434546623babea08496fDan Gohman // at this point, if we don't mind updating dominator info. 317fc8042a1225790b3a6de434546623babea08496fDan Gohman 318fc8042a1225790b3a6de434546623babea08496fDan Gohman // Establish a new preheader, update dominators, etc. 3195464b96073626f811d79d56fa37be230552d2264Devang Patel preserveCanonicalLoopForm(LPM); 3205464b96073626f811d79d56fa37be230552d2264Devang Patel 321fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumRotated; 322c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return true; 323c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel} 324c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 325c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel/// Initialize local data 326c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patelvoid LoopRotate::initialize() { 327c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel L = NULL; 328c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel OrigHeader = NULL; 329c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel OrigPreHeader = NULL; 330c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel NewHeader = NULL; 331c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel Exit = NULL; 332c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel} 3335464b96073626f811d79d56fa37be230552d2264Devang Patel 3345464b96073626f811d79d56fa37be230552d2264Devang Patel/// After loop rotation, loop pre-header has multiple sucessors. 3355464b96073626f811d79d56fa37be230552d2264Devang Patel/// Insert one forwarding basic block to ensure that loop pre-header 3365464b96073626f811d79d56fa37be230552d2264Devang Patel/// has only one successor. 3375464b96073626f811d79d56fa37be230552d2264Devang Patelvoid LoopRotate::preserveCanonicalLoopForm(LPPassManager &LPM) { 3385464b96073626f811d79d56fa37be230552d2264Devang Patel 3395464b96073626f811d79d56fa37be230552d2264Devang Patel // Right now original pre-header has two successors, new header and 3405464b96073626f811d79d56fa37be230552d2264Devang Patel // exit block. Insert new block between original pre-header and 3415464b96073626f811d79d56fa37be230552d2264Devang Patel // new header such that loop's new pre-header has only one successor. 3421d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *NewPreHeader = BasicBlock::Create(OrigHeader->getContext(), 3431d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson "bb.nph", 344b1dbcd886a4b5597a839f299054b78b33fb2d6dfGabor Greif OrigHeader->getParent(), 345051a950000e21935165db56695e35bade668193bGabor Greif NewHeader); 3466a02fc3070c83ad8d59f071c88782f0c366bb07eDan Gohman LoopInfo &LI = getAnalysis<LoopInfo>(); 3475464b96073626f811d79d56fa37be230552d2264Devang Patel if (Loop *PL = LI.getLoopFor(OrigPreHeader)) 348d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson PL->addBasicBlockToLoop(NewPreHeader, LI.getBase()); 349051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(NewHeader, NewPreHeader); 3505464b96073626f811d79d56fa37be230552d2264Devang Patel 3515464b96073626f811d79d56fa37be230552d2264Devang Patel BranchInst *OrigPH_BI = cast<BranchInst>(OrigPreHeader->getTerminator()); 3525464b96073626f811d79d56fa37be230552d2264Devang Patel if (OrigPH_BI->getSuccessor(0) == NewHeader) 3535464b96073626f811d79d56fa37be230552d2264Devang Patel OrigPH_BI->setSuccessor(0, NewPreHeader); 3545464b96073626f811d79d56fa37be230552d2264Devang Patel else { 3552ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(OrigPH_BI->getSuccessor(1) == NewHeader && 3562ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Unexpected original pre-header terminator"); 3575464b96073626f811d79d56fa37be230552d2264Devang Patel OrigPH_BI->setSuccessor(1, NewPreHeader); 3585464b96073626f811d79d56fa37be230552d2264Devang Patel } 3595464b96073626f811d79d56fa37be230552d2264Devang Patel 360cfb32203bceb0638db976fea5ce906b2a1010bacDan Gohman PHINode *PN; 361cfb32203bceb0638db976fea5ce906b2a1010bacDan Gohman for (BasicBlock::iterator I = NewHeader->begin(); 362cfb32203bceb0638db976fea5ce906b2a1010bacDan Gohman (PN = dyn_cast<PHINode>(I)); ++I) { 3635464b96073626f811d79d56fa37be230552d2264Devang Patel int index = PN->getBasicBlockIndex(OrigPreHeader); 3642ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(index != -1 && "Expected incoming value from Original PreHeader"); 3655464b96073626f811d79d56fa37be230552d2264Devang Patel PN->setIncomingBlock(index, NewPreHeader); 3662ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(PN->getBasicBlockIndex(OrigPreHeader) == -1 && 3672ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Expected only one incoming value from Original PreHeader"); 3685464b96073626f811d79d56fa37be230552d2264Devang Patel } 3695464b96073626f811d79d56fa37be230552d2264Devang Patel 3701465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>()) { 371990e866deb158fd88377b5606c8d86603e93e533Devang Patel DT->addNewBlock(NewPreHeader, OrigPreHeader); 372990e866deb158fd88377b5606c8d86603e93e533Devang Patel DT->changeImmediateDominator(L->getHeader(), NewPreHeader); 373990e866deb158fd88377b5606c8d86603e93e533Devang Patel DT->changeImmediateDominator(Exit, OrigPreHeader); 374990e866deb158fd88377b5606c8d86603e93e533Devang Patel for (Loop::block_iterator BI = L->block_begin(), BE = L->block_end(); 375990e866deb158fd88377b5606c8d86603e93e533Devang Patel BI != BE; ++BI) { 376990e866deb158fd88377b5606c8d86603e93e533Devang Patel BasicBlock *B = *BI; 377990e866deb158fd88377b5606c8d86603e93e533Devang Patel if (L->getHeader() != B) { 378990e866deb158fd88377b5606c8d86603e93e533Devang Patel DomTreeNode *Node = DT->getNode(B); 379990e866deb158fd88377b5606c8d86603e93e533Devang Patel if (Node && Node->getBlock() == OrigHeader) 380990e866deb158fd88377b5606c8d86603e93e533Devang Patel DT->changeImmediateDominator(*BI, L->getHeader()); 381990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 382990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 383990e866deb158fd88377b5606c8d86603e93e533Devang Patel DT->changeImmediateDominator(OrigHeader, OrigLatch); 384990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 385990e866deb158fd88377b5606c8d86603e93e533Devang Patel 3861465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands if (DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>()) { 387990e866deb158fd88377b5606c8d86603e93e533Devang Patel // New Preheader's dominance frontier is Exit block. 388990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::DomSetType NewPHSet; 389990e866deb158fd88377b5606c8d86603e93e533Devang Patel NewPHSet.insert(Exit); 390990e866deb158fd88377b5606c8d86603e93e533Devang Patel DF->addBasicBlock(NewPreHeader, NewPHSet); 391990e866deb158fd88377b5606c8d86603e93e533Devang Patel 392990e866deb158fd88377b5606c8d86603e93e533Devang Patel // New Header's dominance frontier now includes itself and Exit block 393990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::iterator HeadI = DF->find(L->getHeader()); 394990e866deb158fd88377b5606c8d86603e93e533Devang Patel if (HeadI != DF->end()) { 395990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::DomSetType & HeaderSet = HeadI->second; 396990e866deb158fd88377b5606c8d86603e93e533Devang Patel HeaderSet.clear(); 397990e866deb158fd88377b5606c8d86603e93e533Devang Patel HeaderSet.insert(L->getHeader()); 398990e866deb158fd88377b5606c8d86603e93e533Devang Patel HeaderSet.insert(Exit); 399990e866deb158fd88377b5606c8d86603e93e533Devang Patel } else { 400990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::DomSetType HeaderSet; 401990e866deb158fd88377b5606c8d86603e93e533Devang Patel HeaderSet.insert(L->getHeader()); 402990e866deb158fd88377b5606c8d86603e93e533Devang Patel HeaderSet.insert(Exit); 403990e866deb158fd88377b5606c8d86603e93e533Devang Patel DF->addBasicBlock(L->getHeader(), HeaderSet); 404990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 405990e866deb158fd88377b5606c8d86603e93e533Devang Patel 406990e866deb158fd88377b5606c8d86603e93e533Devang Patel // Original header (new Loop Latch)'s dominance frontier is Exit. 407990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::iterator LatchI = DF->find(L->getLoopLatch()); 408990e866deb158fd88377b5606c8d86603e93e533Devang Patel if (LatchI != DF->end()) { 409990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::DomSetType &LatchSet = LatchI->second; 410990e866deb158fd88377b5606c8d86603e93e533Devang Patel LatchSet = LatchI->second; 411990e866deb158fd88377b5606c8d86603e93e533Devang Patel LatchSet.clear(); 412990e866deb158fd88377b5606c8d86603e93e533Devang Patel LatchSet.insert(Exit); 413990e866deb158fd88377b5606c8d86603e93e533Devang Patel } else { 414990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::DomSetType LatchSet; 415990e866deb158fd88377b5606c8d86603e93e533Devang Patel LatchSet.insert(Exit); 416990e866deb158fd88377b5606c8d86603e93e533Devang Patel DF->addBasicBlock(L->getHeader(), LatchSet); 417990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 418990e866deb158fd88377b5606c8d86603e93e533Devang Patel 419b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel // If a loop block dominates new loop latch then add to its frontiers 420b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel // new header and Exit and remove new latch (which is equal to original 421b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel // header). 422990e866deb158fd88377b5606c8d86603e93e533Devang Patel BasicBlock *NewLatch = L->getLoopLatch(); 423b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel 424b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel assert(NewLatch == OrigHeader && "NewLatch is inequal to OrigHeader"); 425b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel 426b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>()) { 427b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel for (Loop::block_iterator BI = L->block_begin(), BE = L->block_end(); 428b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BI != BE; ++BI) { 429b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BasicBlock *B = *BI; 430b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel if (DT->dominates(B, NewLatch)) { 431b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel DominanceFrontier::iterator BDFI = DF->find(B); 432b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel if (BDFI != DF->end()) { 433b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel DominanceFrontier::DomSetType &BSet = BDFI->second; 434b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BSet.erase(NewLatch); 435b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BSet.insert(L->getHeader()); 436b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BSet.insert(Exit); 437b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel } else { 438b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel DominanceFrontier::DomSetType BSet; 439b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BSet.insert(L->getHeader()); 440b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BSet.insert(Exit); 441b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel DF->addBasicBlock(B, BSet); 442b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel } 443990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 444990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 445990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 446990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 447990e866deb158fd88377b5606c8d86603e93e533Devang Patel 448990e866deb158fd88377b5606c8d86603e93e533Devang Patel // Preserve canonical loop form, which means Exit block should 449990e866deb158fd88377b5606c8d86603e93e533Devang Patel // have only one predecessor. 450c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman SplitEdge(L->getLoopLatch(), Exit, this); 451990e866deb158fd88377b5606c8d86603e93e533Devang Patel 4522ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(NewHeader && L->getHeader() == NewHeader && 4532ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Invalid loop header after loop rotation"); 4542ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(NewPreHeader && L->getLoopPreheader() == NewPreHeader && 4552ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Invalid loop preheader after loop rotation"); 4562ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(L->getLoopLatch() && 4572ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Invalid loop latch after loop rotation"); 4585464b96073626f811d79d56fa37be230552d2264Devang Patel} 459