Branch instructions

CALL Call

The CALL instruction pushes the current instruction pointer and current CPU flags (N, Z, T, R) on the return address stack, and then replaces the instruction pointer with the location indicated by the scope subr. When a RETURN instruction is executed within the called scope later, the instruction address on the top of the stack will be popped, and the program will continue with the instruction that immediately follows CALL.

A scope is a contiguous set of zero or more instructions in code memory, wherein the names of registers are local to that set of instructions. The Assembly language presently identifies scopes, which can be CALLed, using two colons (::). Labels, which can be JUMPed to, are indicated with a single colon (:). In the code example at the end of this section, times1000 and some_program are scopes, and too_high and wrong_answer are labels.

For security reasons, the return address stack is stored in a dedicated SRAM IC. The sole electrical access to the stack SRAM’s data connects to the instruction pointer exclusively. The only instructions that can access this IC’s contents are CALI, CALL, RETURN, and REVERT. Thus the stack is not used for other purposes in the manner of other architectures, such as for local variables. Because the architecture does not support recursion via the stack, stack overflow is unlikely and in any event cannot cause privilege escalation.

Limitation on stack depth

The stack size is fixed and cannot be changed. A user program should not attempt more than 250 active (nested) CALL statements at any time. (The actual depth is 255, but the operating system needs some of this space.) The architecture is not intended for any stack-based recursion. Moreover, no data is ever stored to the stack.

The stack never overflows. Instead, it wraps around. Although this is undesirable, the only consequence of wraparound is that the CPU will branch somewhere unexpected when a RETURN or REVERT is executed. In user programs, this branch will stay within the user’s nonprivileged code, so stack wrapping will not result in privilege escalation.

Calls to labels

To reduce opportunity for human mistakes, CALL requires that its destination be a scope as opposed to a label. Occasions sometimes come up, including a few places in the Osmin kernel, where a CALL instruction should be to a label instead of a scope. This is the purpose of the LCALL assembler mnemonic, which generates a CALL opcode to a destination within the current scope.

Removed functionality

The dissertation says that conditional CALL instructions are supported, but they have been removed from the architecture. Although they may appear to have the potential to save a little time, their usefulness is limited because of the overhead that is typically needed to pass parameters to the called scope. To set up these parameters always, but make the call only conditionally, would be less efficient than adding a conditional JUMP to bypass both CALL and any needed setup code.

CALL and RETURN example

; Given an unsigned x, quickly compute 1000 * x.
; This will set the R(ange) flag if 1000 * x >= 2**36.
times1000::
    u. x                            ; input
    u. xk                           ; output
    u. t                            ; temporary
    keep x xk                       ; don't reuse these registers

    ; To avoid preventable overflow, we approach 1000 * x from below,
    ; 2 * (512 - 4 - 4 - 4), instead of from above, 1024 - 16 - 8.

    xk = x asl 111111_111111`o      ; 512 * x
    t  = x asl 020202_020202`o      ; 4 * x
    xk = xk - t                     ; 508 * x
    xk = xk - t                     ; 504 * x
    xk = xk - t                     ; 500 * x
    xk = xk + xk                    ; 1000 * x
    return

; Main program
some_program::

    ; Clear R(ange) flag.
    crf

    ; Here's a hard test case that would overflow if times1000
    ; approached its answer from the wrong direction.
    times1000::x = 68719476
    call times1000

    ; Check if overflow occurred.
    jump +r too_high

    ; Check answer.
    cmp times1000::xk - 687194760
    jump != wrong_answer

    ; If we get here, the answer was correct.
    ; ...

too_high:
    ; If we get here, overflow occurred because times1000
    ; was called with x >= 68719477.
    ; ...

wrong_answer:
    ; If we get here, the program didn't work correctly.
    ; ...

JUMP Jump

The JUMP instructions transfer control to the instruction at label dest. This label must be within the present scope. Here is a sample:

again: nop
       jump again    ; infinite loop

Jumps can be conditioned on the N, R, T, or Z flags. The -t and +t designators cause the jump to occur only if T is clear or set, respectively. If the jump does not occur, execution continues with the instruction that immediately follows. The -r and +r do the same using the R flag.

The <, <=, ==, !=, >=, and > designators operate as if a cmp a - b instruction immediately preceded the jump, with the jump taken if a is less than, less than or equal, equal to, not equal to, greater than or equal to, or greater than b, respectively. Equivalently, the jump will be taken only under the following corresponding N and Z flag states:

Note that N and Z are never simultaneously true.

It’s important to use == instead of merely = for the equality test, because

jump = dest

syntactically means to copy a register named dest to a register named jump.

The RETURN VIA form of JUMP allows the destination to be a scope instead of a label. This is merely to placate the assembler, which doesn’t want accidental JUMPs to scopes or CALLs to labels. RETURN VIA can optimize the two-instruction sequence:

call wakanda            ; Assembler forbids a JUMP to wakanda.
return

to one instruction:

return via wakanda      ; Assembler understands a JUMP is intended.

The dissertation says “JUMP may have important pipelining consequences.” Turns out, it doesn’t.

JUMP example

Here is a simple double loop with 6300 inner iterations, where outer register i counts from 0 through 89 and inner register j counts from 0 through 69:

             unsigned i j

             i = 0
     outer:  cmp i 90
             jump >= outer_done
             j = 0
     inner:  cmp j 70
             jump >= inner_done

             ; This is inside both loops. Do something exciting.
             nop

             j = j + 1
             jump inner
inner_done:  i = i + 1
             jump outer
outer_done:  nop

RETURN Return

The RETURN instruction fetches the instruction immediately following the most recent CALL that has not yet returned, and continues the program from that point.

RETURN does not restore the CPU flags (N, Z, T, R) to their condition at the time of the CALL, even though they were saved with the return address. To return with flags restored, use REVERT instead of RETURN.

See also CALL.

REVERT Revert

The REVERT instruction fetches the instruction immediately following the most recent CALL that has not yet returned, and continues the program from that point with the CPU flags exactly as they were at the time the CALL was executed.

In most situations, RETURN is more appropriate than REVERT, because REVERT conceals any flags that have been set by a subroutine, including the R flag that indicates out-of-range arithmetic. REVERT is principally for use by the operating system to resume execution of an interrupted user program.

See also CALL.