[LLVMdev] PHI nodes in machine code

[Misha Brukman]

On Thu, Jul 08, 2004 at 11:12:58AM -0500, Vikram Adve wrote:
> PHI nodes within machine code were originally used by the Sparc
> back-end but they turned out not to be necessary.

Actually, they are currently used in non-SparcV9 backends (see below).

> Instead, LLVM phis are lowered to copy instructions in the machine
> code (I believe this happens just after instruction selection).  

After instruction selection, code generators do not consult LLVM code,
so they cannot lower from LLVM phis anymore (plus, there could be more
Machine Basic Blocks than LLVM basic blocks, so there would be a need
for more copies than the LLVM PHI node specifies.

For example, to implement the 'select' instruction, it is necessary to
move one of two values into a register, or similarly when we want to
evaluate "r = a cond b".  Since the machine code is in SSA, we need to
use the Machine code PHI nodes to specify this to the target-independent
register allocator so that it can coallesce registers appropriately, if
possible.

The SparcV9 backend does not implement the 'select' instruction
directly, it is lowered by the LowerSelect pass before V9 instruction
selector.  Furthermore, V9 has a conditional move instruction which
some other architectures lack, so they need the MachineCode PHI nodes to
work with the target-independent register allocator.

> As far as I know, the machine PHI nodes are not used by the x86
> back-end and you shouldn't need them if you insert the right copies.

The x86 currently uses PHI nodes because it uses the target-independent
register allocator.  In contrast, the V9 backend inserts copies
manually, either via the "PreSelection" pass which it uses or in the
instruction selector itself, as I understand it.

-- 
Misha Brukman :: http://misha.brukman.net :: http://llvm.cs.uiuc.edu