[(3/7)] Widening multiply-and-accumulate pattern matching

On 01/07/11 13:25, Richard Guenther wrote:
> Well - some operations work the same on both signedness if you
> just care about the twos-complement result.  This includes
> multiplication (but not for example division).  For this special
> case I suggest to not bother trying to invent a generic predicate
> but do something local in tree-ssa-math-opts.c.

OK, here's my updated patch.

I've taken the view that we *know* what size and signedness the result 
of the multiplication is, and we know what size the input to the 
addition must be, so all the check has to do is make sure it does that 
same conversion, even if by a roundabout means.

What I hadn't grasped before is that when extending a value it's the 
source type that is significant, not the destination, so the checks are 
not as complex as I had thought.

So, this patch adds a test to ensure that:

  1. the type is not truncated so far that we lose any information; and

  2. the type is only ever extended in the proper signedness.

Also, just to be absolutely sure, I've also added a little bit of logic 
to permit extends that are then undone by a truncate. I'm really not 
sure what guarantees there are about what sort of cast sequences can 
exist? Is this necessary? I haven't managed to coax it to generated any 
examples of extends followed by truncates myself, but in any case, it's 
hardly any code and it'll make sure it's future proofed.

OK?

Andrew

On Mon, Jul 4, 2011 at 4:23 PM, Andrew Stubbs <ams@codesourcery.com> wrote:
> On 01/07/11 13:25, Richard Guenther wrote:
>>
>> Well - some operations work the same on both signedness if you
>> just care about the twos-complement result.  This includes
>> multiplication (but not for example division).  For this special
>> case I suggest to not bother trying to invent a generic predicate
>> but do something local in tree-ssa-math-opts.c.
>
> OK, here's my updated patch.
>
> I've taken the view that we *know* what size and signedness the result of
> the multiplication is, and we know what size the input to the addition must
> be, so all the check has to do is make sure it does that same conversion,
> even if by a roundabout means.
>
> What I hadn't grasped before is that when extending a value it's the source
> type that is significant, not the destination, so the checks are not as
> complex as I had thought.
>
> So, this patch adds a test to ensure that:
>
>  1. the type is not truncated so far that we lose any information; and
>
>  2. the type is only ever extended in the proper signedness.
>
> Also, just to be absolutely sure, I've also added a little bit of logic to
> permit extends that are then undone by a truncate. I'm really not sure what
> guarantees there are about what sort of cast sequences can exist? Is this
> necessary? I haven't managed to coax it to generated any examples of extends
> followed by truncates myself, but in any case, it's hardly any code and
> it'll make sure it's future proofed.
>
> OK?

I think you should assume that series of widenings, (int)(short)char_variable
are already combined.  Thus I believe you only need to consider a single
conversion in valid_types_for_madd_p.

