Code – Random C Program Generator
This is a program I wrote for testing compilers. I used it to find bugs in several compilers, including early versions of LLVM. It has long been surpassed in functionality by follow-on projects, but I still get mail regularly for the original source code (which is much simpler to read & edit).
In 2008, John Regehr & Eric Eide made significant extensions and improvements on this framework including support for volatile variables. See their paper (and new source code).
Original Version:
Random Program Generator [.zip]
Updated: 11-Jan-2007
It generates a random program of arbitrary complexity, including a call graph with specified depth, arbitrarily complex expressions of functions and binary operations, and basic for loops. The program is designed to compile without any errors, and never execute any obviously illegal actions (ie: uninitialized variables). The program generates a hash of the global data structures before termination and prints this to standard out.
Testing a compiler becomes a simple matter of generating an infinite series of random programs, compiling them, and executing them. The programs should never crash (but may run for unbounded time), and the output is entirely dependent on the flow of control. This can be used to test the optimizer by compiling the same source in debug and optimized mode, then comparing the outputs. Differences in output generally signal errors in the optimizer.
The program generator is completely self-contained, and requires no platform specific features (I do call a platform specific seed generator, but this is not strictly necessary). The random number generator is also self-contained and should execute exactly the same for all platforms (thus, the seed number directly corresponds to the generated output, and may be used in a bug report in lieu of full source code).
The program generator operates off a set of probability functions for all important aspects of program generation. These probabilities determine the shape of the final program.
Random C/C++ Program Generator
- Create a set of random types to be used throughout the program
- Create the main func.
- Generate a random block of statements with maximum control & expression nesting depths.
- If new functions were defined in #3, then loop back to fill in it’s body.
- When a maximum number of functions is reached, stop generating new functions and finish off the bodies of the remaining funcs.
- Output generated program.
GOALS:
- Locate basic errors in compiler front-ends (crashes, etc).
- Ferret out correctness errors in optimization passes.
- Support the design of tools to search for improved optimization paths (partial execution, etc).