What is supposed to happen if the 2nd argument is negative?

program Project1;
uses sysutils;
var  a: LongInt;
begin
a := StrToInt('-1');
WriteLn(2 << a);
WriteLn(2 << -1);
ReadLn;
end.

prints:
0
4294967296

"2 << a" translates to "shl eax,cl" (cl being loaded with the result from strtoint)

So at least my cpu thinks the result is 0. (I guess unsigned byte(-1) makes it "2 << 255")
But the compiler (3.1.1) pre-evaluating the constant, comes to a diff result.

Martin Frb wrote

What is supposed to happen if the 2nd argument is negative?

Also see <http://bugs.freepascal.org/view.php?id=17710>.

Regards,

Adriaan van Os

Martin Frb wrote

What is supposed to happen if the 2nd argument is negative?

I would propose to document it as "undefined behaviour", just like C does (http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf , section 4.5.7). The reason is that the behaviour can differ depending on the cpu, so if you want to guarantee consistent behaviour on all platforms, you can no longer just emit a shift left/right instruction and have to add all kinds of checks.

Maybe we should support emitting range checks for the right operand though (to give an error if it falls outside the range of shift values whose behaviour is defined).

Jonas

Alternatively, could it be coopted into something useful e.g. a count of the zero bits on the left/right of the operand?

Section 6.5.7. But in that standard the behaviour is undefined also when "the value of the right operand is greater than or equal to the width of the promoted left operand", which I think is a bit too simplistic (since, if we start talking about the maximum number of bits that can "legally" be shifted, then that number depends on the actual value of the left operand, but on the other hand if we accept that bits get lost, then there is no reason to limit the number of bits that can be shifted)

The right operand of a bitwise shift is a count, a real-world number of bits. A negative number doesn' t make sense and must regarded as an error. So yes, emitting range checking is the right idea. We should do better in Pascal than in C .....

Regards,

Adriaan van Os

"can differ depending on the cpu" IMHO applies to the underlying asm code/instruction.

But I would expect that the compiler should know how this instruction behaves? And then can generate correct code. (Note, I am not asking for negative to work, never expected that. I am puzzled about the diff between constant eval, and run time eval.

I do not know, if any cpu actually takes a negative argument as the shift count, but of course future cpu may do.
In any case the compiler can cast the argument to a unsigned type (making it a very big number)
a << cardinal(b)

Then there is also the maximum size of this argument (on a 64 bit cpu, any number greater 63 will empty the 1st operand). So unless there is a cpu that does not allow 64 as argument, the expression becomes either a << byte(b)
or an a cpu that takes the sign bit into consideration: a << byte(b) AND $7F

Afaik for i386 the 2nd argument is a byte size register. So oni386 the typecast to bye already happens without any overhead.

True, if range checks are enabled, otherwise see my other mail

In other words - if we allow a 1-bit shift to be always correct (independent of the value of the left operand) then N 1-bit shifts are always correct too (for any N >= 0). And then, introducing a difference between shifting N bits and shifting Nx1 bits is absurd.

Not much thought went into that C-standard (nor in anything related to C).

Regards,

Adriaan van Os

Martin Frb wrote on Tue, 19 May 2015:

Then you first have to define "correct", and then probably use a whole bunch of instructions instead of a single one on architectures whose shift instructions do not behave according to this definition "correct".

(Note, I am not asking for negative to work, never expected that. I am puzzled about the diff between constant eval, and run time eval.

Constant integer expressions are typeless (other than that they are whole numbers) and are correct to the limit of the compiler's supported range (which is low(int64) to high(qword) at this time). Run time expressions are executed using a fixed type
(http://bugs.freepascal.org/view.php?id=27739#c82395 ) rather than always evaluated using this "65 bit" arithmetic.

No, it doesn't. Not on all architectures, at least. And on some architectures (certain) shift values > 63 will set the value to 0, while others don't.

So unless there is a cpu that does not allow 64 as argument,

On x86-64, x shr 64 = x, for any value of x. On i386, x shr 32 = x, for any value of x. For PowerPC (32 bit), x shr y = 0 if bit 5 of y is set, otherwise it's (x shr (y mod 32)). Really, there are very good reasons to treat this kind of stuff as undefined (unless you want to build a language for which the speed of compiled code is irrelevant). That's also why range/overflow checking exists as an option: to enable you to still catch such cases if you want, but to not burden all code all the time with these checks.

Jonas

Adriaan van Os wrote on Tue, 19 May 2015:

No, it does not. It only depends on the type. Shifting an uint32_t with value 1 right by 32 bits is undefined. Shifting an uint64_t with value 1 right by 32 bits is 0.

Jonas

Ok

Jonas Maebe wrote

No, it does not. It only depends on the type. Shifting an uint32_t with value 1 right by 32 bits is undefined. Shifting an uint64_t with value 1 right by 32 bits is 0.

As I said, this is absurd, as so many other de-facto bad habits in computing. There should be no difference between shifting a value (of any type) right by N bits or shifting the same value (of the same type) N-times right by 1 bit. That is not a matter of type but of simple logic.

But, of course, I understand that CPUs implement it wrong and that the compilers writers want to be compatible with the CPU doing it wrong. That is probably the most practical solution. But that doesn't make it less ludicrous.

Regards,

Adriaan van Os

Adriaan van Os wrote on Tue, 19 May 2015:

But, of course, I understand that CPUs implement it wrong and that the compilers writers want to be compatible with the CPU doing it wrong. That is probably the most practical solution. But that doesn't make it less ludicrous.

There's non-ludicrous speed (not the Space Balls meaning), non-ludicrous power consumption and non-ludicrous logic: pick any two.

Jonas

Fast N-bit shifters (where N is a stored value in a register) are implemented in full parallel using multiplexers. The issue with that topology is that it doesn't scale well to large bit-widths: a shifter allowing for 64 shifts at once needs twice as many logic as a shifter only allowing 32 logic = more time needed = more
power consumption = more resources needed. So, making "the common case" fast (where N is a low number), simple logic dictates a smaller, simpler shifter - nothing wrong with that.

So in those few rare cases where you actually want to shift something 42 bits, do it in two operations, manually. I do agree code can become messy when targeting multiple platforms, but that is, IMHO, a logical difference between platforms, just like floating point arithmetic: using SSE instructions instead of the x87 instruction set, different results are obtained (and that is the /same/ platform :-) ).