[GCC 4.2 Project] Omega data dependence test

[Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>]

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.