[Soot-list] Shimple -> Continuation Passing Style
malcolm at ece.gatech.edu
Mon Jan 29 23:35:35 EST 2007
Chris Pickett <chris.pickett at mail.mcgill.ca> writes:
> No, forget about Java, your input files would be a textual
> representation of the toy SSA IR.
I'm thinking that, since toy SSA to CPS is seemingly trivial (Kelsey
1995 and Appel's texts "Modern Compiler Implementation"), I can go
directly to getting that basic framework up in Soot. The toy SSA->CPS
algorithm is really quite simple.
> > It would be instructive to then go from there, but maybe a subset of
> > Shimple to CFA is easier?
> I think you mean CPS (unless CFA is an acronym I don't know), but
> nevertheless, yes, use a (very) stripped down Shimple as the toy SSA
> IR. Or not even, just some basic SSA form.
That sounds like the way to go.
> The idea being to play around and figure out at a high level what
> needs to be done, before you begin worrying about all the
> Java-specific stuff.
Any specific Java stuff you have in mind that I will hit?
> example.toy_ssa (written by you)
> | (SableCC-generated parser)
> in-memory toy SSA IR
> | (your SSA->CPS compiler)
> in-memory toy CPS IR
> | (SableCC-generated printer)
> example.toy_cps (which you manually compare against example.toy_ssa)
Ahh, I see. The SSA->CPS compiler will be a series of switch
statements, basically implementing the denotational semantics in
Kelsey's paper. The algorithm reproduced in Appel's book for his toy
language is less than a full page with its maybe 8 or so cases.
A stripped down Shimple/Java would have the same basic cases. Starting
to compile a list of things that will be tricky, I see method invocation
(virtual, static, etc.) and array access as nontrivial.
The printer is obviously trivial since it can be generated in a nested
fashion with S-expressions.
> Anyway, I honestly don't know if it will be useful, and I haven't read
> any of the related work, but it seems likely that you're going to
> throw away your first attempt, so you might as well plan for it to be
> throwaway from the get go.
That's good advice! I sadly realized that so many times.
Even playing around in Soot I've thrown plenty of toy examples away
Thanks so much for bouncing ideas around like this.
More information about the Soot-list