Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 1 | //===- ScalarEvolutionNormalization.cpp - See below -------------*- C++ -*-===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements utilities for working with "normalized" expressions. |
| 11 | // See the comments at the top of ScalarEvolutionNormalization.h for details. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #include "llvm/Analysis/Dominators.h" |
| 16 | #include "llvm/Analysis/LoopInfo.h" |
| 17 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
| 18 | #include "llvm/Analysis/ScalarEvolutionNormalization.h" |
| 19 | using namespace llvm; |
| 20 | |
| 21 | /// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression |
| 22 | /// and now we need to decide whether the user should use the preinc or post-inc |
| 23 | /// value. If this user should use the post-inc version of the IV, return true. |
| 24 | /// |
| 25 | /// Choosing wrong here can break dominance properties (if we choose to use the |
| 26 | /// post-inc value when we cannot) or it can end up adding extra live-ranges to |
| 27 | /// the loop, resulting in reg-reg copies (if we use the pre-inc value when we |
| 28 | /// should use the post-inc value). |
Dan Gohman | b7391fa | 2010-07-20 16:34:50 +0000 | [diff] [blame] | 29 | static bool IVUseShouldUsePostIncValue(Instruction *User, Value *Operand, |
Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 30 | const Loop *L, DominatorTree *DT) { |
| 31 | // If the user is in the loop, use the preinc value. |
| 32 | if (L->contains(User)) return false; |
| 33 | |
| 34 | BasicBlock *LatchBlock = L->getLoopLatch(); |
| 35 | if (!LatchBlock) |
| 36 | return false; |
| 37 | |
| 38 | // Ok, the user is outside of the loop. If it is dominated by the latch |
| 39 | // block, use the post-inc value. |
| 40 | if (DT->dominates(LatchBlock, User->getParent())) |
| 41 | return true; |
| 42 | |
| 43 | // There is one case we have to be careful of: PHI nodes. These little guys |
| 44 | // can live in blocks that are not dominated by the latch block, but (since |
| 45 | // their uses occur in the predecessor block, not the block the PHI lives in) |
| 46 | // should still use the post-inc value. Check for this case now. |
| 47 | PHINode *PN = dyn_cast<PHINode>(User); |
Dan Gohman | fc3678a | 2010-07-20 17:06:20 +0000 | [diff] [blame] | 48 | if (!PN || !Operand) return false; // not a phi, not dominated by latch block. |
Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 49 | |
Dan Gohman | b7391fa | 2010-07-20 16:34:50 +0000 | [diff] [blame] | 50 | // Look at all of the uses of Operand by the PHI node. If any use corresponds |
| 51 | // to a block that is not dominated by the latch block, give up and use the |
Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 52 | // preincremented value. |
Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 53 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) |
Dan Gohman | b7391fa | 2010-07-20 16:34:50 +0000 | [diff] [blame] | 54 | if (PN->getIncomingValue(i) == Operand && |
Dan Gohman | fb272ad | 2010-07-20 00:57:18 +0000 | [diff] [blame] | 55 | !DT->dominates(LatchBlock, PN->getIncomingBlock(i))) |
| 56 | return false; |
Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 57 | |
Dan Gohman | b7391fa | 2010-07-20 16:34:50 +0000 | [diff] [blame] | 58 | // Okay, all uses of Operand by PN are in predecessor blocks that really are |
Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 59 | // dominated by the latch block. Use the post-incremented value. |
| 60 | return true; |
| 61 | } |
| 62 | |
Andrew Trick | 94f01db | 2011-10-13 17:21:09 +0000 | [diff] [blame] | 63 | namespace { |
| 64 | |
| 65 | /// Hold the state used during post-inc expression transformation, including a |
| 66 | /// map of transformed expressions. |
| 67 | class PostIncTransform { |
| 68 | TransformKind Kind; |
| 69 | PostIncLoopSet &Loops; |
| 70 | ScalarEvolution &SE; |
| 71 | DominatorTree &DT; |
| 72 | |
| 73 | DenseMap<const SCEV*, const SCEV*> Transformed; |
| 74 | |
| 75 | public: |
| 76 | PostIncTransform(TransformKind kind, PostIncLoopSet &loops, |
| 77 | ScalarEvolution &se, DominatorTree &dt): |
| 78 | Kind(kind), Loops(loops), SE(se), DT(dt) {} |
| 79 | |
| 80 | const SCEV *TransformSubExpr(const SCEV *S, Instruction *User, |
| 81 | Value *OperandValToReplace); |
| 82 | |
| 83 | protected: |
| 84 | const SCEV *TransformImpl(const SCEV *S, Instruction *User, |
| 85 | Value *OperandValToReplace); |
| 86 | }; |
| 87 | |
| 88 | } // namespace |
| 89 | |
| 90 | /// Implement post-inc transformation for all valid expression types. |
| 91 | const SCEV *PostIncTransform:: |
| 92 | TransformImpl(const SCEV *S, Instruction *User, Value *OperandValToReplace) { |
Dan Gohman | 082d6b6 | 2010-07-20 16:32:11 +0000 | [diff] [blame] | 93 | |
Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 94 | if (const SCEVCastExpr *X = dyn_cast<SCEVCastExpr>(S)) { |
| 95 | const SCEV *O = X->getOperand(); |
Andrew Trick | 94f01db | 2011-10-13 17:21:09 +0000 | [diff] [blame] | 96 | const SCEV *N = TransformSubExpr(O, User, OperandValToReplace); |
Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 97 | if (O != N) |
| 98 | switch (S->getSCEVType()) { |
| 99 | case scZeroExtend: return SE.getZeroExtendExpr(N, S->getType()); |
| 100 | case scSignExtend: return SE.getSignExtendExpr(N, S->getType()); |
| 101 | case scTruncate: return SE.getTruncateExpr(N, S->getType()); |
| 102 | default: llvm_unreachable("Unexpected SCEVCastExpr kind!"); |
| 103 | } |
| 104 | return S; |
| 105 | } |
Dan Gohman | 082d6b6 | 2010-07-20 16:32:11 +0000 | [diff] [blame] | 106 | |
Dan Gohman | fc3678a | 2010-07-20 17:06:20 +0000 | [diff] [blame] | 107 | if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { |
| 108 | // An addrec. This is the interesting part. |
| 109 | SmallVector<const SCEV *, 8> Operands; |
| 110 | const Loop *L = AR->getLoop(); |
| 111 | // The addrec conceptually uses its operands at loop entry. |
| 112 | Instruction *LUser = L->getHeader()->begin(); |
| 113 | // Transform each operand. |
| 114 | for (SCEVNAryExpr::op_iterator I = AR->op_begin(), E = AR->op_end(); |
| 115 | I != E; ++I) { |
Andrew Trick | 94f01db | 2011-10-13 17:21:09 +0000 | [diff] [blame] | 116 | Operands.push_back(TransformSubExpr(*I, LUser, 0)); |
Dan Gohman | fc3678a | 2010-07-20 17:06:20 +0000 | [diff] [blame] | 117 | } |
Andrew Trick | 3228cc2 | 2011-03-14 16:50:06 +0000 | [diff] [blame] | 118 | // Conservatively use AnyWrap until/unless we need FlagNW. |
| 119 | const SCEV *Result = SE.getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); |
Dan Gohman | fc3678a | 2010-07-20 17:06:20 +0000 | [diff] [blame] | 120 | switch (Kind) { |
| 121 | default: llvm_unreachable("Unexpected transform name!"); |
| 122 | case NormalizeAutodetect: |
| 123 | if (IVUseShouldUsePostIncValue(User, OperandValToReplace, L, &DT)) { |
| 124 | const SCEV *TransformedStep = |
Andrew Trick | 94f01db | 2011-10-13 17:21:09 +0000 | [diff] [blame] | 125 | TransformSubExpr(AR->getStepRecurrence(SE), |
| 126 | User, OperandValToReplace); |
Dan Gohman | fc3678a | 2010-07-20 17:06:20 +0000 | [diff] [blame] | 127 | Result = SE.getMinusSCEV(Result, TransformedStep); |
| 128 | Loops.insert(L); |
| 129 | } |
Dan Gohman | 46ffb23 | 2010-09-03 22:12:56 +0000 | [diff] [blame] | 130 | #if 0 |
| 131 | // This assert is conceptually correct, but ScalarEvolution currently |
| 132 | // sometimes fails to canonicalize two equal SCEVs to exactly the same |
| 133 | // form. It's possibly a pessimization when this happens, but it isn't a |
| 134 | // correctness problem, so disable this assert for now. |
Andrew Trick | 94f01db | 2011-10-13 17:21:09 +0000 | [diff] [blame] | 135 | assert(S == TransformSubExpr(Result, User, OperandValToReplace) && |
Dan Gohman | fc3678a | 2010-07-20 17:06:20 +0000 | [diff] [blame] | 136 | "SCEV normalization is not invertible!"); |
| 137 | #endif |
| 138 | break; |
| 139 | case Normalize: |
| 140 | if (Loops.count(L)) { |
| 141 | const SCEV *TransformedStep = |
Andrew Trick | 94f01db | 2011-10-13 17:21:09 +0000 | [diff] [blame] | 142 | TransformSubExpr(AR->getStepRecurrence(SE), |
| 143 | User, OperandValToReplace); |
Dan Gohman | fc3678a | 2010-07-20 17:06:20 +0000 | [diff] [blame] | 144 | Result = SE.getMinusSCEV(Result, TransformedStep); |
| 145 | } |
Dan Gohman | 46ffb23 | 2010-09-03 22:12:56 +0000 | [diff] [blame] | 146 | #if 0 |
| 147 | // See the comment on the assert above. |
Andrew Trick | 94f01db | 2011-10-13 17:21:09 +0000 | [diff] [blame] | 148 | assert(S == TransformSubExpr(Result, User, OperandValToReplace) && |
Dan Gohman | fc3678a | 2010-07-20 17:06:20 +0000 | [diff] [blame] | 149 | "SCEV normalization is not invertible!"); |
| 150 | #endif |
| 151 | break; |
| 152 | case Denormalize: |
| 153 | if (Loops.count(L)) |
| 154 | Result = cast<SCEVAddRecExpr>(Result)->getPostIncExpr(SE); |
| 155 | break; |
| 156 | } |
| 157 | return Result; |
| 158 | } |
| 159 | |
Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 160 | if (const SCEVNAryExpr *X = dyn_cast<SCEVNAryExpr>(S)) { |
| 161 | SmallVector<const SCEV *, 8> Operands; |
| 162 | bool Changed = false; |
Dan Gohman | 082d6b6 | 2010-07-20 16:32:11 +0000 | [diff] [blame] | 163 | // Transform each operand. |
Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 164 | for (SCEVNAryExpr::op_iterator I = X->op_begin(), E = X->op_end(); |
| 165 | I != E; ++I) { |
| 166 | const SCEV *O = *I; |
Andrew Trick | 94f01db | 2011-10-13 17:21:09 +0000 | [diff] [blame] | 167 | const SCEV *N = TransformSubExpr(O, User, OperandValToReplace); |
Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 168 | Changed |= N != O; |
| 169 | Operands.push_back(N); |
| 170 | } |
Dan Gohman | fc3678a | 2010-07-20 17:06:20 +0000 | [diff] [blame] | 171 | // If any operand actually changed, return a transformed result. |
Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 172 | if (Changed) |
| 173 | switch (S->getSCEVType()) { |
| 174 | case scAddExpr: return SE.getAddExpr(Operands); |
| 175 | case scMulExpr: return SE.getMulExpr(Operands); |
| 176 | case scSMaxExpr: return SE.getSMaxExpr(Operands); |
| 177 | case scUMaxExpr: return SE.getUMaxExpr(Operands); |
| 178 | default: llvm_unreachable("Unexpected SCEVNAryExpr kind!"); |
| 179 | } |
| 180 | return S; |
| 181 | } |
Dan Gohman | 082d6b6 | 2010-07-20 16:32:11 +0000 | [diff] [blame] | 182 | |
Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 183 | if (const SCEVUDivExpr *X = dyn_cast<SCEVUDivExpr>(S)) { |
| 184 | const SCEV *LO = X->getLHS(); |
| 185 | const SCEV *RO = X->getRHS(); |
Andrew Trick | 94f01db | 2011-10-13 17:21:09 +0000 | [diff] [blame] | 186 | const SCEV *LN = TransformSubExpr(LO, User, OperandValToReplace); |
| 187 | const SCEV *RN = TransformSubExpr(RO, User, OperandValToReplace); |
Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 188 | if (LO != LN || RO != RN) |
| 189 | return SE.getUDivExpr(LN, RN); |
| 190 | return S; |
| 191 | } |
Dan Gohman | 082d6b6 | 2010-07-20 16:32:11 +0000 | [diff] [blame] | 192 | |
Dan Gohman | 448db1c | 2010-04-07 22:27:08 +0000 | [diff] [blame] | 193 | llvm_unreachable("Unexpected SCEV kind!"); |
| 194 | return 0; |
| 195 | } |
Andrew Trick | 94f01db | 2011-10-13 17:21:09 +0000 | [diff] [blame] | 196 | |
| 197 | /// Manage recursive transformation across an expression DAG. Revisiting |
| 198 | /// expressions would lead to exponential recursion. |
| 199 | const SCEV *PostIncTransform:: |
| 200 | TransformSubExpr(const SCEV *S, Instruction *User, Value *OperandValToReplace) { |
| 201 | |
| 202 | if (isa<SCEVConstant>(S) || isa<SCEVUnknown>(S)) |
| 203 | return S; |
| 204 | |
Andrew Trick | 7f1653a | 2011-10-13 18:49:23 +0000 | [diff] [blame] | 205 | const SCEV *Result = Transformed.lookup(S); |
| 206 | if (Result) |
| 207 | return Result; |
Andrew Trick | 94f01db | 2011-10-13 17:21:09 +0000 | [diff] [blame] | 208 | |
Andrew Trick | 7f1653a | 2011-10-13 18:49:23 +0000 | [diff] [blame] | 209 | Result = TransformImpl(S, User, OperandValToReplace); |
| 210 | Transformed[S] = Result; |
| 211 | return Result; |
Andrew Trick | 94f01db | 2011-10-13 17:21:09 +0000 | [diff] [blame] | 212 | } |
| 213 | |
| 214 | /// Top level driver for transforming an expression DAG into its requested |
| 215 | /// post-inc form (either "Normalized" or "Denormalized". |
| 216 | const SCEV *llvm::TransformForPostIncUse(TransformKind Kind, |
| 217 | const SCEV *S, |
| 218 | Instruction *User, |
| 219 | Value *OperandValToReplace, |
| 220 | PostIncLoopSet &Loops, |
| 221 | ScalarEvolution &SE, |
| 222 | DominatorTree &DT) { |
| 223 | PostIncTransform Transform(Kind, Loops, SE, DT); |
| 224 | return Transform.TransformSubExpr(S, User, OperandValToReplace); |
| 225 | } |