[PATCH v4] tree-optimization/101186 - extend FRE with "equivalence map" for condition prediction

[Di Zhao OS]

Here's a brief summary on the patch:

v4 (this version):
- In process_bb's condition-prediction code: update equivalence-heads if
  value-numbers have changed, otherwise some chances can be lost.

v3 (a few minor updates): 
- Simplify function record_equiv_from_prev_phi_1 by removing an argument.
- Fixed two small bugs that can lead to losing optimize opportunities.
- Link: https://gcc.gnu.org/pipermail/gcc-patches/2021-December/586687.html

v2:
- Use equivalence-heads (disjoint set) to represent temporary equivalences.
- Improved performance by reducing predicates-recording.
- The last version and some discussion:
  https://gcc.gnu.org/pipermail/gcc-patches/2021-December/586116.html
- Earlier discussion:
  https://gcc.gnu.org/pipermail/gcc-patches/2021-October/580688.html
- The patch:
  https://gcc.gnu.org/pipermail/gcc-patches/2021-September/579607.html

v1: 
- The initial patch (use a hashmap to store temporary equivalences):
  https://gcc.gnu.org/pipermail/gcc-patches/2021-June/573603.html
- Updates (fixed some code-style issue) and some explanation:
  https://gcc.gnu.org/pipermail/gcc-patches/2021-July/575531.html
- Reply from Richard:
  https://gcc.gnu.org/pipermail/gcc-patches/2021-July/576185.html

If the patch is considered, a following step I'm thinking is to
teach PRE pass with the temporary equivalences. Currently regression
test pr68619-4.c fails with the patch, because a variable's value
number turns to constant, and its equivalent's head is lost in the
AVAIL set. I think with this change, more partial redundancies can
be found.

Thanks,
Di Zhao

---

Extend FRE with temporary equivalences.

2021-12-24  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:

        * 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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: v4-tree-optimization-101186.patch
Type: application/octet-stream
Size: 37602 bytes
Desc: v4-tree-optimization-101186.patch
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20211224/1e26212f/attachment-0001.obj>