[PATCH] Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big. 65;6800;1c There's loop in vect_peel_nonlinear_iv_init to get init_expr * pow (step_expr, skip_niters). When skipn_iters is too big, compile time hogs. To avoid that, optimize init_expr * pow (step_expr, skip_niters) to init_expr << (exact_log2 (step_expr) * skip_niters) when step_expr is pow of 2, otherwise give up vectorization when skip_niters >= TYPE_PRECISION (TREE_TYPE (init_expr)).

[PATCH] Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big. 65;6800;1c There's loop in vect_peel_nonlinear_iv_init to get init_expr * pow (step_expr, skip_niters). When skipn_iters is too big, compile time hogs. To avoid that, optimize init_expr * pow (step_expr, skip_niters) to init_expr << (exact_log2 (step_expr) * skip_niters) when step_expr is pow of 2, otherwise give up vectorization when skip_niters >= TYPE_PRECISION (TREE_TYPE (init_expr)).

[liuhongt]

Also give up vectorization when niters_skip is negative which will be
used for fully masked loop.

Bootstrapped and regtested on x86_64-pc-linux-gnu{-m32,}.
Ok for trunk?

gcc/ChangeLog:

	PR tree-optimization/111820
	PR tree-optimization/111833
	* tree-vect-loop-manip.cc (vect_can_peel_nonlinear_iv_p): Give
	up vectorization for nonlinear iv vect_step_op_mul when
	step_expr is not exact_log2 and niters is greater than
	TYPE_PRECISION (TREE_TYPE (step_expr)). Also don't vectorize
	for nagative niters_skip which will be used by fully masked
	loop.
	(vect_can_advance_ivs_p): Pass whole phi_info to
	vect_can_peel_nonlinear_iv_p.
	* tree-vect-loop.cc (vect_peel_nonlinear_iv_init): Optimize
	init_expr * pow (step_expr, skipn) to init_expr
	<< (log2 (step_expr) * skipn) when step_expr is exact_log2.

gcc/testsuite/ChangeLog:

	* gcc.target/i386/pr111820-1.c: New test.
	* gcc.target/i386/pr111820-2.c: New test.
	* gcc.target/i386/pr103144-mul-1.c: Adjust testcase.
---
 .../gcc.target/i386/pr103144-mul-1.c          |  6 ++--
 gcc/testsuite/gcc.target/i386/pr111820-1.c    | 16 ++++++++++
 gcc/testsuite/gcc.target/i386/pr111820-2.c    | 17 ++++++++++
 gcc/tree-vect-loop-manip.cc                   | 28 ++++++++++++++--
 gcc/tree-vect-loop.cc                         | 32 ++++++++++++++++---
 5 files changed, 88 insertions(+), 11 deletions(-)
 create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-1.c
 create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-2.c

diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
index 640c34fd959..f80d1094097 100644
--- a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
+++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
@@ -23,7 +23,7 @@ foo_mul_const (int* a)
   for (int i = 0; i != N; i++)
     {
       a[i] = b;
-      b *= 3;
+      b *= 4;
     }
 }
 
@@ -34,7 +34,7 @@ foo_mul_peel (int* a, int b)
   for (int i = 0; i != 39; i++)
     {
       a[i] = b;
-      b *= 3;
+      b *= 4;
     }
 }
 
@@ -46,6 +46,6 @@ foo_mul_peel_const (int* a)
   for (int i = 0; i != 39; i++)
     {
       a[i] = b;
-      b *= 3;
+      b *= 4;
     }
 }
diff --git a/gcc/testsuite/gcc.target/i386/pr111820-1.c b/gcc/testsuite/gcc.target/i386/pr111820-1.c
new file mode 100644
index 00000000000..50e960c39d4
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr111820-1.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -mavx2 -fno-tree-vrp -Wno-aggressive-loop-optimizations -fdump-tree-vect-details" } */
+/* { dg-final { scan-tree-dump "Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big" "vect" } } */
+
+int r;
+int r_0;
+
+void f1 (void)
+{
+  int n = 0;
+  while (-- n)
+    {
+      r_0 += r;
+      r  *= 3;
+    }
+}
diff --git a/gcc/testsuite/gcc.target/i386/pr111820-2.c b/gcc/testsuite/gcc.target/i386/pr111820-2.c
new file mode 100644
index 00000000000..bbdb40798c6
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr111820-2.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-aggressive-loop-optimizations" } */
+/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
+
+int r;
+int r_0;
+
+void f (void)
+{
+  int n = 0;
+  while (-- n)
+    {
+      r_0 += r ;
+      r  *= 2;
+    }
+}
+
diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc
index 2608c286e5d..a530088b61d 100644
--- a/gcc/tree-vect-loop-manip.cc
+++ b/gcc/tree-vect-loop-manip.cc
@@ -1783,8 +1783,10 @@ iv_phi_p (stmt_vec_info stmt_info)
 /* Return true if vectorizer can peel for nonlinear iv.  */
 static bool
 vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
-			      enum vect_induction_op_type induction_type)
+			      stmt_vec_info stmt_info)
 {
+  enum vect_induction_op_type induction_type
+    = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (stmt_info);
   tree niters_skip;
   /* Init_expr will be update by vect_update_ivs_after_vectorizer,
      if niters or vf is unkown:
@@ -1805,11 +1807,31 @@ vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
       return false;
     }
 
+  /* Avoid compile time hog on vect_peel_nonlinear_iv_init.  */
+  if (induction_type == vect_step_op_mul)
+    {
+      tree step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info);
+      tree type = TREE_TYPE (step_expr);
+
+      if (wi::exact_log2 (wi::to_wide (step_expr)) == -1
+	  && LOOP_VINFO_INT_NITERS(loop_vinfo) >= TYPE_PRECISION (type))
+	{
+	  if (dump_enabled_p ())
+	    dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+			     "Avoid compile time hog on"
+			     " vect_peel_nonlinear_iv_init"
+			     " for nonlinear induction vec_step_op_mul"
+			     " when iteration count is too big.\n");
+	  return false;
+	}
+    }
+
   /* Also doens't support peel for neg when niter is variable.
      ??? generate something like niter_expr & 1 ? init_expr : -init_expr?  */
   niters_skip = LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo);
   if ((niters_skip != NULL_TREE
-       && TREE_CODE (niters_skip) != INTEGER_CST)
+       && (TREE_CODE (niters_skip) != INTEGER_CST
+	   || (HOST_WIDE_INT) TREE_INT_CST_LOW (niters_skip) < 0))
       || (!vect_use_loop_mask_for_alignment_p (loop_vinfo)
 	  && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0))
     {
@@ -1870,7 +1892,7 @@ vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
       induction_type = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (phi_info);
       if (induction_type != vect_step_op_add)
 	{
-	  if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, induction_type))
+	  if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, phi_info))
 	    return false;
 
 	  continue;
diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
index 89bdcaa0910..6bb1f3dc462 100644
--- a/gcc/tree-vect-loop.cc
+++ b/gcc/tree-vect-loop.cc
@@ -9134,11 +9134,33 @@ vect_peel_nonlinear_iv_init (gimple_seq* stmts, tree init_expr,
 	init_expr = gimple_convert (stmts, utype, init_expr);
 	unsigned skipn = TREE_INT_CST_LOW (skip_niters);
 	wide_int begin = wi::to_wide (step_expr);
-	for (unsigned i = 0; i != skipn - 1; i++)
-	  begin = wi::mul (begin, wi::to_wide (step_expr));
-	tree mult_expr = wide_int_to_tree (utype, begin);
-	init_expr = gimple_build (stmts, MULT_EXPR, utype, init_expr, mult_expr);
-	init_expr = gimple_convert (stmts, type, init_expr);
+	int pow2_step = wi::exact_log2 (begin);
+	/* Optimize init_expr * pow (step_expr, skipn) to
+	   init_expr << (log2 (step_expr) * skipn).  */
+	if (pow2_step != -1)
+	  {
+	    if (skipn >= TYPE_PRECISION (type)
+		|| skipn > (UINT_MAX / (unsigned) pow2_step)
+		|| skipn * (unsigned) pow2_step >= TYPE_PRECISION (type))
+		init_expr = build_zero_cst (type);
+	    else
+	      {
+		tree lshc = build_int_cst (utype, skipn * (unsigned) pow2_step);
+		init_expr = gimple_build (stmts, LSHIFT_EXPR, utype,
+					  init_expr, lshc);
+	      }
+	  }
+	/* Any better way for init_expr * pow (step_expr, skipn)???.  */
+	else
+	  {
+	    gcc_assert (skipn < TYPE_PRECISION (type));
+	    for (unsigned i = 0; i != skipn - 1; i++)
+	      begin = wi::mul (begin, wi::to_wide (step_expr));
+	    tree mult_expr = wide_int_to_tree (utype, begin);
+	    init_expr = gimple_build (stmts, MULT_EXPR, utype,
+				      init_expr, mult_expr);
+	  }
+	  init_expr = gimple_convert (stmts, type, init_expr);
       }
       break;
 
-- 
2.31.1

Re: [PATCH] Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big. 65; 6800; 1c There's loop in vect_peel_nonlinear_iv_init to get init_expr * pow (step_expr, skip_niters). When skipn_iters is too big, compile time hogs. To avoid that, optimize init_expr * pow (step_expr, skip_niters) to init_expr << (exact_log2 (step_expr) * skip_niters) when step_expr is pow of 2, otherwise give up vectorization when skip_niters >= TYPE_PRECISION (TREE_TYPE (init_expr)).

[Hongtao Liu]

On Wed, Oct 18, 2023 at 4:33 PM liuhongt <hongtao.liu@intel.com> wrote:
>
Cut from subject...
There's a loop in vect_peel_nonlinear_iv_init to get init_expr * pow
(step_expr, skip_niters). When skipn_iters is too big, compile time
hogs. To avoid that, optimize init_expr * pow (step_expr, skip_niters)
to init_expr << (exact_log2 (step_expr) * skip_niters) when step_expr
is pow of 2, otherwise give up vectorization when skip_niters >=
TYPE_PRECISION (TREE_TYPE (init_expr)).

