Random test generation for compiler optimization

[0002] The present invention concerns compiler optimization and pertains particularly to the use of random test generation to test code generated by an optimizing compilation system.

[0003] Programs are generally written in a high level programming language. This high level language, often referred to as source code, is translated by a compiler program into an assembly language. The binary form of the assembly language, called object code, is the form of the code actually executed by a computer. The object code is generally first produced in object code modules. If there is more than one object code module, the object code modules are linked together by a linker. For the purpose of the present application, the term “compile” includes both the process of producing the object code modules and linking the object code modules together.

[0004] In order to increase performance of object code when executed by a target computer, compiled code is frequently optimized. As compiler optimizations have been becoming more complex and aggressive, testing these optimizations has become increasingly difficult.

[0005] Today's state-of-the-art compilers perform a variety of optimizations to improve the performance of compiled code. See, for example, Aho, A. V., Sethi, R. and Ullman, J. D., Compiler Principles, Techniques and Tools, Addison-Wesley (1986). Because of industry pressure for better performing code and faster compilation, there has been a steady growth in the number and complexity of optimizations used by compilers. For example, to avoid the phase ordering problem, multiple optimizations are merged together or a single optimization is implemented in several phases. Optimizations are using more sophisticated analyses, such as register pressure estimates, to identify when an optimization is beneficial. To cut down on compile time, complex data structures are reused across optimizations. Incremental updates are performed to keep this data up to date. Each of these increases in compiler complexity impose an additional risk of defects in the compiler.

[0006] Quality is paramount for a production compiler. Bugs in the optimizer often result in incorrectly running compiled code, which is very difficult for an end-user to debug. Also, users of compiler systems respond to compiler bugs by either turning off optimization altogether or moving to a different compiler or platform.

[0007] To ensure quality in a production compiler, extensive software design and testing processes are strictly adhered to, including design documents, code reviews, black-box testing, white-box testing, and integration testing. See for example, Beizer, B, Software Testing Techniques(2nd edition); Van Nostrand Reinhold (1990), Boujarwah, A and Saleh, K, “Compiler Test Suite: Evaluation and Use in an Automated Test Environment”, Information and Software Technology, Vol. 36, No. 10, (1994), pp. 607-614; and Myers, G, The Art of Software Testing, John Wiley (1979). Despite all this, significant numbers of defects still occur in optimization. Many of these defects are due to subtle interactions between different optimizations or from overlooked corner cases. Writing an exhaustive set of tests that covers all possible cases and interactions between optimizations is impossible given the infinite number of legal source programs as well as the combinatorial number of possible interactions between optimizations.

[0008] Automatic test generation is used extensively for testing hardware. Automatic test generators have also been developed to test various kinds of software. For a review of automatic test generation for compilers, see Burgess, C. J., “The Automated Generation of Test Cases for Compilers,” Software Testing, Verification, and Reliability, Vol. 4, No. 2, (1994), pp. 81-94. Most of the earliest work on automatic test generation concentrated on testing the parser and code generator of compilers. See, Bazzichi, F., and Spadafora, I., “An Automatic Generator for Compiler Testing”, IEEE Transactions on Software Engineering, Vol. SE-8, No. 4, (1982), pp. 343-353; Celentano, A., Crespi-Reghizzo, S., Della-Vigna, P., Ghezzi, C., Granata, G., and Savoretti, F., “Automatic Generation of Test Cases,” Software Practice and Experience, Vol. 10, (1980), pp. 897-918; Hanford, K. V., “Automatic Generation of Test Cases,” IBM Systems Journal, Vol. 9, No. 4, (1970), pp. 242-257; and, Purdom, P., “A Sentence Generator for Testing Parsers,” BIT, Vol. 12, (1972), pp. 366-375. Such test generators produce random source code from a formal grammar of the source language. The compiled code generated from these random source programs cannot be executed.

[0009] Bird, D. L., and Munoz, C. U., “Automatic Generation of Random Self-Checking Test Cases”, IBM Systems Journal, Vol. 22, (1983), pp. 229-245 disclose some of the earliest work performed in field of automatic generation of executable random tests for compilers. This test generator consists of a loop that randomly selects the next kind of statement to be generated, then invokes a subroutine to produce that statement. Self-checks are inserted into the randomly generated program to ensure that it is producing correct results. Because of this, the test generator must predict the values produced by executing the program. This required restrictions to be made on the control flow behavior of the program. More specifically, iterations of a loop cannot use values produced by other iterations.

[0010] A language-independent automatic generator of executable programs was disclosed in Burgess, C. J., “Towards the Automatic Generation of Executable Programs to Test a Pascal Compiler,” Barnes, D. and Brown, P. (eds), Software Engineering'86, IEEE Computing Series Vol. 6, Peter Peregrinus Ltd., (1986), pp. 304-316. This test generator is driven by a grammar annotated with synthesized and inherited attributes to ensure semantic correctness. The generator predicts the correct values produced by their generated programs and inserts self checks to ensure correctness. To allow the correct prediction of values in a program, all loops are constrained to execute only one iteration.

[0011] In Burgess, C. J., and Saidi, M., “The automatic generation of test cases for optimizing Fortran compilers”, Information and Software TechnologyVol. 38 No. 2, (1996), pp. 111-119, a previous test generator was extended to specifically test optimizations. The enhanced test generator delays performing self-check tests on a variable as long as possible, since these self-checks interfere with optimization. This paper also discloses a modified test generator which explicitly produces common subexpressions and induction variables in a randomly generated program.

[0012] Seaman, R. P, “Testing high level language compilers”, IEEE Computer System and Technology Conference, (1974), pp. 6-14, discloses an algorithm which compiles a randomly generated program with two different compilers, executes both versions of the program and compares the results. If the results are different, there must be a bug in one of the compilers.

[0013] In accordance with the preferred embodiment of the present invention, an optimized compiler is tested. Code segments are stored in a segment file. Each code segment includes a description of an external interface with other segments. A source function is built using the code segments. The source function is compiled using optimization to produce first executable code. The source function is also compiled without using optimization to produce second executable code. The first executable code is executed to produce first results. The second executable code is executed to produce second results. The first results are compared with the second results. An error is reported when the first results differ from the second results.

[0014] For example, the source function is built by first choosing a code segment to add to the source function which has an output variable which is of a same type as a return value for the source function. Then additional segments are chosen to add to the source function. Each additional segment, when chosen, has an output variable which is of a same type as an undefined variable in the source function. When there are no undefined variables remaining in the source function, the source function is completed. In the preferred embodiment, after a predetermined number of code segments have been added to the source function, only code segments with no input variables are additionally added to the source function.

[0015] Also in the preferred embodiment, the external interface for each code segment includes a list of any input, output and local variables used by the code segment. Additionally, a type is indicated for each variable in the list. To simplify construction of the source function, each code segment has exactly one output variable.

[0016] Various enhancements are added in different embodiments of the present invention. For example, a subset of the code segments may include a segment function which acts as a subsegment. Each segment function includes as arguments any input and output variables for the segment function.

[0017] Also code segments can include header segments. In various embodiments of the present invention, scoping constraints are added to a subset of the code segments include scoping constraints. Further, in order vary the likelihood of each code segment being used, the code segments are assigned weights which vary a likelihood of each segment being used. A subset of the code segments include arrays as input variables.

[0018] The present invention provides for an efficient and effective way for random testing of an optimized compiler.

[0019] FIG. 1 shows a block diagram of a testing system in accordance with a preferred embodiment of the present invention.

[0020] FIG. 2 is a flowchart which summarizes the testing performed by the testing system shown in FIG. 1 in accordance with a preferred embodiment of the present invention.

[0021] FIG. 1 shows a block diagram of a compiler testing system in accordance with a preferred embodiment of the present invention. A random source code generator engine 20 uses code segments in a segment file 12 to generate identical source code function 11 and source code function 10. As illustrated by blocks 12 and 13, source code function 11 is compiled with optimization and the produced optimized code is executed. Also, as illustrated by blocks 14 and 15, source code function 10 is compiled without optimization and the produced nonoptimized code is executed. As illustrated by a block 16, the results of each execution are compared and, as illustrated by a block 17, the errors are recorded. Using the preferred embodiment, thousands of tests can be generated, compiled and run in this manner in under an hour.

