From patchwork Fri Mar 20 18:17:17 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 452735 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 0AB2E140077 for ; Sat, 21 Mar 2015 05:17:31 +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=sDHwKvfJ; 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:date :from:to:cc:subject:message-id:references:mime-version :content-type:in-reply-to; q=dns; s=default; b=UDdOmUmZxMw6EZ+eQ 01qVO4BOlgdZugPgqF/INFnhUoBiLk21dpBzT0TzH4LM2VZzfTfKz9kAmjnGmIVI TbNN77Hync+LATTTQWv2XdfPjiUbAAuZgrvl6Nn4mYh0c6wBWOdvQ6Y8ZEr2+Hsz dFbiBSA0mqrD+Cs7hpHLG6ZVkE= 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=yKUYoemVxmUkoC7QlVrcXcK /roI=; b=sDHwKvfJr3I6dvgn2F9jv60CkfWE32PIhEzXjm02idrz6eIkSiF0qpK 4ZTVHwyt3j2W5SYjxgNl/j8b6B91aw4WSAURuaGxfld8Th3BfIwp+5PCFMDZ7nb7 o4bkvNSgYBks9ItKX1fEZnKlmoLzMq6LlxZcBmuIYK56wT3qseks= Received: (qmail 29223 invoked by alias); 20 Mar 2015 18:17:23 -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 29208 invoked by uid 89); 20 Mar 2015 18:17:23 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=1.9 required=5.0 tests=AWL, BAYES_50, FREEMAIL_FROM, KAM_FROM_URIBL_PCCC, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=no version=3.3.2 X-HELO: mail-ie0-f182.google.com Received: from mail-ie0-f182.google.com (HELO mail-ie0-f182.google.com) (209.85.223.182) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Fri, 20 Mar 2015 18:17:21 +0000 Received: by ieclw3 with SMTP id lw3so98957601iec.2 for ; Fri, 20 Mar 2015 11:17:19 -0700 (PDT) X-Received: by 10.50.43.162 with SMTP id x2mr27408366igl.46.1426875439606; Fri, 20 Mar 2015 11:17:19 -0700 (PDT) Received: from f1.c.bardezibar.internal (81.37.148.146.bc.googleusercontent.com. [146.148.37.81]) by mx.google.com with ESMTPSA id s7sm3631657ioi.15.2015.03.20.11.17.18 (version=SSLv3 cipher=RC4-SHA bits=128/128); Fri, 20 Mar 2015 11:17:18 -0700 (PDT) Date: Fri, 20 Mar 2015 18:17:17 +0000 From: Sebastian Pop To: Richard Biener Cc: GCC Patches , Jeff Law Subject: Re: Fix PR 65177: diamonds are not valid execution threads for jump threading Message-ID: <20150320181716.GB21421@f1.c.bardezibar.internal> References: <20150318223541.GA17168@f1.c.bardezibar.internal> <20150319195402.GA21421@f1.c.bardezibar.internal> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-IsSubscribed: yes Richard Biener wrote: > On Thu, Mar 19, 2015 at 8:54 PM, Sebastian Pop wrote: > > Richard Biener wrote: > >> please instead fixup after copy_bbs in duplicate_seme_region. > >> > > > > Thanks for the review. > > Attached patch that does not modify copy_bbs. > > Fixes make check in hmmer and make check RUNTESTFLAGS=tree-ssa.exp > > > > Full bootstrap and regtest in progress on x86_64-linux. Ok for trunk? > > Looks good to me. Please also add a testcase. Attached. I will wait to commit until I have a green light from Jeff. Sebastian From f57f9a44717406cd148b3f432565654c36b33f2f Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Fri, 20 Mar 2015 18:12:47 +0100 Subject: [PATCH] diamonds are not valid execution threads for jump threading PR tree-optimization/65177 * tree-ssa-threadupdate.c (verify_seme): Renamed verify_jump_thread. (bb_in_bbs): New. (duplicate_seme_region): Renamed duplicate_thread_path. Redirect all edges not adjacent on the path to the original code. * gcc.dg/tree-ssa/ssa-dom-thread-10.c: New. --- gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c | 24 ++++++ gcc/tree-ssa-threadupdate.c | 93 +++++++++++++++------ 2 files changed, 91 insertions(+), 26 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c new file mode 100644 index 0000000..4acf580 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c @@ -0,0 +1,24 @@ +/* PR 65177 */ +/* { dg-do compile } */ +/* { dg-options "-O3" } */ + +typedef struct p7_profile_s {} P7_PROFILE; +enum p7t_statetype_e { + p7T_S = 4, p7T_N = 5, p7T_E = 7, p7T_C = 8, p7T_J = 10, }; +typedef struct p7_trace_s {} P7_TRACE; +typedef struct p7_gmx_s { + int L; +} P7_GMX; +static inline int select_c(const P7_PROFILE *gm, const P7_GMX *pp, const P7_GMX *gx, int i) { + float path[2]; + return ((path[0] > path[1]) ? p7T_C : p7T_E); +} +void p7_GOATrace(const P7_PROFILE *gm, const P7_GMX *pp, const P7_GMX *gx, P7_TRACE *tr) { + int i = gx->L; + int sprv, scur; + while (sprv != p7T_S) { + switch (sprv) { case p7T_C: scur = select_c(gm, pp, gx, i); break; } + if ( (scur == p7T_N || scur == p7T_J || scur == p7T_C) && scur == sprv) i--; + sprv = scur; + } +} diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index 7a159bb..610e807 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -2328,36 +2328,32 @@ bb_ends_with_multiway_branch (basic_block bb ATTRIBUTE_UNUSED) return false; } -/* Verify that the REGION is a Single Entry Multiple Exits region: make sure no - edge other than ENTRY is entering the REGION. */ +/* Verify that the REGION is a valid jump thread. A jump thread is a special + case of SEME Single Entry Multiple Exits region in which all nodes in the + REGION have exactly one incoming edge. The only exception is the first block + that may not have been connected to the rest of the cfg yet. */ DEBUG_FUNCTION void -verify_seme (edge entry, basic_block *region, unsigned n_region) +verify_jump_thread (basic_block *region, unsigned n_region) { - bitmap bbs = BITMAP_ALLOC (NULL); - for (unsigned i = 0; i < n_region; i++) - bitmap_set_bit (bbs, region[i]->index); + gcc_assert (EDGE_COUNT (region[i]->preds) <= 1); +} - for (unsigned i = 0; i < n_region; i++) - { - edge e; - edge_iterator ei; - basic_block bb = region[i]; +/* Return true when BB is one of the first N items in BBS. */ - /* All predecessors other than ENTRY->src should be in the region. */ - for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ei_next (&ei)) - if (e != entry) - gcc_assert (bitmap_bit_p (bbs, e->src->index)); - } +static inline bool +bb_in_bbs (basic_block bb, basic_block *bbs, int n) +{ + for (int i = 0; i < n; i++) + if (bb == bbs[i]) + return true; - BITMAP_FREE (bbs); + return false; } -/* Duplicates a Single Entry Multiple Exit REGION (set of N_REGION basic - blocks). The ENTRY edge is redirected to the duplicate of the region. If - REGION is not a Single Entry region, ignore any incoming edges other than - ENTRY: this makes the copied region a Single Entry region. +/* Duplicates a jump-thread path of N_REGION basic blocks. + The ENTRY edge is redirected to the duplicate of the region. Remove the last conditional statement in the last basic block in the REGION, and create a single fallthru edge pointing to the same destination as the @@ -2369,7 +2365,7 @@ verify_seme (edge entry, basic_block *region, unsigned n_region) Returns false if it is unable to copy the region, true otherwise. */ static bool -duplicate_seme_region (edge entry, edge exit, +duplicate_thread_path (edge entry, edge exit, basic_block *region, unsigned n_region, basic_block *region_copy) { @@ -2428,7 +2424,53 @@ duplicate_seme_region (edge entry, edge exit, } copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop, - split_edge_bb_loc (entry), 0); + split_edge_bb_loc (entry), false); + + /* Fix up: copy_bbs redirects all edges pointing to copied blocks. The + following code ensures that all the edges exiting the jump-thread path are + redirected back to the original code: these edges are exceptions + invalidating the property that is propagated by executing all the blocks of + the jump-thread path in order. */ + + for (i = 0; i < n_region; i++) + { + edge e; + edge_iterator ei; + basic_block bb = region_copy[i]; + + if (single_succ_p (bb)) + { + /* Make sure the successor is the next node in the path. */ + gcc_assert (i + 1 == n_region + || region_copy[i + 1] == single_succ_edge (bb)->dest); + continue; + } + + /* Special case the last block on the path: make sure that it does not + jump back on the copied path. */ + if (i + 1 == n_region) + { + FOR_EACH_EDGE (e, ei, bb->succs) + if (bb_in_bbs (e->dest, region_copy, n_region - 1)) + { + basic_block orig = get_bb_original (e->dest); + if (orig) + redirect_edge_and_branch_force (e, orig); + } + continue; + } + + /* Redirect all other edges jumping to non-adjacent blocks back to the + original code. */ + FOR_EACH_EDGE (e, ei, bb->succs) + if (region_copy[i + 1] != e->dest) + { + basic_block orig = get_bb_original (e->dest); + if (orig) + redirect_edge_and_branch_force (e, orig); + } + } + if (total_count) { scale_bbs_frequencies_gcov_type (region, n_region, @@ -2445,8 +2487,7 @@ duplicate_seme_region (edge entry, edge exit, } #ifdef ENABLE_CHECKING - /* Make sure no edge other than ENTRY is entering the copied region. */ - verify_seme (entry, region_copy, n_region); + verify_jump_thread (region_copy, n_region); #endif /* Remove the last branch in the jump thread path. */ @@ -2550,7 +2591,7 @@ thread_through_all_blocks (bool may_peel_loop_headers) for (unsigned int j = 0; j < len - 1; j++) region[j] = (*path)[j]->e->dest; - if (duplicate_seme_region (entry, exit, region, len - 1, NULL)) + if (duplicate_thread_path (entry, exit, region, len - 1, NULL)) { /* We do not update dominance info. */ free_dominance_info (CDI_DOMINATORS); -- 1.7.2.5