Indirect function call

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

Indirect function call

Nai XIA
Hi,

The "LLVM Language Reference Manual" mentions about "indirect function call".
I am just curious about what exactly is the __syntax__ of them and how I can
get the callee of an indirect callsite.
>From my point of view, there is hardly any cases where indirect calls are
needed, because anywhere we use a "fptr" in C, it could just be represented
in LLVM IR like this:

%tmp = load void ()** %fptr
call void ()* %tmp( )

So what is indirect call used for?

--
Regards,
Nai

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Indirect function call

Nai XIA
Sorry, again for my noise. :(
The paper -- "The LLVM Instruction Set and Compilation Strategy"  thoroughly discussed the issue
although not mentioned in details in "Ref Manual".

On Sunday 21 May 2006 12:21, Nai Xia wrote:

> Hi,
>
> The "LLVM Language Reference Manual" mentions about "indirect function call".
> I am just curious about what exactly is the __syntax__ of them and how I can
> get the callee of an indirect callsite.
> From my point of view, there is hardly any cases where indirect calls are
> needed, because anywhere we use a "fptr" in C, it could just be represented
> in LLVM IR like this:
>
> %tmp = load void ()** %fptr
> call void ()* %tmp( )
>
> So what is indirect call used for?
>

--
Regards,
Nai

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Re: Indirect function call

AaronNGray
>> So what is indirect call used for?

Virtual method calls or delegates :)

Aaron

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Indirect function call

ymxia
In reply to this post by Nai XIA

The follwing is a snippet of code to find some indirect calls in a module, which I
learned from TopDownClosure.cpp:

void FPS::repairCallGraph(Module &M) {
        CompleteBUDataStructures &DS = getAnalysis<CompleteBUDataStructures>();
        for (Module::iterator f = M.begin(); f != M.end(); ++f ) {
                if( f->isExternal() ) continue;
                for (Function::iterator I = f->begin(); I != f->end(); ++I)  {
                        for(BasicBlock::iterator J = I->begin(); J != I->end(); ++J) {
                                if(CallInst *cs = dyn_cast<CallInst>(J)) {
                                        Function *callee = cs->getCalledFunction();
                                        if(callee) continue;//not a function pointer.
                                        for(CompleteBUDataStructures::callee_iterator K = DS.callee_begin(J); K !=
DS.callee_end(J); ++K) {
                                                if(K->first != J) continue;

                                                CallGraphNode *cgn = getAnalysis<CallGraph>()[f]; // Find a indirect call!
                                                CallGraphNode *calleecgn = getAnalysis<CallGraph>()[K->second];
                                                cgn->addCalledFunction(calleecgn);
                                                std::cerr<<"\n indirect call in "<<f->getName()<<*J<<", callee:
"<<K->second->getName();
                                        }
                                }
                        }
                }
        }
}

But my code does not always works: if the arguments are not pointer,
CompleteBUDataStructures not records it. So, if you want to find all indirect
calls, you maybe have to repair CompleteBUDataStructures. :)

If you do not use BUDataStructures, you can do it yourself: find all load/store
instructions with its destination is function type.



_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Indirect function call

Andrew Lenharth-3
On Mon, 2006-05-22 at 15:33 +0800, 夏一民 wrote:
> But my code does not always works: if the arguments are not pointer,
> CompleteBUDataStructures not records it. So, if you want to find all indirect
> calls, you maybe have to repair CompleteBUDataStructures. :)

Not surprising, CBU is trying to do something entirely different that
what you are.

> If you do not use BUDataStructures, you can do it yourself: find all load/store
> instructions with its destination is function type.

You may want to look at how the call graph builder works.  It finds all
indirect call sites, and also finds all functions whose address escapes
(this is, may be called indirectly).

Finding indirect calls is actually easy, just check if the Op(0) of the
call (or invoke) instruction !isa<Function>.

Andrew


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Indirect function call

Nai XIA
On Monday 22 May 2006 22:22, Andrew Lenharth wrote:

> On Mon, 2006-05-22 at 15:33 +0800, 澶忎竴姘� wrote:
> > But my code does not always works: if the arguments are not pointer,
> > CompleteBUDataStructures not records it. So, if you want to find all indirect
> > calls, you maybe have to repair CompleteBUDataStructures. :)
>
> Not surprising, CBU is trying to do something entirely different that
> what you are.
>
> > If you do not use BUDataStructures, you can do it yourself: find all load/store
> > instructions with its destination is function type.
>
> You may want to look at how the call graph builder works.  It finds all
> indirect call sites, and also finds all functions whose address escapes
> (this is, may be called indirectly).

  The BasicCallGraph class only lines out the indirect calls(makes the caller point to external node),
