possible bug in global allocation phase

possible bug in global allocation phase

[Heiko Panther]

I'm porting a gcc-3.2.3 cross compiler for or32 to a Mac OS X host.
The or32 is a 32 bit machine with 32 registers (r0..r31). The gcc
compiler I'm porting works fine for i86-linux. It is available from 
cvs@cvs.opencores.org:/home/oc/cvs or1k/gcc-3.2.3

In find_reg(), global.c:1056 ff, something bad happens. find_reg is
processing a request for a DI (double integer, needs two registers), and
it finds r31 suitable. I assume it is not suitable, since there is no
r32 to hold the second part of the DI.

TEST_HARD_REG_BIT(used, 32) returns 0 and thus r32 is believed to be
available. This happens because "used" is  of type HARD_REG_SET.
HARD_REG_SET is a 32 bit integer type, so a test for nonexisting bits
will produce wrong results.

My quickly hacked workaround just turns the check around, so all the
tests for non-existing bits that succeeded before now fail.

global.c:1066            &&  TEST_HARD_REG_BIT (~used, j));

It seems perfectly legal for HARD_REG_SET to be 32 bits wide. In
hard-reg-set.h, HARD_REG_SET is #defined a HARD_REG_ELT_TYPE given that
HARD_REG_ELT_TYPE has at least as many bits as the target has got registers.

If I am not mistaken, this would generally mean that find_reg() might
yield errors for n-bit targets if the host HARD_REG_SET is not more than
n bits wide. The reason that the x86 port works could be that the
HARD_REG_SET is 64 bit wide there for some reason, but I did not check
that.

It could be argued that HARD_REG_ELT_TYPE is a native wide type, and
should therefore be 64 bits wide on PPC. I didn't look into why it isn't
in my gcc, but as stated above, it should be legal to have a 32 bit type
there.

If all my assumptions are right, it also follows that this gcc will fail
allocating registers for a target that has 64 registers on a machine
where HARD_REG_SET is 64 bits wide.

Is someone able to confirm this?

Regards,
Heiko Panther

Re: possible bug in global allocation phase

[Jim Wilson]

