Poor register allocation with hardware intrinsic (x86)

[ebfortin]

Description

I'm porting an algorithm from scalar double arithmetics to SIMD using the Hardware Intrinsics. After some testing I concluded that the performance of the SIMD version is worst. Now it can be that I'm just not good at using SIMD instructions. However looking at the asm produced by the JIT, I think there may be a problem.

Configuration

.NET Core 5.0.0 (CoreCLR 5.0.20.21406, CoreFX 5.0.20.21406), X64 RyuJIT

Regression?

Data

Look at one example:

                 var v02 = Avx.HorizontalAdd(v00, v01); // r = (xh + yh) | - xl - yl)
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 00007ffc`ca6fdca4 c5f9284dd0      vmovapd xmm1,xmmword ptr [rbp-30h]
 00007ffc`ca6fdca9 c5f17c4dc0      vhaddpd xmm1,xmm1,xmmword ptr [rbp-40h]
 00007ffc`ca6fdcae c5f9294db0      vmovapd xmmword ptr [rbp-50h],xmm1
                 var v03 = Avx.Subtract(v00, v02);
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 00007ffc`ca6fdcb3 c5f9284dd0      vmovapd xmm1,xmmword ptr [rbp-30h]
 00007ffc`ca6fdcb8 c5f15c4db0      vsubpd  xmm1,xmm1,xmmword ptr [rbp-50h]
 00007ffc`ca6fdcbd c5f9294da0      vmovapd xmmword ptr [rbp-60h],xmm1

This comes from the disassembly of BenchmarkDotet.

Also benchmark results:

Method	EnvironmentVariables	Mean	Error	StdDev	Median	Max
AdditionDouble	COMPlus_EnableHWIntrinsic=0	1.112 ns	0.0658 ns	0.1187 ns	1.100 ns	1.400 ns
AdditionDouble2	COMPlus_EnableHWIntrinsic=0	104.808 ns	2.8832 ns	6.0183 ns	102.300 ns	124.500 ns
AdditionDouble	COMPlus_EnableHWIntrinsic=1	1.065 ns	0.0645 ns	0.0985 ns	1.100 ns	1.200 ns
AdditionDouble2	COMPlus_EnableHWIntrinsic=1	196.530 ns	9.3874 ns	26.4772 ns	178.950 ns	268.100 ns

Analysis

If you look closely you see that each instruction seem to be taken in isolation, with its own register allocation, instead of being global to the method. This means a LOT more memory load/store than seem necessary. There is a lot of register to play with beside xmm1...

The documentation on Hardware Intrinsics states that for some time in the compilation tree intrinsics are seen as method. Maybe they are seen as method for a bit too long and so each "method" see some register allocation but only in its own local "method" context.

category:cq
theme:register-allocator
skill-level:expert
cost:medium

[AndyAyersMS]

@ebfortin the disassembly above looks like it is from un-optimized code. Usually BenchmarkDotNet is pretty good at ensuring that it benchmarks only optimized code, but in this case I wonder.

Can you share your test case, or some representative sample?

[AndyAyersMS]

Going to mark this as future, may reconsider once we have more information.

[ebfortin]

I will provide some more details later tonight. I'll put the method code being evaluated. The benchmark configuration used and other stuff.

[ebfortin]

Code from BenchmarkDotnet to define the benchmarks.

        [IterationSetup]
        public void Setup()
		{
            _a = _rnd.NextDouble();
            _b = _rnd.NextDouble();

            _a2 = new Double2(_a);
            _b2 = new Double2(_b);
		}

        [Benchmark]
        public double AdditionDouble()
        {
            var c = _a + _b;
            return c;
        }

        [Benchmark]
        public Double2 AdditionDouble2()
        {
            var c = _a2 + _b2;
            return c;
        }

Configuration for the benchmark.

    public class BenchmarkConfig : ManualConfig
    {
        private const string JitNoInline = "COMPlus_JitNoInline";
        private const string JitHardwareIntrinsics = "COMPlus_EnableHWIntrinsic";

        public BenchmarkConfig()
        {
            // Configure your benchmarks, see for more details: https://benchmarkdotnet.org/articles/configs/configs.html.
            //Add(Job.Dry);
            Add(ConsoleLogger.Default);
            Add(TargetMethodColumn.Method, StatisticColumn.Max);
            //Add(RPlotExporter.Default, CsvExporter.Default);
            Add(EnvironmentAnalyser.Default);

            
            Add(
                Job.Default.With(CoreRuntime.Core50)
                .WithId("CoreRT")
                );

            Add(
                Job.RyuJitX64
                .With(new EnvironmentVariable(JitHardwareIntrinsics, "1"))
                .WithId("RyunJITX64 : Intrinsics ENABLED")
                );

            Add(
                Job.RyuJitX64
                .With(new EnvironmentVariable(JitHardwareIntrinsics, "0"))
                .WithId("RyunJITX64 : Intrinsics DISABLED")
                );

        }
    }

Code of operator+() called from the Benchmark.

        private static (double, double) Add22(double xh, double xl, double yh, double yl)
		{
            double zh;
            double zl;

            if(Avx2.IsSupported)
			{
                var v00 = Vector128.Create(xh, yh);
                var v01 = Vector128.Create(-xl, -yl);
                var v02 = Avx.HorizontalAdd(v00, v01); // r = (xh + yh) | - xl - yl)
                var v03 = Avx.Subtract(v00, v02);
                var v05 = Avx.HorizontalAdd(v03, Vector128<double>.Zero); // s = xh - r + yh + xl + yl | 0
                var v06 = Avx.Add(v02, v05); // r + s | - xl - yl
                var v08 = Avx.Add(Avx.Subtract(v02, v06), v05);

                zh = v06.GetElement(0);
                zl = v08.GetElement(0);

                return (zh, zl);
			}

            double r, s;

            r = xh + yh;
            s = xh - r + yh + yl + xl;
            zh = r + s;
            zl = r - zh + s;

            return (zh, zl);
        }

        public static Double2 operator +(Double2 a, Double2 b)
		{
            var r = Add22(a.h, a.l, b.h, b.l);
            return new Double2(r);
        }

From BenchmarkDotnet run showing that no debugger is attached.

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.19635
Intel Core i5-7300HQ CPU 2.50GHz (Kaby Lake), 1 CPU, 4 logical and 4 physical cores
.NET Core SDK=5.0.100-preview.3.20216.6
  [Host]     : .NET Core 5.0.0 (CoreCLR 5.0.20.21406, CoreFX 5.0.20.21406), X64 RyuJIT
  Job-IDRGDI : .NET Core 5.0.0 (CoreCLR 5.0.20.21406, CoreFX 5.0.20.21406), X64 RyuJIT
  Job-YDAAYA : .NET Core 5.0.0 (CoreCLR 5.0.20.21406, CoreFX 5.0.20.21406), X64 RyuJIT
  Job-TWHNGR : .NET Core 5.0.0 (CoreCLR 5.0.20.21406, CoreFX 5.0.20.21406), X64 RyuJIT

[EgorBo]

Add22 looks pretty good to me:

G_M12720_IG01:
       vzeroupper 
						;; bbWeight=1    PerfScore 1.00

G_M12720_IG02:
       vmovsd   xmm0, qword ptr [reloc @RWD00]
       vxorps   xmm0, xmm2
       vmovsd   xmm4, qword ptr [rsp+28H]
       vmovsd   xmm2, qword ptr [reloc @RWD00]
       vxorps   xmm2, xmm4
       vmovlhps xmm0, xmm0, xmm2
       vmovlhps xmm1, xmm1, xmm3
       vhaddpd  xmm0, xmm1, xmm0
       vsubpd   xmm1, xmm1, xmm0
       vxorps   xmm2, xmm2, xmm2
       vhaddpd  xmm1, xmm1, xmm2
       vaddpd   xmm2, xmm0, xmm1
       vmovaps  xmm3, xmm2  ;; <-- ?
       vsubpd   xmm0, xmm0, xmm2
       vaddpd   xmm0, xmm0, xmm1
       vmovsd   qword ptr [rcx], xmm3
       vmovsd   qword ptr [rcx+8], xmm0
       mov      rax, rcx
G_M12720_IG03:
       ret      
RWD00  dq	8000000000000000h
; Total bytes of code: 86

The only thing it seems is this repro:

static Vector128<double> Add22(double a, double b)
{
    return Vector128.Create(-a, -b);
}

Codegen:

G_M46873_IG01:
       vzeroupper 
G_M46873_IG02:
       vmovsd   xmm0, qword ptr [reloc @RWD00]
       vxorps   xmm0, xmm1
       vmovsd   xmm1, qword ptr [reloc @RWD00]
       vxorps   xmm1, xmm2
       vmovlhps xmm0, xmm0, xmm1
       vmovupd  xmmword ptr [rcx], xmm0
       mov      rax, rcx
G_M46873_IG03:
       ret      
RWD00  dq	8000000000000000h
; Total bytes of code: 39

it loads 0 twice to perform negations (I am not even mentioning it could do negation only once on top of result)

cc @tannergooding

[EgorBo]

I wonder if we can expand GT_NEG to 0 - x so VN/CSE can pick 0 up (and then optimize to GT_NEG back in lowering if necessary)

[tannergooding]

The loading 0 twice is basically the same as: #37079.

Horizontal Adds aren't necessarily the most performance instructions and it might be better to rearrange the data so you can use normal addition/subtraction instead. It looks like it might be possible at first glance, but I didn't confirm...

Constructing and deconstructing the vector also has some minimal overhead that wouldn't be great in a loop.

[ebfortin]

Add22 looks pretty good to me:

G_M12720_IG01:
       vzeroupper 
						;; bbWeight=1    PerfScore 1.00

G_M12720_IG02:
       vmovsd   xmm0, qword ptr [reloc @RWD00]
       vxorps   xmm0, xmm2
       vmovsd   xmm4, qword ptr [rsp+28H]
       vmovsd   xmm2, qword ptr [reloc @RWD00]
       vxorps   xmm2, xmm4
       vmovlhps xmm0, xmm0, xmm2
       vmovlhps xmm1, xmm1, xmm3
       vhaddpd  xmm0, xmm1, xmm0
       vsubpd   xmm1, xmm1, xmm0
       vxorps   xmm2, xmm2, xmm2
       vhaddpd  xmm1, xmm1, xmm2
       vaddpd   xmm2, xmm0, xmm1
       vmovaps  xmm3, xmm2  ;; <-- ?
       vsubpd   xmm0, xmm0, xmm2
       vaddpd   xmm0, xmm0, xmm1
       vmovsd   qword ptr [rcx], xmm3
       vmovsd   qword ptr [rcx+8], xmm0
       mov      rax, rcx
G_M12720_IG03:
       ret      
RWD00  dq	8000000000000000h
; Total bytes of code: 86

The only thing it seems is this repro:

static Vector128<double> Add22(double a, double b)
{
    return Vector128.Create(-a, -b);
}

Codegen:

G_M46873_IG01:
       vzeroupper 
G_M46873_IG02:
       vmovsd   xmm0, qword ptr [reloc @RWD00]
       vxorps   xmm0, xmm1
       vmovsd   xmm1, qword ptr [reloc @RWD00]
       vxorps   xmm1, xmm2
       vmovlhps xmm0, xmm0, xmm1
       vmovupd  xmmword ptr [rcx], xmm0
       mov      rax, rcx
G_M46873_IG03:
       ret      
RWD00  dq	8000000000000000h
; Total bytes of code: 39

it loads 0 twice to perform negations (I am not even mentioning it could do negation only once on top of result)

cc @tannergooding

And where is this diassembly coming from? Why would un-optimized code be used by BenchmarkDotnet? Because the code that is produced on my side has basically one load before, and one store after any SIMD instruction. And the lower performance comes from there, not in the choice of SIMD instruction. Also what are the condition in the JIT to emit optimized code? Because I see a problem if on some computer it's optimized, on other it's not. It's too variable.

[ebfortin]

I tested it with COMPlus_TC_QuickJit set to 0. A HUGE difference. So indeed the code was not optimized. Which is demonstrated with the output from BenchmarkDotnet diassembler below:

                var v02 = Avx.HorizontalAdd(v00, v01); // r = (xh + yh) | - xl - yl)
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
00007ffa`89ca7d99 c5f97cc9        vhaddpd xmm1,xmm0,xmm1
                var v03 = Avx.Subtract(v00, v02);
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
00007ffa`89ca7d9d c5f95cc1        vsubpd  xmm0,xmm0,xmm1
                var v05 = Avx.HorizontalAdd(v03, Vector128.Zero); // s = xh - r + yh + xl + yl | 0
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
00007ffa`89ca7da1 c5e857d2        vxorps  xmm2,xmm2,xmm2
00007ffa`89ca7da5 c5f97cc2        vhaddpd xmm0,xmm0,xmm2

And if I look at the benchmark, I see that my SIMD code is bad and need improvement, like what @tannergooding was suggesting. Now that the un-optimized variable is out of the way.

However it raises the question : Why wouldn't the Tiered compilation kicks in for this workload? Method being evaluated is too small? Run time is too low?

And a side question : What is AgressiveOptimization doing? Does it affect only C# compilation? Any effect on the JIT? Would be great to have the ability to force optimization, in the JIT, on a per method basis. Would make it possible to ship librairies with critical methods that are sure to get optimized right away. And letting the JIT decide for the others.

[AndyAyersMS]

@adamsitnik any idea why BenchmarkDotNet can't get to Tier1 code in the test case above?

What is AgressiveOptimization doing?

AggressiveOptimization will indeed bypass Tier0 and generate Tier1 code the first time a method is jitted. But it shouldn't be needed in most cases.