Re: [Patch] Improving jump-thread pass for PR 54742

[Richard Biener <richard dot guenther at gmail dot com>]

On Mon, Nov 24, 2014 at 11:05 PM, Sebastian Pop <sebpop@gmail.com> wrote:
> Jeff Law wrote:
>> On 11/23/14 15:22, Sebastian Pop wrote:
>> >The second patch attached limits the search for FSM jump threads to loops.  With
>> >that patch, we are now down to 470 jump threads in an x86_64-linux bootstrap
>> >(and 424 jump threads on powerpc64-linux bootstrap.)
>> >
>> Yea, that was one of the things I was going to poke at as well as a
>> quick scan of your patch gave me the impression it wasn't limited to
>> loops.
>>
>> Again, I haven't looked much at the patch, but I got the impression
>> you're doing a backwards walk through the predecessors to discover
>> the result of the COND_EXPR.  Correct?
>
> Yes.
>
>>
>> That's something I'd been wanting to do -- basically start with a
>> COND_EXPR, then walk the dataflow backwards substituting values into
>> the COND_EXPR (possibly creating non-gimple).  Ultimately the goal
>> is to substitute and fold, getting to a constant :-)
>>
>> The forward exhaustive stuff we do now is, crazy.   The backwards
>> approach could be decoupled from DOM & VRP into an independent pass,
>> which I think would be wise.
>>
>> Using a SEME region copier is also something I really wanted to do
>> long term.  In fact, I believe a lot of tree-ssa-threadupdate.c
>> ought to be ripped out and replaced with a SEME based copier.
>
> I did an experiment around these lines over the week-end, and now that you
> mention it, I feel less shy to speak about; well the patch does not yet pass
> bootstrap, and there still are about 20 failing test-cases.  I feel better
> reading the code generation part of jump-threading after this patch ;-)
> Basically I think all the tree-ssa-threadupdate.c can be replaced by
> duplicate_seme_region that generalizes the code generation.

Btw I once thought about doing on-the-fly lattice use/update and folding
during basic-block copying (or even re-generating expressions via
simplifying gimple_build ()).  Or have a substitute-and-fold like
facility that can run on SEME regions and do this.

Richard.

