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 <hubi...@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);
