ScalarEvolutionNormalization.cpp revision 46ffb231c6c46f093e0485415f01a1a99f31c8be
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" 19using 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). 29static bool IVUseShouldUsePostIncValue(Instruction *User, Value *Operand, 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); 48 if (!PN || !Operand) return false; // not a phi, not dominated by latch block. 49 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 52 // preincremented value. 53 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 54 if (PN->getIncomingValue(i) == Operand && 55 !DT->dominates(LatchBlock, PN->getIncomingBlock(i))) 56 return false; 57 58 // Okay, all uses of Operand by PN are in predecessor blocks that really are 59 // dominated by the latch block. Use the post-incremented value. 60 return true; 61} 62 63const SCEV *llvm::TransformForPostIncUse(TransformKind Kind, 64 const SCEV *S, 65 Instruction *User, 66 Value *OperandValToReplace, 67 PostIncLoopSet &Loops, 68 ScalarEvolution &SE, 69 DominatorTree &DT) { 70 if (isa<SCEVConstant>(S) || isa<SCEVUnknown>(S)) 71 return S; 72 73 if (const SCEVCastExpr *X = dyn_cast<SCEVCastExpr>(S)) { 74 const SCEV *O = X->getOperand(); 75 const SCEV *N = TransformForPostIncUse(Kind, O, User, OperandValToReplace, 76 Loops, SE, DT); 77 if (O != N) 78 switch (S->getSCEVType()) { 79 case scZeroExtend: return SE.getZeroExtendExpr(N, S->getType()); 80 case scSignExtend: return SE.getSignExtendExpr(N, S->getType()); 81 case scTruncate: return SE.getTruncateExpr(N, S->getType()); 82 default: llvm_unreachable("Unexpected SCEVCastExpr kind!"); 83 } 84 return S; 85 } 86 87 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 88 // An addrec. This is the interesting part. 89 SmallVector<const SCEV *, 8> Operands; 90 const Loop *L = AR->getLoop(); 91 // The addrec conceptually uses its operands at loop entry. 92 Instruction *LUser = L->getHeader()->begin(); 93 // Transform each operand. 94 for (SCEVNAryExpr::op_iterator I = AR->op_begin(), E = AR->op_end(); 95 I != E; ++I) { 96 const SCEV *O = *I; 97 const SCEV *N = TransformForPostIncUse(Kind, O, LUser, 0, Loops, SE, DT); 98 Operands.push_back(N); 99 } 100 const SCEV *Result = SE.getAddRecExpr(Operands, L); 101 switch (Kind) { 102 default: llvm_unreachable("Unexpected transform name!"); 103 case NormalizeAutodetect: 104 if (IVUseShouldUsePostIncValue(User, OperandValToReplace, L, &DT)) { 105 const SCEV *TransformedStep = 106 TransformForPostIncUse(Kind, AR->getStepRecurrence(SE), 107 User, OperandValToReplace, Loops, SE, DT); 108 Result = SE.getMinusSCEV(Result, TransformedStep); 109 Loops.insert(L); 110 } 111#if 0 112 // This assert is conceptually correct, but ScalarEvolution currently 113 // sometimes fails to canonicalize two equal SCEVs to exactly the same 114 // form. It's possibly a pessimization when this happens, but it isn't a 115 // correctness problem, so disable this assert for now. 116 assert(S == TransformForPostIncUse(Denormalize, Result, 117 User, OperandValToReplace, 118 Loops, SE, DT) && 119 "SCEV normalization is not invertible!"); 120#endif 121 break; 122 case Normalize: 123 if (Loops.count(L)) { 124 const SCEV *TransformedStep = 125 TransformForPostIncUse(Kind, AR->getStepRecurrence(SE), 126 User, OperandValToReplace, Loops, SE, DT); 127 Result = SE.getMinusSCEV(Result, TransformedStep); 128 } 129#if 0 130 // See the comment on the assert above. 131 assert(S == TransformForPostIncUse(Denormalize, Result, 132 User, OperandValToReplace, 133 Loops, SE, DT) && 134 "SCEV normalization is not invertible!"); 135#endif 136 break; 137 case Denormalize: 138 if (Loops.count(L)) 139 Result = cast<SCEVAddRecExpr>(Result)->getPostIncExpr(SE); 140 break; 141 } 142 return Result; 143 } 144 145 if (const SCEVNAryExpr *X = dyn_cast<SCEVNAryExpr>(S)) { 146 SmallVector<const SCEV *, 8> Operands; 147 bool Changed = false; 148 // Transform each operand. 149 for (SCEVNAryExpr::op_iterator I = X->op_begin(), E = X->op_end(); 150 I != E; ++I) { 151 const SCEV *O = *I; 152 const SCEV *N = TransformForPostIncUse(Kind, O, User, OperandValToReplace, 153 Loops, SE, DT); 154 Changed |= N != O; 155 Operands.push_back(N); 156 } 157 // If any operand actually changed, return a transformed result. 158 if (Changed) 159 switch (S->getSCEVType()) { 160 case scAddExpr: return SE.getAddExpr(Operands); 161 case scMulExpr: return SE.getMulExpr(Operands); 162 case scSMaxExpr: return SE.getSMaxExpr(Operands); 163 case scUMaxExpr: return SE.getUMaxExpr(Operands); 164 default: llvm_unreachable("Unexpected SCEVNAryExpr kind!"); 165 } 166 return S; 167 } 168 169 if (const SCEVUDivExpr *X = dyn_cast<SCEVUDivExpr>(S)) { 170 const SCEV *LO = X->getLHS(); 171 const SCEV *RO = X->getRHS(); 172 const SCEV *LN = TransformForPostIncUse(Kind, LO, User, OperandValToReplace, 173 Loops, SE, DT); 174 const SCEV *RN = TransformForPostIncUse(Kind, RO, User, OperandValToReplace, 175 Loops, SE, DT); 176 if (LO != LN || RO != RN) 177 return SE.getUDivExpr(LN, RN); 178 return S; 179 } 180 181 llvm_unreachable("Unexpected SCEV kind!"); 182 return 0; 183} 184