On Wed, Sep 7, 2022 at 9:30 AM Di Zhao OS <diz...@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.guent...@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.guent...@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 <diz...@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.