> Also give up vectorization when niters_skip is negative which will be
> used for fully masked loop.
>
> Bootstrapped and regtested on x86_64-pc-linux-gnu{-m32,}.
> Ok for trunk?
>
> gcc/ChangeLog:
>
>         PR tree-optimization/111820
>         PR tree-optimization/111833
>         * tree-vect-loop-manip.cc (vect_can_peel_nonlinear_iv_p): Give
>         up vectorization for nonlinear iv vect_step_op_mul when
>         step_expr is not exact_log2 and niters is greater than
>         TYPE_PRECISION (TREE_TYPE (step_expr)). Also don't vectorize
>         for nagative niters_skip which will be used by fully masked
>         loop.
>         (vect_can_advance_ivs_p): Pass whole phi_info to
>         vect_can_peel_nonlinear_iv_p.
>         * tree-vect-loop.cc (vect_peel_nonlinear_iv_init): Optimize
>         init_expr * pow (step_expr, skipn) to init_expr
>         << (log2 (step_expr) * skipn) when step_expr is exact_log2.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.target/i386/pr111820-1.c: New test.
>         * gcc.target/i386/pr111820-2.c: New test.
>         * gcc.target/i386/pr103144-mul-1.c: Adjust testcase.
> ---
>  .../gcc.target/i386/pr103144-mul-1.c          |  6 ++--
>  gcc/testsuite/gcc.target/i386/pr111820-1.c    | 16 ++++++++++
>  gcc/testsuite/gcc.target/i386/pr111820-2.c    | 17 ++++++++++
>  gcc/tree-vect-loop-manip.cc                   | 28 ++++++++++++++--
>  gcc/tree-vect-loop.cc                         | 32 ++++++++++++++++---
>  5 files changed, 88 insertions(+), 11 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-1.c
>  create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-2.c
>
> diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
> index 640c34fd959..f80d1094097 100644
> --- a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
> +++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
> @@ -23,7 +23,7 @@ foo_mul_const (int* a)
>    for (int i = 0; i != N; i++)
>      {
>        a[i] = b;
> -      b *= 3;
> +      b *= 4;
>      }
>  }
>
> @@ -34,7 +34,7 @@ foo_mul_peel (int* a, int b)
>    for (int i = 0; i != 39; i++)
>      {
>        a[i] = b;
> -      b *= 3;
> +      b *= 4;
>      }
>  }
>
> @@ -46,6 +46,6 @@ foo_mul_peel_const (int* a)
>    for (int i = 0; i != 39; i++)
>      {
>        a[i] = b;
> -      b *= 3;
> +      b *= 4;
>      }
>  }
> diff --git a/gcc/testsuite/gcc.target/i386/pr111820-1.c b/gcc/testsuite/gcc.target/i386/pr111820-1.c
> new file mode 100644
> index 00000000000..50e960c39d4
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/i386/pr111820-1.c
> @@ -0,0 +1,16 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -mavx2 -fno-tree-vrp -Wno-aggressive-loop-optimizations -fdump-tree-vect-details" } */
> +/* { dg-final { scan-tree-dump "Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big" "vect" } } */
> +
> +int r;
> +int r_0;
> +
> +void f1 (void)
> +{
> +  int n = 0;
> +  while (-- n)
> +    {
> +      r_0 += r;
> +      r  *= 3;
> +    }
> +}
> diff --git a/gcc/testsuite/gcc.target/i386/pr111820-2.c b/gcc/testsuite/gcc.target/i386/pr111820-2.c
> new file mode 100644
> index 00000000000..bbdb40798c6
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/i386/pr111820-2.c
> @@ -0,0 +1,17 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-aggressive-loop-optimizations" } */
> +/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
> +
> +int r;
> +int r_0;
> +
> +void f (void)
> +{
> +  int n = 0;
> +  while (-- n)
> +    {
> +      r_0 += r ;
> +      r  *= 2;
> +    }
> +}
> +
> diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc
> index 2608c286e5d..a530088b61d 100644
> --- a/gcc/tree-vect-loop-manip.cc
> +++ b/gcc/tree-vect-loop-manip.cc
> @@ -1783,8 +1783,10 @@ iv_phi_p (stmt_vec_info stmt_info)
>  /* Return true if vectorizer can peel for nonlinear iv.  */
>  static bool
>  vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
> -                             enum vect_induction_op_type induction_type)
> +                             stmt_vec_info stmt_info)
>  {
> +  enum vect_induction_op_type induction_type
> +    = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (stmt_info);
>    tree niters_skip;
>    /* Init_expr will be update by vect_update_ivs_after_vectorizer,
>       if niters or vf is unkown:
> @@ -1805,11 +1807,31 @@ vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
>        return false;
>      }
>
> +  /* Avoid compile time hog on vect_peel_nonlinear_iv_init.  */
> +  if (induction_type == vect_step_op_mul)
> +    {
> +      tree step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info);
> +      tree type = TREE_TYPE (step_expr);
> +
> +      if (wi::exact_log2 (wi::to_wide (step_expr)) == -1
> +         && LOOP_VINFO_INT_NITERS(loop_vinfo) >= TYPE_PRECISION (type))
> +       {
> +         if (dump_enabled_p ())
> +           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> +                            "Avoid compile time hog on"
> +                            " vect_peel_nonlinear_iv_init"
> +                            " for nonlinear induction vec_step_op_mul"
> +                            " when iteration count is too big.\n");
> +         return false;
> +       }
> +    }
> +
>    /* Also doens't support peel for neg when niter is variable.
>       ??? generate something like niter_expr & 1 ? init_expr : -init_expr?  */
>    niters_skip = LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo);
>    if ((niters_skip != NULL_TREE
> -       && TREE_CODE (niters_skip) != INTEGER_CST)
> +       && (TREE_CODE (niters_skip) != INTEGER_CST
> +          || (HOST_WIDE_INT) TREE_INT_CST_LOW (niters_skip) < 0))
>        || (!vect_use_loop_mask_for_alignment_p (loop_vinfo)
>           && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0))
>      {
> @@ -1870,7 +1892,7 @@ vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
>        induction_type = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (phi_info);
>        if (induction_type != vect_step_op_add)
>         {
> -         if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, induction_type))
> +         if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, phi_info))
>             return false;
>
>           continue;
> diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
> index 89bdcaa0910..6bb1f3dc462 100644
> --- a/gcc/tree-vect-loop.cc
> +++ b/gcc/tree-vect-loop.cc
> @@ -9134,11 +9134,33 @@ vect_peel_nonlinear_iv_init (gimple_seq* stmts, tree init_expr,
>         init_expr = gimple_convert (stmts, utype, init_expr);
>         unsigned skipn = TREE_INT_CST_LOW (skip_niters);
>         wide_int begin = wi::to_wide (step_expr);
> -       for (unsigned i = 0; i != skipn - 1; i++)
> -         begin = wi::mul (begin, wi::to_wide (step_expr));
> -       tree mult_expr = wide_int_to_tree (utype, begin);
> -       init_expr = gimple_build (stmts, MULT_EXPR, utype, init_expr, mult_expr);
> -       init_expr = gimple_convert (stmts, type, init_expr);
> +       int pow2_step = wi::exact_log2 (begin);
> +       /* Optimize init_expr * pow (step_expr, skipn) to
> +          init_expr << (log2 (step_expr) * skipn).  */
> +       if (pow2_step != -1)
> +         {
> +           if (skipn >= TYPE_PRECISION (type)
> +               || skipn > (UINT_MAX / (unsigned) pow2_step)
> +               || skipn * (unsigned) pow2_step >= TYPE_PRECISION (type))
> +               init_expr = build_zero_cst (type);
> +           else
> +             {
> +               tree lshc = build_int_cst (utype, skipn * (unsigned) pow2_step);
> +               init_expr = gimple_build (stmts, LSHIFT_EXPR, utype,
> +                                         init_expr, lshc);
> +             }
> +         }
> +       /* Any better way for init_expr * pow (step_expr, skipn)???.  */
> +       else
> +         {
> +           gcc_assert (skipn < TYPE_PRECISION (type));
> +           for (unsigned i = 0; i != skipn - 1; i++)
> +             begin = wi::mul (begin, wi::to_wide (step_expr));
> +           tree mult_expr = wide_int_to_tree (utype, begin);
> +           init_expr = gimple_build (stmts, MULT_EXPR, utype,
> +                                     init_expr, mult_expr);
> +         }
> +         init_expr = gimple_convert (stmts, type, init_expr);
>        }
>        break;
>
> --
> 2.31.1
>


-- 
BR,
Hongtao

Re: [PATCH] Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big. 65;6800;1c There's loop in vect_peel_nonlinear_iv_init to get init_expr * pow (step_expr, skip_niters). When skipn_iters is too big, compile time hogs. To avoid that, optimize init_expr * pow (step_expr, skip_niters) to init_expr << (exact_log2 (step_expr) * skip_niters) when step_expr is pow of 2, otherwise give up vectorization when skip_niters >= TYPE_PRECISION (TREE_TYPE (init_expr)).

[Richard Biener]

On Wed, 18 Oct 2023, liuhongt wrote:

> Also give up vectorization when niters_skip is negative which will be
> used for fully masked loop.
> 
> Bootstrapped and regtested on x86_64-pc-linux-gnu{-m32,}.
> Ok for trunk?
> 
> gcc/ChangeLog:
> 
> 	PR tree-optimization/111820
> 	PR tree-optimization/111833
> 	* tree-vect-loop-manip.cc (vect_can_peel_nonlinear_iv_p): Give
> 	up vectorization for nonlinear iv vect_step_op_mul when
> 	step_expr is not exact_log2 and niters is greater than
> 	TYPE_PRECISION (TREE_TYPE (step_expr)). Also don't vectorize
> 	for nagative niters_skip which will be used by fully masked
> 	loop.
> 	(vect_can_advance_ivs_p): Pass whole phi_info to
> 	vect_can_peel_nonlinear_iv_p.
> 	* tree-vect-loop.cc (vect_peel_nonlinear_iv_init): Optimize
> 	init_expr * pow (step_expr, skipn) to init_expr
> 	<< (log2 (step_expr) * skipn) when step_expr is exact_log2.
> 
> gcc/testsuite/ChangeLog:
> 
> 	* gcc.target/i386/pr111820-1.c: New test.
> 	* gcc.target/i386/pr111820-2.c: New test.
> 	* gcc.target/i386/pr103144-mul-1.c: Adjust testcase.
> ---
>  .../gcc.target/i386/pr103144-mul-1.c          |  6 ++--
>  gcc/testsuite/gcc.target/i386/pr111820-1.c    | 16 ++++++++++
>  gcc/testsuite/gcc.target/i386/pr111820-2.c    | 17 ++++++++++
>  gcc/tree-vect-loop-manip.cc                   | 28 ++++++++++++++--
>  gcc/tree-vect-loop.cc                         | 32 ++++++++++++++++---
>  5 files changed, 88 insertions(+), 11 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-1.c
>  create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-2.c
> 
> diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
> index 640c34fd959..f80d1094097 100644
> --- a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
> +++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
> @@ -23,7 +23,7 @@ foo_mul_const (int* a)
>    for (int i = 0; i != N; i++)
>      {
>        a[i] = b;
> -      b *= 3;
> +      b *= 4;
>      }
>  }
>  
> @@ -34,7 +34,7 @@ foo_mul_peel (int* a, int b)
>    for (int i = 0; i != 39; i++)
>      {
>        a[i] = b;
> -      b *= 3;
> +      b *= 4;
>      }
>  }
>  
> @@ -46,6 +46,6 @@ foo_mul_peel_const (int* a)
>    for (int i = 0; i != 39; i++)
>      {
>        a[i] = b;
> -      b *= 3;
> +      b *= 4;
>      }
>  }
> diff --git a/gcc/testsuite/gcc.target/i386/pr111820-1.c b/gcc/testsuite/gcc.target/i386/pr111820-1.c
> new file mode 100644
> index 00000000000..50e960c39d4
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/i386/pr111820-1.c
> @@ -0,0 +1,16 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -mavx2 -fno-tree-vrp -Wno-aggressive-loop-optimizations -fdump-tree-vect-details" } */
> +/* { dg-final { scan-tree-dump "Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big" "vect" } } */
> +
> +int r;
> +int r_0;
> +
> +void f1 (void)
> +{
> +  int n = 0;
> +  while (-- n)
> +    {
> +      r_0 += r;
> +      r  *= 3;
> +    }
> +}
> diff --git a/gcc/testsuite/gcc.target/i386/pr111820-2.c b/gcc/testsuite/gcc.target/i386/pr111820-2.c
> new file mode 100644
> index 00000000000..bbdb40798c6
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/i386/pr111820-2.c
> @@ -0,0 +1,17 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-aggressive-loop-optimizations" } */
> +/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
> +
> +int r;
> +int r_0;
> +
> +void f (void)
> +{
> +  int n = 0;
> +  while (-- n)
> +    {
> +      r_0 += r ;
> +      r  *= 2;
> +    }
> +}
> +
> diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc
> index 2608c286e5d..a530088b61d 100644
> --- a/gcc/tree-vect-loop-manip.cc
> +++ b/gcc/tree-vect-loop-manip.cc
> @@ -1783,8 +1783,10 @@ iv_phi_p (stmt_vec_info stmt_info)
>  /* Return true if vectorizer can peel for nonlinear iv.  */
>  static bool
>  vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
> -			      enum vect_induction_op_type induction_type)
> +			      stmt_vec_info stmt_info)
>  {
> +  enum vect_induction_op_type induction_type
> +    = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (stmt_info);
>    tree niters_skip;
>    /* Init_expr will be update by vect_update_ivs_after_vectorizer,
>       if niters or vf is unkown:
> @@ -1805,11 +1807,31 @@ vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
>        return false;
>      }
>  
> +  /* Avoid compile time hog on vect_peel_nonlinear_iv_init.  */
> +  if (induction_type == vect_step_op_mul)
> +    {
> +      tree step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info);
> +      tree type = TREE_TYPE (step_expr);
> +
> +      if (wi::exact_log2 (wi::to_wide (step_expr)) == -1
> +	  && LOOP_VINFO_INT_NITERS(loop_vinfo) >= TYPE_PRECISION (type))
> +	{
> +	  if (dump_enabled_p ())
> +	    dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> +			     "Avoid compile time hog on"
> +			     " vect_peel_nonlinear_iv_init"
> +			     " for nonlinear induction vec_step_op_mul"
> +			     " when iteration count is too big.\n");
> +	  return false;
> +	}
> +    }
> +
>    /* Also doens't support peel for neg when niter is variable.
>       ??? generate something like niter_expr & 1 ? init_expr : -init_expr?  */
>    niters_skip = LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo);
>    if ((niters_skip != NULL_TREE
> -       && TREE_CODE (niters_skip) != INTEGER_CST)
> +       && (TREE_CODE (niters_skip) != INTEGER_CST
> +	   || (HOST_WIDE_INT) TREE_INT_CST_LOW (niters_skip) < 0))

So the bugs were not fixed without this hunk?  IIRC in the audit
trail we concluded the value is always positive ... (but of course
a large unsigned value can appear negative if you test it this way?)

>        || (!vect_use_loop_mask_for_alignment_p (loop_vinfo)
>  	  && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0))
>      {
> @@ -1870,7 +1892,7 @@ vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
>        induction_type = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (phi_info);
>        if (induction_type != vect_step_op_add)
>  	{
> -	  if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, induction_type))
> +	  if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, phi_info))
>  	    return false;
>  
>  	  continue;
> diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
> index 89bdcaa0910..6bb1f3dc462 100644
> --- a/gcc/tree-vect-loop.cc
> +++ b/gcc/tree-vect-loop.cc
> @@ -9134,11 +9134,33 @@ vect_peel_nonlinear_iv_init (gimple_seq* stmts, tree init_expr,
>  	init_expr = gimple_convert (stmts, utype, init_expr);
>  	unsigned skipn = TREE_INT_CST_LOW (skip_niters);
>  	wide_int begin = wi::to_wide (step_expr);
> -	for (unsigned i = 0; i != skipn - 1; i++)
> -	  begin = wi::mul (begin, wi::to_wide (step_expr));
> -	tree mult_expr = wide_int_to_tree (utype, begin);
> -	init_expr = gimple_build (stmts, MULT_EXPR, utype, init_expr, mult_expr);
> -	init_expr = gimple_convert (stmts, type, init_expr);
> +	int pow2_step = wi::exact_log2 (begin);
> +	/* Optimize init_expr * pow (step_expr, skipn) to
> +	   init_expr << (log2 (step_expr) * skipn).  */
> +	if (pow2_step != -1)
> +	  {
> +	    if (skipn >= TYPE_PRECISION (type)
> +		|| skipn > (UINT_MAX / (unsigned) pow2_step)
> +		|| skipn * (unsigned) pow2_step >= TYPE_PRECISION (type))
> +		init_expr = build_zero_cst (type);
> +	    else
> +	      {
> +		tree lshc = build_int_cst (utype, skipn * (unsigned) pow2_step);
> +		init_expr = gimple_build (stmts, LSHIFT_EXPR, utype,
> +					  init_expr, lshc);
> +	      }
> +	  }
> +	/* Any better way for init_expr * pow (step_expr, skipn)???.  */

I think you can use one of the mpz_pow* functions and
wi::to_mpz/from_mpz for this.  See tree-ssa-loop-niter.cc for the
most heavy user of mpz (but not pow I think).

Richard.

> +	else
> +	  {
> +	    gcc_assert (skipn < TYPE_PRECISION (type));
> +	    for (unsigned i = 0; i != skipn - 1; i++)
> +	      begin = wi::mul (begin, wi::to_wide (step_expr));
> +	    tree mult_expr = wide_int_to_tree (utype, begin);
> +	    init_expr = gimple_build (stmts, MULT_EXPR, utype,
> +				      init_expr, mult_expr);
> +	  }
> +	  init_expr = gimple_convert (stmts, type, init_expr);
>        }
>        break;
>  
> 

[PATCH] Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big.

[liuhongt]

>So the bugs were not fixed without this hunk?  IIRC in the audit
>trail we concluded the value is always positive ... (but of course
>a large unsigned value can appear negative if you test it this way?)
No, I added this incase in the future there's negative skip_niters as
you mentioned in the PR, it's just defensive programming.

>I think you can use one of the mpz_pow* functions and
>wi::to_mpz/from_mpz for this.  See tree-ssa-loop-niter.cc for the
>most heavy user of mpz (but not pow I think).
Changed.

Bootstrapped and regtested on x86_64-pc-linux-gnu{-m32,}.
Ok for trunk.

There's loop in vect_peel_nonlinear_iv_init to get init_expr *
pow (step_expr, skip_niters). When skipn_iters is too big, compile time
hogs. To avoid that, optimize init_expr * pow (step_expr, skip_niters) to
init_expr << (exact_log2 (step_expr) * skip_niters) when step_expr is
pow of 2, otherwise give up vectorization when skip_niters >=
TYPE_PRECISION (TREE_TYPE (init_expr)).

Also give up vectorization when niters_skip is negative which will be
used for fully masked loop.

gcc/ChangeLog:

	PR tree-optimization/111820
	PR tree-optimization/111833
	* tree-vect-loop-manip.cc (vect_can_peel_nonlinear_iv_p): Give
	up vectorization for nonlinear iv vect_step_op_mul when
	step_expr is not exact_log2 and niters is greater than
	TYPE_PRECISION (TREE_TYPE (step_expr)). Also don't vectorize
	for nagative niters_skip which will be used by fully masked
	loop.
	(vect_can_advance_ivs_p): Pass whole phi_info to
	vect_can_peel_nonlinear_iv_p.
	* tree-vect-loop.cc (vect_peel_nonlinear_iv_init): Optimize
	init_expr * pow (step_expr, skipn) to init_expr
	<< (log2 (step_expr) * skipn) when step_expr is exact_log2.

gcc/testsuite/ChangeLog:

	* gcc.target/i386/pr111820-1.c: New test.
	* gcc.target/i386/pr111820-2.c: New test.
	* gcc.target/i386/pr111820-3.c: New test.
	* gcc.target/i386/pr103144-mul-1.c: Adjust testcase.
	* gcc.target/i386/pr103144-mul-2.c: Adjust testcase.
---
 .../gcc.target/i386/pr103144-mul-1.c          |  8 ++---
 .../gcc.target/i386/pr103144-mul-2.c          |  8 ++---
 gcc/testsuite/gcc.target/i386/pr111820-1.c    | 16 +++++++++
 gcc/testsuite/gcc.target/i386/pr111820-2.c    | 16 +++++++++
 gcc/testsuite/gcc.target/i386/pr111820-3.c    | 16 +++++++++
 gcc/tree-vect-loop-manip.cc                   | 28 +++++++++++++--
 gcc/tree-vect-loop.cc                         | 34 ++++++++++++++++---
 7 files changed, 110 insertions(+), 16 deletions(-)
 create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-1.c
 create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-2.c
 create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-3.c

diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
index 640c34fd959..913d7737dcd 100644
--- a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
+++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
@@ -11,7 +11,7 @@ foo_mul (int* a, int b)
   for (int i = 0; i != N; i++)
     {
       a[i] = b;
-      b *= 3;
+      b *= 4;
     }
 }
 
@@ -23,7 +23,7 @@ foo_mul_const (int* a)
   for (int i = 0; i != N; i++)
     {
       a[i] = b;
-      b *= 3;
+      b *= 4;
     }
 }
 
@@ -34,7 +34,7 @@ foo_mul_peel (int* a, int b)
   for (int i = 0; i != 39; i++)
     {
       a[i] = b;
-      b *= 3;
+      b *= 4;
     }
 }
 
@@ -46,6 +46,6 @@ foo_mul_peel_const (int* a)
   for (int i = 0; i != 39; i++)
     {
       a[i] = b;
-      b *= 3;
+      b *= 4;
     }
 }
diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
index 39fdea3a69d..b2ff186e335 100644
--- a/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
+++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
@@ -16,12 +16,12 @@ avx2_test (void)
 
   __builtin_memset (epi32_exp, 0, N * sizeof (int));
   int b = 8;
-  v8si init = __extension__(v8si) { b, b * 3, b * 9, b * 27, b * 81, b * 243, b * 729, b * 2187 };
+  v8si init = __extension__(v8si) { b, b * 4, b * 16, b * 64, b * 256, b * 1024, b * 4096, b * 16384 };
 
   for (int i = 0; i != N / 8; i++)
     {
       memcpy (epi32_exp + i * 8, &init, 32);
-      init *= 6561;
+      init *= 65536;
     }
 
   foo_mul (epi32_dst, b);
@@ -32,11 +32,11 @@ avx2_test (void)
   if (__builtin_memcmp (epi32_dst, epi32_exp, 39 * 4) != 0)
     __builtin_abort ();
 
-  init = __extension__(v8si) { 1, 3, 9, 27, 81, 243, 729, 2187 };
+  init = __extension__(v8si) { 1, 4, 16, 64, 256, 1024, 4096, 16384 };
   for (int i = 0; i != N / 8; i++)
     {
       memcpy (epi32_exp + i * 8, &init, 32);
-      init *= 6561;
+      init *= 65536;
     }
 
   foo_mul_const (epi32_dst);
diff --git a/gcc/testsuite/gcc.target/i386/pr111820-1.c b/gcc/testsuite/gcc.target/i386/pr111820-1.c
new file mode 100644
index 00000000000..50e960c39d4
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr111820-1.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -mavx2 -fno-tree-vrp -Wno-aggressive-loop-optimizations -fdump-tree-vect-details" } */
+/* { dg-final { scan-tree-dump "Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big" "vect" } } */
+
+int r;
+int r_0;
+
+void f1 (void)
+{
+  int n = 0;
+  while (-- n)
+    {
+      r_0 += r;
+      r  *= 3;
+    }
+}
diff --git a/gcc/testsuite/gcc.target/i386/pr111820-2.c b/gcc/testsuite/gcc.target/i386/pr111820-2.c
new file mode 100644
index 00000000000..dbeceb228c3
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr111820-2.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-aggressive-loop-optimizations" } */
+/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
+
+int r;
+int r_0;
+
+void f (void)
+{
+  int n = 0;
+  while (-- n)
+    {
+      r_0 += r ;
+      r  *= 2;
+    }
+}
diff --git a/gcc/testsuite/gcc.target/i386/pr111820-3.c b/gcc/testsuite/gcc.target/i386/pr111820-3.c
new file mode 100644
index 00000000000..b778f517663
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr111820-3.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-aggressive-loop-optimizations" } */
+/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
+
+int r;
+int r_0;
+
+void f (void)
+{
+  int n = 14;
+  while (-- n)
+    {
+      r_0 += r ;
+      r  *= 3;
+    }
+}
diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc
index 2608c286e5d..a530088b61d 100644
--- a/gcc/tree-vect-loop-manip.cc
+++ b/gcc/tree-vect-loop-manip.cc
@@ -1783,8 +1783,10 @@ iv_phi_p (stmt_vec_info stmt_info)
 /* Return true if vectorizer can peel for nonlinear iv.  */
 static bool
 vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
-			      enum vect_induction_op_type induction_type)
+			      stmt_vec_info stmt_info)
 {
+  enum vect_induction_op_type induction_type
+    = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (stmt_info);
   tree niters_skip;
   /* Init_expr will be update by vect_update_ivs_after_vectorizer,
      if niters or vf is unkown:
@@ -1805,11 +1807,31 @@ vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
       return false;
     }
 
+  /* Avoid compile time hog on vect_peel_nonlinear_iv_init.  */
+  if (induction_type == vect_step_op_mul)
+    {
+      tree step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info);
+      tree type = TREE_TYPE (step_expr);
+
+      if (wi::exact_log2 (wi::to_wide (step_expr)) == -1
+	  && LOOP_VINFO_INT_NITERS(loop_vinfo) >= TYPE_PRECISION (type))
+	{
+	  if (dump_enabled_p ())
+	    dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+			     "Avoid compile time hog on"
+			     " vect_peel_nonlinear_iv_init"
+			     " for nonlinear induction vec_step_op_mul"
+			     " when iteration count is too big.\n");
+	  return false;
+	}
+    }
+
   /* Also doens't support peel for neg when niter is variable.
      ??? generate something like niter_expr & 1 ? init_expr : -init_expr?  */
   niters_skip = LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo);
   if ((niters_skip != NULL_TREE
-       && TREE_CODE (niters_skip) != INTEGER_CST)
+       && (TREE_CODE (niters_skip) != INTEGER_CST
+	   || (HOST_WIDE_INT) TREE_INT_CST_LOW (niters_skip) < 0))
       || (!vect_use_loop_mask_for_alignment_p (loop_vinfo)
 	  && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0))
     {
@@ -1870,7 +1892,7 @@ vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
       induction_type = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (phi_info);
       if (induction_type != vect_step_op_add)
 	{
-	  if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, induction_type))
+	  if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, phi_info))
 	    return false;
 
 	  continue;
diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
index 89bdcaa0910..f0dbba50786 100644
--- a/gcc/tree-vect-loop.cc
+++ b/gcc/tree-vect-loop.cc
@@ -9134,11 +9134,35 @@ vect_peel_nonlinear_iv_init (gimple_seq* stmts, tree init_expr,
 	init_expr = gimple_convert (stmts, utype, init_expr);
 	unsigned skipn = TREE_INT_CST_LOW (skip_niters);
 	wide_int begin = wi::to_wide (step_expr);
-	for (unsigned i = 0; i != skipn - 1; i++)
-	  begin = wi::mul (begin, wi::to_wide (step_expr));
-	tree mult_expr = wide_int_to_tree (utype, begin);
-	init_expr = gimple_build (stmts, MULT_EXPR, utype, init_expr, mult_expr);
-	init_expr = gimple_convert (stmts, type, init_expr);
+	int pow2_step = wi::exact_log2 (begin);
+	/* Optimize init_expr * pow (step_expr, skipn) to
+	   init_expr << (log2 (step_expr) * skipn).  */
+	if (pow2_step != -1)
+	  {
+	    if (skipn >= TYPE_PRECISION (type)
+		|| skipn > (UINT_MAX / (unsigned) pow2_step)
+		|| skipn * (unsigned) pow2_step >= TYPE_PRECISION (type))
+		init_expr = build_zero_cst (type);
+	    else
+	      {
+		tree lshc = build_int_cst (utype, skipn * (unsigned) pow2_step);
+		init_expr = gimple_build (stmts, LSHIFT_EXPR, utype,
+					  init_expr, lshc);
+	      }
+	  }
+	/* Any better way for init_expr * pow (step_expr, skipn)???.  */
+	else
+	  {
+	    gcc_assert (skipn < TYPE_PRECISION (type));
+	    auto_mpz base, exp;
+	    wi::to_mpz (begin, base, TYPE_SIGN (type));
+	    mpz_pow_ui (exp, base, skipn);
+	    begin = wi::from_mpz (type, exp, TYPE_SIGN (type));
+	    tree mult_expr = wide_int_to_tree (utype, begin);
+	    init_expr = gimple_build (stmts, MULT_EXPR, utype,
+				      init_expr, mult_expr);
+	  }
+	  init_expr = gimple_convert (stmts, type, init_expr);
       }
       break;
 
-- 
2.31.1

Re: [PATCH] Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big.

[Richard Biener]

On Thu, Oct 19, 2023 at 8:16 AM liuhongt <hongtao.liu@intel.com> wrote:
>
> >So the bugs were not fixed without this hunk?  IIRC in the audit
> >trail we concluded the value is always positive ... (but of course
> >a large unsigned value can appear negative if you test it this way?)
> No, I added this incase in the future there's negative skip_niters as
> you mentioned in the PR, it's just defensive programming.
>
> >I think you can use one of the mpz_pow* functions and
> >wi::to_mpz/from_mpz for this.  See tree-ssa-loop-niter.cc for the
> >most heavy user of mpz (but not pow I think).
> Changed.
>
> Bootstrapped and regtested on x86_64-pc-linux-gnu{-m32,}.
> Ok for trunk.
>
> There's loop in vect_peel_nonlinear_iv_init to get init_expr *
> pow (step_expr, skip_niters). When skipn_iters is too big, compile time
> hogs. To avoid that, optimize init_expr * pow (step_expr, skip_niters) to
> init_expr << (exact_log2 (step_expr) * skip_niters) when step_expr is
> pow of 2, otherwise give up vectorization when skip_niters >=
> TYPE_PRECISION (TREE_TYPE (init_expr)).
>
> Also give up vectorization when niters_skip is negative which will be
> used for fully masked loop.
>
> gcc/ChangeLog:
>
>         PR tree-optimization/111820
>         PR tree-optimization/111833
>         * tree-vect-loop-manip.cc (vect_can_peel_nonlinear_iv_p): Give
>         up vectorization for nonlinear iv vect_step_op_mul when
>         step_expr is not exact_log2 and niters is greater than
>         TYPE_PRECISION (TREE_TYPE (step_expr)). Also don't vectorize
>         for nagative niters_skip which will be used by fully masked
>         loop.
>         (vect_can_advance_ivs_p): Pass whole phi_info to
>         vect_can_peel_nonlinear_iv_p.
>         * tree-vect-loop.cc (vect_peel_nonlinear_iv_init): Optimize
>         init_expr * pow (step_expr, skipn) to init_expr
>         << (log2 (step_expr) * skipn) when step_expr is exact_log2.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.target/i386/pr111820-1.c: New test.
>         * gcc.target/i386/pr111820-2.c: New test.
>         * gcc.target/i386/pr111820-3.c: New test.
>         * gcc.target/i386/pr103144-mul-1.c: Adjust testcase.
>         * gcc.target/i386/pr103144-mul-2.c: Adjust testcase.
> ---
>  .../gcc.target/i386/pr103144-mul-1.c          |  8 ++---
>  .../gcc.target/i386/pr103144-mul-2.c          |  8 ++---
>  gcc/testsuite/gcc.target/i386/pr111820-1.c    | 16 +++++++++
>  gcc/testsuite/gcc.target/i386/pr111820-2.c    | 16 +++++++++
>  gcc/testsuite/gcc.target/i386/pr111820-3.c    | 16 +++++++++
>  gcc/tree-vect-loop-manip.cc                   | 28 +++++++++++++--
>  gcc/tree-vect-loop.cc                         | 34 ++++++++++++++++---
>  7 files changed, 110 insertions(+), 16 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-1.c
>  create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-2.c
>  create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-3.c
>
> diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
> index 640c34fd959..913d7737dcd 100644
> --- a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
> +++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
> @@ -11,7 +11,7 @@ foo_mul (int* a, int b)
>    for (int i = 0; i != N; i++)
>      {
>        a[i] = b;
> -      b *= 3;
> +      b *= 4;
>      }
>  }
>
> @@ -23,7 +23,7 @@ foo_mul_const (int* a)
>    for (int i = 0; i != N; i++)
>      {
>        a[i] = b;
> -      b *= 3;
> +      b *= 4;
>      }
>  }
>
> @@ -34,7 +34,7 @@ foo_mul_peel (int* a, int b)
>    for (int i = 0; i != 39; i++)
>      {
>        a[i] = b;
> -      b *= 3;
> +      b *= 4;
>      }
>  }
>
> @@ -46,6 +46,6 @@ foo_mul_peel_const (int* a)
>    for (int i = 0; i != 39; i++)
>      {
>        a[i] = b;
> -      b *= 3;
> +      b *= 4;
>      }
>  }
> diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
> index 39fdea3a69d..b2ff186e335 100644
> --- a/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
> +++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
> @@ -16,12 +16,12 @@ avx2_test (void)
>
>    __builtin_memset (epi32_exp, 0, N * sizeof (int));
>    int b = 8;
> -  v8si init = __extension__(v8si) { b, b * 3, b * 9, b * 27, b * 81, b * 243, b * 729, b * 2187 };
> +  v8si init = __extension__(v8si) { b, b * 4, b * 16, b * 64, b * 256, b * 1024, b * 4096, b * 16384 };
>
>    for (int i = 0; i != N / 8; i++)
>      {
>        memcpy (epi32_exp + i * 8, &init, 32);
> -      init *= 6561;
> +      init *= 65536;
>      }
>
>    foo_mul (epi32_dst, b);
> @@ -32,11 +32,11 @@ avx2_test (void)
>    if (__builtin_memcmp (epi32_dst, epi32_exp, 39 * 4) != 0)
>      __builtin_abort ();
>
> -  init = __extension__(v8si) { 1, 3, 9, 27, 81, 243, 729, 2187 };
> +  init = __extension__(v8si) { 1, 4, 16, 64, 256, 1024, 4096, 16384 };
>    for (int i = 0; i != N / 8; i++)
>      {
>        memcpy (epi32_exp + i * 8, &init, 32);
> -      init *= 6561;
> +      init *= 65536;
>      }
>
>    foo_mul_const (epi32_dst);
> diff --git a/gcc/testsuite/gcc.target/i386/pr111820-1.c b/gcc/testsuite/gcc.target/i386/pr111820-1.c
> new file mode 100644
> index 00000000000..50e960c39d4
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/i386/pr111820-1.c
> @@ -0,0 +1,16 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -mavx2 -fno-tree-vrp -Wno-aggressive-loop-optimizations -fdump-tree-vect-details" } */
> +/* { dg-final { scan-tree-dump "Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big" "vect" } } */
> +
> +int r;
> +int r_0;
> +
> +void f1 (void)
> +{
> +  int n = 0;
> +  while (-- n)
> +    {
> +      r_0 += r;
> +      r  *= 3;
> +    }
> +}
> diff --git a/gcc/testsuite/gcc.target/i386/pr111820-2.c b/gcc/testsuite/gcc.target/i386/pr111820-2.c
> new file mode 100644
> index 00000000000..dbeceb228c3
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/i386/pr111820-2.c
> @@ -0,0 +1,16 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-aggressive-loop-optimizations" } */
> +/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
> +
> +int r;
> +int r_0;
> +
> +void f (void)
> +{
> +  int n = 0;
> +  while (-- n)
> +    {
> +      r_0 += r ;
> +      r  *= 2;
> +    }
> +}
> diff --git a/gcc/testsuite/gcc.target/i386/pr111820-3.c b/gcc/testsuite/gcc.target/i386/pr111820-3.c
> new file mode 100644
> index 00000000000..b778f517663
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/i386/pr111820-3.c
> @@ -0,0 +1,16 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-aggressive-loop-optimizations" } */
> +/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
> +
> +int r;
> +int r_0;
> +
> +void f (void)
> +{
> +  int n = 14;
> +  while (-- n)
> +    {
> +      r_0 += r ;
> +      r  *= 3;
> +    }
> +}
> diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc
> index 2608c286e5d..a530088b61d 100644
> --- a/gcc/tree-vect-loop-manip.cc
> +++ b/gcc/tree-vect-loop-manip.cc
> @@ -1783,8 +1783,10 @@ iv_phi_p (stmt_vec_info stmt_info)
>  /* Return true if vectorizer can peel for nonlinear iv.  */
>  static bool
>  vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
> -                             enum vect_induction_op_type induction_type)
> +                             stmt_vec_info stmt_info)
>  {
> +  enum vect_induction_op_type induction_type
> +    = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (stmt_info);
>    tree niters_skip;
>    /* Init_expr will be update by vect_update_ivs_after_vectorizer,
>       if niters or vf is unkown:
> @@ -1805,11 +1807,31 @@ vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
>        return false;
>      }
>
> +  /* Avoid compile time hog on vect_peel_nonlinear_iv_init.  */
> +  if (induction_type == vect_step_op_mul)
> +    {
> +      tree step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info);
> +      tree type = TREE_TYPE (step_expr);
> +
> +      if (wi::exact_log2 (wi::to_wide (step_expr)) == -1
> +         && LOOP_VINFO_INT_NITERS(loop_vinfo) >= TYPE_PRECISION (type))

So with pow being available this limit shouldn't be necessary any more and
the testcase adjustment can be avoided?

> +       {
> +         if (dump_enabled_p ())
> +           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> +                            "Avoid compile time hog on"
> +                            " vect_peel_nonlinear_iv_init"
> +                            " for nonlinear induction vec_step_op_mul"
> +                            " when iteration count is too big.\n");
> +         return false;
> +       }
> +    }
> +
>    /* Also doens't support peel for neg when niter is variable.
>       ??? generate something like niter_expr & 1 ? init_expr : -init_expr?  */
>    niters_skip = LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo);
>    if ((niters_skip != NULL_TREE
> -       && TREE_CODE (niters_skip) != INTEGER_CST)
> +       && (TREE_CODE (niters_skip) != INTEGER_CST
> +          || (HOST_WIDE_INT) TREE_INT_CST_LOW (niters_skip) < 0))
>        || (!vect_use_loop_mask_for_alignment_p (loop_vinfo)
>           && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0))
>      {
> @@ -1870,7 +1892,7 @@ vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
>        induction_type = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (phi_info);
>        if (induction_type != vect_step_op_add)
>         {
> -         if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, induction_type))
> +         if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, phi_info))
>             return false;
>
>           continue;
> diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
> index 89bdcaa0910..f0dbba50786 100644
> --- a/gcc/tree-vect-loop.cc
> +++ b/gcc/tree-vect-loop.cc
> @@ -9134,11 +9134,35 @@ vect_peel_nonlinear_iv_init (gimple_seq* stmts, tree init_expr,
>         init_expr = gimple_convert (stmts, utype, init_expr);
>         unsigned skipn = TREE_INT_CST_LOW (skip_niters);
>         wide_int begin = wi::to_wide (step_expr);
> -       for (unsigned i = 0; i != skipn - 1; i++)
> -         begin = wi::mul (begin, wi::to_wide (step_expr));
> -       tree mult_expr = wide_int_to_tree (utype, begin);
> -       init_expr = gimple_build (stmts, MULT_EXPR, utype, init_expr, mult_expr);
> -       init_expr = gimple_convert (stmts, type, init_expr);
> +       int pow2_step = wi::exact_log2 (begin);
> +       /* Optimize init_expr * pow (step_expr, skipn) to
> +          init_expr << (log2 (step_expr) * skipn).  */
> +       if (pow2_step != -1)

and to avoid undefined behavior with too large shift just go the gmp
way unconditionally.

> +         {
> +           if (skipn >= TYPE_PRECISION (type)
> +               || skipn > (UINT_MAX / (unsigned) pow2_step)
> +               || skipn * (unsigned) pow2_step >= TYPE_PRECISION (type))
> +               init_expr = build_zero_cst (type);
> +           else
> +             {
> +               tree lshc = build_int_cst (utype, skipn * (unsigned) pow2_step);
> +               init_expr = gimple_build (stmts, LSHIFT_EXPR, utype,
> +                                         init_expr, lshc);
> +             }
> +         }
> +       /* Any better way for init_expr * pow (step_expr, skipn)???.  */

this comment is now resolved I think.

> +       else
> +         {
> +           gcc_assert (skipn < TYPE_PRECISION (type));
> +           auto_mpz base, exp;
> +           wi::to_mpz (begin, base, TYPE_SIGN (type));
> +           mpz_pow_ui (exp, base, skipn);

mpz_pow_ui uses unsigned long while i think we constrain known niters
to uint64 - so I suggest to use mpz_powm instead (limiting to a possibly
host specific limit - unsigned long - is unfortunately a no-go).

Otherwise looks good to me.

Thanks,
Richard.

> +           begin = wi::from_mpz (type, exp, TYPE_SIGN (type));
> +           tree mult_expr = wide_int_to_tree (utype, begin);
> +           init_expr = gimple_build (stmts, MULT_EXPR, utype,
> +                                     init_expr, mult_expr);
> +         }
> +         init_expr = gimple_convert (stmts, type, init_expr);
>        }
>        break;
>
> --
> 2.31.1
>

[PATCH] Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big.

[liuhongt]

>So with pow being available this limit shouldn't be necessary any more and
>the testcase adjustment can be avoided?
I tries, compile time still hogs on mpz_powm(3, INT_MAX), so i'll just
keep this.

>and to avoid undefined behavior with too large shift just go the gmp
>way unconditionally.
Changed.

>this comment is now resolved I think.
Removed.

>mpz_pow_ui uses unsigned long while i think we constrain known niters
>to uint64 - so I suggest to use mpz_powm instead (limiting to a possibly
>host specific limit - unsigned long - is unfortunately a no-go).
Changed.

There's loop in vect_peel_nonlinear_iv_init to get init_expr *
pow (step_expr, skip_niters). When skipn_iters is too big, compile time
hogs. To avoid that, optimize init_expr * pow (step_expr, skip_niters) to
init_expr << (exact_log2 (step_expr) * skip_niters) when step_expr is
pow of 2, otherwise give up vectorization when skip_niters >=
TYPE_PRECISION (TREE_TYPE (init_expr)).

Also give up vectorization when niters_skip is negative which will be
used for fully masked loop.

Bootstrapped and regtested on x86_64-linux-gnu{-m32,}.
Ok for trunk.

gcc/ChangeLog:

	PR tree-optimization/111820
	PR tree-optimization/111833
	* tree-vect-loop-manip.cc (vect_can_peel_nonlinear_iv_p): Give
	up vectorization for nonlinear iv vect_step_op_mul when
	step_expr is not exact_log2 and niters is greater than
	TYPE_PRECISION (TREE_TYPE (step_expr)). Also don't vectorize
	for nagative niters_skip which will be used by fully masked
	loop.
	(vect_can_advance_ivs_p): Pass whole phi_info to
	vect_can_peel_nonlinear_iv_p.
	* tree-vect-loop.cc (vect_peel_nonlinear_iv_init): Optimize
	init_expr * pow (step_expr, skipn) to init_expr
	<< (log2 (step_expr) * skipn) when step_expr is exact_log2.

gcc/testsuite/ChangeLog:

	* gcc.target/i386/pr111820-1.c: New test.
	* gcc.target/i386/pr111820-2.c: New test.
	* gcc.target/i386/pr111820-3.c: New test.
	* gcc.target/i386/pr103144-mul-1.c: Adjust testcase.
	* gcc.target/i386/pr103144-mul-2.c: Adjust testcase.
---
 .../gcc.target/i386/pr103144-mul-1.c          |  8 +++---
 .../gcc.target/i386/pr103144-mul-2.c          |  8 +++---
 gcc/testsuite/gcc.target/i386/pr111820-1.c    | 16 +++++++++++
 gcc/testsuite/gcc.target/i386/pr111820-2.c    | 16 +++++++++++
 gcc/testsuite/gcc.target/i386/pr111820-3.c    | 16 +++++++++++
 gcc/tree-vect-loop-manip.cc                   | 28 +++++++++++++++++--
 gcc/tree-vect-loop.cc                         | 13 ++++++---
 7 files changed, 90 insertions(+), 15 deletions(-)
 create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-1.c
 create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-2.c
 create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-3.c

diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
index 640c34fd959..913d7737dcd 100644
--- a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
+++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
@@ -11,7 +11,7 @@ foo_mul (int* a, int b)
   for (int i = 0; i != N; i++)
     {
       a[i] = b;
-      b *= 3;
+      b *= 4;
     }
 }
 
@@ -23,7 +23,7 @@ foo_mul_const (int* a)
   for (int i = 0; i != N; i++)
     {
       a[i] = b;
-      b *= 3;
+      b *= 4;
     }
 }
 
@@ -34,7 +34,7 @@ foo_mul_peel (int* a, int b)
   for (int i = 0; i != 39; i++)
     {
       a[i] = b;
-      b *= 3;
+      b *= 4;
     }
 }
 
@@ -46,6 +46,6 @@ foo_mul_peel_const (int* a)
   for (int i = 0; i != 39; i++)
     {
       a[i] = b;
-      b *= 3;
+      b *= 4;
     }
 }
diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
index 39fdea3a69d..b2ff186e335 100644
--- a/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
+++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
@@ -16,12 +16,12 @@ avx2_test (void)
 
   __builtin_memset (epi32_exp, 0, N * sizeof (int));
   int b = 8;
-  v8si init = __extension__(v8si) { b, b * 3, b * 9, b * 27, b * 81, b * 243, b * 729, b * 2187 };
+  v8si init = __extension__(v8si) { b, b * 4, b * 16, b * 64, b * 256, b * 1024, b * 4096, b * 16384 };
 
   for (int i = 0; i != N / 8; i++)
     {
       memcpy (epi32_exp + i * 8, &init, 32);
-      init *= 6561;
+      init *= 65536;
     }
 
   foo_mul (epi32_dst, b);
@@ -32,11 +32,11 @@ avx2_test (void)
   if (__builtin_memcmp (epi32_dst, epi32_exp, 39 * 4) != 0)
     __builtin_abort ();
 
-  init = __extension__(v8si) { 1, 3, 9, 27, 81, 243, 729, 2187 };
+  init = __extension__(v8si) { 1, 4, 16, 64, 256, 1024, 4096, 16384 };
   for (int i = 0; i != N / 8; i++)
     {
       memcpy (epi32_exp + i * 8, &init, 32);
-      init *= 6561;
+      init *= 65536;
     }
 
   foo_mul_const (epi32_dst);
diff --git a/gcc/testsuite/gcc.target/i386/pr111820-1.c b/gcc/testsuite/gcc.target/i386/pr111820-1.c
new file mode 100644
index 00000000000..50e960c39d4
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr111820-1.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -mavx2 -fno-tree-vrp -Wno-aggressive-loop-optimizations -fdump-tree-vect-details" } */
+/* { dg-final { scan-tree-dump "Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big" "vect" } } */
+
+int r;
+int r_0;
+
+void f1 (void)
+{
+  int n = 0;
+  while (-- n)
+    {
+      r_0 += r;
+      r  *= 3;
+    }
+}
diff --git a/gcc/testsuite/gcc.target/i386/pr111820-2.c b/gcc/testsuite/gcc.target/i386/pr111820-2.c
new file mode 100644
index 00000000000..dbeceb228c3
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr111820-2.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-aggressive-loop-optimizations" } */
+/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
+
+int r;
+int r_0;
+
+void f (void)
+{
+  int n = 0;
+  while (-- n)
+    {
+      r_0 += r ;
+      r  *= 2;
+    }
+}
diff --git a/gcc/testsuite/gcc.target/i386/pr111820-3.c b/gcc/testsuite/gcc.target/i386/pr111820-3.c
new file mode 100644
index 00000000000..b778f517663
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr111820-3.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-aggressive-loop-optimizations" } */
+/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
+
+int r;
+int r_0;
+
+void f (void)
+{
+  int n = 14;
+  while (-- n)
+    {
+      r_0 += r ;
+      r  *= 3;
+    }
+}
diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc
index 2608c286e5d..a530088b61d 100644
--- a/gcc/tree-vect-loop-manip.cc
+++ b/gcc/tree-vect-loop-manip.cc
@@ -1783,8 +1783,10 @@ iv_phi_p (stmt_vec_info stmt_info)
 /* Return true if vectorizer can peel for nonlinear iv.  */
 static bool
 vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
-			      enum vect_induction_op_type induction_type)
+			      stmt_vec_info stmt_info)
 {
+  enum vect_induction_op_type induction_type
+    = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (stmt_info);
   tree niters_skip;
   /* Init_expr will be update by vect_update_ivs_after_vectorizer,
      if niters or vf is unkown:
@@ -1805,11 +1807,31 @@ vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
       return false;
     }
 
+  /* Avoid compile time hog on vect_peel_nonlinear_iv_init.  */
+  if (induction_type == vect_step_op_mul)
+    {
+      tree step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info);
+      tree type = TREE_TYPE (step_expr);
+
+      if (wi::exact_log2 (wi::to_wide (step_expr)) == -1
+	  && LOOP_VINFO_INT_NITERS(loop_vinfo) >= TYPE_PRECISION (type))
+	{
+	  if (dump_enabled_p ())
+	    dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+			     "Avoid compile time hog on"
+			     " vect_peel_nonlinear_iv_init"
+			     " for nonlinear induction vec_step_op_mul"
+			     " when iteration count is too big.\n");
+	  return false;
+	}
+    }
+
   /* Also doens't support peel for neg when niter is variable.
      ??? generate something like niter_expr & 1 ? init_expr : -init_expr?  */
   niters_skip = LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo);
   if ((niters_skip != NULL_TREE
-       && TREE_CODE (niters_skip) != INTEGER_CST)
+       && (TREE_CODE (niters_skip) != INTEGER_CST
+	   || (HOST_WIDE_INT) TREE_INT_CST_LOW (niters_skip) < 0))
       || (!vect_use_loop_mask_for_alignment_p (loop_vinfo)
 	  && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0))
     {
@@ -1870,7 +1892,7 @@ vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
       induction_type = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (phi_info);
       if (induction_type != vect_step_op_add)
 	{
-	  if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, induction_type))
+	  if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, phi_info))
 	    return false;
 
 	  continue;
diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
index 89bdcaa0910..7a6bbff0c8f 100644
--- a/gcc/tree-vect-loop.cc
+++ b/gcc/tree-vect-loop.cc
@@ -9132,12 +9132,17 @@ vect_peel_nonlinear_iv_init (gimple_seq* stmts, tree init_expr,
       {
 	tree utype = unsigned_type_for (type);
 	init_expr = gimple_convert (stmts, utype, init_expr);
-	unsigned skipn = TREE_INT_CST_LOW (skip_niters);
+	wide_int skipn = wi::to_wide (skip_niters);
 	wide_int begin = wi::to_wide (step_expr);
-	for (unsigned i = 0; i != skipn - 1; i++)
-	  begin = wi::mul (begin, wi::to_wide (step_expr));
+	auto_mpz base, exp, mod, res;
+	wi::to_mpz (begin, base, TYPE_SIGN (type));
+	wi::to_mpz (skipn, exp, UNSIGNED);
+	mpz_ui_pow_ui (mod, 2, TYPE_PRECISION (type));
+	mpz_powm (res, base, exp, mod);
+	begin = wi::from_mpz (type, res, TYPE_SIGN (type));
 	tree mult_expr = wide_int_to_tree (utype, begin);
-	init_expr = gimple_build (stmts, MULT_EXPR, utype, init_expr, mult_expr);
+	init_expr = gimple_build (stmts, MULT_EXPR, utype,
+				  init_expr, mult_expr);
 	init_expr = gimple_convert (stmts, type, init_expr);
       }
       break;
-- 
2.31.1

Re: [PATCH] Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big.

[Richard Biener]

On Fri, Oct 20, 2023 at 4:21 AM liuhongt <hongtao.liu@intel.com> wrote:
>
> >So with pow being available this limit shouldn't be necessary any more and
> >the testcase adjustment can be avoided?
> I tries, compile time still hogs on mpz_powm(3, INT_MAX), so i'll just
> keep this.

Doh :/  Maybe it's possible to limit the output precision for mpz computes
somehow?  I suspect we're really computing the very large resulting number
here ... unfortunately I don't know GMP enough to tell.

> >and to avoid undefined behavior with too large shift just go the gmp
> >way unconditionally.
> Changed.
>
> >this comment is now resolved I think.
> Removed.
>
> >mpz_pow_ui uses unsigned long while i think we constrain known niters
> >to uint64 - so I suggest to use mpz_powm instead (limiting to a possibly
> >host specific limit - unsigned long - is unfortunately a no-go).
> Changed.
>
> There's loop in vect_peel_nonlinear_iv_init to get init_expr *
> pow (step_expr, skip_niters). When skipn_iters is too big, compile time
> hogs. To avoid that, optimize init_expr * pow (step_expr, skip_niters) to
> init_expr << (exact_log2 (step_expr) * skip_niters) when step_expr is
> pow of 2, otherwise give up vectorization when skip_niters >=
> TYPE_PRECISION (TREE_TYPE (init_expr)).
>
> Also give up vectorization when niters_skip is negative which will be
> used for fully masked loop.
>
> Bootstrapped and regtested on x86_64-linux-gnu{-m32,}.
> Ok for trunk.

OK.

Thanks,
Richard.

> gcc/ChangeLog:
>
>         PR tree-optimization/111820
>         PR tree-optimization/111833
>         * tree-vect-loop-manip.cc (vect_can_peel_nonlinear_iv_p): Give
>         up vectorization for nonlinear iv vect_step_op_mul when
>         step_expr is not exact_log2 and niters is greater than
>         TYPE_PRECISION (TREE_TYPE (step_expr)). Also don't vectorize
>         for nagative niters_skip which will be used by fully masked
>         loop.
>         (vect_can_advance_ivs_p): Pass whole phi_info to
>         vect_can_peel_nonlinear_iv_p.
>         * tree-vect-loop.cc (vect_peel_nonlinear_iv_init): Optimize
>         init_expr * pow (step_expr, skipn) to init_expr
>         << (log2 (step_expr) * skipn) when step_expr is exact_log2.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.target/i386/pr111820-1.c: New test.
>         * gcc.target/i386/pr111820-2.c: New test.
>         * gcc.target/i386/pr111820-3.c: New test.
>         * gcc.target/i386/pr103144-mul-1.c: Adjust testcase.
>         * gcc.target/i386/pr103144-mul-2.c: Adjust testcase.
> ---
>  .../gcc.target/i386/pr103144-mul-1.c          |  8 +++---
>  .../gcc.target/i386/pr103144-mul-2.c          |  8 +++---
>  gcc/testsuite/gcc.target/i386/pr111820-1.c    | 16 +++++++++++
>  gcc/testsuite/gcc.target/i386/pr111820-2.c    | 16 +++++++++++
>  gcc/testsuite/gcc.target/i386/pr111820-3.c    | 16 +++++++++++
>  gcc/tree-vect-loop-manip.cc                   | 28 +++++++++++++++++--
>  gcc/tree-vect-loop.cc                         | 13 ++++++---
>  7 files changed, 90 insertions(+), 15 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-1.c
>  create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-2.c
>  create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-3.c
>
> diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
> index 640c34fd959..913d7737dcd 100644
> --- a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
> +++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
> @@ -11,7 +11,7 @@ foo_mul (int* a, int b)
>    for (int i = 0; i != N; i++)
>      {
>        a[i] = b;
> -      b *= 3;
> +      b *= 4;
>      }
>  }
>
> @@ -23,7 +23,7 @@ foo_mul_const (int* a)
>    for (int i = 0; i != N; i++)
>      {
>        a[i] = b;
> -      b *= 3;
> +      b *= 4;
>      }
>  }
>
> @@ -34,7 +34,7 @@ foo_mul_peel (int* a, int b)
>    for (int i = 0; i != 39; i++)
>      {
>        a[i] = b;
> -      b *= 3;
> +      b *= 4;
>      }
>  }
>
> @@ -46,6 +46,6 @@ foo_mul_peel_const (int* a)
>    for (int i = 0; i != 39; i++)
>      {
>        a[i] = b;
> -      b *= 3;
> +      b *= 4;
>      }
>  }
> diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
> index 39fdea3a69d..b2ff186e335 100644
> --- a/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
> +++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
> @@ -16,12 +16,12 @@ avx2_test (void)
>
>    __builtin_memset (epi32_exp, 0, N * sizeof (int));
>    int b = 8;
> -  v8si init = __extension__(v8si) { b, b * 3, b * 9, b * 27, b * 81, b * 243, b * 729, b * 2187 };
> +  v8si init = __extension__(v8si) { b, b * 4, b * 16, b * 64, b * 256, b * 1024, b * 4096, b * 16384 };
>
>    for (int i = 0; i != N / 8; i++)
>      {
>        memcpy (epi32_exp + i * 8, &init, 32);
> -      init *= 6561;
> +      init *= 65536;
>      }
>
>    foo_mul (epi32_dst, b);
> @@ -32,11 +32,11 @@ avx2_test (void)
>    if (__builtin_memcmp (epi32_dst, epi32_exp, 39 * 4) != 0)
>      __builtin_abort ();
>
> -  init = __extension__(v8si) { 1, 3, 9, 27, 81, 243, 729, 2187 };
> +  init = __extension__(v8si) { 1, 4, 16, 64, 256, 1024, 4096, 16384 };
>    for (int i = 0; i != N / 8; i++)
>      {
>        memcpy (epi32_exp + i * 8, &init, 32);
> -      init *= 6561;
> +      init *= 65536;
>      }
>
>    foo_mul_const (epi32_dst);
> diff --git a/gcc/testsuite/gcc.target/i386/pr111820-1.c b/gcc/testsuite/gcc.target/i386/pr111820-1.c
> new file mode 100644
> index 00000000000..50e960c39d4
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/i386/pr111820-1.c
> @@ -0,0 +1,16 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -mavx2 -fno-tree-vrp -Wno-aggressive-loop-optimizations -fdump-tree-vect-details" } */
> +/* { dg-final { scan-tree-dump "Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big" "vect" } } */
> +
> +int r;
> +int r_0;
> +
> +void f1 (void)
> +{
> +  int n = 0;
> +  while (-- n)
> +    {
> +      r_0 += r;
> +      r  *= 3;
> +    }
> +}
> diff --git a/gcc/testsuite/gcc.target/i386/pr111820-2.c b/gcc/testsuite/gcc.target/i386/pr111820-2.c
> new file mode 100644
> index 00000000000..dbeceb228c3
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/i386/pr111820-2.c
> @@ -0,0 +1,16 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-aggressive-loop-optimizations" } */
> +/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
> +
> +int r;
> +int r_0;
> +
> +void f (void)
> +{
> +  int n = 0;
> +  while (-- n)
> +    {
> +      r_0 += r ;
> +      r  *= 2;
> +    }
> +}
> diff --git a/gcc/testsuite/gcc.target/i386/pr111820-3.c b/gcc/testsuite/gcc.target/i386/pr111820-3.c
> new file mode 100644
> index 00000000000..b778f517663
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/i386/pr111820-3.c
> @@ -0,0 +1,16 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-aggressive-loop-optimizations" } */
> +/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
> +
> +int r;
> +int r_0;
> +
> +void f (void)
> +{
> +  int n = 14;
> +  while (-- n)
> +    {
> +      r_0 += r ;
> +      r  *= 3;
> +    }
> +}
> diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc
> index 2608c286e5d..a530088b61d 100644
> --- a/gcc/tree-vect-loop-manip.cc
> +++ b/gcc/tree-vect-loop-manip.cc
> @@ -1783,8 +1783,10 @@ iv_phi_p (stmt_vec_info stmt_info)
>  /* Return true if vectorizer can peel for nonlinear iv.  */
>  static bool
>  vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
> -                             enum vect_induction_op_type induction_type)
> +                             stmt_vec_info stmt_info)
>  {
> +  enum vect_induction_op_type induction_type
> +    = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (stmt_info);
>    tree niters_skip;
>    /* Init_expr will be update by vect_update_ivs_after_vectorizer,
>       if niters or vf is unkown:
> @@ -1805,11 +1807,31 @@ vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
>        return false;
>      }
>
> +  /* Avoid compile time hog on vect_peel_nonlinear_iv_init.  */
> +  if (induction_type == vect_step_op_mul)
> +    {
> +      tree step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info);
> +      tree type = TREE_TYPE (step_expr);
> +
> +      if (wi::exact_log2 (wi::to_wide (step_expr)) == -1
> +         && LOOP_VINFO_INT_NITERS(loop_vinfo) >= TYPE_PRECISION (type))
> +       {
> +         if (dump_enabled_p ())
> +           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> +                            "Avoid compile time hog on"
> +                            " vect_peel_nonlinear_iv_init"
> +                            " for nonlinear induction vec_step_op_mul"
> +                            " when iteration count is too big.\n");
> +         return false;
> +       }
> +    }
> +
>    /* Also doens't support peel for neg when niter is variable.
>       ??? generate something like niter_expr & 1 ? init_expr : -init_expr?  */
>    niters_skip = LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo);
>    if ((niters_skip != NULL_TREE
> -       && TREE_CODE (niters_skip) != INTEGER_CST)
> +       && (TREE_CODE (niters_skip) != INTEGER_CST
> +          || (HOST_WIDE_INT) TREE_INT_CST_LOW (niters_skip) < 0))
>        || (!vect_use_loop_mask_for_alignment_p (loop_vinfo)
>           && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0))
>      {
> @@ -1870,7 +1892,7 @@ vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
>        induction_type = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (phi_info);
>        if (induction_type != vect_step_op_add)
>         {
> -         if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, induction_type))
> +         if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, phi_info))
>             return false;
>
>           continue;
> diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
> index 89bdcaa0910..7a6bbff0c8f 100644
> --- a/gcc/tree-vect-loop.cc
> +++ b/gcc/tree-vect-loop.cc
> @@ -9132,12 +9132,17 @@ vect_peel_nonlinear_iv_init (gimple_seq* stmts, tree init_expr,
>        {
>         tree utype = unsigned_type_for (type);
>         init_expr = gimple_convert (stmts, utype, init_expr);
> -       unsigned skipn = TREE_INT_CST_LOW (skip_niters);
> +       wide_int skipn = wi::to_wide (skip_niters);
>         wide_int begin = wi::to_wide (step_expr);
> -       for (unsigned i = 0; i != skipn - 1; i++)
> -         begin = wi::mul (begin, wi::to_wide (step_expr));
> +       auto_mpz base, exp, mod, res;
> +       wi::to_mpz (begin, base, TYPE_SIGN (type));
> +       wi::to_mpz (skipn, exp, UNSIGNED);
> +       mpz_ui_pow_ui (mod, 2, TYPE_PRECISION (type));
> +       mpz_powm (res, base, exp, mod);
> +       begin = wi::from_mpz (type, res, TYPE_SIGN (type));
>         tree mult_expr = wide_int_to_tree (utype, begin);
> -       init_expr = gimple_build (stmts, MULT_EXPR, utype, init_expr, mult_expr);
> +       init_expr = gimple_build (stmts, MULT_EXPR, utype,
> +                                 init_expr, mult_expr);
>         init_expr = gimple_convert (stmts, type, init_expr);
>        }
>        break;
> --
> 2.31.1
>

[PATCH GCC13 backport] Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big.

[liuhongt]

This is the backport patch for releases/gcc-13 branch, the original patch for main trunk
is at [1].
The only difference between this backport patch and [1] is GCC13 doesn't support auto_mpz,
So this patch manually use mpz_init/mpz_clear.

[1] https://gcc.gnu.org/pipermail/gcc-patches/2023-October/633661.html

Bootstrapped and regtested on x86_64-pc-linux-gnu{-m32,}
Ok for backport to releases/gcc-13?

There's loop in vect_peel_nonlinear_iv_init to get init_expr *
pow (step_expr, skip_niters). When skipn_iters is too big, compile time
hogs. To avoid that, optimize init_expr * pow (step_expr, skip_niters) to
init_expr << (exact_log2 (step_expr) * skip_niters) when step_expr is
pow of 2, otherwise give up vectorization when skip_niters >=
TYPE_PRECISION (TREE_TYPE (init_expr)).

Also give up vectorization when niters_skip is negative which will be
used for fully masked loop.

gcc/ChangeLog:

	PR tree-optimization/111820
	PR tree-optimization/111833
	* tree-vect-loop-manip.cc (vect_can_peel_nonlinear_iv_p): Give
	up vectorization for nonlinear iv vect_step_op_mul when
	step_expr is not exact_log2 and niters is greater than
	TYPE_PRECISION (TREE_TYPE (step_expr)). Also don't vectorize
	for nagative niters_skip which will be used by fully masked
	loop.
	(vect_can_advance_ivs_p): Pass whole phi_info to
	vect_can_peel_nonlinear_iv_p.
	* tree-vect-loop.cc (vect_peel_nonlinear_iv_init): Optimize
	init_expr * pow (step_expr, skipn) to init_expr
	<< (log2 (step_expr) * skipn) when step_expr is exact_log2.

gcc/testsuite/ChangeLog:

	* gcc.target/i386/pr111820-1.c: New test.
	* gcc.target/i386/pr111820-2.c: New test.
	* gcc.target/i386/pr111820-3.c: New test.
	* gcc.target/i386/pr103144-mul-1.c: Adjust testcase.
	* gcc.target/i386/pr103144-mul-2.c: Adjust testcase.
---
 .../gcc.target/i386/pr103144-mul-1.c          |  8 +++---
 .../gcc.target/i386/pr103144-mul-2.c          |  8 +++---
 gcc/testsuite/gcc.target/i386/pr111820-1.c    | 16 +++++++++++
 gcc/testsuite/gcc.target/i386/pr111820-2.c    | 16 +++++++++++
 gcc/testsuite/gcc.target/i386/pr111820-3.c    | 16 +++++++++++
 gcc/tree-vect-loop-manip.cc                   | 28 +++++++++++++++++--
 gcc/tree-vect-loop.cc                         | 21 +++++++++++---
 7 files changed, 98 insertions(+), 15 deletions(-)
 create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-1.c
 create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-2.c
 create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-3.c

diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
index 640c34fd959..913d7737dcd 100644
--- a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
+++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
@@ -11,7 +11,7 @@ foo_mul (int* a, int b)
   for (int i = 0; i != N; i++)
     {
       a[i] = b;
-      b *= 3;
+      b *= 4;
     }
 }
 
