Propagate complexity problems during domain generation [NFC]

  This patches makes the propagation of complexity problems during
  domain generation consistent. Additionally, it makes it less likely to
  encounter ill-formed domains later, e.g., during schedule generation.

llvm-svn: 269055

3 files changed, 104 insertions, 27 deletions

diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index 75eb254..7e79cd7 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -1563,7 +1563,9 @@ private:
   ///
   /// @param L  The loop to process.
   /// @param LI The LoopInfo for the current function.
-  void addLoopBoundsToHeaderDomain(Loop *L, LoopInfo &LI);
+  ///
+  /// @returns True if there was no problem and false otherwise.
+  bool addLoopBoundsToHeaderDomain(Loop *L, LoopInfo &LI);
 
   /// @brief Compute the branching constraints for each basic block in @p R.
   ///
@@ -1582,7 +1584,9 @@ private:
   /// @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 propagateDomainConstraints(Region *R, ScopDetection &SD,
+  ///
+  /// @returns True if there was no problem and false otherwise.
+  bool propagateDomainConstraints(Region *R, ScopDetection &SD,
                                   DominatorTree &DT, LoopInfo &LI);
 
   /// @brief Propagate invalid domains of statements through @p R.
@@ -1596,7 +1600,9 @@ private:
   /// @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 propagateInvalidStmtDomains(Region *R, ScopDetection &SD,
+  ///
+  /// @returns True if there was no problem and false otherwise.
+  bool propagateInvalidStmtDomains(Region *R, ScopDetection &SD,
                                    DominatorTree &DT, LoopInfo &LI);
 
   /// @brief Compute the domain for each basic block in @p R.
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index f02a807..48b0837 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -1238,7 +1238,7 @@ static __isl_give isl_set *buildConditionSet(ICmpInst::Predicate Pred,
 /// This will fill @p ConditionSets with the conditions under which control
 /// will be moved from @p SI to its successors. Hence, @p ConditionSets will
 /// have as many elements as @p SI has successors.
-static void
+static bool
 buildConditionSets(ScopStmt &Stmt, SwitchInst *SI, Loop *L,
                    __isl_keep isl_set *Domain,
                    SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
@@ -1273,6 +1273,8 @@ buildConditionSets(ScopStmt &Stmt, SwitchInst *SI, Loop *L,
       Domain, isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion));
 
   isl_pw_aff_free(LHS);
+
+  return true;
 }
 
 /// @brief Build the conditions sets for the branch condition @p Condition in
