freenode/#clim - IRC Chatlog
Search
13:02:19
beach
nyef: You have worked on the SBCL compiler, right? I have some questions about where to find information about compilation-related topics. Can I bounce some of them on you?
13:05:39
beach
I am trying to do some control-flow analysis in the presence of nested functions. For example, I need to know when a nested function can be inlined in its caller. I was wondering whether there are some research papers on the topic, or if at least we have some common terminology to talk about things like this.
13:09:41
beach
Ultimately, I would like to determine other things, like whether lambda lifting is possible.
13:10:08
nyef
Most of my practical compiler knowledge, unfortunately, comes from working on SBCL, or from books that you probably already have (the Dragon Book, Muchnick, and so on).
13:11:12
beach
OK, how about this: I write things down, and show it to you. Then you can see whether what I write is common knowledge and perhaps point me to sources of information?
13:12:31
nyef
Actually, what happens if you reverse the question? When can a local (nested?) function *NOT* be inlined?
13:13:45
nyef
And, even then, does that mean "there must be a non-inline copy", or "there can be no inline copy"?
13:14:22
scymtym
it is for ml but mostly about inlining, closure conversion etc. static types always don't play any role
13:14:48
beach
scymtym: My bet is that we are better off with a more traditional notation, like a graph of instructions.
13:16:57
beach
nyef: It is worse than that. If a reference to a nested function is passed to an unknown external function, and that function creates multiple threads, then an arbitrary number of invocations to the nested functions can be live simultaneously.
13:17:36
beach
And if the nested function side effects a variable in its parent, all bets are off with respect to the data flow of that variable, so type inference is not possible, etc.
13:18:29
beach
Such variables might have to be excluded from SSA processing, type inference, etc, etc.
13:18:34
nyef
So, the rough rule of thumb is that any function that "escapes", even if it escapes "downwards" may need to be treated specially as far as its closed-over variables go?
13:19:34
beach
It "may" indeed. But to find out whether it escapes, a control-flow analysis is needed, and to accomplish such an analysis, one needs to know whether a closure escapes.
13:21:48
beach
I do not want to believe dynamic-extent declarations, and instead try to infer as many as possible of those situations.
13:22:43
nyef
Mmm. Be careful there. I screwed up at least one release of SBCL with a broken analysis of some sort in this direction.
13:23:25
beach
That is exactly what I am trying to be, i.e. careful. Hence my question in the first place.
13:25:33
beach
Anyway, thanks. I think I'll continue my thinking, write it down, and submit it for scrutiny. If you feel like looking at it, that would be great. Otherwise, no worries.
13:26:40
beach
I'll invent some terminology as well. If it turns out later that there is established terminology that differs, I'll just adapt.
13:40:04
nyef
Hrm. Found the phrase "lowest common dominator" in a commit message, but that's in reference to STACK analysis.
14:25:07
nyef
beach: The "escapes to another thread" thing has a couple of implications. One is that if there's thread communication going on over closed-over variables then there needs to be appropriate synchronization. Detecting that synchronization might be useful somehow.
14:27:54
nyef
Another is that it doesn't necessarily completely blow out type analysis. Yes, it can be run any number of times at any point post-escape, but there's still the synchronization rules to deal with, which say how the runs interact more generally.
14:50:28
beach
As an example of complex control flow, I came up with the function F in this paste: http://paste.lisp.org/+7P28
14:51:03
beach
Because X is assigned to in G, then all bets are off what X is going to be at any point in time.
14:52:18
beach
H can create any number of threads that call G at any point in time with any argument. So we don't even know that X is the same between two FUNCALLs, or even between two argument evaluations in a single funcall.
15:26:45
nyef
You invoked "threads" as a reason for indeterminacy, but there is no thread synchronization in this function.
15:27:39
nyef
And, as system designer in the absence of a standard model for thread interactions with the language you are implementing, *you* get to pick the semantics.
15:28:41
nyef
No thread synchronization around X, and no thread synchronization in the control-flow paths that could affect X? Devolve to the uni-thread case.
15:33:31
beach
Even with no threads, the value of x can change between two FUNCALLs, and we can't determine the type.
15:44:33
nyef
beach: Actually, we have a bound on the type, though I'm not completely sure where we're permitted to enforce it: It's a FUNCTION.
15:46:34
beach
OK, here is another piece of information. In SICL, I don't intend to trust type declarations.
15:47:12
beach
Anyway, this is not what I wanted to discuss. It was just an example of where type inference must not be applied to X.
15:47:54
beach
jackdaniel: Think LispOS. I can't allow one user to crash the system by a low safety declaration.
15:48:18
beach
I might provide some special system privilege to allow the compilation of unsafe code, and I probably will one day.
15:48:57
nyef
("You said this is a FIXNUM. Therefore, it is a FIXNUM. And if anyone (yourself included) passes a non-FIXNUM here, a TYPE-ERROR will be signalled.")
15:49:43
beach
The passage about unsafe code is that it may be run in a separate address space, but that won't work without using stuff like file descriptors, so a program would have to be written to take that into account.
15:50:39
beach
I will use such declarations to prune the possible paths that the type inferencer has to consider.
15:51:09
nyef
This also leaves the door open to "you said this is a FIXNUM, and I can show that this *is* a FIXNUM, so there's no need to check again."
15:52:28
nyef
Hrm. "Thread-safe" breakpoints by abusing per-thread copy-on-write mappings for code pages?
15:53:21
nyef
Requires the ability to have per-thread address space mappings, including as overlays, which isn't AFAIK a feature in many (any?) common OSes, but is definitely an angle.
15:55:03
beach
Clordane requires per-thread breakpoints, so that (say) the debugger can debug the debugger by setting breakpoints in it.
15:56:13
beach
... and so that one can set breakpoints in system functions that are not inlined, without running the risk that the debugger will stop when it hits one of those.
15:56:30
nyef
Another aspect to this, though, is that if the GC is permitted to move code segments, then it needs to migrate the per-thread pages as well.
15:57:34
beach
Though I have been thinking about GC in SICL, and I think I have come to a radical conclusion...
15:58:19
beach
The per-thread GC is a sliding (compacting) collector, but my recent thinking is to make the global GC is won't move its objects.
15:59:56
nyef
The main disadvantage that immediately comes to mind is the potential for weird heap fragmentation issues.
16:00:01
beach
Certain objects, like hash-table keys can be promoted so that they won't move again, avoiding re-hashing.
16:00:50
beach
nyef: Except that, as the allocator survey by Wilson at al concludes, fragmentation is not a problem in practice. And it will be even less of a problem because most cases are handled by the per-thread allocator.
16:02:05
beach
Oh, definitely. It gave me the opportunity to cite one of the best papers I have ever read.
16:03:14
nyef
I forget, what was your angle for evacuation of live objects from a per-thread nursery?
16:03:14
beach
In summary: Fragmentation was shown to be a problem by theoreticians who used stochastic models of program allocation. Wilson showed that the only programs that allocate that way are programs that don't do anything useful.
16:04:25
beach
And the write barrier promotes as well, so that there are not references from old to young generation.
16:05:41
beach
Anyway, if you want to play tricks with COW, then one could make a rule that functions are allocated in the global heap.
16:08:19
beach
Oh, and I hate to say this, but the fact that objects don't move in the global heap makes it much easier to play nice with foreign code. :)
16:09:06
beach
Imagine that: "SICL, the ideal Common Lisp implementation for interfacing with C or C++".
16:22:39
nyef
... I think that many of my remaining arguments for separate address spaces amount to safety when running alien code and compatibility with a host OS environment.
16:23:17
nyef
And the existence of a host OS environment almost requires the ability to run alien code.
16:23:40
nyef
(The lack of a host OS environment probably leads to a use-case for a C and/or C++ compiler.)
16:24:16
beach
Yes, and I addressed that problem by saying that an alien program could be run as a single Common Lisp function, in a separate address space, and communicating through something similar to file descriptors.
16:26:56
beach
Seen from a C (or similar) perspective, the result of linking a program will be a Common Lisp function that can be called as usual.
16:27:37
beach
That alien function would have to make "system calls" in order to communicate with other programs, allocate space, etc.
17:33:04
nyef
beach: The analysis that I'm remembering with respect to analysis of functions is some DX-based analysis. SBCL 1.0.44.6 - .18, 1.0.44.33 - .34, 1.0.45.5, and 1.0.45.13. November 2010 through January 2011.
17:41:43
nyef
Basically, it was aimed at not allocating value-cell objects for closed-over variables where we could show that they were not necessary.
18:17:41
nyef
Thinking about it, this is basically escape analysis where the compiler tries to prove "this cannot escape", but will accept the user saying "this will not escape upwards".
18:19:59
nyef
And then using the information to replace certain operations with less-expensive counterparts.
18:41:50
nyef
Heh. I'm looking over my notes for references to a LispOS, and came across this gem: "With automatic storage management there are three possibilities: 1. Your garbage collector and compiler have intimate knowledge of each other, and cooperate in order to manage storage allocation and reclamation. 2. The garbage collector behavior is dreadful in some major respect or another. 3. Both."
18:44:31
nyef
There's also a mention "Case 3 is, unfortunately, very common, and still a lot of work."