[-- Attachment #1: Type: text/plain, Size: 897 bytes --]

Heiko Panther wrote:
> TEST_HARD_REG_BIT(used, 32) returns 0 and thus r32 is believed to be
> available. This happens because "used" is  of type HARD_REG_SET.
> HARD_REG_SET is a 32 bit integer type, so a test for nonexisting bits
> will produce wrong results.

Yes, this looks like a legitimate bug to me.  TEST_HARD_REG_BIT provokes 
undefined/implementation defined behaviour if given an out-of-range 
register number.  We can get different behaviour for different targets here.

I see 3 uses of this idiom in global.c, 5 in reload.c, 5 in reload1.c, 
and one in local.c.  And that is just a quick check, I haven't tried 
using grep yet, or trying to verify the count.

I think we need to fix all such occurences by adding a check against 
FIRST_PSEUDO_REGISTER.

I have attached an incomplete example patch showing what I propose.
-- 
Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com

[-- Attachment #2: tmp.file.100 --]
[-- Type: text/plain, Size: 1255 bytes --]

Index: global.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/global.c,v
retrieving revision 1.94
diff -p -r1.94 global.c
*** global.c	19 Jul 2003 14:47:06 -0000	1.94
--- global.c	22 Oct 2003 19:54:03 -0000
*************** find_reg (int num, HARD_REG_SET losers, 
*** 1051,1056 ****
--- 1051,1057 ----
  	      int lim = regno + HARD_REGNO_NREGS (regno, mode);
  	      for (j = regno + 1;
  		   (j < lim
+ 		    && j < FIRST_PSEUDO_REGISTER
  		    && ! TEST_HARD_REG_BIT (used, j));
  		   j++);
  	      if (j == lim)
*************** find_reg (int num, HARD_REG_SET losers, 
*** 1098,1103 ****
--- 1099,1105 ----
  	      int lim = i + HARD_REGNO_NREGS (i, mode);
  	      for (j = i + 1;
  		   (j < lim
+ 		    && j < FIRST_PSEUDO_REGISTER
  		    && ! TEST_HARD_REG_BIT (used, j)
  		    && (REGNO_REG_CLASS (j)
  			== REGNO_REG_CLASS (best_reg + (j - i))
*************** find_reg (int num, HARD_REG_SET losers, 
*** 1137,1142 ****
--- 1139,1145 ----
  	      int lim = i + HARD_REGNO_NREGS (i, mode);
  	      for (j = i + 1;
  		   (j < lim
+ 		    && j < FIRST_PSEUDO_REGISTER
  		    && ! TEST_HARD_REG_BIT (used, j)
  		    && (REGNO_REG_CLASS (j)
  			== REGNO_REG_CLASS (best_reg + (j - i))

Re: possible bug in global allocation phase

[Heiko Panther]

Jim Wilson wrote:
> Heiko Panther wrote:
> 
>> TEST_HARD_REG_BIT(used, 32) returns 0 and thus r32 is believed to be
>> available. This happens because "used" is  of type HARD_REG_SET.
>> HARD_REG_SET is a 32 bit integer type, so a test for nonexisting bits
>> will produce wrong results.
> 
> 
> Yes, this looks like a legitimate bug to me.  TEST_HARD_REG_BIT provokes 
> undefined/implementation defined behaviour if given an out-of-range 
> register number.  We can get different behaviour for different targets 
> here.
> 
> I see 3 uses of this idiom in global.c, 5 in reload.c, 5 in reload1.c, 
> and one in local.c.  And that is just a quick check, I haven't tried 
> using grep yet, or trying to verify the count.
> 
> I think we need to fix all such occurences by adding a check against 
> FIRST_PSEUDO_REGISTER.

I applied the fix which I proposed in about 15 places (although a grep 
will yield about 220 occurences) and could then successfully complete my 
failing compilation.

I developed my approach further by adding this to hard-reg-set.h:

/* Create a test with slightly different semantic. Instead of testing
for a bit, we ask if register corresponding to bit is available (bit is
0) . Then, we can return 'not available' for bits we don't have. 
Introduced because some code would test nonexisting bits, get back 0,
and assume the register's available */

#define TEST_HARD_REG_AVAILABLE(SET, BIT) \
(TEST_HARD_REG_BIT_H(~(SET), (BIT)))
#define TEST_HARD_REG_UNAVAILABLE(SET, BIT) \
(!TEST_HARD_REG_BIT_H(~(SET), (BIT)))

The pro is that this approach won't use more cycles than before.

Whatever approach is chosen, lots of source code needs to be examined 
and modified. I can't really spare the time to do that. I see three 
options. What do you think, which one makes most sense?

1. I could send in a patch with the changes that got my stuff working, 
so TEST_HARD_REG_BIT and TEST_HARD_REG_AVAILABLE would be used mixed. 
I'm not sure whether the TEST_HARD_REG_AVALABLE semantic makes sense in 
every place where TEST_HARD_REG_BIT appears. The "old" TEST_HARD_REG_BIT 
macro could be modified so it aborts when the register number is out of 
range. That would cost as many cycles as your approach, worst case.

2. You could implement your approach.

3. I could just create a bug report. Which has its own problems, since 
few people will actually use this host/target combination. And my target 
is not in the main gcc tree.

Regards,
Heiko Panther

Re: possible bug in global allocation phase

[Jim Wilson]

On Thu, 2003-10-23 at 12:52, Heiko Panther wrote:
> 1. I could send in a patch with the changes that got my stuff working

I can't say for sure since I haven't seen them yet, but your patches do
not appear to be safe.  The problem here is that the TEST_HARD_REG_BIT
macro invokes undefined behavior.  If HARD_REG_SET is a scalar, we get
an out-of-range shift.  If HARD_REG_SET is an array, we get an
out-of-bounds array access.  Inverting the sense of the tests does not
solve this problem.  We still have undefined behavior.  Thus we either
have to check for out-of-range registers inside the TEST_HARD_REG_BIT
macro itself, or avoid passing out-of-range registers in the callers. 
The former is safer, the latter is faster.

I believe that the only place where we have out-of-range registers is
when we are checking regs with large modes that span multiple hard
regs.  This idiom is fairly easy to check for, and thus I think the
latter option is practical.

If we really want to be safer, we could add some enable-checking tests
to TEST_HARD_REG_BIT to check for the out-of-range register case.

> 2. You could implement your approach.

I am hoping to find time soon to do that.

My patch can be made a bit more efficient by moving the extra tests out
of the loop.  The extra tests are necessary for correctness; I see no
way to avoid a few extra cycles here.

> 3. I could just create a bug report.

I think this would be a useful thing to do so that the problem is
tracked.
-- 
Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com