This is an archive of the discontinued LLVM Phabricator instance.

[Polly] Earlier creation of ScopStmt objects
ClosedPublic

Authored by Meinersbur on Oct 1 2015, 5:33 AM.

Details

Summary

This moves the construction of ScopStmt to the beginning of the ScopInfo pass. The late creation was a result of the earlier separation of ScopInfo and TempScopInfo. This will avoid introducing more ScopStmt-like maps in future commits. The AccFuncMap will also be removed in some future commit. DomainMap might also be included into ScopStmt.

The order in which ScopStmt are created changes and initially creates empty statements that are removed in a simplification.

Diff Detail

Repository
rL LLVM

Event Timeline

Meinersbur updated this revision to Diff 36230.Oct 1 2015, 5:33 AM
Meinersbur retitled this revision from to [Polly] Earlier creation of ScopStmt objects.
Meinersbur updated this object.
Meinersbur added reviewers: grosser, jdoerfert.
Meinersbur added a project: Restricted Project.
Meinersbur added subscribers: llvm-commits, pollydev.
grosser accepted this revision.Oct 1 2015, 2:50 PM
grosser edited edge metadata.

lgtm

This revision is now accepted and ready to land.Oct 1 2015, 2:50 PM
jdoerfert added inline comments.Oct 1 2015, 5:29 PM
lib/Analysis/ScopInfo.cpp
2850 ↗(On Diff #36230)

We do not create empyt non-affine regions any more. That should make this special case obsolet.

Meinersbur updated this revision to Diff 36351.Oct 2 2015, 5:48 AM
Meinersbur updated this object.
Meinersbur edited edge metadata.

Rebase to r249099

Some changes necessary because more reasons to no create a ScopStmt were added.

Meinersbur added inline comments.Oct 2 2015, 5:50 AM
lib/Analysis/ScopInfo.cpp
2898 ↗(On Diff #36351)

A test case fails without it. We might instead bail out early as invalid when we encounter a Scop without statements.

This revision was automatically updated to reflect the committed changes.
jdoerfert edited edge metadata.Oct 2 2015, 7:23 AM

Why don't we create statements (and accesses) during the domain generation [second part, propagation]?

Pro:

  • We iterate over the SCoP anyway.
  • We already know which blocks/regions we will keep (at least until hoisting) and which we ignore.
  • The block/region can be checked for accesses at that point in time as good as at any prior one.
  • The Domain for the new statement was just computed and can be used right away, thus:
    • No delayed init() calls needed.
    • No broken/useless ScopStmts flying around.
    • No need to remove anything we can easily avoid building.

Con:

  • Domain generation would perform another task (though, so far schedule generation did this and it seemed fine).
include/polly/ScopInfo.h
1214 ↗(On Diff #36351)

What is a no-op statement here? And why should we build ignored statements in the first place? Aren't they deleted anyway? Do you have performance numbers for this patch by any chance?

lib/Analysis/ScopInfo.cpp
1154 ↗(On Diff #36351)

braces are not needed.

2312 ↗(On Diff #36351)

Calling simplifySCoP 3 times seems a lot. Alone in this method we (directly or indirectly) iterate 3 more times over all statements now.

2380 ↗(On Diff #36351)

Please try to keep/write early exit code instead of indention.

2898 ↗(On Diff #36351)

Which test? Unit or lnt? Shouldn't we fix this somehow? Generating an empyt domain for the case there is no statement seems rather odd.

Why don't we create statements (and accesses) during the domain generation [second part, propagation]?

For DeLICM, while adding MemoryAccesses, there will be a multiple per-Stmt data for which I'd introduce new dictionaries (and lookups) from BasicBlocks to that data. We save this by just using the already existing StmtMap. Problem was, those was created only later.

Con:

  • Domain generation would perform another task (though, so far schedule generation did this and it seemed fine).

This is an important point (but not the reason for this patch). Doing multiple unrelated things in one function makes code hard to understand and modify (e.g. changing the order of the two operations).

include/polly/ScopInfo.h
1214 ↗(On Diff #36351)

What is a no-op statement here?

One without side-effect. Currently it checks whether there is no MemoryAccess at all but we could also remove those which have no write access.

And why should we build ignored statements in the first place?

Because we don't know yet whether they are ignored. E.g. because of load hoisting.

Aren't they deleted anyway?

At the last simplifyScop, yes; but we don't need to do the calculations in-between when we already know they are going to be removed.

Do you have performance numbers for this patch by any chance?

No. I don't expect a noticeable impact on performance.

lib/Analysis/ScopInfo.cpp
2312 ↗(On Diff #36351)

I removed one of them in the actual commit. Iterating over all statements is cheap.

2380 ↗(On Diff #36351)

OK

2898 ↗(On Diff #36351)

I think it was whole-scop-non-affine-subregion-in-loop.ll

This is by design. The affine region is removed because there are no accesses in it. That leaves no statements in the scop. How would you handle this?