[LLVMdev] 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 <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/