public inbox for gcc@gcc.gnu.org
 help / color / mirror / Atom feed
From: Daniel Berlin <dberlin@dberlin.org>
To: Chris Lattner <sabre@nondot.org>
Cc: gcc@gcc.gnu.org, <mdetting@yahoo.com>, <dewar@gnat.com>
Subject: Re: pure and const functions
Date: Mon, 29 Apr 2002 09:23:00 -0000	[thread overview]
Message-ID: <Pine.LNX.4.44.0204291202110.6536-100000@dberlin.org> (raw)
In-Reply-To: <Pine.LNX.4.30.0204291011440.26161-100000@nondot.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/
> 

  reply	other threads:[~2002-04-29 16:22 UTC|newest]

Thread overview: 33+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2002-04-29  8:30 Chris Lattner
2002-04-29  9:23 ` Daniel Berlin [this message]
2002-04-29  9:52   ` Chris Lattner
2002-04-29  9:58   ` Mark Dettinger
  -- strict thread matches above, loose matches on Subject: below --
2002-04-29 17:25 John Wehle
2002-04-29  9:29 Robert Dewar
2002-04-29  9:34 ` Chris Lattner
2002-04-29  8:30 Robert Dewar
2002-04-29  8:57 ` Chris Lattner
2002-04-29  5:18 Robert Dewar
2002-04-29  5:44 ` Mark Dettinger
2002-04-29  3:59 Mark Dettinger
2002-04-26 10:17 Chris Lattner
2002-04-26 10:21 ` Kris Warkentin
2002-04-26 10:30   ` Chris Lattner
2002-04-26 10:34     ` Magnus Fromreide
2002-04-26 10:35       ` Chris Lattner
2002-04-26 10:59         ` Magnus Fromreide
2002-04-26 11:03           ` Chris Lattner
2002-04-26 11:27             ` Magnus Fromreide
2002-04-26 12:49           ` Russ Allbery
2002-04-26 10:36     ` Kris Warkentin
2002-04-26 10:46       ` Chris Lattner
2002-04-26 10:26 ` Tim Hollebeek
2002-04-26 10:30   ` Chris Lattner
2002-04-26 10:56     ` Tony Finch
2002-04-26 10:56     ` Zack Weinberg
2002-04-26 11:01       ` Chris Lattner
2002-08-30 23:02         ` Zack Weinberg
2002-04-26 12:11 ` Mark Mitchell
2002-04-26  5:16 Mark Dettinger
2002-04-26 11:20 ` Joseph S. Myers
2002-04-26 12:59 ` Jakub Jelinek

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=Pine.LNX.4.44.0204291202110.6536-100000@dberlin.org \
    --to=dberlin@dberlin.org \
    --cc=dewar@gnat.com \
    --cc=gcc@gcc.gnu.org \
    --cc=mdetting@yahoo.com \
    --cc=sabre@nondot.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).