Re: a question about const and pure functions.

[Roger Sayle <roger at eyesopen dot com>]

On Thu, 11 Nov 2004, Kenneth Zadeck wrote:
> The minor bugs and missed opportunities are associated with the code
> that controls the pure can call pure and const and const can call const
> put const cannot call pure.  The code is messed up in both ways.  Some
> const calling pures are allowed (if the pure has no args) and some pure
> calls consts are rejected.  These could be fixed in the existing code,
> but there are other issues with performing this analysis at the rtl level.


A "const" call has no side-effects and its results depend purely on the
values of its arguments.  This closely follows the mathematical notion
of a "function".  A "pure" call has no side-effects, but in addition to
it's arguments may depend upon the memory/global variables of the system.

Examples of relevant optimizations include (i) if the result of a const
or a pure function is ignored, then the call to that function may be
completely eliminated, (ii) two calls to a const function with identical
arguments are guaranteed to produce the same result, and the second
invokation may be CSE'd, (iii) two calls to a pure function with identical
arguments are only guaranteed to produce the same results if there are
no write's to memory (that are visible to the function) between the two
calls.  In this case, the second invocation may be CSE'd.  (iv) Writes
to global variables need no be committed (i.e. moved after) calls to
const functions.


Now consider the example:

int var;

int foo()
{
  return var;
}

int bar()
{
  return foo();
}


In this example, foo is "pure", has no side-effects but reads from
global memory.   Although bar only calls "foo" with no arguments, it
still can not be classified as "const".

But contrary to your assertion bar is not "const" as it calls "foo".  The
semantics a "necessary" but no sufficient requirement of a "const"
function is that it only calls "const" functions. Likewise, a requirement
of a "pure" functions is that it only calls "pure" or "const" functions.

The optimization that might be confusing this is that if the result of
the call to foo() in "bar" is ignored, then it effectively doesn't exist.
i.e. in

int bar()
{
  foo();
  return 0;
}

bar() is "const".



> The extensions that I want to add are:
>
> 1) allow const to access memory if the memory is a constant, i.e. if you
> have a readonly static with a decl initial that satisfies
> is_gimple_min_invariant (), such a reference need not be treated
> differently than referencing a "5".

This is a valid and reasonable improvement.


> 4) eventually to allow some loops (if they can be proven to be finite)
> rather than just looking for back edges in the cfg. We have this
> analysis in the compiler, we should be allowed to use the info here.

This is also good, but seems to clash with your hopes of moving
pure/const analysis earlier.


> 3) allow for recursive and mutually recursive pure and const functions.

With the caveat that there can't be mutual recursion between a pure and
a const function [two pure functions may be mutually recursive, and two
const functions may be mutually recursive, but a const function can't
invoke a pure function.  Obviously both pure and const functions can be
recursive.]


> The hope here is that with the exception of setting errno, that most
> small table driven mathematical functions would fall into one of these
> categories.

This is only an issue when not using -ffast-math, which is a reasonable
requirement for any kind of performance benchmarking.  I would suggest
that we could add a "clobber_errno" attribute to the builtin math
functions to provide the compiler a hint that they are const except for
clobbers of errno.  Unfortunately, very few of GCC's backends actually
define GEN_ERRNO_RTX, so identify which memory location is actually
clobbered in the presence of macros in errno.h and thread local storage
is almost impossible.

Additionally, GCC models the "current floating point rounding" direction
by modelling some math functions, such as rint, as pure instead of const.
Hence, upon calling an unknown side-effecting function, GCC can no longer
assume that calls to rint with identical arguments produces the same
result.



I hope this helps, but perhaps I misunderstand your thoughts on const
functions calling pure functions.

Roger
--