This is an archive of the discontinued LLVM Phabricator instance.

[Attributor][WIP] Implement AAReachability
Needs ReviewPublic

Authored by okura on Jul 27 2020, 8:33 AM.

Details

Summary

Currently, AAReachability does not compute anything and only use isPotentiallyReachable.
This patch makes it possible for AAReachability to use liveness information from AAIsDead.
In AAReachability::updateImpl, we collect reachable successor basic blocks for each basic block and construct a graph.
When reachability between two instructions is queried, check it using the graph.

Diff Detail

Event Timeline

okura created this revision.Jul 27 2020, 8:33 AM
Herald added a reviewer: uenoku. · View Herald Transcript
Herald added a reviewer: homerdin. · View Herald Transcript
Herald added a reviewer: baziotis. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript
jdoerfert added inline comments.Jul 27 2020, 10:36 AM
llvm/test/Transforms/Attributor/noalias.ll
919

Make an NFC pre-commit with the tests and "old" check lines. That makes it clear in this patch what changed. Just commit the test without additional review.

okura updated this revision to Diff 281009.Jul 27 2020, 12:07 PM
  • add missing override
  • add tests in another commit

Thanks for working on this! Reachability should be used more and with an actual optimistic implementation it makes sense. The next user (in addition to AANoAlias) could be value simplification, for load/store simplification. Similarly to the noalias case we can preserve other properties for a program point if it is not reachable from all potential violations (I am thinking a use of a dereferenceable argument that cannot be reached from a function call that is not nofree. This makes sense once we split dereferenceable_globally from dereferenceable.) Let's get this in first though ;)

Below some comments.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp
3462

This seems odd. If there is no reason for this version let's remove both initialize methods.

3467

Also not needed as far as I can tell.

3481–3484
3533

This looks like the AAIsDead code, right? Maybe we can instead expose some edge based interface, e.g., AAIsDead::isEdgeDead(BasicBlock, BasicBlock) or AAIsDead::getLiveOutEdges(BasicBlock). WDYT?

3575

We need to profile this but similar maps were causing memory problems before. Make the value a std::unique_ptr and that should already help. I'm not sure about this cache in general. I guess it mainly depends on the usage of this AA later on. For now we can keep it but we should invest in some time tracking for AAs at some point and thereby determine if this is too costly. If that is the case we could "cache" only the queries that were asked and recompute them in every update, not the entire graph.

okura updated this revision to Diff 284663.Aug 11 2020, 4:54 AM
  • reimplement updateImple and interfaces
okura retitled this revision from [Attributor] Implement AAReachability to [Attributor][WIP] Implement AAReachability.Aug 11 2020, 4:55 AM
okura updated this revision to Diff 287499.Aug 24 2020, 2:31 PM
  • fix according to interface change
jdoerfert added inline comments.Aug 25 2020, 2:35 PM
llvm/include/llvm/Transforms/IPO/Attributor.h
895

Why don't these life in the AAReachabilityFunction?

llvm/lib/Transforms/IPO/AttributorAttributes.cpp
2409

Remove this and the initialize in the Impl class.

2415

typo above.

2418

Define this as EdgeTy or similar in the class once you moved the query vectors there.

2457

Don't use count above but the second element of the return value of insert.

okura added inline comments.Aug 25 2020, 11:27 PM
llvm/include/llvm/Transforms/IPO/Attributor.h
895

I put these here for the same reason for this.

okura updated this revision to Diff 287851.Aug 26 2020, 12:55 AM

address comments