[0.31][Backend] Shorten wide immediate materialization #31

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.

   The first implementation can stay within the existing instruction surface. LLVM's RISC-V immediate materializer is a useful reference: peel signed low 12-bit chunks, recurse on the remaining high bits, then emit shifts/additions while unwinding; sparse constants allow larger shifts. Its RV64 base cases also explain why blindly using LUI+ADDI near the signed-32-bit boundary is wrong. LLVM has extension-specific alternatives that should not be imported into CellScript by default.

   A small experiment

   I wrote a separate BigInt bit-vector model with the current short ADDI/LUI/LUI+ADDI cases, signed-12-bit recursion, and coalesced shifts. It normalizes an accepted literal to its signed 64-bit bit pattern after input-range validation. No ADDIW, compressed instructions, or new ISA extensions are needed for this candidate.

   The model passed 231,462 checks: all integers from -65,536 through 65,535, 384 power-of-two boundary checks, 100,000 deterministic 64-bit samples, and six displayed examples. These checks include repeated values. It checked reconstructed bits, immediate/shift ranges, and that the candidate was no longer than the existing expansion. The longest candidate observed was eight instructions; this sampling result is not a proof of an eight-instruction bound.

   Literal	Current expansion bytes	Model candidate bytes
   0x7fffffff	60	12
   0x80000000	60	8
   0x0100000000000000	60	8
   0x8000000000000000	60	8
   0xffffffffffffffff	60	4
   0x123456789abcdef0	60	32

   For the all-ones literal, addi rd, zero, -1 produces the required bit pattern. This does not change the source language's signedness rules. For 0x7fffffff, the candidate is addi 1; slli 31; addi -1; an ADDIW-based alternative can be considered later. The RV64 specification specifies LUI's sign extension and ADDIW's 32-bit-result behavior.

   This is a host arithmetic model, not an assembler test, CKB-VM execution, or whole-ELF measurement. Existing short-form logic was modeled rather than called from Rust. Before acceptance, execute the actual emitted bytes and use a separate oracle.

   Implementation details worth deciding first

   • Introduce one typed immediate plan consumed by both sizing and emission. Preserve literal-range rejection before bit-pattern normalization. Test nonzero destination registers and x0; the model below only reconstructs a writable destination.
   • Keep the fixed entry trampoline separate. src/codegen/assembler.rs:313 deliberately fixes it at 20 bytes, with a fixed two-instruction immediate form. A global replacement of both encoders would break that contract.
   • Exercise branch relaxation, labels, source-map ranges and checker decoding after sizes change.
   • Include high unsigned policy tags in [0.31][Backend] Reduce repeated policy adapters and choose a dispatch strategy #32's tests: current tag materialization can hit this same 60-byte fallback.
   • My suggested first decision is to implement the bounded existing-ISA candidate, then evaluate ADDIW only if measured remaining cases justify extending the assembler/checker surface.

   Reproducible host model (Node.js; no dependencies)

   This standalone research script writes its JSON report under /tmp. It does not load or modify CellScript.

   const assert = require('node:assert/strict');
   const fs = require('node:fs');
   const signed = x => BigInt.asIntN(64, x);
   const bits = x => BigInt.asUintN(64, x);
   function short(v) {
     if (v >= -2048n && v <= 2047n) return [['seed', v]];
     if ((v & 4095n) === 0n && (v >> 12n) >= -524288n && (v >> 12n) <= 524287n) return [['lui', v >> 12n]];
     const hi = (v + 2048n) >> 12n;
     if (v >= -2147483648n && v <= 2147483647n && hi >= -524288n && hi <= 524287n) return [['lui', hi], ['addi', v - (hi << 12n)]];
     return null;
   }
   function plan(v) {
     const base = short(v);
     if (base) return base;
     const lo = BigInt.asIntN(12, v);
     let q = (v - lo) >> 12n;
     let shift = 12n;
     while (q !== 0n && (q & 1n) === 0n && shift < 63n) { q >>= 1n; shift++; }
     const seq = [...plan(q), ['slli', shift]];
     if (lo !== 0n) seq.push(['addi', lo]);
     return seq;
   }
   function execute(seq) {
     let r = 0n;
     for (const [op, n] of seq) {
       if (op === 'seed' || op === 'addi') assert(n >= -2048n && n <= 2047n);
       if (op === 'lui') assert(n >= -524288n && n <= 524287n);
       if (op === 'slli') assert(n > 0n && n < 64n);
       r = bits(op === 'seed' ? n : op === 'lui' ? BigInt.asIntN(32,n << 12n) : op === 'slli' ? r << n : r + n);
     }
     return r;
   }
   let checked = 0;
   const histogram = {};
   let max = 0;
   function check(v, random = false) {
     const seq = plan(signed(v));
     assert.equal(execute(seq), bits(v));
     const old = v <= 9223372036854775807n ? short(v) : null;
     assert(seq.length <= (old ? old.length : 15));
     checked++;
     max = Math.max(max,seq.length);
     if (random) histogram[seq.length] = (histogram[seq.length] || 0) + 1;
     return seq;
   }
   for (let v = -65536n; v <= 65535n; v++) check(v);
   for (let k = 0n; k < 64n; k++) for (const delta of [-1n,0n,1n]) {check(bits((1n << k) + delta));check(signed(-(1n << k) + delta));}
   let rng = 0x6d75a6e7n;
   for (let i = 0; i < 100000; i++) { rng = bits(rng * 6364136223846793005n + 1442695040888963407n); check(rng,true); }
   const examples = [0x7fffffffn,0x80000000n,1n << 56n,1n << 63n,(1n << 64n)-1n,0x123456789abcdef0n].map(v => {
    const seq = check(v);
    const old = v <= 9223372036854775807n ? short(v) : null;
    return {value:'0x'+v.toString(16),old_bytes:old ? old.length*4:60,candidate_bytes:seq.length*4,sequence:seq.map(([op,n])=>[op,n.toString()])};
   });
   const report={kind:'host BigInt bit-vector model only; not assembler or CKB-VM evidence',checked,random_samples:100000,random_seed:'0x6d75a6e7',random_histogram:histogram,max_instructions_observed:max,examples};
   fs.writeFileSync('/tmp/cellscript-031-immediate-experiment.json',JSON.stringify(report,null,2));
   console.log(JSON.stringify(report,null,2));
