Re: Detailed algorithms on inline optimization

Robert A Duff wrote:


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


Chez Scheme does it. See this paper for details:
Fast and Effective Procedure Inlining (Waddell, Dybvig)
http://citeseer.ist.psu.edu/waddell97fast.html


They use effort, size and fold counters to limit code growth. This
works better than just limiting the call depth, as they do constant
folding as they inline. They give results for an effort counter limit
of 1000. This may sound like a lot, but they claim extensive caching
helps exploit the effort expended even on calls that ultimately exheed
a counter limit and fail to inline.


Implementing the basic inlining procedure with counters in one of my
own compilers suggested that this can indeed work very well. There are
many enhancements suggested in the paper, but I didn't have time to
implement them. I expect Chez Scheme uses them, however.


Another interesting aspect of their technique is the different
handling of contexts. They distinguish between value, call, test and
unused references. The caching also exploits this, of course. The
caching leads to specialisation of procedures, so even residual calls
can benefit from this technique.


-- Martin Rodgers http://www.wildcard.demon.co.uk

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