[0.31][Backend] Reuse scalar stack slots and reduce temporary stack traffic #34

Activity

1. a19q3

   added this to the 0.31 milestone on Sep 21, 2026
2. a19q3

   added

   enhancementNew feature or requestNew feature or request

   on Sep 21, 2026
3. a19q3 commented on Sep 21, 2026

   

   a19q3

   on Sep 21, 2026

   CollaboratorAuthor

   More actions

   Research notes, 2026-09-21. CellScript source checked at 6d75a6e7. These are proposed experiments and decisions, not implementation results.

   There is a prerequisite before changing the allocation formula: scalar slot addresses are embedded throughout the emitter.

   A search for .id * 8 and var_id * 8 found 164 matching lines across seven codegen files at the baseline. Some are address formation, not just loads/stores; for example src/codegen/cell_ops.rs:1305. Changing only locals_size would leave those consumers using the old layout.

   A bounded route to slot reuse

   1. Introduce an explicit VarId-to-slot lookup and move scalar accesses/address formation through it, preserving the current mapping initially. Keep raw frame offsets distinct from variable identities.
   2. Compute CFG liveness to a fixed point. For ordinary scalar values, use OUT[B] = union IN[successors] and IN[B] = USE[B] union (OUT[B] - DEF[B]), with actual instruction-level uses/defs and terminator operands. Do not substitute source lexical scope or a single linear block ordering for liveness.
   3. Assign deterministic slots only to compatible, non-interfering values. Keep address-exposed storage, wide fixed bytes, runtime buffers and outgoing arguments out of the initial reuse set unless a separate proof admits them.
   4. Handle stack-traffic elimination independently. Reusing two slots does not by itself eliminate either value's store.

   LLVM's StackSlotColoring implementation checks live-interval interference, keeps stack IDs separate, and adjusts shared slot size/alignment. It is a reference for those constraints, not a drop-in analysis for CellScript IR. LLVM's lifetime semantics also underline that explicit object lifetime is stronger information than a last textual use; CellScript must establish its own contract rather than inherit LLVM's undefined-behavior assumptions.

   Measure the addressing threshold as well as frame size

   src/codegen/frame.rs:185 uses a direct stack access when the offset fits the signed immediate, and otherwise materializes an address. Moving a frequently accessed aligned slot from offset 2,048 to 2,040 changes this path. Add fixtures on both sides of that boundary; frame reduction can produce a discontinuous code-size/cycle improvement there.

   Conversely, a smaller scalar region can leave the reported maximum frame unchanged if an entry adapter still dominates. Record per-entry frames and access counts, not only the maximum.

   Suggested decision: start with centralized slot lookup and conservative scalar reuse. Keep call-crossing register retention and helper scratch reuse as separate experiments. Tests should include loop backedges, diamond joins, multiple definitions where admitted, address-exposed values and calls with more than eight flattened ABI arguments. No allocation change or measured saving is claimed here.
4. a19q3 commented on Sep 23, 2026

   

   a19q3

   on Sep 23, 2026

   CollaboratorAuthor

   More actions

   Review after the 0.31 implementation, 2026-09-23.

   D5 is implemented at 65df937f. The allocator computes CFG liveness and interference, keeps all parameters mutually distinct for entry spills, and assigns scalar slots deterministically. Pointer/resource/wide/external-call and unclassified cases conservatively retain their original layout. The implementation report records the separate address-lookup identity check and final scalar measurements; backend and CI passed.

   There is one reporting item to finish in addition to review: the final scalar rows contain ELF bytes, cycles and stack metrics, but do not expose separate load/store counts. This issue's acceptance explicitly asks for them. Add a small before/after table from the exact artifacts, defining whether counts are static instructions or executed memory operations. A frame reduction does not establish reduced memory traffic. If dynamic traffic instrumentation is deferred, record that explicitly and retain a bounded static instruction-count comparison for the current claim.

   The boundary review should trace joins, loop backedges, terminators, simultaneous parameters, values live across calls, outgoing argument isolation and fallback selection. Map those checks to existing tests and inspect whether any source-map/checker location statement could imply a lifetime guarantee that the reused offset alone does not prove.

   The 260-overlapping-scalar fixture improves from 16,384 → 10,024 ELF bytes, 12,441 → 9,259 successful cycles, and 10,736 → 8,656 bytes of static call-chain stack bound. Publish those together with the traffic table and the retrievable baseline requested in #35.

   General register retention and helper-scratch reuse remain separate follow-ups under accepted D1–D6 decisions. Finish this child with the measurement clarification, named boundary review and an evidence-linked checklist; a general register allocator is not required.
5. a19q3 commented on Sep 25, 2026

   

   a19q3

   on Sep 25, 2026

   CollaboratorAuthor

   More actions

   Engineering acceptance complete at 648bb836.

   Validation on clean commit 648bb8362a82586821c0d4ae9f8b2250dd56ab11: local dev, full ci, and full backend passed; GitHub CI also passed and retains the fresh cost/shape/strict-audit artifacts. The final clean-source cost pair passes another 6,782-metric comparison against the archived candidate. The full backend gate rebuilt pinned CKB f7fa4436 and passed the local-node 43-action, 17-Lock and 26-stateful-scenario matrix. Local acceptance report SHA-256: 8a1aeb4221409f187e82a342c7335db19432a3fd800e9182e1c65806655a889c. This is local-node evidence, not a new public-network deployment.

   The acceptance map covers CFG joins/backedges/terminators, simultaneous parameter spills, internal calls and conservative exclusion of resources, pointers, wide values and unclassified operations. All scalar addresses go through the centralized lookup. Archived before/after static instruction counts show loads 49 → 43 for scalar-chain-260 and 820 → 818 for scalar-overlap-260; stores are unchanged in all nine rows. The evidence is explicitly static decoded text, not dynamic memory traffic. #39 owns register retention/helper-scratch reuse.

   Boundary review / acceptance map · attribution and exact report pairs · frozen coverage and reproduction.

   Engineering closure through 0.31 follows the maintainer’s September 25 instruction to skip #30 and exclude 0.32. Release version promotion, fresh distribution bundles, the final release gate and independent release review remain under #30. This closure neither transfers the 0.30 review waiver nor claims an independent security audit or published 0.31 release.
6. a19q3

   closed this as completedon Sep 25, 2026