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

[Hal Finkel]

----- Original Message -----
> From: "Chandler Carruth" <chandlerc at google.com>
> To: "Hal Finkel" <hfinkel at anl.gov>, "Chris Lattner" <clattner at apple.com>
> Cc: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>
> Sent: Tuesday, July 14, 2015 12:55:37 AM
> Subject: Re: [LLVMdev] GlobalsModRef (and thus LTO) is completely broken
> 
> 
> 
> 
> On Mon, Jul 13, 2015 at 10:38 PM Hal Finkel < hfinkel at anl.gov >
> wrote:
> 
> 
> ----- Original Message -----
> > From: "Chris Lattner" < clattner at apple.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:18:36 AM
> > Subject: Re: [LLVMdev] GlobalsModRef (and thus LTO) is completely
> > broken
> > 
> > 
> > > On 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.
> > 
> > Ah, so it is just an LTO enabled benchmark hack then.
> > 
> > > 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.
> > 
> > Interesting. I’m sure it is no consolation, but GlobalsModRef
> > probably predated the recursion cap :-)
> > 
> > > 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!
> > > 
> > > 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.
> > 
> > Yep, all of these are pretty nasty.
> > 
> > > 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.
> > 
> > Ok, but we need performance information to make sure this doesn’t
> > cause a regression in practice for LTO builds. For example, Spec 2K
> > and 2K6 are a reasonable place to start.
> > 
> > > 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)
> > 
> > Sounds great if we can do this without causing a regression in
> > practice.
> 
> 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.
> 
> 
> Note that I said escape, and you say capture here.

That was intentional. The problem is that I think you need to pick up all captures for a reasonably-general case, because otherwise you need separate logic to handle local queries. If you think that some local variable can't alias some global because you *know* that the global's address has not been captured, then you need to know if you generate a new local capture.

> I've not quite
> thought about it enough to generalize this to capture.
> 
> 
> 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.
> 

You can turn off the depth limit on GetUnderlyingObject.

> 
> 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?
> 
> 
> 
> 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.
> 
> 
> I'm not aware of any non-instrumentation passes that violate it
> today.
> 

Okay, fair enough. Updating those passes to invalidate something in this regard seems manageable.

> 
> 
> I'd really like to get the AA pass that Sam Parker has been working
> on ( http://reviews.llvm.org/D10059 ) in, but it will add measurable
> compile-time overhead if it can't cache, and efficient caching seems
> to depend on the same property.
> 
> 
> 
> 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.

Thanks!

 -Hal

> 
> 
> -Chandler

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory