From patchwork Wed Mar 18 22:35:41 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 451661 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 C46ED1400D5 for ; Thu, 19 Mar 2015 09:36:33 +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=gwfISMsV; 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:subject:message-id:mime-version:content-type; q=dns; s= default; b=dEcLrA84FP5H+7TUN2SmrmP6aK5vktYmBJKJS0SQr6mZ84q0dSf5b q2BFadFFVclf2AJMVUHN5MCGdD7GUpQ8c32ow4X0PoKLKIgqaNncUSAgHgI0RuDK nYgX46T0Hp0VSYgBUeXE5RArR3jG1uIYDsy/Gi2CgbC+CmqMSfvCAk= 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:subject:message-id:mime-version:content-type; s= default; bh=ZW8j0qB9wimFHUKYvgRl5hDIR1k=; b=gwfISMsVbRF4lS7xwzkt RG9blCqkROG1a06v5zhsh7aT3yDtzK0jYkRltJTnXW4UCFHGK5aU4Pb2XRLRAA6j N3cfLAWSiDSRqXITlPyEVDsrZ/OySqOTJVLSFXw9+Ir/wV2YjVBh3UutIyo1Xj1J xOssk9S+CQA/lElzKO4g6ho= Received: (qmail 76064 invoked by alias); 18 Mar 2015 22:35:48 -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 75975 invoked by uid 89); 18 Mar 2015 22:35:47 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=0.5 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, KAM_FROM_URIBL_PCCC, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=no version=3.3.2 X-HELO: mail-ig0-f179.google.com Received: from mail-ig0-f179.google.com (HELO mail-ig0-f179.google.com) (209.85.213.179) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Wed, 18 Mar 2015 22:35:46 +0000 Received: by igbqf9 with SMTP id qf9so7147991igb.1 for ; Wed, 18 Mar 2015 15:35:44 -0700 (PDT) X-Received: by 10.107.151.73 with SMTP id z70mr55421159iod.41.1426718144071; Wed, 18 Mar 2015 15:35:44 -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 q78sm11887035ioi.28.2015.03.18.15.35.42 (version=SSLv3 cipher=RC4-SHA bits=128/128); Wed, 18 Mar 2015 15:35:42 -0700 (PDT) Date: Wed, 18 Mar 2015 22:35:41 +0000 From: Sebastian Pop To: gcc-patches@gcc.gnu.org, Jeff Law Subject: Fix PR 65177: diamonds are not valid execution threads for jump threading Message-ID: <20150318223541.GA17168@f1.c.bardezibar.internal> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) X-IsSubscribed: yes Hi, the attached patch fixes PR 65177 in which the code generator of FSM jump thread would create a diamond on the copied path: see https://gcc.gnu.org/PR65177#c18 for a detailed description. The patch is renaming SEME into jump_thread as the notion of SEME is more general than the special case that we are interested in, in the case of jump-threading: an execution thread to be jump-threaded has the property that each node on the path has exactly one predecessor, disallowing any other control flow like diamonds or back-edge loops within the SEME region. The patch passes regstrap on x86-64-linux, and fixes the make check of hmmer. Ok to commit? Thanks, Sebastian From 8c82e8b8c7d864c009bb7a116faf4acf64954704 Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Tue, 17 Mar 2015 20:28:19 +0100 Subject: [PATCH] fix 65177 PR tree-optimization/65177 * cfghooks.c (bb_in_bbs): New. (copy_bbs): Add parameter make_jump_thread. * cfghooks.h (copy_bbs): Update definition. * cfgloopmanip.c (duplicate_loop_to_header_edge): Update use of copy_bbs. * trans-mem.c (ipa_uninstrument_transaction): Same. * tree-cfg.c (gimple_duplicate_sese_region): Same. (gimple_duplicate_sese_tail): Same. * tree-vect-loop-manip.c (slpeel_tree_duplicate_loop_to_edge_cfg): Same. * tree-ssa-threadupdate.c (verify_seme): Renamed verify_jump_thread. --- gcc/cfghooks.c | 39 +++++++++++++++++++++++++++++++++++++-- gcc/cfghooks.h | 2 +- gcc/cfgloopmanip.c | 2 +- gcc/trans-mem.c | 2 +- gcc/tree-cfg.c | 4 ++-- gcc/tree-ssa-threadupdate.c | 31 ++++++++----------------------- gcc/tree-vect-loop-manip.c | 2 +- 7 files changed, 51 insertions(+), 31 deletions(-) diff --git a/gcc/cfghooks.c b/gcc/cfghooks.c index abeab8c..1a9e2f9 100644 --- a/gcc/cfghooks.c +++ b/gcc/cfghooks.c @@ -1300,6 +1300,18 @@ end: return ret; } +/* Return true when BB is one of the first N items in BBS. */ + +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; + + return false; +} + /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks are placed into array NEW_BBS in the same order. Edges from basic blocks in BBS are also duplicated and copies of those that lead into BBS are @@ -1321,12 +1333,16 @@ end: also in the same order. Newly created basic blocks are put after the basic block AFTER in the - instruction stream, and the order of the blocks in BBS array is preserved. */ + instruction stream, and the order of the blocks in BBS array is preserved. + + When MAKE_JUMP_THREAD is true, only redirect edges to consecutive elements of + BBS. */ void copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs, edge *edges, unsigned num_edges, edge *new_edges, - struct loop *base, basic_block after, bool update_dominance) + struct loop *base, basic_block after, bool update_dominance, + bool make_jump_thread) { unsigned i, j; basic_block bb, new_bb, dom_bb; @@ -1385,6 +1401,25 @@ copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs, if (!(e->dest->flags & BB_DUPLICATED)) continue; + + if (make_jump_thread) + { + /* When creating a jump-thread, we only redirect edges to + consecutive basic blocks. */ + if (i + 1 < n) + { + if (e->dest != bbs[i + 1]) + continue; + } + else + { + /* Do not jump back into the jump-thread path from the last + BB. */ + if (bb_in_bbs (e->dest, bbs, n - 1)) + continue; + } + } + redirect_edge_and_branch_force (e, get_bb_copy (e->dest)); } } diff --git a/gcc/cfghooks.h b/gcc/cfghooks.h index 4a1340e..9a17180 100644 --- a/gcc/cfghooks.h +++ b/gcc/cfghooks.h @@ -238,7 +238,7 @@ extern void lv_add_condition_to_bb (basic_block, basic_block, basic_block, extern bool can_copy_bbs_p (basic_block *, unsigned); extern void copy_bbs (basic_block *, unsigned, basic_block *, edge *, unsigned, edge *, struct loop *, - basic_block, bool); + basic_block, bool, bool); void account_profile_record (struct profile_record *, int); diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c index 45cc85d..e987b6b 100644 --- a/gcc/cfgloopmanip.c +++ b/gcc/cfgloopmanip.c @@ -1337,7 +1337,7 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, /* Copy bbs. */ copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop, - place_after, true); + place_after, true, false); place_after = new_spec_edges[SE_LATCH]->src; if (flags & DLTHE_RECORD_COPY_NUMBER) diff --git a/gcc/trans-mem.c b/gcc/trans-mem.c index 078c2da..eb88735 100644 --- a/gcc/trans-mem.c +++ b/gcc/trans-mem.c @@ -4162,7 +4162,7 @@ ipa_uninstrument_transaction (struct tm_region *region, basic_block *new_bbs = XNEWVEC (basic_block, n); copy_bbs (queue.address (), n, new_bbs, NULL, 0, NULL, NULL, transaction_bb, - true); + true, false); edge e = make_edge (transaction_bb, new_bbs[0], EDGE_TM_UNINSTRUMENTED); add_phi_args_after_copy (new_bbs, n, e); diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index 006bc08..e769fb7 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -6071,7 +6071,7 @@ gimple_duplicate_sese_region (edge entry, edge exit, } copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop, - split_edge_bb_loc (entry), update_dominance); + split_edge_bb_loc (entry), update_dominance, false); if (total_count) { scale_bbs_frequencies_gcov_type (region, n_region, @@ -6240,7 +6240,7 @@ gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNU } copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop, - split_edge_bb_loc (exit), true); + split_edge_bb_loc (exit), true, false); if (total_count) { scale_bbs_frequencies_gcov_type (region, n_region, diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index 7a159bb..96a83fa 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -2328,30 +2328,16 @@ 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); - for (unsigned i = 0; i < n_region; i++) - { - edge e; - edge_iterator ei; - basic_block bb = region[i]; - - /* 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)); - } - - BITMAP_FREE (bbs); + gcc_assert (EDGE_COUNT (region[i]->preds) <= 1); } /* Duplicates a Single Entry Multiple Exit REGION (set of N_REGION basic @@ -2428,7 +2414,7 @@ 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, true); if (total_count) { scale_bbs_frequencies_gcov_type (region, n_region, @@ -2445,8 +2431,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. */ diff --git a/gcc/tree-vect-loop-manip.c b/gcc/tree-vect-loop-manip.c index a344a49..c561f46 100644 --- a/gcc/tree-vect-loop-manip.c +++ b/gcc/tree-vect-loop-manip.c @@ -814,7 +814,7 @@ slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, exit = single_exit (scalar_loop); copy_bbs (bbs, scalar_loop->num_nodes + 1, new_bbs, &exit, 1, &new_exit, NULL, - e->src, true); + e->src, true, false); exit = single_exit (loop); basic_block new_preheader = new_bbs[scalar_loop->num_nodes]; -- 1.7.2.5