[gcc r12-4971] path oracle: Do not look at root oracle for killed defs.

[Aldy Hernandez <aldyh@gcc.gnu.org>]

https://gcc.gnu.org/g:4856699eeb2809c50930bafe341a96470877195d

commit r12-4971-g4856699eeb2809c50930bafe341a96470877195d
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Fri Nov 5 22:25:19 2021 +0100

    path oracle: Do not look at root oracle for killed defs.
    
    The problem here is that we are incorrectly threading 41->20->21 here:
    
      <bb 35> [local count: 56063504182]:
      _134 = M.10_120 + 1;
      if (_71 <= _134)
        goto <bb 19>; [11.00%]
      else
        goto <bb 41>; [89.00%]
    ...
    ...
    ...
      <bb 41> [local count: 49896518755]:
    
      <bb 20> [local count: 56063503181]:
      # lb_75 = PHI <_134(41), 1(18)>
      _117 = mstep_49 + lb_75;
      _118 = _117 + -1;
      _119 = mstep_49 + _118;
      M.10_120 = MIN_EXPR <_119, _71>;
      if (lb_75 > M.10_120)
        goto <bb 21>; [11.00%]
      else
        goto <bb 22>; [89.00%]
    
    First, lb_17 == _134 because of the PHI.
    Second, _134 > M.10_120 because of _134 = M.10_120 + 1.
    
    We then assume that lb_75 > M.10_120, but this is incorrect because
    M.10_120 was killed along the path.
    
    This incorrect thread causes the miscompilation in 527.cam4_r.
    
    Tested on x86-64 and ppc64le Linux.
    
    gcc/ChangeLog:
    
            PR tree-optimization/103061
            * value-relation.cc (path_oracle::path_oracle): Initialize
            m_killed_defs.
            (path_oracle::killing_def): Set m_killed_defs.
            (path_oracle::query_relation): Do not look at the root oracle for
            killed defs.
            * value-relation.h (class path_oracle): Add m_killed_defs.

Diff:
---
 gcc/value-relation.cc | 9 +++++++++
 gcc/value-relation.h  | 1 +
 2 files changed, 10 insertions(+)

diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc
index f1e46d38de1..a0105481466 100644
--- a/gcc/value-relation.cc
+++ b/gcc/value-relation.cc
@@ -1235,6 +1235,7 @@ path_oracle::path_oracle (relation_oracle *oracle)
   m_equiv.m_next = NULL;
   m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
   m_relations.m_head = NULL;
+  m_killed_defs = BITMAP_ALLOC (&m_bitmaps);
 }
 
 path_oracle::~path_oracle ()
@@ -1305,6 +1306,8 @@ 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))
     {
@@ -1389,6 +1392,12 @@ path_oracle::query_relation (basic_block bb, const_bitmap b1, const_bitmap b2)
 
   relation_kind k = m_relations.find_relation (b1, b2);
 
+  // Do not look at the root oracle for names that have been killed
+  // along the path.
+  if (bitmap_intersect_p (m_killed_defs, b1)
+      || bitmap_intersect_p (m_killed_defs, b2))
+    return k;
+
   if (k == VREL_NONE && m_root)
     k = m_root->query_relation (bb, b1, b2);
 
diff --git a/gcc/value-relation.h b/gcc/value-relation.h
index 97be3251144..8086f5552b5 100644
--- a/gcc/value-relation.h
+++ b/gcc/value-relation.h
@@ -233,6 +233,7 @@ private:
   equiv_chain m_equiv;
   relation_chain_head m_relations;
   relation_oracle *m_root;
+  bitmap m_killed_defs;
 
   bitmap_obstack m_bitmaps;
   struct obstack m_chain_obstack;