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


the generated bytecode is

PUTb 2
PUTb 7
PUTc 3

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


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


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.

  • 3
    Your real problem appears to be an incorrectly constructed parse tree. Or perhaps your visitor should be prepending operations (assuming a top-down traversal). In either case, Stack Overflow would probably be a better place to post, but you'd need to show your code and how the particular expression transforms into a parse tree.
    – kdgregory
    Jan 31, 2016 at 15:32
  • @kdgregory I don't actually have a parse tree, I have a AST. The object representation of that first expression looks like this: Multiplication(2, Addition(7, 3)). I don't think there is anything wrong there, the problem is that I'm naively traversing the AST. Jan 31, 2016 at 15:43
  • 2
    Here's a hint: you can only emit bytecode for an operation after you've emitted bycode for the operations that it depends on. Therefore, you should emit all bytecode for the addition before you emit any bytecode for the multiplication. This will turn into a depth-first traversal of your "object representation," where bytecode for the node is emitted after bytecode for both of its child nodes.
    – kdgregory
    Jan 31, 2016 at 16:07
  • @kdgregory I think that's what I'm doing right now: the first child (2) is put in register B, the second child (7+3) is calculated and put in register C. Then the multiplication itself is carried out. The problem is that calculating the second child overrides the first child. Jan 31, 2016 at 16:11
  • 2
    Here's what you said above: "it can store temporary result is RAM". What aren't you doing?
    – kdgregory
    Jan 31, 2016 at 16:20

1 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.


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.

  • I am asking how to make the compiler understand that register B will be overridden and that it needs to store it temporarily in RAM (using Store and Load instructions) in a cleanly designed way. Jan 31, 2016 at 16:06
  • @ToddSewell: Initially, the compiler should simply assume that both register B and C contain valuable information that needs to be preserved. After that, you could start optimizing by dropping unneeded stores. Jan 31, 2016 at 16:31
  • But that delays the problem: how do I detect unneeded stores? Jan 31, 2016 at 16:40
  • @Todd see my update
    – Erik Eidt
    Jan 31, 2016 at 16:47
  • Is the overflow/memory area also tracked by the same data structure? And what do you mean by "if there is anything being tracked" in your last paragraph? Jan 31, 2016 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.