merlyn@ernie.Rosemount.COM (Brian Westley) (02/20/89)
It's starting to look like pure functions are like noalias; everyone
knows what it "means" until you look at it more closely.
Simple repeat calls should be optimizable:
y = sin(x) * sin(x) ;
z = 1.0 / sin(x++) ; /* remember to preserve calling side effect */
It should be possible (and legal) to optimize-out the call completely:
a = b ;
...
x = fudge + (sin(a) - sin(b))/100 ;
Now, should it be possible to fold pure functions with constant arguments?
x = sin(sqrt(2.0)) ; /* turns into simple assignment to a constant? */
This seems reasonable and desirable, but what about user defined functions?
What about pure functions that can only be evaluated at run time, such as a
function that returns the name of the machine the program is running on?
Can the compiler determine that one pure function can be evaluated completely
at compile-time, and another cannot? Or should only the former be considered
"pure"? What about functions that have a first-time-through flag that, e.g.,
precomputes a table of factorials? Does this destroy its purity?
Somewhat related, is this a legal optimization?
static int sqrs[10];
main()
{
int i;
for (i=0; i<10; i++)
sqrs[i] = i * i; /* no further assignments to sqrs[] */
...
static int sqrs[10] = { 0, 1, 4, 9, 16, 25, 36, 49, 64, 81 };
main()
{
int i;
...
-----
Merlyn LeRoygwyn@smoke.BRL.MIL (Doug Gwyn ) (02/21/89)
In article <7256@rosevax.Rosemount.COM> merlyn@ernie.rosemount.com writes: >Now, should it be possible to fold pure functions with constant arguments? > x = sin(sqrt(2.0)) ; /* turns into simple assignment to a constant? */ Sure. Why not? If these functions were implemented as compiler intrinsics, then in fact I would hope that the constant-folding optimization WOULD fold in the effects of such functions. The only possible glitch would be if the target environment had different arithmetic properties from the compilation environment, since the proposed standard requires that compile-time constant folding be performed with at least as much precision as would occur at run time. If accurate simulation of the target run-time arithmetic was too much bother, then I wouldn't really expect the compiler to perform this level of optimization. >This seems reasonable and desirable, but what about user defined functions? >What about pure functions that can only be evaluated at run time, such as a >function that returns the name of the machine the program is running on? >Can the compiler determine that one pure function can be evaluated completely >at compile-time, and another cannot? Or should only the former be considered >"pure"? What about functions that have a first-time-through flag that, e.g., >precomputes a table of factorials? Does this destroy its purity? It all depends on how intelligent the compiler is. If it is able to pre-run your program in effect, converting it to a series of printf() statements that produce the correct results, then more power to it. The general constraint on optimization is that it is not allowed to affect any input or output operations, which must occur in the sequence specified in the original source code with the same observable effects. ANSI C also requires that accesses to volatile-qualified data occur as specified for the virtual C machine. Because of the ability to compile modules separately, this constraint has far-reaching consequences for what is and is not allowed in the way of optimization. IF a compiler were able to determine all the modules to be linked into the application "up front", then it could in theory perform a much higher degree of optimization than is usually actually implemented. In general this will not be possible. It is only the fact that in a hosted environment the C library routines are standardized that permits the compiler to always know their exact properties. >Somewhat related, is this a legal optimization? [Compiler performs specified initialization code in advance.] Sure. I doubt that any existing production C compilers are that smart.
merlyn@ernie.Rosemount.COM (Brian Westley) (02/21/89)
Legend: >>Me >Doug Gwyn >>Now, should it be possible to fold pure functions with constant arguments? >> x = sin(sqrt(2.0)) ; /* turns into simple assignment to a constant? */ > >Sure. Why not?... But then I asked - >>What about pure functions that can only be evaluated at run time, such as a >>function that returns the name of the machine the program is running on? This was my main point: there are functions which return the same results for the same arguments, without side-effects, which can't be folded at compile time if given constant arguments. If such functions are not considered pure, they won't be optimized. If such functions are considered pure, not all pure functions will be foldable into constants. Either you have to tell the compiler which is which, or the compiler has to figure it out (not bloody likely). ----- Merlyn LeRoy #pragma ivory /* 99 44/100% pure */