[3/7] LTO Dead field elimination and field reordering

Erick Ochoa erick.ochoa@theobroma-systems.com
Wed Nov 4 13:28:00 GMT 2020


 From 91947eea01a41bd7b17e501ad7d53dfb6499eefc 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/7] 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                  |  84 ++++-
  gcc/ipa-dfe.h                  |  26 +-
  gcc/ipa-field-reorder.c        | 625 +++++++++++++++++++++++++++++++++
  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, 751 insertions(+), 48 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 39bb6e100c3..035c1e8850f 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -3484,4 +3484,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 c048fac8621..16f594a36b9 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;

@@ -405,14 +408,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);
  }

@@ -468,7 +477,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);
@@ -521,7 +532,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);
@@ -616,7 +629,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;
@@ -628,8 +642,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);
@@ -710,6 +725,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;
@@ -746,6 +764,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);
@@ -778,7 +811,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:
@@ -800,9 +834,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;
  }
@@ -1024,9 +1061,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);

@@ -1080,6 +1119,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 ();
@@ -1089,12 +1130,14 @@ ExprTypeRewriter::_walk_COMPONENT_REF_post 
(const_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 = 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
@@ -1241,7 +1284,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 2472d474869..2b43bc5763a 100644
--- a/gcc/ipa-dfe.h
+++ b/gcc/ipa-dfe.h
@@ -72,7 +72,8 @@ typedef std::map<const_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.  */
@@ -87,7 +88,8 @@ public:
    /* Map RECORD_TYPE -> is_modified.  */
    typedef std::map<const_tree, bool> is_modified_map_t;

-private:
+protected:
+  const char *get_new_suffix ();

    // Modifications to the current sub_type
    std::stack<tree> 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 (),
@@ -181,6 +188,7 @@ public:
    // Delete statement.
    bool delete_statement ();
    bool _delete;
+  bool _can_delete;

  private:
    // Old RECORD_TYPE -> new RECORD_TYPE.
@@ -210,8 +218,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 ();
@@ -245,6 +254,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..611089ecf24
--- /dev/null
+++ b/gcc/ipa-field-reorder.c
@@ -0,0 +1,625 @@
+/* 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_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 = 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);
+}
diff --git a/gcc/ipa-type-escape-analysis.c b/gcc/ipa-type-escape-analysis.c
index e8464a61c80..9944580da6c 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 <vector>
  #include <set>
  #include <map>
@@ -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
@@ -2643,9 +2637,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 0af6bf5443a..38e3a36cefd 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<unsigned> field_offsets_t;

  typedef std::map<const_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