Fractal symbolic analysis

摘要: Modern compilers perform wholesale restructuring of programs to improve their efficiency. Dependence analysis is the most widely used technique for proving correctness such transformations, but it suffers from limitation that considers only memory locations read and written by a statement, does not assume any particular interpretation operations in statement. Exploiting semantics these permits more transformations be proved correct, critical automatic codes as LU with partial pivoting.One approach exploiting program symbolic comparison programs. In principle, this very powerful, practice, intractable all simplest programs.In paper, we propose new form which appropriate use compilers. Fractal compares its transformed version repeatedly simplifying until becomes tractable while ensuring equality simplified sufficient guarantee original programs.Fractal combines some power tractability dependence analysis. We discuss prototype implementation fractal analysis, show how can solve long-open problem verifying required cache performance factorization pivoting.