Aye, between all current register allocators the 'AU.addRequiredID(PHIEliminationID);' will cause phi's to be eliminated to copies, but this misses the point of my question. What I am asking, is how does stack know that the value of the variable which the resulting value of the phi is currently allocated at. For instance take the instruction: Machine Basic Block (mbb) 12 reg16666 = phi reg17777 (mbb 10), reg18888 (mbb 11). Let reg17777 memory location be at the sp+x, and let reg18888 memory location be at sp+y. What memory location will reg16666 be pointing at? And who tells the stack that it needs to somehow make sure that reg16666 contains the value of 17777 when machine basic block 10 branches to 12? My current register allocator (I am working on) waits until it has finished local machine basic block coloring before coordinating between the machine basic blocks. The phi elimination can be done effectively at this point. Thus, instead of have the hassle of coalescing, I have the hassle of phi elimination, which quite honestly, is quite simple as long as I have my i's dotted and t's crossed. Hence, my question. The trouble I foresee is that the reg17777 and reg18888 can both be on the stack. Then, at the end of the mbb 11, reg18888 must be stored not only in it's own slot, but also in reg16666's slot. I am wondering, do I need to communicate this information somehow? Thanks, Jeff Kunkel On Tue, Oct 5, 2010 at 4:35 PM, Cameron Zwarich <zwarich at apple.com> wrote:> At the moment, phi elimination happens before register allocation, so there can be no phis between memory locations. > > Cameron > > On Oct 5, 2010, at 4:19 PM, Jeff Kunkel wrote: > >> When doing phi elimination, does one have to communicate with the >> stack space at all? The problem I see is two distinctly different >> registers may have two distinctly different stack spaces. When these >> registers are combined in a phi, the values the registers point to >> needs to be moved, combined, or otherwise taken care of. I understand >> this is the job of the stack space colorer, but when doing phi >> elimination, does one need to tell the stack space colorer that the >> phi did exist? >> >> Thanks, >> Jeff Kunkel >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >
After studying the PhiElimination class, I believe it is safe to say that the stack handles phi's correctly. Thanks, Jeff Kunkel On Tue, Oct 5, 2010 at 6:02 PM, Jeff Kunkel <jdkunk3 at gmail.com> wrote:> Aye, between all current register allocators the > 'AU.addRequiredID(PHIEliminationID);' will cause phi's to be > eliminated to copies, but this misses the point of my question. > > What I am asking, is how does stack know that the value of the > variable which the resulting value of the phi is currently allocated > at. For instance take the instruction: > > Machine Basic Block (mbb) 12 > reg16666 = phi reg17777 (mbb 10), reg18888 (mbb 11). > > Let reg17777 memory location be at the sp+x, and let reg18888 memory > location be at sp+y. What memory location will reg16666 be pointing > at? And who tells the stack that it needs to somehow make sure that > reg16666 contains the value of 17777 when machine basic block 10 > branches to 12? > > My current register allocator (I am working on) waits until it has > finished local machine basic block coloring before coordinating > between the machine basic blocks. The phi elimination can be done > effectively at this point. Thus, instead of have the hassle of > coalescing, I have the hassle of phi elimination, which quite > honestly, is quite simple as long as I have my i's dotted and t's > crossed. Hence, my question. > > The trouble I foresee is that the reg17777 and reg18888 can both be on > the stack. Then, at the end of the mbb 11, reg18888 must be stored not > only in it's own slot, but also in reg16666's slot. I am wondering, do > I need to communicate this information somehow? > > Thanks, > Jeff Kunkel > > > On Tue, Oct 5, 2010 at 4:35 PM, Cameron Zwarich <zwarich at apple.com> wrote: >> At the moment, phi elimination happens before register allocation, so there can be no phis between memory locations. >> >> Cameron >> >> On Oct 5, 2010, at 4:19 PM, Jeff Kunkel wrote: >> >>> When doing phi elimination, does one have to communicate with the >>> stack space at all? The problem I see is two distinctly different >>> registers may have two distinctly different stack spaces. When these >>> registers are combined in a phi, the values the registers point to >>> needs to be moved, combined, or otherwise taken care of. I understand >>> this is the job of the stack space colorer, but when doing phi >>> elimination, does one need to tell the stack space colorer that the >>> phi did exist? >>> >>> Thanks, >>> Jeff Kunkel >>> _______________________________________________ >>> LLVM Developers mailing list >>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> >> >
There is nothing that currently handles this properly, as far as I know. If you have a phi c = phi(a, b) where a, b and c are all assigned distinct stack slots, then copies must be inserted in the predecessor. If registers have already been allocated, then this memory copy might require a temporary register (unless you're on an architecture like x86 that lets you do memory-to-memory copies without using a register). In general, each phi block in register allocated code lowers to parallel copies on incoming edges that need to be sequentialized. This is a somewhat different problem than normal phi elimination before register allocation. I am also writing an SSA-based register allocator for LLVM; perhaps we can share some code in common passes. Cameron On Oct 5, 2010, at 6:02 PM, Jeff Kunkel wrote:> Aye, between all current register allocators the > 'AU.addRequiredID(PHIEliminationID);' will cause phi's to be > eliminated to copies, but this misses the point of my question. > > What I am asking, is how does stack know that the value of the > variable which the resulting value of the phi is currently allocated > at. For instance take the instruction: > > Machine Basic Block (mbb) 12 > reg16666 = phi reg17777 (mbb 10), reg18888 (mbb 11). > > Let reg17777 memory location be at the sp+x, and let reg18888 memory > location be at sp+y. What memory location will reg16666 be pointing > at? And who tells the stack that it needs to somehow make sure that > reg16666 contains the value of 17777 when machine basic block 10 > branches to 12? > > My current register allocator (I am working on) waits until it has > finished local machine basic block coloring before coordinating > between the machine basic blocks. The phi elimination can be done > effectively at this point. Thus, instead of have the hassle of > coalescing, I have the hassle of phi elimination, which quite > honestly, is quite simple as long as I have my i's dotted and t's > crossed. Hence, my question. > > The trouble I foresee is that the reg17777 and reg18888 can both be on > the stack. Then, at the end of the mbb 11, reg18888 must be stored not > only in it's own slot, but also in reg16666's slot. I am wondering, do > I need to communicate this information somehow? > > Thanks, > Jeff Kunkel > > > On Tue, Oct 5, 2010 at 4:35 PM, Cameron Zwarich <zwarich at apple.com> wrote: >> At the moment, phi elimination happens before register allocation, so there can be no phis between memory locations. >> >> Cameron >> >> On Oct 5, 2010, at 4:19 PM, Jeff Kunkel wrote: >> >>> When doing phi elimination, does one have to communicate with the >>> stack space at all? The problem I see is two distinctly different >>> registers may have two distinctly different stack spaces. When these >>> registers are combined in a phi, the values the registers point to >>> needs to be moved, combined, or otherwise taken care of. I understand >>> this is the job of the stack space colorer, but when doing phi >>> elimination, does one need to tell the stack space colorer that the >>> phi did exist? >>> >>> Thanks, >>> Jeff Kunkel >>> _______________________________________________ >>> LLVM Developers mailing list >>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> >> > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
The allocator you are building, is it the Hack's and Goos's polynomial time algorithm? On Tue, Oct 5, 2010 at 7:14 PM, Cameron Zwarich <zwarich at apple.com> wrote:> There is nothing that currently handles this properly, as far as I know. If you have a phi > > c = phi(a, b) > > where a, b and c are all assigned distinct stack slots, then copies must be inserted in the predecessor. If registers have already been allocated, then this memory copy might require a temporary register (unless you're on an architecture like x86 that lets you do memory-to-memory copies without using a register). > > In general, each phi block in register allocated code lowers to parallel copies on incoming edges that need to be sequentialized. This is a somewhat different problem than normal phi elimination before register allocation. > > I am also writing an SSA-based register allocator for LLVM; perhaps we can share some code in common passes. > > Cameron > > On Oct 5, 2010, at 6:02 PM, Jeff Kunkel wrote: > >> Aye, between all current register allocators the >> 'AU.addRequiredID(PHIEliminationID);' will cause phi's to be >> eliminated to copies, but this misses the point of my question. >> >> What I am asking, is how does stack know that the value of the >> variable which the resulting value of the phi is currently allocated >> at. For instance take the instruction: >> >> Machine Basic Block (mbb) 12 >> reg16666 = phi reg17777 (mbb 10), reg18888 (mbb 11). >> >> Let reg17777 memory location be at the sp+x, and let reg18888 memory >> location be at sp+y. What memory location will reg16666 be pointing >> at? And who tells the stack that it needs to somehow make sure that >> reg16666 contains the value of 17777 when machine basic block 10 >> branches to 12? >> >> My current register allocator (I am working on) waits until it has >> finished local machine basic block coloring before coordinating >> between the machine basic blocks. The phi elimination can be done >> effectively at this point. Thus, instead of have the hassle of >> coalescing, I have the hassle of phi elimination, which quite >> honestly, is quite simple as long as I have my i's dotted and t's >> crossed. Hence, my question. >> >> The trouble I foresee is that the reg17777 and reg18888 can both be on >> the stack. Then, at the end of the mbb 11, reg18888 must be stored not >> only in it's own slot, but also in reg16666's slot. I am wondering, do >> I need to communicate this information somehow? >> >> Thanks, >> Jeff Kunkel >> >> >> On Tue, Oct 5, 2010 at 4:35 PM, Cameron Zwarich <zwarich at apple.com> wrote: >>> At the moment, phi elimination happens before register allocation, so there can be no phis between memory locations. >>> >>> Cameron >>> >>> On Oct 5, 2010, at 4:19 PM, Jeff Kunkel wrote: >>> >>>> When doing phi elimination, does one have to communicate with the >>>> stack space at all? The problem I see is two distinctly different >>>> registers may have two distinctly different stack spaces. When these >>>> registers are combined in a phi, the values the registers point to >>>> needs to be moved, combined, or otherwise taken care of. I understand >>>> this is the job of the stack space colorer, but when doing phi >>>> elimination, does one need to tell the stack space colorer that the >>>> phi did exist? >>>> >>>> Thanks, >>>> Jeff Kunkel >>>> _______________________________________________ >>>> LLVM Developers mailing list >>>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >>> >>> >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >