A Catalog of Research Compiler Infrastructures and Tools

WALA is a framework for static analysis of Java bytecode. From the web page:

The T. J. Watson Libraries for Analysis (WALA) provide static analysis capabilities for Java bytecode and related languages. The system is licensed under the Eclipse Public License, which has been approved by the OSI (Open Source Initiative) as a fully certified open source license. The initial WALA infrastructure was independently developed as part of the DOMO research project at the IBM T.J. Watson Research Center. In 2006, IBM donated the software to the community.

WALA features include:

• Java type system and class hierarchy analysis
• Source language framework supporting Java and JavaScript
• Interprocedural dataflow analysis (RHS solver)
• Context-sensitive tabulation-based slicer
• String analysis based on context-free languages
• Pointer analysis and call graph construction
• SSA-based register-transfer language IR
• General framework for iterative dataflow
• Significant support for J2EE semantics
• General analysis utilities and data structures

JastAdd is a compiler-compiler system based on attribute grammars. It is designed to enable adding new features to a compiler by adding modules to a specification. From the web site:

JastAdd is an open source Java-based compiler compiler system. It is designed to support high-level extensible implementation of compilers and related tools like analyzers, transformation tools, etc.

bddbddb is a BDD-based implementation of Datalog; it is ideal for implementing scalable program analyses.

The APT group at Manchester have released PearColator, which is a dynamic binary translator based on the Jikes RVM and licensed under the IBM CPL. PearColator converts PPC binaries to the Jikes IR, performs optimizations, and recompiles them for the host architecture. As a result, all of the optimizations supported by Jikes are available. PearColator is implemented in Java.

Thanks to Matt Allen for a link to LaTTe: A Fast and Efficient Java VM Just-in-Time Compiler from Seoul National University. According to the website, LaTTe offers:

• Fast and effective JIT translation with:
  • efficient register mapping and allocation (i.e., consistently
    taking one or two seconds for SPECjvm98 which runs 40-70 seconds with
    LaTTe)

  • traditional optimizations (e.g., common subexpression elimination
    and loop invariant code motion)

  • object oriented optimizations (e.g., customization and limited specialization)
• A limited framework for adaptive compilation, which is currently
  based on method run counts.

• A reasonably fast bytecode interpreter, intended to be used with
  the adaptive compilation framework.

• Lightweight monitors.
• On-demand translation of exception handlers.
• A fast non-incremental garbage collector.

The Java Intermediate Language is an XML-based intermediate representation for Java source code. It appears to have been used most for visualization.

Polyglot is a framework that provides a front-end for the Java language and a means to develop extensions to Java. It has been used to develop variants of Java that support static information flow control, parameterized types, and pattern matching. It is also used by the source-to-bytecode compiler in the newest release of the Soot framework.

Thanks to Ira Baxter for a pointer to the DMS Software Reengineering Toolkit. According to the web page,

The DMS Software Reengineering Toolkit is a set of tools for automating customized source program analysis, modification or translation or generation of software systems, containing arbitrary mixtures of languages (”domains”). The term “software” for DMS is very broad and covers any formal notation, including programming languages, markup languages, hardware description languages, design notations, data descriptions, etc.

Predefined frontends exist for many programming, hardware, and markup languages, including Ada, C, C++, C#, Cobol, Fortran, HTML, IDL, Java, Mathematica, Matlab, Motorola 68k assembly, Pascal, PHP, Verilog, VHDL, Visual Basic, and XML; it is apparently also possible to define new frontends.

Thanks to Mykola Rabchevskiy for a pointer to Coco/R, a scanner/parser generator from the University of Linz. It generates source for C# and Java; there are also (apparently unsupported) versions that generate code for Oberon, Pascal, Modula-2, C, C++, Delphi, and Unicon. Coco/R generates recursive descent parsers and scanners from an attributed grammar and is distributed under the GNU GPL.

SableVM is a free/Free spec-compliant and extensible JVM. It includes a JIT for PPC, SPARC and x86, but runs on several more architectures. It supports several different interpreter dispatch models (switched, threaded, inlined) and has an efficient runtime system. It is implemented in C with extensive use of M4 macros.

The SableCC parser generator is a tool for compiler developers who use Java. From the web page:

SableCC is an object-oriented framework that generates compilers (and interpreters) in the Java programming language. This framework is based on two fundamental design decisions. Firstly, the framework uses object-oriented techniques to automatically build a strictly typed abstract syntax tree. Secondly, the framework generates tree-walker classes using an extended version of the visitor design pattern which enables the implementation of actions on the nodes of the abstract syntax tree using inheritance. These two design decisions lead to a tool that supports a shorter development cycle for constructing compilers.

treecc is a tool for building programs that operate on trees (as such, it does not fit neatly into the two “Tools:” categories I have placed it in). It will generate code for C, C++, C#, and Java, and is notable for its aspect-oriented approach to compiler construction.

The Edison Design Group makes a standards-compliant C++ front end, as well as Java and Fortran front-ends. While their primary market is compiler and program transformation tool vendors, apparently they are willing to license these to university researchers on a case-by-case basis. (per their FAQ.)

ERCO is a Java-to-native compiler developed by the Laboratory for Software Technologies at ETH Zürich. From the web site:

