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"
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 TREE_OPERAND (expr
, 1);
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
);
208 && (SSA_VAR_P (pt_var
) || TREE_CODE (pt_var
) == STRING_CST
)
209 && TYPE_SIZE_UNIT (TREE_TYPE (pt_var
))
210 && host_integerp (TYPE_SIZE_UNIT (TREE_TYPE (pt_var
)), 1)
211 && (unsigned HOST_WIDE_INT
)
212 tree_low_cst (TYPE_SIZE_UNIT (TREE_TYPE (pt_var
)), 1)
214 pt_var_size
= TYPE_SIZE_UNIT (TREE_TYPE (pt_var
));
216 return unknown
[object_size_type
];
218 if (pt_var
!= TREE_OPERAND (ptr
, 0))
222 if (object_size_type
& 1)
224 var
= TREE_OPERAND (ptr
, 0);
227 && TREE_CODE (var
) != BIT_FIELD_REF
228 && TREE_CODE (var
) != COMPONENT_REF
229 && TREE_CODE (var
) != ARRAY_REF
230 && TREE_CODE (var
) != ARRAY_RANGE_REF
231 && TREE_CODE (var
) != REALPART_EXPR
232 && TREE_CODE (var
) != IMAGPART_EXPR
)
233 var
= TREE_OPERAND (var
, 0);
234 if (var
!= pt_var
&& TREE_CODE (var
) == ARRAY_REF
)
235 var
= TREE_OPERAND (var
, 0);
236 if (! TYPE_SIZE_UNIT (TREE_TYPE (var
))
237 || ! host_integerp (TYPE_SIZE_UNIT (TREE_TYPE (var
)), 1)
239 && tree_int_cst_lt (pt_var_size
,
240 TYPE_SIZE_UNIT (TREE_TYPE (var
)))))
242 else if (var
!= pt_var
&& TREE_CODE (pt_var
) == MEM_REF
)
245 /* For &X->fld, compute object size only if fld isn't the last
246 field, as struct { int i; char c[1]; } is often used instead
247 of flexible array member. */
248 while (v
&& v
!= pt_var
)
249 switch (TREE_CODE (v
))
252 if (TYPE_SIZE_UNIT (TREE_TYPE (TREE_OPERAND (v
, 0)))
253 && TREE_CODE (TREE_OPERAND (v
, 1)) == INTEGER_CST
)
256 = TYPE_DOMAIN (TREE_TYPE (TREE_OPERAND (v
, 0)));
258 && TYPE_MAX_VALUE (domain
)
259 && TREE_CODE (TYPE_MAX_VALUE (domain
))
261 && tree_int_cst_lt (TREE_OPERAND (v
, 1),
262 TYPE_MAX_VALUE (domain
)))
268 v
= TREE_OPERAND (v
, 0);
275 if (TREE_CODE (TREE_TYPE (v
)) != ARRAY_TYPE
)
280 while (v
!= pt_var
&& TREE_CODE (v
) == COMPONENT_REF
)
281 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
283 && TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
287 v
= TREE_OPERAND (v
, 0);
288 if (TREE_CODE (v
) == COMPONENT_REF
289 && TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
292 tree fld_chain
= TREE_CHAIN (TREE_OPERAND (v
, 1));
293 for (; fld_chain
; fld_chain
= TREE_CHAIN (fld_chain
))
294 if (TREE_CODE (fld_chain
) == FIELD_DECL
)
302 v
= TREE_OPERAND (v
, 0);
304 while (v
!= pt_var
&& TREE_CODE (v
) == COMPONENT_REF
)
305 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
307 && TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
311 v
= TREE_OPERAND (v
, 0);
329 var_size
= TYPE_SIZE_UNIT (TREE_TYPE (var
));
330 else if (!pt_var_size
)
331 return unknown
[object_size_type
];
333 var_size
= pt_var_size
;
334 bytes
= compute_object_offset (TREE_OPERAND (ptr
, 0), var
);
335 if (bytes
!= error_mark_node
)
337 if (TREE_CODE (bytes
) == INTEGER_CST
338 && tree_int_cst_lt (var_size
, bytes
))
339 bytes
= size_zero_node
;
341 bytes
= size_binop (MINUS_EXPR
, var_size
, bytes
);
345 && TREE_CODE (pt_var
) == MEM_REF
346 && bytes
!= error_mark_node
)
348 tree bytes2
= compute_object_offset (TREE_OPERAND (ptr
, 0), pt_var
);
349 if (bytes2
!= error_mark_node
)
351 bytes2
= size_binop (PLUS_EXPR
, bytes2
,
352 TREE_OPERAND (pt_var
, 1));
353 if (TREE_CODE (bytes2
) == INTEGER_CST
354 && tree_int_cst_lt (pt_var_size
, bytes2
))
355 bytes2
= size_zero_node
;
357 bytes2
= size_binop (MINUS_EXPR
, pt_var_size
, bytes2
);
358 bytes
= size_binop (MIN_EXPR
, bytes
, bytes2
);
362 else if (!pt_var_size
)
363 return unknown
[object_size_type
];
367 if (host_integerp (bytes
, 1))
368 return tree_low_cst (bytes
, 1);
370 return unknown
[object_size_type
];
374 /* Compute __builtin_object_size for CALL, which is a GIMPLE_CALL.
375 Handles various allocation calls. OBJECT_SIZE_TYPE is the second
376 argument from __builtin_object_size. If unknown, return
377 unknown[object_size_type]. */
379 static unsigned HOST_WIDE_INT
380 alloc_object_size (const_gimple call
, int object_size_type
)
382 tree callee
, bytes
= NULL_TREE
;
384 int arg1
= -1, arg2
= -1;
386 gcc_assert (is_gimple_call (call
));
388 callee
= gimple_call_fndecl (call
);
390 return unknown
[object_size_type
];
392 alloc_size
= lookup_attribute ("alloc_size", TYPE_ATTRIBUTES (TREE_TYPE(callee
)));
393 if (alloc_size
&& TREE_VALUE (alloc_size
))
395 tree p
= TREE_VALUE (alloc_size
);
397 arg1
= TREE_INT_CST_LOW (TREE_VALUE (p
))-1;
399 arg2
= TREE_INT_CST_LOW (TREE_VALUE (TREE_CHAIN (p
)))-1;
402 if (DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
403 switch (DECL_FUNCTION_CODE (callee
))
405 case BUILT_IN_CALLOC
:
408 case BUILT_IN_MALLOC
:
409 case BUILT_IN_ALLOCA
:
415 if (arg1
< 0 || arg1
>= (int)gimple_call_num_args (call
)
416 || TREE_CODE (gimple_call_arg (call
, arg1
)) != INTEGER_CST
418 && (arg2
>= (int)gimple_call_num_args (call
)
419 || TREE_CODE (gimple_call_arg (call
, arg2
)) != INTEGER_CST
)))
420 return unknown
[object_size_type
];
423 bytes
= size_binop (MULT_EXPR
,
424 fold_convert (sizetype
, gimple_call_arg (call
, arg1
)),
425 fold_convert (sizetype
, gimple_call_arg (call
, arg2
)));
427 bytes
= fold_convert (sizetype
, gimple_call_arg (call
, arg1
));
429 if (bytes
&& host_integerp (bytes
, 1))
430 return tree_low_cst (bytes
, 1);
432 return unknown
[object_size_type
];
436 /* If object size is propagated from one of function's arguments directly
437 to its return value, return that argument for GIMPLE_CALL statement CALL.
438 Otherwise return NULL. */
441 pass_through_call (const_gimple call
)
443 tree callee
= gimple_call_fndecl (call
);
446 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
447 switch (DECL_FUNCTION_CODE (callee
))
449 case BUILT_IN_MEMCPY
:
450 case BUILT_IN_MEMMOVE
:
451 case BUILT_IN_MEMSET
:
452 case BUILT_IN_STRCPY
:
453 case BUILT_IN_STRNCPY
:
454 case BUILT_IN_STRCAT
:
455 case BUILT_IN_STRNCAT
:
456 case BUILT_IN_MEMCPY_CHK
:
457 case BUILT_IN_MEMMOVE_CHK
:
458 case BUILT_IN_MEMSET_CHK
:
459 case BUILT_IN_STRCPY_CHK
:
460 case BUILT_IN_STRNCPY_CHK
:
461 case BUILT_IN_STRCAT_CHK
:
462 case BUILT_IN_STRNCAT_CHK
:
463 if (gimple_call_num_args (call
) >= 1)
464 return gimple_call_arg (call
, 0);
474 /* Compute __builtin_object_size value for PTR. OBJECT_SIZE_TYPE is the
475 second argument from __builtin_object_size. */
477 unsigned HOST_WIDE_INT
478 compute_builtin_object_size (tree ptr
, int object_size_type
)
480 gcc_assert (object_size_type
>= 0 && object_size_type
<= 3);
483 init_offset_limit ();
485 if (TREE_CODE (ptr
) == ADDR_EXPR
)
486 return addr_object_size (NULL
, ptr
, object_size_type
);
488 if (TREE_CODE (ptr
) == SSA_NAME
489 && POINTER_TYPE_P (TREE_TYPE (ptr
))
490 && object_sizes
[object_size_type
] != NULL
)
492 if (!bitmap_bit_p (computed
[object_size_type
], SSA_NAME_VERSION (ptr
)))
494 struct object_size_info osi
;
500 fprintf (dump_file
, "Computing %s %sobject size for ",
501 (object_size_type
& 2) ? "minimum" : "maximum",
502 (object_size_type
& 1) ? "sub" : "");
503 print_generic_expr (dump_file
, ptr
, dump_flags
);
504 fprintf (dump_file
, ":\n");
507 osi
.visited
= BITMAP_ALLOC (NULL
);
508 osi
.reexamine
= BITMAP_ALLOC (NULL
);
509 osi
.object_size_type
= object_size_type
;
514 /* First pass: walk UD chains, compute object sizes that
515 can be computed. osi.reexamine bitmap at the end will
516 contain what variables were found in dependency cycles
517 and therefore need to be reexamined. */
520 collect_object_sizes_for (&osi
, ptr
);
522 /* Second pass: keep recomputing object sizes of variables
523 that need reexamination, until no object sizes are
524 increased or all object sizes are computed. */
525 if (! bitmap_empty_p (osi
.reexamine
))
527 bitmap reexamine
= BITMAP_ALLOC (NULL
);
529 /* If looking for minimum instead of maximum object size,
530 detect cases where a pointer is increased in a loop.
531 Although even without this detection pass 2 would eventually
532 terminate, it could take a long time. If a pointer is
533 increasing this way, we need to assume 0 object size.
534 E.g. p = &buf[0]; while (cond) p = p + 4; */
535 if (object_size_type
& 2)
537 osi
.depths
= XCNEWVEC (unsigned int, num_ssa_names
);
538 osi
.stack
= XNEWVEC (unsigned int, num_ssa_names
);
541 /* collect_object_sizes_for is changing
542 osi.reexamine bitmap, so iterate over a copy. */
543 bitmap_copy (reexamine
, osi
.reexamine
);
544 EXECUTE_IF_SET_IN_BITMAP (reexamine
, 0, i
, bi
)
545 if (bitmap_bit_p (osi
.reexamine
, i
))
546 check_for_plus_in_loops (&osi
, ssa_name (i
));
559 /* collect_object_sizes_for is changing
560 osi.reexamine bitmap, so iterate over a copy. */
561 bitmap_copy (reexamine
, osi
.reexamine
);
562 EXECUTE_IF_SET_IN_BITMAP (reexamine
, 0, i
, bi
)
563 if (bitmap_bit_p (osi
.reexamine
, i
))
565 collect_object_sizes_for (&osi
, ssa_name (i
));
566 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
568 fprintf (dump_file
, "Reexamining ");
569 print_generic_expr (dump_file
, ssa_name (i
),
571 fprintf (dump_file
, "\n");
577 BITMAP_FREE (reexamine
);
579 EXECUTE_IF_SET_IN_BITMAP (osi
.reexamine
, 0, i
, bi
)
580 bitmap_set_bit (computed
[object_size_type
], i
);
582 /* Debugging dumps. */
585 EXECUTE_IF_SET_IN_BITMAP (osi
.visited
, 0, i
, bi
)
586 if (object_sizes
[object_size_type
][i
]
587 != unknown
[object_size_type
])
589 print_generic_expr (dump_file
, ssa_name (i
),
592 ": %s %sobject size "
593 HOST_WIDE_INT_PRINT_UNSIGNED
"\n",
594 (object_size_type
& 2) ? "minimum" : "maximum",
595 (object_size_type
& 1) ? "sub" : "",
596 object_sizes
[object_size_type
][i
]);
600 BITMAP_FREE (osi
.reexamine
);
601 BITMAP_FREE (osi
.visited
);
604 return object_sizes
[object_size_type
][SSA_NAME_VERSION (ptr
)];
607 return unknown
[object_size_type
];
610 /* Compute object_sizes for PTR, defined to VALUE, which is not an SSA_NAME. */
613 expr_object_size (struct object_size_info
*osi
, tree ptr
, tree value
)
615 int object_size_type
= osi
->object_size_type
;
616 unsigned int varno
= SSA_NAME_VERSION (ptr
);
617 unsigned HOST_WIDE_INT bytes
;
619 gcc_assert (object_sizes
[object_size_type
][varno
]
620 != unknown
[object_size_type
]);
621 gcc_assert (osi
->pass
== 0);
623 if (TREE_CODE (value
) == WITH_SIZE_EXPR
)
624 value
= TREE_OPERAND (value
, 0);
626 /* Pointer variables should have been handled by merge_object_sizes. */
627 gcc_assert (TREE_CODE (value
) != SSA_NAME
628 || !POINTER_TYPE_P (TREE_TYPE (value
)));
630 if (TREE_CODE (value
) == ADDR_EXPR
)
631 bytes
= addr_object_size (osi
, value
, object_size_type
);
633 bytes
= unknown
[object_size_type
];
635 if ((object_size_type
& 2) == 0)
637 if (object_sizes
[object_size_type
][varno
] < bytes
)
638 object_sizes
[object_size_type
][varno
] = bytes
;
642 if (object_sizes
[object_size_type
][varno
] > bytes
)
643 object_sizes
[object_size_type
][varno
] = bytes
;
648 /* Compute object_sizes for PTR, defined to the result of a call. */
651 call_object_size (struct object_size_info
*osi
, tree ptr
, gimple call
)
653 int object_size_type
= osi
->object_size_type
;
654 unsigned int varno
= SSA_NAME_VERSION (ptr
);
655 unsigned HOST_WIDE_INT bytes
;
657 gcc_assert (is_gimple_call (call
));
659 gcc_assert (object_sizes
[object_size_type
][varno
]
660 != unknown
[object_size_type
]);
661 gcc_assert (osi
->pass
== 0);
663 bytes
= alloc_object_size (call
, object_size_type
);
665 if ((object_size_type
& 2) == 0)
667 if (object_sizes
[object_size_type
][varno
] < bytes
)
668 object_sizes
[object_size_type
][varno
] = bytes
;
672 if (object_sizes
[object_size_type
][varno
] > bytes
)
673 object_sizes
[object_size_type
][varno
] = bytes
;
678 /* Compute object_sizes for PTR, defined to an unknown value. */
681 unknown_object_size (struct object_size_info
*osi
, tree ptr
)
683 int object_size_type
= osi
->object_size_type
;
684 unsigned int varno
= SSA_NAME_VERSION (ptr
);
685 unsigned HOST_WIDE_INT bytes
;
687 gcc_assert (object_sizes
[object_size_type
][varno
]
688 != unknown
[object_size_type
]);
689 gcc_assert (osi
->pass
== 0);
691 bytes
= unknown
[object_size_type
];
693 if ((object_size_type
& 2) == 0)
695 if (object_sizes
[object_size_type
][varno
] < bytes
)
696 object_sizes
[object_size_type
][varno
] = bytes
;
700 if (object_sizes
[object_size_type
][varno
] > bytes
)
701 object_sizes
[object_size_type
][varno
] = bytes
;
706 /* Merge object sizes of ORIG + OFFSET into DEST. Return true if
707 the object size might need reexamination later. */
710 merge_object_sizes (struct object_size_info
*osi
, tree dest
, tree orig
,
711 unsigned HOST_WIDE_INT offset
)
713 int object_size_type
= osi
->object_size_type
;
714 unsigned int varno
= SSA_NAME_VERSION (dest
);
715 unsigned HOST_WIDE_INT orig_bytes
;
717 if (object_sizes
[object_size_type
][varno
] == unknown
[object_size_type
])
719 if (offset
>= offset_limit
)
721 object_sizes
[object_size_type
][varno
] = unknown
[object_size_type
];
726 collect_object_sizes_for (osi
, orig
);
728 orig_bytes
= object_sizes
[object_size_type
][SSA_NAME_VERSION (orig
)];
729 if (orig_bytes
!= unknown
[object_size_type
])
730 orig_bytes
= (offset
> orig_bytes
)
731 ? (unsigned HOST_WIDE_INT
) 0 : orig_bytes
- offset
;
733 if ((object_size_type
& 2) == 0)
735 if (object_sizes
[object_size_type
][varno
] < orig_bytes
)
737 object_sizes
[object_size_type
][varno
] = orig_bytes
;
743 if (object_sizes
[object_size_type
][varno
] > orig_bytes
)
745 object_sizes
[object_size_type
][varno
] = orig_bytes
;
749 return bitmap_bit_p (osi
->reexamine
, SSA_NAME_VERSION (orig
));
753 /* Compute object_sizes for VAR, defined to the result of an assignment
754 with operator POINTER_PLUS_EXPR. Return true if the object size might
755 need reexamination later. */
758 plus_stmt_object_size (struct object_size_info
*osi
, tree var
, gimple stmt
)
760 int object_size_type
= osi
->object_size_type
;
761 unsigned int varno
= SSA_NAME_VERSION (var
);
762 unsigned HOST_WIDE_INT bytes
;
765 if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
767 op0
= gimple_assign_rhs1 (stmt
);
768 op1
= gimple_assign_rhs2 (stmt
);
770 else if (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
772 tree rhs
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
773 gcc_assert (TREE_CODE (rhs
) == MEM_REF
);
774 op0
= TREE_OPERAND (rhs
, 0);
775 op1
= TREE_OPERAND (rhs
, 1);
780 if (object_sizes
[object_size_type
][varno
] == unknown
[object_size_type
])
783 /* Handle PTR + OFFSET here. */
784 if (TREE_CODE (op1
) == INTEGER_CST
785 && (TREE_CODE (op0
) == SSA_NAME
786 || TREE_CODE (op0
) == ADDR_EXPR
))
788 if (! host_integerp (op1
, 1))
789 bytes
= unknown
[object_size_type
];
790 else if (TREE_CODE (op0
) == SSA_NAME
)
791 return merge_object_sizes (osi
, var
, op0
, tree_low_cst (op1
, 1));
794 unsigned HOST_WIDE_INT off
= tree_low_cst (op1
, 1);
796 /* op0 will be ADDR_EXPR here. */
797 bytes
= addr_object_size (osi
, op0
, object_size_type
);
798 if (bytes
== unknown
[object_size_type
])
800 else if (off
> offset_limit
)
801 bytes
= unknown
[object_size_type
];
802 else if (off
> bytes
)
809 bytes
= unknown
[object_size_type
];
811 if ((object_size_type
& 2) == 0)
813 if (object_sizes
[object_size_type
][varno
] < bytes
)
814 object_sizes
[object_size_type
][varno
] = bytes
;
818 if (object_sizes
[object_size_type
][varno
] > bytes
)
819 object_sizes
[object_size_type
][varno
] = bytes
;
825 /* Compute object_sizes for VAR, defined to VALUE, which is
826 a COND_EXPR. Return true if the object size might need reexamination
830 cond_expr_object_size (struct object_size_info
*osi
, tree var
, tree value
)
833 int object_size_type
= osi
->object_size_type
;
834 unsigned int varno
= SSA_NAME_VERSION (var
);
835 bool reexamine
= false;
837 gcc_assert (TREE_CODE (value
) == COND_EXPR
);
839 if (object_sizes
[object_size_type
][varno
] == unknown
[object_size_type
])
842 then_
= COND_EXPR_THEN (value
);
843 else_
= COND_EXPR_ELSE (value
);
845 if (TREE_CODE (then_
) == SSA_NAME
)
846 reexamine
|= merge_object_sizes (osi
, var
, then_
, 0);
848 expr_object_size (osi
, var
, then_
);
850 if (TREE_CODE (else_
) == SSA_NAME
)
851 reexamine
|= merge_object_sizes (osi
, var
, else_
, 0);
853 expr_object_size (osi
, var
, else_
);
858 /* Compute object sizes for VAR.
859 For ADDR_EXPR an object size is the number of remaining bytes
860 to the end of the object (where what is considered an object depends on
861 OSI->object_size_type).
862 For allocation GIMPLE_CALL like malloc or calloc object size is the size
864 For POINTER_PLUS_EXPR where second operand is a constant integer,
865 object size is object size of the first operand minus the constant.
866 If the constant is bigger than the number of remaining bytes until the
867 end of the object, object size is 0, but if it is instead a pointer
868 subtraction, object size is unknown[object_size_type].
869 To differentiate addition from subtraction, ADDR_EXPR returns
870 unknown[object_size_type] for all objects bigger than half of the address
871 space, and constants less than half of the address space are considered
872 addition, while bigger constants subtraction.
873 For a memcpy like GIMPLE_CALL that always returns one of its arguments, the
874 object size is object size of that argument.
875 Otherwise, object size is the maximum of object sizes of variables
876 that it might be set to. */
879 collect_object_sizes_for (struct object_size_info
*osi
, tree var
)
881 int object_size_type
= osi
->object_size_type
;
882 unsigned int varno
= SSA_NAME_VERSION (var
);
886 if (bitmap_bit_p (computed
[object_size_type
], varno
))
891 if (! bitmap_bit_p (osi
->visited
, varno
))
893 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 */