[CSSPGO] Sorting nodes in a cycle of profiled call graph.
authorHongtao Yu <hoy@fb.com>
Mon, 29 Nov 2021 22:28:27 +0000 (14:28 -0800)
committerHongtao Yu <hoy@fb.com>
Tue, 30 Nov 2021 17:01:08 +0000 (09:01 -0800)
commitbf317f66989cac26e17b4cd16ab1c7bdfe73dbe0
treef28d0c1f80f8128c70902ccf26087b1f0148e2af
parentb8e03be88dc87303f7401ea7b9906947ac67a6db
[CSSPGO] Sorting nodes in a cycle of profiled call graph.

For nodes that are in a cycle of a profiled call graph, the current order the underlying scc_iter computes purely depends on how those nodes are reached from outside the SCC and inside the SCC, based on the Tarjan algorithm. This does not honor profile edge hotness, thus does not gurantee hot callsites to be inlined prior to cold callsites. To mitigate that, I'm adding an extra sorter on top of scc_iter to sort scc functions in the order of callsite hotness, instead of changing the internal of scc_iter.

Sorting on callsite hotness can be optimally based on detecting cycles on a directed call graph, i.e, to remove the coldest edge until a cycle is broken. However, detecting cycles isn't cheap. I'm using an MST-based approach which is faster and appear to deliver some performance wins.

Reviewed By: wenlei

Differential Revision: https://reviews.llvm.org/D114204
llvm/include/llvm/ADT/SCCIterator.h
llvm/include/llvm/Transforms/IPO/ProfiledCallGraph.h
llvm/lib/Transforms/IPO/SampleProfile.cpp
llvm/test/Transforms/SampleProfile/Inputs/profile-context-order-scc.prof [new file with mode: 0644]
llvm/test/Transforms/SampleProfile/profile-context-order.ll
llvm/tools/llvm-profgen/CSPreInliner.cpp