Enabled DFAJumpThreading by Default

[Yangguang]

Summary

I measured the compile time impact for the DFAJumpThreading pass and did functional test on SPEC2017.
As the result shown below, there is almost no impact in compile time. And the SPEC2017 benchmark suit
can be successfully compiled with several DFAJumpThreading transforms being applied to some of the
benchmarks. So I suggest that we enable DFAJumpThreading by Default.

Compile time test:

	DFA false	DFA true	Change (off-on)/off
MultiSourc...Benchmarks/7zip/7zip-benchmark	82.02	82.73	-0.87%
MultiSourc...nchmarks/tramp3d-v4/tramp3d-v4	39.14	39.14	0.00%
MultiSourc.../DOE-ProxyApps-C++/CLAMR/CLAMR	37.25	37.44	-0.51%
MultiSource/Benchmarks/Bullet/bullet	36.88	36.73	0.41%
MultiSourc.../Applications/JM/lencod/lencod	25.89	25.84	0.19%
MultiSourc...e/Applications/ClamAV/clamscan	20.57	20.42	0.73%
MultiSource/Applications/SPASS/SPASS	18.17	18.22	-0.28%
MultiSource/Applications/kimwitu++/kc	18.02	18.00	0.11%
MultiSourc...e/Applications/sqlite3/sqlite3	16.65	16.78	-0.78%
MultiSourc...enchmarks/mafft/pairlocalalign	14.59	14.54	0.34%
MultiSourc...sumer-typeset/consumer-typeset	13.58	13.68	-0.74%
MultiSourc...-ProxyApps-C++/PENNANT/PENNANT	11.70	11.84	-1.20%
MultiSourc.../Applications/JM/ldecod/ldecod	10.59	10.52	0.66%
SingleSour...nchmarks/Adobe-C++/loop_unroll	9.49	9.57	-0.84%
MicroBench...CALS/SubsetCRawLoops/lcalsCRaw	9.20	9.17	0.33%

Number of DFAJumpThreading transforms in compile time test:

"test-suite :: MultiSource/Applications/lua/lua.test" : "dfa-jump-threading.NumTransforms": 1.0, 
"test-suite :: MultiSource/Applications/SPASS/SPASS.test" : "dfa-jump-threading.NumTransforms": 2.0, 
"test-suite :: MultiSource/Benchmarks/7zip/7zip-benchmark.test" : "dfa-jump-threading.NumTransforms": 24.0, 
"test-suite :: MultiSource/Applications/sqlite3/sqlite3.test" : "dfa-jump-threading.NumTransforms": 4.0, 
"test-suite :: MultiSource/Benchmarks/DOE-ProxyApps-C++/CLAMR/CLAMR.test" : "dfa-jump-threading.NumTransforms": 2.0,
"test-suite :: MultiSource/Applications/obsequi/Obsequi.test" : "dfa-jump-threading.NumTransforms": 1.0, 
"test-suite :: MultiSource/Benchmarks/Ptrdist/bc/bc.test" : "dfa-jump-threading.NumTransforms": 1.0, 
"test-suite :: MultiSource/Applications/ClamAV/clamscan.test" : "dfa-jump-threading.NumTransforms": 7.0, 
"test-suite :: MultiSource/Applications/kimwitu++/kc.test" : "dfa-jump-threading.NumTransforms": 2.0, 
"test-suite :: MultiSource/Benchmarks/MiBench/consumer-typeset/consumer-typeset.test" : "dfa-jump-threading.NumTransforms": 4.0, 
"test-suite :: MultiSource/Benchmarks/McCat/01-qbsort/qbsort.test" : "dfa-jump-threading.NumTransforms": 1.0, 
"test-suite :: MultiSource/Benchmarks/MallocBench/gs/gs.test" : "dfa-jump-threading.NumTransforms": 1.0, 
"test-suite :: MultiSource/Benchmarks/MiBench/consumer-jpeg/consuuner-j peg. test" : "dfa-jump-threading.NumTransforms": 1.0, 
"test-suite :: MultiSource/Benchmarks/mediabench/jpeg/jpeg-6a/cjpeg.test" : "dfa-jump-threading.NumTransforms": 1.0,

SPEC2017 function test result:

Benchmark	Compilation	# DFAJumpThreading Transforms
554	Success	0
549	Success	0
544	Success	0
538	Success	2
527	Success	1
526	Success	2
521	Success	1
519	Success	0
511	Success	2
510	Success	4
508	Success	0
507	Success	2
503	Success	0
557	Success	4
548	Success	0
541	Success	0
531	Success	0
525	Success	0
523	Success	7
520	Success	6
505	Success	0
502	Success	3
500	Success	10

[xbolva00]

Yes, we should have pass like this one in the optimization pipelines to achieve better jump threading optimizations (currently llvm is far behind gcc here).

Compile time data are pretty neutral, so probably just go ahead and try to enable it.

[nikic]

Isn't this missing updates for pipeline tests?

Compile-time: https://llvm-compile-time-tracker.com/compare.php?from=387c1573f89117687f4b964ae3a90ea7c91a4f90&to=2a66b841e34f385331226d2b4f89fffd1840cda1&stat=instructions%3Au

This is much more expensive than when I tested this the last time on August 2nd, 2021: https://llvm-compile-time-tracker.com/compare.php?from=380b8a603c6e8997819726b15a76b8f6c94aa21a&to=abb759c879725b7bc09a466e92c9b9eca7f8f483&stat=instructions:u At that time, the pass was pretty cheap, and as such a reasonable tradeoff. Now this doesn't seem to be the case anymore.

I looked through the history of the pass, and this is the only commit that looked like a significant change, so possibly it is at fault: https://github.com/llvm/llvm-project/commit/8b0d7634743965948234b666c77393d4dd8535d7

[xbolva00]

Right, new CT data from compile time tracker looks bad :/

[Yangguang]

Update pipeline tests

[amehsan]

This is much more expensive than when I tested this the last time on August 2nd, 2021: https://llvm-compile-time-tracker.com/compare.php?from=380b8a603c6e8997819726b15a76b8f6c94aa21a&to=abb759c879725b7bc09a466e92c9b9eca7f8f483&stat=instructions:u At that time, the pass was pretty cheap, and as such a reasonable tradeoff. Now this doesn't seem to be the case anymore.

Taking the geomean of compile time change in the above table shows 0.23% increase in compile time. That is not acceptable?

[nikic]

In D140635#4019565, @amehsan wrote:

This is much more expensive than when I tested this the last time on August 2nd, 2021: https://llvm-compile-time-tracker.com/compare.php?from=380b8a603c6e8997819726b15a76b8f6c94aa21a&to=abb759c879725b7bc09a466e92c9b9eca7f8f483&stat=instructions:u At that time, the pass was pretty cheap, and as such a reasonable tradeoff. Now this doesn't seem to be the case anymore.

Taking the geomean of compile time change in the above table shows 0.23% increase in compile time. That is not acceptable?

