[LLVMdev] AliasAnalysis update interface - a tale of sorrow and woe

[Hal Finkel]

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