[RFC] Introduce TREE_AOREFWRAP to cache ao_ref in the IL

  This prototype hack introduces a new tcc_reference TREE_AOREFWRAP
which we can use to wrap a reference tree, recording the ao_ref
associated with it.  That comes in handy when trying to optimize
the constant factor involved with alias stmt walking (or alias
queries in general) where there's parts that are liner in the
reference expression complexity, namely get_ref_base_and_extent,
which shows up usually high on profiles.

The idea was to make a wrapping TREE_AOREFWRAP mostly transparent
to users by making gimple_assign_{lhs,rhs1} strip it and provide
special accessors that get at the embedded ao_ref as well as
doing the wrapping when it's not already there.

The following patch is minimal as to make tree-ssa.exp=ssa-fre-*
not ICE and make the testcases from PR28071 and PR39326 compile
successfully at -O1 (both testcases show a moderately high
load on alias stmt walking around 25%, resp. 34%).  With the
patch which makes use of the cache only from stmt_may_clobber_ref_p
for now the compile-time improves by 7%, resp. 19% which means
overall the idea might be worth pursuing.

I did run into more "issues" with the extra TREE_AOREFWRAP appearing
than anticipated (well, no, not really...).  So given it is a
kind of hack already I'm now thinking of making it even more
transparent by instead of wrapping the refs with another tree
to reallocate the outermost handled_component_p (and only those),
placing the ao_ref after the tree and indicating its presence
by TREE_ASM_WRITTEN (or any other available bit).

As with TREE_AOREFWRAP the key is to invalidate the ao_ref
(strip TREE_AOREFWRAP or unset TREE_ASM_WRITTEN) when its
information becomes stale (for example by unsharing) or invalid
(by mangling the reference into sth semantically different) or
no longer precise (by propagating constants into the reference).

I did consider simply using an (optional) on-the-side hash-map
and allocpool to be initialized by passes and queried by the
oracle.  The downside is that we're optimizing a "constant" factor
of the oracle query but a hash-map lookup isn't exactly
cache-friendly.  Likewise caching across pass boundaries sounded
maybe important (OK, we have at most N ao_refs with N linear in
the program size - but as said, we're optimizing a constant factor).
Existing on-the-side caching includes the SCEV cache for example.

So take this as a proof-of-concept showing the possible gain,
I do think going either the TREE_ASM_WRITTEN or on-the-side table
solution is going to have less issues all around the compiler.

Comments?

Thanks,
Richard.

2021-10-12  Richard Biener  <rguenther@suse.de>

	* treestruct.def (TS_AOREFWRAP): New.
	* tree.def (TREE_AOREFWRAP): Likewise.
	* gimple.h (gimple_assign_lhs): Look through TREE_AOREFWRAP.
	(gimple_assign_rhs1): Likewise.
	(gimple_assign_lhs_with_ao_ref): New.
	(gimple_assign_rhs1_with_ao_ref): Likewise.
	* tree-ssa-alias.c (stmt_may_clobber_ref_p_1): Use the
	ao_ref embedded in the stmts LHS if possible.
	<... and more hacks ...>
---
 gcc/gimple.c               | 62 +++++++++++++++++++++++++++++++++++++-
 gcc/gimple.h               | 12 ++++++--
 gcc/tree-core.h            |  8 +++++
 gcc/tree-inline.c          |  4 +++
 gcc/tree-ssa-alias.c       | 11 +++++--
 gcc/tree-ssa-loop-im.c     |  5 ++-
 gcc/tree-ssa-loop-ivopts.c |  3 ++
 gcc/tree-ssa-loop.c        |  1 +
 gcc/tree-ssa-operands.c    |  1 +
 gcc/tree-streamer.c        |  1 +
 gcc/tree.c                 | 15 +++++++--
 gcc/tree.def               |  4 +++
 gcc/treestruct.def         |  1 +
 13 files changed, 119 insertions(+), 9 deletions(-)
  

Hello,

[this is the fourth attempt to write a comment/review/opinion for this 
ao_ref-in-tcc_reference, please accept some possible incoherence]

On Tue, 12 Oct 2021, Richard Biener via Gcc-patches wrote:

> This prototype hack introduces a new tcc_reference TREE_AOREFWRAP
> which we can use to wrap a reference tree, recording the ao_ref
> associated with it.  That comes in handy when trying to optimize
> the constant factor involved with alias stmt walking (or alias
> queries in general) where there's parts that are liner in the
> reference expression complexity, namely get_ref_base_and_extent,
> which shows up usually high on profiles.

So, generally I like storing things into the IL that are impossible to 
(re-)discover.  Remembering things that are merely slowish to rediscover 
is less clear, the increase of IL memory use, and potentially the 
necessary pointer chasing might just trade one clearly measurable slow 
point (the rediscover computation) with many slow points all over the 
place (the pointer chasing/cache effects).  Here ...

> The following patch is minimal as to make tree-ssa.exp=ssa-fre-*
> not ICE and make the testcases from PR28071 and PR39326 compile
> successfully at -O1 (both testcases show a moderately high
> load on alias stmt walking around 25%, resp. 34%).  With the
> patch which makes use of the cache only from stmt_may_clobber_ref_p
> for now the compile-time improves by 7%, resp. 19% which means
> overall the idea might be worth pursuing.

... you seem to have a point, though.  Also, I am of the opinion that our 
gimple memrefs could be even fatter (and also encode things like 
multi-dimensional accesses, either right from the source code or 
discovered by index analysis), and your idea goes into that direction.  
So, yay for encoding memref properties into the IL, even though here it's 
only a cache.  You solved the necessary invalidation already.  Perhaps 
only partly, that will be seen once exposed to the wild.

So, the only question seems to be how to encode it: either by ...

> transparent by instead of wrapping the refs with another tree

... this (wrapping) ...

> to reallocate the outermost handled_component_p (and only those),

... or that (aggregation).  There is a third possibility if you want this 
only in the gimple world (which is the case): encode it not in the trees 
but in the gimple statements.  This sort of works easily for everything 
except calls.  I will not consider this variant, nor the side table 
implementation.

While writing this email I switched between more liking one or the other, 
multiple times.  So, I'll write down some basic facts/requirements:

1) You basically want to add stuff to an existing structure:
(a) by wrapping: to work seemlessly the outer tree should have similar 
    enough properties to the inner tree (e.g. also be tcc_reference) to be 
    used interchangably in most code, except that which needs to look at 
    the added stuff.
