MAJIC Compiler Techniques

• Source-level optimization:

  Matrix operations like addition and multiplication have a rich algebraic structure that can be exploited to generate efficient code. Modern compilers routinely exploit algebraic properties of floating-point operations, but most existing compilers do not exploit matrix algebra. We are developing novel restructuring technology for optimizing programs at the matrix level. Source-to-source transformations are critical for efficiency regardless of whether the MATLAB program is ultimately just interpreted or compiled down to a lower level.

• Just-In-Time compilation:

  MATLAB is a language designed to be interpreted. It does not have type declarations, and its handling of symbols is ambiguous: e.g. there is no way to determine whether a certain symbol in a MATLAB script is a variable or a function call.

  By deferring compilation as much as possible we can minimize the impact of these problems. Type analysis, used in FALCON, can determine the type of variables and lead to generation of efficient code; however, at runtime, a lot more information is available about the actual types of the variables, and thus type analysis can be both faster and yield more exact types.

  Exact knowledge of array bounds offers the possibility of unrolling loops and vector operations with zero overhead. It also enables the optimization of indexed variable accesses by removing unnecessary loop bounds.

  Analysis at runtime also affords a better knowledge of loop parallelism, allowing the generation of SMP code, yielding even more speed.

  On a multiprocessor machine parsing, analysis, compilation and execution can be pipelined to implement look-ahead compilation and continuous compilation.

• Sparse matrix support

  A large variety of sparse matrix formats are used in practice (the Sparse BLAS project at NIST supports no less than 13 formats), but MATLAB directly supports only Compressed Column Storage (CCS). In many scientific applications, block formats that exploit dense sub-blocks within the overall sparse matrix must be used for efficiency. We are developing technology to permit the generation of efficient sparse code for such formats.