Re: Detailed algorithms on inline optimization

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

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