# Harmonized Assembly Layer

The Harmonized Assembly Layer is a set of words implemented by all Dusk kernels
which have the same semantics and compile native code that has consistent
results on all architectures. For example, "RSP) 2 +) 16b) +," will, on all
arches, compile a set of instructions that will result in the 16-bit addition
of RSP+2 into the Work register. On i386, this is the same as
"ax sp 2 d) word) add,".

This layer allows us to generate performant code in a cross-arch manner. It is
also what compilers such as the C compiler rely on to generate code.

Of course, as with any abstraction, we sometimes lose a little bit in speed and
binary space compared to direct assembler instructions, but in general, the
result is pretty good and direct assembler should be needed only in the tightest
of the loops.

The HAL is implemented at the kernel level and is available from the very
beginning of the boot sequence, which makes extensive use of it to bootstrap
into a usable system.

The HAL is always for the "live" system. It has not been designed with cross-
compiling in mind.

## Register allocation

The HAL has 5 virtual registers: W, A, S, PSP, RSP. Each architecture
implementing the HAL will need to map those virtual registers to actual
registers. Here is the list of mappings for all supported CPUs:

i386  W=eax A=ebx S=edx PSP=esi RSP=esp
ARM   W=r9  A=r11 S=r8  PSP=r10 RSP=r13
RISCV W=x4  A=x5  S=x6  PSP=x3  RSP=x2

## RSP and PSP registers

RSP and PSP registers map directly to Forth's RS pointer and PS pointer. They're
the same.

As a general rule, PSP and RSP are always aligned to 32-bit. In a piece of code
written in HAL, you *can* have PSP break alignment for a short while, but you
have to make it aligned again before you return from your function.

RSP, however, if off-limits to disalignment. It must at all times be 32-bit
aligned.

## W register

The W register is the "work" register and the default destination of all HAL
instructions. When we say that "@," means "fetch", we mean "fetch into the
destination", which is the W register by default.

The W register is PS's top of stack. This means that, for example, increasing
the W register by 1 is the exact same thing as executing the "1+" word.

## A and S register

The HAL has two extra registers that regular Forth doesn't have: the A (Address)
register and the S (Scratch) register.

Both are general purpose registers that can be used both as source and
destination. To use as a source, there's the A) and S) words that behave like
W).

To have an operand target one of those registers as their destination, you use
the A>) and S>) words.

In terms of capabilities, the A register has the exact same ones as W. The S
register can also be used in the same way, but it's used by the "/mod,"
operation as a result register, so it's a tiny bit less "permanent".

## Register permanence

The A and S registers cannot be expected to keep their value across word calls.
As soon as another word is called, we can generally consider those values
destroyed.

However, all HAL operations and macros must preserve A's value (unless A is the
destination, of course). Therefore, we can rely on A's value as long as the code
we generate doesn't branch to other words.

Many words also make the promise of preserving the A register. They will
indicate that they do so with the *A* tag in their description.

Number literals always preserve the A register.

Some units might expand on that promise. If they do so, they'll explicitly
mention it in their documentation.

The S register doesn't have the same guarantees and is used by some HAL
operations and macros as temporary storage. That's why it's called "Scratch".
Operations and macros using it with will mention it in their documentation.

Rule of thumb: if you're coding a HAL macro, use the S register. If you're
coding a regular word, use A because the S register might be swept under your
feet.

It goes without saying that W, being PS's top of stack, is preserved at all
times.

## Operands

All HAL instructions take either no operand (inherent) or one operand parameter.
That operand parameter is a 32-bit number with an arch-specific (that is,
opaque) bit structure and that contains all the information the instruction
needs to know the source and destination of the instruction. Those operands are
detailed in:

* [doc/xcomp/x86/hal]
* [doc/xcomp/arm/hal]
* [doc/xcomp/riscv/hal]

Operand words all end with ")". For example, "A) +," means "add 32-bit location
where the A register points to the W register".

Some operand words are not directly operands, but operand modifiers. For
example, "+)" adds a numerical offset to an operand. "W) 4 +)" refers to the
memory location where W points to, with a 4 bytes displacement. The "8b)"
modifier transforms the operand into a 8-bit operand.

