Graph coloring for register allocation?

[Zack Weinberg]

On Wed, Jan 24, 2001 at 01:08:05PM -0500, Daniel Berlin wrote:
> >
> > SMALL_REGISTER_CLASSES (and therefore all kinds of cruft all over the place).
> > Inability to run the scheduler before register allocation on some machines.
> 
> Unless i'm mistaken, all the papers i've looked at(save one or two, i
> think Chow and Hennessy didn't, it's hard to recall) require that
> scheduling be run before register allocation.

I haven't been reading papers.  The current situation is that if you
run the scheduler before register allocation on certain machines,
reload will run out of registers and abort.  You see things like

void
c4x_optimization_options (level, size)
     int level ATTRIBUTE_UNUSED;
     int size ATTRIBUTE_UNUSED;
{
  /* Scheduling before register allocation can screw up global
     register allocation, especially for functions that use MPY||ADD
     instructions.  The benefit we gain we get by scheduling before
     register allocation is probably marginal anyhow.  */
  flag_schedule_insns = 0;
}

(c4x/c4x.c)  When they say "can screw up", they mean "can make reload
abort."

I had thought this was a problem with all SMALL_REGISTER_CLASSES
machines, but it seems not.

zw