Re: Reload work in progress

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

  In message <Pine.LNX.4.21.0008231816250.9300-100000@balti.cygnus.co.uk>you wr
ite:
  > Every now and then, I'm working on a patch that changes several aspects of
  > how reload works.  So far, most of the discussion has been on Redhat
  > internal mailing lists; Jeff asked me to post a message here as well so
  > that people know about it.  I'm not appending the patch in this mail, it's
  > a bit too large (600K uncompressed).  If anyone is interested, I can send
  > it privately - it's against a not too old CVS version of gcc.
So, one of my questions is are there pieces we can start reviewing and
installing?

For example, are there hunks of infrastructure that we can tackle -- similar
to how we first installed the reload chains and such when we were working
through your localized spilling patch?

What can myself (and others) do to try and move this process forward -- I
think the concepts behind your changes are sound, so I want to see us move
forward as best as we can.

  > The patch tries to address what I perceive are several flaws of reload:
  >  - The enum reload_type/reload_when_needed handling, which tracks reload
  >    lifetimes (such as RELOAD_FOR_INPUT, etc.).
  >    From the original reload implementation, which didn't even have this, to
  >    the current one, this has grown enormously.  One of the problems with it
  >    is that it doesn't give us exact lifetimes of reload registers, and a 
  >    lot of effort must be invested to get any useful life information out
  >    of it at all.  For example, there's a 100 line kludge near the end of
  >    find_reloads which has to modify some combinations of reload types
  >    because the code in reload1.c is incorrect and doesn't handle all
  >    possible cases properly.
Presumably the basic concept you're going to use to replace this involves
creating some kind of dependency tree for the reloads?


  >  - Reload inheritance is a nice concept, but the implementation is just
  >    about incomprehensible and unmaintainable.  Given the size of it, it
  >    also doesn't really work all that well - witness the post-reload
  >    attempts like reload_cse_regs or the noop-moves code in jump.c which
  >    fix up what reload left behind.  Even with these additional
  >    mini-passes, we occasionally end up with obviously stupid code
  >    generation.
Can't argue with the fact that inheritance is an unmaintainable mess with
its current implementation.  However, I'll withhold opinions about the
cleanup passes -- it'd be nice to zap them and we may be able to do so
if your code works out as well as we'd like -- let's consider wiping the
cleanup passes one of the goals, but not a requirement for this work.


  >  - Reload register allocation.  Half a dozen places all over the reload
  >    pass set reg_rtx because each thinks it knows better how to allocate
  >    a reload register than the other ones (e.g. combine_reloads).
Similarly.  This adds a fair amount of complexity and unpredictability to
reload.  Both of which I want to address.

FWIW, reload is kind of like loop in some respects -- we twiddle it in ways
we think are useful, but we can't reliably predict how well those tweaks
work.  That's an excellent sign that we need to do some redesign, cleanup
and simplification that needs to be done.

  > Here's what I'm trying to do about it:
  >  - All reload register allocation is now done during the first pass.
  >    choose_reload_regs/allocate_reload_reg are gone.
Excellent.  I love it.

  >  - We try to track lifetimes accurately.
Excellent.

  >    * Every register that occurs in some way during an insn gets its own
  >      structure (struct reload_reg_use) which records the lifetime.
  >      "Registers" includes reload registers; there's a reload_reg_use
  >      structure for each reload.  Conflicts are checked based on these, so w
  >      we can check conflicts between two reloads with the same function as
  >      conflicts between reloads and hard regs.
Cool.

  >      There can be three ways a register is used: either it's a reload
  >      register, it's used as an input, or it's used as an output.  By keepin
  >      keeping track of registers explicitly used in the insn (either as hard
  >      regs or as allocated pseudos), we can figure out exactly which regs
  >      conflict with each reload.  This might in a few cases lead to better
So for my own information, how would something like an output address reload
be classified in your scheme?  It has some properties of an input reload
and others of an output reload.

What about secondary reloads?

  >    * After find_reloads, we scan the pattern of the insn and search for
  >      register references and replacements, building up definition/use
  >      relations.  There are "reload_insn" structures which describe reload
  >      insns (or rather time slots for emitting them).  Two time slots are
  >      reserved for the reloaded insn itself (earlyclobber outputs and normal
  >      outputs).
Cool.

  >    * After we know the definition/use relationships, there's a small
  >      scheduling pass (don't think of haifa, think of a screenful of code).
Right.    Very cool.  Extra points for using well understood concepts like
def/use relationships :-)


  >  - Reload inheritance is rewritten. It's structured as a pass within reload
  >    and works with the lifetime data structures that were gathered.  It's
  >    deliberately done so as to be not so intrusive on unrelated code - it's
  >    a single block of code that could in theory be deleted without affecting
  >    anything else.
Very very cool.

  > Right now the results tend to be comparable to or slightly better than the
  > existing code (_without_ the help of reload_cse_regs; parts of noop_moves
  > are also gone for now).  Occasionally there are blunders, but I think I
  > know how to fix those.
That's a good enough proof of concept that I think we should be looking for
ways to start integrating parts of the code.


jeff