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
3:08:27
beach
To be clear about my opinion about SSA, let me explain. There are two main properties of SSA. One is that every value of a variable is available, a property that I shall call EVA. Another is that the notation artificially enforces the single assignment by introducing a φ operation. I shall call that property ASA.
3:08:34
beach
I have nothing against the EVA property. I think it is all good. But the ASA property ruins everything by enforcing a number and an order on the predecessors of some nodes. And all the research work I have seen (except one) takes advantage only of EVA.
3:08:35
beach
The exception is an article on value numbering that treats φ as a binary operator like the others, and in doing so, it misses plenty of opportunities for value numbering.
3:10:21
beach
I have yet to find any research that truly needs the ASA property. As a result, I must conclude that the ASA property is just a nuisance, and that we should use a notation that has the EVA property but not the ASA property.
3:12:54
Bike
i mean, i think that's common? it's what llvm does. phi nodes have an alist of (value . block) more or less
3:15:48
beach
There could very well be an assignment in each predecessor of what would otherwise be a φ node.
3:17:36
beach
This seems to me to be a case where every work that needs EVA has gone berserk and adopts SSA wholesale without realizing that the ASA property is not needed, and only represents a nuisance.
3:18:56
Bike
it's convenient to have a link in the merge variable directly to the different assignments, since each block could end with any number of em
3:21:13
no-defun-allowed
I had read some LLVM IR output before, and it didn't seem to fit how I understood SSA, so it seems they are not so strict with it.
3:21:24
beach
Bike: I don't see why it is convenient to have link to that particular assignment. If analysis techniques are used that don't rely on that particular assignment to be special in any way, then I don't see why a reference to it.
3:22:48
Bike
no-defun-allowed: the IR is in SSA. non-SSA variables are used indirectly through memory addresses which have load and store instructions.
3:23:00
beach
no-defun-allowed: I see. I guess that's my point. Most work insists on using SSA and insists that it needs SSA, but in fact, it only needs EVA, and ASA comes with it as an additional nuisance.
3:24:30
Bike
in BIR the way it works currently is that phi nodes, when they exist, compute their DEFINITIONS from the predecessor blocks when queried
3:24:34
no-defun-allowed
Bike: I remember reading some IR graph where it defined a SSA variable (which looked like %foo, not a memory address) in one basic block, then also used it before the definition, which is how I got confused.
3:24:56
beach
I am also accumulating evidence that EVA is a special case of value numbering, where anything but assignment is treated as an unknown operation.
3:25:02
no-defun-allowed
...and that basic block was in a loop. Not really how I thought of SSA, but it could be fine.
3:29:51
no-defun-allowed
It was from a tail-recursive implementation of gcd (though I suppose the CFG would be the same if you transformed it into a loop yourself), like <https://godbolt.org/z/P38vexaMs>
3:31:36
moon-child
incidentally, fun paper about basic block graphs https://link.springer.com/content/pdf/10.1007%2FBFb0026423.pdf
3:33:10
Bike
%7 is only "used before its definition" in the phi node. "%5 = phi i32 [%7,%4],[%1,%2]" means %5 is %7 if control came through block 4, or %1 if it came through block 2. Since 4 is the loop block, obviously it'll have to come from block 2 first.
3:33:12
beach
moon-child: Thanks. Interestingly, the very first words represent incorrect English grammar. :)
3:35:35
beach
moon-child: OK, I will. It is just amusing to me that they don't grab any old native speaker for proofreading.
3:39:59
beach
I guess Germans must be like Swedes; they tend to overestimate their mastery of the English language.
3:43:15
Bike
i like this graph near the end where a basic block having 30 instructions is unrealistic.
3:47:11
beach
"The advantage of edge-labeled graphs is even more drastic when looking at programs with a parallel operator" :)
3:56:35
beach
Otherwise, it's an interesting article. When I decided to use a "single instruction" graph for SICL, I had only the "higher conceptual complexity" aspect in mind.
3:58:14
beach
Plus, my reasoning was that the basic blocks could be computed on demand by a single traversal of the graph, whenever they would be convenient to have.
4:15:02
Bike
hmkay. i filed a pull request that would probably be enough for me to move to trucler in cleavir, but it changes the API a bit
4:18:04
Bike
yeah. trucler is pretty much the main block in cleavir towards actually using the ctype customization stuff
4:48:18
beach
As far as I can tell, that article doesn't really say how to represent branches in an edge-labeled SI graph. But I can see how it would be advantageous to have an explicit representation of program points. So I am considering a representation of two kinds of nodes, instructions and program points.
4:49:11
beach
An instruction would then represent a transition from a program point to one or more program points.
4:50:18
beach
But, that's not the main mission for today. I am introducing new abstractions in register allocation so as to simplify the code. That will take most of the day I imagine.