>> It appears you've built at least parts of two pieces needed to all
>> this as a Bodik style optimizer.  Which is exactly the long term
>> direction I think this code ought to take.
>>
>>
>> >
>> >One of the reasons I think we see more branches is that in sese region copying we
>> >do not use the knowledge of the value of the condition for the last branch in a
>> >jump-thread path: we rely on other propagation passes to remove the branch.  The
>> >last attached patch adds:
>> >
>> >   /* Remove the last branch in the jump thread path.  */
>> >   remove_ctrl_stmt_and_useless_edges (region_copy[n_region - 1], exit->dest);
>> That's certainly a possibility.  But I would expect that even with
>> this limitation something would be picking up the fact that the
>> branch is statically computable (even if it's an RTL optimizer).
>> But it's definitely something to look for.
>>
>> >
>> >Please let me know if the attached patches are producing better results on gcc.
>>
>> For the trunk:
>>   instructions:1339016494968
>>   branches     :243568982489
>>
>> First version of your patch:
>>
>>   instructions:1339739533291
>>   branches:     243806615986
>>
>> Latest version of your patch:
>>
>>   instructions:1339749122609
>>   branches:     243809838262
>
> I think I got about the same results.
>
> I got my scripts installed on the gcc-farm.  I first used an x86_64 gcc75 and
> valgrind was crashing not recognizing how to decode an instruction.  Then I
> moved to gcc112 a powerpc64-linux where I got this data from stage2 cc1plus
> compiling the same file alias.ii at -O2: (I got 3 runs of each mostly because
> there is a bit of noise in all these numbers)
>
> $ valgrind --tool=cachegrind --cache-sim=no --branch-sim=yes ./cc1plus -O2 ~/alias.ii
>
> all 4 patches:
>
> ==153617== I   refs:      13,914,038,211
> ==153617==
> ==153617== Branches:       1,926,407,760  (1,879,827,481 cond + 46,580,279 ind)
> ==153617== Mispredicts:      144,890,904  (  132,094,105 cond + 12,796,799 ind)
> ==153617== Mispred rate:             7.5% (          7.0%     +       27.4%   )
>
> ==34993== I   refs:      13,915,335,629
> ==34993==
> ==34993== Branches:       1,926,597,919  (1,880,017,558 cond + 46,580,361 ind)
> ==34993== Mispredicts:      144,974,266  (  132,177,440 cond + 12,796,826 ind)
> ==34993== Mispred rate:             7.5% (          7.0%     +       27.4%   )
>
> ==140841== I   refs:      13,915,334,459
> ==140841==
> ==140841== Branches:       1,926,597,819  (1,880,017,458 cond + 46,580,361 ind)
> ==140841== Mispredicts:      144,974,296  (  132,177,470 cond + 12,796,826 ind)
> ==140841== Mispred rate:             7.5% (          7.0%     +       27.4%   )
>
> patch 1:
>
> ==99902== I   refs:      13,915,069,710
> ==99902==
> ==99902== Branches:       1,926,963,813  (1,880,376,148 cond + 46,587,665 ind)
> ==99902== Mispredicts:      145,501,564  (  132,656,576 cond + 12,844,988 ind)
> ==99902== Mispred rate:             7.5% (          7.0%     +       27.5%   )
>
> ==3907== I   refs:      13,915,082,469
> ==3907==
> ==3907== Branches:       1,926,965,218  (1,880,377,471 cond + 46,587,747 ind)
> ==3907== Mispredicts:      145,501,569  (  132,656,554 cond + 12,845,015 ind)
> ==3907== Mispred rate:             7.5% (          7.0%     +       27.5%   )
>
> ==44271== I   refs:      13,915,111,997
> ==44271==
> ==44271== Branches:       1,926,968,863  (1,880,380,952 cond + 46,587,911 ind)
> ==44271== Mispredicts:      145,501,858  (  132,656,789 cond + 12,845,069 ind)
> ==44271== Mispred rate:             7.5% (          7.0%     +       27.5%   )
>
> master no-patch:
>
> ==129233== I   refs:      13,910,221,913
> ==129233==
> ==129233== Branches:       1,925,715,095  (1,879,277,776 cond + 46,437,319 ind)
> ==129233== Mispredicts:      144,133,332  (  131,510,534 cond + 12,622,798 ind)
> ==129233== Mispred rate:             7.4% (          6.9%     +       27.1%   )
>
> ==147659== I   refs:      13,910,216,249
> ==147659==
> ==147659== Branches:       1,925,714,029  (1,879,276,708 cond + 46,437,321 ind)
> ==147659== Mispredicts:      144,127,970  (  131,505,172 cond + 12,622,798 ind)
> ==147659== Mispred rate:             7.4% (          6.9%     +       27.1%   )
>
> ==155206== I   refs:      13,910,201,237
> ==155206==
> ==155206== Branches:       1,925,712,267  (1,879,275,030 cond + 46,437,237 ind)
> ==155206== Mispredicts:      144,128,313  (  131,505,542 cond + 12,622,771 ind)
> ==155206== Mispred rate:             7.4% (          6.9%     +       27.1%   )
>
>
> I think that there are about 5 million more instructions executed with the first
> patch, and the other patches on top do not really help.
>
>>
>> Which is in the noise for this test.  Which makes me wonder if I
>> botched something on the latest run.  It doesn't appear so, but I'm
>> re-running just to be sure.  I'm also turning on -g so that I can
>> use cg_annotate to poke a bit deeper and perhaps identify one or
>> more concrete examples where your patch is making this worse.
>
> Thanks,
> Sebastian