This is an archive of the discontinued LLVM Phabricator instance.

[Polly] [RFC] Fine-grain dependency analysis
ClosedPublic

Authored by etherzhhb on Feb 18 2016, 7:53 AM.

Details

Summary

Build dependence information based on tagged access [1], e.g. for access:

MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
    [N] -> { Stmt_for_body[i0] -> MemRef_a[6 + i0] };

we build tag it and get:

  • -> {[Stmt_for_body[i0] -> MemRef_a[]] -> MemRef_a[6 + i0] };

See the attach case for example.

TODO:
1. Introduce an option to disable/enable this feature
2. Unexpected Failures: 157

  1. More testcases

4. Support tagging the access with the memory access and arrayid

[1] 5.3.4 Tagged Access Relations at https://lirias.kuleuven.be/bitstream/123456789/523109/3/polycomp-tutorial-v0.02.pdf

Diff Detail

Repository
rL LLVM

Event Timeline

etherzhhb updated this revision to Diff 48315.Feb 18 2016, 7:53 AM
etherzhhb retitled this revision from to [Polly] [RFC] Access level dependency analysis.
etherzhhb updated this object.
etherzhhb added a reviewer: grosser.
etherzhhb set the repository for this revision to rL LLVM.
etherzhhb added a subscriber: Restricted Project.
etherzhhb added inline comments.Feb 18 2016, 7:58 AM
lib/Analysis/DependenceInfo.cpp
79 ↗(On Diff #48315)

Drop the output dimensions, otherwise we cannot calculate the dependency.

81–82 ↗(On Diff #48315)

isl magic :)

287 ↗(On Diff #48315)

ah ... this line is incorrect...

test/DependenceInfo/access_level_dep_simple_0.ll
4 ↗(On Diff #48315)

Looks like we get both the access level dependency ([Stmt_for_body[i0] -> MemRef_a[]] -> [Stmt_for_body[4 + i0] -> MemRef_a[]] : 0 <= i0 <= -11 + N) and statement level dependence (Stmt_for_body[i0] -> Stmt_for_body[4 + i0] : 0 <= i0 <= -11 + N)

Build dependence information based on tagged access [1], e.g. for access:

MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
    [N] -> { Stmt_for_body[i0] -> MemRef_b[6 + i0] };

we build tag it and get:

  • -> {[Stmt_for_body[i0] -> MemRef_a[]] -> MemRef_b[6 + i0] };

Why does it say MemRef_a and then MemRef_b ?

etherzhhb updated this object.
etherzhhb removed a subscriber: llvm-commits.
etherzhhb added a subscriber: llvm-commits.

Build dependence information based on tagged access [1], e.g. for access:

MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
    [N] -> { Stmt_for_body[i0] -> MemRef_b[6 + i0] };

we build tag it and get:

  • -> {[Stmt_for_body[i0] -> MemRef_a[]] -> MemRef_b[6 + i0] };

Why does it say MemRef_a and then MemRef_b ?

Updated

etherzhhb added inline comments.
test/DependenceInfo/access_level_dep_simple_0.ll
1 ↗(On Diff #48315)

forgot the '-polly-dependences-analysis-type=value-based'

etherzhhb added inline comments.Feb 18 2016, 8:15 AM
lib/Analysis/DependenceInfo.cpp
287 ↗(On Diff #48315)

ah ... this line is incorrect...

grosser edited edge metadata.Feb 18 2016, 8:16 AM

Very nice start. Here a first comment:

lib/Analysis/DependenceInfo.cpp
112 ↗(On Diff #48315)

You probably want to use MA->getID() to obtain a unique tag for each MemoryAccess in a statement. Even though these isl_ids are unique (due to the pointer they reference), they all are called "__polly_array_ref". We should probably give them a unique name too.

etherzhhb updated this revision to Diff 48329.Feb 18 2016, 8:35 AM
etherzhhb updated this object.
etherzhhb edited edge metadata.
etherzhhb retitled this revision from [Polly] [RFC] Access level dependency analysis to [Polly] [RFC] Reference level dependency analysis.
etherzhhb retitled this revision from [Polly] [RFC] Reference level dependency analysis to [Polly] [RFC] Memory reference level dependency analysis.
etherzhhb updated this revision to Diff 48331.Feb 18 2016, 8:44 AM
etherzhhb updated this object.
etherzhhb added inline comments.Feb 18 2016, 8:46 AM
lib/Analysis/DependenceInfo.cpp
126 ↗(On Diff #48331)

we can tag it with MA->getId() as well

305–309 ↗(On Diff #48331)

Can we improve this if-else?

etherzhhb updated this object.Feb 18 2016, 8:47 AM
etherzhhb marked an inline comment as done.Feb 18 2016, 8:50 AM
etherzhhb added inline comments.
lib/Analysis/DependenceInfo.cpp
125 ↗(On Diff #48331)

why it call polly_array_ref instead of polly_memory_access?

Comments inline.

lib/Analysis/DependenceInfo.cpp
126 ↗(On Diff #48331)

MA->getId() will allow you to distinguish two accesses in the same statement to the same array, but by a different instruction.

polly_array_ref is just a name. If polly_memory_access sounds better, we can easily change it.

305–309 ↗(On Diff #48331)

Yes, see https://llvm.org/bugs/show_bug.cgi?id=26320 for a first description why the second code path is there. Johannes, who wrote this code, might be able to tell you better what would be needed to move reduction dependences to schedule trees.

etherzhhb marked an inline comment as done.Feb 18 2016, 9:09 AM
etherzhhb added inline comments.
lib/Analysis/DependenceInfo.cpp
126 ↗(On Diff #48331)

MA->getId() will allow you to distinguish two accesses in the same statement to the same array, but by a different instruction.

yes, we can actually have 3 analyses at 3 different levels.

Comments inline.

lib/Analysis/DependenceInfo.cpp
305–309 ↗(On Diff #48331)

@ether. I just realized you are using the second code path for reference level dependence analysis. I would prefer to use the first code path. Dependence analysis on schedule trees can be significantly faster (we observed this) as the analysis can exploit the tree structure. This is why we moved to schedule trees in the first place.

etherzhhb marked an inline comment as done.Feb 19 2016, 7:20 AM
etherzhhb added inline comments.
lib/Analysis/DependenceInfo.cpp
305–309 ↗(On Diff #48331)

Ok, I will try to tag the schedule trees as well and remove the &&

etherzhhb updated this revision to Diff 48510.Feb 19 2016, 10:06 AM
etherzhhb retitled this revision from [Polly] [RFC] Memory reference level dependency analysis to [Polly] [RFC] Fine-grain dependency analysis.
etherzhhb marked an inline comment as done.
etherzhhb updated this object.Feb 19 2016, 10:07 AM

Sven mentioned `isl_union_flow_get_full_may_dependence`, which might be exactly what you need. From ISL documentation:

The relation returned by C<isl_union_flow_get_full_may_dependence>
relates domain elements of must or may sources to pairs of
domain elements of the sink and accessed data elements.
This relation includes the previous relation as a subset.

Sven mentioned `isl_union_flow_get_full_may_dependence`, which might be exactly what you need. From ISL documentation:

The relation returned by C<isl_union_flow_get_full_may_dependence>
relates domain elements of must or may sources to pairs of
domain elements of the sink and accessed data elements.
This relation includes the previous relation as a subset.

Yes and No, I had tried that out.

C<isl_union_flow_get_full_may_dependence> return memory reference level dependence info, it cannot return the access level dependence info.

Also, Instead of fitting everything into the dependence analysis pass, which will make the dependence analysis too complicated. I may introduce my own analysis pass by customizing the dependency analysis pass.

Hi ether,

I do not think that there is a need to factor this into another pass. In fact, I think for the state we are currently at, the 'flag' solution works well as it shows what can be done and allows us to test the functionality. If we later need this functionality (simultaneously) in different passes, we can always refactor to make it easier accessible. From my point of view, this patch is good to go. However, I would suggest to add a reference-type test case.

Also, if you are interested to eliminate - based on this patch - the reduction dependence detection. This would be of great value.

Best,
Tobias

etherzhhb updated this revision to Diff 49198.Feb 26 2016, 8:52 AM

Update testcase.

grosser accepted this revision.Feb 26 2016, 8:55 AM
grosser edited edge metadata.

LGTM

This revision is now accepted and ready to land.Feb 26 2016, 8:55 AM
This revision was automatically updated to reflect the committed changes.