public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc r12-2721] tree-optimization/101769 - tail recursion creates possibly infinite loop
@ 2021-08-04 8:36 Richard Biener
0 siblings, 0 replies; only message in thread
From: Richard Biener @ 2021-08-04 8:36 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:4d562591018a51f155a2e5d8b9f3e5860111a327
commit r12-2721-g4d562591018a51f155a2e5d8b9f3e5860111a327
Author: Richard Biener <rguenther@suse.de>
Date: Wed Aug 4 09:22:51 2021 +0200
tree-optimization/101769 - tail recursion creates possibly infinite loop
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).
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.
Diff:
---
gcc/testsuite/g++.dg/tree-ssa/pr101769.C | 56 ++++++++++++++++++++++++++++++++
gcc/tree-tailcall.c | 34 +++++++++++--------
2 files changed, 77 insertions(+), 13 deletions(-)
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
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2021-08-04 8:36 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-08-04 8:36 [gcc r12-2721] tree-optimization/101769 - tail recursion creates possibly infinite loop Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).