How do I modify SSA and copy basic blocks?

[Steve Ellcey <sellcey at imgtec dot com>]

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
sellcey@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;
}