gcc/gimple-warn-recursion.c

   1 /* -Winfinite-recursion support.
   2    Copyright (C) 2021 Free Software Foundation, Inc.
   3    Contributed by Martin Sebor <msebor@redhat.com>
   4
   5    This file is part of GCC.
   6
   7    GCC is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3, or (at your option)
  10    any later version.
  11
  12    GCC is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GCC; see the file COPYING3.  If not see
  19    <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "backend.h"
  25 #include "tree.h"
  26 #include "gimple.h"
  27 #include "tree-pass.h"
  28 #include "ssa.h"
  29 #include "diagnostic-core.h"
  30 // #include "tree-dfa.h"
  31 #include "attribs.h"
  32 #include "gimple-iterator.h"
  33
  34 namespace {
  35
  36 const pass_data warn_recursion_data =
  37 {
  38   GIMPLE_PASS, /* type */
  39   "*infinite-recursion", /* name */
  40   OPTGROUP_NONE, /* optinfo_flags */
  41   TV_NONE, /* tv_id */
  42   PROP_ssa, /* properties_required */
  43   0, /* properties_provided */
  44   0, /* properties_destroyed */
  45   0, /* todo_flags_start */
  46   0, /* todo_flags_finish */
  47 };
  48
  49 class pass_warn_recursion : public gimple_opt_pass
  50 {
  51 public:
  52   pass_warn_recursion (gcc::context *);
  53
  54 private:
  55   virtual bool gate (function *) { return warn_infinite_recursion; }
  56
  57   virtual unsigned int execute (function *);
  58
  59   bool find_function_exit (basic_block);
  60
  61   /* Recursive calls found in M_FUNC.  */
  62   vec<gimple *> *m_calls;
  63   /* Basic blocks already visited in the current function.  */
  64   bitmap m_visited;
  65   /* The current function.  */
  66   function *m_func;
  67   /* The current function code if it's (also) a built-in.  */
  68   built_in_function m_built_in;
  69   /* True if M_FUNC is a noreturn function.  */
  70   bool noreturn_p;
  71 };
  72
  73 /* Initialize the pass and its members.  */
  74
  75 pass_warn_recursion::pass_warn_recursion (gcc::context *ctxt)
  76   : gimple_opt_pass (warn_recursion_data, ctxt),
  77     m_calls (), m_visited (), m_func (), m_built_in (), noreturn_p ()
  78 {
  79 }
  80
  81 /* Return true if there is path from BB to M_FUNC exit point along which
  82    there is no (recursive) call to M_FUNC.  */
  83
  84 bool
  85 pass_warn_recursion::find_function_exit (basic_block bb)
  86 {
  87   if (!bitmap_set_bit (m_visited, bb->index))
  88     return false;
  89
  90   if (bb == EXIT_BLOCK_PTR_FOR_FN (m_func))
  91     return true;
  92
  93   /* Iterate over statements in BB, looking for a call to FNDECL.  */
  94   for (auto si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next_nondebug (&si))
  95     {
  96       gimple *stmt = gsi_stmt (si);
  97       if (!is_gimple_call (stmt))
  98         continue;
  99
 100       if (gimple_call_builtin_p (stmt, BUILT_IN_LONGJMP))
 101         /* A longjmp breaks infinite recursion.  */
 102         return true;
 103
 104       if (tree fndecl = gimple_call_fndecl (stmt))
 105         {
 106           /* A throw statement breaks infinite recursion.  */
 107           tree id = DECL_NAME (fndecl);
 108           const char *name = IDENTIFIER_POINTER (id);
 109           if (startswith (name, "__cxa_throw"))
 110             return true;
 111           /* As does a call to POSIX siglongjmp.  */
 112           if (!strcmp (name, "siglongjmp"))
 113             return true;
 114
 115           if (m_built_in && gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)
 116               && m_built_in == DECL_FUNCTION_CODE (fndecl))
 117             {
 118               /* The call is being made from the definition of a built-in
 119                  (e.g., in a replacement of one) to itself.  */
 120               m_calls->safe_push (stmt);
 121               return false;
 122             }
 123         }
 124
 125       if (noreturn_p)
 126         {
 127           /* A noreturn call breaks infinite recursion.  */
 128           int flags = gimple_call_flags (stmt);
 129           if (flags & ECF_NORETURN)
 130             return true;
 131         }
 132
 133       tree callee = gimple_call_fndecl (stmt);
 134       if (!callee || m_func->decl != callee)
 135         continue;
 136
 137       /* Add the recursive call to the vector and return false.  */
 138       m_calls->safe_push (stmt);
 139       return false;
 140     }
 141
 142   /* If no call to FNDECL has been found search all BB's successors.  */
 143   edge e;
 144   edge_iterator ei;
 145   FOR_EACH_EDGE (e, ei, bb->succs)
 146     if (find_function_exit (e->dest))
 147       return true;
 148
 149   return false;
 150 }
 151
 152
 153 /* Search FUNC for unconditionally infinitely recursive calls to self
 154    and issue a warning if it is such a function.  */
 155
 156 unsigned int
 157 pass_warn_recursion::execute (function *func)
 158 {
 159   auto_bitmap visited;
 160   auto_vec<gimple *> calls;
 161
 162   m_visited = visited;
 163   m_calls = &calls;
 164   m_func = func;
 165
 166   /* Avoid diagnosing an apparently infinitely recursive function that
 167      doesn't return where the infinite recursion might be avoided by
 168      a call to another noreturn function.  */
 169   noreturn_p = lookup_attribute ("noreturn", DECL_ATTRIBUTES (m_func->decl));
 170
 171   if (fndecl_built_in_p (m_func->decl, BUILT_IN_NORMAL))
 172     m_built_in = DECL_FUNCTION_CODE (m_func->decl);
 173   else
 174     m_built_in = BUILT_IN_NONE;
 175
 176   basic_block entry_bb = ENTRY_BLOCK_PTR_FOR_FN (func);
 177
 178   if (find_function_exit (entry_bb) || m_calls->length () == 0)
 179     return 0;
 180
 181   if (warning_at (DECL_SOURCE_LOCATION (func->decl),
 182                   OPT_Winfinite_recursion,
 183                   "infinite recursion detected"))
 184     for (auto stmt: *m_calls)
 185       {
 186         location_t loc = gimple_location (stmt);
 187         if (loc == UNKNOWN_LOCATION)
 188           continue;
 189
 190         inform (loc, "recursive call");
 191       }
 192
 193   return 0;
 194 }
 195
 196 } // namespace
 197
 198 gimple_opt_pass *
 199 make_pass_warn_recursion (gcc::context *ctxt)
 200 {
 201   return new pass_warn_recursion (ctxt);
 202 }