[COMMITTED] tree-optimization/106514 - Do not walk equivalence set in path_oracle::killing_def.

[COMMITTED] tree-optimization/106514 - Do not walk equivalence set in path_oracle::killing_def.

[Andrew MacLeod]

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

The path oracles killing_def () routine was removing an ssa-name from 
each equivalence in the set.  This was busy work that did not need to be 
done.

when checking for an equivalence between A and B, the path oracle 
requires that A be in B's set and B be in A's set.  By setting the 
equivalence set for A to contain *just* A, there is no need to visit all 
the equivalences and remove them.

Aldy ran it thru the thread counter, and there was no difference in the 
number of threads found. The testcase in the PR on my machine ran in the 
following times:

there no difference i the default time, but with the specified option  
-O2 --param max-jump-thread-duplication-stmts=30 :

before patch:

backwards jump threading           :  11.64 ( 92%)   0.00 (  0%) 11.71 ( 
91%)    24  (  0%)
TOTAL                           :  12.70          0.07 12.83           47M

After patch:

backwards jump threading           :   1.96 ( 65%)   0.01 ( 10%)   1.99 
( 64%)    24  (  0%)
TOTAL                           :   3.00          0.10 3.12           47M

Clearly more work to do, but much better for a start.  next up, why is 
compute_ranges-in_block () taking over 50% of the time now.

This was bootstrapped on x86_64-pc-linux-gnu with no regressions.  pushed.

Andrew

[-- Attachment #2: P --]
[-- Type: text/plain, Size: 1485 bytes --]

commit 19ffb35d17474bb4dd3eb78963c28d10b5362321
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Wed Aug 3 13:55:42 2022 -0400

    Do not walk equivalence set in path_oracle::killing_def.
    
    When killing a def in the path ranger, there is no need to walk the set
    of existing equivalences clearing bits.  An equivalence match requires
    that both ssa-names have to be in each others set.  As killing_def
    creates a new empty set contianing only the current def,  it already
    ensures false equivaelnces won't happen.
    
            PR tree-optimization/106514
            * value-relation.cc (path_oracle::killing_def) Do not walk the
              equivalence set clearing bits.

diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc
index a447021214f..3f0957ccdd6 100644
--- a/gcc/value-relation.cc
+++ b/gcc/value-relation.cc
@@ -1400,16 +1400,7 @@ path_oracle::killing_def (tree ssa)
   unsigned v = SSA_NAME_VERSION (ssa);
 
   bitmap_set_bit (m_killed_defs, v);
-
-  // Walk the equivalency list and remove SSA from any equivalencies.
-  if (bitmap_bit_p (m_equiv.m_names, v))
-    {
-      for (equiv_chain *ptr = m_equiv.m_next; ptr; ptr = ptr->m_next)
-	if (bitmap_bit_p (ptr->m_names, v))
-	  bitmap_clear_bit (ptr->m_names, v);
-    }
-  else
-    bitmap_set_bit (m_equiv.m_names, v);
+  bitmap_set_bit (m_equiv.m_names, v);
 
   // Now add an equivalency with itself so we don't look to the root oracle.
   bitmap b = BITMAP_ALLOC (&m_bitmaps);