1 /* Array bounds checking.
2 Copyright (C) 2005-2021 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
10
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "tree.h"
25 #include "gimple.h"
26 #include "ssa.h"
27 #include "gimple-array-bounds.h"
28 #include "gimple-iterator.h"
29 #include "gimple-walk.h"
30 #include "tree-dfa.h"
31 #include "fold-const.h"
32 #include "diagnostic-core.h"
33 #include "intl.h"
34 #include "tree-vrp.h"
35 #include "alloc-pool.h"
36 #include "vr-values.h"
37 #include "domwalk.h"
38 #include "tree-cfg.h"
39 #include "attribs.h"
40 #include "builtins.h"
41
42 // This purposely returns a value_range, not a value_range_equiv, to
43 // break the dependency on equivalences for this pass.
44
45 const value_range *
get_value_range(const_tree op)46 array_bounds_checker::get_value_range (const_tree op)
47 {
48 return ranges->get_value_range (op);
49 }
50
51 /* Try to determine the DECL that REF refers to. Return the DECL or
52 the expression closest to it. Used in informational notes pointing
53 to referenced objects or function parameters. */
54
55 static tree
get_base_decl(tree ref)56 get_base_decl (tree ref)
57 {
58 tree base = get_base_address (ref);
59 if (DECL_P (base))
60 return base;
61
62 if (TREE_CODE (base) == MEM_REF)
63 base = TREE_OPERAND (base, 0);
64
65 if (TREE_CODE (base) != SSA_NAME)
66 return base;
67
68 do
69 {
70 gimple *def = SSA_NAME_DEF_STMT (base);
71 if (gimple_assign_single_p (def))
72 {
73 base = gimple_assign_rhs1 (def);
74 if (TREE_CODE (base) != ASSERT_EXPR)
75 return base;
76
77 base = TREE_OPERAND (base, 0);
78 if (TREE_CODE (base) != SSA_NAME)
79 return base;
80
81 continue;
82 }
83
84 if (!gimple_nop_p (def))
85 return base;
86
87 break;
88 } while (true);
89
90 tree var = SSA_NAME_VAR (base);
91 if (TREE_CODE (var) != PARM_DECL)
92 return base;
93
94 return var;
95 }
96
97 /* Return the constant byte size of the object or type referenced by
98 the MEM_REF ARG. On success, set *PREF to the DECL or expression
99 ARG refers to. Otherwise return null. */
100
101 static tree
get_ref_size(tree arg,tree * pref)102 get_ref_size (tree arg, tree *pref)
103 {
104 if (TREE_CODE (arg) != MEM_REF)
105 return NULL_TREE;
106
107 arg = TREE_OPERAND (arg, 0);
108 tree type = TREE_TYPE (arg);
109 if (!POINTER_TYPE_P (type))
110 return NULL_TREE;
111
112 type = TREE_TYPE (type);
113 if (TREE_CODE (type) != ARRAY_TYPE)
114 return NULL_TREE;
115
116 tree nbytes = TYPE_SIZE_UNIT (type);
117 if (!nbytes || TREE_CODE (nbytes) != INTEGER_CST)
118 return NULL_TREE;
119
120 *pref = get_base_decl (arg);
121 return nbytes;
122 }
123
124 /* Return true if REF is (likely) an ARRAY_REF to a trailing array member
125 of a struct. It refines array_at_struct_end_p by detecting a pointer
126 to an array and an array parameter declared using the [N] syntax (as
127 opposed to a pointer) and returning false. Set *PREF to the decl or
128 expression REF refers to. */
129
130 static bool
trailing_array(tree arg,tree * pref)131 trailing_array (tree arg, tree *pref)
132 {
133 tree ref = arg;
134 tree base = get_base_decl (arg);
135 while (TREE_CODE (ref) == ARRAY_REF || TREE_CODE (ref) == MEM_REF)
136 ref = TREE_OPERAND (ref, 0);
137
138 if (TREE_CODE (ref) == COMPONENT_REF)
139 {
140 *pref = TREE_OPERAND (ref, 1);
141 tree type = TREE_TYPE (*pref);
142 if (TREE_CODE (type) == ARRAY_TYPE)
143 {
144 /* A multidimensional trailing array is not considered special
145 no matter what its major bound is. */
146 type = TREE_TYPE (type);
147 if (TREE_CODE (type) == ARRAY_TYPE)
148 return false;
149 }
150 }
151 else
152 *pref = base;
153
154 tree basetype = TREE_TYPE (base);
155 if (TREE_CODE (base) == PARM_DECL
156 && POINTER_TYPE_P (basetype))
157 {
158 tree ptype = TREE_TYPE (basetype);
159 if (TREE_CODE (ptype) == ARRAY_TYPE)
160 return false;
161 }
162
163 return array_at_struct_end_p (arg);
164 }
165
166 /* Checks one ARRAY_REF in REF, located at LOCUS. Ignores flexible
167 arrays and "struct" hacks. If VRP can determine that the array
168 subscript is a constant, check if it is outside valid range. If
169 the array subscript is a RANGE, warn if it is non-overlapping with
170 valid range. IGNORE_OFF_BY_ONE is true if the ARRAY_REF is inside
171 a ADDR_EXPR. Return true if a warning has been issued or if
172 no-warning is set. */
173
174 bool
check_array_ref(location_t location,tree ref,bool ignore_off_by_one)175 array_bounds_checker::check_array_ref (location_t location, tree ref,
176 bool ignore_off_by_one)
177 {
178 if (TREE_NO_WARNING (ref))
179 /* Return true to have the caller prevent warnings for enclosing
180 refs. */
181 return true;
182
183 tree low_sub = TREE_OPERAND (ref, 1);
184 tree up_sub = low_sub;
185 tree up_bound = array_ref_up_bound (ref);
186
187 /* Referenced decl if one can be determined. */
188 tree decl = NULL_TREE;
189
190 /* Set for accesses to interior zero-length arrays. */
191 special_array_member sam{ };
192
193 tree up_bound_p1;
194
195 if (!up_bound
196 || TREE_CODE (up_bound) != INTEGER_CST
197 || (warn_array_bounds < 2 && trailing_array (ref, &decl)))
198 {
199 /* Accesses to trailing arrays via pointers may access storage
200 beyond the types array bounds. For such arrays, or for flexible
201 array members, as well as for other arrays of an unknown size,
202 replace the upper bound with a more permissive one that assumes
203 the size of the largest object is PTRDIFF_MAX. */
204 tree eltsize = array_ref_element_size (ref);
205
206 if (TREE_CODE (eltsize) != INTEGER_CST
207 || integer_zerop (eltsize))
208 {
209 up_bound = NULL_TREE;
210 up_bound_p1 = NULL_TREE;
211 }
212 else
213 {
214 tree ptrdiff_max = TYPE_MAX_VALUE (ptrdiff_type_node);
215 tree maxbound = ptrdiff_max;
216 tree arg = TREE_OPERAND (ref, 0);
217
218 const bool compref = TREE_CODE (arg) == COMPONENT_REF;
219 if (compref)
220 {
221 /* Try to determine the size of the trailing array from
222 its initializer (if it has one). */
223 if (tree refsize = component_ref_size (arg, &sam))
224 if (TREE_CODE (refsize) == INTEGER_CST)
225 maxbound = refsize;
226 }
227
228 if (maxbound == ptrdiff_max)
229 {
230 /* Try to determine the size of the base object. Avoid
231 COMPONENT_REF already tried above. Using its DECL_SIZE
232 size wouldn't necessarily be correct if the reference is
233 to its flexible array member initialized in a different
234 translation unit. */
235 poly_int64 off;
236 if (tree base = get_addr_base_and_unit_offset (arg, &off))
237 {
238 if (TREE_CODE (base) == MEM_REF)
239 {
240 /* Try to determine the size from a pointer to
241 an array if BASE is one. */
242 if (tree size = get_ref_size (base, &decl))
243 maxbound = size;
244 }
245 else if (!compref && DECL_P (base))
246 if (tree basesize = DECL_SIZE_UNIT (base))
247 if (TREE_CODE (basesize) == INTEGER_CST)
248 {
249 maxbound = basesize;
250 decl = base;
251 }
252
253 if (known_gt (off, 0))
254 maxbound = wide_int_to_tree (sizetype,
255 wi::sub (wi::to_wide (maxbound),
256 off));
257 }
258 }
259 else
260 maxbound = fold_convert (sizetype, maxbound);
261
262 up_bound_p1 = int_const_binop (TRUNC_DIV_EXPR, maxbound, eltsize);
263
264 if (up_bound_p1 != NULL_TREE)
265 up_bound = int_const_binop (MINUS_EXPR, up_bound_p1,
266 build_int_cst (ptrdiff_type_node, 1));
267 else
268 up_bound = NULL_TREE;
269 }
270 }
271 else
272 up_bound_p1 = int_const_binop (PLUS_EXPR, up_bound,
273 build_int_cst (TREE_TYPE (up_bound), 1));
274
275 tree low_bound = array_ref_low_bound (ref);
276
277 tree artype = TREE_TYPE (TREE_OPERAND (ref, 0));
278
279 bool warned = false;
280
281 /* Empty array. */
282 if (up_bound && tree_int_cst_equal (low_bound, up_bound_p1))
283 warned = warning_at (location, OPT_Warray_bounds,
284 "array subscript %E is outside array bounds of %qT",
285 low_sub, artype);
286
287 const value_range *vr = NULL;
288 if (TREE_CODE (low_sub) == SSA_NAME)
289 {
290 vr = get_value_range (low_sub);
291 if (!vr->undefined_p () && !vr->varying_p ())
292 {
293 low_sub = vr->kind () == VR_RANGE ? vr->max () : vr->min ();
294 up_sub = vr->kind () == VR_RANGE ? vr->min () : vr->max ();
295 }
296 }
297
298 if (warned)
299 ; /* Do nothing. */
300 else if (vr && vr->kind () == VR_ANTI_RANGE)
301 {
302 if (up_bound
303 && TREE_CODE (up_sub) == INTEGER_CST
304 && (ignore_off_by_one
305 ? tree_int_cst_lt (up_bound, up_sub)
306 : tree_int_cst_le (up_bound, up_sub))
307 && TREE_CODE (low_sub) == INTEGER_CST
308 && tree_int_cst_le (low_sub, low_bound))
309 warned = warning_at (location, OPT_Warray_bounds,
310 "array subscript [%E, %E] is outside "
311 "array bounds of %qT",
312 low_sub, up_sub, artype);
313 }
314 else if (up_bound
315 && TREE_CODE (up_sub) == INTEGER_CST
316 && (ignore_off_by_one
317 ? !tree_int_cst_le (up_sub, up_bound_p1)
318 : !tree_int_cst_le (up_sub, up_bound)))
319 warned = warning_at (location, OPT_Warray_bounds,
320 "array subscript %E is above array bounds of %qT",
321 up_sub, artype);
322 else if (TREE_CODE (low_sub) == INTEGER_CST
323 && tree_int_cst_lt (low_sub, low_bound))
324 warned = warning_at (location, OPT_Warray_bounds,
325 "array subscript %E is below array bounds of %qT",
326 low_sub, artype);
327
328 if (!warned && sam == special_array_member::int_0)
329 warned = warning_at (location, OPT_Wzero_length_bounds,
330 (TREE_CODE (low_sub) == INTEGER_CST
331 ? G_("array subscript %E is outside the bounds "
332 "of an interior zero-length array %qT")
333 : G_("array subscript %qE is outside the bounds "
334 "of an interior zero-length array %qT")),
335 low_sub, artype);
336
337 if (warned)
338 {
339 if (dump_file && (dump_flags & TDF_DETAILS))
340 {
341 fprintf (dump_file, "Array bound warning for ");
342 dump_generic_expr (MSG_NOTE, TDF_SLIM, ref);
343 fprintf (dump_file, "\n");
344 }
345
346 /* Avoid more warnings when checking more significant subscripts
347 of the same expression. */
348 ref = TREE_OPERAND (ref, 0);
349 TREE_NO_WARNING (ref) = 1;
350
351 if (decl)
352 ref = decl;
353
354 tree rec = NULL_TREE;
355 if (TREE_CODE (ref) == COMPONENT_REF)
356 {
357 /* For a reference to a member of a struct object also mention
358 the object if it's known. It may be defined in a different
359 function than the out-of-bounds access. */
360 rec = TREE_OPERAND (ref, 0);
361 if (!VAR_P (rec))
362 rec = NULL_TREE;
363 ref = TREE_OPERAND (ref, 1);
364 }
365
366 if (DECL_P (ref))
367 inform (DECL_SOURCE_LOCATION (ref), "while referencing %qD", ref);
368 if (rec && DECL_P (rec))
369 inform (DECL_SOURCE_LOCATION (rec), "defined here %qD", rec);
370 }
371
372 return warned;
373 }
374
375 /* Wrapper around build_array_type_nelts that makes sure the array
376 can be created at all and handles zero sized arrays specially. */
377
378 static tree
build_printable_array_type(tree eltype,unsigned HOST_WIDE_INT nelts)379 build_printable_array_type (tree eltype, unsigned HOST_WIDE_INT nelts)
380 {
381 if (TYPE_SIZE_UNIT (eltype)
382 && TREE_CODE (TYPE_SIZE_UNIT (eltype)) == INTEGER_CST
383 && !integer_zerop (TYPE_SIZE_UNIT (eltype))
384 && TYPE_ALIGN_UNIT (eltype) > 1
385 && wi::zext (wi::to_wide (TYPE_SIZE_UNIT (eltype)),
386 ffs_hwi (TYPE_ALIGN_UNIT (eltype)) - 1) != 0)
387 eltype = TYPE_MAIN_VARIANT (eltype);
388
389 if (nelts)
390 return build_array_type_nelts (eltype, nelts);
391
392 tree idxtype = build_range_type (sizetype, size_zero_node, NULL_TREE);
393 tree arrtype = build_array_type (eltype, idxtype);
394 arrtype = build_distinct_type_copy (TYPE_MAIN_VARIANT (arrtype));
395 TYPE_SIZE (arrtype) = bitsize_zero_node;
396 TYPE_SIZE_UNIT (arrtype) = size_zero_node;
397 return arrtype;
398 }
399
400 /* Checks one MEM_REF in REF, located at LOCATION, for out-of-bounds
401 references to string constants. If VRP can determine that the array
402 subscript is a constant, check if it is outside valid range.
403 If the array subscript is a RANGE, warn if it is non-overlapping
404 with valid range.
405 IGNORE_OFF_BY_ONE is true if the MEM_REF is inside an ADDR_EXPR
406 (used to allow one-past-the-end indices for code that takes
407 the address of the just-past-the-end element of an array).
408 Returns true if a warning has been issued. */
409
410 bool
check_mem_ref(location_t location,tree ref,bool ignore_off_by_one)411 array_bounds_checker::check_mem_ref (location_t location, tree ref,
412 bool ignore_off_by_one)
413 {
414 if (TREE_NO_WARNING (ref))
415 return false;
416
417 tree arg = TREE_OPERAND (ref, 0);
418 /* The constant and variable offset of the reference. */
419 tree cstoff = TREE_OPERAND (ref, 1);
420 tree varoff = NULL_TREE;
421
422 const offset_int maxobjsize = tree_to_shwi (max_object_size ());
423
424 /* The zero-based array or string constant bounds in bytes. Initially
425 set to [-MAXOBJSIZE - 1, MAXOBJSIZE] until a tighter bound is
426 determined. */
427 offset_int arrbounds[2] = { -maxobjsize - 1, maxobjsize };
428
429 /* The minimum and maximum intermediate offset. For a reference
430 to be valid, not only does the final offset/subscript must be
431 in bounds but all intermediate offsets should be as well.
432 GCC may be able to deal gracefully with such out-of-bounds
433 offsets so the checking is only enabled at -Warray-bounds=2
434 where it may help detect bugs in uses of the intermediate
435 offsets that could otherwise not be detectable. */
436 offset_int ioff = wi::to_offset (fold_convert (ptrdiff_type_node, cstoff));
437 offset_int extrema[2] = { 0, wi::abs (ioff) };
438
439 /* The range of the byte offset into the reference. */
440 offset_int offrange[2] = { 0, 0 };
441
442 /* The statement used to allocate the array or null. */
443 gimple *alloc_stmt = NULL;
444 /* For an allocation statement, the low bound of the size range. */
445 offset_int minbound = 0;
446
447 /* Determine the offsets and increment OFFRANGE for the bounds of each.
448 The loop computes the range of the final offset for expressions such
449 as (A + i0 + ... + iN)[CSTOFF] where i0 through iN are SSA_NAMEs in
450 some range. */
451 const unsigned limit = param_ssa_name_def_chain_limit;
452 for (unsigned n = 0; TREE_CODE (arg) == SSA_NAME && n < limit; ++n)
453 {
454 gimple *def = SSA_NAME_DEF_STMT (arg);
455 if (is_gimple_call (def))
456 {
457 /* Determine the byte size of the array from an allocation call. */
458 wide_int sizrng[2];
459 if (gimple_call_alloc_size (def, sizrng))
460 {
461 arrbounds[0] = 0;
462 arrbounds[1] = offset_int::from (sizrng[1], UNSIGNED);
463 minbound = offset_int::from (sizrng[0], UNSIGNED);
464 alloc_stmt = def;
465 }
466 break;
467 }
468
469 if (gimple_nop_p (def))
470 {
471 /* For a function argument try to determine the byte size
472 of the array from the current function declaratation
473 (e.g., attribute access or related). */
474 wide_int wr[2];
475 tree ref = gimple_parm_array_size (arg, wr);
476 if (!ref)
477 break;
478 arrbounds[0] = offset_int::from (wr[0], UNSIGNED);
479 arrbounds[1] = offset_int::from (wr[1], UNSIGNED);
480 arg = ref;
481 break;
482 }
483
484 if (!is_gimple_assign (def))
485 break;
486
487 tree_code code = gimple_assign_rhs_code (def);
488 if (code == POINTER_PLUS_EXPR)
489 {
490 arg = gimple_assign_rhs1 (def);
491 varoff = gimple_assign_rhs2 (def);
492 }
493 else if (code == ASSERT_EXPR)
494 {
495 arg = TREE_OPERAND (gimple_assign_rhs1 (def), 0);
496 continue;
497 }
498 else
499 return false;
500
501 /* VAROFF should always be a SSA_NAME here (and not even
502 INTEGER_CST) but there's no point in taking chances. */
503 if (TREE_CODE (varoff) != SSA_NAME)
504 break;
505
506 const value_range* const vr = get_value_range (varoff);
507 if (!vr || vr->undefined_p () || vr->varying_p ())
508 break;
509
510 if (!vr->constant_p ())
511 break;
512
513 if (vr->kind () == VR_RANGE)
514 {
515 offset_int min
516 = wi::to_offset (fold_convert (ptrdiff_type_node, vr->min ()));
517 offset_int max
518 = wi::to_offset (fold_convert (ptrdiff_type_node, vr->max ()));
519 if (min < max)
520 {
521 offrange[0] += min;
522 offrange[1] += max;
523 }
524 else
525 {
526 /* When MIN >= MAX, the offset is effectively in a union
527 of two ranges: [-MAXOBJSIZE -1, MAX] and [MIN, MAXOBJSIZE].
528 Since there is no way to represent such a range across
529 additions, conservatively add [-MAXOBJSIZE -1, MAXOBJSIZE]
530 to OFFRANGE. */
531 offrange[0] += arrbounds[0];
532 offrange[1] += arrbounds[1];
533 }
534 }
535 else
536 {
537 /* For an anti-range, analogously to the above, conservatively
538 add [-MAXOBJSIZE -1, MAXOBJSIZE] to OFFRANGE. */
539 offrange[0] += arrbounds[0];
540 offrange[1] += arrbounds[1];
541 }
542
543 /* Keep track of the minimum and maximum offset. */
544 if (offrange[1] < 0 && offrange[1] < extrema[0])
545 extrema[0] = offrange[1];
546 if (offrange[0] > 0 && offrange[0] > extrema[1])
547 extrema[1] = offrange[0];
548
549 if (offrange[0] < arrbounds[0])
550 offrange[0] = arrbounds[0];
551
552 if (offrange[1] > arrbounds[1])
553 offrange[1] = arrbounds[1];
554 }
555
556 tree reftype = NULL_TREE;
557 offset_int eltsize = -1;
558 if (arrbounds[0] >= 0)
559 {
560 /* The byte size of the array has already been determined above
561 based on a pointer ARG. Set ELTSIZE to the size of the type
562 it points to and REFTYPE to the array with the size, rounded
563 down as necessary. */
564 reftype = TREE_TYPE (TREE_TYPE (arg));
565 if (TREE_CODE (reftype) == ARRAY_TYPE)
566 reftype = TREE_TYPE (reftype);
567 if (tree refsize = TYPE_SIZE_UNIT (reftype))
568 if (TREE_CODE (refsize) == INTEGER_CST)
569 eltsize = wi::to_offset (refsize);
570
571 if (eltsize < 0)
572 return false;
573
574 offset_int nelts = arrbounds[1] / eltsize;
575 reftype = build_printable_array_type (reftype, nelts.to_uhwi ());
576 }
577 else if (TREE_CODE (arg) == ADDR_EXPR)
578 {
579 arg = TREE_OPERAND (arg, 0);
580 if (TREE_CODE (arg) != STRING_CST
581 && TREE_CODE (arg) != PARM_DECL
582 && TREE_CODE (arg) != VAR_DECL)
583 return false;
584
585 /* The type of the object being referred to. It can be an array,
586 string literal, or a non-array type when the MEM_REF represents
587 a reference/subscript via a pointer to an object that is not
588 an element of an array. Incomplete types are excluded as well
589 because their size is not known. */
590 reftype = TREE_TYPE (arg);
591 if (POINTER_TYPE_P (reftype)
592 || !COMPLETE_TYPE_P (reftype)
593 || TREE_CODE (TYPE_SIZE_UNIT (reftype)) != INTEGER_CST)
594 return false;
595
596 /* Except in declared objects, references to trailing array members
597 of structs and union objects are excluded because MEM_REF doesn't
598 make it possible to identify the member where the reference
599 originated. */
600 if (RECORD_OR_UNION_TYPE_P (reftype)
601 && (!VAR_P (arg)
602 || (DECL_EXTERNAL (arg) && array_at_struct_end_p (ref))))
603 return false;
604
605 /* FIXME: Should this be 1 for Fortran? */
606 arrbounds[0] = 0;
607
608 if (TREE_CODE (reftype) == ARRAY_TYPE)
609 {
610 /* Set to the size of the array element (and adjust below). */
611 eltsize = wi::to_offset (TYPE_SIZE_UNIT (TREE_TYPE (reftype)));
612 /* Use log2 of size to convert the array byte size in to its
613 upper bound in elements. */
614 const offset_int eltsizelog2 = wi::floor_log2 (eltsize);
615 if (tree dom = TYPE_DOMAIN (reftype))
616 {
617 tree bnds[] = { TYPE_MIN_VALUE (dom), TYPE_MAX_VALUE (dom) };
618 if (TREE_CODE (arg) == COMPONENT_REF)
619 {
620 offset_int size = maxobjsize;
621 if (tree fldsize = component_ref_size (arg))
622 size = wi::to_offset (fldsize);
623 arrbounds[1] = wi::lrshift (size, eltsizelog2);
624 }
625 else if (array_at_struct_end_p (arg) || !bnds[0] || !bnds[1])
626 arrbounds[1] = wi::lrshift (maxobjsize, eltsizelog2);
627 else
628 arrbounds[1] = (wi::to_offset (bnds[1]) - wi::to_offset (bnds[0])
629 + 1) * eltsize;
630 }
631 else
632 arrbounds[1] = wi::lrshift (maxobjsize, eltsizelog2);
633
634 /* Determine a tighter bound of the non-array element type. */
635 tree eltype = TREE_TYPE (reftype);
636 while (TREE_CODE (eltype) == ARRAY_TYPE)
637 eltype = TREE_TYPE (eltype);
638 eltsize = wi::to_offset (TYPE_SIZE_UNIT (eltype));
639 }
640 else
641 {
642 eltsize = 1;
643 tree size = TYPE_SIZE_UNIT (reftype);
644 if (VAR_P (arg))
645 if (tree initsize = DECL_SIZE_UNIT (arg))
646 if (tree_int_cst_lt (size, initsize))
647 size = initsize;
648
649 arrbounds[1] = wi::to_offset (size);
650 }
651 }
652 else
653 return false;
654
655 offrange[0] += ioff;
656 offrange[1] += ioff;
657
658 /* Compute the more permissive upper bound when IGNORE_OFF_BY_ONE
659 is set (when taking the address of the one-past-last element
660 of an array) but always use the stricter bound in diagnostics. */
661 offset_int ubound = arrbounds[1];
662 if (ignore_off_by_one)
663 ubound += eltsize;
664
665 bool warned = false;
666 /* Set if the lower bound of the subscript is out of bounds. */
667 const bool lboob = (arrbounds[0] == arrbounds[1]
668 || offrange[0] >= ubound
669 || offrange[1] < arrbounds[0]);
670 /* Set if only the upper bound of the subscript is out of bounds.
671 This can happen when using a bigger type to index into an array
672 of a smaller type, as is common with unsigned char. */
673 tree axstype = TREE_TYPE (ref);
674 offset_int axssize = 0;
675 if (TREE_CODE (axstype) != UNION_TYPE)
676 if (tree access_size = TYPE_SIZE_UNIT (axstype))
677 if (TREE_CODE (access_size) == INTEGER_CST)
678 axssize = wi::to_offset (access_size);
679
680 const bool uboob = !lboob && offrange[0] + axssize > ubound;
681 if (lboob || uboob)
682 {
683 /* Treat a reference to a non-array object as one to an array
684 of a single element. */
685 if (TREE_CODE (reftype) != ARRAY_TYPE)
686 reftype = build_printable_array_type (reftype, 1);
687
688 /* Extract the element type out of MEM_REF and use its size
689 to compute the index to print in the diagnostic; arrays
690 in MEM_REF don't mean anything. A type with no size like
691 void is as good as having a size of 1. */
692 tree type = TREE_TYPE (ref);
693 while (TREE_CODE (type) == ARRAY_TYPE)
694 type = TREE_TYPE (type);
695 if (tree size = TYPE_SIZE_UNIT (type))
696 {
697 offrange[0] = offrange[0] / wi::to_offset (size);
698 offrange[1] = offrange[1] / wi::to_offset (size);
699 }
700 }
701
702 if (lboob)
703 {
704 if (offrange[0] == offrange[1])
705 warned = warning_at (location, OPT_Warray_bounds,
706 "array subscript %wi is outside array bounds "
707 "of %qT",
708 offrange[0].to_shwi (), reftype);
709 else
710 warned = warning_at (location, OPT_Warray_bounds,
711 "array subscript [%wi, %wi] is outside "
712 "array bounds of %qT",
713 offrange[0].to_shwi (),
714 offrange[1].to_shwi (), reftype);
715 }
716 else if (uboob && !ignore_off_by_one)
717 {
718 tree backtype = reftype;
719 if (alloc_stmt)
720 /* If the memory was dynamically allocated refer to it as if
721 it were an untyped array of bytes. */
722 backtype = build_array_type_nelts (unsigned_char_type_node,
723 arrbounds[1].to_uhwi ());
724
725 warned = warning_at (location, OPT_Warray_bounds,
726 "array subscript %<%T[%wi]%> is partly "
727 "outside array bounds of %qT",
728 axstype, offrange[0].to_shwi (), backtype);
729 }
730
731 if (warned)
732 {
733 if (DECL_P (arg))
734 inform (DECL_SOURCE_LOCATION (arg), "while referencing %qD", arg);
735 else if (alloc_stmt)
736 {
737 location_t loc = gimple_location (alloc_stmt);
738 if (gimple_call_builtin_p (alloc_stmt, BUILT_IN_ALLOCA_WITH_ALIGN))
739 {
740 if (minbound == arrbounds[1])
741 inform (loc, "referencing a variable length array "
742 "of size %wu", minbound.to_uhwi ());
743 else
744 inform (loc, "referencing a variable length array "
745 "of size between %wu and %wu",
746 minbound.to_uhwi (), arrbounds[1].to_uhwi ());
747 }
748 else if (tree fndecl = gimple_call_fndecl (alloc_stmt))
749 {
750 if (minbound == arrbounds[1])
751 inform (loc, "referencing an object of size %wu "
752 "allocated by %qD",
753 minbound.to_uhwi (), fndecl);
754 else
755 inform (loc, "referencing an object of size between "
756 "%wu and %wu allocated by %qD",
757 minbound.to_uhwi (), arrbounds[1].to_uhwi (), fndecl);
758 }
759 else
760 {
761 tree fntype = gimple_call_fntype (alloc_stmt);
762 if (minbound == arrbounds[1])
763 inform (loc, "referencing an object of size %wu "
764 "allocated by %qT",
765 minbound.to_uhwi (), fntype);
766 else
767 inform (loc, "referencing an object of size between "
768 "%wu and %wu allocated by %qT",
769 minbound.to_uhwi (), arrbounds[1].to_uhwi (), fntype);
770 }
771 }
772
773 TREE_NO_WARNING (ref) = 1;
774 return true;
775 }
776
777 if (warn_array_bounds < 2)
778 return false;
779
780 /* At level 2 check also intermediate offsets. */
781 int i = 0;
782 if (extrema[i] < -arrbounds[1] || extrema[i = 1] > ubound)
783 {
784 HOST_WIDE_INT tmpidx = extrema[i].to_shwi () / eltsize.to_shwi ();
785
786 if (warning_at (location, OPT_Warray_bounds,
787 "intermediate array offset %wi is outside array bounds "
788 "of %qT", tmpidx, reftype))
789 {
790 TREE_NO_WARNING (ref) = 1;
791 return true;
792 }
793 }
794
795 return false;
796 }
797
798 /* Searches if the expr T, located at LOCATION computes
799 address of an ARRAY_REF, and call check_array_ref on it. */
800
801 void
check_addr_expr(location_t location,tree t)802 array_bounds_checker::check_addr_expr (location_t location, tree t)
803 {
804 /* For the most significant subscript only, accept taking the address
805 of the just-past-the-end element. */
806 bool ignore_off_by_one = true;
807
808 /* Check each ARRAY_REF and MEM_REF in the reference chain. */
809 do
810 {
811 bool warned = false;
812 if (TREE_CODE (t) == ARRAY_REF)
813 {
814 warned = check_array_ref (location, t, ignore_off_by_one);
815 ignore_off_by_one = false;
816 }
817 else if (TREE_CODE (t) == MEM_REF)
818 warned = check_mem_ref (location, t, ignore_off_by_one);
819
820 if (warned)
821 TREE_NO_WARNING (t) = true;
822
823 t = TREE_OPERAND (t, 0);
824 }
825 while (handled_component_p (t) || TREE_CODE (t) == MEM_REF);
826
827 if (TREE_CODE (t) != MEM_REF
828 || TREE_CODE (TREE_OPERAND (t, 0)) != ADDR_EXPR
829 || TREE_NO_WARNING (t))
830 return;
831
832 tree tem = TREE_OPERAND (TREE_OPERAND (t, 0), 0);
833 tree low_bound, up_bound, el_sz;
834 if (TREE_CODE (TREE_TYPE (tem)) != ARRAY_TYPE
835 || TREE_CODE (TREE_TYPE (TREE_TYPE (tem))) == ARRAY_TYPE
836 || !TYPE_DOMAIN (TREE_TYPE (tem)))
837 return;
838
839 low_bound = TYPE_MIN_VALUE (TYPE_DOMAIN (TREE_TYPE (tem)));
840 up_bound = TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (tem)));
841 el_sz = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (tem)));
842 if (!low_bound
843 || TREE_CODE (low_bound) != INTEGER_CST
844 || !up_bound
845 || TREE_CODE (up_bound) != INTEGER_CST
846 || !el_sz
847 || TREE_CODE (el_sz) != INTEGER_CST)
848 return;
849
850 offset_int idx;
851 if (!mem_ref_offset (t).is_constant (&idx))
852 return;
853
854 bool warned = false;
855 idx = wi::sdiv_trunc (idx, wi::to_offset (el_sz));
856 if (idx < 0)
857 {
858 if (dump_file && (dump_flags & TDF_DETAILS))
859 {
860 fprintf (dump_file, "Array bound warning for ");
861 dump_generic_expr (MSG_NOTE, TDF_SLIM, t);
862 fprintf (dump_file, "\n");
863 }
864 warned = warning_at (location, OPT_Warray_bounds,
865 "array subscript %wi is below "
866 "array bounds of %qT",
867 idx.to_shwi (), TREE_TYPE (tem));
868 }
869 else if (idx > (wi::to_offset (up_bound)
870 - wi::to_offset (low_bound) + 1))
871 {
872 if (dump_file && (dump_flags & TDF_DETAILS))
873 {
874 fprintf (dump_file, "Array bound warning for ");
875 dump_generic_expr (MSG_NOTE, TDF_SLIM, t);
876 fprintf (dump_file, "\n");
877 }
878 warned = warning_at (location, OPT_Warray_bounds,
879 "array subscript %wu is above "
880 "array bounds of %qT",
881 idx.to_uhwi (), TREE_TYPE (tem));
882 }
883
884 if (warned)
885 {
886 if (DECL_P (t))
887 inform (DECL_SOURCE_LOCATION (t), "while referencing %qD", t);
888
889 TREE_NO_WARNING (t) = 1;
890 }
891 }
892
893 /* Return true if T is a reference to a member of a base class that's within
894 the bounds of the enclosing complete object. The function "hacks" around
895 problems discussed in pr98266 and pr97595. */
896
897 static bool
inbounds_memaccess_p(tree t)898 inbounds_memaccess_p (tree t)
899 {
900 if (TREE_CODE (t) != COMPONENT_REF)
901 return false;
902
903 tree mref = TREE_OPERAND (t, 0);
904 if (TREE_CODE (mref) != MEM_REF)
905 return false;
906
907 /* Consider the access if its type is a derived class. */
908 tree mreftype = TREE_TYPE (mref);
909 if (!RECORD_OR_UNION_TYPE_P (mreftype)
910 || !TYPE_BINFO (mreftype))
911 return false;
912
913 /* Compute the size of the referenced object (it could be dynamically
914 allocated). */
915 access_ref aref; // unused
916 tree refop = TREE_OPERAND (mref, 0);
917 tree refsize = compute_objsize (refop, 1, &aref);
918 if (!refsize || TREE_CODE (refsize) != INTEGER_CST)
919 return false;
920
921 /* Compute the byte offset of the member within its enclosing class. */
922 tree fld = TREE_OPERAND (t, 1);
923 tree fldpos = byte_position (fld);
924 if (TREE_CODE (fldpos) != INTEGER_CST)
925 return false;
926
927 /* Compute the byte offset of the member with the outermost complete
928 object by adding its offset computed above to the MEM_REF offset. */
929 tree refoff = TREE_OPERAND (mref, 1);
930 tree fldoff = int_const_binop (PLUS_EXPR, fldpos, refoff);
931 /* Return false if the member offset is greater or equal to the size
932 of the complete object. */
933 if (!tree_int_cst_lt (fldoff, refsize))
934 return false;
935
936 tree fldsiz = DECL_SIZE_UNIT (fld);
937 if (!fldsiz || TREE_CODE (fldsiz) != INTEGER_CST)
938 return false;
939
940 /* Return true if the offset just past the end of the member is less
941 than or equal to the size of the complete object. */
942 tree fldend = int_const_binop (PLUS_EXPR, fldoff, fldsiz);
943 return tree_int_cst_le (fldend, refsize);
944 }
945
946 /* Callback for walk_tree to check a tree for out of bounds array
947 accesses. The array_bounds_checker class is passed in DATA. */
948
949 tree
check_array_bounds(tree * tp,int * walk_subtree,void * data)950 array_bounds_checker::check_array_bounds (tree *tp, int *walk_subtree,
951 void *data)
952 {
953 tree t = *tp;
954 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
955 location_t location;
956
957 if (EXPR_HAS_LOCATION (t))
958 location = EXPR_LOCATION (t);
959 else
960 location = gimple_location (wi->stmt);
961
962 *walk_subtree = TRUE;
963
964 bool warned = false;
965 array_bounds_checker *checker = (array_bounds_checker *) wi->info;
966 if (TREE_CODE (t) == ARRAY_REF)
967 warned = checker->check_array_ref (location, t,
968 false/*ignore_off_by_one*/);
969 else if (TREE_CODE (t) == MEM_REF)
970 warned = checker->check_mem_ref (location, t,
971 false /*ignore_off_by_one*/);
972 else if (TREE_CODE (t) == ADDR_EXPR)
973 {
974 checker->check_addr_expr (location, t);
975 *walk_subtree = false;
976 }
977 else if (inbounds_memaccess_p (t))
978 /* Hack: Skip MEM_REF checks in accesses to a member of a base class
979 at an offset that's within the bounds of the enclosing object.
980 See pr98266 and pr97595. */
981 *walk_subtree = false;
982
983 /* Propagate the no-warning bit to the outer expression. */
984 if (warned)
985 TREE_NO_WARNING (t) = true;
986
987 return NULL_TREE;
988 }
989
990 /* A dom_walker subclass for use by check_all_array_refs, to walk over
991 all statements of all reachable BBs and call check_array_bounds on
992 them. */
993
994 class check_array_bounds_dom_walker : public dom_walker
995 {
996 public:
check_array_bounds_dom_walker(array_bounds_checker * checker)997 check_array_bounds_dom_walker (array_bounds_checker *checker)
998 : dom_walker (CDI_DOMINATORS,
999 /* Discover non-executable edges, preserving EDGE_EXECUTABLE
1000 flags, so that we can merge in information on
1001 non-executable edges from vrp_folder . */
1002 REACHABLE_BLOCKS_PRESERVING_FLAGS),
1003 checker (checker) { }
~check_array_bounds_dom_walker()1004 ~check_array_bounds_dom_walker () {}
1005
1006 edge before_dom_children (basic_block) FINAL OVERRIDE;
1007
1008 private:
1009 array_bounds_checker *checker;
1010 };
1011
1012 /* Implementation of dom_walker::before_dom_children.
1013
1014 Walk over all statements of BB and call check_array_bounds on them,
1015 and determine if there's a unique successor edge. */
1016
1017 edge
before_dom_children(basic_block bb)1018 check_array_bounds_dom_walker::before_dom_children (basic_block bb)
1019 {
1020 gimple_stmt_iterator si;
1021 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1022 {
1023 gimple *stmt = gsi_stmt (si);
1024 struct walk_stmt_info wi;
1025 if (!gimple_has_location (stmt)
1026 || is_gimple_debug (stmt))
1027 continue;
1028
1029 memset (&wi, 0, sizeof (wi));
1030
1031 wi.info = checker;
1032
1033 walk_gimple_op (stmt, array_bounds_checker::check_array_bounds, &wi);
1034 }
1035
1036 /* Determine if there's a unique successor edge, and if so, return
1037 that back to dom_walker, ensuring that we don't visit blocks that
1038 became unreachable during the VRP propagation
1039 (PR tree-optimization/83312). */
1040 return find_taken_edge (bb, NULL_TREE);
1041 }
1042
1043 void
check()1044 array_bounds_checker::check ()
1045 {
1046 check_array_bounds_dom_walker w (this);
1047 w.walk (ENTRY_BLOCK_PTR_FOR_FN (fun));
1048 }
1049