test/CodeGen/X86/switch-bt.ll

   1 ; RUN: llc -mtriple=x86_64-- -asm-verbose=false < %s -jump-table-density=40 -switch-peel-threshold=101 | FileCheck %s
   2
   3 ; This switch should use bit tests, and the third bit test case is just
   4 ; testing for one possible value, so it doesn't need a bt.
   5
   6 ;      CHECK: movabsq $2305843009482129440, %r
   7 ; CHECK-NEXT: btq %rax, %r
   8 ; CHECK-NEXT: jb
   9 ;     CHECK: movl  $671088640, %e
  10 ; CHECK-NEXT: btq %rax, %r
  11 ; CHECK-NEXT: jae
  12 ;      CHECK: testq %rax, %r
  13 ; CHECK-NEXT: j
  14
  15 define void @test(i8* %l) nounwind {
  16 entry:
  17   %l.addr = alloca i8*, align 8                   ; <i8**> [#uses=2]
  18   store i8* %l, i8** %l.addr
  19   %tmp = load i8*, i8** %l.addr                        ; <i8*> [#uses=1]
  20   %tmp1 = load i8, i8* %tmp                           ; <i8> [#uses=1]
  21   %conv = sext i8 %tmp1 to i32                    ; <i32> [#uses=1]
  22   switch i32 %conv, label %sw.default [
  23     i32 62, label %sw.bb
  24     i32 60, label %sw.bb
  25     i32 38, label %sw.bb2
  26     i32 94, label %sw.bb2
  27     i32 61, label %sw.bb2
  28     i32 33, label %sw.bb4
  29   ]
  30
  31 sw.bb:                                            ; preds = %entry, %entry
  32   call void @foo(i32 0)
  33   br label %sw.epilog
  34
  35 sw.bb2:                                           ; preds = %entry, %entry, %entry
  36   call void @foo(i32 1)
  37   br label %sw.epilog
  38
  39 sw.bb4:                                           ; preds = %entry
  40   call void @foo(i32 3)
  41   br label %sw.epilog
  42
  43 sw.default:                                       ; preds = %entry
  44   call void @foo(i32 97)
  45   br label %sw.epilog
  46
  47 sw.epilog:                                        ; preds = %sw.default, %sw.bb4, %sw.bb2, %sw.bb
  48   ret void
  49 }
  50
  51 declare void @foo(i32)
  52
  53 ; Don't zero extend the test operands to pointer type if it can be avoided.
  54 ; rdar://8781238
  55 define void @test2(i32 %x) nounwind ssp {
  56 ; CHECK-LABEL: test2:
  57 ; CHECK: cmpl $6
  58 ; CHECK: ja
  59
  60 ; CHECK-NEXT: movl $91
  61 ; CHECK-NOT: movl
  62 ; CHECK-NEXT: btl
  63 ; CHECK-NEXT: jae
  64 entry:
  65   switch i32 %x, label %if.end [
  66     i32 6, label %if.then
  67     i32 4, label %if.then
  68     i32 3, label %if.then
  69     i32 1, label %if.then
  70     i32 0, label %if.then
  71   ]
  72
  73 if.then:                                          ; preds = %entry, %entry, %entry, %entry, %entry
  74   tail call void @bar() nounwind
  75   ret void
  76
  77 if.end:                                           ; preds = %entry
  78   ret void
  79 }
  80
  81 declare void @bar()
  82
  83 define void @test3(i32 %x) nounwind {
  84 ; CHECK-LABEL: test3:
  85 ; CHECK: cmpl $5
  86 ; CHECK: ja
  87 ; CHECK: cmpl $4
  88 ; CHECK: je
  89   switch i32 %x, label %if.end [
  90     i32 0, label %if.then
  91     i32 1, label %if.then
  92     i32 2, label %if.then
  93     i32 3, label %if.then
  94     i32 5, label %if.then
  95   ]
  96 if.then:
  97   tail call void @bar() nounwind
  98   ret void
  99 if.end:
 100   ret void
 101 }
 102
 103 ; Ensure that optimizing for jump tables doesn't needlessly deteriorate the
 104 ; created binary tree search. See PR22262.
 105 define void @test4(i32 %x, i32* %y) {
 106 ; CHECK-LABEL: test4:
 107
 108 entry:
 109   switch i32 %x, label %sw.default [
 110     i32 10, label %sw.bb
 111     i32 20, label %sw.bb1
 112     i32 30, label %sw.bb2
 113     i32 40, label %sw.bb3
 114     i32 50, label %sw.bb4
 115     i32 60, label %sw.bb5
 116   ]
 117 sw.bb:
 118   store i32 1, i32* %y
 119   br label %sw.epilog
 120 sw.bb1:
 121   store i32 2, i32* %y
 122   br label %sw.epilog
 123 sw.bb2:
 124   store i32 3, i32* %y
 125   br label %sw.epilog
 126 sw.bb3:
 127   store i32 4, i32* %y
 128   br label %sw.epilog
 129 sw.bb4:
 130   store i32 5, i32* %y
 131   br label %sw.epilog
 132 sw.bb5:
 133   store i32 6, i32* %y
 134   br label %sw.epilog
 135 sw.default:
 136   store i32 7, i32* %y
 137   br label %sw.epilog
 138 sw.epilog:
 139   ret void
 140
 141 ; The balanced binary switch here would start with a comparison against 39, but
 142 ; it is currently starting with 29 because of the density-sum heuristic.
 143 ; CHECK: cmpl $39
 144 ; CHECK: jg
 145 ; CHECK: cmpl $10
 146 ; CHECK: je
 147 ; CHECK: cmpl $20
 148 ; CHECK: je
 149 ; CHECK: cmpl $30
 150 ; CHECK: jne
 151 ; CHECK: cmpl $40
 152 ; CHECK: je
 153 ; CHECK: cmpl $50
 154 ; CHECK: je
 155 ; CHECK: cmpl $60
 156 ; CHECK: jne
 157 }
 158
 159
 160 ; Omit the range check when the default case is unreachable, see PR43129.
 161 declare void @g(i32)
 162 define void @test5(i32 %x) {
 163
 164 ; CHECK-LABEL: test5
 165 ; CHECK-NOT: cmp
 166
 167 ; 73 = 2^0 + 2^3 + 2^6
 168 ; CHECK:      movl $73
 169 ; CHECK-NEXT: btl
 170 ; CHECK-NEXT: jb
 171
 172 ; 146 = 2^1 + 2^4 + 2^7
 173 ; CHECK-NEXT: movl $146
 174 ; CHECK-NEXT: btl
 175 ; CHECK-NEXT: jae
 176
 177
 178 entry:
 179   switch i32 %x, label %return [
 180     i32 0, label %bb0
 181     i32 3, label %bb0
 182     i32 6, label %bb0
 183
 184     i32 1, label %bb1
 185     i32 4, label %bb1
 186     i32 7, label %bb1
 187
 188     i32 2, label %bb2
 189     i32 5, label %bb2
 190     i32 8, label %bb2
 191   ]
 192 bb0: tail call void @g(i32 0) br label %return
 193 bb1: tail call void @g(i32 1) br label %return
 194 bb2: tail call void @g(i32 2) br label %return
 195 return: unreachable
 196 }