Evolution of C programming practices – Unix 1973–2015

I found a recent paper that also looks at how the BSD code base has evolved, but from a very different perspective compared to my code-size investigation.

The paper "The Evolution of C Programming Practices: A Study of the Unix Operating System 1973–2015" investigates coding style, and tests seven hypotheses by looking at metrics (line length, number of volatile in the source code, etc.) in 66 releases of Unix from 1973 to 2014. The hypotheses are

1. Programming practices reflect technology affordances (e.g. developers may be more liberal with screen space when using high resolution displays)
2. Modularity increases with code size
3. New language features are increasingly used to saturation point
4. Programmers trust the compiler for register allocation
5. Code formatting practices converge to a common standard
6. Software complexity evolution follows self correction feedback mechanisms
7. Code readability increases

and the result is that they seem to be true, as interpreted through the metrics.

There are several things that annoys me with this paper...

Source code change over time

The earliest source code releases in the study are the "Research systems" from Bell Laboratories, which are followed by Bell-32V, different BSD versions from University of California, BSD386, and FreeBSD. Of these, it is only FreeBSD that continues after 1995, so the early range 1973–1995 consists of multiple variants of the OS developed by different groups in parallel, while the data 1996–2014 consists of FreeBSD only. This may affect the interpretation of the data...

Consider for example this plot from the paper, showing the mean comment size

CMCHAR — mean comment size

The first part of the plot that consists of multiple variants of the OS have points all over the place, while the second part is FreeBSD only, and is rather constant. Several of the metrics have this kind of distribution, and I am not convinced that the data can be interpreted as evolution (rather than different projects have different coding style), or that fitting a cubic spline to the data have much value for this data set.

Language change over time

Some of the metrics are for new functionality in the C language, and are used for testing hypothesis 3 — "new language features are increasingly used to saturation point". But that hypothesis is in some sense obviously true for most of the metrics. For example, K&R C did not have volatile, but C90 requires volatile in order to prevent the compiler from optimizing away memory accesses to memory mapped hardware registers. Furthermore, there are only a finite number of places where it makes sense to use it, so it obviously saturates.

So the metrics mostly measure that the projects switched from K&R C to standardized C, and most of the graphs looks like

DVOL — volatile keyword density

That is, first no usage, then the feature is introduced in all relevant places when the project updates the compiler.

One other issue here is that the header files are excluded in the calculated metrics. I do not think it affects the result of the conclusion (as it is a rather weak statement anyway), but I have often seen things like

#define HW_REG volatile unsigned int

being defined in header files, and such usages are not included in the data (and this skews the data in the discussion of restrict, where the code uses it as __restrict in order to be able to define it in a suitable way for old compilers that do not handle restrict).

Release dates

The data points for the releases have somewhat random dates. One issue is that the paper use each release's mean file date (the average of the files' last modification time) instead of the release date (that is why the graphs stop at November 2010, even though FreeBSD 10 was released in 2014). The idea is that this better reflects the age of the code base, but this has the effect of compressing some of the data points (especially the clustering around 1993-1994), and it makes the spline fitting even more suspect.

One other problem is that the original data used by the researchers seems to have incorrect timestamps. For example, 4.3BSD Net/1 was released in 1989, but is listed as 1993-12-25 in the paper. The same is true for at least the Net/2 release too, which was released in 1991, but the paper list it as 1993-07-02.

20 years of NetBSD code bloat

I started with NetBSD in the mid-nineties, on a Sun SPARC ELC with 32Mbyte of memory, where I used GCC and Emacs on X11 with FVWM as the window manager. I'm still using GCC, Emacs, and FVWM with the same configuration files (updated for pointless changes in Emacs and FVWM), but I now need much more memory and CPU performance... I thought it would be interesting to investigate why.

Much of this is likely due to GCC — the GCC 2.7.2 cc1 from NetBSD 1.2 has a text segment size of 1073152 bytes, while GCC 4.8.5 used for today's NetBSD has a size of 11012557, and I believe the dynamic memory and instruction count used during compilation has increased much more than that. But the operating system has also increased in size (for example, NetBSD 1.2 libc.so is 331776 bytes, compared to 1390980 today), and I plan to start my investigation by looking at the OS.

Building NetBSD

One thing I like about NetBSD is that it avoids pointless changes, so the build process has been the same for a long time. In addition, is is easy to cross-compile it for different architectures — in fact, NetBSD is always cross-compiled, even when building e.g. a x86 distribution on a x86 architecture.

There is a script build.sh that sets up everything, so building a release for e.g. Sun SPARC can be done as

./build.sh -u -U -m sparc release

This first compiles the tools needed for the build, then builds the full release of NetBSD, and packages the result. This works on "any" operating system — you can build NetBSD on e.g. Linux and Mac OS X.

Cross-compiling individual components are also trivial. The tools are per default placed in a directory named after the host platform, in my case obj/tooldir.NetBSD-6.1.5-i386/bin. The most useful tool here is a wrapper for make that sets up the environment for cross-compiling. This can be used to compile any component, e.g.

cd lib/libc
../../obj/tooldir.NetBSD-6.1.5-i386/bin/nbmake-sparc

will build libc.so.

Some results

As a first step, I have built a NetBSD release from trunk 1 January each year 2002–2016, mostly just in order to see that it was as easy to build as I thought, and to try to get a feel for what can be interesting to investigate closer. I stopped at 2002, as the build.sh was not available earlier...

I built i386 (which is the NetBSD name for x86, even though it does not support i386 CPUs any longer) and sun3. The reason I choose them is that they represent two extremes of architectures — sun3 is a hardware platform that was obsolete already in the mid-nineties, so software size "should not" increase for it unless new functionality is added, while the i386 hardware is still used, and it has got more features, bigger caches etc., during this time, which may increase code size.

And the code size has increased during this time. For example, this is how libc.so, libm.so, and the kernel have grown:

These plots do not say much, and code increase is not necessarily "bad", even on constrained platforms, if unused functionality never get paged in. My plan is to look into the details of the reason for these increases (such as new functionality, support for more hardware, compiler changes, careless developers, etc.), to get a feel for how much each reason contributes. Please let me know if there are some specific questions you want me to investigate!

Type-based alias analysis in C

There was some concern that type-based alias analysis could cause problems when it was implemented in GCC, but the conclusion (as expressed in the GCC development list) was that all other compilers already did this optimization,¹ so most code had already been fixed:

There's less and less of this code IMHO — modern compilers have been doing this kind of alias analysis for some time and as a result folks have been forced to fix their code. Of course this doesn't apply to Linux and some other free software projects since they only use gcc.

I guess that mail was a bit too optimistic — it was written in 1998, and I still see lots of broken code and complaints about -fstrict-aiasing...

What type-based alias analysis means

An informal description of the type-based alias analysis rules is that every memory location has a type, and you are only allowed to access the memory using the "correct" type (the compiler can, therefore, assume that two accesses with incompatible types do not alias). The C11 standard describes this in 6.5 "Expressions":

An object shall have its stored value accessed only by an lvalue expression that has one of the following types:

• a type compatible with the effective type of the object,
• a qualified version of a type compatible with the effective type of the object,
• a type that is the signed or unsigned type corresponding to the effective type of the object,
• a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object,
• an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), or
• a character type.

As a concrete example, a variable of type int can only be accessed through an int* (including unsigned int*, const int*, etc.) or through a char* (including unsigned char*, const char*, etc.).

These restrictions allow the compiler to reorder operations when the types ensure that they access different objects. Consider the function

int i;

void foo(float *f)
{
    i = 23;
    *f = 0.0;
    i = i + 19;
}

*f cannot modify i as it has a different type, so the compiler is allowed to move the store to i over the store to *f, and the function is optimized to

void foo(float *f)
{
    *f = 0.0;
    i = 42;
}

Note that the type-based aliasing rules only talk about how to access objects, and not about pointer casting — it is allowed to cast pointers between incompatible types (as long as you follow the rules for pointer casts) such as

int i;
float *f = (float *)&i;

But accessing this as *f will now invoke undefined behavior, as the object pointed to is an int, and it is not allowed to access it by an expression having a float type.

type punning — union

