I decided to take a crack at the coremark optimization (PR 54742) for switch
statements. Since I couldn't figure out the existing jump threading
optimization enough to extend it properly, I decided to try a plugin
optimization pass just for this case and see if I could get that to work.
The basic idea is to find a path from where a variable is assigned a constant
value to where that variable is used in a switch statement. Then I want to
duplicate the blocks in that path (thus removing any alternative entry points
into the path that may give the variable a different value) and plug it into
the cfg.
I think I have code that finds the path that I am interested in, but when
I try to use copy_bbs to copy the basic blocks in order to create my new path,
I get segfaults. I was wondering if anyone could help me understand what I
need to do, in addition to calling copy_bbs, to create my new path and keep
the various ssa and cfg information up to date, either by modifying it or by
blowing it away and regenerating it, I am not worried about compilation speed
at this point so if regenerating all the SSA/cfg data is easiest, I am happy
to do that.
Attached is my plugin as it exists right now and a simple test case using a
switch statement. I am not including the actual coremark code because it is
copyrighted. If you run my example you will see output showing 4 places where
I think I can do my optimization. For example we assign t the value of 0 in
block 2 and from there we go to block 8 and (possibly) to block 3 where we have
our switch statement.
So what I try to do is copy blocks 8 and 3 and change the edge from block
2 to block 8 to go from block 2 to my new copy of block 8 which should
then go to the new copy of block 3. After this we should be able to
optimize the new copy of block 3 to finish with a goto to the 'case 0'
label instead of with a switch/goto.
If you remove the '#if 0' in my code where I comment out the call to
copy_bbs, you will get a seg fault, this is the code that I need help
with. For example, If I copy block 8 and block 3, and there is an edge
from 8 to 3, does copy_bbs automatically create a new edge pointing from the
copy of block 8 to block 3 and replace that in the copied blocks? I think it
does, but I am not sure.
Steve Ellcey
sell...@imgtec.com
Output from the test program using my new optimization phase.
In plugin, registering new pass
Block 2 assigns variable t a constant value of 0
Basic blocks (leading from basic block 2 to switch) are:
8
3
Block 4 assigns variable t a constant value of 1
Basic blocks (leading from basic block 4 to switch) are:
7
8
3
Block 5 assigns variable t a constant value of 2
Basic blocks (leading from basic block 5 to switch) are:
7
8
3
Block 6 assigns variable t a constant value of 1
Basic blocks (leading from basic block 6 to switch) are:
7
8
3
/* 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 that 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. */
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;
}
/* 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 copy bb_list[n-1], we want to leave that alone and
copy bb_list[n-2]...bb_list[0], and change the edge from bb_list[n-1]
to bb_list[n-2] to point to the copy of bb_list[n-2]. Then we
should change the switch in bb_list[0] to a simple goto, but maybe we
can let a later optimization phase (constant propogation) do that for
free. */
static void
create_new_path (basic_block *bbs_list, int n)
{
int i;
basic_block *bbs_list_to_copy = XNEWVEC (basic_block, n);
basic_block *bbs_copies = XNEWVEC (basic_block, n);
basic_block const_bb;
edge orig_edge, new_edge;
/* Put the blocks in 'correct' order. Probably not really needed. */
for (i = 0; i < n-1; i++)
bbs_list_to_copy[i] = bbs_list[n-2-i];
const_bb = bbs_list[n-1];
fprintf(stderr, "Basic blocks (leading from basic block %d to switch) are:\n", const_bb->index);
for (i = 0; i < n-1; i++)
fprintf(stderr, " %d\n", bbs_list_to_copy[i]->index);
#if 0
if (can_copy_bbs_p (bbs_list_to_copy, n-1))
{
orig_edge = find_edge (const_bb, bbs_list_to_copy[0]);
copy_bbs (bbs_list_to_copy, n-1, bbs_copies, &orig_edge, 1, &new_edge, NULL, bbs_list_to_copy[n-2]);
}
#endif
}
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,j;
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);
gcc_assert (find_path (var_bb, bbs_list[n-1]));
/* 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;
fprintf(stderr, "Block %d assigns variable %s a constant value of %d\n", bbs_list[n]->index, name, (int) TREE_INT_CST_LOW (arg));
create_new_path(bbs_list, n + 1);
}
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);
}
}
}
}
/* The main function of the pass scans statements for switches and invokes
process_switch on them. */
static unsigned int
do_switch_shortcut (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_iterator gsi;
for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple stmt = gsi_stmt (gsi);
if (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;
}
/* 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;
fprintf (stderr, "In plugin, registering new pass\n");
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;
}
int foo(char *s, int i, int j)
{
int t;
char c;
t = 0;
c = *s;
while (c != 0) {
switch (t) {
case 0: if (c = 'x') t = 1;
else if (c = 'y') t = 2;
else t = 3;
break;
case 1: if (c = 'y') t = 2;
else t = 3;
break;
case 2: if (c = 'x') t = 1;
else t = 3;
break;
default:
break;
}
s++;
c = *s;
}
return t;
}
