Acus Program Model

Basic Block Scheduling

In the Acus model, a program consists of a series of basic blocks, sequences of code that are always executed in order, and jumps between those blocks. Each basic block ($B_i$) is compiled into its corresponding BF instructions and wrapped in a BF loop pair (i.e. between [ and ]) whose entry is controlled by generated guard code $G_i$. The complete sequence of blocks is enclosed in a main loop, conditional on the value in a special BF cell, the Run cell, which can be reset by any block when the program should be terminated. Prior to entering the main loop, a head section $H$ is responsible for the initial setup of the data tape and the tail code $T$ is responsible for resetting the pointer to the Run cell before the closing bracket of the main loop is encountered:

The aforementioned guard code $G_i$ compares the block index $i$ to the value stored in another predefined cell: the TargetBlock cell. Only when this cell contains the exact index of the block and the Run cell is still nonzero is the loop entered and its code executed. Therefore, each block should at some point set the index of the next block to be executed to keep the program going (not setting a different TargetBlock will cause the same block to be executed ad infinitum). This approach basically implements a state machine that can be expressed in pseudocode as shown in Listing 4. Note that, on each iteration of the main loop, all blocks are scanned until the scheduled block is encountered. In a worst-case scenario, when block i is scheduled by block i+1 (the currently executed block), the system will first need to check all blocks from i+2 up to N before looping back to block 1 and eventually block i.

B = {B1, B2, ..., Bn}

Run = 1
TargetBlock = 1 # not necessarily block 1

while Run:
  for i = 1 ... N:
    if Run AND TargetBlock == i:
      execute B[i]

Frames and Initialization

Each function has its own chunk of memory that it operates on, called a frame. Calling a function has the effect of advancing the data pointer one cell beyond the end of the current function’s frame. When a BF program is executed, the pointer starts at cell 0 in frame 0, which is dedicated to holding the global data (Section Global Data Frame). Frame 1 starts just beyond the end of frame 0; the exact offset depends on the number of global variables and their sizes. The initialization code that runs prior to entering the main loop needs to set up both frame 0 and frame 1:

1. Set a marker (the SeekMarker, Section SeekMarker) at the start of the data-tape (cell 0). This marker can be used as a stop-sign during dynamic pointer movements to locate the start of the global data frame (and to prevent the pointer from moving into the (undefined) negative address-space).

2. Set another marker (the FrameMarker) that marks the start of frame 0 (the global data frame, Section Global Data Frame). This might seem redundant as we already marked the start of this frame with a SeekMarker, but since every frame has a FrameMarker, the global frame needs it as well for generalized algorithms to work.

3. Calculate the size of frame 0 and move the pointer to the start of frame 1 (the frame that will be used by the function that is set as the entrypoint for the program).

4. Mark the start of frame 1 by setting the FrameMarker here as well.

5. Move the data pointer to the Run cell of frame 1 and set its value to 1.

6. While the data pointer points to the Run cell of frame 1, open the main loop (guaranteed to be entered as we just set this cell to 1).

Block Guards

The guards $G_i$ compare the value stored in the TargetBlock cell to their index and check if the Run flag is still set. The results of these comparisons are ANDed together and used as the loop condition for the block that follows immediately after. Because the block index is known at compile time, it can simply be subtracted from (a copy of) the TargetBlock value. If the result is 0, this means we should enter the block given that the Run cell contains a nonzero (true) value. The logic necessary to implement these checks is discussed in more detail in Section Boolean Operations. A simplified BF algorithm that implements this logic could look like the snippet of Listing 5; the real algorithm is more complicated because it needs to support 16-bit block indices (otherwise each program would be limited to only 255 code blocks), which requires 16-bit arithmetic and logic routines (Section Addition and Subtraction).

# Guard code G3: computes ``r AND i == 3''
# r: cell that contains a copy of the run-flag
# i: cell that contains a copy of the target-index
# f: cell that will contain the guard-flag (result of r AND i == 3)

f [-]                  # reset f
r [                    # if run
  f +                  # set guard-flag to 1
  i --- [              # subtract 3 from i, check if nonzero
    f -                # still nonzero -> set flag to zero
    i [-]              # exit i-loop
  ]
  r -                  # exit r-loop
]

# At this point, f is set only when r was set and i == 3  
f [                    # move pointer to guard-flag
  ...                  # user code (block 3)
]

Example: Fibonacci

To illustrate how a program is divided into basic blocks, a simple Fibonacci number generator is shown in Figure 42. It consists of three functions, each of which contains multiple basic blocks. The block IDs are shown in square brackets at the start of each block. Blocks end at control boundaries, i.e. places in the code where potential jumps take place, or explicitly at predefined labels.

The program starts execution in block 10, which is set as the entry point by the initialization code (note that the initialization code of Listing 4 sets the entry point to block 1; the specific example below requires the initialization sequence to set this value to 10 instead). A function call is immediately encountered, ending the current block. After initializing a new stack frame (this will be covered later, in Section Frames and Calls), the TargetBlock is set to block 1: the entry block index of the callee. This will cause control flow to skip over block 11 and loop back to block 1, which will then be entered. When control hits the conditional statement of block 3, either block 4 or 5 will be set as the next target block, depending on the result of evaluating i < n. In this case, both the if and else bodies contain only a single block that immediately terminates in a jump. When control eventually reaches the end of main, the Run cell is set to zero, causing flow to exit the main loop and terminate the program.