tree-optimization/103721 - Only add equivalencies that are still valid.
Commit Message
This patch happens to fix the PR, but I believe it only papers over a
deeper issue that is uncovered in PR104067.
That said, examination of the issue uncovered an oversight in the way
equivalence sets are merged by the equivalence oracle. I have not seen
an instance via the ranger, but I suspect its just a matter of time.
Equivalences sets are added to the basic block in which they occur. By
default, the definition of an SSA_NAME create an equivalence in the DEF
block containing just the name itself. Other equivalences are added as
they are encountered in their respective basic blocks, and are created
by combining whatever equivalence is active (via query) in that block
with the new equivalence. An equivalence introduced by an edge is
currently only added the edge destination is a block with a single
predecessor. It is then added to that block.
When a query is made for the equivalence set for b_2 at BBx, a walk up
the dominance tree is made looking for the first block which has an
equivalence containing b_2. This then becomes the equivalence set for
B2 at BBx.
If this set contains f_8, before we know that f_8 and b_2 actually
equivalent, we query the equivalence set of f_8 at BBx. If it comes back
with the same set, then the 2 names are equivalent. if the set is
different, then they are not.
This allows us to register equivalences as we see them without worrying
about invalidating other equivalences. Rather, we defer validation
until we actually care, and pay the cost at the query point.
This PR has exposed a flaw in how we register equivalence sets around
back edges which could potentially show up somewhere.
searchvolume_5 was use in previous blocks along the back edge and has an
equivalence set of {_5, world_7} in BB8
# searchVolume_11 = PHI <1(4), 0(3)> { _11 }
# currentVolume_8 = searchVolume_5 { _5, _8 , world_7 }
<bb9>
# searchVolume_5 = PHI <searchVolume_11(8)> { _5, _11 }
# currentVolume_6 = PHI <currentVolume_8(8)>
When an equivalence is added for currentVolume_6, a query is made for
the equivalence set for currentVolume_8, which returns the set {_5, _8,
world_7 }. Currently, this is simply combined with {_6} via a bitwise
OR to produce {_5, _6, _8, world_7 }. This is incorrect as _5's
equivalence set is now {_5, _11}.
_6 and _8 dont appear to be directly related to _5, so we were missing
it. What should be happening is when we merge the equivalence set for
currentVolume_6 and currentVolume_8, each member of the set should be
verified by the same criteria the query uses... ie, ask for the equiv
set for _5, _8, and world_7 at BB9, and if it is different than this
set, it isn't added.
This would then create the correct equivalence set { _6, _8, world_7 },
as the query for _5 would come back with {_5, _11} and not evaluate as
equivalent.
And yes, PHIS all happen in parallel... We don't need to worry about
ordering because even if the PHI hadn't been processed in this order,
the definition would have provided a default of { _5 }, and thus still
not been equivalent and still won't be added to the set.
Anyway, even tho I think there is an additional problem in this PR, I
wanted to get approval and check this code in under this PR since it
does need to be fixed, and was uncovered here. We wont close the PR
until we are sure the underlying issue is resolved.
I will also see if I can come up with some kind of test case in the
meantime as well.
Bootstraps on x86_64-pc-linux-gnu with no regressions. Overall compile
time is very nominal.. less than a 0.1% impact on the EVRP/VRP passes,
so the cost is miniscule.
OK for trunk?
Andrew
Comments
On Wed, Jan 19, 2022 at 2:37 AM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> This patch happens to fix the PR, but I believe it only papers over a
> deeper issue that is uncovered in PR104067.
>
> That said, examination of the issue uncovered an oversight in the way
> equivalence sets are merged by the equivalence oracle. I have not seen
> an instance via the ranger, but I suspect its just a matter of time.
>
> Equivalences sets are added to the basic block in which they occur. By
> default, the definition of an SSA_NAME create an equivalence in the DEF
> block containing just the name itself. Other equivalences are added as
> they are encountered in their respective basic blocks, and are created
> by combining whatever equivalence is active (via query) in that block
> with the new equivalence. An equivalence introduced by an edge is
> currently only added the edge destination is a block with a single
> predecessor. It is then added to that block.
>
> When a query is made for the equivalence set for b_2 at BBx, a walk up
> the dominance tree is made looking for the first block which has an
> equivalence containing b_2. This then becomes the equivalence set for
> B2 at BBx.
>
> If this set contains f_8, before we know that f_8 and b_2 actually
> equivalent, we query the equivalence set of f_8 at BBx. If it comes back
> with the same set, then the 2 names are equivalent. if the set is
> different, then they are not.
>
> This allows us to register equivalences as we see them without worrying
> about invalidating other equivalences. Rather, we defer validation
> until we actually care, and pay the cost at the query point.
>
> This PR has exposed a flaw in how we register equivalence sets around
> back edges which could potentially show up somewhere.
>
> searchvolume_5 was use in previous blocks along the back edge and has an
> equivalence set of {_5, world_7} in BB8
>
> # searchVolume_11 = PHI <1(4), 0(3)> { _11 }
> # currentVolume_8 = searchVolume_5 { _5, _8 , world_7 }
>
> <bb9>
> # searchVolume_5 = PHI <searchVolume_11(8)> { _5, _11 }
> # currentVolume_6 = PHI <currentVolume_8(8)>
>
> When an equivalence is added for currentVolume_6, a query is made for
> the equivalence set for currentVolume_8, which returns the set {_5, _8,
> world_7 }. Currently, this is simply combined with {_6} via a bitwise
> OR to produce {_5, _6, _8, world_7 }. This is incorrect as _5's
> equivalence set is now {_5, _11}.
>
> _6 and _8 dont appear to be directly related to _5, so we were missing
> it. What should be happening is when we merge the equivalence set for
> currentVolume_6 and currentVolume_8, each member of the set should be
> verified by the same criteria the query uses... ie, ask for the equiv
> set for _5, _8, and world_7 at BB9, and if it is different than this
> set, it isn't added.
>
> This would then create the correct equivalence set { _6, _8, world_7 },
> as the query for _5 would come back with {_5, _11} and not evaluate as
> equivalent.
>
> And yes, PHIS all happen in parallel... We don't need to worry about
> ordering because even if the PHI hadn't been processed in this order,
> the definition would have provided a default of { _5 }, and thus still
> not been equivalent and still won't be added to the set.
>
> Anyway, even tho I think there is an additional problem in this PR, I
> wanted to get approval and check this code in under this PR since it
> does need to be fixed, and was uncovered here. We wont close the PR
> until we are sure the underlying issue is resolved.
>
> I will also see if I can come up with some kind of test case in the
> meantime as well.
>
> Bootstraps on x86_64-pc-linux-gnu with no regressions. Overall compile
> time is very nominal.. less than a 0.1% impact on the EVRP/VRP passes,
> so the cost is miniscule.
>
> OK for trunk?
OK. I don't quite understand how what you describe above works, it sounds
a bit odd with respect to the idea that equivalences should be transitive but
I should note that forming equivalences from PHI nodes with backedges
is not possible without being very careful since you will easily end up
equating _1 and _1 from different iterations (and thus with different value).
Thanks,
Richard.
>
> Andrew
On 1/19/22 04:33, Richard Biener wrote:
> On Wed, Jan 19, 2022 at 2:37 AM Andrew MacLeod via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>>
>> OK for trunk?
> OK. I don't quite understand how what you describe above works, it sounds
> a bit odd with respect to the idea that equivalences should be transitive but
The transitive check is what prevents us from having to find and update
all the equivalence sets when a name needs to be removed. we can simply
create a new equivalence with that name, and all the older equivalences
in the dom tree will no longer equate with it and are eliminated by the
query. With the nature of on-demand, its possible for equivalences to
get created in unexpected orders, and logging all the equivalences as
they are seen and leaving the final determination to query time seems to
be the easiest and most accurate way to get results. I suspect we miss
a few relations if we process things in a random order, but we
shouldn't get anything wrong.
> I should note that forming equivalences from PHI nodes with backedges
> is not possible without being very careful since you will easily end up
> equating _1 and _1 from different iterations (and thus with different value).
The dominator search version used by ranger won't create equivalences
from back edges normally because the back edge doesn't dominate the
block. The only time we could get an equivalence from a back edge would
be if all the other arguments to a PHI at the top of the loop were
undefined, or the same value as came in on the back edge
ie
top_5 = PHI<val_6(2), val_6(8)> would create an equivalence between
top_5 and val_6... but that's OK because it is just a copy then anyway.
or
top_5 = PHI <undefined(2), val_6(8)>
This will create an equivalence between top_5 and val_6 in the loop,
until we reach the point where val_6 is defined, and then the
equivalence will get killed. its possible that might cause an issue in
a single BB loop, If I could reproduce that... let me experiment. In
which case I'll simply disable equivalences applied to PHIs if its
driven by just a back edge.
I dont see any other way we can get an equivalence/relation from a back
edge with the oracle (other than what the threader does, it has its own
oracle extensions for paths)
Its on my task list to document the entire oracle mechanism for both
equivalences and relations in the next month or two.
Andrew
On Wed, Jan 19, 2022 at 7:41 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> On 1/19/22 04:33, Richard Biener wrote:
> > On Wed, Jan 19, 2022 at 2:37 AM Andrew MacLeod via Gcc-patches
> > <gcc-patches@gcc.gnu.org> wrote:
> >>
> >> OK for trunk?
> > OK. I don't quite understand how what you describe above works, it sounds
> > a bit odd with respect to the idea that equivalences should be transitive but
> The transitive check is what prevents us from having to find and update
> all the equivalence sets when a name needs to be removed. we can simply
> create a new equivalence with that name, and all the older equivalences
> in the dom tree will no longer equate with it and are eliminated by the
> query. With the nature of on-demand, its possible for equivalences to
> get created in unexpected orders, and logging all the equivalences as
> they are seen and leaving the final determination to query time seems to
> be the easiest and most accurate way to get results. I suspect we miss
> a few relations if we process things in a random order, but we
> shouldn't get anything wrong.
Ah, that's an interesting approach to solving this issue!
> > I should note that forming equivalences from PHI nodes with backedges
> > is not possible without being very careful since you will easily end up
> > equating _1 and _1 from different iterations (and thus with different value).
>
> The dominator search version used by ranger won't create equivalences
> from back edges normally because the back edge doesn't dominate the
> block. The only time we could get an equivalence from a back edge would
> be if all the other arguments to a PHI at the top of the loop were
> undefined, or the same value as came in on the back edge
>
> ie
>
> top_5 = PHI<val_6(2), val_6(8)> would create an equivalence between
> top_5 and val_6... but that's OK because it is just a copy then anyway.
>
> or
>
> top_5 = PHI <undefined(2), val_6(8)>
>
> This will create an equivalence between top_5 and val_6 in the loop,
> until we reach the point where val_6 is defined, and then the
> equivalence will get killed. its possible that might cause an issue in
> a single BB loop, If I could reproduce that... let me experiment. In
> which case I'll simply disable equivalences applied to PHIs if its
> driven by just a back edge.
>
> I dont see any other way we can get an equivalence/relation from a back
> edge with the oracle (other than what the threader does, it has its own
> oracle extensions for paths)
Thanks for the explanation.
> Its on my task list to document the entire oracle mechanism for both
> equivalences and relations in the next month or two.
That would be welcome.
Thanks,
Richard.
>
> Andrew
>
commit 100d007b7fdd00dfdf272a4b944832eb1df193bb
Author: Andrew MacLeod <amacleod@redhat.com>
Date: Tue Jan 18 12:42:02 2022 -0500
Only add equivalencies that are still valid.
When equivalencies sets are merged, each member of the set should be queried
to ensure its still valid rather than a bulk union.
* value-relation.cc (relation_oracle::valid_equivs): Query and add
if valid members of a set.
(equiv_oracle::register_equiv): Call valid_equivs rather than
bitmap direct operations.
(path_oracle::register_equiv): Ditto.
* value-relation.h (relation_oracle::valid_equivs): New prototype.
@@ -188,6 +188,23 @@ relation_transitive (relation_kind r1, relation_kind r2)
return rr_transitive_table[r1 - VREL_FIRST][r2 - VREL_FIRST];
}
+// Given an equivalence set EQUIV, set all the bits in B that are still valid
+// members of EQUIV in basic block BB.
+
+void
+relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb)
+{
+ unsigned i;
+ bitmap_iterator bi;
+ EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
+ {
+ tree ssa = ssa_name (i);
+ const_bitmap ssa_equiv = equiv_set (ssa, bb);
+ if (ssa_equiv == equivs)
+ bitmap_set_bit (b, i);
+ }
+}
+
// -------------------------------------------------------------------------
// The very first element in the m_equiv chain is actually just a summary
@@ -364,7 +381,7 @@ equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
// Otherwise create an equivalence for this block which is a copy
// of equiv, the add V to the set.
bitmap b = BITMAP_ALLOC (&m_bitmaps);
- bitmap_copy (b, equiv->m_names);
+ valid_equivs (b, equiv->m_names, bb);
bitmap_set_bit (b, v);
return b;
}
@@ -378,32 +395,32 @@ bitmap
equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1,
equiv_chain *equiv_2)
{
- // If equiv_1 is alreayd in BB, use it as the combined set.
+ // If equiv_1 is already in BB, use it as the combined set.
if (equiv_1->m_bb == bb)
{
- bitmap_ior_into (equiv_1->m_names, equiv_2->m_names);
+ valid_equivs (equiv_1->m_names, equiv_2->m_names, bb);
// Its hard to delete from a single linked list, so
// just clear the second one.
if (equiv_2->m_bb == bb)
bitmap_clear (equiv_2->m_names);
else
- // Ensure equiv_2s names are in the summary for BB.
- bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
+ // Ensure the new names are in the summary for BB.
+ bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
return NULL;
}
// If equiv_2 is in BB, use it for the combined set.
if (equiv_2->m_bb == bb)
{
- bitmap_ior_into (equiv_2->m_names, equiv_1->m_names);
- // Add equiv_1 names into the summary.
- bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
+ valid_equivs (equiv_2->m_names, equiv_1->m_names, bb);
+ // Ensure the new names are in the summary.
+ bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
return NULL;
}
// At this point, neither equivalence is from this block.
bitmap b = BITMAP_ALLOC (&m_bitmaps);
- bitmap_copy (b, equiv_1->m_names);
- bitmap_ior_into (b, equiv_2->m_names);
+ valid_equivs (b, equiv_1->m_names, bb);
+ valid_equivs (b, equiv_2->m_names, bb);
return b;
}
@@ -1289,8 +1306,8 @@ path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
// Don't mess around, simply create a new record and insert it first.
bitmap b = BITMAP_ALLOC (&m_bitmaps);
- bitmap_copy (b, equiv_1);
- bitmap_ior_into (b, equiv_2);
+ valid_equivs (b, equiv_1, bb);
+ valid_equivs (b, equiv_2, bb);
equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
sizeof (equiv_chain));
@@ -96,6 +96,8 @@ public:
virtual void dump (FILE *, basic_block) const = 0;
virtual void dump (FILE *) const = 0;
void debug () const;
+protected:
+ void valid_equivs (bitmap b, const_bitmap equivs, basic_block bb);
};
// This class represents an equivalency set, and contains a link to the next