Expantion of VM operation slots from 96 to 104 or 120
- Lingua principale
- Rust
- Stelle
- 772
- Fork
- 352
- Merge medio
- 1g 12h
- PR unite (30g)
- 93
Descrizione
We currently have 96 operation slots of which 93 are used, leaving only 3 free. This severely limits our ability to add new instructions. For context, the expansion from 88 to 96 slots was done in #887 (motivated by #884).
We propose two options that reclaim unused opcode bits in the `11` prefix group (degree-4 operations), trading 1 or 2 extra trace columns for 8 or 24 new slots, respectively.
## Background
The 7-bit opcode space is partitioned into four groups. A more intuitive way to view them is by how each family's flags are formed under the system-wide degree-9 bound:
| Valid opcode pattern | How flags are formed | Slots | Flag degree | Remaining degree budget |
|----------------------|----------------------|-------|-------------|-------------------------|
| `0xxxxxx` | use all 7 opcode bits directly | 64 | 7 | 2 |
| `100xxx-` | force `b0 = 0`, then use the remaining 6 bits directly | 8 | 6 | 3 |
| `101xxxx` | use `e0 = b6 * (1-b5) * b4` plus `b3..b0` | 16 | 5 | 4 |
| `11xxx--` | use `e1 = b6 * b5` plus `b4..b2`, and force `b1 = b0 = 0` | 8 | 4 | 5 |
So:
- `e0` reduces the `101` family from degree 7 to degree 5.
- `e1` reduces the `11` family from degree 6 to degree 4, but only after additionally forcing `b0 = b1 = 0`.
Here is an overview over the 8 current degree-4 operations for latter use:
| Op | Opcode | b4 | b3 | b2 |
|-------------|--------|----|----|-----|
| MRUPDATE | 96 | 0 | 0 | 0 |
| CRYPTOSTREAM | 100 | 0 | 1 | 0 |
| SYSCALL | 104 | 0 | 0 | 1 |
| CALL | 108 | 0 | 1 | 1 |
| END | 112 | 1 | 0 | 0 |
| REPEAT | 116 | 1 | 0 | 1 |
| RESPAN | 120 | 1 | 1 | 0 |
| HALT | 124 | 1 | 1 | 1 |
## Option A: +1 column, +8 slots
### Design
Add one degree-reduction column:
```
e2 = e1 * b4 (= b6 * b5 * b4)
```
Remove the constraint `very_high_prefix * b0 = 0`, freeing b0 as a discriminating bit. The complementary selector `e1 - e2` (= $b6\*b5\*(1-b4$)) comes for free as a degree two selector
Each degree-4 flag now uses 3 discriminating bits (b0, b2, b3) times a degree-1 selector:
| Subgroup | Selector | Flag degree | Slots |
|----------|----------|-------------|-------|
| b4=1 | e2 | 4 | 8 (4 existing + 4 new) |
| b4=0 | e1 - e2 | 4 | 8 (4 existing + 4 new) |
All 16 flags have degree 4 which is nice, both for the current and future ops.
## Option B: +2 columns, +24 slots
### Design
Add two degree-reduction columns:
```
e2 = e1 * b4 (= b6 * b5 * b4)
e3 = e2 * (1 - b3) (= b6 * b5 * b4 * (1 - b3))
```
Remove both constraints `very_high_prefix * b0 = 0` and `very_high_prefix * b1 = 0`, freeing b0 and b1.
The asymmetric split gives three subgroups:
| Subgroup | Selector | Flag degree | Slots | Current ops |
|----------|----------|-------------|-------|-------------|
| b4=1, b3=0 | e3 | **4** | 8 | END, REPEAT |
| b4=1, b3=1 | e2 - e3 | **4** | 8 | RESPAN, HALT |
| b4=0 | e1 - e2 | **5** | 16 | MRUPDATE, CRYPTOSTREAM, SYSCALL, CALL |
The b4=1 ops, including the END/REPEAT pair which is involved in the degree 9 constraint
```
f_end * f_repeat_next * (hi_next - hi) = 0
```
stay at degree 4.
The b4=0 ops rise to degree 5 but after doing a thorough pass, it looks like all current constraints for the ops in this group should be able to absorb this degree increase. More precisely:
- **`MRUPDATE`**: participates in `no_shift_flags` and the chiplets bus request; both remain below degree 9.
- **`CRYPTOSTREAM`**: directly gates its stack-crypto constraints and a chiplets-bus request; both remain below degree 9.
- **`SYSCALL`**: feeds `control_flow`, block stack / decoder buses, and system-context transitions; these remain below degree 9.
- **`CALL`**: feeds `control_flow`, `no_shift_flags`, block stack / decoder buses, and system ctx/fn-hash transitions; these remain below degree 9.
- **Additive composites** (`control_flow`, `no_shift_flags`): dominated by pre-existing degree-5/7 terms, so adding more degree-5 terms does not raise the composite degree.
- **Stack depth**: `call_or_dyncall_or_syscall` is additive, dominated by DYNCALL (degree 5).
Guida per i contributori
Apri la guida per i contributori
Valutazione
Questa issue non è ancora stata valutata.