Scale is an easily modified compiler written in Java.

See:
Description

Packages

scale.alias	Provides alias analysis.
scale.alias.shapirohorowitz	Provides alias analysis using the Shapiro-Horowitz algorithm.
scale.alias.steensgaard	Provides alias analysis using Steensgaard's algorithm.
scale.annot	Provides a means of attaching annotations to nodes in the Clef AST and Scribble CFG.
scale.backend	Generates assembly language output from the CFG representation of a program.
scale.backend.alpha	Generates assembly language output for the Compaq Alpha® processor from the Scale CFG.
scale.backend.mips	Generates assembly language output for the SGI Mips® processor from the Scale CFG.
scale.backend.ppc	Generates assembly language output for the PowerPC® processor from the Scale CFG.
scale.backend.sparc	Generates assembly language output for the Sun Sparc® processor from the Scale CFG.
scale.backend.trips2	The Trips backend for the Scale compiler generates Trips Intermediate Language (TIL) files for the Trips processor from the Scale CFG.
scale.backend.x86
scale.backend.xyz	This package provides templates that can be used to create a code generator for a different architecture.
scale.callGraph	Provides the main container class for a compilation unit.
scale.clef	Provides for the Clef Abstract Syntax Tree (AST) form used to represent the source language program as closely as possible.
scale.clef.decl	Provides for describing user program declataions such as variables and procedures.
scale.clef.expr	Provides for describing expressions in the Clef AST.
scale.clef.stmt	Provides for representing source language statements in the Clef AST.
scale.clef.symtab	Implements a symbol table for use in constructing the Clef AST.
scale.clef.type	Provides for describing the types of expressions and variables.
scale.clef2scribble	Converts a Clef AST to a Scribble CFG.
scale.common	Provides various base & "helper" classes.
scale.frontend	This package contains the separate parsers for each language that Scale can compile.
scale.frontend.c	This poackage contains the parser for the C language.
scale.frontend.fortran	This poackage contains the parser for the Fortran language.
scale.j2s	Generates a Scribble CFG from a Java® bytecode file.
scale.jcr	Reads Java® bytecode files.
scale.score	This package implements an internal representation of source programs using a control flow graph (CFG) called Scribble.
scale.score.analyses	Performs alias analysis on the CFG.
scale.score.chords	Represents nodes in the CFG.
scale.score.dependence	Provides dependence testing of array references in the CFG.
scale.score.dependence.banerjee	Performs dependence testing using bannerjee's algorithm.
scale.score.dependence.omega	Performs the dependence testing using the Omega test from the omega library.
scale.score.dependence.omega.omegaLib	Implements the Omega Library in Java®.
scale.score.expr	Represents expressions in the CFG.
scale.score.pp	This poackage contains the path profiler logic.
scale.score.pred	Provides various CFG spanning utilities.
scale.score.trans	This package provides various optimizations that operate on the CFG.
scale.test	This package contains the main class of the Scale compiler and other utility programs.
scale.visual	Creates graphical displays of the Scale internal structures.

Scale is an easily modified compiler written in Java. A more complete description is available at the University of Massachusetts Scale web site. The top-level class is the Scale class which provides the top-level control.

Scale is composed of several parts roughly corresponding to the following steps:

1. Parsing
2. Conversion to the Control Flow Graph
3. Alias Analysis Alias Analysis
4. Conversion to Static Single Assignment Form
5. Optimizing the CFG
6. Code Generation

These steps are controlled by the Scale class.

Parsing

Scale uses parsers written in Java to parse C and Fortran programs. These parsers create an abstract syntax tree (AST) representation of the source module which we called Clef. The AST is a high level representation with very little lowering of the original program structures.

Clef AST To C

A Scale Clef AST may be converted into a C program using Clef2C. This is used primarily for debugging the Scale compiler.

Conversion to the Control Flow Graph

After a Clef AST has been constructed and analysed, a Scribble CFG is constructed for each routine in the program. Part of this conversion includes:

• dead code elimination
• lowering of high level structures such as subscript expressions
• converting implicit loops to explicit loops
• converting irreducible graphs to reducible graphs

Scribble CFG To C

Scale can transform the Scribble CFG into a C program using Scribble2C. This transformation is used for testing the compiler. It provides a way of validating the compiler and has been used to instrument programs.

Optimizing the CFG

Scale performs the following optimizations optimizations on the SSA form of the Scribble CFG:

• Sparse Conditional Constant Propagation
• Partial Redundancy Elimination
• Copy Propagation
• Value Numbering
• Loop Invariant Code Motion
• Inlining
• Loop Un-rolling

Code Generation

Scale can transform the Scribble CFG into a machine instructions for the Alpha and Sparc® V8 microprocessor chip. A backend backend for Mips chips is being developed. Backends for additional microprocessors can be added without modifying the Scale compiler.

The backend is composed of machine dependent and machine independent parts. It uses object-oriented concepts to separate the parts. For example, the register allocator is machine independent. It can be easily replaced by a different register allocator and utilized by all the machine code generators. To do this, the concept of an instruction is machine independent and has a specified set of attributes. Machine specific instructions are then derived from this basic concept.

Other Scale related documents

• Coding Style Used in Scale
• Environmental Variables Used in Scale
• Inlining in Scale