On Sun, May 27, 2012 at 3:03 PM, Nikodemus Siivola
<nikodemus@...> wrote:
> On 27 May 2012 13:17, Paul Khuong <pvk@...> wrote:
>
>> We could convert most cases of inlining (e.g. when space > 0) into:
>>
>> (load-time-value (the (function ...)
>> (get-cached-function [specialization key]
>> (lambda (...)
>> inlinable code ...)))
>> t)
>>
>> Hopefully, this can be macro-ed up without any deep change.
>
> +1
>
> IIRC some of the dylan compilers have an inlining mechanism very much
> along these lines:
>
> Define a function, specify which sort of things about which arguments
> make for good special cases, when you encounter one, find/generate the
> specialized version and emit an out of line call to it.
I have a first stab up at
https://github.com/pkhuong/sbcl/tree/cached-specialisation (sorry, I
forgot to americanize the branch name :).
The specialisation stuff is localised to the
compiler/ir1-cached-specialization.lisp and
code/early-cached-specialization.lisp (and one extra form in
ir1-optimize-combination). I'm not quite sure how I'd want to expose
this to users yet.
The new optimizer returns 4 values:
- specialization key
- form to evaluate into the out-of-line function
- list of arguments to that function (as a list of lvars)
- list of lvars that shouldn't inhibit DXness.
Specialisation itself could all work without the additional DX stuff,
but the out of line calls introduce additional consing.
The demo optimizers in ir1-cached-specialization.lisp all follow the
same pattern: constant function arguments that can be optimised
usefully are specialised on, along with sequence argument types,
from-end, and whether start/end have the default value.
The DX stuff mostly happens in recheck-dynamic-extent-lvars. If
functional-may-escape-p is false, the function is DXed. For that to
work, labels/flet have to always be ir1-translated as though there
were a DX declaration. Functional-may-escape-p also have to be much
more aggressive, and try to detect downarg-only funargs (otherwise
auto-dx is useless). I really don't trust that part, especially the
bit where I use lambda-ancestor-p to make sure the use is within
scope.
Downward-only funargs are detected with a new property for known
functions: dx-safe-p is either a list of indices, or a function that
returns a list of lvars. Those argument indices or lvars are
downward-only.
That's not enough for out of line calls though: the function is only
known at runtime. LVARs have gained a new attribute: dx-safe-p. Rather
than determining whether the lvar's value is DX, it only means that
the LVAR shouldn't prevent a value from being stack allocated. This
field is mutated maybe-specialize-call, after the combination's new
function has been ir1-translated.
Finally, we still have to handle straight lambda arguments. I thought
about translating those into IR1 that acts like
(progn ... (lambda ...) ...) => (progn ... (flet (...) ...))
but I'm afraid of the potential for huge stack growth with long
progns. Instead, I'm thinking we should just have a bunch of source
transforms to perform that conversion, with just the right scope;
ideally, there would even be a nice declarative way to do that.
src/compiler/seqtran.lisp has two examples for map and map-into,
Comments/review? functional-may-escape-p looks like a probable source
of bugs; it is very new, and much more aggressive than nikodemus's
initial code.
Paul Khuong
|