On Fri, Dec 4, 2020 at 4:58 AM Erick Ochoa < erick.oc...@theobroma-systems.com> wrote:
> > This commit includes the following components: > > Type-based escape analysis to determine structs that can be modified at > link-time. > Field access analysis to determine which fields are never read. > > The type-based escape analysis provides a list of types, that are not > visible outside of the current linking unit (e.g. parameter types of > external > functions). > > The field access analyses non-escaping structs for fields that > are not used in the linking unit and thus can be removed. > > 2020-11-04 Erick Ochoa <erick.oc...@theobroma-systems.com> > > * Makefile.in: Add file to list of new sources. > * common.opt: Add new flags. > * ipa-type-escape-analysis.c: New file. > --- > gcc/Makefile.in | 1 + > gcc/common.opt | 8 + > gcc/ipa-type-escape-analysis.c | 3428 ++++++++++++++++++++++++++++++++ > gcc/ipa-type-escape-analysis.h | 1152 +++++++++++ > gcc/passes.def | 1 + > gcc/timevar.def | 1 + > gcc/tree-pass.h | 2 + > 7 files changed, 4593 insertions(+) > create mode 100644 gcc/ipa-type-escape-analysis.c > create mode 100644 gcc/ipa-type-escape-analysis.h > > diff --git a/gcc/Makefile.in b/gcc/Makefile.in > index 978a08f7b04..8b18c9217a2 100644 > --- a/gcc/Makefile.in > +++ b/gcc/Makefile.in > @@ -1415,6 +1415,7 @@ OBJS = \ > incpath.o \ > init-regs.o \ > internal-fn.o \ > + ipa-type-escape-analysis.o \ > ipa-cp.o \ > ipa-sra.o \ > ipa-devirt.o \ > diff --git a/gcc/common.opt b/gcc/common.opt > index d4cbb2f86a5..85351738a29 100644 > --- a/gcc/common.opt > +++ b/gcc/common.opt > @@ -3460,4 +3460,12 @@ fipa-ra > Common Report Var(flag_ipa_ra) Optimization > Use caller save register across calls if possible. > +fipa-type-escape-analysis > +Common Report Var(flag_ipa_type_escape_analysis) Optimization > +This flag is only used for debugging the type escape analysis > + > +Wdfa > +Common Var(warn_dfa) Init(1) Warning > +Warn about dead fields at link time. > + > I don't really like the name "-Wdfa" very much; could you maybe come up with a longer and more descriptive name instead? Say, "-Wunused-field" or "-Wunused-private-field" depending on the kind of field: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=72789 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92801 > ; This comment is to ensure we retain the blank line above. > diff --git a/gcc/ipa-type-escape-analysis.c > b/gcc/ipa-type-escape-analysis.c > new file mode 100644 > index 00000000000..32c8bf997fb > --- /dev/null > +++ b/gcc/ipa-type-escape-analysis.c > @@ -0,0 +1,3428 @@ > +/* IPA Type Escape Analysis and Dead Field Elimination > + Copyright (C) 2019-2020 Free Software Foundation, Inc. > + > + Contributed by Erick Ochoa <erick.oc...@theobroma-systems.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 3, 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 COPYING3. If not see > +<http://www.gnu.org/licenses/>. */ > + > +/* Interprocedural dead field analysis (IPA-DFA) > + > + The goal of this analysis is to > + > + 1) discover RECORD_TYPEs which do not escape the current linking unit. > + > + 2) discover fields in RECORD_TYPEs that are never read. > + > + 3) merge the results from 1 and 2 to determine which fields are not > needed. > + > + The algorithm basically consists of the following stages: > + > + 1) Partition all TYPE_P trees into two sets: those trees which reach a > + tree of RECORD_TYPE. > + > + 2.a) Analyze callsites to determine if arguments and return types are > + escaping. > + 2.b) Analyze casts to determine if it would be safe to mark a field > as dead. > + 2.c) Analyze for constructors and static initialization and mark this > as > + TYPE_P trees as unable to be modified > + 2.d) Analyze if FIELD_DECL are accessed via pointer arithmetic and mark > + FIELD_DECLs before as unable to be modified. > + 2.e) Analyze if an address of a FIELD_DECL is taken and mark the whole > + RECORD_TYPE as unable to be modified. > + 2.f) Propagate this information to nested TYPE_P trees. > + 2.g) Propagate this information across different TYPE_P trees that > represent > + equivalent TYPE_P types. > + > + 3.a) Analyze FIELD_DECL to determine whether they are read, > + written or neither. > + 3.b) Unify this information across different RECORD_TYPE trees that > + represent equivalent types > + 3.c) Determine which FIELD_DECL can be deleted. > + > + 4) Calculate the intersection of non-escaping RECORD_TYPEs with > RECORD_TYPEs > + that have a field that can be deleted. > + > + First stage - Determining if a TYPE_P points to a RECORD_TYPE > + ============================================================= > + > + This stage is computed through the *Collector classes. Those are > + TypeCollector, ExprCollector and GimpleTypeCollector which walk up > and down > + types, expressions, and gimple respectively and propagate > information about > + TYPE_P trees and mantain information on the type partitions. > + > + Second stage - Determining if a TYPE_P escapes > + ============================================== > + > + This stage is computed through the *Escaper classes. Those are > + TypeEscaper, ExprEscaper, GimpleEscaper, GimpleCaster classes. These > + classes walk up and down types, expressions and gimple respectively and > + propagate reasons why a TYPE_P tree might be escaping. > + Reasons are always ORed and equivalent TYPE_P trees might hold > different > + results up to when equivalence is computed for all TYPE_P trees and > reasons > + are propagated until a fixedpoint is achieved. > + > + Third stage - Calculating FIELD_DECL accesses > + ============================================= > + > + This stage is computed through the *Accessor classes. Those are > + TypeAccessor, ExprAccessor, and GimpleAccessor. These classes walk > up and > + down TYPE_P, expressions, and gimple respectively and propagate access > + information. If an expression occurs in the LHS, it is marked as > written > + and if it occurs on the RHS, it is marked as read. Special cases where > + addresses of a FIELD_DECLs are taken mark all FIELD_DECL in a > RECORD_TYPE > + as read. > + > + Fourth stage - Intersection of accesses and non_escaping > + ======================================================== > + > + This stage happens in the function > obtain_unescaped_and_unaccessed_fields. > + First all FIELD_DECLs are translated to their respective field offset. > + Then all field offsets for FIELD_DECLs which are READ are stored > + in a set. We then compute the complement of this set and these are the > + offsets of FIELD_DECLs which are never read. > + > + Offsets are needed if we are to find dead fields for anonymous fields. > +*/ > + > + > +#include <vector> > +#include <set> > +#include <map> > +#include <stack> > +#include <string> > + > +#include "config.h" > +#include "system.h" > +#include "coretypes.h" > +#include "backend.h" > +#include "tree.h" > +#include "gimple-expr.h" > +#include "predict.h" > +#include "alloc-pool.h" > +#include "tree-pass.h" > +#include "cgraph.h" > +#include "diagnostic.h" > +#include "fold-const.h" > +#include "gimple-fold.h" > +#include "symbol-summary.h" > +#include "tree-vrp.h" > +#include "ipa-prop.h" > +#include "tree-pretty-print.h" > +#include "tree-inline.h" > +#include "ipa-fnsummary.h" > +#include "ipa-utils.h" > +#include "tree-ssa-ccp.h" > +#include "stringpool.h" > +#include "attribs.h" > +#include "basic-block.h" //needed for gimple.h > +#include "function.h" //needed for gimple.h > +#include "gimple.h" > +#include "stor-layout.h" > +#include "cfg.h" // needed for gimple-iterator.h > +#include "gimple-iterator.h" > +#include "gimplify.h" //unshare_expr > +#include "value-range.h" // make_ssa_name dependency > +#include "tree-ssanames.h" // make_ssa_name > +#include "ssa.h" > +#include "tree-into-ssa.h" > +#include "gimple-ssa.h" // update_stmt > +#include "tree.h" > +#include "gimple-expr.h" > +#include "predict.h" > +#include "alloc-pool.h" > +#include "tree-pass.h" > +#include "cgraph.h" > +#include "diagnostic.h" > +#include "fold-const.h" > +#include "gimple-fold.h" > +#include "symbol-summary.h" > +#include "tree-vrp.h" > +#include "ipa-prop.h" > +#include "tree-pretty-print.h" > +#include "tree-inline.h" > +#include "ipa-fnsummary.h" > +#include "ipa-utils.h" > +#include "tree-ssa-ccp.h" > +#include "stringpool.h" > +#include "attribs.h" > +#include "tree-ssa-alias.h" > +#include "tree-ssanames.h" > +#include "gimple.h" > +#include "cfg.h" > +#include "gimple-iterator.h" > +#include "gimple-ssa.h" > +#include "gimple-pretty-print.h" > + > +#include "ipa-type-escape-analysis.h" > + > +// Main function that drives dfe. > +static unsigned int > +lto_dfe_execute (); > + > +// Partition types into reching record or non reaching record sets. > +static tpartitions_t > +partition_types_into_record_reaching_or_non_record_reaching (); > + > +// Partition types into escaping or non escaping sets. > +static tpartitions_t > +partition_types_into_escaping_nonescaping (); > + > +// Perform dead field elimination. > +static void > +lto_dead_field_elimination (); > + > +// Fixed point calculating to determine escaping types. > +static void > +fix_escaping_types_in_set (tpartitions_t &types); > + > +// Find which fields are accessed. > +static record_field_map_t > +find_fields_accessed (); > + > +// Obtain intersection of unaccessed and non escaping types. > +static record_field_offset_map_t > +obtain_nonescaping_unaccessed_fields (tpartitions_t casting, > + record_field_map_t record_field_map); > + > +// TODO: > +// This was copy pasted from tree-ssa-structalias.c > +// Maybe delete this and make the function visible? > +static HOST_WIDE_INT > +bitpos_of_field (const tree fdecl) > +{ > + if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl)) > + || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl))) > + return -1; > + > + return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl)) * BITS_PER_UNIT > + + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl))); > +} > + > +/* There are some cases where I need to change a tree to a tree. > + * Some of these are part of the way the API is written. To avoid > + * warnings, always use this function for casting away const-ness. > + */ > +inline static tree > +tree_to_tree (tree t) > +{ > + return (tree) t; > +} > + > +namespace { > +const pass_data pass_data_ipa_type_escape_analysis = { > + SIMPLE_IPA_PASS, > + "type-escape-analysis", > + OPTGROUP_NONE, > + TV_NONE, > + (PROP_cfg | PROP_ssa), > + 0, > + 0, > + 0, > + 0, > +}; > + > +class pass_ipa_type_escape_analysis : public simple_ipa_opt_pass > +{ > +public: > + pass_ipa_type_escape_analysis (gcc::context *ctx) > + : simple_ipa_opt_pass (pass_data_ipa_type_escape_analysis, ctx) > + {} > + > + virtual bool gate (function *) > + { > + return in_lto_p && flag_ipa_type_escape_analysis; > + } > + virtual unsigned execute (function *) > + { > + return lto_dfe_execute (); > + } > +}; > +} // namespace > + > +/* Top level function. */ > +static unsigned int > +lto_dfe_execute () > +{ > + lto_dead_field_elimination (); > + log ("finished!\n"); > + return 0; > +} > + > +/* > + * Perform dead field elimination at link-time. > + * This transformation is composed of two main stages: > + * * Finding out which fields are non escaping and unaccessed. > + * * Creating new types and substituting their mention throughout the > + * program. > + */ > +static void > +lto_dead_field_elimination () > +{ > + // Analysis. > + cgraph_node *cnode = NULL; > + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cnode) > + { > + if (cnode->inlined_to) continue; > + cnode->get_body(); > + } > + tpartitions_t escaping_nonescaping_sets > + = partition_types_into_escaping_nonescaping (); > + record_field_map_t record_field_map = find_fields_accessed (); > + record_field_offset_map_t record_field_offset_map > + = obtain_nonescaping_unaccessed_fields (escaping_nonescaping_sets, > + record_field_map); > + if (record_field_offset_map.empty ()) > + return; > + > +} > + > +/* Iterate all gimple bodies and collect trees > + * which are themselves RECORD_TYPE or which > + * somehow reach a RECORD_TYPE tree (e.g., via a > + * pointer, array, reference, union, field, etc...). > + * Let's call these trees record_reaching_trees. > + */ > +static tpartitions_t > +partition_types_into_record_reaching_or_non_record_reaching () > +{ > + gimple_type_collector collector; > + collector.walk (); > + tpartitions_t partitions = collector.get_record_reaching_trees (); > + return partitions; > +} > + > +/* Iterate over all gimple bodies and find out > + * which types are escaping AND are being casted. > + */ > +static tpartitions_t > +partition_types_into_escaping_nonescaping () > +{ > + tpartitions_t partitions > + = partition_types_into_record_reaching_or_non_record_reaching (); > + gimple_caster caster (partitions); > + caster.walk (); > + caster.print_reasons (); > + > + partitions = caster.get_sets (); > + // Unify results from different trees representing the same type > + // until a fixed point is reached. > + fix_escaping_types_in_set (partitions); > + return partitions; > +} > + > +/* Iterate over all gimple bodies and find out > + * which fields are accessed for all RECORD_TYPE > + * types. > + */ > +static record_field_map_t > +find_fields_accessed () > +{ > + gimple_accessor accesser; > + accesser.walk (); > + > + // This record_field_map holds > + // RECORD_TYPE -> (FIELD_DECL -> how field is accessed) > + record_field_map_t record_field_map = accesser.get_map (); > + return record_field_map; > +} > + > +/* Find equivalent RECORD_TYPE trees to tree r_i. > + * This equivalence will be used for merging the results of field accesses > + * across all equivalent RECORD_TYPE trees. > + > + * r_i should exists in the points_to_record set > + * and it is a tree for which this method is going to find the rest of > + * equivalent trees found in record_field_map. > + */ > +static std::vector<tree> > +find_equivalent_trees (tree r_i, record_field_map_t record_field_map, > + tpartitions_t casting) > +{ > + type_incomplete_equality equality; > + std::vector<tree> equivalence; > + bool is_rin_record = casting.in_points_to_record (r_i); > + if (!is_rin_record) > + return equivalence; > + > + for (std::map<tree, field_access_map_t>::const_iterator j > + = record_field_map.begin (), > + f = record_field_map.end (); > + j != f; j++) > + { > + tree r_j = j->first; > + const bool pointer_equal = r_i == r_j; > + if (pointer_equal) > + continue; > + > + bool is_p_record = casting.in_points_to_record (r_i) > + && casting.in_points_to_record (r_j); > + if (!is_p_record) > + continue; > + > + const bool are_equal = equality.equal (r_i, r_j); > + if (!are_equal) > + continue; > + > + equivalence.push_back (r_j); > + } > + return equivalence; > +} > + > +/* > + * FIELD is a FIELD_DECL tree, ACCESSED is a a bitflag that marks > whether the > + * field is read, written or neither. FIELD_OFFSET will hold the > following map: > + * tree (RECORD_TYPE) -> unsigned (bitpos_of_field for read fields). > + */ > +static void > +add_offset_only_if_read (tree field, unsigned access, > + field_offsets_t &field_offset) > +{ > + assert_is_type (field, FIELD_DECL); > + const bool is_read = access & Read; > + if (!is_read) > + return; > + > + tree _field = tree_to_tree (field); > + unsigned f_offset = bitpos_of_field (_field); > + field_offset.insert (f_offset); > +} > + > +/* > + * FIELD_MAP holds the following map: > + * tree (FIELD_DECL) -> access type > + * FIELD_OFFSET is being built here. > + * It should hold > + * tree (RECORD_TYPE) -> bitpos_of_field for read fields). > + */ > +static void > +keep_only_read_fields_from_field_map (field_access_map_t &field_map, > + field_offsets_t &field_offset) > +{ > + for (std::map<tree, unsigned>::iterator j = field_map.begin (), > + f = field_map.end (); > + j != f; ++j) > + { > + add_offset_only_if_read (j->first, j->second, field_offset); > + } > +} > + > +/* > + * EQUIVALENT holds equivalent trees of RECORD_TYPE > + * Update FIELD_OFFSET as the union of all READ FIELDS for the > equivalent trees. > + */ > +static void > +keep_only_read_fields_from_equivalent_field_maps ( > + std::vector<tree> equivalent, record_field_map_t &record_field_map, > + field_offsets_t &field_offset) > +{ > + for (std::vector<tree>::iterator j = equivalent.begin (), > + f = equivalent.end (); > + j != f; j++) > + { > + tree r_j = *j; > + field_access_map_t equivalent_field_map = record_field_map[r_j]; > + keep_only_read_fields_from_field_map (equivalent_field_map, > field_offset); > + } > +} > + > +/* > + * Whether RECORDS are escaping or can't be modified, > + * delete them from the set of candidate RECORDS to be modified. > + */ > +static void > +erase_if_no_fields_can_be_deleted ( > + record_field_offset_map_t &record_field_offset_map, > + std::set<tree> &to_keep, std::set<tree> &to_erase) > +{ > + for (std::map<tree, field_offsets_t>::iterator i > + = record_field_offset_map.begin (), > + e = record_field_offset_map.end (); > + i != e; ++i) > + { > + tree record = i->first; > + const bool keep = to_keep.find (record) != to_keep.end (); > + if (keep) > + continue; > + > + to_erase.insert (record); > + } > + > + for (std::set<tree>::iterator i = to_erase.begin (), > + e = to_erase.end (); > + i != e; ++i) > + { > + tree record = *i; > + record_field_offset_map.erase (record); > + } > +} > + > +/* > + * Mark escaping RECORD_TYPEs as ready to be deleted from the > + * set of candidates to be modified. > + */ > +static void > +mark_escaping_types_to_be_deleted ( > + record_field_offset_map_t &record_field_offset_map, > + std::set<tree> &to_erase, tpartitions_t casting) > +{ > + const tset_t &non_escaping = casting.non_escaping; > + for (std::map<tree, field_offsets_t>::iterator i > + = record_field_offset_map.begin (), > + e = record_field_offset_map.end (); > + i != e; ++i) > + { > + tree record = i->first; > + const bool in_set = non_escaping.find (record) != > non_escaping.end (); > + if (in_set) > + continue; > + > + to_erase.insert (record); > + } > +} > + > +// Obtain nonescaping unaccessed fields > +static record_field_offset_map_t > +obtain_nonescaping_unaccessed_fields (tpartitions_t casting, > + record_field_map_t record_field_map) > +{ > + bool has_fields_that_can_be_deleted = false; > + record_field_offset_map_t record_field_offset_map; > + for (std::map<tree, field_access_map_t>::iterator i > + = record_field_map.begin (), > + e = record_field_map.end (); > + i != e; ++i) > + { > + tree r_i = i->first; > + std::vector<tree> equivalence > + = find_equivalent_trees (r_i, record_field_map, casting); > + field_offsets_t field_offset; > + field_access_map_t original_field_map = record_field_map[r_i]; > + keep_only_read_fields_from_field_map (original_field_map, > field_offset); > + keep_only_read_fields_from_equivalent_field_maps (equivalence, > + record_field_map, > + field_offset); > + // These map holds the following: > + // RECORD_TYPE -> unsigned (bit_pos_offset which has been read) > + record_field_offset_map[r_i] = field_offset; > + } > + > + // So now that we only have the FIELDS which are read, > + // we need to compute the complement... > + > + // Improve: This is tightly coupled, I need to decouple it... > + std::set<tree> to_erase; > + std::set<tree> to_keep; > + mark_escaping_types_to_be_deleted (record_field_offset_map, to_erase, > + casting); > + for (std::map<tree, field_offsets_t>::iterator i > + = record_field_offset_map.begin (), > + e = record_field_offset_map.end (); > + i != e; ++i) > + { > + tree record = i->first; > + const bool will_be_erased = to_erase.find (record) != > to_erase.end (); > + // No need to compute which fields can be deleted if type is > escaping > + if (will_be_erased) > + continue; > + > + field_offsets_t field_offset = i->second; > + for (tree field = TYPE_FIELDS (record); field; field = DECL_CHAIN > (field)) > + { > + unsigned f_offset = bitpos_of_field (field); > + bool in_set2 = field_offset.find (f_offset) != field_offset.end > (); > + if (in_set2) > + { > + field_offset.erase (f_offset); > + continue; > + } > + to_keep.insert (record); > + field_offset.insert (f_offset); > + has_fields_that_can_be_deleted = true; > + // NOTE: With anonymous fields this might be weird to print. > + log ("%s.%s may be deleted\n", > + type_stringifier::get_type_identifier (record).c_str (), > + type_stringifier::get_field_identifier (field).c_str ()); > + > + if (OPT_Wdfa == 0) continue; > + // Anonymous fields? (Which the record can be!). > + warning (OPT_Wdfa, "RECORD_TYPE %qE has dead field %qE in > LTO.\n", > + record, field); > + } > + record_field_offset_map[record] = field_offset; > + } > + > + // Improve: Make this more elegant. > + if (!has_fields_that_can_be_deleted) > + { > + record_field_offset_map_t empty; > + return empty; > + } > + > + erase_if_no_fields_can_be_deleted (record_field_offset_map, to_keep, > + to_erase); > + > + return record_field_offset_map; > +} > + > +// Main interface to TypeWalker > +// Start recursive walk > +void > +type_walker::walk (tree t) > +{ > + gcc_assert (t); > + this->tset.clear (); > + this->_walk (t); > +} > + > +void > +type_walker::_walk (tree type) > +{ > + // Improve, verify that having a type is an invariant. > + // I think there was a specific example which didn't > + // allow for it > + if (!type) > + return; > + > + gcc_assert (type); > + > + // This is an optimization. > + const bool _is_memoized = is_memoized (type); > + if (_is_memoized) > + return; > + > + // This is for correctness > + // Some types are represented as a graph > + // of trees and therefore we need a way to > + // avoid loops in this graph. > + // Imrpove: Outline finding if it is recursive? > + const bool is_recursing = tset.find (type) != tset.end (); > + if (is_recursing) > + return; > + > + tset.insert (type); > + const enum tree_code code = TREE_CODE (type); > + switch (code) > + { > + case VOID_TYPE: > + this->walk_VOID_TYPE (type); > + break; > + case INTEGER_TYPE: > + this->walk_INTEGER_TYPE (type); > + break; > + case REAL_TYPE: > + this->walk_REAL_TYPE (type); > + break; > + case FIXED_POINT_TYPE: > + this->walk_FIXED_POINT_TYPE (type); > + break; > + case COMPLEX_TYPE: > + this->walk_COMPLEX_TYPE (type); > + break; > + case ENUMERAL_TYPE: > + this->walk_ENUMERAL_TYPE (type); > + break; > + case BOOLEAN_TYPE: > + this->walk_BOOLEAN_TYPE (type); > + break; > + case OFFSET_TYPE: > + this->walk_OFFSET_TYPE (type); > + break; > + case RECORD_TYPE: > + this->walk_RECORD_TYPE (type); > + break; > + case POINTER_TYPE: > + this->walk_POINTER_TYPE (type); > + break; > + case REFERENCE_TYPE: > + this->walk_REFERENCE_TYPE (type); > + break; > + case ARRAY_TYPE: > + this->walk_ARRAY_TYPE (type); > + break; > + case UNION_TYPE: > + this->walk_UNION_TYPE (type); > + break; > + case FUNCTION_TYPE: > + this->walk_FUNCTION_TYPE (type); > + break; > + case METHOD_TYPE: > + this->walk_METHOD_TYPE (type); > + break; > + // Since we are dealing only with C at the moment, > + // we don't care about QUAL_UNION_TYPE nor LANG_TYPEs > + // So fail early. > + case QUAL_UNION_TYPE: > + case LANG_TYPE: > + default: > + { > + log ("missing %s\n", get_tree_code_name (code)); > + gcc_unreachable (); > + } > + break; > + } > + tset.erase (type); > +} > + > +// This is used to walk over subtrees. > +// But before walking subtrees, we need to > +// call the pre-order callback > +// and after we need to > +// call the post-order callback. > +#define TypeWalkerFuncDef(code) > \ > + void type_walker::walk_##code (tree t) \ > + { \ > + assert_is_type (t, code); \ > + _walk_##code##_pre (t); \ > + _walk_##code (t); \ > + _walk_##code##_post (t); \ > + } > + > +#define TypeWalkerFuncDefInternal(code) > \ > + void type_walker::_walk_##code (__attribute__ ((unused)) tree t) \ > + {} > + > +TypeWalkerFuncDef (VOID_TYPE) > +TypeWalkerFuncDefInternal (VOID_TYPE) > +TypeWalkerFuncDef (INTEGER_TYPE) > +TypeWalkerFuncDefInternal (INTEGER_TYPE) > +TypeWalkerFuncDef (REAL_TYPE) > +TypeWalkerFuncDefInternal (REAL_TYPE) > +TypeWalkerFuncDef (BOOLEAN_TYPE) > +TypeWalkerFuncDefInternal (BOOLEAN_TYPE) > +TypeWalkerFuncDef (OFFSET_TYPE) > +TypeWalkerFuncDefInternal (OFFSET_TYPE) > +TypeWalkerFuncDef (FIXED_POINT_TYPE) > +TypeWalkerFuncDefInternal (FIXED_POINT_TYPE) > +TypeWalkerFuncDef (COMPLEX_TYPE) > +TypeWalkerFuncDefInternal (COMPLEX_TYPE) > +TypeWalkerFuncDef (ENUMERAL_TYPE) > +TypeWalkerFuncDefInternal (ENUMERAL_TYPE) > + > +/* walk wrapper is used for unwrapping > + * REFERENCE_TYPE, POINTER_TYPE, ARRAY_TYPE. > + */ > +void type_walker::_walk_wrapper (tree t) > +{ > + tree inner_type = TREE_TYPE (t); > + // I think I encountered this code: > + // FIXME: Do we really need this? > + if (!inner_type) > + return; > + > + gcc_assert (inner_type); > + _walk (inner_type); > +} > + > +#define TypeWalkerFuncDefWrapper(code) \ > + void type_walker::_walk_##code (tree t) \ > + { _walk_wrapper (t); } > + > +TypeWalkerFuncDef (POINTER_TYPE) > +TypeWalkerFuncDefWrapper (POINTER_TYPE) > +TypeWalkerFuncDefWrapper (REFERENCE_TYPE) > +TypeWalkerFuncDef (REFERENCE_TYPE) > +TypeWalkerFuncDef (ARRAY_TYPE) > +TypeWalkerFuncDefWrapper (ARRAY_TYPE) > +TypeWalkerFuncDef (RECORD_TYPE) > + > +void > +type_walker::_walk_RECORD_TYPE (tree t) > +{ > + _walk_record_or_union (t); > +} > + > +TypeWalkerFuncDef (UNION_TYPE) > + > +void > +type_walker::_walk_UNION_TYPE (tree t) > +{ > + _walk_record_or_union (t); > +} > + > +void > +type_walker::_walk_record_or_union (tree t) > +{ > + for (tree field = TYPE_FIELDS (t); field; field = DECL_CHAIN (field)) > + { > + gcc_assert (field); > + walk_field (field); > + } > +} > + > +void > +type_walker::walk_field (tree t) > +{ > + _walk_field_pre (t); > + _walk_field (t); > + _walk_field_post (t); > +} > + > +void > +type_walker::_walk_field (tree t) > +{ > + tree inner_type = TREE_TYPE (t); > + gcc_assert (inner_type); > + _walk (inner_type); > +} > + > +TypeWalkerFuncDef (FUNCTION_TYPE) > + > + void type_walker::_walk_FUNCTION_TYPE (tree t) > +{ > + _walk_function_or_method (t); > +} > + > +TypeWalkerFuncDef (METHOD_TYPE) > + > + void type_walker::_walk_METHOD_TYPE (tree t) > +{ > + _walk_function_or_method (t); > +} > + > +void > +type_walker::_walk_function_or_method (tree t) > +{ > + tree ret_type = TREE_TYPE (t); > + walk_return (ret_type); > + walk_args (t); > +} > + > +void > +type_walker::walk_return (tree t) > +{ > + _walk_return_pre (t); > + _walk_return (t); > + _walk_return_post (t); > +} > + > +void > +type_walker::_walk_return (tree t) > +{ > + _walk (t); > +} > + > +void > +type_walker::walk_args (tree t) > +{ > + _walk_args_pre (t); > + _walk_args (t); > + _walk_args_post (t); > +} > + > +void > +type_walker::_walk_args (tree t) > +{ > + for (tree arg_node = TYPE_ARG_TYPES (t); NULL_TREE != arg_node; > + arg_node = TREE_CHAIN (arg_node)) > + { > + tree arg_node_type = TREE_VALUE (arg_node); > + gcc_assert (arg_node_type); > + walk_arg (arg_node_type); > + } > +} > + > +void > +type_walker::walk_arg (tree t) > +{ > + _walk_arg_pre (t); > + _walk_arg (t); > + _walk_arg_post (t); > +} > + > +void > +type_walker::_walk_arg (tree t) > +{ > + _walk (t); > +} > + > +/* Main interface for the ExprWalker... */ > +void > +expr_walker::walk (tree e) > +{ > + _walk_pre (e); > + _walk (e); > + _walk_post (e); > +} > + > +void > +expr_walker::_walk (tree e) > +{ > + gcc_assert (e); > + const enum tree_code code = TREE_CODE (e); > + switch (code) > + { > + case INTEGER_CST: > + walk_INTEGER_CST (e); > + break; > + case REAL_CST: > + walk_REAL_CST (e); > + break; > + case STRING_CST: > + walk_STRING_CST (e); > + break; > + case BIT_FIELD_REF: > + walk_BIT_FIELD_REF (e); > + break; > + case ARRAY_REF: > + walk_ARRAY_REF (e); > + break; > + case MEM_REF: > + walk_MEM_REF (e); > + break; > + case COMPONENT_REF: > + walk_COMPONENT_REF (e); > + break; > + case SSA_NAME: > + walk_SSA_NAME (e); > + break; > + case ADDR_EXPR: > + walk_ADDR_EXPR (e); > + break; > + case VIEW_CONVERT_EXPR: > + walk_VIEW_CONVERT_EXPR (e); > + break; > + case IMAGPART_EXPR: > + walk_IMAGPART_EXPR (e); > + break; > + case VAR_DECL: > + walk_VAR_DECL (e); > + break; > + case FIELD_DECL: > + walk_FIELD_DECL (e); > + break; > + case RESULT_DECL: > + walk_RESULT_DECL (e); > + break; > + case PARM_DECL: > + walk_PARM_DECL (e); > + break; > + case FUNCTION_DECL: > + walk_FUNCTION_DECL (e); > + break; > + case CONSTRUCTOR: > + walk_CONSTRUCTOR (e); > + break; > + case LE_EXPR: > + walk_LE_EXPR (e); > + break; > + case LT_EXPR: > + walk_LT_EXPR (e); > + break; > + case EQ_EXPR: > + walk_EQ_EXPR (e); > + break; > + case GT_EXPR: > + walk_GT_EXPR (e); > + break; > + case GE_EXPR: > + walk_GE_EXPR (e); > + break; > + case NE_EXPR: > + walk_NE_EXPR (e); > + break; > + default: > + { > + log ("missing %s\n", get_tree_code_name (code)); > + gcc_unreachable (); > + } > + break; > + } > +} > + > +/* call pre-order callback for everything > + * call pre-order callback for specific code > + * walk subtrees > + * call post-order callback for specific code > + * call post-order callback for everything. > + */ > +#define ExprWalkerFuncDef(code) \ > + void expr_walker::walk_##code (tree e) \ > + { \ > + assert_is_type (e, code); \ > + _walk_pre (e); \ > + _walk_##code##_pre (e); \ > + _walk_##code (e); \ > + _walk_##code##_post (e); \ > + _walk_post (e); \ > + } > + > +ExprWalkerFuncDef (CONSTRUCTOR) > +ExprWalkerFuncDef (INTEGER_CST) > +ExprWalkerFuncDef (REAL_CST) > +ExprWalkerFuncDef (STRING_CST) > +ExprWalkerFuncDef (BIT_FIELD_REF) > +ExprWalkerFuncDef (ARRAY_REF) > +ExprWalkerFuncDef (MEM_REF) > +ExprWalkerFuncDef (COMPONENT_REF) > +ExprWalkerFuncDef (SSA_NAME) > +ExprWalkerFuncDef (ADDR_EXPR) > +ExprWalkerFuncDef (VIEW_CONVERT_EXPR) > +ExprWalkerFuncDef (IMAGPART_EXPR) > +ExprWalkerFuncDef (FIELD_DECL) > +ExprWalkerFuncDef (VAR_DECL) > +ExprWalkerFuncDef (RESULT_DECL) > +ExprWalkerFuncDef (PARM_DECL) > +ExprWalkerFuncDef (FUNCTION_DECL) > +ExprWalkerFuncDef (LE_EXPR) > +ExprWalkerFuncDef (LT_EXPR) > +ExprWalkerFuncDef (EQ_EXPR) > +ExprWalkerFuncDef (GT_EXPR) > +ExprWalkerFuncDef (GE_EXPR) > +ExprWalkerFuncDef (NE_EXPR) > + > +void expr_walker::_walk_leaf (tree e, const enum tree_code c) > +{ > + assert_is_type (e, c); > +} > + > +void > +expr_walker::_walk_op_n (tree e, unsigned n) > +{ > + gcc_assert (e); > + tree op_n = TREE_OPERAND (e, n); > + gcc_assert (op_n); > + walk (op_n); > +} > + > +void > +expr_walker::_walk_op_0 (tree e, const enum tree_code c) > +{ > + assert_is_type (e, c); > + _walk_op_n (e, 0); > +} > + > +void > +expr_walker::_walk_op_1 (tree e, const enum tree_code c) > +{ > + assert_is_type (e, c); > + _walk_op_n (e, 0); > + _walk_op_n (e, 1); > +} > + > +void > +expr_walker::_walk_CONSTRUCTOR (__attribute__ ((unused)) tree e) > +{ > + // Future-work: If we want to support rewriting CONSTRUCTORs > + // we will have to walk them > +} > + > +void > +expr_walker::_walk_LE_EXPR (tree e) > +{ > + _walk_op_1 (e, LE_EXPR); > +} > + > +void > +expr_walker::_walk_LT_EXPR (tree e) > +{ > + _walk_op_1 (e, LT_EXPR); > +} > + > +void > +expr_walker::_walk_EQ_EXPR (tree e) > +{ > + _walk_op_1 (e, EQ_EXPR); > +} > + > +void > +expr_walker::_walk_GT_EXPR (tree e) > +{ > + _walk_op_1 (e, GT_EXPR); > +} > + > +void > +expr_walker::_walk_GE_EXPR (tree e) > +{ > + _walk_op_1 (e, GE_EXPR); > +} > + > +void > +expr_walker::_walk_NE_EXPR (tree e) > +{ > + _walk_op_1 (e, NE_EXPR); > +} > + > +void > +expr_walker::_walk_INTEGER_CST (tree e) > +{ > + _walk_leaf (e, INTEGER_CST); > +} > + > +void > +expr_walker::_walk_REAL_CST (tree e) > +{ > + _walk_leaf (e, REAL_CST); > +} > + > +void > +expr_walker::_walk_STRING_CST (tree e) > +{ > + _walk_leaf (e, STRING_CST); > +} > + > +void > +expr_walker::_walk_BIT_FIELD_REF (__attribute__ ((unused)) tree e) > +{ > + // TODO: > + // We currently don't support bit_field_ref > + // but maybe we need to do something here? > +} > + > +void > +expr_walker::_walk_ARRAY_REF (tree e) > +{ > + _walk_op_1 (e, ARRAY_REF); > +} > + > +void > +expr_walker::_walk_MEM_REF (tree e) > +{ > + _walk_op_1 (e, MEM_REF); > +} > + > +void > +expr_walker::_walk_COMPONENT_REF (tree e) > +{ > + _walk_op_1 (e, COMPONENT_REF); > +} > + > +void > +expr_walker::_walk_SSA_NAME (tree e) > +{ > + _walk_leaf (e, SSA_NAME); > +} > + > +void > +expr_walker::_walk_ADDR_EXPR (tree e) > +{ > + _walk_op_0 (e, ADDR_EXPR); > +} > + > +void > +expr_walker::_walk_VIEW_CONVERT_EXPR (__attribute__ ((unused)) tree e) > +{ > + // TODO: I don't think we need to do anything here > +} > + > +void > +expr_walker::_walk_IMAGPART_EXPR (__attribute__ ((unused)) tree e) > +{ > + // TODO: I don't think we need to do anything here > +} > + > +void > +expr_walker::_walk_FIELD_DECL (tree e) > +{ > + _walk_leaf (e, FIELD_DECL); > +} > + > +void > +expr_walker::_walk_VAR_DECL (tree e) > +{ > + _walk_leaf (e, VAR_DECL); > +} > + > +void > +expr_walker::_walk_RESULT_DECL (tree e) > +{ > + _walk_leaf (e, RESULT_DECL); > +} > + > +void > +expr_walker::_walk_PARM_DECL (tree e) > +{ > + _walk_leaf (e, PARM_DECL); > +} > + > +void > +expr_walker::_walk_FUNCTION_DECL (tree e) > +{ > + _walk_leaf (e, FUNCTION_DECL); > + for (tree parm = DECL_ARGUMENTS (e); parm; parm = DECL_CHAIN (parm)) > + { > + walk (parm); > + } > +} > + > +/* Main interface for GimpleWalker: > + * iterate over global variables and then for all functions > + * with gimple body. > + */ > +void > +gimple_walker::walk () > +{ > + _walk_globals (); > + std::set<tree> fndecls; > + cgraph_node *node = NULL; > + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) > + { > + node->get_untransformed_body (); > + tree decl = node->decl; > + gcc_assert (decl); > + const bool already_in_set = fndecls.find (decl) != fndecls.end (); > + // I think it is possible for different nodes to point to the same > + // declaration. > + if (already_in_set) > + continue; > + > + _walk_cnode (node); > + fndecls.insert (decl); > + } > +} > + > +/* For each global variable. */ > +void > +gimple_walker::_walk_globals () > +{ > + varpool_node *vnode = NULL; > + FOR_EACH_VARIABLE (vnode) > + { > + _walk_global (vnode); > + } > +} > + > +/* Walk over global variable VNODE. */ > +void > +gimple_walker::_walk_global (varpool_node *vnode) > +{ > + gcc_assert (vnode); > + struct ipa_ref *ref = NULL; > + for (unsigned i = 0; vnode->iterate_referring (i, ref); i++) > + { > + tree var_decl = vnode->decl; > + walk_tree2 (var_decl); > + } > +} > + > +/* Walk over SSA_NAMEs in CNODE. */ > +void > +gimple_walker::_walk_ssa_names (cgraph_node *cnode) > +{ > + tree decl = cnode->decl; > + gcc_assert (decl); > + function *func = DECL_STRUCT_FUNCTION (decl); > + gcc_assert (func); > + size_t i = 0; > + tree ssa_name = NULL; > + push_cfun (func); > + FOR_EACH_SSA_NAME (i, ssa_name, cfun) > + { > + gcc_assert (ssa_name); > + walk_tree2 (ssa_name); > + tree ssa_name_var = SSA_NAME_VAR (ssa_name); > + if (!ssa_name_var) > + continue; > + walk_tree2 (ssa_name_var); > + } > + pop_cfun (); > +} > + > +/* Walk over declaration, locals, ssa_names, and basic blocks > + * in CNODE. */ > +void > +gimple_walker::_walk_cnode (cgraph_node *cnode) > +{ > + gcc_assert (cnode); > + _walk_decl (cnode); > + _walk_locals (cnode); > + _walk_ssa_names (cnode); > + _walk_bb (cnode); > +} > + > +/* Walk over each local declaration in CNODE. */ > +void > +gimple_walker::_walk_locals (cgraph_node *cnode) > +{ > + tree decl = cnode->decl; > + gcc_assert (decl); > + function *func = DECL_STRUCT_FUNCTION (decl); > + gcc_assert (func); > + int i = 0; > + tree var_decl = NULL; > + FOR_EACH_LOCAL_DECL (func, i, var_decl) > + { > + gcc_assert (var_decl); > + walk_tree2 (var_decl); > + } > +} > + > +/* Walk over all basic blocks in CNODE. */ > +void > +gimple_walker::_walk_bb (cgraph_node *cnode) > +{ > + gcc_assert (cnode); > + cnode->get_untransformed_body (); > + tree decl = cnode->decl; > + gcc_assert (decl); > + function *func = DECL_STRUCT_FUNCTION (decl); > + gcc_assert (func); > + basic_block bb = NULL; > + push_cfun (func); > + FOR_EACH_BB_FN (bb, func) > + { > + _walk (bb); > + } > + pop_cfun (); > +} > + > +/* Walk over CNODE->decl. */ > +void > +gimple_walker::_walk_decl (cgraph_node *cnode) > +{ > + tree decl = cnode->decl; > + gcc_assert (decl); > + walk_tree2 (decl); > +} > + > +/* Walk over each gimple statement in BB. */ > +void > +gimple_walker::_walk (basic_block bb) > +{ > + gcc_assert (bb); > + gimple_stmt_iterator gsi = gsi_start_bb (bb); > + while (!gsi_end_p (gsi)) > + { > + this->_deleted = false; > + gimple *stmt = gsi_stmt (gsi); > + walk_gimple (stmt); > + // If it is not deleted just continue. > + if (!this->_deleted) > + { > + gsi_next (&gsi); > + continue; > + } > + > + // Otherwise remove statement. > + unlink_stmt_vdef (stmt); > + gsi_remove (&gsi, true); > + } > + > + // TODO: Maybe outline to its own function? > + for (gimple_stmt_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); > + gsi_next (&gsi)) > + { > + gimple *stmt = gsi_stmt (gsi); > + walk_gimple (stmt); > + } > +} > + > +// call preorder callback > +// walk subtrees > +// call postorder callback > +void > +gimple_walker::walk_gimple (gimple *stmt) > +{ > + _walk_pre_gimple (stmt); > + _walk_gimple (stmt); > + _walk_post_gimple (stmt); > +} > + > +/* Switch for different gimple instruction types. */ > +void > +gimple_walker::_walk_gimple (gimple *stmt) > +{ > +// Do not use _walk_pre (s) > +// Subtle but important distinction, > +// we want to differentiate calling here stamtent from s > +// TODO: Maybe delete though? > +// This could also be the source for the double insertion to stack bug? > + if (gassign *_gassign = dyn_cast<gassign*> (stmt)) > + { > + _walk_pre_gimple (stmt); > + walk_gassign (_gassign); > + _walk_post_gimple (stmt); > + return; > + } > + > + if (greturn *_greturn = dyn_cast<greturn*> (stmt)) > + { > + _walk_pre_gimple (stmt); > + walk_greturn (_greturn); > + _walk_post_gimple (stmt); > + return; > + } > + > + if (gcond *_gcond = dyn_cast<gcond*> (stmt)) > + { > + _walk_pre_gimple (stmt); > + walk_gcond (_gcond); > + _walk_post_gimple (stmt); > + return; > + } > + > + if (gcall *_gcall = dyn_cast<gcall*> (stmt)) > + { > + _walk_pre_gimple (stmt); > + walk_gcall (_gcall); > + _walk_post_gimple (stmt); > + return; > + } > + > + if (glabel *_glabel = dyn_cast<glabel*> (stmt)) > + { > + _walk_pre_gimple (stmt); > + walk_glabel (_glabel); > + _walk_post_gimple (stmt); > + return; > + } > + > + if (gswitch *_gswitch = dyn_cast<gswitch*> (stmt)) > + { > + _walk_pre_gimple (stmt); > + walk_gswitch (_gswitch); > + _walk_post_gimple (stmt); > + return; > + } > + > + > + if (gphi *_gphi = dyn_cast<gphi*> (stmt)) > + { > + _walk_pre_gimple (stmt); > + walk_gphi (_gphi); > + _walk_post_gimple (stmt); > + return; > + } > + > + const enum gimple_code code = gimple_code (stmt); > + switch (code) > + { > + case GIMPLE_PREDICT: > + case GIMPLE_DEBUG: > + case GIMPLE_NOP: > + // I think it is safe to skip these > + // but it would also be nice to walk their sub-trees > + return; > + break; > + default: > + break; > + } > + > + // Break if something is unexpected. > + const char *name = gimple_code_name[code]; > + log ("gimple code name %s\n", name); > + gcc_unreachable (); > +} > + > +void > +gimple_walker::walk_tree2 (tree t) > +{ > + _walk_pre_tree (t); > + _walk_tree (t); > + _walk_post_tree (t); > +} > + > +void > +gimple_walker::_walk_tree (__attribute__((unused)) tree t) > +{} > + > +void > +gimple_walker::walk_gassign (gassign *g) > +{ > + _walk_pre_gassign (g); > + _walk_gassign (g); > + _walk_post_gassign (g); > +} > + > +void > +gimple_walker::_walk_gassign (__attribute__((unused)) gassign *g) > +{} > + > +void > +gimple_walker::walk_greturn (greturn *g) > +{ > + _walk_pre_greturn (g); > + _walk_greturn (g); > + _walk_post_greturn (g); > +} > + > +void > +gimple_walker::_walk_greturn (__attribute__((unused)) greturn *g) > +{} > + > +void > +gimple_walker::walk_gcond (gcond *g) > +{ > + _walk_pre_gcond (g); > + _walk_gcond (g); > + _walk_post_gcond (g); > +} > + > +void > +gimple_walker::_walk_gcond (__attribute__((unused)) gcond *g) > +{} > + > +void > +gimple_walker::walk_gcall (gcall *g) > +{ > + _walk_pre_gcall (g); > + _walk_gcall (g); > + _walk_post_gcall (g); > +} > + > +void > +gimple_walker::_walk_gcall (__attribute__((unused)) gcall *g) > +{} > + > +void > +gimple_walker::walk_glabel (glabel *g) > +{ > + _walk_pre_glabel (g); > + _walk_glabel (g); > + _walk_post_glabel (g); > +} > + > +void > +gimple_walker::_walk_glabel (__attribute__((unused)) glabel *g) > +{} > + > +void > +gimple_walker::walk_gswitch (gswitch *g) > +{ > + _walk_pre_gswitch (g); > + _walk_gswitch (g); > + _walk_post_gswitch (g); > +} > + > +void > +gimple_walker::_walk_gswitch (__attribute__((unused)) gswitch *g) > +{ > +} > + > +void > +gimple_walker::walk_gphi (gphi *g) > +{ > + _walk_pre_gphi (g); > + _walk_gphi (g); > + _walk_post_gphi (g); > +} > + > +void > +gimple_walker::_walk_gphi (__attribute__((unused)) gphi *g) > +{ > +} > + > + > +void > +type_collector::collect (tree t) > +{ > + const bool in_set = ptrset.in_universe (t); > + // Early memoization... > + > + if (in_set) > + return; > + > + // TODO: Can we move this to the beginning > + // of the function. > + gcc_assert (t); > + > + // This is the map that holds the types > + // we will encounter in this walk. > + // It should be empty at the beginning. > + // It maps from tree -> bool. > + // The boolean will be updated to show > + // whether a record is reachable from > + // the type. > + gcc_assert (ptr.empty ()); > + walk (t); > +} > + > +// Make sure partitions are mutually exclusive. > +void > +type_collector::_sanity_check () > +{ > + for (tset_t::iterator i = ptrset.points_to_record.begin (), > + e = ptrset.points_to_record.end (); > + i != e; ++i) > + { > + for (tset_t::iterator j = ptrset.complement.begin (), > + f = ptrset.complement.end (); > + j != f; ++j) > + { > + tree type_ptr = *i; > + gcc_assert (type_ptr); > + tree type_com = *j; > + gcc_assert (type_com); > + const bool valid_sets = type_ptr != type_com; > + if (valid_sets) > + continue; > + > + // Normally, we want a stronger type comparison > + // that is not just the pointer address > + // but this is the first sanity check and then we will need to > + // determine the stronger type comparison. But first we will > need to > + // fix the types... > + gcc_unreachable (); > + } > + } > +} > + > +/* Determine if T is already memoized in the TypeCollector. */ > +bool > +type_collector::is_memoized (tree t) > +{ > + /* If we haven't seen it then no. */ > + const bool in_set = ptrset.in_universe (t); > + if (!in_set) > + return false; > + > + // If the memoized type points to a record > + // we must update all types that can refer > + // to memoized type. > + const bool points_to_record = ptrset.in_points_to_record (t); > + for (std::map<tree, bool>::iterator i = ptr.begin (), > + e = ptr.end (); i != e; ++i) > + { > + i->second |= points_to_record; > + } > + return true; > +} > + > +void > +type_collector::_walk_VOID_TYPE_pre (tree t) > +{ > + ptr[t] = false; > +} > + > +void > +type_collector::_walk_VOID_TYPE_post (tree t) > +{ > + _collect_simple (t); > +} > + > +void > +type_collector::_walk_INTEGER_TYPE_pre (tree t) > +{ > + ptr[t] = false; > +} > + > +void > +type_collector::_walk_INTEGER_TYPE_post (tree t) > +{ > + _collect_simple (t); > +} > + > +void > +type_collector::_walk_REAL_TYPE_pre (tree t) > +{ > + ptr[t] = false; > +} > + > +void > +type_collector::_walk_REAL_TYPE_post (tree t) > +{ > + _collect_simple (t); > +} > + > +void > +type_collector::_walk_FIXED_POINT_TYPE_pre (tree t) > +{ > + ptr[t] = false; > +} > + > +void > +type_collector::_walk_FIXED_POINT_TYPE_post (tree t) > +{ > + _collect_simple (t); > +} > + > +void > +type_collector::_walk_COMPLEX_TYPE_pre (tree t) > +{ > + ptr[t] = false; > +} > + > +void > +type_collector::_walk_COMPLEX_TYPE_post (tree t) > +{ > + _collect_simple (t); > +} > + > +void > +type_collector::_walk_ENUMERAL_TYPE_pre (tree t) > +{ > + ptr[t] = false; > +} > + > +void > +type_collector::_walk_ENUMERAL_TYPE_post (tree t) > +{ > + _collect_simple (t); > +} > + > +void > +type_collector::_walk_BOOLEAN_TYPE_pre (tree t) > +{ > + ptr[t] = false; > +} > + > +void > +type_collector::_walk_BOOLEAN_TYPE_post (tree t) > +{ > + _collect_simple (t); > +} > + > +void > +type_collector::_collect_simple (tree t) > +{ > + // Insert into persistent set. > + ptrset.insert (t, ptr[t]); > + // erase from current working set. > + ptr.erase (t); > +} > + > +void > +type_collector::_walk_ARRAY_TYPE_pre (tree t) > +{ > + ptr[t] = false; > +} > + > +void > +type_collector::_walk_ARRAY_TYPE_post (tree t) > +{ > + _collect_simple (t); > +} > + > +void > +type_collector::_walk_POINTER_TYPE_pre (tree t) > +{ > + ptr[t] = false; > +} > + > +void > +type_collector::_walk_POINTER_TYPE_post (tree t) > +{ > + _collect_simple (t); > +} > + > +void > +type_collector::_walk_REFERENCE_TYPE_pre (tree t) > +{ > + ptr[t] = false; > +} > + > +void > +type_collector::_walk_REFERENCE_TYPE_post (tree t) > +{ > + _collect_simple (t); > +} > + > +void > +type_collector::_walk_RECORD_TYPE_post (tree t) > +{ > + // All in ptr point to record > + for (std::map<tree, bool>::iterator i = ptr.begin (), > + e = ptr.end (); i != e; ++i) > + { > + i->second = true; > + } > + _collect_simple (t); > +} > + > +void > +type_collector::_walk_RECORD_TYPE_pre (tree t) > +{ > + ptr[t] = false; > +} > + > +void > +type_collector::_walk_UNION_TYPE_pre (tree t) > +{ > + ptr[t] = false; > +} > + > +void > +type_collector::_walk_UNION_TYPE_post (tree t) > +{ > + _collect_simple (t); > +} > + > +void > +type_collector::_walk_FUNCTION_TYPE_post (tree t) > +{ > + _collect_simple (t); > +} > + > +void > +type_collector::_walk_FUNCTION_TYPE_pre (tree t) > +{ > + ptr[t] = false; > +} > + > +void > +type_collector::_walk_METHOD_TYPE_post (tree t) > +{ > + _collect_simple (t); > +} > + > +void > +type_collector::_walk_METHOD_TYPE_pre (tree t) > +{ > + ptr[t] = false; > +} > + > +inline void > +expr_collector::_walk_pre (tree e) > +{ > + tree t = TREE_TYPE (e); > + gcc_assert (t); > + typeCollector.collect (t); > +} > + > +/* > + * For global variables T, this method will collect > + * and partition trees corresponding to types > + * into std::sets. Concretely speaking, this class > + * partitions trees into two sets: > + * * reach a RECORD_TYPE > + * * does not reach a RECORD_TYPE. > + */ > +void > +gimple_type_collector::_walk_pre_tree (tree t) > +{ > + _expr_collector.walk (t); > +} > + > +/* > + * For assignment statements S, this method will collect > + * and partition trees corresponding to types > + * into std::sets. Concretely speaking, this class > + * partitions trees into two sets: > + * * reach a RECORD_TYPE > + * * does not reach a RECORD_TYPE > + * The types reachable from the lhs and rhs are placed > + * in these sets. > + */ > +void > +gimple_type_collector::_walk_pre_gassign (gassign *s) > +{ > + tree lhs = gimple_assign_lhs (s); > + _expr_collector.walk (lhs); > + > + const enum gimple_rhs_class gclass = gimple_assign_rhs_class (s); > + switch (gclass) > + { > + case GIMPLE_TERNARY_RHS: > + { > + tree rhs = gimple_assign_rhs3 (s); > + _expr_collector.walk (rhs); > + } > + /* fall-through */ > + case GIMPLE_BINARY_RHS: > + { > + tree rhs = gimple_assign_rhs2 (s); > + _expr_collector.walk (rhs); > + } > + /* fall-through */ > + case GIMPLE_UNARY_RHS: > + case GIMPLE_SINGLE_RHS: > + { > + tree rhs = gimple_assign_rhs1 (s); > + _expr_collector.walk (rhs); > + } > + break; > + default: > + gcc_unreachable (); > + break; > + } > +} > + > +void > +gimple_type_collector::_walk_pre_greturn (greturn *s) > +{ > + tree retval = gimple_return_retval (s); > + if (!retval) > + return; > + > + _expr_collector.walk (retval); > +} > + > +void > +gimple_type_collector::_walk_pre_gcall (gcall *s) > +{ > + // Walk over the arguments. > + unsigned n = gimple_call_num_args (s); > + for (unsigned i = 0; i < n; i++) > + { > + tree a = gimple_call_arg (s, i); > + _expr_collector.walk (a); > + } > + > + // Walk over the return type if it exists. > + tree lhs = gimple_call_lhs (s); > + if (!lhs) > + return; > + > + _expr_collector.walk (lhs); > +} > + > +// Print working set. > +void > +gimple_type_collector::print_collected () > +{ > + tpartitions_t sets = get_record_reaching_trees (); > +} > + > +/* Walk over LHS and RHS of conditions. */ > +void > +gimple_type_collector::_walk_pre_gcond (gcond *s) > +{ > + tree lhs = gimple_cond_lhs (s); > + _expr_collector.walk (lhs); > + tree rhs = gimple_cond_rhs (s); > + _expr_collector.walk (rhs); > +} > + > +bool > +type_escaper::is_memoized (__attribute__ ((unused)) tree t) > +{ > + // Can't memoize here because > + // information is propagated up and down > + // the type. > + return false; > +} > + > +tpartitions_t > +type_escaper::get_sets () > +{ > + place_escaping_types_in_set (); > + return _ptrset; > +} > + > +/* From a map of TREE -> BOOL, the key represents a tree type > + * and the value represents whether the tree escapes. > + * Partition this map into sets. > + */ > +void > +type_escaper::place_escaping_types_in_set () > +{ > + type_stringifier stringifier; > + for (typemap::iterator i = calc.begin (), e = calc.end (); i != e; ++i) > + { > + tree type = i->first; > + > + // We should only track interesting types > + // Types which are not in points_to_record are the ones > + // that are pointed to by records. > + // I think it is possible to prune them ahead of time... > + if (!_ptrset.in_points_to_record (type)) > + continue; > + > + const Reason reason = i->second; > + reason.is_escaping () ? _ptrset.escaping.insert (type) > + : _ptrset.non_escaping.insert (type); > + } > +} > + > +void > +type_escaper::update (tree t, Reason r) > +{ > + gcc_assert (t); > + _reason = r; > + walk (t); > +} > + > +void > +type_escaper::_update_single (tree t, Reason r) > +{ > + gcc_assert (t); > + _reason = r; > + _update (t); > +} > + > +void > +type_escaper::_update (tree t) > +{ > + gcc_assert (t); > + const bool already_in_typemap = calc.find (t) != calc.end (); > + // Do we have to invalidate all types which point to a volatile type? > + // Or do we have to invalidate all types pointed to by a volatile type? > + // Or do we only invalidate all types which are volatile. > + // This is only the third option. > + const bool is_volatile = TYPE_VOLATILE (t); > + Reason _is_volatile; > + _is_volatile.type_is_volatile = is_volatile; > + Reason _inner = _reason | _is_volatile; > + // always OR > + already_in_typemap ? calc[t] |= _inner : calc[t] = _inner; > +} > + > +void > +type_escaper::_walk_ARRAY_TYPE_pre (tree t) > +{ > + _update (t); > +} > + > +void > +type_escaper::_walk_ARRAY_TYPE_post (tree t) > +{ > + _update (t); > +} > + > +void > +type_escaper::_walk_POINTER_TYPE_pre (tree t) > +{ > + _update (t); > +} > + > +void > +type_escaper::_walk_POINTER_TYPE_post (tree t) > +{ > + _update (t); > +} > + > +void > +type_escaper::_walk_REFERENCE_TYPE_pre (tree t) > +{ > + _update (t); > +} > + > +void > +type_escaper::_walk_RECORD_TYPE_pre (tree t) > +{ > + // we are entering a record > + _inside_record++; > + _update (t); > +} > + > +void > +type_escaper::_walk_RECORD_TYPE_post (tree t) > +{ > + _update (t); // This is in case there was a union > + // we are exiting a record > + _inside_record--; > +} > + > +/* Mark as escaping because of union > + * and propagate up and down. > + */ > +void > +type_escaper::_walk_UNION_TYPE_pre (tree t) > +{ > + _inside_union++; > + bool is_escaping = _inside_union > 0; > + _reason.type_is_in_union |= is_escaping; > + _update (t); > +} > + > +/* Mark bit fields as escaping and propagate up > + * and down. > + */ > +void > +type_escaper::_walk_field_pre (tree t) > +{ > + _reason.type_is_in_union |= DECL_BIT_FIELD (t); > +} > + > +void > +type_escaper::_walk_UNION_TYPE_post (tree t) > +{ > + _inside_union--; > + _update (t); > +} > + > +/* Mark as escaping because RECORD has a function pointer > + * propagate up and down. > + */ > +void > +type_escaper::_walk_FUNCTION_TYPE_pre (__attribute__ ((unused)) tree t) > +{ > + _reason.type_is_in_union |= _inside_record > 0; > +} > + > +/* Mark as escaping because RECORD has a function pointer > + * propagate up and down. > + */ > +void > +type_escaper::_walk_METHOD_TYPE_pre (__attribute__ ((unused)) tree t) > +{ > + _reason.type_is_in_union |= _inside_record > 0; > +} > + > +/* Print escaping reasons. */ > +void > +type_escaper::print_reasons () > +{ > + type_stringifier stringifier; > + for (typemap::iterator i = calc.begin (), e = calc.end (); i != e; ++i) > + { > + tree t = i->first; > + std::string name = stringifier.stringify (t); > + Reason r = i->second; > + log ("%s reason: ", name.c_str ()); > + r.print (); > + } > +} > + > +tpartitions_t > +expr_escaper::get_sets () > +{ > + return _type_escaper.get_sets (); > +} > + > +void > +expr_escaper::print_reasons () > +{ > + _type_escaper.print_reasons (); > +} > + > +/* Propagate reason to subexpressions. */ > +void > +expr_escaper::update (tree t, Reason r) > +{ > + gcc_assert (t); > + _r = r; > + walk (t); > +} > + > +/* Propagate reason to type of subexpressions. */ > +void > +expr_escaper::_walk_pre (tree e) > +{ > + _stack.push (e); > + tree t = TREE_TYPE (e); > + > + gcc_assert (t); > + _type_escaper.update (t, _r); > +} > + > +void > +expr_escaper::_walk_post (__attribute__ ((unused)) tree e) > +{ > + _stack.pop (); > +} > + > +/* Capture casting on LHS. */ > +void > +expr_escaper::_walk_SSA_NAME_pre (tree e) > +{ > + tree ssa_type = TREE_TYPE (e); > + > + > + if (_stack.size () < 4) > + return; > + > + tree this_expr = _stack.top (); > + _stack.pop (); > + tree twice = _stack.top (); > + _stack.pop (); > + tree prev_expr = _stack.top (); > + _stack.push (twice); > + _stack.push (this_expr); > + if (TREE_CODE (prev_expr) != MEM_REF) > + return; > + > + tree op1 = TREE_OPERAND (prev_expr, 1); > + gcc_assert (TREE_CODE (op1) == INTEGER_CST); > + tree mref_type = TREE_TYPE (op1); > + > + Reason old_reason = _r; > + type_incomplete_equality structuralEquality; > + // we need to make sure that both of them point to structs? > + if (TREE_CODE (TREE_TYPE (mref_type)) == INTEGER_TYPE) > + return; > + > + _r.type_is_casted = !structuralEquality.equal (mref_type, ssa_type); > + type_stringifier stringifier; > + log ("mref_type is casted %s = %s\n", > stringifier.stringify(mref_type).c_str(), _r.type_is_casted ? "T" : "F"); > + log ("ssa_type is casted %s = %s\n", > stringifier.stringify(ssa_type).c_str(), _r.type_is_casted ? "T" : "F"); > + _type_escaper._update_single (mref_type, _r); > + _type_escaper._update_single (ssa_type, _r); > + _r = old_reason; > +} > + > +/* Mark constructors as escaping. */ > +void > +expr_escaper::_walk_CONSTRUCTOR_pre (tree e) > +{ > + if (TREE_CLOBBER_P (e)) > + return; > + > + // TODO: Instead of overloading global_is_visible field > + // with has a constructor, make a field that denotes that > + // a this has a constructor. > + // Or better yet... modify the constructors! > + _r.global_is_visible = true; > + tree t = TREE_TYPE (e); > + _type_escaper.update (t, _r); > +} > + > +tpartitions_t > +gimple_escaper::get_sets () > +{ > + _expr_escaper.curr_node = NULL; > + return _expr_escaper.get_sets (); > +} > + > +void > +gimple_escaper::print_reasons () > +{ > + _expr_escaper.curr_node = NULL; > + _expr_escaper.print_reasons (); > +} > + > +/* Initialize undefined set of functions. */ > +void > +gimple_escaper::_init () > +{ > + cgraph_node *cnode = NULL; > + FOR_EACH_FUNCTION (cnode) > + { > + gcc_assert (cnode); > + const bool filter = gimple_escaper::filter_known_function (cnode); > + if (filter) > + continue; > + > + tree decl = cnode->decl; > + gcc_assert (decl); > + undefined.insert (decl); > + } > + > + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cnode) > + { > + gcc_assert (cnode); > + cnode->get_untransformed_body (); > + tree decl = cnode->decl; > + gcc_assert (decl); > + undefined.erase (decl); > + } > +} > + > +/* Mark cnode graphs escaping if they are externally visible. */ > +bool > +gimple_escaper::is_function_escaping (cgraph_node *cnode) > +{ > + const bool filter = gimple_escaper::filter_known_function (cnode); > + if (filter) > + return false; > + > + return cnode->externally_visible; > +} > + > +/* Mark fndecl as escaping is they are externally visible or > + * there is no fndecl. */ > +bool > +gimple_escaper::is_function_escaping (tree fndecl) > +{ > + if (!fndecl) > + return true; > + > + if (!TREE_PUBLIC (fndecl) && !DECL_EXTERNAL (fndecl)) > + return false; > + > + return true; > +} > + > +/* Mark variable as escaping if it is externally visible. */ > +bool > +gimple_escaper::is_variable_escaping (varpool_node *vnode) > +{ > + gcc_assert (vnode); > + const bool retval = vnode->externally_visible; > + const bool retval2 = vnode->externally_visible_p (); > + log("%s externally_visible = %d %d\n", vnode->name (), retval, retval2); > + return retval; > +} > + > +/* Walk global variable VNODE. */ > +void > +gimple_escaper::_walk_global (varpool_node *vnode) > +{ > + gcc_assert (vnode); > + tree var_decl = vnode->decl; > + Reason reason; > + const bool is_escaping = is_variable_escaping (vnode); > + reason.global_is_visible = is_escaping; > + > + // TODO: Instead of overloading the semantic meaning of global is > visible > + // make different fields for CONSTRUCTOR and for CONSTRUCTOR is not > in linking > + // unit > + // TODO: Once we are able to rewrite the CONSTRUCTOR we can get rid > of marking > + // types with bracket constructors as illegal. > + tree initial = DECL_INITIAL (var_decl); > + const bool constructor = initial ? TREE_CODE (initial) == CONSTRUCTOR > : false; > + const bool error_mark = initial ? TREE_CODE (initial) == ERROR_MARK : > false; > + reason.global_is_visible > + |= constructor || error_mark; // static initialization... > + > + _expr_escaper.update (var_decl, reason); > + gimple_walker::_walk_global (vnode); > +} > + > +/* Return true if FNDECL is a known function. */ > +bool > +gimple_escaper::filter_known_function (tree fndecl) > +{ > + assert_is_type (fndecl, FUNCTION_DECL); > + if (fndecl_built_in_p (fndecl)) > + { > + switch (DECL_FUNCTION_CODE (fndecl)) > + { > + case BUILT_IN_FREE: > + case BUILT_IN_MALLOC: > + case BUILT_IN_REALLOC: > + case BUILT_IN_CALLOC: > + case BUILT_IN_MEMSET: > + return true; > + break; > + default: > + break; > + } > + } > + > + return false; > +} > + > +/* Return True if NODE points to a known FUNCTION_DECL. */ > +bool > +gimple_escaper::filter_known_function (cgraph_node *node) > +{ > + if (!node) > + return false; > + return filter_known_function (node->decl); > +} > + > +/* Mark Variable declaration of unknown location as escaping. */ > +void > +gimple_escaper::_walk_pre_tree (tree t) > +{ > + // Is any global variable escaping? > + Reason reason; > + if (TREE_CODE (t) == VAR_DECL) > + { > + if (DECL_SOURCE_LOCATION (t) == UNKNOWN_LOCATION) > + // Detecting some builtin types > + // I think fprofile-generate inserts some builtin types which > + // cannot be detected in any other way... > + // TODO: Maybe add a new reason instead of overloading is_indirect. > + reason.is_indirect = true; > + } > + _expr_escaper.update (t, reason); > +} > + > +void > +gimple_escaper::_walk_pre_gassign (gassign *s) > +{ > + Reason reason; > + const enum gimple_rhs_class code = gimple_assign_rhs_class (s); > + switch (code) > + { > + case GIMPLE_TERNARY_RHS: > + { > + tree rhs3 = gimple_assign_rhs3 (s); > + _expr_escaper.update (rhs3, reason); > + } > + /* fall-through */ > + case GIMPLE_BINARY_RHS: > + { > + tree rhs2 = gimple_assign_rhs2 (s); > + _expr_escaper.update (rhs2, reason); > + } > + /* fall-through */ > + case GIMPLE_UNARY_RHS: > + case GIMPLE_SINGLE_RHS: > + { > + tree rhs1 = gimple_assign_rhs1 (s); > + _expr_escaper.update (rhs1, reason); > + tree lhs = gimple_assign_lhs (s); > + if (!lhs) > + break; > + _expr_escaper.update (lhs, reason); > + } > + break; > + default: > + gcc_unreachable (); > + break; > + } > +} > + > +void > +gimple_escaper::_walk_pre_greturn (greturn *s) > +{ > + Reason reason; > + tree val = gimple_return_retval (s); > + if (!val) > + return; > + _expr_escaper.update (val, reason); > +} > + > +void > +gimple_escaper::_walk_pre_gcond (gcond *s) > +{ > + Reason reason; > + tree lhs = gimple_cond_lhs (s); > + tree rhs = gimple_cond_rhs (s); > + gcc_assert (lhs && rhs); > + _expr_escaper.update (lhs, reason); > + _expr_escaper.update (rhs, reason); > +} > + > +void > +gimple_escaper::_walk_pre_gcall (gcall *s) > +{ > + tree fn = gimple_call_fndecl (s); > + // gcc_assert (fn); > + // The above will not always be true > + // It will be false when we have an indirect function > + cgraph_node *node = fn ? cgraph_node::get (fn) : NULL; > + type_stringifier stringifier; > + const bool _is_function_escaping > + = node ? is_function_escaping (node) : is_function_escaping (fn); > + const bool is_undefined = undefined.find (fn) != undefined.end (); > + log ("is undefined %s\n", is_undefined ? "t" : "f"); > + const bool _is_escaping = is_undefined || _is_function_escaping; > + > + Reason arg_reason; > + arg_reason.parameter_is_visible = _is_escaping; > + arg_reason.is_indirect = !fn; > + unsigned n = gimple_call_num_args (s); > + for (unsigned i = 0; i < n; i++) > + { > + tree a = gimple_call_arg (s, i); > + gcc_assert (a); > + if (arg_reason.is_escaping ()) > + { > + std::string name = stringifier.stringify (TREE_TYPE (a)); > + log ("escaping parameter %s\n", name.c_str ()); > + } > + _expr_escaper._type_escaper.update (TREE_TYPE (a), arg_reason); > + } > + > + tree lhs = gimple_call_lhs (s); > + if (!lhs) > + return; > + Reason return_reason; > + return_reason.return_is_visible = _is_escaping; > + return_reason.is_indirect = !fn; > + _expr_escaper.update (lhs, return_reason); > +} > + > +/* Determine if cast comes from a known function. > + * Do this by following the use-def chain. */ > +bool > +gimple_caster::follow_def_to_find_if_really_cast (tree rhs) > +{ > + gimple *def_for_rhs = SSA_NAME_DEF_STMT (rhs); > + gcall *is_call = dyn_cast<gcall *> (def_for_rhs); > + if (!is_call) > + return true; > + > + tree fn = gimple_call_fndecl (is_call); > + if (!fn) > + return true; > + > + bool known_function = gimple_escaper::filter_known_function (fn); > + return !known_function; > +} > + > +void > +gimple_caster::_walk_pre_gassign (gassign *s) > +{ > + const enum gimple_rhs_class code = gimple_assign_rhs_class (s); > + const bool valid_input = GIMPLE_SINGLE_RHS == code; > + if (!valid_input) > + return; > + > + // I originally was using gimple_assign_cast_p > + // but that proved to be insufficient... > + // So we have to use our equality comparison... > + type_incomplete_equality equality; > + tree lhs = gimple_assign_lhs (s); > + tree rhs = gimple_assign_rhs1 (s); > + gcc_assert (lhs && rhs); > + Reason reason; > + tree t_lhs = TREE_TYPE (lhs); > + tree t_rhs = TREE_TYPE (rhs); > + gcc_assert (t_lhs && t_rhs); > + > + type_stringifier stringifier; > + bool is_cast = !equality.equal (TYPE_MAIN_VARIANT(t_lhs), > TYPE_MAIN_VARIANT(t_rhs)); > + // If it is cast, we might need to look at the definition of rhs > + // If the definition comes from a known function... then we are good... > + bool is_ssa = TREE_CODE (rhs) == SSA_NAME; > + is_cast = is_cast && is_ssa ? follow_def_to_find_if_really_cast (rhs) > : is_cast; > + // we allow casts to pointers... > + is_cast = is_cast && !(t_lhs == ptr_type_node); > + reason.type_is_casted = is_cast; > + _expr_escaper._type_escaper.update (TREE_TYPE (lhs), reason); > + _expr_escaper._type_escaper.update (TREE_TYPE (rhs), reason); > + > + gimple_escaper::_walk_pre_gassign (s); > +} > + > +/* Check to see if arguments are casted. */ > +void > +gimple_caster::_walk_pre_gcall (gcall *s) > +{ > + gimple_escaper::_walk_pre_gcall (s); > + > + tree fn = gimple_call_fndecl (s); > + // If there's no function declaration, how do we > + // know the argument types? > + if (!fn) > + return; > + > + cgraph_node *node = cgraph_node::get (fn); > + const bool known_function = gimple_escaper::filter_known_function (node) > + || gimple_escaper::filter_known_function > (fn); > + if (known_function) > + return; > + > + tree f_t = TREE_TYPE (fn); > + type_incomplete_equality equality; > + > + unsigned i = 0; > + type_stringifier stringifier; > + for (tree a = TYPE_ARG_TYPES (f_t); NULL_TREE != a; a = TREE_CHAIN (a)) > + { > + tree formal_t = TREE_VALUE (a); > + // There seems to be a final VOID_TYPE at the end of some functions? > + const enum tree_code code = TREE_CODE (formal_t); > + const bool is_void = VOID_TYPE == code; > + if (is_void) > + continue; > + > + tree real = gimple_call_arg (s, i); > + tree real_t = TREE_TYPE (real); > + bool is_casted = !equality.equal (formal_t, real_t); > + is_casted = is_casted && (formal_t != ptr_type_node); > + log("arg %s is casted: %s\n", > stringifier.stringify(real_t).c_str(), is_casted ? "T" : "F"); > + Reason arg_reason; > + arg_reason.type_is_casted = is_casted; > + _expr_escaper._type_escaper.update (TREE_TYPE (real), arg_reason); > + i++; > + } > + > + tree lhs = gimple_call_lhs (s); > + if (!lhs) > + return; > + > + tree r_t = TREE_TYPE (f_t); > + tree l_t TREE_TYPE (lhs); > + const bool is_casted = !equality.equal (r_t, l_t); > + log ("ret %s is casted: %s\n", stringifier.stringify(l_t).c_str(), > is_casted ? "T" : "F"); > + Reason ret_reason; > + ret_reason.type_is_casted = is_casted; > + _expr_escaper.update (lhs, ret_reason); > +} > + > +bool > +type_accessor::is_memoized (tree t) > +{ > + return memoized_map.find (t) != memoized_map.end (); > +} > + > +/* Add all fields in struct to memoized map. */ > +void > +type_accessor::_walk_RECORD_TYPE_pre (tree t) > +{ > + add_all_fields_in_struct (t); > + memoized_map.insert (t); > +} > + > +/* Initialize all fields as neither read nor written. */ > +void > +type_accessor::add_all_fields_in_struct (tree t) > +{ > + const enum tree_code c = TREE_CODE (t); > + const bool is_record = RECORD_TYPE == c; > + if (!is_record) > + return; > + > + const bool record_already_in_map = _map.find (t) != _map.end (); > + field_access_map_t field_map; > + field_map = record_already_in_map ? _map[t] : field_map; > + > + // Let's add all fields to the field map as empty. > + for (tree field = TYPE_FIELDS (t); field; field = DECL_CHAIN (field)) > + { > + const bool field_already_in_map_2 > + = field_map.find (field) != field_map.end (); > + if (field_already_in_map_2) > + continue; > + field_map[field] = Empty; > + } > + > + _map[t] = field_map; > +} > + > +record_field_map_t > +expr_accessor::get_map () > +{ > + return record_field_map; > +} > + > +void > +expr_accessor::add_all_fields_in_struct (tree t) > +{ > + _type_accessor.walk (t); > +} > + > +void > +expr_accessor::_walk_pre (tree e) > +{ > + _stack.push (e); > + tree t = TREE_TYPE (e); > + add_all_fields_in_struct (t); > +} > + > +void > +expr_accessor::_walk_post (__attribute__ ((unused)) tree e) > +{ > + _stack.pop (); > +} > + > +void > +expr_accessor::update (tree e, unsigned access) > +{ > + _access = access; > + walk (e); > +} > + > +/* Check if we are accessing a field > + * through pointer arithmetic. If this is happening > + * it is likely the result of an optimization. > + * Since we are not modifying these types of expressions yet > + * we must mark all fields leading to the accessed fields > + * as possibly READ. > + > + * TODO: If we modify this expression later on, we could > + * make our transformation more powerful and precise by > + * not marking all fields leading up to this one as possibly > + * read. > + */ > +void > +expr_accessor::_walk_ADDR_EXPR_pre (__attribute__ ((unused)) tree e) > +{ > + log ("expr accessor mem ref\n"); > + log ("stack size = %d\n", _stack.size ()); > + > + if (_stack.size () < 4) > + return; > + > + // TODO: Fix error with double pushing > + tree addr_expr = _stack.top (); > + _stack.pop (); > + tree twice = _stack.top (); > + _stack.pop (); > + tree prev_expr = _stack.top (); > + _stack.push (addr_expr); > + _stack.push (twice); > + log ("prev_expr code = %s\n", get_tree_code_name (TREE_CODE > (prev_expr))); > + if (TREE_CODE (prev_expr) != MEM_REF) > + return; > + > + tree op_0 = TREE_OPERAND (addr_expr, 0); > + tree addr_expr_t = TREE_TYPE (op_0); > + > + type_stringifier stringifier; > + std::string name = stringifier.stringify (addr_expr_t); > + log ("accessing a field through memref...? %s\n", name.c_str ()); > + if (TREE_CODE (addr_expr_t) != RECORD_TYPE) > + return; > + > + // We are accessing a field of a record through pointer arithmetic... > + // So what field offset are we computing... > + tree mref_expr = prev_expr; > + tree offset = TREE_OPERAND (mref_expr, 1); > + gcc_assert (TREE_CODE (offset) == INTEGER_CST); > + tree type_size_tree = TYPE_SIZE_UNIT (addr_expr_t); > + int type_size_int = tree_to_shwi (type_size_tree); > + // TODO: Very recently inserted this assertion so we need to test this > + gcc_assert (type_size_int > 0); > + unsigned offset_int = tree_to_uhwi (offset) % type_size_int; > + // We need to get the field that corresponds to the offset_int > + const bool record_already_in_map > + = record_field_map.find (addr_expr_t) != record_field_map.end (); > + field_access_map_t field_map; > + field_map = record_already_in_map ? record_field_map[addr_expr_t] : > field_map; > + > + tree field = NULL; > + for (field = TYPE_FIELDS (addr_expr_t); field; field = DECL_CHAIN > (field)) > + { > + log ("ever inside?\n"); > + unsigned f_byte_offset = tree_to_uhwi (DECL_FIELD_OFFSET (field)); > + unsigned f_offset = f_byte_offset; > + log ("offset field %d, offset by pointer %d\n", f_offset, > offset_int); > + > + // NOTE: ALL FIELDS BEFORE THIS ONE NEED TO EXIST > + // Otherwise, this pointer arithmetic is invalid... > + // After the transformation > + const bool field_already_in_map > + = field_map.find (field) != field_map.end (); > + unsigned prev_access = field_already_in_map ? field_map[field] : > Empty; > + > + prev_access |= Read; > + field_map[field] = prev_access; > + add_all_fields_in_struct (addr_expr_t); > + record_field_map[addr_expr_t] = field_map; > + > + if (f_offset == offset_int) > + break; > + } > +} > + > +/* Find out if we are taking the address of a FIELD_DECL. > + * If this is the case, it means that all FIELDS in this > + * RECORD_TYPE should be marked as READ for safety. > + */ > +void > +expr_accessor::_walk_COMPONENT_REF_pre (tree e) > +{ > + log ("in component_ref pre\n"); > + assert_is_type (e, COMPONENT_REF); > + tree op0 = TREE_OPERAND (e, 0); > + gcc_assert (op0); > + tree op0_t = TREE_TYPE (op0); > + gcc_assert (op0_t); > + // op0_t can either be a RECORD_TYPE or a UNION_TYPE. > + const enum tree_code code = TREE_CODE (op0_t); > + const bool is_record = RECORD_TYPE == code; > + const bool is_union = UNION_TYPE == code; > + const bool valid = is_record != is_union; > + gcc_assert (valid); > + > + tree op1 = TREE_OPERAND (e, 1); > + assert_is_type (op1, FIELD_DECL); > + log ("%s.%s\n", type_stringifier::get_type_identifier (op0_t).c_str(), > + type_stringifier::get_field_identifier (op1).c_str()); > + const bool record_already_in_map > + = record_field_map.find (op0_t) != record_field_map.end (); > + field_access_map_t field_map; > + field_map = record_already_in_map ? record_field_map[op0_t] : field_map; > + const bool field_already_in_map = field_map.find (op1) != > field_map.end (); > + unsigned prev_access = field_already_in_map ? field_map[op1] : Empty; > + > + prev_access |= _access; > + field_map[op1] = prev_access; > + add_all_fields_in_struct (op0_t); > + record_field_map[op0_t] = field_map; > + > + if (_stack.size () < 4) > + return; > + > + tree this_expr = _stack.top (); > + _stack.pop (); > + tree twice = _stack.top (); > + _stack.pop (); > + tree prev_expr = _stack.top (); > + _stack.push (twice); > + _stack.push (this_expr); > + if (TREE_CODE (prev_expr) != ADDR_EXPR) > + return; > + > + log ("we are taking address of a component?\n"); > + tree t = op0_t; > + if (TREE_CODE (t) != RECORD_TYPE) > + return; > + > + /* If we are taking the address of a component, we need to mark the > whole > + * RECORD_TYPE as escaping due to pointer arithmetic. > + * TODO: Maybe add a flag to enable and disable this for debugging and > + * testing. > + */ > + for (tree field = TYPE_FIELDS (t); field; field = DECL_CHAIN (field)) > + { > + log ("ever inside?\n"); > + const bool field_already_in_map > + = field_map.find (field) != field_map.end (); > + unsigned prev_access = field_already_in_map ? field_map[field] : > Empty; > + > + prev_access |= Read; > + field_map[field] = prev_access; > + add_all_fields_in_struct (t); > + record_field_map[t] = field_map; > + } > +} > + > +/* Print results. */ > +void > +expr_accessor::print_accesses () > +{ > + for (std::map<tree, field_access_map_t>::const_iterator i > + = record_field_map.begin (), > + e = record_field_map.end (); > + i != e; ++i) > + { > + tree record = i->first; > + field_access_map_t field_map = i->second; > + for (std::map<tree, unsigned>::const_iterator j > + = field_map.begin (), > + f = field_map.end (); > + j != f; ++j) > + { > + tree field = j->first; > + const std::string name_r > + = type_stringifier::get_type_identifier (record); > + const std::string name_f > + = type_stringifier::get_field_identifier (field); > + unsigned access = j->second; > + log ("%s.%s = 0x%04x\n", name_r.c_str (), name_f.c_str (), > access); > + } > + } > +} > + > +/* RECORD_TYPE -> (FIELD_DECL -> bitflag) > + * bitflag specifies if field is read, written or neither. > + */ > +record_field_map_t > +gimple_accessor::get_map () > +{ > + return _expr_accessor.get_map (); > +} > + > +void > +gimple_accessor::print_accesses () > +{ > + _expr_accessor.print_accesses (); > +} > + > +/* Mark RHS as Read and LHS as Write. */ > +void > +gimple_accessor::_walk_pre_gassign (gassign *s) > +{ > + // There seems to be quite a bit of code duplication here... > + const enum gimple_rhs_class code = gimple_assign_rhs_class (s); > + switch (code) > + { > + case GIMPLE_TERNARY_RHS: > + { > + tree rhs3 = gimple_assign_rhs3 (s); > + gcc_assert (rhs3); > + _expr_accessor.update (rhs3, Read); > + } > + /* fall-through */ > + case GIMPLE_BINARY_RHS: > + { > + tree rhs2 = gimple_assign_rhs2 (s); > + gcc_assert (rhs2); > + _expr_accessor.update (rhs2, Read); > + } > + /* fall-through */ > + case GIMPLE_UNARY_RHS: > + case GIMPLE_SINGLE_RHS: > + { > + tree rhs1 = gimple_assign_rhs1 (s); > + _expr_accessor.update (rhs1, Read); > + tree lhs = gimple_assign_lhs (s); > + if (!lhs) > + break; > + _expr_accessor.update (lhs, Write); > + break; > + } > + default: > + gcc_unreachable (); > + break; > + } > +} > + > +/* Mark RHS as Read and LHS as Written. */ > +void > +gimple_accessor::_walk_pre_gcall (gcall *s) > +{ > + unsigned n = gimple_call_num_args (s); > + for (unsigned i = 0; i < n; i++) > + { > + tree a = gimple_call_arg (s, i); > + gcc_assert (a); > + _expr_accessor.update (a, Read); > + } > + > + tree lhs = gimple_call_lhs (s); > + if (!lhs) > + return; > + _expr_accessor.update (lhs, Write); > +} > + > +/* Mark as Read. */ > +void > +gimple_accessor::_walk_pre_greturn (greturn *s) > +{ > + tree val = gimple_return_retval (s); > + if (!val) > + return; > + _expr_accessor.update (val, Read); > +} > + > +/* Mark as Read. */ > +void > +gimple_accessor::_walk_pre_gcond (gcond *s) > +{ > + tree lhs = gimple_cond_lhs (s); > + tree rhs = gimple_cond_rhs (s); > + gcc_assert (lhs && rhs); > + _expr_accessor.update (lhs, Read); > + _expr_accessor.update (rhs, Read); > +} > + > +/* Print Reasons why a type might be escaping. */ > +void > +Reason::print () const > +{ > + log ("e=%d g=%d p=%d r=%d c=%d v=%d u=%d i=%d\n", this->is_escaping (), > + this->global_is_visible, this->parameter_is_visible, > + this->return_is_visible, this->type_is_casted, > this->type_is_volatile, > + this->type_is_in_union, this->is_indirect); > +} > + > +/* Or an escaping Reason. */ > +Reason > +Reason::operator| (const Reason &other) > +{ > + Reason retval; > + retval.global_is_visible = this->global_is_visible | > other.global_is_visible; > + retval.parameter_is_visible > + = this->parameter_is_visible | other.parameter_is_visible; > + retval.return_is_visible = this->return_is_visible | > other.return_is_visible; > + retval.type_is_casted = this->type_is_casted | other.type_is_casted; > + retval.type_is_volatile = this->type_is_volatile | > other.type_is_volatile; > + retval.type_is_in_union = this->type_is_in_union | > other.type_is_in_union; > + retval.is_indirect = this->is_indirect | other.is_indirect; > + return retval; > +} > + > +/* Or an escaping Reason. */ > +Reason & > +Reason::operator|= (const Reason &other) > +{ > + this->global_is_visible |= other.global_is_visible; > + this->parameter_is_visible |= other.parameter_is_visible; > + this->return_is_visible |= other.return_is_visible; > + this->type_is_casted |= other.type_is_casted; > + this->type_is_volatile |= other.type_is_volatile; > + this->type_is_in_union |= other.type_is_in_union; > + this->is_indirect |= other.is_indirect; > + return *this; > +} > + > +/* Insert TYPE into a partition depending on IN_POINTS_TO_RECORD. */ > +void > +type_partitions_s::insert (tree type, bool in_points_to_record) > +{ > + gcc_assert (type); > + this->universe.insert (type); > + in_points_to_record ? this->points_to_record.insert (type) > + : this->complement.insert (type); > + const bool in_points_to_set = this->in_points_to_record (type); > + const bool in_complement = this->in_complement (type); > + const bool _xor = in_points_to_set != in_complement; > + // sanity check... > + gcc_assert (_xor); > +} > + > +/* Find out whether TYPE is already in universe. */ > +bool > +type_partitions_s::in_universe (tree type) const > +{ > + gcc_assert (type); > + const bool seen_before = this->universe.find (type) != > this->universe.end (); > + return seen_before; > +} > + > +/* Find out whether TYPE is in points_to_record partition. */ > +bool > +type_partitions_s::in_points_to_record (tree type) const > +{ > + gcc_assert (type); > + const bool seen_before > + = this->points_to_record.find (type) != this->points_to_record.end (); > + return seen_before; > +} > + > +/* Find out whether TYPE is not in points to record partition. */ > +bool > +type_partitions_s::in_complement (tree type) const > +{ > + gcc_assert (type); > + const bool seen_before > + = this->complement.find (type) != this->complement.end (); > + return seen_before; > +} > + > +/* Stringify a type. */ > +std::string > +type_stringifier::stringify (tree t) > +{ > + if (!dump_file) > + return std::string (""); > + _stringification.clear (); > + gcc_assert (t); > + walk (t); > + return _stringification; > +} > + > +void > +type_stringifier::_walk_VOID_TYPE_pre (tree t) > +{ > + _stringify_simple (t); > +} > + > +void > +type_stringifier::_walk_INTEGER_TYPE_pre (tree t) > +{ > + _stringify_simple (t); > +} > + > +void > +type_stringifier::_walk_REAL_TYPE_pre (tree t) > +{ > + _stringify_simple (t); > +} > + > +void > +type_stringifier::_walk_FIXED_POINT_TYPE_pre (tree t) > +{ > + _stringify_simple (t); > +} > + > +void > +type_stringifier::_walk_COMPLEX_TYPE_pre (tree t) > +{ > + _stringify_simple (t); > +} > + > +void > +type_stringifier::_walk_OFFSET_TYPE_pre (tree t) > +{ > + _stringify_simple (t); > +} > + > +void > +type_stringifier::_walk_BOOLEAN_TYPE_pre (tree t) > +{ > + _stringify_simple (t); > +} > + > +void > +type_stringifier::_stringify_simple (tree t) > +{ > + gcc_assert (t); > + const enum tree_code code = TREE_CODE (t); > + this->_stringification += std::string (get_tree_code_name (code)); > +} > + > +void > +type_stringifier::_walk_POINTER_TYPE_post (__attribute__ ((unused)) tree > t) > +{ > + this->_stringification += std::string ("*"); > +} > + > +void > +type_stringifier::_walk_ARRAY_TYPE_post (__attribute__ ((unused)) tree t) > +{ > + this->_stringification += std::string ("[]"); > +} > + > +void > +type_stringifier::_walk_REFERENCE_TYPE_post (__attribute__ ((unused)) > + tree t) > +{ > + this->_stringification += std::string ("&"); > +} > + > +void > +type_stringifier::_walk_UNION_TYPE_pre (tree t) > +{ > + this->_stringification += std::string (" union "); > + _stringify_aggregate_pre (t); > +} > + > +void > +type_stringifier::_walk_UNION_TYPE_post (tree t) > +{ > + _stringify_aggregate_post (t); > +} > + > +void > +type_stringifier::_walk_RECORD_TYPE_pre (tree t) > +{ > + this->_stringification += std::string (" record "); > + _stringify_aggregate_pre (t); > +} > + > +void > +type_stringifier::_walk_RECORD_TYPE_post (tree t) > +{ > + _stringify_aggregate_post (t); > +} > + > +void > +type_stringifier::_stringify_aggregate_pre (tree t) > +{ > + this->_stringification > + += type_stringifier::get_type_identifier (t) + std::string (" {"); > +} > + > +void > +type_stringifier::_stringify_aggregate_post (__attribute__ ((unused)) > + tree t) > +{ > + this->_stringification += std::string ("}"); > +} > + > +void > +type_stringifier::_walk_field_post (tree t) > +{ > + this->_stringification += std::string (" ") > + + type_stringifier::get_field_identifier (t) > + + std::string (";"); > +} > + > +void > +type_stringifier::_walk_METHOD_TYPE_pre (tree t) > +{ > + _stringify_fm_pre (t); > +} > + > +void > +type_stringifier::_walk_METHOD_TYPE_post (tree t) > +{ > + _stringify_fm_post (t); > +} > + > +void > +type_stringifier::_walk_FUNCTION_TYPE_pre (tree t) > +{ > + _stringify_fm_pre (t); > +} > + > +void > +type_stringifier::_walk_FUNCTION_TYPE_post (tree t) > +{ > + _stringify_fm_post (t); > +} > + > +void > +type_stringifier::_stringify_fm_pre (__attribute__ ((unused)) tree t) > +{ > + this->_stringification += std::string ("function { "); > +} > + > +void > +type_stringifier::_stringify_fm_post (__attribute__ ((unused)) tree t) > +{ > + this->_stringification += std::string ("}"); > +} > + > +void > +type_stringifier::_walk_return_pre (__attribute__ ((unused)) tree t) > +{ > + this->_stringification += std::string ("("); > +} > + > +void > +type_stringifier::_walk_return_post (__attribute__ ((unused)) tree t) > +{ > + this->_stringification += std::string (")"); > +} > + > +void > +type_stringifier::_walk_args_pre (__attribute__ ((unused)) tree t) > +{ > + this->_stringification += std::string ("("); > +} > + > +void > +type_stringifier::_walk_args_post (__attribute__ ((unused)) tree t) > +{ > + this->_stringification += std::string (")"); > +} > + > +void > +type_stringifier::_walk_arg_post (__attribute__ ((unused)) tree t) > +{ > + this->_stringification += std::string (", "); > +} > + > +std::string > +type_stringifier::get_type_identifier (tree t) > +{ > + tree name = TYPE_NAME (t); > + const bool no_name = NULL_TREE == name; > + if (no_name) > + return std::string (""); > + > + const enum tree_code name_code = TREE_CODE (name); > + const bool is_name_type_decl = TYPE_DECL == name_code; > + name = is_name_type_decl ? DECL_NAME (name) : name; > + const char *identifier_ptr = IDENTIFIER_POINTER (name); > + gcc_assert (identifier_ptr); > + return std::string (identifier_ptr); > +} > + > +std::string > +type_stringifier::get_field_identifier (tree t) > +{ > + assert_is_type (t, FIELD_DECL); > + tree decl_name = DECL_NAME (t); > + if (!decl_name) > + return std::string (""); > + > + const char *identifier = IDENTIFIER_POINTER (decl_name); > + return std::string (identifier); > +} > + > +/* Return true if L and R have equal structural equalities. */ > +bool > +type_structural_equality::equal (tree l, tree r) > +{ > + return _equal (l, r); > +} > + > +bool > +type_structural_equality::_equal (tree l, tree r) > +{ > + bool valid_inputs = l && r; > + if (!valid_inputs) > + return l == r; > + > + bool equal_codes = _equal_code (l, r); > + if (!equal_codes) > + return equal_codes; > + > + bool recurse_l = set_l.find (l) != set_l.end (); > + bool recurse_r = set_r.find (r) != set_r.end (); > + // Verify that this the case every time. > + bool recurse = recurse_l || recurse_r; > + if (recurse) > + return recurse; > + > + set_l.insert (l); > + set_r.insert (r); > + const enum tree_code code = TREE_CODE (l); > + bool equal_children = false; > + switch (code) > + { > +#define TSE_CASE(code) \ > + case code: \ > + equal_children = _walk_##code (l, r); \ > + break > + > + TSE_CASE (VOID_TYPE); > + TSE_CASE (INTEGER_TYPE); > + TSE_CASE (REAL_TYPE); > + TSE_CASE (FIXED_POINT_TYPE); > + TSE_CASE (COMPLEX_TYPE); > + TSE_CASE (ENUMERAL_TYPE); > + TSE_CASE (BOOLEAN_TYPE); > + TSE_CASE (OFFSET_TYPE); > + TSE_CASE (RECORD_TYPE); > + TSE_CASE (POINTER_TYPE); > + TSE_CASE (REFERENCE_TYPE); > + TSE_CASE (ARRAY_TYPE); > + TSE_CASE (UNION_TYPE); > + TSE_CASE (FUNCTION_TYPE); > + TSE_CASE (METHOD_TYPE); > + default: > + gcc_unreachable (); > + break; > + } > + > + set_l.erase (l); > + set_r.erase (r); > + return equal_children; > +} > + > +bool > +type_structural_equality::_equal_code (tree l, tree r) > +{ > + const enum tree_code code_l = TREE_CODE (l); > + const enum tree_code code_r = TREE_CODE (r); > + const bool equal = code_l == code_r; > + return equal; > +} > + > +#define TSE_FUNC_DEF_SIMPLE(code) \ > + bool type_structural_equality::_walk_##code (tree l, tree r) \ > + { \ > + return _equal_code (l, r); \ > + } > + > +TSE_FUNC_DEF_SIMPLE (VOID_TYPE) > +TSE_FUNC_DEF_SIMPLE (INTEGER_TYPE) > +TSE_FUNC_DEF_SIMPLE (REAL_TYPE) > +TSE_FUNC_DEF_SIMPLE (FIXED_POINT_TYPE) > +TSE_FUNC_DEF_SIMPLE (ENUMERAL_TYPE) > +TSE_FUNC_DEF_SIMPLE (BOOLEAN_TYPE) > +TSE_FUNC_DEF_SIMPLE (OFFSET_TYPE) > +TSE_FUNC_DEF_SIMPLE (COMPLEX_TYPE) > + > +bool > +type_structural_equality::_equal_wrapper (tree l, tree r) > +{ > + tree inner_l = TREE_TYPE (l); > + tree inner_r = TREE_TYPE (r); > + return _equal (inner_l, inner_r); > +} > + > +#define TSE_FUNC_DEF_WRAPPER(code) \ > + bool type_structural_equality::_walk_##code (tree l, tree r) \ > + { \ > + return _equal_wrapper (l, r); \ > + } > + > +TSE_FUNC_DEF_WRAPPER (REFERENCE_TYPE) > +TSE_FUNC_DEF_WRAPPER (ARRAY_TYPE) > +TSE_FUNC_DEF_WRAPPER (POINTER_TYPE) > + > +#define TSE_FUNC_DEF_CONTAINER(code) \ > + bool type_structural_equality::_walk_##code (tree l, tree r) \ > + { \ > + tree field_l = TYPE_FIELDS (l); \ > + tree field_r = TYPE_FIELDS (r); \ > + bool efield_l = field_l; \ > + bool efield_r = field_r; \ > + bool still_equal = efield_l == efield_r; \ > + if (!still_equal) \ > + return still_equal; \ > + \ > + while (field_l && field_r && still_equal) \ > + { > \ > + tree tfield_l = TREE_TYPE (field_l); \ > + tree tfield_r = TREE_TYPE (field_r); \ > + still_equal &= _equal (tfield_l, tfield_r); \ > + field_l = DECL_CHAIN (field_l); \ > + field_r = DECL_CHAIN (field_r); \ > + efield_l = field_l; \ > + efield_r = field_r; \ > + still_equal &= efield_l == efield_r; \ > + } > \ > + return still_equal; > \ > + } > + > +TSE_FUNC_DEF_CONTAINER (RECORD_TYPE) > +TSE_FUNC_DEF_CONTAINER (UNION_TYPE) > + > +#define TSE_FUNC_DEF_FUNC(code) > \ > + bool type_structural_equality::_walk_##code (tree l, tree r) \ > + { \ > + tree tret_l = TREE_TYPE (l); \ > + tree tret_r = TREE_TYPE (r); \ > + bool still_equal = _equal (tret_l, tret_r); > \ > + if (!still_equal) \ > + return still_equal; \ > + \ > + tree arg_l = TYPE_ARG_TYPES (l); \ > + tree arg_r = TYPE_ARG_TYPES (r); \ > + bool earg_l = arg_l; \ > + bool earg_r = arg_r; \ > + still_equal &= earg_l == earg_r; \ > + while (arg_l && arg_r && still_equal) \ > + { > \ > + tree targ_l = TREE_VALUE (arg_l); \ > + tree targ_r = TREE_VALUE (arg_r); \ > + still_equal &= _equal (targ_l, targ_r); \ > + arg_l = TREE_CHAIN (arg_l); \ > + arg_r = TREE_CHAIN (arg_r); \ > + earg_l = arg_l; \ > + earg_r = arg_r; \ > + still_equal &= earg_l == earg_r; \ > + } > \ > + return still_equal; > \ > + } > + > +TSE_FUNC_DEF_FUNC (FUNCTION_TYPE) > +TSE_FUNC_DEF_FUNC (METHOD_TYPE) > + > +/* Used for comparing incomplete types. */ > +bool > +type_incomplete_equality::_equal (tree l, tree r) > +{ > + bool valid_inputs = l && r; > + if (!valid_inputs) > + return l == r; > + > + // If any of these are incomplete, then we can only compare using > + // identifiers... > + const bool complete_l = is_complete (l); > + const bool complete_r = is_complete (r); > + bool can_compare_structurally = complete_l && complete_r; > + if (can_compare_structurally) > + return type_structural_equality::_equal (l, r); > + > + // Before comparing with identifiers > + // make last attempt to compare using main variants. > + tree m_l = TYPE_MAIN_VARIANT (l); > + tree m_r = TYPE_MAIN_VARIANT (r); > + gcc_assert (m_l && m_r); > + can_compare_structurally = m_l == m_r; > + if (can_compare_structurally) > + return true; > + > + const std::string n_l = type_stringifier::get_type_identifier (m_l); > + const std::string n_r = type_stringifier::get_type_identifier (m_r); > + return n_l.compare (n_r) == 0; > +} > + > +/* Remove non-escaping types and place in escaping types if > + * there is a tree in escaping partition which is equivalent to > + * another tree in non-escaping partition. > + * Perform this until a fixed point is reached. > + */ > +static void > +fix_escaping_types_in_set (tpartitions_t &types) > +{ > + bool fixed_point_reached = false; > + type_incomplete_equality structuralEquality; > + do > + { > + std::vector<tree> fixes; > + fixed_point_reached = true; > + for (std::set<tree>::const_iterator i = types.escaping.begin (), > + e = types.escaping.end (); > + i != e; ++i) > + { > + for (std::set<tree>::const_iterator j > + = types.non_escaping.begin (), > + f = types.non_escaping.end (); > + j != f; ++j) > + { > + tree type_esc = *i; > + gcc_assert (type_esc); > + tree type_non = *j; > + gcc_assert (type_non); > + // There can be cases where incomplete types are marked as > + // non-escaping and complete types counter parts are marked > as > + // escaping. > + const bool equal = structuralEquality.equal (type_esc, > type_non); > + if (!equal) > + continue; > + > + fixed_point_reached = false; > + // Add incomplete to escaping > + // delete incomplete from non_escaping > + // We shouldn't do that inside our iteration loop. > + fixes.push_back (type_non); > + } > + } > + > + for (std::vector<tree>::const_iterator i = fixes.begin (), > + e = fixes.end (); > + i != e; ++i) > + { > + tree escaping_type = *i; > + types.escaping.insert (escaping_type); > + types.non_escaping.erase (escaping_type); > + } > + } > + while (!fixed_point_reached); > +} > + > +simple_ipa_opt_pass * > +make_pass_ipa_type_escape_analysis (gcc::context *ctx) > +{ > + return new pass_ipa_type_escape_analysis (ctx); > +} > diff --git a/gcc/ipa-type-escape-analysis.h > b/gcc/ipa-type-escape-analysis.h > new file mode 100644 > index 00000000000..7641529bb39 > --- /dev/null > +++ b/gcc/ipa-type-escape-analysis.h > @@ -0,0 +1,1152 @@ > +/* IPA Type Escape Analysis and Dead Field Elimination > + Copyright (C) 2019-2020 Free Software Foundation, Inc. > + > + Contributed by Erick Ochoa <erick.oc...@theobroma-systems.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 3, 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 COPYING3. If not see > +<http://www.gnu.org/licenses/>. */ > + > +#ifndef GCC_IPA_TYPE_ESCAPE_ANALYSIS_H > +#define GCC_IPA_TYPE_ESCAPE_ANALYSIS_H > + > +/* Logging function, useful for debugging. */ > +void log (const char *const fmt, ...) __attribute__((format(printf, 1, > 0))); > +inline void > +log (const char *const fmt, ...) +{ > + if (!dump_file) > + return; > + > + va_list args; > + va_start (args, fmt); > + vfprintf (dump_file, fmt, args); > + fflush (dump_file); > + va_end (args); > +} > + > +/* Asserts expected gimple code is observed gimple code. */ > +inline void > +is_gimple_code (const gimple *stmt, const enum gimple_code ex_code) > +{ > + gcc_assert (stmt); > + const enum gimple_code ob_code = gimple_code (stmt); > + const bool succeeds = ex_code == ob_code; > + gcc_assert (succeeds); > +} > + > +/* Determine if type A is complete. */ > +inline bool > +is_complete (tree a) > +{ > + gcc_assert (a); > + tree type_size = TYPE_SIZE (a); > + const bool _is_complete = NULL_TREE != type_size; > + return _is_complete; > +} > + > +/* Asserts type A is complete. */ > +inline void > +assert_is_complete (tree a) > +{ > + const bool _is_complete = is_complete (a); > + gcc_assert (_is_complete); > +} > + > +/* Determine if type A is incomplete. */ > +inline bool > +is_incomplete (tree a) > +{ > + return !is_complete (a); > +} > + > +/* Assert type A has is EXPECTED_CODE. */ > +inline void > +assert_is_type (tree a, const enum tree_code expected_code) > +{ > + gcc_assert (a); > + const enum tree_code observed_code = TREE_CODE (a); > + const bool eq_codes = observed_code == expected_code; > + gcc_assert (eq_codes); > +} > + > +/* Assert STMT is of EX_CLASS enum gimple_rhs_class. */ > +inline void > +assert_is_gimple_rhs_class (const gimple *stmt, > + const enum gimple_rhs_class ex_class) > +{ > + gcc_assert (stmt); > + is_gimple_code (stmt, GIMPLE_ASSIGN); > + const enum gimple_rhs_class ob_class = gimple_assign_rhs_class (stmt); > + const bool succeeds = ex_class == ob_class; > + gcc_assert (succeeds); > +} > + > +// TODO: Rename? > +// TSET_T stands for type set. > +typedef std::set<tree> tset_t; > + > +/* Base class used for visiting tree nodes starting with root T. > + * It can handle recursive cases in the tree graph by holding > + * a set of previously seen nodes and checking before walking > + * a node. > + > + * Unlike walk_tree, TypeWalker allows users to create post-order > + * callbacks for each type of tree. > + */ > +class type_walker > +{ > +public: > + type_walker () > + {}; > + > + /* Main interface to type walker. > + * Walk type T. > + */ > + void walk (tree t); > + > +protected: > + > + /* Typeset holds previously visited nodes. */ > + tset_t tset; > + > + /* Inner walking method, used to recurse. */ > + void _walk (tree t); > + > + /* Common walking method for REFERENCE_TYPE, ARRAY_TYPE, and > POINTER_TYPE. */ > + void _walk_wrapper (tree t); > + > + /* Common walking method for RECORD_TYPE and UNION_TYPE. */ > + void _walk_record_or_union (tree t); > + > + /* Common walking method for FUNCTION_TYPE and METHOD_TYPE. */ > + virtual void _walk_function_or_method (tree t); > + > + /* If the type is memoized and we don't need to walk further down. */ > + virtual bool is_memoized (__attribute__ ((unused)) tree t) > + { > + return false; > + } > + > + /* Function definitions for different TYPEs callbacks. > + _pre is the pre-order callback. > + _post is the post-order callback. > + If you want to find a specific type in a specific order, > + (e.g. RECORD_TYPE and preorder) > + you can create a derived class and implement the function > + void _walk_RECORD_TYPE_pre (tree). > + > + walk_##code is the function that calls > + the preorder callback > + walking subtrees > + and the postorder callback. > + This is for each specific tree code. > + > + _walk_##code is the function that walks subtrees for that > + specific tree code. > + */ > +#define TypeWalkerFuncDecl(code) \ > + virtual void _walk_##code##_pre (__attribute__((unused)) tree t) \ > + {}; \ > + virtual void _walk_##code (tree t); \ > + virtual void _walk_##code##_post (__attribute__((unused)) tree t) \ > + {}; \ > + virtual void walk_##code (tree t) > + > +// NOTE the lack of semicolon here. > +// This is so that when using the macro we can use a semi-colon > +// and formatting doesn't break. > + > + /* These are the types for which we can define a pre-order > + * and post-order functions. */ > + TypeWalkerFuncDecl (VOID_TYPE); > + TypeWalkerFuncDecl (INTEGER_TYPE); > + TypeWalkerFuncDecl (REAL_TYPE); > + TypeWalkerFuncDecl (FIXED_POINT_TYPE); > + TypeWalkerFuncDecl (COMPLEX_TYPE); > + TypeWalkerFuncDecl (ENUMERAL_TYPE); > + TypeWalkerFuncDecl (BOOLEAN_TYPE); > + TypeWalkerFuncDecl (OFFSET_TYPE); > + TypeWalkerFuncDecl (RECORD_TYPE); > + TypeWalkerFuncDecl (POINTER_TYPE); > + TypeWalkerFuncDecl (REFERENCE_TYPE); > + TypeWalkerFuncDecl (ARRAY_TYPE); > + TypeWalkerFuncDecl (UNION_TYPE); > + TypeWalkerFuncDecl (FUNCTION_TYPE); > + TypeWalkerFuncDecl (METHOD_TYPE); > + > + /* These are not types, but are still trees that > + * can be reached from a tree type. Therefore, these > + * trees also need to be walked. > + */ > + TypeWalkerFuncDecl (field); > + TypeWalkerFuncDecl (return); > + TypeWalkerFuncDecl (args); > + TypeWalkerFuncDecl (arg); > +}; > + > +/* Base class for the implementation of the visitor pattern for > + * trees which are "expressions". This might be a misnomer. > + * What it means is that it walks whatever can be the result of > + * the trees returned by gimple_assign_rhs{1,2,3}, gimple_return, > + * gimple_call... > + * TODO: The expressions visited here might not be the whole set > + * but it is what was found while experimentally running some C > + * programs. > + */ > +class expr_walker > +{ > +public: > + expr_walker () > + {}; > + > + /* Walk tree E. */ > + void walk (tree e); > + > +private: > + > + /* Virtual function to be implemented. Callback for all E in > preorder. */ > + virtual void _walk_pre (__attribute__ ((unused)) tree e) > + {}; > + > + /* Inner method that will recurse for walking subtrees in E. */ > + void _walk (tree e); > + > + /* Virtual function to be implemented. Callback for all E in > postorder. */ > + virtual void _walk_post (__attribute__ ((unused)) tree e) > + {}; > + > + /* Walking subtrees generically. Either it is a leaf node, > + (i.e., it does not have subtrees), or it has some operands. > + TODO: This can probably be changed to be more general > + by finding out how many operands an expression has. > + > + tree_code C is used to assert that we are visiting an operand > + of a specific tree code. > + */ > + inline void _walk_leaf (tree e, const enum tree_code c); > + inline void _walk_op_n (tree e, unsigned n); > + inline void _walk_op_0 (tree e, const enum tree_code c); > + inline void _walk_op_1 (tree e, const enum tree_code c); > + > + /* Virtual function declarations for the pre-order and post-order > callbacks. > + * _walk_##code##_pre is the preorder callback > + * walk_##code will call the preorder, subtree walker, and postorder > + * _walk_##code is the subtree walker > + * _walk_##code##_post is the post-order callback. > + */ > +#define ExprWalkerFuncDecl(code) > \ > + virtual void _walk_##code##_pre (__attribute__ ((unused)) tree e) \ > + {}; > \ > + void walk_##code (tree e); \ > + void _walk_##code (tree e); \ > + virtual void _walk_##code##_post (__attribute__ ((unused)) tree e) \ > + {} > + > + // Some of these are not "EXPR" codes, but they are reachable > + // from gimple_assign_rhs{1,2,3} and others. > + ExprWalkerFuncDecl (CONSTRUCTOR); > + ExprWalkerFuncDecl (INTEGER_CST); > + ExprWalkerFuncDecl (REAL_CST); > + ExprWalkerFuncDecl (STRING_CST); > + ExprWalkerFuncDecl (BIT_FIELD_REF); > + ExprWalkerFuncDecl (ARRAY_REF); > + ExprWalkerFuncDecl (MEM_REF); > + ExprWalkerFuncDecl (COMPONENT_REF); > + ExprWalkerFuncDecl (SSA_NAME); > + ExprWalkerFuncDecl (ADDR_EXPR); > + ExprWalkerFuncDecl (VIEW_CONVERT_EXPR); > + ExprWalkerFuncDecl (IMAGPART_EXPR); > + ExprWalkerFuncDecl (FIELD_DECL); > + ExprWalkerFuncDecl (VAR_DECL); > + ExprWalkerFuncDecl (RESULT_DECL); > + ExprWalkerFuncDecl (PARM_DECL); > + ExprWalkerFuncDecl (FUNCTION_DECL); > + ExprWalkerFuncDecl (LE_EXPR); > + ExprWalkerFuncDecl (LT_EXPR); > + ExprWalkerFuncDecl (EQ_EXPR); > + ExprWalkerFuncDecl (GT_EXPR); > + ExprWalkerFuncDecl (GE_EXPR); > + ExprWalkerFuncDecl (NE_EXPR); > +}; > + > +/* Base class for applying the visitor pattern to gimple_stmts. > + * This class visits everything it cans during LTO. > + * That includes global variables, and all function declarations that > + * are in the current partition. > + */ > +class gimple_walker > +{ > +public: > + gimple_walker () : _deleted (false) > + {}; > + > + /* Walk the entire code, therefore no input is needed. */ > + void walk (); > + > +protected: > + /* _DELETED is set by overwritten functions that > + * delete a specific gimple stmt. This tells the > + * gimple walker to remove the gimple stmt. > + */ > + bool _deleted; > + > + /* Walk global variables. */ > + void _walk_globals (); > + > + /* Walk individual global variable V. */ > + virtual void _walk_global (varpool_node *v); > + > + /* Will walk declarations, locals, ssa names, and basic blocks. */ > + void _walk_cnode (cgraph_node *cnode); > + > + /* This will walk the CNODE->decl. */ > + void _walk_decl (cgraph_node *cnode); > + > + /* Walk ssa_names in CNODE. */ > + void _walk_ssa_names (cgraph_node *cnode); > + > + /* Walk local variables in CNODE. */ > + void _walk_locals (cgraph_node *cnode); > + > + /* Iterate over all basic blocks in CNODE. */ > + void _walk_bb (cgraph_node *cnode); > + > + /* Iterate over all gimple_stmt in BB. */ > + void _walk (basic_block bb); > + > + /* Function declarations for virtual functions. > + * These include the pre-order callbacks, walk subtrees, > + * and post-order callbacks. > + */ > + virtual void _walk_pre_tree (__attribute__((unused)) tree t) > + {}; > + void walk_tree2 (tree t); > + void _walk_tree (tree t); > + virtual void _walk_post_tree (__attribute__((unused)) tree t) > + {}; > + > + virtual void _walk_pre_gimple (__attribute__((unused)) gimple* g) > + {}; > + void walk_gimple (gimple* g); > + void _walk_gimple (gimple* g); > + virtual void _walk_post_gimple (__attribute__((unused)) gimple* g) > + {}; > + > + virtual void _walk_pre_gassign (__attribute__((unused)) gassign* g) > + {}; > + void walk_gassign (gassign* g); > + void _walk_gassign (gassign* g); > + virtual void _walk_post_gassign (__attribute__((unused)) gassign* g) > + {}; > + > + virtual void _walk_pre_greturn (__attribute__((unused)) greturn* g) > + {}; > + void walk_greturn (greturn* g); > + void _walk_greturn (greturn* g); > + virtual void _walk_post_greturn (__attribute__((unused)) greturn* g) > + {}; > + > + virtual void _walk_pre_gcond (__attribute__((unused)) gcond* g) > + {}; > + void walk_gcond (gcond* g); > + void _walk_gcond (gcond* g); > + virtual void _walk_post_gcond (__attribute__((unused)) gcond* g) > + {}; > + > + virtual void _walk_pre_glabel (__attribute__((unused)) glabel* g) > + {}; > + void walk_glabel (glabel* g); > + void _walk_glabel (glabel* g); > + virtual void _walk_post_glabel (__attribute__((unused)) glabel* g) > + {}; > + > + virtual void _walk_pre_gcall (__attribute__((unused)) gcall *g) > + {}; > + void walk_gcall (gcall *g); > + void _walk_gcall (gcall *g); > + virtual void _walk_post_gcall (__attribute__((unused)) gcall *g) > + {}; > + > + virtual void _walk_pre_gswitch (__attribute__((unused)) gswitch* g) > + {}; > + void walk_gswitch (gswitch* g); > + void _walk_gswitch (gswitch* g); > + virtual void _walk_post_gswitch (__attribute__((unused)) gswitch* g) > + {}; > + > + virtual void _walk_pre_gphi (__attribute__((unused)) gphi* g) > + {}; > + void walk_gphi (gphi* g); > + void _walk_gphi (gphi* g); > + virtual void _walk_post_gphi (__attribute__((unused)) gphi* g) > + {}; > + > +}; > + > +/* TYPE_PARTITIONS_S is a structure that is shared > + * across most of the type escape analysis. It holds > + * 4 different partitions. > + > + * 1. points to record > + * 2. complement of points to record > + * 3. escaping trees > + * 4. non escaping trees > + > + * It also has a set of all types seen so far called universe. > + > + * Ideally 1 union 2 should be universe and 3 union 4 should be universe. > + */ > +struct type_partitions_s > +{ > + /* The set of all types which have been seen. */ > + tset_t universe; > + > + /* The set of all types which somehow refer to a RECORD_TYPE. */ > + tset_t points_to_record; > + > + /* The complement of points_to_record. */ > + tset_t complement; > + > + /* The set of all escaping types. */ > + tset_t escaping; > + > + /* The set of all non escaping types. */ > + tset_t non_escaping; > + > + /* Determine if we have seen this type before. */ > + bool in_universe (tree) const; > + > + /* Determine if tree points to a record. */ > + bool in_points_to_record (tree) const; > + > + /* Determine if tree does not point to a record. */ > + bool in_complement (tree) const; > + > + /* Insert either in points to record or complement. */ > + void insert (tree, bool); > +}; > + > +typedef struct type_partitions_s tpartitions_t; > + > +/* TypeCollector is a derived class from TypeWalker > + * that collects all types reachable from T into the partitions > + * points_to_record or not points to record. > + */ > +class type_collector : public type_walker > +{ > +public: > + type_collector () > + {}; > + > + /* Main interface. */ > + void collect (tree t); > + > + /* Collect the result after walking all trees. */ > + tpartitions_t get_record_reaching_trees () > + { > + _sanity_check (); > + return ptrset; > + } > + > +private: > + /* PTR stands for points to record. Before walking into a RECORD_TYPE > + * tree, the value is always false. Once a RECORD_TYPE is visited, > + * update all values on map to be true. At post-order keys > + * will be erased. > + * Invariants: > + * before pre-order of root T map is empty > + * after post-order of root T map is empty > + > + * In other words, the contents are reset after every > + * call to collect. > + */ > + std::map<tree, bool> ptr; > + > + /* The type partition set that will hold partitions for > + * points to record or does not point to record. > + * Will be updated during post-order with the keys and values > + * from PTR. > + * This datastructure persists across calls to collect. > + */ > + tpartitions_t ptrset; > + > + /* Sanity check determines that the partitions are mutually > + * exclusive. > + */ > + void _sanity_check (); > + > + /* Store T into partition depending on PTR. */ > + void _collect_simple (tree t); > + > + /* If the value is in PTRSET, no need to visit the lower nodes. */ > + virtual bool is_memoized (tree t); > + > + /* These functions insert and erase elements in PTR. > + > + * We probably don't need to create a _pre and _post > + * function for all of them. We could probably substitute > + * one for a general *_pre and *_post method that triggers > + * for all different type T. However, we want to avoid > + * collecting FIELD_DECL, ARGS, and some other none-types. > + */ > + virtual void _walk_VOID_TYPE_pre (tree t); > + virtual void _walk_VOID_TYPE_post (tree t); > + virtual void _walk_INTEGER_TYPE_pre (tree t); > + virtual void _walk_INTEGER_TYPE_post (tree t); > + virtual void _walk_REAL_TYPE_pre (tree t); > + virtual void _walk_REAL_TYPE_post (tree t); > + virtual void _walk_FIXED_POINT_TYPE_pre (tree t); > + virtual void _walk_FIXED_POINT_TYPE_post (tree t); > + virtual void _walk_COMPLEX_TYPE_pre (tree t); > + virtual void _walk_COMPLEX_TYPE_post (tree t); > + virtual void _walk_ENUMERAL_TYPE_pre (tree t); > + virtual void _walk_ENUMERAL_TYPE_post (tree t); > + virtual void _walk_BOOLEAN_TYPE_pre (tree t); > + virtual void _walk_BOOLEAN_TYPE_post (tree t); > + virtual void _walk_ARRAY_TYPE_pre (tree t); > + virtual void _walk_ARRAY_TYPE_post (tree t); > + virtual void _walk_POINTER_TYPE_pre (tree t); > + virtual void _walk_POINTER_TYPE_post (tree t); > + virtual void _walk_REFERENCE_TYPE_pre (tree t); > + virtual void _walk_REFERENCE_TYPE_post (tree t); > + virtual void _walk_UNION_TYPE_pre (tree t); > + virtual void _walk_UNION_TYPE_post (tree t); > + virtual void _walk_FUNCTION_TYPE_pre (tree t); > + virtual void _walk_FUNCTION_TYPE_post (tree t); > + virtual void _walk_METHOD_TYPE_pre (tree t); > + virtual void _walk_METHOD_TYPE_post (tree t); > + > + /* When a RECORD_TYPE is found, update all values in PTR to true. */ > + virtual void _walk_RECORD_TYPE_pre (tree t); > + virtual void _walk_RECORD_TYPE_post (tree t); > +}; > + > +/* Derived class from TypeWalker. This class > + * will recursively print all type trees unlike just printing > + * the identifier. > + * TODO: Is this already implemented with debug_tree / print_tree? > + * If so, we can probably delete this... > + */ > +class type_stringifier : public type_walker > +{ > +public: > + type_stringifier () > + {}; > + > + /* Main method, returns a stringified version of T. */ > + std::string stringify (tree t); > + > + /* Only get type identifier. */ > + static std::string get_type_identifier (tree t); > + > + /* If field is not anonymous, return field identifier. */ > + static std::string get_field_identifier (tree t); > + > +private: > + /* Working string... will hold result for stringify. */ > + std::string _stringification; > + > + /* Append get_tree_code_name. */ > + void _stringify_simple (tree t); > + > + /* Append identifier and "{". */ > + void _stringify_aggregate_pre (tree t); > + > + /* Append "}". */ > + void _stringify_aggregate_post (tree t); > + > + /* Append "function {". */ > + // TODO: For C++ we will need to change this for methods. > + void _stringify_fm_pre (tree t); > + virtual void _walk_METHOD_TYPE_pre (tree t); > + virtual void _walk_METHOD_TYPE_post (tree t); > + virtual void _walk_FUNCTION_TYPE_pre (tree t); > + virtual void _walk_FUNCTION_TYPE_post (tree t); > + > + /* Append "}". */ > + void _stringify_fm_post (tree t); > + > + /* Most of the pre-order walk can probably be replaced by > + * a catch all pre-order call back. > + * TODO: implement that... > + */ > + virtual void _walk_VOID_TYPE_pre (tree t); > + virtual void _walk_INTEGER_TYPE_pre (tree t); > + virtual void _walk_REAL_TYPE_pre (tree t); > + virtual void _walk_FIXED_POINT_TYPE_pre (tree t); > + virtual void _walk_COMPLEX_TYPE_pre (tree t); > + virtual void _walk_BOOLEAN_TYPE_pre (tree t); > + virtual void _walk_OFFSET_TYPE_pre (tree t); > + virtual void _walk_return_pre (tree t); > + virtual void _walk_args_pre (tree t); > + > + /* Append "*". */ > + virtual void _walk_POINTER_TYPE_post (tree t); > + > + /* Append "&". */ > + virtual void _walk_REFERENCE_TYPE_post (tree t); > + > + /* Append "[]". */ > + virtual void _walk_ARRAY_TYPE_post (tree t); > + > + /* Append "record" */ > + virtual void _walk_RECORD_TYPE_pre (tree t); > + virtual void _walk_RECORD_TYPE_post (tree t); > + > + /* Append "union" */ > + virtual void _walk_UNION_TYPE_pre (tree t); > + virtual void _walk_UNION_TYPE_post (tree t); > + > + /* Append "," */ > + virtual void _walk_field_post (tree t); > + virtual void _walk_return_post (tree t); > + > + /* Append "," */ > + virtual void _walk_args_post (tree t); > + virtual void _walk_arg_post (tree t); > +}; > + > +/* ExprCollector is an implementation of ExprWalker. It walks > + * all trees in an expression and calls type collector on > + * the types for all types of nested expressions. > + */ > +class expr_collector : public expr_walker > +{ > +public: > + expr_collector () > + {}; > + > + /* Holds the result after collecting from all trees. */ > + tpartitions_t get_record_reaching_trees () > + { > + return typeCollector.get_record_reaching_trees (); > + } > + > +private: > + type_collector typeCollector; > + > + /* Catch all callback for all nested expressions E. */ > + virtual void _walk_pre (tree e); > +}; > + > +/* Derived from GimpleWalker. Its purpose is to walk all gimple > + * possible and call expression collector to collect types > + * on global variables, assign statement, return statement, > + * condition statement, and call statements. > + */ > +class gimple_type_collector : public gimple_walker > +{ > +public: > + gimple_type_collector () > + {}; > + > + /* This holds the result after walking the whole program. */ > + tpartitions_t get_record_reaching_trees () > + { > + return _expr_collector.get_record_reaching_trees (); > + } > + > + // Print final results. > + // TODO: I believe this could be made const. > + void print_collected (); > + > +private: > + expr_collector _expr_collector; > + > + /* Call back for global variables. */ > + virtual void _walk_pre_tree (tree); > + > + /* Call back for gassign. */ > + virtual void _walk_pre_gassign (gassign *s); > + > + /* Call back for greturn. */ > + virtual void _walk_pre_greturn (greturn *s); > + > + /* Call back for gcond. */ > + virtual void _walk_pre_gcond (gcond *s); > + > + /* Call back for gcall. */ > + virtual void _walk_pre_gcall (gcall *s); > +}; > + > +// Reason for why a type is escaping > +// Used in a map with corresponding trees as keys. > +// TODO: Add bit_field > +// TODO: Add has function pointer > +// TODO: Add has constructor > +struct Reason > +{ > + // Determines whether a type is escaping. > + inline bool is_escaping () const > + { > + return this->global_is_visible || this->parameter_is_visible > + || this->return_is_visible || this->type_is_casted > + || this->type_is_volatile || this->type_is_in_union > + || this->is_indirect; > + } > + > + // Escapes because a global variable is visible. > + bool global_is_visible : 1; > + > + // Escapes because a parameter is used in an > + // externally visible function. > + bool parameter_is_visible : 1; > + > + // Escapes because return value is from > + // an externally visible function. > + bool return_is_visible : 1; > + > + // Escapes because of casting. > + bool type_is_casted : 1; > + > + // Escapes because it is volatile. > + bool type_is_volatile : 1; > + > + // Escapes because it is in union. > + bool type_is_in_union : 1; > + > + // Escapes because is in indirect function call. > + bool is_indirect : 1; > + > + // Merge two reason. > + Reason operator| (const Reason &); > + Reason &operator|= (const Reason &); > + > + // Print reasons a type is escaping. > + void print () const; > + > + // Initialize as non-escaping by default. > + Reason () > + : global_is_visible (0), parameter_is_visible (0), > return_is_visible (0), > + type_is_casted (0), type_is_volatile (0), type_is_in_union (0), > + is_indirect (0) > +{}; > +}; > + > +typedef std::map<tree, Reason> typemap; > + > +/* Type Escaper propagates information on whether a type escapes > + * to all types reachable by a root type. It also propagates > + * information up if a union is found. At the moment > + * we don't transform types which point to unions. > + * We also don't transform RECORD_TYPEs which have function pointers. > + * This can possible be removed. But it is future work. > + * Do not also modify types with bit fields. > + */ > +class type_escaper : public type_walker > +{ > +public: > + type_escaper (tpartitions_t &p) > + : _ptrset (p), _inside_union (0), _inside_record (0) > + {}; > + > + // Hold the partitions for escaping non escaping. > + tpartitions_t &_ptrset; > + > + // Have information that matches a tree type with > + // why a type is escaping. > + typemap calc; > + > + // Get partitions after calculating escaping types. > + tpartitions_t get_sets (); > + > + // Print reasons why a type is escaping. > + void print_reasons (); > + > + // Update type T with escaping reason R. > + void update (tree t, Reason r); > + > + // Update type T with escaping reason R. > + void _update_single (tree t, Reason r); > + > + > +private: > + // TODO: we can probably reduce the amount of functions > + // by adding a catch all pre-order callback... > + virtual void _walk_POINTER_TYPE_pre (tree t); > + virtual void _walk_POINTER_TYPE_post (tree t); > + virtual void _walk_REFERENCE_TYPE_pre (tree t); > + virtual void _walk_ARRAY_TYPE_pre (tree t); > + virtual void _walk_ARRAY_TYPE_post (tree t); > + virtual void _walk_RECORD_TYPE_pre (tree t); > + virtual void _walk_RECORD_TYPE_post (tree t); > + virtual void _walk_field_pre (tree t); > + virtual bool is_memoized (tree t); > + > + /* Mark escaping reason as having a function pointer in a structure, > + * propagate up and down. */ > + virtual void _walk_METHOD_TYPE_pre (tree t); > + virtual void _walk_FUNCTION_TYPE_pre (tree t); > + > + /* Mark escaping reason as having a union and propagate up and down. */ > + virtual void _walk_UNION_TYPE_pre (tree t); > + virtual void _walk_UNION_TYPE_post (tree t); > + > + // Record how many nested unions the current context is in. > + unsigned _inside_union; > + > + // Record how many nested records the current context is in. > + unsigned _inside_record; > + > + // Recursive inner function. > + void _update (tree t); > + > + // Reason to be propagated to all trees reachable by root T > + // Can be updated during the walk. > + Reason _reason; > + > + > + // Final method that places types from calc to partitions. > + void place_escaping_types_in_set (); > +}; > + > +/* Visit all expressions and update reasons why they might be deleted. */ > +class expr_escaper : public expr_walker > +{ > +public: > + expr_escaper (tpartitions_t &types) : _type_escaper (types) > + {}; > + > + /* Main interface: T escapes because R. */ > + void update (tree t, Reason r); > + > + /* Will be used to propagate escaping reasons to Types. */ > + type_escaper _type_escaper; > + > + /* Holds the end result. */ > + tpartitions_t get_sets (); > + > + /* Print end result. */ > + void print_reasons (); > + > + cgraph_node *curr_node; > + > +private: > + // Keep track of the current expressions. The top of the stack > + // is the subexpression being examined. > + // The bottom of the stack is the expression called on the update > + // function. > + std::stack<tree> _stack; > + > + // Reason to propagate across all subexpressions. > + Reason _r; > + > + // push to stack. > + virtual void _walk_pre (tree e); > + > + // pop to stack. > + virtual void _walk_post (tree e); > + > + // Check if there is a cast between the > + // expression (MEM_REF (SSA_NAME)) > + // SSA_NAME is the subexpression of MEM_REF. > + virtual void _walk_SSA_NAME_pre (tree e); > + > + // If the expression E is a constructor then we need > + // to mark these types as escaping because we cannot > + // deal with constructors at the moment. > + virtual void _walk_CONSTRUCTOR_pre (tree e); > +}; > + > +// Do a type structural equality for two types. > +class type_structural_equality > +{ > +public: > + type_structural_equality () > + {}; > + > + // Return TRUE if A and B have equal structures > + bool equal (tree a, tree b); > + > +protected: > + // Recursive _equal > + virtual bool _equal (tree a, tree b); > + > +private: > + // Use to limit recursion if we are revisiting a node > + typedef std::set<tree> tset_t; > + > + // Limit recursion for LHS > + tset_t set_l; > + > + // Limit recursion for RHS > + tset_t set_r; > + > + // Determine if the code is equal > + bool _equal_code (tree a, tree b); > + > + // Wrapper around POINTER_TYPE, ARRAY_TYPE and REFERENCE_TYPE > + bool _equal_wrapper (tree a, tree b); > + > + // Different types we are comparing > +#define TSE_FUNC_DECL(code) \ > + virtual bool _walk_##code (tree l, tree r) > + > + // Current types that can be compared. > + TSE_FUNC_DECL (VOID_TYPE); > + TSE_FUNC_DECL (COMPLEX_TYPE); > + TSE_FUNC_DECL (INTEGER_TYPE); > + TSE_FUNC_DECL (REAL_TYPE); > + TSE_FUNC_DECL (FIXED_POINT_TYPE); > + TSE_FUNC_DECL (POINTER_TYPE); > + TSE_FUNC_DECL (ENUMERAL_TYPE); > + TSE_FUNC_DECL (BOOLEAN_TYPE); > + TSE_FUNC_DECL (OFFSET_TYPE); > + TSE_FUNC_DECL (RECORD_TYPE); > + TSE_FUNC_DECL (REFERENCE_TYPE); > + TSE_FUNC_DECL (ARRAY_TYPE); > + TSE_FUNC_DECL (UNION_TYPE); > + TSE_FUNC_DECL (FUNCTION_TYPE); > + TSE_FUNC_DECL (METHOD_TYPE); > +}; > + > +// Check for equality even when a type is incomplete. > +// When one type is incomplete and MAIN_VARIANTS are different > +// compare only with identifiers. > +// Unsound but it is as sound as it can be. > +class type_incomplete_equality : public type_structural_equality > +{ > +public: > + type_incomplete_equality () > + {}; > + > +protected: > + virtual bool _equal (tree l, tree r); > +}; > + > +/* Inspect gimple code and find reasons why types might escape given a > gimple > + * stmt. */ > +class gimple_escaper : public gimple_walker > +{ > +public: > + gimple_escaper (tpartitions_t &types) : _expr_escaper (types) > + { > + _init (); > + }; > + > + /* Propagate escaping reason to subexpressions. */ > + expr_escaper _expr_escaper; > + > + /* Obtain final result. */ > + tpartitions_t get_sets (); > + > + /* Print final result. */ > + void print_reasons (); > + > +protected: > + /* Set of undefined functions, this set is filled with > + * functions obtained via FOR_EACH_FUNCTION_WITH_GIMPLE_BODY. */ > + typedef std::set<tree> undefset; > + undefset undefined; > + > + /* Initializes undefined. */ > + void _init (); > + > + /* Return true if it is a known builtin function. */ > + static bool filter_known_function (cgraph_node *); > + static bool filter_known_function (tree); > + > + /* Return true if function is externally visible. */ > + static bool is_function_escaping (cgraph_node *); > + static bool is_function_escaping (tree); > + > + /* Return true if variable is externally visible. */ > + static bool is_variable_escaping (varpool_node *); > + > + /* Marks global variables with CONSTRUCTORS and ERROR_MARKs as > escaping. */ > + virtual void _walk_global (varpool_node *); > + > + /* Do not escape on assignments. */ > + virtual void _walk_pre_gassign (gassign *s); > + > + /* Do not escape return values. */ > + virtual void _walk_pre_greturn (greturn *s); > + > + /* Do not escape gcond. */ > + virtual void _walk_pre_gcond (gcond *s); > + > + /* Mark arguments and return type as escaping > + * if callsite is undefined, indirect or externally visible. */ > + virtual void _walk_pre_gcall (gcall *s); > + > + /* Mark T as escaping if is in UNKNOWN_LOCATION. > + * This is a way of finding > + * types introduced by profiling and mark them as escaping. > + * TODO: Improve this. > + */ > + virtual void _walk_pre_tree (tree t); > +}; > + > +/* > + * GimpleCaster is intended to walk gimple > + * and update a map that will hold information > + * on whether a type was casted or not. > + */ > +class gimple_caster : public gimple_escaper > +{ > +public: > + gimple_caster (tpartitions_t &types) : gimple_escaper (types) > +{}; > + > +private: > + /* Determine if cast comes from a known function. */ > + static bool follow_def_to_find_if_really_cast (tree); > + > + /* If arguments are casted, mark them as escaping. > + * Assignments from malloc and other known functions > + * are allowed. > + * */ > + virtual void _walk_pre_gcall (gcall *s); > + > + /* If assignment is casted, mark them as escaping. > + * Assignments from malloc and other known functions > + * are allowed. > + */ > + virtual void _walk_pre_gassign (gassign *s); > +}; > + > +// Bitflags used for determining if a field is > +// never accessed, read or written. > +// TODO: Place on their own namespace? > +const unsigned Empty = 0x0u; > +const unsigned Read = 0x01u; > +const unsigned Write = 0x02u; > + > +// maps FIELD_DECL -> bitflag. > +typedef std::map<tree, unsigned> field_access_map_t; > + > +// maps RECORD_TYPE -> (FIELD_DECL -> bitflag). > +typedef std::map<tree, field_access_map_t> record_field_map_t; > + > +// Class used to determine if a FIELD is read, written or never accessed. > +class type_accessor : public type_walker > +{ > +public: > + type_accessor (record_field_map_t &map) : _map (map) > + {}; > + > +private: > + // maps RECORD -> (FIELD_DECL -> bitflag). > + record_field_map_t &_map; > + > + // set of trees which are memoized and we don't need to look into them. > + std::set<tree> memoized_map; > + > + // If a RECORD_TYPE is walked into, add all fields in struct to > + // record_field_map. > + virtual void _walk_RECORD_TYPE_pre (tree t); > + void add_all_fields_in_struct (tree t); > + > + bool is_memoized (tree t); > +}; > + > +// Determine if a FIELD is read, written or never accessed from > +// an expression. > +class expr_accessor : public expr_walker > +{ > +public: > + expr_accessor () : _type_accessor (record_field_map) > + {}; > + > + // Expr E is accessed in A manner. > + void update (tree e, unsigned a); > + > + // Print results. > + void print_accesses (); > + > + // Add all fields to map. Initialize with empty. > + void add_all_fields_in_struct (tree t); > + > + // Get final results. > + record_field_map_t get_map (); > + > +private: > + // Access {"Read", "Write", "Neither"} to propagate to all > subexpressions. > + unsigned _access; > + > + // Stack to keep track of how current subexpression was reached. > + std::stack<tree> _stack; > + > + // Holds main results. > + record_field_map_t record_field_map; > + > + // Aids expr-accessor in updating types. > + type_accessor _type_accessor; > + > + // Mark FIELD_DECL as read. > + // If ADDR_EXPR is parent expression that means > + // The address of a field is taken. Mark > + // all fields as possibly read. > + virtual void _walk_COMPONENT_REF_pre (tree e); > + > + // Check if parent expression is MEM_REF. > + // This means that an optimization was made > + // and a FIELD_DECL is accessed via pointer > + // arithmetic. Mark all fields from start to the one > + // accessed as read. > + // TODO: We don't necessarily need to mark them as > + // possibly read if we update these expressions to > + // point to the correct address in the future. > + virtual void _walk_ADDR_EXPR_pre (tree e); > + > + // Push to stack. > + virtual void _walk_pre (tree t); > + > + // Pop from stack. > + virtual void _walk_post (tree t); > +}; > + > +/* Walk all gimple and determine if fields were accessed. */ > +class gimple_accessor : public gimple_walker > +{ > +public: > + gimple_accessor () > + {}; > + > + /* Print final results. */ > + void print_accesses (); > + > + /* Get final results. */ > + record_field_map_t get_map (); > + > +private: > + /* Navigate expressions in gimple statements. */ > + expr_accessor _expr_accessor; > + > + /* Mark all RHS expressions reachable from S as Read. > + all all LHS expressions reachable from S as Written. */ > + virtual void _walk_pre_gcall (gcall *s); > + > + /* Mark all RHS expressions reachable from S as Read. > + Mark all LHS expressions reachable from S as Written. */ > + virtual void _walk_pre_gassign (gassign *s); > + > + /* Mark all all expressions reachable from S as read. */ > + virtual void _walk_pre_greturn (greturn *s); > + > + /* Mark all expressions reachable from S as read. */ > + virtual void _walk_pre_gcond (gcond *s); > + > + // Do we need a glabel? I don't think so... > + // But we might need a gswitch. > +}; > + > +typedef std::set<unsigned> field_offsets_t; > + > +typedef std::map<tree, field_offsets_t> record_field_offset_map_t; > + > + > +#endif /* GCC_IPA_TYPE_ESCAPE_ANALYSIS_H */ > diff --git a/gcc/passes.def b/gcc/passes.def > index c68231287b6..a1cf09229d6 100644 > --- a/gcc/passes.def > +++ b/gcc/passes.def > @@ -172,6 +172,7 @@ along with GCC; see the file COPYING3. If not see > passes are executed after partitioning and thus see just parts of > the > compiled unit. */ > INSERT_PASSES_AFTER (all_late_ipa_passes) > + NEXT_PASS (pass_ipa_type_escape_analysis); > NEXT_PASS (pass_ipa_pta); > NEXT_PASS (pass_omp_simd_clone); > TERMINATE_PASS_LIST (all_late_ipa_passes) > diff --git a/gcc/timevar.def b/gcc/timevar.def > index a3031799700..5bda34d8efe 100644 > --- a/gcc/timevar.def > +++ b/gcc/timevar.def > @@ -81,6 +81,7 @@ DEFTIMEVAR (TV_IPA_INLINING , "ipa inlining > heuristics") > DEFTIMEVAR (TV_IPA_FNSPLIT , "ipa function splitting") > DEFTIMEVAR (TV_IPA_COMDATS , "ipa comdats") > DEFTIMEVAR (TV_IPA_OPT , "ipa various optimizations") > +DEFTIMEVAR (TV_IPA_STRUCTURE_REORG , "ipa structure reorg") > DEFTIMEVAR (TV_IPA_LTO_DECOMPRESS , "lto stream decompression") > DEFTIMEVAR (TV_IPA_LTO_COMPRESS , "lto stream compression") > DEFTIMEVAR (TV_IPA_LTO_OUTPUT , "lto stream output") > diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h > index 9cb22acc243..f1a7dc6758e 100644 > --- a/gcc/tree-pass.h > +++ b/gcc/tree-pass.h > @@ -515,6 +515,8 @@ extern ipa_opt_pass_d *make_pass_ipa_devirt > (gcc::context *ctxt); > extern ipa_opt_pass_d *make_pass_ipa_odr (gcc::context *ctxt); > extern ipa_opt_pass_d *make_pass_ipa_reference (gcc::context *ctxt); > extern ipa_opt_pass_d *make_pass_ipa_pure_const (gcc::context *ctxt); > +extern simple_ipa_opt_pass * > +make_pass_ipa_type_escape_analysis (gcc::context *ctxt); > extern simple_ipa_opt_pass *make_pass_ipa_pta (gcc::context *ctxt); > extern simple_ipa_opt_pass *make_pass_ipa_tm (gcc::context *ctxt); > extern simple_ipa_opt_pass *make_pass_target_clone (gcc::context *ctxt); > -- > 2.18.1 > >
