Re: PING^2: [PATCH v5] tree-optimization/101186 - extend FRE with "equivalence map" for condition prediction

[Richard Biener <richard.guenther@gmail.com>]

On Wed, Sep 7, 2022 at 9:30 AM Di Zhao OS <dizhao@os.amperecomputing.com> wrote:
>
> Gentle ping again.

So I got the chance to review the change again on the travel to GNU
Cauldron 2022.

There's quite some factoring / moving of stuff in the patch.  I've
already pushed to trunk
a change that factores out can_track_predicate_on_edge (your vn_tracking_edge),
factoring out is_vn_valid_at_bb also looks useful, so I'll followup
with a similar change.

I'm going to attach a commented quoted patch (because that's what I
produced during
the travel).  An overall comment (also in that attachment) would be

"why are equivalences recorded in the expression hash table at all?  Are
they not predicated values of an SSA name and thus should be a
vn_pval chain in vn_ssa_aux itself?

conditional equivalences are expensive to handle (so are the existing
predicated values which I do not like too much and which, frankly, I've
probably designed too general - ATM we only ever insert predicated
values 'true' and 'false' which could be used to simplify a lot of logic
but would break this patch?)

At some point I wanted to see whether we can use ranger relations
for all of this.

Then, for "true" equivalence tracking it might be interesting to explore
"path value numbering", aka allow revisiting code from the equivalence
op defs to the equivalence producing edge(s) with the equivalence fully
reflected in the value number.  The interesting thing might be that we
can track whether there's any equivalence on the side and based on
use heuristic decide whether that's going to pay off.  It might be also
possible to re-use this to improve jump threading costing.  If we'd be
able to "fork" the VN state we could re-run from the later definition
of an equivalence to the point it is established.

So, overall I wasn't able to get at what this patch will catch and what
it will not catch - that is, to what extent equivalences affect
previously and future recorded expressions.  Plus the implementation
feels like it bolts on the wrong place.

As I'm not happy with my predicated values implementation either I'm
of course a bit biased here (note the implementation was mostly added
to avoid regressions with respect to the previous VN implementation
and I should probably make it less general and more optimized - but
as said, using ranger might be an option here).

You have one testcase, ssa-fre-102.c, that seems to require VN
with equivalences, the others should be catched by rangers relation
handling, no?"

I've looked into using ranger for what the existing predicated value
handling does, plus catch more cases transparently.  I'm not sure
rangers equivalences handling is a good fit so to handle those an
approach like yours might be necessary.  Note I'm not really happy
about the patch as-is (nor I am happy about what I implemented
with predicated values - sorry for that).  I'm not even sure equivalences
can be handled "nicely" :/

Thanks,
Richard.

> Thanks,
> Di Zhao
>
> > -----Original Message-----
> > From: Di Zhao OS
> > Sent: Tuesday, July 12, 2022 2:08 AM
> > To: 'gcc-patches@gcc.gnu.org' <gcc-patches@gcc.gnu.org>
> > Cc: 'Richard Biener' <richard.guenther@gmail.com>
> > Subject: PING: [PATCH v5] tree-optimization/101186 - extend FRE with
> > "equivalence map" for condition prediction
> >
> > Updated the patch in the attachment, so it can apply.
> >
> > Thanks,
> > Di Zhao
> >
> > > -----Original Message-----
> > > From: Di Zhao OS
> > > Sent: Sunday, May 29, 2022 11:59 PM
> > > To: gcc-patches@gcc.gnu.org
> > > Cc: Richard Biener <richard.guenther@gmail.com>
> > > Subject: [PATCH v5] tree-optimization/101186 - extend FRE with "equivalence
> > > map" for condition prediction
> > >
> > > Hi, attached is a new version of the patch. The changes are:
> > > - Skip using temporary equivalences for floating-point values, because
> > > folding expressions can generate incorrect values. For example,
> > > operations on 0.0 and -0.0 may have different results.
> > > - Avoid inserting duplicated back-refs from value-number to predicates.
> > > - Disable fre in testsuite/g++.dg/pr83541.C .
> > >
> > > Summary of the previous versions:
> > > https://gcc.gnu.org/pipermail/gcc-patches/2021-December/587346.html
> > >
> > > Is the patch still considered?
> > >
> > > Thanks,
> > > Di Zhao
> > >
> > > ---
> > >
> > > Extend FRE with temporary equivalences.
> > >
> > > 2022-05-29  Di Zhao  <dizhao@os.amperecomputing.com>
> > >
> > > gcc/ChangeLog:
> > >         PR tree-optimization/101186
> > >         * tree-ssa-sccvn.c (VN_INFO): remove assertions (there could be a
> > >         predicate already).
> > >         (dominated_by_p_w_unex): Moved upward.
> > >         (vn_nary_op_get_predicated_value): Moved upward.
> > >         (is_vn_valid_at_bb): Check if vn_pval is valid at BB.
> > >         (lookup_equiv_head): Lookup the "equivalence head" of given node.
> > >         (lookup_equiv_heads): Lookup the "equivalence head"s of given nodes.
> > >         (vn_tracking_edge): Extracted utility function.
> > >         (init_vn_nary_op_from_stmt): Insert and lookup by "equivalence
> > head"s.
> > >         (vn_nary_op_insert_into): Insert new value at the front.
> > >         (vn_nary_op_insert_pieces_predicated_1): Insert as predicated values
> > >         from pieces.
> > >         (fold_const_from_equiv_heads): Fold N-ary expression of equiv-heads.
> > >         (push_new_nary_ref): Insert a back-reference to vn_nary_op_t.
> > >         (val_equiv_insert): Record temporary equivalence.
> > >         (vn_nary_op_insert_pieces_predicated): Record equivalences instead
> > of
> > >         some predicates; insert back-refs.
> > >         (record_equiv_from_prev_phi_1): Record temporary equivalences
> > > generated
> > >         by PHI nodes.
> > >         (record_equiv_from_prev_phi): Given an outgoing edge of a
> > conditional
> > >         expression taken, record equivalences generated by PHI nodes.
> > >         (visit_nary_op): Add lookup previous results of N-ary operations by
> > >         equivalences.
> > >         (insert_related_predicates_on_edge): Some predicates can be computed
> > >         from equivalences, no need to insert them.
> > >         (process_bb): Add lookup predicated values by equivalences.
> > >         (struct unwind_state): Unwind state of back-refs to vn_nary_op_t.
> > >         (do_unwind): Unwind the back-refs to vn_nary_op_t.
> > >         (do_rpo_vn): Update back-reference unwind state.
> > >         * tree-ssa-sccvn.h (struct nary_ref): hold a lists of references to
> > > the
> > >         nary map entries.
> > >
> > > gcc/testsuite/ChangeLog:
> > >
> > >         * g++.dg/pr83541.C: Disable fre.
> > >         * gcc.dg/tree-ssa/pr68619-2.c: Disable fre.
> > >         * gcc.dg/tree-ssa/pr71947-1.c: Disable fre.
> > >         * gcc.dg/tree-ssa/pr71947-2.c: Disable fre.
> > >         * gcc.dg/tree-ssa/pr71947-3.c: Disable fre.
> > >         * gcc.dg/tree-ssa/pr71947-5.c: Disable fre.
> > >         * gcc.dg/tree-ssa/pr71947-7.c: Disable fre.
> > >         * gcc.dg/tree-ssa/pr71947-8.c: Disable fre.
> > >         * gcc.dg/tree-ssa/pr71947-9.c: Disable fre.
> > >         * gcc.dg/tree-ssa/vrp03.c: Disable fre.
> > >         * gcc.dg/tree-ssa/ssa-fre-100.c: New test.
> > >         * gcc.dg/tree-ssa/ssa-fre-101.c: New test.
> > >         * gcc.dg/tree-ssa/ssa-fre-102.c: New test.
> > >         * gcc.dg/tree-ssa/ssa-pre-34.c: New test.