re: [GCC 4.2 Project] Omega data dependence test

re: [GCC 4.2 Project] Omega data dependence test

[Dan Kegel]

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.
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.

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.  Sounds like you're talking about something
similar, but not for ICEs.  I wish I understood your
proposal better.
- Dan

-- 
Trying to get a job as a c++ developer?  See http://kegel.com/academy/getting-hired.html

re: [GCC 4.2 Project] Omega data dependence test

[Daniel Berlin]

On Mon, 2005-08-08 at 08:40 -0700, Dan Kegel wrote:
> Sebastian Pop wrote:
> 
> 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.  Sounds like you're talking about something
> similar, but not for ICEs.  I wish I understood your
> proposal better.

If we wrote our IR in a sane form, we could do delta debugging in a sane
way, instead of line-wise.

IE remove entire basic blocks at a time, etc.

> - Dan
> 

RE: [GCC 4.2 Project] Omega data dependence test

[Dave Korn]

----Original Message----
>From: Dan Kegel
>Sent: 08 August 2005 16:41

> Sebastian Pop wrote:
>  > [http://gcc.gnu.org/wiki/Omega%20data%20dependence%20test]
>  > ...
> I can't understand a word of the proposal.

  Well, I'll pitch in, because I also wasn't sure at first whether it was
for real and what it was about, but I think I know now.  Did you google
"bill pugh omega solver" and do some background reading?  It didn't take me
too long to get the basic gist of what they're proposing (or at any rate, to
_think_ I had got it!).

  IIUIC, they want to use a linear-algorithm solver to verify the
data-dependence analyses performed by the Bannerjee analyzer by recomputing
the results from an alternative formulation so as to have a 'second opinion'
to compare the output of gcc's current analyses against.[*]

> Mabe you were trying to be funny, but it ended up being obscure.

  Although the last paragraph was purely tongue-in-cheek humour, the rest
looks genuine.  But by the time it gets to the bit about SEB and POP, I
think it's just referring to Seb Pop!

> 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.

  The more esoteric fields of compiler design just _are_ incredibly dense,
theoretical, and hard-to-comprehend without spending a few years at
university studying them.  Unfortunately, that's just the way it is.

    cheers,
      DaveK

[*] - To a first approximation. ;)
-- 
Can't think of a witty .sigline today....

Re: [GCC 4.2 Project] Omega data dependence test

[Sebastian Pop]

Dave Korn wrote:
> 
>   Well, I'll pitch in, because I also wasn't sure at first whether it was
> for real and what it was about, but I think I know now.  Did you google
> "bill pugh omega solver" and do some background reading?  It didn't take me
> too long to get the basic gist of what they're proposing (or at any rate, to
> _think_ I had got it!).
> 
>   IIUIC, they want to use a linear-algorithm solver to verify the

Omega is not linear: it has a worst case exponential time.  It however
does solves systems of linear (in)equalities, or just linear
constraint systems.

> data-dependence analyses performed by the Bannerjee analyzer by recomputing
> the results from an alternative formulation so as to have a 'second opinion'
> to compare the output of gcc's current analyses against.[*]
> 

Yes.

Re: [GCC 4.2 Project] Omega data dependence test

[Sebastian Pop]

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

Re: [GCC 4.2 Project] Omega data dependence test

[Joe Buck]

On Mon, Aug 08, 2005 at 08:35:31PM +0200, Sebastian Pop wrote:
> 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.

Algorithms that are sometimes exponential can still be used if there is
a cutoff mechanism, to abort the algorithm if it exceeds a budget.  This
assumes that we can then fall back to an algorithm that might produce
inferior results, but will produce something usable in reasonable time.

For example, binary decision diagrams are commonly used in digital logic
optimization and formal verification, even though they can require
exponential space.

Re: [GCC 4.2 Project] Omega data dependence test

[Sebastian Pop]

Joe Buck wrote:
> Algorithms that are sometimes exponential can still be used if there is
> a cutoff mechanism, to abort the algorithm if it exceeds a budget.  This
> assumes that we can then fall back to an algorithm that might produce
> inferior results, but will produce something usable in reasonable time.
> 

