[PATCH 0/8 v4] LTO Dead Field Elimination and Field Reordering

[Erick Ochoa]

Hello,

I'm sharing the most recent version of dead-field elimination. In this 
patchset the following issues have been addressed:


* CamelCase -> snake_case
* STL -> GCC specific data structures
* Fixed the commit messages (the last two commits will be squashed in 
future patchset so the commit messages are not really relevant.)


The only criticism that I have not addressed is the use of my own 
visitors for trees and gimple instructions. My position is still that 
the current visitor (for trees) is not enough to address our needs. The 
visitor implemented here has pre and post traversal hooks. Furthermore, 
there is a visitor exclusively for tree expressions and another for tree 
types, which can allow users to focus on a specific tree traversal.


There is one single STL use and that is std::string which is used when 
serializing tree types. I'd would love to keep this since preppending 
and appending std::strings is so easy and it is really only used when 
dumping debug information. (Well, technically two uses of STL, but I 
have seen std::pair being used elsewhere in the repo, so I believe it is 
ok?)


The last two commits will be squashed across the other commits (i.e., no 
patch will ever include references to STL beyond std::string and 
std::pair) and some small issues will be fixed (i.e., some names will 
change and I will remove the use of auto).


I will be running tests this weekend to make sure nothing broke, but 
initial (fast) testing seems to indicate that everything is working 
correctly.


So, why am I sharing this now? I am hoping to provide a follow up to 
those interested in this transformation and I am hoping to receive more 
feedback in order to make this pass something which the community 
values. Please, let me know your comments, questions, concerns, etc...


-Erick

Re: Dead Field Elimination and Field Reordering

[Erick Ochoa]

Hello,

I will be posting today some changes on the patches mailing list. I 
believe that due to some changes in the way clones are materialized, the 
transformation now supports IPA-SRA by default. I still need to test 
this more thoroughly, but initial tests show that this is no longer an 
issue.


After this, I will be removing std data structures and using specific ones.

If anyone have any comments about the transformation, please let me 
know. I am happy to answer questions.


-Erick

On 06.11.20 05:51, Erick Ochoa wrote:

Hi Richard,

just some top-level comments before I write about anything specific:

* I have removed all non-essential flags I introduced
* I have placed the standard headers before config
* I have squashed some changes that I sent to the patches mailing list 
and make sure that the transformation bootstraps on every commit
* I will be sending another set of patches to the patch mailing list 
soon that have the changes mentioned above.


Things I will be working on the next couple of days:

* Removing std datastructures and using GCC specific ones.
* Adding support for ipa-sra.
* Flattening the visitors.

On 05/11/2020 14:10, Richard Biener wrote:

On Tue, Nov 3, 2020 at 5:21 PM Erick Ochoa
 wrote:


Thanks for the review Richard I'll address what I can. I also provide
maybe some hindsight into some of the design decisions here. I'm not
trying to be defensive just hoping to illuminate why some decisions were
made and how some criticisms may fail to really address the reason why
these designs were made.

On 03/11/2020 15:58, Richard Biener wrote:

On Fri, Oct 30, 2020 at 6:44 PM Erick Ochoa
 wrote:


Hello again,

I've been working on several implementations of data layout
optimizations for GCC, and I am again kindly requesting for a 
review of

the type escape based dead field elimination and field reorg.

Thanks to everyone that has helped me. The main differences between 
the
previous commits have been fixing the style, adding comments 
explaining
classes and families of functions, exit gracefully if we handle 
unknown

gimple syntax, and added a heuristic to handle void* casts.

This patchset is organized in the following way:

* Adds a link-time warning if dead fields are detected
* Allows for the dead-field elimination transformation to be applied
* Reorganizes fields in structures.
* Adds some documentation
* Gracefully does not apply transformation if unknown syntax is 
detected.

* Adds a heuristic to handle void* casts

I have tested this transformations as extensively as I can. The way to
trigger these transformations are:

-fipa-field-reorder and -fipa-type-escape-analysis

Having said that, I welcome all criticisms and will try to address 
those
criticisms which I can. Please let me know if you have any 
questions or

comments, I will try to answer in a timely manner.

The code is in:

 refs/vendors/ARM/heads/arm-struct-reorg-wip

Future work includes extending the current heuristic with ipa-modref
extending the analysis to use IPA-PTA as discussed previously.

Few notes:

* Currently it is not safe to use -fipa-sra.
* I added some tests which are now failing by default. This is because
there is no way to safely determine within the test case that a layout
has been transformed. I used to determine that a field was eliminated
doing pointer arithmetic on the fields. And since that is not safe, 
the
analysis decides not to apply the transformation. There is a way to 
deal
with this (add a flag to allow the address of a field to be taken) 
but I

wanted to hear other possibilities to see if there is a better option.
* At this point we’d like to thank the again GCC community for their
patient help so far on the mailing list and in other channels. And we
ask for your support in terms of feedback, comments and testing.


I've only had a brief look at the branch - if you want to even have a
remote chance of making this stage1 you should break the branch
up into a proper patch series and post it with appropriate ChangeLogs
and descriptions.

First, standard includes may _not_ be included after including 
system.h,

in fact, they _need_ to be included from system.h - that includes
things like  or .  There are "convenient" defines you
can use like

#define INCLUDE_SET
#include "system.h"

and system.h will do what you want.  Not to say that you should
use GCCs containers and not the standard library ones.


Thanks I didn't know this!



You expose way too many user-visible command-line options.


Yes, I can certainly remove some debugging flags.



All the stmt / tree walking "meta" code should be avoided - it
would need to be touched each time we change GIMPLE or
GENERIC.  Instead use available walkers if you really need
it in such DFS-ish way.


There are two points being made here:
1. Use the available walkers
2. Changing gimple would imply changes to your code

First:

I did tried using the available walkers in the past, and the walk_tree
function does not contain a 

Re: Dead Field Elimination and Field Reordering

[Erick Ochoa]

Hi Richard,

just some top-level comments before I write about anything specific:

* I have removed all non-essential flags I introduced
* I have placed the standard headers before config
* I have squashed some changes that I sent to the patches mailing list 
and make sure that the transformation bootstraps on every commit
* I will be sending another set of patches to the patch mailing list 
soon that have the changes mentioned above.


Things I will be working on the next couple of days:

* Removing std datastructures and using GCC specific ones.
* Adding support for ipa-sra.
* Flattening the visitors.

On 05/11/2020 14:10, Richard Biener wrote:

On Tue, Nov 3, 2020 at 5:21 PM Erick Ochoa
 wrote:


Thanks for the review Richard I'll address what I can. I also provide
maybe some hindsight into some of the design decisions here. I'm not
trying to be defensive just hoping to illuminate why some decisions were
made and how some criticisms may fail to really address the reason why
these designs were made.

On 03/11/2020 15:58, Richard Biener wrote:

On Fri, Oct 30, 2020 at 6:44 PM Erick Ochoa
 wrote:


Hello again,

I've been working on several implementations of data layout
optimizations for GCC, and I am again kindly requesting for a review of
the type escape based dead field elimination and field reorg.

Thanks to everyone that has helped me. The main differences between the
previous commits have been fixing the style, adding comments explaining
classes and families of functions, exit gracefully if we handle unknown
gimple syntax, and added a heuristic to handle void* casts.

This patchset is organized in the following way:

* Adds a link-time warning if dead fields are detected
* Allows for the dead-field elimination transformation to be applied
* Reorganizes fields in structures.
* Adds some documentation
* Gracefully does not apply transformation if unknown syntax is detected.
* Adds a heuristic to handle void* casts

I have tested this transformations as extensively as I can. The way to
trigger these transformations are:

-fipa-field-reorder and -fipa-type-escape-analysis

Having said that, I welcome all criticisms and will try to address those
criticisms which I can. Please let me know if you have any questions or
comments, I will try to answer in a timely manner.

The code is in:

 refs/vendors/ARM/heads/arm-struct-reorg-wip

Future work includes extending the current heuristic with ipa-modref
extending the analysis to use IPA-PTA as discussed previously.

Few notes:

* Currently it is not safe to use -fipa-sra.
* I added some tests which are now failing by default. This is because
there is no way to safely determine within the test case that a layout
has been transformed. I used to determine that a field was eliminated
doing pointer arithmetic on the fields. And since that is not safe, the
analysis decides not to apply the transformation. There is a way to deal
with this (add a flag to allow the address of a field to be taken) but I
wanted to hear other possibilities to see if there is a better option.
* At this point we’d like to thank the again GCC community for their
patient help so far on the mailing list and in other channels. And we
ask for your support in terms of feedback, comments and testing.


I've only had a brief look at the branch - if you want to even have a
remote chance of making this stage1 you should break the branch
up into a proper patch series and post it with appropriate ChangeLogs
and descriptions.

First, standard includes may _not_ be included after including system.h,
in fact, they _need_ to be included from system.h - that includes
things like  or .  There are "convenient" defines you
can use like

#define INCLUDE_SET
#include "system.h"

and system.h will do what you want.  Not to say that you should
use GCCs containers and not the standard library ones.


Thanks I didn't know this!



You expose way too many user-visible command-line options.


Yes, I can certainly remove some debugging flags.



All the stmt / tree walking "meta" code should be avoided - it
would need to be touched each time we change GIMPLE or
GENERIC.  Instead use available walkers if you really need
it in such DFS-ish way.


There are two points being made here:
1. Use the available walkers
2. Changing gimple would imply changes to your code

First:

I did tried using the available walkers in the past, and the walk_tree
function does not contain a post-order callback. We really need to
propagate information from the gimple leaf nodes back to the root, and
as a way to achieve this (and probably other things like maintaining a
stack of the nodes visited to reach the current node) we really need a
post-order callback.

We did have a conversation about this where you pointed out this pattern:

   *walk_subtrees = 0;
   walk_tree (.. interesting subexpressions ... );
   do post-order work

In the preorder hook, but this only works with simple expressions and we
need more complicated machinery.

Re: Dead Field Elimination and Field Reordering

[Richard Biener via Gcc]

On Tue, Nov 3, 2020 at 5:21 PM Erick Ochoa
 wrote:
