(original) (raw)

----- Original Message -----
\> From: "Xinliang David Li" <xinliangli@gmail.com>
\> To: "Chandler Carruth" <chandlerc@gmail.com>
\> Cc: "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>, "Hal Finkel" <hfinkel@anl.gov>, "Justin Bogner"
\> <mail@justinbogner.com>, "Duncan Exon Smith" <dexonsmith@apple.com>, "Rafael Espíndola" <rafael.espindola@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@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@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