Identical Code Folding (ICF) support

[zamazan4ik]

Hi!

I found that right now wild doesn't support ICF functionality. Are there plans to support it in the future? If yes, how far is it in the wild backlog? :) I tried to find any kind of roadmap or related discussions about ICF in the repo but I've found nothing.

My personal use cases are about shrinking binary size, mostly for Rust-only binaries. However, some Rust binaries are consist of some C or C++ dependencies, so I am interested in ICF support for C stuff too. That's why it would be nice to see support not only for icf=all but for icf=safe too. Unfortunately, right now mold doesn't support safe mode so I forced to use LLD instead.

I totally understand that there are features to implement with much higher priority since ICF comparatively rarely used (from my experience). But it would be nice to have ICF support once in the future in wild too. Not pushing or anything like that - just curious :)

Thank you.

[davidlattimore]

I had avoided looking much at ICF, since it's a pretty expensive phase in terms of linking fast, however recently we've started working on other expensive features (e.g. linker plugin support). I think supporting ICF would be good. I don't have any idea where it'd sit in my priorities, which continuously change anyway, but if anyone else wanted to have a go at implementing it, I'd be all for it.

Since I'm thinking about it, here are some thoughts on implementation...

• Operate on sections, not functions. Each function should be in a separate section anyway and if they're not, then I think I'm fine with us just not deduplicating them.
• We only care about executable sections. (edit: Maybe also RO data)
• Even though ICF is expensive, we still want it to be as fast as possible. Most likely that means doing something similar to what we do with symbols. i.e. a two phase approach. First phase, threads hash relevant sections and add info to buckets based on the hash. Second phase, hashmaps are built for each bucket.
• To be correct, we need to not just hash the input section contents, but also take the relocations into account. However, we can't just hash the section's relocation section because that will be different. We can probably more or less hash the relocations, but with the object's symbol index substituted with the resolved SymbolId.
• Storing any per-section information can be expensive, since there are heaps of sections. Ideally we want to not increase the size of SectionSlot, since that would affect link performance even when ICF isn't in use.
• Most likely the work would be done during section resolution (resolve_sections).

[lapla-cogito]

I think mold supports Safe ICF. However, similar to lld, it only appears to employ a method that records symbols requiring address comparisons in .llvm_addrsig and references them accordingly. Consequently, with non-compliant compilers like gcc, Safe ICF effectively behaves identically to Full ICF.
Upon further investigation, I think there are two possible implementations of Safe ICF without using .llvm_addrsig:

• Exclude symbols containing relocations that reference addresses from ICF processing (though this approach requires caution when applied to rodata sections. See this).
• Utilize thunks. For example, when merging functions A and B, you could either make function B's contents consist solely of a jump instruction to function A, or have both jump to a common merged body. However, this has only been observed being used in lld-macho, and I can't determine its actual applicability...