This is an archive of the discontinued LLVM Phabricator instance.

[Polly][Bug fix] Wrong dependences filtering during Fully Indexed expansion
ClosedPublic

Authored by niosega on Aug 16 2017, 6:52 AM.

Details

Summary

When trying to expand memory accesses, the current version of Polly uses statement Level dependences. The actual implementation is not working in case of multiple dependences per statement. For example in the following source code :

void mse(double A[Ni], double B[Nj], double C[Nj], double D[Nj]) {
  int i,j;
  for (j = 0; j < Ni; j++) {
    for (int i = 0; i<Nj; i++)
S:    B[i] = i;
    for (int i = 0; i<Nj; i++)
T:    D[i] = i;

U:  A[j] = B[j];
      C[j] = D[j];
  }
}

The statement U has two dependences with S and T. The current version of polly fails during expansion.

This patch aims to fix this bug. For that, we use Reference Level dependences to be able to filter dependences according to statement and memory ref. The principle of expansion remains the same as before.

We also noticed that we need to bail out if load come after store (at the same position) in same statement. So a check was added to isExpandable.

Diff Detail

Event Timeline

niosega created this revision.Aug 16 2017, 6:52 AM
simbuerg edited edge metadata.Aug 16 2017, 9:39 AM

Apart from the Load/Store union_map issue and the tests, just a few minor remarks.

lib/Transform/MaximalStaticExpansion.cpp
91

Is there a specific reason you pass MapDependences by-value and not by-reference as you did with expandRead?

207

The comment at this position does not really help me in understanding the following code.

suggestion: I would try to stick to the terminology of your current 'domain'.
Therefore, I would call them reads and writes, not loads and stores.

209

Maybe I miss something, but shouldn't you reset those for each Scop Statement? Later you are forming the union of all previous accesses with the current access.

234

I would word the remark differently, because this doesn't give the user enough information (IMO). Load after Store in the same statement isn't the problem, the problem is that we risk getting the dependences wrong because of that.

Ideally this should be fixed in polly, nothing the user can do about it.

271

// Get the dependences relevant for this MA

321

// Get the dependences relevant for this MA

test/MaximalStaticExpansion/load_after_store_same_statement.ll
2

Do not use -polli-canonicalize (or any other transformation, other than the one you want to test) in tests. Run the IR file through -polli-canonicalize and use the output as test. Otherwise you risk testing more than your pass.

test/MaximalStaticExpansion/working_expansion_multiple_dependences_per_statement.ll
1

See above.

test/MaximalStaticExpansion/working_expansion_multiple_instruction_per_statement.ll
1

See above

niosega updated this revision to Diff 111379.Aug 16 2017, 10:26 AM

Take Andreas remarks into account.

Meinersbur accepted this revision.Aug 17 2017, 6:35 AM

LGTM.

lib/Transform/MaximalStaticExpansion.cpp
91

[Suggestion] If the isl::union_map is not modfied in the function, either pass values (which just 'costs' a reference counter increase+decrease) of by a const reference. With just a reference I'd assume that the function is meant to modify/return the argument.

166

Why? How can this happen?

173

[Suggestion] MA->getLatestAccessRelation().get_tuple_id(isl::dim::out) is cheaper because it does not require projecting-out the domain dimensions.

[Suggestion] MA does not change during each iteration, you can hoist this before the foreach_map invocation.

175–176

[Suggestion] Do this on Map.get_space(), so the projections don't need to be computed.

This revision is now accepted and ready to land.Aug 17 2017, 6:35 AM
niosega updated this revision to Diff 111669.Aug 18 2017, 6:51 AM

Take Michael's suggestions into account.

niosega added inline comments.Aug 18 2017, 6:52 AM
lib/Transform/MaximalStaticExpansion.cpp
166

I don't know why but when I am asking AL_Reference or AL_Access dependencies, I also get Statement to Statement dependencies in the union_map. So I need to filter these out. Am I doing something wrong in the dependencies retrieval call ?

175–176

What is the best solution to get the Id between these two solutions ?

Map.get_space().domain().unwrap().range()
Map.get_space().curry().range().unwrap().domain()
Meinersbur added inline comments.Aug 18 2017, 7:34 AM
lib/Transform/MaximalStaticExpansion.cpp
166

I think this is due to the broken dependency info in case there are reduction candidates. Did you switch off reduction detection?

175–176
Map.get_space().domain().unwrap().get_tuple_id(isl::dim::out)

The second has one operation more, I don't see it having any advantages.

niosega added inline comments.Aug 18 2017, 7:46 AM
lib/Transform/MaximalStaticExpansion.cpp
166

With -polly-dependences-use-reductions=false in the opt command line, I still have the Statement to Statement dependencies.

Meinersbur accepted this revision.Aug 18 2017, 7:53 AM

Andreas, are you going to commit this?

lib/Transform/MaximalStaticExpansion.cpp
166

Can you check whether these are the same as the reference-level dependencies (i.e. without the tag)?

In any case, AL_Access and AL_Reference are very broken. We'll have to fix that one day.

This revision was automatically updated to reflect the committed changes.
niosega added inline comments.Aug 18 2017, 8:09 AM
lib/Transform/MaximalStaticExpansion.cpp
166

For the following source code :

void mse(double A[Ni], double B[Nj], double C[Nj], double D[Nj]) {
  int i,j;
  for (j = 0; j < Ni; j++) {
    for (int i = 0; i<Nj; i++)
      B[i] = i;
    for (int i = 0; i<Nj; i++)
      D[i] = i;
    A[j] = B[j];
    C[j] = D[j];
  }
}

I have these AL_Ref deps :

Stmt_for_body9[i0, i0] -> Stmt_for_end15[i0] : 0 <= i0 <= 9999; 
Stmt_for_body4[i0, i0] -> Stmt_for_end15[i0] : 0 <= i0 <= 9999;
 [Stmt_for_body4[i0, i0] -> MemRef_B[]] -> [Stmt_for_end15[i0] -> MemRef_B[]] : 0 <= i0 <= 9999; 
[Stmt_for_body9[i0, i0] -> MemRef_D[]] -> [Stmt_for_end15[i0] -> MemRef_D[]] : 0 <= i0 <= 9999

And these AL_Statement deps :

Stmt_for_body9[i0, i0] -> Stmt_for_end15[i0] : 0 <= i0 <= 9999; 
Stmt_for_body4[i0, i0] -> Stmt_for_end15[i0] : 0 <= i0 <= 9999

The dependencies seems to be correct and coherent.

Meinersbur added inline comments.Aug 19 2017, 12:30 PM
lib/Transform/MaximalStaticExpansion.cpp
166

Thanks for confirming.