Switch containing holes via table lookup

Hi folks!

In /lib/Transforms/Utils/SimplifyCFG.cpp is optimization code which converts a switch statement to a table lookup but has problems when there are holes in the cases list and the default case can not be served with the table.

My first attempt to fix this is done by additionally testing a small set.

As an example the function
==>
unsigned test(unsigned x) {
    switch (x) {
      case 100: return 0;
      case 101: return 1;
      case 103: return 2;
      case 105: return 3;
      case 107: return 4;
      case 109: return 5;
      case 110: return 6;
      default: return x*3;
      }
    }
<==
can be converted to
==>
  .file "t.cpp"
  .text
  .globl _Z4testj
  .align 16, 0x90
  .type _Z4testj,@function
_Z4testj: # @_Z4testj
  .cfi_startproc
# BB#0: # %entry
                                          # kill: EDI<def> EDI<kill> RDI<def>
  leal -100(%rdi), %eax
  cmpl $11, %eax
  jae .LBB0_3
# BB#1: # %switch.lookup
  movl $1707, %ecx # imm = 0x6AB
  btl %eax, %ecx
  jae .LBB0_3
# BB#2: # %switch.lookup2
  cltq
  movl .Lswitch.table(,%rax,4), %eax
  retq
.LBB0_3: # %sw.default
  leal (%rdi,%rdi,2), %eax
  retq
.Ltmp0:
  .size _Z4testj, .Ltmp0-_Z4testj
  .cfi_endproc

  .type .Lswitch.table,@object # @switch.table
  .section .rodata,"a",@progbits
  .align 16
.Lswitch.table:
  .long 0 # 0x0
  .long 1 # 0x1
  .long 0 # 0x0
  .long 2 # 0x2
  .long 0 # 0x0
  .long 3 # 0x3
  .long 0 # 0x0
  .long 4 # 0x4
  .long 0 # 0x0
  .long 5 # 0x5
  .long 6 # 0x6
  .size .Lswitch.table, 44

  .ident "clang version 3.5 (trunk 200617)"
  .section ".note.GNU-stack","",@progbits
<==

By the way, what for is "cltq" just before accessing the value table?
The upper dword of rax should be zero.

Unfortunately my patch does not always work and the compiler crashes.
What have I overlooked? Please help.

Best regards
Jasper
PS: I posted a very similar message to llvm-commits@cs.uiuc.edu but got no response; perhaps this was the wrong place to discuss it.

patch.txt (3.89 KB)