Hi,
I saw that Stage 1 of GCC 13 development is just ended. So is this
considered? Or should I bring this up when general development is
reopened?
Thanks,
Di Zhao
> -----Original Message-----
> From: Di Zhao OS
> Sent: Tuesday, October 25, 2022 8:18 AM
> To: gcc-patches@gcc.gnu.org
> Cc: Richard Biener <richard.guent...@gmail.com>
> Subject: [PATCH v6] tree-optimization/101186 - extend FRE with "equivalence
> map" for condition prediction
>
> 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.
