Bail as early as possible

[jdoerfert]

Summary

Instead of waiting for the domain construction to finish we will now
bail as early as possible in case a complexity problem is encountered.
This might save compile time but more importantly it makes the "abort"
explicit. While we can always check if we invalidated the assumed
context we can simply propagate the result of the construction back.
This also removes the HasComplexCFG flag that was used for the very
same reason.

[jdoerfert]

Hey Chris,

I would like your input on this patch.

I run into problems with your new HasComplexCFG flag as it will "silently" invalidate domains (ok not that silent because the flag exists but I din't think to check). Can you see if this more explicit approach works for you too?

Thanks in advance,

Johannes

[grosser]

From my perspective this LGTM.

Let's see if Chris has more input.

polly/trunk/include/polly/ScopInfo.h

private:
   bool IsOptimized;
 
   /// @brief True if the underlying region has a single exiting block.
   bool HasSingleExitEdge;
 
   /// @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;
 
   typedef std::list<ScopStmt> StmtSet;
   /// The statements in this Scop.
   StmtSet Stmts;
 
   /// Parameters of this Scop
private:
   void addLoopBoundsToHeaderDomain(Loop *L, LoopInfo &LI);
 
   /// @brief Compute the branching constraints for each basic block in @p R.
   ///
   /// @param R  The region we currently build branching conditions for.
   /// @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.
   ///
   /// @param R  The region we currently build branching conditions for.
   /// @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 removeErrorBlockDomains(ScopDetection &SD, DominatorTree &DT,
                                LoopInfo &LI);
 
   /// @brief Compute the domain for each basic block in @p R.
   ///
   /// @param R  The region we currently traverse.
   /// @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.
   ///
   /// If @p RN does not contain any useful calculation or is only reachable
   /// via error blocks we do not model it in the polyhedral representation.
   ///
   /// @param RN The region part to check.

polly/trunk/lib/Analysis/ScopInfo.cpp

if (containsErrorBlock(SubRegion->getNode(), getRegion(), LI, DT))
       removeDomains(SubRegion->getEntry());
   }
 
   for (auto *BB : R.blocks())
     if (isErrorBlock(*BB, R, LI, DT))
       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);
   auto *EntryBB = R->getEntry();
   auto *L = IsOnlyNonAffineRegion ? nullptr : LI.getLoopFor(EntryBB);
   int LD = getRelativeLoopDepth(L);
   auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx(), 0, LD + 1));
 
   while (LD-- >= 0) {
     S = addDomainDimId(S, LD + 1, L);
     L = L->getParentLoop();
   }
 
   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
   // executed. Representing them in the Scop does not add any value. In fact,
   // it is likely to cause issues during construction of the ScopStmts. The
   // contents of error blocks have not been verfied to be expressible and
   // will cause problems when building up a ScopStmt for them.
   // Furthermore, basic blocks dominated by error blocks may reference
   // 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());
 
   // To create the domain for each block in R we iterate over all blocks and
   // subregions in R and propagate the conditions under which the current region
   // element is executed. To this end we iterate in reverse post order over R as
   // it ensures that we first visit all predecessors of a region node (either a
   // basic block or a subregion) before we visit the region node itself.
   // Initially, only the domain for the SCoP region entry block is set and from
   // there we propagate the current domain to all successors, however we add the
   // condition that the successor is actually executed next.
   // As we are only interested in non-loop carried constraints here we can
   // simply skip loop back edges.
 
   ReversePostOrderTraversal<Region *> RTraversal(R);
   for (auto *RN : RTraversal) {
 
     // Recurse for affine subregions but go on for basic blocks and non-affine
     // subregions.
     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;
       }
     }
 
     if (containsErrorBlock(RN, getRegion(), LI, DT))
       HasErrorBlock = true;
 
     BasicBlock *BB = getRegionNodeBasicBlock(RN);
for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) {
         }
       }
 
       // Set the domain for the successor or merge it with an existing domain in
       // case there are multiple paths (without loop back edges) to the
       // 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(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;
 
-      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());
-      }
-    }
-  }
+      while (++u < ConditionSets.size())
+        isl_set_free(ConditionSets[u]);
+      return false;
+
+  return true;
 }
 
 /// @brief Return the domain for @p BB wrt @p DomainMap.
 ///
 /// This helper function will lookup @p BB in @p DomainMap but also handle the
 /// case where @p BB is contained in a non-affine subregion using the region
 /// tree obtained by @p RI.
 static __isl_give isl_set *
assert(MaxLD >= MinLD &&
          "Maximal loop depth was smaller than mininaml loop depth?");
   return MaxLD - MinLD + 1;
 }
 
 Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI,
            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();
 }
 
 void Scop::init(AliasAnalysis &AA, AssumptionCache &AC, ScopDetection &SD,
                 DominatorTree &DT, LoopInfo &LI) {
   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.
   simplifySCoP(true, DT, LI);
   if (Stmts.empty())
     return;
 
   // The ScopStmts now have enough information to initialize themselves.