diff mbox series

tree-optimization/115825 - improve unroll estimates for volatile accesses

Message ID 20240710123632.DDFAD3865C17@sourceware.org
State New
Headers show
Series tree-optimization/115825 - improve unroll estimates for volatile accesses | expand

Commit Message

Richard Biener July 10, 2024, 12:36 p.m. UTC 
The loop unrolling code assumes that one third of all volatile accesses
can be possibly optimized away which is of course not true.  This leads
to excessive unrolling in some cases.  The following tracks the number
of stmts with side-effects as those are not eliminatable later and
only assumes one third of the other stmts can be further optimized.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

There's quite some testsuite fallout, mostly because of different rounding
and a size of 8 now no longer is optimistically optimized to 5 but only 6.
I can fix that by writing

  *est_eliminated = (unr_insns - not_elim) / 3;

as

  *est_eliminated = unr_insns - not_elim - (unr_insns - not_elim) * 2 / 3;

to preserve the old rounding behavior.  But for example

FAIL: g++.dg/warn/Warray-bounds-20.C  -std=gnu++14 LP64 note (test for 
warnings, line 56)

shows

  size:   3 C::C (_25, &MEM <const void *[8]> [(void *)&_ZTT2D1 + 48B]);

which we now consider not being optimizable (correctly I think) and thus
the optimistic size reduction isn't enough to get the loop unrolled.
Previously the computed size of 20 was reduced to 13, exactly the size
of the not unrolled body.

So the remaining fallout will be

+FAIL: g++.dg/warn/Warray-bounds-20.C  -std=gnu++14 LP64 note (test for 
warnings
, line 56)
+FAIL: g++.dg/warn/Warray-bounds-20.C  -std=gnu++14 note (test for 
warnings, lin
e 66)
...
+FAIL: c-c++-common/ubsan/unreachable-3.c  -std=gnu++14  scan-tree-dump 
optimized "__builtin___ubsan_handle_builtin_unreachable"
...
+FAIL: c-c++-common/ubsan/unreachable-3.c   -O0   scan-tree-dump optimized 
"__builtin___ubsan_handle_builtin_unreachable"

for the latter the issue is __builtin___sanitizer_cov_trace_pc ()

Does this seem feasible overall?  I can fixup the testcases above
with #pragma unroll ...

Thanks,
Richard.

	PR tree-optimization/115825
	* tree-ssa-loop-ivcanon.cc (loop_size::not_eliminatable_after_peeling):
	New.
	(loop_size::last_iteration_not_eliminatable_after_peeling): Likewise.
	(tree_estimate_loop_size): Count stmts with side-effects as
	not optimistically eliminatable.
	(estimated_unrolled_size): Compute the number of stmts that can
	be optimistically eliminated by followup transforms.
	(try_unroll_loop_completely): Adjust.

	* gcc.dg/tree-ssa/cunroll-17.c: New testcase.
---
 gcc/testsuite/gcc.dg/tree-ssa/cunroll-17.c | 11 +++++++
 gcc/tree-ssa-loop-ivcanon.cc               | 35 +++++++++++++++++-----
 2 files changed, 38 insertions(+), 8 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cunroll-17.c
diff mbox series

Patch

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cunroll-17.c b/gcc/testsuite/gcc.dg/tree-ssa/cunroll-17.c
new file mode 100644
index 00000000000..282db99c883
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cunroll-17.c
@@ -0,0 +1,11 @@ 
+/* { dg-do compile } */
+/* { dg-options "-Os -fdump-tree-optimized" } */
+
+char volatile v;
+void for16 (void)
+{
+  for (char i = 16; i > 0; i -= 2)
+    v = i;
+}
+
+/* { dg-final { scan-tree-dump-times " ={v} " 1 "optimized" } } */
diff --git a/gcc/tree-ssa-loop-ivcanon.cc b/gcc/tree-ssa-loop-ivcanon.cc
index 5ef24a91917..dd941c31648 100644
--- a/gcc/tree-ssa-loop-ivcanon.cc
+++ b/gcc/tree-ssa-loop-ivcanon.cc
@@ -139,11 +139,16 @@  struct loop_size
      variable where induction variable starts at known constant.)  */
   int eliminated_by_peeling;
 
+  /* Number of instructions that cannot be further optimized in the
+     peeled loop, for example volatile accesses.  */
+  int not_eliminatable_after_peeling;
+
   /* Same statistics for last iteration of loop: it is smaller because
      instructions after exit are not executed.  */
   int last_iteration;
   int last_iteration_eliminated_by_peeling;
-  
+  int last_iteration_not_eliminatable_after_peeling;
+
   /* If some IV computation will become constant.  */
   bool constant_iv;
 
