Propagate Trip count Assumptions to runtime check

[sabuasal]

Summary

Propagate Trip count Assumptions to runtime check

  This patch updates Polly to use the assumptions we add for trip count
  to simplify the conditions generated in the runtime check added for the
  Scop. We accomplish this by intersecting the Trip Count assumptions
  with the InvalidContext (used for alias checks) then gist these assumptions
  that are already included in the AssumedContext.

  This patch saves about 54Kb in Android build (less than 0.01%) and it
  simplifies the generated runtime check.

[Meinersbur]

lib/Analysis/ScopInfo.cpp

204

[typo] alaias

test/ScopDetect/model-dowhile-update-rtc.ll

29

[typo] NIFIXTRC

33

p_0 >= 5 && !(p_0 <= -1 || p_0 == 2147483647) is equivalent to p_0 >= 5 && p_0 > -1 && p_0 != 2147483647 which could be simplified to p_0 >= 5 && p_0 != 2147483647, ie the FIXRTC case. I guess this is a consequence of having split InvalidContext and AssumedContext to avoid a complement().

I'd prefer some more intelligent treatment of the InvalidContext and AssumedContext handling over special handling of UPPERBOUND assumptions.

The buildMinMaxAccess change is not reflected in this test case.

[sabuasal]

test/ScopDetect/model-dowhile-update-rtc.ll

33

I'd prefer some more intelligent treatment of the InvalidContext and AssumedContext handling over special handling of UPPERBOUND assumptions.

Can you please clarify, are you asking for a different way to propagate the assumptions that don't involve simply intersecting them?

[Meinersbur]

test/ScopDetect/model-dowhile-update-rtc.ll

33

One could determine whether a complement() would actually be expensive. E.g. for p_0 >= 5 we have have choices:

1. Add p_0 >= 5 to AssumedContext
2. Add p_0 < 5 to InvalidContext

For this case, they are equally complex, so we could prefer one over the other.

Another idea is to apply InvalidContext = isl_set_gist(InvalidContext, AssumedContext) that theoretically would remove unnecessary conditions from InvalidContext.

Can you confirm that the separation of InvalidContext/AssumedContext is the issue? I am currently just assuming that.

[sabuasal]

test/ScopDetect/model-dowhile-update-rtc.ll

33

The buildMinMaxAccess change is not reflected in this test case.

Thanks for the catch. First,, this is no longer needed since the buildMinMaxAccess already uses the updated domains for the statements (the ones that got intersected and gisted with RestrictDomainParams). Also, I updated the test case to show the effect on the AliasGroup.

For this case, they are equally complex, so we could prefer one over the other.

Thanks for the explanation, I agree and I did it using by modifying the first suggestion (in the parent patch). In this patch I just want the Invalid Context to look a bit more simplified.

Another idea is to apply InvalidContext = isl_set_gist(InvalidContext, AssumedContext) that theoretically
would remove unnecessary conditions from InvalidContext.

I agree. I am just not sure it falls within the Scop of this patch. Maybe in a later patch since I think such a change will update lots of test cases as well.

Can you confirm that the separation of InvalidContext/AssumedContext is the issue? I am currently just assuming that.

I confirm. We build these two context separately then we generate an AST in:

IslAst::buildRunCondition(Scop &S, __isl_keep isl_ast_build *Build) {

isl_ast_expr *RunCondition;

That is why the AST we get is not the most simplified. My goal from the test case it to show that propagating the info to InvalidContext will make it a bit cleaner.

[sabuasal]

Also, please let me know if you think it'll make sense to commit the two patches at once (once they are approved).

[Meinersbur]

lib/Analysis/ScopInfo.cpp

202–203

[type] first letter case: Avoid, Single, Iteration

3051–3053

[suggestion] This seem to be useful enough to be enabled by default and outside of enforceAssumptionsForAvoidsingleIter since it is unrelated.

test/ScopDetect/model-dowhile-update-rtc.ll

4

-S has no effect with --disable-output.

[serious] Is -O3 should not be necessary either; if some transformation is required by -polly-ast, it should be baked-into the test case.

lib/Analysis/ScopInfo.cpp

static cl::opt<bool> PollyPrintInstructions(
     cl::Hidden, cl::Optional, cl::init(false), cl::cat(PollyCategory));
 
 static cl::opt<bool>
     HandleDoWhile("polly-model-do-while",
                   cl::desc("Prune exeution domain of statements to ignore"
                            " disjunction sets that only have one instance"),
                   cl::Hidden, cl::ZeroOrMore, cl::init(false),
                   cl::cat(PollyCategory));
+
+static cl::opt<bool>
+    CleanRTC("polly-clean-rtc",
+             cl::desc("Propagate parameter restrictions form Trip count"
+                      " assumptions to overflow and alaias checks"),
+             cl::Hidden, cl::ZeroOrMore, cl::init(false),
+             cl::cat(PollyCategory));
+
 //===----------------------------------------------------------------------===//
 
 // Create a sequence of two schedules. Either argument may be null and is
 // interpreted as the empty schedule. Can also return null if both schedules are
 // empty.
 static isl::schedule combineInSequence(isl::schedule Prev, isl::schedule Succ) {
   if (!Prev)
     return Succ;
if (isl_set_n_param(Set.get()) > RunTimeChecksMaxParameters) {
     unsigned InvolvedParams = 0;
     for (unsigned u = 0, e = isl_set_n_param(Set.get()); u < e; u++)
       if (Set.involves_dims(isl::dim::param, u, 1))
         InvolvedParams++;
 
     if (InvolvedParams > RunTimeChecksMaxParameters)
       return false;
   }
+  // Simplify the Alias conditon by intersecting with the
+  // trip count asumption that makes trip count always >= 1.
+  if (CleanRTC && !S.getRestrictDomainParams().plain_is_universe())
+    Set = Set.intersect_params(S.getRestrictDomainParams())
+              .coalesce()
+              .gist_params(S.getRestrictDomainParams());
 
   MinPMA = Set.lexmin_pw_multi_aff();
   MaxPMA = Set.lexmax_pw_multi_aff();
 
   MinPMA = MinPMA.coalesce();
   MaxPMA = MaxPMA.coalesce();
 
   // Adjust the last dimension of the maximal access by one as we want to
if (!RestrictDomainParams.plain_is_universe()) {
     for (ScopStmt &Stmt : *this) {
       isl::set Dom = Stmt.getDomain();
       isl::set NewDom = Dom.intersect_params(RestrictDomainParams);
       NewDom = NewDom.coalesce();
       NewDom = NewDom.gist_params(RestrictDomainParams);
       Stmt.updateDomain(NewDom);
     }
     Schedule = Schedule.gist_domain_params(RestrictDomainParams);
+    if (CleanRTC)
+      InvalidContext = InvalidContext.intersect_params(RestrictDomainParams)
+                           .coalesce()
+                           .gist_params(RestrictDomainParams);
   }
 }
 
 MemoryAccess *Scop::lookupBasePtrAccess(MemoryAccess *MA) {
   Value *PointerBase = MA->getOriginalBaseAddr();
 
   auto *PointerBaseInst = dyn_cast<Instruction>(PointerBase);
   if (!PointerBaseInst)
     return nullptr;
 
   auto *BasePtrStmt = getStmtFor(PointerBaseInst);
   if (!BasePtrStmt)
     return nullptr;
 
   return BasePtrStmt->getArrayAccessOrNULLFor(PointerBaseInst);

test/ScopDetect/model-dowhile-update-rtc.ll

+; REQUIRES: asserts
+; Original C code:
+;void foo(int* A, int* B, unsigned  n) {
+;
+;    unsigned idx =5;
+;    do {
+;      A[idx] += B[idx];
+;      idx++;
+;    } while (idx <= n);
+;}
+
+; This test checks that assumptions for the Trip Count added by modeling
+; do-while like loops can be used to simplify the runtime check for the Scop.
+
+; In the example below we were able to get rid of "n <= -1" in the RTC
+; since we added the assumption "n >= 5".
+
+; RUN: opt -S -polly -O3 -debug-only=polly-ast -debug-only=polly-scops\
+; RUN:     -polly-process-unprofitable %s -polly-model-do-while=true\
+; RUN:     -polly-clean-rtc=false &> %t1
+
+; RUN: opt -S -polly -O3 -debug-only=polly-ast -debug-only=polly-scops\
+; RUN:     -polly-process-unprofitable %s -polly-model-do-while=true\
+; RUN:     -polly-clean-rtc=true &> %t2
+
+; RUN: FileCheck %s < %t1 --check-prefix=NOFIXRTC
+; RUN: FileCheck %s < %t2 --check-prefix=FIXRTC
+
+; NOFIXTRC: Invalid Context:
+; NOFIXRTC:  p_0 < 0
+; NOFIXRTC: :: isl ast :: foo
+; NOFIXRTC: [p_0] -> {  : -2147483648 <= p_0 <= 2147483647 }
+; NOFIXRTC: if (p_0 >= 5 && 0 == (p_0 <= -1 || p_0 == 2147483647) && (&MemRef0[p_0 + 1] <= &MemRef1[5] || &MemRef1[p_0 + 1] <= &MemRef0[5]))
+
+; FIXTRC: Invalid Context:
+; FIXRTC-NOT: p_0 < 0
+; FIXRTC: :: isl ast :: foo :: %do.body---%do.end
+; FIXRTC: [p_0] -> {  : -2147483648 <= p_0 <= 2147483647 }
+; FIXRTC: if (p_0 >= 5 && 0 == (p_0 == 2147483647) && (&MemRef0[p_0 + 1] <= &MemRef1[5] || &MemRef1[p_0 + 1] <= &MemRef0[5]))
+
+; Function Attrs: norecurse nounwind
+define dso_local void @foo(i32* nocapture %A, i32* nocapture readonly %B, i32 %n) local_unnamed_addr {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  br label %do.body
+
+do.body:                                          ; preds = %do.body, %entry.split
+  %idx.0 = phi i32 [ 5, %entry.split ], [ %inc, %do.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %B, i32 %idx.0
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx1 = getelementptr inbounds i32, i32* %A, i32 %idx.0
+  %1 = load i32, i32* %arrayidx1, align 4
+  %add = add nsw i32 %1, %0
+  store i32 %add, i32* %arrayidx1, align 4
+  %inc = add i32 %idx.0, 1
+  %cmp = icmp ugt i32 %inc, %n
+  br i1 %cmp, label %do.end, label %do.body
+
+do.end:                                           ; preds = %do.body
+  ret void
+}