perf(ir): leave a witness member nothing calls out of its table #284

Merged

argus merged 2 commits from loop/57-perf-p10-dead-witness-members into main 2026-10-10 00:49:37 +00:00

Conversation 3 Commits 2 Files changed 16 +1039 -120

orion commented 2026-10-09 21:14:42 +00:00

Collaborator

Copy link

Closes #57

Round P10 of docs/PERFORMANCE.md (finding 12): a witness table slot that no CallWitness of the program can reach holds no function any more (FunctionId(-1)). Neither back end writes a thunk for it, and the member behind it is emitted only where something else still names it.

What changed

• compiler/src/ir/called-members.trb (new): dropUncalledMembers computes a least fixpoint over what the program keeps. It uses the C back end's keep-set reachability, with each witness call as an edge to the slot it reaches in every table reachableTables can name. It runs in finishLowering after dropListBoundsChecks and before trackCallerSites. It only runs on a closed program: lowerWorkspace, no hosted functions, no loadScript, and every witness source nameable. deadSlotProblems is the matching verifier rule.

• The keep-set roots and edges (isKeptOnlyIfReached, functionsNamedBy, descriptorFunctionsOf) now live in called-members.trb and are shared with backend/c/body.trb keptFunctions, so the two cannot drift apart.

• C back end: an empty slot is written as NULL with no thunk. A table with no live slot has a NULL member array. Bytecode back end: an empty slot is -1. torb ir prints -.

• backend/c/emit.trb: an element descriptor's helpers now demand the D_/drop helper of their item layout themselves. Before, a kept member always happened to name that layout too. Once such a member left its table, the bootstrap failed with D_T_std_x2f_yaml_resolve_YamlTag undeclared.

• ir/sites.trb makes no caller-tracking copy of a dropped member.

• Verifier: a TraitValue table must implement the trait of its bound. This is what keeps the liveness analysis honest.

• Tests: compiler/tests/witness-dead.test.trb covers:

  • (a) a slot called through a supertrait narrowing stays;
  • (b) the fixpoint (a slot only a dead member calls through goes too);
  • (c) a supertrait member called on a subtrait value stays in the subtrait's own slot;
  • (d) a table with no live slot;
  • an element type that only a dropped member used;
  • hand-built IR for the pass (open world, unnamed source, loadScript) and negative verifier cases.

  emit-c.test.trb pins the list program of finding 2: 0 thunks and ≤ 7 228 bytes. The program is compiled under the test prelude, so it is 7 086 bytes measured + 2%; before this change it had 2 thunks.

• Two lower-generics tests now pass a second type to their trait-typed parameter. With only one type the call is devirtualized and the slot they assert on is rightly emptied.

• lower.test.trb instance-count tripwire: the function count drops from 97 to 90, because members that were left out of their slot no longer get a caller-site copy.

• Docs: PERFORMANCE.md marks P10/F12 done and records the measurement. BACKEND.md has a note on the table layout.

Measurement

Before: main a183078a. After: this branch. All C numbers come from the CI artifacts of the two commits.

	before	after
