[gcc r13-5484] Fix find_always_executed_bbs handling of infinite loops

[gcc r13-5484] Fix find_always_executed_bbs handling of infinite loops

[Jan Hubicka]

https://gcc.gnu.org/g:da3aca031be736fe4fa8daa57c7efa69dc767160

commit r13-5484-gda3aca031be736fe4fa8daa57c7efa69dc767160
Author: Jan Hubicka <jh@suse.cz>
Date:   Sun Jan 29 01:27:26 2023 +0100

    Fix find_always_executed_bbs handling of infinite loops
    
    This patch fixes the stupid typo info find_always_executed_bbs which made
    all edges to be considered as ones closing infinite loops.  This fix has
    somewhat snowballed as, comparing it to finite_function_p, I noticed a
    divergence in handling of volatile asms (find_always_executed_bbs is conservative
    and thinks that volatile statement may return or do EH, but it is really
    impossible and elsewhere we expects that we dont) and I also noticed
    a bug in handling early returns which made some loops to be missed.
    
    I also noticed that function assumes that irreducible loops are marked in CFG
    which is not necessarily true and it is easy to detect them during the walk.
    
    Bootstrapped/regtested x86_64-linux, comitted.
    
    gcc/ChangeLog:
    
    2023-01-29  Jan Hubicka  <hubicka@ucw.cz>
    
            * ipa-utils.cc: Include calls.h, cfgloop.h and cfganal.h
            (stmt_may_terminate_function_p): If assuming return or EH
            volatile asm is safe.
            (find_always_executed_bbs): Fix handling of terminating BBS and
            infinite loops; add debug output.
            * tree-ssa-alias.cc (stmt_kills_ref_p): Fix debug output
    
    gcc/testsuite/ChangeLog:
    
    2023-01-29  Jan Hubicka  <hubicka@ucw.cz>
    
            * gcc.dg/ipa/ipa-sra-30.c: New test.
            * gcc.dg/ipa/ipa-sra-31.c: New test.
            * gcc.dg/tree-ssa/modref-dse-7.c: New test.

Diff:
---
 gcc/ipa-utils.cc                             | 85 +++++++++++++++++++++-------
 gcc/testsuite/gcc.dg/ipa/ipa-sra-30.c        | 31 ++++++++++
 gcc/testsuite/gcc.dg/ipa/ipa-sra-31.c        |  4 ++
 gcc/testsuite/gcc.dg/tree-ssa/modref-dse-7.c | 22 +++++++
 gcc/tree-ssa-alias.cc                        |  1 +
 5 files changed, 121 insertions(+), 22 deletions(-)

diff --git a/gcc/ipa-utils.cc b/gcc/ipa-utils.cc
index 3d5633340f1..8badcc2c110 100644
--- a/gcc/ipa-utils.cc
+++ b/gcc/ipa-utils.cc
@@ -40,6 +40,9 @@ along with GCC; see the file COPYING3.  If not see
 #include "ipa-modref-tree.h"
 #include "ipa-modref.h"
 #include "tree-ssa-loop-niter.h"
+#include "calls.h"
+#include "cfgloop.h"
+#include "cfganal.h"
 
 /* Debugging function for postorder and inorder code. NOTE is a string
    that is printed before the nodes are printed.  ORDER is an array of
@@ -796,11 +799,11 @@ stmt_may_terminate_function_p (function *fun, gimple *stmt, bool assume_return_o
 {
   if (stmt_can_throw_external (fun, stmt))
     return true;
+  if (assume_return_or_eh)
+    return false;
   gasm *astmt = dyn_cast <gasm *> (stmt);
   if (astmt && gimple_asm_volatile_p (astmt))
     return true;
-  if (assume_return_or_eh)
-    return false;
   if (gimple_could_trap_p (stmt))
     return true;
   if (gcall *call = dyn_cast <gcall *> (stmt))
@@ -832,8 +835,14 @@ find_always_executed_bbs (function *fun, bool assume_return_or_eh)
   auto_vec<basic_block, 20> stack;
   auto_vec<basic_block, 20> terminating_bbs;
   hash_set<basic_block> visited;
+  hash_set<basic_block> terminating_bbs_set;
   edge e;
   edge_iterator ei;
+  int flags = flags_from_decl_or_type (fun->decl);
+  /* PUre and const functions always return.  */
+  assume_return_or_eh |= (flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE);
+  if (!assume_return_or_eh)
+    mark_dfs_back_edges (fun);
 
   /* First walk all BBs reachable from entry stopping on statements that may
      terminate execution.  Everything past this statement is not going to be executed
@@ -843,9 +852,8 @@ find_always_executed_bbs (function *fun, bool assume_return_or_eh)
     {
       basic_block bb = stack.pop ();
       bool found = false, found_exit = false;
-      if (!assume_return_or_eh
-	  && (EDGE_COUNT (bb->succs) == 0 || (bb->flags & BB_IRREDUCIBLE_LOOP)))
-	found = true;
+      if (bb->index == EXIT_BLOCK)
+	continue;
       FOR_EACH_EDGE (e, ei, bb->succs)
 	{
 	  if (e->dest == EXIT_BLOCK_PTR_FOR_FN (fun))
@@ -854,10 +862,28 @@ find_always_executed_bbs (function *fun, bool assume_return_or_eh)
 	      break;
 	    }
 	  /* Watch for infinite loops.  */
