Index: lib/Analysis/ScalarEvolution.cpp
===================================================================
--- lib/Analysis/ScalarEvolution.cpp
+++ lib/Analysis/ScalarEvolution.cpp
@@ -2061,8 +2061,16 @@
     // Okay, if there weren't any loop invariants to be folded, check to see if
     // there are multiple AddRec's with the same loop induction variable being
     // multiplied together.  If so, we can fold them.
+
+    // If the number of AddRec operands is too high, Choose will overflow, so
+    // don't bother entering the loop.
+    bool EarlyOut = false;
+    Choose(AddRec->getNumOperands() - 2,
+           AddRec->getNumOperands() / 2 - 1,
+           EarlyOut);
     for (unsigned OtherIdx = Idx+1;
-         OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
+         !EarlyOut && OtherIdx < Ops.size() &&
+           isa<SCEVAddRecExpr>(Ops[OtherIdx]);
          ++OtherIdx) {
       if (AddRecLoop != cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop())
         continue;
@@ -2085,12 +2093,15 @@
         if (!OtherAddRec || OtherAddRec->getLoop() != AddRecLoop)
           continue;
 
+        // If we are going to overflow. Let's get it over with early.
         bool Overflow = false;
+        int xe = AddRec->getNumOperands() + OtherAddRec->getNumOperands() - 1;
+        Choose(xe - 1, (xe - 1) / 2, Overflow);
+
         Type *Ty = AddRec->getType();
         bool LargerThan64Bits = getTypeSizeInBits(Ty) > 64;
         SmallVector<const SCEV*, 7> AddRecOps;
-        for (int x = 0, xe = AddRec->getNumOperands() +
-               OtherAddRec->getNumOperands() - 1; x != xe && !Overflow; ++x) {
+        for (int x = 0; x != xe && !Overflow; ++x) {
           const SCEV *Term = getConstant(Ty, 0);
           for (int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
             uint64_t Coeff1 = Choose(x, 2*x - y, Overflow);
Index: test/Analysis/ScalarEvolution/choose-overflow-fast.ll
===================================================================
--- test/Analysis/ScalarEvolution/choose-overflow-fast.ll
+++ test/Analysis/ScalarEvolution/choose-overflow-fast.ll
@@ -0,0 +1,48 @@
+; RUN: opt < %s -iv-users
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define void @main() {
+entry:
+  br label %for.body33
+
+for.body33:                                       ; preds = %for.body33, %entry
+  %inc4064 = phi i32 [ %inc40, %for.body33 ], [ 1, %entry ]
+  %mul35.lcssa63 = phi i32 [ %mul35.15, %for.body33 ], [ undef, %entry ]
+  %mul34 = mul i32 %mul35.lcssa63, %inc4064
+  %mul35 = mul i32 %mul34, %mul35.lcssa63
+  %mul34.1 = mul i32 %mul35, %inc4064
+  %mul35.1 = mul i32 %mul34.1, %mul35
+  %mul34.2 = mul i32 %mul35.1, %inc4064
+  %mul35.2 = mul i32 %mul34.2, %mul35.1
+  %mul34.3 = mul i32 %mul35.2, %inc4064
+  %mul35.3 = mul i32 %mul34.3, %mul35.2
+  %mul34.4 = mul i32 %mul35.3, %inc4064
+  %mul35.4 = mul i32 %mul34.4, %mul35.3
+  %mul34.5 = mul i32 %mul35.4, %inc4064
+  %mul35.5 = mul i32 %mul34.5, %mul35.4
+  %mul34.6 = mul i32 %mul35.5, %inc4064
+  %mul35.6 = mul i32 %mul34.6, %mul35.5
+  %mul34.7 = mul i32 %mul35.6, %inc4064
+  %mul35.7 = mul i32 %mul34.7, %mul35.6
+  %mul34.8 = mul i32 %mul35.7, %inc4064
+  %mul35.8 = mul i32 %mul34.8, %mul35.7
+  %mul34.9 = mul i32 %mul35.8, %inc4064
+  %mul35.9 = mul i32 %mul34.9, %mul35.8
+  %mul34.10 = mul i32 %mul35.9, %inc4064
+  %mul35.10 = mul i32 %mul34.10, %mul35.9
+  %mul34.11 = mul i32 %mul35.10, %inc4064
+  %mul35.11 = mul i32 %mul34.11, %mul35.10
+  %mul34.12 = mul i32 %mul35.11, %inc4064
+  %mul35.12 = mul i32 %mul34.12, %mul35.11
+  %mul34.13 = mul i32 %mul35.12, %inc4064
+  %mul35.13 = mul i32 %mul34.13, %mul35.12
+  %mul34.14 = mul i32 %mul35.13, %inc4064
+  %mul35.14 = mul i32 %mul34.14, %mul35.13
+  %mul34.15 = mul i32 %mul35.14, %inc4064
+  %mul35.15 = mul i32 %mul34.15, %mul35.14
+  %inc40 = add i32 %inc4064, 1
+  br label %for.body33
+}
\ No newline at end of file