public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH] implement -Winfinite-recursion [PR88232]
@ 2021-11-10  4:28 Martin Sebor
  2021-11-10 21:27 ` Marek Polacek
                   ` (2 more replies)
  0 siblings, 3 replies; 9+ messages in thread
From: Martin Sebor @ 2021-11-10  4:28 UTC (permalink / raw)
  To: gcc-patches

[-- Attachment #1: Type: text/plain, Size: 1026 bytes --]

The attached patch adds support to the middle end for detecting
infinitely recursive calls.  The warning is controlled by the new
-Winfinite-recursion option.  The option name is the same as
Clang's.

I scheduled the warning pass to run after early inlining to
detect mutually recursive calls but before tail recursion which
turns some recursive calls into infinite loops and so makes
the two indistinguishable.

The warning detects a superset of problems detected by Clang
(based on its tests).  It detects the problem in PR88232
(the feature request) as well as the one in PR 87742,
an unrelated problem report that was root-caused to bug due
to infinite recursion.

This initial version doesn't attempt to deal with superimposed
symbols, so those might trigger false positives.  I'm not sure
that's something to worry about.

The tests are very light, but those for the exceptional cases
are exceedingly superficial, so it's possible those might harbor
some false positives and negatives.

Tested on x86_64-linux.

Martin


[-- Attachment #2: gcc-88232.diff --]
[-- Type: text/x-patch, Size: 17122 bytes --]

Implement -Winfinite-recursion [PR88232].

Resolves:
PR middle-end/88232 - Please implement -Winfinite-recursion

gcc/ChangeLog:

	PR middle-end/88232
	* Makefile.in (OBJS): Add gimple-warn-recursion.o.
	* common.opt: Add -Winfinite-recursion.
	* doc/invoke.texi (-Winfinite-recursion): Document.
	* passes.def (pass_warn_recursion): Schedule a new pass.
	* tree-pass.h (make_pass_warn_recursion): Declare.
	* gimple-warn-recursion.c: New file.

gcc/c-family/ChangeLog:

	PR middle-end/88232
	* c.opt: Add -Winfinite-recursion.

gcc/testsuite/ChangeLog:

	PR middle-end/88232
	* c-c++-common/attr-used-5.c: Suppress valid warning.
	* c-c++-common/attr-used-6.c: Same.
	* c-c++-common/attr-used-9.c: Same.
	* g++.dg/warn/Winfinite-recursion-2.C: New test.
	* g++.dg/warn/Winfinite-recursion.C: New test.
	* gcc.dg/Winfinite-recursion-2.c: New test.
	* gcc.dg/Winfinite-recursion.c: New test.

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 571e9c28e29..a4344d67f44 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1420,6 +1420,7 @@ OBJS = \
 	gimple-streamer-in.o \
 	gimple-streamer-out.o \
 	gimple-walk.o \
+	gimple-warn-recursion.o \
 	gimplify.o \
 	gimplify-me.o \
 	godump.o \
diff --git a/gcc/c-family/c.opt b/gcc/c-family/c.opt
index 06457ac739e..7fb13f278e8 100644
--- a/gcc/c-family/c.opt
+++ b/gcc/c-family/c.opt
@@ -714,6 +714,10 @@ Wincompatible-pointer-types
 C ObjC Var(warn_incompatible_pointer_types) Init(1) Warning
 Warn when there is a conversion between pointers that have incompatible types.
 
+Winfinite-recursion
+C ObjC C++ LTO ObjC++ Var(warn_infinite_recursion) Warning LangEnabledBy(C ObjC C++ LTO ObjC++, Wall)
+Warn for infinitely recursive calls.
+
 Waddress-of-packed-member
 C ObjC C++ ObjC++ Var(warn_address_of_packed_member) Init(1) Warning
 Warn when the address of packed member of struct or union is taken.
diff --git a/gcc/common.opt b/gcc/common.opt
index 1a5b9bfcca9..bc5b29e7e11 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -629,6 +629,10 @@ Wimplicit-fallthrough=
 Common Var(warn_implicit_fallthrough) RejectNegative Joined UInteger Warning IntegerRange(0, 5)
 Warn when a switch case falls through.
 
+Winfinite-recursion
+Var(warn_infinite_recursion) Warning
+Warn for infinitely recursive calls.
+
 Winline
 Common Var(warn_inline) Warning Optimization
 Warn when an inlined function cannot be inlined.
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 2ea23d07c4c..4444231e91e 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -357,6 +357,7 @@ Objective-C and Objective-C++ Dialects}.
 -Wignored-qualifiers  -Wno-incompatible-pointer-types @gol
 -Wimplicit  -Wimplicit-fallthrough  -Wimplicit-fallthrough=@var{n} @gol
 -Wno-implicit-function-declaration  -Wno-implicit-int @gol
+-Winfinite-recursion @gol
 -Winit-self  -Winline  -Wno-int-conversion  -Wint-in-bool-context @gol
 -Wno-int-to-pointer-cast  -Wno-invalid-memory-model @gol
 -Winvalid-pch  -Wjump-misses-init  -Wlarger-than=@var{byte-size} @gol
@@ -6179,6 +6180,14 @@ is only active when @option{-fdelete-null-pointer-checks} is active,
 which is enabled by optimizations in most targets.  The precision of
 the warnings depends on the optimization options used.
 
+@item -Winfinite-recursion @r{(C, C++, Objective-C and Objective-C++ only)}
+@opindex Winfinite-recursion
+@opindex Wno-infinite-recursion
+Warn about infinitely recursive calls.  The warning is effective at all
+optimization levels but it requires optimization in order to detect
+infinite recursion in calls between two or more functions.
+@option{-Winfinite-recursion} is included in @option{-Wall}.
+
 @item -Winit-self @r{(C, C++, Objective-C and Objective-C++ only)}
 @opindex Winit-self
 @opindex Wno-init-self
diff --git a/gcc/gimple-warn-recursion.c b/gcc/gimple-warn-recursion.c
new file mode 100644
index 00000000000..324e63b2651
--- /dev/null
+++ b/gcc/gimple-warn-recursion.c
@@ -0,0 +1,146 @@
+/* -Winfinite-recursion support.
+   Copyright (C) 2021 Free Software Foundation, Inc.
+   Contributed by Martin Sebor <msebor@redhat.com>
+
+   This file is part of GCC.
+
+   GCC is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3, or (at your option)
+   any later version.
+
+   GCC is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with GCC; see the file COPYING3.  If not see
+   <http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "tree.h"
+#include "gimple.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "diagnostic-core.h"
+#include "tree-dfa.h"
+#include "gimple-iterator.h"
+
+namespace {
+
+const pass_data warn_recursion_data =
+{
+  GIMPLE_PASS, /* type */
+  "*infinite-recursion", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  TV_NONE, /* tv_id */
+  PROP_ssa, /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  0, /* todo_flags_finish */
+};
+
+class pass_warn_recursion : public gimple_opt_pass
+{
+public:
+  pass_warn_recursion (gcc::context *ctxt)
+    : gimple_opt_pass (warn_recursion_data, ctxt)
+  {}
+
+  virtual bool gate (function *) { return warn_infinite_recursion; }
+
+  virtual unsigned int execute (function *);
+
+};
+
+/* Return true if there is path from BB to EXIT_BB along which there is
+   no (recursive) call to FNDECL.  Use VISITED to avoid searching already
+   visited basic blocks.  */
+
+static bool
+find_function_exit (tree fndecl, basic_block bb, int flags,
+		    basic_block exit_bb,
+		    auto_vec<gimple *> &calls, auto_bitmap &visited)
+{
+  if (!bitmap_set_bit (visited, bb->index))
+    return false;
+
+  if (bb == exit_bb)
+    return true;
+
+  /* Iterate over statements in BB, looking for a call to FNDECL.  */
+  for (auto si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next_nondebug (&si))
+    {
+      gimple *stmt = gsi_stmt (si);
+      if (!is_gimple_call (stmt))
+	continue;
+
+      tree callee = gimple_call_fndecl (stmt);
+      if (!fndecl || fndecl != callee)
+	continue;
+
+      /* Add the recursive call to the vector and return false.  */
+      calls.safe_push (stmt);
+      return false;
+    }
+
+  /* If no call to FNDECL has been found search all BB's successors.  */
+  edge e;
+  edge_iterator ei;
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    {
+      int eflags = e->flags;
+      if (find_function_exit (fndecl, e->dest, eflags, exit_bb, calls, visited))
+	return true;
+
+      flags = 0;
+    }
+
+  return (flags & EDGE_EH) != 0;
+}
+
+
+/* Search FUNC for unconditionally infinitely recursive calls to self
+   and issue a warning if it is such a function.  */
+
+unsigned int
+pass_warn_recursion::execute (function *func)
+{
+  auto_bitmap visited;
+  auto_vec<gimple *> calls;
+  basic_block exit_bb = EXIT_BLOCK_PTR_FOR_FN (func);
+  basic_block entry_bb = ENTRY_BLOCK_PTR_FOR_FN (func);
+
+  if (find_function_exit (func->decl, entry_bb, 0, exit_bb, calls, visited)
+      || calls.length () == 0)
+    return 0;
+
+  location_t loc = DECL_SOURCE_LOCATION (func->decl);
+  if (!warning_at (loc, OPT_Winfinite_recursion,
+		   "infinite recursion detected"))
+    return 0;
+
+  for (auto stmt: calls)
+    {
+      location_t loc = gimple_location (stmt);
+      if (loc == UNKNOWN_LOCATION)
+	continue;
+
+      inform (loc, "recursive call");
+    }
+
+  return 0;
+}
+
+} // namespace
+
+gimple_opt_pass *
+make_pass_warn_recursion (gcc::context *ctxt)
+{
+  return new pass_warn_recursion (ctxt);
+}
diff --git a/gcc/passes.def b/gcc/passes.def
index 56dab80a029..918f377cfcf 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -71,6 +71,7 @@ along with GCC; see the file COPYING3.  If not see
       NEXT_PASS (pass_rebuild_cgraph_edges);
       NEXT_PASS (pass_local_fn_summary);
       NEXT_PASS (pass_early_inline);
