[PATCH RFC] add generic expansion for MULT_HIGHPART_EXP

[PATCH RFC] add generic expansion for MULT_HIGHPART_EXP

[Alexander Monakov]

Hello,

We currently have an unfortunate situation where, on the one hand, scalar
MULT_HIGHPART_EXPR is usable only if the backend provides the corresponding
pattern (otherwise ICEs in expand), but on the other hand, the BRIG frontend
wants to make use of it.

I think BRIG FE is making assumptions on which types are going to work (based
on behavior of i386 backend), and this recently broke when the backend stopped
exposing SImode mult-highpart in 64-bit mode, causing PR 86948.

For scalar integer modes it is easy enough to implement generic expansion via
widening multiply (although it still won't work for the widest mode).

Do we want such functionality on trunk?

	* expr.c (expand_expr_real_2) <case MULT_HIGHPART_EXPR>: Add generic
	expansion via widening multiply and shift for integer modes.
	* optabs.c (expand_mult_highpart): Receive 'method' from caller.
	* optabs.h (expand_mult_highpart): Adjust prototype.

diff --git a/gcc/expr.c b/gcc/expr.c
index de6709defd6..b3e33077b3d 100644
--- a/gcc/expr.c
+++ b/gcc/expr.c
@@ -8913,10 +8913,23 @@ expand_expr_real_2 (sepops ops, rtx target, machine_mode tmode,
       goto binop;
 
     case MULT_HIGHPART_EXPR:
-      expand_operands (treeop0, treeop1, subtarget, &op0, &op1, EXPAND_NORMAL);
-      temp = expand_mult_highpart (mode, op0, op1, target, unsignedp);
-      gcc_assert (temp);
-      return temp;
+      {
+	int method = can_mult_highpart_p (mode, unsignedp);
+	if (!method)
+	  {
+	    gcc_assert (GET_MODE_CLASS (mode) == MODE_INT);
+	    machine_mode wmode = GET_MODE_2XWIDER_MODE (mode).require ();
+	    int prec = GET_MODE_UNIT_BITSIZE (mode);
+	    ops->code = WIDEN_MULT_EXPR;
+	    ops->type = build_nonstandard_integer_type (prec * 2, unsignedp);
+	    temp = expand_expr_real_2 (ops, NULL_RTX, wmode, EXPAND_NORMAL);
+	    temp = expand_shift (RSHIFT_EXPR, wmode, temp, prec, target,
+				 unsignedp);
+	    return convert_modes (mode, wmode, temp, unsignedp);
+	  }
+	expand_operands (treeop0, treeop1, subtarget, &op0, &op1, EXPAND_NORMAL);
+	return expand_mult_highpart (mode, op0, op1, target, unsignedp, method);
+      }
 
     case FIXED_CONVERT_EXPR:
       op0 = expand_normal (treeop0);
diff --git a/gcc/optabs.c b/gcc/optabs.c
index cadf4676c98..616d6f86720 100644
--- a/gcc/optabs.c
+++ b/gcc/optabs.c
@@ -5871,20 +5871,17 @@ expand_vec_cmp_expr (tree type, tree exp, rtx target)
 
 rtx
 expand_mult_highpart (machine_mode mode, rtx op0, rtx op1,
-		      rtx target, bool uns_p)
+		      rtx target, bool uns_p, int method)
 {
   struct expand_operand eops[3];
   enum insn_code icode;
-  int method, i;
+  int i;
   machine_mode wmode;
   rtx m1, m2;
   optab tab1, tab2;
 
-  method = can_mult_highpart_p (mode, uns_p);
   switch (method)
     {
-    case 0:
-      return NULL_RTX;
     case 1:
       tab1 = uns_p ? umul_highpart_optab : smul_highpart_optab;
       return expand_binop (mode, tab1, op0, op1, target, uns_p,
diff --git a/gcc/optabs.h b/gcc/optabs.h
index f9a8169daf8..ad78c4cbe76 100644
--- a/gcc/optabs.h
+++ b/gcc/optabs.h
@@ -316,7 +316,7 @@ extern rtx expand_vec_cond_expr (tree, tree, tree, tree, rtx);
 extern rtx expand_vec_series_expr (machine_mode, rtx, rtx, rtx);

 /* Generate code for MULT_HIGHPART_EXPR.  */
-extern rtx expand_mult_highpart (machine_mode, rtx, rtx, rtx, bool);
+extern rtx expand_mult_highpart (machine_mode, rtx, rtx, rtx, bool, int);

 extern rtx expand_sync_lock_test_and_set (rtx, rtx, rtx);
 extern rtx expand_atomic_test_and_set (rtx, rtx, enum memmodel);

[PATCH RFC] gimplefe: expose MULT_HIGHPART_EXPR

[Alexander Monakov]

For testing generic expansion of MULT_HIGHPART_EXPR I chose to expose it
via the GIMPLE FE with the following patch.

"h*" is how tree-pretty-print dumps MULT_HIGHPART_EXPR.

This patch accepts "h<whitespace>*" which ideally shouldn't happen, but
I don't see a simple way to fix that.

Is this desirable for trunk?

Is there general policy for how fancy tree codes should be exposed in
the GIMPLE FE?

	* c/gimple-parser.c (c_parser_gimple_statement): Add "h*" for
	MULT_HIGHPART_EXPR.

diff --git a/gcc/c/gimple-parser.c b/gcc/c/gimple-parser.c
index 1be5d14dc2d..cf05c936166 100644
--- a/gcc/c/gimple-parser.c
+++ b/gcc/c/gimple-parser.c
@@ -450,6 +450,7 @@ c_parser_gimple_statement (c_parser *parser, gimple_seq *seq)
 
    gimple-binary-expression:
      gimple-unary-expression * gimple-unary-expression
+     gimple-unary-expression h* gimple-unary-expression
      gimple-unary-expression / gimple-unary-expression
      gimple-unary-expression % gimple-unary-expression
      gimple-unary-expression + gimple-unary-expression
@@ -544,6 +545,18 @@ c_parser_gimple_binary_expression (c_parser *parser)
     case CPP_OR_OR:
       c_parser_error (parser, "%<||%> not valid in GIMPLE");
       return ret;
+    case CPP_NAME:
+	{
+	  tree id = c_parser_peek_token (parser)->value;
+	  if (strcmp (IDENTIFIER_POINTER (id), "h") == 0
+	      && c_parser_peek_2nd_token (parser)->type == CPP_MULT)
+	    {
+	      c_parser_consume_token (parser);
+	      code = MULT_HIGHPART_EXPR;
+	      break;
+	    }
+	}
+      /* Fallthru.  */
     default:
       /* Not a binary expression.  */
       return lhs;

Re: [PATCH RFC] add generic expansion for MULT_HIGHPART_EXP

[Richard Biener]

On Fri, Aug 17, 2018 at 2:54 PM Alexander Monakov <amonakov@ispras.ru> wrote:
>
> Hello,
>
> We currently have an unfortunate situation where, on the one hand, scalar
> MULT_HIGHPART_EXPR is usable only if the backend provides the corresponding
> pattern (otherwise ICEs in expand), but on the other hand, the BRIG frontend
> wants to make use of it.
>
> I think BRIG FE is making assumptions on which types are going to work (based
> on behavior of i386 backend), and this recently broke when the backend stopped
> exposing SImode mult-highpart in 64-bit mode, causing PR 86948.
>
> For scalar integer modes it is easy enough to implement generic expansion via
> widening multiply (although it still won't work for the widest mode).
>
> Do we want such functionality on trunk?

I think that all tree codes should expand correctly always and
nowadays we should
use IFNs for codes that restrict themselves to cases the backend can handle.

Not sure how many we have left though ...

So - how difficult is it to fix BRIG to not use MULT_HIGHPART_EXPR if
not supported?

Richard.

>         * expr.c (expand_expr_real_2) <case MULT_HIGHPART_EXPR>: Add generic
>         expansion via widening multiply and shift for integer modes.
>         * optabs.c (expand_mult_highpart): Receive 'method' from caller.
>         * optabs.h (expand_mult_highpart): Adjust prototype.
>
> diff --git a/gcc/expr.c b/gcc/expr.c
> index de6709defd6..b3e33077b3d 100644
> --- a/gcc/expr.c
> +++ b/gcc/expr.c
> @@ -8913,10 +8913,23 @@ expand_expr_real_2 (sepops ops, rtx target, machine_mode tmode,
>        goto binop;
>
>      case MULT_HIGHPART_EXPR:
> -      expand_operands (treeop0, treeop1, subtarget, &op0, &op1, EXPAND_NORMAL);
> -      temp = expand_mult_highpart (mode, op0, op1, target, unsignedp);
> -      gcc_assert (temp);
> -      return temp;
> +      {
> +       int method = can_mult_highpart_p (mode, unsignedp);
> +       if (!method)
> +         {
> +           gcc_assert (GET_MODE_CLASS (mode) == MODE_INT);
> +           machine_mode wmode = GET_MODE_2XWIDER_MODE (mode).require ();
> +           int prec = GET_MODE_UNIT_BITSIZE (mode);
> +           ops->code = WIDEN_MULT_EXPR;
> +           ops->type = build_nonstandard_integer_type (prec * 2, unsignedp);
> +           temp = expand_expr_real_2 (ops, NULL_RTX, wmode, EXPAND_NORMAL);
> +           temp = expand_shift (RSHIFT_EXPR, wmode, temp, prec, target,
> +                                unsignedp);
> +           return convert_modes (mode, wmode, temp, unsignedp);
> +         }
> +       expand_operands (treeop0, treeop1, subtarget, &op0, &op1, EXPAND_NORMAL);
> +       return expand_mult_highpart (mode, op0, op1, target, unsignedp, method);
> +      }
>
>      case FIXED_CONVERT_EXPR:
>        op0 = expand_normal (treeop0);
> diff --git a/gcc/optabs.c b/gcc/optabs.c
> index cadf4676c98..616d6f86720 100644
> --- a/gcc/optabs.c
> +++ b/gcc/optabs.c
> @@ -5871,20 +5871,17 @@ expand_vec_cmp_expr (tree type, tree exp, rtx target)
>
>  rtx
>  expand_mult_highpart (machine_mode mode, rtx op0, rtx op1,
> -                     rtx target, bool uns_p)
> +                     rtx target, bool uns_p, int method)
>  {
>    struct expand_operand eops[3];
>    enum insn_code icode;
> -  int method, i;
> +  int i;
>    machine_mode wmode;
>    rtx m1, m2;
>    optab tab1, tab2;
>
> -  method = can_mult_highpart_p (mode, uns_p);
>    switch (method)
>      {
> -    case 0:
> -      return NULL_RTX;
>      case 1:
>        tab1 = uns_p ? umul_highpart_optab : smul_highpart_optab;
>        return expand_binop (mode, tab1, op0, op1, target, uns_p,
> diff --git a/gcc/optabs.h b/gcc/optabs.h
> index f9a8169daf8..ad78c4cbe76 100644
> --- a/gcc/optabs.h
> +++ b/gcc/optabs.h
> @@ -316,7 +316,7 @@ extern rtx expand_vec_cond_expr (tree, tree, tree, tree, rtx);
>  extern rtx expand_vec_series_expr (machine_mode, rtx, rtx, rtx);
>
>  /* Generate code for MULT_HIGHPART_EXPR.  */
> -extern rtx expand_mult_highpart (machine_mode, rtx, rtx, rtx, bool);
> +extern rtx expand_mult_highpart (machine_mode, rtx, rtx, rtx, bool, int);
>
>  extern rtx expand_sync_lock_test_and_set (rtx, rtx, rtx);
>  extern rtx expand_atomic_test_and_set (rtx, rtx, enum memmodel);

Re: [PATCH RFC] gimplefe: expose MULT_HIGHPART_EXPR

[Richard Biener]

On Fri, Aug 17, 2018 at 3:09 PM Alexander Monakov <amonakov@ispras.ru> wrote:
>
> For testing generic expansion of MULT_HIGHPART_EXPR I chose to expose it
> via the GIMPLE FE with the following patch.
>
> "h*" is how tree-pretty-print dumps MULT_HIGHPART_EXPR.
>
> This patch accepts "h<whitespace>*" which ideally shouldn't happen, but
> I don't see a simple way to fix that.
>
> Is this desirable for trunk?
>
> Is there general policy for how fancy tree codes should be exposed in
> the GIMPLE FE?

We generally use __FOO (__ABS, __ABSU, __MEM), so I'd prefer
__MULT_HIGHPART, though while the existing examples parse
nicely for humans binary operands are somewhat awkward here
and thus a function-style __MULT_HIGHPART would be easier to read.

For example for POINTER_PLUS_EXPR we decide based on the type
context what '+' maps to.  Applying that to '*' and MULT_HIGHPART_EXPR
looks possible as well but I guess it would be non-obvious as well.

I suppose a case that will arise at some point is the need for
EXACT_DIV_EXPR which is also not supported right now and dumped
as '/[ex]' currently.

So if you think

 z = x __MULT_HIGHPART y;

is fine then please go with that instead.  And yes, the GIMPLE FE
should eventually support all of GIMPLE.

Richard.

>         * c/gimple-parser.c (c_parser_gimple_statement): Add "h*" for
>         MULT_HIGHPART_EXPR.
>
> diff --git a/gcc/c/gimple-parser.c b/gcc/c/gimple-parser.c
> index 1be5d14dc2d..cf05c936166 100644
> --- a/gcc/c/gimple-parser.c
> +++ b/gcc/c/gimple-parser.c
> @@ -450,6 +450,7 @@ c_parser_gimple_statement (c_parser *parser, gimple_seq *seq)
>
>     gimple-binary-expression:
>       gimple-unary-expression * gimple-unary-expression
> +     gimple-unary-expression h* gimple-unary-expression
>       gimple-unary-expression / gimple-unary-expression
>       gimple-unary-expression % gimple-unary-expression
>       gimple-unary-expression + gimple-unary-expression
> @@ -544,6 +545,18 @@ c_parser_gimple_binary_expression (c_parser *parser)
>      case CPP_OR_OR:
>        c_parser_error (parser, "%<||%> not valid in GIMPLE");
>        return ret;
> +    case CPP_NAME:
> +       {
> +         tree id = c_parser_peek_token (parser)->value;
> +         if (strcmp (IDENTIFIER_POINTER (id), "h") == 0
> +             && c_parser_peek_2nd_token (parser)->type == CPP_MULT)
> +           {
> +             c_parser_consume_token (parser);
> +             code = MULT_HIGHPART_EXPR;
> +             break;
> +           }
> +       }
> +      /* Fallthru.  */
>      default:
>        /* Not a binary expression.  */
>        return lhs;

Re: [PATCH RFC] add generic expansion for MULT_HIGHPART_EXP

[Alexander Monakov]

On Mon, 20 Aug 2018, Richard Biener wrote:

> So - how difficult is it to fix BRIG to not use MULT_HIGHPART_EXPR if
> not supported?

Pekka, can you comment? I think you have fallback paths for vector types
only at the moment?

Does BRIG have mult-highpart for 64-bit integers? On 32-bit targets we
won't be able to easily expand them (but on 64-bit targets it is fine).


For scalar types I think we should prefer to implement a generic expansion
rather than have the frontend query the backend. For vector types I am not
sure.

Alexander

Re: [PATCH RFC] add generic expansion for MULT_HIGHPART_EXP

[Pekka Jääskeläinen]

Hi,

On Mon, Aug 20, 2018 at 1:46 PM Alexander Monakov <amonakov@ispras.ru> wrote:
> > So - how difficult is it to fix BRIG to not use MULT_HIGHPART_EXPR if
> > not supported?
>
> Pekka, can you comment? I think you have fallback paths for vector types
> only at the moment?

I think it involves pretty much moving the code of your patch to the
BRIG frontend.
To me it'd look a bit wrong in terms of "division of responsibilities"
as this is not really
frontend-specific as far as I understand (even if BRIG/HSAIL happened
to be the only language
supporting them currently).

> Does BRIG have mult-highpart for 64-bit integers? On 32-bit targets we
> won't be able to easily expand them (but on 64-bit targets it is fine).

Yes it does. 32b targets are not high priority for BRIG FE at this
point, so I wouldn't
worry about this as we assume HSA's "large" model is used, so this is likely not
the only problem when trying to generate for 32b machines.

> For scalar types I think we should prefer to implement a generic expansion
> rather than have the frontend query the backend. For vector types I am not
> sure.

In my relatively gcc-uneducated humble opinion these both belong more
naturally to a
target-specific expansion or "legalization" pass, which tries to
convert tree nodes to what the target
can support.

BR,
Pekka

Re: [PATCH RFC] add generic expansion for MULT_HIGHPART_EXP

[Alexander Monakov]

> > > So - how difficult is it to fix BRIG to not use MULT_HIGHPART_EXPR if
> > > not supported?

Richard, how should we proceed from here?  Do you like the solution in the
initial mail, or would you prefer something else?  FWIW I agree with Pekka,
no need to burden BRIG FE with expanding mul-highpart.

> > Pekka, can you comment? I think you have fallback paths for vector types
> > only at the moment?
> 
> I think it involves pretty much moving the code of your patch to the
> BRIG frontend.
> To me it'd look a bit wrong in terms of "division of responsibilities"
> as this is not really
> frontend-specific as far as I understand (even if BRIG/HSAIL happened
> to be the only language
> supporting them currently).
> 
> > Does BRIG have mult-highpart for 64-bit integers? On 32-bit targets we
> > won't be able to easily expand them (but on 64-bit targets it is fine).
> 
> Yes it does. 32b targets are not high priority for BRIG FE at this
> point, so I wouldn't
> worry about this as we assume HSA's "large" model is used, so this is likely not
> the only problem when trying to generate for 32b machines.
> 
> > For scalar types I think we should prefer to implement a generic expansion
> > rather than have the frontend query the backend. For vector types I am not
> > sure.
> 
> In my relatively gcc-uneducated humble opinion these both belong more
> naturally to a
> target-specific expansion or "legalization" pass, which tries to
> convert tree nodes to what the target
> can support.
> 
> BR,
> Pekka
> 

Re: [PATCH RFC] add generic expansion for MULT_HIGHPART_EXP

[Richard Biener]

On Tue, Aug 28, 2018 at 7:59 AM Alexander Monakov <amonakov@ispras.ru> wrote:
>
> > > > So - how difficult is it to fix BRIG to not use MULT_HIGHPART_EXPR if
> > > > not supported?
>
> Richard, how should we proceed from here?  Do you like the solution in the
> initial mail, or would you prefer something else?  FWIW I agree with Pekka,
> no need to burden BRIG FE with expanding mul-highpart.

I think that if we want to support MULT_HIGHPART generally then we need
to support it for all modes - what's your plan for 32bit targets here?  This
means providing libgcc fallback implementations for modes we cannot directly
expand to.

I'd also like to see better support for MULT_HIGHPART then, for example
verify_gimple_assign_binary does nothing (TODO).

As for the expansion code I wonder if handling it in expand_binop would
be better?  Do we want to expose highpart multiply to users somehow?

Thanks,
Richard.

> > > Pekka, can you comment? I think you have fallback paths for vector types
> > > only at the moment?
> >
> > I think it involves pretty much moving the code of your patch to the
> > BRIG frontend.
> > To me it'd look a bit wrong in terms of "division of responsibilities"
> > as this is not really
> > frontend-specific as far as I understand (even if BRIG/HSAIL happened
> > to be the only language
> > supporting them currently).
> >
> > > Does BRIG have mult-highpart for 64-bit integers? On 32-bit targets we
> > > won't be able to easily expand them (but on 64-bit targets it is fine).
> >
> > Yes it does. 32b targets are not high priority for BRIG FE at this
> > point, so I wouldn't
> > worry about this as we assume HSA's "large" model is used, so this is likely not
> > the only problem when trying to generate for 32b machines.
> >
> > > For scalar types I think we should prefer to implement a generic expansion
> > > rather than have the frontend query the backend. For vector types I am not
> > > sure.
> >
> > In my relatively gcc-uneducated humble opinion these both belong more
> > naturally to a
> > target-specific expansion or "legalization" pass, which tries to
> > convert tree nodes to what the target
> > can support.
> >
> > BR,
> > Pekka
> >

Re: [PATCH RFC] add generic expansion for MULT_HIGHPART_EXP

[Alexander Monakov]

On Tue, 28 Aug 2018, Richard Biener wrote:
> I think that if we want to support MULT_HIGHPART generally then we need
> to support it for all modes - what's your plan for 32bit targets here?  This
> means providing libgcc fallback implementations for modes we cannot directly
> expand to.

I didn't have a plan in mind, but yes, it seems a fallback implementation
would perform a widening multiplication in 4 or 3 (with Karatsuba's trick)
widest multiplications and throw away the low half.  Signed case may need
more care, I'm not sure at the moment.

> I'd also like to see better support for MULT_HIGHPART then, for example
> verify_gimple_assign_binary does nothing (TODO).

I realize I'm not aware of places that would need to be improved, but
verify_gimple_assign_binary doesn't seem like one of them - as far as
I see it treats MULT_HIGHPART exactly like MULT which looks alright.

> As for the expansion code I wonder if handling it in expand_binop would
> be better?

No idea.

> Do we want to expose highpart multiply to users somehow?

Probably not. But there's another way to look at it: generic expansion for
mul-highpart would open the way for efficient 64-bit division by constants
on 32-bit platforms.

Would you recommend BRIG FE to repair this on their end for now? I don't
mind punting on my patch (but in that case please tell me if I should
commit the gimplefe __MULT_HIGHPART anyway).

Thanks.
Alexander

Re: [PATCH RFC] add generic expansion for MULT_HIGHPART_EXP

[Richard Biener]

On Wed, Aug 29, 2018 at 4:00 PM Alexander Monakov <amonakov@ispras.ru> wrote:
>
> On Tue, 28 Aug 2018, Richard Biener wrote:
> > I think that if we want to support MULT_HIGHPART generally then we need
> > to support it for all modes - what's your plan for 32bit targets here?  This
> > means providing libgcc fallback implementations for modes we cannot directly
> > expand to.
>
> I didn't have a plan in mind, but yes, it seems a fallback implementation
> would perform a widening multiplication in 4 or 3 (with Karatsuba's trick)
> widest multiplications and throw away the low half.  Signed case may need
> more care, I'm not sure at the moment.
>
> > I'd also like to see better support for MULT_HIGHPART then, for example
> > verify_gimple_assign_binary does nothing (TODO).
>
> I realize I'm not aware of places that would need to be improved, but
> verify_gimple_assign_binary doesn't seem like one of them - as far as
> I see it treats MULT_HIGHPART exactly like MULT which looks alright.

OK.

> > As for the expansion code I wonder if handling it in expand_binop would
> > be better?
>
> No idea.

At least there would be the code to try wider modes and the libcall fallback.

> > Do we want to expose highpart multiply to users somehow?
>
> Probably not. But there's another way to look at it: generic expansion for
> mul-highpart would open the way for efficient 64-bit division by constants
> on 32-bit platforms.

I see.  But then when highpart multiply is not available as instruction
probably not - and this should be already possible on RTL then.  And on
GIMPLE if it is available.

> Would you recommend BRIG FE to repair this on their end for now? I don't
> mind punting on my patch (but in that case please tell me if I should
> commit the gimplefe __MULT_HIGHPART anyway).

The gimplefe __MULT_HIGHPART is useful so please go ahead with that.

I'm not convinced there's a compelling reason to allow MULT_HIGHPART
if it eventually expands to more than a single instruction.  The reason
we allow vector operations the HW doesn't understand is generic vector
support in the frontends.  So if we'd provide a generic highpart multiply
intrinsic (ISTR other compilers have this) then this would make sense.

So - instead of attacking this at RTL expansion stage or the BRIG FE
side the option is to lower the code during vector lowering for example
or during gimplification (just to name two passes where we generally
perform lowering steps apart from RTL expansion).

Do others have an opinion on how to handle this?

Richard.

>
> Thanks.
> Alexander