[LLVMdev] Trace Use-Def chain

[Andrew Trick]

On May 3, 2011, at 11:37 PM, 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 may be too late responding to be helpful. But this should be easy to do in linear time (disregarding the set lookup time) by maintaining a set of visited blocks and pushing each predecessor block that has not yet been visited on the worklist. Stop pushing predecessors when you reach the def's block. When the worklist is empty, you have all blocks in the set.

-Andy

> On Wed, May 4, 2011 at 7:00 AM, John Criswell <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> 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         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> 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         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/20110506/32c88a8d/attachment.html>