RFR: 8346964: C2: Improve integer multiplication with constant in MulINode::Ideal()

[Jasmine Karthikeyan]

On Mon, 6 Jan 2025 07:55:39 GMT, erifan <duke at openjdk.org> wrote:

> Constant multiplication x*C can be optimized as LEFT SHIFT, ADD or SUB instructions since generally these instructions have smaller latency and larger throughput on most architectures. For example:
> 1. x*8 can be optimized as x<<3.
> 2. x*9 can be optimized as x+x<<3, and x+x<<3 can be lowered as one SHIFT-ADD (ADD instruction combined with LEFT SHIFT) instruction on some architectures, like aarch64 and x86_64.
> 
> Currently OpenJDK implemented a few such patterns in mid-end, including:
> 1. |C| = 1<<n                (n>0)
> 2. |C| = (1<<n) - 1          (n>0)
> 3. |C| = (1<<m) + (1<<n)     (m>n, n>=0)
> 
> The first two are ok. Because on most architectures they are lowered as only one ADD/SUB/SHIFT instruction.
> 
> But the third pattern doesn't always perform well on some architectures, such as aarch64. The third pattern can be split as the following sub patterns:
> 3.1. C = (1<<n) + 1          (n>0)
> 3.2. C = -((1<<n) + 1)       (n>0)
> 3.3. C = (1<<m) + (1<<n)     (m>n, n>0)
> 3.4. C = -((1<<m) + (1<<n))  (m>n, n>0)
> 
> According to Arm optimization guide, if the shift amount > 4, the latency and throughput of ADD instruction is the same with MUL instruction. So in this case, converting MUL to ADD is not profitable. Take a[i] * C on aarch64 as an example.
> 
> Before (MUL is not converted):
> 
>   mov x1, #C
>   mul x2, x1, x0
> 
> 
> Now (MUL is converted):
>   For 3.1:
> 
>     add x2, x0, x0, lsl #n
> 
> 
>   For 3.2:
> 
>     add x2, x0, x0, lsl #n  // same cost with mul if n > 4
>     neg x2, x2
> 
> 
>   For 3.3:
> 
>     lsl x1, x0, #m
>     add x2, x1, x0, lsl #n  // same cost with mul if n > 4
> 
> 
>   For 3.4:
> 
>     lsl x1, x0, #m
>     add x2, x1, x0, lsl #n  // same cost with mul if n > 4
>     neg x2, x2
> 
> 
> Test results (ns/op) on Arm Neoverse V2:
> 
> 		Before	Now	Uplift		Pattern	Notes
> testInt9	103.379	60.702	1.70305756	3.1
> testIntN33	103.231	106.825	0.96635619	3.2	n > 4
> testIntN9	103.448	103.005	1.004300762	3.2	n <= 4
> testInt18	103.354	99.271	1.041129837	3.3	m <= 4, n <= 4
> testInt36	103.396	99.186	1.042445506	3.3	m > 4, n <= 4
> testInt96	103.337	105.416	0.980278136	3.3	m > 4, n > 4
> testIntN18	103.333	139.258	0.742025593	3.4	m <= 4, n <= 4
> testIntN36	103.208	139.132	0.741799155	3.4	m > 4, n <= 4
> testIntN96	103.367	139.471	0.74113615	3.4	m > 4, n > 4
> 
> 
> **(S1) From this point on, we should treat pattern 3 as follows:**
> 3.1  C = (1<<n) + 1          (n>0)
> 3.2  C = -((1<<n) + 1)       (0<n<=4)
> 3.3  C = (1<<m) + (1<<n)     (m>n, 0<n<=4)
> 3.4  C = -((1<<m) + (1<<n))  (disable)
> 
> Since this conversion is implemented in mid-end, it impacts...

I also think that moving mul-related idealization to happen after loop opts would be a good idea. In the past I've noticed that patterns such as `x * 4 * 4` do not properly fold into a single multiply, because the mul is strength reduced into left shifts before constant folding takes place (shifts aren't currently constant folded either, but I think that is a separate issue). By doing such strength reductions after loop opts we can fix that issue as well.

-------------

PR Comment: https://git.openjdk.org/jdk/pull/22922#issuecomment-2629209771