1 /* Type based alias analysis.
2 Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
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/>. */
21 /* This pass determines which types in the program contain only
22 instances that are completely encapsulated by the compilation unit.
23 Those types that are encapsulated must also pass the further
24 requirement that there be no bad operations on any instances of
27 A great deal of freedom in compilation is allowed for the instances
28 of those types that pass these conditions.
31 /* The code in this module is called by the ipa pass manager. It
32 should be one of the later passes since its information is used by
33 the rest of the compilation. */
37 #include "coretypes.h"
40 #include "tree-flow.h"
41 #include "tree-inline.h"
42 #include "tree-pass.h"
43 #include "langhooks.h"
44 #include "pointer-set.h"
46 #include "ipa-utils.h"
47 #include "ipa-type-escape.h"
49 #include "tree-gimple.h"
54 #include "diagnostic.h"
55 #include "langhooks.h"
57 /* Some of the aliasing is called very early, before this phase is
58 called. To assure that this is not a problem, we keep track of if
59 this phase has been run. */
60 static bool initialized
= false;
62 /* This bitmap contains the set of local vars that are the lhs of
63 calls to mallocs. These variables, when seen on the rhs as part of
64 a cast, the cast are not marked as doing bad things to the type
65 even though they are generally of the form
66 "foo = (type_of_foo)void_temp". */
67 static bitmap results_of_malloc
;
69 /* Scratch bitmap for avoiding work. */
70 static bitmap been_there_done_that
;
71 static bitmap bitmap_tmp
;
73 /* There are two levels of escape that types can undergo.
75 EXPOSED_PARAMETER - some instance of the variable is
76 passed by value into an externally visible function or some
77 instance of the variable is passed out of an externally visible
78 function as a return value. In this case any of the fields of the
79 variable that are pointer types end up having their types marked as
82 FULL_ESCAPE - when bad things happen to good types. One of the
83 following things happens to the type: (a) either an instance of the
84 variable has its address passed to an externally visible function,
85 (b) the address is taken and some bad cast happens to the address
86 or (c) explicit arithmetic is done to the address.
95 /* The following two bit vectors global_types_* correspond to
96 previous cases above. During the analysis phase, a bit is set in
97 one of these vectors if an operation of the offending class is
98 discovered to happen on the associated type. */
100 static bitmap global_types_exposed_parameter
;
101 static bitmap global_types_full_escape
;
103 /* All of the types seen in this compilation unit. */
104 static bitmap global_types_seen
;
105 /* Reverse map to take a canon uid and map it to a canon type. Uid's
106 are never manipulated unless they are associated with a canon
108 static splay_tree uid_to_canon_type
;
110 /* Internal structure of type mapping code. This maps a canon type
111 name to its canon type. */
112 static splay_tree all_canon_types
;
114 /* Map from type clones to the single canon type. */
115 static splay_tree type_to_canon_type
;
117 /* A splay tree of bitmaps. An element X in the splay tree has a bit
118 set in its bitmap at TYPE_UID (TYPE_MAIN_VARIANT (Y)) if there was
119 an operation in the program of the form "&X.Y". */
120 static splay_tree uid_to_addressof_down_map
;
122 /* A splay tree of bitmaps. An element Y in the splay tree has a bit
123 set in its bitmap at TYPE_UID (TYPE_MAIN_VARIANT (X)) if there was
124 an operation in the program of the form "&X.Y". */
125 static splay_tree uid_to_addressof_up_map
;
127 /* Tree to hold the subtype maps used to mark subtypes of escaped
129 static splay_tree uid_to_subtype_map
;
131 /* Records tree nodes seen in cgraph_create_edges. Simply using
132 walk_tree_without_duplicates doesn't guarantee each node is visited
133 once because it gets a new htab upon each recursive call from
135 static struct pointer_set_t
*visited_nodes
;
137 static bitmap_obstack ipa_obstack
;
139 /* Get the name of TYPE or return the string "<UNNAMED>". */
141 get_name_of_type (tree type
)
143 tree name
= TYPE_NAME (type
);
146 /* Unnamed type, do what you like here. */
147 return (char*)"<UNNAMED>";
149 /* It will be a TYPE_DECL in the case of a typedef, otherwise, an
151 if (TREE_CODE (name
) == TYPE_DECL
)
153 /* Each DECL has a DECL_NAME field which contains an
154 IDENTIFIER_NODE. (Some decls, most often labels, may have
155 zero as the DECL_NAME). */
156 if (DECL_NAME (name
))
157 return (char*)IDENTIFIER_POINTER (DECL_NAME (name
));
159 /* Unnamed type, do what you like here. */
160 return (char*)"<UNNAMED>";
162 else if (TREE_CODE (name
) == IDENTIFIER_NODE
)
163 return (char*)IDENTIFIER_POINTER (name
);
165 return (char*)"<UNNAMED>";
174 /* Splay tree comparison function on type_brand_s structures. */
177 compare_type_brand (splay_tree_key sk1
, splay_tree_key sk2
)
179 struct type_brand_s
* k1
= (struct type_brand_s
*) sk1
;
180 struct type_brand_s
* k2
= (struct type_brand_s
*) sk2
;
182 int value
= strcmp(k1
->name
, k2
->name
);
184 return k2
->seq
- k1
->seq
;
189 /* All of the "unique_type" code is a hack to get around the sleazy
190 implementation used to compile more than file. Currently gcc does
191 not get rid of multiple instances of the same type that have been
192 collected from different compilation units. */
193 /* This is a trivial algorithm for removing duplicate types. This
194 would not work for any language that used structural equivalence as
195 the basis of its type system. */
196 /* Return either TYPE if this is first time TYPE has been seen an
197 compatible TYPE that has already been processed. */
200 discover_unique_type (tree type
)
202 struct type_brand_s
* brand
= XNEW (struct type_brand_s
);
204 splay_tree_node result
;
206 brand
->name
= get_name_of_type (type
);
211 result
= splay_tree_lookup (all_canon_types
, (splay_tree_key
) brand
);
215 /* Create an alias since this is just the same as
217 tree other_type
= (tree
) result
->value
;
218 if (lang_hooks
.types_compatible_p (type
, other_type
) == 1)
221 /* Insert this new type as an alias for other_type. */
222 splay_tree_insert (type_to_canon_type
,
223 (splay_tree_key
) type
,
224 (splay_tree_value
) other_type
);
227 /* Not compatible, look for next instance with same name. */
231 /* No more instances, create new one since this is the first
232 time we saw this type. */
234 /* Insert the new brand. */
235 splay_tree_insert (all_canon_types
,
236 (splay_tree_key
) brand
,
237 (splay_tree_value
) type
);
239 /* Insert this new type as an alias for itself. */
240 splay_tree_insert (type_to_canon_type
,
241 (splay_tree_key
) type
,
242 (splay_tree_value
) type
);
244 /* Insert the uid for reverse lookup; */
245 splay_tree_insert (uid_to_canon_type
,
246 (splay_tree_key
) TYPE_UID (type
),
247 (splay_tree_value
) type
);
249 bitmap_set_bit (global_types_seen
, TYPE_UID (type
));
255 /* Return true if TYPE is one of the type classes that we are willing
256 to analyze. This skips the goofy types like arrays of pointers to
259 type_to_consider (tree type
)
261 /* Strip the *'s off. */
262 type
= TYPE_MAIN_VARIANT (type
);
263 while (POINTER_TYPE_P (type
) || TREE_CODE (type
) == ARRAY_TYPE
)
264 type
= TYPE_MAIN_VARIANT (TREE_TYPE (type
));
266 switch (TREE_CODE (type
))
272 case QUAL_UNION_TYPE
:
285 /* Get the canon type of TYPE. If SEE_THRU_PTRS is true, remove all
286 the POINTER_TOs and if SEE_THRU_ARRAYS is true, remove all of the
287 ARRAY_OFs and POINTER_TOs. */
290 get_canon_type (tree type
, bool see_thru_ptrs
, bool see_thru_arrays
)
292 splay_tree_node result
;
293 /* Strip the *'s off. */
294 if (!type
|| !type_to_consider (type
))
297 type
= TYPE_MAIN_VARIANT (type
);
299 while (POINTER_TYPE_P (type
) || TREE_CODE (type
) == ARRAY_TYPE
)
300 type
= TYPE_MAIN_VARIANT (TREE_TYPE (type
));
302 else if (see_thru_ptrs
)
303 while (POINTER_TYPE_P (type
))
304 type
= TYPE_MAIN_VARIANT (TREE_TYPE (type
));
306 result
= splay_tree_lookup(type_to_canon_type
, (splay_tree_key
) type
);
309 return discover_unique_type (type
);
310 else return (tree
) result
->value
;
313 /* Same as GET_CANON_TYPE, except return the TYPE_ID rather than the
317 get_canon_type_uid (tree type
, bool see_thru_ptrs
, bool see_thru_arrays
)
319 type
= get_canon_type (type
, see_thru_ptrs
, see_thru_arrays
);
321 return TYPE_UID(type
);
325 /* Return 0 if TYPE is a record or union type. Return a positive
326 number if TYPE is a pointer to a record or union. The number is
327 the number of pointer types stripped to get to the record or union
328 type. Return -1 if TYPE is none of the above. */
331 ipa_type_escape_star_count_of_interesting_type (tree type
)
334 /* Strip the *'s off. */
337 type
= TYPE_MAIN_VARIANT (type
);
338 while (POINTER_TYPE_P (type
))
340 type
= TYPE_MAIN_VARIANT (TREE_TYPE (type
));
344 /* We are interested in records, and unions only. */
345 if (TREE_CODE (type
) == RECORD_TYPE
346 || TREE_CODE (type
) == QUAL_UNION_TYPE
347 || TREE_CODE (type
) == UNION_TYPE
)
354 /* Return 0 if TYPE is a record or union type. Return a positive
355 number if TYPE is a pointer to a record or union. The number is
356 the number of pointer types stripped to get to the record or union
357 type. Return -1 if TYPE is none of the above. */
360 ipa_type_escape_star_count_of_interesting_or_array_type (tree type
)
363 /* Strip the *'s off. */
366 type
= TYPE_MAIN_VARIANT (type
);
367 while (POINTER_TYPE_P (type
) || TREE_CODE (type
) == ARRAY_TYPE
)
369 type
= TYPE_MAIN_VARIANT (TREE_TYPE (type
));
373 /* We are interested in records, and unions only. */
374 if (TREE_CODE (type
) == RECORD_TYPE
375 || TREE_CODE (type
) == QUAL_UNION_TYPE
376 || TREE_CODE (type
) == UNION_TYPE
)
383 /* Return true if the record, or union TYPE passed in escapes this
384 compilation unit. Note that all of the pointer-to's are removed
385 before testing since these may not be correct. */
388 ipa_type_escape_type_contained_p (tree type
)
392 return !bitmap_bit_p (global_types_full_escape
,
393 get_canon_type_uid (type
, true, false));
396 /* Return true if a modification to a field of type FIELD_TYPE cannot
397 clobber a record of RECORD_TYPE. */
400 ipa_type_escape_field_does_not_clobber_p (tree record_type
, tree field_type
)
402 splay_tree_node result
;
408 /* Strip off all of the pointer tos on the record type. Strip the
409 same number of pointer tos from the field type. If the field
410 type has fewer, it could not have been aliased. */
411 record_type
= TYPE_MAIN_VARIANT (record_type
);
412 field_type
= TYPE_MAIN_VARIANT (field_type
);
413 while (POINTER_TYPE_P (record_type
))
415 record_type
= TYPE_MAIN_VARIANT (TREE_TYPE (record_type
));
416 if (POINTER_TYPE_P (field_type
))
417 field_type
= TYPE_MAIN_VARIANT (TREE_TYPE (field_type
));
419 /* However, if field_type is a union, this quick test is not
420 correct since one of the variants of the union may be a
421 pointer to type and we cannot see across that here. So we
422 just strip the remaining pointer tos off the record type
423 and fall thru to the more precise code. */
424 if (TREE_CODE (field_type
) == QUAL_UNION_TYPE
425 || TREE_CODE (field_type
) == UNION_TYPE
)
427 while (POINTER_TYPE_P (record_type
))
428 record_type
= TYPE_MAIN_VARIANT (TREE_TYPE (record_type
));
435 record_type
= get_canon_type (record_type
, true, true);
436 /* The record type must be contained. The field type may
438 if (!ipa_type_escape_type_contained_p (record_type
))
441 uid
= TYPE_UID (record_type
);
442 result
= splay_tree_lookup (uid_to_addressof_down_map
, (splay_tree_key
) uid
);
446 bitmap field_type_map
= (bitmap
) result
->value
;
447 uid
= get_canon_type_uid (field_type
, true, true);
448 /* If the bit is there, the address was taken. If not, it
450 return !bitmap_bit_p (field_type_map
, uid
);
453 /* No bitmap means no addresses were taken. */
458 /* Add TYPE to the suspect type set. Return true if the bit needed to
462 mark_type (tree type
, enum escape_t escape_status
)
467 type
= get_canon_type (type
, true, true);
471 switch (escape_status
)
473 case EXPOSED_PARAMETER
:
474 map
= global_types_exposed_parameter
;
477 map
= global_types_full_escape
;
481 uid
= TYPE_UID (type
);
482 if (bitmap_bit_p (map
, uid
))
486 bitmap_set_bit (map
, uid
);
487 if (escape_status
== FULL_ESCAPE
)
489 /* Efficiency hack. When things are bad, do not mess around
490 with this type anymore. */
491 bitmap_set_bit (global_types_exposed_parameter
, uid
);
497 /* Add interesting TYPE to the suspect type set. If the set is
498 EXPOSED_PARAMETER and the TYPE is a pointer type, the set is
499 changed to FULL_ESCAPE. */
502 mark_interesting_type (tree type
, enum escape_t escape_status
)
505 if (ipa_type_escape_star_count_of_interesting_type (type
) >= 0)
507 if ((escape_status
== EXPOSED_PARAMETER
)
508 && POINTER_TYPE_P (type
))
509 /* EXPOSED_PARAMETERs are only structs or unions are passed by
510 value. Anything passed by reference to an external
511 function fully exposes the type. */
512 mark_type (type
, FULL_ESCAPE
);
514 mark_type (type
, escape_status
);
518 /* Return true if PARENT is supertype of CHILD. Both types must be
519 known to be structures or unions. */
522 parent_type_p (tree parent
, tree child
)
525 tree binfo
, base_binfo
;
526 if (TYPE_BINFO (parent
))
527 for (binfo
= TYPE_BINFO (parent
), i
= 0;
528 BINFO_BASE_ITERATE (binfo
, i
, base_binfo
); i
++)
530 tree binfotype
= BINFO_TYPE (base_binfo
);
531 if (binfotype
== child
)
533 else if (parent_type_p (binfotype
, child
))
536 if (TREE_CODE (parent
) == UNION_TYPE
537 || TREE_CODE (parent
) == QUAL_UNION_TYPE
)
540 /* Search all of the variants in the union to see if one of them
542 for (field
= TYPE_FIELDS (parent
);
544 field
= TREE_CHAIN (field
))
547 if (TREE_CODE (field
) != FIELD_DECL
)
550 field_type
= TREE_TYPE (field
);
551 if (field_type
== child
)
555 /* If we did not find it, recursively ask the variants if one of
556 their children is the child type. */
557 for (field
= TYPE_FIELDS (parent
);
559 field
= TREE_CHAIN (field
))
562 if (TREE_CODE (field
) != FIELD_DECL
)
565 field_type
= TREE_TYPE (field
);
566 if (TREE_CODE (field_type
) == RECORD_TYPE
567 || TREE_CODE (field_type
) == QUAL_UNION_TYPE
568 || TREE_CODE (field_type
) == UNION_TYPE
)
569 if (parent_type_p (field_type
, child
))
574 if (TREE_CODE (parent
) == RECORD_TYPE
)
577 for (field
= TYPE_FIELDS (parent
);
579 field
= TREE_CHAIN (field
))
582 if (TREE_CODE (field
) != FIELD_DECL
)
585 field_type
= TREE_TYPE (field
);
586 if (field_type
== child
)
588 /* You can only cast to the first field so if it does not
590 if (TREE_CODE (field_type
) == RECORD_TYPE
591 || TREE_CODE (field_type
) == QUAL_UNION_TYPE
592 || TREE_CODE (field_type
) == UNION_TYPE
)
594 if (parent_type_p (field_type
, child
))
604 /* Return the number of pointer tos for TYPE and return TYPE with all
605 of these stripped off. */
608 count_stars (tree
* type_ptr
)
610 tree type
= *type_ptr
;
612 type
= TYPE_MAIN_VARIANT (type
);
613 while (POINTER_TYPE_P (type
))
615 type
= TYPE_MAIN_VARIANT (TREE_TYPE (type
));
630 /* Check the cast FROM_TYPE to TO_TYPE. This function requires that
631 the two types have already passed the
632 ipa_type_escape_star_count_of_interesting_type test. */
634 static enum cast_type
635 check_cast_type (tree to_type
, tree from_type
)
637 int to_stars
= count_stars (&to_type
);
638 int from_stars
= count_stars (&from_type
);
639 if (to_stars
!= from_stars
)
642 if (to_type
== from_type
)
645 if (parent_type_p (to_type
, from_type
)) return CT_UP
;
646 if (parent_type_p (from_type
, to_type
)) return CT_DOWN
;
650 /* Check a cast FROM this variable, TO_TYPE. Mark the escaping types
653 check_cast (tree to_type
, tree from
)
655 tree from_type
= get_canon_type (TREE_TYPE (from
), false, false);
656 bool to_interesting_type
, from_interesting_type
;
658 to_type
= get_canon_type (to_type
, false, false);
659 if (!from_type
|| !to_type
|| from_type
== to_type
)
662 to_interesting_type
=
663 ipa_type_escape_star_count_of_interesting_type (to_type
) >= 0;
664 from_interesting_type
=
665 ipa_type_escape_star_count_of_interesting_type (from_type
) >= 0;
667 if (to_interesting_type
)
668 if (from_interesting_type
)
670 /* Both types are interesting. This can be one of four types
671 of cast: useless, up, down, or sideways. We do not care
672 about up or useless. Sideways casts are always bad and
673 both sides get marked as escaping. Downcasts are not
674 interesting here because if type is marked as escaping, all
675 of its subtypes escape. */
676 switch (check_cast_type (to_type
, from_type
))
684 mark_type (to_type
, FULL_ESCAPE
);
685 mark_type (from_type
, FULL_ESCAPE
);
691 /* If this is a cast from the local that is a result from a
692 call to malloc, do not mark the cast as bad. */
693 if (DECL_P (from
) && !bitmap_bit_p (results_of_malloc
, DECL_UID (from
)))
694 mark_type (to_type
, FULL_ESCAPE
);
696 else if (from_interesting_type
)
697 mark_type (from_type
, FULL_ESCAPE
);
700 /* Register the parameter and return types of function FN. The type
701 ESCAPES if the function is visible outside of the compilation
704 check_function_parameter_and_return_types (tree fn
, bool escapes
)
708 if (TYPE_ARG_TYPES (TREE_TYPE (fn
)))
710 for (arg
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
711 arg
&& TREE_VALUE (arg
) != void_type_node
;
712 arg
= TREE_CHAIN (arg
))
714 tree type
= get_canon_type (TREE_VALUE (arg
), false, false);
716 mark_interesting_type (type
, EXPOSED_PARAMETER
);
721 /* FIXME - According to Geoff Keating, we should never have to
722 do this; the front ends should always process the arg list
723 from the TYPE_ARG_LIST. However, Geoff is wrong, this code
724 does seem to be live. */
726 for (arg
= DECL_ARGUMENTS (fn
); arg
; arg
= TREE_CHAIN (arg
))
728 tree type
= get_canon_type (TREE_TYPE (arg
), false, false);
730 mark_interesting_type (type
, EXPOSED_PARAMETER
);
735 tree type
= get_canon_type (TREE_TYPE (TREE_TYPE (fn
)), false, false);
736 mark_interesting_type (type
, EXPOSED_PARAMETER
);
740 /* Return true if the variable T is the right kind of static variable to
741 perform compilation unit scope escape analysis. */
744 has_proper_scope_for_analysis (tree t
)
746 /* If the variable has the "used" attribute, treat it as if it had a
747 been touched by the devil. */
748 tree type
= get_canon_type (TREE_TYPE (t
), false, false);
751 if (lookup_attribute ("used", DECL_ATTRIBUTES (t
)))
753 mark_interesting_type (type
, FULL_ESCAPE
);
757 /* Do not want to do anything with volatile except mark any
758 function that uses one to be not const or pure. */
759 if (TREE_THIS_VOLATILE (t
))
762 /* Do not care about a local automatic that is not static. */
763 if (!TREE_STATIC (t
) && !DECL_EXTERNAL (t
))
766 if (DECL_EXTERNAL (t
) || TREE_PUBLIC (t
))
768 /* If the front end set the variable to be READONLY and
769 constant, we can allow this variable in pure or const
770 functions but the scope is too large for our analysis to set
771 these bits ourselves. */
773 if (TREE_READONLY (t
)
775 && is_gimple_min_invariant (DECL_INITIAL (t
)))
776 ; /* Read of a constant, do not change the function state. */
779 /* The type escapes for all public and externs. */
780 mark_interesting_type (type
, FULL_ESCAPE
);
785 /* If T is a VAR_DECL for a static that we are interested in, add the
786 uid to the bitmap. */
789 check_operand (tree t
)
793 /* This is an assignment from a function, register the types as
795 if (TREE_CODE (t
) == FUNCTION_DECL
)
796 check_function_parameter_and_return_types (t
, true);
798 else if (TREE_CODE (t
) == VAR_DECL
)
799 has_proper_scope_for_analysis (t
);
802 /* Examine tree T for references. */
807 if ((TREE_CODE (t
) == EXC_PTR_EXPR
) || (TREE_CODE (t
) == FILTER_EXPR
))
810 while (TREE_CODE (t
) == REALPART_EXPR
811 || TREE_CODE (t
) == IMAGPART_EXPR
812 || handled_component_p (t
))
814 if (TREE_CODE (t
) == ARRAY_REF
)
815 check_operand (TREE_OPERAND (t
, 1));
816 t
= TREE_OPERAND (t
, 0);
819 if (INDIRECT_REF_P (t
))
820 /* || TREE_CODE (t) == MEM_REF) */
821 check_tree (TREE_OPERAND (t
, 0));
823 if (SSA_VAR_P (t
) || (TREE_CODE (t
) == FUNCTION_DECL
))
827 /* Create an address_of edge FROM_TYPE.TO_TYPE. */
829 mark_interesting_addressof (tree to_type
, tree from_type
)
834 splay_tree_node result
;
836 from_type
= get_canon_type (from_type
, false, false);
837 to_type
= get_canon_type (to_type
, false, false);
839 if (!from_type
|| !to_type
)
842 from_uid
= TYPE_UID (from_type
);
843 to_uid
= TYPE_UID (to_type
);
845 gcc_assert (ipa_type_escape_star_count_of_interesting_type (from_type
) == 0);
847 /* Process the Y into X map pointer. */
848 result
= splay_tree_lookup (uid_to_addressof_down_map
,
849 (splay_tree_key
) from_uid
);
852 type_map
= (bitmap
) result
->value
;
855 type_map
= BITMAP_ALLOC (&ipa_obstack
);
856 splay_tree_insert (uid_to_addressof_down_map
,
858 (splay_tree_value
)type_map
);
860 bitmap_set_bit (type_map
, TYPE_UID (to_type
));
862 /* Process the X into Y reverse map pointer. */
864 splay_tree_lookup (uid_to_addressof_up_map
, (splay_tree_key
) to_uid
);
867 type_map
= (bitmap
) result
->value
;
870 type_map
= BITMAP_ALLOC (&ipa_obstack
);
871 splay_tree_insert (uid_to_addressof_up_map
,
873 (splay_tree_value
)type_map
);
875 bitmap_set_bit (type_map
, TYPE_UID (to_type
));
878 /* Scan tree T to see if there are any addresses taken in within T. */
881 look_for_address_of (tree t
)
883 if (TREE_CODE (t
) == ADDR_EXPR
)
885 tree x
= get_base_var (t
);
886 tree cref
= TREE_OPERAND (t
, 0);
888 /* If we have an expression of the form "&a.b.c.d", mark a.b,
889 b.c and c.d. as having its address taken. */
890 tree fielddecl
= NULL_TREE
;
893 if (TREE_CODE (cref
) == COMPONENT_REF
)
895 fielddecl
= TREE_OPERAND (cref
, 1);
896 mark_interesting_addressof (TREE_TYPE (fielddecl
),
897 DECL_FIELD_CONTEXT (fielddecl
));
899 else if (TREE_CODE (cref
) == ARRAY_REF
)
900 get_canon_type (TREE_TYPE (cref
), false, false);
902 cref
= TREE_OPERAND (cref
, 0);
905 if (TREE_CODE (x
) == VAR_DECL
)
906 has_proper_scope_for_analysis (x
);
911 /* Scan tree T to see if there are any casts within it.
912 LHS Is the LHS of the expression involving the cast. */
915 look_for_casts (tree lhs
__attribute__((unused
)), tree t
)
917 if (is_gimple_cast (t
) || TREE_CODE (t
) == VIEW_CONVERT_EXPR
)
919 tree castfromvar
= TREE_OPERAND (t
, 0);
920 check_cast (TREE_TYPE (t
), castfromvar
);
922 else if (TREE_CODE (t
) == COMPONENT_REF
923 || TREE_CODE (t
) == INDIRECT_REF
924 || TREE_CODE (t
) == BIT_FIELD_REF
)
926 tree base
= get_base_address (t
);
929 t
= TREE_OPERAND (t
, 0);
930 if (TREE_CODE (t
) == VIEW_CONVERT_EXPR
)
932 /* This may be some part of a component ref.
933 IE it may be a.b.VIEW_CONVERT_EXPR<weird_type>(c).d, AFAIK.
934 castfromref will give you a.b.c, not a. */
935 tree castfromref
= TREE_OPERAND (t
, 0);
936 check_cast (TREE_TYPE (t
), castfromref
);
938 else if (TREE_CODE (t
) == COMPONENT_REF
)
939 get_canon_type (TREE_TYPE (TREE_OPERAND (t
, 1)), false, false);
944 /* Check to see if T is a read or address of operation on a static var
945 we are interested in analyzing. */
948 check_rhs_var (tree t
)
950 look_for_address_of (t
);
954 /* Check to see if T is an assignment to a static var we are
955 interested in analyzing. */
958 check_lhs_var (tree t
)
963 /* This is a scaled down version of get_asm_expr_operands from
964 tree_ssa_operands.c. The version there runs much later and assumes
965 that aliasing information is already available. Here we are just
966 trying to find if the set of inputs and outputs contain references
967 or address of operations to local. FN is the function being
968 analyzed and STMT is the actual asm statement. */
971 get_asm_expr_operands (tree stmt
)
973 int noutputs
= list_length (ASM_OUTPUTS (stmt
));
974 const char **oconstraints
975 = (const char **) alloca ((noutputs
) * sizeof (const char *));
978 const char *constraint
;
979 bool allows_mem
, allows_reg
, is_inout
;
981 for (i
=0, link
= ASM_OUTPUTS (stmt
); link
; ++i
, link
= TREE_CHAIN (link
))
983 oconstraints
[i
] = constraint
984 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
985 parse_output_constraint (&constraint
, i
, 0, 0,
986 &allows_mem
, &allows_reg
, &is_inout
);
988 check_lhs_var (TREE_VALUE (link
));
991 for (link
= ASM_INPUTS (stmt
); link
; link
= TREE_CHAIN (link
))
994 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
995 parse_input_constraint (&constraint
, 0, 0, noutputs
, 0,
996 oconstraints
, &allows_mem
, &allows_reg
);
998 check_rhs_var (TREE_VALUE (link
));
1001 /* There is no code here to check for asm memory clobbers. The
1002 casual maintainer might think that such code would be necessary,
1003 but that appears to be wrong. In other parts of the compiler,
1004 the asm memory clobbers are assumed to only clobber variables
1005 that are addressable. All types with addressable instances are
1006 assumed to already escape. So, we are protected here. */
1009 /* Check the parameters of a function call to CALL_EXPR to mark the
1010 types that pass across the function boundary. Also check to see if
1011 this is either an indirect call, a call outside the compilation
1015 check_call (tree call_expr
)
1017 int flags
= call_expr_flags(call_expr
);
1018 tree operand_list
= TREE_OPERAND (call_expr
, 1);
1020 tree callee_t
= get_callee_fndecl (call_expr
);
1022 struct cgraph_node
* callee
;
1023 enum availability avail
= AVAIL_NOT_AVAILABLE
;
1025 for (operand
= operand_list
;
1026 operand
!= NULL_TREE
;
1027 operand
= TREE_CHAIN (operand
))
1029 tree argument
= TREE_VALUE (operand
);
1030 check_rhs_var (argument
);
1036 tree last_arg_type
= NULL
;
1037 callee
= cgraph_node(callee_t
);
1038 avail
= cgraph_function_body_availability (callee
);
1040 /* Check that there are no implicit casts in the passing of
1042 if (TYPE_ARG_TYPES (TREE_TYPE (callee_t
)))
1044 operand
= operand_list
;
1045 for (arg_type
= TYPE_ARG_TYPES (TREE_TYPE (callee_t
));
1046 arg_type
&& TREE_VALUE (arg_type
) != void_type_node
;
1047 arg_type
= TREE_CHAIN (arg_type
))
1051 argument
= TREE_VALUE (operand
);
1052 last_arg_type
= TREE_VALUE(arg_type
);
1053 check_cast (last_arg_type
, argument
);
1054 operand
= TREE_CHAIN (operand
);
1057 /* The code reaches here for some unfortunate
1058 builtin functions that do not have a list of
1065 /* FIXME - According to Geoff Keating, we should never
1066 have to do this; the front ends should always process
1067 the arg list from the TYPE_ARG_LIST. */
1068 operand
= operand_list
;
1069 for (arg_type
= DECL_ARGUMENTS (callee_t
);
1071 arg_type
= TREE_CHAIN (arg_type
))
1075 argument
= TREE_VALUE (operand
);
1076 last_arg_type
= TREE_TYPE(arg_type
);
1077 check_cast (last_arg_type
, argument
);
1078 operand
= TREE_CHAIN (operand
);
1081 /* The code reaches here for some unfortunate
1082 builtin functions that do not have a list of
1088 /* In the case where we have a var_args function, we need to
1089 check the remaining parameters against the last argument. */
1090 arg_type
= last_arg_type
;
1092 operand
!= NULL_TREE
;
1093 operand
= TREE_CHAIN (operand
))
1095 argument
= TREE_VALUE (operand
);
1097 check_cast (arg_type
, argument
);
1100 /* The code reaches here for some unfortunate
1101 builtin functions that do not have a list of
1102 argument types. Most of these functions have
1103 been marked as having their parameters not
1104 escape, but for the rest, the type is doomed. */
1105 tree type
= get_canon_type (TREE_TYPE (argument
), false, false);
1106 mark_interesting_type (type
, FULL_ESCAPE
);
1111 /* The callee is either unknown (indirect call) or there is just no
1112 scannable code for it (external call) . We look to see if there
1113 are any bits available for the callee (such as by declaration or
1114 because it is builtin) and process solely on the basis of those
1117 if (avail
== AVAIL_NOT_AVAILABLE
|| avail
== AVAIL_OVERWRITABLE
)
1119 /* If this is a direct call to an external function, mark all of
1120 the parameter and return types. */
1121 for (operand
= operand_list
;
1122 operand
!= NULL_TREE
;
1123 operand
= TREE_CHAIN (operand
))
1126 get_canon_type (TREE_TYPE (TREE_VALUE (operand
)), false, false);
1127 mark_interesting_type (type
, EXPOSED_PARAMETER
);
1133 get_canon_type (TREE_TYPE (TREE_TYPE (callee_t
)), false, false);
1134 mark_interesting_type (type
, EXPOSED_PARAMETER
);
1137 return (flags
& ECF_MALLOC
);
1140 /* CODE is the operation on OP0 and OP1. OP0 is the operand that we
1141 *know* is a pointer type. OP1 may be a pointer type. */
1143 okay_pointer_operation (enum tree_code code
, tree op0
, tree op1
)
1145 tree op0type
= TYPE_MAIN_VARIANT (TREE_TYPE (op0
));
1146 tree op1type
= TYPE_MAIN_VARIANT (TREE_TYPE (op1
));
1147 if (POINTER_TYPE_P (op1type
))
1154 /* TODO: Handle multiples of op0 size as well */
1155 if (operand_equal_p (size_in_bytes (op0type
), op1
, 0))
1165 /* TP is the part of the tree currently under the microscope.
1166 WALK_SUBTREES is part of the walk_tree api but is unused here.
1167 DATA is cgraph_node of the function being walked. */
1169 /* FIXME: When this is converted to run over SSA form, this code
1170 should be converted to use the operand scanner. */
1173 scan_for_refs (tree
*tp
, int *walk_subtrees
, void *data
)
1175 struct cgraph_node
*fn
= data
;
1178 switch (TREE_CODE (t
))
1181 if (DECL_INITIAL (t
))
1182 walk_tree (&DECL_INITIAL (t
), scan_for_refs
, fn
, visited_nodes
);
1188 /* First look on the lhs and see what variable is stored to */
1189 tree lhs
= TREE_OPERAND (t
, 0);
1190 tree rhs
= TREE_OPERAND (t
, 1);
1192 check_lhs_var (lhs
);
1193 check_cast (TREE_TYPE (lhs
), rhs
);
1195 /* For the purposes of figuring out what the cast affects */
1197 /* Next check the operands on the rhs to see if they are ok. */
1198 switch (TREE_CODE_CLASS (TREE_CODE (rhs
)))
1202 tree op0
= TREE_OPERAND (rhs
, 0);
1203 tree type0
= get_canon_type (TREE_TYPE (op0
), false, false);
1204 tree op1
= TREE_OPERAND (rhs
, 1);
1205 tree type1
= get_canon_type (TREE_TYPE (op1
), false, false);
1207 /* If this is pointer arithmetic of any bad sort, then
1208 we need to mark the types as bad. For binary
1209 operations, no binary operator we currently support
1210 is always "safe" in regard to what it would do to
1211 pointers for purposes of determining which types
1212 escape, except operations of the size of the type.
1213 It is possible that min and max under the right set
1214 of circumstances and if the moon is in the correct
1215 place could be safe, but it is hard to see how this
1216 is worth the effort. */
1218 if (type0
&& POINTER_TYPE_P (type0
)
1219 && !okay_pointer_operation (TREE_CODE (rhs
), op0
, op1
))
1220 mark_interesting_type (type0
, FULL_ESCAPE
);
1221 if (type1
&& POINTER_TYPE_P (type1
)
1222 && !okay_pointer_operation (TREE_CODE (rhs
), op1
, op0
))
1223 mark_interesting_type (type1
, FULL_ESCAPE
);
1225 look_for_casts (lhs
, op0
);
1226 look_for_casts (lhs
, op1
);
1227 check_rhs_var (op0
);
1228 check_rhs_var (op1
);
1233 tree op0
= TREE_OPERAND (rhs
, 0);
1234 tree type0
= get_canon_type (TREE_TYPE (op0
), false, false);
1235 /* For unary operations, if the operation is NEGATE or
1236 ABS on a pointer, this is also considered pointer
1237 arithmetic and thus, bad for business. */
1238 if (type0
&& (TREE_CODE (op0
) == NEGATE_EXPR
1239 || TREE_CODE (op0
) == ABS_EXPR
)
1240 && POINTER_TYPE_P (type0
))
1242 mark_interesting_type (type0
, FULL_ESCAPE
);
1244 check_rhs_var (op0
);
1245 look_for_casts (lhs
, op0
);
1246 look_for_casts (lhs
, rhs
);
1251 look_for_casts (lhs
, rhs
);
1252 check_rhs_var (rhs
);
1254 case tcc_declaration
:
1255 check_rhs_var (rhs
);
1257 case tcc_expression
:
1258 switch (TREE_CODE (rhs
))
1261 look_for_casts (lhs
, TREE_OPERAND (rhs
, 0));
1262 check_rhs_var (rhs
);
1265 /* If this is a call to malloc, squirrel away the
1266 result so we do mark the resulting cast as being
1268 if (check_call (rhs
))
1269 bitmap_set_bit (results_of_malloc
, DECL_UID (lhs
));
1283 /* This case is here to find addresses on rhs of constructors in
1284 decl_initial of static variables. */
1295 get_asm_expr_operands (t
);
1306 /* The init routine for analyzing global static variable usage. See
1307 comments at top for description. */
1311 bitmap_obstack_initialize (&ipa_obstack
);
1312 global_types_exposed_parameter
= BITMAP_ALLOC (&ipa_obstack
);
1313 global_types_full_escape
= BITMAP_ALLOC (&ipa_obstack
);
1314 global_types_seen
= BITMAP_ALLOC (&ipa_obstack
);
1315 results_of_malloc
= BITMAP_ALLOC (&ipa_obstack
);
1317 uid_to_canon_type
= splay_tree_new (splay_tree_compare_ints
, 0, 0);
1318 all_canon_types
= splay_tree_new (compare_type_brand
, 0, 0);
1319 type_to_canon_type
= splay_tree_new (splay_tree_compare_pointers
, 0, 0);
1320 uid_to_subtype_map
= splay_tree_new (splay_tree_compare_ints
, 0, 0);
1321 uid_to_addressof_down_map
= splay_tree_new (splay_tree_compare_ints
, 0, 0);
1322 uid_to_addressof_up_map
= splay_tree_new (splay_tree_compare_ints
, 0, 0);
1324 /* There are some shared nodes, in particular the initializers on
1325 static declarations. We do not need to scan them more than once
1326 since all we would be interested in are the addressof
1328 visited_nodes
= pointer_set_create ();
1332 /* Check out the rhs of a static or global initialization VNODE to see
1333 if any of them contain addressof operations. Note that some of
1334 these variables may not even be referenced in the code in this
1335 compilation unit but their right hand sides may contain references
1336 to variables defined within this unit. */
1339 analyze_variable (struct cgraph_varpool_node
*vnode
)
1341 tree global
= vnode
->decl
;
1342 tree type
= get_canon_type (TREE_TYPE (global
), false, false);
1344 /* If this variable has exposure beyond the compilation unit, add
1345 its type to the global types. */
1347 if (vnode
->externally_visible
)
1348 mark_interesting_type (type
, FULL_ESCAPE
);
1350 gcc_assert (TREE_CODE (global
) == VAR_DECL
);
1352 if (DECL_INITIAL (global
))
1353 walk_tree (&DECL_INITIAL (global
), scan_for_refs
, NULL
, visited_nodes
);
1356 /* This is the main routine for finding the reference patterns for
1357 global variables within a function FN. */
1360 analyze_function (struct cgraph_node
*fn
)
1362 tree decl
= fn
->decl
;
1363 check_function_parameter_and_return_types (decl
,
1364 fn
->local
.externally_visible
);
1366 fprintf (dump_file
, "\n local analysis of %s", cgraph_node_name (fn
));
1369 struct function
*this_cfun
= DECL_STRUCT_FUNCTION (decl
);
1370 basic_block this_block
;
1372 FOR_EACH_BB_FN (this_block
, this_cfun
)
1374 block_stmt_iterator bsi
;
1375 for (bsi
= bsi_start (this_block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1376 walk_tree (bsi_stmt_ptr (bsi
), scan_for_refs
,
1381 /* There may be const decls with interesting right hand sides. */
1382 if (DECL_STRUCT_FUNCTION (decl
))
1385 for (step
= DECL_STRUCT_FUNCTION (decl
)->unexpanded_var_list
;
1387 step
= TREE_CHAIN (step
))
1389 tree var
= TREE_VALUE (step
);
1390 if (TREE_CODE (var
) == VAR_DECL
1391 && DECL_INITIAL (var
)
1392 && !TREE_STATIC (var
))
1393 walk_tree (&DECL_INITIAL (var
), scan_for_refs
,
1395 get_canon_type (TREE_TYPE (var
), false, false);
1402 /* Convert a type_UID into a type. */
1404 type_for_uid (int uid
)
1406 splay_tree_node result
=
1407 splay_tree_lookup (uid_to_canon_type
, (splay_tree_key
) uid
);
1410 return (tree
) result
->value
;
1414 /* Return the a bitmap with the subtypes of the type for UID. If it
1415 does not exist, return either NULL or a new bitmap depending on the
1419 subtype_map_for_uid (int uid
, bool create
)
1421 splay_tree_node result
= splay_tree_lookup (uid_to_subtype_map
,
1422 (splay_tree_key
) uid
);
1425 return (bitmap
) result
->value
;
1428 bitmap subtype_map
= BITMAP_ALLOC (&ipa_obstack
);
1429 splay_tree_insert (uid_to_subtype_map
,
1431 (splay_tree_value
)subtype_map
);
1437 /* Mark all of the supertypes and field types of TYPE as being seen.
1438 Also accumulate the subtypes for each type so that
1439 close_types_full_escape can mark a subtype as escaping if the
1440 supertype escapes. */
1443 close_type_seen (tree type
)
1447 tree binfo
, base_binfo
;
1449 /* See thru all pointer tos and array ofs. */
1450 type
= get_canon_type (type
, true, true);
1454 uid
= TYPE_UID (type
);
1456 if (bitmap_bit_p (been_there_done_that
, uid
))
1458 bitmap_set_bit (been_there_done_that
, uid
);
1460 /* If we are doing a language with a type hierarchy, mark all of
1461 the superclasses. */
1462 if (TYPE_BINFO (type
))
1463 for (binfo
= TYPE_BINFO (type
), i
= 0;
1464 BINFO_BASE_ITERATE (binfo
, i
, base_binfo
); i
++)
1466 tree binfo_type
= BINFO_TYPE (base_binfo
);
1467 bitmap subtype_map
= subtype_map_for_uid
1468 (TYPE_UID (TYPE_MAIN_VARIANT (binfo_type
)), true);
1469 bitmap_set_bit (subtype_map
, uid
);
1470 close_type_seen (get_canon_type (binfo_type
, true, true));
1473 /* If the field is a struct or union type, mark all of the
1475 for (field
= TYPE_FIELDS (type
);
1477 field
= TREE_CHAIN (field
))
1480 if (TREE_CODE (field
) != FIELD_DECL
)
1483 field_type
= TREE_TYPE (field
);
1484 if (ipa_type_escape_star_count_of_interesting_or_array_type (field_type
) >= 0)
1485 close_type_seen (get_canon_type (field_type
, true, true));
1489 /* Take a TYPE that has been passed by value to an external function
1490 and mark all of the fields that have pointer types as escaping. For
1491 any of the non pointer types that are structures or unions,
1492 recurse. TYPE is never a pointer type. */
1495 close_type_exposed_parameter (tree type
)
1500 type
= get_canon_type (type
, false, false);
1503 uid
= TYPE_UID (type
);
1504 gcc_assert (!POINTER_TYPE_P (type
));
1506 if (bitmap_bit_p (been_there_done_that
, uid
))
1508 bitmap_set_bit (been_there_done_that
, uid
);
1510 /* If the field is a struct or union type, mark all of the
1512 for (field
= TYPE_FIELDS (type
);
1514 field
= TREE_CHAIN (field
))
1518 if (TREE_CODE (field
) != FIELD_DECL
)
1521 field_type
= get_canon_type (TREE_TYPE (field
), false, false);
1522 mark_interesting_type (field_type
, EXPOSED_PARAMETER
);
1524 /* Only recurse for non pointer types of structures and unions. */
1525 if (ipa_type_escape_star_count_of_interesting_type (field_type
) == 0)
1526 close_type_exposed_parameter (field_type
);
1530 /* The next function handles the case where a type fully escapes.
1531 This means that not only does the type itself escape,
1533 a) the type of every field recursively escapes
1534 b) the type of every subtype escapes as well as the super as well
1535 as all of the pointer to types for each field.
1537 Note that pointer to types are not marked as escaping. If the
1538 pointed to type escapes, the pointer to type also escapes.
1540 Take a TYPE that has had the address taken for an instance of it
1541 and mark all of the types for its fields as having their addresses
1545 close_type_full_escape (tree type
)
1550 tree binfo
, base_binfo
;
1553 splay_tree_node address_result
;
1555 /* Strip off any pointer or array types. */
1556 type
= get_canon_type (type
, true, true);
1559 uid
= TYPE_UID (type
);
1561 if (bitmap_bit_p (been_there_done_that
, uid
))
1563 bitmap_set_bit (been_there_done_that
, uid
);
1565 subtype_map
= subtype_map_for_uid (uid
, false);
1567 /* If we are doing a language with a type hierarchy, mark all of
1568 the superclasses. */
1569 if (TYPE_BINFO (type
))
1570 for (binfo
= TYPE_BINFO (type
), i
= 0;
1571 BINFO_BASE_ITERATE (binfo
, i
, base_binfo
); i
++)
1573 tree binfotype
= BINFO_TYPE (base_binfo
);
1574 binfotype
= mark_type (binfotype
, FULL_ESCAPE
);
1575 close_type_full_escape (binfotype
);
1578 /* Mark as escaped any types that have been down casted to
1581 EXECUTE_IF_SET_IN_BITMAP (subtype_map
, 0, i
, bi
)
1583 tree subtype
= type_for_uid (i
);
1584 subtype
= mark_type (subtype
, FULL_ESCAPE
);
1585 close_type_full_escape (subtype
);
1588 /* If the field is a struct or union type, mark all of the
1590 for (field
= TYPE_FIELDS (type
);
1592 field
= TREE_CHAIN (field
))
1595 if (TREE_CODE (field
) != FIELD_DECL
)
1598 field_type
= TREE_TYPE (field
);
1599 if (ipa_type_escape_star_count_of_interesting_or_array_type (field_type
) >= 0)
1601 field_type
= mark_type (field_type
, FULL_ESCAPE
);
1602 close_type_full_escape (field_type
);
1606 /* For all of the types A that contain this type B and were part of
1607 an expression like "&...A.B...", mark the A's as escaping. */
1608 address_result
= splay_tree_lookup (uid_to_addressof_up_map
,
1609 (splay_tree_key
) uid
);
1612 bitmap containing_classes
= (bitmap
) address_result
->value
;
1613 EXECUTE_IF_SET_IN_BITMAP (containing_classes
, 0, i
, bi
)
1615 close_type_full_escape (type_for_uid (i
));
1620 /* Transitively close the addressof bitmap for the type with UID.
1621 This means that if we had a.b and b.c, a would have both b and c in
1625 close_addressof_down (int uid
)
1628 splay_tree_node result
=
1629 splay_tree_lookup (uid_to_addressof_down_map
, (splay_tree_key
) uid
);
1635 map
= (bitmap
) result
->value
;
1639 if (bitmap_bit_p (been_there_done_that
, uid
))
1641 bitmap_set_bit (been_there_done_that
, uid
);
1643 /* If the type escapes, get rid of the addressof map, it will not be
1645 if (bitmap_bit_p (global_types_full_escape
, uid
))
1648 splay_tree_remove (uid_to_addressof_down_map
, (splay_tree_key
) uid
);
1652 /* The new_map will have all of the bits for the enclosed fields and
1653 will have the unique id version of the old map. */
1654 new_map
= BITMAP_ALLOC (&ipa_obstack
);
1656 EXECUTE_IF_SET_IN_BITMAP (map
, 0, i
, bi
)
1658 bitmap submap
= close_addressof_down (i
);
1659 bitmap_set_bit (new_map
, i
);
1661 bitmap_ior_into (new_map
, submap
);
1663 result
->value
= (splay_tree_value
) new_map
;
1670 /* The main entry point for type escape analysis. */
1673 type_escape_execute (void)
1675 struct cgraph_node
*node
;
1676 struct cgraph_varpool_node
*vnode
;
1679 splay_tree_node result
;
1683 /* Process all of the variables first. */
1684 for (vnode
= cgraph_varpool_nodes_queue
; vnode
; vnode
= vnode
->next_needed
)
1685 analyze_variable (vnode
);
1687 /* Process all of the functions. next
1689 We do not want to process any of the clones so we check that this
1690 is a master clone. However, we do need to process any
1691 AVAIL_OVERWRITABLE functions (these are never clones) because
1692 they may cause a type variable to escape.
1694 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1696 && (cgraph_is_master_clone (node
)
1697 || (cgraph_function_body_availability (node
) == AVAIL_OVERWRITABLE
)))
1698 analyze_function (node
);
1701 pointer_set_destroy (visited_nodes
);
1702 visited_nodes
= NULL
;
1704 /* Do all of the closures to discover which types escape the
1705 compilation unit. */
1707 been_there_done_that
= BITMAP_ALLOC (&ipa_obstack
);
1708 bitmap_tmp
= BITMAP_ALLOC (&ipa_obstack
);
1710 /* Examine the types that we have directly seen in scanning the code
1711 and add to that any contained types or superclasses. */
1713 bitmap_copy (bitmap_tmp
, global_types_seen
);
1714 EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp
, 0, i
, bi
)
1716 tree type
= type_for_uid (i
);
1717 /* Only look at records and unions and pointer tos. */
1718 if (ipa_type_escape_star_count_of_interesting_or_array_type (type
) >= 0)
1719 close_type_seen (type
);
1721 bitmap_clear (been_there_done_that
);
1723 /* Examine all of the types passed by value and mark any enclosed
1724 pointer types as escaping. */
1725 bitmap_copy (bitmap_tmp
, global_types_exposed_parameter
);
1726 EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp
, 0, i
, bi
)
1728 close_type_exposed_parameter (type_for_uid (i
));
1730 bitmap_clear (been_there_done_that
);
1732 /* Close the types for escape. If something escapes, then any
1733 enclosed types escape as well as any subtypes. */
1734 bitmap_copy (bitmap_tmp
, global_types_full_escape
);
1735 EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp
, 0, i
, bi
)
1737 close_type_full_escape (type_for_uid (i
));
1739 bitmap_clear (been_there_done_that
);
1741 /* Before this pass, the uid_to_addressof_down_map for type X
1742 contained an entry for Y if there had been an operation of the
1743 form &X.Y. This step adds all of the fields contained within Y
1744 (recursively) to X's map. */
1746 result
= splay_tree_min (uid_to_addressof_down_map
);
1749 int uid
= result
->key
;
1750 /* Close the addressof map, i.e. copy all of the transitive
1751 substructures up to this level. */
1752 close_addressof_down (uid
);
1753 result
= splay_tree_successor (uid_to_addressof_down_map
, uid
);
1756 /* Do not need the array types and pointer types in the persistent
1758 result
= splay_tree_min (all_canon_types
);
1761 tree type
= (tree
) result
->value
;
1762 tree key
= (tree
) result
->key
;
1763 if (POINTER_TYPE_P (type
)
1764 || TREE_CODE (type
) == ARRAY_TYPE
)
1766 splay_tree_remove (all_canon_types
, (splay_tree_key
) result
->key
);
1767 splay_tree_remove (type_to_canon_type
, (splay_tree_key
) type
);
1768 splay_tree_remove (uid_to_canon_type
, (splay_tree_key
) TYPE_UID (type
));
1769 bitmap_clear_bit (global_types_seen
, TYPE_UID (type
));
1771 result
= splay_tree_successor (all_canon_types
, (splay_tree_key
) key
);
1776 EXECUTE_IF_SET_IN_BITMAP (global_types_seen
, 0, i
, bi
)
1778 /* The pointer types are in the global_types_full_escape
1779 bitmap but not in the backwards map. They also contain
1780 no useful information since they are not marked. */
1781 tree type
= type_for_uid (i
);
1782 fprintf(dump_file
, "type %d ", i
);
1783 print_generic_expr (dump_file
, type
, 0);
1784 if (bitmap_bit_p (global_types_full_escape
, i
))
1785 fprintf(dump_file
, " escaped\n");
1787 fprintf(dump_file
, " contained\n");
1791 /* Get rid of uid_to_addressof_up_map and its bitmaps. */
1792 result
= splay_tree_min (uid_to_addressof_up_map
);
1795 int uid
= (int)result
->key
;
1796 bitmap bm
= (bitmap
)result
->value
;
1799 splay_tree_remove (uid_to_addressof_up_map
, (splay_tree_key
) uid
);
1800 result
= splay_tree_successor (uid_to_addressof_up_map
, uid
);
1803 /* Get rid of the subtype map. */
1804 result
= splay_tree_min (uid_to_subtype_map
);
1807 bitmap b
= (bitmap
)result
->value
;
1809 splay_tree_remove (uid_to_subtype_map
, result
->key
);
1810 result
= splay_tree_min (uid_to_subtype_map
);
1812 splay_tree_delete (uid_to_subtype_map
);
1813 uid_to_subtype_map
= NULL
;
1815 BITMAP_FREE (global_types_exposed_parameter
);
1816 BITMAP_FREE (been_there_done_that
);
1817 BITMAP_FREE (bitmap_tmp
);
1818 BITMAP_FREE (results_of_malloc
);
1823 gate_type_escape_vars (void)
1825 return (flag_unit_at_a_time
!= 0 && flag_ipa_type_escape
1826 /* Don't bother doing anything if the program has errors. */
1827 && !(errorcount
|| sorrycount
));
1830 struct tree_opt_pass pass_ipa_type_escape
=
1832 "type-escape-var", /* name */
1833 gate_type_escape_vars
, /* gate */
1834 type_escape_execute
, /* execute */
1837 0, /* static_pass_number */
1838 TV_IPA_TYPE_ESCAPE
, /* tv_id */
1839 0, /* properties_required */
1840 0, /* properties_provided */
1841 0, /* properties_destroyed */
1842 0, /* todo_flags_start */
1843 0, /* todo_flags_finish */