From patchwork Wed Aug 21 23:08:31 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 268910 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "localhost", Issuer "www.qmailtoaster.com" (not verified)) by ozlabs.org (Postfix) with ESMTPS id 40FDE2C00B9 for ; Thu, 22 Aug 2013 09:08:45 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=MtzNjnCVvJidkNVlJYvF6Oc+L2uT09Gdoln9eOsFDH1iTqld/2x8o X+LbKcSHcfFpg8xW6mGhmEQ9eZ2aVPbQWg7lplzmR02yAQ0/Xt688VMEhIglNKGR jK15WLj6GLrOf86mHKbVjt8LTOCx5sGUCt57YHz0Z07EaSMhlTupOQ= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=l9dZ68AEcTze6kQVP/d+yTS5OuM=; b=my+hnWYPwFfEuykvq7kZ 5a8vvQo1j8kv4l6GL6eecEqNeg9l5SHB+X+roiRVPhDmzB0A1usyaV/pi6SCP+QA sicVlH0vPFCeHg56kDSvsGnlsdoj/fMfRZcPzQ49EF4xatKOE2lpkkBfFuaTNk1t zfnsY+uIat8o78LpJYZnX8Y= Received: (qmail 29587 invoked by alias); 21 Aug 2013 23:08:37 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 29572 invoked by uid 89); 21 Aug 2013 23:08:37 -0000 X-Spam-SWARE-Status: No, score=-5.4 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_NO, RCVD_IN_HOSTKARMA_W, RCVD_IN_HOSTKARMA_WL, RP_MATCHES_RCVD autolearn=ham version=3.3.2 Received: from nikam.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Wed, 21 Aug 2013 23:08:34 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id 71714542F69; Thu, 22 Aug 2013 01:08:31 +0200 (CEST) Date: Thu, 22 Aug 2013 01:08:31 +0200 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, dodji@seketeli.org Subject: ipa-devirt.c TLC Message-ID: <20130821230831.GD16124@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-06-14) Hi, this patch fixes some issues with ipa-devirt I noticed since the initial commit. 1) I added fixes and comments Doji suggested (thanks!) 2) During the callgraph construction new external nodes may be created that needs to be added into the inheritance graph get more complette andwers from possible_polymorphic_call_targets. While the answer is never complette for external functions, it is better to have more of them than fewer so speculation is not trying to work too hard. I added function that collects all new nodes into the graph. 3) I merged in flag for anonymous_namespace types, but forgot to initialize it (it is used to decide if set of targets is complette and I am not using that flag in mainline ATM) 4) Added possible_polymorphic_call_target_p that can be used for sanity checking of devirtualization machinery. The testing now passes firefox and couple other testcases, but I will submit the verification bits separately of this change. 5) -fdump-ipa-type-inheritance ICEs when there are no polynmorphic types. 6) I managed to get call target cache wrong in a way that is is never freed on node removal as it is supposed to. Bootstrapped/regtested ppc64-linux, will commit it tomorrow if there are no complains and x86_64-linux testing completes. Honza * cgraphunit.c (analyze_functions) Use update_type_inheritance_graph. * ipa-utils.h (update_type_inheritance_graph): Declare. (possible_polymorphic_call_target_p): Declare. (possible_polymorphic_call_target_p): New. * ipa-devirt.c: Update toplevel comments. (cached_polymorphic_call_targets): Move up. (odr_type_d): Move ID down. (polymorphic_type_binfo_p): Update comment. (odr_hasher::remove): Likewise; (get_odr_type): Set anonymous_namespace. (dump_odr_type): Dump it. (dump_type_inheritance_graph): Do not ICE when there are no ODR types. (maybe_record_node): Record node in cached_polymorphic_call_targets. (record_binfo): Add comment. (free_polymorphic_call_targets_hash): Do not ICE when cache is not built. (devirt_node_removal_hook): Do not iCE when cache is freed. (possible_polymorphic_call_target_p): New predicate. (update_type_inheritance_graph): New function. Index: cgraphunit.c =================================================================== --- cgraphunit.c (revision 201899) +++ cgraphunit.c (working copy) @@ -976,6 +976,8 @@ analyze_functions (void) cgraph_process_new_functions (); } } + if (optimize && flag_devirtualize) + update_type_inheritance_graph (); /* Collect entry points to the unit. */ if (cgraph_dump_file) Index: ipa-utils.h =================================================================== --- ipa-utils.h (revision 201899) +++ ipa-utils.h (working copy) @@ -50,12 +50,15 @@ tree get_base_var (tree); struct odr_type_d; typedef odr_type_d *odr_type; void build_type_inheritance_graph (void); +void update_type_inheritance_graph (void); vec possible_polymorphic_call_targets (tree, HOST_WIDE_INT, bool *final = NULL, void **cache_token = NULL); odr_type get_odr_type (tree, bool insert = false); void dump_possible_polymorphic_call_targets (FILE *, tree, HOST_WIDE_INT); +bool possible_polymorphic_call_target_p (tree, HOST_WIDE_INT, + struct cgraph_node *n); /* Return vector containing possible targets of polymorphic call E. If FINALP is non-NULL, store true if the list is complette. @@ -87,6 +90,17 @@ dump_possible_polymorphic_call_targets ( dump_possible_polymorphic_call_targets (f, e->indirect_info->otr_type, e->indirect_info->otr_token); } + +/* Return true if N can be possibly target of a polymorphic call of + E. */ + +inline bool +possible_polymorphic_call_target_p (struct cgraph_edge *e, + struct cgraph_node *n) +{ + return possible_polymorphic_call_target_p (e->indirect_info->otr_type, + e->indirect_info->otr_token, n); +} #endif /* GCC_IPA_UTILS_H */ Index: ipa-devirt.c =================================================================== --- ipa-devirt.c (revision 201899) +++ ipa-devirt.c (working copy) @@ -37,10 +37,10 @@ along with GCC; see the file COPYING3. names and types are the same. OTR = OBJ_TYPE_REF - This is Gimple representation of type information of a polymorphic call. + This is the Gimple representation of type information of a polymorphic call. It contains two parameters: otr_type is a type of class whose method is called. - otr_token is index into virtual table where address is taken. + otr_token is the index into virtual table where address is taken. BINFO This is the type inheritance information attached to each tree @@ -55,7 +55,7 @@ along with GCC; see the file COPYING3. vector. Members of this vectors are not BINFOs associated with a base type. Rather they are new copies of BINFOs (base BINFOs). Their virtual tables may differ from - virtual table of the base type. Also BINFO_OFFSET specify + virtual table of the base type. Also BINFO_OFFSET specifies offset of the base within the type. In the case of single inheritance, the virtual table is shared @@ -72,7 +72,7 @@ along with GCC; see the file COPYING3. token This is an index of virtual method in virtual table associated to the type defining it. Token can be looked up from OBJ_TYPE_REF - or from DECL_VINDEX of given virtual table. + or from DECL_VINDEX of a given virtual table. polymorphic (indirect) call This is callgraph represention of virtual method call. Every @@ -86,7 +86,7 @@ along with GCC; see the file COPYING3. We reconstruct it based on types of methods we see in the unit. This means that the graph is not complete. Types with no methods are not - inserted to the graph. Also types without virtual methods are not + inserted into the graph. Also types without virtual methods are not represented at all, though it may be easy to add this. The inheritance graph is represented as follows: @@ -95,7 +95,7 @@ along with GCC; see the file COPYING3. to one or more tree type nodes that are equivalent by ODR rule. (the multiple type nodes appear only with linktime optimization) - Edges are repsented by odr_type->base and odr_type->derived_types. + Edges are represented by odr_type->base and odr_type->derived_types. At the moment we do not track offsets of types for multiple inheritance. Adding this is easy. @@ -117,26 +117,36 @@ along with GCC; see the file COPYING3. #include "ipa-utils.h" #include "gimple.h" +/* Pointer set of all call targets appearing in the cache. */ +static pointer_set_t *cached_polymorphic_call_targets; + /* The node of type inheritance graph. For each type unique in One Defintion Rule (ODR) sense, we produce one node linking all main variants of types equivalent to it, bases and derived types. */ struct GTY(()) odr_type_d { - /* Unique ID indexing the type in odr_types array. */ - int id; /* leader type. */ tree type; /* All bases. */ vec GTY((skip)) bases; /* All derrived types with virtual methods seen in unit. */ vec GTY((skip)) derived_types; + + /* Unique ID indexing the type in odr_types array. */ + int id; /* Is it in anonymous namespace? */ bool anonymous_namespace; }; -/* Return true if BINFO corresponds to a type with virtual methods. */ +/* Return true if BINFO corresponds to a type with virtual methods. + + Every type has several BINFOs. One is the BINFO associated by the type + while other represents bases of derived types. The BINFOs representing + bases do not have BINFO_VTABLE pointer set when this is the single + inheritance (because vtables are shared). Look up the BINFO of type + and check presence of its vtable. */ static inline bool polymorphic_type_binfo_p (tree binfo) @@ -184,7 +194,7 @@ odr_hasher::hash (const value_type *odr_ return hash_type_name (odr_type->type); } -/* Compare types operations T1 and T2 and return true if they are +/* Compare types T1 and T2 and return true if they are equivalent. */ inline bool @@ -200,13 +210,13 @@ odr_hasher::equal (const value_type *t1, return types_same_for_odr (t1->type, t2); } -/* Free a phi operation structure VP. */ +/* Free ODR type V. */ inline void odr_hasher::remove (value_type *v) { v->bases.release (); v->derived_types.release (); ggc_free (v); } @@ -259,6 +271,7 @@ get_odr_type (tree type, bool insert) val->type = type; val->bases = vNULL; val->derived_types = vNULL; + val->anonymous_namespace = type_in_anonymous_namespace_p (type); *slot = val; for (i = 0; i < BINFO_N_BASE_BINFOS (binfo); i++) /* For now record only polymorphic types. other are @@ -289,7 +302,7 @@ dump_odr_type (FILE *f, odr_type t, int unsigned int i; fprintf (f, "%*s type %i: ", indent * 2, "", t->id); print_generic_expr (f, t->type, TDF_SLIM); - fprintf (f, "\n"); + fprintf (f, "%s\n", t->anonymous_namespace ? " (anonymous namespace)":""); if (TYPE_NAME (t->type)) { fprintf (f, "%*s defined at: %s:%i\n", indent * 2, "", @@ -318,6 +331,8 @@ static void dump_type_inheritance_graph (FILE *f) { unsigned int i; + if (!odr_types_ptr) + return; fprintf (f, "\n\nType inheritance graph:\n"); for (i = 0; i < odr_types.length(); i++) { @@ -383,7 +398,11 @@ maybe_record_node (vec & && !pointer_set_insert (inserted, target) && (target_node = cgraph_get_node (target)) != NULL && symtab_real_symbol_p ((symtab_node)target_node)) - nodes.safe_push (target_node); + { + pointer_set_insert (cached_polymorphic_call_targets, + target_node); + nodes.safe_push (target_node); + } } /* See if BINFO's type match OTR_TYPE. If so, lookup method @@ -430,6 +449,8 @@ record_binfo (vec &nodes /* Walking bases that have no virtual method is pointless excercise. */ if (polymorphic_type_binfo_p (base_binfo)) record_binfo (nodes, base_binfo, otr_type, + /* In the case of single inheritance, the virtual table + is shared with the outer type. */ BINFO_VTABLE (base_binfo) ? base_binfo : type_binfo, otr_token, inserted, matched_vtables); @@ -517,16 +538,18 @@ polymorphic_call_target_hasher::remove ( typedef hash_table polymorphic_call_target_hash_type; static polymorphic_call_target_hash_type polymorphic_call_target_hash; -pointer_set_t *cached_polymorphic_call_targets; /* Destroy polymorphic call target query cache. */ static void free_polymorphic_call_targets_hash () { - polymorphic_call_target_hash.dispose (); - pointer_set_destroy (cached_polymorphic_call_targets); - cached_polymorphic_call_targets = NULL; + if (cached_polymorphic_call_targets) + { + polymorphic_call_target_hash.dispose (); + pointer_set_destroy (cached_polymorphic_call_targets); + cached_polymorphic_call_targets = NULL; + } } /* When virtual function is removed, we may need to flush the cache. */ @@ -534,7 +557,8 @@ free_polymorphic_call_targets_hash () static void devirt_node_removal_hook (struct cgraph_node *n, void *d ATTRIBUTE_UNUSED) { - if (pointer_set_contains (cached_polymorphic_call_targets, n)) + if (cached_polymorphic_call_targets + && pointer_set_contains (cached_polymorphic_call_targets, n)) free_polymorphic_call_targets_hash (); } @@ -663,4 +687,47 @@ dump_possible_polymorphic_call_targets ( fprintf (f, "\n"); } + +/* Return true if N can be possibly target of a polymorphic call of + OTR_TYPE/OTR_TOKEN. */ + +bool +possible_polymorphic_call_target_p (tree otr_type, + HOST_WIDE_INT otr_token, + struct cgraph_node *n) +{ + vec targets; + unsigned int i; + + if (!odr_hash.is_created ()) + return true; + targets = possible_polymorphic_call_targets (otr_type, otr_token); + for (i = 0; i < targets.length (); i++) + if (n == targets[i]) + return true; + return false; +} + + +/* After callgraph construction new external nodes may appear. + Add them into the graph. */ + +void +update_type_inheritance_graph (void) +{ + struct cgraph_node *n; + + if (!odr_hash.is_created ()) + return; + free_polymorphic_call_targets_hash (); + timevar_push (TV_IPA_INHERITANCE); + /* We reconstruct the graph starting of types of all methods seen in the + the unit. */ + FOR_EACH_FUNCTION (n) + if (DECL_VIRTUAL_P (n->symbol.decl) + && !n->symbol.definition + && symtab_real_symbol_p ((symtab_node)n)) + get_odr_type (method_class_type (TREE_TYPE (n->symbol.decl)), true); + timevar_pop (TV_IPA_INHERITANCE); +} #include "gt-ipa-devirt.h"