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>
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>
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 %16 ; MemoryUse(liveOnEntry) %18 = load i32, i32* %17, align 4, !tbaa !2 %19 = getelementptr inbounds i32, i32* %2, i64 %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 %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 %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. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171219/b2c2f1c0/attachment.html>
@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 %16 > ; MemoryUse(liveOnEntry) > %18 = load i32, i32* %17, align 4, !tbaa !2 > %19 = getelementptr inbounds i32, i32* %2, i64 %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 %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 %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/6cf71285/attachment.html>
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'taffect 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 > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171219/026c05d1/attachment.html>