mon1 has quit [Quit: This computer has gone to sleep]
<sb0>
whitequark, why is it complicated to do this static analysis on IR?
<whitequark>
sb0: so there are essentially two cases we need to handle
<whitequark>
the first case is a function. if it's defined in the same scope where it's used, all is simple, but if it's defined in an outer scope, you now have an interprocedural analysis that has to keep track of passing an environment around *and* mutation
<whitequark>
the second case, which is worse, is the embedding
<whitequark>
what i do is i create a class object for every class either brought onto the core device directly, or via an instance of said class
<whitequark>
and then i set the corresponding attribute of the class object to the function body
<whitequark>
but, since the output of the embedding pass is an AST and not IR, what *really* happens is that there's an AST roughly equivalent to the following code:
<whitequark>
def f(self, ...): ...
<whitequark>
class c:
<whitequark>
f = f
<whitequark>
so now I would have to do all the tracking for the function case, *and* also look at the class definition
<whitequark>
which substantially expands once you convert it to IR
<whitequark>
in other words, the /compiler/ IR and the /static analyzer/ IR are two cases with almost opposite design points
<whitequark>
when you're making a compiler IR, what you want to do is to desugar all the syntax into the simplest constituents, without much regard for mapping it back to semantics of surface language
<whitequark>
as a result, you have a simple IR, which is much more expressive than the surface language
<whitequark>
normally, this is what you want, because optimizing passes are all about expressing things that are too simple to be directly represented in the surface language
Mon_ has joined #m-labs
Mon_ is now known as Guest20147
<whitequark>
but when you are writing a static analyzer, the raison d'être of the IR is to simplify out all irrelevant syntactic details of the surface language, but, conversely, keep all of the semantics
mon1 has joined #m-labs
<whitequark>
i.e. you would really want to directly represent lexical scope in a static analyzer IR
<whitequark>
note how in ARTIQ right now, or in LLVM, absolutely no errors propagate up from the IR level
<whitequark>
that's because you cannot. you've thrown away too much information
<whitequark>
(alright, there's actually an error in ARTIQ that propagates up from IR level, it's the undefined local one, but that's really an exception)
<whitequark>
there is another aspect of it, which is that, since users do not, and indeed want not, understand your optimization passes, you do not want to make the results of analysis dependent on any transformations you do on IR
Guest20147 has quit [Quit: This computer has gone to sleep]
<whitequark>
so in this case, it's lucky that analyzing the AST directly is not hard; analyzing the AST is something you generally want
<whitequark>
mapping the results of that to IR level when you're generating IR is more annoying though
Guest20147 has joined #m-labs
<whitequark>
conversely, you really don't want to do inlining on ASTs. loop unrolling is kind of a weird edge case, because it /would/ be quite a bit easier to do it on AST level in this particular case, but that conflicts with the design goal that loops should only be unrolled when necessary
<whitequark>
so that will be done on IR level too
<whitequark>
(directly represent lexical scope) you might think that conflicts with SSA and makes analysis much harder, but interestingly enough, it doesn't
<whitequark>
you can basically say that nested functions capture SSA names from the outer function, as long as you represent mutability using a cell. i.e. bindings are inherently immutable, but some of them hold mutable cells
<whitequark>
that's how IRs for most functional languages look like. they call it CPS though.
Guest20147 has quit [Quit: This computer has gone to sleep]
mon1 has quit [Quit: This computer has gone to sleep]
FabM has joined #m-labs
Mon_ has joined #m-labs
Mon_ is now known as Guest13090
ylamarre1 has quit [Quit: ylamarre1]
Guest13090 has quit [Quit: This computer has gone to sleep]
Mon_1 has joined #m-labs
mon1 has joined #m-labs
Mon_1 has quit [Client Quit]
Mon_ has joined #m-labs
Mon_ is now known as Guest33580
Guest33580 has quit [Quit: This computer has gone to sleep]
FabM has quit [Ping timeout: 250 seconds]
FabM has joined #m-labs
mon1 has quit [Quit: This computer has gone to sleep]
rohitksingh has joined #m-labs
<cr1901_modern1>
Wow, the wikipedia article for CPS is giving me a headache. I hope that's not the case when I can focus better
Mon_1 has joined #m-labs
mon1 has joined #m-labs
Mon_1 has quit [Quit: This computer has gone to sleep]
mon1 has quit [Quit: This computer has gone to sleep]
<whitequark>
CPS is kinda backwards
<whitequark>
the idea is that you transform control flow in a function into a set of mutually recursive functions tailcalling each other
mon1 has joined #m-labs
Mon_ has joined #m-labs
Mon_ is now known as Guest34499
<cr1901_modern1>
One of the links on the wikipedia page led me to a proposed Scheme-to-C impl. As part of the intro, the paper discusses how tail recursion in C can be implemented as a function consisting of a single loop.
<whitequark>
sure
<cr1901_modern1>
The loop calls a function, which returns another function, which is called on the next loop iteration. Now I guess in FP languages, the outer function would also be called recursively
<whitequark>
a tail call is literally a jump
<cr1901_modern1>
so, in a language where tail recursion isn't broken, the inner function would pass in the next function to call to the outer function, instead of returning
<cr1901_modern1>
right
<whitequark>
(you also have to pass arguments somehow, which makes it complicated in C)
<cr1901_modern1>
The paper's intro says the functions vars are global :P
<whitequark>
that sounds like a reasonable way to pass arguments. processor registers are effectively global
<whitequark>
oh yeah, the Charlie on the MTA algorithm
bentley` has quit [Ping timeout: 255 seconds]
<cr1901_modern1>
Interesting read so far. It's a shame I don't remember how I got there (something about "trampolines" and "stack machines") lol
bentley` has joined #m-labs
mon1 has quit [Quit: This computer has gone to sleep]
<cr1901_modern1>
DO you know what the paper refers to as "block compilations" in the Separate Compilation section?
<cr1901_modern1>
bleh, do you know what a block compilation *is* lol
<whitequark>
dunno
<cr1901_modern1>
I just realized that the linked website is the same one with the paper that discusses a simple-to-implement GC algorithm you linked me. Very useful website, even if I disagree with his definition of "Gratuitous waste of bandwidth".
Guest34499 has quit [Quit: This computer has gone to sleep]