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 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/20110503/ffb68e21/attachment.html>
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 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/20110503/1fe6e524/attachment.html>
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. 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 listLLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.eduhttp://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > > _______________________________________________ > LLVM Developers mailing listLLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.eduhttp://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110504/2213836b/attachment.html>