This is an archive of the discontinued LLVM Phabricator instance.

[Polly] Exploit graph properties during domain generation
ClosedPublic

Authored by jdoerfert on Mar 24 2016, 9:04 AM.

Details

Summary
    Exploit graph properties during domain generation
····
      As a CFG is often structured we can simplify the steps performed
      during domain generation. When we push domain information we can
      utilize the information from a block A to build the domain of a
      block B, if A dominates B. When we pull domain information we can
      use information from a block A to build the domain of a block B
      if B post-dominates A. This patch implements both ideas and thereby
      simplifies domains that were not simplified by isl. For the FINAL
      basic block in
        test/ScopInfo/complex-successor-structure-3.ll .
      we used to build a universe set with 81 basic sets. Now it actually is
      represented as universe set.
····
      While the initial idea to utilize the graph structure depended on the
      dominator and post-dominator tree we can use the available region
      information as a coarse grained replacement. To this end we push the
      region entry domain to the region exit and pull it from the region
      entry for the region exit.

Diff Detail

Repository
rL LLVM

Event Timeline

jdoerfert updated this revision to Diff 51562.Mar 24 2016, 9:04 AM
jdoerfert retitled this revision from to Use RegionInfo as shortcut in part of the domain generation [WIP].
jdoerfert updated this object.
jdoerfert added reviewers: grosser, Meinersbur, chrisj.
jdoerfert added a subscriber: Restricted Project.
grosser edited edge metadata.Mar 27 2016, 7:18 AM

Hi Johannes,

the idea of using Regioninfo to 'jump' over the domain propagation is great. I earlier tried to hint to using (post)-dom information, but using region information makes indeed more sense especially as post-dominator information is not (yet) useful in this context.

I just checked out this patch to try it out, but unfortunately I get timeouts for some test cases. I used the command 'arc patch D18450' to checkout the patch, which applied it on top of https://llvm.org/svn/llvm-project/polly/trunk@264286. I then rebased this patch to trunk (264514) where all test pass without timeout. Please let me know if I should have tried this patch with a different version of Polly.

This patch is not coming with any test cases and also does not explicitly describe the benefits it is intended to bring. My understanding is that this patch should both result in simpler domain constraints for certain test cases and should even allow us to construct domains for codes that could not been modeled previously, due to overly complex constraints being constructed. Could you point out these benefits in the commit message and add a test case that shows this benefit? I would expect test/ScopInfo/complex-successor-structure.ll to benefit. However, when I tried it no scop is constructed. Do you understand why?

