Register Scavenging
In Compiler backends, in particular LLVM, Register Scavenging is a last resort mechanism used during the final stages of code generation. It's job is to find a free physical register to perform a temporary task, typically when the compiler has already finished register allocation and suddenly realizes that it needs a scratch register to fix up an instruction.
Common use-case - Eliminating Frame indices
By the time the compiler reaches the function Prolog/Epilog Insertion phase, the Register Allocator has already finished assigning all virtual registers with actual physical ones.
bb.0.entry:
%0:gpr = COPY %a0
%1:gpr = COPY %a1
%2:gpr = ADDW %0, %1
%3:gpr = MULW %2, %1
%a0 = COPY %3
RET 0
%0, %1, %2, %3 are virtual registers and %a0, %a1 are incoming argument registers (physical). After Register Allocation, virtual registers are mapped to physical registers.
bb.0.entry:
mv t0, a0
addw t0, t0, a1
mulw t0, t0, a1
mv a0, t0
ret
If you would like to know more about this you could check out (Register Allocation)[https://en.wikipedia.org/wiki/Register_allocation]
Back to main issue. Eliminating Frame indices is a late backend lowering phase in LLVM where abstract stack references are replaces with concrete addressing modes (base register + offset).
What is a Frame Index
During early Machine IR, LLVM does not yet know the final stack layout. So Instead it uses a symbolic placeholder
fi#0 = -8(sp)
f1#1 = -16(sp)
These are not real addresses, they represent an abstract reference to a stack object before final offset assignment .
bb.0:
%0:gpr = LW #fi#0 0(sp)
ADDW %0, %0, %1
SW %0, fi#1, 0(sp)
As you notice, fi#0 and fi#1 are FrameIndex operands which are abstract references into the stack frame. And you might ask, why do they even exist? Well LLVM delays real stack addressing because the stack layout if not finalized early because spills may still occur later and alignment constraints are not fully known.
So Elimination involves replaces the FRAME_INDEX n with (base register) + (offset). Now the issue occurs when An Instruction needs to load from a stack offset that is too large for a single instruction.
For example, on RISC-V. The immediate offset of a load/store is limited to 12-bit signed, so a naive lowering like
lw to, 4096(sp) is illegal because the limit of a signed 12 bit integer is 2074. the compiler must instead synthesize the address in multiple steps:
lui t1, %hi(4096)
add t1, t1, sp
lw t0, %lo(4096)(t1)
`` ` Now the physical constraint appears. This sequence requires a temporary physical register (t1). The problem is at this stage of the pipeline, register allocation is already finished, In principle, every register is either, actively alive, reserved for ABI constraints or already used in surrounding instructions. So LLVM may not have an immediately available scratch register.
This is where register scavenging is triggered. It works by inspecting local liveness information around the instruction being emitted and selecting a candidate register that can be safely reused. If a free register exits(typically caller-saved registers like t0-t1 or a0-a7), LLVM will temporarily use it as the scratch register for address computation.
If no register is free, scavenging escalates to a spill-based strategy. It selects a live register (a register whose current value is still needed in the future along some execution path), spill it to a stack slot, then it proceeds to use that register as the temporary register. After the address calculation sequence it restores it.
This is not part of the original instruction selection or register allocation phase. It is injected very late, during final machine instruction emission, precisely because it depends on the final encoding constraints and actual register pressure at the emission point.