[Dependence Analysis] Enable delinearization of fixed sized arrays

[artemrad]

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

[bmahjour]

llvm/lib/Analysis/DependenceAnalysis.cpp

3350

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.

3354

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*).

3383

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)
    ...

[Meinersbur]

Thanks for the patch.

llvm/lib/Analysis/DependenceAnalysis.cpp

3354

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;

3355

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

3367

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

[artemrad]

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

[artemrad]

Addressed all comments

llvm/lib/Analysis/DependenceAnalysis.cpp

3350

Done

3354

Done. Thanks for noticing this. It looks much cleaner

3355

Done

3367

Done

3383

Done

llvm/test/Analysis/DependenceAnalysis/Invariant.ll

8

Derp. You are right. Fixed.

[Meinersbur]

LGTM.

@bmahjour Please accept if you are happy as well.

llvm/test/Analysis/DependenceAnalysis/Invariant.ll

9–13

[nit]

[fhahn]

Can you also add some dedicated negative tests?

[fhahn]

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

3371

Can these now be early exits?

[artemrad]

• 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

[artemrad]

@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]

llvm/lib/Analysis/DependenceAnalysis.cpp

3371

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]

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

[fhahn]

llvm/lib/Analysis/DependenceAnalysis.cpp

3371

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]

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

[Meinersbur]

llvm/lib/Analysis/DependenceAnalysis.cpp

3371

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.

[bmahjour]

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

llvm/lib/Analysis/DependenceAnalysis.cpp

3371

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 ↗

(On Diff #342380)

see comment below.

30 ↗

(On Diff #342380)

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

[uabelho]

Hi,

I wrote a PR about a crash that started happening with this patch:
https://bugs.llvm.org/show_bug.cgi?id=52170

[fhahn]

In D101486#3063244, @uabelho wrote:

Hi,

I wrote a PR about a crash that started happening with this patch:
https://bugs.llvm.org/show_bug.cgi?id=52170

@artemrad , @andrew.w.kaylor did you get a chance to investigate the crash yet? Looks like this is still crashing. We might have to revert the patch until the crash is fixed.

[artemrad]

In D101486#3249142, @fhahn wrote:

In D101486#3063244, @uabelho wrote:

Hi,

I wrote a PR about a crash that started happening with this patch:
https://bugs.llvm.org/show_bug.cgi?id=52170

@artemrad , @andrew.w.kaylor did you get a chance to investigate the crash yet? Looks like this is still crashing. We might have to revert the patch until the crash is fixed.

My bad I missed the original post. Looking into it.

[artemrad]

In D101486#3249170, @artemrad wrote:

In D101486#3249142, @fhahn wrote:

In D101486#3063244, @uabelho wrote:

Hi,

I wrote a PR about a crash that started happening with this patch:
https://bugs.llvm.org/show_bug.cgi?id=52170

@artemrad , @andrew.w.kaylor did you get a chance to investigate the crash yet? Looks like this is still crashing. We might have to revert the patch until the crash is fixed.

My bad I missed the original post. Looking into it.

Bug fix in this review - https://reviews.llvm.org/D119261

llvm/lib/Analysis/DependenceAnalysis.cpp

bool DependenceInfo::tryDelinearize(Instruction *Src, Instruction *Dst,
   return true;
 }
 
 bool DependenceInfo::tryDelinearizeFixedSize(
     Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn,
     const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts,
     SmallVectorImpl<const SCEV *> &DstSubscripts) {
 
-  // In general we cannot safely assume that the subscripts recovered from GEPs
-  // are in the range of values defined for their corresponding array
-  // dimensions. For example some C language usage/interpretation make it
-  // impossible to verify this at compile-time. As such we give up here unless
-  // we can assume that the subscripts do not overlap into neighboring
-  // dimensions and that the number of dimensions matches the number of
-  // subscripts being recovered.
-  if (!DisableDelinearizationChecks)
-    return false;
-
   Value *SrcPtr = getLoadStorePointerOperand(Src);
   Value *DstPtr = getLoadStorePointerOperand(Dst);
   const SCEVUnknown *SrcBase =
       dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));
   const SCEVUnknown *DstBase =
       dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));
   assert(SrcBase && DstBase && SrcBase == DstBase &&
          "expected src and dst scev unknowns to be equal");
