[llvm-dev] MemorySSA question
Daniel Berlin via llvm-dev
llvm-dev at lists.llvm.org
Tue Dec 19 09:45:03 PST 2017
On Tue, Dec 19, 2017 at 9:31 AM, Siddharth Bhat <siddu.druid at gmail.com>
wrote:
> > MemoryUses can reach back past the nearest def, so that doesn't affect
> uses
>
> Ahh, I see. I did not know this. Thanks for the clarification.
>
Basically, we allow anything that doesn't require us to have multiple
variables representing the heap.
> I now believe I had passed insufficient AA information when I was trying
> to use memorySSA.
>
> Can I add a detailed explanation that explains this to the memorySSA docs,
> or the "analysis passes" list?
>
Send a patch and i'll be hapy to review it.
> Thanks,
> Siddharth
>
> On Tue 19 Dec, 2017, 21:26 Daniel Berlin, <dberlin at dberlin.org> wrote:
>
>> On Tue, Dec 19, 2017 at 9:10 AM, Siddharth Bhat via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>>> 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".
>>>
>>
>> This is true for def-def relationships, but doesn't;'t matter here.
>>
>>>
>>>
>> 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.
>>>
>>> Yes, but MemoryUses can reach back past the nearest def, so that doesn't
>> affect uses.
>>
>> The limitation here is deliberately done to keep it only requiring a
>> single phi.
>>
>> All data from building this for years in GCC (which also moved from
>> "precise" to "imprecise" for the same reason) told us that the massive
>> amount of def-use chains you end up with from trying to model def-def
>> relationships precisely was not worth it by far.
>>
>> (It degrades into putting N^2 variables into SSA, and attaching N
>> variables to each def/use).
>>
>> 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!
>>>
>>> _______________________________________________
>>> 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/51a5ab63/attachment.html>
More information about the llvm-dev
mailing list