15-745 Project: SSA PRE in MLton

MLton [http://mlton.org/] is a high performance whole-program compiler for Standard ML [1]. One of MLton's intermediate representations is a form of static single assignment control flow graphs ["SSA"; 3]. Though much care is taken to transform the functional source language into an efficient form with explicit loops (much like a C or Java compiler might produce), only a few simple optimizations are done on this representation. For instance, loop-invariant expressions are only hoisted via common sub-expression elimination if they happen to be computed in a block that dominates the loop header.

Our project seeks to develop a version of Partial Redundancy Elimination [4] that is appropriate for MLton's modified SSA IL, and implement it in the compiler.

Partial Redundancy Elimination is an optimization that prevents, where possible, the re-computation of an expression along some paths in a program. PRE is general enough to automatically implement loop-invariant code hoisting. PRE appears to be especially beneficial for functional programs, where the class of expressions that may be moved is much richer: in addition to arithmetic and memory loads, we may also move and coalesce projections from tuples, calls to total functions, and even allocations of persistent values.

We know of an algorithm for PRE in SSA, called SSAPRE [2], which we can adapt for this project. MLton's SSA form has some differences that will preclude us from using the algorithm directly. First, it does not use variable "versions;" each SSA variable is named distinctly. This impacts the tracking of expressions that might be redundant with each other -- SSAPRE only considers instructions that use versions of the same variables. Second, MLton's φ-functions are implicit. Instead of φ-functions at the head of each block, blocks that would have φs instead take arguments (the SSA variables that would have been defined), and the incoming edges pass arguments. This design should not impact the algorithm at all, but it will impact the data structures we use to implement it.

The PRE pass will be fairly modular; to evaluate our success, we'll simply compare the output of MLton on its benchmark suite with the pass turned on and off. It will be most interesting to note the run time of the executables produced, but also the code size and compile time impact.

Plan:

week of plan

3/17- Prepare shared CVS repository, make sure we can both build the code (proposal)

3/24- Don't do anything (spring break)

3/31- Both: Understand SSAPRE algorithm, MLton IL, and their common sub-expression elimination pass

4/2- Mostly Brendan: Work out details of changes to SSAPRE algorithm Mostly Tom: Work out details of implementation in MLton

4/9- Both: continue previous work, prepare milestone report (milestone)

4/16- Both: Type in our algorithm

4/21- Both: Fix bugs, benchmark, and report (due)

Milestone:

By the milestone we expect to have completed the detailed design of our algorithm, including the data structures we will use to actually implement it. Essentially, we propose to be in a position where the actual typing and testing remain. (And, of course, the preparation of the final document and poster.)

Literature Search:

[1] The Definition of Standard ML (Revised). Robin Milner, Mads Tofte, Robert Harper, and David MacQueen. MIT Press, Cambridge, Massachusetts, 1997
[2] A New Algorithm for Partial Redundancy Elimination based on SSA Form, Fred C. Chow, Sun Chan, Robert Kennedy, Shin-Ming Liu, Raymond Lo, Peng Tu. SIGPLAN 1997
[3] Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, F. Kenneth Zadeck. TOPLAS 1991
[4] Global Optimization by Suppression of Partial Redundancies, E. Morel and C. Renvoise. CACM 22 1979.

Resources Needed:

The source code to MLton is freely available, and we are in contact with the authors. It compiles only for the X86 architecture, for which both group members happen to have plenty of access.

Getting Started:

We have already begun looking at the source code to other SSA passes in MLton, and developed some very simple test programs that have easy partially-redundant code for PRE to find. We have also read the SSAPRE paper that describes the basic algorithm that ours will be based on. Nothing but ruinous procrastination prevents us from starting immediately.