Re: stop unnecessary spills in gcc/reload1.c

[Jeffrey A Law <law at cygnus dot com>]

  In message <E10tF0n-0007IZ-00@rano.rano.org>you write:
  > Here's a little patch for reload1.c that stops it from letting
  > instructions that are going to be deleted anyway from causing a spill.
  > In many cases the damage done by the unnecessary spill is repaired
  > later anyway, but there's an example below of a C function which gets
  > better register allocation on Intel with this patch than without it
  > (gcc -S -O2 -dl -dg).
  > 
  > Even when the final code is identical you can see from .c.lreg and
  > .c.greg that fewer spills are happening, so I think this patch is
  > morally right.
  > 
  > It's very messy, though. Someone more familiar with the data
  > structures could probably simplify it a lot. In particular, the first
  > hunk of the patch seems, from experiments, to be unnecessary. However,
  > until I can see why an instruction deleted by a recursive call to
  > delete_dead_insn can never be deleted beforehand due to being in
  > reg_equiv_init[i] for a smaller i, I feel safer doing the deleting in
  > this order ...
  > 
  > I've tested this by bootstrapping the compiler on Intel with extra
  > code doing various consistency checks.
I've discussed this patch at length with Joern, and given the current
implementation and issues I don't think we want to try to include it
right now.

The major problems are its time complexity O(n^2).

Conceptually we should be able to use LOG_LINKS to walk the dependency
chain backwards and avoid the O(n^2) time complexity, but LOG_LINKS are
not necessarily valid after the regmove pass has completed.  Updating
them isn't in the current plan (it's expensive and I think our time
is better spent elsewhere).

FWIW, Joern did indicate that the first loop is unnecessary.


jeff