https://gcc.gnu.org/g:63a8128218cc421b4294f9b8b139197a985ce375
commit r16-1199-g63a8128218cc421b4294f9b8b139197a985ce375
Author: Richard Biener <rguent...@suse.de>
Date: Wed May 28 14:13:00 2025 +0200
Refactor CTZ detection in forwprop
The following refactors the CTZ detection code to be more easily
extensible to also handle CLZ.
* tree-ssa-forwprop.cc (optimize_count_trailing_zeroes):
Inline into ...
(simplify_count_trailing_zeroes): ... this function.
Split out ...
(check_ctz_table): ... a wrapper for CONSTRUCTOR vs. STRING_CST
handling.
Diff:
---
gcc/tree-ssa-forwprop.cc | 161 ++++++++++++++++++++++-------------------------
1 file changed, 74 insertions(+), 87 deletions(-)
diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
index 27197bbc0769..4ef75ba98bd1 100644
--- a/gcc/tree-ssa-forwprop.cc
+++ b/gcc/tree-ssa-forwprop.cc
@@ -2592,6 +2592,22 @@ check_ctz_string (tree string, unsigned HOST_WIDE_INT
mulc,
return matched == bits;
}
+/* Check whether CTOR contains a valid ctz table. */
+static bool
+check_ctz_table (tree ctor, tree type, unsigned HOST_WIDE_INT mulc,
+ HOST_WIDE_INT &zero_val, unsigned shift, unsigned bits)
+{
+ if (TREE_CODE (ctor) == CONSTRUCTOR)
+ return check_ctz_array (ctor, mulc, zero_val, shift, bits);
+ else if (TREE_CODE (ctor) == STRING_CST
+ && TYPE_PRECISION (type) == CHAR_TYPE_SIZE)
+ return check_ctz_string (ctor, mulc, zero_val, shift, bits);
+ return false;
+}
+
+/* Match.pd function to match the ctz expression. */
+extern bool gimple_ctz_table_index (tree, tree *, tree (*)(tree));
+
/* Recognize count trailing zeroes idiom.
The canonical form is array[((x & -x) * C) >> SHIFT] where C is a magic
constant which when multiplied by a power of 2 creates a unique value
@@ -2599,17 +2615,23 @@ check_ctz_string (tree string, unsigned HOST_WIDE_INT
mulc,
to the number of trailing zeroes. Array[0] is returned so the caller can
emit an appropriate sequence depending on whether ctz (0) is defined on
the target. */
+
static bool
-optimize_count_trailing_zeroes (tree array_ref, tree x, tree mulc,
- tree tshift, HOST_WIDE_INT &zero_val)
+simplify_count_trailing_zeroes (gimple_stmt_iterator *gsi)
{
- tree type = TREE_TYPE (array_ref);
- tree array = TREE_OPERAND (array_ref, 0);
+ gimple *stmt = gsi_stmt (*gsi);
+ tree array_ref = gimple_assign_rhs1 (stmt);
+ tree res_ops[3];
+
+ gcc_checking_assert (TREE_CODE (array_ref) == ARRAY_REF);
- gcc_assert (TREE_CODE (mulc) == INTEGER_CST);
- gcc_assert (TREE_CODE (tshift) == INTEGER_CST);
+ if (!gimple_ctz_table_index (TREE_OPERAND (array_ref, 1), &res_ops[0], NULL))
+ return false;
- tree input_type = TREE_TYPE (x);
+ HOST_WIDE_INT zero_val;
+ tree type = TREE_TYPE (array_ref);
+ tree array = TREE_OPERAND (array_ref, 0);
+ tree input_type = TREE_TYPE (res_ops[0]);
unsigned input_bits = tree_to_shwi (TYPE_SIZE (input_type));
/* Check the array element type is not wider than 32 bits and the input is
@@ -2627,102 +2649,67 @@ optimize_count_trailing_zeroes (tree array_ref, tree
x, tree mulc,
if (!low || !integer_zerop (low))
return false;
- unsigned shiftval = tree_to_shwi (tshift);
-
/* Check the shift extracts the top 5..7 bits. */
+ unsigned shiftval = tree_to_shwi (res_ops[2]);
if (shiftval < input_bits - 7 || shiftval > input_bits - 5)
return false;
tree ctor = ctor_for_folding (array);
if (!ctor)
return false;
+ unsigned HOST_WIDE_INT val = tree_to_uhwi (res_ops[1]);
+ if (!check_ctz_table (ctor, type, val, zero_val, shiftval, input_bits))
+ return false;
- unsigned HOST_WIDE_INT val = tree_to_uhwi (mulc);
-
- if (TREE_CODE (ctor) == CONSTRUCTOR)
- return check_ctz_array (ctor, val, zero_val, shiftval, input_bits);
-
- if (TREE_CODE (ctor) == STRING_CST
- && TYPE_PRECISION (type) == CHAR_TYPE_SIZE)
- return check_ctz_string (ctor, val, zero_val, shiftval, input_bits);
-
- return false;
-}
-
-/* Match.pd function to match the ctz expression. */
-extern bool gimple_ctz_table_index (tree, tree *, tree (*)(tree));
+ HOST_WIDE_INT ctz_val = 0;
+ bool zero_ok = CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (input_type),
+ ctz_val) == 2;
+ int nargs = 2;
-static bool
-simplify_count_trailing_zeroes (gimple_stmt_iterator *gsi)
-{
- gimple *stmt = gsi_stmt (*gsi);
- tree array_ref = gimple_assign_rhs1 (stmt);
- tree res_ops[3];
- HOST_WIDE_INT zero_val;
-
- gcc_checking_assert (TREE_CODE (array_ref) == ARRAY_REF);
+ /* If the input value can't be zero, don't special case ctz (0). */
+ if (tree_expr_nonzero_p (res_ops[0]))
+ {
+ zero_ok = true;
+ zero_val = 0;
+ ctz_val = 0;
+ nargs = 1;
+ }
- if (!gimple_ctz_table_index (TREE_OPERAND (array_ref, 1), &res_ops[0], NULL))
+ /* Skip if there is no value defined at zero, or if we can't easily
+ return the correct value for zero. */
+ if (!zero_ok)
+ return false;
+ if (zero_val != ctz_val && !(zero_val == 0 && ctz_val == input_bits))
return false;
- if (optimize_count_trailing_zeroes (array_ref, res_ops[0],
- res_ops[1], res_ops[2], zero_val))
+ gimple_seq seq = NULL;
+ gimple *g;
+ gcall *call = gimple_build_call_internal (IFN_CTZ, nargs, res_ops[0],
+ nargs == 1 ? NULL_TREE
+ : build_int_cst (integer_type_node,
+ ctz_val));
+ gimple_set_location (call, gimple_location (stmt));
+ gimple_set_lhs (call, make_ssa_name (integer_type_node));
+ gimple_seq_add_stmt (&seq, call);
+
+ tree prev_lhs = gimple_call_lhs (call);
+
+ /* Emit ctz (x) & 31 if ctz (0) is 32 but we need to return 0. */
+ if (zero_val == 0 && ctz_val == input_bits)
{
- tree type = TREE_TYPE (res_ops[0]);
- HOST_WIDE_INT ctz_val = 0;
- HOST_WIDE_INT type_size = tree_to_shwi (TYPE_SIZE (type));
- bool zero_ok
- = CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type), ctz_val) == 2;
- int nargs = 2;
-
- /* If the input value can't be zero, don't special case ctz (0). */
- if (tree_expr_nonzero_p (res_ops[0]))
- {
- zero_ok = true;
- zero_val = 0;
- ctz_val = 0;
- nargs = 1;
- }
-
- /* Skip if there is no value defined at zero, or if we can't easily
- return the correct value for zero. */
- if (!zero_ok)
- return false;
- if (zero_val != ctz_val && !(zero_val == 0 && ctz_val == type_size))
- return false;
-
- gimple_seq seq = NULL;
- gimple *g;
- gcall *call
- = gimple_build_call_internal (IFN_CTZ, nargs, res_ops[0],
- nargs == 1 ? NULL_TREE
- : build_int_cst (integer_type_node,
- ctz_val));
- gimple_set_location (call, gimple_location (stmt));
- gimple_set_lhs (call, make_ssa_name (integer_type_node));
- gimple_seq_add_stmt (&seq, call);
-
- tree prev_lhs = gimple_call_lhs (call);
-
- /* Emit ctz (x) & 31 if ctz (0) is 32 but we need to return 0. */
- if (zero_val == 0 && ctz_val == type_size)
- {
- g = gimple_build_assign (make_ssa_name (integer_type_node),
- BIT_AND_EXPR, prev_lhs,
- build_int_cst (integer_type_node,
- type_size - 1));
- gimple_set_location (g, gimple_location (stmt));
- gimple_seq_add_stmt (&seq, g);
- prev_lhs = gimple_assign_lhs (g);
- }
-
- g = gimple_build_assign (gimple_assign_lhs (stmt), NOP_EXPR, prev_lhs);
+ g = gimple_build_assign (make_ssa_name (integer_type_node),
+ BIT_AND_EXPR, prev_lhs,
+ build_int_cst (integer_type_node,
+ input_bits - 1));
+ gimple_set_location (g, gimple_location (stmt));
gimple_seq_add_stmt (&seq, g);
- gsi_replace_with_seq (gsi, seq, true);
- return true;
+ prev_lhs = gimple_assign_lhs (g);
}
- return false;
+ g = gimple_build_assign (gimple_assign_lhs (stmt), NOP_EXPR, prev_lhs);
+ gimple_seq_add_stmt (&seq, g);
+ gsi_replace_with_seq (gsi, seq, true);
+ return true;
}
