This dissertation presents two symbolic compilation frameworks for exploiting high-level semantic information of arrays in numerical codes in order to enable performance-enhancing transformations.; Matrixization is a framework for summarizing loop nests in terms of matrix and array operations. In a statically compiled language such as C or Fortran, it may be used to map loop nests to efficient hand-coded numerical libraries or special-purpose hardware. In a dynamically interpreted language such as MATLAB, it may also be used to eliminate significant interpretation overhead. In the process of detecting high-level operations, matrixization is able to exploit properties such as associativity of matrix multiplication to produce more efficient code. Matrixization is implemented and evaluated as a just-in-time optimization in MAJIC, a research platform for MATLAB.; Fractal symbolic analysis is a symbolic framework to prove the validity of reordering program transformations. While symbolic comparison of two programs is generally undecidable, this framework compares a program and its transformed version by repeatedly simplifying these programs until symbolic analysis becomes tractable, ensuring that equality of simplified programs is sufficient to guarantee equality of the original programs. Fractal symbolic analysis subsumes conventional dependence analysis, yet enables a compiler to perform optimizations conservatively disallowed by dependence analysis such as those on reduction and pivoting codes. It is the first general framework capable of enabling critical optimizations on LU factorization with partial pivoting, a key numerical linear algebra operation, and thus solves what had been an open problem for the past decade in the restructuring compiler community.
展开▼
