[LLVMdev] Finding Merge nodes in CFG

[John Criswell]

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.
>   

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.


>> 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.
>>
>>     
>>> Thanks in advance.
>>>
>>> regards,
>>> Ambika
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>>       
>>     
>
>
>