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

[Xinliang David Li]

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>