llvm dev - Jul 2015 - [LLVMdev] AliasAnalysis update interface - a tale of sorrow and woe

Greetings folks,

As I'm working on refactoring the AA interfaces in LLVM to prepare for the
new pass manager, I keep hitting issues. Some of the complexity that is
hitting this stems from the update API, which consists of three virtual
functions:

deleteValue(Value *V)
copyValue(Value *From, Value *To)
addEscapingUse(Use &U)

These interfaces are *very* rarely called. Here are the only passes that
ever bother to use these:
- MemoryDependenceAnalysis.cpp
- BasicBlockUtils.cpp
- LoopSimplify.cpp
- MergedLoadStoreMotion.cpp
- GVN.cpp

That's it. This is not a complete set of code that can delete a load or
store, nor a complete list of things which can fold something into a Phi
node or otherwise trigger an "escaping" use. Maybe these interfaces
used to
be much more widely used prior to the introduction of AliasSetTracker? Now
that utility is used instead. Either way, basic things like CSE,
store->load forwarding in instcombine, etc., all seem like they *should* be
updating AA, but they aren't....

So, if these update APIs are really important, I'm pretty sure that LLVM is
completely broken already...

But in fact, almost nothing overrides these APIs. The only pass in tree
that uses them at all is GlobalsModRef, which might explain why the world
hasn't melted due to us not calling these update routines reliably.

So I looked into GlobalsModRef to understand why it is overriding these. It
doesn't override copyValue at all. That API point appears to be completely
dead. So my first question is: can I remove copyValue? Is there some out of
tree user that desperately needs this? If so, I'd like to understand why.

The APIs it does override are deleteValue to nix things in its cache, and
addEscapingUse, which it implements by just deleting the used value from
its cache. This last one seems the most interesting. Only GVN calls it, but
GVN does call it. So I commented out the code in addEscapingUse so that it
became a no-op. No test failed. =/ So I added an assert to its
addEscapingUse method. No test failed. So I added a report_fatal_error to
the addEscapingUse method and did an LTO run over clang's bitcode which
finally did reach this code path.

addEscapingUse was added in 2011 by r122787 without any test case. There is
no mention of this fixing a bug. It looks like it may have been intended to
support something thata was never added to the tree.

So I'd like to remove addEscapingUse since we used to not have it, and
we've never bothered to test it and I can't get anything to fail without
it, and GlobalsModRef is the only user and that is only reached during LTO.
Thoughts?

My final question is deleteValue. Again, only GlobalsModRef implements this
extension point. This was added in 2006 in r30684, also without any changes
to any test. It claims to implement a test file, but that test isn't
changed in the commit. Indeed, commenting out the body of deleteValue in
GlobalsModRef causes no test to fail. =/ Fortunately, putting an assert
here *does* trip in the regression test suite, so the code is reached, just
not exercised.

Either way, the use case for the deleteValue at least makes perfect sense.
But there is (IMO) a much better way to accomplish the same task: use a
ValueHandle to trigger the update on deletion. This will prevent widespread
failure to use the deleteValue API to update alias analysis. So I would
like to replace deleteValue with a ValueHandle approach. But I'm  more than
a little nervous implementing this, *as no test actually uses the
behavior*! At least the code is reached...

I think generally, the update API in the AliasAnalysis interface isn't
working well. It is poorly and incompletely used. It isn't even clear that
it is necessary in the face of tools like value handles. Thoughts about
just removing the entire thing and falling back to value handles everywhere?

-Chandler
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150701/aa3395a3/attachment.html>

My opinion:

The interface is essentially broken and unused.
We know it doesn't work.
We should remove it.

Given that we need to sit down and think about stateful alias analysis
due to the new pass manager, it seems like a good time to do that.


