From patchwork Thu Jul 9 10:44:15 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom de Vries X-Patchwork-Id: 493368 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 079CC1402B8 for ; Thu, 9 Jul 2015 20:44:58 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=OOB3FR1E; 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=wTTTVb/aacKdC8kpb mTJB5Qf/jobcijAeZbdYKHFJE5m6HDmYvXFykKvFzBw0DeiTkquwOMrVH4DApfjp uettuaysRnJRoNXUgBSxQIGZkvXru27ci5lKUQ8b7j9L/8r/OaTdAS1skdkLJEoh Xfwp5O3f7A4y0GhVRaQMSy7hJQ= 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=kVMuajYdzlTiMDmkQBiMaNv h8Lg=; b=OOB3FR1EnjM5e/8xC61QG/fl1OjQ/D41u3HCOa/Y4977BK7g+VQpzvV A75FUzPX+EECbX/3AZrgTfOZ5L4kxLP9JprJ09MxvgX0pQuoLdPcpnl8q6gsU8+K QF5FhWKxbqN+GQJXZDh/w6lDGsMXdhMMnrN5uPOnAVy0qornRbJ4= Received: (qmail 127894 invoked by alias); 9 Jul 2015 10:44:51 -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 126267 invoked by uid 89); 9 Jul 2015 10:44:50 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.1 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD, SPF_PASS autolearn=ham version=3.3.2 X-HELO: fencepost.gnu.org Received: from fencepost.gnu.org (HELO fencepost.gnu.org) (208.118.235.10) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Thu, 09 Jul 2015 10:44:48 +0000 Received: from eggs.gnu.org ([2001:4830:134:3::10]:53497) by fencepost.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1ZD9Ju-0001Rv-6M for gcc-patches@gnu.org; Thu, 09 Jul 2015 06:44:46 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZD9Jq-0006Ta-IM for gcc-patches@gnu.org; Thu, 09 Jul 2015 06:44:45 -0400 Received: from relay1.mentorg.com ([192.94.38.131]:60973) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZD9Jq-0006KY-9Q for gcc-patches@gnu.org; Thu, 09 Jul 2015 06:44:42 -0400 Received: from nat-ies.mentorg.com ([192.94.31.2] helo=SVR-IES-FEM-02.mgc.mentorg.com) by relay1.mentorg.com with esmtp id 1ZD9Jm-0003h6-FO from Tom_deVries@mentor.com ; Thu, 09 Jul 2015 03:44:39 -0700 Received: from [127.0.0.1] (137.202.0.76) by SVR-IES-FEM-02.mgc.mentorg.com (137.202.0.106) with Microsoft SMTP Server id 14.3.224.2; Thu, 9 Jul 2015 11:44:36 +0100 Message-ID: <559E507F.5030107@mentor.com> Date: Thu, 9 Jul 2015 12:44:15 +0200 From: Tom de Vries User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.7.0 MIME-Version: 1.0 To: Michael Matz , Richard Biener CC: "gcc-patches@gnu.org" Subject: Re: [RFC] two-phase marking in gt_cleare_cache References: <559A42E9.6000303@mentor.com> In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Windows NT kernel [generic] [fuzzy] X-Received-From: 192.94.38.131 On 07/07/15 16:00, Michael Matz wrote: > Hi, > > On Mon, 6 Jul 2015, Richard Biener wrote: > >>>> By doing so, we make the behaviour of gt_cleare_cache independent of the >>>> order in which the entries are visited, turning: >>>> - hard-to-trigger bugs which trigger for one visiting order but not for >>>> another, into >>>> - more easily triggered bugs which trigger for any visiting order. >>>> >>>> Any comments? >>> >>> I think it is only half-way correct in your proposed change. You only >>> fix the issue for hashes of the same kind. To truly fix the issue you'd >>> have to change generated code for gt_clear_caches () and provide >>> a clearing-only implementation (or pass a operation mode bool to >>> the core worker in hash-table.h). >> >> Hmm, and don't we rather want to first mark and _then_ clear? Because >> if entry B in the hash is live and would keep A live then A _is_ kept in >> the end but you'll remove it from the hash, possibly no longer using a >> still live copy. > > I don't think such use has ever worked with the caching hash tables. Even > the old (before c++) scheme didn't iterate, i.e. if a cache-hash entry A > became life from outside, but it itself kept an entry B live in the hash > table (with no other references to B) then this never worked (or only by > luck), because the slot was always cleared if !ggc_marked_p, so if B was > visited before A it was removed from the hash-table (and in particular B's > gt_ggc_mx routine was never called, so whatever B needed wasn't even > marked). > > Given this I think the call to gt_ggc_mx is superfluous because it > wouldn't work relyably for multi-step dependencies anyway. Hence a > situation that works with that call in place, and breaking without it is > actually a bug waiting to be uncovered. > Attached patch tries to get multi-step dependencies right, without using iteration-till-fixed-point. During the marking phase, we do recursive marking of the cache entries, while skipping the marking of: - the cache entry itself, and - the key component of the cache entry. This marking is done for all non-empty cache entries independent of the current value of keep_cache_entry. So we make a conservative choice here, and by doing so avoid having to iterate-till-fixed-point. During the cache-clear phase, for each cache entry we either non-recursively mark it live, or remove it. AFAIU, this scheme reliably handles multi-step dependencies and does not increase runtime. Passes a minimal c build, and it fixes the ICE of PR66714 (although there still might be a root cause to address, I'm not sure). Thanks, - Tom Use conservative non-iterative strategy for caches 2015-07-09 Tom de Vries PR libgomp/66714 * hash-table.h (gt_cleare_cache): Don't recurse cache entries, just mark. * trans-mem.c (struct tm_wrapper_hasher::ggc_mx (tree_map *&m)): New function. * tree.c (struct tree_vec_map_cache_hasher::ggc_mx (tree_vec_map *&m): Same. * tree.h (struct tree_decl_map_cache_hasher::ggc_mx (tree_decl_map *&m)): Same. * ubsan.c (struct tree_type_map_cache_hasher::ggc_mx (tree_type_map *&m)): Same. * varasm.c (struct tm_clone_hasher::ggc_mx (tree_map *&m)): Same. * testsuite/libgomp.c/pr66714.c: New test. --- gcc/hash-table.h | 28 +++++++++++++++++++++++++++- gcc/trans-mem.c | 4 ++++ gcc/tree.c | 7 +++++++ gcc/tree.h | 6 ++++++ gcc/ubsan.c | 4 ++++ gcc/varasm.c | 4 ++++ libgomp/testsuite/libgomp.c/pr66714.c | 17 +++++++++++++++++ 7 files changed, 69 insertions(+), 1 deletion(-) create mode 100644 libgomp/testsuite/libgomp.c/pr66714.c diff --git a/gcc/hash-table.h b/gcc/hash-table.h index 12e0c96..ce899bd 100644 --- a/gcc/hash-table.h +++ b/gcc/hash-table.h @@ -1046,6 +1046,32 @@ gt_cleare_cache (hash_table *h) if (!h) return; + /* Say we have a cache entry E with key 'from' and non-key 'to'. + + The marking of non-key 'to' should be done in ggc_mx () during the marking + phase. We mark the non-key 'to' conservatively, that is, regardless of + whether the key 'from' is live or not. + + The marking of key 'from' has already been done or not during the marking + phase, and determines whether we keep entry E live during the clear-cache + phase. + If key 'from' is alive, we mark entry E as such. + If key 'from' is not alive: + - we remove the entry E from the cache, and + - entry E will be ggc-freed, and + - key 'from' will be ggc-freed. + - non-key 'to' will not be freed, since we conservatively marked it. But + next ggc invocation, entry E will be gone and no longer cause 'to' to be + marked. So 'to' may be gcc-freed the next ggc invocation. + + Background: A more optimal marking strategy would be to mark the non-key + 'to' only if key 'from' is live. But in order to get to the transitive + closure of that marking, we'd need an iterate-till-fixed-point loop around + the traversing of all cache tables and their entries. + So instead we mark conservatively. The drawback of this strategy + is that cache cycles are not freed. Also, it can take several ggc + invocations for the effects to fully propagate. */ + for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter) if (!table::is_empty (*iter) && !table::is_deleted (*iter)) { @@ -1053,7 +1079,7 @@ gt_cleare_cache (hash_table *h) if (res == 0) h->clear_slot (&*iter); else if (res != -1) - gt_ggc_mx (*iter); + ggc_set_mark (*iter); } } diff --git a/gcc/trans-mem.c b/gcc/trans-mem.c index c809a2e..748a2b6 100644 --- a/gcc/trans-mem.c +++ b/gcc/trans-mem.c @@ -478,6 +478,10 @@ struct tm_wrapper_hasher : ggc_cache_ptr_hash return a->base.from == b->base.from; } + static void ggc_mx (tree_map *&m) { + gt_ggc_mx (m->to); + } + static int keep_cache_entry (tree_map *&m) { diff --git a/gcc/tree.c b/gcc/tree.c index 6628a38..16afae5 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -261,6 +261,13 @@ struct tree_vec_map_cache_hasher : ggc_cache_ptr_hash return a->base.from == b->base.from; } + static void ggc_mx (tree_vec_map *&m) { + /* gt_ggc_mx (vec *v) from vec.h does not do + ggc_test_and_set_mark, so do it here. */ + if (ggc_test_and_set_mark (m->to)) + gt_ggc_mx (m->to); + } + static int keep_cache_entry (tree_vec_map *&m) { diff --git a/gcc/tree.h b/gcc/tree.h index 250f99d..ae48a80 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -4626,6 +4626,8 @@ extern unsigned int tree_map_hash (const void *); extern unsigned int tree_decl_map_hash (const void *); #define tree_decl_map_marked_p tree_map_base_marked_p +extern void gt_ggc_mx (tree&); + struct tree_decl_map_cache_hasher : ggc_cache_ptr_hash { static hashval_t hash (tree_decl_map *m) { return tree_decl_map_hash (m); } @@ -4635,6 +4637,10 @@ struct tree_decl_map_cache_hasher : ggc_cache_ptr_hash return tree_decl_map_eq (a, b); } + static void ggc_mx (tree_decl_map *&m) { + gt_ggc_mx (m->to); + } + static int keep_cache_entry (tree_decl_map *&m) { diff --git a/gcc/ubsan.c b/gcc/ubsan.c index 19eafab..6ea5be8 100644 --- a/gcc/ubsan.c +++ b/gcc/ubsan.c @@ -95,6 +95,10 @@ struct tree_type_map_cache_hasher : ggc_cache_ptr_hash return a->type.from == b->type.from; } + static void ggc_mx (tree_type_map *&m) { + gt_ggc_mx (m->decl); + } + static int keep_cache_entry (tree_type_map *&m) { diff --git a/gcc/varasm.c b/gcc/varasm.c index 3e76032..ff20941 100644 --- a/gcc/varasm.c +++ b/gcc/varasm.c @@ -5793,6 +5793,10 @@ struct tm_clone_hasher : ggc_cache_ptr_hash static hashval_t hash (tree_map *m) { return tree_map_hash (m); } static bool equal (tree_map *a, tree_map *b) { return tree_map_eq (a, b); } + static void ggc_mx (tree_map *&m) { + gt_ggc_mx (m->to); + } + static int keep_cache_entry (tree_map *&e) { diff --git a/libgomp/testsuite/libgomp.c/pr66714.c b/libgomp/testsuite/libgomp.c/pr66714.c new file mode 100644 index 0000000..b60c74d --- /dev/null +++ b/libgomp/testsuite/libgomp.c/pr66714.c @@ -0,0 +1,17 @@ +/* { dg-do "compile" } */ +/* { dg-additional-options "--param ggc-min-expand=0" } */ +/* { dg-additional-options "--param ggc-min-heapsize=0" } */ +/* { dg-additional-options "-g" } */ + +/* Minimized from on target-2.c. */ + +void +fn3 (int x) +{ + double b[3 * x]; + int i; + #pragma omp target + #pragma omp parallel for + for (i = 0; i < x; i++) + b[i] += 1; +} -- 1.9.1