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>.
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
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
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/>. */
23 #include "coretypes.h"
27 #include "tree-pass.h"
29 #include "gimple-pretty-print.h"
30 #include "diagnostic-core.h"
31 #include "fold-const.h"
32 #include "gimple-iterator.h"
40 const pass_data pass_data_walloca
= {
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
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
)
64 virtual bool gate (function
*);
65 virtual unsigned int execute (function
*);
68 // Set to TRUE the first time we run this pass on a function.
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.
79 return warn_alloca
!= 0;
81 return warn_alloca_limit
> 0 || warn_vla_limit
> 0;
84 // Possible problematic uses of alloca.
86 // Alloca argument is within known bounds that are appropriate.
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.
98 // Alloca argument was casted from a signed integer.
99 ALLOCA_CAST_FROM_SIGNED
,
101 // Alloca appears in a loop.
104 // Alloca argument is 0.
107 // Alloca call is unbounded. That is, there is no controlling
108 // predicate for its argument.
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.
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)
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);
166 return alloca_type_and_limit (ALLOCA_UNBOUNDED
);
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
);
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
);
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)
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
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
)
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.
240 cast_from_signed_p (tree ssa
, tree
*invalid_casted_type
)
242 gimple
*def
= SSA_NAME_DEF_STMT (ssa
);
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
));
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.
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 bool tentative_cast_from_signed
= false;
276 tree len
= gimple_call_arg (stmt
, 0);
277 tree len_casted
= NULL
;
279 struct alloca_type_and_limit ret
= alloca_type_and_limit (ALLOCA_UNBOUNDED
);
281 gcc_assert (!is_vla
|| warn_vla_limit
> 0);
282 gcc_assert (is_vla
|| warn_alloca_limit
> 0);
284 // Adjust warn_alloca_max_size for VLAs, by taking the underlying
285 // type into account.
286 unsigned HOST_WIDE_INT max_size
;
288 max_size
= (unsigned HOST_WIDE_INT
) warn_vla_limit
;
290 max_size
= (unsigned HOST_WIDE_INT
) warn_alloca_limit
;
292 // Check for the obviously bounded case.
293 if (TREE_CODE (len
) == INTEGER_CST
)
295 if (tree_to_uhwi (len
) > max_size
)
296 return alloca_type_and_limit (ALLOCA_BOUND_DEFINITELY_LARGE
, len
);
297 if (integer_zerop (len
))
298 return alloca_type_and_limit (ALLOCA_ARG_IS_ZERO
);
299 ret
= alloca_type_and_limit (ALLOCA_OK
);
301 // Check the range info if available.
302 else if (value_range_type range_type
= get_range_info (len
, &min
, &max
))
304 if (range_type
== VR_RANGE
)
306 if (wi::leu_p (max
, max_size
))
307 ret
= alloca_type_and_limit (ALLOCA_OK
);
310 // A cast may have created a range we don't care
311 // about. For instance, a cast from 16-bit to
312 // 32-bit creates a range of 0..65535, even if there
313 // is not really a determinable range in the
314 // underlying code. In this case, look through the
315 // cast at the original argument, and fall through
316 // to look at other alternatives.
318 // We only look at through the cast when its from
319 // unsigned to unsigned, otherwise we may risk
320 // looking at SIGNED_INT < N, which is clearly not
321 // what we want. In this case, we'd be interested
322 // in a VR_RANGE of [0..N].
324 // Note: None of this is perfect, and should all go
325 // away with better range information. But it gets
326 // most of the cases.
327 gimple
*def
= SSA_NAME_DEF_STMT (len
);
328 if (gimple_assign_cast_p (def
)
329 && TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def
))))
332 len_casted
= gimple_assign_rhs1 (def
);
333 range_type
= get_range_info (len_casted
, &min
, &max
);
335 // An unknown range or a range of the entire domain is
336 // really no range at all.
337 if (range_type
== VR_VARYING
338 || (!len_casted
&& is_max (len
, max
))
339 || (len_casted
&& is_max (len_casted
, max
)))
343 else if (range_type
== VR_ANTI_RANGE
)
344 return alloca_type_and_limit (ALLOCA_UNBOUNDED
);
345 else if (range_type
!= VR_VARYING
)
347 alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE
, max
);
350 else if (range_type
== VR_ANTI_RANGE
)
352 // There may be some wrapping around going on. Catch it
353 // with this heuristic. Hopefully, this VR_ANTI_RANGE
354 // nonsense will go away, and we won't have to catch the
355 // sign conversion problems with this crap.
357 // This is here to catch things like:
358 // void foo(signed int n) {
363 if (cast_from_signed_p (len
, invalid_casted_type
))
365 // Unfortunately this also triggers:
367 // __SIZE_TYPE__ n = (__SIZE_TYPE__)blah;
371 // ...which is clearly bounded. So, double check that
372 // the paths leading up to the size definitely don't
374 tentative_cast_from_signed
= true;
377 // No easily determined range and try other things.
380 // If we couldn't find anything, try a few heuristics for things we
381 // can easily determine. Check these misc cases but only accept
382 // them if all predecessors have a known bound.
383 basic_block bb
= gimple_bb (stmt
);
384 if (ret
.type
== ALLOCA_UNBOUNDED
)
386 ret
.type
= ALLOCA_OK
;
387 for (unsigned ix
= 0; ix
< EDGE_COUNT (bb
->preds
); ix
++)
389 gcc_assert (!len_casted
|| TYPE_UNSIGNED (TREE_TYPE (len_casted
)));
390 ret
= alloca_call_type_by_arg (len
, len_casted
,
391 EDGE_PRED (bb
, ix
), max_size
);
392 if (ret
.type
!= ALLOCA_OK
)
397 if (tentative_cast_from_signed
&& ret
.type
!= ALLOCA_OK
)
398 return alloca_type_and_limit (ALLOCA_CAST_FROM_SIGNED
);
402 // Return TRUE if the alloca call in STMT is in a loop, otherwise
403 // return FALSE. As an exception, ignore alloca calls for VLAs that
404 // occur in a loop since those will be cleaned up when they go out of
408 in_loop_p (bool is_vla
, gimple
*stmt
)
410 basic_block bb
= gimple_bb (stmt
);
412 && bb
->loop_father
->header
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
414 // Do not warn on VLAs occurring in a loop, since VLAs are
415 // guaranteed to be cleaned up when they go out of scope.
416 // That is, there is a corresponding __builtin_stack_restore
417 // at the end of the scope in which the VLA occurs.
418 tree fndecl
= gimple_call_fn (stmt
);
419 while (TREE_CODE (fndecl
) == ADDR_EXPR
)
420 fndecl
= TREE_OPERAND (fndecl
, 0);
421 if (DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
423 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_ALLOCA_WITH_ALIGN
)
432 pass_walloca::execute (function
*fun
)
435 FOR_EACH_BB_FN (bb
, fun
)
437 for (gimple_stmt_iterator si
= gsi_start_bb (bb
); !gsi_end_p (si
);
440 gimple
*stmt
= gsi_stmt (si
);
441 location_t loc
= gimple_location (stmt
);
443 if (!gimple_alloca_call_p (stmt
))
445 gcc_assert (gimple_call_num_args (stmt
) >= 1);
447 bool is_vla
= gimple_alloca_call_p (stmt
)
448 && gimple_call_alloca_for_var_p (as_a
<gcall
*> (stmt
));
450 // Strict mode whining for VLAs is handled by the front-end,
451 // so we can safely ignore this case. Also, ignore VLAs if
452 // the user doesn't care about them.
454 && (warn_vla
> 0 || !warn_vla_limit
))
457 if (!is_vla
&& (warn_alloca
|| !warn_alloca_limit
))
460 warning_at (loc
, OPT_Walloca
, G_("use of %<alloca%>"));
464 tree invalid_casted_type
= NULL
;
465 struct alloca_type_and_limit t
466 = alloca_call_type (stmt
, is_vla
, &invalid_casted_type
);
468 // Even if we think the alloca call is OK, make sure it's
470 if (t
.type
== ALLOCA_OK
&& in_loop_p (is_vla
, stmt
))
471 t
= alloca_type_and_limit (ALLOCA_IN_LOOP
);
474 = is_vla
? OPT_Wvla_larger_than_
: OPT_Walloca_larger_than_
;
475 char buff
[WIDE_INT_MAX_PRECISION
/ 4 + 4];
480 case ALLOCA_BOUND_MAYBE_LARGE
:
481 if (warning_at (loc
, wcode
,
482 is_vla
? G_("argument to variable-length array "
484 : G_("argument to %<alloca%> may be too large"))
485 && t
.limit
!= integer_zero_node
)
487 print_decu (t
.limit
, buff
);
488 inform (loc
, G_("limit is %u bytes, but argument "
489 "may be as large as %s"),
490 is_vla
? warn_vla_limit
: warn_alloca_limit
, buff
);
493 case ALLOCA_BOUND_DEFINITELY_LARGE
:
494 if (warning_at (loc
, wcode
,
495 is_vla
? G_("argument to variable-length array "
497 : G_("argument to %<alloca%> is too large"))
498 && t
.limit
!= integer_zero_node
)
500 print_decu (t
.limit
, buff
);
501 inform (loc
, G_("limit is %u bytes, but argument is %s"),
502 is_vla
? warn_vla_limit
: warn_alloca_limit
, buff
);
505 case ALLOCA_BOUND_UNKNOWN
:
506 warning_at (loc
, wcode
,
507 is_vla
? G_("variable-length array bound is unknown")
508 : G_("%<alloca%> bound is unknown"));
510 case ALLOCA_UNBOUNDED
:
511 warning_at (loc
, wcode
,
512 is_vla
? G_("unbounded use of variable-length array")
513 : G_("unbounded use of %<alloca%>"));
516 gcc_assert (!is_vla
);
517 warning_at (loc
, wcode
, G_("use of %<alloca%> within a loop"));
519 case ALLOCA_CAST_FROM_SIGNED
:
520 gcc_assert (invalid_casted_type
!= NULL_TREE
);
521 warning_at (loc
, wcode
,
522 is_vla
? G_("argument to variable-length array "
523 "may be too large due to "
524 "conversion from %qT to %qT")
525 : G_("argument to %<alloca%> may be too large "
526 "due to conversion from %qT to %qT"),
527 invalid_casted_type
, size_type_node
);
529 case ALLOCA_ARG_IS_ZERO
:
530 warning_at (loc
, wcode
,
531 is_vla
? G_("argument to variable-length array "
533 : G_("argument to %<alloca%> is zero"));
544 make_pass_walloca (gcc::context
*ctxt
)
546 return new pass_walloca (ctxt
);