[Soot-list] Shimple -> Continuation Passing Style

[Patrick Lam]

J Malcolm wrote:
> Patrick Lam <plam at sable.mcgill.ca> writes:
> 
>> It would not be easy to convert Java into CPS, for two reasons:
>> 1) state gets mutated all over the place; and
> 
> Very true, but the hope is that control flow analysis will boil all that
> out--quite a task.  CPS has side-effects and state just like any other
> language.

Yes, it seems that state might not be the primary problem.

>> 2) typical Java IRs don't contain first-class functions.  People
>> usually only use CPS for functional languages, after all.
>>
>> If you really wanted to convert Java into CPS, then you'd want to
>> start with SSA form.  Soot contains an SSA form, Shimple.  Then you
>> would need to design an intermediate representation with first-class
>> functions; it would include a new family of types for functions.  You
>> could then apply the transformation from SSA into CPS on that
>> intermediate representation.
> 
> The hope was to use Shimple SSA and go from there.  So after I design
> that transformation, I also must design a printer for it?

You'll need to modify Soot in general to support first-class functions.
 While one could use anonymous objects as first-class functions, that
encoding would be quite painful to use.  So you need to hack the innards
of Soot and add the type, lambda, and application in the IR.  Then you
need to write a printer, but that's not the hard part.

>> I'm not sure what you'd have to do about state.  It may not turn out
>> to be a problem after all; I haven't thought enough about it.
> 
> To keep high fidelity to the original Java program, we hope to have CPS
> primitives for things such as malloc, pointer dereferencing, etc.

Java doesn't contain pointer dereferencing as such; it has field
accesses instead.  It also doesn't quite contain malloc.

You should consult Raja Vallee-Rai's thesis on Soot in general as well
as Navindra Umanee's thesis on Shimple.  They are both available at:

http://www.sable.mcgill.ca/publications/thesis/

> Any tips on how would I go about starting to design an IR?  It isn't
> very clear to me how to transform from Shimple.  Any source you'd
> suggest looking through?

Take a look at the soot.shimple package in the Soot code.  That gives
you an idea of what you'd have to do to implement your IR.  Then the
ShimpleTransformer converts methods from Jimple to Shimple; you'd want
to do something similar.

Good luck and let us know how things go!

pat