llvm dev - Jul 2015 - [LLVMdev] GlobalsModRef (and thus LTO) is completely broken

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.

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.

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150714/bb968247/attachment.html>

> 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.  Are
you aware of any miscompiles that might be attributed to this, or are these
“theoretical" concerns?

-Chris

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

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

On Mon, Jul 13, 2015 at 10:21 PM Chris Lattner <clattner at apple.com>
wrote:
>
> > 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.
> Are you aware of any miscompiles that might be attributed to this, or are
> these “theoretical" concerns?
>
I don't really have any way of benchmarking SPEC with LTO. If that's a
configuration that is super important to people, I'm hoping they'll let
me
know about any particular performance issues.

Ultimately, I'm happy making no performance impacting changes here. The
thing is, I need to remove a broken abstraction (addEscapingUse) that was
half-way added without any test case (literally, I have no test case that
fails if I delete it. The regression tests don't fail if I assert(0) in
it). =/ I don't want to do that if it causes miscompiles for folks that
*are* relying on LTO. So my plan is to essentially post the patch that will
fix the miscompiles but may regress performance. If the miscompiles show up
for those relying on LTO and this (somewhat unsound) pass, they are in the
best position to evaluate the cost/benefit of a performance reducing patch.

Honsetly, my hope is that it won't even impact performance. But I have no
realistic way to measure it in any useful way. And for *my* platforms, I
would be perfectly happy to trade some performance for correctness here.
That's one of the reasons we're not relying on LTO yet. But I understand
that others in the community have more strict performance needs and so I'm
doing what I can to give them options.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150714/2ca6df08/attachment.html>

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?


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


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


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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150714/414f3128/attachment.html>

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

Chandler,

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?

Philip

On 07/13/2015 08:19 PM, Chandler Carruth 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.
>
> 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.
>
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150714/4b110b45/attachment.html>

On Tue, Jul 14, 2015 at 9:07 PM Philip Reames <listmail at
philipreames.com>
wrote:
>  Chandler,
>
> 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?
>
This is one of the other approaches I tried first. =/ It didn't work well.

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.

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.

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.

-Chandler

>
>
> Philip
>
>
> On 07/13/2015 08:19 PM, Chandler Carruth 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.
>
>  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.
>
>  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 listLLVMdev at cs.uiuc.edu        
http://llvm.cs.uiuc.eduhttp://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>  _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150715/dabb5f38/attachment.html>