[LazyCallGraph] Build SCCs of the reference graph in order
authorFangrui Song <i@maskray.me>
Mon, 2 Nov 2020 21:22:42 +0000 (13:22 -0800)
committerFangrui Song <i@maskray.me>
Mon, 2 Nov 2020 21:22:42 +0000 (13:22 -0800)
commit491dd2711f7234e21983da355c32107ee1f6a750
tree9f3377a7a293733232563072ef3f459d97646cb7
parenteed8df6a131453dee779f7e3554d4e0bb591318b
[LazyCallGraph] Build SCCs of the reference graph in order

```
// 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. 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 changing too many
check lines.

Differential Revision: https://reviews.llvm.org/D90566
13 files changed:
llvm/lib/Analysis/LazyCallGraph.cpp
llvm/test/Analysis/LazyCallGraph/alias.ll
llvm/test/Analysis/LazyCallGraph/basic.ll
llvm/test/Other/scc-pass-printer.ll
llvm/test/Transforms/Attributor/IPConstantProp/PR26044.ll
llvm/test/Transforms/Inline/cgscc-cycle-debug.ll
llvm/test/Transforms/Inline/cgscc-cycle.ll
llvm/test/Transforms/Inline/cgscc-incremental-invalidate.ll
llvm/test/Transforms/Inline/cgscc-invalidate.ll
llvm/test/Transforms/OpenMP/globalization_remarks.ll
llvm/test/Transforms/OpenMP/parallel_region_merging.ll
llvm/unittests/Analysis/CGSCCPassManagerTest.cpp
llvm/unittests/Analysis/LazyCallGraphTest.cpp