Re: Left-shift of negative number

Re: Left-shift of negative number

[Pascal Cuoq]

Jens Gustedt wrote:

> Am Freitag, den 17.07.2015, 18:28 +0000 schrieb Loïc Runarvot:
> > According to the C11 standard, doing a left-shift on a negative
> > integer is considered as an undefined behavior (6.5.7:4).
> 
> There is no such thing as "considered undefined behavior",

You are right, the word “considered” is unnecessary.
A left shift on a negative integer is undefined behavior, period.

> this is a
> terminology that makes not much sense. Unfortunately the term
> "undefined behavior" is often used as a synonym for "errorneous code"
> which it just isn't.

But in this case, it is used as a synonym for “being undefined behavior”,
which it is. Or are we reading the phrase “otherwise, the behavior is undefined”
in the relevant clause of the standard differently?

I know that this is not well-known, so perhaps I should explain: ever since
the late 1990s, C compilers have been taking advantage of undefined behavior
in the C standard to introduce new optimizations. So if you rely on undefined
behavior in your C programs, they may not work today, and they may break
tomorrow. For instance, a claim very similar to yours:

> Whereas we can
> reasonably assume that a shift of a negative value in two's complement
> is the same as an unsigned shift,

may be used to justify that INT_MAX + 1 results in INT_MIN on two's
complement platforms. This line of reasoning does not work too well nowadays,
as anyone who has ever read the assembly generated by a modern optimizing
compiler for the function int f(int x) { return x + 1 > x; } has verified for
themselves.

So what about shifts of negative values then? Should we worry that they
will be broken in 2017? No, there is no need to wait.

According to this post, ICC takes full advantage today of the fact
that they are undefined behavior:

http://stackoverflow.com/questions/22883790/left-shift-of-negative-values

And according to one slide in this deck, MSVC does too(*):

http://fsl.cs.illinois.edu/images/2/27/2011-09-30-CK-MVD.pdf

> But this doesn't mean
> that a particular implementation of a C compiler or the C library
> (here musl) can't define a behavior for that.

I sincerely do not think that it's not musl's place to define the behavior
of -1 << 1, until it comes bundled with a C compiler, because until
then, the behavior of that expression is entirely without its control
and entirely within the control of unsympathetic C compilers that have
the C standard on their side. Also the phrase
“strives to be correct in the sense of standards-conformance…”
would need to be amended to something like “works with at least
two GCC-like C compilers”.

Pascal

(*) by the way, do not remember anything that these slides say about
Frama-C. The authors of the slides, when talking about it, have no idea
what the f-word they are talking about, and they have a research the usefulness
of which they conveniently want to impress you with.

Re: Re: Left-shift of negative number

[Jens Gustedt]

[-- Attachment #1: Type: text/plain, Size: 1481 bytes --]

Hello Pascal,
you a probably right with your findings and so we should change the
code as I indicated. I think we just have to promote the one constant
and then all types are unsigned and of the right width.

But I should comment on this:

Am Freitag, den 17.07.2015, 19:55 +0000 schrieb Pascal Cuoq:
> I know that this is not well-known, so perhaps I should explain: ever since
> the late 1990s, C compilers have been taking advantage of undefined behavior
> in the C standard to introduce new optimizations.

No it is actually the other way around. The C standard voluntarily
leaves certain behavior undefined to have leeway for compiler and
library implementors to do what they (think they) have to do. So there
is a clear distinction what UB means for "user" code and for the
implementation.

musl (and other C libraries I suppose) heavily rely on specific
properties of compilers, that is basically all what the writing of a C
library for a specific platform is about.

So the argument to show that this is a bug can not be "that is UB",
but must be, as you did, there is this-and-that compiler for which
this behavior is different.

Jens


-- 
:: INRIA Nancy Grand Est ::: Camus ::::::: ICube/ICPS :::
:: ::::::::::::::: office Strasbourg : +33 368854536   ::
:: :::::::::::::::::::::: gsm France : +33 651400183   ::
:: ::::::::::::::: gsm international : +49 15737185122 ::
:: http://icube-icps.unistra.fr/index.php/Jens_Gustedt ::




[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

Re: Re: Left-shift of negative number

[Szabolcs Nagy]

* Jens Gustedt <jens.gustedt@inria.fr> [2015-07-17 22:23:34 +0200]:
> Am Freitag, den 17.07.2015, 19:55 +0000 schrieb Pascal Cuoq:
> > I know that this is not well-known, so perhaps I should explain: ever since
> > the late 1990s, C compilers have been taking advantage of undefined behavior
> > in the C standard to introduce new optimizations.
> 
> No it is actually the other way around. The C standard voluntarily
> leaves certain behavior undefined to have leeway for compiler and
> library implementors to do what they (think they) have to do. So there
> is a clear distinction what UB means for "user" code and for the
> implementation.
> 

i agree..

> musl (and other C libraries I suppose) heavily rely on specific
> properties of compilers, that is basically all what the writing of a C
> library for a specific platform is about.

..but musl does not want to depend on special compiler
properties, so i disagree with this.

a libc should not make unnecessary assumptions about
other components of the implementation.
(there are cases where the assumptions are necessary
and reasonable, but negative shift is always possible
to avoid).

and it is a good thing to know our assumptions beyond
the guarantees of the standard (eg. musl relies on that
int is 2's complement and at least 32bit) so bug reports
about "ub" or "idb" is ok.

Re: Re: Left-shift of negative number

[Jens Gustedt]

[-- Attachment #1: Type: text/plain, Size: 700 bytes --]

Am Samstag, den 18.07.2015, 01:40 +0200 schrieb Szabolcs Nagy:
> and it is a good thing to know our assumptions beyond
> the guarantees of the standard (eg. musl relies on that
> int is 2's complement and at least 32bit) so bug reports
> about "ub" or "idb" is ok.

I certainly do agree, and I am sorry if my reply came along as if it
wouldn't be welcome, it definitively is.

Jens

-- 
:: INRIA Nancy Grand Est ::: Camus ::::::: ICube/ICPS :::
:: ::::::::::::::: office Strasbourg : +33 368854536   ::
:: :::::::::::::::::::::: gsm France : +33 651400183   ::
:: ::::::::::::::: gsm international : +49 15737185122 ::
:: http://icube-icps.unistra.fr/index.php/Jens_Gustedt ::




[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 181 bytes --]