This is an archive of the discontinued LLVM Phabricator instance.

[BOLT] A new code layout algorithm for function reordering [3b/3]

Authored by spupyrev on Jun 15 2023, 8:43 AM.



This is a new algorithm for function layout (reordering) based on the call graph
extracted from a profile data; see diffs down the stack for more details.

This layout is very similar to the existing hfsort+, but perhaps a little better
on some benchmarks. The goals of the change is as follows:

(i) rename and replace hfsort+ with a newer (hopefully better) implementation.
I'd prefer to keep both algs together for some time to simplify evaluation and
transition, but do want to remove hfsort+ once we're confident that there are
no regressions.

(ii) unify the implementation of code layout algorithms across LLVM. Currently
Passes/HfsortPlus.cpp and Utils/CodeLayout.cpp share many implementation-specific
details; this diff unifies the code.

Diff Detail

Event Timeline

spupyrev created this revision.Jun 15 2023, 8:43 AM
Herald added a reviewer: Amir. · View Herald Transcript
Herald added a reviewer: maksfb. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript
spupyrev published this revision for review.Jun 15 2023, 8:55 AM
spupyrev edited the summary of this revision. (Show Details)
spupyrev added a subscriber: shatianw_mt.
Herald added a project: Restricted Project. · View Herald TranscriptJun 15 2023, 8:55 AM
hzq added a subscriber: hzq.Jul 13 2023, 8:14 PM
spupyrev updated this revision to Diff 544838.Jul 27 2023, 10:12 AM

Since the upstream diffs have landed, this is now ready for review

spupyrev updated this revision to Diff 544874.Jul 27 2023, 11:48 AM


Amir added a comment.Jul 27 2023, 1:57 PM

I just pushed formatting the file as 2b642926b40b1f5d2e9525332a60d9502a289383, please rebase on top of that.

spupyrev updated this revision to Diff 544952.Jul 27 2023, 3:24 PM

rebased past formatting

Amir accepted this revision.Jul 27 2023, 3:34 PM

Thanks! Can we add any tests for the expected layout, using either in-tree or upstream bolt-tests binaries and profiles? I don't see any for hfsort/hfsort+ but I think we want to avoid regressing the layout.


I assume the definition lives in llvm/Transforms and we include the required component in CMakeLists?

This revision is now accepted and ready to land.Jul 27 2023, 3:34 PM

I am adding an internal test for CDS


Yes, ReorderAlgorithm.cpp already uses on llvm/Transforms so it's not a new dependency.

thakis added a subscriber: thakis.Jul 31 2023, 11:41 AM

Looks like this doesn't build on macOS: