Discussion:
User-defined named address spaces for bank-switching
(too old to reply)
Philipp Klaus Krause
2015-12-10 14:10:47 UTC
Permalink
Raw Message
Partitioned memory architectures are common in 8- and 16- bit
microcontrollers. A part of the logical address space is used as a
window into a larger physical address space. The parts of the physical
address space that can be mapped into the window are called memory
banks. There is some mechanism to select which part of the physical
address space is visible in the window. It is used by means of bank
selection instructions.

In C, this is usually exposed by implementation-defined intrinsic named
address spaces in one of the following ways:

1) Generic pointers (void *, etc) are 16 bit, and there is another,
wider pointer type (__far void *, etc). The wider pointer type can point
into any part of the physical address space. Access through the wider
pointer is less efficient, since, depending on the value of the pointer,
certainm bank selection instructions will have to be executed.
2) generic pointers (void *, etc) are wider than 16 bits. Access through
the pointer is less efficient, since, depending on the value of the
pointer, certainm bank selection instructions will have to be executed.
There is also another, smaller 16-bit pointer type (__near void *, etc).

However, this requires certain knowledge about bank selection in the
compiler; also the access through wide types is somewhat inefficient.

IMO, the following could be useful:
Allow defining a named address space for every part of the physical
address space that can be mapped into the window. Allow the user to
define a function that executes the bank-selection instructions to map
into the window. The compiler then can decide at compile time about the
bank-selection instructions to insert into the code. Also, this allows
for supporting bank-selection hardware now known to the compiler.

Example and suggested syntax (from the SDCC manual):

void setb0(void); // The function that sets the currently active memory
bank to b0
void setb1(void); // The function that sets the currently active memory
bank to b1

__addressmod setb0 spaceb0; // Declare a named address space called
spaceb0 that uses setb0()
__addressmod setb1 spaceb1; // Declare a named address space called
spaceb1 that uses setb1()
spaceb0 int x; // An int in address space spaceb0
spaceb1 int *y; // A pointer to an int in address space spaceb1
spaceb0 int *spaceb1 z; // A pointer in address space spaceb1 that
points to an int in address space spaceb0

Do you think is is a useful feature? Important enough to add it to
Embedded C?

Philipp
Hans-Bernhard Bröker
2015-12-10 15:25:08 UTC
Permalink
Raw Message
Post by Philipp Klaus Krause
Partitioned memory architectures are common in 8- and 16- bit
microcontrollers.
...

That looks awfully much like you're trying to re-invent the named
address space extension, as already found in the old "Embedded C
extensions" proposal (document n1005, at one point).

That didn't really leave much of an impression back then.
Post by Philipp Klaus Krause
However, this requires certain knowledge about bank selection in the
compiler; also the access through wide types is somewhat inefficient.
Compilers for platforms needing this kind of hoopla already have the
necessary knowledge, up to and including offering hooks to extend /
replace the bank switching intrinsics. But since that's really very
platform-specific, I rather doubt it can usefully be standardized.
Philipp Klaus Krause
2015-12-10 15:43:14 UTC
Permalink
Raw Message
Post by Hans-Bernhard Bröker
Post by Philipp Klaus Krause
Partitioned memory architectures are common in 8- and 16- bit
microcontrollers.
...
That looks awfully much like you're trying to re-invent the named
address space extension, as already found in the old "Embedded C
extensions" proposal (document n1005, at one point).
N1275 is a more current version. That proposal has two variants of named
address spaces:
1) Implementation-defined intrinsic named address spaces.
2) User-defined named address spaces. However those serve a somewaht
different purpose than the ones I propose. The ones in N1275 allow
theuser to specify functions for writing and reading (useful e.g. for an
EEPROM connected via I²C). The ones I propose are for the case where the
memory in the named address space can be mapped into the lgoical address
space of the system, and teh user specififies functions for the mapping.
Post by Hans-Bernhard Bröker
That didn't really leave much of an impression back then.
What were the problems? I can see N1275 2) not being that useful, as it
is just syntactic sugar for using read-/write-functions. But N1275 1)
seems a useful standardization of existing practice to me.

Philipp
Hans-Bernhard Bröker
2015-12-10 20:20:27 UTC
Permalink
Raw Message
Post by Philipp Klaus Krause
Post by Hans-Bernhard Bröker
Post by Philipp Klaus Krause
Partitioned memory architectures are common in 8- and 16- bit
microcontrollers.
...
That looks awfully much like you're trying to re-invent the named
address space extension, as already found in the old "Embedded C
extensions" proposal (document n1005, at one point).
N1275 is a more current version.
And that was, for all appearances, the end of that: a "type 2" draft, 8
years ago. AIUI, such a document is supposed to have been reviewed
within a 3-year period. I found no sign of such a review, or any other
decision about it.
Post by Philipp Klaus Krause
The ones I propose are for the case where the
memory in the named address space can be mapped into the lgoical address
space of the system, and teh user specififies functions for the mapping.
I don't quite see how the existing proposal (FWIW) would exclude such an
application. A major goal of that was to do precisely what you want
here: allow "far" memory, whether banked or segmented, in a standardized
way. Standardizing the banking mechanism itself is beginning to feel
like overkill to me. That one may not even be possible to implement as
a proper C function.
Post by Philipp Klaus Krause
Post by Hans-Bernhard Bröker
That didn't really leave much of an impression back then.
What were the problems?
For that you'd have to look up the actual committee documents, I think.
s***@casperkitty.com
2015-12-10 16:21:47 UTC
Permalink
Raw Message
I don't think the maintainers of the C Standard are interested in systems
programming, notwithstanding the fact that C was invented *for that purpose*.
Instead, from what I can tell, they perceive C as being a language for things
like high-end computing (the sort of stuff PIXAR would use for rendering and
the like). Given that the Standards Committee hasn't even offered a decent
means of telling a compiler that certain things will alias (aliasing is needed
all the time in systems programming, and occasionally useful but seldom
absolutely needed in high-end programming) named address spaces would seem
even more esoteric. What's really needed is to somehow restart efforts to
standardize an embedded C language which is separate from "Standard" C is
evolving toward being less and less suitable for systems programming.
Philipp Klaus Krause
2015-12-10 17:10:43 UTC
Permalink
Raw Message
C is evolving toward being less and less suitable for systems programming.
Which changes from C90 to C99 or from C99 to C11 make C less suitable
for systems programming? Are there any planned future such changes?

Philipp
s***@casperkitty.com
2015-12-10 17:35:20 UTC
Permalink
Raw Message
Post by Philipp Klaus Krause
C is evolving toward being less and less suitable for systems programming.
Which changes from C90 to C99 or from C99 to C11 make C less suitable
for systems programming? Are there any planned future such changes?
As C was designed, groups of bytes meeting alignment requirements could be
read as other types, regardless of how they were written, and could be
written as other types no matter how they would be read. This viewpoint is
expressed near the start of Chapter 5 of K&R "The C Programming Language"
Second Edition. Such usage is absolutely essential for many kinds of
systems programming.

When the Committee wrote the C89 Standard, they added some rules which
as written drastically changed the language in a fashion making it totally
unsuitable for many kinds of systems programming, but which as commonly
interpreted were far less disruptive. For example, in nearly all compilers
one could safely e.g. declare an array of 32-bit longs and then use it
as a word-aligned bunch of storage that could be safely read using pointers
to short or long, interchangeably, provided code never tried to access it
*directly* as an array of longs.

Over the years, interpretations of the rules have evolved in a direction
which has been increasingly placed the quest for optimization ahead of the
needs of systems programmers. I don't think K&R ever approved of ANSI's
effective type rules, since their book which claims to cover ANSI C doesn't
seem to mention them but instead suggests that on a typical implementation
a pair of bytes may be read as a "short" or four bytes as a "long" without
any mention of the effective type rules.

It's interesting that while most languages and compilers evolve in the
direction of later versions allowing programmers to express a superset of
what was expressible in earlier versions, the C language seems to be moving
in the opposite direction. While some compilers offer ways around some of
the rules, there's no standard for expressing concepts which would be
clearly and unambiguously expressed in the language designed by K&R.
Kaz Kylheku
2015-12-10 19:27:12 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Philipp Klaus Krause
C is evolving toward being less and less suitable for systems programming.
Which changes from C90 to C99 or from C99 to C11 make C less suitable
for systems programming? Are there any planned future such changes?
As C was designed, groups of bytes meeting alignment requirements could be
read as other types, regardless of how they were written, and could be
written as other types no matter how they would be read. This viewpoint is
expressed near the start of Chapter 5 of K&R "The C Programming Language"
Second Edition. Such usage is absolutely essential for many kinds of
systems programming.
K&R might have assured you that this aliased access will *work*, but not
what the value will be. That was, and remains, nonportable.

Nonportable systems programming is adequately served by a concept
which exists in the world, which is that to target a certain
environnment, we use a certain compiler which is closely associated
with that environment.

We use its extensions and rely on its additional stated requirements
to which it adheres.

Even with that, we can still be portable by isolating those parts
of the code for that compiler and environment in their own files
or with #if/#ifdef.

There is no need for an international programming language standard
to contain verbiage for the sake of nonportable programming.

Almost the whole /raison d'etre/ for a programming language standard
is portability: pin down a common dialect which programmers can use
that free of machine and system dependencies.

Code which aliases objects of different types is inherently nonportable,
even if a requirement is made that the aliasing access mechanism
must be reliable. C addresses the requirement for this quite adequately
with the provision of unions, and the provision that objects may be
accessed as byte arrays. If users find it useful to store an object
of one type and retrieve it as another, they can work with their
compiler vendor to negotiate that the union mechanism be implemented
in a way which supports that intent.

Some languages have ways to define the memory representation of objects
in a detailed way so then straighforward access statements or
expressions then effectively perform marshalling on unmarshalling of a
structure in a file or on the network, or the correct access to a
memory-mapped hardware register.

This actually brings little to the table, because it is trivial to
implement these accesses with more elementary operations, and wrap
them in higher level abstractions. Hardware has become a lot more
commoditized and standardized also. Binary file and network formats
are commonly based on data units that correspond to the types available
on common machine architectures and correspond to C types in the
compilers for those machines.

Anyone who wants a rich data format description language can just
use a compiler for one which interoperates with C. Nothing prevents
ASN.1 or whatever from being used in a C project. A suitable translator
spits out the C definitions and functions, and suitable run-time
library is linked which supports those functions.

In general, domain-specific languages can be used with C. For instance,
SQL queries can be mixed with C with a suitable generator; so there is
no need to waste a chapter in ISO C describing an SQL feature.
There is no need to waste a chapter in ISO C describing a grammar
notation for parsing, since a tool like Yacc can be used to combine
C fragments with a grammar to make a parser.
s***@casperkitty.com
2015-12-10 19:54:12 UTC
Permalink
Raw Message
Post by Kaz Kylheku
Post by s***@casperkitty.com
As C was designed, groups of bytes meeting alignment requirements could be
read as other types, regardless of how they were written, and could be
written as other types no matter how they would be read. This viewpoint is
expressed near the start of Chapter 5 of K&R "The C Programming Language"
Second Edition. Such usage is absolutely essential for many kinds of
systems programming.
K&R might have assured you that this aliased access will *work*, but not
what the value will be. That was, and remains, nonportable.
Different platforms will maps bytes to shorts and longs differently, but
I would interpret "One common situation is that any byte can be a char,
a pair of one-byte cells can be treated as a short integer, and four
adjacent bytes form a long," as indicating that on a typical machine where
hardware would treat bytes in such fashion, a programmer could do likewise.
Post by Kaz Kylheku
Nonportable systems programming is adequately served by a concept
which exists in the world, which is that to target a certain
environnment, we use a certain compiler which is closely associated
with that environment.
The whole purpose of having a standard was to get away from situations where
three different compilers for a machine will all have different incompatible
ways of doing the same thing. If the maker of the machine says how things
should be done at the hardware level, a programmer who knows that should have
a reasonable shot at knowing what will need to be done to write code for that
machine, without having to wade through reams of compiler-specific
documentation.
Post by Kaz Kylheku
There is no need for an international programming language standard
to contain verbiage for the sake of nonportable programming.
Very little code is 100% portable, and I would posit that the Standard
wouldn't have to change much to allow most embedded systems programming
to be done almost entirely within its confines, safe for a relatively
small number of intrinsics which would map very directly to constructs
defined by the machine vendor (and which different compiler vendors
should thus interpret the same way).
Post by Kaz Kylheku
Almost the whole /raison d'etre/ for a programming language standard
is portability: pin down a common dialect which programmers can use
that free of machine and system dependencies.
I'd posit that the reason should be to free programmers from *compiler*
dependencies. Machine dependencies are going to be inevitable in many
situations, but compiler dependencies shouldn't be.
Post by Kaz Kylheku
Code which aliases objects of different types is inherently nonportable,
even if a requirement is made that the aliasing access mechanism
must be reliable. C addresses the requirement for this quite adequately
with the provision of unions, and the provision that objects may be
accessed as byte arrays. If users find it useful to store an object
of one type and retrieve it as another, they can work with their
compiler vendor to negotiate that the union mechanism be implemented
in a way which supports that intent.
Suppose one needs to write a function which accepts an array of size_t and
needs to pass it to a function which expects an array of uint32_t. Suppose
further that this function only needs to run on machines where both types
have the same size and representation.

Is there any way to write clean and efficient code which is guaranteed to
run correctly on all platforms where those types have the same size and
representation? Is there any good reason it shouldn't be possible?
Post by Kaz Kylheku
Some languages have ways to define the memory representation of objects
in a detailed way so then straighforward access statements or
expressions then effectively perform marshalling on unmarshalling of a
structure in a file or on the network, or the correct access to a
memory-mapped hardware register.
In many C implementations that could be done through suitable structure
definitions and pointer casts.
Post by Kaz Kylheku
In general, domain-specific languages can be used with C. For instance,
SQL queries can be mixed with C with a suitable generator; so there is
no need to waste a chapter in ISO C describing an SQL feature.
There is no need to waste a chapter in ISO C describing a grammar
notation for parsing, since a tool like Yacc can be used to combine
C fragments with a grammar to make a parser.
One of the design intentions of C was to avoid the need to have code go
through extra layers of processing just to work with data which was already
in the machine's native format. Really all that's needed is a way to say
"regard this memory that may have been written type X (or as some unknown
type) as type Y". I can think of no hardware platforms where that should
be even remotely difficult.
Kaz Kylheku
2015-12-10 20:42:01 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Kaz Kylheku
Post by s***@casperkitty.com
As C was designed, groups of bytes meeting alignment requirements could be
read as other types, regardless of how they were written, and could be
written as other types no matter how they would be read. This viewpoint is
expressed near the start of Chapter 5 of K&R "The C Programming Language"
Second Edition. Such usage is absolutely essential for many kinds of
systems programming.
K&R might have assured you that this aliased access will *work*, but not
By the way, when responding above, I hadn't caught that "second Edition".
I'm not aware that the 2nd edition makes any assurances about aliasing.
Post by s***@casperkitty.com
Post by Kaz Kylheku
what the value will be. That was, and remains, nonportable.
Different platforms will maps bytes to shorts and longs differently, but
I would interpret "One common situation is that any byte can be a char,
a pair of one-byte cells can be treated as a short integer, and four
adjacent bytes form a long," as indicating that on a typical machine where
hardware would treat bytes in such fashion, a programmer could do likewise.
This is only telling the reader how the C type system can correspond to
the machine's typeless bytes and byte cells.

"Treated" clearly refers to how the implementor treats the available
hardware, not "treated" as in C programs can treat these cells however
they want.
Post by s***@casperkitty.com
Post by Kaz Kylheku
Nonportable systems programming is adequately served by a concept
which exists in the world, which is that to target a certain
environnment, we use a certain compiler which is closely associated
with that environment.
The whole purpose of having a standard was to get away from situations where
three different compilers for a machine will all have different incompatible
ways of doing the same thing.
I strongly disagree. The situation where you have three different
compilers for the same machine is vanishingly rare. It happens largely
on popular desktop systems with large user bases where the hardware is
commoditized, and the software landscape is a large zoo of competing
applications in nearly every category.

The idea that the *whole purpose* of the standard is to allow programs to
be portable to the same machine and system through N different compilers
is outlandishly ridiculous.

It's not even *a* purpose; it simply a side effect. Portability to
different systems subsumes portability to one system in several ways.
Post by s***@casperkitty.com
If the maker of the machine says how things
should be done at the hardware level, a programmer who knows that should have
a reasonable shot at knowing what will need to be done to write code for that
machine, without having to wade through reams of compiler-specific
documentation.
This problem is addressed by what is called an ABI. Compilers written to
the same ABI will lay out structures the same way and have the same
calling conventions, so that it's possible to translate different
translation units with different compiler and link them together.

ABI's are out of the scope of ISO C, but they are standards just like
it.
Post by s***@casperkitty.com
Post by Kaz Kylheku
There is no need for an international programming language standard
to contain verbiage for the sake of nonportable programming.
Very little code is 100% portable, and I would posit that the Standard
If we have a portability standard, we can tell to what extent a program
is portable just by looking at it and at that standard.
Post by s***@casperkitty.com
wouldn't have to change much to allow most embedded systems programming
to be done almost entirely within its confines, safe for a relatively
Yes, it did. See, without the standard, "its confines" above refers to
nothing. There are confines, and we can tell to what extent some program
is in those confines or not in those confines.
Post by s***@casperkitty.com
Post by Kaz Kylheku
Almost the whole /raison d'etre/ for a programming language standard
is portability: pin down a common dialect which programmers can use
that free of machine and system dependencies.
I'd posit that the reason should be to free programmers from *compiler*
dependencies.
Then you're looking for an ABI standard: you don't want the compiler
to dictate structure layouts, calling conventions and the like.
Post by s***@casperkitty.com
Machine dependencies are going to be inevitable in many
situations, but compiler dependencies shouldn't be.
Yet programmers sometimes choose compiler-specific extensions to solve
problems.

The Linux kernel can't be built without GCC.
Post by s***@casperkitty.com
Post by Kaz Kylheku
Code which aliases objects of different types is inherently nonportable,
even if a requirement is made that the aliasing access mechanism
must be reliable. C addresses the requirement for this quite adequately
with the provision of unions, and the provision that objects may be
accessed as byte arrays. If users find it useful to store an object
of one type and retrieve it as another, they can work with their
compiler vendor to negotiate that the union mechanism be implemented
in a way which supports that intent.
Suppose one needs to write a function which accepts an array of size_t and
needs to pass it to a function which expects an array of uint32_t. Suppose
further that this function only needs to run on machines where both types
have the same size and representation.
Then both types should be ideally be typedefs for the same thing, which
makes them compatible.
Post by s***@casperkitty.com
Is there any way to write clean and efficient code which is guaranteed to
run correctly on all platforms where those types have the same size and
representation? Is there any good reason it shouldn't be possible?
Yes; just put the code in separate translation units, and cast.
Don't turn on any ISO-C-violating global optimizations.

A conforming implementation cannot tell that you pulled this trick,
because that would require semantic analysis to take place after
translation phase 7.

The C model of translation is that translation units are semantically
analyzed in isolation. When they are brought together, all that takes
place is linkage.

So if one translation unit has an external function which processes
an array of size_t, and the other translation unit prepares an array
of uint32_t, passing it across translation unit boundaries to that
function, there is no conceivable way that can break if uint32_t
and size_t have the same representation, down to the bit level contents
and alignment requirements.
Post by s***@casperkitty.com
in the machine's native format. Really all that's needed is a way to say
"regard this memory that may have been written type X (or as some unknown
type) as type Y".
Happens all the time when you get a piece of memory from malloc and
use it as a structure or whatever.

Compilers have good support for this via unions, and it works across
translation unit boundaries.

If you prepare a "struct foo" in one translation unit, and return a
"void *" pointing to it, then another unit can treat that as a "struct
bar". The memory access itself will work as long as "struct foo" is at
least as large as "struct bar"; no aliasing rule will kick in. That
function in the other translation unit is simply not distinguishable
from malloc. Of course, the contents of "struct foo" may look like trap
representations when interpreted as members of "struct foo".
That's not going to happen for those members which use the same
representation and are at corresponding offsets.

You just can't get away with these tricks in the same translation unit.
30 years ago, maybe you could.
s***@casperkitty.com
2015-12-10 21:55:09 UTC
Permalink
Raw Message
Post by Kaz Kylheku
By the way, when responding above, I hadn't caught that "second Edition".
I'm not aware that the 2nd edition makes any assurances about aliasing.
It doesn't mention the subject, but programmers and compiler vendors alike
interpreted K&R's language to indicate that "long *p" holds an address
of four bytes from which hardware can fetch a long, then "*p" will
interpret those four bytes as a long.
Post by Kaz Kylheku
"Treated" clearly refers to how the implementor treats the available
hardware, not "treated" as in C programs can treat these cells however
they want.
Programmers and compiler vendors read that language as having the same
meaning as it did on the machines where C was first implemented.
Post by Kaz Kylheku
I strongly disagree. The situation where you have three different
compilers for the same machine is vanishingly rare. It happens largely
on popular desktop systems with large user bases where the hardware is
commoditized, and the software landscape is a large zoo of competing
applications in nearly every category.
I would be surprised if you can find an embedded controller family which
represents 1% of total sales volume in the marketplace which only has one
or two cross compilers available. Certainly the vast majority have more
than that.
Post by Kaz Kylheku
The idea that the *whole purpose* of the standard is to allow programs to
be portable to the same machine and system through N different compilers
is outlandishly ridiculous.
I'd say the primary purpose is to avoid *compiler* dependencies. Code
which needs 10GB of RAM isn't going to run on a processor with 1KB,
but there's no reason that C shouldn't be usable to write code for a
micro with 1KB if the program doesn't need to do too much. Most larger
computers have the same general abilities, so tailoring code for them
isn't as necessary as at the lower end of the scale. If one is making
100,000 remote controllers for TV sets, upgrading the processors from 2K
to 4K may cost $25,000. If code will never need that RAM, why spend the
money?
Post by Kaz Kylheku
This problem is addressed by what is called an ABI. Compilers written to
the same ABI will lay out structures the same way and have the same
calling conventions, so that it's possible to translate different
translation units with different compiler and link them together.
An ABI isn't quite sufficient. Embedded programs also frequently need a
few guarantees beyond that, such as the ability to say "Physically
perform all operations specified by the code prior to this point, before
doing any which follow it, flushing and invalidating everything cached
in registers before proceeding". Is there any reason why every compiler
vendor should be called upon to define their own ways of doing such a thing
(or else simply saying that all operations will be performed in the order
requested and such an operation would be a NOP)?
Post by Kaz Kylheku
ABI's are out of the scope of ISO C, but they are standards just like
it.
The ABIs themselves are, but a few things like the ability to ensure
sequencing would not be.
Post by Kaz Kylheku
If we have a portability standard, we can tell to what extent a program
is portable just by looking at it and at that standard.
For how many programs would it be impossible to come up with a standards-
compliant implementation upon which they wouldn't work? Very few programs
are portable. The only question is whether the ways in which they are non-
portable happen to be those which the person judging "portability" thinks
the guarantees they rely upon, though not guaranteed by the Standard, have
sufficient value as to be worth guaranteeing.
Post by Kaz Kylheku
Post by s***@casperkitty.com
wouldn't have to change much to allow most embedded systems programming
to be done almost entirely within its confines, safe for a relatively
Yes, it did. See, without the standard, "its confines" above refers to
nothing. There are confines, and we can tell to what extent some program
is in those confines or not in those confines.
A lot of things are handled consistently by implementations but very poorly
defined by the Standard.
Post by Kaz Kylheku
Post by s***@casperkitty.com
I'd posit that the reason should be to free programmers from *compiler*
dependencies.
Then you're looking for an ABI standard: you don't want the compiler
to dictate structure layouts, calling conventions and the like.
No, but I do need the compiler to provide a means of guaranteeing that
certain groups of operations will happen in a certain order without having
to micro-manage everything. I wouldn't expect the Standard to say anything
about how to trigger DMA operations or tell when they're complete, but I
would like a Standard to provide means of defining write and read memory/
aliasing buffers which, combined with information about the CPU and
controller, would be sufficient to ensure that data gets written and read
correctly without any risk that a compiler might decide that since it had
read a variable into a register before operation that triggered a DMA
request, it can use the cached copy rather than rereading it. Sure it
would be possible to use "volatile" variables for everything DMA is ever
going to touch, but that's massive overkill compared with being able to
tell the compiler that it can rearrange accesses before the DMA, and it
can rearrange accesses after the DMA, but it cannot move accesses accross
the DMA.
Post by Kaz Kylheku
Post by s***@casperkitty.com
Machine dependencies are going to be inevitable in many
situations, but compiler dependencies shouldn't be.
Yet programmers sometimes choose compiler-specific extensions to solve
problems.
What else should they do if the Standard fails to accommodate commonplace
needs?
Post by Kaz Kylheku
Post by s***@casperkitty.com
Suppose one needs to write a function which accepts an array of size_t and
needs to pass it to a function which expects an array of uint32_t. Suppose
further that this function only needs to run on machines where both types
have the same size and representation.
Then both types should be ideally be typedefs for the same thing, which
makes them compatible.
What if one of the libraries are used in some other projects where data
interchange between them isn't required, but where the types don't match?
Post by Kaz Kylheku
Post by s***@casperkitty.com
Is there any way to write clean and efficient code which is guaranteed to
run correctly on all platforms where those types have the same size and
representation? Is there any good reason it shouldn't be possible?
Yes; just put the code in separate translation units, and cast.
Don't turn on any ISO-C-violating global optimizations.
A conforming implementation could keep use memory with tag bits or other
such mechanisms to detect that memory was written as one type and read as
another, and use that as justification to do anything it likes.
Post by Kaz Kylheku
A conforming implementation cannot tell that you pulled this trick,
because that would require semantic analysis to take place after
translation phase 7.
Under the "as-if" rule, if there an implementation could yield a particular
behavior while abiding the indicated stages, the implementation would be
yield that behavior using whatever means it sees fit.
Post by Kaz Kylheku
So if one translation unit has an external function which processes
an array of size_t, and the other translation unit prepares an array
of uint32_t, passing it across translation unit boundaries to that
function, there is no conceivable way that can break if uint32_t
and size_t have the same representation, down to the bit level contents
and alignment requirements.
Hardware tag bits would be a possible legal mechanism. Another mechanism
in some cases might be information stored in the object files about what
kinds of variables are written within a function. Given

void hey(unsigned long *lp)
{
p++;
bar();
p--;
}

a compiler could generate two versions of "hey"--one for use when "bar"
modifies something of "long" or "char" (or variations thereof), and one
for use when it doesn't, and let the linker figure out which one it should
use.

Also, nothing in the Standard would forbid an implementation or VM from
having tag bits for each word of memory for "trap if loaded as int",
"trap if loaded as long", etc.; doing that wouldn't require any cross-
unit analysis.
Post by Kaz Kylheku
Compilers have good support for this via unions, and it works across
translation unit boundaries.
Sort of. I know of no interpretation of the C99 rules which would allow for

union foo { int i; float f; } u;
work_with_int(&(u.i));
work_with_float(&(u.f));

but would not allow for:

union foo { int i; float f; } u;
work_with_int_and_float(&(u.i), &(u.f));

where the latter function expects that if the pointers are equal they will
alias. There is nothing in the Standard which would indicate that the
Effective Type of the union gets changed by writes to it, so either the
former code is invalid or the latter code would be valid; compilers do
not allow for the possibility of aliasing in the latter case, so that
would suggest the former code is invalid.
Post by Kaz Kylheku
If you prepare a "struct foo" in one translation unit, and return a
"void *" pointing to it, then another unit can treat that as a "struct
bar". The memory access itself will work as long as "struct foo" is at
least as large as "struct bar"; no aliasing rule will kick in. That
function in the other translation unit is simply not distinguishable
from malloc. Of course, the contents of "struct foo" may look like trap
representations when interpreted as members of "struct foo".
That's not going to happen for those members which use the same
representation and are at corresponding offsets.
Nothing in the Standard forbids the use of hardware tag bits or other such
things.
Post by Kaz Kylheku
You just can't get away with these tricks in the same translation unit.
30 years ago, maybe you could.
Why is it better to have code jump between translation units, rather than
having a directive for "let's not and say we did"?
Kaz Kylheku
2015-12-10 23:35:31 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Kaz Kylheku
By the way, when responding above, I hadn't caught that "second Edition".
I'm not aware that the 2nd edition makes any assurances about aliasing.
It doesn't mention the subject, but programmers and compiler vendors alike
interpreted K&R's language to indicate that "long *p" holds an address
of four bytes from which hardware can fetch a long, then "*p" will
interpret those four bytes as a long.
Sure, but they didn't go as far as "... even if *p is actually a float
variable in the same scope that is currently in a floating-point
register".
Post by s***@casperkitty.com
Post by Kaz Kylheku
"Treated" clearly refers to how the implementor treats the available
hardware, not "treated" as in C programs can treat these cells however
they want.
Programmers and compiler vendors read that language as having the same
meaning as it did on the machines where C was first implemented.
Post by Kaz Kylheku
I strongly disagree. The situation where you have three different
compilers for the same machine is vanishingly rare. It happens largely
on popular desktop systems with large user bases where the hardware is
commoditized, and the software landscape is a large zoo of competing
applications in nearly every category.
I would be surprised if you can find an embedded controller family which
represents 1% of total sales volume in the marketplace which only has one
or two cross compilers available. Certainly the vast majority have more
than that.
Post by Kaz Kylheku
The idea that the *whole purpose* of the standard is to allow programs to
be portable to the same machine and system through N different compilers
is outlandishly ridiculous.
I'd say the primary purpose is to avoid *compiler* dependencies. Code
which needs 10GB of RAM isn't going to run on a processor with 1KB,
but there's no reason that C shouldn't be usable to write code for a
micro with 1KB if the program doesn't need to do too much. Most larger
computers have the same general abilities, so tailoring code for them
isn't as necessary as at the lower end of the scale. If one is making
100,000 remote controllers for TV sets, upgrading the processors from 2K
to 4K may cost $25,000. If code will never need that RAM, why spend the
money?
Post by Kaz Kylheku
This problem is addressed by what is called an ABI. Compilers written to
the same ABI will lay out structures the same way and have the same
calling conventions, so that it's possible to translate different
translation units with different compiler and link them together.
An ABI isn't quite sufficient. Embedded programs also frequently need a
few guarantees beyond that, such as the ability to say "Physically
perform all operations specified by the code prior to this point, before
doing any which follow it, flushing and invalidating everything cached
in registers before proceeding". Is there any reason why every compiler
vendor should be called upon to define their own ways of doing such a thing
(or else simply saying that all operations will be performed in the order
requested and such an operation would be a NOP)?
Indeed not, and C is slowly moving in the direction of providing
more stuff in this direction. Ten, fifteen years ago, I defined inline
assembly to do atomic operations. Now there are some portable things for
that.
Post by s***@casperkitty.com
Post by Kaz Kylheku
ABI's are out of the scope of ISO C, but they are standards just like
it.
The ABIs themselves are, but a few things like the ability to ensure
sequencing would not be.
*Anything* can be put into a separate document, even if it pertains
to the C language.
Post by s***@casperkitty.com
Post by Kaz Kylheku
If we have a portability standard, we can tell to what extent a program
is portable just by looking at it and at that standard.
For how many programs would it be impossible to come up with a standards-
compliant implementation upon which they wouldn't work? Very few programs
are portable. The only question is whether the ways in which they are non-
portable happen to be those which the person judging "portability" thinks
the guarantees they rely upon, though not guaranteed by the Standard, have
sufficient value as to be worth guaranteeing.
Post by Kaz Kylheku
Post by s***@casperkitty.com
wouldn't have to change much to allow most embedded systems programming
to be done almost entirely within its confines, safe for a relatively
Yes, it did. See, without the standard, "its confines" above refers to
nothing. There are confines, and we can tell to what extent some program
is in those confines or not in those confines.
A lot of things are handled consistently by implementations but very poorly
defined by the Standard.
Post by Kaz Kylheku
Post by s***@casperkitty.com
I'd posit that the reason should be to free programmers from *compiler*
dependencies.
Then you're looking for an ABI standard: you don't want the compiler
to dictate structure layouts, calling conventions and the like.
No, but I do need the compiler to provide a means of guaranteeing that
certain groups of operations will happen in a certain order without having
to micro-manage everything. I wouldn't expect the Standard to say anything
about how to trigger DMA operations or tell when they're complete, but I
would like a Standard to provide means of defining write and read memory/
aliasing buffers which, combined with information about the CPU and
controller, would be sufficient to ensure that data gets written and read
correctly without any risk that a compiler might decide that since it had
read a variable into a register before operation that triggered a DMA
request, it can use the cached copy rather than rereading it. Sure it
would be possible to use "volatile" variables for everything DMA is ever
going to touch, but that's massive overkill compared with being able to
tell the compiler that it can rearrange accesses before the DMA, and it
can rearrange accesses after the DMA, but it cannot move accesses accross
the DMA.
Post by Kaz Kylheku
Post by s***@casperkitty.com
Machine dependencies are going to be inevitable in many
situations, but compiler dependencies shouldn't be.
Yet programmers sometimes choose compiler-specific extensions to solve
problems.
What else should they do if the Standard fails to accommodate commonplace
needs?
Post by Kaz Kylheku
Post by s***@casperkitty.com
Suppose one needs to write a function which accepts an array of size_t and
needs to pass it to a function which expects an array of uint32_t. Suppose
further that this function only needs to run on machines where both types
have the same size and representation.
Then both types should be ideally be typedefs for the same thing, which
makes them compatible.
What if one of the libraries are used in some other projects where data
interchange between them isn't required, but where the types don't match?
Post by Kaz Kylheku
Post by s***@casperkitty.com
Is there any way to write clean and efficient code which is guaranteed to
run correctly on all platforms where those types have the same size and
representation? Is there any good reason it shouldn't be possible?
Yes; just put the code in separate translation units, and cast.
Don't turn on any ISO-C-violating global optimizations.
A conforming implementation could keep use memory with tag bits or other
such mechanisms to detect that memory was written as one type and read as
another, and use that as justification to do anything it likes.
No implementation does. Even if it existed, you might not care about the
code being not portable to it. Market forces would probably make that an
unviable C implementation, leading programmers to use alternatives to
target the same platform. To prevent rejection by programmers, the
implementation would likely have a switch to turn this detection off, so
that programs would work. Moreover, switching it off would likely make
them execute faster, so programers not relying on the type punning would
turn it off also.
Post by s***@casperkitty.com
Post by Kaz Kylheku
A conforming implementation cannot tell that you pulled this trick,
because that would require semantic analysis to take place after
translation phase 7.
Under the "as-if" rule, if there an implementation could yield a
particular behavior while abiding the indicated stages, the
implementation would be yield that behavior using whatever means it
sees fit.
Under the as-if rule, the function in the translation unit is handed
piece of memory which is indistinguishable from the array of size_t
that it expects.

In the absence of some out-of-band tag bits stored somewhere else,
or global analysis which violates the translation phases, the trick
cannot be detected.
Post by s***@casperkitty.com
Post by Kaz Kylheku
So if one translation unit has an external function which processes
an array of size_t, and the other translation unit prepares an array
of uint32_t, passing it across translation unit boundaries to that
function, there is no conceivable way that can break if uint32_t
and size_t have the same representation, down to the bit level contents
and alignment requirements.
Hardware tag bits would be a possible legal mechanism.
Not gonna make a comeback any time soon, and if it does, it will be
strictly used for dynamic languages, not for C and its data types
(other than through some special API, perhaps).
Post by s***@casperkitty.com
Another mechanism
in some cases might be information stored in the object files about what
kinds of variables are written within a function. Given
void hey(unsigned long *lp)
{
p++;
bar();
p--;
}
a compiler could generate two versions of "hey"--one for use when "bar"
modifies something of "long" or "char" (or variations thereof), and one
for use when it doesn't, and let the linker figure out which one it should
use.
The linker can't figure that out because figuring it out is "semantic
analysis". In translation phase 7, the tokens of a program are
"semantically analyzed" and translated as a translation unit.
Then in phase 8, "external object and function references are resolved".
etc.

Semantic analysis ends before linkage, period. No more thinking about
types or optimization or anything complicated other than mapping names
to addresses (resolving).
Post by s***@casperkitty.com
Also, nothing in the Standard would forbid an implementation or VM from
having tag bits for each word of memory for "trap if loaded as int",
"trap if loaded as long", etc.; doing that wouldn't require any cross-
unit analysis.
If that is the case, then in fact size_t and uint32_t do not have
the same representation, and so the conditions are not satisfied for
us to be aliasing those arrays.
Post by s***@casperkitty.com
Post by Kaz Kylheku
Compilers have good support for this via unions, and it works across
translation unit boundaries.
Sort of. I know of no interpretation of the C99 rules which would allow for
union foo { int i; float f; } u;
work_with_int(&(u.i));
work_with_float(&(u.f));
union foo { int i; float f; } u;
work_with_int_and_float(&(u.i), &(u.f));
Once you have taken addresses of the members and start passing them
around, you are no longer working with the union as such; it is
irrelevant.

Working with the union means having a reference to a union object,
and going through its member selection operators.
Post by s***@casperkitty.com
where the latter function expects that if the pointers are equal they will
alias. There is nothing in the Standard which would indicate that the
Effective Type of the union gets changed by writes to it, so either the
former code is invalid or the latter code would be valid; compilers do
not allow for the possibility of aliasing in the latter case, so that
would suggest the former code is invalid.
Post by Kaz Kylheku
If you prepare a "struct foo" in one translation unit, and return a
"void *" pointing to it, then another unit can treat that as a "struct
bar". The memory access itself will work as long as "struct foo" is at
least as large as "struct bar"; no aliasing rule will kick in. That
function in the other translation unit is simply not distinguishable
from malloc. Of course, the contents of "struct foo" may look like trap
representations when interpreted as members of "struct foo".
That's not going to happen for those members which use the same
representation and are at corresponding offsets.
Nothing in the Standard forbids the use of hardware tag bits or other such
things.
Just the fact that memcpy can reproduce the value of an object, yet
isn't going to copy any tag bits (which are not in that object).
Post by s***@casperkitty.com
Post by Kaz Kylheku
You just can't get away with these tricks in the same translation unit.
30 years ago, maybe you could.
Why is it better to have code jump between translation units, rather than
having a directive for "let's not and say we did"?
It isn't; I'm just saying that's the way to realisticaly solve the
stated problem, today.

Philosophically speaking, if pieces of code are lying to each other,
why should they be in the same translation unit? In a sense, they are
enemies, and so belong behind their respective borders. :)
s***@casperkitty.com
2015-12-11 00:26:09 UTC
Permalink
Raw Message
Post by Kaz Kylheku
Post by s***@casperkitty.com
It doesn't mention the subject, but programmers and compiler vendors alike
interpreted K&R's language to indicate that "long *p" holds an address
of four bytes from which hardware can fetch a long, then "*p" will
interpret those four bytes as a long.
Sure, but they didn't go as far as "... even if *p is actually a float
variable in the same scope that is currently in a floating-point
register".
True, but the C89 rules basically only ruled out cases where code sometimes
treated something as a compiler-placed object and sometimes used a pointer
of a different type. I don't think any compilers before C99 made any
assumptions about whether two things accessed via pointers could alias.
Post by Kaz Kylheku
Indeed not, and C is slowly moving in the direction of providing
more stuff in this direction. Ten, fifteen years ago, I defined inline
assembly to do atomic operations. Now there are some portable things for
that.
What's needed for embedded systems, though, often isn't a portable ways of forcing multi-processor synchronization or other such things, but merely a
means of telling the processor to finish its *own* memory sequencing. The
hardware manual would then indicate what needs to happen beyond that.
Post by Kaz Kylheku
*Anything* can be put into a separate document, even if it pertains
to the C language.
Perhaps, though historically ABIs have focused on communication between
things that may be in discrete languages. An ABI would say that a
function needs to receive its first argument in R0 and its second
argument in R1, but in many cases would be silent about the syntax
needed to make that happen in any particular language.
Post by Kaz Kylheku
Post by s***@casperkitty.com
A conforming implementation could keep use memory with tag bits or other
such mechanisms to detect that memory was written as one type and read as
another, and use that as justification to do anything it likes.
No implementation does. Even if it existed, you might not care about the
code being not portable to it. Market forces would probably make that an
unviable C implementation, leading programmers to use alternatives to
target the same platform. To prevent rejection by programmers, the
implementation would likely have a switch to turn this detection off, so
that programs would work. Moreover, switching it off would likely make
them execute faster, so programers not relying on the type punning would
turn it off also.
The fact that such an implementation would be legitimate would mean that
in any situation where such an implementation would be allowed to detect
a violation, a compiler would be allowed to do anything it likes, regardless
of the actual means the compiler uses to detect such violations.
Post by Kaz Kylheku
Under the as-if rule, the function in the translation unit is handed
piece of memory which is indistinguishable from the array of size_t
that it expects.
In the absence of some out-of-band tag bits stored somewhere else,
or global analysis which violates the translation phases, the trick
cannot be detected.
Under the as-if rule, code which does not invoke Undefined Behavior must
be unable to distinguish the behavior from one without tag bits. That
does not imply that tag bits, or any static or run-time analysis whose
effect simulates tag bits, could not alter the behavior of a program which
engages in Undefined Behavior.
Post by Kaz Kylheku
Post by s***@casperkitty.com
Hardware tag bits would be a possible legal mechanism.
Not gonna make a comeback any time soon, and if it does, it will be
strictly used for dynamic languages, not for C and its data types
(other than through some special API, perhaps).
Doesn't matter whether anyone physically bothers to implement them, though
for sandboxing VM such bits could have a very practical use if there were a
slight change made to the Standard with respect to "char" values.
Post by Kaz Kylheku
The linker can't figure that out because figuring it out is "semantic
analysis". In translation phase 7, the tokens of a program are
"semantically analyzed" and translated as a translation unit.
Then in phase 8, "external object and function references are resolved".
etc.
It wouldn't really have to be semantic analysis. A compiler can generate
functions with different names based upon what types are modified thereby.
Linkers are allowed to make decisions about what functions to link based
upon what combinations will yield a buildable image. It's common, for
example, to have systems where if all uses of "printf" employ string
literals and none include floating-point formats, a version of printf
without floating-point support will get linked in. Such a thing may be
accomplished by having the compiler regard printf as an intrinsic, and
have "simple" uses generate a call to "__printf_simple"; a linker may then
have "__printf_simple" either bring in a simple printf routine or else
have "__printf_simple" alias the main printf routine (if it had to be
brought in for some other reason).
Post by Kaz Kylheku
Semantic analysis ends before linkage, period. No more thinking about
types or optimization or anything complicated other than mapping names
to addresses (resolving).
Post by s***@casperkitty.com
Also, nothing in the Standard would forbid an implementation or VM from
having tag bits for each word of memory for "trap if loaded as int",
"trap if loaded as long", etc.; doing that wouldn't require any cross-
unit analysis.
If that is the case, then in fact size_t and uint32_t do not have
the same representation, and so the conditions are not satisfied for
us to be aliasing those arrays.
For purposes of the Standard, they would have the same representation if it
would be impossible for code to distinguish them without invoking Undefined
Behavior.
Post by Kaz Kylheku
Once you have taken addresses of the members and start passing them
around, you are no longer working with the union as such; it is
irrelevant.
Working with the union means having a reference to a union object,
and going through its member selection operators.
Which is in many cases not practical. Sure, if both libraries used arrays
of a union type that contained both size_t and uint32_t, there'd be no
problem, but that wouldn't work very well on systems where the libraries
were supposed to be working with types of different sizes.
Post by Kaz Kylheku
Post by s***@casperkitty.com
Nothing in the Standard forbids the use of hardware tag bits or other such
things.
Just the fact that memcpy can reproduce the value of an object, yet
isn't going to copy any tag bits (which are not in that object).
In which case it sets the tag bits to "last written as character", which
would imply that the object can be read as any type. Though by the rules
of the C99 Standard, if memcpy could tell whether its destination was in
allocated storage (not hard, typically) it could copy tag bits from the
source.
Post by Kaz Kylheku
Post by s***@casperkitty.com
Why is it better to have code jump between translation units, rather than
having a directive for "let's not and say we did"?
It isn't; I'm just saying that's the way to realisticaly solve the
stated problem, today.
Philosophically speaking, if pieces of code are lying to each other,
why should they be in the same translation unit? In a sense, they are
enemies, and so belong behind their respective borders. :)
Is it really lying if the Standard provides no means of saying what needs to
be said? For example, how would you handle a situation in which a method
is expected to receive a structure whose first member is a pointer to a
structure which contains a few function pointers but may contain other
stuff as well, where the expected usage pattern would be:

typedef struct
{
fnptr1 draw;
fnptr2 move;
} DRAWING_SHAPE_CLASS_INFO;
typedef struct
{
DRAWING_SHAPE_CLASS_INFO *typInfo;
RECTANGLE bounding_box;
} DRAWING_SHAPE;
void draw_shapes(DRAWING_SHAPE **shapes, int num_shapes)
{
for (int i=0; i<num_shapes; i++)
shapes[i]->typInfo->draw(shapes[i]);
}

Is there any way to allow some kinds of shapes to have more information
than just the bounding box without adding extra levels of indirection
to all the code that uses them? Is it really "lying" to pass a pointer
to a type whose first two fields match DRAWING_SHAPE except that the
first, rather than being a pointer to DRAWING_SHAPE_CLASS_INFO, is instead
a pointer to a type whose first two fields match that type?
Keith Thompson
2015-12-10 19:43:38 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Philipp Klaus Krause
C is evolving toward being less and less suitable for systems programming.
Which changes from C90 to C99 or from C99 to C11 make C less suitable
for systems programming? Are there any planned future such changes?
As C was designed, groups of bytes meeting alignment requirements
could be read as other types, regardless of how they were written, and
could be written as other types no matter how they would be read.
This viewpoint is expressed near the start of Chapter 5 of K&R "The C
Programming Language" Second Edition. Such usage is absolutely
essential for many kinds of systems programming.
Can you cite the wording in K&R2 Chapter 5 that implies this?

[...]
--
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-12-10 20:20:24 UTC
Permalink
Raw Message
Post by Keith Thompson
Can you cite the wording in K&R2 Chapter 5 that implies this?
"One common situation is that any byte can be a char, a pair of one-byte
cells can be treated as a short integer, and four adjacent bytes form a
long" [page 93].

I think there is a clear implication that if lp is a long* which points to
an address with four bytes the hardware is capable of fetching as a long
with no padding, those four bytes *lp may be used as a long. There is no
mention of any requirement that they may only be used that way if they
were written using either a char* or a short*.

The caveat that writing a union as something other than the last-written
value probably relates to the fact that compilers would often try to treat
registers as a write-through cache. Given something like:

union { double d; short s[8]; } u;

a compiler might decide to leave "s" in memory but allocate a register to
"d". Having updates to "s" hit "d" would require reloading "d" after
every write to "s", and there was no perceived need to burden compilers with
doing that for code using unions *since the only way for the implementation
to actually achieve such a result would be to write the result to memory
and read it back, and such a result could be achieved by using one type of
pointer to write the data to memory one way and using another type of
pointer to read it back.
Kaz Kylheku
2015-12-10 20:51:07 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Keith Thompson
Can you cite the wording in K&R2 Chapter 5 that implies this?
"One common situation is that any byte can be a char, a pair of one-byte
cells can be treated as a short integer, and four adjacent bytes form a
long" [page 93].
Treated by the design of the compiler for the machine, not treated
by you in your program.

Obviously, you the user of the implementation, don't get to decide how
many bytes consistutes a long integer.

The "one common situation" is just a widespread implementation choice.
Post by s***@casperkitty.com
I think there is a clear implication that if lp is a long* which points to
an address with four bytes the hardware is capable of fetching as a long
with no padding, those four bytes *lp may be used as a long. There is no
mention of any requirement that they may only be used that way if they
were written using either a char* or a short*.
There is no mention at all of how anything may or may not be used.
Keith Thompson
2015-12-10 21:41:33 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Keith Thompson
Can you cite the wording in K&R2 Chapter 5 that implies this?
"One common situation is that any byte can be a char, a pair of one-byte
cells can be treated as a short integer, and four adjacent bytes form a
long" [page 93].
I think there is a clear implication that if lp is a long* which points to
an address with four bytes the hardware is capable of fetching as a long
with no padding, those four bytes *lp may be used as a long. There is no
mention of any requirement that they may only be used that way if they
were written using either a char* or a short*.
I don't think that's intended to state a general requirement. In
particular, it's not generally true if the two- or four-byte chunk is
not properly aligned. If it doesn't mention that restriction (which I
presume you'll agree is a valid one), or the fact that short and long
are not necesssarily 2 and 4 bytes, respectively, I don't think we can
reasonably interpret that as a rigorous statement that a (properly
aligned) 4-byte chunk of memory can *always* be treated as a 4-byte
integer.

Also, note that it says that *any* byte can be a char (which is
consistent with the effective type rules), but doesn't use the word
"any" for 2- or 4-byte quantities. I'm not certain that it's an
intentional distinction, but it could be.

That section, I think, is just giving a general idea of how objects are
represented and how pointers work: a 16-bit integer is represented as 2
adjacent bytes, and a 32-bit integer as 4 adjacent bytes. It doesn't
seem to me to be talking about aliasing at all.

Earlier in the same chapter:

The main change in ANSI C is to make exlicit the rules about how
pointers can be manipulated, in effect mandating what good
programmers already practice and good compilers already enforce.

It's not clear that this refers to the effective type rules, but it's
not clear that it doesn't.

[...]
--
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-12-10 22:13:17 UTC
Permalink
Raw Message
I don't think that's intended to state a general requirement...
Also, note that it says that *any* byte can be a char (which is
consistent with the effective type rules), but doesn't use the word
"any" for 2- or 4-byte quantities. I'm not certain that it's an
intentional distinction, but it could be.
It's an obvious distinction which would be need because of alignment issues
and other reasons, whether or not the ANSI rules used character access as
the only bypass, rather than specifying that code should use some other
means of indicating aliasing but allowing character access as a deprecated
means of bypass.
The main change in ANSI C is to make exlicit the rules about how
pointers can be manipulated, in effect mandating what good
programmers already practice and good compilers already enforce.
It's not clear that this refers to the effective type rules, but it's
not clear that it doesn't.
Since malloc returns a range of bytes, and the example given in the
rationale involves accessing an object of static or automatic duration
via pointer of a different type, I think an understanding at the time was
that compiler-placed variables need not be kept strictly in sync with
bytes in memory except when accessed by pointers of their own types, but
I don't think there was any perception that it was illegitimate to use
two different kinds of pointer to operate on an area of memory that wasn't
being used as a compiler-placed object.
Keith Thompson
2015-12-11 00:28:07 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
I don't think that's intended to state a general requirement...
Also, note that it says that *any* byte can be a char (which is
consistent with the effective type rules), but doesn't use the word
"any" for 2- or 4-byte quantities. I'm not certain that it's an
intentional distinction, but it could be.
It's an obvious distinction which would be need because of alignment issues
and other reasons, whether or not the ANSI rules used character access as
the only bypass, rather than specifying that code should use some other
means of indicating aliasing but allowing character access as a deprecated
means of bypass.
I still see no reason to think that K&R were talking about aliasing in
that section.
Post by s***@casperkitty.com
The main change in ANSI C is to make exlicit the rules about how
pointers can be manipulated, in effect mandating what good
programmers already practice and good compilers already enforce.
It's not clear that this refers to the effective type rules, but it's
not clear that it doesn't.
Since malloc returns a range of bytes, and the example given in the
rationale involves accessing an object of static or automatic duration
via pointer of a different type, I think an understanding at the time was
that compiler-placed variables need not be kept strictly in sync with
bytes in memory except when accessed by pointers of their own types, but
I don't think there was any perception that it was illegitimate to use
two different kinds of pointer to operate on an area of memory that wasn't
being used as a compiler-placed object.
I think you're reading more into what K&R wrote than they intended.

What exactly do you mean by "compiler-placed variables"? And what
example in the Rationale are you referring to?
--
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-12-11 16:43:30 UTC
Permalink
Raw Message
Post by Keith Thompson
I still see no reason to think that K&R were talking about aliasing in
that section.
I don't think they were. I am unaware of them having said anything about
aliasing issues in the entire book. In the *absence* of any prohibition
on aliasing, reading a pointer would cause the bytes addressed thereby to
be interpreted as an object of the appropriate type.
Post by Keith Thompson
I think you're reading more into what K&R wrote than they intended.
What exactly do you mean by "compiler-placed variables"? And what
example in the Rationale are you referring to?
The example which was followed by a comment about not needing to support
"dubious" code; I think it involved an integer-type global being written
as a float or vice versa.

By "compiler-placed" variables, I mean those of static or automatic
duration for which the compiler is responsible for procuring storage
somewhere. Perhaps "directly-accessible" might have been better, but I
didn't want to muddy the waters with the fact that on some machines a
compiler might have to generate code to compute the effective address of
things on the stack.

My point is that on a machine where sizeof (short)==2, "short x=y;" might
read two consecutive bytes from memory holding "y" and write two bytes
holding "x", but could also achieve its effect in other ways. It's
possible "x" and "y" might not even be stored in consecutive bytes anywhere.
An operation like "short *x,*y; ... *x=*y;" however would be expected to
read two consecutive bytes identified by *y and write two bytes holding
*x.

The ability to reinterpret memory contents efficiently is extremely
important in many forms of systems programming; I believe the pointer
dereferencing operator of C was intended to be usable for such purpose,
and if it hadn't been there would have been some other operator that
was (though in fact, rather than having an operator which is directly
usable for reinterpreting data, it would have been more efficient to
have barrier directives, and say that no uses before the barrier will
alias each other, and no uses after will alias each other, but uses
before a barrier may alias uses after).
Kaz Kylheku
2015-12-11 17:10:40 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Keith Thompson
I still see no reason to think that K&R were talking about aliasing in
that section.
I don't think they were. I am unaware of them having said anything about
aliasing issues in the entire book. In the *absence* of any prohibition
on aliasing, reading a pointer would cause the bytes addressed thereby to
be interpreted as an object of the appropriate type.
Even in the absence of prohibitions on aliasing, there is no requirement
that optimization must be defeated so that the bytes being accessed
actually contain the most recent value of the object, rather than some
stale value. Or vice versa, that the bytes being stored must invalidate
the cached value of a differently typed view of the object.
s***@casperkitty.com
2015-12-11 17:30:40 UTC
Permalink
Raw Message
Post by Kaz Kylheku
Even in the absence of prohibitions on aliasing, there is no requirement
that optimization must be defeated so that the bytes being accessed
actually contain the most recent value of the object, rather than some
stale value. Or vice versa, that the bytes being stored must invalidate
the cached value of a differently typed view of the object.
Such behaviors may be legitimate in cases where they are consistent with
an implementation's documentation; many compilers had *options* which would
enable various kinds of optimization which imposed restrictions beyond those
implied by hardware, but the default situation was that *in the absence of
documentation to the contrary*, given "short *x,*y;" the statement "*x=*y;"
would use the platform's typical way of reading a two-byte value addressed
by "y", and writing one addressed by "x".

I think what's happened is that over the years C has diverged into two very
different languages used by largely-disjoints sets of people with different
philosophies: applications programmers for high-end computing, and low-level
systems and embedded-systems low-level programmers. A programmer who has
no idea what the underlying behaviors of the native platform would be would
as a consequence have no expectations about how C constructs should map to
such behaviors. By contrast, a programmer who needs a behavior from the
native platform which fits perfectly the defined behavior of a piece of C
code would likely expect the compiler to use the native platform behavior
even in cases where the C Standard wouldn't require it. Programmers of the
former type view those of the latter type as crazy, since they have no clue
about what kinds of things are defined on what processors. Programmers of
the latter type view people writing compilers for the former type as insane
since it seems the compilers go out of their way to break their code for no
sensible reason.

Personally, I think the compiler writers and language maintainers are in
many cases a bit foolish because they invest their efforts into optimizations
which are nowhere near as effective as they could be if they used a more
cooperative approach with programmers and recognized that *if a programmer
who is happy with the performance of a piece of code neglects to add some
directives which could speed it up 100x, there's no reason the compiler
writer should be upset at the missed optimization opportunities*. If a
compiler determines that Undefined Behavior will result if a variable is
greater than 57, but a programmer knows it will never exceed 12, is it
better for the compiler to spend a lot of effort figuring out the variable
will never exceed 57, or--in cases where the programmer cares about speed--
would it be better for the programmer to add a directive telling the
compiler the variable won't exceed 12?
Keith Thompson
2015-12-11 17:18:37 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Keith Thompson
I still see no reason to think that K&R were talking about aliasing in
that section.
I don't think they were. I am unaware of them having said anything about
aliasing issues in the entire book. In the *absence* of any prohibition
on aliasing, reading a pointer would cause the bytes addressed thereby to
be interpreted as an object of the appropriate type.
In the absence of any discussion of alignment, one could assume that
dereferencing a non-null int* should yield an int value -- but we
know that's not always the case. In the absence of any discussion
of some addresses beung valid and others invalid, one could make the
same assumption -- but we know that dereferencing a pointer after the
object it points to has ended its lifetime has undefined behavior.

In that section of K&R, they're merely discussing what objects are
and how pointers work. Since there's no mention of aliasing, it's
not reasonable to conclude that aliasing is permitted in all cases.

K&R2 was based on the ANSI standard. Since it's primarily a
tutorial, it doesn't cover the language definition in the same
depth that the standard does.

Is there anything in K&R2 that actually talks about aliasing?
Is there anything that actually contradicts the effective type
rules given in the standard? Or are you merely asserting that the
relatively vague wording in the introductory parts of K&R2 must
obviously support your preconceived notions?
Post by s***@casperkitty.com
Post by Keith Thompson
I think you're reading more into what K&R wrote than they intended.
What exactly do you mean by "compiler-placed variables"? And what
example in the Rationale are you referring to?
The example which was followed by a comment about not needing to support
"dubious" code; I think it involved an integer-type global being written
as a float or vice versa.
The Rationale (C99RationaleV5.10.pdf) has section numbers, page
numbers, and line numbers. When I asked which example you're
referring to, I was hoping for an exact reference rather than
something I have to search for.

Anyway, the example is in section 6.5, page 60, lines 10-16:

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

and the point of the example is that a compiler is permitted to assume
that a==1, even though b might point to the memory occupied by a and the
assignment might alter its stored value. `b==&a` is the "dubious
possibility" the Rationale was referring to.
Post by s***@casperkitty.com
By "compiler-placed" variables, I mean those of static or automatic
duration for which the compiler is responsible for procuring storage
somewhere. Perhaps "directly-accessible" might have been better, but I
didn't want to muddy the waters with the fact that on some machines a
compiler might have to generate code to compute the effective address of
things on the stack.
I think "named objects" would be a clearer term for what you're trying
to say. So a declared object with automatic or static storage duration
is a "compiler-placed variable", but an object allocated by a call to
malloc() is not. Does that sound right?

Are you saying that the behavior of aliasing is, or should be, different
for named objects vs. allocated objects? (There are some differences in
how the effective type is determined.)
Post by s***@casperkitty.com
My point is that on a machine where sizeof (short)==2, "short x=y;" might
read two consecutive bytes from memory holding "y" and write two bytes
holding "x", but could also achieve its effect in other ways. It's
possible "x" and "y" might not even be stored in consecutive bytes anywhere.
Is this a more complete example of what you're talking about? (It helps
to be very clear about what "x" and "y" are.)

{
short y = 42;
short x = y;
printf("x = %d\n", x);
}

In the absence of the printf call, the entire block could be optimized
away. With the printf, a compiler could generate code equivalent to

puts("x = 42");

But in the abstract machine, two objects of type short are created, one
of them is initialized to 42, and then its value is copied to the other.
Post by s***@casperkitty.com
An operation like "short *x,*y; ... *x=*y;" however would be expected to
read two consecutive bytes identified by *y and write two bytes holding
*x.
Expected by whom?

{
short y_obj = 42;
short x_obj;
short y = &y_obj;
short x = &x_obj;
*x = *y;
printf("*x = %d\n", &x);
}

Are you saying that a compiler is not permitted, or should not be
permitted, to perform the same optimization as for the previous
example? Or does it apply only if x and y point to heap-allocated
objects?

Just as in the previous example, a compiler could legitimately generate
code equivalent to

puts("*x = 42");

[...]
--
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"
Ian Collins
2015-12-12 21:59:45 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
I don't think the maintainers of the C Standard are interested in systems
programming, notwithstanding the fact that C was invented *for that purpose*.
Do you have to keep bringing this up on every available thread?
--
Ian Collins
Loading...