* gcc-interface/decl.c (gnat_to_gnu_entity) <E_Variable>: Translate
[official-gcc.git] / gcc / gimple-ssa-warn-alloca.c
blobae379f90c0c6684f3fed1c13976fb30b07be3468
1 /* Warn on problematic uses of alloca and variable length arrays.
2 Copyright (C) 2016 Free Software Foundation, Inc.
3 Contributed by Aldy Hernandez <aldyh@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
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/>. */
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 "gimple-pretty-print.h"
30 #include "diagnostic-core.h"
31 #include "fold-const.h"
32 #include "gimple-iterator.h"
33 #include "tree-ssa.h"
34 #include "params.h"
35 #include "tree-cfg.h"
36 #include "calls.h"
37 #include "cfgloop.h"
38 #include "intl.h"
40 const pass_data pass_data_walloca = {
41 GIMPLE_PASS,
42 "walloca",
43 OPTGROUP_NONE,
44 TV_NONE,
45 PROP_cfg, // properties_required
46 0, // properties_provided
47 0, // properties_destroyed
48 0, // properties_start
49 0, // properties_finish
52 class pass_walloca : public gimple_opt_pass
54 public:
55 pass_walloca (gcc::context *ctxt)
56 : gimple_opt_pass(pass_data_walloca, ctxt), first_time_p (false)
58 opt_pass *clone () { return new pass_walloca (m_ctxt); }
59 void set_pass_param (unsigned int n, bool param)
61 gcc_assert (n == 0);
62 first_time_p = param;
64 virtual bool gate (function *);
65 virtual unsigned int execute (function *);
67 private:
68 // Set to TRUE the first time we run this pass on a function.
69 bool first_time_p;
72 bool
73 pass_walloca::gate (function *fun ATTRIBUTE_UNUSED)
75 // The first time this pass is called, it is called before
76 // optimizations have been run and range information is unavailable,
77 // so we can only perform strict alloca checking.
78 if (first_time_p)
79 return warn_alloca != 0;
81 return warn_alloca_limit > 0 || warn_vla_limit > 0;
84 // Possible problematic uses of alloca.
85 enum alloca_type {
86 // Alloca argument is within known bounds that are appropriate.
87 ALLOCA_OK,
89 // Alloca argument is KNOWN to have a value that is too large.
90 ALLOCA_BOUND_DEFINITELY_LARGE,
92 // Alloca argument may be too large.
93 ALLOCA_BOUND_MAYBE_LARGE,
95 // Alloca argument is bounded but of an indeterminate size.
96 ALLOCA_BOUND_UNKNOWN,
98 // Alloca argument was casted from a signed integer.
99 ALLOCA_CAST_FROM_SIGNED,
101 // Alloca appears in a loop.
102 ALLOCA_IN_LOOP,
104 // Alloca argument is 0.
105 ALLOCA_ARG_IS_ZERO,
107 // Alloca call is unbounded. That is, there is no controlling
108 // predicate for its argument.
109 ALLOCA_UNBOUNDED
112 // Type of an alloca call with its corresponding limit, if applicable.
113 struct alloca_type_and_limit {
114 enum alloca_type type;
115 // For ALLOCA_BOUND_MAYBE_LARGE and ALLOCA_BOUND_DEFINITELY_LARGE
116 // types, this field indicates the assumed limit if known or
117 // integer_zero_node if unknown. For any other alloca types, this
118 // field is undefined.
119 wide_int limit;
120 alloca_type_and_limit ();
121 alloca_type_and_limit (enum alloca_type type,
122 wide_int i) : type(type), limit(i) { }
123 alloca_type_and_limit (enum alloca_type type) : type(type) { }
126 // NOTE: When we get better range info, this entire function becomes
127 // irrelevant, as it should be possible to get range info for an SSA
128 // name at any point in the program.
130 // We have a few heuristics up our sleeve to determine if a call to
131 // alloca() is within bounds. Try them out and return the type of
132 // alloca call with its assumed limit (if applicable).
134 // Given a known argument (ARG) to alloca() and an EDGE (E)
135 // calculating said argument, verify that the last statement in the BB
136 // in E->SRC is a gate comparing ARG to an acceptable bound for
137 // alloca(). See examples below.
139 // If set, ARG_CASTED is the possible unsigned argument to which ARG
140 // was casted to. This is to handle cases where the controlling
141 // predicate is looking at a casted value, not the argument itself.
142 // arg_casted = (size_t) arg;
143 // if (arg_casted < N)
144 // goto bb3;
145 // else
146 // goto bb5;
148 // MAX_SIZE is WARN_ALLOCA= adjusted for VLAs. It is the maximum size
149 // in bytes we allow for arg.
151 static struct alloca_type_and_limit
152 alloca_call_type_by_arg (tree arg, tree arg_casted, edge e, unsigned max_size)
154 basic_block bb = e->src;
155 gimple_stmt_iterator gsi = gsi_last_bb (bb);
156 gimple *last = gsi_stmt (gsi);
157 if (!last || gimple_code (last) != GIMPLE_COND)
158 return alloca_type_and_limit (ALLOCA_UNBOUNDED);
160 enum tree_code cond_code = gimple_cond_code (last);
161 if (e->flags & EDGE_TRUE_VALUE)
163 else if (e->flags & EDGE_FALSE_VALUE)
164 cond_code = invert_tree_comparison (cond_code, false);
165 else
166 return alloca_type_and_limit (ALLOCA_UNBOUNDED);
168 // Check for:
169 // if (ARG .COND. N)
170 // goto <bb 3>;
171 // else
172 // goto <bb 4>;
173 // <bb 3>:
174 // alloca(ARG);
175 if ((cond_code == LE_EXPR
176 || cond_code == LT_EXPR
177 || cond_code == GT_EXPR
178 || cond_code == GE_EXPR)
179 && (gimple_cond_lhs (last) == arg
180 || gimple_cond_lhs (last) == arg_casted))
182 if (TREE_CODE (gimple_cond_rhs (last)) == INTEGER_CST)
184 tree rhs = gimple_cond_rhs (last);
185 int tst = wi::cmpu (wi::to_widest (rhs), max_size);
186 if ((cond_code == LT_EXPR && tst == -1)
187 || (cond_code == LE_EXPR && (tst == -1 || tst == 0)))
188 return alloca_type_and_limit (ALLOCA_OK);
189 else
191 // Let's not get too specific as to how large the limit
192 // may be. Someone's clearly an idiot when things
193 // degrade into "if (N > Y) alloca(N)".
194 if (cond_code == GT_EXPR || cond_code == GE_EXPR)
195 rhs = integer_zero_node;
196 return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, rhs);
199 else
200 return alloca_type_and_limit (ALLOCA_BOUND_UNKNOWN);
203 // Similarly, but check for a comparison with an unknown LIMIT.
204 // if (LIMIT .COND. ARG)
205 // alloca(arg);
207 // Where LIMIT has a bound of unknown range.
209 // Note: All conditions of the form (ARG .COND. XXXX) where covered
210 // by the previous check above, so we only need to look for (LIMIT
211 // .COND. ARG) here.
212 tree limit = gimple_cond_lhs (last);
213 if ((gimple_cond_rhs (last) == arg
214 || gimple_cond_rhs (last) == arg_casted)
215 && TREE_CODE (limit) == SSA_NAME)
217 wide_int min, max;
218 value_range_type range_type = get_range_info (limit, &min, &max);
220 if (range_type == VR_UNDEFINED || range_type == VR_VARYING)
221 return alloca_type_and_limit (ALLOCA_BOUND_UNKNOWN);
223 // ?? It looks like the above `if' is unnecessary, as we never
224 // get any VR_RANGE or VR_ANTI_RANGE here. If we had a range
225 // for LIMIT, I suppose we would have taken care of it in
226 // alloca_call_type(), or handled above where we handle (ARG .COND. N).
228 // If this ever triggers, we should probably figure out why and
229 // handle it, though it is likely to be just an ALLOCA_UNBOUNDED.
230 return alloca_type_and_limit (ALLOCA_UNBOUNDED);
233 return alloca_type_and_limit (ALLOCA_UNBOUNDED);
236 // Return TRUE if SSA's definition is a cast from a signed type.
237 // If so, set *INVALID_CASTED_TYPE to the signed type.
239 static bool
240 cast_from_signed_p (tree ssa, tree *invalid_casted_type)
242 gimple *def = SSA_NAME_DEF_STMT (ssa);
243 if (def
244 && !gimple_nop_p (def)
245 && gimple_assign_cast_p (def)
246 && !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def))))
248 *invalid_casted_type = TREE_TYPE (gimple_assign_rhs1 (def));
249 return true;
251 return false;
254 // Return TRUE if X has a maximum range of MAX, basically covering the
255 // entire domain, in which case it's no range at all.
257 static bool
258 is_max (tree x, wide_int max)
260 return wi::max_value (TREE_TYPE (x)) == max;
263 // Analyze the alloca call in STMT and return the alloca type with its
264 // corresponding limit (if applicable). IS_VLA is set if the alloca
265 // call is really a BUILT_IN_ALLOCA_WITH_ALIGN, signifying a VLA.
267 // If the alloca call may be too large because of a cast from a signed
268 // type to an unsigned type, set *INVALID_CASTED_TYPE to the
269 // problematic signed type.
271 static struct alloca_type_and_limit
272 alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type)
274 gcc_assert (gimple_alloca_call_p (stmt));
275 tree len = gimple_call_arg (stmt, 0);
276 tree len_casted = NULL;
277 wide_int min, max;
278 struct alloca_type_and_limit ret = alloca_type_and_limit (ALLOCA_UNBOUNDED);
280 gcc_assert (!is_vla || warn_vla_limit > 0);
281 gcc_assert (is_vla || warn_alloca_limit > 0);
283 // Adjust warn_alloca_max_size for VLAs, by taking the underlying
284 // type into account.
285 unsigned HOST_WIDE_INT max_size;
286 if (is_vla)
287 max_size = (unsigned HOST_WIDE_INT) warn_vla_limit;
288 else
289 max_size = (unsigned HOST_WIDE_INT) warn_alloca_limit;
291 // Check for the obviously bounded case.
292 if (TREE_CODE (len) == INTEGER_CST)
294 if (tree_to_uhwi (len) > max_size)
295 return alloca_type_and_limit (ALLOCA_BOUND_DEFINITELY_LARGE, len);
296 if (integer_zerop (len))
297 return alloca_type_and_limit (ALLOCA_ARG_IS_ZERO);
298 ret = alloca_type_and_limit (ALLOCA_OK);
300 // Check the range info if available.
301 else if (value_range_type range_type = get_range_info (len, &min, &max))
303 if (range_type == VR_RANGE)
305 if (wi::leu_p (max, max_size))
306 ret = alloca_type_and_limit (ALLOCA_OK);
307 else
309 // A cast may have created a range we don't care
310 // about. For instance, a cast from 16-bit to
311 // 32-bit creates a range of 0..65535, even if there
312 // is not really a determinable range in the
313 // underlying code. In this case, look through the
314 // cast at the original argument, and fall through
315 // to look at other alternatives.
317 // We only look at through the cast when its from
318 // unsigned to unsigned, otherwise we may risk
319 // looking at SIGNED_INT < N, which is clearly not
320 // what we want. In this case, we'd be interested
321 // in a VR_RANGE of [0..N].
323 // Note: None of this is perfect, and should all go
324 // away with better range information. But it gets
325 // most of the cases.
326 gimple *def = SSA_NAME_DEF_STMT (len);
327 if (gimple_assign_cast_p (def)
328 && TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def))))
331 len_casted = gimple_assign_rhs1 (def);
332 range_type = get_range_info (len_casted, &min, &max);
334 // An unknown range or a range of the entire domain is
335 // really no range at all.
336 if (range_type == VR_VARYING
337 || (!len_casted && is_max (len, max))
338 || (len_casted && is_max (len_casted, max)))
340 // Fall through.
342 else if (range_type == VR_ANTI_RANGE)
343 return alloca_type_and_limit (ALLOCA_UNBOUNDED);
344 else if (range_type != VR_VARYING)
345 return
346 alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, max);
349 else if (range_type == VR_ANTI_RANGE)
351 // There may be some wrapping around going on. Catch it
352 // with this heuristic. Hopefully, this VR_ANTI_RANGE
353 // nonsense will go away, and we won't have to catch the
354 // sign conversion problems with this crap.
355 if (cast_from_signed_p (len, invalid_casted_type))
356 return alloca_type_and_limit (ALLOCA_CAST_FROM_SIGNED);
358 // No easily determined range and try other things.
361 // If we couldn't find anything, try a few heuristics for things we
362 // can easily determine. Check these misc cases but only accept
363 // them if all predecessors have a known bound.
364 basic_block bb = gimple_bb (stmt);
365 if (ret.type == ALLOCA_UNBOUNDED)
367 ret.type = ALLOCA_OK;
368 for (unsigned ix = 0; ix < EDGE_COUNT (bb->preds); ix++)
370 gcc_assert (!len_casted || TYPE_UNSIGNED (TREE_TYPE (len_casted)));
371 ret = alloca_call_type_by_arg (len, len_casted,
372 EDGE_PRED (bb, ix), max_size);
373 if (ret.type != ALLOCA_OK)
374 return ret;
378 return ret;
381 // Return TRUE if the alloca call in STMT is in a loop, otherwise
382 // return FALSE. As an exception, ignore alloca calls for VLAs that
383 // occur in a loop since those will be cleaned up when they go out of
384 // scope.
386 static bool
387 in_loop_p (bool is_vla, gimple *stmt)
389 basic_block bb = gimple_bb (stmt);
390 if (bb->loop_father
391 && bb->loop_father->header != ENTRY_BLOCK_PTR_FOR_FN (cfun))
393 // Do not warn on VLAs occurring in a loop, since VLAs are
394 // guaranteed to be cleaned up when they go out of scope.
395 // That is, there is a corresponding __builtin_stack_restore
396 // at the end of the scope in which the VLA occurs.
397 tree fndecl = gimple_call_fn (stmt);
398 while (TREE_CODE (fndecl) == ADDR_EXPR)
399 fndecl = TREE_OPERAND (fndecl, 0);
400 if (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
401 && is_vla
402 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_ALLOCA_WITH_ALIGN)
403 return false;
405 return true;
407 return false;
410 unsigned int
411 pass_walloca::execute (function *fun)
413 basic_block bb;
414 FOR_EACH_BB_FN (bb, fun)
416 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
417 gsi_next (&si))
419 gimple *stmt = gsi_stmt (si);
420 location_t loc = gimple_location (stmt);
422 if (!gimple_alloca_call_p (stmt))
423 continue;
424 gcc_assert (gimple_call_num_args (stmt) >= 1);
426 bool is_vla = gimple_alloca_call_p (stmt)
427 && gimple_call_alloca_for_var_p (as_a <gcall *> (stmt));
429 // Strict mode whining for VLAs is handled by the front-end,
430 // so we can safely ignore this case. Also, ignore VLAs if
431 // the user doesn't care about them.
432 if (is_vla
433 && (warn_vla > 0 || !warn_vla_limit))
434 continue;
436 if (!is_vla && (warn_alloca || !warn_alloca_limit))
438 if (warn_alloca)
439 warning_at (loc, OPT_Walloca, G_("use of %<alloca%>"));
440 continue;
443 tree invalid_casted_type = NULL;
444 struct alloca_type_and_limit t
445 = alloca_call_type (stmt, is_vla, &invalid_casted_type);
447 // Even if we think the alloca call is OK, make sure it's
448 // not in a loop.
449 if (t.type == ALLOCA_OK && in_loop_p (is_vla, stmt))
450 t = alloca_type_and_limit (ALLOCA_IN_LOOP);
452 enum opt_code wcode
453 = is_vla ? OPT_Wvla_larger_than_ : OPT_Walloca_larger_than_;
454 char buff[WIDE_INT_MAX_PRECISION / 4 + 4];
455 switch (t.type)
457 case ALLOCA_OK:
458 break;
459 case ALLOCA_BOUND_MAYBE_LARGE:
460 if (warning_at (loc, wcode,
461 is_vla ? G_("argument to variable-length array "
462 "may be too large")
463 : G_("argument to %<alloca%> may be too large"))
464 && t.limit != integer_zero_node)
466 print_decu (t.limit, buff);
467 inform (loc, G_("limit is %u bytes, but argument "
468 "may be as large as %s"),
469 is_vla ? warn_vla_limit : warn_alloca_limit, buff);
471 break;
472 case ALLOCA_BOUND_DEFINITELY_LARGE:
473 if (warning_at (loc, wcode,
474 is_vla ? G_("argument to variable-length array "
475 "is too large")
476 : G_("argument to %<alloca%> is too large"))
477 && t.limit != integer_zero_node)
479 print_decu (t.limit, buff);
480 inform (loc, G_("limit is %u bytes, but argument is %s"),
481 is_vla ? warn_vla_limit : warn_alloca_limit, buff);
483 break;
484 case ALLOCA_BOUND_UNKNOWN:
485 warning_at (loc, wcode,
486 is_vla ? G_("variable-length array bound is unknown")
487 : G_("%<alloca%> bound is unknown"));
488 break;
489 case ALLOCA_UNBOUNDED:
490 warning_at (loc, wcode,
491 is_vla ? G_("unbounded use of variable-length array")
492 : G_("unbounded use of %<alloca%>"));
493 break;
494 case ALLOCA_IN_LOOP:
495 gcc_assert (!is_vla);
496 warning_at (loc, wcode, G_("use of %<alloca%> within a loop"));
497 break;
498 case ALLOCA_CAST_FROM_SIGNED:
499 gcc_assert (invalid_casted_type != NULL_TREE);
500 warning_at (loc, wcode,
501 is_vla ? G_("argument to variable-length array "
502 "may be too large due to "
503 "conversion from %qT to %qT")
504 : G_("argument to %<alloca%> may be too large "
505 "due to conversion from %qT to %qT"),
506 invalid_casted_type, size_type_node);
507 break;
508 case ALLOCA_ARG_IS_ZERO:
509 warning_at (loc, wcode,
510 is_vla ? G_("argument to variable-length array "
511 "is zero")
512 : G_("argument to %<alloca%> is zero"));
513 break;
514 default:
515 gcc_unreachable ();
519 return 0;
522 gimple_opt_pass *
523 make_pass_walloca (gcc::context *ctxt)
525 return new pass_walloca (ctxt);