restrict keyword — aliasing hint: Exercises — Coding deep dive

Before we start, one picture to fix vocabulary in your head. When we say two pointers alias, we mean their memory regions touch or overlap. When we say they are disjoint, the regions never share a single byte.

Figure — restrict keyword — aliasing hint

Level 1 — Recognition

Exercise 1.1

Which of these is restrict: (a) a statement, (b) a function, (c) a type qualifier, (d) a preprocessor macro?

Recall Solution

(c) a type qualifier. Just like const sits in the type of a pointer, restrict sits in the type of a pointer (T * restrict p). It is not code that runs; it is a label on the type the compiler reads. See const qualifier for the sibling qualifier.

Exercise 1.2

Read this declaration aloud in plain English:

int * restrict p;

Recall Solution

"p is a pointer to int, and for as long as p is in use, ==any object I reach through p is reached only through p== (or through pointers I copied from p)." It is a promise of no aliasing, nothing more.

Exercise 1.3

True or false: the compiler will emit an error if my two restrict pointers actually overlap.

Recall Solution

False. The compiler cannot prove non-overlap in general (the pointers may come from user input at runtime). So it simply trusts you. A broken promise is undefined behaviour, often only visible at -O2/-O3.

Level 2 — Application

Exercise 2.1

Add restrict (and const where sensible) to make this vectorizable, assuming the three arrays never overlap:

void axpy(float *y, float *x, float a, int n) {
    for (int i = 0; i < n; i++) y[i] = a * x[i] + y[i];
}

Recall Solution

void axpy(float * restrict y, const float * restrict x, float a, int n) {
    for (int i = 0; i < n; i++) y[i] = a * x[i] + y[i];
}

x is only read, so mark it const (a modifiability promise) and restrict (an aliasing promise).
y is written and read, so restrict but not const.
a is a plain value, not a pointer — no qualifier.

Now the compiler knows a store to y[i] can never change x[i+1], so it may load a block of x, multiply-add several lanes at once, and store a block of y. See Compiler optimization & vectorization (SIMD).

Exercise 2.2

In this loop, why does marking factor with restrict let the compiler hoist the read out of the loop?

void scale(float * restrict v, const float * restrict factor, int n) {
    for (int i = 0; i < n; i++) v[i] *= *factor;
}

Recall Solution

Without the promise, the compiler must fear factor points inside v. Then v[i] *= *factor could change *factor itself on some iteration — so it must ==re-read *factor every pass==. With restrict factor, factor cannot alias v, so *factor is loaded once into a register and reused. Fewer memory loads → faster loop.

Exercise 2.3

Rewrite this to promise disjointness, then say in one sentence what could go wrong if the caller ignores that promise:

void merge_sum(long *out, long *in1, long *in2, int n);

Recall Solution

void merge_sum(long * restrict out, const long * restrict in1,
               const long * restrict in2, int n);

If a caller passes an out that overlaps in1 or in2 (e.g. merge_sum(a, a, b, n)), the code has undefined behaviour: the vectorized version may read stale or already-overwritten values, giving wrong sums — and it may only misbehave when optimizations are on.

Level 3 — Analysis

Exercise 3.1

Given int arr[5] = {1,2,3,4,5}; and this restrict copy:

void copy(int * restrict dst, const int * restrict src, int n) {
    for (int i = 0; i < n; i++) dst[i] = src[i];
}

The call copy(arr, arr + 2, 3) copies from {3,4,5} into positions 0..2. Do dst and src overlap? Is the promise honoured? What is arr afterward if the compiler copies front-to-back?

Recall Solution

dst covers bytes of arr[0..2], src covers arr[2..4]. They share arr[2] — so they overlap, the promise is broken, and behaviour is undefined. If (not guaranteed!) the compiler copies simple front-to-back:

i=0: arr[0]=arr[2]=3 → {3,2,3,4,5}
i=1: arr[1]=arr[3]=4 → {3,4,3,4,5}
i=2: arr[2]=arr[4]=5 → {3,4,5,4,5} Result {3,4,5,4,5} — but because it is UB, a vectorized build may give something else. Use memmove semantics for overlap.

Exercise 3.2

Same copy, call copy(arr + 2, arr, 3) — copy {1,2,3} into positions 2..4. Overlap? If the compiler instead vectorizes (reads the whole src block first, then writes), what do you get, and why does that differ from a naive loop?

Recall Solution

dst = arr[2..4], src = arr[0..2] → share arr[2] → overlap → UB.

Naive front-to-back: arr[2]=arr[0]=1, arr[3]=arr[1]=2, arr[4]=arr[2]=1(!) → {1,2,1,2,1} (the write to arr[2] corrupted the later read).
Vectorized (read block {1,2,3} first, then store): {1,2,1,2,3}. Two different answers from the same source line — the visible symptom of relying on restrict when it is false. This is exactly why memcpy is undefined on overlap while memmove is safe.

Exercise 3.3

A student writes:

void f(int * restrict p) {
    int *q = p;      // q derived from p
    *p = 1;
    *q = 2;          // (A)
    int *r = get_other_path();  // NOT derived from p
    *r = 3;          // (B) r happens to point at the same object as p
    printf("%d", *p);
}

Which access, (A) or (B), can violate the restrict promise?

Recall Solution

(B) violates it; (A) is fine. The promise allows access through p and through pointers derived from p — q = p is derived, so *q is legal. But r reaches the same object by a separate, non-derived path; touching the object through r breaks the guarantee that "this object is reached only through p." See Pointer aliasing.

Level 4 — Synthesis

Exercise 4.1

Design a safe API. You must write a function that adds two vectors into a third, but you want it usable even when the caller writes the result on top of an input (c may equal a). Should the output pointer be restrict? Give the signature and justify.

Recall Solution

void vadd(int *c, const int * restrict a, const int * restrict b, int n) {
    for (int i = 0; i < n; i++) c[i] = a[i] + b[i];
}

a and b are read-only and (say) known disjoint → const ... restrict.
c is not restrict**, because the caller is *allowed* to pass c == a. Element-wise c[i]=a[i]+b[i]is safe even whencaliasesa, since each c[i]is written *after* its owna[i]is read and no other index is touched. Markingc` restrict would forbid that legal, useful call. Match the qualifier to the true contract, not to the desire for speed.

Exercise 4.2

Explain, using the disjointness rule from the parent note, why memcpy(dst, src, n) (which declares both parameters restrict) is undefined for overlapping ranges but memmove is not — and write the disjointness condition for memcpy(dst, src, n) as an inequality on addresses.

Recall Solution

memcpy's prototype is void *memcpy(void * restrict dst, const void * restrict src, size_t n);. The two restrict qualifiers assert dst and src name disjoint byte ranges. Formally, treating addresses as integers, the safe condition is: $(dst + n \leq src) \lor (src + n \leq dst)$ i.e. one block ends before the other begins. If neither holds, the ranges overlap and memcpy is UB. memmove omits restrict, so it makes no disjointness promise; it internally chooses a safe copy direction and is defined for any overlap. See memcpy vs memmove.

Level 5 — Mastery

Exercise 5.1

Predict and count. Consider:

void saxpy(float * restrict y, const float * restrict x, float a, int n) {
    for (int i = 0; i < n; i++) y[i] = a * x[i] + y[i];
}

For n = 4, how many loads from memory of a does an optimizing compiler need, and how many for the non-restrict, non-const version in the worst case where it must fear y aliases the storage of a? (a is a value passed in a register, but pretend a naive model spills it.) Focus instead on x reloads: in the aliased worst case, how many extra reloads of already-computed y values are forced across the loop? Give the count of y-writes and the count of x-reads for both versions.

Recall Solution

a is a scalar parameter in a register in both versions — it is loaded once regardless (0 reloads); it is not addressable via x/y, so aliasing of arrays does not touch it. The meaningful difference is ordering and vectorization of the array accesses, not the a count. Counting the array traffic for n = 4:

x-reads: 4 in both versions (one per element — you always need each x[i]).
y-writes: 4 in both versions (one per element).
The restrict version may batch these into 1 vector load of x and 1 vector store of y (4 lanes each) and reorder freely; the non-restrict version must keep them strictly interleaved and ordered (load x[i], load y[i], store y[i], next i) because a store to y[i] might change a not-yet-read x. Numeric summary: x-reads = 4, y-writes = 4 (both versions); vector-instruction count drops from 8 scalar ops to 2 vector ops in the restrict version.

Exercise 5.2

Full trace under both copy orders. Array int a[6] = {10,20,30,40,50,60};. Call the restrict copy from Exercise 3.1 as copy(a, a+1, 5) (shift left by one). Do the regions overlap? Give the result for front-to-back and for back-to-front copy orders, and state which one a correct memmove would pick.

Recall Solution

dst = a[0..4], src = a[1..5] → they overlap heavily → the restrict promise is false → UB.

Front-to-back (i = 0..4): each a[i] = a[i+1] before a[i+1] is overwritten, so: {20,30,40,50,60,60} — correct left-shift! (front-to-back is safe for a left shift).
Back-to-front (i = 4..0): a[4]=a[5]=60, a[3]=a[4]=60(!), a[2]=a[3]=60, a[1]=a[2]=60, a[0]=a[1]=60 → {60,60,60,60,60,60} — corrupted. A correct memmove detects dst < src and copies front-to-back, giving {20,30,40,50,60,60}. Because our restrict copy may legally pick either order, we cannot rely on it — that is the whole lesson.

Exercise 5.3

Synthesis check. In one paragraph, connect four ideas: (i) worst-case aliasing assumption, (ii) restrict as a promise, (iii) undefined behaviour on a broken promise, (iv) why const alone would not help the compiler here.

Recall Solution

A compiler seeing two ordinary pointers must assume the worst case — they might alias — so it inserts defensive reloads and refuses to reorder, killing vectorization. restrict is a programmer's promise that a given pointer is the sole path to its memory, which erases that worst-case fear and unlocks SIMD. But the compiler never checks the promise, so if the regions truly overlap you get undefined behaviour — wrong results that may appear only under optimization. const cannot substitute: const promises "I won't write here," which says nothing about whether another pointer writes here; the aliasing worry is about other pointers touching the data, which only restrict (or C99's restrict semantics) addresses.

Connections

Pointers in C
const qualifier
Pointer aliasing
memcpy vs memmove
Compiler optimization & vectorization (SIMD)
Undefined behaviour in C
C99 standard features