Combiner fixes

Combiner fixes

[Bernd Schmidt]

[-- Attachment #1: Type: text/plain, Size: 1903 bytes --]

While testing a different ARM patch, I found that I was getting some
code changes that I couldn't explain.  It turned out to be a bug in the
combiner: a CONST_INT is created without using trunc_int_for_mode,
missing a sign extension, and it ends up not matching const_int_operand
for that reason.

While I was there, I also added some extra canonicalization that helps
on ARM (and produces the optimization I was previously only seeing by
accident).  According to the documentation,

   * In combinations of `neg', `mult', `plus', and `minus', the `neg'
     operations (if any) will be moved inside the operations as far as
     possible.  For instance, `(neg (mult A B))' is canonicalized as
     `(mult (neg A) B)', but `(plus (mult (neg A) B) C)' is
     canonicalized as `(minus A (mult B C))'.

It doesn't say so explicitly, but I take this to mean we can and should
change both

(set (reg/v:SI 137 [ q ])
     (plus:SI (mult:SI (neg:SI (reg/v:SI 135 [ y ])) (const_int 2))
              (reg/v:SI 137 [ q ])))

and

(set (reg/v:SI 137 [ q ])
     (plus:SI (mult:SI (reg/v:SI 135 [ y ]) (const_int -2))
              (reg/v:SI 137 [ q ])))

into

(set (reg/v:SI 137 [ q ])
     (minus:SI (reg/v:SI 137 [ q ])
        (mult:SI (reg/v:SI 135 [ y ]) (const_int 2))))

The latter is recognized by the ARM backend.  IMO the canonicalization
of a shift into a mult is supposed to produce multiplications by powers
of two, and those are all positive values.

On ARM, this helps as follow:
-       rsb     r3, r0, r0, lsl #30
-       add     r6, r6, r3, lsl #2
+       sub     r6, r6, r0, lsl #2

I've also added code to transform (mult (neg (...)) (const)) into
multiplication by the negated constant.

Bootstrapped and tested on i686-linux.  There are some ARM-specific bits
in here, since we forgot to mask off unwanted bits in a HOST_WIDE_INT in
some places.  ARM tests are in progress.   Ok?


Bernd

[-- Attachment #2: compoundop.diff --]
[-- Type: text/plain, Size: 4134 bytes --]

	* simplify-rtx.c (simplify_binary_operation_1): Change a multiply of a
	negated value and a constant into a multiply by the negated constant.
	* combine.c (make_compound_operation): Use trunc_int_for_mode when
	generating a MULT with constant.  Canonicalize PLUS involving MULT.
	* config/arm/constraints.md (M): Examine only 32 bits of a
	HOST_WIDE_INT.
	* config/arm/predicates.md (power_of_two_operand): Likewise.
	
Index: config/arm/constraints.md
===================================================================
--- config/arm/constraints.md	(revision 162821)
+++ config/arm/constraints.md	(working copy)
@@ -121,7 +121,7 @@ (define_constraint "M"
  "In Thumb-1 state a constant that is a multiple of 4 in the range 0-1020."
  (and (match_code "const_int")
       (match_test "TARGET_32BIT ? ((ival >= 0 && ival <= 32)
-				 || ((ival & (ival - 1)) == 0))
+				 || (((ival & (ival - 1)) & 0xFFFFFFFF) == 0))
 		   : ival >= 0 && ival <= 1020 && (ival & 3) == 0")))
 
 (define_constraint "N"
Index: config/arm/predicates.md
===================================================================
--- config/arm/predicates.md	(revision 162821)
+++ config/arm/predicates.md	(working copy)
@@ -289,7 +289,7 @@ (define_special_predicate "arm_reg_or_ex
 (define_predicate "power_of_two_operand"
   (match_code "const_int")
 {
-  HOST_WIDE_INT value = INTVAL (op);
+  unsigned HOST_WIDE_INT value = INTVAL (op) & 0xffffffff;
 
   return value != 0 && (value & (value - 1)) == 0;
 })
Index: simplify-rtx.c
===================================================================
--- simplify-rtx.c	(revision 162821)
+++ simplify-rtx.c	(working copy)
@@ -2109,6 +2109,10 @@ simplify_binary_operation_1 (enum rtx_co
       if (trueop1 == constm1_rtx)
 	return simplify_gen_unary (NEG, mode, op0, mode);
 
+      if (GET_CODE (op0) == NEG && CONST_INT_P (trueop1))
+	return simplify_gen_binary (MULT, mode, XEXP (op0, 0),
+				    simplify_gen_unary (NEG, mode, op1, mode));
+      
       /* Maybe simplify x * 0 to 0.  The reduction is not valid if
 	 x is NaN, since x * 0 is then also NaN.  Nor is it valid
 	 when the mode has signed zeros, since multiplying a negative
Index: combine.c
===================================================================
--- combine.c	(revision 162821)
+++ combine.c	(working copy)
@@ -7110,10 +7110,46 @@ make_compound_operation (rtx x, enum rtx
 	  && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT
 	  && INTVAL (XEXP (x, 1)) >= 0)
 	{
+	  HOST_WIDE_INT count = INTVAL (XEXP (x, 1));
+	  HOST_WIDE_INT multval = (HOST_WIDE_INT) 1 << count;
+
 	  new_rtx = make_compound_operation (XEXP (x, 0), next_code);
-	  new_rtx = gen_rtx_MULT (mode, new_rtx,
-			      GEN_INT ((HOST_WIDE_INT) 1
-				       << INTVAL (XEXP (x, 1))));
+	  if (GET_CODE (new_rtx) == NEG)
+	    {
+	      new_rtx = XEXP (new_rtx, 0);
+	      multval = -multval;
+	    }
+	  multval = trunc_int_for_mode (multval, mode);
+	  new_rtx = gen_rtx_MULT (mode, new_rtx, GEN_INT (multval));
+	}
+      break;
+
+    case PLUS:
+      lhs = XEXP (x, 0);
+      rhs = XEXP (x, 1);
+      lhs = make_compound_operation (lhs, MEM);
+      rhs = make_compound_operation (rhs, MEM);
+      if (GET_CODE (lhs) == MULT && GET_CODE (XEXP (lhs, 0)) == NEG
+	  && SCALAR_INT_MODE_P (mode))
+	{
+	  tem = simplify_gen_binary (MULT, mode, XEXP (XEXP (lhs, 0), 0),
+				     XEXP (lhs, 1));
+	  new_rtx = simplify_gen_binary (MINUS, mode, rhs, tem);
+	}
+      else if (GET_CODE (lhs) == MULT
+	       && (CONST_INT_P (XEXP (lhs, 1)) && INTVAL (XEXP (lhs, 1)) < 0))
+	{
+	  tem = simplify_gen_binary (MULT, mode, XEXP (lhs, 0),
+				     simplify_gen_unary (NEG, mode,
+							 XEXP (lhs, 1),
+							 mode));
+	  new_rtx = simplify_gen_binary (MINUS, mode, rhs, tem);
+	}
+      else
+	{
+	  SUBST (XEXP (x, 0), lhs);
+	  SUBST (XEXP (x, 1), rhs);
+	  goto maybe_swap;
 	}
       break;
 
@@ -7345,6 +7381,7 @@ make_compound_operation (rtx x, enum rtx
 	  SUBST (XVECEXP (x, i, j), new_rtx);
 	}
 
+ maybe_swap:
   /* If this is a commutative operation, the changes to the operands
      may have made it noncanonical.  */
   if (COMMUTATIVE_ARITH_P (x)

Re: Combiner fixes

[Paolo Bonzini]

On 08/02/2010 10:37 PM, Bernd Schmidt wrote:
> +      if (GET_CODE (op0) == NEG && CONST_INT_P (trueop1))
> +	return simplify_gen_binary (MULT, mode, XEXP (op0, 0),
> +				    simplify_gen_unary (NEG, mode, op1, mode));

Why not go one step further and try it on all operands:

   if (GET_CODE (op0) == NEG)
     {
       rtx temp = simplify_unary (NEG, mode, op1, mode);
       if (temp)
         return simplify_gen_binary (MULT, mode, XEXP (op0, 0), temp);
     }
   if (GET_CODE (op1) == NEG)
     {
       rtx temp = simplify_unary (NEG, mode, op0, mode);
       if (temp)
         return simplify_gen_binary (MULT, mode, temp, XEXP (op1, 0));
     }

Paolo

Re: Combiner fixes

[Bernd Schmidt]

[-- Attachment #1: Type: text/plain, Size: 2081 bytes --]

On 08/03/2010 09:24 AM, Paolo Bonzini wrote:
> On 08/02/2010 10:37 PM, Bernd Schmidt wrote:
>> +      if (GET_CODE (op0) == NEG && CONST_INT_P (trueop1))
>> +    return simplify_gen_binary (MULT, mode, XEXP (op0, 0),
>> +                    simplify_gen_unary (NEG, mode, op1, mode));
> 
> Why not go one step further and try it on all operands:
> 
>   if (GET_CODE (op0) == NEG)
>     {
>       rtx temp = simplify_unary (NEG, mode, op1, mode);
>       if (temp)
>         return simplify_gen_binary (MULT, mode, XEXP (op0, 0), temp);
>     }
>   if (GET_CODE (op1) == NEG)
>     {
>       rtx temp = simplify_unary (NEG, mode, op0, mode);
>       if (temp)
>         return simplify_gen_binary (MULT, mode, temp, XEXP (op1, 0));
>     }

Done (slight typo in the above, needs simplify_unary_operation), and
also implemented the opposite transformation in combine:
 (minus x (mult y -12345))
becomes
 (plus (mult y 12345) x)

I've now also looked at code generation on i686, where it also seems to
help occasionally:
-       imull   $-12, 4(%ecx), %edx
-       movl    $4, %eax
-       subl    %edx, %eax
+       imull   $12, 4(%ecx), %eax
+       addl    $4, %eax
=========
-       sall    $5, %eax
-       negl    %eax
-       imull   $-2, %eax, %eax
+       sall    $6, %eax

There's a single counterexample I found, in 20040709-2.c:
-       imull   $-1029531031, %ecx, %ebp
-       subl    $740551042, %ebp
+       imull   $1103515245, %ecx, %ebp
+       addl    $12345, %ebp
+       imull   $1103515245, %ebp, %ebp
+       addl    $12345, %ebp

where an intermediate (minus (const) (mult x const)) is not recognized
as a valid pattern in combine, which then prevents later
transformations.  I think it's one of these cases where combine could
benefit from looking at 4 insns.

Bootstrapped and regression tested on i686-linux.  In the ARM tests,
with the previous patch I saw an intermittent segfault on one testcase,
which wasn't reproducible when running the compiler manually, and has
gone away with the new version (tests still running).  I think it's
unrelated.


Bernd

[-- Attachment #2: compoundop2.diff --]
[-- Type: text/plain, Size: 5200 bytes --]

	* simplify-rtx.c (simplify_binary_operation_1): Try to simplify away
	NEG as operand of a MULT by merging it with the other operand.
	* combine.c (make_compound_operation): Use trunc_int_for_mode when
	generating a MULT with constant.  Canonicalize PLUS and MINUS involving
	MULT.
	* config/arm/constraints.md (M): Examine only 32 bits of a
	HOST_WIDE_INT.
	* config/arm/predicates.md (power_of_two_operand): Likewise.
	
Index: config/arm/constraints.md
===================================================================
--- config/arm/constraints.md.orig
+++ config/arm/constraints.md
@@ -121,7 +121,7 @@
  "In Thumb-1 state a constant that is a multiple of 4 in the range 0-1020."
  (and (match_code "const_int")
       (match_test "TARGET_32BIT ? ((ival >= 0 && ival <= 32)
-				 || ((ival & (ival - 1)) == 0))
+				 || (((ival & (ival - 1)) & 0xFFFFFFFF) == 0))
 		   : ival >= 0 && ival <= 1020 && (ival & 3) == 0")))
 
 (define_constraint "N"
Index: config/arm/predicates.md
===================================================================
--- config/arm/predicates.md.orig
+++ config/arm/predicates.md
@@ -289,7 +289,7 @@
 (define_predicate "power_of_two_operand"
   (match_code "const_int")
 {
-  HOST_WIDE_INT value = INTVAL (op);
+  unsigned HOST_WIDE_INT value = INTVAL (op) & 0xffffffff;
 
   return value != 0 && (value & (value - 1)) == 0;
 })
Index: simplify-rtx.c
===================================================================
--- simplify-rtx.c.orig
+++ simplify-rtx.c
@@ -2109,6 +2109,19 @@ simplify_binary_operation_1 (enum rtx_co
       if (trueop1 == constm1_rtx)
 	return simplify_gen_unary (NEG, mode, op0, mode);
 
+      if (GET_CODE (op0) == NEG)
+	{
+	  rtx temp = simplify_unary_operation (NEG, mode, op1, mode);
+	  if (temp)
+	    return simplify_gen_binary (MULT, mode, XEXP (op0, 0), temp);
+	}
+      if (GET_CODE (op1) == NEG)
+	{
+	  rtx temp = simplify_unary_operation (NEG, mode, op0, mode);
+	  if (temp)
+	    return simplify_gen_binary (MULT, mode, temp, XEXP (op1, 0));
+	}
+
       /* Maybe simplify x * 0 to 0.  The reduction is not valid if
 	 x is NaN, since x * 0 is then also NaN.  Nor is it valid
 	 when the mode has signed zeros, since multiplying a negative
Index: combine.c
===================================================================
--- combine.c.orig
+++ combine.c
@@ -7110,13 +7110,79 @@ make_compound_operation (rtx x, enum rtx
 	  && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT
 	  && INTVAL (XEXP (x, 1)) >= 0)
 	{
+	  HOST_WIDE_INT count = INTVAL (XEXP (x, 1));
+	  HOST_WIDE_INT multval = (HOST_WIDE_INT) 1 << count;
+
 	  new_rtx = make_compound_operation (XEXP (x, 0), next_code);
-	  new_rtx = gen_rtx_MULT (mode, new_rtx,
-			      GEN_INT ((HOST_WIDE_INT) 1
-				       << INTVAL (XEXP (x, 1))));
+	  if (GET_CODE (new_rtx) == NEG)
+	    {
+	      new_rtx = XEXP (new_rtx, 0);
+	      multval = -multval;
+	    }
+	  multval = trunc_int_for_mode (multval, mode);
+	  new_rtx = gen_rtx_MULT (mode, new_rtx, GEN_INT (multval));
 	}
       break;
 
+    case PLUS:
+      lhs = XEXP (x, 0);
+      rhs = XEXP (x, 1);
+      lhs = make_compound_operation (lhs, MEM);
+      rhs = make_compound_operation (rhs, MEM);
+      if (GET_CODE (lhs) == MULT && GET_CODE (XEXP (lhs, 0)) == NEG
+	  && SCALAR_INT_MODE_P (mode))
+	{
+	  tem = simplify_gen_binary (MULT, mode, XEXP (XEXP (lhs, 0), 0),
+				     XEXP (lhs, 1));
+	  new_rtx = simplify_gen_binary (MINUS, mode, rhs, tem);
+	}
+      else if (GET_CODE (lhs) == MULT
+	       && (CONST_INT_P (XEXP (lhs, 1)) && INTVAL (XEXP (lhs, 1)) < 0))
+	{
+	  tem = simplify_gen_binary (MULT, mode, XEXP (lhs, 0),
+				     simplify_gen_unary (NEG, mode,
+							 XEXP (lhs, 1),
+							 mode));
+	  new_rtx = simplify_gen_binary (MINUS, mode, rhs, tem);
+	}
+      else
+	{
+	  SUBST (XEXP (x, 0), lhs);
+	  SUBST (XEXP (x, 1), rhs);
+	  goto maybe_swap;
+	}
+      x = gen_lowpart (mode, new_rtx);
+      goto maybe_swap;
+
+    case MINUS:
+      lhs = XEXP (x, 0);
+      rhs = XEXP (x, 1);
+      lhs = make_compound_operation (lhs, MEM);
+      rhs = make_compound_operation (rhs, MEM);
+      if (GET_CODE (rhs) == MULT && GET_CODE (XEXP (rhs, 0)) == NEG
+	  && SCALAR_INT_MODE_P (mode))
+	{
+	  tem = simplify_gen_binary (MULT, mode, XEXP (XEXP (rhs, 0), 0),
+				     XEXP (rhs, 1));
+	  new_rtx = simplify_gen_binary (PLUS, mode, tem, lhs);
+	}
+      else if (GET_CODE (rhs) == MULT
+	       && (CONST_INT_P (XEXP (rhs, 1)) && INTVAL (XEXP (rhs, 1)) < 0))
+	{
+	  tem = simplify_gen_binary (MULT, mode, XEXP (rhs, 0),
+				     simplify_gen_unary (NEG, mode,
+							 XEXP (rhs, 1),
+							 mode));
+	  new_rtx = simplify_gen_binary (PLUS, mode, tem, lhs);
+	}
+      else
+	{
+	  SUBST (XEXP (x, 0), lhs);
+	  SUBST (XEXP (x, 1), rhs);
+	  return x;
+	}
+      return gen_lowpart (mode, new_rtx);
+
     case AND:
       /* If the second operand is not a constant, we can't do anything
 	 with it.  */
@@ -7345,6 +7411,7 @@ make_compound_operation (rtx x, enum rtx
 	  SUBST (XVECEXP (x, i, j), new_rtx);
 	}
 
+ maybe_swap:
   /* If this is a commutative operation, the changes to the operands
      may have made it noncanonical.  */
   if (COMMUTATIVE_ARITH_P (x)

Re: Combiner fixes

[Jeff Law]

  On 08/03/10 08:46, Bernd Schmidt wrote:
> On 08/03/2010 09:24 AM, Paolo Bonzini wrote:
>> On 08/02/2010 10:37 PM, Bernd Schmidt wrote:
>>> +      if (GET_CODE (op0) == NEG&&  CONST_INT_P (trueop1))
>>> +    return simplify_gen_binary (MULT, mode, XEXP (op0, 0),
>>> +                    simplify_gen_unary (NEG, mode, op1, mode));
>> Why not go one step further and try it on all operands:
>>
>>    if (GET_CODE (op0) == NEG)
>>      {
>>        rtx temp = simplify_unary (NEG, mode, op1, mode);
>>        if (temp)
>>          return simplify_gen_binary (MULT, mode, XEXP (op0, 0), temp);
>>      }
>>    if (GET_CODE (op1) == NEG)
>>      {
>>        rtx temp = simplify_unary (NEG, mode, op0, mode);
>>        if (temp)
>>          return simplify_gen_binary (MULT, mode, temp, XEXP (op1, 0));
>>      }
> Done (slight typo in the above, needs simplify_unary_operation), and
> also implemented the opposite transformation in combine:
>   (minus x (mult y -12345))
> becomes
>   (plus (mult y 12345) x)
>
> I've now also looked at code generation on i686, where it also seems to
> help occasionally:
> -       imull   $-12, 4(%ecx), %edx
> -       movl    $4, %eax
> -       subl    %edx, %eax
> +       imull   $12, 4(%ecx), %eax
> +       addl    $4, %eax
> =========
> -       sall    $5, %eax
> -       negl    %eax
> -       imull   $-2, %eax, %eax
> +       sall    $6, %eax
>
> There's a single counterexample I found, in 20040709-2.c:
> -       imull   $-1029531031, %ecx, %ebp
> -       subl    $740551042, %ebp
> +       imull   $1103515245, %ecx, %ebp
> +       addl    $12345, %ebp
> +       imull   $1103515245, %ebp, %ebp
> +       addl    $12345, %ebp
>
> where an intermediate (minus (const) (mult x const)) is not recognized
> as a valid pattern in combine, which then prevents later
> transformations.  I think it's one of these cases where combine could
> benefit from looking at 4 insns.
>
> Bootstrapped and regression tested on i686-linux.  In the ARM tests,
> with the previous patch I saw an intermittent segfault on one testcase,
> which wasn't reproducible when running the compiler manually, and has
> gone away with the new version (tests still running).  I think it's
> unrelated.
OK.
jeff

Re: Combiner fixes

[Bernd Schmidt]

On 08/03/2010 05:00 PM, Jeff Law wrote:
>  On 08/03/10 08:46, Bernd Schmidt wrote:
>> On 08/03/2010 09:24 AM, Paolo Bonzini wrote:
>>> Why not go one step further and try it on all operands:
>>>
>>>    if (GET_CODE (op0) == NEG)
>>>      {
>>>        rtx temp = simplify_unary (NEG, mode, op1, mode);
>>>        if (temp)
>>>          return simplify_gen_binary (MULT, mode, XEXP (op0, 0), temp);
>>>      }

> OK.

Actually, do I have to limit that to integer modes?


Bernd

Re: Combiner fixes

[Richard Earnshaw]

On Tue, 2010-08-03 at 17:10 +0200, Bernd Schmidt wrote:
> On 08/03/2010 05:00 PM, Jeff Law wrote:
> >  On 08/03/10 08:46, Bernd Schmidt wrote:
> >> On 08/03/2010 09:24 AM, Paolo Bonzini wrote:
> >>> Why not go one step further and try it on all operands:
> >>>
> >>>    if (GET_CODE (op0) == NEG)
> >>>      {
> >>>        rtx temp = simplify_unary (NEG, mode, op1, mode);
> >>>        if (temp)
> >>>          return simplify_gen_binary (MULT, mode, XEXP (op0, 0), temp);
> >>>      }
> 
> > OK.
> 
> Actually, do I have to limit that to integer modes?
> 

Probably.  But it should be fast with fast-math (or re-associate or
whatever it's called) enabled.

R.

Re: Combiner fixes

[Jeff Law]

  On 08/03/10 09:10, Bernd Schmidt wrote:
> On 08/03/2010 05:00 PM, Jeff Law wrote:
>>   On 08/03/10 08:46, Bernd Schmidt wrote:
>>> On 08/03/2010 09:24 AM, Paolo Bonzini wrote:
>>>> Why not go one step further and try it on all operands:
>>>>
>>>>     if (GET_CODE (op0) == NEG)
>>>>       {
>>>>         rtx temp = simplify_unary (NEG, mode, op1, mode);
>>>>         if (temp)
>>>>           return simplify_gen_binary (MULT, mode, XEXP (op0, 0), temp);
>>>>       }
>> OK.
> Actually, do I have to limit that to integer modes?
Good point.  Probably since you're effectively reassociating which can 
be bad for FP.

jeff

Re: Combiner fixes

[Paolo Bonzini]

On 08/03/2010 05:16 PM, Jeff Law wrote:
> On 08/03/10 09:10, Bernd Schmidt wrote:
>> On 08/03/2010 05:00 PM, Jeff Law wrote:
>>> On 08/03/10 08:46, Bernd Schmidt wrote:
>>>> On 08/03/2010 09:24 AM, Paolo Bonzini wrote:
>>>>> Why not go one step further and try it on all operands:
>>>>>
>>>>> if (GET_CODE (op0) == NEG)
>>>>> {
>>>>> rtx temp = simplify_unary (NEG, mode, op1, mode);
>>>>> if (temp)
>>>>> return simplify_gen_binary (MULT, mode, XEXP (op0, 0), temp);
>>>>> }
>>> OK.
>> Actually, do I have to limit that to integer modes?
>
> Good point. Probably since you're effectively reassociating which can be
> bad for FP.

"-a * b" to "a * -b" is safe even for non-fast-math, try grepping -A.*B 
in fold-const.c.  This of course assumes that simplify_unary_operation 
itself doesn't do any invalid transformation, but that's a different 
problem.

Paolo

Re: Combiner fixes

[Bernd Schmidt]

On 08/03/2010 05:28 PM, Paolo Bonzini wrote:
> "-a * b" to "a * -b" is safe even for non-fast-math, try grepping -A.*B
> in fold-const.c.  This of course assumes that simplify_unary_operation
> itself doesn't do any invalid transformation, but that's a different
> problem.

That seems convincing, so I'll check it in as-is.  Thanks.


Bernd

Re: Combiner fixes

[Richard Guenther]

On Tue, Aug 3, 2010 at 5:28 PM, Paolo Bonzini <bonzini@gnu.org> wrote:
> On 08/03/2010 05:16 PM, Jeff Law wrote:
>>
>> On 08/03/10 09:10, Bernd Schmidt wrote:
>>>
>>> On 08/03/2010 05:00 PM, Jeff Law wrote:
>>>>
>>>> On 08/03/10 08:46, Bernd Schmidt wrote:
>>>>>
>>>>> On 08/03/2010 09:24 AM, Paolo Bonzini wrote:
>>>>>>
>>>>>> Why not go one step further and try it on all operands:
>>>>>>
>>>>>> if (GET_CODE (op0) == NEG)
>>>>>> {
>>>>>> rtx temp = simplify_unary (NEG, mode, op1, mode);
>>>>>> if (temp)
>>>>>> return simplify_gen_binary (MULT, mode, XEXP (op0, 0), temp);
>>>>>> }
>>>>
>>>> OK.
>>>
>>> Actually, do I have to limit that to integer modes?
>>
>> Good point. Probably since you're effectively reassociating which can be
>> bad for FP.
>
> "-a * b" to "a * -b" is safe even for non-fast-math, try grepping -A.*B in
> fold-const.c.  This of course assumes that simplify_unary_operation itself
> doesn't do any invalid transformation, but that's a different problem.

It's not safe on RTL, please do not add FP reassociation there.
(config/i386/i386.c:ix86_expand_{round,trunc,...} would start
to break).

Richard.

Re: Combiner fixes

[Bernd Schmidt]

On 08/03/2010 05:44 PM, Richard Guenther wrote:
> It's not safe on RTL, please do not add FP reassociation there.
> (config/i386/i386.c:ix86_expand_{round,trunc,...} would start
> to break).

Not a problem (I guess a !FLOAT_MODE_P || flag_associative_math test is
needed), but I guess I don't understand how things would break - I see
no multiply operations in these i386 functions.  Can you elaborate?


Bernd

Re: Combiner fixes

[Richard Guenther]

On Tue, Aug 3, 2010 at 6:01 PM, Bernd Schmidt <bernds@codesourcery.com> wrote:
> On 08/03/2010 05:44 PM, Richard Guenther wrote:
>> It's not safe on RTL, please do not add FP reassociation there.
>> (config/i386/i386.c:ix86_expand_{round,trunc,...} would start
>> to break).
>
> Not a problem (I guess a !FLOAT_MODE_P || flag_associative_math test is
> needed), but I guess I don't understand how things would break - I see
> no multiply operations in these i386 functions.  Can you elaborate?

It was just a general comment to re-associations of FP on RTL,
but more important is that we not start doing constant folding,
re-associating should be fine as long as they are valid without
any fancy math flags.

Richard.

>
> Bernd
>

Re: Combiner fixes

[Richard Guenther]

On Tue, Aug 3, 2010 at 6:06 PM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Tue, Aug 3, 2010 at 6:01 PM, Bernd Schmidt <bernds@codesourcery.com> wrote:
>> On 08/03/2010 05:44 PM, Richard Guenther wrote:
>>> It's not safe on RTL, please do not add FP reassociation there.
>>> (config/i386/i386.c:ix86_expand_{round,trunc,...} would start
>>> to break).
>>
>> Not a problem (I guess a !FLOAT_MODE_P || flag_associative_math test is
>> needed), but I guess I don't understand how things would break - I see
>> no multiply operations in these i386 functions.  Can you elaborate?
>
> It was just a general comment to re-associations of FP on RTL,
> but more important is that we not start doing constant folding,
> re-associating should be fine as long as they are valid without
> any fancy math flags.

Btw, doing more elaborate re-association on RTL would need
carrying PAREN_EXPR support down to RTL, which is an
explicit re-association barrier (dropped during expansion because
we do not re-associate FP on RTL - sofar).

Richard.

Re: Combiner fixes

[Paolo Bonzini]

On 08/03/2010 06:08 PM, Richard Guenther wrote:
> On Tue, Aug 3, 2010 at 6:06 PM, Richard Guenther
> <richard.guenther@gmail.com>  wrote:
>> On Tue, Aug 3, 2010 at 6:01 PM, Bernd Schmidt<bernds@codesourcery.com>  wrote:
>>> On 08/03/2010 05:44 PM, Richard Guenther wrote:
>>>> It's not safe on RTL, please do not add FP reassociation there.
>>>> (config/i386/i386.c:ix86_expand_{round,trunc,...} would start
>>>> to break).
>>>
>>> Not a problem (I guess a !FLOAT_MODE_P || flag_associative_math test is
>>> needed), but I guess I don't understand how things would break - I see
>>> no multiply operations in these i386 functions.  Can you elaborate?
>>
>> It was just a general comment to re-associations of FP on RTL,
>> but more important is that we not start doing constant folding,
>> re-associating should be fine as long as they are valid without
>> any fancy math flags.
>
> Btw, doing more elaborate re-association on RTL would need
> carrying PAREN_EXPR support down to RTL, which is an
> explicit re-association barrier (dropped during expansion because
> we do not re-associate FP on RTL - sofar).

Looks like a bad idea...  If someone ever introduces some world-shaking 
transform on RTL that requires reassociation he/she'll have to live with 
requiring -ffast-math or whatnot.

Paolo

Re: Combiner fixes

[Richard Guenther]

On Tue, Aug 3, 2010 at 6:35 PM, Paolo Bonzini <bonzini@gnu.org> wrote:
> On 08/03/2010 06:08 PM, Richard Guenther wrote:
>>
>> On Tue, Aug 3, 2010 at 6:06 PM, Richard Guenther
>> <richard.guenther@gmail.com>  wrote:
>>>
>>> On Tue, Aug 3, 2010 at 6:01 PM, Bernd Schmidt<bernds@codesourcery.com>
>>>  wrote:
>>>>
>>>> On 08/03/2010 05:44 PM, Richard Guenther wrote:
>>>>>
>>>>> It's not safe on RTL, please do not add FP reassociation there.
>>>>> (config/i386/i386.c:ix86_expand_{round,trunc,...} would start
>>>>> to break).
>>>>
>>>> Not a problem (I guess a !FLOAT_MODE_P || flag_associative_math test is
>>>> needed), but I guess I don't understand how things would break - I see
>>>> no multiply operations in these i386 functions.  Can you elaborate?
>>>
>>> It was just a general comment to re-associations of FP on RTL,
>>> but more important is that we not start doing constant folding,
>>> re-associating should be fine as long as they are valid without
>>> any fancy math flags.
>>
>> Btw, doing more elaborate re-association on RTL would need
>> carrying PAREN_EXPR support down to RTL, which is an
>> explicit re-association barrier (dropped during expansion because
>> we do not re-associate FP on RTL - sofar).
>
> Looks like a bad idea...  If someone ever introduces some world-shaking
> transform on RTL that requires reassociation he/she'll have to live with
> requiring -ffast-math or whatnot.

No, the point is that even with -ffast-math reassociating over
PAREN_EXPR is invalid.

Richard.

> Paolo
>

Re: Combiner fixes

[Bernd Schmidt]

On 08/03/2010 06:06 PM, Richard Guenther wrote:
> On Tue, Aug 3, 2010 at 6:01 PM, Bernd Schmidt <bernds@codesourcery.com> wrote:
>> On 08/03/2010 05:44 PM, Richard Guenther wrote:
>>> It's not safe on RTL, please do not add FP reassociation there.
>>> (config/i386/i386.c:ix86_expand_{round,trunc,...} would start
>>> to break).
>>
>> Not a problem (I guess a !FLOAT_MODE_P || flag_associative_math test is
>> needed), but I guess I don't understand how things would break - I see
>> no multiply operations in these i386 functions.  Can you elaborate?
> 
> It was just a general comment to re-associations of FP on RTL,
> but more important is that we not start doing constant folding,
> re-associating should be fine as long as they are valid without
> any fancy math flags.

Constant folding should be dealt with in simplify_unary_operation (NEG,
...) as Paolo said.

So, what is your opinion about this specific transformation?  Should it
be enabled with flag_associative_math only?


Bernd

Re: Combiner fixes

[Richard Guenther]

On Tue, Aug 3, 2010 at 6:11 PM, Bernd Schmidt <bernds@codesourcery.com> wrote:
> On 08/03/2010 06:06 PM, Richard Guenther wrote:
>> On Tue, Aug 3, 2010 at 6:01 PM, Bernd Schmidt <bernds@codesourcery.com> wrote:
>>> On 08/03/2010 05:44 PM, Richard Guenther wrote:
>>>> It's not safe on RTL, please do not add FP reassociation there.
>>>> (config/i386/i386.c:ix86_expand_{round,trunc,...} would start
>>>> to break).
>>>
>>> Not a problem (I guess a !FLOAT_MODE_P || flag_associative_math test is
>>> needed), but I guess I don't understand how things would break - I see
>>> no multiply operations in these i386 functions.  Can you elaborate?
>>
>> It was just a general comment to re-associations of FP on RTL,
>> but more important is that we not start doing constant folding,
>> re-associating should be fine as long as they are valid without
>> any fancy math flags.
>
> Constant folding should be dealt with in simplify_unary_operation (NEG,
> ...) as Paolo said.
>
> So, what is your opinion about this specific transformation?  Should it
> be enabled with flag_associative_math only?

The specific transformation is always valid as it doesn't change
the outcome of the operation.  It can be done unconditionally.

Richard.

>
> Bernd
>

Re: Combiner fixes

[H.J. Lu]

On Tue, Aug 3, 2010 at 7:46 AM, Bernd Schmidt <bernds@codesourcery.com> wrote:
> On 08/03/2010 09:24 AM, Paolo Bonzini wrote:
>> On 08/02/2010 10:37 PM, Bernd Schmidt wrote:
>>> +      if (GET_CODE (op0) == NEG && CONST_INT_P (trueop1))
>>> +    return simplify_gen_binary (MULT, mode, XEXP (op0, 0),
>>> +                    simplify_gen_unary (NEG, mode, op1, mode));
>>
>> Why not go one step further and try it on all operands:
>>
>>   if (GET_CODE (op0) == NEG)
>>     {
>>       rtx temp = simplify_unary (NEG, mode, op1, mode);
>>       if (temp)
>>         return simplify_gen_binary (MULT, mode, XEXP (op0, 0), temp);
>>     }
>>   if (GET_CODE (op1) == NEG)
>>     {
>>       rtx temp = simplify_unary (NEG, mode, op0, mode);
>>       if (temp)
>>         return simplify_gen_binary (MULT, mode, temp, XEXP (op1, 0));
>>     }
>
> Done (slight typo in the above, needs simplify_unary_operation), and
> also implemented the opposite transformation in combine:
>  (minus x (mult y -12345))
> becomes
>  (plus (mult y 12345) x)
>
> I've now also looked at code generation on i686, where it also seems to
> help occasionally:
> -       imull   $-12, 4(%ecx), %edx
> -       movl    $4, %eax
> -       subl    %edx, %eax
> +       imull   $12, 4(%ecx), %eax
> +       addl    $4, %eax
> =========
> -       sall    $5, %eax
> -       negl    %eax
> -       imull   $-2, %eax, %eax
> +       sall    $6, %eax
>
> There's a single counterexample I found, in 20040709-2.c:
> -       imull   $-1029531031, %ecx, %ebp
> -       subl    $740551042, %ebp
> +       imull   $1103515245, %ecx, %ebp
> +       addl    $12345, %ebp
> +       imull   $1103515245, %ebp, %ebp
> +       addl    $12345, %ebp
>
> where an intermediate (minus (const) (mult x const)) is not recognized
> as a valid pattern in combine, which then prevents later
> transformations.  I think it's one of these cases where combine could
> benefit from looking at 4 insns.
>
> Bootstrapped and regression tested on i686-linux.  In the ARM tests,
> with the previous patch I saw an intermittent segfault on one testcase,
> which wasn't reproducible when running the compiler manually, and has
> gone away with the new version (tests still running).  I think it's
> unrelated.
>
>

This caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45182

-- 
H.J.

Re: Combiner fixes

[Bernd Schmidt]

[-- Attachment #1: Type: text/plain, Size: 496 bytes --]

On 08/04/2010 05:39 PM, H.J. Lu wrote:
> This caused:
> 
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45182

This seems to be a latent bug.  We call make_compound_operation on

(plus:V2DI (ashift:V2DI (reg:V2DI 137)
        (const_int 2 [0x2]))
    (reg:V2DI 145))

and try to convert the shift into a multiplication, and
trunc_int_for_mode fails when asked to do something with V2DImode.

I think it's best not to do any of that for anything but plain integer
modes.  Ok if tests pass?


Bernd

[-- Attachment #2: compoundop-fix.diff --]
[-- Type: text/plain, Size: 2324 bytes --]

	PR middle-end/45182
	* combine.c (make_compound_operation): Don't try to convert
	shifts into multiplications for modes that aren't SCALAR_INT_MODE_P.

	PR middle-end/45182
	* gcc.c-torture/compile/pr45182.c: New test.
Index: combine.c
===================================================================
--- combine.c	(revision 162849)
+++ combine.c	(working copy)
@@ -7093,7 +7093,9 @@ make_compound_operation (rtx x, enum rtx
      address, we stay there.  If we have a comparison, set to COMPARE,
      but once inside, go back to our default of SET.  */
 
-  next_code = (code == MEM || code == PLUS || code == MINUS ? MEM
+  next_code = (code == MEM ? MEM
+	       : ((code == PLUS || code == MINUS)
+		  && SCALAR_INT_MODE_P (mode)) ? MEM
 	       : ((code == COMPARE || COMPARISON_P (x))
 		  && XEXP (x, 1) == const0_rtx) ? COMPARE
 	       : in_code == COMPARE ? SET : in_code);
@@ -7127,8 +7129,8 @@ make_compound_operation (rtx x, enum rtx
     case PLUS:
       lhs = XEXP (x, 0);
       rhs = XEXP (x, 1);
-      lhs = make_compound_operation (lhs, MEM);
-      rhs = make_compound_operation (rhs, MEM);
+      lhs = make_compound_operation (lhs, next_code);
+      rhs = make_compound_operation (rhs, next_code);
       if (GET_CODE (lhs) == MULT && GET_CODE (XEXP (lhs, 0)) == NEG
 	  && SCALAR_INT_MODE_P (mode))
 	{
@@ -7157,8 +7159,8 @@ make_compound_operation (rtx x, enum rtx
     case MINUS:
       lhs = XEXP (x, 0);
       rhs = XEXP (x, 1);
-      lhs = make_compound_operation (lhs, MEM);
-      rhs = make_compound_operation (rhs, MEM);
+      lhs = make_compound_operation (lhs, next_code);
+      rhs = make_compound_operation (rhs, next_code);
       if (GET_CODE (rhs) == MULT && GET_CODE (XEXP (rhs, 0)) == NEG
 	  && SCALAR_INT_MODE_P (mode))
 	{
Index: testsuite/gcc.c-torture/compile/pr45182.c
===================================================================
--- testsuite/gcc.c-torture/compile/pr45182.c	(revision 0)
+++ testsuite/gcc.c-torture/compile/pr45182.c	(revision 0)
@@ -0,0 +1,10 @@
+typedef struct TypHeader {
+  struct TypHeader ** ptr;
+} *TypHandle;
+void PlainRange (TypHandle hdList, long lenList, long low, long inc)
+{
+  long i;
+  for (i = 1; i <= lenList; i++ )
+    (((TypHandle*)((hdList)->ptr))[i] = (((TypHandle) (((long)(low + (i-1) *
+inc) << 2) + 1))));
+}

Re: Combiner fixes

[H.J. Lu]

On Wed, Aug 4, 2010 at 9:30 AM, Bernd Schmidt <bernds@codesourcery.com> wrote:
> On 08/04/2010 05:39 PM, H.J. Lu wrote:
>> This caused:
>>
>> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45182
>
> This seems to be a latent bug.  We call make_compound_operation on
>
> (plus:V2DI (ashift:V2DI (reg:V2DI 137)
>        (const_int 2 [0x2]))
>    (reg:V2DI 145))
>
> and try to convert the shift into a multiplication, and
> trunc_int_for_mode fails when asked to do something with V2DImode.
>
> I think it's best not to do any of that for anything but plain integer
> modes.  Ok if tests pass?
>

Doesn't this testcase require vectorizer? We need to ensure that
vectorizer is effective for both 32bit and 64bit on x86.


-- 
H.J.

Re: Combiner fixes

[Bernd Schmidt]

On 08/04/2010 07:45 PM, H.J. Lu wrote:

> Doesn't this testcase require vectorizer? We need to ensure that
> vectorizer is effective for both 32bit and 64bit on x86.

It failed at just -O3.  Not sure what you mean.


Bernd

Re: Combiner fixes

[H.J. Lu]

On Wed, Aug 4, 2010 at 10:49 AM, Bernd Schmidt <bernds@codesourcery.com> wrote:
> On 08/04/2010 07:45 PM, H.J. Lu wrote:
>
>> Doesn't this testcase require vectorizer? We need to ensure that
>> vectorizer is effective for both 32bit and 64bit on x86.
>
> It failed at just -O3.  Not sure what you mean.
>
>

From your description, it is due to

(plus:V2DI (ashift:V2DI (reg:V2DI 137)
       (const_int 2 [0x2]))
   (reg:V2DI 145))

The testcase is a scalar code. Only vectorizer will generate
V2DI. On ia32, gcc -O3 won't generate V2DI by default:

[hjl@gnu-35 delta]$
/net/gnu-1/export/gnu/import/svn/gcc-test/bld/gcc/xgcc
-B/net/gnu-1/export/gnu/import/svn/gcc-test/bld/gcc/ -S -O3
-ffast-math -funroll-loops  pr45182.c -march=i686
[hjl@gnu-35 delta]$
/net/gnu-1/export/gnu/import/svn/gcc-test/bld/gcc/xgcc
-B/net/gnu-1/export/gnu/import/svn/gcc-test/bld/gcc/ -S -O3
-ffast-math -funroll-loops  pr45182.c -march=i686 -msse2
pr45182.c: In function ‘PlainRange’:
pr45182.c:9:1: internal compiler error: in trunc_int_for_mode, at explow.c:57
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.
[hjl@gnu-35 delta]$

On ia32, you need to enable SSE2 to see the failure.

-- 
H.J.

Re: Combiner fixes

[Bernd Schmidt]

On 08/04/2010 08:00 PM, H.J. Lu wrote:
> On ia32, you need to enable SSE2 to see the failure.

Well, you can always add that to your TORTURE_OPTIONS for testing.


Bernd

Re: Combiner fixes

[H.J. Lu]

On Wed, Aug 4, 2010 at 11:02 AM, Bernd Schmidt <bernds@codesourcery.com> wrote:
> On 08/04/2010 08:00 PM, H.J. Lu wrote:
>> On ia32, you need to enable SSE2 to see the failure.
>
> Well, you can always add that to your TORTURE_OPTIONS for testing.
>

We can't ask everyone to add "-msse2" to TORTURE_OPTIONS on ia32.
Testcase in PR45182 only fails with -O3 -msse2 on ia32. If we don't add -msse2,
we may not know it is broken again in the future.

-- 
H.J.

Re: Combiner fixes

[Bernd Schmidt]

On 08/04/2010 08:08 PM, H.J. Lu wrote:
> On Wed, Aug 4, 2010 at 11:02 AM, Bernd Schmidt <bernds@codesourcery.com> wrote:
>> On 08/04/2010 08:00 PM, H.J. Lu wrote:
>>> On ia32, you need to enable SSE2 to see the failure.
>>
>> Well, you can always add that to your TORTURE_OPTIONS for testing.
>>
> 
> We can't ask everyone to add "-msse2" to TORTURE_OPTIONS on ia32.
> Testcase in PR45182 only fails with -O3 -msse2 on ia32. If we don't add -msse2,
> we may not know it is broken again in the future.

I'd expect some people also test x86_64 where it's covered by -O3.
Placing the testcase in gcc.c-torture gives us wider coverage IMO.  If
it's really necessary we can put a copy in gcc.target, but I don't
really see too much value in that.


Bernd

Re: Combiner fixes

[Richard Guenther]

On Wed, Aug 4, 2010 at 11:10 PM, Bernd Schmidt <bernds@codesourcery.com> wrote:
> On 08/04/2010 08:08 PM, H.J. Lu wrote:
>> On Wed, Aug 4, 2010 at 11:02 AM, Bernd Schmidt <bernds@codesourcery.com> wrote:
>>> On 08/04/2010 08:00 PM, H.J. Lu wrote:
>>>> On ia32, you need to enable SSE2 to see the failure.
>>>
>>> Well, you can always add that to your TORTURE_OPTIONS for testing.
>>>
>>
>> We can't ask everyone to add "-msse2" to TORTURE_OPTIONS on ia32.
>> Testcase in PR45182 only fails with -O3 -msse2 on ia32. If we don't add -msse2,
>> we may not know it is broken again in the future.
>
> I'd expect some people also test x86_64 where it's covered by -O3.
> Placing the testcase in gcc.c-torture gives us wider coverage IMO.  If
> it's really necessary we can put a copy in gcc.target, but I don't
> really see too much value in that.

Me neither.  The patch is ok.

Thanks,
Richard.

>
> Bernd
>

Re: Combiner fixes

[Richard Henderson]

> 	* config/arm/constraints.md (M): Examine only 32 bits of a
> 	HOST_WIDE_INT.
> 	* config/arm/predicates.md (power_of_two_operand): Likewise.

Is this left over from before you fixed the GEN_INT to
be trunc_int_for_mode?  This doesn't seem right...


r~

Re: Combiner fixes

[Bernd Schmidt]

On 08/03/2010 06:05 PM, Richard Henderson wrote:
>> 	* config/arm/constraints.md (M): Examine only 32 bits of a
>> 	HOST_WIDE_INT.
>> 	* config/arm/predicates.md (power_of_two_operand): Likewise.
> 
> Is this left over from before you fixed the GEN_INT to
> be trunc_int_for_mode?  This doesn't seem right...

Why not?  The problem is (1 << 31), which is a power of two, but
negative in SImode and fails the test if sizeof HOST_WIDE_INT > 32.
It's actually needed _after_ fixing the GEN_INT.


Bernd

Re: Combiner fixes

[Richard Henderson]

On 08/03/2010 09:09 AM, Bernd Schmidt wrote:
> On 08/03/2010 06:05 PM, Richard Henderson wrote:
>>> 	* config/arm/constraints.md (M): Examine only 32 bits of a
>>> 	HOST_WIDE_INT.
>>> 	* config/arm/predicates.md (power_of_two_operand): Likewise.
>>
>> Is this left over from before you fixed the GEN_INT to
>> be trunc_int_for_mode?  This doesn't seem right...
> 
> Why not?  The problem is (1 << 31), which is a power of two, but
> negative in SImode and fails the test if sizeof HOST_WIDE_INT > 32.
> It's actually needed _after_ fixing the GEN_INT.

Ah, ok.


r~