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

[Hal Finkel]

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