By default, all operands refer to a memory location. Only through the "&)"
operand (see below) can we refer directly to a value in a register.

## &) operand modifier

The &) word takes an input operand and returns its dereferenced counterpart. For
example, m) becomes i), W) becomes a direct reference to W, etc. This also works
with displacements. For example, "RSP) 4 +) &)" yields an operand that points
to RSP+4.

This operand might not be adressable directly by the host CPU. In that case, the
HAL instruction will in fact compile two CPU instructions. For example, "RSP) 4
+) &) +," under i386 would yield "di sp 4 +) lea, ax di add," ("di" being any
unallocated register).

The "&)" word never writes CPU instructions directly, only HAL instruction words
do. The "lea," above wouldn't be written when "&)" is called, but when "+," is.

The &) operand always results in a 32-bit operation. Applying &) sets the HAL
operand to 32-bit, but don't try to apply 16b) or 8b) afterwards, this results
in undefined behavior.

&) can't be used with i).

## <>) operand modifier

The <>) word inverts the destination and the source of the HAL instruction,
storing the result in the source. This also inverts the order of the operands.
For example, "$1234 m) 8b) <>) -," subtracts W from the 8-bit value at address
$1234 and stores the result at that address without affecting W.

### RSP) and PSP) with both &) and <>)

RSP and PSP registers can be directly accessed through &). As sources, there are
no special restrictions. But when the <>) modifier is used, only a subset of the
instructions are allowed and that is: @, +, -, +n,

## RSP) and [rcnt]

The only HAL operation that automatically adjusts [rcnt] (see "Local variables"
in [lib/bm]) is rs+,. Other HAL operations don't touch [rcnt]. Therefore,
special care must be taken when using the RSP) operand.

If you're inside of a regular "code" word, you don't care about [rcnt], so you
can ignore this warning.

However, if you're writing HAL as part of a macro that could be used in a word
that has local variables, then every time you write a HAL operation that
modifies RSP ("RSP) @+," for example), you need to adjust [rcnt] accordingly or
else you'll break local variables.

## le@, be@, and u@

le@, and be@, instructions work like the @, instruction except they read their
data in the specified endian-ness. In all cases, using these instructions with
8b) is exactly the same as using @,.

In addition to reading and writing in specific endian-ness, these instructions
also allow unaligned memory accesses, unlike @,.

HAL implementations for CPUs that natively allow unaligned accesses will alias
one of le@, or be@, to @, for speed.

And then there's u@, which means "unaligned @,". It's like @, but allows
unaligned accesses. In other words, on CPU where unaligned native accesses is
allowed, "u@," aliases to "@,". On other CPUs, it aliases either to "le@," or
"be@,".

le@, and be@, make no sense with &) or i).

## Branching and flags

The HAL can generate branching through its branch instructions, "br, ( op -- )",
"brr, ( op -- )" and "brc, ( op cond -- )".

In those instructions, "op" is a regular HAL operand. The branching word
performs a branch to the absolute address described by the operand.

This operation has no destination and thus is incompatible with A>) S>) and <>).
It is also incompatible with 8b) and 16b).

"br," is for a straight unconditional branching. "brr," (BRanch and Return) is
for a "call", that is, saving the address directly following the "brr," to
someplace that "exit," can return from.

"brc," is for conditional branching and takes an extra "cond" argument.  This
argument is generated by words like "Z)", ">)", etc. and the number they yield
is arch-specific. The idea is that through this number, the "brc," instruction
knows the kind of native branch instruction to generate.

These conditions depend on flags being set (or not) and the conditions under
which these flags are set is not exactly the same across achitectures. The HAL
exposes one flag: Z (zero). CPUs have more flags than that, but they're opaque
to the HAL.

Arithmetic conditions (">)", "<=)", etc.) have no associated flag and can only
be used after a "compare,".

