pure and const functions

[Mark Dettinger <mdetting at yahoo dot com>]

A month ago, there was a discussion whether a pure or const function
should be required to terminate for all inputs and in all contexts.
=> http://gcc.gnu.org/ml/gcc-patches/2002-03/msg01477.html

Since for some code optimizations the termination requirement is important, 
but for other optimizations it is irrelevant, I propose that we should
keep termination issues out of the definition of const and pure. Instead, 
I would rather add the concept of total and partial functions. 
So, I suggest to go with the following attribute definitions:

A function is "pure", if it only examines its arguments, i.e. does not
read global memory and does not take input from any device. In other 
words, if its behavior does not depend on the context.

A function is "const", if - in addition to being pure - it does not have a 
side effect besides returning a value, i.e. it does not modify global memory 
and does not write to a file, to the screen, or to any other device.

A function is "total", if it returns in all cases, i.e. for all inputs
and (for non-pure functions) in all contexts. 

A function is "partial", if it may or may not return. 

A function has the "noreturn" attribute, if it never returns.


If the new concepts "total" and "partial" sound unneccessary to you,
please consider this example:

int fib(int n) {
  if (n==0 || n==1) return n;
  return fib(n-1) + fib(n-2);
}

According to the definitions given above, this function is const, 
but not total, because it does not return for negative n.
This has different implications for different optimizations:

Dead Code Elimination:
----------------------

int double_or_nothing (int n) {
  fib(n);
  return 2*n;
}
  
Since fib is not total, the compiler cannot delete the call fib(n) here, 
although the return value is not used:
If we delete the call, then double_or_nothing always returns, 
while the unoptimized function does not return for negative n. 

Common Subexpression Elimination:
---------------------------------

int fib_cube (int n) {
  return fib(n) * fib(n) * fib(n);
}

Here it does not matter whether fib is total or not. If the first call
returns, the second and third call will return too, since fib is a const
function. So, the compiler can (and should!) optimize this to

int fib_cube (int n) {
  int cse = fib(n);
  return cse * cse * cse;
}

So DCE requires const + total, CSE only requires const here. This is
the reason why I wouldn't add the termination requirement to const,
but rather add a total attribute.

Attributes versus Automatic Detection
-------------------------------------

In my opinion, the compiler should definitely try to determine the
function attributes by code analysis. In many cases, it is possible
to determine automatically whether a function is pure, const or total.
In the fib function, for example, it's easy for the compiler to see 
that the function is const. We definitely need good automatic analyses.
Attributes provided by the programmer should be just for the cases 
that the compiler cannot solve alone.

Finally, here's how I think a good compiler should behave when conflicts 
between user-given attributes and automatically detected attributes occur:

1. If an attribute is present and is clearly wrong, an error should be thrown.
2. If an attribute is present and might be wrong, a warning should be given.
3. If an attribute is missing, but maybe should be there, a suggestion to add 
   the missing attribute should be made.
4. If an attribute is missing, but clearly should be there, the compiler
   should just add the attribute and continue and not bother the programmer.

1 and 4 should be always active. 2 and 3 should be optional.
 
What do you think?

-Mark Dettinger


__________________________________________________
Do You Yahoo!?
Yahoo! Games - play chess, backgammon, pool and more
http://games.yahoo.com/