On Wed, Jul 1, 2015 at 1:18 AM, Chandler Carruth <chandlerc at gmail.com>
wrote:
> Greetings folks,
>
> As I'm working on refactoring the AA interfaces in LLVM to prepare for
the
> new pass manager, I keep hitting issues. Some of the complexity that is
> hitting this stems from the update API, which consists of three virtual
> functions:
>
> deleteValue(Value *V)
> copyValue(Value *From, Value *To)
> addEscapingUse(Use &U)
>
> These interfaces are *very* rarely called. Here are the only passes that
> ever bother to use these:
> - MemoryDependenceAnalysis.cpp
> - BasicBlockUtils.cpp
> - LoopSimplify.cpp
> - MergedLoadStoreMotion.cpp
> - GVN.cpp
>
> That's it. This is not a complete set of code that can delete a load or
> store, nor a complete list of things which can fold something into a Phi
> node or otherwise trigger an "escaping" use. Maybe these
interfaces used to
> be much more widely used prior to the introduction of AliasSetTracker? Now
> that utility is used instead. Either way, basic things like CSE,
store->load
> forwarding in instcombine, etc., all seem like they *should* be updating
AA,
> but they aren't....
>
> So, if these update APIs are really important, I'm pretty sure that
LLVM is
> completely broken already...
>
> But in fact, almost nothing overrides these APIs. The only pass in tree
that
> uses them at all is GlobalsModRef, which might explain why the world
hasn't
> melted due to us not calling these update routines reliably.
>
> So I looked into GlobalsModRef to understand why it is overriding these. It
> doesn't override copyValue at all. That API point appears to be
completely
> dead. So my first question is: can I remove copyValue? Is there some out of
> tree user that desperately needs this? If so, I'd like to understand
why.
>
> The APIs it does override are deleteValue to nix things in its cache, and
> addEscapingUse, which it implements by just deleting the used value from
its
> cache. This last one seems the most interesting. Only GVN calls it, but GVN
> does call it. So I commented out the code in addEscapingUse so that it
> became a no-op. No test failed. =/ So I added an assert to its
> addEscapingUse method. No test failed. So I added a report_fatal_error to
> the addEscapingUse method and did an LTO run over clang's bitcode which
> finally did reach this code path.
>
> addEscapingUse was added in 2011 by r122787 without any test case. There is
> no mention of this fixing a bug. It looks like it may have been intended to
> support something thata was never added to the tree.
>
> So I'd like to remove addEscapingUse since we used to not have it, and
we've
> never bothered to test it and I can't get anything to fail without it,
and
> GlobalsModRef is the only user and that is only reached during LTO.
> Thoughts?
>
> My final question is deleteValue. Again, only GlobalsModRef implements this
> extension point. This was added in 2006 in r30684, also without any changes
> to any test. It claims to implement a test file, but that test isn't
changed
> in the commit. Indeed, commenting out the body of deleteValue in
> GlobalsModRef causes no test to fail. =/ Fortunately, putting an assert
here
> *does* trip in the regression test suite, so the code is reached, just not
> exercised.
>
> Either way, the use case for the deleteValue at least makes perfect sense.
> But there is (IMO) a much better way to accomplish the same task: use a
> ValueHandle to trigger the update on deletion. This will prevent widespread
> failure to use the deleteValue API to update alias analysis. So I would
like
> to replace deleteValue with a ValueHandle approach. But I'm  more than
a
> little nervous implementing this, *as no test actually uses the behavior*!
> At least the code is reached...
>
> I think generally, the update API in the AliasAnalysis interface isn't
> working well. It is poorly and incompletely used. It isn't even clear
that
> it is necessary in the face of tools like value handles. Thoughts about
just
> removing the entire thing and falling back to value handles everywhere?
>
> -Chandler
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

----- Original Message -----
> From: "Daniel Berlin" <dberlin at dberlin.org>
> To: "Chandler Carruth" <chandlerc at gmail.com>
> Cc: "LLVM Developers Mailing List" <llvmdev at
cs.uiuc.edu>, "Hal Finkel" <hfinkel at anl.gov>, "Daniel
Berlin"
> <dannyb at google.com>
> Sent: Wednesday, July 1, 2015 11:31:49 AM
> Subject: Re: [LLVMdev] AliasAnalysis update interface - a tale of sorrow
and woe
> 
> My opinion:
> 
> The interface is essentially broken and unused.
> We know it doesn't work.
> We should remove it.
> 
> Given that we need to sit down and think about stateful alias
> analysis
> due to the new pass manager, it seems like a good time to do that.
+1

 -Hal
