Understanding Type-Based Alias Analysis in C and C++

What are Type Systems?

Type system in statically typed language empowers compilers to identify and reject invalid programs during the type checking phase. Type information associated with different elements of the program (e.g. functions, variables) helps the compiler to detect the state of the program without actually executing the program. While programming language types are frequently employed to detect specific errors during compilation, what is interesting and important is that they serve other purposes as well.

Let’s Talk about Type-based Alias Analysis

Type-based alias analysis is a technique that determines whether two or more pointers or references in a program can potentially point to the same memory address (alias each other, in other words). This analysis mainly relies on the concept of compatible types.

But what exactly are compatible types?

So, aliasing typically occurs between compatible data types. To clarify, data types are deemed compatible when they differ only in attributes like being signed, unsigned, const, or volatile. For instance, both "char" and "unsigned char" are compatible with any other type.

Let’s look at a simple example to understand better:

Assuming the function call is modifyValues(&n, (short*)&n) here, n might be an integer type.

What would be the resulting value of n?

It depends on the optimization level. Let’s look at the assembly in the case of no optimization level (O0) and its being compiled with clang.

This is pretty much standard, similar to what we wrote in high-level code - basically a one-to-one mapping. Looking at the assembly, it is clear that there is aliasing, a and b pointing to the exact same location. Hence, the final value for n would be 8 in this case.

Now, let’s compile the program using an optimization level -O2 ,

Take a look at this big assembly:

In this case, the final value of n would be 47.

Though, is that program right in this case? Obviously, it is not. There is undefined behavior, which is visible through how different optimization levels have different results.

Why is that?

In accordance with the C and C++ standards, when you try to access an object of one type (e.g., int) using an lvalue expression of a different type (e.g., short in a function argument), and these types are not considered compatible (except for specific exceptions outlined in the standards), it leads to undefined behavior. This means that the program's behavior cannot be predicted or relied upon, and it may produce unexpected results.

Personally speaking, I really like when undefined behavior teaches much more about programming than the defined behavior. :)

TBAA in Action:

Consider the following example:

In this case, the compiler and TBAA ensure that the types are not compatible and memory lookup for *n can be optimized by performing it just once. The resulting value can be stored in a register, which is then accessed in each iteration of the loop. This optimization helps reduce memory access overhead and can lead to improved performance.

Now, consider this example:

In the provided example, the types of v and c are compatible, which leads the compiler to assume they may alias, meaning they could refer to the same memory location. Consequently, the compiler takes measures to ensure that fetching the value of *c within the loop will indeed be performed in each iteration. This behavior is implemented to guarantee that the value pointed to by c is fetched afresh in every iteration of the loop. However, it's important to note that this meticulous handling, while beneficial for correctness, can potentially impact performance.

For More Details Let's Look at their Assembly

First Version (Non-compatible types):

Second Version (Compatible types):

In the first version (Foo(float*, int*)), the loop counter n is passed as a pointer to an integer (int*). The code loads this integer value (*n) into a register (rax) before entering the loop, and then uses this register for loop control.

This means that the loop counter is loaded from memory once at the beginning of the loop, and the register value is used throughout the loop iterations.

In the second version in each iteration of the loop, *c is loaded into xmm0.

This behavior ensures that the value pointed to by *c is consistent throughout the loop iterations.

Have you noticed how type-based alias analysis benefits compilers to take optimizations action?

But the question remains:
What is an explicit fix for this, or hint to the compiler that there is no chance of aliasing even in the case of compatible types?

In C, the restrict keyword comes to the rescue when you want to explicitly inform the compiler that there is no chance of aliasing between pointers.

Consider this example:

In practice, you may need to declare both pointers as restrict if you can guarantee that they don't alias each other.

Let's Look at the Assembly for the Above Code:

See how it impacted the performance:

The movss instruction loads the constant 1.0f into xmm0, and then addss adds the value pointed to by c to xmm0. Importantly, c is loaded into xmm0 only once outside the loop and re-used in the loop. Using the restrict keyword, you provide the compiler with the assurance that the memory regions accessed through the pointers v and c do not overlap. The compiler can then optimize the code more aggressively for performance.

However, a word of caution: you must be very careful when using restrict, as the compiler won't warn you about its incorrect use.

Interestingly, the restrict keyword is not a part of C++. Why is that?

The history behind this decision is quite intriguing. When reviewing C99 features for inclusion in C++, there was consideration of adding restrict. However, no paper proposal was made at the time. Hence, it didn't make its way into C++.

restrict was originally designed for fine-grain aliasing in C but may not be well-suited for the type-based aliasing that is more common in C++. In C++, pointers are less prevalent in class abstractions and restrict may not align well with the C++ language design.

In summary, the restrict keyword in C and type-based alias analysis are tools that help compilers generate efficient and optimized code while maintaining program correctness and adherence to language standards.

Thank you for reading!