[RFC] Bare bones of virtual call tracking

Hi,
this patch represents bare bones of what I hope to give me possible targets
of a virtual call.

I basically added One Definition Rule based hash that unify all types that
are same in C++ sense (with LTO many of those are still not merged - I hope
that with few dumps I can improve the merging, too). So every type used in
virtual method declaration gets assigned odr_type entry.

Then I use BINFO_BASE_BINFOS to walk direct bases and produce a type inheritance
graph linking type with its bases but also with its derived types.

So I get:

jan@linux-9ure:~/trunk/build/gcc> ./xgcc -B ./ -O2 devirt-1.C

 type 0: struct A
 defined at: devirt-1.C:7
 methods:
   virtual int A::foo(int)/0
 derived types:
   type 1: struct C
   defined at: devirt-1.C:20
   base odr type ids:  0
   methods:
     virtual int C::foo(int)/2

   type 2: struct B
   defined at: devirt-1.C:14
   base odr type ids:  0
   methods:
     virtual int B::foo(int)/1

I think in future I can also use this for LTO merging (i.e. merge binfos of all
types equivalent by ODR) and perhaps canonical types can be refined to honor
ODR when there is no non-ODR language type of same layout.

Now for single inheritance, I think my work is easy:

I have token and type of the virtual call taken from OBJ_TYPE_REF.  I think
I can just walk my inheritance graph now and on each entry look for method
with given token (I can take it from virtual table, or I can actually
use DECL_VINFO and complette my current partial tracking of them) and put
them into set.  Those should be all possible virtual call targets (defined
in current unit) of the call.

With multiple inheritance I need to adjust offsets.  I assume for every type,
I can simply walk binfos, look for mathing type of the call and look for method
at given token within the binfo.  This will be quadratic.

Other otion would be to track the offsets in my base to derived type link. But
I do not know how to obtain it, since BINFO_BASE_BINFOS do not track them.
Shall I look for TYPE_FIELDs instead? 
Does this approach seem to make sense?

Honza

On 08/12/2013 08:16 AM, Jan Hubicka wrote:
> With multiple inheritance I need to adjust offsets.

It's not clear to me that you need to worry about that in your search. 
A call through a particular vptr can only call overrides that go into a 
vtable that vptr can point to, and you can look up any thunk adjustments 
from the vtable.

> +      /* First skip wrappers that C++ FE puts randomly into types.  */
> +      while (TREE_CODE (t) == TYPE_DECL
> +	     && DECL_ORIGINAL_TYPE (t))

How can you get a decl in your types array?

Jason

> On 08/12/2013 08:16 AM, Jan Hubicka wrote:
> >With multiple inheritance I need to adjust offsets.
> 
> It's not clear to me that you need to worry about that in your
> search. A call through a particular vptr can only call overrides
> that go into a vtable that vptr can point to, and you can look up
> any thunk adjustments from the vtable.

What I think I need to worry about is the case, where I have
type A with a virtual method FOO.  I have call of FOO.
Now I have type B that inherits A with non-zero offset and overwrites
method FOO to FOO2.  

Now call to FOO can be either FOO or FOO2, since someone can make
object of type B and cast it back to A. 
How can look it up in B's representation?
> 
> >+      /* First skip wrappers that C++ FE puts randomly into types.  */
> >+      while (TREE_CODE (t) == TYPE_DECL
> >+	     && DECL_ORIGINAL_TYPE (t))
> 
> How can you get a decl in your types array?

Hmm, I am not sure if I can ;) I just copied the ODR code from tree.c.
Basically I start with RECORD_TYPE or so, look for TYPE_NAME that gives
me a type decl whose name is identifier. I hash it and recursively look
for context.  I am not 100% sure what I can find in the contextes.
For sure there can be namespaces.

One thing I noticed is that I get multiple instances of same type in my
hash in LTO. It seems to be because TYPE_CANONICAL differs.  I wonder
what of LTO type merging of TYPE_CANONICAl can mismatch with C++ style
ODR.

Honza
> 
> Jason