> 
> 
> On Wed, Jul 1, 2015 at 1:18 AM, Chandler Carruth
> <chandlerc at gmail.com> wrote:
> > Greetings folks,
> >
> > As I'm working on refactoring the AA interfaces in LLVM to prepare
> > for the
> > new pass manager, I keep hitting issues. Some of the complexity
> > that is
> > hitting this stems from the update API, which consists of three
> > virtual
> > functions:
> >
> > deleteValue(Value *V)
> > copyValue(Value *From, Value *To)
> > addEscapingUse(Use &U)
> >
> > These interfaces are *very* rarely called. Here are the only passes
> > that
> > ever bother to use these:
> > - MemoryDependenceAnalysis.cpp
> > - BasicBlockUtils.cpp
> > - LoopSimplify.cpp
> > - MergedLoadStoreMotion.cpp
> > - GVN.cpp
> >
> > That's it. This is not a complete set of code that can delete a
> > load or
> > store, nor a complete list of things which can fold something into
> > a Phi
> > node or otherwise trigger an "escaping" use. Maybe these
interfaces
> > used to
> > be much more widely used prior to the introduction of
> > AliasSetTracker? Now
> > that utility is used instead. Either way, basic things like CSE,
> > store->load
> > forwarding in instcombine, etc., all seem like they *should* be
> > updating AA,
> > but they aren't....
> >
> > So, if these update APIs are really important, I'm pretty sure
that
> > LLVM is
> > completely broken already...
> >
> > But in fact, almost nothing overrides these APIs. The only pass in
> > tree that
> > uses them at all is GlobalsModRef, which might explain why the
> > world hasn't
> > melted due to us not calling these update routines reliably.
> >
> > So I looked into GlobalsModRef to understand why it is overriding
> > these. It
> > doesn't override copyValue at all. That API point appears to be
> > completely
> > dead. So my first question is: can I remove copyValue? Is there
> > some out of
> > tree user that desperately needs this? If so, I'd like to
> > understand why.
> >
> > The APIs it does override are deleteValue to nix things in its
> > cache, and
> > addEscapingUse, which it implements by just deleting the used value
> > from its
> > cache. This last one seems the most interesting. Only GVN calls it,
> > but GVN
> > does call it. So I commented out the code in addEscapingUse so that
> > it
> > became a no-op. No test failed. =/ So I added an assert to its
> > addEscapingUse method. No test failed. So I added a
> > report_fatal_error to
> > the addEscapingUse method and did an LTO run over clang's bitcode
> > which
> > finally did reach this code path.
> >
> > addEscapingUse was added in 2011 by r122787 without any test case.
> > There is
> > no mention of this fixing a bug. It looks like it may have been
> > intended to
> > support something thata was never added to the tree.
> >
> > So I'd like to remove addEscapingUse since we used to not have it,
> > and we've
> > never bothered to test it and I can't get anything to fail without
> > it, and
> > GlobalsModRef is the only user and that is only reached during LTO.
> > Thoughts?
> >
> > My final question is deleteValue. Again, only GlobalsModRef
> > implements this
> > extension point. This was added in 2006 in r30684, also without any
> > changes
> > to any test. It claims to implement a test file, but that test
> > isn't changed
> > in the commit. Indeed, commenting out the body of deleteValue in
> > GlobalsModRef causes no test to fail. =/ Fortunately, putting an
> > assert here
> > *does* trip in the regression test suite, so the code is reached,
> > just not
> > exercised.
> >
> > Either way, the use case for the deleteValue at least makes perfect
> > sense.
> > But there is (IMO) a much better way to accomplish the same task:
> > use a
> > ValueHandle to trigger the update on deletion. This will prevent
> > widespread
> > failure to use the deleteValue API to update alias analysis. So I
> > would like
> > to replace deleteValue with a ValueHandle approach. But I'm  more
> > than a
> > little nervous implementing this, *as no test actually uses the
> > behavior*!
> > At least the code is reached...
> >
> > I think generally, the update API in the AliasAnalysis interface
> > isn't
> > working well. It is poorly and incompletely used. It isn't even
> > clear that
> > it is necessary in the face of tools like value handles. Thoughts
> > about just
> > removing the entire thing and falling back to value handles
> > everywhere?
> >
> > -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

