[PATCH] expand: Fix UB in choose_mult_variant [PR105533]

[PATCH] expand: Fix UB in choose_mult_variant [PR105533]

[Jakub Jelinek]

Hi!

As documented in the function comment, choose_mult_variant attempts to
compute costs of 3 different cases, val, -val and val - 1.
The -val case is actually only done if val fits into host int, so there
should be no overflow, but the val - 1 case is done unconditionally.
val is shwi (but inside of synth_mult already uhwi), so when val is
HOST_WIDE_INT_MIN, val - 1 invokes UB.  The following patch fixes that
by using val - HOST_WIDE_INT_1U, but I'm not really convinced it would
DTRT for > 64-bit modes, so I've guarded it as well.  Though, arch
would need to have really strange costs that something that could be
expressed as x << 63 would be better expressed as (x * 0x7fffffffffffffff) + 1
In the long term, I think we should just rewrite
choose_mult_variant/synth_mult etc. to work on wide_int.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2024-03-07  Jakub Jelinek  <jakub@redhat.com>

	PR middle-end/105533
	* expmed.cc (choose_mult_variant): Only try the val - 1 variant
	if val is not HOST_WIDE_INT_MIN or if mode has exactly
	HOST_BITS_PER_WIDE_INT precision.  Avoid triggering UB while computing
	val - 1.

	* gcc.dg/pr105533.c: New test.

--- gcc/expmed.cc.jj	2024-01-03 11:51:27.327789537 +0100
+++ gcc/expmed.cc	2024-03-06 16:01:27.898693433 +0100
@@ -3285,11 +3285,15 @@ choose_mult_variant (machine_mode mode,
       limit.latency = mult_cost - op_cost;
     }
 
-  synth_mult (&alg2, val - 1, &limit, mode);
-  alg2.cost.cost += op_cost;
-  alg2.cost.latency += op_cost;
-  if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost))
-    *alg = alg2, *variant = add_variant;
+  if (val != HOST_WIDE_INT_MIN
+      || GET_MODE_UNIT_PRECISION (mode) == HOST_BITS_PER_WIDE_INT)
+    {
+      synth_mult (&alg2, val - HOST_WIDE_INT_1U, &limit, mode);
+      alg2.cost.cost += op_cost;
+      alg2.cost.latency += op_cost;
+      if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost))
+	*alg = alg2, *variant = add_variant;
+    }
 
   return MULT_COST_LESS (&alg->cost, mult_cost);
 }
--- gcc/testsuite/gcc.dg/pr105533.c.jj	2024-03-06 16:03:50.347757251 +0100
+++ gcc/testsuite/gcc.dg/pr105533.c	2024-03-06 16:03:26.226084751 +0100
@@ -0,0 +1,9 @@
+/* PR middle-end/105533 */
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+long long
+foo (long long x, long long y)
+{
+  return ((x < 0) & (y != 0)) * (-__LONG_LONG_MAX__ - 1);
+}

	Jakub

Re: [PATCH] expand: Fix UB in choose_mult_variant [PR105533]

[Richard Biener]

On Thu, 7 Mar 2024, Jakub Jelinek wrote:

> Hi!
> 
> As documented in the function comment, choose_mult_variant attempts to
> compute costs of 3 different cases, val, -val and val - 1.
> The -val case is actually only done if val fits into host int, so there
> should be no overflow, but the val - 1 case is done unconditionally.
> val is shwi (but inside of synth_mult already uhwi), so when val is
> HOST_WIDE_INT_MIN, val - 1 invokes UB.  The following patch fixes that
> by using val - HOST_WIDE_INT_1U, but I'm not really convinced it would
> DTRT for > 64-bit modes, so I've guarded it as well.  Though, arch
> would need to have really strange costs that something that could be
> expressed as x << 63 would be better expressed as (x * 0x7fffffffffffffff) + 1
> In the long term, I think we should just rewrite
> choose_mult_variant/synth_mult etc. to work on wide_int.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

OK.

> 2024-03-07  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR middle-end/105533
> 	* expmed.cc (choose_mult_variant): Only try the val - 1 variant
> 	if val is not HOST_WIDE_INT_MIN or if mode has exactly
> 	HOST_BITS_PER_WIDE_INT precision.  Avoid triggering UB while computing
> 	val - 1.
> 
> 	* gcc.dg/pr105533.c: New test.
> 
> --- gcc/expmed.cc.jj	2024-01-03 11:51:27.327789537 +0100
> +++ gcc/expmed.cc	2024-03-06 16:01:27.898693433 +0100
> @@ -3285,11 +3285,15 @@ choose_mult_variant (machine_mode mode,
>        limit.latency = mult_cost - op_cost;
>      }
>  
> -  synth_mult (&alg2, val - 1, &limit, mode);
> -  alg2.cost.cost += op_cost;
> -  alg2.cost.latency += op_cost;
> -  if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost))
> -    *alg = alg2, *variant = add_variant;
> +  if (val != HOST_WIDE_INT_MIN
> +      || GET_MODE_UNIT_PRECISION (mode) == HOST_BITS_PER_WIDE_INT)
> +    {
> +      synth_mult (&alg2, val - HOST_WIDE_INT_1U, &limit, mode);
> +      alg2.cost.cost += op_cost;
> +      alg2.cost.latency += op_cost;
> +      if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost))
> +	*alg = alg2, *variant = add_variant;
> +    }
>  
>    return MULT_COST_LESS (&alg->cost, mult_cost);
>  }
> --- gcc/testsuite/gcc.dg/pr105533.c.jj	2024-03-06 16:03:50.347757251 +0100
> +++ gcc/testsuite/gcc.dg/pr105533.c	2024-03-06 16:03:26.226084751 +0100
> @@ -0,0 +1,9 @@
> +/* PR middle-end/105533 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2" } */
> +
> +long long
> +foo (long long x, long long y)
> +{
> +  return ((x < 0) & (y != 0)) * (-__LONG_LONG_MAX__ - 1);
> +}
> 
> 	Jakub
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)