There are cases where you must access data using an incorrect type, and there are a few ways to do this. The usual cases are where you need to get the bitwise representation of some value, and we will consider the example from the Wikipedia article on type punning that negates a floating point number by changing the most significant bit. The examples will assume 32-bit int and float.

The naive version of just casting the a pointer to int* does not work

bool is_negative(float x)
{
    unsigned int *ui = (unsigned int *)&x;
    return (*ui & 0x80000000u) != 0; // Undef behavior reading float as int
}

as it breaks the type-based aliasing rules. The best way to solve this is in most cases to use a union²

bool is_negative(float x)
{
    union
    {
        unsigned int ui;
        float f;
    } u;
    u.f = x;  
    return (u.ui & 0x80000000u) != 0;
}

Both GCC and LLVM are smart enough to generate as efficient code as you would have expected from the invalid version above.

The union trick requires that all accesses are done through the union — the result is not defined when accessing through a pointer, even if the pointer has the "correct" type

bool is_negative(float x)
{
    union
    {
        unsigned int ui;
        float f;
    } u;
    u.f = x;
    unsigned int *ui = &u.ui;
    return (*ui & 0x80000000u) != 0;  // Undefined behavior
}

type punning — character pointer

Character pointers can be used to access any type, so the is_negative function can be implemented as

bool is_negative(float x)
{
    unsigned char *p = (unsigned char *)&x;
    return (p[3] & 0x80) != 0;
}

assuming a little-endian architecture.

Note that int8_t is not guaranteed to be of character type. That is, the following function may be invalid

bool is_negative(float x)
{
    uint8_t *p = (uint8_t *)&x;
    return (p[3] & 0x80) != 0;  // Possible undefined behavior
}

Treating int8_t as a character type is the reasonable thing to do, and I would assume all compilers do this. But there are developers that think this is a bug — see the discussion in GCC bug 66110...

type punning — memcpy

A third way to do the type punning is using memcpy

bool is_negative(float x)
{
    unsigned int ui;
    memcpy(&ui, &x, 4);
    return (ui & 0x80000000u) != 0;
}

Both GCC and LLVM are smart enough to optimize away the memcpy, and generate similar code as the version using a union.

This type punning does only work if the destination is a variable — you cannot use malloc:ed memory for this. The reason is that memcpy copies the effective type from its source when writing to allocated memory

bool is_negative(float x)
{
    unsigned int *p = malloc(4);
    if (p == NULL)
        abort();
    memcpy(p, &x, 4);                // Effective type of *p is now float
    return (*p & 0x80000000u) != 0;  // Undef behavior reading float as int
}

allocated memory

Memory returned from malloc does not have a type, so each memory location gets an effective type when it is written. Subsequent reads must then be done according to the type-based aliasing rules as usual.

The type of the allocated memory can be updated by writing with a new type

void *p = malloc(4);
if (p == NULL)
    abort();
*(float *)p = 1.0;      // Effective type is float
do_something(p);
*(int *)p = 0;          // Effective type is now int

which allows the buffer being used for different things over its lifetime.

This may have some surprising effects, such as the examples in GCC bug 69776 and 70484. Consider the function

int f(int *pi, long *pl)
{
    *pi = 1;
    *pl = 0;
    return *(char *)pi;
}

The type-based aliasing rules say that int and long cannot alias, and this function can be optimized to

int f(int *pi, long *pl)
{
    *pi = 1;
    *pl = 0;
    return 1;
}

But it is possible for the pointers to alias if both point to the same malloc:ed memory, so the following will print a different value depending on if the optimization is done or not

int main(void)
{
    void *p = malloc(sizeof(long));
    if (p == NULL)
        abort();
    printf("%d\n", f(p, p));
    return 0;
}

It is a bit unclear exactly what the C standard requires in these cases, and you can argue that the optimization is invalid in this case. Recent versions of GCC are conservative and do not optimize this, but older versions are more aggressive, so it prudent to try to avoid playing tricks with type changes in allocated memory regardless of what the standard says...

---

1 Many developers seem to think that type-based aliasing was introduced by C99, but that is not true; C90 has essentially the same aliasing rules (although C99 contain some minor clarifications/improvements). I guess the reason for the belief is that GCC added -fstrict-aliasing at roughly the same time as it implemented C99.
2 Many discussions of type punning (such as the Wikipedia article) says that type punning through a union is a GCC extension. The background of this is that C90 said

[...] if a member of a union object is accessed after a value has been stored in a different member of the object, the behavior is implementation-defined.

I believe the committee intended it to work, but made it "implementation-defined" as the concrete result depends on the implementation (byte order, trap representations, etc.). But "implementation-defined" lets the compiler do whatever it wants, as long as the behavior is documented (and the original implementation in GCC did, in fact, have additional restrictions, although that was fixed before the release). GCC documents this works for C90 too, so it is in some sense a GCC extension...

Dangling pointers and undefined behavior

My previous blog post "C pointers are not hardware pointers" says that dangling pointers may invoke undefined behavior even if they are not dereferenced, as in the example

void foo(int *p, int *q)
{
    free(p);
    if (p == q)  // Undefined behavior!
        bar();
}

I have got lots of questions and comments of the form "This cannot be right — the comparison must be valid as p is not modified by free(p)", so this blog post provides more details.

That the behavior is undefined follows from C11 6.2.4 "Storage durations of objects"

The lifetime of an object is the portion of program execution during which storage is guaranteed to be reserved for it. An object exists, has a constant address, and retains its last-stored value throughout its lifetime. If an object is referred to outside of its lifetime, the behavior is undefined. The value of a pointer becomes indeterminate when the object it points to (or just past) reaches the end of its lifetime.

and 7.22.3 "Memory management functions" that says that free ends the lifetime of objects

The lifetime of an allocated object extends from the allocation until the deallocation.

The reason for the standard to make this undefined behavior is that even simple operations on dangling pointers, such as assignment or comparison, may misbehave and result in exceptions or arbitrary values on some architectures.¹ The C99 rationale has an example of how this can happen

Consider a hypothetical segmented architecture on which pointers comprise a segment descriptor and an offset. Suppose that segments are relatively small so that large arrays are allocated in multiple segments. While the segments are valid (allocated, mapped to real memory), the hardware, operating system, or C implementation can make these multiple segments behave like a single object: pointer arithmetic and relational operators use the defined mapping to impose the proper order on the elements of the array. Once the memory is deallocated, the mapping is no longer guaranteed to exist. Use of the segment descriptor might now cause an exception, or the hardware addressing logic might return meaningless data.

---

1. At least on architectures that existed when the first version of the standard was written.

Why volatile is hard to specify and implement

Volatile in C

The main use case for volatile in C is memory mapped hardware where reads and writes may change the hardware state (even reads may change the state — it is common that e.g. a read of an interrupt register resets the value). This means that the compiler must not eliminate, introduce, or reorder memory accesses to such memory.

Real world hardware have restrictions that makes it is hard to specify access rules in a way that works on all hardware. A few examples:

• The original DEC Alpha processor could only do 32-bit load/store operations, so access to an 8-bit variable must be done by reading 32 bits, modifying the value, and writing back the result. This means that writing one element in

  volatile char a[4];
  

  will read and write all the elements.
• Unaligned load/store operations are split into two operations on the bus.
• The hardware may have restrictions on how read-modify-write instructions are used for memory mapped hardware, so e.g. incrementing a volatile variable as a++ may need to be done as a load, an addition, and a store, even if the CPU has an instruction that increments a value in memory.

The standard solves these problems by saying that accesses to volatile objects need to be done as in the source code, but it is up to the implementation to define what constitutes an "access". The text of this is in C11 6.7.3 "Type qualifiers":

An object that has volatile-qualified type may be modified in ways unknown to the implementation or have other unknown side effects. Therefore any expression referring to such an object shall be evaluated strictly according to the rules of the abstract machine, as described in 5.1.2.3. Furthermore, at every sequence point the value last stored in the object shall agree with that prescribed by the abstract machine, except as modified by the unknown factors mentioned previously. What constitutes an access to an object that has volatile-qualified type is implementation-defined.

This means that an implementation can do essentially anything for volatile as long as it can cover this by a definition of "access", but even a reasonable definition may produce surprises. For example, the text above talks about "at every sequence point". This means that the compiler is allowed to optimize

volatile int *p = somevalue;
int s = *p + *p;

as if it said

volatile int *p = somevalue;
int tmp = *p;
int s = tmp + tmp;

as both reads of *p are between sequence points. A similar case is when the value of an assignment expression is used, such as

volatile int a, b;
a = b = 0;

The standard does not say if b is read, i.e. the compiler is allowed to compile this as

b = 0; a = 0;

or

b = 0; a = b;

The examples above are probably not that common, but even trivial cases may be surprising. Consider the load *p in

volatile int *p = somevalue;
*p;

C++ compilers must not generate a load for this case (because of the C++ rules regarding lvalue-to-rvalue conversion). Many developers argue that C compilers must generate a load, but I'm not completely convinced. And, for example, the GCC 5.3.0 manual describes this as if the compiler has a choice:

According to the C standard, such an expression is an rvalue whose type is the unqualified version of its original type, i.e. int. Whether GCC interprets this as a read of the volatile object being pointed to or only as a request to evaluate the expression for its side-effects depends on this type.

If it is a scalar type, or on most targets an aggregate type whose only member object is of a scalar type, or a union type whose member objects are of scalar types, the expression is interpreted by GCC as a read of the volatile object; in the other cases, the expression is only evaluated for its side-effects.

Anyway, many C compilers do not generate the load, so you should not rely on this construct, regardless of what is the right interpretation of the standard.

Using volatile to limit optimization

The C standard specifies that volatile accesses will not be reordered or removed, but CPUs have things like write buffers that reorder and removes writes. That functionality is usually disabled for the memory regions that contain memory mapped hardware, but it is enabled for the stack. This always confuses me when I see local variables being volatile (when not needed by longjmp) — why is it OK for the CPU to reorder memory operations when the compiler must not do it? What did the developer expect to achieve by adding volatile?

The idea is usually to use volatile to disable compiler optimizations. A typical example is cryptographic code that want to clear sensitive data from memory. The "obvious" way of clearing memory does not work

void getPassword(void) {
    char pwd[64];
    if (GetPassword(pwd, sizeof(pwd))) {
        /* Checking of password, secure operations, etc. */
    }
    memset(pwd, 0, sizeof(pwd));
}

as the compiler may optimize away the memset, and the usual suggestion is to change the memset to something like

volatile char *p = pwd;
for (size_t i = 0; i < sizeof(pwd); ++i)
    p[i] = 0;

This may generate store instructions, but it is not guaranteed to clear the memory! Consider for example a hypothetical architecture that invalidates the cache for the stack frame when popping the stack, instead of wasting power and memory bandwidth by writing the now useless data to the memory — the cache will be invalidated before the newly written zeros have reached main memory.

One other problem is that the compiler may have placed sensitive data in "anonymous" temporary space allocated on the stack (e.g. by spilling), in registers etc., as is discussed in "Zeroing buffers is insufficient":

I am absolutely certain that there is software out there which inadvertantly keeps an AES key sitting in an XMM register long after it has been wiped from memory.

It may still be prudent to try to clear the memory (and it does not hurt), but be aware that it is not guaranteed to help either...

Volatile and real world compilers

Compilers tend to have much code handling special cases. There are several reasons, such as

• Different operations can be optimized in different ways
• General optimizations are often expensive, so it makes sense to handle cheap cases separately in order to reduce the load on the general optimization pass, or to be able to do the cheaper cases more often
• The compiler may need different optimization strategies depending on surrounding code (e.g. depending on register pressure)
• Different target CPUs need different optimization strategies

It is easy to forget to check for "volatile" in some obscure corner case, and it is hard test in a way that finds all such problems, so it is not that uncommon to find cases where volatile accesses are reordered/removed.

One example of this is discussed in OpenSSL pull request #102:

#include <stddef.h>

static void memset_s(void * v, size_t n) {
    volatile unsigned char * p = (volatile unsigned char *)v;
    for (size_t i = 0; i < n; ++i) {
        p[i] = 0;
    }
}

void f1() {
    unsigned char x[4];
    memset_s(x, sizeof x);
}

void f2() {
    unsigned char x[7];
    memset_s(x, sizeof x);
}

Current GCC optimizes away the memset_s in f1, but keeps it in f2.

Both functions are optimized the same by the high-level optimizations — the memset_s is inlined, and the loop unrolled:

f1 ()
{
  unsigned char x[4];

  <bb 2>:
  MEM[(volatile unsigned char *)&x] ={v} 0;
  MEM[(volatile unsigned char *)&x + 1B] ={v} 0;
  MEM[(volatile unsigned char *)&x + 2B] ={v} 0;
  MEM[(volatile unsigned char *)&x + 3B] ={v} 0;
  x ={v} {CLOBBER};
  return;
}

f2 ()
{
  unsigned char x[7];

  <bb 2>:
  MEM[(volatile unsigned char *)&x] ={v} 0;
  MEM[(volatile unsigned char *)&x + 1B] ={v} 0;
  MEM[(volatile unsigned char *)&x + 2B] ={v} 0;
  MEM[(volatile unsigned char *)&x + 3B] ={v} 0;
  MEM[(volatile unsigned char *)&x + 4B] ={v} 0;
  MEM[(volatile unsigned char *)&x + 5B] ={v} 0;
  MEM[(volatile unsigned char *)&x + 6B] ={v} 0;
  x ={v} {CLOBBER};
  return;
}

The difference is introduced when the GIMPLE IR above is lowered to the representation used for instruction selection: the compiler sees that x[4] is an int-sized non-volatile array on the stack, where all accesses are using known indices, and this is a special case where it is profitable to place the array in a register (that is then eliminated as its value is never used). The problem is that this is not a valid transformation unless all accesses are non-volatile, and the code forgot to check for this...

Pointer casts in C

The C standard has more restrictions on pointers than what was discussed in the previous blog post. This post covers pointer casts.

Pointer casts and alignment

Casting a pointer invokes undefined behavior if the resulting pointer is not correctly aligned. The standard is written in this way in order to support architectures that use different formats for different kinds of pointers, and such architectures do exist — see for example this mail to the GCC development list about a mainframe architecture that was recently commercially supported with a GCC 4.3 port.

The compiler may use this to optimize memory accesses for processors with strict alignment requirements (such as old ARM processors). Consider for example

void foo(void *p)
{
    memset(p, 0, 4);
}

that clears 32 bits of data. This could be generated as a 32-bit store, but the alignment of p is unknown, so the compiler must generate this as four byte operations if it want to inline the memset

