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

[Benoit Boissinot]

On Tue, Mar 9, 2010 at 9:14 AM, renkun <hbrenkun at yahoo.cn> wrote:
> Thank you, Nick.
> Yes, I have add getAnalysisUsage.
> As I know, some CFG is irreducible.
> At this time, Dominator Tree can not find
> some backedge. Is it means some MachineLoop is
> not be found?
> dominatorTree.jpg is a previous exmaple.

Just remember that for irreducible graphs, there are several
definitions of loops (and thus several definitions of loopedges).
Back-edge (edge pointer to an ancestor during a DFS walk) are
loop-edge, but the converse isn't necessarily true.

And, depending on the DFS, MBB173->MBB172 is not necessarely a
backedge (visiting MBB167 before MBB173 will indeed mark
MBB173->MBB172 as a tree-edge, not as a back-edge).
For loop-edge, you might instead find MBB170->MBB172, or
MBB180->MBB170 plus MBB174->MBB170, or some combinations of those
(MBB170, MBB172, MBB173 are all undominated, any subset from these
three nodes can be choosen as headers).

Cheers,

Benoit