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

[Richard Biener]

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
>