Re: [PATCH]: Very simple reassociation pass

[Daniel Berlin <dberlin at dberlin dot org>]

On Fri, 2005-06-03 at 16:59 -0400, Diego Novillo wrote:
> 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.

okeydoeky.

> 
> > 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.

Sure, i'll function pointerize it.

> 
> 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.

will do.

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

will do.

> 
> > +  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]

That won't work, we need to run the for loop in RPO order so that each
gets assigned a rank in RPO order :)

> 
> You are indexing bb_rank with bb->index

I'm indexing it with the rpo order of basic blocks, not bb->index.

> , basic blocks are not
> consecutive.

I'm not sure why that is relevant?
The RPO computation will find them all, and throw them in the bbs array,
just the same.

<fixing a few small things omitted>
> >
> 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?

Yes and no.

We actually want to reassociate top down recursively, but we can't
because the second we call update_stmt it screws us over by reordering
the operands by something other than rank.
So i'll just remove this for now and leave a note  :)