Index: polly/trunk/include/polly/Support/SCEVAffinator.h
===================================================================
--- polly/trunk/include/polly/Support/SCEVAffinator.h
+++ polly/trunk/include/polly/Support/SCEVAffinator.h
@@ -118,6 +118,7 @@
   PWACtx visitUnknown(const llvm::SCEVUnknown *E);
   PWACtx visitSDivInstruction(llvm::Instruction *SDiv);
   PWACtx visitSRemInstruction(llvm::Instruction *SRem);
+  PWACtx complexityBailout();
 
   friend struct llvm::SCEVVisitor<SCEVAffinator, PWACtx>;
 };
Index: polly/trunk/lib/Support/SCEVAffinator.cpp
===================================================================
--- polly/trunk/lib/Support/SCEVAffinator.cpp
+++ polly/trunk/lib/Support/SCEVAffinator.cpp
@@ -368,7 +368,7 @@
   for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
     Sum = combine(Sum, visit(Expr->getOperand(i)), isl_pw_aff_add);
     if (isTooComplex(Sum))
-      return std::make_pair(nullptr, nullptr);
+      return complexityBailout();
   }
 
   return Sum;
@@ -380,7 +380,7 @@
   for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
     Prod = combine(Prod, visit(Expr->getOperand(i)), isl_pw_aff_mul);
     if (isTooComplex(Prod))
-      return std::make_pair(nullptr, nullptr);
+      return complexityBailout();
   }
 
   return Prod;
@@ -431,7 +431,7 @@
   for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
     Max = combine(Max, visit(Expr->getOperand(i)), isl_pw_aff_max);
     if (isTooComplex(Max))
-      return std::make_pair(nullptr, nullptr);
+      return complexityBailout();
   }
 
   return Max;
@@ -532,3 +532,11 @@
   llvm_unreachable(
       "Unknowns SCEV was neither parameter nor a valid instruction.");
 }
+
+PWACtx SCEVAffinator::complexityBailout() {
+  // We hit the complexity limit for affine expressions; invalidate the scop
+  // and return a constant zero.
+  const DebugLoc &Loc = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
+  S->invalidate(COMPLEXITY, Loc);
+  return visit(SE.getZero(Type::getInt32Ty(BB->getContext())));
+}
Index: polly/trunk/test/ScopInfo/pwaff-complexity-bailout.ll
===================================================================
--- polly/trunk/test/ScopInfo/pwaff-complexity-bailout.ll
+++ polly/trunk/test/ScopInfo/pwaff-complexity-bailout.ll
@@ -0,0 +1,37 @@
+; RUN: opt %loadPolly -analyze -polly-scops -pass-remarks-analysis=.* < %s 2>&1 > /dev/null | FileCheck %s
+
+; Make sure we hit the complexity bailout, and don't crash.
+; CHECK: Low complexity assumption:       {  : false }
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "thumbv8--linux-android"
+
+define hidden void @f(i32 %arg1, i32 %arg2, i32 %cond, i32 %tmp, i32 %tmp196) {
+entry:
+  %div = sdiv i32 %tmp, 8
+  %div10 = sdiv i32 %arg1, 8
+  %div11 = sdiv i32 %tmp196, 2
+  %add = add nsw i32 %div10, %div11
+  %sub19 = add nsw i32 %div, -1
+  %cmp20 = icmp slt i32 %add, %sub19
+  %add.sub19 = select i1 %cmp20, i32 %add, i32 %sub19
+  %div469 = sdiv i32 %arg2, 8
+  %cmp.i68 = icmp slt i32 %div469, %cond
+  %cond.i = select i1 %cmp.i68, i32 %cond, i32 %div469
+  %sub.i69 = add i32 0, %div469
+  %cmp9.i = icmp sgt i32 %sub.i69, %add.sub19
+  %sub15.max_x.i = select i1 %cmp9.i, i32 %add.sub19, i32 %sub.i69
+  %sub30.i = sub nsw i32 %sub15.max_x.i, %cond.i
+  %add31.i = add nsw i32 %sub30.i, 1
+  br label %for.body.us.i
+
+for.body.us.i:
+  br label %for.body47.us.i
+
+for.body47.us.i:
+  %cmp45.us.i = icmp ult i32 0, %add31.i
+  br i1 %cmp45.us.i, label %for.body47.us.i, label %for.cond44.for.cond.cleanup46_crit_edge.us.i
+
+for.cond44.for.cond.cleanup46_crit_edge.us.i:
+  br label %for.body.us.i
+}