Grok Aliasing

Given two pointers or other references to memory, the compiler in many languages has no way to decide if changing any of the memory associated with one pointer affects the contents of some other pointer.

 void fred(char **S,char *d)
 {
   if (**S == 0)  { *d++ = 0; }
   do something else

if (**S == 0) { ..... } }

In the second 'if' of the previous code, the compiler MUST get the value from *S a second time because it cannot know whether or not the assignment to *d changed the contents of **S. It would be very rude, but it may even have changed the contents of the pointer *S!

Exceptions

In the above example, there is No exception, but if one of the pointers was a pointer into a local variable on the stack, then the compiler can often be much more aggressive because it knows if any code has taken the address of that object lately and doing the StructHack in local variable space is definitely a mortal sin that is beyond redemption.

It is the existence of this exception that sometimes means the fastest HighLevelLanguage way to code a routine is to copy construct an object into a local variable! Given a big enough loop inside the routine that repeatedly accesses the members of the object this can speed up code despite the overhead of copying the object.

An alternative method that is currently being explored in compiler design, is to use languages with clearer semantics than CeeLanguage. These languages are more amenable to AliasAnalysis and the compiler can then make many more of these optimizations automatically.

Doesn't the latest draft of C9x (now a bit late ;-) include the restrict keyword, which functions as a poor man's AliasAnalysis?

Indeed it does. It does this in order that C9x might better compete with FortranLanguage, which has prohibitions on certain forms of aliasing.

The impossibility of writing code with aliases in a PureFunctionalLanguage also allows compilers for them to do agressive optimisations of this sort, too.


Whoever revamped this did good: original author. A very good job.
CategoryOptimization

EditText of this page (last edited February 28, 2009) or FindPage with title or text search