J to RISC-V Compiler

Context#

The source language is J, and it is not a subset of C. Jonathan Cook designed it for the course so the project would not be a standard one, and Fall 2024 was its first outing.

What J borrows from C is braces, semicolons, and the word int. Everything else is closer to Algol, and calls are statements rather than expressions, so x = f(y) is inexpressible:

function fib(int n)
{
   int a;
   int b;
   if (n <= 1) then {
      return n;
   } else {
      call fib(n + -1);
      a = returnvalue;
      call fib(n + -2);
      b = returnvalue;
      return a + b;
   }
}

else is mandatory. There is no multiplication, division or modulo; the binary operators are + - & | ^ and that is the whole list. No boolean operators, no pointers, no structs, no comments. The n + -1 is not stylistic either, and the last section explains it.

With no arithmetic beyond addition, the difficulty sits in the calling convention and the control flow rather than in expressions. Built in C with Flex and Bison across seven milestones, about 1,700 lines. The grammar, the scanner and the code generator are mine; the AST node structure and the symbol table came from the instructor as a scaffold.

Stack frames and recursion#

Through the fifth milestone there were no local variables. Every variable, including every parameter, compiled to a single static cell addressed by name. Nested calls still worked, because each callee saved the caller's return address on entry and restored it on exit.

Recursion at that stage was structurally sound and useless. Control flow returned to exactly the right place, but every activation shared one cell per variable, so the first assignment inside a recursive call overwrote its caller's state.

Local variables are what broke it. Per-activation storage needs a frame, and a frame needs a base register that does not move during expression evaluation. Milestone six introduced fp, and the prologue and epilogue roughly doubled in size. The frame is a fixed 128 bytes, with no frame-size computation anywhere.

Offset	Slot	Also
fp+124 … fp+32	96 bytes unused
fp+28	a5 spill
fp+24	a4 spill
fp+20	a3 spill
fp+16	a2 spill	local b
fp+12	a1 spill	local a
fp+8	a0 spill	param n
fp+4	saved fp
fp+0	saved ra	fp == sp
fp-4 and below	expression temporaries

fib:
        addi    sp, sp, -128    # fixed frame, every function
        sw      fp, 4(sp)       # save caller's frame pointer
        sw      ra, 0(sp)       # save return address
        mv      fp, sp
        sw      a0, 8(sp)       # spill a0 through a5, always
        ...
func_exit:                      # one epilogue, shared by every function
        mv      sp, fp          # resync: expression temporaries drift sp
        lw      fp, 4(sp)
        lw      ra, 0(sp)
        addi    sp, sp, 128
        ret

The mv sp, fp exists because expression evaluation does not reliably balance its pushes against its pops. It also conceals a bug: assigning to an array element leaks eight bytes of stack each time, which a function's epilogue absorbs on the way out, leaving the program block, which has no epilogue, as the one place it can run away into an alignment fault.

Milestone seven added return, and an early return from inside an if needs somewhere to jump to, so every epilogue was hoisted into one shared func_exit. That solved returns and locked the design, since a single exit can only restore the stack by a constant.

Generating code#

The target is RV32 under RARS, the simulator the course used, so the system calls are RARS numbers rather than Linux ones. There is no intermediate representation and no optimiser: the generator walks the AST and prints. The absence is visible in the output, where an unconditional jump is followed by a branch that can never be reached.

There is no register allocation either. t0 is a universal accumulator, and every binary operation pushes its left operand, evaluates the right, pops and combines. Nor is there a semantic pass. Name resolution lives in the Bison actions and amounts to one working check, that a variable is not used before it is declared. Type checking does not exist, which is survivable in a language with one real type.

One piece I still like: the relational generator branches to the then-label when the condition is true, so the else block is emitted first and the then block second. Laying the branches out backwards lets the comparison be emitted exactly as written, with no inversion step.

The subtraction bug#

Milestone seven added unary operators as a scanner rule matching - and ~, placed above the existing rule matching + - & | ^. Both match - at length one, and Flex breaks ties by rule order, so - became unary everywhere and binary subtraction quietly stopped existing. Two tests that had been passing stopped compiling.

Reordering the rules restores subtraction and breaks negation instead. The two are mutually exclusive by construction, and no ordering can work, because whether - is unary or binary is not a lexical property. It depends on whether the previous token was an operand, and a scanner looking at one token cannot know that.

The fix is to stop asking the scanner. Emit one token for - and let the parser disambiguate from context, with a precedence override so unary binds tighter than binary:

/* scanner.l */          /* parser.y */
\-  { return MINUS; }    %left  ADDOP MINUS
                         %right UNARY UMINUS

                         expression: expression MINUS expression
                                   | MINUS expression %prec UMINUS

That cleared two other things I had not connected to it. The grammar had been conflict-free for six milestones, and milestone seven introduced exactly one shift/reduce conflict, which was this same ambiguity surfacing a phase later. And the precedence line those rules replaced, %right ADDOP, had made every binary operator right-associative since milestone five, so 10 - 3 - 2 evaluated to 9.

That fix went in long after the course, so the public repository reports zero conflicts and compiles its whole test suite, while everything above describes a compiler that did neither.

What this shows#

The compiler works and its output runs: fib(10) is correct, and so is a linear recursion eight thousand frames deep. What it never had was any way of knowing that automatically, with no expected outputs, no assertions and nothing to run a regression against. I wrote a six-program test suite the day after the final submission, and two of the six did not compile, because of the subtraction bug from the milestone before.

Some of what remains is deliberate simplification: fixed frames, no register allocation, no optimiser. The rest is not. Declared array sizes are ignored, so a large array silently corrupts whatever follows it, and a seventh parameter reads garbage because only six argument registers are ever spilled.