LoopRotation.cpp revision 32663b719b4996b3a735f22bba80d771d50f96e7
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" 173f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel#include "llvm/IntrinsicInst.h" 18c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#include "llvm/Analysis/LoopInfo.h" 19c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#include "llvm/Analysis/LoopPass.h" 20990e866deb158fd88377b5606c8d86603e93e533Devang Patel#include "llvm/Analysis/Dominators.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" 25c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#include "llvm/Support/CommandLine.h" 26c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#include "llvm/Support/Debug.h" 27c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#include "llvm/ADT/Statistic.h" 28c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#include "llvm/ADT/SmallVector.h" 29c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patelusing namespace llvm; 30c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 31c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel#define MAX_HEADER_SIZE 16 32c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 33c4625da483ff9e835aef886864e37dd68fb7a03cDevang PatelSTATISTIC(NumRotated, "Number of loops rotated"); 34c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patelnamespace { 35c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 363e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class LoopRotate : public LoopPass { 37c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel public: 381997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; // Pass ID, replacement for typeid 39ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman LoopRotate() : LoopPass(&ID) {} 40794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 41322313376a9ccac86cbfc208684d84936d62322dDevang Patel // Rotate Loop L as many times as possible. Return true if 42322313376a9ccac86cbfc208684d84936d62322dDevang Patel // loop is rotated at least once. 43c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel bool runOnLoop(Loop *L, LPPassManager &LPM); 44322313376a9ccac86cbfc208684d84936d62322dDevang Patel 45322313376a9ccac86cbfc208684d84936d62322dDevang Patel // LCSSA form makes instruction renaming easier. 46c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel virtual void getAnalysisUsage(AnalysisUsage &AU) const { 479d9b204d6a155f4778a9009c643eed5bf59148e2Devang Patel AU.addRequiredID(LoopSimplifyID); 489d9b204d6a155f4778a9009c643eed5bf59148e2Devang Patel AU.addPreservedID(LoopSimplifyID); 49c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel AU.addRequiredID(LCSSAID); 50c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel AU.addPreservedID(LCSSAID); 51990e866deb158fd88377b5606c8d86603e93e533Devang Patel AU.addPreserved<ScalarEvolution>(); 52990e866deb158fd88377b5606c8d86603e93e533Devang Patel AU.addPreserved<LoopInfo>(); 53d9a6dcba9f394078cff11c8f09a48f2c072de18dDevang Patel AU.addPreserved<DominatorTree>(); 54d9a6dcba9f394078cff11c8f09a48f2c072de18dDevang Patel AU.addPreserved<DominanceFrontier>(); 55c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 56c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 57c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel // Helper functions 58c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 59c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel /// Do actual work 60c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel bool rotateLoop(Loop *L, LPPassManager &LPM); 61c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 62c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel /// Initialize local data 63c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel void initialize(); 64c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 655464b96073626f811d79d56fa37be230552d2264Devang Patel /// After loop rotation, loop pre-header has multiple sucessors. 665464b96073626f811d79d56fa37be230552d2264Devang Patel /// Insert one forwarding basic block to ensure that loop pre-header 675464b96073626f811d79d56fa37be230552d2264Devang Patel /// has only one successor. 685464b96073626f811d79d56fa37be230552d2264Devang Patel void preserveCanonicalLoopForm(LPPassManager &LPM); 695464b96073626f811d79d56fa37be230552d2264Devang Patel 70c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel private: 71c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel Loop *L; 72c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel BasicBlock *OrigHeader; 73c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel BasicBlock *OrigPreHeader; 74c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel BasicBlock *OrigLatch; 75c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel BasicBlock *NewHeader; 76c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel BasicBlock *Exit; 77990e866deb158fd88377b5606c8d86603e93e533Devang Patel LPPassManager *LPM_Ptr; 78c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel }; 79c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel} 80844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 81844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LoopRotate::ID = 0; 82844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<LoopRotate> X("loop-rotate", "Rotate Loops"); 83c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 84394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass *llvm::createLoopRotatePass() { return new LoopRotate(); } 85c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 86322313376a9ccac86cbfc208684d84936d62322dDevang Patel/// Rotate Loop L as many times as possible. Return true if 87cc4e605721e1144da8990edca64bf5799220e279Dan Gohman/// the loop is rotated at least once. 88c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patelbool LoopRotate::runOnLoop(Loop *Lp, LPPassManager &LPM) { 89990e866deb158fd88377b5606c8d86603e93e533Devang Patel 90c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel bool RotatedOneLoop = false; 91c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel initialize(); 92990e866deb158fd88377b5606c8d86603e93e533Devang Patel LPM_Ptr = &LPM; 93c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 94c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel // One loop can be rotated multiple times. 95c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel while (rotateLoop(Lp,LPM)) { 96c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel RotatedOneLoop = true; 97c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel initialize(); 98c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 99c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 100c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return RotatedOneLoop; 101c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel} 102c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 10323d9d27c265753da55a8ee7879820acb4d1e3a6dDan Gohman/// Rotate loop LP. Return true if the loop is rotated. 104c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patelbool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) { 105c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel L = Lp; 106c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 107c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel OrigHeader = L->getHeader(); 108c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel OrigPreHeader = L->getLoopPreheader(); 109c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel OrigLatch = L->getLoopLatch(); 110c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 111cc4e605721e1144da8990edca64bf5799220e279Dan Gohman // If the loop has only one block then there is not much to rotate. 112322313376a9ccac86cbfc208684d84936d62322dDevang Patel if (L->getBlocks().size() == 1) 113c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return false; 114c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 1152ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(OrigHeader && OrigLatch && OrigPreHeader && 1162ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Loop is not in canonical form"); 117e98815469ccd2f1f1585abdc7c36042177bc26f0Devang Patel 118cc4e605721e1144da8990edca64bf5799220e279Dan Gohman // If the loop header is not one of the loop exiting blocks then 119cc4e605721e1144da8990edca64bf5799220e279Dan Gohman // either this loop is already rotated or it is not 120c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel // suitable for loop rotation transformations. 12132663b719b4996b3a735f22bba80d771d50f96e7Dan Gohman if (!L->isLoopExiting(OrigHeader)) 122c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return false; 123c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 124c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator()); 125c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel if (!BI) 126c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return false; 1272ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(BI->isConditional() && "Branch Instruction is not conditional"); 128c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 129322313376a9ccac86cbfc208684d84936d62322dDevang Patel // Updating PHInodes in loops with multiple exits adds complexity. 130322313376a9ccac86cbfc208684d84936d62322dDevang Patel // Keep it simple, and restrict loop rotation to loops with one exit only. 131322313376a9ccac86cbfc208684d84936d62322dDevang Patel // In future, lift this restriction and support for multiple exits if 132322313376a9ccac86cbfc208684d84936d62322dDevang Patel // required. 133b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 134c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel L->getExitBlocks(ExitBlocks); 135c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel if (ExitBlocks.size() > 1) 136c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return false; 137c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 138990e866deb158fd88377b5606c8d86603e93e533Devang Patel // Check size of original header and reject 139990e866deb158fd88377b5606c8d86603e93e533Devang Patel // loop if it is very big. 1403f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel unsigned Size = 0; 1413f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel 1423f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel // FIXME: Use common api to estimate size. 1433f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel for (BasicBlock::const_iterator OI = OrigHeader->begin(), 1443f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel OE = OrigHeader->end(); OI != OE; ++OI) { 1453f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel if (isa<PHINode>(OI)) 1463f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel continue; // PHI nodes don't count. 1473f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel if (isa<DbgInfoIntrinsic>(OI)) 1483f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel continue; // Debug intrinsics don't count as size. 1493f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel Size++; 1503f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel } 1513f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel 1523f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel if (Size > MAX_HEADER_SIZE) 153990e866deb158fd88377b5606c8d86603e93e533Devang Patel return false; 154990e866deb158fd88377b5606c8d86603e93e533Devang Patel 155990e866deb158fd88377b5606c8d86603e93e533Devang Patel // Now, this loop is suitable for rotation. 156990e866deb158fd88377b5606c8d86603e93e533Devang Patel 157e6fe67b2fb48b1f0f3c1ac8c1ce01e67c1f0bb1dDan Gohman // Anything ScalarEvolution may know about this loop or the PHI nodes 158e6fe67b2fb48b1f0f3c1ac8c1ce01e67c1f0bb1dDan Gohman // in its header will soon be invalidated. 159e6fe67b2fb48b1f0f3c1ac8c1ce01e67c1f0bb1dDan Gohman if (ScalarEvolution *SE = getAnalysisIfAvailable<ScalarEvolution>()) 160e6fe67b2fb48b1f0f3c1ac8c1ce01e67c1f0bb1dDan Gohman SE->forgetLoopBackedgeTakenCount(L); 161e6fe67b2fb48b1f0f3c1ac8c1ce01e67c1f0bb1dDan Gohman 162c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel // Find new Loop header. NewHeader is a Header's one and only successor 163f6784a326293941cd4ff6d25da64732760e993f3Chris Lattner // that is inside loop. Header's other successor is outside the 164f6784a326293941cd4ff6d25da64732760e993f3Chris Lattner // loop. Otherwise loop is not suitable for rotation. 165322313376a9ccac86cbfc208684d84936d62322dDevang Patel Exit = BI->getSuccessor(0); 166322313376a9ccac86cbfc208684d84936d62322dDevang Patel NewHeader = BI->getSuccessor(1); 167322313376a9ccac86cbfc208684d84936d62322dDevang Patel if (L->contains(Exit)) 168322313376a9ccac86cbfc208684d84936d62322dDevang Patel std::swap(Exit, NewHeader); 1692ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(NewHeader && "Unable to determine new loop header"); 170322313376a9ccac86cbfc208684d84936d62322dDevang Patel assert(L->contains(NewHeader) && !L->contains(Exit) && 171322313376a9ccac86cbfc208684d84936d62322dDevang Patel "Unable to determine loop header and exit blocks"); 1723796a262c50e0b04c1a5a9571f12bb9bc4936c25Chris Lattner 173cc4e605721e1144da8990edca64bf5799220e279Dan Gohman // This code assumes that the new header has exactly one predecessor. 174cc4e605721e1144da8990edca64bf5799220e279Dan Gohman // Remove any single-entry PHI nodes in it. 1753796a262c50e0b04c1a5a9571f12bb9bc4936c25Chris Lattner assert(NewHeader->getSinglePredecessor() && 1763796a262c50e0b04c1a5a9571f12bb9bc4936c25Chris Lattner "New header doesn't have one pred!"); 1773796a262c50e0b04c1a5a9571f12bb9bc4936c25Chris Lattner FoldSingleEntryPHINodes(NewHeader); 178c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 179e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Begin by walking OrigHeader and populating ValueMap with an entry for 180e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // each Instruction. 181322313376a9ccac86cbfc208684d84936d62322dDevang Patel BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end(); 182e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman DenseMap<const Value *, Value *> ValueMap; 183322313376a9ccac86cbfc208684d84936d62322dDevang Patel 184e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // For PHI nodes, the value available in OldPreHeader is just the 185e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // incoming value from OldPreHeader. 186e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (; PHINode *PN = dyn_cast<PHINode>(I); ++I) 187e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman ValueMap[PN] = PN->getIncomingValue(PN->getBasicBlockIndex(OrigPreHeader)); 188e98815469ccd2f1f1585abdc7c36042177bc26f0Devang Patel 189e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // For the rest of the instructions, create a clone in the OldPreHeader. 190e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman TerminatorInst *LoopEntryBranch = OrigPreHeader->getTerminator(); 191e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (; I != E; ++I) { 192e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman Instruction *C = I->clone(); 193e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman C->setName(I->getName()); 194e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman C->insertBefore(LoopEntryBranch); 195e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman ValueMap[I] = C; 196c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 197c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 198e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Along with all the other instructions, we just cloned OrigHeader's 199e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's 200e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // successors by duplicating their incoming values for OrigHeader. 201e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman TerminatorInst *TI = OrigHeader->getTerminator(); 202e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 203e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (BasicBlock::iterator BI = TI->getSuccessor(i)->begin(); 204e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman PHINode *PN = dyn_cast<PHINode>(BI); ++BI) 205e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreHeader); 206e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 207e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove 208e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // OrigPreHeader's old terminator (the original branch into the loop), and 209e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // remove the corresponding incoming values from the PHI nodes in OrigHeader. 210e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman LoopEntryBranch->eraseFromParent(); 211e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I) 212e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreHeader)); 213e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 214e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Now fix up users of the instructions in OrigHeader, insertting PHI nodes 215e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // as necessary. 216e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman SSAUpdater SSA; 217e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (I = OrigHeader->begin(); I != E; ++I) { 218e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman Value *OrigHeaderVal = I; 219e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman Value *OrigPreHeaderVal = ValueMap[OrigHeaderVal]; 220e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 221e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // The value now exits in two versions: the initial value in the preheader 222e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // and the loop "next" value in the original header. 223e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman SSA.Initialize(OrigHeaderVal); 224e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman SSA.AddAvailableValue(OrigHeader, OrigHeaderVal); 225e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman SSA.AddAvailableValue(OrigPreHeader, OrigPreHeaderVal); 226e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 227e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Visit each use of the OrigHeader instruction. 228e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (Value::use_iterator UI = OrigHeaderVal->use_begin(), 229e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman UE = OrigHeaderVal->use_end(); UI != UE; ) { 230e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Grab the use before incrementing the iterator. 231e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman Use &U = UI.getUse(); 232e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 233e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Increment the iterator before removing the use from the list. 234e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman ++UI; 235e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 236e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // SSAUpdater can't handle a non-PHI use in the same block as an 237e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // earlier def. We can easily handle those cases manually. 238e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman Instruction *UserInst = cast<Instruction>(U.getUser()); 239e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman if (!isa<PHINode>(UserInst)) { 240e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman BasicBlock *UserBB = UserInst->getParent(); 241e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 242e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // The original users in the OrigHeader are already using the 243e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // original definitions. 244e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman if (UserBB == OrigHeader) 24524a1c49172b7572652492ca986d49715ac1435eaDevang Patel continue; 24624a1c49172b7572652492ca986d49715ac1435eaDevang Patel 247e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Users in the OrigPreHeader need to use the value to which the 248e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // original definitions are mapped. 249e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman if (UserBB == OrigPreHeader) { 250e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman U = OrigPreHeaderVal; 251c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel continue; 252e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman } 253c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 254c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 255e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Anything else can be handled by SSAUpdater. 256e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman SSA.RewriteUse(U); 257c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 258c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 259c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 260e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // NewHeader is now the header of the loop. 261c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel L->moveToHeader(NewHeader); 262c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 2635464b96073626f811d79d56fa37be230552d2264Devang Patel preserveCanonicalLoopForm(LPM); 2645464b96073626f811d79d56fa37be230552d2264Devang Patel 265c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel NumRotated++; 266c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return true; 267c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel} 268c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 269c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel/// Initialize local data 270c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patelvoid LoopRotate::initialize() { 271c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel L = NULL; 272c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel OrigHeader = NULL; 273c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel OrigPreHeader = NULL; 274c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel NewHeader = NULL; 275c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel Exit = NULL; 276c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel} 2775464b96073626f811d79d56fa37be230552d2264Devang Patel 2785464b96073626f811d79d56fa37be230552d2264Devang Patel/// After loop rotation, loop pre-header has multiple sucessors. 2795464b96073626f811d79d56fa37be230552d2264Devang Patel/// Insert one forwarding basic block to ensure that loop pre-header 2805464b96073626f811d79d56fa37be230552d2264Devang Patel/// has only one successor. 2815464b96073626f811d79d56fa37be230552d2264Devang Patelvoid LoopRotate::preserveCanonicalLoopForm(LPPassManager &LPM) { 2825464b96073626f811d79d56fa37be230552d2264Devang Patel 2835464b96073626f811d79d56fa37be230552d2264Devang Patel // Right now original pre-header has two successors, new header and 2845464b96073626f811d79d56fa37be230552d2264Devang Patel // exit block. Insert new block between original pre-header and 2855464b96073626f811d79d56fa37be230552d2264Devang Patel // new header such that loop's new pre-header has only one successor. 2861d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *NewPreHeader = BasicBlock::Create(OrigHeader->getContext(), 2871d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson "bb.nph", 288b1dbcd886a4b5597a839f299054b78b33fb2d6dfGabor Greif OrigHeader->getParent(), 289051a950000e21935165db56695e35bade668193bGabor Greif NewHeader); 2905464b96073626f811d79d56fa37be230552d2264Devang Patel LoopInfo &LI = LPM.getAnalysis<LoopInfo>(); 2915464b96073626f811d79d56fa37be230552d2264Devang Patel if (Loop *PL = LI.getLoopFor(OrigPreHeader)) 292d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson PL->addBasicBlockToLoop(NewPreHeader, LI.getBase()); 293051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(NewHeader, NewPreHeader); 2945464b96073626f811d79d56fa37be230552d2264Devang Patel 2955464b96073626f811d79d56fa37be230552d2264Devang Patel BranchInst *OrigPH_BI = cast<BranchInst>(OrigPreHeader->getTerminator()); 2965464b96073626f811d79d56fa37be230552d2264Devang Patel if (OrigPH_BI->getSuccessor(0) == NewHeader) 2975464b96073626f811d79d56fa37be230552d2264Devang Patel OrigPH_BI->setSuccessor(0, NewPreHeader); 2985464b96073626f811d79d56fa37be230552d2264Devang Patel else { 2992ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(OrigPH_BI->getSuccessor(1) == NewHeader && 3002ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Unexpected original pre-header terminator"); 3015464b96073626f811d79d56fa37be230552d2264Devang Patel OrigPH_BI->setSuccessor(1, NewPreHeader); 3025464b96073626f811d79d56fa37be230552d2264Devang Patel } 3035464b96073626f811d79d56fa37be230552d2264Devang Patel 304cfb32203bceb0638db976fea5ce906b2a1010bacDan Gohman PHINode *PN; 305cfb32203bceb0638db976fea5ce906b2a1010bacDan Gohman for (BasicBlock::iterator I = NewHeader->begin(); 306cfb32203bceb0638db976fea5ce906b2a1010bacDan Gohman (PN = dyn_cast<PHINode>(I)); ++I) { 3075464b96073626f811d79d56fa37be230552d2264Devang Patel int index = PN->getBasicBlockIndex(OrigPreHeader); 3082ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(index != -1 && "Expected incoming value from Original PreHeader"); 3095464b96073626f811d79d56fa37be230552d2264Devang Patel PN->setIncomingBlock(index, NewPreHeader); 3102ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(PN->getBasicBlockIndex(OrigPreHeader) == -1 && 3112ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Expected only one incoming value from Original PreHeader"); 3125464b96073626f811d79d56fa37be230552d2264Devang Patel } 3135464b96073626f811d79d56fa37be230552d2264Devang Patel 3141465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>()) { 315990e866deb158fd88377b5606c8d86603e93e533Devang Patel DT->addNewBlock(NewPreHeader, OrigPreHeader); 316990e866deb158fd88377b5606c8d86603e93e533Devang Patel DT->changeImmediateDominator(L->getHeader(), NewPreHeader); 317990e866deb158fd88377b5606c8d86603e93e533Devang Patel DT->changeImmediateDominator(Exit, OrigPreHeader); 318990e866deb158fd88377b5606c8d86603e93e533Devang Patel for (Loop::block_iterator BI = L->block_begin(), BE = L->block_end(); 319990e866deb158fd88377b5606c8d86603e93e533Devang Patel BI != BE; ++BI) { 320990e866deb158fd88377b5606c8d86603e93e533Devang Patel BasicBlock *B = *BI; 321990e866deb158fd88377b5606c8d86603e93e533Devang Patel if (L->getHeader() != B) { 322990e866deb158fd88377b5606c8d86603e93e533Devang Patel DomTreeNode *Node = DT->getNode(B); 323990e866deb158fd88377b5606c8d86603e93e533Devang Patel if (Node && Node->getBlock() == OrigHeader) 324990e866deb158fd88377b5606c8d86603e93e533Devang Patel DT->changeImmediateDominator(*BI, L->getHeader()); 325990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 326990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 327990e866deb158fd88377b5606c8d86603e93e533Devang Patel DT->changeImmediateDominator(OrigHeader, OrigLatch); 328990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 329990e866deb158fd88377b5606c8d86603e93e533Devang Patel 3301465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands if (DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>()) { 331990e866deb158fd88377b5606c8d86603e93e533Devang Patel // New Preheader's dominance frontier is Exit block. 332990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::DomSetType NewPHSet; 333990e866deb158fd88377b5606c8d86603e93e533Devang Patel NewPHSet.insert(Exit); 334990e866deb158fd88377b5606c8d86603e93e533Devang Patel DF->addBasicBlock(NewPreHeader, NewPHSet); 335990e866deb158fd88377b5606c8d86603e93e533Devang Patel 336990e866deb158fd88377b5606c8d86603e93e533Devang Patel // New Header's dominance frontier now includes itself and Exit block 337990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::iterator HeadI = DF->find(L->getHeader()); 338990e866deb158fd88377b5606c8d86603e93e533Devang Patel if (HeadI != DF->end()) { 339990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::DomSetType & HeaderSet = HeadI->second; 340990e866deb158fd88377b5606c8d86603e93e533Devang Patel HeaderSet.clear(); 341990e866deb158fd88377b5606c8d86603e93e533Devang Patel HeaderSet.insert(L->getHeader()); 342990e866deb158fd88377b5606c8d86603e93e533Devang Patel HeaderSet.insert(Exit); 343990e866deb158fd88377b5606c8d86603e93e533Devang Patel } else { 344990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::DomSetType HeaderSet; 345990e866deb158fd88377b5606c8d86603e93e533Devang Patel HeaderSet.insert(L->getHeader()); 346990e866deb158fd88377b5606c8d86603e93e533Devang Patel HeaderSet.insert(Exit); 347990e866deb158fd88377b5606c8d86603e93e533Devang Patel DF->addBasicBlock(L->getHeader(), HeaderSet); 348990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 349990e866deb158fd88377b5606c8d86603e93e533Devang Patel 350990e866deb158fd88377b5606c8d86603e93e533Devang Patel // Original header (new Loop Latch)'s dominance frontier is Exit. 351990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::iterator LatchI = DF->find(L->getLoopLatch()); 352990e866deb158fd88377b5606c8d86603e93e533Devang Patel if (LatchI != DF->end()) { 353990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::DomSetType &LatchSet = LatchI->second; 354990e866deb158fd88377b5606c8d86603e93e533Devang Patel LatchSet = LatchI->second; 355990e866deb158fd88377b5606c8d86603e93e533Devang Patel LatchSet.clear(); 356990e866deb158fd88377b5606c8d86603e93e533Devang Patel LatchSet.insert(Exit); 357990e866deb158fd88377b5606c8d86603e93e533Devang Patel } else { 358990e866deb158fd88377b5606c8d86603e93e533Devang Patel DominanceFrontier::DomSetType LatchSet; 359990e866deb158fd88377b5606c8d86603e93e533Devang Patel LatchSet.insert(Exit); 360990e866deb158fd88377b5606c8d86603e93e533Devang Patel DF->addBasicBlock(L->getHeader(), LatchSet); 361990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 362990e866deb158fd88377b5606c8d86603e93e533Devang Patel 363b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel // If a loop block dominates new loop latch then add to its frontiers 364b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel // new header and Exit and remove new latch (which is equal to original 365b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel // header). 366990e866deb158fd88377b5606c8d86603e93e533Devang Patel BasicBlock *NewLatch = L->getLoopLatch(); 367b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel 368b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel assert(NewLatch == OrigHeader && "NewLatch is inequal to OrigHeader"); 369b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel 370b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>()) { 371b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel for (Loop::block_iterator BI = L->block_begin(), BE = L->block_end(); 372b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BI != BE; ++BI) { 373b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BasicBlock *B = *BI; 374b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel if (DT->dominates(B, NewLatch)) { 375b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel DominanceFrontier::iterator BDFI = DF->find(B); 376b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel if (BDFI != DF->end()) { 377b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel DominanceFrontier::DomSetType &BSet = BDFI->second; 378b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BSet.erase(NewLatch); 379b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BSet.insert(L->getHeader()); 380b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BSet.insert(Exit); 381b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel } else { 382b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel DominanceFrontier::DomSetType BSet; 383b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BSet.insert(L->getHeader()); 384b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel BSet.insert(Exit); 385b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel DF->addBasicBlock(B, BSet); 386b7f40c1a2a74fe9bd98cfab3d0ff139a8510fdfeDevang Patel } 387990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 388990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 389990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 390990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 391990e866deb158fd88377b5606c8d86603e93e533Devang Patel 392990e866deb158fd88377b5606c8d86603e93e533Devang Patel // Preserve canonical loop form, which means Exit block should 393990e866deb158fd88377b5606c8d86603e93e533Devang Patel // have only one predecessor. 394c292caf55c8f2794965542124d6571b5b59f0ba8Dan Gohman SplitEdge(L->getLoopLatch(), Exit, this); 395990e866deb158fd88377b5606c8d86603e93e533Devang Patel 3962ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(NewHeader && L->getHeader() == NewHeader && 3972ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Invalid loop header after loop rotation"); 3982ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(NewPreHeader && L->getLoopPreheader() == NewPreHeader && 3992ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Invalid loop preheader after loop rotation"); 4002ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(L->getLoopLatch() && 4012ba2543df26e15b67d27a449eb58429d62465200Chris Lattner "Invalid loop latch after loop rotation"); 4025464b96073626f811d79d56fa37be230552d2264Devang Patel} 403