[PATCH] implement -Winfinite-recursion [PR88232]

[Marek Polacek]

On Tue, Nov 09, 2021 at 09:28:43PM -0700, Martin Sebor via Gcc-patches wrote:
> 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.

Nice, I've long wanted this warning.  I've made this mistake a couple of
times:

struct S {
  operator int() { return S{}; }
};

and the patch warns about it.
 
> --- 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.

Why do you need this hunk?

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

Why not use e->flags directly?  find_function_exit can't change it AFAICS.

> +	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");
> +    }

I find the shadowing of 'loc' unsightly.  While here, I think 

  if (warning_at (DECL_SOURCE_LOCATION (func->decl), OPT_Winfinite_recursion,
		  "infinite recursion detected"))
    for (auto stmt: calls)
      {
	...
      }

would look neater (and avoids the shadowing), but that's just my opinion.

Marek