A Program Control Structure Generation Algorithm For Compiling Optimization Testing

Compiler is an important system software which transforms source programs written in high-level languages into object programs in low-level languages. It is a basic supporting tool in software development. The quality of a compiler directly affects the execution of other application softwares, so it needs plenty of testing to assure its reliability. Optimization is one of the most important and difficult stages in compiling. It can enhance the performance of object programs through code transformation. Compiling optimization is usually an NP-problem and very complicated, so compiling optimization testing is necessary. Compiling optimization testing tests the optimization function of a compiler which checks whether the generated object code is correct and its execution performance is improved or not.Like the testing flow of other softwares, the main issues in compiling optimization testing include test case generation, test case execution and test result analysis, etc. Test cases in compiling testing are programs written in high-level languages. It is inefficient to generate them manually, so automated test case generation methods are necessary and helpful. In normal compiler testing most of the test case generation methods are based on the grammar of the source language. These methods can test the translation function of a compiler well but lack of the pertinence to the optimization function. In compiling optimization testing, test cases should not only match grammar, but also contain features that can be optimized. Methods that can generate test cases with features that can be optimized are necessary to compiling optimization testing.The application of an optimization algorithm is based on the analysis of source programs. Only programs that have specific control structure and data flow are transformed. Thus we present an automatic test case generation method which uses program control structure as a basis and complements data flow to it. Control structure is a frame of a program and all data are attached to it. The method consists of two parts, control structure generation and data flow generation. First control structure of a test case is generated by the program control structure generation algorithm, and then for different optimization technique, different data flow generation algorithm is applied to the generated control structure to generate data flow and get a complete program as a test case. This method is simple and direct. It can easily describe the features to be optimized in test cases and control their generation. This method can be applied to several compiling optimization techniques.In this paper we focus on the control structure algorithm, which is the basis of the test case generation method. In this algorithm, Parallel and Nest are two parameters to define the relationship between basic control structures which build the whole control structure of a test case. When generating a test case, a complete tree is built according to these two parameters. The tree is cut by given cutting rules andrenewing rules. All the generated trees are judged whether they are valid or not according to given judging rules. All the valid ones will be transformed to program control structures as the output of this algorithm and will be served as a basis for the next step, data flow generation.This method is successfully implemented in an automatic testing tool for compiling optimization. The tool based on this method uses a two-level script language parsing technique, and can automatically generate all the test cases with control structure and data flow which satisfy the optimization technique to be tested. So far this tool has been successfully used in the testing of an embedded optimizing compiler and receives satisfying effect.