Page MenuHomePhabricator

[LazyCallGraph] Build SCCs of the reference graph in order
ClosedPublic

Authored by MaskRay on Nov 1 2020, 10:48 AM.

Details

Summary
// The legacy PM CGPassManager discovers SCCs this way:
for function in the source order
  tarjanSCC(function)

// While the new PM CGSCCPassManager does:
for function in the reversed source order [1]
  discover a reference graph SCC
  build call graph SCCs inside the reference graph SCC

In the common cases, reference graph ~= call graph, the new PM order is
undesired because for a | b | c (3 independent functions), the new PM will
process them in the reversed order: c, b, a. If a <-> b <-> c, we can see
that -print-after-all will report the sole SCC as scc: (c, b, a).

This patch corrects the iteration order [1]. The discovered SCC order will match
the legacy PM in the common cases.

For some tests (Transforms/Inline/cgscc-*.ll and
unittests/Analysis/CGSCCPassManagerTest.cpp), the behaviors are dependent on
the SCC discovery order and there are too many check lines for the particular
order. This patch simply reverses the function order to avoid change too many
check lines.

Diff Detail

Event Timeline

MaskRay created this revision.Nov 1 2020, 10:48 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 1 2020, 10:48 AM
MaskRay requested review of this revision.Nov 1 2020, 10:48 AM
MaskRay edited the summary of this revision. (Show Details)Nov 1 2020, 10:49 AM

I stumbled over the difference before, this makes sense to me.

aeubanks accepted this revision.Nov 2 2020, 12:01 AM

lgtm (thanks for doing this!), just one question about a test

llvm/test/Other/scc-pass-printer.ll
14–24

what's the reason for splitting the NPM and legacy PM RUN lines?

This revision is now accepted and ready to land.Nov 2 2020, 12:01 AM
MaskRay added inline comments.Nov 2 2020, 8:27 AM
llvm/test/Other/scc-pass-printer.ll
14–24

The orders of bar and foo are different...

The legacy PM SCC is bar,foo and thus llvm/lib/Analysis/CallGraphSCCPass.cpp prints the functions in the (reversed) order.

aeubanks added inline comments.Nov 2 2020, 10:42 AM
llvm/test/Other/scc-pass-printer.ll
14–24

Oh sorry I missed that, I thought the only change was the "bar, foo" -> "foo, bar".

This revision was landed with ongoing or failed builds.Nov 2 2020, 1:23 PM
This revision was automatically updated to reflect the committed changes.