SSA/CPS transformation for JVM languges?
Charles Oliver Nutter
can more easily apply optimizations to it. Currently I'm walking the AST
and gathering what info I can, mostly based on isolated nodes. It seems
that an SSA graph would be easier to inspect, and I'd get more
optimizations almost for free.
My questions are:
* Anyone know of a compiler toolchain for JVM which accepts an SSA
graph, or tools that might help with this process?
* Does this sound like a good idea? Perhaps there's a shared library
possibility here?
- Charlie
Tobias Ivarsson
It doesn't use a traditional flowgraph SSA. Instead I've chosen a representation that's closer to the internal representation in Hotspot, a so called "sea of nodes" SSA. This is because it simplifies instruction scheduling.
I would definetly like to share this with as many of you as possible. But I'm doing heavy refactoring at the moment, and would prefer to wait two-three weeks (after PyCon) with the sharing.
/Tobias
Robert Fischer
library yet. I'd be very interested in working with other people to do SSA work, though.
For the work I've done so far, I've been using Scala, and it's...okay. Calling Scala code from
Java/Groovy requires understanding of the non-obvious compiler mappings in Scala, so once you're in
Scala, it's best to stay there. Also, I'm not sold that the Scala pattern matching is really
gaining me much over polymorphic method calls in this particular case -- and this is coming from a
once-upon-a-time OCaml hacker/evangelist. So redoing what SSA library stuff I've got in raw Java
might be better, at least in terms of garnering contributions.
I'm not particularly interested in a dynamically-typed SSA library since correctness is critical in
the SSA, and if I didn't have the type safety, I'd want to implement it. Although I could be sold
another direction on that point.
I'm also less excited about CPS, since that's going to tend towards optimized code resulting in
non-recursive function tail calls, which I'm trying to avoid until we get a version of the JVM which
can optimize them.
~~ Robert Fischer.
Grails Training http://GroovyMag.com/training
Smokejumper Consulting http://SmokejumperIT.com
Enfranchised Mind Blog http://EnfranchisedMind.com/blog
Check out my book, "Grails Persistence with GORM and GSQL"!
http://www.smokejumperit.com/redirect.html
Robert Fischer
~~ Robert.
James Abley
>
> Want.
>
> ~~ Robert.
>
> Tobias Ivarsson wrote:
>> I have such a compiler framework in my optimizing Jython compiler. I'll
>> have it ready for other people to work with by PyCon, if you are
>> attending this year we can talk about it face to face.
>>
>> It doesn't use a traditional flowgraph SSA. Instead I've chosen a
>> representation that's closer to the internal representation in Hotspot,
>> a so called "sea of nodes" SSA. This is because it simplifies
>> instruction scheduling.
>>
>> I would definetly like to share this with as many of you as possible.
>> But I'm doing heavy refactoring at the moment, and would prefer to wait
>> two-three weeks (after PyCon) with the sharing.
>>
>> /Tobias
Any chance of sneak previews on github / A N Other?
Cheers,
James
Tobias Ivarsson
2009/3/13 Robert Fischer <robert....@smokejumperit.com>:
>
> Want.
I should have written about it earlier, all this encouragement would have been nice a few months ago...
I guess you would like more static typing support than what I have implemented at this point. I haven't had the need yet since Jython is a dynamic language. But that need is approaching rapidly and I have plans scetched out on various pieces of paper for how type annotations are to be added.
It's in a mercurial repo on my personal network at the moment, but I'll commit it to the Jython svn repository at some point next week. I'll make sure to make an announcement here when I do ;)
/Tobias
Robert Fischer
need to keep type definitions around for method calls, but that's about it...
~~ Robert.
Tobias Ivarsson wrote:
>
> On Fri, Mar 13, 2009 at 4:08 PM, James Abley <james...@gmail.com
> <mailto:james...@gmail.com>> wrote:
>
>
> 2009/3/13 Robert Fischer <robert....@smokejumperit.com
Tobias Ivarsson
Isn't the static type verification pretty much done and over with by the time you get to SSA? You
need to keep type definitions around for method calls, but that's about it...
Sorry - my mind was skipping a few steps ahead since it was busy coding at the same time as I wrote that message. If you have type annotations in your source then of course they end up in your SSA through your symbol table. I was thinking about the data-flow analysis I am going to add to do type inference with Jython.
Charles Oliver Nutter
> I have such a compiler framework in my optimizing Jython compiler. I'll
> have it ready for other people to work with by PyCon, if you are
> attending this year we can talk about it face to face.
>
> It doesn't use a traditional flowgraph SSA. Instead I've chosen a
> representation that's closer to the internal representation in Hotspot,
> a so called "sea of nodes" SSA. This is because it simplifies
> instruction scheduling.
>
> I would definetly like to share this with as many of you as possible.
> But I'm doing heavy refactoring at the moment, and would prefer to wait
> two-three weeks (after PyCon) with the sharing.
Tom and I will both be at Pycon, and sticking around for a couple days
of hacking afterward, so that would be a good time to talk about this. I
knew you were working on something similar, and figured I'd start
getting a leg up now on how to do a similar transform for JRuby.
I'll read up on "sea of nodes" SSA as well, so I don't go down the wrong
path.
- Charlie
Charles Oliver Nutter
> I've started down the SSA route for Cornerstone, too. This is why I'm not back to using your BS
> library yet. I'd be very interested in working with other people to do SSA work, though.
Forgive me if I missed it, but what's Cornerstone? I'm intrigued.
> I'm not particularly interested in a dynamically-typed SSA library since correctness is critical in
> the SSA, and if I didn't have the type safety, I'd want to implement it. Although I could be sold
> another direction on that point.
Are you saying you'd rather have the SSA library implemented in Java? I
don't think any of us are against that, and it would definitely be more
generally-applicable.
> I'm also less excited about CPS, since that's going to tend towards optimized code resulting in
> non-recursive function tail calls, which I'm trying to avoid until we get a version of the JVM which
> can optimize them.
I believe TCO has already landed on MLVM, so it's at least on the way.
- Charlie
Charles Oliver Nutter
>
>
> On Fri, Mar 13, 2009 at 4:25 PM, Robert Fischer
> <robert....@smokejumperit.com
>
>
> Isn't the static type verification pretty much done and over with by
> the time you get to SSA? You
> need to keep type definitions around for method calls, but that's
> about it...
>
>
> Sorry - my mind was skipping a few steps ahead since it was busy coding
> at the same time as I wrote that message. If you have type annotations
> in your source then of course they end up in your SSA through your
> symbol table. I was thinking about the data-flow analysis I am going to
> add to do type inference with Jython.
We'll be interested in the same aspects for JRuby, since we currently do
no type profiling/analysis at all and it would be nice to have a simple
way to propagate those types once we start gathering them.
In the interim, though, a fully dynamic SSA would be fine for my
purposes, since I'm mostly looking for flow-control and local var
optimizations.
- Charlie
Charles Oliver Nutter
>> I'm not particularly interested in a dynamically-typed SSA library since correctness is critical in
>> the SSA, and if I didn't have the type safety, I'd want to implement it. Although I could be sold
>> another direction on that point.
>
> Are you saying you'd rather have the SSA library implemented in Java? I
> don't think any of us are against that, and it would definitely be more
> generally-applicable.
Nevermind, I understand what you mean now. Ideally if we eventually
arrived at a static-typed SSA we could just pass "Object" or similar
through and and still have it work, albeit without any cross-call
optimizations.
- Charlie
Robert Fischer
> Robert Fischer wrote:
>> I've started down the SSA route for Cornerstone, too. This is why I'm not back to using your BS
>> library yet. I'd be very interested in working with other people to do SSA work, though.
>
> Forgive me if I missed it, but what's Cornerstone? I'm intrigued.
>
many times about what could/should be done, so I've decided to put some time where my mouth is.
I've been using your BiteScript and watching your Duby stuff as a model, and I'd like to contribute
back to that, too, when I've got a bit more free time: Autobase + work + next book + NFJS + training
+ spring gardening is currently killing me.
>> I'm not particularly interested in a dynamically-typed SSA library since correctness is critical in
>> the SSA, and if I didn't have the type safety, I'd want to implement it. Although I could be sold
>> another direction on that point.
>
> Are you saying you'd rather have the SSA library implemented in Java? I
> don't think any of us are against that, and it would definitely be more
> generally-applicable.
>
I'm saying -- gently -- that my Scala stuff probably isn't worth sharing, and if I were to do it
over again, I'd do it in Java. But I'm also saying I'm willing to be sold on a non-statically typed
language impl given that the alternative is coding Java.
>> I'm also less excited about CPS, since that's going to tend towards optimized code resulting in
>> non-recursive function tail calls, which I'm trying to avoid until we get a version of the JVM which
>> can optimize them.
>
> I believe TCO has already landed on MLVM, so it's at least on the way.
>
I know, and I'm crazy excited. How is that being implemented, BTW? Did they remove the GOTO
restriction, or is there a new byte code to trigger a tail call?
Charles Oliver Nutter
> Charles Oliver Nutter wrote:
>> Robert Fischer wrote:
>>> I've started down the SSA route for Cornerstone, too. This is why I'm not back to using your BS
>>> library yet. I'd be very interested in working with other people to do SSA work, though.
>> Forgive me if I missed it, but what's Cornerstone? I'm intrigued.
>>
> It's an experiment in type systems, expressiveness, and concurrency. I shot my mouth of one too
> many times about what could/should be done, so I've decided to put some time where my mouth is.
> I've been using your BiteScript and watching your Duby stuff as a model, and I'd like to contribute
> back to that, too, when I've got a bit more free time: Autobase + work + next book + NFJS + training
> + spring gardening is currently killing me.
Well, I have dozens of projects on my plate, but I'd like to hear more.
You should post a little description here on jvm-l when you're
comfortable doing so. And don't worry about getting back to
BiteScript...I'll have a 0.1 release out soon since I'm using it for
JRuby's Java type generator (compiler2), which will mark the second
real-world consumer of BiteScript. That should help ferret out issues,
and I'm also planning a mild refactoring soon too.
>>> I'm not particularly interested in a dynamically-typed SSA library since correctness is critical in
>>> the SSA, and if I didn't have the type safety, I'd want to implement it. Although I could be sold
>>> another direction on that point.
>> Are you saying you'd rather have the SSA library implemented in Java? I
>> don't think any of us are against that, and it would definitely be more
>> generally-applicable.
>>
> I'm saying -- gently -- that my Scala stuff probably isn't worth sharing, and if I were to do it
> over again, I'd do it in Java. But I'm also saying I'm willing to be sold on a non-statically typed
> language impl given that the alternative is coding Java.
Ok, gotcha. Java is quite all right by me.
>>> I'm also less excited about CPS, since that's going to tend towards optimized code resulting in
>>> non-recursive function tail calls, which I'm trying to avoid until we get a version of the JVM which
>>> can optimize them.
>> I believe TCO has already landed on MLVM, so it's at least on the way.
>>
> I know, and I'm crazy excited. How is that being implemented, BTW? Did they remove the GOTO
> restriction, or is there a new byte code to trigger a tail call?
I believe it's a new bytecode, or else some other artificial marker.
It's not done automatically.
Of course, once it's there, every compiler on the planet can start
tagging tail calls if they want, so I don't expect the artificial marker
will be a problem.
- Charlie
Tobias Ivarsson
They use the WIDE-opcode before the invoke* bytecode to annotate the instruction as a tail-call.
so WIDE+INVOKE*+RETURN == tailcall.
Charles Oliver Nutter
Ahh, good to know. Nice and simple.
- Charlie