4. a19q3 commented on Sep 23, 2026

   

   a19q3

   on Sep 23, 2026

   CollaboratorAuthor

   More actions

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

   D2 is implemented at 65df937f. The issue's “Implementation is planned” paragraph now describes historical status. The immediate planner validates reconstructed RV64 values, shares its plan with layout/emission, and retains the non-growing fallback. The fixed entry trampoline remains separate. Backend and CI passed; see the final implementation and validation record.

   Remaining work:

   1. Have the named compiler/checker reviewer inspect signed-low-chunk decomposition, sign extension at RV64 endpoints, shift bounds, destination x0, and the stable equal-length tie-break. Confirm that sizing, encoding and branch relaxation consume the same plan and that trampoline code does not enter this path. Attach the review to the exact commit and relevant boundary/encoded-VM tests.
   2. Link a reproducible D2-only before/after comparison, alongside the final whole-compiler report. The retained intermediate reports should become retrievable with the baseline under [0.31][Cost] Extend cost budgets to rejection paths, composition, and call-chain stack use #35. Final policy savings include other passes and should not be attributed entirely to immediate encoding.
   3. Reconcile this issue's acceptance checklist with those links and the accepted D1–D6 decisions; keep review findings as concrete fixes with focused regressions and the matching gates.

   No new materialization algorithm or ISA extension is needed to finish the accepted 0.31 scope. A global-minimum proof was never the acceptance criterion. This child can complete once its implementation evidence and boundary review are accepted; version bump, fresh downstream bundles and publication belong to #30's release work.
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 D2-only control now has archived source identities, report pairs and a reproducible command. Baseline versus D2 passes 6,782 comparable metrics with no regression. For 8 actions with a 32-byte argument: ELF 11,680 → 10,000 bytes, worst successful transaction 14,158 → 13,678 cycles, selected-group rejection 12,455 → 11,975 cycles. Encoded-VM tests cover literal boundaries, x0, far branches and the fixed trampoline; no new ISA or materialization algorithm was added.

   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