Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Student project suggestions from industry (fronted by Alan Mycroft)
Computer Laboratory > Alan Mycroft > Teaching > Student project suggestions from industry (fronted by Alan Mycroft)

Note

Industrially-suggested projects are, in general, not as carefully honed as those suggested by members of CL staff. However, they can offer many possibilities to demonstrate excellence and maybe even a job or research contact after your degree. Based on these considerations, you should not consider such a project unless you were in the top half of the class list for CST Part 1B or equivalent.

The main issue to discuss with your Director of Studies is supervision arrangements. While the industrial contact may be willing to give specialist supervisions on the fine detail, you will need to convince your director of studies that there are no supervisory gaps by either periodic discussion with your DofS convincing her/him that everything is going OK, or by an additional "programming style" type supervisor.

To avoid external people getting swamped with email, it would be help if you would cc: such requests to me, and also to respect any statements below such as "project full for this year".

Contents

Projects

Converting C-- to Continuation-Passing Style (CPS)

  • Originator: Simon Peyton Jones, Microsoft Research, (simonpj@microsoft.com)
  • Lab Contact: Alan Mycroft
  • Special Resources: None
CPS conversion means translating a functional program so that it never returns, instead always calling another function representing the ``rest of the program''. CPS form enables interesting approaches to compilation (see for example Appel's book "Compiling with Continuations'').

Simon Peyton Jones writes: "C-- is an compiler intermediate language, whose purpose is to encapsulate a retargetable code generator. (More details at http://cminusminus.org.)

"C-- supports procedures, much in the same way that C does, and the C-- compiler is responsible for stack layout decisions. One possible way to implement C-- is to compile it to C; and a good way to do that is in two steps: first, a C-- to C-- transformation (CPS conversion) that makes the stack explicit, and yields a C-- program that never calls a procedure; and second, a simple syntax conversion to C.

"I have a particular application in mind -- the Glasgow Haskell Compiler. GHC's current code generator generates C-- internally, already in CPS-converted form. As a result, the code generator is pretty complicated.

"I'd like to factor it into two: a code generate that generates ordinary C-- (with full procedure calls), and a CPS converter. The former is GHC-specific, but the latter is quite generic. Then we could generate C by composing the two together, or instead just run the first part and emit C-- to a full-blown C-- compiler.

"The project is to perform CPS conversion on C--. Norman Ramsey and I have throught through many of the issues involved. It is far from a trivial task, but is not rocket science. I keep not getting around to doing it. It would be a good project for a (rather good) undergraduate.

"The easiest way to implement it (and the most useful to me) would be in Haskell, because all the data types already exist in GHC. My guess is that a successful project would yield a publishable paper as well as a useful artefact."

XAP4 Post-Link Analyzer/Optimizer

A post-link optimizer takes a whole program (i.e., application plus libraries) after the linking stage and applies global analyses and transformations on it. The advantages of working on the entire program is that even modest optimizations which may not be worthwhile when applied to small sections of program can often lead to significant improvements in code size when applied globally.

The XAP4, a new 16-bit RISC-like embedded processor developed by Cambridge Consultants Ltd (CCL), is targeted at small-memory deeply-embedded systems. While the use of GCC leads to quite good optimization of application code, the extent of optimization is limited to a per-module basis. Whole-program optimization is therefore a very attractive proposition.

The aim of this project is to produce a tool which shows that post-link optimization of XAP4 programs is worthwhile. This could be achieved through analysis alone, producing a report including call graphs, code metrics, estimated code profiles (based only on static analysis), etc., or actually transforming the program to produce an output binary image that is measurably smaller. Example optimizations include global dead code elimination ("dead stripping"), basic block merging, and procedural abstraction.

An example of a commercial product, for ideas and inspiration, is AbsInt's Post Pass Optimizer.

See here for details about xIDE and earlier processors (the XAP3 is the closest to the XAP4).


© 2005 University of Cambridge Computer Laboratory
Please send any comments to Alan Mycroft
Page last updated on 24-Sep-2005 at 13:00 by Alan Mycroft