This is an archive of the discontinued LLVM Phabricator instance.

[Polly] Track assumptions and restrictions separately
ClosedPublic

Authored by jdoerfert on Feb 14 2016, 2:47 PM.

Details

Summary
In order to speed up compile time and to avoid random timeouts we now
separately track assumptions and restrictions. In this context assumptions
describe parameter valuations we need and restrictions describe parameter
valuations we do not allow. During AST generation we create a runtime check
for both, whereas the one for the restrictions is negated before a
conjunction is build.

Except the In-Bounds assumptions we currently only track restrictions.

Diff Detail

Repository
rL LLVM

Event Timeline

jdoerfert updated this revision to Diff 47934.Feb 14 2016, 2:47 PM
jdoerfert retitled this revision from to [Polly] Track assumptions and restrictions separately.
jdoerfert updated this object.
jdoerfert added reviewers: grosser, Meinersbur.
jdoerfert added a subscriber: Restricted Project.
grosser edited edge metadata.Feb 16 2016, 5:55 AM

Hi Johannes,

thanks for this patch. It looks very nice. I just have two semantical issues, I need feedback on and two smaller stylistic comments.

include/polly/ScopInfo.h
1313 ↗(On Diff #47934)

Comment is incomplete

lib/Analysis/ScopInfo.cpp
591 ↗(On Diff #47934)

Is there a specific reason we do not drop the complement and use the other assumption context?

594 ↗(On Diff #47934)

Plain boolean parameters make it difficult to understand the code without knowing the name of parameter 4. Maybe just introduce an enum that clearly describes the two cases? Maybe ASSUME_VALID, ASSUME_INVALID?

1312 ↗(On Diff #47934)

Nice.

1748 ↗(On Diff #47934)

Nice.

1913 ↗(On Diff #47934)

Did you check that the very same simplication logic also works for invalid context.

Assuming you have code

   for (i = 0; i < N; i++)
S:     ...

here we have N > 0 when we project the domain on the parameter set.

Now, assuming the code is invalid for N > 1000. If we gist_simplify the invalid set, we loose this constraint, no?

2406 ↗(On Diff #47934)

Nice to drop the complement.

2507 ↗(On Diff #47934)

Nice to drop the complement.

3093 ↗(On Diff #47934)

This should not be NULL, no?

3103 ↗(On Diff #47934)

This should not be NULL, no?

lib/CodeGen/IslAst.cpp
337 ↗(On Diff #47934)

Can we only add the condition of the invalid context if it is non-trivial? This will make the output nicer and also should reduce the number of test cases changed?

test/Isl/CodeGen/exprModDiv.ll
42 ↗(On Diff #47934)

This change seems to be independently beneficial. Maybe it could be committed ahead of time?

test/ScopInfo/assume_gep_bounds_2.ll
19 ↗(On Diff #47934)

Unnecessary whitespace changes?

test/ScopInfo/long-sequence-of-error-blocks-2.ll
10 ↗(On Diff #47934)

Nice!

jdoerfert updated this revision to Diff 48631.Feb 21 2016, 11:03 AM
jdoerfert marked 12 inline comments as done.
jdoerfert edited edge metadata.

Update according to the comments

lib/Analysis/ScopInfo.cpp
591 ↗(On Diff #47934)

This way all INBOUNDS assumption are "positve" thus assumptions. We could make it an restriction here easily but the current implementation of INBOUNDS further down will always need a complement and the current choice is probably more effiecent.

Tl;dr
No "real" reason. It just looks weird to have INBOUNDS assumptions as well as restrictions...

1913 ↗(On Diff #47934)

Mh,... I removed the secon call for now. I have to think about this.

grosser accepted this revision.Feb 25 2016, 5:20 AM
grosser edited edge metadata.

LGTM. Thank you Johannes!

This revision is now accepted and ready to land.Feb 25 2016, 5:20 AM
This revision was automatically updated to reflect the committed changes.