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

[Jeff Kunkel]

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