test/Transforms/InstCombine/redundant-left-shift-input-masking-variant-d.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt %s -instcombine -S | FileCheck %s
   3
   4 ; If we have some pattern that leaves only some low bits set, and then performs
   5 ; left-shift of those bits, if none of the bits that are left after the final
   6 ; shift are modified by the mask, we can omit the mask.
   7
   8 ; There are many variants to this pattern:
   9 ;   d)  (x & ((-1 << maskNbits) >> maskNbits)) << shiftNbits
  10 ; simplify to:
  11 ;   x << shiftNbits
  12 ; iff (shiftNbits-maskNbits) s>= 0 (i.e. shiftNbits u>= maskNbits)
  13
  14 ; Simple tests. We don't care about extra uses.
  15
  16 declare void @use32(i32)
  17
  18 define i32 @t0_basic(i32 %x, i32 %nbits) {
  19 ; CHECK-LABEL: @t0_basic(
  20 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
  21 ; CHECK-NEXT:    [[T1:%.*]] = lshr i32 [[T0]], [[NBITS]]
  22 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]
  23 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
  24 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
  25 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
  26 ; CHECK-NEXT:    [[T4:%.*]] = shl i32 [[X]], [[NBITS]]
  27 ; CHECK-NEXT:    ret i32 [[T4]]
  28 ;
  29   %t0 = shl i32 -1, %nbits
  30   %t1 = lshr i32 %t0, %nbits
  31   %t2 = and i32 %t1, %x
  32   call void @use32(i32 %t0)
  33   call void @use32(i32 %t1)
  34   call void @use32(i32 %t2)
  35   %t4 = shl i32 %t2, %nbits
  36   ret i32 %t4
  37 }
  38
  39 define i32 @t1_bigger_shift(i32 %x, i32 %nbits) {
  40 ; CHECK-LABEL: @t1_bigger_shift(
  41 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
  42 ; CHECK-NEXT:    [[T1:%.*]] = lshr i32 [[T0]], [[NBITS]]
  43 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]
  44 ; CHECK-NEXT:    [[T3:%.*]] = add i32 [[NBITS]], 1
  45 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
  46 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
  47 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
  48 ; CHECK-NEXT:    call void @use32(i32 [[T3]])
  49 ; CHECK-NEXT:    [[T4:%.*]] = shl i32 [[X]], [[T3]]
  50 ; CHECK-NEXT:    ret i32 [[T4]]
  51 ;
  52   %t0 = shl i32 -1, %nbits
  53   %t1 = lshr i32 %t0, %nbits
  54   %t2 = and i32 %t1, %x
  55   %t3 = add i32 %nbits, 1
  56   call void @use32(i32 %t0)
  57   call void @use32(i32 %t1)
  58   call void @use32(i32 %t2)
  59   call void @use32(i32 %t3)
  60   %t4 = shl i32 %t2, %t3
  61   ret i32 %t4
  62 }
  63
  64 ; Vectors
  65
  66 declare void @use3xi32(<3 x i32>)
  67
  68 define <3 x i32> @t2_vec_splat(<3 x i32> %x, <3 x i32> %nbits) {
  69 ; CHECK-LABEL: @t2_vec_splat(
  70 ; CHECK-NEXT:    [[T0:%.*]] = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]]
  71 ; CHECK-NEXT:    [[T1:%.*]] = lshr <3 x i32> [[T0]], [[NBITS]]
  72 ; CHECK-NEXT:    [[T2:%.*]] = and <3 x i32> [[T1]], [[X:%.*]]
  73 ; CHECK-NEXT:    [[T3:%.*]] = add <3 x i32> [[NBITS]], <i32 1, i32 1, i32 1>
  74 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T0]])
  75 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T1]])
  76 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T2]])
  77 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T3]])
  78 ; CHECK-NEXT:    [[T4:%.*]] = shl <3 x i32> [[X]], [[T3]]
  79 ; CHECK-NEXT:    ret <3 x i32> [[T4]]
  80 ;
  81   %t0 = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, %nbits
  82   %t1 = lshr <3 x i32> %t0, %nbits
  83   %t2 = and <3 x i32> %t1, %x
  84   %t3 = add <3 x i32> %nbits, <i32 1, i32 1, i32 1>
  85   call void @use3xi32(<3 x i32> %t0)
  86   call void @use3xi32(<3 x i32> %t1)
  87   call void @use3xi32(<3 x i32> %t2)
  88   call void @use3xi32(<3 x i32> %t3)
  89   %t4 = shl <3 x i32> %t2, %t3
  90   ret <3 x i32> %t4
  91 }
  92
  93 define <3 x i32> @t3_vec_nonsplat(<3 x i32> %x, <3 x i32> %nbits) {
  94 ; CHECK-LABEL: @t3_vec_nonsplat(
  95 ; CHECK-NEXT:    [[T0:%.*]] = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]]
  96 ; CHECK-NEXT:    [[T1:%.*]] = lshr <3 x i32> [[T0]], [[NBITS]]
  97 ; CHECK-NEXT:    [[T2:%.*]] = and <3 x i32> [[T1]], [[X:%.*]]
  98 ; CHECK-NEXT:    [[T3:%.*]] = add <3 x i32> [[NBITS]], <i32 1, i32 0, i32 2>
  99 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T0]])
 100 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T1]])
 101 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T2]])
 102 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T3]])
 103 ; CHECK-NEXT:    [[T4:%.*]] = shl <3 x i32> [[X]], [[T3]]
 104 ; CHECK-NEXT:    ret <3 x i32> [[T4]]
 105 ;
 106   %t0 = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, %nbits
 107   %t1 = lshr <3 x i32> %t0, %nbits
 108   %t2 = and <3 x i32> %t1, %x
 109   %t3 = add <3 x i32> %nbits, <i32 1, i32 0, i32 2>
 110   call void @use3xi32(<3 x i32> %t0)
 111   call void @use3xi32(<3 x i32> %t1)
 112   call void @use3xi32(<3 x i32> %t2)
 113   call void @use3xi32(<3 x i32> %t3)
 114   %t4 = shl <3 x i32> %t2, %t3
 115   ret <3 x i32> %t4
 116 }
 117
 118 define <3 x i32> @t4_vec_undef(<3 x i32> %x, <3 x i32> %nbits) {
 119 ; CHECK-LABEL: @t4_vec_undef(
 120 ; CHECK-NEXT:    [[T0:%.*]] = shl <3 x i32> <i32 -1, i32 undef, i32 -1>, [[NBITS:%.*]]
 121 ; CHECK-NEXT:    [[T1:%.*]] = lshr <3 x i32> [[T0]], [[NBITS]]
 122 ; CHECK-NEXT:    [[T2:%.*]] = and <3 x i32> [[T1]], [[X:%.*]]
 123 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T0]])
 124 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T1]])
 125 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T2]])
 126 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[NBITS]])
 127 ; CHECK-NEXT:    [[T4:%.*]] = shl <3 x i32> [[X]], [[NBITS]]
 128 ; CHECK-NEXT:    ret <3 x i32> [[T4]]
 129 ;
 130   %t0 = shl <3 x i32> <i32 -1, i32 undef, i32 -1>, %nbits
 131   %t1 = lshr <3 x i32> %t0, %nbits
 132   %t2 = and <3 x i32> %t1, %x
 133   %t3 = add <3 x i32> %nbits, <i32 0, i32 undef, i32 0>
 134   call void @use3xi32(<3 x i32> %t0)
 135   call void @use3xi32(<3 x i32> %t1)
 136   call void @use3xi32(<3 x i32> %t2)
 137   call void @use3xi32(<3 x i32> %t3)
 138   %t4 = shl <3 x i32> %t2, %t3
 139   ret <3 x i32> %t4
 140 }
 141
 142 ; Commutativity
 143
 144 declare i32 @gen32()
 145
 146 define i32 @t5_commutativity0(i32 %nbits) {
 147 ; CHECK-LABEL: @t5_commutativity0(
 148 ; CHECK-NEXT:    [[X:%.*]] = call i32 @gen32()
 149 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
 150 ; CHECK-NEXT:    [[T1:%.*]] = lshr i32 [[T0]], [[NBITS]]
 151 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[X]], [[T1]]
 152 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 153 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
 154 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
 155 ; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[X]], [[NBITS]]
 156 ; CHECK-NEXT:    ret i32 [[T3]]
 157 ;
 158   %x = call i32 @gen32()
 159   %t0 = shl i32 -1, %nbits
 160   %t1 = lshr i32 %t0, %nbits
 161   %t2 = and i32 %x, %t1 ; swapped order
 162   call void @use32(i32 %t0)
 163   call void @use32(i32 %t1)
 164   call void @use32(i32 %t2)
 165   %t3 = shl i32 %t2, %nbits
 166   ret i32 %t3
 167 }
 168
 169 define i32 @t6_commutativity1(i32 %nbits0, i32 %nbits1) {
 170 ; CHECK-LABEL: @t6_commutativity1(
 171 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS0:%.*]]
 172 ; CHECK-NEXT:    [[T1:%.*]] = lshr i32 [[T0]], [[NBITS0]]
 173 ; CHECK-NEXT:    [[T2:%.*]] = shl i32 -1, [[NBITS1:%.*]]
 174 ; CHECK-NEXT:    [[T3:%.*]] = lshr i32 [[T0]], [[NBITS1]]
 175 ; CHECK-NEXT:    [[T4:%.*]] = and i32 [[T3]], [[T1]]
 176 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 177 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
 178 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
 179 ; CHECK-NEXT:    call void @use32(i32 [[T3]])
 180 ; CHECK-NEXT:    call void @use32(i32 [[T4]])
 181 ; CHECK-NEXT:    [[T5:%.*]] = shl i32 [[T3]], [[NBITS0]]
 182 ; CHECK-NEXT:    ret i32 [[T5]]
 183 ;
 184   %t0 = shl i32 -1, %nbits0
 185   %t1 = lshr i32 %t0, %nbits0
 186   %t2 = shl i32 -1, %nbits1
 187   %t3 = lshr i32 %t0, %nbits1
 188   %t4 = and i32 %t3, %t1 ; both hands of 'and' could be mask..
 189   call void @use32(i32 %t0)
 190   call void @use32(i32 %t1)
 191   call void @use32(i32 %t2)
 192   call void @use32(i32 %t3)
 193   call void @use32(i32 %t4)
 194   %t5 = shl i32 %t4, %nbits0
 195   ret i32 %t5
 196 }
 197 define i32 @t7_commutativity2(i32 %nbits0, i32 %nbits1) {
 198 ; CHECK-LABEL: @t7_commutativity2(
 199 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS0:%.*]]
 200 ; CHECK-NEXT:    [[T1:%.*]] = lshr i32 [[T0]], [[NBITS0]]
 201 ; CHECK-NEXT:    [[T2:%.*]] = shl i32 -1, [[NBITS1:%.*]]
 202 ; CHECK-NEXT:    [[T3:%.*]] = lshr i32 [[T0]], [[NBITS1]]
 203 ; CHECK-NEXT:    [[T4:%.*]] = and i32 [[T3]], [[T1]]
 204 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 205 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
 206 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
 207 ; CHECK-NEXT:    call void @use32(i32 [[T3]])
 208 ; CHECK-NEXT:    call void @use32(i32 [[T4]])
 209 ; CHECK-NEXT:    [[T5:%.*]] = shl i32 [[T4]], [[NBITS1]]
 210 ; CHECK-NEXT:    ret i32 [[T5]]
 211 ;
 212   %t0 = shl i32 -1, %nbits0
 213   %t1 = lshr i32 %t0, %nbits0
 214   %t2 = shl i32 -1, %nbits1
 215   %t3 = lshr i32 %t0, %nbits1
 216   %t4 = and i32 %t3, %t1 ; both hands of 'and' could be mask..
 217   call void @use32(i32 %t0)
 218   call void @use32(i32 %t1)
 219   call void @use32(i32 %t2)
 220   call void @use32(i32 %t3)
 221   call void @use32(i32 %t4)
 222   %t5 = shl i32 %t4, %nbits1
 223   ret i32 %t5
 224 }
 225
 226 ; Fast-math flags. We must not preserve them!
 227
 228 define i32 @t8_nuw(i32 %x, i32 %nbits) {
 229 ; CHECK-LABEL: @t8_nuw(
 230 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
 231 ; CHECK-NEXT:    [[T1:%.*]] = lshr i32 [[T0]], [[NBITS]]
 232 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]
 233 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 234 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
 235 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
 236 ; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[X]], [[NBITS]]
 237 ; CHECK-NEXT:    ret i32 [[T3]]
 238 ;
 239   %t0 = shl i32 -1, %nbits
 240   %t1 = lshr i32 %t0, %nbits
 241   %t2 = and i32 %t1, %x
 242   call void @use32(i32 %t0)
 243   call void @use32(i32 %t1)
 244   call void @use32(i32 %t2)
 245   %t3 = shl nuw i32 %t2, %nbits
 246   ret i32 %t3
 247 }
 248
 249 define i32 @t9_nsw(i32 %x, i32 %nbits) {
 250 ; CHECK-LABEL: @t9_nsw(
 251 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
 252 ; CHECK-NEXT:    [[T1:%.*]] = lshr i32 [[T0]], [[NBITS]]
 253 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]
 254 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 255 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
 256 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
 257 ; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[X]], [[NBITS]]
 258 ; CHECK-NEXT:    ret i32 [[T3]]
 259 ;
 260   %t0 = shl i32 -1, %nbits
 261   %t1 = lshr i32 %t0, %nbits
 262   %t2 = and i32 %t1, %x
 263   call void @use32(i32 %t0)
 264   call void @use32(i32 %t1)
 265   call void @use32(i32 %t2)
 266   %t3 = shl nsw i32 %t2, %nbits
 267   ret i32 %t3
 268 }
 269
 270 define i32 @t10_nuw_nsw(i32 %x, i32 %nbits) {
 271 ; CHECK-LABEL: @t10_nuw_nsw(
 272 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
 273 ; CHECK-NEXT:    [[T1:%.*]] = lshr i32 [[T0]], [[NBITS]]
 274 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]
 275 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 276 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
 277 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
 278 ; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[X]], [[NBITS]]
 279 ; CHECK-NEXT:    ret i32 [[T3]]
 280 ;
 281   %t0 = shl i32 -1, %nbits
 282   %t1 = lshr i32 %t0, %nbits
 283   %t2 = and i32 %t1, %x
 284   call void @use32(i32 %t0)
 285   call void @use32(i32 %t1)
 286   call void @use32(i32 %t2)
 287   %t3 = shl nuw nsw i32 %t2, %nbits
 288   ret i32 %t3
 289 }
 290
 291 ; Special test
 292
 293 declare void @llvm.assume(i1 %cond)
 294
 295 ; We can't simplify (%shiftnbits-%masknbits) but we have an assumption.
 296 define i32 @t11_assume_uge(i32 %x, i32 %masknbits, i32 %shiftnbits) {
 297 ; CHECK-LABEL: @t11_assume_uge(
 298 ; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i32 [[SHIFTNBITS:%.*]], [[MASKNBITS:%.*]]
 299 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
 300 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[MASKNBITS]]
 301 ; CHECK-NEXT:    [[T1:%.*]] = lshr i32 [[T0]], [[MASKNBITS]]
 302 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]
 303 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 304 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
 305 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
 306 ; CHECK-NEXT:    [[T4:%.*]] = shl i32 [[T2]], [[SHIFTNBITS]]
 307 ; CHECK-NEXT:    ret i32 [[T4]]
 308 ;
 309   %cmp = icmp uge i32 %shiftnbits, %masknbits
 310   call void @llvm.assume(i1 %cmp)
 311   %t0 = shl i32 -1, %masknbits
 312   %t1 = lshr i32 %t0, %masknbits
 313   %t2 = and i32 %t1, %x
 314   call void @use32(i32 %t0)
 315   call void @use32(i32 %t1)
 316   call void @use32(i32 %t2)
 317   %t4 = shl i32 %t2, %shiftnbits
 318   ret i32 %t4
 319 }
 320
 321 ; Negative tests
 322
 323 define i32 @n12_different_shamts0(i32 %x, i32 %nbits0, i32 %nbits1) {
 324 ; CHECK-LABEL: @n12_different_shamts0(
 325 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 [[X:%.*]], [[NBITS0:%.*]]
 326 ; CHECK-NEXT:    [[T1:%.*]] = lshr i32 [[T0]], [[NBITS1:%.*]]
 327 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[X]]
 328 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 329 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
 330 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
 331 ; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[T2]], [[NBITS0]]
 332 ; CHECK-NEXT:    ret i32 [[T3]]
 333 ;
 334   %t0 = shl i32 %x, %nbits0 ; different shift amts
 335   %t1 = lshr i32 %t0, %nbits1 ; different shift amts
 336   %t2 = and i32 %t1, %x
 337   call void @use32(i32 %t0)
 338   call void @use32(i32 %t1)
 339   call void @use32(i32 %t2)
 340   %t3 = shl i32 %t2, %nbits0
 341   ret i32 %t3
 342 }
 343
 344 define i32 @n13_different_shamts1(i32 %x, i32 %nbits0, i32 %nbits1) {
 345 ; CHECK-LABEL: @n13_different_shamts1(
 346 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 [[X:%.*]], [[NBITS0:%.*]]
 347 ; CHECK-NEXT:    [[T1:%.*]] = lshr i32 [[T0]], [[NBITS1:%.*]]
 348 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[X]]
 349 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 350 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
 351 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
 352 ; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[T2]], [[NBITS1]]
 353 ; CHECK-NEXT:    ret i32 [[T3]]
 354 ;
 355   %t0 = shl i32 %x, %nbits0 ; different shift amts
 356   %t1 = lshr i32 %t0, %nbits1 ; different shift amts
 357   %t2 = and i32 %t1, %x
 358   call void @use32(i32 %t0)
 359   call void @use32(i32 %t1)
 360   call void @use32(i32 %t2)
 361   %t3 = shl i32 %t2, %nbits1
 362   ret i32 %t3
 363 }