Changes in directory llvm/lib/Analysis:
ScalarEvolution.cpp updated: 1.118 -> 1.119
ScalarEvolutionExpander.cpp updated: 1.17 -> 1.18
---
Log message:
Add a SCEV class and supporting code for sign-extend expressions.
This created an ambiguity for expandInTy to decide when to use
sign-extension or zero-extension, but it turns out that most of its callers
don't actually need a type conversion, now that LLVM types don't have
explicit signedness. Drop expandInTy in favor of plain expand, and change
the few places that actually need a type conversion to do it themselves.
---
Diffs of the changes: (+53 -7)
ScalarEvolution.cpp | 47 ++++++++++++++++++++++++++++++++++++++++++++
ScalarEvolutionExpander.cpp | 13 +++++-------
2 files changed, 53 insertions(+), 7 deletions(-)
Index: llvm/lib/Analysis/ScalarEvolution.cpp
diff -u llvm/lib/Analysis/ScalarEvolution.cpp:1.118
llvm/lib/Analysis/ScalarEvolution.cpp:1.119
--- llvm/lib/Analysis/ScalarEvolution.cpp:1.118 Wed Jun 6 06:26:20 2007
+++ llvm/lib/Analysis/ScalarEvolution.cpp Fri Jun 15 09:38:12 2007
@@ -245,6 +245,32 @@
OS << "(zeroextend " << *Op << " to " << *Ty << ")";
}
+// SCEVSignExtends - Only allow the creation of one SCEVSignExtendExpr for any
+// particular input. Don't use a SCEVHandle here, or else the object will
never
+// be deleted!
+static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
+ SCEVSignExtendExpr*> > SCEVSignExtends;
+
+SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty)
+ : SCEV(scSignExtend), Op(op), Ty(ty) {
+ assert(Op->getType()->isInteger() && Ty->isInteger() &&
+ "Cannot sign extend non-integer value!");
+ assert(Op->getType()->getPrimitiveSizeInBits() < Ty->getPrimitiveSizeInBits()
+ && "This is not an extending conversion!");
+}
+
+SCEVSignExtendExpr::~SCEVSignExtendExpr() {
+ SCEVSignExtends->erase(std::make_pair(Op, Ty));
+}
+
+ConstantRange SCEVSignExtendExpr::getValueRange() const {
+ return getOperand()->getValueRange().signExtend(getBitWidth());
+}
+
+void SCEVSignExtendExpr::print(std::ostream &OS) const {
+ OS << "(signextend " << *Op << " to " << *Ty << ")";
+}
+
// SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any
// particular input. Don't use a SCEVHandle here, or else the object will
never
// be deleted!
@@ -588,6 +614,21 @@
return Result;
}
+SCEVHandle SCEVSignExtendExpr::get(const SCEVHandle &Op, const Type *Ty) {
+ if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
+ return SCEVUnknown::get(
+ ConstantExpr::getSExt(SC->getValue(), Ty));
+
+ // FIXME: If the input value is a chrec scev, and we can prove that the value
+ // did not overflow the old, smaller, value, we can sign extend all of the
+ // operands (often constants). This would allow analysis of something like
+ // this: for (signed char X = 0; X < 100; ++X) { int Y = X; }
+
+ SCEVSignExtendExpr *&Result = (*SCEVSignExtends)[std::make_pair(Op, Ty)];
+ if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty);
+ return Result;
+}
+
// get - Get a canonical add expression, or something simpler if possible.
SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) {
assert(!Ops.empty() && "Cannot get empty add!");
@@ -1370,6 +1411,9 @@
if (SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S))
return GetConstantFactor(E->getOperand()).zext(
cast<IntegerType>(E->getType())->getBitWidth());
+ if (SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S))
+ return GetConstantFactor(E->getOperand()).sext(
+ cast<IntegerType>(E->getType())->getBitWidth());
if (SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
// The result is the min of all operands.
@@ -1470,6 +1514,9 @@
case Instruction::ZExt:
return SCEVZeroExtendExpr::get(getSCEV(I->getOperand(0)), I->getType());
+ case Instruction::SExt:
+ return SCEVSignExtendExpr::get(getSCEV(I->getOperand(0)), I->getType());
+
case Instruction::BitCast:
// BitCasts are no-op casts so we just eliminate the cast.
if (I->getType()->isInteger() &&
Index: llvm/lib/Analysis/ScalarEvolutionExpander.cpp
diff -u llvm/lib/Analysis/ScalarEvolutionExpander.cpp:1.17
llvm/lib/Analysis/ScalarEvolutionExpander.cpp:1.18
--- llvm/lib/Analysis/ScalarEvolutionExpander.cpp:1.17 Tue Apr 17 18:43:50 2007
+++ llvm/lib/Analysis/ScalarEvolutionExpander.cpp Fri Jun 15 09:38:12 2007
@@ -93,18 +93,17 @@
}
Value *SCEVExpander::visitMulExpr(SCEVMulExpr *S) {
- const Type *Ty = S->getType();
int FirstOp = 0; // Set if we should emit a subtract.
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0)))
if (SC->getValue()->isAllOnesValue())
FirstOp = 1;
int i = S->getNumOperands()-2;
- Value *V = expandInTy(S->getOperand(i+1), Ty);
+ Value *V = expand(S->getOperand(i+1));
// Emit a bunch of multiply instructions
for (; i >= FirstOp; --i)
- V = InsertBinop(Instruction::Mul, V, expandInTy(S->getOperand(i), Ty),
+ V = InsertBinop(Instruction::Mul, V, expand(S->getOperand(i)),
InsertPt);
// -1 * ... ---> 0 - ...
if (FirstOp == 1)
@@ -122,10 +121,10 @@
// {X,+,F} --> X + {0,+,F}
if (!isa<SCEVConstant>(S->getStart()) ||
!cast<SCEVConstant>(S->getStart())->getValue()->isZero()) {
- Value *Start = expandInTy(S->getStart(), Ty);
+ Value *Start = expand(S->getStart());
std::vector<SCEVHandle> NewOps(S->op_begin(), S->op_end());
NewOps[0] = SCEVUnknown::getIntegerSCEV(0, Ty);
- Value *Rest = expandInTy(SCEVAddRecExpr::get(NewOps, L), Ty);
+ Value *Rest = expand(SCEVAddRecExpr::get(NewOps, L));
// FIXME: look for an existing add to use.
return InsertBinop(Instruction::Add, Rest, Start, InsertPt);
@@ -164,7 +163,7 @@
// If this is a simple linear addrec, emit it now as a special case.
if (S->getNumOperands() == 2) { // {0,+,F} --> i*F
- Value *F = expandInTy(S->getOperand(1), Ty);
+ Value *F = expand(S->getOperand(1));
// IF the step is by one, just return the inserted IV.
if (ConstantInt *CI = dyn_cast<ConstantInt>(F))
@@ -201,5 +200,5 @@
SCEVHandle V = S->evaluateAtIteration(IH);
//cerr << "Evaluated: " << *this << "\n to: " << *V << "\n";
- return expandInTy(V, Ty);
+ return expand(V);
}
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
