This is an archive of the discontinued LLVM Phabricator instance.

[lld-macho] Allow order files and call graph sorting to be used together
ClosedPublic

Authored by lgrey on Jan 14 2022, 1:01 PM.

Details

Summary

If both an order file and a call graph profile are present, the edges of the call graph which use symbols present in the order file are not used. All of the symbols in the order file will appear at the beginning of the section just as they do currently. In other words, the highest priority derived from the call graph will be below the lowest priority derived from the order file.

Practically, this change renames CallGraphSort.{h,cpp} to SectionPriorities.{h,cpp}, and most order file and call graph profile related code is moved into the new file to reduce duplication.

Diff Detail

Event Timeline

lgrey created this revision.Jan 14 2022, 1:01 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptJan 14 2022, 1:01 PM
Herald added a subscriber: mgorny. · View Herald Transcript
lgrey requested review of this revision.Jan 14 2022, 1:01 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 14 2022, 1:01 PM
oontvoo added inline comments.
lld/MachO/SectionPriorities.cpp
39

it's confusing that this variable is named with k, which I assume means it's a constant, and yet it's updated by the function below.

(also I think this is a google specific style - the LLVM coding standard seems to suggest camel case only)

254

you're not modifying the symbol

262

You may need to check this against NULL since synthetic symbols don't have InputFile (they'd return NULL)

lgrey updated this revision to Diff 401699.Jan 20 2022, 10:50 AM
lgrey marked an inline comment as done.

Comment round and format

lld/MachO/SectionPriorities.cpp
254

Done (but for my edification: why pointer to const vs. const ref?)

lgrey marked 2 inline comments as done.Jan 20 2022, 10:51 AM
lgrey updated this revision to Diff 401702.Jan 20 2022, 10:57 AM

Update callsites

LG - thanks!
(will leave it open for thakis)

lld/MachO/SectionPriorities.cpp
254

(commented below also - I suggested const* because the objects themselves are stored as pointers, so you can avoid the whole deref + taking address trip. Also it's not common to see const ref in lld code)

372

i would suggest changing this to const Defined* sym too

380

nit: unless you're planning on taking care of this shortly - a bit more info on what to be done here would be helpful

lgrey updated this revision to Diff 401765.Jan 20 2022, 1:19 PM

Ref - > pointer to const in addSym

lgrey marked an inline comment as done.Jan 20 2022, 1:26 PM
lgrey added inline comments.
lld/MachO/SectionPriorities.cpp
380

I moved this (with minor changes) from Writer.cpp, so I actually have no context on it! I left it in since int3@ (the original author) might still have ideas/plans for it, or at the least as a signpost that there might be an unhandled case (similar proved useful in https://reviews.llvm.org/rGc4b45eeb44fdc49). Would it be better to delete?

oontvoo accepted this revision as: oontvoo.Jan 20 2022, 1:33 PM
This revision is now accepted and ready to land.Jan 20 2022, 1:33 PM
oontvoo added inline comments.Jan 20 2022, 1:33 PM
lld/MachO/SectionPriorities.cpp
380

Ah, ok - I guess let's leave it here then. :)

lgrey updated this revision to Diff 402040.Jan 21 2022, 10:49 AM

Format and rebase

I'd have one commit that does nothing but the file rename, then a 2nd commit that only moves unchanged functions around (both fine to commit directly), and then I'd rebase this on top of that so that it only shows the behavior change.

Having the file name be different from ELF and COFF is a bit unfortunate, but oh well.

lgrey updated this revision to Diff 402943.Jan 25 2022, 9:27 AM

Rebased on rename/function move

lgrey added a comment.Jan 25 2022, 9:27 AM

I'd have one commit that does nothing but the file rename, then a 2nd commit that only moves unchanged functions around (both fine to commit directly), and then I'd rebase this on top of that so that it only shows the behavior change.

Having the file name be different from ELF and COFF is a bit unfortunate, but oh well.

Done

thakis accepted this revision.Jan 27 2022, 6:19 PM

Code looks fine to me.

I tried it on Chromium, and apparently there are 542489 from all cg_profile section edges in the .o files, leading to 350079 entries in config->callGraphProfile. The edges are between 122620 isecs, compared to 918787 symbols total. So 800K symbols don't end up with an edge and just 122K do. That feels surprisingly low to me.

(The 542489 seems surprisingly low already: There's ~40k TUs, so that's just 10 call edges per TU on average.)

Maybe I'm holding something wrong locally.

lld/MachO/SectionPriorities.cpp
254

(fwiw, i think references for things that can't be null is fine)

290

I would've expected this to be expensive: In Chromium Framework, we have ~500K of these edges, so this is 1M calls to getSymbolPriority() (which we later call once more for every symbol; there's ~920K symbols). But to my surprise, I can't measure a slowdown from it, so I suppose it's ok.

(The alternative would be to store the symbol's priority in the symbol or its isec and to compute it just once. But, no need, apparently.)

376–377

When does this return non-0? The call graph order omits edges where either start or end have a priority from the order file, so it can only happen if two distinct symbols have the same isec, right? Does this run after ICF? Are there things other than ICF that could trigger it?

lgrey added inline comments.Jan 28 2022, 6:56 AM
lld/MachO/SectionPriorities.cpp
376–377

In the absence of call graph sorting, this is the same logic as currently unless I broke something. I'll get back to you about ICF, but there's N_ALT_ENTRY (also theoretically a problem if there are multiple symbols via N_ALT_ENTRY and one is an order file and another has a CG edge; I think this is rare and mostly covered by order file priorities being higher).