1 /* __builtin_object_size (ptr, object_size_type) computation
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
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"
29 #include "tree-pretty-print.h"
30 #include "gimple-pretty-print.h"
31 #include "tree-flow.h"
32 #include "tree-pass.h"
33 #include "tree-ssa-propagate.h"
35 struct object_size_info
38 bitmap visited
, reexamine
;
42 unsigned int *stack
, *tos
;
45 static unsigned HOST_WIDE_INT unknown
[4] = { -1, -1, 0, 0 };
47 static tree
compute_object_offset (const_tree
, const_tree
);
48 static unsigned HOST_WIDE_INT
addr_object_size (struct object_size_info
*,
50 static unsigned HOST_WIDE_INT
alloc_object_size (const_gimple
, int);
51 static tree
pass_through_call (const_gimple
);
52 static void collect_object_sizes_for (struct object_size_info
*, tree
);
53 static void expr_object_size (struct object_size_info
*, tree
, tree
);
54 static bool merge_object_sizes (struct object_size_info
*, tree
, tree
,
55 unsigned HOST_WIDE_INT
);
56 static bool plus_stmt_object_size (struct object_size_info
*, tree
, gimple
);
57 static bool cond_expr_object_size (struct object_size_info
*, tree
, tree
);
58 static unsigned int compute_object_sizes (void);
59 static void init_offset_limit (void);
60 static void check_for_plus_in_loops (struct object_size_info
*, tree
);
61 static void check_for_plus_in_loops_1 (struct object_size_info
*, tree
,
64 /* object_sizes[0] is upper bound for number of bytes till the end of
66 object_sizes[1] is upper bound for number of bytes till the end of
67 the subobject (innermost array or field with address taken).
68 object_sizes[2] is lower bound for number of bytes till the end of
69 the object and object_sizes[3] lower bound for subobject. */
70 static unsigned HOST_WIDE_INT
*object_sizes
[4];
72 /* Bitmaps what object sizes have been computed already. */
73 static bitmap computed
[4];
75 /* Maximum value of offset we consider to be addition. */
76 static unsigned HOST_WIDE_INT offset_limit
;
79 /* Initialize OFFSET_LIMIT variable. */
81 init_offset_limit (void)
83 if (host_integerp (TYPE_MAX_VALUE (sizetype
), 1))
84 offset_limit
= tree_low_cst (TYPE_MAX_VALUE (sizetype
), 1);
91 /* Compute offset of EXPR within VAR. Return error_mark_node
95 compute_object_offset (const_tree expr
, const_tree var
)
97 enum tree_code code
= PLUS_EXPR
;
101 return size_zero_node
;
103 switch (TREE_CODE (expr
))
106 base
= compute_object_offset (TREE_OPERAND (expr
, 0), var
);
107 if (base
== error_mark_node
)
110 t
= TREE_OPERAND (expr
, 1);
111 off
= size_binop (PLUS_EXPR
, DECL_FIELD_OFFSET (t
),
112 size_int (tree_low_cst (DECL_FIELD_BIT_OFFSET (t
), 1)
118 case VIEW_CONVERT_EXPR
:
119 case NON_LVALUE_EXPR
:
120 return compute_object_offset (TREE_OPERAND (expr
, 0), var
);
123 base
= compute_object_offset (TREE_OPERAND (expr
, 0), var
);
124 if (base
== error_mark_node
)
127 off
= TYPE_SIZE_UNIT (TREE_TYPE (expr
));
131 base
= compute_object_offset (TREE_OPERAND (expr
, 0), var
);
132 if (base
== error_mark_node
)
135 t
= TREE_OPERAND (expr
, 1);
136 if (TREE_CODE (t
) == INTEGER_CST
&& tree_int_cst_sgn (t
) < 0)
139 t
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (t
), t
);
141 t
= fold_convert (sizetype
, t
);
142 off
= size_binop (MULT_EXPR
, TYPE_SIZE_UNIT (TREE_TYPE (expr
)), t
);
146 gcc_assert (TREE_CODE (TREE_OPERAND (expr
, 0)) == ADDR_EXPR
);
147 return TREE_OPERAND (expr
, 1);
150 return error_mark_node
;
153 return size_binop (code
, base
, off
);
157 /* Compute __builtin_object_size for PTR, which is a ADDR_EXPR.
158 OBJECT_SIZE_TYPE is the second argument from __builtin_object_size.
159 If unknown, return unknown[object_size_type]. */
161 static unsigned HOST_WIDE_INT
162 addr_object_size (struct object_size_info
*osi
, const_tree ptr
,
163 int object_size_type
)
165 tree pt_var
, pt_var_size
= NULL_TREE
, var_size
, bytes
;
167 gcc_assert (TREE_CODE (ptr
) == ADDR_EXPR
);
169 pt_var
= TREE_OPERAND (ptr
, 0);
170 if (REFERENCE_CLASS_P (pt_var
))
171 pt_var
= get_base_address (pt_var
);
174 && TREE_CODE (pt_var
) == MEM_REF
175 && TREE_CODE (TREE_OPERAND (pt_var
, 0)) == SSA_NAME
176 && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (pt_var
, 0))))
178 unsigned HOST_WIDE_INT sz
;
180 if (!osi
|| (object_size_type
& 1) != 0)
182 sz
= compute_builtin_object_size (TREE_OPERAND (pt_var
, 0),
183 object_size_type
& ~1);
184 if (host_integerp (TREE_OPERAND (pt_var
, 1), 0))
185 sz
-= TREE_INT_CST_LOW (TREE_OPERAND (pt_var
, 1));
191 tree var
= TREE_OPERAND (pt_var
, 0);
193 collect_object_sizes_for (osi
, var
);
194 if (bitmap_bit_p (computed
[object_size_type
],
195 SSA_NAME_VERSION (var
)))
196 sz
= object_sizes
[object_size_type
][SSA_NAME_VERSION (var
)];
198 sz
= unknown
[object_size_type
];
199 if (host_integerp (TREE_OPERAND (pt_var
, 1), 0))
200 sz
-= TREE_INT_CST_LOW (TREE_OPERAND (pt_var
, 1));
205 if (sz
!= unknown
[object_size_type
] && sz
< offset_limit
)
206 pt_var_size
= size_int (sz
);
209 && (SSA_VAR_P (pt_var
) || TREE_CODE (pt_var
) == STRING_CST
)
210 && TYPE_SIZE_UNIT (TREE_TYPE (pt_var
))
211 && host_integerp (TYPE_SIZE_UNIT (TREE_TYPE (pt_var
)), 1)
212 && (unsigned HOST_WIDE_INT
)
213 tree_low_cst (TYPE_SIZE_UNIT (TREE_TYPE (pt_var
)), 1)
215 pt_var_size
= TYPE_SIZE_UNIT (TREE_TYPE (pt_var
));
217 return unknown
[object_size_type
];
219 if (pt_var
!= TREE_OPERAND (ptr
, 0))
223 if (object_size_type
& 1)
225 var
= TREE_OPERAND (ptr
, 0);
228 && TREE_CODE (var
) != BIT_FIELD_REF
229 && TREE_CODE (var
) != COMPONENT_REF
230 && TREE_CODE (var
) != ARRAY_REF
231 && TREE_CODE (var
) != ARRAY_RANGE_REF
232 && TREE_CODE (var
) != REALPART_EXPR
233 && TREE_CODE (var
) != IMAGPART_EXPR
)
234 var
= TREE_OPERAND (var
, 0);
235 if (var
!= pt_var
&& TREE_CODE (var
) == ARRAY_REF
)
236 var
= TREE_OPERAND (var
, 0);
237 if (! TYPE_SIZE_UNIT (TREE_TYPE (var
))
238 || ! host_integerp (TYPE_SIZE_UNIT (TREE_TYPE (var
)), 1)
240 && tree_int_cst_lt (pt_var_size
,
241 TYPE_SIZE_UNIT (TREE_TYPE (var
)))))
243 else if (var
!= pt_var
&& TREE_CODE (pt_var
) == MEM_REF
)
246 /* For &X->fld, compute object size only if fld isn't the last
247 field, as struct { int i; char c[1]; } is often used instead
248 of flexible array member. */
249 while (v
&& v
!= pt_var
)
250 switch (TREE_CODE (v
))
253 if (TYPE_SIZE_UNIT (TREE_TYPE (TREE_OPERAND (v
, 0)))
254 && TREE_CODE (TREE_OPERAND (v
, 1)) == INTEGER_CST
)
257 = TYPE_DOMAIN (TREE_TYPE (TREE_OPERAND (v
, 0)));
259 && TYPE_MAX_VALUE (domain
)
260 && TREE_CODE (TYPE_MAX_VALUE (domain
))
262 && tree_int_cst_lt (TREE_OPERAND (v
, 1),
263 TYPE_MAX_VALUE (domain
)))
269 v
= TREE_OPERAND (v
, 0);
276 if (TREE_CODE (TREE_TYPE (v
)) != ARRAY_TYPE
)
281 while (v
!= pt_var
&& TREE_CODE (v
) == COMPONENT_REF
)
282 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
284 && TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
288 v
= TREE_OPERAND (v
, 0);
289 if (TREE_CODE (v
) == COMPONENT_REF
290 && TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
293 tree fld_chain
= DECL_CHAIN (TREE_OPERAND (v
, 1));
294 for (; fld_chain
; fld_chain
= DECL_CHAIN (fld_chain
))
295 if (TREE_CODE (fld_chain
) == FIELD_DECL
)
303 v
= TREE_OPERAND (v
, 0);
305 while (v
!= pt_var
&& TREE_CODE (v
) == COMPONENT_REF
)
306 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
308 && TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
312 v
= TREE_OPERAND (v
, 0);
330 var_size
= TYPE_SIZE_UNIT (TREE_TYPE (var
));
331 else if (!pt_var_size
)
332 return unknown
[object_size_type
];
334 var_size
= pt_var_size
;
335 bytes
= compute_object_offset (TREE_OPERAND (ptr
, 0), var
);
336 if (bytes
!= error_mark_node
)
338 if (TREE_CODE (bytes
) == INTEGER_CST
339 && tree_int_cst_lt (var_size
, bytes
))
340 bytes
= size_zero_node
;
342 bytes
= size_binop (MINUS_EXPR
, var_size
, bytes
);
346 && TREE_CODE (pt_var
) == MEM_REF
347 && bytes
!= error_mark_node
)
349 tree bytes2
= compute_object_offset (TREE_OPERAND (ptr
, 0), pt_var
);
350 if (bytes2
!= error_mark_node
)
352 bytes2
= size_binop (PLUS_EXPR
, bytes2
,
353 TREE_OPERAND (pt_var
, 1));
354 if (TREE_CODE (bytes2
) == INTEGER_CST
355 && tree_int_cst_lt (pt_var_size
, bytes2
))
356 bytes2
= size_zero_node
;
358 bytes2
= size_binop (MINUS_EXPR
, pt_var_size
, bytes2
);
359 bytes
= size_binop (MIN_EXPR
, bytes
, bytes2
);
363 else if (!pt_var_size
)
364 return unknown
[object_size_type
];
368 if (host_integerp (bytes
, 1))
369 return tree_low_cst (bytes
, 1);
371 return unknown
[object_size_type
];
375 /* Compute __builtin_object_size for CALL, which is a GIMPLE_CALL.
376 Handles various allocation calls. OBJECT_SIZE_TYPE is the second
377 argument from __builtin_object_size. If unknown, return
378 unknown[object_size_type]. */
380 static unsigned HOST_WIDE_INT
381 alloc_object_size (const_gimple call
, int object_size_type
)
383 tree callee
, bytes
= NULL_TREE
;
385 int arg1
= -1, arg2
= -1;
387 gcc_assert (is_gimple_call (call
));
389 callee
= gimple_call_fndecl (call
);
391 return unknown
[object_size_type
];
393 alloc_size
= lookup_attribute ("alloc_size", TYPE_ATTRIBUTES (TREE_TYPE(callee
)));
394 if (alloc_size
&& TREE_VALUE (alloc_size
))
396 tree p
= TREE_VALUE (alloc_size
);
398 arg1
= TREE_INT_CST_LOW (TREE_VALUE (p
))-1;
400 arg2
= TREE_INT_CST_LOW (TREE_VALUE (TREE_CHAIN (p
)))-1;
403 if (DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
404 switch (DECL_FUNCTION_CODE (callee
))
406 case BUILT_IN_CALLOC
:
409 case BUILT_IN_MALLOC
:
410 case BUILT_IN_ALLOCA
:
416 if (arg1
< 0 || arg1
>= (int)gimple_call_num_args (call
)
417 || TREE_CODE (gimple_call_arg (call
, arg1
)) != INTEGER_CST
419 && (arg2
>= (int)gimple_call_num_args (call
)
420 || TREE_CODE (gimple_call_arg (call
, arg2
)) != INTEGER_CST
)))
421 return unknown
[object_size_type
];
424 bytes
= size_binop (MULT_EXPR
,
425 fold_convert (sizetype
, gimple_call_arg (call
, arg1
)),
426 fold_convert (sizetype
, gimple_call_arg (call
, arg2
)));
428 bytes
= fold_convert (sizetype
, gimple_call_arg (call
, arg1
));
430 if (bytes
&& host_integerp (bytes
, 1))
431 return tree_low_cst (bytes
, 1);
433 return unknown
[object_size_type
];
437 /* If object size is propagated from one of function's arguments directly
438 to its return value, return that argument for GIMPLE_CALL statement CALL.
439 Otherwise return NULL. */
442 pass_through_call (const_gimple call
)
444 tree callee
= gimple_call_fndecl (call
);
447 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
448 switch (DECL_FUNCTION_CODE (callee
))
450 case BUILT_IN_MEMCPY
:
451 case BUILT_IN_MEMMOVE
:
452 case BUILT_IN_MEMSET
:
453 case BUILT_IN_STRCPY
:
454 case BUILT_IN_STRNCPY
:
455 case BUILT_IN_STRCAT
:
456 case BUILT_IN_STRNCAT
:
457 case BUILT_IN_MEMCPY_CHK
:
458 case BUILT_IN_MEMMOVE_CHK
:
459 case BUILT_IN_MEMSET_CHK
:
460 case BUILT_IN_STRCPY_CHK
:
461 case BUILT_IN_STRNCPY_CHK
:
462 case BUILT_IN_STRCAT_CHK
:
463 case BUILT_IN_STRNCAT_CHK
:
464 if (gimple_call_num_args (call
) >= 1)
465 return gimple_call_arg (call
, 0);
475 /* Compute __builtin_object_size value for PTR. OBJECT_SIZE_TYPE is the
476 second argument from __builtin_object_size. */
478 unsigned HOST_WIDE_INT
479 compute_builtin_object_size (tree ptr
, int object_size_type
)
481 gcc_assert (object_size_type
>= 0 && object_size_type
<= 3);
484 init_offset_limit ();
486 if (TREE_CODE (ptr
) == ADDR_EXPR
)
487 return addr_object_size (NULL
, ptr
, object_size_type
);
489 if (TREE_CODE (ptr
) == SSA_NAME
490 && POINTER_TYPE_P (TREE_TYPE (ptr
))
491 && object_sizes
[object_size_type
] != NULL
)
493 if (!bitmap_bit_p (computed
[object_size_type
], SSA_NAME_VERSION (ptr
)))
495 struct object_size_info osi
;
501 fprintf (dump_file
, "Computing %s %sobject size for ",
502 (object_size_type
& 2) ? "minimum" : "maximum",
503 (object_size_type
& 1) ? "sub" : "");
504 print_generic_expr (dump_file
, ptr
, dump_flags
);
505 fprintf (dump_file
, ":\n");
508 osi
.visited
= BITMAP_ALLOC (NULL
);
509 osi
.reexamine
= BITMAP_ALLOC (NULL
);
510 osi
.object_size_type
= object_size_type
;
515 /* First pass: walk UD chains, compute object sizes that
516 can be computed. osi.reexamine bitmap at the end will
517 contain what variables were found in dependency cycles
518 and therefore need to be reexamined. */
521 collect_object_sizes_for (&osi
, ptr
);
523 /* Second pass: keep recomputing object sizes of variables
524 that need reexamination, until no object sizes are
525 increased or all object sizes are computed. */
526 if (! bitmap_empty_p (osi
.reexamine
))
528 bitmap reexamine
= BITMAP_ALLOC (NULL
);
530 /* If looking for minimum instead of maximum object size,
531 detect cases where a pointer is increased in a loop.
532 Although even without this detection pass 2 would eventually
533 terminate, it could take a long time. If a pointer is
534 increasing this way, we need to assume 0 object size.
535 E.g. p = &buf[0]; while (cond) p = p + 4; */
536 if (object_size_type
& 2)
538 osi
.depths
= XCNEWVEC (unsigned int, num_ssa_names
);
539 osi
.stack
= XNEWVEC (unsigned int, num_ssa_names
);
542 /* collect_object_sizes_for is changing
543 osi.reexamine bitmap, so iterate over a copy. */
544 bitmap_copy (reexamine
, osi
.reexamine
);
545 EXECUTE_IF_SET_IN_BITMAP (reexamine
, 0, i
, bi
)
546 if (bitmap_bit_p (osi
.reexamine
, i
))
547 check_for_plus_in_loops (&osi
, ssa_name (i
));
560 /* collect_object_sizes_for is changing
561 osi.reexamine bitmap, so iterate over a copy. */
562 bitmap_copy (reexamine
, osi
.reexamine
);
563 EXECUTE_IF_SET_IN_BITMAP (reexamine
, 0, i
, bi
)
564 if (bitmap_bit_p (osi
.reexamine
, i
))
566 collect_object_sizes_for (&osi
, ssa_name (i
));
567 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
569 fprintf (dump_file
, "Reexamining ");
570 print_generic_expr (dump_file
, ssa_name (i
),
572 fprintf (dump_file
, "\n");
578 BITMAP_FREE (reexamine
);
580 EXECUTE_IF_SET_IN_BITMAP (osi
.reexamine
, 0, i
, bi
)
581 bitmap_set_bit (computed
[object_size_type
], i
);
583 /* Debugging dumps. */
586 EXECUTE_IF_SET_IN_BITMAP (osi
.visited
, 0, i
, bi
)
587 if (object_sizes
[object_size_type
][i
]
588 != unknown
[object_size_type
])
590 print_generic_expr (dump_file
, ssa_name (i
),
593 ": %s %sobject size "
594 HOST_WIDE_INT_PRINT_UNSIGNED
"\n",
595 (object_size_type
& 2) ? "minimum" : "maximum",
596 (object_size_type
& 1) ? "sub" : "",
597 object_sizes
[object_size_type
][i
]);
601 BITMAP_FREE (osi
.reexamine
);
602 BITMAP_FREE (osi
.visited
);
605 return object_sizes
[object_size_type
][SSA_NAME_VERSION (ptr
)];
608 return unknown
[object_size_type
];
611 /* Compute object_sizes for PTR, defined to VALUE, which is not an SSA_NAME. */
614 expr_object_size (struct object_size_info
*osi
, tree ptr
, tree value
)
616 int object_size_type
= osi
->object_size_type
;
617 unsigned int varno
= SSA_NAME_VERSION (ptr
);
618 unsigned HOST_WIDE_INT bytes
;
620 gcc_assert (object_sizes
[object_size_type
][varno
]
621 != unknown
[object_size_type
]);
622 gcc_assert (osi
->pass
== 0);
624 if (TREE_CODE (value
) == WITH_SIZE_EXPR
)
625 value
= TREE_OPERAND (value
, 0);
627 /* Pointer variables should have been handled by merge_object_sizes. */
628 gcc_assert (TREE_CODE (value
) != SSA_NAME
629 || !POINTER_TYPE_P (TREE_TYPE (value
)));
631 if (TREE_CODE (value
) == ADDR_EXPR
)
632 bytes
= addr_object_size (osi
, value
, object_size_type
);
634 bytes
= unknown
[object_size_type
];
636 if ((object_size_type
& 2) == 0)
638 if (object_sizes
[object_size_type
][varno
] < bytes
)
639 object_sizes
[object_size_type
][varno
] = bytes
;
643 if (object_sizes
[object_size_type
][varno
] > bytes
)
644 object_sizes
[object_size_type
][varno
] = bytes
;
649 /* Compute object_sizes for PTR, defined to the result of a call. */
652 call_object_size (struct object_size_info
*osi
, tree ptr
, gimple call
)
654 int object_size_type
= osi
->object_size_type
;
655 unsigned int varno
= SSA_NAME_VERSION (ptr
);
656 unsigned HOST_WIDE_INT bytes
;
658 gcc_assert (is_gimple_call (call
));
660 gcc_assert (object_sizes
[object_size_type
][varno
]
661 != unknown
[object_size_type
]);
662 gcc_assert (osi
->pass
== 0);
664 bytes
= alloc_object_size (call
, object_size_type
);
666 if ((object_size_type
& 2) == 0)
668 if (object_sizes
[object_size_type
][varno
] < bytes
)
669 object_sizes
[object_size_type
][varno
] = bytes
;
673 if (object_sizes
[object_size_type
][varno
] > bytes
)
674 object_sizes
[object_size_type
][varno
] = bytes
;
679 /* Compute object_sizes for PTR, defined to an unknown value. */
682 unknown_object_size (struct object_size_info
*osi
, tree ptr
)
684 int object_size_type
= osi
->object_size_type
;
685 unsigned int varno
= SSA_NAME_VERSION (ptr
);
686 unsigned HOST_WIDE_INT bytes
;
688 gcc_assert (object_sizes
[object_size_type
][varno
]
689 != unknown
[object_size_type
]);
690 gcc_assert (osi
->pass
== 0);
692 bytes
= unknown
[object_size_type
];
694 if ((object_size_type
& 2) == 0)
696 if (object_sizes
[object_size_type
][varno
] < bytes
)
697 object_sizes
[object_size_type
][varno
] = bytes
;
701 if (object_sizes
[object_size_type
][varno
] > bytes
)
702 object_sizes
[object_size_type
][varno
] = bytes
;
707 /* Merge object sizes of ORIG + OFFSET into DEST. Return true if
708 the object size might need reexamination later. */
711 merge_object_sizes (struct object_size_info
*osi
, tree dest
, tree orig
,
712 unsigned HOST_WIDE_INT offset
)
714 int object_size_type
= osi
->object_size_type
;
715 unsigned int varno
= SSA_NAME_VERSION (dest
);
716 unsigned HOST_WIDE_INT orig_bytes
;
718 if (object_sizes
[object_size_type
][varno
] == unknown
[object_size_type
])
720 if (offset
>= offset_limit
)
722 object_sizes
[object_size_type
][varno
] = unknown
[object_size_type
];
727 collect_object_sizes_for (osi
, orig
);
729 orig_bytes
= object_sizes
[object_size_type
][SSA_NAME_VERSION (orig
)];
730 if (orig_bytes
!= unknown
[object_size_type
])
731 orig_bytes
= (offset
> orig_bytes
)
732 ? (unsigned HOST_WIDE_INT
) 0 : orig_bytes
- offset
;
734 if ((object_size_type
& 2) == 0)
736 if (object_sizes
[object_size_type
][varno
] < orig_bytes
)
738 object_sizes
[object_size_type
][varno
] = orig_bytes
;
744 if (object_sizes
[object_size_type
][varno
] > orig_bytes
)
746 object_sizes
[object_size_type
][varno
] = orig_bytes
;
750 return bitmap_bit_p (osi
->reexamine
, SSA_NAME_VERSION (orig
));
754 /* Compute object_sizes for VAR, defined to the result of an assignment
755 with operator POINTER_PLUS_EXPR. Return true if the object size might
756 need reexamination later. */
759 plus_stmt_object_size (struct object_size_info
*osi
, tree var
, gimple stmt
)
761 int object_size_type
= osi
->object_size_type
;
762 unsigned int varno
= SSA_NAME_VERSION (var
);
763 unsigned HOST_WIDE_INT bytes
;
766 if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
768 op0
= gimple_assign_rhs1 (stmt
);
769 op1
= gimple_assign_rhs2 (stmt
);
771 else if (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
773 tree rhs
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
774 gcc_assert (TREE_CODE (rhs
) == MEM_REF
);
775 op0
= TREE_OPERAND (rhs
, 0);
776 op1
= TREE_OPERAND (rhs
, 1);
781 if (object_sizes
[object_size_type
][varno
] == unknown
[object_size_type
])
784 /* Handle PTR + OFFSET here. */
785 if (TREE_CODE (op1
) == INTEGER_CST
786 && (TREE_CODE (op0
) == SSA_NAME
787 || TREE_CODE (op0
) == ADDR_EXPR
))
789 if (! host_integerp (op1
, 1))
790 bytes
= unknown
[object_size_type
];
791 else if (TREE_CODE (op0
) == SSA_NAME
)
792 return merge_object_sizes (osi
, var
, op0
, tree_low_cst (op1
, 1));
795 unsigned HOST_WIDE_INT off
= tree_low_cst (op1
, 1);
797 /* op0 will be ADDR_EXPR here. */
798 bytes
= addr_object_size (osi
, op0
, object_size_type
);
799 if (bytes
== unknown
[object_size_type
])
801 else if (off
> offset_limit
)
802 bytes
= unknown
[object_size_type
];
803 else if (off
> bytes
)
810 bytes
= unknown
[object_size_type
];
812 if ((object_size_type
& 2) == 0)
814 if (object_sizes
[object_size_type
][varno
] < bytes
)
815 object_sizes
[object_size_type
][varno
] = bytes
;
819 if (object_sizes
[object_size_type
][varno
] > bytes
)
820 object_sizes
[object_size_type
][varno
] = bytes
;
826 /* Compute object_sizes for VAR, defined to VALUE, which is
827 a COND_EXPR. Return true if the object size might need reexamination
831 cond_expr_object_size (struct object_size_info
*osi
, tree var
, tree value
)
834 int object_size_type
= osi
->object_size_type
;
835 unsigned int varno
= SSA_NAME_VERSION (var
);
836 bool reexamine
= false;
838 gcc_assert (TREE_CODE (value
) == COND_EXPR
);
840 if (object_sizes
[object_size_type
][varno
] == unknown
[object_size_type
])
843 then_
= COND_EXPR_THEN (value
);
844 else_
= COND_EXPR_ELSE (value
);
846 if (TREE_CODE (then_
) == SSA_NAME
)
847 reexamine
|= merge_object_sizes (osi
, var
, then_
, 0);
849 expr_object_size (osi
, var
, then_
);
851 if (TREE_CODE (else_
) == SSA_NAME
)
852 reexamine
|= merge_object_sizes (osi
, var
, else_
, 0);
854 expr_object_size (osi
, var
, else_
);
859 /* Compute object sizes for VAR.
860 For ADDR_EXPR an object size is the number of remaining bytes
861 to the end of the object (where what is considered an object depends on
862 OSI->object_size_type).
863 For allocation GIMPLE_CALL like malloc or calloc object size is the size
865 For POINTER_PLUS_EXPR where second operand is a constant integer,
866 object size is object size of the first operand minus the constant.
867 If the constant is bigger than the number of remaining bytes until the
868 end of the object, object size is 0, but if it is instead a pointer
869 subtraction, object size is unknown[object_size_type].
870 To differentiate addition from subtraction, ADDR_EXPR returns
871 unknown[object_size_type] for all objects bigger than half of the address
872 space, and constants less than half of the address space are considered
873 addition, while bigger constants subtraction.
874 For a memcpy like GIMPLE_CALL that always returns one of its arguments, the
875 object size is object size of that argument.
876 Otherwise, object size is the maximum of object sizes of variables
877 that it might be set to. */
880 collect_object_sizes_for (struct object_size_info
*osi
, tree var
)
882 int object_size_type
= osi
->object_size_type
;
883 unsigned int varno
= SSA_NAME_VERSION (var
);
887 if (bitmap_bit_p (computed
[object_size_type
], varno
))
892 if (bitmap_set_bit (osi
->visited
, varno
))
894 object_sizes
[object_size_type
][varno
]
895 = (object_size_type
& 2) ? -1 : 0;
899 /* Found a dependency loop. Mark the variable for later
901 bitmap_set_bit (osi
->reexamine
, varno
);
902 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
904 fprintf (dump_file
, "Found a dependency loop at ");
905 print_generic_expr (dump_file
, var
, dump_flags
);
906 fprintf (dump_file
, "\n");
912 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
914 fprintf (dump_file
, "Visiting use-def links for ");
915 print_generic_expr (dump_file
, var
, dump_flags
);
916 fprintf (dump_file
, "\n");
919 stmt
= SSA_NAME_DEF_STMT (var
);
922 switch (gimple_code (stmt
))
926 tree rhs
= gimple_assign_rhs1 (stmt
);
927 if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
928 || (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
929 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == MEM_REF
))
930 reexamine
= plus_stmt_object_size (osi
, var
, stmt
);
931 else if (gimple_assign_single_p (stmt
)
932 || gimple_assign_unary_nop_p (stmt
))
934 if (TREE_CODE (rhs
) == SSA_NAME
935 && POINTER_TYPE_P (TREE_TYPE (rhs
)))
936 reexamine
= merge_object_sizes (osi
, var
, rhs
, 0);
937 else if (TREE_CODE (rhs
) == COND_EXPR
)
938 reexamine
= cond_expr_object_size (osi
, var
, rhs
);
940 expr_object_size (osi
, var
, rhs
);
943 unknown_object_size (osi
, var
);
949 tree arg
= pass_through_call (stmt
);
952 if (TREE_CODE (arg
) == SSA_NAME
953 && POINTER_TYPE_P (TREE_TYPE (arg
)))
954 reexamine
= merge_object_sizes (osi
, var
, arg
, 0);
955 else if (TREE_CODE (arg
) == COND_EXPR
)
956 reexamine
= cond_expr_object_size (osi
, var
, arg
);
958 expr_object_size (osi
, var
, arg
);
961 call_object_size (osi
, var
, stmt
);
966 /* Pointers defined by __asm__ statements can point anywhere. */
967 object_sizes
[object_size_type
][varno
] = unknown
[object_size_type
];
972 tree decl
= SSA_NAME_VAR (var
);
974 if (TREE_CODE (decl
) != PARM_DECL
&& DECL_INITIAL (decl
))
975 expr_object_size (osi
, var
, DECL_INITIAL (decl
));
977 expr_object_size (osi
, var
, decl
);
985 for (i
= 0; i
< gimple_phi_num_args (stmt
); i
++)
987 tree rhs
= gimple_phi_arg (stmt
, i
)->def
;
989 if (object_sizes
[object_size_type
][varno
]
990 == unknown
[object_size_type
])
993 if (TREE_CODE (rhs
) == SSA_NAME
)
994 reexamine
|= merge_object_sizes (osi
, var
, rhs
, 0);
995 else if (osi
->pass
== 0)
996 expr_object_size (osi
, var
, rhs
);
1006 || object_sizes
[object_size_type
][varno
] == unknown
[object_size_type
])
1008 bitmap_set_bit (computed
[object_size_type
], varno
);
1009 bitmap_clear_bit (osi
->reexamine
, varno
);
1013 bitmap_set_bit (osi
->reexamine
, varno
);
1014 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1016 fprintf (dump_file
, "Need to reexamine ");
1017 print_generic_expr (dump_file
, var
, dump_flags
);
1018 fprintf (dump_file
, "\n");
1024 /* Helper function for check_for_plus_in_loops. Called recursively
1028 check_for_plus_in_loops_1 (struct object_size_info
*osi
, tree var
,
1031 gimple stmt
= SSA_NAME_DEF_STMT (var
);
1032 unsigned int varno
= SSA_NAME_VERSION (var
);
1034 if (osi
->depths
[varno
])
1036 if (osi
->depths
[varno
] != depth
)
1040 /* Found a loop involving pointer addition. */
1041 for (sp
= osi
->tos
; sp
> osi
->stack
; )
1044 bitmap_clear_bit (osi
->reexamine
, *sp
);
1045 bitmap_set_bit (computed
[osi
->object_size_type
], *sp
);
1046 object_sizes
[osi
->object_size_type
][*sp
] = 0;
1053 else if (! bitmap_bit_p (osi
->reexamine
, varno
))
1056 osi
->depths
[varno
] = depth
;
1057 *osi
->tos
++ = varno
;
1059 switch (gimple_code (stmt
))
1064 if ((gimple_assign_single_p (stmt
)
1065 || gimple_assign_unary_nop_p (stmt
))
1066 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
1068 tree rhs
= gimple_assign_rhs1 (stmt
);
1070 check_for_plus_in_loops_1 (osi
, rhs
, depth
);
1072 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
1074 tree basevar
= gimple_assign_rhs1 (stmt
);
1075 tree cst
= gimple_assign_rhs2 (stmt
);
1077 gcc_assert (TREE_CODE (cst
) == INTEGER_CST
);
1079 check_for_plus_in_loops_1 (osi
, basevar
,
1080 depth
+ !integer_zerop (cst
));
1089 tree arg
= pass_through_call (stmt
);
1092 if (TREE_CODE (arg
) == SSA_NAME
)
1093 check_for_plus_in_loops_1 (osi
, arg
, depth
);
1104 for (i
= 0; i
< gimple_phi_num_args (stmt
); i
++)
1106 tree rhs
= gimple_phi_arg (stmt
, i
)->def
;
1108 if (TREE_CODE (rhs
) == SSA_NAME
)
1109 check_for_plus_in_loops_1 (osi
, rhs
, depth
);
1118 osi
->depths
[varno
] = 0;
1123 /* Check if some pointer we are computing object size of is being increased
1124 within a loop. If yes, assume all the SSA variables participating in
1125 that loop have minimum object sizes 0. */
1128 check_for_plus_in_loops (struct object_size_info
*osi
, tree var
)
1130 gimple stmt
= SSA_NAME_DEF_STMT (var
);
1132 /* NOTE: In the pre-tuples code, we handled a CALL_EXPR here,
1133 and looked for a POINTER_PLUS_EXPR in the pass-through
1134 argument, if any. In GIMPLE, however, such an expression
1135 is not a valid call operand. */
1137 if (is_gimple_assign (stmt
)
1138 && gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
1140 tree basevar
= gimple_assign_rhs1 (stmt
);
1141 tree cst
= gimple_assign_rhs2 (stmt
);
1143 gcc_assert (TREE_CODE (cst
) == INTEGER_CST
);
1145 if (integer_zerop (cst
))
1148 osi
->depths
[SSA_NAME_VERSION (basevar
)] = 1;
1149 *osi
->tos
++ = SSA_NAME_VERSION (basevar
);
1150 check_for_plus_in_loops_1 (osi
, var
, 2);
1151 osi
->depths
[SSA_NAME_VERSION (basevar
)] = 0;
1157 /* Initialize data structures for the object size computation. */
1160 init_object_sizes (void)
1162 int object_size_type
;
1164 if (object_sizes
[0])
1167 for (object_size_type
= 0; object_size_type
<= 3; object_size_type
++)
1169 object_sizes
[object_size_type
] = XNEWVEC (unsigned HOST_WIDE_INT
, num_ssa_names
);
1170 computed
[object_size_type
] = BITMAP_ALLOC (NULL
);
1173 init_offset_limit ();
1177 /* Destroy data structures after the object size computation. */
1180 fini_object_sizes (void)
1182 int object_size_type
;
1184 for (object_size_type
= 0; object_size_type
<= 3; object_size_type
++)
1186 free (object_sizes
[object_size_type
]);
1187 BITMAP_FREE (computed
[object_size_type
]);
1188 object_sizes
[object_size_type
] = NULL
;
1193 /* Simple pass to optimize all __builtin_object_size () builtins. */
1196 compute_object_sizes (void)
1201 gimple_stmt_iterator i
;
1202 for (i
= gsi_start_bb (bb
); !gsi_end_p (i
); gsi_next (&i
))
1204 tree callee
, result
;
1205 gimple call
= gsi_stmt (i
);
1207 if (gimple_code (call
) != GIMPLE_CALL
)
1210 callee
= gimple_call_fndecl (call
);
1212 || DECL_BUILT_IN_CLASS (callee
) != BUILT_IN_NORMAL
1213 || DECL_FUNCTION_CODE (callee
) != BUILT_IN_OBJECT_SIZE
)
1216 init_object_sizes ();
1217 result
= fold_call_stmt (call
, false);
1220 if (gimple_call_num_args (call
) == 2
1221 && POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call
, 0))))
1223 tree ost
= gimple_call_arg (call
, 1);
1225 if (host_integerp (ost
, 1))
1227 unsigned HOST_WIDE_INT object_size_type
1228 = tree_low_cst (ost
, 1);
1230 if (object_size_type
< 2)
1231 result
= fold_convert (size_type_node
,
1232 integer_minus_one_node
);
1233 else if (object_size_type
< 4)
1234 result
= fold_convert (size_type_node
,
1243 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1245 fprintf (dump_file
, "Simplified\n ");
1246 print_gimple_stmt (dump_file
, call
, 0, dump_flags
);
1249 if (!update_call_from_tree (&i
, result
))
1252 /* NOTE: In the pre-tuples code, we called update_stmt here. This is
1253 now handled by gsi_replace, called from update_call_from_tree. */
1255 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1257 fprintf (dump_file
, "to\n ");
1258 print_gimple_stmt (dump_file
, call
, 0, dump_flags
);
1259 fprintf (dump_file
, "\n");
1264 fini_object_sizes ();
1268 struct gimple_opt_pass pass_object_sizes
=
1274 compute_object_sizes
, /* execute */
1277 0, /* static_pass_number */
1278 TV_NONE
, /* tv_id */
1279 PROP_cfg
| PROP_ssa
, /* properties_required */
1280 0, /* properties_provided */
1281 0, /* properties_destroyed */
1282 0, /* todo_flags_start */
1283 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */