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
14:20:41
beach
Bike: I did what splittist calls a "brain dump" this morning. It is probably stuff that is hard to digest by most #sicl participants, but if you could have a quick look (at your leisure of course) I would appreciate it. It should be in the logs.
14:22:52
Bike
i thought you were going to have some kind of local unwind instruction, but maybe i misunderstood
14:24:54
beach
I was going to, but it seems it is not necessary, and it doesn't solve the problem anyway.
14:27:03
beach
I mean, sure, I could stick such an instruction whenever there is a change in the dynamic environment, but I wouldn't know what to do with it. And if I stick it in as a result only of a RETURN-FROM or GO, then that won't solve the problem, because I may have UNWIND thunks to execute in other cases as well.
14:32:59
beach
A different solution would be to implement UNWIND-PROTECT always as a function call. That would force an UNWIND-INSTRUCTION whenever the cleanup forms need to be executed. But I still need to pop the environment for local changes like when a LET binding of a special variable ends normally.
14:35:10
Bike
so if you trun a local exit through an unwind protect into a "grab thunk, funcall it" thing, is there a similar sequence for a special variable unbinding?
14:36:39
beach
No, and that's the thing. All I have is two consecutive instructions to be executed in different dynamic environments.
14:39:34
beach
Again, all I have as output from AST-to-HIR is two consecutive instructions in different environments.
14:44:02
beach
So, if memory serves (HAHAHAHA!!) I meant to handle it as a special operator that generates an instruction UNWIND-PROTECT-INSTRUCTION.
14:45:56
Bike
i'll have to think about how special variable un/binding can work in clasp right now. i don't think the representation here is very amenable to what clasp is doing.
14:46:57
beach
It should work. If I introduce a special UNBIND-INSTRUCTION, then that could be turned into the actions you need in order to unbind.
14:49:00
beach
Right now I am thinking of it as being introduced in this post-AST-to-HIR transformation when there is an instruction with a successor in a different environment, and the difference is a bind-instruction.
14:50:40
beach
To generate it directly, the compilation context would have to contain a representation of the dynamic-environment stack.
14:52:30
beach
That could be fixed of course, which might in fact be the best solution so that the information does not have to be re-derived.
14:58:10
beach
I might make it a transformation for now, and put off modifying AST-to-HIR until later on.
15:00:35
beach
In order to plan for such a change to AST-to-HIR for later, I would need to be convinced that I am not doing anything that would be impossible to process for certain clients.
15:01:39
beach
But the more I think about that, that appears to be the good solution: Change the compilation context so that it contains a stack with the symbolic representation of the dynamic environment.
15:06:00
beach
I know I have only a small number of cases left to handle before I can generate native code. But it seems that every new case I tackle requires a significant change or addition before it works to my satisfaction.
15:09:36
beach
So, let's think about UNWIND-PROTECT. When a programmer uses that, it's that there is a possibility that there is a non-local transfer through it. So we do need to create a thunk and stick it in the dynamic environment. There could be a possible optimization when the protected forms terminate normally, but it may not be worth the trouble.
15:12:51
beach
It seems reasonable to compile it as an ENCLOSE of a nested function, an UNWIND-PROTECT-INSTRUCTION that takes the thunk as the input and the instructions of the protected form as its successor.
15:14:21
beach
The instruction adds an UNWIND-PROTECT entry that contains the thunk to the dynamic environment.
15:15:37
beach
The local control transfer from the protected form to the successor of the UNWIND-PROTECT form will be one where the dynamic environment is different.
15:16:08
beach
So we detect statically that there is an UNWIND-PROTECT entry on the dynamic environment, find the thunk and funcall it.
15:16:37
beach
I mean, we introduce and instruction in that control arc to find the thunk, and we introduce another instruction to funcall it.
15:17:31
beach
But that could be bundled up into a single instruction, which might be better for clients that handle UNWIND-PROTECT as a function call.