To be able to rely on consistant conditional branching, HAL instructions make
guarantees on the flags set by certain instructions. If an instruction has a "Z"
next to it in the listing below, it's safe to conditionally branch using "Z)" or
"NZ)" right after having called it. Even if the native instruction for a
particular HAL word doesn't supply that flag, the HAL instruction will generate
the necessary native instructions to make it so, at the cost of speed. For this
reason, we minimize flag guarantees in HAL words.

Condition flags are only valid right after the instruction that's supposed to
set it. Flags are considered destroyed as soon as you compile another
instruction... with two exceptions.

First, there's branching that preserves flags. This means that after a br, or
brc, flags are the same as they were before.

Then, there's "dropf,", which does the same as "drop," except it guarantees that
flags are preserved. On most platforms, the implementations will be the same as
"drop,", but some CPUs might require a bit of maneuvering that has a speed cost,
hence the separate words. This word is used in situations where we've just made
a "compare," on W, then we'd like to brc, but we want to drop W first.

### 8b) and 16b) arithmetics and flags

8b) and 16b) modifiers only apply to memory accesses. On many CPUs arithmetics
are "upscaled" to 32-bit (e.g. ARM), but not all (e.g. i386, m68k). This means
that in most cases, flags or carry values shouldn't be relied upon after a 8b)
or 16b) arithmetic operation. If the flag result would be the same in all widths
then it can be relied upon.

In short, unless you are certain that a carry cannot occur, a 8b) or 16b) +, -,
or *, is dangerous because the result in undefined.

This applies to compare, which means that, for example,
"$4242 i) @, A) 8b) compare," will never set the Z flag because even if A)
is $42, comparison is done on the whole W register.

This also applies to +n, which means, for example, that if W points to a byte
with $ff in it, "1 W) 8b) +n," will *not* set the Z flag, as one might expect
otherwise. If W points to a byte with $00 in it, "0 W) 8b) +n" *will* set the
Z flag though, as this is consistent with 32-bit arithmetics logic.

It should also be noted that it never makes sense to apply 8b) or 16b) to PSP)
or RSP). Because of endian-ness, those operand can never refer to a reliable
location in a portable way.

In some cases, this "all arithmetics are 32-bit" doctrine is limiting, but it
does buy us a fair deal of simplicity in terms of HAL implementation, so the
tradeoff is good.

### Forward branching

Branching as described above works for backward branches, but what about forward
ones? They are achieved through "br! ( br tgt -- )". If you create a dummy
branch with "0 i) br," and remember where "here" was before you called it, you
can call "br!" with "br" being the recorded "here" and "tgt" being the
target absolute address to switch your branch to. Example:

  here 0 i) br, ... here br!
  here 0 NZ) brc, ... here br!

The "fbr," macro makes things shorter:

  fbr, ... here br!
  NZ) fbrc, ... here br!

"br!" is designed to take the beginning of the op as a parameter. It does
CPU-specific handling of whatever it needs to do to write the resulting target
at the correct place.

## pushlr, poplr, and popexit,

In Dusk, "Call" means "Push the address of the instruction following the current
one to RSP and then jump to the address being called". "Return" means "Pop RSP
and jump to that address".

On "traditional" CPU architectures, this maps exactly to the behavior of the
native "call" and "return" instructions, so we can live a happy life of
blissful ignorance when using these CPUs.

On some CPUs such as ARM [doc/hw/arm] and RISC-V [doc/hw/riscv], the native
"call" model is to save the address we'll want to return to to a register and
leave the task of push/popping to RSP to the programmer. In Dusk, we call that
register the "Link Register" (LR).

Of course, one thing we could do is to simply wrap all calls and returns in Dusk
into RSP push/pop operations, but that would squander a wonderful speedup
opportunity: With such an approach to calling, we can avoid one push and one pop
on each "leaf" routine call, that is, on each call to a routine that doesn't
call any other routine. That adds up to quite a lot of pushes and pops.

To grab this opportunity, the HAL has three words: pushlr, poplr, and popexit,

On "traditional" CPUs, these are hollow shells. The first two are noops and the
last one is an alias to "exit,". On ARM, these words push and pop the
return address register to and from RSP.

