llvm dev - Jan 2010 - [LLVMdev] 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/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dominatorTree.jpg
Type: image/jpeg
Size: 71233 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100125/4e2bba87/attachment.jpg>

2010/1/25 任坤 <hbrenkun at yahoo.cn>:
> 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

Dear Benoit:

  Thanks for your answer.

Best Regards.

Ren Kun

--- 10年1月25日，周一, 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>
> 抄送: "llvm" <llvmdev at cs.uiuc.edu>
> 日期: 2010年1月25日,周一,下午6:14
> 2010/1/25 任坤 <hbrenkun at yahoo.cn>:
> > 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/