(b) by aggregating the stuff into the existing structure itself: if you 
    need both structs (with and without stuff) the pure thing to do is to 
    actually create two structs, once with, once without stuff.
2) the added stuff is optional
3) we have multiple things (all tcc_reference) to which to add stuff
4) all tcc_reference are tree_exp, which is variable number of operands,
   which constrain things we can do naturally (e.g. we can't add stuff 
   after tree_exp, except by constraining the number of operands)

Considering this it seems that aggregation is worse: you basically double 
the number of structure types (at least conceptually, if you go with your 
bit-idea).  So, some idea of wrapping seems more natural.

(I think your idea of aggregation but going with a bit flag to indicate if 
this tcc_reference is or isn't annotated, and therefore has things 
allocated after the variable number of operands, is a terrible hack)

There is another possibility doing something like your bit-flag 
aggregation but with fewer hackery: if ao_ref would be a tree it could be 
a normal operand of a tree_exp (and hence tcc_reference), just that the 
number of operands then would vary depending on if it's annotated or not.

Making ao_ref into a tree would also enable the use of ANNOTATE_EXPR for a 
generic wrapping tree.  (Currently its used only in very specific cases, 
so ANNOTATE_EXPR handling would need to be extended all over, and as it's 
not a tcc_reference it would probably rather mean to introduce a new 
ANNOTATE_REF).

Anyway, with this:

struct tree_ref_annotation {
  struct tree_base base;
  struct ao_ref ao_ref;
};

DEFTREECODE(TREE_MEM_ANNO, "mem_anno", tcc_exceptional, 0);

you could then add

DEFTREECODE(MEM_REF_A, "mem_ref_a", tcc_reference, 3);

where TREE_OPERAND(memref, 2) would then be a TREE_MEM_ANNO.  If we were 
to add one operand slot to each tcc_reference we could even do without new 
tree codes: the existence of an ao_ref would simply be indicated by 
TREE_OPERAND(ref, position) being non-NULL.  It would of course enlargen 
each tcc_reference by one pointer, but maybe we could move more things 
into the above ref_annotation from somewhere else (points-to sets? scev 
info?) and then trade saving memory there with this pointer which then 
will more often be used.  (I think the eight bytes one has to pay for 
wrapping the ao_ref into a tree by adding tree_base might be quite 
acceptabable, or, if ao_ref would be a tree itself (not just wrapped into 
one), then e.g. the ao_ref.volatile_p flag could be grabbed from tree_base 
and free up the 8 bytes again)

So, at _this_ write-through of the email I think I like the above idea 
best: make ao_ref be a tree (at least its storage, because it currently 
is a one-member-function class), make ao_ref.volatile_p be 
tree_base.volatile_flag (hence TREE_VOLATILE(ao_ref)) (this reduces 
sizeof(ao_ref) by 8), increase all nr-of-operand of each tcc_reference by 
1, and make TREE_AO_REF(reftree) be "TREE_OPERAND(reftree, 
TREE_CODE_LENGTH(reftree) - 1)", i.e. the last operand of such 
tcc_reference tree.

Hmm, food for thought :)


Ciao,
Michael.
  

On Wed, 13 Oct 2021, Michael Matz wrote:

> Hello,
> 
> [this is the fourth attempt to write a comment/review/opinion for this 
> ao_ref-in-tcc_reference, please accept some possible incoherence]
> 
> On Tue, 12 Oct 2021, Richard Biener via Gcc-patches wrote:
> 
> > This prototype hack introduces a new tcc_reference TREE_AOREFWRAP
> > which we can use to wrap a reference tree, recording the ao_ref
> > associated with it.  That comes in handy when trying to optimize
> > the constant factor involved with alias stmt walking (or alias
> > queries in general) where there's parts that are liner in the
> > reference expression complexity, namely get_ref_base_and_extent,
> > which shows up usually high on profiles.
> 
> So, generally I like storing things into the IL that are impossible to 
> (re-)discover.  Remembering things that are merely slowish to rediscover 
> is less clear, the increase of IL memory use, and potentially the 
> necessary pointer chasing might just trade one clearly measurable slow 
> point (the rediscover computation) with many slow points all over the 
> place (the pointer chasing/cache effects).  Here ...

Note putting the cache in the IL rather than on-the-side was to
improve this - notably the approach embedding the ao_ref within
the outermost ref allocation (the TREE_ASM_WRITTEN thing) would
be just a pointer add away from memory we access anyway.  It also
cuts down the cost of the cache query itself to a bit test in
cache rather than querying a hashtable (and the hashtable pointer).

But yes, embedding any sort of cache into the IL is questionable.

> > The following patch is minimal as to make tree-ssa.exp=ssa-fre-*
> > not ICE and make the testcases from PR28071 and PR39326 compile
> > successfully at -O1 (both testcases show a moderately high
> > load on alias stmt walking around 25%, resp. 34%).  With the
> > patch which makes use of the cache only from stmt_may_clobber_ref_p
> > for now the compile-time improves by 7%, resp. 19% which means
> > overall the idea might be worth pursuing.
> 
> ... you seem to have a point, though.  Also, I am of the opinion that our 
> gimple memrefs could be even fatter (and also encode things like 
> multi-dimensional accesses, either right from the source code or 
> discovered by index analysis), and your idea goes into that direction.

Agreed with the issue of our reference tree representation, not sure
if the cache really goes into the fixing direction though.

> So, yay for encoding memref properties into the IL, even though here it's 
> only a cache.  You solved the necessary invalidation already.  Perhaps 
> only partly, that will be seen once exposed to the wild.
> 
> So, the only question seems to be how to encode it: either by ...
> 
> > transparent by instead of wrapping the refs with another tree
> 
> ... this (wrapping) ...
> 
> > to reallocate the outermost handled_component_p (and only those),
> 
> ... or that (aggregation).  There is a third possibility if you want this 
> only in the gimple world (which is the case): encode it not in the trees 
> but in the gimple statements.  This sort of works easily for everything 
> except calls.  I will not consider this variant, nor the side table 
> implementation.

Yeah, I was not considering to use the GIMPLE stmt itself because
we can have two (for aggregate copies) and N (for calls and asms).
I'm still considering the side table though.

> 
> While writing this email I switched between more liking one or the other, 
> multiple times.  So, I'll write down some basic facts/requirements:
> 
> 1) You basically want to add stuff to an existing structure:
> (a) by wrapping: to work seemlessly the outer tree should have similar 
>     enough properties to the inner tree (e.g. also be tcc_reference) to be 
>     used interchangably in most code, except that which needs to look at 
>     the added stuff.
> (b) by aggregating the stuff into the existing structure itself: if you 
>     need both structs (with and without stuff) the pure thing to do is to 
>     actually create two structs, once with, once without stuff.
> 2) the added stuff is optional
> 3) we have multiple things (all tcc_reference) to which to add stuff
> 4) all tcc_reference are tree_exp, which is variable number of operands,
>    which constrain things we can do naturally (e.g. we can't add stuff 
>    after tree_exp, except by constraining the number of operands)
> 
> Considering this it seems that aggregation is worse: you basically double 
> the number of structure types (at least conceptually, if you go with your 
> bit-idea).  So, some idea of wrapping seems more natural.
> 
> (I think your idea of aggregation but going with a bit flag to indicate if 
> this tcc_reference is or isn't annotated, and therefore has things 
> allocated after the variable number of operands, is a terrible hack)
> 
> There is another possibility doing something like your bit-flag 
> aggregation but with fewer hackery: if ao_ref would be a tree it could be 
> a normal operand of a tree_exp (and hence tcc_reference), just that the 
> number of operands then would vary depending on if it's annotated or not.
> 
> Making ao_ref into a tree would also enable the use of ANNOTATE_EXPR for a 
> generic wrapping tree.  (Currently its used only in very specific cases, 
> so ANNOTATE_EXPR handling would need to be extended all over, and as it's 
> not a tcc_reference it would probably rather mean to introduce a new 
> ANNOTATE_REF).
> 
> Anyway, with this:
> 
> struct tree_ref_annotation {
>   struct tree_base base;
>   struct ao_ref ao_ref;
> };
> 
> DEFTREECODE(TREE_MEM_ANNO, "mem_anno", tcc_exceptional, 0);
> 
> you could then add
> 
> DEFTREECODE(MEM_REF_A, "mem_ref_a", tcc_reference, 3);
> 
> where TREE_OPERAND(memref, 2) would then be a TREE_MEM_ANNO.  If we were 
> to add one operand slot to each tcc_reference we could even do without new 
> tree codes: the existence of an ao_ref would simply be indicated by 
> TREE_OPERAND(ref, position) being non-NULL.  It would of course enlargen 
> each tcc_reference by one pointer, but maybe we could move more things 
> into the above ref_annotation from somewhere else (points-to sets? scev 
> info?) and then trade saving memory there with this pointer which then 
> will more often be used.  (I think the eight bytes one has to pay for 
> wrapping the ao_ref into a tree by adding tree_base might be quite 
> acceptabable, or, if ao_ref would be a tree itself (not just wrapped into 
> one), then e.g. the ao_ref.volatile_p flag could be grabbed from tree_base 
> and free up the 8 bytes again)
> 
> So, at _this_ write-through of the email I think I like the above idea 
> best: make ao_ref be a tree (at least its storage, because it currently 
> is a one-member-function class), make ao_ref.volatile_p be 
> tree_base.volatile_flag (hence TREE_VOLATILE(ao_ref)) (this reduces 
> sizeof(ao_ref) by 8), increase all nr-of-operand of each tcc_reference by 
> 1, and make TREE_AO_REF(reftree) be "TREE_OPERAND(reftree, 
> TREE_CODE_LENGTH(reftree) - 1)", i.e. the last operand of such 
> tcc_reference tree.

Hmm.  I'm not sure that's really something I like - it's especially
quite some heavy lifting while at the same time lacking true boldness
as to changing the representation of memory refs ;)

> Hmm, food for thought :)

That said - I've prototyped the TREE_ASM_WRITTEN way now because it's
even simpler than the original TREE_AOREFWRAP approach, see below.

Note that I'm not embedding it into the tree structure, I'm merely
using the same allocation to store two objects, the outermost ref
and the ao_ref associated with it.  Quote:

