clang generates incorrect code with bit shifts passed as function parameter

[mtl1979]

Source:

#include <stdlib.h>
#include <string.h>

int main()
{
   int bits = 8;
   char* a = (char*)malloc(1 << bits);
   char* b = (char*)malloc(1 << bits);
   memcpy(b, a, 1 << bits);
   return 0;
}

Generated assembler code:

main:                                   # @main
        .cfi_startproc
# %bb.0:
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset %rbp, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register %rbp
        subq    $32, %rsp
        movl    $0, -4(%rbp)
        movl    $8, -8(%rbp)
        movl    -8(%rbp), %ecx
        movl    $1, %eax
                                        # kill: def $cl killed $ecx
        shll    %cl, %eax
        movslq  %eax, %rdi
        callq   malloc@PLT
        movq    %rax, -16(%rbp)
        movl    -8(%rbp), %ecx
        movl    $1, %eax
                                        # kill: def $cl killed $ecx
        shll    %cl, %eax
        movslq  %eax, %rdi
        callq   malloc@PLT
        movq    %rax, -24(%rbp)
        movq    -24(%rbp), %rdi
        movq    -16(%rbp), %rsi
        movl    -8(%rbp), %ecx
        movl    $1, %eax
                                        # kill: def $cl killed $ecx
        shll    %cl, %eax
        movslq  %eax, %rdx
        callq   memcpy@PLT
        xorl    %eax, %eax
        addq    $32, %rsp
        popq    %rbp
        .cfi_def_cfa %rsp, 8
        retq

The relevant part is:

        shll    %cl, %eax
        movslq  %eax, %rdi

It should zero-extend, not sign-extend as bit shift is unsigned operation. It's also promoting after the shift which can possibly cause overflow, instead it should promote before the shift. In ideal world, one could use UINTPTR_C() to force promoting before the cast, but none of the common compilers understand it.

clang version: Ubuntu clang version 15.0.2-1

[topperc]

I believe clang's behavior is in agreement with the C standard. The result of the expression (1 << bits) always has int type. It doesn't matter how it is used.

Converting int to size_t follows this rule from the C standard

Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or
subtracting one more than the maximum value that can be represented in the new type
until the value is in the range of the new type.6

This happens to map to sign extension in a twos complement representation.

[mtl1979]

Left shift can never result in signed integer as that would by definition overflow instead of discarding the highest bit. Constant can't overflow either as it is always represented by type that can contain the value without truncation, even if that value requires more bits than 32 or 64. There is no rule in C standard that states constant is always 32-bit signed integer. Even hexadecimal constants are unsigned by default, no matter what the highest bit is.

As such left shifting of already negative number doesn't result in defined behaviour and actually already results in warning.

[llvmbot]

@llvm/issue-subscribers-clang-frontend

[shafik]

The C standard says the following for bitwise shift:

The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

So the type of the promoted operands in this case will be int and the result will be type int.

We can also see this from the AST dump, godbolt: https://godbolt.org/z/hq4Gvdhcf

    |         `-BinaryOperator <col:28, col:33> 'int' '<<'
    |           |-IntegerLiteral <col:28> 'int' 1
    |           `-ImplicitCastExpr <col:33> 'int' <LValueToRValue>
    |             `-DeclRefExpr <col:33> 'int' lvalue Var 0x56399d510718 'bits' 'int'

we can see the integer literal is type int and bits is also type int after the implicit cast and the result type is int.

[mtl1979]

C standard, the 1999 version, says the bitwise shift operation is only defined for positive numbers (unsigned, logical shift), as in unsigned numbers; behaviour of negative signed numbers (arithmetic shift) are left as compiler extension, but in the standard the result is always as if the left operand and the result is unsigned.

Like I mentioned earlier, result of left shift "can" throw arithmetic overflow if used with signed integer and the highest bit changes, but the result must still be same as with logical shift (unsigned). Result of right shift of signed integer is always undefined behaviour in standard.

[topperc]

clang, gcc, icc, and MSCV all do a sign extend after the shift either through movsx or cdqe. https://godbolt.org/z/sPnoKEYWj

[mtl1979]

@topperc Just because all common compilers do the same way doesn't mean the way they do it is correct. This is already mentioned online when citing the 1999 version of C standard, which is still the most relevant version.

I've already filed bugs against clang, gcc and Visual C++ mentioning all the possible incorrect and correct code examples with actual and expected results. This also comes to observation that compilers do not always declare UINTPTR_C() macro which is the only "correct" way to declare 64-bit integer constants/literals in bitwise shifts that can change bit width depending on architecture.

One would expect there to also be SIZE_C() macro, but I haven't seen any compiler so far that fully implements it and/or the underlying type modifier "z".

Some compilers don't even declare signed equivalent ssize_t, even though memcpy use it internally as a maximum limit, and it sometimes traps if the highest bit of third parameter is set (for example under FreeBSD).

[alvinhochun]

C standard, the 1999 version, says the bitwise shift operation is only defined for positive numbers (unsigned, logical shift), as in unsigned numbers; behaviour of negative signed numbers (arithmetic shift) are left as compiler extension, but in the standard the result is always as if the left operand and the result is unsigned.

I think this is a misinterpretation of the standard. From C99 §6.5.7/p4:

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. [...] If E1 has a signed type and nonnegative value, and E1 × 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

According to this, 1 << 31 is undefined behaviour; it does not give an unsigned result. It is the same in C11 and C++11, but C++14 makes it defined by casting the result back to signed.

GCC does have a documented extension (https://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html) which makes its behaviour implementation-defined, but still keeps the result signed, making it the same as C++14:

• The results of some bitwise operations on signed integers (C90 6.3, C99 and C11 6.5).

Bitwise operators act on the representation of the value including both the sign and value bits, where the sign bit is considered immediately above the highest-value value bit. [...]

As an extension to the C language, GCC does not use the latitude given in C99 and C11 only to treat certain aspects of signed ‘<<’ as undefined. However, -fsanitize=shift (and -fsanitize=undefined) will diagnose such cases. They are also diagnosed where constant expressions are required.

To me it looks like Clang is doing the right thing.

[mtl1979]

I've tested all possible shifts with x86-64 and the result of the left shift operation is always unsigned logical shift... It's essentially impossible to emit assembler code that does arithmetic signed left shift as the processor microcode doesn't have any implementation for it. As such even attempt to emit the mnemonic will result in wrong result as non-existing mnemonic doesn't cause hardware exception, it is just silently ignored and treated as logical unsigned shift, which does not give same result when shift amount is maximum allowed (31 or 63) assuming the left side of the operation is 1 that requires only one bit.

x86-64 hardware implementation does not agree with the standard as it will always modify CF flag, which is also known as overflow flag, and does modify highest bit during attempted arithmetic shift. This makes it clear that the highest bit can't be used for sign-extending as its value is technically garbage and thus undefined behaviour by the strict definition of the C99 standard.

However the right shift can be emitted as arithmetic signed shift, which still agrees with my initial statement that the assembler output is indeed incorrect.

[alvinhochun]

However the right shift can be emitted as arithmetic signed shift, which still agrees with my initial statement that the assembler output is indeed incorrect.

Left shifts and right shifts are two separate operations. Clang already compiles signed right shift as sar, which is correct. I don't see how that is related to left shift?

[topperc]

Here's my understanding according to the C standard.

The constant 1 is a decimal constant with no suffix. It's type is the first type it fits in from the list int, long int or long long int. Obviously it fits in int so 1 is an int.

Now for the left shift. The standard says

The integer promotions are performed on each of the operands. The type of the result is
that of the promoted left operand.

Since we already established that the 1 is an int, integer promotion doesn't apply to it. According to the second sentence the result of the expression matches the left operand which is int so the result is also int.

Now we come to the conversion from int to size_t. That is done according to this sentence

Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or
subtracting one more than the maximum value that can be represented in the new type
until the value is in the range of the new type.4

In a twos complement representation this maps to sign extension. This is done based on the types and not the operation that produced the type.

It is undefined behavior to left shift a negative int or for left shift to set the MSB of int. So assuming 32-bit int, the program has undefined behavior if bit 31 is set in the int before or after the shift. So for (1 << bits), bits must be <= 30 for the program to be well defined. If bit 31 is zero, as it must be to be a well defined program, the sign extend is equivalent to zero extend.

Now to your point about no UINTPTR_C() or SIZET_C, you could write ((size_t)1 << bits) and it would do the right thing.

[mtl1979]

Even with arithmetic left shift, the definition in the standard implies that the result of shift must be left side multiplied by 2 to the power of right-side, which means the result must be all zeroes on overflow (not 0x80000000)... This part is not undefined behaviour in the standard. Sign-extending when the high bit is zero is same as zero-extending. The undefined part only applies to negative numbers. This is because the sign bit can be overwritten with any of the other bits and the value can wrap to positive numbers, thus result not agreeing with the first sentence.

So the conclusion is that using arithmetic left or right shift with positive numbers, the high bit of result should always be 0, and with negative numbers, the high bit of result should always be 1. The remaining bits are the 31 lowest bits of the result of the shift instruction. Even if the architecture doesn't support arithmetic left shift in hardware, the generated code should either conform to standard or refuse to generate the code, or emit warning, if it can't follow the exact letter of the standard.

Because on x86-64, there is only logical left shift instruction in microcode, the generated code is incorrect. The arithmetic shift should not result in "shl(l)" mnemonic alone ("sal(l)" mnemonic being alias of "shl(l)"). It should mask out the highest bit of result. In optimized code the masking can be eliminated if the result is known to have highest bit unset.

[topperc]

(1 << 31) is undefined behavior by this sentence from the spec.

If E1 has a signed
type and nonnegative value, and E1 × 2
E2 is representable in the result type, then that is
the resulting value; otherwise, the behavior is undefined.

1 * 2^31 should be +2147483648, but that isn't representable in an int so it's undefined behavior.

Twos complement storage for int is not part of the C standard. So the standard does not define what happens when a positive number is shifted to become a negative number. A different result would happen if the int were stored in sign magnitude, for example.

[mtl1979]

Twos complement storage for int is not part of the C standard. So the standard does not define what happens when a positive number is shifted to become a negative number. A different result would happen if the int were stored in sign magnitude, for example.

Actually it does define shift expression quite accurately. It is defined as binary operation, which means left shift is always unsigned (logical shift) as interpreting it as signed (arithmetic) would violate the definition. This is scattered all around the C99 standard, but it's quite easy to extract the relevant sentences by searching for "shift" in the PDF version.

I'm not arguing that the C99 standard itself is incorrect behaviour, but in places it contradicts itself and that clang makes wrong assumptions based on undefined behaviour when it comes to generating code for x86-64. x86 architecture was created a long time before the C99 standard was written or ratified and like I mentioned, the contents of the standard have changed since the launch of the architecture. C99 was widely adopted by compiler developers no earlier than 2015 (Visual C++ 2015 had quite complete support for C99).

[topperc]

The standard text for left shift describes different behaviors for unsigned types and signed types.

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with
zeros. If E1 has an unsigned type, the value of the result is E1 × 2
E2, reduced modulo
one more than the maximum value representable in the result type. If E1 has a signed
type and nonnegative value, and E1 × 2
E2 is representable in the result type, then that is
the resulting value; otherwise, the behavior is undefined.

I wouldn't even say its defined as a binary operation. Its defined in terms of multiply.

Where does it say its always an unsigned operation?

[mtl1979]

6.3 Conversions 6.3.1.1 Boolean, characters, and integers

"Several operators convert operand values from one type to another automatically."

"The rank of any unsigned integer type shall equal the rank of the corresponding signed integer type, if any."

"If an int can represent all values of the original type, the value is converted to an int; otherwise, it is converted to an unsigned int."

As left shift of signed integer is undefined, the automatic conversion to unsigned integer will apply, thus left side or shift operator is unsigned by default due to being implementation dependent (as in microcode of x86-64 architecture).

There is no rule that width of signed shift is 31 bits, even though precision is 31 bits. Width of any shift is either 32 or 64 bits in modern architectures. As such promotion to unsigned type will always happen with left shift due to failure of third quote from the standard. The modulo of the result to 0x7FFFFFFF will violate the part "If an int can represent all values of the original type". The result of left shift is always unsigned due to lack of arithmetic left shift implementation in microcode, as allowed by the first quote.

Original assertion was that literal 1 is converted to "int" and stays as "int", but the reality is that it is converted to "unsigned int" in the shift operator as stated in the first quote and should stay as "unsigned int" as stated in the third quote.

[topperc]

As left shift of signed integer is undefined, the automatic conversion to unsigned integer will apply

It's undefined means it undefined. It doesn't mean it become unsigned because that is defined.

Original assertion was that literal 1 is converted to "int" and stays as "int", but the reality is that it is converted to "unsigned int" in the shift operator as stated in the first quote and should stay as "unsigned int" as stated in the third quote.

An int can represent literal 1 so if it started as and int why should it be converted to unsigned int?

[mtl1979]

As left shift of signed integer is undefined, the automatic conversion to unsigned integer will apply

It's undefined means it undefined. It doesn't mean it become unsigned because that is defined.

No, it becomes unsigned as that is what all modern architectures do in hardware. Compiler should always generate code that works with the target instruction set.

Original assertion was that literal 1 is converted to "int" and stays as "int", but the reality is that it is converted to "unsigned int" in the shift operator as stated in the first quote and should stay as "unsigned int" as stated in the third quote.

An int can represent literal 1 so if it started as and int why should it be converted to unsigned int?

But int can't represent all results of left shift expression. This is same as implementing "left shift" as C function, its signature would be unsigned left_shift(unsigned value, unsigned char shift_amount);. This signature agrees with the C99 standard and all three quotes I mentioned. Second parameter is unsigned char instead of int just because it's more efficient as it is using 8-bit register CL internally and makes it clear negative amounts are discouraged.

As I already said earlier, arithmetic left shift can be implemented in software as combination of logical left shift and mask with 0x8000000, basically copying the highest bit from source operand to result operand.

[alvinhochun]

As left shift of signed integer is undefined, the automatic conversion to unsigned integer will apply

It's undefined means it undefined. It doesn't mean it become unsigned because that is defined.

No, it becomes unsigned as that is what all modern architectures do in hardware. Compiler should always generate code that works with the target instruction set.

No, undefined behaviour is undefined. The standard does not impose any requirements when it comes to undefined behaviour. When a compiler generates code which happens to do something for the undefined cases, it is either by chance or a compiler extension.

Original assertion was that literal 1 is converted to "int" and stays as "int", but the reality is that it is converted to "unsigned int" in the shift operator as stated in the first quote and should stay as "unsigned int" as stated in the third quote.

An int can represent literal 1 so if it started as and int why should it be converted to unsigned int?

But int can't represent all results of left shift expression. This is same as implementing "left shift" as C function, its signature would be unsigned left_shift(unsigned value, unsigned char shift_amount);. This signature agrees with the C99 standard and all three quotes I mentioned. Second parameter is unsigned char instead of int just because it's more efficient as it is using 8-bit register CL internally and makes it clear negative amounts are discouraged.

As I already said earlier, arithmetic left shift can be implemented in software as combination of logical left shift and mask with 0x8000000, basically copying the highest bit from source operand to result operand.

The standard is clear that the result type of a shift operation is that of the promoted left operand, as already quoted multiple times in previous replies. Because the type of the promoted left operand is signed int, the result must also be signed int. It does not matter what may seem more reasonable. What you suggested outright violates the standard.

[mtl1979]

The standard clearly says the result of arithmetic left shift is modulo the precision of signed int, which is same as mask with 0x80000000, which means it doesn't violate the standard. Restoring back the highest bit means shift by 0 bits gives same value as result, which agrees with the standard, as the valid range is 0-31.

As I already quoted, promotion can be operator specific, which means it can also be considered implementation-specific, as very few architectures can do arithmetic left shift, which means arithmetic left shift always depend on implementation. This doesn't violate the standard and still means the generated code above is wrong as it is clearly without any optimizations applied, otherwise it would have deduced that 1 << 8 always equals 256 and that movl $0, -4(%rbp) has no effect.