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 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150903/eebb2229/attachment.html>
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 <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 > > _______________________________________________ > 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/c01f22e1/attachment.html>
> 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 <mailto: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 <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 <mailto: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/9a7eb290/attachment.html>