[LLVMdev] [LLVMDev] Phi elimination: Who does what

[Cameron Zwarich]

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