Re: Detailed algorithms on inline optimization

Ray <bear@sonic.net>
Thu, 21 Jan 2010 10:18:33 -0800

          From comp.compilers

Related articles
[3 earlier articles]
Re: Detailed algorithms on inline optimization bobduff@shell01.TheWorld.com (Robert A Duff) (2010-01-19)
Re: Detailed algorithms on inline optimization gneuner2@comcast.net (George Neuner) (2010-01-19)
Re: Detailed algorithms on inline optimization miles@gnu.org (Miles Bader) (2010-01-20)
Re: Detailed algorithms on inline optimization rangsynth@gmail.com (Robin Holmes) (2010-01-20)
Re: Detailed algorithms on inline optimization jeremy.wright@microfocus.com (Jeremy Wright) (2010-01-20)
Re: Detailed algorithms on inline optimization dot@dotat.at (Tony Finch) (2010-01-21)
Re: Detailed algorithms on inline optimization bear@sonic.net (Ray) (2010-01-21)
Re: Detailed algorithms on inline optimization bobduff@shell01.TheWorld.com (Robert A Duff) (2010-01-21)
Re: Detailed algorithms on inline optimization cdodd@acm.org (Chris Dodd) (2010-01-23)
Re: Detailed algorithms on inline optimization mcrodgers@gmail.com (Martin Rodgers) (2010-01-24)
Re: Detailed algorithms on inline optimization anton@mips.complang.tuwien.ac.at (2010-01-25)
Re: Detailed algorithms on inline optimization monnier@iro.umontreal.ca (Stefan Monnier) (2010-01-25)
Re: Detailed algorithms on inline optimization kkylheku@gmail.com (Kaz Kylheku) (2010-01-28)
[4 later articles]
| List of all articles for this month |

From: Ray <bear@sonic.net>
Newsgroups: comp.compilers
Date: Thu, 21 Jan 2010 10:18:33 -0800
Organization: Doubtful
References: 10-01-058 10-01-061 10-01-063
Keywords: optimize
Posted-Date: 21 Jan 2010 14:53:54 EST

Robert A Duff wrote:


> Yeah, I was kind of impressed by the Verdix Ada compiler (years ago).
> A recursive Factorial function, something like:
>
> function Factorial (N : Natural) return Positive is
> begin
> if N = 0 then
> return 1;
> else
> return N * Factorial(N-1);
> end if;
> end Factorial;
>
> And then a call like "X := Factorial(7);" would compile into
> a "move 5040 into X" instruction. It had inlined 7 levels,
> and then constant-folded it. Factorial(8) didn't do that.
>
> I think 7 levels is excessive -- I'd choose 1, or maybe 2,
> because you're not normally going to be able to constant-fold
> the whole thing away.


I'd regard that as normal, but would not suspect that it was done by
means of inlining multiple levels of a recursive function and then
constant-folding and dead-code elimination until just the result was
left; I'd guess rather that the function was directly evaluated by the
compiler itself, subject to time and memory consumption limits which 7
levels of recursion did not violate, and the result was just plugged
in in place of the call.


What you have here is a "Pure" function in the FP sense, meaning its
results depend on nothing outside its own definition and its own
argument, and it changes nothing that could affect the result of any
other function. If a Pure Function call is correct (ie, types check,
it does not cause an error or other condition that could affect flow
of control, it's terminating, and it evaluates in finite memory space)
then any call to it with constant arguments can be evaluated at
compile time and replaced by its result.


So what I'd guess the compiler did was prove that the function was
pure, then evaluate the call at compile time. The 7-level limit
is probably just because the compiler imposed time and memory
limits due to being unable to prove that the call was correct.


With good reason, BTW: a negative argument, although correctly typed,
results in an infinite regress given the above code, hence calls to
the function cannot be guaranteed correct in all cases - and I don't
think I've heard of any compilers that try to prove such meta-
information on a per-call basis as opposed to a per-function basis.


                                                                Bear


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.