[LLVMdev] Identifying backedges

[Nick Lewycky]

Villmow, Micah wrote:
> Bhavani, 
>  A simple way that I'm not sure is 100% guaranteed to work is if the
> branch is to an earlier or later basic block.

This is either the right approach or a dangerously terrible idea, 
depending on what exactly you meant.

The order that BasicBlocks are iterated over in a given Function is 
undefined. They happen to be produced by llvm-gcc in order and because 
LLVM passes don't go out of their way to scramble them, they will 
generally end up in order. But the only guarantee about the ordering is 
that the first one is the function entry block.

If you meant order as in, ordered by a dominance comparison function, 
then you had the right answer. Assuming your pass depends on no other 
analyses, the cheapest way to find a backedge is to depend upon the 
DominatorTree pass, and ask it. If the branch target (or either branch 
target for conditional branches) dominate the block containing the 
branch, then it's a backedge.

If you happen to depend on LoopInfo already, you can ask it whether the 
BB that contains the branch is part of a loop or not.

Nick

> Micah
> 
> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu]
> On Behalf Of bhavani krishnan
> Sent: Wednesday, December 03, 2008 3:20 PM
> To: Nick Lewycky; LLVM Developers Mailing List
> Subject: [LLVMdev] Identifying backedges
> 
> Hi,
> 
> How do I find out if a branch instruction belongs to an if-else or a
> loop i.e it is a backedge.
> 
> Thanks,
> Bhavani
> 
> 
>       
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>