Re: a strange infelicity of register allocation

[Zack Weinberg <zack@rabi.columbia.edu>]

On Tue, 26 Jan 1999 05:55:21 -0700, Jeffrey A Law wrote:
>  > >The next step is to find out what registers are used by the
>  > >entries on the conflict list.  In the .greg file there should be
>  > >something like this:
>  > >
>  > >;; Register dispositions:
>  > >94 in 5  96 in 7  97 in 20  98 in 5  99 in 4  100 in 9
>  > >102 in 13  104 in 14  106 in 15  108 in 16  110 in 31  112 in 22
>  > >[ ... ]
>  > 
>  > 23 in 0  27 in 4  28 in 3  32 in 1  40 in 0  42 in 3  
>  > 43 in 5  46 in 0  49 in 0  57 in 5  64 in 0  70 in 0  
>  > 75 in 0  79 in 0  80 in 0  85 in 0  94 in 0  
>  > 
>  > which is strange: hard register 2 (ecx) isn't used for anything.  What
>  > would cause that?
>Check and see if there are any "Spilling reg 2." messages.  I bet you'll find
>one for an insn over which pseudo 30 is live.

Nope.  No spills of reg 2 anywhere.

>As you mentioned, it might be worth doing a manual live range split so that
>reg 44 can get allocated into a hard register rather than a stack slot.
>
>It's interesting to note that pseudos 27 and 32 are the only registers
>allocated to hard registers 4 and 1 respectively.  Presumably they have long
>lifetimes (which makes them conflict with everything) and high usage counts
>which gives them a high priority.
>
>It would be interesting to know what user variables those pseudos correspond
>to (or temporary expressions if they aren't a user variable).  They may be
>candidates for splitting too.  It would also be interesting to relate them
>back to the source to see if their weighted counts make any sense.

Pseudo 27 was the input buffer pointer, which deserved a permanent
register.  Pseudo 32 was `count', a variable used heavily in the outer
loop but not anywhere in the inner loop - code like this:

for (;;)
{
  count = read (...);
  if (count < 0) goto error;
  else if (count == 0) break;
  offset += count;
  ip = ibase;
  ip[count] = '\0';
  if (offset > limit) { /* grow output buffer */ }

  while ((c = *ip++) != '\0')
    switch (c)
    {
      /* count not used anywhere in here */
    }
}

I put a block around the real useful range of `count' and declared it
there, and it now shares reg 1 with pseudo 96 which appears to be a
pointer to the `cpp_options' structure.

That, plus inventing a variable to use instead of `c' inside the
switch, and adjusting some branches to go straight to their final
destinations, has fixed up the allocation pretty well.

;; Register dispositions:
23 in 0  27 in 4  28 in 3  29 in 5  35 in 1  40 in 0  
42 in 3  43 in 5  44 in 2  46 in 0  49 in 0  58 in 0  
65 in 0  76 in 0  80 in 0  81 in 0  86 in 0  96 in 1  
;; Hard regs used:  0 1 2 3 4 5 6 7 16

Reg 76 used to be reg 75.  Reg 44 now gets a hard register, and we're
using all the registers again.  The invented variable, which is reg
56, does not get a hard register - that's unfortunate but not nearly
as bad.  I think it's because the code that uses reg 56 looks like
this:

	case '?':
	if (opts->trigraphs || opts->warn_trigraphs)
	{
	  char d;
	  ... stuff involving d but not c ...
	}
	else
	   *op++ = c;
	break;

It would need to realize that c is dead if the conditional is true.
That's live-range-splitting again, yes?

The failure to recognize that `count' is only live in the outer part
of the loop concerns me.  We do have live range *trimming*, don't we?
If so, why doesn't it work here?

So yes, this code benefits considerably from live range splitting.  I
am not sure about the use-count issue, I'd have to stare a lot more.
Another place this code could win is if local register allocation
could handle a block like this itself:

{
  int x = read(...)
  if (x < 0)
    goto error;
  else if (x == 0)
    goto eof;
 
   /* do stuff with x here */
}

I think this is what you meant by `extended basic blocks' ?  There are
a bunch of cases like this.

zw