gcc/gimple-warn-recursion.cc

   1 /* -Winfinite-recursion support.
   2    Copyright (C) 2021-2023 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   bool gate (function *) final override { return warn_infinite_recursion; }
  56
  57   unsigned int execute (function *) final override;
  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
 116               && gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)
 117               && m_built_in == DECL_FUNCTION_CODE (fndecl))
 118             {
 119               const char *cname
 120                 = IDENTIFIER_POINTER (DECL_NAME (current_function_decl));
 121               /* Don't warn about gnu_inline extern inline function
 122                  like strcpy calling __builtin_strcpy, that is fine,
 123                  if some call is made (the builtin isn't expanded inline),
 124                  a call is made to the external definition.  */
 125               if (!(DECL_DECLARED_INLINE_P (current_function_decl)
 126                     && DECL_EXTERNAL (current_function_decl))
 127                   || strcmp (name, cname) == 0)
 128                 {
 129                   /* The call is being made from the definition of a built-in
 130                      (e.g., in a replacement of one) to itself.  */
 131                   m_calls->safe_push (stmt);
 132                   return false;
 133                 }
 134             }
 135         }
 136
 137       if (noreturn_p)
 138         {
 139           /* A noreturn call breaks infinite recursion.  */
 140           int flags = gimple_call_flags (stmt);
 141           if (flags & ECF_NORETURN)
 142             return true;
 143         }
 144
 145       tree callee = gimple_call_fndecl (stmt);
 146       if (!callee || m_func->decl != callee)
 147         continue;
 148
 149       /* Add the recursive call to the vector and return false.  */
 150       m_calls->safe_push (stmt);
 151       return false;
 152     }
 153
 154   /* If no call to FNDECL has been found search all BB's successors.  */
 155   edge e;
 156   edge_iterator ei;
 157   FOR_EACH_EDGE (e, ei, bb->succs)
 158     if (find_function_exit (e->dest))
 159       return true;
 160
 161   return false;
 162 }
 163
 164
 165 /* Search FUNC for unconditionally infinitely recursive calls to self
 166    and issue a warning if it is such a function.  */
 167
 168 unsigned int
 169 pass_warn_recursion::execute (function *func)
 170 {
 171   auto_bitmap visited;
 172   auto_vec<gimple *> calls;
 173
 174   m_visited = visited;
 175   m_calls = &calls;
 176   m_func = func;
 177
 178   /* Avoid diagnosing an apparently infinitely recursive function that
 179      doesn't return where the infinite recursion might be avoided by
 180      a call to another noreturn function.  */
 181   noreturn_p = lookup_attribute ("noreturn", DECL_ATTRIBUTES (m_func->decl));
 182
 183   if (fndecl_built_in_p (m_func->decl, BUILT_IN_NORMAL))
 184     m_built_in = DECL_FUNCTION_CODE (m_func->decl);
 185   else
 186     m_built_in = BUILT_IN_NONE;
 187
 188   basic_block entry_bb = ENTRY_BLOCK_PTR_FOR_FN (func);
 189
 190   if (find_function_exit (entry_bb) || m_calls->length () == 0)
 191     return 0;
 192
 193   if (warning_at (DECL_SOURCE_LOCATION (func->decl),
 194                   OPT_Winfinite_recursion,
 195                   "infinite recursion detected"))
 196     for (auto stmt: *m_calls)
 197       {
 198         location_t loc = gimple_location (stmt);
 199         if (loc == UNKNOWN_LOCATION)
 200           continue;
 201
 202         inform (loc, "recursive call");
 203       }
 204
 205   return 0;
 206 }
 207
 208 } // namespace
 209
 210 gimple_opt_pass *
 211 make_pass_warn_recursion (gcc::context *ctxt)
 212 {
 213   return new pass_warn_recursion (ctxt);
 214 }