Hi Simon,> From: Simone Atzeni <simone.at at gmail.com> > To: John Criswell <jtcriswel at gmail.com> > Cc: llvmdev at cs.uiuc.edu > Subject: Re: [LLVMdev] Walking thru CallGraph bottom up > Message-ID: <318EBA41-2040-4EFE-B330-5813C817C2A2 at gmail.com> > Content-Type: text/plain; charset="windows-1252" > > 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? >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. 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. 1. You can keep a list of functions in your search path, pushing to the list each time you visit a new node. 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. 3. Search in another path, until you hit the node you're looking for. 4. And then you can have a call path from main to your function in the list. Note that you may need a DFS on the entire CallGraph if you want all possible call paths from main to your function. 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. Hope this helps a little. Apologies if you find any format, layout or etiquette problems in my mail. This is the first time I write to a mailing list. Thanks. --- Regards, Kevin Hu hxy9243 at gmail.com> Thanks. > Simone > > > On Feb 25, 2015, at 09:01, John Criswell <jtcriswel at gmail.com> wrote: > > > > On 2/25/15 10:51 AM, Simone Atzeni wrote: > >> Thanks John. > >> > >> I guess I will use a ModulePass, so when I am implementing the > ?runOnModule? function, > >> do I have to loop through all the functions, for each functions all the > BasicBlocks and for each BasicBlock all the instructions > > > > If you know the Instruction, you can get it's basic block using > Instruction::getParent(), and then get its enclosing function using > BasicBlock::getParent(). > > > > 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. > > > >> or given the Module I have to call the CallGraph directly? > >> Is there an example out there? I can?t find anything. > > > > It uses the DSA CallGraph pass, but > http://llvm.org/viewvc/llvm-project/safecode/branches/release_32/lib/InsertPoolChecks/CFIChecks.cpp?revision=189030&view=markup > < > http://llvm.org/viewvc/llvm-project/safecode/branches/release_32/lib/InsertPoolChecks/CFIChecks.cpp?revision=189030&view=markup> > might provide a decent example. > > > > Regards, > > > > John Criswell > > > >> > >> Thanks. > >> Simone > >> > >>> On Feb 24, 2015, at 13:29, John Criswell <jtcriswel at gmail.com> wrote: > >>> > >>> On 2/24/15 2:27 PM, Simone Atzeni wrote: > >>>> Hi all, > >>>> > >>>> I would like to create a Pass that given an IR instruction walks > starting from that instruction up to the main function > >>>> to identify all the functions call that have been made to call that > instruction. > >>>> > >>>> Is it possible? What kind of Pass should I create? > >>> Yes, it is possible. I think a ModulePass would be most appropriate, > though a FunctionPass may be alright. > >>> > >>> 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). > >>> > >>> -- John T. > >>> > >>>> Thanks > >>>> Best, > >>>> Simone > >>>> > >>>> Simone Atzeni > >>>> simone.at at gmail.com > >>>> +1 (801) 696-8373 > >>>> > >>>> > >>>> _______________________________________________ > >>>> LLVM Developers mailing list > >>>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > >>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >>> > >>> -- > >>> John Criswell > >>> Assistant Professor > >>> Department of Computer Science, University of Rochester > >>> http://www.cs.rochester.edu/u/criswell > >>> > > > > > > -- > > John Criswell > > Assistant Professor > > Department of Computer Science, University of Rochester > > http://www.cs.rochester.edu/u/criswell < > http://www.cs.rochester.edu/u/criswell> > -------------- next part -------------- > An HTML attachment was scrubbed... > URL: < > http://lists.cs.uiuc.edu/pipermail/llvmdev/attachments/20150226/51760124/attachment-0001.html > > > d of LLVMdev Digest, Vol 128, Issue 111 > ***************************************** >Yours, Kevin Hu -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150226/25de5871/attachment.html>
Dear Simon, 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. 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. 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). Regards, John Criswell On 2/26/15 10:13 PM, Kevin Hu wrote:> Hi Simon, > > From: Simone Atzeni <simone.at at gmail.com <mailto:simone.at at gmail.com>> > To: John Criswell <jtcriswel at gmail.com <mailto:jtcriswel at gmail.com>> > Cc: llvmdev at cs.uiuc.edu <mailto:llvmdev at cs.uiuc.edu> > Subject: Re: [LLVMdev] Walking thru CallGraph bottom up > Message-ID: <318EBA41-2040-4EFE-B330-5813C817C2A2 at gmail.com > <mailto:318EBA41-2040-4EFE-B330-5813C817C2A2 at gmail.com>> > Content-Type: text/plain; charset="windows-1252" > > 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? > > > 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. > > 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. > > 1. You can keep a list of functions in your search path, pushing to > the list each time you visit a new node. > 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. > 3. Search in another path, until you hit the node you're looking for. > 4. And then you can have a call path from main to your function in the > list. > > Note that you may need a DFS on the entire CallGraph if you want all > possible call paths from main to your function. > > 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. > > Hope this helps a little. > > Apologies if you find any format, layout or etiquette problems in my > mail. This is the first time I write to a mailing list. > > Thanks. > > --- > Regards, > Kevin Hu > hxy9243 at gmail.com <mailto:hxy9243 at gmail.com> > > Thanks. > Simone > > > On Feb 25, 2015, at 09:01, John Criswell <jtcriswel at gmail.com > <mailto:jtcriswel at gmail.com>> wrote: > > > > On 2/25/15 10:51 AM, Simone Atzeni wrote: > >> Thanks John. > >> > >> I guess I will use a ModulePass, so when I am implementing the > ?runOnModule? function, > >> do I have to loop through all the functions, for each functions > all the BasicBlocks and for each BasicBlock all the instructions > > > > If you know the Instruction, you can get it's basic block using > Instruction::getParent(), and then get its enclosing function > using BasicBlock::getParent(). > > > > 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. > > > >> or given the Module I have to call the CallGraph directly? > >> Is there an example out there? I can?t find anything. > > > > It uses the DSA CallGraph pass, but > http://llvm.org/viewvc/llvm-project/safecode/branches/release_32/lib/InsertPoolChecks/CFIChecks.cpp?revision=189030&view=markup > <http://llvm.org/viewvc/llvm-project/safecode/branches/release_32/lib/InsertPoolChecks/CFIChecks.cpp?revision=189030&view=markup> > might provide a decent example. > > > > Regards, > > > > John Criswell > > > >> > >> Thanks. > >> Simone > >> > >>> On Feb 24, 2015, at 13:29, John Criswell <jtcriswel at gmail.com > <mailto:jtcriswel at gmail.com>> wrote: > >>> > >>> On 2/24/15 2:27 PM, Simone Atzeni wrote: > >>>> Hi all, > >>>> > >>>> I would like to create a Pass that given an IR instruction > walks starting from that instruction up to the main function > >>>> to identify all the functions call that have been made to > call that instruction. > >>>> > >>>> Is it possible? What kind of Pass should I create? > >>> Yes, it is possible. I think a ModulePass would be most > appropriate, though a FunctionPass may be alright. > >>> > >>> 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). > >>> > >>> -- John T. > >>> > >>>> Thanks > >>>> Best, > >>>> Simone > >>>> > >>>> Simone Atzeni > >>>> simone.at at gmail.com <mailto:simone.at at gmail.com> > >>>> +1 (801) 696-8373 <tel:%2B1%20%28801%29%20696-8373> > >>>> > >>>> > >>>> _______________________________________________ > >>>> LLVM Developers mailing list > >>>> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu> > http://llvm.cs.uiuc.edu > >>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >>> > >>> -- > >>> John Criswell > >>> Assistant Professor > >>> Department of Computer Science, University of Rochester > >>> http://www.cs.rochester.edu/u/criswell > >>> > > > > > > -- > > John Criswell > > Assistant Professor > > Department of Computer Science, University of Rochester > > http://www.cs.rochester.edu/u/criswell > <http://www.cs.rochester.edu/u/criswell> > -------------- next part -------------- > An HTML attachment was scrubbed... > URL: > <http://lists.cs.uiuc.edu/pipermail/llvmdev/attachments/20150226/51760124/attachment-0001.html> > d of LLVMdev Digest, Vol 128, Issue 111 > ***************************************** > > > > > Yours, > Kevin Hu-- John Criswell Assistant Professor Department of Computer Science, University of Rochester http://www.cs.rochester.edu/u/criswell -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150227/b1deeaa5/attachment.html>
Hi guys, thank you so much for your great answers. I kept looking for such a data structure but there is no such a thing as you confirmed. But I think I have all the info I need thanks to your suggestions. If I get something working I will share it! Thanks again! Cheers, Simone> On Feb 26, 2015, at 22:00, John Criswell <jtcriswel at gmail.com> wrote: > > Dear Simon, > > 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. > > 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. > > 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). > > Regards, > > John Criswell > > On 2/26/15 10:13 PM, Kevin Hu wrote: >> >> Hi Simon, >> >> From: Simone Atzeni <simone.at at gmail.com <mailto:simone.at at gmail.com>> >> To: John Criswell <jtcriswel at gmail.com <mailto:jtcriswel at gmail.com>> >> Cc: llvmdev at cs.uiuc.edu <mailto:llvmdev at cs.uiuc.edu> >> Subject: Re: [LLVMdev] Walking thru CallGraph bottom up >> Message-ID: <318EBA41-2040-4EFE-B330-5813C817C2A2 at gmail.com <mailto:318EBA41-2040-4EFE-B330-5813C817C2A2 at gmail.com>> >> Content-Type: text/plain; charset="windows-1252" >> >> 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? >> >> 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. >> >> 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. >> >> 1. You can keep a list of functions in your search path, pushing to the list each time you visit a new node. >> 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. >> 3. Search in another path, until you hit the node you're looking for. >> 4. And then you can have a call path from main to your function in the list. >> >> Note that you may need a DFS on the entire CallGraph if you want all possible call paths from main to your function. >> >> 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. >> >> Hope this helps a little. >> >> Apologies if you find any format, layout or etiquette problems in my mail. This is the first time I write to a mailing list. >> >> Thanks. >> >> --- >> Regards, >> Kevin Hu >> hxy9243 at gmail.com <mailto:hxy9243 at gmail.com> >> >> Thanks. >> Simone >> >> > On Feb 25, 2015, at 09:01, John Criswell <jtcriswel at gmail.com <mailto:jtcriswel at gmail.com>> wrote: >> > >> > On 2/25/15 10:51 AM, Simone Atzeni wrote: >> >> Thanks John. >> >> >> >> I guess I will use a ModulePass, so when I am implementing the ?runOnModule? function, >> >> do I have to loop through all the functions, for each functions all the BasicBlocks and for each BasicBlock all the instructions >> > >> > If you know the Instruction, you can get it's basic block using Instruction::getParent(), and then get its enclosing function using BasicBlock::getParent(). >> > >> > 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. >> > >> >> or given the Module I have to call the CallGraph directly? >> >> Is there an example out there? I can?t find anything. >> > >> > It uses the DSA CallGraph pass, but http://llvm.org/viewvc/llvm-project/safecode/branches/release_32/lib/InsertPoolChecks/CFIChecks.cpp?revision=189030&view=markup <http://llvm.org/viewvc/llvm-project/safecode/branches/release_32/lib/InsertPoolChecks/CFIChecks.cpp?revision=189030&view=markup> <http://llvm.org/viewvc/llvm-project/safecode/branches/release_32/lib/InsertPoolChecks/CFIChecks.cpp?revision=189030&view=markup <http://llvm.org/viewvc/llvm-project/safecode/branches/release_32/lib/InsertPoolChecks/CFIChecks.cpp?revision=189030&view=markup>> might provide a decent example. >> > >> > Regards, >> > >> > John Criswell >> > >> >> >> >> Thanks. >> >> Simone >> >> >> >>> On Feb 24, 2015, at 13:29, John Criswell <jtcriswel at gmail.com <mailto:jtcriswel at gmail.com>> wrote: >> >>> >> >>> On 2/24/15 2:27 PM, Simone Atzeni wrote: >> >>>> Hi all, >> >>>> >> >>>> I would like to create a Pass that given an IR instruction walks starting from that instruction up to the main function >> >>>> to identify all the functions call that have been made to call that instruction. >> >>>> >> >>>> Is it possible? What kind of Pass should I create? >> >>> Yes, it is possible. I think a ModulePass would be most appropriate, though a FunctionPass may be alright. >> >>> >> >>> 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). >> >>> >> >>> -- John T. >> >>> >> >>>> Thanks >> >>>> Best, >> >>>> Simone >> >>>> >> >>>> Simone Atzeni >> >>>> simone.at at gmail.com <mailto:simone.at at gmail.com> >> >>>> +1 (801) 696-8373 <tel:%2B1%20%28801%29%20696-8373> >> >>>> >> >>>> >> >>>> _______________________________________________ >> >>>> LLVM Developers mailing list >> >>>> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu> http://llvm.cs.uiuc.edu <http://llvm.cs.uiuc.edu/> >> >>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev <http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev> >> >>> >> >>> -- >> >>> John Criswell >> >>> Assistant Professor >> >>> Department of Computer Science, University of Rochester >> >>> http://www.cs.rochester.edu/u/criswell <http://www.cs.rochester.edu/u/criswell> >> >>> >> > >> > >> > -- >> > John Criswell >> > Assistant Professor >> > Department of Computer Science, University of Rochester >> > http://www.cs.rochester.edu/u/criswell <http://www.cs.rochester.edu/u/criswell> <http://www.cs.rochester.edu/u/criswell <http://www.cs.rochester.edu/u/criswell>> >> -------------- next part -------------- >> An HTML attachment was scrubbed... >> URL: <http://lists.cs.uiuc.edu/pipermail/llvmdev/attachments/20150226/51760124/attachment-0001.html <http://lists.cs.uiuc.edu/pipermail/llvmdev/attachments/20150226/51760124/attachment-0001.html>> >> d of LLVMdev Digest, Vol 128, Issue 111 >> ***************************************** >> >> >> >> Yours, >> Kevin Hu > > > -- > John Criswell > Assistant Professor > Department of Computer Science, University of Rochester > http://www.cs.rochester.edu/u/criswell <http://www.cs.rochester.edu/u/criswell>-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150226/38e422bf/attachment.html>