# Dusk C compiler implementation details

Prerequisite: doc/hal

## How the code is generated

DuskCC is a single pass compiler. It generates its code as it consumes the
tokens, without going through an AST. This makes the compiler much simpler but
has some drawbacks, the main one being limits in the sophistication of the code
it can generate. But the end result is really not that bad. When one values
simplicity, it's worth it.

It can, however, look ahead input tokens. It has to if it wants to generate
expressions with proper precedence rules.

The general principle is simple: repeateadly parse tokens and map them to HAL
operands and operations.

When, for example, parsing "a + b * c;", it:

1. Parses "a", determines that, for example, lives in RSP+0 (through its
   declarator database).
2. Parses "+", determines that we're in a Binary Operation context, so it needs
   to look ahead.
3. Parses "b", determines that it lives at RSP+4.
4. Before generating the code, it needs to lookahead to see if there's another
   binary operator and if it has better precedence.
5. Indeed, it parses "*", so it recurses.
6. Parses "c", determines it lives at RSP+8.
7. Again, looks ahead. End of statement? good, we don't recurse.
8. Compiles "RSP) 4 +) @, RSP) 8 +) *,". Intermediate result in W.
9. We unwind recursion and let the caller know, through the ExprOp structure
   (see below), that the right hand of the "+" is in the W register.
10. We compile "RSP) +,", final result is in W.

There are, of course, many other types of C constructs to build and we won't go
over them all, but this small examples gives the general idea behind most of the
code in DuskCC.

## C Types

There are two categories of types: the base types and the complex types.

The base types are void, char, short, int and their unsigned counterparts,
uchar, ushort and uint. They are expressed as a simple number lower than $10,
with the low 3 bits being a type ID and bit 3 being the "unsigned" flag.

Complex types are structures and function signatures. They are described in the
CDecl structured described in the following section.

Some word expect only CDecl structures as their arguments (in which case their
signature will indicate "cdecl"), but some words expect either a CDecl or a base
type (in which case their signature will indicate "type"). These words
discriminate between the two through the "cdecl?" word which simply check
whether the argument is lower than $10 (no CDecl pointer will ever be lower than
$10).

Basic types are never directly associated with a variable. All declarations go
through the CDecl structure.

## The CDecl structure

C code interacts with basically 4 types of locations:

1. Global variables (absolute addresses)
2. Function arguments (PS-relative addresses)
3. Function local variables (RS-relative addresses)
4. Immediates (constants)

In the first 3 cases, interactions with those locations first require the C code
to declare those locations through declarators ("int x;", etc.). These
declarators, when parsed, are stored in a structure named CDecl which lives in
type.fs. The last case doesn't go through CDecl and is managed in the ExprOp
structure (see below).

This type is a linked list which sees multiple uses. For Struct types, fields
are stored in the LL with each member of the struct being a separate CDecl.
Also, the function local variable space is stored as a linked list of CDecl.

The basic idea of the CDecl is to bring these important informations together:

1. type: the type of the declaration, which can be a link to another CDecl, but
   also one of the basic types.
2. storage: where this declaration is stored (absolute, PS, RS). One of the
   STORAGE_* constants.
3. lvl: indirection levels of the declaration.
4. nbelem: if an array, number of elements in it. Otherwise, 0.
5. offset: offset in bytes within its parent structure. that parent structure
   might be a Struct, but also a stack frame (PS or RS).
   If storage = STORAGE_MEM, offset is an absolute address.
6. name: a string. the identifier under which this has been declared. Can be
   NULLSTR (from lib/str) in the case of anonymous structures or function
   signatures.

Examples:

uint foo(int a, short b) { uchar *y; int x; }
  name=foo type=$b storage=STORAGE_MEM lvl=0 nbelem=0 offset=abs addr
  name=a   type=$3 storage=STORAGE_PS lvl=0 nbelem=0 offset=4
  name=b   type=$2 storage=STORAGE_PS lvl=0 nbelem=0 offset=0
  name=y   type=$a storage=STORAGE_RS lvl=1 nbelem=0 offset=0
  name=x   type=$3 storage=STORAGE_RS lvl=0 nbelem=0 offset=1

NOTE: in STORAGE_PS, all variables are 4b wide regardless of the type.