> > On 08/12/2013 08:16 AM, Jan Hubicka wrote:
> > >With multiple inheritance I need to adjust offsets.
> > 
> > It's not clear to me that you need to worry about that in your
> > search. A call through a particular vptr can only call overrides
> > that go into a vtable that vptr can point to, and you can look up
> > any thunk adjustments from the vtable.
> 
> What I think I need to worry about is the case, where I have
> type A with a virtual method FOO.  I have call of FOO.
> Now I have type B that inherits A with non-zero offset and overwrites
> method FOO to FOO2.  
> 
> Now call to FOO can be either FOO or FOO2, since someone can make
> object of type B and cast it back to A. 
> How can look it up in B's representation?
> > 
> > >+      /* First skip wrappers that C++ FE puts randomly into types.  */
> > >+      while (TREE_CODE (t) == TYPE_DECL
> > >+	     && DECL_ORIGINAL_TYPE (t))
> > 
> > How can you get a decl in your types array?
> 
> Hmm, I am not sure if I can ;) I just copied the ODR code from tree.c.

OK, I don't visit TYPE_DECLs, at least for Mozilla's javascript shell.  I will
remove the code and keep sanity check.  Perhaps it can be dropped from tree.c'
ODR handling too, then.
> 
> One thing I noticed is that I get multiple instances of same type in my
> hash in LTO. It seems to be because TYPE_CANONICAL differs.  I wonder
> what of LTO type merging of TYPE_CANONICAl can mismatch with C++ style
> ODR.

And this was a stupid bug.  Always initialize your initial hash value 
when you hash everything incrementally ;))

Honza
> 
> Honza
> > 
> > Jason

It might be more flexible to represent the analysis results as a
type/inheritance graph -- i.e. explicitly introduce inheritance edge
class to capture the interitence relationship (offset, etc) between
two class nodes. The 'method' should probably be augmented to include
vtable slot index info. Inherited (not overridden) methods do not need
to represented in the derived type node etc.

thanks,

David

