Optimization pass for coremark switch statement

[Steve Ellcey <sellcey at imgtec dot com>]

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
sellcey@imgtec.com

/* Alias analysis for GNU C
   Copyright (C) 2013 Free Software Foundation, Inc.
   Contributed by Steve Ellcey (sellcey@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;
}