@@ -267,8 +272,10 @@  tree_estimate_loop_size (class loop *loop, edge exit, edge edge_to_cancel,
 
   size->overall = 0;
   size->eliminated_by_peeling = 0;
+  size->not_eliminatable_after_peeling = 0;
   size->last_iteration = 0;
   size->last_iteration_eliminated_by_peeling = 0;
+  size->last_iteration_not_eliminatable_after_peeling = 0;
   size->num_pure_calls_on_hot_path = 0;
   size->num_non_pure_calls_on_hot_path = 0;
   size->non_call_stmts_on_hot_path = 0;
@@ -292,6 +299,7 @@  tree_estimate_loop_size (class loop *loop, edge exit, edge edge_to_cancel,
 	{
 	  gimple *stmt = gsi_stmt (gsi);
 	  int num = estimate_num_insns (stmt, &eni_size_weights);
+	  bool not_eliminatable_after_peeling = false;
 	  bool likely_eliminated = false;
 	  bool likely_eliminated_last = false;
 	  bool likely_eliminated_peeled = false;
@@ -304,7 +312,9 @@  tree_estimate_loop_size (class loop *loop, edge exit, edge edge_to_cancel,
 
 	  /* Look for reasons why we might optimize this stmt away. */
 
-	  if (!gimple_has_side_effects (stmt))
+	  if (gimple_has_side_effects (stmt))
+	    not_eliminatable_after_peeling = true;
+	  else
 	    {
 	      /* Exit conditional.  */
 	      if (exit && body[i] == exit->src
@@ -377,11 +387,15 @@  tree_estimate_loop_size (class loop *loop, edge exit, edge edge_to_cancel,
 	  size->overall += num;
 	  if (likely_eliminated || likely_eliminated_peeled)
 	    size->eliminated_by_peeling += num;
+	  if (not_eliminatable_after_peeling)
+	    size->not_eliminatable_after_peeling += num;
 	  if (!after_exit)
 	    {
 	      size->last_iteration += num;
 	      if (likely_eliminated || likely_eliminated_last)
 		size->last_iteration_eliminated_by_peeling += num;
+	      if (not_eliminatable_after_peeling)
+		size->last_iteration_not_eliminatable_after_peeling += num;
 	    }
 	  if ((size->overall * 3 / 2 - size->eliminated_by_peeling
 	      - size->last_iteration_eliminated_by_peeling) > upper_bound)
@@ -437,18 +451,22 @@  tree_estimate_loop_size (class loop *loop, edge exit, edge edge_to_cancel,
    It is (NUNROLL + 1) * size of loop body with taking into account
    the fact that in last copy everything after exit conditional
    is dead and that some instructions will be eliminated after
-   peeling.  */
+   peeling.  Set *EST_ELIMINATED to the number of stmts that could be
+   optimistically eliminated by followup transforms.  */
 static unsigned HOST_WIDE_INT
 estimated_unrolled_size (struct loop_size *size,
+			 unsigned HOST_WIDE_INT *est_eliminated,
 			 unsigned HOST_WIDE_INT nunroll)
 {
   HOST_WIDE_INT unr_insns = ((nunroll)
   			     * (HOST_WIDE_INT) (size->overall
 			     			- size->eliminated_by_peeling));
-  if (!nunroll)
-    unr_insns = 0;
+  HOST_WIDE_INT not_elim
+    = ((nunroll) * (HOST_WIDE_INT) size->not_eliminatable_after_peeling);
   unr_insns += size->last_iteration - size->last_iteration_eliminated_by_peeling;
+  not_elim += size->last_iteration_not_eliminatable_after_peeling;
 
+  *est_eliminated = (unr_insns - not_elim) / 3;
   return unr_insns;
 }
 
@@ -829,8 +847,9 @@  try_unroll_loop_completely (class loop *loop,
 	    }
 
 	  unsigned HOST_WIDE_INT ninsns = size.overall;
+	  unsigned HOST_WIDE_INT est_eliminated;
 	  unsigned HOST_WIDE_INT unr_insns
-	    = estimated_unrolled_size (&size, n_unroll);
+	    = estimated_unrolled_size (&size, &est_eliminated, n_unroll);
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    {
 	      fprintf (dump_file, "  Loop size: %d\n", (int) ninsns);
@@ -842,7 +861,7 @@  try_unroll_loop_completely (class loop *loop,
 	     cautious on guessing if the unrolling is going to be
 	     profitable.
 	     Move from estimated_unrolled_size to unroll small loops.  */
-	  if (unr_insns * 2 / 3
+	  if (unr_insns - est_eliminated
 	      /* If there is IV variable that will become constant, we
 		 save one instruction in the loop prologue we do not
 		 account otherwise.  */
@@ -919,7 +938,7 @@  try_unroll_loop_completely (class loop *loop,
 	     2) Big loop after completely unroll may not be vectorized
 	     by BB vectorizer.  */
 	  else if ((cunrolli && !loop->inner
-		    ? unr_insns : unr_insns * 2 / 3)
+		    ? unr_insns : unr_insns - est_eliminated)
 		   > (unsigned) param_max_completely_peeled_insns)
 	    {
 	      if (dump_file && (dump_flags & TDF_DETAILS))