llvm/test/Transforms/InstCombine/and-xor-or.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -instcombine -S | FileCheck %s
   3
   4 ; a & (a ^ b) --> a & ~b
   5
   6 define i32 @and_xor_common_op(i32 %pa, i32 %pb) {
   7 ; CHECK-LABEL: @and_xor_common_op(
   8 ; CHECK-NEXT:    [[A:%.*]] = udiv i32 42, [[PA:%.*]]
   9 ; CHECK-NEXT:    [[B:%.*]] = udiv i32 43, [[PB:%.*]]
  10 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
  11 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[A]], [[TMP1]]
  12 ; CHECK-NEXT:    ret i32 [[R]]
  13 ;
  14   %a = udiv i32 42, %pa ; thwart complexity-based canonicalization
  15   %b = udiv i32 43, %pb ; thwart complexity-based canonicalization
  16   %xor = xor i32 %a, %b
  17   %r = and i32 %a, %xor
  18   ret i32 %r
  19 }
  20
  21 ; a & (b ^ a) --> a & ~b
  22
  23 define i32 @and_xor_common_op_commute1(i32 %pa, i32 %pb) {
  24 ; CHECK-LABEL: @and_xor_common_op_commute1(
  25 ; CHECK-NEXT:    [[A:%.*]] = udiv i32 42, [[PA:%.*]]
  26 ; CHECK-NEXT:    [[B:%.*]] = udiv i32 43, [[PB:%.*]]
  27 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
  28 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[A]], [[TMP1]]
  29 ; CHECK-NEXT:    ret i32 [[R]]
  30 ;
  31   %a = udiv i32 42, %pa ; thwart complexity-based canonicalization
  32   %b = udiv i32 43, %pb ; thwart complexity-based canonicalization
  33   %xor = xor i32 %b, %a
  34   %r = and i32 %a, %xor
  35   ret i32 %r
  36 }
  37
  38 ; (b ^ a) & a --> a & ~b
  39
  40 define i32 @and_xor_common_op_commute2(i32 %pa, i32 %pb) {
  41 ; CHECK-LABEL: @and_xor_common_op_commute2(
  42 ; CHECK-NEXT:    [[A:%.*]] = udiv i32 42, [[PA:%.*]]
  43 ; CHECK-NEXT:    [[B:%.*]] = udiv i32 43, [[PB:%.*]]
  44 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
  45 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[A]], [[TMP1]]
  46 ; CHECK-NEXT:    ret i32 [[R]]
  47 ;
  48   %a = udiv i32 42, %pa ; thwart complexity-based canonicalization
  49   %b = udiv i32 43, %pb ; thwart complexity-based canonicalization
  50   %xor = xor i32 %b, %a
  51   %r = and i32 %xor, %a
  52   ret i32 %r
  53 }
  54
  55 ; (a ^ b) & a --> a & ~b
  56
  57 define <2 x i32> @and_xor_common_op_commute3(<2 x i32> %pa, <2 x i32> %pb) {
  58 ; CHECK-LABEL: @and_xor_common_op_commute3(
  59 ; CHECK-NEXT:    [[A:%.*]] = udiv <2 x i32> <i32 42, i32 43>, [[PA:%.*]]
  60 ; CHECK-NEXT:    [[B:%.*]] = udiv <2 x i32> <i32 43, i32 42>, [[PB:%.*]]
  61 ; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i32> [[B]], <i32 -1, i32 -1>
  62 ; CHECK-NEXT:    [[R:%.*]] = and <2 x i32> [[A]], [[TMP1]]
  63 ; CHECK-NEXT:    ret <2 x i32> [[R]]
  64 ;
  65   %a = udiv <2 x i32> <i32 42, i32 43>, %pa ; thwart complexity-based canonicalization
  66   %b = udiv <2 x i32> <i32 43, i32 42>, %pb ; thwart complexity-based canonicalization
  67   %xor = xor <2 x i32> %a, %b
  68   %r = and <2 x i32> %xor, %a
  69   ret <2 x i32> %r
  70 }
  71
  72 ; It's ok to match a common constant.
  73 ; The xor should be a 'not' op (-1 constant).
  74
  75 define <4 x i32> @and_xor_common_op_constant(<4 x i32> %A) {
  76 ; CHECK-LABEL: @and_xor_common_op_constant(
  77 ; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i32> [[A:%.*]], <i32 -1, i32 -1, i32 -1, i32 -1>
  78 ; CHECK-NEXT:    [[TMP2:%.*]] = and <4 x i32> [[TMP1]], <i32 1, i32 2, i32 3, i32 4>
  79 ; CHECK-NEXT:    ret <4 x i32> [[TMP2]]
  80 ;
  81   %1 = xor <4 x i32> %A, <i32 1, i32 2, i32 3, i32 4>
  82   %2 = and <4 x i32> <i32 1, i32 2, i32 3, i32 4>, %1
  83   ret <4 x i32> %2
  84 }
  85
  86 ; a & (a ^ ~b) --> a & b
  87
  88 define i32 @and_xor_not_common_op(i32 %a, i32 %b) {
  89 ; CHECK-LABEL: @and_xor_not_common_op(
  90 ; CHECK-NEXT:    [[T4:%.*]] = and i32 [[A:%.*]], [[B:%.*]]
  91 ; CHECK-NEXT:    ret i32 [[T4]]
  92 ;
  93   %b2 = xor i32 %b, -1
  94   %t2 = xor i32 %a, %b2
  95   %t4 = and i32 %t2, %a
  96   ret i32 %t4
  97 }
  98
  99 ; a & (a ^ ~b) --> a & b
 100
 101 define i32 @and_xor_not_common_op_extrause(i32 %a, i32 %b, i32* %dst) {
 102 ; CHECK-LABEL: @and_xor_not_common_op_extrause(
 103 ; CHECK-NEXT:    [[B2:%.*]] = xor i32 [[B:%.*]], -1
 104 ; CHECK-NEXT:    store i32 [[B2]], i32* [[DST:%.*]], align 4
 105 ; CHECK-NEXT:    [[T4:%.*]] = and i32 [[A:%.*]], [[B]]
 106 ; CHECK-NEXT:    ret i32 [[T4]]
 107 ;
 108   %b2 = xor i32 %b, -1
 109   store i32 %b2, i32* %dst
 110   %t2 = xor i32 %a, %b2
 111   %t4 = and i32 %t2, %a
 112   ret i32 %t4
 113 }
 114
 115 ; a & ~(a ^ b) --> a & b
 116
 117 define i32 @and_not_xor_common_op(i32 %a, i32 %b) {
 118 ; CHECK-LABEL: @and_not_xor_common_op(
 119 ; CHECK-NEXT:    [[T4:%.*]] = and i32 [[A:%.*]], [[B:%.*]]
 120 ; CHECK-NEXT:    ret i32 [[T4]]
 121 ;
 122   %b2 = xor i32 %b, %a
 123   %t2 = xor i32 %b2, -1
 124   %t4 = and i32 %t2, %a
 125   ret i32 %t4
 126 }
 127
 128 declare i32 @gen32()
 129 define i32 @and_not_xor_common_op_commutative(i32 %b) {
 130 ; CHECK-LABEL: @and_not_xor_common_op_commutative(
 131 ; CHECK-NEXT:    [[A:%.*]] = call i32 @gen32()
 132 ; CHECK-NEXT:    [[T4:%.*]] = and i32 [[A]], [[B:%.*]]
 133 ; CHECK-NEXT:    ret i32 [[T4]]
 134 ;
 135   %a = call i32 @gen32()
 136   %b2 = xor i32 %a, %b ; swapped order
 137   %t2 = xor i32 %b2, -1
 138   %t4 = and i32 %a, %t2 ; swapped order
 139   ret i32 %t4
 140 }
 141
 142 ; rdar://10770603
 143 ; (x & y) | (x ^ y) -> x | y
 144
 145 define i64 @or(i64 %x, i64 %y) {
 146 ; CHECK-LABEL: @or(
 147 ; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Y:%.*]], [[X:%.*]]
 148 ; CHECK-NEXT:    ret i64 [[TMP1]]
 149 ;
 150   %1 = and i64 %y, %x
 151   %2 = xor i64 %y, %x
 152   %3 = add i64 %1, %2
 153   ret i64 %3
 154 }
 155
 156 ; (x & y) + (x ^ y) -> x | y
 157
 158 define i64 @or2(i64 %x, i64 %y) {
 159 ; CHECK-LABEL: @or2(
 160 ; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Y:%.*]], [[X:%.*]]
 161 ; CHECK-NEXT:    ret i64 [[TMP1]]
 162 ;
 163   %1 = and i64 %y, %x
 164   %2 = xor i64 %y, %x
 165   %3 = or i64 %1, %2
 166   ret i64 %3
 167 }
 168
 169 ; PR37098 - https://bugs.llvm.org/show_bug.cgi?id=37098
 170 ; Reassociate bitwise logic to eliminate a shift.
 171 ; There are 4 commuted * 3 shift ops * 3 logic ops = 36 potential variations of this fold.
 172 ; Mix the commutation options to provide coverage using less tests.
 173
 174 define i8 @and_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 175 ; CHECK-LABEL: @and_shl(
 176 ; CHECK-NEXT:    [[SX:%.*]] = shl i8 [[X:%.*]], [[SHAMT:%.*]]
 177 ; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]]
 178 ; CHECK-NEXT:    [[A:%.*]] = and i8 [[SX]], [[Z:%.*]]
 179 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[SY]], [[A]]
 180 ; CHECK-NEXT:    ret i8 [[R]]
 181 ;
 182   %sx = shl i8 %x, %shamt
 183   %sy = shl i8 %y, %shamt
 184   %a = and i8 %sx, %z
 185   %r = and i8 %sy, %a
 186   ret i8 %r
 187 }
 188
 189 define i8 @or_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 190 ; CHECK-LABEL: @or_shl(
 191 ; CHECK-NEXT:    [[SX:%.*]] = shl i8 [[X:%.*]], [[SHAMT:%.*]]
 192 ; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]]
 193 ; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z:%.*]]
 194 ; CHECK-NEXT:    [[R:%.*]] = or i8 [[A]], [[SY]]
 195 ; CHECK-NEXT:    ret i8 [[R]]
 196 ;
 197   %sx = shl i8 %x, %shamt
 198   %sy = shl i8 %y, %shamt
 199   %a = or i8 %sx, %z
 200   %r = or i8 %a, %sy
 201   ret i8 %r
 202 }
 203
 204 define i8 @xor_shl(i8 %x, i8 %y, i8 %zarg, i8 %shamt) {
 205 ; CHECK-LABEL: @xor_shl(
 206 ; CHECK-NEXT:    [[Z:%.*]] = sdiv i8 42, [[ZARG:%.*]]
 207 ; CHECK-NEXT:    [[SX:%.*]] = shl i8 [[X:%.*]], [[SHAMT:%.*]]
 208 ; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]]
 209 ; CHECK-NEXT:    [[A:%.*]] = xor i8 [[Z]], [[SX]]
 210 ; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], [[SY]]
 211 ; CHECK-NEXT:    ret i8 [[R]]
 212 ;
 213   %z = sdiv i8 42, %zarg ; thwart complexity-based canonicalization
 214   %sx = shl i8 %x, %shamt
 215   %sy = shl i8 %y, %shamt
 216   %a = xor i8 %z, %sx
 217   %r = xor i8 %a, %sy
 218   ret i8 %r
 219 }
 220
 221 define i8 @and_lshr(i8 %x, i8 %y, i8 %zarg, i8 %shamt) {
 222 ; CHECK-LABEL: @and_lshr(
 223 ; CHECK-NEXT:    [[Z:%.*]] = sdiv i8 42, [[ZARG:%.*]]
 224 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]]
 225 ; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]]
 226 ; CHECK-NEXT:    [[A:%.*]] = and i8 [[Z]], [[SX]]
 227 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[SY]], [[A]]
 228 ; CHECK-NEXT:    ret i8 [[R]]
 229 ;
 230   %z = sdiv i8 42, %zarg ; thwart complexity-based canonicalization
 231   %sx = lshr i8 %x, %shamt
 232   %sy = lshr i8 %y, %shamt
 233   %a = and i8 %z, %sx
 234   %r = and i8 %sy, %a
 235   ret i8 %r
 236 }
 237
 238 define i8 @or_lshr(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 239 ; CHECK-LABEL: @or_lshr(
 240 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]]
 241 ; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]]
 242 ; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z:%.*]]
 243 ; CHECK-NEXT:    [[R:%.*]] = or i8 [[SY]], [[A]]
 244 ; CHECK-NEXT:    ret i8 [[R]]
 245 ;
 246   %sx = lshr i8 %x, %shamt
 247   %sy = lshr i8 %y, %shamt
 248   %a = or i8 %sx, %z
 249   %r = or i8 %sy, %a
 250   ret i8 %r
 251 }
 252
 253 define i8 @xor_lshr(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 254 ; CHECK-LABEL: @xor_lshr(
 255 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]]
 256 ; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]]
 257 ; CHECK-NEXT:    [[A:%.*]] = xor i8 [[SX]], [[Z:%.*]]
 258 ; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], [[SY]]
 259 ; CHECK-NEXT:    ret i8 [[R]]
 260 ;
 261   %sx = lshr i8 %x, %shamt
 262   %sy = lshr i8 %y, %shamt
 263   %a = xor i8 %sx, %z
 264   %r = xor i8 %a, %sy
 265   ret i8 %r
 266 }
 267
 268 define i8 @and_ashr(i8 %x, i8 %y, i8 %zarg, i8 %shamt) {
 269 ; CHECK-LABEL: @and_ashr(
 270 ; CHECK-NEXT:    [[Z:%.*]] = sdiv i8 42, [[ZARG:%.*]]
 271 ; CHECK-NEXT:    [[SX:%.*]] = ashr i8 [[X:%.*]], [[SHAMT:%.*]]
 272 ; CHECK-NEXT:    [[SY:%.*]] = ashr i8 [[Y:%.*]], [[SHAMT]]
 273 ; CHECK-NEXT:    [[A:%.*]] = and i8 [[Z]], [[SX]]
 274 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[A]], [[SY]]
 275 ; CHECK-NEXT:    ret i8 [[R]]
 276 ;
 277   %z = sdiv i8 42, %zarg ; thwart complexity-based canonicalization
 278   %sx = ashr i8 %x, %shamt
 279   %sy = ashr i8 %y, %shamt
 280   %a = and i8 %z, %sx
 281   %r = and i8 %a, %sy
 282   ret i8 %r
 283 }
 284
 285 define i8 @or_ashr(i8 %x, i8 %y, i8 %zarg, i8 %shamt) {
 286 ; CHECK-LABEL: @or_ashr(
 287 ; CHECK-NEXT:    [[Z:%.*]] = sdiv i8 42, [[ZARG:%.*]]
 288 ; CHECK-NEXT:    [[SX:%.*]] = ashr i8 [[X:%.*]], [[SHAMT:%.*]]
 289 ; CHECK-NEXT:    [[SY:%.*]] = ashr i8 [[Y:%.*]], [[SHAMT]]
 290 ; CHECK-NEXT:    [[A:%.*]] = or i8 [[Z]], [[SX]]
 291 ; CHECK-NEXT:    [[R:%.*]] = or i8 [[SY]], [[A]]
 292 ; CHECK-NEXT:    ret i8 [[R]]
 293 ;
 294   %z = sdiv i8 42, %zarg ; thwart complexity-based canonicalization
 295   %sx = ashr i8 %x, %shamt
 296   %sy = ashr i8 %y, %shamt
 297   %a = or i8 %z, %sx
 298   %r = or i8 %sy, %a
 299   ret i8 %r
 300 }
 301
 302 define <2 x i8> @xor_ashr(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z, <2 x i8> %shamt) {
 303 ; CHECK-LABEL: @xor_ashr(
 304 ; CHECK-NEXT:    [[SX:%.*]] = ashr <2 x i8> [[X:%.*]], [[SHAMT:%.*]]
 305 ; CHECK-NEXT:    [[SY:%.*]] = ashr <2 x i8> [[Y:%.*]], [[SHAMT]]
 306 ; CHECK-NEXT:    [[A:%.*]] = xor <2 x i8> [[SX]], [[Z:%.*]]
 307 ; CHECK-NEXT:    [[R:%.*]] = xor <2 x i8> [[A]], [[SY]]
 308 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 309 ;
 310   %sx = ashr <2 x i8> %x, %shamt
 311   %sy = ashr <2 x i8> %y, %shamt
 312   %a = xor <2 x i8> %sx, %z
 313   %r = xor <2 x i8> %a, %sy
 314   ret <2 x i8> %r
 315 }
 316
 317 ; Negative test - different logic ops
 318
 319 define i8 @or_and_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 320 ; CHECK-LABEL: @or_and_shl(
 321 ; CHECK-NEXT:    [[SX:%.*]] = shl i8 [[X:%.*]], [[SHAMT:%.*]]
 322 ; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]]
 323 ; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z:%.*]]
 324 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[SY]], [[A]]
 325 ; CHECK-NEXT:    ret i8 [[R]]
 326 ;
 327   %sx = shl i8 %x, %shamt
 328   %sy = shl i8 %y, %shamt
 329   %a = or i8 %sx, %z
 330   %r = and i8 %sy, %a
 331   ret i8 %r
 332 }
 333
 334 ; Negative test - different shift ops
 335
 336 define i8 @or_lshr_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 337 ; CHECK-LABEL: @or_lshr_shl(
 338 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]]
 339 ; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]]
 340 ; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z:%.*]]
 341 ; CHECK-NEXT:    [[R:%.*]] = or i8 [[A]], [[SY]]
 342 ; CHECK-NEXT:    ret i8 [[R]]
 343 ;
 344   %sx = lshr i8 %x, %shamt
 345   %sy = shl i8 %y, %shamt
 346   %a = or i8 %sx, %z
 347   %r = or i8 %a, %sy
 348   ret i8 %r
 349 }
 350
 351 ; Negative test - different shift amounts
 352
 353 define i8 @or_lshr_shamt2(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 354 ; CHECK-LABEL: @or_lshr_shamt2(
 355 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X:%.*]], 5
 356 ; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT:%.*]]
 357 ; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z:%.*]]
 358 ; CHECK-NEXT:    [[R:%.*]] = or i8 [[SY]], [[A]]
 359 ; CHECK-NEXT:    ret i8 [[R]]
 360 ;
 361   %sx = lshr i8 %x, 5
 362   %sy = lshr i8 %y, %shamt
 363   %a = or i8 %sx, %z
 364   %r = or i8 %sy, %a
 365   ret i8 %r
 366 }
 367
 368 ; Negative test - multi-use
 369
 370 define i8 @xor_lshr_multiuse(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 371 ; CHECK-LABEL: @xor_lshr_multiuse(
 372 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]]
 373 ; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]]
 374 ; CHECK-NEXT:    [[A:%.*]] = xor i8 [[SX]], [[Z:%.*]]
 375 ; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], [[SY]]
 376 ; CHECK-NEXT:    [[R2:%.*]] = sdiv i8 [[A]], [[R]]
 377 ; CHECK-NEXT:    ret i8 [[R2]]
 378 ;
 379   %sx = lshr i8 %x, %shamt
 380   %sy = lshr i8 %y, %shamt
 381   %a = xor i8 %sx, %z
 382   %r = xor i8 %a, %sy
 383   %r2 = sdiv i8 %a, %r
 384   ret i8 %r2
 385 }
 386