docs/ir.btft

[table class="topnav"]
[tr]
[td class="logotab"]nscc[e]
[td][see name="index"]index[e][e]
[td][see name="nsc"]nsc[e][e]
[td][see name="ir"]ir[e][e]
[td][see name="nscc"]nscc[e][e]
[e]
[e]
 
[h1]ir: the intermediate formats[e]
 
each stage reads one format and writes the next; this page pins every one of them, versioned. a version bumps when the format changes -- the stages are written against exactly these versions and accept exactly what they emit. the version lives here, not in the files: no format carries a version line (the only header any of them has is the optional target header below), so a version is this page's name for one exact grammar: any change to a line shape or a node vocabulary is a bump, and the writer and every reader of the changed format move to it together, in the same commit -- there is never a stage that reads two versions.
 
[table]
[tr][th]file[e][th]version[e][th]written by[e][th]format[e][e]
[tr][td].toks.j0[e][td]v1[e][td]jlex0[e][td]one token per line[e][e]
[tr][td].cst.j1[e][td]v2[e][td]jparse1[e][td]s-expression tree[e][e]
[tr][td].ast.j2[e][td]v2[e][td]jscope2[e][td]s-expression tree[e][e]
[tr][td].tast.j3[e][td]v2[e][td]jtype3[e][td]s-expression tree[e][e]
[tr][td].cast.j4[e][td]v2[e][td]jdesugar4[e][td]s-expression tree[e][e]
[tr][td].lir.j5[e][td]v2[e][td]jlower5[e][td]line-based 3-address[e][e]
[tr][td].mir0.j6[e][td]v2[e][td]jselect6[e][td]line-based, vregs[e][e]
[tr][td].mir1.j7[e][td]v2[e][td]jalloc7[e][td]line-based, real regs[e][e]
[e]
 
[h2]common rules[e]
 
[ul]
[li]all formats are text; every line ends in LF; every file ends with a newline.[e]
[li]indentation is one literal tab character (U+0009) per level, and nothing else -- a tab is 8 columns for display, but a reader must reject space-indented lines, and no stage ever converts tabs to spaces (8 spaces are not a tab here; only a tab is).[e]
[li]determinism: every stage is a pure function of its input (plus, for the last stage, the target header). two runs of the same compile are byte-identical -- the test suite asserts it.[e]
[e]
 
[h2].toks.j0 v1[e]
 
one token per line: TYPE TEXT L:C, whitespace-separated, where TEXT is the raw lexeme and L:C is 1-based line:column of the token's first char. TEXT is raw EXCEPT for STRLIT and CHARLIT lexemes, which arrive \xHH-escaped (a string literal may contain spaces, which would otherwise break the one-line-one-token shape) -- jparse1 unescapes them. keywords and type names are their own uppercase token types (RETURN, I32, ...), never re-split from ident text. the last line is always "EOF - L:C".
 
[code]
GLOBAL global 1:1
I32 i32 1:8
IDENT main 1:12
LPAREN ( 1:16
RPAREN ) 1:17
EOF - 2:1
[e]
 
[h2].cst.j1 / .ast.j2 / .tast.j3 / .cast.j4 v2[e]
 
the four tree stages share one s-expression text format (jcplib::tree):
 
[ul]
[li]one node opener per line: (op atom atom ...). a node whose kids are ALL leaves renders them inline on its opener line; a node with even one non-leaf kid puts EVERY kid on its own line, indented one tab deeper, and glues its closing ) to the end of the last line of the subtree -- inline leaves never mix with below-line kids, because the reader could not recover the interleaving order.[e]
[li]atom escaping, pinned exactly: backslash -> \x5C, space -> \x20, ( -> \x28, ) -> \x29, and every other non-graphic byte -> \xHH -- so a newline inside an atom is \x0A, never a literal \n, and a line can never contain a raw space or paren. a string literal atom like "foo bar" is carried as its exact bytes and survives the format unbroken.[e]
[li]at=L:C atoms ride STATEMENT nodes only (block, decl, assign, stmt, if, while, switch, ret, break, continue, and the toplevel func/fdecl/gvar) -- pure expressions never carry one, and expression-level errors are reported at the enclosing statement.[e]
[li]: T atoms ride typed expression nodes only (jtype3 onward) plus the ret node when it returns a value -- two atoms, a bare colon then the type. the one untyped (ref N) is a function designator: a (ref N) whose N is a function's sym, which appears only as the kid of an (addr) (the &f form) and carries no : T, because a function is not a value -- the (addr) above it is : ptr.[e]
[li]symbol ids run from 1 in walk order; jdesugar4's generated tmps use negative ids (sym=-1, -2, ...) so they can never collide with a real symbol; (ref N) carries the bare id as its only atom.[e]
[li]labels are per-function: jdesugar4 owns the L0, L1, ... namespace (loop/switch lowering), jlower5 owns I0, I1, ... (its own if/else lowering) -- the two can never collide.[e]
[e]
 
