5

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?

  • 2
    Generating bytecode is a very similar process to generating machine code from assembly language. You may want to look at how assemblers solve this problem (particularly single pass assemblers, as they have the best solution IMO -- see this stackoverflow question for a description of how they work). – Periata Breatta Jan 2 '17 at 11:02
5

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.

  • "Instead of absolute targets one would usually prefer relative jumps so that the byte code can be moved around freely." - I am not exactly sure what you mean by that statement. Could you elaborate a bit. Thanks. – Christian Dean Jan 1 '17 at 4:16
  • @Engineer, this has to do with the available addressing modes of the instruction set for branch target operands. Many instruction sets provide absolute addressing capabilities (for branch targets and sometimes also for load/store/memory operands), many also provide pc-relative branches... – Erik Eidt Jan 1 '17 at 4:48
  • 2
    @Engineer, PC relative branches (and sometimes memory targets for constants and tables) allow for position independent code, which is pretty nice. The same code can be mapped into different address spaces at different locations for different users and still works fine. Absolute branches mean that the code either has to be loaded where it was expected, or, the branches/operands have to be fixed up after loading (which would mean the code must be loaded into (at least temporarily) writable memory). – Erik Eidt Jan 1 '17 at 4:49
  • 1
    @Engineer In machine code, the main motivation for relative jumps is operand size. An absolute address needs full pointer-size (e.g. 64 bits). But most jumps only skip tens or hundreds of instructions. Storing a program-counter delta instead of a full address allows the machine code to be more compact. Position-independent code as mentioned by Erik Eidt is also nice, and a precondition for security features like ASLR. For bytecodes, I don't really see the point. In theory relative jumps allow you to delete instructions without having to update every jump, simplifying some optimizations. – amon Jan 1 '17 at 10:24
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).

  • Thanks for the answer. I believe I understand most of your solution, I'm a little confused, however, about what generateLabel() is returning? While doing more research I came across a term - backtracking - which seems the use the same method. What exactly is generateLabel() returning? A pattern of bytes? – Christian Dean Jan 1 '17 at 3:30
  • 1
    It returns an object that represent an "assembly language" label. E.g. L1:. Aka a branch target; that you can use as the operand of a conditional or unconditional branch. Note that as machine code or byte code, these labels no longer exists, as by then they have all been resolved/defined, so the branch instructions that use them are now using pc relative offsets or absolute addresses for their target. The labels are a temporary mechanism to translate logical branch targets into machine/byte code operands. – Erik Eidt Jan 1 '17 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.