+/* Check the input types, TYPE1 and TYPE2 to a widening multiply,

what are those types?  Is TYPE1 the result type and TYPE2 the
operand type?  If so why

+  initial_bitsize = TYPE_PRECISION (type1) + TYPE_PRECISION (type2);

this?!

+  initial_unsigned = TYPE_UNSIGNED (type1) && TYPE_UNSIGNED (type2);

that also looks odd.  So probably TYPE1 isn't the result type.  If they
are the types of the operands, then what operand is EXPR for?

I didn't look at the actual implementation of the function because of the
lack of understanding of the inputs.

-  if (TREE_CODE (rhs1) == SSA_NAME)
+  for (tmp = rhs1, rhs1_code = ERROR_MARK;
+       TREE_CODE (tmp) == SSA_NAME
+       && (CONVERT_EXPR_CODE_P (rhs1_code) || rhs1_code == ERROR_MARK);
+       tmp = gimple_assign_rhs1 (rhs1_stmt))
     {
-      rhs1_stmt = SSA_NAME_DEF_STMT (rhs1);
-      if (is_gimple_assign (rhs1_stmt))
-       rhs1_code = gimple_assign_rhs_code (rhs1_stmt);
+      rhs1_stmt = SSA_NAME_DEF_STMT (tmp);
+      if (!is_gimple_assign (rhs1_stmt))
+       break;
+      rhs1_code = gimple_assign_rhs_code (rhs1_stmt);
     }

the result looks a bit like spaghetti code ... and lacks a comment
on what it is trying to do.  It looks like it sees through an arbitrary
number of conversions - possibly ones that will make the
macc invalid, as for (short)int-var * short-var + int-var.  So you'll
be pessimizing code by doing that unconditionally.  As I said
above you should at most consider one intermediate conversion.

I believe the code should be arranged such that only valid
conversions are looked through in the first place.  Valid, in
that the resulting types should still match the macc constraints.

Richard.

> Andrew
>

On 07/07/11 10:58, Richard Guenther wrote:
> I think you should assume that series of widenings, (int)(short)char_variable
> are already combined.  Thus I believe you only need to consider a single
> conversion in valid_types_for_madd_p.

Hmm, I'm not so sure. I'll look into it a bit further.

> +/* Check the input types, TYPE1 and TYPE2 to a widening multiply,
>
> what are those types?  Is TYPE1 the result type and TYPE2 the
> operand type?  If so why

TYPE1 and TYPE2 are the inputs to the multiply. I thought I explained 
that in the comment before the function.

> +  initial_bitsize = TYPE_PRECISION (type1) + TYPE_PRECISION (type2);
>
> this?!

The result of the multiply will be this many bits wide. This may be 
narrower than the type that holds it.

E.g., 16-bit * 8-bit gives a result at most 24-bits wide, which will 
usually be held in a 32- or 64-bit variable.

> +  initial_unsigned = TYPE_UNSIGNED (type1)&&  TYPE_UNSIGNED (type2);
>
> that also looks odd.  So probably TYPE1 isn't the result type.  If they
> are the types of the operands, then what operand is EXPR for?

EXPR, as the comment says, is the addition that follows the multiply.

> -  if (TREE_CODE (rhs1) == SSA_NAME)
> +  for (tmp = rhs1, rhs1_code = ERROR_MARK;
> +       TREE_CODE (tmp) == SSA_NAME
> +&&  (CONVERT_EXPR_CODE_P (rhs1_code) || rhs1_code == ERROR_MARK);
> +       tmp = gimple_assign_rhs1 (rhs1_stmt))
>       {
> -      rhs1_stmt = SSA_NAME_DEF_STMT (rhs1);
> -      if (is_gimple_assign (rhs1_stmt))
> -       rhs1_code = gimple_assign_rhs_code (rhs1_stmt);
> +      rhs1_stmt = SSA_NAME_DEF_STMT (tmp);
> +      if (!is_gimple_assign (rhs1_stmt))
> +       break;
> +      rhs1_code = gimple_assign_rhs_code (rhs1_stmt);
>       }
>
> the result looks a bit like spaghetti code ... and lacks a comment
> on what it is trying to do.  It looks like it sees through an arbitrary
> number of conversions - possibly ones that will make the
> macc invalid, as for (short)int-var * short-var + int-var.  So you'll
> be pessimizing code by doing that unconditionally.  As I said
> above you should at most consider one intermediate conversion.

Ok, I need to add a comment here. The code does indeed look back through 
an arbitrary number of conversions. It is searching for the last real 
operation before the addition, hoping to find a multiply.

> I believe the code should be arranged such that only valid
> conversions are looked through in the first place.  Valid, in
> that the resulting types should still match the macc constraints.

Well, it might be possible to discard some conversions initially, but 
until the multiply is found, and it's input types are known, we can't 
know for certain what conversions are valid.

I think I need to explain what's going on here more clearly.

   1. It finds an addition statement. It's not known yet whether it is 
part of a multiply-and-accumulate, or not.

   2. It follows the conversion chain back from each operand to see if 
it finds a multiply, or widening multiply statement.

   3. If it finds a non-widening multiply, it checks it to see if it 
could be widening multiply-and-accumulate (it will already have been 
rejected as a widening multiply on it's own, but the addition might be 
in a wider mode, or the target might provide multiply-and-accumulate 
insns that don't have corresponding widening multiply insns).

   4. (This is the new bit!) It looks to see if there are any 
conversions between the multiply and addition that can safely be ignored.

   5. If we get here, then emit any necessary conversion statements, and 
convert the addition to a WIDEN_MULT_PLUS_EXPR.

Before these changes, any conversion between the multiply and addition 
statements would prevent optimization, even though there are many cases 
where the conversions are valid, and even inserted automatically.

I'm going to go away and find out whether there are really any cases 
where there can legitimately be more than one conversion, and at least 
update my patch with better commenting.

Thanks for you review.

Andrew

On 07/07/11 11:26, Andrew Stubbs wrote:
> On 07/07/11 10:58, Richard Guenther wrote:
>> I think you should assume that series of widenings,
>> (int)(short)char_variable
>> are already combined.  Thus I believe you only need to consider a single
>> conversion in valid_types_for_madd_p.
>
> Hmm, I'm not so sure. I'll look into it a bit further.

OK, here's a test case that gives multiple conversions:

   long long
   foo (long long a, signed char b, signed char c)
   {
     int bc = b * c;
     return a + (short)bc;
   }

The dump right before the widen_mult pass gives:

   foo (long long int a, signed char b, signed char c)
   {
     int bc;
     long long int D.2018;
     short int D.2017;
     long long int D.2016;
     int D.2015;
     int D.2014;

   <bb 2>:
     D.2014_2 = (int) b_1(D);
     D.2015_4 = (int) c_3(D);
     bc_5 = D.2014_2 * D.2015_4;
     D.2017_6 = (short int) bc_5;
     D.2018_7 = (long long int) D.2017_6;
     D.2016_9 = D.2018_7 + a_8(D);
     return D.2016_9;

   }

Here we have a multiply and accumulate done the long way. The 8-bit 
inputs are widened to 32-bit, multiplied to give a 32-bit result (of 
which only the lower 16-bits contain meaningful data), then truncated to 
16-bits, and sign-extended up to 64-bits ready for the 64-bit addition.

This is slight contrived, perhaps, but not unlike the sort of thing that 
might occur when you have inline functions and macros, and most 
importantly - it is mathematically valid!


So, here's the output from my patched widen_mult pass:

   foo (long long int a, signed char b, signed char c)
   {
     int bc;
     long long int D.2018;
     short int D.2017;
     long long int D.2016;
     int D.2015;
     int D.2014;

   <bb 2>:
     D.2014_2 = (int) b_1(D);
     D.2015_4 = (int) c_3(D);
     bc_5 = b_1(D) w* c_3(D);
     D.2017_6 = (short int) bc_5;
     D.2018_7 = (long long int) D.2017_6;
     D.2016_9 = WIDEN_MULT_PLUS_EXPR <b_1(D), c_3(D), a_8(D)>;
     return D.2016_9;

   }

As you can see, everything except the WIDEN_MULT_PLUS_EXPR statement is 
now redundant. (Ideally, this would be removed now, but in fact it 
doesn't get eliminated until the RTL into_cfglayout pass. This is not 
new behaviour.)


My point is that it's possible to have at least two conversions to 
examine. Is it possible to have more? I don't know, but once I'm dealing 
with two I might as well deal with an arbitrary number.

Andrew

On Thu, Jul 7, 2011 at 1:43 PM, Andrew Stubbs <andrew.stubbs@gmail.com> wrote:
> On 07/07/11 11:26, Andrew Stubbs wrote:
>>
>> On 07/07/11 10:58, Richard Guenther wrote:
>>>
>>> I think you should assume that series of widenings,
>>> (int)(short)char_variable
>>> are already combined.  Thus I believe you only need to consider a single
>>> conversion in valid_types_for_madd_p.
>>
>> Hmm, I'm not so sure. I'll look into it a bit further.
>
> OK, here's a test case that gives multiple conversions:
>
>  long long
>  foo (long long a, signed char b, signed char c)
>  {
>    int bc = b * c;
>    return a + (short)bc;
>  }
>
> The dump right before the widen_mult pass gives:
>
>  foo (long long int a, signed char b, signed char c)
>  {
>    int bc;
>    long long int D.2018;
>    short int D.2017;
>    long long int D.2016;
>    int D.2015;
>    int D.2014;
>
>  <bb 2>:
>    D.2014_2 = (int) b_1(D);
>    D.2015_4 = (int) c_3(D);
>    bc_5 = D.2014_2 * D.2015_4;
>    D.2017_6 = (short int) bc_5;

Ok, so you have a truncation that is a no-op value-wise.  I would
argue that this truncation should be removed independent on
whether we have a widening multiply instruction or not.

The technically most capable place to remove non-value-changing
truncations (and combine them with a successive conversion)
would be value-range propagation.  Which already knows:

Value ranges after VRP:

b_1(D): VARYING
D.2698_2: [-128, 127]
c_3(D): VARYING
D.2699_4: [-128, 127]
bc_5: [-16256, 16384]
D.2701_6: [-16256, 16384]
D.2702_7: [-16256, 16384]
a_8(D): VARYING
D.2700_9: VARYING

thus truncating bc_5 to short does not change the value.

The simplification could be made when looking at the
statement

>    D.2018_7 = (long long int) D.2017_6;

in vrp_fold_stmt, based on the fact that this conversion
converts from a value-preserving intermediate conversion.
Thus the transform would replace the D.2017_6 operand
with bc_5.

So yes, the case appears - but it shouldn't ;)

I'll cook up a quick patch for VRP.

Thanks,
Richard.

>    D.2016_9 = D.2018_7 + a_8(D);
>    return D.2016_9;
>
>  }
>
> Here we have a multiply and accumulate done the long way. The 8-bit inputs
> are widened to 32-bit, multiplied to give a 32-bit result (of which only the
> lower 16-bits contain meaningful data), then truncated to 16-bits, and
> sign-extended up to 64-bits ready for the 64-bit addition.
>
> This is slight contrived, perhaps, but not unlike the sort of thing that
> might occur when you have inline functions and macros, and most importantly
> - it is mathematically valid!
>
>
> So, here's the output from my patched widen_mult pass:
>
>  foo (long long int a, signed char b, signed char c)
>  {
>    int bc;
>    long long int D.2018;
>    short int D.2017;
>    long long int D.2016;
>    int D.2015;
>    int D.2014;
>
>  <bb 2>:
>    D.2014_2 = (int) b_1(D);
>    D.2015_4 = (int) c_3(D);
>    bc_5 = b_1(D) w* c_3(D);
>    D.2017_6 = (short int) bc_5;
>    D.2018_7 = (long long int) D.2017_6;
>    D.2016_9 = WIDEN_MULT_PLUS_EXPR <b_1(D), c_3(D), a_8(D)>;
>    return D.2016_9;
>
>  }
>
> As you can see, everything except the WIDEN_MULT_PLUS_EXPR statement is now
> redundant. (Ideally, this would be removed now, but in fact it doesn't get
> eliminated until the RTL into_cfglayout pass. This is not new behaviour.)
>
>
> My point is that it's possible to have at least two conversions to examine.
> Is it possible to have more? I don't know, but once I'm dealing with two I
> might as well deal with an arbitrary number.
>
> Andrew
>

On Thu, Jul 7, 2011 at 2:28 PM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Thu, Jul 7, 2011 at 1:43 PM, Andrew Stubbs <andrew.stubbs@gmail.com> wrote:
>> On 07/07/11 11:26, Andrew Stubbs wrote:
>>>
>>> On 07/07/11 10:58, Richard Guenther wrote:
>>>>
>>>> I think you should assume that series of widenings,
>>>> (int)(short)char_variable
>>>> are already combined.  Thus I believe you only need to consider a single
>>>> conversion in valid_types_for_madd_p.
>>>
>>> Hmm, I'm not so sure. I'll look into it a bit further.
>>
>> OK, here's a test case that gives multiple conversions:
>>
>>  long long
>>  foo (long long a, signed char b, signed char c)
>>  {
>>    int bc = b * c;
>>    return a + (short)bc;
>>  }
>>
>> The dump right before the widen_mult pass gives:
>>
>>  foo (long long int a, signed char b, signed char c)
>>  {
>>    int bc;
>>    long long int D.2018;
>>    short int D.2017;
>>    long long int D.2016;
>>    int D.2015;
>>    int D.2014;
>>
>>  <bb 2>:
>>    D.2014_2 = (int) b_1(D);
>>    D.2015_4 = (int) c_3(D);
>>    bc_5 = D.2014_2 * D.2015_4;
>>    D.2017_6 = (short int) bc_5;
>
> Ok, so you have a truncation that is a no-op value-wise.  I would
> argue that this truncation should be removed independent on
> whether we have a widening multiply instruction or not.
>
> The technically most capable place to remove non-value-changing
> truncations (and combine them with a successive conversion)
> would be value-range propagation.  Which already knows:
>
> Value ranges after VRP:
>
> b_1(D): VARYING
> D.2698_2: [-128, 127]
> c_3(D): VARYING
> D.2699_4: [-128, 127]
> bc_5: [-16256, 16384]
> D.2701_6: [-16256, 16384]
> D.2702_7: [-16256, 16384]
> a_8(D): VARYING
> D.2700_9: VARYING
>
> thus truncating bc_5 to short does not change the value.
>
> The simplification could be made when looking at the
> statement
>
>>    D.2018_7 = (long long int) D.2017_6;
>
> in vrp_fold_stmt, based on the fact that this conversion
> converts from a value-preserving intermediate conversion.
> Thus the transform would replace the D.2017_6 operand
> with bc_5.
>
> So yes, the case appears - but it shouldn't ;)
>
> I'll cook up a quick patch for VRP.

Like the attached.  I'll finish and properly test it.

Richard.

On 07/07/11 13:37, Richard Guenther wrote:
>> I'll cook up a quick patch for VRP.
>
> Like the attached.  I'll finish and properly test it.

Your patch appears to do the wrong thing for this test case:

int
foo (int a, short b, short c)
{
   int bc = b * c;
   return a + (short)bc;
}

With your patch, the input to the widening-mult pass now looks like this:

foo (int a, short int b, short int c)
{
   int bc;
   int D.2016;
   int D.2015;
   int D.2014;

<bb 2>:
   D.2014_2 = (int) b_1(D);
   D.2015_4 = (int) c_3(D);
   bc_5 = D.2014_2 * D.2015_4;
   D.2016_9 = bc_5 + a_8(D);
   return D.2016_9;

}

It looks like when the user tries to deliberately break the maths your 
patch seems to unbreak it.

Andrew

On Fri, Jul 8, 2011 at 2:44 PM, Andrew Stubbs <ams@codesourcery.com> wrote:
> On 07/07/11 13:37, Richard Guenther wrote:
>>>
>>> I'll cook up a quick patch for VRP.
>>
>> Like the attached.  I'll finish and properly test it.
>
> Your patch appears to do the wrong thing for this test case:
>
> int
> foo (int a, short b, short c)
> {
>  int bc = b * c;
>  return a + (short)bc;
> }
>
> With your patch, the input to the widening-mult pass now looks like this:
>
> foo (int a, short int b, short int c)
> {
>  int bc;
>  int D.2016;
>  int D.2015;
>  int D.2014;
>
> <bb 2>:
>  D.2014_2 = (int) b_1(D);
>  D.2015_4 = (int) c_3(D);
>  bc_5 = D.2014_2 * D.2015_4;
>  D.2016_9 = bc_5 + a_8(D);
>  return D.2016_9;
>
> }
>
> It looks like when the user tries to deliberately break the maths your patch
> seems to unbreak it.

Yeah, I fixed that in the checked in version.

Richard.

> Andrew
>