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 <rguent...@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 <rguent...@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>();
--
2.31.1
