Detecting reductions in a smarter fashion

[Daniel Berlin <dberlin at dberlin dot org>]

While looking through the vectorizer code, i noticed that it's reduction
detection is very "rigid" right now, and depends on the order you
process statements and basic blocks (or else something might not be
found to be a reduction def soon enough). It also seems split among
various places.

There is a nice way of detecting all the reductions in a loop, and i've
attached the majority of the code to do it, you just need to fill in a
little code that is vectorizer specific.

Basically, every reduction in a loop will form a cycle in the SSA graph,
like an induction variable.

Thus, if you perform a SCC finding algorithm on the SSA graph, it will
hand you all the components that could be part of the the reduction at
once, instead of you trying to find them piece by piece.

This gives you the advantage that you can perform all the legality
testing, and whether you can vectorize the reduction, having all the
operations in front of you at the same time, and mark them all at once.

It also gives you a means to easily extend the current support for
simple reductions to multi-statement reductions whenever you get around
to it.

The code is also useful for anyone who wants to perform operations on
SCC's found in the SSA graph (It's ripped out of the value numbering
code i'm working on), hence the reason i've sent it to gcc-patches

HTH,
Dan

typedef struct dfs_ssa_aux
{
  /* SCC information.  */
  unsigned int dfsnum;
  bool visited;
  unsigned int low;
  bool on_sccstack;
} *dfs_ssa_aux_t;


/* Next DFS number to assign.  */
static unsigned int next_dfs_num;

/* Stack of SCC components.  */
static VEC (tree, heap) *sccstack;

/* BB->reverse post order number mapping.  */
static int *rpo_numbers;

static inline dfs_ssa_aux_t
DFS_INFO (tree name)
{
  return ((dfs_ssa_aux_t) SSA_NAME_AUX (name));
}

/* Print the components of strongly connected component SCC to OUT. */

static void
print_scc (FILE *out, VEC (tree, heap) *scc)
{
  tree var;
  unsigned int i;

  fprintf (out, "SCC consists of: ");
  for (i = 0; VEC_iterate (tree, scc, i, var); i++)
    {
      print_generic_expr (out, var, 0);
      fprintf (out, " ");
    }
  fprintf (out, "\n");
}

static void
init_dfs (void)
{
 size_t i;
 int j;
 int *rpo_numbers_temp;

 sccstack = NULL;
 next_dfs_num = 1;
 
 rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
 rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
 pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
 
 /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
    the i'th block in RPO order is bb.  We want to map bb's to RPO
    numbers, so we need to rearrange this array.  */
 for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
   rpo_numbers[rpo_numbers_temp[j]] = j;

 XDELETEVEC (rpo_numbers_temp);

 /* Allocate memory for the DFS information.  */
 for (i = 0; i < num_ssa_names; i++)
    {
      tree name = ssa_name (i);
      if (name)
	{
	  SSA_NAME_AUX (name) = XCNEW (struct dfs_ssa_aux);
	  DFS_INFO (name)->valnum = VN_TOP;
	  DFS_INFO (name)->expr = name;
	}
    }
}

static void
free_dfs (void)
{
  for (i = 0; i < num_ssa_names; i++)
    {
      tree name = ssa_name (i);
      if (name)
	{
	  XDELETE (SSA_NAME_AUX (name));
	  SSA_NAME_AUX (name) = NULL;
	}
    }
  VEC_free (tree, heap, sccstack);
  XDELETEVEC (rpo_numbers);
}

/* Return true if NAME is constant in the dominance region containing
   the block HEADER.  */

static bool
is_region_const (tree name, basic_block header)
{
  tree def;
  basic_block block;

  if (is_gimple_min_invariant (name))
    return true;
  def = SSA_NAME_DEF_STMT (name);

  /* If this is live on entry, it will haee an empty definition site. */
  if (IS_EMPTY_STMT (def))
    return true;

  /* Otherwise, see if name is invariant, or it's definition dominates
     header.  */
  block = bb_for_stmt (def);
  return header != block && dominated_by_p (CDI_DOMINATORS, header, block);
}

/* Return true if NAME is in the list of members of SCC.  */

static bool
in_scc (VEC (tree, heap) *scc, tree name)
{
  unsigned int i;
  tree n;

  for (i = 0; VEC_iterate (tree, scc, i, n); i++)
    if (n == name)
      return true;
  return false;
}

