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