-	  if (!found && (assume_return_or_eh & EDGE_DFS_BACK)
-	      && !finite_loop_p (e->src->loop_father))
-	    found = true;
+	  if (!found
+	      && !assume_return_or_eh && (e->flags & EDGE_DFS_BACK))
+	    {
+	      if (!dom_info_available_p (CDI_DOMINATORS))
+		calculate_dominance_info (CDI_DOMINATORS);
+	      /* If this is not a loop latch edge it is an irreducible region.
+		 Assume that it is infinite.
+		 TODO: with C++ forced progression we can still walk the
+		 irreducible region and see if it contains any side effects.
+		 Similarly for loops.  -ffinite-loops does not really imply
+		 this since we allow inlining across -ffinite-loops bondary
+		 and thus it can be used only as a loop flag.  */
+	      if (e->dest->loop_father->header != e->dest
+		  || !dominated_by_p (CDI_DOMINATORS, bb, e->dest))
+		found = true;
+	      else if (!finite_loop_p (e->dest->loop_father))
+		found = true;
+	    }
 	}
+      if (!assume_return_or_eh
+	  && (EDGE_COUNT (bb->succs) == 0 || (bb->flags & BB_IRREDUCIBLE_LOOP)))
+	found = true;
       for (gimple_stmt_iterator si = gsi_start_nondebug_after_labels_bb (bb);
 	   !gsi_end_p (si) && !found; gsi_next_nondebug (&si))
 	if (stmt_may_terminate_function_p (fun, gsi_stmt (si), assume_return_or_eh))
@@ -869,7 +895,10 @@ find_always_executed_bbs (function *fun, bool assume_return_or_eh)
 	{
 	  visited.add (EXIT_BLOCK_PTR_FOR_FN (fun));
 	  if (!found_exit)
-	    terminating_bbs.safe_push (bb);
+	    {
+	      terminating_bbs.safe_push (bb);
+	      terminating_bbs_set.add (bb);
+	    }
 	}
       else
 	FOR_EACH_EDGE (e, ei, bb->succs)
@@ -883,8 +912,7 @@ find_always_executed_bbs (function *fun, bool assume_return_or_eh)
 
   bitmap ret = BITMAP_ALLOC (NULL);
   /* A degenerated case when there is no path to exit.  */
-  if (!visited.contains (EXIT_BLOCK_PTR_FOR_FN (fun))
-      && terminating_bbs.is_empty ())
+  if (!visited.contains (EXIT_BLOCK_PTR_FOR_FN (fun)))
     {
       bitmap_set_bit (ret,
 		      single_succ_edge
@@ -945,7 +973,7 @@ find_always_executed_bbs (function *fun, bool assume_return_or_eh)
 	    }
 	  /* DFS is visiting BB for first time.  */
 	  *slot = cstate = XOBNEW (&state_obstack, struct astate);
-	  cstate->low = cstate->dfs_preorder = next_dfs_num++;
+	  cstate->low = cstate->high = cstate->dfs_preorder = next_dfs_num++;
 	  w.cstate = cstate;
 	  /* Exit block is special; process all fake edges we identified.  */
 	  if (bb == EXIT_BLOCK_PTR_FOR_FN (fun))
@@ -981,25 +1009,38 @@ find_always_executed_bbs (function *fun, bool assume_return_or_eh)
 	  if (!cstate2)
 	    {
 	      if (e->src != ENTRY_BLOCK_PTR_FOR_FN (fun))
-	        cstate->low = 0;
+		cstate->low = 0;
 	      continue;
 	    }
 	  cstate->low = MIN (cstate->low, (*cstate2)->low);
 	  cstate->high = MAX (cstate->high, (*cstate2)->high);
 	}
