Fractal symbolic analysis
Fractal symbolic analysis is a powerful new analysis technique for verifying the legality of program transformations. Most compilers use dependence analysis for this purpose, but dependence analysis is limited because it considers only the sets of locations read and written by statements, without assuming any interpretation for the operators in the language. In principle, symbolic analysis and comparison of programs does not suffer from this limitation, but it is intractable for all but the simplest programs.
Fractal symbolic analysis combines some of the power of symbolic program analysis with the tractability of dependence analysis. If a program and its restructured version are simple enough, they are analyzed symbolically; otherwise, the programs are simplified to produce two new programs whose equality implies equality of the original programs. If these simplied programs cannot be analyzed symbolically, they are themselves simplified. It is guaranteed that this recursive simplification process will ultimately produce programs that are simple enough to be analyzed symbolically.
We have shown that fractal symbolic analysis is strictly more powerful than dependence analysis. We have used fractal symbolic analysis to solve the problem of automatic blocking of LU factorization with pivoting to obtain performance competitive with hand-blocked code in the LAPACK library, and to restructure left-looking factorization codes to right-looking codes, and vice versa.