Simplicissimus

For abstract data types (ADTs) there are many potential optimizations of code that current compilers are unable to perform. These optimizations either depend on the functional specification of the computational task performed through an ADT or on the semantics of the objects defined. In either case the abstract properties on which optimizations would have to be based cannot be automatically inferred by the compiler. In the Simplicissimus project our aim is to address this level-of-abstraction barrier by showing how a compiler can be organized so that it can make use of semantic information about an ADT at its natural abstract level.

Keywords: open compilation, concepts, generic programming, library design

Design Documents

Overview and architecture

Title:User-extensible Simplification---Type-based Optimizer Generators
Abstract: In this paper our aim is to address this level-of-abstraction barrier by showing how a compiler can be organized so that it can make use of semantic information about an ADT at its natural abstract level, before type lowering, inlining, or other traditional compiler steps obliterate the chance. We present an extended case study of one component of a C++ compiler, the simplifier, discuss the design decisions of a new simplifier (simplifier generator) and its implementation in C++; and give performance measurements. The new simplifier is connected to the Gnu C++ compiler and currently performs optimizations at very high level in the front end. When tested with the Matrix Template Library, a library already highly fine-tuned by hand, we achieved run-time improvements of up to six percent.
Download: [Copyright:Springer Verlag] [pdf]
Reference:

@InProceedings{SGM+00,
  author    = "Schupp, Sibylle and Gregor, Douglas P. and Musser, David R. and Liu, Shin-Ming",
  title     = "User-extensible Simplification---Type-based Optimizer Generators", 
  booktitle = "International Conference on Compiler Construction",
  series    = "Lecture Notes in Computer Science",
  editor    = "Reinhard Wilhelm",
  year      =  2001 
}

Title:Library Transformations
Abstract: While software methodology encourages the use of libraries and advocates architectures of layered libraries, in practice the composition of libraries is not always seamless and the combination of two well-designed libraries not necessarily well designed, since it could result in suboptimal call sequences, lost functionality, or avoidable overhead. In this paper we introduce Simplicissimus, a framework for rewrite-based source code transformations, that allows for code replacement in a systematic and safe manner. We discuss the design and implementation of the framework and illustrate its functionality with applications in several areas. Simplicissimus is integrated into the Gnu C++ compiler.
Download: send email to one of the authors (copyright restrictions)
Reference:

@InProceedings{SGM+00b,
  author    = "Schupp, Sibylle and Gregor, Douglas P. and Musser, David R. and Liu, Shin-Ming",
  title     = "Library Transformations", 
  booktitle = "Proc. IEEE Internat. Conf. Source Code Analysis and Manipulation, Florence 2001",
  pages    = "109-121",
  editor    = "Mark Hamann",
  year      =  2001 
}

Title: Design Patterns for Library Optimizations
Abstract: We apply the notion of design patterns to optimizations performed by designers of software libraries, focusing especially on object-oriented numerical libraries. We formalize three design patterns that we have abstracted from many existing libraries and discuss the role of these formalizations as a tool for guiding compiler optimizers to operate at a very high level that would otherwise be left unoptimized. Finally, we discuss the implemetation of a design pattern-based compiler optimizer for \Cpp\ abstract data types.
Download: send email to one of the authors (copyright restrictions)
Reference:

@InProceedings{GSM00b,
  author    = "Gregor, Douglas P. and Schupp, Sibylle and Musser, David R.",
  title     = "Design Patterns for Library Optimizations", 
  booktitle = "Proc. International Conf. on Parallel/High-Performance Object-Oriented Scientific Computing (POOSC'01) Tampa, FL, 2001",
  series    = "",
  editor    = "K. Davis, J.Strieglitz ",
  year      =  to appear 
}

Concept implementation

Title:Algebraic Concepts Represented in C++
Abstract: In this report we provide the definition of fundamental algebraic concepts in C++, from semigroups to commutative fields. Presented as a sequence of subsequent refinements, we formally specify each concept in the concept description language Tecton, define its representation in C++ and illustrate it with C++ types.
Download:[pdf]
Reference:

@TechReport{SGM00b,
  author =       "Schupp, Sibylle and Gregor, Douglas P. and Musser, David R.",
  title =        "Algebraic concepts represented in {C}++", 
  institution =  "Rensselaer Polytechnic Institute",
  year =          2000,
  type =         "Technical Report",
  number =       "TR-00-8"
}

Intermediate Representation

Title: Simplicissimus Internal Representation
Download: [pdf] [dvi]
Abstract: Simplicissimus performs compile-time simplifications without direct compiler-level intervention, requiring an internal representation that can be processed using template metaprogramming techniques. We employ a purely type-based form of expression templates as our internal representation, which allows arbitrary transformations using the Turing-complete language of template metaprogramming.

Presentations

Title:Programming and Compiling with Concepts
Where:New England Programming Languages and Systems (NEPLS) Meeting, Brown University, Rhode Island, Dec. 2000.
Download: [html]

Title:A Framework for Self-Optimizing Libraries
Where: Colloquium, Univ. Notre Dame, Indiana, Feb 2001.
Download: [html]

Title:Simplicissimus: An Extensible Type-Based Optimizer Generator
Where: Seminar RPI, March 2001.
Download: [ppt] [html]

Title:User-defined Simplification: Type-Based Optimizer Generators
Where:Int. Conf. Compiler Construction (CC), Genova, Italy, April 2001
Download: [sdd] [ppt] [html]

Title:From Compilation to Software Engineering
Where:April 2001
Download: [sdd] [ppt] [html]

Title:Design Patterns for Library Optimization
Where:Parallel/Object-Oriented High Performance Computing (POOSC'01), Tampa, FL, October 2001
Download: [ppt] [html]

Title:Library Transformations
Where:Source Code Analysis and Manipulation (SCAM'01), Florence, Italy, November 2001
Download: [ppt] [html]

The Type Description Language (TDL)

TDL is a small language, syntactically similar to a subset of C++, that allows users to provide the required semantic information about their data types in a compact way. A filter program then expands the information to the format Simplicissimus expects.

Design document [.dvi | .pdf]
Manpages:
- [tdl.1]
- [tdl.5]

People

Current members:

Students: Doug Gregor, Eric Caraszi, Luke Hodorowicz
Faculty: Sibylle Schupp, Dave Musser

External member:

Shin-Ming Liu (Hewlett-Packard; prior: SGI)

Past member:

Brad King

Acknowledgments and History

Simplicissimus is supported in part by Silicon Graphics, Inc., Mountain View, California, and by the National Science Foundation under Grant No. 0131354. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
We thank Sun Chan, Alex Stepanov, and Bolek Syzmanski for initiating the collaboration between SGI and RPI; Sun was also directly involved in the first stages of the project. Raymond Lo and Shin-Ming Liu were the ones who suggested to focus on simplification. Fred Chow contributed to early discussions on higher type optimization.