[LLVMdev] How to Check whether BasicBlock resides in a conditional branch

[Daniel Berlin]

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