Find all backedges of CFG by MachineDominatorTree. please look at my jpg.

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Find all backedges of CFG by MachineDominatorTree. please look at my jpg.

任坤
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
Reply | Threaded
Open this post in threaded view
|

Re: Find all backedges of CFG by MachineDominatorTree. please look at my jpg.

Benoit Boissinot-4
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


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Find all backedges of CFG by MachineDominatorTree. please look at my jpg.

任坤
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
Reply | Threaded
Open this post in threaded view
|

Re: Find all backedges of CFG by MachineDominatorTree. please look at my jpg.

任坤
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
Reply | Threaded
Open this post in threaded view
|

Re: Find all backedges of CFG by MachineDominatorTree. please look at my jpg.

Benoit Boissinot-4
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