llvm dev - Aug 2012 - [LLVMdev] How to Check whether BasicBlock resides in a conditional branch

Hello All,

I want to dertermine whether a basicblock is in a conditional branch. such as,

//============================if a > 2 // BasicBlock A
then

BasicBlock B

endif

BasicBlock C
//============================What I want to identify is BasicBlock B, which is
in a condtional
block. but C is not.
In other words, I want to distinguish BasicBlocks that  * must *  be
executed and that *may* be executed.

CFG's iterator may not help, as  LLVM IR br would be:
A:
br %cmp,  %lable.B,  %label.C

B
br C

C

both of the blocks could be operand of br instruction.

code in C *must be executed*, but B is not.


Is there any availiable API in LLVM to distinguish them?

Thanks.

Can't you do it by performing some analysis on CFG? You can traverse that
structure with BFS. And after that for all the BB you have visited more than
once, you try to find a parent that has a branch instruction as a terminator.
Additionally you ensure that there are no BB with branches as terminators on
your way. If such parent exist, you mark that there is exist a direct connection
between this parent and BB.

Anyway I think it's impossible to detect all of such BB - you have indirect
jumps, you can have a complicated branch structure with implicit flows that are
hard to analyse - like this:

a = 0; 
b = 1;
if (X == 1)
  a = 1;
if (X == 0)
  b = 0;
if (a  == 0)
  Y = 0;
if (b == 1)
  Y = 1;
// in the end  Y = X
if(X == Y)
  BasicBlock C
endif

BasicBlock D

In this example BasicBlock C is *must* executed, however it's hard to detect
that it is.

--
Yaroslav Markov
PhD student in Computer Science
Stony Brook University
________________________________________
From: llvmdev-bounces at cs.uiuc.edu [llvmdev-bounces at cs.uiuc.edu] on behalf
of Jianfei Hu [hujianfei258 at gmail.com]
Sent: Saturday, August 25, 2012 8:44 AM
To: LLVMdev at cs.uiuc.edu
Subject: [LLVMdev] How to Check whether BasicBlock resides in a conditional    
branch

Hello All,

I want to dertermine whether a basicblock is in a conditional branch. such as,

//============================if a > 2 // BasicBlock A
then

BasicBlock B

endif

BasicBlock C
//============================What I want to identify is BasicBlock B, which is
in a condtional
block. but C is not.
In other words, I want to distinguish BasicBlocks that  * must *  be
executed and that *may* be executed.

CFG's iterator may not help, as  LLVM IR br would be:
A:
br %cmp,  %lable.B,  %label.C

B
br C

C

both of the blocks could be operand of br instruction.

code in C *must be executed*, but B is not.


Is there any availiable API in LLVM to distinguish them?

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

In the general sense you may get some help by looking at the control dependence
graph.
- dibyendu

----- Original Message -----
From: Jianfei Hu [mailto:hujianfei258 at gmail.com]
Sent: Saturday, August 25, 2012 07:43 AM
To: LLVMdev at cs.uiuc.edu <LLVMdev at cs.uiuc.edu>
Subject: [LLVMdev] How to Check whether BasicBlock resides in a conditional
branch

Hello All,

I want to dertermine whether a basicblock is in a conditional branch. such as,

//============================if a > 2 // BasicBlock A
then

BasicBlock B

endif

BasicBlock C
//============================What I want to identify is BasicBlock B, which is
in a condtional
block. but C is not.
In other words, I want to distinguish BasicBlocks that  * must *  be
executed and that *may* be executed.

CFG's iterator may not help, as  LLVM IR br would be:
A:
br %cmp,  %lable.B,  %label.C

B
br C

C

both of the blocks could be operand of br instruction.

code in C *must be executed*, but B is not.


Is there any availiable API in LLVM to distinguish them?

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

2012/8/25 Iaroslav Markov <ymarkov at
cs.stonybrook.edu>:
> Can't you do it by performing some analysis on CFG? You can traverse
that structure with BFS. And after that for all the BB you have visited more
than once, you try to find a parent that has a branch instruction as a
terminator. Additionally you ensure that there are no BB with branches as
terminators on your way. If such parent exist, you mark
that there is exist a direct connection between this parent and BB.

What do you mean by "there are no BB with branches as terminators on
your way" ?  I remember All BB end with a terminator....
Well, I think if the basicblock only has one  predecessor block, it
also means its predecessor and iteself have direct connection.
Do you mean this?
>
> Anyway I think it's impossible to detect all of such BB - you have
indirect jumps, you can have a complicated branch structure with implicit flows
that are hard to analyse - like this:
>
> a = 0;
> b = 1;
> if (X == 1)
>   a = 1;
> if (X == 0)
>   b = 0;
> if (a  == 0)
>   Y = 0;
> if (b == 1)
>   Y = 1;
> // in the end  Y = X
> if(X == Y)
>   BasicBlock C
> endif
>
> BasicBlock D
>
> In this example BasicBlock C is *must* executed, however it's hard to
detect that it is.
Yes, the precise execution condtion may be difficut to get. I just
want rough results.

