On Mon, 2005-08-22 at 22:21 +0200, Zdenek Dvorak wrote:
> > > > 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.
Except that suboptimally means it used one more register than it should
have, or spilled 2 more loads.
In terms of performance of generated code, the simple approaches and the
optimal approaches were within .4% of each other on all programs tested.
So who cares if we hit them when it doesn't matter?