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 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.