Page MenuHomePhabricator

Propagate Trip count Assumptions to runtime check
Needs ReviewPublic

Authored by sabuasal on Jun 13 2019, 4:04 PM.

Details

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.

Diff Detail

Event Timeline

sabuasal created this revision.Jun 13 2019, 4:04 PM
Herald added a project: Restricted Project. · View Herald Transcript
sabuasal edited the summary of this revision. (Show Details)
Meinersbur added inline comments.Jun 13 2019, 5:58 PM
lib/Analysis/ScopInfo.cpp
204

[typo] alaias

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

[typo] NIFIXTRC

34

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 marked an inline comment as done.Jun 17 2019, 12:39 PM
sabuasal added inline comments.
test/ScopDetect/model-dowhile-update-rtc.ll
34

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 added inline comments.Jun 18 2019, 1:00 PM
test/ScopDetect/model-dowhile-update-rtc.ll
34

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 updated this revision to Diff 205868.Jun 20 2019, 11:38 AM
sabuasal marked an inline comment as done.
sabuasal edited the summary of this revision. (Show Details)
sabuasal added reviewers: huihuiz, zinob.
sabuasal added inline comments.
test/ScopDetect/model-dowhile-update-rtc.ll
34

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.

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

Meinersbur added inline comments.Wed, Jun 26, 1:23 PM
lib/Analysis/ScopInfo.cpp
202–203

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

3043–3045

[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
3

-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.