5
$\begingroup$

I understand how backpatching works during intermediate code generation, but I do not understand why it is needed.

A common argument for using backpatching during intermediate code generation is as follows:

Suppose the intermediate code generated is:

goto L1

...

L1:

When goto L1 is generated, the actual address of the target of goto is unknown. So we use a label L1 as a placeholder. When the code L1: is generated, we can backpatch the address where L1: is to goto L1.

However, why should we use the actual address for L1 during intermediate code generation? For example, LLVM IR uses symbolic labels in branch instructions instead of their actual addresses.

Even the RISC-V assembly language, which is often used as a targe language during targe code generation, uses symbolic labels in jump instructions. Isn't it the job of an assembler to replace labels with actual addresses?


The related post does not address my concerns above.

$\endgroup$
1
  • 2
    $\begingroup$ Internally, LLVM does not really use symbolic labels. It uses direct pointers to blocks on the CFG, where a block has a label. Its only when serializing the graph, that the label names really have any relevance. $\endgroup$ Commented May 18, 2023 at 14:10

6 Answers 6

12
$\begingroup$

In the case of LLVM IR, I think the point here is not backpatching an address, but backpatching a label. If the label is "created" at the point where it is in the code, any forward jumps to it will have to be backpatched.

There are other ways to define an API for building IRs, but this works.

Backpatching addresses is the job of an assembler, however some compilers compile directly to machine language, not going through an assembler. This is true of LLVM, which can be used as a JIT compiler where calling out to an assembler would hinder performance.

Contrary to what the other answer says, the CPU typically doesn't want an address. Most CPUs do provide a way to jump to an address, but more commonly, it is more efficient to jump to a relative offset, i.e. the difference between the address of the jump instruction and the address of the target. Not only is the code sequence shorter, it is more position-independent.

Some CPUs have "long" and "short" jump instructions, where the "short" version will only let you jump less than 128 bytes away in either direction (give or take), but the short instruction is one byte shorter. Because the short instruction is shorter, this means that whether or not you can use a "short" jump may depend on whether or not any jump instructions between the jump and its target are "short" or not.

If the the goal is to minimise the final binary size, the general case of this problem is known to be NP-complete.

For some classic algorithms to solve this, see:

$\endgroup$
3
  • 1
    $\begingroup$ @hengxin Thanks for the fix! $\endgroup$
    – Pseudonym
    Commented May 18, 2023 at 9:53
  • 1
    $\begingroup$ Since you bring up short/long relative branches (like for x86 or maybe ARM Thumb or RISC-V compressed), see also Why is the "start small" algorithm for branch displacement not optimal? - it is if you don't have any directives like align 16 that expand to a variable amount of bytes depending on their start address. But most real code does, and my answer shows an example of an optimal solution that start-small doesn't find. Real assemblers do use "start small" because it's much faster than NP-complete, usually just a few passes over the list of branches $\endgroup$ Commented May 19, 2023 at 19:53
  • $\begingroup$ Nice! Of course, enforcing alignment wasn't useful or appropriate in the 1970s, given that memories were much smaller and there was no advantage to jumping to the start of a cache line. It still may not be appropriate on small microcontrollers today, but for modern general computing, I like your approach. $\endgroup$
    – Pseudonym
    Commented May 20, 2023 at 1:08
2
$\begingroup$

When emitting textual assembly code, backpatching is not strictly necessary, as long as you can predict what the label of a destination is going to be even if that destination is in the future.

There are different ways to make that happen, such as numbering your basic blocks, or doing code generation from your AST or directly in the parser (as done in Compiler design in C by Allen Holub).

$\endgroup$
1
$\begingroup$

I realize that Java bytecode uses (absolute/relative) address offset instead of (symbolic) labels in its jumping instructions such as goto. Then I know that backpatching is indeed useful during intermediate code generation. (javac uses backpatching.)

$\endgroup$
0
$\begingroup$

One thing I do during compilers I've written is backpatching for recursive closures (in ML syntax):

let c = 333 in
let rec f1 x = f2 (x - c)
    and f2 x = f1 (x - c)
in
  f1 3

This compiles down into something like:

f1 = make_closure(c, f2 <-- f2 doesn't exist yet, so this is a placeholder)
f2 = make_closure(c, f1)
backpatch(f1, f2)

Since the functions call each other, you have to delay when you fill in the closure struct, so you emit placeholders and backpatch later.

$\endgroup$
0
$\begingroup$

I don't think you'd ever have to backpatch a control flow address in intermediate code, where you'd at best have abstract labels. One of the reasons we have intermediate code is not to have to do irrelevant low-level things like that in the compiler.

However, we can generalize. Intermediate code may be processed such that various calculated attributes can flow in any direction among the nodes of the program. When they flow in a backwards direction, then that is backpatching.

In a tree/DAG representation of a program, there can be attributes that flow right to left.

For instance, classic example: Pascal-style declarations: VAR a, b, c : INTEGER. We might parse this roughly from left to right, seeing the declared a, b and c identifiers first. Then, the type attribute has to flow backwards from the INTEGER type to those nodes. That's a sort of backpatching.

Or C structures:

struct node {
  struct node *left, *right;
};

When struct node appears, it has to be introduced as an incomplete type node. Then when the definition is parsed, the type node is backpatched with information about the member types, and flipped to completed state.

When we divide intermediate code into basic blocks, something like batchpatching can take place. Say that we want the basic blocks to be objects which have direct references to other basic blocks (like the ones they jump to). For that, we must resolve the labels. We can do two passes whereby we build up, say, a hash which maps labels to basic blocks, and associates basic blocks with lists of adjacent labels. Then we replace those adjacent labels with blocks references from the hash.

$\endgroup$
-1
$\begingroup$

The CPU wants an actual address.

$\endgroup$
1
  • $\begingroup$ Thanks. But why should we generate them during intermediate code generation? In my understanding, it is the assembler that does this job after a kind of assembly code is generated. $\endgroup$
    – hengxin
    Commented May 18, 2023 at 6:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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