test/CodeGen/X86/switch.ll

   1 ; RUN: llc -mtriple=x86_64-linux-gnu %s -o - | FileCheck %s
   2 ; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -O0 | FileCheck --check-prefix=NOOPT %s
   3
   4 declare void @g(i32)
   5
   6 define void @basic(i32 %x) {
   7 entry:
   8   switch i32 %x, label %return [
   9     i32 3, label %bb0
  10     i32 1, label %bb1
  11     i32 4, label %bb1
  12     i32 5, label %bb0
  13   ]
  14 bb0: tail call void @g(i32 0) br label %return
  15 bb1: tail call void @g(i32 1) br label %return
  16 return: ret void
  17
  18 ; Should be lowered as straight compares in -O0 mode.
  19 ; NOOPT-LABEL: basic
  20 ; NOOPT: subl $3, %eax
  21 ; NOOPT: je
  22 ; NOOPT: subl $1, %eax
  23 ; NOOPT: je
  24 ; NOOPT: subl $4, %eax
  25 ; NOOPT: je
  26 ; NOOPT: subl $5, %eax
  27 ; NOOPT: je
  28
  29 ; Jump table otherwise.
  30 ; CHECK-LABEL: basic
  31 ; CHECK: decl
  32 ; CHECK: cmpl $4
  33 ; CHECK: ja
  34 ; CHECK: jmpq *.LJTI
  35 }
  36
  37
  38 define void @simple_ranges(i32 %x) {
  39 entry:
  40   switch i32 %x, label %return [
  41     i32 0, label %bb0
  42     i32 1, label %bb0
  43     i32 2, label %bb0
  44     i32 3, label %bb0
  45     i32 100, label %bb1
  46     i32 101, label %bb1
  47     i32 102, label %bb1
  48     i32 103, label %bb1
  49   ]
  50 bb0: tail call void @g(i32 0) br label %return
  51 bb1: tail call void @g(i32 1) br label %return
  52 return: ret void
  53
  54 ; Should be lowered to two range checks.
  55 ; CHECK-LABEL: simple_ranges
  56 ; CHECK: leal -100
  57 ; CHECK: cmpl $4
  58 ; CHECK: jae
  59 ; CHECK: cmpl $3
  60 ; CHECK: ja
  61 }
  62
  63
  64 define void @jt_is_better(i32 %x) {
  65 entry:
  66   switch i32 %x, label %return [
  67     i32 0, label %bb0
  68     i32 2, label %bb0
  69     i32 4, label %bb0
  70     i32 1, label %bb1
  71     i32 3, label %bb1
  72     i32 5, label %bb1
  73
  74     i32 6, label %bb2
  75     i32 7, label %bb3
  76     i32 8, label %bb4
  77   ]
  78 bb0: tail call void @g(i32 0) br label %return
  79 bb1: tail call void @g(i32 1) br label %return
  80 bb2: tail call void @g(i32 2) br label %return
  81 bb3: tail call void @g(i32 3) br label %return
  82 bb4: tail call void @g(i32 4) br label %return
  83 return: ret void
  84
  85 ; Cases 0-5 could be lowered with two bit tests,
  86 ; but with 6-8, the whole switch is suitable for a jump table.
  87 ; CHECK-LABEL: jt_is_better
  88 ; CHECK: cmpl $8
  89 ; CHECK: jbe
  90 ; CHECK: jmpq *.LJTI
  91 }
  92
  93
  94 define void @bt_is_better(i32 %x) {
  95 entry:
  96   switch i32 %x, label %return [
  97     i32 0, label %bb0
  98     i32 3, label %bb0
  99     i32 6, label %bb0
 100     i32 1, label %bb1
 101     i32 4, label %bb1
 102     i32 7, label %bb1
 103     i32 2, label %bb2
 104     i32 5, label %bb2
 105     i32 8, label %bb2
 106
 107   ]
 108 bb0: tail call void @g(i32 0) br label %return
 109 bb1: tail call void @g(i32 1) br label %return
 110 bb2: tail call void @g(i32 2) br label %return
 111 return: ret void
 112
 113 ; This could be lowered as a jump table, but bit tests is more efficient.
 114 ; CHECK-LABEL: bt_is_better
 115 ; 73 = 2^0 + 2^3 + 2^6
 116 ; CHECK: movl $73
 117 ; CHECK: btl
 118 ; 146 = 2^1 + 2^4 + 2^7
 119 ; CHECK: movl $146
 120 ; CHECK: btl
 121 ; 292 = 2^2 + 2^5 + 2^8
 122 ; CHECK: movl $292
 123 ; CHECK: btl
 124 }
 125
 126
 127 define void @optimal_pivot1(i32 %x) {
 128 entry:
 129   switch i32 %x, label %return [
 130     i32 100, label %bb0
 131     i32 200, label %bb1
 132     i32 300, label %bb0
 133     i32 400, label %bb1
 134     i32 500, label %bb0
 135     i32 600, label %bb1
 136
 137   ]
 138 bb0: tail call void @g(i32 0) br label %return
 139 bb1: tail call void @g(i32 1) br label %return
 140 return: ret void
 141
 142 ; Should pivot around 400 for two subtrees of equal size.
 143 ; CHECK-LABEL: optimal_pivot1
 144 ; CHECK-NOT: cmpl
 145 ; CHECK: cmpl $399
 146 }
 147
 148
 149 define void @optimal_pivot2(i32 %x) {
 150 entry:
 151   switch i32 %x, label %return [
 152     i32 100, label %bb0   i32 101, label %bb1   i32 102, label %bb2   i32 103, label %bb3
 153     i32 200, label %bb0   i32 201, label %bb1   i32 202, label %bb2   i32 203, label %bb3
 154     i32 300, label %bb0   i32 301, label %bb1   i32 302, label %bb2   i32 303, label %bb3
 155     i32 400, label %bb0   i32 401, label %bb1   i32 402, label %bb2   i32 403, label %bb3
 156
 157   ]
 158 bb0: tail call void @g(i32 0) br label %return
 159 bb1: tail call void @g(i32 1) br label %return
 160 bb2: tail call void @g(i32 2) br label %return
 161 bb3: tail call void @g(i32 3) br label %return
 162 return: ret void
 163
 164 ; Should pivot around 300 for two subtrees with two jump tables each.
 165 ; CHECK-LABEL: optimal_pivot2
 166 ; CHECK-NOT: cmpl
 167 ; CHECK: cmpl $299
 168 ; CHECK: jmpq *.LJTI
 169 ; CHECK: jmpq *.LJTI
 170 ; CHECK: jmpq *.LJTI
 171 ; CHECK: jmpq *.LJTI
 172 }
 173
 174
 175 define void @optimal_jump_table1(i32 %x) {
 176 entry:
 177   switch i32 %x, label %return [
 178     i32 0,  label %bb0
 179     i32 5,  label %bb1
 180     i32 6,  label %bb2
 181     i32 12, label %bb3
 182     i32 13, label %bb4
 183     i32 15, label %bb5
 184   ]
 185 bb0: tail call void @g(i32 0) br label %return
 186 bb1: tail call void @g(i32 1) br label %return
 187 bb2: tail call void @g(i32 2) br label %return
 188 bb3: tail call void @g(i32 3) br label %return
 189 bb4: tail call void @g(i32 4) br label %return
 190 bb5: tail call void @g(i32 5) br label %return
 191 return: ret void
 192
 193 ; Splitting in the largest gap (between 6 and 12) would yield suboptimal result.
 194 ; Expecting a jump table from 5 to 15.
 195 ; CHECK-LABEL: optimal_jump_table1
 196 ; CHECK: leal -5
 197 ; CHECK: cmpl $10
 198 ; CHECK: jmpq *.LJTI
 199 }
 200
 201
 202 define void @optimal_jump_table2(i32 %x) {
 203 entry:
 204   switch i32 %x, label %return [
 205     i32 0,  label %bb0
 206     i32 1,  label %bb1
 207     i32 2,  label %bb2
 208     i32 9,  label %bb3
 209     i32 14, label %bb4
 210     i32 15, label %bb5
 211   ]
 212 bb0: tail call void @g(i32 0) br label %return
 213 bb1: tail call void @g(i32 1) br label %return
 214 bb2: tail call void @g(i32 2) br label %return
 215 bb3: tail call void @g(i32 3) br label %return
 216 bb4: tail call void @g(i32 4) br label %return
 217 bb5: tail call void @g(i32 5) br label %return
 218 return: ret void
 219
 220 ; Partitioning the cases to the minimum number of dense sets is not good enough.
 221 ; This can be partitioned as {0,1,2,9},{14,15} or {0,1,2},{9,14,15}. The former
 222 ; should be preferred. Expecting a table from 0-9.
 223 ; CHECK-LABEL: optimal_jump_table2
 224 ; CHECK: cmpl $9
 225 ; CHECK: jmpq *.LJTI
 226 }
 227
 228
 229 define void @optimal_jump_table3(i32 %x) {
 230 entry:
 231   switch i32 %x, label %return [
 232     i32 1,  label %bb0
 233     i32 2,  label %bb1
 234     i32 3,  label %bb2
 235     i32 10, label %bb3
 236     i32 13, label %bb0
 237     i32 14, label %bb1
 238     i32 15, label %bb2
 239     i32 20, label %bb3
 240     i32 25, label %bb4
 241   ]
 242 bb0: tail call void @g(i32 0) br label %return
 243 bb1: tail call void @g(i32 1) br label %return
 244 bb2: tail call void @g(i32 2) br label %return
 245 bb3: tail call void @g(i32 3) br label %return
 246 bb4: tail call void @g(i32 4) br label %return
 247 return: ret void
 248
 249 ; Splitting to maximize left-right density sum and gap size would split this
 250 ; between 3 and 10, and then between 20 and 25. It's better to build a table
 251 ; from 1-20.
 252 ; CHECK-LABEL: optimal_jump_table3
 253 ; CHECK: leal -1
 254 ; CHECK: cmpl $19
 255 ; CHECK: jmpq *.LJTI
 256 }
 257
 258 %struct.S = type { %struct.S*, i32 }
 259 define void @phi_node_trouble(%struct.S* %s) {
 260 entry:
 261   br label %header
 262 header:
 263   %ptr = phi %struct.S* [ %s, %entry ], [ %next, %loop ]
 264   %bool = icmp eq %struct.S* %ptr, null
 265   br i1 %bool, label %exit, label %loop
 266 loop:
 267   %nextptr = getelementptr inbounds %struct.S, %struct.S* %ptr, i64 0, i32 0
 268   %next = load %struct.S*, %struct.S** %nextptr
 269   %xptr = getelementptr inbounds %struct.S, %struct.S* %next, i64 0, i32 1
 270   %x = load i32, i32* %xptr
 271   switch i32 %x, label %exit [
 272     i32 4, label %header
 273     i32 36, label %exit2
 274     i32 69, label %exit2
 275     i32 25, label %exit2
 276   ]
 277 exit:
 278   ret void
 279 exit2:
 280   ret void
 281
 282 ; This will be lowered to a comparison with 4 and then bit tests. Make sure
 283 ; that the phi node in %header gets a value from the comparison block.
 284 ; CHECK-LABEL: phi_node_trouble
 285 ; CHECK: movq (%[[REG1:[a-z]+]]), %[[REG1]]
 286 ; CHECK: movl 8(%[[REG1]]), %[[REG2:[a-z]+]]
 287 ; CHECK: cmpl $4, %[[REG2]]
 288 }
 289
 290
 291 define void @default_only(i32 %x) {
 292 entry:
 293   br label %sw
 294 return:
 295   ret void
 296 sw:
 297   switch i32 %x, label %return [
 298   ]
 299
 300 ; Branch directly to the default.
 301 ; (In optimized builds the switch is removed earlier.)
 302 ; NOOPT-LABEL: default_only
 303 ; NOOPT: .[[L:[A-Z0-9_]+]]:
 304 ; NOOPT-NEXT: retq
 305 ; NOOPT: jmp .[[L]]
 306 }
 307
 308
 309 define void @int_max_table_cluster(i8 %x) {
 310 entry:
 311   switch i8 %x, label %return [
 312     i8 0, label %bb0 i8 1, label %bb0 i8 2, label %bb0 i8 3, label %bb0
 313     i8 4, label %bb0 i8 5, label %bb0 i8 6, label %bb0 i8 7, label %bb0
 314     i8 8, label %bb0 i8 9, label %bb0 i8 10, label %bb0 i8 11, label %bb0
 315     i8 12, label %bb0 i8 13, label %bb0 i8 14, label %bb0 i8 15, label %bb0
 316     i8 16, label %bb0 i8 17, label %bb0 i8 18, label %bb0 i8 19, label %bb0
 317     i8 20, label %bb0 i8 21, label %bb0 i8 22, label %bb0 i8 23, label %bb0
 318     i8 24, label %bb0 i8 25, label %bb0 i8 26, label %bb0 i8 27, label %bb0
 319     i8 28, label %bb0 i8 29, label %bb0 i8 30, label %bb0 i8 31, label %bb0
 320     i8 32, label %bb0 i8 33, label %bb0 i8 34, label %bb0 i8 35, label %bb0
 321     i8 36, label %bb0 i8 37, label %bb0 i8 38, label %bb0 i8 39, label %bb0
 322     i8 40, label %bb0 i8 41, label %bb0 i8 42, label %bb0 i8 43, label %bb0
 323     i8 44, label %bb0 i8 45, label %bb0 i8 46, label %bb0 i8 47, label %bb0
 324     i8 48, label %bb0 i8 49, label %bb0 i8 50, label %bb0 i8 51, label %bb0
 325     i8 52, label %bb0 i8 53, label %bb0 i8 54, label %bb0 i8 55, label %bb0
 326     i8 56, label %bb0 i8 57, label %bb0 i8 58, label %bb0 i8 59, label %bb0
 327     i8 60, label %bb0 i8 61, label %bb0 i8 62, label %bb0 i8 63, label %bb0
 328     i8 64, label %bb0 i8 65, label %bb0 i8 66, label %bb0 i8 67, label %bb0
 329     i8 68, label %bb0 i8 69, label %bb0 i8 70, label %bb0 i8 71, label %bb0
 330     i8 72, label %bb0 i8 73, label %bb0 i8 74, label %bb0 i8 75, label %bb0
 331     i8 76, label %bb0 i8 77, label %bb0 i8 78, label %bb0 i8 79, label %bb0
 332     i8 80, label %bb0 i8 81, label %bb0 i8 82, label %bb0 i8 83, label %bb0
 333     i8 84, label %bb0 i8 85, label %bb0 i8 86, label %bb0 i8 87, label %bb0
 334     i8 88, label %bb0 i8 89, label %bb0 i8 90, label %bb0 i8 91, label %bb0
 335     i8 92, label %bb0 i8 93, label %bb0 i8 94, label %bb0 i8 95, label %bb0
 336     i8 96, label %bb0 i8 97, label %bb0 i8 98, label %bb0 i8 99, label %bb0
 337     i8 100, label %bb0 i8 101, label %bb0 i8 102, label %bb0 i8 103, label %bb0
 338     i8 104, label %bb0 i8 105, label %bb0 i8 106, label %bb0 i8 107, label %bb0
 339     i8 108, label %bb0 i8 109, label %bb0 i8 110, label %bb0 i8 111, label %bb0
 340     i8 112, label %bb0 i8 113, label %bb0 i8 114, label %bb0 i8 115, label %bb0
 341     i8 116, label %bb0 i8 117, label %bb0 i8 118, label %bb0 i8 119, label %bb0
 342     i8 120, label %bb0 i8 121, label %bb0 i8 122, label %bb0 i8 123, label %bb0
 343     i8 124, label %bb0 i8 125, label %bb0 i8 126, label %bb0 i8 127, label %bb0
 344     i8 -64, label %bb1 i8 -63, label %bb1 i8 -62, label %bb1 i8 -61, label %bb1
 345     i8 -60, label %bb1 i8 -59, label %bb1 i8 -58, label %bb1 i8 -57, label %bb1
 346     i8 -56, label %bb1 i8 -55, label %bb1 i8 -54, label %bb1 i8 -53, label %bb1
 347     i8 -52, label %bb1 i8 -51, label %bb1 i8 -50, label %bb1 i8 -49, label %bb1
 348     i8 -48, label %bb1 i8 -47, label %bb1 i8 -46, label %bb1 i8 -45, label %bb1
 349     i8 -44, label %bb1 i8 -43, label %bb1 i8 -42, label %bb1 i8 -41, label %bb1
 350     i8 -40, label %bb1 i8 -39, label %bb1 i8 -38, label %bb1 i8 -37, label %bb1
 351     i8 -36, label %bb1 i8 -35, label %bb1 i8 -34, label %bb1 i8 -33, label %bb1
 352     i8 -32, label %bb2 i8 -31, label %bb2 i8 -30, label %bb2 i8 -29, label %bb2
 353     i8 -28, label %bb2 i8 -27, label %bb2 i8 -26, label %bb2 i8 -25, label %bb2
 354     i8 -24, label %bb2 i8 -23, label %bb2 i8 -22, label %bb2 i8 -21, label %bb2
 355     i8 -20, label %bb2 i8 -19, label %bb2 i8 -18, label %bb2 i8 -17, label %bb2
 356     i8 -16, label %bb3 i8 -15, label %bb3 i8 -14, label %bb3 i8 -13, label %bb3
 357     i8 -12, label %bb3 i8 -11, label %bb3 i8 -10, label %bb3 i8 -9, label %bb3
 358   ]
 359 bb0: tail call void @g(i32 0) br label %return
 360 bb1: tail call void @g(i32 1) br label %return
 361 bb2: tail call void @g(i32 1) br label %return
 362 bb3: tail call void @g(i32 1) br label %return
 363 return: ret void
 364
 365 ; Don't infloop on jump tables where the upper bound is the max value of the
 366 ; input type (in this case 127).
 367 ; CHECK-LABEL: int_max_table_cluster
 368 ; CHECK: jmpq *.LJTI
 369 }