[llvm-dev] LLVM and strict SSA

[Natanael Ramos via llvm-dev]

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).

--

Natanael Ramos
Membro do corpo discente de Ciência da Computação pelo Instituto Federal de
Minas Gerais - Campus Formiga

[Matthias Braun via llvm-dev]

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 Developers mailing list
llvm...@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

[Quentin Colombet via llvm-dev]

On Sep 4, 2015, at 10:23 AM, Matthias Braun via llvm-dev <llvm...@lists.llvm.org> wrote:

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

On Sep 3, 2015, at 10:45 AM, Natanael Ramos via llvm-dev <llvm...@lists.llvm.org> wrote:

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.

[Natanael Ramos via llvm-dev]

Thanks for your answers.

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