unroll: Avoid unnecessary tail loops for constant niters

unroll and jam can decide to unroll the outer loop of a nest like:

  for (int j = 0; j < n; ++j)
    for (int i = 0; i < n; ++i)
      x[i] += __builtin_expf (y[j][i]);

It then uses a tail loop to handle any left-over iterations.

However, the code is structured so that this tail loop is always used.
If n is a multiple of the unroll factor UF, the final UF iterations will
use the tail loop rather than the unrolled loop.

“Fixing” that for variable loop counts would mean introducing another
runtime test: a branch around the tail loop if there are no more
iterations.  There's at least an argument that the overhead of doing
that test might not pay for itself.

But we use this structure even if the iteration count is provably
a multiple of UF at compile time.  E.g. with s/n/100/ and an
unroll factor of 2, the first 98 iterations use the unrolled loop
and the final 2 iterations use the original loop.

This patch makes the unroller avoid a tail loop in that case.
The end result seemed easier to follow if variables were declared
at the point of initialisation, so that it's more obvious which
ones are meaningful even when there's no tail loop.

Tested on aarch64-linux-gnu so far, will test on x86_64-linux-gnu too.
OK to install if testing passes?

Richard


gcc/
	* tree-ssa-loop-manip.c (determine_exit_conditions): Return a null
	exit condition if no tail loop is needed, and if the original exit
	condition should therefore be kept as-is.
	(tree_transform_and_unroll_loop): Handle that case here too.

gcc/testsuite/
	* gcc.dg/unroll-9.c: New test/
---
 gcc/testsuite/gcc.dg/unroll-9.c |  12 ++
 gcc/tree-ssa-loop-manip.c       | 306 +++++++++++++++++---------------
 2 files changed, 176 insertions(+), 142 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/unroll-9.c

On July 20, 2021 5:31:17 PM GMT+02:00, Richard Sandiford via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
>unroll and jam can decide to unroll the outer loop of a nest like:
>
>  for (int j = 0; j < n; ++j)
>    for (int i = 0; i < n; ++i)
>      x[i] += __builtin_expf (y[j][i]);
>
>It then uses a tail loop to handle any left-over iterations.
>
>However, the code is structured so that this tail loop is always used.
>If n is a multiple of the unroll factor UF, the final UF iterations
>will
>use the tail loop rather than the unrolled loop.
>
>“Fixing” that for variable loop counts would mean introducing another
>runtime test: a branch around the tail loop if there are no more
>iterations.  There's at least an argument that the overhead of doing
>that test might not pay for itself.
>
>But we use this structure even if the iteration count is provably
>a multiple of UF at compile time.  E.g. with s/n/100/ and an
>unroll factor of 2, the first 98 iterations use the unrolled loop
>and the final 2 iterations use the original loop.
>
>This patch makes the unroller avoid a tail loop in that case.
>The end result seemed easier to follow if variables were declared
>at the point of initialisation, so that it's more obvious which
>ones are meaningful even when there's no tail loop.
>
>Tested on aarch64-linux-gnu so far, will test on x86_64-linux-gnu too.
>OK to install if testing passes?

Ok. 

Richard. 