/* Process a strongly connected component, SCC.  */
static void
process_scc (VEC (tree, heap) *scc)
{
  basic_block header = NULL;
  unsigned int i;
  tree n;
  bool isreduction = true;
  /* A singleton SCC cannot be a reduction.  */
  if (VEC_length (tree, scc) == 1)
    return;

  /* First, find the header, the outermost node defining some member
     of our SCC.  */
  for (i = 0; VEC_iterate (tree, scc, i, n); i++)
    {
      tree def = SSA_NAME_DEF_STMT (n);
      basic_block defbb = bb_for_stmt (def);

      if (!IS_EMPTY_STMT (def) && defbb)
	if (! header || rpo_numbers[header->index] > rpo_numbers[defbb->index])
	  header = defbb;
    }

  /*
     Any proper reduction will have all of the members either

     1. Contained in the SCC vector if they are loop variant
     2. Dominate header (the outermost basic block containing a member of the
     SCC) if they are loop invariant.  
     
     That, in addition to whatever conditions the vectorizer imposes
     on reductions it can support.  */

  for (i = 0; VEC_iterate (tree, scc, i, n); i++)
    {
      tree def = SSA_NAME_DEF_STMT (n);

      /* XXX: Add code to see if it a supported reduction operation
	 type in okay_reduction_op. */

      if (!(TREE_CODE (def) == MODIFY_EXPR
	    && okay_reduction_op (TREE_OPERAND (def, 1)))
	  && !(TREE_CODE (def) == PHI_NODE))
	{
	  isreduction = false;
	  break;
	}
      else
	{
	  ssa_op_iter iter;
	  use_operand_p usep;

	  /* Furthermore, each operation on a reduction or its components
	     will be be defined cyclically by a member of this scc, or a
	     region constant.  */
	  FOR_EACH_PHI_OR_STMT_USE (usep, def, iter, SSA_OP_USE)
	    {
	      tree operand = USE_FROM_PTR (usep);
	      if (!in_scc (scc, operand) && !is_region_const (operand, header))
		{
		  isreduction = false;
		  break;
		}
	    }
	  /* XXX: Here you have the statements that make up the reduction,
	     and can perform whatever testing you want on them.  */
	}
    }
  if (!isreduction)
    return;
}


/* Depth first search on NAME to discover and process SCC's in the SSA
   graph.  This uses Tarjan's algorithm.  */

static void
DFS (tree name)
{
  ssa_op_iter iter;
  use_operand_p usep;

  /* SCC info */
  DFS_INFO (name)->dfsnum = next_dfs_num++;
  DFS_INFO (name)->visited = true;
  DFS_INFO (name)->low = DFS_INFO (name)->dfsnum;

  VEC_safe_push (tree, heap, sccstack, name);
  DFS_INFO (name)->on_sccstack = true;

  /* Recursively DFS on our operands, looking for SCC's.  */
  if (!IS_EMPTY_STMT (SSA_NAME_DEF_STMT (name)))
    {
      FOR_EACH_PHI_OR_STMT_USE (usep, SSA_NAME_DEF_STMT (name),
				iter, SSA_OP_USE)
	{
	  tree use = USE_FROM_PTR (usep);

	  if (TREE_CODE (use) != SSA_NAME)
	    continue;

	  if (! (DFS_INFO (use)->visited))
	    {
	      DFS (use);
	      DFS_INFO (name)->low = MIN (DFS_INFO (name)->low,
					 DFS_INFO (use)->low);
	    }
	  if (DFS_INFO (use)->dfsnum < DFS_INFO (name)->dfsnum
	      && DFS_INFO (use)->on_sccstack)
	    {
	      DFS_INFO (name)->low = MIN (DFS_INFO (use)->dfsnum,
					  DFS_INFO (name)->low);
	    }
	}
    }

  /* See if we found an SCC.  */
  if (DFS_INFO (name)->low == DFS_INFO (name)->dfsnum)
    {
      VEC (tree, heap) *scc = NULL;
      tree x;

      /* Found an SCC, pop it off the SCC stack and process it.  */
      do
	{
	  x = VEC_pop (tree, sccstack);

	  DFS_INFO (x)->on_sccstack = false;
	  VEC_safe_push (tree, heap, scc, x);
	} while (x != name);

      if (dump_file && (dump_flags & TDF_DETAILS))
	print_scc (dump_file, scc);
      process_scc (scc);

      VEC_free (tree, heap, scc);
    }
}

static void
discover_SCC (void)
{
  size_t i;
  
  for (i = 0; i < num_ssa_names; i++)
    {
      tree name = ssa_name (i);
      if (name && is_gimple_reg (name)
	  && bb_for_stmt (SSA_NAME_DEF_STMT (name))
	  && DFS_INFO (name)->visited == false)
	DFS (name);
    }
}