From: Mark Dettinger <mdetting@yahoo.com>
To: gcc@gcc.gnu.org
Subject: pure and const functions
Date: Fri, 26 Apr 2002 05:16:00 -0000 [thread overview]
Message-ID: <20020426120807.1657.qmail@web13609.mail.yahoo.com> (raw)
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/
next reply other threads:[~2002-04-26 12:08 UTC|newest]
Thread overview: 33+ messages / expand[flat|nested] mbox.gz Atom feed top
2002-04-26 5:16 Mark Dettinger [this message]
2002-04-26 11:20 ` Joseph S. Myers
2002-04-26 12:59 ` Jakub Jelinek
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 ` Zack Weinberg
2002-04-26 11:01 ` Chris Lattner
2002-08-30 23:02 ` Zack Weinberg
2002-04-26 10:56 ` Tony Finch
2002-04-26 12:11 ` Mark Mitchell
2002-04-29 3:59 Mark Dettinger
2002-04-29 5:18 Robert Dewar
2002-04-29 5:44 ` Mark Dettinger
2002-04-29 8:30 Robert Dewar
2002-04-29 8:57 ` Chris Lattner
2002-04-29 8:30 Chris Lattner
2002-04-29 9:23 ` Daniel Berlin
2002-04-29 9:52 ` Chris Lattner
2002-04-29 9:58 ` Mark Dettinger
2002-04-29 9:29 Robert Dewar
2002-04-29 9:34 ` Chris Lattner
2002-04-29 17:25 John Wehle
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=20020426120807.1657.qmail@web13609.mail.yahoo.com \
--to=mdetting@yahoo.com \
--cc=gcc@gcc.gnu.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).