Page MenuHomePhabricator

[DependenceInfo] Remove access to WAW and WAR: Expose both as False [NFC]
AbandonedPublic

Authored by bollu on Mar 22 2017, 9:18 AM.

Details

Summary

This patch sets the stage for rework of the WAW and WAR dependences. The
migration is to store both the WAW and the WAR together in a single map
called as "False" (the false dependences). The motivation for this
change is explained below.

Motivation #1: semantics of isl_union_flow_get_{must|may}_dependence:

Code snippet for reference:

DependenceInfo.cpp:374-377

Flow = buildFlow(MustWrite, MustWrite, Read, Schedule);

WAW = isl_union_flow_get_must_dependence(Flow);

WAR = isl_union_flow_get_may_dependence(Flow);

isl_union_flow_get_may_dependence will return:

  1. all dependences that start from a May source
  2. dependences that start form a Must source but connect to a May source before reaching the Sink. In particular, something like: Sink <- ... <- May source <- ... <- Must source is counted as a *May* dependence.
  1. isl_union_flow_get_must_dependence only returns dependences are of the form: Sink <- .. <No may source> .. <- Must source

Hence, in our case, we get too many WAR dependences, since something of
the form:

MustWrite <- Read <- MustWrite

is counted as WAR (may dependence).
Similary, we will have too little WAW (must) dependences.
Both our WAW and WAR computation will be incorrect due to the incorrect
call to buildFlow. This needs to be fixed later on.

However, to generate WAW and WAR dependences correctly, we will need 2
calls to buildFlow() - one for WAW and one for WAR, which is very expensive.
If we combine WAR and WAW into one map (False), we need only one call to
buildFlow() to build False.

There is only one place in Polly where we care about the
difference between a WAR and WAW:

lib/Transform/ScheduleOptimizer.cpp:containsOnlyMatMulDep()

This patch changes the function to not care about WAW dependence
exclusively. Now, there is effectively *no* place in polly where we ask
for WAW or WAR sepearately. So, combining them into a single map has no
functional difference in Polly.

We can migrate from storing WAW and WAR separately to storing them together as
False.

Motivation #2: take May writes into account, build TC_RED with alternate

strategy:

Currently, we are only considering MustWrite when building WAW and WAR.
We wish to also consider May-writes when building WAW and WAR.

  1. This helps with correctness of WAW and WAR we track.
  2. If we treat Reduction-like memory accesses as May-writes, we are able to compute TC_RED without actually incurring a call to the expensive isl_union_map_transitive_closure.

Event Timeline

bollu created this revision.Mar 22 2017, 9:18 AM
grosser accepted this revision.Mar 23 2017, 3:03 AM

This looks good to me. As this is a rather large change, I would like to get an explicit OK from Michael and Roman.

include/polly/DependenceInfo.h
89

Why do you put this between TYPE_RED and TYPE_TC_RED. I would expect this to come before TYPE_RED.

This revision is now accepted and ready to land.Mar 23 2017, 3:03 AM
bollu updated this revision to Diff 92778.Mar 23 2017, 3:14 AM

Changed ordering of FALSE and RED in dependences type enum.

gareevroman edited edge metadata.Mar 24 2017, 3:43 AM

Hi Siddharth,

thanks for the patch!

However, to generate WAW and WAR dependences correctly, we will need 2
calls to buildFlow() - one for WAW and one for WAR, which is very expensive.

It would be great, if you could attach the results of the LLVM test-suite compile-time evaluation to show it.

There is only one place in Polly where we care about the
difference between a WAR and WAW:

lib/Transform/ScheduleOptimizer.cpp:containsOnlyMatMulDep()

This patch changes the function to not care about WAW dependence
exclusively.

Please see inline comments.

Also, please, prefix titles with "[Polly]".

include/polly/DependenceInfo.h
179

I'm not sure whether it's good to use variable names that are almost similar to reserved keywords. Could you rename it to, for example, FalseDep?

lib/CodeGen/IslAst.cpp
186

Why do you store the union of all dependences in Dep? We planned to check only RAW dependences here. Furthermore, we intended to check that there are no WAR dependences.

bollu abandoned this revision.Apr 3 2017, 11:38 AM