<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><div>On May 3, 2011, at 11:37 PM, tarun agrawal wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">Thanks John,<br><br>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.<br></blockquote><div><br></div><div>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.</div><div><br></div><div>-Andy</div><br><blockquote type="cite">
<div class="gmail_quote">On Wed, May 4, 2011 at 7:00 AM, John Criswell <span dir="ltr"><<a href="mailto:criswell@illinois.edu" target="_blank">criswell@illinois.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div bgcolor="#ffffff" text="#000000">
Dear Tarun,<br>
<br>
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.<br>
<br>
-- John T.<div><div></div><div><br>
<br>
<br>
On 5/3/11 8:24 PM, John Criswell wrote:
<blockquote type="cite">
On 5/3/11 4:08 PM, tarun agrawal wrote:
<blockquote type="cite"> HI <br>
<br>
I know it is a very simple question not worth asking here but I
am really struggling pls help me out..<br>
</blockquote>
<br>
This is a question worth asking; it's just that not everyone can
answer all the time.<br>
:)<br>
<br>
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.<br>
<br>
This approach won't work in two cases:<br>
<br>
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.<br>
<br>
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.<br>
<br>
For more information on how to iterate through def-use chains, see
the LLVM Programmer's Manual:<br>
<a href="http://llvm.org/docs/ProgrammersManual.html#iterate_chains" target="_blank">http://llvm.org/docs/ProgrammersManual.html#iterate_chains</a><br>
<br>
-- John T.<br>
<br>
<blockquote type="cite"><br>
<div class="gmail_quote">On Tue, May 3, 2011 at 10:10 PM, tarun
agrawal <span dir="ltr"><<a href="mailto:tarun@cse.iitb.ac.in" target="_blank">tarun@cse.iitb.ac.in</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">Hi,<br>
<br>
I need to get all the basic blocks that are there, in the
path from definition of an instruction to use of that
instruction.<br>
<br>
<br>
Regards <br>
<font color="#888888">Tarun<br>
</font></blockquote>
</div>
<br>
<pre><fieldset></fieldset>
_______________________________________________
LLVM Developers mailing list
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu/" target="_blank">http://llvm.cs.uiuc.edu</a>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a>
</pre>
</blockquote>
<br>
<pre><fieldset></fieldset>
_______________________________________________
LLVM Developers mailing list
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu/" target="_blank">http://llvm.cs.uiuc.edu</a>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a>
</pre>
</blockquote>
<br>
</div></div></div>
</blockquote></div><br>
_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></blockquote></div><br></body></html>