Thanks for your suggestion!
>
> --
> Yaroslav Markov
> PhD student in Computer Science
> Stony Brook University
> ________________________________________
> From: llvmdev-bounces at cs.uiuc.edu [llvmdev-bounces at cs.uiuc.edu] on
behalf of Jianfei Hu [hujianfei258 at gmail.com]
> Sent: Saturday, August 25, 2012 8:44 AM
> To: LLVMdev at cs.uiuc.edu
> Subject: [LLVMdev] How to Check whether BasicBlock resides in a conditional
branch
>
> Hello All,
>
> I want to dertermine whether a basicblock is in a conditional branch. such
as,
>
> //============================> if a > 2 // BasicBlock A
> then
>
> BasicBlock B
>
> endif
>
> BasicBlock C
> //============================> What I want to identify is BasicBlock B,
which is in a condtional
> block. but C is not.
> In other words, I want to distinguish BasicBlocks that  * must *  be
> executed and that *may* be executed.
>
> CFG's iterator may not help, as  LLVM IR br would be:
> A:
> br %cmp,  %lable.B,  %label.C
>
> B
> br C
>
> C
>
> both of the blocks could be operand of br instruction.
>
> code in C *must be executed*, but B is not.
>
>
> Is there any availiable API in LLVM to distinguish them?
>
> Thanks.
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Thanks, I may have a try.

2012/8/25 Das, Dibyendu <Dibyendu.Das at amd.com>:
> In the general sense you may get some help by looking at the control
dependence graph.
> - dibyendu
>
> ----- Original Message -----
> From: Jianfei Hu [mailto:hujianfei258 at gmail.com]
> Sent: Saturday, August 25, 2012 07:43 AM
> To: LLVMdev at cs.uiuc.edu <LLVMdev at cs.uiuc.edu>
> Subject: [LLVMdev] How to Check whether BasicBlock resides in a conditional
branch
>
> Hello All,
>
> I want to dertermine whether a basicblock is in a conditional branch. such
as,
>
> //============================> if a > 2 // BasicBlock A
> then
>
> BasicBlock B
>
> endif
>
> BasicBlock C
> //============================> What I want to identify is BasicBlock B,
which is in a condtional
> block. but C is not.
> In other words, I want to distinguish BasicBlocks that  * must *  be
> executed and that *may* be executed.
>
> CFG's iterator may not help, as  LLVM IR br would be:
> A:
> br %cmp,  %lable.B,  %label.C
>
> B
> br C
>
> C
>
> both of the blocks could be operand of br instruction.
>
> code in C *must be executed*, but B is not.
>
>
> Is there any availiable API in LLVM to distinguish them?
>
> Thanks.
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>

Hi Jianfei Hu,

the GVN pass does something like this in the logic around
GVN::propagateEquality.  If in your example it was

   if a == 2 // BasicBlock A
   then

then it replaces all occurrences of a with 2 in BasicBlock A.  For this
it needs to understand which basic blocks can only be reached via this
conditional edge "a == 2".

Ciao, Duncan.

> Hello All,
>
> I want to dertermine whether a basicblock is in a conditional branch. such
as,
>
> //============================> if a > 2 // BasicBlock A
> then
>
> BasicBlock B
>
> endif
>
> BasicBlock C
> //============================> What I want to identify is BasicBlock B,
which is in a condtional
> block. but C is not.
> In other words, I want to distinguish BasicBlocks that  * must *  be
> executed and that *may* be executed.
>
> CFG's iterator may not help, as  LLVM IR br would be:
> A:
> br %cmp,  %lable.B,  %label.C
>
> B
> br C
>
> C
>
> both of the blocks could be operand of br instruction.
>
> code in C *must be executed*, but B is not.
>
>
> Is there any availiable API in LLVM to distinguish them?
>
> Thanks.
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

GVN's algorithm for this is not complete, but a simple approximation
(it uses edge dominance).

It will not find all blocks for which the property is true, just the
ones it can easily and cheaply prove its true.
It expects iteration  and leader lookups will take care of the rest later on.

So it wouldn't give him a solution.

The set of blocks he is looking for is exactly the set the control
dependence graph will give you.
IE a node n is control dependent on a node c if node c determines
whether n is executed.

However, it's a bit more tricky than this, because of loops (and
nested loops).  Nodes can be control dependent on themselves, or
control-dependent on multiple nodes (in the case of nested loops).

As such, it's easier to talk about control dependence on the edges
that come out of the conditional.

If you do this, you get

node n is control dependent on edge (u->v) if
n postdominates v
n does not strictly postdominate u

(IE all paths from v to exit go through n, but not all paths from u to
exit go through n, thus the edge u->v is determining whether n
executes).

You could actually use this in GVN as well, but computing
post-dominance may be more expensive than the approximation +
iteration it does now.

On Sun, Aug 26, 2012 at 3:53 PM, Duncan Sands <baldrick at free.fr>
wrote:
> Hi Jianfei Hu,
>
> the GVN pass does something like this in the logic around
> GVN::propagateEquality.  If in your example it was
>
>   if a == 2 // BasicBlock A
>   then
>
> then it replaces all occurrences of a with 2 in BasicBlock A.  For this
> it needs to understand which basic blocks can only be reached via this
> conditional edge "a == 2".
>
> Ciao, Duncan.
>
>
>
>> Hello All,
>>
>> I want to dertermine whether a basicblock is in a conditional branch.
such
>> as,
>>
>> //============================>> if a > 2 // BasicBlock A
>> then
>>
>> BasicBlock B
>>
>> endif
>>
>> BasicBlock C
>> //============================>> What I want to identify is
BasicBlock B, which is in a condtional
>> block. but C is not.
>> In other words, I want to distinguish BasicBlocks that  * must *  be
>> executed and that *may* be executed.
>>
>> CFG's iterator may not help, as  LLVM IR br would be:
>> A:
>> br %cmp,  %lable.B,  %label.C
>>
>> B
>> br C
>>
>> C
>>
>> both of the blocks could be operand of br instruction.
>>
>> code in C *must be executed*, but B is not.
>>
>>
>> Is there any availiable API in LLVM to distinguish them?
>>
>> Thanks.
>> _______________________________________________
>> 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