diff mbox series

tree-optimization/114760 - check variants of >> and << in loop-niter

Message ID SJ2PR01MB8193C85EE8338FEF42210259E8E72@SJ2PR01MB8193.prod.exchangelabs.com
State New
Headers
Series tree-optimization/114760 - check variants of >> and << in loop-niter |

Checks

Context Check Description
linaro-tcwg-bot/tcwg_gcc_build--master-arm fail Testing failed
linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 fail Testing failed

Commit Message

Di Zhao OS May 10, 2024, 10:55 a.m. UTC 
  This patch tries to fix pr114760 by checking for the
variants explicitly. When recognizing bit counting idiom,
include pattern "x * 2" for "x << 1", and "x / 2" for
"x >> 1" (given x is unsigned).

Bootstrapped and tested on x86_64-linux-gnu.

Thanks,
Di Zhao

---

gcc/ChangeLog:
        PR tree-optimization/114760
        * tree-ssa-loop-niter.cc (is_lshift_by_1): New function
        to check if STMT is equivalent to x << 1.
        (is_rshift_by_1): New function to check if STMT is
        equivalent to x >> 1.
        (number_of_iterations_cltz): Enhance the identification
        of logical shift by one.
        (number_of_iterations_cltz_complement): Enhance the
        identification of logical shift by one.

gcc/testsuite/ChangeLog:
        PR tree-optimization/114760
        * gcc.dg/tree-ssa/pr114760-1.c: New test.
        * gcc.dg/tree-ssa/pr114760-2.c: New test.
---
 gcc/testsuite/gcc.dg/tree-ssa/pr114760-1.c | 69 ++++++++++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/pr114760-2.c | 20 +++++++
 gcc/tree-ssa-loop-niter.cc                 | 56 +++++++++++++-----
 3 files changed, 131 insertions(+), 14 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr114760-1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr114760-2.c

Comments

Richard Biener May 10, 2024, 12:55 p.m. UTC | #1 
On Fri, May 10, 2024 at 12:55 PM Di Zhao OS
<dizhao@os.amperecomputing.com> wrote:
>
> This patch tries to fix pr114760 by checking for the
> variants explicitly. When recognizing bit counting idiom,
> include pattern "x * 2" for "x << 1", and "x / 2" for
> "x >> 1" (given x is unsigned).
>
> Bootstrapped and tested on x86_64-linux-gnu.
>
> Thanks,
> Di Zhao
>
> ---
>
> gcc/ChangeLog:
>         PR tree-optimization/114760
>         * tree-ssa-loop-niter.cc (is_lshift_by_1): New function
>         to check if STMT is equivalent to x << 1.
>         (is_rshift_by_1): New function to check if STMT is
>         equivalent to x >> 1.
>         (number_of_iterations_cltz): Enhance the identification
>         of logical shift by one.
>         (number_of_iterations_cltz_complement): Enhance the
>         identification of logical shift by one.
>
> gcc/testsuite/ChangeLog:
>         PR tree-optimization/114760
>         * gcc.dg/tree-ssa/pr114760-1.c: New test.
>         * gcc.dg/tree-ssa/pr114760-2.c: New test.
> ---
>  gcc/testsuite/gcc.dg/tree-ssa/pr114760-1.c | 69 ++++++++++++++++++++++
>  gcc/testsuite/gcc.dg/tree-ssa/pr114760-2.c | 20 +++++++
>  gcc/tree-ssa-loop-niter.cc                 | 56 +++++++++++++-----
>  3 files changed, 131 insertions(+), 14 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr114760-1.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr114760-2.c
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr114760-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr114760-1.c
> new file mode 100644
> index 00000000000..9f10ccc3b51
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr114760-1.c
> @@ -0,0 +1,69 @@
> +/* PR tree-optimization/114760 */
> +/* { dg-do compile } */
> +/* { dg-require-effective-target clz } */
> +/* { dg-require-effective-target ctz } */
> +/* { dg-options "-O3 -fdump-tree-optimized" } */
> +
> +unsigned
> +ntz32_1 (unsigned x)
> +{
> +  int n = 32;
> +  while (x != 0)
> +    {
> +      n = n - 1;
> +      x = x * 2;
> +    }
> +  return n;
> +}
> +
> +unsigned
> +ntz32_2 (unsigned x)
> +{
> +  int n = 32;
> +  while (x != 0)
> +    {
> +      n = n - 1;
> +      x = x + x;
> +    }
> +  return n;
> +}
> +
> +unsigned
> +ntz32_3 (unsigned x)
> +{
> +  int n = 32;
> +  while (x != 0)
> +    {
> +      n = n - 1;
> +      x = x << 1;
> +    }
> +  return n;
> +}
> +
> +#define PREC (__CHAR_BIT__ * __SIZEOF_INT__)
> +int
> +nlz32_1 (unsigned int b) {
> +    int c = PREC;
> +
> +    while (b != 0) {
> +       b >>= 1;
> +       c --;
> +    }
> +
> +    return c;
> +}
> +
> +int
> +nlz32_2 (unsigned int b) {
> +    int c = PREC;
> +
> +    while (b != 0) {
> +       b /= 2;
> +       c --;
> +    }
> +
> +    return c;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "__builtin_ctz|\\.CTZ" 3 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "__builtin_clz|\\.CLZ" 2 "optimized" } } */
> \ No newline at end of file
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr114760-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr114760-2.c
> new file mode 100644
> index 00000000000..e1b4c4b1338
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr114760-2.c
> @@ -0,0 +1,20 @@
> +/* PR tree-optimization/114760 */
> +/* { dg-do compile } */
> +/* { dg-require-effective-target clz } */
> +/* { dg-options "-O3 -fdump-tree-optimized" } */
> +
> +// Check that for signed type, there's no CLZ.
> +#define PREC (__CHAR_BIT__ * __SIZEOF_INT__)
> +int
> +no_nlz32 (int b) {
> +    int c = PREC;
> +
> +    while (b != 0) {
> +       b /= 2;
> +       c --;
> +    }
> +
> +    return c;
> +}
> +
> +/* { dg-final { scan-tree-dump-not "__builtin_ctz|\\.CLZ" "optimized" } } */
> \ No newline at end of file
> diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
> index 0fde07e626f..1d99264949b 100644
> --- a/gcc/tree-ssa-loop-niter.cc
> +++ b/gcc/tree-ssa-loop-niter.cc
> @@ -2303,6 +2303,38 @@ build_cltz_expr (tree src, bool leading, bool define_at_zero)
>    return call;
>  }
>
> +/* Returns true if STMT is equivalent to x << 1.  */
> +
> +static bool
> +is_lshift_by_1 (gimple *stmt)

You are checking for gimple-assign before calling these so please
use a 'gassign *' typed argument.

> +{
> +  if (gimple_assign_rhs_code (stmt) == LSHIFT_EXPR
> +      && integer_onep (gimple_assign_rhs2 (stmt)))
> +    return true;
> +  if (gimple_assign_rhs_code (stmt) == MULT_EXPR
> +      && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
> +      && tree_to_shwi (gimple_assign_rhs2 (stmt)) == 2)

You need to check for tree_fits_shwi_p (wich also checks for INTEGER_CST)
before using tree_to_shwi.

Ok with this change (to both functions).

Thanks,
Richard.

> +    return true;
> +  return false;
> +}
> +
> +/* Returns true if STMT is equivalent to x >> 1.  */
> +
> +static bool
> +is_rshift_by_1 (gimple *stmt)
> +{
> +  if (!TYPE_UNSIGNED (TREE_TYPE (gimple_assign_lhs (stmt))))
> +    return false;
> +  if (gimple_assign_rhs_code (stmt) == RSHIFT_EXPR
> +      && integer_onep (gimple_assign_rhs2 (stmt)))
> +    return true;
> +  if (gimple_assign_rhs_code (stmt) == TRUNC_DIV_EXPR
> +      && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
> +      && tree_to_shwi (gimple_assign_rhs2 (stmt)) == 2)
> +    return true;
> +  return false;
> +}
> +
>  /* See comment below for number_of_iterations_bitcount.
>     For c[lt]z, we have:
>
> @@ -2400,14 +2432,12 @@ number_of_iterations_cltz (loop_p loop, edge exit,
>
>    /* 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)))
> +  if (!is_gimple_assign (iv_2_stmt))
> +    return false;
> +  bool left_shift = false;
> +  if (!((left_shift = is_lshift_by_1 (iv_2_stmt))
> +       || is_rshift_by_1 (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);
>
> @@ -2516,14 +2546,12 @@ number_of_iterations_cltz_complement (loop_p loop, edge exit,
>
>    /* 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)))
> +  if (!is_gimple_assign (iv_2_stmt))
> +    return false;
> +  bool left_shift = false;
> +  if (!((left_shift = is_lshift_by_1 (iv_2_stmt))
> +       || is_rshift_by_1 (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);
>
> --
> 2.25.1
>
>
>
Di Zhao OS May 11, 2024, 10:10 a.m. UTC | #2 
Fixed the problems and committed to trunk.

Thanks,
Di Zhao

> -----Original Message-----
> From: Richard Biener <richard.guenther@gmail.com>
> Sent: Friday, May 10, 2024 8:56 PM
> To: Di Zhao OS <dizhao@os.amperecomputing.com>
> Cc: gcc-patches@gcc.gnu.org
> Subject: Re: [PATCH] tree-optimization/114760 - check variants of >> and << in
> loop-niter
> 
> On Fri, May 10, 2024 at 12:55 PM Di Zhao OS
> <dizhao@os.amperecomputing.com> wrote:
> >
> > This patch tries to fix pr114760 by checking for the
> > variants explicitly. When recognizing bit counting idiom,
> > include pattern "x * 2" for "x << 1", and "x / 2" for
> > "x >> 1" (given x is unsigned).
> >
> > Bootstrapped and tested on x86_64-linux-gnu.
> >
> > Thanks,
> > Di Zhao
> >
> > ---
> >
> > gcc/ChangeLog:
> >         PR tree-optimization/114760
> >         * tree-ssa-loop-niter.cc (is_lshift_by_1): New function
> >         to check if STMT is equivalent to x << 1.
> >         (is_rshift_by_1): New function to check if STMT is
> >         equivalent to x >> 1.
> >         (number_of_iterations_cltz): Enhance the identification
> >         of logical shift by one.
> >         (number_of_iterations_cltz_complement): Enhance the
> >         identification of logical shift by one.
> >
> > gcc/testsuite/ChangeLog:
> >         PR tree-optimization/114760
> >         * gcc.dg/tree-ssa/pr114760-1.c: New test.
> >         * gcc.dg/tree-ssa/pr114760-2.c: New test.
> > ---
> >  gcc/testsuite/gcc.dg/tree-ssa/pr114760-1.c | 69 ++++++++++++++++++++++
> >  gcc/testsuite/gcc.dg/tree-ssa/pr114760-2.c | 20 +++++++
> >  gcc/tree-ssa-loop-niter.cc                 | 56 +++++++++++++-----
> >  3 files changed, 131 insertions(+), 14 deletions(-)
> >  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr114760-1.c
> >  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr114760-2.c
> >
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr114760-1.c
> b/gcc/testsuite/gcc.dg/tree-ssa/pr114760-1.c
> > new file mode 100644
> > index 00000000000..9f10ccc3b51
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr114760-1.c
> > @@ -0,0 +1,69 @@
> > +/* PR tree-optimization/114760 */
> > +/* { dg-do compile } */
> > +/* { dg-require-effective-target clz } */
> > +/* { dg-require-effective-target ctz } */
> > +/* { dg-options "-O3 -fdump-tree-optimized" } */
> > +
> > +unsigned
> > +ntz32_1 (unsigned x)
> > +{
> > +  int n = 32;
> > +  while (x != 0)
> > +    {
> > +      n = n - 1;
> > +      x = x * 2;
> > +    }
> > +  return n;
> > +}
> > +
> > +unsigned
> > +ntz32_2 (unsigned x)
> > +{
> > +  int n = 32;
> > +  while (x != 0)
> > +    {
> > +      n = n - 1;
> > +      x = x + x;
> > +    }
> > +  return n;
> > +}
> > +
> > +unsigned
> > +ntz32_3 (unsigned x)
> > +{
> > +  int n = 32;
> > +  while (x != 0)
> > +    {
> > +      n = n - 1;
> > +      x = x << 1;
> > +    }
> > +  return n;
> > +}
> > +
> > +#define PREC (__CHAR_BIT__ * __SIZEOF_INT__)
> > +int
> > +nlz32_1 (unsigned int b) {
> > +    int c = PREC;
> > +
> > +    while (b != 0) {
> > +       b >>= 1;
> > +       c --;
> > +    }
> > +
> > +    return c;
> > +}
> > +
> > +int
> > +nlz32_2 (unsigned int b) {
> > +    int c = PREC;
> > +
> > +    while (b != 0) {
> > +       b /= 2;
> > +       c --;
> > +    }
> > +
> > +    return c;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump-times "__builtin_ctz|\\.CTZ" 3
> "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times "__builtin_clz|\\.CLZ" 2
> "optimized" } } */
> > \ No newline at end of file
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr114760-2.c
> b/gcc/testsuite/gcc.dg/tree-ssa/pr114760-2.c
> > new file mode 100644
> > index 00000000000..e1b4c4b1338
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr114760-2.c
> > @@ -0,0 +1,20 @@
> > +/* PR tree-optimization/114760 */
> > +/* { dg-do compile } */
> > +/* { dg-require-effective-target clz } */
> > +/* { dg-options "-O3 -fdump-tree-optimized" } */
> > +
> > +// Check that for signed type, there's no CLZ.
> > +#define PREC (__CHAR_BIT__ * __SIZEOF_INT__)
> > +int
> > +no_nlz32 (int b) {
> > +    int c = PREC;
> > +
> > +    while (b != 0) {
> > +       b /= 2;
> > +       c --;
> > +    }
> > +
> > +    return c;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump-not "__builtin_ctz|\\.CLZ" "optimized" } }
> */
> > \ No newline at end of file
> > diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
> > index 0fde07e626f..1d99264949b 100644
> > --- a/gcc/tree-ssa-loop-niter.cc
> > +++ b/gcc/tree-ssa-loop-niter.cc
> > @@ -2303,6 +2303,38 @@ build_cltz_expr (tree src, bool leading, bool
> define_at_zero)
> >    return call;
> >  }
> >
> > +/* Returns true if STMT is equivalent to x << 1.  */
> > +
> > +static bool
> > +is_lshift_by_1 (gimple *stmt)
> 
> You are checking for gimple-assign before calling these so please
> use a 'gassign *' typed argument.
> 
> > +{
> > +  if (gimple_assign_rhs_code (stmt) == LSHIFT_EXPR
> > +      && integer_onep (gimple_assign_rhs2 (stmt)))
> > +    return true;
> > +  if (gimple_assign_rhs_code (stmt) == MULT_EXPR
> > +      && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
> > +      && tree_to_shwi (gimple_assign_rhs2 (stmt)) == 2)
> 
> You need to check for tree_fits_shwi_p (wich also checks for INTEGER_CST)
> before using tree_to_shwi.
> 
> Ok with this change (to both functions).
> 
> Thanks,
> Richard.
> 
> > +    return true;
> > +  return false;
> > +}
> > +
> > +/* Returns true if STMT is equivalent to x >> 1.  */
> > +
> > +static bool
> > +is_rshift_by_1 (gimple *stmt)
> > +{
> > +  if (!TYPE_UNSIGNED (TREE_TYPE (gimple_assign_lhs (stmt))))
> > +    return false;
> > +  if (gimple_assign_rhs_code (stmt) == RSHIFT_EXPR
> > +      && integer_onep (gimple_assign_rhs2 (stmt)))
> > +    return true;
> > +  if (gimple_assign_rhs_code (stmt) == TRUNC_DIV_EXPR
> > +      && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
> > +      && tree_to_shwi (gimple_assign_rhs2 (stmt)) == 2)
> > +    return true;
> > +  return false;
> > +}
> > +
> >  /* See comment below for number_of_iterations_bitcount.
> >     For c[lt]z, we have:
> >
> > @@ -2400,14 +2432,12 @@ number_of_iterations_cltz (loop_p loop, edge exit,
> >
> >    /* 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)))
> > +  if (!is_gimple_assign (iv_2_stmt))
> > +    return false;
> > +  bool left_shift = false;
> > +  if (!((left_shift = is_lshift_by_1 (iv_2_stmt))
> > +       || is_rshift_by_1 (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);
> >
> > @@ -2516,14 +2546,12 @@ number_of_iterations_cltz_complement (loop_p loop,
> edge exit,
> >
> >    /* 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)))
> > +  if (!is_gimple_assign (iv_2_stmt))
> > +    return false;
> > +  bool left_shift = false;
> > +  if (!((left_shift = is_lshift_by_1 (iv_2_stmt))
> > +       || is_rshift_by_1 (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);
> >
> > --
> > 2.25.1
> >
> >
> >
diff mbox series

Patch

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr114760-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr114760-1.c
new file mode 100644
index 00000000000..9f10ccc3b51
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr114760-1.c
@@ -0,0 +1,69 @@ 
+/* PR tree-optimization/114760 */
+/* { dg-do compile } */
+/* { dg-require-effective-target clz } */
+/* { dg-require-effective-target ctz } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+unsigned
+ntz32_1 (unsigned x)
+{
+  int n = 32;
+  while (x != 0)
+    {
+      n = n - 1;
+      x = x * 2;
+    }
+  return n;
+}
+
+unsigned
+ntz32_2 (unsigned x)
+{
+  int n = 32;
+  while (x != 0)
+    {
+      n = n - 1;
+      x = x + x;
+    }
+  return n;
+}
+
+unsigned
+ntz32_3 (unsigned x)
+{
+  int n = 32;
+  while (x != 0)
+    {
+      n = n - 1;
+      x = x << 1;
+    }
+  return n;
+}
+
+#define PREC (__CHAR_BIT__ * __SIZEOF_INT__)
+int
+nlz32_1 (unsigned int b) {
+    int c = PREC;
+
+    while (b != 0) {
+	b >>= 1;
+	c --;
+    }
+
+    return c;
+}
+
+int
+nlz32_2 (unsigned int b) {
+    int c = PREC;
+
+    while (b != 0) {
+	b /= 2;
+	c --;
+    }
+
+    return c;
+}
+
+/* { dg-final { scan-tree-dump-times "__builtin_ctz|\\.CTZ" 3 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "__builtin_clz|\\.CLZ" 2 "optimized" } } */
\ No newline at end of file
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr114760-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr114760-2.c
new file mode 100644
index 00000000000..e1b4c4b1338
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr114760-2.c
@@ -0,0 +1,20 @@ 
+/* PR tree-optimization/114760 */
+/* { dg-do compile } */
+/* { dg-require-effective-target clz } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+// Check that for signed type, there's no CLZ.
+#define PREC (__CHAR_BIT__ * __SIZEOF_INT__)
+int
+no_nlz32 (int b) {
+    int c = PREC;
+
+    while (b != 0) {
+	b /= 2;
+	c --;
+    }
+
+    return c;
+}
+
+/* { dg-final { scan-tree-dump-not "__builtin_ctz|\\.CLZ" "optimized" } } */
\ No newline at end of file
diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
index 0fde07e626f..1d99264949b 100644
--- a/gcc/tree-ssa-loop-niter.cc
+++ b/gcc/tree-ssa-loop-niter.cc
@@ -2303,6 +2303,38 @@  build_cltz_expr (tree src, bool leading, bool define_at_zero)
   return call;
 }
 