----- Original Message -----
> From: "Chandler Carruth" <chandlerc at gmail.com>
> To: "LLVM Developers Mailing List" <llvmdev at
cs.uiuc.edu>, "Hal Finkel" <hfinkel at anl.gov>, "Daniel
Berlin"
> <dannyb at google.com>
> Sent: Wednesday, July 1, 2015 3:18:33 AM
> Subject: AliasAnalysis update interface - a tale of sorrow and woe
> 
> 
> Greetings folks,
> 
> 
> As I'm working on refactoring the AA interfaces in LLVM to prepare
> for the new pass manager, I keep hitting issues. Some of the
> complexity that is hitting this stems from the update API, which
> consists of three virtual functions:
> 
> 
> deleteValue(Value *V)
> copyValue(Value *From, Value *To)
> addEscapingUse(Use &U)
> 
> 
> These interfaces are *very* rarely called. Here are the only passes
> that ever bother to use these:
> - MemoryDependenceAnalysis.cpp
> - BasicBlockUtils.cpp
> - LoopSimplify.cpp
> - MergedLoadStoreMotion.cpp
> - GVN.cpp
> 
> 
> That's it. This is not a complete set of code that can delete a load
> or store, nor a complete list of things which can fold something
> into a Phi node or otherwise trigger an "escaping" use. Maybe
these
> interfaces used to be much more widely used prior to the
> introduction of AliasSetTracker? Now that utility is used instead.
> Either way, basic things like CSE, store->load forwarding in
> instcombine, etc., all seem like they *should* be updating AA, but
> they aren't....
> 
> 
> So, if these update APIs are really important, I'm pretty sure that
> LLVM is completely broken already...
> 
> 
> But in fact, almost nothing overrides these APIs. The only pass in
> tree that uses them at all is GlobalsModRef, which might explain why
> the world hasn't melted due to us not calling these update routines
> reliably.
> 
> 
> So I looked into GlobalsModRef to understand why it is overriding
> these. It doesn't override copyValue at all. That API point appears
> to be completely dead. So my first question is: can I remove
> copyValue? Is there some out of tree user that desperately needs
> this? If so, I'd like to understand why.
> 
> 
> The APIs it does override are deleteValue to nix things in its cache,
> and addEscapingUse, which it implements by just deleting the used
> value from its cache. This last one seems the most interesting. Only
> GVN calls it, but GVN does call it. So I commented out the code in
> addEscapingUse so that it became a no-op. No test failed. =/ So I
> added an assert to its addEscapingUse method. No test failed. So I
> added a report_fatal_error to the addEscapingUse method and did an
> LTO run over clang's bitcode which finally did reach this code path.
> 
> 
> addEscapingUse was added in 2011 by r122787 without any test case.
> There is no mention of this fixing a bug. It looks like it may have
> been intended to support something thata was never added to the
> tree.
> 
> 
> So I'd like to remove addEscapingUse since we used to not have it,
> and we've never bothered to test it and I can't get anything to
fail
> without it, and GlobalsModRef is the only user and that is only
> reached during LTO. Thoughts?
> 
> 
> My final question is deleteValue. Again, only GlobalsModRef
> implements this extension point. This was added in 2006 in r30684,
> also without any changes to any test. It claims to implement a test
> file, but that test isn't changed in the commit. Indeed, commenting
> out the body of deleteValue in GlobalsModRef causes no test to fail.
> =/ Fortunately, putting an assert here *does* trip in the regression
> test suite, so the code is reached, just not exercised.
> 
> 
> Either way, the use case for the deleteValue at least makes perfect
> sense. But there is (IMO) a much better way to accomplish the same
> task: use a ValueHandle to trigger the update on deletion. This will
> prevent widespread failure to use the deleteValue API to update
> alias analysis. So I would like to replace deleteValue with a
> ValueHandle approach. But I'm more than a little nervous
> implementing this, *as no test actually uses the behavior*! At least
> the code is reached...
> 
> 
> I think generally, the update API in the AliasAnalysis interface
> isn't working well. It is poorly and incompletely used. It isn't
> even clear that it is necessary in the face of tools like value
> handles. Thoughts about just removing the entire thing and falling
> back to value handles everywhere?
As a side point, I don't think we currently have a ValueHandle type that can
detect when a new use of a value is added. Do we? This would certainly be useful
for some kind of AA result caching, etc.

 -Hal
> 
> 
> -Chandler
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