+  size_t length = tree_code_size (TREE_CODE (lhs));
+  if (!TREE_ASM_WRITTEN (lhs))
+    {
+      tree alt_lhs
+       = ggc_alloc_cleared_tree_node_stat (length + sizeof (ao_ref));
+      memcpy (alt_lhs, lhs, length);
+      TREE_ASM_WRITTEN (alt_lhs) = 1;
+      *ref = new ((char *)alt_lhs + length) ao_ref;
+      ao_ref_init (*ref, alt_lhs);
+      stmt->op[0] = alt_lhs;


Richard.



From 97afd5e6bb32a0985a274ffe0cd26c8f935042ec Mon Sep 17 00:00:00 2001
From: Richard Biener <rguenther@suse.de>
Date: Thu, 14 Oct 2021 10:39:34 +0200
Subject: [PATCH] Introduce ao_ref cache in the IL
To: gcc-patches@gcc.gnu.org

This prototypes the alternate implementation suggested in
<ref> using TREE_ASM_WRITTEN on tcc_reference trees to denote
an adjacent ao_ref.  A complication I ran into when prototyping
is that we cannot re-allocate a component which has an SSA use
since there's no easy way to get to that to update the use pointer
in the immediate use structure.  So the prototype simply excuses
itself from caching anything on outermost components with a SSA
operand.

The patch misses strathegic unsetting of TREE_ASM_WRITTEN whenever
the cache becomes stale (both in the correctness and optimality sense)
but we didn't re-allocate the outermost component.  As optimization
we could use a 2nd bit to indicate the ao_ref storage is present but
unused.

Compared to the TREE_AOREFWRAP variant this survives building the
stage1 target libraries crashing "only" in IPA-CP when building
libgomp ...

The compile-time numbers are not as impressive (likely due to the
SSA operand issue), improving 7% (same as the other patch) and 10%
(less than the 19% seen in the other patch).  That means trying
to handle the SSA use adjustment might be worth.

Note that both patches only make light use of the approach and
specifically will not help the alias walks of DCE and DSE.

2021-10-14  Richard Biener  <rguenther@suse.de>

	* gimple.h (gimple_assign_lhs_with_ao_ref): New.
	* gimple.c (gimple_assign_lhs_with_ao_ref): Likewise.
	* tree-ssa-alias.c (stmt_may_clobber_ref_p_1): Use the
	ao_ref embedded in the stmts LHS if possible.
	* tree.c (copy_node): Unset TREE_ASM_WRITTEN on tcc_reference
	trees.
---
 gcc/gimple.c         | 52 ++++++++++++++++++++++++++++++++++++++++++++
 gcc/gimple.h         |  1 +
 gcc/tree-ssa-alias.c | 11 +++++++---
 gcc/tree.c           |  3 +++
 4 files changed, 64 insertions(+), 3 deletions(-)

diff --git a/gcc/gimple.c b/gcc/gimple.c
index cc7a88e822b..ceaa3ea3556 100644
--- a/gcc/gimple.c
+++ b/gcc/gimple.c
@@ -1758,6 +1758,58 @@ gimple_set_bb (gimple *stmt, basic_block bb)
 }
 
 
