LLVM API Documentation
00001 //===- LoopVR.cpp - Value Range analysis driven by loop information -------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // FIXME: What does this do? 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #define DEBUG_TYPE "loopvr" 00015 #include "llvm/Analysis/LoopVR.h" 00016 #include "llvm/Constants.h" 00017 #include "llvm/Instructions.h" 00018 #include "llvm/LLVMContext.h" 00019 #include "llvm/Analysis/LoopInfo.h" 00020 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 00021 #include "llvm/Assembly/Writer.h" 00022 #include "llvm/Support/CFG.h" 00023 #include "llvm/Support/Debug.h" 00024 #include "llvm/Support/raw_ostream.h" 00025 using namespace llvm; 00026 00027 char LoopVR::ID = 0; 00028 static RegisterPass<LoopVR> X("loopvr", "Loop Value Ranges", false, true); 00029 00030 /// getRange - determine the range for a particular SCEV within a given Loop 00031 ConstantRange LoopVR::getRange(const SCEV *S, Loop *L, ScalarEvolution &SE) { 00032 const SCEV *T = SE.getBackedgeTakenCount(L); 00033 if (isa<SCEVCouldNotCompute>(T)) 00034 return ConstantRange(cast<IntegerType>(S->getType())->getBitWidth(), true); 00035 00036 T = SE.getTruncateOrZeroExtend(T, S->getType()); 00037 return getRange(S, T, SE); 00038 } 00039 00040 /// getRange - determine the range for a particular SCEV with a given trip count 00041 ConstantRange LoopVR::getRange(const SCEV *S, const SCEV *T, ScalarEvolution &SE){ 00042 00043 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) 00044 return ConstantRange(C->getValue()->getValue()); 00045 00046 ConstantRange FullSet(cast<IntegerType>(S->getType())->getBitWidth(), true); 00047 00048 // {x,+,y,+,...z}. We detect overflow by checking the size of the set after 00049 // summing the upper and lower. 00050 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 00051 ConstantRange X = getRange(Add->getOperand(0), T, SE); 00052 if (X.isFullSet()) return FullSet; 00053 for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) { 00054 ConstantRange Y = getRange(Add->getOperand(i), T, SE); 00055 if (Y.isFullSet()) return FullSet; 00056 00057 APInt Spread_X = X.getSetSize(), Spread_Y = Y.getSetSize(); 00058 APInt NewLower = X.getLower() + Y.getLower(); 00059 APInt NewUpper = X.getUpper() + Y.getUpper() - 1; 00060 if (NewLower == NewUpper) 00061 return FullSet; 00062 00063 X = ConstantRange(NewLower, NewUpper); 00064 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 00065 return FullSet; // we've wrapped, therefore, full set. 00066 } 00067 return X; 00068 } 00069 00070 // {x,*,y,*,...,z}. In order to detect overflow, we use k*bitwidth where 00071 // k is the number of terms being multiplied. 00072 if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) { 00073 ConstantRange X = getRange(Mul->getOperand(0), T, SE); 00074 if (X.isFullSet()) return FullSet; 00075 00076 const IntegerType *Ty = IntegerType::get(SE.getContext(), X.getBitWidth()); 00077 const IntegerType *ExTy = IntegerType::get(SE.getContext(), 00078 X.getBitWidth() * Mul->getNumOperands()); 00079 ConstantRange XExt = X.zeroExtend(ExTy->getBitWidth()); 00080 00081 for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i) { 00082 ConstantRange Y = getRange(Mul->getOperand(i), T, SE); 00083 if (Y.isFullSet()) return FullSet; 00084 00085 ConstantRange YExt = Y.zeroExtend(ExTy->getBitWidth()); 00086 XExt = ConstantRange(XExt.getLower() * YExt.getLower(), 00087 ((XExt.getUpper()-1) * (YExt.getUpper()-1)) + 1); 00088 } 00089 return XExt.truncate(Ty->getBitWidth()); 00090 } 00091 00092 // X smax Y smax ... Z is: range(smax(X_smin, Y_smin, ..., Z_smin), 00093 // smax(X_smax, Y_smax, ..., Z_smax)) 00094 // It doesn't matter if one of the SCEVs has FullSet because we're taking 00095 // a maximum of the minimums across all of them. 00096 if (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) { 00097 ConstantRange X = getRange(SMax->getOperand(0), T, SE); 00098 if (X.isFullSet()) return FullSet; 00099 00100 APInt smin = X.getSignedMin(), smax = X.getSignedMax(); 00101 for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i) { 00102 ConstantRange Y = getRange(SMax->getOperand(i), T, SE); 00103 smin = APIntOps::smax(smin, Y.getSignedMin()); 00104 smax = APIntOps::smax(smax, Y.getSignedMax()); 00105 } 00106 if (smax + 1 == smin) return FullSet; 00107 return ConstantRange(smin, smax + 1); 00108 } 00109 00110 // X umax Y umax ... Z is: range(umax(X_umin, Y_umin, ..., Z_umin), 00111 // umax(X_umax, Y_umax, ..., Z_umax)) 00112 // It doesn't matter if one of the SCEVs has FullSet because we're taking 00113 // a maximum of the minimums across all of them. 00114 if (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) { 00115 ConstantRange X = getRange(UMax->getOperand(0), T, SE); 00116 if (X.isFullSet()) return FullSet; 00117 00118 APInt umin = X.getUnsignedMin(), umax = X.getUnsignedMax(); 00119 for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i) { 00120 ConstantRange Y = getRange(UMax->getOperand(i), T, SE); 00121 umin = APIntOps::umax(umin, Y.getUnsignedMin()); 00122 umax = APIntOps::umax(umax, Y.getUnsignedMax()); 00123 } 00124 if (umax + 1 == umin) return FullSet; 00125 return ConstantRange(umin, umax + 1); 00126 } 00127 00128 // L udiv R. Luckily, there's only ever 2 sides to a udiv. 00129 if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) { 00130 ConstantRange L = getRange(UDiv->getLHS(), T, SE); 00131 ConstantRange R = getRange(UDiv->getRHS(), T, SE); 00132 if (L.isFullSet() && R.isFullSet()) return FullSet; 00133 00134 if (R.getUnsignedMax() == 0) { 00135 // RHS must be single-element zero. Return an empty set. 00136 return ConstantRange(R.getBitWidth(), false); 00137 } 00138 00139 APInt Lower = L.getUnsignedMin().udiv(R.getUnsignedMax()); 00140 00141 APInt Upper; 00142 00143 if (R.getUnsignedMin() == 0) { 00144 // Just because it contains zero, doesn't mean it will also contain one. 00145 ConstantRange NotZero(APInt(L.getBitWidth(), 1), 00146 APInt::getNullValue(L.getBitWidth())); 00147 R = R.intersectWith(NotZero); 00148 } 00149 00150 // But, the intersection might still include zero. If it does, then we know 00151 // it also included one. 00152 if (R.contains(APInt::getNullValue(L.getBitWidth()))) 00153 Upper = L.getUnsignedMax(); 00154 else 00155 Upper = L.getUnsignedMax().udiv(R.getUnsignedMin()); 00156 00157 return ConstantRange(Lower, Upper); 00158 } 00159 00160 // ConstantRange already implements the cast operators. 00161 00162 if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) { 00163 T = SE.getTruncateOrZeroExtend(T, ZExt->getOperand()->getType()); 00164 ConstantRange X = getRange(ZExt->getOperand(), T, SE); 00165 return X.zeroExtend(cast<IntegerType>(ZExt->getType())->getBitWidth()); 00166 } 00167 00168 if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) { 00169 T = SE.getTruncateOrZeroExtend(T, SExt->getOperand()->getType()); 00170 ConstantRange X = getRange(SExt->getOperand(), T, SE); 00171 return X.signExtend(cast<IntegerType>(SExt->getType())->getBitWidth()); 00172 } 00173 00174 if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) { 00175 T = SE.getTruncateOrZeroExtend(T, Trunc->getOperand()->getType()); 00176 ConstantRange X = getRange(Trunc->getOperand(), T, SE); 00177 if (X.isFullSet()) return FullSet; 00178 return X.truncate(cast<IntegerType>(Trunc->getType())->getBitWidth()); 00179 } 00180 00181 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) { 00182 const SCEVConstant *Trip = dyn_cast<SCEVConstant>(T); 00183 if (!Trip) return FullSet; 00184 00185 if (AddRec->isAffine()) { 00186 const SCEV *StartHandle = AddRec->getStart(); 00187 const SCEV *StepHandle = AddRec->getOperand(1); 00188 00189 const SCEVConstant *Step = dyn_cast<SCEVConstant>(StepHandle); 00190 if (!Step) return FullSet; 00191 00192 uint32_t ExWidth = 2 * Trip->getValue()->getBitWidth(); 00193 APInt TripExt = Trip->getValue()->getValue(); TripExt.zext(ExWidth); 00194 APInt StepExt = Step->getValue()->getValue(); StepExt.zext(ExWidth); 00195 if ((TripExt * StepExt).ugt(APInt::getLowBitsSet(ExWidth, ExWidth >> 1))) 00196 return FullSet; 00197 00198 const SCEV *EndHandle = SE.getAddExpr(StartHandle, 00199 SE.getMulExpr(T, StepHandle)); 00200 const SCEVConstant *Start = dyn_cast<SCEVConstant>(StartHandle); 00201 const SCEVConstant *End = dyn_cast<SCEVConstant>(EndHandle); 00202 if (!Start || !End) return FullSet; 00203 00204 const APInt &StartInt = Start->getValue()->getValue(); 00205 const APInt &EndInt = End->getValue()->getValue(); 00206 const APInt &StepInt = Step->getValue()->getValue(); 00207 00208 if (StepInt.isNegative()) { 00209 if (EndInt == StartInt + 1) return FullSet; 00210 return ConstantRange(EndInt, StartInt + 1); 00211 } else { 00212 if (StartInt == EndInt + 1) return FullSet; 00213 return ConstantRange(StartInt, EndInt + 1); 00214 } 00215 } 00216 } 00217 00218 // TODO: non-affine addrec, udiv, SCEVUnknown (narrowed from elsewhere)? 00219 00220 return FullSet; 00221 } 00222 00223 void LoopVR::getAnalysisUsage(AnalysisUsage &AU) const { 00224 AU.addRequiredTransitive<LoopInfo>(); 00225 AU.addRequiredTransitive<ScalarEvolution>(); 00226 AU.setPreservesAll(); 00227 } 00228 00229 bool LoopVR::runOnFunction(Function &F) { Map.clear(); return false; } 00230 00231 void LoopVR::print(std::ostream &os, const Module *) const { 00232 raw_os_ostream OS(os); 00233 for (std::map<Value *, ConstantRange *>::const_iterator I = Map.begin(), 00234 E = Map.end(); I != E; ++I) { 00235 OS << *I->first << ": " << *I->second << '\n'; 00236 } 00237 } 00238 00239 void LoopVR::releaseMemory() { 00240 for (std::map<Value *, ConstantRange *>::iterator I = Map.begin(), 00241 E = Map.end(); I != E; ++I) { 00242 delete I->second; 00243 } 00244 00245 Map.clear(); 00246 } 00247 00248 ConstantRange LoopVR::compute(Value *V) { 00249 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 00250 return ConstantRange(CI->getValue()); 00251 00252 Instruction *I = dyn_cast<Instruction>(V); 00253 if (!I) 00254 return ConstantRange(cast<IntegerType>(V->getType())->getBitWidth(), false); 00255 00256 LoopInfo &LI = getAnalysis<LoopInfo>(); 00257 00258 Loop *L = LI.getLoopFor(I->getParent()); 00259 if (!L || L->isLoopInvariant(I)) 00260 return ConstantRange(cast<IntegerType>(V->getType())->getBitWidth(), false); 00261 00262 ScalarEvolution &SE = getAnalysis<ScalarEvolution>(); 00263 00264 const SCEV *S = SE.getSCEV(I); 00265 if (isa<SCEVUnknown>(S) || isa<SCEVCouldNotCompute>(S)) 00266 return ConstantRange(cast<IntegerType>(V->getType())->getBitWidth(), false); 00267 00268 return ConstantRange(getRange(S, L, SE)); 00269 } 00270 00271 ConstantRange LoopVR::get(Value *V) { 00272 std::map<Value *, ConstantRange *>::iterator I = Map.find(V); 00273 if (I == Map.end()) { 00274 ConstantRange *CR = new ConstantRange(compute(V)); 00275 Map[V] = CR; 00276 return *CR; 00277 } 00278 00279 return *I->second; 00280 } 00281 00282 void LoopVR::remove(Value *V) { 00283 std::map<Value *, ConstantRange *>::iterator I = Map.find(V); 00284 if (I != Map.end()) { 00285 delete I->second; 00286 Map.erase(I); 00287 } 00288 } 00289 00290 void LoopVR::narrow(Value *V, const ConstantRange &CR) { 00291 if (CR.isFullSet()) return; 00292 00293 std::map<Value *, ConstantRange *>::iterator I = Map.find(V); 00294 if (I == Map.end()) 00295 Map[V] = new ConstantRange(CR); 00296 else 00297 Map[V] = new ConstantRange(Map[V]->intersectWith(CR)); 00298 }