[LLVMdev] Finding Merge nodes in CFG

[ambika]

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