RE: pure and const functions

RE: pure and const functions

[Chris Lattner]

> 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.

While this is true in a practical sense, given infinite resources, this is
certainly not the case.  Assuming you had a whole lot of stack space and
bunch of time, the negative values for 'n' would wrap around to positive
values.  Eventually it would get to 1 and terminate.

As this is the case, for this example...

int double_or_nothing (int n) {
  fib(n);
  return 2*n;
}

... it should be optimizable to:

int double_or_nothing (int n) {
  return 2*n;
}

...because on an ideal, theoretical, machine, they results are exactly the
same.

IOW: we don't try to predict stack overflow in other cases, so why should
     we have to worry about that possibility here?

There may be other cases where functions are "partial", can you give
another example?

-Chris

http://www.nondot.org/~sabre/os/
http://www.nondot.org/~sabre/Projects/

Re: pure and const functions

[Kris Warkentin]

----- Original Message -----
From: "Chris Lattner" <sabre@nondot.org>
To: <gcc@gcc.gnu.org>
Sent: Friday, April 26, 2002 12:50 PM
Subject: RE: pure and const functions


>
> > 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.
>
> While this is true in a practical sense, given infinite resources, this is
> certainly not the case.  Assuming you had a whole lot of stack space and
> bunch of time, the negative values for 'n' would wrap around to positive
> values.  Eventually it would get to 1 and terminate.
>
> As this is the case, for this example...
>
> int double_or_nothing (int n) {
>   fib(n);
>   return 2*n;
> }
>
> ... it should be optimizable to:
>
> int double_or_nothing (int n) {
>   return 2*n;
> }
>
> ...because on an ideal, theoretical, machine, they results are exactly the
> same.
>
> IOW: we don't try to predict stack overflow in other cases, so why should
>      we have to worry about that possibility here?
>
> There may be other cases where functions are "partial", can you give
> another example?

One that calls a longjmp() or does an exec()?

>
> -Chris
>
> http://www.nondot.org/~sabre/os/
> http://www.nondot.org/~sabre/Projects/
>
>

Re: pure and const functions

[Chris Lattner]

> One that calls a longjmp() or does an exec()?

But those presumably would not be pure or const, would they?

-Chris

http://www.nondot.org/~sabre/os/
http://www.nondot.org/~sabre/Projects/

Re: pure and const functions

[Magnus Fromreide]

On Fri, 26 Apr 2002, Chris Lattner wrote:

> But those presumably would not be pure or const, would they?

Possibly, but given the definitions in the original post fprintf is pure
and it is also partial since you can't foresee what odd devices there
might be to write to.

Re: pure and const functions

[Chris Lattner]

On Fri, 26 Apr 2002, Magnus Fromreide wrote:

> On Fri, 26 Apr 2002, Chris Lattner wrote:
> > But those presumably would not be pure or const, would they?
>
> Possibly, but given the definitions in the original post fprintf is pure
> and it is also partial since you can't foresee what odd devices there
> might be to write to.

fprintf isn't pure though, it modifies global buffers, calls syscalls, and
otherwise has a lot of side effects...

I wouldn't want:

fprintf(stdout, "hello world\n");

to be eliminated because I don't use the return value of fprintf.  :)

-Chris

http://www.nondot.org/~sabre/os/
http://www.nondot.org/~sabre/Projects/

Re: pure and const functions

[Magnus Fromreide]

On Fri, 26 Apr 2002, Chris Lattner wrote:

> fprintf isn't pure though, it modifies global buffers, calls syscalls, and
> otherwise has a lot of side effects...

The original definition of pure is

>> 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.

That is, his explanation of pure leaves some leeway to utilize odd things.
Another classic pure function is the intel outb function.
I think that you wouldn't be allowed to remove pure functions no matter
what since they are allowed to affect global state, they just aren't
allowed to be affected by any part of the global state.

Bugger, even operator / fits, and that one is const and partial.

> I wouldn't want:
>
> fprintf(stdout, "hello world\n");
>
> to be eliminated because I don't use the return value of fprintf.  :)

I have to agree but still states that you aren't allowed to do that since
the used definition of pure is to weak.

Re: pure and const functions

[Chris Lattner]

> > to be eliminated because I don't use the return value of fprintf.  :)
>
> I have to agree but still states that you aren't allowed to do that since
> the used definition of pure is to weak.

Then the definition has to be fixed.  :)

The whole point of this discussion is to enable transformations like:

foo()+foo() -> 2*foo() and

fib(10000) -> /* noop */

right?  In this case, _no_ global state may be access or updated, whether
it be a side effect causing syscall or an update of a buffer.

-Chris

http://www.nondot.org/~sabre/os/
http://www.nondot.org/~sabre/Projects/

Re: pure and const functions

[Magnus Fromreide]

On Fri, 26 Apr 2002, Chris Lattner wrote:

> Then the definition has to be fixed.  :)

*nod*

> The whole point of this discussion is to enable transformations like:
>
> foo()+foo() -> 2*foo() and
>
> fib(10000) -> /* noop */
>
> right?  In this case, _no_ global state may be access or updated, whether
> it be a side effect causing syscall or an update of a buffer.

This is the point of the "const" modifier used in the original post.

Here I am speaking in the context of the original post (I agree that the
use of "pure function" is bewildering in this thread)

pure functions may change global state and may depend of their arguments.
const functions may depend of their aguments only.

What I am after is that we use the definitions in the gcc manual

> `pure'
>      Many functions have no effects except the return value and their
>      return value depends only on the parameters and/or global
>      variables.  Such a function can be subject to common subexpression
>      elimination and loop optimization just as an arithmetic operator
>      would be.  These functions should be declared with the attribute
>      `pure'.

and

> `const'
>      Many functions do not examine any values except their arguments,
>      and have no effects except the return value.  Basically this is
>      just slightly more strict class than the `pure' attribute above,
>      since function is not allowed to read global memory.
>
>      Note that a function that has pointer arguments and examines the
>      data pointed to must _not_ be declared `const'.  Likewise, a
>      function that calls a non-`const' function usually must not be
>      `const'.  It does not make sense for a `const' function to return
>      `void'.

rather than the botched ones specified in the original post.

/Violently agreeing with most of the people around here.

Re: pure and const functions

[Russ Allbery]

Magnus Fromreide <magfr@lysator.liu.se> writes:
> On Fri, 26 Apr 2002, Chris Lattner wrote:

>> fprintf isn't pure though, it modifies global buffers, calls syscalls, and
>> otherwise has a lot of side effects...

> The original definition of pure is

>>> 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.

> That is, his explanation of pure leaves some leeway to utilize odd things.

fprintf reads and modifies the FILE struct pointed to by its first
argument.

> I think that you wouldn't be allowed to remove pure functions no matter
> what since they are allowed to affect global state, they just aren't
> allowed to be affected by any part of the global state.

That's my understanding too.  Pure functions with that definition could be
relocated but not removed entirely; const functions could be removed
entirely if their return values aren't used.

-- 
Russ Allbery (rra@stanford.edu)             <http://www.eyrie.org/~eagle/>

Re: pure and const functions

[Kris Warkentin]

----- Original Message -----
From: "Chris Lattner" <sabre@nondot.org>
To: "Kris Warkentin" <kewarken@qnx.com>
Cc: <gcc@gcc.gnu.org>
Sent: Friday, April 26, 2002 1:22 PM
Subject: Re: pure and const functions


> > One that calls a longjmp() or does an exec()?
>
> But those presumably would not be pure or const, would they?

What if the longjmp or exec were conditional on something?  In fact, some
things are even conditional on external things like the status of a register
on a card or something which could be bound to a volatile variable.

Kris
>
> -Chris
>
> http://www.nondot.org/~sabre/os/
> http://www.nondot.org/~sabre/Projects/
>
>

Re: pure and const functions

[Chris Lattner]

On Fri, 26 Apr 2002, Kris Warkentin wrote:

> > But those presumably would not be pure or const, would they?
>
> What if the longjmp or exec were conditional on something?  In fact, some
> things are even conditional on external things like the status of a register
> on a card or something which could be bound to a volatile variable.

Again, those wouldn't be pure.  My understanding of pure functions is that
they should not have side effects, and should have output that only
depends on the input parameters.  Given this understanding (which may be
faulty), anything that uses external inputs would not be pure...

Transforming foo()+foo()  into 2*foo() does not work if foo is defined as:

int foo() {
  if (card_status_ok) return 1;
  return 0;
}

-Chris

http://www.nondot.org/~sabre/os/
http://www.nondot.org/~sabre/Projects/

Re: pure and const functions

[Tim Hollebeek]

On Fri, Apr 26, 2002 at 11:50:07AM -0500, Chris Lattner wrote:
> 
> > 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.
> 
> While this is true in a practical sense, given infinite resources, this is
> certainly not the case.  Assuming you had a whole lot of stack space and
> bunch of time, the negative values for 'n' would wrap around to positive
> values.

Actually, it's signed, so we get undefined behavior instead.  This
*really* muddies the waters, since the compiler need only preserve the
behavior of programs that don't invoke undefined behavior.

> There may be other cases where functions are "partial", can you give
> another example?

There are similar obvious trivial examples:

int hang_unless_positive(int n) /* a const function */ { 
    if (n <= 0) {
        while (1) {
        }
    }

    return n;
}

void do_nothing(int n) {
   hang_unless_positive(n) + hang_unless_positive(-n);
   launch_preemptive_nuclear_strike_on_arkansas();
}

Re: pure and const functions

[Chris Lattner]

> > There may be other cases where functions are "partial", can you give
> > another example?
>
> There are similar obvious trivial examples:
> int hang_unless_positive(int n) /* a const function */ {
>     if (n <= 0) while (1) ;
>     return n;
> }

Sure, but are there any good examples of a function that would be _useful_
to be marked as pure or const, but which might not return?

I know that it's certainly possible to come up with straw man examples
that show these cases, but the question is whether or not it's worth the
implementation effort to add this.  The only way to get some approximation
of an answer to this is to get some sense for how often this comes up.

Currently the situation is that if you have one of these functions, you
cannot mark it pure, is that correct?

-Chris

http://www.nondot.org/~sabre/os/
http://www.nondot.org/~sabre/Projects/

Re: pure and const functions

[Tony Finch]

Chris Lattner <sabre@nondot.org> wrote:
>
>Sure, but are there any good examples of a function that would be _useful_
>to be marked as pure or const, but which might not return?

	int
	counterrors(int count)
	{
		count++;
		if(count > MAXERRORS)
			exit(1);
		return(count);
	}

Tony.
-- 
f.a.n.finch <dot@dotat.at> http://dotat.at/
FAIR ISLE FAEROES: MAINLY NORTHWESTERLY 7 TO SEVERE GALE 9, OCCASIONALLY STORM
10 IN FAIR ISLE. RAIN THEN SQUALLY WINTRY SHOWERS. MODERATE OR GOOD.

Re: pure and const functions

[Zack Weinberg]

On Fri, Apr 26, 2002 at 12:27:07PM -0500, Chris Lattner wrote:
> 
> Sure, but are there any good examples of a function that would be _useful_
> to be marked as pure or const, but which might not return?

The examples being kicked around earlier were of routines that were
pure except for assertions to enforce data structure integrity.  We
would like the compiler to optimize on the basis that the data
structure is correct and therefore the pure function will always
return.

zw

Re: pure and const functions

[Chris Lattner]

On Fri, 26 Apr 2002, Zack Weinberg wrote:
> > Sure, but are there any good examples of a function that would be _useful_
> > to be marked as pure or const, but which might not return?
>
> The examples being kicked around earlier were of routines that were
> pure except for assertions to enforce data structure integrity.  We
> would like the compiler to optimize on the basis that the data
> structure is correct and therefore the pure function will always
> return.

Ok, now I'm more confused than before.  :)  When optimizing, do you
consider it ok for the compiler to drop the assertions in a pure function,
if it decides to elide the call to the function?

If not, is it really pure?

-Chris

http://www.nondot.org/~sabre/os/
http://www.nondot.org/~sabre/Projects/

Re: pure and const functions

[Zack Weinberg]

On Fri, Apr 26, 2002 at 12:55:51PM -0500, Chris Lattner wrote:
> On Fri, 26 Apr 2002, Zack Weinberg wrote:
> > > Sure, but are there any good examples of a function that would be _useful_
> > > to be marked as pure or const, but which might not return?
> >
> > The examples being kicked around earlier were of routines that were
> > pure except for assertions to enforce data structure integrity.  We
> > would like the compiler to optimize on the basis that the data
> > structure is correct and therefore the pure function will always
> > return.
> 
> Ok, now I'm more confused than before.  :)  When optimizing, do you
> consider it ok for the compiler to drop the assertions in a pure function,
> if it decides to elide the call to the function?

Yes.  Generally this comes up in code of the form

  if (pure_function_which_contains_assertions (structure)
      && expression_which_would_be_provably_false_if_it_had_been_written_first)
    {
      huge block of code which does something with structure
    }

where 'predicate' contains some assertions.  We want GCC to realize
that the entire block is dead code.  Losing the assertions is a minor
price to pay.

zw

RE: pure and const functions

[Mark Mitchell]

--On Friday, April 26, 2002 11:50:07 AM -0500 Chris Lattner 
<sabre@nondot.org> wrote:

>
>> 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.
>
> While this is true in a practical sense, given infinite resources, this is
> certainly not the case.  Assuming you had a whole lot of stack space and
> bunch of time, the negative values for 'n' would wrap around to positive
> values.  Eventually it would get to 1 and terminate.

Actually, C does not guarantee that negative values wrap around to
positive values.

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com

Re: pure and const functions

[John Wehle]

> Does the latest GCC really already try to prove functions as pure?

Current mainline.

> int square (int n) {
>   int i,j,result;
> 
>   result = 0;
>   for (i=0; i<n; i++)
>     for (j=0; j<n; j++)
>       result++;
>   return result;
> }

Loops are not currently handled.  There is a pending
patch to handle loops with known iteration counts:

  http://gcc.gnu.org/ml/gcc-patches/2002-03/msg01612.html

-- John
-------------------------------------------------------------------------
|   Feith Systems  |   Voice: 1-215-646-8000  |  Email: john@feith.com  |
|    John Wehle    |     Fax: 1-215-540-5495  |                         |
-------------------------------------------------------------------------

Re: pure and const functions

[Robert Dewar]

> I don't really agree with this.  If the compiler can determine that it's
> pure, the programmer shouldn't have to provide the annotation.  Instead
> (at least for the C/C++ frontends), I propose that we trust the programmer
> to not do something dumb (scary I know...).  These languages are built
> around the notion that the programmer knows what they are doing, I don't
> see how it would be any different here...

In order for the programmer to "know what they are doing", you have to do
one of two things:

1. Define what pure means semantically

or

2. Define what the functional effect of declarting something pure is

I actually think you *do* agree with me. What I said was that it was in
practice impractical for the compiler to check that you are doing the
right thing when you declare a function pure (though obvious problems
might be detectable and cause appropriate warnings).

As an example of a fuction that is unlikely to obey any set of semantic
rules but in practice can be treated as pure, consider a sqrt function
which is instrumented to count the number of times it is called. This
is obviously not pure in the semantic sense, but operationally it may
make perfect sense to treat it as pure.

Re: pure and const functions

[Chris Lattner]

> I actually think you *do* agree with me. What I said was that it was in

I now agree that I agree with you.  :)

I think that:

> 2. Define what the functional effect of declarting something pure is

... is easiest, and should probably be made especially clear in the
documentation, because it is what impacts the user.  The problem is that
it has to be updated as new transformations are added...

> 1. Define what pure means semantically

This needs to be well understood by GCC developers that are making the new
transformations... but it would certainly be nice to have.  Unfortunately
it's kind of hard to pin down, your sqrt example is a good example of
why. :)

-Chris

http://www.nondot.org/~sabre/os/
http://www.nondot.org/~sabre/Projects/

Re: pure and const functions

[Robert Dewar]

> 
> 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.
> 
> 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).

Given that a programmer can mark things as pure, you need to decide

1. If the compiler can check that this designation is correct. The answer
is pretty clearly no.

2. What exactly is the criterion for "correct" designation of Pure (in
Ada by the way this is the Pure_Function pragma).

Yes, the compiler can try to prove some functions pure, but it will always
end up being too conservative, which is fine.

Re: pure and const functions

[Chris Lattner]

On Mon, 29 Apr 2002, Robert Dewar wrote:

> Given that a programmer can mark things as pure, you need to decide
>
> 1. If the compiler can check that this designation is correct. The answer
> is pretty clearly no.

I don't really agree with this.  If the compiler can determine that it's
pure, the programmer shouldn't have to provide the annotation.  Instead
(at least for the C/C++ frontends), I propose that we trust the programmer
to not do something dumb (scary I know...).  These languages are built
around the notion that the programmer knows what they are doing, I don't
see how it would be any different here...

-Chris

http://www.nondot.org/~sabre/os/
http://www.nondot.org/~sabre/Projects/

Re: pure and const functions

[Chris Lattner]

>>   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.

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.

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/

Re: pure and const functions

[Daniel Berlin]

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/
> 

Re: pure and const functions

[Chris Lattner]

On Mon, 29 Apr 2002, Daniel Berlin wrote:

> > 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.

While I'm sure that there is room for improvement in our analysis of pure
functions, the point was originally that there will always be cases that
are not analyzable (for example, the sqrt case mentioned by Robert, which
is NOT pure, but the programmer can decide to treat it as such).  The fact
that there are unanalyzable cases does not automatically make them not
"pure", they just aren't analyzable.

That said, it will be interesting to see how much benefit your analysis
provides to common programs... how many pure functions do you typically
find?  Are the GCC transformations able to take advantage of the extra
information to increase performance?

-Chris

http://www.nondot.org/~sabre/os/
http://www.nondot.org/~sabre/Projects/

Re: pure and const functions

[Mark Dettinger]

Does the latest GCC really already try to prove functions as pure?
If yes, can anyone point me to the code that does that, please?
And why does it fail to recognize this function as pure:

int square (int n) {
  int i,j,result;

  result = 0;
  for (i=0; i<n; i++)
    for (j=0; j<n; j++)
      result++;
  return result;
}

which clearly is a pure (and even a const) function, right?


-Mark Dettinger


__________________________________________________
Do You Yahoo!?
Yahoo! Health - your guide to health and wellness
http://health.yahoo.com

Re: pure and const functions

[Robert Dewar]

> > `pure'
> >      Many functions have no effects except the return value and their
> >      return value depends only on the parameters and/or global
> >      variables. 


This is a bit of a confused definition

  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.

Conditions b) and c) are quite different from an optimization point of view.

In GNAT we define a pure function as one for which it is permissible to
optimize away multiple calls with provably identical parameter calls.

Re: pure and const functions

[Mark Dettinger]

>   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.

> Conditions b) and c) are quite different from an optimization point of view.
> In GNAT we define a pure function as one for which it is permissible to
> optimize away multiple calls with provably identical parameter calls.

If I understood it correctly, that would be a "const" function in gcc.
Sometimes pure is enough to optimize, sometimes you need const.

foo()+foo() ---> 2*foo()   is possible, if foo() is pure

a=foo();         a=foo();
n++;        ---> n++;      is only possible, if foo() is const,
b=foo();         b=a;      since foo() might depend on the global var n
 
                          
-Mark Dettinger


__________________________________________________
Do You Yahoo!?
Yahoo! Health - your guide to health and wellness
http://health.yahoo.com

Re: pure and const functions

[Mark Dettinger]

Sorry for causing unneccessary confusion - the definition of "pure" 
in my original posting was wrong. The definition in the gcc manual

> `pure'
>      Many functions have no effects except the return value and their
>      return value depends only on the parameters and/or global
>      variables. 

is good. The whole point, as Chris Lattner pointed out, is to make
optimizations like foo()+foo() ---> 2*foo() possible. (Currently,
GCC is not very good here.)

Such a common subexpression elimination does not require foo() 
to terminate for all inputs and in all contexts. For this reason, 
I think that termination issues should be kept out of the definition 
of "pure". 
If we require a "pure" function to always terminate - as some people 
have advocated - we 

(1) get a stricter kind of "pure" that is better for dead code
    elimination, but worse for CSE elimination.

(2) make it much harder for the compiler to automatically recognize
    a "pure" function

It's still a good idea to add detection code that determines 
whether a function is total, i.e. always terminates.
We just should not MIX this with the definition of pure. 
Treating the issues separately yields better results.

foo is pure           --> foo()+foo() can be optimized to 2*foo()
foo is pure and total --> foo();      can be optimized to ;


-Mark Dettinger


__________________________________________________
Do You Yahoo!?
Yahoo! Health - your guide to health and wellness
http://health.yahoo.com

pure and const functions

[Mark Dettinger]

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/

Re: pure and const functions

[Joseph S. Myers]

On Fri, 26 Apr 2002, Mark Dettinger wrote:

> 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.

Pure functions are pure functions of *the whole state of the machine*
(including global memory).

http://gcc.gnu.org/ml/gcc-patches/1999-08/msg00588.html

-- 
Joseph S. Myers
jsm28@cam.ac.uk

Re: pure and const functions

[Jakub Jelinek]

On Fri, Apr 26, 2002 at 05:08:07AM -0700, Mark Dettinger wrote:
> 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.

This is totally different from current meaning of "pure" attribute.
Pure are functions which may read global memory, but may not write any
global memory nor have any other side effects.

	Jakub