This repository implements a bare-bones demonstration of the Orion algorithm discussed in the research paper "Compiler Validation via Equivalence Modulo Inputs" (the paper is available here among other places).
Orion is designed to find compiler bugs via an innovation called Equivalence Module Inputs, called EMI for shot. The "inputs" to the Orion algorithm are a compiler that we wish to find bugs in and some unit tests for that compiler (i.e. code the compiler is supposed to compile). Orion then loops over all unit tests and uses them to find bugs as follows:
Given a unit test, it first compiles the test with the provided compiler. Then it chooses a subset of inputs from the domain of the executable (e.g. if the unit test takes two integers as input, it might choose to run the test for {(0, 0), (1, 1), (4, -10)}). It runs the executable with each of those inputs and stores coverage information. It uses the coverage information to find code regions that are dead for the whole chosen subset of inputs. Since these are dead regions (w.r.t. these inputs) Orion is free to modify the regions without changing the behaviour of the executable (w.r.t. these inputs). Therefore we can modify the original unit test's dead regions arbitrarily - Orion just chooses to delete a few randomly chosen statements out of those regions. We now have an original unit test and a set of modified unit tests that behave the same way for our chosen input subset. This group of tests is called "equivalent modulo input". Since all tests should behave the same way, we can now use our compiler to compile the modified tests and then execute them to see if the behaviour stays the same. If it doesn't, we have found a bug in our compiler.
This repository implements the Orion algorithm and an accompanying compiler in Scala. The compiler is just for demonstration purposes and compiles from a subset of Scala to a subset of Scala (which I called Smala) while doing some simple optimization. The Smala files can be executed by parsing them into an AST and then simulating the execution. Another option would have been to excute the files using reflection but simulating the execution is fairly easy, so reflection isn't really worth it.