Re: [PATCH] Fix PR46556 (poor address generation)

["William J. Schmidt" <wschmidt at linux dot vnet dot ibm dot com>]

On Thu, 2011-10-06 at 12:13 +0200, Richard Guenther wrote:
> People have already commented on pieces, so I'm looking only
> at the tree-ssa-reassoc.c pieces (did you consider piggy-backing
> on IVOPTs instead?  The idea is to expose additional CSE
> opportunities, right?  So it's sort-of a strength-reduction
> optimization on scalar code (classically strength reduction
> in loops transforms for (i) { z = i*x; } to z = 0; for (i) { z += x }).
> That might be worth in general, even for non-address cases.
> So - if you rename that thing to tree-ssa-strength-reduce.c you
> can get away without piggy-backing on anything ;)  If you
> structure it to detect a strength reduction opportunity
> (thus, you'd need to match two/multiple of the patterns at the same time)
> that would be a bonus ... generalizing it a little bit would be
> another.

These are all good ideas.  I will think about casting this as a more
general strength reduction over extended basic blocks outside of loops.
First I'll put together some simple tests to see whether we're currently
missing some non-address opportunities.

<snip>

> > +  mult_op0 = TREE_OPERAND (offset, 0);
> > +  mult_op1 = TREE_OPERAND (offset, 1);
> > +
> > +  if (TREE_CODE (mult_op0) != PLUS_EXPR
> > +      || TREE_CODE (mult_op1) != INTEGER_CST
> > +      || TREE_CODE (TREE_OPERAND (mult_op0, 1)) != INTEGER_CST)
> > +    return NULL_TREE;
> > +
> > +  t1 = TREE_OPERAND (base, 0);
> > +  t2 = TREE_OPERAND (mult_op0, 0);
> > +  c1 = TREE_INT_CST_LOW (TREE_OPERAND (base, 1));
> > +  c2 = TREE_INT_CST_LOW (TREE_OPERAND (mult_op0, 1));
> > +  c3 = TREE_INT_CST_LOW (mult_op1);
> 
> Before accessing TREE_INT_CST_LOW you need to make sure the
> constants fit into a HWI using host_integerp () (which
> conveniently includes the check for INTEGER_CST).
> 
> Note that you need to sign-extend the MEM_REF offset,
> thus use mem_ref_offset (base).low instead of
> TREE_INT_CST_LOW (TREE_OPERAND (base, 1)).  Might be worth
> to add a testcase with negative offset ;)

D'oh! >.<

> 
> > +  c4 = bitpos / BITS_PER_UNIT;
> > +  c = c1 + c2 * c3 + c4;
> 
> And you don't know whether this operation overflows.  Thus it's
> probably easiest to use double_ints instead of HOST_WIDE_INTs
> in all of the code.

OK, thanks, will do.

<snip>

> 
> > +  /* Determine whether the expression can be represented with base and
> > +     offset components.  */
> > +  base = get_inner_reference (*expr, &bitsize, &bitpos, &offset, &mode,
> > +			      &unsignedp, &volatilep, false);
> > +  if (!base || !offset)
> > +    return false;
> > +
> > +  /* Look for a restructuring opportunity.  */
> > +  if ((mem_ref = restructure_base_and_offset (expr, gsi, base,
> > +					      offset, bitpos)) == NULL_TREE)
> > +    return false;
> 
> What I'm missing is a check whether the old address computation stmts
> will be dead after the transform.

Hm, not quite sure what to do here.  Prior to the transformation I'll
have an assignment with something like:

ARRAY_REF (COMPONENT_REF (MEM_REF (Ta, Cb), FIELD_DECL c), Td)

on LHS or RHS.  Ta and Td will be part of the replacement.  What should
I be checking for?

<snip>

> >  
> > -      if (is_gimple_assign (stmt)
> > -	  && !stmt_could_throw_p (stmt))
> > +      /* Look for restructuring opportunities within an expression
> > +	 that references memory.  We only do this for blocks not
> > +         contained in loops, since the ivopts machinery does a 
> > +         good job on loop expressions, and we don't want to interfere
> > +	 with other loop optimizations.  */
> > +      if (!in_loop && gimple_vuse (stmt) && gimple_assign_single_p (stmt))
> >  	{
> > +	  tree *lhs, *rhs;
> > +	  lhs = gimple_assign_lhs_ptr (stmt);
> > +	  chgd_mem_ref = restructure_mem_ref (lhs, &gsi) || chgd_mem_ref;
> > +	  rhs = gimple_assign_rhs1_ptr (stmt);
> > +	  chgd_mem_ref = restructure_mem_ref (rhs, &gsi) || chgd_mem_ref;
> 
> It will either be a store or a load, but never both (unless it's an
> aggregate copy which I think we should not handle).  So ...
> 
>   if (gimple_vdef (stmt))
>     ... lhs
>   else if (gimple_vuse (stmt))
>     ... rhs

OK, with your suggested gating on non-BLKmode I agree.

> > +	}
> > +
> > +      else if (is_gimple_assign (stmt)
> > +	       && !stmt_could_throw_p (stmt))
> > +	{
> >  	  tree lhs, rhs1, rhs2;
> >  	  enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
> >  
> > @@ -2489,6 +2615,12 @@ reassociate_bb (basic_block bb)
> >  	    }
> >  	}
> >      }
> > +  /* If memory references have been restructured, immediate uses need
> > +     to be cleaned up.  */
> > +  if (chgd_mem_ref)
> > +    for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> > +      update_stmt (gsi_stmt (gsi));
> 
> ICK.  Definitely a no ;)
> 
> Why does a update_stmt () after the restructure_mem_ref call not work?

Ah, yeah, I meant to check again on that before submitting.  >.< 

IIRC, at some point the update_stmt () following restructure_mem_ref was
still giving me verify errors.  I thought perhaps the statements created
by force_gimple_operand_gsi might be giving me trouble -- threw this in
to work around it and missed it on my pre-submission review.

I'll re-check this.  If for some reason it is the inserted statements, I
can more carefully update just those -- but I just need to go back and
sort it out.  Sorry for letting that slip through.

Thanks for the review!

Bill

> 
> Richard.