#include "llvm/Analysis/LoopVR.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
+#include "llvm/LLVMContext.h"
+#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/CFG.h"
using namespace llvm;
char LoopVR::ID = 0;
-static RegisterPass<LoopVR> X("loopvr", "Loop Value Ranges", true, true);
+static RegisterPass<LoopVR> X("loopvr", "Loop Value Ranges", false, 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);
+ConstantRange LoopVR::getRange(const SCEV *S, Loop *L, ScalarEvolution &SE) {
+ const SCEV *T = SE.getBackedgeTakenCount(L);
if (isa<SCEVCouldNotCompute>(T))
return ConstantRange(cast<IntegerType>(S->getType())->getBitWidth(), true);
}
/// getRange - determine the range for a particular SCEV with a given trip count
-ConstantRange LoopVR::getRange(SCEVHandle S, SCEVHandle T, ScalarEvolution &SE){
+ConstantRange LoopVR::getRange(const SCEV *S, const SCEV *T, ScalarEvolution &SE){
- if (SCEVConstant *C = dyn_cast<SCEVConstant>(S))
+ if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
return ConstantRange(C->getValue()->getValue());
-
+
ConstantRange FullSet(cast<IntegerType>(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<SCEVAddExpr>(S)) {
+ if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
ConstantRange X = getRange(Add->getOperand(0), T, SE);
if (X.isFullSet()) return FullSet;
for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) {
// {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<SCEVMulExpr>(S)) {
+ if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(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());
+ const IntegerType *Ty = IntegerType::get(SE.getContext(), X.getBitWidth());
+ const IntegerType *ExTy = IntegerType::get(SE.getContext(),
+ X.getBitWidth() * Mul->getNumOperands());
ConstantRange XExt = X.zeroExtend(ExTy->getBitWidth());
for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i) {
// 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<SCEVSMaxExpr>(S)) {
+ if (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) {
ConstantRange X = getRange(SMax->getOperand(0), T, SE);
if (X.isFullSet()) return FullSet;
// 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<SCEVUMaxExpr>(S)) {
+ if (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) {
ConstantRange X = getRange(UMax->getOperand(0), T, SE);
if (X.isFullSet()) return FullSet;
}
// L udiv R. Luckily, there's only ever 2 sides to a udiv.
- if (SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
+ if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
ConstantRange L = getRange(UDiv->getLHS(), T, SE);
ConstantRange R = getRange(UDiv->getRHS(), T, SE);
if (L.isFullSet() && R.isFullSet()) return FullSet;
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);
+ R = R.intersectWith(NotZero);
}
- // But, the maximal intersection might still include zero. If it does, then
- // we know it also included one.
+ // But, the 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
// ConstantRange already implements the cast operators.
- if (SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) {
+ if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) {
T = SE.getTruncateOrZeroExtend(T, ZExt->getOperand()->getType());
ConstantRange X = getRange(ZExt->getOperand(), T, SE);
return X.zeroExtend(cast<IntegerType>(ZExt->getType())->getBitWidth());
}
- if (SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) {
+ if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) {
T = SE.getTruncateOrZeroExtend(T, SExt->getOperand()->getType());
ConstantRange X = getRange(SExt->getOperand(), T, SE);
return X.signExtend(cast<IntegerType>(SExt->getType())->getBitWidth());
}
- if (SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) {
+ if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) {
T = SE.getTruncateOrZeroExtend(T, Trunc->getOperand()->getType());
ConstantRange X = getRange(Trunc->getOperand(), T, SE);
if (X.isFullSet()) return FullSet;
return X.truncate(cast<IntegerType>(Trunc->getType())->getBitWidth());
}
- if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
- SCEVConstant *Trip = dyn_cast<SCEVConstant>(T);
+ if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
+ const SCEVConstant *Trip = dyn_cast<SCEVConstant>(T);
if (!Trip) return FullSet;
if (AddRec->isAffine()) {
- SCEVHandle StartHandle = AddRec->getStart();
- SCEVHandle StepHandle = AddRec->getOperand(1);
+ const SCEV *StartHandle = AddRec->getStart();
+ const SCEV *StepHandle = AddRec->getOperand(1);
- SCEVConstant *Step = dyn_cast<SCEVConstant>(StepHandle);
+ const SCEVConstant *Step = dyn_cast<SCEVConstant>(StepHandle);
if (!Step) return FullSet;
uint32_t ExWidth = 2 * Trip->getValue()->getBitWidth();
if ((TripExt * StepExt).ugt(APInt::getLowBitsSet(ExWidth, ExWidth >> 1)))
return FullSet;
- SCEVHandle EndHandle = SE.getAddExpr(StartHandle,
+ const SCEV *EndHandle = SE.getAddExpr(StartHandle,
SE.getMulExpr(T, StepHandle));
- SCEVConstant *Start = dyn_cast<SCEVConstant>(StartHandle);
- SCEVConstant *End = dyn_cast<SCEVConstant>(EndHandle);
+ const SCEVConstant *Start = dyn_cast<SCEVConstant>(StartHandle);
+ const SCEVConstant *End = dyn_cast<SCEVConstant>(EndHandle);
if (!Start || !End) return FullSet;
const APInt &StartInt = Start->getValue()->getValue();
return FullSet;
}
+void LoopVR::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequiredTransitive<LoopInfo>();
+ AU.addRequiredTransitive<ScalarEvolution>();
+ AU.setPreservesAll();
+}
+
bool LoopVR::runOnFunction(Function &F) { Map.clear(); return false; }
-void LoopVR::print(std::ostream &os, const Module *) const {
- raw_os_ostream OS(os);
+void LoopVR::print(raw_ostream &OS, const Module *) const {
for (std::map<Value *, ConstantRange *>::const_iterator I = Map.begin(),
E = Map.end(); I != E; ++I) {
OS << *I->first << ": " << *I->second << '\n';
return ConstantRange(cast<IntegerType>(V->getType())->getBitWidth(), false);
LoopInfo &LI = getAnalysis<LoopInfo>();
- ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
Loop *L = LI.getLoopFor(I->getParent());
- if (L->isLoopInvariant(I))
+ if (!L || L->isLoopInvariant(I))
return ConstantRange(cast<IntegerType>(V->getType())->getBitWidth(), false);
- SCEVHandle S = SE.getSCEV(I);
+ ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
+
+ const SCEV *S = SE.getSCEV(I);
if (isa<SCEVUnknown>(S) || isa<SCEVCouldNotCompute>(S))
return ConstantRange(cast<IntegerType>(V->getType())->getBitWidth(), false);
if (I == Map.end())
Map[V] = new ConstantRange(CR);
else
- Map[V] = new ConstantRange(Map[V]->maximalIntersectWith(CR));
+ Map[V] = new ConstantRange(Map[V]->intersectWith(CR));
}
projects / oota-llvm.git / blobdiff