From patchwork Wed Oct 23 13:55:46 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 285674 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 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 75D0F2C032E for ; Thu, 24 Oct 2013 00:55:56 +1100 (EST) 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:subject:content-type; q= dns; s=default; b=aQqaVyl1qhqOuN+1jmWDE5oyWWoNm8+8RrdH5rqdbJsUQj jAXYQcuDMJZiBml1Z+YpjGWqO7bQ0uGnR1wM6LhlBM/E1MkSfyNq74O+W8P6ZzYy Jm7C7423lTZA+x6ZNekmNAM743kmikqg0G+O9JbNyklHTZmA0QNr9qnE4H0s0= 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:subject:content-type; s= default; bh=44OTeFH8nFlHo8WEHxyHI4/+HDU=; b=nuM+EElGHQiIvEcI1h/B dY1KgHKDgZIcOKs8C6al9QBxMsGB6jJoBr7NajAOTAwxWggYLpP/Bc5faLcIVEW0 EZeKQANe2AHHvbHJ3fMRzpMHz7jQPWAQWO0VakbdHzOe6Mozt/D2o3JCuHV8kslI c6eFaNBIQhnEJWi9+TxT7Jg= Received: (qmail 14100 invoked by alias); 23 Oct 2013 13:55:50 -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 14085 invoked by uid 89); 23 Oct 2013 13:55:49 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-4.5 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 23 Oct 2013 13:55:48 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r9NDtkJY020365 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Wed, 23 Oct 2013 09:55:47 -0400 Received: from stumpy.slc.redhat.com (ovpn-113-151.phx2.redhat.com [10.3.113.151]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id r9NDtkS1031922 for ; Wed, 23 Oct 2013 09:55:46 -0400 Message-ID: <5267D562.5090900@redhat.com> Date: Wed, 23 Oct 2013 07:55:46 -0600 From: Jeff Law User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.0 MIME-Version: 1.0 To: gcc-patches Subject: [PATCH] More threading cleanups X-IsSubscribed: yes During testing of the generalized FSA opt I ran into a case where we tried to thread through a joiner with abnormal outgoing edges. Since we can't reliably clone the joiner and redirect just one of its outgoing edges in this case, we need to avoid even trying to thread through such blocks. While looking at that I realized we don't need the code to filter out jump threading opportunities involving joiner blocks. We can avoid the unnecessary duplication by first handling all the jump threads which do not require a joiner block, then handling the jump threads which do require a joiner block. Finally, I was able to look at a dangling AUX field problem that I've seen a few times. While I haven't seen it on the trunk, I believe it's just latent. When we thread the latch edge to an exit edge, we clear loop->header. If we had another thread path into that same loop from outside, the second thread path will be ignored because loop->header is NULL. This leaves a dangling edge AUX field, which we need to clear. All three issues are addressed by this patch. Bootstrapped and regression tested on x86_64-unknown-linux-gnu. Installed on the trunk. commit 9e33df4427bf4e13c32d3296fcdc1ee1b1fd7bfa Author: Jeff Law Date: Wed Oct 23 07:53:46 2013 -0600 * tree-ssa-threadedge.c (thread_across_edge): Do not allow threading through joiner blocks with abnormal outgoing edges. * tree-ssa-threadupdate.c (thread_block_1): Renamed from thread_block. Add parameter JOINERS, to allow/disallow threading through joiner blocks. (thread_block): New. Call thread_block_1. (mark_threaded_blocks): Remove code to filter out certain cases of threading through joiner blocks. (thread_through_all_blocks): Document how we can have a dangling edge AUX field and clear it. diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 6132515..acd6620 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,17 @@ +2013-10-23 Jeff Law + + * tree-ssa-threadedge.c (thread_across_edge): Do not allow threading + through joiner blocks with abnormal outgoing edges. + + * tree-ssa-threadupdate.c (thread_block_1): Renamed from thread_block. + Add parameter JOINERS, to allow/disallow threading through joiner + blocks. + (thread_block): New. Call thread_block_1. + (mark_threaded_blocks): Remove code to filter out certain cases + of threading through joiner blocks. + (thread_through_all_blocks): Document how we can have a dangling + edge AUX field and clear it. + 2013-10-23 Ian Lance Taylor * doc/invoke.texi (Option Summary): Remove -fno-default-inline. diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c index bbc4f9b..810908b 100644 --- a/gcc/tree-ssa-threadedge.c +++ b/gcc/tree-ssa-threadedge.c @@ -1040,6 +1040,16 @@ thread_across_edge (gimple dummy_cond, edge_iterator ei; bool found; + /* If E->dest has abnormal outgoing edges, then there's no guarantee + we can safely redirect any of the edges. Just punt those cases. */ + FOR_EACH_EDGE (taken_edge, ei, e->dest->succs) + if (taken_edge->flags & EDGE_ABNORMAL) + { + remove_temporary_equivalences (stack); + BITMAP_FREE (visited); + return; + } + /* Look at each successor of E->dest to see if we can thread through it. */ FOR_EACH_EDGE (taken_edge, ei, e->dest->succs) { diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index bde81a8..1027191 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -616,10 +616,12 @@ redirection_block_p (basic_block bb) the appropriate duplicate of BB. If NOLOOP_ONLY is true, we only perform the threading as long as it - does not affect the structure of the loops in a nontrivial way. */ + does not affect the structure of the loops in a nontrivial way. + + If JOINERS is true, then thread through joiner blocks as well. */ static bool -thread_block (basic_block bb, bool noloop_only) +thread_block_1 (basic_block bb, bool noloop_only, bool joiners) { /* E is an incoming edge into BB that we may or may not want to redirect to a duplicate of BB. */ @@ -642,7 +644,9 @@ thread_block (basic_block bb, bool noloop_only) e = loop_latch_edge (loop); vec *path = THREAD_PATH (e); - if (path) + if (path + && (((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && joiners) + || ((*path)[1]->type == EDGE_COPY_SRC_BLOCK && !joiners))) { for (unsigned int i = 1; i < path->length (); i++) { @@ -666,6 +670,11 @@ thread_block (basic_block bb, bool noloop_only) continue; vec *path = THREAD_PATH (e); + + if (((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && !joiners) + || ((*path)[1]->type == EDGE_COPY_SRC_BLOCK && joiners)) + continue; + e2 = path->last ()->e; if (!e2 || noloop_only) { @@ -762,6 +771,24 @@ thread_block (basic_block bb, bool noloop_only) return local_info.jumps_threaded; } +/* Wrapper for thread_block_1 so that we can first handle jump + thread paths which do not involve copying joiner blocks, then + handle jump thread paths which have joiner blocks. + + By doing things this way we can be as aggressive as possible and + not worry that copying a joiner block will create a jump threading + opportunity. */ + +static bool +thread_block (basic_block bb, bool noloop_only) +{ + bool retval; + retval = thread_block_1 (bb, noloop_only, false); + retval |= thread_block_1 (bb, noloop_only, true); + return retval; +} + + /* Threads edge E through E->dest to the edge THREAD_TARGET (E). Returns the copy of E->dest created during threading, or E->dest if it was not necessary to copy it (E is its single predecessor). */ @@ -1240,57 +1267,14 @@ mark_threaded_blocks (bitmap threaded_blocks) edge e; edge_iterator ei; - /* It is possible to have jump threads in which one is a subpath - of the other. ie, (A, B), (B, C), (C, D) where B is a joiner - block and (B, C), (C, D) where no joiner block exists. - - When this occurs ignore the jump thread request with the joiner - block. It's totally subsumed by the simpler jump thread request. - - This results in less block copying, simpler CFGs. More importantly, - when we duplicate the joiner block, B, in this case we will create - a new threading opportunity that we wouldn't be able to optimize - until the next jump threading iteration. - - So first convert the jump thread requests which do not require a - joiner block. */ + /* Move the jump threading requests from PATHS to each edge + which starts a jump thread path. */ for (i = 0; i < paths.length (); i++) { vec *path = paths[i]; - - if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK) - { - edge e = (*path)[0]->e; - e->aux = (void *)path; - bitmap_set_bit (tmp, e->dest->index); - } - } - - /* Now iterate again, converting cases where we want to thread - through a joiner block, but only if no other edge on the path - already has a jump thread attached to it. */ - for (i = 0; i < paths.length (); i++) - { - vec *path = paths[i]; - - - if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK) - { - unsigned int j; - - for (j = 0; j < path->length (); j++) - if ((*path)[j]->e->aux != NULL) - break; - - /* If we iterated through the entire path without exiting the loop, - then we are good to go, attach the path to the starting edge. */ - if (j == path->length ()) - { - edge e = (*path)[0]->e; - e->aux = path; - bitmap_set_bit (tmp, e->dest->index); - } - } + edge e = (*path)[0]->e; + e->aux = (void *)path; + bitmap_set_bit (tmp, e->dest->index); } /* If we have a joiner block (J) which has two successors S1 and S2 and @@ -1488,6 +1472,39 @@ thread_through_all_blocks (bool may_peel_loop_headers) retval |= thread_through_loop_header (loop, may_peel_loop_headers); } + /* Assume we had a jump thread path which went from the latch to the exit + and a path which goes from outside to inside the same loop. + + If the latch to exit was handled first, we will thread it and clear + loop->header. + + The second path will be ignored by thread_block because we're going + through a loop header. It will also be ignored by the loop above + because loop->header is NULL. + + This results in the second path never being threaded. The failure + mode is a dangling AUX field. + + This is inherently a bit of a pain to fix, so we just walk all the + blocks and all the incoming edges to those blocks and clear their + AUX fields. */ + basic_block bb; + edge_iterator ei; + edge e; + FOR_EACH_BB (bb) + { + FOR_EACH_EDGE (e, ei, bb->preds) + if (e->aux) + { + vec *path = THREAD_PATH (e); + + for (unsigned int i = 0; i < path->length (); i++) + delete (*path)[i]; + path->release (); + e->aux = NULL; + } + } + statistics_counter_event (cfun, "Jumps threaded", thread_stats.num_threaded_edges);