Dear LLVM developers, My name is Artem Vopilov, I am a student at TU Darmstadt. I am writing to you again to ask about Alias Analysis. Now I attached IR code and C code of program I analyze with Alias Analysis. Running commands "opt -analyze -aa-eval -print-all-alias-modref-info" and for printing sets of alias "opt -analyze -aa-eval -print-alias-sets" gives me the results, that in main function variables %a, %0, %2, %4 alias. However I expected from Alias Analysis to indicate that pointers which point to same memory location alias, namely, %ptra and %ptrb. I learnt from your last messages, that "A pointer is just a variable containing memory address, so pointer itself will never alias with other pointers, but the ‘pointee’ will alias with other memory addresses." My goal is to find sets of pointers, that point to the same memory locations. Am I right, that with Alias Analysis I cannot accomplish my aim? Is it possible to achieve it using LLVM? Thank you. I am looking forward to hearing from you! Respectfully yours, Artem Vopilov -------------- next part -------------- An embedded and charset-unspecified text was scrubbed... Name: test_IR.txt URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20181214/8bf6d1b1/attachment.txt> -------------- next part -------------- A non-text attachment was scrubbed... Name: text.c Type: text/x-c Size: 432 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20181214/8bf6d1b1/attachment.bin>
Doerfert, Johannes Rudolf via llvm-dev
2018-Dec-14 16:58 UTC
[llvm-dev] LLVM Alias Analysis problem
Hi Artem, 1) Please do not CC all the llvm lists you can find. llvm-dev is the one for questions like this one, llvm-admin, mailman, bugs-admin, ... are not. 2) Please attach the _full_ LLVM-IR you used, the ".txt" file you attached is not complete and therefore not helpful. We can all open/read ".ll" files and so should you. As long as you pass the -S flag to opt (and clang in combination with -emit-llvm) you get human readable (=plain text) LLVM-IR as outpu. 3) You should probably run something like: clang -emit-llvm -S -O3 -mllvm -disable-llvm-optzns test.c -o test.ll to get your initial IR. Then you probably want to continue with opt -S -mem2reg -instcombine -simplifycfg test.ll -o test_clean.ll to clean up the IR a bit (especially to remove the stack locations introduced for variables and transform them into "proper SSA values".) Finally you run your analyzes as you did before opt -analyze -aa-eval -print-all-alias-modref-info test_clean.ll to get your results. If you need help understand the results, please let us know and provide enough information for us to comprehend your problem. You should also take a look at the test.ll and test_clean.ll and make sure you fully understand what the code representation means. As I noted in the other thread, your example is to simple, after the stack locations are promoted to registers, there is no "ptra/ptrb" that could alias anymore. I hope this helps. Cheers, Johannes On 12/14, Артём Вопилов via llvm-dev wrote:> Dear LLVM developers, > > My name is Artem Vopilov, I am a student at TU Darmstadt. I am writing to you again to ask about Alias Analysis. > > Now I attached IR code and C code of program I analyze with Alias Analysis. > > Running commands "opt -analyze -aa-eval -print-all-alias-modref-info" and for printing sets of alias "opt -analyze -aa-eval -print-alias-sets" gives me the results, that in main function variables %a, %0, %2, %4 alias. > > However I expected from Alias Analysis to indicate that pointers which point to same memory location alias, namely, %ptra and %ptrb. > I learnt from your last messages, that "A pointer is just a variable containing memory address, so pointer itself will never alias with other pointers, but the ‘pointee’ will alias with other memory addresses." > > My goal is to find sets of pointers, that point to the same memory locations. > Am I right, that with Alias Analysis I cannot accomplish my aim? Is it possible to achieve it using LLVM? > Thank you. > > I am looking forward to hearing from you! > > Respectfully yours, > Artem Vopilov> ; ModuleID = '<stdin>' > target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" > target triple = "x86_64-unknown-linux-gnu" > > ; Function Attrs: nounwind uwtable > define i32 @main() #0 { > entry: > %retval = alloca i32, align 4 > %a = alloca i32, align 4 > %b = alloca i32, align 4 > %ptra = alloca i32*, align 8 > %ptrb = alloca i32*, align 8 > %temp = alloca i32, align 4 > %sum = alloca i32, align 4 > store i32 0, i32* %retval > store i32 9, i32* %a, align 4 > store i32 7, i32* %b, align 4 > store i32* %a, i32** %ptra, align 8 > store i32* %a, i32** %ptrb, align 8 > %0 = load i32** %ptrb, align 8 > %1 = load i32* %0, align 4 > store i32 %1, i32* %b, align 4 > %2 = load i32** %ptrb, align 8 > store i32 4, i32* %2, align 4 > %3 = load i32* %a, align 4 > %4 = load i32** %ptrb, align 8 > %5 = load i32* %4, align 4 > %call = call i32 @addNumbers(i32 %3, i32 %5) > store i32 %call, i32* %sum, align 4 > %6 = load i32* %sum, align 4 > ret i32 %6 > } > > ; Function Attrs: nounwind uwtable > define i32 @addNumbers(i32 %a, i32 %b) #0 { > entry: > %a.addr = alloca i32, align 4 > %b.addr = alloca i32, align 4 > %result = alloca i32, align 4 > %notResult = alloca i32*, align 8 > store i32 %a, i32* %a.addr, align 4 > store i32 %b, i32* %b.addr, align 4 > store i32* %b.addr, i32** %notResult, align 8 > %0 = load i32* %a.addr, align 4 > %1 = load i32** %notResult, align 8 > %2 = load i32* %1, align 4 > %add = add nsw i32 %0, %2 > store i32 %add, i32* %result, align 4 > %3 = load i32* %result, align 4 > ret i32 %3 > }> #include <stdio.h> > > > int addNumbers(int a, int b); > > > int main() > { > int a = 9, b = 7; > int *ptra, *ptrb; > int temp; > int sum; > > ptra = &a; > ptrb = ptra; > b = *ptrb; > > *ptrb = 4; > > sum = addNumbers(a, *ptrb); > > return sum; > } > > > int addNumbers(int a,int b) > { > int result; > int *notResult; > > notResult = &b; > > result = a + *notResult; > > return result; > } >> _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-- Johannes Doerfert Researcher Argonne National Laboratory Lemont, IL 60439, USA jdoerfert at anl.gov -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 228 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20181214/4df083f0/attachment.sig>
Dear Johannes,<br /><br />Thank you for your response!<br />I will follow the steps you described!<br /><br />Best regards,<br />Artem<br /><br /><br /><div>14.12.2018, 19:59, "Doerfert, Johannes Rudolf" <jdoerfert@anl.gov>:</div><blockquote type="cite"><div><p>Hi Artem,<br /><br />1) Please do not CC all the llvm lists you can find. llvm-dev is the one<br /> for questions like this one, llvm-admin, mailman, bugs-admin, ... are<br /> not.<br /><br />2) Please attach the _full_ LLVM-IR you used, the ".txt" file you<br /> attached is not complete and therefore not helpful. We can all<br /> open/read ".ll" files and so should you. As long as you pass the -S<br /> flag to opt (and clang in combination with -emit-llvm) you get human<br /> readable (=plain text) LLVM-IR as outpu.<br /><br />3) You should probably run something like:<br /> clang -emit-llvm -S -O3 -mllvm -disable-llvm-optzns test.c -o test.ll<br /> to get your initial IR. Then you probably want to continue with<br /> opt -S -mem2reg -instcombine -simplifycfg test.ll -o test_clean.ll<br /> to clean up the IR a bit (especially to remove the stack locations<br /> introduced for variables and transform them into "proper SSA values".)<br /> Finally you run your analyzes as you did before<br /> opt -analyze -aa-eval -print-all-alias-modref-info test_clean.ll<br /> to get your results. If you need help understand the results, please<br /> let us know and provide enough information for us to comprehend your<br /> problem. You should also take a look at the test.ll and test_clean.ll<br /> and make sure you fully understand what the code representation<br /> means. As I noted in the other thread, your example is to simple,<br /> after the stack locations are promoted to registers, there is no<br /> "ptra/ptrb" that could alias anymore.<br /><br />I hope this helps.<br /><br />Cheers,<br /> Johannes<br /><br /><br /><br />On 12/14, Артём Вопилов via llvm-dev wrote:<br /></p><blockquote> Dear LLVM developers,<br /><br /> My name is Artem Vopilov, I am a student at TU Darmstadt. I am writing to you again to ask about Alias Analysis.<br /><br /> Now I attached IR code and C code of program I analyze with Alias Analysis.<br /><br /> Running commands "opt -analyze -aa-eval -print-all-alias-modref-info" and for printing sets of alias "opt -analyze -aa-eval -print-alias-sets" gives me the results, that in main function variables %a, %0, %2, %4 alias.<br /><br /> However I expected from Alias Analysis to indicate that pointers which point to same memory location alias, namely, %ptra and %ptrb.<br /> I learnt from your last messages, that "A pointer is just a variable containing memory address, so pointer itself will never alias with other pointers, but the ‘pointee’ will alias with other memory addresses."<br /><br /> My goal is to find sets of pointers, that point to the same memory locations.<br /> Am I right, that with Alias Analysis I cannot accomplish my aim? Is it possible to achieve it using LLVM?<br /> Thank you.<br /><br /> I am looking forward to hearing from you!<br /><br /> Respectfully yours,<br /> Artem Vopilov<br /></blockquote><p><br /></p><blockquote> ; ModuleID = '<stdin>'<br /> target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"<br /> target triple = "x86_64-unknown-linux-gnu"<br /><br /> ; Function Attrs: nounwind uwtable<br /> define i32 @main() #0 {<br /> entry:<br /> %retval = alloca i32, align 4<br /> %a = alloca i32, align 4<br /> %b = alloca i32, align 4<br /> %ptra = alloca i32*, align 8<br /> %ptrb = alloca i32*, align 8<br /> %temp = alloca i32, align 4<br /> %sum = alloca i32, align 4<br /> store i32 0, i32* %retval<br /> store i32 9, i32* %a, align 4<br /> store i32 7, i32* %b, align 4<br /> store i32* %a, i32** %ptra, align 8<br /> store i32* %a, i32** %ptrb, align 8<br /> %0 = load i32** %ptrb, align 8<br /> %1 = load i32* %0, align 4<br /> store i32 %1, i32* %b, align 4<br /> %2 = load i32** %ptrb, align 8<br /> store i32 4, i32* %2, align 4<br /> %3 = load i32* %a, align 4<br /> %4 = load i32** %ptrb, align 8<br /> %5 = load i32* %4, align 4<br /> %call = call i32 @addNumbers(i32 %3, i32 %5)<br /> store i32 %call, i32* %sum, align 4<br /> %6 = load i32* %sum, align 4<br /> ret i32 %6<br /> }<br /><br /> ; Function Attrs: nounwind uwtable<br /> define i32 @addNumbers(i32 %a, i32 %b) #0 {<br /> entry:<br /> %a.addr = alloca i32, align 4<br /> %b.addr = alloca i32, align 4<br /> %result = alloca i32, align 4<br /> %notResult = alloca i32*, align 8<br /> store i32 %a, i32* %a.addr, align 4<br /> store i32 %b, i32* %b.addr, align 4<br /> store i32* %b.addr, i32** %notResult, align 8<br /> %0 = load i32* %a.addr, align 4<br /> %1 = load i32** %notResult, align 8<br /> %2 = load i32* %1, align 4<br /> %add = add nsw i32 %0, %2<br /> store i32 %add, i32* %result, align 4<br /> %3 = load i32* %result, align 4<br /> ret i32 %3<br /> }<br /></blockquote><p><br /></p><blockquote> #include <stdio.h><br /><br /><br /> int addNumbers(int a, int b);<br /><br /><br /> int main()<br /> {<br /> int a = 9, b = 7;<br /> int *ptra, *ptrb;<br /> int temp;<br /> int sum;<br /><br /> ptra = &a;<br /> ptrb = ptra;<br /> b = *ptrb;<br /><br /> *ptrb = 4;<br /><br /> sum = addNumbers(a, *ptrb);<br /><br /> return sum;<br /> }<br /><br /><br /> int addNumbers(int a,int b)<br /> {<br /> int result;<br /> int *notResult;<br /><br /> notResult = &b;<br /><br /> result = a + *notResult;<br /><br /> return result;<br /> }<br /><br /></blockquote><p><br /></p><blockquote> _______________________________________________<br /> LLVM Developers mailing list<br /> <a href="http:///touch/compose?to=llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br /> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank" rel="noopener noreferrer">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br /></blockquote><p><br /><br /></p><span>-- <br /></span><p><br />Johannes Doerfert<br />Researcher<br /><br />Argonne National Laboratory<br />Lemont, IL 60439, USA<br /><br /><a href="http:///touch/compose?to=jdoerfert@anl.gov">jdoerfert@anl.gov</a><br /></p></div></blockquote><div><br /></div><div><br /></div><div></div><div><br /></div>
> On 14 Dec 2018, at 16:58, Doerfert, Johannes Rudolf via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > Hi Artem, > > 1) Please do not CC all the llvm lists you can find. llvm-dev is the one > for questions like this one, llvm-admin, mailman, bugs-admin, ... are > not. > > 2) Please attach the _full_ LLVM-IR you used, the ".txt" file you > attached is not complete and therefore not helpful. We can all > open/read ".ll" files and so should you. As long as you pass the -S > flag to opt (and clang in combination with -emit-llvm) you get human > readable (=plain text) LLVM-IR as outpu.According to the function group comments, the missing line seems to be: attributes #0 = { nounwind uwtable } @Артём: Hi, One other thing llvm-dev will need to know is the version of LLVM you're using. It looks like it isn't a recent version since load instructions changed a while back. For example: %0 = load i32* %a.addr, align 4 from your .txt is now: %0 = load i32, i32* %a.addr, align 4 in recent LLVM-IR.> 3) You should probably run something like: > clang -emit-llvm -S -O3 -mllvm -disable-llvm-optzns test.c -o test.ll > to get your initial IR. Then you probably want to continue with > opt -S -mem2reg -instcombine -simplifycfg test.ll -o test_clean.ll > to clean up the IR a bit (especially to remove the stack locations > introduced for variables and transform them into "proper SSA values".) > Finally you run your analyzes as you did before > opt -analyze -aa-eval -print-all-alias-modref-info test_clean.ll > to get your results. If you need help understand the results, please > let us know and provide enough information for us to comprehend your > problem. You should also take a look at the test.ll and test_clean.ll > and make sure you fully understand what the code representation > means. As I noted in the other thread, your example is to simple, > after the stack locations are promoted to registers, there is no > "ptra/ptrb" that could alias anymore. > > I hope this helps. > > Cheers, > Johannes > > > > On 12/14, Артём Вопилов via llvm-dev wrote: >> Dear LLVM developers, >> >> My name is Artem Vopilov, I am a student at TU Darmstadt. I am writing to you again to ask about Alias Analysis. >> >> Now I attached IR code and C code of program I analyze with Alias Analysis. >> >> Running commands "opt -analyze -aa-eval -print-all-alias-modref-info" and for printing sets of alias "opt -analyze -aa-eval -print-alias-sets" gives me the results, that in main function variables %a, %0, %2, %4 alias. >> >> However I expected from Alias Analysis to indicate that pointers which point to same memory location alias, namely, %ptra and %ptrb. >> I learnt from your last messages, that "A pointer is just a variable containing memory address, so pointer itself will never alias with other pointers, but the ‘pointee’ will alias with other memory addresses." >> >> My goal is to find sets of pointers, that point to the same memory locations. >> Am I right, that with Alias Analysis I cannot accomplish my aim? Is it possible to achieve it using LLVM? >> Thank you. >> >> I am looking forward to hearing from you! >> >> Respectfully yours, >> Artem Vopilov > >> ; ModuleID = '<stdin>' >> target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" >> target triple = "x86_64-unknown-linux-gnu" >> >> ; Function Attrs: nounwind uwtable >> define i32 @main() #0 { >> entry: >> %retval = alloca i32, align 4 >> %a = alloca i32, align 4 >> %b = alloca i32, align 4 >> %ptra = alloca i32*, align 8 >> %ptrb = alloca i32*, align 8 >> %temp = alloca i32, align 4 >> %sum = alloca i32, align 4 >> store i32 0, i32* %retval >> store i32 9, i32* %a, align 4 >> store i32 7, i32* %b, align 4 >> store i32* %a, i32** %ptra, align 8 >> store i32* %a, i32** %ptrb, align 8 >> %0 = load i32** %ptrb, align 8 >> %1 = load i32* %0, align 4 >> store i32 %1, i32* %b, align 4 >> %2 = load i32** %ptrb, align 8 >> store i32 4, i32* %2, align 4 >> %3 = load i32* %a, align 4 >> %4 = load i32** %ptrb, align 8 >> %5 = load i32* %4, align 4 >> %call = call i32 @addNumbers(i32 %3, i32 %5) >> store i32 %call, i32* %sum, align 4 >> %6 = load i32* %sum, align 4 >> ret i32 %6 >> } >> >> ; Function Attrs: nounwind uwtable >> define i32 @addNumbers(i32 %a, i32 %b) #0 { >> entry: >> %a.addr = alloca i32, align 4 >> %b.addr = alloca i32, align 4 >> %result = alloca i32, align 4 >> %notResult = alloca i32*, align 8 >> store i32 %a, i32* %a.addr, align 4 >> store i32 %b, i32* %b.addr, align 4 >> store i32* %b.addr, i32** %notResult, align 8 >> %0 = load i32* %a.addr, align 4 >> %1 = load i32** %notResult, align 8 >> %2 = load i32* %1, align 4 >> %add = add nsw i32 %0, %2 >> store i32 %add, i32* %result, align 4 >> %3 = load i32* %result, align 4 >> ret i32 %3 >> } > >> #include <stdio.h> >> >> >> int addNumbers(int a, int b); >> >> >> int main() >> { >> int a = 9, b = 7; >> int *ptra, *ptrb; >> int temp; >> int sum; >> >> ptra = &a; >> ptrb = ptra; >> b = *ptrb; >> >> *ptrb = 4; >> >> sum = addNumbers(a, *ptrb); >> >> return sum; >> } >> >> >> int addNumbers(int a,int b) >> { >> int result; >> int *notResult; >> >> notResult = &b; >> >> result = a + *notResult; >> >> return result; >> } >> > >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev> > > > -- > > Johannes Doerfert > Researcher > > Argonne National Laboratory > Lemont, IL 60439, USA > > jdoerfert at anl.gov <mailto:jdoerfert at anl.gov> > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <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/20181214/415bc973/attachment-0001.html>