[LLVMdev] Finding Merge nodes in CFG

[John Criswell]

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.

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