This is an archive of the discontinued LLVM Phabricator instance.

[Attributor] Introduce the `AA::isPotentiallyReachable` helper APIs
ClosedPublic

Authored by jdoerfert on Jan 31 2022, 6:24 PM.

Details

Summary

To make usage easier (compared to the many reachability related AAs),
this patch introduces a helper API, AA::isPotentiallyReachable, which
performs all the necessary steps. It also does the "backwards"
reachability (see D106720) as that simplifies the AA a lot (backwards
queries were somewhat different from the other query resolvers), and
ensures we use cached values in every stage.

To test inter-procedural reachability in a reasonable way this patch
includes an extension to AAPointerInfo::forallInterferingWrites.
Basically, we can exclude writes if they cannot reach a load "during the
lifetime" of the allocation. That is, we need to go up the call graph to
determine reachability until we can determine the allocation would be
dead in the caller. This leads to new constant propagations (through
memory) in value-simplify-pointer-info-gpu.ll.

Note: The new code contains plenty debug output to determine how
reachability queries are resolved.

Parts extracted from D110078.

Diff Detail

Event Timeline

jdoerfert created this revision.Jan 31 2022, 6:24 PM
jdoerfert requested review of this revision.Jan 31 2022, 6:24 PM
Herald added a reviewer: baziotis. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript
kuter added inline comments.Jan 31 2022, 7:23 PM
llvm/lib/Transforms/IPO/Attributor.cpp
482

We haven't called FnReachabilityAA.instructionCanReach yet. This function won't do interprocedural reachability if there is no GoBackwardsCB ?

kuter added inline comments.Jan 31 2022, 7:27 PM
llvm/lib/Transforms/IPO/Attributor.cpp
471

I don't think this would work for recursive functions when doing backwards reachability.
the next instruction might contain a call that will reach ToI

jdoerfert added inline comments.Jan 31 2022, 8:56 PM
llvm/lib/Transforms/IPO/Attributor.cpp
471

I don't understand what the problem is.
If CurFromI->getNextNode() can reach ToI, the query isAssumedReachable(A, *CurFromI, *ToI); will be true.
Other calls that end up in the ToFn, e.g., going through recursion, are handled by the continue here instead of a return false.

482

Yes, as the comment states, if there is no backwards CB we give up. Nothing right now will otherwise cause this to not return "may reach" anyway. We eventually hit an external function and the callers are unknown and we give up. Once we have logic to determine an internal function can only be reached from specific places, etc. we can do more, unclear if that will be here though.

kuter accepted this revision.Jan 31 2022, 9:20 PM

LGTM

llvm/lib/Transforms/IPO/Attributor.cpp
471

I think you are right. I need to sleep a little more : )

482

I interpreted the comment as not doing any backwards search if there is no callback not "not doing any interprocedural reachability" but ok.

This revision is now accepted and ready to land.Jan 31 2022, 9:20 PM
jdoerfert added inline comments.Jan 31 2022, 9:45 PM
llvm/lib/Transforms/IPO/Attributor.cpp
482

return true = giving up

This revision was landed with ongoing or failed builds.Jan 31 2022, 11:43 PM
This revision was automatically updated to reflect the committed changes.