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

[Philip Reames]

On 07/01/2015 09:37 AM, Hal Finkel wrote:
> ----- 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
+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
>>>