[llvm-dev] MemorySSA question
Daniel Berlin via llvm-dev
llvm-dev at lists.llvm.org
Tue Dec 19 09:31:36 PST 2017
For use-def relationships, yes.
In particular, given a MemoryUse, it's defining access will be something
that actually may/must aliases it.
For def-def relationships, no.
Given a MemoryDef, it's defining access will be the nearest dominating
MemoryDef, regardless of whether it aliases it or not.
On Tue, Dec 19, 2017 at 9:25 AM, Siddharth Bhat <siddu.druid at gmail.com>
wrote:
> @daniel: so, memorySSA is as precise as AA allows it to be?
>
> Thanks
> Siddharth
>
> On Tue 19 Dec, 2017, 21:17 Daniel Berlin via llvm-dev, <
> llvm-dev at lists.llvm.org> wrote:
>
>> On Tue, Dec 19, 2017 at 3:13 AM, 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.
>>>
>>> Yes, that is correct.
>>
>>
>>> 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.
>>>
>>
>> If AA could prove it, MemorySSA would have a MemoryUse(1) instead.
>>
>>>
>>> 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.
>>>
>>
>> Here, the underlying AA is unable to distinguish, AFAICT, after some
>> transformation.
>>
>> clang -c -o test_clang_out.ll -emit-llvm -O3 test.c -S
>> bin/opt -print-memoryssa -debug test_clang_out.ll
>>
>> (note lack of other passes):
>>
>> ; <label>:15: ; preds = %15, %8
>> ; 3 = MemoryPhi({%8,liveOnEntry},{%15,1})
>> %16 = phi i64 [ 0, %8 ], [ %23, %15 ]
>> %17 = getelementptr inbounds i32, i32* %1, i64
>> <https://maps.google.com/?q=1,+i64&entry=gmail&source=g> %16
>> ; MemoryUse(liveOnEntry)
>> %18 = load i32, i32* %17, align 4, !tbaa !2
>> %19 = getelementptr inbounds i32, i32* %2, i64
>> <https://maps.google.com/?q=2,+i64&entry=gmail&source=g> %16
>> ; MemoryUse(liveOnEntry)
>> %20 = load i32, i32* %19, align 4, !tbaa !2
>> %21 = add nsw i32 %20, %18
>> %22 = getelementptr inbounds i32, i32* %0, i64 %16
>> ; 1 = MemoryDef(3)
>> store i32 %21, i32* %22, align 4, !tbaa !2
>> %23 = add nuw nsw i64 %16, 5
>> %24 = icmp slt i64 %23, %9
>> br i1 %24, label %15, label %10
>>
>> ; <label>:25: ; preds = %25, %12
>> ; 4 = MemoryPhi({%12,1},{%25,2})
>> %26 = phi i64 [ 0, %12 ], [ %33, %25 ]
>> %27 = getelementptr inbounds i32, i32* %0, i64 %26
>> ; MemoryUse(1)
>> %28 = load i32, i32* %27, align 4, !tbaa !2
>> %29 = getelementptr inbounds i32, i32* %3, i64
>> <https://maps.google.com/?q=3,+i64&entry=gmail&source=g> %26
>> ; MemoryUse(liveOnEntry)
>> %30 = load i32, i32* %29, align 4, !tbaa !2
>> %31 = mul nsw i32 %30, %28
>> %32 = getelementptr inbounds i32, i32* %4, i64
>> <https://maps.google.com/?q=4,+i64&entry=gmail&source=g> %26
>> ; 2 = MemoryDef(4)
>> store i32 %31, i32* %32, align 4, !tbaa !2
>> %33 = add nuw nsw i64 %26, 5
>> %34 = icmp slt i64 %33, %14
>> br i1 %34, label %25, label %35
>>
>>
>> Note memoryuse reaching back through memoryphi.
>>
>>
>> MemorySSA is deliberately imprecise for def-def relationships, but this
>> is not the cause of your issue. Yours is caused by AA not being able to
>> distinguish anymore.
>>
>>
>> _______________________________________________
>> 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/e7999707/attachment.html>
More information about the llvm-dev
mailing list