The "foo" declaration is the root of a LL that contains the "a" and "b"
arguments. Local variables are temporary (not needed once the function's code
is generated) and stored in a separate LL.

struct bar { int **x; short y[42]; }
  name=bar type=$0 storage=unused lvl=unused nbelem=unused offset=unused
  name=x   type=$3 storage=unused lvl=2 nbelem=0 offset=0
  name=y   type=$2 storage=unused lvl=0 nbelem=42 offset=4

NOTE: although arrays are pointers, they have lvl=0 (unless it's an array of
pointers). In the pointer arithmetic logic, the fact that nbelem<>0 counts as an
indirection level.

The "bar" declaration is the root of a LL containing the struct's members.

void baz(bar *a) { bar x[42]; char y; }
  name=baz type=$0 storage=STORAGE_MEM lvl=0 nbelem=0 offset=abs addr
  name=a   type=CDecl ptr  storage=STORAGE_PS lvl=1 nbelem=0 offset=0
  name=x   type=CDecl ptr  storage=STORAGE_RS lvl=0 nbelem=42 offset=0;
  name=y   type=$1         storage=STORAGE_RS lvl=0 nbelem=0 offset=42*(42*2+4)

## The ExprOp structure

C expressions are composed of operators which deal with one or two operands and
return one result. Those operands and results are passed around as the ExprOp
structure defined in expr.fs.

ExprOp structures are ephemeral and only used in the context of generating an
expression. They're discarded afterwards. For this reason, they're created in
the system scratchpad. No need to worry about freeing them.

The base building blocks of an expression are twofold: a identifier referring to
a CDecl or a constant. So far, so good.

Because DuskCC builds upon the HAL and that almost all HAL operators revolve
around the W register, the result of a C operator is always the W register. So
there's a third building block for you.

In complex expressions, we need to keep multiple intermediates around. For that,
we use PS as a temporary location, which we'll refer to later as we resolve the
expression. That's your fourth building block right there.

These are the four main result types, which all have constants in the ExprOp
namespace: CONST, W, CDECL, PS. Other types are for special circumstances.

The goal of the ExprOp structure is to keep track of where the operands live at
so that we can generate the proper HAL operands to feed to the HAL operators
we're generating.

As illustrated earlier, the expression generation mechanism is recursive so we
always start out at the deep end of the expression, with either a constant or a
CDecl created in parseFactor. It is at this point that the ExprOp's "base"
attributes, "cdecl" and "lvl" are set.

When an operator is applied, we generally end up with a ExprOp "upgraded" to W.
Then, we either bring in a new ExprOp in the mix (binary operator) or tranform
the existing ExprOp (unary operator) which already lives in W.

Upgrading results to W needs to be done carefully because there's only one such
register. Because of that, the ExprOp structure keeps track of whether W is used
globally through its "currentW" static variable. For this reason, it's important
to "release" ExprOp structs when they're finally consumed.

Then, this ExprOp is either used as an operand of an assign operatorm used as a
call argument, or used as a return value. The cycle is complete.

## :hal# vs :hal$

The main purpose of a ExprOp is to, at some point, produce a HAL operand (or to
"be W"). This is done through the :hal# ( self -- halop ) method. This method
works for CONST, CDECL and PS types, but not for W because even though it's
technically possible to produce a HAL operand for W (the "W)" operand), this
isn't ever supposed to happen. That's why there's this "#" at the end (for
"assert"), because we abort when it doesn't make sense.

This method produces the right halop for the right context, including
indirection levels and operand size.

Once a HAL operand has been generated, we usually don't reuse the ExprOp because
the resulting operation lives in W. To protect us from ourselves, it's better to
use the ":hal$" method which additionally releases the ExprOp (sets it to NONE).

## A register usage

The A register is used in some places during code generation, but only in
contexts that resolve immediately. Results stored in there can't be, for
example, still stored when a function call is generated.

In binary operations, resolution order of the two operands is important with
regards to the A register. Whichever operand ends up in W, we need to resolve
it first because this resolution might use the A register. If the other operand,
the one ending as the HAL operand argument, generates its HAL operand first and
turns out to live in the A register, W resolution might end up overwriting that
value.

