[PATCH 3/6] Add Field Reordering
Erick Ochoa
erick.ochoa@theobroma-systems.com
Fri Nov 6 14:31:05 GMT 2020
From 72e6ea57b04ca2bf223faef262b478dc407cdca7 Mon Sep 17 00:00:00 2001
From: Erick Ochoa <erick.ochoa@theobroma-systems.com>
Date: Sun, 9 Aug 2020 10:22:49 +0200
Subject: [PATCH 3/6] Add Field Reordering
Field reordering of structs at link-time
2020-11-04 Erick Ochoa <erick.ochoa@theobroma-systems.com>
* gcc/Makefile.in: add new file to list of sources
* gcc/common.opt: add new flag for field reordering
* gcc/passes.def: add new pass
* gcc/tree-pass.h: same
* gcc/ipa-field-reorder.c: New file
* gcc/ipa-type-escape-analysis.c: Export common functions
* gcc/ipa-type-escape-analysis.h: Same
---
gcc/Makefile.in | 1 +
gcc/common.opt | 4 +
gcc/ipa-dfe.c | 86 ++++-
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 | 2 +
9 files changed, 749 insertions(+), 49 deletions(-)
create mode 100644 gcc/ipa-field-reorder.c
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 8ef6047870b..2184bd0fc3d 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1417,6 +1417,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 85351738a29..7885d0f5c0c 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -3468,4 +3468,8 @@ Wdfa
Common Var(warn_dfa) Init(1) Warning
Warn about dead fields at link time.
+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 31a5066f1b5..5602ee667d4 100644
--- a/gcc/ipa-dfe.c
+++ b/gcc/ipa-dfe.c
@@ -185,7 +185,7 @@ get_types_replacement (record_field_offset_map_t
record_field_offset_map,
{
TypeStringifier stringifier;
- TypeReconstructor reconstructor (record_field_offset_map);
+ TypeReconstructor reconstructor (record_field_offset_map, "reorg");
for (std::set<tree>::const_iterator i = to_modify.begin (),
e = to_modify.end ();
i != e; ++i)
@@ -245,9 +245,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 ();
}
@@ -361,8 +361,11 @@ TypeReconstructor::set_is_not_modified_yet (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;
@@ -408,14 +411,20 @@ TypeReconstructor::is_memoized (tree t)
return already_changed;
}
-static tree
-get_new_identifier (tree type)
+const char *
+TypeReconstructor::get_new_suffix ()
+{
+ return _suffix;
+}
+
+tree
+get_new_identifier (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);
}
@@ -471,7 +480,9 @@ TypeReconstructor::_walk_ARRAY_TYPE_post (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);
@@ -524,7 +535,9 @@ TypeReconstructor::_walk_POINTER_TYPE_post (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 = tree_to_tree (t);
@@ -619,7 +632,8 @@ TypeReconstructor::_walk_RECORD_TYPE_post (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;
@@ -631,8 +645,9 @@ TypeReconstructor::_walk_RECORD_TYPE_post (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);
@@ -713,6 +728,9 @@ ExprTypeRewriter::_walk_PARM_DECL_post (tree t)
{
tree temp = 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;
@@ -749,6 +767,21 @@ ExprTypeRewriter::_walk_FUNCTION_DECL_post (tree t)
void
ExprTypeRewriter::_walk_MEM_REF_post (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 = 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);
@@ -781,7 +814,8 @@ ExprTypeRewriter::_walk_MEM_REF_post (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 = tree_to_tree (e);
+ TREE_OPERAND (_e, 1) = new_offset_tree;
}
// TODO:
@@ -803,9 +837,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;
}
@@ -1027,9 +1064,11 @@
ExprTypeRewriter::handle_pointer_arithmetic_constants (gimple *s, tree p,
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);
@@ -1083,6 +1122,8 @@ ExprTypeRewriter::_walk_post (tree e)
void
ExprTypeRewriter::_walk_COMPONENT_REF_post (tree e)
{
+ gcc_assert (e);
+
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 ();
@@ -1092,12 +1133,14 @@ ExprTypeRewriter::_walk_COMPONENT_REF_post (tree e)
std::pair<tree, bool> p = _map2[f];
tree n_f = p.first;
bool is_deleted = p.second;
- TREE_OPERAND (e, 1) = n_f;
+ tree _e = 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
@@ -1244,7 +1287,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 b5886003b15..e5ef0cfc230 100644
--- a/gcc/ipa-dfe.h
+++ b/gcc/ipa-dfe.h
@@ -69,7 +69,8 @@ typedef std::map<tree, std::pair<tree, bool> >
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. */
@@ -84,7 +85,8 @@ public:
/* Map RECORD_TYPE -> is_modified. */
typedef std::map<tree, bool> is_modified_map_t;
-private:
+protected:
+ const char *get_new_suffix ();
// Modifications to the current sub_type
std::stack<tree> in_progress;
@@ -105,6 +107,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;
@@ -127,6 +132,7 @@ private:
// If the type has been modified.
bool get_is_modified (tree);
+private:
// Compute new FIELD_DECL list.
virtual void _walk_field_pre (tree);
virtual void _walk_field_post (tree);
@@ -150,8 +156,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 (),
@@ -178,6 +185,7 @@ public:
// Delete statement.
bool delete_statement ();
bool _delete;
+ bool _can_delete;
private:
// Old RECORD_TYPE -> new RECORD_TYPE.
@@ -207,8 +215,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 ();
@@ -242,6 +251,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 (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..4c1ddc6d0e3
--- /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 <string>
+#include <vector>
+#include <set>
+#include <map>
+#include <stack>
+#include <algorithm>
+#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"
+#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 (tree);
+};
+
+/* Compare FIELD_DECL tree based on TYPE_SIZE unit. */
+static bool
+compare_FIELD_DECLs_TYPE_SIZE (tree _l, tree _r)
+{
+ gcc_assert (_l && _r);
+
+ tree l = tree_to_tree (_l);
+ tree r = 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 (tree t)
+{
+ 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<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 (
+ (tree) copy_node (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<tree>::iterator j = to_reorder.begin (),
+ f = to_reorder.end (); j != f; ++j)
+ {
+ entered_loop = true;
+ tree current_field_inner = *j;
+ if (!prev_field)
+ {
+ TYPE_FIELDS (copy) = tree_to_tree (current_field_inner);
+ }
+ else
+ {
+ DECL_CHAIN (prev_field)
+ = tree_to_tree (current_field_inner);
+ }
+
+ prev_field = tree_to_tree (current_field_inner);
+ }
+
+ if (entered_loop)
+ break;
+ }
+
+ // Modify _reorg_fields map
+ for (std::vector<tree>::iterator i = to_reorder.begin (),
+ e = to_reorder.end (); i != e; ++i)
+ {
+ tree to_find = *i;
+ unsigned to_find_i = bitpos_of_field (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 (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_ALIAS_SET (copy_variant) = -1;
+ 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 = 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:
+ {
+ tree rhs3 = gimple_assign_rhs3 (s);
+ gcc_assert (rhs3);
+ exprAccessor.update (rhs3, Empty);
+ }
+ /* fall-through */
+ case GIMPLE_BINARY_RHS:
+ {
+ tree rhs2 = gimple_assign_rhs2 (s);
+ gcc_assert (rhs2);
+ exprAccessor.update (rhs2, Empty);
+ }
+ /* fall-through */
+ case GIMPLE_UNARY_RHS:
+ case GIMPLE_SINGLE_RHS:
+ {
+ tree rhs1 = gimple_assign_rhs1 (s);
+ exprAccessor.update (rhs1, Empty);
+ 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++)
+ {
+ tree a = gimple_call_arg (s, i);
+ gcc_assert (a);
+ exprAccessor.update (a, Empty);
+ }
+
+ 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)
+{
+ 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)
+{
+ tree lhs = gimple_cond_lhs (s);
+ 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 ();
+
+ // 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<tree> to_modify)
+{
+ TypeStringifier stringifier;
+
+ TypeReconstructorFieldReordering reconstructor (record_field_offset_map,
+ "reorder");
+ for (std::set<tree>::const_iterator i = to_modify.begin (),
+ e = to_modify.end ();
+ i != e; ++i)
+ {
+ tree record = *i;
+ reconstructor.walk (TYPE_MAIN_VARIANT (record));
+ }
+
+ for (std::set<tree>::const_iterator i = to_modify.begin (),
+ e = to_modify.end ();
+ i != e; ++i)
+ {
+ 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<tree, tree>::const_iterator i = map.begin (),
+ e = map.end ();
+ i != e; ++i)
+ {
+ 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 = 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<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);
+}
diff --git a/gcc/ipa-type-escape-analysis.c b/gcc/ipa-type-escape-analysis.c
index 3852545a8bd..aec7b924533 100644
--- a/gcc/ipa-type-escape-analysis.c
+++ b/gcc/ipa-type-escape-analysis.c
@@ -166,6 +166,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 "ipa-type-escape-analysis.h"
#include "ipa-dfe.h"
@@ -178,10 +179,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 ();
@@ -194,11 +191,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
@@ -323,8 +314,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 ();
@@ -490,9 +480,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;
@@ -552,10 +543,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;
}
@@ -1174,6 +1166,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);
}
@@ -1395,8 +1389,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
@@ -2631,9 +2625,13 @@ ExprAccessor::_walk_ADDR_EXPR_pre (__attribute__
((unused)) 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 17e9ac8f9d7..0058c145793 100644
--- a/gcc/ipa-type-escape-analysis.h
+++ b/gcc/ipa-type-escape-analysis.h
@@ -1125,10 +1125,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);
@@ -1151,5 +1152,14 @@ typedef std::set<unsigned> field_offsets_t;
typedef std::map<tree, field_offsets_t> 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 a1cf09229d6..156421aa837 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -173,6 +173,7 @@ along with GCC; see the file COPYING3. If not see
compiled unit. */
INSERT_PASSES_AFTER (all_late_ipa_passes)
NEXT_PASS (pass_ipa_type_escape_analysis);
+ NEXT_PASS (pass_ipa_field_reorder);
NEXT_PASS (pass_ipa_pta);
NEXT_PASS (pass_omp_simd_clone);
TERMINATE_PASS_LIST (all_late_ipa_passes)
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index f1a7dc6758e..4392e099359 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -517,6 +517,8 @@ 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_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);
--
2.18.1
More information about the Gcc-patches
mailing list