Re: Early jump threading

[Jeff Law <law@redhat.com>]

On 08/12/2016 02:02 AM, Richard Biener wrote:
> On Thu, 11 Aug 2016, Jan Hubicka wrote:
>
>> Hi,
>> this patch adds early jump threading pass.  Jump threading is one of most
>> common cases where estimated profile becomes corrupted, because the branches
>> are predicted independently beforehand. This patch simply adds early mode to
>> jump threader that does not permit code growth and thus only win/win threads
>> are done before profile is constructed.
>>
>> Naturally this also improves IPA decisions because code size/time is estimated
>> more acurately.
>>
>> It is not very cool to add another pass and the jump threader is already
>> run 5 times. I think incrementally we could drop one of late threaders at least.
>> I tried to measure compile time effects but they are in wash. Moreover the patch
>> pays for itself in cc1plus code size:
>>
>> Before patch to tweak size estimates: 27779964
>> Current mainline:                     27748900
>> With patch applied:                   27716173
>>
>> So despite adding few functions the code size effect is positive which I think
>> is quite nice.
>>
>> Given the fact that jump threading seems quite lightweit, I wonder why it is
>> guarded by flag_expensive_optimizations? Is it expensive in terms of code
>> size?
>>
>> The effectivity of individual threading passes is as follows (for tramp3d)
>>
>>       mainline                              with patch
>> pass  thread count     profile mismatches   thread count    profile mismatch
>> early                                       525
>> 1     1853             1900                 316             337
>> 2     4                812                  4               288
>> 3     24               1450                 32              947
>> 4     76               1457                 75              975
>>
>> So at least tramp3d data seems to suggest that we can drop the second occurence
>> of jump threading and that most of the job thread1 does can be done by the
>> size restricted early version (the lower absolute counts are caused by the
>> fact that threadable paths gets duplicated by the inliner). 50% drop in
>> profile distortion is not bad. I wonder why basically every threaded paths seems
>> to introduce a mismatch.
>>
>> The patch distorts testusite somewhat, in most cases we only want to update
>> dump files or disable early threading:
>>
>> +XPASS: gcc.dg/uninit-15.c  (test for warnings, line 13)
>> +XPASS: gcc.dg/uninit-15.c  (test for warnings, line 23)
>> +FAIL: gcc.dg/uninit-15.c  (test for warnings, line 24)
>> +FAIL: gcc.dg/tree-ssa/pr68198.c scan-tree-dump-times thread1 "Registering FSM" 1
>> +FAIL: gcc.dg/tree-ssa/pr69196-1.c scan-tree-dump thread1 "FSM did not thread around loop and would copy too many statements"
>> +FAIL: gcc.dg/tree-ssa/ssa-dom-thread-2b.c scan-tree-dump-times thread1 "Jumps threaded: 1" 1
>> +FAIL: gcc.dg/tree-ssa/ssa-thread-13.c scan-tree-dump thread1 "FSM"
>> +FAIL: gcc.dg/tree-ssa/vrp01.c scan-tree-dump-times vrp1 "Folding predicate p_.*to 1" 1
>> +FAIL: gcc.dg/tree-ssa/vrp56.c scan-tree-dump thread1 "Jumps threaded: 1"
>> +FAIL: gcc.dg/tree-ssa/vrp92.c scan-tree-dump vrp1 "res_.: \\\\[1, 1\\\\]"
>>
>> This testcase is the now probably unnecesary heuristics (it may still be
>> relevant in cases we do not thread because of size bounds but its effectivity
>> may not be worth the maintenance cost):
>>
>> +FAIL: g++.dg/predict-loop-exit-1.C  -std=gnu++11  scan-tree-dump-times profile_estimate "extra loop exit heuristics of edge[^:]*:" 2
>> +FAIL: g++.dg/predict-loop-exit-1.C  -std=gnu++11  scan-tree-dump-times profile_estimate "loop exit heuristics of edge[^:]*:" 3
>> +FAIL: g++.dg/predict-loop-exit-1.C  -std=gnu++14  scan-tree-dump-times profile_estimate "extra loop exit heuristics of edge[^:]*:" 2
>> +FAIL: g++.dg/predict-loop-exit-1.C  -std=gnu++14  scan-tree-dump-times profile_estimate "loop exit heuristics of edge[^:]*:" 3
>> +FAIL: g++.dg/predict-loop-exit-1.C  -std=gnu++98  scan-tree-dump-times profile_estimate "extra loop exit heuristics of edge[^:]*:" 2
>> +FAIL: g++.dg/predict-loop-exit-1.C  -std=gnu++98  scan-tree-dump-times profile_estimate "loop exit heuristics of edge[^:]*:" 3
>> +FAIL: g++.dg/predict-loop-exit-2.C  -std=gnu++11  scan-tree-dump-times profile_estimate "extra loop exit heuristics of edge[^:]*:" 1
>> +FAIL: g++.dg/predict-loop-exit-2.C  -std=gnu++11  scan-tree-dump-times profile_estimate "loop exit heuristics of edge[^:]*:" 2
>> +FAIL: g++.dg/predict-loop-exit-2.C  -std=gnu++14  scan-tree-dump-times profile_estimate "extra loop exit heuristics of edge[^:]*:" 1
>> +FAIL: g++.dg/predict-loop-exit-2.C  -std=gnu++14  scan-tree-dump-times profile_estimate "loop exit heuristics of edge[^:]*:" 2
>> +FAIL: g++.dg/predict-loop-exit-2.C  -std=gnu++98  scan-tree-dump-times profile_estimate "extra loop exit heuristics of edge[^:]*:" 1
>> +FAIL: g++.dg/predict-loop-exit-2.C  -std=gnu++98  scan-tree-dump-times profile_estimate "loop exit heuristics of edge[^:]*:" 2
>> +FAIL: g++.dg/predict-loop-exit-3.C  -std=gnu++11  scan-tree-dump-times profile_estimate "extra loop exit heuristics of edge[^:]*:" 2
>> +FAIL: g++.dg/predict-loop-exit-3.C  -std=gnu++11  scan-tree-dump-times profile_estimate "loop exit heuristics of edge[^:]*:" 3
>> +FAIL: g++.dg/predict-loop-exit-3.C  -std=gnu++14  scan-tree-dump-times profile_estimate "extra loop exit heuristics of edge[^:]*:" 2
>> +FAIL: g++.dg/predict-loop-exit-3.C  -std=gnu++14  scan-tree-dump-times profile_estimate "loop exit heuristics of edge[^:]*:" 3
>> +FAIL: g++.dg/predict-loop-exit-3.C  -std=gnu++98  scan-tree-dump-times profile_estimate "extra loop exit heuristics of edge[^:]*:" 2
>> +FAIL: g++.dg/predict-loop-exit-3.C  -std=gnu++98  scan-tree-dump-times profile_estimate "loop exit heuristics of edge[^:]*:" 3
>>
>> If the patch seems acceptable, I will do the updates. One option why I did
>> not do that is that it seems to be now posisble to pass parameters to passes
>> from passes.def, so perhaps we do not need early_thread_jumps, but doing so is
>> consistent with way we handle other early passes.
>
> Few comments on the patch itself below.  Note currently the pass is
> enabled at -O[s2]+ only which I think is fine.  We certainly do not
> want it at -Og.  (and nobody seems to try making -O1 sane anyway)
>
> Given your statistics we want to remove thread2 and thread3 (I guess
> tracer immediately before thread_jumps is odd as well, I'd at least
> swap them).  The fact that thread4 threads more than thread3 argues
> for DOM being required as a FSM thread enabler rather than the
> other way around.  So I'd try with generally moving the threader
> _after_ CSE-like optimizations.
What we want to be doing is threading *before* CSE-like optimizations 
and removing the DOM/VRP jump threaders.  Based on what I've seen for 
the last 15 years, threading helps CSE far more often than the opposite.

The fact that we do CSE first, then threading is an artifact of the 
threading implementation wanting to exploit the CSE tables.  But that's 
not necessary in a backwards walking threader.

So what we need to be going is figuring out what key things aren't being 
handled so that we can drop the DOM/VRP threaders.  Once that's done we 
will want to look at whether or not any of the standalone threading 
passes continue to make sense.

jeff