>
> Thanks for the review Richard I'll address what I can. I also provide
> maybe some hindsight into some of the design decisions here. I'm not
> trying to be defensive just hoping to illuminate why some decisions were
> made and how some criticisms may fail to really address the reason why
> these designs were made.
>
> On 03/11/2020 15:58, Richard Biener wrote:
> > On Fri, Oct 30, 2020 at 6:44 PM Erick Ochoa
> >  wrote:
> >>
> >> Hello again,
> >>
> >> I've been working on several implementations of data layout
> >> optimizations for GCC, and I am again kindly requesting for a review of
> >> the type escape based dead field elimination and field reorg.
> >>
> >> Thanks to everyone that has helped me. The main differences between the
> >> previous commits have been fixing the style, adding comments explaining
> >> classes and families of functions, exit gracefully if we handle unknown
> >> gimple syntax, and added a heuristic to handle void* casts.
> >>
> >> This patchset is organized in the following way:
> >>
> >> * Adds a link-time warning if dead fields are detected
> >> * Allows for the dead-field elimination transformation to be applied
> >> * Reorganizes fields in structures.
> >> * Adds some documentation
> >> * Gracefully does not apply transformation if unknown syntax is detected.
> >> * Adds a heuristic to handle void* casts
> >>
> >> I have tested this transformations as extensively as I can. The way to
> >> trigger these transformations are:
> >>
> >> -fipa-field-reorder and -fipa-type-escape-analysis
> >>
> >> Having said that, I welcome all criticisms and will try to address those
> >> criticisms which I can. Please let me know if you have any questions or
> >> comments, I will try to answer in a timely manner.
> >>
> >> The code is in:
> >>
> >> refs/vendors/ARM/heads/arm-struct-reorg-wip
> >>
> >> Future work includes extending the current heuristic with ipa-modref
> >> extending the analysis to use IPA-PTA as discussed previously.
> >>
> >> Few notes:
> >>
> >> * Currently it is not safe to use -fipa-sra.
> >> * I added some tests which are now failing by default. This is because
> >> there is no way to safely determine within the test case that a layout
> >> has been transformed. I used to determine that a field was eliminated
> >> doing pointer arithmetic on the fields. And since that is not safe, the
> >> analysis decides not to apply the transformation. There is a way to deal
> >> with this (add a flag to allow the address of a field to be taken) but I
> >> wanted to hear other possibilities to see if there is a better option.
> >> * At this point we’d like to thank the again GCC community for their
> >> patient help so far on the mailing list and in other channels. And we
> >> ask for your support in terms of feedback, comments and testing.
> >
> > I've only had a brief look at the branch - if you want to even have a
> > remote chance of making this stage1 you should break the branch
> > up into a proper patch series and post it with appropriate ChangeLogs
> > and descriptions.
> >
> > First, standard includes may _not_ be included after including system.h,
> > in fact, they _need_ to be included from system.h - that includes
> > things like  or .  There are "convenient" defines you
> > can use like
> >
> > #define INCLUDE_SET
> > #include "system.h"
> >
> > and system.h will do what you want.  Not to say that you should
> > use GCCs containers and not the standard library ones.
>
> Thanks I didn't know this!
>
> >
> > You expose way too many user-visible command-line options.
>
> Yes, I can certainly remove some debugging flags.
>
> >
> > All the stmt / tree walking "meta" code should be avoided - it
> > would need to be touched each time we change GIMPLE or
> > GENERIC.  Instead use available walkers if you really need
> > it in such DFS-ish way.
>
> There are two points being made here:
> 1. Use the available walkers
> 2. Changing gimple would imply changes to your code
>
> First:
>
> I did tried using the available walkers in the past, and the walk_tree
> function does not contain a post-order callback. We really need to
> propagate information from the gimple leaf nodes back to the root, and
> as a way to achieve this (and probably other things like maintaining a
> stack of the nodes visited to reach the current node) we really need a
> post-order callback.
>
> We did have a conversation about this where you pointed out this pattern:
>
>   *walk_subtrees = 0;
>   walk_tree (.. interesting subexpressions ... );
>   do post-order work
>
> In the preorder hook, but this only works with simple expressions and we
> need more complicated machinery.
>
> Furthermore, I did look into extending the current walk_tree function
> with post-order callbacks but due to implementation details in the
> function (tail-recursion), we both agreed that having both
> tail-recursion AND a post-order hook was impossible.

Yes, I remember the 

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

[Erick Ochoa]

From bad08833616e9dd7a212e55b93503200393da942 Mon Sep 17 00:00:00 2001
From: Erick Ochoa 
Date: Sun, 30 Aug 2020 10:21:35 +0200
Subject: [PATCH 5/7] Abort if Gimple produced from C++ or Fortran sources is
 found.

2020-11-04  Erick Ochoa  

* gcc/ipa-field-reorder: Add flag to exit transformation
* gcc/ipa-type-escape-analysis: Same

---
 gcc/ipa-field-reorder.c|  3 +-
 gcc/ipa-type-escape-analysis.c | 53 --
 gcc/ipa-type-escape-analysis.h |  2 ++
 3 files changed, 48 insertions(+), 10 deletions(-)

diff --git a/gcc/ipa-field-reorder.c b/gcc/ipa-field-reorder.c
index 611089ecf24..c23e6a3f818 100644
--- a/gcc/ipa-field-reorder.c
+++ b/gcc/ipa-field-reorder.c
@@ -590,6 +590,7 @@ lto_fr_execute ()
 {
   log ("here in field reordering \n");
   // Analysis.
+  detected_incompatible_syntax = false;
   tpartitions_t escaping_nonescaping_sets
 = partition_types_into_escaping_nonescaping ();
   record_field_map_t record_field_map = find_fields_accessed ();
@@ -597,7 +598,7 @@ lto_fr_execute ()
 = obtain_nonescaping_unaccessed_fields (escaping_nonescaping_sets,
record_field_map, 0);

-  if (record_field_offset_map.empty ())
+  if (detected_incompatible_syntax || record_field_offset_map.empty ())
 return 0;

   // Prepare for transformation.
diff --git a/gcc/ipa-type-escape-analysis.c b/gcc/ipa-type-escape-analysis.c
index 9944580da6c..b06f33e24fb 100644
--- a/gcc/ipa-type-escape-analysis.c
+++ b/gcc/ipa-type-escape-analysis.c
@@ -170,6 +170,10 @@ along with GCC; see the file COPYING3.  If not see
 #include "ipa-type-escape-analysis.h"
 #include "ipa-dfe.h"

+#define ABORT_IF_NOT_C true
+
+bool detected_incompatible_syntax = false;
+
 // Main function that drives dfe.
 static unsigned int
 lto_dfe_execute ();
@@ -256,13 +260,14 @@ static void
 lto_dead_field_elimination ()
 {
   // Analysis.
+  detected_incompatible_syntax = false;
   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, OPT_Wdfa);
-  if (record_field_offset_map.empty ())
+  if (detected_incompatible_syntax || record_field_offset_map.empty ())
 return;

 // Prepare for transformation.
@@ -589,6 +594,7 @@ TypeWalker::_walk (const_tree type)
   // Improve, verify that having a type is an invariant.
   // I think there was a specific example which didn't
   // allow for it
+  if (detected_incompatible_syntax) return;
   if (!type)
 return;

@@ -642,9 +648,9 @@ TypeWalker::_walk (const_tree type)
 case POINTER_TYPE:
   this->walk_POINTER_TYPE (type);
   break;
-case REFERENCE_TYPE:
-  this->walk_REFERENCE_TYPE (type);
-  break;
+//case REFERENCE_TYPE:
+//  this->walk_REFERENCE_TYPE (type);
+//  break;
 case ARRAY_TYPE:
   this->walk_ARRAY_TYPE (type);
   break;
@@ -654,18 +660,24 @@ TypeWalker::_walk (const_tree type)
 case FUNCTION_TYPE:
   this->walk_FUNCTION_TYPE (type);
   break;
-case METHOD_TYPE:
-  this->walk_METHOD_TYPE (type);
-  break;
+//case METHOD_TYPE:
+  //this->walk_METHOD_TYPE (type);
+  //break;
 // Since we are dealing only with C at the moment,
 // we don't care about QUAL_UNION_TYPE nor LANG_TYPEs
 // So fail early.
+case REFERENCE_TYPE:
+case METHOD_TYPE:
 case QUAL_UNION_TYPE:
 case LANG_TYPE:
 default:
   {
log ("missing %s\n", get_tree_code_name (code));
+#ifdef ABORT_IF_NOT_C
+   detected_incompatible_syntax = true;
+#else
gcc_unreachable ();
+#endif
   }
   break;
 }
