From a11e2eb845ffc1ad9aee0a96d6998a3e084edfcd Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Mon, 30 Jun 2008 00:04:21 +0000 Subject: [PATCH] Add a value range analysis that lazily computes ranges using ScalarEvolutions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52885 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/LoopVR.h | 90 ++++++++++ include/llvm/LinkAllPasses.h | 2 + lib/Analysis/LoopVR.cpp | 289 +++++++++++++++++++++++++++++++++ 3 files changed, 381 insertions(+) create mode 100644 include/llvm/Analysis/LoopVR.h create mode 100644 lib/Analysis/LoopVR.cpp diff --git a/include/llvm/Analysis/LoopVR.h b/include/llvm/Analysis/LoopVR.h new file mode 100644 index 00000000000..ce9d95b40f6 --- /dev/null +++ b/include/llvm/Analysis/LoopVR.h @@ -0,0 +1,90 @@ +//===- LoopVR.cpp - Value Range analysis driven by loop information -------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the interface for the loop-driven value range pass. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_LOOPVR_H +#define LLVM_ANALYSIS_LOOPVR_H + +#include "llvm/Pass.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Support/ConstantRange.h" +#include +#include + +namespace llvm { + +/// LoopVR - This class maintains a mapping of Values to ConstantRanges. +/// There are interfaces to look up and update ranges by value, and for +/// accessing all values with range information. +/// +class LoopVR : public FunctionPass { +public: + static char ID; // Class identification, replacement for typeinfo + + LoopVR() : FunctionPass(intptr_t(&ID)) {} + + bool runOnFunction(Function &F); + virtual void print(std::ostream &os, const Module *) const; + void releaseMemory(); + + void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + AU.addRequired(); + AU.setPreservesAll(); + } + + //===--------------------------------------------------------------------- + // Methods that are used to look up and update particular values. + + /// get - return the ConstantRange for a given Value of IntegerType. + ConstantRange get(Value *V); + + /// remove - remove a value from this analysis. + void remove(Value *V); + + /// narrow - improve our unterstanding of a Value by pointing out that it + /// must fall within ConstantRange. To replace a range, remove it first. + void narrow(Value *V, const ConstantRange &CR); + + //===--------------------------------------------------------------------- + // Methods that are used to iterate across all values with information. + + /// size - returns the number of Values with information + unsigned size() const { return Map.size(); } + + typedef std::map::iterator iterator; + + /// begin - return an iterator to the first Value, ConstantRange pair + iterator begin() { return Map.begin(); } + + /// end - return an iterator one past the last Value, ConstantRange pair + iterator end() { return Map.end(); } + + /// getValue - return the Value referenced by an iterator + Value *getValue(iterator I) { return I->first; } + + /// getConstantRange - return the ConstantRange referenced by an iterator + ConstantRange getConstantRange(iterator I) { return *I->second; } + +private: + ConstantRange compute(Value *V); + + ConstantRange getRange(SCEVHandle S, Loop *L, ScalarEvolution &SE); + + ConstantRange getRange(SCEVHandle S, SCEVHandle T, ScalarEvolution &SE); + + std::map Map; +}; + +} // end llvm namespace + +#endif diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h index eaa97b6ae65..76a4a2f58d7 100644 --- a/include/llvm/LinkAllPasses.h +++ b/include/llvm/LinkAllPasses.h @@ -19,6 +19,7 @@ #include "llvm/Analysis/FindUsedTypes.h" #include "llvm/Analysis/IntervalPartition.h" #include "llvm/Analysis/LoadValueNumbering.h" +#include "llvm/Analysis/LoopVR.h" #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ScalarEvolution.h" @@ -122,6 +123,7 @@ namespace { (void)new llvm::IntervalPartition(); (void)new llvm::FindUsedTypes(); (void)new llvm::ScalarEvolution(); + (void)new llvm::LoopVR(); ((llvm::Function*)0)->viewCFGOnly(); llvm::AliasSetTracker X(*(llvm::AliasAnalysis*)0); X.add((llvm::Value*)0, 0); // for -print-alias-sets diff --git a/lib/Analysis/LoopVR.cpp b/lib/Analysis/LoopVR.cpp new file mode 100644 index 00000000000..eb7524a9c2f --- /dev/null +++ b/lib/Analysis/LoopVR.cpp @@ -0,0 +1,289 @@ +//===- LoopVR.cpp - Value Range analysis driven by loop information -------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "loopvr" +#include "llvm/Analysis/LoopVR.h" +#include "llvm/Constants.h" +#include "llvm/Instructions.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/Assembly/Writer.h" +#include "llvm/Support/CFG.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/Streams.h" +using namespace llvm; + +char LoopVR::ID = 0; +namespace { +static RegisterPass X("loopvr", "Loop Value Ranges", true, true); +} + +/// getRange - determine the range for a particular SCEV within a given Loop +ConstantRange LoopVR::getRange(SCEVHandle S, Loop *L, ScalarEvolution &SE) { + SCEVHandle T = SE.getIterationCount(L); + if (isa(T)) + return ConstantRange(cast(S->getType())->getBitWidth(), true); + + T = SE.getTruncateOrZeroExtend(T, S->getType()); + return getRange(S, T, SE); +} + +/// getRange - determine the range for a particular SCEV with a given trip count +ConstantRange LoopVR::getRange(SCEVHandle S, SCEVHandle T, ScalarEvolution &SE){ + + if (SCEVConstant *C = dyn_cast(S)) + return ConstantRange(C->getValue()->getValue()); + + ConstantRange FullSet(cast(S->getType())->getBitWidth(), true); + + // {x,+,y,+,...z}. We detect overflow by checking the size of the set after + // summing the upper and lower. + if (SCEVAddExpr *Add = dyn_cast(S)) { + ConstantRange X = getRange(Add->getOperand(0), T, SE); + if (X.isFullSet()) return FullSet; + for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) { + ConstantRange Y = getRange(Add->getOperand(i), T, SE); + if (Y.isFullSet()) return FullSet; + + APInt Spread_X = X.getSetSize(), Spread_Y = Y.getSetSize(); + APInt NewLower = X.getLower() + Y.getLower(); + APInt NewUpper = X.getUpper() + Y.getUpper() - 1; + if (NewLower == NewUpper) + return FullSet; + + X = ConstantRange(NewLower, NewUpper); + if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) + return FullSet; // we've wrapped, therefore, full set. + } + return X; + } + + // {x,*,y,*,...,z}. In order to detect overflow, we use k*bitwidth where + // k is the number of terms being multiplied. + if (SCEVMulExpr *Mul = dyn_cast(S)) { + ConstantRange X = getRange(Mul->getOperand(0), T, SE); + if (X.isFullSet()) return FullSet; + + const IntegerType *Ty = IntegerType::get(X.getBitWidth()); + const IntegerType *ExTy = IntegerType::get(X.getBitWidth() * + Mul->getNumOperands()); + ConstantRange XExt = X.zeroExtend(ExTy->getBitWidth()); + + for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i) { + ConstantRange Y = getRange(Mul->getOperand(i), T, SE); + if (Y.isFullSet()) return FullSet; + + ConstantRange YExt = Y.zeroExtend(ExTy->getBitWidth()); + XExt = ConstantRange(XExt.getLower() * YExt.getLower(), + ((XExt.getUpper()-1) * (YExt.getUpper()-1)) + 1); + } + return XExt.truncate(Ty->getBitWidth()); + } + + // X smax Y smax ... Z is: range(smax(X_smin, Y_smin, ..., Z_smin), + // smax(X_smax, Y_smax, ..., Z_smax)) + // It doesn't matter if one of the SCEVs has FullSet because we're taking + // a maximum of the minimums across all of them. + if (SCEVSMaxExpr *SMax = dyn_cast(S)) { + ConstantRange X = getRange(SMax->getOperand(0), T, SE); + if (X.isFullSet()) return FullSet; + + APInt smin = X.getSignedMin(), smax = X.getSignedMax(); + for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i) { + ConstantRange Y = getRange(SMax->getOperand(i), T, SE); + smin = APIntOps::smax(smin, Y.getSignedMin()); + smax = APIntOps::smax(smax, Y.getSignedMax()); + } + if (smax + 1 == smin) return FullSet; + return ConstantRange(smin, smax + 1); + } + + // X umax Y umax ... Z is: range(umax(X_umin, Y_umin, ..., Z_umin), + // umax(X_umax, Y_umax, ..., Z_umax)) + // It doesn't matter if one of the SCEVs has FullSet because we're taking + // a maximum of the minimums across all of them. + if (SCEVUMaxExpr *UMax = dyn_cast(S)) { + ConstantRange X = getRange(UMax->getOperand(0), T, SE); + if (X.isFullSet()) return FullSet; + + APInt umin = X.getUnsignedMin(), umax = X.getUnsignedMax(); + for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i) { + ConstantRange Y = getRange(UMax->getOperand(i), T, SE); + umin = APIntOps::umax(umin, Y.getUnsignedMin()); + umax = APIntOps::umax(umax, Y.getUnsignedMax()); + } + if (umax + 1 == umin) return FullSet; + return ConstantRange(umin, umax + 1); + } + + // L udiv R. Luckily, there's only ever 2 sides to a udiv. + if (SCEVUDivExpr *UDiv = dyn_cast(S)) { + ConstantRange L = getRange(UDiv->getLHS(), T, SE); + ConstantRange R = getRange(UDiv->getRHS(), T, SE); + if (L.isFullSet() && R.isFullSet()) return FullSet; + + if (R.getUnsignedMax() == 0) { + // RHS must be single-element zero. Return an empty set. + return ConstantRange(R.getBitWidth(), false); + } + + APInt Lower = L.getUnsignedMin().udiv(R.getUnsignedMax()); + + APInt Upper; + + if (R.getUnsignedMin() == 0) { + // Just because it contains zero, doesn't mean it will also contain one. + // Use maximalIntersectWith to get the right behaviour. + ConstantRange NotZero(APInt(L.getBitWidth(), 1), + APInt::getNullValue(L.getBitWidth())); + R = R.maximalIntersectWith(NotZero); + } + + // But, the maximal intersection might still include zero. If it does, then + // we know it also included one. + if (R.contains(APInt::getNullValue(L.getBitWidth()))) + Upper = L.getUnsignedMax(); + else + Upper = L.getUnsignedMax().udiv(R.getUnsignedMin()); + + return ConstantRange(Lower, Upper); + } + + // ConstantRange already implements the cast operators. + + if (SCEVZeroExtendExpr *ZExt = dyn_cast(S)) { + T = SE.getTruncateOrZeroExtend(T, ZExt->getOperand()->getType()); + ConstantRange X = getRange(ZExt->getOperand(), T, SE); + return X.zeroExtend(cast(ZExt->getType())->getBitWidth()); + } + + if (SCEVSignExtendExpr *SExt = dyn_cast(S)) { + T = SE.getTruncateOrZeroExtend(T, SExt->getOperand()->getType()); + ConstantRange X = getRange(SExt->getOperand(), T, SE); + return X.signExtend(cast(SExt->getType())->getBitWidth()); + } + + if (SCEVTruncateExpr *Trunc = dyn_cast(S)) { + T = SE.getTruncateOrZeroExtend(T, Trunc->getOperand()->getType()); + ConstantRange X = getRange(Trunc->getOperand(), T, SE); + if (X.isFullSet()) return FullSet; + return X.truncate(cast(Trunc->getType())->getBitWidth()); + } + + if (SCEVAddRecExpr *AddRec = dyn_cast(S)) { + SCEVConstant *Trip = dyn_cast(T); + if (!Trip) return FullSet; + + if (AddRec->isAffine()) { + SCEVHandle StartHandle = AddRec->getStart(); + SCEVHandle StepHandle = AddRec->getOperand(1); + + SCEVConstant *Step = dyn_cast(StepHandle); + if (!Step) return FullSet; + + uint32_t ExWidth = 2 * Trip->getValue()->getBitWidth(); + APInt TripExt = Trip->getValue()->getValue(); TripExt.zext(ExWidth); + APInt StepExt = Step->getValue()->getValue(); StepExt.zext(ExWidth); + if ((TripExt * StepExt).ugt(APInt::getLowBitsSet(ExWidth, ExWidth >> 1))) + return FullSet; + + SCEVHandle EndHandle = SE.getAddExpr(StartHandle, + SE.getMulExpr(T, StepHandle)); + SCEVConstant *Start = dyn_cast(StartHandle); + SCEVConstant *End = dyn_cast(EndHandle); + if (!Start || !End) return FullSet; + + const APInt &StartInt = Start->getValue()->getValue(); + const APInt &EndInt = End->getValue()->getValue(); + const APInt &StepInt = Step->getValue()->getValue(); + + if (StepInt.isNegative()) { + if (EndInt == StartInt + 1) return FullSet; + return ConstantRange(EndInt, StartInt + 1); + } else { + if (StartInt == EndInt + 1) return FullSet; + return ConstantRange(StartInt, EndInt + 1); + } + } + } + + // TODO: non-affine addrec, udiv, SCEVUnknown (narrowed from elsewhere)? + + return FullSet; +} + +bool LoopVR::runOnFunction(Function &F) { Map.clear(); return false; } + +void LoopVR::print(std::ostream &os, const Module *) const { + for (std::map::const_iterator I = Map.begin(), + E = Map.end(); I != E; ++I) { + os << *I->first << ": "; + I->second->print(os); + os << "\n"; + } +} + +void LoopVR::releaseMemory() { + for (std::map::iterator I = Map.begin(), + E = Map.end(); I != E; ++I) { + delete I->second; + } + + Map.clear(); +} + +ConstantRange LoopVR::compute(Value *V) { + if (ConstantInt *CI = dyn_cast(V)) + return ConstantRange(CI->getValue()); + + Instruction *I = dyn_cast(V); + if (!I) + return ConstantRange(cast(V->getType())->getBitWidth(), false); + + LoopInfo &LI = getAnalysis(); + ScalarEvolution &SE = getAnalysis(); + + Loop *L = LI.getLoopFor(I->getParent()); + if (L->isLoopInvariant(I)) + return ConstantRange(cast(V->getType())->getBitWidth(), false); + + SCEVHandle S = SE.getSCEV(I); + if (isa(S) || isa(S)) + return ConstantRange(cast(V->getType())->getBitWidth(), false); + + return ConstantRange(getRange(S, L, SE)); +} + +ConstantRange LoopVR::get(Value *V) { + std::map::iterator I = Map.find(V); + if (I == Map.end()) { + ConstantRange *CR = new ConstantRange(compute(V)); + Map[V] = CR; + return *CR; + } + + return *I->second; +} + +void LoopVR::remove(Value *V) { + std::map::iterator I = Map.find(V); + if (I != Map.end()) { + delete I->second; + Map.erase(I); + } +} + +void LoopVR::narrow(Value *V, const ConstantRange &CR) { + if (CR.isFullSet()) return; + + std::map::iterator I = Map.find(V); + if (I == Map.end()) + Map[V] = new ConstantRange(CR); + else + Map[V] = new ConstantRange(Map[V]->maximalIntersectWith(CR)); +} -- 2.34.1