[0022] Random source code generator engine 20 works by randomly generating source code function 11 and source code function 10. The rules on how to randomly generate source code function 11 and source code function 10 is stored in segment file 21. Segment file 21 describes the grammar of the language for which to generate random programs, and contains constraints to ensure correctness. In the preferred embodiment, segment file 21 allows one to generate specific code sequences, allowing the user to stress a single component or phase.

[0023] To maximize the usefulness of random source code generator engine 20, there are several requirements on the type of random functions that random source code generator engine 20 can generate. First, random source code generator engine 20 is able to generate executable functions, since the majority of compiler defects only show up in the execution of the compiled programs. Second, the executable functions return a comparable result, so that it is possible to differentiate between correctly running and incorrectly running functions. Third, the executable functions are deterministic, so that their results won't vary with optimization. For example, undefined variables are allowed. Fourth, the generated functions have some resemblance to actual user code. This means, for example, avoiding sequences that are common in random code but uncommon in real programs, such as large amounts of unreachable or dead code. Finally, random source code generator engine 20 provides an ability to easily restrain or extend the kinds of random code it generates, so that a user can specialize it to test one particular optimization phase or extend it to handle new cases.

[0024] In the preferred embodiment, random source code generator engine 20 is small and relatively language-independent. This allows for maximum flexibility. All language specific syntax or semantics is placed in segment file 21.

[0025] Segment file 21 tells random source code generator engine 20 how to generate a random function. More specifically, segment file 21 contains a collection of code snippets called segments. Random source code generator engine 20 generates a random function by generating a random sequence of these segments. To ensure that random source code generator engine 20 generates a deterministic, executable function, each segment in segment file 21 is annotated with input and output information so to ensure that a valid sequence of segments is generated. Some examples of segments are shown in Table 1 below:

[0026] A segment consists of a snippet of legal source code enclosed by BEGIN/END markers. The legal source code is preceded by one or more special statements which name the input, output, inout, and local variables of the code snippet. The four possible special statements are INPUT, OUTPUT, INOUT, and LOCAL. The type of each variable is declared in each special statement. In the preferred embodiment, a variable can occur in only one of these statements and at most once in that statement. Also in the preferred embodiment, each segment is required to have either exactly one output variable or one inout variable. This restriction eases the implementation of the algorithm for random source code generator engine 20.

[0027] The special statements are needed for several purposes. First, the special statements describe all the variables used within the segment. This allows random source code generator engine 20 to rename these variables to avoid name clashes between segments. Second, the special statements describe the interfaces of the segment. That is, the special statements describe what variables are produced or consumed by the segment, so that it can ensure that other segments would consume or produce these variables, so as to avoid generating programs with undefined variables or dead code. Inout variables are treated as both input and output variables. Third, the type specified for each variable is used to ensure that there are no type mismatches of variables shared across two or more segments. The type is also used by Random source code generator engine 20 to generate the type declarations for the variables.

[0028] FIG. 2 shows the testing as orchestrated by random source code generator engine 20. In a step 31, two procedures with the same body of code are generated. The body is generated via the generate_func_body( ) algorithm shown below in Table 2. Compiler pragmas are also generated to enable optimization for one of the procedures and to disable optimization for the other. This step can be repeated many times to generate many tests in a single source file.

[0029] In a step 32, the main program is generated. The main program calls each pair of procedures generated earlier and compares their results. If they differ. An error message is printed out.

[0030] In a step 33, the generated source file is compiled. In a step 34 it is determined whether any compile-time errors occurred. If so, in a step 35, the source file and the errors are saved.

[0031] In a step 36, the compiled source file is executed. In a step 37 it is determined whether any failures occurred during execution. If so, in a step 38, the source file and errors are saved. If there were no errors detected, in a step 39 the source file is discarded.

[0032] In a step 40, the test may be repeated as often as desired. For example, the test may be repeated using either the same or a different segment file.

[0033] Table 2 below shows the basic algorithm (generate_func_body( )) for generating a random procedure used by random source code generator engine 20.

