diff options
Diffstat (limited to 'gcc-4.2.1-5666.3/gcc/ipa-type-escape.c')
-rw-r--r-- | gcc-4.2.1-5666.3/gcc/ipa-type-escape.c | 1868 |
1 files changed, 1868 insertions, 0 deletions
diff --git a/gcc-4.2.1-5666.3/gcc/ipa-type-escape.c b/gcc-4.2.1-5666.3/gcc/ipa-type-escape.c new file mode 100644 index 000000000..495193d3f --- /dev/null +++ b/gcc-4.2.1-5666.3/gcc/ipa-type-escape.c @@ -0,0 +1,1868 @@ +/* Type based alias analysis. + Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc. + Contributed by Kenneth Zadeck <zadeck@naturalbridge.com> + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ + +/* This pass determines which types in the program contain only + instances that are completely encapsulated by the compilation unit. + Those types that are encapsulated must also pass the further + requirement that there be no bad operations on any instances of + those types. + + A great deal of freedom in compilation is allowed for the instances + of those types that pass these conditions. +*/ + +/* The code in this module is called by the ipa pass manager. It + should be one of the later passes since its information is used by + the rest of the compilation. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "tree.h" +#include "tree-flow.h" +#include "tree-inline.h" +#include "tree-pass.h" +#include "langhooks.h" +#include "pointer-set.h" +#include "ggc.h" +#include "ipa-utils.h" +#include "ipa-type-escape.h" +#include "c-common.h" +#include "tree-gimple.h" +#include "cgraph.h" +#include "output.h" +#include "flags.h" +#include "timevar.h" +#include "diagnostic.h" +#include "langhooks.h" + +/* Some of the aliasing is called very early, before this phase is + called. To assure that this is not a problem, we keep track of if + this phase has been run. */ +static bool initialized = false; + +/* This bitmap contains the set of local vars that are the lhs of + calls to mallocs. These variables, when seen on the rhs as part of + a cast, the cast are not marked as doing bad things to the type + even though they are generally of the form + "foo = (type_of_foo)void_temp". */ +static bitmap results_of_malloc; + +/* Scratch bitmap for avoiding work. */ +static bitmap been_there_done_that; +static bitmap bitmap_tmp; + +/* There are two levels of escape that types can undergo. + + EXPOSED_PARAMETER - some instance of the variable is + passed by value into an externally visible function or some + instance of the variable is passed out of an externally visible + function as a return value. In this case any of the fields of the + variable that are pointer types end up having their types marked as + FULL_ESCAPE. + + FULL_ESCAPE - when bad things happen to good types. One of the + following things happens to the type: (a) either an instance of the + variable has its address passed to an externally visible function, + (b) the address is taken and some bad cast happens to the address + or (c) explicit arithmetic is done to the address. +*/ + +enum escape_t +{ + EXPOSED_PARAMETER, + FULL_ESCAPE +}; + +/* The following two bit vectors global_types_* correspond to + previous cases above. During the analysis phase, a bit is set in + one of these vectors if an operation of the offending class is + discovered to happen on the associated type. */ + +static bitmap global_types_exposed_parameter; +static bitmap global_types_full_escape; + +/* All of the types seen in this compilation unit. */ +static bitmap global_types_seen; +/* Reverse map to take a canon uid and map it to a canon type. Uid's + are never manipulated unless they are associated with a canon + type. */ +static splay_tree uid_to_canon_type; + +/* Internal structure of type mapping code. This maps a canon type + name to its canon type. */ +static splay_tree all_canon_types; + +/* Map from type clones to the single canon type. */ +static splay_tree type_to_canon_type; + +/* A splay tree of bitmaps. An element X in the splay tree has a bit + set in its bitmap at TYPE_UID (TYPE_MAIN_VARIANT (Y)) if there was + an operation in the program of the form "&X.Y". */ +static splay_tree uid_to_addressof_down_map; + +/* A splay tree of bitmaps. An element Y in the splay tree has a bit + set in its bitmap at TYPE_UID (TYPE_MAIN_VARIANT (X)) if there was + an operation in the program of the form "&X.Y". */ +static splay_tree uid_to_addressof_up_map; + +/* Tree to hold the subtype maps used to mark subtypes of escaped + types. */ +static splay_tree uid_to_subtype_map; + +/* Records tree nodes seen in cgraph_create_edges. Simply using + walk_tree_without_duplicates doesn't guarantee each node is visited + once because it gets a new htab upon each recursive call from + scan_for_refs. */ +static struct pointer_set_t *visited_nodes; + +static bitmap_obstack ipa_obstack; + +/* Get the name of TYPE or return the string "<UNNAMED>". */ +static char* +get_name_of_type (tree type) +{ + tree name = TYPE_NAME (type); + + if (!name) + /* Unnamed type, do what you like here. */ + return (char*)"<UNNAMED>"; + + /* It will be a TYPE_DECL in the case of a typedef, otherwise, an + identifier_node */ + if (TREE_CODE (name) == TYPE_DECL) + { + /* Each DECL has a DECL_NAME field which contains an + IDENTIFIER_NODE. (Some decls, most often labels, may have + zero as the DECL_NAME). */ + if (DECL_NAME (name)) + return (char*)IDENTIFIER_POINTER (DECL_NAME (name)); + else + /* Unnamed type, do what you like here. */ + return (char*)"<UNNAMED>"; + } + else if (TREE_CODE (name) == IDENTIFIER_NODE) + return (char*)IDENTIFIER_POINTER (name); + else + return (char*)"<UNNAMED>"; +} + +struct type_brand_s +{ + char* name; + int seq; +}; + +/* Splay tree comparison function on type_brand_s structures. */ + +static int +compare_type_brand (splay_tree_key sk1, splay_tree_key sk2) +{ + struct type_brand_s * k1 = (struct type_brand_s *) sk1; + struct type_brand_s * k2 = (struct type_brand_s *) sk2; + + int value = strcmp(k1->name, k2->name); + if (value == 0) + return k2->seq - k1->seq; + else + return value; +} + +/* All of the "unique_type" code is a hack to get around the sleazy + implementation used to compile more than file. Currently gcc does + not get rid of multiple instances of the same type that have been + collected from different compilation units. */ +/* This is a trivial algorithm for removing duplicate types. This + would not work for any language that used structural equivalence as + the basis of its type system. */ +/* Return either TYPE if this is first time TYPE has been seen an + compatible TYPE that has already been processed. */ + +static tree +discover_unique_type (tree type) +{ + struct type_brand_s * brand = XNEW (struct type_brand_s); + int i = 0; + splay_tree_node result; + + brand->name = get_name_of_type (type); + + while (1) + { + brand->seq = i++; + result = splay_tree_lookup (all_canon_types, (splay_tree_key) brand); + + if (result) + { + /* Create an alias since this is just the same as + other_type. */ + tree other_type = (tree) result->value; + if (lang_hooks.types_compatible_p (type, other_type) == 1) + { + free (brand); + /* Insert this new type as an alias for other_type. */ + splay_tree_insert (type_to_canon_type, + (splay_tree_key) type, + (splay_tree_value) other_type); + return other_type; + } + /* Not compatible, look for next instance with same name. */ + } + else + { + /* No more instances, create new one since this is the first + time we saw this type. */ + brand->seq = i++; + /* Insert the new brand. */ + splay_tree_insert (all_canon_types, + (splay_tree_key) brand, + (splay_tree_value) type); + + /* Insert this new type as an alias for itself. */ + splay_tree_insert (type_to_canon_type, + (splay_tree_key) type, + (splay_tree_value) type); + + /* Insert the uid for reverse lookup; */ + splay_tree_insert (uid_to_canon_type, + (splay_tree_key) TYPE_UID (type), + (splay_tree_value) type); + + bitmap_set_bit (global_types_seen, TYPE_UID (type)); + return type; + } + } +} + +/* Return true if TYPE is one of the type classes that we are willing + to analyze. This skips the goofy types like arrays of pointers to + methods. */ +static bool +type_to_consider (tree type) +{ + /* Strip the *'s off. */ + type = TYPE_MAIN_VARIANT (type); + while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE) + type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); + + switch (TREE_CODE (type)) + { + case BOOLEAN_TYPE: + case COMPLEX_TYPE: + case ENUMERAL_TYPE: + case INTEGER_TYPE: + case QUAL_UNION_TYPE: + case REAL_TYPE: + case RECORD_TYPE: + case UNION_TYPE: + case VECTOR_TYPE: + case VOID_TYPE: + return true; + + default: + return false; + } +} + +/* Get the canon type of TYPE. If SEE_THRU_PTRS is true, remove all + the POINTER_TOs and if SEE_THRU_ARRAYS is true, remove all of the + ARRAY_OFs and POINTER_TOs. */ + +static tree +get_canon_type (tree type, bool see_thru_ptrs, bool see_thru_arrays) +{ + splay_tree_node result; + /* Strip the *'s off. */ + if (!type || !type_to_consider (type)) + return NULL; + + type = TYPE_MAIN_VARIANT (type); + if (see_thru_arrays) + while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE) + type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); + + else if (see_thru_ptrs) + while (POINTER_TYPE_P (type)) + type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); + + result = splay_tree_lookup(type_to_canon_type, (splay_tree_key) type); + + if (result == NULL) + return discover_unique_type (type); + else return (tree) result->value; +} + +/* Same as GET_CANON_TYPE, except return the TYPE_ID rather than the + TYPE. */ + +static int +get_canon_type_uid (tree type, bool see_thru_ptrs, bool see_thru_arrays) +{ + type = get_canon_type (type, see_thru_ptrs, see_thru_arrays); + if (type) + return TYPE_UID(type); + else return 0; +} + +/* Return 0 if TYPE is a record or union type. Return a positive + number if TYPE is a pointer to a record or union. The number is + the number of pointer types stripped to get to the record or union + type. Return -1 if TYPE is none of the above. */ + +int +ipa_type_escape_star_count_of_interesting_type (tree type) +{ + int count = 0; + /* Strip the *'s off. */ + if (!type) + return -1; + type = TYPE_MAIN_VARIANT (type); + while (POINTER_TYPE_P (type)) + { + type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); + count++; + } + + /* We are interested in records, and unions only. */ + if (TREE_CODE (type) == RECORD_TYPE + || TREE_CODE (type) == QUAL_UNION_TYPE + || TREE_CODE (type) == UNION_TYPE) + return count; + else + return -1; +} + + +/* Return 0 if TYPE is a record or union type. Return a positive + number if TYPE is a pointer to a record or union. The number is + the number of pointer types stripped to get to the record or union + type. Return -1 if TYPE is none of the above. */ + +int +ipa_type_escape_star_count_of_interesting_or_array_type (tree type) +{ + int count = 0; + /* Strip the *'s off. */ + if (!type) + return -1; + type = TYPE_MAIN_VARIANT (type); + while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE) + { + type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); + count++; + } + + /* We are interested in records, and unions only. */ + if (TREE_CODE (type) == RECORD_TYPE + || TREE_CODE (type) == QUAL_UNION_TYPE + || TREE_CODE (type) == UNION_TYPE) + return count; + else + return -1; +} + + +/* Return true if the record, or union TYPE passed in escapes this + compilation unit. Note that all of the pointer-to's are removed + before testing since these may not be correct. */ + +bool +ipa_type_escape_type_contained_p (tree type) +{ + if (!initialized) + return false; + return !bitmap_bit_p (global_types_full_escape, + get_canon_type_uid (type, true, false)); +} + +/* Return true if a modification to a field of type FIELD_TYPE cannot + clobber a record of RECORD_TYPE. */ + +bool +ipa_type_escape_field_does_not_clobber_p (tree record_type, tree field_type) +{ + splay_tree_node result; + int uid; + + if (!initialized) + return false; + + /* Strip off all of the pointer tos on the record type. Strip the + same number of pointer tos from the field type. If the field + type has fewer, it could not have been aliased. */ + record_type = TYPE_MAIN_VARIANT (record_type); + field_type = TYPE_MAIN_VARIANT (field_type); + while (POINTER_TYPE_P (record_type)) + { + record_type = TYPE_MAIN_VARIANT (TREE_TYPE (record_type)); + if (POINTER_TYPE_P (field_type)) + field_type = TYPE_MAIN_VARIANT (TREE_TYPE (field_type)); + else + /* However, if field_type is a union, this quick test is not + correct since one of the variants of the union may be a + pointer to type and we cannot see across that here. So we + just strip the remaining pointer tos off the record type + and fall thru to the more precise code. */ + if (TREE_CODE (field_type) == QUAL_UNION_TYPE + || TREE_CODE (field_type) == UNION_TYPE) + { + while (POINTER_TYPE_P (record_type)) + record_type = TYPE_MAIN_VARIANT (TREE_TYPE (record_type)); + break; + } + else + return true; + } + + record_type = get_canon_type (record_type, true, true); + /* The record type must be contained. The field type may + escape. */ + if (!ipa_type_escape_type_contained_p (record_type)) + return false; + + uid = TYPE_UID (record_type); + result = splay_tree_lookup (uid_to_addressof_down_map, (splay_tree_key) uid); + + if (result) + { + bitmap field_type_map = (bitmap) result->value; + uid = get_canon_type_uid (field_type, true, true); + /* If the bit is there, the address was taken. If not, it + wasn't. */ + return !bitmap_bit_p (field_type_map, uid); + } + else + /* No bitmap means no addresses were taken. */ + return true; +} + + +/* Add TYPE to the suspect type set. Return true if the bit needed to + be marked. */ + +static tree +mark_type (tree type, enum escape_t escape_status) +{ + bitmap map = NULL; + int uid; + + type = get_canon_type (type, true, true); + if (!type) + return NULL; + + switch (escape_status) + { + case EXPOSED_PARAMETER: + map = global_types_exposed_parameter; + break; + case FULL_ESCAPE: + map = global_types_full_escape; + break; + } + + uid = TYPE_UID (type); + if (bitmap_bit_p (map, uid)) + return type; + else + { + bitmap_set_bit (map, uid); + if (escape_status == FULL_ESCAPE) + { + /* Efficiency hack. When things are bad, do not mess around + with this type anymore. */ + bitmap_set_bit (global_types_exposed_parameter, uid); + } + } + return type; +} + +/* Add interesting TYPE to the suspect type set. If the set is + EXPOSED_PARAMETER and the TYPE is a pointer type, the set is + changed to FULL_ESCAPE. */ + +static void +mark_interesting_type (tree type, enum escape_t escape_status) +{ + if (!type) return; + if (ipa_type_escape_star_count_of_interesting_type (type) >= 0) + { + if ((escape_status == EXPOSED_PARAMETER) + && POINTER_TYPE_P (type)) + /* EXPOSED_PARAMETERs are only structs or unions are passed by + value. Anything passed by reference to an external + function fully exposes the type. */ + mark_type (type, FULL_ESCAPE); + else + mark_type (type, escape_status); + } +} + +/* Return true if PARENT is supertype of CHILD. Both types must be + known to be structures or unions. */ + +/* APPLE LOCAL begin 6107012 */ +static struct pointer_set_t GTY(()) *parent_type_p_pset; +/* APPLE LOCAL end 6107012 */ + +static bool +parent_type_p (tree parent, tree child) +{ + int i; + tree binfo, base_binfo; + + /* APPLE LOCAL begin 6107012 */ + /* Don't walk the same tree twice. */ + if (parent_type_p_pset && pointer_set_insert (parent_type_p_pset, parent)) + return false; + /* APPLE LOCAL end 6107012 */ + + if (TYPE_BINFO (parent)) + for (binfo = TYPE_BINFO (parent), i = 0; + BINFO_BASE_ITERATE (binfo, i, base_binfo); i++) + { + tree binfotype = BINFO_TYPE (base_binfo); + if (binfotype == child) + return true; + else if (parent_type_p (binfotype, child)) + return true; + } + if (TREE_CODE (parent) == UNION_TYPE + || TREE_CODE (parent) == QUAL_UNION_TYPE) + { + tree field; + /* Search all of the variants in the union to see if one of them + is the child. */ + for (field = TYPE_FIELDS (parent); + field; + field = TREE_CHAIN (field)) + { + tree field_type; + if (TREE_CODE (field) != FIELD_DECL) + continue; + + field_type = TREE_TYPE (field); + if (field_type == child) + return true; + } + + /* If we did not find it, recursively ask the variants if one of + their children is the child type. */ + for (field = TYPE_FIELDS (parent); + field; + field = TREE_CHAIN (field)) + { + tree field_type; + if (TREE_CODE (field) != FIELD_DECL) + continue; + + field_type = TREE_TYPE (field); + if (TREE_CODE (field_type) == RECORD_TYPE + || TREE_CODE (field_type) == QUAL_UNION_TYPE + || TREE_CODE (field_type) == UNION_TYPE) + if (parent_type_p (field_type, child)) + return true; + } + } + + if (TREE_CODE (parent) == RECORD_TYPE) + { + tree field; + for (field = TYPE_FIELDS (parent); + field; + field = TREE_CHAIN (field)) + { + tree field_type; + if (TREE_CODE (field) != FIELD_DECL) + continue; + + field_type = TREE_TYPE (field); + if (field_type == child) + return true; + /* You can only cast to the first field so if it does not + match, quit. */ + if (TREE_CODE (field_type) == RECORD_TYPE + || TREE_CODE (field_type) == QUAL_UNION_TYPE + || TREE_CODE (field_type) == UNION_TYPE) + { + if (parent_type_p (field_type, child)) + return true; + else + break; + } + } + } + return false; +} + +/* Return the number of pointer tos for TYPE and return TYPE with all + of these stripped off. */ + +static int +count_stars (tree* type_ptr) +{ + tree type = *type_ptr; + int i = 0; + type = TYPE_MAIN_VARIANT (type); + while (POINTER_TYPE_P (type)) + { + type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); + i++; + } + + *type_ptr = type; + return i; +} + +enum cast_type { + CT_UP, + CT_DOWN, + CT_SIDEWAYS, + CT_USELESS +}; + +/* Check the cast FROM_TYPE to TO_TYPE. This function requires that + the two types have already passed the + ipa_type_escape_star_count_of_interesting_type test. */ + +static enum cast_type +check_cast_type (tree to_type, tree from_type) +{ + int to_stars = count_stars (&to_type); + int from_stars = count_stars (&from_type); + if (to_stars != from_stars) + return CT_SIDEWAYS; + + if (to_type == from_type) + return CT_USELESS; + + /* APPLE LOCAL 6107012 */ + parent_type_p_pset = pointer_set_create (); + if (parent_type_p (to_type, from_type)) return CT_UP; + /* APPLE LOCAL begin 6107012 */ + pointer_set_destroy (parent_type_p_pset); + parent_type_p_pset = pointer_set_create (); + /* APPLE LOCAL end 6107012 */ + if (parent_type_p (from_type, to_type)) return CT_DOWN; + /* APPLE LOCAL begin 6107012 */ + pointer_set_destroy (parent_type_p_pset); + parent_type_p_pset = (struct pointer_set_t *)0; + /* APPLE LOCAL end 6107012 */ + return CT_SIDEWAYS; +} + +/* Check a cast FROM this variable, TO_TYPE. Mark the escaping types + if appropriate. */ +static void +check_cast (tree to_type, tree from) +{ + tree from_type = get_canon_type (TREE_TYPE (from), false, false); + bool to_interesting_type, from_interesting_type; + + to_type = get_canon_type (to_type, false, false); + if (!from_type || !to_type || from_type == to_type) + return; + + to_interesting_type = + ipa_type_escape_star_count_of_interesting_type (to_type) >= 0; + from_interesting_type = + ipa_type_escape_star_count_of_interesting_type (from_type) >= 0; + + if (to_interesting_type) + if (from_interesting_type) + { + /* Both types are interesting. This can be one of four types + of cast: useless, up, down, or sideways. We do not care + about up or useless. Sideways casts are always bad and + both sides get marked as escaping. Downcasts are not + interesting here because if type is marked as escaping, all + of its subtypes escape. */ + switch (check_cast_type (to_type, from_type)) + { + case CT_UP: + case CT_USELESS: + case CT_DOWN: + break; + + case CT_SIDEWAYS: + mark_type (to_type, FULL_ESCAPE); + mark_type (from_type, FULL_ESCAPE); + break; + } + } + else + { + /* If this is a cast from the local that is a result from a + call to malloc, do not mark the cast as bad. */ + if (DECL_P (from) && !bitmap_bit_p (results_of_malloc, DECL_UID (from))) + mark_type (to_type, FULL_ESCAPE); + } + else if (from_interesting_type) + mark_type (from_type, FULL_ESCAPE); +} + +/* Register the parameter and return types of function FN. The type + ESCAPES if the function is visible outside of the compilation + unit. */ +static void +check_function_parameter_and_return_types (tree fn, bool escapes) +{ + tree arg; + + if (TYPE_ARG_TYPES (TREE_TYPE (fn))) + { + for (arg = TYPE_ARG_TYPES (TREE_TYPE (fn)); + arg && TREE_VALUE (arg) != void_type_node; + arg = TREE_CHAIN (arg)) + { + tree type = get_canon_type (TREE_VALUE (arg), false, false); + if (escapes) + mark_interesting_type (type, EXPOSED_PARAMETER); + } + } + else + { + /* FIXME - According to Geoff Keating, we should never have to + do this; the front ends should always process the arg list + from the TYPE_ARG_LIST. However, Geoff is wrong, this code + does seem to be live. */ + + for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg)) + { + tree type = get_canon_type (TREE_TYPE (arg), false, false); + if (escapes) + mark_interesting_type (type, EXPOSED_PARAMETER); + } + } + if (escapes) + { + tree type = get_canon_type (TREE_TYPE (TREE_TYPE (fn)), false, false); + mark_interesting_type (type, EXPOSED_PARAMETER); + } +} + +/* Return true if the variable T is the right kind of static variable to + perform compilation unit scope escape analysis. */ + +static inline void +has_proper_scope_for_analysis (tree t) +{ + /* If the variable has the "used" attribute, treat it as if it had a + been touched by the devil. */ + tree type = get_canon_type (TREE_TYPE (t), false, false); + if (!type) return; + + if (lookup_attribute ("used", DECL_ATTRIBUTES (t))) + { + mark_interesting_type (type, FULL_ESCAPE); + return; + } + + /* Do not want to do anything with volatile except mark any + function that uses one to be not const or pure. */ + if (TREE_THIS_VOLATILE (t)) + return; + + /* Do not care about a local automatic that is not static. */ + if (!TREE_STATIC (t) && !DECL_EXTERNAL (t)) + return; + + if (DECL_EXTERNAL (t) || TREE_PUBLIC (t)) + { + /* If the front end set the variable to be READONLY and + constant, we can allow this variable in pure or const + functions but the scope is too large for our analysis to set + these bits ourselves. */ + + if (TREE_READONLY (t) + && DECL_INITIAL (t) + && is_gimple_min_invariant (DECL_INITIAL (t))) + ; /* Read of a constant, do not change the function state. */ + else + { + /* The type escapes for all public and externs. */ + mark_interesting_type (type, FULL_ESCAPE); + } + } +} + +/* If T is a VAR_DECL for a static that we are interested in, add the + uid to the bitmap. */ + +static void +check_operand (tree t) +{ + if (!t) return; + + /* This is an assignment from a function, register the types as + escaping. */ + if (TREE_CODE (t) == FUNCTION_DECL) + check_function_parameter_and_return_types (t, true); + + else if (TREE_CODE (t) == VAR_DECL) + has_proper_scope_for_analysis (t); +} + +/* Examine tree T for references. */ + +static void +check_tree (tree t) +{ + if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)) + return; + + while (TREE_CODE (t) == REALPART_EXPR + || TREE_CODE (t) == IMAGPART_EXPR + || handled_component_p (t)) + { + if (TREE_CODE (t) == ARRAY_REF) + check_operand (TREE_OPERAND (t, 1)); + t = TREE_OPERAND (t, 0); + } + + if (INDIRECT_REF_P (t)) +/* || TREE_CODE (t) == MEM_REF) */ + check_tree (TREE_OPERAND (t, 0)); + + if (SSA_VAR_P (t) || (TREE_CODE (t) == FUNCTION_DECL)) + check_operand (t); +} + +/* Create an address_of edge FROM_TYPE.TO_TYPE. */ +static void +mark_interesting_addressof (tree to_type, tree from_type) +{ + int from_uid; + int to_uid; + bitmap type_map; + splay_tree_node result; + + from_type = get_canon_type (from_type, false, false); + to_type = get_canon_type (to_type, false, false); + + if (!from_type || !to_type) + return; + + from_uid = TYPE_UID (from_type); + to_uid = TYPE_UID (to_type); + + gcc_assert (ipa_type_escape_star_count_of_interesting_type (from_type) == 0); + + /* Process the Y into X map pointer. */ + result = splay_tree_lookup (uid_to_addressof_down_map, + (splay_tree_key) from_uid); + + if (result) + type_map = (bitmap) result->value; + else + { + type_map = BITMAP_ALLOC (&ipa_obstack); + splay_tree_insert (uid_to_addressof_down_map, + from_uid, + (splay_tree_value)type_map); + } + bitmap_set_bit (type_map, TYPE_UID (to_type)); + + /* Process the X into Y reverse map pointer. */ + result = + splay_tree_lookup (uid_to_addressof_up_map, (splay_tree_key) to_uid); + + if (result) + type_map = (bitmap) result->value; + else + { + type_map = BITMAP_ALLOC (&ipa_obstack); + splay_tree_insert (uid_to_addressof_up_map, + to_uid, + (splay_tree_value)type_map); + } + bitmap_set_bit (type_map, TYPE_UID (to_type)); +} + +/* Scan tree T to see if there are any addresses taken in within T. */ + +static void +look_for_address_of (tree t) +{ + if (TREE_CODE (t) == ADDR_EXPR) + { + tree x = get_base_var (t); + tree cref = TREE_OPERAND (t, 0); + + /* If we have an expression of the form "&a.b.c.d", mark a.b, + b.c and c.d. as having its address taken. */ + tree fielddecl = NULL_TREE; + while (cref!= x) + { + if (TREE_CODE (cref) == COMPONENT_REF) + { + fielddecl = TREE_OPERAND (cref, 1); + mark_interesting_addressof (TREE_TYPE (fielddecl), + DECL_FIELD_CONTEXT (fielddecl)); + } + else if (TREE_CODE (cref) == ARRAY_REF) + get_canon_type (TREE_TYPE (cref), false, false); + + cref = TREE_OPERAND (cref, 0); + } + + if (TREE_CODE (x) == VAR_DECL) + has_proper_scope_for_analysis (x); + } +} + + +/* Scan tree T to see if there are any casts within it. + LHS Is the LHS of the expression involving the cast. */ + +static void +look_for_casts (tree lhs __attribute__((unused)), tree t) +{ + if (is_gimple_cast (t) || TREE_CODE (t) == VIEW_CONVERT_EXPR) + { + tree castfromvar = TREE_OPERAND (t, 0); + check_cast (TREE_TYPE (t), castfromvar); + } + else if (TREE_CODE (t) == COMPONENT_REF + || TREE_CODE (t) == INDIRECT_REF + || TREE_CODE (t) == BIT_FIELD_REF) + { + tree base = get_base_address (t); + while (t != base) + { + t = TREE_OPERAND (t, 0); + if (TREE_CODE (t) == VIEW_CONVERT_EXPR) + { + /* This may be some part of a component ref. + IE it may be a.b.VIEW_CONVERT_EXPR<weird_type>(c).d, AFAIK. + castfromref will give you a.b.c, not a. */ + tree castfromref = TREE_OPERAND (t, 0); + check_cast (TREE_TYPE (t), castfromref); + } + else if (TREE_CODE (t) == COMPONENT_REF) + get_canon_type (TREE_TYPE (TREE_OPERAND (t, 1)), false, false); + } + } +} + +/* Check to see if T is a read or address of operation on a static var + we are interested in analyzing. */ + +static void +check_rhs_var (tree t) +{ + look_for_address_of (t); + check_tree(t); +} + +/* Check to see if T is an assignment to a static var we are + interested in analyzing. */ + +static void +check_lhs_var (tree t) +{ + check_tree(t); +} + +/* This is a scaled down version of get_asm_expr_operands from + tree_ssa_operands.c. The version there runs much later and assumes + that aliasing information is already available. Here we are just + trying to find if the set of inputs and outputs contain references + or address of operations to local. FN is the function being + analyzed and STMT is the actual asm statement. */ + +static void +get_asm_expr_operands (tree stmt) +{ + int noutputs = list_length (ASM_OUTPUTS (stmt)); + const char **oconstraints + = (const char **) alloca ((noutputs) * sizeof (const char *)); + int i; + tree link; + const char *constraint; + bool allows_mem, allows_reg, is_inout; + + for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link)) + { + oconstraints[i] = constraint + = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); + parse_output_constraint (&constraint, i, 0, 0, + &allows_mem, &allows_reg, &is_inout); + + check_lhs_var (TREE_VALUE (link)); + } + + for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link)) + { + constraint + = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); + parse_input_constraint (&constraint, 0, 0, noutputs, 0, + oconstraints, &allows_mem, &allows_reg); + + check_rhs_var (TREE_VALUE (link)); + } + + /* There is no code here to check for asm memory clobbers. The + casual maintainer might think that such code would be necessary, + but that appears to be wrong. In other parts of the compiler, + the asm memory clobbers are assumed to only clobber variables + that are addressable. All types with addressable instances are + assumed to already escape. So, we are protected here. */ +} + +/* Check the parameters of a function call to CALL_EXPR to mark the + types that pass across the function boundary. Also check to see if + this is either an indirect call, a call outside the compilation + unit. */ + +static bool +check_call (tree call_expr) +{ + int flags = call_expr_flags(call_expr); + tree operand_list = TREE_OPERAND (call_expr, 1); + tree operand; + tree callee_t = get_callee_fndecl (call_expr); + tree argument; + struct cgraph_node* callee; + enum availability avail = AVAIL_NOT_AVAILABLE; + + for (operand = operand_list; + operand != NULL_TREE; + operand = TREE_CHAIN (operand)) + { + tree argument = TREE_VALUE (operand); + check_rhs_var (argument); + } + + if (callee_t) + { + tree arg_type; + tree last_arg_type = NULL; + callee = cgraph_node(callee_t); + avail = cgraph_function_body_availability (callee); + + /* Check that there are no implicit casts in the passing of + parameters. */ + if (TYPE_ARG_TYPES (TREE_TYPE (callee_t))) + { + operand = operand_list; + for (arg_type = TYPE_ARG_TYPES (TREE_TYPE (callee_t)); + arg_type && TREE_VALUE (arg_type) != void_type_node; + arg_type = TREE_CHAIN (arg_type)) + { + if (operand) + { + argument = TREE_VALUE (operand); + last_arg_type = TREE_VALUE(arg_type); + check_cast (last_arg_type, argument); + operand = TREE_CHAIN (operand); + } + else + /* The code reaches here for some unfortunate + builtin functions that do not have a list of + argument types. */ + break; + } + } + else + { + /* FIXME - According to Geoff Keating, we should never + have to do this; the front ends should always process + the arg list from the TYPE_ARG_LIST. */ + operand = operand_list; + for (arg_type = DECL_ARGUMENTS (callee_t); + arg_type; + arg_type = TREE_CHAIN (arg_type)) + { + if (operand) + { + argument = TREE_VALUE (operand); + last_arg_type = TREE_TYPE(arg_type); + check_cast (last_arg_type, argument); + operand = TREE_CHAIN (operand); + } + else + /* The code reaches here for some unfortunate + builtin functions that do not have a list of + argument types. */ + break; + } + } + + /* In the case where we have a var_args function, we need to + check the remaining parameters against the last argument. */ + arg_type = last_arg_type; + for (; + operand != NULL_TREE; + operand = TREE_CHAIN (operand)) + { + argument = TREE_VALUE (operand); + if (arg_type) + check_cast (arg_type, argument); + else + { + /* The code reaches here for some unfortunate + builtin functions that do not have a list of + argument types. Most of these functions have + been marked as having their parameters not + escape, but for the rest, the type is doomed. */ + tree type = get_canon_type (TREE_TYPE (argument), false, false); + mark_interesting_type (type, FULL_ESCAPE); + } + } + } + + /* The callee is either unknown (indirect call) or there is just no + scannable code for it (external call) . We look to see if there + are any bits available for the callee (such as by declaration or + because it is builtin) and process solely on the basis of those + bits. */ + + if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE) + { + /* If this is a direct call to an external function, mark all of + the parameter and return types. */ + for (operand = operand_list; + operand != NULL_TREE; + operand = TREE_CHAIN (operand)) + { + tree type = + get_canon_type (TREE_TYPE (TREE_VALUE (operand)), false, false); + mark_interesting_type (type, EXPOSED_PARAMETER); + } + + if (callee_t) + { + tree type = + get_canon_type (TREE_TYPE (TREE_TYPE (callee_t)), false, false); + mark_interesting_type (type, EXPOSED_PARAMETER); + } + } + return (flags & ECF_MALLOC); +} + +/* CODE is the operation on OP0 and OP1. OP0 is the operand that we + *know* is a pointer type. OP1 may be a pointer type. */ +static bool +okay_pointer_operation (enum tree_code code, tree op0, tree op1) +{ + tree op0type = TYPE_MAIN_VARIANT (TREE_TYPE (op0)); + tree op1type = TYPE_MAIN_VARIANT (TREE_TYPE (op1)); + if (POINTER_TYPE_P (op1type)) + return false; + switch (code) + { + case MULT_EXPR: + case PLUS_EXPR: + case MINUS_EXPR: + /* TODO: Handle multiples of op0 size as well */ + if (operand_equal_p (size_in_bytes (op0type), op1, 0)) + return true; + /* fallthrough */ + + default: + return false; + } + return false; +} + +/* TP is the part of the tree currently under the microscope. + WALK_SUBTREES is part of the walk_tree api but is unused here. + DATA is cgraph_node of the function being walked. */ + +/* FIXME: When this is converted to run over SSA form, this code + should be converted to use the operand scanner. */ + +static tree +scan_for_refs (tree *tp, int *walk_subtrees, void *data) +{ + struct cgraph_node *fn = data; + tree t = *tp; + + switch (TREE_CODE (t)) + { + case VAR_DECL: + if (DECL_INITIAL (t)) + walk_tree (&DECL_INITIAL (t), scan_for_refs, fn, visited_nodes); + *walk_subtrees = 0; + break; + + case MODIFY_EXPR: + { + /* First look on the lhs and see what variable is stored to */ + tree lhs = TREE_OPERAND (t, 0); + tree rhs = TREE_OPERAND (t, 1); + + check_lhs_var (lhs); + check_cast (TREE_TYPE (lhs), rhs); + + /* For the purposes of figuring out what the cast affects */ + + /* Next check the operands on the rhs to see if they are ok. */ + switch (TREE_CODE_CLASS (TREE_CODE (rhs))) + { + case tcc_binary: + { + tree op0 = TREE_OPERAND (rhs, 0); + tree type0 = get_canon_type (TREE_TYPE (op0), false, false); + tree op1 = TREE_OPERAND (rhs, 1); + tree type1 = get_canon_type (TREE_TYPE (op1), false, false); + + /* If this is pointer arithmetic of any bad sort, then + we need to mark the types as bad. For binary + operations, no binary operator we currently support + is always "safe" in regard to what it would do to + pointers for purposes of determining which types + escape, except operations of the size of the type. + It is possible that min and max under the right set + of circumstances and if the moon is in the correct + place could be safe, but it is hard to see how this + is worth the effort. */ + + if (type0 && POINTER_TYPE_P (type0) + && !okay_pointer_operation (TREE_CODE (rhs), op0, op1)) + mark_interesting_type (type0, FULL_ESCAPE); + if (type1 && POINTER_TYPE_P (type1) + && !okay_pointer_operation (TREE_CODE (rhs), op1, op0)) + mark_interesting_type (type1, FULL_ESCAPE); + + look_for_casts (lhs, op0); + look_for_casts (lhs, op1); + check_rhs_var (op0); + check_rhs_var (op1); + } + break; + case tcc_unary: + { + tree op0 = TREE_OPERAND (rhs, 0); + tree type0 = get_canon_type (TREE_TYPE (op0), false, false); + /* For unary operations, if the operation is NEGATE or + ABS on a pointer, this is also considered pointer + arithmetic and thus, bad for business. */ + if (type0 && (TREE_CODE (op0) == NEGATE_EXPR + || TREE_CODE (op0) == ABS_EXPR) + && POINTER_TYPE_P (type0)) + { + mark_interesting_type (type0, FULL_ESCAPE); + } + check_rhs_var (op0); + look_for_casts (lhs, op0); + look_for_casts (lhs, rhs); + } + + break; + case tcc_reference: + look_for_casts (lhs, rhs); + check_rhs_var (rhs); + break; + case tcc_declaration: + check_rhs_var (rhs); + break; + case tcc_expression: + switch (TREE_CODE (rhs)) + { + case ADDR_EXPR: + look_for_casts (lhs, TREE_OPERAND (rhs, 0)); + check_rhs_var (rhs); + break; + case CALL_EXPR: + /* If this is a call to malloc, squirrel away the + result so we do mark the resulting cast as being + bad. */ + if (check_call (rhs)) + bitmap_set_bit (results_of_malloc, DECL_UID (lhs)); + break; + default: + break; + } + break; + default: + break; + } + *walk_subtrees = 0; + } + break; + + case ADDR_EXPR: + /* This case is here to find addresses on rhs of constructors in + decl_initial of static variables. */ + check_rhs_var (t); + *walk_subtrees = 0; + break; + + case CALL_EXPR: + check_call (t); + *walk_subtrees = 0; + break; + + case ASM_EXPR: + get_asm_expr_operands (t); + *walk_subtrees = 0; + break; + + default: + break; + } + return NULL; +} + + +/* The init routine for analyzing global static variable usage. See + comments at top for description. */ +static void +ipa_init (void) +{ + bitmap_obstack_initialize (&ipa_obstack); + global_types_exposed_parameter = BITMAP_ALLOC (&ipa_obstack); + global_types_full_escape = BITMAP_ALLOC (&ipa_obstack); + global_types_seen = BITMAP_ALLOC (&ipa_obstack); + results_of_malloc = BITMAP_ALLOC (&ipa_obstack); + + uid_to_canon_type = splay_tree_new (splay_tree_compare_ints, 0, 0); + all_canon_types = splay_tree_new (compare_type_brand, 0, 0); + type_to_canon_type = splay_tree_new (splay_tree_compare_pointers, 0, 0); + uid_to_subtype_map = splay_tree_new (splay_tree_compare_ints, 0, 0); + uid_to_addressof_down_map = splay_tree_new (splay_tree_compare_ints, 0, 0); + uid_to_addressof_up_map = splay_tree_new (splay_tree_compare_ints, 0, 0); + + /* There are some shared nodes, in particular the initializers on + static declarations. We do not need to scan them more than once + since all we would be interested in are the addressof + operations. */ + visited_nodes = pointer_set_create (); + initialized = true; +} + +/* Check out the rhs of a static or global initialization VNODE to see + if any of them contain addressof operations. Note that some of + these variables may not even be referenced in the code in this + compilation unit but their right hand sides may contain references + to variables defined within this unit. */ + +static void +analyze_variable (struct cgraph_varpool_node *vnode) +{ + tree global = vnode->decl; + tree type = get_canon_type (TREE_TYPE (global), false, false); + + /* If this variable has exposure beyond the compilation unit, add + its type to the global types. */ + + if (vnode->externally_visible) + mark_interesting_type (type, FULL_ESCAPE); + + gcc_assert (TREE_CODE (global) == VAR_DECL); + + if (DECL_INITIAL (global)) + walk_tree (&DECL_INITIAL (global), scan_for_refs, NULL, visited_nodes); +} + +/* This is the main routine for finding the reference patterns for + global variables within a function FN. */ + +static void +analyze_function (struct cgraph_node *fn) +{ + tree decl = fn->decl; + check_function_parameter_and_return_types (decl, + fn->local.externally_visible); + if (dump_file) + fprintf (dump_file, "\n local analysis of %s", cgraph_node_name (fn)); + + { + struct function *this_cfun = DECL_STRUCT_FUNCTION (decl); + basic_block this_block; + + FOR_EACH_BB_FN (this_block, this_cfun) + { + block_stmt_iterator bsi; + for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi)) + walk_tree (bsi_stmt_ptr (bsi), scan_for_refs, + fn, visited_nodes); + } + } + + /* There may be const decls with interesting right hand sides. */ + if (DECL_STRUCT_FUNCTION (decl)) + { + tree step; + for (step = DECL_STRUCT_FUNCTION (decl)->unexpanded_var_list; + step; + step = TREE_CHAIN (step)) + { + tree var = TREE_VALUE (step); + if (TREE_CODE (var) == VAR_DECL + && DECL_INITIAL (var) + && !TREE_STATIC (var)) + walk_tree (&DECL_INITIAL (var), scan_for_refs, + fn, visited_nodes); + get_canon_type (TREE_TYPE (var), false, false); + } + } +} + + + +/* Convert a type_UID into a type. */ +static tree +type_for_uid (int uid) +{ + splay_tree_node result = + splay_tree_lookup (uid_to_canon_type, (splay_tree_key) uid); + + if (result) + return (tree) result->value; + else return NULL; +} + +/* Return the a bitmap with the subtypes of the type for UID. If it + does not exist, return either NULL or a new bitmap depending on the + value of CREATE. */ + +static bitmap +subtype_map_for_uid (int uid, bool create) +{ + splay_tree_node result = splay_tree_lookup (uid_to_subtype_map, + (splay_tree_key) uid); + + if (result) + return (bitmap) result->value; + else if (create) + { + bitmap subtype_map = BITMAP_ALLOC (&ipa_obstack); + splay_tree_insert (uid_to_subtype_map, + uid, + (splay_tree_value)subtype_map); + return subtype_map; + } + else return NULL; +} + +/* Mark all of the supertypes and field types of TYPE as being seen. + Also accumulate the subtypes for each type so that + close_types_full_escape can mark a subtype as escaping if the + supertype escapes. */ + +static void +close_type_seen (tree type) +{ + tree field; + int i, uid; + tree binfo, base_binfo; + + /* See thru all pointer tos and array ofs. */ + type = get_canon_type (type, true, true); + if (!type) + return; + + uid = TYPE_UID (type); + + if (bitmap_bit_p (been_there_done_that, uid)) + return; + bitmap_set_bit (been_there_done_that, uid); + + /* If we are doing a language with a type hierarchy, mark all of + the superclasses. */ + if (TYPE_BINFO (type)) + for (binfo = TYPE_BINFO (type), i = 0; + BINFO_BASE_ITERATE (binfo, i, base_binfo); i++) + { + tree binfo_type = BINFO_TYPE (base_binfo); + bitmap subtype_map = subtype_map_for_uid + (TYPE_UID (TYPE_MAIN_VARIANT (binfo_type)), true); + bitmap_set_bit (subtype_map, uid); + close_type_seen (get_canon_type (binfo_type, true, true)); + } + + /* If the field is a struct or union type, mark all of the + subfields. */ + for (field = TYPE_FIELDS (type); + field; + field = TREE_CHAIN (field)) + { + tree field_type; + if (TREE_CODE (field) != FIELD_DECL) + continue; + + field_type = TREE_TYPE (field); + if (ipa_type_escape_star_count_of_interesting_or_array_type (field_type) >= 0) + close_type_seen (get_canon_type (field_type, true, true)); + } +} + +/* Take a TYPE that has been passed by value to an external function + and mark all of the fields that have pointer types as escaping. For + any of the non pointer types that are structures or unions, + recurse. TYPE is never a pointer type. */ + +static void +close_type_exposed_parameter (tree type) +{ + tree field; + int uid; + + type = get_canon_type (type, false, false); + if (!type) + return; + uid = TYPE_UID (type); + gcc_assert (!POINTER_TYPE_P (type)); + + if (bitmap_bit_p (been_there_done_that, uid)) + return; + bitmap_set_bit (been_there_done_that, uid); + + /* If the field is a struct or union type, mark all of the + subfields. */ + for (field = TYPE_FIELDS (type); + field; + field = TREE_CHAIN (field)) + { + tree field_type; + + if (TREE_CODE (field) != FIELD_DECL) + continue; + + field_type = get_canon_type (TREE_TYPE (field), false, false); + mark_interesting_type (field_type, EXPOSED_PARAMETER); + + /* Only recurse for non pointer types of structures and unions. */ + if (ipa_type_escape_star_count_of_interesting_type (field_type) == 0) + close_type_exposed_parameter (field_type); + } +} + +/* The next function handles the case where a type fully escapes. + This means that not only does the type itself escape, + + a) the type of every field recursively escapes + b) the type of every subtype escapes as well as the super as well + as all of the pointer to types for each field. + + Note that pointer to types are not marked as escaping. If the + pointed to type escapes, the pointer to type also escapes. + + Take a TYPE that has had the address taken for an instance of it + and mark all of the types for its fields as having their addresses + taken. */ + +static void +close_type_full_escape (tree type) +{ + tree field; + unsigned int i; + int uid; + tree binfo, base_binfo; + bitmap_iterator bi; + bitmap subtype_map; + splay_tree_node address_result; + + /* Strip off any pointer or array types. */ + type = get_canon_type (type, true, true); + if (!type) + return; + uid = TYPE_UID (type); + + if (bitmap_bit_p (been_there_done_that, uid)) + return; + bitmap_set_bit (been_there_done_that, uid); + + subtype_map = subtype_map_for_uid (uid, false); + + /* If we are doing a language with a type hierarchy, mark all of + the superclasses. */ + if (TYPE_BINFO (type)) + for (binfo = TYPE_BINFO (type), i = 0; + BINFO_BASE_ITERATE (binfo, i, base_binfo); i++) + { + tree binfotype = BINFO_TYPE (base_binfo); + binfotype = mark_type (binfotype, FULL_ESCAPE); + close_type_full_escape (binfotype); + } + + /* Mark as escaped any types that have been down casted to + this type. */ + if (subtype_map) + EXECUTE_IF_SET_IN_BITMAP (subtype_map, 0, i, bi) + { + tree subtype = type_for_uid (i); + subtype = mark_type (subtype, FULL_ESCAPE); + close_type_full_escape (subtype); + } + + /* If the field is a struct or union type, mark all of the + subfields. */ + for (field = TYPE_FIELDS (type); + field; + field = TREE_CHAIN (field)) + { + tree field_type; + if (TREE_CODE (field) != FIELD_DECL) + continue; + + field_type = TREE_TYPE (field); + if (ipa_type_escape_star_count_of_interesting_or_array_type (field_type) >= 0) + { + field_type = mark_type (field_type, FULL_ESCAPE); + close_type_full_escape (field_type); + } + } + + /* For all of the types A that contain this type B and were part of + an expression like "&...A.B...", mark the A's as escaping. */ + address_result = splay_tree_lookup (uid_to_addressof_up_map, + (splay_tree_key) uid); + if (address_result) + { + bitmap containing_classes = (bitmap) address_result->value; + EXECUTE_IF_SET_IN_BITMAP (containing_classes, 0, i, bi) + { + close_type_full_escape (type_for_uid (i)); + } + } +} + +/* Transitively close the addressof bitmap for the type with UID. + This means that if we had a.b and b.c, a would have both b and c in + its maps. */ + +static bitmap +close_addressof_down (int uid) +{ + bitmap_iterator bi; + splay_tree_node result = + splay_tree_lookup (uid_to_addressof_down_map, (splay_tree_key) uid); + bitmap map = NULL; + bitmap new_map; + unsigned int i; + + if (result) + map = (bitmap) result->value; + else + return NULL; + + if (bitmap_bit_p (been_there_done_that, uid)) + return map; + bitmap_set_bit (been_there_done_that, uid); + + /* If the type escapes, get rid of the addressof map, it will not be + needed. */ + if (bitmap_bit_p (global_types_full_escape, uid)) + { + BITMAP_FREE (map); + splay_tree_remove (uid_to_addressof_down_map, (splay_tree_key) uid); + return NULL; + } + + /* The new_map will have all of the bits for the enclosed fields and + will have the unique id version of the old map. */ + new_map = BITMAP_ALLOC (&ipa_obstack); + + EXECUTE_IF_SET_IN_BITMAP (map, 0, i, bi) + { + bitmap submap = close_addressof_down (i); + bitmap_set_bit (new_map, i); + if (submap) + bitmap_ior_into (new_map, submap); + } + result->value = (splay_tree_value) new_map; + + BITMAP_FREE (map); + return new_map; +} + + +/* The main entry point for type escape analysis. */ + +static unsigned int +type_escape_execute (void) +{ + struct cgraph_node *node; + struct cgraph_varpool_node *vnode; + unsigned int i; + bitmap_iterator bi; + splay_tree_node result; + + ipa_init (); + + /* Process all of the variables first. */ + for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed) + analyze_variable (vnode); + + /* Process all of the functions. next + + We do not want to process any of the clones so we check that this + is a master clone. However, we do need to process any + AVAIL_OVERWRITABLE functions (these are never clones) because + they may cause a type variable to escape. + */ + for (node = cgraph_nodes; node; node = node->next) + if (node->analyzed + && (cgraph_is_master_clone (node) + || (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE))) + analyze_function (node); + + + pointer_set_destroy (visited_nodes); + visited_nodes = NULL; + + /* Do all of the closures to discover which types escape the + compilation unit. */ + + been_there_done_that = BITMAP_ALLOC (&ipa_obstack); + bitmap_tmp = BITMAP_ALLOC (&ipa_obstack); + + /* Examine the types that we have directly seen in scanning the code + and add to that any contained types or superclasses. */ + + bitmap_copy (bitmap_tmp, global_types_seen); + EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi) + { + tree type = type_for_uid (i); + /* Only look at records and unions and pointer tos. */ + if (ipa_type_escape_star_count_of_interesting_or_array_type (type) >= 0) + close_type_seen (type); + } + bitmap_clear (been_there_done_that); + + /* Examine all of the types passed by value and mark any enclosed + pointer types as escaping. */ + bitmap_copy (bitmap_tmp, global_types_exposed_parameter); + EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi) + { + close_type_exposed_parameter (type_for_uid (i)); + } + bitmap_clear (been_there_done_that); + + /* Close the types for escape. If something escapes, then any + enclosed types escape as well as any subtypes. */ + bitmap_copy (bitmap_tmp, global_types_full_escape); + EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi) + { + close_type_full_escape (type_for_uid (i)); + } + bitmap_clear (been_there_done_that); + + /* Before this pass, the uid_to_addressof_down_map for type X + contained an entry for Y if there had been an operation of the + form &X.Y. This step adds all of the fields contained within Y + (recursively) to X's map. */ + + result = splay_tree_min (uid_to_addressof_down_map); + while (result) + { + int uid = result->key; + /* Close the addressof map, i.e. copy all of the transitive + substructures up to this level. */ + close_addressof_down (uid); + result = splay_tree_successor (uid_to_addressof_down_map, uid); + } + + /* Do not need the array types and pointer types in the persistent + data structures. */ + result = splay_tree_min (all_canon_types); + while (result) + { + tree type = (tree) result->value; + tree key = (tree) result->key; + if (POINTER_TYPE_P (type) + || TREE_CODE (type) == ARRAY_TYPE) + { + splay_tree_remove (all_canon_types, (splay_tree_key) result->key); + splay_tree_remove (type_to_canon_type, (splay_tree_key) type); + splay_tree_remove (uid_to_canon_type, (splay_tree_key) TYPE_UID (type)); + bitmap_clear_bit (global_types_seen, TYPE_UID (type)); + } + result = splay_tree_successor (all_canon_types, (splay_tree_key) key); + } + + if (dump_file) + { + EXECUTE_IF_SET_IN_BITMAP (global_types_seen, 0, i, bi) + { + /* The pointer types are in the global_types_full_escape + bitmap but not in the backwards map. They also contain + no useful information since they are not marked. */ + tree type = type_for_uid (i); + fprintf(dump_file, "type %d ", i); + print_generic_expr (dump_file, type, 0); + if (bitmap_bit_p (global_types_full_escape, i)) + fprintf(dump_file, " escaped\n"); + else + fprintf(dump_file, " contained\n"); + } + } + + /* Get rid of uid_to_addressof_up_map and its bitmaps. */ + result = splay_tree_min (uid_to_addressof_up_map); + while (result) + { + int uid = (int)result->key; + bitmap bm = (bitmap)result->value; + + BITMAP_FREE (bm); + splay_tree_remove (uid_to_addressof_up_map, (splay_tree_key) uid); + result = splay_tree_successor (uid_to_addressof_up_map, uid); + } + + /* Get rid of the subtype map. */ + result = splay_tree_min (uid_to_subtype_map); + while (result) + { + bitmap b = (bitmap)result->value; + BITMAP_FREE(b); + splay_tree_remove (uid_to_subtype_map, result->key); + result = splay_tree_min (uid_to_subtype_map); + } + splay_tree_delete (uid_to_subtype_map); + uid_to_subtype_map = NULL; + + BITMAP_FREE (global_types_exposed_parameter); + BITMAP_FREE (been_there_done_that); + BITMAP_FREE (bitmap_tmp); + BITMAP_FREE (results_of_malloc); + return 0; +} + +static bool +gate_type_escape_vars (void) +{ + return (flag_unit_at_a_time != 0 && flag_ipa_type_escape + /* Don't bother doing anything if the program has errors. */ + && !(errorcount || sorrycount)); +} + +struct tree_opt_pass pass_ipa_type_escape = +{ + "type-escape-var", /* name */ + gate_type_escape_vars, /* gate */ + type_escape_execute, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_IPA_TYPE_ESCAPE, /* tv_id */ + 0, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0, /* todo_flags_finish */ + 0 /* letter */ +}; + |