Re: Patch to simplify reload register allocation

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

  In message <Pine.LNX.4.10.9909171657220.6179-100000@biriani.cygnus.co.uk>you 
write:
  > There are currently two reload register allocation mechanisms; one which is
  > used during the first pass(es) of reload, using calculate_needs and
  > find_reload_regs, and a second one (choose_reload_regs/allocate_reload_reg)
  > which is used during reload_as_needed.
Yup.  And you know me, I dislike code like this, particularly when the two
hunks of code are closely intertwined.

  > These passes must work together, the first one must ensure that it makes
  > enough registers available for the second pass.  However, these passes
  > currently work in very different ways, and it is not at all obvious that
  > they will always agree on the number of reload regs needed.
Right.  I often wonder *why* things were done this way.  It just seems like
a poor design.  I wonder if Jim Wilson or Richard Kenner might be able to
provide some insight into the history of this code.

It might be worth looking at some of the more important historical versions
of gcc to see if they provide any clues about the design of this code.  Though
we might not find anything useful at all.  Hard to tell.

  > Also, due to
  > historical reasons, the first pass is a lot more complex than it needs to
  > be: the calculate_needs code is left over from the time when we needed to
  > compute maximum needs across all insns.
I wasn't aware of that.


  > The patch below tries to clean this up a little.  The first allocation pass
  > is simplified; it now uses reload_reg_class_lower just like the second pass
  > to compute a safe order for allocating registers to reloads, and then grabs
  > reload registers in that order; this is an algorithm similar to the one 
used
  > by the second pass.
Sounds like the right direction.


  > This algorithm is not completely fail-safe, however.  Consider this
  > scenario:
  >   * four registers: r0 .. r3
  >   * two classes: low_regs (r0 and r1) and all_regs (all four regs)
  >   * a group reload for class all_regs, and a single register reload for
  >     low_regs
  > Since reload_reg_class_lower puts the group reload in front of the other
  > one we might end up grabbing r0 and r1 for the group, leaving nothing for
  > the single register reload.  I don't see any attempts to handle this case
  > in the current code, so I'm not sure this is an issue with any of the
  > existing ports.
I'm not sure either.  At first I thought this was the same as the z8k problem
(see z8k.h in devo/gcc/config/z8k and look for RELOAD_ALLOC_ORDER).  But
they look like distinct issues.

[ FWIW, if someone wants to clean up the z8k, I'm more than happy to contribute
  it to GCC.  It will not work as-is because of the reload issues, and it's
  probably suffering from a fair amount of bitrot.  Or I could contribute it,
  but mark it as a dead port similar to the pyr, spur, etc. ]


  > With this patch, the information about which hard reg is allocated to which
  > reload is kept until reload_as_needed.  This is used in choose_reload_regs
  > in the no inheritance fallback case.  This way, it is guaranteed that the
  > second pass always finds a valid set of reload registers - it just uses the
  > one found during the first pass if necessary.  This makes the assumption
  > that find_reloads returns the same set of reloads during both passes
  > explicit - it will abort if the reloads appear different.
All this sounds good too.

  > I'm not entirely sure what the force_group code in allocate_reload_regs is
  > supposed to do.  Probably it can now go away, since we can always provide a
  > safe allocation at this point.
This is something we probably can figure out by poking at some of the older
versions of gcc lying around.

  > The patch contains two more or less unrelated cleanup items: moving
  > reload_mode and reload_nregs into the reload structure and computing them
  > only once, in find_reloads; and getting rid of all the save_xxx nonsense
  > in choose_reload_regs.
Sounds good too.

[ ... ]
  > Long-term, I'd like to try and get rid of choose_reload_regs completely; if
  > we could do reload inheritance during the first pass we could just re-use
  > the existing reload register assignments during the second pass; this
  > might even avoid some spilling.
Sounds reasonable too.


Basically I like all the base concept.  However, we've got some rather serious
changes already happening in the tree and I'd like to see it settle down and
stabilize a little before go into another reload revamp.

However, the two cleanups are probably simple enough since they're not changing
any underlying assumptions in reload.  We should probably break them out review
'em and install 'em.

I see that this change also moved reload_nregs and reload_mode into the reload
structure.  You might as well break those out too (and you can consider that
pre-approved).


jeff