<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Tue, Jul 14, 2015 at 9:07 PM Philip Reames <<a href="mailto:listmail@philipreames.com">listmail@philipreames.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>Chandler,<br>
<br>
Given you say explicitly that this only effects the LTO pipeline,
I was curious if you thought this is an issue that we could skip
past for the new pass manager work. Getting the normal
optimization pass manager - which doesn't have this issue -
working seems like a very reasonable first step. Even if we had
to add some hack to the old pass manager - like say, separating
out the problematic interface and making the few passes that use
it go through hoops to get to GlobalsModRef specifically as
opposed to any AA pass with the interface - that seems like a
worthwhile tradeoff. Would this type of approach work? Or am I
missing something?</div></div></blockquote><div><br></div><div>This is one of the other approaches I tried first. =/ It didn't work well.</div><div><br></div><div>The problem is that we use inheritance for all aspects of managing AA in LLVM today. It both serves as the tool for composing different aspects of AA, the tool for composing different AA passes, and as the common interface that the rest of the optimizer accepts on its interface boundaries. The problem I ran into with just leaving GlobalsModRef alone is that I need to change the interface that is threaded through the rest of the optimizer to be compatible with what the new PM uses.</div><div><br></div><div>I think it may be possible to do this by introducing some pretty horrible hacks in the AliasAnalysis base class that allow it to essentially behave as a shim for the new pass manager *or* as the integral part of the old pass manager. But I think that'll be pretty horrible, hard to craft, brittle, and might fall apart at any point as I'm going when I hit some aspect that breaks the trick. =/ So I'm hoping to not go this route if its at all possible.</div><div><br></div><div>Some early comments from folks in IRC benchmarking with GlobalsModRef are encouraging that it may not actually be a particularly problematic performance regression for any benchmarks to disable the broken bits here.</div><div><br></div><div>-Chandler</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000"><div><br>
<br>
Philip</div></div><div bgcolor="#FFFFFF" text="#000000"><div><br>
<br>
On 07/13/2015 08:19 PM, Chandler Carruth wrote:<br>
</div></div><div bgcolor="#FFFFFF" text="#000000"><blockquote type="cite">
<div dir="ltr">Ok folks,
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>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....</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>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!</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>So my plan is:</div>
<div><br>
</div>
<div>1) Fix obvious issues with GloblasModRef and switch it to
ValueHandles</div>
<div>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.</div>
<div>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)</div>
<div><br>
</div>
<div>Thoughts?</div>
<div>-Chandler</div>
</div>
<br>
<fieldset></fieldset>
<br>
</blockquote></div><div bgcolor="#FFFFFF" text="#000000"><blockquote type="cite"><pre>_______________________________________________
LLVM Developers mailing list
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a>
</pre>
</blockquote></div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" rel="noreferrer" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" rel="noreferrer" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote></div></div>