tree-optimization: Recognize widened unsigned multiply overflow checks
Checks
| Context |
Check |
Description |
| linaro-tcwg-bot/tcwg_gcc_build--master-arm |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_gcc_check--master-arm |
success
|
Test passed
|
| linaro-tcwg-bot/tcwg_simplebootstrap_build--master-aarch64-bootstrap |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_simplebootstrap_build--master-arm-bootstrap |
success
|
Build passed
|
Commit Message
From: Zhou Xuhang <zhouxh2002@gmail.com>
For unsigned operands, a widened multiplication compared against the maximum value of the narrow type is an overflow check when the widened type is at least twice as precise as the operand type.
Fold this idiom to IFN_MUL_OVERFLOW, matching the existing canonical form used for other unsigned multiplication overflow checks.
gcc/
* match.pd: Simplify widened unsigned multiply comparison against
the narrow type maximum to IFN_MUL_OVERFLOW.
gcc/testsuite/
* g++.target/i386/mul-overflow-widen-1.C: New test.
* g++.target/i386/mul-overflow-widen-2.C: New test.
Signed-off-by: Zhou Xuhang <zhouxh2002@gmail.com>
---
gcc/match.pd | 22 +++++++
.../g++.target/i386/mul-overflow-widen-1.C | 64 +++++++++++++++++++
.../g++.target/i386/mul-overflow-widen-2.C | 36 +++++++++++
3 files changed, 122 insertions(+)
create mode 100644 gcc/testsuite/g++.target/i386/mul-overflow-widen-1.C
create mode 100644 gcc/testsuite/g++.target/i386/mul-overflow-widen-2.C
Comments
On Wed, Jun 3, 2026 at 12:04 PM Xuhang Zhou <zhouxh2002@gmail.com> wrote:
>
> From: Zhou Xuhang <zhouxh2002@gmail.com>
>
> For unsigned operands, a widened multiplication compared against the maximum value of the narrow type is an overflow check when the widened type is at least twice as precise as the operand type.
>
> Fold this idiom to IFN_MUL_OVERFLOW, matching the existing canonical form used for other unsigned multiplication overflow checks.
>
> gcc/
> * match.pd: Simplify widened unsigned multiply comparison against
> the narrow type maximum to IFN_MUL_OVERFLOW.
>
> gcc/testsuite/
> * g++.target/i386/mul-overflow-widen-1.C: New test.
> * g++.target/i386/mul-overflow-widen-2.C: New test.
>
> Signed-off-by: Zhou Xuhang <zhouxh2002@gmail.com>
> ---
> gcc/match.pd | 22 +++++++
> .../g++.target/i386/mul-overflow-widen-1.C | 64 +++++++++++++++++++
> .../g++.target/i386/mul-overflow-widen-2.C | 36 +++++++++++
> 3 files changed, 122 insertions(+)
> create mode 100644 gcc/testsuite/g++.target/i386/mul-overflow-widen-1.C
> create mode 100644 gcc/testsuite/g++.target/i386/mul-overflow-widen-2.C
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 0be4eff818b..5fad200f67b 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -8478,6 +8478,28 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> (with { tree t = TREE_TYPE (@0), cpx = build_complex_type (t); }
> (cmp (imagpart (IFN_MUL_OVERFLOW:cpx @0 @1)) { build_zero_cst (t); })))))
>
> +/* Likewise, ((type) A * B) > max where type is at least twice as wide
> + as the type of unsigned A and B checks whether A * B would overflow. */
> +(for cmp (gt le)
> + out (ne eq)
> + (simplify
> + (cmp:c (mult:s (convert@3 @0) (convert @1)) INTEGER_CST@2)
The :c on the compare should not be necessary.
Given the
/* Similarly, for unsigned operands, (((type) A * B) >> prec) != 0 where type
is at least twice as wide as type of A and B, simplify to
__builtin_mul_overflow (A, B, <unused>). */
(for cmp (eq ne)
(simplify
(cmp (rshift (mult:s (convert@3 @0) (convert @1)) INTEGER_CST@2)
integer_zerop)
pattern I wonder if either variant should be the canonical form even when
there's no support for umulv4? Thus, we'd have a canonicalization patttern
and only one pattern recognizing IFN_MUL_OVERFLOW? The variant
without the shift is one operation less, so I'd declare that canonical?
> + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
> + && INTEGRAL_TYPE_P (TREE_TYPE (@3))
> + && TYPE_UNSIGNED (TREE_TYPE (@0))
> + && TYPE_UNSIGNED (TREE_TYPE (@3))
> + && (TYPE_PRECISION (TREE_TYPE (@3))
> + >= 2 * TYPE_PRECISION (TREE_TYPE (@0)))
> + && TYPE_MAX_VALUE (TREE_TYPE (@0))
> + && (wi::to_widest (@2)
> + == wi::to_widest (TYPE_MAX_VALUE (TREE_TYPE (@0))))
> + && types_match (@0, @1)
> + && type_has_mode_precision_p (TREE_TYPE (@0))
> + && (optab_handler (umulv4_optab, TYPE_MODE (TREE_TYPE (@0)))
> + != CODE_FOR_nothing))
> + (with { tree t = TREE_TYPE (@0), cpx = build_complex_type (t); }
> + (out (imagpart (IFN_MUL_OVERFLOW:cpx @0 @1)) { build_zero_cst (t); })))))
> +
> /* Demote operands of IFN_{ADD,SUB,MUL}_OVERFLOW. */
> (for ovf (IFN_ADD_OVERFLOW IFN_SUB_OVERFLOW IFN_MUL_OVERFLOW)
> (simplify
> diff --git a/gcc/testsuite/g++.target/i386/mul-overflow-widen-1.C b/gcc/testsuite/g++.target/i386/mul-overflow-widen-1.C
> new file mode 100644
> index 00000000000..d1002717a13
> --- /dev/null
> +++ b/gcc/testsuite/g++.target/i386/mul-overflow-widen-1.C
> @@ -0,0 +1,64 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized -masm=att" } */
> +/* { dg-final { scan-tree-dump-times " = \\.MUL_OVERFLOW " 8 "optimized" } } */
> +/* { dg-final { scan-assembler-times "\tmulw\t" 3 } } */
> +/* { dg-final { scan-assembler-times "\tmull\t" 5 } } */
> +/* { dg-final { scan-assembler-times "\tseto\t" 5 } } */
> +/* { dg-final { scan-assembler-times "\tsetno\t" 3 } } */
> +
> +typedef unsigned short uint16_t;
> +typedef unsigned int uint32_t;
> +typedef unsigned long long uint64_t;
> +
> +#define UINT16_MAX 65535U
> +#define UINT32_MAX 4294967295U
> +
> +bool
> +mul16_gt (uint16_t x, uint16_t y)
> +{
> + return uint32_t (x) * y > UINT16_MAX;
> +}
> +
> +bool
> +mul16_le (uint16_t x, uint16_t y)
> +{
> + return uint32_t (x) * y <= UINT16_MAX;
> +}
> +
> +bool
> +mul16_builtin (uint16_t x, uint16_t y)
> +{
> + uint16_t result;
> + return __builtin_mul_overflow (x, y, &result);
> +}
> +
> +bool
> +mul32_gt (uint32_t x, uint32_t y)
> +{
> + return uint64_t (x) * y > UINT32_MAX;
> +}
> +
> +bool
> +mul32_le (uint32_t x, uint32_t y)
> +{
> + return uint64_t (x) * y <= UINT32_MAX;
> +}
> +
> +bool
> +mul32_gt_rev (uint32_t x, uint32_t y)
> +{
> + return UINT32_MAX < uint64_t (x) * y;
> +}
> +
> +bool
> +mul32_le_rev (uint32_t x, uint32_t y)
> +{
> + return UINT32_MAX >= uint64_t (x) * y;
> +}
> +
> +bool
> +mul32_builtin (uint32_t x, uint32_t y)
> +{
> + uint32_t result;
> + return __builtin_mul_overflow (x, y, &result);
> +}
> diff --git a/gcc/testsuite/g++.target/i386/mul-overflow-widen-2.C b/gcc/testsuite/g++.target/i386/mul-overflow-widen-2.C
> new file mode 100644
> index 00000000000..94f5eb9de30
> --- /dev/null
> +++ b/gcc/testsuite/g++.target/i386/mul-overflow-widen-2.C
> @@ -0,0 +1,36 @@
> +/* { dg-do compile { target int128 } } */
> +/* { dg-options "-O2 -fdump-tree-optimized -masm=att" } */
> +/* { dg-final { scan-tree-dump-times " = \\.MUL_OVERFLOW " 4 "optimized" } } */
> +/* { dg-final { scan-assembler-times "\tmulq\t" 4 } } */
> +/* { dg-final { scan-assembler-times "\tseto\t" 3 } } */
> +/* { dg-final { scan-assembler-times "\tsetno\t" 1 } } */
> +
> +typedef unsigned long long uint64_t;
> +typedef unsigned __int128 uint128_t;
> +
> +#define UINT64_MAX 18446744073709551615ULL
> +
> +bool
> +mul64_gt (uint64_t x, uint64_t y)
> +{
> + return uint128_t (x) * y > UINT64_MAX;
> +}
> +
> +bool
> +mul64_le (uint64_t x, uint64_t y)
> +{
> + return uint128_t (x) * y <= UINT64_MAX;
> +}
> +
> +bool
> +mul64_high (uint64_t x, uint64_t y)
> +{
> + return ((__int128) x * y >> 64) != 0;
> +}
> +
> +bool
> +mul64_builtin (uint64_t x, uint64_t y)
> +{
> + uint64_t result;
> + return __builtin_mul_overflow (x, y, &result);
> +}
> --
> 2.43.0
>
@@ -8478,6 +8478,28 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(with { tree t = TREE_TYPE (@0), cpx = build_complex_type (t); }
(cmp (imagpart (IFN_MUL_OVERFLOW:cpx @0 @1)) { build_zero_cst (t); })))))
+/* Likewise, ((type) A * B) > max where type is at least twice as wide
+ as the type of unsigned A and B checks whether A * B would overflow. */
+(for cmp (gt le)
+ out (ne eq)
+ (simplify
+ (cmp:c (mult:s (convert@3 @0) (convert @1)) INTEGER_CST@2)
+ (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
+ && INTEGRAL_TYPE_P (TREE_TYPE (@3))
+ && TYPE_UNSIGNED (TREE_TYPE (@0))
+ && TYPE_UNSIGNED (TREE_TYPE (@3))
+ && (TYPE_PRECISION (TREE_TYPE (@3))
+ >= 2 * TYPE_PRECISION (TREE_TYPE (@0)))
+ && TYPE_MAX_VALUE (TREE_TYPE (@0))
+ && (wi::to_widest (@2)
+ == wi::to_widest (TYPE_MAX_VALUE (TREE_TYPE (@0))))
+ && types_match (@0, @1)
+ && type_has_mode_precision_p (TREE_TYPE (@0))
+ && (optab_handler (umulv4_optab, TYPE_MODE (TREE_TYPE (@0)))
+ != CODE_FOR_nothing))
+ (with { tree t = TREE_TYPE (@0), cpx = build_complex_type (t); }
+ (out (imagpart (IFN_MUL_OVERFLOW:cpx @0 @1)) { build_zero_cst (t); })))))
+
/* Demote operands of IFN_{ADD,SUB,MUL}_OVERFLOW. */
(for ovf (IFN_ADD_OVERFLOW IFN_SUB_OVERFLOW IFN_MUL_OVERFLOW)
(simplify
new file mode 100644
@@ -0,0 +1,64 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -masm=att" } */
+/* { dg-final { scan-tree-dump-times " = \\.MUL_OVERFLOW " 8 "optimized" } } */
+/* { dg-final { scan-assembler-times "\tmulw\t" 3 } } */
+/* { dg-final { scan-assembler-times "\tmull\t" 5 } } */
+/* { dg-final { scan-assembler-times "\tseto\t" 5 } } */
+/* { dg-final { scan-assembler-times "\tsetno\t" 3 } } */
+
+typedef unsigned short uint16_t;
+typedef unsigned int uint32_t;
+typedef unsigned long long uint64_t;
+
+#define UINT16_MAX 65535U
+#define UINT32_MAX 4294967295U
+
+bool
+mul16_gt (uint16_t x, uint16_t y)
+{
+ return uint32_t (x) * y > UINT16_MAX;
+}
+
+bool
+mul16_le (uint16_t x, uint16_t y)
+{
+ return uint32_t (x) * y <= UINT16_MAX;
+}
+
+bool
+mul16_builtin (uint16_t x, uint16_t y)
+{
+ uint16_t result;
+ return __builtin_mul_overflow (x, y, &result);
+}
+
+bool
+mul32_gt (uint32_t x, uint32_t y)
+{
+ return uint64_t (x) * y > UINT32_MAX;
+}
+
+bool
+mul32_le (uint32_t x, uint32_t y)
+{
+ return uint64_t (x) * y <= UINT32_MAX;
+}
+
+bool
+mul32_gt_rev (uint32_t x, uint32_t y)
+{
+ return UINT32_MAX < uint64_t (x) * y;
+}
+
+bool
+mul32_le_rev (uint32_t x, uint32_t y)
+{
+ return UINT32_MAX >= uint64_t (x) * y;
+}
+
+bool
+mul32_builtin (uint32_t x, uint32_t y)
+{
+ uint32_t result;
+ return __builtin_mul_overflow (x, y, &result);
+}
new file mode 100644
@@ -0,0 +1,36 @@
+/* { dg-do compile { target int128 } } */
+/* { dg-options "-O2 -fdump-tree-optimized -masm=att" } */
+/* { dg-final { scan-tree-dump-times " = \\.MUL_OVERFLOW " 4 "optimized" } } */
+/* { dg-final { scan-assembler-times "\tmulq\t" 4 } } */
+/* { dg-final { scan-assembler-times "\tseto\t" 3 } } */
+/* { dg-final { scan-assembler-times "\tsetno\t" 1 } } */
+
+typedef unsigned long long uint64_t;
+typedef unsigned __int128 uint128_t;
+
+#define UINT64_MAX 18446744073709551615ULL
+
+bool
+mul64_gt (uint64_t x, uint64_t y)
+{
+ return uint128_t (x) * y > UINT64_MAX;
+}
+
+bool
+mul64_le (uint64_t x, uint64_t y)
+{
+ return uint128_t (x) * y <= UINT64_MAX;
+}
+
+bool
+mul64_high (uint64_t x, uint64_t y)
+{
+ return ((__int128) x * y >> 64) != 0;
+}
+
+bool
+mul64_builtin (uint64_t x, uint64_t y)
+{
+ uint64_t result;
+ return __builtin_mul_overflow (x, y, &result);
+}