> > > Google for optimal register allocation and you'll find a bunch of papers
> > > that try to take *everything* into account.
> > > You'll discover that except for coalescing, the "simple approaches"
> > > actually aren't more than ~3% off completely optimal approaches that
> > > take literally everything into account.
> > The only thing I ever said is that all of the "simple approaches" suffer
> > from the local minimum type problems, and that their behavior is too
> > unreliable and unpredictable to claim things like "this is only a
> > workaround that we will be able to remove once we improve RA".
> You missed my point.
> Existing research on optimal register allocation argues very well that
> it is *not* the case that simple approaches get stuck in local minima.
> They are, in fact, in almost all cases, globally optimal, except for
> coalescing strategy.
as you yourself admit, its only "almost all cases" (and cannot be
reasonably expected to be better). And if we are going to create
difficult instances of RA in the preceding optimizers, we are bound to
be hitting the "few" cases where the RA behaves significantly
suboptimally sometimes. And yes, we are bound to be hitting them
sometimes even if all the other optimizers are careful about register
pressure; I would expect it to be less frequently, but of course I have
nothing but the common sense to place my expectations upon -- I cannot
really think about a way how to measure any numbers about this, without
significant changes (including, but not limited to, writing a new RA) to