[5/8,v2] middle-end: Add cltz_complement idiom recognition

  On Thu, Nov 24, 2022 at 11:41:31AM +0100, Richard Biener wrote:
> Note we do have CTZ and CLZ
> optabs and internal functions - in case there's a HImode CLZ this
> could be elided.  More general you can avoid using the __builtin_
> functions with their fixed types in favor of using IFN_C[TL]Z which
> are type agnostic (but require optab support - you should be able
> to check this via direct_internal_fn_supported_p).

IFN support added. I've also renamed the defined_at_zero parameter to
define_at_zero, since this is a request for the expression to define it,
rather than a guarantee that it is already defined.

New patch below, bootstrapped and regression tested on
aarch64-unknown-linux-gnu and x86_64-pc-linux-gnu - ok to merge?

---

This recognises patterns of the form:
while (n) { n >>= 1 }

This patch results in improved (but still suboptimal) codegen:

foo (unsigned int b) {
    int c = 0;

    while (b) {
        b >>= 1;
        c++;
    }

    return c;
}

foo:
.LFB11:
        .cfi_startproc
        cbz     w0, .L3
        clz     w1, w0
        tst     x0, 1
        mov     w0, 32
        sub     w0, w0, w1
        csel    w0, w0, wzr, ne
        ret

The conditional is unnecessary. phiopt could recognise a redundant csel
(using cond_removal_in_builtin_zero_pattern) when one of the inputs is a
clz call, but it cannot recognise the redunancy when the input is (e.g.)
(32 - clz).

I could perhaps extend this function to recognise this pattern in a later
patch, if this is a good place to recognise more patterns.

gcc/ChangeLog:

	PR tree-optimization/94793
	* tree-scalar-evolution.cc (expression_expensive_p): Add checks
	for c[lt]z optabs.
	* tree-ssa-loop-niter.cc (build_cltz_expr): New.
	(number_of_iterations_cltz_complement): New.
	(number_of_iterations_bitcount): Add call to the above.

gcc/testsuite/ChangeLog:

	* lib/target-supports.exp (check_effective_target_clz)
	(check_effective_target_clzl, check_effective_target_clzll)
	(check_effective_target_ctz, check_effective_target_clzl)
	(check_effective_target_ctzll): New.
	* gcc.dg/tree-ssa/cltz-complement-max.c: New test.
	* gcc.dg/tree-ssa/clz-complement-char.c: New test.
	* gcc.dg/tree-ssa/clz-complement-int.c: New test.
	* gcc.dg/tree-ssa/clz-complement-long-long.c: New test.
	* gcc.dg/tree-ssa/clz-complement-long.c: New test.
	* gcc.dg/tree-ssa/ctz-complement-char.c: New test.
	* gcc.dg/tree-ssa/ctz-complement-int.c: New test.
	* gcc.dg/tree-ssa/ctz-complement-long-long.c: New test.
	* gcc.dg/tree-ssa/ctz-complement-long.c: New test.

---
  

On Thu, Dec 22, 2022 at 6:42 PM Andrew Carlotti <andrew.carlotti@arm.com> wrote:
>
> On Thu, Nov 24, 2022 at 11:41:31AM +0100, Richard Biener wrote:
> > Note we do have CTZ and CLZ
> > optabs and internal functions - in case there's a HImode CLZ this
> > could be elided.  More general you can avoid using the __builtin_
> > functions with their fixed types in favor of using IFN_C[TL]Z which
> > are type agnostic (but require optab support - you should be able
> > to check this via direct_internal_fn_supported_p).
>
> IFN support added. I've also renamed the defined_at_zero parameter to
> define_at_zero, since this is a request for the expression to define it,
> rather than a guarantee that it is already defined.
>
> New patch below, bootstrapped and regression tested on
> aarch64-unknown-linux-gnu and x86_64-pc-linux-gnu - ok to merge?

OK, and sorry for the delay.

Richard.

> ---
>
> This recognises patterns of the form:
> while (n) { n >>= 1 }
>
> This patch results in improved (but still suboptimal) codegen:
>
> foo (unsigned int b) {
>     int c = 0;
>
>     while (b) {
>         b >>= 1;
>         c++;
>     }
>
>     return c;
> }
>
> foo:
> .LFB11:
>         .cfi_startproc
>         cbz     w0, .L3
>         clz     w1, w0
>         tst     x0, 1
>         mov     w0, 32
>         sub     w0, w0, w1
>         csel    w0, w0, wzr, ne
>         ret
>
> The conditional is unnecessary. phiopt could recognise a redundant csel
> (using cond_removal_in_builtin_zero_pattern) when one of the inputs is a
> clz call, but it cannot recognise the redunancy when the input is (e.g.)
> (32 - clz).
>
> I could perhaps extend this function to recognise this pattern in a later
> patch, if this is a good place to recognise more patterns.
>
> gcc/ChangeLog:
>
>         PR tree-optimization/94793
>         * tree-scalar-evolution.cc (expression_expensive_p): Add checks
>         for c[lt]z optabs.
>         * tree-ssa-loop-niter.cc (build_cltz_expr): New.
>         (number_of_iterations_cltz_complement): New.
>         (number_of_iterations_bitcount): Add call to the above.
>
> gcc/testsuite/ChangeLog:
>
>         * lib/target-supports.exp (check_effective_target_clz)
>         (check_effective_target_clzl, check_effective_target_clzll)
>         (check_effective_target_ctz, check_effective_target_clzl)
>         (check_effective_target_ctzll): New.
>         * gcc.dg/tree-ssa/cltz-complement-max.c: New test.
>         * gcc.dg/tree-ssa/clz-complement-char.c: New test.
>         * gcc.dg/tree-ssa/clz-complement-int.c: New test.
>         * gcc.dg/tree-ssa/clz-complement-long-long.c: New test.
>         * gcc.dg/tree-ssa/clz-complement-long.c: New test.
>         * gcc.dg/tree-ssa/ctz-complement-char.c: New test.
>         * gcc.dg/tree-ssa/ctz-complement-int.c: New test.
>         * gcc.dg/tree-ssa/ctz-complement-long-long.c: New test.
>         * gcc.dg/tree-ssa/ctz-complement-long.c: New test.
>
> ---
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cltz-complement-max.c b/gcc/testsuite/gcc.dg/tree-ssa/cltz-complement-max.c
> new file mode 100644
> index 0000000000000000000000000000000000000000..1a29ca52e42e50822e4e3213b2cb008b766d0318
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/cltz-complement-max.c
> @@ -0,0 +1,60 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fno-tree-loop-optimize -fdump-tree-optimized" } */
> +
> +#define PREC (__CHAR_BIT__)
> +
> +int clz_complement_count1 (unsigned char b) {
> +    int c = 0;
> +
> +    while (b) {
> +       b >>= 1;
> +       c++;
> +    }
> +    if (c <= PREC)
> +      return 0;
> +    else
> +      return 34567;
> +}
> +
> +int clz_complement_count2 (unsigned char b) {
> +    int c = 0;
> +
> +    while (b) {
> +       b >>= 1;
> +       c++;
> +    }
> +    if (c <= PREC - 1)
> +      return 0;
> +    else
> +      return 76543;
> +}
> +
> +int ctz_complement_count1 (unsigned char b) {
> +    int c = 0;
> +
> +    while (b) {
> +       b <<= 1;
> +       c++;
> +    }
> +    if (c <= PREC)
> +      return 0;
> +    else
> +      return 23456;
> +}
> +
> +int ctz_complement_count2 (unsigned char b) {
> +    int c = 0;
> +
> +    while (b) {
> +       b <<= 1;
> +       c++;
> +    }
> +    if (c <= PREC - 1)
> +      return 0;
> +    else
> +      return 65432;
> +}
> +/* { dg-final { scan-tree-dump-times "34567" 0 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "76543" 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "23456" 0 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "65432" 1 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-char.c b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-char.c
> new file mode 100644
> index 0000000000000000000000000000000000000000..2ebe8fabcaf0ce88f3a6a46e9ba4ba79b7d3672e
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-char.c
> @@ -0,0 +1,31 @@
> +/* { dg-do run } */
> +/* { dg-require-effective-target clz } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +#define PREC (__CHAR_BIT__)
> +
> +int
> +__attribute__ ((noinline, noclone))
> +foo (unsigned char b) {
> +    int c = 0;
> +
> +    while (b) {
> +       b >>= 1;
> +       c++;
> +    }
> +
> +    return c;
> +}
> +
> +int main()
> +{
> +  if (foo(0) != 0)
> +    __builtin_abort ();
> +  if (foo(5) != 3)
> +    __builtin_abort ();
> +  if (foo(255) != 8)
> +    __builtin_abort ();
> +  return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "__builtin_clz|\\.CLZ" 1 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-int.c b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-int.c
> new file mode 100644
> index 0000000000000000000000000000000000000000..f2c5c23f6a7d84ecb637c6961698b0fc30d7426b
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-int.c
> @@ -0,0 +1,31 @@
> +/* { dg-do run } */
> +/* { dg-require-effective-target clz } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +#define PREC (__CHAR_BIT__ * __SIZEOF_INT__)
> +
> +int
> +__attribute__ ((noinline, noclone))
> +foo (unsigned int b) {
> +    int c = 0;
> +
> +    while (b) {
> +       b >>= 1;
> +       c++;
> +    }
> +
> +    return c;
> +}
> +
> +int main()
> +{
> +  if (foo(0) != 0)
> +    __builtin_abort ();
> +  if (foo(5) != 3)
> +    __builtin_abort ();
> +  if (foo(1 << (PREC - 1)) != PREC)
> +    __builtin_abort ();
> +  return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "__builtin_clz|\\.CLZ" 1 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-long-long.c b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-long-long.c
> new file mode 100644
> index 0000000000000000000000000000000000000000..7f7793f0efac1f0d793e6e99b84988e5cc5221c9
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-long-long.c
> @@ -0,0 +1,31 @@
> +/* { dg-do run } */
> +/* { dg-require-effective-target clzll } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +#define PREC (__CHAR_BIT__ * __SIZEOF_LONG_LONG__)
> +
> +int
> +__attribute__ ((noinline, noclone))
> +foo (unsigned long long b) {
> +    int c = 0;
> +
> +    while (b) {
> +       b >>= 1;
> +       c++;
> +    }
> +
> +    return c;
> +}
> +
> +int main()
> +{
> +  if (foo(0) != 0)
> +    __builtin_abort ();
> +  if (foo(5) != 3)
> +    __builtin_abort ();
> +  if (foo(1LL << (PREC - 1)) != PREC)
> +    __builtin_abort ();
> +  return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "__builtin_clz|\\.CLZ" 1 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-long.c b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-long.c
> new file mode 100644
> index 0000000000000000000000000000000000000000..97161bb7a74260bea20e325ebab64acb33a2b696
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-long.c
> @@ -0,0 +1,31 @@
> +/* { dg-do run } */
> +/* { dg-require-effective-target clzl } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +#define PREC (__CHAR_BIT__ * __SIZEOF_LONG__)
> +
> +int
> +__attribute__ ((noinline, noclone))
> +foo (unsigned long b) {
> +    int c = 0;
> +
> +    while (b) {
> +       b >>= 1;
> +       c++;
> +    }
> +
> +    return c;
> +}
> +
> +int main()
> +{
> +  if (foo(0) != 0)
> +    __builtin_abort ();
> +  if (foo(5) != 3)
> +    __builtin_abort ();
> +  if (foo(1L << (PREC - 1)) != PREC)
> +    __builtin_abort ();
> +  return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "__builtin_clz|\\.CLZ" 1 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-char.c b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-char.c
> new file mode 100644
> index 0000000000000000000000000000000000000000..b9afe8852d8ffbc7ee9a0760cf04b8f98af293a2
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-char.c
> @@ -0,0 +1,31 @@
> +/* { dg-do run } */
> +/* { dg-require-effective-target ctz } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +#define PREC (__CHAR_BIT__)
> +
> +int
> +__attribute__ ((noinline, noclone))
> +foo (unsigned char b) {
> +    int c = 0;
> +
> +    while (b) {
> +       b <<= 1;
> +       c++;
> +    }
> +
> +    return c;
> +}
> +
> +int main()
> +{
> +  if (foo(0) != 0)
> +    __builtin_abort ();
> +  if (foo(96) != PREC - 5)
> +    __builtin_abort ();
> +  if (foo(35) != PREC)
> +    __builtin_abort ();
> +  return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "__builtin_ctz|\\.CTZ" 1 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-int.c b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-int.c
> new file mode 100644
> index 0000000000000000000000000000000000000000..d2702a65daf34db66550d2255395db68a29a4797
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-int.c
> @@ -0,0 +1,31 @@
> +/* { dg-do run } */
> +/* { dg-require-effective-target ctz } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +#define PREC (__CHAR_BIT__ * __SIZEOF_INT__)
> +
> +int
> +__attribute__ ((noinline, noclone))
> +foo (unsigned int b) {
> +    int c = 0;
> +
> +    while (b) {
> +       b <<= 1;
> +       c++;
> +    }
> +
> +    return c;
> +}
> +
> +int main()
> +{
> +  if (foo(0) != 0)
> +    __builtin_abort ();
> +  if (foo(96) != PREC - 5)
> +    __builtin_abort ();
> +  if (foo(35) != PREC)
> +    __builtin_abort ();
> +  return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "__builtin_ctz|\\.CTZ" 1 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-long-long.c b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-long-long.c
> new file mode 100644
> index 0000000000000000000000000000000000000000..1ea0d5d7d9f8be1824c4177c33edd91e66b4ddab
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-long-long.c
> @@ -0,0 +1,31 @@
> +/* { dg-do run } */
> +/* { dg-require-effective-target ctzll } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +#define PREC (__CHAR_BIT__ * __SIZEOF_LONG_LONG__)
> +
> +int
> +__attribute__ ((noinline, noclone))
> +foo (unsigned long long b) {
> +    int c = 0;
> +
> +    while (b) {
> +       b <<= 1;
> +       c++;
> +    }
> +
> +    return c;
> +}
> +
> +int main()
> +{
> +  if (foo(0) != 0)
> +    __builtin_abort ();
> +  if (foo(96) != PREC - 5)
> +    __builtin_abort ();
> +  if (foo(35) != PREC)
> +    __builtin_abort ();
> +  return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "__builtin_ctz|\\.CTZ" 1 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-long.c b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-long.c
> new file mode 100644
> index 0000000000000000000000000000000000000000..80fb02dcfa68bc022ae69b26fb189323e01fc6fc
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-long.c
> @@ -0,0 +1,31 @@
> +/* { dg-do run } */
> +/* { dg-require-effective-target ctzl } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +#define PREC (__CHAR_BIT__ * __SIZEOF_LONG__)
> +
> +int
> +__attribute__ ((noinline, noclone))
> +foo (unsigned long b) {
> +    int c = 0;
> +
> +    while (b) {
> +       b <<= 1;
> +       c++;
> +    }
> +
> +    return c;
> +}
> +
> +int main()
> +{
> +  if (foo(0) != 0)
> +    __builtin_abort ();
> +  if (foo(96) != PREC - 5)
> +    __builtin_abort ();
> +  if (foo(35) != PREC)
> +    __builtin_abort ();
> +  return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "__builtin_ctz|\\.CTZ" 1 "optimized" } } */
> diff --git a/gcc/testsuite/lib/target-supports.exp b/gcc/testsuite/lib/target-supports.exp
> index 2a058c67c53466fe41b748d37ab660afd4e3403f..c745202624da672d1bdc21b8e74c1daac6ad9933 100644
> --- a/gcc/testsuite/lib/target-supports.exp
> +++ b/gcc/testsuite/lib/target-supports.exp
> @@ -8701,6 +8701,72 @@ proc check_effective_target_popcount { } {
>      } "" ]
>  }
>
> +# Return 1 if the target supports clz on int.
> +
> +proc check_effective_target_clz { } {
> +    return [check_no_messages_and_pattern clz "!\\(call" rtl-expand {
> +        int foo (int b)
> +          {
> +            return __builtin_clz (b);
> +          }
> +    } "" ]
> +}
> +
> +# Return 1 if the target supports clz on long.
> +
> +proc check_effective_target_clzl { } {
> +    return [check_no_messages_and_pattern clzl "!\\(call" rtl-expand {
> +       int foo (long b)
> +         {
> +           return __builtin_clzl (b);
> +         }
> +    } "" ]
> +}
> +
> +# Return 1 if the target supports clz on long long.
> +
> +proc check_effective_target_clzll { } {
> +    return [check_no_messages_and_pattern clzll "!\\(call" rtl-expand {
> +        int foo (long long b)
> +          {
> +            return __builtin_clzll (b);
> +          }
> +    } "" ]
> +}
> +
> +# Return 1 if the target supports ctz on int.
> +
> +proc check_effective_target_ctz { } {
> +    return [check_no_messages_and_pattern ctz "!\\(call" rtl-expand {
> +        int foo (int b)
> +          {
> +            return __builtin_ctz (b);
> +          }
> +    } "" ]
> +}
> +
> +# Return 1 if the target supports ctz on long.
> +
> +proc check_effective_target_ctzl { } {
> +    return [check_no_messages_and_pattern ctzl "!\\(call" rtl-expand {
> +       int foo (long b)
> +         {
> +           return __builtin_ctzl (b);
> +         }
> +    } "" ]
> +}
> +
> +# Return 1 if the target supports ctz on long long.
> +
> +proc check_effective_target_ctzll { } {
> +    return [check_no_messages_and_pattern ctzll "!\\(call" rtl-expand {
> +        int foo (long long b)
> +          {
> +            return __builtin_ctzll (b);
> +          }
> +    } "" ]
> +}
> +
>  # Return 1 if the target supports atomic operations on "long long"
>  # and can execute them.
>  #
> diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc
> index f75398afb7c9fdf42e69e940e2232942143049f6..0e4e87aea34622c8ee21f5c8e29dae2d0cdd2643 100644
> --- a/gcc/tree-scalar-evolution.cc
> +++ b/gcc/tree-scalar-evolution.cc
> @@ -3397,12 +3397,21 @@ expression_expensive_p (tree expr, hash_map<tree, uint64_t> &cache,
>          library call for popcount when backend does not have an instruction
>          to do so.  We consider this to be expensive and generate
>          __builtin_popcount only when backend defines it.  */
> +      optab optab;
>        combined_fn cfn = get_call_combined_fn (expr);
>        switch (cfn)
>         {
>         CASE_CFN_POPCOUNT:
> +         optab = popcount_optab;
> +         goto bitcount_call;
> +       CASE_CFN_CLZ:
> +         optab = clz_optab;
> +         goto bitcount_call;
> +       CASE_CFN_CTZ:
> +         optab = ctz_optab;
> +bitcount_call:
>           /* Check if opcode for popcount is available in the mode required.  */
> -         if (optab_handler (popcount_optab,
> +         if (optab_handler (optab,
>                              TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr, 0))))
>               == CODE_FOR_nothing)
>             {
> @@ -3415,7 +3424,7 @@ expression_expensive_p (tree expr, hash_map<tree, uint64_t> &cache,
>                  instructions.  */
>               if (is_a <scalar_int_mode> (mode, &int_mode)
>                   && GET_MODE_SIZE (int_mode) == 2 * UNITS_PER_WORD
> -                 && (optab_handler (popcount_optab, word_mode)
> +                 && (optab_handler (optab, word_mode)
>                       != CODE_FOR_nothing))
>                   break;
>               return true;
> diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
> index fece876099c1687569d6351e7d2416ea6acae5b5..ce2441f2a6dbdf2d8fe42755d5d1abd8a631bb5c 100644
> --- a/gcc/tree-ssa-loop-niter.cc
> +++ b/gcc/tree-ssa-loop-niter.cc
> @@ -42,6 +42,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "tree-chrec.h"
>  #include "tree-scalar-evolution.h"
>  #include "tree-dfa.h"
> +#include "internal-fn.h"
>  #include "gimple-range.h"
>
>
> @@ -2198,6 +2199,224 @@ number_of_iterations_popcount (loop_p loop, edge exit,
>    return true;
>  }
>
> +/* 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.  */
> +
> +static tree
> +build_cltz_expr (tree src, bool leading, bool define_at_zero)
> +{
> +  tree fn;
> +  internal_fn ifn = leading ? IFN_CLZ : IFN_CTZ;
> +  bool use_ifn = false;
> +  int prec = TYPE_PRECISION (TREE_TYPE (src));
> +  int i_prec = TYPE_PRECISION (integer_type_node);
> +  int li_prec = TYPE_PRECISION (long_integer_type_node);
> +  int lli_prec = TYPE_PRECISION (long_long_integer_type_node);
> +
> +  tree utype = unsigned_type_for (TREE_TYPE (src));
> +  src = fold_convert (utype, src);
> +
> +  if (direct_internal_fn_supported_p (ifn, utype, OPTIMIZE_FOR_BOTH))
> +    use_ifn = true;
> +  else if (prec <= i_prec)
> +    fn = leading ? builtin_decl_implicit (BUILT_IN_CLZ)
> +                : builtin_decl_implicit (BUILT_IN_CTZ);
> +  else if (prec == li_prec)
> +    fn = leading ? builtin_decl_implicit (BUILT_IN_CLZL)
> +                : builtin_decl_implicit (BUILT_IN_CTZL);
> +  else if (prec == lli_prec || prec == 2 * lli_prec)
> +    fn = leading ? builtin_decl_implicit (BUILT_IN_CLZLL)
> +                : builtin_decl_implicit (BUILT_IN_CTZLL);
> +  else
> +    return NULL_TREE;
> +
> +  tree call;
> +  if (use_ifn)
> +    {
> +      call = build_call_expr_internal_loc (UNKNOWN_LOCATION, ifn,
> +                                          integer_type_node, 1, src);
> +      int val;
> +      scalar_int_mode mode = SCALAR_INT_TYPE_MODE (utype);
> +      int optab_defined_at_zero
> +       = leading ? CLZ_DEFINED_VALUE_AT_ZERO (mode, val)
> +                 : CTZ_DEFINED_VALUE_AT_ZERO (mode, val);
> +      if (define_at_zero && !(optab_defined_at_zero == 2 && val == prec))
> +       {
> +         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 (prec == 2 * lli_prec)
> +    {
> +      tree src1 = fold_convert (long_long_unsigned_type_node,
> +                               fold_build2 (RSHIFT_EXPR, TREE_TYPE (src),
> +                                            unshare_expr (src),
> +                                            build_int_cst (integer_type_node,
> +                                                           lli_prec)));
> +      tree src2 = fold_convert (long_long_unsigned_type_node, src);
> +      /* We count the zeroes in src1, and add the number in src2 when src1
> +        is 0.  */
> +      if (!leading)
> +       std::swap(src1, src2);
> +      tree call1 = build_call_expr (fn, 1, src1);
> +      tree call2 = build_call_expr (fn, 1, src2);
> +      if (define_at_zero)
> +       {
> +         tree is_zero2 = fold_build2 (NE_EXPR, boolean_type_node, src2,
> +                                      build_zero_cst (TREE_TYPE (src2)));
> +         call2 = fold_build3(COND_EXPR, integer_type_node, is_zero2, call2,
> +                             build_int_cst (integer_type_node, lli_prec));
> +       }
> +      tree is_zero1 = fold_build2 (NE_EXPR, boolean_type_node, src1,
> +                                  build_zero_cst (TREE_TYPE (src1)));
> +      call = fold_build3(COND_EXPR, integer_type_node, is_zero1, call1,
> +                        fold_build2 (PLUS_EXPR, integer_type_node, call2,
> +                                     build_int_cst (integer_type_node,
> +                                                    lli_prec)));
> +    }
> +  else
> +    {
> +      if (prec < i_prec)
> +       src = fold_convert (unsigned_type_node, src);
> +
> +      call = build_call_expr (fn, 1, src);
> +      if (define_at_zero)
> +       {
> +         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));
> +       }
> +
> +      if (leading && prec < i_prec)
> +       call = fold_build2(MINUS_EXPR, integer_type_node, call,
> +                          build_int_cst (integer_type_node,
> +                                         i_prec - prec));
> +    }
> +
> +  return call;
> +}
> +
> +/* See comment below for number_of_iterations_bitcount.
> +   For c[lt]z complement, we have:
> +
> +   modify:
> +   iv_2 = iv_1 >> 1 OR iv_1 << 1
> +
> +   test:
> +   if (iv != 0)
> +
> +   modification count:
> +   src precision - c[lt]z (src)
> +
> + */
> +
> +static bool
> +number_of_iterations_cltz_complement (loop_p loop, edge exit,
> +                              enum tree_code code,
> +                              class tree_niter_desc *niter)
> +{
> +  bool modify_before_test = true;
> +  HOST_WIDE_INT max;
> +
> +  /* Check that condition for staying inside the loop is like
> +     if (iv != 0).  */
> +  gimple *cond_stmt = last_stmt (exit->src);
> +  if (!cond_stmt
> +      || gimple_code (cond_stmt) != GIMPLE_COND
> +      || code != NE_EXPR
> +      || !integer_zerop (gimple_cond_rhs (cond_stmt))
> +      || TREE_CODE (gimple_cond_lhs (cond_stmt)) != SSA_NAME)
> +    return false;
> +
> +  tree iv_2 = gimple_cond_lhs (cond_stmt);
> +  gimple *iv_2_stmt = SSA_NAME_DEF_STMT (iv_2);
> +
> +  /* If the test comes before the iv modification, then these will actually be
> +     iv_1 and a phi node.  */
> +  if (gimple_code (iv_2_stmt) == GIMPLE_PHI
> +      && gimple_bb (iv_2_stmt) == loop->header
> +      && gimple_phi_num_args (iv_2_stmt) == 2
> +      && (TREE_CODE (gimple_phi_arg_def (iv_2_stmt,
> +                                        loop_latch_edge (loop)->dest_idx))
> +         == SSA_NAME))
> +    {
> +      /* iv_2 is actually one of the inputs to the phi.  */
> +      iv_2 = gimple_phi_arg_def (iv_2_stmt, loop_latch_edge (loop)->dest_idx);
> +      iv_2_stmt = SSA_NAME_DEF_STMT (iv_2);
> +      modify_before_test = false;
> +    }
> +
> +  /* Make sure iv_2_stmt is a logical shift by one stmt:
> +     iv_2 = iv_1 {>>|<<} 1  */
> +  if (!is_gimple_assign (iv_2_stmt)
> +      || (gimple_assign_rhs_code (iv_2_stmt) != LSHIFT_EXPR
> +         && (gimple_assign_rhs_code (iv_2_stmt) != RSHIFT_EXPR
> +             || !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_lhs (iv_2_stmt)))))
> +      || !integer_onep (gimple_assign_rhs2 (iv_2_stmt)))
> +    return false;
> +
> +  bool left_shift = (gimple_assign_rhs_code (iv_2_stmt) == LSHIFT_EXPR);
> +
> +  tree iv_1 = gimple_assign_rhs1 (iv_2_stmt);
> +
> +  /* Check the recurrence.  */
> +  gimple *phi = SSA_NAME_DEF_STMT (iv_1);
> +  if (gimple_code (phi) != GIMPLE_PHI
> +      || (gimple_bb (phi) != loop_latch_edge (loop)->dest)
> +      || (iv_2 != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx)))
> +    return false;
> +
> +  /* We found a match.  */
> +  tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx);
> +  int src_precision = TYPE_PRECISION (TREE_TYPE (src));
> +
> +  /* Get the corresponding c[lt]z builtin.  */
> +  tree expr = build_cltz_expr (src, !left_shift, true);
> +
> +  if (!expr)
> +    return false;
> +
> +  expr = fold_build2 (MINUS_EXPR, integer_type_node,
> +                     build_int_cst (integer_type_node, src_precision),
> +                     expr);
> +
> +  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);
> +      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->niter = simplify_using_initial_conditions (loop, expr);
> +
> +  if (TREE_CODE (niter->niter) == INTEGER_CST)
> +    niter->max = tree_to_uhwi (niter->niter);
> +  else
> +    niter->max = max;
> +
> +  niter->bound = NULL_TREE;
> +  niter->cmp = ERROR_MARK;
> +  return true;
> +}
> +
>  /* See if LOOP contains a bit counting idiom. The idiom consists of two parts:
>     1. A modification to the induction variabler;.
>     2. A test to determine whether or not to exit the loop.
> @@ -2244,7 +2463,8 @@ number_of_iterations_bitcount (loop_p loop, edge exit,
>                                enum tree_code code,
>                                class tree_niter_desc *niter)
>  {
> -  return number_of_iterations_popcount (loop, exit, code, niter);
> +  return (number_of_iterations_popcount (loop, exit, code, niter)
> +         || number_of_iterations_cltz_complement (loop, exit, code, niter));
>  }
>
>  /* Substitute NEW_TREE for OLD in EXPR and fold the result.
  

On Thu, 2022-12-22 17:42:16 +0000, Andrew Carlotti via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
> New patch below, bootstrapped and regression tested on
> aarch64-unknown-linux-gnu and x86_64-pc-linux-gnu - ok to merge?

> diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
> index fece876099c1687569d6351e7d2416ea6acae5b5..ce2441f2a6dbdf2d8fe42755d5d1abd8a631bb5c 100644
> --- a/gcc/tree-ssa-loop-niter.cc
> +++ b/gcc/tree-ssa-loop-niter.cc
> @@ -42,6 +42,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "tree-chrec.h"
>  #include "tree-scalar-evolution.h"
>  #include "tree-dfa.h"
> +#include "internal-fn.h"
>  #include "gimple-range.h"
>  
>  
> @@ -2198,6 +2199,224 @@ number_of_iterations_popcount (loop_p loop, edge exit,
>    return true;
>  }
>  
> +/* 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.  */
> +
> +static tree
> +build_cltz_expr (tree src, bool leading, bool define_at_zero)
> +{
[...]
> +
> +  tree call;
> +  if (use_ifn)
> +    {
> +      call = build_call_expr_internal_loc (UNKNOWN_LOCATION, ifn,
> +					   integer_type_node, 1, src);
> +      int val;
> +      scalar_int_mode mode = SCALAR_INT_TYPE_MODE (utype);
         ^^^^^^^^^^^^^^^^^^^^

This will give us a new unused variable warning.

> +      int optab_defined_at_zero
> +	= leading ? CLZ_DEFINED_VALUE_AT_ZERO (mode, val)
> +		  : CTZ_DEFINED_VALUE_AT_ZERO (mode, val);
> +      if (define_at_zero && !(optab_defined_at_zero == 2 && val == prec))
> +	{
> +	  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));
> +	}
> +    }

MfG, JBG

--
  

On Thu, Jan 19, 2023 at 10:19 AM Jan-Benedict Glaw <jbglaw@lug-owl.de> wrote:
>
> On Thu, 2022-12-22 17:42:16 +0000, Andrew Carlotti via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
> > New patch below, bootstrapped and regression tested on
> > aarch64-unknown-linux-gnu and x86_64-pc-linux-gnu - ok to merge?
>
> > diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
> > index fece876099c1687569d6351e7d2416ea6acae5b5..ce2441f2a6dbdf2d8fe42755d5d1abd8a631bb5c 100644
> > --- a/gcc/tree-ssa-loop-niter.cc
> > +++ b/gcc/tree-ssa-loop-niter.cc
> > @@ -42,6 +42,7 @@ along with GCC; see the file COPYING3.  If not see
> >  #include "tree-chrec.h"
> >  #include "tree-scalar-evolution.h"
> >  #include "tree-dfa.h"
> > +#include "internal-fn.h"
> >  #include "gimple-range.h"
> >
> >
> > @@ -2198,6 +2199,224 @@ number_of_iterations_popcount (loop_p loop, edge exit,
> >    return true;
> >  }
> >
> > +/* 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.  */
> > +
> > +static tree
> > +build_cltz_expr (tree src, bool leading, bool define_at_zero)
> > +{
> [...]
> > +
> > +  tree call;
> > +  if (use_ifn)
> > +    {
> > +      call = build_call_expr_internal_loc (UNKNOWN_LOCATION, ifn,
> > +                                        integer_type_node, 1, src);
> > +      int val;
> > +      scalar_int_mode mode = SCALAR_INT_TYPE_MODE (utype);
>          ^^^^^^^^^^^^^^^^^^^^
>
> This will give us a new unused variable warning.

I wonder if hardening the defaults.h macros like

#define CLZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE)  (((MODE), (VALUE)), 0)

fixes that and makes sense (also to avoid losing side-effects for the arguments)

Richard.


> > +      int optab_defined_at_zero
> > +     = leading ? CLZ_DEFINED_VALUE_AT_ZERO (mode, val)
> > +               : CTZ_DEFINED_VALUE_AT_ZERO (mode, val);
> > +      if (define_at_zero && !(optab_defined_at_zero == 2 && val == prec))
> > +     {
> > +       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));
> > +     }
> > +    }
>
> MfG, JBG
>
> --