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

[Hal Finkel]

----- 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.

> 
> 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.

 -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