-
Notifications
You must be signed in to change notification settings - Fork 26
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Nim goto intermediate representation (GIRN) #516
Comments
It totally sounds like the n-word, what about NIR ?. 🤔 It will be like a file written to disk or sqlite or just an object in memory?.
So it has to convert |
Yes. |
This comment was marked as resolved.
This comment was marked as resolved.
This comment was marked as resolved.
This comment was marked as resolved.
This comment was marked as resolved.
This comment was marked as resolved.
This comment was marked as resolved.
This comment was marked as resolved.
This comment was marked as resolved.
This comment was marked as resolved.
This comment was marked as resolved.
This comment was marked as resolved.
This comment was marked as resolved.
This comment was marked as resolved.
This comment was marked as resolved.
This comment was marked as resolved.
Given |
That's already covered via |
Exceptions in llvm are modeled by making function call act as a conditional, essentially, with two return points, pretty much like an if statement: one for the normal case and one for the exceptional case - modelling it this way is similar to the boolean "if err" after each function call, but I suspect dedicating a call type (llvm calls it One side effect of this strategy is that
translations like these lead to information loss - while some of that information can be recovered with analysis, such analysis slows down the compiler and still sometimes recreates imperfect information - this is something to consider in general: the semantics, and in particular the constraints, of the language offer opportunities that easily get lost in translation ("this is a copy-on-write construct, so read-only copies are cheap") - we can mitigate this to some extent, but like the try/finally most clearly shows, there will be other cases that are more subtle. |
That's one thing I wanted to avoid, yes, but the question remains how to model it so that it can easily be recovered for JS/C++ codegen. |
So this wouldn't be as simple as having One question I had -- does this give more opportunities to do static analysis or would that primarily remain in the AST level? P.S. thanks for the name change. It's ridiculous but just avoids a whole potential can of worms given things in the USA, and was like the second thing that came to mind. |
Maybe it works with more special kinds of labels: try:
f(a)
finally:
echo "done"
becomes (roughly): TryLabel Lunused
f(a)
case raised
of true: goto L1
FinallyLabel L1
echo "done"
goto ProcEnd
label ProcEnd |
That seems plausible? It'd at least keep the information in the IR. Though, would it require backends to have to handle the TryLabel, FinallyLabel types or would they just be metadata? |
The backends need to handle them but it's a weird question, they exist for the backends. |
speaking of labels, LLVM has a similar mechanism (IR metadata) which basically allows attaching any kind of metadata to any IR node - it is used for transporting pass-specific metadata to later stages, for example type information to the type-based alias analysis pass - language frontends that are statically typed can "opt in" to generate the type data - similarly, extended control-flow information or "known ranges of values" could be propagated across passes which would alleviate the need to recover them via costly analysis but still allow analysis to enhance the IR along the way. Having a "generic" metadata passing capability is something
Why only "requested"? TBAA is a good example: if you're compiling without optimizations, you don't want to waste time on generating and storing type information which later will be ignored. |
I've been following the OCaml Effect handler's for a while and something about GIRN & goto's tickles my brain as having possible overlap. Perhaps it's just the idea that with the OCaml style effects non-local control flow, exceptions, async, et al are just instances of the same underlying mechanism. Would there be a way to do something similar with the goto's and perhaps a set of metadata for non-local jumps? It might be possible to re-use it for analyzing closure iterator's used for async as well. Perhaps not for runtime composable effects, but as an underlying coherent schema for non-local control? |
I've read the paper and it doesn't really apply. It uses a new runtime and a type (or rather effect) system extension. GIRN is much simpler (to implement). GIRN is also not a CPS representation as for that you need the notion of a parametrized goto instruction like |
Ah makes sense that GIRN wouldn't encode the CPS-level representation. Just more of a hopeful thought than anything too serious -- though it was interesting to consider how CSP-level info could be used to provide non-exception effect handlers for handling things like overflows. On another note, it'd be interesting how the Also, it's completely outside of my current wheelhouse so I'll let y'all get back to practical compiler work. :-) |
Note: don't mix CPS (continuation-passing style) and CSP (communicating sequential processes) |
Eh, thanks I'm guilty -- fixed my post. |
NIR is GIRN that was NGIR 🐈⬛ ? |
Abstract
I outline a new IR for the Nim compiler that aims to reduce the compiler's overall complexity.
Motivation
Nim's IR is based on its AST: While the AST served us well in the past, it's now clear that many of Nim's features like "definite assignment analysis", "nil checking" or its "move analyser" would be easier with a different program representation. GIRN is that different representation.
Description
I called it the "Goto intermediate representation for Nim (GIRN)". The type system is left untouched and everything is strictly typed. GIRN focuses on a control flow abstraction. Function calls can remain nested. Compared to the AST GIRN contains these major changes:
A proc body is a single list of instructions and control flow is mapped to labels and
goto
. Thegoto
instruction is designed/handicapped to keep the control flow graphs reducible so that no complex fixpoint algorithms are required.Additional computed information is stored alongside the instructions:
kill x
. Indicates that the scope ofx
has ended and thatx
will not be used afterwards.assume cond
. At this point we know thatcond
holds.require cond
. At this point we need to prove thatcond
holds.assumeHasValue x
. After this pointx
will have a value (but it's not specified which one).goto loopLabel
are distinct from labels which are the targets of forward jumps.case
statements, noif
statements. A backend can easily convert a case statement that only has one or two branches into anif
statement.GIRN has the following properties:
The JS backend would benefit from reliable frontend inlining and once we have it we can properly distinguish between
.inline
which should bealways inline
and.hot
and.cold
procs.Code Examples
The examples here focus on the "move analyser". The move analyser does both control flow and data flow analysis.
The data flow aspect needs
assumeHasValue
as a summary instruction in order to be effective:Loops are interesting: If the loop "comes after" the definition of the variable it is an "inner loop" and we have to watch out:
Is translated into:
It is reasonably easy to see that
use x
is not the last use.Compare that with:
Which is translated to:
Again, it is easy to see what is really going on.
kill
instructions model the scopes effectively and also help with destructor injections.Backwards Compatibility
There are no incompatibilities as it only affects the passes after macro expansions.
Open problem
How to model
try finally
so that it can still be translated totry
for the JavaScript and C++ backends. Aside from that exceptions are simple to model via an expliciton error: goto errorHandler
instruction after a function call that can throw.The text was updated successfully, but these errors were encountered: