freenode/#clasp - IRC Chatlog
Search
4:37:08
beach
Inlining global functions such as CAR is not as trivial as we might have thought. For good reasons, in Common Lisp, you are not allowed to shadow CAR in an FLET, so we must give it a different name, and make sure that references to it in the form of direct function calls are renamed. References like #'CAR should not be affected.
4:38:52
beach
Though I guess we could translate each call, like (car x) becomes (flet ((car (x)) <copy-of-ast>) (car x))
4:43:06
beach
In that case, it is fairly simple. Just replace (car x) by (flet ((<gensym> (x) <copy-of-ast>)) (<gensym> x)).
5:32:51
drmeister
Next I'll add multiple entry points - but I have to work on some other stuff for a couple of days. (I keep saying that - but I keep working on code).
7:15:14
beach
If by "multiple entry points" you mean different entry points into a function according to the number of arguments passed, then it may not be worthwhile. With a lot of inlining, most functions will do some non-trivial computations, and the cost of that computation may dwarf the cost of a test for the number of arguments.
7:39:57
Shinmera
I think I recall learning in my compilers class that JDK compiled multiple entry points for some methods, but I can't recall why.
8:30:25
loke
Shinmera: you might be thinking of how the Java compiler implements covariant return types.
8:46:51
beach
I think what drmeister is doing is taken from an idea from the Movitz compiler in order to avoid checking the number of arguments in many cases. A static programming language would not have that problem.
8:49:44
beach
See page 4 of this document: http://www.european-lisp-workshop.org/archives/2004/submissions/Fjeld.pdf
8:51:37
beach
In most cases, a register could then be freed up, namely the one that holds the argument count.
8:59:18
beach
As an example of complex control flow, I came up with the function F in this paste: http://paste.lisp.org/+7P28
12:27:01
drmeister
The _FOOA^COMMON-LISP-USER^FN^^ is the fastgf dispatch function evaluating va_arg and comparing it to an integer. va_arg is probably the slow part.
12:59:30
drmeister
If shiho is there - can you tell her that I fixed the problem she was having last night and she can pull and rebuild.
13:01:38
drmeister
After sleeping on it I don't think I'll bother with multiple entry points. They don't solve the problem I thought they solved.
13:07:23
drmeister
I don't think I can leave empty space on the stack for processing keyword arguments.
13:08:15
drmeister
So I use varargs and spill register arguments into the register save area and rewind the va_list structure to point to the first argument.
13:09:12
drmeister
They have to do work to figure out if they should pull the next argument from the register save area or from the overflow area.
13:10:52
drmeister
At the very least I should give fastgf the ability to use register arguments - it's not difficult.
13:14:11
drmeister
They take a list of arguments and a list of next methods. Where do the registers go?
13:21:02
beach
drmeister: For standard generic functions with only required arguments, you should be able to do better than a list of arguments.
13:23:38
Bike
i think having the actual effective method form can help with that, like, if it's (call-method #<standard-reader-method> ...) that's when we can inline the read
13:26:35
beach
That kind of work looks like it is independent of the implementation. It would be great if you could pay attention and separate the possible Clasp-specific parts so that the rest of your code could be reused.
13:27:21
Bike
i'll try. i mean, the first thing i want to do is change clasp's compute-effective-method so that it returns something usable anywhere
13:28:59
Bike
right now it works like https://github.com/robert-strandh/SICL/blob/master/Code/CLOS/compute-effective-method-support-a.lisp which is kind of opaque
13:30:16
Bike
clasp seems to have gotten through clos without standard-optimized/reader/writer-method, that's a good start
13:32:55
Bike
for eliminating it completely, i think i know when the actualf irst generic function call is, so i think if everything is satiated before that it will work
15:02:50
beach
Bike: So, let me get this straight. We want to do some value numbering. For one thing, we want to do some simple value numbering to improve type inference and perhaps to be able to remove some useless temporaries. We should be careful about removing temporaries, though, because it may make register allocation harder.
15:02:59
beach
We might also want to do some value numbering for primop:car, primop:fixnum-add, etc. in case there is duplication of those operations on operands that are equal. Now both value numbering and type inference depend on control flow, so if the control flow is complicated, then we may have to omit some variables from the analysis.
15:03:02
beach
Inlining means that the environment of the inlined function is in fact part of the environment of the caller. So inlining works only if there is a single occurrence of the callee environment active at any point in time. In particular, if the environment may be captured during the invocation of the callee, and if that can happen more than once during the invocation of the caller, then we can not inline.
15:05:08
Bike
Um... meaning you can't inline within a function that encloses? no, that can't be right
15:07:29
beach
So, take SORT for instance. The function that calls SORT (call it F) has a single environment active while sort is executing, so the environment created when F is called is destroyed when F exists.
15:09:25
beach
But, again, if F is only called once during the invocation of ITS caller, then we are again OK.
15:09:30
Bike
if F calls some unknown function and one of the arguments in the call is a closure, just to be clear?
15:12:39
beach
We are also OK in the (unusual) situation where the closure created by F when it calls ARBITRARY does not refer to any of the variables in F's environment.
15:16:13
beach
So it boils down to determining whether it is fine for the callee environment to be part of the caller environment, and this is fine if and only if no more than one instance of the callee environment is active at any point in time.
15:18:36
beach
Interestingly, whether the callee accesses or modifies variables in its caller, does not influence the inlinability.
15:23:42
Bike
If you have (lambda (x) (let () (lambda () x))), the implicit LET-lambda can still be inlined, even though it has a closure referring to the caller's environment, right? is returning a closure okay, just as long as it's not passed to an arbitrary function?
15:25:00
beach
Yes, like I said, references to the caller's environment don't influence the decision. In this case the (let () ...) has an empty environment, so it can trivially always be shared with that of its caller.
15:25:30
Bike
drmeister: clos::set-funcallable-instance-function checks whether the new value is a funcallable instance (with asOrNull<FuncallableInstance_O>) and then passes to another function. but we pass it symbols all the time, what's going on?
15:26:53
Bike
so in (lambda (x) (let ((y x)) (lambda () y))) we couldn't inline the let-lambda, at least not without further analysis, because every time the outer lambda is called the let-lambda should make a new environment.
15:30:37
beach
The good news is that the vast majority of cases are very simple, so we can get away with a simple analysis initially and work on more sophisticated ones later.
15:32:11
beach
For value numbering and type inference, we must first determine the set of variables that can be counted on to be modified ONLY as a result of the usual control flow. Clearly, variables that are not accessed in nested functions qualify. Whether shared variables qualify depends on considerations similar to the ones about inlining.
15:34:45
beach
In fact, if a nested function (say F) that modifies some variable of its caller can be inlined, then by inlining it, we have normal control flow again.