[LLVMdev] Getting rid of phi instructions?

[Jianzhou Zhao]

On Wed, Aug 31, 2011 at 4:32 PM, Michael Ilseman <michael at lunarg.com> wrote:
>>  the next tool reading the IR does not like phis when it's generating VHDL.
>
> If you're doing a conversion from LLVM IR to some other non-SSA IR
> (like the tool's), you can do the phi node removal yourself as you
> convert. Basically, every predecessor block referenced by a phi node
> will have an assignment to that variable before branching. There are
> techniques to make the resultant code more efficient, see Cytron et
> al.[1].
>
> [1] "Efficiently computing static single assignment form and the
> control dependence graph"
> http://www.eecs.umich.edu/~mahlke/583w03/reading/cytron_toplas_91.pdf

The idea in [1] does not work for all cases. There are two problems
1) consider the code
l1:
    x1 = 1
    br l2
l2 :
    x = phi [l1 x1] [l2 x2]
    x2 = x + 1
    br false l1 l3
l3 :
    print x

Because x1 and x2's liveness range are conflicting, the following
out-of-SSA is not correct.

l1:
    x1 = 1
    x = x1
    br l2
l2 :
    x2 = x + 1
    x = x2
    br false l1 l3
l3 :
    print x

Since x = x2 kills the x = x1

2) the other problem is that all phinodes need to be update atomically,
l:
  x = 1
  y = 0
  br l'
l':
 y = phi [l x] [l' x]
 x = phi [l y ] [l' y]
 br l

So, we may need more temporaries to break the interference. Here are
some work on fixing the issues

Practical improvements to the construction and destruction of static
single assignment form
  http://www.citeulike.org/user/JianzhouZhao/article/2755291
Translating out of static single assignment form
  http://www.citeulike.org/user/JianzhouZhao/article/7350004

>
> On Wed, Aug 31, 2011 at 2:06 AM, Teemu Rinta-aho
> <teemu.rinta-aho at nomadiclab.com> wrote:
>> On 30.8.2011, at 19.19, Eli Friedman wrote:
>>
>>> reg2mem won't do quite this transformation... not sure exactly what you need.
>>
>> I need to get rid of phis. This code is compiled from C++ and for some functions
>> there are no phis, but multiple call instructions. I am targeting hardware
>> in the end, and the next tool reading the IR does not like phis when it's generating VHDL.
>> My questions may be somewhat silly from the viewpoint of software compilation for a CPU.
>>
>> Thanks.
>>
>> Teemu
>> _______________________________________________
>> 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
>



-- 
Jianzhou