Loop Dependence Analysis - Alias Detection

Alias Detection

Inside loops, the same variable can be accessed for both read and write, at the same or different location within each iteration. Not only that, but the same region in memory can be accessed via different variables. When the same region in memory can be accessed by more than one variable, you have an alias.

Some aliases are very simple to detect:

a = b; for (i = 0; i < MAX; ++i) a = b; a = 0;

It is obvious that b is an alias to a, thus this code is actually shifting the array to the left. But this is not always so obvious, for instance the standard C library function strcpy copies one string to another, but the caller could provide overlapped regions like this:

strcpy(x, x+1);

when the internal loop could be implemented as:

while(*src != 0) { *dst = *src; src++; dst++; }

The dependency of src and dst is not obvious from within the function, you have to analyse every caller to make sure there isn't any. In the case of a library function, there is no way to assure it won't happen, so the compiler has to assume one way or another. If the compiler assumes there is no alias, whenever the regions overlap, you get undefined behaviour. If it assumes there is, you always get non-optimized code for every case.

Some compilers accept special keywords to work out if it can assume no alias, such as restrict.