[PATCH]: Very simple reassociation pass

[Diego Novillo]

On Mon, May 09, 2005 at 02:12:35PM -0400, Daniel Berlin wrote:

> This adds a simple reassociation pass.
> It does no linearization, just rank and hashtable based expression
> rearrangement.  We could do more work and get some more results, but it
> does what i built it to do.
> I'm also not sure concentrating heavily on scalar optimization is going
> to be a win anyway.
> 
Well, I guess this is OK.  You mentioned separately that it has
negligible compile time impact and produces better code.  The
algorithm is relatively straightforward and small, so I don't
have a problem with it.

> Patches to make it do whatever else someone's else's plans for grand
> scheming reassociation are welcome, but i don't have any more particular
> plans right now (I wrote this thing over the weekend :P)
> 
If that's the case, then perhaps you could make either
reassociate_expr a function pointer, or make it a collection of
calls to helpers.

I see that you put it relatively late in the pipeline.  Any
particular reason?  Any ideas where it might have the greatest
impact?

Unless there are any major objections, let's put it in after a
few cleanups (below).


> +static void
> +init_reassoc (void)
> +{
> +  int i;
> +  unsigned int rank = 2;
> +  
> +  tree param;
> +  int *bbs = xmalloc (n_basic_blocks * sizeof (int));
> +  
> +  memset (&reassociate_stats, 0, sizeof (reassociate_stats));
> +
> +  /* Reverse RPO will give us something where deeper loops come later.
>
RPO?  Expand on first use.

> +   */
> +  flow_reverse_top_sort_order_compute (bbs);
> +  bb_rank = xcalloc (n_basic_blocks, sizeof (unsigned int));
>
s/n_basic_blocks/last_basic_block + 1/

> +  value_rank = htab_create (511, valrank_hash,
> +			    valrank_eq, free);
> +  seen_binops = htab_create (511, seen_binop_hash,
> +			     seen_binop_eq, free);
> +
> +  /* Give each argument a distinct rank.   */
> +  for (param = DECL_ARGUMENTS (current_function_decl);
> +       param;
> +       param = TREE_CHAIN (param))
> +    {
> +      if (default_def (param) != NULL)
> +	{
> +	  tree def = default_def (param);
> +	  insert_value_rank (def, ++rank);
> +	}
> +    }
> +  
> +  /* Set up rank for each BB  */
> +  for (i = 0; i < n_basic_blocks; i++)
> +    bb_rank[bbs[i]] = ++rank  << 16;
> +
Ouch.  No.

FOR_EACH_BB (bb)
  bb_rank[bb->index]

You are indexing bb_rank with bb->index, basic blocks are not
consecutive.

> +static unsigned int
> +get_rank (tree e)
> +{
> +  valrank_t vr;
> +
> +  /* Constants have rank 0.  */  
> +  if (is_gimple_min_invariant (e))
> +    return 0;
> +  
> +  /* SSA_NAME's have the rank of the expression they are the result
> +     of.
> +     For globals and uninitialized values, the rank is 0.
> +     For function arguments, use the pre-setup rank.
> +     For PHI nodes, stores, asm statements, etc, we use the rank of
> +     the BB.
> +     For simple operations, the rank is the maximum rank of any of
> +     its operands, or the bb_rank, whichever is less.
> +
> +     I make no claims that this is optimal, however, it gives good
> +     results
> +  */
> +     
Too much spacing.  Also, finish comment with '.  */'

> +      stmt = SSA_NAME_DEF_STMT (e);
> +      if (bb_for_stmt (stmt) == NULL)
> +	return 0;
> +      
return NULL;

> +static bool
> +reassociate_expr (tree bexpr, block_stmt_iterator *currbsi)
> +{
> +  tree lhs = TREE_OPERAND (bexpr, 0);
> +  tree rhs = TREE_OPERAND (bexpr, 1);
> +  tree lhsdef;
> +  tree lhsi;
> +  bool changed = false;
> +  unsigned int lhsrank = get_rank (lhs);
> +  unsigned int rhsrank = get_rank (rhs);
> +
> +  /* I don't want to get into the business of floating point
> +     reassociation.  */

/* Do not reassociate floating point expressions.  */

> +  if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
> +      || !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
> +    return false;
> +    
> +  /* We want the greater ranked operand to be our "LHS" for simplicity
> +     sake.  There is no point in actually modifying the expression, as
> +     update_stmt will simply resort the operands anyway. */
> +  if (lhsrank < rhsrank)
> +    {
> +      tree temp;
> +      unsigned int temp1;
> +      temp = lhs;
> +      lhs = rhs;
> +      rhs = temp;
> +      temp1 = lhsrank;
> +      lhsrank = rhsrank;
> +      rhsrank = temp1;
> +    }
> +
> +  /* If the high ranked operand is an SSA_NAME, and the binary
> +     operator is not something we've already seen somewhere else (IE
> +     may be redundant), attempt to reassociate it.
>
(i.e., it may be redundant).

> +     
> +     We can't reassociate expressions unless the expression we are
> +     going to reassociate with is only used in our current expression,
> +     or else we may screw up other computations. 
>
An example showing what may happen in that case will help here.

> +#if 0
> +		      reassociate_expr (lhsi, &lhsbsi);
> +		      reassociate_expr (bexpr, currbsi);
> +		      update_stmt (lhsdef);
> +		      update_stmt (bsi_stmt (*currbsi));
> +		      lhsbsi = bsi_for_stmt (lhsdef);
> +		      update_stmt (bsi_stmt (lhsbsi));
> +#endif

A failed experiment?

> +
> +/* Reassociate expressions in basic block BB, return true if any
>
s/basic block BB/basic block BB and its dominator children/


Diego.