[The World of Linkers—Lab 13] Addresses Have Semantics: Safe ICF and Code Order
Implement conservative ICF and text ordering on class12's ET_EXEC and static-PIE backends. Eligible code sections share their contents; sections with significant address identity remain distinct. Symbols, relocations, unwind tables, and debug information must agree with the folded layout. Theory 12 develops partition refinement and address identity; unwind compatibility explains the metadata comparison.
Project: class13 code and tests; private-repository access is required. Reuse class8's frontend and liveness analysis, class10 or class11 lowering, and class12 debug output. Fold before layout and retain input identities and merged-piece mappings. The supplied link and link_pie select the two backends; the CLI selects PIE with --pie.
Implementation tasks
Complete three interfaces in the class13 crate library. The class13 README specifies the complete comparison relation and diagnostics.
| Task | Interface | Result |
|---|---|---|
| C13.1 | fold | Refine candidate equivalence classes and map aliases to representatives |
| C13.2 | unwind_descriptions | Build normalized CIE/FDE descriptions for live code in the specified order |
| C13.3 | link_with | Collect candidates and significance, then compose folding, ordering, layout, and class12::finish |
Candidates are live Text input sections; each whole section is one folding unit. Choose the smallest SectionId as the representative. Symbols retain their section-relative offsets, and an alias's relocations are not applied twice. Process order after folding: an alias names its representative, and duplicate requests are removed stably.
The task has a deliberately conservative boundary. Compare raw bytes, relocation references, and normalized unwind descriptions without normalizing relocation fields. keep and live non-NONE relocations other than PLT32 pin their target candidates. The implementation does not read .llvm_addrsig, so a PC32 call also prevents its target from folding. This is the project's contract; other linkers' safe ICF policies may differ.
Unwind comparison removes only the FDE's CIE-pointer and initial-location fields. Range, augmentation, CFI, and padding remain significant. The default ET_EXEC and PIE pipelines preserve unwind information and reject unsupported personality or LSDA encodings. Only programs without runtime unwinding or backtraces may explicitly select AbortOnly; that policy still processes address significance and debug data.
For example, candidate functions A and B may have identical machine bytes while A calls a candidate in class X and B calls one in class Y. They can be in the same initial partition; once the target class numbers enter the signature, the next refinement separates them. If X and Y later merge, recompute the partition and continue until the class assignment stops changing. The fixed point is therefore part of the reference graph, not the result of one memcmp of instruction bytes.
Reach a fixed point before changing layout
fold returns aliases between input section identities, not addresses. Build an initial partition from bytes, alignment, reference shape, and unwind descriptions; repeatedly refine it by the partitions of referenced targets until a fixed point; only then let link_with remove copies, redirect references, and update debug data. Folding after one comparison misses recursive differences and distinct CFI.
Acceptance separates address significance, FDE compatibility, symbol redirection, and execution: function pointers and keep preserve distinct addresses, call-only targets may share one, and folded DWARF becomes a tombstone. The no-fold fixture must reproduce class12, showing that the ICF layer has not silently changed the base backend.
Trace each task to its tests
| Task | Key tests | Property established |
|---|---|---|
C13.1 fold | folding_propagates_through_calls, recursion_reaches_the_greatest_fixed_point | Equivalence classes iterate over the reference graph to a fixed point, rather than stopping at one byte comparison. |
C13.2 unwind_descriptions | folding_requires_equal_runtime_unwind_descriptions | Functions with equal machine code but different unwind semantics remain separate. |
C13.3 link_with | address_taken_functions_stay_distinct, folding_preserves_merged_constants_and_compatible_unwind | Address significance, merged constants, GOT/TLS, unwind, and debug coordinates remain coherent after folding. |
Read the contract equivalence relation first, then the native address, debugger, and execution tests; a smaller file is not evidence of correct ICF.
Acceptance
From the repository root, on native x86-64 Linux:
cargo test --locked -p class13cargo test --locked -p class13 --releasepython3 scripts/grade.py class13Acceptance checks code identity together with program behavior:
- Folding relation: representative selection, reference differences, recursive equivalence, and candidate-order independence. Eligible functions share an address; address-taken or kept functions retain distinct addresses.
- Metadata consistency: folded copies receive debug tombstones, leaving only the representative's valid description. Equal instruction bytes with different CFI remain separate; unsupported exception encodings are rejected.
- Ordering and composition: explicit order, aliases, invalid requests, merged constants, GOT, TLS, unwind tables, and debug information in both backends, plus CLI/library equivalence.
A dedicated fixture with no folds and no ordering must reproduce class12's corresponding output in full. An empty order list does not disable ICF: eligible candidates still fold. Tests do not require arbitrary input-file permutations to produce identical bytes.