Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 1 | //===- LoopRotation.cpp - Loop Rotation Pass ------------------------------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements Loop Rotation Pass. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 14 | #define DEBUG_TYPE "loop-rotate" |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 15 | |
| 16 | #include "llvm/Transforms/Scalar.h" |
| 17 | #include "llvm/Function.h" |
| 18 | #include "llvm/Instructions.h" |
| 19 | #include "llvm/Analysis/LoopInfo.h" |
| 20 | #include "llvm/Analysis/LoopPass.h" |
Devang Patel | 990e866 | 2007-07-11 23:47:28 +0000 | [diff] [blame] | 21 | #include "llvm/Analysis/Dominators.h" |
| 22 | #include "llvm/Analysis/ScalarEvolution.h" |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 23 | #include "llvm/Transforms/Utils/Local.h" |
Devang Patel | 990e866 | 2007-07-11 23:47:28 +0000 | [diff] [blame] | 24 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 25 | #include "llvm/Support/CommandLine.h" |
| 26 | #include "llvm/Support/Debug.h" |
| 27 | #include "llvm/ADT/Statistic.h" |
| 28 | #include "llvm/ADT/SmallVector.h" |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 29 | |
| 30 | using namespace llvm; |
| 31 | |
| 32 | #define MAX_HEADER_SIZE 16 |
| 33 | |
| 34 | STATISTIC(NumRotated, "Number of loops rotated"); |
| 35 | namespace { |
| 36 | |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 37 | class VISIBILITY_HIDDEN RenameData { |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 38 | public: |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 39 | RenameData(Instruction *O, Value *P, Instruction *H) |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 40 | : Original(O), PreHeader(P), Header(H) { } |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 41 | public: |
| 42 | Instruction *Original; // Original instruction |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 43 | Value *PreHeader; // Original pre-header replacement |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 44 | Instruction *Header; // New header replacement |
| 45 | }; |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 46 | |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 47 | class VISIBILITY_HIDDEN LoopRotate : public LoopPass { |
| 48 | |
| 49 | public: |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 50 | static char ID; // Pass ID, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 51 | LoopRotate() : LoopPass((intptr_t)&ID) {} |
| 52 | |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 53 | // Rotate Loop L as many times as possible. Return true if |
| 54 | // loop is rotated at least once. |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 55 | bool runOnLoop(Loop *L, LPPassManager &LPM); |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 56 | |
| 57 | // LCSSA form makes instruction renaming easier. |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 58 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Devang Patel | 9d9b204 | 2008-02-15 01:24:49 +0000 | [diff] [blame] | 59 | AU.addRequiredID(LoopSimplifyID); |
| 60 | AU.addPreservedID(LoopSimplifyID); |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 61 | AU.addRequiredID(LCSSAID); |
| 62 | AU.addPreservedID(LCSSAID); |
Devang Patel | 990e866 | 2007-07-11 23:47:28 +0000 | [diff] [blame] | 63 | AU.addPreserved<ScalarEvolution>(); |
| 64 | AU.addPreserved<LoopInfo>(); |
Devang Patel | d9a6dcb | 2007-07-30 20:22:53 +0000 | [diff] [blame] | 65 | AU.addPreserved<DominatorTree>(); |
| 66 | AU.addPreserved<DominanceFrontier>(); |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 67 | } |
| 68 | |
| 69 | // Helper functions |
| 70 | |
| 71 | /// Do actual work |
| 72 | bool rotateLoop(Loop *L, LPPassManager &LPM); |
| 73 | |
| 74 | /// Initialize local data |
| 75 | void initialize(); |
| 76 | |
| 77 | /// Make sure all Exit block PHINodes have required incoming values. |
| 78 | /// If incoming value is constant or defined outside the loop then |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 79 | /// PHINode may not have an entry for original pre-header. |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 80 | void updateExitBlock(); |
| 81 | |
| 82 | /// Return true if this instruction is used outside original header. |
| 83 | bool usedOutsideOriginalHeader(Instruction *In); |
| 84 | |
| 85 | /// Find Replacement information for instruction. Return NULL if it is |
| 86 | /// not available. |
Devang Patel | 4522c8a | 2007-04-09 17:09:13 +0000 | [diff] [blame] | 87 | const RenameData *findReplacementData(Instruction *I); |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 88 | |
Devang Patel | 5464b96 | 2007-04-09 20:19:46 +0000 | [diff] [blame] | 89 | /// After loop rotation, loop pre-header has multiple sucessors. |
| 90 | /// Insert one forwarding basic block to ensure that loop pre-header |
| 91 | /// has only one successor. |
| 92 | void preserveCanonicalLoopForm(LPPassManager &LPM); |
| 93 | |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 94 | private: |
| 95 | |
| 96 | Loop *L; |
| 97 | BasicBlock *OrigHeader; |
| 98 | BasicBlock *OrigPreHeader; |
| 99 | BasicBlock *OrigLatch; |
| 100 | BasicBlock *NewHeader; |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 101 | BasicBlock *Exit; |
Devang Patel | 990e866 | 2007-07-11 23:47:28 +0000 | [diff] [blame] | 102 | LPPassManager *LPM_Ptr; |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 103 | SmallVector<RenameData, MAX_HEADER_SIZE> LoopHeaderInfo; |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 104 | }; |
| 105 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 106 | char LoopRotate::ID = 0; |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 107 | RegisterPass<LoopRotate> X ("loop-rotate", "Rotate Loops"); |
| 108 | } |
| 109 | |
| 110 | LoopPass *llvm::createLoopRotatePass() { return new LoopRotate(); } |
| 111 | |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 112 | /// Rotate Loop L as many times as possible. Return true if |
| 113 | /// loop is rotated at least once. |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 114 | bool LoopRotate::runOnLoop(Loop *Lp, LPPassManager &LPM) { |
Devang Patel | 990e866 | 2007-07-11 23:47:28 +0000 | [diff] [blame] | 115 | |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 116 | bool RotatedOneLoop = false; |
| 117 | initialize(); |
Devang Patel | 990e866 | 2007-07-11 23:47:28 +0000 | [diff] [blame] | 118 | LPM_Ptr = &LPM; |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 119 | |
| 120 | // One loop can be rotated multiple times. |
| 121 | while (rotateLoop(Lp,LPM)) { |
| 122 | RotatedOneLoop = true; |
| 123 | initialize(); |
| 124 | } |
| 125 | |
| 126 | return RotatedOneLoop; |
| 127 | } |
| 128 | |
Dan Gohman | 23d9d27 | 2007-05-11 21:10:54 +0000 | [diff] [blame] | 129 | /// Rotate loop LP. Return true if the loop is rotated. |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 130 | bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) { |
| 131 | |
| 132 | L = Lp; |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 133 | |
| 134 | OrigHeader = L->getHeader(); |
| 135 | OrigPreHeader = L->getLoopPreheader(); |
| 136 | OrigLatch = L->getLoopLatch(); |
| 137 | |
| 138 | // If loop has only one block then there is not much to rotate. |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 139 | if (L->getBlocks().size() == 1) |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 140 | return false; |
| 141 | |
Devang Patel | 5464b96 | 2007-04-09 20:19:46 +0000 | [diff] [blame] | 142 | assert (OrigHeader && OrigLatch && OrigPreHeader && |
Dan Gohman | 23d9d27 | 2007-05-11 21:10:54 +0000 | [diff] [blame] | 143 | "Loop is not in canonical form"); |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 144 | |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 145 | // If loop header is not one of the loop exit block then |
| 146 | // either this loop is already rotated or it is not |
| 147 | // suitable for loop rotation transformations. |
| 148 | if (!L->isLoopExit(OrigHeader)) |
| 149 | return false; |
| 150 | |
| 151 | BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator()); |
| 152 | if (!BI) |
| 153 | return false; |
Nick Lewycky | 79a2c4f | 2007-11-21 05:21:54 +0000 | [diff] [blame] | 154 | assert (BI->isConditional() && "Branch Instruction is not conditional"); |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 155 | |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 156 | // Updating PHInodes in loops with multiple exits adds complexity. |
| 157 | // Keep it simple, and restrict loop rotation to loops with one exit only. |
| 158 | // In future, lift this restriction and support for multiple exits if |
| 159 | // required. |
Devang Patel | b7211a2 | 2007-08-21 00:31:24 +0000 | [diff] [blame] | 160 | SmallVector<BasicBlock*, 8> ExitBlocks; |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 161 | L->getExitBlocks(ExitBlocks); |
| 162 | if (ExitBlocks.size() > 1) |
| 163 | return false; |
| 164 | |
Devang Patel | 990e866 | 2007-07-11 23:47:28 +0000 | [diff] [blame] | 165 | // Check size of original header and reject |
| 166 | // loop if it is very big. |
| 167 | if (OrigHeader->getInstList().size() > MAX_HEADER_SIZE) |
| 168 | return false; |
| 169 | |
| 170 | // Now, this loop is suitable for rotation. |
| 171 | |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 172 | // Find new Loop header. NewHeader is a Header's one and only successor |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 173 | // that is inside loop. Header's other successor is out side the |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 174 | // loop. Otherwise loop is not suitable for rotation. |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 175 | Exit = BI->getSuccessor(0); |
| 176 | NewHeader = BI->getSuccessor(1); |
| 177 | if (L->contains(Exit)) |
| 178 | std::swap(Exit, NewHeader); |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 179 | assert (NewHeader && "Unable to determine new loop header"); |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 180 | assert(L->contains(NewHeader) && !L->contains(Exit) && |
| 181 | "Unable to determine loop header and exit blocks"); |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 182 | |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 183 | // Copy PHI nodes and other instructions from original header |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 184 | // into original pre-header. Unlike original header, original pre-header is |
| 185 | // not a member of loop. |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 186 | // |
| 187 | // New loop header is one and only successor of original header that |
| 188 | // is inside the loop. All other original header successors are outside |
| 189 | // the loop. Copy PHI Nodes from original header into new loop header. |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 190 | // Add second incoming value, from original loop pre-header into these phi |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 191 | // nodes. If a value defined in original header is used outside original |
| 192 | // header then new loop header will need new phi nodes with two incoming |
| 193 | // values, one definition from original header and second definition is |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 194 | // from original loop pre-header. |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 195 | |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 196 | // Remove terminator from Original pre-header. Original pre-header will |
| 197 | // receive a clone of original header terminator as a new terminator. |
| 198 | OrigPreHeader->getInstList().pop_back(); |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 199 | BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end(); |
Devang Patel | 4522c8a | 2007-04-09 17:09:13 +0000 | [diff] [blame] | 200 | PHINode *PN = NULL; |
| 201 | for (; (PN = dyn_cast<PHINode>(I)); ++I) { |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 202 | Instruction *In = I; |
| 203 | |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 204 | // PHI nodes are not copied into original pre-header. Instead their values |
| 205 | // are directly propagated. |
| 206 | Value * NPV = PN->getIncomingValueForBlock(OrigPreHeader); |
| 207 | |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 208 | // Create new PHI node with two incoming values for NewHeader. |
| 209 | // One incoming value is from OrigLatch (through OrigHeader) and |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 210 | // second incoming value is from original pre-header. |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame^] | 211 | PHINode *NH = PHINode::Create(In->getType(), In->getName()); |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 212 | NH->addIncoming(PN->getIncomingValueForBlock(OrigLatch), OrigHeader); |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 213 | NH->addIncoming(NPV, OrigPreHeader); |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 214 | NewHeader->getInstList().push_front(NH); |
| 215 | |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 216 | // "In" can be replaced by NH at various places. |
| 217 | LoopHeaderInfo.push_back(RenameData(In, NPV, NH)); |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 218 | } |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 219 | |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 220 | // Now, handle non-phi instructions. |
| 221 | for (; I != E; ++I) { |
| 222 | Instruction *In = I; |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 223 | |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 224 | assert (!isa<PHINode>(In) && "PHINode is not expected here"); |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 225 | // This is not a PHI instruction. Insert its clone into original pre-header. |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 226 | // If this instruction is using a value from same basic block then |
| 227 | // update it to use value from cloned instruction. |
| 228 | Instruction *C = In->clone(); |
| 229 | C->setName(In->getName()); |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 230 | OrigPreHeader->getInstList().push_back(C); |
| 231 | |
| 232 | for (unsigned opi = 0, e = In->getNumOperands(); opi != e; ++opi) { |
| 233 | if (Instruction *OpPhi = dyn_cast<PHINode>(In->getOperand(opi))) { |
| 234 | if (const RenameData *D = findReplacementData(OpPhi)) { |
| 235 | // This is using values from original header PHI node. |
| 236 | // Here, directly used incoming value from original pre-header. |
| 237 | C->setOperand(opi, D->PreHeader); |
| 238 | } |
| 239 | } |
| 240 | else if (Instruction *OpInsn = |
| 241 | dyn_cast<Instruction>(In->getOperand(opi))) { |
| 242 | if (const RenameData *D = findReplacementData(OpInsn)) |
| 243 | C->setOperand(opi, D->PreHeader); |
| 244 | } |
| 245 | } |
| 246 | |
| 247 | |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 248 | // If this instruction is used outside this basic block then |
| 249 | // create new PHINode for this instruction. |
| 250 | Instruction *NewHeaderReplacement = NULL; |
| 251 | if (usedOutsideOriginalHeader(In)) { |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame^] | 252 | PHINode *PN = PHINode::Create(In->getType(), In->getName()); |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 253 | PN->addIncoming(In, OrigHeader); |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 254 | PN->addIncoming(C, OrigPreHeader); |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 255 | NewHeader->getInstList().push_front(PN); |
| 256 | NewHeaderReplacement = PN; |
| 257 | } |
| 258 | |
| 259 | // "In" can be replaced by NPH or NH at various places. |
| 260 | LoopHeaderInfo.push_back(RenameData(In, C, NewHeaderReplacement)); |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 261 | } |
| 262 | |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 263 | // Rename uses of original header instructions to reflect their new |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 264 | // definitions (either from original pre-header node or from newly created |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 265 | // new header PHINodes. |
| 266 | // |
| 267 | // Original header instructions are used in |
| 268 | // 1) Original header: |
| 269 | // |
| 270 | // If instruction is used in non-phi instructions then it is using |
| 271 | // defintion from original heder iteself. Do not replace this use |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 272 | // with definition from new header or original pre-header. |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 273 | // |
| 274 | // If instruction is used in phi node then it is an incoming |
| 275 | // value. Rename its use to reflect new definition from new-preheader |
| 276 | // or new header. |
| 277 | // |
| 278 | // 2) Inside loop but not in original header |
| 279 | // |
| 280 | // Replace this use to reflect definition from new header. |
Devang Patel | 4522c8a | 2007-04-09 17:09:13 +0000 | [diff] [blame] | 281 | for(unsigned LHI = 0, LHI_E = LoopHeaderInfo.size(); LHI != LHI_E; ++LHI) { |
| 282 | const RenameData &ILoopHeaderInfo = LoopHeaderInfo[LHI]; |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 283 | |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 284 | if (!ILoopHeaderInfo.Header) |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 285 | continue; |
| 286 | |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 287 | Instruction *OldPhi = ILoopHeaderInfo.Original; |
| 288 | Instruction *NewPhi = ILoopHeaderInfo.Header; |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 289 | |
| 290 | // Before replacing uses, collect them first, so that iterator is |
| 291 | // not invalidated. |
| 292 | SmallVector<Instruction *, 16> AllUses; |
| 293 | for (Value::use_iterator UI = OldPhi->use_begin(), UE = OldPhi->use_end(); |
Devang Patel | 24a1c49 | 2007-04-09 16:21:29 +0000 | [diff] [blame] | 294 | UI != UE; ++UI) { |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 295 | Instruction *U = cast<Instruction>(UI); |
| 296 | AllUses.push_back(U); |
| 297 | } |
| 298 | |
| 299 | for (SmallVector<Instruction *, 16>::iterator UI = AllUses.begin(), |
| 300 | UE = AllUses.end(); UI != UE; ++UI) { |
| 301 | Instruction *U = *UI; |
| 302 | BasicBlock *Parent = U->getParent(); |
| 303 | |
| 304 | // Used inside original header |
| 305 | if (Parent == OrigHeader) { |
| 306 | // Do not rename uses inside original header non-phi instructions. |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 307 | PHINode *PU = dyn_cast<PHINode>(U); |
Devang Patel | 24a1c49 | 2007-04-09 16:21:29 +0000 | [diff] [blame] | 308 | if (!PU) |
| 309 | continue; |
| 310 | |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 311 | // Do not rename uses inside original header phi nodes, if the |
| 312 | // incoming value is for new header. |
| 313 | if (PU->getBasicBlockIndex(NewHeader) != -1 |
| 314 | && PU->getIncomingValueForBlock(NewHeader) == U) |
| 315 | continue; |
Devang Patel | 4522c8a | 2007-04-09 17:09:13 +0000 | [diff] [blame] | 316 | |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 317 | U->replaceUsesOfWith(OldPhi, NewPhi); |
| 318 | continue; |
| 319 | } |
| 320 | |
| 321 | // Used inside loop, but not in original header. |
| 322 | if (L->contains(U->getParent())) { |
Devang Patel | 24a1c49 | 2007-04-09 16:21:29 +0000 | [diff] [blame] | 323 | if (U != NewPhi) |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 324 | U->replaceUsesOfWith(OldPhi, NewPhi); |
| 325 | continue; |
| 326 | } |
Nick Lewycky | 8f5149e | 2007-07-07 16:23:34 +0000 | [diff] [blame] | 327 | |
Devang Patel | 990e866 | 2007-07-11 23:47:28 +0000 | [diff] [blame] | 328 | // Used inside Exit Block. Since we are in LCSSA form, U must be PHINode. |
| 329 | if (U->getParent() == Exit) { |
| 330 | assert (isa<PHINode>(U) && "Use in Exit Block that is not PHINode"); |
| 331 | |
| 332 | PHINode *UPhi = cast<PHINode>(U); |
| 333 | // UPhi already has one incoming argument from original header. |
| 334 | // Add second incoming argument from new Pre header. |
| 335 | UPhi->addIncoming(ILoopHeaderInfo.PreHeader, OrigPreHeader); |
| 336 | } else { |
| 337 | // Used outside Exit block. Create a new PHI node from exit block |
| 338 | // to receive value from ne new header ane pre header. |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame^] | 339 | PHINode *PN = PHINode::Create(U->getType(), U->getName()); |
Devang Patel | 990e866 | 2007-07-11 23:47:28 +0000 | [diff] [blame] | 340 | PN->addIncoming(ILoopHeaderInfo.PreHeader, OrigPreHeader); |
| 341 | PN->addIncoming(OldPhi, OrigHeader); |
| 342 | Exit->getInstList().push_front(PN); |
| 343 | U->replaceUsesOfWith(OldPhi, PN); |
| 344 | } |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 345 | } |
| 346 | } |
| 347 | |
| 348 | /// Make sure all Exit block PHINodes have required incoming values. |
| 349 | updateExitBlock(); |
| 350 | |
| 351 | // Update CFG |
| 352 | |
| 353 | // Removing incoming branch from loop preheader to original header. |
| 354 | // Now original header is inside the loop. |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 355 | for (BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end(); |
| 356 | I != E; ++I) { |
| 357 | Instruction *In = I; |
| 358 | PHINode *PN = dyn_cast<PHINode>(In); |
| 359 | if (!PN) |
| 360 | break; |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 361 | |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 362 | PN->removeIncomingValue(OrigPreHeader); |
| 363 | } |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 364 | |
| 365 | // Make NewHeader as the new header for the loop. |
| 366 | L->moveToHeader(NewHeader); |
| 367 | |
Devang Patel | 5464b96 | 2007-04-09 20:19:46 +0000 | [diff] [blame] | 368 | preserveCanonicalLoopForm(LPM); |
| 369 | |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 370 | NumRotated++; |
| 371 | return true; |
| 372 | } |
| 373 | |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 374 | /// Make sure all Exit block PHINodes have required incoming values. |
| 375 | /// If incoming value is constant or defined outside the loop then |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 376 | /// PHINode may not have an entry for original pre-header. |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 377 | void LoopRotate::updateExitBlock() { |
| 378 | |
| 379 | for (BasicBlock::iterator I = Exit->begin(), E = Exit->end(); |
| 380 | I != E; ++I) { |
| 381 | |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 382 | PHINode *PN = dyn_cast<PHINode>(I); |
Devang Patel | 24a1c49 | 2007-04-09 16:21:29 +0000 | [diff] [blame] | 383 | if (!PN) |
| 384 | break; |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 385 | |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 386 | // There is already one incoming value from original pre-header block. |
| 387 | if (PN->getBasicBlockIndex(OrigPreHeader) != -1) |
Devang Patel | 6c36157 | 2007-04-09 22:20:10 +0000 | [diff] [blame] | 388 | continue; |
Devang Patel | cfde959 | 2007-04-09 16:41:46 +0000 | [diff] [blame] | 389 | |
Devang Patel | 4522c8a | 2007-04-09 17:09:13 +0000 | [diff] [blame] | 390 | const RenameData *ILoopHeaderInfo; |
Devang Patel | cfde959 | 2007-04-09 16:41:46 +0000 | [diff] [blame] | 391 | Value *V = PN->getIncomingValueForBlock(OrigHeader); |
| 392 | if (isa<Instruction>(V) && |
| 393 | (ILoopHeaderInfo = findReplacementData(cast<Instruction>(V)))) { |
Chris Lattner | e34e9a2 | 2007-04-14 23:32:02 +0000 | [diff] [blame] | 394 | assert(ILoopHeaderInfo->PreHeader && "Missing New Preheader Instruction"); |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 395 | PN->addIncoming(ILoopHeaderInfo->PreHeader, OrigPreHeader); |
Devang Patel | cfde959 | 2007-04-09 16:41:46 +0000 | [diff] [blame] | 396 | } else { |
Devang Patel | e988154 | 2007-04-09 19:04:21 +0000 | [diff] [blame] | 397 | PN->addIncoming(V, OrigPreHeader); |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 398 | } |
| 399 | } |
| 400 | } |
| 401 | |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 402 | /// Initialize local data |
| 403 | void LoopRotate::initialize() { |
| 404 | L = NULL; |
| 405 | OrigHeader = NULL; |
| 406 | OrigPreHeader = NULL; |
| 407 | NewHeader = NULL; |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 408 | Exit = NULL; |
| 409 | |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 410 | LoopHeaderInfo.clear(); |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 411 | } |
| 412 | |
Devang Patel | 24a1c49 | 2007-04-09 16:21:29 +0000 | [diff] [blame] | 413 | /// Return true if this instruction is used by any instructions in the loop that |
| 414 | /// aren't in original header. |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 415 | bool LoopRotate::usedOutsideOriginalHeader(Instruction *In) { |
| 416 | |
| 417 | for (Value::use_iterator UI = In->use_begin(), UE = In->use_end(); |
| 418 | UI != UE; ++UI) { |
| 419 | Instruction *U = cast<Instruction>(UI); |
| 420 | if (U->getParent() != OrigHeader) { |
| 421 | if (L->contains(U->getParent())) |
| 422 | return true; |
| 423 | } |
| 424 | } |
| 425 | |
| 426 | return false; |
| 427 | } |
| 428 | |
| 429 | /// Find Replacement information for instruction. Return NULL if it is |
| 430 | /// not available. |
Devang Patel | 4522c8a | 2007-04-09 17:09:13 +0000 | [diff] [blame] | 431 | const RenameData *LoopRotate::findReplacementData(Instruction *In) { |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 432 | |
Devang Patel | 3223133 | 2007-04-09 16:11:48 +0000 | [diff] [blame] | 433 | // Since LoopHeaderInfo is small, linear walk is OK. |
Devang Patel | 4522c8a | 2007-04-09 17:09:13 +0000 | [diff] [blame] | 434 | for(unsigned LHI = 0, LHI_E = LoopHeaderInfo.size(); LHI != LHI_E; ++LHI) { |
| 435 | const RenameData &ILoopHeaderInfo = LoopHeaderInfo[LHI]; |
| 436 | if (ILoopHeaderInfo.Original == In) |
| 437 | return &ILoopHeaderInfo; |
| 438 | } |
Devang Patel | c4625da | 2007-04-07 01:25:15 +0000 | [diff] [blame] | 439 | return NULL; |
| 440 | } |
Devang Patel | 5464b96 | 2007-04-09 20:19:46 +0000 | [diff] [blame] | 441 | |
| 442 | /// After loop rotation, loop pre-header has multiple sucessors. |
| 443 | /// Insert one forwarding basic block to ensure that loop pre-header |
| 444 | /// has only one successor. |
| 445 | void LoopRotate::preserveCanonicalLoopForm(LPPassManager &LPM) { |
| 446 | |
| 447 | // Right now original pre-header has two successors, new header and |
| 448 | // exit block. Insert new block between original pre-header and |
| 449 | // new header such that loop's new pre-header has only one successor. |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame^] | 450 | BasicBlock *NewPreHeader = BasicBlock::Create("bb.nph", OrigHeader->getParent(), |
| 451 | NewHeader); |
Devang Patel | 5464b96 | 2007-04-09 20:19:46 +0000 | [diff] [blame] | 452 | LoopInfo &LI = LPM.getAnalysis<LoopInfo>(); |
| 453 | if (Loop *PL = LI.getLoopFor(OrigPreHeader)) |
Owen Anderson | d735ee8 | 2007-11-27 03:43:35 +0000 | [diff] [blame] | 454 | PL->addBasicBlockToLoop(NewPreHeader, LI.getBase()); |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame^] | 455 | BranchInst::Create(NewHeader, NewPreHeader); |
Devang Patel | 5464b96 | 2007-04-09 20:19:46 +0000 | [diff] [blame] | 456 | |
| 457 | BranchInst *OrigPH_BI = cast<BranchInst>(OrigPreHeader->getTerminator()); |
| 458 | if (OrigPH_BI->getSuccessor(0) == NewHeader) |
| 459 | OrigPH_BI->setSuccessor(0, NewPreHeader); |
| 460 | else { |
Devang Patel | c415afc | 2007-04-09 21:40:43 +0000 | [diff] [blame] | 461 | assert (OrigPH_BI->getSuccessor(1) == NewHeader && |
Devang Patel | 5464b96 | 2007-04-09 20:19:46 +0000 | [diff] [blame] | 462 | "Unexpected original pre-header terminator"); |
| 463 | OrigPH_BI->setSuccessor(1, NewPreHeader); |
| 464 | } |
| 465 | |
| 466 | for (BasicBlock::iterator I = NewHeader->begin(), E = NewHeader->end(); |
| 467 | I != E; ++I) { |
| 468 | Instruction *In = I; |
| 469 | PHINode *PN = dyn_cast<PHINode>(In); |
| 470 | if (!PN) |
| 471 | break; |
| 472 | |
| 473 | int index = PN->getBasicBlockIndex(OrigPreHeader); |
| 474 | assert (index != -1 && "Expected incoming value from Original PreHeader"); |
| 475 | PN->setIncomingBlock(index, NewPreHeader); |
| 476 | assert (PN->getBasicBlockIndex(OrigPreHeader) == -1 && |
| 477 | "Expected only one incoming value from Original PreHeader"); |
| 478 | } |
| 479 | |
Devang Patel | 990e866 | 2007-07-11 23:47:28 +0000 | [diff] [blame] | 480 | if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { |
| 481 | DT->addNewBlock(NewPreHeader, OrigPreHeader); |
| 482 | DT->changeImmediateDominator(L->getHeader(), NewPreHeader); |
| 483 | DT->changeImmediateDominator(Exit, OrigPreHeader); |
| 484 | for (Loop::block_iterator BI = L->block_begin(), BE = L->block_end(); |
| 485 | BI != BE; ++BI) { |
| 486 | BasicBlock *B = *BI; |
| 487 | if (L->getHeader() != B) { |
| 488 | DomTreeNode *Node = DT->getNode(B); |
| 489 | if (Node && Node->getBlock() == OrigHeader) |
| 490 | DT->changeImmediateDominator(*BI, L->getHeader()); |
| 491 | } |
| 492 | } |
| 493 | DT->changeImmediateDominator(OrigHeader, OrigLatch); |
| 494 | } |
| 495 | |
| 496 | if(DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { |
| 497 | |
| 498 | // New Preheader's dominance frontier is Exit block. |
| 499 | DominanceFrontier::DomSetType NewPHSet; |
| 500 | NewPHSet.insert(Exit); |
| 501 | DF->addBasicBlock(NewPreHeader, NewPHSet); |
| 502 | |
| 503 | // New Header's dominance frontier now includes itself and Exit block |
| 504 | DominanceFrontier::iterator HeadI = DF->find(L->getHeader()); |
| 505 | if (HeadI != DF->end()) { |
| 506 | DominanceFrontier::DomSetType & HeaderSet = HeadI->second; |
| 507 | HeaderSet.clear(); |
| 508 | HeaderSet.insert(L->getHeader()); |
| 509 | HeaderSet.insert(Exit); |
| 510 | } else { |
| 511 | DominanceFrontier::DomSetType HeaderSet; |
| 512 | HeaderSet.insert(L->getHeader()); |
| 513 | HeaderSet.insert(Exit); |
| 514 | DF->addBasicBlock(L->getHeader(), HeaderSet); |
| 515 | } |
| 516 | |
| 517 | // Original header (new Loop Latch)'s dominance frontier is Exit. |
| 518 | DominanceFrontier::iterator LatchI = DF->find(L->getLoopLatch()); |
| 519 | if (LatchI != DF->end()) { |
| 520 | DominanceFrontier::DomSetType &LatchSet = LatchI->second; |
| 521 | LatchSet = LatchI->second; |
| 522 | LatchSet.clear(); |
| 523 | LatchSet.insert(Exit); |
| 524 | } else { |
| 525 | DominanceFrontier::DomSetType LatchSet; |
| 526 | LatchSet.insert(Exit); |
| 527 | DF->addBasicBlock(L->getHeader(), LatchSet); |
| 528 | } |
| 529 | |
| 530 | // If a loop block dominates new loop latch then its frontier is |
| 531 | // new header and Exit. |
| 532 | BasicBlock *NewLatch = L->getLoopLatch(); |
| 533 | DominatorTree *DT = getAnalysisToUpdate<DominatorTree>(); |
| 534 | for (Loop::block_iterator BI = L->block_begin(), BE = L->block_end(); |
| 535 | BI != BE; ++BI) { |
| 536 | BasicBlock *B = *BI; |
| 537 | if (DT->dominates(B, NewLatch)) { |
| 538 | DominanceFrontier::iterator BDFI = DF->find(B); |
| 539 | if (BDFI != DF->end()) { |
| 540 | DominanceFrontier::DomSetType &BSet = BDFI->second; |
| 541 | BSet = BDFI->second; |
| 542 | BSet.clear(); |
| 543 | BSet.insert(L->getHeader()); |
| 544 | BSet.insert(Exit); |
| 545 | } else { |
| 546 | DominanceFrontier::DomSetType BSet; |
| 547 | BSet.insert(L->getHeader()); |
| 548 | BSet.insert(Exit); |
| 549 | DF->addBasicBlock(B, BSet); |
| 550 | } |
| 551 | } |
| 552 | } |
| 553 | } |
| 554 | |
| 555 | // Preserve canonical loop form, which means Exit block should |
| 556 | // have only one predecessor. |
| 557 | BasicBlock *NExit = SplitEdge(L->getLoopLatch(), Exit, this); |
| 558 | |
| 559 | // Preserve LCSSA. |
| 560 | BasicBlock::iterator I = Exit->begin(), E = Exit->end(); |
| 561 | PHINode *PN = NULL; |
| 562 | for (; (PN = dyn_cast<PHINode>(I)); ++I) { |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame^] | 563 | PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName()); |
Devang Patel | 990e866 | 2007-07-11 23:47:28 +0000 | [diff] [blame] | 564 | unsigned N = PN->getNumIncomingValues(); |
| 565 | for (unsigned index = 0; index < N; ++index) |
| 566 | if (PN->getIncomingBlock(index) == NExit) { |
| 567 | NewPN->addIncoming(PN->getIncomingValue(index), L->getLoopLatch()); |
| 568 | PN->setIncomingValue(index, NewPN); |
| 569 | PN->setIncomingBlock(index, NExit); |
| 570 | NExit->getInstList().push_front(NewPN); |
| 571 | } |
| 572 | } |
| 573 | |
Devang Patel | 5464b96 | 2007-04-09 20:19:46 +0000 | [diff] [blame] | 574 | assert (NewHeader && L->getHeader() == NewHeader |
| 575 | && "Invalid loop header after loop rotation"); |
| 576 | assert (NewPreHeader && L->getLoopPreheader() == NewPreHeader |
| 577 | && "Invalid loop preheader after loop rotation"); |
| 578 | assert (L->getLoopLatch() |
| 579 | && "Invalid loop latch after loop rotation"); |
Devang Patel | 990e866 | 2007-07-11 23:47:28 +0000 | [diff] [blame] | 580 | |
Devang Patel | 5464b96 | 2007-04-09 20:19:46 +0000 | [diff] [blame] | 581 | } |