Index: include/polly/ScopInfo.h
===================================================================
--- include/polly/ScopInfo.h
+++ include/polly/ScopInfo.h
@@ -1287,9 +1287,6 @@
   /// @brief Flag to remember if the SCoP contained an error block or not.
   bool HasErrorBlock;
 
-  /// @brief Flag to indicate if the SCop has a complex control flow.
-  bool HasComplexCFG;
-
   /// Max loop depth.
   unsigned MaxLoopDepth;
 
@@ -1436,7 +1433,9 @@
   /// @param SD The ScopDetection analysis for the current function.
   /// @param DT The DominatorTree for the current function.
   /// @param LI The LoopInfo for the current function.
-  void buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD,
+  ///
+  /// @returns True if there was no problem and false otherwise.
+  bool buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD,
                                          DominatorTree &DT, LoopInfo &LI);
 
   /// @brief Propagate the domain constraints through the region @p R.
@@ -1463,7 +1462,9 @@
   /// @param SD The ScopDetection analysis for the current function.
   /// @param DT The DominatorTree for the current function.
   /// @param LI The LoopInfo for the current function.
-  void buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT,
+  ///
+  /// @returns True if there was no problem and false otherwise.
+  bool buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT,
                     LoopInfo &LI);
 
   /// @brief Check if a region part should be represented in the SCoP or not.
Index: lib/Analysis/ScopInfo.cpp
===================================================================
--- lib/Analysis/ScopInfo.cpp
+++ lib/Analysis/ScopInfo.cpp
@@ -2143,7 +2143,7 @@
       removeDomains(BB);
 }
 
-void Scop::buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT,
+bool Scop::buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT,
                         LoopInfo &LI) {
 
   bool IsOnlyNonAffineRegion = SD.isNonAffineSubRegion(R, R);
@@ -2160,9 +2160,11 @@
   DomainMap[EntryBB] = S;
 
   if (IsOnlyNonAffineRegion)
-    return;
+    return true;
+
+  if (!buildDomainsWithBranchConstraints(R, SD, DT, LI))
+    return false;
 
-  buildDomainsWithBranchConstraints(R, SD, DT, LI);
   propagateDomainConstraints(R, SD, DT, LI);
 
   // Error blocks and blocks dominated by them have been assumed to never be
@@ -2174,9 +2176,10 @@
   // instructions in the error block which, if the error block is not modeled,
   // can themselves not be constructed properly.
   removeErrorBlockDomains(SD, DT, LI);
+  return true;
 }
 
-void Scop::buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD,
+bool Scop::buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD,
                                              DominatorTree &DT, LoopInfo &LI) {
   auto &BoxedLoops = *SD.getBoxedLoops(&getRegion());
 
@@ -2199,7 +2202,8 @@
     if (RN->isSubRegion()) {
       Region *SubRegion = RN->getNodeAs<Region>();
       if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
-        buildDomainsWithBranchConstraints(SubRegion, SD, DT, LI);
+        if (!buildDomainsWithBranchConstraints(SubRegion, SD, DT, LI))
+          return false;
         continue;
       }
     }
@@ -2279,25 +2283,24 @@
       // successor block.
       isl_set *&SuccDomain = DomainMap[SuccBB];
 
-      if (HasComplexCFG) {
-        isl_set_free(CondSet);
-        continue;
-      }
       if (!SuccDomain)
         SuccDomain = CondSet;
       else
-        SuccDomain = isl_set_union(SuccDomain, CondSet);
-
-      SuccDomain = isl_set_coalesce(SuccDomain);
-      if (isl_set_n_basic_set(SuccDomain) > MaxConjunctsInDomain) {
-        auto *Empty = isl_set_empty(isl_set_get_space(SuccDomain));
-        isl_set_free(SuccDomain);
-        SuccDomain = Empty;
-        HasComplexCFG = true;
-        invalidate(COMPLEXITY, DebugLoc());
-      }
+        SuccDomain = isl_set_coalesce(isl_set_union(SuccDomain, CondSet));
+
+      // Check if the maximal number of domain conjuncts was reached.
+      // In case this happens we will clean up and bail.
+      if (isl_set_n_basic_set(SuccDomain) <= MaxConjunctsInDomain)
+        continue;
+
+      invalidate(COMPLEXITY, DebugLoc());
+      while (++u < ConditionSets.size())
+        isl_set_free(ConditionSets[u]);
+      return false;
     }
   }
+
+  return true;
 }
 
 /// @brief Return the domain for @p BB wrt @p DomainMap.
@@ -2771,10 +2774,9 @@
            unsigned MaxLoopDepth)
     : SE(&ScalarEvolution), R(R), IsOptimized(false),
       HasSingleExitEdge(R.getExitingBlock()), HasErrorBlock(false),
-      HasComplexCFG(false), MaxLoopDepth(MaxLoopDepth),
-      IslCtx(isl_ctx_alloc(), isl_ctx_free), Context(nullptr),
-      Affinator(this, LI), AssumedContext(nullptr), InvalidContext(nullptr),
-      Schedule(nullptr) {
+      MaxLoopDepth(MaxLoopDepth), IslCtx(isl_ctx_alloc(), isl_ctx_free),
+      Context(nullptr), Affinator(this, LI), AssumedContext(nullptr),
+      InvalidContext(nullptr), Schedule(nullptr) {
   isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_ABORT);
   buildContext();
 }
@@ -2784,7 +2786,8 @@
   addUserAssumptions(AC, DT, LI);
   buildInvariantEquivalenceClasses(SD);
 
-  buildDomains(&R, SD, DT, LI);
+  if (!buildDomains(&R, SD, DT, LI))
+    return;
 
   // Remove empty and ignored statements.
   // Exit early in case there are no executable statements left in this scop.