LoopRotation.cpp revision c137120bb047a7017cbab21f5f9c9e6f65e2b84f
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" 173fc178ffdad0c3359f8e4bad084556a3054e1ed2Devang Patel#include "llvm/IntrinsicInst.h" 18d9e079706e782c5f054322a0d15f063a1a683230Chris Lattner#include "llvm/Analysis/CodeMetrics.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 // LCSSA form makes instruction renaming easier. 43c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel virtual void getAnalysisUsage(AnalysisUsage &AU) const { 441e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addPreserved<DominatorTree>(); 451e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addRequired<LoopInfo>(); 461e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addPreserved<LoopInfo>(); 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>(); 52c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 53c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 54a1ae0c74affb3672e75c6d9984dc092886f48454Chris Lattner bool runOnLoop(Loop *L, LPPassManager &LPM); 554aefc9bf1b963f2fe42f2de3341cd1eb5a9a0ce7Chris Lattner bool rotateLoop(Loop *L); 56c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 57c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel private: 58012ca949afc1e78c06dd49b8bc5f3b6f6c45458dChris Lattner LoopInfo *LI; 59c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel }; 60c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel} 61844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 62844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LoopRotate::ID = 0; 632ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(LoopRotate, "loop-rotate", "Rotate Loops", false, false) 642ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopInfo) 652ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopSimplify) 662ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LCSSA) 672ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(LoopRotate, "loop-rotate", "Rotate Loops", false, false) 68c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 69394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass *llvm::createLoopRotatePass() { return new LoopRotate(); } 70c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 71322313376a9ccac86cbfc208684d84936d62322dDevang Patel/// Rotate Loop L as many times as possible. Return true if 72cc4e605721e1144da8990edca64bf5799220e279Dan Gohman/// the loop is rotated at least once. 734aefc9bf1b963f2fe42f2de3341cd1eb5a9a0ce7Chris Lattnerbool LoopRotate::runOnLoop(Loop *L, LPPassManager &LPM) { 74012ca949afc1e78c06dd49b8bc5f3b6f6c45458dChris Lattner LI = &getAnalysis<LoopInfo>(); 75990e866deb158fd88377b5606c8d86603e93e533Devang Patel 76c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel // One loop can be rotated multiple times. 77012ca949afc1e78c06dd49b8bc5f3b6f6c45458dChris Lattner bool MadeChange = false; 784aefc9bf1b963f2fe42f2de3341cd1eb5a9a0ce7Chris Lattner while (rotateLoop(L)) 79012ca949afc1e78c06dd49b8bc5f3b6f6c45458dChris Lattner MadeChange = true; 80c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 81012ca949afc1e78c06dd49b8bc5f3b6f6c45458dChris Lattner return MadeChange; 82c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel} 83c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 8464c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner/// RewriteUsesOfClonedInstructions - We just cloned the instructions from the 8564c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner/// old header into the preheader. If there were uses of the values produced by 8664c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner/// these instruction that were outside of the loop, we have to insert PHI nodes 8764c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner/// to merge the two values. Do this now. 8864c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattnerstatic void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader, 8964c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner BasicBlock *OrigPreheader, 9064c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner ValueToValueMapTy &ValueMap) { 9164c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // Remove PHI node entries that are no longer live. 9264c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner BasicBlock::iterator I, E = OrigHeader->end(); 9364c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I) 9464c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader)); 9564c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner 9664c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // Now fix up users of the instructions in OrigHeader, inserting PHI nodes 9764c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // as necessary. 9864c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner SSAUpdater SSA; 9964c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner for (I = OrigHeader->begin(); I != E; ++I) { 10064c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner Value *OrigHeaderVal = I; 10164c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner 10264c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // If there are no uses of the value (e.g. because it returns void), there 10364c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // is nothing to rewrite. 10464c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner if (OrigHeaderVal->use_empty()) 10564c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner continue; 10664c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner 10764c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner Value *OrigPreHeaderVal = ValueMap[OrigHeaderVal]; 10864c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner 10964c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // The value now exits in two versions: the initial value in the preheader 11064c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // and the loop "next" value in the original header. 11164c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName()); 11264c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner SSA.AddAvailableValue(OrigHeader, OrigHeaderVal); 11364c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal); 11464c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner 11564c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // Visit each use of the OrigHeader instruction. 11664c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner for (Value::use_iterator UI = OrigHeaderVal->use_begin(), 11764c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner UE = OrigHeaderVal->use_end(); UI != UE; ) { 11864c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // Grab the use before incrementing the iterator. 11964c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner Use &U = UI.getUse(); 12064c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner 12164c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // Increment the iterator before removing the use from the list. 12264c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner ++UI; 12364c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner 12464c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // SSAUpdater can't handle a non-PHI use in the same block as an 12564c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // earlier def. We can easily handle those cases manually. 12664c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner Instruction *UserInst = cast<Instruction>(U.getUser()); 12764c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner if (!isa<PHINode>(UserInst)) { 12864c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner BasicBlock *UserBB = UserInst->getParent(); 12964c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner 13064c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // The original users in the OrigHeader are already using the 13164c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // original definitions. 13264c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner if (UserBB == OrigHeader) 13364c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner continue; 13464c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner 13564c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // Users in the OrigPreHeader need to use the value to which the 13664c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // original definitions are mapped. 13764c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner if (UserBB == OrigPreheader) { 13864c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner U = OrigPreHeaderVal; 13964c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner continue; 14064c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner } 14164c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner } 14264c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner 14364c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // Anything else can be handled by SSAUpdater. 14464c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner SSA.RewriteUse(U); 14564c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner } 14664c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner } 14764c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner} 14864c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner 14923d9d27c265753da55a8ee7879820acb4d1e3a6dDan Gohman/// Rotate loop LP. Return true if the loop is rotated. 1504aefc9bf1b963f2fe42f2de3341cd1eb5a9a0ce7Chris Lattnerbool LoopRotate::rotateLoop(Loop *L) { 151cc4e605721e1144da8990edca64bf5799220e279Dan Gohman // If the loop has only one block then there is not much to rotate. 152322313376a9ccac86cbfc208684d84936d62322dDevang Patel if (L->getBlocks().size() == 1) 153c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return false; 1542aa69082310f48162cb732efdc41613391796cd7Chris Lattner 1552aa69082310f48162cb732efdc41613391796cd7Chris Lattner BasicBlock *OrigHeader = L->getHeader(); 1562aa69082310f48162cb732efdc41613391796cd7Chris Lattner 1572aa69082310f48162cb732efdc41613391796cd7Chris Lattner BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator()); 1582aa69082310f48162cb732efdc41613391796cd7Chris Lattner if (BI == 0 || BI->isUnconditional()) 1592aa69082310f48162cb732efdc41613391796cd7Chris Lattner return false; 1602aa69082310f48162cb732efdc41613391796cd7Chris Lattner 161cc4e605721e1144da8990edca64bf5799220e279Dan Gohman // If the loop header is not one of the loop exiting blocks then 162cc4e605721e1144da8990edca64bf5799220e279Dan Gohman // either this loop is already rotated or it is not 163c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel // suitable for loop rotation transformations. 16432663b719b4996b3a735f22bba80d771d50f96e7Dan Gohman if (!L->isLoopExiting(OrigHeader)) 165c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return false; 166c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 167322313376a9ccac86cbfc208684d84936d62322dDevang Patel // Updating PHInodes in loops with multiple exits adds complexity. 168322313376a9ccac86cbfc208684d84936d62322dDevang Patel // Keep it simple, and restrict loop rotation to loops with one exit only. 169322313376a9ccac86cbfc208684d84936d62322dDevang Patel // In future, lift this restriction and support for multiple exits if 170322313376a9ccac86cbfc208684d84936d62322dDevang Patel // required. 171b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 172c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel L->getExitBlocks(ExitBlocks); 173c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel if (ExitBlocks.size() > 1) 174c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel return false; 175c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 176d9e079706e782c5f054322a0d15f063a1a683230Chris Lattner // Check size of original header and reject loop if it is very big. 177d9e079706e782c5f054322a0d15f063a1a683230Chris Lattner { 178d9e079706e782c5f054322a0d15f063a1a683230Chris Lattner CodeMetrics Metrics; 179d9e079706e782c5f054322a0d15f063a1a683230Chris Lattner Metrics.analyzeBasicBlock(OrigHeader); 180d9e079706e782c5f054322a0d15f063a1a683230Chris Lattner if (Metrics.NumInsts > MAX_HEADER_SIZE) 181d9e079706e782c5f054322a0d15f063a1a683230Chris Lattner return false; 1823f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel } 1833f43a7021fae71c056f5e1afc60016cfd8193f68Devang Patel 184990e866deb158fd88377b5606c8d86603e93e533Devang Patel // Now, this loop is suitable for rotation. 18564c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner BasicBlock *OrigPreheader = L->getLoopPreheader(); 1862aa69082310f48162cb732efdc41613391796cd7Chris Lattner BasicBlock *OrigLatch = L->getLoopLatch(); 187f5bf464b701908d16f7cee0bbf2b8c8df4f3a917Chris Lattner 188f5bf464b701908d16f7cee0bbf2b8c8df4f3a917Chris Lattner // If the loop could not be converted to canonical form, it must have an 189f5bf464b701908d16f7cee0bbf2b8c8df4f3a917Chris Lattner // indirectbr in it, just give up. 190f5bf464b701908d16f7cee0bbf2b8c8df4f3a917Chris Lattner if (OrigPreheader == 0 || OrigLatch == 0) 191f5bf464b701908d16f7cee0bbf2b8c8df4f3a917Chris Lattner return false; 192990e866deb158fd88377b5606c8d86603e93e533Devang Patel 193e6fe67b2fb48b1f0f3c1ac8c1ce01e67c1f0bb1dDan Gohman // Anything ScalarEvolution may know about this loop or the PHI nodes 194e6fe67b2fb48b1f0f3c1ac8c1ce01e67c1f0bb1dDan Gohman // in its header will soon be invalidated. 195e6fe67b2fb48b1f0f3c1ac8c1ce01e67c1f0bb1dDan Gohman if (ScalarEvolution *SE = getAnalysisIfAvailable<ScalarEvolution>()) 1964c7279ac726e338400626fca5a09b5533426eb6aDan Gohman SE->forgetLoop(L); 197e6fe67b2fb48b1f0f3c1ac8c1ce01e67c1f0bb1dDan Gohman 198c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel // Find new Loop header. NewHeader is a Header's one and only successor 199f6784a326293941cd4ff6d25da64732760e993f3Chris Lattner // that is inside loop. Header's other successor is outside the 200f6784a326293941cd4ff6d25da64732760e993f3Chris Lattner // loop. Otherwise loop is not suitable for rotation. 2014aefc9bf1b963f2fe42f2de3341cd1eb5a9a0ce7Chris Lattner BasicBlock *Exit = BI->getSuccessor(0); 2024aefc9bf1b963f2fe42f2de3341cd1eb5a9a0ce7Chris Lattner BasicBlock *NewHeader = BI->getSuccessor(1); 203322313376a9ccac86cbfc208684d84936d62322dDevang Patel if (L->contains(Exit)) 204322313376a9ccac86cbfc208684d84936d62322dDevang Patel std::swap(Exit, NewHeader); 2052ba2543df26e15b67d27a449eb58429d62465200Chris Lattner assert(NewHeader && "Unable to determine new loop header"); 206322313376a9ccac86cbfc208684d84936d62322dDevang Patel assert(L->contains(NewHeader) && !L->contains(Exit) && 207322313376a9ccac86cbfc208684d84936d62322dDevang Patel "Unable to determine loop header and exit blocks"); 2083796a262c50e0b04c1a5a9571f12bb9bc4936c25Chris Lattner 209cc4e605721e1144da8990edca64bf5799220e279Dan Gohman // This code assumes that the new header has exactly one predecessor. 210cc4e605721e1144da8990edca64bf5799220e279Dan Gohman // Remove any single-entry PHI nodes in it. 2113796a262c50e0b04c1a5a9571f12bb9bc4936c25Chris Lattner assert(NewHeader->getSinglePredecessor() && 2123796a262c50e0b04c1a5a9571f12bb9bc4936c25Chris Lattner "New header doesn't have one pred!"); 2133796a262c50e0b04c1a5a9571f12bb9bc4936c25Chris Lattner FoldSingleEntryPHINodes(NewHeader); 214c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 215e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Begin by walking OrigHeader and populating ValueMap with an entry for 216e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // each Instruction. 217322313376a9ccac86cbfc208684d84936d62322dDevang Patel BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end(); 2186ccb3652933bcdede2b2a53cf76ddd56ce9592a2Chris Lattner ValueToValueMapTy ValueMap; 219322313376a9ccac86cbfc208684d84936d62322dDevang Patel 220e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // For PHI nodes, the value available in OldPreHeader is just the 221e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // incoming value from OldPreHeader. 222e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (; PHINode *PN = dyn_cast<PHINode>(I); ++I) 223c137120bb047a7017cbab21f5f9c9e6f65e2b84fJay Foad ValueMap[PN] = PN->getIncomingValueForBlock(OrigPreheader); 224e98815469ccd2f1f1585abdc7c36042177bc26f0Devang Patel 22550fb46983ccae116bdbda64471f4861108766135Chris Lattner // For the rest of the instructions, either hoist to the OrigPreheader if 22650fb46983ccae116bdbda64471f4861108766135Chris Lattner // possible or create a clone in the OldPreHeader if not. 22764c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner TerminatorInst *LoopEntryBranch = OrigPreheader->getTerminator(); 22850fb46983ccae116bdbda64471f4861108766135Chris Lattner while (I != E) { 22950fb46983ccae116bdbda64471f4861108766135Chris Lattner Instruction *Inst = I++; 23050fb46983ccae116bdbda64471f4861108766135Chris Lattner 23150fb46983ccae116bdbda64471f4861108766135Chris Lattner // If the instruction's operands are invariant and it doesn't read or write 23250fb46983ccae116bdbda64471f4861108766135Chris Lattner // memory, then it is safe to hoist. Doing this doesn't change the order of 23350fb46983ccae116bdbda64471f4861108766135Chris Lattner // execution in the preheader, but does prevent the instruction from 23450fb46983ccae116bdbda64471f4861108766135Chris Lattner // executing in each iteration of the loop. This means it is safe to hoist 23550fb46983ccae116bdbda64471f4861108766135Chris Lattner // something that might trap, but isn't safe to hoist something that reads 23650fb46983ccae116bdbda64471f4861108766135Chris Lattner // memory (without proving that the loop doesn't write). 23750fb46983ccae116bdbda64471f4861108766135Chris Lattner if (L->hasLoopInvariantOperands(Inst) && 23850fb46983ccae116bdbda64471f4861108766135Chris Lattner !Inst->mayReadFromMemory() && !Inst->mayWriteToMemory() && 2393fc178ffdad0c3359f8e4bad084556a3054e1ed2Devang Patel !isa<TerminatorInst>(Inst) && !isa<DbgInfoIntrinsic>(Inst)) { 24050fb46983ccae116bdbda64471f4861108766135Chris Lattner Inst->moveBefore(LoopEntryBranch); 24150fb46983ccae116bdbda64471f4861108766135Chris Lattner continue; 24250fb46983ccae116bdbda64471f4861108766135Chris Lattner } 24350fb46983ccae116bdbda64471f4861108766135Chris Lattner 24450fb46983ccae116bdbda64471f4861108766135Chris Lattner // Otherwise, create a duplicate of the instruction. 24550fb46983ccae116bdbda64471f4861108766135Chris Lattner Instruction *C = Inst->clone(); 246b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner 247d9ec3572f3d0997348361334446f942194522127Chris Lattner // Eagerly remap the operands of the instruction. 248d9ec3572f3d0997348361334446f942194522127Chris Lattner RemapInstruction(C, ValueMap, 249d9ec3572f3d0997348361334446f942194522127Chris Lattner RF_NoModuleLevelChanges|RF_IgnoreMissingEntries); 250d9ec3572f3d0997348361334446f942194522127Chris Lattner 251d9ec3572f3d0997348361334446f942194522127Chris Lattner // With the operands remapped, see if the instruction constant folds or is 252d9ec3572f3d0997348361334446f942194522127Chris Lattner // otherwise simplifyable. This commonly occurs because the entry from PHI 253d9ec3572f3d0997348361334446f942194522127Chris Lattner // nodes allows icmps and other instructions to fold. 254012ca949afc1e78c06dd49b8bc5f3b6f6c45458dChris Lattner Value *V = SimplifyInstruction(C); 255012ca949afc1e78c06dd49b8bc5f3b6f6c45458dChris Lattner if (V && LI->replacementPreservesLCSSAForm(C, V)) { 256d9ec3572f3d0997348361334446f942194522127Chris Lattner // If so, then delete the temporary instruction and stick the folded value 257d9ec3572f3d0997348361334446f942194522127Chris Lattner // in the map. 258d9ec3572f3d0997348361334446f942194522127Chris Lattner delete C; 259d9ec3572f3d0997348361334446f942194522127Chris Lattner ValueMap[Inst] = V; 260d9ec3572f3d0997348361334446f942194522127Chris Lattner } else { 261d9ec3572f3d0997348361334446f942194522127Chris Lattner // Otherwise, stick the new instruction into the new block! 262d9ec3572f3d0997348361334446f942194522127Chris Lattner C->setName(Inst->getName()); 263d9ec3572f3d0997348361334446f942194522127Chris Lattner C->insertBefore(LoopEntryBranch); 264d9ec3572f3d0997348361334446f942194522127Chris Lattner ValueMap[Inst] = C; 265d9ec3572f3d0997348361334446f942194522127Chris Lattner } 266c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel } 267c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 268e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Along with all the other instructions, we just cloned OrigHeader's 269e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's 270e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // successors by duplicating their incoming values for OrigHeader. 271e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman TerminatorInst *TI = OrigHeader->getTerminator(); 272e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 273e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman for (BasicBlock::iterator BI = TI->getSuccessor(i)->begin(); 274e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman PHINode *PN = dyn_cast<PHINode>(BI); ++BI) 27564c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreheader); 276e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 277e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove 278e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // OrigPreHeader's old terminator (the original branch into the loop), and 279e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // remove the corresponding incoming values from the PHI nodes in OrigHeader. 280e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman LoopEntryBranch->eraseFromParent(); 281e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman 28264c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // If there were any uses of instructions in the duplicated block outside the 28364c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner // loop, update them, inserting PHI nodes as required 28464c24db959815c6b7edbebd32e5a16936d75b2e1Chris Lattner RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap); 285c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 286e6e37b94e86acfa33e687a6284079d0adb0c8c4aDan Gohman // NewHeader is now the header of the loop. 287c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel L->moveToHeader(NewHeader); 288883401a72f03286cb51d08bf1c894c7d7eb58a31Chris Lattner assert(L->getHeader() == NewHeader && "Latch block is our new header"); 289c4625da483ff9e835aef886864e37dd68fb7a03cDevang Patel 2905d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner 2915d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // At this point, we've finished our major CFG changes. As part of cloning 2925d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // the loop into the preheader we've simplified instructions and the 2935d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // duplicated conditional branch may now be branching on a constant. If it is 2945d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // branching on a constant and if that constant means that we enter the loop, 2955d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // then we fold away the cond branch to an uncond branch. This simplifies the 2965d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // loop in cases important for nested loops, and it also means we don't have 2975d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // to split as many edges. 2985d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner BranchInst *PHBI = cast<BranchInst>(OrigPreheader->getTerminator()); 2995d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner assert(PHBI->isConditional() && "Should be clone of BI condbr!"); 3005d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner if (!isa<ConstantInt>(PHBI->getCondition()) || 3015d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner PHBI->getSuccessor(cast<ConstantInt>(PHBI->getCondition())->isZero()) 3025d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner != NewHeader) { 3035d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // The conditional branch can't be folded, handle the general case. 3045d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // Update DominatorTree to reflect the CFG change we just made. Then split 3055d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // edges as necessary to preserve LoopSimplify form. 3065d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>()) { 3075d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // Since OrigPreheader now has the conditional branch to Exit block, it is 3085d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // the dominator of Exit. 3095d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner DT->changeImmediateDominator(Exit, OrigPreheader); 3105d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner DT->changeImmediateDominator(NewHeader, OrigPreheader); 3115d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner 3125d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // Update OrigHeader to be dominated by the new header block. 3135d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner DT->changeImmediateDominator(OrigHeader, OrigLatch); 3145d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner } 3155d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner 3165d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // Right now OrigPreHeader has two successors, NewHeader and ExitBlock, and 3175d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // thus is not a preheader anymore. Split the edge to form a real preheader. 3185d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner BasicBlock *NewPH = SplitCriticalEdge(OrigPreheader, NewHeader, this); 3195d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner NewPH->setName(NewHeader->getName() + ".lr.ph"); 3200e4a1543aba1364fe4a1eacee46b6d08d4611506Chris Lattner 3215d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // Preserve canonical loop form, which means that 'Exit' should have only one 3225d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // predecessor. 3235d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner BasicBlock *ExitSplit = SplitCriticalEdge(L->getLoopLatch(), Exit, this); 3245d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner ExitSplit->moveBefore(Exit); 3255d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner } else { 3265d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // We can fold the conditional branch in the preheader, this makes things 3275d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // simpler. The first step is to remove the extra edge to the Exit block. 3285d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner Exit->removePredecessor(OrigPreheader, true /*preserve LCSSA*/); 329bd5426a4f263eca7893fc54775d6cd86e729e100Devang Patel BranchInst *NewBI = BranchInst::Create(NewHeader, PHBI); 330bd5426a4f263eca7893fc54775d6cd86e729e100Devang Patel NewBI->setDebugLoc(PHBI->getDebugLoc()); 3315d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner PHBI->eraseFromParent(); 3325d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner 3335d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // With our CFG finalized, update DomTree if it is available. 3345d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>()) { 3355d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner // Update OrigHeader to be dominated by the new header block. 3365d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner DT->changeImmediateDominator(NewHeader, OrigPreheader); 3375d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner DT->changeImmediateDominator(OrigHeader, OrigLatch); 3385d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner } 339990e866deb158fd88377b5606c8d86603e93e533Devang Patel } 3400e4a1543aba1364fe4a1eacee46b6d08d4611506Chris Lattner 3415d37370a6ff255293d0b97abf9e8b3d46ed17238Chris Lattner assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation"); 3420e4a1543aba1364fe4a1eacee46b6d08d4611506Chris Lattner assert(L->getLoopLatch() && "Invalid loop latch after loop rotation"); 343a1ae0c74affb3672e75c6d9984dc092886f48454Chris Lattner 34493767fdb61dfff6ab13056b2a73209998ae4e786Chris Lattner // Now that the CFG and DomTree are in a consistent state again, try to merge 34593767fdb61dfff6ab13056b2a73209998ae4e786Chris Lattner // the OrigHeader block into OrigLatch. This will succeed if they are 34693767fdb61dfff6ab13056b2a73209998ae4e786Chris Lattner // connected by an unconditional branch. This is just a cleanup so the 34793767fdb61dfff6ab13056b2a73209998ae4e786Chris Lattner // emitted code isn't too gross in this common case. 34893767fdb61dfff6ab13056b2a73209998ae4e786Chris Lattner MergeBlockIntoPredecessor(OrigHeader, this); 349a1ae0c74affb3672e75c6d9984dc092886f48454Chris Lattner 350a1ae0c74affb3672e75c6d9984dc092886f48454Chris Lattner ++NumRotated; 351a1ae0c74affb3672e75c6d9984dc092886f48454Chris Lattner return true; 3525464b96073626f811d79d56fa37be230552d2264Devang Patel} 353a1ae0c74affb3672e75c6d9984dc092886f48454Chris Lattner 354