tree f28d0c1f80f8128c70902ccf26087b1f0148e2af
parent b8e03be88dc87303f7401ea7b9906947ac67a6db
author Hongtao Yu <hoy@fb.com> 1638224907 -0800
committer Hongtao Yu <hoy@fb.com> 1638291668 -0800

[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