Words defined through "high level" mechanisms such as ":" call those words
automatically, no need to worry. However, words created with "code" don't
because it could be a "leaf" word.

This means that if you create a "code" word that happens to not be a "leaf"
(that calls another word), it needs to call "pushlr," as a prelude and to call
"poplr," before it returns. Leaf words don't need to do that, which makes them
faster.

## popret

On most CPUs, the return address for a call is a 32-bit absolute address living
in RS. This means, for example, that if you want to pop that return address
"manually", all you need to do is "r>".

But wait, don't do it! It's the wrong way. The problem is that some CPUs don't
hold their return addresses in such manner. For example, AMD64 [doc/hw/amd64]
pushes a 64-bit address that will contain the RBP Base Address, where what we
want is a 32-bit offset relative to that base address.

"popret" is a semantical equivalent to "r>" but for situations where you want
to pop a return address that has been pushed by a call. It will yield the same
kind of result on all CPUs.

## Word marks

On some architectures (on WASM), there is a strong separation between "code" and
"data" and memory areas containing executable code have to be "marked" as such.
We do so with "wordmark,". Calling this results in an arbitrary number of bytes
to be written to "here" to serve as such mark (it's a noop in architectures not
needing it).

This mark also serves as JIT status, which means that when a piece of code
changes (for example in "realias"), its word mark should be re-written.

These marks apply to
- every word on sysdict
- every location that is targeted by a CALL instruction

The "code" word will automatically write a word mark, while the "entry" word
will not.

## Instruction cache clearing

Some CPUs such as ARM have separate data and instruction cache (icache). This
means that writing to an address and then executing it right away might result
in executing the wrong code if that address happened to be in the icache.

Clearing the icache at the right moment is tricky, but it's also possible to
cover a lot of grounds with simple rules, such as:

On CPUs needing to clear the icache, the HAL does so at the end of exit,
popexit, br, and br!.

Because any kind of code that is immediately reachable and not broken has to end
with one of these, it covers pretty much all possible cases.

## HAL powerups

The API described here is what the kernel and [xcomp/boot.fs] supply, but Dusk
has even more than that in the form of "HAL powerups". Units in the "hal/"
directory such as [hal/muldiv] or [hal/opq] augment the HAL with new
capabilities.

## HAL API

Operand words:

W)    -- op          Indirect W register
A)    -- op          Indirect A register
S)    -- op          Indirect S register
PSP)  -- op          Indirect PSP register
RSP)  -- op          Indirect RSP register
i)    n -- op        Immediate operand. Can't use with <>)
m)    addr -- op     Absolute address
sys)  off -- op      SYSVARS reference [doc/data]. Depending on systems, might
                     be register-based or absolute memory reference.
+)    op disp -- op  Apply displacement to op. Can be applied multiple times.
                     Displacement can be negative.
W>)   op -- op       Set destination to W
A>)   op -- op       Set destination to A
S>)   op -- op       Set destination to S
&)    op -- op       Dereference operand (see above)
<>)   op -- op       Direction of the operation is inverted (see above)
8b)   op -- op       Make op 8-bit
16b)  op -- op       Make op 16-bit
32b)  op -- op       Make op 32-bit (default)

Branching and conditions:

Z)   "Zero" flag set. On "compare,", this means "equal".
NZ)  "Zero" flag not set. On "compare," this means "not equal".
<)
<=)
>)
>=)
s<)   Signed comparison
s<=)
s>)
s>=)

C>W, ( cond -- )
  If cond is met, W=1. Otherwise, W=0.

br, ( op -- )
  Branch to address a.
  Cannot be used with A>) S>) <>) 8b) 16b).
  If used with &), destroys the value of source.
brc, op cond --
  Branch to address a if condition is met.
  Cannot be used with A>) S>) <>) 8b) 16b).
  If used with &), destroys the value of source.
brr, ( op -- )
  Compile a branch to address a while at the same time setting the "return
  address" (commonly, that means pushing to RSP, but not always) to the
  instruction directly following this one. This is commonly called a "call".
  Cannot be used with A>) S>) <>) 8b) 16b).
  If used with &), destroys the value of source.
