<div dir="ltr">Without the patch is also returns the wrong answer for all of these, it just doesn't cause LICM to promote because it returns PartialAlias  (which is still wrong).<div><br></div><div>We return may-alias instead, and now suddenly it's happy to promote them.</div><div><br></div><div>The broken noalias results exist both before and after my patch:<br><br><div>===== Alias Analysis Evaluator Report =====</div><div>   521 Total Alias Queries Performed</div><div>   176 no alias responses (33.7%)</div><div>-  334 may alias responses (64.1%)</div><div>-  10 partial alias responses (1.9%)</div><div>+  344 may alias responses (66.0%)</div><div>+  0 partial alias responses (0.0%)</div><div>   1 must alias responses (0.1%)</div><div><br></div><div><br></div><div>I suspect this is all caused by a different set of bugs:</div><div><span style="font-size:13.1999998092651px"><br></span></div><div><span style="font-size:13.1999998092651px">1. visitStoreInst does not appear to handle the case of value being a GEP properly (Personally, i had no idea this was allowed ...)</span><br></div><div><div>It should somehow call into the visitGEP code, but it doesn't.</div></div><div><br></div><div>Thus, it never assigns anything into the value of the global.</div><div>2. Something is either busted in querying or in attributes for stores that have geps directly as their pointer value.</div><div><br></div><div dir="ltr"><div><br></div><div>I will work up a separate patch for this issue unless someone thinks i should shoehorn it into the existing patch.</div><div><br></div><div><br></div><div><br></div><div><br></div><br><div class="gmail_quote">On Fri Jan 23 2015 at 12:52:02 PM Ana Pazos <<a href="mailto:apazos@codeaurora.org" target="_blank">apazos@codeaurora.org</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div lang="EN-US" link="blue" vlink="purple"><div><p class="MsoNormal">Hi Daniel,<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></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”).<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal">I looked at one of the failures and it has to do with disambiguating array indexes.<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></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.<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal">Find attached a reduced test case. <u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></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<u></u><u></u></p><p class="MsoNormal">LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 1)<u></u><u></u></p><p class="MsoNormal">LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 2)<u></u><u></u></p><p class="MsoNormal">LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 3)<u></u><u></u></p><p class="MsoNormal">LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 4)<u></u><u></u></p><p class="MsoNormal">LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 5)<u></u><u></u></p><p class="MsoNormal">LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 6)<u></u><u></u></p><p class="MsoNormal">LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 7)<u></u><u></u></p><p class="MsoNormal">LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 8)<u></u><u></u></p><p class="MsoNormal">LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 9)<u></u><u></u></p><p class="MsoNormal">LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 10)<u></u><u></u></p><p class="MsoNormal">LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 11)<u></u><u></u></p><p class="MsoNormal">LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 12)<u></u><u></u></p><p class="MsoNormal">LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 13)<u></u><u></u></p><p class="MsoNormal">LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 14)<u></u><u></u></p><p class="MsoNormal">LICM: Promoting value stored to in loop: i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 15)<u></u><u></u></p><p class="MsoNormal">LICM sinking instruction:   %conv32 = trunc i32 %add31 to i16<u></u><u></u></p><p class="MsoNormal">LICM sinking instruction:   %add31 = sub nsw i32 %conv18, %conv17<u></u><u></u></p><p class="MsoNormal">LICM sinking instruction:   %conv22 = trunc i32 %sub to i16<u></u><u></u></p><p class="MsoNormal">LICM sinking instruction:   %sub = sub nsw i32 %conv17, %conv18<u></u><u></u></p><p class="MsoNormal">LICM sinking instruction:   %conv19 = trunc i32 %add to i16<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></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<u></u><u></u></p><p class="MsoNormal">ok<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal">If you look at the .ll file, you notice that  pointer p alias with pA:<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal">%p.0 = phi i16* [ getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 0), %for.body ], [ %incdec.ptr49, %for.body48 ]<u></u><u></u></p><p class="MsoNormal">…<u></u><u></u></p><p class="MsoNormal">for.body48:                   <u></u>                    ; preds = %for.cond45<u></u><u></u></p><p class="MsoNormal">  %incdec.ptr49 = getelementptr inbounds i16* %p.0, i64 1<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal">CFL AA disambiguates p, pA[0], but not the other indexes (coming from incdec.ptr49 updates):<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal">Basic AA disambiguates them all:<u></u><u></u></p><p class="MsoNormal">opt -basicaa -aa-eval -evaluate-aa-metadata -print-no-aliases -print-may-aliases -disable-output test2.ll<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></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<u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal">Thanks,<u></u><u></u></p><p class="MsoNormal">Ana.<u></u><u></u></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></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"> <a href="mailto:llvmdev-bounces@cs.uiuc.edu" target="_blank">llvmdev-bounces@cs.uiuc.edu</a> [mailto:<a href="mailto:llvmdev-bounces@cs.uiuc.edu" target="_blank">llvmdev-bounces@cs.<u></u>uiuc.edu</a>] <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</span></p></div></div><div lang="EN-US" link="blue" vlink="purple"><div><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><br><b>Subject:</b> Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers<u></u><u></u></span></p></div></div><div lang="EN-US" link="blue" vlink="purple"><div><p class="MsoNormal"><u></u> <u></u></p><div><p class="MsoNormal">Works for me<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></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:<u></u><u></u></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 :)<u></u><u></u></p></div><div><div><p class="MsoNormal"><u></u> <u></u></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:<u></u><u></u></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><u></u><u></u></p><div><p class="MsoNormal"><u></u> <u></u></p></div></div><div><div><p class="MsoNormal">We can add a special "Unknown" StratifiedAttr and query it before anything else, i.e:<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">// in CFLAliasAnalysis::query, as the first potential return<u></u><u></u></p></div><div><p class="MsoNormal">if (AttrsA[AttrUnknown] || AttrsB[AttrUnknown])<u></u><u></u></p></div><div><p class="MsoNormal">  return MayAlias;<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">The only *potential* issue with this approach would be that in the following code segment:<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">void fn() {<u></u><u></u></p></div><div><p class="MsoNormal">  int *foo = (int*)rand();<u></u><u></u></p></div><div><p class="MsoNormal">  int *bar = new int;<u></u><u></u></p></div><div><p class="MsoNormal">  int **baz = rand() ? &foo : &bar;<u></u><u></u></p></div><div><p class="MsoNormal">  int value = **baz;<u></u><u></u></p></div><div><p class="MsoNormal">}<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">The stratified sets would look like:<u></u><u></u></p></div><div><p class="MsoNormal">    {value} is below {foo, bar} is below {baz}. <u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></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.<u></u><u></u></p></div></div><div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">George<u></u><u></u></p></div></div><div><div><p class="MsoNormal"><u></u> <u></u></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:<u></u><u></u></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"><u></u> <u></u></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 :)<u></u><u></u></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.<u></u><u></u></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". :)<u></u><u></u></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.<u></u><u></u></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.<u></u><u></u></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?<u></u><u></u></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).<u></u><u></u></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!<u></u><u></u></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> <u></u><u></u></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"><u></u><u></u></span></p><div><div><p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:black"><u></u> <u></u></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>-- <u></u><u></u></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<u></u><u></u></span></p></div></div></div></div></blockquote></div><p class="MsoNormal"><u></u> <u></u></p></div></div></blockquote></div></div></div></blockquote></div><p class="MsoNormal"><u></u> <u></u></p></div></div></div></blockquote></div></div></div></div>