Jozef Kruger. Specification Of Loop Optimizations In Stratego. Improving the AutoBayes System. Master's thesis. Institute of Information and Computing Sciences, Utrecht University, The Netherlands. November 2003. (pdf)

Abstract

Manually writing programs that perform statistic data analysis is an arduous and error prone task. In order to automatically generate such programs the AutoBayes system has been developed at NASA Ames, California. This system takes an analysis description and generates fully documented C/C++ code from it, this process is called program synthesis. In this process of generating code, no optimizations are performed. This project extends the AutoBayes system with an optimizer that especially aims at loop optimizations.

XBayes is the (loop-)optimizer described in this thesis and it performs a number of optimizations: loop fusion, sum simplification, invariant code elimination, common subexpression elimination with alpha equality and constant propagation. A large part of the project consists of dependence analysis; data dependences in particular. This is the basis for the loop fusion algorithm. The loop fusion algorithm we will present in this thesis has been based upon Typed Fusion, but is completely rewritten in order to obtain a rewriting algorithm instead of an imperative one.

The system transforms abstract syntax trees (ASTs), which are a high level representation of programs generated by the AutoBayes system. One of the benifits of this high level representation is that more information (or structure) about the program is available. An example of this are summation constructs which are transformed into loops when C code is generated. With these constructs, more specific transformations can be done (sum simplification for example).

The optimizer has been implemented in the Stratego language, a language based on the paradigm of rewriting rules and strategies. The AutoBayes system was written in Prolog, therefore a bridge between the two languages has been built as well. AutoBayes makes heavy use of attributes to assert conditions and generate comments throughout its synthesis phase, the optimizations described in this thesis also add comments whenever a transformation has been done.