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

[Hal Finkel]

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