On Mon, Oct 31, 2011 at 9:19 PM, Tom de Vries <tom_devr...@mentor.com> wrote: > On 10/30/2011 10:54 AM, Richard Guenther wrote: >> On Sun, Oct 30, 2011 at 9:27 AM, Tom de Vries <tom_devr...@mentor.com> wrote: >>> On 10/30/2011 09:20 AM, Tom de Vries wrote: >>>> Richard, >>>> >>>> I have a fix for PR50878. >>> >>> Sorry, with patch this time. >> >> Ok for now, but see Davids mail and the complexity issue with iteratively >> updating dominators. > > I'm not sure which mail you mean.
The one I CCed you on, which complained about iterative dominator fixing taking 70% of the compile-time in some GCC testsuite test. >> It seems to me that we know exactly what to update >> and how, and we should do that (well, if we need up-to-date dominators, >> re-computing them once in the pass would be ok). >> > > Indeed, in this example we know exactly what to update and how. However, > PR50908 > popped up, and there that's not the case anymore. > > Consider the following cfg, where A is the direct dominator of I: > > A > / \ > B \ > / \ \ > C D > /| |\ > E F > |\ /| > | x | > |/ \| > G H > \ / > I > > Say E and F are duplicates, and F is removed. The cfg then looks like > this: > > A > / \ > B \ > / \ \ > C D > / \ / \ > E > / \ > G H > \ / > I > > E is now the new direct dominator of I. > > The patch for PR50878 did not address this example, since it uses the set of > bbs > directly dominated by the (single) predecessor of bb1 and bb2. > > The new patch calculates the updated dominator info by taking the nearest > common > dominator (A) of bb1 (F) and bb2 (E), and getting the set of bbs immediately > dominated by it. Part of this set is now directly dominated by bb2. > > Ideally we would have a means to determine which bbs in the set are now > directly dominated by bb2, and call set_immediate_dominator for those bbs, but > we don't, so instead we let iterate_fix_dominators figure it out. > > Additionally, the patch makes sure it updates dominator info before updating > the > vuses, this fixes a latent bug. > > The patch fixes both PR50908 and PR50878. > > Bootstrapped and reg-tested on x86_64 and i686, and build and reg-tested on > ARM > and MIPS. > > Ok for trunk? Ok, but please add testcases for all the bugs you fixed. This helps adding test coverage for these cases. Thanks, Richard. > Thanks, > - Tom > >> Richard. >> >>> Thanks, >>> - Tom >>> >>>> >>>> A simplified form of the problem from the test-case of the PR is shown in >>>> this >>>> cfg. Block 12 has as direct dominator block 5. >>>> >>>> 5 >>>> / \ >>>> / \ >>>> * * >>>> 6 7 >>>> | | >>>> | | >>>> * * >>>> 8 9 >>>> \ / >>>> \ / >>>> * >>>> 12 >>>> >>>> tail_merge_optimize finds that blocks 6 and 7 are duplicates. After >>>> replacing >>>> block 7 by block 6, the cfg looks like this: >>>> >>>> 5 >>>> | >>>> | >>>> * >>>> 6 >>>> / \ >>>> / \ >>>> * * >>>> 8 9 >>>> \ / >>>> \ / >>>> * >>>> 12 >>>> >>>> The new direct dominator of block 12 is block 6, but the current algorithm >>>> only >>>> recalculates dominator info for blocks 6, 8 and 9. >>>> >>>> The patch fixes this by additionally recalculating the dominator info for >>>> blocks >>>> immediately dominated by bb2 (block 6 in the example), if bb2 has a single >>>> predecessor after replacement. >>>> >>>> Bootstapped and reg-tested on x86_64 and i686. Build and reg-tested on >>>> MIPS and ARM. >>>> >>>> Ok for trunk? >>>> >>>> Thanks, >>>> - Tom >>>> >>>> 2011-10-30 Tom de Vries <t...@codesourcery.com> >>>> >>>> PR tree-optimization/50878 >>>> * tree-ssa-tail-merge.c (replace_block_by): Recalculate dominator >>>> info >>>> for blocks immediately dominated by bb2, if bb2 has a single >>>> predecessor >>>> after replacement. >>> >>> > > 2011-10-31 Tom de Vries <t...@codesourcery.com> > > PR tree-optimization/50908 > * tree-ssa-tail-merge.c (update_vuses): Now that edges are removed > before update_vuses, test for 1 predecessor rather than two. > (delete_block_update_dominator_info): New function, part of it factored > out of ... > (replace_block_by): Use delete_block_update_dominator_info. Call > update_vuses after deleting bb1 and updating dominator info, instead of > before. >
