Abstract
We describe a test development method, named OTK, that is aimed at optimizing compiler testing. The OTK method is based on constructing a model of optimizer’s input data. The method allows developing tests targeted to testing a chosen optimizer. A formal data model is constructed on the basis of an abstract informal description of an algorithm of the optimizer under test. In the paper, we consider in detail the process of analyzing an optimization algorithm and building a formal model. We also consider in outline the other part of the method, test selection and test running. The OTK method has been successfully applied in several case studies, including test development for several different optimizing compilers for modern architectures.
Chapter PDF
Similar content being viewed by others
Keywords
References
Allen, R., Kennedy, K.: Optimizing Compilers for Modern Architectures. Morgan Kaufmann Publishers, San Francisco (2002)
Arkhipova, M.V.: Semantic analyzer tests generation. Numerical Methods and Programming, vol. 7, pp. 55–70 (in Russian) (2006), http://num-meth.srcc.msu.su/english/zhurnal/tom_2006/v7r206.html
Beizer, B.: Software Testing Techniques. van Nostrand Reinhold (1990)
Bourdonov, I.B., Kossatchev, A.S., Kuliamin, V.V., Petrenko, A.K.: UniTesK Test Suite Architecture. In: Eriksson, L.-H., Lindsay, P.A. (eds.) FME 2002. LNCS, vol. 2391, pp. 77–88. Springer, Heidelberg (2002)
Duncan, A.G., Hutchison, J.S.: Using Attributed Grammars to Test Designs and Implementation. In: Proceedings of the 5th international conference on Software engineering, Piscataway, NJ, USA, pp. 170–178. IEEE Press, New York (1981)
Hannan, J., Pfenning, F.: Compiler Verification in LF. In: Proc. 7th Annual IEEE Symposium on Logic in Computer Science, pp. 407–418 (1992)
Harm, J., Lämmel, R.: Two-dimensional Approximation Coverage. Informatica Journal, 24(3) (2000)
Jaramillo, C., Gupta, R., Soffa, M.L.: Comparison Checking: An Approach to Avoid Debugging of Optimized Code. In: Nierstrasz, O., Lemoine, M. (eds.) Software Engineering - ESEC/FSE 1999. LNCS, vol. 1687, pp. 268–284. Springer, Heidelberg (1999)
Kalinov, A., Kossatchev, A., Posypkin, M., Shishkov, V.: Using ASM Specification for automatic test suite generation for mpC parallel programming language compiler. In: Proc. 4th International Workshop on Action Semantic, AS, BRICS note series NS-02-8, pp. 99–109 (2002)
Kossatchev, A.S., Petrenko, A.K., Zelenov, S.V., Zelenova, S.A.: Application of Model-Based Approach for Automated Testing of Optimizing Compilers. In: Proceedings of the International Workshop on Program Understanding. Novosibirsk, pp. 81–88 (2003)
Lämmel, R.: Grammar testing. In: Hussmann, H. (ed.) ETAPS 2001 and FASE 2001. LNCS, vol. 2029, pp. 201–216. Springer, Heidelberg (2001)
McKeeman, W.: Differential testing for software. Digital Technical Journal 10(1), 100–107 (1998)
McNerney, T.S.: Verifying the Correctness of Compiler Transformations on Basic Blocks using Abstract Interpretation. In: Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pp. 106–115 (1991)
Muchnick, S.: Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, San Francisco (1997)
Necula, G.: Translation Validation for an Optimizing Compiler. In: Proc. ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 83–95 (2000)
OTK: Optimizer Testing Kit. http://www.unitesk.com/content/category/9/17/35/
Petrenko, A.K.: Specification Based Testing: Towards Practice. In: Bjørner, D., Broy, M., Zamulin, A.V. (eds.) PSI 2001. LNCS, vol. 2244, pp. 287–300. Springer, Heidelberg (2001)
Purdom, P.: A Sentence Generator For Testing Parsers. BIT 2, 336–375 (1972)
TreeDL: Tree Description Language. http://treedl.sourceforge.net/treedl/treedl_en.html
UniTESK Technology Web-site. http://www.unitesk.com/
Wand, M., Wang, Zh.: Conditional Lambda-Theories and the Verification of Static Properties of Programs. In: Proc. 5th IEEE Symposium on Logic in Computer Science, pp. 321–332 (1990)
Wand, M.: Compiler Correctness for Parallel Languages. In: FPCA. Conference on Functional Programming Languages and Computer Architecture, pp. 120–134 (1995)
Zelenov, S.V., Silakov, D.V., Petrenko, A.K., Conrad, M., Fey, I.: Automatic Test Generation for Model-Based Code Generators. In: Proc. 2nd International Symposium on Leveraging Applications of Formal Methods, Verification and Validation, ISoLA (2006)
Zelenov, S., Zelenova, S.: Automated Generation of Positive and Negative Tests for Parsers. In: Grieskamp, W., Weise, C. (eds.) FATES 2005. LNCS, vol. 3997, pp. 187–202. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 IFIP International Federation for Information Processing
About this paper
Cite this paper
Zelenov, S., Zelenova, S. (2007). Model-Based Testing of Optimizing Compilers. In: Petrenko, A., Veanes, M., Tretmans, J., Grieskamp, W. (eds) Testing of Software and Communicating Systems. FATES TestCom 2007 2007. Lecture Notes in Computer Science, vol 4581. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73066-8_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-73066-8_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73065-1
Online ISBN: 978-3-540-73066-8
eBook Packages: Computer ScienceComputer Science (R0)