>Richard
>
>
>gcc/
>	* tree-ssa-loop-manip.c (determine_exit_conditions): Return a null
>	exit condition if no tail loop is needed, and if the original exit
>	condition should therefore be kept as-is.
>	(tree_transform_and_unroll_loop): Handle that case here too.
>
>gcc/testsuite/
>	* gcc.dg/unroll-9.c: New test/
>---
> gcc/testsuite/gcc.dg/unroll-9.c |  12 ++
> gcc/tree-ssa-loop-manip.c       | 306 +++++++++++++++++---------------
> 2 files changed, 176 insertions(+), 142 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/unroll-9.c
>
>diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
>index 28ae1316fa0..41f9872ca10 100644
>--- a/gcc/tree-ssa-loop-manip.c
>+++ b/gcc/tree-ssa-loop-manip.c
>@@ -997,8 +997,10 @@ can_unroll_loop_p (class loop *loop, unsigned
>factor,
>/* Determines the conditions that control execution of LOOP unrolled
>FACTOR
>    times.  DESC is number of iterations of LOOP.  ENTER_COND is set to
>    condition that must be true if the main loop can be entered.
>+   If the loop does not always iterate an exact multiple of FACTOR
>times,
>EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values
>describing
>-   how the exit from the unrolled loop should be controlled.  */
>+   how the exit from the unrolled loop should be controlled. 
>Otherwise,
>+   the trees are set to null and EXIT_CMP is set to ERROR_MARK.  */
> 
> static void
>determine_exit_conditions (class loop *loop, class tree_niter_desc
>*desc,
>@@ -1079,6 +1081,16 @@ determine_exit_conditions (class loop *loop,
>class tree_niter_desc *desc,
>   assum = fold_build2 (cmp, boolean_type_node, base, bound);
>   cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
> 
>+  if (integer_nonzerop (cond)
>+      && integer_zerop (desc->may_be_zero))
>+    {
>+      /* Convert the latch count to an iteration count.  */
>+      tree niter = fold_build2 (PLUS_EXPR, type, desc->niter,
>+				build_one_cst (type));
>+      if (multiple_of_p (type, niter, bigstep))
>+	return;
>+    }
>+
>cond = force_gimple_operand (unshare_expr (cond), &stmts, false,
>NULL_TREE);
>   if (stmts)
>  gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
>@@ -1234,137 +1246,138 @@ tree_transform_and_unroll_loop (class loop
>*loop, unsigned factor,
> 				transform_callback transform,
> 				void *data)
> {
>-  gcond *exit_if;
>-  tree ctr_before, ctr_after;
>-  tree enter_main_cond, exit_base, exit_step, exit_bound;
>-  enum tree_code exit_cmp;
>-  gphi *phi_old_loop, *phi_new_loop, *phi_rest;
>-  gphi_iterator psi_old_loop, psi_new_loop;
>-  tree init, next, new_init;
>-  class loop *new_loop;
>-  basic_block rest, exit_bb;
>-  edge old_entry, new_entry, old_latch, precond_edge, new_exit;
>-  edge new_nonexit, e;
>-  gimple_stmt_iterator bsi;
>-  use_operand_p op;
>-  bool ok;
>-  unsigned i;
>-  profile_probability prob, prob_entry, scale_unrolled;
>-  profile_count freq_e, freq_h;
>   gcov_type new_est_niter = niter_for_unrolled_loop (loop, factor);
>unsigned irr = loop_preheader_edge (loop)->flags &
>EDGE_IRREDUCIBLE_LOOP;
>-  auto_vec<edge> to_remove;
> 
>+  enum tree_code exit_cmp;
>+  tree enter_main_cond, exit_base, exit_step, exit_bound;
>   determine_exit_conditions (loop, desc, factor,
> 			     &enter_main_cond, &exit_base, &exit_step,
> 			     &exit_cmp, &exit_bound);
>+  bool single_loop_p = !exit_base;
> 
>/* Let us assume that the unrolled loop is quite likely to be entered. 
>*/
>+  profile_probability prob_entry;
>   if (integer_nonzerop (enter_main_cond))
>     prob_entry = profile_probability::always ();
>   else
>     prob_entry = profile_probability::guessed_always ()
> 			.apply_scale (PROB_UNROLLED_LOOP_ENTERED, 100);
> 
>-  /* The values for scales should keep profile consistent, and
>somewhat close
>-     to correct.
>-
>-     TODO: The current value of SCALE_REST makes it appear that the
>loop that
>-     is created by splitting the remaining iterations of the unrolled
>loop is
>-     executed the same number of times as the original loop, and with
>the same
>-     frequencies, which is obviously wrong.  This does not appear to
>cause
>-     problems, so we do not bother with fixing it for now.  To make
>the profile
>-     correct, we would need to change the probability of the exit edge
>of the
>-     loop, and recompute the distribution of frequencies in its body
>because
>-     of this change (scale the frequencies of blocks before and after
>the exit
>-     by appropriate factors).  */
>-  scale_unrolled = prob_entry;
>-
>-  new_loop = loop_version (loop, enter_main_cond, NULL, prob_entry,
>-			   prob_entry.invert (), scale_unrolled,
>-			   profile_probability::guessed_always (),
>-			   true);
>-  gcc_assert (new_loop != NULL);
>-  update_ssa (TODO_update_ssa);
>-
>-  /* Prepare the cfg and update the phi nodes.  Move the loop exit to
>the
>-     loop latch (and make its condition dummy, for the moment).  */
>-  rest = loop_preheader_edge (new_loop)->src;
>-  precond_edge = single_pred_edge (rest);
>-  split_edge (loop_latch_edge (loop));
>-  exit_bb = single_pred (loop->latch);
>-
>-  /* Since the exit edge will be removed, the frequency of all the
>blocks
>-     in the loop that are dominated by it must be scaled by
>-     1 / (1 - exit->probability).  */
>-  if (exit->probability.initialized_p ())
>-    scale_dominated_blocks_in_loop (loop, exit->src,
>-				    /* We are scaling up here so probability
>-				       does not fit.  */
>-				    loop->header->count,
>-				    loop->header->count
>-				    - loop->header->count.apply_probability
>-					 (exit->probability));
>-
>-  bsi = gsi_last_bb (exit_bb);
>-  exit_if = gimple_build_cond (EQ_EXPR, integer_zero_node,
>-			       integer_zero_node,
>-			       NULL_TREE, NULL_TREE);
>-
>-  gsi_insert_after (&bsi, exit_if, GSI_NEW_STMT);
>-  new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
>-  rescan_loop_exit (new_exit, true, false);
>-
>-  /* Set the probability of new exit to the same of the old one.  Fix
>-     the frequency of the latch block, by scaling it back by
>-     1 - exit->probability.  */
>-  new_exit->probability = exit->probability;
>-  new_nonexit = single_pred_edge (loop->latch);
>-  new_nonexit->probability = exit->probability.invert ();
>-  new_nonexit->flags = EDGE_TRUE_VALUE;
>-  if (new_nonexit->probability.initialized_p ())
>-    scale_bbs_frequencies (&loop->latch, 1, new_nonexit->probability);
>-
>-  old_entry = loop_preheader_edge (loop);
>-  new_entry = loop_preheader_edge (new_loop);
>-  old_latch = loop_latch_edge (loop);
>-  for (psi_old_loop = gsi_start_phis (loop->header),
>-       psi_new_loop = gsi_start_phis (new_loop->header);
>-       !gsi_end_p (psi_old_loop);
>-       gsi_next (&psi_old_loop), gsi_next (&psi_new_loop))
>+  gcond *exit_if = nullptr;
>+  class loop *new_loop = nullptr;
>+  basic_block rest;
>+  edge new_exit;
>+  if (!single_loop_p)
>     {
>-      phi_old_loop = psi_old_loop.phi ();
>-      phi_new_loop = psi_new_loop.phi ();
>-
>-      init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry);
>-      op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry);
>-      gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR
>(op)));
>-      next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch);
>-
>-      /* Prefer using original variable as a base for the new ssa
>name.
>-	 This is necessary for virtual ops, and useful in order to avoid
>-	 losing debug info for real ops.  */
>-      if (TREE_CODE (next) == SSA_NAME
>-	  && useless_type_conversion_p (TREE_TYPE (next),
>-					TREE_TYPE (init)))
>-	new_init = copy_ssa_name (next);
>-      else if (TREE_CODE (init) == SSA_NAME
>-	       && useless_type_conversion_p (TREE_TYPE (init),
>-					     TREE_TYPE (next)))
>-	new_init = copy_ssa_name (init);
>-      else if (useless_type_conversion_p (TREE_TYPE (next), TREE_TYPE
>(init)))
>-	new_init = make_temp_ssa_name (TREE_TYPE (next), NULL, "unrinittmp");
>-      else
>-	new_init = make_temp_ssa_name (TREE_TYPE (init), NULL, "unrinittmp");
>+      /* The values for scales should keep profile consistent, and
>somewhat
>+	 close to correct.
>+
>+	 TODO: The current value of SCALE_REST makes it appear that the loop
>+	 that is created by splitting the remaining iterations of the
>unrolled
>+	 loop is executed the same number of times as the original loop, and
>+	 with the same frequencies, which is obviously wrong.  This does not
>+	 appear to cause problems, so we do not bother with fixing it for
>now.
>+	 To make the profile correct, we would need to change the probability
>+	 of the exit edge of the loop, and recompute the distribution of
>+	 frequencies in its body because of this change (scale the
>frequencies
>+	 of blocks before and after the exit by appropriate factors).  */
>+      profile_probability scale_unrolled = prob_entry;
>+      new_loop = loop_version (loop, enter_main_cond, NULL,
>prob_entry,
>+			       prob_entry.invert (), scale_unrolled,
>+			       profile_probability::guessed_always (),
>+			       true);
>+      gcc_assert (new_loop != NULL);
>+      update_ssa (TODO_update_ssa);
>+
>+      /* Prepare the cfg and update the phi nodes.  Move the loop exit
>to the
>+	 loop latch (and make its condition dummy, for the moment).  */
>+      rest = loop_preheader_edge (new_loop)->src;
>+      edge precond_edge = single_pred_edge (rest);
>+      split_edge (loop_latch_edge (loop));
>+      basic_block exit_bb = single_pred (loop->latch);
>+
>+      /* Since the exit edge will be removed, the frequency of all the
>blocks
>+	 in the loop that are dominated by it must be scaled by
>+	 1 / (1 - exit->probability).  */
>+      if (exit->probability.initialized_p ())
>+	scale_dominated_blocks_in_loop (loop, exit->src,
>+					/* We are scaling up here so
>+					   probability does not fit.  */
>+					loop->header->count,
>+					loop->header->count
>+					- loop->header->count.apply_probability
>+					    (exit->probability));
>+
>+      gimple_stmt_iterator bsi = gsi_last_bb (exit_bb);
>+      exit_if = gimple_build_cond (EQ_EXPR, integer_zero_node,
>+				   integer_zero_node,
>+				   NULL_TREE, NULL_TREE);
>+
>+      gsi_insert_after (&bsi, exit_if, GSI_NEW_STMT);
>+      new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
>+      rescan_loop_exit (new_exit, true, false);
>+
>+      /* Set the probability of new exit to the same of the old one. 
>Fix
>+	 the frequency of the latch block, by scaling it back by
>+	 1 - exit->probability.  */
>+      new_exit->probability = exit->probability;
>+      edge new_nonexit = single_pred_edge (loop->latch);
>+      new_nonexit->probability = exit->probability.invert ();
>+      new_nonexit->flags = EDGE_TRUE_VALUE;
>+      if (new_nonexit->probability.initialized_p ())
>+	scale_bbs_frequencies (&loop->latch, 1, new_nonexit->probability);
>+
>+      edge old_entry = loop_preheader_edge (loop);
>+      edge new_entry = loop_preheader_edge (new_loop);
>+      edge old_latch = loop_latch_edge (loop);
>+      for (gphi_iterator psi_old_loop = gsi_start_phis (loop->header),
>+	     psi_new_loop = gsi_start_phis (new_loop->header);
>+	   !gsi_end_p (psi_old_loop);
>+	   gsi_next (&psi_old_loop), gsi_next (&psi_new_loop))
>+	{
>+	  gphi *phi_old_loop = psi_old_loop.phi ();
>+	  gphi *phi_new_loop = psi_new_loop.phi ();
>+
>+	  tree init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry);
>+	  use_operand_p op
>+	    = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry);
>+	  gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
>+	  tree next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch);
>+
>+	  /* Prefer using original variable as a base for the new ssa name.
>+	     This is necessary for virtual ops, and useful in order to avoid
>+	     losing debug info for real ops.  */
>+	  tree new_init;
>+	  if (TREE_CODE (next) == SSA_NAME
>+	      && useless_type_conversion_p (TREE_TYPE (next),
>+					    TREE_TYPE (init)))
>+	    new_init = copy_ssa_name (next);
>+	  else if (TREE_CODE (init) == SSA_NAME
>+		   && useless_type_conversion_p (TREE_TYPE (init),
>+						 TREE_TYPE (next)))
>+	    new_init = copy_ssa_name (init);
>+	  else if (useless_type_conversion_p (TREE_TYPE (next),
>+					      TREE_TYPE (init)))
>+	    new_init = make_temp_ssa_name (TREE_TYPE (next), NULL,
>+					   "unrinittmp");
>+	  else
>+	    new_init = make_temp_ssa_name (TREE_TYPE (init), NULL,
>+					   "unrinittmp");
> 
>-      phi_rest = create_phi_node (new_init, rest);
>+	  gphi *phi_rest = create_phi_node (new_init, rest);
>+	  add_phi_arg (phi_rest, init, precond_edge, UNKNOWN_LOCATION);
>+	  add_phi_arg (phi_rest, next, new_exit, UNKNOWN_LOCATION);
>+	  SET_USE (op, new_init);
>+	}
> 
>-      add_phi_arg (phi_rest, init, precond_edge, UNKNOWN_LOCATION);
>-      add_phi_arg (phi_rest, next, new_exit, UNKNOWN_LOCATION);
>-      SET_USE (op, new_init);
>+      remove_path (exit);
>+    }
>+  else
>+    {
>+      new_exit = exit;
>+      rest = exit->dest;
>     }
>-
>-  remove_path (exit);
> 
>   /* Transform the loop.  */
>   if (transform)
>@@ -1376,57 +1389,66 @@ tree_transform_and_unroll_loop (class loop
>*loop, unsigned factor,
>   bitmap_ones (wont_exit);
>   bitmap_clear_bit (wont_exit, factor - 1);
> 
>-  ok = gimple_duplicate_loop_to_header_edge
>+  auto_vec<edge> to_remove;
>+  bool ok = gimple_duplicate_loop_to_header_edge
> 	  (loop, loop_latch_edge (loop), factor - 1,
> 	   wont_exit, new_exit, &to_remove, DLTHE_FLAG_UPDATE_FREQ);
>   gcc_assert (ok);
> 
>-  FOR_EACH_VEC_ELT (to_remove, i, e)
>+  for (edge e : to_remove)
>     {
>       ok = remove_path (e);
>       gcc_assert (ok);
>     }
>   update_ssa (TODO_update_ssa);
> 
>-  /* Ensure that the frequencies in the loop match the new estimated
>-     number of iterations, and change the probability of the new
>-     exit edge.  */
>-
>-  freq_h = loop->header->count;
>-  freq_e = (loop_preheader_edge (loop))->count ();
>-  if (freq_h.nonzero_p ())
>+  if (!single_loop_p)
>     {
>-      /* Avoid dropping loop body profile counter to 0 because of zero
>count
>-	 in loop's preheader.  */
>-      if (freq_h.nonzero_p () && !(freq_e == profile_count::zero ()))
>-        freq_e = freq_e.force_nonzero ();
>-      scale_loop_frequencies (loop, freq_e.probability_in (freq_h));
>+      /* Ensure that the frequencies in the loop match the new
>estimated
>+	 number of iterations, and change the probability of the new
>+	 exit edge.  */
>+
>+      profile_count freq_h = loop->header->count;
>+      profile_count freq_e = (loop_preheader_edge (loop))->count ();
>+      if (freq_h.nonzero_p ())
>+	{
>+	  /* Avoid dropping loop body profile counter to 0 because of zero
>+	     count in loop's preheader.  */
>+	  if (freq_h.nonzero_p () && !(freq_e == profile_count::zero ()))
>+	    freq_e = freq_e.force_nonzero ();
>+	  scale_loop_frequencies (loop, freq_e.probability_in (freq_h));
>+	}
>     }
> 
>-  exit_bb = single_pred (loop->latch);
>+  basic_block exit_bb = single_pred (loop->latch);
>   new_exit = find_edge (exit_bb, rest);
>   new_exit->probability = profile_probability::always ()
> 				.apply_scale (1, new_est_niter + 1);
> 
>-  rest->count += new_exit->count ();
>+  if (!single_loop_p)
>+    rest->count += new_exit->count ();
> 
>-  new_nonexit = single_pred_edge (loop->latch);
>-  prob = new_nonexit->probability;
>+  edge new_nonexit = single_pred_edge (loop->latch);
>+  profile_probability prob = new_nonexit->probability;
>   new_nonexit->probability = new_exit->probability.invert ();
>   prob = new_nonexit->probability / prob;
>   if (prob.initialized_p ())
>     scale_bbs_frequencies (&loop->latch, 1, prob);
> 
>-  /* Finally create the new counter for number of iterations and add
>the new
>-     exit instruction.  */
>-  bsi = gsi_last_nondebug_bb (exit_bb);
>-  exit_if = as_a <gcond *> (gsi_stmt (bsi));
>-  create_iv (exit_base, exit_step, NULL_TREE, loop,
>-	     &bsi, false, &ctr_before, &ctr_after);
>-  gimple_cond_set_code (exit_if, exit_cmp);
>-  gimple_cond_set_lhs (exit_if, ctr_after);
>-  gimple_cond_set_rhs (exit_if, exit_bound);
>-  update_stmt (exit_if);
>+  if (!single_loop_p)
>+    {
>+      /* Finally create the new counter for number of iterations and
>add
>+	 the new exit instruction.  */
>+      tree ctr_before, ctr_after;
>+      gimple_stmt_iterator bsi = gsi_last_nondebug_bb (exit_bb);
>+      exit_if = as_a <gcond *> (gsi_stmt (bsi));
>+      create_iv (exit_base, exit_step, NULL_TREE, loop,
>+		 &bsi, false, &ctr_before, &ctr_after);
>+      gimple_cond_set_code (exit_if, exit_cmp);
>+      gimple_cond_set_lhs (exit_if, ctr_after);
>+      gimple_cond_set_rhs (exit_if, exit_bound);
>+      update_stmt (exit_if);
>+    }
> 
>   checking_verify_flow_info ();
>   checking_verify_loop_structure ();
>diff --git a/gcc/testsuite/gcc.dg/unroll-9.c
>b/gcc/testsuite/gcc.dg/unroll-9.c
>new file mode 100644
>index 00000000000..2d65ec3691d
>--- /dev/null
>+++ b/gcc/testsuite/gcc.dg/unroll-9.c
>@@ -0,0 +1,12 @@
>+/* { dg-options "-O3 -fdump-tree-unrolljam -fno-math-errno" } */
>+
>+void
>+f (float *restrict x, float y[100][100])
>+{
>+  for (int j = 0; j < 100; ++j)
>+    for (int i = 0; i < 100; ++i)
>+      x[i] += __builtin_expf (y[j][i]);
>+}
>+
>+/* The loop should be unrolled 2 times, without a tail loop.  */
>+/* { dg-final { scan-tree-dump-times "__builtin_expf" 2 "unrolljam" }
>} */