commit 81ca07ab3320418a73aa1b80dd737df007fffc70
parent da8a77a17bd3e28d40a5ea34c75137acfc09cabb
Author: Virgil Dupras <hsoft@hardcoded.net>
Date: Sun, 26 Mar 2023 14:00:50 -0400
halcc: improve impl docs
Diffstat:
| M | fs/doc/cc/impl.txt | | | 241 | ++++++++++++++++++++++++++++--------------------------------------------------- |
1 file changed, 85 insertions(+), 156 deletions(-)
diff --git a/fs/doc/cc/impl.txt b/fs/doc/cc/impl.txt
@@ -1,5 +1,44 @@
# Dusk C compiler implementation details
+## 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 Result 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.
+
+## The Result structure
+
+TODO
+
## Caller save
Native words don't save registers they use. For Forth words, it doesn't matter
@@ -13,7 +52,7 @@ 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.
-## Function call stack frame
+## Stack frames
In C-compiled code, local variables and arguments being passed during function
calls are placed on something called a stack frame.
@@ -24,12 +63,26 @@ 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. Its arguments are already on PS, where they should be, so it does nothing.
+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.
+shrinks. Then, we return.
Let's use an example:
@@ -38,49 +91,20 @@ int foobar(int a, int b) {
return a+b+x;
}
-For Forth, this function can be called like this:
-
-1 2 foobar . \ prints "45"
-
-Here's what PS and RS look like at the moment foobar is called:
+The HAL equivalent for this is:
- |-----------| |-------------|
- PSP+4 ->| $00000001 | RSP+0 -> | return addr |
- PSP+0 ->| $00000002 | |-------------|
- |-----------|
+code foobar ( a b -- n )
+ dup, -4 rs+,
+ 42 LIT>W, RSP) !,
+ PSP 4 +) @,
+ PSP) +,
+ RSP) +,
+ 8 ps+, 4 rs+,
+ exit,
-During the function prelude, PSP doesn't change, but the compiler assigns each
-argument to its proper place in PS.
-
-At the same time, the prelude also decreases RSP by 4 to make space for local
-variables:
-
- |-----------| |---------------|
- PSP+4 ->| int a = 1 | RSP+4 -> | return addr |
- PSP+0 ->| int b = 2 | RSP+0 -> | int x = undef |
- |-----------| |---------------|
-
-Then, we execute "int x = 42", which sets RSP+0:
-
- |-----------| |---------------|
- PSP+4 ->| int a = 1 | RSP+4 -> | return addr |
- PSP+0 ->| int b = 2 | RSP+0 -> | int x = 42 |
- |-----------| |---------------|
-
-Then, "return a+b+x" does a "soft" push to PS, that is, it pushes to PS as if
-the arguments had been popped during the prelude. This means that our return
-value overwrites "a". PSP is increased by 4:
-
- |-----------| |---------------|
- PSP+0 ->| $0000002d | RSP+4 -> | return addr |
- PSP-4 ->| int b = 2 | RSP+0 -> | int x = 42 |
- |-----------| |---------------|
-
-Then, before returning, we deallocate the local stack:
+For Forth, this function can be called like this:
- |-----------| |-------------|
- PSP+0 ->| $0000002d | RSP+0 -> | return addr |
- |-----------| |-------------|
+1 2 foobar . \ prints "45"
## pspush() and pspop()
@@ -89,8 +113,7 @@ 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 (except what calling Forth
-words, see below). Let's see an example:
+in functions that have a "void (void)" signature. Let's see an example:
void foobar() {
int b = pspop();
@@ -99,115 +122,21 @@ void foobar() {
pspush(a+b+x);
}
-This function does the exact same thing as the previous "foobar()", but stacks
-will look different. After function prelude:
-
- |-----------| |---------------|
- PSP+4 ->| $00000001 | RSP+12-> | return addr |
- PSP+0 ->| $00000002 | RSP+8 -> | int b = undef |
- |-----------| RSP+4 -> | int a = undef |
- RSP+0 -> | int x = undef |
- |---------------|
-
-Then, after the first 3 lines:
-
- PSP+0 ->|-----------| |---------------|
- RSP+12-> | return addr |
- RSP+8 -> | int b = 2 |
- RSP+4 -> | int a = 1 |
- RSP+0 -> | int x = 42 |
- |---------------|
-
-And right before returning:
-
- |-----------| |-------------|
- PSP+0 ->| $0000002d | RSP+0 -> | return addr |
- |-----------| |-------------|
-
-## The compiler VM
-
-The goal of this VM, which lives in /comp/c/vm, is to provide a unified API for
-code generation of a C AST across CPU architecture.
-
-Computation done by this generated code is centered around two operands, Op1 and
-Op2. Those operands can "live" in different places depending on the context: in
-a register, in memory, or as a constant.
-
-Operands can be stored in these locations:
-
-None: operand not specified
-Constant: a constant value. Cannot be used as a "destination" op.
-Stack Frame: an address on the Stack Frame
-Register: value currently being held a register
-
-Besides the location, each operand has an accompanying "argument", whose
-meaning depends on the location:
-
-Constant: the value of the constant
-Stack Frame: the offset relative to the SF pointer
-Arguments Frame: the offset relative to the AF pointer
-Register: the ID of the register
-
-Operations are compiled by calling the appropriate op word. For example,
-"vmadd," is the "binary +" operations. These operations have different op
-requirements and effects depending on their type.
-
-Unary op: Requires vmop. Keeps vmop allocated.
-Binary op: Requires vmop and vmop^. Keeps vmop allocated and deallocates vmop^.
-Assign op: Same as Binary op.
-vmret,: Requires a deallocated vmop^. If vmop is allocated, compile a push to
-PS and then de-allocate it.
-
-### vm?:, ( condop -- )
-
-(I intend to have a more complete documentation of the different operation
-types, but for now I just want to document this tricky little op while it's
-fresh.)
-
-Now that's a special little op, a triop masquerading as a binop. The idea is
-that we do a little bit like a if() *except* that it leaks a value, something
-that the regular if() doesn't do (this has implication for the Forth VM which
-tracks PS levels).
-
-You call this op at the ":" operator. When you encountered the "?" operator, you
-simply :push'ed your operand and kept it around, and kept vmop^ (the "result if
-true" operand) as vmop. Now, at ":" time, you have your true op in vmop and your
-false one in vmop^.
-
-Calling vm?:, will compile both ops, wraping them around jumps, but, more
-importantly, it will "merge" vmop and vmop^ into one single op, that is, the
-location that *both* branches of the condition will return to. That will be the
-result of this binop. This "merge" is arch-specific.
-
-### vmswitch, ( 'lookup -- )
-
-Resolve vmop and apply "switch" logic to the supplied *pointer* to lookup table.
-The lookup table has this format:
-
-- 4b count
-- count*4b values to compare
-- count*4b jump addresses
-
-We generate code to compare vmop with all elements of the lookup table and, if
-found, jump to the corresponding address. If no element match, no jump is made.
-
-### Jumping in the VM
-
-There are 2 kinds of jumps: forward and backward. In forward jumps, we need to
-emit a jump opcode followed by a placeholder and then push the address of that
-placeholder to PS. When we reach the target, we write the target address to that
-placeholder.
-
-In backward jumps, we push the target address upon meeting it, and then simply
-write the jump opcode followed by that address.
-
-Forward jumps are written with the "[" words:
-
-vmjmp[, ... ]vmjmp
-vmjz[, ... ]vmjmp
-
-Backward jumps are written with the non-"[" words:
-
-here ... vmjmp,
-here ... vmjnz,
+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 LIT>W, 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.