## ExprOp indirection levels

An important challenge in the CC is to know when we've "hit bottom" in the
indirection chain, that is, the moment at which the instruction acquires the
width of the base type (32-bit, 16-bit or 8-bit).

A CDecl has a "lvl" attributes which indicate the indirection level of the
declaration (with a ":lvl" helper that conditionally adds 1 to it for types that
"naturally" yield references), so that's our starting point.

On top of that, the ExprOp also maintain its own "lvl" variable. This is because
some operators (such as *, &, -> etc.) change the indirection level. So, when a
ExprOp is created from a CDecl (which is the majority of the cases), it inherits
its "lvl" from "CDecl :lvl", and keeps track of indirection levels from there.

When that "lvl" hits 0, we know we've hit bottom, so that's when we apply width
to our instruction.

Another use for that "lvl" is for pointer arithmetics. As you know, "p + 1" when
"p" is a "int*" actually generates "p + 4". We perform this mangling when "lvl"
is more than 0 and that the other side of the operator is a lvl0 operand.

## Caller save

Native words don't save registers they use. For Forth words, it doesn't matter
much because all words are "atomic". Once they return, register values don't
matter anymore. Some native words call each other and in this case, careful
threading is necessary, but otherwise, it works well as is.

When other languages are concerned, however, this attribute becomes important
because if a C expression calls a Forth word, then it loses register values.

Therefore, it's important to remember that in Dusk OS, it's the caller's
responsibility to save/restore registers around a call.

## Stack frames

In C-compiled code, local variables and arguments being passed during function
calls are placed on something called a stack frame.

In Dusk, we have two stack frames. The "arguments" frame lives in PS and the
"local" frame (for local variables) lives on RS.  The caller of a C function
has to allocate enough space to place the arguments it's passing to the
function. When you think about it, it's the same thing as with Forth words.

When the function begins, it allocates enough space for its local variables on
RS. It also pushes (with "dup,") the value of its W register to PS so that it
becomes free for computation (and that PSP+0 points to the last argument).

When executing a complex expression, temporary space is needed to store
intermediate results. We push those intermediate results to PS. To ensure that
we can always access the arguments frame as well as the previously pushed
temporary values at the correct offset, we keep track, at compile time, of PS
grows through the "psoff" (PS offset) variable. This starts at 0 regardless of
argument frame size, and increase by 4 each time we push. We then adjust all PS
accesses by this offset.

To minimize the number of "ps+," operations in a function, we don't free PS
after each statement, although temporary values are never needed across
statements. We keep psoff as-is and reset it to "neutral" position only at
branches and function returns.

When the function returns, it frees the local frame from RS. It also adjusts
PSP according to the function's "argument balance". If it returns more arguments
than it received, PS will grow, if it returns less arguments than received, PS
shrinks. Then, we return.

Let's use an example:

int foobar(int a, int b) {
    int x = 42;
    return a+b+x;
}

The HAL equivalent for this is:

code foobar ( a b -- n )
  dup, -4 rs+,
  42 i) @, RSP) !,
  PSP 4 +) @,
  PSP) +,
  RSP) +,
  8 ps+, 4 rs+,
  exit,

For Forth, this function can be called like this:

1 2 foobar . \ prints "45"

## pspush() and pspop()

Builtin functions pspush() and pspop() allow for direct control over PS. This
gives you the ability to pop or push a variable number of arguments from/to PS.

These functions, however, are incompatible with arguments and return values. If
you use both at the same time, they'll mess your PS stack. You can only use them
in functions that have a "void (void)" signature. Let's see an example:

void foobar() {
    int b = pspop();
    int a = pspop();
    int x = 42;
    pspush(a+b+x);
}

This word is functionally identical to the previous "foobar()", but the HAL will
look like this:

code foobar ( a b -- n )
  dup, -12 rs+,
  PSP) @, RSP) !,
  PSP) 4+) @, RSP) 4 +) !,
  42 i) @, RSP) 8 +) !,
  RSP 4 +) @,
  RSP) +,
  RSP) 8 +) +,
  PSP) !,
  8 ps+, 12 rs+, drop,
  exit,

As you can see, it's less efficient than the first version, but it can be useful
in siutations where the number of arguments is variable.
