Why is backpatching needed during intermediate code generation? For what purposes?

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.

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:

• Edward Robertson, Code Generation and Storage Allocation for Machines with Span-Dependent Instructions.

• Thomas Szymanski, Assembling code for machines with span-dependent instructions.

StackExchange Computer Science Q#160234, answer score: 12