Dirac notation as expressions, computed in loops¶
Status: parked on 2026-10-26, resumed on 2026-10-29 (Luciano, issue
#18) as a compiler change only: the loops are generated in software with
today’s instruction set, and the pointers and RPT of section 6 are not
adopted for now (section 8). Step (a) of section 5, the grammar, the tree
and the shapes with the code still unrolled and every golden identical,
is in main (from commit 20112ab, tag archive/dirac-parser); step (b),
the loops in software, was done on 2026-10-30 (section 9); step (c), the
unrolled generators removed, on 2026-10-30 too (section 1.2 describes them
as they were; the shift register exec_shift stays). Decision (Luciano, 2026-10-25): the
Dirac notation of C± stops being a closed set of grammar rules, one per
form, each with a generator that unrolls the computation, and becomes
expressions in the parser: every operator a node of the tree, with shape
rules (a vector of N, an N×M matrix, a bra or a ket) and a compile error
when the shapes do not match. The code is generated as loops in software.
Choosing, later, between the software loop and the array unit
(array-unit.md, parked as well) is separate work; nothing
here depends on that unit. Section 6.8 compares the two.
Marks: fact (read in the code, with file and line), measured (run on the study’s branch, method given), deduced (reasoned, not run).
1. Why the unrolled form cannot stay¶
1.1 Program size and time grow with N² (measured)¶
Every Dirac form is unrolled at compile time: one group of instructions per
element, no loop. To see what that costs, proc_rls (the RLS fixture,
Compilers/CMMComp/Tests/proc_rls) was compiled with every [4] replaced by
[N] and the read of x (x # fin(0)*0.001 -> |x⟩;) repeated N times, as
the fixture repeats it 4 times. Words: n_ins in app_log.txt. Clocks: a
probe on the core counts the clocks between the first OUT of two loop turns
(an OUT that follows at least 8 clocks without one). Commit 46f4067
(the main of 2026-10-25), built with
make CFLAGS="-O2 -Wall -Werror", Icarus Verilog.
N |
words of program |
bits per word |
clocks per turn |
|---|---|---|---|
4 |
335 |
16 |
307 |
8 |
1091 |
18 |
1011 |
16 |
3947 |
19 |
3667 |
32 |
15035 |
21 |
13971 |
128 |
232091 |
25 |
not simulated |
At N = 4 the output is the fixture’s golden, bit for bit.
The two series follow
words = 14N² + 21N + 27,
clocks per turn = 13N² + 20N + 19,
exactly at every point measured (words at all five, clocks at N = 4, 8, 16
and 32; the clock formula, fitted on 4, 8 and 16, predicted the 13 971 of
N = 32 before it was simulated). At N = 32 the 400 values of the input file
run out after the first turn; the clocks do not depend on the data, since
no branch of the program does. At N = 128 the clock formula gives 215 571 clocks per turn
(deduced). The N² terms are the unrolled forms: per turn, |P|x⟩ costs 3
instructions per element of P, |P| - |K⟩⟨Px| 5, 1.010101|P| 3, and the N
shifts of x 2 per element each, 13 in all; the words add the one-time
1000.0|I|.
At N = 128 the program is 232 091 words of 25 bits, 5 802 275 bits. The DE10-Nano’s Cyclone V has 553 M10K blocks (the count Quartus reports for the device in the fits of the array-unit work), 553 × 10 240 = 5 662 720 bits: the program memory alone would need more block memory than the whole chip has, before the data memory (16 908 words at N = 128). Compiling it took 43 s.
1.2 Every combination is a rule and a generator (fact)¶
(Before step b; the generators below were removed in step c, 2026-10-30,
and the line numbers are those of that time.) There are no Dirac
expressions in the parser. Each form is a statement rule
of its own in Compilers/CMMComp/Sources/CMMComp.y, built into a
STMT_DIRAC node tagged with one dirac_op (Compilers/CMMComp/Headers/ast.h
244-255), dispatched in stmt_emit (Compilers/CMMComp/Sources/ast.c
1289-1300) to one generator in Compilers/CMMComp/Sources/stdlib.c:
form |
rule ( |
generator ( |
|---|---|---|
|
509 |
|
|
426 |
|
|
207 |
|
|
427 |
|
|
208 |
|
|
428 |
|
|
429 |
|
|
430 |
|
|
431 |
|
|
432 |
|
|
433 |
|
|
434 |
|
|
340 |
|
|
435 |
|
The generators take about 940 lines of stdlib.c (2617 to 3562), most of it
the same checks repeated in each. A new combination, |a⟩ - |b⟩ or
|A| + c|a⟩⟨b| or ⟨a|M|b⟩, needs a rule, a dirac_op, a constructor, a
case in stmt_emit, a generator with its checks and its type cases, a
prototype in stdlib.h and an MSG_INFO_DIRAC_* message: about eight places
for each form, and the forms multiply with every operator added. The
issue #18 lists seven families still missing.
2. Defects and limits known today¶
The full survey is in issue #18. Measured on the study’s branch with small programs compiled and simulated (2026-10-25):
what |
expected |
today |
where |
|---|---|---|---|
|
10 30 20 60 |
10 20 30 60 |
|
|
90 170 280 340 |
90 180 270 340 |
|
|
2 1 |
2 2 |
|
|
6 0 0 |
0 0 0 |
|
All four are fixed by step (b) (section 9), and the fixture dirac_shapes
checks each against values computed apart from YANC.
The fixtures missed the first three: in proc_rls the outer product is
K Pxᵀ with K = g Px, symmetric up to rounding, and |P| - |K⟩⟨Px| writes P
in place at the same element; dirac_assign never outputs a matrix and its
a # |B|a⟩ has B = I.
Limits, from the code (fact) unless marked:
no
compin any form (MSG_ERR_NOT_IMPL_COMPLEXin every generator);the scalar must have the vector’s type: no int/float mix (
MSG_ERR_VARS_SAME_TYPE);with the scalar 1, every form still multiplies:
out(0, 1|a⟩)isLOD_V,MLT 1,OUTper word, and the multiplier is synthesized for it;out(p, |a⟩)without a scalar is a syntax error (issue #18);the outer product only square, a, b and A of one size, with no weight;
exec_cIindexesN*i+jwith N the number of rows and never checks that the matrix is square (deduced: a non-square matrix gets the wrong cells);the declaration forms of 1.2 are not in the manual (
docs/library.md, “Vectors in Dirac notation”, lists only the assignment forms);the grammar has one shift/reduce conflict today, with no
%expect: bison 3.8.2 reports it in the state ofA # c|B|;, wherec | B | ...could also be a bitwise or. Bison shifts, so the Dirac reading wins. The same ambiguity is the main problem of section 3.1.
3. The proposal¶
3.1 Grammar¶
The notation stays as it is written today. A Dirac term is a chain of names
between bars: ⟨a|, |M|, |a⟩, ⟨a|M|b⟩, |A|B|x⟩. Juxtaposition is the
product: c|a⟩, |a⟩⟨b|, |A||B|. Sums and differences use + and -.
In a chain, the first name is a bra (row vector) when the chain opens with
⟨, the last is a ket (column vector) when it closes with ⟩, and every
other name is a matrix. |I|, |0⟩ and |in(p)⟩ stay as they are.
The difficulty is the bar. C± keeps C’s bitwise or, so a | b | c must still
parse as (a | b) | c, and the parser must tell it apart from c|M|v⟩.
The two token strings are the same up to the last token, so no grammar with
one token of lookahead can decide where the coefficient ends. Three ways out
were compared, each as a bison prototype with the operators and precedences
of CMMComp.y (measured, bison 3.8.2):
what |
conflicts |
for |
against |
|
|---|---|---|---|---|
G1 |
keep one statement rule per form, add the missing ones |
1 today, more with each form |
no lexer change |
the problem of section 1.2 |
G2 |
a separate nonterminal |
1 (the same as today) |
no lexer change |
vector values only at statement level; a scalar coefficient with |
G3 |
Dirac terms inside |
0 |
one grammar for scalars and vectors; any context; precedence of the product set apart from |
the lexer looks at the symbol table |
Recommended: G3. The lexer already resolves every name against the
symbol table when it reads it (exec_id, Compilers/CMMComp/Sources/variaveis.c
232, with the function’s scope), so the information is at hand (fact). The
rule: a | followed, after blanks, by the name of an array (a variable with
dims set) that is not followed by [ is the token DBAR; any other |
is the bar it is today (bitwise or, or the bar that closes a matrix or a
bra). An array’s name without an index is not an operand today (measured:
int y = 3 | a; with int a[4] stops with “where’s the array index for
the variable ‘a’?”), so no program that compiles today changes meaning.
With an index it is (c | a[0]): the first version of the rule missed
that, and the fixture NegTests/dirac_or_index.cmm keeps it. |in(p)⟩ is lexed whole, like |0⟩ today,
because x | in(0) is a valid or of an input.
The grammar G3 adds to exp:
exp : ... | dirac | exp dirac %prec JUXT
dirac : DBAR ID tail | KET ID tail | EYE | VZERO | KETIN
tail : BRA | '|' | DBAR ID tail
with the product’s precedence between + - and * / %:
%left '|' ... (as today, lower)
%left '+' '-'
%left JUXT DBAR KET EYE VZERO KETIN
%left '*' '/' '%'
so 2*c|a⟩ is (2*c)|a⟩ (the coefficient computed first, as today’s rule
exp '|' ID BRA does), and |b⟩ + c|a⟩ is |b⟩ + (c|a⟩). A prototype
parser with that lexer rule (arrays named by a fixed list) printed these
trees (measured):
source |
tree |
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
and every form of section 1.2 with the tree its generator computes today.
The statements become two: ID '#' exp ';' and, for the declaration,
TYPE ID '[' INUM ']' '#' exp ';'; out(p, exp) takes a scalar or a vector
by its shape. The shift register a # c -> |a⟩ is not linear algebra and
stays a statement of its own.
Risks of G3 (deduced): a #define name after a bar is expanded after the
lexer has decided; the lexer reads one token ahead of the parser, so an
array declared and used after a bar in the same statement would not yet be
an array (no such statement exists: the declaration forms use the new name
before #).
3.2 Shapes¶
Every node of the tree gets a shape (rows, cols); a scalar is (1, 1), a ket
of N is (N, 1), a bra of N is (1, N), an N×M matrix is (N, M). A 1D array is
a ket or a bra by its place in the chain; a name in a matrix place must be
2D, a name in a vector place 1D. The rules, checked bottom-up in a pass like
typecheck_expr (ast.c 327):
node |
shapes |
result |
|---|---|---|
|
equal |
the same |
|
any |
the same |
|
any X |
X’s |
|
X (n, k), Y (k, m) |
(n, m); k = 1 is an outer product, k > 1 a sum over k |
|
take the size the context needs |
|
|
v 1D of N: X (N, 1) or (1, N); v N×M: X (N, M) |
|
|
X (1, 1) |
|
|
X (1, 1), (N, 1) or (1, N) |
A mismatch is a compile error naming the line, the two operands and their
shapes. Messages, each in messages.h with M(pt, en); the names reuse
what exists (MSG_ERR_NOT_A_VECTOR, MSG_ERR_NOT_A_MATRIX,
MSG_ERR_DIM_MISMATCH) and add, as a proposal:
name |
English text |
|---|---|
|
line %d: %s (%s) and %s (%s) do not have the same shape |
|
line %d: %s (%s) times %s (%s): %d columns against %d rows |
|
line %d: %s is %s and the expression is %s |
|
line %d: a %s where a number is needed |
|
line %d: out() writes a number or a vector, and %s is %s |
|
line %d: %s is read and written with a different index: the result goes through the temporary area (%d words) |
|
at the end of the compilation, when the area exists: its size in words, the lines that need it with the words of each, and how to avoid it (3.4, requirement 4) |
with a shape written as “a vector of 4”, “a row of 4”, “a 4x3 matrix” (in
Portuguese “um vetor de 4”, “uma linha de 4”, “uma matriz 4x3”). The
element types follow the scalar rules of typecheck_expr (int, float,
comp), so the mix of int and float is allowed where + and * allow it
today. With comp, a bra conjugates. The texts in messages.h are not
these: on 2026-10-29 Luciano approved versions in the casual tone of
cmmcomp’s other messages (“adding a vector of 4 and a 2x2 matrix? Those
shapes don’t fit, mate!”).
3.3 Into the expression tree (fact, then proposal)¶
What the tree has today:
expr_node(ast.h128-143) carries a kind, a type, a v_table id and two children; there is no shape. Codegen is deferred:ast_emit_expr(ast.c517) walks the tree post-order and calls the scalar helpers.What the walker returns is an
expr(ast.h42-45): a type and the place of a single value, the accumulator (id 0) or a variable. A vector or matrix value has nowhere to live in that result.The only Dirac node is
EXPR_INNER(ast.h68), whose children must be plain variables (ast.c742 readsn->left->id,n->right->id) and which calls the unrolledexec_vtv.The loops a lowering needs already exist as nodes:
STMT_WHILEwith thefordesugaring and its bottom test (for_bottom_test,ast.c269),STMT_ARRAY_ASSIGNandEXPR_ARRAY_INDEXwith an index expression, which emitLDI/STI(seen in the assembly of section 3.5).Literal 1 already drops out of a multiplication (
ast.c569-571) when the surviving operand has the result’s type.
Proposal: add rows and cols to expr_node and four kinds,
EXPR_DIRAC_REF (an array in a chain, with its role), EXPR_DIRAC_PROD
(juxtaposition), EXPR_DIRAC_CONST (|I|, |0⟩) and EXPR_DIRAC_IN
(|in(p)⟩); +, - and unary - stay EXPR_BINOP/EXPR_UNOP, with
shapecheck_expr filling the shape. EXPR_INNER becomes the case of
EXPR_DIRAC_PROD whose result is (1, 1). STMT_DIRAC, dirac_op, the ten
stmt_dirac_* constructors and the twelve generators of section 1.2 except
exec_shift go away. A vector-shaped tree is never handed to ast_emit_expr:
it is lowered first (3.4).
3.4 Code generation¶
Superseded by section 6 (Luciano, 2026-10-25): the loops are to take the fewest instructions possible, with small hardware if needed, so L1 below (the generic walker, 12 to 20 instructions an element) is replaced by a generator of its own for the Dirac loops. The rest of this section (the requirements on scalars, aliasing, the temporary area) still holds. That generator, with today’s instructions only, is section 9.
Three ways were weighed:
how |
for |
against |
|
|---|---|---|---|
L1 |
lower each Dirac statement to the loops and indexed accesses the tree already has ( |
every combination at once; the scalar walker’s types, mixing and folding; one code path to test; the line tables point at the Dirac line |
the code is what the general array code gives (3.5) |
L2 |
one hand-written loop emitter per operator, with |
could shave instructions |
back to one generator per operator, each with its type cases |
L3 |
keep unrolling below a size |
fastest for small N |
two code paths; the decision of 2026-10-25 is loops |
Recommended: L1, with these requirements:
The value of each element is a scalar expression tree. For a target element (r) or (r, c): a ket
|a⟩givesa[r], a bra⟨a|givesa[c],|M|givesM[r][c],c Xgivesc * X(r, c),X + YgivesX(r, c) + Y(r, c), an outer product|a⟩⟨b|givesa[r] * b[c], and a product with k > 1 becomes an accumulator:s = X(r, 0) * Y(0, c), thens = s + X(r, j) * Y(j, c)for j = 1 to k−1, in that order (section 4 says why the order matters).Scalar subtrees are computed once, before the loops, into a compiler temporary (as
exec_cvdoes with__aux_var,stdlib.c2857). That keeps today’s semantics (fin(0)in a coefficient is read once) and keeps calls out of the loops. A literal stays in place, so the folding of* 1removes1|a⟩’s multiply (issue #18).No
MLTfor an index. The 2D access of the general array code computesr*N + cwithMLT(LOD r; MLT 4; ADD c; LDI P, measured in 3.5), which synthesizes the integer multiplier in a program that may use only floats: measured, the loop version ofproc_rlsturns onMLTandSF_MLTin its processor, the Dirac version onlyF_MLT. The lowering keeps a running row offset (anADDof N per row), and an element-wise matrix operation (c|A|,|A| - |B|, the zero) runs over one flat index of N·M. The area of the extra multiplier was not measured.Aliasing. When the target is read with a different index from the one written (
a # |M|a⟩,P # |P||Q|, a transpose), the result is computed into the temporary area and copied to the target at the end, withMSG_INFO_DIRAC_TEMPon that line. Read at the same index (P # |P| - |K⟩⟨Px|, the case ofproc_rls) needs nothing: each element reads only itself before it is written.Chains are grouped to keep the work at N²:
|A|B|x⟩isA (B x), withB xin the temporary area, not(A B) x. A chain of three products alternates two blocks of the area (t1 = C x, t2 = B t1, target = A t2).One temporary area for the whole program (Luciano, 2026-10-25). A temporary lives only inside one Dirac statement, and no two statements can be inside each other: C± has no recursion, and the scalar subtrees, function calls included, are computed before the loops (requirement 2). The interrupt (
#PRACA) saves no context and does not come back to the point it left (Luciano, 2026-10-25; fact:itrforces the program counter toITRADDand no return address is kept,SAPHO/core.v152). So the compiler declares one global array,__dirac_tmp, whose size in words is the largest, over the statements of the program, of the blocks one statement has live at once (a block of N for a vector, N·M for a matrix; withcomplater, two words an element). int and float share it: a word is a word, the type is in the instructions. A program with no aliasing and no chain longer than one product has no area: no data memory is spent (pay only for what you use). The loop counters, the derived indexes and the parts computed before the loops (__dk,__dd,__dh) are numbered inside a statement and carry the name of the function (__dk3_main): a function called from a coefficient has its own and leaves the caller’s alone (corrected 2026-10-30, section 9). All these names start with__(asm-names.md, rule 2).At the end of the compilation, when the area exists, cmmcomp prints
MSG_INFO_DIRAC_TEMP_TOTAL: the size of the area, each line that needs it with its words, and how to avoid it, by cause:target read at another index (
a # |M|a⟩): write the result to an array that is not on the right-hand side, if the program has one free at that point (t # |M|a⟩;, then uset);a chain of products (
|A|B|x⟩): if the program keepsB xanyway, compute it into an array of its own in a statement before (y # |B|x⟩; v # |A|y⟩;).
The hint saves memory only when the user has an array that is free at that point; otherwise the area is the cheapest place, and the message says so.
3.5 Cost against the unrolled form¶
To have a measured stand-in for L1, proc_rls was written by hand with
for loops and indexed accesses in C±, element by element in the order of
today’s generators (the transposed index of exec_Mmvvt kept), and
compiled by today’s cmmcomp. This is the code the general array path gives,
the code L1 would hand to the walker before requirement 3.
N |
Dirac today: words |
loops: words |
Dirac today: clocks per turn |
loops: clocks per turn |
|---|---|---|---|---|
4 |
335 |
289 |
307 |
1227 |
16 |
3947 |
469 |
3667 |
15 975 |
32 |
15 035 |
709 |
13 971 |
61 623 |
128 |
232 091 |
2149 |
215 571 (formula) |
959 127 (formula) |
All measured except the two marked; the loop version at N = 8 gave 349 words
and 4287 clocks. The loop series follow words = 15N + 229 (the 15N is the
test’s own N copies of the read of x, each a loop of fixed size) and
clocks = 58N² + 69N + 23, fitted on N = 4, 8 and 16 and exact at N = 32
(61 623 predicted and simulated). At N = 4 the loop version’s output is the
golden, and the bits of P and w after the 20 turns are the Dirac version’s
(section 4).
Per element, read in the loop version’s assembly (fact) against the
unrolled code: inner product 12 instructions against 3, a row of |P|x⟩ 14
against 3, the outer-product update of P 20 against 5, 1.010101|P| 14
against 3, one step of the shift 10 against 2, one word of out 10 against
4. Both versions run close to one instruction per clock: the N² terms of the
clock formulas (13 and 58) are the sums of these counts (deduced from the
match).
What this says:
Program size stops depending on N: at N = 128, 2149 words of 22 bits (47 278 bits) against 5.8 Mbit. Already at N = 4 the loops are smaller.
Time per turn is about 4 to 4.5 times the unrolled code’s, for every N. That is the price of loops on this instruction set: a load through
LDIneeds the index in the accumulator, and the counter costs five instructions a turn (LOD k; ADD 1; SET k; LES; JIZ). The array unit of array-unit.md is one way to win that back, section 6 another; this work does not try to.With requirement 3, the matrix loops lose the
MLTand the index arithmetic: deduced, the element-wise ones from 14 to about 10 instructions per element. Not measured.A hand-written emitter (L2) for the inner product could keep the sum on the stack and save one instruction in twelve (deduced), not enough to justify a second code generator.
4. Tests¶
Same output, bit for bit. dirac_assign and proc_rls must give the
same golden_sim after the change; their golden.asm change, on purpose
(loops instead of unrolled code), and the pull request says so. That holds
if every element is computed with the same operations on the same operands
in the same order. Where the order can change:
The sum over k of an inner product or of a matrix-vector product: today from k = 0 upwards,
((p0 + p1) + p2) + .... The lowering keeps that order. A loop counting down, or a sum split in two halves, would change the bits.Operand order inside an element. Today’s generators write the element first and the scalar second (
LOD_V v k; F_MLT c, that isv[k]*c),K[k]*e + w[k]for|w⟩ + e|K⟩, and-(a[i]*b[j]) + Bfor|B| - |a⟩⟨b|. A lowering that follows the source writesc*v[k],w[k] + e*K[k]andB - a[i]*b[j]. Measured, with no#FROUND(level 0, asproc_rls): over 500 pairs of random floats,x*yandy*x,x+yandy+x,x-yand-y+xgave the same bits every time; and the loop version ofproc_rlswithP - K*Pxin place of-(K*Px) + Pleft P and w bit for bit as the Dirac version does (and saved 16 clocks a turn: oneSF_SU2per element instead ofF_NEGandSF_ADD). So the lowering may write the source’s order. Not checked at#FROUND 1and 2, whose subtraction is not the same circuit (fround1-subtraction.md): the fixture runs at level 0, so its golden is not at risk, but the claim is only made for level 0.The outer product’s index. Fixing the transposition of
exec_Mmvvtchanges which product is subtracted where: with K = g Px, the element (r, c) becomes(Px[r]*g)*Px[c]instead of(Px[c]*g)*Px[r]. Measured at N = 4, by writing the bits of P and w (throughcopyto an int) after the 20 turns: with the index fixed, 19 of the 20 words differ from today’s, in the last bits. The fixture’s output,w*1000converted to int, is still the golden at N = 4 (and with the source’s order as well). Soproc_rls/golden_simshould not change, but that is a property of this output, not of the arithmetic; the pull request says so, and if a later N or input shows a difference, it is the fix and not a regression.dirac_assignoutputs only the constant 1, so itsgolden_simholds whatever the Dirac code does. Itsa # |B|a⟩with B = I goes through the temporary of requirement 4.
A new fixture, dirac_shapes, with small integers and floats that are
exact in the float format (so the expected values are written by hand, not
taken from YANC), outputting every element:
A # |a⟩⟨b|with a = (1, 2, 3) and b = (10, 30): 10 30 20 60 30 90, the outer product in the right order and not square;A # |B| - |a⟩⟨b|andA # |B| + 2|a⟩⟨b|with B ≠ Bᵀ;a # |M|a⟩with M a permutation (the aliasing);v # |a⟩ + |b⟩,v # |a⟩ - |b⟩,y = ⟨a|M|b⟩,v # ⟨a|M|with M not square;the int shift
a # k+1 -> |a⟩;out(0, 1|a⟩)andout(0, |a⟩), thegolden.asmshowing noMLTand the processor no multiplier (issue #18);int with float:
float v[3] # k|a⟩withint k.
And a fixture of compile errors, one per message of 3.2, each checked for its line and its text in both languages.
5. Decisions (Luciano, 2026-10-25)¶
Grammar G3: Dirac terms inside
exp, the lexer’sDBARfor a bar followed by the name of an array.Code generation L1: lowering to the loop nodes of the tree; the
exec_*generators go, exceptexec_shift. Reopened the same day: section 6.Aliasing: through the temporary area, with an info line on the statement and the total at the end of the compilation, with hints (3.4, requirements 4 and 6).
out(p, X)refuses a matrix for now (MSG_ERR_DIRAC_OUT_MATRIX).compin a later step of its own (the conjugation of a bra and a fixture).No unrolling for small N (L3): one code path. At N = 2,
out(0, |a⟩)unrolled would be 4 words and 4 clocks, the loop about 10 words and 20 clocks (deduced); to be measured later if it matters.The shape names of 3.2, in English and Portuguese.
Three steps, each diff shown before its commit: (a) the tree, the shapes and the grammar, the present fixtures giving the same output; (b) the lowering to loops, the
golden.asmofdirac_assignandproc_rlschanging on purpose; (c) the generators removed, the fixturedirac_shapesand the fixture of errors.This note reaches
mainthrough its own pull request before the code.The measured defects of section 2 are fixed by the redesign, not by a patch to the unrolled generators; the CHANGELOG warns about them.
6. Loops with small hardware (prototype, 2026-10-25 and 26)¶
Luciano asked for the fewest instructions in the loops, adding
instructions if needed, within these limits (2026-10-25): no memory of
its own (no second port, not the array unit of array-unit.md: that is the
coprocessor mode, which a parameter will choose instead of this), only
small hardware (registers, counters, multiplexers), every block in a
generate and built only when the program uses it, the logic added
measured, and no path longer than today’s path through the float
adder: the clock must not drop.
Everything here is a prototype outside main, kept whole in the tag
archive/dirac-loops-proto under .smoke/dirac-proto/: a modified copy of
SAPHO/ (proto/SAPHO, made by proto/patch_core.py), a bench
(proto/bench.py) and the fit scripts (proto/map.sh, proto/fit.sh,
proto/sta.sh). No compiler emits the new instructions yet: the bench
writes them by hand.
6.1 What the pipeline allows (fact)¶
Read in SAPHO/core.v, SAPHO/instr_dec.v and SAPHO/processor.v:
every instruction takes one clock, a jump or
JIZincluded: the jump is decided in the decode and the fetch takes the target in the same cycle (prefetch,core.v95-157);the data memory has one read port and one write port, with their own addresses (
mem_addr_rd,mem_addr_wr);an instruction is decoded in cycle t (its read address leaves then), the word read arrives in t+1, the ALU works in t+1 (the ALU operation is registered in
instr_dec) and the acc is written at the end of t+1;a write happens in the decode cycle and stores
ula_out, which in that cycle is the result of the previous instruction: that is howSETworks;LDI basereadsmem[base + ula_fast];STI basewrites the acc tomem[base + stack top]and pops (mem_ctrl,core.v448-481).
One ALU means one operation a clock. With one read port, an element of an inner product costs at least three instructions (load, multiply, add), which is what today’s unrolled code takes. The write port is idle in most instructions: that is the room left.
6.2 Software only, measured first¶
Before the hardware, the best loops with today’s instructions, written by
hand, simulated, the same bits as the compiler’s (inner product of 16, 6
turns; y # |M|v⟩ of 16x16, 3 turns):
code |
instructions an element |
words |
clocks a turn |
|---|---|---|---|
inner product, the compiler’s |
12 |
57 |
199 |
sum on the stack, negative index, |
10 |
55 |
168 |
the same, unrolled by 5 |
6.8 |
79 |
120 |
|
3 |
826 |
941 |
|
4.6 |
137 |
1358 |
The negative index (from -N to -1, the base at the end of the array) lets
JIZ close the loop; the column unrolling makes the code grow with N, not
N². Both need an assembler alias LDI_V/STI_V (base plus a constant), no
hardware.
6.3 The design¶
Three blocks, each in a generate on a parameter asmcomp would set from
the program (NPTR, RPT):
Four pointers P0 to P3, each as wide as a data address. With
NPTR > 0, the top bit of a memory instruction’s operand selects the pointer mode:[1:0]k, the pointer of the instruction’s own access,[3:2]its change after the access (01 +1, 10 -1). asmcomp widens the operand by one bit, so no other operand reaches that bit (an invariant of the assembler, not checked by the hardware).SETP k a(opcode 110) loads pointer k with the address a, an immediate (every Dirac pointer starts at a constant address).A parallel store of the previous result: in pointer mode,
[4]also storesula_out(the result of the previous instruction, whatSETstores) through pointer[6:5]j, changed by[8:7]. It uses the idle write port. The compiler pipelines the loop: the load of element i stores the result of element i-1, with one instruction before and one after the loop.A zero-overhead loop:
RPT L n(opcode 111) runs the L instructions after it n times with no jump instruction. Three registers (the first address of the body, the address after it, the turns left) and a flag; when the PC is about to fetch the address after the body with turns left, the fetch takes the first address. One level; the outer loop of a matrix stays in software. No jump inside the body (a contract of the compiler). The operand holds L in 3 bits and n below it.
Opcodes 108 and 109 stay for DOT/DOB of array-unit.md. Every select reads
registers and the instruction word, never the ALU: the pointer feeds the
base input of the LDI/STI adder, whose other input (ula_fast)
comes much later, and the RPT choice is ready before the decode decides
a jump (pc_load stays the last select of the fetch address).
6.4 Measured in simulation¶
proto/bench.py: each form compiled by cmmcomp as today (the reference),
the unrolled stretch replaced by the hand-written loop, both simulated on
the same inputs (2 turns, N = 16), the output compared bit for bit, the
clocks of the stretch counted by a probe on the fetch address. All 11
give the same bits. Today’s element order is kept, the transposed outer
product included, so that the bits can be compared.
form |
words today -> prototype |
clocks today -> prototype |
the loop body |
|---|---|---|---|
|
48 -> 9 |
48 -> 51 |
|
|
768 -> 18 |
768 -> 884 |
the same, a row a turn of a software loop |
|
48 -> 8 |
48 -> 36 |
|
|
64 -> 11 |
64 -> 53 |
|
|
1280 -> 24 |
1280 -> 1189 |
4 a element |
|
1280 -> 22 |
1280 -> 933 |
|
|
768 -> 8 |
768 -> 516 |
|
|
768 -> 19 |
768 -> 676 |
|
|
17 -> 4 |
17 -> 19 |
|
|
32 -> 8 |
32 -> 21 |
|
|
64 -> 6 |
64 -> 66 |
|
F_SU2 is memory minus acc (ula.v 1626-1627: F_SU1 turns the sign of
the memory input, F_SU2 that of the acc); F_SU1 gave other bits. With
F_SU2 the bits are those of today’s F_NEG; F_ADD, at #FROUND 0; not
checked at levels 1 and 2. |M|v⟩ is 15 % slower than unrolled: 7
instructions of software loop a row; a second level of RPT would remove
them (not designed). The prototype core with NPTR = 0 and RPT = 0
gives the output and the clocks of the original (checked on |M|v⟩), and
sapho_all with the blocks on and unused gives its golden output.
6.5 Measured in Quartus¶
sapho_all (every block in, #FROUND 2) against sapho_ptr, the same
program with the operand widened from 11 to 12 bits, NPTR = 4, RPT = 1,
on the DE10-Nano (5CSEBA6U23I7), fmax.sh, seed 1, 2026-10-25:
|
|
difference |
|
|---|---|---|---|
Fmax |
32.11 MHz |
31.82 MHz |
-0.9 % |
logic (fit) |
3545 ALMs |
3643 ALMs |
+98 (+2.8 %) |
logic (synthesis estimate) |
3378 ALMs |
3467 ALMs |
+89 (+2.6 %) |
registers |
1193 |
1253 |
+60 |
program memory bits |
21,054 |
22,109 |
+1055 (one bit a word) |
The worst path is the same chain in both: the acc or the ALU input, the
exponent alignment, the float adder, the normaliser, the ALU output mux,
the stack; 30.88 ns of data path in sapho_all, 30.76 ns in sapho_ptr.
None of the 3000 worst paths of sapho_ptr (down to -20.6 ns of slack at
the 10 ns asked) touches the new blocks. Asked of quartus_sta on the same
fit, the worst paths through them, at 10 ns:
path |
slack |
about |
|---|---|---|
out of the pointers, to the data memory address |
+1.7 ns |
8 ns |
into the pointers (from the instruction memory) |
-2.0 ns |
12 ns |
out of the |
+1.6 ns |
8 ns |
into the |
-14.7 ns |
25 ns |
The last one came from the counter counting a turn only without a jump
(~pc_load), which pulled the JIZ decision, made from the ALU, into the
counter. The contract already forbids a jump in the body, so the condition
was dropped (2026-10-26): the 11 forms still give the same bits; its
path was not timed again.
The -0.9 % is one seed each: fmax.sh warns that a fit can be off by
several per cent from one seed to another. Not yet shown either way.
6.6 proc_rls whole (measured, 2026-10-26)¶
The forms of 6.4 were run one at a time. proc_rls was then run whole:
proto/rls_bench.py (in the tag archive/dirac-loops-proto, beside
bench.py, whose loops it reuses) compiles the fixture with arrays of N, as
in section 1, and replaces every Dirac stretch, in rls_update, in the N
shifts and in the out, by the hand-written pointer and RPT loops; the
initialisation (P # 1000|I|, w # |0⟩), run once, stays unrolled. Both
versions are simulated for the 20 turns of the fixture, today’s on
SAPHO/, the other on the prototype’s copy, F_SU2 in the update of P:
N |
output |
words today -> pointers |
clocks a turn today -> pointers |
|---|---|---|---|
4 |
the same bits; today’s also the golden |
339 -> 186 |
303 -> 349 (+15 %) |
16 |
the same bits |
3951 -> 570 |
3663 -> 2989 (-18 %) |
32 |
the same bits |
15 039 -> 1530 |
13 967 -> 10 541 (-25 %) |
Against the loops in software alone (3.5: 15 975 clocks at N = 16, 61 623 at
N = 32) the pointers are 5.3 and 5.8 times faster. Most of the 1530 words
left at N = 32 are the unrolled initialisation (over 1024 words) and the
test’s own N copies of the read of x; a generator would make the
initialisation a loop as well (deduced). Deduced: the loss at N = 4
is the fixed cost of each stretch, the SETPs and the 7 instructions of
software loop a row of |P|x⟩ and of the update of P; a second level of
RPT, or a pointer that walks a whole matrix, would remove it (6.7, 4).
6.7 Open, in order¶
Two more seeds of each (
proto/fit.shwithSEED=2,SEED=3, a fit about 50 minutes, one at a time) with the counter fixed, and the path into theRPTcounter timed again (proto/sta.sh).Luciano decides: these instructions, and then decision 2 of section 5 becomes a generator of its own for the Dirac loops.
In the repository, if yes:
SAPHO/core.vandprocessor.vfrom the prototype (the diff to him first, as for every HDL change), the rows ofisa.tsvand of the copiescheck_isa.pyholds to it, asmcomp (the mnemonicsSETPandRPT, the pointer syntax, the widened operand,NPTR/RPTfrom the program), the manual’s instruction reference.Open in the design: a second
RPTlevel for the rows of a matrix;comp(two words an element); whether the pointers also serve ordinary C± arrays in loops (forwitha[k]), which would speed up every program, not only the Dirac notation.Other hardware for the loops, not built (deduced, 2026-10-26): a second level of
RPT; a pointer with a programmable step (+N), so a column is walked as easily as a row (transpose,⟨a|M|, the outer product without swapping the loops); a pointer with row and column counters that walks a whole matrix in one loop; a decrement-and-jump counter in place ofRPT(one clock a turn more, nothing in the fetch); pointers alone with the loops unrolled by 4 or 8. Left out: a float multiply-add in one clock, which would put the multiplier in series with the float adder, today’s worst path.
6.8 Against the array unit¶
The two designs answer the same question, faster array code, at different costs, and do not exclude each other (a parameter could choose):
pointers and |
array unit (array-unit.md) |
|
|---|---|---|
logic |
+98 ALMs (one seed) |
about +920 ALMs, 1 RAM block, 1 DSP block |
memory |
today’s |
a second, dual-port memory for the arrays |
clock |
-0.9 % on one seed, not yet repeated |
below what three seeds resolve |
inner product, a word |
3 clocks |
1 clock |
results |
the bits of the loop in software |
the MAC rounds once: other bits |
compilers |
a loop generator, two instructions |
two address spaces, the S bit, more |
Deduced: over the pointers, the unit speeds up the N² parts of
proc_rls 2 to 3 times, not the tenfold it shows over loops in software;
any later decision on the unit is to be weighed against the pointers.
7. For the documentation (issue #40)¶
Done with step (b), on 2026-10-30: docs/library.md, “Vectors in Dirac
notation”, says each point below, with the measured table of section 9
in place of that of 3.5.
The manual (docs/library.md, “Vectors in Dirac notation”) replaces the
table of forms with the rules: what a chain between bars means (bra, ket,
matrix by place), that juxtaposition is the product and binds tighter than
+ and looser than *, that the shapes must match and what the error says,
that a scalar in an expression is computed once before the element loop,
that int and float mix as in scalar expressions, when a statement uses the
temporary area and how to avoid it (the end-of-compilation summary of 3.4),
that out() does not take a matrix, and the forms the old table
listed as examples, including the declaration form float v[N] # ...,
which the manual never listed. It says that the code is a loop: its size
does not grow with the arrays, and it runs about four times slower per
element than the unrolled code of earlier versions, with the measured table
of 3.5. It says that a program which wrote A # |a⟩⟨b| or
A # |B| - |a⟩⟨b| with versions up to this one got the outer product
transposed, and that a # |M|a⟩ and the int shift of an expression were
wrong, so that results computed with them need checking. The CHANGELOG says
the same, and that golden.asm of dirac_assign and proc_rls changed.
8. Where it stopped, and how to resume (2026-10-26)¶
Parked by Luciano on 2026-10-26, with main back to its own line of
releases. Nothing of it is in main but this note; the code is in tags:
archive/dirac-parser: this note’s history and step (a), the parser with shapes (commit 20112ab), every golden identical, twelve negative tests inCompilers/CMMComp/NegTests/.git switch -c <branch> archive/dirac-parsergives it back as a branch;mainhas moved since, so it is merged withmainfirst.archive/dirac-loops-proto: the prototype of section 6 under.smoke/dirac-proto/(the SAPHO copy,bench.py,rls_bench.py, the fit scripts and their logs).
Where it stopped: section 6.7, item 1 (two more seeds of each fit, the
RPT counter’s path timed again), then Luciano’s decision on the
instructions of section 6 (item 2). Step (b) of section 5 follows from
that decision: a loop generator with the pointers, or loops in software.
Resumed on 2026-10-29. Luciano chose loops in software, with no
change to SAPHO: the pointers and RPT stay a measured option (section
6), not adopted. Step (a) was merged with main and brought in; step (b)
lowers the Dirac terms to loops with today’s instructions, with the
temporary area of 3.4. Luciano asked (2026-10-29) that proc_rls be
checked against an RLS computed apart from YANC, not only against its
recorded output. The plan was to bring rls_bench.py (tag
archive/dirac-loops-proto) into the regression, but read again on
2026-10-30 it is not such a reference: it compares the unrolled code with
hand-written pointer loops, on the prototype’s SAPHO, from paths outside
the repository. The reference is Scripts/rls_ref.py instead (section 9).
No check of proc_rls’s output can show the transposition of section 2:
its outer product is symmetric.
9. Step (b): loops in software (2026-10-30)¶
Luciano’s words for it: the leanest code possible, with new virtual
instructions if needed, no hardware. Code in
Compilers/CMMComp/Sources/dirac.c; ast.c checks shapes and target and
hands the tree over.
Two virtual instructions. LDI_V x k and STI_V x k are LDI and
STI (opcodes 3 and 7) with a constant k added to the base, as LOD_V
is LOD with one: rows of isa.tsv, ASMComp.l, pass1.l and
asm_share.c, nothing in SAPHO. A loop counter runs from -n up to 0, so
the JIZ after its increment closes the loop with no comparison (the
for of C± tests with LES every turn), and the base sits at the end of
the array: LDI_V a 4 with the counter at -4 reads a[0].
How an element is computed (fact, dirac.c). For each element of the
result the Dirac tree becomes a scalar expression tree: |a⟩ at row r is
a[r], |M| is M[r][c], c X is X(r, c)*c (the element first, the
scalar second, as the old generators), a product of inner size k is a sum
over k. The scalar walker (ast_emit_expr) emits that tree, with its
types, its mixing of int and float and its folding (1|a⟩ has no
multiply); the array reads are new leaves, EXPR_DIRAC_ELEM, and the sums
EXPR_DIRAC_SUM. Further:
a sum keeps its partial result on the stack; its first term is taken out of the loop, and a cell at index 0 is the array’s own name, a memory operand:
⟨a|b⟩startsLOD a; F_MLT b. A sum of 2 terms has no loop;an index of a matrix is a sum of loop variables, never a multiply: a loop’s counter steps by the stride its index is used with most deeply (the row length for the rows of
|M|x⟩), and another stride gets a variable stepped with the counter (requirement 3 of 3.4);a matrix expression that only adds and scales matrices of the target’s shape runs over one flat index;
what does not depend on the inner loop is computed at the top of the outer one (
K[r]in|K⟩⟨Px|), and a scalar that is not a literal or a variable before the loops (requirement 2), converted once when the elements are float and it is int;the target read at other cells than the one written goes through
__dirac_tmpand is copied back (requirement 4); a product inside a chain that does not depend on every loop around it is computed into__dirac_tmpfirst, and a chain closed by a ket is read from the right,|A|B|x⟩asA (B x)(requirement 5). One area for the program, as large as the largest statement needs, declared after#PRNAMEat the end of the compilation (requirement 6);the shift register stays
exec_shift, unrolled (2 words an element); its int case of section 2 is added.
Instructions per element in the loop body, read in the assembly of
proc_rls (fact), against the unrolled code and the for loops of 3.5:
form |
unrolled |
|
loops of step (b) |
|---|---|---|---|
|
3 |
12 |
10 |
a row of |
3 |
14 |
11 |
|
5 |
20 |
13 |
|
3 |
14 |
9 |
|
3 |
9 |
|
|
4 |
12 |
|
|
4 |
10 |
9 |
|
1 |
7 |
Five of each are the loop (LOD k; ADD 1; SET k; JIZ; JMP, or P_LOD k
first in a sum), and a store takes two (PSH of the index, STI_V).
Measured with the method of 1.1 (proc_rls with arrays of N, Icarus,
clocks between the first OUT of two turns), main at 515de8f (the
unrolled code, whose numbers are those of 1.1) against this branch:
N |
words, unrolled |
words, loops |
clocks a turn, unrolled |
clocks a turn, loops |
|---|---|---|---|---|
4 |
335 |
235 |
307 |
855 |
8 |
1091 |
343 |
1011 |
2811 |
16 |
3947 |
751 |
3667 |
10 083 |
32 |
15 035 |
2335 |
13 971 |
38 067 |
The loops follow clocks = 35N² + 69N + 19 (fitted on 4, 8 and 16, exact at
32) and words = 2N² + 3N + 191, whose 2N² are the test’s own N unrolled
shifts. The two give the same output over the five turns both simulate
at every N. Per turn the loops take 2.7 to
2.8 times the unrolled code’s clocks, and 0.62 to 0.70 times those of the
for loops of 3.5 (58N²).
Tests. dirac_shapes (new): every element of 49 Dirac statements, int and
float, the outer product not square, |B| ± |a⟩⟨b| with B not
symmetric, a # |M|a⟩ and C # |M||C| through the temporary area,
chains, ⟨a|M|, the int shift, |in(p)⟩, out of a vector, 160 values;
its golden is written by Scripts/dirac_ref.py, the same statements in
Python on integers the float format holds exactly, and the regression
checks that it still is. Scripts/rls_ref.py computes the RLS of
proc_rls in double precision from its input files: the recorded output
is that filter’s, with no difference in any of the 80 words. Measured by
changing the filter there: without the update of P the largest difference
is 4348, with P started at 10 instead of 1000 it is 653, but a forgetting
factor of 1 gives 0, and so does the transposition, so this checks the
filter as a whole and dirac_shapes the details. cases.tsv has 176
combinations. proc_rls/golden_sim is unchanged; dirac_assign, which
writes 1 in a loop forever, writes 195 of them in the regression’s
100 000 clocks instead of 812 (the same values).
Corrected after the audit of 2026-10-30. Three defects of this step,
found by reading dirac.c and checked by compiling, each one now in
dirac_shapes, which the code before the correction fails (x came out
1838 instead of 1847):
a Dirac number inside a scalar expression whose chain went through the temporary area overwrote the value the walker held in the accumulator (
x = x*3.0 + ⟨a|M|M|M|e⟩gave 0 + the number): that value now goes to a variable before the first instruction of the number;the product of a chain went to
__dirac_tmpbefore the parts computed before the loops, so a function called from a coefficient that has a Dirac statement of its own overwrote the block before it was read: the parts now go first, and the statement is built again reading them;the compiler’s variables had the same names in every function, so that call also overwrote the caller’s coefficients: they now carry the function’s name.
Also: the left operand is built before the right one (C left the order to
the host compiler, and with it the order of two in(p) and the
numbering of the variables). The compiler’s own tables grow as a statement
needs: before, a statement stopped at 64 loops (63 sums such as |M|a⟩
measured), 64 parts computed before the loops or 8 row lengths read by
one loop (7 matrices of different widths measured), sizes picked when the
code was written, with no reason in the hardware, and the sets of loops
were 64-bit masks; they are now questions to the tree (dep_on).
Step (c), 2026-10-30. The eleven generators of 1.2 (exec_vtv to
exec_vout, 840 lines of stdlib.c) and the twenty messages only they used
are gone; nothing reached them since step (b) (Scripts/cmm_cov.sh, issue
#69: no test and no grammar rule did). The shift register exec_shift
stays.
Open. |I| inside a larger expression, and |I| or |0⟩ inside
a chain (a syntax error today). comp (decision 5). An int counter of
an index past the word: at #NUBITS 8 a flat loop over more than 128
cells overflows (deduced, as a for would; not checked). Unrolling a loop
of very few turns, which decision 6 left out: at N = 2 the loop costs more
than the unrolled code in words and in clocks (deduced).