Other Optimizations · Synapse-191

The caching system is one of the optimizations used by Acus to try to somewhat limit the number of generated BF instructions, which tends to grow very fast for complex programs. Even though it was never a goal to produce highly optimized BF, several other optimizations have been implemented to fight the explosive nature of the generated output. Each of these techniques will be briefly outlined in this chapter.

Move Semantics

The algorithms for moving and copying BF cells are very similar: copying means we simultaneously move to the target cell and a scratch cell, only for the scratch cell to be emptied back into the source location. Obviously, we should move and avoid the full copy algorithm whenever possible. Therefore, if we can prove that the source is expendable, we can just move its contents out of it to a new location. Acus tries to find as many opportunities as possible to move instead of copy. For example, this is possible in the following situations:

Assignment from a temporary expression. e.g. x = y + z, where y + z is a temporary which does not outlive the statement anyway.
Flushing cache entries that are about to be deleted. When a cache tree is flushed prior to it being deleted, we can move instead of copy towards the root.

Literal Evaluation

Constant Folding

While Acus does not implement advanced constant-expression evaluation (it does not keep track of known values of runtime variables), it will apply constant folding to literal expressions. For example, consider the expression 3 + 4. In a naive implementation, the compiler might need to allocate 2 temporary slots for the literal expressions 3 and 4 and call a runtime algorithm on those slots to compute the value 7. Acus will simply collapse this to the literal expression 7 without generating any runtime code.

Specialized Constant Algorithms

All operators come in 2 flavors: one to apply its effect to two slots and one to apply its effect to a slot paired with a constant. For example, the expressions x * y and x * 8 might be evaluated differently. In the latter case, the constant can be evaluated to determine if the algorithm can be simplified or optimized. Multiplication by 0 will instantly result in the cell being zeroed out, whereas multiplication by 1 can return without any modifications at all. Similar optimizations have been implemented for other arithmetic and logical operators.

Addition and subtraction by 0 result in a no-op.
Multiplication by 0 results in immediate 0.
Multiplication by 1 results in a no-op.
Division by 0 rules are hard-coded (see Division by Zero).
Unsigned comparisons to 0 only need to check if the value is 0 (can’t be less than 0 anyway).
Signed comparisons to 0 can use the sign-bit algorithms.

Primitive and BF Merging

Merging Primitives

Before generating actual BF characters, Acus will produce a series of primitives, each of which represents a relatively simple sequence of BF instructions on a slightly higher level (Table 13). Sequences of primitives can sometimes be merged into shorter sequences or even no-ops. For example, if the primitive MovePointerRelative(3) is immediately followed by the primitive MovePointerRelative(6), they can be merged into a single MovePointerRelative(9). This leads to a series of merge-rules, listed in Table 14. By applying these rules iteratively to the generated sequence of primitives, the program can be shrunk significantly in post-processing.

Table 13. Acus primitives.
Primitive	Description
Primitive	Description
`LoopOpen`	Open a BF loop, compiles to simply `[`.
`LoopClose`	Close a BF loop, compiles to simply `]`.
`MovePointerRelative(x)`	Move the pointer by `x` cells (positive means to the right).
`ChangeValue(c)`	Change the current value by an amount `c`.
`ZeroCell`	Set the current value to `0` using `[-]`.
`ZeroCellPlus`	Set the current value to `0` using `[+]`.
`ConstructConstant(c)`	Construct the value `c` in the current cell.
`MoveData(x)`	Move the contents of the current cell to relative position `x`.
`CopyData(x)`	Copy the contents of the current cell to relative position `x`.
`Add(x)`	Add the value of the cell at relative position `x` to the value of the current cell.
`Subtract(x)`	Subtract the value of the cell at relative position `x` from the value of the current cell.
`Boolean`	Set the current cell to its boolean value.
`Not`	Set the current cell to its logical not value.
`Or(x)`	Set the current value to the logical OR of this value and the value inside the cell at relative offset `x`.
`And(x)`	Set the current value to the logical AND of this value and the value inside the cell at relative offset `x`.
`Xor(x)`	Set the current value to the logical XOR of this value and the value inside the cell at relative offset `x`.
`Equal(x)`	Set the current value to 1 if it is equal to the value in the cell at relative offset `x`, 0 otherwise.
`Less(x)`	Set the current value to 1 if it is less than the value in the cell at relative offset `x`, 0 otherwise.
`LessOrEqual(x)`	Set the current value to 1 if it is less than or equal to the value in the cell at relative offset `x`, 0 otherwise.
`Greater(x)`	Set the current value to 1 if it is greater than the value in the cell at relative offset `x`, 0 otherwise.
`GreaterOrEqual(x)`	Set the current value to 1 if it is greater than or equal to the value in the cell at relative offset `x`, 0 otherwise.
`Cmp(c)`	Set the current value to 1 if it is equal to the compile-time constant `c`, 0 otherwise.

