<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)"><!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><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;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",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;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:"Courier New";}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
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-US link=blue vlink=purple><div class=WordSection1><p class=MsoNormal>Hi Daniel,<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>There are correctness issues with the latest patch (from Wed 1/21/2015 11:10 AM with “Updated testcases to have MayAlias/note issues as FIXME”).<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I looked at one of the failures and it has to do with disambiguating array indexes.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>With CFL AA enabled, LICM promotion is sinking stores outside of the loop incorrectly. If I disable LICM promotion, the tests pass.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Find attached a reduced test case. <o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>clang -c --target=aarch64-linux-gnu -mcpu=cortex-a57 -Ofast -mllvm -use-cfl-aa -S test2.c -o test2out -mllvm -debug-only=licm<o:p></o:p></p><p class=MsoNormal>LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 1)<o:p></o:p></p><p class=MsoNormal>LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 2)<o:p></o:p></p><p class=MsoNormal>LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 3)<o:p></o:p></p><p class=MsoNormal>LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 4)<o:p></o:p></p><p class=MsoNormal>LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 5)<o:p></o:p></p><p class=MsoNormal>LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 6)<o:p></o:p></p><p class=MsoNormal>LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 7)<o:p></o:p></p><p class=MsoNormal>LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 8)<o:p></o:p></p><p class=MsoNormal>LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 9)<o:p></o:p></p><p class=MsoNormal>LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 10)<o:p></o:p></p><p class=MsoNormal>LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 11)<o:p></o:p></p><p class=MsoNormal>LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 12)<o:p></o:p></p><p class=MsoNormal>LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 13)<o:p></o:p></p><p class=MsoNormal>LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 14)<o:p></o:p></p><p class=MsoNormal>LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 15)<o:p></o:p></p><p class=MsoNormal>LICM sinking instruction: %conv32 = trunc i32 %add31 to i16<o:p></o:p></p><p class=MsoNormal>LICM sinking instruction: %add31 = sub nsw i32 %conv18, %conv17<o:p></o:p></p><p class=MsoNormal>LICM sinking instruction: %conv22 = trunc i32 %sub to i16<o:p></o:p></p><p class=MsoNormal>LICM sinking instruction: %sub = sub nsw i32 %conv17, %conv18<o:p></o:p></p><p class=MsoNormal>LICM sinking instruction: %conv19 = trunc i32 %add to i16<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>clang -c --target=aarch64-linux-gnu -mcpu=cortex-a57 -Ofast -mllvm –use-cfl-aa -S test2.c -o test2out -mllvm -debug-only=licm -mllvm -disable-licm-promotion<o:p></o:p></p><p class=MsoNormal>ok<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>If you look at the .ll file, you notice that pointer p alias with pA:<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>%p.0 = phi i16* [ getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 0), %for.body ], [ %incdec.ptr49, %for.body48 ]<o:p></o:p></p><p class=MsoNormal>…<o:p></o:p></p><p class=MsoNormal>for.body48: ; preds = %for.cond45<o:p></o:p></p><p class=MsoNormal> %incdec.ptr49 = getelementptr inbounds i16* %p.0, i64 1<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>CFL AA disambiguates p, pA[0], but not the other indexes (coming from incdec.ptr49 updates):<o:p></o:p></p><p class=MsoNormal> <span style='color:red'>MayAlias</span>: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 0), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> <span style='color:red'>NoAlias</span>: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 1), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 2), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 3), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 4), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 5), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 6), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 7), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 8), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 9), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 10), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 11), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 12), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 13), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 14), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 15), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Basic AA disambiguates them all:<o:p></o:p></p><p class=MsoNormal>opt -basicaa -aa-eval -evaluate-aa-metadata -print-no-aliases -print-may-aliases -disable-output test2.ll<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 0), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 1), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 2), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 3), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 4), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 5), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 6), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 7), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 8), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 9), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 10), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 11), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 12), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 13), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 14), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal> MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16 %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 15), align 2, !tbaa !1<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Thanks,<o:p></o:p></p><p class=MsoNormal>Ana.<o:p></o:p></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>From:</span></b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'> llvmdev-bounces@cs.uiuc.edu [mailto:llvmdev-bounces@cs.uiuc.edu] <b>On Behalf Of </b>George Burgess IV<br><b>Sent:</b> Thursday, January 22, 2015 5:47 PM<br><b>To:</b> Daniel Berlin<br><b>Cc:</b> Jiangning Liu; LLVM Developers Mailing List<br><b>Subject:</b> Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers<o:p></o:p></span></p><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal>Works for me<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal>On Thu, Jan 22, 2015 at 8:27 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>> wrote:<o:p></o:p></p><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in'><div><p class=MsoNormal style='margin-bottom:12.0pt'>We should use graph edges, so we can do something better at set build time :)<o:p></o:p></p></div><div><div><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal>On Thu Jan 22 2015 at 5:20:46 PM George Burgess IV <<a href="mailto:george.burgess.iv@gmail.com" target="_blank">george.burgess.iv@gmail.com</a>> wrote:<o:p></o:p></p><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in'><div><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'>> Should we be added an edge from the inttoptr to all other pointer values? Is there a better way?</span><o:p></o:p></p><div><p class=MsoNormal><o:p> </o:p></p></div></div><div><div><p class=MsoNormal>We can add a special "Unknown" StratifiedAttr and query it before anything else, i.e:<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>// in CFLAliasAnalysis::query, as the first potential return<o:p></o:p></p></div><div><p class=MsoNormal>if (AttrsA[AttrUnknown] || AttrsB[AttrUnknown])<o:p></o:p></p></div><div><p class=MsoNormal> return MayAlias;<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>The only *potential* issue with this approach would be that in the following code segment:<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>void fn() {<o:p></o:p></p></div><div><p class=MsoNormal> int *foo = (int*)rand();<o:p></o:p></p></div><div><p class=MsoNormal> int *bar = new int;<o:p></o:p></p></div><div><p class=MsoNormal> int **baz = rand() ? &foo : &bar;<o:p></o:p></p></div><div><p class=MsoNormal> int value = **baz;<o:p></o:p></p></div><div><p class=MsoNormal>}<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>The stratified sets would look like:<o:p></o:p></p></div><div><p class=MsoNormal> {value} is below {foo, bar} is below {baz}. <o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Potential issue: The sets {foo, bar} and {value} would be marked with the "Unknown" attribute, while {baz} would have no attributes. I can't immediately think of a case where {baz} lacking "Unknown" would be harmful, but if such a case exists, then we may need a different approach.<o:p></o:p></p></div></div><div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>George<o:p></o:p></p></div></div><div><div><p class=MsoNormal><o:p> </o:p></p></div><div><div><p class=MsoNormal>On Thu, Jan 22, 2015 at 8:03 PM, Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>> wrote:<o:p></o:p></p><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in'><div><div><div class=MsoNormal align=center style='text-align:center'><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'><hr size=2 width="100%" align=center></span></div><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'><o:p> </o:p></span></p><blockquote style='margin-top:5.0pt;margin-bottom:5.0pt'><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'>From: "Daniel Berlin" <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>><br> To: "Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>><br> Cc: "Jiangning Liu" <<a href="mailto:Jiangning.Liu@arm.com" target="_blank">Jiangning.Liu@arm.com</a>>, "George Burgess IV" <<a href="mailto:george.burgess.iv@gmail.com" target="_blank">george.burgess.iv@gmail.com</a>>, "LLVM Developers<br> Mailing List" <<a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a>>, "Nick Lewycky" <<a href="mailto:nlewycky@google.com" target="_blank">nlewycky@google.com</a>><br> Sent: Wednesday, January 21, 2015 3:48:25 PM<br> Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers<br> <br> On Wed Jan 21 2015 at 12:30:50 PM Hal Finkel < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> ><br> wrote:<br> <br> ----- Original Message -----<br> > From: "Daniel Berlin" < <a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a> ><br> > To: "Hal Finkel" < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> ><br> > Cc: "Jiangning Liu" < <a href="mailto:Jiangning.Liu@arm.com" target="_blank">Jiangning.Liu@arm.com</a> >, "George Burgess IV"<br> > < <a href="mailto:george.burgess.iv@gmail.com" target="_blank">george.burgess.iv@gmail.com</a> >, "LLVM Developers<br> > Mailing List" < <a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a> >, "Nick Lewycky" <<br> > <a href="mailto:nlewycky@google.com" target="_blank">nlewycky@google.com</a> ><br> > Sent: Wednesday, January 21, 2015 1:10:07 PM<br> > Subject: Re: [LLVMdev] question about enabling cfl-aa and<br> > collecting a57 numbers<br> > <br> > Updated testcases to have MayAlias/note issues as FIXME.<br> > <br> <br> Okay, thanks! This LGTM, but we should probably split the delegation<br> fixes from the others and commit as two separate patches (especially<br> because Ana noted some potential miscompiles caused by the other<br> improvements).<br> <br> <br> <br> I think she mentioned the miscompiles due to us returning<br> partialalias. But in any case, i 'm happy to, but just to note they<br> are all required to get the LICM issue fixed :)<o:p></o:p></span></p></blockquote><p class=MsoNormal style='margin-bottom:12.0pt'><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'><br>Okay, please do that and commit them.<o:p></o:p></span></p><blockquote style='margin-top:5.0pt;margin-bottom:5.0pt'><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'> <br> <br> <br> Regarding this:<br> <br> @@ -768,7 +774,10 @@ static Optional<StratifiedAttr><br> valueToAttrIndex(Value *Val) {<br> return AttrGlobalIndex;<br> <br> if (auto *Arg = dyn_cast<Argument>(Val))<br> - if (!Arg->hasNoAliasAttr())<br> + // Only pointer arguments should have the argument attribute,<br> + // because things can't escape through scalars without us seeing a<br> + // cast, and thus, interaction with them doesn't matter.<br> + if (!Arg->hasNoAliasAttr() && Arg->getType()->isPointerTy())<br> return argNumberToAttrIndex(Arg-> getArgNo());<br> return NoneType();<br> }<br> <br> when we do see the inttoptr case, we add an edge from the source to<br> the destination.<br> <br> <br> Correct.<br> <br> <br> If we've not noted potential aliasing of the non-pointer-typed<br> argument, then does this end up looking like a unique global?<br> <br> <br> <br> No. It will end up looking like something that points to nothing.<br> Even without this change, it will end up looking like something that<br> points to nothing, it will just have an attribute that says<br> "argument". :)<o:p></o:p></span></p></blockquote><p class=MsoNormal style='margin-bottom:12.0pt'><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'><br>Okay, fair enough.<o:p></o:p></span></p><blockquote style='margin-top:5.0pt;margin-bottom:5.0pt'><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'> <br> <br> You can come up with cases where even with this attribute set, it<br> will get the wrong answer. It just happens to have code that,<br> through luck, gets the right answer in a lot of cases:<br> <br> (That is this code:<br> <br> <br> if (AttrsA.any() && AttrsB.any())<br> return AliasAnalysis::MayAlias;<br> )<br> <br> <br> So there is a bug here, but it's not caused by this code.<br> <br> <br> The bug here is that we can't ever know what happens as the result of<br> inttoptr. We never do math, and the tracking we do is never going to<br> be sufficient to determine the range of possible pointers for an<br> inttoptr in all cases (in theory, it could point to anything<br> anywhere in the program. If we knew the sizes of *all* objects, and<br> any binary operator performed on it was evaluable, we could do a<br> little better. If we knew the value came from a ptrtoint, we could<br> do better, etc).<br> Same with ptrtoint.<br> <br> <br> The result of both of these instructions should start to be "we have<br> no idea what the pointer that comes from inttoptr or goes to<br> ptrtoint points to", and we should return mayalias for anything that<br> interacts with them.<br> We don't do that right now.<br> We are just hiding it mildly well.<o:p></o:p></span></p></blockquote><p class=MsoNormal style='margin-bottom:12.0pt'><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'><br>Should we be added an edge from the inttoptr to all other pointer values? Is there a better way?<o:p></o:p></span></p><blockquote style='margin-top:5.0pt;margin-bottom:5.0pt'><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'> <br> <br> <br> <br> <br> Speaking of which, the code has checks for global variables in<br> several places. Do these need to be for globals that are not aliases<br> and don't have weak linkage?<br> <br> <br> <br> It's more a question of whether they are in SSA form than if they are<br> globals.<br> <br> <br> It's effectively using Globals/Arguments as a way to say "don't know"<br> in some cases, where it should really just say "don't know".<br> <br> <br> There is a bunch of code i now have marked for cleanup and bugfixes<br> around these issues (constant vs global handling, handling of<br> non-pointer values, etc).<o:p></o:p></span></p></blockquote><p class=MsoNormal style='margin-bottom:12.0pt'><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'><br>Okay, thanks!<o:p></o:p></span></p><blockquote style='margin-top:5.0pt;margin-bottom:5.0pt'><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'> <br> <br> As mentioned, the above is necessary to fix the LICM issue (and is<br> correct, even if somewhere else is wrong. For reference, GCC does<br> the identical thing to what i'm saying :P), but i'm happy to move it<br> to a separate fix (that includes fixes for the other<br> argument/unknown related issues) if you like.<br> <br> <o:p></o:p></span></p></blockquote><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'><br>Generically speaking, I'd prefer the fixes to be broken up as much as practical. Please go ahead and commit them.</span><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:#888888'><br><br> -Hal</span><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'><o:p></o:p></span></p><div><div><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'><o:p> </o:p></span></p><blockquote style='margin-top:5.0pt;margin-bottom:5.0pt'><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'> <br> <br> <br> <br> <br> <br> Thanks again,<br> Hal<br> <br> > <br> > <br> > <br> > <br> > On Tue Jan 20 2015 at 3:54:10 PM Hal Finkel < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> ><br> > wrote:<br> > <br> > <br> > ----- Original Message -----<br> > > From: "Daniel Berlin" < <a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a> ><br> > > To: "Hal Finkel" < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> ><br> > > Cc: "Jiangning Liu" < <a href="mailto:Jiangning.Liu@arm.com" target="_blank">Jiangning.Liu@arm.com</a> >, "George Burgess<br> > > IV"<br> > > < <a href="mailto:george.burgess.iv@gmail.com" target="_blank">george.burgess.iv@gmail.com</a> >, "LLVM Developers<br> > > Mailing List" < <a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a> >, "Nick Lewycky" <<br> > > <a href="mailto:nlewycky@google.com" target="_blank">nlewycky@google.com</a> ><br> > > Sent: Tuesday, January 20, 2015 1:48:44 PM<br> > > Subject: Re: [LLVMdev] question about enabling cfl-aa and<br> > > collecting a57 numbers<br> > > <br> > > So, I can make all these testcases work, but it's a little tricky<br> > > (it<br> > > involves tracking some things, like GEP byte range, and then<br> > > checking bases and using getObjectSize, much like BasicAA does).<br> > > <br> > > <br> > > Because i really don't want to put that much "not well tested"<br> > > code<br> > > in a bugfix, and honestly, i'm not sure we will catch any cases<br> > > here<br> > > that BasicAA does not, i've attached a change to XFAIL these<br> > > testcases, and updated the code to return MayAlias.<br> > <br> > Okay. I think you might as well just update the test cases to want<br> > MayAlias, and put a FIXME comment explaining that they could be<br> > PartialAlias. As far as I know, there is no code in LLVM that<br> > really<br> > handles a PartialAlias differently than a MayAlias or MustAlias,<br> > and<br> > so while there may be some benefit here, I'm not sure it will be<br> > worth the effort.<br> > <br> > > <br> > > I will build and test a patch to get these back to PartialAlias,<br> > > but<br> > > this patch will at least get us to not be "giving wrong answers".<br> > > I<br> > > will also see if we catch anything with it that BasicAA does not,<br> > > because if we don't, it doesn't seem worth it to me.<br> > <br> > My guess is that BasicAA will get almost all of the interesting<br> > PartialAlias cases, and as I said, we essentially ignore them<br> > anyway.<br> > <br> > As a side note, there is this one place in lib/Analysis/<br> > MemoryDependenceAnalysis.cpp that could use some attention:<br> > <br> > #if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting<br> > loads<br> > // in terms of clobbering loads, but since it does this by looking<br> > // at the clobbering load directly, it doesn't know about any<br> > // phi translation that may have happened along the way.<br> > <br> > // If we have a partial alias, then return this as a clobber for<br> > the<br> > // client to handle.<br> > if (R == AliasAnalysis::PartialAlias)<br> > return MemDepResult::getClobber(Inst) ;<br> > #endif<br> > <br> > > <br> > > <br> > > Conservative new patch attached.<br> > > <br> > > <br> > > <br> > > (Note that i still updated the testcases, because we will *never*<br> > > be<br> > > able to legally return PartialAlias as they were written)<br> > > <br> > <br> > Yes, sounds good.<br> > <br> > -Hal<br> > <br> > > <br> > > <br> > > <br> > > <br> > > <br> > > <br> > > <br> > > On Sun Jan 18 2015 at 2:12:47 PM Daniel Berlin <<br> > > <a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a><br> > > > wrote:<br> > > <br> > > <br> > > <br> > > On Sat Jan 17 2015 at 3:15:27 PM Hal Finkel < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> ><br> > > wrote:<br> > > <br> > > <br> > > ----- Original Message -----<br> > > > From: "Daniel Berlin" < <a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a> ><br> > > > To: "Hal Finkel" < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> ><br> > > > Cc: "Jiangning Liu" < <a href="mailto:Jiangning.Liu@arm.com" target="_blank">Jiangning.Liu@arm.com</a> >, "George Burgess<br> > > > IV"<br> > > > < <a href="mailto:george.burgess.iv@gmail.com" target="_blank">george.burgess.iv@gmail.com</a> >, "LLVM Developers<br> > > > Mailing List" < <a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a> >, "Nick Lewycky" <<br> > > > <a href="mailto:nlewycky@google.com" target="_blank">nlewycky@google.com</a> ><br> > > > Sent: Saturday, January 17, 2015 1:08:10 PM<br> > > > Subject: Re: [LLVMdev] question about enabling cfl-aa and<br> > > > collecting a57 numbers<br> > > > <br> > > > <br> > > > <br> > > > <br> > > > On Sat Jan 17 2015 at 12:03:33 AM Hal Finkel < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a><br> > > > ><br> > > > wrote:<br> > > > <br> > > > <br> > > > Hi Danny,<br> > > > <br> > > > // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that<br> > > > // BasicAliasAnalysis wins if they disagree. This is intended<br> > > > to<br> > > > help<br> > > > // support "obvious" type-punning idioms.<br> > > > - if (UseCFLAA)<br> > > > - addPass( createCFLAliasAnalysisPass());<br> > > > addPass( createTypeBasedAliasAnalysisPa ss());<br> > > > addPass( createScopedNoAliasAAPass());<br> > > > + if (UseCFLAA)<br> > > > + addPass( createCFLAliasAnalysisPass());<br> > > > addPass( createBasicAliasAnalysisPass() );<br> > > > <br> > > > Do we really want to change the order here? I had originally<br> > > > placed<br> > > > it after the metadata-based passes thinking that the<br> > > > compile-time<br> > > > would be better (guessing that the metadata queries would be<br> > > > faster<br> > > > than the CFL queries, so if the metadata could quickly return a<br> > > > NoAlias, then we'd cut out unecessary CFL queries). Perhaps<br> > > > this<br> > > > is<br> > > > an irrelevant effect, but we should have some documented<br> > > > rationale.<br> > > > <br> > > > <br> > > > <br> > > > Yeah, this was a mistake (Chandler had suggested it was right<br> > > > earlier, but we were both wrong :P)<br> > > > <br> > > > <br> > > > <br> > > > ; CHECK: PartialAlias: i16* %bigbase0, i8* %phi<br> > > > -define i8 @test0(i8* %base, i1 %x) {<br> > > > +define i8 @test0(i1 %x) {<br> > > > entry:<br> > > > + %base = alloca i8, align 4<br> > > > %baseplusone = getelementptr i8* %base, i64 1<br> > > > br i1 %x, label %red, label %green<br> > > > red:<br> > > > @@ -25,8 +26,9 @@ green:<br> > > > }<br> > > > <br> > > > why should this return PartialAlias? %ohi does partially<br> > > > overlap,<br> > > > so<br> > > > this correct, but what happens when the overlap is partial or<br> > > > control dependent?<br> > > > So, after talking with some people offline, they convinced me<br> > > > in<br> > > > SSA<br> > > > form, the name would change in these situations, and the only<br> > > > situations you can get into trouble is with things "based on<br> > > > pointer<br> > > > arguments" (because you have no idea what their initial state<br> > > > is),<br> > > > or "globals" (because they are not in SSA form)<br> > > > I could not come up with a case otherwise<br> > > <br> > > Okay; that part of the code could really use some more<br> > > commentary.<br> > > I'd really appreciate it if you should put these thoughts in<br> > > written<br> > > form that could be added as comments.<br> > > <br> > > <br> > > <br> > > <br> > > <br> > > Will do<br> > > <br> > > <br> > > <br> > > > But i'm welcome to hear if you think this is wrong.<br> > > > <br> > > > FWIW: I bootstrapped/tested the compiler with an assert that<br> > > > triggered if CFL-AA was going to return PartialAlias and<br> > > > BasicAA<br> > > > would have returned NoAlias, and it did not trigger with this<br> > > > change.<br> > > > <br> > > > <br> > > > (It would have triggered before this set of changes)<br> > > > <br> > > > Not proof of course, but it at least tells me it's not<br> > > > "obviously<br> > > > wrong" :)<br> > > > <br> > > > <br> > > <br> > > That's good :) -- but, not exactly what I was concerned about.<br> > > Our<br> > > general convention has been that PartialAlias is a "strong"<br> > > result,<br> > > like MustAlias, but implies that AA has proved that only a<br> > > partial<br> > > overlap will occur.<br> > > <br> > > So, in this test case we get the right result:<br> > > <br> > > ; CHECK: PartialAlias: i16* %bigbase0, i8* %phi<br> > > define i8 @test0(i1 %x) {<br> > > entry:<br> > > %base = alloca i8, align 4<br> > > %baseplusone = getelementptr i8* %base, i64 1<br> > > br i1 %x, label %red, label %green<br> > > red:<br> > > br label %green<br> > > green:<br> > > %phi = phi i8* [ %baseplusone, %red ], [ %base, %entry ]<br> > > store i8 0, i8* %phi<br> > > <br> > > %bigbase0 = bitcast i8* %base to i16*<br> > > store i16 -1, i16* %bigbase0<br> > > <br> > > %loaded = load i8* %phi<br> > > ret i8 %loaded<br> > > }<br> > > <br> > > because %phi will have a partial overlap with %bigbase0, the only<br> > > uncertainty is whether the overlap is with the low byte or the<br> > > high<br> > > byte. But if I modify the test to be this:<br> > > <br> > > define i8 @test0x(i1 %x) {<br> > > entry:<br> > > %base = alloca i8, align 4<br> > > %baseplustwo = getelementptr i8* %base, i64 2<br> > > br i1 %x, label %red, label %green<br> > > red:<br> > > br label %green<br> > > green:<br> > > %phi = phi i8* [ %baseplustwo, %red ], [ %base, %entry ]<br> > > store i8 0, i8* %phi<br> > > <br> > > %bigbase0 = bitcast i8* %base to i16*<br> > > store i16 -1, i16* %bigbase0<br> > > <br> > > %loaded = load i8* %phi<br> > > ret i8 %loaded<br> > > }<br> > > <br> > > I still get this result:<br> > > PartialAlias: i16* %bigbase0, i8* %phi<br> > > <br> > > <br> > > <br> > > <br> > > <br> > > <br> > > <br> > > but now %phi might not overlap %bigbase0 at all (although, when<br> > > it<br> > > does, there is a partial overlap), so we should just return<br> > > MayAlias<br> > > (perhaps without delegation because this is a definitive<br> > > result?).<br> > > <br> > > <br> > > <br> > > <br> > > Yeah, i have to do some size checking, let me see if we have the<br> > > info<br> > > and i'll update the patch.<br> > > <br> > > <br> > > <br> > > <br> > > Otherwise, my view is that we should always delegate MayAlias,<br> > > because we have no idea what order the passes are in or what pass<br> > > someone has inserted where :)<br> > > <br> > > <br> > > (WIW: I believe the same about everything except MustAlias and<br> > > NoAlias, but currently we don't delegate PartialAlias.<br> > > We claim PartialAlias is a definitive result, but it really<br> > > isn't.<br> > > Right now we have TBAA that will give NoAlias results on things<br> > > other<br> > > passes claim are PartialAlias, and that result is correct. That's<br> > > just in our default, we have no idea what other people do. Even<br> > > if<br> > > you ignore TBAA, plenty of other compilers have noalias/mustalias<br> > > metadata that would have the same effect.<br> > <br> > --<br> > Hal Finkel<br> > Assistant Computational Scientist<br> > Leadership Computing Facility<br> > Argonne National Laboratory<br> > <br> <br> --<br> Hal Finkel<br> Assistant Computational Scientist<br> Leadership Computing Facility<br> Argonne National Laboratory<br> <br><br>-- <o:p></o:p></span></p></blockquote><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black'><br>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<o:p></o:p></span></p></div></div></div></div></blockquote></div><p class=MsoNormal><o:p> </o:p></p></div></div></blockquote></div></div></div></blockquote></div><p class=MsoNormal><o:p> </o:p></p></div></div></body></html>