per-stage node vocabularies: jparse1's header comment enumerates the full cst set ((unit), (func NAME ret=T ... (params (param NAME T)...) (body ...)), (fdecl ...), (gvar ...), (block), (decl), (assign OP ...), (stmt), (if C THEN (else ELSE)?), (while), (switch (case VAL stmt...)* (default ...)?), (ret EXPR)?, (break), (continue), (binop OP A B), (unop OP A), (addr), (deref), (preinc/postinc/predec/postdec), (call NAME ARG...), (icall CALLEE ARG...), (cast T E), (cond C T E), (sizeof T)/(sizeof E), (intlit), (charlit), (strlit), (var)). jparse1 emits (call NAME ...) for every bare-name callee and (icall CALLEE ARG...) for any other callee expression. jscope2 rewrites (var) -> (ref ID) and (call NAME ...) -> (call ID name=X ...) when NAME is a function, or -> (icall (ref ID) ARG...) when NAME is instead a variable (an indirect call through its value); (addr (var NAME)) whose NAME is no variable but a function becomes (addr (ref ID)) with the function's sym; and it adds sym=N/linkage= atoms to func/fdecl/gvar/decl/param. the v2 change is exactly this: the icall node and the function-designator (ref N) under (addr) -- v1 had neither. jtype3 adds : T to every expr and inserts (cast T ...) nodes (an icall is always : i64, its first kid always : ptr). jdesugar4 flattens bodies to {decl, assign, call, icall, if, goto, label, return} statements -- expression nodes stay full trees, annotations included.
 
[h2].lir.j5 v2[e]
 
line-based, 5-space indent (five SPACES, the one place the format indents with spaces -- it is not a tree). an optional first line is the target header:
 
[code]
target MODE [key=value ...]
[e]
 
the target header is the whole of nscc's -s state, injected by the driver between jdesugar4 and jlower5 and passed through VERBATIM by j5, j6 and j7; jemit8 is its only consumer. MODE is freestanding, with os=Linux or os=NetBSD (plus osver=, e.g. 10.99.12, when netbsd). because the mode rides in the IR itself, .lir.j5 through .mir1.j7 are self-describing and A/B tests are pure diffs.
 
after the optional header, the func header -- the line three stages must pass through intact:
 
[code]
func NAME sym=N linkage=LOCAL|GLOBAL ret=T frame=F locals=K
[e]
 
jselect6 recomputes frame (vregs get slots) and adds vregs=V; everything else survives verbatim. then the body, one instruction per line, then end. the full opcode set, enumerated with signatures (operand order: dst first, sources after; %vN is a local slot, %tN a tmp, sym=N name=X a global):
 
