From: Kyrylo Tkachov <[email protected]>
number_of_iterations_cltz_complement handles loops that shift an IV
until it is zero. If the start value T of the IV can be zero and the
target does not define .CLZ at zero, build_cltz_expr builds
T != 0 ? .CLZ (T) : PREC. The final value replacement gimplifies the
count before the select, so .CLZ (T) is also evaluated for a zero T,
where its result is undefined. For sqrtllu in
gcc.c-torture/execute/920501-6.c, sccp on x86_64 emits
_28 = t_10(D) != 0;
_27 = .CLZ (t_10(D));
_22 = (unsigned int) _27;
_29 = 64 - _22;
_23 = (long long unsigned int) _29;
b_30 = _28 ? _23 : 1;
The expansion now implements any value at zero. As Richard Biener
suggested in PR111280 comment 6, build .CLZ (T, PREC) instead of the
select.
The loop in sqrtllu modifies the IV before the exit test. For such
loops the number of iterations was PREC - 1 - .CLZ (T), with another
select for a zero T. The first value that the loop tests is T >> 1
(T << 1 for CTZ), and PREC minus the count of that value is right for
all T. Use it and drop the select:
_27 = t_10(D) >> 1;
_28 = .CLZ (_27, 64);
_39 = 65 - _28;
b_30 = (long long unsigned int) _39;
If the conditions on entry to the loop show that T is not zero, the
count needs no value at zero. simplify_using_initial_conditions removed
the select in that case, so ask it before the count is built. Guarded
loops, which include while loops after header copying, keep their code.
sqrtllu has 17 instead of 19 instructions on aarch64 and 23 instead of
25 on x86_64 with -march=x86-64-v3. Without LZCNT it has 29 instead of
22 on x86_64, because the expansion of .CLZ (_27, 64) tests _27.
Types without a .CLZ or .CTZ internal function use the builtins with a
select, as before.
Bootstrapped and tested on aarch64-none-linux-gnu and x86_64-linux.
gcc/ChangeLog:
PR tree-optimization/111280
* tree-ssa-loop-niter.cc (build_cltz_expr): Pass the precision
as the value at zero of the internal function instead of a
select. Unshare SRC in the select of the builtins.
(number_of_iterations_cltz_complement): Ask for a value at zero
only if SRC can be zero on entry. If the IV is modified before
the test and SRC can be zero, count the zeros of the first value
tested.
gcc/testsuite/ChangeLog:
PR tree-optimization/111280
* gcc.dg/tree-ssa/pr111280.c: New test.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
gcc/testsuite/gcc.dg/tree-ssa/pr111280.c | 63 ++++++++++++++++++++++++
gcc/tree-ssa-loop-niter.cc | 61 ++++++++++++-----------
2 files changed, 95 insertions(+), 29 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr111280.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr111280.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr111280.c
new file mode 100644
index 00000000000..a1f5e821043
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr111280.c
@@ -0,0 +1,63 @@
+/* PR tree-optimization/111280 */
+/* { dg-do run } */
+/* { dg-require-effective-target int32 } */
+/* { dg-require-effective-target clz_ifn } */
+/* { dg-require-effective-target ctz_ifn } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* The first value that the loops test is T shifted by one. It can be
+ zero, so its count needs a value at zero. */
+
+__attribute__((noipa)) int
+clz_loop (unsigned int t)
+{
+ int b = 0;
+ do
+ b++;
+ while ((t >>= 1) != 0);
+ return b;
+}
+
+__attribute__((noipa)) int
+ctz_loop (unsigned int t)
+{
+ int b = 0;
+ do
+ b++;
+ while ((t <<= 1) != 0);
+ return b;
+}
+
+/* The loop is entered only with a nonzero T, so the count needs no value
+ at zero. */
+
+__attribute__((noipa)) int
+clz_guarded (unsigned int t)
+{
+ int b = 0;
+ while (t)
+ {
+ t >>= 1;
+ b++;
+ }
+ return b;
+}
+
+int
+main ()
+{
+ if (clz_loop (0) != 1 || clz_loop (1) != 1 || clz_loop (6) != 3
+ || clz_loop (0x80000000u) != 32)
+ __builtin_abort ();
+ if (ctz_loop (0) != 1 || ctz_loop (0x80000000u) != 1 || ctz_loop (6) != 31
+ || ctz_loop (1) != 32)
+ __builtin_abort ();
+ if (clz_guarded (0) != 0 || clz_guarded (6) != 3
+ || clz_guarded (0x80000000u) != 32)
+ __builtin_abort ();
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times {\.CLZ \(_\d+, 32\)} 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times {\.CTZ \(_\d+, 32\)} 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times {\.CLZ \(t_\d+\(D\)\)} 1 "optimized" } }
*/
diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
index 6c368acb99b..4a1fc779f05 100644
--- a/gcc/tree-ssa-loop-niter.cc
+++ b/gcc/tree-ssa-loop-niter.cc
@@ -2191,10 +2191,9 @@ number_of_iterations_popcount (loop_p loop, edge exit,
/* Return an expression that counts the leading/trailing zeroes of src.
If define_at_zero is true, then the built expression will be defined to
- return the precision of src when src == 0 (using either a conditional
- expression or a suitable internal function).
- Otherwise, we can elide the conditional expression and let src = 0 invoke
- undefined behaviour. */
+ return the precision of src when src == 0 (using the second argument of
+ the internal function or a conditional expression).
+ Otherwise, the result for src == 0 is undefined. */
static tree
build_cltz_expr (tree src, bool leading, bool define_at_zero)
@@ -2227,24 +2226,11 @@ build_cltz_expr (tree src, bool leading, bool
define_at_zero)
tree call;
if (use_ifn)
{
- int val;
- int optab_defined_at_zero
- = (leading
- ? CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (utype), val)
- : CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (utype), val));
- tree arg2 = NULL_TREE;
- if (define_at_zero && optab_defined_at_zero == 2 && val == prec)
- arg2 = build_int_cst (integer_type_node, val);
+ tree arg2 = (define_at_zero
+ ? build_int_cst (integer_type_node, prec) : NULL_TREE);
call = build_call_expr_internal_loc (UNKNOWN_LOCATION, ifn,
integer_type_node, arg2 ? 2 : 1,
src, arg2);
- if (define_at_zero && arg2 == NULL_TREE)
- {
- tree is_zero = fold_build2 (NE_EXPR, boolean_type_node, src,
- build_zero_cst (TREE_TYPE (src)));
- call = fold_build3 (COND_EXPR, integer_type_node, is_zero, call,
- build_int_cst (integer_type_node, prec));
- }
}
else if (fn == NULL_TREE)
return NULL_TREE;
@@ -2287,7 +2273,9 @@ build_cltz_expr (tree src, bool leading, bool
define_at_zero)
build_int_cst (integer_type_node, i_prec - prec));
if (define_at_zero)
{
- tree is_zero = fold_build2 (NE_EXPR, boolean_type_node, src,
+ /* SRC can be a shift, so do not share it with the call. */
+ tree is_zero = fold_build2 (NE_EXPR, boolean_type_node,
+ unshare_expr (src),
build_zero_cst (TREE_TYPE (src)));
call = fold_build3 (COND_EXPR, integer_type_node, is_zero, call,
build_int_cst (integer_type_node, prec));
@@ -2679,8 +2667,26 @@ number_of_iterations_cltz_complement (loop_p loop, edge
exit,
int src_precision = TYPE_PRECISION (TREE_TYPE (src));
- /* Get the corresponding c[lt]z builtin. */
- tree expr = build_cltz_expr (src, !left_shift, true);
+ tree src_zero = fold_build2 (EQ_EXPR, boolean_type_node, src,
+ build_zero_cst (TREE_TYPE (src)));
+ bool src_nonzero
+ = integer_zerop (simplify_using_initial_conditions (loop, src_zero));
+
+ /* If the IV is modified before the test, the first value tested is SRC
+ shifted by one. If SRC can be zero, count the zeros of that value
+ instead of subtracting one from the count of SRC. Then the result is
+ also right for a zero SRC. */
+ tree count_src = src;
+ if (modify_before_test && !src_nonzero)
+ {
+ tree utype = unsigned_type_for (TREE_TYPE (src));
+ count_src = fold_build2 (left_shift ? LSHIFT_EXPR : RSHIFT_EXPR, utype,
+ fold_convert (utype, src), integer_one_node);
+ }
+
+ /* Get the corresponding c[lt]z builtin. It needs a value at zero only
+ if its argument can be zero. */
+ tree expr = build_cltz_expr (count_src, !left_shift, !src_nonzero);
if (!expr)
return false;
@@ -2691,21 +2697,18 @@ number_of_iterations_cltz_complement (loop_p loop, edge
exit,
max = src_precision;
- tree may_be_zero = boolean_false_node;
-
if (modify_before_test)
{
- expr = fold_build2 (MINUS_EXPR, integer_type_node, expr,
- integer_one_node);
+ if (src_nonzero)
+ expr = fold_build2 (MINUS_EXPR, integer_type_node, expr,
+ integer_one_node);
max = max - 1;
- may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node, src,
- build_zero_cst (TREE_TYPE (src)));
}
expr = fold_convert (unsigned_type_node, expr);
niter->assumptions = boolean_true_node;
- niter->may_be_zero = simplify_using_initial_conditions (loop, may_be_zero);
+ niter->may_be_zero = boolean_false_node;
niter->niter = simplify_using_initial_conditions (loop, expr);
if (TREE_CODE (niter->niter) == INTEGER_CST)
--
2.54.0 (Apple Git-157)
