Debugging and Testing Optimizers through Comparison Checking

AbstractWe present a novel technique called comparison checking that helps optimizer writers debug optimizers by testing, for given inputs, that the semantics of a program are not changed by the application of optimizations. We have successfully applied comparison checking to a large class of program transformations that alter (1) the relative ordering in which values are computed by the intermediate code statements, (2) the form of the intermediate code statements, and (3) the control flow structure using code replication. We outline the key steps that lead to the automation of comparison checking. The application of comparison checking to test the implementations of high level loop transformations, low level code optimizations, and global register allocation for given program inputs is then described