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

Hal Finkel hfinkel at anl.gov
Tue Jul 14 11:53:08 PDT 2015

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

More information about the llvm-dev mailing list