----- Original Message -----
> From: "Hal Finkel" <hfinkel at anl.gov>
> To: "Chandler Carruth" <chandlerc at gmail.com>
> Cc: "LLVM Developers Mailing List" <llvmdev at
cs.uiuc.edu>, "Daniel Berlin" <dannyb at google.com>
> Sent: Thursday, July 2, 2015 3:14:38 PM
> Subject: Re: AliasAnalysis update interface - a tale of sorrow and woe
> 
> ----- Original Message -----
> > From: "Chandler Carruth" <chandlerc at gmail.com>
> > To: "LLVM Developers Mailing List" <llvmdev at
cs.uiuc.edu>, "Hal
> > Finkel" <hfinkel at anl.gov>, "Daniel Berlin"
> > <dannyb at google.com>
> > Sent: Wednesday, July 1, 2015 3:18:33 AM
> > Subject: AliasAnalysis update interface - a tale of sorrow and woe
> > 
> > 
> > Greetings folks,
> > 
> > 
> > As I'm working on refactoring the AA interfaces in LLVM to prepare
> > for the new pass manager, I keep hitting issues. Some of the
> > complexity that is hitting this stems from the update API, which
> > consists of three virtual functions:
> > 
> > 
> > deleteValue(Value *V)
> > copyValue(Value *From, Value *To)
> > addEscapingUse(Use &U)
> > 
> > 
> > These interfaces are *very* rarely called. Here are the only passes
> > that ever bother to use these:
> > - MemoryDependenceAnalysis.cpp
> > - BasicBlockUtils.cpp
> > - LoopSimplify.cpp
> > - MergedLoadStoreMotion.cpp
> > - GVN.cpp
> > 
> > 
> > That's it. This is not a complete set of code that can delete a
> > load
> > or store, nor a complete list of things which can fold something
> > into a Phi node or otherwise trigger an "escaping" use.
Maybe these
> > interfaces used to be much more widely used prior to the
> > introduction of AliasSetTracker? Now that utility is used instead.
> > Either way, basic things like CSE, store->load forwarding in
> > instcombine, etc., all seem like they *should* be updating AA, but
> > they aren't....
> > 
> > 
> > So, if these update APIs are really important, I'm pretty sure
that
> > LLVM is completely broken already...
> > 
> > 
> > But in fact, almost nothing overrides these APIs. The only pass in
> > tree that uses them at all is GlobalsModRef, which might explain
> > why
> > the world hasn't melted due to us not calling these update
routines
> > reliably.
> > 
> > 
> > So I looked into GlobalsModRef to understand why it is overriding
> > these. It doesn't override copyValue at all. That API point
appears
> > to be completely dead. So my first question is: can I remove
> > copyValue? Is there some out of tree user that desperately needs
> > this? If so, I'd like to understand why.
> > 
> > 
> > The APIs it does override are deleteValue to nix things in its
> > cache,
> > and addEscapingUse, which it implements by just deleting the used
> > value from its cache. This last one seems the most interesting.
> > Only
> > GVN calls it, but GVN does call it. So I commented out the code in
> > addEscapingUse so that it became a no-op. No test failed. =/ So I
> > added an assert to its addEscapingUse method. No test failed. So I
> > added a report_fatal_error to the addEscapingUse method and did an
> > LTO run over clang's bitcode which finally did reach this code
> > path.
> > 
> > 
> > addEscapingUse was added in 2011 by r122787 without any test case.
> > There is no mention of this fixing a bug. It looks like it may have
> > been intended to support something thata was never added to the
> > tree.
> > 
> > 
> > So I'd like to remove addEscapingUse since we used to not have it,
> > and we've never bothered to test it and I can't get anything
to
> > fail
> > without it, and GlobalsModRef is the only user and that is only
> > reached during LTO. Thoughts?
> > 
> > 
> > My final question is deleteValue. Again, only GlobalsModRef
> > implements this extension point. This was added in 2006 in r30684,
> > also without any changes to any test. It claims to implement a test
> > file, but that test isn't changed in the commit. Indeed,
commenting
> > out the body of deleteValue in GlobalsModRef causes no test to
> > fail.
> > =/ Fortunately, putting an assert here *does* trip in the
> > regression
> > test suite, so the code is reached, just not exercised.
> > 
> > 
> > Either way, the use case for the deleteValue at least makes perfect
> > sense. But there is (IMO) a much better way to accomplish the same
> > task: use a ValueHandle to trigger the update on deletion. This
> > will
> > prevent widespread failure to use the deleteValue API to update
> > alias analysis. So I would like to replace deleteValue with a
> > ValueHandle approach. But I'm more than a little nervous
> > implementing this, *as no test actually uses the behavior*! At
> > least
> > the code is reached...
> > 
> > 
> > I think generally, the update API in the AliasAnalysis interface
> > isn't working well. It is poorly and incompletely used. It
isn't
> > even clear that it is necessary in the face of tools like value
> > handles. Thoughts about just removing the entire thing and falling
> > back to value handles everywhere?
> 
> As a side point, I don't think we currently have a ValueHandle type
> that can detect when a new use of a value is added. Do we? This
> would certainly be useful for some kind of AA result caching, etc.
I should add that I'm somewhat afraid, however, of the compile-time
implications of adding the necessary hook.

 -Hal
> 
>  -Hal
> 
> > 
> > 
> > -Chandler
> 
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory