Implement BMI1 and BMI2 intrinsics

[tannergooding]

Pending BMI1:

• AndNot
• BitFieldExtract
• ExtractLowestSetBit
• GetMaskUptoLowestSetBit
• ResetLowestSetBit
• TrailingZeroCount

Pending BMI2:

• MultiplyNoFlags
• ParallelBitDeposit
• ParallelBitExtract
• ZeroHighBits

[tannergooding]

Logged issue and self-assigned. I have most of this done locally.

[tannergooding]

Some of the type parameters for BitFieldExtract should be changed. Specifically, start and length should both be bytes.

GetMaskUptoLowestSetBit should be renamed to correct the casing.

[tannergooding]

FYI. @eerhardt, @fiigii, @CarolEidt

[mikedn]

AndNot is pointless as intrinsics, it should be easy to generate automatically. And MultiplyNoFlags is probably pointless since "no flags" is not something that has meaning in C#.

[GrabYourPitchforks]

pext and pdep in particular would be useful for the UTF-8 processing work we're doing.

[tannergooding]

MultiplyNoFlags is probably pointless since "no flags" is not something that has meaning in C#

C# does not, but other intrinsics do and mulx is useful in a number of scenarios involving things like BigInt (it would be even more useful if we directly exposed the AddWithCarry intrinsics).

AndNot is pointless as intrinsics, it should be easy to generate automatically.

Potentially, although I think it would be good to expose anyways. At the very least, it will help in porting existing algorithms that use it. It can also be used in lowering if the JIT more generally recognizes the AndNot pattern.

[voinokin]

My 5c
ANDN can be used for branchless select operation in absence of CMOV with the following sequence:

• eval cc
• SETcc sel + zero-extend
• NEG sel
• AND r1, sel
• ANDN r2, sel
• OR r1, r2
  Not the fastest solution, still saves 1 NOT op and potentially 1 reg wrt to just ANDs

This can be expanded to branchless min and max

[fiigii]

Specifically, start and length should both be bytes.

@tannergooding Thank you for the work. Could you elaborate on this?

[tannergooding]

@fiigii, those values (start and length) are combined and encoded in operand 3 (VEX.vvvv) of the instruction.

Bit 7:0 of the second source operand specifies the starting bit position of bit extraction. A START value exceeding the operand size will not extract any bits from the second source operand. Bit 15:8 of the second source operand specifies the maximum number of bits (LENGTH) beginning at the START position to extract.

BEXTR r32a, r/m32, r32b

[fiigii]

Yes, but these arguments will be promoted to 32bit in the runtime even if they are byte.

[tannergooding]

Yes, but these arguments will be promoted to 32bit in the runtime even if they are byte.

They are currently set to uint for the 32-bit overloads and ulong for the 64-bit overloads. At the very least, they should be uint on both overloads.

I had suggested changing to byte, as that better represents the actual value range and how we have encoded similar operands on other instrinsic methods.

[fiigii]

Agree, thanks for the explanation.

[tannergooding]

This is mostly just waiting on the API fixes to flow back from CoreFX so that I can finish validating the implementation with tests.

[tannergooding]

@GrabYourPitchforks, the PR implementing pdep and pext is up here: dotnet/coreclr#18785

It will probably be sometime next week before it is actually merged, due to the Jenkins outages.