@@ -1283,7 +1285,7 @@ buildConditionSets(ScopStmt &Stmt, SwitchInst *SI, Loop *L,
 /// have as many elements as @p TI has successors. If @p TI is nullptr the
 /// context under which @p Condition is true/false will be returned as the
 /// new elements of @p ConditionSets.
-static void
+static bool
 buildConditionSets(ScopStmt &Stmt, Value *Condition, TerminatorInst *TI,
                    Loop *L, __isl_keep isl_set *Domain,
                    SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
@@ -1299,10 +1301,12 @@ buildConditionSets(ScopStmt &Stmt, Value *Condition, TerminatorInst *TI,
     auto Opcode = BinOp->getOpcode();
     assert(Opcode == Instruction::And || Opcode == Instruction::Or);
 
-    buildConditionSets(Stmt, BinOp->getOperand(0), TI, L, Domain,
-                       ConditionSets);
-    buildConditionSets(Stmt, BinOp->getOperand(1), TI, L, Domain,
-                       ConditionSets);
+    if (!buildConditionSets(Stmt, BinOp->getOperand(0), TI, L, Domain,
+                            ConditionSets))
+      return false;
+    if (!buildConditionSets(Stmt, BinOp->getOperand(1), TI, L, Domain,
+                            ConditionSets))
+      return false;
 
     isl_set_free(ConditionSets.pop_back_val());
     isl_set *ConsCondPart0 = ConditionSets.pop_back_val();
@@ -1352,13 +1356,14 @@ buildConditionSets(ScopStmt &Stmt, Value *Condition, TerminatorInst *TI,
   if (TooComplex) {
     S.invalidate(COMPLEXITY, TI ? TI->getDebugLoc() : DebugLoc());
     isl_set_free(AlternativeCondSet);
-    AlternativeCondSet = isl_set_empty(isl_set_get_space(ConsequenceCondSet));
     isl_set_free(ConsequenceCondSet);
-    ConsequenceCondSet = isl_set_empty(isl_set_get_space(AlternativeCondSet));
+    return false;
   }
 
   ConditionSets.push_back(ConsequenceCondSet);
   ConditionSets.push_back(isl_set_coalesce(AlternativeCondSet));
+
+  return true;
 }
 
 /// @brief Build the conditions sets for the terminator @p TI in the @p Domain.
@@ -1366,7 +1371,7 @@ buildConditionSets(ScopStmt &Stmt, Value *Condition, TerminatorInst *TI,
 /// This will fill @p ConditionSets with the conditions under which control
 /// will be moved from @p TI to its successors. Hence, @p ConditionSets will
 /// have as many elements as @p TI has successors.
-static void
+static bool
 buildConditionSets(ScopStmt &Stmt, TerminatorInst *TI, Loop *L,
                    __isl_keep isl_set *Domain,
                    SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
@@ -1378,7 +1383,7 @@ buildConditionSets(ScopStmt &Stmt, TerminatorInst *TI, Loop *L,
 
   if (TI->getNumSuccessors() == 1) {
     ConditionSets.push_back(isl_set_copy(Domain));
-    return;
+    return true;
   }
 
   Value *Condition = getConditionFromTerminator(TI);
@@ -1900,7 +1905,10 @@ void Scop::addUserAssumptions(AssumptionCache &AC, DominatorTree &DT,
     }
 
     SmallVector<isl_set *, 2> ConditionSets;
-    buildConditionSets(*Stmts.begin(), Val, nullptr, L, Context, ConditionSets);
+    if (!buildConditionSets(*Stmts.begin(), Val, nullptr, L, Context,
+                            ConditionSets))
+      continue;
+
     assert(ConditionSets.size() == 2);
     isl_set_free(ConditionSets[1]);
 
@@ -2273,7 +2281,8 @@ bool Scop::buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT,
   if (!buildDomainsWithBranchConstraints(R, SD, DT, LI))
     return false;
 
-  propagateDomainConstraints(R, SD, DT, LI);
+  if (!propagateDomainConstraints(R, SD, DT, LI))
+    return false;
 
   // 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,
@@ -2287,7 +2296,8 @@ bool Scop::buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT,
   // with an empty set. Additionally, we will record for each block under which
   // parameter combination it would be reached via an error block in its
   // InvalidDomain. This information is needed during load hoisting.
-  propagateInvalidStmtDomains(R, SD, DT, LI);
+  if (!propagateInvalidStmtDomains(R, SD, DT, LI))
+    return false;
 
   return true;
 }
@@ -2351,7 +2361,7 @@ static __isl_give isl_set *adjustDomainDimensions(Scop &S,
   return Dom;
 }
 
-void Scop::propagateInvalidStmtDomains(Region *R, ScopDetection &SD,
+bool Scop::propagateInvalidStmtDomains(Region *R, ScopDetection &SD,
                                        DominatorTree &DT, LoopInfo &LI) {
   auto &BoxedLoops = *SD.getBoxedLoops(&getRegion());
 
@@ -2426,11 +2436,13 @@ void Scop::propagateInvalidStmtDomains(Region *R, ScopDetection &SD,
 
       isl_set_free(InvalidDomain);
       invalidate(COMPLEXITY, TI->getDebugLoc());
-      return;
+      return false;
     }
 
     Stmt->setInvalidDomain(InvalidDomain);
   }
+
+  return true;
 }
 
 void Scop::propagateDomainConstraintsToRegionExit(
@@ -2549,8 +2561,9 @@ bool Scop::buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD,
     SmallVector<isl_set *, 8> ConditionSets;
     if (RN->isSubRegion())
       ConditionSets.push_back(isl_set_copy(Domain));
-    else
-      buildConditionSets(*getStmtFor(BB), TI, BBLoop, Domain, ConditionSets);
+    else if (!buildConditionSets(*getStmtFor(BB), TI, BBLoop, Domain,
+                                 ConditionSets))
+      return false;
 
     // Now iterate over the successors and set their initial domain based on
     // their condition set. We skip back edges here and have to be careful when
@@ -2672,7 +2685,7 @@ __isl_give isl_set *Scop::getPredecessorDomainConstraints(BasicBlock *BB,
   return PredDom;
 }
 
-void Scop::propagateDomainConstraints(Region *R, ScopDetection &SD,
+bool Scop::propagateDomainConstraints(Region *R, ScopDetection &SD,
                                       DominatorTree &DT, LoopInfo &LI) {
   // Iterate over the region R and propagate the domain constrains from the
   // predecessors to the current node. In contrast to the
@@ -2691,7 +2704,8 @@ void Scop::propagateDomainConstraints(Region *R, ScopDetection &SD,
     if (RN->isSubRegion()) {
       Region *SubRegion = RN->getNodeAs<Region>();
       if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
-        propagateDomainConstraints(SubRegion, SD, DT, LI);
+        if (!propagateDomainConstraints(SubRegion, SD, DT, LI))
+          return false;
         continue;
       }
     }
@@ -2707,8 +2721,11 @@ void Scop::propagateDomainConstraints(Region *R, ScopDetection &SD,
 
     Loop *BBLoop = getRegionNodeLoop(RN, LI);
     if (BBLoop && BBLoop->getHeader() == BB && getRegion().contains(BBLoop))
-      addLoopBoundsToHeaderDomain(BBLoop, LI);
+      if (!addLoopBoundsToHeaderDomain(BBLoop, LI))
+        return false;
   }
+
+  return true;
 }
 
 /// @brief Create a map from SetSpace -> SetSpace where the dimensions @p Dim
@@ -2731,7 +2748,7 @@ createNextIterationMap(__isl_take isl_space *SetSpace, unsigned Dim) {
   return NextIterationMap;
 }
 
-void Scop::addLoopBoundsToHeaderDomain(Loop *L, LoopInfo &LI) {
+bool Scop::addLoopBoundsToHeaderDomain(Loop *L, LoopInfo &LI) {
   int LoopDepth = getRelativeLoopDepth(L);
   assert(LoopDepth >= 0 && "Loop in region should have at least depth one");
 
@@ -2764,8 +2781,9 @@ void Scop::addLoopBoundsToHeaderDomain(Loop *L, LoopInfo &LI) {
     else {
       SmallVector<isl_set *, 8> ConditionSets;
       int idx = BI->getSuccessor(0) != HeaderBB;
-      buildConditionSets(*getStmtFor(LatchBB), TI, L, LatchBBDom,
-                         ConditionSets);
+      if (!buildConditionSets(*getStmtFor(LatchBB), TI, L, LatchBBDom,
+                              ConditionSets))
+        return false;
 
       // Free the non back edge condition set as we do not need it.
       isl_set_free(ConditionSets[1 - idx]);
@@ -2803,12 +2821,13 @@ void Scop::addLoopBoundsToHeaderDomain(Loop *L, LoopInfo &LI) {
   // <nsw> tag.
   if (Affinator.hasNSWAddRecForLoop(L)) {
     isl_set_free(Parts.first);
-    return;
+    return true;
   }
 
   isl_set *UnboundedCtx = isl_set_params(Parts.first);
   recordAssumption(INFINITELOOP, UnboundedCtx,
                    HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION);
+  return true;
 }
 
 void Scop::buildAliasChecks(AliasAnalysis &AA) {
diff --git a/polly/test/ScopInfo/early_exit_for_complex_domains.ll b/polly/test/ScopInfo/early_exit_for_complex_domains.ll
new file mode 100644
index 0000000..660b8c4
--- /dev/null
+++ b/polly/test/ScopInfo/early_exit_for_complex_domains.ll
@@ -0,0 +1,52 @@
+; RUN: opt %loadPolly -polly-scops -disable-output < %s
+;
+; Check we do not crash.
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct.regnode_charclass_class.2.42.654.690.726.870.978.1770.1806.1842.2166.2274.2382.2598.2814.3030.3064 = type { i8, i8, i16, i32, [32 x i8], [4 x i8] }
+
+; Function Attrs: nounwind uwtable
+define void @S_cl_or(%struct.regnode_charclass_class.2.42.654.690.726.870.978.1770.1806.1842.2166.2274.2382.2598.2814.3030.3064* %cl, %struct.regnode_charclass_class.2.42.654.690.726.870.978.1770.1806.1842.2166.2274.2382.2598.2814.3030.3064* %or_with) #0 {
+entry:
+  %flags = getelementptr inbounds %struct.regnode_charclass_class.2.42.654.690.726.870.978.1770.1806.1842.2166.2274.2382.2598.2814.3030.3064, %struct.regnode_charclass_class.2.42.654.690.726.870.978.1770.1806.1842.2166.2274.2382.2598.2814.3030.3064* %or_with, i64 0, i32 0
+  %0 = load i8, i8* %flags, align 4, !tbaa !1
+  %conv = zext i8 %0 to i32
+  %1 = load i8, i8* undef, align 4, !tbaa !1
+  br label %land.lhs.true35
+
+land.lhs.true35:                                  ; preds = %entry
+  %and38 = and i32 %conv, 2
+  %tobool39 = icmp ne i32 %and38, 0
+  %and42 = and i8 %1, 2
+  %tobool43 = icmp eq i8 %and42, 0
+  %or.cond45 = and i1 %tobool39, %tobool43
+  br i1 %or.cond45, label %if.end91, label %for.body49
+
+for.body49:                                       ; preds = %land.lhs.true35
+  %2 = load i8, i8* %flags, align 4, !tbaa !1
+  %and65 = and i8 %2, 8
+  %tobool66 = icmp eq i8 %and65, 0
+  br i1 %tobool66, label %if.end91, label %for.body71
+
+for.body71:                                       ; preds = %for.body71, %for.body49
+  %arrayidx77 = getelementptr inbounds %struct.regnode_charclass_class.2.42.654.690.726.870.978.1770.1806.1842.2166.2274.2382.2598.2814.3030.3064, %struct.regnode_charclass_class.2.42.654.690.726.870.978.1770.1806.1842.2166.2274.2382.2598.2814.3030.3064* %cl, i64 0, i32 5, i64 0
+  store i8 undef, i8* %arrayidx77, align 1, !tbaa !7
+  br i1 false, label %for.body71, label %if.end91
+
+if.end91:                                         ; preds = %for.body71, %for.body49, %land.lhs.true35
+  ret void
+}
+
+attributes #0 = { nounwind uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 3.9.0 (http://llvm.org/git/clang.git af4db76e059c1a3f4a7f437001051ccebc8a50fe)"}
+!1 = !{!2, !3, i64 0}
+!2 = !{!"regnode_charclass_class", !3, i64 0, !3, i64 1, !5, i64 2, !6, i64 4, !3, i64 8, !3, i64 40}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C/C++ TBAA"}
+!5 = !{!"short", !3, i64 0}
+!6 = !{!"int", !3, i64 0}
+!7 = !{!3, !3, i64 0}