[llvm-bugs] [Bug 28658] New: MemorySSA non linearity

[via llvm-bugs]

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

            Bug ID: 28658
           Summary: MemorySSA non linearity
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: sebpop at gmail.com
                CC: david.majnemer at gmail.com, dberlin at dberlin.org,
                    george.burgess.iv at gmail.com, llvm-bugs at lists.llvm.org
    Classification: Unclassified

While investigating the cause of a huge number of queries to the MemSSA in the
test-suite, I found that the compilation of
MultiSource/Applications/JM/ldecod/macroblock.c 
has an unusually high number of lookups:

   436 memoryssa                    - Number of Memory SSA version cache hits
 30401 memoryssa                    - Number of MemorySSA version cache inserts
128166 memoryssa                    - Number of Memory SSA version cache
lookups

>From that file I extracted something that exposes the non linearity in the
number of lookups.

$ cat fun.c
#define loop do { \
    for (j=0;j<m;j++)                           \
      A[i+j] += B[i+j] * C[i][H[i+j]];          \
  } while (0)

void fun(int *A, int **C, int *H, int n, int m) {
  int i, j;
  for (i=0;i<n;i++) {
    int *B = A[i] ? C[i] : C[i+1];
    loop; loop; loop; loop; loop; loop; loop; loop; loop; loop;
    loop; loop; loop; loop; loop; loop; loop; loop; loop; loop;
  }
}

$ clang -O3 -mllvm -stats fun.c
 10284 memoryssa             - Number of MemorySSA version cache inserts
 20569 memoryssa             - Number of Memory SSA version cache lookups

Number of Memory SSA version cache lookups:
80 loops - 20569
40 loops - 5489
20 loops - 1549
10 loops - 479
1 loop - 29

Adding another statement in the loop:
#define loop do { \
    for (j=0;j<m;j++)                           \
      A[i+j] += B[i+j] * C[i][H[i+j]];          \
      A[i-j] += B[i-j] * C[i+j][H[i-j]];        \
  } while (0)

Number of Memory SSA version cache lookups:
80 loops - 160824
40 loops - 42024
20 loops - 11424
10 loops - 3324
1 loop - 138

-- 
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/20160722/af1e6ec1/attachment.html>