CPS and optimization

[Peter Keller]

Hello,

I'm implementing varients of the interpreters and compilers from the
book "Lisp In Small Pieces" into Common Lisp.

In order to implement things like catch/throw, block/return-from,
tagbody/go, the book states that explicit continuation management
is needed. In these interpreters, the code which is to be evaluated
gets converted in a direct syntax translation method to a CPS form.

My question is: If CPS is mandatory to implement escapes, then when
doing direct syntax translation into CPS we fixate the execution
order of expressions very early. So how does one perform the usual
optimizations like for block structured languages? The concept of a
basic block is a bit lost in the CPS world.

I know of the correspondance between CPS and SSA forms, is that what I
would apply here? I'd convert the CPS form to SSA basic blocks, perform
the optimization operations upon it, then convert it back to CPS?

Thank you.

-pete

[D Herring]

On 11/09/2010 10:53 PM, Peter Keller wrote:

> I know of the correspondance between CPS and SSA forms, is that what I
> would apply here? I'd convert the CPS form to SSA basic blocks, perform
> the optimization operations upon it, then convert it back to CPS?

Rather each SSA optimization should have an equivalent optimization
for "well behaved" CPS forms. The well-behaved restriction comes from
CPS allowing some things that are not possible in SSA.

[OT] If you do convert to SSA, I'd just throw the code through LLVM.
It seems to me that low-level optimizations (e.g. local scheduling,
opcode selection, and register allocation) are fairly well solved
whereas higher-level optimizations (e.g. profiling-driven inlining,
fast-path generation, and data-structure selection) need more
interaction with the programmer and provide interesting new opportunities.

- Daniel

[Peter Keller]

D Herring <dher...@at.tentpost.dot.com> wrote:
> On 11/09/2010 10:53 PM, Peter Keller wrote:
>
>> I know of the correspondance between CPS and SSA forms, is that what I
>> would apply here? I'd convert the CPS form to SSA basic blocks, perform
>> the optimization operations upon it, then convert it back to CPS?
>
> Rather each SSA optimization should have an equivalent optimization
> for "well behaved" CPS forms. The well-behaved restriction comes from
> CPS allowing some things that are not possible in SSA.

Is there a rosetta stone document which shows the same optimization in SSA
form and well-behaved CPS form? If so, could I get a reference to it?

Thank you.

-pete

[Mark Wooding]

Peter Keller <psi...@cs.wisc.edu> writes:

> In order to implement things like catch/throw, block/return-from,
> tagbody/go, the book states that explicit continuation management
> is needed.

I don't think it's compulsory: some Schemes don't even do a full CPS
transformation. The Python compiler used in CMU CL and SBCL does
represent continuations (the limited ones needed to implement Common
Lisp, anyway) explicitly fairly early; you may find reading the compiler
source interesting.

-- [mdw]

[Pascal J. Bourguignon]

Peter Keller <psi...@cs.wisc.edu> writes:

Indeed. CPS is rather a low level representation. A kind of normalized
form.

For example, both:

(block n1 e1 (block n2 e2 e3))

and:

(block n1 e1 e2 e3)

could have the same representation in CPS (eg. if nobody returns from
n2).

Similarly, order of execution requires fixating only in presence of side
effects, which is best determined by the compiler, and once a set of CPS
segments have been proved without side effects, the compiler can freely
reorder them according only to the data flow dependencies.

--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

[namekuseijin]

On 10 nov, 01:53, Peter Keller <psil...@cs.wisc.edu> wrote:
> My question is: If CPS is mandatory to implement escapes, then when
> doing direct syntax translation into CPS we fixate the execution
> order of expressions very early. So how does one perform the usual
> optimizations like for block structured languages? The concept of a
> basic block is a bit lost in the CPS world.

you're talking about different levels of abstraction here. Blocks in
structured language are indeed equivalent to lexical closures in
Scheme. CPS is equivalent to structureless goto programming: you do
something then go to something else to continue the computations.

[Peter Keller]

So, when you say "the limited ones needed to implement Common Lisp", which
ones are they and for what language features--the ones I mentioned?

-pete