On Thu, Oct 20, 2011 at 3:48 PM, Tom de Vries <tom_devr...@mentor.com> wrote:
> 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?
+ if (gimple_code (stmt) != GIMPLE_PHI &&
+ !dominated_by_p (CDI_DOMINATORS, gimple_bb (stmt), bb2))
continue;
&&s go to the next line please.
The unlink_virtual_phi function needs a comment.
Ok with that changes.
Richard.
> Thanks,
> - Tom
>
> 2011-10-20 Tom de Vries <t...@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.
>
