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