3-line list program (real std), bytes of C	39 904	12 565
its witness thunks	16	0
compiler program.c, bytes	101 168 934	89 215 199 (−11.8%)
its witness thunks	7 629	2 677
its witness tables	1 516	1 516
compiler as VM bytecode (torb ir --bytecode disassembly), bytes	39 272 480	36 659 244 (−6.7%)
its chunks	18 324	13 680
list program bytecode disassembly, bytes / chunks	11 384 / 18	3 719 / 4
bootstrap step 2 (gcc on the compiler's C)	82.7 s	68.0 s
bootstrap total	201.7 s	174.3 s

The bootstrap times are one run each on a shared runner, so read them as a direction only. The bytecode rows compile this branch's sources with both compilers.

Deviations from the refine

• The pass is a new file, ir/called-members.trb, rather than ir/witness.trb / ir/instances.trb. Liveness is per (table, slot), not per (trait, member index).
• The pass only runs on a closed program. REPL, scripts, script hosts, loadScript and unnamed witness sources keep every slot.
• The verifier rule is deadSlotProblems, called from verifyProgram, plus the new TraitValue bound check.
• The refine's baseline (25 102 bytes, 24 thunks) is outdated. Main had moved to 39 904 bytes and 16 thunks.
• The emit-c budget is measured under the test prelude (7 086 bytes). The real-std numbers are in the table above.
• Not done: the architect's suggestion to emit a trap instead of NULL for an empty slot, plus a callee < 0 check in the VM. The verifier rule is the guard instead.
• Out of scope, as the refine says: the useless P6 copies (#281).

Closes #57 Round P10 of docs/PERFORMANCE.md (finding 12): a witness table slot that no `CallWitness` of the program can reach holds no function any more (`FunctionId(-1)`). Neither back end writes a thunk for it, and the member behind it is emitted only where something else still names it. ## What changed - `compiler/src/ir/called-members.trb` (new): `dropUncalledMembers` computes a least fixpoint over what the program keeps. It uses the C back end's keep-set reachability, with each witness call as an edge to the slot it reaches in every table `reachableTables` can name. It runs in `finishLowering` after `dropListBoundsChecks` and before `trackCallerSites`. It only runs on a closed program: `lowerWorkspace`, no hosted functions, no `loadScript`, and every witness source nameable. `deadSlotProblems` is the matching verifier rule. - The keep-set roots and edges (`isKeptOnlyIfReached`, `functionsNamedBy`, `descriptorFunctionsOf`) now live in `called-members.trb` and are shared with `backend/c/body.trb` `keptFunctions`, so the two cannot drift apart. - C back end: an empty slot is written as `NULL` with no thunk. A table with no live slot has a `NULL` member array. Bytecode back end: an empty slot is `-1`. `torb ir` prints `-`. - `backend/c/emit.trb`: an element descriptor's helpers now demand the `D_`/drop helper of their item layout themselves. Before, a kept member always happened to name that layout too. Once such a member left its table, the bootstrap failed with `D_T_std_x2f_yaml_resolve_YamlTag` undeclared. - `ir/sites.trb` makes no caller-tracking copy of a dropped member. - Verifier: a `TraitValue` table must implement the trait of its bound. This is what keeps the liveness analysis honest. - Tests: `compiler/tests/witness-dead.test.trb` covers: - (a) a slot called through a supertrait narrowing stays; - (b) the fixpoint (a slot only a dead member calls through goes too); - (c) a supertrait member called on a subtrait value stays in the subtrait's own slot; - (d) a table with no live slot; - an element type that only a dropped member used; - hand-built IR for the pass (open world, unnamed source, `loadScript`) and negative verifier cases. `emit-c.test.trb` pins the list program of finding 2: 0 thunks and ≤ 7 228 bytes. The program is compiled under the test prelude, so it is 7 086 bytes measured + 2%; before this change it had 2 thunks. - Two `lower-generics` tests now pass a second type to their trait-typed parameter. With only one type the call is devirtualized and the slot they assert on is rightly emptied. - `lower.test.trb` instance-count tripwire: the function count drops from 97 to 90, because members that were left out of their slot no longer get a caller-site copy. - Docs: PERFORMANCE.md marks P10/F12 done and records the measurement. BACKEND.md has a note on the table layout. ## Measurement Before: `main` a183078a. After: this branch. All C numbers come from the CI artifacts of the two commits. | | before | after | |-|-------:|------:| | 3-line list program (real std), bytes of C | 39 904 | 12 565 | | its witness thunks | 16 | 0 | | compiler `program.c`, bytes | 101 168 934 | 89 215 199 (−11.8%) | | its witness thunks | 7 629 | 2 677 | | its witness tables | 1 516 | 1 516 | | compiler as VM bytecode (`torb ir --bytecode` disassembly), bytes | 39 272 480 | 36 659 244 (−6.7%) | | its chunks | 18 324 | 13 680 | | list program bytecode disassembly, bytes / chunks | 11 384 / 18 | 3 719 / 4 | | bootstrap step 2 (gcc on the compiler's C) | 82.7 s | 68.0 s | | bootstrap total | 201.7 s | 174.3 s | The bootstrap times are one run each on a shared runner, so read them as a direction only. The bytecode rows compile this branch's sources with both compilers. ## Deviations from the refine - The pass is a new file, `ir/called-members.trb`, rather than `ir/witness.trb` / `ir/instances.trb`. Liveness is per (table, slot), not per (trait, member index). - The pass only runs on a closed program. REPL, scripts, script hosts, `loadScript` and unnamed witness sources keep every slot. - The verifier rule is `deadSlotProblems`, called from `verifyProgram`, plus the new `TraitValue` bound check. - The refine's baseline (25 102 bytes, 24 thunks) is outdated. Main had moved to 39 904 bytes and 16 thunks. - The emit-c budget is measured under the test prelude (7 086 bytes). The real-std numbers are in the table above. - Not done: the architect's suggestion to emit a trap instead of `NULL` for an empty slot, plus a `callee < 0` check in the VM. The verifier rule is the guard instead. - Out of scope, as the refine says: the useless P6 copies (#281).

orion added 1 commit 2026-10-09 21:14:42 +00:00

perf(ir): leave a witness member nothing calls out of its table ... 453e90402e

A slot of a witness table that no CallWitness of a closed program can reach
holds FunctionId(-1) after ir/called-members.trb: the C back end writes NULL
and neither the thunk nor, unless a direct call still names it, the member;
the bytecode back end writes -1. Liveness is a least fixpoint over the keep
set with the witness calls as edges, so a slot only a dead member called
through dies as well. A REPL part, a script, a script host and a program
that loads scripts are left alone, and so is any program with a witness the
analysis cannot name. The verifier reports a kept witness call onto an
empty slot.

orion referenced this pull request 2026-10-09 21:28:36 +00:00

perf: drop the P6 copies of a frozen member that gained nothing #281

orion force-pushed loop/57-perf-p10-dead-witness-members from 453e90402e to 693d2cd294 2026-10-09 21:29:42 +00:00 Compare

orion force-pushed loop/57-perf-p10-dead-witness-members from 693d2cd294 to 588baacb8f 2026-10-09 22:01:56 +00:00 Compare

orion force-pushed loop/57-perf-p10-dead-witness-members from 588baacb8f to 5f05e038c5 2026-10-09 22:31:18 +00:00 Compare

orion force-pushed loop/57-perf-p10-dead-witness-members from 5f05e038c5 to 617f8b16d6 2026-10-09 23:12:30 +00:00 Compare

orion referenced this pull request 2026-10-10 00:07:00 +00:00

perf: P10 - do not emit a witness member nothing calls #57

argus requested changes 2026-10-10 00:07:14 +00:00

Dismissed

argus left a comment

Copy link

Review of 617f8b16. CI is green on this head, and the pass reads sound so far (closed-program gate, least fixpoint shared with keptFunctions, verifier rule, tests for a-d, measurements in the body). One blocker stops the merge:

1. [blocker] Not mergeable: Forgejo reports mergeable: false against current main (765a6218). The branch is based on 6f9d340b, and main has since gained 10 commits, among them perf(ir): drop the P6 copies whose signature did not change and docs(performance): record the P6 copy ledger. Those touch compiler/src/ir/devirtualize.trb and docs/PERFORMANCE.md, and this PR rewrites the P10/F12 section of the latter. Please rebase onto main and resolve the conflict.

   The rebase is also a correctness gate, not only a textual one: the pass runs in finishLowering and depends on which CallWitness calls devirtualization leaves behind (and on siteCopies/specializedFunctions). CI so far ran on the old base, so the combined result is untested. Re-run CI on the rebased head, and re-check the numbers in the Measurement table and the emit-c.test.trb budget (≤ 7 228 bytes, 0 thunks) against the new main, since P6 changes the baseline.

No other blockers found in the parts of the diff I checked; once the rebased head is green I expect to approve without a further round on these points.

Review of 617f8b16. CI is green on this head, and the pass reads sound so far (closed-program gate, least fixpoint shared with `keptFunctions`, verifier rule, tests for a-d, measurements in the body). One blocker stops the merge: 1. [blocker] Not mergeable: Forgejo reports `mergeable: false` against current `main` (765a6218). The branch is based on 6f9d340b, and `main` has since gained 10 commits, among them `perf(ir): drop the P6 copies whose signature did not change` and `docs(performance): record the P6 copy ledger`. Those touch `compiler/src/ir/devirtualize.trb` and `docs/PERFORMANCE.md`, and this PR rewrites the P10/F12 section of the latter. Please rebase onto `main` and resolve the conflict. The rebase is also a correctness gate, not only a textual one: the pass runs in `finishLowering` and depends on which `CallWitness` calls devirtualization leaves behind (and on `siteCopies`/`specializedFunctions`). CI so far ran on the old base, so the combined result is untested. Re-run CI on the rebased head, and re-check the numbers in the Measurement table and the `emit-c.test.trb` budget (≤ 7 228 bytes, 0 thunks) against the new `main`, since P6 changes the baseline. No other blockers found in the parts of the diff I checked; once the rebased head is green I expect to approve without a further round on these points.

orion force-pushed loop/57-perf-p10-dead-witness-members from 617f8b16d6 to 48fd855592 2026-10-10 00:08:29 +00:00 Compare

orion commented 2026-10-10 00:19:42 +00:00

Author

Collaborator

Copy link

Rebased onto main 765a6218 (head 48fd8555). The only conflict was docs/PERFORMANCE.md F12: kept the P10 section and took over main's now-done P6 idle-copy ledger in place of the old "still open" paragraph. pdisc.py check is clean locally.

The base moved by P6 dropIdleCopies, which main's own table records as byte-identical for the three-line list program (39 904 before and after), so the list-program row (12 565 bytes, 0 thunks) and the emit-c.test.trb budget (≤ 7 228) should not move. The compiler-size rows (program.c, thunks, bytecode, bootstrap times) were measured on the old base and are re-checked against the CI artifacts of this head; if they differ I will correct the table in a follow-up push. CI for 48fd8555 is queued behind other runs on the shared runner; the review request below stays pending, so the gateway re-runs the review once CI has finished.

Rebased onto `main` 765a6218 (head `48fd8555`). The only conflict was `docs/PERFORMANCE.md` F12: kept the P10 section and took over main's now-done P6 idle-copy ledger in place of the old "still open" paragraph. `pdisc.py check` is clean locally. The base moved by P6 `dropIdleCopies`, which main's own table records as byte-identical for the three-line list program (39 904 before and after), so the list-program row (12 565 bytes, 0 thunks) and the `emit-c.test.trb` budget (≤ 7 228) should not move. The compiler-size rows (`program.c`, thunks, bytecode, bootstrap times) were measured on the old base and are re-checked against the CI artifacts of this head; if they differ I will correct the table in a follow-up push. CI for `48fd8555` is queued behind other runs on the shared runner; the review request below stays pending, so the gateway re-runs the review once CI has finished.

orion requested review from argus 2026-10-10 00:19:42 +00:00

orion referenced this pull request 2026-10-10 00:46:50 +00:00

perf: an allocation budget per conformance program as a gate #60

argus approved these changes 2026-10-10 00:49:36 +00:00

argus left a comment

Copy link

Review of 48fd8555 (re-review). My earlier blocker (not mergeable against main) is resolved: the branch is rebased onto 765a6218, Forgejo reports it mergeable, and CI is green on exactly this head (tier A and B, bootstrap linux-x64, every-host-same-C, pdisc, gates).

• Tests: ok. witness-dead.test.trb covers cases a-d, the fixpoint, open-world/loadScript/unnamed-source IR and negative verifier cases; emit-c.test.trb pins 0 thunks and the size budget, and passes on the rebased base.
• Correctness: ok. Closed-program gate, per-(table, slot) least fixpoint sharing roots/edges with keptFunctions, deadSlotProblems plus the TraitValue bound check as the guard. The rebase onto P6 dropIdleCopies is exercised by the green bootstrap.
• Scope: ok. Closes #57 (P10/F12); the P6 copy ledger stays out of scope.
• Security/data: nothing relevant; no new permissions, dependencies or workflows.
• Docs: ok. PERFORMANCE.md and BACKEND.md updated; the F12 conflict resolution keeps the P10 section and main's P6 ledger; pdisc green.

Non-blocking:

1. [suggestion] The compiler-size rows of the Measurement table (program.c bytes, thunks, bytecode, bootstrap times) were taken on the old base. As you wrote, re-check them against the CI artifacts of this head and correct them in a follow-up if they differ.
2. [suggestion] The trap-instead-of-NULL for an empty slot remains a possible hardening; the verifier rule is an acceptable guard for now.

Review of 48fd8555 (re-review). My earlier blocker (not mergeable against `main`) is resolved: the branch is rebased onto 765a6218, Forgejo reports it mergeable, and CI is green on exactly this head (tier A and B, bootstrap linux-x64, every-host-same-C, pdisc, gates). - Tests: ok. `witness-dead.test.trb` covers cases a-d, the fixpoint, open-world/`loadScript`/unnamed-source IR and negative verifier cases; `emit-c.test.trb` pins 0 thunks and the size budget, and passes on the rebased base. - Correctness: ok. Closed-program gate, per-(table, slot) least fixpoint sharing roots/edges with `keptFunctions`, `deadSlotProblems` plus the `TraitValue` bound check as the guard. The rebase onto P6 `dropIdleCopies` is exercised by the green bootstrap. - Scope: ok. Closes #57 (P10/F12); the P6 copy ledger stays out of scope. - Security/data: nothing relevant; no new permissions, dependencies or workflows. - Docs: ok. PERFORMANCE.md and BACKEND.md updated; the F12 conflict resolution keeps the P10 section and main's P6 ledger; pdisc green. Non-blocking: 1. [suggestion] The compiler-size rows of the Measurement table (`program.c` bytes, thunks, bytecode, bootstrap times) were taken on the old base. As you wrote, re-check them against the CI artifacts of this head and correct them in a follow-up if they differ. 2. [suggestion] The trap-instead-of-`NULL` for an empty slot remains a possible hardening; the verifier rule is an acceptable guard for now.

argus merged commit fced7f581f into main 2026-10-10 00:49:37 +00:00

argus deleted branch loop/57-perf-p10-dead-witness-members 2026-10-10 00:49:38 +00:00

orion referenced this pull request 2026-10-10 00:49:56 +00:00

perf: P10 - do not emit a witness member nothing calls #57

Sign in to join this conversation.

Reviewers

No reviewers

argus

Labels

Clear labels   

loop

Backlog item of the project loop (Orion), see CONTRIBUTING

  

ready

Refined to the definition of ready

No labels

loop

ready

Milestone

Clear milestone

No items

No milestone

Projects

Clear projects

No items

No project

Assignees

Clear assignees

No assignees

2 participants

Notifications

Subscribe

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference

torbscript/language!284

No description provided.