lib/Analysis/LoopVR.cpp

   1 //===- LoopVR.cpp - Value Range analysis driven by loop information -------===//
   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 #define DEBUG_TYPE "loopvr"
  11 #include "llvm/Analysis/LoopVR.h"
  12 #include "llvm/Constants.h"
  13 #include "llvm/Instructions.h"
  14 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  15 #include "llvm/Assembly/Writer.h"
  16 #include "llvm/Support/CFG.h"
  17 #include "llvm/Support/Debug.h"
  18 #include "llvm/Support/Streams.h"
  19 using namespace llvm;
  20
  21 char LoopVR::ID = 0;
  22 namespace {
  23 static RegisterPass<LoopVR> X("loopvr", "Loop Value Ranges", true, true);
  24 }
  25
  26 /// getRange - determine the range for a particular SCEV within a given Loop
  27 ConstantRange LoopVR::getRange(SCEVHandle S, Loop *L, ScalarEvolution &SE) {
  28   SCEVHandle T = SE.getIterationCount(L);
  29   if (isa<SCEVCouldNotCompute>(T))
  30     return ConstantRange(cast<IntegerType>(S->getType())->getBitWidth(), true);
  31
  32   T = SE.getTruncateOrZeroExtend(T, S->getType());
  33   return getRange(S, T, SE);
  34 }
  35
  36 /// getRange - determine the range for a particular SCEV with a given trip count
  37 ConstantRange LoopVR::getRange(SCEVHandle S, SCEVHandle T, ScalarEvolution &SE){
  38
  39   if (SCEVConstant *C = dyn_cast<SCEVConstant>(S))
  40     return ConstantRange(C->getValue()->getValue());
  41
  42   ConstantRange FullSet(cast<IntegerType>(S->getType())->getBitWidth(), true);
  43
  44   // {x,+,y,+,...z}. We detect overflow by checking the size of the set after
  45   // summing the upper and lower.
  46   if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
  47     ConstantRange X = getRange(Add->getOperand(0), T, SE);
  48     if (X.isFullSet()) return FullSet;
  49     for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) {
  50       ConstantRange Y = getRange(Add->getOperand(i), T, SE);
  51       if (Y.isFullSet()) return FullSet;
  52
  53       APInt Spread_X = X.getSetSize(), Spread_Y = Y.getSetSize();
  54       APInt NewLower = X.getLower() + Y.getLower();
  55       APInt NewUpper = X.getUpper() + Y.getUpper() - 1;
  56       if (NewLower == NewUpper)
  57         return FullSet;
  58
  59       X = ConstantRange(NewLower, NewUpper);
  60       if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
  61         return FullSet; // we've wrapped, therefore, full set.
  62     }
  63     return X;
  64   }
  65
  66   // {x,*,y,*,...,z}. In order to detect overflow, we use k*bitwidth where
  67   // k is the number of terms being multiplied.
  68   if (SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
  69     ConstantRange X = getRange(Mul->getOperand(0), T, SE);
  70     if (X.isFullSet()) return FullSet;
  71
  72     const IntegerType *Ty = IntegerType::get(X.getBitWidth());
  73     const IntegerType *ExTy = IntegerType::get(X.getBitWidth() *
  74                                                Mul->getNumOperands());
  75     ConstantRange XExt = X.zeroExtend(ExTy->getBitWidth());
  76
  77     for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i) {
  78       ConstantRange Y = getRange(Mul->getOperand(i), T, SE);
  79       if (Y.isFullSet()) return FullSet;
  80
  81       ConstantRange YExt = Y.zeroExtend(ExTy->getBitWidth());
  82       XExt = ConstantRange(XExt.getLower() * YExt.getLower(),
  83                            ((XExt.getUpper()-1) * (YExt.getUpper()-1)) + 1);
  84     }
  85     return XExt.truncate(Ty->getBitWidth());
  86   }
  87
  88   // X smax Y smax ... Z is: range(smax(X_smin, Y_smin, ..., Z_smin),
  89   //                               smax(X_smax, Y_smax, ..., Z_smax))
  90   // It doesn't matter if one of the SCEVs has FullSet because we're taking
  91   // a maximum of the minimums across all of them.
  92   if (SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) {
  93     ConstantRange X = getRange(SMax->getOperand(0), T, SE);
  94     if (X.isFullSet()) return FullSet;
  95
  96     APInt smin = X.getSignedMin(), smax = X.getSignedMax();
  97     for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i) {
  98       ConstantRange Y = getRange(SMax->getOperand(i), T, SE);
  99       smin = APIntOps::smax(smin, Y.getSignedMin());
 100       smax = APIntOps::smax(smax, Y.getSignedMax());
 101     }
 102     if (smax + 1 == smin) return FullSet;
 103     return ConstantRange(smin, smax + 1);
 104   }
 105
 106   // X umax Y umax ... Z is: range(umax(X_umin, Y_umin, ..., Z_umin),
 107   //                               umax(X_umax, Y_umax, ..., Z_umax))
 108   // It doesn't matter if one of the SCEVs has FullSet because we're taking
 109   // a maximum of the minimums across all of them.
 110   if (SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) {
 111     ConstantRange X = getRange(UMax->getOperand(0), T, SE);
 112     if (X.isFullSet()) return FullSet;
 113
 114     APInt umin = X.getUnsignedMin(), umax = X.getUnsignedMax();
 115     for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i) {
 116       ConstantRange Y = getRange(UMax->getOperand(i), T, SE);
 117       umin = APIntOps::umax(umin, Y.getUnsignedMin());
 118       umax = APIntOps::umax(umax, Y.getUnsignedMax());
 119     }
 120     if (umax + 1 == umin) return FullSet;
 121     return ConstantRange(umin, umax + 1);
 122   }
 123
 124   // L udiv R. Luckily, there's only ever 2 sides to a udiv.
 125   if (SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
 126     ConstantRange L = getRange(UDiv->getLHS(), T, SE);
 127     ConstantRange R = getRange(UDiv->getRHS(), T, SE);
 128     if (L.isFullSet() && R.isFullSet()) return FullSet;
 129
 130     if (R.getUnsignedMax() == 0) {
 131       // RHS must be single-element zero. Return an empty set.
 132       return ConstantRange(R.getBitWidth(), false);
 133     }
 134
 135     APInt Lower = L.getUnsignedMin().udiv(R.getUnsignedMax());
 136
 137     APInt Upper;
 138
 139     if (R.getUnsignedMin() == 0) {
 140       // Just because it contains zero, doesn't mean it will also contain one.
 141       // Use maximalIntersectWith to get the right behaviour.
 142       ConstantRange NotZero(APInt(L.getBitWidth(), 1),
 143                             APInt::getNullValue(L.getBitWidth()));
 144       R = R.maximalIntersectWith(NotZero);
 145     }
 146
 147     // But, the maximal intersection might still include zero. If it does, then
 148     // we know it also included one.
 149     if (R.contains(APInt::getNullValue(L.getBitWidth())))
 150       Upper = L.getUnsignedMax();
 151     else
 152       Upper = L.getUnsignedMax().udiv(R.getUnsignedMin());
 153
 154     return ConstantRange(Lower, Upper);
 155   }
 156
 157   // ConstantRange already implements the cast operators.
 158
 159   if (SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) {
 160     T = SE.getTruncateOrZeroExtend(T, ZExt->getOperand()->getType());
 161     ConstantRange X = getRange(ZExt->getOperand(), T, SE);
 162     return X.zeroExtend(cast<IntegerType>(ZExt->getType())->getBitWidth());
 163   }
 164
 165   if (SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) {
 166     T = SE.getTruncateOrZeroExtend(T, SExt->getOperand()->getType());
 167     ConstantRange X = getRange(SExt->getOperand(), T, SE);
 168     return X.signExtend(cast<IntegerType>(SExt->getType())->getBitWidth());
 169   }
 170
 171   if (SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) {
 172     T = SE.getTruncateOrZeroExtend(T, Trunc->getOperand()->getType());
 173     ConstantRange X = getRange(Trunc->getOperand(), T, SE);
 174     if (X.isFullSet()) return FullSet;
 175     return X.truncate(cast<IntegerType>(Trunc->getType())->getBitWidth());
 176   }
 177
 178   if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
 179     SCEVConstant *Trip = dyn_cast<SCEVConstant>(T);
 180     if (!Trip) return FullSet;
 181
 182     if (AddRec->isAffine()) {
 183       SCEVHandle StartHandle = AddRec->getStart();
 184       SCEVHandle StepHandle = AddRec->getOperand(1);
 185
 186       SCEVConstant *Step = dyn_cast<SCEVConstant>(StepHandle);
 187       if (!Step) return FullSet;
 188
 189       uint32_t ExWidth = 2 * Trip->getValue()->getBitWidth();
 190       APInt TripExt = Trip->getValue()->getValue(); TripExt.zext(ExWidth);
 191       APInt StepExt = Step->getValue()->getValue(); StepExt.zext(ExWidth);
 192       if ((TripExt * StepExt).ugt(APInt::getLowBitsSet(ExWidth, ExWidth >> 1)))
 193         return FullSet;
 194
 195       SCEVHandle EndHandle = SE.getAddExpr(StartHandle,
 196                                            SE.getMulExpr(T, StepHandle));
 197       SCEVConstant *Start = dyn_cast<SCEVConstant>(StartHandle);
 198       SCEVConstant *End = dyn_cast<SCEVConstant>(EndHandle);
 199       if (!Start || !End) return FullSet;
 200
 201       const APInt &StartInt = Start->getValue()->getValue();
 202       const APInt &EndInt = End->getValue()->getValue();
 203       const APInt &StepInt = Step->getValue()->getValue();
 204
 205       if (StepInt.isNegative()) {
 206         if (EndInt == StartInt + 1) return FullSet;
 207         return ConstantRange(EndInt, StartInt + 1);
 208       } else {
 209         if (StartInt == EndInt + 1) return FullSet;
 210         return ConstantRange(StartInt, EndInt + 1);
 211       }
 212     }
 213   }
 214
 215   // TODO: non-affine addrec, udiv, SCEVUnknown (narrowed from elsewhere)?
 216
 217   return FullSet;
 218 }
 219
 220 bool LoopVR::runOnFunction(Function &F) { Map.clear(); return false; }
 221
 222 void LoopVR::print(std::ostream &os, const Module *) const {
 223   for (std::map<Value *, ConstantRange *>::const_iterator I = Map.begin(),
 224        E = Map.end(); I != E; ++I) {
 225     os << *I->first << ": ";
 226     I->second->print(os);
 227     os << "\n";
 228   }
 229 }
 230
 231 void LoopVR::releaseMemory() {
 232   for (std::map<Value *, ConstantRange *>::iterator I = Map.begin(),
 233        E = Map.end(); I != E; ++I) {
 234     delete I->second;
 235   }
 236
 237   Map.clear();
 238 }
 239
 240 ConstantRange LoopVR::compute(Value *V) {
 241   if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
 242     return ConstantRange(CI->getValue());
 243
 244   Instruction *I = dyn_cast<Instruction>(V);
 245   if (!I)
 246     return ConstantRange(cast<IntegerType>(V->getType())->getBitWidth(), false);
 247
 248   LoopInfo &LI = getAnalysis<LoopInfo>();
 249   ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
 250
 251   Loop *L = LI.getLoopFor(I->getParent());
 252   if (L->isLoopInvariant(I))
 253     return ConstantRange(cast<IntegerType>(V->getType())->getBitWidth(), false);
 254
 255   SCEVHandle S = SE.getSCEV(I);
 256   if (isa<SCEVUnknown>(S) || isa<SCEVCouldNotCompute>(S))
 257     return ConstantRange(cast<IntegerType>(V->getType())->getBitWidth(), false);
 258
 259   return ConstantRange(getRange(S, L, SE));
 260 }
 261
 262 ConstantRange LoopVR::get(Value *V) {
 263   std::map<Value *, ConstantRange *>::iterator I = Map.find(V);
 264   if (I == Map.end()) {
 265     ConstantRange *CR = new ConstantRange(compute(V));
 266     Map[V] = CR;
 267     return *CR;
 268   }
 269
 270   return *I->second;
 271 }
 272
 273 void LoopVR::remove(Value *V) {
 274   std::map<Value *, ConstantRange *>::iterator I = Map.find(V);
 275   if (I != Map.end()) {
 276     delete I->second;
 277     Map.erase(I);
 278   }
 279 }
 280
 281 void LoopVR::narrow(Value *V, const ConstantRange &CR) {
 282   if (CR.isFullSet()) return;
 283
 284   std::map<Value *, ConstantRange *>::iterator I = Map.find(V);
 285   if (I == Map.end())
 286     Map[V] = new ConstantRange(CR);
 287   else
 288     Map[V] = new ConstantRange(Map[V]->maximalIntersectWith(CR));
 289 }