[Soot-list] Shimple -> Continuation Passing Style

[J Malcolm]

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)
>      |
>      V
> in-memory toy SSA IR
>      |
>      | (your SSA->CPS compiler)
>      |
>      V
> in-memory toy CPS IR
>      |
>      | (SableCC-generated printer)
>      |
>      V
> 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
already.

Thanks so much for bouncing ideas around like this.

-jm