Only add user assumptions on known parameters [NFC]

  Before, assumptions derived from llvm.assume could reference new
  parameters that were not known to the SCoP before. These were neither
  beneficial to the representation nor to the user that reads the
  emitted remark. Now we project them out and keep only user assumptions
  on known parameters. Nevertheless, the new parameters are still part
  of the SCoPs parameter space as the SCEVAffinator currently adds them
  on demand.

llvm-svn: 267441

3 files changed, 131 insertions, 1 deletions

diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 6baa395f06c..18912169369 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -1877,7 +1877,15 @@ void Scop::addUserAssumptions(AssumptionCache &AC, DominatorTree &DT,
       continue;
     }
 
-    addParams(DetectedParams);
+    // Collect all newly introduced parameters.
+    ParameterSetTy NewParams;
+    for (auto *Param : DetectedParams) {
+      Param = extractConstantFactor(Param, *SE).second;
+      Param = getRepresentingInvariantLoadSCEV(Param);
+      if (Parameters.count(Param))
+        continue;
+      NewParams.insert(Param);
+    }
 
     SmallVector<isl_set *, 2> ConditionSets;
     buildConditionSets(*Stmts.begin(), Val, nullptr, L, Context, ConditionSets);
@@ -1885,6 +1893,22 @@ void Scop::addUserAssumptions(AssumptionCache &AC, DominatorTree &DT,
     isl_set_free(ConditionSets[1]);
 
     auto *AssumptionCtx = ConditionSets[0];
+
+    // Project out newly introduced parameters as they are not otherwise useful.
+    if (!NewParams.empty()) {
+      for (unsigned u = 0; u < isl_set_n_param(AssumptionCtx); u++) {
+        auto *Id = isl_set_get_dim_id(AssumptionCtx, isl_dim_param, u);
+        auto *Param = static_cast<const SCEV *>(isl_id_get_user(Id));
+        isl_id_free(Id);
+
+        if (!NewParams.count(Param))
+          continue;
+
+        AssumptionCtx =
+            isl_set_project_out(AssumptionCtx, isl_dim_param, u--, 1);
+      }
+    }
+
     emitOptimizationRemarkAnalysis(
         F.getContext(), DEBUG_TYPE, F, CI->getDebugLoc(),
         "Use user assumption: " + stringFromIslObj(AssumptionCtx));
diff --git a/polly/test/ScopInfo/user_provided_assumptions_2.ll b/polly/test/ScopInfo/user_provided_assumptions_2.ll
new file mode 100644
index 00000000000..f85c30e272f
--- /dev/null
+++ b/polly/test/ScopInfo/user_provided_assumptions_2.ll
@@ -0,0 +1,52 @@
+; RUN: opt %loadPolly -pass-remarks-analysis="polly-scops" -polly-scops -disable-output < %s 2>&1 | FileCheck %s
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s --check-prefix=SCOP
+;
+; CHECK:      remark: <unknown>:0:0: SCoP begins here.
+; CHECK-NEXT: remark: <unknown>:0:0: Use user assumption: { : }
+; CHECK-NEXT: remark: <unknown>:0:0: SCoP ends here.
+
+; SCOP:      Context:
+; SCOP-NEXT: [N, M] -> { : -2147483648 <= N <= 2147483647 and -2147483648 <= M <= 2147483647 }
+; SCOP:      Assumed Context:
+; SCOP-NEXT: [N, M] -> { : }
+; SCOP:      Invalid Context:
+; SCOP-NEXT: [N, M] -> { : 1 = 0 }
+;
+;    int f(int *A, int N, int M) {
+;      __builtin_assume(M > 0);
+;      for (int i = 0; i < N; i++)
+;        A[i]++;
+;      return M;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define i32 @f(i32* %A, i32 %N, i32 %M) {
+entry:
+  %cmp = icmp sgt i32 %M, 0
+  call void @llvm.assume(i1 %cmp)
+  %tmp = sext i32 %N to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %cmp1 = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp1, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp1 = load i32, i32* %arrayidx, align 4
+  %inc = add nsw i32 %tmp1, 1
+  store i32 %inc, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret i32 %M
+}
+
+declare void @llvm.assume(i1) #1
+
diff --git a/polly/test/ScopInfo/user_provided_assumptions_3.ll b/polly/test/ScopInfo/user_provided_assumptions_3.ll
new file mode 100644
index 00000000000..f16df219218
--- /dev/null
+++ b/polly/test/ScopInfo/user_provided_assumptions_3.ll
@@ -0,0 +1,54 @@
+; RUN: opt %loadPolly -pass-remarks-analysis="polly-scops" -polly-scops -disable-output < %s 2>&1 | FileCheck %s
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s --check-prefix=SCOP
+;
+; CHECK:      remark: <unknown>:0:0: SCoP begins here.
+; CHECK-NEXT: remark: <unknown>:0:0: Use user assumption: [N] -> { : N >= 2 }
+; CHECK-NEXT: remark: <unknown>:0:0: SCoP ends here.
+
+; SCOP:      Context:
+; SCOP-NEXT: [N, M] -> { : 2 <= N <= 2147483647 and -2147483648 <= M <= 2147483647 }
+; SCOP:      Assumed Context:
+; SCOP-NEXT: [N, M] -> { : }
+; SCOP:      Invalid Context:
+; SCOP-NEXT: [N, M] -> { : 1 = 0 }
+;
+;    int f(int *A, int N, int M) {
+;      __builtin_assume(M > 0 && N > M);
+;      for (int i = 0; i < N; i++)
+;        A[i]++;
+;      return M;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define i32 @f(i32* %A, i32 %N, i32 %M) {
+entry:
+  %cmp = icmp sgt i32 %M, 0
+  %cmp1 = icmp sgt i32 %N, %M
+  %and = and i1 %cmp, %cmp1
+  call void @llvm.assume(i1 %and)
+  %tmp1 = sext i32 %N to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %land.end
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %cmp2 = icmp slt i64 %indvars.iv, %tmp1
+  br i1 %cmp2, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp2 = load i32, i32* %arrayidx, align 4
+  %inc = add nsw i32 %tmp2, 1
+  store i32 %inc, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret i32 %M
+}
+
+declare void @llvm.assume(i1) #1
+