Re: pure and const functions

[Daniel Berlin <dberlin at dberlin dot org>]

On Mon, 29 Apr 2002, Chris Lattner wrote:

> 
> >>   a) having no effects except the return value
> >>   b) return value depends only on the parameters
> >>   c) return value depends on global variables
> >>
> >> Condition a) is too strong for removal of duplicate calls, since it
> >> eliminates considering memo functions as pure.
> 
> > Yes, but I think that's okay. There are cases where duplicate calls
> > to a non-pure memoizing function could be removed too, but how should
> > the compiler determine which side-effects can be ignored?
> > All we say is that if condition a) is fulfilled, we are on the safe
> > side.
> 
> There are two different issues going on here confusing things:
> 
> 1. The defined semantics
> 2. What we actually do
> 
> For #1, Robert is correct...
> >   a) having no effects except the return value
> 
> Is too strong of a statement... the problem is that it's really hard to
> make an accurate summary of what things really are.  Perhaps "Always
> returns the same value for a particular set of input parameters" coupled
> with "makes no changes to global state that would break the program if
> they didn't happen" is close enough.  Effectively we just need to get
> across the idea that a pure function _can_ be eliminated, and doing so
> should not affect the semantics of the program.

Correct.  

In fact, you could reformulate robert's a, b, and c as

a. SIDE_EFFECT_FREE (func) = TRUE
b. DMOD (func) == empty && GMOD(func) == empty && GREF (func) == empty.
(it doesn't modify global variables directly or indirectly, it doesn't 
directly modify variables in our current function as a side-effect of 
the call, and it doesn't reference any globals)
c. DMOD (func) == empty && GMOD(func) == empty && REF(func) == empty.
("", and it doesn't reference any locals or passed in parameters. We'll 
pretend here that REF contains the formals passed in. That's usually put 
in GREF instead, though not always..)


THe trouble is that people try to formulate SIDE_EFFECT_FREE in terms of 
DMOD, GMOD and REF, or get confused into thinking that if DMOD(func) == 
empty and GMOD (func) == empty and GREF(func) == empty and REF(func) == 
empty, then SIDE_EFFECT_FREE(func) = TRUE.

Which is wrong.

It's

(MOD (func) == empty) == SIDE_EFFECT_FREE (true)

where MOD is the set of all variables that may be modified as a side 
effect. This includes may-alias information, while DMOD/GMOD alone do not.


> 
> This seems nice and simple, but #2 confuses things.  As I understand it,
> GCC automatically trys to prove functions pure.  Obviously it will not be
> able to figure out the structure of a memoizing function in general, so it
> would punt on these functions, thus not automatically marking it pure.

This is not necessarily true.
Some of the algorithms i've implemented or am experimenting with to 
compute MOD/REF and GMOD/GREF seem to do just fine on most memoizing 
functions.
Assuming you don't play mean pointer tricks.
I'm just trying to find the right tradeoff in speed and memory usage.
Disk space i'm not concerned with (the info is stored in a database using 
Samba's TDB, and can, in some cases, get large. But i'm ignoring this 
issue for now).

> The programmer, however, can manually add the pure attribute, so the
> actual _notion_ of being pure is still intact, even if the actual
> implementation isn't "smart enough" (and there isn't really any reasonable
> way to make it so).
> 
> -Chris
> 
> http://www.nondot.org/~sabre/os/
> http://www.nondot.org/~sabre/Projects/
>