[LLVMdev] Walking thru CallGraph bottom up

[Kevin Hu]

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>