+/* Returns true if STMT is equivalent to x << 1.  */
+
+static bool
+is_lshift_by_1 (gimple *stmt)
+{
+  if (gimple_assign_rhs_code (stmt) == LSHIFT_EXPR
+      && integer_onep (gimple_assign_rhs2 (stmt)))
+    return true;
+  if (gimple_assign_rhs_code (stmt) == MULT_EXPR
+      && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
+      && tree_to_shwi (gimple_assign_rhs2 (stmt)) == 2)
+    return true;
+  return false;
+}
+
+/* Returns true if STMT is equivalent to x >> 1.  */
+
+static bool
+is_rshift_by_1 (gimple *stmt)
+{
+  if (!TYPE_UNSIGNED (TREE_TYPE (gimple_assign_lhs (stmt))))
+    return false;
+  if (gimple_assign_rhs_code (stmt) == RSHIFT_EXPR
+      && integer_onep (gimple_assign_rhs2 (stmt)))
+    return true;
+  if (gimple_assign_rhs_code (stmt) == TRUNC_DIV_EXPR
+      && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
+      && tree_to_shwi (gimple_assign_rhs2 (stmt)) == 2)
+    return true;
+  return false;
+}
+
 /* See comment below for number_of_iterations_bitcount.
    For c[lt]z, we have:
 
@@ -2400,14 +2432,12 @@  number_of_iterations_cltz (loop_p loop, edge exit,
 
   /* 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)))
+  if (!is_gimple_assign (iv_2_stmt))
+    return false;
+  bool left_shift = false;
+  if (!((left_shift = is_lshift_by_1 (iv_2_stmt))
+	|| is_rshift_by_1 (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);
 
@@ -2516,14 +2546,12 @@  number_of_iterations_cltz_complement (loop_p loop, edge exit,
 
   /* 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)))
+  if (!is_gimple_assign (iv_2_stmt))
+    return false;
+  bool left_shift = false;
+  if (!((left_shift = is_lshift_by_1 (iv_2_stmt))
+	|| is_rshift_by_1 (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);