Re: [PATCH] Fix PR28868, eliminate redundant PHI nodes

[Daniel Berlin <dberlin at dberlin dot org>]

This looks fine to me, thanks for fixing this!

On Sat, Apr 4, 2009 at 1:51 PM, Richard Guenther <rguenther@suse.de> wrote:
>
> Appearantly nothing does this right now, so we end up with
>
> f:
> ? ? ? ?pushl ? %ebp
> ? ? ? ?movl ? ?%esp, %ebp
> ? ? ? ?movl ? ?8(%ebp), %ecx
> ? ? ? ?movl ? ?12(%ebp), %eax
> ? ? ? ?testl ? %ecx, %ecx
> ? ? ? ?movl ? ?%eax, %edx
> ? ? ? ?jne ? ? .L3
> ? ? ? ?movl ? ?16(%ebp), %eax
> ? ? ? ?movl ? ?%eax, %edx
> .L3:
> ? ? ? ?addl ? ?%edx, %eax
> ? ? ? ?popl ? ?%ebp
> ? ? ? ?ret
>
> from
>
> int f(int t, int a, int b)
> {
> ?int c, d;
> ?if (t)
> ? ?{
> ? ? ?c = a;
> ? ? ?d = a;
> ? ?}
> ?else
> ? ?{
> ? ? ?c = b;
> ? ? ?d = b;
> ? ?}
> ?return c+d;
> }
>
> instead of just
>
> f:
> ? ? ? ?pushl ? %ebp
> ? ? ? ?movl ? ?%esp, %ebp
> ? ? ? ?movl ? ?8(%ebp), %edx
> ? ? ? ?movl ? ?12(%ebp), %eax
> ? ? ? ?testl ? %edx, %edx
> ? ? ? ?jne ? ? .L3
> ? ? ? ?movl ? ?16(%ebp), %eax
> .L3:
> ? ? ? ?addl ? ?%eax, %eax
> ? ? ? ?popl ? ?%ebp
> ? ? ? ?ret
>
> (note the extra moves)
>
> Eliminating redundant PHIs fits nicely into the elimination phase
> of FRE/PRE although it gets somewhat more tricky due to PHI insertion.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu. ?Does this look sane?
>
> Thanks,
> Richard.
>
> 2009-04-04 ?Richard Guenther ?<rguenther@suse.de>
>
> ? ? ? ?PR tree-optimization/28868
> ? ? ? ?* tree-ssa-pre.c (inserted_phi_names): New bitmap to keep track
> ? ? ? ?of which PHI results we inserted.
> ? ? ? ?(insert_into_preds_of_block): Record inserted PHIs.
> ? ? ? ?(eliminate): Eliminate redundant PHI nodes.
> ? ? ? ?(init_pre): Init inserted_phi_names.
>
> ? ? ? ?* gcc.dg/tree-ssa/ssa-fre-21.c: New testcase.
> ? ? ? ?* gcc.dg/tree-ssa/ssa-sccvn-1.c: Adjust.
> ? ? ? ?* gcc.dg/tree-ssa/ssa-sccvn-2.c: Likewise.
> ? ? ? ?* gcc.dg/tree-ssa/ssa-sccvn-4.c: Likewise.
>
> Index: gcc/tree-ssa-pre.c
> ===================================================================
> *** gcc/tree-ssa-pre.c.orig ? ? 2009-04-04 13:05:18.000000000 +0200
> --- gcc/tree-ssa-pre.c ?2009-04-04 17:22:38.000000000 +0200
> *************** can_PRE_operation (tree op)
> *** 2597,2602 ****
> --- 2597,2603 ----
> ? ? for performing quick dead code elimination of insertions we made
> ? ? that didn't turn out to be necessary. ? */
> ?static VEC(gimple,heap) *inserted_exprs;
> + static bitmap inserted_phi_names;
>
> ?/* Pool allocated fake store expressions are placed onto this
> ? ? worklist, which, after performing dead code elimination, is walked
> *************** insert_into_preds_of_block (basic_block
> *** 3242,3247 ****
> --- 3243,3250 ----
> ? ?VN_INFO_GET (gimple_phi_result (phi))->valnum = gimple_phi_result (phi);
> ? ?VN_INFO (gimple_phi_result (phi))->value_id = val;
> ? ?VEC_safe_push (gimple, heap, inserted_exprs, phi);
> + ? bitmap_set_bit (inserted_phi_names,
> + ? ? ? ? ? ? ? ? SSA_NAME_VERSION (gimple_phi_result (phi)));
> ? ?FOR_EACH_EDGE (pred, ei, block->preds)
> ? ? ?{
> ? ? ? ?pre_expr ae = avail[pred->src->index];
> *************** eliminate (void)
> *** 4129,4144 ****
> ? ? ? ? ? ? ? ?}
> ? ? ? ? ? ?}
> ? ? ? ?}
> ? ? ?}
>
> ? ?/* We cannot remove stmts during BB walk, especially not release SSA
> ! ? ? ?names there as this confuses the VN machinery. ?*/
> ? ?for (i = 0; VEC_iterate (gimple, to_remove, i, stmt); ++i)
> ? ? ?{
> ! ? ? ? gsi = gsi_for_stmt (stmt);
> ! ? ? ? unlink_stmt_vdef (stmt);
> ! ? ? ? gsi_remove (&gsi, true);
> ! ? ? ? release_defs (stmt);
> ? ? ?}
> ? ?VEC_free (gimple, heap, to_remove);
>
> --- 4132,4226 ----
> ? ? ? ? ? ? ? ?}
> ? ? ? ? ? ?}
> ? ? ? ?}
> +
> + ? ? ? for (gsi = gsi_start_phis (b); !gsi_end_p (gsi);)
> + ? ? ? {
> + ? ? ? ? gimple stmt, phi = gsi_stmt (gsi);
> + ? ? ? ? tree sprime = NULL_TREE, res = PHI_RESULT (phi);
> + ? ? ? ? pre_expr sprimeexpr, resexpr;
> + ? ? ? ? gimple_stmt_iterator gsi2;
> +
> + ? ? ? ? /* We want to perform redundant PHI elimination. ?Do so by
> + ? ? ? ? ? ?replacing the PHI with a single copy if possible.
> + ? ? ? ? ? ?Do not touch inserted, single-argument or virtual PHIs. ?*/
> + ? ? ? ? if (gimple_phi_num_args (phi) == 1
> + ? ? ? ? ? ? || !is_gimple_reg (res)
> + ? ? ? ? ? ? || bitmap_bit_p (inserted_phi_names, SSA_NAME_VERSION (res)))
> + ? ? ? ? ? {
> + ? ? ? ? ? ? gsi_next (&gsi);
> + ? ? ? ? ? ? continue;
> + ? ? ? ? ? }
> +
> + ? ? ? ? resexpr = get_or_alloc_expr_for_name (res);
> + ? ? ? ? sprimeexpr = bitmap_find_leader (AVAIL_OUT (b),
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?get_expr_value_id (resexpr), NULL);
> + ? ? ? ? if (sprimeexpr)
> + ? ? ? ? ? {
> + ? ? ? ? ? ? if (sprimeexpr->kind == CONSTANT)
> + ? ? ? ? ? ? ? sprime = PRE_EXPR_CONSTANT (sprimeexpr);
> + ? ? ? ? ? ? else if (sprimeexpr->kind == NAME)
> + ? ? ? ? ? ? ? sprime = PRE_EXPR_NAME (sprimeexpr);
> + ? ? ? ? ? ? else
> + ? ? ? ? ? ? ? gcc_unreachable ();
> + ? ? ? ? ? }
> + ? ? ? ? if (!sprimeexpr
> + ? ? ? ? ? ? || sprime == res)
> + ? ? ? ? ? {
> + ? ? ? ? ? ? gsi_next (&gsi);
> + ? ? ? ? ? ? continue;
> + ? ? ? ? ? }
> +
> + ? ? ? ? if (dump_file && (dump_flags & TDF_DETAILS))
> + ? ? ? ? ? {
> + ? ? ? ? ? ? fprintf (dump_file, "Replaced redundant PHI node defining ");
> + ? ? ? ? ? ? print_generic_expr (dump_file, res, 0);
> + ? ? ? ? ? ? fprintf (dump_file, " with ");
> + ? ? ? ? ? ? print_generic_expr (dump_file, sprime, 0);
> + ? ? ? ? ? ? fprintf (dump_file, "\n");
> + ? ? ? ? ? }
> +
> + ? ? ? ? remove_phi_node (&gsi, false);
> +
> + ? ? ? ? stmt = gimple_build_assign (res, sprime);
> + ? ? ? ? SSA_NAME_DEF_STMT (res) = stmt;
> + ? ? ? ? if (TREE_CODE (sprime) == SSA_NAME)
> + ? ? ? ? ? gimple_set_plf (SSA_NAME_DEF_STMT (sprime),
> + ? ? ? ? ? ? ? ? ? ? ? ? ? NECESSARY, true);
> + ? ? ? ? gsi2 = gsi_after_labels (b);
> + ? ? ? ? gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
> + ? ? ? ? /* Queue the copy for eventual removal. ?*/
> + ? ? ? ? VEC_safe_push (gimple, heap, to_remove, stmt);
> + ? ? ? ? pre_stats.eliminations++;
> + ? ? ? }
> ? ? ?}
>
> ? ?/* We cannot remove stmts during BB walk, especially not release SSA
> ! ? ? ?names there as this confuses the VN machinery. ?The stmts ending
> ! ? ? ?up in to_remove are either stores or simple copies. ?*/
> ? ?for (i = 0; VEC_iterate (gimple, to_remove, i, stmt); ++i)
> ? ? ?{
> ! ? ? ? tree lhs = gimple_assign_lhs (stmt);
> ! ? ? ? use_operand_p use_p;
> ! ? ? ? gimple use_stmt;
> !
> ! ? ? ? /* If there is a single use only, propagate the equivalency
> ! ? ? ? ?instead of keeping the copy. ?*/
> ! ? ? ? if (TREE_CODE (lhs) == SSA_NAME
> ! ? ? ? ? && single_imm_use (lhs, &use_p, &use_stmt))
> ! ? ? ? {
> ! ? ? ? ? SET_USE (use_p, gimple_assign_rhs1 (stmt));
> ! ? ? ? ? update_stmt (stmt);
> ! ? ? ? }
> !
> ! ? ? ? /* If this is a store or a now unused copy, remove it. ?*/
> ! ? ? ? if (TREE_CODE (lhs) != SSA_NAME
> ! ? ? ? ? || has_zero_uses (lhs))
> ! ? ? ? {
> ! ? ? ? ? gsi = gsi_for_stmt (stmt);
> ! ? ? ? ? unlink_stmt_vdef (stmt);
> ! ? ? ? ? gsi_remove (&gsi, true);
> ! ? ? ? ? release_defs (stmt);
> ! ? ? ? }
> ? ? ?}
> ? ?VEC_free (gimple, heap, to_remove);
>
> *************** init_pre (bool do_fre)
> *** 4296,4301 ****
> --- 4378,4384 ----
> ? ?calculate_dominance_info (CDI_DOMINATORS);
>
> ? ?bitmap_obstack_initialize (&grand_bitmap_obstack);
> + ? inserted_phi_names = BITMAP_ALLOC (&grand_bitmap_obstack);
> ? ?phi_translate_table = htab_create (5110, expr_pred_trans_hash,
> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? expr_pred_trans_eq, free);
> ? ?expression_to_id = htab_create (num_ssa_names * 3,
> Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-23.c
> ===================================================================
> *** /dev/null ? 1970-01-01 00:00:00.000000000 +0000
> --- gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-23.c ?2009-04-04 16:54:25.000000000 +0200
> ***************
> *** 0 ****
> --- 1,21 ----
> + /* { dg-do compile } */
> + /* { dg-options "-O -fdump-tree-fre" } */
> +
> + int f(int t, int a, int b)
> + {
> + ? int c, d;
> + ? if (t)
> + ? ? {
> + ? ? ? c = a;
> + ? ? ? d = a;
> + ? ? }
> + ? else
> + ? ? {
> + ? ? ? c = b;
> + ? ? ? d = b;
> + ? ? }
> + ? return c+d;
> + }
> +
> + /* { dg-final { scan-tree-dump-times "PHI" 1 "fre" } } */
> + /* { dg-final { cleanup-tree-dump "fre" } } */
> Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-1.c
> ===================================================================
> *** gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-1.c.orig ? ?2007-09-07 17:37:28.000000000 +0200
> --- gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-1.c 2009-04-04 16:54:25.000000000 +0200
> *************** void vnum_test8(int *data)
> *** 17,21 ****
> ? ?}
> ?}
> ?/* We should eliminate m - n, and set n = n + k into n = m. */
> ! /* { dg-final { scan-tree-dump-times "Eliminated: 2" 1 "fre"} } */
> ?/* { dg-final { cleanup-tree-dump "fre" } } */
> --- 17,21 ----
> ? ?}
> ?}
> ?/* We should eliminate m - n, and set n = n + k into n = m. */
> ! /* { dg-final { scan-tree-dump-times "Eliminated: 3" 1 "fre"} } */
> ?/* { dg-final { cleanup-tree-dump "fre" } } */
> Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-2.c
> ===================================================================
> *** gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-2.c.orig ? ?2007-09-07 17:37:28.000000000 +0200
> --- gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-2.c 2009-04-04 16:54:25.000000000 +0200
> *************** int vnum_test8(int *data)
> *** 21,25 ****
> ?}
> ?/* We should eliminate m - n, and set n = n + k into n = m, and
> ? ? set p to 0 */
> ! /* { dg-final { scan-tree-dump-times "Eliminated: 3" 1 "fre"} } */
> ?/* { dg-final { cleanup-tree-dump "fre" } } */
> --- 21,25 ----
> ?}
> ?/* We should eliminate m - n, and set n = n + k into n = m, and
> ? ? set p to 0 */
> ! /* { dg-final { scan-tree-dump-times "Eliminated: 4" 1 "fre"} } */
> ?/* { dg-final { cleanup-tree-dump "fre" } } */
> Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-4.c
> ===================================================================
> *** gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-4.c.orig ? ?2007-09-07 17:37:28.000000000 +0200
> --- gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-4.c 2009-04-04 16:54:25.000000000 +0200
> *************** int vnum_test8(int *data)
> *** 23,27 ****
> ?}
> ?/* We should eliminate m - n, n + k, set data[5] = 0, eliminate the
> ? ? address arithmetic for data[5], and set p = 0.
> ! /* { dg-final { scan-tree-dump-times "Eliminated: 5" 1 "fre"} } */
> ?/* { dg-final { cleanup-tree-dump "fre" } } */
> --- 23,27 ----
> ?}
> ?/* We should eliminate m - n, n + k, set data[5] = 0, eliminate the
> ? ? address arithmetic for data[5], and set p = 0.
> ! /* { dg-final { scan-tree-dump-times "Eliminated: 6" 1 "fre"} } */
> ?/* { dg-final { cleanup-tree-dump "fre" } } */
>