This is an archive of the discontinued LLVM Phabricator instance.

[Attributor] Derive AAFunctionReachability attribute.
ClosedPublic

Authored by kuter on Jun 19 2021, 2:37 PM.

Details

Summary

This attribute uses Attributor's internal 'optimistic' call graph
information to answer queries about function call reachability.

Functions can become reachable over time as new call edges are
discovered.

Diff Detail

Event Timeline

kuter created this revision.Jun 19 2021, 2:37 PM
kuter requested review of this revision.Jun 19 2021, 2:37 PM
Herald added a reviewer: sstefan1. · View Herald Transcript
Herald added a reviewer: baziotis. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript
kuter updated this revision to Diff 353217.Jun 19 2021, 4:48 PM

Unit test added.

kuter updated this revision to Diff 353218.Jun 19 2021, 5:03 PM

Added a test case for a unknown callee

kuter edited the summary of this revision. (Show Details)Jun 19 2021, 7:25 PM
kuter updated this revision to Diff 353221.Jun 19 2021, 7:27 PM

clang-format :/

kuter updated this revision to Diff 353230.Jun 20 2021, 4:59 AM
  • Implement getAsStr()
  • Naming Changes.
jdoerfert added inline comments.Jun 21 2021, 8:48 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
8289

Move it down to the use. Also rename it to make clear what this is, e.g. NonConstThis.

8294

Eventually we don't want this. We want to check, for example, if an unknown callee can reach Fn at all.
We also want to encode domain knowledge about (some) GPU kernels as we know they can only be called "from the outside".
That is, you cannot reach one kernel from another one.

8313

I don't get why we do this conditionally. If we have an unreachable query already, and then a new one comes in, we still now depend on the state of all AAs we asked in the meantime.

8348

Swap the cases, and use continue to make it easier to read.

8385

Couldn't we add dependences here, maybe keep track of all the AAs above and then add dependences in the false case. removes complexity I think

kuter added inline comments.Jun 21 2021, 9:15 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
8313

We should already have deps if the UnreachableQueries is not empty. I might remove this since this is a very tiny optimization.

kuter added inline comments.Jun 21 2021, 9:50 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
8385

This is just for checking a single function. In the updateImpl method above we have a for loop that goes over unreachable queries.
moving the call to recieveUpdates here would cause us to call it multiple times which not needed.

kuter updated this revision to Diff 353406.Jun 21 2021, 10:01 AM
  • Simplify control flow
  • Rename const_cast
kuter marked 2 inline comments as done.Jun 21 2021, 10:04 AM
jdoerfert added inline comments.Jun 21 2021, 10:30 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
8385

The concept of "receiveUpdates" seems to be some optimization but I fear it will simply lead to errors.

Let's talk this through:
Adding a dependence is pretty cheap.
We should add dependences as we use AAs not at some point later somehow.
In this function we know what AAs we used to come up with a optimistic result, if any.
I fail to see what would be worse if we directly add dependences to those AAs before we return false, it certainly will make this easier to read as multiple implicit dependences will go away.

(FWIW, if you argue it's an optimization you might have to show how much it saves actually. I expect the result here to be well withing the noise so it's not worth making the code harder to read.)

kuter added inline comments.Jun 22 2021, 10:04 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
8385

I agree that moving the contentes of receiveUpdates here should be ok since adding deps is fast.
I fear that things can get really slow if we are not careful about our dependencies.
Since we are doing this in a recursive way we are actually creating a lot of AAFunctionReachability attributes.

if all functions that where queried where reachable, we do not need any dependencies since functions can't become unreachable after we find that they are reachable.

kuter updated this revision to Diff 353742.Jun 22 2021, 12:10 PM

remove the recieveUpdates

This revision is now accepted and ready to land.Jun 22 2021, 1:09 PM

remove the WIP tag before committing

kuter retitled this revision from [WIP][Attributor] Derive AAFunctionReachability attribute. to [Attributor] Derive AAFunctionReachability attribute..Jun 23 2021, 8:31 AM
This revision was automatically updated to reflect the committed changes.