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

[Cameron Zwarich]

For spilling, I plan to use the Hack-Braun generalization of the furthest-first heuristic for SSA:

http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun09cc.pdf

For coloring, there are a few different approaches you can take, e.g. dominator tree scan, puzzle-solving, or a modified graph coloring / coalescing heuristic like IRC. The best quality for the least amount of implementation effort is probably a dominator tree scan with register preferences, so I'll try that first:

http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun10cc.pdf

Cameron

On Oct 5, 2010, at 7:43 PM, Jeff Kunkel wrote:

> 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
>> 
>> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev