This is an archive of the discontinued LLVM Phabricator instance.

Add LazyCallGraph API to add function to RefSCC
ClosedPublic

Authored by modocache on Jan 5 2020, 5:33 AM.

Details

Summary

Depends on https://reviews.llvm.org/D70927.

LazyCallGraph::addNewFunctionIntoSCC allows users to insert a new
function node into a call graph, into a specific, existing SCC.

Extend this interface such that functions can be added even when they do
not belong in any existing SCC, but instead in a new SCC within an
existing RefSCC.

The ability to insert new functions as part of a RefSCC is necessary for
outlined functions that do not form a strongly connected cycle with the
function they are outlined from. An example of such a function would be the
coroutine funclets 'f.resume', etc., which are outlined from a coroutine 'f'.
Coroutine 'f' only references the funclets' addresses, it does not call
them directly.

Event Timeline

modocache created this revision.Jan 5 2020, 5:33 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 5 2020, 5:33 AM

The short-circuit change makes sense to me. But what caused the creation of extra SCCs due to self-recursion? Is that because of the short-cut from line 808-825 and the clearing of SCC stack and DFS stack broke the LowLink and DFSNumber check of later Tarjan DFS?

Since this fix targets self-recursion specifically, just wanted to make sure the underlying issue doesn't go beyond self-recursion. Specifically, will we (incorrectly) create extra SCC if we have an indirect recursion/cycle from that target node, and we get caught by line 808-825 before every node in the original SCC is visited and placed on PendingSCCStack..

Yeah, very good questions. When I was writing this patch, I was focused more on getting my specific use case, the one covered by the unit test, to work without hitting an assert. (I also think this is potentially a performance optimization, but I haven't measured in any meaningful way.) But I'm also curious why this occurs, and will look into it a little more. I'd ideally like to get a unit test case that demonstrates the issue without being based on top of D70927, but I wasn't able to in this first iteration of the patch.

modocache marked an inline comment as done.Jan 6 2020, 11:15 AM
modocache added inline comments.
llvm/unittests/Analysis/CGSCCPassManagerTest.cpp
1624

I think I see the issue.

First of all, this comment is incorrect: CallGraphUpdater::registerOutlinedFunction doesn't automatically add any edges between f and g, that's up to the user to do themself -- it doesn't create a reference edge, a call edge, it doesn't create anything.

Here I'm inserting g into the same SCC as f, but for that to be a valid SCC to insert into, f and g need to be part of the same strongly-connected component, meaning a call edge path exists connecting f *-> g and g *-> f. (For typical "outlining" of a part of the body of f into some outlined function, a call edge path from f *-> g would almost certainly exist.)

However, in the case of coroutine funclets, there is only a ref edge f -> g. And in this example, there's not even a ref edge f -> g`.

So this is user error: I shouldn't be inserting f into g, I ought to instead create an SCC especially for g. If I do so, then later when the call graph is updated to handle the demotion of f -> f from a call edge to a ref edge, the DFS walk won't find a new SCC (g), and incorporateNewSCCRange won't be called with ranges [(g), (f)] for f.

That's my theory, anyway. If I end up being right, I'll probably end up abandoning this change and changing D71899 slightly.

modocache planned changes to this revision.Jan 6 2020, 11:15 AM
modocache updated this revision to Diff 236503.Jan 6 2020, 9:06 PM

I updated this patch such that it can address the underlying problem encountered by the coro-split pass in D71899: we need a method of inserting new ref edges into an existing call graph, whereas currently the CallGraphUpdater only allows the insertion of call edges. I don't know if there's any use for such an API in the old CallGraph, so I left that unimplemented. I also considered simply adding this functionality as a member function on LazyCallGraph or one of its inner classes, but decided to reuse CallGraphUpdater in order to share some of the logic.

modocache updated this revision to Diff 236504.Jan 6 2020, 9:07 PM
modocache retitled this revision from Short-circuit SCC update for self-referential edge to [PM][CGSCC] API for outlined ref edges.
modocache edited the summary of this revision. (Show Details)

Update fields in Phabricator.

modocache updated this revision to Diff 236506.Jan 6 2020, 9:09 PM

Remove the now unneeded check for self-referential edges.

Harbormaster completed remote builds in B43398: Diff 236504.
Harbormaster completed remote builds in B43400: Diff 236506.
modocache updated this revision to Diff 236507.Jan 6 2020, 9:10 PM

Sorry for the noise -- this undo's a comment change.

modocache updated this revision to Diff 236512.Jan 6 2020, 9:25 PM

Add documentation for the new member function.

modocache updated this revision to Diff 236669.Jan 7 2020, 12:42 PM

Rebase onto the latest revision of D70927.

modocache updated this revision to Diff 242245.Feb 3 2020, 8:13 PM
modocache retitled this revision from [PM][CGSCC] API for outlined ref edges to Add LazyCallGraph API to add function to RefSCC.
modocache edited the summary of this revision. (Show Details)

Update based on @jdoerfert's latest version of revision D70927. Previous versions added a public member function to CallGraphUpdater, the latest versions instead add a public member function to LazyCallGraph. This update does the same, it moves the new member function, from CallGraphUpdater::registerReferredToOutlinedFunction, to LazyCallGraph::addNewFunctionIntoRefSCC.

modocache added a subscriber: hfinkel.

Now that the underlying D70927 has been committed, this diff needs a code review. I'll add @hfinkel since he left some helpful review comments on D70927.

You don't have a CallGraphUpdater interface for this. Is this on purpose? (The test mentions CallGraphUpdater still).

llvm/include/llvm/Analysis/LazyCallGraph.h
1064

You have to specify that the node will form a new SCC inside of \p RC

modocache updated this revision to Diff 244564.Feb 13 2020, 8:06 PM

Thanks, @jdoerfert! As per your suggestions I updated the docblock and the test comments, and I added a test specifically for LazyCallGraph. Built and tested everything with ASAN and it passes.

modocache marked an inline comment as done.Feb 13 2020, 8:07 PM
jdoerfert accepted this revision.Feb 15 2020, 8:03 PM

LGTM.

llvm/include/llvm/Analysis/LazyCallGraph.h
1065

Nit: -completely

This revision is now accepted and ready to land.Feb 15 2020, 8:03 PM
modocache updated this revision to Diff 244996.Feb 17 2020, 9:45 AM

Thanks for the reviews, @jdoerfert! I addressed your comment by removing the redundant 'completely'. I'll commit this in a few minutes.

This revision was automatically updated to reflect the committed changes.