skip to content

How does an intermediate bytecode change if it is stack-based rather than register-based?

level: seniorimportance: nice to knowfreq 30%

answer

  1. operands implicit versus operands named
  2. post-order walk emits the stack form
  3. more instructions, narrower each
  4. provenance needs a stack simulation
  5. naming costs work, buys explicit data flow

basics

~20 s

Stack-based code leaves operands implicit on an operand stack: instructions are short and trivial to emit from a tree walk, but the stream is longer and data flow must be reconstructed. Register-based code names operands explicitly, costing wider instructions and a naming step.

solid answer

~50 s

A **stack-based** intermediate code takes its operands from an operand stack and pushes results back: `(a + b) * c` becomes push `a`, push `b`, `add`, push `c`, `mul` — five instructions, none of which mentions where its inputs are. A **register-based** form names operands: `t1 = a + b`, `t2 = t1 * c` — two instructions. The stack form is generated by a post-order tree walk with no bookkeeping, encodes compactly because most instructions carry no operand field, and is simple to check for well-formedness. The costs are that the stream is longer, so a straightforward interpreter dispatches more often, and that operand provenance is implicit — anything later that wants to know which instruction produced a value must simulate the stack to recover it. The register form pays a naming step up front and wider encodings in exchange for explicit data flow and fewer instructions.

go deeper

for a junior

Recall that some intermediate codes keep operands on a stack that instructions push and pop, while others name their operands directly inside the instruction.

for a middle

Emit both forms for a two-operator expression and compare them: five instructions against two here, with the stack form carrying no operand fields at all.

for a senior

Argue the choice for a real artefact — a code you must validate before trusting versus one you must analyse and translate — and name the stack simulation that recovers data flow when you picked the implicit form.

for a principal

Own the encoding as a long-lived boundary: it constrains who can produce the code, how cheaply it can be verified, and how much work every consumer must repeat before it can do anything useful.

## Two ways to say where the operands are An intermediate code has to answer one question on every instruction: *where do the inputs come from and where does the output go?* There are two classic answers. **Implicitly, through a stack.** Instructions pop their operands from an operand stack and push their result. `add` says nothing about *what* it adds; the stack shape at that point decides. **Explicitly, by name.** Instructions carry operand fields: `mul t3, t1, t2`. Nothing is implicit, and there is no stack discipline to maintain. ## The same expression, both ways For `(a + b) * c`: ``` ; stack-based: 5 instructions push a push b add ; pops two, pushes one push c mul ; pops two, pushes one ; register-based: 2 instructions t1 = a + b t2 = t1 * c ``` Five against two. The counts scale roughly that way in general: the stack form pays an instruction for every operand it brings into position, while the register form names operands inside the instruction that uses them. ## The trade, item by item | Dimension | Stack-based | Register-based | |---|---|---| | Instruction count for an expression | Higher — operands pushed separately | Lower — operands named in place | | Bytes per instruction | Smaller: most carry no operand field | Larger: operand fields must be encoded | | Total size of the stream | Often comparable; more instructions, each narrower | Often comparable from the other direction | | Generating it | A post-order walk emits it directly | Needs a naming step for intermediates | | Dispatches in a simple interpreter | More, one per instruction | Fewer | | Data flow | Implicit in stack depth; must be simulated to recover | Written in the operand fields | | Verifying well-formedness | Straightforward: track stack depth and shape | Needs the naming to be checked instead | | Distance to a register machine | Further: the stack must be undone first | Closer: operands are already named | The row that decides most designs is **data flow**. Any later stage that asks "which instruction produced this value?" gets an answer for free from a register form. From a stack form it must walk the block simulating pushes and pops to rebuild the same information — work that is mechanical but must be done before anything interesting can be. ## When each is the right choice - A **stack form** suits a compact, easily produced, easily validated encoding. If the code is generated by many producers, shipped over a wire, or checked before it is trusted, the simplicity of "emit a post-order walk" and "validate by tracking depth" is worth real money. - A **register form** suits a code you intend to analyse, rewrite or translate to machine code. Its operands are already in the shape the target wants, and the flat, named form is the one later rewrites are comfortable on. It is not either/or over the whole pipeline. A compiler can accept a compact stack form at the boundary and convert it to a named form internally — a conversion that is exactly the stack simulation described above. Ecosystems differ in which they standardise on, and in whether an execution engine converts before running; the trade-offs above are what drives that difference rather than any one design being better. ## Two claims that get inverted 1. **"Stack code is bigger."** It is *longer* — more instructions — but each instruction is *narrower*, because operand fields are what take space. Which stream is bigger in bytes depends on the encoding, and the two often land close together. 2. **"Register code is easier to generate."** The opposite, at this stage: the stack form falls out of a tree walk with no bookkeeping, while the register form needs fresh names allocated as you go. ## What interviewers listen for A candidate who can emit both forms for a small expression, count the instructions honestly, and then name the real trade — compactness and ease of generation against explicit data flow — has the material. One who reaches for "registers are faster" without saying why the intermediate form's shape matters has not.

  • Why is a stack-based form easy to validate before trusting it?
    Well-formedness is largely a property of stack depth and operand shape at each point, which can be checked by a single pass that simulates depth along every path. There is no naming scheme to verify, and a mismatch shows up immediately as an underflow or an inconsistent depth at a merge.
  • What has to happen before a stack-based form can be translated to a register machine?
    The implicit data flow must be made explicit: walk each block simulating the pushes and pops, and give a name to every value that is pushed. After that the code is in effect a named form, and the usual mapping onto real registers can proceed.
  • Does a lower instruction count mean the register form runs faster?
    For a simple interpreter, fewer dispatches usually help. But the comparison depends on how the code is executed — an engine that translates before running erases much of the difference — and on encoding size and locality. Instruction count alone is not a performance argument.

saying these in an interview costs you the question

  • Says stack-based encodings are wider per instruction than register ones
  • Claims a register-based form is easier to emit from a tree
  • Assumes instruction count alone decides which stream is bigger
  • Thinks a stack form cannot express branches or jumps
  • Treats the choice as settled by speed with no other consideration