[0034] As shown by the algorithm in Table 2, random source code generator engine 20 generates code for a function body from the bottom-up, starting with the return statement of the function. Random source code generator engine 20 first generates a statement that returns the return-value (_retval). Random source code generator engine 20 then inserts the return value (_retval) into the set of undefined variables (U) and the set of procedure-local variables (P). Random source code generator engine 20 then enters the main loop of the algorithm, which iterates until there are no more undefined variables. For each iteration of the loop, random source code generator engine 20 removes a variable (v) from the set of undefined variables (U), chooses a segment that defines that variable's type, and prints out that segment after some renaming. More specifically, the first step is to choose a segment whose output variable has the same type as the undefined variable. (The algorithm for choosing a segment is set out in Table 3 below). If the segment's output variable is an inout variable, the variable is put back into the set of undefined variables (U). Random source code generator engine 20 then makes a copy of the segment's body and renames all occurrences of the segment's output variable in the copy of its body to be the undefined variable (v). Finally, the iteration must handle all the input and local variables in the segment. For each input and local variable (x), Random source code generator engine 20 comes up with a new, unique name for the variable (y) and renames that variable (x) to its new name (y). Random source code generator engine 20 also adds the new variable to the set of procedure local variables (P) and if the variable is an input variable, to the set of undefined variables (U) as well. When the while loop finishes, the algorithm generates a declaration for each procedure local variable.

[0035] Table 3 below sets out an algorithm (choose_a_segment( )) by which random source code generator engine 20 chooses a segment.

[0036] The algorithm shown in Table 3 takes two arguments: the desired type for the output variable of the to-be-chosen segment (t), and the number of segments generated so far (n). If n is less than the maximum number of allowed internal segments, (i.e., segments with inputs), the algorithm simply returns some random segment whose output variable type is t. However, if n exceeds the maximum number of allowed internal segments, the algorithm imposes the additional constraint that the returned segment has no input nor inout variables. This was done to prevent the algorithm from generating a random program with potentially infinite number of segments, thus ensuring that the algorithm terminates. If for some reason, random source code generator engine 20 cannot find a segment with the imposed constraints on input and output variables, random source code generator engine 20 generates an error and aborts.

[0037] Table 4 below sets out an example procedure generated by random source code generator engine 20 using the segments set out in Table 1 above and the algorithms set out in Table 2 and Table 3 above:

[0038] Random source code generator engine 20 begins by generating the statement “return _retval” and inserting the variable _retval in the set of undefined variables and the set of procedure local variables. Random source code generator engine 20 then enters the main while loop of function generate_func_body( ). This iterates until there are no more undefined variables. On the first iteration, the loop removes _retval from the set of undefined variables. Function generate_func_body( ) then calls choose_a_segment( ) with the type of _retval (int) and the number of segments generated so far (0). Now since the number of segments generated so far is less than the maximum number of internal segments, (for example, max_internal_segs is 3 for this example), function choose_a_segment( ) can use either segment (b) or segment (c). For example, segment (c) is randomly chosen from these two segments and returned. Next, random source code generator engine 20 renames the output variable z of the segment's body (“z=(int) x;”) to _retval, then renames the input variable x to new variable v1. Random source code generator engine 20 then adds v1 to the set of undefined variables and the set of procedure-local variables. At the end of the iteration, the updated text of the segment's body is prepended to the start of the procedure's body. This process continues until there are no more undefined segments. Termination is guaranteed since after max_internal_segs number of segments are generated, the routine choose_a_segment( ) restricts the set of legal segments to either segment (a) or (b). Once there are no more undefined variables, random source code generator engine 20 inserts a declaration for each procedure-local variable and returns.

[0039] In an alternative embodiment of the present invention, random source code generator engine 20 is extended to randomly generate control flow.

[0040] To support control flow, a new SEGMENT( ) function is added to segment file 21 syntax. The SEGMENT( ) function is a subsegment which is used in the body of a segment to indicate locations where random source code generator engine 20 should insert randomly generated code. When a segment's body is added to the code of the random program, all SEGMENT( ) functions in that body are replaced with randomly generated sequences of segments. This allows random source code generator engine 20 to generate random, structured control flow without needing explicit knowledge on how specific control flow constructs work.

[0041] Some examples of uses of the SEGMENT( ) functions are set out in Table 5 below.

[0042] The SEGMENT( ) function takes several arguments, which describe the variables to be used or defined by the random code sequence that will replace the SEGMENT( ) function. Each argument of a SEGMENT( ) function is prepended by an IN, OUT, or INOUT keyword, so to identify if the given variable is to be used, defined, or used and modified.