br! ( braddr tgtaddr -- )
  Given "braddr" pointing to a branch instruction, change the reference at the
  address so that it targets "tgtaddr". Used for forward branching.
exit, ( -- )
  Compile a return from a call.
pushlr, ( -- )
  Push the current return address to RSP (on relevant CPUs)
poplr, ( -- )
  Pop RSP in return address register (on relevant CPUs)
popexit, ( -- )
  Equivalent to "poplr, exit," but faster.
wordmark, ( -- )
  Write a "word mark". See section above.
popexit ( -- ) *I*
  Same as "r>" for for call return addresses (see above)

Instructions:

@,       op --      Read source into dest
le@,     op --      Read source into dest in little endian byte order. No &) i)
be@,     op --      Read source into dest in big endian byte order. No &) i)
u@,      op --      Read possibly unaligned source into dest. No &) i)
@!,      op --      Swap dest and source
+,       op --   Z  dest + source
-,       op --   Z  dest - source
swap-,   op --   Z  source - dest
*,       op --      dest * source.
/mod,    op --      divide dest by source and put remainder in S register.
                    Can't be used with S>).
<<,      op --   Z  dest lshift source. C only works if src is 1.
>>,      op --   Z  dest rshift source. C only works if src is 1.
s>>,     op --   Z  Arithmetic ("signed") shift right. Instead of filling the
                    "right" part of dest with zeroes, it fills it with its b31.
&,       op --   Z  dest and source
|,       op --   Z  dest or source
^,       op --   Z  dest xor source
@+,      op --      Read source into dest and then add 4/2/1 to operand's
                    dereferenced source. Cannot be used with m) i) &)
                    If source is the same as dest, behavior is undefined.
-@,      op --      Subtract 4/2/1 to operand's dereferenced source and then
                    read source into dest. Decrement happens before fetch,
                    hence the symbol order being the opposite of "@+".
                    Cannot be used with m) i) &).
compare, op --   *  Compare source to dest, that is, subtract source from dest,
                    discarding the result and keeping the flags.
                    Flags kept: Z < > <= >= s> s< s<= s>=
                    example: if W=1 and A=2, "A) &) compare," makes "<)"
                    condition true.
+n,      n op -- Z  Add n to source without affecting dest
                    Can't use with i) or <>)
                    Z flag unreliable when targeting "PSP) &)" or "RSP) &)"
dropf,  --          Perform a "drop," while preserving flags.

## Range instructions

The range instructions below don't take any HAL operand as a parameter, so they
always generate the same code, with a fixed meaning for registers. These words
come in 3 forms for the 3 possible byte widths, with the "w" prefix for 16-bit
and "c" prefix for 8-bit width.

Note that when we refer to a number of elements, it's not the same thing as
bytes unless we're in 8-bit width. See "Ranges" in [doc/usage/lit].

Code generated by those compilers are "zero guarded", that is, they are noop if
S is 0.

When the description for register values aren't specified in the descriptions
below, their value is unspecified and shouldn't be relied upon.

fill, --   Fill memory range of S elements starting at A with value W.
wfill,     Afterwards, A point to the address following the last written
cfill,     element.
move, --   Copy S elements from W to A.
wmove,     Afterwards, W and A point to the address following the last read and
cmove,     written element.
[]=,  --   Compare S elements in addresses W and A. As soon as an element
w[]=,      differ stop right there. If all elements were equal, Z is set.
c[]=,      Otherwise, Z is unset. On empty range, Z is set.
idx,  --   Compare S elements in address A to value W. As soon as an element
widx,      is equal, stop right there. If an element was found, Z is set, S
cidx,      is its index (first element is 0). Otherwise, Z is unset.
           On empty range, Z is unset.

## HAL macros

These words below aren't implemented in kernels and are combinations of the
words above, but they're pretty useful nonetheless.

ps+,    n --    Add n to PSP
rs+,    n --    Add n to RSP