Table 14. Primitive merge rules.
Primitive	Followed By	Merged Into
Primitive	Followed By	Merged Into
`ZeroCell`	`ZeroCell`	`ZeroCell`
`ZeroCell`	`ZeroCellPlus`	`ZeroCell`
`ZeroCellPlus`	`ZeroCellPlus`	`ZeroCellPlus`
`ZeroCellPlus`	`ZeroCell`	`ZeroCellPlus`
`LoopClose`	`ZeroCell`	`LoopClose`
`LoopClose`	`ZeroCellPlus`	`LoopClose`
`MovePointerRelative(x)`	`MovePointerRelative(y)`	`MovePointerRelative(x + y)`
`ConstructConstant(c)`	`ChangeValue(d)`	`ConstructConstant(c + d)`
`ConstructConstant(c)`	`ConstructConstant(d)`	`ConstructConstant(d)`
`ConstructConstant(c)`	`ZeroCell`	`ZeroCell`
`ConstructConstant(c)`	`ZeroCellPlus`	`ZeroCellPlus`
`ConstructConstant(c)`	`Boolean`	`ConstructConstant(c != 0)`
`ConstructConstant(c)`	`Not`	`ConstructConstant(c == 0)`
`ConstructConstant(c)`	`Cmp(d)`	`ConstructConstant(c == d)`
`ChangeValue(c)`	`ChangeValue(d)`	`ChangeValue(c + d)`
`ChangeValue(c)`	`ZeroCell`	`ZeroCell`
`ChangeValue(c)`	`ZeroCellPlus`	`ZeroCellPlus`
`ChangeValue(c)`	`ConstructConstant(d)`	`ConstructConstant(d)`
`MoveData(x)`	`ZeroCell`	`MoveData(x)`
`MoveData(x)`	`ZeroCellPlus`	`MoveData(x)`
`CopyData(x)`	`ZeroCell`	`MoveData(x)`
`CopyData(x)`	`ZeroCellPlus`	`MoveData(x)`
`Cmp(c)`	`ZeroCell`	`ZeroCell`
`Cmp(c)`	`ZeroCellPlus`	`ZeroCellPlus`
`Cmp(c)`	`Boolean`	`Cmp(c)`
`Boolean`	`Boolean`	`Boolean`
`Boolean`	`Not`	`Not`
`Not`	`Boolean`	`Not`
`Not`	`Not`	`Boolean`
`Or(x)`	`Boolean`	`Or(x)`
`And(x)`	`Boolean`	`And(x)`
`Xor(x)`	`Boolean`	`Xor(x)`
`Add(x)`	`ZeroCell`	`ZeroCell`
`Add(x)`	`ZeroCellPlus`	`ZeroCellPlus`
`Add(x)`	`ConstructConstant(c)`	`ConstructConstant(c)`
`Subtract(x)`	`ZeroCell`	`ZeroCell`
`Subtract(x)`	`ZeroCellPlus`	`ZeroCellPlus`
`Subtract(x)`	`ConstructConstant(c)`	`ConstructConstant(c)`
`Equal(x)`	`ZeroCell`	`ZeroCell`
`Equal(x)`	`ZeroCellPlus`	`ZeroCellPlus`
`Equal(x)`	`ConstructConstant(c)`	`ConstructConstant(c)`
`Equal(x)`	`Boolean`	`Equal(x)`
`Less(x)`	`ZeroCell`	`ZeroCell`
`Less(x)`	`ZeroCellPlus`	`ZeroCellPlus`
`Less(x)`	`ConstructConstant(c)`	`ConstructConstant(c)`
`Less(x)`	`Boolean`	`Less(x)`
`LessOrEqual(x)`	`ZeroCell`	`ZeroCell`
`LessOrEqual(x)`	`ZeroCellPlus`	`ZeroCellPlus`
`LessOrEqual(x)`	`ConstructConstant(c)`	`ConstructConstant(c)`
`LessOrEqual(x)`	`Boolean`	`LessOrEqual(x)`
`Greater(x)`	`ZeroCell`	`ZeroCell`
`Greater(x)`	`ZeroCellPlus`	`ZeroCellPlus`
`Greater(x)`	`ConstructConstant(c)`	`ConstructConstant(c)`
`Greater(x)`	`Boolean`	`Greater(x)`
`GreaterOrEqual(x)`	`ZeroCell`	`ZeroCell`
`GreaterOrEqual(x)`	`ZeroCellPlus`	`ZeroCellPlus`
`GreaterOrEqual(x)`	`ConstructConstant(c)`	`ConstructConstant(c)`
`GreaterOrEqual(x)`	`Boolean`	`GreaterOrEqual(x)`

Merging BF

As a final pass, after all primitives have been lowered into actual BF characters, Acus will scan the resulting source code for cancellation opportunities: sequences of consecutive + and - or < and > commands that can be collapsed. The primitive-merging rules already do this to some extent by merging ChangeValue and MovePointerRelative primitives, but that does not capture all opportunities. For example, when a MovePointerRelative primitive is followed by another that, when lowered to BF, starts with a sequence of > commands, these can be merged or cancelled in the final result.