Hi everyone,

I'm looking at more optimisations under x86_64 that use the BMI instructions.  I've come across one situation that I need clarity on... how are SHL and SHR instructions handled if the shift value exceeds the word size?

For example, say I have the code "power2 := 1 shl index;"... assuming everything here is a LongWord (32-bit unsigned integer), what happens if index is 32 or higher?  Logic would state that the result should be zero, since all of the bits are essentially shifted out of the register, but under x86, the SHL and SHR instructions effectively do the following:

power2 := 1 shi (index mod 32);

("mod 64" for 64-bit registers)

So in this case, 1 shl 32 will return 1.  This may cause problems with other platforms where the index isn't masked like this, and I've noticed code in the compiler that looks out for this, which is especially important for bitmasks since "(1 shl 32) - 1" won't return $FFFFFFFF as expected, but 0 instead.  There are some problems though because the BZHI instruction, which is otherwise great for producing such masks, doesn't modify the input if the index is equal to or greater than the word size (it does set the carry flag though) and so the equivalent of "(1 shl 32) - 1" will return $FFFFFFFF.

From a cross-platform perspective, how are too-large indices generally handled to ensure consistent cross-platform behaviour? I know ARM and AArch64 also reduces the index modulo the word size, but I don't know if this holds for other platforms.  If one assumes (index mod word_size), it will make any kind of BZHI optimisation a little janky (any kind of optimisation that doesn't account for the case of a too-large index would only be valid under -O4 rules).

Kit

Hi there:

J. Gareth Moreton wrote

[...] I've come across one situation that I need clarity on... how are SHL and SHR instructions handled if the shift value exceeds the word size?

About a half year ago I raised a documentation issue regarding that: https://gitlab.com/freepascal.org/fpc/documentation/-/issues/39304

Bottom line: The behavior is _undefined_. Explanation by Jonas Maebe:

Such behaviour is indeed undefined (it's not implementation-defined because when evaluating at compile time you may get different results compared to when it gets evaluated at run time due to architecture peculiarities).

That's useful - thank you.  Michael Van Canneyt mentioend he updated the documentation for this - where is this usually located? It's not here, for example: https://www.freepascal.org/docs-html/ref/refsu45.html

Kit

J. Gareth Moreton via fpc-devel schrieb am
Mo., 24. Okt. 2022, 13:52:

That's useful - thank you. Michael Van Canneyt mentioend he updated the documentation for this - where is this usually located? It's not here, for example: https://www.freepascal.org/docs-html/ref/refsu45.html

That is for the last released version, in this case 3.2.2. A snapshot of the documentation for the development version is available at https://www.freepascal.org/daily/daily.html, so the one you want is here: https://www.freepascal.org/daily/doc/ref/refsu46.html

Regards,
Sven

The more I learn!

J. Gareth Moreton wrote

That's useful - thank you.  Michael Van Canneyt mentioend he updated the documentation for this - where is this usually located? It's not here, for example: https://www.freepascal.org/docs-html/ref/refsu45.html

Daily documentation:

https://www.freepascal.org/daily/daily.html

In particular:

https://www.freepascal.org/daily/doc/ref/refsu46.html

Michael.

Thanks Michael.  Sven already filled me in - the more I learn!

Kit

What I want to do is the following...

Say I have the expression "(1 shl x) - 1"... under the default AMD Athlon optimisations, you might get something like this:

(x in %cl, Result in %eax)
movl $1,%eax
shll %cl,%eax
subl $1,%eax

Under -CpCOREAVX2, you might get this (ignoring any zero-extensions required on the index):

(x in %ecx, Result in %eax)
movl  $1,%eax
shlxl %ecx,%eax,%eax
subl  $1,%eax

All of these sequences take at least 3 cycles, or more accurately, have a dependency chain of length 3.  Now consider using BZHI:

(x in %ecx, Result in %eax)
movl  $-1,%eax
bzhil %ecx,%eax,%eax

A dependency chain length of 2 (I'm not sure how many cycles it takes for BZHI to complete execution).

The savings go further if this result is used as a mask then discarded,
i.e. "Result := Input and ((1 shl x) - 1)".  Under AMD Athlon, for example:

(x in %cl, Input in %edx, Result in %eax)
movl $1,%eax
shll %cl,%eax
subl $1,%eax
andl %edx,%eax

Under -CpCOREAVX2:

(x in %ecx, Input in %edx, Result in %eax)
movl  $1,%eax
shlxl %ecx,%eax,%eax
subl  $1,%eax
andl  %edx,%eax

All have a dependency chain length of 4.  But with BZHI:

(x in %ecx, Input in %edx, Result in %eax)
movl  $-1,%eax
bzhil %ecx,%edx,%eax

Once again, the dependency chain length is reduced to 2.  Like with the earlier two, this sequence also works if Input is a reference rather than a register; e.g.

(x in %ecx, Result in %eax)
movl  $-1,%eax
bzhil %ecx,(ref-to-Input),%eax

A problem, however, arises if the index x is out of range.  In the case of 32-bit operands, the shift instructions in x86 and ARM (including AArch64) essentially reduce the index modulo 32.  "(1 shl 32) - 1" is often expected to return $FFFFFFFF, a mask that covers the entire bitrange, but "1 shl 32" returns 1 in this case, so the resultant mask ends up being all zeroes.  However, with BZHI, if the index is out of range, the carry flag is set and the output (%eax in this case) is set equal to the input, which results in "(1 shl 32) - 1" returning $FFFFFFFF.  I think the same thing happens with negative indices, since BZHI is essentially unsigned (it also only reads the least significant byte of the index register).  With this in mind, and "1 shl 32" being considered undefined for 32-bit operands, is this an acceptable optimisation?

Kit

P.S. There is code in the compiler that catches undefined bitmasks and simply sets it to all ones if the index is 32 or 64 or whatever the integer word size is.  If BZHI is used, a peephole or node optimisation can be used to eliminate this catch since it becomes unnecessary with BZHI.

Correction to last post.  When applying BZHI to an input ("Result := Input and ((1 shl x) - 1)"), the initial "mov $-1,%eax" is unnecessary unless the mask is being preserved, and is just:

bzhil %ecx,(ref-to-Input),%eax

Kit