@@ -23,7 +23,7 @@ foo_mul_const (int* a)
   for (int i = 0; i != N; i++)
     {
       a[i] = b;
-      b *= 3;
+      b *= 4;
     }
 }
 
@@ -34,7 +34,7 @@ foo_mul_peel (int* a, int b)
   for (int i = 0; i != 39; i++)
     {
       a[i] = b;
-      b *= 3;
+      b *= 4;
     }
 }
 
@@ -46,6 +46,6 @@ foo_mul_peel_const (int* a)
   for (int i = 0; i != 39; i++)
     {
       a[i] = b;
-      b *= 3;
+      b *= 4;
     }
 }
diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
index 39fdea3a69d..b2ff186e335 100644
--- a/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
+++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
@@ -16,12 +16,12 @@ avx2_test (void)
 
   __builtin_memset (epi32_exp, 0, N * sizeof (int));
   int b = 8;
-  v8si init = __extension__(v8si) { b, b * 3, b * 9, b * 27, b * 81, b * 243, b * 729, b * 2187 };
+  v8si init = __extension__(v8si) { b, b * 4, b * 16, b * 64, b * 256, b * 1024, b * 4096, b * 16384 };
 
   for (int i = 0; i != N / 8; i++)
     {
       memcpy (epi32_exp + i * 8, &init, 32);
-      init *= 6561;
+      init *= 65536;
     }
 
   foo_mul (epi32_dst, b);
@@ -32,11 +32,11 @@ avx2_test (void)
   if (__builtin_memcmp (epi32_dst, epi32_exp, 39 * 4) != 0)
     __builtin_abort ();
 
-  init = __extension__(v8si) { 1, 3, 9, 27, 81, 243, 729, 2187 };
+  init = __extension__(v8si) { 1, 4, 16, 64, 256, 1024, 4096, 16384 };
   for (int i = 0; i != N / 8; i++)
     {
       memcpy (epi32_exp + i * 8, &init, 32);
-      init *= 6561;
+      init *= 65536;
     }
 
   foo_mul_const (epi32_dst);
diff --git a/gcc/testsuite/gcc.target/i386/pr111820-1.c b/gcc/testsuite/gcc.target/i386/pr111820-1.c
new file mode 100644
index 00000000000..50e960c39d4
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr111820-1.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -mavx2 -fno-tree-vrp -Wno-aggressive-loop-optimizations -fdump-tree-vect-details" } */
+/* { dg-final { scan-tree-dump "Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big" "vect" } } */
+
+int r;
+int r_0;
+
+void f1 (void)
+{
+  int n = 0;
+  while (-- n)
+    {
+      r_0 += r;
+      r  *= 3;
+    }
+}
diff --git a/gcc/testsuite/gcc.target/i386/pr111820-2.c b/gcc/testsuite/gcc.target/i386/pr111820-2.c
new file mode 100644
index 00000000000..dbeceb228c3
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr111820-2.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-aggressive-loop-optimizations" } */
+/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
+
+int r;
+int r_0;
+
+void f (void)
+{
+  int n = 0;
+  while (-- n)
+    {
+      r_0 += r ;
+      r  *= 2;
+    }
+}
diff --git a/gcc/testsuite/gcc.target/i386/pr111820-3.c b/gcc/testsuite/gcc.target/i386/pr111820-3.c
new file mode 100644
index 00000000000..b778f517663
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr111820-3.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-aggressive-loop-optimizations" } */
+/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
+
+int r;
+int r_0;
+
+void f (void)
+{
+  int n = 14;
+  while (-- n)
+    {
+      r_0 += r ;
+      r  *= 3;
+    }
+}
diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc
index f60fa50e8f4..767b19b15a1 100644
--- a/gcc/tree-vect-loop-manip.cc
+++ b/gcc/tree-vect-loop-manip.cc
@@ -1391,8 +1391,10 @@ iv_phi_p (stmt_vec_info stmt_info)
 /* Return true if vectorizer can peel for nonlinear iv.  */
 static bool
 vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
-			      enum vect_induction_op_type induction_type)
+			      stmt_vec_info stmt_info)
 {
+  enum vect_induction_op_type induction_type
+    = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (stmt_info);
   tree niters_skip;
   /* Init_expr will be update by vect_update_ivs_after_vectorizer,
      if niters or vf is unkown:
@@ -1413,11 +1415,31 @@ vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
       return false;
     }
 
+  /* Avoid compile time hog on vect_peel_nonlinear_iv_init.  */
+  if (induction_type == vect_step_op_mul)
+    {
+      tree step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info);
+      tree type = TREE_TYPE (step_expr);
+
+      if (wi::exact_log2 (wi::to_wide (step_expr)) == -1
+	  && LOOP_VINFO_INT_NITERS(loop_vinfo) >= TYPE_PRECISION (type))
+	{
+	  if (dump_enabled_p ())
+	    dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+			     "Avoid compile time hog on"
+			     " vect_peel_nonlinear_iv_init"
+			     " for nonlinear induction vec_step_op_mul"
+			     " when iteration count is too big.\n");
+	  return false;
+	}
+    }
+
   /* Also doens't support peel for neg when niter is variable.
      ??? generate something like niter_expr & 1 ? init_expr : -init_expr?  */
   niters_skip = LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo);
   if ((niters_skip != NULL_TREE
-       && TREE_CODE (niters_skip) != INTEGER_CST)
+       && (TREE_CODE (niters_skip) != INTEGER_CST
+	   || (HOST_WIDE_INT) TREE_INT_CST_LOW (niters_skip) < 0))
       || (!vect_use_loop_mask_for_alignment_p (loop_vinfo)
 	  && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0))
     {
@@ -1478,7 +1500,7 @@ vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
       induction_type = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (phi_info);
       if (induction_type != vect_step_op_add)
 	{
-	  if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, induction_type))
+	  if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, phi_info))
 	    return false;
 
 	  continue;
diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
index 92d2e0ef9be..2f098b96b1d 100644
--- a/gcc/tree-vect-loop.cc
+++ b/gcc/tree-vect-loop.cc
@@ -8728,13 +8728,26 @@ vect_peel_nonlinear_iv_init (gimple_seq* stmts, tree init_expr,
       {
 	tree utype = unsigned_type_for (type);
 	init_expr = gimple_convert (stmts, utype, init_expr);
-	unsigned skipn = TREE_INT_CST_LOW (skip_niters);
+	wide_int skipn = wi::to_wide (skip_niters);
 	wide_int begin = wi::to_wide (step_expr);
-	for (unsigned i = 0; i != skipn - 1; i++)
-	  begin = wi::mul (begin, wi::to_wide (step_expr));
+	mpz_t base, exp, mod, res;
+	mpz_init (base);
+	mpz_init (mod);
+	mpz_init (exp);
+	mpz_init (res);
+	wi::to_mpz (begin, base, TYPE_SIGN (type));
+	wi::to_mpz (skipn, exp, UNSIGNED);
+	mpz_ui_pow_ui (mod, 2, TYPE_PRECISION (type));
+	mpz_powm (res, base, exp, mod);
+	begin = wi::from_mpz (type, res, TYPE_SIGN (type));
 	tree mult_expr = wide_int_to_tree (utype, begin);
-	init_expr = gimple_build (stmts, MULT_EXPR, utype, init_expr, mult_expr);
+	init_expr = gimple_build (stmts, MULT_EXPR, utype,
+				  init_expr, mult_expr);
 	init_expr = gimple_convert (stmts, type, init_expr);
+	mpz_clear (base);
+	mpz_clear (mod);
+	mpz_clear (exp);
+	mpz_clear (res);
       }
       break;
 
-- 
2.31.1

Re: [PATCH GCC13 backport] Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big.

[Richard Biener]

> Am 24.10.2023 um 13:22 schrieb liuhongt <hongtao.liu@intel.com>:
> 
> This is the backport patch for releases/gcc-13 branch, the original patch for main trunk
> is at [1].
> The only difference between this backport patch and [1] is GCC13 doesn't support auto_mpz,
> So this patch manually use mpz_init/mpz_clear.
> 
> [1] https://gcc.gnu.org/pipermail/gcc-patches/2023-October/633661.html
> 
> Bootstrapped and regtested on x86_64-pc-linux-gnu{-m32,}
> Ok for backport to releases/gcc-13?

Ok.

Richard 

> There's loop in vect_peel_nonlinear_iv_init to get init_expr *
> pow (step_expr, skip_niters). When skipn_iters is too big, compile time
> hogs. To avoid that, optimize init_expr * pow (step_expr, skip_niters) to
> init_expr << (exact_log2 (step_expr) * skip_niters) when step_expr is
> pow of 2, otherwise give up vectorization when skip_niters >=
> TYPE_PRECISION (TREE_TYPE (init_expr)).
> 
> Also give up vectorization when niters_skip is negative which will be
> used for fully masked loop.
> 
> gcc/ChangeLog:
> 
>    PR tree-optimization/111820
>    PR tree-optimization/111833
>    * tree-vect-loop-manip.cc (vect_can_peel_nonlinear_iv_p): Give
>    up vectorization for nonlinear iv vect_step_op_mul when
>    step_expr is not exact_log2 and niters is greater than
>    TYPE_PRECISION (TREE_TYPE (step_expr)). Also don't vectorize
>    for nagative niters_skip which will be used by fully masked
>    loop.
>    (vect_can_advance_ivs_p): Pass whole phi_info to
>    vect_can_peel_nonlinear_iv_p.
>    * tree-vect-loop.cc (vect_peel_nonlinear_iv_init): Optimize
>    init_expr * pow (step_expr, skipn) to init_expr
>    << (log2 (step_expr) * skipn) when step_expr is exact_log2.
> 
> gcc/testsuite/ChangeLog:
> 
>    * gcc.target/i386/pr111820-1.c: New test.
>    * gcc.target/i386/pr111820-2.c: New test.
>    * gcc.target/i386/pr111820-3.c: New test.
>    * gcc.target/i386/pr103144-mul-1.c: Adjust testcase.
>    * gcc.target/i386/pr103144-mul-2.c: Adjust testcase.
> ---
> .../gcc.target/i386/pr103144-mul-1.c          |  8 +++---
> .../gcc.target/i386/pr103144-mul-2.c          |  8 +++---
> gcc/testsuite/gcc.target/i386/pr111820-1.c    | 16 +++++++++++
> gcc/testsuite/gcc.target/i386/pr111820-2.c    | 16 +++++++++++
> gcc/testsuite/gcc.target/i386/pr111820-3.c    | 16 +++++++++++
> gcc/tree-vect-loop-manip.cc                   | 28 +++++++++++++++++--
> gcc/tree-vect-loop.cc                         | 21 +++++++++++---
> 7 files changed, 98 insertions(+), 15 deletions(-)
> create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-1.c
> create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-2.c
> create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-3.c
> 
> diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
> index 640c34fd959..913d7737dcd 100644
> --- a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
> +++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c
> @@ -11,7 +11,7 @@ foo_mul (int* a, int b)
>   for (int i = 0; i != N; i++)
>     {
>       a[i] = b;
> -      b *= 3;
> +      b *= 4;
>     }
> }
> 
> @@ -23,7 +23,7 @@ foo_mul_const (int* a)
>   for (int i = 0; i != N; i++)
>     {
>       a[i] = b;
> -      b *= 3;
> +      b *= 4;
>     }
> }
> 
> @@ -34,7 +34,7 @@ foo_mul_peel (int* a, int b)
>   for (int i = 0; i != 39; i++)
>     {
>       a[i] = b;
> -      b *= 3;
> +      b *= 4;
>     }
> }
> 
> @@ -46,6 +46,6 @@ foo_mul_peel_const (int* a)
>   for (int i = 0; i != 39; i++)
>     {
>       a[i] = b;
> -      b *= 3;
> +      b *= 4;
>     }
> }
> diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
> index 39fdea3a69d..b2ff186e335 100644
> --- a/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
> +++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c
> @@ -16,12 +16,12 @@ avx2_test (void)
> 
>   __builtin_memset (epi32_exp, 0, N * sizeof (int));
>   int b = 8;
> -  v8si init = __extension__(v8si) { b, b * 3, b * 9, b * 27, b * 81, b * 243, b * 729, b * 2187 };
> +  v8si init = __extension__(v8si) { b, b * 4, b * 16, b * 64, b * 256, b * 1024, b * 4096, b * 16384 };
> 
>   for (int i = 0; i != N / 8; i++)
>     {
>       memcpy (epi32_exp + i * 8, &init, 32);
> -      init *= 6561;
> +      init *= 65536;
>     }
> 
>   foo_mul (epi32_dst, b);
> @@ -32,11 +32,11 @@ avx2_test (void)
>   if (__builtin_memcmp (epi32_dst, epi32_exp, 39 * 4) != 0)
>     __builtin_abort ();
> 
> -  init = __extension__(v8si) { 1, 3, 9, 27, 81, 243, 729, 2187 };
> +  init = __extension__(v8si) { 1, 4, 16, 64, 256, 1024, 4096, 16384 };
>   for (int i = 0; i != N / 8; i++)
>     {
>       memcpy (epi32_exp + i * 8, &init, 32);
> -      init *= 6561;
> +      init *= 65536;
>     }
> 
>   foo_mul_const (epi32_dst);
> diff --git a/gcc/testsuite/gcc.target/i386/pr111820-1.c b/gcc/testsuite/gcc.target/i386/pr111820-1.c
> new file mode 100644
> index 00000000000..50e960c39d4
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/i386/pr111820-1.c
> @@ -0,0 +1,16 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -mavx2 -fno-tree-vrp -Wno-aggressive-loop-optimizations -fdump-tree-vect-details" } */
> +/* { dg-final { scan-tree-dump "Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big" "vect" } } */
> +
> +int r;
> +int r_0;
> +
> +void f1 (void)
> +{
> +  int n = 0;
> +  while (-- n)
> +    {
> +      r_0 += r;
> +      r  *= 3;
> +    }
> +}
> diff --git a/gcc/testsuite/gcc.target/i386/pr111820-2.c b/gcc/testsuite/gcc.target/i386/pr111820-2.c
> new file mode 100644
> index 00000000000..dbeceb228c3
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/i386/pr111820-2.c
> @@ -0,0 +1,16 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-aggressive-loop-optimizations" } */
> +/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
> +
> +int r;
> +int r_0;
> +
> +void f (void)
> +{
> +  int n = 0;
> +  while (-- n)
> +    {
> +      r_0 += r ;
> +      r  *= 2;
> +    }
> +}
> diff --git a/gcc/testsuite/gcc.target/i386/pr111820-3.c b/gcc/testsuite/gcc.target/i386/pr111820-3.c
> new file mode 100644
> index 00000000000..b778f517663
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/i386/pr111820-3.c
> @@ -0,0 +1,16 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-aggressive-loop-optimizations" } */
> +/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
> +
> +int r;
> +int r_0;
> +
> +void f (void)
> +{
> +  int n = 14;
> +  while (-- n)
> +    {
> +      r_0 += r ;
> +      r  *= 3;
> +    }
> +}
> diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc
> index f60fa50e8f4..767b19b15a1 100644
> --- a/gcc/tree-vect-loop-manip.cc
> +++ b/gcc/tree-vect-loop-manip.cc
> @@ -1391,8 +1391,10 @@ iv_phi_p (stmt_vec_info stmt_info)
> /* Return true if vectorizer can peel for nonlinear iv.  */
> static bool
> vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
> -                  enum vect_induction_op_type induction_type)
> +                  stmt_vec_info stmt_info)
> {
> +  enum vect_induction_op_type induction_type
> +    = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (stmt_info);
>   tree niters_skip;
>   /* Init_expr will be update by vect_update_ivs_after_vectorizer,
>      if niters or vf is unkown:
> @@ -1413,11 +1415,31 @@ vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
>       return false;
>     }
> 
> +  /* Avoid compile time hog on vect_peel_nonlinear_iv_init.  */
> +  if (induction_type == vect_step_op_mul)
> +    {
> +      tree step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info);
> +      tree type = TREE_TYPE (step_expr);
> +
> +      if (wi::exact_log2 (wi::to_wide (step_expr)) == -1
> +      && LOOP_VINFO_INT_NITERS(loop_vinfo) >= TYPE_PRECISION (type))
> +    {
> +      if (dump_enabled_p ())
> +        dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> +                 "Avoid compile time hog on"
> +                 " vect_peel_nonlinear_iv_init"
> +                 " for nonlinear induction vec_step_op_mul"
> +                 " when iteration count is too big.\n");
> +      return false;
> +    }
> +    }
> +
>   /* Also doens't support peel for neg when niter is variable.
>      ??? generate something like niter_expr & 1 ? init_expr : -init_expr?  */
>   niters_skip = LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo);
>   if ((niters_skip != NULL_TREE
> -       && TREE_CODE (niters_skip) != INTEGER_CST)
> +       && (TREE_CODE (niters_skip) != INTEGER_CST
> +       || (HOST_WIDE_INT) TREE_INT_CST_LOW (niters_skip) < 0))
>       || (!vect_use_loop_mask_for_alignment_p (loop_vinfo)
>      && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0))
>     {
> @@ -1478,7 +1500,7 @@ vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
>       induction_type = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (phi_info);
>       if (induction_type != vect_step_op_add)
>    {
> -      if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, induction_type))
> +      if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, phi_info))
>        return false;
> 
>      continue;
> diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
> index 92d2e0ef9be..2f098b96b1d 100644
> --- a/gcc/tree-vect-loop.cc
> +++ b/gcc/tree-vect-loop.cc
> @@ -8728,13 +8728,26 @@ vect_peel_nonlinear_iv_init (gimple_seq* stmts, tree init_expr,
>       {
>    tree utype = unsigned_type_for (type);
>    init_expr = gimple_convert (stmts, utype, init_expr);
> -    unsigned skipn = TREE_INT_CST_LOW (skip_niters);
> +    wide_int skipn = wi::to_wide (skip_niters);
>    wide_int begin = wi::to_wide (step_expr);
> -    for (unsigned i = 0; i != skipn - 1; i++)
> -      begin = wi::mul (begin, wi::to_wide (step_expr));
> +    mpz_t base, exp, mod, res;
> +    mpz_init (base);
> +    mpz_init (mod);
> +    mpz_init (exp);
> +    mpz_init (res);
> +    wi::to_mpz (begin, base, TYPE_SIGN (type));
> +    wi::to_mpz (skipn, exp, UNSIGNED);
> +    mpz_ui_pow_ui (mod, 2, TYPE_PRECISION (type));
> +    mpz_powm (res, base, exp, mod);
> +    begin = wi::from_mpz (type, res, TYPE_SIGN (type));
>    tree mult_expr = wide_int_to_tree (utype, begin);
> -    init_expr = gimple_build (stmts, MULT_EXPR, utype, init_expr, mult_expr);
> +    init_expr = gimple_build (stmts, MULT_EXPR, utype,
> +                  init_expr, mult_expr);
>    init_expr = gimple_convert (stmts, type, init_expr);
> +    mpz_clear (base);
> +    mpz_clear (mod);
> +    mpz_clear (exp);
> +    mpz_clear (res);
>       }
>       break;
> 
> -- 
> 2.31.1
>