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