[Bug c/12754] New: Faulty register allocation under certain circumstances

[Bug c/12754] New: Faulty register allocation under certain circumstances

[heiko dot panther at web dot de]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=12754

           Summary: Faulty register allocation under certain circumstances
           Product: gcc
           Version: 3.2.3
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: heiko dot panther at web dot de
                CC: gcc-bugs at gcc dot gnu dot org,wilson at specifixinc
                    dot com
 GCC build triplet: powerpc-apple-darwin
  GCC host triplet: powerpc-apple-darwin
GCC target triplet: or32-none-elf

This bug is not specific to the host or target it was met on. It is merely connected to the size of the 
type HARD_REG_SET on the host and the number of hard registers of the target. Bug appeared in 
gcc-3.1 as well.

I already talked about this to Jim Wilson, who seemed willing to work on it, so I CC'd him :)

Here's the full report:

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.

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.

A grep for TEST_HARD_REG_BIT yields about 220 occurences, about 100 in gcc, the rest in target 
configs (mainly IA32/64). All these places would have to be checked.

[Bug optimization/12754] Faulty register allocation under certain circumstances

[pinskia at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=12754


pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c                           |optimization

[Bug optimization/12754] Faulty register allocation under certain circumstances

[wilson at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=12754


wilson at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2003-10-29 08:31:05
               date|                            |


------- Additional Comments From wilson at gcc dot gnu dot org  2003-10-29 08:30 -------
I have reproduced the problem.  The instructions for checking out the sources
are a little incomplete, but it wasn't hard to get the info I needed from the
web site at www.opencodes.org.

I have 3 ideas for how to fix this, none of which I am completely happy with.
1) Make HARD_REG_SET slightly bigger, so we can't accidentally read past the end
of it.  I suspect this will have a small effect on gcc compile time performance
for most targets.  This isn't foolproof, since we have to guess at how much
bigger to make HARD_REG_SET, and we might guess wrong.
2) Add a check for out of range registers in TEST_HARD_REG_BIT.  This is
guaranteed to work, but will have the biggest effect on gcc compile time.
3) Add checks for out of range registers at all call sites that might scan past
FIRST_PSEUDO_REGISTER accidentally.  This assumes we can identify all such
places, and avoid adding more in the future.  So this is the least safe
solution, but should have the least affect on gcc compile time.  The unsafe call
sites all use similar idioms, so it is possible to identify them.  See for
instance setup_save_areas in caller-save.c, and find_regs in global.c.

An advantage of solution 3 is that it also avoids other out-of-range accesses. 
setup_save_areas in caller-save.c also has out-of-bounds array accesses for
regno_save_mem and regno_save_mode for instance.

So for now I am investigating solution 3.

I believe that there is no problem with CLEAR_HARD_REG_BIT and SET_HARD_REG_BIT.
 Both of these are used only when we either already have a valid register, or we
have a register that passed a previous TEST_HARD_REG_BIT test, and therefore we
should never get out-of-range registers in the CLEAR and SET macros if the TEST
macro is used correctly.

[Bug optimization/12754] Faulty register allocation under certain circumstances

[giovannibajo at libero dot it]

------- Additional Comments From giovannibajo at libero dot it  2004-01-15 13:25 -------
Jim, is this a regression? Does it work correctly in 2.95? Can you also attach 
a preprocessed testcase here so that others may look into it as well? Thanks.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |giovannibajo at libero dot
                   |                            |it


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=12754

[Bug optimization/12754] Faulty register allocation under certain circumstances

[wilson at specifixinc dot com]

------- Additional Comments From wilson at specifixinc dot com  2004-01-16 22:21 -------
Subject: Re:  Faulty register allocation under
	certain circumstances

On Thu, 2004-01-15 at 05:25, giovannibajo at libero dot it wrote:
> Jim, is this a regression? Does it work correctly in 2.95? Can you also attach 
> a preprocessed testcase here so that others may look into it as well? Thanks.

The problem is more complicated than that.

The port in question, or32, does not exist in the FSF tree.  So this bug
is not reproducible against any FSF tree.  However, the problem is
present in the FSF tree, and has been for a long time.

The underlying problem here is that we have many out-of-range array
accesses because of how we use the TEST_HARD_REG_BIT macro.  An obvious
place is in caller-save.c, which has
  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
    for (j = MOVE_MAX_WORDS; j > 0; j--)
      {
	...
        for (k = 0; k < j; k++)
          if (! TEST_HARD_REG_BIT (hard_regs_used, i + k))
If MOVE_MAX_WORDS > 1, then this reads past the end of the
HARD_REG_SET.  However, what happens here depends on how many registers
you have, and which definition of a HARD_REG_SET gets used.  In the vast
majority of cases, nothing bad can happen here, as HARD_REG_SET
naturally has some padding unless you have exactly a multiple of 32
registers.  In the or32 case, they have exactly 32 (or maybe it is 64?)
registers, and thus just going one bit too far takes you the next word. 
This out-of-bounds access can cause various problems.  Most of these
problems are in the register allocator/reload, and that is where the
or32 port fails.

The same code is present in gcc-2.95, and I wouldn't be surprised if
there are examples of this problem as far back as gcc-2.0.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=12754