Having worked on SSA register allocators in the past I have to say that SSA is actually a good fit for register allocation. However LLVM IR is indeed not. You don't have any target instructions or register classed/constraints. It wouldn't make much sense to designate registers to llvm IR values nor is there a way to express that in IR. llvm has the machine instruction (MI) representation for that. - Matthias> On Jun 17, 2015, at 5:37 AM, David Chisnall <David.Chisnall at cl.cam.ac.uk> wrote: > > On 15 Jun 2015, at 17:21, Kartik Ramkrishnan <kartikram3 at gmail.com> wrote: >> >> Thanks. I will also work on doing an SSA register allocation that returns SSA form (IR), since it is not yet implemented. > > It’s not implemented because it doesn’t really make sense as a concept. Register allocation is all about making use of a finite set of registers, spilling values to memory if they don’t fit. In SSA form, you have an infinite number of registers and (more importantly) you can only assign to each register once, so there is no way of spilling from a register and then using that register for something else. > > To implement register allocation in LLVM IR, you would need IR not to be SSA, and then it wouldn’t be LLVM IR. > > David >
On 17 June 2015 at 18:05, Matthias Braun <mbraun at apple.com> wrote:> Having worked on SSA register allocators in the past I have to say that SSA is actually a good fit for register allocation. However LLVM IR is indeed not. You don't have any target instructions or register classed/constraints. It wouldn't make much sense to designate registers to llvm IR values nor is there a way to express that in IR. llvm has the machine instruction (MI) representation for that.If I got it right, the intention here is to do simulations in IR. I'm assuming this is some form of cost function that instead of executing, would try to predict what would happen if it did run, without running. For that, doing some form of register allocation in IR can actually be beneficial from the register pressure point of view. You could even do that in a generic way by just passing the ABI register allocation first (what we do during lowering/legalization) and then just letting the simulator know how many GPRs there are, and the simulator can then estimate register pressure in basic blocks or functions by using a poor-man's version of liveness analysis on the remaining SSA registers in the sub-graph. While this would be an interesting project, I can't see this being an integral part of the LLVM codebase, as it would mess up the IR beyond recognition by current back-ends. cheers, --renato
Matthias and David, Thanks for the insight into the problem at hand :) Yes, generally, we would do the reg alloc on MI because it has meaning on an actual architecture we specified. For the project I'm working on, I'm *intentionally* not using MI, as I need to find out whether it is possible to evaluate code on different architectures, using IR simulations. Since it is not possible to return SSA form after doing reg-alloc on the IR, I'll be satisfied with a non-SSA IR, or if you will, NS-IR. This won't be LLVM IR but I can modify my IR simulator and use it nonetheless. Thanks, Kartik. On Wed, Jun 17, 2015 at 12:05 PM, Matthias Braun <mbraun at apple.com> wrote:> Having worked on SSA register allocators in the past I have to say that > SSA is actually a good fit for register allocation. However LLVM IR is > indeed not. You don't have any target instructions or register > classed/constraints. It wouldn't make much sense to designate registers to > llvm IR values nor is there a way to express that in IR. llvm has the > machine instruction (MI) representation for that. > > - Matthias > > > On Jun 17, 2015, at 5:37 AM, David Chisnall <David.Chisnall at cl.cam.ac.uk> > wrote: > > > > On 15 Jun 2015, at 17:21, Kartik Ramkrishnan <kartikram3 at gmail.com> > wrote: > >> > >> Thanks. I will also work on doing an SSA register allocation that > returns SSA form (IR), since it is not yet implemented. > > > > It’s not implemented because it doesn’t really make sense as a concept. > Register allocation is all about making use of a finite set of registers, > spilling values to memory if they don’t fit. In SSA form, you have an > infinite number of registers and (more importantly) you can only assign to > each register once, so there is no way of spilling from a register and then > using that register for something else. > > > > To implement register allocation in LLVM IR, you would need IR not to be > SSA, and then it wouldn’t be LLVM IR. > > > > David > > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150617/2906d133/attachment.html>
In my simulations, I am actually running the IR, rather than only evaluating cost function. I don't want to go too much into the details currently because I am hoping to get some results and publish them :) I don't know if it will be useful for the LLVM codebase yet. If the weird IR proves to have useful application, then maybe that is possible. On Wed, Jun 17, 2015 at 2:10 PM, Renato Golin <renato.golin at linaro.org> wrote:> On 17 June 2015 at 18:05, Matthias Braun <mbraun at apple.com> wrote: > > Having worked on SSA register allocators in the past I have to say that > SSA is actually a good fit for register allocation. However LLVM IR is > indeed not. You don't have any target instructions or register > classed/constraints. It wouldn't make much sense to designate registers to > llvm IR values nor is there a way to express that in IR. llvm has the > machine instruction (MI) representation for that. > > If I got it right, the intention here is to do simulations in IR. I'm > assuming this is some form of cost function that instead of executing, > would try to predict what would happen if it did run, without running. > For that, doing some form of register allocation in IR can actually be > beneficial from the register pressure point of view. > > You could even do that in a generic way by just passing the ABI > register allocation first (what we do during lowering/legalization) > and then just letting the simulator know how many GPRs there are, and > the simulator can then estimate register pressure in basic blocks or > functions by using a poor-man's version of liveness analysis on the > remaining SSA registers in the sub-graph. > > While this would be an interesting project, I can't see this being an > integral part of the LLVM codebase, as it would mess up the IR beyond > recognition by current back-ends. > > cheers, > --renato >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150617/dd652ab9/attachment.html>