Index: ScalarEvolution.cpp
===================================================================
--- ScalarEvolution.cpp
+++ ScalarEvolution.cpp
@@ -913,7 +913,6 @@
   // Expr by Denominator for the following functions with empty implementation.
   void visitTruncateExpr(const SCEVTruncateExpr *Numerator) {}
   void visitZeroExtendExpr(const SCEVZeroExtendExpr *Numerator) {}
-  void visitSignExtendExpr(const SCEVSignExtendExpr *Numerator) {}
   void visitUDivExpr(const SCEVUDivExpr *Numerator) {}
   void visitSMaxExpr(const SCEVSMaxExpr *Numerator) {}
   void visitUMaxExpr(const SCEVUMaxExpr *Numerator) {}
@@ -941,17 +940,64 @@
     }
   }
 
+  void treatCastDenominator(const SCEVCastExpr *CENumerator, const SCEV **Q,
+                        const SCEV **R) {
+    if (const SCEVTruncateExpr *TruncDenominator =
+                                      dyn_cast<SCEVTruncateExpr>(Denominator)) {
+      divide(SE, CENumerator->getOperand(), TruncDenominator->getOperand(), Q, R);
+    }
+    else
+    if (const SCEVZeroExtendExpr *ZExtDenominator =
+                                      dyn_cast<SCEVZeroExtendExpr>(Denominator)) {
+      divide(SE, CENumerator->getOperand(), ZExtDenominator->getOperand(), Q, R);
+    }
+    else
+    if (const SCEVSignExtendExpr *SExtDenominator =
+                                      dyn_cast<SCEVSignExtendExpr>(Denominator)) {
+      // Dropping SExt in Dividend and Divisor
+      divide(SE, CENumerator->getOperand(), SExtDenominator->getOperand(), Q, R);
+    }
+    else
+      divide(SE, CENumerator->getOperand(), Denominator, Q, R);
+  }
+
+  void visitSignExtendExpr(const SCEVSignExtendExpr *Numerator) {
+    const SCEV *Q, *R;
+    treatCastDenominator(Numerator, &Q, &R);
+
+    // Note that the division operation here is signed.
+    //  And SExt does not change the value of the divisor nor of the dividend.
+    //  So we can take out the SExt from both the divisor and the dividend
+    // And, we sign extend the Quotient and Remainder because
+    //  the resulting type of the Quotient and Remainder should be the type of
+    //      the Dividend,
+    //  since we assume that the Divisor can be in the most extreme case
+    //   +1 or -1 and Dividend already is a signed integer type since it is
+    //   the result of a sext operation.
+    //  If we don't SExt, the Quotient and Remainder will have the type of
+    //  the Dividend (and Divisor).
+
+    Quotient = SE.getSignExtendExpr(Q, Numerator->getType());
+    Remainder = SE.getSignExtendExpr(R, Numerator->getType());
+  }
+
   void visitAddRecExpr(const SCEVAddRecExpr *Numerator) {
     const SCEV *StartQ, *StartR, *StepQ, *StepR;
     if (!Numerator->isAffine())
       return cannotDivide(Numerator);
     divide(SE, Numerator->getStart(), Denominator, &StartQ, &StartR);
     divide(SE, Numerator->getStepRecurrence(SE), Denominator, &StepQ, &StepR);
-    // Bail out if the types do not match.
-    Type *Ty = Denominator->getType();
-    if (Ty != StartQ->getType() || Ty != StartR->getType() ||
-        Ty != StepQ->getType() || Ty != StepR->getType())
-      return cannotDivide(Numerator);
+
+    // This is from Manuel Selva's patch (https://reviews.llvm.org/D35478).
+    //  We have to put this code here instead of the conditionals with
+    //    cannotDivide() in order to work with sext expressions.
+    assert(Numerator->getStart()->getType() == StartQ->getType() &&
+           StartQ->getType() == StartR->getType() &&
+           "Expected matching types");
+    assert(Numerator->getStepRecurrence(SE)->getType() == StepQ->getType() &&
+           StepQ->getType() == StepR->getType() &&
+           "Expected matching types");
+
     Quotient = SE.getAddRecExpr(StartQ, StepQ, Numerator->getLoop(),
                                 Numerator->getNoWrapFlags());
     Remainder = SE.getAddRecExpr(StartR, StepR, Numerator->getLoop(),
@@ -960,7 +1006,7 @@
 
   void visitAddExpr(const SCEVAddExpr *Numerator) {
     SmallVector<const SCEV *, 2> Qs, Rs;
-    Type *Ty = Denominator->getType();
+    Type *Ty = Numerator->getType();
 
     for (const SCEV *Op : Numerator->operands()) {
       const SCEV *Q, *R;
@@ -970,6 +1016,9 @@
       if (Ty != Q->getType() || Ty != R->getType())
         return cannotDivide(Numerator);
 
+      assert(Ty == Q->getType() && Ty == R->getType() &&
+               "Expected matching types");
+
       Qs.push_back(Q);
       Rs.push_back(R);
     }
@@ -1030,13 +1079,13 @@
     // The Remainder is obtained by replacing Denominator by 0 in Numerator.
     ValueToValueMap RewriteMap;
     RewriteMap[cast<SCEVUnknown>(Denominator)->getValue()] =
-        cast<SCEVConstant>(Zero)->getValue();
+        cast<SCEVConstant>(SE.getZero(Denominator->getType()))->getValue();
     Remainder = SCEVParameterRewriter::rewrite(Numerator, SE, RewriteMap, true);
 
     if (Remainder->isZero()) {
       // The Quotient is obtained by replacing Denominator by 1 in Numerator.
       RewriteMap[cast<SCEVUnknown>(Denominator)->getValue()] =
-          cast<SCEVConstant>(One)->getValue();
+          cast<SCEVConstant>(SE.getOne(Denominator->getType()))->getValue();
       Quotient =
           SCEVParameterRewriter::rewrite(Numerator, SE, RewriteMap, true);
       return;
@@ -1058,8 +1107,8 @@
   SCEVDivision(ScalarEvolution &S, const SCEV *Numerator,
                const SCEV *Denominator)
       : SE(S), Denominator(Denominator) {
-    Zero = SE.getZero(Denominator->getType());
-    One = SE.getOne(Denominator->getType());
+    Zero = SE.getZero(Numerator->getType());
+    One = SE.getOne(Numerator->getType());
 
     // We generally do not know how to divide Expr by Denominator. We
     // initialize the division to a "cannot divide" state to simplify the rest
@@ -10667,6 +10716,10 @@
 
 // Return the number of product terms in S.
 static inline int numberOfTerms(const SCEV *S) {
+  if (const SCEVSignExtendExpr *SExtS = dyn_cast<SCEVSignExtendExpr>(S)) {
+    return numberOfTerms(SExtS->getOperand());
+  }
+
   if (const SCEVMulExpr *Expr = dyn_cast<SCEVMulExpr>(S))
     return Expr->getNumOperands();
   return 1;