mov     r3, #0
strb    r3, [r0, #0]
strb    r3, [r0, #1]
strb    r3, [r0, #2]
strb    r3, [r0, #3]

Consider now

void bar(int *);

void foo(void *p)
{
    memset(p, 0, 4);
    bar(p);
}

The call to bar will convert p to an int* pointer, and this invokes undefined behavior if p is not 32-bit aligned. So the compiler may assume p is aligned, and the memset can now be generated as a 32-bit store

mov     r3, #0
str     r3, [r0, #0]

This example illustrates two things that often cause confusion with regard to undefined behavior

• The effect of undefined behavior may go back in time — the undefined behavior is invoked when calling bar, but the compiler may use this to optimize code executed before bar in a way that would make it misbehave if p was not correctly aligned.
• The compiler just use the undefined behavior of misaligned conversion to determine that p must be aligned, which then affects each use of p in the same way as if the alignment had been known by some other means — i.e. the compiler developers do not go out of their way implementing evil algorithms doing obscure transformations back in time based on undefined behavior.

Function pointers

It is not allowed to cast between a function pointer and a pointer to object type (i.e. a "normal" pointer). The reason is that they may be very different on a hardware level, and it may be impossible to represent data pointers as function pointers, or vice versa. One trivial example is when function pointers and data pointers have different width, such as the MS-DOS "medium" memory model that use 32-bit pointers for code but only 16-bit pointers for data.

Casting between integers and pointers

Casting between integers and pointers are implementation defined, so the compiler may choose to handle this in any way it want (although the standard has a footnote saying that the intention is that the mapping between pointers and integers should "be consistent with the addressing structure of the execution environment").

The only thing that is guaranteed to work on any implementation is casting between the integer value 0 and pointers:

An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.

I have read far too many confused discussions about if the value of NULL is guaranteed to be 0. In some sense it is, as (void*)0 == NULL evaluates to true, but the value of (void*)NULL does not need to be 0 when stored in memory — the implementation may for example choose to implement the cast operator as flipping the most significant bit,¹ which means that the code

union {
    uintptr_t u;
    void *p;
} u;
u.p = 0;
printf("0x%" PRIxPTR "\n", u.u);

prints 0x80000000 on a 32-bit machine.

One other thing to note is that NULL is defined as being a "null pointer constant", which does not need to be of a pointer type per the quoted text above! This may cause problems when passing NULL to a va_arg function.

---

1. This is not a completely stupid example. Consider a small embedded processor that has some hardware mapped at address 0. The platform does not have much memory, so 0x80000000 is guaranteed not to be a valid address, and the implementation use this for NULL. There are in general better ways of handling this, but I have seen this done for real hardware...

C pointers are not hardware pointers

Pointers in the C language are more abstract than pointers in the hardware, and the compiler may surprise developers that think that pointers in C work in the same way as pointers in the CPU.

A C pointer points into what the standard calls an object, points to the byte following the object, or has the value NULL. The concept of "object" here is very different from the C++ object — an object in the C standard is a range of bytes allocated as a unit,¹ so x and y are objects in

int x;
struct foo y[10];

and the memory returned by a call to malloc is an object.

Dangling pointers are dangerous, and may invoke undefined behavior even when they are not dereferenced. The reason is that the value of a pointer becomes indeterminate when the object it points to (or just past) reaches the end of its lifetime. That is, a dangling pointer is treated the same way as an uninitialized pointer, and all use of uninitialized values invokes undefined behavior.

void foo(int *p, int *q)
{
    free(p);
    if (p == q)  // Undefined behavior!
        bar();
}

The pointer p has indeterminate value after free(p), so the comparison invokes undefined behavior.

Comparing pointers using the relational operators (<, >, <=, and >=) requires them to point into the same object (or the byte following the object). That is

int *p = malloc(64 * sizeof(int));
int *q = p + i;
if (p < q)
   foo();

is fine (provided that 0 ≤ i ≤ 64), but

int *p = malloc(64 * sizeof(int));
int *q = malloc(64 * sizeof(int));
if (p < q)  // Undefined behavior!
   foo();

invokes undefined behavior. Similarly, subtraction of pointers are only allowed for array objects, and both pointers must point into the same array object (or the byte following the object).

Arithmetic on a pointer cannot make it point outside the object (more than on the byte following the object). In particular, arithmetic on a pointer cannot make it point into another object. This is useful for compilers, as they can use this to track memory accesses and trivially determine that reads and writes through pointers derived from different objects do not conflict. Actually, it would be very hard for the compiler to place variables in registers if writes through pointers could modify arbitrary objects!

There is however one special case where a pointer can point to the address of another object — two objects may be placed next to each other in memory, which is typical for cases such as as

int x, y;

and p and q can now have the same value after

int *p = &x + 1;
int *q = &y;

But the pointer p does not really point to y — it points to the address following x. Dereferencing p invokes undefined behavior, so you cannot really use the fact that p and q have the same value.

GCC has a somewhat aggressive interpretation on the standard, so it compiles p == q to false if it determines that they are derived from different objects (see GCC bug 61502 for details). This has the fun effect that it is possible to get pointers p and q that point at the same memory address, but p == q evaluates to false, as in

#include <stdio.h>

int main(void)
{
    int x, y;
    int *p = &x + 1;
    int *q = &y;
    printf("%p %p %d\n", (void*)p, (void*)q, p == q);
    return 0;
}

that prints

0x7f7fffffdafc 0x7f7fffffdafc 0

on my development machine when compiled with a recent GCC.

---

1. The C standard's definition of object is a bit more involved, as it also involves the type of the data within the range of bytes, but this does not affect the discussion in this blog post. I'll come back to the type related part in a future blog post on aliasing.

This blog post was updated 2016-05-19:

• Added casts in last example
• Changed 256 to 64*sizeof(int) in examples

How undefined signed overflow enables optimizations in GCC

Signed integers are not allowed to overflow in C and C++, and this helps compilers generate better code. I was interested in how GCC is taking advantage of this, and here are my findings.¹

Signed integer expression simplification

The nice property of overflow being undefined is that signed integer operations works as in normal mathematics — you can cancel out values so that (x*10)/5 simplifies to x*2, or (x+1)<(y+3) simplifies to x<(y+2). Increasing a value always makes it larger, so x<(x+1) is always true.

GCC iterates over the IR (the compiler's Internal Representation of the program), and does the following transformations (x, and y are signed integers, c, c1, and c2 are positive constants, and cmp is a comparison operator. I have only listed the transformations for positive constants, but GCC handles negative constants too in the obvious way)

• Eliminate multiplication in comparison with 0

  (x * c) cmp 0   ->   x cmp 0 
  

• Eliminate division after multiplication
  

  (x * c1) / c2   ->   x * (c1 / c2) if c1 is divisible by c2
  

• Eliminate negation

  (-x) / (-y)     ->   x / y
  

• Simplify comparisons that are always true or false

  x + c < x       ->   false
  x + c <= x      ->   false
  x + c > x       ->   true
  x + c >= x      ->   true
  

• Eliminate negation in comparisons

  (-x) cmp (-y)   ->   y cmp x
  

• Reduce magnitude of constants

  x + c > y       ->   x + (c - 1) >= y
  x + c <= y      ->   x + (c - 1) < y
  

• Eliminate constants in comparisons

  (x + c1) cmp c2         ->   x cmp (c2 - c1)
  (x + c1) cmp (y + c2)   ->   x cmp (y + (c2 - c1)) if c1 <= c2
  

  The second transformation is only valid if c1 <= c2, as it would otherwise introduce an overflow when y has the value INT_MIN.

Pointer arithmetic and type promotion

If an operation does not overflow, then we will get the same result if we do the operation in a wider type. This is often useful when doing things like array indexing on 64-bit architectures — the index calculations are typically done using 32-bit int, but the pointers are 64-bit, and the compiler may generate more efficient code when signed overflow is undefined by promoting the 32-bit integers to 64-bit operations instead of generating type extensions.

One other aspect of this is that undefined overflow ensures that a[i] and a[i+1] are adjacent. This improves analysis of memory accesses for vectorization etc.

Value range calculations

The compiler keeps track of the variables' range of possible values at each point in the program, i.e. for code such as

int x = foo();
if (x > 0) {
  int y = x + 5;
  int z = y / 4;

it determines that x has the range [1, INT_MAX] after the if-statement, and can thus determine that y has the range [6, INT_MAX] as overflow is not allowed. And the next line can be optimized to

  int z = y >> 2;

as the compiler knows that y is non-negative.

The undefined overflow helps optimizations that need to compare two values (as the wrapping case would give possible values of the form [INT_MIN, (INT_MIN+4)] or [6, INT_MAX] that prevents all useful comparisons with < or >), such as

• Changing comparisons x<y to true or false if the ranges for x and y does not overlap
• Changing min(x,y) or max(x,y) to x or y if the ranges do not overlap
• Changing abs(x) to x or -x if the range does not cross 0
• Changing x/c to x>>log2(c) if x>0 and the constant c is a power of 2
• Changing x%c to x&(c-1) if x>0 and the constant c is a power of 2

Loop analysis and optimization

The canonical example of why undefined signed overflow helps loop optimizations is that loops like

for (int i = 0; i <= m; i++)

are guaranteed to terminate for undefined overflow. This helps architectures that have specific loop instructions, as they do in general not handle infinite loops.

But undefined signed overflow helps many more loop optimizations. All analysis such as determining number of iteration, transforming induction variables, and keeping track of memory accesses are using everything in the previous sections in order to do its work. In particular, the set of loops that can be vectorized are severely reduced when signed overflow is allowed.

---

1. Using GCC trunk r233186,  "gcc version 6.0.0 20160205 (experimental)"

This blog post was updated 2016-02-23:

• Corrected first sentence to say "overflow"instead of "wrap".
• Removed one incorrect transformation from "Eliminate Negation" where I had misread the GCC source code.
• Corrected the ranges in the "Value range calculations" example.