+      NEXT_PASS (pass_warn_recursion);
       NEXT_PASS (pass_all_early_optimizations);
       PUSH_INSERT_PASSES_WITHIN (pass_all_early_optimizations)
 	  NEXT_PASS (pass_remove_cgraph_callee_edges);
diff --git a/gcc/testsuite/c-c++-common/attr-used-5.c b/gcc/testsuite/c-c++-common/attr-used-5.c
index 448e19f6f0e..7ba5a455706 100644
--- a/gcc/testsuite/c-c++-common/attr-used-5.c
+++ b/gcc/testsuite/c-c++-common/attr-used-5.c
@@ -1,6 +1,6 @@
 /* { dg-do compile } */
 /* { dg-skip-if "non-ELF target" { *-*-darwin* } } */
-/* { dg-options "-Wall -O2" } */
+/* { dg-options "-Wall -Wno-infinite-recursion -O2" } */
 
 struct dtv_slotinfo_list
 {
diff --git a/gcc/testsuite/c-c++-common/attr-used-6.c b/gcc/testsuite/c-c++-common/attr-used-6.c
index b9974e2a4f2..00b128205b6 100644
--- a/gcc/testsuite/c-c++-common/attr-used-6.c
+++ b/gcc/testsuite/c-c++-common/attr-used-6.c
@@ -1,6 +1,6 @@
 /* { dg-do compile } */
 /* { dg-skip-if "non-ELF target" { *-*-darwin* } } */
-/* { dg-options "-Wall -O2" } */
+/* { dg-options "-Wall  -Wno-infinite-recursion -O2" } */
 
 struct dtv_slotinfo_list
 {
diff --git a/gcc/testsuite/c-c++-common/attr-used-9.c b/gcc/testsuite/c-c++-common/attr-used-9.c
index 049c0beb1ee..c4d86c19bc5 100644
--- a/gcc/testsuite/c-c++-common/attr-used-9.c
+++ b/gcc/testsuite/c-c++-common/attr-used-9.c
@@ -1,6 +1,6 @@
 /* { dg-do compile } */
 /* { dg-skip-if "non-ELF target" { *-*-darwin* } } */
-/* { dg-options "-Wall -O2" } */
+/* { dg-options "-Wall -Wno-infinite-recursion -O2" } */
 
 struct dtv_slotinfo_list
 {
diff --git a/gcc/testsuite/g++.dg/warn/Winfinite-recursion-2.C b/gcc/testsuite/g++.dg/warn/Winfinite-recursion-2.C
new file mode 100644
index 00000000000..b3102836664
--- /dev/null
+++ b/gcc/testsuite/g++.dg/warn/Winfinite-recursion-2.C
@@ -0,0 +1,75 @@
+/* PR middle-end/88232 - Please implement -Winfinite-recursion
+   Test case from PR 87742 (see PR 88232, comment 2.
+   { dg-do compile { target c++11 } }
+   { dg-options "-Wall -Winfinite-recursion" } */
+
+namespace std
+{
+class type_info {
+public:
+  void k() const;
+};
+
+} // namespace std
+
+using std::type_info;
+
+template <int a> struct f { static constexpr int c = a; };
+struct h {
+  typedef int e;
+};
+
+template <unsigned long, typename...> struct m;
+template <unsigned long ab, typename i, typename j, typename... ac>
+struct m<ab, i, j, ac...> : m<ab + 1, i, ac...> {};
+template <unsigned long ab, typename j, typename... ac>
+struct m<ab, j, j, ac...> : f<ab> {};
+template <unsigned long, typename...> struct n;
+template <unsigned long ab, typename j, typename... ac>
+struct n<ab, j, ac...> : n<ab - 1, ac...> {};
+template <typename j, typename... ac> struct n<0, j, ac...> : h {};
+template <typename... l> class F {
+  template <typename i> struct I : m<0, i, l...> {};
+  template <int ab> struct s : n<ab, l...> {};
+  static const type_info *const b[];
+  struct G {
+    template <typename ag>
+    operator ag() const       // { dg-warning "-Winfinite-recursion" }
+    {
+      return *this;
+    }
+  };
+  unsigned o;
+  G ah;
+
+public:
+  F();
+  long t() const { return o; }
+  const type_info &m_fn3() const { return *b[o]; }
+  template <int ab> typename s<ab>::e *m_fn4() const {
+    if (o != ab)
+      return nullptr;
+    return ah;
+  }
+  template <int ab> void m_fn5() const {
+    m_fn4<ab>();
+    const type_info &r = m_fn3();
+    r.k();
+  }
+  template <typename i> void u() const { m_fn5<I<i>::c>(); }
+};
+template <typename... l> const type_info *const F<l...>::b[] {&typeid(l)...};
+using am = unsigned char;
+class H {
+  enum bd : am { be = 2 };
+  using bf = F<int, int, H>;
+  bf ah;
+  template <typename bg> void v() const { ah.u<bg>(); }
+  void w() const;
+};
+void H::w() const {
+  bd d = bd(ah.t());
+  switch (d)
+  case be:
+    v<H>();
+}
diff --git a/gcc/testsuite/g++.dg/warn/Winfinite-recursion.C b/gcc/testsuite/g++.dg/warn/Winfinite-recursion.C
new file mode 100644
index 00000000000..26c3d25c414
--- /dev/null
+++ b/gcc/testsuite/g++.dg/warn/Winfinite-recursion.C
@@ -0,0 +1,125 @@
+/* PR middle-end/88232 - Please implement -Winfinite-recursion
+   { dg-do compile }
+   { dg-options "-Wall -Winfinite-recursion" } */
+
+template <typename D>
+struct C
+{
+  void foo ()                 // { dg-warning "-Winfinite-recursion" }
+  {
+    static_cast<D *>(this)->foo ();
+  }
+};
+
+struct D : C<D>
+{
+  // this is missing:
+  // void foo() {}
+};
+
+void f (D *d)
+{
+  d->foo ();
+}
+
+
+struct E : C<D>
+{
+  void foo() {}
+};
+
+void g (E *e)
+{
+  e->foo ();
+}
+
+
+struct X
+{
+  X ();   // might throw
+};
+
+void nowarn_except ()
+{
+  X x;
+  nowarn_except ();
+}
+
+
+void nowarn_try_catch ()
+{
+  try
+    {
+      X x;
+      nowarn_try_catch ();
+    }
+  catch (...)
+    {
+    }
+}
+
+
+void
+warn_try_try_catch_catch ()   // { dg-warning "-Winfinite-recursion" }
+{
+  try
+    {
+      try
+	{
+	  X x;
+	  warn_try_try_catch_catch ();
+	}
+      catch (...)
+	{
+	  warn_try_try_catch_catch ();
+	}
+    }
+  catch (...)
+    {
+      // unreachable
+    }
+}
+
+
+void
+warn_try_catch_rethrow ()     // { dg-warning "-Winfinite-recursion" }
+{
+  try
+    {
+      X x;
+      warn_try_catch_rethrow ();  // { dg-message "recursive call" }
+    }
+  catch (...)
+    {
+      warn_try_catch_rethrow ();  // { dg-message "recursive call" }
+      throw;   // unreachable
+    }
+}
+
+
+void
+warn_try_catch ()             // { dg-warning "-Winfinite-recursion" }
+{
+  try
+    {
+      X x;
+      warn_try_catch ();      // { dg-message "recursive call" }
+    }
+  catch (...)
+    {
+      warn_try_catch ();      // { dg-message "recursive call" }
+    }
+}
+
+void
+warn_try_catch_call ()        // { dg-warning "-Winfinite-recursion" }
+{
+  try
+    {
+      X x;
+      warn_try_catch_call (); // { dg-message "recursive call" }
+    }
+  catch (...) {  }
+
+  warn_try_catch_call ();     // { dg-message "recursive call" }
+}
diff --git a/gcc/testsuite/gcc.dg/Winfinite-recursion-2.c b/gcc/testsuite/gcc.dg/Winfinite-recursion-2.c
new file mode 100644
index 00000000000..0f1e4ef4228
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/Winfinite-recursion-2.c
@@ -0,0 +1,25 @@
+/* PR middle-end/88232 - Please implement -Winfinite-recursion
+   { dg-do compile }
+   { dg-options "-O2 -Wall -Winfinite-recursion" } */
+
+int nowarn_fact (int n)
+{
+  return n ? n * nowarn_fact (n - 1) : 1;
+}
+
+
+static int fi_v (void);
+
+/* It would seem preferable to issue the warning for the extern function
+   but as it happens it's the static function that's inlined into a recursive
+   call to itself and warn_call_fi_v() expands to a call to it.  */
+
+int warn_call_fi_v (void)     // { dg-warning "-Winfinite-recursion" "" { xfail *-*-* } }
+{
+  return fi_v ();             // { dg-message "recursive call" }
+}
+
+static int fi_v (void)        // { dg-warning "-Winfinite-recursion" }
+{
+  return warn_call_fi_v ();
+}
diff --git a/gcc/testsuite/gcc.dg/Winfinite-recursion.c b/gcc/testsuite/gcc.dg/Winfinite-recursion.c
new file mode 100644
index 00000000000..84eb2ace4db
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/Winfinite-recursion.c
@@ -0,0 +1,46 @@
+/* PR middle-end/88232 - Please implement -Winfinite-recursion
+   { dg-do compile }
+   { dg-options "-Wall -Winfinite-recursion" } */
+
+extern int ei;
+
+int warn_fi_v (void)          // { dg-warning "-Winfinite-recursion" }
+{
+  return warn_fi_v ();        // { dg-message "recursive call" }
+}
+
+int nowarn_fi_v (void)
+{
+  if (ei++ == 0)
+    return nowarn_fi_v ();
+  return 0;
+}
+
+int warn_if_i (int i)         // { dg-warning "-Winfinite-recursion" }
+{
+  if (i > 0)
+    return warn_if_i (--i);   // { dg-message "recursive call" }
+  else if (i < 0)
+    return warn_if_i (-i);    // { dg-message "recursive call" }
+  else
+    return warn_if_i (7);     // { dg-message "recursive call" }
+}
+
+
+int nowarn_if_i (int i)
+{
+  if (i > 0)
+    return nowarn_if_i (--i);
+  else if (i < 0)
+    return nowarn_if_i (-i);
+  else
+    return -1;
+}
+
+/* Verify there's no warning for a function that doesn't return.  */
+int nowarn_call_noreturn (void)
+{
+  __attribute__ ((noreturn)) void fnoreturn (void);
+
+  fnoreturn ();
+}
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index d494aff1c4c..3559c3c9f1b 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -435,6 +435,7 @@ extern gimple_opt_pass *make_pass_object_sizes (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_early_object_sizes (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_warn_access (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_warn_printf (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_warn_recursion (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_strlen (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_fold_builtins (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_post_ipa_warn (gcc::context *ctxt);

^ permalink raw reply	[flat|nested] 9+ messages in thread
end of thread, other threads:[~2021-11-24 16:36 UTC | newest]

Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-11-10  4:28 [PATCH] implement -Winfinite-recursion [PR88232] Martin Sebor
2021-11-10 21:27 ` Marek Polacek
2021-11-11 18:21   ` [PATCH v2] " Martin Sebor
2021-11-11 18:26     ` Marek Polacek
2021-11-11 21:46 ` Martin Sebor
2021-11-19 15:11   ` PING " Martin Sebor
2021-11-23 19:11   ` Jeff Law
2021-11-24 10:16 ` [PATCH] " Thomas Schwinge
2021-11-24 16:36   ` Martin Sebor

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).