freenode/#sicl - IRC Chatlog
Search
5:45:13
alandipert
yesterday i learned the penalty of doing my reader the async/incremental way... 10x, my ~50 line nascent boot.lisp took 100ms to compile
5:46:37
alandipert
i didn't notice the slowness since i'd been doing everything at a repl so far. fortunately i switched to sync pretty easily and now it's down to 8ms
6:32:44
beach
I need to sort out all the cases of non-local control transfer. And by that I mean a case where one HIR instruction is executed in some dynamic environment DE, but its successor is executed in a dynamic environment that is a strict suffix of DE.
6:35:32
beach
So let DE be the list of entries (e0 e1 ... en) and let the strict suffix environment SE be (ei ei+1 ... en) where 0 < i <= n.
6:36:59
beach
The simple case is when we have an UNWIND-INSTRUCTION. This instruction is emitted when we do not know what entries might exist in the prefix, because of some arbitrary intervening function invocations.
6:37:28
beach
Then we need to do a full transfer to an exit point as the Common Lisp HyperSpec describes.
6:39:43
beach
We traverse DE to find the entry to which we transfer control, "abandoning" intermediate entries. If no entry is found, signal an error. If an entry is found, unwind by abandoning the intermediate entries, calling thunks established by unwind-protect, etc.
6:41:14
beach
We can generate code for the UNWIND-INSTRUCTION as a call to a function that does all this, and then returns as usual. The generated code ends with a jump to instruction where execution must continue.
6:42:32
beach
Now for the tricky case. It is when there is no UNWIND-INSTRUCTION. Yet, we have a non-local control transfer.
7:05:33
beach
There are two complications that I need to return to. One is the dynamic environment of the successors of the CATCH-INSTRUCTION. The other has to do with whether entries of the dynamic environment are allocated on the stack or on the heap.
7:07:48
beach
Also, let's say that DE = (e0 ... en) is itself a prefix that has been established by the current function, and that the full dynamic environment FE is really (e0 ... en en+1 ... em) so that the current function was called with (en+1 ... em) as the dynamic environment.
7:08:23
beach
Now, for the case where we have a non-local control transfer, but no UNWIND-INSTRUCTION.
7:09:57
beach
There are two cases where this can happen. Case 1 is when the control transfer is a result of compiling a RETURN-FROM or a GO. Case 2 when it is not.
7:14:46
beach
In the first case, there is a BIND-INSTRUCTION that establishes an environment entry, and in the second case, there is an UNWIND-PROTECT-INSTRUCTION that also establishes an entry.
7:17:42
beach
A third case is the last instruction of a BLOCK. And a fourth, the last instruction of a TAGBODY.
7:20:36
beach
In case 2, there can be more than one entry in (e0 ... ei-1) because LETs can be nested, or A LET can be nested inside an UNWIND-PROTECT, etc.
7:22:50
beach
The main important question for case 2 is whether there are any UNWIND-PROTECT entries among the entries (e0 ... ei-1), because if that is the case, the associated thunks must be executed.
7:25:31
beach
Putting aside the second complication mentioned above for a second, if there are no UNWIND-PROTECT entries in (e0 ... ei-1), we can just abandon the entire thing, i.e. do nothing. The successor instruction of the control transfer will be executed in (ei ... en).
7:26:30
beach
As it turns out, whether there are UNWIND-PROTECT entries in (e0 ... ei-1) can be determined statically.
7:27:49
beach
While we can not know the identities of the entries in (e0 ... en) at compile time, we can establish a symbolic representation of them that includes the type.
7:28:29
beach
Every instruction has a slot containing lexical location that represents the dynamic environment in which it is executed.
7:29:21
beach
And every instruction that establishes a new dynamic environment has a lexical location as an output for the new dynamic environment.
7:34:11
beach
So we can traverse the instruction graph, looking for these instructions that establish new environments, and we get something like In:Tn:en+1->en In-1:Tn-1:en->en-1 etc. where Ij is an instruction, Tj is a type.
7:35:17
beach
Now, with this information, we can determine whether a non-local control transfer contains an UNWIND-PROTECT entry.
7:37:21
beach
As it turns out, case 1 (the control transfer is a result of a RETURN-FROM or a GO within the same function) can be handled the same way.
7:39:18
beach
If the entries are allocated on the stack, they can't just be abandoned as food for the garbage collector. They need to be popped off explicitly.
7:41:12
beach
Maybe this situation can be handled by explicit POP instructions inserted in the arc that represents the non-local transfer.
7:43:25
beach
And, if there is an UNWIND-PROTECT entry we need some instruction to execute the thunk. Perhaps this could be handled with a special instruction to get the thunk from the top entry in the dynamic environment combined with a FUNCALL-INSTRUCTION.
7:46:01
beach
So then, the control arc representing the non-local control transfer will have some sequence of instructions, some of which are POP instructions, some of which are instructions to get the thunk from the top entry, and some of which are FUNCALL-INSTRUCTIONs.
8:11:03
beach
If the UNWIND-INSTRUCTION is a result of a RETURN-FROM, it is possible that the "successor" is executed in the same environment as the CATCH-INSTRUCTION itself, or it is possible that the compiler put in a NOP there that is executed in the environment established by the CATCH-INSTRUCTION, so that the non-local transfer is between the NOP and its successor.
8:11:04
beach
Similarly, if an UNWIND-INSTRUCTION is the result of a GO, and the tag is the immediately before the end of the TAGBODY, then it is possible that the "successor" of the UNWIND-INSTRUCTION is executed in the same environment as the CATCH-INSTRUCTION. Though, if the tag to go to is followed by some instructions, then the "successor" of the UNWIND-INSTRUCTION is executed in the dynamic environment established by the CATCH.
8:11:48
beach
The complication here is that if we call a function UNWIND to do the work, then that function can not have access to the information that is needed.
8:14:17
beach
So here is a suggested solution. The UNWIND function will always leave the entry that was established by the CATCH-INSTRUCTION on top of the dynamic-environment stack. We determine statically whether the "successor" of the UNWIND-INSTRUCTION is in the same environment as that of the CATCH-INSTRUCTION (case A) or whether it is in the environment ESTABLISHED by the CATCH-INSTRUCTION (case B).
8:15:55
beach
In case A, we insert another of those POP instructions right after the call to the UNWIND function, and before the jump to the successor.
8:18:21
beach
I am tempted to insert all these functions as part of Cleavir AST-to-HIR, simply because I can't imagine how they would hurt any client. I mean, they just add information that can be ignored by the client HIR-to-MIR conversion.
8:18:59
beach
But, for now, I'll define the additional instructions in Cleavir, but I will make the transformation optional, in HIR-transformations.
8:28:36
beach
Oh, one more thing. When a BLOCK/TAGBODY entry is popped off of the dynamic environment, does it need to be marked as "abandoned"?
8:29:39
beach
I.e., is there a situation in which, at some later point, this entry might become the target of an UNWIND-INSTRUCTION?
8:33:37
beach
The reason I think it can't happen is that there is no possibility of capturing the dynamic environment, so this entry can no longer be referred to.
12:18:48
shka_
because of a bad prior decission current protocol has this messy concept of multistage aggregation
12:19:37
heisig
I'm genuinely curious about the performance you can get. Also, I think it is an interesting challenge to design the right protocol for working with these closures.
12:24:11
shka_
range can act as a closure factory, and all i reall need is one function to push stuff down in aggregation