Hello to all LLVM developers. I'm developing a register allocator using LLVM, my allocator has a local search phase: given a solution (assignment of virtual registers to physical registers or memory) generated in the first phase of the algorithm, some movements are applied to this solution in order to find a better solution. To apply such movements, I need to unassign a virtual register from a physical register and one from the memory, and swap those two. To unassign from a physical register, the method *unassign* from the *LiveRegMatrix* class can be used. But, in the other hand, the class *InlineSpiller* doesn't provide a similar method, like *unspill*. So I thought, instead of applying the spill directly during the first phase of the algorithm, I would store the virtual registers candidates to spill in an auxiliary structure. So that when it was decided to apply spill at some virtual register, it would be added to the structure and that would be ignored in the next iteration of the algorithm. After local search phase is completed, the spill would be applied in fact to these virtual registers contained in auxiliary structure. Using this structure I can move make the switch between virtual registers assigned to physical registers and virtual registers candidates to go to the memory smoothly. So my question is this: Following this approach of "Lazy Spill", leads to any side effects? Far as I know applying spill to a virtual register leads to insert instructions of load/store in the code, which may make it necessary to run the Liveness Analysis again, changing the structure of Live Intervals. That would be a problem, but looking at the source code of *InlineSpiller* class, I see no invocation of Liveness Analysis after applying spill. Att -- 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/20150901/a049cee7/attachment.html>
Hi Natanael,> On Sep 1, 2015, at 11:38 AM, Natanael Ramos via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > Hello to all LLVM developers. > > I'm developing a register allocator using LLVM, my allocator has a local search phase: given a solution (assignment of virtual registers to physical registers or memory) generated in the first phase of the algorithm, some movements are applied to this solution in order to find a better solution. To apply such movements, I need to unassign a virtual register from a physical register and one from the memory, and swap those two. To unassign from a physical register, the method unassign from the LiveRegMatrix class can be used. But, in the other hand, the class InlineSpiller doesn't provide a similar method, like unspill. > > So I thought, instead of applying the spill directly during the first phase of the algorithm, I would store the virtual registers candidates to spill in an auxiliary structure. So that when it was decided to apply spill at some virtual register, it would be added to the structure and that would be ignored in the next iteration of the algorithm. After local search phase is completed, the spill would be applied in fact to these virtual registers contained in auxiliary structure. Using this structure I can move make the switch between virtual registers assigned to physical registers and virtual registers candidates to go to the memory smoothly. > So my question is this: Following this approach of "Lazy Spill", leads to any side effects?You need to model the live-range splitting involved by the insertion of load and store instructions. I want to expose such interface in the spiller for this kind of lazy spilling (look for the memory state I added recently in the greedy allocator), but I do not know when I will get to it. This is way down in my todolist.> Far as I know applying spill to a virtual register leads to insert instructions of load/store in the code, which may make it necessary to run the Liveness Analysis again, changing the structure of Live Intervals. That would be a problem, but looking at the source code of InlineSpiller class, I see no invocation of Liveness Analysis after applying spill.The InlineSpiller does update the liveness analysis, look for method on the LiveIntervals object instead the InlineSpiller. Cheers, -Quentin> > Att > > > -- > 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/20150901/6d469665/attachment.html>
Thank you for your help Quentin. I'm trying to avoid to have to work with Live Range Splitting. This allocator is for my Work of completion of undergraduate course in Computer Science, so I don't have enough time to work with advanced techniques, like Splitting, because it will demand a little bit more of research. But can be done in future works. For now, I will have to think in another methodology of local search. Thank you for the hint, I will look at the LiveIntervals. Att Em 01/09/2015 17:04, "Quentin Colombet" <qcolombet at apple.com> escreveu: Hi Natanael, On Sep 1, 2015, at 11:38 AM, Natanael Ramos via llvm-dev < llvm-dev at lists.llvm.org> wrote: Hello to all LLVM developers. I'm developing a register allocator using LLVM, my allocator has a local search phase: given a solution (assignment of virtual registers to physical registers or memory) generated in the first phase of the algorithm, some movements are applied to this solution in order to find a better solution. To apply such movements, I need to unassign a virtual register from a physical register and one from the memory, and swap those two. To unassign from a physical register, the method *unassign* from the *LiveRegMatrix* class can be used. But, in the other hand, the class *InlineSpiller* doesn't provide a similar method, like *unspill*. So I thought, instead of applying the spill directly during the first phase of the algorithm, I would store the virtual registers candidates to spill in an auxiliary structure. So that when it was decided to apply spill at some virtual register, it would be added to the structure and that would be ignored in the next iteration of the algorithm. After local search phase is completed, the spill would be applied in fact to these virtual registers contained in auxiliary structure. Using this structure I can move make the switch between virtual registers assigned to physical registers and virtual registers candidates to go to the memory smoothly. So my question is this: Following this approach of "Lazy Spill", leads to any side effects? You need to model the live-range splitting involved by the insertion of load and store instructions. I want to expose such interface in the spiller for this kind of lazy spilling (look for the memory state I added recently in the greedy allocator), but I do not know when I will get to it. This is way down in my todolist. Far as I know applying spill to a virtual register leads to insert instructions of load/store in the code, which may make it necessary to run the Liveness Analysis again, changing the structure of Live Intervals. That would be a problem, but looking at the source code of *InlineSpiller* class, I see no invocation of Liveness Analysis after applying spill. The InlineSpiller does update the liveness analysis, look for method on the LiveIntervals object instead the InlineSpiller. Cheers, -Quentin Att -- 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/20150901/244c7a6d/attachment.html>