[LLVMdev] GlobalsModRef (and thus LTO) is completely broken (original) (raw)

Xinliang David Li xinliangli at gmail.com
Tue Jul 14 12:36:51 PDT 2015

On Tue, Jul 14, 2015 at 11:53 AM, Hal Finkel <hfinkel at anl.gov> wrote:

----- Original Message ----- > From: "Xinliang David Li" <xinliangli at gmail.com> > To: "Chandler Carruth" <chandlerc at gmail.com> > Cc: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>, "Hal Finkel" <_ _hfinkel at anl.gov>, "Justin Bogner" > <mail at justinbogner.com>, "Duncan Exon Smith" <dexonsmith at apple.com>, "Rafael Espíndola" <rafael.espindola at gmail.com> > Sent: Tuesday, July 14, 2015 12:59:29 PM > Subject: Re: [LLVMdev] GlobalsModRef (and thus LTO) is completely broken > > > > > > > On Mon, Jul 13, 2015 at 8:19 PM, Chandler Carruth <_ _> chandlerc at gmail.com > wrote: > > > > Ok folks, > > > I wrote up the general high-level thoughts I have about stateful AA > in a separate thread. But we need to sort out the completely and > horribly broken aspects of GlobalsModRef today, and the practical > steps forward. This email is totally about the practical stuff. > > > Now, as to why I emailed this group of people and with this subject, > the only pass pipeline that includes GlobalsModRef, is the LTO > pipeline. So we have significantly less testing here than we do for > stuff in the main pipeline. Also, I don't have any benchmarks I can > effectively run to tell me if my changes impacted performance. =/ So > I may need your help to evaluate some of this. Now, onto the > challenges.... > > > First, GlobalsModRef as currently implemented completely abuses a > loophole in the current pass manager to incorrectly stick around > even while it is being "invalidated". I don't know of any way to fix > this in the current pass manager without completely defeating the > purpose of the analysis pass. The consequence is that whether passes > claim to preserve AA or not is irrelevant, GlobalsModRef will be > preserved anyways! =[[[[ So the only way to make things work > correctly is to make GlobalsModRef survive any per-function > changes to the IR. We cannot rely on AA updates at all. > > > Most of the updates that GlobalsModRef needs can be provided by a > ValueHandle now that we have them. This will prevent ABA-style > issues in its caches, etc. I plan to send out a patch soon that > switches it over to this strategy. > > > It is also relying on a precomputed set of global variables whose > address is never used by an instruction other than some very small > set (gep, bitcast) as "non-address-taken". It then runs > GetUnderlyingObject on the two pointers in alias queries, and if > that finds one of these "non-address-taken" globals for one of the > memory locations but not the other, it concludes no-alias! This is > broken for a number of reasons. > > > a) If the two locations merely have a different depth of > instruction stack, because GetUnderlyingObject has a recursion cap, > one side can fail while the other succeeds, and we erroneously > produce no-alias. > > > How about adding an optional argument to the interface to ignore > limit? >

We have this already. > > b) If instcombine or any other pass for any reason introduces on one > path an instruction that GetUnderlyingObject can't look through > (select, phi, load, ....), we incorrectly conclude no-alias. This is > what addEscapingUse was intended to solve, but we would literally > have to call it from every pass because we can't rely on analysis > invalidation! > > > > > I am not sure if this matters. If a pointer is loaded from the > memory, then either pointer points to heap or the the underlying > object is address taken. For the phi case, I wonder what > transformation can introduce it while the original source construct > does not escape/addr-take the global already. > 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. 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.

> c) If any pass actually escapes a pointer from one function into > another, we invalidate the underlying assumption of > 'non-address-taken' that it relies upon. > > > This can probably happen with function outlining etc. 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.

yes, tsan does that -- however LTOing instrumented program together with runtime library source is a very unlikely scenario though.

David

-Hal

> > thanks, > > > > > David > > > > > > > Now, as I argued in my general AA thread, I think we might be able to > assume that (c) doesn't happen today. But both (a) and (b) seem like > active nightmares to try to fix. I can see hacky ways to avoid (a) > where we detect why GetUnderlyingObject fails, but I don't see how > to fix both (a) and (b) (or to fix (a) well) without just disabling > this specific aspect of GloblasModRef. > > > So that's what I'd like to do. It shouldn't impact the mod/ref > information provided by the analysis, just the alias sets. > > > However, even this may not be necessary. We may just not in practice > see these issues, and I don't really want to perturb the LTO > generated code quality for a hypothetical issue until we actually > have the tools in place to handle things reasonably. > > > So my plan is: > > > 1) Fix obvious issues with GloblasModRef and switch it to > ValueHandles > 2) Mail out a patch to disable this part of GlobalsModRef. I can put > it behind a flag or however folks would like it to work. > 3) Remove addEscapingUse() update API, which without #2 may regress > some LTO test case I don't have (because I don't have any other than > bootstrap) > > > Thoughts? > -Chandler _> ________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > -- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150714/4b3ad2ac/attachment.html>

More information about the llvm-dev mailing list