Re: [PATCH][RFC] Introduce TREE_AOREFWRAP to cache ao_ref in the IL
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.
Re: [PATCH][RFC] Introduce TREE_AOREFWRAP to cache ao_ref in the IL
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.
Re: [PATCH][RFC] Introduce TREE_AOREFWRAP to cache ao_ref in the IL
Michael Matz via Gcc-patches 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
Re: [PATCH][RFC] Introduce TREE_AOREFWRAP to cache ao_ref in the IL
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.
Re: [PATCH][RFC] Introduce TREE_AOREFWRAP to cache ao_ref in the IL
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
Re: [PATCH][RFC] Introduce TREE_AOREFWRAP to cache ao_ref in the IL
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)
[PATCH][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
* 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(-)
diff --git a/gcc/gimple.c b/gcc/gimple.c
index cc7a88e822b..070304b64bf 100644
--- a/gcc/gimple.c
+++ b/gcc/gimple.c
@@ -1758,6 +1758,60 @@ gimple_set_bb (gimple *stmt, basic_block bb)
}
+/* Return rhs1 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_rhs1_with_ao_ref (gassign *stmt, ao_ref **ref)
+{
+ tree rhs1 = stmt->op[1];
+ if (!REFERENCE_CLASS_P (rhs1))
+{
+ *ref = NULL;
+ return rhs1;
+}
+ if (TREE_CODE (rhs1) != TREE_AOREFWRAP)
+{
+ rhs1 = build1 (TREE_AOREFWRAP, TREE_TYPE (rhs1), rhs1);
+ static_assert (sizeof (ao_ref) == sizeof (rhs1->aorefwrap.ref_storage),
+"wrong aorefwrap storage size");
+ *ref = new (>aorefwrap.ref_storage) ao_ref;
+ ao_ref_init (*ref, TREE_OPERAND (rhs1, 0));
+ stmt->op[1] = rhs1;
+ return TREE_OPERAND (rhs1, 0);
+}
+ *ref = reinterpret_cast (>aorefwrap.ref_storage);
+ return TREE_OPERAND (rhs1, 0);
+}
+
+/* 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
