From patchwork Mon Jun 3 13:38:31 2019 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: 1109278 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-502211-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="Kr3AI75K"; dkim-atps=neutral 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 45Hbjw50bbz9s1c for ; Mon, 3 Jun 2019 23:38:44 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :subject:to:cc:message-id:date:mime-version:content-type; q=dns; s=default; b=E0zAb5Wf4BaZm/GnKTfGkGBa3nLZk51wnF1HC5NZbsKBBacBIT d2gg660YDxD2PlUrqA5pz/SHeILN+O1SLrtMt75fLxZ28vyPtXyJiUfWEBFVL+XO OnVOScdpqCKi0YZ32pAlTRNTYOPnrlgY+fi0AdeZhWUQbNranBQpumRTM= 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:from :subject:to:cc:message-id:date:mime-version:content-type; s= default; bh=r2OXFcbcQFj0HFqiDrqGIdqB8zw=; b=Kr3AI75KLs57Wa73XvKT oZqGVr9Sw2Eib74QYRRoMR07iuweOVsAYtU0+R7X5o7cOAjP3Ww1exifwnjSfuJh BqgISTdcEAkqScUoiUxfIu2GUnuo08EujvyNvQUhX9jVLkJglb0mY3k+EMP5Vx9U 2ssuGGs5k52eIH9pJ8OUOys= Received: (qmail 5656 invoked by alias); 3 Jun 2019 13:38:36 -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 5647 invoked by uid 89); 3 Jun 2019 13:38:36 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-16.1 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, SPF_PASS autolearn=ham version=3.3.1 spammy=1937, needle, smart, sk:release X-HELO: mx1.suse.de Received: from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 03 Jun 2019 13:38:34 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id 0584DAED9; Mon, 3 Jun 2019 13:38:32 +0000 (UTC) From: =?utf-8?q?Martin_Li=C5=A1ka?= Subject: [PATCH 1/2] IPA ICF: rewrite references into a hash_map. To: gcc-patches@gcc.gnu.org Cc: Jan Hubicka Message-ID: <24adbe26-a48e-e1d0-b9d9-1961b4c93e67@suse.cz> Date: Mon, 3 Jun 2019 15:38:31 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.7.0 MIME-Version: 1.0 X-IsSubscribed: yes Hi. The patch makes signification LTO WPA speed up for godot project from 76s to 65s. The patch uses more smart data structure for value numbering algorithm that we use. Patch can bootstrap on x86_64-linux-gnu and survives regression tests. Ready to be installed? Thanks, Martin gcc/ChangeLog: 2019-06-03 Martin Liska * ipa-icf.h (struct sem_usage_pair_hash): New. (sem_usage_pair_hash::hash): Likewise. (sem_usage_pair_hash::equal): Likewise. (struct sem_usage_hash): Likewise. * ipa-icf.c (sem_item::sem_item): Initialize referenced_by_count. (sem_item::add_reference): Register a reference in ref_map and not in target->usages. (sem_item::setup): Remove initialization of dead vectors. (sem_item::~sem_item): Remove usage of dead vectors. (sem_item::dump): Remove dump of references. (sem_item_optimizer::sem_item_optimizer): Initialize m_references. (sem_item_optimizer::read_section): Remove useless dump. (sem_item_optimizer::parse_funcs_and_vars): Likewise here. (sem_item_optimizer::build_graph): Pass m_references to ::add_reference. (sem_item_optimizer::verify_classes): Remove usage of dead vectors. (sem_item_optimizer::traverse_congruence_split): Return true when a class is split. (sem_item_optimizer::do_congruence_step_for_index): Use hash_map for look up of (sem_item *, index). That brings significant speed up. (sem_item_optimizer::do_congruence_step): Return true when a split is done. (congruence_class::is_class_used): Use referenced_by_count. --- gcc/ipa-icf.c | 102 ++++++++++++++++++++------------------------------ gcc/ipa-icf.h | 45 ++++++++++++++++++---- 2 files changed, 78 insertions(+), 69 deletions(-) diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c index 074181491da..a4705eee936 100644 --- a/gcc/ipa-icf.c +++ b/gcc/ipa-icf.c @@ -138,14 +138,15 @@ sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index) } sem_item::sem_item (sem_item_type _type, bitmap_obstack *stack) -: type (_type), m_hash (-1), m_hash_set (false) +: type (_type), referenced_by_count (0), m_hash (-1), m_hash_set (false) { setup (stack); } sem_item::sem_item (sem_item_type _type, symtab_node *_node, bitmap_obstack *stack) -: type (_type), node (_node), m_hash (-1), m_hash_set (false) +: type (_type), node (_node), referenced_by_count (0), m_hash (-1), + m_hash_set (false) { decl = node->decl; setup (stack); @@ -154,13 +155,18 @@ sem_item::sem_item (sem_item_type _type, symtab_node *_node, /* Add reference to a semantic TARGET. */ void -sem_item::add_reference (sem_item *target) +sem_item::add_reference (ref_map *refs, + sem_item *target) { - refs.safe_push (target); - unsigned index = refs.length (); - target->usages.safe_push (new sem_usage_pair(this, index)); + unsigned index = reference_count++; + bool existed; + + vec &v + = refs->get_or_insert (new sem_usage_pair (target, index), &existed); + v.safe_push (this); bitmap_set_bit (target->usage_index_bitmap, index); refs_set.add (target->node); + ++target->referenced_by_count; } /* Initialize internal data structures. Bitmap STACK is used for @@ -171,20 +177,14 @@ sem_item::setup (bitmap_obstack *stack) { gcc_checking_assert (node); - refs.create (0); + reference_count = 0; tree_refs.create (0); - usages.create (0); usage_index_bitmap = BITMAP_ALLOC (stack); } sem_item::~sem_item () { - for (unsigned i = 0; i < usages.length (); i++) - delete usages[i]; - - refs.release (); tree_refs.release (); - usages.release (); BITMAP_FREE (usage_index_bitmap); } @@ -199,13 +199,6 @@ sem_item::dump (void) fprintf (dump_file, "[%s] %s (tree:%p)\n", type == FUNC ? "func" : "var", node->dump_name (), (void *) node->decl); fprintf (dump_file, " hash: %u\n", get_hash ()); - fprintf (dump_file, " references: "); - - for (unsigned i = 0; i < refs.length (); i++) - fprintf (dump_file, "%s%s ", refs[i]->node->name (), - i < refs.length() - 1 ? "," : ""); - - fprintf (dump_file, "\n"); } } @@ -2230,7 +2223,7 @@ unsigned int sem_item_optimizer::class_id = 0; sem_item_optimizer::sem_item_optimizer () : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL), - m_varpool_node_hooks (NULL), m_merged_variables () + m_varpool_node_hooks (NULL), m_merged_variables (), m_references () { m_items.create (0); bitmap_obstack_initialize (&m_bmstack); @@ -2341,13 +2334,8 @@ sem_item_optimizer::read_section (lto_file_decl_data *file_data, node = lto_symtab_encoder_deref (encoder, index); hashval_t hash = streamer_read_uhwi (&ib_main); - gcc_assert (node->definition); - if (dump_file) - fprintf (dump_file, "Symbol added: %s (tree: %p)\n", - node->dump_asm_name (), (void *) node->decl); - if (is_a (node)) { cgraph_node *cnode = dyn_cast (node); @@ -2611,12 +2599,6 @@ sem_item_optimizer::parse_funcs_and_vars (void) { m_items.safe_push (f); m_symtab_node_map.put (cnode, f); - - if (dump_file) - fprintf (dump_file, "Parsed function:%s\n", f->node->asm_name ()); - - if (dump_file && (dump_flags & TDF_DETAILS)) - f->dump_to_file (dump_file); } else if (dump_file) fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ()); @@ -2745,7 +2727,7 @@ sem_item_optimizer::build_graph (void) sem_item **slot = m_symtab_node_map.get (e->callee->ultimate_alias_target ()); if (slot) - item->add_reference (*slot); + item->add_reference (&m_references, *slot); e = e->next_callee; } @@ -2757,7 +2739,7 @@ sem_item_optimizer::build_graph (void) sem_item **slot = m_symtab_node_map.get (ref->referred->ultimate_alias_target ()); if (slot) - item->add_reference (*slot); + item->add_reference (&m_references, *slot); } } } @@ -2987,13 +2969,6 @@ sem_item_optimizer::verify_classes (void) gcc_assert (item); gcc_assert (item->cls == cls); - - for (unsigned k = 0; k < item->usages.length (); k++) - { - sem_usage_pair *usage = item->usages[k]; - gcc_assert (usage->item->index_in_class - < usage->item->cls->members.length ()); - } } } } @@ -3106,10 +3081,11 @@ sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls, /* Release class if not presented in work list. */ if (!in_worklist) delete cls; - } + return true; + } - return true; + return false; } /* Compare function for sorting pairs in do_congruence_step_f. */ @@ -3131,7 +3107,7 @@ sem_item_optimizer::sort_congruence_split (const void *a_, const void *b_) /* Tests if a class CLS used as INDEXth splits any congruence classes. Bitmap stack BMSTACK is used for bitmap allocation. */ -void +bool sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls, unsigned int index) { @@ -3140,31 +3116,32 @@ sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls, for (unsigned int i = 0; i < cls->members.length (); i++) { sem_item *item = cls->members[i]; + sem_usage_pair needle (item, index); + vec *callers = m_references.get (&needle); + if (callers == NULL) + continue; - /* Iterate all usages that have INDEX as usage of the item. */ - for (unsigned int j = 0; j < item->usages.length (); j++) + for (unsigned int j = 0; j < callers->length (); j++) { - sem_usage_pair *usage = item->usages[j]; - - if (usage->index != index) + sem_item *caller = (*callers)[j]; + if (caller->cls->members.length () < 2) continue; - - bitmap *slot = split_map.get (usage->item->cls); + bitmap *slot = split_map.get (caller->cls); bitmap b; if(!slot) { b = BITMAP_ALLOC (&m_bmstack); - split_map.put (usage->item->cls, b); + split_map.put (caller->cls, b); } else b = *slot; - gcc_checking_assert (usage->item->cls); - gcc_checking_assert (usage->item->index_in_class - < usage->item->cls->members.length ()); + gcc_checking_assert (caller->cls); + gcc_checking_assert (caller->index_in_class + < caller->cls->members.length ()); - bitmap_set_bit (b, usage->item->index_in_class); + bitmap_set_bit (b, caller->index_in_class); } } @@ -3180,12 +3157,16 @@ sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls, pair.cls = cls; splitter_class_removed = false; + bool r = false; for (unsigned i = 0; i < to_split.length (); ++i) - traverse_congruence_split (to_split[i].first, to_split[i].second, &pair); + r |= traverse_congruence_split (to_split[i].first, to_split[i].second, + &pair); /* Bitmap clean-up. */ split_map.traverse (NULL); + + return r; } /* Every usage of a congruence class CLS is a candidate that can split the @@ -3206,9 +3187,8 @@ sem_item_optimizer::do_congruence_step (congruence_class *cls) EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi) { if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, " processing congruence step for class: %u, " - "index: %u\n", cls->id, i); - + fprintf (dump_file, " processing congruence step for class: %u " + "(%u items), index: %u\n", cls->id, cls->members.length (), i); do_congruence_step_for_index (cls, i); if (splitter_class_removed) @@ -3648,7 +3628,7 @@ bool congruence_class::is_class_used (void) { for (unsigned int i = 0; i < members.length (); i++) - if (members[i]->usages.length ()) + if (members[i]->referenced_by_count) return true; return false; diff --git a/gcc/ipa-icf.h b/gcc/ipa-icf.h index 27d588c9c12..ede4c94dbd3 100644 --- a/gcc/ipa-icf.h +++ b/gcc/ipa-icf.h @@ -126,7 +126,6 @@ struct symbol_compare_hash : nofree_ptr_hash } }; - /* Semantic item usage pair. */ class sem_usage_pair { @@ -141,6 +140,32 @@ public: unsigned int index; }; +struct sem_usage_pair_hash : pointer_hash +{ + static inline hashval_t hash (sem_usage_pair *); + static inline bool equal (sem_usage_pair *, sem_usage_pair *); +}; + +inline hashval_t +sem_usage_pair_hash::hash (sem_usage_pair *pair) +{ + inchash::hash hstate; + + hstate.add_ptr (pair->item); + hstate.add_int (pair->index); + + return hstate.end (); +} + +inline bool +sem_usage_pair_hash::equal (sem_usage_pair *p1, sem_usage_pair *p2) +{ + return p1->item == p2->item && p1->index == p2->index; +} + +struct sem_usage_hash : sem_usage_pair_hash, typed_delete_remove {}; +typedef hash_map > ref_map; + typedef std::pair symtab_pair; /* Semantic item is a base class that encapsulates all shared functionality @@ -168,7 +193,7 @@ public: virtual void init (void) = 0; /* Add reference to a semantic TARGET. */ - void add_reference (sem_item *target); + void add_reference (ref_map *map, sem_item *target); /* Fast equality function based on knowledge known in WPA. */ virtual bool equals_wpa (sem_item *item, @@ -216,8 +241,9 @@ public: /* Declaration tree node. */ tree decl; - /* Semantic references used that generate congruence groups. */ - vec refs; + /* Number of references to a semantic symbols (function calls, + variable references). */ + unsigned reference_count; /* Pointer to a congruence class the item belongs to. */ congruence_class *cls; @@ -225,9 +251,6 @@ public: /* Index of the item in a class belonging to. */ unsigned int index_in_class; - /* List of semantic items where the instance is used. */ - vec usages; - /* A bitmap with indices of all classes referencing this item. */ bitmap usage_index_bitmap; @@ -239,6 +262,9 @@ public: /* Temporary hash used where hash values of references are added. */ hashval_t global_hash; + + /* Number of references to this symbol. */ + unsigned referenced_by_count; protected: /* Cached, once calculated hash for the item. */ @@ -581,7 +607,7 @@ private: /* Tests if a class CLS used as INDEXth splits any congruence classes. Bitmap stack BMSTACK is used for bitmap allocation. */ - void do_congruence_step_for_index (congruence_class *cls, unsigned int index); + bool do_congruence_step_for_index (congruence_class *cls, unsigned int index); /* Makes pairing between a congruence class CLS and semantic ITEM. */ static void add_item_to_class (congruence_class *cls, sem_item *item); @@ -644,6 +670,9 @@ private: /* Vector of merged variables. Needed for fixup of points-to-analysis info. */ vec m_merged_variables; + + /* Hash map will all references. */ + ref_map m_references; }; // class sem_item_optimizer } // ipa_icf namespace