Abstract. Although there are many register allocation algorithms that work well, it can be difficult to correctly implement these algorithms. As a result, it is common for bugs to remain in the register allocator, even after the compiler is released. The r
Published in “The 13th International Static Analysis Symposium”, Korea, 2006
Catching and Identifying Bugs in Register Allocation
Yuqiang Huang , Bruce R. Childers , and Mary Lou Soffa
Department of Computer Science
University of Pittsburgh
Pittsburgh, Pennsylvania 15260
{yuqiangh, childers}@cs.pitt.edu Department of Computer Science University of Virginia Charlottesville, Virginia 22904 soffa@cs.virginia.edu
Abstract. Although there are many register allocation algorithms that work
well, it can be difficult to correctly implement these algorithms. As a result, it
is common for bugs to remain in the register allocator, even after the
compiler is released. The register allocator may run, but bugs can cause it to
produce incorrect output code. The output program may even execute
properly on some test data, but errors can remain. In this paper, we propose
novel data flow analyses to statically check that the output code from the
register allocator is correct in terms of its data dependences. The approach is
accurate, fast, and can identify and report error locations and types. No false
alarms are produced. The paper describes our approach, called SARAC, and
a tool, called ra-analyzer, that statically checks a register allocation and
reports the errors it finds. The tool has an average compile-time overhead of
only 8% and a modest average memory overhead of 85KB.
1 Introduction
One of the most critical compiler transformations is register allocation, as a good allocator can make a dramatic difference in obtaining good performance [4, 11]. One study even reported that careful register allocation makes one order of magnitude difference in performance [26]! Thus, considerable effort has been given to developing new allocation algorithms or variants of existing ones [2-7, 11, 12, 24, 26, 28, 30]. Given the many algorithm variants and the complexity of modern architectures, implementing register allocation is often a complex and error prone task. Particularly, it is difficult to detect and locate bugs in an erroneous output of the allocator if the code runs to completion. Some efforts [13, 18, 21] have proposed techniques to ensure the allocator’s implementation is correct. In this paper, we describe a novel technique to check the correctness of register allocation and also to report the bugs. This technique is useful throughout the lifetime of a compiler, particularly during the development period.
Although a compiler undergoes much testing, bugs in the register allocator often slip past regression tests and are reported after release. What is worse is that many of these bugs cause the compiler to fail on some input programs, but not on others. The generated code may have bugs, although the compiler did not crash. Such latent bugs will not be discovered until a particular test input causes the program to fail. Assuming that a test input catches the bug, the developer is likely to believe that the bug is in the program itself, rather than the compiler. She will spend much time and effort tracking
Pointer-Range Analysis. In the 11th International Static Analysis Symposium (SAS'04), Verona, Italy, August 26-28, 2004. [7] Qi Sun, Anindya ...
(IEE) Springer Berlin/Heidelberg The MIT Press Oxford Press Springer Springer...International Static Analysis Symposium IEEE International Requirement Engineering ...
(13th CCL) and The 2nd International Symposium ...Syntactic analysis and parsing the Web ? Tagging ...published in the Journal of Chinese Information ...
Conference on Software Maintenance International Conference on Software Reuse International Conf on Function Programming International Static Analysis Symposium ...
Conference on Software Maintenance International Conference on Software Reuse International Conf on Function Programming International Static Analysis Symposium ...
//www.cs.luc.edu/icfp/ International Static Analysis Symposium Springer http://www.sas.com/events/dmconf/m2005/ International Symposium on Software ...
Symposium International Static Analysis Symposium Foundations of Software Engineering Tools and Algorithms for TACAS the Construction and Analysis of Systems ...
This is an extended version of a paper BG96] which appeared in the Proceedings of the Third International Static Analysis Symposium, Aachen, Germany, ...
Symposium International Static Analysis Symposium Foundations of Software Engineering Tools and Algorithms for TACAS the Construction and Analysis of Systems ...
热门文档