@@ -848,6 +860,7 @@ TypeWalker::_walk_arg (const_tree t)
 void
 ExprWalker::walk (const_tree e)
 {
+  if (detected_incompatible_syntax) return;
   _walk_pre (e);
   _walk (e);
   _walk_post (e);
@@ -932,7 +945,11 @@ ExprWalker::_walk (const_tree e)
 default:
   {
log ("missing %s\n", get_tree_code_name (code));
+#ifdef ABORT_IF_NOT_C
+   detected_incompatible_syntax = true;
+#else
gcc_unreachable ();
+#endif
   }
   break;
 }
@@ -1165,6 +1182,7 @@ GimpleWalker::walk ()
   cgraph_node *node = NULL;
   FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
 {
+  if (detected_incompatible_syntax) return;
   node->get_untransformed_body ();
   tree decl = node->decl;
   gcc_assert (decl);
@@ -1411,7 +1429,11 @@ GimpleWalker::_walk_gimple (gimple *stmt)
   // Break if something is unexpected.
   const char *name = gimple_code_name[code];
   log ("gimple code name %s\n", name);
+#ifdef ABORT_IF_NOT_C
+  detected_incompatible_syntax = true;
+#else
   gcc_unreachable ();
+#endif
 }

 void
@@ -2947,6 +2969,8 @@ TypeStringifier::stringify (const_tree t)
 return 

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

[Erick Ochoa]

From 09feb1cc82a5d9851a6b524e37c32554b923b1c4 Mon Sep 17 00:00:00 2001
From: Erick Ochoa 
Date: Thu, 6 Aug 2020 14:07:20 +0200
Subject: [PATCH 2/7] Add Dead Field Elimination

Using the Dead Field Analysis, Dead Field Elimination
automatically transforms gimple to eliminate fields that
are never read.

2020-11-04  Erick Ochoa  

* gcc/Makefile.in: add file to list of sources
* gcc/ipa-dfe.c: New
* gcc/ipa-dfe.h: Same
* gcc/ipa-type-escape-analysis.h: Export code used in dfe.
* gcc/ipa-type-escape-analysis.c: Call transformation

