How to optimize a mixed stack/register bytecode with control flow and side effects?

Question

I'm trying to figure out a technique to optimize bytecode for the following virtual machine:

• Bytecode is a flat list of instructions, with execution starting from the first instruction.

• Stack bytecode: instructions like i++, a+b, method calls f(a, b, c), etc. occur on the top 1, 2, N values on an operand stack, and leave their result on the top of the operand stack

• Bytecode to discard the top value of the stack, e.g. if you call a method for side effects but don't want the return value

• An array of N local variables, instructions to copy values from a local variable to/from the top of the operand stack

• Unconditional GOTO, conditional JUMPs with various predicates on the top of the operand stack

• Side effecting instructions: reading/writing the top value of the operand stack to global variables

The input will be some valid bytecode for this virtual machine, but with some redundancy: some instructions will be unreachable, some variables that are computed on the operand-stack will get popped, some variables stored in local-variables will get over-written without ever being read, some GOTOs will go first to another GOTO rather than straight to the final destination.

I know for a start, a forward traversal following jumps will tell us where the reachable instructions are and let us eliminate unreachable instructions. But how about the others: optimizing away code computing un-used values, or redundant GOTOs?

I know for side-effect-free programs I can compute a dataflow graph, starting from the returned value, and walk backwards to see which computed values are unused. But that doesn't seem to work in the case where there are side effects whose order I need to preserve, since a dataflow graph would just ignore them. Presumably I'll need a controlflow graph in addition to the dataflow graph, but I'm not sure how the two graphs would work together to help me optimize the bytecode.

What kinds of techniques can I use to optimize those away in the presence of control flow and global side effects (both reads and writes) whose order needs to be preserved? Does CPS or SSA or any of the other intermediate representation formats help in this?

Answer 1

There's a huge body of research on this topic, so I really recommend reading a compiler book. Muchnik's book can work well as a reference. I really like Modern Compiler Implementation but I think it's out of print.

If you're the kind that learns better by reading code, the Scala compiler does all of the above, and the JVM fits all of the bullet points you listed for your VM.

More to the point:

• I would highly recommend a representation that doesn't use the stack. It's painful to keep it consistent when you modify the code: if you remove an instruction that pushes a value on the stack on one branch you need to add a drop on the other branches too, or else the stack will be inconsistent at the merge point. You can generate stack-based code easily from register-based code after all optimization passes are done

• You would like to remove "dead-code". If you representation is already in a simple form (I think ANF is way simpler than CPS and I used it successfully -- roughly, it breaks all expressions into simple two-operand ones and temporaries) you can simply mark as "live" all effectful instructions. You'd then need "Liveness" information, which computes what assignments are used later (you'd go backwards starting with all live instructions and mark as "live" their inputs, and so on). The tricky bits are at merge points in the CFG, where you need to approximate conservatively (basically, know less and less about your program to account for the uncertainty of which branch was taken)

• I think the simplest way is to keep the control flow as your primary data structure and compute data-flow information (such as Liveness) whenever you need it

• if you have the choice, use a tree rather than a CFG. A tree preserves the structure of your program (while, ifs), while conditional and unconditional jumps are way more powerful and you'll spend effort re-computing what was thrown away from the AST (for instance, finding the dominators in the CFG)

• you will probably run dead-code a few times in your pipeline, since each optimization pass may produce more dead-code. That's all right, and usually better than to make every optimization pass smarter and unnecessarily complex.

Answer 2

Each thing you're referring to requires/has its own individual optimization algorithm.  An optimizer is a collection of optimization algorithms, run in a sequence, often even repeated until no changes.

I know for a start, a forward traversal following jumps will tell us where the reachable instructions are and let us eliminate unreachable instructions. But how about the others: optimizing away code computing un-used values, or redundant GOTOs?

Unused expressions are optimized (i.e. eliminated) one instruction at a time, by identifying the last value not used, and eliminating the instruction that generates that value.  One instruction at a time, the whole unused expression can be removed.  The basic algorithm identifies a single instruction whose value is unused, and the algorithm is repeated until no changes.

