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 <mse...@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
