This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Register Pressure in Instruction Level Parallelism (fwd)
On Sat, Jul 13, 2002 at 09:17:20PM -0400, Daniel Jacobowitz wrote:
> On Sun, Jul 14, 2002 at 10:48:45AM +1000, Duraid Madina wrote:
> > Michael blurted:
> >
> > > > > current ILP processors. We give an exact formulation with integer
> > > > > programming for all register pressure problems.
> > >
> > > ... integer programming doesn't sound too promising in a
> > > production compiler. I'll read it anyway.
> >
> > Can you explain what exactly wouldn't be "too promising" about a
> > compiler that poses some difficult (NP-complete) questions in a
> > standard, massively popular format (integer programming), and answers
> > them using some simple heuristic (or perhaps an external) solver?
> > Skimming through that thesis, it's not as if he's shattering records
> > with CPLEX...
>
> What isn't promising about it is that integer programming is a
> technique for exact solutions to NP-complete problems. Since these are
> hard problems, exact solutions tend to be very computation-intensive.
Yes, but a major part of Sid's thesis is to provide efficient heuristics
for these hard to solve problems:
"We give an exact formulation with integer
programming for all register pressure problems. We also provide
algorithmic solutions. Experimental results show that our heuristics are
nearly optimal."
> GCC is slow enough as it is; integer programming based allocation is
> exceptionally computation-intensive, especially for large or
> pathological programs.
>
> --
> Daniel Jacobowitz Carnegie Mellon University
> MontaVista Software Debian GNU/Linux Developer