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 ((unsigned HOST_WIDE_INT
) warn_alloca_limit
> 0
82 || (unsigned HOST_WIDE_INT
) warn_vla_limit
> 0);
85 // Possible problematic uses of alloca.
87 // Alloca argument is within known bounds that are appropriate.
90 // Alloca argument is KNOWN to have a value that is too large.
91 ALLOCA_BOUND_DEFINITELY_LARGE
,
93 // Alloca argument may be too large.
94 ALLOCA_BOUND_MAYBE_LARGE
,
96 // Alloca argument is bounded but of an indeterminate size.
99 // Alloca argument was casted from a signed integer.
100 ALLOCA_CAST_FROM_SIGNED
,
102 // Alloca appears in a loop.
105 // Alloca argument is 0.
108 // Alloca call is unbounded. That is, there is no controlling
109 // predicate for its argument.
113 // Type of an alloca call with its corresponding limit, if applicable.
114 struct 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.
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
) { }
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.
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).
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.
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)
149 // MAX_SIZE is WARN_ALLOCA= adjusted for VLAs. It is the maximum size
150 // in bytes we allow for arg.
152 static struct alloca_type_and_limit
153 alloca_call_type_by_arg (tree arg
, tree arg_casted
, edge e
, unsigned max_size
)
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
);
161 enum tree_code cond_code
= gimple_cond_code (last
);
162 if (e
->flags
& EDGE_TRUE_VALUE
)
164 else if (e
->flags
& EDGE_FALSE_VALUE
)
165 cond_code
= invert_tree_comparison (cond_code
, false);
167 return alloca_type_and_limit (ALLOCA_UNBOUNDED
);
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
))
183 if (TREE_CODE (gimple_cond_rhs (last
)) == INTEGER_CST
)
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
);
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
,
202 return alloca_type_and_limit (ALLOCA_BOUND_UNKNOWN
);
205 // Similarly, but check for a comparison with an unknown LIMIT.
206 // if (LIMIT .COND. ARG)
209 // Where LIMIT has a bound of unknown range.
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
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
)
220 value_range_type range_type
= get_range_info (limit
, &min
, &max
);
222 if (range_type
== VR_UNDEFINED
|| range_type
== VR_VARYING
)
223 return alloca_type_and_limit (ALLOCA_BOUND_UNKNOWN
);
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).
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
);
235 return alloca_type_and_limit (ALLOCA_UNBOUNDED
);
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.
242 cast_from_signed_p (tree ssa
, tree
*invalid_casted_type
)
244 gimple
*def
= SSA_NAME_DEF_STMT (ssa
);
246 && !gimple_nop_p (def
)
247 && gimple_assign_cast_p (def
)
248 && !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def
))))
250 *invalid_casted_type
= TREE_TYPE (gimple_assign_rhs1 (def
));
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.
260 is_max (tree x
, wide_int max
)
262 return wi::max_value (TREE_TYPE (x
)) == max
;
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 is really a BUILT_IN_ALLOCA_WITH_ALIGN, signifying a VLA.
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.
273 static struct alloca_type_and_limit
274 alloca_call_type (gimple
*stmt
, bool is_vla
, tree
*invalid_casted_type
)
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
;
281 struct alloca_type_and_limit ret
= alloca_type_and_limit (ALLOCA_UNBOUNDED
);
283 gcc_assert (!is_vla
|| (unsigned HOST_WIDE_INT
) warn_vla_limit
> 0);
284 gcc_assert (is_vla
|| (unsigned HOST_WIDE_INT
) warn_alloca_limit
> 0);
286 // Adjust warn_alloca_max_size for VLAs, by taking the underlying
287 // type into account.
288 unsigned HOST_WIDE_INT max_size
;
290 max_size
= (unsigned HOST_WIDE_INT
) warn_vla_limit
;
292 max_size
= (unsigned HOST_WIDE_INT
) warn_alloca_limit
;
294 // Check for the obviously bounded case.
295 if (TREE_CODE (len
) == INTEGER_CST
)
297 if (tree_to_uhwi (len
) > max_size
)
298 return alloca_type_and_limit (ALLOCA_BOUND_DEFINITELY_LARGE
,
300 if (integer_zerop (len
))
301 return alloca_type_and_limit (ALLOCA_ARG_IS_ZERO
);
302 ret
= alloca_type_and_limit (ALLOCA_OK
);
304 // Check the range info if available.
305 else if (TREE_CODE (len
) == SSA_NAME
)
307 value_range_type range_type
= get_range_info (len
, &min
, &max
);
308 if (range_type
== VR_RANGE
)
310 if (wi::leu_p (max
, max_size
))
311 ret
= alloca_type_and_limit (ALLOCA_OK
);
314 // A cast may have created a range we don't care
315 // about. For instance, a cast from 16-bit to
316 // 32-bit creates a range of 0..65535, even if there
317 // is not really a determinable range in the
318 // underlying code. In this case, look through the
319 // cast at the original argument, and fall through
320 // to look at other alternatives.
322 // We only look at through the cast when its from
323 // unsigned to unsigned, otherwise we may risk
324 // looking at SIGNED_INT < N, which is clearly not
325 // what we want. In this case, we'd be interested
326 // in a VR_RANGE of [0..N].
328 // Note: None of this is perfect, and should all go
329 // away with better range information. But it gets
330 // most of the cases.
331 gimple
*def
= SSA_NAME_DEF_STMT (len
);
332 if (gimple_assign_cast_p (def
))
334 tree rhs1
= gimple_assign_rhs1 (def
);
335 tree rhs1type
= TREE_TYPE (rhs1
);
337 // Bail if the argument type is not valid.
338 if (!INTEGRAL_TYPE_P (rhs1type
))
339 return alloca_type_and_limit (ALLOCA_OK
);
341 if (TYPE_UNSIGNED (rhs1type
))
344 range_type
= get_range_info (len_casted
, &min
, &max
);
347 // An unknown range or a range of the entire domain is
348 // really no range at all.
349 if (range_type
== VR_VARYING
350 || (!len_casted
&& is_max (len
, max
))
351 || (len_casted
&& is_max (len_casted
, max
)))
355 else if (range_type
== VR_ANTI_RANGE
)
356 return alloca_type_and_limit (ALLOCA_UNBOUNDED
);
357 else if (range_type
!= VR_VARYING
)
358 return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE
, max
);
361 else if (range_type
== VR_ANTI_RANGE
)
363 // There may be some wrapping around going on. Catch it
364 // with this heuristic. Hopefully, this VR_ANTI_RANGE
365 // nonsense will go away, and we won't have to catch the
366 // sign conversion problems with this crap.
368 // This is here to catch things like:
369 // void foo(signed int n) {
374 if (cast_from_signed_p (len
, invalid_casted_type
))
376 // Unfortunately this also triggers:
378 // __SIZE_TYPE__ n = (__SIZE_TYPE__)blah;
382 // ...which is clearly bounded. So, double check that
383 // the paths leading up to the size definitely don't
385 tentative_cast_from_signed
= true;
388 // No easily determined range and try other things.
391 // If we couldn't find anything, try a few heuristics for things we
392 // can easily determine. Check these misc cases but only accept
393 // them if all predecessors have a known bound.
394 basic_block bb
= gimple_bb (stmt
);
395 if (ret
.type
== ALLOCA_UNBOUNDED
)
397 ret
.type
= ALLOCA_OK
;
398 for (unsigned ix
= 0; ix
< EDGE_COUNT (bb
->preds
); ix
++)
400 gcc_assert (!len_casted
|| TYPE_UNSIGNED (TREE_TYPE (len_casted
)));
401 ret
= alloca_call_type_by_arg (len
, len_casted
,
402 EDGE_PRED (bb
, ix
), max_size
);
403 if (ret
.type
!= ALLOCA_OK
)
408 if (tentative_cast_from_signed
&& ret
.type
!= ALLOCA_OK
)
409 return alloca_type_and_limit (ALLOCA_CAST_FROM_SIGNED
);
413 // Return TRUE if the alloca call in STMT is in a loop, otherwise
414 // return FALSE. As an exception, ignore alloca calls for VLAs that
415 // occur in a loop since those will be cleaned up when they go out of
419 in_loop_p (bool is_vla
, gimple
*stmt
)
421 basic_block bb
= gimple_bb (stmt
);
423 && bb
->loop_father
->header
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
425 // Do not warn on VLAs occurring in a loop, since VLAs are
426 // guaranteed to be cleaned up when they go out of scope.
427 // That is, there is a corresponding __builtin_stack_restore
428 // at the end of the scope in which the VLA occurs.
429 tree fndecl
= gimple_call_fn (stmt
);
430 while (TREE_CODE (fndecl
) == ADDR_EXPR
)
431 fndecl
= TREE_OPERAND (fndecl
, 0);
432 if (DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
434 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_ALLOCA_WITH_ALIGN
)
443 pass_walloca::execute (function
*fun
)
446 FOR_EACH_BB_FN (bb
, fun
)
448 for (gimple_stmt_iterator si
= gsi_start_bb (bb
); !gsi_end_p (si
);
451 gimple
*stmt
= gsi_stmt (si
);
452 location_t loc
= gimple_location (stmt
);
454 if (!gimple_alloca_call_p (stmt
))
456 gcc_assert (gimple_call_num_args (stmt
) >= 1);
458 bool is_vla
= gimple_alloca_call_p (stmt
)
459 && gimple_call_alloca_for_var_p (as_a
<gcall
*> (stmt
));
461 // Strict mode whining for VLAs is handled by the front-end,
462 // so we can safely ignore this case. Also, ignore VLAs if
463 // the user doesn't care about them.
465 && (warn_vla
> 0 || !warn_vla_limit
))
468 if (!is_vla
&& (warn_alloca
|| !warn_alloca_limit
))
471 warning_at (loc
, OPT_Walloca
, G_("use of %<alloca%>"));
475 tree invalid_casted_type
= NULL
;
476 struct alloca_type_and_limit t
477 = alloca_call_type (stmt
, is_vla
, &invalid_casted_type
);
479 // Even if we think the alloca call is OK, make sure it's
481 if (t
.type
== ALLOCA_OK
&& in_loop_p (is_vla
, stmt
))
482 t
= alloca_type_and_limit (ALLOCA_IN_LOOP
);
485 = is_vla
? OPT_Wvla_larger_than_
: OPT_Walloca_larger_than_
;
486 char buff
[WIDE_INT_MAX_PRECISION
/ 4 + 4];
491 case ALLOCA_BOUND_MAYBE_LARGE
:
492 if (warning_at (loc
, wcode
,
493 is_vla
? G_("argument to variable-length array "
495 : G_("argument to %<alloca%> may be too large"))
498 print_decu (t
.limit
, buff
);
499 inform (loc
, G_("limit is %u bytes, but argument "
500 "may be as large as %s"),
501 is_vla
? warn_vla_limit
: warn_alloca_limit
, buff
);
504 case ALLOCA_BOUND_DEFINITELY_LARGE
:
505 if (warning_at (loc
, wcode
,
506 is_vla
? G_("argument to variable-length array "
508 : G_("argument to %<alloca%> is too large"))
511 print_decu (t
.limit
, buff
);
512 inform (loc
, G_("limit is %u bytes, but argument is %s"),
513 is_vla
? warn_vla_limit
: warn_alloca_limit
, buff
);
516 case ALLOCA_BOUND_UNKNOWN
:
517 warning_at (loc
, wcode
,
518 is_vla
? G_("variable-length array bound is unknown")
519 : G_("%<alloca%> bound is unknown"));
521 case ALLOCA_UNBOUNDED
:
522 warning_at (loc
, wcode
,
523 is_vla
? G_("unbounded use of variable-length array")
524 : G_("unbounded use of %<alloca%>"));
527 gcc_assert (!is_vla
);
528 warning_at (loc
, wcode
, G_("use of %<alloca%> within a loop"));
530 case ALLOCA_CAST_FROM_SIGNED
:
531 gcc_assert (invalid_casted_type
!= NULL_TREE
);
532 warning_at (loc
, wcode
,
533 is_vla
? G_("argument to variable-length array "
534 "may be too large due to "
535 "conversion from %qT to %qT")
536 : G_("argument to %<alloca%> may be too large "
537 "due to conversion from %qT to %qT"),
538 invalid_casted_type
, size_type_node
);
540 case ALLOCA_ARG_IS_ZERO
:
541 warning_at (loc
, wcode
,
542 is_vla
? G_("argument to variable-length array "
544 : G_("argument to %<alloca%> is zero"));
555 make_pass_walloca (gcc::context
*ctxt
)
557 return new pass_walloca (ctxt
);