diff mbox series

[COMMITTED] path oracle: Do not look at root oracle for killed defs.

Message ID 20211106153557.98170-1-aldyh@redhat.com
State Committed
Commit 4856699eeb2809c50930bafe341a96470877195d
Headers
Series [COMMITTED] path oracle: Do not look at root oracle for killed defs. |

Commit Message

Aldy Hernandez Nov. 6, 2021, 3:35 p.m. UTC 
  [This is more Andrew's domain, but this is a P1 PR and I'd like to
unbreak the SPEC run, since this is a straigthforward fix.  When he
returns he can double check my work and give additional suggestions.]

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.

Committed.

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.
---
 gcc/value-relation.cc | 9 +++++++++
 gcc/value-relation.h  | 1 +
 2 files changed, 10 insertions(+)

Comments

Richard Biener Nov. 8, 2021, 8:44 a.m. UTC | #1 
On Sat, Nov 6, 2021 at 4:38 PM Aldy Hernandez via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> [This is more Andrew's domain, but this is a P1 PR and I'd like to
> unbreak the SPEC run, since this is a straigthforward fix.  When he
> returns he can double check my work and give additional suggestions.]
>
> 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.

Huh, since SSA has only a single definition it cannot be "killed".
What can happen is that if you look across backedges that the same
reg can have two different values.  Basically when you look across
backedges you have to discard all knowledge you derived from
stuff that's dominated by the backedge destination.

>
> This incorrect thread causes the miscompilation in 527.cam4_r.
>
> Tested on x86-64 and ppc64le Linux.
>
> Committed.
>
> 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.
> ---
>  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;
> --
> 2.31.1
>
Andrew MacLeod Nov. 8, 2021, 5:23 p.m. UTC | #2 
On 11/8/21 3:44 AM, Richard Biener via Gcc-patches wrote:
> On Sat, Nov 6, 2021 at 4:38 PM Aldy Hernandez via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>> [This is more Andrew's domain, but this is a P1 PR and I'd like to
>> unbreak the SPEC run, since this is a straigthforward fix.  When he
>> returns he can double check my work and give additional suggestions.]
>>
>> 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.
> Huh, since SSA has only a single definition it cannot be "killed".
> What can happen is that if you look across backedges that the same
> reg can have two different values.  Basically when you look across
> backedges you have to discard all knowledge you derived from
> stuff that's dominated by the backedge destination.
>
Yeah, its just terminology... the path oracle follows a linear set of 
edges, so when we see the DEF of an ssa-name, any existing relations 
that have been seen have, by definition, come from a back edge at some 
point.  If the root oracle has that relation, as in this case, it came 
from a back edge.

"Killing" is referring to killing any relations in the path up to this 
point when we see the definition of the SSA_NAME. This includes anything 
in, or preceding, the path to this point.. We were removing any 
relations found in the path, but  were missing the "preceding" part.

Andrew
Andrew MacLeod Nov. 8, 2021, 5:40 p.m. UTC | #3 
On 11/6/21 11:35 AM, Aldy Hernandez wrote:
> [This is more Andrew's domain, but this is a P1 PR and I'd like to
> unbreak the SPEC run, since this is a straigthforward fix.  When he
> returns he can double check my work and give additional suggestions.]
>
> 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.
>
> Committed.
>
> 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.
> ---
>   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;

Yeah, that is fine I think.

Rangers oracle doesn't suffer from this issue since it is dominance 
based..  we wont find any relation from a back edge because it won't 
dominate the definition.  The path oracle may start after a block 
containing a back edge, as so may inherit relations from that back edge.

The path oracle operates as an add-onto the normal oracle.   it simply 
maintains a list of relations that have been seen along the path, in the 
order it has seen them.  these are combined with any relations rangers 
oracle has active at the first block in the path.   That is why when we 
see an SSA_NAME defined while walking the path we may see relations 
already existing...  And we need to NOT find any relation that existed 
before the definition.

Anderw
diff mbox series

Patch

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;