The ETH Research COmpiler (ERCO) is a research Java byte-code to native compiler that is used in several projects in our group as for teaching in advanced compiler classes. We translate the Java bytecode to an internal representation in static single assignment form on which we perform several analyses and some optimizations. The backend generates native object file for the Intel IA-32 platform which are then linked to the Java runtime system provided by the GCJ project.

Judging from the comments on the web page, ERCO is at a fairly early stage of development as of this writing.

The venerable SUIF system is “a free infrastructure designed to support collaborative research in optimizing and parallelizing compilers.” It is fairly straightforward to write your own passes on the SUIF IR in C++. Frontends exist for C, C++, Fortran, and Java, and SUIF can interoperate with Zephyr; there are MIPS and C backends.

The ANTLR Parser Generator and Translator Generator is a well-regarded tool to aid in generating compiler frontends in Java, C# or C++. From the web page:

ANother Tool for Language Recognition, (formerly PCCTS) is a language tool that provides a framework for constructing recognizers, compilers, and translators from grammatical descriptions containing Java, C#, or C++ actions. ANTLR provides excellent support for tree construction, tree walking, and translation.

Thanks to Mulhern for the suggestion.

The Byte Code Engineering Library (BCEL) is a Java library enabling creation, analysis, and modification of Java .class files. According to its website, it “is already being used successfully in several projects such as compilers, optimizers, obsfuscators, code generators and analysis tools.” BCEL also includes a bytecode verifier that is designed to give more useful feedback about unverifiable bytecode than would be output by the JVM verifier.

Thanks to Mulhern for the suggestion.

Manoj Plakal points out that I have not mentioned GCC. GCC, of course, has frontends for many languages, including C, C++, Objective-C, Java, Fortran, Pascal, and Ada; and backends for nearly every computer architecture ever created as well as a great many that weren’t. It has a reputation for being difficult to use for research, but that hasn’t stopped many people from doing so.

Feel free to TrackBack this entry if you’re using GCC for programming languages research, or if you have tips for using GCC for programming languages research.

Scale is a compiler from the ALI group at Massachusetts. Scale is a modular compiler that provides frontends for C, Java, and Fortran, and a backend that produces C. Scale supports alias analysis (including implementations of Shapiro-Horwitz, Stensgaard, and a simple algorithm), SSA, and a battery of scalar optimizations (redundancy elimination, value numbering, etc.). Scale uses an IR called Scribble and supports annotating the IR with information for additional passes. It is implemented in Java.

The Open Runtime Platform is a modular virtual machine infrastructure, enabling creation of JIT and GC components that are not tightly-coupled and can be swapped out. It is implemented in C and C++ and runs on IA-32 Linux and Windows. Papers about the JIT and GC strategies that it includes are available from Intel.

Zephyr Compiler Infrastructure provides a means to define an intermediate representation and write passes on it in several languages; it also provides a hardware description language to power a code-generator generator. From the web site:

If you describe your intermediate forms using Zephyr’s Abstract Syntax Description Language (ASDL), we can generate data-structure definitions in C, C++, Java, Standard ML, and Haskell. Your IR can be serialized on disk and freely exchanged among compiler passes written in these languages…

[Zephyr] generate[s] the machine-dependent parts from descriptions of instructions’ semantics, of binary representations, or of other properties. Zephyr’s Computer Systems Description Languages (CSDL) let you describe as much or as little as you need for your application.

Zephyr also seems to provide a reasonable set of built-in optimizations.

Jikes RVM (née Jalapeno) is a production-quality virtual machine for Java, enabling research in virtual machine technology, just-in-time compilation, memory management, and more. From the web page:

Jikes RVM runs on Linux®/IA-32, AIX?/PowerPC?, OS X/PowerPC, and Linux/PowerPC platforms and advances the state-of-the-art of virtual machine technologies for dynamic compilation, adaptive optimization, garbage collection, thread scheduling, and synchronization. A distinguishing characteristic of Jikes RVM is that it is implemented in the Java? programming language and is self-hosted i.e., its Java code runs on itself without requiring a second virtual machine. Most other virtual machines for the Java platform are written in native code (typically, C or C++). A Java implementation provides ease of portability, and a seamless integration of virtual machine and application resources such as objects, threads, and operating-system interfaces.

The FLEX compiler infrastructure transforms Java programs and is implemented in Java. It specifically targets embedded applications and has MIPS, StrongARM, and C backends. FLEX supports region-based memory allocation, multiple thread models, and optimization for space.

Joeq is a virtual machine that can execute, analyze, and optimize Java class files, x86 ELF object (.o) files, and files in the SUIF intermediate representation. It is implemented in Java, and runs both in a hosted mode (on another JVM) and self-hosted (compiling itself).

Soot is a compiler infrastructure and framework for Java bytecodes and Java source code, implemented in Java. It supplies several intermediate representations, including:

• “streamlined” bytecode,
• a typed three-address IR,
• a typed three-address IR with SSA,
• an “aggregated” version of the three-address IR.

Many analyses and optimizations are provided, including several high-quality whole-program pointer analyses, devirtualization of monomorphic call sites, and most standard intraprocedural optimizations. Also enables decompilation of bytecodes to Java source.

Very easy to extend. I use it in my research.