llvm/test/Transforms/SimplifyCFG/rangereduce.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -passes=simplifycfg -simplifycfg-require-and-preserve-domtree=1 -switch-to-lookup -S | FileCheck %s
   3 ; RUN: opt < %s -passes='simplifycfg<switch-to-lookup>' -S | FileCheck %s
   4
   5 target datalayout = "e-n32"
   6
   7 define i32 @test1(i32 %a) {
   8 ; CHECK-LABEL: @test1(
   9 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
  10 ; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
  11 ; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
  12 ; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
  13 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 4
  14 ; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
  15 ; CHECK:       switch.lookup:
  16 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], ptr @switch.table.test1, i32 0, i32 [[TMP4]]
  17 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
  18 ; CHECK-NEXT:    br label [[COMMON_RET]]
  19 ; CHECK:       common.ret:
  20 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
  21 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
  22 ;
  23   switch i32 %a, label %def [
  24   i32 97, label %one
  25   i32 101, label %two
  26   i32 105, label %three
  27   i32 109, label %three
  28   ]
  29
  30 def:
  31   ret i32 8867
  32
  33 one:
  34   ret i32 11984
  35 two:
  36   ret i32 1143
  37 three:
  38   ret i32 99783
  39 }
  40
  41 ; Optimization shouldn't trigger; bitwidth > 64
  42 define i128 @test2(i128 %a) {
  43 ; CHECK-LABEL: @test2(
  44 ; CHECK-NEXT:    switch i128 [[A:%.*]], label [[COMMON_RET:%.*]] [
  45 ; CHECK-NEXT:    i128 97, label [[ONE:%.*]]
  46 ; CHECK-NEXT:    i128 101, label [[TWO:%.*]]
  47 ; CHECK-NEXT:    i128 105, label [[THREE:%.*]]
  48 ; CHECK-NEXT:    i128 109, label [[THREE]]
  49 ; CHECK-NEXT:    ]
  50 ; CHECK:       common.ret:
  51 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i128 [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ], [ 8867, [[TMP0:%.*]] ]
  52 ; CHECK-NEXT:    ret i128 [[COMMON_RET_OP]]
  53 ; CHECK:       one:
  54 ; CHECK-NEXT:    br label [[COMMON_RET]]
  55 ; CHECK:       two:
  56 ; CHECK-NEXT:    br label [[COMMON_RET]]
  57 ; CHECK:       three:
  58 ; CHECK-NEXT:    br label [[COMMON_RET]]
  59 ;
  60   switch i128 %a, label %def [
  61   i128 97, label %one
  62   i128 101, label %two
  63   i128 105, label %three
  64   i128 109, label %three
  65   ]
  66
  67 def:
  68   ret i128 8867
  69
  70 one:
  71   ret i128 11984
  72 two:
  73   ret i128 1143
  74 three:
  75   ret i128 99783
  76 }
  77
  78 ; Optimization shouldn't trigger; no holes present
  79 define i32 @test3(i32 %a) {
  80 ; CHECK-LABEL: @test3(
  81 ; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[A:%.*]], 97
  82 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 3
  83 ; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
  84 ; CHECK:       switch.lookup:
  85 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32], ptr @switch.table.test3, i32 0, i32 [[SWITCH_TABLEIDX]]
  86 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
  87 ; CHECK-NEXT:    br label [[COMMON_RET]]
  88 ; CHECK:       common.ret:
  89 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
  90 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
  91 ;
  92   switch i32 %a, label %def [
  93   i32 97, label %one
  94   i32 98, label %two
  95   i32 99, label %three
  96   ]
  97
  98 def:
  99   ret i32 8867
 100
 101 one:
 102   ret i32 11984
 103 two:
 104   ret i32 1143
 105 three:
 106   ret i32 99783
 107 }
 108
 109 ; Optimization shouldn't trigger; not an arithmetic progression
 110 define i32 @test4(i32 %a) {
 111 ; CHECK-LABEL: @test4(
 112 ; CHECK-NEXT:    switch i32 [[A:%.*]], label [[COMMON_RET:%.*]] [
 113 ; CHECK-NEXT:    i32 97, label [[ONE:%.*]]
 114 ; CHECK-NEXT:    i32 102, label [[TWO:%.*]]
 115 ; CHECK-NEXT:    i32 105, label [[THREE:%.*]]
 116 ; CHECK-NEXT:    i32 109, label [[THREE]]
 117 ; CHECK-NEXT:    ]
 118 ; CHECK:       common.ret:
 119 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ], [ 8867, [[TMP0:%.*]] ]
 120 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
 121 ; CHECK:       one:
 122 ; CHECK-NEXT:    br label [[COMMON_RET]]
 123 ; CHECK:       two:
 124 ; CHECK-NEXT:    br label [[COMMON_RET]]
 125 ; CHECK:       three:
 126 ; CHECK-NEXT:    br label [[COMMON_RET]]
 127 ;
 128   switch i32 %a, label %def [
 129   i32 97, label %one
 130   i32 102, label %two
 131   i32 105, label %three
 132   i32 109, label %three
 133   ]
 134
 135 def:
 136   ret i32 8867
 137
 138 one:
 139   ret i32 11984
 140 two:
 141   ret i32 1143
 142 three:
 143   ret i32 99783
 144 }
 145
 146 ; Optimization shouldn't trigger; not a power of two
 147 define i32 @test5(i32 %a) {
 148 ; CHECK-LABEL: @test5(
 149 ; CHECK-NEXT:    switch i32 [[A:%.*]], label [[COMMON_RET:%.*]] [
 150 ; CHECK-NEXT:    i32 97, label [[ONE:%.*]]
 151 ; CHECK-NEXT:    i32 102, label [[TWO:%.*]]
 152 ; CHECK-NEXT:    i32 107, label [[THREE:%.*]]
 153 ; CHECK-NEXT:    i32 112, label [[THREE]]
 154 ; CHECK-NEXT:    ]
 155 ; CHECK:       common.ret:
 156 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ], [ 8867, [[TMP0:%.*]] ]
 157 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
 158 ; CHECK:       one:
 159 ; CHECK-NEXT:    br label [[COMMON_RET]]
 160 ; CHECK:       two:
 161 ; CHECK-NEXT:    br label [[COMMON_RET]]
 162 ; CHECK:       three:
 163 ; CHECK-NEXT:    br label [[COMMON_RET]]
 164 ;
 165   switch i32 %a, label %def [
 166   i32 97, label %one
 167   i32 102, label %two
 168   i32 107, label %three
 169   i32 112, label %three
 170   ]
 171
 172 def:
 173   ret i32 8867
 174
 175 one:
 176   ret i32 11984
 177 two:
 178   ret i32 1143
 179 three:
 180   ret i32 99783
 181 }
 182
 183 define i32 @test6(i32 %a) optsize {
 184 ; CHECK-LABEL: @test6(
 185 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], -109
 186 ; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
 187 ; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
 188 ; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
 189 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 4
 190 ; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
 191 ; CHECK:       switch.lookup:
 192 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], ptr @switch.table.test6, i32 0, i32 [[TMP4]]
 193 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
 194 ; CHECK-NEXT:    br label [[COMMON_RET]]
 195 ; CHECK:       common.ret:
 196 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
 197 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
 198 ;
 199   switch i32 %a, label %def [
 200   i32 -97, label %one
 201   i32 -101, label %two
 202   i32 -105, label %three
 203   i32 -109, label %three
 204   ]
 205
 206 def:
 207   ret i32 8867
 208
 209 one:
 210   ret i32 11984
 211 two:
 212   ret i32 1143
 213 three:
 214   ret i32 99783
 215 }
 216
 217 define i8 @test7(i8 %a) optsize {
 218 ; CHECK-LABEL: @test7(
 219 ; CHECK-NEXT:  common.ret:
 220 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 [[A:%.*]], -36
 221 ; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 [[TMP0]], 2
 222 ; CHECK-NEXT:    [[TMP2:%.*]] = shl i8 [[TMP0]], 6
 223 ; CHECK-NEXT:    [[TMP3:%.*]] = or i8 [[TMP1]], [[TMP2]]
 224 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp ult i8 [[TMP3]], 4
 225 ; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = zext i8 [[TMP3]] to i32
 226 ; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul nuw nsw i32 [[SWITCH_CAST]], 8
 227 ; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i32 -943228976, [[SWITCH_SHIFTAMT]]
 228 ; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i32 [[SWITCH_DOWNSHIFT]] to i8
 229 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = select i1 [[TMP4]], i8 [[SWITCH_MASKED]], i8 -93
 230 ; CHECK-NEXT:    ret i8 [[COMMON_RET_OP]]
 231 ;
 232   switch i8 %a, label %def [
 233   i8 220, label %one
 234   i8 224, label %two
 235   i8 228, label %three
 236   i8 232, label %three
 237   ]
 238
 239 def:
 240   ret i8 8867
 241
 242 one:
 243   ret i8 11984
 244 two:
 245   ret i8 1143
 246 three:
 247   ret i8 99783
 248 }
 249
 250 define i32 @test8(i32 %a) optsize {
 251 ; CHECK-LABEL: @test8(
 252 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
 253 ; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
 254 ; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
 255 ; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
 256 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 5
 257 ; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
 258 ; CHECK:       switch.lookup:
 259 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [5 x i32], ptr @switch.table.test8, i32 0, i32 [[TMP4]]
 260 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
 261 ; CHECK-NEXT:    br label [[COMMON_RET]]
 262 ; CHECK:       common.ret:
 263 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
 264 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
 265 ;
 266   switch i32 %a, label %def [
 267   i32 97, label %one
 268   i32 101, label %two
 269   i32 105, label %three
 270   i32 113, label %three
 271   ]
 272
 273 def:
 274   ret i32 8867
 275
 276 one:
 277   ret i32 11984
 278 two:
 279   ret i32 1143
 280 three:
 281   ret i32 99783
 282 }
 283
 284 define i32 @test9(i32 %a) {
 285 ; CHECK-LABEL: @test9(
 286 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 6
 287 ; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 1
 288 ; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 31
 289 ; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
 290 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 8
 291 ; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
 292 ; CHECK:       switch.lookup:
 293 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [8 x i32], ptr @switch.table.test9, i32 0, i32 [[TMP4]]
 294 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
 295 ; CHECK-NEXT:    br label [[COMMON_RET]]
 296 ; CHECK:       common.ret:
 297 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
 298 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
 299 ;
 300   switch i32 %a, label %def [
 301   i32 18, label %one
 302   i32 20, label %two
 303   i32 6, label %three
 304   i32 10, label %three
 305   ]
 306
 307 def:
 308   ret i32 8867
 309
 310 one:
 311   ret i32 11984
 312 two:
 313   ret i32 1143
 314 three:
 315   ret i32 99783
 316 }
 317