<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
On 5/4/11 1:37 AM, tarun agrawal wrote:
<blockquote
cite="mid:BANLkTinVxVJ+5wfbyTHN_WNv9-6Xj5cH+A@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=ISO-8859-1">
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>
<br>
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.<br>
<br>
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.<br>
<br>
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.<br>
:)<br>
<br>
-- John T.<br>
<br>
<blockquote
cite="mid:BANLkTinVxVJ+5wfbyTHN_WNv9-6Xj5cH+A@mail.gmail.com"
type="cite">
<br>
<div class="gmail_quote">On Wed, May 4, 2011 at 7:00 AM, John
Criswell <span dir="ltr"><<a moz-do-not-send="true"
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><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 moz-do-not-send="true"
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
moz-do-not-send="true"
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 moz-do-not-send="true" href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a moz-do-not-send="true" href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a>
<a moz-do-not-send="true" 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 moz-do-not-send="true" href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a moz-do-not-send="true" href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a>
<a moz-do-not-send="true" 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>
</blockquote>
<br>
</body>
</html>