but do not resolves them using alias analysis such as DSA.
I think DSA solve this problem for interested call sites by finding the corresponding globals(i.e. the functions)
for the callsite DSnode. Maybe 夏一民 just wanted to point out that DSA does not take all callsite into count.
But just as suggested in callgraph.h, "As an extension in the future, there may be multiple nodes with a null
function.  These will be used when we can prove (through pointer analysis) that an indirect call site can
call only a specific set of functions."

Maybe Chris can us give more helpful comments.

>
> Finding indirect calls is actually easy, just check if the Op(0) of the
> call (or invoke) instruction !isa<Function>.
>
> Andrew
>
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

--
Regards,
Nai

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Indirect function call

Chris Lattner
On Tue, 23 May 2006, Nai Xia wrote:
> Maybe Chris can us give more helpful comments.

Andrew (and Dinakar, and perhaps others) are the current current
maintainers of DSA.

-Chris

--
http://nondot.org/sabre/
http://llvm.org/

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Indirect function call

Nai XIA
On Tuesday 23 May 2006 13:34, Chris Lattner wrote:
> On Tue, 23 May 2006, Nai Xia wrote:
> > Maybe Chris can us give more helpful comments.
>
> Andrew (and Dinakar, and perhaps others) are the current current
> maintainers of DSA.
Oh, I'd say sorry to you and Andrew both.
I had though you are the maintainer... ...

So I am currently thinking that maybe it is not hard to make the callgraph more accurate
in a similar way DSA deals with indirect callsites.
I am just curious about why it is not already in LLVM.
I think identifying the range of an indirect call is a worthwhile job,
for example if we want to track the correctness of a program's control flow
with the possibility that it is being attacked through buffer overflow.

>
> -Chris
>

--
Regards,
Nai

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Indirect function call

Chris Lattner
On Tue, 23 May 2006, Nai Xia wrote:

> So I am currently thinking that maybe it is not hard to make the
> callgraph more accurate in a similar way DSA deals with indirect
> callsites. I am just curious about why it is not already in LLVM. I
> think identifying the range of an indirect call is a worthwhile job, for
> example if we want to track the correctness of a program's control flow
> with the possibility that it is being attacked through buffer overflow.

Sure.  More precise call graph analysis can benefit many clients.  This is
why the CallGraph interface is an abstract one that can be implemented
with many different algorithms.  If you'd like to work on a new
implementation, that would be great.

-Chris

--
http://nondot.org/sabre/
http://llvm.org/

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Indirect function call

Nai XIA
I think I will make a try. :)

On Tuesday 23 May 2006 14:03, Chris Lattner wrote:

> On Tue, 23 May 2006, Nai Xia wrote:
>
> > So I am currently thinking that maybe it is not hard to make the
> > callgraph more accurate in a similar way DSA deals with indirect
> > callsites. I am just curious about why it is not already in LLVM. I
> > think identifying the range of an indirect call is a worthwhile job, for
> > example if we want to track the correctness of a program's control flow
> > with the possibility that it is being attacked through buffer overflow.
>
> Sure.  More precise call graph analysis can benefit many clients.  This is
> why the CallGraph interface is an abstract one that can be implemented
> with many different algorithms.  If you'd like to work on a new
> implementation, that would be great.
>
> -Chris
>

--
Regards,
Nai

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Re: Indirect function call

ymxia
In reply to this post by Nai XIA
>On Monday 22 May 2006 22:22, Andrew Lenharth wrote:
>  The BasicCallGraph class only lines out the indirect calls(makes the caller
point to external node),
>but do not resolves them using alias analysis such as DSA.
>I think DSA solve this problem for interested call sites by finding the
corresponding globals(i.e. the functions)
>for the callsite DSnode.

Yes, if we want to determine all indirect call(including function pointers in
structs, arrays), we should improve DSA to analyze function pointer, and then
exploit pointing set of function pointer in callgraph analysis. :)

Yimin


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Indirect function call

Andrew Lenharth-3
In reply to this post by Nai XIA
On Tue, 2006-05-23 at 13:32 +0800, Nai Xia wrote:

