1 /* __builtin_object_size (ptr, object_size_type) computation
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Jakub Jelinek <jakub@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
27 #include "diagnostic-core.h"
28 #include "tree-pretty-print.h"
29 #include "gimple-pretty-print.h"
30 #include "tree-flow.h"
31 #include "tree-pass.h"
32 #include "tree-ssa-propagate.h"
34 struct object_size_info
37 bitmap visited
, reexamine
;
41 unsigned int *stack
, *tos
;
44 static unsigned HOST_WIDE_INT unknown
[4] = { -1, -1, 0, 0 };
46 static tree
compute_object_offset (const_tree
, const_tree
);
47 static unsigned HOST_WIDE_INT
addr_object_size (struct object_size_info
*,
49 static unsigned HOST_WIDE_INT
alloc_object_size (const_gimple
, int);
50 static tree
pass_through_call (const_gimple
);
51 static void collect_object_sizes_for (struct object_size_info
*, tree
);
52 static void expr_object_size (struct object_size_info
*, tree
, tree
);
53 static bool merge_object_sizes (struct object_size_info
*, tree
, tree
,
54 unsigned HOST_WIDE_INT
);
55 static bool plus_stmt_object_size (struct object_size_info
*, tree
, gimple
);
56 static bool cond_expr_object_size (struct object_size_info
*, tree
, tree
);
57 static unsigned int compute_object_sizes (void);
58 static void init_offset_limit (void);
59 static void check_for_plus_in_loops (struct object_size_info
*, tree
);
60 static void check_for_plus_in_loops_1 (struct object_size_info
*, tree
,
63 /* object_sizes[0] is upper bound for number of bytes till the end of
65 object_sizes[1] is upper bound for number of bytes till the end of
66 the subobject (innermost array or field with address taken).
67 object_sizes[2] is lower bound for number of bytes till the end of
68 the object and object_sizes[3] lower bound for subobject. */
69 static unsigned HOST_WIDE_INT
*object_sizes
[4];
71 /* Bitmaps what object sizes have been computed already. */
72 static bitmap computed
[4];
74 /* Maximum value of offset we consider to be addition. */
75 static unsigned HOST_WIDE_INT offset_limit
;
78 /* Initialize OFFSET_LIMIT variable. */
80 init_offset_limit (void)
82 if (host_integerp (TYPE_MAX_VALUE (sizetype
), 1))
83 offset_limit
= tree_low_cst (TYPE_MAX_VALUE (sizetype
), 1);
90 /* Compute offset of EXPR within VAR. Return error_mark_node
94 compute_object_offset (const_tree expr
, const_tree var
)
96 enum tree_code code
= PLUS_EXPR
;
100 return size_zero_node
;
102 switch (TREE_CODE (expr
))
105 base
= compute_object_offset (TREE_OPERAND (expr
, 0), var
);
106 if (base
== error_mark_node
)
109 t
= TREE_OPERAND (expr
, 1);
110 off
= size_binop (PLUS_EXPR
, DECL_FIELD_OFFSET (t
),
111 size_int (tree_low_cst (DECL_FIELD_BIT_OFFSET (t
), 1)
117 case VIEW_CONVERT_EXPR
:
118 case NON_LVALUE_EXPR
:
119 return compute_object_offset (TREE_OPERAND (expr
, 0), var
);
122 base
= compute_object_offset (TREE_OPERAND (expr
, 0), var
);
123 if (base
== error_mark_node
)
126 off
= TYPE_SIZE_UNIT (TREE_TYPE (expr
));
130 base
= compute_object_offset (TREE_OPERAND (expr
, 0), var
);
131 if (base
== error_mark_node
)
134 t
= TREE_OPERAND (expr
, 1);
135 if (TREE_CODE (t
) == INTEGER_CST
&& tree_int_cst_sgn (t
) < 0)
138 t
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (t
), t
);
140 t
= fold_convert (sizetype
, t
);
141 off
= size_binop (MULT_EXPR
, TYPE_SIZE_UNIT (TREE_TYPE (expr
)), t
);
145 gcc_assert (TREE_CODE (TREE_OPERAND (expr
, 0)) == ADDR_EXPR
);
146 return double_int_to_tree (sizetype
, mem_ref_offset (expr
));
149 return error_mark_node
;
152 return size_binop (code
, base
, off
);
156 /* Compute __builtin_object_size for PTR, which is a ADDR_EXPR.
157 OBJECT_SIZE_TYPE is the second argument from __builtin_object_size.
158 If unknown, return unknown[object_size_type]. */
160 static unsigned HOST_WIDE_INT
161 addr_object_size (struct object_size_info
*osi
, const_tree ptr
,
162 int object_size_type
)
164 tree pt_var
, pt_var_size
= NULL_TREE
, var_size
, bytes
;
166 gcc_assert (TREE_CODE (ptr
) == ADDR_EXPR
);
168 pt_var
= TREE_OPERAND (ptr
, 0);
169 if (REFERENCE_CLASS_P (pt_var
))
170 pt_var
= get_base_address (pt_var
);
173 && TREE_CODE (pt_var
) == MEM_REF
174 && TREE_CODE (TREE_OPERAND (pt_var
, 0)) == SSA_NAME
175 && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (pt_var
, 0))))
177 unsigned HOST_WIDE_INT sz
;
179 if (!osi
|| (object_size_type
& 1) != 0)
181 sz
= compute_builtin_object_size (TREE_OPERAND (pt_var
, 0),
182 object_size_type
& ~1);
183 if (host_integerp (TREE_OPERAND (pt_var
, 1), 0))
184 sz
-= TREE_INT_CST_LOW (TREE_OPERAND (pt_var
, 1));
190 tree var
= TREE_OPERAND (pt_var
, 0);
192 collect_object_sizes_for (osi
, var
);
193 if (bitmap_bit_p (computed
[object_size_type
],
194 SSA_NAME_VERSION (var
)))
195 sz
= object_sizes
[object_size_type
][SSA_NAME_VERSION (var
)];
197 sz
= unknown
[object_size_type
];
198 if (host_integerp (TREE_OPERAND (pt_var
, 1), 0))
199 sz
-= TREE_INT_CST_LOW (TREE_OPERAND (pt_var
, 1));
204 if (sz
!= unknown
[object_size_type
] && sz
< offset_limit
)
205 pt_var_size
= size_int (sz
);
209 && host_integerp (DECL_SIZE_UNIT (pt_var
), 1)
210 && (unsigned HOST_WIDE_INT
)
211 tree_low_cst (DECL_SIZE_UNIT (pt_var
), 1) < offset_limit
)
212 pt_var_size
= DECL_SIZE_UNIT (pt_var
);
214 && (SSA_VAR_P (pt_var
) || TREE_CODE (pt_var
) == STRING_CST
)
215 && TYPE_SIZE_UNIT (TREE_TYPE (pt_var
))
216 && host_integerp (TYPE_SIZE_UNIT (TREE_TYPE (pt_var
)), 1)
217 && (unsigned HOST_WIDE_INT
)
218 tree_low_cst (TYPE_SIZE_UNIT (TREE_TYPE (pt_var
)), 1)
220 pt_var_size
= TYPE_SIZE_UNIT (TREE_TYPE (pt_var
));
222 return unknown
[object_size_type
];
224 if (pt_var
!= TREE_OPERAND (ptr
, 0))
228 if (object_size_type
& 1)
230 var
= TREE_OPERAND (ptr
, 0);
233 && TREE_CODE (var
) != BIT_FIELD_REF
234 && TREE_CODE (var
) != COMPONENT_REF
235 && TREE_CODE (var
) != ARRAY_REF
236 && TREE_CODE (var
) != ARRAY_RANGE_REF
237 && TREE_CODE (var
) != REALPART_EXPR
238 && TREE_CODE (var
) != IMAGPART_EXPR
)
239 var
= TREE_OPERAND (var
, 0);
240 if (var
!= pt_var
&& TREE_CODE (var
) == ARRAY_REF
)
241 var
= TREE_OPERAND (var
, 0);
242 if (! TYPE_SIZE_UNIT (TREE_TYPE (var
))
243 || ! host_integerp (TYPE_SIZE_UNIT (TREE_TYPE (var
)), 1)
245 && tree_int_cst_lt (pt_var_size
,
246 TYPE_SIZE_UNIT (TREE_TYPE (var
)))))
248 else if (var
!= pt_var
&& TREE_CODE (pt_var
) == MEM_REF
)
251 /* For &X->fld, compute object size only if fld isn't the last
252 field, as struct { int i; char c[1]; } is often used instead
253 of flexible array member. */
254 while (v
&& v
!= pt_var
)
255 switch (TREE_CODE (v
))
258 if (TYPE_SIZE_UNIT (TREE_TYPE (TREE_OPERAND (v
, 0)))
259 && TREE_CODE (TREE_OPERAND (v
, 1)) == INTEGER_CST
)
262 = TYPE_DOMAIN (TREE_TYPE (TREE_OPERAND (v
, 0)));
264 && TYPE_MAX_VALUE (domain
)
265 && TREE_CODE (TYPE_MAX_VALUE (domain
))
267 && tree_int_cst_lt (TREE_OPERAND (v
, 1),
268 TYPE_MAX_VALUE (domain
)))
274 v
= TREE_OPERAND (v
, 0);
281 if (TREE_CODE (TREE_TYPE (v
)) != ARRAY_TYPE
)
286 while (v
!= pt_var
&& TREE_CODE (v
) == COMPONENT_REF
)
287 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
289 && TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
293 v
= TREE_OPERAND (v
, 0);
294 if (TREE_CODE (v
) == COMPONENT_REF
295 && TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
298 tree fld_chain
= DECL_CHAIN (TREE_OPERAND (v
, 1));
299 for (; fld_chain
; fld_chain
= DECL_CHAIN (fld_chain
))
300 if (TREE_CODE (fld_chain
) == FIELD_DECL
)
308 v
= TREE_OPERAND (v
, 0);
310 while (v
!= pt_var
&& TREE_CODE (v
) == COMPONENT_REF
)
311 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
313 && TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
317 v
= TREE_OPERAND (v
, 0);
335 var_size
= TYPE_SIZE_UNIT (TREE_TYPE (var
));
336 else if (!pt_var_size
)
337 return unknown
[object_size_type
];
339 var_size
= pt_var_size
;
340 bytes
= compute_object_offset (TREE_OPERAND (ptr
, 0), var
);
341 if (bytes
!= error_mark_node
)
343 if (TREE_CODE (bytes
) == INTEGER_CST
344 && tree_int_cst_lt (var_size
, bytes
))
345 bytes
= size_zero_node
;
347 bytes
= size_binop (MINUS_EXPR
, var_size
, bytes
);
351 && TREE_CODE (pt_var
) == MEM_REF
352 && bytes
!= error_mark_node
)
354 tree bytes2
= compute_object_offset (TREE_OPERAND (ptr
, 0), pt_var
);
355 if (bytes2
!= error_mark_node
)
357 if (TREE_CODE (bytes2
) == INTEGER_CST
358 && tree_int_cst_lt (pt_var_size
, bytes2
))
359 bytes2
= size_zero_node
;
361 bytes2
= size_binop (MINUS_EXPR
, pt_var_size
, bytes2
);
362 bytes
= size_binop (MIN_EXPR
, bytes
, bytes2
);
366 else if (!pt_var_size
)
367 return unknown
[object_size_type
];
371 if (host_integerp (bytes
, 1))
372 return tree_low_cst (bytes
, 1);
374 return unknown
[object_size_type
];
378 /* Compute __builtin_object_size for CALL, which is a GIMPLE_CALL.
379 Handles various allocation calls. OBJECT_SIZE_TYPE is the second
380 argument from __builtin_object_size. If unknown, return
381 unknown[object_size_type]. */
383 static unsigned HOST_WIDE_INT
384 alloc_object_size (const_gimple call
, int object_size_type
)
386 tree callee
, bytes
= NULL_TREE
;
388 int arg1
= -1, arg2
= -1;
390 gcc_assert (is_gimple_call (call
));
392 callee
= gimple_call_fndecl (call
);
394 return unknown
[object_size_type
];
396 alloc_size
= lookup_attribute ("alloc_size", TYPE_ATTRIBUTES (TREE_TYPE(callee
)));
397 if (alloc_size
&& TREE_VALUE (alloc_size
))
399 tree p
= TREE_VALUE (alloc_size
);
401 arg1
= TREE_INT_CST_LOW (TREE_VALUE (p
))-1;
403 arg2
= TREE_INT_CST_LOW (TREE_VALUE (TREE_CHAIN (p
)))-1;
406 if (DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
407 switch (DECL_FUNCTION_CODE (callee
))
409 case BUILT_IN_CALLOC
:
412 case BUILT_IN_MALLOC
:
413 case BUILT_IN_ALLOCA
:
419 if (arg1
< 0 || arg1
>= (int)gimple_call_num_args (call
)
420 || TREE_CODE (gimple_call_arg (call
, arg1
)) != INTEGER_CST
422 && (arg2
>= (int)gimple_call_num_args (call
)
423 || TREE_CODE (gimple_call_arg (call
, arg2
)) != INTEGER_CST
)))
424 return unknown
[object_size_type
];
427 bytes
= size_binop (MULT_EXPR
,
428 fold_convert (sizetype
, gimple_call_arg (call
, arg1
)),
429 fold_convert (sizetype
, gimple_call_arg (call
, arg2
)));
431 bytes
= fold_convert (sizetype
, gimple_call_arg (call
, arg1
));
433 if (bytes
&& host_integerp (bytes
, 1))
434 return tree_low_cst (bytes
, 1);
436 return unknown
[object_size_type
];
440 /* If object size is propagated from one of function's arguments directly
441 to its return value, return that argument for GIMPLE_CALL statement CALL.
442 Otherwise return NULL. */
445 pass_through_call (const_gimple call
)
447 tree callee
= gimple_call_fndecl (call
);
450 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
451 switch (DECL_FUNCTION_CODE (callee
))
453 case BUILT_IN_MEMCPY
:
454 case BUILT_IN_MEMMOVE
:
455 case BUILT_IN_MEMSET
:
456 case BUILT_IN_STRCPY
:
457 case BUILT_IN_STRNCPY
:
458 case BUILT_IN_STRCAT
:
459 case BUILT_IN_STRNCAT
:
460 case BUILT_IN_MEMCPY_CHK
:
461 case BUILT_IN_MEMMOVE_CHK
:
462 case BUILT_IN_MEMSET_CHK
:
463 case BUILT_IN_STRCPY_CHK
:
464 case BUILT_IN_STRNCPY_CHK
:
465 case BUILT_IN_STRCAT_CHK
:
466 case BUILT_IN_STRNCAT_CHK
:
467 case BUILT_IN_ASSUME_ALIGNED
:
468 if (gimple_call_num_args (call
) >= 1)
469 return gimple_call_arg (call
, 0);
479 /* Compute __builtin_object_size value for PTR. OBJECT_SIZE_TYPE is the
480 second argument from __builtin_object_size. */
482 unsigned HOST_WIDE_INT
483 compute_builtin_object_size (tree ptr
, int object_size_type
)
485 gcc_assert (object_size_type
>= 0 && object_size_type
<= 3);
488 init_offset_limit ();
490 if (TREE_CODE (ptr
) == ADDR_EXPR
)
491 return addr_object_size (NULL
, ptr
, object_size_type
);
493 if (TREE_CODE (ptr
) == SSA_NAME
494 && POINTER_TYPE_P (TREE_TYPE (ptr
))
495 && object_sizes
[object_size_type
] != NULL
)
497 if (!bitmap_bit_p (computed
[object_size_type
], SSA_NAME_VERSION (ptr
)))
499 struct object_size_info osi
;
505 fprintf (dump_file
, "Computing %s %sobject size for ",
506 (object_size_type
& 2) ? "minimum" : "maximum",
507 (object_size_type
& 1) ? "sub" : "");
508 print_generic_expr (dump_file
, ptr
, dump_flags
);
509 fprintf (dump_file
, ":\n");
512 osi
.visited
= BITMAP_ALLOC (NULL
);
513 osi
.reexamine
= BITMAP_ALLOC (NULL
);
514 osi
.object_size_type
= object_size_type
;
519 /* First pass: walk UD chains, compute object sizes that
520 can be computed. osi.reexamine bitmap at the end will
521 contain what variables were found in dependency cycles
522 and therefore need to be reexamined. */
525 collect_object_sizes_for (&osi
, ptr
);
527 /* Second pass: keep recomputing object sizes of variables
528 that need reexamination, until no object sizes are
529 increased or all object sizes are computed. */
530 if (! bitmap_empty_p (osi
.reexamine
))
532 bitmap reexamine
= BITMAP_ALLOC (NULL
);
534 /* If looking for minimum instead of maximum object size,
535 detect cases where a pointer is increased in a loop.
536 Although even without this detection pass 2 would eventually
537 terminate, it could take a long time. If a pointer is
538 increasing this way, we need to assume 0 object size.
539 E.g. p = &buf[0]; while (cond) p = p + 4; */
540 if (object_size_type
& 2)
542 osi
.depths
= XCNEWVEC (unsigned int, num_ssa_names
);
543 osi
.stack
= XNEWVEC (unsigned int, num_ssa_names
);
546 /* collect_object_sizes_for is changing
547 osi.reexamine bitmap, so iterate over a copy. */
548 bitmap_copy (reexamine
, osi
.reexamine
);
549 EXECUTE_IF_SET_IN_BITMAP (reexamine
, 0, i
, bi
)
550 if (bitmap_bit_p (osi
.reexamine
, i
))
551 check_for_plus_in_loops (&osi
, ssa_name (i
));
564 /* collect_object_sizes_for is changing
565 osi.reexamine bitmap, so iterate over a copy. */
566 bitmap_copy (reexamine
, osi
.reexamine
);
567 EXECUTE_IF_SET_IN_BITMAP (reexamine
, 0, i
, bi
)
568 if (bitmap_bit_p (osi
.reexamine
, i
))
570 collect_object_sizes_for (&osi
, ssa_name (i
));
571 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
573 fprintf (dump_file
, "Reexamining ");
574 print_generic_expr (dump_file
, ssa_name (i
),
576 fprintf (dump_file
, "\n");
582 BITMAP_FREE (reexamine
);
584 EXECUTE_IF_SET_IN_BITMAP (osi
.reexamine
, 0, i
, bi
)
585 bitmap_set_bit (computed
[object_size_type
], i
);
587 /* Debugging dumps. */
590 EXECUTE_IF_SET_IN_BITMAP (osi
.visited
, 0, i
, bi
)
591 if (object_sizes
[object_size_type
][i
]
592 != unknown
[object_size_type
])
594 print_generic_expr (dump_file
, ssa_name (i
),
597 ": %s %sobject size "
598 HOST_WIDE_INT_PRINT_UNSIGNED
"\n",
599 (object_size_type
& 2) ? "minimum" : "maximum",
600 (object_size_type
& 1) ? "sub" : "",
601 object_sizes
[object_size_type
][i
]);
605 BITMAP_FREE (osi
.reexamine
);
606 BITMAP_FREE (osi
.visited
);
609 return object_sizes
[object_size_type
][SSA_NAME_VERSION (ptr
)];
612 return unknown
[object_size_type
];
615 /* Compute object_sizes for PTR, defined to VALUE, which is not an SSA_NAME. */
618 expr_object_size (struct object_size_info
*osi
, tree ptr
, tree value
)
620 int object_size_type
= osi
->object_size_type
;
621 unsigned int varno
= SSA_NAME_VERSION (ptr
);
622 unsigned HOST_WIDE_INT bytes
;
624 gcc_assert (object_sizes
[object_size_type
][varno
]
625 != unknown
[object_size_type
]);
626 gcc_assert (osi
->pass
== 0);
628 if (TREE_CODE (value
) == WITH_SIZE_EXPR
)
629 value
= TREE_OPERAND (value
, 0);
631 /* Pointer variables should have been handled by merge_object_sizes. */
632 gcc_assert (TREE_CODE (value
) != SSA_NAME
633 || !POINTER_TYPE_P (TREE_TYPE (value
)));
635 if (TREE_CODE (value
) == ADDR_EXPR
)
636 bytes
= addr_object_size (osi
, value
, object_size_type
);
638 bytes
= unknown
[object_size_type
];
640 if ((object_size_type
& 2) == 0)
642 if (object_sizes
[object_size_type
][varno
] < bytes
)
643 object_sizes
[object_size_type
][varno
] = bytes
;
647 if (object_sizes
[object_size_type
][varno
] > bytes
)
648 object_sizes
[object_size_type
][varno
] = bytes
;
653 /* Compute object_sizes for PTR, defined to the result of a call. */
656 call_object_size (struct object_size_info
*osi
, tree ptr
, gimple call
)
658 int object_size_type
= osi
->object_size_type
;
659 unsigned int varno
= SSA_NAME_VERSION (ptr
);
660 unsigned HOST_WIDE_INT bytes
;
662 gcc_assert (is_gimple_call (call
));
664 gcc_assert (object_sizes
[object_size_type
][varno
]
665 != unknown
[object_size_type
]);
666 gcc_assert (osi
->pass
== 0);
668 bytes
= alloc_object_size (call
, object_size_type
);
670 if ((object_size_type
& 2) == 0)
672 if (object_sizes
[object_size_type
][varno
] < bytes
)
673 object_sizes
[object_size_type
][varno
] = bytes
;
677 if (object_sizes
[object_size_type
][varno
] > bytes
)
678 object_sizes
[object_size_type
][varno
] = bytes
;
683 /* Compute object_sizes for PTR, defined to an unknown value. */
686 unknown_object_size (struct object_size_info
*osi
, tree ptr
)
688 int object_size_type
= osi
->object_size_type
;
689 unsigned int varno
= SSA_NAME_VERSION (ptr
);
690 unsigned HOST_WIDE_INT bytes
;
692 gcc_assert (object_sizes
[object_size_type
][varno
]
693 != unknown
[object_size_type
]);
694 gcc_assert (osi
->pass
== 0);
696 bytes
= unknown
[object_size_type
];
698 if ((object_size_type
& 2) == 0)
700 if (object_sizes
[object_size_type
][varno
] < bytes
)
701 object_sizes
[object_size_type
][varno
] = bytes
;
705 if (object_sizes
[object_size_type
][varno
] > bytes
)
706 object_sizes
[object_size_type
][varno
] = bytes
;
711 /* Merge object sizes of ORIG + OFFSET into DEST. Return true if
712 the object size might need reexamination later. */
715 merge_object_sizes (struct object_size_info
*osi
, tree dest
, tree orig
,
716 unsigned HOST_WIDE_INT offset
)
718 int object_size_type
= osi
->object_size_type
;
719 unsigned int varno
= SSA_NAME_VERSION (dest
);
720 unsigned HOST_WIDE_INT orig_bytes
;
722 if (object_sizes
[object_size_type
][varno
] == unknown
[object_size_type
])
724 if (offset
>= offset_limit
)
726 object_sizes
[object_size_type
][varno
] = unknown
[object_size_type
];
731 collect_object_sizes_for (osi
, orig
);
733 orig_bytes
= object_sizes
[object_size_type
][SSA_NAME_VERSION (orig
)];
734 if (orig_bytes
!= unknown
[object_size_type
])
735 orig_bytes
= (offset
> orig_bytes
)
736 ? (unsigned HOST_WIDE_INT
) 0 : orig_bytes
- offset
;
738 if ((object_size_type
& 2) == 0)
740 if (object_sizes
[object_size_type
][varno
] < orig_bytes
)
742 object_sizes
[object_size_type
][varno
] = orig_bytes
;
748 if (object_sizes
[object_size_type
][varno
] > orig_bytes
)
750 object_sizes
[object_size_type
][varno
] = orig_bytes
;
754 return bitmap_bit_p (osi
->reexamine
, SSA_NAME_VERSION (orig
));
758 /* Compute object_sizes for VAR, defined to the result of an assignment
759 with operator POINTER_PLUS_EXPR. Return true if the object size might
760 need reexamination later. */
763 plus_stmt_object_size (struct object_size_info
*osi
, tree var
, gimple stmt
)
765 int object_size_type
= osi
->object_size_type
;
766 unsigned int varno
= SSA_NAME_VERSION (var
);
767 unsigned HOST_WIDE_INT bytes
;
770 if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
772 op0
= gimple_assign_rhs1 (stmt
);
773 op1
= gimple_assign_rhs2 (stmt
);
775 else if (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
777 tree rhs
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
778 gcc_assert (TREE_CODE (rhs
) == MEM_REF
);
779 op0
= TREE_OPERAND (rhs
, 0);
780 op1
= TREE_OPERAND (rhs
, 1);
785 if (object_sizes
[object_size_type
][varno
] == unknown
[object_size_type
])
788 /* Handle PTR + OFFSET here. */
789 if (TREE_CODE (op1
) == INTEGER_CST
790 && (TREE_CODE (op0
) == SSA_NAME
791 || TREE_CODE (op0
) == ADDR_EXPR
))
793 if (! host_integerp (op1
, 1))
794 bytes
= unknown
[object_size_type
];
795 else if (TREE_CODE (op0
) == SSA_NAME
)
796 return merge_object_sizes (osi
, var
, op0
, tree_low_cst (op1
, 1));
799 unsigned HOST_WIDE_INT off
= tree_low_cst (op1
, 1);
801 /* op0 will be ADDR_EXPR here. */
802 bytes
= addr_object_size (osi
, op0
, object_size_type
);
803 if (bytes
== unknown
[object_size_type
])
805 else if (off
> offset_limit
)
806 bytes
= unknown
[object_size_type
];
807 else if (off
> bytes
)
814 bytes
= unknown
[object_size_type
];
816 if ((object_size_type
& 2) == 0)
818 if (object_sizes
[object_size_type
][varno
] < bytes
)
819 object_sizes
[object_size_type
][varno
] = bytes
;
823 if (object_sizes
[object_size_type
][varno
] > bytes
)
824 object_sizes
[object_size_type
][varno
] = bytes
;
830 /* Compute object_sizes for VAR, defined to VALUE, which is
831 a COND_EXPR. Return true if the object size might need reexamination
835 cond_expr_object_size (struct object_size_info
*osi
, tree var
, tree value
)
838 int object_size_type
= osi
->object_size_type
;
839 unsigned int varno
= SSA_NAME_VERSION (var
);
840 bool reexamine
= false;
842 gcc_assert (TREE_CODE (value
) == COND_EXPR
);
844 if (object_sizes
[object_size_type
][varno
] == unknown
[object_size_type
])
847 then_
= COND_EXPR_THEN (value
);
848 else_
= COND_EXPR_ELSE (value
);
850 if (TREE_CODE (then_
) == SSA_NAME
)
851 reexamine
|= merge_object_sizes (osi
, var
, then_
, 0);
853 expr_object_size (osi
, var
, then_
);
855 if (TREE_CODE (else_
) == SSA_NAME
)
856 reexamine
|= merge_object_sizes (osi
, var
, else_
, 0);
858 expr_object_size (osi
, var
, else_
);
863 /* Compute object sizes for VAR.
864 For ADDR_EXPR an object size is the number of remaining bytes
865 to the end of the object (where what is considered an object depends on
866 OSI->object_size_type).
867 For allocation GIMPLE_CALL like malloc or calloc object size is the size
869 For POINTER_PLUS_EXPR where second operand is a constant integer,
870 object size is object size of the first operand minus the constant.
871 If the constant is bigger than the number of remaining bytes until the
872 end of the object, object size is 0, but if it is instead a pointer
873 subtraction, object size is unknown[object_size_type].
874 To differentiate addition from subtraction, ADDR_EXPR returns
875 unknown[object_size_type] for all objects bigger than half of the address
876 space, and constants less than half of the address space are considered
877 addition, while bigger constants subtraction.
878 For a memcpy like GIMPLE_CALL that always returns one of its arguments, the
879 object size is object size of that argument.
880 Otherwise, object size is the maximum of object sizes of variables
881 that it might be set to. */
884 collect_object_sizes_for (struct object_size_info
*osi
, tree var
)
886 int object_size_type
= osi
->object_size_type
;
887 unsigned int varno
= SSA_NAME_VERSION (var
);
891 if (bitmap_bit_p (computed
[object_size_type
], varno
))
896 if (bitmap_set_bit (osi
->visited
, varno
))
898 object_sizes
[object_size_type
][varno
]
899 = (object_size_type
& 2) ? -1 : 0;
903 /* Found a dependency loop. Mark the variable for later
905 bitmap_set_bit (osi
->reexamine
, varno
);
906 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
908 fprintf (dump_file
, "Found a dependency loop at ");
909 print_generic_expr (dump_file
, var
, dump_flags
);
910 fprintf (dump_file
, "\n");
916 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
918 fprintf (dump_file
, "Visiting use-def links for ");
919 print_generic_expr (dump_file
, var
, dump_flags
);
920 fprintf (dump_file
, "\n");
923 stmt
= SSA_NAME_DEF_STMT (var
);
926 switch (gimple_code (stmt
))
930 tree rhs
= gimple_assign_rhs1 (stmt
);
931 if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
932 || (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
933 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == MEM_REF
))
934 reexamine
= plus_stmt_object_size (osi
, var
, stmt
);
935 else if (gimple_assign_single_p (stmt
)
936 || gimple_assign_unary_nop_p (stmt
))
938 if (TREE_CODE (rhs
) == SSA_NAME
939 && POINTER_TYPE_P (TREE_TYPE (rhs
)))
940 reexamine
= merge_object_sizes (osi
, var
, rhs
, 0);
941 else if (TREE_CODE (rhs
) == COND_EXPR
)
942 reexamine
= cond_expr_object_size (osi
, var
, rhs
);
944 expr_object_size (osi
, var
, rhs
);
947 unknown_object_size (osi
, var
);
953 tree arg
= pass_through_call (stmt
);
956 if (TREE_CODE (arg
) == SSA_NAME
957 && POINTER_TYPE_P (TREE_TYPE (arg
)))
958 reexamine
= merge_object_sizes (osi
, var
, arg
, 0);
959 else if (TREE_CODE (arg
) == COND_EXPR
)
960 reexamine
= cond_expr_object_size (osi
, var
, arg
);
962 expr_object_size (osi
, var
, arg
);
965 call_object_size (osi
, var
, stmt
);
970 /* Pointers defined by __asm__ statements can point anywhere. */
971 object_sizes
[object_size_type
][varno
] = unknown
[object_size_type
];
976 tree decl
= SSA_NAME_VAR (var
);
978 if (TREE_CODE (decl
) != PARM_DECL
&& DECL_INITIAL (decl
))
979 expr_object_size (osi
, var
, DECL_INITIAL (decl
));
981 expr_object_size (osi
, var
, decl
);
989 for (i
= 0; i
< gimple_phi_num_args (stmt
); i
++)
991 tree rhs
= gimple_phi_arg (stmt
, i
)->def
;
993 if (object_sizes
[object_size_type
][varno
]
994 == unknown
[object_size_type
])
997 if (TREE_CODE (rhs
) == SSA_NAME
)
998 reexamine
|= merge_object_sizes (osi
, var
, rhs
, 0);
999 else if (osi
->pass
== 0)
1000 expr_object_size (osi
, var
, rhs
);
1010 || object_sizes
[object_size_type
][varno
] == unknown
[object_size_type
])
1012 bitmap_set_bit (computed
[object_size_type
], varno
);
1013 bitmap_clear_bit (osi
->reexamine
, varno
);
1017 bitmap_set_bit (osi
->reexamine
, varno
);
1018 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1020 fprintf (dump_file
, "Need to reexamine ");
1021 print_generic_expr (dump_file
, var
, dump_flags
);
1022 fprintf (dump_file
, "\n");
1028 /* Helper function for check_for_plus_in_loops. Called recursively
1032 check_for_plus_in_loops_1 (struct object_size_info
*osi
, tree var
,
1035 gimple stmt
= SSA_NAME_DEF_STMT (var
);
1036 unsigned int varno
= SSA_NAME_VERSION (var
);
1038 if (osi
->depths
[varno
])
1040 if (osi
->depths
[varno
] != depth
)
1044 /* Found a loop involving pointer addition. */
1045 for (sp
= osi
->tos
; sp
> osi
->stack
; )
1048 bitmap_clear_bit (osi
->reexamine
, *sp
);
1049 bitmap_set_bit (computed
[osi
->object_size_type
], *sp
);
1050 object_sizes
[osi
->object_size_type
][*sp
] = 0;
1057 else if (! bitmap_bit_p (osi
->reexamine
, varno
))
1060 osi
->depths
[varno
] = depth
;
1061 *osi
->tos
++ = varno
;
1063 switch (gimple_code (stmt
))
1068 if ((gimple_assign_single_p (stmt
)
1069 || gimple_assign_unary_nop_p (stmt
))
1070 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
1072 tree rhs
= gimple_assign_rhs1 (stmt
);
1074 check_for_plus_in_loops_1 (osi
, rhs
, depth
);
1076 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
1078 tree basevar
= gimple_assign_rhs1 (stmt
);
1079 tree cst
= gimple_assign_rhs2 (stmt
);
1081 gcc_assert (TREE_CODE (cst
) == INTEGER_CST
);
1083 check_for_plus_in_loops_1 (osi
, basevar
,
1084 depth
+ !integer_zerop (cst
));
1093 tree arg
= pass_through_call (stmt
);
1096 if (TREE_CODE (arg
) == SSA_NAME
)
1097 check_for_plus_in_loops_1 (osi
, arg
, depth
);
1108 for (i
= 0; i
< gimple_phi_num_args (stmt
); i
++)
1110 tree rhs
= gimple_phi_arg (stmt
, i
)->def
;
1112 if (TREE_CODE (rhs
) == SSA_NAME
)
1113 check_for_plus_in_loops_1 (osi
, rhs
, depth
);
1122 osi
->depths
[varno
] = 0;
1127 /* Check if some pointer we are computing object size of is being increased
1128 within a loop. If yes, assume all the SSA variables participating in
1129 that loop have minimum object sizes 0. */
1132 check_for_plus_in_loops (struct object_size_info
*osi
, tree var
)
1134 gimple stmt
= SSA_NAME_DEF_STMT (var
);
1136 /* NOTE: In the pre-tuples code, we handled a CALL_EXPR here,
1137 and looked for a POINTER_PLUS_EXPR in the pass-through
1138 argument, if any. In GIMPLE, however, such an expression
1139 is not a valid call operand. */
1141 if (is_gimple_assign (stmt
)
1142 && gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
1144 tree basevar
= gimple_assign_rhs1 (stmt
);
1145 tree cst
= gimple_assign_rhs2 (stmt
);
1147 gcc_assert (TREE_CODE (cst
) == INTEGER_CST
);
1149 if (integer_zerop (cst
))
1152 osi
->depths
[SSA_NAME_VERSION (basevar
)] = 1;
1153 *osi
->tos
++ = SSA_NAME_VERSION (basevar
);
1154 check_for_plus_in_loops_1 (osi
, var
, 2);
1155 osi
->depths
[SSA_NAME_VERSION (basevar
)] = 0;
1161 /* Initialize data structures for the object size computation. */
1164 init_object_sizes (void)
1166 int object_size_type
;
1168 if (object_sizes
[0])
1171 for (object_size_type
= 0; object_size_type
<= 3; object_size_type
++)
1173 object_sizes
[object_size_type
] = XNEWVEC (unsigned HOST_WIDE_INT
, num_ssa_names
);
1174 computed
[object_size_type
] = BITMAP_ALLOC (NULL
);
1177 init_offset_limit ();
1181 /* Destroy data structures after the object size computation. */
1184 fini_object_sizes (void)
1186 int object_size_type
;
1188 for (object_size_type
= 0; object_size_type
<= 3; object_size_type
++)
1190 free (object_sizes
[object_size_type
]);
1191 BITMAP_FREE (computed
[object_size_type
]);
1192 object_sizes
[object_size_type
] = NULL
;
1197 /* Simple pass to optimize all __builtin_object_size () builtins. */
1200 compute_object_sizes (void)
1205 gimple_stmt_iterator i
;
1206 for (i
= gsi_start_bb (bb
); !gsi_end_p (i
); gsi_next (&i
))
1208 tree callee
, result
;
1209 gimple call
= gsi_stmt (i
);
1211 if (gimple_code (call
) != GIMPLE_CALL
)
1214 callee
= gimple_call_fndecl (call
);
1216 || DECL_BUILT_IN_CLASS (callee
) != BUILT_IN_NORMAL
1217 || DECL_FUNCTION_CODE (callee
) != BUILT_IN_OBJECT_SIZE
)
1220 init_object_sizes ();
1221 result
= fold_call_stmt (call
, false);
1224 if (gimple_call_num_args (call
) == 2
1225 && POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call
, 0))))
1227 tree ost
= gimple_call_arg (call
, 1);
1229 if (host_integerp (ost
, 1))
1231 unsigned HOST_WIDE_INT object_size_type
1232 = tree_low_cst (ost
, 1);
1234 if (object_size_type
< 2)
1235 result
= fold_convert (size_type_node
,
1236 integer_minus_one_node
);
1237 else if (object_size_type
< 4)
1238 result
= build_zero_cst (size_type_node
);
1246 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1248 fprintf (dump_file
, "Simplified\n ");
1249 print_gimple_stmt (dump_file
, call
, 0, dump_flags
);
1252 if (!update_call_from_tree (&i
, result
))
1255 /* NOTE: In the pre-tuples code, we called update_stmt here. This is
1256 now handled by gsi_replace, called from update_call_from_tree. */
1258 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1260 fprintf (dump_file
, "to\n ");
1261 print_gimple_stmt (dump_file
, call
, 0, dump_flags
);
1262 fprintf (dump_file
, "\n");
1267 fini_object_sizes ();
1271 struct gimple_opt_pass pass_object_sizes
=
1277 compute_object_sizes
, /* execute */
1280 0, /* static_pass_number */
1281 TV_NONE
, /* tv_id */
1282 PROP_cfg
| PROP_ssa
, /* properties_required */
1283 0, /* properties_provided */
1284 0, /* properties_destroyed */
1285 0, /* todo_flags_start */
1286 TODO_verify_ssa
/* todo_flags_finish */