1 /* __builtin_object_size (ptr, object_size_type) computation
2 Copyright (C) 2004-2013 Free Software Foundation, Inc.
3 Contributed by Jakub Jelinek <jakub@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
26 #include "tree-object-size.h"
27 #include "diagnostic-core.h"
28 #include "gimple-pretty-print.h"
30 #include "basic-block.h"
31 #include "tree-ssa-alias.h"
32 #include "internal-fn.h"
33 #include "gimple-fold.h"
34 #include "gimple-expr.h"
37 #include "gimple-iterator.h"
38 #include "gimple-ssa.h"
39 #include "stringpool.h"
40 #include "tree-ssanames.h"
41 #include "tree-pass.h"
42 #include "tree-ssa-propagate.h"
43 #include "tree-phinodes.h"
44 #include "ssa-iterators.h"
46 struct object_size_info
49 bitmap visited
, reexamine
;
53 unsigned int *stack
, *tos
;
56 static const unsigned HOST_WIDE_INT unknown
[4] = { -1, -1, 0, 0 };
58 static tree
compute_object_offset (const_tree
, const_tree
);
59 static unsigned HOST_WIDE_INT
addr_object_size (struct object_size_info
*,
61 static unsigned HOST_WIDE_INT
alloc_object_size (const_gimple
, int);
62 static tree
pass_through_call (const_gimple
);
63 static void collect_object_sizes_for (struct object_size_info
*, tree
);
64 static void expr_object_size (struct object_size_info
*, tree
, tree
);
65 static bool merge_object_sizes (struct object_size_info
*, tree
, tree
,
66 unsigned HOST_WIDE_INT
);
67 static bool plus_stmt_object_size (struct object_size_info
*, tree
, gimple
);
68 static bool cond_expr_object_size (struct object_size_info
*, tree
, gimple
);
69 static unsigned int compute_object_sizes (void);
70 static void init_offset_limit (void);
71 static void check_for_plus_in_loops (struct object_size_info
*, tree
);
72 static void check_for_plus_in_loops_1 (struct object_size_info
*, tree
,
75 /* object_sizes[0] is upper bound for number of bytes till the end of
77 object_sizes[1] is upper bound for number of bytes till the end of
78 the subobject (innermost array or field with address taken).
79 object_sizes[2] is lower bound for number of bytes till the end of
80 the object and object_sizes[3] lower bound for subobject. */
81 static unsigned HOST_WIDE_INT
*object_sizes
[4];
83 /* Bitmaps what object sizes have been computed already. */
84 static bitmap computed
[4];
86 /* Maximum value of offset we consider to be addition. */
87 static unsigned HOST_WIDE_INT offset_limit
;
90 /* Initialize OFFSET_LIMIT variable. */
92 init_offset_limit (void)
94 if (tree_fits_uhwi_p (TYPE_MAX_VALUE (sizetype
)))
95 offset_limit
= tree_to_uhwi (TYPE_MAX_VALUE (sizetype
));
102 /* Compute offset of EXPR within VAR. Return error_mark_node
106 compute_object_offset (const_tree expr
, const_tree var
)
108 enum tree_code code
= PLUS_EXPR
;
112 return size_zero_node
;
114 switch (TREE_CODE (expr
))
117 base
= compute_object_offset (TREE_OPERAND (expr
, 0), var
);
118 if (base
== error_mark_node
)
121 t
= TREE_OPERAND (expr
, 1);
122 off
= size_binop (PLUS_EXPR
, DECL_FIELD_OFFSET (t
),
123 size_int (tree_to_uhwi (DECL_FIELD_BIT_OFFSET (t
))
129 case VIEW_CONVERT_EXPR
:
130 case NON_LVALUE_EXPR
:
131 return compute_object_offset (TREE_OPERAND (expr
, 0), var
);
134 base
= compute_object_offset (TREE_OPERAND (expr
, 0), var
);
135 if (base
== error_mark_node
)
138 off
= TYPE_SIZE_UNIT (TREE_TYPE (expr
));
142 base
= compute_object_offset (TREE_OPERAND (expr
, 0), var
);
143 if (base
== error_mark_node
)
146 t
= TREE_OPERAND (expr
, 1);
147 if (TREE_CODE (t
) == INTEGER_CST
&& tree_int_cst_sgn (t
) < 0)
150 t
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (t
), t
);
152 t
= fold_convert (sizetype
, t
);
153 off
= size_binop (MULT_EXPR
, TYPE_SIZE_UNIT (TREE_TYPE (expr
)), t
);
157 gcc_assert (TREE_CODE (TREE_OPERAND (expr
, 0)) == ADDR_EXPR
);
158 return double_int_to_tree (sizetype
, mem_ref_offset (expr
));
161 return error_mark_node
;
164 return size_binop (code
, base
, off
);
168 /* Compute __builtin_object_size for PTR, which is a ADDR_EXPR.
169 OBJECT_SIZE_TYPE is the second argument from __builtin_object_size.
170 If unknown, return unknown[object_size_type]. */
172 static unsigned HOST_WIDE_INT
173 addr_object_size (struct object_size_info
*osi
, const_tree ptr
,
174 int object_size_type
)
176 tree pt_var
, pt_var_size
= NULL_TREE
, var_size
, bytes
;
178 gcc_assert (TREE_CODE (ptr
) == ADDR_EXPR
);
180 pt_var
= TREE_OPERAND (ptr
, 0);
181 while (handled_component_p (pt_var
))
182 pt_var
= TREE_OPERAND (pt_var
, 0);
185 && TREE_CODE (pt_var
) == MEM_REF
)
187 unsigned HOST_WIDE_INT sz
;
189 if (!osi
|| (object_size_type
& 1) != 0
190 || TREE_CODE (TREE_OPERAND (pt_var
, 0)) != SSA_NAME
)
192 sz
= compute_builtin_object_size (TREE_OPERAND (pt_var
, 0),
193 object_size_type
& ~1);
197 tree var
= TREE_OPERAND (pt_var
, 0);
199 collect_object_sizes_for (osi
, var
);
200 if (bitmap_bit_p (computed
[object_size_type
],
201 SSA_NAME_VERSION (var
)))
202 sz
= object_sizes
[object_size_type
][SSA_NAME_VERSION (var
)];
204 sz
= unknown
[object_size_type
];
206 if (sz
!= unknown
[object_size_type
])
208 double_int dsz
= double_int::from_uhwi (sz
) - mem_ref_offset (pt_var
);
209 if (dsz
.is_negative ())
211 else if (dsz
.fits_uhwi ())
214 sz
= unknown
[object_size_type
];
217 if (sz
!= unknown
[object_size_type
] && sz
< offset_limit
)
218 pt_var_size
= size_int (sz
);
222 && tree_fits_uhwi_p (DECL_SIZE_UNIT (pt_var
))
223 && tree_to_uhwi (DECL_SIZE_UNIT (pt_var
)) < offset_limit
)
224 pt_var_size
= DECL_SIZE_UNIT (pt_var
);
226 && TREE_CODE (pt_var
) == STRING_CST
227 && TYPE_SIZE_UNIT (TREE_TYPE (pt_var
))
228 && tree_fits_uhwi_p (TYPE_SIZE_UNIT (TREE_TYPE (pt_var
)))
229 && tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (pt_var
)))
231 pt_var_size
= TYPE_SIZE_UNIT (TREE_TYPE (pt_var
));
233 return unknown
[object_size_type
];
235 if (pt_var
!= TREE_OPERAND (ptr
, 0))
239 if (object_size_type
& 1)
241 var
= TREE_OPERAND (ptr
, 0);
244 && TREE_CODE (var
) != BIT_FIELD_REF
245 && TREE_CODE (var
) != COMPONENT_REF
246 && TREE_CODE (var
) != ARRAY_REF
247 && TREE_CODE (var
) != ARRAY_RANGE_REF
248 && TREE_CODE (var
) != REALPART_EXPR
249 && TREE_CODE (var
) != IMAGPART_EXPR
)
250 var
= TREE_OPERAND (var
, 0);
251 if (var
!= pt_var
&& TREE_CODE (var
) == ARRAY_REF
)
252 var
= TREE_OPERAND (var
, 0);
253 if (! TYPE_SIZE_UNIT (TREE_TYPE (var
))
254 || ! tree_fits_uhwi_p (TYPE_SIZE_UNIT (TREE_TYPE (var
)))
256 && tree_int_cst_lt (pt_var_size
,
257 TYPE_SIZE_UNIT (TREE_TYPE (var
)))))
259 else if (var
!= pt_var
&& TREE_CODE (pt_var
) == MEM_REF
)
262 /* For &X->fld, compute object size only if fld isn't the last
263 field, as struct { int i; char c[1]; } is often used instead
264 of flexible array member. */
265 while (v
&& v
!= pt_var
)
266 switch (TREE_CODE (v
))
269 if (TYPE_SIZE_UNIT (TREE_TYPE (TREE_OPERAND (v
, 0)))
270 && TREE_CODE (TREE_OPERAND (v
, 1)) == INTEGER_CST
)
273 = TYPE_DOMAIN (TREE_TYPE (TREE_OPERAND (v
, 0)));
275 && TYPE_MAX_VALUE (domain
)
276 && TREE_CODE (TYPE_MAX_VALUE (domain
))
278 && tree_int_cst_lt (TREE_OPERAND (v
, 1),
279 TYPE_MAX_VALUE (domain
)))
285 v
= TREE_OPERAND (v
, 0);
292 if (TREE_CODE (TREE_TYPE (v
)) != ARRAY_TYPE
)
297 while (v
!= pt_var
&& TREE_CODE (v
) == COMPONENT_REF
)
298 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
300 && TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
304 v
= TREE_OPERAND (v
, 0);
305 if (TREE_CODE (v
) == COMPONENT_REF
306 && TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
309 tree fld_chain
= DECL_CHAIN (TREE_OPERAND (v
, 1));
310 for (; fld_chain
; fld_chain
= DECL_CHAIN (fld_chain
))
311 if (TREE_CODE (fld_chain
) == FIELD_DECL
)
319 v
= TREE_OPERAND (v
, 0);
321 while (v
!= pt_var
&& TREE_CODE (v
) == COMPONENT_REF
)
322 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
324 && TREE_CODE (TREE_TYPE (TREE_OPERAND (v
, 0)))
328 v
= TREE_OPERAND (v
, 0);
346 var_size
= TYPE_SIZE_UNIT (TREE_TYPE (var
));
347 else if (!pt_var_size
)
348 return unknown
[object_size_type
];
350 var_size
= pt_var_size
;
351 bytes
= compute_object_offset (TREE_OPERAND (ptr
, 0), var
);
352 if (bytes
!= error_mark_node
)
354 if (TREE_CODE (bytes
) == INTEGER_CST
355 && tree_int_cst_lt (var_size
, bytes
))
356 bytes
= size_zero_node
;
358 bytes
= size_binop (MINUS_EXPR
, var_size
, bytes
);
362 && TREE_CODE (pt_var
) == MEM_REF
363 && bytes
!= error_mark_node
)
365 tree bytes2
= compute_object_offset (TREE_OPERAND (ptr
, 0), pt_var
);
366 if (bytes2
!= error_mark_node
)
368 if (TREE_CODE (bytes2
) == INTEGER_CST
369 && tree_int_cst_lt (pt_var_size
, bytes2
))
370 bytes2
= size_zero_node
;
372 bytes2
= size_binop (MINUS_EXPR
, pt_var_size
, bytes2
);
373 bytes
= size_binop (MIN_EXPR
, bytes
, bytes2
);
377 else if (!pt_var_size
)
378 return unknown
[object_size_type
];
382 if (tree_fits_uhwi_p (bytes
))
383 return tree_to_uhwi (bytes
);
385 return unknown
[object_size_type
];
389 /* Compute __builtin_object_size for CALL, which is a GIMPLE_CALL.
390 Handles various allocation calls. OBJECT_SIZE_TYPE is the second
391 argument from __builtin_object_size. If unknown, return
392 unknown[object_size_type]. */
394 static unsigned HOST_WIDE_INT
395 alloc_object_size (const_gimple call
, int object_size_type
)
397 tree callee
, bytes
= NULL_TREE
;
399 int arg1
= -1, arg2
= -1;
401 gcc_assert (is_gimple_call (call
));
403 callee
= gimple_call_fndecl (call
);
405 return unknown
[object_size_type
];
407 alloc_size
= lookup_attribute ("alloc_size",
408 TYPE_ATTRIBUTES (TREE_TYPE (callee
)));
409 if (alloc_size
&& TREE_VALUE (alloc_size
))
411 tree p
= TREE_VALUE (alloc_size
);
413 arg1
= TREE_INT_CST_LOW (TREE_VALUE (p
))-1;
415 arg2
= TREE_INT_CST_LOW (TREE_VALUE (TREE_CHAIN (p
)))-1;
418 if (DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
419 switch (DECL_FUNCTION_CODE (callee
))
421 case BUILT_IN_CALLOC
:
424 case BUILT_IN_MALLOC
:
425 case BUILT_IN_ALLOCA
:
426 case BUILT_IN_ALLOCA_WITH_ALIGN
:
432 if (arg1
< 0 || arg1
>= (int)gimple_call_num_args (call
)
433 || TREE_CODE (gimple_call_arg (call
, arg1
)) != INTEGER_CST
435 && (arg2
>= (int)gimple_call_num_args (call
)
436 || TREE_CODE (gimple_call_arg (call
, arg2
)) != INTEGER_CST
)))
437 return unknown
[object_size_type
];
440 bytes
= size_binop (MULT_EXPR
,
441 fold_convert (sizetype
, gimple_call_arg (call
, arg1
)),
442 fold_convert (sizetype
, gimple_call_arg (call
, arg2
)));
444 bytes
= fold_convert (sizetype
, gimple_call_arg (call
, arg1
));
446 if (bytes
&& tree_fits_uhwi_p (bytes
))
447 return tree_to_uhwi (bytes
);
449 return unknown
[object_size_type
];
453 /* If object size is propagated from one of function's arguments directly
454 to its return value, return that argument for GIMPLE_CALL statement CALL.
455 Otherwise return NULL. */
458 pass_through_call (const_gimple call
)
460 tree callee
= gimple_call_fndecl (call
);
463 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
464 switch (DECL_FUNCTION_CODE (callee
))
466 case BUILT_IN_MEMCPY
:
467 case BUILT_IN_MEMMOVE
:
468 case BUILT_IN_MEMSET
:
469 case BUILT_IN_STRCPY
:
470 case BUILT_IN_STRNCPY
:
471 case BUILT_IN_STRCAT
:
472 case BUILT_IN_STRNCAT
:
473 case BUILT_IN_MEMCPY_CHK
:
474 case BUILT_IN_MEMMOVE_CHK
:
475 case BUILT_IN_MEMSET_CHK
:
476 case BUILT_IN_STRCPY_CHK
:
477 case BUILT_IN_STRNCPY_CHK
:
478 case BUILT_IN_STPNCPY_CHK
:
479 case BUILT_IN_STRCAT_CHK
:
480 case BUILT_IN_STRNCAT_CHK
:
481 case BUILT_IN_ASSUME_ALIGNED
:
482 if (gimple_call_num_args (call
) >= 1)
483 return gimple_call_arg (call
, 0);
493 /* Compute __builtin_object_size value for PTR. OBJECT_SIZE_TYPE is the
494 second argument from __builtin_object_size. */
496 unsigned HOST_WIDE_INT
497 compute_builtin_object_size (tree ptr
, int object_size_type
)
499 gcc_assert (object_size_type
>= 0 && object_size_type
<= 3);
502 init_offset_limit ();
504 if (TREE_CODE (ptr
) == ADDR_EXPR
)
505 return addr_object_size (NULL
, ptr
, object_size_type
);
507 if (TREE_CODE (ptr
) == SSA_NAME
508 && POINTER_TYPE_P (TREE_TYPE (ptr
))
509 && object_sizes
[object_size_type
] != NULL
)
511 if (!bitmap_bit_p (computed
[object_size_type
], SSA_NAME_VERSION (ptr
)))
513 struct object_size_info osi
;
519 fprintf (dump_file
, "Computing %s %sobject size for ",
520 (object_size_type
& 2) ? "minimum" : "maximum",
521 (object_size_type
& 1) ? "sub" : "");
522 print_generic_expr (dump_file
, ptr
, dump_flags
);
523 fprintf (dump_file
, ":\n");
526 osi
.visited
= BITMAP_ALLOC (NULL
);
527 osi
.reexamine
= BITMAP_ALLOC (NULL
);
528 osi
.object_size_type
= object_size_type
;
533 /* First pass: walk UD chains, compute object sizes that
534 can be computed. osi.reexamine bitmap at the end will
535 contain what variables were found in dependency cycles
536 and therefore need to be reexamined. */
539 collect_object_sizes_for (&osi
, ptr
);
541 /* Second pass: keep recomputing object sizes of variables
542 that need reexamination, until no object sizes are
543 increased or all object sizes are computed. */
544 if (! bitmap_empty_p (osi
.reexamine
))
546 bitmap reexamine
= BITMAP_ALLOC (NULL
);
548 /* If looking for minimum instead of maximum object size,
549 detect cases where a pointer is increased in a loop.
550 Although even without this detection pass 2 would eventually
551 terminate, it could take a long time. If a pointer is
552 increasing this way, we need to assume 0 object size.
553 E.g. p = &buf[0]; while (cond) p = p + 4; */
554 if (object_size_type
& 2)
556 osi
.depths
= XCNEWVEC (unsigned int, num_ssa_names
);
557 osi
.stack
= XNEWVEC (unsigned int, num_ssa_names
);
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
))
565 check_for_plus_in_loops (&osi
, ssa_name (i
));
578 /* collect_object_sizes_for is changing
579 osi.reexamine bitmap, so iterate over a copy. */
580 bitmap_copy (reexamine
, osi
.reexamine
);
581 EXECUTE_IF_SET_IN_BITMAP (reexamine
, 0, i
, bi
)
582 if (bitmap_bit_p (osi
.reexamine
, i
))
584 collect_object_sizes_for (&osi
, ssa_name (i
));
585 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
587 fprintf (dump_file
, "Reexamining ");
588 print_generic_expr (dump_file
, ssa_name (i
),
590 fprintf (dump_file
, "\n");
596 BITMAP_FREE (reexamine
);
598 EXECUTE_IF_SET_IN_BITMAP (osi
.reexamine
, 0, i
, bi
)
599 bitmap_set_bit (computed
[object_size_type
], i
);
601 /* Debugging dumps. */
604 EXECUTE_IF_SET_IN_BITMAP (osi
.visited
, 0, i
, bi
)
605 if (object_sizes
[object_size_type
][i
]
606 != unknown
[object_size_type
])
608 print_generic_expr (dump_file
, ssa_name (i
),
611 ": %s %sobject size "
612 HOST_WIDE_INT_PRINT_UNSIGNED
"\n",
613 (object_size_type
& 2) ? "minimum" : "maximum",
614 (object_size_type
& 1) ? "sub" : "",
615 object_sizes
[object_size_type
][i
]);
619 BITMAP_FREE (osi
.reexamine
);
620 BITMAP_FREE (osi
.visited
);
623 return object_sizes
[object_size_type
][SSA_NAME_VERSION (ptr
)];
626 return unknown
[object_size_type
];
629 /* Compute object_sizes for PTR, defined to VALUE, which is not an SSA_NAME. */
632 expr_object_size (struct object_size_info
*osi
, tree ptr
, tree value
)
634 int object_size_type
= osi
->object_size_type
;
635 unsigned int varno
= SSA_NAME_VERSION (ptr
);
636 unsigned HOST_WIDE_INT bytes
;
638 gcc_assert (object_sizes
[object_size_type
][varno
]
639 != unknown
[object_size_type
]);
640 gcc_assert (osi
->pass
== 0);
642 if (TREE_CODE (value
) == WITH_SIZE_EXPR
)
643 value
= TREE_OPERAND (value
, 0);
645 /* Pointer variables should have been handled by merge_object_sizes. */
646 gcc_assert (TREE_CODE (value
) != SSA_NAME
647 || !POINTER_TYPE_P (TREE_TYPE (value
)));
649 if (TREE_CODE (value
) == ADDR_EXPR
)
650 bytes
= addr_object_size (osi
, value
, object_size_type
);
652 bytes
= unknown
[object_size_type
];
654 if ((object_size_type
& 2) == 0)
656 if (object_sizes
[object_size_type
][varno
] < bytes
)
657 object_sizes
[object_size_type
][varno
] = bytes
;
661 if (object_sizes
[object_size_type
][varno
] > bytes
)
662 object_sizes
[object_size_type
][varno
] = bytes
;
667 /* Compute object_sizes for PTR, defined to the result of a call. */
670 call_object_size (struct object_size_info
*osi
, tree ptr
, gimple call
)
672 int object_size_type
= osi
->object_size_type
;
673 unsigned int varno
= SSA_NAME_VERSION (ptr
);
674 unsigned HOST_WIDE_INT bytes
;
676 gcc_assert (is_gimple_call (call
));
678 gcc_assert (object_sizes
[object_size_type
][varno
]
679 != unknown
[object_size_type
]);
680 gcc_assert (osi
->pass
== 0);
682 bytes
= alloc_object_size (call
, object_size_type
);
684 if ((object_size_type
& 2) == 0)
686 if (object_sizes
[object_size_type
][varno
] < bytes
)
687 object_sizes
[object_size_type
][varno
] = bytes
;
691 if (object_sizes
[object_size_type
][varno
] > bytes
)
692 object_sizes
[object_size_type
][varno
] = bytes
;
697 /* Compute object_sizes for PTR, defined to an unknown value. */
700 unknown_object_size (struct object_size_info
*osi
, tree ptr
)
702 int object_size_type
= osi
->object_size_type
;
703 unsigned int varno
= SSA_NAME_VERSION (ptr
);
704 unsigned HOST_WIDE_INT bytes
;
706 gcc_assert (object_sizes
[object_size_type
][varno
]
707 != unknown
[object_size_type
]);
708 gcc_assert (osi
->pass
== 0);
710 bytes
= unknown
[object_size_type
];
712 if ((object_size_type
& 2) == 0)
714 if (object_sizes
[object_size_type
][varno
] < bytes
)
715 object_sizes
[object_size_type
][varno
] = bytes
;
719 if (object_sizes
[object_size_type
][varno
] > bytes
)
720 object_sizes
[object_size_type
][varno
] = bytes
;
725 /* Merge object sizes of ORIG + OFFSET into DEST. Return true if
726 the object size might need reexamination later. */
729 merge_object_sizes (struct object_size_info
*osi
, tree dest
, tree orig
,
730 unsigned HOST_WIDE_INT offset
)
732 int object_size_type
= osi
->object_size_type
;
733 unsigned int varno
= SSA_NAME_VERSION (dest
);
734 unsigned HOST_WIDE_INT orig_bytes
;
736 if (object_sizes
[object_size_type
][varno
] == unknown
[object_size_type
])
738 if (offset
>= offset_limit
)
740 object_sizes
[object_size_type
][varno
] = unknown
[object_size_type
];
745 collect_object_sizes_for (osi
, orig
);
747 orig_bytes
= object_sizes
[object_size_type
][SSA_NAME_VERSION (orig
)];
748 if (orig_bytes
!= unknown
[object_size_type
])
749 orig_bytes
= (offset
> orig_bytes
)
750 ? (unsigned HOST_WIDE_INT
) 0 : orig_bytes
- offset
;
752 if ((object_size_type
& 2) == 0)
754 if (object_sizes
[object_size_type
][varno
] < orig_bytes
)
756 object_sizes
[object_size_type
][varno
] = orig_bytes
;
762 if (object_sizes
[object_size_type
][varno
] > orig_bytes
)
764 object_sizes
[object_size_type
][varno
] = orig_bytes
;
768 return bitmap_bit_p (osi
->reexamine
, SSA_NAME_VERSION (orig
));
772 /* Compute object_sizes for VAR, defined to the result of an assignment
773 with operator POINTER_PLUS_EXPR. Return true if the object size might
774 need reexamination later. */
777 plus_stmt_object_size (struct object_size_info
*osi
, tree var
, gimple stmt
)
779 int object_size_type
= osi
->object_size_type
;
780 unsigned int varno
= SSA_NAME_VERSION (var
);
781 unsigned HOST_WIDE_INT bytes
;
784 if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
786 op0
= gimple_assign_rhs1 (stmt
);
787 op1
= gimple_assign_rhs2 (stmt
);
789 else if (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
791 tree rhs
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
792 gcc_assert (TREE_CODE (rhs
) == MEM_REF
);
793 op0
= TREE_OPERAND (rhs
, 0);
794 op1
= TREE_OPERAND (rhs
, 1);
799 if (object_sizes
[object_size_type
][varno
] == unknown
[object_size_type
])
802 /* Handle PTR + OFFSET here. */
803 if (TREE_CODE (op1
) == INTEGER_CST
804 && (TREE_CODE (op0
) == SSA_NAME
805 || TREE_CODE (op0
) == ADDR_EXPR
))
807 if (! tree_fits_uhwi_p (op1
))
808 bytes
= unknown
[object_size_type
];
809 else if (TREE_CODE (op0
) == SSA_NAME
)
810 return merge_object_sizes (osi
, var
, op0
, tree_to_uhwi (op1
));
813 unsigned HOST_WIDE_INT off
= tree_to_uhwi (op1
);
815 /* op0 will be ADDR_EXPR here. */
816 bytes
= addr_object_size (osi
, op0
, object_size_type
);
817 if (bytes
== unknown
[object_size_type
])
819 else if (off
> offset_limit
)
820 bytes
= unknown
[object_size_type
];
821 else if (off
> bytes
)
828 bytes
= unknown
[object_size_type
];
830 if ((object_size_type
& 2) == 0)
832 if (object_sizes
[object_size_type
][varno
] < bytes
)
833 object_sizes
[object_size_type
][varno
] = bytes
;
837 if (object_sizes
[object_size_type
][varno
] > bytes
)
838 object_sizes
[object_size_type
][varno
] = bytes
;
844 /* Compute object_sizes for VAR, defined at STMT, which is
845 a COND_EXPR. Return true if the object size might need reexamination
849 cond_expr_object_size (struct object_size_info
*osi
, tree var
, gimple stmt
)
852 int object_size_type
= osi
->object_size_type
;
853 unsigned int varno
= SSA_NAME_VERSION (var
);
854 bool reexamine
= false;
856 gcc_assert (gimple_assign_rhs_code (stmt
) == COND_EXPR
);
858 if (object_sizes
[object_size_type
][varno
] == unknown
[object_size_type
])
861 then_
= gimple_assign_rhs2 (stmt
);
862 else_
= gimple_assign_rhs3 (stmt
);
864 if (TREE_CODE (then_
) == SSA_NAME
)
865 reexamine
|= merge_object_sizes (osi
, var
, then_
, 0);
867 expr_object_size (osi
, var
, then_
);
869 if (TREE_CODE (else_
) == SSA_NAME
)
870 reexamine
|= merge_object_sizes (osi
, var
, else_
, 0);
872 expr_object_size (osi
, var
, else_
);
877 /* Compute object sizes for VAR.
878 For ADDR_EXPR an object size is the number of remaining bytes
879 to the end of the object (where what is considered an object depends on
880 OSI->object_size_type).
881 For allocation GIMPLE_CALL like malloc or calloc object size is the size
883 For POINTER_PLUS_EXPR where second operand is a constant integer,
884 object size is object size of the first operand minus the constant.
885 If the constant is bigger than the number of remaining bytes until the
886 end of the object, object size is 0, but if it is instead a pointer
887 subtraction, object size is unknown[object_size_type].
888 To differentiate addition from subtraction, ADDR_EXPR returns
889 unknown[object_size_type] for all objects bigger than half of the address
890 space, and constants less than half of the address space are considered
891 addition, while bigger constants subtraction.
892 For a memcpy like GIMPLE_CALL that always returns one of its arguments, the
893 object size is object size of that argument.
894 Otherwise, object size is the maximum of object sizes of variables
895 that it might be set to. */
898 collect_object_sizes_for (struct object_size_info
*osi
, tree var
)
900 int object_size_type
= osi
->object_size_type
;
901 unsigned int varno
= SSA_NAME_VERSION (var
);
905 if (bitmap_bit_p (computed
[object_size_type
], varno
))
910 if (bitmap_set_bit (osi
->visited
, varno
))
912 object_sizes
[object_size_type
][varno
]
913 = (object_size_type
& 2) ? -1 : 0;
917 /* Found a dependency loop. Mark the variable for later
919 bitmap_set_bit (osi
->reexamine
, varno
);
920 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
922 fprintf (dump_file
, "Found a dependency loop at ");
923 print_generic_expr (dump_file
, var
, dump_flags
);
924 fprintf (dump_file
, "\n");
930 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
932 fprintf (dump_file
, "Visiting use-def links for ");
933 print_generic_expr (dump_file
, var
, dump_flags
);
934 fprintf (dump_file
, "\n");
937 stmt
= SSA_NAME_DEF_STMT (var
);
940 switch (gimple_code (stmt
))
944 tree rhs
= gimple_assign_rhs1 (stmt
);
945 if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
946 || (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
947 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == MEM_REF
))
948 reexamine
= plus_stmt_object_size (osi
, var
, stmt
);
949 else if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
950 reexamine
= cond_expr_object_size (osi
, var
, stmt
);
951 else if (gimple_assign_single_p (stmt
)
952 || gimple_assign_unary_nop_p (stmt
))
954 if (TREE_CODE (rhs
) == SSA_NAME
955 && POINTER_TYPE_P (TREE_TYPE (rhs
)))
956 reexamine
= merge_object_sizes (osi
, var
, rhs
, 0);
958 expr_object_size (osi
, var
, rhs
);
961 unknown_object_size (osi
, var
);
967 tree arg
= pass_through_call (stmt
);
970 if (TREE_CODE (arg
) == SSA_NAME
971 && POINTER_TYPE_P (TREE_TYPE (arg
)))
972 reexamine
= merge_object_sizes (osi
, var
, arg
, 0);
974 expr_object_size (osi
, var
, arg
);
977 call_object_size (osi
, var
, stmt
);
982 /* Pointers defined by __asm__ statements can point anywhere. */
983 object_sizes
[object_size_type
][varno
] = unknown
[object_size_type
];
987 if (SSA_NAME_VAR (var
)
988 && TREE_CODE (SSA_NAME_VAR (var
)) == PARM_DECL
)
989 expr_object_size (osi
, var
, SSA_NAME_VAR (var
));
991 /* Uninitialized SSA names point nowhere. */
992 object_sizes
[object_size_type
][varno
] = unknown
[object_size_type
];
999 for (i
= 0; i
< gimple_phi_num_args (stmt
); i
++)
1001 tree rhs
= gimple_phi_arg (stmt
, i
)->def
;
1003 if (object_sizes
[object_size_type
][varno
]
1004 == unknown
[object_size_type
])
1007 if (TREE_CODE (rhs
) == SSA_NAME
)
1008 reexamine
|= merge_object_sizes (osi
, var
, rhs
, 0);
1009 else if (osi
->pass
== 0)
1010 expr_object_size (osi
, var
, rhs
);
1020 || object_sizes
[object_size_type
][varno
] == unknown
[object_size_type
])
1022 bitmap_set_bit (computed
[object_size_type
], varno
);
1023 bitmap_clear_bit (osi
->reexamine
, varno
);
1027 bitmap_set_bit (osi
->reexamine
, varno
);
1028 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1030 fprintf (dump_file
, "Need to reexamine ");
1031 print_generic_expr (dump_file
, var
, dump_flags
);
1032 fprintf (dump_file
, "\n");
1038 /* Helper function for check_for_plus_in_loops. Called recursively
1042 check_for_plus_in_loops_1 (struct object_size_info
*osi
, tree var
,
1045 gimple stmt
= SSA_NAME_DEF_STMT (var
);
1046 unsigned int varno
= SSA_NAME_VERSION (var
);
1048 if (osi
->depths
[varno
])
1050 if (osi
->depths
[varno
] != depth
)
1054 /* Found a loop involving pointer addition. */
1055 for (sp
= osi
->tos
; sp
> osi
->stack
; )
1058 bitmap_clear_bit (osi
->reexamine
, *sp
);
1059 bitmap_set_bit (computed
[osi
->object_size_type
], *sp
);
1060 object_sizes
[osi
->object_size_type
][*sp
] = 0;
1067 else if (! bitmap_bit_p (osi
->reexamine
, varno
))
1070 osi
->depths
[varno
] = depth
;
1071 *osi
->tos
++ = varno
;
1073 switch (gimple_code (stmt
))
1078 if ((gimple_assign_single_p (stmt
)
1079 || gimple_assign_unary_nop_p (stmt
))
1080 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
1082 tree rhs
= gimple_assign_rhs1 (stmt
);
1084 check_for_plus_in_loops_1 (osi
, rhs
, depth
);
1086 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
1088 tree basevar
= gimple_assign_rhs1 (stmt
);
1089 tree cst
= gimple_assign_rhs2 (stmt
);
1091 gcc_assert (TREE_CODE (cst
) == INTEGER_CST
);
1093 check_for_plus_in_loops_1 (osi
, basevar
,
1094 depth
+ !integer_zerop (cst
));
1103 tree arg
= pass_through_call (stmt
);
1106 if (TREE_CODE (arg
) == SSA_NAME
)
1107 check_for_plus_in_loops_1 (osi
, arg
, depth
);
1118 for (i
= 0; i
< gimple_phi_num_args (stmt
); i
++)
1120 tree rhs
= gimple_phi_arg (stmt
, i
)->def
;
1122 if (TREE_CODE (rhs
) == SSA_NAME
)
1123 check_for_plus_in_loops_1 (osi
, rhs
, depth
);
1132 osi
->depths
[varno
] = 0;
1137 /* Check if some pointer we are computing object size of is being increased
1138 within a loop. If yes, assume all the SSA variables participating in
1139 that loop have minimum object sizes 0. */
1142 check_for_plus_in_loops (struct object_size_info
*osi
, tree var
)
1144 gimple stmt
= SSA_NAME_DEF_STMT (var
);
1146 /* NOTE: In the pre-tuples code, we handled a CALL_EXPR here,
1147 and looked for a POINTER_PLUS_EXPR in the pass-through
1148 argument, if any. In GIMPLE, however, such an expression
1149 is not a valid call operand. */
1151 if (is_gimple_assign (stmt
)
1152 && gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
1154 tree basevar
= gimple_assign_rhs1 (stmt
);
1155 tree cst
= gimple_assign_rhs2 (stmt
);
1157 gcc_assert (TREE_CODE (cst
) == INTEGER_CST
);
1159 if (integer_zerop (cst
))
1162 osi
->depths
[SSA_NAME_VERSION (basevar
)] = 1;
1163 *osi
->tos
++ = SSA_NAME_VERSION (basevar
);
1164 check_for_plus_in_loops_1 (osi
, var
, 2);
1165 osi
->depths
[SSA_NAME_VERSION (basevar
)] = 0;
1171 /* Initialize data structures for the object size computation. */
1174 init_object_sizes (void)
1176 int object_size_type
;
1178 if (object_sizes
[0])
1181 for (object_size_type
= 0; object_size_type
<= 3; object_size_type
++)
1183 object_sizes
[object_size_type
] = XNEWVEC (unsigned HOST_WIDE_INT
, num_ssa_names
);
1184 computed
[object_size_type
] = BITMAP_ALLOC (NULL
);
1187 init_offset_limit ();
1191 /* Destroy data structures after the object size computation. */
1194 fini_object_sizes (void)
1196 int object_size_type
;
1198 for (object_size_type
= 0; object_size_type
<= 3; object_size_type
++)
1200 free (object_sizes
[object_size_type
]);
1201 BITMAP_FREE (computed
[object_size_type
]);
1202 object_sizes
[object_size_type
] = NULL
;
1207 /* Simple pass to optimize all __builtin_object_size () builtins. */
1210 compute_object_sizes (void)
1215 gimple_stmt_iterator i
;
1216 for (i
= gsi_start_bb (bb
); !gsi_end_p (i
); gsi_next (&i
))
1219 gimple call
= gsi_stmt (i
);
1220 if (!gimple_call_builtin_p (call
, BUILT_IN_OBJECT_SIZE
))
1223 init_object_sizes ();
1224 result
= fold_call_stmt (call
, false);
1227 if (gimple_call_num_args (call
) == 2
1228 && POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call
, 0))))
1230 tree ost
= gimple_call_arg (call
, 1);
1232 if (tree_fits_uhwi_p (ost
))
1234 unsigned HOST_WIDE_INT object_size_type
1235 = tree_to_uhwi (ost
);
1237 if (object_size_type
< 2)
1238 result
= fold_convert (size_type_node
,
1239 integer_minus_one_node
);
1240 else if (object_size_type
< 4)
1241 result
= build_zero_cst (size_type_node
);
1249 gcc_assert (TREE_CODE (result
) == INTEGER_CST
);
1251 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1253 fprintf (dump_file
, "Simplified\n ");
1254 print_gimple_stmt (dump_file
, call
, 0, dump_flags
);
1255 fprintf (dump_file
, " to ");
1256 print_generic_expr (dump_file
, result
, 0);
1257 fprintf (dump_file
, "\n");
1260 tree lhs
= gimple_call_lhs (call
);
1264 /* Propagate into all uses and fold those stmts. */
1266 imm_use_iterator iter
;
1267 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, lhs
)
1269 use_operand_p use_p
;
1270 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
1271 SET_USE (use_p
, result
);
1272 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
1274 update_stmt (gsi_stmt (gsi
));
1279 fini_object_sizes ();
1285 const pass_data pass_data_object_sizes
=
1287 GIMPLE_PASS
, /* type */
1289 OPTGROUP_NONE
, /* optinfo_flags */
1290 false, /* has_gate */
1291 true, /* has_execute */
1292 TV_NONE
, /* tv_id */
1293 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1294 0, /* properties_provided */
1295 0, /* properties_destroyed */
1296 0, /* todo_flags_start */
1297 TODO_verify_ssa
, /* todo_flags_finish */
1300 class pass_object_sizes
: public gimple_opt_pass
1303 pass_object_sizes (gcc::context
*ctxt
)
1304 : gimple_opt_pass (pass_data_object_sizes
, ctxt
)
1307 /* opt_pass methods: */
1308 opt_pass
* clone () { return new pass_object_sizes (m_ctxt
); }
1309 unsigned int execute () { return compute_object_sizes (); }
1311 }; // class pass_object_sizes
1316 make_pass_object_sizes (gcc::context
*ctxt
)
1318 return new pass_object_sizes (ctxt
);