bool DependenceInfo::tryDelinearizeFixedSize(
   Value *DstBasePtr = DstGEP->getOperand(0);
   while (auto *PCast = dyn_cast<BitCastInst>(SrcBasePtr))
     SrcBasePtr = PCast->getOperand(0);
   while (auto *PCast = dyn_cast<BitCastInst>(DstBasePtr))
     DstBasePtr = PCast->getOperand(0);
 
   // Check that for identical base pointers we do not miss index offsets
   // that have been added before this GEP is applied.
-  if (SrcBasePtr == SrcBase->getValue() && DstBasePtr == DstBase->getValue()) {
-    assert(SrcSubscripts.size() == DstSubscripts.size() &&
-           SrcSubscripts.size() == SrcSizes.size() + 1 &&
-           "Expected equal number of entries in the list of sizes and "
-           "subscripts.");
-    LLVM_DEBUG({
-      dbgs() << "Delinearized subscripts of fixed-size array\n"
-             << "SrcGEP:" << *SrcGEP << "\n"
-             << "DstGEP:" << *DstGEP << "\n";
-    });
-    return true;
-  }
+  if (SrcBasePtr != SrcBase->getValue() || DstBasePtr != DstBase->getValue()) {
+    SrcSubscripts.clear();
+    DstSubscripts.clear();
+    return false;
+  }
+  // Statically check that the array bounds are in-range.
+  if (!DisableDelinearizationChecks) {
+    bool FailedRangeCheck = false;
+    size_t SrcSize = SrcSubscripts.size();
+    for (size_t I = 1; I < SrcSize && !FailedRangeCheck; ++I) {
+      const auto *S = SrcSubscripts[I];
+      if (!isKnownNonNegative(S, SrcPtr))
+        FailedRangeCheck = true;
+      if (auto *SType = dyn_cast<IntegerType>(S->getType())) {
+        const SCEV *Range =
+            SE->getConstant(ConstantInt::get(SType, SrcSizes[I - 1], false));
+        if (!isKnownLessThan(S, Range))
+          FailedRangeCheck = true;
+      }
+    }
+    size_t DstSize = DstSubscripts.size();
+    for (size_t I = 1; I < DstSize && !FailedRangeCheck; ++I) {
+      const auto *S = DstSubscripts[I];
+      if (!isKnownNonNegative(S, DstPtr))
+        FailedRangeCheck = true;
+      if (auto *SType = dyn_cast<IntegerType>(S->getType())) {
+        const SCEV *Range =
+            SE->getConstant(ConstantInt::get(SType, DstSizes[I - 1], false));
+        if (!isKnownLessThan(S, Range))
+          FailedRangeCheck = true;
+      }
+    }
+    if (FailedRangeCheck) {
+      SrcSubscripts.clear();
+      DstSubscripts.clear();
+      return false;
+    }
+  }
 
-  SrcSubscripts.clear();
-  DstSubscripts.clear();
-  return false;
-}
-
 bool DependenceInfo::tryDelinearizeParametricSize(
     Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn,
     const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts,
     SmallVectorImpl<const SCEV *> &DstSubscripts) {
 
   Value *SrcPtr = getLoadStorePointerOperand(Src);
   Value *DstPtr = getLoadStorePointerOperand(Dst);
   const SCEVUnknown *SrcBase =

llvm/test/Analysis/DependenceAnalysis/Coupled.ll

 ;;    *B++ = A[i][i];
 
 define void @couple11([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: couple11
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [=|<]!
+; CHECK: da analyze - flow [=|<] splitable!
+; CHECK: da analyze - split level = 1, iteration = 9!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

 ;;    *B++ = A[i][i];
 
 define void @couple12([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: couple12
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [<]!
+; CHECK: da analyze - flow [<] splitable!
+; CHECK: da analyze - split level = 1, iteration = 11!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

llvm/test/Analysis/DependenceAnalysis/Invariant.ll

 ; RUN: opt < %s -disable-output "-passes=print<da>" -aa-pipeline=basic-aa 2>&1 \
 ; RUN: | FileCheck %s
 ; RUN: opt < %s -analyze -enable-new-pm=0 -basic-aa -da | FileCheck %s
 
 ; Test for a bug, which caused an assert when an invalid
 ; SCEVAddRecExpr is created in addToCoefficient.
 
+; float foo (float g, float* rr[40]) {
+;     float res= 0.0f;
+;     for (int i = 0, j = 0; i < 40 && j < 40; i +=5, j+=5) {
+;         float add = rr[j][j] + rr[i][j];
+;         res = add > g? add : res;
+;     }
+;     return res;
+; }
+
 ; CHECK-LABEL: foo
 ; CHECK: da analyze - consistent input [S 0]!
-; CHECK: da analyze - input [* *|<]!
+; CHECK: da analyze - input [* 0|<]!
 ; CHECK: da analyze - none!
 
 define float @foo(float %g, [40 x float]* %rr) nounwind {
 entry:
   br label %for.cond1.preheader
 
 for.cond1.preheader:
   %i.04 = phi i32 [ 0, %entry ], [ %add10, %for.inc9 ]

llvm/test/Analysis/DependenceAnalysis/Separability.ll

 ;;        for (long int l = 0; l < 50; l++) {
 ;;          A[n][i][j + k] = i;
 ;;          *B++ = A[10][i + 10][2*j - l];
 
 define void @sep0([100 x [100 x i32]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
-; CHECK: da analyze - output [= * * S]!
+; CHECK: da analyze - output [0 * * S]!
 ; CHECK: da analyze - flow [* * * *|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - input [* * S *]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc22
   %B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc22 ]

 ;;        for (long int l = 0; l < 50; l++) {
 ;;          A[i][i][j + k] = i;
 ;;          *B++ = A[10][i + 10][2*j - l];
 
 define void @sep1([100 x [100 x i32]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
-; CHECK: da analyze - output [= * * S]!
+; CHECK: da analyze - output [0 * * S]!
 ; CHECK: da analyze - flow [* * * *|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - input [* * S *]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc22
   %B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc22 ]

 ;;        for (long int l = 0; l < 50; l++) {
 ;;          A[i][i][i + k][l] = i;
 ;;          *B++ = A[10][i + 10][j + k][l + 10];
 
 define void @sep2([100 x [100 x [100 x i32]]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
-; CHECK: da analyze - output [= S = =]!
-; CHECK: da analyze - flow [* * * <>]!
+; CHECK: da analyze - consistent output [0 S 0 0]!
+; CHECK: da analyze - flow [> * * -10]!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - input [= * * *]!
+; CHECK: da analyze - input [0 * * 0]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc26
   %B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc26 ]
   %i.07 = phi i64 [ 0, %entry ], [ %inc27, %for.inc26 ]
   br label %for.cond4.preheader
 

 ;;        for (long int l = 0; l < 50; l++) {
 ;;          A[i][i][i + k][l + k] = i;
 ;;          *B++ = A[10][i + 10][j + k][l + 10];
 
 define void @sep3([100 x [100 x [100 x i32]]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
-; CHECK: da analyze - output [= S = =]!
-; CHECK: da analyze - flow [* * * *|<]!
+; CHECK: da analyze - consistent output [0 S 0 0]!
+; CHECK: da analyze - flow [> * * *]!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - input [= * * *]!
+; CHECK: da analyze - input [0 * * 0]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc27
   %B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc27 ]
   %i.07 = phi i64 [ 0, %entry ], [ %inc28, %for.inc27 ]
   br label %for.cond4.preheader
 

llvm/test/Transforms/LoopInterchange/loop-interchange-optimization-remarks.ll

for.body4:                                        ; preds = %for.body4, %for.cond1.preheader
   %arrayidx10 = getelementptr inbounds [3 x [3 x i32]], [3 x [3 x i32]]* @A10, i64 0, i64 %indvars.iv, i64 %indvars.iv.next27
   %tmp1 = trunc i64 %indvars.iv to i32
   store i32 %tmp1, i32* %arrayidx10, align 4
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
   %exitcond = icmp ne i64 %indvars.iv.next, 3
   br i1 %exitcond, label %for.body4, label %for.cond.loopexit
 }
 
-; CHECK: --- !Missed
+; CHECK: --- !Passed
 ; CHECK-NEXT: Pass:            loop-interchange
-; CHECK-NEXT: Name:            Dependence
+; CHECK-NEXT: Name:            Interchanged
 ; CHECK-NEXT: Function:        test03
 ; CHECK-NEXT: Args:
-; CHECK-NEXT:   - String:          Cannot interchange loops due to dependences.
+; CHECK-NEXT:   - String:          Loop interchanged with enclosing loop.
 ; CHECK-NEXT: ...
 
 ; DELIN: --- !Passed
 ; DELIN-NEXT: Pass:            loop-interchange
 ; DELIN-NEXT: Name:            Interchanged
 ; DELIN-NEXT: Function:        test03
 ; DELIN-NEXT: Args:
 ; DELIN-NEXT:  - String:          Loop interchanged with enclosing loop.

llvm/test/Transforms/LoopInterchange/profitability.ll

 ; RUN: opt < %s -loop-interchange -pass-remarks-output=%t -verify-dom-info -verify-loop-info \
 ; RUN:     -pass-remarks=loop-interchange -pass-remarks-missed=loop-interchange
 ; RUN: FileCheck -input-file %t %s
 
-; RUN: opt < %s -loop-interchange -pass-remarks-output=%t -verify-dom-info -verify-loop-info \
-; RUN:     -pass-remarks=loop-interchange -pass-remarks-missed=loop-interchange \
-; RUN:     -da-disable-delinearization-checks
-; RUN: FileCheck --check-prefix=DELIN -input-file %t %s
-
 ;; We test profitability model in these test cases.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @A = common global [100 x [100 x i32]] zeroinitializer
 @B = common global [100 x [100 x i32]] zeroinitializer
 
 ;;---------------------------------------Test case 01---------------------------------
 ;; Loops interchange will result in code vectorization and hence profitable. Check for interchange.
 ;;   for(int i=1;i<100;i++)
 ;;     for(int j=1;j<100;j++)
 ;;       A[j][i] = A[j - 1][i] + B[j][i];
 
-; CHECK:      Name:            Dependence
+; CHECK:      Name:            Interchanged
 ; CHECK-NEXT: Function:        interchange_01
 
-; DELIN:      Name:            Interchanged
-; DELIN-NEXT: Function:        interchange_01
-
 define void @interchange_01() {
 entry:
   br label %for2.preheader
 
 for2.preheader:
   %i30 = phi i64 [ 1, %entry ], [ %i.next31, %for1.inc14 ]
   br label %for2