On 10/17/2011 01:51 PM, Richard Guenther wrote: > On Sun, Oct 16, 2011 at 12:05 PM, Tom de Vries <tom_devr...@mentor.com> wrote: >> On 10/14/2011 12:00 PM, Richard Guenther wrote: >>> On Fri, Oct 14, 2011 at 1:12 AM, Tom de Vries <tom_devr...@mentor.com> >>> wrote: >>>> On 10/12/2011 02:19 PM, Richard Guenther wrote: >>>>> On Wed, Oct 12, 2011 at 8:35 AM, Tom de Vries <vr...@codesourcery.com> >>>>> wrote: >>>>>> Richard, >>>>>> >>>>>> I have a patch for PR50672. >>>>>> >>>>>> When compiling the testcase from the PR with -ftree-tail-merge, the >>>>>> scenario is >>>>>> as follows: >>>>>> >>>>>> We start out tail_merge_optimize with blocks 14 and 20, which are alike, >>>>>> but not >>>>>> equal, since they have different successors: >>>>>> ... >>>>>> # BLOCK 14 freq:690 >>>>>> # PRED: 25 [61.0%] (false,exec) >>>>>> >>>>>> if (wD.2197_57(D) != 0B) >>>>>> goto <bb 15>; >>>>>> else >>>>>> goto <bb 16>; >>>>>> # SUCC: 15 [78.4%] (true,exec) 16 [21.6%] (false,exec) >>>>>> >>>>>> >>>>>> # BLOCK 20 freq:2900 >>>>>> # PRED: 29 [100.0%] (fallthru) 31 [100.0%] (fallthru) >>>>>> >>>>>> # .MEMD.2447_209 = PHI <.MEMD.2447_125(29), .MEMD.2447_129(31)> >>>>>> if (wD.2197_57(D) != 0B) >>>>>> goto <bb 5>; >>>>>> else >>>>>> goto <bb 6>; >>>>>> # SUCC: 5 [85.0%] (true,exec) 6 [15.0%] (false,exec) >>>>>> ... >>>>>> >>>>>> In the first iteration, we merge block 5 with block 15 and block 6 with >>>>>> block >>>>>> 16. After that, the blocks 14 and 20 are equal. >>>>>> >>>>>> In the second iteration, the blocks 14 and 20 are merged, by redirecting >>>>>> the >>>>>> incoming edges of block 20 to block 14, and removing block 20. >>>>>> >>>>>> Block 20 also contains the definition of .MEMD.2447_209. Removing the >>>>>> definition >>>>>> delinks the vuse of .MEMD.2447_209 in block 5: >>>>>> ... >>>>>> # BLOCK 5 freq:6036 >>>>>> # PRED: 20 [85.0%] (true,exec) >>>>>> >>>>>> # PT = nonlocal escaped >>>>>> D.2306_58 = &thisD.2200_10(D)->D.2156; >>>>>> # .MEMD.2447_132 = VDEF <.MEMD.2447_209> >>>>>> # USE = anything >>>>>> # CLB = anything >>>>>> drawLineD.2135 (D.2306_58, wD.2197_57(D), gcD.2198_59(D)); >>>>>> goto <bb 17>; >>>>>> # SUCC: 17 [100.0%] (fallthru,exec) >>>>>> ... >>>>> >>>>> And block 5 is retained and block 15 is discarded? >>>>> >>>> >>>> Indeed. >>>> >>>>>> After the pass, when executing the TODO_update_ssa_only_virtuals, we >>>>>> update the >>>>>> drawLine call in block 5 using rewrite_update_stmt, which calls >>>>>> maybe_replace_use for the vuse operand. >>>>>> >>>>>> However, maybe_replace_use doesn't have an effect since the old vuse and >>>>>> the new >>>>>> vuse happen to be the same (rdef == use), so SET_USE is not called and >>>>>> the vuse >>>>>> remains delinked: >>>>>> ... >>>>>> if (rdef && rdef != use) >>>>>> SET_USE (use_p, rdef); >>>>>> ... >>>>>> >>>>>> The patch fixes this by forcing SET_USE for delinked uses. >>>>> >>>>> That isn't the correct fix. Whoever unlinks the vuse (by removing its >>>>> definition) has to replace it with something valid, which is either the >>>>> bare symbol .MEM, or the VUSE associated with the removed VDEF >>>>> (thus, as unlink_stmt_vdef does). >>>>> >>>> >>>> Another try. For each deleted bb, we call unlink_stmt_vdef for the >>>> statements, >>>> and replace the .MEM phi uses with the bare .MEM symbol. >>>> >>>> Bootstrapped and reg-tested on x86_64. >>>> >>>> Ok for trunk? >>> >>> Better. For >>> >>> + >>> + FOR_EACH_IMM_USE_STMT (use_stmt, iter, res) >>> + { >>> + FOR_EACH_IMM_USE_ON_STMT (use_p, iter) >>> + SET_USE (use_p, SSA_NAME_VAR (res)); >>> + } >>> >>> you can use mark_virtual_phi_result_for_renaming (phi) instead. >>> >>> + for (i = gsi_last_bb (bb); !gsi_end_p (i); gsi_prev_nondebug (&i)) >>> + unlink_stmt_vdef (gsi_stmt (i)); >>> >>> is that actually necessary? That is, isn't the block that follows a >>> deleted block always starting with a virtual PHI? >> >> Block 20 is deleted. Block 5 follows the deleted block 20. Block 5 does not >> start with a virtual PHI. >> >>> If not it should >>> be enough to walk to the first stmt that uses a virtual operand >>> and similar to the PHI case replace all its uses with the bare >>> symbol. >> >> I think we need to handle the exposed uses (meaning outside the block) of >> vdefs >> in each deleted block. The only vdef that can have exposed uses is the last >> vdef >> in the block. So we should find the last vdef (gimple with gimple_vdef or >> virtual PHI) and handle the related uses. >> >> Bootstrapped and regtested on x86_64. OK for trunk? > > Hmmm. I can see that this will fail when the block has a store > but not a virtual PHI node, thus, when renaming does not reach > a bare .MEM symbol walking the use-def chain from the VUSE > of the store. What release_last_vdef should do is trigger a rename > of subsequent VUSEs in successors of the deleted block. Which > requires you to do something like > > static void > rename_last_vdef (basic_block bb) > { > + gimple_stmt_iterator i; > + > + for (i = gsi_last_bb (bb); !gsi_end_p (i); gsi_prev_nondebug (&i)) > + { > + gimple stmt = gsi_stmt (i); > + if (gimple_vdef (stmt) == NULL_TREE) > + continue; > + > + mark_virtual_operand_for_renaming (gimple_vdef (stmt)); > return; > } > > + for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i)) > + { > + gimple phi = gsi_stmt (i); > + tree res = gimple_phi_result (phi); > + > + if (is_gimple_reg (res)) > + continue; > + > + mark_virtual_phi_result_for_renaming (phi); > + return; > + } > } > > And split out the > > result_var = SSA_NAME_VAR (result_ssa); > FOR_EACH_IMM_USE_STMT (stmt, iter, result_ssa) > { > FOR_EACH_IMM_USE_ON_STMT (use_p, iter) > SET_USE (use_p, result_var); > update_stmt (stmt); > used = true; > } > if (used) > mark_sym_for_renaming (result_var); > > part of mark_virtual_phi_result_for_renaming into the new function > mark_virtual_operand_for_renaming (basically rename it and > make mark_virtual_phi_result_for_renaming a wrapper around it, > passing gimple_phi_result). > > Ok with a change as suggested above. >
Retested on x86_64 and committed. Thanks, - Tom > Thanks, > Richard. > 2011-10-18 Tom de Vries <t...@codesourcery.com> PR tree-optimization/50672 * tree-ssa-dce.c (mark_virtual_operand_for_renaming): New function, factored out of ... (mark_virtual_phi_result_for_renaming): Use mark_virtual_operand_for_renaming. * tree-flow.h (mark_virtual_operand_for_renaming): Declare. * tree-ssa-tail-merge.c (release_last_vdef): New function. (purge_bbs): Add update_vops parameter. Call release_last_vdef for each deleted basic block. (tail_merge_optimize): Add argument to call to purge_bbs.
Index: gcc/tree-ssa-tail-merge.c =================================================================== --- gcc/tree-ssa-tail-merge.c (revision 179773) +++ gcc/tree-ssa-tail-merge.c (working copy) @@ -773,18 +773,56 @@ same_succ_flush_bbs (bitmap bbs) } } +/* Release the last vdef in BB, either normal or phi result. */ + +static void +release_last_vdef (basic_block bb) +{ + gimple_stmt_iterator i; + + for (i = gsi_last_bb (bb); !gsi_end_p (i); gsi_prev_nondebug (&i)) + { + gimple stmt = gsi_stmt (i); + if (gimple_vdef (stmt) == NULL_TREE) + continue; + + mark_virtual_operand_for_renaming (gimple_vdef (stmt)); + return; + } + + for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i)) + { + gimple phi = gsi_stmt (i); + tree res = gimple_phi_result (phi); + + if (is_gimple_reg (res)) + continue; + + mark_virtual_phi_result_for_renaming (phi); + return; + } + +} + /* Delete all deleted_bbs. */ static void -purge_bbs (void) +purge_bbs (bool update_vops) { 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) - delete_basic_block (BASIC_BLOCK (i)); + { + 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); @@ -1665,7 +1703,7 @@ tail_merge_optimize (unsigned int todo) break; free_dominance_info (CDI_DOMINATORS); - purge_bbs (); + purge_bbs (update_vops); if (iteration_nr == max_iterations) break; Index: gcc/tree-ssa-dce.c =================================================================== --- gcc/tree-ssa-dce.c (revision 179773) +++ gcc/tree-ssa-dce.c (working copy) @@ -982,18 +982,36 @@ propagate_necessity (struct edge_list *e } } -/* Replace all uses of result of PHI by underlying variable and mark it +/* Replace all uses of NAME by underlying variable and mark it for renaming. */ void -mark_virtual_phi_result_for_renaming (gimple phi) +mark_virtual_operand_for_renaming (tree name) { bool used = false; imm_use_iterator iter; use_operand_p use_p; gimple stmt; - tree result_ssa, result_var; + tree name_var; + + name_var = SSA_NAME_VAR (name); + FOR_EACH_IMM_USE_STMT (stmt, iter, name) + { + FOR_EACH_IMM_USE_ON_STMT (use_p, iter) + SET_USE (use_p, name_var); + update_stmt (stmt); + used = true; + } + if (used) + mark_sym_for_renaming (name_var); +} +/* Replace all uses of result of PHI by underlying variable and mark it + for renaming. */ + +void +mark_virtual_phi_result_for_renaming (gimple phi) +{ if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Marking result for renaming : "); @@ -1001,19 +1019,10 @@ mark_virtual_phi_result_for_renaming (gi fprintf (dump_file, "\n"); } - result_ssa = gimple_phi_result (phi); - result_var = SSA_NAME_VAR (result_ssa); - FOR_EACH_IMM_USE_STMT (stmt, iter, result_ssa) - { - FOR_EACH_IMM_USE_ON_STMT (use_p, iter) - SET_USE (use_p, result_var); - update_stmt (stmt); - used = true; - } - if (used) - mark_sym_for_renaming (result_var); + mark_virtual_operand_for_renaming (gimple_phi_result (phi)); } + /* Remove dead PHI nodes from block BB. */ static bool Index: gcc/tree-flow.h =================================================================== --- gcc/tree-flow.h (revision 179773) +++ gcc/tree-flow.h (working copy) @@ -715,6 +715,7 @@ bool stmt_dominates_stmt_p (gimple, gimp void mark_virtual_ops_for_renaming (gimple); /* In tree-ssa-dce.c */ +void mark_virtual_operand_for_renaming (tree); void mark_virtual_phi_result_for_renaming (gimple); /* In tree-ssa-threadedge.c */