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.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37591 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 53 insertions, 7 deletions

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index bf67fd3fff..3ae65286fa 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -245,6 +245,32 @@ void SCEVZeroExtendExpr::print(std::ostream &OS) const {
   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 @@ SCEVHandle SCEVZeroExtendExpr::get(const SCEVHandle &Op, const Type *Ty) {
   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 @@ static APInt GetConstantFactor(SCEVHandle S) {
   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 @@ SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) {
     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() &&
diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index c88c781195..c8c683cb3f 100644
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -93,18 +93,17 @@ Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS,
 }
 
 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 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) {
   // {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 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) {
 
   // 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 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) {
   SCEVHandle V = S->evaluateAtIteration(IH);
   //cerr << "Evaluated: " << *this << "\n     to: " << *V << "\n";
 
-  return expandInTy(V, Ty);
+  return expand(V);
 }