Bibliography for “Practical Testing of a C99 Compiler Using Output Comparison”
This is an updated version of the bibliography from my article, “Practical Testing of a C99 Compiler Using Output Comparison,” published in Software: Practice and Experience (http://doi.wiley.com/10.1002/spe.812; a pre-print is available at http://pobox.com/~flash/Practical_Testing_of_C99.pdf.) The journal version of the bibliography is in reference order, and contains items discussed in the article but not directly relevant to compiler testing. The online version is sorted alphabetically, with items on topics other than compiler testing separated; it will be updated if more articles on compiler testing appear. The emphasis, as the title of the article indicates, is on practical testing of C/C++ compilers.
The literature on compiler testing is surprisingly scant. There is substantial literature on the theoretical design of compilers which would provably not need testing, but the audience for such work is largely disjoint from that for the testing of compilers for widely-used languages which will have a substantial user base. There are also a number of articles on the automated generation of test code, but given that there is now a substantial base of real Open Source software, this is less useful than formerly.
This article, and PalmSource’s testing, was firmly directed towards shipping a high-quality, but imperfect, compiler which would be of practical use to the developer community. Producing an inherently bug-free compiler for a theoretically desirable language was not an option. The goal was to catch as high a proportion of serious bugs as possible in a useful compiler for two widely-used languages, C99 and C++98.
The best available bibliography was over a decade old, by Dr. C.J. Burgess of the University of Bristol; it was a posting to the comp.compilers Usenet newsgroups, below [Burgess]. (See now also the bibliography in [Chen, Patra, et al.]) Bailey & Davidson [Bailey & Davidson] is an academic article on the testing of function calls, somewhat similar to Lindig’s Quest [Lindig]; it contains the interesting observations that “the state-of-the-art in compiler testing is inadequate” (p. 1040), and that in their experience, the ratio of failed tests to bugs was approximately one thousand to one (p. 1041). The standard work on compiler theory is Compilers: Principles, Techniques and Tools [Aho et al], commonly known as the Dragon book. It is a good general introduction, but had little direct relevance to our testing, except for some extra caution in including examples of spaghetti code; other standard compiler texts which were consulted, but did not have significant sections on testing, are omitted from the bibliography. A Retargetable C Compiler: Design and Implementation [Fraser & Hanson] contains a brief section on the authors’ experience with testing their compiler, with some practical advice on the importance of regression test cases; difficulties in using lcc’s regression tests for other compilers are discussed above, in the section on emulated-execution output correctness testing. An updated and alphabetized version of this bibliography will be made available at http://pobox.com/~flash/compiler_testing_bibliography.html.
- Bailey, Mark W. and Davidson, Jack W., “Automatic Detection and Diagnosis of Faults in Generated Code for Procedure Calls”, IEEE Transactions on Software Engineering, volume 29, issue 11, 2003. An abstract is available online, at http://csdl.computer.org/comp/trans/ts/2003/11/e1031abs.htm, as is an earlier version of the full paper, http://big-oh.cs.hamilton.edu/~bailey/pubs/techreps/TR-2001-1.pdf
- Bhattacharya, Soumyabrata “ANSI C Test suites,” comp.compilers, http://compilers.iecc.com/comparch/article/94-10-060, 1994.
- Burgess, C.J. , “Bibliography for Automatic Test Data Generation for Compilers,” comp.compilers, http://compilers.iecc.com/comparch/article/93-12-064, 1993.
- Junjie Chen, Yanwei Bai, Dan Hao, Yingfei Xiong, Hongyu Zhang, Bing Xie. “Learning to Prioritize Test Programs for Compiler Testing,” ICSE'17: 39th International Conference on Software Engineering, Buenos Aires, Argentina, May 2017.
- Junjie Chen, Jibesh Patra, Michael Pradel, Yingfei Xiong, Hongyu Zhang, Dan Hao, and Lu Zhang. 2019. “A Survey of Compiler Testing.” ACM Computing Surveys, to Appear, 2020. (But note that the preprint refers to itself as “ACM Comput. Surv. 1, 1, Article 1 (January 2019),” with an invalid DOI: https://doi.org/10.1145/3363562.)
- Schloss Dagstuhl, Testing and Verification of Compilers
- DejaGnu http://www.gnu.org/software/dejagnu/, 1993-.
- Delta, a tool for test failure minimization, Wilkerson, Daniel and McPeak, Scott, http://delta.tigris.org, 2003-5. Based on [Zeller]. See also [Open Source Quality Project].
- Dziubinski, Matt P. “C++ links: compilers - correctness”.
- Eide, Eric and Regehr, John “Volatiles are miscompiled, and what to do about it” in Proceedings of the 7th ACM international conference on Embedded software, ISBN 978-1-60558-468-3, Association for Computing Machinery 2008. Preprint at http://www.cs.utah.edu/~regehr/papers/emsoft08-preprint.pdf.
- Ellison, Chucky and Rosu, Grigore “Defining the Undefinedness of C,” University of Illinois technical report, 2012.
- Equivalent Modulo Input Compiler Validation Project, UC Davis
- Fernandez, Mary and Ramsey, Norman “Automatic Checking of Instruction Specifications,” in Proceedings of the 19th International Conference on Software Engineering, ISBN:0-89791-914-9, Association for Computing Machinery 1997. Preprint at http://www.cs.tufts.edu/~nr/pubs/checker.html.
- Fraser, Christopher and Hanson, David, A Retargetable C compiler: Design and Implementation, ISBN: 0-8053-1670-1, Benjamin/Cummings Publishing, 1995, §19.5 pp. 531–3.
Niranjan Hasabnis, Rui Qiao, and R. Sekar, 2015. “Checking correctness of code generator architecture specifications.” In Proceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO '15). IEEE Computer Society, Washington, DC, USA, 167-178.
- Jones, Derek “Who Guards the Guardians?” (a study of the coverage of the Perennial Validation Suite), http://www.knosof.co.uk/whoguard.html, 1993.
- Kahan, William Sumner, Thos, et al., Paranoia Floating Point Test, http://www.netlib.org/paranoia/paranoia.c, 1983-5.
- lcc, A Retargetable Compiler for ANSI C, http://www.cs.princeton.edu/software/lcc/; described in A Retargetable C Compiler: Design and Implementation, Hanson, David R. and Fraser, Christopher W., ISBN: 0-8053-1670-1, Benjamin/Cummings Publishing 1995.
- Lindig, Christian, “Random Testing of the Translation of C Function Calls”, http://code.google.com/p/quest-tester/. Proceedings of the Sixth International Workshop on Automated Debugging, ISBN 1-59593-050-7, Association for Computing Machinery 2005.
- McKeeman, William M. “Differential Testing for Software,” Digital Technical Journal, Vol. 10 No. 1, 1998.
- MattPD: “C++ links: compilers - correctness”
- Modena Test++ Suite, http://modena.us/testpp.htm.
- George C. Necula, “Translation Validation for an Optimizing Compiler”
- Open Source Quality Project http://osq.cs.berkeley.edu/.
- Perennial Validation Suites http://peren.com/pages/products_set.htm.
- Plum Hall C and C++ Validation Test Suites http://plumhall.com/suites.html.
- Regehr, John “Embedded in Academia : A Critical Look at the SCADE Compiler Verification Kit,” blog posting, 2011.
- Regehr, John “Are Compilers Getting More or Less Reliable?” blog posting, 2013.
- Regehr, John “Guidelines for Research on Finding Bugs” blog posting, 2013.
John Regehr, Yang Chen, Pascal Cuoq, Eric Eide, Chucky Ellison, and Xuejun Yang,
Test-Case Reduction for C Compiler Bugs (C-Reduce)
in Proceedings of 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2012), Beijing, China, June 2012.
- Sheridan, Flash, “Practical Testing of a C99 Compiler Using Output Comparison,” Software: Practice and Experience, http://dx.doi.org/10.1002/spe.812, 2007. A pre-print is available at http://pobox.com/~flash/Practical_Testing_of_C99.pdf. A list of bugs discovered using the techniques in the article is at http://pobox.com/~flash/FlashsOpenSourceBugReports.html.
- Small Device C Compiler (SDCC), Dutta, Sandeep et al., http://sdcc.sourceforge.net/, 1999-.
- Zhendong Su et al., Equivalence Modulo Inputs Compiler Validation Project, University of California, Davis, 2014–.
- Chengnian Sun, Vu Le, Qirun Zhang, and Zhendong Su, “Toward Understanding Compiler Bugs in GCC and LLVM,” Proceedings of ISSTA 2016, Saarbrucken, Germany, 2016. Source code and dataset; pre-print.
- Tydeman, Fred, C99 FPCE Test Suite, http://www.tybor.com/readme.1st, 1995-2006.
- Vallat, Miod “Compilers in OpenBSD,” openbsd-misc posting 2013.
- Xi Wang, Nickolai Zeldovich, M. Frans Kaashoek, and Armando Solar-Lezama, “Towards optimization-safe systems,”SOSP'13: The 24th ACM Symposium on Operating Systems Principles,2013.
- Xuejun Yang, Random Testing of Open Source C Compilers,, doctoral thesis, The University of Utah, December 2014.
- Xuejun Yang, Yang Chen, Eric Eide, and John Regehr, “Finding and Understanding Bugs in C Compilers,” Proceedings of the 2011 ACM SIGPLAN Conference on Programming Language Design and Implementation, http://dx.doi.org/10.1145/1993498.1993532, preprint at http://www.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf
- Zeller, A.: “Yesterday, my program worked. Today, it does not. Why?”, Software Engineering - ESEC/FSE'99: 7th European Software Engineering Conference, ISSN 0302-9743, volume 1687 of Lecture Notes in Computer Science, pp. 253-267, 1999.
- Qirun Zhang, Chengnian Sun, and Zhendong Su, “Skeletal Program Enumeration for Rigorous Compiler Testing,” in Proceedings of PLDI, Barcelona, Spain, June 2017.
Source Code Useful for Compiler Testing (Primarily C/C++)
- Aho, Alfred V., Sethi, Ravi, and Ullman, Jeffrey D., Compilers: Principles, Techniques and Tools, ISBN: 0201100886, Addison Wesley 1986, §11.4, p. 731. The 2006 edition omits this section, but comments on page 16: “Optimizing compilers are so difficult to get right that we dare say that no optimizing compiler is completely error-free! Thus, the most important objective in writing a compiler is that it is correct.”
- Apple Bug Database https://bugreport.apple.com/, free registration required.
- Apogee Software, Inc., http://www.apogee.com/compilers.html, 1988-.
- ARM Application Binary Interface (ARM ABI), http://www.arm.com/products/DevTools/ABI.html, 2001-.
- ARM Developer Suite (ADS), version 1.2, http://www.arm.com/support/ads_faq.html, 2001-2004.
- ARMulator: ARM Emulator, GDB Version: http://sources.redhat.com/cgi-bin/cvsweb.cgi/src/sim/arm/?cvsroot=src, 1999-. See also the results of the documentation ‘info gdb Target’, subsection ‘Target Commands’, paragraph ‘target sim’, in versions of GDB with ARM emulator support. This requires building with the ‘--target=arm-none-elf’ option; see [GDB Bug 1884].
- Beizer, Boris, Software System Testing and Quality Assurance, ISBN: 0442213069, Van Nostrand 1984.
- C++98 ISO/IEC Standard, ANSI/ISO 14882:1998(E), http://www.techstreet.com/cgi-bin/detail?product_id=1143945, 1998.
- C89 ANSI X3.159-1989, ANSI/ISO 9899-1990. Commonly referred to as “ANSI C.”
- C99 ISO/IEC Standard, INCITS/ISO/IEC 9899-1999, second edition, http://webstore.ansi.org/ansidocstore/product.asp?sku=INCITS%2FISO%2FIEC+9899-1999, 1999.
- CodeSourcery GNU Toolchain for ARM Processors, http://www.codesourcery.com/gnu_toolchains/arm/, 1997-. CodeSourcery’s bug database is not accessible to the public; the mailing list for their ARM compiler is archived at http://www.codesourcery.com/archives/arm-gnu.
- CodeSourcery 2005Q3-2, Release announcement for the 2005Q3-2 version of the CodeSourcery GNU Toolchain for ARM Processors, http://www.codesourcery.com/archives/arm-gnu-announce/msg00006.html, 2005.
- Cygwin http://www.cygwin.com, 1995-.
- Dominus, Mark Jason, Good Advice and Maxims for Programmers,” http://jwenet.net/notebook/2005/1036.html, 2002.
- Edison Design Group, Inc., http://www.edg.com/cpp.html, 1991-.
- Freely Distributable Mathematics Library (FDLIBM), Sun Microsystems, Inc., http://www.netlib.org/fdlibm/readme, 1993.
- GNU Compiler Collection (GCC) http://gcc.gnu.org, 1987-.
- GCC Bugzilla Database: http://gcc.gnu.org/bugzilla. See also http://pobox.com/~flash/FlashsOpenSourceBugReports.html for an ongoing list of bugs found with the techniques presented here.
- GCC C-Torture Test Suite: http://gcc.gnu.org/install/test.html.
- GNU Project Debugger (GDB), http://www.gnu.org/software/gdb, 1988-.
- GDB Bugzilla Database: http://sources.redhat.com/cgi-bin/gnatsweb.pl.
- Griffith, Arthur, GCC: The Complete Reference, ISBN: 0072224053, McGraw-Hill 2002.
- Harbison, Samuel P., and Steele, Guy L., C: A Reference Manual, Fifth Edition, ISBN: 013089592X, http://www.careferencemanual.com/, Prentice Hall 2002.
- Kaner, Cem, Falk, Jack, and Nguyen, Hung Q., Testing Computer Software, Second Edition, ISBN: 0471358460, Wiley 1999.
- Kernighan, Brian W. and Ritchie, Dennis M., The C Programming Language, Second Edition, ISBN: 0131103628, Prentice Hall 1988.
- Palm OS® Developer Suite: https://www.developerpavilion.com/palmos/page.asp?page_id=365&tool_id=6, free registration required, 2004-.
- Palm OS Cobalt®, http://www.palmos.com/dev/tech/oses/cobalt60.html, 2003-.
- Perl (Practical Extraction and Report Language), Programming Perl, Third Edition, Wall, Larry et al., ISBN: 0-596-000278, O'Reilly & Associates 2000, http://www.perl.org, 1987-.
Copyright © 2002-2007, Access Systems Americas, Inc. PalmSource, Palm OS and Palm Powered, and certain other trade names, trademarks and logos are trademarks which may be registered in the United States, France, Germany, Japan, the United Kingdom and other countries, and are either owned by PalmSource, Inc. or its affiliates, or are licensed exclusively to PalmSource, Inc. by Palm Trademark Holding Company, LLC. All other brands, trademarks and service marks used herein are or may be trademarks of, and are used to identify other products or services of, their respective owners. All rights reserved. Copyright © 2008-2017, Flash (K.J.) Sheridan.