llvm dev - Oct 2010 - [LLVMdev] [LLVMDev] Phi elimination: Who does what

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

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

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
>
>