The provenance memory model for C

Summary

Pointer aliasing and program optimization We say that two pointer values p and q during the execution of a program alias if they point to the same object in memory. To see that the question if two pointers alias has an influence on the optimization of code, let’s consider the following simple example of an iterative function. It implements an approximation algorithm for the reciprocal r := 1/a of the value a := *aₚ which doesn’t use division. // Reciprocal approximation // // This interface is horrific, don't use it. // This just serves as an artificial example // for this article. constexpr double ε = 0x1P-24; constexpr double Π⁻ = 1.0 - ε; constexpr double Π⁺ = 1.0 + ε; void recip(double* aₚ, double* řₚ) { for (;;) { register double Π = (*aₚ)*(*řₚ); if ((Π⁻ < Π) && (Π < Π⁺)) { break; } else { (*řₚ) *= (2.0 - Π); } } } The function receives a pointer to a second value ř := *řₚ with a rough approximation for r. It then iteratively approaches r within a chosen precision ε: the current values a and ř are multiplied into a value Π and if that value is sufficiently close to 1.0 the iteration stops. If it is not, ř is corrected and the loop continues. What is interesting for our context of aliasing is that this function has two pointer arguments that both point to a value of the same type double. One of these pointer targets *řₚ is loaded from memory, modified and stored at each iteration. In total, the non-optimized function as specified above in each iteration has 3 load and 1 store operations, 2 comparisons, 1 logical operation, and 3 arithmetic operations. So loads and stores from memory make up 4 of about 10 operations in total. But wait, can’t this be done better? Yes, obviously, a much better version of this could look as follows. void recip⁺(double* aₚ, double* řₚ) { register double a = *aₚ; register double ř = *řₚ; for (;;) { register double Π = a*ř; if ((Π⁻ < Π) && (Π < Π⁺)) { break; } else { ř *= (2.0 - Π); } } *řₚ = ř; } That is, we load a and ř once, at the ...