LLVM API Documentation

LoopVR.cpp

Go to the documentation of this file.
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 }