Index: llvm/trunk/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/trunk/lib/Analysis/ScalarEvolution.cpp
+++ llvm/trunk/lib/Analysis/ScalarEvolution.cpp
@@ -211,6 +211,11 @@
                   cl::desc("Max coefficients in AddRec during evolving"),
                   cl::init(8));
 
+static cl::opt<unsigned>
+    HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden,
+                  cl::desc("Size of the expression which is considered huge"),
+                  cl::init(4096));
+
 //===----------------------------------------------------------------------===//
 //                           SCEV class definitions
 //===----------------------------------------------------------------------===//
@@ -845,6 +850,17 @@
   return F.Size;
 }
 
+/// Returns true if the subtree of \p S contains at least HugeExprThreshold
+/// nodes.
+static bool isHugeExpression(const SCEV *S) {
+  return S->getExpressionSize() >= HugeExprThreshold;
+}
+
+/// Returns true of \p Ops contains a huge SCEV (see definition above).
+static bool hasHugeExpression(ArrayRef<const SCEV *> Ops) {
+  return any_of(Ops, isHugeExpression);
+}
+
 namespace {
 
 struct SCEVDivision : public SCEVVisitor<SCEVDivision, void> {
@@ -2404,7 +2420,7 @@
   }
 
   // Limit recursion calls depth.
-  if (Depth > MaxArithDepth)
+  if (Depth > MaxArithDepth || hasHugeExpression(Ops))
     return getOrCreateAddExpr(Ops, Flags);
 
   // Okay, check to see if the same value occurs in the operand list more than
@@ -2883,7 +2899,7 @@
   Flags = StrengthenNoWrapFlags(this, scMulExpr, Ops, Flags);
 
   // Limit recursion calls depth.
-  if (Depth > MaxArithDepth)
+  if (Depth > MaxArithDepth || hasHugeExpression(Ops))
     return getOrCreateMulExpr(Ops, Flags);
 
   // If there are any constants, fold them together.
@@ -3056,7 +3072,8 @@
       // Limit max number of arguments to avoid creation of unreasonably big
       // SCEVAddRecs with very complex operands.
       if (AddRec->getNumOperands() + OtherAddRec->getNumOperands() - 1 >
-          MaxAddRecSize)
+          MaxAddRecSize || isHugeExpression(AddRec) ||
+          isHugeExpression(OtherAddRec))
         continue;
 
       bool Overflow = false;
Index: llvm/trunk/test/Analysis/ScalarEvolution/huge_expression_limit.ll
===================================================================
--- llvm/trunk/test/Analysis/ScalarEvolution/huge_expression_limit.ll
+++ llvm/trunk/test/Analysis/ScalarEvolution/huge_expression_limit.ll
@@ -0,0 +1,41 @@
+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
+; RUN: opt < %s -analyze -scalar-evolution -scalar-evolution-huge-expr-threshold=1 | FileCheck %s
+
+define void @test(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e, i32 %f) {
+; CHECK-LABEL: 'test'
+; CHECK-NEXT:  Classifying expressions for: @test
+; CHECK-NEXT:    %add1 = add i32 %a, %b
+; CHECK-NEXT:    --> (%a + %b) U: full-set S: full-set
+; CHECK-NEXT:    %add2 = add i32 %add1, %c
+; CHECK-NEXT:    --> ((%a + %b) + %c) U: full-set S: full-set
+; CHECK-NEXT:    %add3 = add i32 %add2, %d
+; CHECK-NEXT:    --> (((%a + %b) + %c) + %d) U: full-set S: full-set
+; CHECK-NEXT:    %add4 = add i32 %add3, %e
+; CHECK-NEXT:    --> ((((%a + %b) + %c) + %d) + %e) U: full-set S: full-set
+; CHECK-NEXT:    %add5 = add i32 %add4, %f
+; CHECK-NEXT:    --> (((((%a + %b) + %c) + %d) + %e) + %f) U: full-set S: full-set
+; CHECK-NEXT:    %mul1 = mul i32 %a, %b
+; CHECK-NEXT:    --> (%a * %b) U: full-set S: full-set
+; CHECK-NEXT:    %mul2 = mul i32 %mul1, %c
+; CHECK-NEXT:    --> ((%a * %b) * %c) U: full-set S: full-set
+; CHECK-NEXT:    %mul3 = mul i32 %mul2, %d
+; CHECK-NEXT:    --> (((%a * %b) * %c) * %d) U: full-set S: full-set
+; CHECK-NEXT:    %mul4 = mul i32 %mul3, %e
+; CHECK-NEXT:    --> ((((%a * %b) * %c) * %d) * %e) U: full-set S: full-set
+; CHECK-NEXT:    %mul5 = mul i32 %mul4, %f
+; CHECK-NEXT:    --> (((((%a * %b) * %c) * %d) * %e) * %f) U: full-set S: full-set
+; CHECK-NEXT:  Determining loop execution counts for: @test
+;
+  %add1 = add i32 %a, %b
+  %add2 = add i32 %add1, %c
+  %add3 = add i32 %add2, %d
+  %add4 = add i32 %add3, %e
+  %add5 = add i32 %add4, %f
+
+  %mul1 = mul i32 %a, %b
+  %mul2 = mul i32 %mul1, %c
+  %mul3 = mul i32 %mul2, %d
+  %mul4 = mul i32 %mul3, %e
+  %mul5 = mul i32 %mul4, %f
+  ret void
+}
Index: llvm/trunk/test/Transforms/LoopStrengthReduce/X86/bin_power.ll
===================================================================
--- llvm/trunk/test/Transforms/LoopStrengthReduce/X86/bin_power.ll
+++ llvm/trunk/test/Transforms/LoopStrengthReduce/X86/bin_power.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -loop-reduce -S | FileCheck %s
+; RUN: opt < %s -scalar-evolution-huge-expr-threshold=1000000 -loop-reduce -S | FileCheck %s
 
 target datalayout = "e-m:e-i32:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"