Hi,
I have basic block and I want to find a merge node just above this basic block.
How can I do this?
Thanks in advance.
regards,
Ambika
ambika wrote:
Hi,
I have basic block and I want to find a merge node just above this basic block.
How can I do this?
Can you clarify what you mean by a "merge node?" Are you looking for the proper place to insert a phi node? Are you trying to find the first basic block that dominates the basic block of interest, or do you mean something else entirely?
-- John T.
Actually I have collected some pointer information in the form [ p -> a,c
]. Now suppose at some node I have information as [p->a,c]. Now i want to
find a merge node above this node where this information is actually
geting merged.
So if I get a merge node above this, I can check in its predecessors if
their out has only [p->a] or [p->c] and if not so then I will look for the
next merge node above this one, and so on.
ambika@cse.iitb.ac.in wrote:
Actually I have collected some pointer information in the form [ p -> a,c
]. Now suppose at some node I have information as [p->a,c]. Now i want to
find a merge node above this node where this information is actually
geting merged.
So if I get a merge node above this, I can check in its predecessors if
their out has only [p->a] or [p->c] and if not so then I will look for the
next merge node above this one, and so on.
Okay.
If you're only interested in the intra-procedural merging of points-to information for SSA variables, then you simply need to climb up the def-use chain of the value of interest until you hit a phi-node. Once you hit a phi-node, then you know that information is getting merged from incoming values from different predecessor basic blocks. Look at each input to the phi-node and the input's corresponding predecessor basic block, and you should get what you want.
Note, however, that this only handles merging of points-to information through SSA values within a single function (i.e., simple intra-procedural data flow). There are two other possible sources of merging:
1) Merging through non-SSA variables (i.e., memory). If the points-to analysis you're examining tracks information through memory, then merging can be done at LLVM store instructions (e.g., two pointers could be stored into the same memory location). Back-tracking def-use chains isn't sufficient for finding this kind of merging, and since the points-to analysis would probably use classical data-flow analysis (as described in the Kam and Ullman paper), finding the exact merge point after the analysis has been done may not be possible.
2) Inter-procedural data-flow through function arguments and return values. You can generally track these through SSA values, but indirect function calls and vararg functions can make this difficult.
-- John T.
Actually I am interested only if the information merges at join node, otherwise not... So just getting a node with more than one predecessor might help.
But can I figure out if there is a function call in between, in any of these nodes?
Thanks a lot for helping out...
John Criswell wrote:
ambika wrote:
Actually I am interested only if the information merges at join node, otherwise not... So just getting a node with more than one predecessor might help.
It sounds like a phi instruction is what you're looking for, then.
But can I figure out if there is a function call in between, in any of these nodes?
You should be able to. The easiest thing to do is to record all the basic blocks you visit while climbing up the def-use chain and then to iterate through all instructions in each basic block and see if there's a call instruction (you may want to ignore calls to intrinsic functions).
You'll want to record the set of basic blocks or instructions visited anyway because you want to avoid infinite looping through a def-use chain that happens to be in a loop.
-- John T.