Can this mostly useless while loop be optimized out?

[Francois Grieu]

// This post is a valid C program

#include <stdio.h>
#include <stdlib.h>

typedef struct tFoo
{
int *fPtr;
int fIntA;
int fIntB;
} tFoo;

tFoo *gFoo;

// assuming inNbFoo>=0 and inNbFoo<=SIZE_MAX/sizeof(tFoo)
// allocate inNbFoo tFoo and set all fields to NULL or 0
void setfoo(int inNbFoo)
{
gFoo = calloc(inNbFoo,sizeof(*gFoo));
if (gFoo!=NULL)
while(--inNbFoo)
gFoo[inNbFoo].fPtr = NULL;
}

int main(void)
{
setfoo(7);
if (gFoo!=NULL && gFoo[0].fPtr!=NULL)
printf("wrongo\n");
return 0;
}

/*
For strict portability, it appears that the while loop is mandatory,
in case NULL is not represented by the all-zero bit pattern.
But is there a portable way to determine at compile time that it
is not needed, which is the case on most machines, and/or
otherwise help the compiler to remove the while loop ?

TIA,
Francois Grieu
*/

 

[Jens Thoms Toerring]

// This post is a valid C program

#include <stdio.h>
#include <stdlib.h>

typedef struct tFoo
{
int *fPtr;
int fIntA;
int fIntB;
} tFoo;

tFoo *gFoo;

// assuming inNbFoo>=0 and inNbFoo<=SIZE_MAX/sizeof(tFoo)
// allocate inNbFoo tFoo and set all fields to NULL or 0
void setfoo(int inNbFoo)
{
gFoo = calloc(inNbFoo,sizeof(*gFoo));
if (gFoo!=NULL)
while(--inNbFoo)
gFoo[inNbFoo].fPtr = NULL;
}

int main(void)
{
setfoo(7);
if (gFoo!=NULL && gFoo[0].fPtr!=NULL)
printf("wrongo\n");
return 0;
}

For strict portability, it appears that the while loop is mandatory,
in case NULL is not represented by the all-zero bit pattern.
But is there a portable way to determine at compile time that it
is not needed, which is the case on most machines, and/or
otherwise help the compiler to remove the while loop ?

If have no idea on how to do it at compile time, but at
run time you could try

int *dummy = NULL;

gFoo = calloc( inNbFoo, sizeof *gFoo );
if ( gFoo != NULL
&& memcmp( &dummy, &gFoo[ 0 ].fPtr, sizeof gFoo[ 0 ].fPtr ) )

to compare the bit pattern of a known NULL pointer to that
of one that was initialized with all bits set to 0. Of course,
there could be false positives on a hypothetical system that
has both a all-bits-null NULL pointer and a non-all-bits-null
NULL pointer at the same time, but the worst that then happens
is that the pointers get set to NULL unnecessarily. I also
considered using just

gFoo[ 0 ].fPtr != NULL

for the test, but then machines could exist where a pointer
with all-bits-null is a trap representation, so just using
the value of 'gFoo[ 0 ].fPtr' could result in undefined be-
haviour...
Regards, Jens

 

[Eric Sosman]

[...]
// assuming inNbFoo>=0 and inNbFoo<=SIZE_MAX/sizeof(tFoo)
// allocate inNbFoo tFoo and set all fields to NULL or 0
void setfoo(int inNbFoo)
{
gFoo = calloc(inNbFoo,sizeof(*gFoo));
if (gFoo!=NULL)
while(--inNbFoo)
gFoo[inNbFoo].fPtr = NULL;
}

Aside: Note that this loop leaves gFoo[0].fPtr un-set,
and that it misbehaves badly if inNbFoo is initially zero.

For strict portability, it appears that the while loop is mandatory,
in case NULL is not represented by the all-zero bit pattern.
But is there a portable way to determine at compile time that it
is not needed, which is the case on most machines, and/or
otherwise help the compiler to remove the while loop ?

I can think of no way to make the determination at
compile time. You could, of course, run a "helper" program
that wrote an appropriate #define into a file that you would
then #include when compiling the "real" program.

For related situations I wrote a fillmem() function that
fills a memory area with repetitions of an arbitrary pattern,
using memcpy() with successively-doubling sizes. If you're
interested, you can find the source in my post of <Googles>
May 12, 2005.

 

