From patchwork Wed Feb 25 16:19:34 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Martin_Li=C5=A1ka?= X-Patchwork-Id: 443498 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.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id BDB2E140083 for ; Thu, 26 Feb 2015 03:19:49 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass reason="1024-bit key; unprotected key" header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=JVRKaE9h; dkim-adsp=none (unprotected policy); dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:cc:subject:references :in-reply-to:content-type; q=dns; s=default; b=kkKtXJqaANo3bEghJ 3RSIk6Cl/i+Ct/PjC7JT5Ejcr04QG+yeHEiUct5F744drPD3aW8LIr+eXbTrp5Sv qT+ssLTZnBnF7Qp8VEeE8CzTBOPgD4UXAG6vvuHfDOMSGNm/UnH/Ph08C8BEti+t hDPO+j7PI92mjLNkp/GY3bUSpg= 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 :message-id:date:from:mime-version:to:cc:subject:references :in-reply-to:content-type; s=default; bh=uRn5M/totGub/1tysRplSbt DDxs=; b=JVRKaE9heImQmhrjTJsv8pRBj1HkYOZ3Oqilm9h2Ma8fj42OexISGBO nmoz6oNLAPuymgWXiUJWoTIE3Emm7RkuBecLQDAXHpHZnPZQNDJh4oZQXZxIcOiF yXLbezCiwKlBFCQ/MAq8DydTH/iSc/HTUwRmmugKNCuJKs6JHjDM= Received: (qmail 70633 invoked by alias); 25 Feb 2015 16:19:40 -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 70613 invoked by uid 89); 25 Feb 2015 16:19:39 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.2 required=5.0 tests=AWL, BAYES_00 autolearn=ham version=3.3.2 X-HELO: mx2.suse.de Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Wed, 25 Feb 2015 16:19:37 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 6005EACF3; Wed, 25 Feb 2015 16:19:34 +0000 (UTC) Message-ID: <54EDF616.9070908@suse.cz> Date: Wed, 25 Feb 2015 17:19:34 +0100 From: =?windows-1252?Q?Martin_Li=9Aka?= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.2.0 MIME-Version: 1.0 To: gcc-patches@gcc.gnu.org CC: "hubicka@ >> Jan Hubicka" Subject: Re: [PATCH] Fix for PR ipa/64693 References: <54DC77A5.4020409@suse.cz> <20150212165758.GA3301@kam.mff.cuni.cz> <54E7308B.3020400@suse.cz> <20150220183956.GD21632@kam.mff.cuni.cz> In-Reply-To: <20150220183956.GD21632@kam.mff.cuni.cz> X-IsSubscribed: yes On 02/20/2015 07:39 PM, Jan Hubicka wrote: >> Hello. >> >> There's updated version that reflects how should we handle congruence classes that have any >> address reference. Patch can bootstrap x86_64-linux-pc and no new regression is introduced? >> >> Ready for trunk? >> Thanks, >> Martin >> >> > >> >From d7472e55b345214d55ed49f5f10deafa9a24a4fc Mon Sep 17 00:00:00 2001 >> From: mliska >> Date: Thu, 19 Feb 2015 16:08:09 +0100 >> Subject: [PATCH 1/2] Fix PR ipa/64693 >> >> gcc/ChangeLog: >> >> 2015-02-20 Martin Liska >> >> PR ipa/64693 >> * ipa-icf.c (sem_item_optimizer::add_item_to_class): Identify if >> a newly added item has an address reference. >> (sem_item_optimizer::subdivide_classes_by_addr_references): >> New function. >> (sem_item_optimizer::process_cong_reduction): Include subdivision >> based on address references. >> * ipa-icf.h (struct addr_refs_hashmap_traits): New struct. >> * ipa-ref.h (has_addr_ref_p): New function. >> >> gcc/testsuite/ChangeLog: >> >> 2015-02-20 Martin Liska >> >> * gcc.dg/ipa/ipa-icf-26.c: Update expected test results. >> * gcc.dg/ipa/ipa-icf-33.c: Remove duplicate line. >> * gcc.dg/ipa/ipa-icf-34.c: New test. > >> >> diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c >> index 494fdcf..859b9d1 100644 >> --- a/gcc/ipa-icf.c >> +++ b/gcc/ipa-icf.c >> @@ -1809,6 +1809,9 @@ sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item) >> item->index_in_class = cls->members.length (); >> cls->members.safe_push (item); >> item->cls = cls; >> + >> + if (!cls->has_member_with_addr_ref && item->node->ref_list.has_addr_ref_p ()) >> + cls->has_member_with_addr_ref = true; >> } >> >> /* Congruence classes are built by hash value. */ >> @@ -1969,6 +1972,84 @@ sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa) >> verify_classes (); >> } >> >> +/* Subdivide classes by address references that members of the class >> + reference. Example can be a pair of functions that have an address >> + taken from a function. If these addresses are different the class >> + is split. */ > > OK, I am bit surprised you have a separate loop for this instead of doing it at > a place you compare ipa-ref rerences anyway, but I suppose you know the code > better than I do ;) >> + while(!worklist_empty ()) >> + { >> + /* Process complete congruence reduction. */ >> + while ((cls = worklist_pop ()) != NULL) >> + do_congruence_step (cls); >> + >> + /* Subdivide newly created classes according to references. */ >> + unsigned new_classes = subdivide_classes_by_addr_references (); > > I think this needs to be performed just once, because subdividing does not > depend on congurences. >> >> +/* Class is container for address references for a symtab_node. */ >> + >> +class addr_refs_collection >> +{ >> +public: >> + addr_refs_collection (symtab_node *node) >> + { >> + m_references.create (0); >> + ipa_ref *ref; >> + >> + if (is_a (node) && DECL_VIRTUAL_P (node->decl)) >> + return; >> + >> + for (unsigned i = 0; i < node->num_references (); i++) >> + { >> + ref = node->iterate_reference (i, ref); >> + if (ref->use == IPA_REF_ADDR) >> + m_references.safe_push (ref->referred); > > You do not need to consider IPA_REF_ADDR of virtual table/ctors/dtors and virtual functions > to be address references (because these are never compared for equality.) Test it as > > The proper conditon on when address matter is > if (!DECL_VIRTUAL_P (ref->referred->decl) > && (TREE_CODE (ref->referred->decl) != FUNCTION_DECL > || (!DECL_CXX_CONSTRUCTOR_P (ref->referred->decl) > && !DECL_CXX_DESTRUCTOR_P (ref->referred->decl))) > > please also update sem_function::merge by adding cdtors in addition > to DECL_VIRTUAL_P > > Why sem_item_optimizer::filter_removed_items checks cdtors? >> + } >> + } >> + >> + /* Vector of address references. */ >> + vec m_references; >> +}; >> + >> +/* Hash traits for addr_refs_collection map. */ >> + >> +struct addr_refs_hashmap_traits: default_hashmap_traits >> +{ >> + static hashval_t >> + hash (const addr_refs_collection *v) >> + { >> + inchash::hash hstate; >> + hstate.add_int (v->m_references.length ()); >> + >> + return hstate.end (); > > This looks like a poor choice of hash function because the count will likely > match. equal_address_to basically walks to alias targets > A safe approximation is to hash ultimate_alias_target of all entries in your list. >> + } >> + >> + static bool >> + equal_keys (const addr_refs_collection *a, >> + const addr_refs_collection *b) >> + { >> + if (a->m_references.length () != b->m_references.length ()) >> + return false; >> + >> + for (unsigned i = 0; i < a->m_references.length (); i++) >> + if (a->m_references[i]->equal_address_to (b->m_references[i]) != 1) >> + return false; >> + >> + return true; >> + } >> +}; > > OK with these changes. > Honza > Hello Honza. I've updated the patch so that your notes are resolved. Moreover, I've added comparison for interposable symbols that are either target of reference or are called by a function. Please read the patch to verify the comparison is as you expected. I'm going to run testsuite. Thanks, Martin From 8dae064e67e30537486e0d502fc5df39d37cee3e Mon Sep 17 00:00:00 2001 From: mliska Date: Thu, 19 Feb 2015 16:08:09 +0100 Subject: [PATCH 1/3] Fix PR ipa/64693 gcc/ChangeLog: 2015-02-20 Martin Liska PR ipa/64693 * ipa-icf.c (sem_item_optimizer::add_item_to_class): Identify if a newly added item has an address reference. (sem_item_optimizer::subdivide_classes_by_addr_references): New function. (sem_item_optimizer::process_cong_reduction): Include subdivision based on address references. * ipa-icf.h (struct addr_refs_hashmap_traits): New struct. (sem_item::is_nonvirtual_or_cdtor): New function. gcc/testsuite/ChangeLog: 2015-02-20 Martin Liska * gcc.dg/ipa/ipa-icf-26.c: Update expected test results. * gcc.dg/ipa/ipa-icf-33.c: Remove duplicate line. * gcc.dg/ipa/ipa-icf-34.c: New test. --- gcc/ipa-icf.c | 130 ++++++++++++++++++++++++++++++++-- gcc/ipa-icf.h | 85 ++++++++++++++++++++++ gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c | 3 +- gcc/testsuite/gcc.dg/ipa/ipa-icf-33.c | 1 - gcc/testsuite/gcc.dg/ipa/ipa-icf-34.c | 43 +++++++++++ 5 files changed, 255 insertions(+), 7 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/ipa/ipa-icf-34.c diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c index 494fdcf..fbb641d 100644 --- a/gcc/ipa-icf.c +++ b/gcc/ipa-icf.c @@ -126,6 +126,40 @@ along with GCC; see the file COPYING3. If not see using namespace ipa_icf_gimple; namespace ipa_icf { + +/* Constructor. */ + +addr_refs_collection::addr_refs_collection (symtab_node *node) +{ + m_references.create (0); + m_interposables.create (0); + + ipa_ref *ref; + + if (is_a (node) && DECL_VIRTUAL_P (node->decl)) + return; + + for (unsigned i = 0; i < node->num_references (); i++) + { + ref = node->iterate_reference (i, ref); + if (ref->use == IPA_REF_ADDR + && sem_item::is_nonvirtual_or_cdtor (ref->referred->decl)) + m_references.safe_push (ref->referred); + + if (ref->referred->get_availability () <= AVAIL_INTERPOSABLE) + m_interposables.safe_push (ref->referred); + } + + if (is_a (node)) + { + cgraph_node *cnode = dyn_cast (node); + + for (cgraph_edge *e = cnode->callees; e; e = e->next_callee) + if (e->callee->get_availability () <= AVAIL_INTERPOSABLE) + m_interposables.safe_push (e->callee); + } +} + /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */ sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index): @@ -638,11 +672,11 @@ sem_function::merge (sem_item *alias_item) /* See if original and/or alias address can be compared for equality. */ original_address_matters - = (!DECL_VIRTUAL_P (original->decl) + = (sem_item::is_nonvirtual_or_cdtor (original->decl) && (original->externally_visible || original->address_taken_from_non_vtable_p ())); alias_address_matters - = (!DECL_VIRTUAL_P (alias->decl) + = (sem_item::is_nonvirtual_or_cdtor (alias->decl) && (alias->externally_visible || alias->address_taken_from_non_vtable_p ())); @@ -1969,6 +2003,82 @@ sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa) verify_classes (); } +/* Subdivide classes by address references that members of the class + reference. Example can be a pair of functions that have an address + taken from a function. If these addresses are different the class + is split. */ + +unsigned +sem_item_optimizer::subdivide_classes_by_addr_references () +{ + unsigned newly_created_classes = 0; + + for (hash_table ::iterator it = m_classes.begin (); + it != m_classes.end (); ++it) + { + unsigned int class_count = (*it)->classes.length (); + auto_vec new_classes; + + for (unsigned i = 0; i < class_count; i++) + { + congruence_class *c = (*it)->classes [i]; + + if (c->members.length() > 1) + { + hash_map , addr_refs_hashmap_traits> split_map; + + for (unsigned j = 0; j < c->members.length (); j++) + { + sem_item *source_node = c->members[j]; + + addr_refs_collection *collection = new addr_refs_collection (source_node->node); + + vec *slot = &split_map.get_or_insert (collection); + gcc_checking_assert (slot); + + slot->safe_push (source_node); + } + + /* If the map contains more than one key, we have to split the map + appropriately. */ + if (split_map.elements () != 1) + { + bool first_class = true; + + hash_map , addr_refs_hashmap_traits>::iterator it2 = split_map.begin (); + for (; it2 != split_map.end (); ++it2) + { + congruence_class *new_cls; + new_cls = new congruence_class (class_id++); + + for (unsigned k = 0; k < (*it2).second.length (); k++) + add_item_to_class (new_cls, (*it2).second[k]); + + worklist_push (new_cls); + newly_created_classes++; + + if (first_class) + { + (*it)->classes[i] = new_cls; + first_class = false; + } + else + { + new_classes.safe_push (new_cls); + m_classes_count++; + } + } + } + } + } + + for (unsigned i = 0; i < new_classes.length (); i++) + (*it)->classes.safe_push (new_classes[i]); + } + + return newly_created_classes; +} + /* Verify congruence classes if checking is enabled. */ void @@ -2258,8 +2368,20 @@ sem_item_optimizer::process_cong_reduction (void) fprintf (dump_file, "Congruence class reduction\n"); congruence_class *cls; - while ((cls = worklist_pop ()) != NULL) - do_congruence_step (cls); + + while(!worklist_empty ()) + { + /* Process complete congruence reduction. */ + while ((cls = worklist_pop ()) != NULL) + do_congruence_step (cls); + + /* Subdivide newly created classes according to references. */ + unsigned new_classes = subdivide_classes_by_addr_references (); + + if (dump_file) + fprintf (dump_file, "Address reference subdivision created: %u " + "new classes.\n", new_classes); + } } /* Debug function prints all informations about congruence classes. */ diff --git a/gcc/ipa-icf.h b/gcc/ipa-icf.h index a55699b..dd016f3 100644 --- a/gcc/ipa-icf.h +++ b/gcc/ipa-icf.h @@ -63,6 +63,70 @@ enum sem_item_type VAR }; +/* Class is container for address references for a symtab_node. */ + +class addr_refs_collection +{ +public: + /* Constructor. */ + addr_refs_collection (symtab_node *node); + + /* Destructor. */ + ~addr_refs_collection () + { + m_references.release (); + m_interposables.release (); + } + + /* Vector of address references. */ + vec m_references; + + /* Vector of interposable references. */ + vec m_interposables; +}; + +/* Hash traits for addr_refs_collection map. */ + +struct addr_refs_hashmap_traits: default_hashmap_traits +{ + static hashval_t + hash (const addr_refs_collection *v) + { + inchash::hash hstate; + hstate.add_int (v->m_references.length ()); + + for (unsigned i = 0; i < v->m_references.length (); i++) + hstate.add_ptr (v->m_references[i]->ultimate_alias_target ()); + + hstate.add_int (v->m_interposables.length ()); + + for (unsigned i = 0; i < v->m_interposables.length (); i++) + hstate.add_ptr (v->m_interposables[i]->ultimate_alias_target ()); + + return hstate.end (); + } + + static bool + equal_keys (const addr_refs_collection *a, + const addr_refs_collection *b) + { + if (a->m_references.length () != b->m_references.length ()) + return false; + + for (unsigned i = 0; i < a->m_references.length (); i++) + if (a->m_references[i]->equal_address_to (b->m_references[i]) != 1) + return false; + + for (unsigned i = 0; i < a->m_interposables.length (); i++) + if (!a->m_interposables[i]->semantically_equivalent_p + (b->m_interposables[i])) + return false; + + return true; + } +}; + + /* Semantic item usage pair. */ class sem_usage_pair { @@ -140,6 +204,15 @@ public: contains_polymorphic_type_p comparison. */ static bool get_base_types (tree *t1, tree *t2); + /* Return true if given DECL is neither virtual nor cdtor. */ + static bool is_nonvirtual_or_cdtor (tree decl) + { + return !DECL_VIRTUAL_P (decl) + && (TREE_CODE (decl) != FUNCTION_DECL + || (!DECL_CXX_CONSTRUCTOR_P (decl) + && !DECL_CXX_DESTRUCTOR_P (decl))); + } + /* Return true if target supports alias symbols. */ bool target_supports_symbol_aliases_p (void); @@ -467,6 +540,12 @@ private: classes. If IN_WPA, fast equality function is invoked. */ void subdivide_classes_by_equality (bool in_wpa = false); + /* Subdivide classes by address references that members of the class + reference. Example can be a pair of functions that have an address + taken from a function. If these addresses are different the class + is split. */ + unsigned subdivide_classes_by_addr_references (); + /* Debug function prints all informations about congruence classes. */ void dump_cong_classes (void); @@ -487,6 +566,12 @@ private: /* Pops a class from worklist. */ congruence_class *worklist_pop (); + /* Return true if worklist is empty. */ + bool worklist_empty () + { + return worklist.empty (); + } + /* Every usage of a congruence class CLS is a candidate that can split the collection of classes. Bitmap stack BMSTACK is used for bitmap allocation. */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c index 0c5a5a6..f48c040 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c +++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c @@ -38,7 +38,6 @@ int main() return 0; } -/* { dg-final { scan-ipa-dump "Semantic equality hit:bar->foo" "icf" } } */ /* { dg-final { scan-ipa-dump "Semantic equality hit:remove->destroy" "icf" } } */ -/* { dg-final { scan-ipa-dump "Equal symbols: 2" "icf" } } */ +/* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf" } } */ /* { dg-final { cleanup-ipa-dump "icf" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-33.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-33.c index d7e814d..7b6a8ae 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-33.c +++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-33.c @@ -23,5 +23,4 @@ int main() } /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf" } } */ -/* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf" } } */ /* { dg-final { cleanup-ipa-dump "icf" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-34.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-34.c new file mode 100644 index 0000000..7772e49 --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-34.c @@ -0,0 +1,43 @@ +/* { dg-do compile } */ +/* { dg-options "-O0 -fipa-icf -fdump-ipa-icf-details" } */ + +#include +#include + +int callback1(int a) +{ + return a * a; +} + +int callback2(int a) +{ + return a * a; +} + +static int test(int (*callback) (int)) +{ + if (callback == callback1) + return 1; + + return 0; +} + +int foo() +{ + return test(&callback1); +} + +int bar() +{ + return test(&callback2); +} + +int main() +{ + assert (foo() != bar()); + + return 0; +} + +/* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf" } } */ +/* { dg-final { cleanup-ipa-dump "icf" } } */ -- 2.1.2