Compiling Your Code Into Bytecode

The last lesson built the machine that runs bytecode. But bytecode does not fall from the sky. Something has to translate your ordinary source into that flat list of instructions, and that something is a compiler, the same kind of tool that turns any language into a lower form. Virtualization simply points a compiler at an invented target instead of a real CPU. This lesson walks that translation end to end.

Two halves of one pipeline

Every virtualizer has a front end and a back end. The front end reads your source and understands its structure. The back end emits instructions for the target machine. In between sits a syntax tree, the shared representation both halves agree on. If you took the level on how programs are represented, you have met all of these already. Virtualization is those exact stages with the final target swapped out.

Step one: source becomes a tree

Text is a bad shape to compile from, because meaning in code is nested, not linear. So the first move is to parse the source into a tree that captures which parts belong inside which. In the expression two plus three times four, the multiplication has to sit deeper in the tree than the addition, because it must happen first. The tree, not the left-to-right text, is what encodes that order.

Expand the tree above. The assignment sits at the top. Its value is an addition, and one side of that addition is a multiplication holding three and four. Edit the source and watch the shape change. This tree is the exact thing the back end is about to walk.

Step two: walking the tree to emit instructions

The back end visits the tree from the bottom up. To emit code for an addition, it first emits the code that leaves the left value on the stack, then the code that leaves the right value on the stack, then a single add instruction to combine them. Applied to the whole tree, this rule produces a flat instruction stream where operands are always pushed before the operation that consumes them. That is why a stack machine works so cleanly: a tree walk naturally produces exactly the order a stack wants.

source:   answer = 2 + 3 * 4

tree:     Assign answer
            +
             2
             *
              3
              4

emitted:  PUSH 2
          PUSH 3
          PUSH 4
          MUL          ; 3 * 4 first, because it sits deeper
          ADD          ; then 2 + 12
          STORE answer

Think of the tree walk as reading a set of nested boxes and writing a to-do list. You cannot combine two things until both are on the table, so the list always says fetch this, fetch that, then combine, working outward from the innermost box. The emitted instructions are just that to-do list, flattened into a straight line.

Why the emitted order surprises people

The written source reads two plus three times four, left to right. The emitted bytecode computes three times four first. Nothing was reordered dishonestly; the tree captured the real order of operations, and the flat stream simply spells it out. This is the first reason virtualized output looks nothing like your source: even before any protection tricks, a faithful compile already rearranges the surface into stack order and strips away every plus sign, name, and parenthesis.

A statement compiles the same way. An if becomes code that evaluates the condition, then a conditional jump that skips the body when the condition is false, then the body, then a landing spot. A while adds a jump at the bottom back to the condition. The tree walk has a small rule for each kind of node, and stitched together those rules turn an entire program into one instruction stream with jumps standing in for every branch and loop.

This is also where per-build variation is injected cleanly. Because the back end is the only place opcode numbers are chosen, a virtualizer can assign a fresh numbering to push, add, jump, and the rest on every build, and emit against that numbering. The front end and tree are unchanged; only the final encoding differs. An attacker who decoded one build's numbers has learned a table the next build discards. The later lesson on per-build machines returns to exactly this.

Virtualization is a compiler with an invented target. Parse source into a tree that captures real precedence, walk the tree bottom up emitting operands before operations, and stitch jumps in for branches and loops. The output is a flat instruction stream that no longer resembles the source, before a single protection trick is added.

Frequently asked questions