[patch] tree-ssa-forwprop.c: Catch more forward propagation opportunities.

[Jeffrey A Law]

On Fri, 2005-04-15 at 10:52 -0400, Kazu Hirata wrote:
> Hi,
> 
> Attached is a patch to catch more forward propagation opportunities.
> 
> Consider
> 
> int
> foo (int a)
> {
>   int b = a != 0;
>   unsigned char c = b;
>   if (c)
>     return 1;
>   else
>     return 0;
> }
> 
> After the first forwprop, we get
> 
>   b_3 = a_2 != 0;
>   c_4 = (unsigned char) b_3;
>   if (c_4 != 0) goto <L0>; else goto <L2>;
> 
> Note that we can actually propagate the preceding two statements into
> the COND_EXPR and obtain much shorter
> 
>   if (a_2 != 0) goto <L0>; else goto <L2>;
> 
> The patch solves this problem by having a COND_EXPR "eat" an
> integer-integer cast if the rhs of the cast is defined by a
> comparison.  In the example above, b_3 is defined by a comparison, so
> we first propagate the cast into the COND_EXPR and get
> 
>   if (b_3 != 0) goto <L0>; else goto <L2>;
> 
> After that, the existing code in tree-ssa-forwprop.c can forward
> propagate a_2 != 0 into the COND_EXPR and get
> 
>   if (a_2 != 0) goto <L0>; else goto <L2>;
> 
> as desired.
> 
> Without this patch, we forward propagate 4983 statements while
> compiling cc1-i files.  With this patch, we do 6297 statements.  An
> impressive 26% improvement!
> 
> Note that forward propagation into COND_EXPRs is important for both
> jump threading and VRP so that we can create useful conditoinal
> equivalences and add ASSERT_EXPRs, respectively.  I'll post a message
> on this later.
> 
> Although I am working on a more generic combiner that's not restricted
> to COND_EXPRs, and I expect much of the code in tree-ssa-forwprop.c
> will be replaced by fold, I would like to get this patch in anyway as
> a 26% improvement is too good to miss.
> 
> Tested on i686-pc-linux-gnu.  OK to apply?
> 
> Kazu Hirata
> 
> 2005-04-15  Kazu Hirata  <kazu@cs.umass.edu>
> 
> 	PR tree-optimization/21031
> 	* tree-ssa-forwprop.c (ssa_name_defined_by_comparison_p): New.
> 	(forward_propagate_into_cond_1): Call it.  Forward propagate
> 	integer-integer casts into COND_EXPRs.
> 
> 2005-04-15  Kazu Hirata  <kazu@cs.umass.edu>
> 
> 	PR tree-optimization/21031
> 	* gcc.dg/tree-ssa/pr21031.c: New.
I had to ponder this for a while, but I believe your patch is safe and
good.  Please install.

We have to be careful propagating a cast as the cast might do things
like mask off high order bits if the cast is narrowing to an unsigned
type.

However, by only allowing propagation of the cast when the RHS of
the cast is defined by a conditional is safe as the conditional creates
a 0/1 value, which is going to be the same even if we perform a
narrowing cast.

I like the fact that it relies upon existing code to handle the second
propagation opportunity.

Thanks,
Jeff