[PATCH] tree-optimization/101769 - tail recursion creates possibly infinite loop

[PATCH] tree-optimization/101769 - tail recursion creates possibly infinite loop

[Richard Biener]

This makes tail recursion optimization produce a loop structure
manually rather than relying on loop fixup.  That also allows the
loop to be marked as finite (it would eventually blow the stack
if it were not).

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

2021-08-04  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/101769
	* tree-tailcall.c (eliminate_tail_call): Add the created loop
	for the first recursion and return it via the new output parameter.
	(optimize_tail_call): Pass through new output param.
	(tree_optimize_tail_calls_1): After creating all latches,
	add the created loop to the loop tree.  Do not mark loops for fixup.

	* g++.dg/tree-ssa/pr101769.C: New testcase.
---
 gcc/testsuite/g++.dg/tree-ssa/pr101769.C | 56 ++++++++++++++++++++++++
 gcc/tree-tailcall.c                      | 34 ++++++++------
 2 files changed, 77 insertions(+), 13 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/tree-ssa/pr101769.C

diff --git a/gcc/testsuite/g++.dg/tree-ssa/pr101769.C b/gcc/testsuite/g++.dg/tree-ssa/pr101769.C
new file mode 100644
index 00000000000..4979c42236b
--- /dev/null
+++ b/gcc/testsuite/g++.dg/tree-ssa/pr101769.C
@@ -0,0 +1,56 @@
+// { dg-do compile }
+// { dg-require-effective-target c++11 }
+// { dg-options "-O2 -fdump-tree-optimized" }
+
+struct Node
+{
+  Node*	right;
+  Node*	down;
+};
+
+inline
+void free_node(Node*)
+{
+}
+
+void free_all(Node* n_)
+{
+  if (n_ == nullptr) {
+      return;
+  }
+  free_all(n_->right);
+  do {
+      Node* t = n_->down;
+      free_node(n_);
+      n_ = t;
+  } while (n_);
+}
+
+void free_all2_r(Node* n_)
+{
+  if (n_->right) {
+      free_all2_r(n_->right);
+  }
+  do {
+      Node* t = n_->down;
+      free_node(n_);
+      n_ = t;
+  } while (n_);
+}
+
+void free_all2(Node* n_)
+{
+  if (n_) {
+      free_all2_r(n_);
+  }
+}
+
+void loop(Node* n_)
+{
+  do {
+      n_ = n_->down;
+  } while (n_);
+}
+
+// All functions should be empty.
+// { dg-final { scan-tree-dump-times "<bb " 4 "optimized" } }
diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c
index f2833d25ce8..f2f3a6b6dc1 100644
--- a/gcc/tree-tailcall.c
+++ b/gcc/tree-tailcall.c
@@ -131,9 +131,6 @@ static tree m_acc, a_acc;
 
 static bitmap tailr_arg_needs_copy;
 
-static bool optimize_tail_call (struct tailcall *, bool);
-static void eliminate_tail_call (struct tailcall *);
-
 /* Returns false when the function is not suitable for tail call optimization
    from some reason (e.g. if it takes variable number of arguments).  */
 
@@ -926,10 +923,11 @@ decrease_profile (basic_block bb, profile_count count)
 }
 
 /* Eliminates tail call described by T.  TMP_VARS is a list of
-   temporary variables used to copy the function arguments.  */
+   temporary variables used to copy the function arguments.
+   Allocates *NEW_LOOP if not already done and initializes it.  */
 
 static void
-eliminate_tail_call (struct tailcall *t)
+eliminate_tail_call (struct tailcall *t, class loop *&new_loop)
 {
   tree param, rslt;
   gimple *stmt, *call;
@@ -999,6 +997,16 @@ eliminate_tail_call (struct tailcall *t)
   gcc_assert (e);
   PENDING_STMT (e) = NULL;
 
+  /* Add the new loop.  */
+  if (!new_loop)
+    {
+      new_loop = alloc_loop ();
+      new_loop->header = first;
+      new_loop->finite_p = true;
+    }
+  else
+    gcc_assert (new_loop->header == first);
+
   /* Add phi node entries for arguments.  The ordering of the phi nodes should
      be the same as the ordering of the arguments.  */
   for (param = DECL_ARGUMENTS (current_function_decl),
@@ -1037,11 +1045,12 @@ eliminate_tail_call (struct tailcall *t)
    mark the tailcalls for the sibcall optimization.  */
 
 static bool
-optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
+optimize_tail_call (struct tailcall *t, bool opt_tailcalls,
+		    class loop *&new_loop)
 {
   if (t->tail_recursion)
     {
-      eliminate_tail_call (t);
+      eliminate_tail_call (t, new_loop);
       return true;
     }
 
@@ -1177,12 +1186,15 @@ tree_optimize_tail_calls_1 (bool opt_tailcalls)
       opt_tailcalls = false;
     }
 
+  class loop *new_loop = NULL;
   for (; tailcalls; tailcalls = next)
     {
       next = tailcalls->next;
-      changed |= optimize_tail_call (tailcalls, opt_tailcalls);
+      changed |= optimize_tail_call (tailcalls, opt_tailcalls, new_loop);
       free (tailcalls);
     }
+  if (new_loop)
+    add_loop (new_loop, loops_for_fn (cfun)->tree_root);
 
   if (a_acc || m_acc)
     {
@@ -1198,11 +1210,7 @@ tree_optimize_tail_calls_1 (bool opt_tailcalls)
     }
 
   if (changed)
-    {
-      /* We may have created new loops.  Make them magically appear.  */
-      loops_state_set (LOOPS_NEED_FIXUP);
-      free_dominance_info (CDI_DOMINATORS);
-    }
+    free_dominance_info (CDI_DOMINATORS);
 
   /* Add phi nodes for the virtual operands defined in the function to the
      header of the loop created by tail recursion elimination.  Do so
-- 
2.31.1