| /* SSA Jump Threading |
| Copyright (C) 2005-2016 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 |
| <http://www.gnu.org/licenses/>. */ |
| |
| #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; |
| |
| /* Simple helper to get the last statement from BB, which is assumed |
| to be a control statement. Return NULL if the last statement is |
| not a control statement. */ |
| |
| static gimple * |
| get_gimple_control_stmt (basic_block bb) |
| { |
| gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb); |
| |
| if (gsi_end_p (gsi)) |
| return NULL; |
| |
| gimple *stmt = gsi_stmt (gsi); |
| enum gimple_code code = gimple_code (stmt); |
| if (code == GIMPLE_COND || code == GIMPLE_SWITCH || code == GIMPLE_GOTO) |
| return stmt; |
| return NULL; |
| } |
| |
| /* 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<basic_block, va_gc> *&path, |
| hash_set<basic_block> *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 SSA_NAME NAME 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 name, |
| hash_set<basic_block> *visited_bbs, |
| vec<basic_block, va_gc> *&path, |
| bool seen_loop_phi) |
| { |
| /* If NAME appears in an abnormal PHI, then don't try to trace its |
| value back through PHI nodes. */ |
| if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) |
| return; |
| |
| gimple *def_stmt = SSA_NAME_DEF_STMT (name); |
| basic_block var_bb = gimple_bb (def_stmt); |
| |
| if (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 |
| || (gimple_phi_num_args (def_stmt) |
| >= (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS))) |
| return; |
| |
| /* Avoid infinite recursion. */ |
| if (visited_bbs->add (var_bb)) |
| return; |
| |
| gphi *phi = as_a <gphi *> (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<basic_block, va_gc> *next_path; |
| vec_alloc (next_path, 10); |
| |
| /* When VAR_BB == LAST_BB_IN_PATH, then the first block in the path |
| will already be in VISITED_BBS. When they are not equal, then we |
| must ensure that first block is accounted for to ensure we do not |
| create bogus jump threading paths. */ |
| visited_bbs->add ((*path)[0]); |
| FOR_EACH_EDGE (e, ei, last_bb_in_path->preds) |
| { |
| hash_set<basic_block> *visited_bbs = new hash_set<basic_block>; |
| |
| 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; |
| if (gimple_phi_num_args (phi) |
| < (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS)) |
| { |
| 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; |
| |
| /* Note BBI is not in the path yet, hence the +1 in the test below |
| to make sure BBI is accounted for in the path length test. */ |
| int path_length = path->length (); |
| if (path_length + 1 > 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; |
| bool threaded_through_latch = false; |
| bool multiway_branch_in_path = false; |
| bool threaded_multiway_branch = 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 = 0; j < path_length; j++) |
| { |
| basic_block bb = (*path)[j]; |
| |
| /* Remember, blocks in the path are stored in opposite order |
| in the PATH array. The last entry in the array represents |
| the block with an outgoing edge that we will redirect to the |
| jump threading path. Thus we don't care about that block's |
| loop father, nor how many statements are in that block because |
| it will not be copied or whether or not it ends in a multiway |
| branch. */ |
| if (j < path_length - 1) |
| { |
| if (bb->loop_father != loop) |
| { |
| path_crosses_loops = true; |
| break; |
| } |
| |
| /* PHIs in the path will create degenerate PHIS in the |
| copied path which will then get propagated away, so |
| looking at just the duplicate path the PHIs would |
| seem unimportant. |
| |
| But those PHIs, because they're assignments to objects |
| typically with lives that exist outside the thread path, |
| will tend to generate PHIs (or at least new PHI arguments) |
| at points where we leave the thread path and rejoin |
| the original blocks. So we do want to account for them. |
| |
| We ignore virtual PHIs. We also ignore cases where BB |
| has a single incoming edge. That's the most common |
| degenerate PHI we'll see here. Finally we ignore PHIs |
| that are associated with the value we're tracking as |
| that object likely dies. */ |
| if (EDGE_COUNT (bb->succs) > 1 && EDGE_COUNT (bb->preds) > 1) |
| { |
| for (gphi_iterator gsip = gsi_start_phis (bb); |
| !gsi_end_p (gsip); |
| gsi_next (&gsip)) |
| { |
| gphi *phi = gsip.phi (); |
| tree dst = gimple_phi_result (phi); |
| |
| /* Note that if both NAME and DST are anonymous |
| SSA_NAMEs, then we do not have enough information |
| to consider them associated. */ |
| if ((SSA_NAME_VAR (dst) != SSA_NAME_VAR (name) |
| || !SSA_NAME_VAR (dst)) |
| && !virtual_operand_p (dst)) |
| ++n_insns; |
| } |
| } |
| |
| for (gsi = gsi_after_labels (bb); |
| !gsi_end_p (gsi); |
| gsi_next_nondebug (&gsi)) |
| { |
| gimple *stmt = gsi_stmt (gsi); |
| /* Do not count empty statements and labels. */ |
| if (gimple_code (stmt) != GIMPLE_NOP |
| && !(gimple_code (stmt) == GIMPLE_ASSIGN |
| && gimple_assign_rhs_code (stmt) == ASSERT_EXPR) |
| && !is_gimple_debug (stmt)) |
| ++n_insns; |
| } |
| |
| /* We do not look at the block with the threaded branch |
| in this loop. So if any block with a last statement that |
| is a GIMPLE_SWITCH or GIMPLE_GOTO is seen, then we have a |
| multiway branch on our path. |
| |
| The block in PATH[0] is special, it's the block were we're |
| going to be able to eliminate its branch. */ |
| gimple *last = last_stmt (bb); |
| if (last && (gimple_code (last) == GIMPLE_SWITCH |
| || gimple_code (last) == GIMPLE_GOTO)) |
| { |
| if (j == 0) |
| threaded_multiway_branch = true; |
| else |
| multiway_branch_in_path = true; |
| } |
| } |
| |
| /* Note if we thread through the latch, we will want to include |
| the last entry in the array when determining if we thread |
| through the loop latch. */ |
| if (loop->latch == bb) |
| threaded_through_latch = true; |
| } |
| |
| /* We are going to remove the control statement at the end of the |
| last block in the threading path. So don't count it against our |
| statement count. */ |
| n_insns--; |
| |
| gimple *stmt = get_gimple_control_stmt ((*path)[0]); |
| gcc_assert (stmt); |
| /* We have found a constant value for ARG. For GIMPLE_SWITCH |
| and GIMPLE_GOTO, we use it as-is. However, for a GIMPLE_COND |
| we need to substitute, fold and simplify so we can determine |
| the edge taken out of the last block. */ |
| if (gimple_code (stmt) == GIMPLE_COND) |
| { |
| enum tree_code cond_code = gimple_cond_code (stmt); |
| |
| /* We know the underyling format of the condition. */ |
| arg = fold_binary (cond_code, boolean_type_node, |
| arg, gimple_cond_rhs (stmt)); |
| } |
| |
| /* If this path threaded through the loop latch back into the |
| same loop and the destination does not dominate the loop |
| latch, then this thread would create an irreducible loop. |
| |
| We have to know the outgoing edge to figure this out. */ |
| edge taken_edge = find_taken_edge ((*path)[0], arg); |
| |
| /* There are cases where we may not be able to extract the |
| taken edge. For example, a computed goto to an absolute |
| address. Handle those cases gracefully. */ |
| if (taken_edge == NULL) |
| { |
| path->pop (); |
| continue; |
| } |
| |
| bool creates_irreducible_loop = false; |
| if (threaded_through_latch |
| && loop == taken_edge->dest->loop_father |
| && (determine_bb_domination_status (loop, taken_edge->dest) |
| == DOMST_NONDOMINATING)) |
| creates_irreducible_loop = true; |
| |
| 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; |
| } |
| |
| /* We avoid creating irreducible inner loops unless we thread through |
| a multiway branch, in which case we have deemed it worth losing |
| other loop optimizations later. |
| |
| We also consider it worth creating an irreducible inner loop if |
| the number of copied statement is low relative to the length of |
| the path -- in that case there's little the traditional loop |
| optimizer would have done anyway, so an irreducible loop is not |
| so bad. */ |
| if (!threaded_multiway_branch && creates_irreducible_loop |
| && (n_insns * PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS) |
| > path_length * PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS))) |
| |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| fprintf (dump_file, |
| "FSM would create irreducible loop without threading " |
| "multiway branch.\n"); |
| path->pop (); |
| continue; |
| } |
| |
| |
| /* If this path does not thread through the loop latch, then we are |
| using the FSM threader to find old style jump threads. This |
| is good, except the FSM threader does not re-use an existing |
| threading path to reduce code duplication. |
| |
| So for that case, drastically reduce the number of statements |
| we are allowed to copy. */ |
| if (!(threaded_through_latch && threaded_multiway_branch) |
| && (n_insns * PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS) |
| >= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS))) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| fprintf (dump_file, |
| "FSM did not thread around loop and would copy too " |
| "many statements.\n"); |
| path->pop (); |
| continue; |
| } |
| |
| /* When there is a multi-way branch on the path, then threading can |
| explode the CFG due to duplicating the edges for that multi-way |
| branch. So like above, only allow a multi-way branch on the path |
| if we actually thread a multi-way branch. */ |
| if (!threaded_multiway_branch && multiway_branch_in_path) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| fprintf (dump_file, |
| "FSM Thread through multiway branch without threading " |
| "a multiway branch.\n"); |
| path->pop (); |
| continue; |
| } |
| |
| vec<jump_thread_edge *> *jump_thread_path |
| = new vec<jump_thread_edge *> (); |
| |
| /* 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. */ |
| 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 (edge e) |
| { |
| if (!flag_expensive_optimizations |
| || optimize_function_for_size_p (cfun) |
| || e->dest->loop_father != e->src->loop_father |
| || loop_depth (e->dest->loop_father) == 0) |
| return; |
| |
| gimple *stmt = get_gimple_control_stmt (e->dest); |
| if (!stmt) |
| return; |
| |
| enum gimple_code code = gimple_code (stmt); |
| tree name = NULL; |
| if (code == GIMPLE_SWITCH) |
| name = gimple_switch_index (as_a <gswitch *> (stmt)); |
| else if (code == GIMPLE_GOTO) |
| name = gimple_goto_dest (stmt); |
| else if (code == GIMPLE_COND) |
| { |
| if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME |
| && TREE_CODE (gimple_cond_rhs (stmt)) == INTEGER_CST |
| && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))) |
| || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))))) |
| name = gimple_cond_lhs (stmt); |
| } |
| |
| if (!name || TREE_CODE (name) != SSA_NAME) |
| return; |
| |
| vec<basic_block, va_gc> *bb_path; |
| vec_alloc (bb_path, 10); |
| vec_safe_push (bb_path, e->dest); |
| hash_set<basic_block> *visited_bbs = new hash_set<basic_block>; |
| |
| 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); |
| } |