Detection And Localization For Compiler Optimization Bugs

Compiler optimizations play an important role in compilers to improve program performance.Generally,for a given program,we need to utilize a specific compiler optimization to optimize it to achieve better performance.However,this may cause serious compiler bugs,which may lead to unintended program behavior or even cause disaster.In these years,although many studies have developed techniques for the detection and localization of compiler bugs,no systematic work has been conducted to detect and localize compiler bugs caused by compiler optimizations(hereafter,we call these compiler bugs as compiler optimization bugs).There are many kinds of compiler optimizations and their behaviors may be influenced by each other,which makes it hard to test compiler optimization and localize compiler optimization bugs.Hence,in this thesis,we try to study the detection and localization of compiler optimization bugs to better guarantee the quality of compilers.In this thesis,our work contains three aspects,namely the understanding of compiler optimization bugs,the detection of compiler optimization bugs,and the localization of compiler optimization bugs.Firstly,to better understand compiler optimization bugs,we conduct an empirical study to investigate the characteristics of compiler optimization bugs.Secondly,we propose an efficient technique for testing compiler optimizations to detect compiler optimization bugs.Finally,to help developers better diagnose and repair compiler optimization bugs,we present an efficient technique to automatically localize compiler optimization bugs.Specifically,the main research work of this thesis is as follows:(1)A historical bug data based characteristic analysis of compiler optimization bugs.This study explores the characteristics of compiler optimization bugs.By analyzing a large amount of compiler optimization bugs,this study reveals five characteristics of compiler optimization bugs,including the distribution of optimization bugs over time and the distribution in components,the optimizations related to the optimization bugs,the types of optimization bugs,the time that optimization bugs live,and the bug fixes information of optimization bugs.The results of this study show that although compilers have been tested extensively,compiler optimizations are still the most bug-prone component in compilers and fixing compiler optimization bugs is still time-consuming.Hence,more effective techniques are needed to ensure the quality of compiler optimizations.(2)A representative instance selection-based method for compiler optimization bug detection.Due to the enormous number of compiler optimization sequences and testing programs,this method mainly resolves two challenges to improve test efficiency,namely the acquisition of representative optimization sequences and the selection of representative testing programs.To address these two challenges,this method first presents efficient vector representation methods of compiler optimization sequences and testing programs.Then a“centroid” based selection scheme is proposed to select representative compiler optimization sequences and testing programs.By using representative compiler optimization sequences and testing programs,this technique improves the possibility to find more compiler optimization sequence bugs in a limited time.The experimental results show that this method significantly improves the test efficiency by up to 24.76% ～ 50.57%.Within seven months,this technique has detected 104 valid compiler optimization sequence bugs within 5 types,of which 21 have been confirmed or fixed.(3)A search-based method for compiler optimization bug localization.This method localizes the files that contain the corresponding compiler optimization bug by comparing the compiler execution traces between the buggy optimization sequence and bug-free optimization sequences.Hence,this method transforms the problem of the localization for a compiler optimization sequence bug to the problem of the construction for bug-free optimization sequences.Therefore,to resolve this problem,a constrained genetic algorithm is proposed to construct a set of bug-free compiler optimization sequences based on the given buggy compiler optimization sequence.The evaluation based on 60 real-world optimization sequence bugs demonstrates that this technique can successfully localize 65.00% bugs in the top 5 suspicious files.The efficiency of localization is improved by up to 77.27%.The work in this thesis has achieved remarkable effectiveness in detecting and locating compiler optimization sequence bugs.This can help developers better detect and diagnose compiler optimization bugs,thus improving the reliability of compiler optimizations.