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>
> MemoryUses can reach back past the nearest def, so that doesn't affectuses Ahh, I see. I did not know this. Thanks for the clarification. 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? 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/1d74662e/attachment-0001.html>
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>