[llvm-dev] LLVM and strict SSA

[Natanael Ramos via llvm-dev]

Thanks for your answers.

Yes, coloring can be done in polinomial time, but spilling and Coalescing
are still NP.
Em 04/09/2015 2:35 PM, "Quentin Colombet" <qcolombet at apple.com> escreveu:

>
> On Sep 4, 2015, at 10:23 AM, Matthias Braun via llvm-dev <
> llvm-dev at 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-dev at 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
> Membro do corpo discente de Ciência da Computação pelo Instituto Federal
> de
> Minas Gerais - Campus Formiga
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150904/0b9c5cb5/attachment.html>