!,      op --   Write dest to source. Shortcut for "<>) @,"
!+,     op --   Equivalent to "<>) @+,". Source==dest is weird, but fine.
-!,     op --   Equivalent to "<>) -@,".

fbr,     -- a    Forward branch. Equivalent to "here 0 i) br,"
fbrc,    c -- a  Equivalent to "here 0 i) rot brc,"
bbr,     a --    Backward branch. Equivalent to "i) br,"
bbrc,    a c --  Equivalent to "swap i) swap brc,"
ifz,     -- a    Equivalent to "NZ) fbrc,"
ifnz,    -- a    Equivalent to "Z) fbrc,"
execute, a --    Equivalent to "i) brr,"

## Mirror compilers

There are also some compiler words that all have the same "( -- )" signature and
that compile the same operation as their name, without the "," part. You can use
them to create a "code" word or to inline an operation instead of calling it.

dup, swap, nip, drop, 2drop, rot, over, rot>, tuck, 2dup,

## Generating code in multiple widths

Sometimes, we want to generate a piece of code in multiple widths and repeating
the code 3 times is tedious and noisy. "MOD)" might help. "MOD)" is an
indirection put over "8b)", "16b)" and "32b)" that is set at compile time with
"8b" "16b" and "32b". Here's an example usage:

  : _, W) MOD) @, exit, ;
  code @ 32b _,
  code w@ 16b _,
  code c@ 8b _,

## Examples

To give a better idea of how the HAL works, here are examples with their
corresponding i386 instructions:

PSP) @,                                ax si 0 d) mov,
A) 8b) !,                              bx 0 d) al mov,
RSP 4 +) A>) +,                        bx sp 4 d) add,
PSP) &) A>) @!,                        bx si xchg,
PSP) <>) <<,                           cx ax mov,
                                       si 0 d) cl shl,
RSP) @+,                               ax sp 0 d) mov,
                                       sp 4 i) add,
A) 16b) !+,                            bx 0 d) 16b) ax mov,
                                       bx 2 i) add,
A) 16 +) &) @,                         bx 16 d) lea,
$1234 m) +n,                           $1234 m) 42 i) add,
42 PSP) &) +n,                         si 42 i) add,
54 i) -,                               ax 54 i) sub,

Here are actual word implementations:

code drop PSP) @+, exit,
code dup PSP) -!, exit,
code swap PSP) @!, exit,
code nip 4 ps+, exit,
code over PSP) -!, PSP) 4 +) @, exit,
code 1+ 1 i) +, exit,
code lshift PSP) <>) <<, PSP) @+, exit,
code c@ W) 8b) @, exit,
code not 0 i) compare, Z) C>W, exit,
code execute S) &) !, drop, S) &) br,

Branching:

' foo execute, \ call "foo"
' foo bbr, \ jump to "foo"
42 i) compare, ' foo Z) bbrc, \ jump to "foo" if W=42
here bbr, \ infinite loop
\ Execute code "..." only if W <= A
A) &) compare, >) fbrc, ... here br!

## HAL number bank

Numbers supplied to i) m) and +) can be any number of the 32-bit range.
Nevertheless, as per HAL API constraints, all operands occupy only one PS slot.

Therein lies a problem: how can a 32-bit operand include its necessary metadata
along with a possible offset that can be anything in the 32-bit range? It does
so through a number bank mechanism.

The number bank is a 4b * 15 global and static rolling buffer. This allows us to
assign arbitrary number to slots numbering from 1 to 15. This slot number
occupies only 4 bit in our HAL operand, which is much more manageable. Slot 0
always yields the number 0 and isn't part of the rolling buffer.

This allows up to 15 operands associated with numbers to coexist at once on PS,
making HAL and assemblers (which piggy-back on this API) pretty macro-able.

Every kernel implement this number bank and expose this API:

hbank' ( slot -- a )
  Get address associated to bank slot.

hbank! ( n -- slot )
  Reserve a new slot and write "n" to it. Yield the ID of the new slot.

hbank@ ( slot -- n )
  Yield number in slot.

hbank+ ( n slot -- )
  Add "n" to slot. Don't use this with slot 0!