Not sure how you arrived at that number (isn't it 0.44% geomean across optimized builds?), but no, these regressions are not acceptable for what the pass does, especially if we already know that it can be much faster.

Some of the regressions might be due to second-order effects (i.e. the transform triggers, and this affects compile-time of other transforms), but there are some really large regressions without code size changes, which indicate that the pass itself is slow. For example libclamav_regex_regexec.c has a 16% regression, configfile.c has a 12% regression and header.c has a 17% regression, all without changes in code size.

[Yangguang]

In D140635#4019740, @nikic wrote:

In D140635#4019565, @amehsan wrote:

This is much more expensive than when I tested this the last time on August 2nd, 2021: https://llvm-compile-time-tracker.com/compare.php?from=380b8a603c6e8997819726b15a76b8f6c94aa21a&to=abb759c879725b7bc09a466e92c9b9eca7f8f483&stat=instructions:u At that time, the pass was pretty cheap, and as such a reasonable tradeoff. Now this doesn't seem to be the case anymore.

Taking the geomean of compile time change in the above table shows 0.23% increase in compile time. That is not acceptable?

Not sure how you arrived at that number (isn't it 0.44% geomean across optimized builds?), but no, these regressions are not acceptable for what the pass does, especially if we already know that it can be much faster.

Some of the regressions might be due to second-order effects (i.e. the transform triggers, and this affects compile-time of other transforms), but there are some really large regressions without code size changes, which indicate that the pass itself is slow. For example libclamav_regex_regexec.c has a 16% regression, configfile.c has a 12% regression and header.c has a 17% regression, all without changes in code size.

Thanks for the info! We are now working on the fix for the compile time issue.

llvm/lib/Passes/PassBuilderPipelines.cpp

 static cl::opt<bool>
     EnableDFAJumpThreading("enable-dfa-jump-thread",
                            cl::desc("Enable DFA jump threading"),
-                           cl::init(false), cl::Hidden);
+                           cl::init(true), cl::Hidden);
 
 static cl::opt<bool>
     EnableHotColdSplit("hot-cold-split",

llvm/test/Other/new-pm-defaults.ll

 ; CHECK-O-NEXT: Running analysis: DemandedBitsAnalysis
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-EP-PEEPHOLE-NEXT: Running pass: NoOpFunctionPass
+; CHECK-O2-NEXT: Running pass: DFAJumpThreadingPass
+; CHECK-O3-NEXT: Running pass: DFAJumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running pass: JumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running analysis: LazyValueAnalysis
 ; CHECK-O23SZ-NEXT: Running pass: CorrelatedValuePropagationPass

llvm/test/Other/new-pm-thinlto-defaults.ll

 ; CHECK-O-NEXT: Running pass: BDCEPass
 ; CHECK-O-NEXT: Running analysis: DemandedBitsAnalysis
 ; CHECK-O-NEXT: Running pass: InstCombinePass
+; CHECK-O2-NEXT: Running pass: DFAJumpThreadingPass
+; CHECK-O3-NEXT: Running pass: DFAJumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running pass: JumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running analysis: LazyValueAnalysis
 ; CHECK-O23SZ-NEXT: Running pass: CorrelatedValuePropagationPass

llvm/test/Other/new-pm-thinlto-postlink-pgo-defaults.ll

 ; CHECK-O-NEXT: Running pass: BDCEPass
 ; CHECK-O-NEXT: Running analysis: DemandedBitsAnalysis
 ; CHECK-O-NEXT: Running pass: InstCombinePass
+; CHECK-O2-NEXT: Running pass: DFAJumpThreadingPass
+; CHECK-O3-NEXT: Running pass: DFAJumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running pass: JumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running analysis: LazyValueAnalysis
 ; CHECK-O23SZ-NEXT: Running pass: CorrelatedValuePropagationPass

llvm/test/Other/new-pm-thinlto-postlink-samplepgo-defaults.ll

 ; CHECK-O-NEXT: Running pass: BDCEPass
 ; CHECK-O-NEXT: Running analysis: DemandedBitsAnalysis
 ; CHECK-O-NEXT: Running pass: InstCombinePass
+; CHECK-O2-NEXT: Running pass: DFAJumpThreadingPass
+; CHECK-O3-NEXT: Running pass: DFAJumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running pass: JumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running analysis: LazyValueAnalysis
 ; CHECK-O23SZ-NEXT: Running pass: CorrelatedValuePropagationPass

llvm/test/Other/new-pm-thinlto-prelink-pgo-defaults.ll

 ; CHECK-O-NEXT: Running pass: BDCEPass
 ; CHECK-O-NEXT: Running analysis: DemandedBitsAnalysis
 ; CHECK-O-NEXT: Running pass: InstCombinePass
+; CHECK-O2-NEXT: Running pass: DFAJumpThreadingPass
+; CHECK-O3-NEXT: Running pass: DFAJumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running pass: JumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running analysis: LazyValueAnalysis
 ; CHECK-O23SZ-NEXT: Running pass: CorrelatedValuePropagationPass

llvm/test/Other/new-pm-thinlto-prelink-samplepgo-defaults.ll

 ; CHECK-O-NEXT: Running pass: BDCEPass
 ; CHECK-O-NEXT: Running analysis: DemandedBitsAnalysis
 ; CHECK-O-NEXT: Running pass: InstCombinePass
+; CHECK-O2-NEXT: Running pass: DFAJumpThreadingPass
+; CHECK-O3-NEXT: Running pass: DFAJumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running pass: JumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running analysis: LazyValueAnalysis
 ; CHECK-O23SZ-NEXT: Running pass: CorrelatedValuePropagationPass