[Bug target/57583] New: large switches with jump tables are horribly broken on m68k

[Bug target/57583] New: large switches with jump tables are horribly broken on m68k

[mikpe at it dot uu.se]

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

            Bug ID: 57583
           Summary: large switches with jump tables are horribly broken on
                    m68k
           Product: gcc
           Version: 4.8.1
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: target
          Assignee: unassigned at gcc dot gnu.org
          Reporter: mikpe at it dot uu.se

Created attachment 30288
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30288&action=edit
test case and generator program

Switch jump tables on m68k-linux use 16-bit PC-relative offsets.  No
verification is made that the offsets actually fit in 16 bits, instead they are
silently truncated.  As a result, a large switch may branch to a wrong address;
in my case it branches into the jump table itself causing a SIGILL.

There are two bugs here:

1. GCC seems to hard-code the use of 16-bit offsets in its jump tables on
m68k-linux.  It should have an option to use 32-bit offsets instead.

2. GAS (not part of GCC I know) truncates ".word" operands to 16 bits without
warning or error when significant bits are lost.  I'll file that separately at
the sourceware/binutils bugzilla.

The test case contains a for (;;) loop with a switch () with 64K cases 0 ..
64K-1, each case containing a function call and a break. That switch becomes
the following assembly code on m68k-linux with gcc-4.8.1:

.L259:
        move.l (%a2),-(%sp)
        move.l %a2,-(%sp)
        jsr fetch
        addq.l #8,%sp
        and.l #65535,%d0
        move.w .L262(%pc,%d0.l*2),%d0
        jmp %pc@(2,%d0:w)
        .balignw 2,0x284c
.L262:
        .word .L260-.L262
        (64K - 1 more of these with varying labels in the first operand)

When run on the target the code SIGILLs:

0x80000402 in fetch ()
1: x/i $pc
=> 0x80000402 <fetch+14>:       rts
(gdb)
0x80001c0c in loop ()
1: x/i $pc
=> 0x80001c0c <loop+20>:        addql #8,%sp
(gdb)
0x80001c0e in loop ()
1: x/i $pc
=> 0x80001c0e <loop+22>:        andil #65535,%d0
(gdb)
0x80001c14 in loop ()
1: x/i $pc
=> 0x80001c14 <loop+28>:        movew %pc@(0x80001c1c <loop+36>,%d0:l:2),%d0
(gdb)
0x80001c18 in loop ()
1: x/i $pc
=> 0x80001c18 <loop+32>:        jmp %pc@(0x80001c1c <loop+36>,%d0:w)
(gdb) print $d0
$3 = 4

*** THIS "4" SHOWS THAT THE JUMP TABLE ENTRY HAS BEEN TRUNCATED

(gdb) stepi
0x80001c20 in loop ()
1: x/i $pc
=> 0x80001c20 <loop+40>:        .short 0xfff2
(gdb) stepi

Program received signal SIGILL, Illegal instruction.

I'm attaching the test case (bug.c) and the program used to generate it
(genbug.c).

Classifying as a target bug since the code works on x86_64 and powerpc64.

[Bug target/57583] large switches with jump tables are horribly broken on m68k

[schwab@linux-m68k.org]

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

--- Comment #1 from Andreas Schwab <schwab@linux-m68k.org> ---
Apparently GAS has lost its BROKEN_DOT_WORD handing.

[Bug target/57583] large switches with jump tables are horribly broken on m68k

[mikpe at it dot uu.se]

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

--- Comment #2 from Mikael Pettersson <mikpe at it dot uu.se> ---
<http://sourceware.org/bugzilla/show_bug.cgi?id=15602> is the corresponding
binutils/gas bug.

[Bug target/57583] large switches with jump tables are horribly broken on m68k

[mikpe at it dot uu.se]

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

--- Comment #3 from Mikael Pettersson <mikpe at it dot uu.se> ---
It's not too difficult to make the m68k backend use 32-bit offsets in its jump
tables (adjust CASE_VECTOR_MODE, ASM_OUTPUT_ADDR_DIFF_ELT,
ASM_RETURN_CASE_JUMP, drop the sign-extend from the tablejump expander,
likewise in the unnamed insn that matches the output from the tablejump
expander).  I have a crude patch to do that, and make it compile-time
selectable via an option.

However, it seems to me that the compiler should be able to figure out for
itself if a given jump table might need 32-bit offsets.  In the worst case
every element will overflow a (signed) 16-bit offset (0..32K-1 positive range)
and need a GAS-inserted trampoline, for a total of 2 + 6 == 8 bytes per
element.  So tables with no more than 4K elements should work with 16-bit
offsets.  Tables larger than that may have their trampolines more than 32K away
from the table PC base, which cannot work with 16-bit offsets, so for those the
compiler should use 32-bit offsets.  Seems to require implementing "casesi" for
m68k though.

[Bug target/57583] large switches with jump tables are horribly broken on m68k

[hp at gcc dot gnu.org]

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

--- Comment #4 from Hans-Peter Nilsson <hp at gcc dot gnu.org> ---
(In reply to Mikael Pettersson from comment #3)
> It's not too difficult to make the m68k backend use 32-bit offsets in its
> jump tables (adjust CASE_VECTOR_MODE, ASM_OUTPUT_ADDR_DIFF_ELT,
> ASM_RETURN_CASE_JUMP, drop the sign-extend from the tablejump expander,
> likewise in the unnamed insn that matches the output from the tablejump
> expander).  I have a crude patch to do that,

Does your patch define CASE_VECTOR_SHORTEN_MODE?
Otherwise that'll probably be one of the first review comments.

> and make it compile-time
> selectable via an option.

FWIW, -mbigtable for sh.

> However, it seems to me that the compiler should be able to figure out for
> itself if a given jump table might need 32-bit offsets.

The length insn attribute needs to be defined in order to take advantage of the
existing machinery.  It seems it currently isn't, for m68k.

[Bug target/57583] large switches with jump tables are horribly broken on m68k

[schwab@linux-m68k.org]

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

--- Comment #5 from Andreas Schwab <schwab@linux-m68k.org> ---
The assembler already handles jump targets that are too far away (via the
BROKEN_DOT_WORD hack), this issue is about growing the table itself too large
so that the overflow table is not reachable any more within 32K.

[Bug target/57583] large switches with jump tables are horribly broken on m68k

[hp at gcc dot gnu.org]

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

--- Comment #6 from Hans-Peter Nilsson <hp at gcc dot gnu.org> ---
(In reply to Andreas Schwab from comment #5)
> The assembler already handles jump targets that are too far away (via the
> BROKEN_DOT_WORD hack), this issue is about growing the table itself too
> large so that the overflow table is not reachable any more within 32K.

There's no confusion here.  While a less involved patch will suffice where just
the table is too big, CASE_VECTOR_SHORTEN_MODE can detect and handle both
issues. I think it will also allow for jump-tables closer to the 4K entries
than the significantly lower limit you'll find workable with a less involved
patch and relying on BROKEN_DOT_WORD.