This is an archive of the discontinued LLVM Phabricator instance.

Introduce a CallGraph updater helper class
ClosedPublic

Authored by jdoerfert on Dec 2 2019, 2:47 PM.

Details

Summary

The CallGraphUpdater is a helper that simplifies the process of updating
the call graph, both old and new style, while running an CG-SCC pass.

The uses are, for now, contained in different commits, e.g. D70767.

More functionality, e.g., replace a function with a new version, is
added as we need it.

Diff Detail

Event Timeline

jdoerfert created this revision.Dec 2 2019, 2:47 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 2 2019, 2:47 PM

Build result: pass - 60395 tests passed, 0 failed and 726 were skipped.

Log files: console-log.txt, CMakeCache.txt

jdoerfert updated this revision to Diff 232584.Dec 6 2019, 9:11 AM

Add comment

Build result: pass - 60558 tests passed, 0 failed and 726 were skipped.

Log files: console-log.txt, CMakeCache.txt

@hfinkel ping, this is a dependence for 2 CG-SCC patches

hfinkel added inline comments.Dec 27 2019, 12:22 AM
llvm/lib/Analysis/CGSCCPassManager.cpp
456 ↗(On Diff #232584)

This patch seems to be doing two things. One, is fixing this FIXME, and the second is adding the CallGraphUpdater wrapper. Can you split out these two changes?

Also, can you add unit tests for these various things?

llvm/lib/Transforms/Utils/CallGraphUpdater.cpp
46

What's the state of this? Should we have an assert for now?

jdoerfert updated this revision to Diff 235666.Dec 30 2019, 7:19 PM
jdoerfert marked an inline comment as done.

Extract parts into D72025, improve the existing functionality, add unit tests.

Unit tests: pass. 61163 tests passed, 0 failed and 728 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Thanks for this! I'm depending on this patch in D71899.

I noticed an edge case when using the CallGraphUpdater to introduce coroutine funclets for recursive coroutine functions, specifically when compiling this: https://github.com/lewissbaker/cppcoro/blob/d83ee9352ea2652fbc4f02885f9d19770f5e9608/test/recursive_generator_tests.cpp#L164. I reduced this to a small unit test, and what I think may be a reasonable fix, in D72226. Please feel free to review my patch, merge it into this one, or to address the issue however you like. And please let me know if it's actually just a user error on my part.

I had a question about where registerOutlinedFunction belongs, but other than that this LGTM! I'm not an expert, though, so maybe @chandlerc or someone could review this.

llvm/include/llvm/Transforms/Utils/CallGraphUpdater.h
27

Because it's a friend of LazyCallGraph and so can modify its internal state, I'd say CallGraphUpdater is a lot more than just a wrapper to unify the two interfaces. I rely on CallGraphUpdater in my patch D71899 because it allows me to insert an outlined function node into the call graph via CallGraphUpdater:: registerOutlinedFunction, defined below.

This makes me wonder whether the functionality implemented in the body of CallGraphUpdater::registerOutlinedFunction should actually be moved, to a public member function on LazyCallGraph or one of its other helper classes. The body of that function reaches into internal mappings in LazyCallGraph and modifies them -- that seems like something only LazyCallGraph itself should be responsible for.

The other member functions of CallGraphUpdater only use CallGraph and LazyCallGraph API that are public, so those do seem like "wrappers" to me. But CallGraphUpdater::registerOutlinedFunction seems like something different. If that function is going to remain, I'd suggest updating this docblock to indicate that CallGraphUpdater provides an interface that isn't available on LazyCallGraph itself.

44

Just echoing my nit-pick comment on D72025, but I think "CGSCC" is the canonical abbreviation. "CG-SCC" only appears in this diff and D72025.

wenlei added a subscriber: wenlei.Jan 5 2020, 10:12 AM
jdoerfert updated this revision to Diff 236474.Jan 6 2020, 3:26 PM

More tests, late function removal and other improvements

Unit tests: pass. 61278 tests passed, 0 failed and 736 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Friendly ping for review on this one. @jdoerfert is there anything blocking this besides code review? I think the clang-tidy errors are legitimate, FWIW, but they shouldn't be blockers for code review.

Reviewers: this is a blocker for @jdoerfert's patch for an attributor CGSCC pass, as well as for a series of patches supporting coroutine passes in the new pass manager.

jdoerfert updated this revision to Diff 240027.Jan 23 2020, 3:23 PM

Improvements after running the Attributor SCC pass on the LLVM test suite

Unit tests: fail. 62156 tests passed, 7 failed and 811 were skipped.

failed: LLVM-Unit.Analysis/_/AnalysisTests/CGSCCPassManagerTest.TestUpdateCGAndAnalysisManagerForPasses8
failed: libc++.std/language_support/cmp/cmp_partialord/partialord.pass.cpp
failed: libc++.std/language_support/cmp/cmp_strongeq/cmp.strongeq.pass.cpp
failed: libc++.std/language_support/cmp/cmp_strongord/strongord.pass.cpp
failed: libc++.std/language_support/cmp/cmp_weakeq/cmp.weakeq.pass.cpp
failed: libc++.std/language_support/cmp/cmp_weakord/weakord.pass.cpp
failed: libc++.std/thread/thread_mutex/thread_mutex_requirements/thread_mutex_requirements_mutex/thread_mutex_recursive/lock.pass.cpp

clang-tidy: fail. clang-tidy found 0 errors and 2 warnings. 0 of them are added as review comments below (why?).

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

hfinkel added inline comments.Jan 31 2020, 12:48 PM
llvm/include/llvm/Transforms/Utils/CallGraphUpdater.h
32

Please add some documentation explaining why you have a separate list of dead Comdat functions.

llvm/lib/Transforms/Utils/CallGraphUpdater.cpp
98

I agree with @modocache, this looks like an internal implementation detail of LCG. Can you move the logic into that class?

jdoerfert updated this revision to Diff 241935.Feb 2 2020, 11:22 AM
jdoerfert marked 4 inline comments as done.

Add documentation

jdoerfert marked an inline comment as done.Feb 2 2020, 11:25 AM
jdoerfert added inline comments.
llvm/include/llvm/Transforms/Utils/CallGraphUpdater.h
27

Resolved by making it part of the LazyCallGraph API.

llvm/lib/Transforms/Utils/CallGraphUpdater.cpp
98

@modocache Has a patch for this already (D72226) which I somehow missed for a month.
Options are to merge them or to apply them in order. I don't care which we choose.

Unit tests: fail. 62406 tests passed, 1 failed and 839 were skipped.

failed: LLVM-Unit.Analysis/_/AnalysisTests/CGSCCPassManagerTest.TestUpdateCGAndAnalysisManagerForPasses8

clang-tidy: fail. clang-tidy found 0 errors and 2 warnings. 0 of them are added as review comments below (why?).

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

jdoerfert updated this revision to Diff 241954.Feb 2 2020, 7:37 PM

Fix the tests

Unit tests: pass. 62406 tests passed, 0 failed and 839 were skipped.

clang-tidy: fail. clang-tidy found 0 errors and 2 warnings. 0 of them are added as review comments below (why?).

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

modocache requested changes to this revision.Feb 3 2020, 9:36 AM

Sorry if it's presumptuous of me to request changes, but I guess @hfinkel may agree with me here that registerOutlinedFunction ought to be moved to LazyCallGraph or one of its inner classes.

llvm/lib/Transforms/Utils/CallGraphUpdater.cpp
98

My revision D72226 builds on the idea of adding a CallGraphUpdater class, adding a specific function I need when outlining. I need something like this in order to make my particular CGSCC pass, coro-split, work with LazyCallGraph.

That being said, my (relatively new LLVM contributor) opinion is that CallGraphUpdater reaches a bit too deep into the LazyCallGraph internals -- it needs to be friends with LazyCallGraph, LazyCallGraph::SCC, and LazyCallGraph::Node in order to accomplish what it's doing here: modifying the DFSNumber and LowLink members of the node, both of which seem to be like implementation details of the Tarjan DFS algorithm being used under the hood. It seems like @hfinkel agrees with me, that the logic to perform the specific SCC discovery algorithm should be encapsulated entirely within LazyCallGraph. And I would not mind modifying my patch D72226 to work with such an approach.

This revision now requires changes to proceed.Feb 3 2020, 9:36 AM
jdoerfert added a comment.EditedFeb 3 2020, 1:24 PM

Sorry if it's presumptuous of me to request changes,

That is always OK.

but I guess @hfinkel may agree with me here that registerOutlinedFunction ought to be moved to LazyCallGraph or one of its inner classes.

I'm confused. I mentioned in my last response that you moved the "problematic" logic into LazyCallGraph in your patch (D72226), or did you do something different?
Please clarify what you want me to do that is different, or the same, to your patch. I'm happy to move logic into the LazyCallGraph class for example.

I mean in your patch registerOutlinedFunction looks "clean":

void CallGraphUpdater::registerOutlinedFunction(Function &NewFn) {
  if (CG) {
    CG->addToCallGraph(&NewFn);
  } else if (LCG) {
    LazyCallGraph::Node &CGNode = createNode(*LCG, NewFn);
    addNodeToSCC(*LCG, *SCC, CGNode);
  }
}

EDIT: I moved the logic into LazyCallGraph::addNewFunctionIntoSCC. Does that address your concerns? (It also allowed me to remove the updater as a friend)

jdoerfert updated this revision to Diff 242181.Feb 3 2020, 2:02 PM

Fix spelling and try to address concerns

Unit tests: unknown.

clang-tidy: fail. clang-tidy found 5 errors and 2 warnings. 0 of them are added as review comments below (why?).

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

jdoerfert updated this revision to Diff 242183.Feb 3 2020, 2:12 PM

Fix typo and remove last CallGraphUpdater friend decl by exposing a single API function.

jdoerfert updated this revision to Diff 242185.Feb 3 2020, 2:14 PM

Fixed copy/paste error, eliminated warnings

Unit tests: unknown.

clang-tidy: fail. clang-tidy found 5 errors and 2 warnings. 0 of them are added as review comments below (why?).

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

Unit tests: pass. 62436 tests passed, 0 failed and 845 were skipped.

clang-tidy: pass.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

jdoerfert updated this revision to Diff 242201.Feb 3 2020, 3:00 PM

Fix clang format (empty line)

modocache accepted this revision.Feb 3 2020, 5:55 PM

I mentioned in my last response that you moved the "problematic" logic into LazyCallGraph in your patch (D72226), or did you do something different? Please clarify what you want me to do that is different, or the same, to your patch. I'm happy to move logic into the LazyCallGraph class for example.

Ah, yes, I see the confusion! In D72226 I still have the logic in CallGraphUpdater, I didn't move it into LazyCallGraph. In D72226, I moved the "problematic" logic into new member functions on CallGraphUpdater:

LazyCallGraph::Node &CallGraphUpdater::createNode(LazyCallGraph &LCG,
                                                  Function &Fn) {
  assert(!LCG.lookup(Fn) && "node already exists");

  LazyCallGraph::Node &CGNode = LCG.get(Fn);
  LCG.NodeMap[&Fn] = &CGNode;
  CGNode.DFSNumber = CGNode.LowLink = -1;  // <- HERE, I think this implementation detail ought not be exposed to CallGraphUpdater
  CGNode.populate();
  return CGNode;
}

void CallGraphUpdater::addNodeToSCC(LazyCallGraph &LCG, LazyCallGraph::SCC &SCC,
                                    LazyCallGraph::Node &N) {
  SCC.Nodes.push_back(&N);
  LCG.SCCMap[&N] = &SCC;  // <- HERE, I think this implementation detail ought not be exposed to CallGraphUpdater
}

So my specific suggestion would be to move the lines marked "HERE" into a member function on LazyCallGraph, thus removing the need for CallGraphUpdater to be marked as a friend.

EDIT: I moved the logic into LazyCallGraph::addNewFunctionIntoSCC. Does that address your concerns? (It also allowed me to remove the updater as a friend)

Yes, that's exactly what I meant! Sorry I wasn't clearer!

Your latest update addressed all of my comments -- thank you! I do wish someone who's authored more of CallGraph or LazyCallGraph could chime in here, but this at least LGTM. Thanks for this work! It was a tremendous help in my own work to adapt coroutines to the new pass manager.

llvm/include/llvm/Transforms/Utils/CallGraphUpdater.h
31

Nit-pick typo: s/seperatly/separately/g.

This revision is now accepted and ready to land.Feb 3 2020, 5:55 PM
modocache added inline comments.Feb 3 2020, 7:14 PM
llvm/include/llvm/Analysis/LazyCallGraph.h
1062

Ah, I missed one thing; I think this deserves its own unit test in LazyCallGraphTest.cpp.

jdoerfert updated this revision to Diff 242248.Feb 3 2020, 8:15 PM

Add (simple) unit test for LazyCallGraph::addNewFunctionIntoSCC

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

Unit tests: pass. 62437 tests passed, 0 failed and 845 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

hfinkel accepted this revision.Feb 4 2020, 7:24 AM

LGTM

This revision was automatically updated to reflect the committed changes.