From: Zhou Xuhang <[email protected]>
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.
Canonicalize the shifted high-half form to the widened comparison form, then
fold the comparison form to IFN_MUL_OVERFLOW when the target has direct
unsigned multiply-overflow support.
gcc/
* match.pd: Canonicalize shifted high-half unsigned multiply
overflow checks to widened comparisons. 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 <[email protected]>
---
Thanks for your review! I agree with your idea and updated the patch along
those lines.
Changes in v2:
- Removed the unnecessary :c from the comparison pattern.
- Changed the shifted high-half idiom to canonicalize to the following
widened comparison form.
- Kept the umulv4 optab check only on the final widened-comparison to
IFN_MUL_OVERFLOW fold.
- Added uint16_t and uint64_t/__int128 test coverage.
I also tested the no-umulv4 path by temporarily disabling the final
umulv4-gated fold. In that setup, the shifted form canonicalized to the widened
comparison form as expected.
gcc/match.pd | 31 +++++++--
.../g++.target/i386/mul-overflow-widen-1.C | 64 +++++++++++++++++++
.../g++.target/i386/mul-overflow-widen-2.C | 36 +++++++++++
3 files changed, 127 insertions(+), 4 deletions(-)
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..b9fcda03d4b 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -8457,10 +8457,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(with { tree t = TREE_TYPE (@0), cpx = build_complex_type (t); }
(out (imagpart (IFN_MUL_OVERFLOW:cpx @0 @1)) { build_zero_cst (t); })))))
-/* 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>). */
+/* Similarly, for unsigned operands, (((type) A * B) >> prec) != 0
+ (or == 0) where type is at least twice as wide as type of A and B,
+ canonicalize to the following ((utype) A * B) > max (or <= max) pattern. */
(for cmp (eq ne)
+ out (le gt)
(simplify
(cmp (rshift (mult:s (convert@3 @0) (convert @1)) INTEGER_CST@2)
integer_zerop)
@@ -8472,11 +8473,33 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
&& tree_fits_uhwi_p (@2)
&& tree_to_uhwi (@2) == TYPE_PRECISION (TREE_TYPE (@0))
&& types_match (@0, @1)
+ && TYPE_MAX_VALUE (TREE_TYPE (@0)))
+ (with { tree utype = unsigned_type_for (TREE_TYPE (@3)); }
+ (out (mult:utype (convert:utype @0) (convert:utype @1))
+ { fold_convert (utype, TYPE_MAX_VALUE (TREE_TYPE (@0))); })))))
+
+/* For unsigned operands, ((type) A * B) > max where type is at least twice as
wide
+ as the type of unsigned A and B.
+ Simplify it to __builtin_mul_overflow (A, B, <unused>). */
+(for cmp (gt le)
+ out (ne eq)
+ (simplify
+ (cmp (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); }
- (cmp (imagpart (IFN_MUL_OVERFLOW:cpx @0 @1)) { build_zero_cst (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)
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
