Name
Abstract | ||
|---|---|---|
Modern compilers perform wholesale restructuring of programs to improve their efficiency. Dependence analysis is the most widely used technique for proving the correctness of such transformations, but it suffers from the limitation that it considers only the memory locations read and written by a statement, and does not assume any particular interpretation for the operations in that statement. Exploiting the semantics of these operations permits more transformations to be proved correct, and is critical for automatic restructuring of codes such as LU with partial pivoting.One approach to exploiting the semantics of program operations is symbolic analysis and comparison of programs. In principle, this technique is very powerful, but in practice, it is intractable for all but the simplest programs.In this paper, we propose a new form of symbolic analysis and comparison of programs which is appropriate for use in restructuring compilers. Fractal symbolic analysis compares a program and its transformed version by repeatedly simplifying these programs until symbolic analysis becomes tractable while ensuring that equality of the simplified programs is sufficient to guarantee equality of the original programs.Fractal symbolic analysis combines some of the power of symbolic analysis with the tractability of dependence analysis. We discuss a prototype implementation of fractal symbolic analysis, and show how it can be used to solve the long-open problem of verifying the correctness of transformations required to improve the cache performance of LU factorization with partial pivoting. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1145/377792.377804 | I4CS |
Keywords | DocType | Volume |
wholesale restructuring,original program,symbolic analysis,lu factorization,automatic restructuring,dependence analysis,program operation,fractal symbolic analysis,partial pivoting,restructuring compiler,programming language,languages,algorithms,compilers,program optimization | Journal | cs.PL/0001009 |
ISBN | Citations | PageRank |
1-58113-410-X | 5 | 0.62 |
References | Authors | |
17 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikolay Mateev | 1 | 149 | 11.92 |
| Vijay Menon | 2 | 191 | 13.11 |
| Keshav Pingali | 3 | 3056 | 256.64 |