Page MenuHomePhabricator

[Dependence Analysis] Enable delinearization of fixed sized arrays
ClosedPublic

Authored by artemrad on Apr 28 2021, 2:04 PM.

Details

Summary

Allow delinearization of fixed sized arrays if we can prove that the GEP indices do not overflow the array dimensions. The checks applied are similar to the ones that are used for delinearization of parametric size arrays. Make sure that the GEP indices are non-negative and that they are smaller than the range of that dimension.

Changes Summary:

  • Updated the LIT tests with more exact values, as we are able to delinearize and apply more exact tests
  • profitability.ll - now able to delinearize in all cases, no need to use -da-disable-delinearization-checks flag and run the test twice
  • loop-interchange-optimization-remarks.ll - in one of the cases we are able to delinearize without using -da-disable-delinearization-checks
  • SimpleSIVNoValidityCheckFixedSize.ll - removed unnecessary "-da-disable-delinearization-checks" flag. Now can get the exact answer without it.
  • SimpleSIVNoValidityCheckFixedSize.ll and PreliminaryNoValidityCheckFixedSize.ll - made negative tests more explicit, in order to demonstrate the need for "-da-disable-delinearization-checks" flag

Diff Detail

Event Timeline

artemrad created this revision.Apr 28 2021, 2:04 PM
artemrad requested review of this revision.Apr 28 2021, 2:04 PM
bmahjour added inline comments.Apr 29 2021, 8:20 AM
llvm/lib/Analysis/DependenceAnalysis.cpp
3351–3393

perhaps part of the old comment can be carried over here to explain what we mean by in-range and why we have that option.

3355

In order to avoid code duplication, you should create a lambda for the code from line 3354 to 3364, parameterize SrcSize, SrcPtr, and SrcSubscripts, and call that lambda twice (once for checking Src* and once for checking Dst*).

3384

this assert should be moved right before line 3350, since the new range check assumes that the size array is one element smaller than the subscripts array.

llvm/test/Analysis/DependenceAnalysis/Invariant.ll
8

Glad to see this comment, but it should be written as a loop nest to be semantically equivalent to the test

for (int i = 0; i < 40; i+=5)
  for (int j = 0; j < 40; j+=5)
    ...

Thanks for the patch.

llvm/lib/Analysis/DependenceAnalysis.cpp
3355

A lambda might also useful to have the cleanup code just once. (and make return skip all remaining tests)

Check = [] {
  for (...) {
    return false;
  }
  return true;
};
if (Check()) {
   ...
   return false;
}

SrcSubscripts.clear();
DstSubscripts.clear();
return false;
3356

[style] Don’t “almost always” use auto, except in specific cases.

3368

[style] Don’t “almost always” use auto, except in specific cases.

artemrad updated this revision to Diff 341930.Apr 30 2021, 8:49 AM

Fixed style issues
Moved repeated code into a lamba
Fixed Invariant.ll comment

artemrad marked an inline comment as done.Apr 30 2021, 8:53 AM

Addressed all comments

llvm/lib/Analysis/DependenceAnalysis.cpp
3351–3393

Done

3355

Done. Thanks for noticing this. It looks much cleaner

3356

Done

3368

Done

3384

Done

llvm/test/Analysis/DependenceAnalysis/Invariant.ll
8

Derp. You are right. Fixed.

LGTM.

@bmahjour Please accept if you are happy as well.

llvm/test/Analysis/DependenceAnalysis/Invariant.ll
9–13

[nit]

fhahn added a comment.Apr 30 2021, 9:16 AM

Can you also add some dedicated negative tests?

FYI a while ago I worked on a set of patches to add versioning support when de-linearizing accesses in DA. It's still a bit messy (there's some overlap with this patch, but the version here is much nicer by using the existing isKnownNonNegative & co), but it seems like a reasonable future extension. Not sure when/if I'll have time to break up the patch & finish it up.

llvm/lib/Analysis/DependenceAnalysis.cpp
3372

Can these now be early exits?

artemrad updated this revision to Diff 341994.Apr 30 2021, 11:38 AM
artemrad edited the summary of this revision. (Show Details)
  • SimpleSIVNoValidityCheckFixedSize.ll - removed unnecessary "-da-disable-delinearization-checks" flag. Now can get the exact answer without it.
  • SimpleSIVNoValidityCheckFixedSize.ll and PreliminaryNoValidityCheckFixedSize.ll - made negative tests more explicit, in order to demonstrate the need for "-da-disable-delinearization-checks" flag

@fhahn There already exists negative tests for delinearization in the LIT tests (see most tests in loop-interchange-optimization-remarks.ll). I still agree with you though, negative tests should still be present in the DependenceAnalysis folder directly, not somewhere else by fluke. In the most recent update to the diff I added explicit negative tests, see SimpleSIVNoValidityCheckFixedSize.ll and PreliminaryNoValidityCheckFixedSize.ll

artemrad added inline comments.Apr 30 2021, 11:49 AM
llvm/lib/Analysis/DependenceAnalysis.cpp
3372

I guess you are right. In my code we will exit early as soon as we do the next iteration of the loop (see loop condition.) With your proposal we skip a few instructions, for the cost of adding brackets to the if statement. I don't know if that is worth it, and whether it will make any impact on the performance as the loop calculation is fairly lightweight.

I don't personally have a preference, if you insist I will add a return statement there.

artemrad marked 6 inline comments as done and an inline comment as not done.Apr 30 2021, 1:12 PM

@bmahjour @fhahn Please let me know if there are further comments, otherwise please accept. I believe to have addressed all comments.

fhahn added inline comments.May 3 2021, 7:00 AM
llvm/lib/Analysis/DependenceAnalysis.cpp
3372

My thinking was that we could get rid of the FailedRangeCheck variable, and just return false here (and return true; in at the ned. Then have

if (!AllIndicesInRange() || !AllIndicesInRange())
...

It seems to me that this would simplify the code a bit and is more in line with the usual style in LLVM ( https://llvm.org/docs/CodingStandards.html#use-early-exits-and-continue-to-simplify-code)

artemrad updated this revision to Diff 342380.May 3 2021, 7:24 AM

@fhahn You are right, removing FailingRangeCheck is much cleaner. I have updated the code as per your comment.

Meinersbur added inline comments.May 3 2021, 7:25 AM
llvm/lib/Analysis/DependenceAnalysis.cpp
3372

Some cleanups need to be done in the fail case:

SrcSubscripts.clear();
DstSubscripts.clear();

This is why is suggested earlier to wrap the checks in another Check lambda. We already have a lambda, resulting in a lambda-in-a-lambda. Could be done (or refactored into its own function), but I am not sure whether the result will be any nicer.

Alternatively, one could wrap the clean-up in a destructor scope using a llvm::make_scope_exit.

artemrad marked 2 inline comments as done.May 3 2021, 7:25 AM
bmahjour accepted this revision.EditedMay 3 2021, 1:47 PM

LGTM pending indicated test change and no further comments from Michael.

llvm/lib/Analysis/DependenceAnalysis.cpp
3372

Not sure, I follow your suggestion @Meinersbur . The lambda is just checking the range, returning true if in range and false otherwise. The cleanup is done on line 3383-3384.

llvm/test/Analysis/DependenceAnalysis/PreliminaryNoValidityCheckFixedSize.ll
3

see comment below.

30

This is already being done in llvm/test/Analysis/DependenceAnalysis/Preliminary.ll. No need to repeat it here.

This revision is now accepted and ready to land.May 3 2021, 1:47 PM