]> git.ipfire.org Git - thirdparty/gcc.git/blame - gcc/tree-object-size.c
projects / thirdparty / gcc.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
2007-06-15 Eric Christopher <echristo@apple.com>
[thirdparty/gcc.git] / gcc / tree-object-size.c
CommitLineData
0a39fd54 1/* __builtin_object_size (ptr, object_size_type) computation
535664e3 2 Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
0a39fd54 3 Contributed by Jakub Jelinek <jakub@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 2, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING. If not, write to
c2b61805 19the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20Boston, MA 02110-1301, USA. */
0a39fd54 21
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "tm.h"
26#include "tree.h"
4a29c97c 27#include "toplev.h"
0a39fd54 28#include "diagnostic.h"
29#include "tree-flow.h"
30#include "tree-pass.h"
31#include "tree-ssa-propagate.h"
32
33struct object_size_info
34{
35 int object_size_type;
36 bitmap visited, reexamine;
37 int pass;
38 bool changed;
39 unsigned int *depths;
40 unsigned int *stack, *tos;
41};
42
43static unsigned HOST_WIDE_INT unknown[4] = { -1, -1, 0, 0 };
44
45static tree compute_object_offset (tree, tree);
46static unsigned HOST_WIDE_INT addr_object_size (tree, int);
47static unsigned HOST_WIDE_INT alloc_object_size (tree, int);
48static tree pass_through_call (tree);
49static void collect_object_sizes_for (struct object_size_info *, tree);
50static void expr_object_size (struct object_size_info *, tree, tree);
51static bool merge_object_sizes (struct object_size_info *, tree, tree,
52 unsigned HOST_WIDE_INT);
53static bool plus_expr_object_size (struct object_size_info *, tree, tree);
ec0fa513 54static bool cond_expr_object_size (struct object_size_info *, tree, tree);
2a1990e9 55static unsigned int compute_object_sizes (void);
0a39fd54 56static void init_offset_limit (void);
57static void check_for_plus_in_loops (struct object_size_info *, tree);
58static void check_for_plus_in_loops_1 (struct object_size_info *, tree,
59 unsigned int);
60
61/* object_sizes[0] is upper bound for number of bytes till the end of
62 the object.
63 object_sizes[1] is upper bound for number of bytes till the end of
64 the subobject (innermost array or field with address taken).
65 object_sizes[2] is lower bound for number of bytes till the end of
66 the object and object_sizes[3] lower bound for subobject. */
67static unsigned HOST_WIDE_INT *object_sizes[4];
68
69/* Bitmaps what object sizes have been computed already. */
70static bitmap computed[4];
71
72/* Maximum value of offset we consider to be addition. */
73static unsigned HOST_WIDE_INT offset_limit;
74
75
76/* Initialize OFFSET_LIMIT variable. */
77static void
78init_offset_limit (void)
79{
80 if (host_integerp (TYPE_MAX_VALUE (sizetype), 1))
81 offset_limit = tree_low_cst (TYPE_MAX_VALUE (sizetype), 1);
82 else
83 offset_limit = -1;
84 offset_limit /= 2;
85}
86
87
88/* Compute offset of EXPR within VAR. Return error_mark_node
89 if unknown. */
90
91static tree
92compute_object_offset (tree expr, tree var)
93{
94 enum tree_code code = PLUS_EXPR;
95 tree base, off, t;
96
97 if (expr == var)
98 return size_zero_node;
99
100 switch (TREE_CODE (expr))
101 {
102 case COMPONENT_REF:
103 base = compute_object_offset (TREE_OPERAND (expr, 0), var);
104 if (base == error_mark_node)
105 return base;
106
107 t = TREE_OPERAND (expr, 1);
108 off = size_binop (PLUS_EXPR, DECL_FIELD_OFFSET (t),
109 size_int (tree_low_cst (DECL_FIELD_BIT_OFFSET (t), 1)
110 / BITS_PER_UNIT));
111 break;
112
113 case REALPART_EXPR:
114 case NOP_EXPR:
115 case CONVERT_EXPR:
116 case VIEW_CONVERT_EXPR:
117 case NON_LVALUE_EXPR:
118 return compute_object_offset (TREE_OPERAND (expr, 0), var);
119
120 case IMAGPART_EXPR:
121 base = compute_object_offset (TREE_OPERAND (expr, 0), var);
122 if (base == error_mark_node)
123 return base;
124
125 off = TYPE_SIZE_UNIT (TREE_TYPE (expr));
126 break;
127
128 case ARRAY_REF:
129 base = compute_object_offset (TREE_OPERAND (expr, 0), var);
130 if (base == error_mark_node)
131 return base;
132
133 t = TREE_OPERAND (expr, 1);
134 if (TREE_CODE (t) == INTEGER_CST && tree_int_cst_sgn (t) < 0)
135 {
136 code = MINUS_EXPR;
137 t = fold_build1 (NEGATE_EXPR, TREE_TYPE (t), t);
138 }
535664e3 139 t = fold_convert (sizetype, t);
0a39fd54 140 off = size_binop (MULT_EXPR, TYPE_SIZE_UNIT (TREE_TYPE (expr)), t);
141 break;
142
143 default:
144 return error_mark_node;
145 }
146
147 return size_binop (code, base, off);
148}
149
150
151/* Compute __builtin_object_size for PTR, which is a ADDR_EXPR.
152 OBJECT_SIZE_TYPE is the second argument from __builtin_object_size.
153 If unknown, return unknown[object_size_type]. */
154
155static unsigned HOST_WIDE_INT
156addr_object_size (tree ptr, int object_size_type)
157{
158 tree pt_var;
159
160 gcc_assert (TREE_CODE (ptr) == ADDR_EXPR);
161
162 pt_var = TREE_OPERAND (ptr, 0);
163 if (REFERENCE_CLASS_P (pt_var))
164 pt_var = get_base_address (pt_var);
165
166 if (pt_var
167 && (SSA_VAR_P (pt_var) || TREE_CODE (pt_var) == STRING_CST)
168 && TYPE_SIZE_UNIT (TREE_TYPE (pt_var))
169 && host_integerp (TYPE_SIZE_UNIT (TREE_TYPE (pt_var)), 1)
170 && (unsigned HOST_WIDE_INT)
171 tree_low_cst (TYPE_SIZE_UNIT (TREE_TYPE (pt_var)), 1) < offset_limit)
172 {
173 tree bytes;
174
175 if (pt_var != TREE_OPERAND (ptr, 0))
176 {
177 tree var;
178
179 if (object_size_type & 1)
180 {
181 var = TREE_OPERAND (ptr, 0);
182
183 while (var != pt_var
184 && TREE_CODE (var) != BIT_FIELD_REF
185 && TREE_CODE (var) != COMPONENT_REF
186 && TREE_CODE (var) != ARRAY_REF
187 && TREE_CODE (var) != ARRAY_RANGE_REF
188 && TREE_CODE (var) != REALPART_EXPR
189 && TREE_CODE (var) != IMAGPART_EXPR)
190 var = TREE_OPERAND (var, 0);
191 if (var != pt_var && TREE_CODE (var) == ARRAY_REF)
192 var = TREE_OPERAND (var, 0);
193 if (! TYPE_SIZE_UNIT (TREE_TYPE (var))
194 || ! host_integerp (TYPE_SIZE_UNIT (TREE_TYPE (var)), 1)
195 || tree_int_cst_lt (TYPE_SIZE_UNIT (TREE_TYPE (pt_var)),
196 TYPE_SIZE_UNIT (TREE_TYPE (var))))
197 var = pt_var;
198 }
199 else
200 var = pt_var;
201
202 bytes = compute_object_offset (TREE_OPERAND (ptr, 0), var);
203 if (bytes != error_mark_node)
204 {
205 if (TREE_CODE (bytes) == INTEGER_CST
206 && tree_int_cst_lt (TYPE_SIZE_UNIT (TREE_TYPE (var)), bytes))
207 bytes = size_zero_node;
208 else
209 bytes = size_binop (MINUS_EXPR,
210 TYPE_SIZE_UNIT (TREE_TYPE (var)), bytes);
211 }
212 }
213 else
214 bytes = TYPE_SIZE_UNIT (TREE_TYPE (pt_var));
215
216 if (host_integerp (bytes, 1))
217 return tree_low_cst (bytes, 1);
218 }
219
220 return unknown[object_size_type];
221}
222
223
224/* Compute __builtin_object_size for CALL, which is a CALL_EXPR.
225 Handles various allocation calls. OBJECT_SIZE_TYPE is the second
226 argument from __builtin_object_size. If unknown, return
227 unknown[object_size_type]. */
228
229static unsigned HOST_WIDE_INT
230alloc_object_size (tree call, int object_size_type)
231{
c2f47e15 232 tree callee, bytes = NULL_TREE;
4a29c97c 233 tree alloc_size;
234 int arg1 = -1, arg2 = -1;
0a39fd54 235
236 gcc_assert (TREE_CODE (call) == CALL_EXPR);
237
238 callee = get_callee_fndecl (call);
4a29c97c 239 if (!callee)
240 return unknown[object_size_type];
241
242 alloc_size = lookup_attribute ("alloc_size", TYPE_ATTRIBUTES (TREE_TYPE(callee)));
243 if (alloc_size && TREE_VALUE (alloc_size))
244 {
245 tree p = TREE_VALUE (alloc_size);
246
247 arg1 = TREE_INT_CST_LOW (TREE_VALUE (p))-1;
248 if (TREE_CHAIN (p))
249 arg2 = TREE_INT_CST_LOW (TREE_VALUE (TREE_CHAIN (p)))-1;
250 }
251
252 if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
0a39fd54 253 switch (DECL_FUNCTION_CODE (callee))
254 {
4a29c97c 255 case BUILT_IN_CALLOC:
256 arg2 = 1;
257 /* fall through */
0a39fd54 258 case BUILT_IN_MALLOC:
259 case BUILT_IN_ALLOCA:
4a29c97c 260 arg1 = 0;
0a39fd54 261 default:
262 break;
263 }
264
4a29c97c 265 if (arg1 < 0 || arg1 >= call_expr_nargs (call)
266 || TREE_CODE (CALL_EXPR_ARG (call, arg1)) != INTEGER_CST
267 || (arg2 >= 0
268 && (arg2 >= call_expr_nargs (call)
269 || TREE_CODE (CALL_EXPR_ARG (call, arg2)) != INTEGER_CST)))
270 return unknown[object_size_type];
271
272 if (arg2 >= 0)
273 bytes = size_binop (MULT_EXPR,
274 fold_convert (sizetype, CALL_EXPR_ARG (call, arg1)),
275 fold_convert (sizetype, CALL_EXPR_ARG (call, arg2)));
276 else if (arg1 >= 0)
277 bytes = fold_convert (sizetype, CALL_EXPR_ARG (call, arg1));
278
c2f47e15 279 if (bytes && host_integerp (bytes, 1))
0a39fd54 280 return tree_low_cst (bytes, 1);
281
282 return unknown[object_size_type];
283}
284
285
286/* If object size is propagated from one of function's arguments directly
287 to its return value, return that argument for CALL_EXPR CALL.
288 Otherwise return NULL. */
289
290static tree
291pass_through_call (tree call)
292{
293 tree callee = get_callee_fndecl (call);
0a39fd54 294
295 if (callee
296 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
297 switch (DECL_FUNCTION_CODE (callee))
298 {
299 case BUILT_IN_MEMCPY:
300 case BUILT_IN_MEMMOVE:
301 case BUILT_IN_MEMSET:
302 case BUILT_IN_STRCPY:
303 case BUILT_IN_STRNCPY:
304 case BUILT_IN_STRCAT:
305 case BUILT_IN_STRNCAT:
306 case BUILT_IN_MEMCPY_CHK:
307 case BUILT_IN_MEMMOVE_CHK:
308 case BUILT_IN_MEMSET_CHK:
309 case BUILT_IN_STRCPY_CHK:
310 case BUILT_IN_STRNCPY_CHK:
311 case BUILT_IN_STRCAT_CHK:
312 case BUILT_IN_STRNCAT_CHK:
c2f47e15 313 if (call_expr_nargs (call) >= 1)
314 return CALL_EXPR_ARG (call, 0);
0a39fd54 315 break;
316 default:
317 break;
318 }
319
320 return NULL_TREE;
321}
322
323
324/* Compute __builtin_object_size value for PTR. OBJECT_SIZE_TYPE is the
325 second argument from __builtin_object_size. */
326
327unsigned HOST_WIDE_INT
328compute_builtin_object_size (tree ptr, int object_size_type)
329{
330 gcc_assert (object_size_type >= 0 && object_size_type <= 3);
331
332 if (! offset_limit)
333 init_offset_limit ();
334
335 if (TREE_CODE (ptr) == ADDR_EXPR)
336 return addr_object_size (ptr, object_size_type);
337 else if (TREE_CODE (ptr) == CALL_EXPR)
338 {
339 tree arg = pass_through_call (ptr);
340
341 if (arg)
342 return compute_builtin_object_size (arg, object_size_type);
343 else
344 return alloc_object_size (ptr, object_size_type);
345 }
346 else if (TREE_CODE (ptr) == SSA_NAME
347 && POINTER_TYPE_P (TREE_TYPE (ptr))
348 && object_sizes[object_size_type] != NULL)
349 {
350 if (!bitmap_bit_p (computed[object_size_type], SSA_NAME_VERSION (ptr)))
351 {
352 struct object_size_info osi;
353 bitmap_iterator bi;
354 unsigned int i;
355
356 if (dump_file)
357 {
358 fprintf (dump_file, "Computing %s %sobject size for ",
359 (object_size_type & 2) ? "minimum" : "maximum",
360 (object_size_type & 1) ? "sub" : "");
361 print_generic_expr (dump_file, ptr, dump_flags);
362 fprintf (dump_file, ":\n");
363 }
364
365 osi.visited = BITMAP_ALLOC (NULL);
366 osi.reexamine = BITMAP_ALLOC (NULL);
367 osi.object_size_type = object_size_type;
368 osi.depths = NULL;
369 osi.stack = NULL;
370 osi.tos = NULL;
371
372 /* First pass: walk UD chains, compute object sizes that
373 can be computed. osi.reexamine bitmap at the end will
374 contain what variables were found in dependency cycles
375 and therefore need to be reexamined. */
376 osi.pass = 0;
377 osi.changed = false;
378 collect_object_sizes_for (&osi, ptr);
379
380 /* Second pass: keep recomputing object sizes of variables
381 that need reexamination, until no object sizes are
382 increased or all object sizes are computed. */
383 if (! bitmap_empty_p (osi.reexamine))
384 {
385 bitmap reexamine = BITMAP_ALLOC (NULL);
386
387 /* If looking for minimum instead of maximum object size,
388 detect cases where a pointer is increased in a loop.
389 Although even without this detection pass 2 would eventually
390 terminate, it could take a long time. If a pointer is
391 increasing this way, we need to assume 0 object size.
392 E.g. p = &buf[0]; while (cond) p = p + 4; */
393 if (object_size_type & 2)
394 {
4c36ffe6 395 osi.depths = XCNEWVEC (unsigned int, num_ssa_names);
396 osi.stack = XNEWVEC (unsigned int, num_ssa_names);
0a39fd54 397 osi.tos = osi.stack;
398 osi.pass = 1;
399 /* collect_object_sizes_for is changing
400 osi.reexamine bitmap, so iterate over a copy. */
401 bitmap_copy (reexamine, osi.reexamine);
402 EXECUTE_IF_SET_IN_BITMAP (reexamine, 0, i, bi)
403 if (bitmap_bit_p (osi.reexamine, i))
404 check_for_plus_in_loops (&osi, ssa_name (i));
405
406 free (osi.depths);
407 osi.depths = NULL;
408 free (osi.stack);
409 osi.stack = NULL;
410 osi.tos = NULL;
411 }
412
413 do
414 {
415 osi.pass = 2;
416 osi.changed = false;
417 /* collect_object_sizes_for is changing
418 osi.reexamine bitmap, so iterate over a copy. */
419 bitmap_copy (reexamine, osi.reexamine);
420 EXECUTE_IF_SET_IN_BITMAP (reexamine, 0, i, bi)
421 if (bitmap_bit_p (osi.reexamine, i))
422 {
423 collect_object_sizes_for (&osi, ssa_name (i));
424 if (dump_file && (dump_flags & TDF_DETAILS))
425 {
426 fprintf (dump_file, "Reexamining ");
427 print_generic_expr (dump_file, ssa_name (i),
428 dump_flags);
429 fprintf (dump_file, "\n");
430 }
431 }
432 }
433 while (osi.changed);
434
435 BITMAP_FREE (reexamine);
436 }
437 EXECUTE_IF_SET_IN_BITMAP (osi.reexamine, 0, i, bi)
438 bitmap_set_bit (computed[object_size_type], i);
439
440 /* Debugging dumps. */
441 if (dump_file)
442 {
443 EXECUTE_IF_SET_IN_BITMAP (osi.visited, 0, i, bi)
444 if (object_sizes[object_size_type][i]
445 != unknown[object_size_type])
446 {
447 print_generic_expr (dump_file, ssa_name (i),
448 dump_flags);
449 fprintf (dump_file,
450 ": %s %sobject size "
451 HOST_WIDE_INT_PRINT_UNSIGNED "\n",
452 (object_size_type & 2) ? "minimum" : "maximum",
453 (object_size_type & 1) ? "sub" : "",
454 object_sizes[object_size_type][i]);
455 }
456 }
457
458 BITMAP_FREE (osi.reexamine);
459 BITMAP_FREE (osi.visited);
460 }
461
462 return object_sizes[object_size_type][SSA_NAME_VERSION (ptr)];
463 }
464
465 return unknown[object_size_type];
466}
467
468
469/* Compute object_sizes for PTR, defined to VALUE, which is not
470 a SSA_NAME. */
471
472static void
473expr_object_size (struct object_size_info *osi, tree ptr, tree value)
474{
475 int object_size_type = osi->object_size_type;
476 unsigned int varno = SSA_NAME_VERSION (ptr);
477 unsigned HOST_WIDE_INT bytes;
478
479 gcc_assert (object_sizes[object_size_type][varno]
480 != unknown[object_size_type]);
481 gcc_assert (osi->pass == 0);
482
483 if (TREE_CODE (value) == WITH_SIZE_EXPR)
484 value = TREE_OPERAND (value, 0);
485
486 /* Pointer variables should have been handled by merge_object_sizes. */
487 gcc_assert (TREE_CODE (value) != SSA_NAME
488 || !POINTER_TYPE_P (TREE_TYPE (value)));
489
490 if (TREE_CODE (value) == ADDR_EXPR)
491 bytes = addr_object_size (value, object_size_type);
492 else if (TREE_CODE (value) == CALL_EXPR)
493 bytes = alloc_object_size (value, object_size_type);
494 else
495 bytes = unknown[object_size_type];
496
497 if ((object_size_type & 2) == 0)
498 {
499 if (object_sizes[object_size_type][varno] < bytes)
500 object_sizes[object_size_type][varno] = bytes;
501 }
502 else
503 {
504 if (object_sizes[object_size_type][varno] > bytes)
505 object_sizes[object_size_type][varno] = bytes;
506 }
507}
508
509
510/* Merge object sizes of ORIG + OFFSET into DEST. Return true if
511 the object size might need reexamination later. */
512
513static bool
514merge_object_sizes (struct object_size_info *osi, tree dest, tree orig,
515 unsigned HOST_WIDE_INT offset)
516{
517 int object_size_type = osi->object_size_type;
518 unsigned int varno = SSA_NAME_VERSION (dest);
519 unsigned HOST_WIDE_INT orig_bytes;
520
521 if (object_sizes[object_size_type][varno] == unknown[object_size_type])
522 return false;
523 if (offset >= offset_limit)
524 {
525 object_sizes[object_size_type][varno] = unknown[object_size_type];
526 return false;
527 }
528
529 if (osi->pass == 0)
530 collect_object_sizes_for (osi, orig);
531
532 orig_bytes = object_sizes[object_size_type][SSA_NAME_VERSION (orig)];
533 if (orig_bytes != unknown[object_size_type])
534 orig_bytes = (offset > orig_bytes)
535 ? (unsigned HOST_WIDE_INT) 0 : orig_bytes - offset;
536
537 if ((object_size_type & 2) == 0)
538 {
539 if (object_sizes[object_size_type][varno] < orig_bytes)
540 {
541 object_sizes[object_size_type][varno] = orig_bytes;
542 osi->changed = true;
543 }
544 }
545 else
546 {
547 if (object_sizes[object_size_type][varno] > orig_bytes)
548 {
549 object_sizes[object_size_type][varno] = orig_bytes;
550 osi->changed = true;
551 }
552 }
553 return bitmap_bit_p (osi->reexamine, SSA_NAME_VERSION (orig));
554}
555
556
557/* Compute object_sizes for PTR, defined to VALUE, which is
558 a PLUS_EXPR. Return true if the object size might need reexamination
559 later. */
560
561static bool
562plus_expr_object_size (struct object_size_info *osi, tree var, tree value)
563{
564 tree op0 = TREE_OPERAND (value, 0);
565 tree op1 = TREE_OPERAND (value, 1);
566 bool ptr1_p = POINTER_TYPE_P (TREE_TYPE (op0))
567 && TREE_CODE (op0) != INTEGER_CST;
568 bool ptr2_p = POINTER_TYPE_P (TREE_TYPE (op1))
569 && TREE_CODE (op1) != INTEGER_CST;
570 int object_size_type = osi->object_size_type;
571 unsigned int varno = SSA_NAME_VERSION (var);
572 unsigned HOST_WIDE_INT bytes;
573
574 gcc_assert (TREE_CODE (value) == PLUS_EXPR);
575
576 if (object_sizes[object_size_type][varno] == unknown[object_size_type])
577 return false;
578
579 /* Swap operands if needed. */
580 if (ptr2_p && !ptr1_p)
581 {
582 tree tem = op0;
583 op0 = op1;
584 op1 = tem;
585 ptr1_p = true;
586 ptr2_p = false;
587 }
588
589 /* Handle PTR + OFFSET here. */
590 if (ptr1_p
591 && !ptr2_p
592 && TREE_CODE (op1) == INTEGER_CST
593 && (TREE_CODE (op0) == SSA_NAME
594 || TREE_CODE (op0) == ADDR_EXPR))
595 {
596 if (! host_integerp (op1, 1))
597 bytes = unknown[object_size_type];
598 else if (TREE_CODE (op0) == SSA_NAME)
599 return merge_object_sizes (osi, var, op0, tree_low_cst (op1, 1));
600 else
601 {
602 unsigned HOST_WIDE_INT off = tree_low_cst (op1, 1);
603
19256cce 604 bytes = compute_builtin_object_size (op0, object_size_type);
06f9fe3e 605 if (bytes == unknown[object_size_type])
606 ;
607 else if (off > offset_limit)
0a39fd54 608 bytes = unknown[object_size_type];
609 else if (off > bytes)
610 bytes = 0;
611 else
612 bytes -= off;
613 }
614 }
615 else
616 bytes = unknown[object_size_type];
617
618 if ((object_size_type & 2) == 0)
619 {
620 if (object_sizes[object_size_type][varno] < bytes)
621 object_sizes[object_size_type][varno] = bytes;
622 }
623 else
624 {
625 if (object_sizes[object_size_type][varno] > bytes)
626 object_sizes[object_size_type][varno] = bytes;
627 }
628 return false;
629}
630
631
ec0fa513 632/* Compute object_sizes for PTR, defined to VALUE, which is
633 a COND_EXPR. Return true if the object size might need reexamination
634 later. */
635
636static bool
637cond_expr_object_size (struct object_size_info *osi, tree var, tree value)
638{
639 tree then_, else_;
640 int object_size_type = osi->object_size_type;
641 unsigned int varno = SSA_NAME_VERSION (var);
642 bool reexamine = false;
643
644 gcc_assert (TREE_CODE (value) == COND_EXPR);
645
646 if (object_sizes[object_size_type][varno] == unknown[object_size_type])
647 return false;
648
649 then_ = COND_EXPR_THEN (value);
650 else_ = COND_EXPR_ELSE (value);
651
652 if (TREE_CODE (then_) == SSA_NAME)
653 reexamine |= merge_object_sizes (osi, var, then_, 0);
654 else
655 expr_object_size (osi, var, then_);
656
657 if (TREE_CODE (else_) == SSA_NAME)
658 reexamine |= merge_object_sizes (osi, var, else_, 0);
659 else
660 expr_object_size (osi, var, else_);
661
662 return reexamine;
663}
664
665
0a39fd54 666/* Compute object sizes for VAR.
667 For ADDR_EXPR an object size is the number of remaining bytes
56d36a49 668 to the end of the object (where what is considered an object depends on
0a39fd54 669 OSI->object_size_type).
670 For allocation CALL_EXPR like malloc or calloc object size is the size
671 of the allocation.
672 For pointer PLUS_EXPR where second operand is a constant integer,
673 object size is object size of the first operand minus the constant.
674 If the constant is bigger than the number of remaining bytes until the
675 end of the object, object size is 0, but if it is instead a pointer
676 subtraction, object size is unknown[object_size_type].
677 To differentiate addition from subtraction, ADDR_EXPR returns
678 unknown[object_size_type] for all objects bigger than half of the address
679 space, and constants less than half of the address space are considered
680 addition, while bigger constants subtraction.
681 For a memcpy like CALL_EXPR that always returns one of its arguments, the
682 object size is object size of that argument.
683 Otherwise, object size is the maximum of object sizes of variables
684 that it might be set to. */
685
686static void
687collect_object_sizes_for (struct object_size_info *osi, tree var)
688{
689 int object_size_type = osi->object_size_type;
690 unsigned int varno = SSA_NAME_VERSION (var);
691 tree stmt;
692 bool reexamine;
693
694 if (bitmap_bit_p (computed[object_size_type], varno))
695 return;
696
697 if (osi->pass == 0)
698 {
699 if (! bitmap_bit_p (osi->visited, varno))
700 {
701 bitmap_set_bit (osi->visited, varno);
702 object_sizes[object_size_type][varno]
703 = (object_size_type & 2) ? -1 : 0;
704 }
705 else
706 {
707 /* Found a dependency loop. Mark the variable for later
708 re-examination. */
709 bitmap_set_bit (osi->reexamine, varno);
710 if (dump_file && (dump_flags & TDF_DETAILS))
711 {
712 fprintf (dump_file, "Found a dependency loop at ");
713 print_generic_expr (dump_file, var, dump_flags);
714 fprintf (dump_file, "\n");
715 }
716 return;
717 }
718 }
719
720 if (dump_file && (dump_flags & TDF_DETAILS))
721 {
722 fprintf (dump_file, "Visiting use-def links for ");
723 print_generic_expr (dump_file, var, dump_flags);
724 fprintf (dump_file, "\n");
725 }
726
727 stmt = SSA_NAME_DEF_STMT (var);
728 reexamine = false;
729
730 switch (TREE_CODE (stmt))
731 {
732 case RETURN_EXPR:
35cc02b5 733 gcc_assert (TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT);
0a39fd54 734 stmt = TREE_OPERAND (stmt, 0);
735 /* FALLTHRU */
736
35cc02b5 737 case GIMPLE_MODIFY_STMT:
0a39fd54 738 {
35cc02b5 739 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1), arg;
0a39fd54 740 STRIP_NOPS (rhs);
741
742 if (TREE_CODE (rhs) == CALL_EXPR)
743 {
744 arg = pass_through_call (rhs);
745 if (arg)
746 rhs = arg;
747 }
748
749 if (TREE_CODE (rhs) == SSA_NAME
750 && POINTER_TYPE_P (TREE_TYPE (rhs)))
751 reexamine = merge_object_sizes (osi, var, rhs, 0);
752
753 else if (TREE_CODE (rhs) == PLUS_EXPR)
754 reexamine = plus_expr_object_size (osi, var, rhs);
755
ec0fa513 756 else if (TREE_CODE (rhs) == COND_EXPR)
757 reexamine = cond_expr_object_size (osi, var, rhs);
758
0a39fd54 759 else
760 expr_object_size (osi, var, rhs);
761 break;
762 }
763
764 case ASM_EXPR:
765 /* Pointers defined by __asm__ statements can point anywhere. */
766 object_sizes[object_size_type][varno] = unknown[object_size_type];
767 break;
768
769 case NOP_EXPR:
770 {
771 tree decl = SSA_NAME_VAR (var);
772
773 gcc_assert (IS_EMPTY_STMT (stmt));
774
775 if (TREE_CODE (decl) != PARM_DECL && DECL_INITIAL (decl))
776 expr_object_size (osi, var, DECL_INITIAL (decl));
777 else
778 expr_object_size (osi, var, decl);
779 }
780 break;
781
782 case PHI_NODE:
783 {
784 int i;
785
786 for (i = 0; i < PHI_NUM_ARGS (stmt); i++)
787 {
788 tree rhs = PHI_ARG_DEF (stmt, i);
789
790 if (object_sizes[object_size_type][varno]
791 == unknown[object_size_type])
792 break;
793
794 if (TREE_CODE (rhs) == SSA_NAME)
795 reexamine |= merge_object_sizes (osi, var, rhs, 0);
796 else if (osi->pass == 0)
797 expr_object_size (osi, var, rhs);
798 }
799 break;
800 }
801 default:
802 gcc_unreachable ();
803 }
804
805 if (! reexamine
806 || object_sizes[object_size_type][varno] == unknown[object_size_type])
807 {
808 bitmap_set_bit (computed[object_size_type], varno);
809 bitmap_clear_bit (osi->reexamine, varno);
810 }
811 else
812 {
813 bitmap_set_bit (osi->reexamine, varno);
814 if (dump_file && (dump_flags & TDF_DETAILS))
815 {
816 fprintf (dump_file, "Need to reexamine ");
817 print_generic_expr (dump_file, var, dump_flags);
818 fprintf (dump_file, "\n");
819 }
820 }
821}
822
823
824/* Helper function for check_for_plus_in_loops. Called recursively
825 to detect loops. */
826
827static void
828check_for_plus_in_loops_1 (struct object_size_info *osi, tree var,
829 unsigned int depth)
830{
831 tree stmt = SSA_NAME_DEF_STMT (var);
832 unsigned int varno = SSA_NAME_VERSION (var);
833
834 if (osi->depths[varno])
835 {
836 if (osi->depths[varno] != depth)
837 {
838 unsigned int *sp;
839
840 /* Found a loop involving pointer addition. */
841 for (sp = osi->tos; sp > osi->stack; )
842 {
843 --sp;
844 bitmap_clear_bit (osi->reexamine, *sp);
845 bitmap_set_bit (computed[osi->object_size_type], *sp);
846 object_sizes[osi->object_size_type][*sp] = 0;
847 if (*sp == varno)
848 break;
849 }
850 }
851 return;
852 }
853 else if (! bitmap_bit_p (osi->reexamine, varno))
854 return;
855
856 osi->depths[varno] = depth;
857 *osi->tos++ = varno;
858
859 switch (TREE_CODE (stmt))
860 {
861 case RETURN_EXPR:
35cc02b5 862 gcc_assert (TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT);
0a39fd54 863 stmt = TREE_OPERAND (stmt, 0);
864 /* FALLTHRU */
865
35cc02b5 866 case GIMPLE_MODIFY_STMT:
0a39fd54 867 {
35cc02b5 868 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1), arg;
0a39fd54 869 STRIP_NOPS (rhs);
870
871 if (TREE_CODE (rhs) == CALL_EXPR)
872 {
873 arg = pass_through_call (rhs);
874 if (arg)
875 rhs = arg;
876 }
877
878 if (TREE_CODE (rhs) == SSA_NAME)
879 check_for_plus_in_loops_1 (osi, rhs, depth);
880 else if (TREE_CODE (rhs) == PLUS_EXPR)
881 {
882 tree op0 = TREE_OPERAND (rhs, 0);
883 tree op1 = TREE_OPERAND (rhs, 1);
884 tree cst, basevar;
885
886 if (TREE_CODE (op0) == SSA_NAME)
887 {
888 basevar = op0;
889 cst = op1;
890 }
891 else
892 {
893 basevar = op1;
894 cst = op0;
895 gcc_assert (TREE_CODE (basevar) == SSA_NAME);
896 }
897 gcc_assert (TREE_CODE (cst) == INTEGER_CST);
898
899 check_for_plus_in_loops_1 (osi, basevar,
900 depth + !integer_zerop (cst));
901 }
902 else
903 gcc_unreachable ();
904 break;
905 }
906 case PHI_NODE:
907 {
908 int i;
909
910 for (i = 0; i < PHI_NUM_ARGS (stmt); i++)
911 {
912 tree rhs = PHI_ARG_DEF (stmt, i);
913
914 if (TREE_CODE (rhs) == SSA_NAME)
915 check_for_plus_in_loops_1 (osi, rhs, depth);
916 }
917 break;
918 }
919 default:
920 gcc_unreachable ();
921 }
922
923 osi->depths[varno] = 0;
924 osi->tos--;
925}
926
927
928/* Check if some pointer we are computing object size of is being increased
929 within a loop. If yes, assume all the SSA variables participating in
930 that loop have minimum object sizes 0. */
931
932static void
933check_for_plus_in_loops (struct object_size_info *osi, tree var)
934{
935 tree stmt = SSA_NAME_DEF_STMT (var);
936
937 switch (TREE_CODE (stmt))
938 {
939 case RETURN_EXPR:
35cc02b5 940 gcc_assert (TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT);
0a39fd54 941 stmt = TREE_OPERAND (stmt, 0);
942 /* FALLTHRU */
943
35cc02b5 944 case GIMPLE_MODIFY_STMT:
0a39fd54 945 {
35cc02b5 946 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1), arg;
0a39fd54 947 STRIP_NOPS (rhs);
948
949 if (TREE_CODE (rhs) == CALL_EXPR)
950 {
951 arg = pass_through_call (rhs);
952 if (arg)
953 rhs = arg;
954 }
955
956 if (TREE_CODE (rhs) == PLUS_EXPR)
957 {
958 tree op0 = TREE_OPERAND (rhs, 0);
959 tree op1 = TREE_OPERAND (rhs, 1);
960 tree cst, basevar;
961
962 if (TREE_CODE (op0) == SSA_NAME)
963 {
964 basevar = op0;
965 cst = op1;
966 }
967 else
968 {
969 basevar = op1;
970 cst = op0;
971 gcc_assert (TREE_CODE (basevar) == SSA_NAME);
972 }
973 gcc_assert (TREE_CODE (cst) == INTEGER_CST);
974
975 if (integer_zerop (cst))
976 break;
977
978 osi->depths[SSA_NAME_VERSION (basevar)] = 1;
979 *osi->tos++ = SSA_NAME_VERSION (basevar);
980 check_for_plus_in_loops_1 (osi, var, 2);
981 osi->depths[SSA_NAME_VERSION (basevar)] = 0;
982 osi->tos--;
983 }
984 break;
985 }
986 default:
987 break;
988 }
989}
990
991
992/* Initialize data structures for the object size computation. */
993
994void
995init_object_sizes (void)
996{
997 int object_size_type;
998
999 if (object_sizes[0])
1000 return;
1001
1002 for (object_size_type = 0; object_size_type <= 3; object_size_type++)
1003 {
4c36ffe6 1004 object_sizes[object_size_type] = XNEWVEC (unsigned HOST_WIDE_INT, num_ssa_names);
0a39fd54 1005 computed[object_size_type] = BITMAP_ALLOC (NULL);
1006 }
1007
1008 init_offset_limit ();
1009}
1010
1011
1012/* Destroy data structures after the object size computation. */
1013
1014void
1015fini_object_sizes (void)
1016{
1017 int object_size_type;
1018
1019 for (object_size_type = 0; object_size_type <= 3; object_size_type++)
1020 {
1021 free (object_sizes[object_size_type]);
1022 BITMAP_FREE (computed[object_size_type]);
1023 object_sizes[object_size_type] = NULL;
1024 }
1025}
1026
1027
1028/* Simple pass to optimize all __builtin_object_size () builtins. */
1029
2a1990e9 1030static unsigned int
0a39fd54 1031compute_object_sizes (void)
1032{
1033 basic_block bb;
1034 FOR_EACH_BB (bb)
1035 {
1036 block_stmt_iterator i;
1037 for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
1038 {
1039 tree *stmtp = bsi_stmt_ptr (i);
1040 tree call = get_rhs (*stmtp);
1041 tree callee, result;
1042
1043 if (!call || TREE_CODE (call) != CALL_EXPR)
1044 continue;
1045
1046 callee = get_callee_fndecl (call);
1047 if (!callee
1048 || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
1049 || DECL_FUNCTION_CODE (callee) != BUILT_IN_OBJECT_SIZE)
1050 continue;
1051
1052 init_object_sizes ();
c2f47e15 1053 result = fold_call_expr (call, false);
0a39fd54 1054 if (!result)
1055 {
c2f47e15 1056 if (call_expr_nargs (call) == 2
1057 && POINTER_TYPE_P (TREE_TYPE (CALL_EXPR_ARG (call, 0))))
0a39fd54 1058 {
c2f47e15 1059 tree ost = CALL_EXPR_ARG (call, 1);
0a39fd54 1060
1061 if (host_integerp (ost, 1))
1062 {
1063 unsigned HOST_WIDE_INT object_size_type
1064 = tree_low_cst (ost, 1);
1065
1066 if (object_size_type < 2)
1067 result = fold_convert (size_type_node,
1068 integer_minus_one_node);
1069 else if (object_size_type < 4)
1070 result = size_zero_node;
1071 }
1072 }
1073
1074 if (!result)
1075 continue;
1076 }
1077
1078 if (dump_file && (dump_flags & TDF_DETAILS))
1079 {
1080 fprintf (dump_file, "Simplified\n ");
1081 print_generic_stmt (dump_file, *stmtp, dump_flags);
1082 }
1083
1084 if (!set_rhs (stmtp, result))
6276113b 1085 gcc_unreachable ();
0a39fd54 1086 update_stmt (*stmtp);
1087
1088 if (dump_file && (dump_flags & TDF_DETAILS))
1089 {
1090 fprintf (dump_file, "to\n ");
1091 print_generic_stmt (dump_file, *stmtp, dump_flags);
1092 fprintf (dump_file, "\n");
1093 }
1094 }
1095 }
1096
1097 fini_object_sizes ();
2a1990e9 1098 return 0;
0a39fd54 1099}
1100
1101struct tree_opt_pass pass_object_sizes =
1102{
1103 "objsz", /* name */
1104 NULL, /* gate */
1105 compute_object_sizes, /* execute */
1106 NULL, /* sub */
1107 NULL, /* next */
1108 0, /* static_pass_number */
1109 0, /* tv_id */
1110 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1111 0, /* properties_provided */
1112 0, /* properties_destroyed */
1113 0, /* todo_flags_start */
1114 TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */
1115 0 /* letter */
1116};
Mirror of https://gcc.gnu.org/git/gcc.git