Hi:
I hope to cut all backedges of MachineFunction CFG, then topological sort MachineBasicBlocks. 1. MachineDominatorTree *domintree = new MachineDominatorTree(); domintree->runOnMachineFunction(mf); 2. Then travel mf one by one. When domintree->dominates(next,current) is true, there is a backedge from current node to next node. move this backedge form CFG. But I find A LOOP in some CFG, there is backedge from current to next, dominates function reture "FALSE". So my algorithm find Graph can not be toplogical sort. 3. how do I find all backedges of CFG??? Thanks renkun ___________________________________________________________ 好玩贺卡等你发，邮箱贺卡全新上线！ http://card.mail.cn.yahoo.com/ _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev dominatorTree.jpg (95K) Download Attachment |
2010/1/25 任坤 <[hidden email]>:
> Hi: > > I hope to cut all backedges of MachineFunction CFG, then topological sort MachineBasicBlocks. > > 1. MachineDominatorTree *domintree = new MachineDominatorTree(); > domintree->runOnMachineFunction(mf); > > 2. Then travel mf one by one. > When domintree->dominates(next,current) is true, there is a backedge from current node to next node. move this backedge form CFG. > > But I find A LOOP in some CFG, there is backedge from current to next, dominates function reture "FALSE". So my algorithm find Graph can not be > toplogical sort. > > 3. how do I find all backedges of CFG??? longer true that the target of a back-edge dominates the source. If you want back-edges, just do a depth-first search of the CFG, the back-edges are the edges going to an already processed node. If you want loop-edges (edges going to loop headers, that is more generic than back-edges), you'll need to build the loop nesting forest. Cheers, Benoit _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
Dear Benoit:
Thanks for your answer. Best Regards. Ren Kun --- 10年1月25日，周一, Benoit Boissinot <[hidden email]> 写道： > 发件人: Benoit Boissinot <[hidden email]> > 主题: Re: [LLVMdev] Find all backedges of CFG by MachineDominatorTree. please look at my jpg. > 收件人: "任坤" <[hidden email]> > 抄送: "llvm" <[hidden email]> > 日期: 2010年1月25日,周一,下午6:14 > 2010/1/25 任坤 <[hidden email]>: > > Hi: > > > > I hope to cut all backedges of MachineFunction CFG, > then topological sort MachineBasicBlocks. > > > > 1. MachineDominatorTree *domintree = new > MachineDominatorTree(); > > domintree->runOnMachineFunction(mf); > > > > 2. Then travel mf one by one. > > When > domintree->dominates(next,current) is true, there is a > backedge from current node to next node. move this backedge > form CFG. > > > > But I find A LOOP in some CFG, there > is backedge from current to next, dominates function reture > "FALSE". So my algorithm find Graph can not be > > toplogical sort. > > > > 3. how do I find all backedges of CFG??? > > For non-reducible graphs (as is the case for your example), > it is no > longer true that the target of a back-edge dominates the > source. > > If you want back-edges, just do a depth-first search of the > CFG, the > back-edges are the edges going to an already processed > node. If you > want loop-edges (edges going to loop headers, that is more > generic > than back-edges), you'll need to build the loop nesting > forest. > > Cheers, > > Benoit > ___________________________________________________________ 好玩贺卡等你发，邮箱贺卡全新上线！ http://card.mail.cn.yahoo.com/ _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
In reply to this post by 任坤
Hi, Dear Boissinot:
1. When I have irreducible CFG, I travel its nodes by DFS. search backedge for every node. After I finish one node, push it into a stack. [0, 1, 2, M] <---push. [0, 1, 2, M,...N] <---push. When resolving node M, find a edge from node N to node M, N is not in stack(M < N), It is a backedge. N is in stack(M > N), It is NOT a backedge. I treat these backedges as loop-edges. M is Loop header node. If I cut these edges from CFG, CFG can be topological sort. Am I right??? --- 10年1月26日，周二, Benoit Boissinot <[hidden email]> 写道： > 发件人: Benoit Boissinot <[hidden email]> > 主题: Re: [LLVMdev] Find all backedges of CFG by MachineDominatorTree. please look at my jpg. > 收件人: "任坤" <[hidden email]> > 日期: 2010年1月26日,周二,下午3:12 > On Tue, Jan 26, 2010 at 01:31:53PM > +0800, 浠诲潳 wrote: > > Hi, Dear Boissinot: > > > > If a graph(CFG) is irreducible, how to find every loop > headers of CFG? > > > > If I have a simple algorithm to find them, I think it > is easy to use > > depth-first search to find all loop-edges. > > Since there are several definition of loops, the simplest > way is to > choose: backedge target are loop-headers. > > Backedge is then defined by a DFS of the CFG (you'll find > that in most > textbooks). > http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm > > regards, > > Benoit > > -- > :wq > ___________________________________________________________ 好玩贺卡等你发，邮箱贺卡全新上线！ http://card.mail.cn.yahoo.com/ _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
On Tue, Jan 26, 2010 at 10:04:16PM +0800, 任坤 wrote:
> Hi, Dear Boissinot: > > 1. When I have irreducible CFG, I travel its nodes by DFS. > search backedge for every node. After I finish one node, > push it into a stack. > [0, 1, 2, M] <---push. > [0, 1, 2, M,...N] <---push. > > When resolving node M, find a edge from node N to node M, > N is not in stack(M < N), It is a backedge. > N is in stack(M > N), It is NOT a backedge. > > I treat these backedges as loop-edges. M is Loop header node. > If I cut these edges from CFG, CFG can be topological sort. > > Am I right??? yes, exactly. regards, Benoit -- :wq _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
Free forum by Nabble | Edit this page |