[Bug middle-end/11823] New: Optimizing large jump tables for switch statements

[alga at rgai dot hu]

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

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

           Summary: Optimizing large jump tables for switch statements
           Product: gcc
           Version: 3.4
            Status: UNCONFIRMED
          Severity: minor
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: alga at rgai dot hu
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: arm-unknown-elf

In some cases GCC generates very large jump tables, e.g. the table can contain
too few different case values wrt. the table size. In these cases when
optimizing for size it would be preferable to use some other mechanism for the
jumping problem. For example, in some cases it would be more effecient to
create simple compare and branch pairs for checking the case values.

--- c example ---
// arm-elf-gcc -S -g0 -Os -o large-jump.s large-jump.c
int i;
int func(int a)
{
  switch(a)
  {
    case 0:   i = 20; break;
    case 1:   i = 50; break;
    case 2:   i = 29; break;
    case 10:  i = 20; break;
    case 11:  i = 50; break;
    case 12:  i = 29; break;
    case 20:  i = 20; break;
    case 21:  i = 50; break;
    case 22:  i = 29; break;
    case 52:  i = 79; break;
    case 110: i = 27; break;
    default:  i = 77; break;
  }
  return i;
}

--- arm code ---
func:
	ldr	r2, .L17
	cmp	r0, #110
	ldrls	pc, [pc, r0, asl #2]
	b	.L14
	.p2align 2
.L15:
	.word	.L9
	.word	.L10
	.word	.L11
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L9
	.word	.L10
	.word	.L11
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L9
	.word	.L10
	.word	.L11
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L12
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L14
	.word	.L13
.L9:
	mov	r3, #20
	b	.L16
.L10:
	mov	r3, #50
	b	.L16
.L11:
	mov	r3, #29
	b	.L16
.L12:
	mov	r3, #79
	b	.L16
.L13:
	mov	r3, #27
	b	.L16
.L14:
	mov	r3, #77
.L16:
	str	r3, [r2, #0]
	ldr	r3, .L17
	ldr	r0, [r3, #0]
	mov	pc, lr