[gcc(refs/users/kubaneko/heads/histogram)] Merge final fix for copy header from master

[gcc(refs/users/kubaneko/heads/histogram)] Merge final fix for copy header from master

[Jan Hubicka]

https://gcc.gnu.org/g:3d73340a2969f72b754736f77d5285a86df2ed14

commit 3d73340a2969f72b754736f77d5285a86df2ed14
Author: Honza <jh@ryzen3.suse.cz>
Date:   Sat Apr 22 11:28:41 2023 +0200

    Merge final fix for copy header from master

Diff:
---
 gcc/cfgloopmanip.h           |   1 +
 gcc/tree-ssa-loop-ch.cc      | 114 +++++++++++++++++++++++++++++++++++--------
 gcc/tree-ssa-loop-ivcanon.cc |  57 +++++++++++++++++++++-
 3 files changed, 150 insertions(+), 22 deletions(-)

diff --git a/gcc/cfgloopmanip.h b/gcc/cfgloopmanip.h
index 93e417fcb7d..c40cfeae0e3 100644
--- a/gcc/cfgloopmanip.h
+++ b/gcc/cfgloopmanip.h
@@ -59,5 +59,6 @@ class loop * loop_version (class loop *, void *,
 			    basic_block *,
 			    profile_probability, profile_probability,
 			    profile_probability, profile_probability, bool);
+void adjust_loop_info_after_peeling (class loop *loop, int npeel, bool precise);
 
 #endif /* GCC_CFGLOOPMANIP_H */
diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc
index e621011fe44..2fad2a3d7b6 100644
--- a/gcc/tree-ssa-loop-ch.cc
+++ b/gcc/tree-ssa-loop-ch.cc
@@ -461,7 +461,8 @@ ch_base::copy_headers (function *fun)
       edge e;
       edge_iterator ei;
       FOR_EACH_EDGE (e, ei, loop->header->preds)
-	entry_count += e->count ();
+	if (e->src != loop->latch)
+	  entry_count += e->count ();
       while (should_duplicate_loop_header_p (header, loop, &remaining_limit))
 	{
 	  if (dump_file && (dump_flags & TDF_DETAILS))
@@ -498,8 +499,11 @@ ch_base::copy_headers (function *fun)
 
       /* Ensure that the header will have just the latch as a predecessor
 	 inside the loop.  */
-      if (!single_pred_p (exit->dest))
-	exit = single_pred_edge (split_edge (exit));
+      if (!single_pred_p (nonexit->dest))
+	{
+	  header = split_edge (nonexit);
+	  exit = single_pred_edge (header);
+	}
 
       entry = loop_preheader_edge (loop);
 
@@ -560,18 +564,17 @@ ch_base::copy_headers (function *fun)
       /* Update header of the loop.  */
       loop->header = header;
       /* Find correct latch.  We only duplicate chain of conditionals so
-         there should be precisely two edges to the new header.  One entry
-         edge and one to latch.  */
+	 there should be precisely two edges to the new header.  One entry
+	 edge and one to latch.  */
       FOR_EACH_EDGE (e, ei, loop->header->preds)
-       if (header != e->src)
-         {
-           loop->latch = e->src;
-           break;
-         }
-      /* Ensure that the latch and the preheader is simple (we know that they
-	 are not now, since there was the loop exit condition.  */
-      split_edge (loop_preheader_edge (loop));
-      split_edge (loop_latch_edge (loop));
+	if (header != e->src)
+	  {
+	    loop->latch = e->src;
+	    break;
+	  }
+      /* Ensure that the latch is simple.  */
+      if (!single_succ_p (loop_latch_edge (loop)->src))
+	split_edge (loop_latch_edge (loop));
 
       if (dump_file && (dump_flags & TDF_DETAILS))
 	{
@@ -580,22 +583,91 @@ ch_base::copy_headers (function *fun)
 	  else
 	    fprintf (dump_file, "Loop %d is still not do-while loop.\n",
 		     loop->num);
+	  fprintf (dump_file, "Exit count: ");
+	  exit_count.dump (dump_file);
+	  fprintf (dump_file, "\nEntry count: ");
+	  entry_count.dump (dump_file);
+	  fprintf (dump_file, "\n");
 	}
-      // if it is unlikely that after header copy the iterations enter the loop
-      // it behaves like peeling 1 time
+
+      /* We possibly decreased number of itrations by 1.  */
       auto_vec<edge> exits = get_loop_exit_edges (loop);
-      if (nexits == (int) exits.length ())
-	adjust_loop_estimates_minus (loop, 1, true);
+      bool precise = (nexits == (int) exits.length ());
+      if (!get_max_loop_iterations_int (loop))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "Loop %d no longer loops.\n", loop->num);
+	  /* TODO: We can unloop like in tree-ssa-loop-ivcanon.  */
+	  precise = false;
+	}
+      /* Check that loop may not terminate in other way than via
+	 basic blocks we duplicated.  */
+      if (precise)
+	{
+	  basic_block *bbs = get_loop_body (loop);
+	  for (unsigned i = 0; i < loop->num_nodes && precise; ++i)
+	   {
+	     basic_block bb = bbs[i];
+	     bool found_exit = false;
+	     FOR_EACH_EDGE (e, ei, bb->succs)
+	      if (!flow_bb_inside_loop_p (loop, e->dest))
+		{
+		  found_exit = true;
+		  break;
+		}
+	     /* If BB has exit, it was duplicated.  */
+	     if (found_exit)
+	       continue;
+	     /* Give up on irreducible loops.  */
+	     if (bb->flags & BB_IRREDUCIBLE_LOOP)
+	       {
+		 precise = false;
+		 break;
+	       }
+	     /* Check that inner loops are finite.  */
+	     for (class loop *l = bb->loop_father; l != loop && precise;
+		  l = loop_outer (l))
+	       if (!l->finite_p)
+		 {
+		   precise = false;
+		   break;
+		 }
+	     /* Verify that there is no statement that may be terminate
+		execution in a way not visible to CFG.  */
+	     for (gimple_stmt_iterator bsi = gsi_start_bb (bb);
+		  !gsi_end_p (bsi); gsi_next (&bsi))
+	       if (stmt_can_terminate_bb_p (gsi_stmt (bsi)))
+		 precise = false;
+	   }
+	}
+      if (precise)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file,
+		     "Peeled all exits:"
+		     " decreased number of iterations of loop %d by 1.\n",
+		     loop->num);
+	  adjust_loop_info_after_peeling (loop, 1, true);
+	}
       else if (exit_count >= entry_count.apply_scale (9, 10))
-	adjust_loop_estimates_minus (loop, 1, false);
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file,
+		     "Peeled likely exits: likely decreased number "
+		     "of iterations of loop %d by 1.\n", loop->num);
+	  adjust_loop_info_after_peeling (loop, 1, false);
+	}
+      else if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "Not decreased number"
+		 " of iterations of loop %d; likely exits remains.\n",
+		 loop->num);
 
       changed = true;
     }
 
   if (changed)
     {
-      if (flag_checking)
-       verify_loop_structure ();
       update_ssa (TODO_update_ssa);
       /* After updating SSA form perform CSE on the loop header
 	 copies.  This is esp. required for the pass before
diff --git a/gcc/tree-ssa-loop-ivcanon.cc b/gcc/tree-ssa-loop-ivcanon.cc
index 9c8443fd8e6..6a9ed49bb25 100644
--- a/gcc/tree-ssa-loop-ivcanon.cc
+++ b/gcc/tree-ssa-loop-ivcanon.cc
@@ -980,6 +980,61 @@ estimated_peeled_sequence_size (struct loop_size *size,
 			     	       - size->eliminated_by_peeling), 1);
 }
 
+/* Update loop estimates after peeling LOOP by NPEEL.
+   If PRECISE is false only likely exists were duplicated and thus
+   do not update any estimates that are supposed to be always reliable.  */
+void
+adjust_loop_info_after_peeling (class loop *loop, int npeel, bool precise)
+{
+  if (loop->any_estimate)
+    {
+      /* Since peeling is mostly about loops where first few
+	 iterations are special, it is not quite correct to
+	 assume that the remaining iterations will behave
+	 the same way.  However we do not have better info
+	 so update the esitmate, since it is likely better
+	 than keeping it as it is.
+
+	 Remove it if it looks wrong.
+
+	 TODO: We likely want to special case the situation where
+	 peeling is optimizing out exit edges and only update
+	 estimates here.  */
+      if (wi::leu_p (npeel, loop->nb_iterations_estimate))
+	loop->nb_iterations_estimate -= npeel;
+      else
+	loop->any_estimate = false;
+    }
+  if (loop->any_upper_bound && precise)
+    {
+      if (wi::leu_p (npeel, loop->nb_iterations_upper_bound))
+	loop->nb_iterations_upper_bound -= npeel;
+      else
+	{
+	  /* Peeling maximal number of iterations or more
+	     makes no sense and is a bug.
+	     We should peel completely.  */
+	  gcc_unreachable ();
+	}
+    }
+  if (loop->any_likely_upper_bound)
+    {
+      if (wi::leu_p (npeel, loop->nb_iterations_likely_upper_bound))
+	loop->nb_iterations_likely_upper_bound -= npeel;
+      else
+	{
+	  loop->any_estimate = true;
+	  loop->nb_iterations_estimate = 0;
+	  loop->nb_iterations_likely_upper_bound = 0;
+	}
+    }
+  if (loop->counters)
+    {
+      histogram_counters_minus_upper_bound (loop->counters, npeel);
+      /* TODO: Update loop estimate if possible.  */
+    }
+}
+
 /* If the loop is expected to iterate N times and is
    small enough, duplicate the loop body N+1 times before
    the loop itself.  This way the hot path will never
@@ -1184,7 +1239,7 @@ try_peel_loop (class loop *loop,
 			 "peeled loop %d, %i times.\n", loop->num, (int)npeel);
     }
 
-  adjust_loop_estimates_minus (loop, npeel, true);
+  adjust_loop_info_after_peeling (loop, npeel, true);
 
   profile_count entry_count = profile_count::zero ();