Sorry for the late update. I've been on a vacation and then I spent some time updating and verifying the patch.
Attached is a new version of the patch. There are some changes:
1. Store equivalences in a vn_pval chain in vn_ssa_aux, rather than
in the expression hash table. (Following Richard's suggestion.)
2. Extracted insert_single_predicated_value function.
3. Simplify record_equiv_from_prev_phi a bit.
4. Changed some of the functions' names and tried to improve the
comments a little.
Current status of the new testcases in the patch:
ssa-fre-200.c Can also be optimized by evrp
ssa-fre-201.c Not optimized in trunk.
ssa-fre-202.c foo() can be removed by evrp; while x + b is not
folded.
ssa-pre-34.c Not optimized in trunk.
Initially, this patch is motivated to remove the unreachable codes
in case like ssa-pre-34.c, in which we need to use equivalence
relation produced from a preceding condition for another condition.
VRP didn't optimize that because it needs jump threading to make
the relation valid at the second condition.
After browsing the mechanisms of VRP and FRE, it seems to me there
are two options: 1) Teach VRP to identify related but not threaded
conditions. That might require introducing value-numbering into VRP
to detect common expressions, and I think is too much for this.
2) Introduce temporary equivalence in sccvn, which I thought would
change less on current code. (And along the reviews and updating
patch I see how ad-hoc it was.)
I saw from the talk about VN there's plan to replace predicated
values by ranger. So how does it goes? Is there something I can help
with? (For the case ssa-pre-34.c, I think maybe it still needs the
predicated-value support, to lookup related conditional expressions.)
Below are about questions in the last review:
> > /* Valid hashtables storing information we have proven to be
> > correct. */
> > @@ -490,9 +492,9 @@ VN_INFO (tree name)
> > nary->predicated_values = 0;
> > nary->u.result = boolean_true_node;
> > vn_nary_op_insert_into (nary, valid_info->nary);
> > - gcc_assert (nary->unwind_to == NULL);
>
> why's that? doesn't this mean unwinding will be broken?
Previously, predicate "argument_x == NULL" or "argument_x != NULL"
is always new here (because argument_x's VN is just inserted.)
But with the patch, there can be slot for "argument_x == NULL"
or "argument_x != NULL" already. It won't break unwinding as the
new value is not linked to the unwind-chain.
>
> > /* Also do not link it into the undo chain. */
> > last_inserted_nary = nary->next;
> > + /* There could be a predicate already. */
> > nary->next = (vn_nary_op_t)(void *)-1;
> > nary = alloc_vn_nary_op_noinit (2, &vn_tables_insert_obstack);
> > init_vn_nary_op_from_pieces (nary, 2, EQ_EXPR,
> > /* Compute and return the hash value for nary operation VBO1. */
> >
> > hashval_t
> > @@ -4226,6 +4342,9 @@ init_vn_nary_op_from_stmt (vn_nary_op_t vno, gassign
> > *stmt)
> > for (i = 0; i < vno->length; ++i)
> > vno->op[i] = gimple_op (stmt, i + 1);
> > }
> > + /* Insert and lookup N-ary results by the operands' equivalence heads.
> > */
> > + if (gimple_bb (stmt))
> > + lookup_equiv_heads (vno->length, vno->op, vno->op, gimple_bb (stmt));
>
> That seems like the wrong place, the function didn't even valueize before.
To utilize temp-equivalences and get more simplified result, n-ary
expressions should be always inserted and lookup by the operands'
equivalence heads. So practically all the places
init_vn_nary_op_from_stmt is used, lookup_equiv_heads (changed to
get_equiv_heads) should be called. As I haven't found better place
to put that, I just left it here in the patch..
> > visit_nary_op (tree lhs, gassign *stmt)
> > {
> > vn_nary_op_t vnresult;
> > - tree result = vn_nary_op_lookup_stmt (stmt, &vnresult);
> > - if (! result && vnresult)
> > + unsigned length = vn_nary_length_from_stmt (stmt);
> > + vn_nary_op_t vno
> > + = XALLOCAVAR (struct vn_nary_op_s, sizeof_vn_nary_op (length));
> > + init_vn_nary_op_from_stmt (vno, stmt);
> > + tree result = NULL_TREE;
> > + /* Try to get a simplified result. */
> > + /* Do not simplify variable used in PHI at loop exit, or
> > + simplify_peeled_chrec/constant_after_peeling may miss the loop. */
> > + gimple *use_stmt;
> > + use_operand_p use_p;
> > + if (!(single_imm_use (lhs, &use_p, &use_stmt)
> > + && gimple_code (use_stmt) == GIMPLE_PHI
> > + && single_succ_p (gimple_bb (use_stmt))
> > + && (single_succ_edge (gimple_bb (use_stmt))->flags & EDGE_DFS_BACK)))
> > + result = fold_const_from_equiv_heads (vno->length, vno->opcode,
> > vno->op,
> > + vno->type);
>
> copy propagating conditional equivalences has proved problematic, why
> do this at all when there's no actual simplification? It's a bit odd that
> we need a special fold_const_from_equiv_heads here, why is general
> valueization not handling equivalences? Are they supposed to be only
> used for simplifying conditionals?
With temporary equivalences introduced, expressions like "a - equiv(a)"
and "a == equiv (a)" can be folded, and no need to store predicates
like "a == b is true". The function fold_const_from_equiv_heads is
intended to limit the usage of gimple_simplify, to when a constant can
be folded using equivalences. The code seems too complex but I haven't
figured out how to improve it yet. (I'm not very acquainted on how to
use the simplifying utility properly, I hope I can get some advices
here.) Also, could I have more details about "copy propagating
conditional equivalences has proved problematic" ?
Thank you very much,
Di Zhao
----
Extend FRE with temporary equivalences.
2022-10-24 Di Zhao <diz...@os.amperecomputing.com>
gcc/ChangeLog:
* tree-ssa-sccvn.cc (VN_INFO): remove assertions (there could be
a predicate already).
(dominated_by_p_w_unex): Moved upward.
(is_pval_valid_at_bb): Check if vn_pval is valid at BB.
(get_equiv_head): Returns the "equivalence head" of given node.
(get_equiv_heads): Get the "equivalence head"s of given nodes.
(init_vn_nary_op_from_stmt): Insert and lookup nary expressions
by "equivalence head"s.
(insert_single_predicated_value): Extracted utility.
(vn_nary_op_insert_into): Use the extracted utility
insert_single_predicated_value.
(fold_const_from_equiv_heads): Fold N-ary expression to constant
by equiv-heads.
(push_new_nary_ref): Insert a back-reference to vn_nary_op_t.
(alloc_single_predicated_value): Extracted utility.
(push_single_equiv): Push a new value to the equivalence list.
(record_temporary_equivalence): 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 a taken edge of a conditional
branch, record equivalences generated by PHI nodes.
(visit_nary_op): 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 and temporary
equivalences.
(do_unwind): Unwind the back-refs and temporary equivalences.
(do_rpo_vn_1): Update unwind state of back-reference and
temporary equivalences.
* tree-ssa-sccvn.h (struct temp_equiv): In vn_ssa_aux, hold a
list of temporary equivalences.
(struct nary_ref): In vn_ssa_aux, 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-200.c: New test.
* gcc.dg/tree-ssa/ssa-fre-201.c: New test.
* gcc.dg/tree-ssa/ssa-fre-202.c: New test.
* gcc.dg/tree-ssa/ssa-pre-34.c: New test.
v6-tree-optimization-101186.patch
Description: v6-tree-optimization-101186.patch
