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.
In the general sense you may get some help by looking at the control dependence graph.
- dibyendu
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!
Sorry, for confusion. Yes, I meant exactly this - that there are no "forks". You actually can use some flow network algorithm: let's say that entry BB is a source node with unity flow, if block has two successors, you split the flow between them. After calculating a flow within every edge, all *must* nodes will have a sum of incoming flows equal to one - that's how you distinguish it from *may* nodes.
Actually, you should read
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.
like this:
And after that for all the BB you have visited more than once, you try to find a parent that has a branch instruction that fork the flow as a terminator. Additionally you ensure that there are no BB with branches that are not forks as terminators on your way.
But anyway ignore this, this is ineffective - the flow thing works faster.
Thanks, I may have a try.
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.
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.