Redundant branches are handled with their own specific optimization that looks for branches to branches.  Sometimes code is rearranged as well to improve conditional branch fall thru.  There are also loop oriented optimizations to remove unconditional branches at the end of the loop (in favor of conditional branches).

In summary, each transformation is an individual optimization, and an optimizing compiler has hundreds of these, some of which are repeated until they cannot match the pattern(s) they're looking for.

But that doesn't seem to work in the case where there are side effects whose order I need to preserve, since a dataflow graph would just ignore them. Presumably I'll need a controlflow graph in addition to the dataflow graph, but I'm not sure how the two graphs would work together to help me optimize the bytecode.

Data flow analysis necessarily takes control flow into account.

Control flow analysis involves identifying basic blocks, which are sequences of instructions uninterrupted by branching, e.g. starting at a label and ending with a branch instruction or another label.  Further control flow analysis links the basic blocks, identifying loops, if-then-else constructs, etc..

The output of control flow analysis is a graph structure, meaning nodes & edges; nodes for basic blocks, and edges that connect them.

Data flow analysis usually takes two forms: analysis within the basic blocks and analysis between basic blocks' edges following the control flow.  Typically, these are also done bidirectionally, forwards: tracking reaching definitions, and backwards: tracking exposed uses.  So, we get information on definitions of variables and uses of variables.

The output of data flow is usually some variation on bit vectors, where each bit position represents a different variable in the program.  If the bit is set then there is a definition of the variable (for definitions, or a use for usages, and if clear, there isn't).  (Data flow algorithms that operate on the control flow graph and are fixpoint algorithms, meaning they converge: they can be repeated until no changes.)

We can consider that before and after each instruction in the program, there are two potential bit vectors that represent what (preceding) definitions reach that location and what (succeeding) uses consume results — though usually this information is not stored at every instruction, but only before the beginning and after the ending of each basic block (instruction-level information is reproducible during traversal of the basic block).

Optimizations use this data flow information in various ways.  For example, when a definition of a variable does not have a usage, this can be detected, which is how unused computations are identified.  For another example, it can be determined that two variables are (or aren't) live at the same point in the program, and thus, need (or don't need) different CPU registers.

SSA is a form of data flow analysis that introduces and tracks versions of variables so that the information is globally correct (it is accurate location-free), whereas older (arguably simpler) data flow algorithms track variables directly and such tracking must be understood in context of location.

Answer 3

You just described a programming language called Forth. It is open-source and has many implementations covering the relatively naive, to the very sophisticated.

One technique is to treat every thing in your machine: the stack, the heap, the file system, the screen, etc.. as having an associated action list with each action taking the value produced by the previous action, and returning an updated value. Every instruction is essentially a set of actions that are appended to these lists.

Actions will still need a relative order but it does not need to be strict in the sense of each action being sequential with all others. It does however need to be strict enough so that an action always reads the correct value, and presents that value to latter operations on the variable. This allows these actions to be ignorant of the state of the rest of the system, they only care about the object they are being applied to. Any other information they use was either passed in when the action was added to the list, or another action in an earlier temporal action grouping has assigned the value.

Following this, two (or more) instructions produce a set of actions on these lists. Now some actions will cancel each other out. Say swap a,b; swap b,a;. These have zero effect on the outcome when they are next to each other. The actions that are left are the necessary and sufficient actions that need to occur for that code to have been executed.

To optimse this code:

1. Define a new instruction which has exactly these actions as its definition.
2. Find a shorter series of instructions with the same actions as its definition, hopefully with few/no cancelling out actions.

I would also step back and look at the program structure represented by the source. If this is identical to the machine structure, ignore this, but if it is in higher-order structures try applying your optimisations at this graph level. At this level of semantic detail it is much simplier to apply specific optimisations as you don't have to recognise them from a sequence of smaller steps, and some common queries regarding branches, siblings, etc.. are trivial.