> On Monday 22 May 2006 22:22, Andrew Lenharth wrote:
> > On Mon, 2006-05-22 at 15:33 +0800, 澶忎竴姘� wrote:
> > > But my code does not always works: if the arguments are not pointer,
> > > CompleteBUDataStructures not records it. So, if you want to find all indirect
> > > calls, you maybe have to repair CompleteBUDataStructures. :)
> >
> > Not surprising, CBU is trying to do something entirely different that
> > what you are.
> >
> > > If you do not use BUDataStructures, you can do it yourself: find all load/store
> > > instructions with its destination is function type.
> >
> > You may want to look at how the call graph builder works.  It finds all
> > indirect call sites, and also finds all functions whose address escapes
> > (this is, may be called indirectly).
>
>   The BasicCallGraph class only lines out the indirect calls(makes the caller point to external node),
> but do not resolves them using alias analysis such as DSA.
> I think DSA solve this problem for interested call sites by finding the corresponding globals(i.e. the functions)
> for the callsite DSnode. Maybe 夏一民 just wanted to point out that DSA does not take all callsite into count.
> But just as suggested in callgraph.h, "As an extension in the future, there may be multiple nodes with a null
> function.  These will be used when we can prove (through pointer analysis) that an indirect call site can
> call only a specific set of functions."

First, if you want call site information, you need TD not BU.  Second,
TD still isn't perfect.  I have a series of patches that improve DSA's
indirect call handling, but they are ugly and not yet ready for
incorporation into mainline.  If you really want to try them I can send
you patches, or you can check out my monotone tree.

I also have some clients of the TD call graph that make use of it (well
make use of the Global list in the function pointer's DSNode), such as a
devirtualizer.  Again, I can send you a copy or you can checkout my
tree.

Andrew


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Indirect function call

Nai XIA
On Tuesday 23 May 2006 23:11, Andrew Lenharth wrote:

> On Tue, 2006-05-23 at 13:32 +0800, Nai Xia wrote:
> > On Monday 22 May 2006 22:22, Andrew Lenharth wrote:
> > > On Mon, 2006-05-22 at 15:33 +0800, 婢跺繋绔村锟� wrote:
> > > > But my code does not always works: if the arguments are not pointer,
> > > > CompleteBUDataStructures not records it. So, if you want to find all indirect
> > > > calls, you maybe have to repair CompleteBUDataStructures. :)
> > >
> > > Not surprising, CBU is trying to do something entirely different that
> > > what you are.
> > >
> > > > If you do not use BUDataStructures, you can do it yourself: find all load/store
> > > > instructions with its destination is function type.
> > >
> > > You may want to look at how the call graph builder works.  It finds all
> > > indirect call sites, and also finds all functions whose address escapes
> > > (this is, may be called indirectly).
> >
> >   The BasicCallGraph class only lines out the indirect calls(makes the caller point to external node),
> > but do not resolves them using alias analysis such as DSA.
> > I think DSA solve this problem for interested call sites by finding the corresponding globals(i.e. the functions)
> > for the callsite DSnode. Maybe 澶忎竴姘� just wanted to point out that DSA does not take all callsite into count.
> > But just as suggested in callgraph.h, "As an extension in the future, there may be multiple nodes with a null
> > function.  These will be used when we can prove (through pointer analysis) that an indirect call site can
> > call only a specific set of functions."
>
> First, if you want call site information, you need TD not BU.  Second,
> TD still isn't perfect.  I have a series of patches that improve DSA's
> indirect call handling, but they are ugly and not yet ready for
> incorporation into mainline.  If you really want to try them I can send
> you patches, or you can check out my monotone tree.
>
> I also have some clients of the TD call graph that make use of it (well
> make use of the Global list in the function pointer's DSNode), such as a
> devirtualizer.  Again, I can send you a copy or you can checkout my
> tree.
That would be great! Unfortunately, I did not find your personal cvs in your homepage.
So could you tell me your cvs entry and please point out briefly those codes in interest?
Of course, It's ok to sent the patches to this email.
Thank you very much !

>
> Andrew
>
>

--
Regards,
Nai

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Re: Indirect function call

Andrew Lenharth-2
In reply to this post by ymxia
On Tue, 2006-05-23 at 03:51, 夏一民 wrote:
> Yes, if we want to determine all indirect call(including function pointers in
> structs, arrays), we should improve DSA to analyze function pointer, and then
> exploit pointing set of function pointer in callgraph analysis. :)

Various people have done this in the past (a DSA based callgraph
analysis).  Try emailing Rob Bocchino.  He's done this in the past and
probably can be convinced to brush off that code and make it work with
the current callgraph interface.

Andrew


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev