===================================================================
@@ -753,6 +753,19 @@ delete_basic_block_same_succ (basic_bloc
bitmap_set_bit (deleted_bb_preds, e->src->index);
}
+/* Removes BB from its corresponding same_succ. */
+
+static void
+same_succ_flush_bb (basic_block bb)
+{
+ same_succ same = BB_SAME_SUCC (bb);
+ BB_SAME_SUCC (bb) = NULL;
+ if (bitmap_single_bit_set_p (same->bbs))
+ htab_remove_elt_with_hash (same_succ_htab, same, same->hashval);
+ else
+ bitmap_clear_bit (same->bbs, bb->index);
+}
+
/* Removes all bbs in BBS from their corresponding same_succ. */
static void
@@ -762,15 +775,7 @@ same_succ_flush_bbs (bitmap bbs)
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
- {
- basic_block bb = BASIC_BLOCK (i);
- same_succ same = BB_SAME_SUCC (bb);
- BB_SAME_SUCC (bb) = NULL;
- if (bitmap_single_bit_set_p (same->bbs))
- htab_remove_elt_with_hash (same_succ_htab, same, same->hashval);
- else
- bitmap_clear_bit (same->bbs, i);
- }
+ same_succ_flush_bb (BASIC_BLOCK (i));
}
/* Release the last vdef in BB, either normal or phi result. */
@@ -807,23 +812,8 @@ release_last_vdef (basic_block bb)
/* Delete all deleted_bbs. */
static void
-purge_bbs (bool update_vops)
+purge_bbs (void)
{
- unsigned int i;
- bitmap_iterator bi;
- basic_block bb;
-
- same_succ_flush_bbs (deleted_bbs);
-
- EXECUTE_IF_SET_IN_BITMAP (deleted_bbs, 0, i, bi)
- {
- bb = BASIC_BLOCK (i);
- if (!update_vops)
- release_last_vdef (bb);
-
- delete_basic_block (bb);
- }
-
bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
bitmap_clear (deleted_bbs);
}
@@ -1363,26 +1353,54 @@ find_clusters (void)
}
}
+static void
+unlink_virtual_phi (gimple phi, tree name)
+{
+ use_operand_p use_p;
+ imm_use_iterator iter;
+ gimple use_stmt;
+ tree vdef = gimple_phi_result (phi);
+
+ if (!vdef
+ || TREE_CODE (vdef) != SSA_NAME)
+ return;
+
+ FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
+ {
+ FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+ SET_USE (use_p, name);
+ }
+
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef))
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name) = 1;
+}
+
/* Create or update a vop phi in BB2. Use VUSE1 arguments for all the
REDIRECTED_EDGES, or if VUSE1 is NULL_TREE, use BB_VOP_AT_EXIT. If a new
phis is created, use the phi instead of VUSE2 in BB2. */
static void
-update_vuses (tree vuse1, tree vuse2, basic_block bb2,
+update_vuses (bool vuse1_phi_args, tree vuse1, tree vuse2, basic_block bb2,
VEC (edge,heap) *redirected_edges)
{
gimple stmt, phi = NULL;
- tree lhs = NULL_TREE, arg;
+ tree lhs = NULL_TREE, arg, var;
unsigned int i;
- gimple def_stmt2;
+ gimple def_stmt2 = NULL;
imm_use_iterator iter;
use_operand_p use_p;
edge_iterator ei;
edge e;
- def_stmt2 = SSA_NAME_DEF_STMT (vuse2);
+ if (vuse2 != NULL_TREE)
+ {
+ var = SSA_NAME_VAR (vuse2);
+ def_stmt2 = SSA_NAME_DEF_STMT (vuse2);
+ }
+ else
+ var = SSA_NAME_VAR (vuse1);
- if (gimple_bb (def_stmt2) == bb2)
+ if (def_stmt2 && gimple_bb (def_stmt2) == bb2)
/* Update existing phi. */
phi = def_stmt2;
else
@@ -1392,38 +1410,41 @@ update_vuses (tree vuse1, tree vuse2, ba
return;
/* Create a phi. */
- lhs = make_ssa_name (SSA_NAME_VAR (vuse2), NULL);
+ lhs = make_ssa_name (var, NULL);
VN_INFO_GET (lhs);
phi = create_phi_node (lhs, bb2);
SSA_NAME_DEF_STMT (lhs) = phi;
/* Set default argument vuse2 for all preds. */
+ arg = vuse2 == NULL_TREE ? gimple_phi_result (phi): vuse2;
FOR_EACH_EDGE (e, ei, bb2->preds)
- add_phi_arg (phi, vuse2, e, UNKNOWN_LOCATION);
+ add_phi_arg (phi, arg, e, UNKNOWN_LOCATION);
}
/* Update phi. */
for (i = 0; i < EDGE_COUNT (redirected_edges); ++i)
{
e = VEC_index (edge, redirected_edges, i);
- if (vuse1 != NULL_TREE)
- arg = vuse1;
- else
+ if (vuse1_phi_args)
arg = BB_VOP_AT_EXIT (e->src);
+ else
+ arg = vuse1 == NULL_TREE ? gimple_phi_result (phi): vuse1;
+
add_phi_arg (phi, arg, e, UNKNOWN_LOCATION);
}
/* Return if we updated an existing phi. */
- if (gimple_bb (def_stmt2) == bb2)
+ if (def_stmt2 && gimple_bb (def_stmt2) == bb2)
return;
- /* Replace relevant uses of vuse2 with the newly created phi. */
- FOR_EACH_IMM_USE_STMT (stmt, iter, vuse2)
+ /* Replace relevant uses with the newly created phi. */
+ FOR_EACH_IMM_USE_STMT (stmt, iter, vuse2 == NULL_TREE ? vuse1 : vuse2)
{
if (stmt == phi)
continue;
- if (gimple_code (stmt) != GIMPLE_PHI)
- if (gimple_bb (stmt) != bb2)
+
+ if (gimple_code (stmt) != GIMPLE_PHI &&
+ !dominated_by_p (CDI_DOMINATORS, gimple_bb (stmt), bb2))
continue;
FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
@@ -1432,8 +1453,16 @@ update_vuses (tree vuse1, tree vuse2, ba
{
unsigned int pred_index = PHI_ARG_INDEX_FROM_USE (use_p);
basic_block pred = EDGE_PRED (gimple_bb (stmt), pred_index)->src;
- if (pred != bb2)
+ if (!dominated_by_p (CDI_DOMINATORS, pred, bb2))
continue;
+
+ if (pred == bb2 && EDGE_COUNT (gimple_bb (stmt)->preds) == 2)
+ {
+ gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+ unlink_virtual_phi (stmt, lhs);
+ remove_phi_node (&gsi, true);
+ break;
+ }
}
SET_USE (use_p, lhs);
update_stmt (stmt);
@@ -1507,6 +1536,8 @@ replace_block_by (basic_block bb1, basic
VEC (edge,heap) *redirected_edges = NULL;
edge e;
edge_iterator ei;
+ bool vuse1_phi_args = false;
+ VEC (basic_block,heap) *fix_dom_bb;
phi_vuse2 = vop_at_entry (bb2);
if (phi_vuse2 != NULL_TREE && TREE_CODE (phi_vuse2) != SSA_NAME)
@@ -1517,11 +1548,11 @@ replace_block_by (basic_block bb1, basic
/* Find the vops at entry of bb1 and bb2. */
phi_vuse1 = vop_at_entry (bb1);
- /* If one of the 2 not found, it means there's no need to update. */
- update_vops = phi_vuse1 != NULL_TREE && phi_vuse2 != NULL_TREE;
+ /* If both are not found, it means there's no need to update. */
+ update_vops = phi_vuse1 != NULL_TREE || phi_vuse2 != NULL_TREE;
}
- if (update_vops && gimple_bb (SSA_NAME_DEF_STMT (phi_vuse1)) == bb1)
+ if (phi_vuse1 && gimple_bb (SSA_NAME_DEF_STMT (phi_vuse1)) == bb1)
{
/* If the vop at entry of bb1 is a phi, save the phi alternatives in
BB_VOP_AT_EXIT, before we lose that information by redirecting the
@@ -1531,7 +1562,7 @@ replace_block_by (basic_block bb1, basic
arg = PHI_ARG_DEF_FROM_EDGE (SSA_NAME_DEF_STMT (phi_vuse1), e);
BB_VOP_AT_EXIT (e->src) = arg;
}
- phi_vuse1 = NULL;
+ vuse1_phi_args = true;
}
/* Mark the basic block for later deletion. */
@@ -1556,9 +1587,22 @@ replace_block_by (basic_block bb1, basic
/* Update the vops. */
if (update_vops)
{
- update_vuses (phi_vuse1, phi_vuse2, bb2, redirected_edges);
+ update_vuses (vuse1_phi_args, phi_vuse1, phi_vuse2, bb2,
+ redirected_edges);
VEC_free (edge, heap, redirected_edges);
}
+ else
+ release_last_vdef (bb1);
+
+ same_succ_flush_bb (bb1);
+ delete_basic_block (bb1);
+
+ fix_dom_bb = VEC_alloc (basic_block, heap, 2);
+ VEC_safe_push (basic_block, heap, fix_dom_bb, bb2);
+ FOR_EACH_EDGE (e, ei, bb2->succs)
+ VEC_safe_push (basic_block, heap, fix_dom_bb, e->dest);
+ iterate_fix_dominators (CDI_DOMINATORS, fix_dom_bb, false);
+ VEC_free (basic_block, heap, fix_dom_bb);
}
/* Bbs for which update_debug_stmt need to be called. */
@@ -1708,13 +1752,11 @@ tail_merge_optimize (unsigned int todo)
if (nr_bbs_removed == 0)
break;
- free_dominance_info (CDI_DOMINATORS);
- purge_bbs (update_vops);
+ purge_bbs ();
if (iteration_nr == max_iterations)
break;
- calculate_dominance_info (CDI_DOMINATORS);
update_worklist ();
}
@@ -1724,7 +1766,6 @@ tail_merge_optimize (unsigned int todo)
if (nr_bbs_removed_total > 0)
{
- calculate_dominance_info (CDI_DOMINATORS);
update_debug_stmts ();
if (dump_file && (dump_flags & TDF_DETAILS))
===================================================================
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-dominator-opts -fdump-tree-pre" } */
+
+int bar (int i);
+
+void
+foo (int c, int d)
+{
+ if (bar (c))
+ bar (c);
+ d = 33;
+ while (c == d);
+}
+
+/* { dg-final { scan-tree-dump-times "== 33" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
Richard, I have a fix for PR50763. The second example from the PR looks like this: ... int bar (int i); void foo (int c, int d) { if (bar (c)) bar (c); d = 33; while (c == d); } ... When compiled with -O2 -fno-dominator-opt, the gimple representation before ftree-tail-merge looks like this: ... foo (intD.6 cD.1606, intD.6 dD.1607) { intD.6 D.2730; # BLOCK 2 freq:900 # PRED: ENTRY [100.0%] (fallthru,exec) # .MEMD.2733_6 = VDEF <.MEMD.2733_5(D)> # USE = nonlocal # CLB = nonlocal D.2730_2 = barD.1605 (cD.1606_1(D)); if (D.2730_2 != 0) goto <bb 3>; else goto <bb 7>; # SUCC: 3 [29.0%] (true,exec) 7 [71.0%] (false,exec) # BLOCK 7 freq:639 # PRED: 2 [71.0%] (false,exec) goto <bb 4>; # SUCC: 4 [100.0%] (fallthru) # BLOCK 3 freq:261 # PRED: 2 [29.0%] (true,exec) # .MEMD.2733_7 = VDEF <.MEMD.2733_6> # USE = nonlocal # CLB = nonlocal barD.1605 (cD.1606_1(D)); # SUCC: 4 [100.0%] (fallthru,exec) # BLOCK 4 freq:900 # PRED: 7 [100.0%] (fallthru) 3 [100.0%] (fallthru,exec) # .MEMD.2733_4 = PHI <.MEMD.2733_6(7), .MEMD.2733_7(3)> if (cD.1606_1(D) == 33) goto <bb 8>; else goto <bb 9>; # SUCC: 8 [91.0%] (true,exec) 9 [9.0%] (false,exec) # BLOCK 9 freq:81 # PRED: 4 [9.0%] (false,exec) goto <bb 6>; # SUCC: 6 [100.0%] (fallthru) # BLOCK 8 freq:819 # PRED: 4 [91.0%] (true,exec) # SUCC: 5 [100.0%] (fallthru) # BLOCK 5 freq:9100 # PRED: 8 [100.0%] (fallthru) 10 [100.0%] (fallthru) if (cD.1606_1(D) == 33) goto <bb 10>; else goto <bb 11>; # SUCC: 10 [91.0%] (true,exec) 11 [9.0%] (false,exec) # BLOCK 10 freq:8281 # PRED: 5 [91.0%] (true,exec) goto <bb 5>; # SUCC: 5 [100.0%] (fallthru) # BLOCK 11 freq:819 # PRED: 5 [9.0%] (false,exec) # SUCC: 6 [100.0%] (fallthru) # BLOCK 6 freq:900 # PRED: 11 [100.0%] (fallthru) 9 [100.0%] (fallthru) # VUSE <.MEMD.2733_4> return; # SUCC: EXIT [100.0%] } ... During the first iteration, tail_merge_optimize finds that block 9 and 11, and block 8 and 10 are equal, and removes block 11 and 10. During the second iteration it finds that block 4 and block 5 are equal, and it removes block 5. Since pre had no effect, the responsibility for updating the vops lies with tail_merge_optimize. Block 4 starts with a virtual PHI which needs updating, but replace_block_by decides that an update is not necessary, because vop_at_entry returns NULL_TREE for block 5 (the vop_at_entry for block 4 is .MEMD.2733_4). What is different from normal is that block 4 dominates block 5. The patch makes sure that the vops are also updated if vop_at_entry is defined for only one of bb1 and bb2. This also forced me to rewrite the code that updates the uses, which uses dominator info now. This forced me to keep the dominator info up-to-date. Which forced me to move the actual deletion of the basic block and some additional bookkeeping related to that from purge_bbs to replace_block_by. Additionally, I fixed the case that update_vuses leaves virtual phis with only one argument (see unlink_virtual_phi). bootstrapped and reg-tested on x86_64. The tested patch had one addition to the attached patch: calling verify_dominators at the end of replace_block_by. OK for trunk? Thanks, - Tom 2011-10-20 Tom de Vries <tom@codesourcery.com> PR tree-optimization/50763 * tree-ssa-tail-merge.c (same_succ_flush_bb): New function, factored out of ... (same_succ_flush_bbs): Use same_succ_flush_bb. (purge_bbs): Remove argument. Remove calls to same_succ_flush_bbs, release_last_vdef and delete_basic_block. (unlink_virtual_phi): New function. (update_vuses): Add and use vuse1_phi_args argument. Set var to SSA_NAME_VAR of vuse1 or vuse2, and use var. Handle case that def_stmt2 is NULL. Use phi result as phi arg in case vuse1 or vuse2 is NULL_TREE. Replace uses of vuse1 if vuse2 is NULL_TREE. Fix code to limit replacement of uses. Propagate phi argument for phis with a single argument. (replace_block_by): Update vops if phi_vuse1 or phi_vuse2 is NULL_TREE. Set vuse1_phi_args if vuse1 is a phi defined in bb1. Add vuse1_phi_args as argument to call to update_vuses. Call release_last_vdef, same_succ_flush_bb, delete_basic_block. Update CDI_DOMINATORS info. (tail_merge_optimize): Remove argument in call to purge_bbs. Remove call to free_dominance_info. Only call calculate_dominance_info once. * gcc.dg/pr50763.c: New test.