Page MenuHomePhabricator

[Polly] Delinearize _all_ accesses to a multi-dimensional array

Authored by grosser on Sep 12 2014, 3:29 AM.



Even though we previously correctly detected the multi-dimensional access
pattern for accesses with a certain base address, we only delinearized
non-affine accesses to this address. Affine accesses have not been touched and
remained as single dimensional accesses. The result was an inconsistent
description of accesses to the same array, with some being one dimensional and
some being multi-dimensional.

This patch ensures that all accesses are delinearized with the same
dimensionality as soon as a single one of them has been detected as non-affine.

While writing this patch, it became evident that the options
-polly-allow-nonaffine and -polly-detect-keep-going have not been properly
supported in case delinearization has been turned on. This patch adds relevant
test coverage and addresses these issues as well. We also added some more
documentation to the functions that are modified in this patch.

TODO: The documentation and the structure of this function is possibly still

non-perfect. If reviewers can suggest ways to further improve the
readability of this function, such comments are appreciated. Maybe we
should outline some of the computations performed in

This fixes

Diff Detail


Event Timeline

grosser updated this revision to Diff 13621.Sep 12 2014, 3:29 AM
grosser retitled this revision from to Delinearize _all_ accesses to a multi-dimensional array.
grosser updated this object.
grosser added a subscriber: Unknown Object (MLST).
jdoerfert retitled this revision from Delinearize _all_ accesses to a multi-dimensional array to [Polly] Delinearize _all_ accesses to a multi-dimensional array.Sep 12 2014, 3:43 AM
jdoerfert edited edge metadata.Sep 12 2014, 4:07 AM

some minor comments.

369 ↗(On Diff #13621)

What does PIAF mean?

388 ↗(On Diff #13621)

Did I miss an assignment of IsNonAffine or is this check always false?

405 ↗(On Diff #13621)

Could you use a cast or an assert here to indicate that we "know" it is an AddRec?

412 ↗(On Diff #13621)

The nested if statements make this harder to understand than it actually is.

Maybe we should just copy the isEmpty check, first if it is empty, then if it is not.

424 ↗(On Diff #13621)

Above you used continue here, then reported the invalid access and checked for kepp going, I like that way (the one above) better. Maybe you could even put the two into a small function.

469 ↗(On Diff #13621)

Shouldn't we at least detect them and bail?

Do we have a test case for this?

55 ↗(On Diff #13621)

Not needed.

7 ↗(On Diff #13621)

Not needed.

38 ↗(On Diff #13621)

Nice test case.

sebpop added inline comments.Sep 12 2014, 12:17 PM
369 ↗(On Diff #13621)

Pair <Instruction, AccessFunction>

412 ↗(On Diff #13621)

It is simpler to read the if statements when the short clause comes first:

if (Shape->DelinearizedSizes.empty()) {
  IsNonAffine = true;
} else {
  if (Acc->DelinearizedSubscripts.empty()) {
    IsNonAffine = true;
  } else {
     // Long clause goes here.

Hi Johannes, hi Sebastian

thanks for the review. It was very valuable and nicely improved this patch. I will send an updated version right after.

369 ↗(On Diff #13621)


Yes, this is definitely an abbreviation that is not well known. It was here before, but I can change it to just 'Pair'. That should be clear, as we extract the two elements in the following two lines.

388 ↗(On Diff #13621)

Good catch. In fact this part was just wrong. In case this is not a SCEVAddRecExpr, we should not report the full array as non-affine, but instead just do not collect parametric terms there. If I would just have fixed the code as written, every constant access e.g. A[0][0] would have broken the delinearization.

I added this case to the test case submitted later in this patch.

405 ↗(On Diff #13621)

Unfortunately we don't know. In case this is not a SCEVAddRecExpr, we now assume (and verify) the access corresponds to the innermost dimension.

412 ↗(On Diff #13621)

I pulled out the reporting of a failed delinearization. This removed one level of indentation.

424 ↗(On Diff #13621)

I had this before. The problem is that the code for this reporting would then be replicated a couple of times. I also thought about using a separate function, but as the result of the reporting can have control flow implications, I can not make this a simple function call, but would need something like the following for every case where we assign IsNonAffine:

if (reportAndCheckForReturn(Inst, S, &GlobalNonAffine)
  return false;

The other changes allowed a couple of simplifications. Maybe it is now already simple enough.

469 ↗(On Diff #13621)

This is somehow unrelated, but you are right it should be fixed. I added a separate patch that fixes this issue before we perform the actual all-accesses patch.

55 ↗(On Diff #13621)

Removed data layout and triple.

7 ↗(On Diff #13621)

Removed the triple, the data-layout is required for -polly-scops.

grosser updated this revision to Diff 13658.Sep 12 2014, 1:40 PM
grosser edited edge metadata.

A new patch:

"Check that the elements of an array have the same size"

And some updates to

"Delinearize _all_ accesses to a multi-dimensional array"

to address Johannes' review comments.

dpeixott added inline comments.Sep 12 2014, 1:49 PM
90 ↗(On Diff #13658)

The rrkDifferentElementSize enum value should go above rrkLastAffFunc because ReportDifferentArrayElementSize is a subclass of ReportAffFunc. Otherwise


will be false.

grosser updated this revision to Diff 13659.Sep 12 2014, 1:55 PM

Address David's comment

grosser updated this revision to Diff 13670.Sep 13 2014, 12:25 AM
grosser edited edge metadata.

Update the ReportDifferentElementSize.ll test case

For some reason, a wrong test case file slipped in, which did not test for the
right error.

jdoerfert accepted this revision.Sep 13 2014, 6:38 AM
jdoerfert edited edge metadata.


This revision is now accepted and ready to land.Sep 13 2014, 6:38 AM
grosser closed this revision.Sep 13 2014, 7:57 AM
grosser updated this revision to Diff 13672.

Closed by commit rL217727 (authored by @grosser).

grosser closed this revision.Sep 13 2014, 7:57 AM
grosser updated this revision to Diff 13673.

Closed by commit rL217728 (authored by @grosser).