llvm dev - Jan 2010 - [LLVMdev] Find all backedges of CFG by MachineDominatorTree. please look at my jpg.

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 <bboissin+llvm at gmail.com> 写道：
> 发件人: Benoit Boissinot <bboissin+llvm at gmail.com>
> 主题: Re: [LLVMdev] Find all backedges of CFG by MachineDominatorTree. 
please look at my jpg.
> 收件人: "任坤" <hbrenkun at yahoo.cn>
> 日期: 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/

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