Pointer Complications

Let’s talk about pointers. As a quick refresher, pointers hold the location of a slot in memory. You can then manipulate this location, either by dereferencing it and getting the items that are being pointed to, or by moving the pointer around with pointer addition.

In C/C++, arrays and pointers are pretty similar, so you can loop through an array using a pointer.

Take this program, which prints out 1 to 5:

#include <stdio.h>

int main() {
    int x[] = {1,2,3,4,5};
    int* start = x;
    int* end = x + 5;
    for (; start < end; start++) { printf("%d, ", *start); }
}

Pointers are useful in many cases – if you want to represent a recursive data structure, you can do so with pointers:

struct Node {
    int value;
    struct Node* next;
};

Also, if you want to just listen to an update to some other memory, you can do so with pointers. Without them, or some related construct, any update to would have to be written to all the listeners, which could be very expensive.

But this makes optimizing code much harder.

Take this simple example:

int is_a(char *a, char *b) {
    *a = 'a';
    *b = 'b';
    return *a == 'a';
}

Since we set the a pointer to ‘a’, and the b pointer to ‘b’, and then check if the a pointer is ‘a’, this should just be return 1. However, the a pointer and the b pointer could be the same pointer.

But the function allows us to pass the same pointer as a and b, which breaks this assumption:

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

int is_a(char *a, char *b) {
    *a = 'a';
    *b = 'b';
    return *a == 'a';
}

int main() {
    char* a = malloc(sizeof(char));
    printf("is_a, %d", is_a(a, a));
}

In which case this returns 0.

If there was some way to say that pointer a and pointer b could not be the same pointer, then we could do this optimization.

C does have a keyword, restrict that hints to the compiler that the memory locations do not alias (they don’t intersect), but in this case it doesn’t generate any better code and it isn’t a compile time restriction, so this keyword isn’t useful in this case.

How do you represent a pointer?

Recently, I’ve been working on a C compiler, and got to the point where I had to support pointers in C.

Most people think that a pointer is a number (with its length being your computer’s word size, normally 64 bits these days), but that doesn’t work. In the previous example above, I did pointer arithmetic on an int* start, with start++ (increment start by 1). However, since an int is 4 bytes, and since each increment prints the next number, this actually increments the pointer by 4 bytes. But if I had a char*, since char is 1 byte, incrementing a char increments the pointer by 1 byte.

On top of its size, a pointer also needs to store its type (since you can’t pass a pointer of a different type to a function that wants a specific pointer), but you also need to support casting.

A pointer can be cast to a number, or to another pointer type. If cast to a number, and then back to a pointer, what happens to its type information, or its size? Does it disappear? Some important questions to ponder.

Also, you’d want to have type-safety with pointers. It would be odd to take a pointer to an int and then change it to a pointer to another type, like an array. It makes sense to increment or decrement the pointer to an array, but not for a pointer to an int. If this is the case, then pointers should also hold their type.

On top of that, pointers can point to initialized or uninitialized memory. So that needs to be handled too – in C++, the end pointer of a collection always points to one past the end of a collection, which is generally uninitialized.

Also for optimization reasons, it’s also useful to know if pointers alias, or if a certain location in memory is only accessible by one pointer or multiple. In the is_a example above, if we know that the two pointers are different and cannot access the same location, then we can emit “return true” for the function. But that also requires keeping track of where it came from, which is called provenance. This information is important for optimizations, but also useful for error messages to the user – if the compiler knows where a pointer came from, and the user tries to use it incorrectly, it’ll have more information about how things went wrong.

Pointers are complicated. They’re also not just a number.