On 08/11/2016 08:02 AM, 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
So the real question here is what did VRP1 threading do between the
standalone thread1/thread2 passes. ie, it may look tempting to
eliminate the standalone thread2 pass, but threading done by VRP1 is
expected to be pushed into the thread{1,2} passes. So removing thread2
is premature at this point.
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)
This seems like a step backwards to me. We're warning about "j", but in
the context in which its used, we really ought to be warning about "i".
And we lost a later warning.
+FAIL: gcc.dg/tree-ssa/pr68198.c scan-tree-dump-times thread1 "Registering FSM"
1
Moved into early-threading, so adjusting test for that seems appropriate.
+FAIL: gcc.dg/tree-ssa/pr69196-1.c scan-tree-dump thread1 "FSM did not thread around
loop and would copy too many statements"
I'm not sure how to best check this one. Threading this test too
aggressively results in something like a 2X bloat in the resulting code
on the sparc.
+FAIL: gcc.dg/tree-ssa/ssa-dom-thread-2b.c scan-tree-dump-times thread1 "Jumps
threaded: 1" 1
Moved into early threading, so adjusting the test for that seems
appropriate to me.
+FAIL: gcc.dg/tree-ssa/ssa-thread-13.c scan-tree-dump thread1 "FSM"
Moved into early threading, so adjusting the test for that seems
appropriate to me.
+FAIL: gcc.dg/tree-ssa/vrp01.c scan-tree-dump-times vrp1 "Folding predicate p_.*to
1" 1
So the optimization moved into fre1 as a result of early jump threading
which is good. We should probably check for that, even if the test is
badly mis-named now.
But this is showing one of the cases where the backwards threader is
deficient. It's not using the conditional as an implied set. It's a
known limitation and I'm hoping Andrew's work makes that an easier
problem to solve.
+FAIL: gcc.dg/tree-ssa/vrp56.c scan-tree-dump thread1 "Jumps threaded: 1"
Moved into early threading, so adjusting the test for that seems
appropriate to me.
+FAIL: gcc.dg/tree-ssa/vrp92.c scan-tree-dump vrp1 "res_.: \\\\[1, 1\\\\]"
Some results adjustment seems to be in order here. I think verifying
that early threading finds the obvious jump threads, then vrp is able to
eliminate the 2nd conditional and the result is a collapsed return i for
the entire function.
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
You're the best judge on how to deal with these. I leave that to your
discretion.
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.
Your call on this. One of the things in the related literature is a
limiter on how far back the use-def chains we go. I'd envisioned adding
that limiter and having early jump threading use a different (much
smaller) limiter. But I don't think it's critical at this point.
Bootstrapped/regtested x86_64-linux
Honza
* passes.def (pass_early_thread_jumps): Schedule after forwprop.
* tree-pass.h (make_pass_early_thread_jumps): Declare.
* tree-ssa-threadbackward.c (fsm_find_thread_path,
fsm_find_thread_path, profitable_jump_thread_path,
fsm_find_control_statement_thread_paths,
find_jump_threads_backwards): Add speed_p parameter.
(pass_data_early_thread_jumps): New pass.
(make_pass_early_thread_jumps): New function.
LGTM. OK after fixing up the tests.
Jeff
