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 --git a/gcc/ipa-utils.cc b/gcc/ipa-utils.cc
index 3d5633340f11a51aeb4b40dd208dba01f7e1a9c6..8badcc2c1109414373e89859452a0d6f7501a127 100644 (file)
--- 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 (file)
index 0000000..5c8e8ed
--- /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 (file)
index 0000000..0a636d6
--- /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 (file)
index 0000000..85a01d3
--- /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 b8f107dfa52a96200efc80df7cfb102857cd4f9b..7089e8b5bf3807fe26f042a278d31895cf4cfe1b 100644 (file)
--- 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;