From: Kyrylo Tkachov <[email protected]>
cond_removal_in_builtin_zero_pattern removes the branch in
r = 0;
if (x != 0)
r = __builtin_popcount (x);
and in the same form with bswap, bitreverse, ffs, parity, clrsb, clz and
ctz, when the call gives the other PHI argument for a zero argument. It
moves the call and an optional conversion of x before the condition.
match.pd has these folds since r14-362 and r14-414, except for
bitreverse, and match_simplify_replacement can now move the conversion
and the call, so the function is not needed. Add bitreverse to the
match.pd fold.
The function did not check for maybe undefined operands, but
match_simplify_replacement does. To keep the x != 0 case, allow a
maybe undefined operand in a moved statement if the condition uses
that operand. A widening conversion to a _BitInt wider than any
integer mode, which bitint lowering turns into a loop, is not moved
with the call any more, so such a branch stays.
The folds now happen in early phiopt when the result is the existing
call. A widening conversion and the call are two moved statements,
which the default of --param=phiopt-max-moved-stmts allows.
This is the second part of the patch by Andrea Pinski at
https://gcc.gnu.org/pipermail/gcc-patches/2026-July/723433.html
Bootstrapped and tested on aarch64-none-linux-gnu and x86_64-linux.
gcc/ChangeLog:
* match.pd (a != 0 ? FUN(a) : 0 -> Fun(a)): Also for BITREVERSE.
* tree-ssa-phiopt.cc (cheap_middle_stmt_lhs): Allow a maybe
undefined operand that the condition uses.
(cond_removal_in_builtin_zero_pattern): Remove.
(pass_phiopt::execute): Do not call it.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/phi-opt-60.c: New test.
* gcc.dg/tree-ssa/phi-opt-61.c: New test.
* gcc.dg/tree-ssa/phi-opt-63.c: New test.
Co-authored-by: Andrea Pinski <[email protected]>
Signed-off-by: Andrea Pinski <[email protected]>
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
gcc/match.pd | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/phi-opt-60.c | 25 ++
gcc/testsuite/gcc.dg/tree-ssa/phi-opt-61.c | 40 +++
gcc/testsuite/gcc.dg/tree-ssa/phi-opt-63.c | 25 ++
gcc/tree-ssa-phiopt.cc | 286 +--------------------
5 files changed, 98 insertions(+), 280 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-60.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-61.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-63.c
diff --git a/gcc/match.pd b/gcc/match.pd
index ebbe24c0aea..6d037daa991 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -11745,7 +11745,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
#endif
/* a != 0 ? FUN(a) : 0 -> Fun(a) for some builtin functions. */
-(for func (POPCOUNT BSWAP FFS PARITY)
+(for func (POPCOUNT BSWAP FFS PARITY BITREVERSE)
(simplify
(cond (ne @0 integer_zerop@1) (func@3 (convert? @0)) integer_zerop@2)
@3))
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-60.c
b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-60.c
new file mode 100644
index 00000000000..1ba8dc53dca
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-60.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-phiopt1-details" } */
+
+/* match.pd folds x != 0 ? FUN (x) : 0 to FUN (x), and phiopt moves the
+ call and the conversion before the condition. */
+
+unsigned
+f1 (unsigned x)
+{
+ unsigned r = 0;
+ if (x)
+ r = __builtin_bitreverse32 (x);
+ return r;
+}
+
+int
+f2 (int x)
+{
+ int r = 0;
+ if (x)
+ r = __builtin_popcountl ((unsigned long) x);
+ return r;
+}
+
+/* { dg-final { scan-tree-dump-times "to straightline code" 2 "phiopt1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-61.c
b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-61.c
new file mode 100644
index 00000000000..7d262307233
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-61.c
@@ -0,0 +1,40 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgimple -fdump-tree-phiopt2-details" } */
+
+/* X_2 may be undefined, but the condition already uses it, so phiopt can
+ move the count before the condition. */
+
+int __GIMPLE (ssa,startwith("phiopt2"))
+f (int c, unsigned int y)
+{
+ unsigned int x;
+ int t;
+ int r;
+
+ __BB(2):
+ if (c_1(D) != 0)
+ goto __BB3;
+ else
+ goto __BB4;
+
+ __BB(3):
+ goto __BB4;
+
+ __BB(4):
+ x_2 = __PHI (__BB2: x_3(D), __BB3: y_4(D));
+ if (x_2 != 0u)
+ goto __BB5;
+ else
+ goto __BB6;
+
+ __BB(5):
+ t_5 = __builtin_popcount (x_2);
+ goto __BB6;
+
+ __BB(6):
+ r_6 = __PHI (__BB4: 0, __BB5: t_5);
+ return r_6;
+}
+
+/* { dg-final { scan-tree-dump-times "to straightline code" 1 "phiopt2" } } */
+/* { dg-final { scan-tree-dump-times "if \\(" 1 "phiopt2" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-63.c
b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-63.c
new file mode 100644
index 00000000000..e0f7facaa7f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-63.c
@@ -0,0 +1,25 @@
+/* { dg-do compile { target bitint575 } } */
+/* { dg-options "-O2 -std=c23 -fdump-tree-phiopt-details" } */
+
+/* The nop conversion to a wide _BitInt type is moved with the count. */
+
+int
+f (signed _BitInt(256) x)
+{
+ int r = 0;
+ if (x != 0)
+ r = __builtin_popcountg ((unsigned _BitInt(256)) x);
+ return r;
+}
+
+int
+g (signed _BitInt(192) x)
+{
+ int r = 77;
+ if (x != 0)
+ r = __builtin_ctzg ((unsigned _BitInt(192)) x);
+ return r;
+}
+
+/* { dg-final { scan-tree-dump-times "to straightline code" 1 "phiopt1" } } */
+/* { dg-final { scan-tree-dump-times "to straightline code" 1 "phiopt2" } } */
diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index 5f24314c3c9..f3ab9fdac96 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -920,8 +920,9 @@ one_feeding_comparison_into_p (basic_block bb,
/* Return the SSA name defined by STMT, a statement in a middle basic block,
if STMT does not access memory, cannot trap, has no side effects and does
- not use a maybe undefined value, so that it can be executed
- unconditionally or removed. Otherwise return NULL_TREE. */
+ not use a maybe undefined value that the condition before the block does
+ not use, so that it can be executed unconditionally or removed.
+ Otherwise return NULL_TREE. */
static tree
cheap_middle_stmt_lhs (gimple *stmt)
@@ -935,8 +936,11 @@ cheap_middle_stmt_lhs (gimple *stmt)
ssa_op_iter it;
tree use;
+ gcond *cond = as_a <gcond *> (*gsi_last_bb (single_pred (gimple_bb (stmt))));
FOR_EACH_SSA_TREE_OPERAND (use, stmt, it, SSA_OP_USE)
- if (ssa_name_maybe_undef_p (use))
+ if (ssa_name_maybe_undef_p (use)
+ && use != gimple_cond_lhs (cond)
+ && use != gimple_cond_rhs (cond))
return NULL_TREE;
/* Allow assignments but allow some builtin/internal calls.
@@ -2928,276 +2932,6 @@ spaceship_replacement (basic_block cond_bb, basic_block
middle_bb,
return true;
}
-/* Optimize x ? __builtin_fun (x) : C, where C is __builtin_fun (0).
- Convert
-
- <bb 2>
- if (b_4(D) != 0)
- goto <bb 3>
- else
- goto <bb 4>
-
- <bb 3>
- _2 = (unsigned long) b_4(D);
- _9 = __builtin_popcountl (_2);
- OR
- _9 = __builtin_popcountl (b_4(D));
-
- <bb 4>
- c_12 = PHI <0(2), _9(3)>
-
- Into
- <bb 2>
- _2 = (unsigned long) b_4(D);
- _9 = __builtin_popcountl (_2);
- OR
- _9 = __builtin_popcountl (b_4(D));
-
- <bb 4>
- c_12 = PHI <_9(2)>
-
- Similarly for __builtin_clz or __builtin_ctz if
- C?Z_DEFINED_VALUE_AT_ZERO is 2, optab is present and
- instead of 0 above it uses the value from that macro. */
-
-static bool
-cond_removal_in_builtin_zero_pattern (basic_block cond_bb,
- basic_block middle_bb,
- edge e1, edge e2, gphi *phi,
- tree arg0, tree arg1)
-{
- gimple_stmt_iterator gsi, gsi_from;
- gimple *call;
- gimple *cast = NULL;
- tree lhs, arg;
-
- /* Check that
- _2 = (unsigned long) b_4(D);
- _9 = __builtin_popcountl (_2);
- OR
- _9 = __builtin_popcountl (b_4(D));
- are the only stmts in the middle_bb. */
-
- gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
- if (gsi_end_p (gsi))
- return false;
- cast = gsi_stmt (gsi);
- gsi_next_nondebug (&gsi);
- if (!gsi_end_p (gsi))
- {
- call = gsi_stmt (gsi);
- gsi_next_nondebug (&gsi);
- if (!gsi_end_p (gsi))
- return false;
- }
- else
- {
- call = cast;
- cast = NULL;
- }
-
- /* Check that we have a popcount/clz/ctz builtin. */
- if (!is_gimple_call (call))
- return false;
-
- lhs = gimple_get_lhs (call);
-
- if (lhs == NULL_TREE)
- return false;
-
- combined_fn cfn = gimple_call_combined_fn (call);
- if (gimple_call_num_args (call) != 1
- && (gimple_call_num_args (call) != 2
- || cfn == CFN_CLZ
- || cfn == CFN_CTZ))
- return false;
-
- arg = gimple_call_arg (call, 0);
-
- internal_fn ifn = IFN_LAST;
- int val = 0;
- bool any_val = false;
- switch (cfn)
- {
- CASE_CFN_BSWAP:
- CASE_CFN_BITREVERSE:
- CASE_CFN_FFS:
- CASE_CFN_PARITY:
- CASE_CFN_POPCOUNT:
- break;
- CASE_CFN_CLZ:
- if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
- {
- tree type = TREE_TYPE (arg);
- if (BITINT_TYPE_P (type))
- {
- if (gimple_call_num_args (call) == 1)
- {
- any_val = true;
- ifn = IFN_CLZ;
- break;
- }
- if (!tree_fits_shwi_p (gimple_call_arg (call, 1)))
- return false;
- HOST_WIDE_INT at_zero = tree_to_shwi (gimple_call_arg (call, 1));
- if ((int) at_zero != at_zero)
- return false;
- ifn = IFN_CLZ;
- val = at_zero;
- break;
- }
- if (direct_internal_fn_supported_p (IFN_CLZ, type, OPTIMIZE_FOR_BOTH)
- && CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
- val) == 2)
- {
- ifn = IFN_CLZ;
- break;
- }
- }
- return false;
- CASE_CFN_CTZ:
- if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
- {
- tree type = TREE_TYPE (arg);
- if (BITINT_TYPE_P (type))
- {
- if (gimple_call_num_args (call) == 1)
- {
- any_val = true;
- ifn = IFN_CTZ;
- break;
- }
- if (!tree_fits_shwi_p (gimple_call_arg (call, 1)))
- return false;
- HOST_WIDE_INT at_zero = tree_to_shwi (gimple_call_arg (call, 1));
- if ((int) at_zero != at_zero)
- return false;
- ifn = IFN_CTZ;
- val = at_zero;
- break;
- }
- if (direct_internal_fn_supported_p (IFN_CTZ, type, OPTIMIZE_FOR_BOTH)
- && CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
- val) == 2)
- {
- ifn = IFN_CTZ;
- break;
- }
- }
- return false;
- case CFN_BUILT_IN_CLRSB:
- val = TYPE_PRECISION (integer_type_node) - 1;
- break;
- case CFN_BUILT_IN_CLRSBL:
- val = TYPE_PRECISION (long_integer_type_node) - 1;
- break;
- case CFN_BUILT_IN_CLRSBLL:
- val = TYPE_PRECISION (long_long_integer_type_node) - 1;
- break;
- default:
- return false;
- }
-
- if (cast)
- {
- /* We have a cast stmt feeding popcount/clz/ctz builtin. */
- /* Check that we have a cast prior to that. */
- if (gimple_code (cast) != GIMPLE_ASSIGN
- || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (cast)))
- return false;
- /* Result of the cast stmt is the argument to the builtin. */
- if (arg != gimple_assign_lhs (cast))
- return false;
- arg = gimple_assign_rhs1 (cast);
- }
-
- gcond *cond = dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
-
- /* Cond_bb has a check for b_4 [!=|==] 0 before calling the popcount/clz/ctz
- builtin. */
- if (!cond
- || (gimple_cond_code (cond) != NE_EXPR
- && gimple_cond_code (cond) != EQ_EXPR)
- || !integer_zerop (gimple_cond_rhs (cond))
- || arg != gimple_cond_lhs (cond))
- return false;
-
- edge true_edge, false_edge;
- /* We need to know which is the true edge and which is the false
- edge so that we know when to invert the condition below. */
- extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
-
- /* Forward the edges over the middle basic block. */
- if (true_edge->dest == middle_bb)
- true_edge = EDGE_SUCC (true_edge->dest, 0);
- if (false_edge->dest == middle_bb)
- false_edge = EDGE_SUCC (false_edge->dest, 0);
-
- /* Canonicalize the args with respect to the edges,
- arg0 is from the true edge and arg1 is from the
- false edge.
- That is `cond ? arg0 : arg1`.*/
- if (true_edge == e1)
- gcc_assert (false_edge == e2);
- else
- {
- gcc_assert (false_edge == e1);
- gcc_assert (true_edge == e2);
- std::swap (arg0, arg1);
- }
-
- /* Canonicalize the args such that we get:
- `arg != 0 ? arg0 : arg1`. So swap arg0/arg1
- around if cond was an equals. */
- if (gimple_cond_code (cond) == EQ_EXPR)
- std::swap (arg0, arg1);
-
- /* Check PHI arguments. */
- if (lhs != arg0
- || TREE_CODE (arg1) != INTEGER_CST)
- return false;
- if (any_val)
- {
- if (!tree_fits_shwi_p (arg1))
- return false;
- HOST_WIDE_INT at_zero = tree_to_shwi (arg1);
- if ((int) at_zero != at_zero)
- return false;
- val = at_zero;
- }
- else if (wi::to_wide (arg1) != val)
- return false;
-
- /* And insert the popcount/clz/ctz builtin and cast stmt before the
- cond_bb. */
- gsi = gsi_last_bb (cond_bb);
- if (cast)
- {
- gsi_from = gsi_for_stmt (cast);
- gsi_move_before (&gsi_from, &gsi);
- reset_flow_sensitive_info (gimple_get_lhs (cast));
- }
- gsi_from = gsi_for_stmt (call);
- if (ifn == IFN_LAST
- || (gimple_call_internal_p (call) && gimple_call_num_args (call) == 2))
- gsi_move_before (&gsi_from, &gsi);
- else
- {
- /* For __builtin_c[lt]z* force .C[LT]Z ifn, because only
- the latter is well defined at zero. */
- call = gimple_build_call_internal (ifn, 2, gimple_call_arg (call, 0),
- build_int_cst (integer_type_node,
val));
- gimple_call_set_lhs (call, lhs);
- gsi_insert_before (&gsi, call, GSI_SAME_STMT);
- gsi_remove (&gsi_from, true);
- }
- reset_flow_sensitive_info (lhs);
-
- /* Now update the PHI and remove unneeded bbs. */
- replace_phi_edge_with_variable (cond_bb, e2, phi, lhs);
- return true;
-}
-
/* Auxiliary functions to determine the set of memory accesses which
can't trap because they are preceded by accesses to the same memory
portion. We do that for MEM_REFs, so we only need to track
@@ -5349,12 +5083,6 @@ pass_phiopt::execute (function *)
else if (comparison_combine (bb, bb1, bb2, e1, e2, phi,
arg0, arg1, diamond_p))
cfgchanged = true;
- else if (!early_p
- && !diamond_p
- && single_pred_p (bb1)
- && cond_removal_in_builtin_zero_pattern (bb, bb1, e1, e2,
- phi, arg0, arg1))
- cfgchanged = true;
else if (single_pred_p (bb1)
&& !diamond_p
&& spaceship_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
--
2.54.0 (Apple Git-157)
