Fix failure when -fno-rtti test is run in C++17 or later
[official-gcc.git] / gcc / gimple-ssa-warn-alloca.c
blob434770772ae7b5c8ea74286bfb0b2b9bd2c1e988
1 /* Warn on problematic uses of alloca and variable length arrays.
2 Copyright (C) 2016-2018 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 "builtins.h"
37 #include "calls.h"
38 #include "cfgloop.h"
39 #include "intl.h"
41 const pass_data pass_data_walloca = {
42 GIMPLE_PASS,
43 "walloca",
44 OPTGROUP_NONE,
45 TV_NONE,
46 PROP_cfg, // properties_required
47 0, // properties_provided
48 0, // properties_destroyed
49 0, // properties_start
50 0, // properties_finish
53 class pass_walloca : public gimple_opt_pass
55 public:
56 pass_walloca (gcc::context *ctxt)
57 : gimple_opt_pass(pass_data_walloca, ctxt), first_time_p (false)
59 opt_pass *clone () { return new pass_walloca (m_ctxt); }
60 void set_pass_param (unsigned int n, bool param)
62 gcc_assert (n == 0);
63 first_time_p = param;
65 virtual bool gate (function *);
66 virtual unsigned int execute (function *);
68 private:
69 // Set to TRUE the first time we run this pass on a function.
70 bool first_time_p;
73 bool
74 pass_walloca::gate (function *fun ATTRIBUTE_UNUSED)
76 // The first time this pass is called, it is called before
77 // optimizations have been run and range information is unavailable,
78 // so we can only perform strict alloca checking.
79 if (first_time_p)
80 return warn_alloca != 0;
82 // Warning is disabled when its size limit is greater than PTRDIFF_MAX
83 // for the target maximum, which makes the limit negative since when
84 // represented in signed HOST_WIDE_INT.
85 return warn_alloca_limit >= 0 || warn_vla_limit >= 0;
88 // Possible problematic uses of alloca.
89 enum alloca_type {
90 // Alloca argument is within known bounds that are appropriate.
91 ALLOCA_OK,
93 // Alloca argument is KNOWN to have a value that is too large.
94 ALLOCA_BOUND_DEFINITELY_LARGE,
96 // Alloca argument may be too large.
97 ALLOCA_BOUND_MAYBE_LARGE,
99 // Alloca argument is bounded but of an indeterminate size.
100 ALLOCA_BOUND_UNKNOWN,
102 // Alloca argument was casted from a signed integer.
103 ALLOCA_CAST_FROM_SIGNED,
105 // Alloca appears in a loop.
106 ALLOCA_IN_LOOP,
108 // Alloca argument is 0.
109 ALLOCA_ARG_IS_ZERO,
111 // Alloca call is unbounded. That is, there is no controlling
112 // predicate for its argument.
113 ALLOCA_UNBOUNDED
116 // Type of an alloca call with its corresponding limit, if applicable.
117 struct alloca_type_and_limit {
118 enum alloca_type type;
119 // For ALLOCA_BOUND_MAYBE_LARGE and ALLOCA_BOUND_DEFINITELY_LARGE
120 // types, this field indicates the assumed limit if known or
121 // integer_zero_node if unknown. For any other alloca types, this
122 // field is undefined.
123 wide_int limit;
124 alloca_type_and_limit ();
125 alloca_type_and_limit (enum alloca_type type,
126 wide_int i) : type(type), limit(i) { }
127 alloca_type_and_limit (enum alloca_type type) : type(type) { }
130 // NOTE: When we get better range info, this entire function becomes
131 // irrelevant, as it should be possible to get range info for an SSA
132 // name at any point in the program.
134 // We have a few heuristics up our sleeve to determine if a call to
135 // alloca() is within bounds. Try them out and return the type of
136 // alloca call with its assumed limit (if applicable).
138 // Given a known argument (ARG) to alloca() and an EDGE (E)
139 // calculating said argument, verify that the last statement in the BB
140 // in E->SRC is a gate comparing ARG to an acceptable bound for
141 // alloca(). See examples below.
143 // If set, ARG_CASTED is the possible unsigned argument to which ARG
144 // was casted to. This is to handle cases where the controlling
145 // predicate is looking at a casted value, not the argument itself.
146 // arg_casted = (size_t) arg;
147 // if (arg_casted < N)
148 // goto bb3;
149 // else
150 // goto bb5;
152 // MAX_SIZE is WARN_ALLOCA= adjusted for VLAs. It is the maximum size
153 // in bytes we allow for arg.
155 static struct alloca_type_and_limit
156 alloca_call_type_by_arg (tree arg, tree arg_casted, edge e,
157 unsigned HOST_WIDE_INT max_size)
159 basic_block bb = e->src;
160 gimple_stmt_iterator gsi = gsi_last_bb (bb);
161 gimple *last = gsi_stmt (gsi);
163 const offset_int maxobjsize = tree_to_shwi (max_object_size ());
165 /* When MAX_SIZE is greater than or equal to PTRDIFF_MAX treat
166 allocations that aren't visibly constrained as OK, otherwise
167 report them as (potentially) unbounded. */
168 alloca_type unbounded_result = (max_size < maxobjsize.to_uhwi ()
169 ? ALLOCA_UNBOUNDED : ALLOCA_OK);
171 if (!last || gimple_code (last) != GIMPLE_COND)
173 return alloca_type_and_limit (unbounded_result);
176 enum tree_code cond_code = gimple_cond_code (last);
177 if (e->flags & EDGE_TRUE_VALUE)
179 else if (e->flags & EDGE_FALSE_VALUE)
180 cond_code = invert_tree_comparison (cond_code, false);
181 else
182 return alloca_type_and_limit (unbounded_result);
184 // Check for:
185 // if (ARG .COND. N)
186 // goto <bb 3>;
187 // else
188 // goto <bb 4>;
189 // <bb 3>:
190 // alloca(ARG);
191 if ((cond_code == LE_EXPR
192 || cond_code == LT_EXPR
193 || cond_code == GT_EXPR
194 || cond_code == GE_EXPR)
195 && (gimple_cond_lhs (last) == arg
196 || gimple_cond_lhs (last) == arg_casted))
198 if (TREE_CODE (gimple_cond_rhs (last)) == INTEGER_CST)
200 tree rhs = gimple_cond_rhs (last);
201 int tst = wi::cmpu (wi::to_widest (rhs), max_size);
202 if ((cond_code == LT_EXPR && tst == -1)
203 || (cond_code == LE_EXPR && (tst == -1 || tst == 0)))
204 return alloca_type_and_limit (ALLOCA_OK);
205 else
207 // Let's not get too specific as to how large the limit
208 // may be. Someone's clearly an idiot when things
209 // degrade into "if (N > Y) alloca(N)".
210 if (cond_code == GT_EXPR || cond_code == GE_EXPR)
211 rhs = integer_zero_node;
212 return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE,
213 wi::to_wide (rhs));
216 else
218 /* Analogous to ALLOCA_UNBOUNDED, when MAX_SIZE is greater
219 than or equal to PTRDIFF_MAX, treat allocations with
220 an unknown bound as OK. */
221 alloca_type unknown_result
222 = (max_size < maxobjsize.to_uhwi ()
223 ? ALLOCA_BOUND_UNKNOWN : ALLOCA_OK);
224 return alloca_type_and_limit (unknown_result);
228 // Similarly, but check for a comparison with an unknown LIMIT.
229 // if (LIMIT .COND. ARG)
230 // alloca(arg);
232 // Where LIMIT has a bound of unknown range.
234 // Note: All conditions of the form (ARG .COND. XXXX) where covered
235 // by the previous check above, so we only need to look for (LIMIT
236 // .COND. ARG) here.
237 tree limit = gimple_cond_lhs (last);
238 if ((gimple_cond_rhs (last) == arg
239 || gimple_cond_rhs (last) == arg_casted)
240 && TREE_CODE (limit) == SSA_NAME)
242 wide_int min, max;
243 value_range_type range_type = get_range_info (limit, &min, &max);
245 if (range_type == VR_UNDEFINED || range_type == VR_VARYING)
246 return alloca_type_and_limit (ALLOCA_BOUND_UNKNOWN);
248 // ?? It looks like the above `if' is unnecessary, as we never
249 // get any VR_RANGE or VR_ANTI_RANGE here. If we had a range
250 // for LIMIT, I suppose we would have taken care of it in
251 // alloca_call_type(), or handled above where we handle (ARG .COND. N).
253 // If this ever triggers, we should probably figure out why and
254 // handle it, though it is likely to be just an ALLOCA_UNBOUNDED.
255 return alloca_type_and_limit (unbounded_result);
258 return alloca_type_and_limit (unbounded_result);
261 // Return TRUE if SSA's definition is a cast from a signed type.
262 // If so, set *INVALID_CASTED_TYPE to the signed type.
264 static bool
265 cast_from_signed_p (tree ssa, tree *invalid_casted_type)
267 gimple *def = SSA_NAME_DEF_STMT (ssa);
268 if (def
269 && !gimple_nop_p (def)
270 && gimple_assign_cast_p (def)
271 && !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def))))
273 *invalid_casted_type = TREE_TYPE (gimple_assign_rhs1 (def));
274 return true;
276 return false;
279 // Return TRUE if X has a maximum range of MAX, basically covering the
280 // entire domain, in which case it's no range at all.
282 static bool
283 is_max (tree x, wide_int max)
285 return wi::max_value (TREE_TYPE (x)) == max;
288 // Analyze the alloca call in STMT and return the alloca type with its
289 // corresponding limit (if applicable). IS_VLA is set if the alloca
290 // call was created by the gimplifier for a VLA.
292 // If the alloca call may be too large because of a cast from a signed
293 // type to an unsigned type, set *INVALID_CASTED_TYPE to the
294 // problematic signed type.
296 static struct alloca_type_and_limit
297 alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type)
299 gcc_assert (gimple_alloca_call_p (stmt));
300 bool tentative_cast_from_signed = false;
301 tree len = gimple_call_arg (stmt, 0);
302 tree len_casted = NULL;
303 wide_int min, max;
304 edge_iterator ei;
305 edge e;
307 gcc_assert (!is_vla || warn_vla_limit >= 0);
308 gcc_assert (is_vla || warn_alloca_limit >= 0);
310 // Adjust warn_alloca_max_size for VLAs, by taking the underlying
311 // type into account.
312 unsigned HOST_WIDE_INT max_size;
313 if (is_vla)
314 max_size = warn_vla_limit;
315 else
316 max_size = warn_alloca_limit;
318 // Check for the obviously bounded case.
319 if (TREE_CODE (len) == INTEGER_CST)
321 if (tree_to_uhwi (len) > max_size)
322 return alloca_type_and_limit (ALLOCA_BOUND_DEFINITELY_LARGE,
323 wi::to_wide (len));
324 if (integer_zerop (len))
326 const offset_int maxobjsize
327 = wi::to_offset (max_object_size ());
328 alloca_type result = (max_size < maxobjsize
329 ? ALLOCA_ARG_IS_ZERO : ALLOCA_OK);
330 return alloca_type_and_limit (result);
333 return alloca_type_and_limit (ALLOCA_OK);
336 // Check the range info if available.
337 if (TREE_CODE (len) == SSA_NAME)
339 value_range_type range_type = get_range_info (len, &min, &max);
340 if (range_type == VR_RANGE)
342 if (wi::leu_p (max, max_size))
343 return alloca_type_and_limit (ALLOCA_OK);
344 else
346 // A cast may have created a range we don't care
347 // about. For instance, a cast from 16-bit to
348 // 32-bit creates a range of 0..65535, even if there
349 // is not really a determinable range in the
350 // underlying code. In this case, look through the
351 // cast at the original argument, and fall through
352 // to look at other alternatives.
354 // We only look at through the cast when its from
355 // unsigned to unsigned, otherwise we may risk
356 // looking at SIGNED_INT < N, which is clearly not
357 // what we want. In this case, we'd be interested
358 // in a VR_RANGE of [0..N].
360 // Note: None of this is perfect, and should all go
361 // away with better range information. But it gets
362 // most of the cases.
363 gimple *def = SSA_NAME_DEF_STMT (len);
364 if (gimple_assign_cast_p (def))
366 tree rhs1 = gimple_assign_rhs1 (def);
367 tree rhs1type = TREE_TYPE (rhs1);
369 // Bail if the argument type is not valid.
370 if (!INTEGRAL_TYPE_P (rhs1type))
371 return alloca_type_and_limit (ALLOCA_OK);
373 if (TYPE_UNSIGNED (rhs1type))
375 len_casted = rhs1;
376 range_type = get_range_info (len_casted, &min, &max);
379 // An unknown range or a range of the entire domain is
380 // really no range at all.
381 if (range_type == VR_VARYING
382 || (!len_casted && is_max (len, max))
383 || (len_casted && is_max (len_casted, max)))
385 // Fall through.
387 else if (range_type == VR_ANTI_RANGE)
388 return alloca_type_and_limit (ALLOCA_UNBOUNDED);
390 if (range_type != VR_VARYING)
392 const offset_int maxobjsize
393 = wi::to_offset (max_object_size ());
394 alloca_type result = (max_size < maxobjsize
395 ? ALLOCA_BOUND_MAYBE_LARGE : ALLOCA_OK);
396 return alloca_type_and_limit (result, max);
400 else if (range_type == VR_ANTI_RANGE)
402 // There may be some wrapping around going on. Catch it
403 // with this heuristic. Hopefully, this VR_ANTI_RANGE
404 // nonsense will go away, and we won't have to catch the
405 // sign conversion problems with this crap.
407 // This is here to catch things like:
408 // void foo(signed int n) {
409 // if (n < 100)
410 // alloca(n);
411 // ...
412 // }
413 if (cast_from_signed_p (len, invalid_casted_type))
415 // Unfortunately this also triggers:
417 // __SIZE_TYPE__ n = (__SIZE_TYPE__)blah;
418 // if (n < 100)
419 // alloca(n);
421 // ...which is clearly bounded. So, double check that
422 // the paths leading up to the size definitely don't
423 // have a bound.
424 tentative_cast_from_signed = true;
427 // No easily determined range and try other things.
430 // If we couldn't find anything, try a few heuristics for things we
431 // can easily determine. Check these misc cases but only accept
432 // them if all predecessors have a known bound.
433 struct alloca_type_and_limit ret = alloca_type_and_limit (ALLOCA_OK);
434 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds)
436 gcc_assert (!len_casted || TYPE_UNSIGNED (TREE_TYPE (len_casted)));
437 ret = alloca_call_type_by_arg (len, len_casted, e, max_size);
438 if (ret.type != ALLOCA_OK)
439 break;
442 if (ret.type != ALLOCA_OK && tentative_cast_from_signed)
443 ret = alloca_type_and_limit (ALLOCA_CAST_FROM_SIGNED);
445 // If we have a declared maximum size, we can take it into account.
446 if (ret.type != ALLOCA_OK
447 && gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX))
449 tree arg = gimple_call_arg (stmt, 2);
450 if (compare_tree_int (arg, max_size) <= 0)
451 ret = alloca_type_and_limit (ALLOCA_OK);
452 else
454 const offset_int maxobjsize
455 = wi::to_offset (max_object_size ());
456 alloca_type result = (max_size < maxobjsize
457 ? ALLOCA_BOUND_MAYBE_LARGE : ALLOCA_OK);
458 ret = alloca_type_and_limit (result, wi::to_wide (arg));
462 return ret;
465 // Return TRUE if STMT is in a loop, otherwise return FALSE.
467 static bool
468 in_loop_p (gimple *stmt)
470 basic_block bb = gimple_bb (stmt);
471 return
472 bb->loop_father && bb->loop_father->header != ENTRY_BLOCK_PTR_FOR_FN (cfun);
475 unsigned int
476 pass_walloca::execute (function *fun)
478 basic_block bb;
479 FOR_EACH_BB_FN (bb, fun)
481 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
482 gsi_next (&si))
484 gimple *stmt = gsi_stmt (si);
485 location_t loc = gimple_location (stmt);
487 if (!gimple_alloca_call_p (stmt))
488 continue;
490 const bool is_vla
491 = gimple_call_alloca_for_var_p (as_a <gcall *> (stmt));
493 // Strict mode whining for VLAs is handled by the front-end,
494 // so we can safely ignore this case. Also, ignore VLAs if
495 // the user doesn't care about them.
496 if (is_vla)
498 if (warn_vla > 0 || warn_vla_limit < 0)
499 continue;
501 else if (warn_alloca)
503 warning_at (loc, OPT_Walloca, G_("use of %<alloca%>"));
504 continue;
506 else if (warn_alloca_limit < 0)
507 continue;
509 tree invalid_casted_type = NULL;
510 struct alloca_type_and_limit t
511 = alloca_call_type (stmt, is_vla, &invalid_casted_type);
513 // Even if we think the alloca call is OK, make sure it's not in a
514 // loop, except for a VLA, since VLAs are guaranteed to be cleaned
515 // up when they go out of scope, including in a loop.
516 if (t.type == ALLOCA_OK && !is_vla && in_loop_p (stmt))
518 /* As in other instances, only diagnose this when the limit
519 is less than the maximum valid object size. */
520 const offset_int maxobjsize
521 = wi::to_offset (max_object_size ());
522 if ((unsigned HOST_WIDE_INT) warn_alloca_limit
523 < maxobjsize.to_uhwi ())
524 t = alloca_type_and_limit (ALLOCA_IN_LOOP);
527 enum opt_code wcode
528 = is_vla ? OPT_Wvla_larger_than_ : OPT_Walloca_larger_than_;
529 char buff[WIDE_INT_MAX_PRECISION / 4 + 4];
530 switch (t.type)
532 case ALLOCA_OK:
533 break;
534 case ALLOCA_BOUND_MAYBE_LARGE:
536 auto_diagnostic_group d;
537 if (warning_at (loc, wcode,
538 is_vla ? G_("argument to variable-length "
539 "array may be too large")
540 : G_("argument to %<alloca%> may be too "
541 "large"))
542 && t.limit != 0)
544 print_decu (t.limit, buff);
545 inform (loc, G_("limit is %wu bytes, but argument "
546 "may be as large as %s"),
547 is_vla ? warn_vla_limit : warn_alloca_limit, buff);
550 break;
551 case ALLOCA_BOUND_DEFINITELY_LARGE:
553 auto_diagnostic_group d;
554 if (warning_at (loc, wcode,
555 is_vla ? G_("argument to variable-length"
556 " array is too large")
557 : G_("argument to %<alloca%> is too large"))
558 && t.limit != 0)
560 print_decu (t.limit, buff);
561 inform (loc, G_("limit is %wu bytes, but argument is %s"),
562 is_vla ? warn_vla_limit : warn_alloca_limit,
563 buff);
566 break;
567 case ALLOCA_BOUND_UNKNOWN:
568 warning_at (loc, wcode,
569 is_vla ? G_("variable-length array bound is unknown")
570 : G_("%<alloca%> bound is unknown"));
571 break;
572 case ALLOCA_UNBOUNDED:
573 warning_at (loc, wcode,
574 is_vla ? G_("unbounded use of variable-length array")
575 : G_("unbounded use of %<alloca%>"));
576 break;
577 case ALLOCA_IN_LOOP:
578 gcc_assert (!is_vla);
579 warning_at (loc, wcode, G_("use of %<alloca%> within a loop"));
580 break;
581 case ALLOCA_CAST_FROM_SIGNED:
582 gcc_assert (invalid_casted_type != NULL_TREE);
583 warning_at (loc, wcode,
584 is_vla ? G_("argument to variable-length array "
585 "may be too large due to "
586 "conversion from %qT to %qT")
587 : G_("argument to %<alloca%> may be too large "
588 "due to conversion from %qT to %qT"),
589 invalid_casted_type, size_type_node);
590 break;
591 case ALLOCA_ARG_IS_ZERO:
592 warning_at (loc, wcode,
593 is_vla ? G_("argument to variable-length array "
594 "is zero")
595 : G_("argument to %<alloca%> is zero"));
596 break;
597 default:
598 gcc_unreachable ();
602 return 0;
605 gimple_opt_pass *
606 make_pass_walloca (gcc::context *ctxt)
608 return new pass_walloca (ctxt);