On Mon, Aug 12, 2013 at 5:16 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
> Hi,
> this patch represents bare bones of what I hope to give me possible targets
> of a virtual call.
>
> I basically added One Definition Rule based hash that unify all types that
> are same in C++ sense (with LTO many of those are still not merged - I hope
> that with few dumps I can improve the merging, too). So every type used in
> virtual method declaration gets assigned odr_type entry.
>
> Then I use BINFO_BASE_BINFOS to walk direct bases and produce a type inheritance
> graph linking type with its bases but also with its derived types.
>
> So I get:
>
> jan@linux-9ure:~/trunk/build/gcc> ./xgcc -B ./ -O2 devirt-1.C
>
>  type 0: struct A
>  defined at: devirt-1.C:7
>  methods:
>    virtual int A::foo(int)/0
>  derived types:
>    type 1: struct C
>    defined at: devirt-1.C:20
>    base odr type ids:  0
>    methods:
>      virtual int C::foo(int)/2
>
>    type 2: struct B
>    defined at: devirt-1.C:14
>    base odr type ids:  0
>    methods:
>      virtual int B::foo(int)/1
>
> I think in future I can also use this for LTO merging (i.e. merge binfos of all
> types equivalent by ODR) and perhaps canonical types can be refined to honor
> ODR when there is no non-ODR language type of same layout.
>
> Now for single inheritance, I think my work is easy:
>
> I have token and type of the virtual call taken from OBJ_TYPE_REF.  I think
> I can just walk my inheritance graph now and on each entry look for method
> with given token (I can take it from virtual table, or I can actually
> use DECL_VINFO and complette my current partial tracking of them) and put
> them into set.  Those should be all possible virtual call targets (defined
> in current unit) of the call.
>
> With multiple inheritance I need to adjust offsets.  I assume for every type,
> I can simply walk binfos, look for mathing type of the call and look for method
> at given token within the binfo.  This will be quadratic.
>
> Other otion would be to track the offsets in my base to derived type link. But
> I do not know how to obtain it, since BINFO_BASE_BINFOS do not track them.
> Shall I look for TYPE_FIELDs instead?
> Does this approach seem to make sense?
>
> Honza
>
> Index: Makefile.in
> ===================================================================
> --- Makefile.in (revision 201654)
> +++ Makefile.in (working copy)
> @@ -1275,6 +1275,7 @@
>         init-regs.o \
>         internal-fn.o \
>         ipa-cp.o \
> +       ipa-devirt.o \
>         ipa-split.o \
>         ipa-inline.o \
>         ipa-inline-analysis.o \
> @@ -2945,6 +2946,10 @@
>     $(TREE_PASS_H) $(GIMPLE_H) $(TARGET_H) $(GGC_H) pointer-set.h \
>     $(IPA_UTILS_H) tree-inline.h $(HASH_TABLE_H) profile.h $(PARAMS_H) \
>     $(LTO_STREAMER_H) $(DATA_STREAMER_H)
> +ipa-devirt.o : ipa-devirt.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(CGRAPH_H) \
> +   $(TREE_PASS_H) $(GIMPLE_H) $(TARGET_H) $(GGC_H) pointer-set.h \
> +   $(IPA_UTILS_H) tree-inline.h $(HASH_TABLE_H) profile.h $(PARAMS_H) \
> +   $(LTO_STREAMER_H) $(DATA_STREAMER_H)
>  ipa-prop.o : ipa-prop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
>     langhooks.h $(GGC_H) $(TARGET_H) $(CGRAPH_H) $(IPA_PROP_H) $(DIAGNOSTIC_H) \
>     $(TREE_FLOW_H) $(TM_H) $(TREE_PASS_H) $(FLAGS_H) $(TREE_H) \
> Index: ipa-devirt.c
> ===================================================================
> --- ipa-devirt.c        (revision 0)
> +++ ipa-devirt.c        (working copy)
> @@ -0,0 +1,267 @@
> +/* Basic IPA optimizations and utilities.
> +   Copyright (C) 2003-2013 Free Software Foundation, Inc.
> +
> +This file is part of GCC.
> +
> +GCC is free software; you can redistribute it and/or modify it under
> +the terms of the GNU General Public License as published by the Free
> +Software Foundation; either version 3, or (at your option) any later
> +version.
> +
> +GCC is distributed in the hope that it will be useful, but WITHOUT ANY
> +WARRANTY; without even the implied warranty of MERCHANTABILITY or
> +FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
> +for more details.
> +
> +You should have received a copy of the GNU General Public License
> +along with GCC; see the file COPYING3.  If not see
> +<http://www.gnu.org/licenses/>.  */
> +
> +#include "config.h"
> +#include "system.h"
> +#include "coretypes.h"
> +#include "tm.h"
> +#include "cgraph.h"
> +#include "tree-pass.h"
> +#include "gimple.h"
> +#include "ggc.h"
> +#include "flags.h"
> +#include "pointer-set.h"
> +#include "target.h"
> +#include "tree-iterator.h"
> +#include "pointer-set.h"
> +#include "hash-table.h"
> +#include "params.h"
> +#include "tree-pretty-print.h"
> +
> +struct odr_type_d
> +{
> +  int id;
> +  vec<tree> types;
> +  pointer_set_t *types_set;
> +  vec<struct odr_type_d *> bases;
> +  vec<struct odr_type_d *> derived_types;
> +  vec<struct cgraph_node *> methods;
> +};
> +
> +typedef odr_type_d *odr_type;
> +
> +/* One Definition Rule hashtable helpers.  */
> +
> +struct odr_hasher
> +{
> +  typedef odr_type_d value_type;
> +  typedef odr_type_d compare_type;
> +  static inline hashval_t hash (const value_type *);
> +  static inline bool equal (const value_type *, const compare_type *);
> +  static inline void remove (value_type *);
> +};
> +
> +/* Return the computed hashcode for ODR_TYPE.  */
> +
> +inline hashval_t
> +odr_hasher::hash (const value_type *odr_type)
> +{
> +  hashval_t hash;
> +  tree t = odr_type->types[0];
> +  while (t)
> +    {
> +      /* First skip wrappers that C++ FE puts randomly into types.  */
> +      while (TREE_CODE (t) == TYPE_DECL
> +            && DECL_ORIGINAL_TYPE (t))
> +        t = DECL_ORIGINAL_TYPE (t);
> +      if (TREE_CODE (t) == TYPE_DECL
> +         && DECL_FILE_SCOPE_P (t))
> +        t = DECL_NAME (t);
> +
> +      /* Hash the names.  */
> +      if (TREE_CODE (t) == IDENTIFIER_NODE)
> +       hash = iterative_hash_hashval_t (hash, htab_hash_pointer (t));
> +      else if (DECL_P (t))
> +        {
> +         gcc_checking_assert (TREE_CODE (DECL_NAME (t)) == IDENTIFIER_NODE);
> +         hash = iterative_hash_hashval_t (hash, htab_hash_pointer (DECL_NAME (t)));
> +         t = DECL_CONTEXT (t);
> +        }
> +
> +      /* Look into type names.  */
> +      else if (TYPE_P (t))
> +       {
> +         t = TYPE_MAIN_VARIANT (t);
> +
> +         /* Anonymous namespaces must be unique.  */
> +         if (TYPE_STUB_DECL (t) && !!TREE_PUBLIC (TYPE_STUB_DECL (t)))
> +           return iterative_hash_hashval_t (hash, htab_hash_pointer (TYPE_STUB_DECL (t)));
> +         /* Skip internal types.  */
> +         if (TYPE_NAME (t))
> +           {
> +             gcc_assert (TREE_CODE (DECL_NAME (TYPE_NAME (t))) == IDENTIFIER_NODE);
> +             hash = iterative_hash_hashval_t (hash, htab_hash_pointer (DECL_NAME (TYPE_NAME (t))));
> +           }
> +         t = TYPE_CONTEXT (t);
> +       }
> +    }
> +  return hash;
> +}
> +
> +/* Compare types operations T1 and T2 and return true if they are
> +   equivalent.  */
> +
> +inline bool
> +odr_hasher::equal (const value_type *t1, const compare_type *t2)
> +{
> +  if (t1->types[0] == t2->types[0])
> +    return true;
> +  return types_same_for_odr (t1->types[0], t2->types[0]);
> +}
> +
> +/* Free a phi operation structure VP.  */
> +
> +inline void
> +odr_hasher::remove (value_type *v)
> +{
> +  v->types.release ();
> +  v->bases.release ();
> +  v->methods.release ();
> +  free (v);
> +}
> +
> +/* ODR type hash.  */
> +typedef hash_table <odr_hasher> odr_hash_type;
> +odr_hash_type odr_hash;
> +vec <odr_type> odr_types;
> +
> +/* Get ODR type hash entry for TYPE.  */
> +odr_type
> +get_odr_type (tree type)
> +{
> +  odr_type_d key;
> +  odr_type_d **slot;
> +  odr_type val;
> +
> +  type = TYPE_MAIN_VARIANT (type);
> +  key.types = vNULL;
> +  key.types.safe_push (type);
> +  slot = odr_hash.find_slot (&key, INSERT);
> +  if (*slot)
> +    {
> +      val = *slot;
> +      key.types.release ();
> +      if (!pointer_set_contains (val->types_set, type))
> +       {
> +         gcc_assert (in_lto_p);
> +         val->types.safe_push (type);
> +         pointer_set_insert (val->types_set, type);
> +       }
> +    }
> +  else
> +    {
> +      tree binfo = TYPE_BINFO (type);
> +      unsigned int i;
> +
> +      val = XNEW (odr_type_d);
> +      val->types = key.types;
> +      val->types_set = pointer_set_create ();
> +      val->bases = vNULL;
> +      val->derived_types = vNULL;
> +      val->methods = vNULL;
> +      pointer_set_insert (val->types_set, type);
> +      *slot = val;
> +      for (i = 0; i < BINFO_N_BASE_BINFOS (binfo); i++)
> +       {
> +         odr_type base = get_odr_type (BINFO_TYPE (BINFO_BASE_BINFO (binfo, i)));
> +         base->derived_types.safe_push (val);
> +         val->bases.safe_push (base);
> +       }
> +      /* First record bases, then add into array so ids are increasing.  */
> +      val->id = odr_types.length();
> +      odr_types.safe_push (val);
> +    }
> +  return val;
> +}
> +
> +void
> +dump_odr_type (FILE *f, odr_type t, int indent=0)
> +{
> +  unsigned int i;
> +  fprintf (f, "%*s type %i: ", indent * 2, "", t->id);
> +  print_generic_expr (f, t->types[0], TDF_SLIM);
> +  fprintf (f, "\n");
> +  if (TYPE_NAME (t->types[0]))
> +    {
> +      fprintf (f, "%*s defined at: %s:%i\n", indent * 2, "",
> +              DECL_SOURCE_FILE (TYPE_NAME (t->types[0])),
> +              DECL_SOURCE_LINE (TYPE_NAME (t->types[0])));
> +    }
> +  if (t->bases.length())
> +    {
> +      fprintf (f, "%*s base odr type ids: ", indent * 2, "");
> +      for (i = 0; i < t->bases.length(); i++)
> +       fprintf (f, " %i", t->bases[i]->id);
> +      fprintf (f, "\n");
> +    }
> +  if (t->methods.length())
> +    {
> +      fprintf (f, "%*s methods:\n", indent * 2, "");
> +      for (i = 0; i < t->methods.length(); i++)
> +       fprintf (f, "  %*s %s/%i\n", indent * 2, "",
> +                cgraph_node_name (t->methods[i]),
> +                t->methods[i]->symbol.order);
> +    }
> +  if (t->derived_types.length())
> +    {
> +      fprintf (f, "%*s derived types:\n", indent * 2, "");
> +      for (i = 0; i < t->derived_types.length(); i++)
> +        dump_odr_type (f, t->derived_types[i], indent + 1);
> +    }
> +  fprintf (f, "\n");
> +}
> +
> +void
> +dump_odrs (FILE *f)
> +{
> +  unsigned int i;
> +  for (i = 0; i < odr_types.length(); i++)
> +    {
> +      if (odr_types[i]->bases.length() == 0)
> +       dump_odr_type (f, odr_types[i]);
> +    }
> +  for (i = 0; i < odr_types.length(); i++)
> +    {
> +      if (odr_types[i]->types.length() > 1)
> +       {
> +         int j;
> +         fprintf (f, "Duplicate tree types for odr type %i\n", i);
> +         for (j = 0; i < odr_types[i]->types.length(); j++)
> +           {
> +             print_node (dump_file, "", odr_types[i]->types[j], 0);
> +             putc ('\n', stderr);
> +           }
> +       }
> +    }
> +}
> +
> +/* Given method type T, return type of class it belongs to.
> +   Lookup this pointer and get its type.    */
> +tree
> +method_class_type (tree t)
> +{
> +  tree first_parm_type = TREE_VALUE (TYPE_ARG_TYPES (t));
> +  return TREE_TYPE (first_parm_type);
> +}
> +
> +void
> +ipa_devirt_init (void)
> +{
> +  struct cgraph_node *n;
> +
> +  if (odr_hash.is_created ())
> +    return;
> +  odr_hash.create (23);
> +  odr_types = vNULL;
> +  FOR_EACH_FUNCTION (n)
> +    if (DECL_VIRTUAL_P (n->symbol.decl)
> +       && symtab_real_symbol_p ((symtab_node)n))
> +      get_odr_type (method_class_type (TREE_TYPE (n->symbol.decl)))->methods.safe_push (n);
> +  dump_odrs (stderr);
> +}
> Index: ipa.c
> ===================================================================
> --- ipa.c       (revision 201654)
> +++ ipa.c       (working copy)
> @@ -225,6 +225,7 @@
>  #endif
>    if (file)
>      fprintf (file, "\nReclaiming functions:");
> +  ipa_devirt_init ();
>  #ifdef ENABLE_CHECKING
>    FOR_EACH_FUNCTION (node)
>      gcc_assert (!node->symbol.aux);

> It might be more flexible to represent the analysis results as a
> type/inheritance graph -- i.e. explicitly introduce inheritance edge
> class to capture the interitence relationship (offset, etc) between
> two class nodes. The 'method' should probably be augmented to include

Yep, that is general goal. I simply have vectors to represent edges in the
graph, but adding offset is on my TODO.

> vtable slot index info. Inherited (not overridden) methods do not need
> to represented in the derived type node etc.

Isn't it what DECL_VINDEX is supposed to give me?

Honza

Jason,
I introduced an warning on ODR violations (i.e. when I hot two types that are
equivalent by my ODR code and have different canonical types). Unforutnately
this hits a false positives on template instantiations.  Here my ODR code
apparently never sees the types of template parameters; just the template
name itself that is same for all instances.

I suppose I need to walk those, too.  Is there language independent way to get
to C++ template parameters? (dwarf2out seems to use langhook) and if not, would
be possible to introduce one?

Also it would help if the FINAL flag on methods and classes was made language
independent.

Thank you,
Honza