[LLVMdev] Finding Merge nodes in CFG
criswell at uiuc.edu
Tue Jun 1 08:52:04 PDT 2010
ambika at 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.
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
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.
>> ambika wrote:
>>> I have basic block and I want to find a merge node just above this basic
>>> 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.
>>> Thanks in advance.
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
More information about the llvm-dev