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?