This is the code for the first stage Onramp code generator.
The first stage code generator takes a form of Onramp assembly emitted by early stage Onramp compilers as input, optimizes it, and outputs it in general Onramp assembly.
The first stage compiler, by virtue of being written in assembly, emits terribly inefficient code so there is a lot of opportunity for simple optimizations. This code generator is essentially just a peephole optimizer for it.
This code generator doesn't work on arbitrary assembly however. It makes various assumptions about the input (for example, it assumes that registers r4-r8 are unused), so it only works on assembly output by the early stage Onramp compilers. In this sense the input really is an intermediate representation, not full assembly but a restricted subset of it. This code generator accepts it and turns it into general assembly (one that uses all registers for example.)
But the fact that the compiler output is itself valid assembly makes it possible to compile this code generator without first needing a code generator! This is how we break the chicken-and-egg problem without having to write a code generator in assembly. The build script for this code generator is interesting: we compile it into an unoptimized executable, then immediately run it on its own assembly and re-link to produce an optimized build without having to recompile.
The first stage code generator is bootstrapped before the second stage linker. This means we don't have local label support, so we have to fit everything in one translation unit. However, the stage is fairly large, so we bootstrap it after the second stage preprocessor in order to use include files to organize it.
This means the code layout is a bit unconventional: almost all of the code is in header files only. These still include each other naturally. If there would be a circular dependency between header files, we move the necessary declarations into common.h, which is ultimately included first.
This code is written in Onramp Minimal C (omC). Since we don't have structs, it uses "emulated structs" as described in cci/1 to store instructions.
The optimizations performed are organized into passes. We try to combine as many optimizations into each pass as possible in order to minimize the number of passes.
These are the passes and optimizations implemented so far:
- Forward Scan
- Forward Propagation
- Block Scan
- Backward Propagation
This replaces push/pop pairs with movs into unused registers. For example, cci/0 emits huge amounts of push/pop instructions like this:
push r0
...
push r0
...
pop r1
...
pop r1This optimization pass converts the above to:
mov r5 r0
...
mov r4 r0
...
mov r1 r4
...
mov r1 r5The optimization is done in a single pass through the function. It only applies if there are no labels, jumps, calls, or other instructions that use rsp in between the push and pop.
This increases performance significantly on its own; push and pop are each composed of two primitive instructions that access memory while mov is one primitive instruction that uses only registers. More importantly, this prepares for other transformations that will rename registers and eliminate more code.
Registers r4-r8 are not used in cci/0 or cci/1 assembly so we use them to replace push/pop. This lets us replace up to five nested push/pop so we can optimize some pretty deep expressions. This code only works on the subset of assembly generated by cci/0 and cci/1, not on handwritten assembly or assembly generated by the final stage compiler. There is minimal safety checking for this.
(cci/0 doesn't use r9 either except in the function preamble but cci/1 does use it, e.g. in compile_stack_shift(). If we eventually upgrade cci/0 enough to delete cci/1 we could use r9 here.)
This optimization takes advantage of the fact that a memory instruction takes two arguments (conventionally a base and offset) and adds them together. It is used to optimize code like this:
add rb rpp ra
ldw r0 rb 0We keep track of the last instruction that wrote to each register. When we scan ldw r0 rb 0, we can see that one of its arguments is zero and the other is a register, so we look at what wrote to that register. If it's an add, and neither of its arguments have been modified in between, we can substitute both arguments. The result is:
add rb rpp ra
ldw r0 rpp raAssuming rb is otherwise unused, the add instruction will be removed later by dead store elimination.
In the forward propagation pass, we walk through the function keeping track of the contents of registers. A register can contain either a constant, another register, a variable (not implemented yet), or an unknown value.
When a register appears as the input to a later instruction, and we know the contents of that register, we may be able to substitute it. This is the main mechanism used by constant and register propagation.
For example if we see mov r0 r1, we record that r0 is a copy of r1. If r0 is used in a later instruction and r1 has not been modified in between, we can replace the argument r0 with r1.
Note that this does not remove the potentially redundant mov r0 r1 on its own. If after this pass there are no more reads of r0, the mov r0 r1 instruction will be removed later by dead store elimination.
This optimizes a lot of redundant register moves that happen due to our push/pop optimization.
This is a very straightforward constant folding optimization. We keep track of when a constant value is written to a register and replace later reads of that register with the constant.
For example, consider the following instructions:
add r0 5 3
mov r1 r0When scanning the first instruction, we record that r0 contains 8, which fits in a mix-type byte. When scanning the second instruction, we know that r0 is 8, so we substitute it: the mov becomes mov r1 8.
add r0 5 3
mov r1 8Note that the original add r0 5 3 is not touched by this optimization in case r0 is used somewhere else where it can't be substituted (for example, if a later instruction is ret.) If r0 is actually unused, the instruction will be removed later by dead store elimination.
We also do a few other minor optimizations related to constant arithmetic and logic operations. If an instruction contains an operation that doesn't change the result, for example shrs r1 r0 0 or divs r1 r0 1, we replace it with mov r1 r0. This can eliminate some expensive instructions (especially signed instructions). We can also simplify a few other bitwise operations with constants, for example xor -1 is replaced with not.
Lastly, we optimize jnz and jz, either changing them to jmp or deleting them entirely if the predicate is a constant. This can enable later optimizations (dead code and trivial jump elimination.)
If we reach a jmp or ret instruction, the rest of the block is unreachable: we set a flag that trims all instructions up to the next label.
For example, when a function ends in a statement like return x;, cci/0 often produces code that looks like this:
ldw r0 rfp -4
leave
ret
zero r0
leave
retIt does this because an implicit return is required at the end of functions, and for main(), it must return 0. When closing a function, cci/0 doesn't check whether a return was already made, or whether the function is main(), or whether the function returns void. It just adds return 0; unconditionally. Dead code elimination removes these redundant returns.
This doesn't remove much for ret, but there is an important purpose for removing code after jmp: it can cause the trivial jump optimization to apply. See Trivial Jump Elimination below.
The dead block elimination pass deletes unreachable blocks.
In the forward propagation pass, whenever we find an instruction that references a label, or whenever control flow falls through to a label, we mark that label declaration used. Any labels that are not marked used are unreachable.
The deletion happens in the dead block elimination pass. We simply iterate over all labels in the function. If any label was not marked used, all instructions from that label to the next are deleted.
Dead store elimination is performed in the backward propagation pass. We start at the bottom of the function and scan all the way to the top, keeping track of what (numbered) registers are used.
If a register is possibly used, a preceding store to it must be preserved. If a register is not used, stores to the register are useless, and so can be deleted by dead store elimination.
When we reach a ret instruction, only r0 may be used, because it is the only register used for return values in the standard calling convention. In this case r0 is marked used and all other registers are marked unused.
When we reach a call instruction, r0-r3 may be used, because they carry arguments in the standard calling convention. In this case r0-r3 are marked used and r4-r9 are marked unused.
When we reach a jump instruction (jmp, jz or jnz), all numbered registers may be used because all of them may carry temporaries into the destination block. (This optimizer is not capable of tracking what registers are actually used by other blocks.)
For all other instructions, we first check if it stores to a register that is unused. If so, the instruction is deleted. Otherwise, we mark all input registers to the instruction as used.
This is the most important optimization for speeding up code. Most other optimizations just transform instructions; they do not delete them. The other optimizations that do delete instructions, like dead code and dead block elimination, do so because the instructions were not reachable in the first place.
By contrast this optimization deletes reachable instructions that it determines are useless. All other optimizations rely on this to improve the performance of code.
When a jmp to a label is immediately followed by that label, the jmp can be eliminated; control flow can simply fall through to the label.
Occasionally, and especially in unit tests, constant folding on a false if statement turns a jz/jnz into a jmp to the next label. The rest of the block after the jmp is then eliminated by the dead code optimization. Since the jmp is now immediately followed by the label, the jmp is eliminated by this optimization as well.
For example, consider the cci/0 test case expr/expr-shift.c:
int main(void) {
if ((5 >> 2) != 1) { return 1; }
if ((5 >> 0) != 5) { return 2; }
if ((5 << 2) != 20) { return 3; }
if ((5 << 0) != 5) { return 4; }
}Since the return N; is inside the if statement, the compiler emits a conditional jump (jnz) after it, then emits the return N;. Constant folding computes the expression and turns the jnz into a jmp, and dead code elimination deletes the now unreachable return N;. Since the jmp now immediately precedes its label, it is deleted as well.
This has an important effect on dead store elimination: a jmp would normally mark all registers as used, but since it is eliminated, it does not affect register states. This means dead store elimination continues to work past the label.
The combination of these optimizations mean that all of the code is eliminated and this entire function is turned into the equivalent of return 0;.