What is the common procedure when producing jump targets in bytecode?

Question

Over the course of the past few days, I've been trying many different methods for correctly calculating jump targets in bytecode, but none have been practical or reliable. Furthermore, the methods I've tried did not allow nested if-statements and/or elif statements, which are important features of any language.

I am walking my abstract syntax tree recursively, testing the type of each node, and generating the appropriate instructions. However, I am unsure of how to properly generate the instructions for an conditional branch node. I understand to basic logic the instructions I generate should follow:

• If the condition that the if/elif statement is testing is true, then run the if/elif statement's body, and jump past all other logic branches(elif/else) under this if/elif statement.
• Otherwise, jump to the next nearest logic branch under this if/elif statement.

What I do not understand though, how I should calculate the correct jump to the "next nearest branch" or the jump past "all other logic branches".

I also attempted to look over the source code for the bytecode compiler for Python - implemented in compile.c - but because of my lack of skill in C, I didn't have a very good grasp on the concepts used.

However, multiple languages have implemented conditional logic before, and I am fairly sure that there is common method used when implementing things such as this. If so, what is this method, and how can it be implemented to generate code for multiple branch instructions?

Answer 1

Not all virtual machines use a linear byte code. If the byte code forms a graph data structure, the conditional operation can directly reference all branches, and no explicit jump targets have to be calculated (in fact, the concept of a jump target is somewhat nonsensical with such a byte code). I have used this approach in some toy language implementations.

Most “real” byte codes use a multi pass approach to calculate jump targets. Let's first visualize the byte code structure we need:

    ,-------------------------.
   |                          v
branch, then-branch..., jump, else-branch..., end
                          |                   ^ 
                          `-------------------'

There is some branching opcode that either continues directly with the then-branch, or jumps into the else-branch. At the end of the then-branch, an unconditional jump points to the end.

When we emit the byte code, we can emit the branch and jump instructions with dummy values, and then go back to fix them later:

branch, then-branch..., jump, else-branch..., end
   |                      |
   v                      v
  ???                    ???

Once the byte code is emitted, we know precisely how long the then-branch and the else-branch is. We can then overwrite all jumps with their correct target. In pseudcode:

compile_conditional(cond, then, else):
   compile(cond)
   branch = emit(branch, null)

   compile_all(then)
   jump = emit(jump, null)

   branch.target = current_location

   compile_all(else)

   jump.target = current_location

Instead of absolute targets one would usually prefer relative jumps so that the byte code can be moved around freely.

The CPython code you linked to does something like this: the jump targets are compiled before the jump so that the target is known. The trick is that it first generates a linked list of basic blocks (similar to the byte code graph mentioned above). Each jump targets one basic block. The block then contains any instructions. We have a basic block for the end, a block for the else-branch, and a block for the then-branch (see compiler_if()). An assembly pass assemble_jump_offsets() then iterates through the blocks and calculates the block offsets in the byte code. Once that is done, we can iterate through all instructions in all blocks and update the jump instructions with a relative target.

Answer 2

I use a routine that evaluates a given AST for branching to a desired label (with a boolean indicating normal or reversal of the jump condition).

In pseudo code, (I'm trying to convey the algorithm, not a coding style) I generate code for the if statement as follows:

void generateCodeForIfStatement ( ifNode ) {
    var targetForFalseCondition = generateLabel ();
    generateConditionalTestAndBranch ( ifNode.conditionalExpression, 
                                       targetForFalseCondition,
                                       false );
    generateCodeForStatement ( ifNode.thenPart );
    if ( ! ifNode.hasElsePart () ) {
        placeLabelHere ( targetForFalseCondition );
    }
    else {
        var targetAfterElse = generateLabel ();
        jumpTo ( targetAfterElse );
        placeLabelHere ( targetForFalseCondition );
        generateCodeForStatement ( ifNode.elsePart );
        placeLabelHere ( targetAfterElse );
    }
}

This handles both if-then and if-then-else. The conditional expression is evaluated and should branch to the else part (or at least around the then-part if the else-part is absent) if the expression evaluates to false. Thus, we pass false to generateConditionalTestAndBranch for the jumpIfTrue parameter, to get things started off.

We also need to have a capability to generate a forward label -- i.e we need to use the label now, but it is at an as yet unknown/undefined location; then to be able to place it (define its location) in the generated code later when we know. Hopefully you can see that in the pseudo code.

In more detail, whenever an as-yet-undefined label is used in a generated instruction, the associated byte code instruction can be put into a list so that later when the label's location is defined, that list (of instructions) is fixed up (this is the part where (forward) branch target operands are translated from labels, as the labels eventually disappear from the final machine/byte code), without necessarily using a pass over the generated code.

(If variable sized instructions are available for branches (e.g. a short instruction for a short distance or a long instruction for a long distance), then there is opportunity for optimization of the branch instruction sizes for forward branches.)

---

Next, this conditional expression evaluator generates a test and branch instruction sequence that goes to the specified jumpTarget parameter when the condition evaluates to true, and falls thru to any code that comes (is placed) after when the condition evaluates to false.

void generateConditionalTestAndBranch ( AST conditionalExpression,                      
                                       BranchTarget jumpTarget, 
                                       bool jumpOnTrue ) {
    switch ( conditionalExpression.nodeType ) {
        ...
        case "!" :
            generateConditionalTestAndBranch ( ast.child, target, ! jumpOnTrue );
            break;
        case "&&" :
            if ( jumpOnTrue )
                generateTestAndJumpAround ( ast, target, jumpOnTrue );
            else
                generateTestAndJumpThru ( ast, target, jumpOnTrue );
            break;
        case "||" :
            if ( jumpOnTrue )
                generateTestAndJumpThru ( ast, target, jumpOnTrue );
            else
                generateTestAndJumpAround ( ast, target, jumpOnTrue );
           break;
        ...
    }
}

As you can see, when you have a ! operator, the code simply reverses the jumpIfTrue flag and continues evaluating the rest.

&& and || also have short circuit evaluation that introduces branches and nested conditions (expressions), and look very similar to each other; this as they are related (e.g. by demorgan). They each evaluate the left child and right child in a context given the current value of jumpIfTrue.

Finally, following are the simple helper functions for the short circuit evaluation shared by && and ||. Of course, these helpers are designed to support composing &&, || and ! expressions, reversing the jump direction as needed.

---

void generateTestAndJumpThru ( AST binaryNode, BranchTarget target, bool jumpIfTrue ) {
    generateConditionalTestAndBranch ( binaryNode.leftChild, target, jumpIfTrue );
    generateConditionalTestAndBranch ( binaryNode.rightChild, target, jumpIfTrue );
}

To evaluate if ( a && b ), we need branch to the else part if either evaluates to false, so, we test a and branch to the else part if it is false, then test b and branch to the else part if it is false.

---

void generateTestAndJumpAround ( AST binaryNode, BranchTarget target, bool jumpIfTrue ) {
    var around = generateLabel ();
    generateConditionalTestAndBranch ( binaryNode.leftChild, around, ! jumpIfTrue );
    generateConditionalTestAndBranch ( binaryNode.rightChild, target, jumpIfTrue );
    placeLabelHere ( around );
}

To evaluate if ( a || b ), we need to branch to the else part both are false, so, we first test a, and if it is true we can skip the b evaluation. In case a is false we go on to test b, and if that is also false, we go to the else part.

---

Also, when the only (or the first) statement of the then-part or the else-part is a break, continue, return, or goto statement, there are additional code generation optimizations that can be easily performed here (to forgo branches to branches; alternatively those can be cleaned up later).