Why is shifting too far undefined behvaior?

[Philipp Klaus Krause]

Looking at the C23 draft N2596, section J.2 (but this AFAIK has been the
same forever), we see that there is undefined behavior, when "An
expression is shifted by a negative number or by an amount greater than
or equal to the width of the promoted expression (6.5.7)." or "An
expression having signed promoted type is left-shifted and either the
value of the expression is negative or the result of shifting would not
be representable in the promoted type (6.5.7)."

Does anyone know why this was made undefined (as opposed to yielding an
unspecified value)? The C99 rationale doesn't mention anything.

The only idea that comes to my mind is that it would be to allow
implementations to trap at runtime when shifting too far, which might
help with debugging.

[Ike Naar]

Another thing that comes to mind is that on a machine with N-bit
wordsize, the machine instruction for shifting might only use log2(N) bits
to specify the number of places to shift.
Shifting N places or more would not be possible on such hardware
(at least, not with a single shift instruction).

[Richard Kettlewell]

True for x86, for example.

> Shifting N places or more would not be possible on such hardware
> (at least, not with a single shift instruction).

That can explain why the standard doesn’t tie the behavior down exactly,
it doesn’t explain why it leaves it as UB rather than matching Philipp’s
suggestion, or making it implementation-defined behavior (so an x86
implementation would define it as equivalent to shifting mod word size,
for instance).

--
https://www.greenend.org.uk/rjk/

[Richard Damon]

My impression is that this behavior goes back to early versions of the
standardization process, and 'Unspecified Value' wasn't a term used
then, but that has evolved. There also may have been hardware that would
trap in this case.

The wording probably could be changed to something like an unspecified
value or a trap, but it may be the case that some implementation can
show that there is some significant optimization based on this undefined
behavior (maybe based on the knowledge that the shift value now
effectively has a limited range or no behavior is defined, so can be
igrored.)

[Keith Thompson]

Dennis Ritchie wrote about this in comp.arch in 2002, but didn't
specifically explain why it's undefined behavior rather than an
unspecified value.

https://yarchive.net/comp/c_shifts.html

From: Dennis Ritchie <d...@bell-labs.com>
Newsgroups: comp.arch
Subject: Re: shift instructions on different processors
Date: Tue, 12 Feb 2002 04:47:05 +0000
Message-ID: <3C689E49...@bell-labs.com>

glen herrmannsfeldt wrote:
>
> There have been questions on both C and Java newsgroups about
> the effect of shift operations when the shift value equals or
> exceeds the number of bits available to be shifted.
>
> I know that the reason for such a restriction is that many architectures
> use only some bits of the shift amount.
>
> x86 uses the low 5 bits for 32 bit shifts, and low 6 bits for 64 bits.
>
> IBM S/360, S/370, S/390 etc., use the low 6 bits for 32 and 64 bits.
...

Meissner followed up with various other architectures as well.

I looked at my Interdata 8/32 manual (1975), which describes
a 32-bit machine, and was amused to find, under the
"Shift Left Logical" instruction,

"... the shift count is specified by the least significant
five bits of the second operand."

I added a contemporaneous hand-written notation "!!" to this.

On the next page, under "Shift Right Logical," it similarly
says, "the least significant five bits of the second operand."

Here my notation is an underlining, accompanied by "Shit!!"

And that, children, is why the C and Java rules are as they are.
The C manual in 6th Edition Unix didn't have the value restriction.
K&R I did.

Dennis

Perhaps it was thought that shifting too far is analagous to integer
overflow, which has undefined behavior for signed types. And Ritchie
may not have wanted to assume that no CPUs trap on a large shift.

K&R1 says "The result is undefined", not that it has undefined behavior
(I don't think K&R1 had the concept of undefined behavior).

--
Keith Thompson (The_Other_Keith) Keith.S.T...@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */

[Philipp Klaus Krause]

Am 21.09.21 um 20:01 schrieb Keith Thompson:

>
> I looked at my Interdata 8/32 manual (1975), which describes
> a 32-bit machine, and was amused to find, under the
> "Shift Left Logical" instruction,
>
> "... the shift count is specified by the least significant
> five bits of the second operand."

The modern Z80N (a Z80 variant used in the ZX Spectrum Next) has a
"shift left arithmetic" that shifts 16-bit register de left by the
number specified in the lower 5 bits of 8-bit register b.

So in SDCC when targeting the Z80N, left-shifting a 16-bit value could,
depending on which register the shifted value gets allocated to, shift
either by the lower 5 bits of the right operand (is the Z80N instruction
is used) or the lower 8 bits of the right operand (if normal code for
Z80 left shift is generated) or by the actual right operand (if the
value of the right operand can be determined at compile time).

[Vincent Lefevre]

In article <siceh0$1lm$1...@solani.org>,

Philipp Klaus Krause <p...@spth.de> wrote:

> Does anyone know why this was made undefined (as opposed to yielding an
> unspecified value)? The C99 rationale doesn't mention anything.

> The only idea that comes to my mind is that it would be to allow
> implementations to trap at runtime when shifting too far, which might
> help with debugging.

Yes, and perhaps to allow optimization that could be invalidated with
an unspecified value (e.g. deduce the range of some values).

--
Vincent Lefèvre <vin...@vinc17.net> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)

[Vincent Lefevre]

In article <sek2J.55967$jm6....@fx07.iad>,

Richard Damon <Ric...@damon-family.org> wrote:

> The wording probably could be changed to something like an unspecified
> value or a trap,

[...]

Note: an unspecified value or a trap = an indeterminate value

[Keith Thompson]

Vincent Lefevre <vincen...@vinc17.net> writes:
> In article <sek2J.55967$jm6....@fx07.iad>,
> Richard Damon <Ric...@damon-family.org> wrote:
>
>> The wording probably could be changed to something like an unspecified
>> value or a trap,
> [...]
>
> Note: an unspecified value or a trap = an indeterminate value

An indeterminate value is either an unspecified value or a trap
*representation". Richard didn't say "trap representation" (I won't
attempt to guess whether that's what he meant.)

A "trap" (not a term used by the standard) usually means that the
program terminates in some unfriendly way -- which might as well be
undefined behavior.

[James Kuyper]

On 9/21/21 10:05 PM, Keith Thompson wrote:
> Vincent Lefevre <vincen...@vinc17.net> writes:
>> In article <sek2J.55967$jm6....@fx07.iad>,
>> Richard Damon <Ric...@damon-family.org> wrote:
>>
>>> The wording probably could be changed to something like an unspecified
>>> value or a trap,
>> [...]
>>
>> Note: an unspecified value or a trap = an indeterminate value
>
> An indeterminate value is either an unspecified value or a trap
> *representation". Richard didn't say "trap representation" (I won't
> attempt to guess whether that's what he meant.)
>
> A "trap" (not a term used by the standard) usually means that the
> program terminates in some unfriendly way -- which might as well be
> undefined behavior.

True. But "perform a trap" is a term defined by the standard as meaning
"interrupt execution of the program such that no further operations are
performed". Per footnote 2, "fetching a trap representation might
perform a trap, but is not required to do so".
While I agree that "trap representation" is most likely what he meant,
"perform a trap" is an alternative possibility.

[Keith Thompson]

James Kuyper <james...@alumni.caltech.edu> writes:
> On 9/21/21 10:05 PM, Keith Thompson wrote:
>> Vincent Lefevre <vincen...@vinc17.net> writes:
>>> In article <sek2J.55967$jm6....@fx07.iad>,
>>> Richard Damon <Ric...@damon-family.org> wrote:
>>>
>>>> The wording probably could be changed to something like an unspecified
>>>> value or a trap,
>>> [...]
>>>
>>> Note: an unspecified value or a trap = an indeterminate value
>>
>> An indeterminate value is either an unspecified value or a trap
>> *representation". Richard didn't say "trap representation" (I won't
>> attempt to guess whether that's what he meant.)
>>
>> A "trap" (not a term used by the standard) usually means that the
>> program terminates in some unfriendly way -- which might as well be
>> undefined behavior.
>
> True. But "perform a trap" is a term defined by the standard as meaning
> "interrupt execution of the program such that no further operations are
> performed". Per footnote 2, "fetching a trap representation might
> perform a trap, but is not required to do so".

You're right. That definition is N1570 3.19.4.

> While I agree that "trap representation" is most likely what he meant,
> "perform a trap" is an alternative possibility.

(BTW, you sent your reply to me by email as well as posting it here.)

[Richard Damon]

Yes, that was the 'trap' I was referring to. The Standard basically uses
perform a trap to mean a hardware based exception that the software may
or might not be able to intercept as a 'signal'.

[David Brown]

One possibility for some of the cases is that a target could implement
"x <<= y" in hardware or software as :

while (y--) x <<= 1;

(Other shift operations would be similar.)

For at least some of the cases that are undefined behaviour in the spec,
if these were changed to implementation-defined or unspecified results
then you'd need extra checks to avoid almost-infinite loops.

For the signed integers, the expectation for arithmetic operations is
that the results will always be mathematically correct for integer
results. If you can't get the correct result, it is undefined
behaviour. This allows the compiler a great deal of freedom and
information that can be used for analysis and optimisation - such as
knowing that adding two positive numbers gives a positive result.

However, those are not good reasons for leaving (E1 << E2) undefined for
negative E1 in cases where E1 * 2 ^ E2 fits within the result type, or
for making (E1 >> E2) implementation defined for negative E1.

[James Kuyper]

On 9/22/21 12:12 AM, Keith Thompson wrote:
...

> (BTW, you sent your reply to me by email as well as posting it here.)

Sorry - I'm still failing to adapt to the change in the meaning of
Thunderbird's "Reply" button.

For those who have no idea what I'm talking about - for a decade or
more, I've used Mozilla Thunderbird to post follow-up messages using the
"Reply" button. Several months ago they added a "Follow-Up" button to do
that, and changed the "Reply" button to send a message exclusively to
the e-mail of the person who posted the message. Even though the new
button naming makes more sense and is more consistent with the way
e-mails are handled, breaking a habit of two decades has proven very
difficult for me.

[James Kuyper]

On 9/22/21 7:08 AM, Richard Damon wrote:
> On 9/22/21 12:02 AM, James Kuyper wrote:

...

>> True. But "perform a trap" is a term defined by the standard as meaning
>> "interrupt execution of the program such that no further operations are
>> performed". Per footnote 2, "fetching a trap representation might
>> perform a trap, but is not required to do so".
>> While I agree that "trap representation" is most likely what he meant,
>> "perform a trap" is an alternative possibility.
>>
>
> Yes, that was the 'trap' I was referring to. The Standard basically uses
> perform a trap to mean a hardware based exception that the software may
> or might not be able to intercept as a 'signal'.

I don't think that raising a signal qualifies. The standard specifies
that "no further operations are performed". It doesn't add "unless the
signal is intercepted". I don't think that anything which allows
handlers registered using atexit(), abort_handler_s(),
ignore_handler_s(), or set_constraint_handler_s() to be executed
qualifies as performing a trap, either, since those would also allow
further operations to be performed.

[Vincent Lefevre]

In article <87zgs5m...@nosuchdomain.example.com>,

Keith Thompson <Keith.S.T...@gmail.com> wrote:

> Vincent Lefevre <vincen...@vinc17.net> writes:
> > In article <sek2J.55967$jm6....@fx07.iad>,
> > Richard Damon <Ric...@damon-family.org> wrote:
> >
> >> The wording probably could be changed to something like an unspecified
> >> value or a trap,
> > [...]
> >
> > Note: an unspecified value or a trap = an indeterminate value

> An indeterminate value is either an unspecified value or a trap
> *representation". Richard didn't say "trap representation" (I won't
> attempt to guess whether that's what he meant.)

> A "trap" (not a term used by the standard) usually means that the
> program terminates in some unfriendly way -- which might as well be
> undefined behavior.

Yes, but a "trap" (where the word appears without "representation"
in the standard) is never used to mean a value, contrary to
"trap representation". Since this was applied to "indeterminate value",
I interpreted "trap" as "trap representation".

[Vincent Lefevre]

In article <sie9tb$5jg$1...@dont-email.me>,

James Kuyper <james...@alumni.caltech.edu> wrote:

> True. But "perform a trap" is a term defined by the standard as meaning
> "interrupt execution of the program such that no further operations are
> performed". Per footnote 2, "fetching a trap representation might
> perform a trap, but is not required to do so".
> While I agree that "trap representation" is most likely what he meant,
> "perform a trap" is an alternative possibility.

I wonder why it is defined, because it does not seem to be used at all
in the standard.

[Vincent Lefevre]

In article <sif7c9$t46$1...@dont-email.me>,

David Brown <david...@hesbynett.no> wrote:

> However, those are not good reasons for leaving (E1 << E2) undefined for
> negative E1 in cases where E1 * 2 ^ E2 fits within the result type, or
> for making (E1 >> E2) implementation defined for negative E1.

Yes, and also for non-negative E1.

There was a "bug" in GNU MPFR (only affecting tools checking the
conformance, as in practice, this worked on all processors, AFAIK),
because while we ensured that E1 * 2 ^ E2 always fitted, E2 could
be equal to the type width (this can happen when E1 = 0), which is
currently disallowed by the standard.

[James Kuyper]

Correction - since the definition of "perform a trap" says explicitly
that "Implementations that support Annex L are permitted to invoke a
runtime-constraint handler when they perform a trap.", I should not have
included set_constraint_handler_s() in that list.

[James Kuyper]

On 9/23/21 7:10 AM, Vincent Lefevre wrote:
> In article <sie9tb$5jg$1...@dont-email.me>,
> James Kuyper <james...@alumni.caltech.edu> wrote:
>
>> True. But "perform a trap" is a term defined by the standard as meaning
>> "interrupt execution of the program such that no further operations are
>> performed". Per footnote 2, "fetching a trap representation might
>> perform a trap, but is not required to do so".
>> While I agree that "trap representation" is most likely what he meant,
>> "perform a trap" is an alternative possibility.
>
> I wonder why it is defined, because it does not seem to be used at all
> in the standard.

Me too. It is used in notes in the descriptions of "bounded undefined
behavior" (L2.2) and "critical undefined behavior" (L2.3). However,
since performing a trap is clearly one of the things permitted for
undefined behavior, it's not clear that mentioning it in those contexts
makes any difference, particularly since notes are non-normative.

[Tim Rentsch]

Philipp Klaus Krause <p...@spth.de> writes:

> Looking at the C23 draft N2596, section J.2 (but this AFAIK has been
> the same forever), we see that there is undefined behavior, when "An
> expression is shifted by a negative number or by an amount greater
> than or equal to the width of the promoted expression (6.5.7)." or
> "An expression having signed promoted type is left-shifted and
> either the value of the expression is negative or the result of
> shifting would not be representable in the promoted type (6.5.7)."
>
> Does anyone know why this was made undefined (as opposed to yielding
> an unspecified value)?

This question tacitly assumes that there needs to be a reason.
To me it seems quite plausible that these cases were left as
undefined behavior simply because no one saw any reason to
define them. Not everything thinks that just because something
can be done that it should be done.

> The C99 rationale doesn't mention anything.

That observation supports the hypothesis that no one thought it
important to define the behavior in any way.