From 78cf0a232ee4314a9d668aab9b4b54f86b308111 Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Thu, 27 Aug 2015 17:11:21 -0500 Subject: port revision 219584 from linaro/gcc-4_9-branch gcc/ 2015-01-14 Yvan Roux Backport from trunk r218451. 2014-12-06 James Greenhalgh Sebastian Pop Brian Rzycki PR tree-optimization/54742 * 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. * tree-cfg.c (split_edge_bb_loc): Export. * tree-cfg.h (split_edge_bb_loc): Declared extern. * 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. (thread_through_normal_block): Call find_control_statement_thread_paths. * tree-ssa-threadupdate.c (dump_jump_thread_path): Pretty print EDGE_FSM_THREAD. (verify_seme): New. (duplicate_seme_region): New. (thread_through_all_blocks): Generate code for EDGE_FSM_THREAD edges calling duplicate_seme_region. * tree-ssa-threadupdate.h (jump_thread_edge_type): Add EDGE_FSM_THREAD. gcc/testsuite/ 2015-01-14 Yvan Roux Backport from trunk r218451. 2014-12-06 James Greenhalgh Sebastian Pop Brian Rzycki PR tree-optimization/54742 * gcc.dg/tree-ssa/ssa-dom-thread-6.c: New test. * gcc.dg/tree-ssa/ssa-dom-thread-7.c: New test. --- gcc-4.9/gcc/doc/invoke.texi | 12 + gcc-4.9/gcc/params.def | 15 ++ .../testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c | 43 ++++ .../testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c | 127 ++++++++++ gcc-4.9/gcc/tree-cfg.c | 2 +- gcc-4.9/gcc/tree-cfg.h | 1 + gcc-4.9/gcc/tree-ssa-threadedge.c | 275 ++++++++++++++++++++- gcc-4.9/gcc/tree-ssa-threadupdate.c | 203 ++++++++++++++- gcc-4.9/gcc/tree-ssa-threadupdate.h | 1 + 9 files changed, 676 insertions(+), 3 deletions(-) create mode 100644 gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c create mode 100644 gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c (limited to 'gcc-4.9') diff --git a/gcc-4.9/gcc/doc/invoke.texi b/gcc-4.9/gcc/doc/invoke.texi index f8350c418..b5d9c4ba0 100644 --- a/gcc-4.9/gcc/doc/invoke.texi +++ b/gcc-4.9/gcc/doc/invoke.texi @@ -10442,6 +10442,18 @@ is greater or equal to this number, use callbacks instead of inline checks. E.g. to disable inline code use @option{--param asan-instrumentation-with-call-threshold=0}. +@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-4.9/gcc/params.def b/gcc-4.9/gcc/params.def index 3d2c913fd..518d379ed 100644 --- a/gcc-4.9/gcc/params.def +++ b/gcc-4.9/gcc/params.def @@ -1389,6 +1389,21 @@ DEFPARAM (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS, "during uninitialized variable analysis", 1000, 1, 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) + /* Fraction of adjusting fp setting cost in framepointer shrinkwrapping. */ DEFPARAM (PARAM_FPSET_COST_FRACTION, "fpset-cost-fraction", diff --git a/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c new file mode 100644 index 000000000..bb34a7432 --- /dev/null +++ b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c @@ -0,0 +1,43 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-dom1-details" } */ +/* { dg-final { scan-tree-dump-times "FSM" 6 "dom1" } } */ +/* { dg-final { cleanup-tree-dump "dom1" } } */ + +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-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c new file mode 100644 index 000000000..21474f0b4 --- /dev/null +++ b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c @@ -0,0 +1,127 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-dom1-details" } */ +/* { dg-final { scan-tree-dump-times "FSM" 19 "dom1" } } */ +/* { dg-final { cleanup-tree-dump "dom1" } } */ + +enum STATE { + S0=0, + SI, + S1, + S2, + S3, + S4, + S5, + S6 +}; + +int bar (enum STATE s); + +enum STATE foo (unsigned char **y, unsigned *c) +{ + unsigned char *x = *y; + unsigned char n; + enum STATE s = S0; + + for( ; *x && s != SI; x++ ) + { + n = *x; + if (n == 'x') + { + x++; + break; + } + switch(s) + { + case S0: + if(bar(n)) + s = S3; + else if( n == 'a' || n == 'b' ) + s = S1; + else if( n == 'c' ) + s = S4; + else + { + s = SI; + c[SI]++; + } + c[S0]++; + break; + case S1: + if(bar(n)) + { + s = S3; + c[S1]++; + } + else if( n == 'c' ) + { + s = S4; + c[S1]++; + } + else + { + s = SI; + c[S1]++; + } + break; + case S3: + if( n == 'c' ) + { + s = S4; + c[S3]++; + } + else if(!bar(n)) + { + s = SI; + c[S3]++; + } + break; + case S4: + if( n == 'E' || n == 'e' ) + { + s = S2; + c[S4]++; + } + else if(!bar(n)) + { + s = SI; + c[S4]++; + } + break; + case S2: + if( n == 'a' || n == 'b' ) + { + s = S5; + c[S2]++; + } + else + { + s = SI; + c[S2]++; + } + break; + case S5: + if(bar(n)) + { + s = S6; + c[S5]++; + } + else + { + s = SI; + c[S5]++; + } + break; + case S6: + if(!bar(n)) + { + s = SI; + c[SI]++; + } + break; + default: + break; + } + } + *y=x; + return s; +} diff --git a/gcc-4.9/gcc/tree-cfg.c b/gcc-4.9/gcc/tree-cfg.c index 29aa8c7a7..d83fb3760 100644 --- a/gcc-4.9/gcc/tree-cfg.c +++ b/gcc-4.9/gcc/tree-cfg.c @@ -2667,7 +2667,7 @@ reinstall_phi_args (edge new_edge, edge old_edge) near its "logical" location. This is of most help to humans looking at debugging dumps. */ -static basic_block +basic_block split_edge_bb_loc (edge edge_in) { basic_block dest = edge_in->dest; diff --git a/gcc-4.9/gcc/tree-cfg.h b/gcc-4.9/gcc/tree-cfg.h index a115df58b..e6dee8073 100644 --- a/gcc-4.9/gcc/tree-cfg.h +++ b/gcc-4.9/gcc/tree-cfg.h @@ -62,6 +62,7 @@ extern void verify_gimple_in_cfg (struct function *); extern tree gimple_block_label (basic_block); extern void add_phi_args_after_copy_bb (basic_block); extern void add_phi_args_after_copy (basic_block *, unsigned, edge); +extern basic_block split_edge_bb_loc (edge); extern bool gimple_duplicate_sese_region (edge, edge, basic_block *, unsigned, basic_block *, bool); extern bool gimple_duplicate_sese_tail (edge, edge, basic_block *, unsigned, diff --git a/gcc-4.9/gcc/tree-ssa-threadedge.c b/gcc-4.9/gcc/tree-ssa-threadedge.c index c715e842d..d3fe4afab 100644 --- a/gcc-4.9/gcc/tree-ssa-threadedge.c +++ b/gcc-4.9/gcc/tree-ssa-threadedge.c @@ -617,6 +617,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. @@ -638,6 +639,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; @@ -897,6 +904,248 @@ thread_around_empty_blocks (edge taken_edge, return false; } +/* Return true if the CFG contains at least one path from START_BB to END_BB. + When a path is found, record in PATH the blocks from END_BB to START_BB. + VISITED_BBS is used to make sure we don't fall into an infinite loop. Bound + the recursion to basic blocks belonging to LOOP. */ + +static bool +fsm_find_thread_path (basic_block start_bb, basic_block end_bb, + vec *&path, + pointer_set_t *visited_bbs, loop_p loop) +{ + if (loop != start_bb->loop_father) + return false; + + 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 (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop)) + { + 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, + 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; + + /* For the moment we assume that an SSA chain only contains phi nodes, and + eventually one of the phi arguments will be an integer constant. In the + future, this could be extended to also handle simple assignments of + arithmetic operations. */ + if (gimple_code (def_stmt) != GIMPLE_PHI) + return; + + /* Avoid infinite recursion. */ + if (pointer_set_insert (visited_phis, def_stmt)) + return; + + int next_path_length = 0; + basic_block last_bb_in_path = path->last (); + + /* Following the chain of SSA_NAME definitions, we jumped from a definition in + LAST_BB_IN_PATH to a definition in VAR_BB. When these basic blocks are + different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB. */ + if (var_bb != last_bb_in_path) + { + edge e; + int e_count = 0; + edge_iterator ei; + vec *next_path; + vec_alloc (next_path, n_basic_blocks_for_fn (cfun)); + + FOR_EACH_EDGE (e, ei, last_bb_in_path->preds) + { + pointer_set_t *visited_bbs = pointer_set_create (); + + if (fsm_find_thread_path (var_bb, e->src, next_path, visited_bbs, + e->src->loop_father)) + ++e_count; + + pointer_set_destroy (visited_bbs); + + /* If there is more than one path, stop. */ + if (e_count > 1) + { + vec_free (next_path); + return; + } + } + + /* Stop if we have not found a path: this could occur when the recursion + is stopped by one of the bounds. */ + if (e_count == 0) + { + vec_free (next_path); + return; + } + + /* Append all the nodes from NEXT_PATH to PATH. */ + vec_safe_splice (path, next_path); + next_path_length = next_path->length (); + vec_free (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; + + if (TREE_CODE (arg) == SSA_NAME) + { + vec_safe_push (path, bbi); + /* Recursively follow SSA_NAMEs looking for a constant definition. */ + fsm_find_control_statement_thread_paths (arg, visited_phis, path); + path->pop (); + continue; + } + + if (TREE_CODE (arg) != INTEGER_CST) + continue; + + int path_length = path->length (); + /* A path with less than 2 basic blocks should not be jump-threaded. */ + if (path_length < 2) + continue; + + if (path_length > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "FSM jump-thread path not considered: " + "the number of basic blocks on the path " + "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n"); + continue; + } + + if (max_threaded_paths <= 0) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "FSM jump-thread path not considered: " + "the number of previously recorded FSM paths to thread " + "exceeds PARAM_MAX_FSM_THREAD_PATHS.\n"); + continue; + } + + /* Add BBI to the path. */ + vec_safe_push (path, bbi); + ++path_length; + + int n_insns = 0; + gimple_stmt_iterator gsi; + int j; + loop_p loop = (*path)[0]->loop_father; + bool path_crosses_loops = false; + + /* Count the number of instructions on the path: as these instructions + will have to be duplicated, we will not record the path if there are + too many instructions on the path. Also check that all the blocks in + the path belong to a single loop. */ + for (j = 1; j < path_length - 1; j++) + { + basic_block bb = (*path)[j]; + + if (bb->loop_father != loop) + { + path_crosses_loops = true; + break; + } + + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple stmt = gsi_stmt (gsi); + /* Do not count empty statements and labels. */ + if (gimple_code (stmt) != GIMPLE_NOP + && gimple_code (stmt) != GIMPLE_LABEL + && !is_gimple_debug (stmt)) + ++n_insns; + } + } + + if (path_crosses_loops) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "FSM jump-thread path not considered: " + "the path crosses loops.\n"); + path->pop (); + continue; + } + + if (n_insns >= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "FSM jump-thread path not considered: " + "the number of instructions on the path " + "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n"); + path->pop (); + continue; + } + + vec *jump_thread_path + = new vec (); + + /* Record the edges between the blocks in PATH. */ + for (j = 0; j < path_length - 1; j++) + { + edge e = find_edge ((*path)[path_length - j - 1], + (*path)[path_length - j - 2]); + gcc_assert (e); + jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD); + 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); + + register_jump_thread (jump_thread_path); + --max_threaded_paths; + + /* Remove BBI from the path. */ + path->pop (); + } + + /* Remove all the nodes that we added from NEXT_PATH. */ + if (next_path_length) + vec_safe_truncate (path, (path->length () - next_path_length)); +} + /* We are exiting E->src, see if E->dest ends with a conditional jump which has a known value when reached via E. @@ -982,7 +1231,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); @@ -1028,6 +1280,27 @@ thread_through_normal_block (edge e, backedge_seen_p); return 1; } + + if (!flag_expensive_optimizations + || optimize_function_for_size_p (cfun) + || TREE_CODE (cond) != SSA_NAME + || e->dest->loop_father != e->src->loop_father + || loop_depth (e->dest->loop_father) == 0) + 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); + pointer_set_t *visited_phis = pointer_set_create (); + + max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS); + fsm_find_control_statement_thread_paths (cond, visited_phis, bb_path); + + pointer_set_destroy (visited_phis); + vec_free (bb_path); } return 0; } diff --git a/gcc-4.9/gcc/tree-ssa-threadupdate.c b/gcc-4.9/gcc/tree-ssa-threadupdate.c index f458d6a99..d1b289ffa 100644 --- a/gcc-4.9/gcc/tree-ssa-threadupdate.c +++ b/gcc-4.9/gcc/tree-ssa-threadupdate.c @@ -156,8 +156,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_FSM_THREAD ? " FSM": ""), path[0]->e->src->index, path[0]->e->dest->index); for (unsigned int i = 1; i < path.length (); i++) @@ -1622,6 +1623,155 @@ 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. */ + +DEBUG_FUNCTION void +verify_seme (edge entry, 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); +} + +/* 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. + + 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 + EXIT edge. + + The new basic blocks are stored to REGION_COPY in the same order as they had + in REGION, provided that REGION_COPY is not NULL. + + Returns false if it is unable to copy the region, true otherwise. */ + +static bool +duplicate_seme_region (edge entry, edge exit, + basic_block *region, unsigned n_region, + basic_block *region_copy) +{ + unsigned i; + bool free_region_copy = false, copying_header = false; + struct loop *loop = entry->dest->loop_father; + edge exit_copy; + edge redirected; + int total_freq = 0, entry_freq = 0; + gcov_type total_count = 0, entry_count = 0; + + if (!can_copy_bbs_p (region, n_region)) + return false; + + /* Some sanity checking. Note that we do not check for all possible + missuses of the functions. I.e. if you ask to copy something weird, + it will work, but the state of structures probably will not be + correct. */ + for (i = 0; i < n_region; i++) + { + /* We do not handle subloops, i.e. all the blocks must belong to the + same loop. */ + if (region[i]->loop_father != loop) + return false; + } + + initialize_original_copy_tables (); + + if (copying_header) + set_loop_copy (loop, loop_outer (loop)); + else + set_loop_copy (loop, loop); + + if (!region_copy) + { + region_copy = XNEWVEC (basic_block, n_region); + free_region_copy = true; + } + + if (entry->dest->count) + { + total_count = entry->dest->count; + entry_count = entry->count; + /* Fix up corner cases, to avoid division by zero or creation of negative + frequencies. */ + if (entry_count > total_count) + entry_count = total_count; + } + else + { + total_freq = entry->dest->frequency; + entry_freq = EDGE_FREQUENCY (entry); + /* Fix up corner cases, to avoid division by zero or creation of negative + frequencies. */ + if (total_freq == 0) + total_freq = 1; + else if (entry_freq > total_freq) + entry_freq = total_freq; + } + + copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop, + split_edge_bb_loc (entry), 0); + if (total_count) + { + scale_bbs_frequencies_gcov_type (region, n_region, + total_count - entry_count, + total_count); + scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count, + total_count); + } + else + { + scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq, + total_freq); + scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq); + } + +#ifdef ENABLE_CHECKING + /* Make sure no edge other than ENTRY is entering the copied region. */ + verify_seme (entry, region_copy, n_region); +#endif + + /* Remove the last branch in the jump thread path. */ + remove_ctrl_stmt_and_useless_edges (region_copy[n_region - 1], exit->dest); + edge e = make_edge (region_copy[n_region - 1], exit->dest, EDGE_FALLTHRU); + + if (e) { + rescan_loop_exit (e, true, false); + e->probability = REG_BR_PROB_BASE; + e->count = region_copy[n_region - 1]->count; + } + + /* Redirect the entry and add the phi node arguments. */ + redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest)); + gcc_assert (redirected != NULL); + flush_pending_stmts (entry); + + /* Add the other PHI node arguments. */ + add_phi_args_after_copy (region_copy, n_region, NULL); + + if (free_region_copy) + free (region_copy); + + free_original_copy_tables (); + return true; +} + /* Walk through all blocks and thread incoming edges to the appropriate outgoing edge for each edge pair recorded in THREADED_EDGES. @@ -1651,6 +1801,57 @@ thread_through_all_blocks (bool may_peel_loop_headers) threaded_blocks = BITMAP_ALLOC (NULL); memset (&thread_stats, 0, sizeof (thread_stats)); + /* Jump-thread all FSM threads before other jump-threads. */ + for (i = 0; i < paths.length ();) + { + vec *path = paths[i]; + edge entry = (*path)[0]->e; + + if ((*path)[0]->type != EDGE_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; + + if (duplicate_seme_region (entry, exit, region, len - 1, NULL)) + { + /* We do not update dominance info. */ + free_dominance_info (CDI_DOMINATORS); + bitmap_set_bit (threaded_blocks, entry->src->index); + retval = true; + } + + delete_jump_thread_path (path); + paths.unordered_remove (i); + } + + /* Remove from PATHS all the jump-threads starting with an edge already + jump-threaded. */ + 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-4.9/gcc/tree-ssa-threadupdate.h b/gcc-4.9/gcc/tree-ssa-threadupdate.h index 426aca5e6..22c5bceb9 100644 --- a/gcc-4.9/gcc/tree-ssa-threadupdate.h +++ b/gcc-4.9/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_FSM_THREAD, EDGE_COPY_SRC_BLOCK, EDGE_COPY_SRC_JOINER_BLOCK, EDGE_NO_COPY_SRC_BLOCK -- cgit v1.2.3 From c39d2a2bd89ed7a9ff995f2fc1e2e693fab8ee9f Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Fri, 28 Aug 2015 15:29:57 -0500 Subject: backport patch for PR 64878: do not jump thread across more than one back-edge 2015-02-04 Sebastian Pop Brian Rzycki PR tree-optimization/64878 * tree-ssa-threadedge.c: Include tree-ssa-loop.h. (fsm_find_control_statement_thread_paths): Add parameter seen_loop_phi. Stop recursion at loop phi nodes after having visited a loop phi node. * testsuite/gcc.dg/tree-ssa/ssa-dom-thread-8.c: New. --- .../testsuite/gcc.dg/tree-ssa/ssa-dom-thread-8.c | 440 +++++++++++++++++++++ gcc-4.9/gcc/tree-ssa-threadedge.c | 19 +- 2 files changed, 456 insertions(+), 3 deletions(-) create mode 100644 gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-8.c (limited to 'gcc-4.9') diff --git a/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-8.c b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-8.c new file mode 100644 index 000000000..9be75aaf2 --- /dev/null +++ b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-8.c @@ -0,0 +1,440 @@ +/* PR 64878 */ +/* { dg-options "-O2" } */ +/* { dg-do run } */ + +struct A { int a1; }; +struct B { char *b1; int b2; int b3; }; +struct C { char *c1; int c2; struct B *c3; }; +extern struct A *f1 (char *s); +static struct A *f2 (struct C *x); +__attribute__ ((noinline, noclone)) int f3 (struct A *x, struct A *z) { asm volatile ("" : : "g" (x), "g" (z) : "memory"); return 0; } +__attribute__ ((noinline, noclone)) void f4 (struct A *x, char *y, struct A *z) { asm volatile ("" : : "g" (x), "g" (z), "g" (y) : "memory"); } +__attribute__ ((noinline, noclone)) struct B *f5 (void) { static char b[32]; static struct B f3 = { b, 0, 32 }; return &f3; } +__attribute__ ((noinline, noclone)) int f6 (struct B *p, char *w, int z) { asm volatile ("" : : "g" (p), "g" (w), "g" (z) : "memory"); return 0; } +__attribute__ ((noinline, noclone)) void f7 (struct B *p) { asm volatile ("" : : "g" (p) : "memory"); } +__attribute__ ((noinline, noclone)) void f8 (struct B *p) { asm volatile ("" : : "g" (p) : "memory"); } +__attribute__ ((noinline, noclone)) void f9 (struct A *x) { asm volatile ("" : : "g" (x) : "memory"); } +__attribute__ ((noinline, noclone)) struct A *f10 (void) { static struct A j; asm volatile ("" : : : "memory"); return &j; } +__attribute__ ((noinline, noclone)) struct A *f11 (void) { static struct A j; asm volatile ("" : : : "memory"); return &j; } +__attribute__ ((noinline, noclone)) struct A *f12 (int b) { static struct A j; asm volatile ("" : : "g" (b) : "memory"); return &j; } +__attribute__ ((noinline, noclone)) struct A *f13 (int i) { static struct A j; asm volatile ("" : : "g" (i) : "memory"); return &j; } +__attribute__ ((noinline, noclone)) struct A *f14 (double d) { static struct A j; asm volatile ("" : : "g" (&d) : "memory"); return &j; } +__attribute__ ((noinline, noclone)) struct A *f15 (char *s) { static struct A j; asm volatile ("" : : "g" (s) : "memory"); return &j; } +char *t = "0123456789abcdef"; +char *u = "0123456789.+-e"; + +__attribute__ ((noinline, noclone)) struct A * +f1 (char *s) +{ + struct C f; + struct A *o; + f.c1 = s; + f.c2 = 0; + f.c3 = f5 (); + o = f2 (&f); + f8 (f.c3); + return o; +} + +static struct A * +f2 (struct C *x) +{ + int a, b, e = 0; + struct A *f = 0, *o; + char *g = 0; + char h = '\0'; + int i = 0, j = 0; + a = 0; + b = 1; + char c; + do + { + c = x->c1[x->c2]; + switch (a) + { + case 0: + if (c == ' ') + x->c2++; + else if (c == '/') + { + a = 4; + j = x->c2++; + } + else + a = b; + break; + case 1: + switch (c) + { + case '{': + a = 0; + b = 15; + f = f10 (); + x->c2++; + break; + case '[': + a = 0; + b = 13; + f = f11 (); + x->c2++; + break; + case 'N': + case 'n': + a = 3; + j = x->c2++; + break; + case '"': + case '\'': + h = c; + f7 (x->c3); + a = 8; + j = ++x->c2; + break; + case 'T': + case 't': + case 'F': + case 'f': + a = 11; + j = x->c2++; + break; + case '0' ... '9': + case '-': + i = 0; + a = 12; + j = x->c2++; + break; + default: + e = 1; + goto out; + } + break; + case 2: + goto out; + case 3: + if (__builtin_strncmp ("null", x->c1 + j, x->c2 - j)) + { + e = 2; + goto out; + } + if (x->c2 - j == 4) + { + f = 0; + b = 2; + a = 0; + } + else + x->c2++; + break; + case 4: + if (c == '*') + a = 5; + else if (c == '/') + a = 6; + else + { + e = 8; + goto out; + } + x->c2++; + break; + case 5: + if (c == '*') + a = 7; + x->c2++; + break; + case 6: + if (c == '\n') + a = 0; + x->c2++; + break; + case 7: + if (c == '/') + a = 0; + else + a = 5; + x->c2++; + break; + case 8: + if (c == h) + { + f6 (x->c3, x->c1 + j, x->c2 - j); + f = f15 (x->c3->b1); + b = 2; + a = 0; + } + else if (c == '\\') + { + b = 8; + a = 9; + } + x->c2++; + break; + case 9: + switch (c) + { + case '"': + case '\\': + f6 (x->c3, x->c1 + j, x->c2 - j - 1); + j = x->c2++; + a = b; + break; + case 'b': + case 'n': + case 'r': + case 't': + f6 (x->c3, x->c1 + j, x->c2 - j - 1); + if (c == 'b') + f6 (x->c3, "\b", 1); + else if (c == 'n') + f6 (x->c3, "\n", 1); + else if (c == 'r') + f6 (x->c3, "\r", 1); + else if (c == 't') + f6 (x->c3, "\t", 1); + j = ++x->c2; + a = b; + break; + case 'u': + f6 (x->c3, x->c1 + j, x->c2 - j - 1); + j = ++x->c2; + a = 10; + break; + default: + e = 7; + goto out; + } + break; + case 10: + if (__builtin_strchr (t, c)) + { + x->c2++; + if (x->c2 - j == 4) + { + unsigned char w[3]; + unsigned int s = + (((x->c1[j] <= '9') ? x->c1[j] - '0' : (x->c1[j] & 7) + 9) << 12) + + (((x->c1[j + 1] <= '9') ? x->c1[j + 1] - '0' : (x->c1[j + 1] & 7) + 9) << 8) + + (((x->c1[j + 2] <= '9') ? x->c1[j + 2] - '0' : (x->c1[j + 2] & 7) + 9) << 4) + + ((x->c1[j + 3] <= '9') ? x->c1[j + 3] - '0' : (x->c1[j + 3] & 7) + 9); + if (s < 0x80) + { + w[0] = s; + f6 (x->c3, (char *) w, 1); + } + else if (s < 0x800) + { + w[0] = 0xc0 | (s >> 6); + w[1] = 0x80 | (s & 0x3f); + f6 (x->c3, (char *) w, 2); + } + else + { + w[0] = 0x0 | (s >> 12); + w[1] = 0x80 | ((s >> 6) & 0x3f); + w[2] = 0x80 | (s & 0x3f); + f6 (x->c3, (char *) w, 3); + } + j = x->c2; + a = b; + } + } + else + { + e = 7; + goto out; + } + break; + case 11: + if (__builtin_strncmp ("true", x->c1 + j, x->c2 - j) == 0) + { + if (x->c2 - j == 4) + { + f = f12 (1); + b = 2; + a = 0; + } + else + x->c2++; + } + else if (__builtin_strncmp ("false", x->c1 + j, x->c2 - j) == 0) + { + if (x->c2 - j == 5) + { + f = f12 (0); + b = 2; + a = 0; + } + else + x->c2++; + } + else + { + e = 3; + goto out; + } + break; + case 12: + if (!c || !__builtin_strchr (u, c)) + { + if (!i) + f = f13 (0); + else + f = f14 (0.0); + b = 2; + a = 0; + } + else + { + if (c == '.' || c == 'e') + i = 1; + x->c2++; + } + break; + case 13: + if (c == ']') + { + x->c2++; + b = 2; + a = 0; + } + else + { + o = f2 (x); + if (((unsigned long) o > (unsigned long) -4000L)) + { + e = 5; + goto out; + } + f3 (f, o); + b = 14; + a = 0; + } + break; + case 14: + if (c == ']') + { + x->c2++; + b = 2; + a = 0; + } + else if (c == ',') + { + x->c2++; + b = 13; + a = 0; + } + else + { + f9 (f); + e = 5; + goto out; + } + break; + case 15: + a = 16; + j = x->c2; + break; + case 16: + if (c == '}') + { + x->c2++; + b = 2; + a = 0; + } + else if (c == '"' || c == '\'') + { + h = c; + f7 (x->c3); + a = 17; + j = ++x->c2; + } + else + { + e = 6; + goto out; + } + break; + case 17: + if (c == h) + { + f6 (x->c3, x->c1 + j, x->c2 - j); + g = __builtin_strdup (x->c3->b1); + b = 18; + a = 0; + } + else if (c == '\\') + { + b = 17; + a = 9; + } + x->c2++; + break; + case 18: + if (c == ':') + { + x->c2++; + b = 19; + a = 0; + } + else + { + e = -6; + goto out; + } + break; + case 19: + o = f2 (x); + if (((unsigned long) o > (unsigned long) -4000L)) + { + e = 6; + goto out; + } + f4 (f, g, o); + __builtin_free (g); + g = 0; + b = 20; + a = 0; + break; + case 20: + if (c == '}') + { + x->c2++; + b = 2; + a = 0; + } + else if (c == ',') + { + x->c2++; + b = 15; + a = 0; + } + else + { + e = 6; + goto out; + } + break; + } + } + while (c); + if (a != 2 && b != 2) + e = 9; +out: + __builtin_free (g); + if (e == 0) + return f; + f9 (f); + return 0; +} + +int +main () +{ + asm volatile ("" : : : "memory"); + struct A *r = f1 ("{ \"id\": null, \"blahah\": \"foobarbazbar\", \"barbar\": { \"barbarbarba\":" + "\"abcdefgh\", \"ijklmnopqr\": \"stuvwxyzabcdefghijklmnopqrstuv\", \"xyzxyz\":" + " [ \"1\" ] } }"); + if (!r) + __builtin_abort (); + return 0; +} diff --git a/gcc-4.9/gcc/tree-ssa-threadedge.c b/gcc-4.9/gcc/tree-ssa-threadedge.c index d3fe4afab..cad91ef66 100644 --- a/gcc-4.9/gcc/tree-ssa-threadedge.c +++ b/gcc-4.9/gcc/tree-ssa-threadedge.c @@ -48,6 +48,7 @@ along with GCC; see the file COPYING3. If not see #include "langhooks.h" #include "params.h" #include "tree-ssa-threadedge.h" +#include "tree-ssa-loop.h" /* To avoid code explosion due to jump threading, we limit the number of statements we are going to copy. This variable @@ -947,7 +948,8 @@ static int max_threaded_paths; static void fsm_find_control_statement_thread_paths (tree expr, pointer_set_t *visited_phis, - vec *&path) + vec *&path, + bool seen_loop_phi) { tree var = SSA_NAME_VAR (expr); gimple def_stmt = SSA_NAME_DEF_STMT (expr); @@ -970,6 +972,14 @@ fsm_find_control_statement_thread_paths (tree expr, int next_path_length = 0; basic_block last_bb_in_path = path->last (); + if (loop_containing_stmt (def_stmt)->header == gimple_bb (def_stmt)) + { + /* Do not walk through more than one loop PHI node. */ + if (seen_loop_phi) + return; + seen_loop_phi = true; + } + /* Following the chain of SSA_NAME definitions, we jumped from a definition in LAST_BB_IN_PATH to a definition in VAR_BB. When these basic blocks are different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB. */ @@ -1030,7 +1040,9 @@ fsm_find_control_statement_thread_paths (tree expr, { vec_safe_push (path, bbi); /* Recursively follow SSA_NAMEs looking for a constant definition. */ - fsm_find_control_statement_thread_paths (arg, visited_phis, path); + fsm_find_control_statement_thread_paths (arg, visited_phis, path, + seen_loop_phi); + path->pop (); continue; } @@ -1297,7 +1309,8 @@ thread_through_normal_block (edge e, pointer_set_t *visited_phis = pointer_set_create (); max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS); - fsm_find_control_statement_thread_paths (cond, visited_phis, bb_path); + fsm_find_control_statement_thread_paths (cond, visited_phis, bb_path, + false); pointer_set_destroy (visited_phis); vec_free (bb_path); -- cgit v1.2.3 From fa0139c9969e54f37f0add025af87cc21b46ffcb Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Fri, 28 Aug 2015 15:36:58 -0500 Subject: backport patch to fix PR65048 PR tree-optimization/65048 * tree-ssa-threadupdate.c (valid_jump_thread_path): New. (thread_through_all_blocks): Call valid_jump_thread_path. Remove invalid FSM jump-thread paths. PR tree-optimization/65048 * gcc.dg/tree-ssa/ssa-dom-thread-9.c: New. --- .../testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c | 50 ++++++++++++++++++++++ gcc-4.9/gcc/tree-ssa-threadupdate.c | 40 ++++++++++++++--- 2 files changed, 84 insertions(+), 6 deletions(-) create mode 100644 gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c (limited to 'gcc-4.9') diff --git a/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c new file mode 100644 index 000000000..6be42038b --- /dev/null +++ b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c @@ -0,0 +1,50 @@ +/* PR 65048 */ +/* { dg-do compile } */ +/* { dg-options "-O3" } */ + +int a, b, c, d; +void fn (void); + +int +foo (x) +{ + switch (x) + { + case 'A': + return 'T'; + case 'U': + return 'A'; + } +} + +void +bar (int x, int y) +{ + switch (c) + { + case 'U': + switch (x) + { + default: + fn (); + case 'G': + switch (y) + { + case 'A': + d = 7; + } + } + } +} + +void +baz (void) +{ + while (1) + { + a = foo (); + b = foo (); + bar (a, b); + } +} + diff --git a/gcc-4.9/gcc/tree-ssa-threadupdate.c b/gcc-4.9/gcc/tree-ssa-threadupdate.c index d1b289ffa..3c7df9add 100644 --- a/gcc-4.9/gcc/tree-ssa-threadupdate.c +++ b/gcc-4.9/gcc/tree-ssa-threadupdate.c @@ -1772,6 +1772,21 @@ duplicate_seme_region (edge entry, edge exit, return true; } +/* Return true when PATH is a valid jump-thread path. */ + +static bool +valid_jump_thread_path (vec *path) +{ + unsigned len = path->length (); + + /* Check that the path is connected. */ + for (unsigned int j = 0; j < len - 1; j++) + if ((*path)[j]->e->dest != (*path)[j+1]->e->src) + return false; + + return true; +} + /* Walk through all blocks and thread incoming edges to the appropriate outgoing edge for each edge pair recorded in THREADED_EDGES. @@ -1807,12 +1822,25 @@ thread_through_all_blocks (bool may_peel_loop_headers) vec *path = paths[i]; edge entry = (*path)[0]->e; - if ((*path)[0]->type != EDGE_FSM_THREAD - /* Do not jump-thread twice from the same block. */ - || bitmap_bit_p (threaded_blocks, entry->src->index)) { - i++; - continue; - } + /* Only code-generate FSM jump-threads in this loop. */ + if ((*path)[0]->type != EDGE_FSM_THREAD) + { + i++; + continue; + } + + /* Do not jump-thread twice from the same block. */ + if (bitmap_bit_p (threaded_blocks, entry->src->index) + /* Verify that the jump thread path is still valid: a + previous jump-thread may have changed the CFG, and + invalidated the current path. */ + || !valid_jump_thread_path (path)) + { + /* Remove invalid FSM jump-thread paths. */ + delete_jump_thread_path (path); + paths.unordered_remove (i); + continue; + } unsigned len = path->length (); edge exit = (*path)[len - 1]->e; -- cgit v1.2.3 From aa65e2d1e40e4dd0d936a275683c4aadfe8aa20f Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Fri, 28 Aug 2015 15:43:11 -0500 Subject: backport patch to fix PR65177 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. --- .../testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c | 24 ++++++ gcc-4.9/gcc/tree-ssa-threadupdate.c | 93 ++++++++++++++++------ 2 files changed, 91 insertions(+), 26 deletions(-) create mode 100644 gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c (limited to 'gcc-4.9') diff --git a/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c new file mode 100644 index 000000000..4acf580e1 --- /dev/null +++ b/gcc-4.9/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-4.9/gcc/tree-ssa-threadupdate.c b/gcc-4.9/gcc/tree-ssa-threadupdate.c index 3c7df9add..c2f02a6ab 100644 --- a/gcc-4.9/gcc/tree-ssa-threadupdate.c +++ b/gcc-4.9/gcc/tree-ssa-threadupdate.c @@ -1623,36 +1623,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 @@ -1664,7 +1660,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) { @@ -1726,7 +1722,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, @@ -1743,8 +1785,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. */ @@ -1849,7 +1890,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); -- cgit v1.2.3 From 65f8bbbcc74a4777f0629190ea9121fc94a79257 Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Fri, 28 Aug 2015 15:51:12 -0500 Subject: backport fix for PR65735 PR tree-optimization/65735 * tree-ssa-threadedge.c (fsm_find_control_statement_thread_paths): Remove visited_phis argument, add visited_bbs, avoid recursing into the same bb rather than just into the same phi node. (thread_through_normal_block): Adjust caller. * gcc.c-torture/compile/pr65735.c: New test. --- .../gcc/testsuite/gcc.c-torture/compile/pr65735.c | 21 +++++++++++++++++++++ gcc-4.9/gcc/tree-ssa-threadedge.c | 12 ++++++------ 2 files changed, 27 insertions(+), 6 deletions(-) create mode 100644 gcc-4.9/gcc/testsuite/gcc.c-torture/compile/pr65735.c (limited to 'gcc-4.9') diff --git a/gcc-4.9/gcc/testsuite/gcc.c-torture/compile/pr65735.c b/gcc-4.9/gcc/testsuite/gcc.c-torture/compile/pr65735.c new file mode 100644 index 000000000..c30de8ea3 --- /dev/null +++ b/gcc-4.9/gcc/testsuite/gcc.c-torture/compile/pr65735.c @@ -0,0 +1,21 @@ +/* PR tree-optimization/65735 */ + +int foo (void); + +void +bar (int a, int b, int c) +{ + while (!a) + { + c = foo (); + if (c == 7) + c = b; + switch (c) + { + case 1: + a = b++; + if (b) + b = 1; + } + } +} diff --git a/gcc-4.9/gcc/tree-ssa-threadedge.c b/gcc-4.9/gcc/tree-ssa-threadedge.c index cad91ef66..604123e10 100644 --- a/gcc-4.9/gcc/tree-ssa-threadedge.c +++ b/gcc-4.9/gcc/tree-ssa-threadedge.c @@ -947,7 +947,7 @@ static int max_threaded_paths; static void fsm_find_control_statement_thread_paths (tree expr, - pointer_set_t *visited_phis, + pointer_set_t *visited_bbs, vec *&path, bool seen_loop_phi) { @@ -966,7 +966,7 @@ fsm_find_control_statement_thread_paths (tree expr, return; /* Avoid infinite recursion. */ - if (pointer_set_insert (visited_phis, def_stmt)) + if (pointer_set_insert (visited_bbs, var_bb)) return; int next_path_length = 0; @@ -1040,7 +1040,7 @@ fsm_find_control_statement_thread_paths (tree expr, { vec_safe_push (path, bbi); /* Recursively follow SSA_NAMEs looking for a constant definition. */ - fsm_find_control_statement_thread_paths (arg, visited_phis, path, + fsm_find_control_statement_thread_paths (arg, visited_bbs, path, seen_loop_phi); path->pop (); @@ -1306,13 +1306,13 @@ thread_through_normal_block (edge e, vec *bb_path; vec_alloc (bb_path, n_basic_blocks_for_fn (cfun)); vec_safe_push (bb_path, e->dest); - pointer_set_t *visited_phis = pointer_set_create (); + pointer_set_t *visited_bbs = pointer_set_create (); max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS); - fsm_find_control_statement_thread_paths (cond, visited_phis, bb_path, + fsm_find_control_statement_thread_paths (cond, visited_bbs, bb_path, false); - pointer_set_destroy (visited_phis); + pointer_set_destroy (visited_bbs); vec_free (bb_path); } return 0; -- cgit v1.2.3