LLVM and strict SSA

Hello to all LLVM Developers.

The LLVM IR is in strict SSA form (i.e. every variable is defined before it is used along every path from the entry to exit point)?
According to the documentation, currently the LLVM IR is in the SSA form, but I don’t see additional information about strict SSA form.

The strict SSA form provide opportunities of optimization in register allocation, because is proved that all interference graphs of the IR in strict SSA form are chordal and for those, there are polynomial algorithms for the graph coloring (http://web.cs.ucla.edu/~palsberg/paper/aplas05.pdf).

LLVM has multiple intermediate representations. Before register allocation llvm IR is translated into the representation most often called machine IR (MIR) which is in strict SSA form for some passes but is then lowered to non SSA form in the PHIElimination and TwoAddressInstruction passes.

  • Matthias

LLVM has multiple intermediate representations. Before register allocation llvm IR is translated into the representation most often called machine IR (MIR) which is in strict SSA form for some passes but is then lowered to non SSA form in the PHIElimination and TwoAddressInstruction passes.

  • Matthias

Hello to all LLVM Developers.

The LLVM IR is in strict SSA form (i.e. every variable is defined before it is used along every path from the entry to exit point)?
According to the documentation, currently the LLVM IR is in the SSA form, but I don’t see additional information about strict SSA form.

The strict SSA form provide opportunities of optimization in register allocation, because is proved that all interference graphs of the IR in strict SSA form are chordal and for those, there are polynomial algorithms for the graph coloring (http://web.cs.ucla.edu/~palsberg/paper/aplas05.pdf).

This is true only when you set aside the hardware constraints IIRC.
Anyway, the hard part in the allocator is spilling and coalescing, not coloring.

Like Matthias said, for reg alloc, we are not in strict SSA anymore.

Q.

Thanks for your answers.

Yes, coloring can be done in polinomial time, but spilling and Coalescing are still NP.