[llvm-dev] MemorySSA question

[Siddharth Bhat via llvm-dev]

I could be entirely wrong, but from my understanding of memorySSA, each def
defines an "abstract heap state" which has the coarsest possible definition
- any write will be modelled as a "new heap state". So in that sense, from
what I understand, it does not actually model the heap in a fine grained
way. Any write to any part of the heap will create a new memorydef node.

With respect to that model, memorySSA is right. The value of A could depend
on the abstract heap state of the definition of array "e".

I'm on my phone, so this may not make much sense, but I hope this helps,
Siddharth.

On Tue 19 Dec, 2017, 15:13 Venugopal Raghavan via llvm-dev, <
llvm-dev at lists.llvm.org> wrote:

> 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.
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-- 
Sending this from my phone, please excuse any typos!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171219/da1f45eb/attachment-0001.html>