Use __restrict__ Pointer to Enable Alias Analysis Optimization

Topic Overview

Promise Non-Overlapping Pointers

C99 restrict tells the compiler two pointer parameters do not alias the same memory, enabling aggressive load/store reordering and vectorization. Violating the promise is undefined behavior. BLAS kernels and memcpy implementations use restrict heavily.

Example Kernel

Separate read and write buffers with restrict so the compiler can vectorize the loop without runtime alias checks.

cCopy
Loading…

• -fno-strict-aliasing disables type-based alias analysis; avoid in hot code
• __restrict__ is the GCC spelling accepted in C++
• restrict on struct members is C99 only in limited cases
• Compare assembly with and without restrict on the same loop

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will mark a hot loop with restrict and show improved vectorization or fewer memory barriers in assembly. This exercise asks you to document the aliasing assumption.

Your Task

For void add(int *dst, int *a, int *b, int n) with dst[i] = a[i] + b[i], the compiler cannot assume the arrays are separate. If dst overlaps a, a store can change a later load. So it either stays scalar, or emits a runtime overlap check that picks a vector loop only when that is safe. __restrict__ promises "no overlap", so the vector loop runs unconditionally, and if the promise is false the results are silently wrong. Simulate all three on real memory.

Input

cCopy
Loading…

Rules

• C semantics: the scalar loop for i: m[DST+i] = m[A+i] + m[B+i].
• Vector loop: for each full chunk of W, first load all W sums into temporaries, then store all W. Any remainder runs scalar.
• Without restrict: the compiler's check passes when each source range is either disjoint from [DST, DST+N) or identical to it (DST == A, in-place). If the check passes, run the vector loop, otherwise the scalar one.
• With restrict: always run the vector loop.
• Describe each overlap as no overlap, same array (in place), overlap, dst is K elements after X or overlap, dst is K elements before X.
• Verdict:
  • restrict was a lie: K of N results wrong if the restrict results differ from C semantics.
  • Otherwise, if the check failed: overlap happens to be harmless for this width.
  • Otherwise, if a source is the destination itself: results match, but passing the same array to restrict pointers is still undefined.
  • Otherwise: restrict is correct here.
• Errors: width: 1..16 and call: out of bounds (memory has 64 ints) (every range must fit, and N >= 1).

Output

cCopy
Loading…

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Implement the vector loop as load-all-then-store-all per chunk. That ordering is exactly why it differs from scalar code under overlap.
2. Start every run from freshly initialised memory, so the three versions are compared on identical input.

Hidden tests cover overlap distances smaller and larger than the vector width, a width of 1 (vectorising changes nothing), overlap with b instead of a, remainders that do not fill a chunk, in-place calls, and out-of-bounds calls.