Investigation into further opportunities for mulshift optimization in RyuJIT across jit-diff inputs

Mulshift.md

Mulshift Opportunities

These are the results of running RyuJIT over the jit-diff input set with instrumentation in place to quantify the opportunities for rewriting multiplication by constants to shift+lea seqeunces.

Morph

The code in fgMorphSmpOp where the transformation is currently performed was instrumented to report what constants were identified in multiplications. The following tables shows the results over various input sets.

Input: --frameworks --tests

Constants	Occurrences	Proportion	Handled Already
(all)	556799	100.00%	-
4	120203	21.59%	yes
8	74259	13.34%	yes
2	31249	5.61%	yes
1	23871	4.29%	-
3	10106	1.82%	yes
5	8876	1.59%	yes
6	8697	1.56%	yes
7	8067	1.45%	no
10	7477	1.34%	yes
16	7383	1.33%	yes
9	7103	1.28%	yes
12	6920	1.24%	yes
11	6706	1.20%	no
13	6345	1.14%	no
14	6218	1.12%	no
15	6107	1.10%	no
24	5956	1.07%	yes
17	5692	1.02%	no
18	5547	1.00%	yes

(table truncated at last row with >= 1% proportion)

This shows that morph is already transforming 60% of the constants it sees on this input set. Note that the other constants would require longer sequences and so not see as much benefit.

Input: --frameworks

Constants	Occurrences	Proportion	Handled Already
(all)	15144	100.00%	-
8	5513	36.40%	yes
2	3143	20.75%	yes
4	2137	14.11%	yes
16	1369	9.04%	yes
24	1207	7.97%	yes
32	414	2.73%	yes
3	285	1.88%	yes
40	160	1.06%	yes
28	126	0.83%	no
10	103	0.68%	yes
72	99	0.65%	yes
5	82	0.54%	yes
12	71	0.47%	yes
-1521134295	63	0.42%	no
100	31	0.20%	no
8.64E+11	27	0.18%	no
7	24	0.16%	no
20	22	0.15%	yes
9	21	0.14%	yes
16777619	21	0.14%	no
400	17	0.11%	no
10000	17	0.11%	no
60	15	0.10%	no

(table truncated at last row with >= 0.1% proportion)

This shows that morph is already transforming 96% of the constants it sees on this input set.

Input: tests under JIT/Performance/CodeQuality

Constants	Occurrences	Proportion	Handled Already
(all)	1872	100.00%	-
8	1039	55.50%	yes
4	444	23.72%	yes
2	246	13.14%	yes
20	30	1.60%	yes
16	25	1.34%	yes
5	16	0.85%	yes
3	10	0.53%	yes
12	10	0.53%	yes
50000	6	0.32%	no
10000	4	0.21%	no
100000	4	0.21%	no
120	3	0.16%	no
25173	3	0.16%	no
10	2	0.11%	yes
100	2	0.11%	no
110	2	0.11%	no
130	2	0.11%	no
140	2	0.11%	no
3877	2	0.11%	no
139968	2	0.11%	no
254754	2	0.11%	no
529562	2	0.11%	no
999563	2	0.11%	no
5000000	2	0.11%	no
7	1	0.05%	no
50	1	0.05%	no
76	1	0.05%	no
77	1	0.05%	no
96	1	0.05%	no
255	1	0.05%	no
1000	1	0.05%	no
60000	1	0.05%	no
262140	1	0.05%	no
3687091	1	0.05%	no

(table not truncated)

This shows that morph is already transforming 97% of the constants it sees on this input set.

Conclusion

Morph is already capitilizing on the vast majority of opporunities it sees, especially in frameworks and benchmarks code.

CodeGen

The code in genCodeForMul where the transformation to lea is performed (just for 3, 5, and 9) was instrumented to report what constants were identified in multiplications. This would show if mulshift-able constants were (re-)appearing after morph. The following tables shows the results over various input sets.

Input: --frameworks --tests

Constants	Occurrences	Proportion	Handled Already	Power of 2
(all)	8496	100.00%	-	-
16	2774	32.65%		yes
3	1537	18.09%	yes
100	883	10.39%
5	528	6.21%	yes
56	450	5.30%
48	410	4.83%
-1521134295	329	3.87%
12	188	2.21%
32	141	1.66%		yes
2	113	1.33%
24	108	1.27%
7	88	1.04%
26	84	0.99%
52	72	0.85%
16777619	64	0.75%
28	56	0.66%
10000000	52	0.61%
120	47	0.55%
9	42	0.49%	yes
19	29	0.34%
4	28	0.33%		yes
17	26	0.31%
8	23	0.27%		yes

(table truncated for brevity)

This input set shows a clear missed opportunity to represent multiply-by-16 as shift-by-4.

Input: --frameworks

Constants	Occurrences	Proportion	Handled Already	Power of 2
(all)	1411	100.00%	-	-
3	722	51.17%	yes
5	217	15.38%	yes
-1521134295	61	4.32%
28	56	3.97%
9	39	2.76%	yes
2	31	2.20%		yes
100	30	2.13%
7	24	1.70%
16777619	21	1.49%
400	17	1.20%
10000	16	1.13%
60	15	1.06%
96	13	0.92%
19	11	0.78%
10000000	9	0.64%
48	8	0.57%
56	8	0.57%
88	8	0.57%
126	8	0.57%
365	8	0.57%
14	6	0.43%
101	6	0.43%
3600	6	0.43%
8	5	0.35%		yes

(table truncated for brevity)

This input set shows no interesting opportunities.

Input: tests under JIT/Performance/CodeQuality

Constants	Occurrences	Proportion	Handled Already	Power of 2
(all)	85	100.00%	-	-
5	26	30.59%	yes
3	9	10.59%	yes
50000	9	10.59%
100000	4	4.71%
100	3	3.53%
120	3	3.53%
1000	3	3.53%
10000	3	3.53%
25173	3	3.53%
3877	2	2.35%
60000	2	2.35%
139968	2	2.35%
5000000	2	2.35%
10	1	1.18%
50	1	1.18%
76	1	1.18%
77	1	1.18%
96	1	1.18%
110	1	1.18%
130	1	1.18%
140	1	1.18%
255	1	1.18%
254754	1	1.18%
262140	1	1.18%
529562	1	1.18%
999563	1	1.18%
3687091	1	1.18%

(table not truncated)

This input set shows no interesting opportunities.

Conclusion

Given how cheap it would be, we may as well identify powers of two at this late stage to ensure they won't appear in generated machine code, but the opportunities are not rampant (aside from the 32% of constants in the full input set being 16).