Witnessing Control Flow Graph Optimizations
- Project Research
- 1-5 Chapters
- Abstract : Available
- Table of Content: Available
- Reference Style: APA
- Recommended for : Student Researchers
- NGN 3000
ABSTRACT
Proving the correctness of a program transformation, and specifically, of a compiler optimization, is a long-standing research problem. Trusting the compiler requires to guarantee that the properties verified on the source program hold for the compiled target-code as well. Thus, the primary objective of formal correctness verification is to preserve the semantics of the source code, maintaining untouched its logical behavior. Traditional methods for formal correctness verification are not convenient to validate large and complex programs like compilers [1], and intensive testing, despite its proven efficacy, cannot guarantee the absence of bugs [2]. This thesis is part of a larger on-going research project aimed to demonstrate the feasibility to overcome the difficulties of traditional formal methods. K. Namjoshi and L. Zuck [3] propose a new methodology for creating an automated proof to guarantee the correctness of every execution of an optimization. A witness is a run-time generated relation between the source code and the target code, before and after the transformation. The relation is able to represent all the properties that must be valid throughout the optimization, offering a mathematical formula to prove, through a SMT-Solver (typically Microsoft Z3 ), if the invariants hold and the semantics is preserved. This work is a further step towards the implementation of a witnessing compiler [4]: the SimplifyCFG pass of the LLVM compiler framework is augmented with a witness generator procedure which constructs, run-time, the relations to prove the correctness of every single simplification in the control flow graph, performed by the compiler. We show that it is feasible to augment the SimplifyCFG pass with a witness generation procedure. We describe the structure of the code and the mathematical relations designed to demonstrate the correctness of a transformation on the Control Flow Graph. Benchmarks and tests will prove the correct behavior of our implementation and the effectiveness of the witnessing procedure. We provide details about the witnesses and the results of the benchmarks. First, the problem is described, together with the limitations of the traditional methods; then a solution is designed and explained. Details about the actual implementation for the SimplifyCFG code are provided in further sections
Related Project Materials
AN ASSESSMENT OF THE EFFECTIVENESS OF COST PLANNING TOOLS AND TECHNIQUES ON CONSTRUCTION PROJECT PERFORMANCE IN NIGERIA
BACKGROUND OF THE STUDY
It is a known fact that the Nigerian construction industry continues to occupy an important posi...
KNOWLEDGE, ATTITUDE AND PRACTICE OF DENTAL HEALTH CARE AMONG PRIMARY SCHOOL PUPILS IN ZARIA
ABSTRACT
The purpose of the study was to assess,“The knowledge, attitude and practice of dental health care among primary sch...
EFFECT OF INTEREST RATE ON ECONOMIC GROWTH IN NIGERIA
-
- Background of the Study
The effect of Interest rate on e...
DEVELOPMENTAND CHARACTERIZATION OF BIOCOMPOSITES FROM POLYLACTIC ACID AND GROUNDNUT SHELL ASH NANOPARTICLES
STATEMENT OF PROBLEM
Nanocomposite is a class of composites in which the dimensions of the reinforcing particles are in...
THE IMPACT OF INTERNAL CONTROL SYSTEM ON THE FINANCIAL MANAGEMENT OF AN ORGANIZATION
ABSTRACT
Over the years, there have being a problem of incorrect and unreliable financial record which has lead to loss of organizational...
THE IMPACT OF EDUCATIONAL FACILITIES ON THE ACADEMIC PERFORMANCE OF STUDENTS IN SENIOR SECONDARY SCHOOLS IN LAGOS STATE
EXCERPT FROM THE STUDY
- Educational facilities such as school libraries, Instructional materials, adequate classr...
Read more
EXAMINING THE ROLE OF EARLY CHILDHOOD EDUCATION IN ENHANCING VISUAL ARTS SKILLS
ABSTRACT: This study Examined the Role of Early Childhood Education in Enhancing Visual Arts Skills. The obj...
Read moreEFFECT OF PRICING STRATEGIES ON SALES VOLUME -A CASE STUDY FPA MARKETING MODEL SHOP
Background of the study
Businesses today are facing one of the most competitive eras in history. The rise and fall of bu...
Read moreTHE IMPACT OF INFORMATION AND COMMUNICATION TECHNOLOGY ON THE EFFICIENT MANAGEMENT IN PUBLIC ENTERPRISE
ABSTRACT
This project focuses on “the Impact of Information and Communication Technology and the Efficiency of Man...
Read moreASSESSMENT OF LECTURERS’ ATTITUDES, SELF- EFFICACY AND ACCESS TO THE UTILIZATION OF INFORMATION AND COMMUNICATION TECNOLOGY IN COLLEGES OF EDUCATION IN NIGERIA
ABSTRACT
This study assessed lecturers‟ attitudes, self-Efficacy and access on utilization of Information and Communication Technologies...
Read more
