Early jump threading

[Richard Biener]

On August 11, 2016 4:27:00 PM GMT+02:00, Jan Hubicka <hubicka@ucw.cz> 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.
>> 
>> I wonder why you choose to put the FSM threader early which only does
>> backward threading(?!).  I'd expect forward threading to be more
>> profitable (though we don't have a separate threader for that and
>> would need VRP or DOM - but it seems we will get an early VRP
>anyway).
>
>On tramp3d all VRP passes threads together 730 branches, all DOM passes
>393, so
>FSM threading (with 1957 branches) is the most effective one. Perhaps
>eventually
>early VRP can also do bit of work.
>
>I am not 100% sure from where "backward" is comming from. I guess is
>means that
>analysis goes backward from conditionals to definitions: it looks for
>conditional driven by a PHI statement that has a constant value on some
>paths
>and duplicates for those. This seems cheap and rather effective way of
>getting
>good part of the threading oppurtunities (most expensive part is
>probably
>identifying and walking paths that will not be threaded at the end).

Ah, I thought it was exclusively dealing with threading through back edges which is sth I'd avoid doing early?

>BTW I wonder if the same analysis can't be done for other instructions
>where constant
>operands are very profitable, like division or multiplication.

No idea, but Jeff will likely know.

Richard.

>
>Honza