Dead Field Elimination and Field Reordering

Erick Ochoa
Tue Nov 3 16:21:51 GMT 2020

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 <vector> or <map>.  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


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.


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 big of a short-coming. I was told 
that I could look at cgraph_node->clone.param_adjustments and find out 
how the parameters are being adjusted. I will certainly work on this, 
however, due to exploring the feasibility of using a points-to-analysis 
instead of a type-based escape analysis to drive this transformation, 
making this transformation safe with IPA SRA had to be put on the back 

So, overall, yes, I agree that it would be better if this transformation 
worked with IPA-SRA and I also think it can be done.

> 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.

What exactly do you mean by this "not carry any semantics"? If we are 
modifying a type, a type carries the semantics of how big the expected 
type is. So I at least need to know whether the pointer arithmetic 
affects a type I modified and if that's the case how big the previous 
type was and how smaller it is once the fields are deleted.

Can you be more concrete and point out the specific line of code? I 
think I have covered all cases here, but I just want to be really sure.

> 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 (&gsi))
>          walk PHIs
>       for (auto gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
>          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.

We could certainly flatten the visitors into a single larger visitor. 
The idea is to maintain a separation between statements, expressions, 
and types. That is why there are visitors for statements, expressions 
and types. And sure, each stage of the analysis might need slightly 
different ways to model gimple, so there are several derived classes.

Again, this was a design decision and I'm not married to it. I will try 
to refactor it to have a larger visitor.

> 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.

Originally I wrote these transformations with a lot of assertions to 
make fuzzying easier. In my experience, I have not seen REFERENCE_TYPE, 
QUAL_UNION_TYPE, nor METHOD_TYPE being generated from C code. Could we 
handle these gimple types in the future? Sure! I'd be happy to 
contribute such changes. However, since this optimization was written 
mostly targetting C code, I would need some time to revisit the 
assumptions that were made at the time and make sure that the 
implementation does not break. So, instead, at the moment, if we detect 
something that is not normally seen in "Gimple from C", we will abort 
and exit the optimization / analysis without transforming anything.

> 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.

I don't want to use modref only to replace the void* "coloring" 
heuristic. What I want is to use IPA-PTA to avoid using the IPA type 
escape analysis, however the level of precision for IPA-PTA needed for 
such things is not enough at the moment. I believe that using modref in 
the IPA type escape analysis, while the infrastructure for IPA-PTA grows 
is the best way to go forward. It gives me more experience writing 
transformations following the style that the community likes, learn 
about infrastructure available in GCC, and provides a way to test the 
future implementation (i.e., we can test the IPA-PTA implementation 
against the type-escape implementation).

Again, thank you very much for the review! It will be hard for me to 
address some of these concerns in a timely manner. I would appreciate if 
we can continue having some discussion about the design decisions I made 
and whether or not they do make sense and maybe are enough to address 
some concerns. Otherwise, I'll just try my best to address the concerns 
listed here by changing the implementation.

> Richard.

More information about the Gcc mailing list