Scale Data Flow Diagram

Click on the above image to go to information about that part of the Scale compiler.

C Parser

Scale has its own Java-based parser that convert directly from C source code to an abstract syntax tree (the Clef AST). The Java-based C parser was built using ANTLR. Dialects supported are standard C, C99, and K&R C.

This parser also implements many gcc specific extensions. Using the -gcc command line switch enables these GCC-isms to be recognized by the Scale compiler.

Fortran Parser

Scale has its own Java-based parser that convert directly from Fortran source code to an abstract syntax tree (the Clef AST). As Fortran is a context-sensitive language, the Fortran Java-based parser was built "by hand". Dialects supported are standard Fortran 77. Fortran 90 and Fortran 95 are under development.

Clef AST To C

Clef AST to Scribble CFG

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

Example C output

Optimizations

Scale performs optimizations (except for inlining) in any order. The following optimizations are performed on the SSA form of the Scribble CFG:

• Sparse Conditional Constant Propagation
• Copy Propagation
• Value Numbering
• Loop Invariant Code Motion
• Scalar Replacement for Array Elements
• Loop Un-rolling
• Partial Redundancy Elimination

• Inlining
• Global Variable Replacement
• Place struct Fields in Registers
• Useless Copy Removal
• Dead Variable Elimination

Some optimizations can be performed on either the SSA or normal form of the CFG.

• Basic Block Redundant Load and Store Elimination.
• Expression Tree Height Reduction

Code Generator

Scale can transform the Scribble CFG into machine instructions for the Alpha, PowerPC, Sparc® V8, and Trips microprocessor chips. (A backend for Mips chips is available but not complete.) The compiler generates assembly language which then must be assembled by the native assembler. Code generators 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.

Displaying the CFG

Displaying the AST