Okay, I stand corrected.  As a practical implementation we can have a
mechanism as push/pop timevar, that would monitor the time and space
of an algorithm and that can cancel the computation for failing on a
safe approximation.  As a first concretization, I was thinking to use
threads, but I'm not sure whether this is suitable for GCC.

Re: [GCC 4.2 Project] Omega data dependence test

[Joe Buck]

On Tue, Aug 09, 2005 at 04:59:28PM +0200, Sebastian Pop wrote:
> Joe Buck wrote:
> > Algorithms that are sometimes exponential can still be used if there is
> > a cutoff mechanism, to abort the algorithm if it exceeds a budget.  This
> > assumes that we can then fall back to an algorithm that might produce
> > inferior results, but will produce something usable in reasonable time.
> > 
> 
> Okay, I stand corrected.  As a practical implementation we can have a
> mechanism as push/pop timevar, that would monitor the time and space
> of an algorithm and that can cancel the computation for failing on a
> safe approximation.  As a first concretization, I was thinking to use
> threads, but I'm not sure whether this is suitable for GCC.

The problem with using time as a cutoff is that you then get results that
can't be reproduced reliably.  Better to count something that is a feature
of the algorithm, e.g. number of executions of some inner loop, number of
nodes visited, or the like, so that all users get the same results.

Re: [GCC 4.2 Project] Omega data dependence test

[Sebastian Pop]

Joe Buck wrote:
> The problem with using time as a cutoff is that you then get results that
> can't be reproduced reliably.  Better to count something that is a feature
> of the algorithm, e.g. number of executions of some inner loop, number of
> nodes visited, or the like, 

On the other hand, it is not based on such features that you'll be
able to provide a watermark on time and space... Having guarantees on
compile time and space is probably what some users will want instead
of yet another bunch of --param max-foo-nodes.

I'd like to ask GCC users in general: how many are using these params?

Why not having instead a set of flags that limit the resources allowed
for each "unnecessary" (to be defined...) part of the compiler?  For
example, I'd like a guarantee that any tree level optimizer will stop
after at most 5 seconds and at most 300M of garbage: you'd say,
-fbudget-time=5 and -fbudget-space=300M instead of having to deal with
some obscure params.

> so that all users get the same results.

I see your point: we'll have bug reports that will be difficult to
reproduce.  I have not yet thought at a solution for this one, but
there should be some practical way to make bugs deterministic again,
otherwise we'll just step into a Schrodinger box, and that's a Bad
Thing.

seb

Re: [GCC 4.2 Project] Omega data dependence test

[Daniel Berlin]

On Sun, 2005-08-14 at 01:12 +0200, Sebastian Pop wrote:
> Joe Buck wrote:
> > The problem with using time as a cutoff is that you then get results that
> > can't be reproduced reliably.  Better to count something that is a feature
> > of the algorithm, e.g. number of executions of some inner loop, number of
> > nodes visited, or the like, 
> 
> On the other hand, it is not based on such features that you'll be
> able to provide a watermark on time and space... Having guarantees on
> compile time and space is probably what some users will want instead
> of yet another bunch of --param max-foo-nodes.

Sebastian,  I really think you are worrying too much.
It's pretty rare that it will take going all the way to omega to be able
to disambiguate two dependences.

Re: [GCC 4.2 Project] Omega data dependence test

[Sebastian Pop]

Daniel Berlin wrote:
> 
> Sebastian,  I really think you are worrying too much.

right.

> It's pretty rare that it will take going all the way to omega to be able
> to disambiguate two dependences.
> 

for dependence tests we exercise only a limited part of omega, but now
suppose that we'll use omega for other purposes, for example cache
miss equations, scheduling, regalloc, etc.  One of these users will
sooner or later end by triggering the exponential bullet.

Re: [GCC 4.2 Project] Omega data dependence test

[Daniel Berlin]

On Sun, 2005-08-14 at 13:14 +0200, Sebastian Pop wrote:
> Daniel Berlin wrote:
> > 
> > Sebastian,  I really think you are worrying too much.
> 
> right.
> 
> > It's pretty rare that it will take going all the way to omega to be able
> > to disambiguate two dependences.
> > 
> 
> for dependence tests we exercise only a limited part of omega, but now
> suppose that we'll use omega for other purposes, for example cache
> miss equations, 
Most cache miss equations are using distance numbers, which we don't
always need to go all the way to omega to get.

> scheduling, 

Dependence again :)

> regalloc, 

Dependence again :)

> etc.  One of these users will
> sooner or later end by triggering the exponential bullet.

Only if you use such a big hammer for every small nail :)

Re: [GCC 4.2 Project] Omega data dependence test

[Ian Lance Taylor]

Sebastian Pop <sebastian.pop@cri.ensmp.fr> writes:

> I'd like to ask GCC users in general: how many are using these params?

We use them at my current employer, mainly to remove limits which were
imposed to keep compile time under control.  We have code which needs
to run as fast as possible, for which compile time is, by comparison,
irrelevant.  So we drastically bump up the values for parameters like
large-function-growth, inline-unit-growth, and
max-pending-list-length.  And it makes a huge difference in the
generated code.  But if I weren't there to give advice, I have low
confidence that they would know about --param at all.

> Why not having instead a set of flags that limit the resources allowed
> for each "unnecessary" (to be defined...) part of the compiler?  For
> example, I'd like a guarantee that any tree level optimizer will stop
> after at most 5 seconds and at most 300M of garbage: you'd say,
> -fbudget-time=5 and -fbudget-space=300M instead of having to deal with
> some obscure params.

I have to agree that having 69 different parameters is a lot more
useful for compiler developers than it is for compiler users.  Some of
the parameters, like large-function-growth, are fairly easy to
understand and to use, particularly in conjunction with -Winline.
Some of the other parameters, like lim-expensive or
max-cse-path-length, are basically meaningless to anybody who hasn't
studied the compiler in depth.

I have to agree that setting time and space budgets would be much more
useful for users than --param (not that we should remove --param, as
it is useful for compiler developers).  Or there is the idea which has
been suggested several times, of permitting optimization to be
specified along the orthogonal axes of time of compilation, speed of
generated code, size of generated code, and debuggability.

(While a time budget in seconds would lead to irreproducible results,
a time budget expressed in a scale from fast to slow compilation time
would not, and would be nearly as useful for users.)

Ian

Re: [GCC 4.2 Project] Omega data dependence test

[Daniel Berlin]

On Tue, 9 Aug 2005, Sebastian Pop wrote:

> Joe Buck wrote:
>> Algorithms that are sometimes exponential can still be used if there is
>> a cutoff mechanism, to abort the algorithm if it exceeds a budget.  This
>> assumes that we can then fall back to an algorithm that might produce
>> inferior results, but will produce something usable in reasonable time.
>>
>
> Okay, I stand corrected.  As a practical implementation we can have a
> mechanism as push/pop timevar, that would monitor the time and space
> of an algorithm and that can cancel the computation for failing on a
> safe approximation.  As a first concretization, I was thinking to use
> threads, but I'm not sure whether this is suitable for GCC.

A lot of data dependence related algorithms are exponential in the worst 
case, and work fine in production compilers, without cutoffs.

XLC uses fourier motzkin without any cutoffs, for example (as does intel, 
i believe) :)


>
>

Re: [GCC 4.2 Project] Omega data dependence test

[Daniel Kegel]

Andrew wrote:
 >> No threads in gcc, please.
 >
 > Why? If this is only for double checking, why not?

Sorry, I missed that boehm-gc already uses threads.

Ignore me, I'm just a cranky old-school programmer...

but still, if there's a way to implement the checker
without using threads, that would surely be safer.

Re: [GCC 4.2 Project] Omega data dependence test

[Daniel Kegel]

sebastian.pop@cri.ensmp.fr wrote:
> Okay, I stand corrected.  As a practical implementation we can have a
> mechanism as push/pop timevar, that would monitor the time and space
> of an algorithm and that can cancel the computation for failing on a
> safe approximation.  As a first concretization, I was thinking to use
> threads, but I'm not sure whether this is suitable for GCC.

No threads in gcc, please.

Re: [GCC 4.2 Project] Omega data dependence test

[Andrew Pinski]

On Aug 9, 2005, at 1:59 PM, Daniel Kegel wrote:

> No threads in gcc, please.

Why?  If this is only for double checking, why not?

-- Pinski

[GCC 4.2 Project] Omega data dependence test

[Sebastian Pop]

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.