Page MenuHomePhabricator

[Polly] Store the size of the outermost dimension in case of newly created arrays that require memory allocation.
ClosedPublic

Authored by gareevroman on Aug 29 2016, 6:59 AM.

Diff Detail

Repository
rL LLVM

Event Timeline

gareevroman retitled this revision from to [Polly] Store the size of the outermost dimension in case of newly created arrays that require memory allocation..
gareevroman updated this object.
gareevroman added a subscriber: pollydev.
Meinersbur edited edge metadata.Aug 29 2016, 8:29 AM

Thank you for the patch.

lib/Analysis/ScopInfo.cpp
221–222 ↗(On Diff #69567)

This is probably not relevant at the moment because updateSizes is only called on previosly existing array:

This unconditionally ignores the first dimension size. I think this is only because NewSizes[0 + ExtraDimsNew] is NULL. not an intrinisic property of sizes.

1031 ↗(On Diff #69567)

Wouldn't it be better to already prepend nullptr in Access->Sizes when it is created? We'd have consistently all dimension size arrays having as many elements as array indices, instead some with nullptr as first element, others with one element less.

lib/CodeGen/IslNodeBuilder.cpp
1160 ↗(On Diff #69567)

getNumberOfDimensions() return an unsigned int. 0u - 1 is undefined behaviour.

test/Isl/CodeGen/MemAccess/create_arrays.ll
15 ↗(On Diff #69567)

Should this be double E[270336][200000]?
You may need to update the print function to only print '*' if sizes[0] is nullptr.

30 ↗(On Diff #69567)

Well Done!

test/Isl/CodeGen/MemAccess/create_arrays___%bb9---%bb26.jscop
5 ↗(On Diff #69567)

Nice

test/Isl/CodeGen/MemAccess/create_arrays___%bb9---%bb26.jscop.transformed
36 ↗(On Diff #69567)

Nice

gareevroman edited edge metadata.
gareevroman marked 2 inline comments as done.

A new version updated according to the comments.

Hi Michael,

thank you for the comments!

lib/Analysis/ScopInfo.cpp
221–222 ↗(On Diff #69567)

This is probably not relevant at the moment because updateSizes is only called on previosly existing array:

I think that it's relevant even in case of previosly existing array. Let's consider, for example, llvm/tools/polly/test/ScopInfo/user_provided_assumptions.ll. In this case, if try to build the following memory access,

            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
                [N, M] -> { Stmt_for_body_22[i0, i1] -> MemRef_C[i0, i1] };

we should be able to update dimension sizes of MemRef_C and change them from [*] to [*], [100].

lib/CodeGen/IslNodeBuilder.cpp
1160 ↗(On Diff #69567)

I've added an additional condition to check it.

Meinersbur accepted this revision.Aug 30 2016, 6:34 AM
Meinersbur edited edge metadata.

LGTM

lib/Analysis/ScopInfo.cpp
838 ↗(On Diff #69664)

this->Sizes.insert is usually used to get the member instead of the parameter of the same name.

Can you make the caller prepend nullptr entry? I think it makes sense for consistency and in case we create MemoryAccesses with this constructer where we know what the outermost size is.

lib/CodeGen/IslNodeBuilder.cpp
1157–1159 ↗(On Diff #69664)

Good idea

This revision is now accepted and ready to land.Aug 30 2016, 6:34 AM
gareevroman edited edge metadata.

A new version updated according to the comments.

Hi Michael,

thank you for the review!

However, I'm not sure whether we should ignore the first dimension size of all kinds of memory accesses. Should we do it only in case of MK_Arrays that are not newly created? I've added this condition in the new version of patch and also updated the comment that corresponds to ScopArrayInfo::updateSizes.

lib/Analysis/ScopInfo.cpp
838 ↗(On Diff #69664)

Maybe the callers of addArrayAccess should prepend nullptr entry. What do you think about it?

However, I'm not sure whether we should ignore the first dimension size of all kinds of memory accesses. Should we do it only in case of MK_Arrays that are not newly created? I've added this condition in the new version of patch and also updated the comment that corresponds to ScopArrayInfo::updateSizes.

I understand that nullptr as dimension size means "I don't know the dimension's size"/"I it can be any value". updateSizes checks if the new array size is in conflict with the old one and returns false if it is. Seeing nullptr in this interpretation means "I don't know the size yet, but if the caller tells me it is this size, I will update it to this size."

That is, instead of ignoring the first size dimensions on some condition, we should check whether it is nullptr.
If it is nullptr -> No conflict, continue and update size
Not nullptr, same value as new size -> No conflict, continue
Not nullptr, different value than old -> Discordant sizes, bail-out (return false)

This is hypothetical since, AFAIK, updateSizes is only called during polly-scops pass when there are no newly created arrays (yet).

For non-MK_Arrays, the sizes are not relevant. It could have valid values of:

  • {} (empty sizes array)
  • {nullptr} (unknown size)
  • {1} (exactly one element; scalar)

Probably the last is "most accurate", but I don't really have a preference here. Use whatever works best.
Actually, this gives me the idea that would could handle such scalar ScopArrayInfos as a special case of newly created arrays, since for both we are going to create allocas for which we need the size.

What do you think?

Michael

lib/Analysis/ScopInfo.cpp
838 ↗(On Diff #69664)

Yes, that's what I meant.

A new version updated according to the comments.

gareevroman added a comment.EditedSep 12 2016, 6:49 AM

Hi Michael,

sorry for the late reply.

I understand that nullptr as dimension size means "I don't know the dimension's size"/"I it can be any value". updateSizes checks if the new array size is in conflict with the old one and returns false if it is. Seeing nullptr in this interpretation means "I don't know the size yet, but if the caller tells me it is this size, I will update it to this size."

That is, instead of ignoring the first size dimensions on some condition, we should check whether it is nullptr.
If it is nullptr -> No conflict, continue and update size
Not nullptr, same value as new size -> No conflict, continue
Not nullptr, different value than old -> Discordant sizes, bail-out (return false)

I agree with it. ScopArrayInfo::updateSizes was modified according to these comments.

This is hypothetical since, AFAIK, updateSizes is only called during polly-scops pass when there are no newly created arrays (yet).

If I'm not mistaken, after application of the patch the first dimensions can be nullptr even when there are no newly created arrays. To check it, we can, for example, add the following code to the updateSizes and run 'make check-polly'.

if (DimensionSizes.size() > 0 && !DimensionSizes[0])
  abort();

For non-MK_Arrays, the sizes are not relevant. It could have valid values of:

{} (empty sizes array)
{nullptr} (unknown size)
{1} (exactly one element; scalar)
Probably the last is "most accurate", but I don't really have a preference here. Use whatever works best.
Actually, this gives me the idea that would could handle such scalar ScopArrayInfos as a special case of newly created arrays, since for both we are going to create allocas for which we need the size.

What do you think?

I think that it's reasonable. Should we try to implement it in a separate patch?

sorry for the late reply.

np.

I agree with it. ScopArrayInfo::updateSizes was modified according to these comments.

The new diff still treats the first dimension specially, although there is nothing special about it (which is the motivation for my remarks). Here is what I had in mind:

for (int i = 0; i < SharedDims; i++) {
  auto &NewSize = NewSizes[i + ExtraDimsNew];
  auto &KnownSize = DimensionSizes[i + ExtraDimsOld];
  if (NewSize && KnownSize && NewSize != KnownSize)
   return false;
}

This is hypothetical since, AFAIK, updateSizes is only called during polly-scops pass when there are no newly created arrays (yet).

If I'm not mistaken, after application of the patch the first dimensions can be nullptr even when there are no newly created arrays. To check it, we can, for example, add the following code to the updateSizes and run 'make check-polly'.

if (DimensionSizes.size() > 0 && !DimensionSizes[0])
  abort();

I think that the first dimensions is always nullptr, and all others are never nullptr. This is what your code is written for, but we can be more general, where nullptr could be at any position.

For non-MK_Arrays, the sizes are not relevant. It could have valid values of:

{} (empty sizes array)
{nullptr} (unknown size)
{1} (exactly one element; scalar)
Probably the last is "most accurate", but I don't really have a preference here. Use whatever works best.
Actually, this gives me the idea that would could handle such scalar ScopArrayInfos as a special case of newly created arrays, since for both we are going to create allocas for which we need the size.

What do you think?

I think that it's reasonable. Should we try to implement it in a separate patch?

If you are interested, do it in a separate patch.

(I already accepted the patch as I think it is already functionally working, so go ahead if you feel to commit; this is only how I think the code could be 'nicer')

This revision was automatically updated to reflect the committed changes.

I think that the first dimensions is always nullptr, and all others are never nullptr. This is what your code is written for, but we can be more general, where nullptr could be at any position.

OK. If this is the case, we should probably add additional checks. For example, as far as I understand, DimSCEVs from IslExprBuilder::createAccessAddress should not be nullptrs.

If you are interested, do it in a separate patch.

(I already accepted the patch as I think it is already functionally working, so go ahead if you feel to commit; this is only how I think the code could be 'nicer')

OK. Thanks for the review!

I think that the first dimensions is always nullptr, and all others are never nullptr. This is what your code is written for, but we can be more general, where nullptr could be at any position.

OK. If this is the case, we should probably add additional checks. For example, as far as I understand, DimSCEVs from IslExprBuilder::createAccessAddress should not be nullptrs.

This is true. If we hit nullptr at code generation, we don't have collected enough information and should never happen.

OK. Thanks for the review!

Thanks for writing the patch.