Page MenuHomePhabricator

[Attributor] Implement AAReachability
Needs ReviewPublic

Authored by okura on Mon, Jul 27, 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.Mon, Jul 27, 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.Mon, Jul 27, 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.Mon, Jul 27, 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
3262

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

3267

Also not needed as far as I can tell.

3281–3284
3333

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?

3375

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.