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

[Benoit Boissinot]

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