+      if (dump_file && (dump_flags & TDF_DETAILS) && bb != EXIT_BLOCK_PTR_FOR_FN (fun))
+	fprintf (dump_file, "BB %i %s preorder %i posorder %i low %i high %i\n",
+		 bb->index, terminating_bbs_set.contains (bb) ? "(terminating)": "",
+		 cstate->dfs_preorder, cstate->dfs_postorder, cstate->low, cstate->high);
       if (cstate->low == cstate->dfs_preorder && cstate->high == cstate->dfs_postorder
 	  && bb != EXIT_BLOCK_PTR_FOR_FN (fun))
 	bitmap_set_bit (ret, bb->index);
-      FOR_EACH_EDGE (e, ei, bb->succs)
-	{
-	  astate **cstate2 = state.get (e->dest);
-	  if (!cstate2)
-	    continue;
-	  cstate->low = MIN (cstate->low, (*cstate2)->low);
-	  cstate->high = MAX (cstate->high, (*cstate2)->high);
-	}
-    }
+      if (terminating_bbs_set.contains (bb))
+	cstate->low = 0;
+      else
+	FOR_EACH_EDGE (e, ei, bb->succs)
+	  {
+	    astate **cstate2 = state.get (e->dest);
+	    if (!cstate2)
+	      continue;
+	    cstate->low = MIN (cstate->low, (*cstate2)->low);
+	    cstate->high = MAX (cstate->high, (*cstate2)->high);
+	  }
+      }
   obstack_free (&state_obstack, NULL);
+  if (dump_file)
+    {
+      fprintf (dump_file, "Always executed bbbs %s: ",
+	       assume_return_or_eh ? "(assuming return or EH)": "");
+      bitmap_print (dump_file, ret, "", "\n");
+    }
 
   return ret;
 }
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-sra-30.c b/gcc/testsuite/gcc.dg/ipa/ipa-sra-30.c
new file mode 100644
index 00000000000..5c8e8ed8ca1
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-sra-30.c
@@ -0,0 +1,31 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-ipa-sra"  } */
+struct list
+{
+	 struct list *next;
+	 int val;
+};
+__attribute__ ((noinline))
+static int reta (int *a)
+{
+	return *a;
+}
+__attribute__ ((noinline))
+static int
+kill(struct list *l, int *a)
+{
+	int v;
+	while (l)
+	{
+		v = l->val;
+		l=l->next;
+	}
+	return reta (a) + v;
+}
+int
+test(struct list *l, int *a)
+{
+	return kill (l, a);
+}
+/* Loop in kill may be infinite; do not SRA.  */
+/* { dg-final { scan-ipa-dump-not "Created new node kill.isra"  "sra"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-sra-31.c b/gcc/testsuite/gcc.dg/ipa/ipa-sra-31.c
new file mode 100644
index 00000000000..0a636d66872
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-sra-31.c
@@ -0,0 +1,4 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-ipa-sra -ffinite-loops"  } */
+#include "ipa-sra-30.c"
+/* { dg-final { scan-ipa-dump "Created new node kill.isra"  "sra"  } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modref-dse-7.c b/gcc/testsuite/gcc.dg/tree-ssa/modref-dse-7.c
new file mode 100644
index 00000000000..85a01d30cea
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/modref-dse-7.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized"  } */
+struct list
+{
+	 struct list *next;
+};
+__attribute__ ((noinline))
+void
+kill(struct list *l, int *a)
+{
+	while (l)
+		l=l->next;
+	*a = 0;
+}
+void
+test(struct list *l, int *a)
+{
+	*a=12345;
+	kill (l, a);
+	return;
+}
+/* { dg-final { scan-tree-dump-not "12345" "optimized"} } */
diff --git a/gcc/tree-ssa-alias.cc b/gcc/tree-ssa-alias.cc
index b8f107dfa52..7089e8b5bf3 100644
--- a/gcc/tree-ssa-alias.cc
+++ b/gcc/tree-ssa-alias.cc
@@ -3522,6 +3522,7 @@ stmt_kills_ref_p (gimple *stmt, ao_ref *ref)
 			       "ipa-modref: call to %s kills ",
 			       node->dump_name ());
 		      print_generic_expr (dump_file, ref->base);
+		      fprintf (dump_file, "\n");
 		    }
 		    ++alias_stats.modref_kill_yes;
 		    return true;