[llvm-dev] MemorySSA question

[Venugopal Raghavan via llvm-dev]

Hi,

I am new to MemorySSA and wanted to understand its capabilities. Hence I
wrote the following program (test.c):

int N;

void test(int *restrict a, int *restrict b, int *restrict c, int *restrict
d, int *restrict e) {
  int i;
  for (i = 0; i < N; i = i + 5) {
     a[i] = b[i] + c[i];
  }

  for (i = 0; i < N - 5; i = i + 5) {
     e[i] = a[i] * d[i];
  }
}

I compiled this program using the following commands:

clang -c -o test_clang_out.ll -emit-llvm -O3 test.c
opt -o test_opt_out.ll -O3 -passes='print<memoryssa>' -disable-output
test_clang_out.ll > out 2>&1

The relevant parts of the file "out" are shown below:
                                 .
                                 .
                                 .

for.body:                                         ; preds = %for.body.lr.ph,
%for.body
; 3 = MemoryPhi({for.body.lr.ph,liveOnEntry},{for.body,1})
  %indvars.iv35 = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next36,
%for.body ]
  %arrayidx = getelementptr inbounds i32, i32* %b, i64 %indvars.iv35
; MemoryUse(3)
  %2 = load i32, i32* %arrayidx, align 4, !tbaa !2
  %arrayidx2 = getelementptr inbounds i32, i32* %c, i64 %indvars.iv35
; MemoryUse(3)
  %3 = load i32, i32* %arrayidx2, align 4, !tbaa !2
  %add = add nsw i32 %3, %2
  %arrayidx4 = getelementptr inbounds i32, i32* %a, i64 %indvars.iv35
*; 1 = MemoryDef(3)*
  store i32 %add, i32* %arrayidx4, align 4, !tbaa !2
  %indvars.iv.next36 = add nuw nsw i64 %indvars.iv35, 5
  %cmp = icmp slt i64 %indvars.iv.next36, %1
  br i1 %cmp, label %for.body, label %for.end

 for.end:                                          ; preds = %for.body
  %cmp729 = icmp sgt i32 %0, 5
  br i1 %cmp729, label %for.body8.lr.ph, label %for.end17

for.body8.lr.ph:                                  ; preds = %for.end
  %sub = add nsw i32 %0, -5
  %4 = sext i32 %sub to i64
  br label %for.body8

  for.body8:                                        ; preds = %
for.body8.lr.ph, %for.body8
*; 4 = MemoryPhi({for.body8.lr.ph
<http://for.body8.lr.ph>,1},{for.body8,2})*
  %indvars.iv = phi i64 [ 0, %for.body8.lr.ph ], [ %indvars.iv.next,
%for.body8 ]
  %arrayidx10 = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
*; MemoryUse(4)*
  %5 = load i32, i32* %arrayidx10, align 4, !tbaa !2
  %arrayidx12 = getelementptr inbounds i32, i32* %d, i64 %indvars.iv
; MemoryUse(4)
  %6 = load i32, i32* %arrayidx12, align 4, !tbaa !2
  %mul = mul nsw i32 %6, %5
  %arrayidx14 = getelementptr inbounds i32, i32* %e, i64 %indvars.iv
*; 2 = MemoryDef(4)*
  store i32 %mul, i32* %arrayidx14, align 4, !tbaa !2
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 5
  %cmp7 = icmp slt i64 %indvars.iv.next, %4
  br i1 %cmp7, label %for.body8, label %for.end17



I have highlighted the interesting lines in bold.

I was interested in the use of array "a" in the second loop and and wanted
to check if memorySSA would show the reaching definitions for these uses to
emanate from the definitions in  1 = MemoryDef(3)  and, indeed, the
MemoryUse(4) corresponding to the use of "a" shows the reaching definition
to be from the MemoryPhi node 4, which, in turn has one of its reaching
definitions as 1 = MemoryDef(3). But this MemoryPHi node also has another
reaching definition which is 2 = MemoryDef(4) which corresponds to the
definition of array e in the second loop.

This seems to make the MemorySSA form imprecise because it seems to
indicate that the use of "a" in the second loop could be having a reaching
definition from the definition of "a" in the first loop or the definition
of "e" in the second loop (through the MemoryPhi). I would have expected
only the first reaching definition to be inferred.

Am I mis-interpreting the information here or mis-understanding the
capabilities of MemorySSA? If not, can someone explain why the information
is imprecise? Maybe the underlying alias analysis is unable to disambiguate
the different arrays? But I would have thought that this would not be a
difficult case for alias analysis.

Thanks.

Regards,
Venugopal Raghavan.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171219/50aae653/attachment.html>