llvm dev - Dec 2008 - [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

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.

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

> How do I find out if a branch instruction belongs to an if-else or a 
> loop i.e it is a backedge.
Have you looked at LoopInfo?

-Tanya
>
> Thanks,
> Bhavani
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

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
>

bhavani krishnan wrote:
> Hi,
>
> How do I find out if a branch instruction belongs to an if-else or a loop
i.e it is a backedge.
>   
Are you wanting a way to tell if an edge is a backedge so that you know 
whether or not it's part of a loop, or are you actually looking for 
loops *and* if/then/else constructs?

-- John T.
> Thanks,
> Bhavani
>
>
>       
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>