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

[Pete Cooper]

> On Jul 13, 2015, at 10:34 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. 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?
MergeGlobals creates new globals which could escape.  This is probably going to be treated differently from updating AA as there’s nothing tracking the new global yet, so nothing to update.  But still best to make sure this is ok.

Pete
> 
> 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.
> 
> -Hal
> 
>> Are you aware of any miscompiles that might be attributed
>> to this, or are these “theoretical" concerns?
>> 
>> -Chris
>> 
>> 
> 
> -- 
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev