Re: Detailed algorithms on inline optimization

Ray <bear@sonic.net> writes:


> 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.


That's a reasonable guess, but it's also a wrong guess. ;-)
I know how it worked, and it worked as I said, via inlining.


Note that inlining also works for other recursive cases,
where no constant folding applies -- a tree walk, for
example.


> 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.


I hope by "time limit" you mean a limit on the number of steps.
You really don't want to measure real time (at compile time),
because then the compiler will get different answers depending
on the phase of the moon. I know of one compiler that did
something like that, and it was a nightmare in terms of
customer support.


> With good reason, BTW: a negative argument, although correctly typed,
> results in an infinite regress given the above code, ...


No, a negative argument will raise an exception. The subtype of the
formal parameter is Natural, which is defined in Ada as:


        subtype Natural is Integer range 0 .. Integer'Last;


so Factorial(-10) will fail a range check.


But you're right -- if the formal's subtype were Integer,
then the compiler needs to make sure it doesn't loop
forever (or run out of memory).


- Bob

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