<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=utf-8"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Roboto;
panose-1:0 0 0 0 0 0 0 0 0 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:Roboto;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-GB link=blue vlink=purple><div class=WordSection1><p class=MsoNormal><span style='font-family:Roboto;mso-fareast-language:EN-US'>Hi Kuba,<o:p></o:p></span></p><p class=MsoNormal><span style='font-family:Roboto;mso-fareast-language:EN-US'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-family:Roboto;mso-fareast-language:EN-US'>wow – thank you SO much for taking the time to answer in such detail!<o:p></o:p></span></p><p class=MsoNormal><span style='font-family:Roboto;mso-fareast-language:EN-US'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-family:Roboto;mso-fareast-language:EN-US'>These are lots of hints, I will gladly + thoroughly check them all :) I am currently researching different ways of tackling _<i>static</i>_ data race detection on instruction level (LLVM IR) _<i>without</i>_ the need of source code annotations incl. different trade-offs on different programs (I will narrow the topic down a bit as I go and have an understanding of what’s currently possible).<o:p></o:p></span></p><p class=MsoNormal><span style='font-family:Roboto;mso-fareast-language:EN-US'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-family:Roboto;mso-fareast-language:EN-US'>Thanks again for pointing me directions,<o:p></o:p></span></p><p class=MsoNormal><span style='font-family:Roboto;mso-fareast-language:EN-US'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-family:Roboto;mso-fareast-language:EN-US'>Cheers<o:p></o:p></span></p><p class=MsoNormal><span style='font-family:Roboto;mso-fareast-language:EN-US'>Armin<o:p></o:p></span></p><p class=MsoNormal><span style='font-family:Roboto;mso-fareast-language:EN-US'><o:p> </o:p></span></p><p class=MsoNormal><b><span lang=EN-US>From:</span></b><span lang=EN-US> Jakub (Kuba) Kuderski <kubakuderski@gmail.com> <br><b>Sent:</b> 18 December 2018 19:21<br><b>To:</b> armin@hasitzka.com<br><b>Cc:</b> llvm-dev <llvm-dev@lists.llvm.org><br><b>Subject:</b> Re: [llvm-dev] Interprocedural AA<o:p></o:p></span></p><p class=MsoNormal><o:p> </o:p></p><div><div><div><div><div><div><p class=MsoNormal style='margin-bottom:12.0pt'>Hi Armin,<br><br>For demand-driven pointer analysis, there's cfl-steens-aa and cfl-anders-aa already in LLVM [1]. Last I've heard, the implementation was good enough to be used for optimization, but I don't know if it has bit-rotten or not since then.<o:p></o:p></p></div><div><p class=MsoNormal>For global analysis, you can take a look at the SVF framework [2]. They have nice documentation that explains how the analysis works.<br>As for the original DSA, we maintain a port for fairly recent llvm 5.0 as a part of the SeaHorn verification framework [3]. There's also our custom flavor of DSA, SeaDsa [4].<br><br>But taking a step back, it really depends on what you want to do with it. If you want to optimize programs, perhaps it'd be best if you relied on Basic/TB AA and inlined in all the interprocedural contexts you care about. If that's not feasible, if you don't intend to do many AA queries, try CFL from LLVM. If you need precise interprocedural AA for whole programs, and your programs are small, try SVF. To my knowledge, no publicly-available Andersen-style pointer analysis scales to large programs (say > 500MB bitcode), and you may have more luck with DSA. The best approach is probably to take existing implementations, see which one is scalable enough for the problem you are interested in, and tweak it to gain more precision. If you are interested in AA, there is a nice overview of the field here [5].<br><br>Best,<br>Kuba<br><br>[1] <a href="https://github.com/grievejia/GSoC2016/blob/master/writeup.pdf" target="_blank">https://github.com/grievejia/GSoC2016/blob/master/writeup.pdf</a><br>[2] <a href="https://github.com/SVF-tools/SVF">https://github.com/SVF-tools/SVF</a><br>[3] <a href="https://github.com/seahorn/llvm-dsa/tree/llvm-5.0">https://github.com/seahorn/llvm-dsa/tree/llvm-5.0</a><br>[4] <a href="https://github.com/seahorn/sea-dsa">https://github.com/seahorn/sea-dsa</a><br>[5] <a href="https://yanniss.github.io/points-to-tutorial15.pdf">https://yanniss.github.io/points-to-tutorial15.pdf</a><o:p></o:p></p></div></div></div></div></div></div><p class=MsoNormal><o:p> </o:p></p><div><div><p class=MsoNormal>On Tue, Dec 18, 2018 at 11:21 AM via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<o:p></o:p></p></div><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm'><p class=MsoNormal>Hi,<br><br>I'm looking for interprocedural AAs and have, of course, found<br><a href="https://llvm.org/docs/AliasAnalysis.html" target="_blank">https://llvm.org/docs/AliasAnalysis.html</a>. However, the AAs that come<br>bundled with LLVM do not work interprocedurally in a way that I need it<br>(on/with stack variables). The two interesting looking AAs come with the<br>optional `poolalloc' module that hasn't been updated in years (I guess<br><a href="http://lists.llvm.org/pipermail/llvm-dev/2015-February/082054.html" target="_blank">http://lists.llvm.org/pipermail/llvm-dev/2015-February/082054.html</a> never<br>happened). My question: is there currently some interprocedural AA that<br>LLVM suggests (and/or even uses internally) that can cope with something<br>like this (without the need to inline everything for analysis' sake):<br><br>void foo(int* x) {<br> *x = 22; // <-- same value<br>}<br><br>int main(void) {<br> int x; // <-- same value<br> (void) foo(&x);<br> return 0;<br>}<br><br>Thanks a lot for your thoughts :)<br><br>Armin<br><br>_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></p></blockquote></div><p class=MsoNormal><br clear=all><o:p></o:p></p><div><p class=MsoNormal><o:p> </o:p></p></div><p class=MsoNormal>-- <o:p></o:p></p><div><div><p class=MsoNormal>Jakub Kuderski<o:p></o:p></p></div></div></div></body></html>