This is an archive of the discontinued LLVM Phabricator instance.

[Polly][ScopInfo]Fix wrong map in updating AccessRelation of multi-element access
Needs ReviewPublic

Authored by bin.narwal on Nov 17 2019, 3:46 AM.

Details

Summary

Hi,
This patch fixes bug at https://bugs.llvm.org/show_bug.cgi?id=35108. Root cause is:
when building memory access, the subscripts for MultiDim Access are built in units of
element type in functions buildAccessMultiDim*, while for SingleDim Access are built in
units of bytes in function buildAccessSingleDim. Later in function updateDimensionality,
we need to update AccessRelation for multi-element access, ideally, the difference in
subscripts aforementioned needs to be considered. However, it's not and we always
handle it as in units of bytes.

This patch fixes the issue as well as adds a test case. Any comment?

Thanks,

Diff Detail

Event Timeline

bin.narwal created this revision.Nov 17 2019, 3:46 AM

Adding @grosser as reviewer who wrote the code in question and already looked into the issue.

I don't think DimsArray > 1 is a reliable indicator whether buildAccessMultiDim* or any of the other access builder has been used. IMHO the issue is that sometimes we have an interpretation of "array of bytes", at other times it is "array of elements". "array of elements" isn't always possibly, for instance if any memcpy occurs on the array. I though of switching to "array of bytes"-always but this yields non-injective access functions that parts of Polly bails out of (e.g. DeLICM is not prepared for this).

When I looked into the issue, I identified the following code being part of the problem:

if (DimsAccess == 1) {
  isl::val V = isl::val(Ctx, ArrayElemSize);
  AccessRelation = AccessRelation.floordiv_val(V);
}

which assumes single dimensions only and is just wrong with more dimensions. It seems your patch just does the the same thing with more dimensions.

bin.narwal added a comment.EditedNov 24 2019, 5:10 AM

Adding @grosser as reviewer who wrote the code in question and already looked into the issue.

I don't think DimsArray > 1 is a reliable indicator whether buildAccessMultiDim* or any of the other access builder has been used. IMHO the issue is that sometimes we have an interpretation of "array of bytes", at other times it is "array of elements". "array of elements" isn't always possibly, for instance if any memcpy occurs on the array. I though of switching to "array of bytes"-always but this yields non-injective access functions that parts of Polly bails out of (e.g. DeLICM is not prepared for this).

When I looked into the issue, I identified the following code being part of the problem:

if (DimsAccess == 1) {
  isl::val V = isl::val(Ctx, ArrayElemSize);
  AccessRelation = AccessRelation.floordiv_val(V);
}

which assumes single dimensions only and is just wrong with more dimensions. It seems your patch just does the the same thing with more dimensions.

Hmm, subscripts (thus AccessRelations) for multi-dimensions are built in units of elment type, so it's right to handle only single dimension here?

I guess this assumption is from reading the code building memory access for single/multi dimension cases, but yes, I agree it's not as good as expected.

Anyway, leaving this to the code author.

Thanks,
bin

When I looked into the issue, I identified the following code being part of the problem:

if (DimsAccess == 1) {
  isl::val V = isl::val(Ctx, ArrayElemSize);
  AccessRelation = AccessRelation.floordiv_val(V);
}

which assumes single dimensions only and is just wrong with more dimensions. It seems your patch just does the the same thing with more dimensions.

Hmm, subscripts (thus AccessRelations) for multi-dimensions are built in units of elment type, so it's right to handle only single dimension here?

I guess this assumption is from reading the code building memory access for single/multi dimension cases, but yes, I agree it's not as good as expected.

Part of why I think the code above is wrong is because whatever function created AccessRelation also defines/assumes ArrayElemSize. The code above re-defines the access relation in terms of bytes, but does not adjust ArrayElemSize (that is, SAI->ElementType). Effectively, making the array larger than it is.

The only reason this does not break big time is that the size of the outermost dimension (with DimsAccess == 1 there is just one dimension) is rarely used. It is not needed for the address computation in CodeGen.