1/* Warn on problematic uses of alloca and variable length arrays.
2 Copyright (C) 2016-2017 Free Software Foundation, Inc.
3 Contributed by Aldy Hernandez <aldyh@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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 "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"
39
40const 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
50};
51
52class pass_walloca : public gimple_opt_pass
53{
54public:
55 pass_walloca (gcc::context *ctxt)
56 : gimple_opt_pass(pass_data_walloca, ctxt), first_time_p (false)
57 {}
58 opt_pass *clone () { return new pass_walloca (m_ctxt); }
59 void set_pass_param (unsigned int n, bool param)
60 {
61 gcc_assert (n == 0);
62 first_time_p = param;
63 }
64 virtual bool gate (function *);
65 virtual unsigned int execute (function *);
66
67 private:
68 // Set to TRUE the first time we run this pass on a function.
69 bool first_time_p;
70};
71
72bool
73pass_walloca::gate (function *fun ATTRIBUTE_UNUSED)
74{
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;
80
81 return ((unsigned HOST_WIDE_INT) warn_alloca_limit > 0
82 || (unsigned HOST_WIDE_INT) warn_vla_limit > 0);
83}
84
85// Possible problematic uses of alloca.
86enum alloca_type {
87 // Alloca argument is within known bounds that are appropriate.
88 ALLOCA_OK,
89
90 // Alloca argument is KNOWN to have a value that is too large.
91 ALLOCA_BOUND_DEFINITELY_LARGE,
92
93 // Alloca argument may be too large.
94 ALLOCA_BOUND_MAYBE_LARGE,
95
96 // Alloca argument is bounded but of an indeterminate size.
97 ALLOCA_BOUND_UNKNOWN,
98
99 // Alloca argument was casted from a signed integer.
100 ALLOCA_CAST_FROM_SIGNED,
101
102 // Alloca appears in a loop.
103 ALLOCA_IN_LOOP,
104
105 // Alloca argument is 0.
106 ALLOCA_ARG_IS_ZERO,
107
108 // Alloca call is unbounded. That is, there is no controlling
109 // predicate for its argument.
110 ALLOCA_UNBOUNDED
111};
112
113// Type of an alloca call with its corresponding limit, if applicable.
114struct alloca_type_and_limit {
115 enum alloca_type type;
116 // For ALLOCA_BOUND_MAYBE_LARGE and ALLOCA_BOUND_DEFINITELY_LARGE
117 // types, this field indicates the assumed limit if known or
118 // integer_zero_node if unknown. For any other alloca types, this
119 // field is undefined.
120 wide_int limit;
121 alloca_type_and_limit ();
122 alloca_type_and_limit (enum alloca_type type,
123 wide_int i) : type(type), limit(i) { }
124 alloca_type_and_limit (enum alloca_type type) : type(type) { }
125};
126
127// NOTE: When we get better range info, this entire function becomes
128// irrelevant, as it should be possible to get range info for an SSA
129// name at any point in the program.
130//
131// We have a few heuristics up our sleeve to determine if a call to
132// alloca() is within bounds. Try them out and return the type of
133// alloca call with its assumed limit (if applicable).
134//
135// Given a known argument (ARG) to alloca() and an EDGE (E)
136// calculating said argument, verify that the last statement in the BB
137// in E->SRC is a gate comparing ARG to an acceptable bound for
138// alloca(). See examples below.
139//
140// If set, ARG_CASTED is the possible unsigned argument to which ARG
141// was casted to. This is to handle cases where the controlling
142// predicate is looking at a casted value, not the argument itself.
143// arg_casted = (size_t) arg;
144// if (arg_casted < N)
145// goto bb3;
146// else
147// goto bb5;
148//
149// MAX_SIZE is WARN_ALLOCA= adjusted for VLAs. It is the maximum size
150// in bytes we allow for arg.
151
152static struct alloca_type_and_limit
153alloca_call_type_by_arg (tree arg, tree arg_casted, edge e, unsigned max_size)
154{
155 basic_block bb = e->src;
156 gimple_stmt_iterator gsi = gsi_last_bb (bb);
157 gimple *last = gsi_stmt (gsi);
158 if (!last || gimple_code (last) != GIMPLE_COND)
159 return alloca_type_and_limit (ALLOCA_UNBOUNDED);
160
161 enum tree_code cond_code = gimple_cond_code (last);
162 if (e->flags & EDGE_TRUE_VALUE)
163 ;
164 else if (e->flags & EDGE_FALSE_VALUE)
165 cond_code = invert_tree_comparison (cond_code, false);
166 else
167 return alloca_type_and_limit (ALLOCA_UNBOUNDED);
168
169 // Check for:
170 // if (ARG .COND. N)
171 // goto <bb 3>;
172 // else
173 // goto <bb 4>;
174 // <bb 3>:
175 // alloca(ARG);
176 if ((cond_code == LE_EXPR
177 || cond_code == LT_EXPR
178 || cond_code == GT_EXPR
179 || cond_code == GE_EXPR)
180 && (gimple_cond_lhs (last) == arg
181 || gimple_cond_lhs (last) == arg_casted))
182 {
183 if (TREE_CODE (gimple_cond_rhs (last)) == INTEGER_CST)
184 {
185 tree rhs = gimple_cond_rhs (last);
186 int tst = wi::cmpu (wi::to_widest (rhs), max_size);
187 if ((cond_code == LT_EXPR && tst == -1)
188 || (cond_code == LE_EXPR && (tst == -1 || tst == 0)))
189 return alloca_type_and_limit (ALLOCA_OK);
190 else
191 {
192 // Let's not get too specific as to how large the limit
193 // may be. Someone's clearly an idiot when things
194 // degrade into "if (N > Y) alloca(N)".
195 if (cond_code == GT_EXPR || cond_code == GE_EXPR)
196 rhs = integer_zero_node;
197 return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE,
198 wi::to_wide (rhs));
199 }
200 }
201 else
202 return alloca_type_and_limit (ALLOCA_BOUND_UNKNOWN);
203 }
204
205 // Similarly, but check for a comparison with an unknown LIMIT.
206 // if (LIMIT .COND. ARG)
207 // alloca(arg);
208 //
209 // Where LIMIT has a bound of unknown range.
210 //
211 // Note: All conditions of the form (ARG .COND. XXXX) where covered
212 // by the previous check above, so we only need to look for (LIMIT
213 // .COND. ARG) here.
214 tree limit = gimple_cond_lhs (last);
215 if ((gimple_cond_rhs (last) == arg
216 || gimple_cond_rhs (last) == arg_casted)
217 && TREE_CODE (limit) == SSA_NAME)
218 {
219 wide_int min, max;
220 value_range_type range_type = get_range_info (limit, &min, &max);
221
222 if (range_type == VR_UNDEFINED || range_type == VR_VARYING)
223 return alloca_type_and_limit (ALLOCA_BOUND_UNKNOWN);
224
225 // ?? It looks like the above `if' is unnecessary, as we never
226 // get any VR_RANGE or VR_ANTI_RANGE here. If we had a range
227 // for LIMIT, I suppose we would have taken care of it in
228 // alloca_call_type(), or handled above where we handle (ARG .COND. N).
229 //
230 // If this ever triggers, we should probably figure out why and
231 // handle it, though it is likely to be just an ALLOCA_UNBOUNDED.
232 return alloca_type_and_limit (ALLOCA_UNBOUNDED);
233 }
234
235 return alloca_type_and_limit (ALLOCA_UNBOUNDED);
236}
237
238// Return TRUE if SSA's definition is a cast from a signed type.
239// If so, set *INVALID_CASTED_TYPE to the signed type.
240
241static bool
242cast_from_signed_p (tree ssa, tree *invalid_casted_type)
243{
244 gimple *def = SSA_NAME_DEF_STMT (ssa);
245 if (def
246 && !gimple_nop_p (def)
247 && gimple_assign_cast_p (def)
248 && !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def))))
249 {
250 *invalid_casted_type = TREE_TYPE (gimple_assign_rhs1 (def));
251 return true;
252 }
253 return false;
254}
255
256// Return TRUE if X has a maximum range of MAX, basically covering the
257// entire domain, in which case it's no range at all.
258
259static bool
260is_max (tree x, wide_int max)
261{
262 return wi::max_value (TREE_TYPE (x)) == max;
263}
264
265// Analyze the alloca call in STMT and return the alloca type with its
266// corresponding limit (if applicable). IS_VLA is set if the alloca
267// call was created by the gimplifier for a VLA.
268//
269// If the alloca call may be too large because of a cast from a signed
270// type to an unsigned type, set *INVALID_CASTED_TYPE to the
271// problematic signed type.
272
273static struct alloca_type_and_limit
274alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type)
275{
276 gcc_assert (gimple_alloca_call_p (stmt));
277 bool tentative_cast_from_signed = false;
278 tree len = gimple_call_arg (stmt, 0);
279 tree len_casted = NULL;
280 wide_int min, max;
281 edge_iterator ei;
282 edge e;
283
284 gcc_assert (!is_vla || (unsigned HOST_WIDE_INT) warn_vla_limit > 0);
285 gcc_assert (is_vla || (unsigned HOST_WIDE_INT) warn_alloca_limit > 0);
286
287 // Adjust warn_alloca_max_size for VLAs, by taking the underlying
288 // type into account.
289 unsigned HOST_WIDE_INT max_size;
290 if (is_vla)
291 max_size = (unsigned HOST_WIDE_INT) warn_vla_limit;
292 else
293 max_size = (unsigned HOST_WIDE_INT) warn_alloca_limit;
294
295 // Check for the obviously bounded case.
296 if (TREE_CODE (len) == INTEGER_CST)
297 {
298 if (tree_to_uhwi (len) > max_size)
299 return alloca_type_and_limit (ALLOCA_BOUND_DEFINITELY_LARGE,
300 wi::to_wide (len));
301 if (integer_zerop (len))
302 return alloca_type_and_limit (ALLOCA_ARG_IS_ZERO);
303
304 return alloca_type_and_limit (ALLOCA_OK);
305 }
306
307 // Check the range info if available.
308 if (TREE_CODE (len) == SSA_NAME)
309 {
310 value_range_type range_type = get_range_info (len, &min, &max);
311 if (range_type == VR_RANGE)
312 {
313 if (wi::leu_p (max, max_size))
314 return alloca_type_and_limit (ALLOCA_OK);
315 else
316 {
317 // A cast may have created a range we don't care
318 // about. For instance, a cast from 16-bit to
319 // 32-bit creates a range of 0..65535, even if there
320 // is not really a determinable range in the
321 // underlying code. In this case, look through the
322 // cast at the original argument, and fall through
323 // to look at other alternatives.
324 //
325 // We only look at through the cast when its from
326 // unsigned to unsigned, otherwise we may risk
327 // looking at SIGNED_INT < N, which is clearly not
328 // what we want. In this case, we'd be interested
329 // in a VR_RANGE of [0..N].
330 //
331 // Note: None of this is perfect, and should all go
332 // away with better range information. But it gets
333 // most of the cases.
334 gimple *def = SSA_NAME_DEF_STMT (len);
335 if (gimple_assign_cast_p (def))
336 {
337 tree rhs1 = gimple_assign_rhs1 (def);
338 tree rhs1type = TREE_TYPE (rhs1);
339
340 // Bail if the argument type is not valid.
341 if (!INTEGRAL_TYPE_P (rhs1type))
342 return alloca_type_and_limit (ALLOCA_OK);
343
344 if (TYPE_UNSIGNED (rhs1type))
345 {
346 len_casted = rhs1;
347 range_type = get_range_info (len_casted, &min, &max);
348 }
349 }
350 // An unknown range or a range of the entire domain is
351 // really no range at all.
352 if (range_type == VR_VARYING
353 || (!len_casted && is_max (len, max))
354 || (len_casted && is_max (len_casted, max)))
355 {
356 // Fall through.
357 }
358 else if (range_type == VR_ANTI_RANGE)
359 return alloca_type_and_limit (ALLOCA_UNBOUNDED);
360 else if (range_type != VR_VARYING)
361 return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, max);
362 }
363 }
364 else if (range_type == VR_ANTI_RANGE)
365 {
366 // There may be some wrapping around going on. Catch it
367 // with this heuristic. Hopefully, this VR_ANTI_RANGE
368 // nonsense will go away, and we won't have to catch the
369 // sign conversion problems with this crap.
370 //
371 // This is here to catch things like:
372 // void foo(signed int n) {
373 // if (n < 100)
374 // alloca(n);
375 // ...
376 // }
377 if (cast_from_signed_p (len, invalid_casted_type))
378 {
379 // Unfortunately this also triggers:
380 //
381 // __SIZE_TYPE__ n = (__SIZE_TYPE__)blah;
382 // if (n < 100)
383 // alloca(n);
384 //
385 // ...which is clearly bounded. So, double check that
386 // the paths leading up to the size definitely don't
387 // have a bound.
388 tentative_cast_from_signed = true;
389 }
390 }
391 // No easily determined range and try other things.
392 }
393
394 // If we couldn't find anything, try a few heuristics for things we
395 // can easily determine. Check these misc cases but only accept
396 // them if all predecessors have a known bound.
397 struct alloca_type_and_limit ret = alloca_type_and_limit (ALLOCA_OK);
398 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds)
399 {
400 gcc_assert (!len_casted || TYPE_UNSIGNED (TREE_TYPE (len_casted)));
401 ret = alloca_call_type_by_arg (len, len_casted, e, max_size);
402 if (ret.type != ALLOCA_OK)
403 break;
404 }
405
406 if (ret.type != ALLOCA_OK && tentative_cast_from_signed)
407 ret = alloca_type_and_limit (ALLOCA_CAST_FROM_SIGNED);
408
409 // If we have a declared maximum size, we can take it into account.
410 if (ret.type != ALLOCA_OK
411 && gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX))
412 {
413 tree arg = gimple_call_arg (stmt, 2);
414 if (compare_tree_int (arg, max_size) <= 0)
415 ret = alloca_type_and_limit (ALLOCA_OK);
416 else
417 ret = alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE,
418 wi::to_wide (arg));
419 }
420
421 return ret;
422}
423
424// Return TRUE if STMT is in a loop, otherwise return FALSE.
425
426static bool
427in_loop_p (gimple *stmt)
428{
429 basic_block bb = gimple_bb (stmt);
430 return
431 bb->loop_father && bb->loop_father->header != ENTRY_BLOCK_PTR_FOR_FN (cfun);
432}
433
434unsigned int
435pass_walloca::execute (function *fun)
436{
437 basic_block bb;
438 FOR_EACH_BB_FN (bb, fun)
439 {
440 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
441 gsi_next (&si))
442 {
443 gimple *stmt = gsi_stmt (si);
444 location_t loc = gimple_location (stmt);
445
446 if (!gimple_alloca_call_p (stmt))
447 continue;
448 gcc_assert (gimple_call_num_args (stmt) >= 1);
449
450 const bool is_vla
451 = gimple_call_alloca_for_var_p (as_a <gcall *> (stmt));
452
453 // Strict mode whining for VLAs is handled by the front-end,
454 // so we can safely ignore this case. Also, ignore VLAs if
455 // the user doesn't care about them.
456 if (is_vla
457 && (warn_vla > 0 || !warn_vla_limit))
458 continue;
459
460 if (!is_vla && (warn_alloca || !warn_alloca_limit))
461 {
462 if (warn_alloca)
463 warning_at (loc, OPT_Walloca, G_("use of %<alloca%>"));
464 continue;
465 }
466
467 tree invalid_casted_type = NULL;
468 struct alloca_type_and_limit t
469 = alloca_call_type (stmt, is_vla, &invalid_casted_type);
470
471 // Even if we think the alloca call is OK, make sure it's not in a
472 // loop, except for a VLA, since VLAs are guaranteed to be cleaned
473 // up when they go out of scope, including in a loop.
474 if (t.type == ALLOCA_OK && !is_vla && in_loop_p (stmt))
475 t = alloca_type_and_limit (ALLOCA_IN_LOOP);
476
477 enum opt_code wcode
478 = is_vla ? OPT_Wvla_larger_than_ : OPT_Walloca_larger_than_;
479 char buff[WIDE_INT_MAX_PRECISION / 4 + 4];
480 switch (t.type)
481 {
482 case ALLOCA_OK:
483 break;
484 case ALLOCA_BOUND_MAYBE_LARGE:
485 if (warning_at (loc, wcode,
486 is_vla ? G_("argument to variable-length array "
487 "may be too large")
488 : G_("argument to %<alloca%> may be too large"))
489 && t.limit != 0)
490 {
491 print_decu (t.limit, buff);
492 inform (loc, G_("limit is %u bytes, but argument "
493 "may be as large as %s"),
494 is_vla ? warn_vla_limit : warn_alloca_limit, buff);
495 }
496 break;
497 case ALLOCA_BOUND_DEFINITELY_LARGE:
498 if (warning_at (loc, wcode,
499 is_vla ? G_("argument to variable-length array "
500 "is too large")
501 : G_("argument to %<alloca%> is too large"))
502 && t.limit != 0)
503 {
504 print_decu (t.limit, buff);
505 inform (loc, G_("limit is %u bytes, but argument is %s"),
506 is_vla ? warn_vla_limit : warn_alloca_limit, buff);
507 }
508 break;
509 case ALLOCA_BOUND_UNKNOWN:
510 warning_at (loc, wcode,
511 is_vla ? G_("variable-length array bound is unknown")
512 : G_("%<alloca%> bound is unknown"));
513 break;
514 case ALLOCA_UNBOUNDED:
515 warning_at (loc, wcode,
516 is_vla ? G_("unbounded use of variable-length array")
517 : G_("unbounded use of %<alloca%>"));
518 break;
519 case ALLOCA_IN_LOOP:
520 gcc_assert (!is_vla);
521 warning_at (loc, wcode, G_("use of %<alloca%> within a loop"));
522 break;
523 case ALLOCA_CAST_FROM_SIGNED:
524 gcc_assert (invalid_casted_type != NULL_TREE);
525 warning_at (loc, wcode,
526 is_vla ? G_("argument to variable-length array "
527 "may be too large due to "
528 "conversion from %qT to %qT")
529 : G_("argument to %<alloca%> may be too large "
530 "due to conversion from %qT to %qT"),
531 invalid_casted_type, size_type_node);
532 break;
533 case ALLOCA_ARG_IS_ZERO:
534 warning_at (loc, wcode,
535 is_vla ? G_("argument to variable-length array "
536 "is zero")
537 : G_("argument to %<alloca%> is zero"));
538 break;
539 default:
540 gcc_unreachable ();
541 }
542 }
543 }
544 return 0;
545}
546
547gimple_opt_pass *
548make_pass_walloca (gcc::context *ctxt)
549{
550 return new pass_walloca (ctxt);
551}
552