diff options
Diffstat (limited to 'gcc/ipa-field-reorder.c')
| -rw-r--r-- | gcc/ipa-field-reorder.c | 622 |
1 files changed, 622 insertions, 0 deletions
diff --git a/gcc/ipa-field-reorder.c b/gcc/ipa-field-reorder.c new file mode 100644 index 00000000000..f67928f012f --- /dev/null +++ b/gcc/ipa-field-reorder.c @@ -0,0 +1,622 @@ +/* IPA Type Escape Analysis and Dead Field Elimination + Copyright (C) 2019-2020 Free Software Foundation, Inc. + + Contributed by Erick Ochoa <erick.ochoa@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 field reordering + + The goal of this transformation is to re-order fields in structures + at link time. + + The field reordering transformation allows to reduce the memory + footprint of structs, which not only improves performance, but also memory + consumption. So this is an interesting feature on embedded systems with + tight memory constraints. + + First stage - DFA + ================= + + Use DFA to compute the set of FIELD_DECLs which can be reordered. + This is different from IPA-DFE in that all reads do not prevent reordering + of fields, with the exception of those which take the address of a field + or those in MEM_REF. Therefore ExprEscaper remains the same, but + GimpleCaster is modified. + + Second stage - Reorder fields + ============================= + + Use TypeReconstructorFieldReordering to reorder fields. + + Third stage - Substitute Types and Relayout + =========================================== + + Change all types changed and references to FIELD_DECLs + */ + +#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 <vector> +#include <set> +#include <map> +#include <stack> +#include <algorithm> + +#include "ipa-type-escape-analysis.h" +#include "ipa-dfe.h" + +// 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))); +} + +/* Basically we are creating a specialized GimpleAccesser for FieldReordering. + * Here instead of marking fields as "READ" or "WRITE", we are marking them as + * "READ" via pointer arithmetic. Other "READS" and "WRITES" are ignored since + * it would be possible to reorder the fields. + */ +class GimpleAccesserFieldReordering : public GimpleAccesser +{ +public: + GimpleAccesserFieldReordering (){}; + +private: + /* 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. +}; + +/* Class used to create new types derived from types that might be + * reordered. + */ +class TypeReconstructorFieldReordering : public TypeReconstructor +{ +public: + TypeReconstructorFieldReordering (record_field_offset_map_t records, + const char *suffix) + : TypeReconstructor (records, suffix) + {}; + +private: + // Compute new RECORD_TYPE. + virtual void _walk_RECORD_TYPE_post (const_tree); +}; + +/* Compare FIELD_DECL tree based on TYPE_SIZE unit */ +static bool +compare_FIELD_DECLs_TYPE_SIZE (const_tree _l, const_tree _r) +{ + gcc_assert (_l && _r); + + tree l = const_tree_to_tree (_l); + tree r = const_tree_to_tree (_r); + + const enum tree_code code_l = TREE_CODE (l); + const enum tree_code code_r = TREE_CODE (r); + const bool is_left_field_decl = code_l == FIELD_DECL; + const bool is_right_field_decl = code_r == FIELD_DECL; + bool is_valid = is_left_field_decl && is_right_field_decl; + gcc_assert (is_valid); + + tree type_l = TREE_TYPE (l); + tree type_r = TREE_TYPE (r); + const bool is_type_l = TYPE_P (type_l); + const bool is_type_r = TYPE_P (type_r); + is_valid = is_type_l && is_type_r; + gcc_assert (is_valid); + + tree size_l = TYPE_SIZE_UNIT (type_l); + tree size_r = TYPE_SIZE_UNIT (type_r); + is_valid = size_l && size_r; + gcc_assert (is_valid); + + int int_l = tree_to_shwi (size_l); + int int_r = tree_to_shwi (size_r); + const bool is_gte_l = int_l >= 0; + const bool is_gte_r = int_r >= 0; + is_valid = is_gte_l && is_gte_r; + gcc_assert (is_valid); + + return int_l > int_r; +} + +void +TypeReconstructorFieldReordering::_walk_RECORD_TYPE_post (const_tree t) +{ + const_tree t2 = for_reference.top (); + gcc_assert (t2 == t); + for_reference.pop (); + + tree copy = in_progress.top (); + in_progress.pop (); + field_tuple_list_t field_tuple_list = field_list_stack.top (); + field_list_stack.pop (); + + // So, here all the work has been done to make sure + // that the fields produced a field_tuple_list_t + // with old fields and pointers to new fields. + // There might be NULL values if new fields are that can be resorted.. + // So, now we want to do a couple of things. + // First, collect all fields in a struct and make a copy of them + bool is_modified = get_is_modified (t); + std::vector<const_tree> to_reorder; + is_modified = true; + for (field_tuple_list_t::iterator i = field_tuple_list.begin (), e = field_tuple_list.end (); + i != e; ++i) + { + field_tuple_t field_tuple = *i; + tree modified_field = field_tuple.second; + + if (!modified_field) + { + // This means that the field can be re-ordered... + is_modified = true; + } + + log ("we can reorder %s ? %s\n", + TypeStringifier::get_field_identifier (field_tuple.first).c_str (), + !modified_field ? "true" : "false"); + to_reorder.push_back ( + (const_tree) copy_node (const_tree_to_tree (field_tuple.first))); + } + + if (is_modified) + { + tree prev_field = NULL; + bool entered_loop = false; + // Sort them + std::sort (to_reorder.begin (), to_reorder.end (), + compare_FIELD_DECLs_TYPE_SIZE); + is_modified = false; + + for (field_tuple_list_t::iterator i = field_tuple_list.begin (), e = field_tuple_list.end (); + i != e; ++i) + { + field_tuple_t field_tuple = *i; + tree modified_field = field_tuple.second; + + if (!modified_field) + { + // This means that the field can be re-ordered... + is_modified = true; + } + + tree current_field = modified_field; + if (!is_modified) + { + prev_field = current_field; + continue; + } + + gcc_assert (!modified_field && is_modified); + // Create new TYPE_FIELDS with the order we want + for (std::vector<const_tree>::iterator j = to_reorder.begin (), f = to_reorder.end (); j != f; ++j) + { + entered_loop = true; + const_tree current_field_inner = *j; + if (!prev_field) + { + TYPE_FIELDS (copy) = const_tree_to_tree (current_field_inner); + } + else + { + DECL_CHAIN (prev_field) + = const_tree_to_tree (current_field_inner); + } + + prev_field = const_tree_to_tree (current_field_inner); + } + + if (entered_loop) + break; + } + + // Modify _reorg_fields map + for (std::vector<const_tree>::iterator i = to_reorder.begin (), e = to_reorder.end (); i != e; ++i) + { + const_tree to_find = *i; + unsigned to_find_i = bitpos_of_field (const_tree_to_tree (to_find)); + const char *to_find_str + = TypeStringifier::get_field_identifier (to_find).c_str (); + // O^2 for now but an improvement can be to change this + for (tree field = TYPE_FIELDS (t); field; field = DECL_CHAIN (field)) + { + // safe for anonymous structs + const char *haystack + = TypeStringifier::get_field_identifier (field).c_str (); + unsigned haystack_i = bitpos_of_field (field); + if (haystack_i == to_find_i) + { + _reorg_fields[field] + = std::make_pair (const_tree_to_tree (to_find), false); + log ("substituting %s for %s\n", to_find_str, haystack); + } + } + } + } + + const bool is_main_variant = TYPE_MAIN_VARIANT (t) == t; + // We already must have done the main variant... + if (!is_main_variant) + { + tree main = TYPE_MAIN_VARIANT (t); + tree main_reorg = _reorg_map[main]; + tree copy_variant = build_distinct_type_copy (main_reorg); + TYPE_NAME (copy_variant) + = get_new_identifier (copy, this->get_new_suffix ()); + TYPE_SIZE (copy_variant) = NULL; + //TYPE_SIZE (main_reorg) = NULL; + TypeStringifier stringifier; + std::string name_o = stringifier.stringify(main_reorg); + std::string name_r = stringifier.stringify(copy_variant); + log ("before layout main_reorged %s\n", name_o.c_str()); + log ("there is a type alias set %s\n", TYPE_ALIAS_SET_KNOWN_P(main_reorg) == 0 ? "T" : "F"); + log ("before layout reorg %s\n", name_r.c_str()); + TYPE_ALIAS_SET(copy_variant) = -1; + log ("there is a type alias set %s\n", TYPE_ALIAS_SET_KNOWN_P(copy_variant) == 0 ? "T" : "F"); + layout_type (copy_variant); + TYPE_MAIN_VARIANT (copy_variant) = main_reorg; + _reorg_map[t] = copy_variant; + } + else + { + // Ok, so now that we have fixed the TYPE_FIELDS of the copy... + // We need to call layout_type + copy = is_modified ? build_distinct_type_copy (copy) : copy; + TYPE_NAME (copy) = is_modified + ? get_new_identifier (copy, this->get_new_suffix ()) + : TYPE_NAME (copy); + // This is useful so that we go again through type layout + TYPE_SIZE (copy) = is_modified ? NULL : TYPE_SIZE (copy); + TYPE_MAIN_VARIANT (copy) = is_modified ? copy : TYPE_MAIN_VARIANT (copy); + if (is_modified) + layout_type (copy); + tree _t = const_tree_to_tree (t); + _reorg_map[t] = is_modified ? copy : _t; + } + + tree record = _reorg_map[t]; + for (tree field = TYPE_FIELDS (record); field; field = DECL_CHAIN (field)) + { + relayout_decl (field); + log ("new offset for %s %d\n", + TypeStringifier::get_field_identifier (field).c_str (), + bitpos_of_field (field)); + } +} + +/* Mark all as empty (a.k.a. we can sort) */ +void +GimpleAccesserFieldReordering::_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: + { + const_tree rhs3 = gimple_assign_rhs3 (s); + gcc_assert (rhs3); + exprAccessor.update (rhs3, Empty); + } + /* fall-through */ + case GIMPLE_BINARY_RHS: + { + const_tree rhs2 = gimple_assign_rhs2 (s); + gcc_assert (rhs2); + exprAccessor.update (rhs2, Empty); + } + /* fall-through */ + case GIMPLE_UNARY_RHS: + case GIMPLE_SINGLE_RHS: + { + const_tree rhs1 = gimple_assign_rhs1 (s); + exprAccessor.update (rhs1, Empty); + const_tree lhs = gimple_assign_lhs (s); + if (!lhs) + break; + exprAccessor.update (lhs, Empty); + break; + } + default: + gcc_unreachable (); + break; + } +} + +/* Mark all as empty (a.k.a. we can sort) */ +void +GimpleAccesserFieldReordering::_walk_pre_gcall (gcall *s) +{ + unsigned n = gimple_call_num_args (s); + for (unsigned i = 0; i < n; i++) + { + const_tree a = gimple_call_arg (s, i); + gcc_assert (a); + exprAccessor.update (a, Empty); + } + + const_tree lhs = gimple_call_lhs (s); + if (!lhs) + return; + exprAccessor.update (lhs, Empty); +} + +/* Mark all as empty (a.k.a. we can sort) */ +void +GimpleAccesserFieldReordering::_walk_pre_greturn (greturn *s) +{ + const_tree val = gimple_return_retval (s); + if (!val) + return; + exprAccessor.update (val, Empty); +} + +/* Mark all as empty (a.k.a. we can sort) */ +void +GimpleAccesserFieldReordering::_walk_pre_gcond (gcond *s) +{ + const_tree lhs = gimple_cond_lhs (s); + const_tree rhs = gimple_cond_rhs (s); + gcc_assert (lhs && rhs); + exprAccessor.update (lhs, Empty); + exprAccessor.update (rhs, Empty); +} + +/* Top level function. */ +static unsigned int +lto_fr_execute (); + +static record_field_map_t +find_fields_accessed (); + +namespace { +const pass_data pass_data_ipa_field_reorder = { + SIMPLE_IPA_PASS, + "field-reorder", + OPTGROUP_NONE, + TV_NONE, + (PROP_cfg | PROP_ssa), + 0, + 0, + 0, + 0, +}; + +class pass_ipa_field_reorder : public simple_ipa_opt_pass +{ +public: + pass_ipa_field_reorder (gcc::context *ctx) + : simple_ipa_opt_pass (pass_data_ipa_field_reorder, ctx) + {} + + virtual bool gate (function *) { return in_lto_p && flag_ipa_field_reorder; } + virtual unsigned execute (function *) { return lto_fr_execute (); } +}; +} // namespace + +record_field_map_t static find_fields_accessed () +{ + GimpleAccesserFieldReordering accesser; + accesser.walk (); + + // Dump for debugging. + if (flag_print_access_analysis) + accesser.print_accesses (); + + // 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; +} + +/* record_field_offset_map holds information on which FIELD_DECLs might be + * resorted from RECORD_TYPEs. to_modify holds trees which point to a + * RECORD_TYPE which might be resorted. From these two inputs, we need to + * compute two maps: + * * a map of RECORD_TYPE (old) -> RECORD_TYPE (new) + * * a map of FIELD_DECL (old) -> FIELD_DECL (new) + + * The first maps trees in to_modify (which point to RECORD_TYPEs (old)) to + * trees which have been modified to point to the new definition of + * RECORD_TYPEs. + + * The second maps old FIELD_DECLs trees to the new FIELD_DECLs. + */ +reorg_maps_t +get_reordered_field_maps (record_field_offset_map_t record_field_offset_map, + std::set<const_tree> to_modify) +{ + TypeStringifier stringifier; + + TypeReconstructorFieldReordering reconstructor (record_field_offset_map, + "reorder"); + for (std::set<const_tree>::const_iterator i = to_modify.begin (), + e = to_modify.end (); + i != e; ++i) + { + const_tree record = *i; + reconstructor.walk (TYPE_MAIN_VARIANT (record)); + } + + for (std::set<const_tree>::const_iterator i = to_modify.begin (), + e = to_modify.end (); + i != e; ++i) + { + const_tree record = *i; + reconstructor.walk (record); + } + + reorg_record_map_t map = reconstructor.get_map (); + reorg_field_map_t field_map = reconstructor.get_field_map (); + + // Here, we are just making sure that we are not doing anything too crazy. + // Also, we found some types for which TYPE_CACHED_VALUES_P is not being + // rewritten. This is probably indicative of a bug in + // TypeReconstructorFieldReordering. + for (std::map<const_tree, tree>::const_iterator i = map.begin (), + e = map.end (); + i != e; ++i) + { + const_tree o_record = i->first; + std::string o_name = stringifier.stringify (o_record); + log ("original: %s\n", o_name.c_str ()); + tree r_record = i->second; + std::string r_name + = r_record ? stringifier.stringify (r_record) : std::string (""); + log ("modified: %s\n", r_name.c_str ()); + if (!r_record) + continue; + tree m_record = TYPE_MAIN_VARIANT (r_record); + // Info: We had a bug where some TYPED_CACHED_VALUES were preserved? + tree _o_record = const_tree_to_tree (o_record); + TYPE_CACHED_VALUES_P (_o_record) = false; + TYPE_CACHED_VALUES_P (m_record) = false; + + bool in_map = map.find (m_record) != map.end (); + if (!in_map) + continue; + tree mm_record = map[m_record]; + // Info: I think this is no longer needed... + // Please verify + TYPE_MAIN_VARIANT (r_record) = mm_record; + } + + return std::make_pair (map, field_map); +} + +/* Top level function. */ +static unsigned int +lto_fr_execute () +{ + log ("here in field reordering \n"); + // Analysis. + 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, 0); + + if (record_field_offset_map.empty ()) + return 0; + + // Prepare for transformation. + std::set<const_tree> to_modify + = get_all_types_pointing_to (record_field_offset_map, + escaping_nonescaping_sets); + + reorg_maps_t replacements + = get_reordered_field_maps (record_field_offset_map, to_modify); + reorg_record_map_t map = replacements.first; + reorg_field_map_t field_map = replacements.second; + substitute_types_in_program (map, field_map, false); + + GimpleWalker walker; + walker.walk (); + log ("finished!\n"); + + return 0; +} + +simple_ipa_opt_pass * +make_pass_ipa_field_reorder (gcc::context *ctx) +{ + return new pass_ipa_field_reorder (ctx); +} |