freenode/#sicl - IRC Chatlog
Search
19:10:40
samlamamma
(or well, SSA:ifies one of its IR:s is perhaps a more appropriate way of saying it)
19:10:58
Bike
SSA isn't an IR so much as a property an IR can have, and the IR used by SICL, HIR, is not generally in SSA form.
19:13:56
samlamamma
I thought it'd be nice for a dynamically typed language. All of a sudden each variable has exactly 1 type, for example
19:14:21
Bike
beach does not like that theoretically that theoretically it can cause a quadratically scaling blowup in code size, and that in usual presentations it means that predecessors to a block have to be ordered.
19:15:34
Bike
take the code (typecase x (cons (car x)) (integer (1+ x))). Even if X has a single assignment, type inference needs to infer different types in the different branches.
19:16:23
samlamamma
That's true, as x would be T in (typecase [] ...) and then cons and integer in the two branches
19:17:27
Bike
to get one type per variable you actually need a single static use form, so to speak. that's what the new Cleavir IR, BIR, is in part based on, but SICL isn't using that
19:20:05
samlamamma
Yeah, you'd need to compile the 'consequences' of the typecase into SSA through some set-assert mechanism. like (jump cons_x) \n cons_x:
19:20:34
samlamamma
I think this is what GccEmacs does, it has these vars in its SSA which have constraints set upon them.
19:21:58
Bike
yeah, you can do it as constraint propagation. that's what SBCL does. the SSA doesn't help very much with this is all.
19:24:36
samlamamma
GccEmacs did have some examples which had nicer results than SBCL does. The author hypothesised it was because of SSA
19:25:25
karlosz
SSA does help. it means you don't need to keep track of kill sets when propagating constraints
19:26:27
karlosz
the author of the python compiler wanted to add ssa and tried it for Python 2 which was in gwydion
19:28:38
karlosz
that would help with removing some dead code like (let ((x ...)) (if (bar) (setq x 2) (setq x 3)) ... or something where its clear the definition doesn't reach the use
19:30:02
Bike
you can't in general put closure variables in SSA form, right? the variable is like a data structure.
19:30:04
karlosz
since you have to simultaneously figure out what variables are set or closed over as a precondition to ssa conversion
19:32:09
karlosz
a function which is only ever local called and closes over variables just lambda lifts the environment
19:35:13
karlosz
and also ssa conversion should probably be made incremental to avoid committing to phase ordering as well
19:36:15
samlamamma
Wouldn't there be a way of doing different types of static analysis through abstract interpretation? Where the IR is the language which is interpreted.
19:38:23
samlamamma
Right, I'm saying too little. I read this paper, Abstracting definitional interpreters
19:38:24
karlosz
i mean if you make an analysis that dispatches off of the different basic ir language constructs, how is that different from a definitional interpreter?
19:39:35
karlosz
its nice to have a flow graph as the ir because you can reason about control flow like loops
19:40:14
samlamamma
AFAIK, SBCL works by mutating the IR, putting constraints on nodes and edges of the CFG, yeah?
19:41:07
samlamamma
(when I make statements, I'm basically asking, because you guys clearly know more than me)
19:41:38
karlosz
and then the constraint propagation takes type conditionals on lexical variables and pushes those through edges of the cfg
19:43:21
karlosz
(+ (* [1, 6] [3, 7]) [1, 100]) where [,] is interval notation doesn't require pushing constraints but still needs partial evaluation to give the right types
19:43:42
karlosz
by pushes those through edges of the cfg, i just mean if you have (if (typep x 'cons) A B)
19:44:21
karlosz
constraint propagation is path sensitive in the sense that the basic block A will have the constraint "lexical variable X is cons" and B has "lexical variable X is not cons"
19:45:09
karlosz
partial evaluation then takes those constraints and propagate that information to the references of X
19:47:32
samlamamma
and these constraints are actually in the IR? Pretend that regular Lisp is the IR. We'd actually have objects x0,x1 which has an attached type
19:47:43
pjb
karlosz: what about (let ((x '(a . d))) (make-thread (lambda () (setf x 42))) (if (typep x 'cons) (+ x x) 0))
19:49:35
karlosz
samlamamma: the IR is not formally specified. the "IR" is just whatever information you have about the program
19:51:28
karlosz
from the point of view of actually doing the type inference it doesn't matter how you view it, you are just modifying some data structure holding information about the program
19:52:14
samlamamma
I'm used to way more formal stuff. Probably because I mostly read research and not actual code bases lol :-/.
19:52:18
karlosz
it's nice to have a formally specified IR if you want to prove things about it, but for a practical compiler it doesn't matter that much
19:52:41
karlosz
research papers need to formally specify exactly what kind of language they are using so they can prove stuff about ti
19:53:13
karlosz
though it sometimes helps to informally specify it since it does help with soundness
19:53:24
samlamamma
Yup. The nice thing about having to formally specify something is that it typically ends up pretty small, because formally specifying stuff is a
19:55:08
Bike
i would like to make a function to copy BIR modules so that scymtym's visualizer and such can show changes easier, but unfortunately, doing a copy is going to be kind of a pain in the ass
19:56:31
Bike
also (not) triggering the shared-initialize stuff at the (wrong) right times, which ofc goes with what you were saying the other day about rewriting BIR being annoying
19:58:09
Bike
it's like on the one hand i don't want to be triggering the "you can't change this thing's use" stuff all the time, but also I don't want to have to manually force updates to use lists or something
19:59:22
karlosz
maybe using the output indirection rather than trying to maintain input lists will help with that
20:00:02
karlosz
it's probably best to move that stuff out of clos mechanisms if you want to have a copying protocol
20:01:16
Bike
putting methods on shared-initialize makes creating objects through other means really annoying.
20:02:23
karlosz
having explicit constructors and defining macros to abstract over that stuff instead of using clos sounds like the way to go to me
20:04:24
Bike
scymtym: maybe. my last attempt involved allocate-instance-ing everything and then filling it all in with initialize-instance, but slot-values more directly could work too
20:08:08
karlosz
function-level copier sounds feasible as long as its being transplanted into the same module
20:09:24
Bike
Yeah, it's just more involved because you need to copy some variables but not closed over variables, and also you might need to copy closures within the function
20:11:18
Bike
oh, on that note, i was thinking of extending the contifier to handle functions that never return, since in that case they don't need to have a common return point
20:12:44
karlosz
i suspect the noncomputation change may have possibly regressed the contifier a bit
20:13:18
karlosz
the fact that this didn't go off more quickly makes me suspect that https://github.com/s-expressionists/Cleavir/commit/29d73fd910fcd19ee5ee4d164ab14ece8d385b4a
20:14:32
Bike
well, i didn't check if they were contified or not, i just didn't see any check on a function's returni in common-return-cont
20:18:47
karlosz
uh, yeah, the logic is a little convoluted, but essentially how it works for functions that never return is that common-return-cont will return unknown because all the calls return to different places (they don't actually return, but the calls would return to different places if the function DID return)
20:19:07
karlosz
https://github.com/s-expressionists/Cleavir/blob/29d73fd910fcd19ee5ee4d164ab14ece8d385b4a/BIR-transformations/interpolate-function.lisp#L250
20:19:33
karlosz
so here it says that we can contify :UNKNOWN return-points if local function doesn't return (i..e have a returni instruction)
20:20:32
karlosz
it would be nice if the IR could be made to make the contifier cleaner, since that's definitely the most non-trivial and brittle optimization right now
20:21:21
karlosz
this function is what i worried might have regressed https://github.com/s-expressionists/Cleavir/blob/29d73fd910fcd19ee5ee4d164ab14ece8d385b4a/BIR-transformations/interpolate-function.lisp#L8
20:21:36
karlosz
this was actually cleaner in HIR, but the block structure kinda blocks the data-flow and control flow a bit
20:21:59
karlosz
in sbcl its a bit better because lvars and ctrans are divorced from the basic block structure a bit more
20:23:04
Bike
i did a basic update of that function in noncomputation but without thinking too deeply about it
20:23:44
Bike
i still don't entirely understand what ctrans are. are they explained in the cmucl internals thing somewhere?
20:24:04
karlosz
ignoring jumps so that (if (foo) (f) (g)) the calls (f) and (g) return to the "same place"
20:24:35
Bike
yeah i know what logical-continuation does conceptually, i just mean i wasn't editing much smarter than sed
20:24:51
karlosz
Bike: in cmucl lvars and ctrans are one data structure called "continuation". here, i recently updated the sbcl block comment to explain that better...
20:25:30
karlosz
https://github.com/sbcl/sbcl/blob/54ce2e42f9ccefb2e831ef8831245cb08d570429/src/compiler/node.lisp#L118
20:25:51
karlosz
i just updated this comment to be more like the comment in cmucl since the one in cmucl was better
20:26:45
karlosz
so like instead of nodes having a next pointer to a node, it has a next pointer to a ctran, which has a next pointer to a node
20:32:13
Bike
i'm sorry, i am just totally failing to comprehend the point of this. i'm sure there is one, i just don't understand
20:33:36
Bike
does the ctran... i mean... like if you have a node, and it outputs something, the ctran represents the continuation that receives that something?
20:36:46
karlosz
that's also how the ir1 conversion pass is able to make (if x y (if a b c)) only make 6 basic blocks instead of 7
20:37:38
Bike
i see there's a USE field. that's the node that takes as input the node that has the ctran next? i can't phrase this very well
20:39:27
karlosz
its pretty confusing since as the comment i wrote said, a lot of this is keeping terminology from back when ctrans and lvars were packaged into one thing called continuation
20:39:54
karlosz
the USE field of an lvar is also the nodes which define it, not the node which receives the value. thats the dest
20:40:28
karlosz
the idea of the term USE is that a node would "use" a continuation by going there next
20:43:09
Bike
it says the use is nil for block start ctrans, so i guess the cblock must have the predecessor information that could include having more than one predecessor.
20:44:02
Bike
and this would also be helpful for doing modifications on the ir, rather than just generating it?
20:45:21
karlosz
i don't remember if it actually helps with doing modifications, but it definitely helps with generating it
20:46:25
karlosz
instead of needing to keep a handle on a node, which could possibly be swapped out or substituted for, you keep a handle on the ctran
20:49:51
karlosz
this is the design decision that makes working with Python "easy", as paul khuong explains in the 2nd and 3rd paragraphs of this https://pvk.ca/Blog/2013/11/22/the-weaknesses-of-sbcls-type-propagation/
20:53:47
karlosz
looking at the ir1-translator for IF is pretty instructive on how lvars and ctrans are actually used: https://github.com/sbcl/sbcl/blob/54ce2e42f9ccefb2e831ef8831245cb08d570429/src/compiler/ir1-translators.lisp#L24
20:59:51
karlosz
ir1-convert takes the predicate form and translates it with "pred-ctran" being the "next"
21:00:09
karlosz
and at the end of each ir1-convert method it links up the control flow with the "next"
21:09:01
Bike
if you have (if x (if y z w) v), first this ir1 translator gets called. it does ctran-starts-block on the next. it calls ir1-convert on (if y z w) which goes back here. it calls ctran-starts-block on next again, which does nothing I guess? and then calls ir1-convert again on z and w. so all the ir1-convert calls on z, w, v get the same next to hook up to.
21:10:17
karlosz
which is nice, because it is the next-ctran, and the decision to which block it belongs to is more flexible
21:10:36
karlosz
unlike with the block based approach where you're tied to making a block for every merge point
21:17:44
karlosz
i was banging my head for a while on how to change ast-to-bir to do this without the indirection but i don't think it's possible
21:24:40
Bike
how about the ctran/lvar split? do you think that's justified, or was the original cmucl design of having one "continuation" better?
21:29:37
karlosz
me and dougk were super confused, because the commit by alexey dejneka which split the continuation structure into lvars and ctrans had absolutely NO explanation
21:30:29
moon-child
beach, ebrasca: froggey spoke in #osdev earlier today and over the past couple of days, so almost certainly not dead
21:31:16
Bike
i should just rewrite the readme since clearly if i wait on a stable IR format i will die first
21:32:42
karlosz
also i think douglas katzman mentioned that the bug in question seemed to be fixed in cmucl without doing this
21:34:54
karlosz
i spent quite a long time finding like some kind of explanation for this but nothing turned up
21:40:11
karlosz
what did happen though is that a lot of the comments no longer make any sense because of course not all the comments were updated