1 /* -Winfinite-recursion support.
2 Copyright (C) 2021-2022 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:
gate(function *)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
pass_warn_recursion(gcc::context * ctxt)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
find_function_exit(basic_block bb)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
execute(function * func)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 *
make_pass_warn_recursion(gcc::context * ctxt)211 make_pass_warn_recursion (gcc::context *ctxt)
212 {
213 return new pass_warn_recursion (ctxt);
214 }
215