lib/Analysis/ScopInfo.cpp
2229 ↗(On Diff #51562)

A higher level comment (possibly even with some example) would be very helpful to get a quick understanding of this code. In case this is the missing comment you are talking about in the "WIP-message".

I think I understood the code without this comment, but I would still like to review this patch with your comment in place to ensure what I understood is indeed what you aimed for.

2238 ↗(On Diff #51562)

The reason why we have two branches would e.g. be interesting to point out in the comment.

2241 ↗(On Diff #51562)

The overall size of this function grows after this patch to now over three screen pages. I think in general we should really try to split this function in smaller entities. To make sure that this patch is not adding even more to this growth, it might be worth to move the code above in its own function.

2331 ↗(On Diff #51562)

This function has now grown to over three screen pages and is becoming increasingly difficult to read. Would there be an easy way to split this function into smaller pieces, possibly even before this commit is going in?

jdoerfert updated this revision to Diff 51751.Mar 27 2016, 2:32 PM
jdoerfert edited edge metadata.

Used shortcut in both domain generation parts + refactoring

jdoerfert added inline comments.Mar 27 2016, 2:36 PM
test/ScopInfo/non_affine_region_1.ll
23 ↗(On Diff #51751)

This was a bug in the original test. The domain of bb8 should have never been a singleton (that's what I think at this point at least).

jdoerfert retitled this revision from Use RegionInfo as shortcut in part of the domain generation [WIP] to [Polly] Exploit graph properties during domain generation.Mar 29 2016, 8:38 AM
jdoerfert updated this object.
grosser accepted this revision.Mar 29 2016, 10:51 AM
grosser edited edge metadata.

Hi Johannes,

thanks a lot for splitting up this function and and commenting the new features. This is now indeed a lot clearer to me. I added a couple of smaller comments, but most are rather minor or typos.

From my point you can commit these changes. When doing so, it would be great if you could split this into a couple of independent commits such that functional and non-functional changes are clear even to an outsider. These seem to be independent changes to me:

  1. Pull out *adjustDomainDimensions [NFC]
  2. Add addDomainDimId at some places (fixes michael's bug?)
  3. Propagating constrains
  4. Something that changes domains (unclear were)

Best,
Tobias

include/polly/ScopInfo.h
1429 ↗(On Diff #51751)

Is this dominance/post-dominance property true if A is part of a loop, which does not contain B? Something like:

pre:
  br label %A

A:
  br %cnd, %A, %B

B:

The domains of A and B may have different dimensionality and can consequently not be be compared, right?

What about unreachables/infinite loops? Do they need to be considered? Assuming we commit the "fixed" the post-dominator patch, the exit of a region may be reachable by less parameters than the input?

Adding a short note what happens with these exceptions would be nice.

lib/Analysis/ScopInfo.cpp
2195 ↗(On Diff #51751)

Pulling this out into a separate function is a very good idea. It makes the code a lot more readable and removes code duplication. Could this + ​getFirstNonBoxedLoopFor could be a separate [NFC]? In case it can, I would suggest to pull this out and commit it ahead of time. (no further review required).

2217 ↗(On Diff #51751)

Maybe also add an assert(NewL->getParentLoop() == OldL->getParentLoop()

2225 ↗(On Diff #51751)

You seem to add here 'addDomainDimId', which was not here before. Do I remember correctly that this fixes Michael's bug? In case it does, I suggest to commit just this line as independent functional change together with Michael's test case and include a commit message that explains _why_ this became necessary.

2234 ↗(On Diff #51751)

Overall, this function is a lot more readable then the old version. Very nice!

2256 ↗(On Diff #51751)

different

2319 ↗(On Diff #51751)

through

2349 ↗(On Diff #51751)

propagate (without the 's')

2412 ↗(On Diff #51751)

Point at end of sentence.

2429 ↗(On Diff #51751)

All predecessors

2433 ↗(On Diff #51751)

Point.

test/ScopInfo/complex-successor-structure-2.ll
10 ↗(On Diff #51751)

Nice!

test/ScopInfo/complex-successor-structure-3.ll
15 ↗(On Diff #51751)

Nice.

test/ScopInfo/complex-successor-structure.ll
4 ↗(On Diff #51751)

has is -> drop one of them.

This revision is now accepted and ready to land.Mar 29 2016, 10:51 AM
jdoerfert added inline comments.Mar 29 2016, 11:40 AM
include/polly/ScopInfo.h
1429 ↗(On Diff #51751)

Is this dominance/post-dominance property true if A is part of a loop, which does not contain B? Something like:
The domains of A and B may have different dimensionality and can consequently not be be compared, right?

Short answer is Yes. Long answer:
Even now (with regions) we allow this and use the "adjustDimensionality" function to fix the dimensions of %pre to match %B in your example. Between %A and %B we need to consider %cnd anyway.

What about unreachables/infinite loops? Do they need to be considered? Assuming we commit the "fixed" the post-dominator patch, the exit of a region may be reachable by less parameters than the input?

Yes and no. While they are reachable by less inputs we do not model them that way. At least not until we allow "return" statements. If we encounter "unreachable" we will (and do) assume it to be not executed but that does not affect the domains of later notes. This is a problem (e.g. bug PR26683) but it also helps to keep domains concise. In any case, we can handle that differently here if we decide to do so.

Adding a short note what happens with these exceptions would be nice.

Since nothing changed I can write what happens now, thus before and after the patch. Though, that is again something that is not related for me...

lib/Analysis/ScopInfo.cpp
2195 ↗(On Diff #51751)

This sounds like unnecessary work but I will check if it makes sense.

2217 ↗(On Diff #51751)

Makes sense.

2225 ↗(On Diff #51751)
  1. It does not fix any bugs that I am aware of. If there was a bug caused by this it would crash at compile time.
  2. I am not sure what Michaels bug was, this should not be it anyway.
  3. This was and is necessary because the domains need to match when we combine them. That has not changed with this commit.
grosser added inline comments.Mar 29 2016, 1:05 PM
include/polly/ScopInfo.h
1429 ↗(On Diff #51751)

My understanding was that this comment was describing the shortcut of propagating constraints across regions and specifically justifying
why it is safe to do so. As this optimization has not been present before the patch, I wonder how this can already happen today.

lib/Analysis/ScopInfo.cpp
2195 ↗(On Diff #51751)

It is currently still unclear to me which code changes introduce the precise
test cases changes. Splitting off functionality in parts that change output and changes that do not impact behavior is useful both for bisecting, but especially to document which parts are non-functional-changes.

It also speed ups patch reviews immensely. In fact, as already said earlier, I very much invite you to commit clearly beneficial refactoring that are NFC directly only relying on post-commit review, such that the actual functional change that needs to be reviewed is smaller.

2225 ↗(On Diff #51751)

Thanks for clarifying.

Regarding 3): I understand that the calls to addDomainDimId have been already in buildDomainsWithBranchConstraints. However, in propagateDomainConstraints you replace very similar code with this function. The original code in propagateDomainConstraints did not have these calls, so they seem to be added. Or did I miss something here? In case they are indeed new, it would be good to explicitly state in the commit that this change change does not change functionality.

jdoerfert added inline comments.Mar 29 2016, 1:44 PM
include/polly/ScopInfo.h
1429 ↗(On Diff #51751)

Your right but I think we talk about two different things here:

What changed is __how__ we generate the domain, not __what__ domain is generated.

You asked about domains after infinite loops or unreachables, I tried to explain that the outcome is the same as it is now, though, your'r right the way we get there is now different/smarter.

lib/Analysis/ScopInfo.cpp
2195 ↗(On Diff #51751)

I like the idea but it's not that I refactor the code, then implement something and commit both together. I refactor while implementing and it is not always clear how to separate them. Furthermore I could not commit the refactoring earlier as I was waiting on another patch to be commited.

2225 ↗(On Diff #51751)

They might have been added but I do not have/know of any test were they were necessary. In buildDomainsWithBranchConstrians they are [to my knowledge], thus I had to include them here. From my point of view I did not add them anywere (in order to change something) but I merely kept them were they have been. Additionally, I am not sure that mentioning this call in the commit message is a good thing anyway. It is a low level detail not something I would write in a commit message.

This revision was automatically updated to reflect the committed changes.