Re: Detailed algorithms on inline optimization

Robert A Duff <bobduff@shell01.TheWorld.com> writes:


> Peng Yu <pengyu.ut@gmail.com> writes:
>
>> [Unless you're trying to in-line a recursive function, it's pretty straightforward. -John]
>
> Or indirect/dispatching calls.
>
> You can inline recursive calls if you limit the depth.
>
> - Bob
> [True. Does anyone do that, inline the first few times though and then punt to the
> normal routine? -John]


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 don't know if GNAT (the gcc Ada compiler) can do this sort
of thing. I don't think it's all that hard to implement,
and could speed up things like a binary tree walk (inline
the call on Tree.Left one level, and do tail-recursion
on the call on Tree.Right).


The gcc back end does some inlining (which applies to all
languages), and the GNAT Ada front end does some other inlining.
But I'm not familiar with details in this area of gcc/GNAT.


- Bob

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