diff --git a/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h b/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h
--- a/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -343,6 +343,10 @@
 
     /// Return the value of this chain of recurrences at the specified
     /// iteration number.
+    ///
+    /// Note that SCEVCouldNotCompute is returned if evaluation attempt failed.
+    /// For example, if precision of \p It is less than required to perform
+    /// evaluation an instance of SCEVCouldNotCompute is returned.
     const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
 
     /// Return the number of iterations of this loop that produce
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -1205,6 +1205,15 @@
   IntegerType *CalculationTy = IntegerType::get(SE.getContext(),
                                                       CalculationBits);
   const SCEV *Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy);
+
+  // 'It' should have at least 'CalculationBits' precision for the calculation
+  // to be correct. Check that by verifying that downconversion of upconverted
+  // value is not changed. In other words check that X == trunc(zext(X)).
+  if (SE.getTypeSizeInBits(It->getType()) < CalculationBits &&
+      It != SE.getTruncateExpr(Dividend, It->getType()))
+    // Return SCEVCouldNotCompute if 'It' doesn't have enough precision.
+    return SE.getCouldNotCompute();
+
   for (unsigned i = 1; i != K; ++i) {
     const SCEV *S = SE.getMinusSCEV(It, SE.getConstant(It->getType(), i));
     Dividend = SE.getMulExpr(Dividend,
@@ -8320,7 +8329,9 @@
       if (BackedgeTakenCount == getCouldNotCompute()) return AddRec;
 
       // Then, evaluate the AddRec.
-      return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
+      const SCEV *ValAtIter =
+          AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
+      if (!isa<SCEVCouldNotCompute>(ValAtIter)) return ValAtIter;
     }
 
     return AddRec;
diff --git a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
--- a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -1627,7 +1627,9 @@
     NewS = Ext;
 
   const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE);
-  //cerr << "Evaluated: " << *this << "\n     to: " << *V << "\n";
+  assert(!isa<SCEVCouldNotCompute>(V) &&
+         "Expansion of AddRec failed. Can't evaluate SCEV at iteration.");
+  // cerr << "Evaluated: " << *this << "\n     to: " << *V << "\n";
 
   // Truncate the result down to the original type, if needed.
   const SCEV *T = SE.getTruncateOrNoop(V, Ty);