1207618Srdivacky//===- ScalarEvolutionNormalization.cpp - See below -------------*- C++ -*-===// 2207618Srdivacky// 3207618Srdivacky// The LLVM Compiler Infrastructure 4207618Srdivacky// 5207618Srdivacky// This file is distributed under the University of Illinois Open Source 6207618Srdivacky// License. See LICENSE.TXT for details. 7207618Srdivacky// 8207618Srdivacky//===----------------------------------------------------------------------===// 9207618Srdivacky// 10207618Srdivacky// This file implements utilities for working with "normalized" expressions. 11207618Srdivacky// See the comments at the top of ScalarEvolutionNormalization.h for details. 12207618Srdivacky// 13207618Srdivacky//===----------------------------------------------------------------------===// 14207618Srdivacky 15207618Srdivacky#include "llvm/Analysis/Dominators.h" 16207618Srdivacky#include "llvm/Analysis/LoopInfo.h" 17207618Srdivacky#include "llvm/Analysis/ScalarEvolutionExpressions.h" 18207618Srdivacky#include "llvm/Analysis/ScalarEvolutionNormalization.h" 19207618Srdivackyusing namespace llvm; 20207618Srdivacky 21207618Srdivacky/// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression 22207618Srdivacky/// and now we need to decide whether the user should use the preinc or post-inc 23207618Srdivacky/// value. If this user should use the post-inc version of the IV, return true. 24207618Srdivacky/// 25207618Srdivacky/// Choosing wrong here can break dominance properties (if we choose to use the 26207618Srdivacky/// post-inc value when we cannot) or it can end up adding extra live-ranges to 27207618Srdivacky/// the loop, resulting in reg-reg copies (if we use the pre-inc value when we 28207618Srdivacky/// should use the post-inc value). 29212904Sdimstatic bool IVUseShouldUsePostIncValue(Instruction *User, Value *Operand, 30207618Srdivacky const Loop *L, DominatorTree *DT) { 31207618Srdivacky // If the user is in the loop, use the preinc value. 32207618Srdivacky if (L->contains(User)) return false; 33207618Srdivacky 34207618Srdivacky BasicBlock *LatchBlock = L->getLoopLatch(); 35207618Srdivacky if (!LatchBlock) 36207618Srdivacky return false; 37207618Srdivacky 38207618Srdivacky // Ok, the user is outside of the loop. If it is dominated by the latch 39207618Srdivacky // block, use the post-inc value. 40207618Srdivacky if (DT->dominates(LatchBlock, User->getParent())) 41207618Srdivacky return true; 42207618Srdivacky 43207618Srdivacky // There is one case we have to be careful of: PHI nodes. These little guys 44207618Srdivacky // can live in blocks that are not dominated by the latch block, but (since 45207618Srdivacky // their uses occur in the predecessor block, not the block the PHI lives in) 46207618Srdivacky // should still use the post-inc value. Check for this case now. 47207618Srdivacky PHINode *PN = dyn_cast<PHINode>(User); 48212904Sdim if (!PN || !Operand) return false; // not a phi, not dominated by latch block. 49207618Srdivacky 50212904Sdim // Look at all of the uses of Operand by the PHI node. If any use corresponds 51212904Sdim // to a block that is not dominated by the latch block, give up and use the 52207618Srdivacky // preincremented value. 53207618Srdivacky for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 54212904Sdim if (PN->getIncomingValue(i) == Operand && 55212904Sdim !DT->dominates(LatchBlock, PN->getIncomingBlock(i))) 56212904Sdim return false; 57207618Srdivacky 58212904Sdim // Okay, all uses of Operand by PN are in predecessor blocks that really are 59207618Srdivacky // dominated by the latch block. Use the post-incremented value. 60207618Srdivacky return true; 61207618Srdivacky} 62207618Srdivacky 63226633Sdimnamespace { 64212904Sdim 65226633Sdim/// Hold the state used during post-inc expression transformation, including a 66226633Sdim/// map of transformed expressions. 67226633Sdimclass PostIncTransform { 68226633Sdim TransformKind Kind; 69226633Sdim PostIncLoopSet &Loops; 70226633Sdim ScalarEvolution &SE; 71226633Sdim DominatorTree &DT; 72226633Sdim 73226633Sdim DenseMap<const SCEV*, const SCEV*> Transformed; 74226633Sdim 75226633Sdimpublic: 76226633Sdim PostIncTransform(TransformKind kind, PostIncLoopSet &loops, 77226633Sdim ScalarEvolution &se, DominatorTree &dt): 78226633Sdim Kind(kind), Loops(loops), SE(se), DT(dt) {} 79226633Sdim 80226633Sdim const SCEV *TransformSubExpr(const SCEV *S, Instruction *User, 81226633Sdim Value *OperandValToReplace); 82226633Sdim 83226633Sdimprotected: 84226633Sdim const SCEV *TransformImpl(const SCEV *S, Instruction *User, 85226633Sdim Value *OperandValToReplace); 86226633Sdim}; 87226633Sdim 88226633Sdim} // namespace 89226633Sdim 90226633Sdim/// Implement post-inc transformation for all valid expression types. 91226633Sdimconst SCEV *PostIncTransform:: 92226633SdimTransformImpl(const SCEV *S, Instruction *User, Value *OperandValToReplace) { 93226633Sdim 94207618Srdivacky if (const SCEVCastExpr *X = dyn_cast<SCEVCastExpr>(S)) { 95207618Srdivacky const SCEV *O = X->getOperand(); 96226633Sdim const SCEV *N = TransformSubExpr(O, User, OperandValToReplace); 97207618Srdivacky if (O != N) 98207618Srdivacky switch (S->getSCEVType()) { 99207618Srdivacky case scZeroExtend: return SE.getZeroExtendExpr(N, S->getType()); 100207618Srdivacky case scSignExtend: return SE.getSignExtendExpr(N, S->getType()); 101207618Srdivacky case scTruncate: return SE.getTruncateExpr(N, S->getType()); 102207618Srdivacky default: llvm_unreachable("Unexpected SCEVCastExpr kind!"); 103207618Srdivacky } 104207618Srdivacky return S; 105207618Srdivacky } 106212904Sdim 107212904Sdim if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 108212904Sdim // An addrec. This is the interesting part. 109212904Sdim SmallVector<const SCEV *, 8> Operands; 110212904Sdim const Loop *L = AR->getLoop(); 111212904Sdim // The addrec conceptually uses its operands at loop entry. 112212904Sdim Instruction *LUser = L->getHeader()->begin(); 113212904Sdim // Transform each operand. 114212904Sdim for (SCEVNAryExpr::op_iterator I = AR->op_begin(), E = AR->op_end(); 115212904Sdim I != E; ++I) { 116226633Sdim Operands.push_back(TransformSubExpr(*I, LUser, 0)); 117212904Sdim } 118221345Sdim // Conservatively use AnyWrap until/unless we need FlagNW. 119221345Sdim const SCEV *Result = SE.getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); 120212904Sdim switch (Kind) { 121212904Sdim case NormalizeAutodetect: 122263508Sdim // Normalize this SCEV by subtracting the expression for the final step. 123263508Sdim // We only allow affine AddRecs to be normalized, otherwise we would not 124263508Sdim // be able to correctly denormalize. 125263508Sdim // e.g. {1,+,3,+,2} == {-2,+,1,+,2} + {3,+,2} 126263508Sdim // Normalized form: {-2,+,1,+,2} 127263508Sdim // Denormalized form: {1,+,3,+,2} 128263508Sdim // 129263508Sdim // However, denormalization would use the a different step expression than 130263508Sdim // normalization (see getPostIncExpr), generating the wrong final 131263508Sdim // expression: {-2,+,1,+,2} + {1,+,2} => {-1,+,3,+,2} 132263508Sdim if (AR->isAffine() && 133263508Sdim IVUseShouldUsePostIncValue(User, OperandValToReplace, L, &DT)) { 134263508Sdim Result = SE.getMinusSCEV(Result, AR->getStepRecurrence(SE)); 135212904Sdim Loops.insert(L); 136212904Sdim } 137212904Sdim#if 0 138212904Sdim // This assert is conceptually correct, but ScalarEvolution currently 139212904Sdim // sometimes fails to canonicalize two equal SCEVs to exactly the same 140212904Sdim // form. It's possibly a pessimization when this happens, but it isn't a 141212904Sdim // correctness problem, so disable this assert for now. 142226633Sdim assert(S == TransformSubExpr(Result, User, OperandValToReplace) && 143212904Sdim "SCEV normalization is not invertible!"); 144212904Sdim#endif 145212904Sdim break; 146212904Sdim case Normalize: 147212904Sdim if (Loops.count(L)) { 148212904Sdim const SCEV *TransformedStep = 149226633Sdim TransformSubExpr(AR->getStepRecurrence(SE), 150226633Sdim User, OperandValToReplace); 151212904Sdim Result = SE.getMinusSCEV(Result, TransformedStep); 152212904Sdim } 153212904Sdim#if 0 154212904Sdim // See the comment on the assert above. 155226633Sdim assert(S == TransformSubExpr(Result, User, OperandValToReplace) && 156212904Sdim "SCEV normalization is not invertible!"); 157212904Sdim#endif 158212904Sdim break; 159212904Sdim case Denormalize: 160212904Sdim if (Loops.count(L)) 161212904Sdim Result = cast<SCEVAddRecExpr>(Result)->getPostIncExpr(SE); 162212904Sdim break; 163212904Sdim } 164212904Sdim return Result; 165212904Sdim } 166212904Sdim 167207618Srdivacky if (const SCEVNAryExpr *X = dyn_cast<SCEVNAryExpr>(S)) { 168207618Srdivacky SmallVector<const SCEV *, 8> Operands; 169207618Srdivacky bool Changed = false; 170212904Sdim // Transform each operand. 171207618Srdivacky for (SCEVNAryExpr::op_iterator I = X->op_begin(), E = X->op_end(); 172207618Srdivacky I != E; ++I) { 173207618Srdivacky const SCEV *O = *I; 174226633Sdim const SCEV *N = TransformSubExpr(O, User, OperandValToReplace); 175207618Srdivacky Changed |= N != O; 176207618Srdivacky Operands.push_back(N); 177207618Srdivacky } 178212904Sdim // If any operand actually changed, return a transformed result. 179207618Srdivacky if (Changed) 180207618Srdivacky switch (S->getSCEVType()) { 181207618Srdivacky case scAddExpr: return SE.getAddExpr(Operands); 182207618Srdivacky case scMulExpr: return SE.getMulExpr(Operands); 183207618Srdivacky case scSMaxExpr: return SE.getSMaxExpr(Operands); 184207618Srdivacky case scUMaxExpr: return SE.getUMaxExpr(Operands); 185207618Srdivacky default: llvm_unreachable("Unexpected SCEVNAryExpr kind!"); 186207618Srdivacky } 187207618Srdivacky return S; 188207618Srdivacky } 189212904Sdim 190207618Srdivacky if (const SCEVUDivExpr *X = dyn_cast<SCEVUDivExpr>(S)) { 191207618Srdivacky const SCEV *LO = X->getLHS(); 192207618Srdivacky const SCEV *RO = X->getRHS(); 193226633Sdim const SCEV *LN = TransformSubExpr(LO, User, OperandValToReplace); 194226633Sdim const SCEV *RN = TransformSubExpr(RO, User, OperandValToReplace); 195207618Srdivacky if (LO != LN || RO != RN) 196207618Srdivacky return SE.getUDivExpr(LN, RN); 197207618Srdivacky return S; 198207618Srdivacky } 199212904Sdim 200207618Srdivacky llvm_unreachable("Unexpected SCEV kind!"); 201207618Srdivacky} 202226633Sdim 203226633Sdim/// Manage recursive transformation across an expression DAG. Revisiting 204226633Sdim/// expressions would lead to exponential recursion. 205226633Sdimconst SCEV *PostIncTransform:: 206226633SdimTransformSubExpr(const SCEV *S, Instruction *User, Value *OperandValToReplace) { 207226633Sdim 208226633Sdim if (isa<SCEVConstant>(S) || isa<SCEVUnknown>(S)) 209226633Sdim return S; 210226633Sdim 211226633Sdim const SCEV *Result = Transformed.lookup(S); 212226633Sdim if (Result) 213226633Sdim return Result; 214226633Sdim 215226633Sdim Result = TransformImpl(S, User, OperandValToReplace); 216226633Sdim Transformed[S] = Result; 217226633Sdim return Result; 218226633Sdim} 219226633Sdim 220226633Sdim/// Top level driver for transforming an expression DAG into its requested 221226633Sdim/// post-inc form (either "Normalized" or "Denormalized". 222226633Sdimconst SCEV *llvm::TransformForPostIncUse(TransformKind Kind, 223226633Sdim const SCEV *S, 224226633Sdim Instruction *User, 225226633Sdim Value *OperandValToReplace, 226226633Sdim PostIncLoopSet &Loops, 227226633Sdim ScalarEvolution &SE, 228226633Sdim DominatorTree &DT) { 229226633Sdim PostIncTransform Transform(Kind, Loops, SE, DT); 230226633Sdim return Transform.TransformSubExpr(S, User, OperandValToReplace); 231226633Sdim} 232