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> wrote:> > > On Fri, Apr 24, 2015 at 3:17 PM, Xiangyang Guo <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. >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150424/0bfc3bcd/attachment.html>
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>
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. Regards Xiangyang On Fri, Apr 24, 2015 at 7:43 PM, John Criswell <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> > wrote: > >> >> >> On Fri, Apr 24, 2015 at 3:17 PM, Xiangyang Guo <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 listLLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.eduhttp://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > > -- > John Criswell > Assistant Professor > Department of Computer Science, University of Rochesterhttp://www.cs.rochester.edu/u/criswell > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150425/26f35432/attachment.html>