I have created a dynamically loadable optimization pass for optimizing the switch statement in the core_state_transition function of the coremark benchmark. This pass is not fully tested (I haven't run anything other then coremark with it) and it has no controls for limiting how much code it copies when doing the optimization but I do get an impressive speed up on coremark on the MIPS chips I ran it on and I thought I would send it out to see if there were any comments on it or suggestions for improvements (hopefully something more useful then telling me to add some controls for limiting the code copying).
My main concern is that I am using gimple_duplicate_sese_region to copy blocks and the comments for this routine say it should only be used on single-entry, single-exit regions. I use it on individual blocks and while every block is (by definition) single entry, they are not necessarily single exit. If anyone knows what needs to be done to gimple_duplicate_sese_region to make it safe for multiple-exit blocks, I would love to hear it. In the meantime coremark does seem to compile correctly and its self check passes when I compile with this optimization pass using gimple_duplicate_sese_region as is. Comments? Steve Ellcey sell...@imgtec.com
/* Alias analysis for GNU C Copyright (C) 2013 Free Software Foundation, Inc. Contributed by Steve Ellcey (sell...@imgtec.com). 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/>. */ /* This file implements an optimization where, when a variable is set to a constant value and there is a path that leads from this definition to a switch statement that uses the variable as its controlling expression we duplicate the blocks on this path and change the switch goto to a direct goto to the label of the switch block that control would goto based on the value of the variable. */ #include <gcc-plugin.h> #include <plugin-version.h> #include <tree-pass.h> #include <tree.h> #include <tree-flow.h> #include <tree-flow-inline.h> #include <basic-block.h> #include <pointer-set.h> #include <gimple.h> int plugin_is_GPL_compatible; /* Helper function for find_path, visited_bbs is used to make sure we don't fall into an infinite loop. */ static int find_path_1(basic_block start_bb, basic_block end_bb, struct pointer_set_t *visited_bbs) { edge_iterator ei; edge e; if (start_bb == end_bb) return 1; if (!pointer_set_insert (visited_bbs, start_bb)) { FOR_EACH_EDGE (e, ei, start_bb->succs) if (find_path_1 (e->dest, end_bb, visited_bbs)) return 1; } return 0; } /* Return 1 if there is a path from start_bb to end_bb and 0 if there is not. There may be multiple paths from start_bb to end_bb. */ static int find_path(basic_block start_bb, basic_block end_bb) { edge_iterator ei; edge e; struct pointer_set_t *visited_bbs; int p = 0; if (start_bb == end_bb) return 1; visited_bbs = pointer_set_create (); if (!pointer_set_insert (visited_bbs, start_bb)) { FOR_EACH_EDGE (e, ei, start_bb->succs) if (find_path_1 (e->dest, end_bb, visited_bbs)) { p = 1; break; } } pointer_set_destroy (visited_bbs); return p; } /* We save the paths we want to copy in bbs_list_array. n_bbs_list is the number of paths saved, bbs_list_array[i] is the list of basic blocks in one path. Each path starts with the block where a variable is assigned a constant value (bbs_list_array[i][0]) and ends with the switch statement block (bbs_list_array[i][bbs_list_size[i]-2]) and then the block that the switch statement is going to go to given the constant value of the variable (bbs_list_array[i][bbs_list_size[i]-1]). */ static basic_block *bbs_list_array[40]; static int val_array[40]; static int bbs_list_size[40]; static int n_bbs_list = 0; /* bbs_list[0] is the block with the switch statement, bbs_list[n-1] is the block where the switch statement variable is assigned a constant value, The entries in between make a (reverse) path between the two. We don't want to change bb_list, we want to leave that alone and and copy the path to bbs_list_array so that we wind up with a list (array) of paths that we want to update. We also want to add the block that the switch is going to go to on to the list so that we know which exit from the switch statement is important when calling gimple_duplicate_sese_region. */ static void save_new_path (basic_block *bbs_list, int n, tree val) { int i; edge switch_taken_edge; if (n <= 1) return; if (n_bbs_list >= 40) return; /* Put the blocks in 'correct' order and add in where we want to go after the switch statement, We want to leave bbs_list untouched for future calls. */ bbs_list_array[n_bbs_list] = XNEWVEC (basic_block, n+1); for (i = 0; i < n; i++) bbs_list_array[n_bbs_list][i] = bbs_list[n-i-1]; /* gimple switch_stmt = last_stmt (bbs_list[0]); */ switch_taken_edge = find_taken_edge (bbs_list[0], val); bbs_list_array[n_bbs_list][n] = switch_taken_edge->dest; bbs_list_size[n_bbs_list] = n + 1; val_array[n_bbs_list] = (int) TREE_INT_CST_LOW (val); #if 0 fprintf(stderr, "(1) Basic blocks [const value is %d], path is:\n", (int) TREE_INT_CST_LOW (val)); for (i = 0; i < bbs_list_size[n_bbs_list]; i++) fprintf(stderr, " %d\n", bbs_list_array[n_bbs_list][i]->index); #endif n_bbs_list = n_bbs_list + 1; } /* switch_stmt is a switch statement whose switch index expression is the variable expr. We trace the value of the variable back through any phi nodes looking for places where it gets a constant value and save the path in bbs_list. Then we call save_new_path to create a list of such paths. */ static void process_switch (tree expr, gimple switch_stmt, struct pointer_set_t *visited_phis, basic_block *bbs_list, int n) { gimple def_stmt; tree var; unsigned int i; edge e; edge_iterator ei; basic_block bbx; basic_block var_bb; int e_count; var = SSA_NAME_VAR (expr); gcc_assert (var); gcc_assert (gimple_code (switch_stmt) == GIMPLE_SWITCH); def_stmt = SSA_NAME_DEF_STMT (expr); var_bb = gimple_bb (def_stmt); /* If there are no definitions of var, return. */ if (var_bb == NULL) return; /* We have a variable definition (var) that is defined in var_bb, We want to put the path from var_bb to the current bb into the bbs_list. If there is more then one path, skip this and don't try to do the optimization. */ bbx = bbs_list[n-1]; while (bbx != var_bb) { e_count = 0; FOR_EACH_EDGE (e, ei, bbx->preds) { if (find_path (var_bb, e->src)) { bbs_list[n] = e->src; n = n + 1; e_count = e_count + 1; } } if (e_count != 1) return; bbx = bbs_list[n-1]; } if ((gimple_code (def_stmt) == GIMPLE_PHI) && !pointer_set_insert (visited_phis, def_stmt)) { for (i = 0; i < gimple_phi_num_args (def_stmt); i++) { tree arg = gimple_phi_arg_def (def_stmt, i); if (arg && (TREE_CODE (arg) == INTEGER_CST)) { /* const char *name = IDENTIFIER_POINTER (DECL_NAME (var)); */ bbs_list[n] = gimple_phi_arg_edge (def_stmt, i)->src; save_new_path(bbs_list, n + 1, arg); } else if (arg && (TREE_CODE (arg) == SSA_NAME)) { bbs_list[n] = gimple_phi_arg_edge (def_stmt, i)->src; process_switch (arg, switch_stmt, visited_phis, bbs_list, n+1); } } } } /* Find paths that lead from blocks where a variable is assigned a constant value to a switch statement where that variable is used as the switch index. Save the paths in bbs_list_array so that they can be processed by copy_switch_paths. */ static unsigned int find_switch_shortcuts (void) { basic_block bb; struct pointer_set_t *visited_phis; basic_block *bbs_list; int n = 1; bbs_list = XNEWVEC (basic_block, n_basic_blocks); visited_phis = pointer_set_create (); FOR_EACH_BB (bb) { gimple stmt = last_stmt (bb); if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) { tree op = gimple_switch_index (stmt); tree var = SSA_NAME_VAR (op); if (var) { bbs_list[0] = bb; process_switch (op, stmt, visited_phis, bbs_list, n); } } } pointer_set_destroy (visited_phis); return 0; } /* Copy the basic block that is the destination block of orig_edge, then modify/replace the edge in orig_edge->pred basic block with a new edge that goes to the new block. Fix up any PHI nodes that may need to be updated. */ edge duplicate_succ_block (edge orig_edge, edge exit_edge) { basic_block orig_block, new_block; bool b; gcc_assert (orig_edge); orig_block = orig_edge->dest; #if 0 fprintf(stderr, "Duplicating block %d\n", orig_block->index); gimple_dump_bb (stderr, orig_block, 0, TDF_TREE|TDF_LINENO|TDF_COMMENT); #endif b = gimple_duplicate_sese_region (orig_edge, exit_edge, &orig_block, 1, &new_block); gcc_assert (b); return find_edge (orig_edge->src, new_block); } /* Go through the paths saved in bbs_list_array and make copies of them. */ static void copy_switch_paths (void) { int i, j; edge orig_edge, new_edge, exit_edge; /* Process each path in bbs_list_size. */ for (i = 0; i < n_bbs_list; i++) { #if 0 fprintf(stderr, "(2) Basic blocks [const value is %d], path is:\n", val_array[i]); for (j = 0; j < bbs_list_size[i]; j++) fprintf(stderr, " %d\n", bbs_list_array[i][j]->index); #endif /* For each path in bbs_list_size loop through and copy each block in the path (except the first on where the constant is assigned and the final one where the switch statement goes to. If the path to be copied has only one predecessor do not copy it, that will just create dead blocks. I.e if the first block had 3 predecessors and we made two copies, the remaining one will only have 1 predecessor and we don't need to copy it again. */ if (!single_pred_p (bbs_list_array[i][1])) { for (j = 1; j < bbs_list_size[i]-1; j++) { orig_edge = find_edge (bbs_list_array[i][j-1], bbs_list_array[i][j]); exit_edge = find_edge (bbs_list_array[i][j], bbs_list_array[i][j+1]); new_edge = duplicate_succ_block (orig_edge, exit_edge); bbs_list_array[i][j] = new_edge->dest; } } } } static unsigned int do_switch_shortcut (void) { n_bbs_list = 0; find_switch_shortcuts (); copy_switch_paths (); return 0; } /* The pass gate. */ static bool gate_switch_shortcut (void) { return 1; } struct opt_pass pass_switch_shortcut = { GIMPLE_PASS, "switch_shortcut", /* name */ OPTGROUP_NONE, /* optinfo_flags */ gate_switch_shortcut, /* gate */ do_switch_shortcut, /* execute */ NULL, /* sub */ NULL, /* next */ 0, /* static_pass_number */ (timevar_id_t) 0, /* tv_id */ PROP_cfg | PROP_ssa, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ TODO_update_ssa | TODO_verify_ssa | TODO_verify_stmts | TODO_verify_flow /* todo_flags_finish */ }; int plugin_init (struct plugin_name_args *plugin_info, struct plugin_gcc_version *version) { struct register_pass_info pass_info; if (!plugin_default_version_check (version, &gcc_version)) return 1; #if 0 fprintf (stderr, "In plugin, registering new pass\n"); #endif pass_info.pass = &pass_switch_shortcut; pass_info.reference_pass_name = "ifcombine"; pass_info.ref_pass_instance_number = 1; pass_info.pos_op = PASS_POS_INSERT_AFTER; register_callback (plugin_info->base_name, PLUGIN_PASS_MANAGER_SETUP, NULL, &pass_info); return 0; }
