1 //===- LoopVR.cpp - Value Range analysis driven by loop information -------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // FIXME: What does this do?
12 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "loopvr"
15 #include "llvm/Analysis/LoopVR.h"
16 #include "llvm/Constants.h"
17 #include "llvm/Instructions.h"
18 #include "llvm/LLVMContext.h"
19 #include "llvm/Analysis/LoopInfo.h"
20 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
21 #include "llvm/Assembly/Writer.h"
22 #include "llvm/Support/CFG.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/raw_ostream.h"
28 static RegisterPass<LoopVR> X("loopvr", "Loop Value Ranges", false, true);
30 /// getRange - determine the range for a particular SCEV within a given Loop
31 ConstantRange LoopVR::getRange(const SCEV *S, Loop *L, ScalarEvolution &SE) {
32 const SCEV *T = SE.getBackedgeTakenCount(L);
33 if (isa<SCEVCouldNotCompute>(T))
34 return ConstantRange(cast<IntegerType>(S->getType())->getBitWidth(), true);
36 T = SE.getTruncateOrZeroExtend(T, S->getType());
37 return getRange(S, T, SE);
40 /// getRange - determine the range for a particular SCEV with a given trip count
41 ConstantRange LoopVR::getRange(const SCEV *S, const SCEV *T, ScalarEvolution &SE){
43 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
44 return ConstantRange(C->getValue()->getValue());
46 LLVMContext &Context = SE.getContext();
48 ConstantRange FullSet(cast<IntegerType>(S->getType())->getBitWidth(), true);
50 // {x,+,y,+,...z}. We detect overflow by checking the size of the set after
51 // summing the upper and lower.
52 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
53 ConstantRange X = getRange(Add->getOperand(0), T, SE);
54 if (X.isFullSet()) return FullSet;
55 for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) {
56 ConstantRange Y = getRange(Add->getOperand(i), T, SE);
57 if (Y.isFullSet()) return FullSet;
59 APInt Spread_X = X.getSetSize(), Spread_Y = Y.getSetSize();
60 APInt NewLower = X.getLower() + Y.getLower();
61 APInt NewUpper = X.getUpper() + Y.getUpper() - 1;
62 if (NewLower == NewUpper)
65 X = ConstantRange(NewLower, NewUpper);
66 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
67 return FullSet; // we've wrapped, therefore, full set.
72 // {x,*,y,*,...,z}. In order to detect overflow, we use k*bitwidth where
73 // k is the number of terms being multiplied.
74 if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
75 ConstantRange X = getRange(Mul->getOperand(0), T, SE);
76 if (X.isFullSet()) return FullSet;
78 const IntegerType *Ty = Context.getIntegerType(X.getBitWidth());
79 const IntegerType *ExTy = Context.getIntegerType(X.getBitWidth() *
80 Mul->getNumOperands());
81 ConstantRange XExt = X.zeroExtend(ExTy->getBitWidth());
83 for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i) {
84 ConstantRange Y = getRange(Mul->getOperand(i), T, SE);
85 if (Y.isFullSet()) return FullSet;
87 ConstantRange YExt = Y.zeroExtend(ExTy->getBitWidth());
88 XExt = ConstantRange(XExt.getLower() * YExt.getLower(),
89 ((XExt.getUpper()-1) * (YExt.getUpper()-1)) + 1);
91 return XExt.truncate(Ty->getBitWidth());
94 // X smax Y smax ... Z is: range(smax(X_smin, Y_smin, ..., Z_smin),
95 // smax(X_smax, Y_smax, ..., Z_smax))
96 // It doesn't matter if one of the SCEVs has FullSet because we're taking
97 // a maximum of the minimums across all of them.
98 if (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) {
99 ConstantRange X = getRange(SMax->getOperand(0), T, SE);
100 if (X.isFullSet()) return FullSet;
102 APInt smin = X.getSignedMin(), smax = X.getSignedMax();
103 for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i) {
104 ConstantRange Y = getRange(SMax->getOperand(i), T, SE);
105 smin = APIntOps::smax(smin, Y.getSignedMin());
106 smax = APIntOps::smax(smax, Y.getSignedMax());
108 if (smax + 1 == smin) return FullSet;
109 return ConstantRange(smin, smax + 1);
112 // X umax Y umax ... Z is: range(umax(X_umin, Y_umin, ..., Z_umin),
113 // umax(X_umax, Y_umax, ..., Z_umax))
114 // It doesn't matter if one of the SCEVs has FullSet because we're taking
115 // a maximum of the minimums across all of them.
116 if (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) {
117 ConstantRange X = getRange(UMax->getOperand(0), T, SE);
118 if (X.isFullSet()) return FullSet;
120 APInt umin = X.getUnsignedMin(), umax = X.getUnsignedMax();
121 for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i) {
122 ConstantRange Y = getRange(UMax->getOperand(i), T, SE);
123 umin = APIntOps::umax(umin, Y.getUnsignedMin());
124 umax = APIntOps::umax(umax, Y.getUnsignedMax());
126 if (umax + 1 == umin) return FullSet;
127 return ConstantRange(umin, umax + 1);
130 // L udiv R. Luckily, there's only ever 2 sides to a udiv.
131 if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
132 ConstantRange L = getRange(UDiv->getLHS(), T, SE);
133 ConstantRange R = getRange(UDiv->getRHS(), T, SE);
134 if (L.isFullSet() && R.isFullSet()) return FullSet;
136 if (R.getUnsignedMax() == 0) {
137 // RHS must be single-element zero. Return an empty set.
138 return ConstantRange(R.getBitWidth(), false);
141 APInt Lower = L.getUnsignedMin().udiv(R.getUnsignedMax());
145 if (R.getUnsignedMin() == 0) {
146 // Just because it contains zero, doesn't mean it will also contain one.
147 ConstantRange NotZero(APInt(L.getBitWidth(), 1),
148 APInt::getNullValue(L.getBitWidth()));
149 R = R.intersectWith(NotZero);
152 // But, the intersection might still include zero. If it does, then we know
153 // it also included one.
154 if (R.contains(APInt::getNullValue(L.getBitWidth())))
155 Upper = L.getUnsignedMax();
157 Upper = L.getUnsignedMax().udiv(R.getUnsignedMin());
159 return ConstantRange(Lower, Upper);
162 // ConstantRange already implements the cast operators.
164 if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) {
165 T = SE.getTruncateOrZeroExtend(T, ZExt->getOperand()->getType());
166 ConstantRange X = getRange(ZExt->getOperand(), T, SE);
167 return X.zeroExtend(cast<IntegerType>(ZExt->getType())->getBitWidth());
170 if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) {
171 T = SE.getTruncateOrZeroExtend(T, SExt->getOperand()->getType());
172 ConstantRange X = getRange(SExt->getOperand(), T, SE);
173 return X.signExtend(cast<IntegerType>(SExt->getType())->getBitWidth());
176 if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) {
177 T = SE.getTruncateOrZeroExtend(T, Trunc->getOperand()->getType());
178 ConstantRange X = getRange(Trunc->getOperand(), T, SE);
179 if (X.isFullSet()) return FullSet;
180 return X.truncate(cast<IntegerType>(Trunc->getType())->getBitWidth());
183 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
184 const SCEVConstant *Trip = dyn_cast<SCEVConstant>(T);
185 if (!Trip) return FullSet;
187 if (AddRec->isAffine()) {
188 const SCEV *StartHandle = AddRec->getStart();
189 const SCEV *StepHandle = AddRec->getOperand(1);
191 const SCEVConstant *Step = dyn_cast<SCEVConstant>(StepHandle);
192 if (!Step) return FullSet;
194 uint32_t ExWidth = 2 * Trip->getValue()->getBitWidth();
195 APInt TripExt = Trip->getValue()->getValue(); TripExt.zext(ExWidth);
196 APInt StepExt = Step->getValue()->getValue(); StepExt.zext(ExWidth);
197 if ((TripExt * StepExt).ugt(APInt::getLowBitsSet(ExWidth, ExWidth >> 1)))
200 const SCEV *EndHandle = SE.getAddExpr(StartHandle,
201 SE.getMulExpr(T, StepHandle));
202 const SCEVConstant *Start = dyn_cast<SCEVConstant>(StartHandle);
203 const SCEVConstant *End = dyn_cast<SCEVConstant>(EndHandle);
204 if (!Start || !End) return FullSet;
206 const APInt &StartInt = Start->getValue()->getValue();
207 const APInt &EndInt = End->getValue()->getValue();
208 const APInt &StepInt = Step->getValue()->getValue();
210 if (StepInt.isNegative()) {
211 if (EndInt == StartInt + 1) return FullSet;
212 return ConstantRange(EndInt, StartInt + 1);
214 if (StartInt == EndInt + 1) return FullSet;
215 return ConstantRange(StartInt, EndInt + 1);
220 // TODO: non-affine addrec, udiv, SCEVUnknown (narrowed from elsewhere)?
225 void LoopVR::getAnalysisUsage(AnalysisUsage &AU) const {
226 AU.addRequiredTransitive<LoopInfo>();
227 AU.addRequiredTransitive<ScalarEvolution>();
228 AU.setPreservesAll();
231 bool LoopVR::runOnFunction(Function &F) { Map.clear(); return false; }
233 void LoopVR::print(std::ostream &os, const Module *) const {
234 raw_os_ostream OS(os);
235 for (std::map<Value *, ConstantRange *>::const_iterator I = Map.begin(),
236 E = Map.end(); I != E; ++I) {
237 OS << *I->first << ": " << *I->second << '\n';
241 void LoopVR::releaseMemory() {
242 for (std::map<Value *, ConstantRange *>::iterator I = Map.begin(),
243 E = Map.end(); I != E; ++I) {
250 ConstantRange LoopVR::compute(Value *V) {
251 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
252 return ConstantRange(CI->getValue());
254 Instruction *I = dyn_cast<Instruction>(V);
256 return ConstantRange(cast<IntegerType>(V->getType())->getBitWidth(), false);
258 LoopInfo &LI = getAnalysis<LoopInfo>();
260 Loop *L = LI.getLoopFor(I->getParent());
261 if (!L || L->isLoopInvariant(I))
262 return ConstantRange(cast<IntegerType>(V->getType())->getBitWidth(), false);
264 ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
266 const SCEV *S = SE.getSCEV(I);
267 if (isa<SCEVUnknown>(S) || isa<SCEVCouldNotCompute>(S))
268 return ConstantRange(cast<IntegerType>(V->getType())->getBitWidth(), false);
270 return ConstantRange(getRange(S, L, SE));
273 ConstantRange LoopVR::get(Value *V) {
274 std::map<Value *, ConstantRange *>::iterator I = Map.find(V);
275 if (I == Map.end()) {
276 ConstantRange *CR = new ConstantRange(compute(V));
284 void LoopVR::remove(Value *V) {
285 std::map<Value *, ConstantRange *>::iterator I = Map.find(V);
286 if (I != Map.end()) {
292 void LoopVR::narrow(Value *V, const ConstantRange &CR) {
293 if (CR.isFullSet()) return;
295 std::map<Value *, ConstantRange *>::iterator I = Map.find(V);
297 Map[V] = new ConstantRange(CR);
299 Map[V] = new ConstantRange(Map[V]->intersectWith(CR));