[LLVMdev] convert LLVM IR to another IR without SSA

John Criswell jtcriswel at gmail.com
Sat Apr 25 10:11:25 PDT 2015


On 4/25/15 10:51 AM, Xiangyang Guo wrote:
> Hi, John,
>
> Thanks for your valuable information. reg2mem will introduce too many 
> load-store operation and the number of registers is huge. It seems the 
> paper you mentioned is what I need.

Yes, you'll either need to do what is in the paper or do what the code 
generator does (as Diego suggested).

If you look at the paper, you can probably skip to the part in the end 
in which they discuss converting code out of SSA form.

Regards,

John Criswell

>
> Regards
>
> Xiangyang
>
> On Fri, Apr 24, 2015 at 7:43 PM, John Criswell <jtcriswel at gmail.com 
> <mailto:jtcriswel at gmail.com>> wrote:
>
>     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  <mailto: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
>
>


-- 
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/20150425/bf229d74/attachment.html>


More information about the llvm-dev mailing list