<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Mon, Jul 13, 2015 at 10:38 PM Hal Finkel <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">----- Original Message -----<br>
> From: "Chris Lattner" <<a href="mailto:clattner@apple.com" target="_blank">clattner@apple.com</a>><br>
> To: "Chandler Carruth" <<a href="mailto:chandlerc@gmail.com" target="_blank">chandlerc@gmail.com</a>><br>
> Cc: "LLVM Developers Mailing List" <<a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a>>, "Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>>, "Justin Bogner"<br>
> <<a href="mailto:mail@justinbogner.com" target="_blank">mail@justinbogner.com</a>>, "Duncan Exon Smith" <<a href="mailto:dexonsmith@apple.com" target="_blank">dexonsmith@apple.com</a>>, "Rafael Espíndola" <<a href="mailto:rafael.espindola@gmail.com" target="_blank">rafael.espindola@gmail.com</a>><br>
> Sent: Tuesday, July 14, 2015 12:18:36 AM<br>
> Subject: Re: [LLVMdev] GlobalsModRef (and thus LTO) is completely broken<br>
><br>
><br>
> > On Jul 13, 2015, at 8:19 PM, Chandler Carruth <<a href="mailto:chandlerc@gmail.com" target="_blank">chandlerc@gmail.com</a>><br>
> > wrote:<br>
> ><br>
> > Ok folks,<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>
> > Now, as to why I emailed this group of people and with this<br>
> > subject, the only pass pipeline that includes GlobalsModRef, is<br>
> > the LTO pipeline.<br>
><br>
> Ah, so it is just an LTO enabled benchmark hack then.<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>
> > a) If the two locations merely have a different *depth* of<br>
> > instruction stack, because GetUnderlyingObject has a recursion<br>
> > cap, one side can fail while the other succeeds, and we<br>
> > erroneously produce no-alias.<br>
><br>
> Interesting.  I’m sure it is no consolation, but GlobalsModRef<br>
> probably predated the recursion cap :-)<br>
><br>
> > b) If instcombine or any other pass for any reason introduces on<br>
> > one path an instruction that GetUnderlyingObject can't look<br>
> > through (select, phi, load, ....), we incorrectly conclude<br>
> > no-alias. This is what addEscapingUse was intended to solve, but<br>
> > we would literally have to call it from every pass because we<br>
> > can't rely on analysis invalidation!<br>
> ><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>
> Yep, all of these are pretty nasty.<br>
><br>
> > Now, as I argued in my general AA thread, I think we might be able<br>
> > to assume that (c) doesn't happen today. But both (a) and (b) seem<br>
> > like active nightmares to try to fix. I can see hacky ways to<br>
> > avoid (a) where we detect *why* GetUnderlyingObject fails, but I<br>
> > don't see how to fix both (a) and (b) (or to fix (a) well) without<br>
> > just disabling this specific aspect of GloblasModRef.<br>
><br>
> Ok, but we need performance information to make sure this doesn’t<br>
> cause a regression in practice for LTO builds.  For example, Spec 2K<br>
> and 2K6 are a reasonable place to start.<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<br>
> > put 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<br>
> > than bootstrap)<br>
><br>
> Sounds great if we can do this without causing a regression in<br>
> practice.<br>
<br>
Personally, I'm comfortable with moving to a contractual obligation for the escaping uses situation: No pass may capture the address of a (previously-uncaptured) global (even locally) without notifying the AA infrastructure.</blockquote><div><br></div><div>Note that I said escape, and you say capture here. I've not quite thought about it enough to generalize this to capture.</div><div><br></div><div>Anyways, I don't generally disagree (see my lengthier mail about how I'm envisioning AA updates). However, this is *not sufficient* to fix GloblasModRef. You also have to somehow prevent asymmetric evaluation of GetUnderlyingObject on the two pointers queried. To fix this would require a substantially different implementation of GlobalsModRef which I think is possible, but which I don't realistically have the time to implement right now.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I can't think of any in-tree pass that does this now, although we might certainly have some in the future. Can you think of any we have now?<br></blockquote><div><br></div><div>If you LTO the ASan runtime along with the instrumentation, then the instrumentation pass violates this today. Most instrumentation passes violate this if the optimizer can see the runtime.</div><div><br></div><div>I'm not aware of any non-instrumentation passes that violate it today.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
I'd really like to get the AA pass that Sam Parker has been working on (<a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__reviews.llvm.org_D10059&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=M5nKu3oFb7f5qZRKGWm6Pb9OP2gtZNAeIrYyoyZ3vZc&s=nYPLTVmQJnHSLYS89BP8njbHftKBK6ONGU7MXmtitzg&e=" rel="noreferrer" target="_blank">http://reviews.llvm.org/D10059</a>) in, but it will add measurable compile-time overhead if it can't cache, and efficient caching seems to depend on the same property.<br></blockquote><div><br></div><div>Sorry I haven't chimed in there. I'm worried that there is *no* sound way to do this in the current pass manager, but I'll read that patch and chime in with specific suggestions.</div><div><br></div><div>-Chandler</div></div></div>