[LLVMdev] Finding Merge nodes in CFG
ambika
ambika at cse.iitb.ac.in
Wed Jun 2 12:20:03 PDT 2010
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
>>>>
>>>>
>>>
>>
>>
>>
>
More information about the llvm-dev
mailing list