Compiler design prevent register override

Question

I'm trying to write a compiler for a self-designed CPU with accompanying instruction set. The CPU has 3 registers, 2 input registers (B and C) and one output register (D). When for example an ADD instruction is executed the sum of B and C is calculated and stored in D.

I'm trying to write the compiler with the visitor design pattern: I have a bunch of language tree classes like "IfStatement", "Addition", "Integer" and a visitor "Compiler". The visitor would look at each node of the tree and append bytecode to the end of the bytecode list. I can't figure out how to cleanly handle register overrides: when evaluating the expression

2*(7+3)

the generated bytecode is

PUTb 2
PUTb 7
PUTc 3
ADD
MOVE D C
MUL

As you can see the 2 is overridden by the 7. I want the compiler to realize it can reverse the order to

(7+3)*2

or that it can store temporary result is RAM, using some other instructions, this will certainly be necessary for more complex expressions like

(7-5)*(8+3)

Is there a clean/object-oriented way to handle this? Is the Visitor pattern not appropriate here? Do I need to look at some advanced techniques like register coloring? The compiler will be written in Java, bu I don't think that really matters.

Answer 1

You're going to need an overflow area, perhaps a stack, or some chunk of memory.

You'll also want to get the generated code correct before optimizing it, because optimizing broken code is basically impossible.

So , given a stack, you should have something like: PUT b,2; Push b; Put b,7; Put c,3; ADD; Pop b; MUL and if using memory, PUT b,2; Store b @1; Put b,7; Put c,3; ADD; Load b @1; MUL. Next, to get the optimization, you can have a separate pass that balances the tree, by changing the order of the operands based on simple weight.

EDIT:

You create a data structure that tracks the contents of the registers (you might assume empty at statement start). Each time you generate an instruction you update that data structure to mark what is in it (e.g. what tree node and/or what operand, i.e.variable or constant, or overflow temporary variable).

Before you generate an operation, you ensure that its sources are in the registers as needed, and if not you perform a load from the overflow area, or variable area, or constant area/immediates, or from another register.

(By design, you shouldn't have the case where you need to generate anything else at this point other than a load of some kind, e.g. if you are about to generate the MUL, you won't have to generate an ADD, because that should have been handled already in by the appropriate visiting traversal.)

But -- before you do any load of operands (which will overwrite the register) you generate a store to an overflow area if there is anything being tracked. Also do the same for the target/output register (e.g. of MUL). And the whole time updating your tracking structure so the next instruction generated will have the state of the registers & overflow temps as of the current point in the code.