llvm dev - Dec 2015 - Finding all pointers to functions

I need to track down all pointers anywhere in a module that could be
pointing to functions (because some of the optimizations I want to do,
require either identifying every use of a function, or conservatively
identifying when such cannot be done).

A starting point is to look at all the global variables:

  for (auto &G : M.globals())
    for (auto &V : G.operands())
      if (auto F = dyn_cast<Function>(V))

Of course, instructions can also refer to functions, both as direct calls
and otherwise:

  for (auto &F : M) {
    for (auto &I : inst_range(F)) {
      for (auto &V : I.operands())
        if (auto F = dyn_cast<Function>(V))

But there are other things as well, for example it seems there is something
called a personality function that can be a pointer to another function, so
need to add that

    if (F.hasPersonalityFn())

It seems there are other things called prefix data and prologue data, which
are pointers to constants, which could contain pointers to functions, so
would need to include those as well.

Am I correct in thinking that prefix data and prologue data will not be
included in the global variables list, so do need special handling?

Could they be recursive? That is, could those constants contain pointers to
other constants... which end up containing pointers to functions... such
that none of the intermediate constant objects are in the global variable
list?

Is there anything else I'm missing?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151222/d1dd5ce0/attachment.html>

Oh, I just came across Function::hasAddressTaken. Maybe I can just use that
instead?

On Tue, Dec 22, 2015 at 5:11 AM, Russell Wallace <russell.wallace at
gmail.com>
wrote:
> I need to track down all pointers anywhere in a module that could be
> pointing to functions (because some of the optimizations I want to do,
> require either identifying every use of a function, or conservatively
> identifying when such cannot be done).
>
> A starting point is to look at all the global variables:
>
>   for (auto &G : M.globals())
>     for (auto &V : G.operands())
>       if (auto F = dyn_cast<Function>(V))
>
> Of course, instructions can also refer to functions, both as direct calls
> and otherwise:
>
>   for (auto &F : M) {
>     for (auto &I : inst_range(F)) {
>       for (auto &V : I.operands())
>         if (auto F = dyn_cast<Function>(V))
>
> But there are other things as well, for example it seems there is
> something called a personality function that can be a pointer to another
> function, so need to add that
>
>     if (F.hasPersonalityFn())
>
> It seems there are other things called prefix data and prologue data,
> which are pointers to constants, which could contain pointers to functions,
> so would need to include those as well.
>
> Am I correct in thinking that prefix data and prologue data will not be
> included in the global variables list, so do need special handling?
>
> Could they be recursive? That is, could those constants contain pointers
> to other constants... which end up containing pointers to functions... such
> that none of the intermediate constant objects are in the global variable
> list?
>
> Is there anything else I'm missing?
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151222/9c6c50dc/attachment.html>

On 12/22/15 4:45 AM, Russell Wallace via llvm-dev wrote:
> Oh, I just came across Function::hasAddressTaken. Maybe I can just use 
> that instead?
You could conservatively assume that any function that has its address 
taken has a pointer to it that escapes into memory or external code.  To 
make things a little more accurate, you could scan the uses of any 
function for which hasAddressTaken() returns true and see if any of its 
uses escapes its function or escapes into memory or external code.  I 
believe hasAddressTaken() returns true if the function is subjected to a 
cast instruction, and functions are often casted if they are used in a 
call that uses a different signature than the function's declared signature.

To get anything more accurate, you'll need to use alias analysis or 
points-to analysis.  DSA tracks function pointers in the heap and can 
tell you whether the function is called from external code. However, 
DSA's accuracy currently suffers if it is run after LLVM's 
optimizations, and the code needs some serious TLC.

Regards,

John Criswell
>
> On Tue, Dec 22, 2015 at 5:11 AM, Russell Wallace 
> <russell.wallace at gmail.com <mailto:russell.wallace at
gmail.com>> wrote:
>
>     I need to track down all pointers anywhere in a module that could
>     be pointing to functions (because some of the optimizations I want
>     to do, require either identifying every use of a function, or
>     conservatively identifying when such cannot be done).
>
>     A starting point is to look at all the global variables:
>
>       for (auto &G : M.globals())
>         for (auto &V : G.operands())
>           if (auto F = dyn_cast<Function>(V))
>
>     Of course, instructions can also refer to functions, both as
>     direct calls and otherwise:
>
>       for (auto &F : M) {
>         for (auto &I : inst_range(F)) {
>           for (auto &V : I.operands())
>             if (auto F = dyn_cast<Function>(V))
>
>     But there are other things as well, for example it seems there is
>     something called a personality function that can be a pointer to
>     another function, so need to add that
>
>         if (F.hasPersonalityFn())
>
>     It seems there are other things called prefix data and prologue
>     data, which are pointers to constants, which could contain
>     pointers to functions, so would need to include those as well.
>
>     Am I correct in thinking that prefix data and prologue data will
>     not be included in the global variables list, so do need special
>     handling?
>
>     Could they be recursive? That is, could those constants contain
>     pointers to other constants... which end up containing pointers to
>     functions... such that none of the intermediate constant objects
>     are in the global variable list?
>
>     Is there anything else I'm missing?
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
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/20151222/c3de204d/attachment.html>

Hi Russell,
> I need to track down all pointers anywhere in a module that could be
pointing to functions (because some of the optimizations I want to do, require
either identifying every use of a function, or conservatively identifying when
such cannot be done).
> 
> A starting point is to look at all the global variables:
> 
>   for (auto &G : M.globals())
>     for (auto &V : G.operands())
>       if (auto F = dyn_cast<Function>(V))
> 
> Of course, instructions can also refer to functions, both as direct calls
and otherwise:
> 
>   for (auto &F : M) {
>     for (auto &I : inst_range(F)) {
>       for (auto &V : I.operands())
>         if (auto F = dyn_cast<Function>(V))
Your code is reminiscent of the traversal logic in tools/verify-uselistorder.

There's a chance you might be able to reuse the ValueMapping class from that
project.

> But there are other things as well, for example it seems there is something
called a personality function that can be a pointer to another function, so need
to add that
> 
>     if (F.hasPersonalityFn())
> 
> It seems there are other things called prefix data and prologue data, which
are pointers to constants, which could contain pointers to functions, so would
need to include those as well.
> 
> Am I correct in thinking that prefix data and prologue data will not be
included in the global variables list, so do need special handling?
Prefix data, prologue data, and function personalities do not need to be
globals.

This will require special handling. The ValueMapping class has good skeleton
code for this.

> Could they be recursive? That is, could those constants contain pointers to
other constants... which end up containing pointers to functions... such that
none of the intermediate constant objects are in the global variable list?
I don't see how this is possible. If it is, we'd need to file a PR
against verify-uselistorder.


best
vedant

Everyone else has said good/important things here, but for the original
problem I'm not quite sure why you were trying to search through to find
the uses, rather than walking the Function's use list?

- David

On Mon, Dec 21, 2015 at 9:11 PM, Russell Wallace via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> I need to track down all pointers anywhere in a module that could be
> pointing to functions (because some of the optimizations I want to do,
> require either identifying every use of a function, or conservatively
> identifying when such cannot be done).
>
> A starting point is to look at all the global variables:
>
>   for (auto &G : M.globals())
>     for (auto &V : G.operands())
>       if (auto F = dyn_cast<Function>(V))
>
> Of course, instructions can also refer to functions, both as direct calls
> and otherwise:
>
>   for (auto &F : M) {
>     for (auto &I : inst_range(F)) {
>       for (auto &V : I.operands())
>         if (auto F = dyn_cast<Function>(V))
>
> But there are other things as well, for example it seems there is
> something called a personality function that can be a pointer to another
> function, so need to add that
>
>     if (F.hasPersonalityFn())
>
> It seems there are other things called prefix data and prologue data,
> which are pointers to constants, which could contain pointers to functions,
> so would need to include those as well.
>
> Am I correct in thinking that prefix data and prologue data will not be
> included in the global variables list, so do need special handling?
>
> Could they be recursive? That is, could those constants contain pointers
> to other constants... which end up containing pointers to functions... such
> that none of the intermediate constant objects are in the global variable
> list?
>
> Is there anything else I'm missing?
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160107/cbf4ed70/attachment.html>

Because that was before I realized that functions keep track of a use list.

On Thu, Jan 7, 2016 at 5:40 PM, David Blaikie <dblaikie at gmail.com>
wrote:
> Everyone else has said good/important things here, but for the original
> problem I'm not quite sure why you were trying to search through to
find
> the uses, rather than walking the Function's use list?
>
> - David
>
> On Mon, Dec 21, 2015 at 9:11 PM, Russell Wallace via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> I need to track down all pointers anywhere in a module that could be
>> pointing to functions (because some of the optimizations I want to do,
>> require either identifying every use of a function, or conservatively
>> identifying when such cannot be done).
>>
>> A starting point is to look at all the global variables:
>>
>>   for (auto &G : M.globals())
>>     for (auto &V : G.operands())
>>       if (auto F = dyn_cast<Function>(V))
>>
>> Of course, instructions can also refer to functions, both as direct
calls
>> and otherwise:
>>
>>   for (auto &F : M) {
>>     for (auto &I : inst_range(F)) {
>>       for (auto &V : I.operands())
>>         if (auto F = dyn_cast<Function>(V))
>>
>> But there are other things as well, for example it seems there is
>> something called a personality function that can be a pointer to
another
>> function, so need to add that
>>
>>     if (F.hasPersonalityFn())
>>
>> It seems there are other things called prefix data and prologue data,
>> which are pointers to constants, which could contain pointers to
functions,
>> so would need to include those as well.
>>
>> Am I correct in thinking that prefix data and prologue data will not be
>> included in the global variables list, so do need special handling?
>>
>> Could they be recursive? That is, could those constants contain
pointers
>> to other constants... which end up containing pointers to functions...
such
>> that none of the intermediate constant objects are in the global
variable
>> list?
>>
>> Is there anything else I'm missing?
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160107/a7e40813/attachment.html>