[Ben Bacarisse]

// This post is a valid C program

#include <stdio.h>
#include <stdlib.h>

typedef struct tFoo
{
int *fPtr;
int fIntA;
int fIntB;
} tFoo;

tFoo *gFoo;

// assuming inNbFoo>=0 and inNbFoo<=SIZE_MAX/sizeof(tFoo)
// allocate inNbFoo tFoo and set all fields to NULL or 0
void setfoo(int inNbFoo)
{
gFoo = calloc(inNbFoo,sizeof(*gFoo));
if (gFoo!=NULL)
while(--inNbFoo)
gFoo[inNbFoo].fPtr = NULL;
}

If have no idea on how to do it at compile time, but at
run time you could try

int *dummy = NULL;

An small nit: you should use a pointer of the same type (or at the
least another struct pointer) since int pointers may have a different
representations than struct pointers.

To the OP:
If you have an integer type the same size as a struct pointer (you can
test this at compile time) then you can do this:

union ptr_test {
struct dummy *dp;
uintptr_t rep;
};

union ptr_test ptest;
ptest.dp = 0;
if (ptest.rep)
/* code to loop setting pointers */

and you can hope that the compiler will optimise away the loop by
knowing that the test is false on machines with all-bits-zero null
struct pointers. A quick test suggests that gcc does do this.

 

[Boon]

To the OP:
If you have an integer type the same size as a struct pointer (you can
test this at compile time) then you can do this:

union ptr_test {
struct dummy *dp;
uintptr_t rep;
};

union ptr_test ptest;
ptest.dp = 0;
if (ptest.rep)

AFAIU, writing to one member of a union, then reading from a different
one is not portable.

In C89 (3.3.2.3 Structure and union members)

"""
With one exception, 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. One special guarantee is made
in order to simplify the use of unions: If a union contains several
structures that share a common initial sequence, and if the union
object currently contains one of these structures, it is permitted to
inspect the common initial part of any of them. Two structures share
a common initial sequence if corresponding members have compatible
types for a sequence of one or more initial members.
"""

In C99 (6.2.6.1 General)

"""
When a value is stored in a member of an object of union type, the bytes
of the object representation that do not correspond to that member but
do correspond to other members take unspecified values.
"""

 

[Ben Bacarisse]

AFAIU, writing to one member of a union, then reading from a different
one is not portable.

Yes, you are right but in some sense that is the point! We want the
implementation defined effect of re-interpreting the bits as an int.

If the machines you want to port to have ints with no trap
representations then all is well. But you are right that there is a
problem if the bits used for a null struct pointer are a trap
representation for the uintptr_t type and I can't say off hand if this
can be avoided. Can you see a fix? It would be a good solution if it
can be made DS9000-proof.

I wanted to get round using memcmp since gcc does not detect when
memcpy(&nullptr, &zerobits, sizeof nullptr) is zero. It does detect
the integer test.

 

[Jens Thoms Toerring]

(e-mail address removed) (Jens Thoms Toerring) writes:

// This post is a valid C program

#include <stdio.h>
#include <stdlib.h>

typedef struct tFoo
{
int *fPtr;
int fIntA;
int fIntB;
} tFoo;

tFoo *gFoo;

// assuming inNbFoo>=0 and inNbFoo<=SIZE_MAX/sizeof(tFoo)
// allocate inNbFoo tFoo and set all fields to NULL or 0
void setfoo(int inNbFoo)
{
gFoo = calloc(inNbFoo,sizeof(*gFoo));
if (gFoo!=NULL)
while(--inNbFoo)
gFoo[inNbFoo].fPtr = NULL;
}

If have no idea on how to do it at compile time, but at
run time you could try

int *dummy = NULL;

An small nit: you should use a pointer of the same type (or at the
least another struct pointer) since int pointers may have a different
representations than struct pointers.

Mmm, as far as I can see he wants to initialize int pointers
(that are members of the structure) and not a pointer to the
structure. Shouldn't he then use an int pointer to copy from?

Regards, Jens

 

[Old Wolf]

  union ptr_test {
       struct dummy *dp;
       uintptr_t rep;
  };

  union ptr_test ptest;
  ptest.dp = 0;
  if (ptest.rep)
     /* code to loop setting pointers */

