[LLVMdev] Trace Use-Def chain

[John Criswell]

On 5/4/11 1:37 AM, tarun agrawal wrote:
> Thanks John,
>
> I know how to iterate through def-use chains and I also have realized 
> the need for an algorithm to do the work. But the algorithm I am able 
> to figure out is not linear in time. It wold be a great help  if 
> someone suggest me a way to get all basic-block along all path between 
> two instruction.

I don't know of an algorithm off-hand.  I suspect that this is the point 
where you'll need to sit down with a compiler or graph theory textbook 
and either find an algorithm or develop one on your own.

One thing that might help would be to think if using dominator and 
post-dominator information could speed up the process.  I'm not sure if 
it would lead to a faster algorithm, but if I had to develop such an 
algorithm, that's where I'd start.

Also, non-linear algorithms are fine on small inputs.  You only need to 
find a better algorithm if your analysis is taking too long to complete 
or a professor/adviser/boss is telling you it has to be better.
:)

-- John T.

>
> On Wed, May 4, 2011 at 7:00 AM, John Criswell <criswell at illinois.edu 
> <mailto:criswell at illinois.edu>> wrote:
>
>     Dear Tarun,
>
>     It just occurred to me that this may or may not be what you are
>     asking about.  This only finds basic blocks along the def-use
>     chain of an instruction; it does not find all basic blocks along
>     all paths between two instructions.  I don't know of an algorithm
>     off-hand for the latter, but if you understand how to iterate over
>     def-use chains and the control-flow graph, then writing up an
>     algorithm for the latter should be pretty easy.
>
>     -- John T.
>
>
>
>     On 5/3/11 8:24 PM, John Criswell wrote:
>>     On 5/3/11 4:08 PM, tarun agrawal wrote:
>>>     HI
>>>
>>>     I know it is a very simple question not worth asking here but I
>>>     am really struggling pls help me out..
>>
>>     This is a question worth asking; it's just that not everyone can
>>     answer all the time.
>>     :)
>>
>>     If all you want to do is to follow the SSA def-use chain within a
>>     single function, then this is very easy.  All you have to do is
>>     use the use_iterator of the Instruction object to iterate through
>>     its def-use chain.  For all uses that are instructions, use the
>>     getParent() method to find the basic block containing the
>>     instruction.  That's it.
>>
>>     This approach won't work in two cases:
>>
>>     1) If you want to trace def/use through memory.  Memory is not in
>>     SSA form, and so you have to use extra analysis to track from
>>     which store the result of a load originates.
>>
>>     2) If you want to track def/use inter-procedurally through
>>     function arguments and return values.  If you don't care about
>>     tracking through memory, this is a fairly easy inter-procedural
>>     analysis to do, and we have some code internally at University of
>>     Illinois that does it.  If you need it, I can talk to Vikram and
>>     see if we can give you a copy.
>>
>>     For more information on how to iterate through def-use chains,
>>     see the LLVM Programmer's Manual:
>>     http://llvm.org/docs/ProgrammersManual.html#iterate_chains
>>
>>     -- John T.
>>
>>>
>>>     On Tue, May 3, 2011 at 10:10 PM, tarun agrawal
>>>     <tarun at cse.iitb.ac.in <mailto:tarun at cse.iitb.ac.in>> wrote:
>>>
>>>         Hi,
>>>
>>>         I need to get all the basic blocks that are there, in the
>>>         path from definition of an instruction to use of that
>>>         instruction.
>>>
>>>
>>>         Regards
>>>         Tarun
>>>
>>>
>>>
>>>     _______________________________________________
>>>     LLVM Developers mailing list
>>>     LLVMdev at cs.uiuc.edu  <mailto:LLVMdev at cs.uiuc.edu>          http://llvm.cs.uiuc.edu
>>>     http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>>
>>     _______________________________________________
>>     LLVM Developers mailing list
>>     LLVMdev at cs.uiuc.edu  <mailto:LLVMdev at cs.uiuc.edu>          http://llvm.cs.uiuc.edu
>>     http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110504/c5ca9087/attachment.html>