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