[RFC] add generic expansion for MULT_HIGHPART_EXP

Message ID alpine.LNX.2.20.13.1808171514330.2296@monopod.intra.ispras.ru
State New
Headers show
Series
  • [RFC] add generic expansion for MULT_HIGHPART_EXP
Related show

Commit Message

Alexander Monakov Aug. 17, 2018, 12:54 p.m.
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.

Comments

Richard Biener Aug. 20, 2018, 9:35 a.m. | #1
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);
Alexander Monakov Aug. 20, 2018, 10:46 a.m. | #2
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
Pekka Jääskeläinen Aug. 24, 2018, 11:11 a.m. | #3
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
Alexander Monakov Aug. 28, 2018, 5:59 a.m. | #4
> > > 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

>
Richard Biener Aug. 28, 2018, 10:06 a.m. | #5
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

> >
Alexander Monakov Aug. 29, 2018, 2 p.m. | #6
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
Richard Biener Aug. 30, 2018, 8:20 a.m. | #7
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

Patch

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);