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>