+/* Return lhs of a STMT with GIMPLE_SINGLE_RHS and initialize *REF
+   to the wrapping TREE_AOREFWRAP ao_ref or if rhs1 is not wrapped,
+   wrap it.  When wrapping is not profitable initialize *REF to NULL.  */
+
+tree
+gimple_assign_lhs_with_ao_ref (gassign *stmt, ao_ref **ref)
+{
+  tree lhs = stmt->op[0];
+  if (!REFERENCE_CLASS_P (lhs))
+    {
+      *ref = NULL;
+      return lhs;
+    }
+  /* ???  When we replace a component with SSA uses we have to
+     adjust the use pointer in the ssa_use_operand_t structure.
+     For now simply avoid this situation, doing a update_stmt here
+     would be super-ugly.
+     REALPART_EXPR, IMAGPART_EXPR, BIT_FIELD_REF and VIEW_CONVERT_EXPR
+     are always fine, MEM_REF and TARGET_MEM_REF are hardly profitable
+     to cache.  */
+  if (TREE_CODE (lhs) == MEM_REF
+      || TREE_CODE (lhs) == TARGET_MEM_REF
+      || (TREE_CODE (lhs) == COMPONENT_REF
+	  && TREE_OPERAND (lhs, 2) != NULL_TREE)
+      || ((TREE_CODE (lhs) == ARRAY_REF
+	   || TREE_CODE (lhs) == ARRAY_RANGE_REF)
+	  && (TREE_CODE (TREE_OPERAND (lhs, 1)) == SSA_NAME
+	      || (TREE_OPERAND (lhs, 2)
+		  && TREE_CODE (TREE_OPERAND (lhs, 2)) == SSA_NAME)
+	      || (TREE_OPERAND (lhs, 3)
+		  && TREE_CODE (TREE_OPERAND (lhs, 3)) == SSA_NAME))))
+    {
+      *ref = NULL;
+      return lhs;
+    }
+
+  size_t length = tree_code_size (TREE_CODE (lhs));
+  if (!TREE_ASM_WRITTEN (lhs))
+    {
+      tree alt_lhs
+	= ggc_alloc_cleared_tree_node_stat (length + sizeof (ao_ref));
+      memcpy (alt_lhs, lhs, length);
+      TREE_ASM_WRITTEN (alt_lhs) = 1;
+      *ref = new ((char *)alt_lhs + length) ao_ref;
+      ao_ref_init (*ref, alt_lhs);
+      stmt->op[0] = alt_lhs;
+      return alt_lhs;
+    }
+  *ref = reinterpret_cast <ao_ref *> ((char *)lhs + length);
+  return lhs;
+}
+
 /* Modify the RHS of the assignment pointed-to by GSI using the
    operands in the expression tree EXPR.
 
diff --git a/gcc/gimple.h b/gcc/gimple.h
index 303623b3ced..5b18045e128 100644
--- a/gcc/gimple.h
+++ b/gcc/gimple.h
@@ -2654,6 +2654,7 @@ gimple_assign_rhs1 (const gimple *gs)
   return gimple_assign_rhs1 (ass);
 }
 
+extern tree gimple_assign_lhs_with_ao_ref (gassign *, ao_ref **);
 
 /* Return a pointer to the first operand on the RHS of assignment
    statement GS.  */
diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
index ce667ff32b9..670d03748a8 100644
--- a/gcc/tree-ssa-alias.c
+++ b/gcc/tree-ssa-alias.c
@@ -3144,12 +3144,17 @@ stmt_may_clobber_ref_p_1 (gimple *stmt, ao_ref *ref, bool tbaa_p)
     }
   else if (gimple_assign_single_p (stmt))
     {
-      tree lhs = gimple_assign_lhs (stmt);
+      ao_ref *rp;
+      tree lhs = gimple_assign_lhs_with_ao_ref (as_a <gassign *> (stmt), &rp);
       if (TREE_CODE (lhs) != SSA_NAME)
 	{
 	  ao_ref r;
-	  ao_ref_init (&r, lhs);
-	  return refs_may_alias_p_1 (ref, &r, tbaa_p);
+	  if (!rp)
+	    {
+	      ao_ref_init (&r, lhs);
+	      rp = &r;
+	    }
+	  return refs_may_alias_p_1 (ref, rp, tbaa_p);
 	}
     }
   else if (gimple_code (stmt) == GIMPLE_ASM)
diff --git a/gcc/tree.c b/gcc/tree.c
index 7bfd64160f4..c0d43859235 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -1390,6 +1390,9 @@ copy_node (tree node MEM_STAT_DECL)
 	  TYPE_CACHED_VALUES (t) = NULL_TREE;
 	}
     }
+  else if (TREE_CODE_CLASS (code) == tcc_reference)
+    /* We did not and do not want to copy the adjacent ao_ref.  */
+    TREE_ASM_WRITTEN (t) = 0;
     else if (code == TARGET_OPTION_NODE)
       {
 	TREE_TARGET_OPTION (t) = ggc_alloc<struct cl_target_option>();
  

Hello,

On Thu, 14 Oct 2021, Richard Biener wrote:

> > So, at _this_ write-through of the email I think I like the above idea 
> > best: make ao_ref be a tree (at least its storage, because it currently 
> > is a one-member-function class), make ao_ref.volatile_p be 
> > tree_base.volatile_flag (hence TREE_VOLATILE(ao_ref)) (this reduces 
> > sizeof(ao_ref) by 8), increase all nr-of-operand of each tcc_reference by 
> > 1, and make TREE_AO_REF(reftree) be "TREE_OPERAND(reftree, 
> > TREE_CODE_LENGTH(reftree) - 1)", i.e. the last operand of such 
> > tcc_reference tree.
> 
> Hmm.  I'm not sure that's really something I like - it's especially
> quite some heavy lifting while at the same time lacking true boldness
> as to changing the representation of memory refs ;)