This doesn't test what we want to test; setting
dp = 0 doesn't necessarily set all bits to 0 in
rep. (the int may have padding bits, e.g. if it
is an odd-parity system).

I think the method of comparing a calloc'd pointer
with a null pointer (using memcmp) is the most
promising.

 

[lawrence.jones]

AFAIU, writing to one member of a union, then reading from a different
one is not portable.

In general, yes; but there are specific cases that are well defined (at
least in C99). For examples, writing to one int member and reading from
another int member or storing a non-negative value into an int member
and reading from an unsigned member.

 

[Ben Bacarisse]

(e-mail address removed) (Jens Thoms Toerring) writes:

// This post is a valid C program

#include <stdio.h>
#include <stdlib.h>

typedef struct tFoo
{
int *fPtr;
int fIntA;
int fIntB;
} tFoo;

tFoo *gFoo;

// assuming inNbFoo>=0 and inNbFoo<=SIZE_MAX/sizeof(tFoo)
// allocate inNbFoo tFoo and set all fields to NULL or 0
void setfoo(int inNbFoo)
{
gFoo = calloc(inNbFoo,sizeof(*gFoo));
if (gFoo!=NULL)
while(--inNbFoo)
gFoo[inNbFoo].fPtr = NULL;
}

If have no idea on how to do it at compile time, but at
run time you could try

int *dummy = NULL;

An small nit: you should use a pointer of the same type (or at the
least another struct pointer) since int pointers may have a different
representations than struct pointers.

Mmm, as far as I can see he wants to initialize int pointers
(that are members of the structure) and not a pointer to the
structure. Shouldn't he then use an int pointer to copy from?

Ha! You are right of course. Don't know where I got a struct pointer
type from.

 

[Ben Bacarisse]

This doesn't test what we want to test; setting
dp = 0 doesn't necessarily set all bits to 0 in
rep.

Yes, but that is the whole point of the code: set a pointer to null
and then see if we get zeros or not. This is not properly portable
the null pointer representation may be a trap when interpreted as an
int (i.e. we get UB). There is also the possibility that the null
pointer may look like (a non-trap) negative zero but then all that
happens is we get a harmless "false positive" from the test.

It is possible that this is "portable enough", but since the situation
being covered is not a common one, anything other than a properly
portable solution may not be of any use.

I think the method of comparing a calloc'd pointer
with a null pointer (using memcmp) is the most
promising.

Yes, it is certainly safe but I wanted a method that the compiler
spotted. gcc, at least, does not see that the memcmp will be 0 on my
machine whereas it does spot that the int will be zero.

Using an unsigned char array and an explicit test of the bytes (rather
than a memcmp) similarly foxed the optimiser.

 

[Ben Bacarisse]

I suspect what he means is the following:

Suppose the pointer and the int are 32 bits.

Suppose the pointer bit representation for a null is 0x00000001.

Suppose that's a valid representation of int 0, with the 1 bit being
an odd parity bit. In other words, not a trap representation. The
standard requires the bit representation 0x00000000 to be *a* valid
zero (6.2.6.2{5}), but this of course needn't be the *only* valid
zero. Your code assumes that 0x00000000 is the only valid bit
representation of an int 0.

Yes. I planned on suggesting testing the number of value bits, and/or
the int range but ended up shorting that to "if you have an int type
the same size a pointer" which is too weak. If you have a 2s
complement int type of the right size with no padding, I think it
works. That may be too restrictive to have any value left (since we
are talking about odd machines to start with).

The if-test fails and the code skips setting the pointers manually,
even though that would be required in this case since the pointers
don't have an all-bits-zero representation for null.


A negative zero has at least one 1 bit, so you'd want to set the
pointers manually. But your if-test fails and skips the manual
setting of pointers. This is again because your code assumes that
0x00000000 is the only valid bit representation of int 0.

Yes, its a false negative, not a false positive. Must sleep more.

 

[Nate Eldredge]

Yes, it is certainly safe but I wanted a method that the compiler
spotted. gcc, at least, does not see that the memcmp will be 0 on my
machine whereas it does spot that the int will be zero.

Using an unsigned char array and an explicit test of the bytes (rather
than a memcmp) similarly foxed the optimiser.

I'm not sure it's such a big deal that the compiler should optimize it
out. You can do the test once and then act appropriately thereafter.

thing *allocate_things(int howmany) {
static int calloc_ok = -1;
if (calloc_ok == -1) {
int *ptr = NULL;
char *c = calloc(sizeof(ptr));
if (!c)
return NULL;
if (memcmp(c, &ptr, sizeof(ptr)) == 0)
calloc_ok = 1;
else
calloc_ok = 0;
free(c);
}
if (calloc_ok) {
return calloc(howmany, sizeof(thing));
} else {
thing *p = malloc(howmany * sizeof(thing));
int i;
for (i = 0; i < howmany; i++)
p.field = NULL;
return p;
}
}

If testing calloc_ok every time is too much, you could use a function
pointer.

thing *allocate_things_via_calloc(int howmany);
thing *allocate_things_via_malloc_with_initialization_loop(int howmany);
thing *allocate_things_pickone(int howmany);

thing *(*allocate_things)(int) = allocate_things_pickone;

thing *allocate_things_pickone(int howmany) {
int *ptr = NULL;
char *c = calloc(sizeof(ptr));
if (!c)
return NULL;
if (memcmp(c, &ptr, sizeof(ptr)) == 0)
allocate_things = allocate_things_via_calloc;
else
allocate_things = allocate_things_via_malloc_with_initialization_loop;
free(c);
return allocate_things(howmany);
}

 

[Keith Thompson]

// This post is a valid C program
[snip]

/*
For strict portability, it appears that the while loop is mandatory,
in case NULL is not represented by the all-zero bit pattern.
But is there a portable way to determine at compile time that it
is not needed, which is the case on most machines, and/or
otherwise help the compiler to remove the while loop ?

[...]

There is one problem with writing code that does different things
depending on whether a null pointer is represented as all-bits-zero.
Since null pointers are all-bits-zero on the vast majority of
implementations, the code will probably never actually be tested on a
system where they aren't. If you make a subtle error that only shows
up when null pointer are not all-bits-zero, it's likely that the error
will never be detected. (It's also likely that it will never cause
any problems, but if you're writing the code in the first place you
presumably want to get it right.)

 

[Chetan]

// This post is a valid C program
[snip]

/*
For strict portability, it appears that the while loop is mandatory,
in case NULL is not represented by the all-zero bit pattern.
But is there a portable way to determine at compile time that it
is not needed, which is the case on most machines, and/or
otherwise help the compiler to remove the while loop ?

[...]

There is one problem with writing code that does different things
depending on whether a null pointer is represented as all-bits-zero.
Since null pointers are all-bits-zero on the vast majority of
implementations, the code will probably never actually be tested on a
system where they aren't. If you make a subtle error that only shows
up when null pointer are not all-bits-zero, it's likely that the error
will never be detected. (It's also likely that it will never cause
any problems, but if you're writing the code in the first place you
presumably want to get it right.)

What are the actual implementations where a NULL has a representation
other than all zero bytes?

So far I haven't heard from anyone where it actually is different.
Some compilers for microcontrollers etc. might have a reason to do
such a thing, but I am not sure which ones they are, if any. Of
course, NULL is defined with the assumption it can be changed there
can be compilers with behave that way, but I am interested in actual
cases.

Also, the case of type specific null pointers is too far fetched in
the context.

 

[Keith Thompson]

What are the actual implementations where a NULL has a representation
other than all zero bytes?

I think someone has posted an example. I've certainly seen an
implementation for a language other than C that used something other
than all-bits-zero for the language's equivalent of a null pointer
(<OT>a Pascal implementation that used the value 1; attempts to
dereference it would usually trap on the hardware in question</OT>).

The point is that (a) it's permitted by the language, and (b) if
you're writing defensive code that's intended to work on systems with
non-all-bits-zero null pointers, presumably it's worthwhile to get
both cases right.

So far I haven't heard from anyone where it actually is different.
Some compilers for microcontrollers etc. might have a reason to do
such a thing, but I am not sure which ones they are, if any. Of
course, NULL is defined with the assumption it can be changed there
can be compilers with behave that way, but I am interested in actual
cases.

Actually the definition of NULL needn't have anything to do with the
representation of a null pointer. Either 0 or ((void*)0) is a null
pointer constant, and therefore a valid definition for NULL,
regardless of how a null pointer constant is represented.

Also, the case of type specific null pointers is too far fetched in
the context.

There are real-world systems where different pointer types have
different representations. I've worked on such a system, where all
pointers had the same size, but byte pointers stored a byte offset
(relative to a 64-bit word) in the otherwise unused upper bits.

 

[Chetan]

I think someone has posted an example. I've certainly seen an
implementation for a language other than C that used something other
than all-bits-zero for the language's equivalent of a null pointer
(<OT>a Pascal implementation that used the value 1; attempts to
dereference it would usually trap on the hardware in question</OT>).

The point is that (a) it's permitted by the language, and (b) if
you're writing defensive code that's intended to work on systems with
non-all-bits-zero null pointers, presumably it's worthwhile to get
both cases right.

In a language with strict type checking as Pascal, it is possible, but
in that case, many things can be taken care of by the compiler. I
searched online and haven't found any real example where a C compiler
behaves that way.

Actually the definition of NULL needn't have anything to do with the
representation of a null pointer. Either 0 or ((void*)0) is a null
pointer constant, and therefore a valid definition for NULL,
regardless of how a null pointer constant is represented.

That is fine. I am talking about the machine representation of NULL
pointer, which I thought was question.

There are real-world systems where different pointer types have
different representations. I've worked on such a system, where all
pointers had the same size, but byte pointers stored a byte offset
(relative to a 64-bit word) in the otherwise unused upper bits.

It looks like you are talking about different types of pointers as
against pointers to different types, which I intended.

Anyway, thanks for the response. I haven't visited this group for a
while and the volume seems to be very high.

 

[Keith Thompson]

That is fine. I am talking about the machine representation of NULL
pointer, which I thought was question.

A bit of terminology:

NULL is a macro, defined in <stddef.h> and several other standard
headers. It expands to an implementation-defined null pointer
constant. It's typically either ``0'' or ``((void*)0)''.

A null pointer constant is an integer constant expression with the
value 0, or such an expression cast to void*. It's a construct that
can occur in C source.

A null pointer is a particular value of a pointer type; it doesn't
point to anything. It's a value that can exists during program
execution.

It looks like you are talking about different types of pointers as
against pointers to different types, which I intended.

Um, different types of pointers *are* pointers to different types.
(Well, mostly; qualifiers like "const" can also make a difference.)
Some systems have (had?) things like "near" and "far" pointers, but
that's non-standard.

On the system I referred to above (it was a Cray T90), the hardware
supported pointers to 64-bit words, but the C compiler supported 8-bit
bytes. A pointer to anything that's the size of a word or bigger
(such as int*) is simply a hardware word address. A pointer to a byte
(such as char*) needs additional information to specify which byte
within the word it points to; the compiler stores a 3-bit offset in
the otherwise unused high-order bits of the 64-bit address.

Anyway, thanks for the response. I haven't visited this group for a
while and the volume seems to be very high.

Yes, but the *useful* volume is a bit lower. } 8-(}

 

[Flash Gordon]

In a language with strict type checking as Pascal, it is possible, but
in that case, many things can be taken care of by the compiler.

It is just as possible in C.

I
searched online and haven't found any real example where a C compiler
behaves that way.

<snip>

Search for "null pointer 0x55555555" without the quotes and you will
find someone who actually has an implementation where the null pointer
is not all bits zero. Others may exist either now on in the future. You
just have to decide whether it is worth the effort of catering for such
systems. If you cater for them, then do it properly, if you don't cater
for them properly then you don't need either compile or run time checks
to provide partial/broken support for them.

 

[Tim Woodall]

What are the actual implementations where a NULL has a representation
other than all zero bytes?

So far I haven't heard from anyone where it actually is different.
Some compilers for microcontrollers etc. might have a reason to do
such a thing, but I am not sure which ones they are, if any. Of
course, NULL is defined with the assumption it can be changed there
can be compilers with behave that way, but I am interested in actual
cases.

AS/400. I spent a long time fixing a code base that relied on memsetting
structures to 0 and then assuming the pointers in them NULL.

Also, the case of type specific null pointers is too far fetched in
the context.

Don't know if that was the case or not. I never investigated that far.

See this post for some other quirks of pointers on the AS/400

http://ghostscript.com/pipermail/bug-gs/2001-May/000413.html

Tim.