From 1982fe2692b6c3b7f969ffc4edac59f9d4359e91 Mon Sep 17 00:00:00 2001 From: Jakub Jelinek Date: Fri, 3 Jun 2022 11:41:21 +0200 Subject: [PATCH] match.pd: Optimize __builtin_mul_overflow_p (x, cst, (stype)0) [PR105777] The following patch is an incremental change to the PR30314 enhancement, this one handles signed types. For signed types (but still, the same for 1st and result element type and non-zero constant that fits into that type), we actually need to watch for overflow in direction to positive and negative infinity and it also depends on whether the cst operand is positive or negative. For __builtin_mul_overflow_p (x, cst, (stype) 0): For cst > 0, we can simplify it to: x > INT_MAX / cst || x < INT_MIN / cst aka: x + (unsigned) (INT_MIN / cst) > (unsigned) (INT_MAX / cst) - (unsigned) (INT_MIN / cst) and for cst < 0 to: x < INT_MAX / cst || x > INT_MIN / cst aka: x + (unsigned) (INT_MAX / cst) > (unsigned) (INT_MIN / cst) - (unsigned) (INT_MAX / cst) Additionally, I've added executable testcases, so we don't just check for the optimization to be performed, but also that it is correct (done that even for the other PR's testcase). 2022-06-03 Jakub Jelinek PR middle-end/30314 PR middle-end/105777 * match.pd (__builtin_mul_overflow_p (x, cst, (stype) 0) -> x > stype_max / cst || x < stype_min / cst): New simplification. * gcc.dg/tree-ssa/pr30314.c: Add noipa attribute to all functions. * gcc.dg/tree-ssa/pr105777.c: New test. * gcc.c-torture/execute/pr30314.c: New test. * gcc.c-torture/execute/pr105777.c: New test. --- gcc/match.pd | 30 +++++++++-- gcc/testsuite/gcc.c-torture/execute/pr105777.c | 73 ++++++++++++++++++++++++++ gcc/testsuite/gcc.c-torture/execute/pr30314.c | 29 ++++++++++ gcc/testsuite/gcc.dg/tree-ssa/pr105777.c | 68 ++++++++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/pr30314.c | 8 +-- 5 files changed, 201 insertions(+), 7 deletions(-) create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr105777.c create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr30314.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr105777.c diff --git a/gcc/match.pd b/gcc/match.pd index 2d3ffc4..44a385b 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -5970,15 +5970,39 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (ovf @1 @0)))) /* Optimize __builtin_mul_overflow_p (x, cst, (utype) 0) if all 3 types - are unsigned to x > (umax / cst). */ + are unsigned to x > (umax / cst). Similarly for signed type, but + in that case it needs to be outside of a range. */ (simplify (imagpart (IFN_MUL_OVERFLOW:cs@2 @0 integer_nonzerop@1)) (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) - && TYPE_UNSIGNED (TREE_TYPE (@0)) && TYPE_MAX_VALUE (TREE_TYPE (@0)) && types_match (TREE_TYPE (@0), TREE_TYPE (TREE_TYPE (@2))) && int_fits_type_p (@1, TREE_TYPE (@0))) - (convert (gt @0 (trunc_div! { TYPE_MAX_VALUE (TREE_TYPE (@0)); } @1))))) + (if (TYPE_UNSIGNED (TREE_TYPE (@0))) + (convert (gt @0 (trunc_div! { TYPE_MAX_VALUE (TREE_TYPE (@0)); } @1))) + (if (TYPE_MIN_VALUE (TREE_TYPE (@0))) + (if (integer_minus_onep (@1)) + (convert (eq @0 { TYPE_MIN_VALUE (TREE_TYPE (@0)); })) + (with + { + tree lo = int_const_binop (TRUNC_DIV_EXPR, + TYPE_MIN_VALUE (TREE_TYPE (@0)), + fold_convert (TREE_TYPE (@0), @1)); + tree hi = int_const_binop (TRUNC_DIV_EXPR, + TYPE_MAX_VALUE (TREE_TYPE (@0)), + fold_convert (TREE_TYPE (@0), @1)); + tree etype = range_check_type (TREE_TYPE (@0)); + if (etype) + { + if (wi::neg_p (wi::to_wide (@1))) + std::swap (lo, hi); + lo = fold_convert (etype, lo); + hi = fold_convert (etype, hi); + hi = int_const_binop (MINUS_EXPR, hi, lo); + } + } + (if (etype) + (convert (gt (minus (convert:etype @0) { lo; }) { hi; }))))))))) /* Simplification of math builtins. These rules must all be optimizations as well as IL simplifications. If there is a possibility that the new diff --git a/gcc/testsuite/gcc.c-torture/execute/pr105777.c b/gcc/testsuite/gcc.c-torture/execute/pr105777.c new file mode 100644 index 0000000..4a21750 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr105777.c @@ -0,0 +1,73 @@ +/* PR middle-end/105777 */ + +#include "../../gcc.dg/tree-ssa/pr105777.c" + +int +main () +{ + if (foo (0) != 0 + || foo (__INT_MAX__ / 35) != 0 + || foo (__INT_MAX__ / 35 + 1) != 1 + || foo (__INT_MAX__) != 1 + || foo ((-__INT_MAX__ - 1) / 35) != 0 + || foo ((-__INT_MAX__ - 1) / 35 - 1) != 1 + || foo (-__INT_MAX__ - 1) != 1) + __builtin_abort (); + if (bar (0) != 0 + || bar (__LONG_MAX__ / 35) != 0 + || bar (__LONG_MAX__ / 35 + 1) != 1 + || bar (__LONG_MAX__) != 1 + || bar ((-__LONG_MAX__ - 1) / 35) != 0 + || bar ((-__LONG_MAX__ - 1) / 35 - 1) != 1 + || bar (-__LONG_MAX__ - 1) != 1) + __builtin_abort (); + if (baz (0) != 0 + || baz (__INT_MAX__ / 42) != 0 + || baz (__INT_MAX__ / 42 + 1) != 1 + || baz (__INT_MAX__) != 1 + || baz ((-__INT_MAX__ - 1) / 42) != 0 + || baz ((-__INT_MAX__ - 1) / 42 - 1) != 1 + || baz (-__INT_MAX__ - 1) != 1) + __builtin_abort (); + if (qux (0) != 0 + || qux (__LONG_MAX__ / 42) != 0 + || qux (__LONG_MAX__ / 42 + 1) != 1 + || qux (__LONG_MAX__) != 1 + || qux ((-__LONG_MAX__ - 1) / 42) != 0 + || qux ((-__LONG_MAX__ - 1) / 42 - 1) != 1 + || qux (-__LONG_MAX__ - 1) != 1) + __builtin_abort (); + if (corge (0) != 0 + || corge (__INT_MAX__ / -39) != 0 + || corge (__INT_MAX__ / -39 - 1) != 1 + || corge (__INT_MAX__) != 1 + || corge ((-__INT_MAX__ - 1) / -39) != 0 + || corge ((-__INT_MAX__ - 1) / -39 + 1) != 1 + || corge (-__INT_MAX__ - 1) != 1) + __builtin_abort (); + if (garply (0) != 0 + || garply (__LONG_MAX__ / -39) != 0 + || garply (__LONG_MAX__ / -39 - 1) != 1 + || garply (__LONG_MAX__) != 1 + || garply ((-__LONG_MAX__ - 1) / -39) != 0 + || garply ((-__LONG_MAX__ - 1) / -39 + 1) != 1 + || garply (-__LONG_MAX__ - 1) != 1) + __builtin_abort (); + if (grault (0) != 0 + || grault (__INT_MAX__ / -46) != 0 + || grault (__INT_MAX__ / -46 - 1) != 1 + || grault (__INT_MAX__) != 1 + || grault ((-__INT_MAX__ - 1) / -46) != 0 + || grault ((-__INT_MAX__ - 1) / -46 + 1) != 1 + || grault (-__INT_MAX__ - 1) != 1) + __builtin_abort (); + if (waldo (0) != 0 + || waldo (__LONG_MAX__ / -46) != 0 + || waldo (__LONG_MAX__ / -46 - 1) != 1 + || waldo (__LONG_MAX__) != 1 + || waldo ((-__LONG_MAX__ - 1) / -46) != 0 + || waldo ((-__LONG_MAX__ - 1) / -46 + 1) != 1 + || waldo (-__LONG_MAX__ - 1) != 1) + __builtin_abort (); + return 0; +} diff --git a/gcc/testsuite/gcc.c-torture/execute/pr30314.c b/gcc/testsuite/gcc.c-torture/execute/pr30314.c new file mode 100644 index 0000000..e1d71e2 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr30314.c @@ -0,0 +1,29 @@ +/* PR middle-end/30314 */ + +#include "../../gcc.dg/tree-ssa/pr30314.c" + +int +main () +{ + if (foo (0) != 0 + || foo (~0U / 35) != 0 + || foo (~0U / 35 + 1) != 1 + || foo (~0U) != 1) + __builtin_abort (); + if (bar (0) != 0 + || bar (~0UL / 35) != 0 + || bar (~0UL / 35 + 1) != 1 + || bar (~0UL) != 1) + __builtin_abort (); + if (baz (0) != 0 + || baz (~0U / 42) != 0 + || baz (~0U / 42 + 1) != 1 + || baz (~0U) != 1) + __builtin_abort (); + if (qux (0) != 0 + || qux (~0UL / 42) != 0 + || qux (~0UL / 42 + 1) != 1 + || qux (~0UL) != 1) + __builtin_abort (); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr105777.c b/gcc/testsuite/gcc.dg/tree-ssa/pr105777.c new file mode 100644 index 0000000..418708b --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr105777.c @@ -0,0 +1,68 @@ +/* PR middle-end/105777 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-final { scan-tree-dump-not "\.MUL_OVERFLOW " "optimized" } } */ +/* { dg-final { scan-tree-dump " \\+ 61356675;" "optimized" { target int32 } } } */ +/* { dg-final { scan-tree-dump " > 122713350" "optimized" { target int32 } } } */ +/* { dg-final { scan-tree-dump " \\+ 263524915338707880" "optimized" { target lp64 } } } */ +/* { dg-final { scan-tree-dump " > 527049830677415760" "optimized" { target lp64 } } } */ +/* { dg-final { scan-tree-dump " \\+ 51130563" "optimized" { target int32 } } } */ +/* { dg-final { scan-tree-dump " > 102261126" "optimized" { target int32 } } } */ +/* { dg-final { scan-tree-dump " \\+ 219604096115589900" "optimized" { target lp64 } } } */ +/* { dg-final { scan-tree-dump " > 439208192231179800" "optimized" { target lp64 } } } */ +/* { dg-final { scan-tree-dump " \\+ 55063683;" "optimized" { target int32 } } } */ +/* { dg-final { scan-tree-dump " > 110127366" "optimized" { target int32 } } } */ +/* { dg-final { scan-tree-dump " \\+ 236496718893712200" "optimized" { target lp64 } } } */ +/* { dg-final { scan-tree-dump " > 472993437787424400" "optimized" { target lp64 } } } */ +/* { dg-final { scan-tree-dump " \\+ 46684427" "optimized" { target int32 } } } */ +/* { dg-final { scan-tree-dump " > 93368854" "optimized" { target int32 } } } */ +/* { dg-final { scan-tree-dump " \\+ 200508087757712517" "optimized" { target lp64 } } } */ +/* { dg-final { scan-tree-dump " > 401016175515425034" "optimized" { target lp64 } } } */ + +__attribute__((noipa)) int +foo (int x) +{ + return __builtin_mul_overflow_p (x, 35, 0); +} + +__attribute__((noipa)) int +bar (long int x) +{ + return __builtin_mul_overflow_p (x, 35L, 0L); +} + +__attribute__((noipa)) int +baz (int x) +{ + return __builtin_mul_overflow_p (42, x, 0); +} + +__attribute__((noipa)) int +qux (long int x) +{ + return __builtin_mul_overflow_p (42, x, 0L); +} + +__attribute__((noipa)) int +corge (int x) +{ + return __builtin_mul_overflow_p (x, -39, 0); +} + +__attribute__((noipa)) int +garply (long int x) +{ + return __builtin_mul_overflow_p (x, -39L, 0L); +} + +__attribute__((noipa)) int +grault (int x) +{ + return __builtin_mul_overflow_p (-46, x, 0); +} + +__attribute__((noipa)) int +waldo (long int x) +{ + return __builtin_mul_overflow_p (-46, x, 0L); +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr30314.c b/gcc/testsuite/gcc.dg/tree-ssa/pr30314.c index 99e4ee2..10b0b85 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr30314.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr30314.c @@ -7,25 +7,25 @@ /* { dg-final { scan-tree-dump " > 102261126" "optimized" { target int32 } } } */ /* { dg-final { scan-tree-dump " > 439208192231179800" "optimized" { target lp64 } } } */ -int +__attribute__((noipa)) int foo (unsigned int x) { return __builtin_mul_overflow_p (x, 35U, 0U); } -int +__attribute__((noipa)) int bar (unsigned long int x) { return __builtin_mul_overflow_p (x, 35UL, 0UL); } -int +__attribute__((noipa)) int baz (unsigned int x) { return __builtin_mul_overflow_p (42, x, 0U); } -int +__attribute__((noipa)) int qux (unsigned long int x) { return __builtin_mul_overflow_p (42, x, 0UL); -- 2.7.4