Re: [GCC 4.2 Project] Omega data dependence test

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

Dan Kegel wrote:
> Sebastian Pop wrote:
> > [http://gcc.gnu.org/wiki/Omega%20data%20dependence%20test]
> > ...
> I can't understand a word of the proposal.
> Mabe you were trying to be funny, but it ended up being obscure.

I'm sorry.  This was not my intent.

> If the average gcc developer can understand it, then
> it doesn't matter that I can't, but I have a feeling
> others might find it hard to read, too.
> 

I'll try to explain again the goal of the project in a shorter
version.  I have implemented a data dependence analysis, and I want to
validate the results that it produces.  For this, I'm proposing to
compute the same information using another algorithm, and finally do a
diff.

The second implementation of the data dependence analysis is using the
Omega solver.  However, this solver is known to be exponential on some
cases (not all the cases, and in practice when used for basic data
dependence problems it is fast).  So the only option we have is to not
expose this solver to our users, but use it for debugging and
improving the compiler.

This was also the purpose of the long term "plans": we can use this
kind of expensive yet exact analyzers to detect deficiencies in the
compiler, and report bugs.

> But this part caught my eye:
> 
> >  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.
> 
> Since I started playing with delta debugging for
> tracking down ICEs, I've been thinking it might
> be nice to have an option to gcc to perform
> delta debugging automatically if an ICE occurs,
> and have it automatically submit the minimized
> testcase.  

Exactly.  For example, it will be possible to replace the fancy_abort
with a DD.  

Another thing that users of the compiler want is an automatic variable
renaming, such that the testcase that they provide does not reveal
parts of their projects.  All these can be integrated in GCC once we
have this intermediate representation dump to disk.

> Sounds like you're talking about something
> similar, but not for ICEs.  I wish I understood your
> proposal better.

As Daniel Berlin has pointed out, a smarter DD can be implemented
directly in the compiler.  What is guiding the current DDs is a fail
to a test: the ICE.  The same thing can be implemented in the
compiler, and you can have as an objective to minimize the size of the
representation while still preserving a feature of the original
program.  This feature can be, for example, a regression with respect
to an optimal solution.

So clearly you have two paths for detecting regressions: either you
evaluate a run of the produced code on some machine and for a given
input data (something like Anthony's regression hunting), or you
attack the results of the heuristic functions with an exact solver, as
written by Mark in the oracular optimization page.

Sebastian