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

Benoit Boissinot bboissin+llvm at gmail.com
Tue Jan 26 06:13:47 PST 2010

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.




More information about the llvm-dev mailing list