Discussion:
definition of implementation-defined behavior
(too old to reply)
Noob
2015-05-15 20:18:35 UTC
Permalink
Raw Message
[ Cross-posted to comp.std.c ]
As far as I understand (which may be not far enough),
"Implementation-defined behavior" = "unspecified behavior
where each implementation documents how the choice is made"
"Unspecified behavior" = "use of an unspecified value,
or other behavior where this International Standard
provides two or more possibilities and imposes no further
requirements on which is chosen in any instance"
When the standard qualifies a program construct as
"implementation-defined", the standard is supposed
to provide an exhaustive list (implicit or explicit)
of the allowed behaviors an implementation may choose
from. "Do something random" is typically not an option.
I am afraid that you have fallen foul of a serious gotcha in the
standard. While that is ONE interpretation, it is not the one
held my the majority of WG14 when I was on it, which was that an
implementation was allowed to specify that the behaviour was
undefined. And, of course, an implementation is allowed to define
undefined behaviour, and many do.
If you regard that as hopelessly confusing and inconsistent, you
are not alone, but those of us who tried to get the mess improved
(it is not soluble) failed dismally. Some other languages try to
ensure that all implementation-defined behaviour has a specified
intent (and sometimes constraints on what may happen), and have a
generic statement that honouring the intent is expected.
The definitions I provided were copied from the C99 standard.
The last paragraph was just my own interpretation.

Is an implementation allowed to specify program constructs
identified as "implementation-defined" as having undefined
behavior? (What an awkward sentence...)

Regards.
Nick Maclaren
2015-05-15 20:24:23 UTC
Permalink
Raw Message
Post by Noob
Is an implementation allowed to specify program constructs
identified as "implementation-defined" as having undefined
behavior? (What an awkward sentence...)
The majority of WG14 agreed; a minority did not. The people who
tried to get it formally stated failed to do so.


Regards,
Nick Maclaren.
s***@casperkitty.com
2015-10-08 18:35:54 UTC
Permalink
Raw Message
Post by Nick Maclaren
Post by Noob
Is an implementation allowed to specify program constructs
identified as "implementation-defined" as having undefined
behavior? (What an awkward sentence...)
The majority of WG14 agreed; a minority did not. The people who
tried to get it formally stated failed to do so.
The C language would be in much better shape if most of the actions which
presently invoke Undefined Behavior were specified as follows:

1. Implementations would be required to document the full range of
consequences that might result; every possible consequence must be
accounted for, but implementations may list potential consequences
beyond those that actually occur in the present implementation.

2. Saying "The consequences cannot be bounded with certainty" would
be a conforming specification, but would be recognized as being less
helpful than more specific guarantees.

Most of the actions which presently invoke Undefined Behavior will, on 99%
of implementations, have one of the following consequences:

1. The action will use the same instruction or instruction sequence that
would be used to perform an action in the non-UB case, with whatever
consequences would result from doing that. For example, on a 32-bit
machine, 1u<<35 might yield 8 if the shift-left instruction evaluated
its bit-count operand mod 32.

2. The action will use an instruction sequence which will yield the
"semantically-correct" behavior. For example, on a 32-bit machine,
1u<<35 might yield 0 if it were evaluated by shifting left one bit,
35 times.

3. The action which will trap in an implementation-defined fashion which
could typically be configured by impelementation-defined means to cause
an abnormal program termination (or will do so by default).

Because different implementations might usefully do each of these, mandating
any particular behavior would prevent platforms which did something else
from exposing that ability to programmers. Further, because doing #1 may
on some platforms have unpredictable consequences, the actions could not be
described as invoking Implementation-Defined behavior since that required
that the document say what would happen, rather than merely listing various
things that might.

Although from a requirements standpoint there would be no difference between
Undefined Behavior and behavior which an implementation would be required
to bound, if implementations that needed to specify that a behavior was
unbounded could do so simply by neglecting to specify otherwise, having the
spec imply that implementations should try to be more specific when practical
would have helped make clear what language people were actually writing code
in. A significant portion (perhaps not quite a majority, but a large chunk
nonetheless) of the code written in the 1990s for microcomputers was written
not in C89, but a de-facto quasi-standard superset to which compiler
manufacturers were expected to conform. For some strange reason, some people
seem to believe that certain constructs have always invoked unconstrained
Undefined Behavior, when the reality is that for most such actions any
compiler which didn't do one of a small number of common actions would be
viewed as quirky and rejected by the marketplace. Unfortunately, despite
the fact that the C compiler marketplace is totally dominated by compilers
for microcomputers, the Standards Committee has refused to even acknowledge
the existence of such de facto standards.

I suspect the supposed reason for refusing to acknowledge such standards is
to avoid fragmenting the language. On the other hand, I would counter that
since one should not expect a little 4Kbyte microcontroller to be able to
usefully run the same software as a 4Gbyte PC, one should not expect
that a C compiler for the tiny microcontroller should necessarily support
every feature that would be available on the PC. The fact that a machine
can't support useful features which are available on other machines should
not prevent that machine from running C programs that don't need that
feature, but on the flip-side, the fact that a useful feature might not be
supportable on a 4Kbyte micro doesn't mean it shouldn't be made available
to C programmers on a 4GByte PC. Documenting useful features which are
available on some platforms but not all would fragment the language far
less than having compiler writers independently decide how to support
features which programmers require but which are not provided for by the
Standard.
Wojtek Lerch
2015-10-09 04:52:25 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Most of the actions which presently invoke Undefined Behavior will, on 99%
I don't have enough statistical data to judge the accuracy of your claim
about "most" and "99%", but you missed an important case: many compilers
these days put a lot of effort in optimization, and often make decisions
based on the assumption that the programmer has made sure to avoid
undefined behaviour. A smart optimizer can reshuffle a program's
operations to such a degree that running it with inputs that trigger
undefined behaviour can be completely different from what a human might
expect based on a naive reading of the C code.
m***@yahoo.co.uk
2015-10-09 14:47:37 UTC
Permalink
Raw Message
Post by Wojtek Lerch
Post by s***@casperkitty.com
Most of the actions which presently invoke Undefined Behavior will, on 99%
I don't have enough statistical data to judge the accuracy of your claim
about "most" and "99%", but you missed an important case: many compilers
these days put a lot of effort in optimization, and often make decisions
based on the assumption that the programmer has made sure to avoid
undefined behaviour. A smart optimizer can reshuffle a program's
operations to such a degree that running it with inputs that trigger
undefined behaviour can be completely different from what a human might
expect based on a naive reading of the C code.
Yes. My favourite is:
int32_t array[128/4], v=0x00010203;
size_t x;
for (x=0; x < 128/4; x++) {
array[x] = v;
v += 0x01010101;
}
GCC optimizes this to a loop that overwrites all memory.
The problem is that it first transforms it into something like:
int32_t array[128/4], *p=array, v = 0x00010203;
do {
*p++ = v;
v += 0x01010101;
} while (v != 0x80818283);
Then it notices that v starts positive and increases, so it can
never be negative ... so it omits the test.
Kaz Kylheku
2015-10-09 15:12:42 UTC
Permalink
Raw Message
Post by m***@yahoo.co.uk
Post by Wojtek Lerch
Post by s***@casperkitty.com
Most of the actions which presently invoke Undefined Behavior will, on 99%
I don't have enough statistical data to judge the accuracy of your claim
about "most" and "99%", but you missed an important case: many compilers
these days put a lot of effort in optimization, and often make decisions
based on the assumption that the programmer has made sure to avoid
undefined behaviour. A smart optimizer can reshuffle a program's
operations to such a degree that running it with inputs that trigger
undefined behaviour can be completely different from what a human might
expect based on a naive reading of the C code.
int32_t array[128/4], v=0x00010203;
size_t x;
for (x=0; x < 128/4; x++) {
array[x] = v;
v += 0x01010101;
}
GCC optimizes this to a loop that overwrites all memory.
Any GCC version whatsoever on any target?
Post by m***@yahoo.co.uk
int32_t array[128/4], *p=array, v = 0x00010203;
do {
*p++ = v;
v += 0x01010101;
} while (v != 0x80818283);
Then it notices that v starts positive and increases, so it can
never be negative ... so it omits the test.
The final value v attains is only 0x20212223. The hypothesized generated code
is testing for an incorrect final value.
m***@yahoo.co.uk
2015-10-10 09:23:06 UTC
Permalink
Raw Message
Post by Kaz Kylheku
Post by m***@yahoo.co.uk
Post by Wojtek Lerch
Post by s***@casperkitty.com
Most of the actions which presently invoke Undefined Behavior will, on 99%
I don't have enough statistical data to judge the accuracy of your claim
about "most" and "99%", but you missed an important case: many compilers
these days put a lot of effort in optimization, and often make decisions
based on the assumption that the programmer has made sure to avoid
undefined behaviour. A smart optimizer can reshuffle a program's
operations to such a degree that running it with inputs that trigger
undefined behaviour can be completely different from what a human might
expect based on a naive reading of the C code.
int32_t array[128/4], v=0x00010203;
size_t x;
for (x=0; x < 128/4; x++) {
array[x] = v;
v += 0x01010101;
}
GCC optimizes this to a loop that overwrites all memory.
Any GCC version whatsoever on any target?
The actual bug report (with correct code) is:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=33498

RESOLVED INVALID
s***@casperkitty.com
2015-10-10 19:08:51 UTC
Permalink
Raw Message
Post by m***@yahoo.co.uk
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=33498
RESOLVED INVALID
I wish compiler writers would recognize that:

1. The purpose of a compiler is to facilitate the generation of
programs which meet application requirements.

2. In many fields, *ALL* applications are subject to the following
requirements:

a. Given valid input, produce valid output.

b. Given invalid (possibly maliciously crafted) input, uphold some
loose behavioral guarantees [e.g. don't allow someone who crafts
malicious input to execute arbitrary code].

3. A program which cannot be reasonably expected to meet requirements
should be considered, at best, useless, and the "efficiency" of such
a program is meaningless.

I do not think those statements should be particularly controversial.

If one takes the view that it is impossible to know whether a program's
behavior will meet requirements when it performs actions whose behavior is
constrained by neither the C Specification nor platform documentation, that
would imply that for many fields, any useful program must never invoke
Undefined Behavior for any combination of inputs. This would in turn
imply that in all situations where an optimizer would be able to improve
the "efficiency" of a program by making UB-based inferences about the input
data it would receive, the resulting executable would be useless. I fail
to see much value in optimization features that are only effective on
useless programs.

I would suggest that from an optimization perspective, it would be much more
useful to have implementations specify behavioral models which allow the
compiler considerable flexibility, but which would offer strong enough
guarantees to assist programmers in meeting application requirements.

For example, I would like to see some normative behavioral models for
overflow handling which are targeted toward the assumption that overflow
will not occur for valid input, but might occur with maliciously-crafted
input. A fairly tight overflow model, for example, might guarantee to
abide by the following constraints:

1. The result of every calculation may be mod-reduced via an Unspecified
power-of-two modulus which is at least as large as the appropriate
integer size, and which satisfies #2.

2. Any value stored to a variable of the same size which will be read
or partially-written via an alias before it is next written must
have been mod-reduced to its proper size by an earlier calculation.

3. A variable which is not aliased as described in #2 may hold a value
larger than its type provided that that variable and any others to
which the variable might be copied without intervening arithmetic
expressions must be large enough to hold that value. No portion of
a variable may spontaneously change its value.

4. A type-cast expression shall be viewed as a mod-reduction operation
even the operand is being cast to its own type.

Such rules would allow a number of useful optimizations compared with
requiring strict mod reduction (especially on systems which, because of
memory-bus or other constraints, have an "int" size which smaller than
the paltform's main arithmetic registers) but would still do a very good
job of keeping programs from falling "off the rails". For example, given:

int arr[1000];
int blah(int x, int y)
{
if (x < 0 || y < 0) return 1;
x+=y;
if (x < 0) return 2;
if (x >= 1000) return 3;
return arr[i]++;
}

a compiler which was required to use mod-wrapping on the integer overflow
would not be allowed to optimize away the second "if", but under the rules
given above a compiler would be free to have the overflow case store either
a wrapped or unwrapped value into x, provided that all downstream code saw
the same value. It would thus be unspecified whether passing (2147483647,1)
to the function would cause it to return 2 or 3, but if the second "if" saw
the positive value, the third "if" would be required to do as well.

Note that because there are some platforms where code that returned 2 in
the overflow case could be more efficient than code which had to return
3, and there are other platforms where code which returned 3 could be
more efficient than code which had to return 2, a program which could leave
overflow handling to a compiler which guaranteed the semantics listed
above could more efficiently meet a requirement that the function not
expose security vulnerabilities than would be possible if a program had
to check for the overflow case itself.

Allowing somewhat looser constraints would increase the level of care
necessary for code which is guarding things like array indices, but
would make it possible for carefully-written code to leave a compiler
with more opportunities for useful optimizations than would be possible
under the tighter model given above.

While I have no objection to the fact that the C Standard does not mandate
that compilers support any particular behavioral model for things like
overflow, I think it is unhelpful for the Committee to completely ignore
the fact that most platforms have historically provided some guarantees
surrounding overflow, and that a lot of code written to exploit such
guarantees is much more efficient than it could have been if those guarantees
were unavailable.
Wojtek Lerch
2015-10-11 06:01:11 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
If one takes the view that it is impossible to know whether a program's
behavior will meet requirements when it performs actions whose behavior is
constrained by neither the C Specification nor platform documentation, that
would imply that for many fields, any useful program must never invoke
Undefined Behavior for any combination of inputs.
For many fields, yes.
Post by s***@casperkitty.com
This would in turn
imply that in all situations where an optimizer would be able to improve
the "efficiency" of a program by making UB-based inferences about the input
data it would receive, the resulting executable would be useless.
That sounds backwards.

If a compiler can prove that a program has undefined behaviour for some
inputs, then indeed the resulting executable is useless in the "many
fields" that require no UB for any inputs. But that's the programmer's
fault, not the compiler's. It also is a tautology.

In the real world, I doubt compilers care that much about whether a
complete program's behaviour is undefined for some inputs or not.
That's the programmer's problem, not the compiler's, and for some fields
it's not a problem at all. For some fields, the program's input is
under control and the behaviour resulting from an invalid input is not a
concern.

In the real world, an optimizer often can't see the complete program,
and the inferences are more about "this function will never be called
incorrectly" than "this program will never receive an incorrect input"
(where "incorrect" = "leading to UB"). Either way, ensuring that a
program is not useless is the programmer's job, not the compiler's.
Post by s***@casperkitty.com
I fail
to see much value in optimization features that are only effective on
useless programs.
I thought we were talking about optimizations that are based on the
assumption that a program is in fact not useless, and therefore may
cause the behaviour of "useless programs" to be completely unexpected.
I fail to see much value in being concerned about the behaviour of
useless programs.
s***@casperkitty.com
2015-10-12 01:27:09 UTC
Permalink
Raw Message
Post by Wojtek Lerch
Post by s***@casperkitty.com
If one takes the view that it is impossible to know whether a program's
behavior will meet requirements when it performs actions whose behavior is
constrained by neither the C Specification nor platform documentation, that
would imply that for many fields, any useful program must never invoke
Undefined Behavior for any combination of inputs.
For many fields, yes.
Post by s***@casperkitty.com
This would in turn
imply that in all situations where an optimizer would be able to improve
the "efficiency" of a program by making UB-based inferences about the input
data it would receive, the resulting executable would be useless.
That sounds backwards.
If a compiler can prove that a program has undefined behaviour for some
inputs, then indeed the resulting executable is useless in the "many
fields" that require no UB for any inputs. But that's the programmer's
fault, not the compiler's. It also is a tautology.
The design of many implementations has historically guaranteed certain
things about the consequences of actions for which the C Standard imposes
no requirements. In many cases, even extremely loose guarantees were
sufficient to allow programs to meet requirements, and thus code making
use of such guarantees could be more efficient than code which did not
do so.

Unfortunately, the Standards Committee has persistently refused to recognize
some guarantees which were honored by many compilers (or in at least one
case, by their own admission, by 100% of all known compilers for two's-
complement architectures).
Post by Wojtek Lerch
In the real world, I doubt compilers care that much about whether a
complete program's behaviour is undefined for some inputs or not.
That's the programmer's problem, not the compiler's, and for some fields
it's not a problem at all. For some fields, the program's input is
under control and the behaviour resulting from an invalid input is not a
concern.
Indeed, there are some fields where such optimization behavior might be
useful. There's a difference, however, between how compilers which target
specialized fields should be expected to behave, versus "general-purpose"
compilers.
Post by Wojtek Lerch
In the real world, an optimizer often can't see the complete program,
and the inferences are more about "this function will never be called
incorrectly" than "this program will never receive an incorrect input"
(where "incorrect" = "leading to UB"). Either way, ensuring that a
program is not useless is the programmer's job, not the compiler's.
The problem is that there's no standardized means by which a programmer can
be sure that a compiler won't make certain inferences, and there's no longer
any reason to believe that compilers won't try to break code.

Suppose, for example, you want to write a function which accepts an array of
pointers to structures whose first member is an integer, along with two
indices, and reports whether the first is larger than the second. That
could, on many compilers, be written as:

typedef struct { int32_t sort_key; } INT_AND_MORE;
void compare(INT_AND_MORE** arr, int32_t index1, int32_t index2)
{
return *arr[index1) > *arr[index2];
}

and called by typecasting an array of some other kind of pointer to an
INT_AND_MORE**, because all struct pointers are required by the Standard
to have identical representations. Unfortunately, some compilers require
the code to be written as:

typedef struct { int32_t sort_key; } INT_AND_MORE;
void compare(INT_AND_MORE** arr, int32_t index1, int32_t index2)
{
INT_AND_MORE k1,k2;
memcpy(&k1, arr+index1, sizeof k1);
memcpy(&k2, arr+index1, sizeof k2);
return k1 > k2;
}

because if the array contains pointers of some other type (as would be the
normal usage case) reading out such a pointer using a variable of type
INT_AND_MORE** would be Undefined Behavior. Most compilers wouldn't catch
that in most cases, but with aggressive in-lining and whole-program
optimizations there's no way to be sure an optimizer wouldn't use that
ANSI-invented rule as an excuse to break code.

While some compilers may be able to optimize the memcpy operations to yield
the same code as what the first would have yielded on a compiler which
ignores the type punning rules that ANSI invented for C89, I think it would
be more helpful to have a means by which the code can assert that it will
not work on compilers that use those rules, and any compilers using such
rules must refuse compilation outright.
Post by Wojtek Lerch
Post by s***@casperkitty.com
I fail
to see much value in optimization features that are only effective on
useless programs.
I thought we were talking about optimizations that are based on the
assumption that a program is in fact not useless, and therefore may
cause the behaviour of "useless programs" to be completely unexpected.
I fail to see much value in being concerned about the behaviour of
useless programs.
If a program performs an action upon which the Standard imposes no
requirements, but which on 90+% of compilers will yield an effect which
meets requirements, the executable yielded by compiling such a program on
any of those 90% of compilers will be useful.
Wojtek Lerch
2015-10-12 05:11:17 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Wojtek Lerch
Post by s***@casperkitty.com
If one takes the view that it is impossible to know whether a program's
behavior will meet requirements when it performs actions whose behavior is
constrained by neither the C Specification nor platform documentation, that
would imply that for many fields, any useful program must never invoke
Undefined Behavior for any combination of inputs.
For many fields, yes.
Post by s***@casperkitty.com
This would in turn
imply that in all situations where an optimizer would be able to improve
the "efficiency" of a program by making UB-based inferences about the input
data it would receive, the resulting executable would be useless.
That sounds backwards.
If a compiler can prove that a program has undefined behaviour for some
inputs, then indeed the resulting executable is useless in the "many
fields" that require no UB for any inputs. But that's the programmer's
fault, not the compiler's. It also is a tautology.
The design of many implementations has historically guaranteed certain
things about the consequences of actions for which the C Standard imposes
no requirements. In many cases, even extremely loose guarantees were
sufficient to allow programs to meet requirements, and thus code making
use of such guarantees could be more efficient than code which did not
do so.
One of goals of C is to be implementable even on strange and exotic
hardware. Most programs don't need to be able to run on every single
implementation of C, no matter how weird; that's why many programs make
all sort of assumptions that C does not guarantee -- for instance, that
char is precisely 8 bits wide; or that int is precisely 32 bits wide; or
that int is wider than char; or that a pointer can fit into an int; or
that a function pointer can fit into a data pointer; or that int32_t
exists; or that signed integer overflow behaves in the common way. For
each of those assumptions, there are some implementations where it's
false; but a vast number of programs don't care about any of those
implementations.

But there are some programs that do. Do they deserve to lose the status
of valid C programs, just because they're a minority?

The good news is that just because standard C does not make guarantees
about those common assumptions, it doesn't mean that someone else can't.
For instance, POSIX makes some guarantees in addition to what standard
C promises, such as 8-bit char and the ability to represent a function
pointer as a void* (see dlsym()). Nothing prevents other organizations
from coming up with their own sets of strengthened guarantees and
convincing compiler vendors to officially commit to them. And perhaps
also defining a way for programs to verify that the compiler does
provide the additional guarantees, perhaps by using a preprocessor
check. (In fact, many of the assumptions I listed can be verified by a
preprocessor check using standard macros only, without any external help.)
Post by s***@casperkitty.com
Unfortunately, the Standards Committee has persistently refused to recognize
some guarantees which were honored by many compilers (or in at least one
case, by their own admission, by 100% of all known compilers for two's-
complement architectures).
The problem is that adding those guarantees to the standard would make
some implementations non-conforming; worse, it could mean that on some
hardware that has a conforming (albeit weird) implementation today,
suddenly C can't be an available language anymore. That sounds more
like Java's philosophy than C's. C has always had the ambition to be
the new assembler, and I don't think it would be a good idea for it to
abandon exotic hardware, now that most non-exotic hardware is powerful
enough to run Java anyway.

In C, I think it would be good enough if programs had a way to detect
when an implementation doesn't make some of the guarantees that the
program needs to rely on. Personally, I don't think it would be wrong
if the C standard defined a few new macros to indicate a predictable
behaviour of integer overflow, and perhaps several other things that you
would like to have guarantees about. Would that satisfy you too?
Post by s***@casperkitty.com
Post by Wojtek Lerch
In the real world, I doubt compilers care that much about whether a
complete program's behaviour is undefined for some inputs or not.
That's the programmer's problem, not the compiler's, and for some fields
it's not a problem at all. For some fields, the program's input is
under control and the behaviour resulting from an invalid input is not a
concern.
Indeed, there are some fields where such optimization behavior might be
useful. There's a difference, however, between how compilers which target
specialized fields should be expected to behave, versus "general-purpose"
compilers.
That sounds backwards to me again. A "general-purpose" compiler, to me,
is one that aims to be sufficient for all fields, or at least the
majority of fields, including as many of the specialized ones as
reasonably possible. Optimization in general is desirable in pretty
much all fields. If you require a compiler that will guarantee a "sane"
behaviour (in whatever sense of "sane" you feel is fitting) even with
inputs for which the programmer has failed to avoid running into what
the standard C considers undefined behaviour, I would consider *that* a
specialized field.
Post by s***@casperkitty.com
Post by Wojtek Lerch
In the real world, an optimizer often can't see the complete program,
and the inferences are more about "this function will never be called
incorrectly" than "this program will never receive an incorrect input"
(where "incorrect" = "leading to UB"). Either way, ensuring that a
program is not useless is the programmer's job, not the compiler's.
The problem is that there's no standardized means by which a programmer can
be sure that a compiler won't make certain inferences, and there's no longer
any reason to believe that compilers won't try to break code.
Huh? Compilers don't try to break code; it's programmers that write
broken code. If the programmer does his job and makes sure that his
code doesn't invoke undefined behaviour, the compiler will do its job
too, and the code will behave the way the language guarantees it to behave.

[...]
Post by s***@casperkitty.com
Post by Wojtek Lerch
Post by s***@casperkitty.com
I fail
to see much value in optimization features that are only effective on
useless programs.
I thought we were talking about optimizations that are based on the
assumption that a program is in fact not useless, and therefore may
cause the behaviour of "useless programs" to be completely unexpected.
I fail to see much value in being concerned about the behaviour of
useless programs.
If a program performs an action upon which the Standard imposes no
requirements, but which on 90+% of compilers will yield an effect which
meets requirements, the executable yielded by compiling such a program on
any of those 90% of compilers will be useful.
And you think that that's enough of a reason to declare the remaining
10% of compilers broken and non-conforming? Wouldn't it be much better
to give programs a way to detect when a compiler doesn't fall into the
particular 90% set that the programmer cared about, without punishing
those programmers who work with a different set of assumptions and
compilers?
s***@casperkitty.com
2015-10-12 07:04:20 UTC
Permalink
Raw Message
Post by Wojtek Lerch
One of goals of C is to be implementable even on strange and exotic
hardware...
I am fully cognizant of that, perhaps so than most people. I have written
a TCP/IP stack on bare metal for the TMS320C5x which has 16-bit 'char'
values and a few other interesting quirks.
Post by Wojtek Lerch
And perhaps
also defining a way for programs to verify that the compiler does
provide the additional guarantees, perhaps by using a preprocessor
check. (In fact, many of the assumptions I listed can be verified by a
preprocessor check using standard macros only, without any external help.)
That's what I consider long overdue.
Post by Wojtek Lerch
Post by s***@casperkitty.com
Unfortunately, the Standards Committee has persistently refused to recognize
some guarantees which were honored by many compilers (or in at least one
case, by their own admission, by 100% of all known compilers for two's-
complement architectures).
The problem is that adding those guarantees to the standard would make
some implementations non-conforming; worse, it could mean that on some
hardware that has a conforming (albeit weird) implementation today,
suddenly C can't be an available language anymore. That sounds more
like Java's philosophy than C's. C has always had the ambition to be
the new assembler, and I don't think it would be a good idea for it to
abandon exotic hardware, now that most non-exotic hardware is powerful
enough to run Java anyway.
I should have clarified my point--I didn't mean to ask that all compilers
be required to guarantee such behaviors--merely that there be a means by
which every compiler can be obliged to, at its option, either guarantee
some particular behavior or else refuse to do so.
Post by Wojtek Lerch
In C, I think it would be good enough if programs had a way to detect
when an implementation doesn't make some of the guarantees that the
program needs to rely on. Personally, I don't think it would be wrong
if the C standard defined a few new macros to indicate a predictable
behaviour of integer overflow, and perhaps several other things that you
would like to have guarantees about. Would that satisfy you too?
That's basically what I'd like Universal eXtended C to be. I didn't post
an example on this thread, but I've mentioned the idea more on a thread
called "New Directions". While there are a few ways things could be done,
and I'm not sure what the best would be, one approach would merely add the
following requirements to a compiler:

1. Have a file called "<uxcloc.h>", and refrain from putting in it anything
contrary to the UXC specifications (an file containing nothing but a single
newline would meet requirements).

2. Refrain from using any identifier starting with __UXC or __uxc in any
fashion contrary to the UXC specifications.

It would be more helpful, of course, if a compiler contained definitions in
uxcloc.h which would indicate that it can offer guarantees beyond the bare
minimum required by the C Standard, but UXC compliance would not require that
a compiler do anything except provide a means of asking what guarantees it
will uphold.

[Note: For UXC to be convenient and flexible, programs would need to include
a header file corresponding to the version of UXC they need to use; that file
would include <uxcloc.h> and then supply defaults for any macros not defined
in the compiler's file. A compiler which is compliant with an old version of
UXC would not need to be modified to use programs written for a newer version
if the programs contained a copy of the "uxc.h" file for the standard they
wished to use.

For example, if the first version of UXC didn't distinguish between the
behavior of x<<N with N less than 256 from the behavior with N greater
than 255, but some processors made a distinction and some code could benefit
from it, a newer "uxc.h" file could check if <uxcloc.h> defines the macro
describing oversized shifts, but not the one describing oversized shifts
that are below 256, and if so define the latter in terms of the former.
Post by Wojtek Lerch
That sounds backwards to me again. A "general-purpose" compiler, to me,
is one that aims to be sufficient for all fields, or at least the
majority of fields, including as many of the specialized ones as
reasonably possible. Optimization in general is desirable in pretty
much all fields. If you require a compiler that will guarantee a "sane"
behaviour (in whatever sense of "sane" you feel is fitting) even with
inputs for which the programmer has failed to avoid running into what
the standard C considers undefined behaviour, I would consider *that* a
specialized field.
Many programs may receive data from untrusted sources; in today's widely
connected universe, I would consider that possibility the norm rather
than the exception. People who both (1) are willing to ensure that their
programs will never receive data from untrustworthy sources, and (2) need
maximum performance, could enable optimizations which would be dangerous
if programs were receiving data from untrustworthy sources, and would be
unnecessary if maximum performance weren't required. I would consider
a safe default better than a dangerous one.
Post by Wojtek Lerch
Post by s***@casperkitty.com
The problem is that there's no standardized means by which a programmer can
be sure that a compiler won't make certain inferences, and there's no longer
any reason to believe that compilers won't try to break code.
Huh? Compilers don't try to break code; it's programmers that write
broken code. If the programmer does his job and makes sure that his
code doesn't invoke undefined behaviour, the compiler will do its job
too, and the code will behave the way the language guarantees it to behave.
Historically, compilers were expected to avoid replacing Non-Critical
Undefined Behavior (see Annex L) with Critical Undefined Behavior. Many
would insert extra instructions for that purpose, even when not required
to do so by the Standard. For example, the 8x51 and PIC compilers I have
used, given:

uint8_t a,b; ...
a<<=1;
b<<=1;

will insert a "clear carry" instruction before the second shift instruction,
rather than letting the most significant bit of "a" propagate into the
least significant bit of "b". Nothing in the C89 or subsequent standards
mandates such behavior, but the makers of the compilers did not think that
a left-shift of a negative value should behave as Critical Undefined
Behavior.
Post by Wojtek Lerch
Post by s***@casperkitty.com
If a program performs an action upon which the Standard imposes no
requirements, but which on 90+% of compilers will yield an effect which
meets requirements, the executable yielded by compiling such a program on
any of those 90% of compilers will be useful.
And you think that that's enough of a reason to declare the remaining
10% of compilers broken and non-conforming? Wouldn't it be much better
to give programs a way to detect when a compiler doesn't fall into the
particular 90% set that the programmer cared about, without punishing
those programmers who work with a different set of assumptions and
compilers?
What I want is not to require that all compilers support all behaviors
common to the 90%, but merely that there be a means by which every compiler
(whether in the 90% or the 10%) can be asked if it supports certain features
and guarantees, and that any compiler which fails to answer negatively about
features or guarantees it does not support would be non-conforming regardless
of whether the feature or guarantee would otherwise be required.
Wojtek Lerch
2015-10-13 03:42:35 UTC
Permalink
Raw Message
...
Post by s***@casperkitty.com
Post by Wojtek Lerch
In C, I think it would be good enough if programs had a way to detect
when an implementation doesn't make some of the guarantees that the
program needs to rely on. Personally, I don't think it would be wrong
if the C standard defined a few new macros to indicate a predictable
behaviour of integer overflow, and perhaps several other things that you
would like to have guarantees about. Would that satisfy you too?
That's basically what I'd like Universal eXtended C to be. I didn't post
an example on this thread, but I've mentioned the idea more on a thread
called "New Directions".
Okay, that sounds reasonable. Couldn't that be started as an open
project, perhaps sponsored by some organization that maintains programs
that run on many different implementations, and might find your project
useful? The initial implementation could consist of a list of ifdefs to
recognize compilers that people have contributed the details for, with a
fallback to a safe set of defaults. If becomes popular enough, maybe
the community could convince compiler vendors to provide official
versions of the header, and then maybe get it included in the next
version of C?

...
Post by s***@casperkitty.com
Post by Wojtek Lerch
That sounds backwards to me again. A "general-purpose" compiler, to me,
is one that aims to be sufficient for all fields, or at least the
majority of fields, including as many of the specialized ones as
reasonably possible. Optimization in general is desirable in pretty
much all fields. If you require a compiler that will guarantee a "sane"
behaviour (in whatever sense of "sane" you feel is fitting) even with
inputs for which the programmer has failed to avoid running into what
the standard C considers undefined behaviour, I would consider *that* a
specialized field.
Many programs may receive data from untrusted sources; in today's widely
connected universe, I would consider that possibility the norm rather
than the exception.
Yes, but is it the norm to let programs invoke undefined behaviour on
bad data, and expect that the compiler will handle that in a "nice" way?
I hope not. In my world, the norm is to write code that does not
invoke undefined behaviour, no matter how bad the input data is. If I
make a mistake and my code does invoke undefined behaviour, I don't want
it to behave in a "sane" way -- I want it to crash and give me a core
file to debug.
Post by s***@casperkitty.com
People who both (1) are willing to ensure that their
programs will never receive data from untrustworthy sources, and (2) need
maximum performance, could enable optimizations which would be dangerous
if programs were receiving data from untrustworthy sources, and would be
unnecessary if maximum performance weren't required. I would consider
a safe default better than a dangerous one.
But this isn't about complete programs; compilers usually see only a
fragment of a program at a time. Do all functions in a C program
receive their arguments from an untrustworthy source? Not in my
programs, not even in those that can't trust their inputs. People who
don't care about the speed or size of their executables but do want them
to react predictably to undefined behaviour can disable all optimizations...
Post by s***@casperkitty.com
Post by Wojtek Lerch
Post by s***@casperkitty.com
The problem is that there's no standardized means by which a programmer can
be sure that a compiler won't make certain inferences, and there's no longer
any reason to believe that compilers won't try to break code.
Huh? Compilers don't try to break code; it's programmers that write
broken code. If the programmer does his job and makes sure that his
code doesn't invoke undefined behaviour, the compiler will do its job
too, and the code will behave the way the language guarantees it to behave.
Historically, compilers were expected to avoid replacing Non-Critical
Undefined Behavior (see Annex L) with Critical Undefined Behavior.
Those sound like useful concepts; I'll have to look them up before I can
say more about them.
s***@casperkitty.com
2015-10-13 07:21:13 UTC
Permalink
Raw Message
Post by Wojtek Lerch
Post by s***@casperkitty.com
That's basically what I'd like Universal eXtended C to be. I didn't post
an example on this thread, but I've mentioned the idea more on a thread
called "New Directions".
Okay, that sounds reasonable. Couldn't that be started as an open
project, perhaps sponsored by some organization that maintains programs
that run on many different implementations, and might find your project
useful? The initial implementation could consist of a list of ifdefs to
recognize compilers that people have contributed the details for, with a
fallback to a safe set of defaults. If becomes popular enough, maybe
the community could convince compiler vendors to provide official
versions of the header, and then maybe get it included in the next
version of C?
Would you like to help me figure out how best to start such a thing?

Do you know if gcc provides a way of letting the preprocessor know what compile-time options are in effect? Much of the usefulness would come
from the ability to have programs squawk if the compiler is invoked
without specifying the required options.
Post by Wojtek Lerch
Yes, but is it the norm to let programs invoke undefined behaviour on
bad data, and expect that the compiler will handle that in a "nice" way?
I hope not. In my world, the norm is to write code that does not
invoke undefined behaviour, no matter how bad the input data is. If I
make a mistake and my code does invoke undefined behaviour, I don't want
it to behave in a "sane" way -- I want it to crash and give me a core
file to debug.
There are a lot of cases where it makes sense for a program which takes
input from an untrustworthy source to have functions whose behavior is
specified as, e.g.

int64_t calc(int32_t v1, int32_t v2, int64_t v3);

// If v1*v2 is representable as int32_t and v1*v2+v3 is representable
// as int64, return v1*v2+v3; otherwise return any number within the
// range of an int64.

On platforms which perform uint32_t to int32_t casting in the usual
fashion, there would be two ways to write the function so as to avoid
any behavior not specified by the C Standard:

return (int64_t)(1u*v1*v2+(uint64_t)v3);

or
return (int64_t)((uint64_t)v1*v2+v3);

On some platforms, the first form will be much more efficient (e.g. the
ARM Cortex-M0 has a fast 32x32->32 multiply instruction, but no 32x32->64
multiply instruction, so requiring that the product be computed as 64 bits
would be expensive. On some other platforms like x86 or x64, however, the
second form would be more efficient since it would be cheaper to use the
upper 32 bits supplied by the multiply instruction than to sign-extend the
lower 32 bits.

In the event that either behavior would be equally acceptable, I would
suggest that writing the code as:

__UXC_REQUIRE(__UXC_INT_OVERFLOW(), __UXC_PARTIAL_INDETERMINATE_VALUE)
__UXC_REQUIRE(__UXC_OVERSIZE_INT_CAST(), __UXC_MOD_CLIP)

return (int64_t)(v1*v2+v3);

would allow the compiler to implement the code in whatever fashion would be
most efficient in the non-overflow case while guaranteeing that the code
would have no side effects beyond returning an arbitrary value in the
non-overflow case. [One thing I'd allow code to specify as a requirement
which I think would increase the amount of freedom they could afford to
give compilers generally would be that expressions which overflow may yield
numbers outside the range of their type, but an explicit cast to an integer
type must perform two's-complement reduction into that type's range.
Post by Wojtek Lerch
But this isn't about complete programs; compilers usually see only a
fragment of a program at a time. Do all functions in a C program
receive their arguments from an untrustworthy source? Not in my
programs, not even in those that can't trust their inputs. People who
don't care about the speed or size of their executables but do want them
to react predictably to undefined behaviour can disable all optimizations...
I would suggest that in many cases, being able to safely say "I need the
compiler to abide by certain constraints in case of overflow" and then let
overflows happen will allow many more opportunities for optimization than
could be achieved if the programmer had to select exactly what should happen
in case of overflow. Further, code which tries to preemptively deal with
overflow is often tricky, hard to read, and hard to validate. Letting the
programmer focus on the interesting cases and let the compiler worry about
the overflow case would seem much more useful.
Post by Wojtek Lerch
Post by s***@casperkitty.com
Historically, compilers were expected to avoid replacing Non-Critical
Undefined Behavior (see Annex L) with Critical Undefined Behavior.
Those sound like useful concepts; I'll have to look them up before I can
say more about them.
I think Annex L is a great concept, but unfortunately it (IMHO) leaves
ambiguous the question of whether the following code would be safe on a
platform that claims analyzability:

int dat[1000];
int maybesafe(int x)
{
if (x < 0) return 1;
x++;
if (x >= 1000) return 2;
if (x < 0) return 3;
return dat[x];
}

On a system where integers are defined as wrapping, the code would be safe.
It would also be safe, and more efficient, if the system stored x in a
way that could hold values larger than "int" without overflowing, since
that would allow the third if-check to be eliminated while still avoiding
any errant access to "dat".

Unfortunately, it's not clear that analyzability implies that code would be
required to have the result of the increment behave consistently as a large
positive number or as a negative number. Under a loose integer-overflow
model, it would be legitimate for a compiler to regard the result of the
overflowed arithmetic as +2147483648 when comparing to zero, but as
-2147483648 when comparing against 1000; it's unclear whether Annex L would
forbid that model.
Wojtek Lerch
2015-10-14 03:20:16 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Wojtek Lerch
Post by s***@casperkitty.com
That's basically what I'd like Universal eXtended C to be. I didn't post
an example on this thread, but I've mentioned the idea more on a thread
called "New Directions".
Okay, that sounds reasonable. Couldn't that be started as an open
project, perhaps sponsored by some organization that maintains programs
that run on many different implementations, and might find your project
useful? The initial implementation could consist of a list of ifdefs to
recognize compilers that people have contributed the details for, with a
fallback to a safe set of defaults. If becomes popular enough, maybe
the community could convince compiler vendors to provide official
versions of the header, and then maybe get it included in the next
version of C?
Would you like to help me figure out how best to start such a thing?
Sorry, that's not really anywhere near my area of expertise. Besides,
you haven't convinced me yet that it would be worth the effort. :)
Post by s***@casperkitty.com
Do you know if gcc provides a way of letting the preprocessor know what compile-time options are in effect?
I doubt it, but there's a lot I don't know about gcc.
Post by s***@casperkitty.com
Post by Wojtek Lerch
Yes, but is it the norm to let programs invoke undefined behaviour on
bad data, and expect that the compiler will handle that in a "nice" way?
I hope not. In my world, the norm is to write code that does not
invoke undefined behaviour, no matter how bad the input data is. If I
make a mistake and my code does invoke undefined behaviour, I don't want
it to behave in a "sane" way -- I want it to crash and give me a core
file to debug.
There are a lot of cases where it makes sense for a program which takes
input from an untrustworthy source to have functions whose behavior is
specified as
...

I'm not entirely sure how you meant your example to be extrapolated --
did you mean to propose that every function in such a program should be
written in such a way that it might produce an "unspecified" value for
some invalid arguments but could never invoke undefined behaviour, no
matter how insanely invalid the arguments are, and no matter whether
there's code in the program that has a remote chance of calling the
function that way? Do you actually follow such a rule in the real life?

...
Post by s***@casperkitty.com
Post by Wojtek Lerch
But this isn't about complete programs; compilers usually see only a
fragment of a program at a time. Do all functions in a C program
receive their arguments from an untrustworthy source? Not in my
programs, not even in those that can't trust their inputs. People who
don't care about the speed or size of their executables but do want them
to react predictably to undefined behaviour can disable all optimizations...
I would suggest that in many cases, being able to safely say "I need the
compiler to abide by certain constraints in case of overflow" and then let
overflows happen will allow many more opportunities for optimization than
could be achieved if the programmer had to select exactly what should happen
in case of overflow. Further, code which tries to preemptively deal with
overflow is often tricky, hard to read, and hard to validate. Letting the
programmer focus on the interesting cases and let the compiler worry about
the overflow case would seem much more useful.
Yeah, I wouldn't be against having additional facilities, such as
predefined preprocessor macros, to let programs recognize
implementations that deal with certain undefined behaviours in certain
predictable and potentially useful way. But I wouldn't expect it to
become part of the standard before it becomes existing practice.
s***@casperkitty.com
2015-10-14 05:46:56 UTC
Permalink
Raw Message
Post by Wojtek Lerch
I'm not entirely sure how you meant your example to be extrapolated --
did you mean to propose that every function in such a program should be
written in such a way that it might produce an "unspecified" value for
some invalid arguments but could never invoke undefined behaviour, no
matter how insanely invalid the arguments are, and no matter whether
there's code in the program that has a remote chance of calling the
function that way? Do you actually follow such a rule in the real life?
If a routine is supposed to perform a computation without side-effects, then
the existence of possible input conditions which would result in side-effects
will make analysis of the code and how it fits into other operations more
complicated. Being able to say that a piece of code will never have
any adverse side-effects no matter what inputs it receives makes analysis
much simpler.
Keith Thompson
2015-10-12 14:51:50 UTC
Permalink
Raw Message
Wojtek Lerch <***@yahoo.ca> writes:
[...]
Post by Wojtek Lerch
One of goals of C is to be implementable even on strange and exotic
hardware. Most programs don't need to be able to run on every single
implementation of C, no matter how weird; that's why many programs make
all sort of assumptions that C does not guarantee -- for instance, that
char is precisely 8 bits wide; or that int is precisely 32 bits wide; or
that int is wider than char; or that a pointer can fit into an int; or
that a function pointer can fit into a data pointer; or that int32_t
exists; or that signed integer overflow behaves in the common way. For
each of those assumptions, there are some implementations where it's
false; but a vast number of programs don't care about any of those
implementations.
A quibble: Assuming that a pointer can fit into an int is both dangerous
(it's not true on modern 64-bit systems) and unnecessary, since we have
intptr_t and uintptr_t.
Post by Wojtek Lerch
But there are some programs that do. Do they deserve to lose the status
of valid C programs, just because they're a minority?
[...]
Post by Wojtek Lerch
For instance, POSIX makes some guarantees in addition to what standard
C promises, such as 8-bit char and the ability to represent a function
pointer as a void* (see dlsym()).
POSIX does require CHAR_BIT==8, but I don't believe it guarantees that a
function pointer can be converted to void* and back again without loss
of information. As I recall, an earlier version of POSIX did have that
requirement, but it currently only requires that a void* pointer
*returned by dlsym()* can be converted to the appropriate
pointer-to-function type.
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
s***@casperkitty.com
2015-10-12 15:37:18 UTC
Permalink
Raw Message
Post by Keith Thompson
... Most programs don't need to be able to run on every single
implementation of C, no matter how weird; that's why many programs make
all sort of assumptions that C does not guarantee -- for instance, that
char is precisely 8 bits wide; or that int is precisely 32 bits wide; or
that int is wider than char; or that a pointer can fit into an int; or
that a function pointer can fit into a data pointer; or that int32_t
exists; or that signed integer overflow behaves in the common way.
A quibble: Assuming that a pointer can fit into an int is both dangerous
(it's not true on modern 64-bit systems) and unnecessary, since we have
intptr_t and uintptr_t.
I think the sentence would have been better worded as "Assuming a pointer
has a representation compatible with some integer type", but even that
would be an unwarranted assumption on some systems which have a uintptr_t
Many systems will have a uintptr_t type which is larger than its pointer
type and some will have one that's smaller [systems which don't have a
uintptr_t type would be less of a concern, since there's no danger of code
which expects such a type to exist malfunctioning on a platform which does
not define it].
Post by Keith Thompson
POSIX does require CHAR_BIT==8, but I don't believe it guarantees that a
function pointer can be converted to void* and back again without loss
of information. As I recall, an earlier version of POSIX did have that
requirement, but it currently only requires that a void* pointer
*returned by dlsym()* can be converted to the appropriate
pointer-to-function type.
I think it would be helpful if there were a standard-defined means by which
code could ask when such conversions will be necessary. I understand that
there are some systems where, for various technical reasons, they will be
required, but in cases where it is *unlikely* that a piece of code will ever
need to be ported to such systems I think it would be helpful to have a
standard directive code could use which would say "This code is written for
systems which allow round-trip conversions between function pointers and
data pointers using an arbitrary mixture of type punning and type casting;
any compiler which do not allow that must refuse compilation". Such a
directive would ensure that in the event that there is a later need to
port code to such a system, the issue will be noticed and addressed, but in
the more-probable scenario that such porting is never required programmers
won't have wasted time on writing unnecessary dlsym() calls.
Keith Thompson
2015-10-12 18:47:36 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Keith Thompson
... Most programs don't need to be able to run on every single
implementation of C, no matter how weird; that's why many programs make
all sort of assumptions that C does not guarantee -- for instance, that
char is precisely 8 bits wide; or that int is precisely 32 bits wide; or
that int is wider than char; or that a pointer can fit into an int; or
that a function pointer can fit into a data pointer; or that int32_t
exists; or that signed integer overflow behaves in the common way.
A quibble: Assuming that a pointer can fit into an int is both dangerous
(it's not true on modern 64-bit systems) and unnecessary, since we have
intptr_t and uintptr_t.
I think the sentence would have been better worded as "Assuming a pointer
has a representation compatible with some integer type", but even that
would be an unwarranted assumption on some systems which have a uintptr_t
Many systems will have a uintptr_t type which is larger than its pointer
type and some will have one that's smaller [systems which don't have a
uintptr_t type would be less of a concern, since there's no danger of code
which expects such a type to exist malfunctioning on a platform which does
not define it].
I think it would be better phrased as "uintptr_t exists".

I doubt that many systems will make uintptr_t bigger than void*; there's
rarely a good reason to do so. If void* is 32 or 64 bits, uintptr_t
will typically be 32 or 64 bits, respectively.

uintptr_t can only be smaller than void* if void* has extra bits that
don't contribute to its value, which also seems unlikely.

The standard guarantees that converting a void* value to uintptr_t and
back to void* yields a value that compares equal to the original
pointer. The most straightfoward way to implement that is to use an
integer type that's the same size as void* (some exotic systems might
have to do something else). And if that guarantee can't be made, then
the implementation won't provide uintptr_t.
Post by s***@casperkitty.com
Post by Keith Thompson
POSIX does require CHAR_BIT==8, but I don't believe it guarantees that a
function pointer can be converted to void* and back again without loss
of information. As I recall, an earlier version of POSIX did have that
requirement, but it currently only requires that a void* pointer
*returned by dlsym()* can be converted to the appropriate
pointer-to-function type.
I think it would be helpful if there were a standard-defined means by which
code could ask when such conversions will be necessary.
Perhaps I'm misunderstanding you, because there such conversions are
*always* necessary. dlsym() returns a void*. If it refers to a
function, you have to convert it to a pointer-to-function type before
you can use it.
Post by s***@casperkitty.com
I understand that
there are some systems where, for various technical reasons, they will be
required, but in cases where it is *unlikely* that a piece of code will ever
need to be ported to such systems I think it would be helpful to have a
standard directive code could use which would say "This code is written for
systems which allow round-trip conversions between function pointers and
data pointers using an arbitrary mixture of type punning and type casting;
any compiler which do not allow that must refuse compilation". Such a
directive would ensure that in the event that there is a later need to
port code to such a system, the issue will be noticed and addressed, but in
the more-probable scenario that such porting is never required programmers
won't have wasted time on writing unnecessary dlsym() calls.
What does calling dlsym() have to do with whether such pointer
conversions are allowed in general? dlsym() takes a handle (returned by
dlopen() and a name, and returns a pointer to the named entity. What
(not quite 100% portable) alternative to dlsym() do you think exists?
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
s***@casperkitty.com
2015-10-12 20:14:28 UTC
Permalink
Raw Message
Post by Keith Thompson
Post by s***@casperkitty.com
I think the sentence would have been better worded as "Assuming a pointer
has a representation compatible with some integer type"...
I think it would be better phrased as "uintptr_t exists".
The assumption goes back before there was such a thing as uintptr_t.
Post by Keith Thompson
I doubt that many systems will make uintptr_t bigger than void*; there's
rarely a good reason to do so. If void* is 32 or 64 bits, uintptr_t
will typically be 32 or 64 bits, respectively.
I know of systems with three-byte and six-byte pointers that do not have
24-bit or 48-bit integer types.
Post by Keith Thompson
uintptr_t can only be smaller than void* if void* has extra bits that
don't contribute to its value, which also seems unlikely.
Some implementations have a lot of padding bits in their pointer type,
especially if the same CPU core may be used on a machine which has 16K of
memory or 16MiB of memory. I don't know of any compilers whose uintptr_t
type is optimized to exploit that, but such a thing could plausibly and
usefully exist.
Post by Keith Thompson
The standard guarantees that converting a void* value to uintptr_t and
back to void* yields a value that compares equal to the original
pointer. The most straightfoward way to implement that is to use an
integer type that's the same size as void* (some exotic systems might
have to do something else). And if that guarantee can't be made, then
the implementation won't provide uintptr_t.
That is certainly the most common approach.
Post by Keith Thompson
Perhaps I'm misunderstanding you, because there such conversions are
*always* necessary. dlsym() returns a void*. If it refers to a
function, you have to convert it to a pointer-to-function type before
you can use it.
I'm not familiar with dlsym() in particular, but in the days where it was
necessary to support interaction between 16-bit and 32-bit code, Windows
would require that code invoking something that might either be a 16-bit
or 32-bit function would need to pass a pointer to the function to a system
routine that would either return the passed-in pointer (if it was a 32-bit
method) or return a new object with some 32-bit code that would set things
up to call the 16-bit code. When code was done using the thunk, it was
then expected to call a "release" function, which would either do nothing
if given a pointer to a "real" 32-bit method, or release the memory which
was allocated for the thunk if it was pointing to a newly-constructed
interface object.

On a modern system, code which takes a function pointer, calls the function
to construct a thunk, invokes the thunk, and calls the function to release
the thunk will work, but the functions to construct and delete thunks no
longer do anything. The brief bit you said about dlsym() made it sound
like a similar concept, but perhaps I misinterpreted you.
Keith Thompson
2015-10-12 22:46:22 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Keith Thompson
Post by s***@casperkitty.com
I think the sentence would have been better worded as "Assuming a pointer
has a representation compatible with some integer type"...
I think it would be better phrased as "uintptr_t exists".
The assumption goes back before there was such a thing as uintptr_t.
Those days are gone (except perhaps for some old compilers that don't
conform to C99 or later).
Post by s***@casperkitty.com
Post by Keith Thompson
I doubt that many systems will make uintptr_t bigger than void*; there's
rarely a good reason to do so. If void* is 32 or 64 bits, uintptr_t
will typically be 32 or 64 bits, respectively.
I know of systems with three-byte and six-byte pointers that do not have
24-bit or 48-bit integer types.
I knew it was possible for uintptr_t to be bigger than void*.
Apparently there actually are such systems. But I still doubt that
there are many of them, which is what you said.
Post by s***@casperkitty.com
Post by Keith Thompson
uintptr_t can only be smaller than void* if void* has extra bits that
don't contribute to its value, which also seems unlikely.
Some implementations have a lot of padding bits in their pointer type,
especially if the same CPU core may be used on a machine which has 16K of
memory or 16MiB of memory. I don't know of any compilers whose uintptr_t
type is optimized to exploit that, but such a thing could plausibly and
usefully exist.
Sure, it's possible. But in any case, I'm not sure what real difference
it makes. Personally, I'd just use uintptr_t and not worry about its
size.
Post by s***@casperkitty.com
Post by Keith Thompson
The standard guarantees that converting a void* value to uintptr_t and
back to void* yields a value that compares equal to the original
pointer. The most straightfoward way to implement that is to use an
integer type that's the same size as void* (some exotic systems might
have to do something else). And if that guarantee can't be made, then
the implementation won't provide uintptr_t.
That is certainly the most common approach.
Post by Keith Thompson
Perhaps I'm misunderstanding you, because there such conversions are
*always* necessary. dlsym() returns a void*. If it refers to a
function, you have to convert it to a pointer-to-function type before
you can use it.
I'm not familiar with dlsym() in particular, but in the days where it was
necessary to support interaction between 16-bit and 32-bit code, Windows
would require that code invoking something that might either be a 16-bit
or 32-bit function would need to pass a pointer to the function to a system
routine that would either return the passed-in pointer (if it was a 32-bit
method) or return a new object with some 32-bit code that would set things
up to call the 16-bit code. When code was done using the thunk, it was
then expected to call a "release" function, which would either do nothing
if given a pointer to a "real" 32-bit method, or release the memory which
was allocated for the thunk if it was pointing to a newly-constructed
interface object.
Ok. That doesn't sound at all like what I thought we were talking about.
Post by s***@casperkitty.com
On a modern system, code which takes a function pointer, calls the function
to construct a thunk, invokes the thunk, and calls the function to release
the thunk will work, but the functions to construct and delete thunks no
longer do anything. The brief bit you said about dlsym() made it sound
like a similar concept, but perhaps I misinterpreted you.
dlsym returns a pointer (to an object or function) given a symbol name.
It doesn't start with an existing pointer to the object or function.

http://pubs.opengroup.org/onlinepubs/9699919799/functions/dlsym.html
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
s***@casperkitty.com
2015-10-12 22:54:58 UTC
Permalink
Raw Message
Post by Keith Thompson
Post by s***@casperkitty.com
I know of systems with three-byte and six-byte pointers that do not have
24-bit or 48-bit integer types.
I knew it was possible for uintptr_t to be bigger than void*.
Apparently there actually are such systems. But I still doubt that
there are many of them, which is what you said.
In the embedded world, there are a fair number of popular 8-bit platforms
which use an address space larger than 64K but smaller than 16MB. There
would be no benefit to using a 32-bit pointer type, and using a 24-bit type
causes no alignment difficulties.

On the Intel 80386, pointers used to contain a 16-bit segment and 32-bit
offset. A lot of software found that it was most convenient to just use
one segment for everything and thus ignores the segment register, though
system-level code sometimes had to worry about segments when copying
data from one process' address space to another's. I would guess that at
some point it became pretty normal to pad the pointers out to 64 bits for
alignment purposes, but from a hardware standpoint the pointers were 48
bits (and I think in x86, from the processor's point of view, they still
are).
Post by Keith Thompson
Ok. That doesn't sound at all like what I thought we were talking about.
Hence the confusion. Sorry 'bout that.
Philip Lantz
2015-10-13 05:52:51 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
On the Intel 80386, pointers used to contain a 16-bit segment and 32-bit
offset. A lot of software found that it was most convenient to just use
one segment for everything and thus ignores the segment register, though
system-level code sometimes had to worry about segments when copying
data from one process' address space to another's. I would guess that at
some point it became pretty normal to pad the pointers out to 64 bits for
alignment purposes,
I don't believe this has ever been normal.
Post by s***@casperkitty.com
but from a hardware standpoint the pointers were 48
bits (and I think in x86, from the processor's point of view, they still
are).
They are. And 80 bits in long mode.
Hans-Bernhard Bröker
2015-10-13 17:09:39 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
On the Intel 80386, pointers used to contain a 16-bit segment and 32-bit
offset.
Not really. You're mixing that up with 16-bit x86, which really did use
16-bit "segment" plus 16 bit "offset", which would combine into a 20-bit
real address in a somewhat silly fashion.

In theory, a full pointer for 32-bit x86 would have needed a 16-bit
selector (not the same as a segment) plus a 32-bit pointer, but in
practice, this was used so rarely that one might as well forget this
possibility even existed. 32-bit x86 used the "flat" memory model
almost exclusively, so pointers never used to be anything but the 32-bit
offset from the segment start address.
Post by s***@casperkitty.com
I would guess that at some point it became pretty normal to pad the
pointers out to 64 bits for alignment purposes,
I'm pretty such a guess of yours would be incorrect.

Because those extra 16 bits have an entirely different meaning from the
plain 32 bit address component, merging the two into some kind of 48-bit
or 64-bit number would have been blatantly foolish. The selector is
used for lookup in the segment descriptor table, only. It is never
combined with the address to form some kind of "48-bit huge pointer"
number. There is no relation whatsoever between e.g. 0x0003::0xFFFFFFFF
and 0x0004::0x00000000, so pretending the two came from some unified
48-bit number space would be FUBAR.
Post by s***@casperkitty.com
but from a hardware standpoint the pointers were 48
bits (and I think in x86, from the processor's point of view, they still
are).
You think incorrectly there. While there are indeed 48-bit addresses
somewhere in a 32-bit x86 CPU, from the running machine code's
point-of-view they essentially don't exist. They're purely used to
configure the MMU (page tables, segment descriptor tables), and
non-privileged code doesn't even get to see those. The kind of code
we're talking about here, i.e. what could conceivably come out of the C
compiler, uses nothing but 32-bit addressing.
s***@casperkitty.com
2015-10-13 20:06:49 UTC
Permalink
Raw Message
Post by Hans-Bernhard Bröker
Post by s***@casperkitty.com
On the Intel 80386, pointers used to contain a 16-bit segment and 32-bit
offset.
Not really. You're mixing that up with 16-bit x86, which really did use
16-bit "segment" plus 16 bit "offset", which would combine into a 20-bit
real address in a somewhat silly fashion.
In theory, a full pointer for 32-bit x86 would have needed a 16-bit
selector (not the same as a segment) plus a 32-bit pointer, but in
practice, this was used so rarely that one might as well forget this
possibility even existed. 32-bit x86 used the "flat" memory model
almost exclusively, so pointers never used to be anything but the 32-bit
offset from the segment start address.
Intel's documentation for the 80386 expected that people would make a lot
more use of segments than they ever did. Something like LDS or LES,
however, fetches a 48-bit value.
Post by Hans-Bernhard Bröker
Post by s***@casperkitty.com
I would guess that at some point it became pretty normal to pad the
pointers out to 64 bits for alignment purposes,
I'm pretty such a guess of yours would be incorrect.
Because those extra 16 bits have an entirely different meaning from the
plain 32 bit address component, merging the two into some kind of 48-bit
or 64-bit number would have been blatantly foolish. The selector is
used for lookup in the segment descriptor table, only. It is never
combined with the address to form some kind of "48-bit huge pointer"
number. There is no relation whatsoever between e.g. 0x0003::0xFFFFFFFF
and 0x0004::0x00000000, so pretending the two came from some unified
48-bit number space would be FUBAR.
Nothing about the existence of uintptr_t implies linear addressing.
Compilers for the 8086 allowed seg:offset pointers to be cast to unsigned
long, with the upper word receiving the segment part and the lower word
containing the offset, and such casts were often useful even though doing arithmetic on the resulting values would generally not be useful.

For example, a structure might contain a "type" field, along with a "data"
field that depending upon the type might represent a 32-bit number or a
pointer to more data. Using an integer type for both purposes may in
some cases be more convenient than using a union.
Post by Hans-Bernhard Bröker
You think incorrectly there. While there are indeed 48-bit addresses
somewhere in a 32-bit x86 CPU, from the running machine code's
point-of-view they essentially don't exist. They're purely used to
configure the MMU (page tables, segment descriptor tables), and
non-privileged code doesn't even get to see those. The kind of code
we're talking about here, i.e. what could conceivably come out of the C
compiler, uses nothing but 32-bit addressing.
When did "LDS" cease to be a user-mode instruction? It's entirely possible
that the OS might set the length of the segment descriptor table to 1, in
which case code wouldn't exactly have a huge variety of segments to choose
from, but unless something has changed LDS expects to fetch a 48-bit
seg+offset pointer.
Philip Lantz
2015-10-14 06:38:54 UTC
Permalink
Raw Message
Post by Hans-Bernhard Bröker
Post by s***@casperkitty.com
On the Intel 80386, pointers used to contain a 16-bit segment and 32-bit
offset.
Not really. You're mixing that up with 16-bit x86, which really did use
16-bit "segment" plus 16 bit "offset", which would combine into a 20-bit
real address in a somewhat silly fashion.
In theory, a full pointer for 32-bit x86 would have needed a 16-bit
selector (not the same as a segment) plus a 32-bit pointer, but in
practice, this was used so rarely that one might as well forget this
possibility even existed. 32-bit x86 used the "flat" memory model
almost exclusively, so pointers never used to be anything but the 32-bit
offset from the segment start address.
Post by s***@casperkitty.com
I would guess that at some point it became pretty normal to pad the
pointers out to 64 bits for alignment purposes,
I'm pretty such a guess of yours would be incorrect.
Because those extra 16 bits have an entirely different meaning from the
plain 32 bit address component, merging the two into some kind of 48-bit
or 64-bit number would have been blatantly foolish. The selector is
used for lookup in the segment descriptor table, only. It is never
combined with the address to form some kind of "48-bit huge pointer"
number. There is no relation whatsoever between e.g. 0x0003::0xFFFFFFFF
and 0x0004::0x00000000, so pretending the two came from some unified
48-bit number space would be FUBAR.
Post by s***@casperkitty.com
but from a hardware standpoint the pointers were 48
bits (and I think in x86, from the processor's point of view, they still
are).
You think incorrectly there. While there are indeed 48-bit addresses
somewhere in a 32-bit x86 CPU, from the running machine code's
point-of-view they essentially don't exist. They're purely used to
configure the MMU (page tables, segment descriptor tables), and
non-privileged code doesn't even get to see those. The kind of code
we're talking about here, i.e. what could conceivably come out of the C
compiler, uses nothing but 32-bit addressing.
Until I got to your last sentence, I was about to retort that the x86
certainly does have 48 (and 80) bit pointers. See, for example, the call
instruction. But you're right, that no code that uses such instructions
would come out of a modern C compiler.
Wojtek Lerch
2015-10-13 03:44:14 UTC
Permalink
Raw Message
Post by Keith Thompson
[...]
Post by Wojtek Lerch
One of goals of C is to be implementable even on strange and exotic
hardware. Most programs don't need to be able to run on every single
implementation of C, no matter how weird; that's why many programs make
all sort of assumptions that C does not guarantee -- for instance, that
char is precisely 8 bits wide; or that int is precisely 32 bits wide; or
that int is wider than char; or that a pointer can fit into an int; or
that a function pointer can fit into a data pointer; or that int32_t
exists; or that signed integer overflow behaves in the common way. For
each of those assumptions, there are some implementations where it's
false; but a vast number of programs don't care about any of those
implementations.
A quibble: Assuming that a pointer can fit into an int is both dangerous
(it's not true on modern 64-bit systems) and unnecessary, since we have
intptr_t and uintptr_t.
I know. But that doesn't change the fact that many programs do it. I
have seem some of them.
Post by Keith Thompson
[...]
Post by Wojtek Lerch
For instance, POSIX makes some guarantees in addition to what standard
C promises, such as 8-bit char and the ability to represent a function
pointer as a void* (see dlsym()).
POSIX does require CHAR_BIT==8, but I don't believe it guarantees that a
function pointer can be converted to void* and back again without loss
of information. As I recall, an earlier version of POSIX did have that
requirement, but it currently only requires that a void* pointer
*returned by dlsym()* can be converted to the appropriate
pointer-to-function type.
I didn't want to go too deep into details, but perhaps I should have
written "... the ability to represent *some* function pointers as a
void*." Would that have been better?
s***@casperkitty.com
2015-10-12 17:04:43 UTC
Permalink
Raw Message
Post by Wojtek Lerch
Post by s***@casperkitty.com
The problem is that there's no standardized means by which a programmer can
be sure that a compiler won't make certain inferences, and there's no longer
any reason to believe that compilers won't try to break code.
Huh? Compilers don't try to break code; it's programmers that write
broken code. If the programmer does his job and makes sure that his
code doesn't invoke undefined behaviour, the compiler will do its job
too, and the code will behave the way the language guarantees it to behave.
Suppose a library specifies that they store 16-bit data into a buffer
halfword-aligned and a particular endianness, but do not specify whether
they use type "short*" or "int*" for the purpose, and also specify that
they store 32-bit data word-aligned but likewise do not specify whether
they use type "int*" or "long*".

Another library expects to receive suitably-aligned 16-bit and 32-bit
data, but likewise does not specify the type used to read it.

If a program receives data from the first library and passes it to the
second, and it turns out the two libraries use different types with
identical representations, and and everything works until the newest
build system recognizes that some of the code paths which pass data
between the two libraries will cause memory to be written as one type
and read as another in a violation of the C89 rules, and consequently
decides to omit such code paths, causing the code to stop working, to
whom or what should the failure be attributed?
Wojtek Lerch
2015-10-13 03:49:19 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Wojtek Lerch
Post by s***@casperkitty.com
The problem is that there's no standardized means by which a programmer can
be sure that a compiler won't make certain inferences, and there's no longer
any reason to believe that compilers won't try to break code.
Huh? Compilers don't try to break code; it's programmers that write
broken code. If the programmer does his job and makes sure that his
code doesn't invoke undefined behaviour, the compiler will do its job
too, and the code will behave the way the language guarantees it to behave.
Suppose a library specifies that they store 16-bit data into a buffer
halfword-aligned and a particular endianness, but do not specify whether
they use type "short*" or "int*" for the purpose, and also specify that
they store 32-bit data word-aligned but likewise do not specify whether
they use type "int*" or "long*".
Why not? If it's a C library, wouldn't it be wrong to underspecify it
like that?
Post by s***@casperkitty.com
Another library expects to receive suitably-aligned 16-bit and 32-bit
data, but likewise does not specify the type used to read it.
Again, why not?
Post by s***@casperkitty.com
If a program receives data from the first library and passes it to the
second, and it turns out the two libraries use different types with
identical representations, and and everything works until the newest
build system recognizes that some of the code paths which pass data
between the two libraries will cause memory to be written as one type
and read as another in a violation of the C89 rules, and consequently
decides to omit such code paths, causing the code to stop working, to
whom or what should the failure be attributed?
My vote would be the people who wrote the specifications of the two
libraries.
s***@casperkitty.com
2015-10-13 07:39:51 UTC
Permalink
Raw Message
Post by Wojtek Lerch
Why not? If it's a C library, wouldn't it be wrong to underspecify it
like that?
Until recently, clients would have no reason to need to know the exact means
by which the data got stored into memory, because there was zero likelihood
of a compiler/linker trying to analyze aliasing across compilation units.
Given that the optimizations made possible by the strict aliasing rule can
also be facilitated using "restrict", and that the value of the strict-
aliasing-based optimizations is often inversely proportional to the ease
of finding them, I see no reason somebody in the year 2000 or even 2008
should have expected that compiler writers would get so aggressive in
exploiting strict aliasing, especially since the only reason that the rule
hadn't caused a lot of trouble in the preceding decade was that most
programmers and compiler writers alike ignored it.
Post by Wojtek Lerch
My vote would be the people who wrote the specifications of the two
libraries.
My vote would be with the people who decided that "optimizations" were
more important than compatibility with existing code.

To my mind, if it is possible to write code in a language to achieve a
certain level of performance with an old compiler, new versions of the
language should allow such code to be written in such a way as to still
yield the same performance on the old compiler but also work on the
new compiler. The C89 strict aliasing rule, as written, totally fails
in that regard.
Wojtek Lerch
2015-10-13 16:51:59 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Wojtek Lerch
Why not? If it's a C library, wouldn't it be wrong to underspecify it
like that?
Until recently, clients would have no reason to need to know the exact means
by which the data got stored into memory, because there was zero likelihood
of a compiler/linker trying to analyze aliasing across compilation units.
I don't know; the desire to follow the rules of the language feels like
a reason to me, even when I believe that the likelihood of the compiler
detecting my violation of the rules is zero.
Post by s***@casperkitty.com
Given that the optimizations made possible by the strict aliasing rule can
also be facilitated using "restrict", and that the value of the strict-
aliasing-based optimizations is often inversely proportional to the ease
of finding them, I see no reason somebody in the year 2000 or even 2008
should have expected that compiler writers would get so aggressive in
exploiting strict aliasing, especially since the only reason that the rule
hadn't caused a lot of trouble in the preceding decade was that most
programmers and compiler writers alike ignored it.
That's the wrong approach. Rules are rules; if you break them, you're
doing it at your own risk. If it turns out that you have underestimated
the risk, it's your own fault. Instead of complaining when the rules
start to be enforced, you should have tried to get the rules changed
beforehand.
Post by s***@casperkitty.com
Post by Wojtek Lerch
My vote would be the people who wrote the specifications of the two
libraries.
My vote would be with the people who decided that "optimizations" were
more important than compatibility with existing code.
Optimizations *should* be more important than compatibility with
*broken* code. If your code invokes undefined behaviour but you don't
want its actual behaviour to change, don't switch to a new compiler. Or
try disabling optimizations. Or try to get the language changed so that
your UB is no longer UB. Or try to convince your compiler vendor that
your UB should be handled the way you expect it to be.

Or just fix your code.
Post by s***@casperkitty.com
To my mind, if it is possible to write code in a language to achieve a
certain level of performance with an old compiler, new versions of the
language should allow such code to be written in such a way as to still
yield the same performance on the old compiler but also work on the
new compiler. The C89 strict aliasing rule, as written, totally fails
in that regard.
I have to admit I'm not as familiar with C89 or older as I am with C99
and newer; but I know that both have many corner cases where the rules
could be better. But the rules are the contract between the programmer
and the compiler -- even if you don't like a rule and know know it's not
enforced today, breaking it has the potential of causing trouble in the
future.
s***@casperkitty.com
2015-10-13 19:46:04 UTC
Permalink
Raw Message
Post by Wojtek Lerch
Post by s***@casperkitty.com
Until recently, clients would have no reason to need to know the exact means
by which the data got stored into memory, because there was zero likelihood
of a compiler/linker trying to analyze aliasing across compilation units.
I don't know; the desire to follow the rules of the language feels like
a reason to me, even when I believe that the likelihood of the compiler
detecting my violation of the rules is zero.
The supposed purpose of C89 was not to establish a new language, but rather
to formally document an existing language that existing compilers were
already using.

The Strict Aliasing Rule bears no relation whatsoever to anything which
existed in the language before; if Borland and Microsoft had released
compilers in 1990 which failed to work with code that violated the Strict
Aliasing Rule, everyone would have called those compilers "broken", and if
Borland and Microsoft had pointed to the Standard, a new standard would
have been established very quickly which would have been C89 minus the
Strict Aliasing Rule.

While proponents of the Strict Aliasing Rule claim it has been accepted
since 1989, and it's possible that some people believe that, that statement
is fundamentally a lie. While that the fraction of programmers who believe
in the rule's legitimacy may have reached 50%, most of those people only
accepted the rule because they were unaware of the history behind it.
Post by Wojtek Lerch
That's the wrong approach. Rules are rules; if you break them, you're
doing it at your own risk. If it turns out that you have underestimated
the risk, it's your own fault. Instead of complaining when the rules
start to be enforced, you should have tried to get the rules changed
beforehand.
What fraction of useful C programs are strictly conforming? Even 1%?

In the real world, if a municipality had a rule which imposed a $5 fine
for walking on the courthouse lawn between 12:30pm and 1:00pm on Tuesdays,
but the rule was widely ignored for years until one Tuesday the police
decided to round up everyone on the lawn and fine them $5, all of the
fines would get thrown out of court on the basis that the persistent
overt failure of the government to act upon overt non-compliance made the
"law" unenforceable. Any government officials who wanted the public to
regard as legitimate any renewed enforcement of such a rule would need to
start the rule-making process from scratch.
Post by Wojtek Lerch
Post by s***@casperkitty.com
My vote would be with the people who decided that "optimizations" were
more important than compatibility with existing code.
Optimizations *should* be more important than compatibility with
*broken* code. If your code invokes undefined behaviour but you don't
want its actual behaviour to change, don't switch to a new compiler. Or
try disabling optimizations. Or try to get the language changed so that
your UB is no longer UB. Or try to convince your compiler vendor that
your UB should be handled the way you expect it to be.
Type punning via pointers was 100% unambiguously legitimate until the
authors of C89 added a rule whose sole purpose was to allow compilers to
regard as Undefined Behavior certain constructs whose behavior had been
100% when applied to types without padding bits, and for which in many
cases no alternative existed which would not require code to be slower,
harder to read, or both.

Which of the following partial routines to set the MSB of large numbers of
consecutive bytes in a buffer would you rather read:

// Process first few bytes so ptr is aligned, them...
uint32_t* wptr = (uint32_t*)ptr;
// Process n/4 words
uint32_t wcount = count>>2;
for (uint32_t i=0; i<wcount; i++)
*wptr++ |= 0x80808080;

than

// Process first few bytes so ptr is aligned, then...
uint32_t* wptr = (uint32_t*)ptr;
// Process n/4 words
uint32_t wcount = count>>2;
for (uint32_t i=0; i<wcount; i++)
{
uint32_t temp;
memcpy(&temp, wptr+i, 4);
temp |= 0x80808080;
memcpy(wptr+i, temp, 4);
}

Provided one only used compilers which allowed aliasing to be turned off,
and made sure that it was disabled, with which of the above programs could
one have greater confidence that a compiler would yield decent performance?
Post by Wojtek Lerch
Or just fix your code.
Do you consider the second program above easier to read than the first?

Presently, compilers generally provide a means of disabling strict aliasing,
though they may require one to give up other useful and safe optimizations
in order to do so. I would like compilers to continue to provide that
option, and do so independently of other useful and safe optimizations which
do not impinge upon program design the way the Strict Aliasing Rule does.

I would think boycotting of the rule increases the likelihood of compiler
writers shifting their efforts away from trying to enforce it and work
toward defining more directives like "restrict" [which should have been
"__restrict"] which can allow vastly more effective optimizations than
the Strict Aliasing Rule ever could, without breaking existing code.

For example, if a pointer to a non-const object is cast to a const*, a
compiler is required to accept the possibility that the pointer may
legitimately be cast to a non-const pointer and used to modify the object.
I would like to see a "restrict const" qualifier which would indicate that
code creating the pointer is allowed to cache the object identified
thereby without regard for whether the recipient of the qualified pointer
might try to write to it, and which would authorize implementations that
document the existence of a "restrict const violation" trap to have such a
trap fire if an attempt is made to modify an object using a pointer that
has "gone through" a "restrict const" qualifier [note that the syntax would
be "char restrict const *p" whereas the existing restrict is
"char *restrict p".]
Post by Wojtek Lerch
Post by s***@casperkitty.com
To my mind, if it is possible to write code in a language to achieve a
certain level of performance with an old compiler, new versions of the
language should allow such code to be written in such a way as to still
yield the same performance on the old compiler but also work on the
new compiler. The C89 strict aliasing rule, as written, totally fails
in that regard.
I have to admit I'm not as familiar with C89 or older as I am with C99
and newer; but I know that both have many corner cases where the rules
could be better. But the rules are the contract between the programmer
and the compiler -- even if you don't like a rule and know know it's not
enforced today, breaking it has the potential of causing trouble in the
future.
I'd say there was something of a "contract" between the ANSI Committee and
the programming community, that indicated that ANSI was supposed to
standardize the pre-existing language rather than invent a new one, and
when ANSI blatantly violated it, programmers and compiler writers alike
regarded the "real" C programming language as being the same as it had
been before the ANSI Standard was ratified. Had ANSI provided a useful
means by which code could have complied with the Strict Aliasing Rule
without impacting the performance of other code (e.g. by defining a
__IGNORE_TYPE(ptr, size) directive which would require that a compiler
either evaluate ptr and size or not, at its leisure, and ignore anything
it might be able to infer about the type associated with "size" bytes
starting at address "ptr") then it could have eliminated the special
exemption for character types (thus making the rule more effective for
its stated purpose) and allowed any existing code to be made compliant
with the new rule without affecting performance on old compilers (simply
have code define __IGNORE_TYPE(x,y) as an empty macro when using a pre-C89
compiler). Had ANSI done that, the rule would have been useful, and I
would support its continued existence.

I cannot, however, suggest that a rule should be enabled by default until
a zero-impact means of compliance has been available for at least five
years. Since no such means has yet been defined, that would put the
earliest reasonable date sometime after 2021.
Keith Thompson
2015-10-13 20:13:29 UTC
Permalink
Raw Message
***@casperkitty.com writes:
[...]
Post by s***@casperkitty.com
While proponents of the Strict Aliasing Rule claim it has been accepted
since 1989, and it's possible that some people believe that, that statement
is fundamentally a lie.
[...]

This kind of overstated rhetoric makes it difficult to take your ideas
seriously.
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
s***@casperkitty.com
2015-10-13 21:10:20 UTC
Permalink
Raw Message
Post by Keith Thompson
This kind of overstated rhetoric makes it difficult to take your ideas
seriously.
Perhaps "lie" was not the best term as it implied malice on the part of
the person speaking, but I do not believe there is any objective
justification for any claim of long-standing broad-based support for
the Strict Aliasing Rule.

If the corpus of C programs produced between 1-1-1990 and 1-1-2010 were
subjected to analysis, looking for two kinds of programs:

1. Those which go through some effort to avoid violating strict aliasing,
and are successful at doing so.

2. Those which violate strict aliasing requirements (even if they make some
failed efforts to avoid doing so)

If the Rule had broad-based support, the first kind of program should be
vastly more numerous than the second in a wide variety of application
fields.

When compilers emerged which would break code that used 16-bit and 32-bit
types to process groups of items, was the more common response that people
should use memcpy, or was the more common response that people should make
certain they disable the "strict aliasing" options?

As with the Emperor's recently-acquired raiment, whose who see greater
value in severely curtailing the expressiveness of a language so as to
give compilers a small amounts of flexibility to make slight optimizations,
than in expanding the expressiveness of a language so that programmers can
voluntarily give the compiler flexibility over things they don't care
about, perceive those who don't join their vision as fools. Their beliefs,
however, don't make the Emperor any less naked.
Richard Damon
2015-10-14 02:55:52 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
The supposed purpose of C89 was not to establish a new language, but rather
to formally document an existing language that existing compilers were
already using.
The Strict Aliasing Rule bears no relation whatsoever to anything which
existed in the language before; if Borland and Microsoft had released
compilers in 1990 which failed to work with code that violated the Strict
Aliasing Rule, everyone would have called those compilers "broken", and if
Borland and Microsoft had pointed to the Standard, a new standard would
have been established very quickly which would have been C89 minus the
Strict Aliasing Rule.
While proponents of the Strict Aliasing Rule claim it has been accepted
since 1989, and it's possible that some people believe that, that statement
is fundamentally a lie. While that the fraction of programmers who believe
in the rule's legitimacy may have reached 50%, most of those people only
accepted the rule because they were unaware of the history behind it.
My understanding is that the rule WAS put in to allow some optimization.
Without the rule it was feared that a compiler would have a hard time
keeping results temporarily in variables. Say you have an int result,
and the program writes through a pointer to long. Without the Strict
Aliasing Rule, that write through the pointer could possible change ANY
value cached in a register, unless the compiler could prove that the
pointer can't point to the variable the results came from (And compilers
weren't nearly as good at making such proofs back then).
Kaz Kylheku
2015-10-14 03:05:13 UTC
Permalink
Raw Message
Post by Richard Damon
Post by s***@casperkitty.com
The supposed purpose of C89 was not to establish a new language, but rather
to formally document an existing language that existing compilers were
already using.
The Strict Aliasing Rule bears no relation whatsoever to anything which
existed in the language before; if Borland and Microsoft had released
compilers in 1990 which failed to work with code that violated the Strict
Aliasing Rule, everyone would have called those compilers "broken", and if
Borland and Microsoft had pointed to the Standard, a new standard would
have been established very quickly which would have been C89 minus the
Strict Aliasing Rule.
While proponents of the Strict Aliasing Rule claim it has been accepted
since 1989, and it's possible that some people believe that, that statement
is fundamentally a lie. While that the fraction of programmers who believe
in the rule's legitimacy may have reached 50%, most of those people only
accepted the rule because they were unaware of the history behind it.
My understanding is that the rule WAS put in to allow some optimization.
Without the rule it was feared that a compiler would have a hard time
keeping results temporarily in variables. Say you have an int result,
and the program writes through a pointer to long. Without the Strict
Aliasing Rule, that write through the pointer could possible change ANY
value cached in a register, unless the compiler could prove that the
pointer can't point to the variable the results came from (And compilers
weren't nearly as good at making such proofs back then).
Oh, but that's okay; to hell with the the common case---let that be slow
and bloated in instruction count, as long as once in a while I can write some
"punny" code which runs twice as fast as the best portable alternative (under
GCC x.y.z targetting i686).
s***@casperkitty.com
2015-10-14 05:13:33 UTC
Permalink
Raw Message
Post by Richard Damon
My understanding is that the rule WAS put in to allow some optimization.
Without the rule it was feared that a compiler would have a hard time
keeping results temporarily in variables. Say you have an int result,
and the program writes through a pointer to long. Without the Strict
Aliasing Rule, that write through the pointer could possible change ANY
value cached in a register, unless the compiler could prove that the
pointer can't point to the variable the results came from (And compilers
weren't nearly as good at making such proofs back then).
I wouldn't find the strict aliasing rule objectionable if (1) it were made
"opt-in", and/or (2) it provided a means of localized bypass which could
be expected not to degrade performance on any compiler below what it would
be if the rule didn't exist. Using memcpy to read a pointer to a temporary,
changing the temporary, and using memcpy to write the pointer back will
generally work, but on many compilers it is likely to be slower (sometimes a
*lot* slower) than code which simply used the original pointer directly,
and will also be far less legible. If an intrinsic existed which was
equivalent to "memmove(ptr, ptr, size)" but didn't actually physically move
anything except on those rare occasions where hardware caching or other
such issues might make it necessary, use of such an intrinsic could make
code more legible while having zero adverse performance impact, but that's
not how the rule is designed.
Kaz Kylheku
2015-10-14 05:26:54 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Richard Damon
My understanding is that the rule WAS put in to allow some optimization.
Without the rule it was feared that a compiler would have a hard time
keeping results temporarily in variables. Say you have an int result,
and the program writes through a pointer to long. Without the Strict
Aliasing Rule, that write through the pointer could possible change ANY
value cached in a register, unless the compiler could prove that the
pointer can't point to the variable the results came from (And compilers
weren't nearly as good at making such proofs back then).
I wouldn't find the strict aliasing rule objectionable if (1) it were made
"opt-in", and/or (2) it provided a means of localized bypass which could
Strict aliasing is good computer science. Objects should be used by operations
of the correct type which match those objects. Any deviation from that
assumption should be opt-out.

All halfway decent high level languages regard the misuse of an object as
another type repugnant.

(If you want type punning galore, there is C's predecessor, BCPL. Everything is
a word, whose type is that of whatever is operating on it at the moment.)

Making punning defined, in some sense, is an optimization downer. From time to
time you can do things that are very efficient; however, at the cost of the
average code generation being completely sub-par.

Any time pointers are involved in a block of code, a write through a pointer to
any type has to spill the all register-cached values of the same type and of
any other type that could conceivably be the targets of that pointer.

Ordinary portable code which *isn't* doing type punning suffers because
of the support for the trick.

The main goal of a high level language, as far as optimization goes, should be
to make portable, idiomatic code run fast. Programmers who want machine-specific
risk can always use inline assembly. (Or even "out of line" assembly, written in
a separate source file with a .S suffix or whatever.)

The industry standard practice is to write portable code in C, and write code
which does the same thing same thing in several assembly languages, as needed,
using #ifdefs or Makefile rules to build accordingly.

I'm not aware of anything which stands in your way if you want to write your
project mostly in C, yet also squeeze every cycle out of some block of code.
s***@casperkitty.com
2015-10-14 06:19:21 UTC
Permalink
Raw Message
Post by Kaz Kylheku
Strict aliasing is good computer science. Objects should be used by operations
of the correct type which match those objects. Any deviation from that
assumption should be opt-out.
I wouldn't mind having it be opt-out if there were clean defined ways of
opting out, but no Standard-defined ways are icky. Can you offer any
reason why writing

for (i=0; i<n; i++)
{
uint32_t temp;
memcpy(&temp, array+i, sizeof temp);
temp |= 0x80808080;
memcpy(array+i, &temp, sizeof *p);
}

is somehow "better compute science" than would be:

__UNALIAS(array, n * sizeof (uint32_t));
for (i=0; i<n; i++)
array[i] |= 0x80808080;
__UNALIAS(array, n * sizeof (uint32_t));

Also, there are many places where the C type system necessitates the use of
type punning because of its inability to recognize a relationship among, e.g.

struct THING { uint32_t size; uint16_t dat[]; };
struct THING4 { uint32_t size; uint16_t dat[4]; };
struct THING8 { uint32_t size; uint16_t dat[8]; };

If there's never a need to statically or automatically allocate any kind of
THING, one could simply use flexible array members and malloc storage for
them, but if one needs static or automatic variables that can hold data,
that approach won't work.

It's too bad C added the prohibition against zero-sized objects, since
it would otherwise be possible to write:

struct THING { uint32_t size; uint16_t dat[0]; };
struct { struct THING base; uint16_t dat[4]; } my_dat4 =
{{4}, {1,2,3,4}};

and then use &my_dat4.base as a clearly-legitimate THING*, but C doesn't
allow that.
Post by Kaz Kylheku
All halfway decent high level languages regard the misuse of an object as
another type repugnant.
Other languages have much better type systems than C.
Post by Kaz Kylheku
Making punning defined, in some sense, is an optimization downer. From time to
time you can do things that are very efficient; however, at the cost of the
average code generation being completely sub-par.
I wouldn't mind having to let the compiler know when code is using type
punning if the workarounds could be relied upon not to generate needless
extra code on old nor new compilers.
Post by Kaz Kylheku
Any time pointers are involved in a block of code, a write through a pointer to
any type has to spill the all register-cached values of the same type and of
any other type that could conceivably be the targets of that pointer.
To do an an even remotely-effective job of eliminating register spills, one
needs to use "restrict". Once one uses "restrict", the compiler can avoid
having to worry about aliasing with all types, including that of the pointer
and char*--two cases which strict aliasing rules don't help at all with.
Post by Kaz Kylheku
Ordinary portable code which *isn't* doing type punning suffers because
of the support for the trick.
How would adding a useful intrinsic to enable type punning make anyone
suffer, and why is not "restrict" the right solution in any case?
Post by Kaz Kylheku
The main goal of a high level language, as far as optimization goes, should be
to make portable, idiomatic code run fast. Programmers who want machine-specific
risk can always use inline assembly. (Or even "out of line" assembly, written in
a separate source file with a .S suffix or whatever.)
A compiler which lets a programmer actually specify what's needed can often
do a better job of adapting itself to register usage patterns than assembly
language. What's needed, though, is a means by which a programmer that
needs specific certain circumstances can request them.
s***@casperkitty.com
2015-10-14 19:40:22 UTC
Permalink
Raw Message
Post by Kaz Kylheku
All halfway decent high level languages regard the misuse of an object as
another type repugnant.
Java and .NET languages both allow a reference to an array of references to
Cat to be passed to a function which expects a reference to an array of
references to Object. While this creates the possibility that code might
try to store something that isn't a reference to a Cat within an array of
references to Cat (in which case both Java and .NET languages will trigger
a run-time trap) it also makes it possible to write code that can receive
an array arrays of references and access the references within it without
having to know or care about the type of the array itself.

Such a thing was possible in K&R C, and probably anything that could have
been deemed an implementation of C prior to C89.

Is there any way in C89 or any subsequent version to write a method that
can accept a pointer to an array of pointers to arbitrary structure types(*)
and process them using code which is both efficient and readable?

(*)the Standard does not require that a "void*" have the same representation
as a "struct STRUCT1*", but does require that a "struct STRUCT1*" and a
"struct STRUCT2*" must have the same representation.
Kaz Kylheku
2015-10-14 19:59:19 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Kaz Kylheku
All halfway decent high level languages regard the misuse of an object as
another type repugnant.
Java and .NET languages both allow a reference to an array of references to
Cat to be passed to a function which expects a reference to an array of
references to Object. While this creates the possibility that code might
try to store something that isn't a reference to a Cat within an array of
references to Cat (in which case both Java and .NET languages will trigger
a run-time trap) it also makes it possible to write code that can receive
an array arrays of references and access the references within it without
having to know or care about the type of the array itself.
Such a thing was possible in K&R C, and probably anything that could have
been deemed an implementation of C prior to C89.
Is there any way in C89 or any subsequent version to write a method that
can accept a pointer to an array of pointers to arbitrary structure types(*)
and process them using code which is both efficient and readable?
(*)the Standard does not require that a "void*" have the same representation
as a "struct STRUCT1*", but does require that a "struct STRUCT1*" and a
"struct STRUCT2*" must have the same representation.
To be maximally portable, you have to use a union of all the struct types.
There is a special provision in C that if a union of structures is formed, and
those structures have some common initial members in common (let's call that
the "common prefix"), then this common prefix can be accessed through
any member of the union.

Regarding pointers, C99 also says this: "All pointers to union types shall have
the same representation and alignment requirements as each other."

In practice, code which doesn't use unions to achieve the same thing,
but relies on punning between structures which have some common initial
members, is /de facto/ portable also. It achieves the virtue of easier
extensibility and space saving. The union-based "blessed" approach means that
each object has the worst-case size, and that if new variants have to be
added, the union has to be edited. Dispensing with the union means that
new program modules can add variants without old code being recompiled;
it's no longer "blessed" though: it's between you and the compiler(s)
you are using.
s***@casperkitty.com
2015-10-14 20:25:51 UTC
Permalink
Raw Message
Post by Kaz Kylheku
To be maximally portable, you have to use a union of all the struct types.
There is a special provision in C that if a union of structures is formed, and
those structures have some common initial members in common (let's call that
the "common prefix"), then this common prefix can be accessed through
any member of the union.
Would you deem it practical for all such libraries whose functions might
be used on such an array must include the *same* union type, which must
in turn include all the pointer types that client code might possibly want
to use with it, even if the types used by the client code might have even
been dreamed of at the time some of the libraries were written?
Post by Kaz Kylheku
Regarding pointers, C99 also says this: "All pointers to union types shall have
the same representation and alignment requirements as each other."
In practice, code which doesn't use unions to achieve the same thing,
but relies on punning between structures which have some common initial
members, is /de facto/ portable also. It achieves the virtue of easier
extensibility and space saving. The union-based "blessed" approach means that
each object has the worst-case size, and that if new variants have to be
added, the union has to be edited. Dispensing with the union means that
new program modules can add variants without old code being recompiled;
it's no longer "blessed" though: it's between you and the compiler(s)
you are using.
Unfortunately, the strict aliasing rule is simultaneously most usefully
applicable to pointers and most annoyingly impossible to cleanly get around
in code which is intended to be type-agnostic, except by disabling the
strict aliasing rule.
Wojtek Lerch
2015-10-14 03:40:54 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Wojtek Lerch
Post by s***@casperkitty.com
Until recently, clients would have no reason to need to know the exact means
by which the data got stored into memory, because there was zero likelihood
of a compiler/linker trying to analyze aliasing across compilation units.
I don't know; the desire to follow the rules of the language feels like
a reason to me, even when I believe that the likelihood of the compiler
detecting my violation of the rules is zero.
The supposed purpose of C89 was not to establish a new language, but rather
to formally document an existing language that existing compilers were
already using.
Really? I thought it was more along the lines of reconciling the mess
of dialects existing at the time, tightening up unclear or ambiguous
specifications, and inventing new solutions for some of the problems
that none of the dialects solved. But I don't really know that much
about how it all started -- generally I have been more interested in the
result.
Post by s***@casperkitty.com
The Strict Aliasing Rule bears no relation whatsoever to anything which
existed in the language before; if Borland and Microsoft had released
compilers in 1990 which failed to work with code that violated the Strict
Aliasing Rule, everyone would have called those compilers "broken", and if
Borland and Microsoft had pointed to the Standard, a new standard would
have been established very quickly which would have been C89 minus the
Strict Aliasing Rule.
Perhaps. But that didn't happen. ISO C became the C standard.
Post by s***@casperkitty.com
While proponents of the Strict Aliasing Rule claim it has been accepted
since 1989, and it's possible that some people believe that, that statement
is fundamentally a lie. While that the fraction of programmers who believe
in the rule's legitimacy may have reached 50%, most of those people only
accepted the rule because they were unaware of the history behind it.
Or maybe the reason they accepted the rule is because it's part of the
language? The history of how C became the language it is may be
interesting, but don't see how it affects the practicalities of everyday
programming. It could be that the standard would define a better
language without that particular rule, or with a different rule plugged
in instead; but if you want to improve C89 by getting rid of the rule,
you're two and a half decades late. You can also try to get the rule
removed or changed in the next version of C, but for the time being the
rule is part of C, no matter how much you dislike it.
Post by s***@casperkitty.com
Post by Wojtek Lerch
That's the wrong approach. Rules are rules; if you break them, you're
doing it at your own risk. If it turns out that you have underestimated
the risk, it's your own fault. Instead of complaining when the rules
start to be enforced, you should have tried to get the rules changed
beforehand.
What fraction of useful C programs are strictly conforming? Even 1%?
Why do you mention strictly conforming? A lot of programs are useful
without being strictly conforming. A lot of useful programs depend on
implementation-defined aspects of the language, or would fail to compile
(or to run correctly) on implementations that don't satisfy certain
conditions, or rely on promises given by other specifications, such as
POSIX. Some of them even invoke undefined behaviour as per the C
standard, if there's another spec that defines their behaviour (such as
converting the result of the POSIX dlsym() to a function pointer).
Post by s***@casperkitty.com
In the real world, if a municipality had a rule which imposed a $5 fine
for walking on the courthouse lawn between 12:30pm and 1:00pm on Tuesdays,
but the rule was widely ignored for years until one Tuesday the police
decided to round up everyone on the lawn and fine them $5, all of the
fines would get thrown out of court on the basis that the persistent
overt failure of the government to act upon overt non-compliance made the
"law" unenforceable. Any government officials who wanted the public to
regard as legitimate any renewed enforcement of such a rule would need to
start the rule-making process from scratch.
That's not really a good analogy. A better analogy would be a
government rule allowing restaurants to enforce a dress code. If no
restaurant took advantage of the rule for two and a half decades, and
then suddenly one decided to require suits and ties, would courts side
with people who wanted to keep going to that restaurant in T-shirts?
Post by s***@casperkitty.com
Post by Wojtek Lerch
Post by s***@casperkitty.com
My vote would be with the people who decided that "optimizations" were
more important than compatibility with existing code.
Optimizations *should* be more important than compatibility with
*broken* code. If your code invokes undefined behaviour but you don't
want its actual behaviour to change, don't switch to a new compiler. Or
try disabling optimizations. Or try to get the language changed so that
your UB is no longer UB. Or try to convince your compiler vendor that
your UB should be handled the way you expect it to be.
Type punning via pointers was 100% unambiguously legitimate until the
authors of C89 added a rule whose sole purpose was to allow compilers to
regard as Undefined Behavior certain constructs whose behavior had been
100% when applied to types without padding bits, and for which in many
cases no alternative existed which would not require code to be slower,
harder to read, or both.
Perhaps. I'm not arguing about whether adding that particular rule to
the language 25 years ago was a good idea or not. My argument is that
it's been part of the language for a very long time, and expecting
everybody to agree to pretend that it doesn't exist is not very realistic.

...
Post by s***@casperkitty.com
I would think boycotting of the rule increases the likelihood of compiler
writers shifting their efforts away from trying to enforce it and work
toward defining more directives like "restrict" [which should have been
"__restrict"] which can allow vastly more effective optimizations than
the Strict Aliasing Rule ever could, without breaking existing code.
Boycotting by who?
Post by s***@casperkitty.com
For example, if a pointer to a non-const object is cast to a const*, a
compiler is required to accept the possibility that the pointer may
legitimately be cast to a non-const pointer and used to modify the object.
I would like to see a "restrict const" qualifier which would indicate that
code creating the pointer is allowed to cache the object identified
thereby without regard for whether the recipient of the qualified pointer
might try to write to it, and which would authorize implementations that
document the existence of a "restrict const violation" trap to have such a
trap fire if an attempt is made to modify an object using a pointer that
has "gone through" a "restrict const" qualifier [note that the syntax would
be "char restrict const *p" whereas the existing restrict is
"char *restrict p".]
That indeed sounds useful, except I think you'd need a different syntax
to avoid the ambiguity in "char * restrict const *p".
Post by s***@casperkitty.com
Post by Wojtek Lerch
Post by s***@casperkitty.com
To my mind, if it is possible to write code in a language to achieve a
certain level of performance with an old compiler, new versions of the
language should allow such code to be written in such a way as to still
yield the same performance on the old compiler but also work on the
new compiler. The C89 strict aliasing rule, as written, totally fails
in that regard.
I have to admit I'm not as familiar with C89 or older as I am with C99
and newer; but I know that both have many corner cases where the rules
could be better. But the rules are the contract between the programmer
and the compiler -- even if you don't like a rule and know know it's not
enforced today, breaking it has the potential of causing trouble in the
future.
I'd say there was something of a "contract" between the ANSI Committee and
the programming community, that indicated that ANSI was supposed to
standardize the pre-existing language rather than invent a new one, and
when ANSI blatantly violated it, programmers and compiler writers alike
regarded the "real" C programming language as being the same as it had
been before the ANSI Standard was ratified.
Perhaps, but that's ancient history now. The same situation happened a
decade later with with C99, and in my experience programmers who resist
C99 and consider C89 the "real" C are a disappearing breed too. I am
not seeing any signs of a third round of adjustments triggered by C11
yet, but I expect it to start, reluctantly, in a few years.
s***@casperkitty.com
2015-10-14 07:27:53 UTC
Permalink
Raw Message
Post by Wojtek Lerch
Post by s***@casperkitty.com
What fraction of useful C programs are strictly conforming? Even 1%?
Why do you mention strictly conforming? A lot of programs are useful
without being strictly conforming.
Of course they are. The Standard, however, does not define any meaningful
definitions of conformity other than "strictly conforming" programs which
will in theory run on any conforming implementation [though the way the
Standard is written, an implementation merely has to be capable of running
at least one program, rather than being able to run all strictly-conforming
programs] or "conforming" programs, each of which will run on some
implementation somewhere.

Any program that is not strictly conforming does not run in C99 (or C11,
C89, or whatever), but rather runs in some language which is an extended
version of the Standard. In some extended versions of the Standard,
type punning via pointers is expressly legal. In others, overflow is
defined as wrapping in two's-complement fashion. Is there any reason
to regard any of those extended versions of the Standard as any less
"legitimate" than any other for purposes of writing anything other than
strictly-conforming programs?
Post by Wojtek Lerch
That's not really a good analogy. A better analogy would be a
government rule allowing restaurants to enforce a dress code. If no
restaurant took advantage of the rule for two and a half decades, and
then suddenly one decided to require suits and ties, would courts side
with people who wanted to keep going to that restaurant in T-shirts?
Depending upon where the restaurant was located, it might find itself very
popular, or it might find itself completely without customers.
Post by Wojtek Lerch
That indeed sounds useful, except I think you'd need a different syntax
to avoid the ambiguity in "char * restrict const *p".
I can see there could be a problem there, though I'll admit I don't quite
understand the effect of an inner "restrict" on nested pointers.
Post by Wojtek Lerch
Perhaps, but that's ancient history now. The same situation happened a
decade later with with C99, and in my experience programmers who resist
C99 and consider C89 the "real" C are a disappearing breed too. I am
not seeing any signs of a third round of adjustments triggered by C11
yet, but I expect it to start, reluctantly, in a few years.
I want to see the language move forward, but think it needs to focus on
what I would call "programmer-driven optimization". One of the supposed
reasons that compilers supposedly need to use rules about UB to make
inferences about what values a variable might contain when code reaches
certain points is to allow in-line function expansion to drop dead code.
While I think eliminating genuinely dead code is a great idea, I would
suggest that adding compiler intrinsics for that purpose would help
compilers supply better diagnostic facilities while generating more
efficient code.

Adding intrinsics like __CHECKED_ASSUME(condition) which a compiler could
at its leisure either ignore or treat as an assertion which would prevent
the following code from executing if it isn't true would allow a compiler
to perform dead-code elimination much more accurately than would be
possible using UB alone, and would also allow diagnostics to reliably
distinguish between cases where part of the code isn't expected to handle
a given input from those where part of the code which is *expected* to
handle a given input is buggy and won't actually handle it correctly.

Further, there are many kinds of programs where overflow trapping would be
desirable to ensure that the program won't produce seemingly-valid-but-wrong
output. Manual overflow-trapping code, however, is hard to read, difficult
to get right, and hard to optimize. Defining semantics for overflow
trapping would allow applications which need such trapping to be much more
efficient than would otherwise be possible, especially if an expression like

int a,b,c,d; ...
a=b+c+d;

would be allowed to arbitrarily trap or not in the scenario where the
mathematical value of b+c was not representable as "int" but the mathematical
value of b+c+d was. On some platforms with registers longer than the
memory bus, it may be most efficient to keep values with precision beyond
"int" as long as they can stay in registers, but validate that the
registers are within the range of "int" before spilling them [thus only
having to save half the register]. A programmer cannot be expected to know
when it would be best to keep intermediate results as "long" and when to
keep them as "int", but a compiler would have access to information that
the programmer doesn't.
Wojtek Lerch
2015-10-14 14:26:32 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Wojtek Lerch
Post by s***@casperkitty.com
What fraction of useful C programs are strictly conforming? Even 1%?
Why do you mention strictly conforming? A lot of programs are useful
without being strictly conforming.
Of course they are. The Standard, however, does not define any meaningful
definitions of conformity other than "strictly conforming" programs which
will in theory run on any conforming implementation [though the way the
Standard is written, an implementation merely has to be capable of running
at least one program, rather than being able to run all strictly-conforming
programs] or "conforming" programs, each of which will run on some
implementation somewhere.
Agreed, the two categories that the standard defines names for are not
very useful in practice. Why are we discussing them again? :)
Post by s***@casperkitty.com
Any program that is not strictly conforming does not run in C99 (or C11,
C89, or whatever), but rather runs in some language which is an extended
version of the Standard.
Not true. A program that is not strictly conforming can still be a
correct program whose behaviour is dictated by standard C -- it's just
that the behaviour may depend on some implementation-defined or
unspecified details of the implementation. In the standard's own words
(4#3 in C99):

"A program that is correct in all other aspects, operating on correct
data, containing unspecified behavior shall be a correct program and act
in accordance with 5.1.2.3."

Personally I would extend the category of Useful Programs to ones that
only work on a certain subset of all implementations -- preferably
rejecting unacceptable implementations via an #error directive, but also
possibly by documenting their requirements in prose.
Post by s***@casperkitty.com
In some extended versions of the Standard,
type punning via pointers is expressly legal. In others, overflow is
defined as wrapping in two's-complement fashion. Is there any reason
to regard any of those extended versions of the Standard as any less
"legitimate" than any other for purposes of writing anything other than
strictly-conforming programs?
One fairly good reason is that they are not formally recognized ISO
standards. But if you can find implementations that officially promise
to follow your extended version of C, then absolutely, it may be worth
taking advantage of -- or not, depending on whether the gains justify
the loss of portability.

But if you use an implementations that appears to follow your extended
version of C without committing to it officially, then, well, if you
decide to rely on it, you're doing it at your own risk.

...
Post by s***@casperkitty.com
Post by Wojtek Lerch
Perhaps, but that's ancient history now. The same situation happened a
decade later with with C99, and in my experience programmers who resist
C99 and consider C89 the "real" C are a disappearing breed too. I am
not seeing any signs of a third round of adjustments triggered by C11
yet, but I expect it to start, reluctantly, in a few years.
I want to see the language move forward, but think it needs to focus on
what I would call "programmer-driven optimization". One of the supposed
reasons that compilers supposedly need to use rules about UB to make
inferences about what values a variable might contain when code reaches
certain points is to allow in-line function expansion to drop dead code.
I think that different rules about UB are meant to allow different kinds
of optimizations. Without the type punning rule, a compiler would have
to assume (except when it could prove otherwise) that all pointers in a
program may point to overlapping objects and therefore accesses via
pointers cannot be re-ordered and pointed-to values cannot be cached.
That could have a huge impact on all sorts of optimizations in any
program that uses pointers in a non-trivial way.

If you do need type punning, you can still do it, explicitly, by using a
union. What's wrong with that?
Post by s***@casperkitty.com
While I think eliminating genuinely dead code is a great idea, I would
suggest that adding compiler intrinsics for that purpose would help
compilers supply better diagnostic facilities while generating more
efficient code.
Personally I care more about optimizing live code. As long as a
compiler notices trivial things like "if(constant)", I'm happy to
eliminate my dead code by not writing it in the first place. :)
s***@casperkitty.com
2015-10-14 17:15:46 UTC
Permalink
Raw Message
Post by Wojtek Lerch
Post by s***@casperkitty.com
Any program that is not strictly conforming does not run in C99 (or C11,
C89, or whatever), but rather runs in some language which is an extended
version of the Standard.
Not true. A program that is not strictly conforming can still be a
correct program whose behaviour is dictated by standard C -- it's just
that the behaviour may depend on some implementation-defined or
unspecified details of the implementation. In the standard's own words
"A program that is correct in all other aspects, operating on correct
data, containing unspecified behavior shall be a correct program and act
in accordance with 5.1.2.3."
You're correct that there is a third useful category of programs implied
by the Standard, though the Standard does not assign a label to it, which
consists of programs for which every compiler would be required to issue
a diagnostic or else implement proper behavior, though the number of
programs in this category is much smaller than it should be, since most
Implementation-Dependent behaviors have no defined means of confirming
that an implementation will meet needs.
Post by Wojtek Lerch
Personally I would extend the category of Useful Programs to ones that
only work on a certain subset of all implementations -- preferably
rejecting unacceptable implementations via an #error directive, but also
possibly by documenting their requirements in prose.
I'd go along with that, though I think it would be better to have a
__REQUIRE directive with standardized way of indicating what semantics a
program requires, and also some new type names. For example, if code
requires that the multiplication of two 32-bit unsigned values yields a
mod-4294967296 result, I would suggest that having a type "uwrap32_t"
which must honor such semantics in cases where the compiler accepts it
would be more helpful than

#if (INT_MAX > 4294967295)
#error "Sorry, this program needs 'int' to be 32 bits or smaller"
#endif

especially since it would be possible for a compiler to have "int" be 64
bits and yet still support a "uwrap32_t" type.

Likewise, I would consider:

__UXC_REQUIRE(__UXC_INTEGER_OVERFLOW, __UXC_INTEGER_OVERFLOW_WRAP)

to be more helpful than

#if (...something that doesn't yet exist)
#error This code requires wrapping integer overflow semantics
#endif

since a compiler could respond to the former by automatically enabling
the appropriate options, or else by yielding a diagnostic message which
could say whether a command-line switch would be able to achieve the
necessary behavior.

Further, I think there would be useful category of programs which would be
guaranteed to work on any compiler which satisfied all __REQUIRE directives,
and would work on at least one [implying that its requirements were not
contradictory].
Post by Wojtek Lerch
One fairly good reason is that they are not formally recognized ISO
standards. But if you can find implementations that officially promise
to follow your extended version of C, then absolutely, it may be worth
taking advantage of -- or not, depending on whether the gains justify
the loss of portability.
There are a lot of things that aren't mandated by any standard, but are
widely supported. Does anything in the Standard, for example, require
that (int16_t)65535 must yield -1? I would not a little surprised if
any implementations that are designed for practical use would yield any
other value, but from what I can tell the value of (int16_t)65535 is
Implementation Defined, and I don't think the Standard imposes any more
restrictions on it than that.
Post by Wojtek Lerch
But if you use an implementations that appears to follow your extended
version of C without committing to it officially, then, well, if you
decide to rely on it, you're doing it at your own risk.
If 90% of implementations can guarantee that something will work a certain
way, and if such guarantee is useful, is there any reason the Standard
shouldn't define a means of refusing compilation on any platform that
doesn't meet that requirement?
Post by Wojtek Lerch
I think that different rules about UB are meant to allow different kinds
of optimizations. Without the type punning rule, a compiler would have
to assume (except when it could prove otherwise) that all pointers in a
program may point to overlapping objects and therefore accesses via
pointers cannot be re-ordered and pointed-to values cannot be cached.
That could have a huge impact on all sorts of optimizations in any
program that uses pointers in a non-trivial way.
I do not consider that plausible as a major motivation. Let me offer
another much more important one. Suppose that one is writing a language
to run on two kinds of machines:

1. Some machines will trap on signed integer overflow, and would require
extra code to yield wrapping behavior.

2. Some machines will use wrapping arithmetic on signed integer overflow,
and would require extra code to trap.

Certainly both kinds of machines existed when C was being developed.

Suppose further that, with regard to applications:

1. Some applications are required not to produce seemingly-valid-but-wrong
output in case of integer overflow.

2. Some applications need to perform a number of calculations upon a mix
of valid and invalid data, produce correct results for the parts of
the data which are valid, and may produce arbitrary results for the
parts of the data which are invalid.

I think it's pretty clear that some applications fit each requirement above.

If overflow had been mandated to have wrapping behavior, then someone who
was writing the first kind of application for the first kind of machine
would have to write code to detect overflow himself (even thought he machine
could have done it for him), and the compiler would have to itself add code
to ensure that no overflows could occur in any of the arithmetic and cause
a trap. The net result would be that mandating wrapping overflow would make
the first kind of application code unnecessarily hard to write, and much
slower to execute, than would be possible leaving overflow undefined.

If overflow had been mandated as having trapping behavior, then someone who
was writing the second kind of application for the second kind of machine
would have to add extra code to prevent overflow, and the machine would have
to attach extra machine code code to all of the user code (including code
whose sole purpose was to avoid overflow) to detect and trap on overflow.
Again, making things much worse than leaving overflow undefined.

Given that machines that were often used for applications of the first type
would be more likely to have the first kind of overflow semantics than those
which were used more for applications of the second type, it should be clear
that mandating either form of overflow semantics would benefit code that
needed to run on one machine, but be extremely harmful to code that needed
to run on the other.

If there were any significant perceived need to have programs which could
run on machines other than those for which they were written, both needs
could have been fulfilled very nicely by allowing programs to specify what
sort of overflow semantics they need. On the other hand, given the
resource constraints under which C was operating, it was deemed easier to
have programmers simply pencil in a list of requirements and expect that
anyone who would want to use a program would read the hand-written note.
Post by Wojtek Lerch
If you do need type punning, you can still do it, explicitly, by using a
union. What's wrong with that?
It requires that all code using the data structure must use the same union
type, which in turn requires that all code using the data structure must
know all of the types that any other code might need to use to access it.

Consider the following function:

/* Given an array of pointers to any kind of structure, consolidate
all non-null pointers to the start and all null pointers to the
back, keeping items in order */

int consolidate(struct GENERIC_STRUCTURE **array, int size)
{
int i,n;

n=0;
for (i=0; i<size; i++)
if (array[i]) array[n++] = array[i];
for (i=n; i<size; i++)
array[i] = 0;
}

struct INT_S { int x; };
struct INT_S *int_structures[123];
struct DOUBLE_S { double y; };
struct DOUBLE_S *double_structures[123];

In the absence of the strict aliasing rule, the above method would be
able to operate on int_structures or double_structures, or any other
array of pointers to any structure type.

Can you offer any way to write an equivalent function in C89?

Suppose that on a system where "int" and "long" have identical 32-bit
representations, one has an external library which will process a small
portion of an "int[]", and another which will process a small portion of
a "long[]". One needs to pass an array of 1,000,000 32-bit values to
to the first library, then the second, then the first, then second, etc.
a million times.

Can you suggest a reasonable way doing that on C89 which could be
reasonably guaranteed to not run orders of magnitude slower than
code would run without the strict aliasing rule?
Post by Wojtek Lerch
Personally I care more about optimizing live code. As long as a
compiler notices trivial things like "if(constant)", I'm happy to
eliminate my dead code by not writing it in the first place. :)
How would you handle the situation where a function gets in-lined five
times, and part of the code is live for two of them and dead for three?
Kaz Kylheku
2015-10-14 18:23:03 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Wojtek Lerch
Post by s***@casperkitty.com
Any program that is not strictly conforming does not run in C99 (or C11,
C89, or whatever), but rather runs in some language which is an extended
version of the Standard.
Not true. A program that is not strictly conforming can still be a
correct program whose behaviour is dictated by standard C -- it's just
that the behaviour may depend on some implementation-defined or
unspecified details of the implementation. In the standard's own words
"A program that is correct in all other aspects, operating on correct
data, containing unspecified behavior shall be a correct program and act
in accordance with 5.1.2.3."
You're correct that there is a third useful category of programs implied
by the Standard, though the Standard does not assign a label to it, which
consists of programs for which every compiler would be required to issue
a diagnostic or else implement proper behavior, though the number of
programs in this category is much smaller than it should be, since most
Implementation-Dependent behaviors have no defined means of confirming
that an implementation will meet needs.
Implementation-defined behaviors must be documented by an implementation.
In effect, the implementation provides a local extension to the standard.

The users of an implementation judge its conformance to the standard,
*and* to the implmeentation's own document.

If the implementation says "fflush(stdin) clears the keyboard buffer",
and that doesn't happen, then that implementation has a bug: not an ISO C
conformance bug (since ISO C gives no requirement), but a failed conformance to
its own document (since the implementation purports to supply a documented
extension in a place where ISO C gives no requirement).

Consider that languages which don't have ISO standards are nevertheless
documented and can have bugs due to not correctly implementing something they
document.. If the Python 3 manual says that some function does one thing, but
it is found to have another, then that is a defect.

ISO-standard languages benefit from a body of requirements that they can import
from the ISO document. When two such languages share the same ISO document,
they have all of that document's requirements in common, which then helps
programs work in both languages.
Post by s***@casperkitty.com
I'd go along with that, though I think it would be better to have a
__REQUIRE directive with standardized way of indicating what semantics a
program requires, and also some new type names. For example, if code
requires that the multiplication of two 32-bit unsigned values yields a
mod-4294967296 result, I would suggest that having a type "uwrap32_t"
which must honor such semantics in cases where the compiler accepts it
would be more helpful than
#if (INT_MAX > 4294967295)
#error "Sorry, this program needs 'int' to be 32 bits or smaller"
#endif
That type was introduced in C99 and is called uint32_t.

It need not be present. There is a way to detect it via the preprocessor.

#include <inttypes.h>

#ifdef PRIu32
// we have uint32_t
#else
#error "PORTME: code relies on having uint32_t"
#endif

Maybe you should catch up on 16-year-old C basics?

Even without the C99 features, you can do better than clumsy #ifdefs
on INT_MAX, like have a tidy build configuration system which detects
features and gives them clear names:

#include "config.h" /* generated header */
#if HAVE_UINT32
...
#endif

All of this is a Solved Problem.
s***@casperkitty.com
2015-10-14 19:11:27 UTC
Permalink
Raw Message
Post by Kaz Kylheku
Post by s***@casperkitty.com
I'd go along with that, though I think it would be better to have a
__REQUIRE directive with standardized way of indicating what semantics a
program requires, and also some new type names. For example, if code
requires that the multiplication of two 32-bit unsigned values yields a
mod-4294967296 result, I would suggest that having a type "uwrap32_t"
which must honor such semantics in cases where the compiler accepts it
would be more helpful than
#if (INT_MAX > 4294967295)
#error "Sorry, this program needs 'int' to be 32 bits or smaller"
#endif
That type was introduced in C99 and is called uint32_t.
So you're saying that on all platforms defining uint32_t, the program

int main(void)
{
uint32_t x=4294967295;
x*=x;
return x;
}

is defined as returning 1? Even if "int" happens to be 64 bits?
Kaz Kylheku
2015-10-14 19:46:15 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Kaz Kylheku
Post by s***@casperkitty.com
I'd go along with that, though I think it would be better to have a
__REQUIRE directive with standardized way of indicating what semantics a
program requires, and also some new type names. For example, if code
requires that the multiplication of two 32-bit unsigned values yields a
mod-4294967296 result, I would suggest that having a type "uwrap32_t"
which must honor such semantics in cases where the compiler accepts it
would be more helpful than
#if (INT_MAX > 4294967295)
#error "Sorry, this program needs 'int' to be 32 bits or smaller"
#endif
That type was introduced in C99 and is called uint32_t.
So you're saying that on all platforms defining uint32_t, the program
int main(void)
{
uint32_t x=4294967295;
Yes. Well, of courwse, a header must be included for uint32_t to be declared.
Post by s***@casperkitty.com
x*=x;
return x;
}
is defined as returning 1? Even if "int" happens to be 64 bits?
Arithmetic on a 32 bit unsigned type takes place modulo 2**32, so
yes, x*x is 1, and this 1 is stored back into x.

In the return statement, this 1 converts to the value 1 of type int.

(In all conversions among integer types, if the value of the source
type is representable in the range of the destination type,
the behavior is well-defined: the value is preserved.)

int being 64 bits simply doesn't enter into relevance. The int type
is not involved in the arithmetic at all. Arithmetic on uint32_t
will not promote to int.

Maybe you should read some C tutorials?
Keith Thompson
2015-10-14 20:00:15 UTC
Permalink
Raw Message
Kaz Kylheku <***@kylheku.com> writes:
[...]
Post by Kaz Kylheku
int being 64 bits simply doesn't enter into relevance. The int type
is not involved in the arithmetic at all. Arithmetic on uint32_t
will not promote to int.
Citation needed.

Assume int is 64 bits and uint32_t is a typedef for unsigned short.
Why would unsigned short operands not promote to int?
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Kaz Kylheku
2015-10-15 01:36:22 UTC
Permalink
Raw Message
Post by Keith Thompson
[...]
Post by Kaz Kylheku
int being 64 bits simply doesn't enter into relevance. The int type
is not involved in the arithmetic at all. Arithmetic on uint32_t
will not promote to int.
Citation needed.
Assume int is 64 bits and uint32_t is a typedef for unsigned short.
Why would unsigned short operands not promote to int?
Oops; that's a problem. In that configuration, you can't multiply (uint32_t) -1
by itself without overflow.

It seems wortwhie to fix that situation by, say, introducing a variant of the
short type that promotes to unsigned int rather than int, and making uint32_t a
typedef for that type rather than unsigned short.

Promotion should have been designed so that unsigned bitfields, chars
and shorts go to unsigned int even if int can represent their values.
That's almost certainly irreparable in the "foreseeable" future.

Keith Thompson
2015-10-14 19:55:16 UTC
Permalink
Raw Message
[...]
Post by Kaz Kylheku
Post by s***@casperkitty.com
I'd go along with that, though I think it would be better to have a
__REQUIRE directive with standardized way of indicating what semantics a
program requires, and also some new type names. For example, if code
requires that the multiplication of two 32-bit unsigned values yields a
mod-4294967296 result, I would suggest that having a type "uwrap32_t"
which must honor such semantics in cases where the compiler accepts it
would be more helpful than
#if (INT_MAX > 4294967295)
#error "Sorry, this program needs 'int' to be 32 bits or smaller"
#endif
That type was introduced in C99 and is called uint32_t.
Almost.

Given:

uint32_t x = UINT32_MAX;
uint32_t y = UINT32_MAX;
uint32_t z = x * y;

*most* implementations will set z to 1. But if int is 64 bits, then the
two operands of the "*" will be promoted to signed int. The product
exceeds INT_MAX (2**63-1), so the behavior of the multiplication is
undefined.

The integer promotion rules give int and unsigned int a special status
within the set of predefined integer types. They have that same status
within the set of [u]intN_t types, but their position within that set
varies from one implementation to another. (I wonder if this problem
could have been avoided if the ANSI C committee had adopted unsigned
preserving rules rather than value preserving rules.)
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
s***@casperkitty.com
2015-10-14 20:12:46 UTC
Permalink
Raw Message
Post by Keith Thompson
The integer promotion rules give int and unsigned int a special status
within the set of predefined integer types. They have that same status
within the set of [u]intN_t types, but their position within that set
varies from one implementation to another. (I wonder if this problem
could have been avoided if the ANSI C committee had adopted unsigned
preserving rules rather than value preserving rules.)
I would suggest that what's needed, fundamentally, is to have distinct sets
of types uwrapN_t, and unumN_t, such that any code which uses the former
and compiles must have the same promotions applied to it as would be applied
if "int" were N bits, and any code which uses an rvalue of the latter type
and compiles must behave as though it was implicitly converted to a signed
type large enough to hold its value.

Any existing platform which defines uintN_t types could predefine for each
such type either uwrapN_t or unumN_t, depending upon whether the type would
auto-promote to a signed type.

Additionally, it would be possible for implementations to define other such
types provided that they were mapped to compiler intrinsics which would
either behave as required or refuse compilation (and I'd probably allow
compilers the option of refusing compilation in any situation where one
operand was a uwrap_N type and the other was a larger signed type, since
having a compiler demand casts in such cases would be less likely to
cause unexpected porting difficulties than would having a compiler silently
generate code whose semantics change in unintended ways).

Would that seem like a good solution to the problem?
Kaz Kylheku
2015-10-14 16:29:20 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Wojtek Lerch
Post by s***@casperkitty.com
What fraction of useful C programs are strictly conforming? Even 1%?
Why do you mention strictly conforming? A lot of programs are useful
without being strictly conforming.
Of course they are. The Standard, however, does not define any meaningful
definitions of conformity other than "strictly conforming" programs which
will in theory run on any conforming implementation [though the way the
This is only because "strictly conforming" is a concept which the Standard
requires for its own purposes.

Users and implementors can easily identify other definitions of conformity
that fits their descriptive requirements.

For instance, we can have a category of program which closely resembles
"strictly conforming" but which blows past some of the minimum resource limits.

Provided that an implementation meets the program's demands for resources
(thereby going beyond the minimum requirements), such a program's meaning is
clear and given by the Standard. Users expect implementations to take advantage
of the actual computing resources of a platform, and not artificially cause
programs to fail by imposing the minimum limits.

We can also recognize a category of program which is like the above, plus uses
platform-specific functions. The functions are defined by some platform-specific
standard, and essentially constitute translation units which are added to the
program.
Post by s***@casperkitty.com
Standard is written, an implementation merely has to be capable of running
at least one program, rather than being able to run all strictly-conforming
Note that this isn't the definition of conformance. A conforming implementation
has to be capable of translating and executing at least one strictly-conforming
program; however, the ability to do that doesn't confirm conformance.

Conformance is left open-ended. It's up to the users and implementors to agree
on what is acceptable.

The standard only gives an opinion on what some minimum acceptability should
be. The standard is telling us that if an implementation cannot demonstrate
translation and execution so much as a single strictly conforming program, it
must not be regarded as conforming.

Defining conformance as the translation and execution of all strictly-conforming
programs would be simultaneously intractable and useless. Intractable because
the space of test cases is too vast to verify, and useless because even if that
were accomplished, it would only confirm a fairly useless subset of all possible
programs. Real world applications aren't strictly conforming. A toolchain which
handles all possible strictly-conforming programs, but breaks frequently and
miserably on non-strictly-conforming programs isn't of very good quality.
Post by s***@casperkitty.com
Any program that is not strictly conforming does not run in C99 (or C11,
C89, or whatever), but rather runs in some language which is an extended
version of the Standard.
That is not the case. Some programs that are not strictly conforming
are that way only because they blow past a minimum limit, not because
they use nonstandard language features.

Secondly, C distinguishes "language" and "library". Some programs that
are not strictly conforming simply rely on additional translation units
which are supplied by the platform, but their use of the language is
completely standard.

In C terminology, calling read(fd, buffer, size) is not understood
as writing in a different C dialect, but as using a non-ISO-C
library function. The expression *can* in fact appear in a strictly conforming
program (if it defines a function or macro called read). What makes it
non-strictly-conforming is only that the definition of read doesn't
appear in the program, but is expected to come from a platform library.

In other words, because C programs routinely define new vocabularies of
declared identifiers, the mere use of declared identifiers from a platform
library doesn't give rise to a new dialect of C.
Post by s***@casperkitty.com
In some extended versions of the Standard,
type punning via pointers is expressly legal. In others, overflow is
defined as wrapping in two's-complement fashion. Is there any reason
to regard any of those extended versions of the Standard as any less
"legitimate" than any other for purposes of writing anything other than
strictly-conforming programs?
No; in fact the above, if documented, are conforming extensions: they
are additional requirements which fill in for undefined behavior.

Their use, in a program, isn't less "legitimate". It is less "portable".

The perspective that less portable programs are less "legitimate" is only
an emotional opinion. Portability is sometimes an explicit requirement
for an application and sometimes isn't. It is also a continous quantity,
not boolean. It may refer to the proportion of the program (say percentage
of the lines of code) which are portable, or to the inverse amount of effort
required to port the program.

If all else is equal, portability is better than nonportability; but all
else is rarely equal.
Kaz Kylheku
2015-10-14 16:30:25 UTC
Permalink
Raw Message
Post by Kaz Kylheku
Post by s***@casperkitty.com
Post by Wojtek Lerch
Post by s***@casperkitty.com
What fraction of useful C programs are strictly conforming? Even 1%?
Why do you mention strictly conforming? A lot of programs are useful
without being strictly conforming.
Of course they are. The Standard, however, does not define any meaningful
definitions of conformity other than "strictly conforming" programs which
will in theory run on any conforming implementation [though the way the
This is only because "strictly conforming" is a concept which the Standard
requires for its own purposes.
Users and implementors can easily identify other definitions of conformity
^^^^^^^^^^
Post by Kaz Kylheku
that fits their descriptive requirements.
Oops, what? "Conformance", of course. :)
Keith Thompson
2015-10-14 17:15:20 UTC
Permalink
Raw Message
[...]
Post by Kaz Kylheku
Post by s***@casperkitty.com
Standard is written, an implementation merely has to be capable of running
at least one program, rather than being able to run all strictly-conforming
Note that this isn't the definition of conformance. A conforming
implementation has to be capable of translating and executing at least
one strictly-conforming program; however, the ability to do that
doesn't confirm conformance.
[...]

The standard (N1570 5.2.4.1) requires an implementation to

be able to translate and execute at least one program that contains
at least one instance of every one of the following limits:
[...]

It doesn't say that that one program has to be strictly conforming
(though there's probably no good reason for it not to be).

The point of that requirement, BTW, is that the easiest way
to satisfy it is to create a *useful* implementation that
is able to translate and execute *many* different programs,
because the implementation doesn't impose arbitrary fixed limits.
An implementation that can handle one and only one program might be
"conforming", but it would not be useful or relevant.
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
s***@casperkitty.com
2015-10-14 17:42:14 UTC
Permalink
Raw Message
Post by Keith Thompson
The standard (N1570 5.2.4.1) requires an implementation to
be able to translate and execute at least one program that contains
[...]
It doesn't say that that one program has to be strictly conforming
(though there's probably no good reason for it not to be).
Would a program that ignored its input and always output the string "This
is a diagnostic" be a "standard conforming C implementation"? If one were
to write a program which taxed all of the minimum limits but whose sole
purpose was to output the string "This is a diagnostic", feeding that
program into the aforementioned "C implementation" would cause it to
produce the behavior mandated by the Standard. Feeding any other well-
formed C program would cause it to behave as though the program blew out
the stack--a situation where the Standard imposes no requirements.
Feeding an ill-formed C program would result in a diagnostic.

Clearly the authors of the Standard would not intend that such a thing be
considered a "standard conforming C implementation", but would it not meet
the requirements for such, given the way the Standard is written?

Generally, the purpose of a Standard is to provide a means of usefully
classifying partitioning things into categories of things that definitely
meet the Standard, those that definitely do not, and possibly a (hopefully
small) category of things not fitting in the other two. I am unable to see
any way in which the C Standards can be said to satisfy that purpose, though
perhaps you might?

I would posit that it would be extremely useful to have standards for
programs and implementations that could identify a large set of programs
and a large set of compilers, such that feeding any program in the first
set to any compiler in the second would result in the compiler either
rejecting the program in a way that could be detected via Implementation-
Defined means, or running the program in such a way as to satisfy that
program's requirements.

IMHO, good code should be written in such a fashion as to have one meaning,
and a good language should make it easy to achieve that. To use a Unicode
analogy, there is no requirement that a Unicode font regard &#x2603; as a
picture of a snowman, but there is a requirement that fonts refrain from
using that character code for other purposes. I would like to see C head
in a similar direction. While some might fear that would fragment the
language, I would suggest that it would instead do the opposite. If there
were a type for "sign-magnitude integer", then code which needs to perform
type punning between a sign-magnitude integer and a like-sized unsigned
integer would not compile on a two's-complement implementation which does
not support that type, but it would be possible for a two's-complement
implementation to add support for such a type without having to change
the semantics of code that doesn't need to use that type specifically.
Kaz Kylheku
2015-10-14 18:06:38 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Keith Thompson
The standard (N1570 5.2.4.1) requires an implementation to
be able to translate and execute at least one program that contains
[...]
It doesn't say that that one program has to be strictly conforming
(though there's probably no good reason for it not to be).
Would a program that ignored its input and always output the string "This
is a diagnostic" be a "standard conforming C implementation"?
No, because you could easily find a requirement in the Standard which
the implementation neglects to satisfy (thus exhibiting nonconformance).

The Standard doesn't define what is a "conforming implementation", only that
such a thing, it must successfully translate and execute at least one program.
Post by s***@casperkitty.com
If one were
to write a program which taxed all of the minimum limits but whose sole
purpose was to output the string "This is a diagnostic", feeding that
program into the aforementioned "C implementation" would cause it to
produce the behavior mandated by the Standard. Feeding any other well-
formed C program would cause it to behave as though the program blew out
the stack--a situation where the Standard imposes no requirements.
If you feed any strictly conforming C program to an C implementation, and it is
not successfully translated and executed, that is evidence that it is
nonconforming. The standard gives a set of requirements about how that
program is to be treated, and that doesn't happen. Thus the requirements
are violated, which is nonconformance.
Post by s***@casperkitty.com
Clearly the authors of the Standard would not intend that such a thing be
considered a "standard conforming C implementation", but would it not meet
Clearly, which is why no such definition is made.
Post by s***@casperkitty.com
Generally, the purpose of a Standard is to provide a means of usefully
classifying partitioning things into categories of things that definitely
meet the Standard, those that definitely do not, and possibly a (hopefully
small) category of things not fitting in the other two.
That means to classify arises from the total of all the requirements given in
the document.

To meet a requirement is to conform; no fail to implement a (non-optional)
requirement is not to conform.

We can tell when a C compiler is broken in some way with regard to the
standard. Usually, some program is found to misbehave. The misbehavior is
reproduced in a portable program, and traced to an incorrectly implemented
or missing requirement. (The standard gives one interpretation to the
situation inside the program, but the result on the implementation differs.)
Post by s***@casperkitty.com
IMHO, good code should be written in such a fashion as to have one meaning,
If you wish to convey one meaning, it behooves you to avoid tricks like type
punning, which have multiple meanings on different target platforms
(which holds even if the aliasing access itself is given implementation-defined
behavior, rather than undefined).
s***@casperkitty.com
2015-10-14 18:40:12 UTC
Permalink
Raw Message
Post by Kaz Kylheku
The Standard doesn't define what is a "conforming implementation", only that
such a thing, it must successfully translate and execute at least one program.
Correct.
Post by Kaz Kylheku
If you feed any strictly conforming C program to an C implementation, and it is
not successfully translated and executed, that is evidence that it is
nonconforming. The standard gives a set of requirements about how that
program is to be treated, and that doesn't happen. Thus the requirements
are violated, which is nonconformance.
I thought you just said that implementations were not required to correctly
process *all* conforming programs, but rather *at least one*. The fact
that an implementation fails to process some particular program would not
imply that there does not exist any program which it could process in the
required fashion.

If one has two black boxes, one of which is the "implementation" I described
and the other of which is a full-featured C implementation, and there exists
at least one valid C program which, when fed to both boxes, would result in
them producing identical behaviors, by what means could one determine that
one of the black boxes ran a C program in legitimate fashion and the other
did not? Does anything in the Standard require that implementations not be
viewed as black boxes?
Post by Kaz Kylheku
Post by s***@casperkitty.com
Generally, the purpose of a Standard is to provide a means of usefully
classifying partitioning things into categories of things that definitely
meet the Standard, those that definitely do not, and possibly a (hopefully
small) category of things not fitting in the other two.
That means to classify arises from the total of all the requirements given in
the document.
To meet a requirement is to conform; no fail to implement a (non-optional)
requirement is not to conform.
We can tell when a C compiler is broken in some way with regard to the
standard. Usually, some program is found to misbehave. The misbehavior is
reproduced in a portable program, and traced to an incorrectly implemented
or missing requirement. (The standard gives one interpretation to the
situation inside the program, but the result on the implementation differs.)
The Standard does not, from what I can tell, mandate that for any given
implementation there must exist more than one possible source file which,
when fed to the implementation, would not result in it exceeding some
resource limit. The Standard does not require implementations define any
means of identifying whether a given source file will exceed any resource
limtis, nor does it impose any requirements on what must happen if a
resource limit is exceeded.

While a compiler compiler where 99.999% of possible inputs would exceed
resource limits wouldn't be very useful even if it was kind enough to
report that limits had been exceed rather than wandering off into UB-ville,
I don't see anything in the Standard which would say such a compiler was
not compliant.
Post by Kaz Kylheku
Post by s***@casperkitty.com
IMHO, good code should be written in such a fashion as to have one meaning,
If you wish to convey one meaning, it behooves you to avoid tricks like type
punning, which have multiple meanings on different target platforms
(which holds even if the aliasing access itself is given implementation-defined
behavior, rather than undefined).
Given the following two programs:

int main(void)
{
uint32_t x = 0xEEEEEEEF;
int32_t v1 = *((unsigned char*)&x);
return (v1 != 0);
}

int main(void)
{
uint32_t x = 0xEEEEEEEF;
int32_t v1 = x;
return (v1 != 0);
}

which one has more possible behaviors? Consider also:

int main(void)
{
uint16_t x = 1, y=2;
return (x-y) > 0;
}

On platforms which don't enforce strict aliasing, type punning tends to
behave a lot more consistently than unsigned integer math.
Kaz Kylheku
2015-10-14 19:02:54 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Kaz Kylheku
The Standard doesn't define what is a "conforming implementation", only that
such a thing, it must successfully translate and execute at least one program.
Correct.
Post by Kaz Kylheku
If you feed any strictly conforming C program to an C implementation, and it is
not successfully translated and executed, that is evidence that it is
nonconforming. The standard gives a set of requirements about how that
program is to be treated, and that doesn't happen. Thus the requirements
are violated, which is nonconformance.
I thought you just said that implementations were not required to correctly
process *all* conforming programs, but rather *at least one*.
Yes; but that doesn't define what a conforming implementation is!

"All conforming students wear the student uniform" doesn't mean
that a conforming student is defined as someone wearing that uniform!
Counterexample: uniformed student caught smoking in the washroom.
Post by s***@casperkitty.com
The fact
that an implementation fails to process some particular program would not
imply that there does not exist any program which it could process in the
required fashion.
The fact that an implementation fails a program which is correct, maximally
portable, and within every single minimum implementation limit would
obviously constitute evidence that the implementation has a conformance issue.
Post by s***@casperkitty.com
If one has two black boxes, one of which is the "implementation" I described
and the other of which is a full-featured C implementation, and there exists
at least one valid C program which, when fed to both boxes, would result in
them producing identical behaviors, by what means could one determine that
one of the black boxes ran a C program in legitimate fashion and the other
did not?
By trying other C programs. It wouldn't take long to discover that one
implementation is a complete sham that doesn't actually translate programs.
Post by s***@casperkitty.com
Does anything in the Standard require that implementations not be
viewed as black boxes?
For one thing, the fact that programs can reveal nearly any aspect of their
state by producing output. We can add debugging printfs to a program to have it
examine and report the states of objects at various points in the execution.

Nevertheless, blackboxes can be probed, and can be verified whether they
are the same or different, or whether they conform to some description.
Post by s***@casperkitty.com
Post by Kaz Kylheku
Post by s***@casperkitty.com
Generally, the purpose of a Standard is to provide a means of usefully
classifying partitioning things into categories of things that definitely
meet the Standard, those that definitely do not, and possibly a (hopefully
small) category of things not fitting in the other two.
That means to classify arises from the total of all the requirements given in
the document.
To meet a requirement is to conform; no fail to implement a (non-optional)
requirement is not to conform.
We can tell when a C compiler is broken in some way with regard to the
standard. Usually, some program is found to misbehave. The misbehavior is
reproduced in a portable program, and traced to an incorrectly implemented
or missing requirement. (The standard gives one interpretation to the
situation inside the program, but the result on the implementation differs.)
The Standard does not, from what I can tell, mandate that for any given
implementation there must exist more than one possible source file which,
when fed to the implementation, would not result in it exceeding some
resource limit.
How so? What the minium limits are and what they apply to is clearly
spelled out, and not determined by the implementation.

There is a vast number of maximally portable C programs which stay
within the limits.

(There are also programs to which we have to apply implementation-specific
reasoning in order to determine whther they stay within the limits.
E.g. we could make some contrived program which makes a large number of
memory allocations if, and only if, int is 16 bits wide.)
Keith Thompson
2015-10-14 19:44:32 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Keith Thompson
The standard (N1570 5.2.4.1) requires an implementation to
be able to translate and execute at least one program that contains
[...]
It doesn't say that that one program has to be strictly conforming
(though there's probably no good reason for it not to be).
Would a program that ignored its input and always output the string "This
is a diagnostic" be a "standard conforming C implementation"? If one were
to write a program which taxed all of the minimum limits but whose sole
purpose was to output the string "This is a diagnostic", feeding that
program into the aforementioned "C implementation" would cause it to
produce the behavior mandated by the Standard. Feeding any other well-
formed C program would cause it to behave as though the program blew out
the stack--a situation where the Standard imposes no requirements.
Feeding an ill-formed C program would result in a diagnostic.
You snipped an important part of my previous post:

The point of that requirement, BTW, is that the easiest way to
satisfy it is to create a *useful* implementation that is able
to translate and execute *many* different programs, because
the implementation doesn't impose arbitrary fixed limits.
An implementation that can handle one and only one program
might be "conforming", but it would not be useful or relevant.

The standard does not attempt to require all conforming
implementations to be useful. I can't think of a way it could do so.
All implementations have some capacity limits. It is not practical,
and perhaps not possible, to precisely define the set of programs
that do not exceed the limits of a reasonable implementation.

Since I haven't seen anyone selling perversely conforming but useless C
compilers that accept only a single program and print a single
meaningless diagnostic message for every translation unit, I suggest
that the standard has done its job reasonably well.
Post by s***@casperkitty.com
Clearly the authors of the Standard would not intend that such a thing be
considered a "standard conforming C implementation", but would it not meet
the requirements for such, given the way the Standard is written?
Sure it would -- but so what?

[...]
Post by s***@casperkitty.com
I would posit that it would be extremely useful to have standards for
programs and implementations that could identify a large set of programs
and a large set of compilers, such that feeding any program in the first
set to any compiler in the second would result in the compiler either
rejecting the program in a way that could be detected via Implementation-
Defined means, or running the program in such a way as to satisfy that
program's requirements.
I would posit that we don't have that now, and yet we have a substantial
number of conforming and useful C compilers.
Post by s***@casperkitty.com
IMHO, good code should be written in such a fashion as to have one meaning,
and a good language should make it easy to achieve that. To use a Unicode
analogy, there is no requirement that a Unicode font regard &#x2603; as a
picture of a snowman, but there is a requirement that fonts refrain from
using that character code for other purposes. I would like to see C head
in a similar direction. While some might fear that would fragment the
language, I would suggest that it would instead do the opposite. If there
were a type for "sign-magnitude integer", then code which needs to perform
type punning between a sign-magnitude integer and a like-sized unsigned
integer would not compile on a two's-complement implementation which does
not support that type, but it would be possible for a two's-complement
implementation to add support for such a type without having to change
the semantics of code that doesn't need to use that type specifically.
It always comes back to type-punning, doesn't it?
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
James Kuyper
2015-10-14 20:18:50 UTC
Permalink
Raw Message
Post by Keith Thompson
Post by s***@casperkitty.com
Post by Keith Thompson
The standard (N1570 5.2.4.1) requires an implementation to
be able to translate and execute at least one program that contains
[...]
It doesn't say that that one program has to be strictly conforming
(though there's probably no good reason for it not to be).
Would a program that ignored its input and always output the string "This
is a diagnostic" be a "standard conforming C implementation"? If one were
Not quite: one thing a implementation of C is required to do is accept
any strictly conforming program (a freestanding implementation is only
required to accept a small well-specified subset of all strictly
conforming programs). (4.1p6) The standard does not define what "accept"
means in this context. Based upon common English usage, I've argued that
an implementation could satisfy this requirement by issuing the message
"Program accepted", without doing anything else with the program (I can
accept a gift without ever opening it). But I think that at a minimum,
you do need something like that included in your message.

Note, also, that an implementation is required to generate a diagnostic
message containing the specified tokens (6.10.5p1) if a #error directive
survives conditional compilation, and is prohibited from successfully
translating such a program. (4p4)

As far as I can see, that means that a fully conforming implementation
can use 5.2.4.1 to justify skipping all of the translation phases after
phase 4, for every program except the "one program", which is can handle
as a special case. However, it must correctly implement phases 1-4. I
call this the "minimally-conforming implementation".
Post by Keith Thompson
Post by s***@casperkitty.com
to write a program which taxed all of the minimum limits but whose sole
purpose was to output the string "This is a diagnostic", feeding that
program into the aforementioned "C implementation" would cause it to
produce the behavior mandated by the Standard. Feeding any other well-
formed C program would cause it to behave as though the program blew out
the stack--a situation where the Standard imposes no requirements.
Feeding an ill-formed C program would result in a diagnostic.
Note: "ill-formed" is a term with a specific meaning assigned to it by
the C++ standard, but not by the C standard. You could cause one kind of
confusion if you intended to cross-reference the C definition, and a
different kind of confusion if you didn't intend to cross-reference it.
I'd favor a term defined by neither standard (such as well-defined
behavior) to avoid such confusion.

...
Post by Keith Thompson
Since I haven't seen anyone selling perversely conforming but useless C
compilers that accept only a single program and print a single
meaningless diagnostic message for every translation unit, I suggest
that the standard has done its job reasonably well.
Obviously no one would buy it. I think it might be possible to give away
a minimally conforming implementation of C as a joke, though only to the
very small set of people who would appreciate the joke. I've
occasionally thought about using some small portion of my spare time to
create such an implementation, just to expand my understanding of
compilers and parsers - but "spare time" is one of the things that was
already in short supply before my twins got born, and has since
completely vanished from sight.
--
James Kuyper
s***@casperkitty.com
2015-10-14 20:41:38 UTC
Permalink
Raw Message
Post by James Kuyper
Not quite: one thing a implementation of C is required to do is accept
any strictly conforming program (a freestanding implementation is only
required to accept a small well-specified subset of all strictly
conforming programs). (4.1p6) The standard does not define what "accept"
means in this context. Based upon common English usage, I've argued that
an implementation could satisfy this requirement by issuing the message
"Program accepted", without doing anything else with the program (I can
accept a gift without ever opening it). But I think that at a minimum,
you do need something like that included in your message.
I think one of the options for "accepting" a program would be immediate
execution. An "implementation" that happened to output whatever the
program given to it would have produced as output if run on a more
"normal" implementation could be deemed to have "run" the program that
was fed to it.
Post by James Kuyper
Note, also, that an implementation is required to generate a diagnostic
message containing the specified tokens (6.10.5p1) if a #error directive
survives conditional compilation, and is prohibited from successfully
translating such a program. (4p4)
As far as I can see, that means that a fully conforming implementation
can use 5.2.4.1 to justify skipping all of the translation phases after
phase 4, for every program except the "one program", which is can handle
as a special case. However, it must correctly implement phases 1-4. I
call this the "minimally-conforming implementation".
Would a program that simply echoed "Here's a diagnostic:", followed by
the contents of the input file, suffice for the #error behavior? And
could other requirements be met by documenting that the stack size is
4K, but each evaluating any rvalue of any type may consume up to 5K of
stack? The fact that each rvalue of any type "may" consume up to 5K
wouldn't forbid the compiler from reducing the "stack usage" of programs
whose required output happened to match that of the minimally-conforming
implementation.
Post by James Kuyper
Obviously no one would buy it. I think it might be possible to give away
a minimally conforming implementation of C as a joke, though only to the
very small set of people who would appreciate the joke. I've
occasionally thought about using some small portion of my spare time to
create such an implementation, just to expand my understanding of
compilers and parsers - but "spare time" is one of the things that was
already in short supply before my twins got born, and has since
completely vanished from sight.
On a related note, I think the shortest conforming C program would probably
be something like an underscore, an uppercase letter (e.g. Q), and a
newline, since one could make a "C implementation" that using a shell
script that ran a compiler with _Q predefined as e.g.

int main(void) {return 42;}

in which case that short file would be a legitimate C program whose useful
purpose was to return the Answer to Life, the Universe, and Everything.
Kaz Kylheku
2015-10-13 18:23:12 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Wojtek Lerch
Post by s***@casperkitty.com
The problem is that there's no standardized means by which a programmer can
be sure that a compiler won't make certain inferences, and there's no longer
any reason to believe that compilers won't try to break code.
Huh? Compilers don't try to break code; it's programmers that write
broken code. If the programmer does his job and makes sure that his
code doesn't invoke undefined behaviour, the compiler will do its job
too, and the code will behave the way the language guarantees it to behave.
Suppose a library specifies that they store 16-bit data into a buffer
halfword-aligned and a particular endianness, but do not specify whether
they use type "short*" or "int*" for the purpose, and also specify that
they store 32-bit data word-aligned but likewise do not specify whether
they use type "int*" or "long*".
Another library expects to receive suitably-aligned 16-bit and 32-bit
data, but likewise does not specify the type used to read it.
If a program receives data from the first library and passes it to the
second, and it turns out the two libraries use different types with
identical representations, and and everything works until the newest
build system recognizes that some of the code paths which pass data
between the two libraries will cause memory to be written as one type
and read as another in a violation of the C89 rules, and consequently
decides to omit such code paths, causing the code to stop working, to
whom or what should the failure be attributed?
The failure is attributed to the situation of using a new compiler on old
code.

If this escapes into the wild, the failure can be attributed to a poor process:
letting loose a new compiler on old code and just blindly assume that
everything will be fine, combined with inadequate testing.

In any case, the only way this kind of situation will happen is if the compiler
has global optimizations (gcc has them) and they are turned on by default (not
the case).

Global optimizations means that there is information in a compiled translation
unit in order to further transform its code before linkage.

In fact, I have argued in the past that this violates ISO C.

A C program is made up of translation units, which are separately processed
(translated) until the translation phase of linkage. According to ISO C,
semantic translation doesn't take place at linkage any more.

Therefore, the situation you describe requires a nonconforming compiler: one
which separately translates the two libraries such that they work properly
as before (i.e. in the absence of the knowledge about the cross-module
type punning issue). Then, when the two are linked together, it has to realize
that type punning is going on and wreck the code. This means it is continuing
to perform semantic analysis and translation into translation phase 8.

For instance, I'm looking at C99, which says that in translation phase 7,
the second last phase, "[t]he resulting tokens are syntactically and
semantically analyzed and translated as a translation unit."
The in the last phase, phase 8, "[a]ll external object and function references
are resolved. [... etc]". No mention is made of anything that resembles
analysis, translation or anything to do with such semantics.
Analysis and translation activities must not leak out of phase 7 into 8.

In summary, as you can see, the ISO standard is on your side here (or at least
was, as of C99). Conforming C compilers must not look for cross-module type
punning and break it on purpose, calling that optimization.
--
Music DIY Mailing List: http://www.kylheku.com/diy
ADA MP-1 Mailing List: http://www.kylheku.com/mp1
s***@casperkitty.com
2015-10-13 20:37:37 UTC
Permalink
Raw Message
Post by Kaz Kylheku
In fact, I have argued in the past that this violates ISO C.
I don't think it does, though I think a better-designed standard would render
the point moot.

It would be legal for an implementation to allocate two bytes of physical
memory to each "char"; one would be visible to the programmer, and the
other would be used by the implementation to keep track of the type that was
used to write the first. As long as the implementation cleared the type
information in certain cases when compelled to do so by the Standard, and
accepted any type of read from memory whose type information had been
cleared in such fashion, it would be entitled to do anything it likes if
an implementation were to read using one pointer type data written using
a different, incompatible, type. If an implementation could be configured
to trap into an attached debugger, such a facility could actually be useful
(IMHO the potential usefulness of such a facility would have been a much
better excuse than "optimization" for the rule in its present form).

Going beyond the above, it would be legitimate for an implementation to
maintain in addition to the RAM used by the main program execution, a
few extra copies of RAM used to evaluate speculative execution paths. It
would thus be possible to have a run-time implementation determine that a
program was going to read memory in violation of the Strict Aliasing
Rule without having to perform all of the preceding side-effects first.

All of these things could be done legitimately by the implementation at
run-time, and the Standard clearly applies "as-if" semantics to its rules.

IMHO, a bigger point of contention I would make is that Undefined Behavior
should be required to honor data dependencies and causality. Given:

int ch = getch();
if (ch < 34) ch = (ch-32) << 1; else ch <<= ch;

on a 32-bit machine the above code could be guaranteed to perform Undefined
Behavior regardless of what character is typed, but I would argue that even
so the compiler should not be entitled to move the behavior ahead of the
"getch()". I would further suggest that while the time taken to execute a
piece of code, even if infinite, should not be considered a side-effect that
implementations have to uphold, endless looping should not in and of itself
be deemed to invoke completely Undefined Behavior. Given:

void blah(int x)
{
unsigned char y = 0;
if (x==23) fprintf(stderr, "WOW!\n");
while(x != 23)
y+=2;
fprintf(stderr, "MOO!\n");
fprintf(stderr, "x==%d\n",x);
fprintf(stderr, "y & 1 ==%d\n",y);
fprintf(stderr, "y==%d\n",y);
}

I would suggest that if "blah" is called with x equal to 12, a compiler
should be allowed to run everything up until it's about to run the last
printf, whereupon it should be required to either stall or trap in
an Implementation-Defined fashion (a compiler could figure out that the
values output by all printf statements before the last will never change
in the course of the loop, and could thus legitimately be predetermined
before the loop even runs. The last statement, however, would imply a
data dependency on a computation which is updated during the loop, and
I would suggest that a good language should require compilers to uphold
that.
Jakob Bohm
2015-10-13 20:55:44 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Kaz Kylheku
In fact, I have argued in the past that this violates ISO C.
I don't think it does, though I think a better-designed standard would render
the point moot.
It would be legal for an implementation to allocate two bytes of physical
memory to each "char"; one would be visible to the programmer, and the
other would be used by the implementation to keep track of the type that was
used to write the first. As long as the implementation cleared the type
information in certain cases when compelled to do so by the Standard, and
accepted any type of read from memory whose type information had been
cleared in such fashion, it would be entitled to do anything it likes if
an implementation were to read using one pointer type data written using
a different, incompatible, type. If an implementation could be configured
to trap into an attached debugger, such a facility could actually be useful
(IMHO the potential usefulness of such a facility would have been a much
better excuse than "optimization" for the rule in its present form).
Going beyond the above, it would be legitimate for an implementation to
maintain in addition to the RAM used by the main program execution, a
few extra copies of RAM used to evaluate speculative execution paths. It
would thus be possible to have a run-time implementation determine that a
program was going to read memory in violation of the Strict Aliasing
Rule without having to perform all of the preceding side-effects first.
All of these things could be done legitimately by the implementation at
run-time, and the Standard clearly applies "as-if" semantics to its rules.
IMHO, a bigger point of contention I would make is that Undefined Behavior
int ch = getch();
if (ch < 34) ch = (ch-32) << 1; else ch <<= ch;
on a 32-bit machine the above code could be guaranteed to perform Undefined
Behavior regardless of what character is typed, but I would argue that even
so the compiler should not be entitled to move the behavior ahead of the
"getch()". I would further suggest that while the time taken to execute a
piece of code, even if infinite, should not be considered a side-effect that
implementations have to uphold, endless looping should not in and of itself
void blah(int x)
{
unsigned char y = 0;
if (x==23) fprintf(stderr, "WOW!\n");
while(x != 23)
y+=2;
fprintf(stderr, "MOO!\n");
fprintf(stderr, "x==%d\n",x);
fprintf(stderr, "y & 1 ==%d\n",y);
fprintf(stderr, "y==%d\n",y);
}
I would suggest that if "blah" is called with x equal to 12, a compiler
should be allowed to run everything up until it's about to run the last
printf, whereupon it should be required to either stall or trap in
an Implementation-Defined fashion (a compiler could figure out that the
values output by all printf statements before the last will never change
in the course of the loop, and could thus legitimately be predetermined
before the loop even runs. The last statement, however, would imply a
data dependency on a computation which is updated during the loop, and
I would suggest that a good language should require compilers to uphold
that.
Unfortunately, your idea of ignoring infinite loops is problematic for
any existing code which uses infinite loops deliberately, regardless of
data dependencies.

Example 1:

/* This is common kernel code on CPUs that don't have a low power
* idle function, such as the x86 HLT instruction or the 6800 STOP
* instruction
*/

int thread_idle(void *arg) {
struct processor *pProc = arg;

os_pin_thread_to_cpy(__cur_thread, pProc);

for(;;) {}

assert(0); /* Should NEVER get here */
return 0; /* Suppress warning about not returning a value */
}


...
int os_main(...) {
...
for (loop over installed processors) {
os_start_thread(thread_idle, pProcessor);
}
...
}

Example 2:

void _assertion_failed(const char *msgtxt) {
fflush(stdout);
fputs(stderr, "\nAssertion failed: ");
fputs(stderr, msgtxt);
fflush(stderr);
_tryexitprocess(SOME_ERROR_CONSTANT);
/* Blech, memory state is so badly damaged we can't even return to
* the OS, at least avoid getting any further into trouble
*/
for (;;) { /* Do not proceed */
}
}


Enjoy

Jakob
--
Jakob Bohm, CIO, Partner, WiseMo A/S. https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark. Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded
s***@casperkitty.com
2015-10-13 21:39:47 UTC
Permalink
Raw Message
Post by Jakob Bohm
Unfortunately, your idea of ignoring infinite loops is problematic for
any existing code which uses infinite loops deliberately, regardless of
data dependencies.
I agree that in some application fields there is a need for a goto-self
loop. On the other hand, if the Standard defined macros for
__SEQUENCED_SIDE_EFFECT() and __UNSEQUENCED_SIDE_EFFECT(), with a proviso
that any potentially-endless loop which does not contain any other side-
effect must include one of the above, I would suggest that adding one of
the above macros to such a loop would in many cases make code clearer and
should not adversely affect performance in any event except in those cases
where there really was no need to delay code following the loop.

For many application purposes, however, I would suggest that it is useful
to allow a compiler to transform something like:

void honk_and_maybe_hoot(int hoot_count, int hoot_freq)
{
honk();
for (int i=0; i<hoot_count; i++)
hoot(hoot_freq);
}
...
void calc_freq_honk_hoot(int hoots, int p2)
{
honk_and_maybe_hoot(hoots, slow_calculation_with_no_side_effects(p2));
}

into:

void calc_freq_honk_hoot(int hoots, int p2)
{
honk();
if (hoots > 0)
{
int freq = slow_calculation_with_no_side_effects(p2);
for (int i=0; i<hoots; i++)
{
hoot(freq);
}
}

In the event that slow_calculation_with_no_side_effects finishes, the
later version of the code will be equivalent to the former except that it
will run must faster when "hoots" is negative or zero. I think there is
some considerable value, for some application fields, to letting a compiler
make the substitution even in cases where it can't prove that the slow
calculation would ever complete.

Unfortunately, the present C rules specify that endless loops with no
side-effects have completely undefined behavior. While I would favor
in some application fields letting compilers rearrange code as shown
above, and while I would favor allowing for the existence of an
implementation-defined "endless loop trap", the present rules go way
beyond that, to the point that if a program is supposed to search for
solutions to a problem until it finds one, and a compiler is able to
analyze the program sufficiently to recognize that the problem has no
solution, the compiler would be allowed to do anything it likes.
Requiring programmers to either ensure that loop termination condition
can actually arise or else waste time and code executing some unwanted
side-effect (since Standard C doesn't define any dummy side effects)
doesn't seem very helpful in cases where the whole reason for the code's
existence is that the programmer doesn't know whether the loop is going
to terminate.
Keith Thompson
2015-10-13 22:00:02 UTC
Permalink
Raw Message
***@casperkitty.com writes:
[...]
Post by s***@casperkitty.com
Unfortunately, the present C rules specify that endless loops with no
side-effects have completely undefined behavior.
[...]

Only if the controlling expression is not a constant expression. Even
then, the standard only permits the compiler to assume that the loop
terminates. It's not clear that that leads to undefined behavior
(though IMHO the current wording is bad enough that one could argue
either way).

N1570 6.8.5p6.
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
s***@casperkitty.com
2015-10-13 22:30:02 UTC
Permalink
Raw Message
Post by Keith Thompson
Only if the controlling expression is not a constant expression. Even
then, the standard only permits the compiler to assume that the loop
terminates. It's not clear that that leads to undefined behavior
(though IMHO the current wording is bad enough that one could argue
either way).
In the real world, an invitation to assume something implies a promise that
if the recipient of the invitation performs certain actions which pose
unexpected costs because the assumption proved false, the party tendering
the invitation will assume responsibility for those costs. The invitation
would *not*, however, imply that a recipient who determined that the only
way the assumption could prove true was if some other condition applied,
would be entitled to behave as though that latter condition were true.

Because the C Standard says that programs "may assume" that loops terminate,
but fails to specify what they're allowed to do on the basis of that
assumption, I see no reason why it would be unlawful for a program which
was able to conclude that it would be impossible for a loop to terminate
after the 2,147,483,648th repetition to initialize a 32-bit counter to zero
and increment it once each loop. If the loop terminates like it is
supposed to, the existence of the counter will not have any improper
effect on the program. If the loop doesn't terminate within that number
of repetitions, the program would have Undefined Behavior.
Jakob Bohm
2015-10-13 22:03:34 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Jakob Bohm
Unfortunately, your idea of ignoring infinite loops is problematic for
any existing code which uses infinite loops deliberately, regardless of
data dependencies.
I agree that in some application fields there is a need for a goto-self
loop. On the other hand, if the Standard defined macros for
__SEQUENCED_SIDE_EFFECT() and __UNSEQUENCED_SIDE_EFFECT(), with a proviso
that any potentially-endless loop which does not contain any other side-
effect must include one of the above, I would suggest that adding one of
the above macros to such a loop would in many cases make code clearer and
should not adversely affect performance in any event except in those cases
where there really was no need to delay code following the loop.
For many application purposes, however, I would suggest that it is useful
void honk_and_maybe_hoot(int hoot_count, int hoot_freq)
{
honk();
for (int i=0; i<hoot_count; i++)
hoot(hoot_freq);
}
...
void calc_freq_honk_hoot(int hoots, int p2)
{
honk_and_maybe_hoot(hoots, slow_calculation_with_no_side_effects(p2));
}
void calc_freq_honk_hoot(int hoots, int p2)
{
honk();
if (hoots > 0)
{
int freq = slow_calculation_with_no_side_effects(p2);
for (int i=0; i<hoots; i++)
{
hoot(freq);
}
}
In the event that slow_calculation_with_no_side_effects finishes, the
later version of the code will be equivalent to the former except that it
will run must faster when "hoots" is negative or zero. I think there is
some considerable value, for some application fields, to letting a compiler
make the substitution even in cases where it can't prove that the slow
calculation would ever complete.
Unfortunately, the present C rules specify that endless loops with no
side-effects have completely undefined behavior. While I would favor
in some application fields letting compilers rearrange code as shown
above, and while I would favor allowing for the existence of an
implementation-defined "endless loop trap", the present rules go way
beyond that, to the point that if a program is supposed to search for
solutions to a problem until it finds one, and a compiler is able to
analyze the program sufficiently to recognize that the problem has no
solution, the compiler would be allowed to do anything it likes.
Requiring programmers to either ensure that loop termination condition
can actually arise or else waste time and code executing some unwanted
side-effect (since Standard C doesn't define any dummy side effects)
doesn't seem very helpful in cases where the whole reason for the code's
existence is that the programmer doesn't know whether the loop is going
to terminate.
My point (which you sorely missed) is that in *sane* compilers (which
you seem to be favoring in any other argument than this one), a
non-terminating loop *is* a side effect which the programmer probably
cares about regardless if it is intentional or not.

Now I most certainly disagree with the acceptability of any
implementation which does anything but spin the CPU until externally
terminated when confronted with an actual infinite loop.

I also strongly oppose any introduction of run time traps into the C
language except where explicitly requested by the programmer. There
are traditionally allowed exceptions for non-hypothetical invalid
pointer dereference, division by 0 and (on some platforms) division by
very small number.

There are also common (possibly standard) functions that allow the
programmer to explicitly request that some unusual floating point
operations may cause a trap.

Now here is an example of an unintentional infinite loop that the
programmer would still want the compiler to honor:

#include <stdio.h>

/* Imagine a much larger program */

static unsigned long foo(void)
{
unsigned long i, j;

j = 2;
for (i = 0; i < 10; j++) {
j <<= 1;
}

return j;
}

static unsigned long bar(void)
{
unsigned long i, j;

j = 2;
for (i = 0; i < 10; i++) {
j *= 3;
}

return j;
}

int main(int argc, char**argv)
{
unsigned long twoten, threeten;

puts("Begin"); /* debug */
twoten = foo();
puts("foo worked"); /* debug */
threeten = bar();
puts("bar worked"); /* debug */

printf("2^10=%lu 3^10=%lu\n", twoten, threeten);

return (argc != 1);
}

If the compiler started moving around the accidental infinite loop in
foo(), the programmer could be mislead into thinking his program was
failing elsewhere, preventing him from fixing the bug. (Note: There
are many scenarios where using a real single-stepping debugger is not
possible).


Enjoy

Jakob
--
Jakob Bohm, CIO, Partner, WiseMo A/S. https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark. Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded
s***@casperkitty.com
2015-10-13 23:06:39 UTC
Permalink
Raw Message
Post by Jakob Bohm
My point (which you sorely missed) is that in *sane* compilers (which
you seem to be favoring in any other argument than this one), a
non-terminating loop *is* a side effect which the programmer probably
cares about regardless if it is intentional or not.
My requirements for a compiler to be considered "sane" are:

1. It must support one or more modes which satisfies a relatively strict
clearly-defined causal behavioral model; it may also support modes with
various looser behavioral models.

2. Even in modes with somewhat looser behavioral models, sufficient
directives must exist to allow code to achieve the same behavior as
would be achieved under a looser model, without adversely affecting
the performance of code evaluated using the looser model.

Putting those two things together, I would suggest that someone whose
code might contain loops with non-constant controlling expressions whose
only important side-effect is their failure to terminate should start
using a compiler in a mode which will honor such side-effects, but should
add either __SEQUENCED_SIDE_EFFECT() or __UNSEQUENCED_SIDE_EFFECT()
directives to the code within all such loops. Once that is done, the
programmer may then enable compiler options to enable more optimizations
based upon assumed loop termination and/or insert safeguards so that loops
reaching a point where termination would be impossible can trigger an
implementation-defined trap.

There can be huge performance benefits to allowing compilers to rearrange
aspects of a program that a programmer doesn't care about. What's important,
that some compiler writers seem to miss, such an ability is only useful when
useful there are adequate means by which the programmer can maintain enough
control over program behavior to meet requirements without having to ask
the computer to perform operations that are not of interest. If for some
reason a particular CPU would issue a hardware trap if code fell into an
endless loop that didn't change anything in memory, a compiler might need
to have the __UNSEQUENCED_SIDE_EFFECT() macro expand to an increment of a
volatile variable, but in that case the operation would be of interest
since it would guard against a hardware trap. It should not, however, be
necessary for a program to access a meaningless volatile variable purely
for the purpose of preventing a compiler from making unwanted inferences.
Post by Jakob Bohm
Now I most certainly disagree with the acceptability of any
implementation which does anything but spin the CPU until externally
terminated when confronted with an actual infinite loop.
If a loop weren't infinite, but would instead run for 500,000,000,000 years,
performing no I/O and accessing no volatile variables, a compiler would be
fully entitled to defer execution of the loop until code needed a value
which could not be computed any other way. If code never needed any value
that was computed in the loop, it would be free to skip the loop altogether.

I would suggest that in places where a programmer would want a loop with a
non-constant control condition to run endlessly, adding a directive to make
such intention clear would be a good thing, especially since in the absence
of a sequenced side-effect a compiler would be entitled to defer any earlier
side-effects the program might have produced until after the loop completes.

If my stance here seems inconsistent with my stance on the strict aliasing
rule, note I am specifying here a means by which any program which would
need an endless loop with a non-constant condition could request that using
a directive which would have no effect on code generation except in those
cases where it was needed to prevent unwanted compiler behavior.
Post by Jakob Bohm
I also strongly oppose any introduction of run time traps into the C
language except where explicitly requested by the programmer. There
are traditionally allowed exceptions for non-hypothetical invalid
pointer dereference, division by 0 and (on some platforms) division by
very small number.
There are many purposes for which various traps are useful. What is
important is that their existence be clearly defined by the implementation
documentation (it would be helpful, though not necessary, for their effects
to also be defined). Programmers should reject any implementation whose
trapping behavior could not be guaranteed to meet their requirements.
Post by Jakob Bohm
Now here is an example of an unintentional infinite loop that the
...
Post by Jakob Bohm
If the compiler started moving around the accidental infinite loop in
foo(), the programmer could be mislead into thinking his program was
failing elsewhere, preventing him from fixing the bug. (Note: There
are many scenarios where using a real single-stepping debugger is not
possible).
If a programmer wants to ensure that code gets executed in a particular
sequence, the programmer should either compile in a mode that offers that
guarantee, or should add __SEQUENCED_SIDE_EFFECT() directives to the code.
There are many situations where it's possible for good compilers to achieve
2:1 or better speedups on code by rearranging the order in which various
operations are performed. While I agree 100% that it's vital that there
be ways of forcing certain parts of the code to execute in rigid sequence,
for many kinds of application it's better to give the compiler flexibility.

Note that given something like:

uint64_t time_blah(uint32_t x)
{
uint64_t total;
for (uint32_t i; i<1000000; i++)
total+=blah(x);
return total;
}

a compiler that could determine that blah() had no side-effects would be
entitled to rewrite the code as:

uint64_t time_blah(uint32_t x)
{
return 1000000LL*blah(x);
}

which would in most cases be an improvement, but would of course render any
benchmarks useless.
Kaz Kylheku
2015-10-13 21:31:56 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Kaz Kylheku
In fact, I have argued in the past that this violates ISO C.
I don't think it does, though I think a better-designed standard would render
the point moot.
I suspect you might not be correctly resolving what "this" refers to in my
sentence.
s***@casperkitty.com
2015-10-13 21:54:19 UTC
Permalink
Raw Message
Post by Kaz Kylheku
Post by s***@casperkitty.com
Post by Kaz Kylheku
In fact, I have argued in the past that this violates ISO C.
I don't think it does, though I think a better-designed standard would render
the point moot.
I suspect you might not be correctly resolving what "this" refers to in my
sentence.
I believe you were talking about the idea of a compiler drawing inferences
by reading into other translation units.

I would suggest that such a thing would only be considered a violation of
the Standard if it would result in the code behaving in a fashion which
would not otherwise be allowable under the Standard.

As written, the Standard says that if code writes memory as one type and
reads it as another, and the combination of types is not one that is
expressly allowed, an implementation is allowed to do anything it likes.
Nothing in the Standard specifies what means an implementation can use
to determine that an invalid read has occurred or will occur. Even if
the Specification expressly forbade the linker from analyzing the
relationships between compilation units, that wouldn't preclude the
possibility of an implementation trapping attempts to write memory as
one type in one compilation unit and read it as another type in another
compilation unit.
Kaz Kylheku
2015-10-14 02:57:48 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Kaz Kylheku
Post by s***@casperkitty.com
Post by Kaz Kylheku
In fact, I have argued in the past that this violates ISO C.
I don't think it does, though I think a better-designed standard would render
the point moot.
I suspect you might not be correctly resolving what "this" refers to in my
sentence.
I believe you were talking about the idea of a compiler drawing inferences
by reading into other translation units.
I would suggest that such a thing would only be considered a violation of
the Standard if it would result in the code behaving in a fashion which
would not otherwise be allowable under the Standard.
That's a ridiculous tautology.
Post by s***@casperkitty.com
As written, the Standard says that if code writes memory as one type and
reads it as another, and the combination of types is not one that is
expressly allowed, an implementation is allowed to do anything it likes.
In the situation of the two libraries that you described, the implementation
cannot tell that such a thing has happened. The behavior can be inferred from
the bitwise representation which is written by one library and read by the
other.

Detecting that type punning is going on as data are passed between two
libraries requires semantic analysis, and it requires that analysis to take
place in a translation phase where analysis and translation is understood to be
complete.

Changing the behavior of the code to break the libraries requires continued
translation, not only analysis.

So, your earlier worry that this situation can break due to silly rules in the
standard is unwarranted; you ought to be relieved that you can reasonably
have certain expectations between translation unit boundaries.
Post by s***@casperkitty.com
Nothing in the Standard specifies what means an implementation can use
to determine that an invalid read has occurred or will occur.
Yes, however, we deduce that some means are improper. We can also rule
out mechanisms which require time to flow backwards, or various
violations of physics.
Post by s***@casperkitty.com
Even if
the Specification expressly forbade the linker from analyzing the
relationships between compilation units, that wouldn't preclude the
possibility of an implementation trapping attempts to write memory as
one type in one compilation unit and read it as another type in another
compilation unit.
Yes it would; in order to trap, the implementation needs a "legal pretext" for
doing so: it has to distinguish the allegedly incorrect accesses from good ones.

There has to be something rotten about the bits themselves; they have to be
a "trap representation".

But no such thing is the case; they have the expected representation with no
funny bits.

If they have a trap representation, then the developers trying to make this
stuff work have an actual problem: the architecture has changed and the
representations between the two libraries not compatible.
Kaz Kylheku
2015-10-11 19:12:29 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
If one takes the view that it is impossible to know whether a program's
behavior will meet requirements when it performs actions whose behavior is
constrained by neither the C Specification nor platform documentation, that
would imply that for many fields, any useful program must never invoke
Undefined Behavior for any combination of inputs.
"Undefined Behavior" only means that the standard doesn't have requirements
for some construct.

It doesn't imply that the construct is wrong.

For example, __asm__ ("whatever") has undefined behavior.

Other than some completely trivial utilities, no real-world C program is
free of undefined behavior.

Calling a platform-specific library function is undefined behavior; it meets
the definition of a non-portable construct for which the standard imposes no
requirements.
Post by s***@casperkitty.com
This would in turn
imply that in all situations where an optimizer would be able to improve
the "efficiency" of a program by making UB-based inferences about the input
data it would receive, the resulting executable would be useless. I fail
to see much value in optimization features that are only effective on
useless programs.
Optimizers don't make "UB based inferences". They make "NON-UB based
inferences": inferences based on the belief that the program won't invoke
undefined behavior.

(Where "undefined behavior", in this case, refers to behavior that is not
defined by the standard *AND* that is not defined by the compiler; i.e.
situations for which the standard hasn't made requirements, and the compiler
implementors haven't filled in any requirements, either.)
Post by s***@casperkitty.com
While I have no objection to the fact that the C Standard does not mandate
that compilers support any particular behavioral model for things like
overflow, I think it is unhelpful for the Committee to completely ignore
the fact that most platforms have historically provided some guarantees
surrounding overflow, and that a lot of code written to exploit such
It's the GCC people who are ignoring this. Programmers programming C on
mainstream machines expect signed integers to give them access to certain
wrapping behavior.

GCC (no longer) provides that.

It's certainly reasonable for the *standard* to leave the behavior undefined
(i.e. impose no requirements at all) because overflow is nonportable.

However, C implementations are expected to provide a model of basic types and
operations which "reveal the machine" to the programmer.

I agree with you in this way: it is much more valuable to have predictable
overflow for signed integers, than to have some crazy optimizations which break
on signed overflow.

It's really not the business of the standard, though: this is purely an
attitude problem on the part of the ignorant monkeys who are at the helm of
modern GCC development.

GCC isn't a set of tools that can be trusted any more.

"For chrissake, that compiler shouldn't have been allowed to graduate
from kindergarten. We're talking "sloth that was dropped on the head as
a baby" level retardation levels." -- Linus Torvalds on GCC 4.9
s***@casperkitty.com
2015-10-12 02:31:47 UTC
Permalink
Raw Message
Post by Kaz Kylheku
(Where "undefined behavior", in this case, refers to behavior that is not
defined by the standard *AND* that is not defined by the compiler; i.e.
situations for which the standard hasn't made requirements, and the compiler
implementors haven't filled in any requirements, either.)
Until fairly recently, compiler writers and programmers alike recognized a
distinction between two distinct kinds of Undefined Behavior, even though
outside of Annex L the authors of the C Standard have been blind to it.

Very few C programmers would dispute the notion that if a program writes to
memory which the compiler or runtime library could legitimately be expecting
to use, in undocumented fashion, for their own internal purposes, an
implementation would be under no obligation to limit the consequences of such
an action. Annex L would refer to that kind of thing as "Critical Undefined
Behavior".

Until recently, however, very few compiler writers would have disputed the
notion that things like integer overflow should generally be treated
differently except when targeting certain hardware which traps such things
in a fashion that cannot usefully be documented (e.g. where an integer
overflow that occurs during the cycle when a hardware interrupt arrives
will cause a control signal to change at the wrong time resulting in an
essentially random jump to program memory). On 99% of C platforms, a
calculation which resulted in an integer overflow would either trigger a
documented trap or would yield some arbitrary value (the numerical result
was completely predictable on some platforms, and less so on others, but
in many cases a simple guarantee that an overflow would have no effect
other than yielding some arbitrary value could be extremely helpful).

I would posit that in many cases, the value which programmers can receive
from even very loose guarantees is greater than the value of any
optimizations which can be obtained that way and could not be obtained
even more effectively, as well as more safely, using various forms of
__ASSUME directives.
Post by Kaz Kylheku
It's the GCC people who are ignoring this. Programmers programming C on
mainstream machines expect signed integers to give them access to certain
wrapping behavior.
I would like to see a standard means by which programs could indicate how
precisely they need overflow to wrap. For example, on a 16-bit platform,
given

int i,j; ...
long l=i*j;

some platforms would require more time to sign-extend an "int" result than
to use an "int*int->long" multiply instruction, and the result of storing
the full "long" value would not typically be surprising. A more quirky case
might be:

int i,j; ...
i*=j;
long l=i;

here it might be helpful for a compiler to store the full 32-bit value into
l even though logically it would seem "i" should only hold 16 bits. If code
can deal with an over-sized value in "l", efficiency could be improved by
allowing that, but I would suggest that code should use a directive to
indicate what it requires.
Post by Kaz Kylheku
It's really not the business of the standard, though: this is purely an
attitude problem on the part of the ignorant monkeys who are at the helm of
modern GCC development.
What should be the business of the Standard is to recognize the existence
of common guarantees, and provide a standard means via which code can say
what behaviors it requires.

I would like to see a standard set of headers and macros (which could
optionally invoke intrinsics) [working title: Universal eXtended C]
such that if X is a UXC-compliant compiler and Y is a strictly UXC-conforming
program, then feeding Y to X will result in one of the following:

1. X executes Y as intended.
2. X identifies at least one requirement of Y that X cannot support.

In particular, it would never result in:

3. X compiles Y, but there's no way of knowing whether X will behave as
intended.

Presently, if a program can't be written in strictly-conforming C, the
Standard provides no way of knowing whether the program will be usable on
any given compiler. Given that 99% of programs cannot usefully be written
in strictly-conforming C, the so-called "standard" really isn't much of
one.

Defining a standard for UXC would make it possible for a large fraction
of useful programs to meet a standard of strict compliance that actually
meant something, in many cases without requiring any changes to the code
itself [just adding a #include and some macro directives]. While it would
be highly unlikely that any compiler would be able to run all programs,
and while few programs would run on all compilers, it would be possible,
given a program and a compiler, to know whether that program would be
compatible with that compiler.
s***@casperkitty.com
2015-10-12 07:16:43 UTC
Permalink
Raw Message
Post by Kaz Kylheku
It's really not the business of the standard, though: this is purely an
attitude problem on the part of the ignorant monkeys who are at the helm of
modern GCC development.
GCC isn't a set of tools that can be trusted any more.
"For chrissake, that compiler shouldn't have been allowed to graduate
from kindergarten. We're talking "sloth that was dropped on the head as
a baby" level retardation levels." -- Linus Torvalds on GCC 4.9
I wonder if any of the people involved with gcc were responsible for the
silly type punning restrictions which were included in C89 but ignored by
pretty much everyone for a decade or more? The attitude given in the
rationale for including those restrictions is pretty heinous. Declaring
that existing production code which needs to do things that are not
possible under the new rules is "dubious" and thus need not be supported
shows a remarkable degree of contempt for the language and its users.
Kaz Kylheku
2015-10-12 16:28:56 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Kaz Kylheku
It's really not the business of the standard, though: this is purely an
attitude problem on the part of the ignorant monkeys who are at the helm of
modern GCC development.
GCC isn't a set of tools that can be trusted any more.
"For chrissake, that compiler shouldn't have been allowed to graduate
from kindergarten. We're talking "sloth that was dropped on the head as
a baby" level retardation levels." -- Linus Torvalds on GCC 4.9
I wonder if any of the people involved with gcc were responsible for the
silly type punning restrictions which were included in C89 but ignored by
pretty much everyone for a decade or more?
rationale for including those restrictions is pretty heinous. Declaring
that existing production code which needs to do things that are not
possible under the new rules is "dubious" and thus need not be supported
shows a remarkable degree of contempt for the language and its users.
Type punning is a garbage programming technique with few legitimate uses. It
breaks the integrity of the type system, and should only be allowed with the
use of loudly delineated escape hatches which contain all of its effects that
*can* becontained.

It is quite desirable for compilers to optimize based on the assumption
that objects aren't being misused due to abuses of the type system or
of pointer displacement beyond object boundaries and such.
s***@casperkitty.com
2015-10-12 17:33:33 UTC
Permalink
Raw Message
Post by Kaz Kylheku
Type punning is a garbage programming technique with few legitimate uses. It
breaks the integrity of the type system, and should only be allowed with the
use of loudly delineated escape hatches which contain all of its effects that
*can* becontained.
In some kinds of programming, type punning makes it possible for programmers
to speed up performance-critical code by a factor or two or more.

Much of C's success stems from the fact that implementations which could
reasonably enable such techniques, did so.

If the language provided escape hatches which would never cause any needless
degradation of performance, it might be reasonable to fault programmers who
fail to use them, but the fact that a lot of code is written to be faster
than the rules allow does not mean the code is defective--it means the rules
are defective.
Post by Kaz Kylheku
It is quite desirable for compilers to optimize based on the assumption
that objects aren't being misused due to abuses of the type system or
of pointer displacement beyond object boundaries and such.
It would be even more desirable for compilers to optimize based upon things
that programmers concerned about speed would be more than happy to let
the compilers know. For example, given:

int g;

void blah(float *fp)
{
g += foo();
g += bar();
g += 2;
*fp+=1;
g += biz();
g += boz();
}

in the absence of type punning rules, it would require five loads and five
stores of g. The type punning rule reduces that to four loads and four
stores. On the other hand, if the code were written as:

static __inline void do_blah(float *fp, int const restrict *gp)
{
*gp += foo();
*gp += bar();
*gp += 2;
*fp+=1;
*gp += biz();
*gp += boz();
}
void blah(float *fp)
{
do_blah(fp, &g);
}

a compiler that was willing to do the inline despite the size of the code
involved (since it's only in-lined once) would be able to reduce save an
additional three more loads/stores versus what would be possible using
type-based aliasing, and doesn't require type-based aliasing to accomplish
them.

While having to use an in-line method is rather obnoxious from a syntactical
standpoint, the semantics and performance would be are far superior to those
achievable via the C89 type punning rule, and the solution to the syntactical
ugliness would be to define a syntax to create a "restrict pointer" from an
lvalue and attach it to an identifier which would then behave as an lvalue
(e.g. so code could create the local identifier "g" which would hold a const
restrict pointer to global variale "g", and have it behave as a variable
rather than a pointer to one).
Keith Thompson
2015-10-10 20:37:23 UTC
Permalink
Raw Message
***@yahoo.co.uk writes:
[...]
Post by m***@yahoo.co.uk
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=33498
RESOLVED INVALID
That bug report includes this link:

http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html#more

which says:

Why can't you warn when optimizing based on undefined behavior?


People often ask why the compiler doesn't produce warnings
when it is taking advantage of undefined behavior to do an
optimization, since any such case might actually be a bug in
the user code. The challenges with this approach are that it
is 1) likely to generate far too many warnings to be useful -
because these optimizations kick in all the time when there is
no bug, 2) it is really tricky to generate these warnings only
when people want them, and 3) we have no good way to express
(to the user) how a series of optimizations combined to expose
the opportunity being optimized.

There's more.
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
s***@casperkitty.com
2015-10-10 21:15:27 UTC
Permalink
Raw Message
Post by Keith Thompson
People often ask why the compiler doesn't produce warnings
when it is taking advantage of undefined behavior to do an
optimization, since any such case might actually be a bug in
the user code. The challenges with this approach are that it
is 1) likely to generate far too many warnings to be useful -
because these optimizations kick in all the time when there is
no bug, 2) it is really tricky to generate these warnings only
when people want them, and 3) we have no good way to express
(to the user) how a series of optimizations combined to expose
the opportunity being optimized.
This is one of the reasons why I think the idea of using Undefined Behavior
for optimization is misguided. The only way such warnings can be useful
is if, in cases where a compiler is optimizing away code on the basis of
an assumption, there is a directive by which a programmer can tell the
compiler "I know XX is true; don't warn me when using that fact for
optimization". If such a directive exists, however, they could be used to
drive optimization even in cases where no Undefined Behavior was involved.

For example:

int pow10(int x)
{
if (x >= 1000000) return 6;
if (x >= 100000) return 5;
if (x >= 10000) return 4;
if (x >= 1000) return 3;
if (x >= 100) return 2;
if (x >= 10) return 1;
return 0;
}
int blah(int *x, int *pow)
{
*pow = pow10(x);
return x*x;
}
int hey(int x1, int *pow1, int x2, int *pow2)
{
blah(x1, pow1);
return blah(x2, pow2);
}

A hyper-modern compiler writer would pride himself on the fact that a
compiler which in-lined all the method calls eliminate the tests for
values 100000 and up since the "return x*x;" statement would cause
arithmetic overflow. If the need to prevent such optimization drove
the programmer to replace the return statement with

return x<10000u ? x*x : 0;

on the basis that the value would never be needed when x was larger
than 10000, a compiler might not be able to optimize out the "if"
text. Further, if the value of x2 would never exceed 999, the compiler
would have failed to capitalize on the fact that it didn't need the
first four "if" tests in the evaluation of pow10(x2).

Having a means of telling the compiler that x2 will be less than 1000,
and that the programmer won't care about the value of x*x in cases where
it exceeds 100000, would allow the above function to be optimized far
more effectively than is possible under Standard C, no matter how much
the compiler tries to exploit Undefined Behavior. Further, pushing the
the programmer to add a test which can't be optimized out is not a good
way to yield efficient code.
Keith Thompson
2015-10-09 15:47:12 UTC
Permalink
Raw Message
Post by m***@yahoo.co.uk
Post by Wojtek Lerch
Post by s***@casperkitty.com
Most of the actions which presently invoke Undefined Behavior will, on 99%
I don't have enough statistical data to judge the accuracy of your claim
about "most" and "99%", but you missed an important case: many compilers
these days put a lot of effort in optimization, and often make decisions
based on the assumption that the programmer has made sure to avoid
undefined behaviour. A smart optimizer can reshuffle a program's
operations to such a degree that running it with inputs that trigger
undefined behaviour can be completely different from what a human might
expect based on a naive reading of the C code.
int32_t array[128/4], v=0x00010203;
size_t x;
for (x=0; x < 128/4; x++) {
array[x] = v;
v += 0x01010101;
}
GCC optimizes this to a loop that overwrites all memory.
int32_t array[128/4], *p=array, v = 0x00010203;
do {
*p++ = v;
v += 0x01010101;
} while (v != 0x80818283);
Then it notices that v starts positive and increases, so it can
never be negative ... so it omits the test.
I think you made a mistake in your example; v never overflows.

If you omit the "/4", the final value of v does overflow (it would
be 0x80818283 in the absence of overflow).

Even with that change, gcc doesn't generate an infinite loop at
any optimization level (though in principle it could). I tried
gcc versions 4.8.4 and 5.2.0 in both 32-bit and 64-bit mode.
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
m***@yahoo.co.uk
2015-10-10 09:14:08 UTC
Permalink
Raw Message
Post by Keith Thompson
Post by m***@yahoo.co.uk
Post by Wojtek Lerch
Post by s***@casperkitty.com
Most of the actions which presently invoke Undefined Behavior will, on 99%
I don't have enough statistical data to judge the accuracy of your claim
about "most" and "99%", but you missed an important case: many compilers
these days put a lot of effort in optimization, and often make decisions
based on the assumption that the programmer has made sure to avoid
undefined behaviour. A smart optimizer can reshuffle a program's
operations to such a degree that running it with inputs that trigger
undefined behaviour can be completely different from what a human might
expect based on a naive reading of the C code.
int32_t array[128/4], v=0x00010203;
size_t x;
for (x=0; x < 128/4; x++) {
array[x] = v;
v += 0x01010101;
}
GCC optimizes this to a loop that overwrites all memory.
int32_t array[128/4], *p=array, v = 0x00010203;
do {
*p++ = v;
v += 0x01010101;
} while (v != 0x80818283);
Then it notices that v starts positive and increases, so it can
never be negative ... so it omits the test.
I think you made a mistake in your example; v never overflows.
I did. The increment should be 0x04040404 throughout. Sorry!
Post by Keith Thompson
If you omit the "/4", the final value of v does overflow (it would
be 0x80818283 in the absence of overflow).
Even with that change, gcc doesn't generate an infinite loop at
any optimization level (though in principle it could). I tried
gcc versions 4.8.4 and 5.2.0 in both 32-bit and 64-bit mode.
--
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
s***@casperkitty.com
2015-10-09 17:13:09 UTC
Permalink
Raw Message
Post by Wojtek Lerch
I don't have enough statistical data to judge the accuracy of your claim
about "most" and "99%", but you missed an important case: many compilers
these days put a lot of effort in optimization, and often make decisions
based on the assumption that the programmer has made sure to avoid
undefined behaviour. A smart optimizer can reshuffle a program's
operations to such a degree that running it with inputs that trigger
undefined behaviour can be completely different from what a human might
expect based on a naive reading of the C code.
I should have said 99% have *historically* done that, but my point was that
if C had specified things in the fashion I indicated compiler writers would
have added useful optimization constructs to the language rather than trying
to "re-purpose" actions which whose behavior was left undefined by the spec
*for the purpose of allowing implementations to make available their own
useful, documented, implementation-specific behaviors*.

I would suggest, for example, that N1570 6.5p7 (commonly called the "strict
aliasing rule" for people who find names easier to remember than numbers)
was likely intended to allow for the possibility that a compiler might
have an option to attempt to trap accidental accesses of wrong-type objects;
the provisions about allowing "char" type accesses were necessary to ensure
that it would be possible to have methods like "memcpy" which need to be
able to read and write things as bytes.

If the rule had been written for the purpose of optimization, it would have
left out the provisions that allow things to be read or written using
character types, but instead included a provision that if code writes
storage using one type and reads it using another (including "char"), it
must first invoke some intrinsic on that range of memory. On systems where
e.g. the floating-point and main processing units have separate caches,
allowing a compiler to omit cache synchronization after *((float*)p)=x;
even if that memory might next be read as "int" rather than "float" would
be a useful optimization *except* that exploiting it would greatly impair
the performance of all "char*" accesses including those which have nothing
do do with accessing memory bytes which hold floating-point data.

BTW, I would like to see the language spec move in a direction such that:

1. Existing compiler could be brought into compliance with the new spec
merely by adding some header files.

2. A substantial fraction (perhaps a majority) of existing code which
presently relies upon behaviors not included in the C Specification
could easily be modified such that its behavior would be fully
specified, but compilers would be allowed to either implement the
program according to specification or refuse compilation.

3. Writing code to allow for only one possible interpretation should not
be overly cumbersome compared with writing code which would yield the
desired behavior on some implementations but undesired behavior on
others.

4. Standardized intrinsics should be defined which would not impose any
new requirements on implementations, but instead ease them. For example,
it may be useful to have a 16-bit signed integer type "intf16_t" whose
storage would be identical to "int16_t", but which was subject to two
constraints:

a. An explicit typecast to "intf16_t" will behave as a typecast to
"int16_t", but...

b. Coercion of a value outside the -32768..32767 range to intf16_t via
means other than a typecast may have more loosely specified behavior.

Any compiler could simply make "intf16_t" be an alias of "int16_t", but
given "int32_t x(int16f_t p) { p++; return p; }" a compiler for a
32-bit platform would not be required add code to make 32767+1 wrap
to -32768.

I believe achievement of all those objectives should be fairly easy and
straightforward from a technical perspective; the only difficulty I can
see would be political interference from those who want to use Undefined
Behavior to make inferences about the inputs a program will need to
handle.
Keith Thompson
2015-10-09 19:30:17 UTC
Permalink
Raw Message
***@casperkitty.com writes:
[...]
Post by s***@casperkitty.com
I would suggest, for example, that N1570 6.5p7 (commonly called the "strict
aliasing rule" for people who find names easier to remember than numbers)
was likely intended to allow for the possibility that a compiler might
have an option to attempt to trap accidental accesses of wrong-type objects;
the provisions about allowing "char" type accesses were necessary to ensure
that it would be possible to have methods like "memcpy" which need to be
able to read and write things as bytes.
If the rule had been written for the purpose of optimization, it would have
left out the provisions that allow things to be read or written using
character types, but instead included a provision that if code writes
storage using one type and reads it using another (including "char"), it
must first invoke some intrinsic on that range of memory. On systems where
e.g. the floating-point and main processing units have separate caches,
allowing a compiler to omit cache synchronization after *((float*)p)=x;
even if that memory might next be read as "int" rather than "float" would
be a useful optimization *except* that exploiting it would greatly impair
the performance of all "char*" accesses including those which have nothing
do do with accessing memory bytes which hold floating-point data.
[...]

Here's what the C99 Rationale
http://www.open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10.pdf
says about the "strict aliasing rule" (section 6.5, page 59-60):

The types of lvalues that may be used to access an object have been
restricted so that an optimizer is not required to make worst-case
aliasing assumptions (see also 6.7.3.1)

In practice, aliasing arises with the use of pointers. A contrived
example to illustrate the issues is

int a;
void f(int * b)
{
a = 1;
*b = 2;
g(a);
}

It is tempting to generate the call to g as if the source
expression were g(1), but b might point to a, so this
optimization is not safe. On the other hand, consider

int a;
void f( double * b )
{
a = 1;
*b = 2.0;
g(a);
}

Again the optimization is incorrect only if b points to
a. However, this would only have come about if the address of
a were somewhere cast to double*. The C89 Committee has decided
that such dubious possibilities need not be allowed for.

In principle, then, aliasing only need be allowed for when
the lvalues all have the same type. In practice, the C89
Committee recognized certain prevalent exceptions:

* The lvalue types may differ in signedness. In the
common range, a signed integer type and its unsigned
variant have the same representation; and it was
felt that an appreciable body of existing code is
not "strictly typed" in this area.

* Character pointer types are often used in the
bytewise manipulation of objects; a byte stored
through such a character pointer may well end up
in an object of any type.

* A qualified version of the object’s type, though
formally a different type, provides the same
interpretation of the value of the object.
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
s***@casperkitty.com
2015-10-09 20:29:44 UTC
Permalink
Raw Message
Post by Keith Thompson
Here's what the C99 Rationale
http://www.open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10.pdf
While that may have been offered as a rationale for keeping the rule, I
don't think it has anything to do with why it was originally written
as it was. If the first example were written:

int a;
void f(int * restrict b)
{
a = 1;
*b = 2;
g(a);
}

the same optimization available in the second case would be available in
the first, even though "a" and "b" are the same type. Further, consider
the following two functions:

int x;
void f1(void)
{
x+=g(1);
x+=g(2);
x+=g(3);
}
void f2(void)
{
int temp=x;
temp+=g(1);
temp+=g(2);
temp+=g(3);
x=temp;
}

There are some platforms where f1 would be much faster than f2, and there
are some where f2 would be much faster than f1. If the behavior of g()
would not be adversely affected by either form, it would be helpful to
have a means of letting the compiler select whichever would be most
efficient, e.g.

void f3(void)
{
int temp __cache_of x;
temp+=g(1);
temp+=g(2);
temp+=g(3);
x = temp;
}

with the semantics that at any time the compiler could store the value
of temp to x at any time, and could trash the value in temp at any time
when its value was stored in x, provided that it reloaded x into temp
before using temp again [compilers which don't have any special handling
for the feature could handle code using it merely by defining a macro:

#define __cache_of =

It would be better for compilers to process __cache_of syntactically so
as to allow its use only in legitimate contexts, but the macro definition
would suffice to let the compiler run code using the directive].
Keith Thompson
2015-10-09 21:18:32 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Keith Thompson
Here's what the C99 Rationale
http://www.open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10.pdf
While that may have been offered as a rationale for keeping the rule, I
don't think it has anything to do with why it was originally written
as it was.
Without further evidence, I'll assume the Rationale as published by the
committee is accurate.
Post by s***@casperkitty.com
int a;
void f(int * restrict b)
{
a = 1;
*b = 2;
g(a);
}
the same optimization available in the second case would be available in
the first, even though "a" and "b" are the same type.
The "strict aliasing rule" was introduced in C89. The "restrict"
keyword wasn't added until C99.

[...]
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
s***@casperkitty.com
2015-10-09 22:24:37 UTC
Permalink
Raw Message
Post by Keith Thompson
The "strict aliasing rule" was introduced in C89. The "restrict"
keyword wasn't added until C99.
The quoted rationale was for C99, and my recollection of the history is that:

1. The actual rule goes back to K&R 1978 edition, and so its original
inclusion in C89 would have been a consequence of that. I don't know
where I can find the text of the 1978 edition to confirm.

2. There was discussion about whether or not to *keep* the rule in C99, and
the fact that C99 had a certain rationale for keeping the rule does not
imply that was the basis for the rule's existence in the first place.

If the rule does appear in the 1978 edition, I would regard as highly
implausible the idea that it was aimed at the sorts of optimizations for
which it has since been used, because not only is the rule very poorly
designed for that purpose, but the idea that such optimizations would be
applied to C would have been inconceivable in 1978.
s***@casperkitty.com
2015-10-09 23:04:13 UTC
Permalink
Raw Message
I just did some searching and it appears the same rationale was given in C89,
but can't find whether the requirement goes back before that.

In any case, if the rule did originate then, I would consider include it in
the top ten worst blunders in the language, since there are many useful
things which cannot be done efficiently without violating the rule, and
since everything useful that the rule accomplishes could have been done
better other ways.

Maybe the rule was invented for C89 and my nature simply compels me to
think there must actually have been a useful reason for it to have been
specified as it was (the rules would have made sense if it were used for
type validation).

In any case, the rule was largely ignored in the 1990s by compilers and
programmers alike, to the betterment of all.
Kaz Kylheku
2015-10-10 05:32:27 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
I just did some searching and it appears the same rationale was given in C89,
but can't find whether the requirement goes back before that.
In any case, if the rule did originate then, I would consider include it in
the top ten worst blunders in the language, since there are many useful
things which cannot be done efficiently without violating the rule, and
since everything useful that the rule accomplishes could have been done
better other ways.
Things are not that bleak.

Firstly, aliasing between bytes and other types is well-defined to an extent:
bytes of objects can be accessed through lvalues of character type.

Secondly, you can use a union to alias things "safely". Here, "safely" means
"not running afoul of strict aliasing".

If you want to reinterpret a 32 bit integer as a 32 bit float, and not
have that access optimized away, that's the way to do it: store the 32
bit integer into a 32-bit-integer-typed member of a union and then
access a 32-bit-float-typed member of the same union.
s***@casperkitty.com
2015-10-10 17:58:17 UTC
Permalink
Raw Message
Post by Kaz Kylheku
Secondly, you can use a union to alias things "safely". Here, "safely" means
"not running afoul of strict aliasing".
Unfortunately, from what I can tell, there are many cases where the rules are
insufficient to guarantee safety. For example, although the Standards
specify that certain pointer types have compatible representations, e.g.
given:

typedef union { uint16_t hh[2]; uint32_t w; } U1;
typedef union { uint16_t hh[2]; uint32_t ww[1]; } U2;

I think a compiler would be required to guarantee expected behavior if
something written using type U1 or U2 is read as its own type, uint16_t,
or uint32_t, or if something written as type uint16_t or uint32_t is
read out as its own type, U1, or U2.

I see nothing in in the Standard that would allow code to write as U1 and
read as U2, nor vice versa, without invoking Undefined Behavior.

I suppose that if programmers agreed on a convention that data should always
be read using unions but written as primitives that would allow readers and
writers to be compatible, but if p is a U1* it seems rather hokey to say:

*(uint32_t*)p = p->w + 1;

Is there something I'm missing?

Also, suppose code is supposed to receive a pointer to an array of pointers
to structures that have a known initial sequence but whose type is otherwise
unknown. For example:

typedef struct { uint32_t size; } SIZED_THING;
typedef struct { uint32_t size, int x; } INT_THING;
typedef struct { uint32_t size, double x; } DBL_THING;

int_thing1 = {sizeof INT_THING, 123};
int_thing2 = {sizeof INT_THING, 456};
dbl_thing1 = {sizeof DBL_THING, 12.3};
dbl_thing1 = {sizeof DBL_THING, 45.6};

INT_THING *int_thing_array[2] = {&int_thing1, &int_thing2};
DBL_THING *dbl_thing_array[2] = {&dbl_thing1, &dbl_thing2};
SIZED_THING *sized_thing_array[2] =
{(SIZED_THING*)&int_thing1, (SIZED_THING*)&dbl_thing2};

uint32_t total_size(SIZED_THING **arr , uint32_t count)
{
uint32_t i,tot=0;
for (i=0; i<count; i++)
tot += arr[i]->size;
return tot;
}

If there were not strict aliasing rule, it would be legal to pass either
int_thing_array or dbl_thing_array to the total_size method provided that
code used a typecast [it's too bad there's no "generic double-indirect
pointer" type, since void** specifically means a pointer to a void pointer
and not a pointer to something else].

Is there any practical way to have one method which can accept any of the
arrays while still allowing:

1. The owners of the arrays in question to access members directly (e.g.
int_thing_array[1]->x rather than ((INT_THING*)int_thing_array[1])->x
or something similar?)

2. The processing of additional types which may be defined in future, and
about which nothing is known beyond the fact that they start with a
"uint32_t size" member?

Historically, programmers could safely use such types, secure in the
knowledge that compiler writers were focused on more important things than
trying to find excuses to identify code whose meaning was not defined by
the language of the Standard, but whose meaning would historically have
been well understood and recognized as useful by 100% of compiler writers?

A lot of object-oriented frameworks make use of the latter pattern; is
there any efficient way to write such a thing without granting hyper-
modern compilers an excuse to break the code?
Keith Thompson
2015-10-09 23:18:30 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Keith Thompson
The "strict aliasing rule" was introduced in C89. The "restrict"
keyword wasn't added until C99.
The quoted rationale was for C99,
The quote was from the C99 Rationale document, but it referred
explicitly to the C89 committee:

The C89 Committee has decided that such dubious possibilities need
not be allowed for.
Post by s***@casperkitty.com
1. The actual rule goes back to K&R 1978 edition, and so its original
inclusion in C89 would have been a consequence of that. I don't know
where I can find the text of the 1978 edition to confirm.
You're saying that the strict aliasing rule is in K&R1? I don't
*think* that's correct, but it's hard to grep dead trees. I have
a paper copy of the book in front of me. I don't see anything
resembling the strict aliasing rule, and there are several passages
that suggest it was not in effect, though it does acknowledge that
some constructs (like using a pointer of any type or an integer as
the prefix of the -> operator) are not portable.

If there's something similar to the strict aliasing rule in K&R2,
I can check for a corresponding rule in K&R1.

Even earlier versions of the C Reference Manual (but not the main body
of K&R1) can be found at:

https://www.bell-labs.com/usr/dmr/www/cman.pdf
https://www.bell-labs.com/usr/dmr/www/cman74.pdf
Post by s***@casperkitty.com
2. There was discussion about whether or not to *keep* the rule in C99, and
the fact that C99 had a certain rationale for keeping the rule does not
imply that was the basis for the rule's existence in the first place.
I see no indication of such a discussion in the C99 Rationale; it seems
to describe, and implicitly endorse, a decision made by the C89
committee. That's not to say that such a discussion didn't take place,
but I'd be at least mildly surprised if it did.
Post by s***@casperkitty.com
If the rule does appear in the 1978 edition, I would regard as highly
implausible the idea that it was aimed at the sorts of optimizations for
which it has since been used, because not only is the rule very poorly
designed for that purpose, but the idea that such optimizations would be
applied to C would have been inconceivable in 1978.
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
s***@casperkitty.com
2015-10-10 00:05:27 UTC
Permalink
Raw Message
Post by Keith Thompson
The quote was from the C99 Rationale document, but it referred
The C89 Committee has decided that such dubious possibilities need
not be allowed for.
Fair enough. As noted in my succeeding post, I was able to find the
C89 rationale and identified the same text there. I still think the
attitude of the Committee as expressed in the above statement is totally
heinous for a group which is supposed to be codifying a language which
was already in use, and in which code using such "dubious possibilities"
in performance-critical code could often make it run twice as fast would
be possible otherwise.

I could offer a simple set of rules with the same purpose which would be
much easier to work with, allow better optimizations than are possible
under the C89 rule, and not interfere with any programming techniques,
"dubious" or not, that would have been possible in the rule's absence:

1. An implementation may only make use of this section if it defines a macro
__STRICT_ALIASING as a positive integer literal.

2. Using a pointer of one type to read data written as another type will
yield Undefined Behavior unless the __SYNC intrinsic has been used on
the memory holding the data between the read and the write, or unless
the implementation does not define the __STRICT_ALIASING macro as
defined above.

3. The intrinsic __SYNC(ptr, size) will clear allow 'size' bytes starting
at 'ptr' to be read as any type. Invocation with a zero size with a
valid or null pointer will have no effect. Invocation with a negative
size or a size which would extend past the object invokes Undefined
Behavior. Implementations may ignore one or both arguments.

4. The functions memcpy() and memmove() may be used on data of any type;
the destination shall be considered to have bee written as the same type
as the source.

Can you suggest any way in the C89 rules are better than the ones given
above? The existence of __SYNC would eliminate the need to special-case
reads and writes of character types, and would also make it possible for
code to safely do things like using 32-bit types to manipulate word-
aligned pairs of 16-bit values.
Post by Keith Thompson
You're saying that the strict aliasing rule is in K&R1? I don't
*think* that's correct, but it's hard to grep dead trees. I have
a paper copy of the book in front of me. I don't see anything
resembling the strict aliasing rule, and there are several passages
that suggest it was not in effect, though it does acknowledge that
some constructs (like using a pointer of any type or an integer as
the prefix of the -> operator) are not portable.
Maybe I should buy myself a copy of K&R1.
Post by Keith Thompson
Even earlier versions of the C Reference Manual (but not the main body
https://www.bell-labs.com/usr/dmr/www/cman.pdf
https://www.bell-labs.com/usr/dmr/www/cman74.pdf
I see no indication of such a discussion in the C99 Rationale; it seems
to describe, and implicitly endorse, a decision made by the C89
committee. That's not to say that such a discussion didn't take place,
but I'd be at least mildly surprised if it did.
It's possible my recollection of such things is fuzzy. I recall having
read various discussions of whether various rules were desirable or
undesirable but as to whether any such discussions were "official" or
were simply outsiders adding their own commentary I have no idea.
Keith Thompson
2015-10-10 02:51:06 UTC
Permalink
Raw Message
***@casperkitty.com writes:
[...]
Post by s***@casperkitty.com
Maybe I should buy myself a copy of K&R1.
Good luck finding one. (I think I bought mine in 1981.)
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
s***@casperkitty.com
2015-10-10 04:18:41 UTC
Permalink
Raw Message
Post by Keith Thompson
[...]
Post by s***@casperkitty.com
Maybe I should buy myself a copy of K&R1.
Good luck finding one. (I think I bought mine in 1981.)
There seem to be copies for sale under $10 on eBay and elsewhere.

BTW, what would you think of adding an intrinsic to the language which would
specify that set the "effective type" of a range of memory to "char", with
the semantics that the arguments may or may not be evaluated?

Existing compilers could support the intrinsic via an empty macro when they
do not require its use, and code which would require the functionality
implied by the intrinsic would only be able to run on compilers which would
require its use if those compilers actually support that functionality.

Also, what do you suppose the authors of the Standard would have suggested
as the proper way to write code which would need to be able to process 32-bit
chunks of halfword-per-pixel data without knowing the type which was used to
create it?
Kaz Kylheku
2015-10-10 05:24:32 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Keith Thompson
The "strict aliasing rule" was introduced in C89. The "restrict"
keyword wasn't added until C99.
1. The actual rule goes back to K&R 1978 edition, and so its original
inclusion in C89 would have been a consequence of that. I don't know
where I can find the text of the 1978 edition to confirm.
2. There was discussion about whether or not to *keep* the rule in C99, and
the fact that C99 had a certain rationale for keeping the rule does not
imply that was the basis for the rule's existence in the first place.
If the rule does appear in the 1978 edition, I would regard as highly
I don't think that it does. It didn't even occur to them to optimize
based on such things. Optimization in 1978 C was derived from the fact that
you can stuff multiple side effects into a C expression, and that the compiler
doesn't have to care about any underhanded ways in which those stuffed effects
interact with each other---regardless of their type.
s***@casperkitty.com
2015-10-10 16:25:42 UTC
Permalink
Raw Message
Post by Kaz Kylheku
I don't think that it does. It didn't even occur to them to optimize
based on such things.
The rule is horribly designed from an optimization perspective, but reasonably
designed from the perspective of what would be necessary to add type checking
to a diagnostic build using primitive compiler technology. I'm curious what
sorts of code the committee members had looked at when they formulated that
abomination, since code which runs twice as fast as code abiding by that rule
could run can hardly be called an "dubious".
James Kuyper
2015-05-15 20:51:33 UTC
Permalink
Raw Message
Post by Noob
[ Cross-posted to comp.std.c ]
As far as I understand (which may be not far enough),
"Implementation-defined behavior" = "unspecified behavior
where each implementation documents how the choice is made"
"Unspecified behavior" = "use of an unspecified value,
or other behavior where this International Standard
provides two or more possibilities and imposes no further
requirements on which is chosen in any instance"
When the standard qualifies a program construct as
"implementation-defined", the standard is supposed
to provide an exhaustive list (implicit or explicit)
of the allowed behaviors an implementation may choose
from. "Do something random" is typically not an option.
True - but choosing randomly is an option, so long as the chosen
behavior is on the list.
Post by Noob
I am afraid that you have fallen foul of a serious gotcha in the
standard. While that is ONE interpretation, it is not the one
held my the majority of WG14 when I was on it, which was that an
implementation was allowed to specify that the behaviour was
undefined. And, of course, an implementation is allowed to define
undefined behaviour, and many do.
If you regard that as hopelessly confusing and inconsistent, you
are not alone, but those of us who tried to get the mess improved
(it is not soluble) failed dismally. Some other languages try to
ensure that all implementation-defined behaviour has a specified
intent (and sometimes constraints on what may happen), and have a
generic statement that honouring the intent is expected.
The definitions I provided were copied from the C99 standard.
The last paragraph was just my own interpretation.
Is an implementation allowed to specify program constructs
identified as "implementation-defined" as having undefined
behavior? (What an awkward sentence...)
I believe not, because the standard defines what "undefined behavior"
means: "behavior, upon use of a nonportable or erroneous program
construct or of erroneous data, for which this International Standard
imposes no requirements" (3.4.3p1).

When the behavior is described by the standard as
"implementation-defined", the standard does impose some requirements:
namely that one of the "two or more possibilities" provided by the
standard must be chosen. Since "undefined behavior" says that the
standard imposes no requirements, it would be simply false for the
implementation's definition of that behavior to say "undefined behavior".

What an implementation is perfectly free to do is to document that it
makes the choice randomly (assuming that this is a correct description
of how the choice is made). Even if the process for making the choice
isn't random, if it's sufficiently complicated, it could be effectively
unpredictable.
Keith Thompson
2015-05-15 21:41:03 UTC
Permalink
Raw Message
Post by James Kuyper
Post by Noob
[ Cross-posted to comp.std.c ]
[...]
Post by James Kuyper
Post by Noob
"Implementation-defined behavior" = "unspecified behavior
where each implementation documents how the choice is made"
"Unspecified behavior" = "use of an unspecified value,
or other behavior where this International Standard
provides two or more possibilities and imposes no further
requirements on which is chosen in any instance"
When the standard qualifies a program construct as
"implementation-defined", the standard is supposed
to provide an exhaustive list (implicit or explicit)
of the allowed behaviors an implementation may choose
from. "Do something random" is typically not an option.
True - but choosing randomly is an option, so long as the chosen
behavior is on the list.
Post by Noob
I am afraid that you have fallen foul of a serious gotcha in the
standard. While that is ONE interpretation, it is not the one
held my the majority of WG14 when I was on it, which was that an
implementation was allowed to specify that the behaviour was
undefined. And, of course, an implementation is allowed to define
undefined behaviour, and many do.
If you regard that as hopelessly confusing and inconsistent, you
are not alone, but those of us who tried to get the mess improved
(it is not soluble) failed dismally. Some other languages try to
ensure that all implementation-defined behaviour has a specified
intent (and sometimes constraints on what may happen), and have a
generic statement that honouring the intent is expected.
The definitions I provided were copied from the C99 standard.
The last paragraph was just my own interpretation.
Is an implementation allowed to specify program constructs
identified as "implementation-defined" as having undefined
behavior? (What an awkward sentence...)
I believe not, because the standard defines what "undefined behavior"
means: "behavior, upon use of a nonportable or erroneous program
construct or of erroneous data, for which this International Standard
imposes no requirements" (3.4.3p1).
When the behavior is described by the standard as
namely that one of the "two or more possibilities" provided by the
standard must be chosen. Since "undefined behavior" says that the
standard imposes no requirements, it would be simply false for the
implementation's definition of that behavior to say "undefined behavior".
But the standard doesn't always provide these "two or more
possibilities".

For example, N1570 5.2.4.2.2p8 describe the floating-point rounding
behavior for values of FLT_ROUNDS of -1, 0, 1, 2, and 3, and the says:

All other values for FLT_ROUNDS characterize implementation-defined
rounding behavior.

It doesn't specify the choice of behavior beyond saying that it's
"rounding behavior".

And N1570 6.2.4p4 says:

The result of attempting to indirectly access an object with thread
storage duration from a thread other than the one with which the
object is associated is implementation-defined.

I see no restrictions there at all, except that the implementation must
document the behavior somehow.

[...]
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
James Kuyper
2015-05-15 22:17:28 UTC
Permalink
Raw Message
...
Post by Keith Thompson
Post by James Kuyper
Post by Noob
Is an implementation allowed to specify program constructs
identified as "implementation-defined" as having undefined
behavior? (What an awkward sentence...)
I believe not, because the standard defines what "undefined behavior"
means: "behavior, upon use of a nonportable or erroneous program
construct or of erroneous data, for which this International Standard
imposes no requirements" (3.4.3p1).
When the behavior is described by the standard as
namely that one of the "two or more possibilities" provided by the
standard must be chosen. Since "undefined behavior" says that the
standard imposes no requirements, it would be simply false for the
implementation's definition of that behavior to say "undefined behavior".
But the standard doesn't always provide these "two or more
possibilities".
For example, N1570 5.2.4.2.2p8 describe the floating-point rounding
All other values for FLT_ROUNDS characterize implementation-defined
rounding behavior.
It doesn't specify the choice of behavior beyond saying that it's
"rounding behavior".
The result of attempting to indirectly access an object with thread
storage duration from a thread other than the one with which the
object is associated is implementation-defined.
I see no restrictions there at all, except that the implementation must
document the behavior somehow.
I agree that when the standard fails to impose meaningful restrictions
on implementation-defined behavior, my argument ceases to be valid.
There are, thankfully, relatively few such cases.
Loading...