Sprint 24: ICF (-icf=safe)

Prerequisites

Sprints 9, 23 — atoms, dead-strip done.

Goals

Identical Code Folding: merge atoms whose content, relocations, and attributes are identical, so one copy survives. Safe mode only — respects address-taken symbols so function-pointer equality is preserved.

Deliverables

1. Safety rules

Atom is foldable iff:

• It lives in __TEXT,__text, __TEXT,__cstring, __TEXT,__literal16, __TEXT,__const, or __DATA_CONST,__const.
• It has no NoDeadStrip flag.
• It has no AddressTaken annotation (see below).
• It is not the primary symbol of its atom under -exported_symbols_list.

2. Address-taken detection

During reloc application (Sprint 11 + this sprint's prep pass), mark any atom referenced via Unsigned or PointerToGot or any GOT_LOAD_* as AddressTaken. Function pointers, vtable slots, RTTI entries, anything comparable via == — all take the address, so they must not be folded.

Only Branch26 references are considered "fold-safe" on their own; direct calls don't create address equality.

3. Segregation algorithm

Two-phase refinement (lld/MachO style):

1. Initial hash: for each foldable atom, compute a 64-bit hash over (size, flags, content bytes, reloc list normalized to (kind, addend, target class)).
2. Bucket: group atoms by hash. Single-element buckets are unique and not foldable.
3. Refine: within each bucket, check pairwise equality of content + relocs. Use equivalence classes — two atoms equivalent iff every referenced atom is equivalent (fixed-point refinement, à la Hopcroft's DFA minimization).
4. Repeat step 3 until no class splits. Converges in log(N) iterations in practice.
5. Fold: within each final equivalence class, pick a winner by input command-line order (stable, deterministic); rewrite every other atom's owner_symbol redirect to the winner; erase the loser atoms.

4. Reloc patching

After folding, some relocations now point at folded-away atoms. Rewrite every such reloc to target the winner. Layout recomputed; sizes shrink.

5. -icf=none path

Default off. -icf=safe enables. -icf=all (unsafe, doesn't respect AddressTaken) is not implemented — emits a diagnostic.

6. Interaction with -map and -why_live

• -map reports folded symbols with their winner: _foo folded to _bar.
• -why_live of a folded symbol reports the winner's live-chain.

7. Determinism

Winner selection by command-line order is stable across invocations. Hash function is seeded with a fixed seed — same inputs, same winners, same output bytes.

Testing Strategy

• Fixture: two functions with byte-identical code and relocs. -icf=safe folds them into one; nm shows only one entry, both symbol aliases point at the same address.
• Address-taken fixture: two identical functions, one has its address stored in a table. Fold does not happen for the address-taken one; both survive.
• String dedup: __cstring atoms with identical content folded.
• Large-scale: 50+ near-identical functions, fold correctness verified by running each alias.
• Differential: folded output's __text size matches ld -icf=safe within 1%.

Definition of Done

• -icf=safe reduces text size on a constructed fixture.
• Address-taken functions never folded.
• All aliases point to the folded winner at runtime.
• fortsh builds with -icf=safe and behaves identically to its -icf=none counterpart.