Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 1 | //===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by the LLVM research group and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 9 | // |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 10 | // This transformation analyzes and transforms the induction variables (and |
| 11 | // computations derived from them) into simpler forms suitable for subsequent |
| 12 | // analysis and transformation. |
| 13 | // |
Reid Spencer | 47a53ac | 2006-08-18 09:01:07 +0000 | [diff] [blame] | 14 | // This transformation makes the following changes to each loop with an |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 15 | // identifiable induction variable: |
| 16 | // 1. All loops are transformed to have a SINGLE canonical induction variable |
| 17 | // which starts at zero and steps by one. |
| 18 | // 2. The canonical induction variable is guaranteed to be the first PHI node |
| 19 | // in the loop header block. |
| 20 | // 3. Any pointer arithmetic recurrences are raised to use array subscripts. |
| 21 | // |
| 22 | // If the trip count of a loop is computable, this pass also makes the following |
| 23 | // changes: |
| 24 | // 1. The exit condition for the loop is canonicalized to compare the |
| 25 | // induction value against the exit value. This turns loops like: |
| 26 | // 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)' |
| 27 | // 2. Any use outside of the loop of an expression derived from the indvar |
| 28 | // is changed to compute the derived value outside of the loop, eliminating |
| 29 | // the dependence on the exit value of the induction variable. If the only |
| 30 | // purpose of the loop is to compute the exit value of some derived |
| 31 | // expression, this transformation will make the loop dead. |
| 32 | // |
| 33 | // This transformation should be followed by strength reduction after all of the |
| 34 | // desired loop transformations have been performed. Additionally, on targets |
| 35 | // where it is profitable, the loop could be transformed to count down to zero |
| 36 | // (the "do loop" optimization). |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 37 | // |
| 38 | //===----------------------------------------------------------------------===// |
| 39 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 40 | #define DEBUG_TYPE "indvars" |
Chris Lattner | 022103b | 2002-05-07 20:03:00 +0000 | [diff] [blame] | 41 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 42 | #include "llvm/BasicBlock.h" |
Chris Lattner | 59fdaee | 2004-04-15 15:21:43 +0000 | [diff] [blame] | 43 | #include "llvm/Constants.h" |
Chris Lattner | 18b3c97 | 2003-12-22 05:02:01 +0000 | [diff] [blame] | 44 | #include "llvm/Instructions.h" |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 45 | #include "llvm/Type.h" |
Nate Begeman | 36f891b | 2005-07-30 00:12:19 +0000 | [diff] [blame] | 46 | #include "llvm/Analysis/ScalarEvolutionExpander.h" |
John Criswell | 47df12d | 2003-12-18 17:19:19 +0000 | [diff] [blame] | 47 | #include "llvm/Analysis/LoopInfo.h" |
Devang Patel | 5ee9997 | 2007-03-07 06:39:01 +0000 | [diff] [blame] | 48 | #include "llvm/Analysis/LoopPass.h" |
Chris Lattner | 455889a | 2002-02-12 22:39:50 +0000 | [diff] [blame] | 49 | #include "llvm/Support/CFG.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 50 | #include "llvm/Support/Compiler.h" |
Chris Lattner | ee4f13a | 2007-01-07 01:14:12 +0000 | [diff] [blame] | 51 | #include "llvm/Support/Debug.h" |
Chris Lattner | a4b9c78 | 2004-10-11 23:06:50 +0000 | [diff] [blame] | 52 | #include "llvm/Support/GetElementPtrTypeIterator.h" |
John Criswell | 47df12d | 2003-12-18 17:19:19 +0000 | [diff] [blame] | 53 | #include "llvm/Transforms/Utils/Local.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 54 | #include "llvm/Support/CommandLine.h" |
Reid Spencer | a54b7cb | 2007-01-12 07:05:14 +0000 | [diff] [blame] | 55 | #include "llvm/ADT/SmallVector.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 56 | #include "llvm/ADT/Statistic.h" |
John Criswell | 47df12d | 2003-12-18 17:19:19 +0000 | [diff] [blame] | 57 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 58 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 59 | STATISTIC(NumRemoved , "Number of aux indvars removed"); |
| 60 | STATISTIC(NumPointer , "Number of pointer indvars promoted"); |
| 61 | STATISTIC(NumInserted, "Number of canonical indvars added"); |
| 62 | STATISTIC(NumReplaced, "Number of exit values replaced"); |
| 63 | STATISTIC(NumLFTR , "Number of loop exit tests replaced"); |
Chris Lattner | 3324e71 | 2003-12-22 03:58:44 +0000 | [diff] [blame] | 64 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 65 | namespace { |
Devang Patel | 5ee9997 | 2007-03-07 06:39:01 +0000 | [diff] [blame] | 66 | class VISIBILITY_HIDDEN IndVarSimplify : public LoopPass { |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 67 | LoopInfo *LI; |
| 68 | ScalarEvolution *SE; |
Chris Lattner | 15cad75 | 2003-12-23 07:47:09 +0000 | [diff] [blame] | 69 | bool Changed; |
Chris Lattner | 3324e71 | 2003-12-22 03:58:44 +0000 | [diff] [blame] | 70 | public: |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 71 | |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 72 | static char ID; // Pass identification, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 73 | IndVarSimplify() : LoopPass((intptr_t)&ID) {} |
| 74 | |
Devang Patel | 5ee9997 | 2007-03-07 06:39:01 +0000 | [diff] [blame] | 75 | bool runOnLoop(Loop *L, LPPassManager &LPM); |
| 76 | bool doInitialization(Loop *L, LPPassManager &LPM); |
| 77 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 78 | AU.addRequiredID(LCSSAID); |
| 79 | AU.addRequiredID(LoopSimplifyID); |
| 80 | AU.addRequired<ScalarEvolution>(); |
| 81 | AU.addRequired<LoopInfo>(); |
| 82 | AU.addPreservedID(LoopSimplifyID); |
| 83 | AU.addPreservedID(LCSSAID); |
| 84 | AU.setPreservesCFG(); |
| 85 | } |
Chris Lattner | 15cad75 | 2003-12-23 07:47:09 +0000 | [diff] [blame] | 86 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 87 | private: |
Devang Patel | 5ee9997 | 2007-03-07 06:39:01 +0000 | [diff] [blame] | 88 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 89 | void EliminatePointerRecurrence(PHINode *PN, BasicBlock *Preheader, |
| 90 | std::set<Instruction*> &DeadInsts); |
Chris Lattner | 9ba46c1 | 2006-09-21 05:12:20 +0000 | [diff] [blame] | 91 | Instruction *LinearFunctionTestReplace(Loop *L, SCEV *IterationCount, |
| 92 | SCEVExpander &RW); |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 93 | void RewriteLoopExitValues(Loop *L); |
| 94 | |
| 95 | void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts); |
Chris Lattner | 3324e71 | 2003-12-22 03:58:44 +0000 | [diff] [blame] | 96 | }; |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 97 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 98 | char IndVarSimplify::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 99 | RegisterPass<IndVarSimplify> X("indvars", "Canonicalize Induction Variables"); |
Chris Lattner | 5e76140 | 2002-09-10 05:24:05 +0000 | [diff] [blame] | 100 | } |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 101 | |
Devang Patel | 5ee9997 | 2007-03-07 06:39:01 +0000 | [diff] [blame] | 102 | LoopPass *llvm::createIndVarSimplifyPass() { |
Chris Lattner | 3324e71 | 2003-12-22 03:58:44 +0000 | [diff] [blame] | 103 | return new IndVarSimplify(); |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 104 | } |
| 105 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 106 | /// DeleteTriviallyDeadInstructions - If any of the instructions is the |
| 107 | /// specified set are trivially dead, delete them and see if this makes any of |
| 108 | /// their operands subsequently dead. |
| 109 | void IndVarSimplify:: |
| 110 | DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts) { |
| 111 | while (!Insts.empty()) { |
| 112 | Instruction *I = *Insts.begin(); |
| 113 | Insts.erase(Insts.begin()); |
| 114 | if (isInstructionTriviallyDead(I)) { |
| 115 | for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) |
| 116 | if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i))) |
| 117 | Insts.insert(U); |
| 118 | SE->deleteInstructionFromRecords(I); |
Chris Lattner | ee4f13a | 2007-01-07 01:14:12 +0000 | [diff] [blame] | 119 | DOUT << "INDVARS: Deleting: " << *I; |
Chris Lattner | a4b9c78 | 2004-10-11 23:06:50 +0000 | [diff] [blame] | 120 | I->eraseFromParent(); |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 121 | Changed = true; |
| 122 | } |
| 123 | } |
| 124 | } |
| 125 | |
| 126 | |
| 127 | /// EliminatePointerRecurrence - Check to see if this is a trivial GEP pointer |
| 128 | /// recurrence. If so, change it into an integer recurrence, permitting |
| 129 | /// analysis by the SCEV routines. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 130 | void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN, |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 131 | BasicBlock *Preheader, |
| 132 | std::set<Instruction*> &DeadInsts) { |
| 133 | assert(PN->getNumIncomingValues() == 2 && "Noncanonicalized loop!"); |
| 134 | unsigned PreheaderIdx = PN->getBasicBlockIndex(Preheader); |
| 135 | unsigned BackedgeIdx = PreheaderIdx^1; |
| 136 | if (GetElementPtrInst *GEPI = |
Chris Lattner | cda9ca5 | 2005-08-10 01:12:06 +0000 | [diff] [blame] | 137 | dyn_cast<GetElementPtrInst>(PN->getIncomingValue(BackedgeIdx))) |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 138 | if (GEPI->getOperand(0) == PN) { |
Chris Lattner | cda9ca5 | 2005-08-10 01:12:06 +0000 | [diff] [blame] | 139 | assert(GEPI->getNumOperands() == 2 && "GEP types must match!"); |
Chris Lattner | ee4f13a | 2007-01-07 01:14:12 +0000 | [diff] [blame] | 140 | DOUT << "INDVARS: Eliminating pointer recurrence: " << *GEPI; |
| 141 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 142 | // Okay, we found a pointer recurrence. Transform this pointer |
| 143 | // recurrence into an integer recurrence. Compute the value that gets |
| 144 | // added to the pointer at every iteration. |
| 145 | Value *AddedVal = GEPI->getOperand(1); |
| 146 | |
| 147 | // Insert a new integer PHI node into the top of the block. |
| 148 | PHINode *NewPhi = new PHINode(AddedVal->getType(), |
| 149 | PN->getName()+".rec", PN); |
Chris Lattner | c5c5e6a | 2004-06-20 05:04:01 +0000 | [diff] [blame] | 150 | NewPhi->addIncoming(Constant::getNullValue(NewPhi->getType()), Preheader); |
| 151 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 152 | // Create the new add instruction. |
Chris Lattner | c5c5e6a | 2004-06-20 05:04:01 +0000 | [diff] [blame] | 153 | Value *NewAdd = BinaryOperator::createAdd(NewPhi, AddedVal, |
| 154 | GEPI->getName()+".rec", GEPI); |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 155 | NewPhi->addIncoming(NewAdd, PN->getIncomingBlock(BackedgeIdx)); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 156 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 157 | // Update the existing GEP to use the recurrence. |
| 158 | GEPI->setOperand(0, PN->getIncomingValue(PreheaderIdx)); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 159 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 160 | // Update the GEP to use the new recurrence we just inserted. |
| 161 | GEPI->setOperand(1, NewAdd); |
| 162 | |
Chris Lattner | a4b9c78 | 2004-10-11 23:06:50 +0000 | [diff] [blame] | 163 | // If the incoming value is a constant expr GEP, try peeling out the array |
| 164 | // 0 index if possible to make things simpler. |
| 165 | if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEPI->getOperand(0))) |
| 166 | if (CE->getOpcode() == Instruction::GetElementPtr) { |
| 167 | unsigned NumOps = CE->getNumOperands(); |
| 168 | assert(NumOps > 1 && "CE folding didn't work!"); |
| 169 | if (CE->getOperand(NumOps-1)->isNullValue()) { |
| 170 | // Check to make sure the last index really is an array index. |
Chris Lattner | 1730078 | 2005-11-18 18:30:47 +0000 | [diff] [blame] | 171 | gep_type_iterator GTI = gep_type_begin(CE); |
Chris Lattner | ceda605 | 2005-11-17 19:35:42 +0000 | [diff] [blame] | 172 | for (unsigned i = 1, e = CE->getNumOperands()-1; |
Chris Lattner | a4b9c78 | 2004-10-11 23:06:50 +0000 | [diff] [blame] | 173 | i != e; ++i, ++GTI) |
| 174 | /*empty*/; |
| 175 | if (isa<SequentialType>(*GTI)) { |
| 176 | // Pull the last index out of the constant expr GEP. |
Chris Lattner | 55eb1c4 | 2007-01-31 04:40:53 +0000 | [diff] [blame] | 177 | SmallVector<Value*, 8> CEIdxs(CE->op_begin()+1, CE->op_end()-1); |
Chris Lattner | a4b9c78 | 2004-10-11 23:06:50 +0000 | [diff] [blame] | 178 | Constant *NCE = ConstantExpr::getGetElementPtr(CE->getOperand(0), |
Chris Lattner | 55eb1c4 | 2007-01-31 04:40:53 +0000 | [diff] [blame] | 179 | &CEIdxs[0], |
| 180 | CEIdxs.size()); |
Reid Spencer | cae5754 | 2007-03-02 00:28:52 +0000 | [diff] [blame] | 181 | GetElementPtrInst *NGEPI = new GetElementPtrInst( |
| 182 | NCE, Constant::getNullValue(Type::Int32Ty), NewAdd, |
| 183 | GEPI->getName(), GEPI); |
Nick Lewycky | 5adcefb | 2007-06-06 03:51:56 +0000 | [diff] [blame] | 184 | SE->deleteInstructionFromRecords(GEPI); |
Chris Lattner | a4b9c78 | 2004-10-11 23:06:50 +0000 | [diff] [blame] | 185 | GEPI->replaceAllUsesWith(NGEPI); |
| 186 | GEPI->eraseFromParent(); |
| 187 | GEPI = NGEPI; |
| 188 | } |
| 189 | } |
| 190 | } |
| 191 | |
| 192 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 193 | // Finally, if there are any other users of the PHI node, we must |
| 194 | // insert a new GEP instruction that uses the pre-incremented version |
| 195 | // of the induction amount. |
| 196 | if (!PN->use_empty()) { |
| 197 | BasicBlock::iterator InsertPos = PN; ++InsertPos; |
| 198 | while (isa<PHINode>(InsertPos)) ++InsertPos; |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 199 | Value *PreInc = |
| 200 | new GetElementPtrInst(PN->getIncomingValue(PreheaderIdx), |
Chris Lattner | 6934a04 | 2007-02-11 01:23:03 +0000 | [diff] [blame] | 201 | NewPhi, "", InsertPos); |
| 202 | PreInc->takeName(PN); |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 203 | PN->replaceAllUsesWith(PreInc); |
| 204 | } |
| 205 | |
| 206 | // Delete the old PHI for sure, and the GEP if its otherwise unused. |
| 207 | DeadInsts.insert(PN); |
| 208 | |
| 209 | ++NumPointer; |
| 210 | Changed = true; |
| 211 | } |
| 212 | } |
| 213 | |
| 214 | /// LinearFunctionTestReplace - This method rewrites the exit condition of the |
Chris Lattner | 59fdaee | 2004-04-15 15:21:43 +0000 | [diff] [blame] | 215 | /// loop to be a canonical != comparison against the incremented loop induction |
| 216 | /// variable. This pass is able to rewrite the exit tests of any loop where the |
| 217 | /// SCEV analysis can determine a loop-invariant trip count of the loop, which |
| 218 | /// is actually a much broader range than just linear tests. |
Chris Lattner | 9ba46c1 | 2006-09-21 05:12:20 +0000 | [diff] [blame] | 219 | /// |
| 220 | /// This method returns a "potentially dead" instruction whose computation chain |
| 221 | /// should be deleted when convenient. |
| 222 | Instruction *IndVarSimplify::LinearFunctionTestReplace(Loop *L, |
| 223 | SCEV *IterationCount, |
| 224 | SCEVExpander &RW) { |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 225 | // Find the exit block for the loop. We can currently only handle loops with |
| 226 | // a single exit. |
Chris Lattner | f1ab4b4 | 2004-04-18 22:14:10 +0000 | [diff] [blame] | 227 | std::vector<BasicBlock*> ExitBlocks; |
| 228 | L->getExitBlocks(ExitBlocks); |
Chris Lattner | 9ba46c1 | 2006-09-21 05:12:20 +0000 | [diff] [blame] | 229 | if (ExitBlocks.size() != 1) return 0; |
Chris Lattner | f1ab4b4 | 2004-04-18 22:14:10 +0000 | [diff] [blame] | 230 | BasicBlock *ExitBlock = ExitBlocks[0]; |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 231 | |
| 232 | // Make sure there is only one predecessor block in the loop. |
| 233 | BasicBlock *ExitingBlock = 0; |
| 234 | for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); |
| 235 | PI != PE; ++PI) |
| 236 | if (L->contains(*PI)) { |
| 237 | if (ExitingBlock == 0) |
| 238 | ExitingBlock = *PI; |
| 239 | else |
Chris Lattner | 9ba46c1 | 2006-09-21 05:12:20 +0000 | [diff] [blame] | 240 | return 0; // Multiple exits from loop to this block. |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 241 | } |
| 242 | assert(ExitingBlock && "Loop info is broken"); |
| 243 | |
| 244 | if (!isa<BranchInst>(ExitingBlock->getTerminator())) |
Chris Lattner | 9ba46c1 | 2006-09-21 05:12:20 +0000 | [diff] [blame] | 245 | return 0; // Can't rewrite non-branch yet |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 246 | BranchInst *BI = cast<BranchInst>(ExitingBlock->getTerminator()); |
| 247 | assert(BI->isConditional() && "Must be conditional to be part of loop!"); |
| 248 | |
Chris Lattner | 9ba46c1 | 2006-09-21 05:12:20 +0000 | [diff] [blame] | 249 | Instruction *PotentiallyDeadInst = dyn_cast<Instruction>(BI->getCondition()); |
| 250 | |
Chris Lattner | d244057 | 2004-04-15 20:26:22 +0000 | [diff] [blame] | 251 | // If the exiting block is not the same as the backedge block, we must compare |
| 252 | // against the preincremented value, otherwise we prefer to compare against |
| 253 | // the post-incremented value. |
| 254 | BasicBlock *Header = L->getHeader(); |
| 255 | pred_iterator HPI = pred_begin(Header); |
| 256 | assert(HPI != pred_end(Header) && "Loop with zero preds???"); |
| 257 | if (!L->contains(*HPI)) ++HPI; |
| 258 | assert(HPI != pred_end(Header) && L->contains(*HPI) && |
| 259 | "No backedge in loop?"); |
Chris Lattner | 59fdaee | 2004-04-15 15:21:43 +0000 | [diff] [blame] | 260 | |
Chris Lattner | d244057 | 2004-04-15 20:26:22 +0000 | [diff] [blame] | 261 | SCEVHandle TripCount = IterationCount; |
| 262 | Value *IndVar; |
| 263 | if (*HPI == ExitingBlock) { |
| 264 | // The IterationCount expression contains the number of times that the |
| 265 | // backedge actually branches to the loop header. This is one less than the |
| 266 | // number of times the loop executes, so add one to it. |
Dan Gohman | e19dd87 | 2007-06-15 18:00:55 +0000 | [diff] [blame^] | 267 | ConstantInt *OneC = ConstantInt::get(IterationCount->getType(), 1); |
| 268 | TripCount = SCEVAddExpr::get(IterationCount, SCEVConstant::get(OneC)); |
Chris Lattner | d244057 | 2004-04-15 20:26:22 +0000 | [diff] [blame] | 269 | IndVar = L->getCanonicalInductionVariableIncrement(); |
| 270 | } else { |
| 271 | // We have to use the preincremented value... |
| 272 | IndVar = L->getCanonicalInductionVariable(); |
| 273 | } |
Chris Lattner | ee4f13a | 2007-01-07 01:14:12 +0000 | [diff] [blame] | 274 | |
| 275 | DOUT << "INDVARS: LFTR: TripCount = " << *TripCount |
| 276 | << " IndVar = " << *IndVar << "\n"; |
Chris Lattner | 59fdaee | 2004-04-15 15:21:43 +0000 | [diff] [blame] | 277 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 278 | // Expand the code for the iteration count into the preheader of the loop. |
| 279 | BasicBlock *Preheader = L->getLoopPreheader(); |
Dan Gohman | d19534a | 2007-06-15 14:38:12 +0000 | [diff] [blame] | 280 | Value *ExitCnt = RW.expandCodeFor(TripCount, Preheader->getTerminator()); |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 281 | |
Reid Spencer | e4d87aa | 2006-12-23 06:05:41 +0000 | [diff] [blame] | 282 | // Insert a new icmp_ne or icmp_eq instruction before the branch. |
| 283 | ICmpInst::Predicate Opcode; |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 284 | if (L->contains(BI->getSuccessor(0))) |
Reid Spencer | e4d87aa | 2006-12-23 06:05:41 +0000 | [diff] [blame] | 285 | Opcode = ICmpInst::ICMP_NE; |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 286 | else |
Reid Spencer | e4d87aa | 2006-12-23 06:05:41 +0000 | [diff] [blame] | 287 | Opcode = ICmpInst::ICMP_EQ; |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 288 | |
Reid Spencer | e4d87aa | 2006-12-23 06:05:41 +0000 | [diff] [blame] | 289 | Value *Cond = new ICmpInst(Opcode, IndVar, ExitCnt, "exitcond", BI); |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 290 | BI->setCondition(Cond); |
| 291 | ++NumLFTR; |
| 292 | Changed = true; |
Chris Lattner | 9ba46c1 | 2006-09-21 05:12:20 +0000 | [diff] [blame] | 293 | return PotentiallyDeadInst; |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 294 | } |
| 295 | |
| 296 | |
| 297 | /// RewriteLoopExitValues - Check to see if this loop has a computable |
| 298 | /// loop-invariant execution count. If so, this means that we can compute the |
| 299 | /// final value of any expressions that are recurrent in the loop, and |
| 300 | /// substitute the exit values from the loop into any instructions outside of |
| 301 | /// the loop that use the final values of the current expressions. |
| 302 | void IndVarSimplify::RewriteLoopExitValues(Loop *L) { |
| 303 | BasicBlock *Preheader = L->getLoopPreheader(); |
| 304 | |
| 305 | // Scan all of the instructions in the loop, looking at those that have |
| 306 | // extra-loop users and which are recurrences. |
Chris Lattner | 4a7553e | 2004-04-23 21:29:48 +0000 | [diff] [blame] | 307 | SCEVExpander Rewriter(*SE, *LI); |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 308 | |
| 309 | // We insert the code into the preheader of the loop if the loop contains |
| 310 | // multiple exit blocks, or in the exit block if there is exactly one. |
| 311 | BasicBlock *BlockToInsertInto; |
Chris Lattner | f1ab4b4 | 2004-04-18 22:14:10 +0000 | [diff] [blame] | 312 | std::vector<BasicBlock*> ExitBlocks; |
Chris Lattner | 9f3d738 | 2007-03-04 03:43:23 +0000 | [diff] [blame] | 313 | L->getUniqueExitBlocks(ExitBlocks); |
Chris Lattner | f1ab4b4 | 2004-04-18 22:14:10 +0000 | [diff] [blame] | 314 | if (ExitBlocks.size() == 1) |
| 315 | BlockToInsertInto = ExitBlocks[0]; |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 316 | else |
| 317 | BlockToInsertInto = Preheader; |
| 318 | BasicBlock::iterator InsertPt = BlockToInsertInto->begin(); |
| 319 | while (isa<PHINode>(InsertPt)) ++InsertPt; |
| 320 | |
Chris Lattner | 20aa098 | 2004-04-17 18:44:09 +0000 | [diff] [blame] | 321 | bool HasConstantItCount = isa<SCEVConstant>(SE->getIterationCount(L)); |
| 322 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 323 | std::set<Instruction*> InstructionsToDelete; |
Chris Lattner | 9f3d738 | 2007-03-04 03:43:23 +0000 | [diff] [blame] | 324 | std::map<Instruction*, Value*> ExitValues; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 325 | |
Chris Lattner | 9f3d738 | 2007-03-04 03:43:23 +0000 | [diff] [blame] | 326 | // Find all values that are computed inside the loop, but used outside of it. |
| 327 | // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan |
| 328 | // the exit blocks of the loop to find them. |
| 329 | for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { |
| 330 | BasicBlock *ExitBB = ExitBlocks[i]; |
| 331 | |
| 332 | // If there are no PHI nodes in this exit block, then no values defined |
| 333 | // inside the loop are used on this path, skip it. |
| 334 | PHINode *PN = dyn_cast<PHINode>(ExitBB->begin()); |
| 335 | if (!PN) continue; |
| 336 | |
| 337 | unsigned NumPreds = PN->getNumIncomingValues(); |
| 338 | |
| 339 | // Iterate over all of the PHI nodes. |
| 340 | BasicBlock::iterator BBI = ExitBB->begin(); |
| 341 | while ((PN = dyn_cast<PHINode>(BBI++))) { |
Chris Lattner | c9838f2 | 2007-03-03 22:48:48 +0000 | [diff] [blame] | 342 | |
Chris Lattner | 9f3d738 | 2007-03-04 03:43:23 +0000 | [diff] [blame] | 343 | // Iterate over all of the values in all the PHI nodes. |
| 344 | for (unsigned i = 0; i != NumPreds; ++i) { |
| 345 | // If the value being merged in is not integer or is not defined |
| 346 | // in the loop, skip it. |
| 347 | Value *InVal = PN->getIncomingValue(i); |
| 348 | if (!isa<Instruction>(InVal) || |
| 349 | // SCEV only supports integer expressions for now. |
| 350 | !isa<IntegerType>(InVal->getType())) |
| 351 | continue; |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 352 | |
Chris Lattner | 9f3d738 | 2007-03-04 03:43:23 +0000 | [diff] [blame] | 353 | // If this pred is for a subloop, not L itself, skip it. |
| 354 | if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) |
| 355 | continue; // The Block is in a subloop, skip it. |
| 356 | |
| 357 | // Check that InVal is defined in the loop. |
| 358 | Instruction *Inst = cast<Instruction>(InVal); |
| 359 | if (!L->contains(Inst->getParent())) |
| 360 | continue; |
Chris Lattner | 9caed54 | 2007-03-04 01:00:28 +0000 | [diff] [blame] | 361 | |
Chris Lattner | 9f3d738 | 2007-03-04 03:43:23 +0000 | [diff] [blame] | 362 | // We require that this value either have a computable evolution or that |
| 363 | // the loop have a constant iteration count. In the case where the loop |
| 364 | // has a constant iteration count, we can sometimes force evaluation of |
| 365 | // the exit value through brute force. |
| 366 | SCEVHandle SH = SE->getSCEV(Inst); |
| 367 | if (!SH->hasComputableLoopEvolution(L) && !HasConstantItCount) |
| 368 | continue; // Cannot get exit evolution for the loop value. |
| 369 | |
| 370 | // Okay, this instruction has a user outside of the current loop |
| 371 | // and varies predictably *inside* the loop. Evaluate the value it |
| 372 | // contains when the loop exits, if possible. |
| 373 | SCEVHandle ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop()); |
| 374 | if (isa<SCEVCouldNotCompute>(ExitValue) || |
| 375 | !ExitValue->isLoopInvariant(L)) |
| 376 | continue; |
Chris Lattner | 9caed54 | 2007-03-04 01:00:28 +0000 | [diff] [blame] | 377 | |
Chris Lattner | 9f3d738 | 2007-03-04 03:43:23 +0000 | [diff] [blame] | 378 | Changed = true; |
| 379 | ++NumReplaced; |
| 380 | |
| 381 | // See if we already computed the exit value for the instruction, if so, |
| 382 | // just reuse it. |
| 383 | Value *&ExitVal = ExitValues[Inst]; |
| 384 | if (!ExitVal) |
Dan Gohman | d19534a | 2007-06-15 14:38:12 +0000 | [diff] [blame] | 385 | ExitVal = Rewriter.expandCodeFor(ExitValue, InsertPt); |
Chris Lattner | 9f3d738 | 2007-03-04 03:43:23 +0000 | [diff] [blame] | 386 | |
| 387 | DOUT << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal |
| 388 | << " LoopVal = " << *Inst << "\n"; |
| 389 | |
| 390 | PN->setIncomingValue(i, ExitVal); |
| 391 | |
| 392 | // If this instruction is dead now, schedule it to be removed. |
| 393 | if (Inst->use_empty()) |
| 394 | InstructionsToDelete.insert(Inst); |
| 395 | |
| 396 | // See if this is a single-entry LCSSA PHI node. If so, we can (and |
| 397 | // have to) remove |
Chris Lattner | 9caed54 | 2007-03-04 01:00:28 +0000 | [diff] [blame] | 398 | // the PHI entirely. This is safe, because the NewVal won't be variant |
| 399 | // in the loop, so we don't need an LCSSA phi node anymore. |
Chris Lattner | 9f3d738 | 2007-03-04 03:43:23 +0000 | [diff] [blame] | 400 | if (NumPreds == 1) { |
Nick Lewycky | 5adcefb | 2007-06-06 03:51:56 +0000 | [diff] [blame] | 401 | SE->deleteInstructionFromRecords(PN); |
Chris Lattner | 9f3d738 | 2007-03-04 03:43:23 +0000 | [diff] [blame] | 402 | PN->replaceAllUsesWith(ExitVal); |
| 403 | PN->eraseFromParent(); |
| 404 | break; |
Chris Lattner | c9838f2 | 2007-03-03 22:48:48 +0000 | [diff] [blame] | 405 | } |
| 406 | } |
Chris Lattner | c9838f2 | 2007-03-03 22:48:48 +0000 | [diff] [blame] | 407 | } |
| 408 | } |
| 409 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 410 | DeleteTriviallyDeadInstructions(InstructionsToDelete); |
| 411 | } |
| 412 | |
Devang Patel | 5ee9997 | 2007-03-07 06:39:01 +0000 | [diff] [blame] | 413 | bool IndVarSimplify::doInitialization(Loop *L, LPPassManager &LPM) { |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 414 | |
Devang Patel | 5ee9997 | 2007-03-07 06:39:01 +0000 | [diff] [blame] | 415 | Changed = false; |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 416 | // First step. Check to see if there are any trivial GEP pointer recurrences. |
| 417 | // If there are, change them into integer recurrences, permitting analysis by |
| 418 | // the SCEV routines. |
| 419 | // |
| 420 | BasicBlock *Header = L->getHeader(); |
| 421 | BasicBlock *Preheader = L->getLoopPreheader(); |
Devang Patel | 5ee9997 | 2007-03-07 06:39:01 +0000 | [diff] [blame] | 422 | SE = &LPM.getAnalysis<ScalarEvolution>(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 423 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 424 | std::set<Instruction*> DeadInsts; |
Reid Spencer | 2da5c3d | 2004-09-15 17:06:42 +0000 | [diff] [blame] | 425 | for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { |
| 426 | PHINode *PN = cast<PHINode>(I); |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 427 | if (isa<PointerType>(PN->getType())) |
| 428 | EliminatePointerRecurrence(PN, Preheader, DeadInsts); |
Reid Spencer | 2da5c3d | 2004-09-15 17:06:42 +0000 | [diff] [blame] | 429 | } |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 430 | |
| 431 | if (!DeadInsts.empty()) |
| 432 | DeleteTriviallyDeadInstructions(DeadInsts); |
| 433 | |
Devang Patel | 5ee9997 | 2007-03-07 06:39:01 +0000 | [diff] [blame] | 434 | return Changed; |
| 435 | } |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 436 | |
Devang Patel | 5ee9997 | 2007-03-07 06:39:01 +0000 | [diff] [blame] | 437 | bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { |
Chris Lattner | 3324e71 | 2003-12-22 03:58:44 +0000 | [diff] [blame] | 438 | |
Devang Patel | 5ee9997 | 2007-03-07 06:39:01 +0000 | [diff] [blame] | 439 | |
| 440 | LI = &getAnalysis<LoopInfo>(); |
| 441 | SE = &getAnalysis<ScalarEvolution>(); |
| 442 | |
| 443 | Changed = false; |
| 444 | BasicBlock *Header = L->getHeader(); |
| 445 | std::set<Instruction*> DeadInsts; |
| 446 | |
Chris Lattner | 9caed54 | 2007-03-04 01:00:28 +0000 | [diff] [blame] | 447 | // Verify the input to the pass in already in LCSSA form. |
| 448 | assert(L->isLCSSAForm()); |
| 449 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 450 | // Check to see if this loop has a computable loop-invariant execution count. |
| 451 | // If so, this means that we can compute the final value of any expressions |
| 452 | // that are recurrent in the loop, and substitute the exit values from the |
| 453 | // loop into any instructions outside of the loop that use the final values of |
| 454 | // the current expressions. |
Chris Lattner | 3dec1f2 | 2002-05-10 15:38:35 +0000 | [diff] [blame] | 455 | // |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 456 | SCEVHandle IterationCount = SE->getIterationCount(L); |
| 457 | if (!isa<SCEVCouldNotCompute>(IterationCount)) |
| 458 | RewriteLoopExitValues(L); |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 459 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 460 | // Next, analyze all of the induction variables in the loop, canonicalizing |
| 461 | // auxillary induction variables. |
| 462 | std::vector<std::pair<PHINode*, SCEVHandle> > IndVars; |
| 463 | |
Reid Spencer | 2da5c3d | 2004-09-15 17:06:42 +0000 | [diff] [blame] | 464 | for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { |
| 465 | PHINode *PN = cast<PHINode>(I); |
Chris Lattner | 42a7551 | 2007-01-15 02:27:26 +0000 | [diff] [blame] | 466 | if (PN->getType()->isInteger()) { // FIXME: when we have fast-math, enable! |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 467 | SCEVHandle SCEV = SE->getSCEV(PN); |
| 468 | if (SCEV->hasComputableLoopEvolution(L)) |
Chris Lattner | cda9ca5 | 2005-08-10 01:12:06 +0000 | [diff] [blame] | 469 | // FIXME: It is an extremely bad idea to indvar substitute anything more |
| 470 | // complex than affine induction variables. Doing so will put expensive |
| 471 | // polynomial evaluations inside of the loop, and the str reduction pass |
| 472 | // currently can only reduce affine polynomials. For now just disable |
| 473 | // indvar subst on anything more complex than an affine addrec. |
Chris Lattner | 595ee7e | 2004-07-26 02:47:12 +0000 | [diff] [blame] | 474 | if (SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SCEV)) |
Chris Lattner | cda9ca5 | 2005-08-10 01:12:06 +0000 | [diff] [blame] | 475 | if (AR->isAffine()) |
Chris Lattner | 595ee7e | 2004-07-26 02:47:12 +0000 | [diff] [blame] | 476 | IndVars.push_back(std::make_pair(PN, SCEV)); |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 477 | } |
Reid Spencer | 2da5c3d | 2004-09-15 17:06:42 +0000 | [diff] [blame] | 478 | } |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 479 | |
| 480 | // If there are no induction variables in the loop, there is nothing more to |
| 481 | // do. |
Chris Lattner | f50af08 | 2004-04-17 18:08:33 +0000 | [diff] [blame] | 482 | if (IndVars.empty()) { |
| 483 | // Actually, if we know how many times the loop iterates, lets insert a |
| 484 | // canonical induction variable to help subsequent passes. |
| 485 | if (!isa<SCEVCouldNotCompute>(IterationCount)) { |
Chris Lattner | 4a7553e | 2004-04-23 21:29:48 +0000 | [diff] [blame] | 486 | SCEVExpander Rewriter(*SE, *LI); |
| 487 | Rewriter.getOrInsertCanonicalInductionVariable(L, |
Chris Lattner | f50af08 | 2004-04-17 18:08:33 +0000 | [diff] [blame] | 488 | IterationCount->getType()); |
Chris Lattner | 9ba46c1 | 2006-09-21 05:12:20 +0000 | [diff] [blame] | 489 | if (Instruction *I = LinearFunctionTestReplace(L, IterationCount, |
| 490 | Rewriter)) { |
| 491 | std::set<Instruction*> InstructionsToDelete; |
| 492 | InstructionsToDelete.insert(I); |
| 493 | DeleteTriviallyDeadInstructions(InstructionsToDelete); |
| 494 | } |
Chris Lattner | f50af08 | 2004-04-17 18:08:33 +0000 | [diff] [blame] | 495 | } |
Devang Patel | 5ee9997 | 2007-03-07 06:39:01 +0000 | [diff] [blame] | 496 | return Changed; |
Chris Lattner | f50af08 | 2004-04-17 18:08:33 +0000 | [diff] [blame] | 497 | } |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 498 | |
| 499 | // Compute the type of the largest recurrence expression. |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 500 | // |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 501 | const Type *LargestType = IndVars[0].first->getType(); |
Chris Lattner | fcb81f5 | 2004-04-22 14:59:40 +0000 | [diff] [blame] | 502 | bool DifferingSizes = false; |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 503 | for (unsigned i = 1, e = IndVars.size(); i != e; ++i) { |
| 504 | const Type *Ty = IndVars[i].first->getType(); |
Reid Spencer | abaa8ca | 2007-01-08 16:32:00 +0000 | [diff] [blame] | 505 | DifferingSizes |= |
| 506 | Ty->getPrimitiveSizeInBits() != LargestType->getPrimitiveSizeInBits(); |
| 507 | if (Ty->getPrimitiveSizeInBits() > LargestType->getPrimitiveSizeInBits()) |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 508 | LargestType = Ty; |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 509 | } |
| 510 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 511 | // Create a rewriter object which we'll use to transform the code with. |
Chris Lattner | 4a7553e | 2004-04-23 21:29:48 +0000 | [diff] [blame] | 512 | SCEVExpander Rewriter(*SE, *LI); |
Chris Lattner | 15cad75 | 2003-12-23 07:47:09 +0000 | [diff] [blame] | 513 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 514 | // Now that we know the largest of of the induction variables in this loop, |
| 515 | // insert a canonical induction variable of the largest size. |
Chris Lattner | 4a7553e | 2004-04-23 21:29:48 +0000 | [diff] [blame] | 516 | Value *IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L,LargestType); |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 517 | ++NumInserted; |
| 518 | Changed = true; |
Chris Lattner | ee4f13a | 2007-01-07 01:14:12 +0000 | [diff] [blame] | 519 | DOUT << "INDVARS: New CanIV: " << *IndVar; |
Chris Lattner | 15cad75 | 2003-12-23 07:47:09 +0000 | [diff] [blame] | 520 | |
Dan Gohman | d19534a | 2007-06-15 14:38:12 +0000 | [diff] [blame] | 521 | if (!isa<SCEVCouldNotCompute>(IterationCount)) { |
| 522 | if (IterationCount->getType() != LargestType) |
| 523 | IterationCount = SCEVZeroExtendExpr::get(IterationCount, LargestType); |
Chris Lattner | 9ba46c1 | 2006-09-21 05:12:20 +0000 | [diff] [blame] | 524 | if (Instruction *DI = LinearFunctionTestReplace(L, IterationCount,Rewriter)) |
| 525 | DeadInsts.insert(DI); |
Dan Gohman | d19534a | 2007-06-15 14:38:12 +0000 | [diff] [blame] | 526 | } |
Chris Lattner | 15cad75 | 2003-12-23 07:47:09 +0000 | [diff] [blame] | 527 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 528 | // Now that we have a canonical induction variable, we can rewrite any |
| 529 | // recurrences in terms of the induction variable. Start with the auxillary |
| 530 | // induction variables, and recursively rewrite any of their uses. |
| 531 | BasicBlock::iterator InsertPt = Header->begin(); |
| 532 | while (isa<PHINode>(InsertPt)) ++InsertPt; |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 533 | |
Chris Lattner | 5d461d2 | 2004-04-21 22:22:01 +0000 | [diff] [blame] | 534 | // If there were induction variables of other sizes, cast the primary |
| 535 | // induction variable to the right size for them, avoiding the need for the |
| 536 | // code evaluation methods to insert induction variables of different sizes. |
Chris Lattner | fcb81f5 | 2004-04-22 14:59:40 +0000 | [diff] [blame] | 537 | if (DifferingSizes) { |
Reid Spencer | a54b7cb | 2007-01-12 07:05:14 +0000 | [diff] [blame] | 538 | SmallVector<unsigned,4> InsertedSizes; |
| 539 | InsertedSizes.push_back(LargestType->getPrimitiveSizeInBits()); |
| 540 | for (unsigned i = 0, e = IndVars.size(); i != e; ++i) { |
| 541 | unsigned ithSize = IndVars[i].first->getType()->getPrimitiveSizeInBits(); |
Chris Lattner | ef60b2c | 2007-01-12 22:51:20 +0000 | [diff] [blame] | 542 | if (std::find(InsertedSizes.begin(), InsertedSizes.end(), ithSize) |
| 543 | == InsertedSizes.end()) { |
Chris Lattner | fcb81f5 | 2004-04-22 14:59:40 +0000 | [diff] [blame] | 544 | PHINode *PN = IndVars[i].first; |
Reid Spencer | a54b7cb | 2007-01-12 07:05:14 +0000 | [diff] [blame] | 545 | InsertedSizes.push_back(ithSize); |
Chris Lattner | ee4f13a | 2007-01-07 01:14:12 +0000 | [diff] [blame] | 546 | Instruction *New = new TruncInst(IndVar, PN->getType(), "indvar", |
| 547 | InsertPt); |
Chris Lattner | fcb81f5 | 2004-04-22 14:59:40 +0000 | [diff] [blame] | 548 | Rewriter.addInsertedValue(New, SE->getSCEV(New)); |
Chris Lattner | ee4f13a | 2007-01-07 01:14:12 +0000 | [diff] [blame] | 549 | DOUT << "INDVARS: Made trunc IV for " << *PN |
| 550 | << " NewVal = " << *New << "\n"; |
Chris Lattner | fcb81f5 | 2004-04-22 14:59:40 +0000 | [diff] [blame] | 551 | } |
Reid Spencer | a54b7cb | 2007-01-12 07:05:14 +0000 | [diff] [blame] | 552 | } |
Chris Lattner | fcb81f5 | 2004-04-22 14:59:40 +0000 | [diff] [blame] | 553 | } |
| 554 | |
Chris Lattner | ee4f13a | 2007-01-07 01:14:12 +0000 | [diff] [blame] | 555 | // Rewrite all induction variables in terms of the canonical induction |
| 556 | // variable. |
Chris Lattner | 5d461d2 | 2004-04-21 22:22:01 +0000 | [diff] [blame] | 557 | std::map<unsigned, Value*> InsertedSizes; |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 558 | while (!IndVars.empty()) { |
| 559 | PHINode *PN = IndVars.back().first; |
Dan Gohman | d19534a | 2007-06-15 14:38:12 +0000 | [diff] [blame] | 560 | Value *NewVal = Rewriter.expandCodeFor(IndVars.back().second, InsertPt); |
Chris Lattner | ee4f13a | 2007-01-07 01:14:12 +0000 | [diff] [blame] | 561 | DOUT << "INDVARS: Rewrote IV '" << *IndVars.back().second << "' " << *PN |
| 562 | << " into = " << *NewVal << "\n"; |
Chris Lattner | 6934a04 | 2007-02-11 01:23:03 +0000 | [diff] [blame] | 563 | NewVal->takeName(PN); |
Chris Lattner | 5d461d2 | 2004-04-21 22:22:01 +0000 | [diff] [blame] | 564 | |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 565 | // Replace the old PHI Node with the inserted computation. |
Chris Lattner | fcb81f5 | 2004-04-22 14:59:40 +0000 | [diff] [blame] | 566 | PN->replaceAllUsesWith(NewVal); |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 567 | DeadInsts.insert(PN); |
| 568 | IndVars.pop_back(); |
| 569 | ++NumRemoved; |
Chris Lattner | 4753bf2 | 2001-12-05 19:41:33 +0000 | [diff] [blame] | 570 | Changed = true; |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 571 | } |
| 572 | |
Chris Lattner | b4782d1 | 2004-04-22 15:12:36 +0000 | [diff] [blame] | 573 | #if 0 |
Chris Lattner | 1363e85 | 2004-04-21 23:36:08 +0000 | [diff] [blame] | 574 | // Now replace all derived expressions in the loop body with simpler |
| 575 | // expressions. |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 576 | for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i) |
| 577 | if (LI->getLoopFor(L->getBlocks()[i]) == L) { // Not in a subloop... |
| 578 | BasicBlock *BB = L->getBlocks()[i]; |
| 579 | for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) |
Chris Lattner | 42a7551 | 2007-01-15 02:27:26 +0000 | [diff] [blame] | 580 | if (I->getType()->isInteger() && // Is an integer instruction |
Chris Lattner | 1363e85 | 2004-04-21 23:36:08 +0000 | [diff] [blame] | 581 | !I->use_empty() && |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 582 | !Rewriter.isInsertedInstruction(I)) { |
| 583 | SCEVHandle SH = SE->getSCEV(I); |
Chris Lattner | 4a7553e | 2004-04-23 21:29:48 +0000 | [diff] [blame] | 584 | Value *V = Rewriter.expandCodeFor(SH, I, I->getType()); |
Chris Lattner | 1363e85 | 2004-04-21 23:36:08 +0000 | [diff] [blame] | 585 | if (V != I) { |
Chris Lattner | 6934a04 | 2007-02-11 01:23:03 +0000 | [diff] [blame] | 586 | if (isa<Instruction>(V)) |
| 587 | V->takeName(I); |
Chris Lattner | 1363e85 | 2004-04-21 23:36:08 +0000 | [diff] [blame] | 588 | I->replaceAllUsesWith(V); |
| 589 | DeadInsts.insert(I); |
| 590 | ++NumRemoved; |
| 591 | Changed = true; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 592 | } |
Chris Lattner | 40bf8b4 | 2004-04-02 20:24:31 +0000 | [diff] [blame] | 593 | } |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 594 | } |
Chris Lattner | b4782d1 | 2004-04-22 15:12:36 +0000 | [diff] [blame] | 595 | #endif |
Chris Lattner | 1363e85 | 2004-04-21 23:36:08 +0000 | [diff] [blame] | 596 | |
Chris Lattner | 1363e85 | 2004-04-21 23:36:08 +0000 | [diff] [blame] | 597 | DeleteTriviallyDeadInstructions(DeadInsts); |
Owen Anderson | eb70591 | 2006-08-25 22:12:36 +0000 | [diff] [blame] | 598 | |
Chris Lattner | 9caed54 | 2007-03-04 01:00:28 +0000 | [diff] [blame] | 599 | assert(L->isLCSSAForm()); |
Devang Patel | 5ee9997 | 2007-03-07 06:39:01 +0000 | [diff] [blame] | 600 | return Changed; |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 601 | } |