There are certain patterns that are not recognized by the method optimize_spaceship. For example, a == b ? 0 : (a > b) : 1 : -1; is rightly recognized as spaceship operator. But a <= b ? -(a < b) : 1 or a >= b ? (a > b) : -1 is not being currently recognized.
This patch recognizes such patterns and chooses to emit the spaceship optab if target supports it, which improves code-generation for such targets. 2026-06-16 Avinash Jayakar <[email protected]> gcc/ChangeLog: PR tree-optimization/59429 * match.pd: New match patterns to recognize spaceship variants. * tree-ssa-math-opts.cc (gimple_spaceship): Match function declaration. (match_spaceship): New function to recognize spaceship given phi node. (math_opts_dom_walker::after_dom_children): Add match_spaceship check. gcc/testsuite/ChangeLog: PR tree-optimization/59429 * lib/target-supports.exp (check_effective_target_spaceship): Add new proc for spaceship optab. x86, aarch64 and s390 included. * gcc.dg/spaceship_int_variants.c: New test. * gcc.dg/spaceship_uint_variants.c: New test. * gcc.dg/spaceship_mixed_variants.c: New test. --- gcc/match.pd | 18 + gcc/testsuite/gcc.dg/spaceship_int_variants.c | 101 ++++++ .../gcc.dg/spaceship_mixed_variants.c | 324 ++++++++++++++++++ .../gcc.dg/spaceship_uint_variants.c | 101 ++++++ gcc/testsuite/lib/target-supports.exp | 10 + gcc/tree-ssa-math-opts.cc | 109 +++++- 6 files changed, 662 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/spaceship_int_variants.c create mode 100644 gcc/testsuite/gcc.dg/spaceship_mixed_variants.c create mode 100644 gcc/testsuite/gcc.dg/spaceship_uint_variants.c diff --git a/gcc/match.pd b/gcc/match.pd index 21b0945943b..475939a0b63 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -236,6 +236,24 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) && !TYPE_UNSIGNED (TREE_TYPE (@0))) (abs @0))) +/* Following match patterns are used by the match_spaceship function to detect + all possible spaceship combinations. */ +#if GIMPLE +(if (INTEGRAL_TYPE_P (type)) + (for op (lt ne) + (match (spaceship @0 @1) + (cond^ (le @0 @1) (negate (convert? (op @0 @1))) integer_onep))) + (for op (lt ne) + (match (spaceship @0 @1) + (cond^ (le @1 @0) (convert? (op @1 @0)) integer_minus_onep))) + (for op (gt ne) + (match (spaceship @0 @1) + (cond^ (ge @0 @1) (convert? (op @0 @1)) integer_minus_onep)))) + (for op (gt ne) + (match (spaceship @0 @1) + (cond^ (ge @1 @0) (negate (convert? (op @1 @0))) integer_onep))) +#endif + /* Simplifications of operations with one constant operand and simplifications to constants or single values. */ diff --git a/gcc/testsuite/gcc.dg/spaceship_int_variants.c b/gcc/testsuite/gcc.dg/spaceship_int_variants.c new file mode 100644 index 00000000000..41cd78354d7 --- /dev/null +++ b/gcc/testsuite/gcc.dg/spaceship_int_variants.c @@ -0,0 +1,101 @@ +/* { dg-do compile } */ +/* { dg-require-effective-target spaceship } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-final { scan-tree-dump-times {\.SPACESHIP \([^,]+, [^,]+, -1\)} 24 optimized } } */ + +int sp1 (int a, int b) +{ + return a < b ? -1 : a > b ? 1 : 0; +} +int sp1_1 (int a, int b) +{ + return a < b ? -1 : a == b ? 0 : 1; +} +int sp1_2 (int a, int b) +{ + return a < b ? -1 : a != b ? 1 : 0; +} +int sp1_3 (int a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} +int sp2 (int a, int b) +{ + return a == b ? 0 : a > b ? 1 : -1; +} +int sp2_1 (int a, int b) +{ + return a == b ? 0 : a < b ? -1 : 1; +} +int sp2_2 (int a, int b) +{ + return a == b ? 0 : a >= b ? 1 : -1; +} +int sp2_3 (int a, int b) +{ + return a == b ? 0 : a <= b ? -1 : 1; +} +int sp3 (int a, int b) +{ + return a != b ? (a > b ? 1 : -1) : 0; +} +int sp3_1 (int a, int b) +{ + return a != b ? (a < b ? -1 : 1) : 0; +} +int sp3_2 (int a, int b) +{ + return a != b ? (a >= b ? 1 : -1) : 0; +} +int sp3_3 (int a, int b) +{ + return a != b ? (a <= b ? -1 : 1) : 0; +} +int sp4 (int a, int b) +{ + return a > b ? 1 : a == b ? 0 : -1; +} +int sp4_1 (int a, int b) +{ + return a > b ? 1 : a < b ? -1 : 0; +} +int sp4_2 (int a, int b) +{ + return a > b ? 1 : a != b ? -1 : 0; +} +int sp4_3 (int a, int b) +{ + return a > b ? 1 : a >= b ? 0 : -1; +} +int sp5 (int a, int b) +{ + return a <= b ? (a == b ? 0 : -1) : 1; +} +int sp5_1 (int a, int b) +{ + return a <= b ? (a >= b ? 0 : -1) : 1; +} +int sp5_2 (int a, int b) +{ + return a <= b ? (a != b ? -1 : 0) : 1; +} +int sp5_3 (int a, int b) +{ + return a <= b ? (a < b ? -1 : 0) : 1; +} +int sp6 (int a, int b) +{ + return a >= b ? (a == b ? 0 : 1) : -1; +} +int sp6_1 (int a, int b) +{ + return a >= b ? (a != b ? 1 : 0) : -1; +} +int sp6_2 (int a, int b) +{ + return a >= b ? (a <= b ? 0 : 1) : -1; +} +int sp6_3 (int a, int b) +{ + return a >= b ? (a > b ? 1 : 0) : -1; +} diff --git a/gcc/testsuite/gcc.dg/spaceship_mixed_variants.c b/gcc/testsuite/gcc.dg/spaceship_mixed_variants.c new file mode 100644 index 00000000000..a6d7c96363a --- /dev/null +++ b/gcc/testsuite/gcc.dg/spaceship_mixed_variants.c @@ -0,0 +1,324 @@ +/* { dg-do compile } */ +/* { dg-require-effective-target spaceship } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-final { scan-tree-dump-times {\.SPACESHIP \([^,]+, [^,]+, -1\)} 64 optimized } } */ + +signed char sp1_1 (signed char a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +signed char sp1_2 (signed char a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +signed char sp1_3 (signed char a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +signed char sp1_4 (signed char a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +signed char sp1_5 (short a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +signed char sp1_6 (short a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +signed char sp1_7 (short a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +signed char sp1_8 (short a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +signed char sp1_9 (int a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +signed char sp1_10 (int a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +signed char sp1_11 (int a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +signed char sp1_12 (int a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +signed char sp1_13 (long long a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +signed char sp1_14 (long long a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +signed char sp1_15 (long long a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +signed char sp1_16 (long long a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_1 (signed char a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_2 (signed char a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_3 (signed char a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_4 (signed char a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_5 (short a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_6 (short a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_7 (short a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_8 (short a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_9 (int a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_10 (int a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_11 (int a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_12 (int a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_13 (long long a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_14 (long long a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_15 (long long a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +short sp2_16 (long long a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_1 (signed char a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_2 (signed char a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_3 (signed char a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_4 (signed char a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_5 (short a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_6 (short a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_7 (short a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_8 (short a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_9 (int a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_10 (int a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_11 (int a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_12 (int a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_13 (long long a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_14 (long long a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_15 (long long a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +int sp3_16 (long long a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_1 (signed char a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_2 (signed char a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_3 (signed char a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_4 (signed char a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_5 (short a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_6 (short a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_7 (short a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_8 (short a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_9 (int a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_10 (int a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_11 (int a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_12 (int a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_13 (long long a, signed char b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_14 (long long a, short b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_15 (long long a, int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} + +long long sp4_16 (long long a, long long b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} diff --git a/gcc/testsuite/gcc.dg/spaceship_uint_variants.c b/gcc/testsuite/gcc.dg/spaceship_uint_variants.c new file mode 100644 index 00000000000..360b17c2557 --- /dev/null +++ b/gcc/testsuite/gcc.dg/spaceship_uint_variants.c @@ -0,0 +1,101 @@ +/* { dg-do compile } */ +/* { dg-require-effective-target spaceship } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-final { scan-tree-dump-times {\.SPACESHIP \([^,]+, [^,]+, 1\)} 24 optimized } } */ + +int sp1 (unsigned int a, unsigned int b) +{ + return a < b ? -1 : a > b ? 1 : 0; +} +int sp1_1 (unsigned int a, unsigned int b) +{ + return a < b ? -1 : a == b ? 0 : 1; +} +int sp1_2 (unsigned int a, unsigned int b) +{ + return a < b ? -1 : a != b ? 1 : 0; +} +int sp1_3 (unsigned int a, unsigned int b) +{ + return a < b ? -1 : a <= b ? 0 : 1; +} +int sp2 (unsigned int a, unsigned int b) +{ + return a == b ? 0 : a > b ? 1 : -1; +} +int sp2_1 (unsigned int a, unsigned int b) +{ + return a == b ? 0 : a < b ? -1 : 1; +} +int sp2_2 (unsigned int a, unsigned int b) +{ + return a == b ? 0 : a >= b ? 1 : -1; +} +int sp2_3 (unsigned int a, unsigned int b) +{ + return a == b ? 0 : a <= b ? -1 : 1; +} +int sp3 (unsigned int a, unsigned int b) +{ + return a != b ? (a > b ? 1 : -1) : 0; +} +int sp3_1 (unsigned int a, unsigned int b) +{ + return a != b ? (a < b ? -1 : 1) : 0; +} +int sp3_2 (unsigned int a, unsigned int b) +{ + return a != b ? (a >= b ? 1 : -1) : 0; +} +int sp3_3 (unsigned int a, unsigned int b) +{ + return a != b ? (a <= b ? -1 : 1) : 0; +} +int sp4 (unsigned int a, unsigned int b) +{ + return a > b ? 1 : a == b ? 0 : -1; +} +int sp4_1 (unsigned int a, unsigned int b) +{ + return a > b ? 1 : a < b ? -1 : 0; +} +int sp4_2 (unsigned int a, unsigned int b) +{ + return a > b ? 1 : a != b ? -1 : 0; +} +int sp4_3 (unsigned int a, unsigned int b) +{ + return a > b ? 1 : a >= b ? 0 : -1; +} +int sp5 (unsigned int a, unsigned int b) +{ + return a <= b ? (a == b ? 0 : -1) : 1; +} +int sp5_1 (unsigned int a, unsigned int b) +{ + return a <= b ? (a >= b ? 0 : -1) : 1; +} +int sp5_2 (unsigned int a, unsigned int b) +{ + return a <= b ? (a != b ? -1 : 0) : 1; +} +int sp5_3 (unsigned int a, unsigned int b) +{ + return a <= b ? (a < b ? -1 : 0) : 1; +} +int sp6 (unsigned int a, unsigned int b) +{ + return a >= b ? (a == b ? 0 : 1) : -1; +} +int sp6_1 (unsigned int a, unsigned int b) +{ + return a >= b ? (a != b ? 1 : 0) : -1; +} +int sp6_2 (unsigned int a, unsigned int b) +{ + return a >= b ? (a <= b ? 0 : 1) : -1; +} +int sp6_3 (unsigned int a, unsigned int b) +{ + return a >= b ? (a > b ? 1 : 0) : -1; +} diff --git a/gcc/testsuite/lib/target-supports.exp b/gcc/testsuite/lib/target-supports.exp index 0298509ae9c..de91038d882 100644 --- a/gcc/testsuite/lib/target-supports.exp +++ b/gcc/testsuite/lib/target-supports.exp @@ -10409,6 +10409,16 @@ proc check_effective_target_popcount { } { } "" ] } + +# Return 1 if target supports spaceship optab + +proc check_effective_target_spaceship { } { + return [expr { [check_effective_target_x86] + || [istarget aarch64*-*-*] + || [check_effective_target_s390_mvx] }] +} + + # Return 1 if the target supports clz on int. proc check_effective_target_clz { } { diff --git a/gcc/tree-ssa-math-opts.cc b/gcc/tree-ssa-math-opts.cc index 2f4ee8ac26f..f0ede668d95 100644 --- a/gcc/tree-ssa-math-opts.cc +++ b/gcc/tree-ssa-math-opts.cc @@ -115,6 +115,7 @@ along with GCC; see the file COPYING3. If not see #include "domwalk.h" #include "tree-ssa-math-opts.h" #include "dbgcnt.h" +#include "langhooks.h" #include "cfghooks.h" /* This structure represents one basic block that either computes a @@ -4124,6 +4125,7 @@ extern bool gimple_unsigned_integer_sat_add (tree, tree*, tree (*)(tree)); extern bool gimple_unsigned_integer_sat_sub (tree, tree*, tree (*)(tree)); extern bool gimple_unsigned_integer_sat_trunc (tree, tree*, tree (*)(tree)); extern bool gimple_unsigned_integer_sat_mul (tree, tree*, tree (*)(tree)); +extern bool gimple_spaceship (tree, tree*, tree (*)(tree)); extern bool gimple_signed_integer_sat_add (tree, tree*, tree (*)(tree)); extern bool gimple_signed_integer_sat_sub (tree, tree*, tree (*)(tree)); @@ -4333,6 +4335,110 @@ match_saturation_mul (gimple_stmt_iterator *gsi, gphi *phi) ops[1]); } +/* Try to match variants of spaceship operation: + <bb 2> + if (a_3(D) >= b_4(D)) -- CMP_1 + goto <bb 3>; + else + goto <bb 4>; + + <bb 3> + _1 = a_3(D) > b_4(D); -- CMP_2 + _5 = (int) _1; + + <bb 4> + # _2 = PHI <-1(2), _5(3)> + => + _2 = .SPACESHIP (a_3(D), b_4(D), -1); + + All possible canonical variants of the comparison operator in CMP_1 and + CMP_2 has been included in gimple_spaceship function. */ +static bool +match_spaceship (gimple_stmt_iterator *gsi, gphi *phi) +{ + if (gimple_phi_num_args (phi) != 2) + return false; + tree ops[2]; + tree phi_result = gimple_phi_result (phi); + + if (!gimple_spaceship (phi_result, ops, NULL)) + return false; + + /* Allow different modes as long as both are integral types. */ + if (!INTEGRAL_TYPE_P (TREE_TYPE (phi_result)) + || !INTEGRAL_TYPE_P (TREE_TYPE (ops[0]))) + return false; + + tree ops_type = TREE_TYPE (ops[0]); + machine_mode ops_mode = TYPE_MODE (ops_type); + machine_mode promoted_mode = ops_mode; + tree promoted_type = ops_type; + bool is_unsigned = TYPE_UNSIGNED (ops_type); + + /* Check if spaceship optab is available for the operand mode. + If not, try promoting to a wider mode that is supported. */ + if (optab_handler (spaceship_optab, ops_mode) == CODE_FOR_nothing) + { + /* Try promoting to wider modes (e.g., QI/HI -> SI -> DI). */ + machine_mode wider_mode; + FOR_EACH_WIDER_MODE_FROM (wider_mode, ops_mode) + { + if (optab_handler (spaceship_optab, wider_mode) + != CODE_FOR_nothing) + { + /* Check if we can get a type for this mode with matching + signedness. */ + promoted_type = lang_hooks.types.type_for_mode (wider_mode, + is_unsigned); + if (promoted_type != NULL_TREE && INTEGRAL_TYPE_P (promoted_type)) + { + promoted_mode = wider_mode; + break; + } + } + } + + // If no suitable promoted mode found, give up. + if (promoted_mode == ops_mode) + return false; + } + + /* If promotion is needed, insert conversion statements. + We must use GIMPLE assignments rather than fold_convert because + gimple_call arguments must be valid GIMPLE values (SSA names or + constants), not tree expressions. */ + ops[0] = gimple_convert (gsi, true, GSI_SAME_STMT, UNKNOWN_LOCATION, + promoted_type, ops[0]); + ops[1] = gimple_convert (gsi, true, GSI_SAME_STMT, UNKNOWN_LOCATION, + promoted_type, ops[1]); + + tree spaceship_arg_3 = is_unsigned ? build_one_cst (integer_type_node) + : build_minus_one_cst (integer_type_node); + + gcall *call = gimple_build_call_internal (IFN_SPACESHIP, 3, ops[0], ops[1], + spaceship_arg_3); + + /* SPACESHIP optab always returns signed int (SI mode). + Cast to phi_result's type if needed. */ + tree call_result_type = integer_type_node; + if (!types_compatible_p (TREE_TYPE (phi_result), call_result_type)) + { + tree call_result = make_ssa_name (call_result_type); + gimple_call_set_lhs (call, call_result); + gsi_insert_before (gsi, call, GSI_SAME_STMT); + gassign *cast_stmt = gimple_build_assign (phi_result, NOP_EXPR, + call_result); + gsi_insert_before (gsi, cast_stmt, GSI_SAME_STMT); + } + else + { + gimple_call_set_lhs (call, phi_result); + gsi_insert_before (gsi, call, GSI_SAME_STMT); + } + return true; +} + + /* * Try to match saturation unsigned sub. * <bb 2> [local count: 1073741824]: @@ -6515,7 +6621,8 @@ math_opts_dom_walker::after_dom_children (basic_block bb) if (match_saturation_add (&gsi, phi) || match_saturation_sub (&gsi, phi) || match_saturation_trunc (&gsi, phi) - || match_saturation_mul (&gsi, phi)) + || match_saturation_mul (&gsi, phi) + || match_spaceship (&gsi, phi)) remove_phi_node (&psi, /* release_lhs_p */ false); } -- 2.54.0
