Backpatching is a common and handy technique used in assemblers and compilers. While generating code, they often need to encode "jump" instructions to places in the code that don't exist yet. Backpatching is how they do that.
Consider the following assembly code for an imaginary stack machine:
; Is three equal to two? The nation wonders.
START: push 3
push 2
jne NOPE ; jne: "Jump if Not Equal"
jmp YEP ; jmp: "JuMP unconditionally"
; No way! Let's try it again just to be sure.
NOPE: jmp START
YEP: halt
When the assembler first sees the label NOPE, it has no way of knowing where NOPE is going to be in the code at run time. The way to find out where we're going is to look at everything that lies between here and there, and see how big it all is.
Here's what we do: We have two tables. The first table associates label names with lists of offsets. Each time we encounter a reference to a label, we put a dummy in the code and save the offset of that dummy in the list of offsets for the label in question. We'll call this the Operand Offset Table, and when we've finished our first pass through the source code, it'll look like this (for clarity, all instructions and operands are presumed to be one byte each):
"NOPE" => [ 5 ]
"YEP" => [ 7 ]
"START" => [ 9 ]
The second table associates labels with their offsets in the code. We'll call it the Label Offset Table. Whenever we see a label followed by a colon (":"), we'll add that label to the table. If it's already there, we'll error out and scold the user.
At the end of the day, the Label Offset Table looks like this:
"START" => 0
"NOPE" => 8
"YEP" => 10
Now we've seen the whole program and generated all the code, except that we've got a bunch of jump instructions with meaningless operands. The next step is to fix the operands, which is easy: Buzz through the Operand Offset Table. For each entry, look up that label by name in the Label Offset Table (if it's not there, that's the linker's headache). Plug the offset of the label into each of the operands where it belongs. You're done.
When you're generating code in a compiler, gotos are more complicated than jumps are in an assembler, because you've got to worry about scope and God knows what-all else. Compilers also do backpatching for control flow, and that's much easier. If you're recursively walking a parse tree1, let's say you have a generate_code_for_if_statement() function. It'll get a parse tree node with at most three branches: A boolean expression, an "if true" branch, and maybe an "else" branch2. All the backpatching you'll need is two offsets: The offset of the start of the else branch (if any), and the offset of the next instruction following the whole statement. You don't have to have any tables for that, just four local unsigned longs, named appropriately. You don't have to worry about what's inside those branches, because you're recursive.
// This is example code. Assume that our "compiler" class
// has whatever a compiler class would obviously need.
void compiler::generate_code_for_if_statement( ptnode * stmt )
{
ulong jmp_over_else_operand_offset = 0;
ulong jz_on_boolean_operand_offset = 0;
ulong else_branch_offset = 0;
ulong stmt_end_offset = 0;
// The boolean thing.
generate_code( stmt->branch[ 0 ] );
// If the expression evaluates to zero ("false"), jump to
// the next thing after the code for the "true" branch.
// That "thing" may be the "else" branch, if we've got one.
// JZ means "Jump if Zero". Since we're a stack machine,
// the value which may or may not be zero is the top value
// on the stack, which the instruction will pop. The code
// in the boolean branch ought to leave something there
// when it executes; if it doesn't, there's a bug somewhere
// upstream in the compiler, and the stack will get into an
// inconsistent state at run time, probably causing us to
// crash someplace else. With luck and the grace of God,
// we'll underflow right here, but don't count on it.
add_instruction( JZ );
// Offset in code of what we're about to add.
jz_on_boolean_operand_offset = next_offset();
// Dummy operand for JZ, to be backpatched later.
add_operand_4( 0 );
// "true" branch. We'll fall through to this if the JZ
// doesn't wake up and put us elsewhere.
generate_code( stmt->branch[ 1 ] );
// Is there an "else"?
if ( stmt->branch[ 2 ] ) {
// If there's an "else", the "true" branch will have to
// jump over it.
add_instruction( JMP );
// Save for backpatching
jmp_over_else_operand_offset = next_offset();
// Plug in a dummy
add_operand_4( 0 );
else_branch_offset = next_offset();
generate_code( stmt->branch[ 2 ] );
stmt_end_offset = next_offset();
set_operand_4( jmp_over_else_operand_offset,
stmt_end_offset );
set_operand_4( jz_on_boolean_operand_offset,
else_branch_offset );
} else {
// If there's no "else" branch, the "false" case of the
// conditional will dump us out after the end of the
// "if".
stmt_end_offset = next_offset();
set_operand_4( jz_on_boolean_operand_offset,
stmt_end_offset );
}
}
You could invent enormously more complicated and less efficient ways to do the same thing, but this one is good enough for me. Doing the same thing for a switch statement does get a bit hairier, of course.
I did see a cool way of doing the if/else stuff in (I think) The UNIX Programming Environment by Kernighan and Pike: Branch code is generated by recursive functions, each of which returns the offset you'll need to jump over it. So you don't bother storing those, you just plug 'em right in.
For more detail, see Compilers: Principles, Techniques and Tools by Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman (Addison-Wesley 1986; ISBN 0-201-10088-6), a.k.a. the "Dragon Book".
If there are any errors in the above, I hope somebody will be kind enough to let me know.
1 It may seem tempting to generate code right in the parser. Don't. Just to begin with, think of all the state that a recursive parse-tree walker stores on the call stack, and then think of having to keep it all straight some other way. This stuff's weird enough without trying to do everything at once.
2 An "else if" is just an "if" within an otherwise empty "else":
// This...
if ( a ) b;
else if ( b ) c;
else if ( c ) d;
// ...is exactly equivalent to this:
if ( a ) {
b;
} else {
if ( b ) {
c;
} else {
if ( c ) {
d;
}
}
}
You're better off chaining them like that than going berserk trying to do something clever. As I recall, Perl has that goofy "elsif" keyword precisely because they decided to require curly braces on all code controlled by "if"s. As a charitable observer, I can't comment on their motives for doing that.