From patchwork Fri Sep 26 20:14:51 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 393951 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 22CEF1401EB for ; Sat, 27 Sep 2014 06:15:07 +1000 (EST) 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=kkQ5ib6u93xChw6hO rsZJY+fH3l8lW/kfkxAWdVIJL9TYjJH2afIbOGQRAhB8Ss7XkY3RjJwbeFAk/Azy B7l+lhatDX3bZgcF1qcAXNK25m2//YZdLbwCCleqQD2SVC5wU0XV+Zi/tO7XHNG9 7MOJdyuBQ8Un8eDby3vQyuHoTo= 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=nutblcslB5cHns7anQHaMuz Yy9k=; b=wnjMH0tlugi21ziduiI9ldWkB88wduUIqj4wzHm/+rcyNUseQv7RFin WqscFf1Rcr266OqgG5LHdB7hegiBZwHhgY9xwakt//A/+RuIMweEbXk5bsqkt0D6 AA2DaWhI1tgnYmcNjfir6J/xA7LscyRic2YlSygH4d68Tazfx8do= Received: (qmail 20122 invoked by alias); 26 Sep 2014 20:14:58 -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 20110 invoked by uid 89); 26 Sep 2014 20:14:57 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.6 required=5.0 tests=BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-ig0-f177.google.com Received: from mail-ig0-f177.google.com (HELO mail-ig0-f177.google.com) (209.85.213.177) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Fri, 26 Sep 2014 20:14:55 +0000 Received: by mail-ig0-f177.google.com with SMTP id h3so219450igd.4 for ; Fri, 26 Sep 2014 13:14:53 -0700 (PDT) X-Received: by 10.50.154.5 with SMTP id vk5mr16906770igb.39.1411762493497; Fri, 26 Sep 2014 13:14:53 -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 k6sm2622232ige.13.2014.09.26.13.14.52 for (version=SSLv3 cipher=RC4-SHA bits=128/128); Fri, 26 Sep 2014 13:14:52 -0700 (PDT) Date: Fri, 26 Sep 2014 20:14:51 +0000 From: Sebastian Pop To: Jeff Law Cc: Richard Biener , James Greenhalgh , Steve Ellcey , GCC Patches Subject: Re: [Patch] Switch elimination pass for PR 54742 Message-ID: <20140926201451.GA16704@f1.c.bardezibar.internal> References: <1408480796.31355.7.camel@ubuntu-sellcey> <20140821094109.GA20536@arm.com> <53FB73C0.7090507@redhat.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <53FB73C0.7090507@redhat.com> User-Agent: Mutt/1.5.21 (2010-09-15) X-IsSubscribed: yes Jeff Law wrote: > On 08/21/14 04:30, Richard Biener wrote: > >>It turns Jeff's jump-threading code in to a strange franken-pass of bits and > >>pieces of detection and optimisation, and would need some substantial > >>reworking to fit in with Jeff's changes last Autumn, but if it is more > >>likely to be acceptable for trunk then perhaps we could look to revive it. > >>It would be nice to reuse the path copy code Jeff added last year, but I > >>don't have much intuition as to how feasible that is. > >> > >>Was this the sort of thing that you were imagining? > > > >Yeah, didn't look too closely though. > It'd be pretty ugly I suspect. But it's probably worth pondering > since that approach would eliminate the concerns about the cost of > detection (which is problematical for the jump threader) by using > Steve's code for that. > > On the update side, I suspect most, if not all of the framework is > in place to handle this kind of update if the right threading paths > were passed to the updater. I can probably cobble together that > by-hand and see what the tree-ssa-threadupdate does with it. But > it'll be a week or so before I could look at it. I adapted the patch James has sent last year to use the new update paths mechanism. I verified that the attached patch does register all the paths that need to be threaded. Thread updater seems to have some problems handling the attached testcase (a simplified version of the testcase attached to the bug.) Jeff, could you please have a look at why the jump-thread updater is crashing? Let me know if you want me to continue looking at the problem. Thanks, Sebastian From 1f09b819559865be5a366e11a9c0f9bf495f91bc Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Fri, 26 Sep 2014 14:54:20 -0500 Subject: [PATCH] jump thread for PR 54742 Adapted from a patch from James Greenhalgh. * Makefile.in: Add dependence on pointer-set.o. * tree-ssa-threadedge.c: Include pointer-set.h. (simplify_control_stmt_condition): Restore the original value of cond when simplification fails. (find_thread_path): New. (find_control_statement_thread_paths): New. (thread_through_normal_block): Call find_control_statement_thread_paths. * testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c: New. --- gcc/Makefile.in | 1 + gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c | 32 +++++ gcc/tree-ssa-threadedge.c | 170 ++++++++++++++++++++++- 3 files changed, 202 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 6f251a5..ebaed55 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1310,6 +1310,7 @@ OBJS = \ opts-global.o \ passes.o \ plugin.o \ + pointer-set.o \ postreload-gcse.o \ postreload.o \ predict.o \ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c new file mode 100644 index 0000000..f3ef725 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c @@ -0,0 +1,32 @@ +int sum0, sum1, sum2, sum3; +int foo(char * s, char** ret) +{ + int state=0; + char c; + + for (; *s && state != 4; s++) + { + c = *s; + if (c == '*') + { + s++; + break; + } + switch (state) { + case 0: + if (c == '+') state = 1; + else if (c != '-') sum0+=c; + break; + case 1: + if (c == '+') state = 2; + else if (c == '-') state = 0; + else sum1+=c; + break; + default: + break; + } + + } + *ret = s; + return state; +} diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c index 3dee5ba..ee09841 100644 --- a/gcc/tree-ssa-threadedge.c +++ b/gcc/tree-ssa-threadedge.c @@ -49,6 +49,7 @@ along with GCC; see the file COPYING3. If not see #include "params.h" #include "tree-ssa-threadedge.h" #include "builtins.h" +#include "pointer-set.h" /* To avoid code explosion due to jump threading, we limit the number of statements we are going to copy. This variable @@ -628,6 +629,7 @@ simplify_control_stmt_condition (edge e, rather than use a relational operator. These are simpler to handle. */ if (TREE_CODE (cond) == SSA_NAME) { + tree original_lhs = cond; cached_lhs = cond; /* Get the variable's current value from the equivalence chains. @@ -656,6 +658,12 @@ simplify_control_stmt_condition (edge e, pass specific callback to try and simplify it further. */ if (cached_lhs && ! is_gimple_min_invariant (cached_lhs)) cached_lhs = (*simplify) (stmt, stmt); + + /* We couldn't find an invariant. But, callers of this + function may be able to do something useful with the + unmodified destination. */ + if (!cached_lhs) + cached_lhs = original_lhs; } else cached_lhs = NULL; @@ -915,6 +923,145 @@ thread_around_empty_blocks (edge taken_edge, return false; } +/* Return true if there is at least one path from START_BB to END_BB. + VISITED_BBS is used to make sure we don't fall into an infinite loop. */ + +static bool +find_thread_path (basic_block start_bb, basic_block end_bb, + vec *&path, + struct pointer_set_t *visited_bbs) +{ + if (start_bb == end_bb) + { + vec_safe_push (path, start_bb); + return true; + } + + if (!pointer_set_insert (visited_bbs, start_bb)) + { + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, start_bb->succs) + if (find_thread_path (e->dest, end_bb, path, visited_bbs)) + { + vec_safe_push (path, start_bb); + return true; + } + } + + return false; +} + +/* CTRL_STMT is a COND_EXPR or SWITCH_EXPR statement whose controlling + expression is the variable EXPR. We trace the value of the variable back + through any phi nodes looking for places where it gets a constant + value and save the path. */ + +static void +find_control_statement_thread_paths (tree expr, + struct pointer_set_t *visited_phis, + vec *&path) +{ + tree var = SSA_NAME_VAR (expr); + gimple def_stmt = SSA_NAME_DEF_STMT (expr); + basic_block var_bb = gimple_bb (def_stmt); + + if (var == NULL || var_bb == NULL) + return; + + vec *next_path; + vec_alloc (next_path, n_basic_blocks_for_fn (cfun)); + + basic_block last_bb_in_path = path->last (); + + /* Put the path from var_bb to last_bb_in_path into next_path. */ + if (var_bb != last_bb_in_path) + { + edge e; + int e_count = 0; + edge_iterator ei; + + FOR_EACH_EDGE (e, ei, last_bb_in_path->preds) + { + struct pointer_set_t *visited_bbs = pointer_set_create (); + + if (find_thread_path (var_bb, e->src, next_path, visited_bbs)) + e_count = e_count + 1; + + pointer_set_destroy (visited_bbs); + + /* If there is more than one path, stop. */ + if (e_count > 1) + { + vec_free (next_path); + return; + } + } + } + + // Visit PHI nodes once. + if (gimple_code (def_stmt) != GIMPLE_PHI + || pointer_set_insert (visited_phis, def_stmt)) { + vec_free (next_path); + return; + } + + // Append all the nodes from next_path to path. + vec_safe_splice (path, next_path); + gcc_assert (path->last () == var_bb); + + // Iterate over the arguments of PHI. + unsigned int i; + for (i = 0; i < gimple_phi_num_args (def_stmt); i++) + { + tree arg = gimple_phi_arg_def (def_stmt, i); + basic_block bbi = gimple_phi_arg_edge (def_stmt, i)->src; + + // Skip edges pointing outside the current loop. + if (!arg || var_bb->loop_father != bbi->loop_father) + continue; + + // Add BBI to the path. + vec_safe_push (path, bbi); + + if (TREE_CODE (arg) == INTEGER_CST) + { + int j, n = path->length (); + vec *jump_thread_path + = new vec (); + + for (j = 0; j < n-1; j++) + { + edge e = find_edge ((*path)[n - j - 1], + (*path)[n - j - 2]); + gcc_assert (e); + enum jump_thread_edge_type kind; + + if (j == 0) + kind = EDGE_START_JUMP_THREAD; + else if (single_pred_p (e->dest)) + kind = EDGE_COPY_SRC_BLOCK; + else + kind = EDGE_COPY_SRC_JOINER_BLOCK; + + jump_thread_edge *x = new jump_thread_edge (e, kind); + jump_thread_path->safe_push (x); + } + + register_jump_thread (jump_thread_path); + } + else if (TREE_CODE (arg) == SSA_NAME) + find_control_statement_thread_paths (arg, visited_phis, path); + + /* Remove BBI from the path. */ + path->pop (); + } + + /* Remove all the nodes that we added from next_path. */ + vec_safe_truncate (path, (path->length () - next_path->length ())); + vec_free (next_path); +} + /* We are exiting E->src, see if E->dest ends with a conditional jump which has a known value when reached via E. @@ -1000,7 +1147,10 @@ thread_through_normal_block (edge e, cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify, handle_dominating_asserts); - if (cond && is_gimple_min_invariant (cond)) + if (!cond) + return 0; + + if (is_gimple_min_invariant (cond)) { edge taken_edge = find_taken_edge (e->dest, cond); basic_block dest = (taken_edge ? taken_edge->dest : NULL); @@ -1046,6 +1196,24 @@ thread_through_normal_block (edge e, backedge_seen_p); return 1; } + + if (TREE_CODE (cond) != SSA_NAME) + return 0; + + /* When COND cannot be simplified, try to find paths from a control + statement back through the PHI nodes which would affect that control + statement. */ + vec *bb_path; + vec_alloc (bb_path, n_basic_blocks_for_fn (cfun)); + vec_safe_push (bb_path, e->dest); + struct pointer_set_t *visited_phis = pointer_set_create (); + + find_control_statement_thread_paths (cond, visited_phis, bb_path); + + pointer_set_destroy (visited_phis); + vec_free (bb_path); + + return -1; } return 0; } -- 2.1.0.243.g30d45f7