[LLVMdev] convert LLVM IR to another IR without SSA

[John Criswell]

Dear Xiangyang,

There is an LLVM pass called reg2mem which does what Diego suggests.  If 
you're not worried about efficiency, that might work for you.

If you need to do an efficient conversion of code from SSA form to 
non-SSA form, then you need to read Efficiently Computing Single Static 
Assignment Form and the Control Dependence Graph by Ron Cytron, Jeane 
Ferrante, et. al. (I may have gotten the title or authors slightly wrong 
as I'm recalling this from memory).

Anyway, that paper describes how to generate code from SSA form.  In 
essence, you need to do what register allocation does: figure out which 
SSA values in the same def-use chain can live in the same variable 
(because they don't conflict) and which SSA values must be assigned to 
different variables (because they are alive at the same time).  If you 
read the above paper, it should become clear.

Regards,

John Criswell


On 4/24/15 4:55 PM, Xiangyang Guo wrote:
> Hi, Diego,
>
> Thanks for your quick reply. Inserting a copy instruction may not work 
> here because I have a limitation of virtual register number. I need to 
> assign registers with ssa form to registers without ssa form. I will 
> look the source code you point out.
>
> Thanks
>
> Xiangyang
>
> On Fri, Apr 24, 2015 at 4:19 PM, Diego Novillo <dnovillo at google.com 
> <mailto:dnovillo at google.com>> wrote:
>
>
>
>     On Fri, Apr 24, 2015 at 3:17 PM, Xiangyang Guo <xguo6 at ncsu.edu
>     <mailto:xguo6 at ncsu.edu>> wrote:
>
>         Hi,
>
>         I want to convert LLVM IR to another type of IR, which has no
>         SSA form. So the most important thing I need to handle is Phi
>         node and register allocation because another type of IR has a
>         limitation of virtual register number. The first thing I can
>         think about is to learn how LLVM Backend works because LLVM
>         Backend handles these things. But I'm not familiar with
>         Backend. After reading some source code and online tutorials,
>         I think a Backend is too much for my purpose. I really
>         appreciate that if someone can give me hints.
>
>
>     The easiest way to think about PHI nodes is to consider them
>     copies on CFG edges.  If you do the naive translation of inserting
>     a copy instruction on the corresponding edge for each PHI
>     argument, you'll get a rough approximation for the corresponding
>     normal form.
>
>     This is, of course, very inefficient, but it's the main idea.
>
>     If you can look at GCC's source code, take a look at the algorithm
>     in file gcc/tree-outof-ssa.c.  That implements an SSA->Normal
>     transformation. I'm not really sure where in the LLVM's backend
>     this is done.
>
>
>     Diego.
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


-- 
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150424/c90d9894/attachment.html>