edited ld.lld.1

nits

nit

tests

minor

D159526 performed the rename. If this patch is applied, applyCDSort in lld/ELF will need to be updated again. This is exactly the scenario I want to avoid.

In D152840#4648582, @MaskRay wrote:

In D152840#4648483, @spupyrev wrote:

In D152840#4648482, @MaskRay wrote:

Thanks for the update. I am mainly waiting for the renamed function (applyCDSort does not convey the meaning well), changes of nested std::pair and std::vector => SmallVector<*, 0>

I have an impression the changes are made in the follow-up D159526 (which I'd prefer to land after this one). Do I miss something?

You are right. You may rebase this patch on top of D159526 :)

In D152840#4648482, @MaskRay wrote:

Thanks for the update. I am mainly waiting for the renamed function (applyCDSort does not convey the meaning well), changes of nested std::pair and std::vector => SmallVector<*, 0>

renaming the option

comments

rebasing to latest

Thanks for looking into this. I made the requested changes

addressing comments, adding a test for cdsort

Thanks. We recently discussed a case where stale matching was unable to match any block in a function and so function exec count was not set. We thought it's still beneficial to set exec count in this case for function reordering. I assume the entry block match will also make stale matching set function exec count in this scenario?

rebase

rebase

Since the last change wasn't trivial, I'll wait for another review before landing this

Addressing comments by reverting the changes in MCPlusBuilder.h

rebase & adjust logging

Sorry for overlooking this; here is a fix: https://reviews.llvm.org/D156734

I am adding an internal test for CDS

Ready for review now

rebased past formatting

clang-format

nit

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

rebase

nit

Updated the part computing matching metrics to make it more readable. Let me know if there is still confusion.

Thanks for review Rahman. I'll wait a few more days before landing in case anyone else has suggestions.

rebase

reverting accidentally attached changes

rebase to latest

another typo

a typo

• wrapping binary stats into a struct;
• printing matching stats based on strong hashes, where we have high confidence in correctness.

Moving stats from BinaryFunction to (aggregated) BinaryContext

addressing comments (mostly adding periods)

comments

nit

Added a test. Without the change, the output is

...
BOLT-INFO: Starting pass: reorder-functions
BOLT-INFO: hot func main (400)
BOLT-INFO: hot func func1 (500)
BOLT-INFO: hot func func2 (1500)
BOLT-INFO: hot func func3 (100)
BOLT-INFO: hot func func4 (99)
BOLT-INFO: hot func func5 (110)
...

Thanks for teaching me how to measure the impact of instruction caches. While re-running the experiments with the new events, I realized that my earlier report was not using C^3 as the baseline. Instead the numbers were on top of an improved code layout (referred to hfsort+) utilized by BOLT, which is not relevant here; I apologize for the confusion.
Below are details of the latest run on the same clang benchmarks, with and without huge pages. In addition to comparing the new algorithm to C^3, i'm also including the numbers on top of the "input" ordering that comes from the compiler. Here I'm building the binary with LTO and AutoFDO, but observe similar numbers when using instrumentation counts or other sampling-based profiling approaches (e.g., CSSPGO).

Hmm. I was using "cpu/event=0x85,umask=0x61/u" for i-TLB misses, which we got from https://download.01.org/perfmon, which has even been moved since then. Back in 2017 (when the algorithm was developed) we thought this is the "right" event to look at, but it might not be the case. Which one would you recommend to look at? I see this page has a good description.

Here are my measurements on the clang binary (release_14) by compiling two large cpp files (benchmark1 and benchmark2). Negative values are improvements, bold ones are stat sig.

@rahmanl @davidxl Our measurements are always on top of C^3 (the one currently utilized by CallGraphSort.cpp). If we compare against "no-function-ordering" (ie looking at the order produced by the compiler), then the wins would be well beyond 1% cpu but that's not a realistic scenario these days. The linked follow-up diffs, D152840 and D153039, enable the ordering in the linker and in the BOLT. I'll share more specific numbers on my benchmarks soon.

Do you have a follow-up diff to adjust BOLT's part?

rebasing & fixing the test & adding debug logging