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

[Di Zhao OS <dizhao@os.amperecomputing.com>]

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.guenther@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  <dizhao@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.