From 08bed62633d76681eafb7630216a6cce22e30fa2 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Sun, 9 Aug 2020 10:22:49 +0200 Subject: Add Field Reordering Field reordering of structs at link-time --- gcc/Makefile.in | 1 + gcc/common.opt | 4 + gcc/ipa-dfe.c | 84 ++++-- gcc/ipa-dfe.h | 26 +- gcc/ipa-field-reorder.c | 622 +++++++++++++++++++++++++++++++++++++++++ gcc/ipa-type-escape-analysis.c | 44 ++- gcc/ipa-type-escape-analysis.h | 12 +- gcc/passes.def | 1 + gcc/tree-pass.h | 1 + 9 files changed, 747 insertions(+), 48 deletions(-) create mode 100644 gcc/ipa-field-reorder.c diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 4377a2856d0..d6b4c8af65e 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1410,6 +1410,7 @@ OBJS = \ internal-fn.o \ ipa-type-escape-analysis.o \ ipa-dfe.o \ + ipa-field-reorder.o \ ipa-cp.o \ ipa-sra.o \ ipa-devirt.o \ diff --git a/gcc/common.opt b/gcc/common.opt index fe16c2105d4..7eb8150a258 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -3488,4 +3488,8 @@ fprint-access-analysis Common Report Var(flag_print_access_analysis) Optimization This flag is used to print the access analysis (if field is read or written to). +fipa-field-reorder +Common Report Var(flag_ipa_field_reorder) Optimization +Reorder fields. + ; This comment is to ensure we retain the blank line above. diff --git a/gcc/ipa-dfe.c b/gcc/ipa-dfe.c index 47d80d73a10..08e20f73f45 100644 --- a/gcc/ipa-dfe.c +++ b/gcc/ipa-dfe.c @@ -242,9 +242,9 @@ get_types_replacement (record_field_offset_map_t record_field_offset_map, */ void substitute_types_in_program (reorg_record_map_t map, - reorg_field_map_t field_map) + reorg_field_map_t field_map, bool _delete) { - GimpleTypeRewriter rewriter (map, field_map); + GimpleTypeRewriter rewriter (map, field_map, _delete); rewriter.walk (); rewriter._rewrite_function_decl (); } @@ -358,8 +358,11 @@ TypeReconstructor::set_is_not_modified_yet (const_tree t) return; tree type = _reorg_map[tt]; - const bool is_modified + bool is_modified = strstr (TypeStringifier::get_type_identifier (type).c_str (), ".reorg"); + is_modified + |= (bool) strstr (TypeStringifier::get_type_identifier (type).c_str (), + ".reorder"); if (!is_modified) return; @@ -404,14 +407,20 @@ TypeReconstructor::is_memoized (const_tree t) return already_changed; } -static tree -get_new_identifier (const_tree type) +const char * +TypeReconstructor::get_new_suffix () +{ + return _suffix; +} + +tree +get_new_identifier (const_tree type, const char *suffix) { const char *identifier = TypeStringifier::get_type_identifier (type).c_str (); - const bool is_new_type = strstr (identifier, "reorg"); + const bool is_new_type = strstr (identifier, suffix); gcc_assert (!is_new_type); char *new_name; - asprintf (&new_name, "%s.reorg", identifier); + asprintf (&new_name, "%s.%s", identifier, suffix); return get_identifier (new_name); } @@ -467,7 +476,9 @@ TypeReconstructor::_walk_ARRAY_TYPE_post (const_tree t) TREE_TYPE (copy) = build_variant_type_copy (TREE_TYPE (copy)); copy = is_modified ? build_distinct_type_copy (copy) : copy; TREE_TYPE (copy) = is_modified ? _reorg_map[TREE_TYPE (t)] : TREE_TYPE (copy); - TYPE_NAME (copy) = is_modified ? get_new_identifier (copy) : TYPE_NAME (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); tree domain = TYPE_DOMAIN (t); @@ -520,7 +531,9 @@ TypeReconstructor::_walk_POINTER_TYPE_post (const_tree t) copy = is_modified ? build_variant_type_copy (copy) : copy; TREE_TYPE (copy) = is_modified ? _reorg_map[TREE_TYPE (t)] : TREE_TYPE (copy); - TYPE_NAME (copy) = is_modified ? get_new_identifier (copy) : TYPE_NAME (copy); + TYPE_NAME (copy) = is_modified + ? get_new_identifier (copy, this->get_new_suffix ()) + : TYPE_NAME (copy); TYPE_CACHED_VALUES_P (copy) = false; tree _t = const_tree_to_tree (t); @@ -614,7 +627,8 @@ TypeReconstructor::_walk_RECORD_TYPE_post (const_tree t) tree main = TYPE_MAIN_VARIANT (t); tree main_reorg = _reorg_map[main]; tree copy_variant = build_variant_type_copy (main_reorg); - TYPE_NAME (copy_variant) = get_new_identifier (copy); + TYPE_NAME (copy_variant) + = get_new_identifier (copy, this->get_new_suffix ()); TYPE_SIZE (copy_variant) = NULL; TYPE_MAIN_VARIANT (copy_variant) = main_reorg; TYPE_SIZE (main_reorg) = NULL; @@ -626,8 +640,9 @@ TypeReconstructor::_walk_RECORD_TYPE_post (const_tree t) // 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) : TYPE_NAME (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); @@ -708,6 +723,9 @@ ExprTypeRewriter::_walk_PARM_DECL_post (const_tree t) { tree temp = const_tree_to_tree (t); tree ttemp = TREE_TYPE (temp); + TypeStringifier stringifier; + const char *name = stringifier.stringify (ttemp).c_str (); + log ("relayout parameter declaration %s\n", name); const bool is_interesting = is_interesting_type (ttemp); if (!is_interesting) return; @@ -744,6 +762,21 @@ ExprTypeRewriter::_walk_FUNCTION_DECL_post (const_tree t) void ExprTypeRewriter::_walk_MEM_REF_post (const_tree e) { + tree op0 = TREE_OPERAND (e, 0); + tree t2 = TREE_TYPE (op0); + const bool in_map2 = _map.find (t2) != _map.end (); + + log ("trying out substituting expression in component_Ref directly\n"); + TypeStringifier stringifier; + log ("mem_ref doing weird things maybe %s\n", + stringifier.stringify (t2).c_str ()); + if (in_map2) + { + log ("success\n"); + tree r_t = _map[t2]; + tree _e = const_tree_to_tree (op0); + TREE_TYPE (_e) = r_t; + } // The second operand is a pointer constant. // Its type specifying the type used for type based alias analysis tree op1 = TREE_OPERAND (e, 1); @@ -776,7 +809,8 @@ ExprTypeRewriter::_walk_MEM_REF_post (const_tree e) = old_offset / old_type_size_int * reorg_type_size_int + remainder; tree new_offset_tree = build_int_cst (TREE_TYPE (op1), new_offset); - TREE_OPERAND (e, 1) = new_offset_tree; + tree _e = const_tree_to_tree (e); + TREE_OPERAND (_e, 1) = new_offset_tree; } // TODO: @@ -798,9 +832,12 @@ ExprTypeRewriter::is_interesting_type (tree t) // Let's just do a quick sanity check tree interesting_type = t; - const bool has_valid_suffix + bool has_valid_suffix = strstr (TypeStringifier::get_type_identifier (interesting_type).c_str (), ".reorg"); + has_valid_suffix |= (bool) + strstr (TypeStringifier::get_type_identifier (interesting_type).c_str (), + ".reorder"); gcc_assert (has_valid_suffix); return true; } @@ -1022,9 +1059,11 @@ ExprTypeRewriter::handle_pointer_arithmetic_constants (gimple *s, tree p, const_tree original_type = _imap[reorg_type]; // If we are here, that means that our type has the ".reorg" suffix // Let's add a sanity check - const bool has_suffix + bool has_suffix = strstr (TypeStringifier::get_type_identifier (reorg_type).c_str (), ".reorg"); + has_suffix |= (bool) strstr ( + TypeStringifier::get_type_identifier (reorg_type).c_str (), ".reorder"); bool is_valid_input = has_suffix; gcc_assert (is_valid_input); @@ -1078,6 +1117,8 @@ ExprTypeRewriter::_walk_post (const_tree e) void ExprTypeRewriter::_walk_COMPONENT_REF_post (const_tree e) { + gcc_assert (e); + const_tree f = TREE_OPERAND (e, 1); // So, what we need is a map between this field and the new field const bool in_map = _map2.find (f) != _map2.end (); @@ -1087,12 +1128,14 @@ ExprTypeRewriter::_walk_COMPONENT_REF_post (const_tree e) std::pair p = _map2[f]; tree n_f = p.first; bool is_deleted = p.second; - TREE_OPERAND (e, 1) = n_f; + tree _e = const_tree_to_tree (e); + TREE_OPERAND (_e, 1) = n_f; if (!is_deleted) return; - _delete = true; + _delete = _can_delete && true; + log ("are we deleting? %s %s\n", _delete ? "t" : "f", is_deleted ? "t" : "f"); } void @@ -1239,7 +1282,14 @@ GimpleTypeRewriter::_walk_pre_gassign (gassign *s) { case POINTER_PLUS_EXPR: case POINTER_DIFF_EXPR: + log ("am i handling pointer arithmetic?\n"); + if (dump_file) + print_gimple_stmt (dump_file, s, 0); + log ("\n"); handle_pointer_arithmetic (s); + if (dump_file) + print_gimple_stmt (dump_file, s, 0); + log ("\n"); break; default: break; diff --git a/gcc/ipa-dfe.h b/gcc/ipa-dfe.h index 74cf8bfa863..b00575c5003 100644 --- a/gcc/ipa-dfe.h +++ b/gcc/ipa-dfe.h @@ -72,7 +72,8 @@ typedef std::map > reorg_field_map_t; class TypeReconstructor : public TypeWalker { public: - TypeReconstructor (record_field_offset_map_t records) : _records (records) + TypeReconstructor (record_field_offset_map_t records, const char *suffix) + : _records (records), _suffix (suffix) {}; /* Whether a type has already been modified. */ @@ -87,7 +88,8 @@ public: /* Map RECORD_TYPE -> is_modified. */ typedef std::map is_modified_map_t; -private: +protected: + const char *get_new_suffix (); // Modifications to the current sub_type std::stack in_progress; @@ -108,6 +110,9 @@ private: // Which records can be modified. record_field_offset_map_t _records; + // The new suffix + const char *_suffix; + // Which fields will be deleted. field_tuple_list_stack_t field_list_stack; @@ -130,6 +135,7 @@ private: // If the type has been modified. bool get_is_modified (const_tree); +private: // Compute new FIELD_DECL list. virtual void _walk_field_pre (const_tree); virtual void _walk_field_post (const_tree); @@ -153,8 +159,9 @@ private: class ExprTypeRewriter : public ExprWalker { public: - ExprTypeRewriter (reorg_record_map_t map, reorg_field_map_t map2) - : _delete (false), _map (map), _map2 (map2) + ExprTypeRewriter (reorg_record_map_t map, reorg_field_map_t map2, + bool can_delete) + : _delete (false), _can_delete (can_delete), _map (map), _map2 (map2) { /* Create an inverse map new RECORD_TYPE -> old RECORD_TYPE. */ for (reorg_record_map_t::iterator i = map.begin (), e = map.end (); i != e; ++i) @@ -180,6 +187,7 @@ public: // Delete statement. bool delete_statement (); bool _delete; + bool _can_delete; private: // Old RECORD_TYPE -> new RECORD_TYPE. @@ -209,8 +217,9 @@ private: class GimpleTypeRewriter : public GimpleWalker { public: - GimpleTypeRewriter (reorg_record_map_t map, reorg_field_map_t map2) - : exprTypeRewriter (map, map2) + GimpleTypeRewriter (reorg_record_map_t map, reorg_field_map_t map2, + bool can_delete) + : exprTypeRewriter (map, map2, can_delete) {}; void _rewrite_function_decl (); @@ -244,6 +253,9 @@ get_types_replacement (record_field_offset_map_t record_field_offset_map, // Substitute types. void substitute_types_in_program (reorg_record_map_t map, - reorg_field_map_t field_map); + reorg_field_map_t field_map, bool _delete); + +tree +get_new_identifier (const_tree type, const char *suffix); #endif /* GCC_IPA_DFE */ 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 + +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 +. */ + +/* 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 +#include +#include +#include +#include + +#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 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::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::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 to_modify) +{ + TypeStringifier stringifier; + + TypeReconstructorFieldReordering reconstructor (record_field_offset_map, + "reorder"); + for (std::set::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_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_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 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); +} diff --git a/gcc/ipa-type-escape-analysis.c b/gcc/ipa-type-escape-analysis.c index a9deb05cc5f..a961fb40d3d 100644 --- a/gcc/ipa-type-escape-analysis.c +++ b/gcc/ipa-type-escape-analysis.c @@ -161,6 +161,7 @@ along with GCC; see the file COPYING3. If not see #include "gimple-iterator.h" #include "gimple-ssa.h" #include "gimple-pretty-print.h" +#include "tree-cfg.h" #include #include #include @@ -177,10 +178,6 @@ lto_dfe_execute (); 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 (); @@ -193,11 +190,6 @@ fix_escaping_types_in_set (tpartitions_t &types); 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? @@ -269,7 +261,7 @@ lto_dead_field_elimination () 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); + record_field_map, OPT_Wdfa); if (record_field_offset_map.empty ()) return; @@ -282,8 +274,7 @@ lto_dead_field_elimination () reorg_record_map_t map = replacements.first; reorg_field_map_t field_map = replacements.second; // Transformation. - substitute_types_in_program (map, field_map); - + substitute_types_in_program (map, field_map, true); } /* Iterate all gimple bodies and collect trees @@ -304,7 +295,7 @@ partition_types_into_record_reaching_or_non_record_reaching () /* Iterate over all gimple bodies and find out * which types are escaping AND are being casted. */ -static tpartitions_t +tpartitions_t partition_types_into_escaping_nonescaping () { tpartitions_t partitions @@ -327,8 +318,7 @@ partition_types_into_escaping_nonescaping () * which fields are accessed for all RECORD_TYPE * types. */ -static record_field_map_t -find_fields_accessed () +record_field_map_t static find_fields_accessed () { GimpleAccesser accesser; accesser.walk (); @@ -498,9 +488,10 @@ mark_escaping_types_to_be_deleted ( } // Obtain nonescaping unaccessed fields -static record_field_offset_map_t +record_field_offset_map_t obtain_nonescaping_unaccessed_fields (tpartitions_t casting, - record_field_map_t record_field_map) + record_field_map_t record_field_map, + int _warning) { bool has_fields_that_can_be_deleted = false; record_field_offset_map_t record_field_offset_map; @@ -560,10 +551,11 @@ obtain_nonescaping_unaccessed_fields (tpartitions_t casting, TypeStringifier::get_type_identifier (record).c_str (), TypeStringifier::get_field_identifier (field).c_str ()); - if (OPT_Wdfa == 0) continue; + if (_warning == 0) + continue; // Anonymous fields? (Which the record can be!). - warning (OPT_Wdfa, "RECORD_TYPE %qE has dead field %qE in LTO.\n", - record, field); + warning (_warning, "RECORD_TYPE %qE has dead field %qE in LTO.\n", + record, field); } record_field_offset_map[record] = field_offset; } @@ -1182,6 +1174,8 @@ GimpleWalker::walk () if (already_in_set) continue; + if (dump_file) + dump_function_to_file (node->decl, dump_file, TDF_NONE); _walk_cnode (node); fndecls.insert (decl); } @@ -1403,8 +1397,8 @@ GimpleWalker::_walk_gimple (gimple *stmt) const enum gimple_code code = gimple_code (stmt); switch (code) { - case GIMPLE_PREDICT: case GIMPLE_DEBUG: + case GIMPLE_PREDICT: case GIMPLE_NOP: // I think it is safe to skip these // but it would also be nice to walk their sub-trees @@ -2641,9 +2635,13 @@ ExprAccessor::_walk_ADDR_EXPR_pre (__attribute__ ((unused)) const_tree e) for (field = TYPE_FIELDS (addr_expr_t); field; field = DECL_CHAIN (field)) { log ("ever inside?\n"); + // This is a weird result... 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); + unsigned f_bit_offset = tree_to_uhwi (DECL_FIELD_BIT_OFFSET (field)) / 8; + unsigned f_offset = f_byte_offset + f_bit_offset; + // unsigned f_offset = bitpos_of_field (field); + log ("offset field %d %d, offset by pointer %d \n ", f_offset, + f_bit_offset, offset_int); // NOTE: ALL FIELDS BEFORE THIS ONE NEED TO EXIST // Otherwise, this pointer arithmetic is invalid... diff --git a/gcc/ipa-type-escape-analysis.h b/gcc/ipa-type-escape-analysis.h index 17a0a51d817..5faa723a6a6 100644 --- a/gcc/ipa-type-escape-analysis.h +++ b/gcc/ipa-type-escape-analysis.h @@ -1128,10 +1128,11 @@ public: /* Get final results. */ record_field_map_t get_map (); -private: +protected: /* Navigate expressions in gimple statements. */ ExprAccessor exprAccessor; +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); @@ -1154,5 +1155,14 @@ typedef std::set field_offsets_t; typedef std::map record_field_offset_map_t; +// Partition types into escaping or non escaping sets. +tpartitions_t +partition_types_into_escaping_nonescaping (); + +// Compute set of not escaping unaccessed fields +record_field_offset_map_t +obtain_nonescaping_unaccessed_fields (tpartitions_t casting, + record_field_map_t record_field_map, + int warning); #endif /* GCC_IPA_TYPE_ESCAPE_ANALYSIS_H */ diff --git a/gcc/passes.def b/gcc/passes.def index 67d2520c1f8..f93c589b124 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -172,6 +172,7 @@ along with GCC; see the file COPYING3. If not see INSERT_PASSES_AFTER (all_late_ipa_passes) NEXT_PASS (pass_materialize_all_clones); NEXT_PASS (pass_ipa_type_escape_analysis); + NEXT_PASS (pass_ipa_field_reorder); NEXT_PASS (pass_ipa_structure_reorg); NEXT_PASS (pass_ipa_prototype); NEXT_PASS (pass_ipa_pta); diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index bcb7e921eac..5871c43bb75 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -511,6 +511,7 @@ 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_structure_reorg (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_field_reorder (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); -- cgit v1.2.3