---
 gcc/Makefile.in|1 +
 gcc/ipa-dfe.c  | 1280 
 gcc/ipa-dfe.h  |  250 +++
 gcc/ipa-type-escape-analysis.c |   21 +-
 gcc/ipa-type-escape-analysis.h |   10 +
 5 files changed, 1553 insertions(+), 9 deletions(-)
 create mode 100644 gcc/ipa-dfe.c
 create mode 100644 gcc/ipa-dfe.h

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 8b18c9217a2..8ef6047870b 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1416,6 +1416,7 @@ OBJS = \
init-regs.o \
internal-fn.o \
ipa-type-escape-analysis.o \
+   ipa-dfe.o \
ipa-cp.o \
ipa-sra.o \
ipa-devirt.o \
diff --git a/gcc/ipa-dfe.c b/gcc/ipa-dfe.c
new file mode 100644
index 000..c048fac8621
--- /dev/null
+++ b/gcc/ipa-dfe.c
@@ -0,0 +1,1280 @@
+/* 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 dead field elimination (IPA-DFE)
+
+   The goal of this transformation is to
+
+   1) Create new types to replace RECORD_TYPEs which hold dead fields.
+   2) Substitute instances of old RECORD_TYPEs for new RECORD_TYPEs.
+   3) Substitute instances of old FIELD_DECLs for new FIELD_DECLs.
+   4) Fix some instances of pointer arithmetic.
+   5) Relayout where needed.
+
+   First stage - DFA
+   =
+
+   Use DFA to compute the set of FIELD_DECLs which can be deleted.
+
+   Second stage - Reconstruct Types
+   
+
+   This stage is done by two family of classes, the SpecificTypeCollector
+   and the TypeReconstructor.
+
+   The SpecificTypeCollector collects all TYPE_P trees which point to
+   RECORD_TYPE trees returned by DFA.  The TypeReconstructor will create
+   new RECORD_TYPE trees and new TYPE_P trees replacing the old RECORD_TYPE
+   trees with the new RECORD_TYPE trees.
+
+   Third stage - Substitute Types and Relayout
+   ===
+
+   This stage is handled by ExprRewriter and GimpleRewriter.
+   Some pointer arithmetic is fixed here to take into account those 
eliminated

+   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"

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

[Erick Ochoa]

From 1609f4713b6d0ab2e84e52b4fbd6f645f10a95e7 Mon Sep 17 00:00:00 2001
From: Erick Ochoa 
Date: Fri, 16 Oct 2020 08:49:08 +0200
Subject: [PATCH 6/7] Add heuristic to take into account void* pattern.

We add a heuristic in order to be able to transform functions which
receive void* arguments as a way to generalize over arguments. An
example of this is qsort. The heuristic works by first inspecting
leaves in the call graph. If the leaves only contain a reference
to a single RECORD_TYPE then we color the nodes in the call graph
as "casts are safe in this function and does not call external
visible functions". We propagate this property up the callgraph
until a fixed point is reached. This will later be changed to
use ipa-modref.

2020-11-04  Erick Ochoa  

* ipa-type-escape-analysis.c : Add new heuristic
* ipa-field-reorder.c : Use heuristic
* ipa-type-escape-analysis.h : Change signatures
---
 gcc/ipa-field-reorder.c|   3 +-
 gcc/ipa-type-escape-analysis.c | 186 +++--
 gcc/ipa-type-escape-analysis.h |  72 -
 3 files changed, 246 insertions(+), 15 deletions(-)

diff --git a/gcc/ipa-field-reorder.c b/gcc/ipa-field-reorder.c
index c23e6a3f818..5dcc5a38958 100644
--- a/gcc/ipa-field-reorder.c
+++ b/gcc/ipa-field-reorder.c
@@ -591,8 +591,9 @@ lto_fr_execute ()
   log ("here in field reordering \n");
   // Analysis.
   detected_incompatible_syntax = false;
+  std::map whitelisted = get_whitelisted_nodes();
   tpartitions_t escaping_nonescaping_sets
-= partition_types_into_escaping_nonescaping ();
+= partition_types_into_escaping_nonescaping (whitelisted);
   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,
diff --git a/gcc/ipa-type-escape-analysis.c b/gcc/ipa-type-escape-analysis.c
index b06f33e24fb..fe68eaf70c7 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 
 #include 
 #include 
+#include 

 #include "ipa-type-escape-analysis.h"
 #include "ipa-dfe.h"
@@ -249,6 +250,99 @@ lto_dfe_execute ()
   return 0;
 }

+/* Heuristic to determine if casting is allowed in a function.
+ * This heuristic attempts to allow casting in functions which follow the
+ * pattern where a struct pointer or array pointer is casted to void* or
+ * char*.  The heuristic works as follows:
+ *
+ * There is a simple per-function analysis that determines whether there
+ * is more than 1 type of struct referenced in the body of the method.
+ * If there is more than 1 type of struct referenced in the body,
+ * then the layout of the structures referenced within the body
+ * cannot be casted.  However, if there's only one type of struct 
referenced

+ * in the body of the function, casting is allowed in the function itself.
+ * The logic behind this is that the if the code follows good programming
+ * practices, the only way the memory should be accessed is via a singular
+ * type. There is also another requisite to this per-function analysis, and
+ * that is that the function can only call colored functions or functions
+ * which are available in the linking unit.
+ *
+ * Using this per-function analysis, we then start coloring leaf nodes 
in the

+ * call graph as ``safe'' or ``unsafe''.  The color is propagated to the
+ * callers of the functions until a fixed point is reached.
+ */
+std::map
+get_whitelisted_nodes ()
+{
+  cgraph_node *node = NULL;
+  std::set nodes;
+  std::set leaf_nodes;
+  std::set leaf_nodes_decl;
+  FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
+  {
+node->get_untransformed_body ();
+nodes.insert(node);
+if (node->callees) continue;
+
+leaf_nodes.insert (node);
+leaf_nodes_decl.insert (node->decl);
+  }
+
+  std::queue worklist;
+  for (std::set::iterator i = leaf_nodes.begin (),
+e = leaf_nodes.end (); i != e; ++i)
+  {
+if (dump_file) fprintf (dump_file, "is a leaf node %s\n", 
(*i)->name ());

+worklist.push (*i);
+  }
+
+  for (std::set::iterator i = nodes.begin (),
+e = nodes.end (); i != e; ++i)
+  {
+worklist.push (*i);
+  }
+
+  std::map map;
+  while (!worklist.empty ())
+  {
+
+if (detected_incompatible_syntax) return map;
+cgraph_node *i = worklist.front ();
+worklist.pop ();
+if (dump_file) fprintf (dump_file, "analyzing %s %p\n", i->name (), i);
+GimpleWhiteLister whitelister;
+whitelister._walk_cnode (i);
+bool no_external = whitelister.does_not_call_external_functions (i, 
map);

+bool before_in_map = map.find (i->decl) != map.end ();
+bool place_callers_in_worklist = !before_in_map;
+if (!before_in_map)
+{
+  map.insert(std::pair(i->decl, no_external));
+} else
+{
+  map[i->decl] = no_external;
+}
+bool previous_value = map[i->decl];
+place_callers_in_worklist |= 

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

[Erick Ochoa]

From 747b13bf2c6f5b17bc46316998f01483f8039548 Mon Sep 17 00:00:00 2001
From: Erick Ochoa 
Date: Wed, 4 Nov 2020 13:42:35 +0100
Subject: [PATCH 7/7] Getting rid of warnings


2020-11-04  Erick Ochoa  

* gcc/ipa-dfe.c : Change const_tree to tree
* gcc/ipa-dfe.h : same
* gcc/ipa-field-reorder.h : same
* gcc/ipa-type-escape-analysis.c : same, add unused attribute
* gcc/ipa-type-escape-analysis.h : same, add unused attribute

---
 gcc/ipa-dfe.c  | 164 -
 gcc/ipa-dfe.h  |  80 ++---
 gcc/ipa-field-reorder.c|  72 ++--
 gcc/ipa-type-escape-analysis.c | 612 -
 gcc/ipa-type-escape-analysis.h | 312 -
 5 files changed, 621 insertions(+), 619 deletions(-)

diff --git a/gcc/ipa-dfe.c b/gcc/ipa-dfe.c
index 16f594a36b9..e163a32617c 100644
--- a/gcc/ipa-dfe.c
+++ b/gcc/ipa-dfe.c
@@ -126,22 +126,22 @@ along with GCC; see the file COPYING3.  If not see
  * Find all non_escaping types which point to RECORD_TYPEs in
  * record_field_offset_map.
  */
-std::set
+std::set
 get_all_types_pointing_to (record_field_offset_map_t 
record_field_offset_map,

   tpartitions_t casting)
 {
   const tset_t _escaping = casting.non_escaping;

-  std::set specific_types;
+  std::set specific_types;
   TypeStringifier stringifier;

   // Here we are just placing the types of interest in a set.
-  for (std::map::const_iterator i
+  for (std::map::const_iterator i
= record_field_offset_map.begin (),
e = record_field_offset_map.end ();
i != e; ++i)
 {
-  const_tree record = i->first;
+  tree record = i->first;
   std::string name = stringifier.stringify (record);
   specific_types.insert (record);
 }
@@ -150,16 +150,16 @@ get_all_types_pointing_to 
(record_field_offset_map_t record_field_offset_map,


   // SpecificTypeCollector will collect all types which point to the 
types in

   // the set.
-  for (std::set::const_iterator i = non_escaping.begin (),
+  for (std::set::const_iterator i = non_escaping.begin (),
e = non_escaping.end ();
i != e; ++i)
 {
-  const_tree type = *i;
+  tree type = *i;
   specifier.walk (type);
 }

   // These are all the types which need modifications.
-  std::set to_modify = specifier.get_set ();
+  std::set to_modify = specifier.get_set ();
   return to_modify;
 }

@@ -178,24 +178,24 @@ get_all_types_pointing_to 
(record_field_offset_map_t record_field_offset_map,

  */
 reorg_maps_t
 get_types_replacement (record_field_offset_map_t record_field_offset_map,
-  std::set to_modify)
+  std::set to_modify)
 {
   TypeStringifier stringifier;

   TypeReconstructor reconstructor (record_field_offset_map, "reorg");
-  for (std::set::const_iterator i = to_modify.begin (),
+  for (std::set::const_iterator i = to_modify.begin (),
e = to_modify.end ();
i != e; ++i)
 {
-  const_tree record = *i;
+  tree record = *i;
   reconstructor.walk (TYPE_MAIN_VARIANT (record));
 }

-  for (std::set::const_iterator i = to_modify.begin (),
+  for (std::set::const_iterator i = to_modify.begin (),
e = to_modify.end ();
i != e; ++i)
 {
-  const_tree record = *i;
+  tree record = *i;
   reconstructor.walk (record);
 }

@@ -205,11 +205,11 @@ get_types_replacement (record_field_offset_map_t 
record_field_offset_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 
TypeReconstructor.

-  for (std::map::const_iterator i = map.begin (),
+  for (std::map::const_iterator i = map.begin (),
  e = map.end ();
i != e; ++i)
 {
-  const_tree o_record = i->first;
+  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;
@@ -220,7 +220,7 @@ get_types_replacement (record_field_offset_map_t 
record_field_offset_map,

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);
+  tree _o_record = tree_to_tree (o_record);
   TYPE_CACHED_VALUES_P (_o_record) = false;
   TYPE_CACHED_VALUES_P (m_record) = false;

@@ -252,44 +252,44 @@ substitute_types_in_program (reorg_record_map_t map,
 /* Return a set of trees which point to the set of trees
  * that can be modified.
  */
-std::set
+std::set
 SpecificTypeCollector::get_set ()
 {
   return to_return;
 }

 void
-SpecificTypeCollector::_walk_POINTER_TYPE_pre 

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

[Erick Ochoa]

From 91947eea01a41bd7b17e501ad7d53dfb6499eefc Mon Sep 17 00:00:00 2001
From: Erick Ochoa 
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  

* 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 (_name, "%s.reorg", identifier);
+  asprintf (_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 = 

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

[Erick Ochoa]

From a8c4d5b99d5c4168ede79054396cba514fdf23b5 Mon Sep 17 00:00:00 2001
From: Erick Ochoa 
Date: Mon, 10 Aug 2020 09:10:37 +0200
Subject: [PATCH 4/7] Add documentation for dead field elimination

2020-11-04  Erick Ochoa  

* gcc/Makefile.in: Add file to documentation sources
* gcc/doc/dfe.texi: New section
* gcc/doc/gccint.texi: Include new section

---
 gcc/Makefile.in |   3 +-
 gcc/doc/dfe.texi| 187 
 gcc/doc/gccint.texi |   2 +
 3 files changed, 191 insertions(+), 1 deletion(-)
 create mode 100644 gcc/doc/dfe.texi

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 2184bd0fc3d..7e4c442416d 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -3275,7 +3275,8 @@ TEXI_GCCINT_FILES = gccint.texi gcc-common.texi 
gcc-vers.texi		\

 gnu.texi gpl_v3.texi fdl.texi contrib.texi languages.texi  \
 sourcebuild.texi gty.texi libgcc.texi cfg.texi tree-ssa.texi   \
 loop.texi generic.texi gimple.texi plugins.texi optinfo.texi   \
-match-and-simplify.texi analyzer.texi ux.texi poly-int.texi
+match-and-simplify.texi analyzer.texi ux.texi poly-int.texi\
+dfe.texi

 TEXI_GCCINSTALL_FILES = install.texi install-old.texi fdl.texi \
 gcc-common.texi gcc-vers.texi
diff --git a/gcc/doc/dfe.texi b/gcc/doc/dfe.texi
new file mode 100644
index 000..e8d01d817d3
--- /dev/null
+++ b/gcc/doc/dfe.texi
@@ -0,0 +1,187 @@
+@c Copyright (C) 2001 Free Software Foundation, Inc.
+@c This is part of the GCC manual.
+@c For copying conditions, see the file gcc.texi.
+
+@node Dead Field Elimination
+@chapter Dead Field Elimination
+
+@node Dead Field Elimination Internals
+@section Dead Field Elimination Internals
+
+@subsection Introduction
+
+Dead field elimination is a compiler transformation that removes fields 
from structs. There are several challenges to removing fields from 
structs at link time but, depending on the workload of the compiled 
program and the architecture where the program runs, dead field 
elimination might be a worthwhile transformation to apply. Generally 
speaking, when the bottle-neck of an application is given by the memory 
bandwidth of the host system and the memory requested is of a struct 
which can be reduced in size, then that combination of workload, program 
and architecture can benefit from applying dead field elimination. The 
benefits come from removing unnecessary fields from structures and thus 
reducing the memory/cache requirements to represent a structure.

+
+
+
+While challenges exist to fully automate a dead field elimination 
transformation, similar and more powerful optimizations have been 
implemented in the past. Chakrabarti et al [0] implement struct peeling, 
splitting into hot and cold parts of a structure, and field reordering. 
Golovanevsky et al [1] also shows efforts to implement data layout 
optimizations at link time. Unlike the work of Chakrabarti and 
Golovanesky, this text only talks about dead field elimination. This 
doesn't mean that the implementation can't be expanded to perform other 
link-time layout optimizations, it just means that dead field 
elimination is the only transformation that is implemented at the time 
of this writing.

+
+[0] Chakrabarti, Gautam, Fred Chow, and L. PathScale. "Structure layout 
optimizations in the open64 compiler: Design, implementation and 
measurements." Open64 Workshop at the International Symposium on Code 
Generation and Optimization. 2008.

+
+[1] Golovanevsky, Olga, and Ayal Zaks. "Struct-reorg: current status 
and future perspectives." Proceedings of the GCC Developers’ Summit. 2007.

+
+@subsection Overview
+
+The dead field implementation is structured in the following way:
+
+
+@itemize @bullet
+@item
+Collect all types which can refer to a @code{RECORD_TYPE}. This means 
that if we have a pointer to a record, we also collect this pointer. Or 
an array, or a union.

+@item
+Mark types as escaping. More of this in the following section.
+@item
+Find fields which can be deleted. (Iterate over all gimple code and 
find which fields are read.)

+@item
+Create new types with removed fields (and reference these types in 
pointers, arrays, etc.)

+@item
+Modify gimple to include these types.
+@end itemize
+
+
+Most of this code relies on the visitor pattern. Types, Expr, and 
Gimple statements are visited using this pattern. You can find the base 
classes in @file{type-walker.c} @file{expr-walker.c} and 
@file{gimple-walker.c}. There are assertions in place where a type, 
expr, or gimple code is encountered which has not been encountered 
before during the testing of this transformation. This facilitates 
fuzzying of the transformation.

+
+@subsubsection Implementation Details: Is a global variable escaping?
+
+How does the analysis determine whether a global variable is visible to 
code outside the current linking unit? In the file 
@file{gimple-escaper.c} we have a simple 

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

[Erick Ochoa]

Hi,

I've been working on several implementations of data layout 
optimizations for GCC, and I am again kindly requesting for a review of 
the type escape based dead field elimination and field reorg.


This patchset is organized in the following way:

* Adds a link-time warning if dead fields are detected
* Allows for the dead-field elimination transformation to be applied
* Reorganizes fields in structures.
* Adds some documentation
* Gracefully does not apply transformation if unknown syntax is detected.
* Adds a heuristic to handle void* casts

I have tested this transformations as extensively as I can. The way to 
trigger these transformations are:


-fipa-field-reorder and -fipa-type-escape-analysis

Having said that, I welcome all criticisms and will try to address those 
criticisms which I can. Please let me know if you have any questions or 
comments, I will try to answer in a timely manner.


There has been some initial discussion on the GCC mailing list but I'm 
submitting the patches to the patches mailing list now. Some of the 
initial criticisms mentioned on the GCC mailing list previously will be 
addressed in the following days, and I believe there is definitely 
enough time to address them all during Stage 1.


I had to add one last commit to account to some differences in the build 
script on master. I will be working today to squash it, but I still 
wanted to submit these patches in order to start the review process.


I have bootstrapped on aarch64-linux

Re: Dead Field Elimination and Field Reordering

[Erick Ochoa]

Thanks for the review Richard I'll address what I can. I also provide 
maybe some hindsight into some of the design decisions here. I'm not 
trying to be defensive just hoping to illuminate why some decisions were 
made and how some criticisms may fail to really address the reason why 
these designs were made.


On 03/11/2020 15:58, Richard Biener wrote:

On Fri, Oct 30, 2020 at 6:44 PM Erick Ochoa
 wrote:


Hello again,

I've been working on several implementations of data layout
optimizations for GCC, and I am again kindly requesting for a review of
the type escape based dead field elimination and field reorg.

Thanks to everyone that has helped me. The main differences between the
previous commits have been fixing the style, adding comments explaining
classes and families of functions, exit gracefully if we handle unknown
gimple syntax, and added a heuristic to handle void* casts.

This patchset is organized in the following way:

* Adds a link-time warning if dead fields are detected
* Allows for the dead-field elimination transformation to be applied
* Reorganizes fields in structures.
* Adds some documentation
* Gracefully does not apply transformation if unknown syntax is detected.
* Adds a heuristic to handle void* casts

I have tested this transformations as extensively as I can. The way to
trigger these transformations are:

-fipa-field-reorder and -fipa-type-escape-analysis

Having said that, I welcome all criticisms and will try to address those
criticisms which I can. Please let me know if you have any questions or
comments, I will try to answer in a timely manner.

The code is in:

refs/vendors/ARM/heads/arm-struct-reorg-wip

Future work includes extending the current heuristic with ipa-modref
extending the analysis to use IPA-PTA as discussed previously.

Few notes:

* Currently it is not safe to use -fipa-sra.
* I added some tests which are now failing by default. This is because
there is no way to safely determine within the test case that a layout
has been transformed. I used to determine that a field was eliminated
doing pointer arithmetic on the fields. And since that is not safe, the
analysis decides not to apply the transformation. There is a way to deal
with this (add a flag to allow the address of a field to be taken) but I
wanted to hear other possibilities to see if there is a better option.
* At this point we’d like to thank the again GCC community for their
patient help so far on the mailing list and in other channels. And we
ask for your support in terms of feedback, comments and testing.


I've only had a brief look at the branch - if you want to even have a
remote chance of making this stage1 you should break the branch
up into a proper patch series and post it with appropriate ChangeLogs
and descriptions.

First, standard includes may _not_ be included after including system.h,
in fact, they _need_ to be included from system.h - that includes
things like  or .  There are "convenient" defines you
can use like

#define INCLUDE_SET
#include "system.h"

and system.h will do what you want.  Not to say that you should
use GCCs containers and not the standard library ones.


Thanks I didn't know this!



You expose way too many user-visible command-line options.


Yes, I can certainly remove some debugging flags.



All the stmt / tree walking "meta" code should be avoided - it
would need to be touched each time we change GIMPLE or
GENERIC.  Instead use available walkers if you really need
it in such DFS-ish way.


There are two points being made here:
1. Use the available walkers
2. Changing gimple would imply changes to your code

First:

I did tried using the available walkers in the past, and the walk_tree 
function does not contain a post-order callback. We really need to 
propagate information from the gimple leaf nodes back to the root, and 
as a way to achieve this (and probably other things like maintaining a 
stack of the nodes visited to reach the current node) we really need a 
post-order callback.


We did have a conversation about this where you pointed out this pattern:

 *walk_subtrees = 0;
 walk_tree (.. interesting subexpressions ... );
 do post-order work

In the preorder hook, but this only works with simple expressions and we 
need more complicated machinery.


Furthermore, I did look into extending the current walk_tree function 
with post-order callbacks but due to implementation details in the 
function (tail-recursion), we both agreed that having both 
tail-recursion AND a post-order hook was impossible.


Second:

I would expect any transformation that performs an analysis in an IR be 
needing to at least be re-reviewed somehow when the IR is re-written. I 
also don't think extending the base visitor classes would be too difficult.




That "IPA SRA is not safe" is of course not an option but hints
at a shortcoming in your safety analysis.


I looked into how to make this transformation safe with IPA-SRA in the 
past. I don't think it is really that 

Re: Dead Field Elimination and Field Reordering

[Richard Biener via Gcc]

On Fri, Oct 30, 2020 at 6:44 PM Erick Ochoa
 wrote:
>
> Hello again,
>
> I've been working on several implementations of data layout
> optimizations for GCC, and I am again kindly requesting for a review of
> the type escape based dead field elimination and field reorg.
>
> Thanks to everyone that has helped me. The main differences between the
> previous commits have been fixing the style, adding comments explaining
> classes and families of functions, exit gracefully if we handle unknown
> gimple syntax, and added a heuristic to handle void* casts.
>
> This patchset is organized in the following way:
>
> * Adds a link-time warning if dead fields are detected
> * Allows for the dead-field elimination transformation to be applied
> * Reorganizes fields in structures.
> * Adds some documentation
> * Gracefully does not apply transformation if unknown syntax is detected.
> * Adds a heuristic to handle void* casts
>
> I have tested this transformations as extensively as I can. The way to
> trigger these transformations are:
>
> -fipa-field-reorder and -fipa-type-escape-analysis
>
> Having said that, I welcome all criticisms and will try to address those
> criticisms which I can. Please let me know if you have any questions or
> comments, I will try to answer in a timely manner.
>
> The code is in:
>
>refs/vendors/ARM/heads/arm-struct-reorg-wip
>
> Future work includes extending the current heuristic with ipa-modref
> extending the analysis to use IPA-PTA as discussed previously.
>
> Few notes:
>
> * Currently it is not safe to use -fipa-sra.
> * I added some tests which are now failing by default. This is because
> there is no way to safely determine within the test case that a layout
> has been transformed. I used to determine that a field was eliminated
> doing pointer arithmetic on the fields. And since that is not safe, the
> analysis decides not to apply the transformation. There is a way to deal
> with this (add a flag to allow the address of a field to be taken) but I
> wanted to hear other possibilities to see if there is a better option.
> * At this point we’d like to thank the again GCC community for their
> patient help so far on the mailing list and in other channels. And we
> ask for your support in terms of feedback, comments and testing.

I've only had a brief look at the branch - if you want to even have a
remote chance of making this stage1 you should break the branch
up into a proper patch series and post it with appropriate ChangeLogs
and descriptions.

First, standard includes may _not_ be included after including system.h,
in fact, they _need_ to be included from system.h - that includes
things like  or .  There are "convenient" defines you
can use like

#define INCLUDE_SET
#include "system.h"

and system.h will do what you want.  Not to say that you should
use GCCs containers and not the standard library ones.

You expose way too many user-visible command-line options.

All the stmt / tree walking "meta" code should be avoided - it
would need to be touched each time we change GIMPLE or
GENERIC.  Instead use available walkers if you really need
it in such DFS-ish way.

That "IPA SRA is not safe" is of course not an option but hints
at a shortcoming in your safety analysis.

In DFE in handle_pointer_arithmetic_constants you
look at the type of an operand - that's not safe since
this type doesn't carry any semantics.

The DFE code is really hard to follow since it diverges
from GCC style which would do sth like the following
to iterate over all stmt [operands]:

FOR_EACH_BB_FN (fun, bb)
  {
 for (auto gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next ())
walk PHIs
 for (auto gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next ())
walk stmts, for example via walk_gimple_stmt ()
  }

and I'd expect a single visitor with a switch () over the gimple/operation
kind rather than gazillion overloads I have no idea what they exactly
visit and how.

In a later change on the branch I see sth like ABORT_IF_NOT_C
where I'm not sure what this is after - you certainly can handle
IL constructs you do not handle conservatively (REFERENCE_TYPE
is the same as POINTER_TYPE - they are exchangable for the
middle-end, METHOD_TYPE is the same as FUNCTION_TYPE,
a QUAL_UNION_TYPE is not semantically different from
a UNION_TYPE for the middle-end it only differs in layout handing.

I see you only want to replace the void * "coloring" with modref
so you'll keep using "IPA type escape analysis".  I don't think
that's good to go.

Richard.

Dead Field Elimination and Field Reordering

[Erick Ochoa]

Hello again,

I've been working on several implementations of data layout 
optimizations for GCC, and I am again kindly requesting for a review of 
the type escape based dead field elimination and field reorg.


Thanks to everyone that has helped me. The main differences between the 
previous commits have been fixing the style, adding comments explaining 
classes and families of functions, exit gracefully if we handle unknown 
gimple syntax, and added a heuristic to handle void* casts.


This patchset is organized in the following way:

* Adds a link-time warning if dead fields are detected
* Allows for the dead-field elimination transformation to be applied
* Reorganizes fields in structures.
* Adds some documentation
* Gracefully does not apply transformation if unknown syntax is detected.
* Adds a heuristic to handle void* casts

I have tested this transformations as extensively as I can. The way to 
trigger these transformations are:


-fipa-field-reorder and -fipa-type-escape-analysis

Having said that, I welcome all criticisms and will try to address those 
criticisms which I can. Please let me know if you have any questions or 
comments, I will try to answer in a timely manner.


The code is in:

  refs/vendors/ARM/heads/arm-struct-reorg-wip

Future work includes extending the current heuristic with ipa-modref 
extending the analysis to use IPA-PTA as discussed previously.


Few notes:

* Currently it is not safe to use -fipa-sra.
* I added some tests which are now failing by default. This is because 
there is no way to safely determine within the test case that a layout 
has been transformed. I used to determine that a field was eliminated 
doing pointer arithmetic on the fields. And since that is not safe, the 
analysis decides not to apply the transformation. There is a way to deal 
with this (add a flag to allow the address of a field to be taken) but I 
wanted to hear other possibilities to see if there is a better option.
* At this point we’d like to thank the again GCC community for their 
patient help so far on the mailing list and in other channels. And we 
ask for your support in terms of feedback, comments and testing.