[table]
[tr][th]line[e][th]meaning[e][e]
[tr][td]%vN = slot T OFF(%rbp)[e][td]local N's slot (OFF = -8*(N+1)); all slot lines come before any body line[e][e]
[tr][td]param T %vN[e][td]the N-th incoming sysv arg spills into this slot, in order[e][e]
[tr][td]%tN = const T VAL[e][td]integer constant[e][e]
[tr][td]%tN = str "..."[e][td]string blob DEFINITION, numbered .LCn in first-use order (content \xHH-escaped)[e][e]
[tr][td]%tN = str .LCn[e][td]string blob REFERENCE (the same literal again -- same address, see nsc.btft)[e][e]
[tr][td]%tN = load T %vN | sym=N name=X[e][td]load local / global[e][e]
[tr][td]st T %tN, %vN | sym=N name=X[e][td]store local / global[e][e]
[tr][td]%tN = ld8 %tM[e][td]deref load (8 bytes)[e][e]
[tr][td]%tN = ld T %tM[e][td]typed load through a ptr (struct field/array element), sign/zero-extended by T[e][e]
[tr][td]st8 %tN, %tM[e][td]deref store (8 bytes)[e][e]
[tr][td]st T %tN, %tM[e][td]typed store through a ptr, at T's exact width[e][e]
[tr][td]%tN = add|sub|mul|sdiv|smod|udiv|umod|and|or|xor T %tA, %tB[e][td]binary arithmetic (sdiv/smod signed, udiv/umod unsigned -- the names are unambiguous on purpose)[e][e]
[tr][td]%tN = shl|sar|shr T %tA, %tB[e][td]shift (sar signed, shr unsigned); %tB is the count[e][e]
[tr][td]%tN = neg|not T %tA[e][td]unary[e][e]
[tr][td]%tN = cast SRC_T DST_T %tA[e][td]width conversion (sign-extend/truncate)[e][e]
[tr][td]%tN = cmp T eq|ne|lt|le|gt|ge %tA, %tB[e][td]compare, result 0/1[e][e]
[tr][td]%tN = addrof %vN | sym=N name=X[e][td]address of a local / global / function (a function's sym=N name=X is the same shape as a global's)[e][e]
[tr][td]%tN = call T sym=N name=X (T %tA)...[e][td]call; T=void drops the %tN (arg widths ride with each arg)[e][e]
[tr][td]%tN = icall T %tF (T %tA)...[e][td]indirect call through the ptr value in %tF (computed before the args); same arg groups as call, T is always i64 (nsc types every indirect call's result i64), and a discarded result drops the %tN. new in v2[e][e]
[tr][td]scall N NAME %vK (T %tA)...[e][td]a struct-returning call: the result's N words land straight in the local's slots %vK.. (word 0 in %rax, word 1 in %rdx)[e][e]
[tr][td]ret T %tN | ret void[e][td]return[e][e]
[tr][td]sret N %vK[e][td]struct return: word 0 from %vK to %rax, word 1 (N==2) to %rdx[e][e]
[tr][td]if %tN L[e][td]branch to L when the value is 0 (the else label)[e][e]
[tr][td]goto L | label L[e][td]unconditional jump / its target[e][e]
[e]
 
after all funcs: gvar NAME sym=N linkage=LOCAL|GLOBAL T VAL... lines -- one VAL for a scalar (its folded constant), one folded word per field/element for struct.NAME and [N]T globals. slots are word-addressed: an aggregate local/param takes one %vN slot PER WORD (struct field, array element), the first word carries the type and the rest carry 'word', and consecutive words run DOWNWARD (%vK at off, %vK+1 at off-8) -- field k and element i both sit at base - 8*k.
 
[h2].mir0.j6 v2[e]
 
same line shape (5-space indent, func/end/gvar at column 0), real x86 mnemonics, virtual registers %rN (one per lir %tN). the func header gains vregs=V; frame = align16(8 * (locals + vregs)). the opcode set:
 
[table]
[tr][th]line[e][th]meaning[e][e]
[tr][td]%rN = mov_imm T VAL[e][td]constant into a vreg[e][e]
[tr][td]%rN = mov T OFF(%rbp) | NAME(%rip)[e][td]load (sign-extended by T)[e][e]
[tr][td]st T %rM, OFF(%rbp) | NAME(%rip)[e][td]store[e][e]
[tr][td]%rN = ld8 %rM | st8 %rM, %rN[e][td]deref load / store[e][e]
[tr][td]%rN = add|sub|imul|idiv|imod|and|or|xor T %rA, %rB[e][td]binary (idiv/imod = signed)[e][e]
[tr][td]%rN = shl|sar T %rA, %rB[e][td]shift (value, count)[e][e]
[tr][td]neg|not T %rS, %rN[e][td]unary[e][e]
[tr][td]%rN = cast T1 T2 %rM[e][td]conversion[e][e]
[tr][td]cmp T OP A, B[e][td]compare: flags, ALWAYS immediately followed by the setcc/jcc that consumes it -- flags live for exactly one line[e][e]
[tr][td]setcc CC %rN[e][td]0/1 into %rN from the flags[e][e]
[tr][td]jcc CC L | jmp L | label L[e][td]branches[e][e]
[tr][td]%rN = lea_slot OFF | lea_glob NAME | lea_str .LCn[e][td]address of a slot / global / string[e][e]
[tr][td]argp T OFF(%rbp)[e][td]incoming sysv arg spill, in order[e][e]
[tr][td]arg T %rM[e][td]outgoing call arg, in order (then call NAME, then retv T %rN)[e][e]
[tr][td]call NAME | retv T %rN[e][td]the call and its result[e][e]
[tr][td]icall %rF[e][td]indirect call through the address in vreg %rF, in call NAME's place (args before it, retv after it). new in v2[e][e]
[tr][td]ret T %rM | ret[e][td]return[e][e]
[tr][td]str "..."[e][td]string blob content, passed through for jemit8[e][e]
[e]
 
[h2].mir1.j7 v2[e]
 
the invariant: SAME grammar as .mir0.j6, but real registers and offsets instead of vregs -- every %rN becomes -8(locals+N+1)(%rbp), and physical regs (%rax scratch, %rcx deref/shift/idiv, %rdi...%r9 args, %r11 an indirect call's target) appear only where one instruction immediately needs one. an icall %rF expands to movq %rF's slot into %r11, then icall %r11 (new in v2), which jemit8 prints as call *%r11: %r11 is sysv's scratch register, loaded after every arg register is already filled, and it is none of the arg registers, not %rax (the result) and not %rcx (arg 4). cmp -- setcc adjacency is LAW: a reader may rely on a setcc/jcc consuming the flags of the immediately preceding line. every mir0 line expands to a fixed self-contained sequence (see jalloc7's header for the full table). jemit8's only input, and it is never fed to anything else.