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