From 0732f75fce0fb24a4989b510d57ebd2b05c1a67f Mon Sep 17 00:00:00 2001 From: Jeff Law Date: Sun, 11 Oct 2015 19:17:51 -0600 Subject: [PATCH] [PATCH] Refactoring FSM bits into their own file [PATCH] Refactoring FSM bits into their own file * tree-ssa-threadedge.c (fsm_find_thread_path): Moved from here into tree-ssa-threadbackward.c. (fsm_find_control_statement_thread_paths): Likewise. (thread_through_normal_block): Break out FSM bits and move them into a new function in tree-ssa-threadbackward.c. Call new function instead. Minimize header file usage. * tree-ssa-threadbackward.h: New file. * tree-ssa-threadbackward.c: Likewise. * Makefile.in (OBJS): Add tree-ssa-threadbackward.o From-SVN: r228700 --- gcc/ChangeLog | 13 ++ gcc/Makefile.in | 1 + gcc/tree-ssa-threadbackward.c | 325 ++++++++++++++++++++++++++++++++++ gcc/tree-ssa-threadbackward.h | 25 +++ gcc/tree-ssa-threadedge.c | 293 +----------------------------- 5 files changed, 366 insertions(+), 291 deletions(-) create mode 100644 gcc/tree-ssa-threadbackward.c create mode 100644 gcc/tree-ssa-threadbackward.h diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b39d6a5a1ab..eff9eeaea04 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,16 @@ +2015-10-11 Jeff Law + + * tree-ssa-threadedge.c (fsm_find_thread_path): Moved from here into + tree-ssa-threadbackward.c. + (fsm_find_control_statement_thread_paths): Likewise. + (thread_through_normal_block): Break out FSM bits and move them + into a new function in tree-ssa-threadbackward.c. Call new function + instead. + Minimize header file usage. + * tree-ssa-threadbackward.h: New file. + * tree-ssa-threadbackward.c: Likewise. + * Makefile.in (OBJS): Add tree-ssa-threadbackward.o + 2015-10-11 Uros Bizjak * config/alpha/alpha.h (ALPHA_ROUND): Implement using ROUND_UP macro. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 009c745a0c8..7e3aefac3fc 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1478,6 +1478,7 @@ OBJS = \ tree-ssa-structalias.o \ tree-ssa-tail-merge.o \ tree-ssa-ter.o \ + tree-ssa-threadbackward.o \ tree-ssa-threadedge.o \ tree-ssa-threadupdate.o \ tree-ssa-uncprop.o \ diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c new file mode 100644 index 00000000000..0012aa39180 --- /dev/null +++ b/gcc/tree-ssa-threadbackward.c @@ -0,0 +1,325 @@ +/* SSA Jump Threading + Copyright (C) 2005-2015 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "predict.h" +#include "tree.h" +#include "gimple.h" +#include "fold-const.h" +#include "cfgloop.h" +#include "gimple-iterator.h" +#include "tree-cfg.h" +#include "tree-ssa-threadupdate.h" +#include "params.h" +#include "tree-ssa-loop.h" +#include "cfganal.h" +#include "tree-pass.h" + +static int max_threaded_paths; + +/* 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, + hash_set *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 (!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, loop)) + { + vec_safe_push (path, start_bb); + return true; + } + } + + return false; +} + +/* 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_bbs, + vec *&path, + bool seen_loop_phi) +{ + 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 (visited_bbs->add (var_bb)) + return; + + gphi *phi = as_a (def_stmt); + int next_path_length = 0; + basic_block last_bb_in_path = path->last (); + + if (loop_containing_stmt (phi)->header == gimple_bb (phi)) + { + /* 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. */ + 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) + { + hash_set *visited_bbs = new hash_set; + + if (fsm_find_thread_path (var_bb, e->src, next_path, visited_bbs, + e->src->loop_father)) + ++e_count; + + delete 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; + } + + /* Make sure we haven't already visited any of the nodes in + NEXT_PATH. Don't add them here to avoid pollution. */ + for (unsigned int i = 0; i < next_path->length () - 1; i++) + { + if (visited_bbs->contains ((*next_path)[i])) + { + vec_free (next_path); + return; + } + } + + /* Now add the nodes to VISISTED_BBS. */ + for (unsigned int i = 0; i < next_path->length () - 1; i++) + visited_bbs->add ((*next_path)[i]); + + /* 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 (phi); i++) + { + tree arg = gimple_phi_arg_def (phi, i); + basic_block bbi = gimple_phi_arg_edge (phi, 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_bbs, path, + seen_loop_phi); + + 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)); +} + +/* Search backwards from BB looking for paths where NAME (an SSA_NAME) + is a constant. Record such paths for jump threading. + + It is assumed that BB ends with a control statement and that by + finding a path where NAME is a constant, we can thread the path. */ + +void +find_jump_threads_backwards (tree name, basic_block bb) +{ + vec *bb_path; + vec_alloc (bb_path, n_basic_blocks_for_fn (cfun)); + vec_safe_push (bb_path, bb); + hash_set *visited_bbs = new hash_set; + + max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS); + fsm_find_control_statement_thread_paths (name, visited_bbs, bb_path, false); + + delete visited_bbs; + vec_free (bb_path); +} diff --git a/gcc/tree-ssa-threadbackward.h b/gcc/tree-ssa-threadbackward.h new file mode 100644 index 00000000000..f055f432dd7 --- /dev/null +++ b/gcc/tree-ssa-threadbackward.h @@ -0,0 +1,25 @@ +/* Header file for SSA dominator optimizations. + Copyright (C) 2013-2015 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_TREE_SSA_THREADFSM_H +#define GCC_TREE_SSA_THREADFSM_H + +extern void find_jump_threads_backwards (tree, basic_block); + +#endif /* GCC_TREE_SSA_THREADFSM_H */ diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c index c58b5e35408..5ca945864e7 100644 --- a/gcc/tree-ssa-threadedge.c +++ b/gcc/tree-ssa-threadedge.c @@ -25,28 +25,18 @@ along with GCC; see the file COPYING3. If not see #include "predict.h" #include "tree.h" #include "gimple.h" -#include "hard-reg-set.h" #include "ssa.h" -#include "alias.h" #include "fold-const.h" -#include "flags.h" -#include "tm_p.h" #include "cfgloop.h" -#include "timevar.h" -#include "dumpfile.h" -#include "internal-fn.h" #include "gimple-iterator.h" #include "tree-cfg.h" -#include "tree-ssa-propagate.h" #include "tree-ssa-threadupdate.h" -#include "langhooks.h" #include "params.h" #include "tree-ssa-scopedtables.h" #include "tree-ssa-threadedge.h" -#include "tree-ssa-loop.h" +#include "tree-ssa-threadbackward.h" #include "tree-ssa-dom.h" #include "builtins.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 @@ -894,275 +884,6 @@ 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, - hash_set *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 (!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, 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, - hash_set *visited_bbs, - vec *&path, - bool seen_loop_phi) -{ - 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 (visited_bbs->add (var_bb)) - return; - - gphi *phi = as_a (def_stmt); - int next_path_length = 0; - basic_block last_bb_in_path = path->last (); - - if (loop_containing_stmt (phi)->header == gimple_bb (phi)) - { - /* 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. */ - 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) - { - hash_set *visited_bbs = new hash_set; - - if (fsm_find_thread_path (var_bb, e->src, next_path, visited_bbs, - e->src->loop_father)) - ++e_count; - - delete 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; - } - - /* Make sure we haven't already visited any of the nodes in - NEXT_PATH. Don't add them here to avoid pollution. */ - for (unsigned int i = 0; i < next_path->length () - 1; i++) - { - if (visited_bbs->contains ((*next_path)[i])) - { - vec_free (next_path); - return; - } - } - - /* Now add the nodes to VISISTED_BBS. */ - for (unsigned int i = 0; i < next_path->length () - 1; i++) - visited_bbs->add ((*next_path)[i]); - - /* 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 (phi); i++) - { - tree arg = gimple_phi_arg_def (phi, i); - basic_block bbi = gimple_phi_arg_edge (phi, 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_bbs, path, - seen_loop_phi); - - 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. @@ -1333,17 +1054,7 @@ thread_through_normal_block (edge e, /* 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_bbs = new hash_set; - - max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS); - fsm_find_control_statement_thread_paths (cond, visited_bbs, bb_path, - false); - - delete visited_bbs; - vec_free (bb_path); + find_jump_threads_backwards (cond, e->dest); } return 0; } -- 2.30.2