[PATCH] tree-optimization/103721 - Only add equivalencies that are still valid.

[PATCH] tree-optimization/103721 - Only add equivalencies that are still valid.

[Andrew MacLeod]

[-- Attachment #1: Type: text/plain, Size: 3741 bytes --]

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

[-- Attachment #2: 721.diff --]
[-- Type: text/x-patch, Size: 4498 bytes --]

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.

diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc
index 32ca693c464..0134e0328ba 100644
--- a/gcc/value-relation.cc
+++ b/gcc/value-relation.cc
@@ -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));
diff --git a/gcc/value-relation.h b/gcc/value-relation.h
index 44d0796d939..d840234f355 100644
--- a/gcc/value-relation.h
+++ b/gcc/value-relation.h
@@ -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

Re: [PATCH] tree-optimization/103721 - Only add equivalencies that are still valid.

[Richard Biener]

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

Re: [PATCH] tree-optimization/103721 - Only add equivalencies that are still valid.

[Andrew MacLeod]

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

Re: [PATCH] tree-optimization/103721 - Only add equivalencies that are still valid.

[Richard Biener]

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
>