Well, it would at least enable such changes later in an orderly fashion.

> That said - I've prototyped the TREE_ASM_WRITTEN way now because it's 
> even simpler than the original TREE_AOREFWRAP approach, see below.
> 
> Note that I'm not embedding it into the tree structure, I'm merely
> using the same allocation to store two objects, the outermost ref
> and the ao_ref associated with it.  Quote:
> 
> +  size_t length = tree_code_size (TREE_CODE (lhs));
> +  if (!TREE_ASM_WRITTEN (lhs))
> +    {
> +      tree alt_lhs
> +       = ggc_alloc_cleared_tree_node_stat (length + sizeof (ao_ref));
> +      memcpy (alt_lhs, lhs, length);
> +      TREE_ASM_WRITTEN (alt_lhs) = 1;
> +      *ref = new ((char *)alt_lhs + length) ao_ref;

You need to ensure that alt_lhs+length is properly aligned for ao_ref, but 
yeah, for a hack that works.  If you really want to go that way you need 
good comments about this hack.  It's really somewhat worrisome that the 
size of the allocation depends on a bit in tree_base.

(It's a really cute hack that works as a micro optimization, the question 
is, do we really need to go there already, are all other less hacky 
approaches not bringing similar improvements?  The cuter the hacks the 
less often they pay off in the long run of production software :) )


Ciao,
Michael.
  

Michael Matz via Gcc-patches <gcc-patches@gcc.gnu.org> writes:
> Hello,
>
> On Thu, 14 Oct 2021, Richard Biener wrote:
>
>> > So, at _this_ write-through of the email I think I like the above idea 
>> > best: make ao_ref be a tree (at least its storage, because it currently 
>> > is a one-member-function class), make ao_ref.volatile_p be 
>> > tree_base.volatile_flag (hence TREE_VOLATILE(ao_ref)) (this reduces 
>> > sizeof(ao_ref) by 8), increase all nr-of-operand of each tcc_reference by 
>> > 1, and make TREE_AO_REF(reftree) be "TREE_OPERAND(reftree, 
>> > TREE_CODE_LENGTH(reftree) - 1)", i.e. the last operand of such 
>> > tcc_reference tree.
>> 
>> Hmm.  I'm not sure that's really something I like - it's especially
>> quite some heavy lifting while at the same time lacking true boldness
>> as to changing the representation of memory refs ;)
>
> Well, it would at least enable such changes later in an orderly fashion.
>
>> That said - I've prototyped the TREE_ASM_WRITTEN way now because it's 
>> even simpler than the original TREE_AOREFWRAP approach, see below.
>> 
>> Note that I'm not embedding it into the tree structure, I'm merely
>> using the same allocation to store two objects, the outermost ref
>> and the ao_ref associated with it.  Quote:
>> 
>> +  size_t length = tree_code_size (TREE_CODE (lhs));
>> +  if (!TREE_ASM_WRITTEN (lhs))
>> +    {
>> +      tree alt_lhs
>> +       = ggc_alloc_cleared_tree_node_stat (length + sizeof (ao_ref));
>> +      memcpy (alt_lhs, lhs, length);
>> +      TREE_ASM_WRITTEN (alt_lhs) = 1;
>> +      *ref = new ((char *)alt_lhs + length) ao_ref;
>
> You need to ensure that alt_lhs+length is properly aligned for ao_ref, but 
> yeah, for a hack that works.  If you really want to go that way you need 
> good comments about this hack.  It's really somewhat worrisome that the 
> size of the allocation depends on a bit in tree_base.
>
> (It's a really cute hack that works as a micro optimization, the question 
> is, do we really need to go there already, are all other less hacky 
> approaches not bringing similar improvements?  The cuter the hacks the 
> less often they pay off in the long run of production software :) )

FWIW, having been guilty of adding a similar hack(?) to SYMBOL_REFs
for block_symbol, I like the approach of concatenating/combining structures
based on flags.  The main tree and rtl types have too much baggage and
so I think there are some things that are better represented outside
of them.

I suppose cselib VALUE rtxes are also similar, although they're more
of a special case, since cselib data doesn't survive between passes.

Thanks,
Richard
  

Hello,

On Mon, 18 Oct 2021, Richard Sandiford wrote:

> > (It's a really cute hack that works as a micro optimization, the question 
> > is, do we really need to go there already, are all other less hacky 
> > approaches not bringing similar improvements?  The cuter the hacks the 
> > less often they pay off in the long run of production software :) )
> 
> FWIW, having been guilty of adding a similar hack(?) to SYMBOL_REFs
> for block_symbol, I like the approach of concatenating/combining structures
> based on flags.

The problem is that if you unset the flag you can't free the (now useless) 
storage.  What's worse is that you can't even reuse it anymore, because 
you lost the knowledge that it exists (except if you want to use another 
flag to note that).  It's of course obvious, but it helps to spell that 
out if we want to argue about ...

> The main tree and rtl types have too much baggage and

... baggage.  What you actually gain by associating different info pieces 
by address (e.g. concatenate allocations) is that you don't need to refer 
to one from the other, that's the space you spare, not anything inherent 
in the structures (which remain to have the members they would have 
anyway).  So, you basically trade one pointer (or index), which would 
possibly be optional, with address association and inflexibility (with the 
impossibility to manage both pieces individually: you can't free the 
second piece, and you can't add the second piece post-allocation).  It 
might be a good trade off sometimes, but in the abstract it's not a good 
design.

Regarding trees and space: to make something a tree you need 8 bytes and 
get a number of flags, and an arbitrary 4-byte blob in return.  I don't 
see that as much baggage.  We could reduce it further by splitting the 
arbitrary union and the tree_code+flags parts.  Especially for things 
referred to from tree_exp it makes sense to try making them trees 
themself.

> so I think there are some things that are better represented outside
> of them.
> 
> I suppose cselib VALUE rtxes are also similar, although they're more
> of a special case, since cselib data doesn't survive between passes.


Ciao,
Michael.
  

On Mon, 18 Oct 2021, Michael Matz wrote:

> Hello,
> 
> On Mon, 18 Oct 2021, Richard Sandiford wrote:
> 
> > > (It's a really cute hack that works as a micro optimization, the question 
> > > is, do we really need to go there already, are all other less hacky 
> > > approaches not bringing similar improvements?  The cuter the hacks the 
> > > less often they pay off in the long run of production software :) )
> > 
> > FWIW, having been guilty of adding a similar hack(?) to SYMBOL_REFs
> > for block_symbol, I like the approach of concatenating/combining structures
> > based on flags.
> 
> The problem is that if you unset the flag you can't free the (now useless) 
> storage.  What's worse is that you can't even reuse it anymore, because 
> you lost the knowledge that it exists (except if you want to use another 
> flag to note that).

Yes, I suspect in the end I'd use two bits to optimize this case.

> It's of course obvious, but it helps to spell that 
> out if we want to argue about ...
> 
> > The main tree and rtl types have too much baggage and
> 
> ... baggage.  What you actually gain by associating different info pieces 
> by address (e.g. concatenate allocations) is that you don't need to refer 
> to one from the other, that's the space you spare, not anything inherent 
> in the structures (which remain to have the members they would have 
> anyway).  So, you basically trade one pointer (or index), which would 
> possibly be optional, with address association and inflexibility (with the 
> impossibility to manage both pieces individually: you can't free the 
> second piece, and you can't add the second piece post-allocation).  It 
> might be a good trade off sometimes, but in the abstract it's not a good 
> design.
> 
> Regarding trees and space: to make something a tree you need 8 bytes and 
> get a number of flags, and an arbitrary 4-byte blob in return.  I don't 
> see that as much baggage.  We could reduce it further by splitting the 
> arbitrary union and the tree_code+flags parts.  Especially for things 
> referred to from tree_exp it makes sense to try making them trees 
> themself.

So the main issue is that I consider none of the discussed approaches
nice (or well-designed), so I went for the one that appears to be
least intrusive (the concatenating and bit-indication).

That said, I'm probably going to codify the on-the-side 
(optional) hashtable variant as well which is at least well-designed
but might have a disadvantage in the larger constant overhead and
principle difficulties in carrying info across passes and a necessarily
more explicit invalidation API.  Note all prototypes missed the
verification part (that info is not stale and reasonably up-to-date).

The real answer might of course be to invent the "proper" MEM_REF
tree that has fast access to ao_ref-style info as well as being
able to encode the important parts of the access path.

Richard.