From patchwork Tue Nov 18 22:19:33 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 412211 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 AC90714010F for ; Wed, 19 Nov 2014 09:19:51 +1100 (AEDT) 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=bXv+/E6/AjS3JFgTr clET9USC668JI1llKdXKvfeNeFgcCH2y5sREAjLb2RoNJfSjpDDZpmtOI5cw0HGc cOgdqB0bd8a7DSr0+hR8uJP083LURf8b9Cin993JHQ14DQ6XNUd3iKYqWwemLskb QnAyJ4Pyog+Vqj4rfHvaflQh1Q= 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=Bd1q3j5lEiZZDjaA+Gnz8GK kmPs=; b=mUIgV7y0bDt9ncaPdityMhCsDlNXjFys1ljfafxnzp2HnD/CyCQuqmF SCFUbh1LMjlyUtXVWBLLAU5Y/ofWVLMd63MQdyte14lYOG4ivBSrCYaowK597UHy X4KArO45H8giNQpGG082jNvHjx5rVRpsU1zsL3pTUBXF8EzVMHAQ= Received: (qmail 30124 invoked by alias); 18 Nov 2014 22:19:42 -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 30114 invoked by uid 89); 18 Nov 2014 22:19:41 -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-ie0-f174.google.com Received: from mail-ie0-f174.google.com (HELO mail-ie0-f174.google.com) (209.85.223.174) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Tue, 18 Nov 2014 22:19:38 +0000 Received: by mail-ie0-f174.google.com with SMTP id rl12so4597178iec.33 for ; Tue, 18 Nov 2014 14:19:36 -0800 (PST) X-Received: by 10.43.127.73 with SMTP id gz9mr36645075icc.6.1416349176128; Tue, 18 Nov 2014 14:19:36 -0800 (PST) Received: from f1.c.bardezibar.internal (81.37.148.146.bc.googleusercontent.com. [146.148.37.81]) by mx.google.com with ESMTPSA id a4sm8397496igx.10.2014.11.18.14.19.34 for (version=SSLv3 cipher=RC4-SHA bits=128/128); Tue, 18 Nov 2014 14:19:35 -0800 (PST) Date: Tue, 18 Nov 2014 22:19:33 +0000 From: Sebastian Pop To: Richard Biener Cc: Jeff Law , James Greenhalgh , Steve Ellcey , GCC Patches Subject: Re: [Patch] Improving jump-thread pass for PR 54742 Message-ID: <20141118221933.GA7298@f1.c.bardezibar.internal> References: <1408480796.31355.7.camel@ubuntu-sellcey> <20140821094109.GA20536@arm.com> <53FB73C0.7090507@redhat.com> <20140926201451.GA16704@f1.c.bardezibar.internal> <20141026213433.GA22140@f1.c.bardezibar.internal> <20141111011404.GA23088@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 Tue, Nov 11, 2014 at 2:14 AM, Sebastian Pop wrote: > > Hi Jeff, > > > > I have adapted the code generation part from James' patch to current trunk, and > > the resulting patch gets the 30% speedup on coremark and passes bootstrap of GCC. > > > > Ok for trunk? > > In addition to missing documentation for the parameters > > + /* If we are copying an abnormally shaped region, keep track of > + which block will become our loop header. */ > + if ((region[i] != entry->dest && region[i] == loop->header) > + || (region[i] != entry->src && region[i] == loop->latch)) > + { > + save_loop_details = true; > + memo_loop_latch_no = i; > + memo_loop_header_no = i; > + } > > this looks bogus as you overwrite latch/header. Right, this should be: if (region[i] != entry->dest && region[i] == loop->header) { save_loop_details = true; memo_loop_header_no = i; } if (region[i] != entry->src && region[i] == loop->latch) { save_loop_details = true; memo_loop_latch_no = i; } > I wonder what you > tried to fix with this as "abnormally shaped" isn't sth we support > given the check before (all blocks must belong to the same loop > and thus entry is always the loop header or there is no loop)? > The regions that we duplicate start inside a loop and stay inside the same loop, and the jump threading path is not allowed to go in deeper nested loops. The reason why we need to modify the sese duplication function is that the sese region that we need to duplicate starts at an arbitrary place inside the loop, whereas the current user of the sese duplication function tree-ssa-loop-ch.c:245 starts at the edge entering the loop and exits at the latch edge. > I'll leave the rest to Jeff but it looks good to me from an overall > structure. > Thanks for your review. Sebastian PS: Patch passed bootstrap and regtest on x86_64-linux. PS: I have run some perf analysis with the patch: - on a bootstrap of GCC I see 3209 FSM jump threads - libpng and libjpeg contain FSM jump threads, the perf increase is in the 1% (measured on simulators and reduced data sets) - coremark gets jump threaded (as expected) - I'm setting up the llvm test-suite and I will report perf differences From aee8e01469c05e370b757b20c357a1c9dae57950 Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Fri, 26 Sep 2014 14:54:20 -0500 Subject: [PATCH] extend jump thread for finite state automata PR 54742 Adapted from a patch from James Greenhalgh. * params.def (max-fsm-thread-path-insns, max-fsm-thread-length, max-fsm-thread-paths): New. * doc/invoke.texi (max-fsm-thread-path-insns, max-fsm-thread-length, max-fsm-thread-paths): Documented. * testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c: New. * tree-cfg.c (gimple_duplicate_sese_region): Save and restore loop header and latch. * tree-ssa-threadedge.c (simplify_control_stmt_condition): Restore the original value of cond when simplification fails. (fsm_find_thread_path): New. (fsm_find_control_statement_thread_paths): New. (fsm_thread_through_normal_block): Call find_control_statement_thread_paths. * tree-ssa-threadupdate.c (dump_jump_thread_path): Pretty print EDGE_START_FSM_THREAD. (thread_through_all_blocks): Generate code for EDGE_START_FSM_THREAD edges calling gimple_duplicate_sese_region. * tree-ssa-threadupdate.h (jump_thread_edge_type): Add EDGE_START_FSM_THREAD. --- gcc/doc/invoke.texi | 12 ++ gcc/params.def | 15 ++ gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c | 38 +++++ gcc/tree-cfg.c | 26 ++- gcc/tree-ssa-threadedge.c | 201 ++++++++++++++++++++++- gcc/tree-ssa-threadupdate.c | 52 +++++- gcc/tree-ssa-threadupdate.h | 1 + 7 files changed, 340 insertions(+), 5 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 13270bc..613edbb 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -10586,6 +10586,18 @@ large and significantly increase compile time at optimization level @option{-O1} and higher. This parameter is a maximum nubmer of statements in a single generated constructor. Default value is 5000. +@item max-fsm-thread-path-insns +Maximum number of instructions to copy when duplicating blocks on a +finite state automaton jump thread path. The default is 100. + +@item max-fsm-thread-length +Maximum number of basic blocks on a finite state automaton jump thread +path. The default is 10. + +@item max-fsm-thread-paths +Maximum number of new jump thread paths to create for a finite state +automaton. The default is 50. + @end table @end table diff --git a/gcc/params.def b/gcc/params.def index d2d2add..55c287e 100644 --- a/gcc/params.def +++ b/gcc/params.def @@ -1125,6 +1125,21 @@ DEFPARAM (PARAM_CHKP_MAX_CTOR_SIZE, "Maximum number of statements to be included into a single static " "constructor generated by Pointer Bounds Checker", 5000, 100, 0) + +DEFPARAM (PARAM_MAX_FSM_THREAD_PATH_INSNS, + "max-fsm-thread-path-insns", + "Maximum number of instructions to copy when duplicating blocks on a finite state automaton jump thread path", + 100, 1, 999999) + +DEFPARAM (PARAM_MAX_FSM_THREAD_LENGTH, + "max-fsm-thread-length", + "Maximum number of basic blocks on a finite state automaton jump thread path", + 10, 1, 999999) + +DEFPARAM (PARAM_MAX_FSM_THREAD_PATHS, + "max-fsm-thread-paths", + "Maximum number of new jump thread paths to create for a finite state automaton", + 50, 1, 999999) /* Local variables: 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..310d3db --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c @@ -0,0 +1,38 @@ +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-cfg.c b/gcc/tree-cfg.c index ee10bc6..297749f 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -5949,10 +5949,12 @@ gimple_duplicate_sese_region (edge entry, edge exit, { unsigned i; bool free_region_copy = false, copying_header = false; + bool save_loop_details = false; struct loop *loop = entry->dest->loop_father; edge exit_copy; vec doms; edge redirected; + int memo_loop_header_no = 0, memo_loop_latch_no = 0; int total_freq = 0, entry_freq = 0; gcov_type total_count = 0, entry_count = 0; @@ -5970,9 +5972,20 @@ gimple_duplicate_sese_region (edge entry, edge exit, if (region[i]->loop_father != loop) return false; - if (region[i] != entry->dest - && region[i] == loop->header) - return false; + /* If we are copying a region that starts and ends in an arbirary place in + the loop: keep track of which block will become our loop header. */ + if (region[i] != entry->dest && region[i] == loop->header) + { + save_loop_details = true; + memo_loop_header_no = i; + } + + /* And which block will become our loop latch. */ + if (region[i] != entry->src && region[i] == loop->latch) + { + save_loop_details = true; + memo_loop_latch_no = i; + } } /* In case the function is used for loop header copying (which is the primary @@ -6055,6 +6068,13 @@ gimple_duplicate_sese_region (edge entry, edge exit, loop->latch = exit->src; } + /* Restore loop details if we were asked to save them. */ + if (save_loop_details) + { + loop->header = region[memo_loop_header_no]; + loop->latch = region[memo_loop_latch_no]; + } + /* Redirect the entry and add the phi node arguments. */ redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest)); gcc_assert (redirected != NULL); diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c index d5b9696..edd3c49 100644 --- a/gcc/tree-ssa-threadedge.c +++ b/gcc/tree-ssa-threadedge.c @@ -56,6 +56,8 @@ along with GCC; see the file COPYING3. If not see #include "params.h" #include "tree-ssa-threadedge.h" #include "builtins.h" +#include "cfg.h" +#include "cfganal.h" /* To avoid code explosion due to jump threading, we limit the number of statements we are going to copy. This variable @@ -660,6 +662,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. @@ -688,6 +691,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; @@ -947,6 +956,173 @@ 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 +fsm_find_thread_path (basic_block start_bb, basic_block end_bb, + vec *&path, + hash_set *visited_bbs, int n_insns) +{ + if (start_bb == end_bb) + { + vec_safe_push (path, start_bb); + return true; + } + + if (!visited_bbs->add (start_bb)) + { + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, start_bb->succs) + if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, n_insns)) + { + vec_safe_push (path, start_bb); + return true; + } + } + + return false; +} + +static int max_threaded_paths; + +/* We trace the value of the variable EXPR back through any phi nodes looking + for places where it gets a constant value and save the path. Stop after + having recorded MAX_PATHS jump threading paths. */ + +static void +fsm_find_control_statement_thread_paths (tree expr, + hash_set *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) + { + hash_set *visited_bbs = new hash_set; + + if (fsm_find_thread_path (var_bb, e->src, next_path, visited_bbs, 0)) + ++e_count; + + delete 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 + || visited_phis->add (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 (); + int joiners = 0; + + 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_FSM_THREAD; + else if (single_pred_p (e->src)) + kind = EDGE_NO_COPY_SRC_BLOCK; + else { + kind = EDGE_COPY_SRC_JOINER_BLOCK; + ++joiners; + } + + jump_thread_edge *x = new jump_thread_edge (e, kind); + jump_thread_path->safe_push (x); + } + + /* Add the edge taken when the control variable has value ARG. */ + edge taken_edge = find_taken_edge ((*path)[0], arg); + jump_thread_edge *x + = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK); + jump_thread_path->safe_push (x); + + /* A path with less than 3 nodes should not be jump-threaded. */ + if (n > 2 && n < PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH) + && max_threaded_paths > 0) + { + int n_insns = 0; + gimple_stmt_iterator gsi; + + for (j = 1; j < n - 1; j++) + for (gsi = gsi_start_bb ((*path)[j]); !gsi_end_p (gsi); + gsi_next (&gsi)) + ++n_insns; + + if (n_insns < PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS)) + { + register_jump_thread (jump_thread_path); + --max_threaded_paths; + } + } + } + else if (TREE_CODE (arg) == SSA_NAME) + fsm_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. @@ -1032,7 +1208,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); @@ -1078,6 +1257,26 @@ thread_through_normal_block (edge e, backedge_seen_p); return 1; } + + if (TREE_CODE (cond) != SSA_NAME + || e->dest->loop_father != e->src->loop_father) + 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); + hash_set *visited_phis = new hash_set; + + max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS); + fsm_find_control_statement_thread_paths (cond, visited_phis, bb_path); + + delete visited_phis; + vec_free (bb_path); + + return -1; } return 0; } diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index 151ed83..ec8e21f 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -167,8 +167,9 @@ dump_jump_thread_path (FILE *dump_file, vec path, bool registering) { fprintf (dump_file, - " %s jump thread: (%d, %d) incoming edge; ", + " %s%s jump thread: (%d, %d) incoming edge; ", (registering ? "Registering" : "Cancelling"), + (path[0]->type == EDGE_START_FSM_THREAD ? " FSM": ""), path[0]->e->src->index, path[0]->e->dest->index); for (unsigned int i = 1; i < path.length (); i++) @@ -2343,6 +2344,55 @@ thread_through_all_blocks (bool may_peel_loop_headers) threaded_blocks = BITMAP_ALLOC (NULL); memset (&thread_stats, 0, sizeof (thread_stats)); + for (i = 0; i < paths.length ();) + { + vec *path = paths[i]; + edge entry = (*path)[0]->e; + + if ((*path)[0]->type != EDGE_START_FSM_THREAD + /* Do not jump-thread twice from the same block. */ + || bitmap_bit_p (threaded_blocks, entry->src->index)) { + i++; + continue; + } + + unsigned len = path->length (); + edge exit = (*path)[len - 1]->e; + basic_block *region = XNEWVEC (basic_block, len - 1); + + for (unsigned int j = 0; j < len - 1; j++) + region[j] = (*path)[j]->e->dest; + + bool success = gimple_duplicate_sese_region (entry, exit, region, + len - 1, NULL, 0); + delete_jump_thread_path (path); + paths.unordered_remove (i); + + if (success) + { + /* We do not update dominance info. */ + free_dominance_info (CDI_DOMINATORS); + bitmap_set_bit (threaded_blocks, entry->src->index); + } + } + + for (i = 0; i < paths.length ();) + { + vec *path = paths[i]; + edge entry = (*path)[0]->e; + + /* Do not jump-thread twice from the same block. */ + if (bitmap_bit_p (threaded_blocks, entry->src->index)) + { + delete_jump_thread_path (path); + paths.unordered_remove (i); + } + else + i++; + } + + bitmap_clear (threaded_blocks); + mark_threaded_blocks (threaded_blocks); initialize_original_copy_tables (); diff --git a/gcc/tree-ssa-threadupdate.h b/gcc/tree-ssa-threadupdate.h index 426aca5..42c3a9e 100644 --- a/gcc/tree-ssa-threadupdate.h +++ b/gcc/tree-ssa-threadupdate.h @@ -26,6 +26,7 @@ extern bool thread_through_all_blocks (bool); enum jump_thread_edge_type { EDGE_START_JUMP_THREAD, + EDGE_START_FSM_THREAD, EDGE_COPY_SRC_BLOCK, EDGE_COPY_SRC_JOINER_BLOCK, EDGE_NO_COPY_SRC_BLOCK -- 2.1.0.243.g30d45f7