[llvm-bugs] [Bug 40526] New: dependence analysis degradations due to removal of GEP analysis in D35430

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=40526

            Bug ID: 40526
           Summary: dependence analysis degradations due to removal of GEP
                    analysis in D35430
           Product: libraries
           Version: trunk
          Hardware: All
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Global Analyses
          Assignee: unassignedbugs at nondot.org
          Reporter: andreas.hommel at nxp.com
                CC: llvm-bugs at lists.llvm.org

We are currently moving a project from LLVM4 to LLVM7 and found major
degradations in some of our benchmarks that are due to the removal of the GEP
based da analysis by D35430.

The now purely SCEV based da pass is no longer able to handle this case:

#define N 200
int a[N][N];
void test(void)
{
  for (int i = 0; i < N; ++i) {
    for (int j = i + 1; j < N; ++j) {
      a[i][j] = a[j][i];
    }
  }
}

With LLVM4 we get 

$ clang -S -emit-llvm -O1 test.c
$ opt -analyze -da test.ll
Printing analysis 'Dependence Analysis' for function 'test':
da analyze - none!
da analyze - none!
da analyze - none!

With LLVM7 the above incorrectly prints:

da analyze -
input [* *]!
anti [<= *|<]!
none!

So, it fails to classify the first and second dependence correctly. The first
is for ld/ld, so it is not that important, but the second is for the ld/st
dependency.

The LLVM4 GEP based analysis for the ld/st uses this:

da analyze -     common nesting levels = 2
    maximum nesting levels = 2
    SrcPtrSCEV = @a
    DstPtrSCEV = @a
    using GEPs
    subscript 0
        src = 0
        dst = 0
        class = 0
        loops = {}
    subscript 1
        src = {{1,+,1}<nuw><nsw><%for.body>,+,1}<nuw><nsw><%for.body4>
        dst = {0,+,1}<nuw><nsw><%for.body>
        class = 3
        loops = {1 2}
    subscript 2
        src = {0,+,1}<nuw><nsw><%for.body>
        dst = {{1,+,1}<nuw><nsw><%for.body>,+,1}<nuw><nsw><%for.body4>
        class = 3
        loops = {1 2}
    Separable = {0}
    Coupled = {2}

and Banerjee can handle this.

With LLVM7 we only get a single SCEV subscript:

da analyze -     common nesting levels = 2
    maximum nesting levels = 2
    SrcPtrSCEV = @a
    DstPtrSCEV = @a
    using SCEVs
    SrcSCEV = {{(800 + @a)<nsw>,+,804}<%for.body>,+,800}<nw><%for.body4>
    DstSCEV = {{(4 + @a)<nuw><nsw>,+,804}<%for.body>,+,4}<nw><%for.body4>
    subscript 0
        src = {{(800 + @a)<nsw>,+,804}<%for.body>,+,800}<nw><%for.body4>
        dst = {{(4 + @a)<nuw><nsw>,+,804}<%for.body>,+,4}<nw><%for.body4>
        class = 3
        loops = {1 2}
    Separable = {0}
    Coupled = {}

Which is not handled by da’s delinearization or by any of the following da
analysis methods.

The GEP based analysis was removed by D35430, but I am not sure what this
removal really fixes. It also seems to break other cases that previously
worked, e.g., for loop interchange. The Coupled.ll in this review has two
dimensions in the code, so I am not seeing why there should be only one
dimension. Also, the new result, for

;;  for (long int i = 0; i < 50; i++) {
;;    A[i][3*i - 6] = i;
;;    *B++ = A[i][i];

define void @couple6([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
entry:
  br label %for.body

; CHECK-LABEL: couple6
; CHECK: da analyze - none!
; CHECK: da analyze - flow [<]!
; CHECK: da analyze - confused!
; CHECK: da analyze - none!
; CHECK: da analyze - confused!
; CHECK: da analyze - none!

is not correct either, the load/store intersect at i==3, so ideally this would
be reported as splitable.

The GEPs usually come from a compiler’s FE and are a direct representation of
the source code. Just not using this seems to be a mistake, especially since
there is currently no mechanism (e.g., da’s de-linearization) to recover this
for trivial and common cases like my example above.

I would propose to undo this commit and look for another way to fix this that
will not remove the GEP part.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20190130/ac2bfc7a/attachment.html>