API Proposal: ShiftLeft, ShiftRight for Vector<T>

[mjmckp]

Updated Proposal

#20510 (comment)

---

Original Proposal

This is a proposal of the ideas discussed in issue #20147.

There are a few SIMD operations on System.Numerics.Vector<T> missing that are required to implement vectorized versions of log, exp, sin, and cos.

There is a C implementation of these methods using AVX intrinsics here, which I have translated into a C# implemention using Vector<T> here. In the implementation, I have added fake versions of the missing intrinsics.

@mellinoe suggested creating two separate issues for the missing methods (the other issue is #20509), so the purpose of this issue is to propose the addition of the following methods:

public static Vector<short> ShiftLeft(Vector<short> x, int n)
public static Vector<int> ShiftLeft(Vector<int> x, int n)
public static Vector<long> ShiftLeft(Vector<long> x, int n)
public static Vector<short> ShiftRight(Vector<short> x, int n)
public static Vector<int> ShiftRight(Vector<int> x, int n)
public static Vector<long> ShiftRight(Vector<long> x, int n)

which map directly to the following AVX2 intrinsics:

_mm256_slli_epi16
_mm256_slli_epi32
_mm256_slli_epi64
_mm256_srli_epi16
_mm256_srli_epi32
_mm256_srli_epi64

respectively.

[mellinoe]

@CarolEidt @sivarv

The main conceptual problem with these methods is that, at least if our past investigations are valid, it is not feasible for the JIT to produce good SIMD instructions for these in all cases, because the second parameter is not necessarily a constant. It can do so if the methods are called with a constant parameter, but this cannot be guaranteed in C#. There is a "pit of failure" so to speak, where the performance of the method drops off a cliff if used improperly. For example, consider the following:

result = ShiftLeft(v, 5); // Constant parameter
result = ShiftLeft(v, this.Settings.ShiftAmount); // Parameter from an indirect value

The second call cannot be properly optimized because this.Settings.ShiftAmount is not a compile-time constant. The first call CAN be, because 5 is a compile-time constant. There is no way to enforce or communicate that the second usage is degenerate / invalid and will be many times slower than the first usage.

The most obvious workaround for this: bake specific constants into the method signature, e.g. force them to be a part of the compile-time signature:

public static Vector<T> ShiftLeftOne(Vector<T> v);
public static Vector<T> ShiftLeftTwo(Vector<T> v);
public static Vector<T> ShiftLeftThree(Vector<T> v);
public static Vector<T> ShiftLeftFour(Vector<T> v);
...

[sivarv]

CC @russellhadley

[jackmott]

What about use of an enum?

enum ShiftAmount : byte/int { One = 1, Two, Three, ... };
public static Vector<T> ShiftLeft(Vector<T> v, ShiftAmount a);

// called like:

var result = ShiftLeft(v,ShiftAmount.One);
var result = ShiftLeft(v,ShiftAmount.Two);
var result = ShiftLeft(v,ShiftAmount.Three);

[mellinoe]

The problem is that the value cannot be guaranteed to be a compile-time constant. There is no way to guarantee that in C#, except to make the constant a part of the method signature (i.e. the name of the method). Enums don't help in that regard.

[jackmott]

Of course, sorry. So the C# compiler seems to have the facility to identify if something is a compile time constant or not, as evidenced by error messages on optional parameters on functions.

Are there any other motivations for semantics to constrain an input parameter to be a compile time constant? Or would that definitely be a no-go?

[svick]

Could including a Roslyn analyzer in the NuGet package be a solution?

That way, if you write ShiftLeft(v, notAConstant) in C# or VB, you get a warning in VS.

Caveats:

• Not sure what would happen in e.g. VS Code or dotnet build, but those could probably be improved to support analyzers, if they don't already.
• The warning won't show up in other languages, like F#.

[jackmott]

Is NEON the only architecture where this needs to be a constant?

[mjmckp]

Out of interest: Why doesn't the JIT support immediate operands?

[mellinoe]

@svick Including a Roslyn analyzer is a potential option -- it's the only one we've thought of that could help here, TBH.

@jackmott I'm not very familiar with NEON. The discussion above certainly applies to SSE/AVX instruction families.

@mjmckp It's not that the JIT "doesn't support immediate operands". The problem is that, when writing C# code, there is no way to enforce that you call a function with an immediate operand; that just isn't a concept available in the language or type system. When the JIT encounters such a call, every option at that point is sub-optimal. The JIT could either:

• Generate an exception telling you that you messed up (not a good experience).
• Generate a very slow version of the "intrinsic".

Like I said above, I think the Roslyn analyzer is the best option that we've thought of. We have never shipped such an analyzer with a BCL package, though, so I'm not sure exactly what it would look like.

[mjmckp]

@mellinoe I guess what I meant was: Why can't the JIT look at each invocation of the method, and either 1) generate a fixed instruction which contains the immediate operand when the argument is a literal value, or, 2) generate a dynamic instruction which contains the runtime value of the argument? I'm sure there's a perfectly good reason why it can't, I'm just curious!

[mellinoe]

@mjmckp It should be able to, but the "dynamic instruction" version will be many times slower, in theory. If we hit that path, we've essentially "failed" to give you an intrinsic operation. We'd like to design something where it is obvious when you make that mistake, and how to easily fix it.

[4creators]

I think there is a solution to that problem - code has to talk to compiler (Jit):

[AttributeUsage(AttributeTargets.Parameter)]
internal class JitIntrinsicParamAttribute : Attribute 
{
    public JitIntrinsicParamAttribute(ParamType type) { Type = type; }
    public IntrinsicParamType Type { get; private set; }    
}

internal enum IntrinsicParamType 
{ 
    Unknown,
    Immediate 
}

public static Vector<T> ShiftLeft(Vector<T> x, [JitIntrinsicParam(IntrinsicParamType.Immediate)] int n);

but on the other end compiler has to listen and should understand above code - without Jit changes implementation would be very difficult.

Encountering above attribute compiler should implement rewriting transform which would ensure that shift operation receives argument as an immediate value disregard of what we pass to method invocation.

The above pattern can be further generalized to include other difficult to implement corner cases.

[mellinoe]

@4creators You can still pass a non-constant value to that method. The problem isn't that the JIT can't detect this case (it can), but that there is no way to gracefully recover at that point. Ideally, your code would not compile if you passed a non-constant parameter to the function, but C#/IL does not allow that in any way.

[svick]

I think using an attribute is a good idea. I would mean that:

• Future versions of compilers (including compilers for languages that don't support Roslyn analyzers) could detect the attribute and produce the error themselves.
• The analyzer wouldn't have to change whenever a new method with immediate parameters is added, since it could detect the attribute.

Though, what would happen if the compiler and the analyzer produced the same error? Is there some way to avoid producing two errors in that case?

[4creators]

@mellinoe My proposal essentially allows for non-constant values to be passed to intrinsic method which uses processor instruction requiring immediate operand.

Intel definition of one of the shift intrinsics is as follows:

_mm256_slli_epi16/32/64
Logical shift of word/doubleword/quadword elements to left according to specified number. 
The corresponding Intel® AVX2 instruction is VPSLLW, VPSLLD, or VPSLLQ*.

VPSLLW 128 bit Intel instruction definition is as follows:

VPSLLW xmm1, xmm2, xmm3/m128 -> Shift words in xmm2 left by amount specified in xmm3/m128 while shifting in 0s.
VPSLLW xmm1, xmm2, imm8 -> Shift words in xmm2 left by imm8 while shifting in 0s.

VPSLLW 256 bit instruction definition is as follows:

VPSLLW ymm1, ymm2, xmm3/m128 -> Shift words in ymm2 left by amount specified in xmm3/m128 while shifting in 0s.
VPSLLW ymm1, ymm2, imm8 -> Shift words in ymm2 left by imm8 while shifting in 0s.

Using above information one can notice that shift instructions accept not only imm8 operand which has to be a compile time constant as it can be a value of the xmm register which is passed as operand to one of the forms of VPSLLW or m128 memory location.

Going further the only significant gurantee which Jit compiler has to provide is that register stores value of parameter and not it's address. In my opinion (however I do not know RyuJit internals good enough to be any authority on that) it does allow to pass a non-constant value to that instruction and the compiler (RyuJit) must ensure during all compilation passes and in particular during register allocation, instruction selection and instruction scheduling that passed value is stored in appropriate register.

What is even more important based on available VPSLL*, VPSRL* we can add additional Vector<T> shift functions overloads and operators as follows:

public static Vector<T> ShiftLeft(Vector<T> x, Vector<U> n);
public static Vector<T> ShiftRight(Vector<T> x, Vector<U> n);
public static operator Vector<T> <<(Vector<T> x, int n);
public static operator Vector<T> <<(Vector<T> x, Vector<U> n);
public static operator Vector<T> >>(Vector<T> x, int n);
public static operator Vector<T> >>(Vector<T> x, Vector<U> n);
public static operator Vector<T> <<=(Vector<T> x, int n);
public static operator Vector<T> <<=(Vector<T> x, Vector<U> n);
public static operator Vector<T> >>=(Vector<T> x, int n);
public static operator Vector<T> >>=(Vector<T> x, Vector<U> n);

@svick I agree that attributes could be used during Roslyn compilation and by Roslyn analyzers but due to flexibility which we have on processor instruction level at least with x86 ISA this would not be required.