Specifying and verifying program transformations with PTRANS

compiler correctness;control flow graphs;temporal logic;rewriting;graph transformation;interactive theorem proving;operational semantics;concurrency;relaxed memory models;Satisfiability Modulo Theories (SMT) solvers

Mansky, William

关键词: compiler correctness;    control flow graphs;    temporal logic;    rewriting;    graph transformation;    interactive theorem proving;    operational semantics;    concurrency;    relaxed memory models;    Satisfiability Modulo Theories (SMT) solvers;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/49385/William_Mansky.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Software developers, compiler designers, and formal methods researchers all stand to benefit from improved tools for compiler design and verification. Program correctness for compiled languages depends fundamentally on compiler correctness, and compiler optimizations are usually not formally verified due to the effortinvolved. This is particularly true for optimizations on parallel programs, which are often more difficult to specify correctly and to verify than their sequential counterparts, especially in the presence of relaxed memory models. In this thesis, we outline a Verification Framework for Optimizations and Program Transformations, designed to facilitate stating and reasoning about compiler optimizations and transformations on parallel programs. Most verified compilation projects focus on a single intermediate language and a small number of input and output languages, later adding new targets as extensions; our framework, on the other hand, is designed with language-independence as a first principle, and we seek to generalize and reuse as much as possible across multiple target languages. Our framework makes use of the novel PTRANS transformation specification language, in which program transformations are expressed as rewrites on control flow graphs with temporal logic side conditions. The syntax of PTRANS allows cleaner, more proof-amenable specification of program optimizations. PTRANS has two sets of semantics: an abstract semantics for verification, and an executable semantics that allows specifications to act as prototypes for the optimizationsthemselves, so that candidate optimizations can be tested and refined before going on to formally verify them or include them in a compiler. We address the problems of parallelism head-on by developing a generic framework for memory models in VeriF-OPT, and present a method of importing external analyses such as alias analysis to overcome potential limitations of temporal logic. Finally, we demonstrate the use ofthe framework by prototyping, testing, and verifying the correctness of several variants of redundant store elimination in two markedly different intermediate languages.