Skip to topic | Skip to bottom


Home

EelcoVisser
EelcoVisser.SimplifyingTheSimplifierr1.3 - 28 Apr 2005 - 22:53 - Main.wiki

Start of topic | Skip to actions

Moved Permanently

The document has moved here.


Project Description

The simplifier of the GHC performs optimizations by applying a number of small transformation rules iteratively to the abstract syntax tree of a program. The simplifier is implemented as one big Haskell module. The implementation is not modular and is difficult to change. Small changes lead to a big difference in optimization behaviour. It is not possible to make different versions of the simplifier re-using the same basic code. In addition, GHC has introduced user-definable optimization rules that can be specified by the user as pragmas in the program. The design of the simplifier, however, suggests a modular set-up that is based on a number of separate transformation rules that are combined into one transformation. (source: Simon Peyton Jones)

This suggests that the Stratego approach of defining transformations as a set of transformation rules combined with a strategy that applies these rules would be advantageous to the implementation of the simplifier. The goal of this project is to develop a modular implementation of the GHC simplifier in Stratego. The goal is not to just replicate the GHC simplifier, but to explore the possibilities of Stratego in implementing it, possibly leading to a family of simplifiers. The result should be evaluated against the following questions:

  • Correctness
    • Is it possible to replicate the behaviour of the simplier?

  • Is the result a readable specification of simplification?

  • Modularity: Is it possible to
    • Create different configurations or strategies based on the same set of rules
    • Vary the rules used?
    • Vary the command-line options (e.g., inlining heuristics) to simplifier?
    • Add user-defined optimization rules

  • Performance
    • What is complexity of the simplifier?
    • Does it scale up?

Literature

Implementation of optimization in the Glasgow Haskell Compiler

  • Implementation of the simplifier: see the GHC source distribution

Helium compiler

  • Ask Arjan van IJzendoorn

Stratego

  • General Stratego knowledge. See Stratego:StrategoPublications

Implementation of optimizers in Stratego

ATerm Exchange Format

  • Efficient Annotated Terms. M.G.J. van den Brand, H.A. de Jong, P. Klint, and P.A. Olivier. Software - Practice & Experience, 30:259-291, 2000.

Planning

Set up Infrastructure

  • Use the front-end of Arjan van IJzendoorn's Helium compiler
  • Use Daan Leijen's back-end (compiler to byte-code)
  • Make a translation from Core language to ATerm Format
    • Write after front-end
    • Read before back-end

Set up Benchmarks

  • Collect set of programs to optimize
  • Automate the running and measuring of performance figures
  • Also measure compile time

Implement Simplifier

  • Study the implementation of the simplifier in Haskell
  • Implement the rules as separate rewrite rules
  • Define strategies to apply the rules
  • Experiment with different configurations of the simplifier
    • Measure performance of compiled programs and compiler
  • Add additional optimizations

Thesis

  • Discuss related work
  • Describe the design and implementation of the simplifier
  • Evaluate advantages and disadvantages of using Stratego

-- EelcoVisser - 27 Nov 2001



Edit | Attach | Printable | Raw | More topic actions
Revisions: | r1.3 | > | r1.2 | > | r1.1 | Page history | Backlinks
You are here: EelcoVisser > SimplifyingTheSimplifier

to top

Copyright © 2003-2017, Software Engineering Research Group, Delft University of Technology, The Netherlands