<div dir="ltr">> <span style="font-size:12.8000001907349px">Fixing that still gives a wrong result, i haven't started to track down what *else* is going on here.</span><div><span style="font-size:12.8000001907349px"><br></span></div><div><span style="font-size:12.8000001907349px">Running with the attached diff + a modified buildGraphFrom to handle the constexpr GEPs, we seem to flag everything in test2.ll (conservatively) correctly.</span></div><div><span style="font-size:12.8000001907349px"><br></span></div><div><span style="font-size:12.8000001907349px">Is `store` the only place we can expect to see these constexpr analogs, or is just about anywhere fair game?</span></div><div><span style="font-size:12.8000001907349px"><br></span></div><div><span style="font-size:12.8000001907349px">George</span></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Jan 23, 2015 at 8:18 PM, Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">----- Original Message -----<br>
> From: "Daniel Berlin" <<a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a>><br>
> To: "Hal Finkel" <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>><br>
</span><span class="">> Cc: "Jiangning Liu" <<a href="mailto:Jiangning.Liu@arm.com">Jiangning.Liu@arm.com</a>>, "LLVM Developers Mailing List" <<a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a>>, "Ana Pazos"<br>
> <<a href="mailto:apazos@codeaurora.org">apazos@codeaurora.org</a>>, "George Burgess IV" <<a href="mailto:george.burgess.iv@gmail.com">george.burgess.iv@gmail.com</a>><br>
</span><span class="">> Sent: Friday, January 23, 2015 7:14:24 PM<br>
> Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers<br>
><br>
><br>
</span><span class="">> No, i mean the actual store instruction looks like "store i16<br>
> %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> 12), align 2, !tbaa !1"<br>
><br>
><br>
> Not that the pointer operand comes from a GEP, but it is a<br>
> constantexpr, whose opcode is GEP.<br>
<br>
</span>Ah, yep. We have ConstantExpr analogs for just about everything. ;)<br>
<span class=""><br>
><br>
><br>
> It sucks that there is such a complex thing to be handled as a store<br>
> operand directly , but such is life ...<br>
><br>
><br>
> CFL-AA *should* treat this like an assignment to GEP operand, not<br>
> like a normal store, which is *x = y. This is really *(&GEP operand)<br>
> = y.<br>
><br>
><br>
> But currently, it does nothing right here :)<br>
><br>
><br>
> I haven't tracked down entirely what is happening, but for sure,<br>
> visitStoreInst doesn't do the right thing in this case.<br>
> Fixing that still gives a wrong result, i haven't started to track<br>
> down what *else* is going on here.<br>
><br>
><br>
> I suspect either more ConstantExpr related bugs, or the global<br>
> attribute is not being fully propagated around or something.<br>
><br>
<br>
</span>Fair enough.<br>
<span class="HOEnZb"><font color="#888888"><br>
 -Hal<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
