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

Andrew MacLeod amacleod@redhat.com
Mon Nov 8 17:40:24 GMT 2021


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




More information about the Gcc-patches mailing list