Hi, first, this is a real project proposal for GCC 4.2, not a joke, although I have to confess that I have had fun to "filer la metaphore" from http://gcc.gnu.org/wiki/Sample%20Project%20Page
You can find the same proposal at http://gcc.gnu.org/wiki/Omega%20data%20dependence%20test Have fun, Sebastian Omega data dependence test We propose a Practical Oracle Program (POP) for exactly solving Integer Linear Programs (ILP): an adaptation of Bill Pugh's Omega solver (BOP) that is experimentally known to be fast for small problems, but is also known to be exponential in general. Another choice of POP that will probably be submitted for a future release is Paul Feautrier's Parametric Integer Programming (PIP), that is known to have a good behavior for larger problems, but still is an exponential Oracle. In general, we like POPs to be expressive enough for being able to solve a broad range of problems: it is this exponential worst case fear that gives POPs their mystic traits, but we will try to "demystify the mystified". In this first step, we're proposing a formulation of the data dependence tests as queries to BOP, and a flag that tests the validity of the current Banerjee Analyzer for Data-dependences (BAD) against the predictions of BOP. The regression flag is not enabled by default, such that the POP will never be executed for normal uses of the compiler. Personnel * Sebastian Pop * Daniel Berlin Delivery Date This project will be ready for the first stage of GCC-4.2. Benefits * Bug masters will have a tool for checking the correctness of the dependence analysis. * The flag will allow users to report bugs in the implementations of these two solvers. Dependencies None for the moment. Modifications Required Adding some new files, a flag, and some code in tree-data-ref.c that formulates the data dependence problem as a constraint system in a format that BOP understands. More fun (take a seat, laugh a bit) The rest is just science fiction, so if you're the Release Manager (RM) of GCC, you can skip all the rest, unless you want to have more fun on the [Oracular Optimizations|Sample Project Page], and see a practical implementation of a meta-POP. So what happens next? Based on queries to a POP, we will be able to propose several flags to test the regressions of our heuristics with respect to optimal behavior: the current analyzers and optimization decisions will be compared to the results of the exactly solved problem as predicted by the POP. This kind of costly regression flags will be used by Super Enthusiasts of Betacompilers (SEB) such as the gentoo-ers, BSD-ers, or system embedd-ers, that have nothing else to do than recompiling the world, whatever the price, whatever the time they have to spend, in the hope that they'll obtain a faster code. In a further future, when GCC will finally have a proper intermediate representation that can be stored to disk and then loaded back to memory, we will transform the SEB into GCC contributors. The plan is to propose the integration of a delta debugger (DD) into GCC such that the regression flags will directly output a reduced pattern that will show the regression. A pattern-zilla will collect the optimal solution and a testcase that show the weakness of a heuristic function. SEB will act at a first meta-level as a POP for the code of the compiler itself. And for ending the induction, I'll let your imagination to come up with ideas of how to implement the next meta-level. I have to acknowledge that Kenneth Zadeck has pushed me into all this, and thus the first step of the induction was initiated by Kenny.
