<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Hi guys,<div class=""><br class=""></div><div class="">thank you so much for your great answers.</div><div class="">I kept looking for such a data structure but there is no such a thing as you confirmed.</div><div class="">But I think I have all the info I need thanks to your suggestions.</div><div class="">If I get something working I will share it!</div><div class=""><br class=""></div><div class="">Thanks again!</div><div class="">Cheers,</div><div class="">Simone</div><div class=""><div apple-content-edited="true" class=""><div class=""><br class=""></div>
</div>
<br class=""><div><blockquote type="cite" class=""><div class="">On Feb 26, 2015, at 22:00, John Criswell <<a href="mailto:jtcriswel@gmail.com" class="">jtcriswel@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class="">
<meta content="text/html; charset=utf-8" http-equiv="Content-Type" class="">
<div text="#000000" bgcolor="#FFFFFF" class="">
<div class="moz-cite-prefix">Dear Simon,<br class="">
<br class="">
Kevin is correct; as far as I can tell, there is no method of
getting the functions calling a given function. Instead, you have
to start at the main() function and search for the function using
a depth-first or breadth-first search.<br class="">
<br class="">
What may make sense is to build a new data structure that has
nodes that point from callees to callers once and then use that
for your queries. That way, you're not researching the CallGraph
all the time.<br class="">
<br class="">
One important note is that the CallGraph has an "external node"
which represents all unresolved calls (e.g., indirect function
calls). Technically, you need to start searching from this node
as well as the main() node (as a program can call out to external
code which then calls back into the program; think of qsort() as
an example).<br class="">
<br class="">
Regards,<br class="">
<br class="">
John Criswell<br class="">
<br class="">
On 2/26/15 10:13 PM, Kevin Hu wrote:<br class="">
</div>
<blockquote cite="mid:CAH_2Da3uMT7_N_R_TnmUYw2kieGcKYAiqBaA5ZAwqBP+yna9TQ@mail.gmail.com" type="cite" class="">
<meta http-equiv="Context-Type" content="text/html; charset=UTF-8" class="">
<div dir="ltr" class=""><img moz-do-not-send="true" height="1" width="1" class="">
<div class="gmail_extra">
<div class="gmail_quote">
<div class="">Hi Simon,</div>
<div class=""> <br class="">
</div>
<blockquote class="gmail_quote">
From: Simone Atzeni <<a moz-do-not-send="true" href="mailto:simone.at@gmail.com" class="">simone.at@gmail.com</a>><br class="">
To: John Criswell <<a moz-do-not-send="true" href="mailto:jtcriswel@gmail.com" class="">jtcriswel@gmail.com</a>><br class="">
Cc: <a moz-do-not-send="true" href="mailto:llvmdev@cs.uiuc.edu" class="">llvmdev@cs.uiuc.edu</a><br class="">
Subject: Re: [LLVMdev] Walking thru CallGraph bottom up<br class="">
Message-ID: <<a moz-do-not-send="true" href="mailto:318EBA41-2040-4EFE-B330-5813C817C2A2@gmail.com" class="">318EBA41-2040-4EFE-B330-5813C817C2A2@gmail.com</a>><br class="">
Content-Type: text/plain; charset="windows-1252"<br class="">
<br class="">
I think I got it and the example is pretty, however for
what I understand, I can get the CallGraphNode for a given
function F that has a list that represents all the
functions that F is calling, but how can I get the list of
the functions that are calling F? There is not a sort a
similar list?<br class="">
</blockquote>
<div class=""><br class="">
</div>
<div class="">After doing a simple search inside the LLVM documents,
I found no so such data structures or methods for finding
the callers of a CallGraphNode.</div>
<div class=""><br class="">
</div>
<div class="">However, since your problem is to find the path from
main to the target function in the CallGraph, I think a
depth-first-search from the main node might work.
Following is the algorithm I have in mind.</div>
<div class=""><br class="">
</div>
<div class="">1. You can keep a list of functions in your search
path, pushing to the list each time you visit a new node.</div>
<div class="">2. If you find the one you currently have is a wrong
path (you reach a leaf or a visited node), you pop out all
the functions in the wrong path from your list.</div>
<div class="">3. Search in another path, until you hit the node
you're looking for. </div>
<div class="">4. And then you can have a call path from main to your
function in the list.</div>
<div class=""><br class="">
</div>
<div class="">Note that you may need a DFS on the entire CallGraph if
you want all possible call paths from main to your
function.</div>
<div class=""><br class="">
</div>
<div class="">IMHO, by getting a list of callers of a target function
doesn't actually help simplify the problem a lot. You
still need a DFS or BFS from the node to find the main
function node.</div>
<div class=""><br class="">
</div>
<div class="">Hope this helps a little.</div>
<div class=""><br class="">
</div>
<div class="">Apologies if you find any format, layout or etiquette
problems in my mail. This is the first time I write to a
mailing list.</div>
<div class=""><br class="">
</div>
<div class="">Thanks.</div>
<div class=""><br class="">
</div>
<div class="">---</div>
<div class="">Regards,</div>
<div class="">Kevin Hu</div>
<div class=""><a moz-do-not-send="true" href="mailto:hxy9243@gmail.com" class="">hxy9243@gmail.com</a></div>
<div class=""> </div>
<blockquote class="gmail_quote">
Thanks.<br class="">
Simone<br class="">
<br class="">
> On Feb 25, 2015, at 09:01, John Criswell <<a moz-do-not-send="true" href="mailto:jtcriswel@gmail.com" class="">jtcriswel@gmail.com</a>>
wrote:<br class="">
><br class="">
> On 2/25/15 10:51 AM, Simone Atzeni wrote:<br class="">
>> Thanks John.<br class="">
>><br class="">
>> I guess I will use a ModulePass, so when I am
implementing the ?runOnModule? function,<br class="">
>> do I have to loop through all the functions, for
each functions all the BasicBlocks and for each BasicBlock
all the instructions<br class="">
><br class="">
> If you know the Instruction, you can get it's basic
block using Instruction::getParent(), and then get its
enclosing function using BasicBlock::getParent().<br class="">
><br class="">
> Once you know the enclosing function, you can use the
CallGraph pass to find which functions call it, and then
repeat the procedures for functions calling that function,
etc.<br class="">
><br class="">
>> or given the Module I have to call the CallGraph
directly?<br class="">
>> Is there an example out there? I can?t find
anything.<br class="">
><br class="">
> It uses the DSA CallGraph pass, but <a moz-do-not-send="true" href="http://llvm.org/viewvc/llvm-project/safecode/branches/release_32/lib/InsertPoolChecks/CFIChecks.cpp?revision=189030&view=markup" target="_blank" class="">http://llvm.org/viewvc/llvm-project/safecode/branches/release_32/lib/InsertPoolChecks/CFIChecks.cpp?revision=189030&view=markup</a>
<<a moz-do-not-send="true" href="http://llvm.org/viewvc/llvm-project/safecode/branches/release_32/lib/InsertPoolChecks/CFIChecks.cpp?revision=189030&view=markup" target="_blank" class="">http://llvm.org/viewvc/llvm-project/safecode/branches/release_32/lib/InsertPoolChecks/CFIChecks.cpp?revision=189030&view=markup</a>>
might provide a decent example.<br class="">
><br class="">
> Regards,<br class="">
><br class="">
> John Criswell<br class="">
><br class="">
>><br class="">
>> Thanks.<br class="">
>> Simone<br class="">
>><br class="">
>>> On Feb 24, 2015, at 13:29, John Criswell <<a moz-do-not-send="true" href="mailto:jtcriswel@gmail.com" class="">jtcriswel@gmail.com</a>>
wrote:<br class="">
>>><br class="">
>>> On 2/24/15 2:27 PM, Simone Atzeni wrote:<br class="">
>>>> Hi all,<br class="">
>>>><br class="">
>>>> I would like to create a Pass that given
an IR instruction walks starting from that instruction up
to the main function<br class="">
>>>> to identify all the functions call that
have been made to call that instruction.<br class="">
>>>><br class="">
>>>> Is it possible? What kind of Pass should
I create?<br class="">
>>> Yes, it is possible. I think a ModulePass
would be most appropriate, though a FunctionPass may be
alright.<br class="">
>>><br class="">
>>> To get the call graph, you can use LLVM's
CallGraph analysis. If you need to handle function
pointers more accurately than LLVM's internal CallGraph
analysis does, you can use DSA's CallGraph analysis (which
has the same interface but may only work with LLVM 3.2 and
earlier LLVM releases).<br class="">
>>><br class="">
>>> -- John T.<br class="">
>>><br class="">
>>>> Thanks<br class="">
>>>> Best,<br class="">
>>>> Simone<br class="">
>>>><br class="">
>>>> Simone Atzeni<br class="">
>>>> <a moz-do-not-send="true" href="mailto:simone.at@gmail.com" class="">simone.at@gmail.com</a><br class="">
>>>> <a moz-do-not-send="true" href="tel:%2B1%20%28801%29%20696-8373" value="+18016968373" class="">+1 (801) 696-8373</a><br class="">
>>>><br class="">
>>>><br class="">
>>>>
_______________________________________________<br class="">
>>>> LLVM Developers mailing list<br class="">
>>>> <a moz-do-not-send="true" href="mailto:LLVMdev@cs.uiuc.edu" class="">LLVMdev@cs.uiuc.edu</a>
<a moz-do-not-send="true" href="http://llvm.cs.uiuc.edu/" target="_blank" class="">http://llvm.cs.uiuc.edu</a><br class="">
>>>> <a moz-do-not-send="true" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank" class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br class="">
>>><br class="">
>>> --<br class="">
>>> John Criswell<br class="">
>>> Assistant Professor<br class="">
>>> Department of Computer Science, University of
Rochester<br class="">
>>> <a moz-do-not-send="true" href="http://www.cs.rochester.edu/u/criswell" target="_blank" class="">http://www.cs.rochester.edu/u/criswell</a><br class="">
>>><br class="">
><br class="">
><br class="">
> --<br class="">
> John Criswell<br class="">
> Assistant Professor<br class="">
> Department of Computer Science, University of
Rochester<br class="">
> <a moz-do-not-send="true" href="http://www.cs.rochester.edu/u/criswell" target="_blank" class="">http://www.cs.rochester.edu/u/criswell</a>
<<a moz-do-not-send="true" href="http://www.cs.rochester.edu/u/criswell" target="_blank" class="">http://www.cs.rochester.edu/u/criswell</a>><br class="">
-------------- next part --------------<br class="">
An HTML attachment was scrubbed...<br class="">
URL: <<a moz-do-not-send="true" href="http://lists.cs.uiuc.edu/pipermail/llvmdev/attachments/20150226/51760124/attachment-0001.html" target="_blank" class="">http://lists.cs.uiuc.edu/pipermail/llvmdev/attachments/20150226/51760124/attachment-0001.html</a>><br class="">
d of LLVMdev Digest, Vol 128, Issue 111<br class="">
*****************************************<br class="">
</blockquote>
</div>
<br class="">
<br class="">
<div class=""><br class="">
</div>
<div class="gmail_signature">
<div dir="ltr" class="">Yours,
<div class="">Kevin Hu</div>
</div>
</div>
</div>
</div>
</blockquote>
<br class="">
<br class="">
<pre class="moz-signature" cols="72">--
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
<a class="moz-txt-link-freetext" href="http://www.cs.rochester.edu/u/criswell">http://www.cs.rochester.edu/u/criswell</a></pre>
</div>
</div></blockquote></div><br class=""></div></body></html>