<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jul 14, 2015 at 11:53 AM, 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: "Xinliang David Li" <<a href="mailto:xinliangli@gmail.com">xinliangli@gmail.com</a>><br>
> To: "Chandler Carruth" <<a href="mailto:chandlerc@gmail.com">chandlerc@gmail.com</a>><br>
> Cc: "LLVM Developers Mailing List" <<a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a>>, "Hal Finkel" <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>>, "Justin Bogner"<br>
> <<a href="mailto:mail@justinbogner.com">mail@justinbogner.com</a>>, "Duncan Exon Smith" <<a href="mailto:dexonsmith@apple.com">dexonsmith@apple.com</a>>, "Rafael Espíndola" <<a href="mailto:rafael.espindola@gmail.com">rafael.espindola@gmail.com</a>><br>
</span><span class="">> Sent: Tuesday, July 14, 2015 12:59:29 PM<br>
> Subject: Re: [LLVMdev] GlobalsModRef (and thus LTO) is completely broken<br>
><br>
><br>
><br>
><br>
><br>
><br>
</span><div><div class="h5">> On Mon, Jul 13, 2015 at 8:19 PM, Chandler Carruth <<br>
> <a href="mailto:chandlerc@gmail.com">chandlerc@gmail.com</a> > wrote:<br>
><br>
><br>
><br>
> Ok folks,<br>
><br>
><br>
> I wrote up the general high-level thoughts I have about stateful AA<br>
> in a separate thread. But we need to sort out the completely and<br>
> horribly broken aspects of GlobalsModRef today, and the practical<br>
> steps forward. This email is totally about the practical stuff.<br>
><br>
><br>
> Now, as to why I emailed this group of people and with this subject,<br>
> the only pass pipeline that includes GlobalsModRef, is the LTO<br>
> pipeline. So we have significantly less testing here than we do for<br>
> stuff in the main pipeline. Also, I don't have any benchmarks I can<br>
> effectively run to tell me if my changes impacted performance. =/ So<br>
> I may need your help to evaluate some of this. Now, onto the<br>
> challenges....<br>
><br>
><br>
> First, GlobalsModRef as currently implemented completely abuses a<br>
> loophole in the current pass manager to incorrectly stick around<br>
> even while it is being "invalidated". I don't know of any way to fix<br>
> this in the current pass manager without completely defeating the<br>
> purpose of the analysis pass. The consequence is that whether passes<br>
> claim to preserve AA or not is irrelevant, GlobalsModRef will be<br>
> preserved anyways! =[[[[ So the only way to make things work<br>
> correctly is to make GlobalsModRef survive *any* per-function<br>
> changes to the IR. We cannot rely on AA updates at all.<br>
><br>
><br>
> Most of the updates that GlobalsModRef needs can be provided by a<br>
> ValueHandle now that we have them. This will prevent ABA-style<br>
> issues in its caches, etc. I plan to send out a patch soon that<br>
> switches it over to this strategy.<br>
><br>
><br>
> It is also relying on a precomputed set of global variables whose<br>
> address is never used by an instruction other than some very small<br>
> set (gep, bitcast) as "non-address-taken". It then runs<br>
> GetUnderlyingObject on the two pointers in alias queries, and if<br>
> that finds one of these "non-address-taken" globals for one of the<br>
> memory locations but not the other, it concludes no-alias! This is<br>
> broken for a number of reasons.<br>
><br>
><br>
> a) If the two locations merely have a different *depth* of<br>
> instruction stack, because GetUnderlyingObject has a recursion cap,<br>
> one side can fail while the other succeeds, and we erroneously<br>
> produce no-alias.<br>
><br>
><br>
> How about adding an optional argument to the interface to ignore<br>
> limit?<br>
><br>
<br>
</div></div>We have this already.<br>
<span class=""><br>
><br>
> b) If instcombine or any other pass for any reason introduces on one<br>
> path an instruction that GetUnderlyingObject can't look through<br>
> (select, phi, load, ....), we incorrectly conclude no-alias. This is<br>
> what addEscapingUse was intended to solve, but we would literally<br>
> have to call it from every pass because we can't rely on analysis<br>
> invalidation!<br>
><br>
><br>
><br>
><br>
> I am not sure if this matters. If a pointer is loaded from the<br>
> memory, then either pointer points to heap or the the underlying<br>
> object is address taken. For the phi case, I wonder what<br>
> transformation can introduce it while the original source construct<br>
> does not escape/addr-take the global already.<br>
><br>
<br>
</span>The problem is determining whether both pointers derive from the same global. For that, you need to track dependencies through loads/stores. You could, however, just give up on those cases.<br>
<span class=""><br></span></blockquote><div><br></div><div>My point is that if access-1 has untractable/unanalyzable access pattern involving load, it can not possibly come from a non-address taken global variable.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">
><br>
> c) If any pass actually escapes a pointer from one function into<br>
> another, we invalidate the underlying assumption of<br>
> 'non-address-taken' that it relies upon.<br>
><br>
><br>
> This can probably happen with function outlining etc.<br>
<br>
</span>Yes, exactly (and this is why I said we'd likely have such things in the future). As Chandler pointed out, our instrumentation passes already do this as well.<br>
<span class="HOEnZb"><font color="#888888"><br></font></span></blockquote><div><br></div><div><br></div><div>yes, tsan does that -- however LTOing instrumented program together with runtime library source is a very unlikely scenario though.</div><div><br></div><div>David</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="HOEnZb"><font color="#888888">
 -Hal<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
><br>
> thanks,<br>
><br>
><br>
><br>
><br>
> David<br>
><br>
><br>
><br>
><br>
><br>
><br>
> Now, as I argued in my general AA thread, I think we might be able to<br>
> assume that (c) doesn't happen today. But both (a) and (b) seem like<br>
> active nightmares to try to fix. I can see hacky ways to avoid (a)<br>
> where we detect *why* GetUnderlyingObject fails, but I don't see how<br>
> to fix both (a) and (b) (or to fix (a) well) without just disabling<br>
> this specific aspect of GloblasModRef.<br>
><br>
><br>
> So that's what I'd like to do. It shouldn't impact the mod/ref<br>
> information provided by the analysis, just the alias sets.<br>
><br>
><br>
> However, even this may not be necessary. We may just not in practice<br>
> see these issues, and I don't really want to perturb the LTO<br>
> generated code quality for a hypothetical issue until we actually<br>
> have the tools in place to handle things reasonably.<br>
><br>
><br>
> So my plan is:<br>
><br>
><br>
> 1) Fix obvious issues with GloblasModRef and switch it to<br>
> ValueHandles<br>
> 2) Mail out a patch to disable this part of GlobalsModRef. I can put<br>
> it behind a flag or however folks would like it to work.<br>
> 3) Remove addEscapingUse() update API, which without #2 may regress<br>
> some LTO test case I don't have (because I don't have any other than<br>
> bootstrap)<br>
><br>
><br>
> Thoughts?<br>
> -Chandler<br>
> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" rel="noreferrer" target="_blank">http://llvm.cs.uiuc.edu</a><br>
> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" rel="noreferrer" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
><br>
><br>
><br>
<br>
</div></div><div class="HOEnZb"><div class="h5">--<br>
Hal Finkel<br>
Assistant Computational Scientist<br>
Leadership Computing Facility<br>
Argonne National Laboratory<br>
</div></div></blockquote></div><br></div></div>