[0043] The algorithm for generating random code for a SEGMENT( ) function is similar to the algorithm set out in Table 2, but with a few modifications. At the start of the algorithm, all OUT and INOUT arguments are placed in the undefined variable set. Also, whenever a new segment is chosen, before putting all input and inout variables of that segment in the undefined set, an attempt is made to match the input and inout variables with all unmatched IN and INOUT arguments. If an input/inout variable is the same type as an unmatched IN/INOUT argument, that variable is matched with the argument, the variable is renamed to the IN/INOUT argument's name, and the variable is not placed in the undefined variable set. If max_internal_segs number of segments is not generated yet, some random subset of the segment's input variables are purposely not matched to the IN arguments, so to encourage longer random code sequences. Occasionally, copies are inserted to resolve naming conflicts of INOUT arguments, where the names of the input and output variables matched with the INOUT argument do not match.

[0044] The algorithm for choosing a segment, set out in Table 3 is modified to handle control flow. First, when more than max_internal_segs have been generated, instead of using segments with no inputs, the algorithm only uses the segments whose input variable's can match the unmatched IN arguments, (i.e., there are no more input variables of a particular type than the number of unmatched IN arguments of that type). Also, any segments containing a SEGMENT( ) function are not allowed when there are more than max_internal_segs segments. This is to prevent the algorithm from generating programs with infinitely deep nesting of control flow.

[0045] One issue with the above modifications to handle SEGMENT( ) functions is that it is possible for the algorithm to generate random code sequences for a SEGMENT( ) function that do not use all the IN arguments. Although this does not result in incorrectly running programs, it is undesirable since it can result in a lot of dead code. This issue is partially remedied by extending the algorithm for choosing a segment to perform some lookahead to identify specific candidates. This technique is not foolproof, but it does make it less likely for unresolved IN arguments to occur.

[0046] Other preferred embodiments of the present invention include extensions that are added to random source code generator engine 20 to improve its usefulness. For example, header segments are used. This allows specification of code in the header of a randomly generated program so that it is possible to specify global variables, constants, and type declarations.

[0047] Also random number/token generators are used to cut down on the number of segments that need to be written in order to specify some random range of numbers, (e.g., from −2 to 2) or some random token, (e.g., ‘+’, ‘−’, ‘*’, ‘/’).

[0048] Also, in various embodiments of the present invention, segments are assigned weights to make the segments more or less likely to be used.

[0049] Further, multiple input (INM) arguments and multiple input/output (INOUTM) arguments of SEGMENT functions are provided for. This allows certain input to be used multiple times, (e.g., the induction variable of a loop or array types). To allow this, the two additional qualifiers for SEGMENT function arguments (IN and INOUTM) are added.

[0050] Also scoping constraints are used. The scoping constraints restrict the places where a segment can be used to particular instances of SEGMENT functions. For example, if a segment uses the break statement in C, the use of that segment is restricted to loop or switch bodies. To allow this, segments are labeled with a particular scope type and specific SEGMENT( ) functions are labeled with that type. Also global (SGLOBAL) variables are used.

[0051] Random source code generator engine 20 can be used to generate random loops with arrays accesses. A simplified example of segments random source code generator engine 20 uses to generate random code with arrays is shown in Table 6 below:

[0052] Table 7 shows an example of random code random source code generator engine 20 generates from the segments shown in Table 6 above.

[0053] In the example shown in Table 7 above, a new type called int_arrays is declared in the header segment of the algorithm shown. Header segments are described above. The new type called int_arrays declares an integer array. By doing this, arrays can be used as inputs, outputs and local variables in segments.

[0054] Also, in the header segment there is declared a new type called index to hold the array index. A special type for array indices is declared so that array index variables can be specified as inputs or outputs of segments without the worry of out-of-bounds errors. Also, a segment is included that collapses an array to a single checksum integer so that all of the elements of an array can contribute to the return value of the procedure. With careful design of the segment file 21, more complex examples can be generated with multidimensional arrays, multiply nested loops, complex array indexing, and other characteristics of array intensive programs.

[0055] The foregoing discussion discloses and describes merely exemplary methods and embodiments of the present invention. As will be understood by those familiar with the art, the invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. Accordingly, the disclosure of the present invention is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.