From patchwork Mon Aug 12 18:08:04 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 266605 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 08EFA2C011D for ; Tue, 13 Aug 2013 04:08:19 +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:cc:subject:message-id:references:mime-version :content-type:in-reply-to; q=dns; s=default; b=d9G4uIwNIkIAH467z Nv/Sp06rEKUYhS6daR8o69P7/5zQ+wXYmB64wpwPGjCFg9O2dk77NUm8syFl1yE9 dn6TEM7xvq2QLlc49cbuhWskhrZ/8+wdeW/p7KNWBKMisTP9OCbIE5jykmuZyW01 VH590Z7OJjQYuFfxlg+T/+yJU0= 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:cc:subject:message-id:references:mime-version :content-type:in-reply-to; s=default; bh=8WTAc8bNfI4JYupaUHkRzNe 7rO4=; b=VmH5RDJiBpp3InqvIyayRlpsJ35iiudNDxCOapz+FtXXbbFPLyv0JBy /tcqydU5gHXVLmWd5+FWQonLnvlv9d6HlrEA26eMyNX7K3yf4ENhj8W7ImGjJdks wkRZFrsJXAz9ut6hwyyh2erxsqsH1wy8VartF7xc5qwtk/Ou4o8w= Received: (qmail 382 invoked by alias); 12 Aug 2013 18:08:10 -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 365 invoked by uid 89); 12 Aug 2013 18:08:09 -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; Mon, 12 Aug 2013 18:08:07 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id A51B3542FE1; Mon, 12 Aug 2013 20:08:04 +0200 (CEST) Date: Mon, 12 Aug 2013 20:08:04 +0200 From: Jan Hubicka To: Jan Hubicka Cc: Jason Merrill , gcc-patches@gcc.gnu.org, mjambor@suse.cz Subject: Re: [RFC] Bare bones of virtual call tracking Message-ID: <20130812180804.GA7579@kam.mff.cuni.cz> References: <20130812121624.GF22678@kam.mff.cuni.cz> <5208FF6C.3060408@redhat.com> <20130812162159.GB17776@kam.mff.cuni.cz> <20130812164332.GC17776@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20130812164332.GC17776@kam.mff.cuni.cz> User-Agent: Mutt/1.5.20 (2009-06-14) Hi, I guess I understand you now about the offsets. I do not need to update token, right? Here is updated and somewhat more complette patch (now I can get list of possible targets and use it to prune the callgraph) I also added sanity check that ipa-cp devirtualization actually picks one of targets from my list. Honza Index: ipa-devirt.c =================================================================== --- ipa-devirt.c (revision 0) +++ ipa-devirt.c (revision 0) @@ -0,0 +1,359 @@ +/* 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 +. */ + +#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" +#include "diagnostic.h" + +struct odr_type_d +{ + int id; + vec types; + pointer_set_t *types_set; + vec bases; + vec derived_types; + vec 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 = 0; + tree t = odr_type->types[0]; + while (t) + { + gcc_assert (TREE_CODE (t) != TYPE_DECL); + + /* 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. */ + gcc_assert (TYPE_NAME (t)); + 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) +{ + bool same; + if (t1->types[0] == t2->types[0]) + return true; + same = types_same_for_odr (t1->types[0], t2->types[0]); +#if 0 + if (!same + && odr_hasher::hash (t1) == odr_hasher::hash (t2)) + { + TREE_NO_WARNING (t2->types[0]) = 1; + if (TYPE_CANONICAL (t1->types[0]) == TYPE_CANONICAL (t2->types[0])) + fprintf (stderr, "Mismatch\n"); + else + fprintf (stderr, "Canonical Mismatch\n"); + debug_tree (t1->types[0]); + debug_tree (t2->types[0]); + } +#endif + return same; +} + +/* 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_hash_type; +odr_hash_type odr_hash; +vec 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; + hashval_t hash; + + type = TYPE_MAIN_VARIANT (type); + key.types = vNULL; + key.types.safe_push (type); + hash = odr_hasher::hash (&key); + slot = odr_hash.find_slot_with_hash (&key, hash, INSERT); + if (*slot) + { + val = *slot; + key.types.release (); + if (!pointer_set_insert (val->types_set, type)) + { + gcc_assert (in_lto_p); + val->types.safe_push (type); + if (!types_compatible_p (val->types[0], type) + && warning_at (DECL_SOURCE_LOCATION (type), 0, + "type %qD violate one definition rule ", + type)) + inform (DECL_SOURCE_LOCATION (val->types[0]), + "the inconsistent declaration of same name"); + } + } + else + { + tree binfo = TYPE_BINFO (type); + unsigned int i; + + val = XCNEW (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, " hash: %li canonical: %i\n", (long)odr_hasher::hash (t), TYPE_UID (TYPE_CANONICAL (t->types[0]))); + 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) + { + unsigned int j; + fprintf (f, "Duplicate tree types for odr type %i\n", i); + for (j = 0; j < odr_types[i]->types.length(); j++) + { + tree t; + fprintf (f, "duplicate #%i\n", j); + print_node (f, "", odr_types[i]->types[j], 0); + t = odr_types[i]->types[j]; + while (TYPE_P (t) && TYPE_CONTEXT (t)) + { + t = TYPE_CONTEXT (t); + print_node (f, "", t, 0); + } + putc ('\n',f); + } + } + } +} + +/* 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 +possible_virtual_call_targets_1 (vec &nodes, + pointer_set_t *inserted, + tree otr_type, + odr_type type, + HOST_WIDE_INT offset, + HOST_WIDE_INT otr_token) +{ + tree binfo = get_binfo_at_offset (TYPE_BINFO (type->types[0]), + offset, otr_type); + tree target; + struct cgraph_node *target_node; + unsigned int i; + + gcc_assert (binfo); + target = gimple_get_virt_method_for_binfo (otr_token, binfo); + if (target + && (target_node = cgraph_get_node (target)) != NULL + && symtab_real_symbol_p ((symtab_node)target_node) + && !pointer_set_insert (inserted, target_node)) + { + nodes.safe_push (target_node); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " %s/%i\n", + cgraph_node_name (target_node), + target_node->symbol.order); + } + for (i = 0; i < type->derived_types.length(); i++) + possible_virtual_call_targets_1 (nodes, inserted, + otr_type, + type->derived_types[i], + offset, otr_token); +} + +vec +possible_virtual_call_targets (tree otr_type, + HOST_WIDE_INT offset, + HOST_WIDE_INT otr_token) +{ + pointer_set_t *inserted = pointer_set_create (); + odr_type type = get_odr_type (otr_type); + vec nodes=vNULL; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Targets for virtual call of type id %i:", type->id); + print_generic_expr (dump_file, otr_type, TDF_SLIM); + fprintf (dump_file, " with offset %i and token %i\n", (int)offset, (int)otr_token); + } + possible_virtual_call_targets_1 (nodes, inserted, otr_type, type, offset, otr_token); + + pointer_set_destroy (inserted); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\n"); + return nodes; +} + +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); +#if 0 + FOR_EACH_FUNCTION (n) + for (e = n->indirect_calls; e; e = e->next_callee) + if (e->indirect_info->polymorphic) + possible_virtual_call_targets (e->indirect_info->otr_type, + e->indirect_info->offset, + e->indirect_info->otr_token); +#endif + if (cgraph_dump_file) + dump_odrs (cgraph_dump_file); +} Index: ipa-utils.h =================================================================== --- ipa-utils.h (revision 201640) +++ ipa-utils.h (working copy) @@ -45,6 +45,9 @@ vec ipa_get_nodes_in_cycle (struct cgraph_node *); int ipa_reverse_postorder (struct cgraph_node **); tree get_base_var (tree); +void ipa_devirt_init (void); +vec +possible_virtual_call_targets (tree, HOST_WIDE_INT, HOST_WIDE_INT); #endif /* GCC_IPA_UTILS_H */ Index: ipa.c =================================================================== --- ipa.c (revision 201640) +++ ipa.c (working copy) @@ -225,6 +225,8 @@ #endif if (file) fprintf (file, "\nReclaiming functions:"); + if (optimize && flag_devirtualize) + ipa_devirt_init (); #ifdef ENABLE_CHECKING FOR_EACH_FUNCTION (node) gcc_assert (!node->symbol.aux); @@ -243,8 +245,8 @@ && !node->symbol.in_other_partition && (!cgraph_can_remove_if_no_direct_calls_and_refs_p (node) /* Keep around virtual functions for possible devirtualization. */ - || (before_inlining_p - && DECL_VIRTUAL_P (node->symbol.decl)))) + /*|| (before_inlining_p + && DECL_VIRTUAL_P (node->symbol.decl))*/)) { gcc_assert (!node->global.inlined_to); pointer_set_insert (reachable, node); @@ -318,7 +320,32 @@ pointer_set_insert (reachable, e->callee); enqueue_node ((symtab_node) e->callee, &first, reachable); } + /* Keep alive possible targets for devirtualization. + Even after inlining we want to keep the possible targets in the boundary, + so late passes can still produce direct call even if chance for inlining + is lost. We however remove the actual function bodies. */ + if (optimize && flag_devirtualize) + for (e = cnode->indirect_calls; e; e = e->next_callee) + if (e->indirect_info->polymorphic) + { + unsigned int i; + vec targets = possible_virtual_call_targets (e->indirect_info->otr_type, + e->indirect_info->offset, + e->indirect_info->otr_token); + for (i = 0; i < targets.length(); i++) + { + struct cgraph_node *n = targets[i]; + if (n->symbol.definition + && before_inlining_p + && (!DECL_EXTERNAL (n->symbol.decl) + || n->symbol.alias)) + pointer_set_insert (reachable, n); + enqueue_node ((symtab_node) n, &first, reachable); + } + targets.release (); + } + /* When inline clone exists, mark body to be preserved so when removing offline copy of the function we don't kill it. */ if (cnode->global.inlined_to) @@ -1407,54 +1430,10 @@ bool something_changed = false; int i; gcov_type overall_time = 0, cutoff = 0, cumulated = 0, overall_size = 0; + struct cgraph_node *n,*n2; + int nindirect = 0, ncommon = 0, nunknown = 0, nuseless = 0, nconverted = 0; + bool node_map_initialized = false; - /* Produce speculative calls: we saved common traget from porfiling into - e->common_target_id. Now, at link time, we can look up corresponding - function node and produce speculative call. */ - if (in_lto_p) - { - struct cgraph_edge *e; - struct cgraph_node *n,*n2; - - init_node_map (false); - FOR_EACH_DEFINED_FUNCTION (n) - { - bool update = false; - - for (e = n->indirect_calls; e; e = e->next_callee) - if (e->indirect_info->common_target_id) - { - n2 = find_func_by_profile_id (e->indirect_info->common_target_id); - if (n2) - { - if (dump_file) - { - fprintf (dump_file, "Indirect call -> direct call from" - " other module %s/%i => %s/%i, prob %3.2f\n", - xstrdup (cgraph_node_name (n)), n->symbol.order, - xstrdup (cgraph_node_name (n2)), n2->symbol.order, - e->indirect_info->common_target_probability - / (float)REG_BR_PROB_BASE); - } - cgraph_turn_edge_to_speculative - (e, n2, - apply_scale (e->count, - e->indirect_info->common_target_probability), - apply_scale (e->frequency, - e->indirect_info->common_target_probability)); - update = true; - } - else - if (dump_file) - fprintf (dump_file, "Function with profile-id %i not found.\n", - e->indirect_info->common_target_id); - } - if (update) - inline_update_overall_summary (n); - } - del_node_map (); - } - if (dump_file) dump_histogram (dump_file, histogram); for (i = 0; i < (int)histogram.length (); i++) Index: ipa-prop.c =================================================================== --- ipa-prop.c (revision 201640) +++ ipa-prop.c (working copy) @@ -38,6 +38,7 @@ #include "data-streamer.h" #include "tree-streamer.h" #include "params.h" +#include "ipa-utils.h" /* Intermediate information about a parameter that is only useful during the run of ipa_analyze_node and is not kept afterwards. */ @@ -2259,6 +2260,21 @@ struct inline_edge_summary *es = inline_edge_summary (ie); bool unreachable = false; + /* Sanity check that we actually have the virtual call in list of targets. */ + if (ie->indirect_info->polymorphic + && flag_devirtualize && cgraph_get_node (target)) + { + unsigned int i; + vec targets = possible_virtual_call_targets (ie->indirect_info->otr_type, + ie->indirect_info->offset, + ie->indirect_info->otr_token); + for (i = 0; i < targets.length(); i++) + if (targets[i]->symbol.decl == target) + break; + gcc_assert (i != targets.length()); + targets.release (); + } + if (TREE_CODE (target) == ADDR_EXPR) target = TREE_OPERAND (target, 0); if (TREE_CODE (target) != FUNCTION_DECL)