><br>
><br>
><br>
><br>
><br>
> On Fri Jan 23 2015 at 4:45:34 PM Hal Finkel < <a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a> ><br>
> wrote:<br>
><br>
><br>
> ----- Original Message -----<br>
> > From: "Daniel Berlin" < <a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a> ><br>
> > To: "Ana Pazos" < <a href="mailto:apazos@codeaurora.org">apazos@codeaurora.org</a> >, "George Burgess IV" <<br>
> > <a href="mailto:george.burgess.iv@gmail.com">george.burgess.iv@gmail.com</a> ><br>
> > Cc: "Jiangning Liu" < <a href="mailto:Jiangning.Liu@arm.com">Jiangning.Liu@arm.com</a> >, "LLVM Developers<br>
> > Mailing List" < <a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a> >, "Hal Finkel"<br>
> > < <a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a> ><br>
> > Sent: Friday, January 23, 2015 5:09:06 PM<br>
> > Subject: Re: [LLVMdev] question about enabling cfl-aa and<br>
> > collecting a57 numbers<br>
> ><br>
> ><br>
> > Without the patch is also returns the wrong answer for all of<br>
> > these,<br>
> > it just doesn't cause LICM to promote because it returns<br>
> > PartialAlias (which is still wrong).<br>
> ><br>
> ><br>
> > We return may-alias instead, and now suddenly it's happy to promote<br>
> > them.<br>
> ><br>
> ><br>
> > The broken noalias results exist both before and after my patch:<br>
> ><br>
> ><br>
> > ===== Alias Analysis Evaluator Report =====<br>
> > 521 Total Alias Queries Performed<br>
> > 176 no alias responses (33.7%)<br>
> > - 334 may alias responses (64.1%)<br>
> > - 10 partial alias responses (1.9%)<br>
> > + 344 may alias responses (66.0%)<br>
> > + 0 partial alias responses (0.0%)<br>
> > 1 must alias responses (0.1%)<br>
> ><br>
> ><br>
> ><br>
> ><br>
> > I suspect this is all caused by a different set of bugs:<br>
> ><br>
> ><br>
> > 1. visitStoreInst does not appear to handle the case of value being<br>
> > a<br>
> > GEP properly (Personally, i had no idea this was allowed ...)<br>
> ><br>
><br>
> You mean that the value being stored is a pointer value coming from a<br>
> GEP? Why would that be special (compared to any other way of<br>
> generating a pointer value, inttoptr for example)?<br>
><br>
> ><br>
> > It should somehow call into the visitGEP code, but it doesn't.<br>
> ><br>
> ><br>
> > Thus, it never assigns anything into the value of the global.<br>
> > 2. Something is either busted in querying or in attributes for<br>
> > stores<br>
> > that have geps directly as their pointer value.<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > I will work up a separate patch for this issue unless someone<br>
> > thinks<br>
> > i should shoehorn it into the existing patch.<br>
> ><br>
> ><br>
><br>
> A separate patch is good.<br>
><br>
> Thanks again,<br>
> Hal<br>
><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > On Fri Jan 23 2015 at 12:52:02 PM Ana Pazos < <a href="mailto:apazos@codeaurora.org">apazos@codeaurora.org</a><br>
> > ><br>
> > wrote:<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > Hi Daniel,<br>
> ><br>
> ><br>
> ><br>
> > There are correctness issues with the latest patch (from Wed<br>
> > 1/21/2015 11:10 AM with “Updated testcases to have MayAlias/note<br>
> > issues as FIXME”).<br>
> ><br>
> ><br>
> ><br>
> > I looked at one of the failures and it has to do with<br>
> > disambiguating<br>
> > array indexes.<br>
> ><br>
> ><br>
> ><br>
> > With CFL AA enabled, LICM promotion is sinking stores outside of<br>
> > the<br>
> > loop incorrectly. If I disable LICM promotion, the tests pass.<br>
> ><br>
> ><br>
> ><br>
> > Find attached a reduced test case.<br>
> ><br>
> ><br>
> ><br>
> > clang -c --target=aarch64-linux-gnu -mcpu=cortex-a57 -Ofast -mllvm<br>
> > -use-cfl-aa -S test2.c -o test2out -mllvm -debug-only=licm<br>
> ><br>
> > LICM: Promoting value stored to in loop: i16* getelementptr<br>
> > inbounds<br>
> > ([16 x i16]* @pA, i64 0, i64 1)<br>
> ><br>
> > LICM: Promoting value stored to in loop: i16* getelementptr<br>
> > inbounds<br>
> > ([16 x i16]* @pA, i64 0, i64 2)<br>
> ><br>
> > LICM: Promoting value stored to in loop: i16* getelementptr<br>
> > inbounds<br>
> > ([16 x i16]* @pA, i64 0, i64 3)<br>
> ><br>
> > LICM: Promoting value stored to in loop: i16* getelementptr<br>
> > inbounds<br>
> > ([16 x i16]* @pA, i64 0, i64 4)<br>
> ><br>
> > LICM: Promoting value stored to in loop: i16* getelementptr<br>
> > inbounds<br>
> > ([16 x i16]* @pA, i64 0, i64 5)<br>
> ><br>
> > LICM: Promoting value stored to in loop: i16* getelementptr<br>
> > inbounds<br>
> > ([16 x i16]* @pA, i64 0, i64 6)<br>
> ><br>
> > LICM: Promoting value stored to in loop: i16* getelementptr<br>
> > inbounds<br>
> > ([16 x i16]* @pA, i64 0, i64 7)<br>
> ><br>
> > LICM: Promoting value stored to in loop: i16* getelementptr<br>
> > inbounds<br>
> > ([16 x i16]* @pA, i64 0, i64 8)<br>
> ><br>
> > LICM: Promoting value stored to in loop: i16* getelementptr<br>
> > inbounds<br>
> > ([16 x i16]* @pA, i64 0, i64 9)<br>
> ><br>
> > LICM: Promoting value stored to in loop: i16* getelementptr<br>
> > inbounds<br>
> > ([16 x i16]* @pA, i64 0, i64 10)<br>
> ><br>
> > LICM: Promoting value stored to in loop: i16* getelementptr<br>
> > inbounds<br>
> > ([16 x i16]* @pA, i64 0, i64 11)<br>
> ><br>
> > LICM: Promoting value stored to in loop: i16* getelementptr<br>
> > inbounds<br>
> > ([16 x i16]* @pA, i64 0, i64 12)<br>
> ><br>
> > LICM: Promoting value stored to in loop: i16* getelementptr<br>
> > inbounds<br>
> > ([16 x i16]* @pA, i64 0, i64 13)<br>
> ><br>
> > LICM: Promoting value stored to in loop: i16* getelementptr<br>
> > inbounds<br>
> > ([16 x i16]* @pA, i64 0, i64 14)<br>
> ><br>
> > LICM: Promoting value stored to in loop: i16* getelementptr<br>
> > inbounds<br>
> > ([16 x i16]* @pA, i64 0, i64 15)<br>
> ><br>
> > LICM sinking instruction: %conv32 = trunc i32 %add31 to i16<br>
> ><br>
> > LICM sinking instruction: %add31 = sub nsw i32 %conv18, %conv17<br>
> ><br>
> > LICM sinking instruction: %conv22 = trunc i32 %sub to i16<br>
> ><br>
> > LICM sinking instruction: %sub = sub nsw i32 %conv17, %conv18<br>
> ><br>
> > LICM sinking instruction: %conv19 = trunc i32 %add to i16<br>
> ><br>
> ><br>
> ><br>
> > clang -c --target=aarch64-linux-gnu -mcpu=cortex-a57 -Ofast -mllvm<br>
> > –use-cfl-aa -S test2.c -o test2out -mllvm -debug-only=licm -mllvm<br>
> > -disable-licm-promotion<br>
> ><br>
> > ok<br>
> ><br>
> ><br>
> ><br>
> > If you look at the .ll file, you notice that pointer p alias with<br>
> > pA:<br>
> ><br>
> ><br>
> ><br>
> > %p.0 = phi i16* [ getelementptr inbounds ([16 x i16]* @pA, i64 0,<br>
> > i64<br>
> > 0), %for.body ], [ %incdec.ptr49, %for.body48 ]<br>
> ><br>
> > …<br>
> ><br>
> > for.body48: ; preds = %for.cond45<br>
> ><br>
> > %incdec.ptr49 = getelementptr inbounds i16* %p.0, i64 1<br>
> ><br>
> ><br>
> ><br>
> > CFL AA disambiguates p, pA[0], but not the other indexes (coming<br>
> > from<br>
> > incdec.ptr49 updates):<br>
> ><br>
> > MayAlias : %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 0), align 2, !tbaa !1<br>
> ><br>
> > NoAlias : %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 1), align 2, !tbaa !1<br>
> ><br>
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 2), align 2, !tbaa !1<br>
> ><br>
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 3), align 2, !tbaa !1<br>
> ><br>
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 4), align 2, !tbaa !1<br>
> ><br>
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 5), align 2, !tbaa !1<br>
> ><br>
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 6), align 2, !tbaa !1<br>
> ><br>
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 7), align 2, !tbaa !1<br>
> ><br>
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 8), align 2, !tbaa !1<br>
> ><br>
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 9), align 2, !tbaa !1<br>
> ><br>
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 10), align 2, !tbaa !1<br>
> ><br>
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 11), align 2, !tbaa !1<br>
> ><br>
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 12), align 2, !tbaa !1<br>
> ><br>
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 13), align 2, !tbaa !1<br>
> ><br>
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 14), align 2, !tbaa !1<br>
> ><br>
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 15), align 2, !tbaa !1<br>
> ><br>
> ><br>
> ><br>
> > Basic AA disambiguates them all:<br>
> ><br>
> > opt -basicaa -aa-eval -evaluate-aa-metadata -print-no-aliases<br>
> > -print-may-aliases -disable-output test2.ll<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 0), align 2, !tbaa !1<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 1), align 2, !tbaa !1<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 2), align 2, !tbaa !1<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 3), align 2, !tbaa !1<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 4), align 2, !tbaa !1<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 5), align 2, !tbaa !1<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 6), align 2, !tbaa !1<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 7), align 2, !tbaa !1<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 8), align 2, !tbaa !1<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 9), align 2, !tbaa !1<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 10), align 2, !tbaa !1<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 11), align 2, !tbaa !1<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 12), align 2, !tbaa !1<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 13), align 2, !tbaa !1<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 14), align 2, !tbaa !1<br>
> ><br>
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16<br>
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64<br>
> > 15), align 2, !tbaa !1<br>
> ><br>
> ><br>
> ><br>
> > Thanks,<br>
> ><br>
> > Ana.<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > From: <a href="mailto:llvmdev-bounces@cs.uiuc.edu">llvmdev-bounces@cs.uiuc.edu</a> [mailto: llvmdev-bounces@cs.<br>
> > <a href="http://uiuc.edu" target="_blank">uiuc.edu</a> ] On Behalf Of George Burgess IV<br>
> > Sent: Thursday, January 22, 2015 5:47 PM<br>
> > To: Daniel Berlin<br>
> > Cc: Jiangning Liu; LLVM Developers Mailing List<br>
> ><br>
> ><br>
> ><br>
> ><br>
> > Subject: Re: [LLVMdev] question about enabling cfl-aa and<br>
> > collecting<br>
> > a57 numbers<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > Works for me<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > On Thu, Jan 22, 2015 at 8:27 PM, Daniel Berlin <<br>
> > <a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a><br>
> > > wrote:<br>
> ><br>
> ><br>
> ><br>
> ><br>
> > We should use graph edges, so we can do something better at set<br>
> > build<br>
> > time :)<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > On Thu Jan 22 2015 at 5:20:46 PM George Burgess IV <<br>
> > <a href="mailto:george.burgess.iv@gmail.com">george.burgess.iv@gmail.com</a> > wrote:<br>
> ><br>
> ><br>
> ><br>
> ><br>
> > > Should we be added an edge from the inttoptr to all other pointer<br>
> > > values? Is there a better way?<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > We can add a special "Unknown" StratifiedAttr and query it before<br>
> > anything else, i.e:<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > // in CFLAliasAnalysis::query, as the first potential return<br>
> ><br>
> ><br>
> > if (AttrsA[AttrUnknown] || AttrsB[AttrUnknown])<br>
> ><br>
> ><br>
> > return MayAlias;<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > The only *potential* issue with this approach would be that in the<br>
> > following code segment:<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > void fn() {<br>
> ><br>
> ><br>
> > int *foo = (int*)rand();<br>
> ><br>
> ><br>
> > int *bar = new int;<br>
> ><br>
> ><br>
> > int **baz = rand() ? &foo : &bar;<br>
> ><br>
> ><br>
> > int value = **baz;<br>
> ><br>
> ><br>
> > }<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > The stratified sets would look like:<br>
> ><br>
> ><br>
> > {value} is below {foo, bar} is below {baz}.<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > Potential issue: The sets {foo, bar} and {value} would be marked<br>
> > with<br>
> > the "Unknown" attribute, while {baz} would have no attributes. I<br>
> > can't immediately think of a case where {baz} lacking "Unknown"<br>
> > would be harmful, but if such a case exists, then we may need a<br>
> > different approach.<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > George<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > On Thu, Jan 22, 2015 at 8:03 PM, Hal Finkel < <a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a> ><br>
> > wrote:<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > From: "Daniel Berlin" < <a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a> ><br>
> > To: "Hal Finkel" < <a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a> ><br>
> > Cc: "Jiangning Liu" < <a href="mailto:Jiangning.Liu@arm.com">Jiangning.Liu@arm.com</a> >, "George Burgess IV"<br>
> > <<br>
> > <a href="mailto:george.burgess.iv@gmail.com">george.burgess.iv@gmail.com</a> >, "LLVM Developers<br>
> > Mailing List" < <a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a> >, "Nick Lewycky" <<br>
> > <a href="mailto:nlewycky@google.com">nlewycky@google.com</a> ><br>
> > Sent: Wednesday, January 21, 2015 3:48:25 PM<br>
> > Subject: Re: [LLVMdev] question about enabling cfl-aa and<br>
> > collecting<br>
> > a57 numbers<br>
> ><br>
> > On Wed Jan 21 2015 at 12:30:50 PM Hal Finkel < <a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a> ><br>
> > wrote:<br>
> ><br>
> > ----- Original Message -----<br>
> > > From: "Daniel Berlin" < <a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a> ><br>
> > > To: "Hal Finkel" < <a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a> ><br>
> > > Cc: "Jiangning Liu" < <a href="mailto:Jiangning.Liu@arm.com">Jiangning.Liu@arm.com</a> >, "George Burgess<br>
> > > IV"<br>
> > > < <a href="mailto:george.burgess.iv@gmail.com">george.burgess.iv@gmail.com</a> >, "LLVM Developers<br>
> > > Mailing List" < <a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a> >, "Nick Lewycky" <<br>
> > > <a href="mailto:nlewycky@google.com">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<br>
> > delegation<br>
> > fixes from the others and commit as two separate patches<br>
> > (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 :)<br>
> ><br>
> ><br>
> > Okay, please do that and commit them.<br>
> ><br>
> ><br>
> ><br>
> ><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<br>
> > 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<br>
> > that<br>
> > points to nothing, it will just have an attribute that says<br>
> > "argument". :)<br>
> ><br>
> ><br>
> > Okay, fair enough.<br>
> ><br>
> ><br>
> ><br>
> ><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<br>
> > of<br>
> > inttoptr. We never do math, and the tracking we do is never going<br>
> > 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<br>
> > 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<br>
> > that<br>
> > interacts with them.<br>
> > We don't do that right now.<br>
> > We are just hiding it mildly well.<br>
> ><br>
> ><br>
> > Should we be added an edge from the inttoptr to all other pointer<br>
> > values? Is there a better way?<br>
> ><br>
> ><br>
> ><br>
> ><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<br>
> > 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<br>
> > are<br>
> > globals.<br>
> ><br>
> ><br>
> > It's effectively using Globals/Arguments as a way to say "don't<br>
> > 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).<br>
> ><br>
> ><br>
> > Okay, thanks!<br>
> ><br>
> ><br>
> ><br>
> ><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<br>
> > it<br>
> > to a separate fix (that includes fixes for the other<br>
> > argument/unknown related issues) if you like.<br>
> ><br>
> ><br>
> ><br>
> ><br>
> > Generically speaking, I'd prefer the fixes to be broken up as much<br>
> > as<br>
> > practical. Please go ahead and commit them.<br>
> ><br>
> > -Hal<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><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">hfinkel@anl.gov</a> ><br>
> > > wrote:<br>
> > ><br>
> > ><br>
> > > ----- Original Message -----<br>
> > > > From: "Daniel Berlin" < <a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a> ><br>
> > > > To: "Hal Finkel" < <a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a> ><br>
> > > > Cc: "Jiangning Liu" < <a href="mailto:Jiangning.Liu@arm.com">Jiangning.Liu@arm.com</a> >, "George Burgess<br>
> > > > IV"<br>
> > > > < <a href="mailto:george.burgess.iv@gmail.com">george.burgess.iv@gmail.com</a> >, "LLVM Developers<br>
> > > > Mailing List" < <a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a> >, "Nick Lewycky" <<br>
> > > > <a href="mailto:nlewycky@google.com">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<br>
> > > > tricky<br>
> > > > (it<br>
> > > > involves tracking some things, like GEP byte range, and then<br>
> > > > checking bases and using getObjectSize, much like BasicAA<br>
> > > > 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<br>
> > > 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<br>
> > > > PartialAlias,<br>
> > > > but<br>
> > > > this patch will at least get us to not be "giving wrong<br>
> > > > answers".<br>
> > > > I<br>
> > > > will also see if we catch anything with it that BasicAA does<br>
> > > > 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<br>
> > > 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<br>
> > > > *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">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">hfinkel@anl.gov</a> ><br>
> > > > wrote:<br>
> > > ><br>
> > > ><br>
> > > > ----- Original Message -----<br>
> > > > > From: "Daniel Berlin" < <a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a> ><br>
> > > > > To: "Hal Finkel" < <a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a> ><br>
> > > > > Cc: "Jiangning Liu" < <a href="mailto:Jiangning.Liu@arm.com">Jiangning.Liu@arm.com</a> >, "George<br>
> > > > > Burgess<br>
> > > > > IV"<br>
> > > > > < <a href="mailto:george.burgess.iv@gmail.com">george.burgess.iv@gmail.com</a> >, "LLVM Developers<br>
> > > > > Mailing List" < <a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a> >, "Nick Lewycky" <<br>
> > > > > <a href="mailto:nlewycky@google.com">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 <<br>
> > > > > <a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a><br>
> > > > > ><br>
> > > > > wrote:<br>
> > > > ><br>
> > > > ><br>
> > > > > Hi Danny,<br>
> > > > ><br>
> > > > > // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so<br>
> > > > > 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<br>
> > > > > 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<br>
> > > > 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<br>
> > > > 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<br>
> > > > 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.<br>
> > > > 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<br>
> > > > 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>
> > --<br>
> ><br>
> ><br>
> > Hal Finkel<br>
> > Assistant Computational Scientist<br>
> > Leadership Computing Facility<br>
> > Argonne National Laboratory<br>
> ><br>
> ><br>
> ><br>
> ><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>
</div></div></blockquote></div><br></div>