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

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature
   2 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
   3
   4 declare void @use(i32)
   5
   6 ; a & (a ^ b) --> a & ~b
   7
   8 define i32 @and_xor_common_op(i32 %pa, i32 %pb) {
   9 ; CHECK-LABEL: define {{[^@]+}}@and_xor_common_op
  10 ; CHECK-SAME: (i32 [[PA:%.*]], i32 [[PB:%.*]]) {
  11 ; CHECK-NEXT:    [[A:%.*]] = udiv i32 42, [[PA]]
  12 ; CHECK-NEXT:    [[B:%.*]] = udiv i32 43, [[PB]]
  13 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
  14 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[A]], [[TMP1]]
  15 ; CHECK-NEXT:    ret i32 [[R]]
  16 ;
  17   %a = udiv i32 42, %pa ; thwart complexity-based canonicalization
  18   %b = udiv i32 43, %pb ; thwart complexity-based canonicalization
  19   %xor = xor i32 %a, %b
  20   %r = and i32 %a, %xor
  21   ret i32 %r
  22 }
  23
  24 ; a & (b ^ a) --> a & ~b
  25
  26 define i32 @and_xor_common_op_commute1(i32 %pa, i32 %pb) {
  27 ; CHECK-LABEL: define {{[^@]+}}@and_xor_common_op_commute1
  28 ; CHECK-SAME: (i32 [[PA:%.*]], i32 [[PB:%.*]]) {
  29 ; CHECK-NEXT:    [[A:%.*]] = udiv i32 42, [[PA]]
  30 ; CHECK-NEXT:    [[B:%.*]] = udiv i32 43, [[PB]]
  31 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
  32 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[A]], [[TMP1]]
  33 ; CHECK-NEXT:    ret i32 [[R]]
  34 ;
  35   %a = udiv i32 42, %pa ; thwart complexity-based canonicalization
  36   %b = udiv i32 43, %pb ; thwart complexity-based canonicalization
  37   %xor = xor i32 %b, %a
  38   %r = and i32 %a, %xor
  39   ret i32 %r
  40 }
  41
  42 ; (b ^ a) & a --> a & ~b
  43
  44 define i32 @and_xor_common_op_commute2(i32 %pa, i32 %pb) {
  45 ; CHECK-LABEL: define {{[^@]+}}@and_xor_common_op_commute2
  46 ; CHECK-SAME: (i32 [[PA:%.*]], i32 [[PB:%.*]]) {
  47 ; CHECK-NEXT:    [[A:%.*]] = udiv i32 42, [[PA]]
  48 ; CHECK-NEXT:    [[B:%.*]] = udiv i32 43, [[PB]]
  49 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
  50 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[A]], [[TMP1]]
  51 ; CHECK-NEXT:    ret i32 [[R]]
  52 ;
  53   %a = udiv i32 42, %pa ; thwart complexity-based canonicalization
  54   %b = udiv i32 43, %pb ; thwart complexity-based canonicalization
  55   %xor = xor i32 %b, %a
  56   %r = and i32 %xor, %a
  57   ret i32 %r
  58 }
  59
  60 ; (a ^ b) & a --> a & ~b
  61
  62 define <2 x i32> @and_xor_common_op_commute3(<2 x i32> %pa, <2 x i32> %pb) {
  63 ; CHECK-LABEL: define {{[^@]+}}@and_xor_common_op_commute3
  64 ; CHECK-SAME: (<2 x i32> [[PA:%.*]], <2 x i32> [[PB:%.*]]) {
  65 ; CHECK-NEXT:    [[A:%.*]] = udiv <2 x i32> <i32 42, i32 43>, [[PA]]
  66 ; CHECK-NEXT:    [[B:%.*]] = udiv <2 x i32> <i32 43, i32 42>, [[PB]]
  67 ; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i32> [[B]], <i32 -1, i32 -1>
  68 ; CHECK-NEXT:    [[R:%.*]] = and <2 x i32> [[A]], [[TMP1]]
  69 ; CHECK-NEXT:    ret <2 x i32> [[R]]
  70 ;
  71   %a = udiv <2 x i32> <i32 42, i32 43>, %pa ; thwart complexity-based canonicalization
  72   %b = udiv <2 x i32> <i32 43, i32 42>, %pb ; thwart complexity-based canonicalization
  73   %xor = xor <2 x i32> %a, %b
  74   %r = and <2 x i32> %xor, %a
  75   ret <2 x i32> %r
  76 }
  77
  78 ; It's ok to match a common constant.
  79 ; The xor should be a 'not' op (-1 constant).
  80
  81 define <4 x i32> @and_xor_common_op_constant(<4 x i32> %A) {
  82 ; CHECK-LABEL: define {{[^@]+}}@and_xor_common_op_constant
  83 ; CHECK-SAME: (<4 x i32> [[A:%.*]]) {
  84 ; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i32> [[A]], <i32 -1, i32 -1, i32 -1, i32 -1>
  85 ; CHECK-NEXT:    [[TMP2:%.*]] = and <4 x i32> [[TMP1]], <i32 1, i32 2, i32 3, i32 4>
  86 ; CHECK-NEXT:    ret <4 x i32> [[TMP2]]
  87 ;
  88   %1 = xor <4 x i32> %A, <i32 1, i32 2, i32 3, i32 4>
  89   %2 = and <4 x i32> <i32 1, i32 2, i32 3, i32 4>, %1
  90   ret <4 x i32> %2
  91 }
  92
  93 ; a & (a ^ ~b) --> a & b
  94
  95 define i32 @and_xor_not_common_op(i32 %a, i32 %b) {
  96 ; CHECK-LABEL: define {{[^@]+}}@and_xor_not_common_op
  97 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
  98 ; CHECK-NEXT:    [[T4:%.*]] = and i32 [[A]], [[B]]
  99 ; CHECK-NEXT:    ret i32 [[T4]]
 100 ;
 101   %b2 = xor i32 %b, -1
 102   %t2 = xor i32 %a, %b2
 103   %t4 = and i32 %t2, %a
 104   ret i32 %t4
 105 }
 106
 107 ; a & (a ^ ~b) --> a & b
 108
 109 define i32 @and_xor_not_common_op_extrause(i32 %a, i32 %b, i32* %dst) {
 110 ; CHECK-LABEL: define {{[^@]+}}@and_xor_not_common_op_extrause
 111 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32* [[DST:%.*]]) {
 112 ; CHECK-NEXT:    [[B2:%.*]] = xor i32 [[B]], -1
 113 ; CHECK-NEXT:    store i32 [[B2]], i32* [[DST]], align 4
 114 ; CHECK-NEXT:    [[T4:%.*]] = and i32 [[A]], [[B]]
 115 ; CHECK-NEXT:    ret i32 [[T4]]
 116 ;
 117   %b2 = xor i32 %b, -1
 118   store i32 %b2, i32* %dst
 119   %t2 = xor i32 %a, %b2
 120   %t4 = and i32 %t2, %a
 121   ret i32 %t4
 122 }
 123
 124 ; a & ~(a ^ b) --> a & b
 125
 126 define i32 @and_not_xor_common_op(i32 %a, i32 %b) {
 127 ; CHECK-LABEL: define {{[^@]+}}@and_not_xor_common_op
 128 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
 129 ; CHECK-NEXT:    [[T4:%.*]] = and i32 [[A]], [[B]]
 130 ; CHECK-NEXT:    ret i32 [[T4]]
 131 ;
 132   %b2 = xor i32 %b, %a
 133   %t2 = xor i32 %b2, -1
 134   %t4 = and i32 %t2, %a
 135   ret i32 %t4
 136 }
 137
 138 declare i32 @gen32()
 139 define i32 @and_not_xor_common_op_commutative(i32 %b) {
 140 ; CHECK-LABEL: define {{[^@]+}}@and_not_xor_common_op_commutative
 141 ; CHECK-SAME: (i32 [[B:%.*]]) {
 142 ; CHECK-NEXT:    [[A:%.*]] = call i32 @gen32()
 143 ; CHECK-NEXT:    [[T4:%.*]] = and i32 [[A]], [[B]]
 144 ; CHECK-NEXT:    ret i32 [[T4]]
 145 ;
 146   %a = call i32 @gen32()
 147   %b2 = xor i32 %a, %b ; swapped order
 148   %t2 = xor i32 %b2, -1
 149   %t4 = and i32 %a, %t2 ; swapped order
 150   ret i32 %t4
 151 }
 152
 153 ; rdar://10770603
 154 ; (x & y) | (x ^ y) -> x | y
 155
 156 define i64 @or(i64 %x, i64 %y) {
 157 ; CHECK-LABEL: define {{[^@]+}}@or
 158 ; CHECK-SAME: (i64 [[X:%.*]], i64 [[Y:%.*]]) {
 159 ; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Y]], [[X]]
 160 ; CHECK-NEXT:    ret i64 [[TMP1]]
 161 ;
 162   %1 = and i64 %y, %x
 163   %2 = xor i64 %y, %x
 164   %3 = add i64 %1, %2
 165   ret i64 %3
 166 }
 167
 168 ; (x & y) + (x ^ y) -> x | y
 169
 170 define i64 @or2(i64 %x, i64 %y) {
 171 ; CHECK-LABEL: define {{[^@]+}}@or2
 172 ; CHECK-SAME: (i64 [[X:%.*]], i64 [[Y:%.*]]) {
 173 ; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Y]], [[X]]
 174 ; CHECK-NEXT:    ret i64 [[TMP1]]
 175 ;
 176   %1 = and i64 %y, %x
 177   %2 = xor i64 %y, %x
 178   %3 = or i64 %1, %2
 179   ret i64 %3
 180 }
 181
 182 ; ((x & y) ^ z) | y -> (z | y)
 183
 184 define i64 @and_xor_or1(i64 %px, i64 %py, i64 %pz) {
 185 ; CHECK-LABEL: define {{[^@]+}}@and_xor_or1
 186 ; CHECK-SAME: (i64 [[PX:%.*]], i64 [[PY:%.*]], i64 [[PZ:%.*]]) {
 187 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY]]
 188 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ]]
 189 ; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Z]], [[Y]]
 190 ; CHECK-NEXT:    ret i64 [[TMP1]]
 191 ;
 192   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
 193   %y = udiv i64 42, %py ; thwart complexity-based canonicalization
 194   %z = udiv i64 42, %pz ; thwart complexity-based canonicalization
 195   %1 = and i64 %x, %y
 196   %2 = xor i64 %1, %z
 197   %3 = or i64 %2, %y
 198   ret i64 %3
 199 }
 200
 201 ; ((y & x) ^ z) | y -> (z | y)
 202
 203 define i64 @and_xor_or2(i64 %px, i64 %py, i64 %pz) {
 204 ; CHECK-LABEL: define {{[^@]+}}@and_xor_or2
 205 ; CHECK-SAME: (i64 [[PX:%.*]], i64 [[PY:%.*]], i64 [[PZ:%.*]]) {
 206 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY]]
 207 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ]]
 208 ; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Z]], [[Y]]
 209 ; CHECK-NEXT:    ret i64 [[TMP1]]
 210 ;
 211   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
 212   %y = udiv i64 42, %py ; thwart complexity-based canonicalization
 213   %z = udiv i64 42, %pz ; thwart complexity-based canonicalization
 214   %1 = and i64 %y, %x
 215   %2 = xor i64 %1, %z
 216   %3 = or i64 %2, %y
 217   ret i64 %3
 218 }
 219
 220 ; (z ^ (x & y)) | y -> (z | y)
 221
 222 define i64 @and_xor_or3(i64 %px, i64 %py, i64 %pz) {
 223 ; CHECK-LABEL: define {{[^@]+}}@and_xor_or3
 224 ; CHECK-SAME: (i64 [[PX:%.*]], i64 [[PY:%.*]], i64 [[PZ:%.*]]) {
 225 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY]]
 226 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ]]
 227 ; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Z]], [[Y]]
 228 ; CHECK-NEXT:    ret i64 [[TMP1]]
 229 ;
 230   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
 231   %y = udiv i64 42, %py ; thwart complexity-based canonicalization
 232   %z = udiv i64 42, %pz ; thwart complexity-based canonicalization
 233   %1 = and i64 %x, %y
 234   %2 = xor i64 %z, %1
 235   %3 = or i64 %2, %y
 236   ret i64 %3
 237 }
 238
 239 ; (z ^ (y & x)) | y -> (z | y)
 240
 241 define i64 @and_xor_or4(i64 %px, i64 %py, i64 %pz) {
 242 ; CHECK-LABEL: define {{[^@]+}}@and_xor_or4
 243 ; CHECK-SAME: (i64 [[PX:%.*]], i64 [[PY:%.*]], i64 [[PZ:%.*]]) {
 244 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY]]
 245 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ]]
 246 ; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Z]], [[Y]]
 247 ; CHECK-NEXT:    ret i64 [[TMP1]]
 248 ;
 249   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
 250   %y = udiv i64 42, %py ; thwart complexity-based canonicalization
 251   %z = udiv i64 42, %pz ; thwart complexity-based canonicalization
 252   %1 = and i64 %y, %x
 253   %2 = xor i64 %z, %1
 254   %3 = or i64 %2, %y
 255   ret i64 %3
 256 }
 257
 258 ; y | ((x & y) ^ z) -> (y | z)
 259
 260 define i64 @and_xor_or5(i64 %px, i64 %py, i64 %pz) {
 261 ; CHECK-LABEL: define {{[^@]+}}@and_xor_or5
 262 ; CHECK-SAME: (i64 [[PX:%.*]], i64 [[PY:%.*]], i64 [[PZ:%.*]]) {
 263 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY]]
 264 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ]]
 265 ; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Y]], [[Z]]
 266 ; CHECK-NEXT:    ret i64 [[TMP1]]
 267 ;
 268   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
 269   %y = udiv i64 42, %py ; thwart complexity-based canonicalization
 270   %z = udiv i64 42, %pz ; thwart complexity-based canonicalization
 271   %1 = and i64 %x, %y
 272   %2 = xor i64 %1, %z
 273   %3 = or i64 %y, %2
 274   ret i64 %3
 275 }
 276
 277 ; y | ((y & x) ^ z) -> (y | z)
 278
 279 define i64 @and_xor_or6(i64 %px, i64 %py, i64 %pz) {
 280 ; CHECK-LABEL: define {{[^@]+}}@and_xor_or6
 281 ; CHECK-SAME: (i64 [[PX:%.*]], i64 [[PY:%.*]], i64 [[PZ:%.*]]) {
 282 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY]]
 283 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ]]
 284 ; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Y]], [[Z]]
 285 ; CHECK-NEXT:    ret i64 [[TMP1]]
 286 ;
 287   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
 288   %y = udiv i64 42, %py ; thwart complexity-based canonicalization
 289   %z = udiv i64 42, %pz ; thwart complexity-based canonicalization
 290   %1 = and i64 %y, %x
 291   %2 = xor i64 %1, %z
 292   %3 = or i64 %y, %2
 293   ret i64 %3
 294 }
 295
 296 ; y | (z ^ (x & y)) -> (y | z)
 297
 298 define i64 @and_xor_or7(i64 %px, i64 %py, i64 %pz) {
 299 ; CHECK-LABEL: define {{[^@]+}}@and_xor_or7
 300 ; CHECK-SAME: (i64 [[PX:%.*]], i64 [[PY:%.*]], i64 [[PZ:%.*]]) {
 301 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY]]
 302 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ]]
 303 ; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Y]], [[Z]]
 304 ; CHECK-NEXT:    ret i64 [[TMP1]]
 305 ;
 306   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
 307   %y = udiv i64 42, %py ; thwart complexity-based canonicalization
 308   %z = udiv i64 42, %pz ; thwart complexity-based canonicalization
 309   %1 = and i64 %x, %y
 310   %2 = xor i64 %z, %1
 311   %3 = or i64 %y, %2
 312   ret i64 %3
 313 }
 314
 315 ; y | (z ^ (y & x)) -> (y | z)
 316
 317 define i64 @and_xor_or8(i64 %px, i64 %py, i64 %pz) {
 318 ; CHECK-LABEL: define {{[^@]+}}@and_xor_or8
 319 ; CHECK-SAME: (i64 [[PX:%.*]], i64 [[PY:%.*]], i64 [[PZ:%.*]]) {
 320 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY]]
 321 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ]]
 322 ; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Y]], [[Z]]
 323 ; CHECK-NEXT:    ret i64 [[TMP1]]
 324 ;
 325   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
 326   %y = udiv i64 42, %py ; thwart complexity-based canonicalization
 327   %z = udiv i64 42, %pz ; thwart complexity-based canonicalization
 328   %1 = and i64 %y, %x
 329   %2 = xor i64 %z, %1
 330   %3 = or i64 %y, %2
 331   ret i64 %3
 332 }
 333
 334 ; w | (z ^ (y & x))
 335
 336 define i64 @and_xor_or_negative(i64 %x, i64 %y, i64 %z, i64 %w) {
 337 ; CHECK-LABEL: define {{[^@]+}}@and_xor_or_negative
 338 ; CHECK-SAME: (i64 [[X:%.*]], i64 [[Y:%.*]], i64 [[Z:%.*]], i64 [[W:%.*]]) {
 339 ; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[Y]], [[X]]
 340 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i64 [[TMP1]], [[Z]]
 341 ; CHECK-NEXT:    [[TMP3:%.*]] = or i64 [[TMP2]], [[W]]
 342 ; CHECK-NEXT:    ret i64 [[TMP3]]
 343 ;
 344   %1 = and i64 %y, %x
 345   %2 = xor i64 %z, %1
 346   %3 = or i64 %w, %2
 347   ret i64 %3
 348 }
 349
 350 ; PR37098 - https://bugs.llvm.org/show_bug.cgi?id=37098
 351 ; Reassociate bitwise logic to eliminate a shift.
 352 ; There are 4 commuted * 3 shift ops * 3 logic ops = 36 potential variations of this fold.
 353 ; Mix the commutation options to provide coverage using less tests.
 354
 355 define i8 @and_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 356 ; CHECK-LABEL: define {{[^@]+}}@and_shl
 357 ; CHECK-SAME: (i8 [[X:%.*]], i8 [[Y:%.*]], i8 [[Z:%.*]], i8 [[SHAMT:%.*]]) {
 358 ; CHECK-NEXT:    [[SX:%.*]] = shl i8 [[X]], [[SHAMT]]
 359 ; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y]], [[SHAMT]]
 360 ; CHECK-NEXT:    [[A:%.*]] = and i8 [[SX]], [[Z]]
 361 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[SY]], [[A]]
 362 ; CHECK-NEXT:    ret i8 [[R]]
 363 ;
 364   %sx = shl i8 %x, %shamt
 365   %sy = shl i8 %y, %shamt
 366   %a = and i8 %sx, %z
 367   %r = and i8 %sy, %a
 368   ret i8 %r
 369 }
 370
 371 define i8 @or_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 372 ; CHECK-LABEL: define {{[^@]+}}@or_shl
 373 ; CHECK-SAME: (i8 [[X:%.*]], i8 [[Y:%.*]], i8 [[Z:%.*]], i8 [[SHAMT:%.*]]) {
 374 ; CHECK-NEXT:    [[SX:%.*]] = shl i8 [[X]], [[SHAMT]]
 375 ; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y]], [[SHAMT]]
 376 ; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z]]
 377 ; CHECK-NEXT:    [[R:%.*]] = or i8 [[A]], [[SY]]
 378 ; CHECK-NEXT:    ret i8 [[R]]
 379 ;
 380   %sx = shl i8 %x, %shamt
 381   %sy = shl i8 %y, %shamt
 382   %a = or i8 %sx, %z
 383   %r = or i8 %a, %sy
 384   ret i8 %r
 385 }
 386
 387 define i8 @xor_shl(i8 %x, i8 %y, i8 %zarg, i8 %shamt) {
 388 ; CHECK-LABEL: define {{[^@]+}}@xor_shl
 389 ; CHECK-SAME: (i8 [[X:%.*]], i8 [[Y:%.*]], i8 [[ZARG:%.*]], i8 [[SHAMT:%.*]]) {
 390 ; CHECK-NEXT:    [[Z:%.*]] = sdiv i8 42, [[ZARG]]
 391 ; CHECK-NEXT:    [[SX:%.*]] = shl i8 [[X]], [[SHAMT]]
 392 ; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y]], [[SHAMT]]
 393 ; CHECK-NEXT:    [[A:%.*]] = xor i8 [[Z]], [[SX]]
 394 ; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], [[SY]]
 395 ; CHECK-NEXT:    ret i8 [[R]]
 396 ;
 397   %z = sdiv i8 42, %zarg ; thwart complexity-based canonicalization
 398   %sx = shl i8 %x, %shamt
 399   %sy = shl i8 %y, %shamt
 400   %a = xor i8 %z, %sx
 401   %r = xor i8 %a, %sy
 402   ret i8 %r
 403 }
 404
 405 define i8 @and_lshr(i8 %x, i8 %y, i8 %zarg, i8 %shamt) {
 406 ; CHECK-LABEL: define {{[^@]+}}@and_lshr
 407 ; CHECK-SAME: (i8 [[X:%.*]], i8 [[Y:%.*]], i8 [[ZARG:%.*]], i8 [[SHAMT:%.*]]) {
 408 ; CHECK-NEXT:    [[Z:%.*]] = sdiv i8 42, [[ZARG]]
 409 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X]], [[SHAMT]]
 410 ; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y]], [[SHAMT]]
 411 ; CHECK-NEXT:    [[A:%.*]] = and i8 [[Z]], [[SX]]
 412 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[SY]], [[A]]
 413 ; CHECK-NEXT:    ret i8 [[R]]
 414 ;
 415   %z = sdiv i8 42, %zarg ; thwart complexity-based canonicalization
 416   %sx = lshr i8 %x, %shamt
 417   %sy = lshr i8 %y, %shamt
 418   %a = and i8 %z, %sx
 419   %r = and i8 %sy, %a
 420   ret i8 %r
 421 }
 422
 423 define i8 @or_lshr(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 424 ; CHECK-LABEL: define {{[^@]+}}@or_lshr
 425 ; CHECK-SAME: (i8 [[X:%.*]], i8 [[Y:%.*]], i8 [[Z:%.*]], i8 [[SHAMT:%.*]]) {
 426 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X]], [[SHAMT]]
 427 ; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y]], [[SHAMT]]
 428 ; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z]]
 429 ; CHECK-NEXT:    [[R:%.*]] = or i8 [[SY]], [[A]]
 430 ; CHECK-NEXT:    ret i8 [[R]]
 431 ;
 432   %sx = lshr i8 %x, %shamt
 433   %sy = lshr i8 %y, %shamt
 434   %a = or i8 %sx, %z
 435   %r = or i8 %sy, %a
 436   ret i8 %r
 437 }
 438
 439 define i8 @xor_lshr(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 440 ; CHECK-LABEL: define {{[^@]+}}@xor_lshr
 441 ; CHECK-SAME: (i8 [[X:%.*]], i8 [[Y:%.*]], i8 [[Z:%.*]], i8 [[SHAMT:%.*]]) {
 442 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X]], [[SHAMT]]
 443 ; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y]], [[SHAMT]]
 444 ; CHECK-NEXT:    [[A:%.*]] = xor i8 [[SX]], [[Z]]
 445 ; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], [[SY]]
 446 ; CHECK-NEXT:    ret i8 [[R]]
 447 ;
 448   %sx = lshr i8 %x, %shamt
 449   %sy = lshr i8 %y, %shamt
 450   %a = xor i8 %sx, %z
 451   %r = xor i8 %a, %sy
 452   ret i8 %r
 453 }
 454
 455 define i8 @and_ashr(i8 %x, i8 %y, i8 %zarg, i8 %shamt) {
 456 ; CHECK-LABEL: define {{[^@]+}}@and_ashr
 457 ; CHECK-SAME: (i8 [[X:%.*]], i8 [[Y:%.*]], i8 [[ZARG:%.*]], i8 [[SHAMT:%.*]]) {
 458 ; CHECK-NEXT:    [[Z:%.*]] = sdiv i8 42, [[ZARG]]
 459 ; CHECK-NEXT:    [[SX:%.*]] = ashr i8 [[X]], [[SHAMT]]
 460 ; CHECK-NEXT:    [[SY:%.*]] = ashr i8 [[Y]], [[SHAMT]]
 461 ; CHECK-NEXT:    [[A:%.*]] = and i8 [[Z]], [[SX]]
 462 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[A]], [[SY]]
 463 ; CHECK-NEXT:    ret i8 [[R]]
 464 ;
 465   %z = sdiv i8 42, %zarg ; thwart complexity-based canonicalization
 466   %sx = ashr i8 %x, %shamt
 467   %sy = ashr i8 %y, %shamt
 468   %a = and i8 %z, %sx
 469   %r = and i8 %a, %sy
 470   ret i8 %r
 471 }
 472
 473 define i8 @or_ashr(i8 %x, i8 %y, i8 %zarg, i8 %shamt) {
 474 ; CHECK-LABEL: define {{[^@]+}}@or_ashr
 475 ; CHECK-SAME: (i8 [[X:%.*]], i8 [[Y:%.*]], i8 [[ZARG:%.*]], i8 [[SHAMT:%.*]]) {
 476 ; CHECK-NEXT:    [[Z:%.*]] = sdiv i8 42, [[ZARG]]
 477 ; CHECK-NEXT:    [[SX:%.*]] = ashr i8 [[X]], [[SHAMT]]
 478 ; CHECK-NEXT:    [[SY:%.*]] = ashr i8 [[Y]], [[SHAMT]]
 479 ; CHECK-NEXT:    [[A:%.*]] = or i8 [[Z]], [[SX]]
 480 ; CHECK-NEXT:    [[R:%.*]] = or i8 [[SY]], [[A]]
 481 ; CHECK-NEXT:    ret i8 [[R]]
 482 ;
 483   %z = sdiv i8 42, %zarg ; thwart complexity-based canonicalization
 484   %sx = ashr i8 %x, %shamt
 485   %sy = ashr i8 %y, %shamt
 486   %a = or i8 %z, %sx
 487   %r = or i8 %sy, %a
 488   ret i8 %r
 489 }
 490
 491 define <2 x i8> @xor_ashr(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z, <2 x i8> %shamt) {
 492 ; CHECK-LABEL: define {{[^@]+}}@xor_ashr
 493 ; CHECK-SAME: (<2 x i8> [[X:%.*]], <2 x i8> [[Y:%.*]], <2 x i8> [[Z:%.*]], <2 x i8> [[SHAMT:%.*]]) {
 494 ; CHECK-NEXT:    [[SX:%.*]] = ashr <2 x i8> [[X]], [[SHAMT]]
 495 ; CHECK-NEXT:    [[SY:%.*]] = ashr <2 x i8> [[Y]], [[SHAMT]]
 496 ; CHECK-NEXT:    [[A:%.*]] = xor <2 x i8> [[SX]], [[Z]]
 497 ; CHECK-NEXT:    [[R:%.*]] = xor <2 x i8> [[A]], [[SY]]
 498 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 499 ;
 500   %sx = ashr <2 x i8> %x, %shamt
 501   %sy = ashr <2 x i8> %y, %shamt
 502   %a = xor <2 x i8> %sx, %z
 503   %r = xor <2 x i8> %a, %sy
 504   ret <2 x i8> %r
 505 }
 506
 507 ; Negative test - different logic ops
 508
 509 define i8 @or_and_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 510 ; CHECK-LABEL: define {{[^@]+}}@or_and_shl
 511 ; CHECK-SAME: (i8 [[X:%.*]], i8 [[Y:%.*]], i8 [[Z:%.*]], i8 [[SHAMT:%.*]]) {
 512 ; CHECK-NEXT:    [[SX:%.*]] = shl i8 [[X]], [[SHAMT]]
 513 ; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y]], [[SHAMT]]
 514 ; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z]]
 515 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[SY]], [[A]]
 516 ; CHECK-NEXT:    ret i8 [[R]]
 517 ;
 518   %sx = shl i8 %x, %shamt
 519   %sy = shl i8 %y, %shamt
 520   %a = or i8 %sx, %z
 521   %r = and i8 %sy, %a
 522   ret i8 %r
 523 }
 524
 525 ; Negative test - different shift ops
 526
 527 define i8 @or_lshr_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 528 ; CHECK-LABEL: define {{[^@]+}}@or_lshr_shl
 529 ; CHECK-SAME: (i8 [[X:%.*]], i8 [[Y:%.*]], i8 [[Z:%.*]], i8 [[SHAMT:%.*]]) {
 530 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X]], [[SHAMT]]
 531 ; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y]], [[SHAMT]]
 532 ; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z]]
 533 ; CHECK-NEXT:    [[R:%.*]] = or i8 [[A]], [[SY]]
 534 ; CHECK-NEXT:    ret i8 [[R]]
 535 ;
 536   %sx = lshr i8 %x, %shamt
 537   %sy = shl i8 %y, %shamt
 538   %a = or i8 %sx, %z
 539   %r = or i8 %a, %sy
 540   ret i8 %r
 541 }
 542
 543 ; Negative test - different shift amounts
 544
 545 define i8 @or_lshr_shamt2(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 546 ; CHECK-LABEL: define {{[^@]+}}@or_lshr_shamt2
 547 ; CHECK-SAME: (i8 [[X:%.*]], i8 [[Y:%.*]], i8 [[Z:%.*]], i8 [[SHAMT:%.*]]) {
 548 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X]], 5
 549 ; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y]], [[SHAMT]]
 550 ; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z]]
 551 ; CHECK-NEXT:    [[R:%.*]] = or i8 [[SY]], [[A]]
 552 ; CHECK-NEXT:    ret i8 [[R]]
 553 ;
 554   %sx = lshr i8 %x, 5
 555   %sy = lshr i8 %y, %shamt
 556   %a = or i8 %sx, %z
 557   %r = or i8 %sy, %a
 558   ret i8 %r
 559 }
 560
 561 ; Negative test - multi-use
 562
 563 define i8 @xor_lshr_multiuse(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 564 ; CHECK-LABEL: define {{[^@]+}}@xor_lshr_multiuse
 565 ; CHECK-SAME: (i8 [[X:%.*]], i8 [[Y:%.*]], i8 [[Z:%.*]], i8 [[SHAMT:%.*]]) {
 566 ; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X]], [[SHAMT]]
 567 ; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y]], [[SHAMT]]
 568 ; CHECK-NEXT:    [[A:%.*]] = xor i8 [[SX]], [[Z]]
 569 ; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], [[SY]]
 570 ; CHECK-NEXT:    [[R2:%.*]] = sdiv i8 [[A]], [[R]]
 571 ; CHECK-NEXT:    ret i8 [[R2]]
 572 ;
 573   %sx = lshr i8 %x, %shamt
 574   %sy = lshr i8 %y, %shamt
 575   %a = xor i8 %sx, %z
 576   %r = xor i8 %a, %sy
 577   %r2 = sdiv i8 %a, %r
 578   ret i8 %r2
 579 }
 580
 581 ; Reassociate chains of extend(X) | (extend(Y) | Z).
 582 ; Check that logical op is performed on a smaller type and then extended.
 583
 584 define i64 @sext_or_chain(i64 %a, i16 %b, i16 %c) {
 585 ; CHECK-LABEL: define {{[^@]+}}@sext_or_chain
 586 ; CHECK-SAME: (i64 [[A:%.*]], i16 [[B:%.*]], i16 [[C:%.*]]) {
 587 ; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[B]] to i64
 588 ; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[C]] to i64
 589 ; CHECK-NEXT:    [[OR:%.*]] = or i64 [[CONV]], [[A]]
 590 ; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[OR]], [[CONV2]]
 591 ; CHECK-NEXT:    ret i64 [[OR2]]
 592 ;
 593   %conv = sext i16 %b to i64
 594   %conv2 = sext i16 %c to i64
 595   %or = or i64 %a, %conv
 596   %or2 = or i64 %or, %conv2
 597   ret i64 %or2
 598 }
 599
 600 define i64 @zext_or_chain(i64 %a, i16 %b, i16 %c) {
 601 ; CHECK-LABEL: define {{[^@]+}}@zext_or_chain
 602 ; CHECK-SAME: (i64 [[A:%.*]], i16 [[B:%.*]], i16 [[C:%.*]]) {
 603 ; CHECK-NEXT:    [[CONV:%.*]] = zext i16 [[B]] to i64
 604 ; CHECK-NEXT:    [[CONV2:%.*]] = zext i16 [[C]] to i64
 605 ; CHECK-NEXT:    [[OR:%.*]] = or i64 [[CONV]], [[A]]
 606 ; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[OR]], [[CONV2]]
 607 ; CHECK-NEXT:    ret i64 [[OR2]]
 608 ;
 609   %conv = zext i16 %b to i64
 610   %conv2 = zext i16 %c to i64
 611   %or = or i64 %a, %conv
 612   %or2 = or i64 %or, %conv2
 613   ret i64 %or2
 614 }
 615
 616 define i64 @sext_and_chain(i64 %a, i16 %b, i16 %c) {
 617 ; CHECK-LABEL: define {{[^@]+}}@sext_and_chain
 618 ; CHECK-SAME: (i64 [[A:%.*]], i16 [[B:%.*]], i16 [[C:%.*]]) {
 619 ; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[B]] to i64
 620 ; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[C]] to i64
 621 ; CHECK-NEXT:    [[AND:%.*]] = and i64 [[CONV]], [[A]]
 622 ; CHECK-NEXT:    [[AND2:%.*]] = and i64 [[AND]], [[CONV2]]
 623 ; CHECK-NEXT:    ret i64 [[AND2]]
 624 ;
 625   %conv = sext i16 %b to i64
 626   %conv2 = sext i16 %c to i64
 627   %and = and i64 %a, %conv
 628   %and2 = and i64 %and, %conv2
 629   ret i64 %and2
 630 }
 631
 632 define i64 @zext_and_chain(i64 %a, i16 %b, i16 %c) {
 633 ; CHECK-LABEL: define {{[^@]+}}@zext_and_chain
 634 ; CHECK-SAME: (i64 [[A:%.*]], i16 [[B:%.*]], i16 [[C:%.*]]) {
 635 ; CHECK-NEXT:    [[CONV:%.*]] = zext i16 [[B]] to i64
 636 ; CHECK-NEXT:    [[CONV2:%.*]] = zext i16 [[C]] to i64
 637 ; CHECK-NEXT:    [[AND:%.*]] = and i64 [[CONV]], [[A]]
 638 ; CHECK-NEXT:    [[AND2:%.*]] = and i64 [[AND]], [[CONV2]]
 639 ; CHECK-NEXT:    ret i64 [[AND2]]
 640 ;
 641   %conv = zext i16 %b to i64
 642   %conv2 = zext i16 %c to i64
 643   %and = and i64 %a, %conv
 644   %and2 = and i64 %and, %conv2
 645   ret i64 %and2
 646 }
 647
 648 define i64 @sext_xor_chain(i64 %a, i16 %b, i16 %c) {
 649 ; CHECK-LABEL: define {{[^@]+}}@sext_xor_chain
 650 ; CHECK-SAME: (i64 [[A:%.*]], i16 [[B:%.*]], i16 [[C:%.*]]) {
 651 ; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[B]] to i64
 652 ; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[C]] to i64
 653 ; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[CONV]], [[A]]
 654 ; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[XOR]], [[CONV2]]
 655 ; CHECK-NEXT:    ret i64 [[XOR2]]
 656 ;
 657   %conv = sext i16 %b to i64
 658   %conv2 = sext i16 %c to i64
 659   %xor = xor i64 %a, %conv
 660   %xor2 = xor i64 %xor, %conv2
 661   ret i64 %xor2
 662 }
 663
 664 define i64 @zext_xor_chain(i64 %a, i16 %b, i16 %c) {
 665 ; CHECK-LABEL: define {{[^@]+}}@zext_xor_chain
 666 ; CHECK-SAME: (i64 [[A:%.*]], i16 [[B:%.*]], i16 [[C:%.*]]) {
 667 ; CHECK-NEXT:    [[CONV:%.*]] = zext i16 [[B]] to i64
 668 ; CHECK-NEXT:    [[CONV2:%.*]] = zext i16 [[C]] to i64
 669 ; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[CONV]], [[A]]
 670 ; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[XOR]], [[CONV2]]
 671 ; CHECK-NEXT:    ret i64 [[XOR2]]
 672 ;
 673   %conv = zext i16 %b to i64
 674   %conv2 = zext i16 %c to i64
 675   %xor = xor i64 %a, %conv
 676   %xor2 = xor i64 %xor, %conv2
 677   ret i64 %xor2
 678 }
 679
 680 ; Negative test with more uses.
 681 define i64 @sext_or_chain_two_uses1(i64 %a, i16 %b, i16 %c, i64 %d) {
 682 ; CHECK-LABEL: define {{[^@]+}}@sext_or_chain_two_uses1
 683 ; CHECK-SAME: (i64 [[A:%.*]], i16 [[B:%.*]], i16 [[C:%.*]], i64 [[D:%.*]]) {
 684 ; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[B]] to i64
 685 ; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[C]] to i64
 686 ; CHECK-NEXT:    [[OR:%.*]] = or i64 [[CONV]], [[A]]
 687 ; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[OR]], [[CONV2]]
 688 ; CHECK-NEXT:    [[USE:%.*]] = udiv i64 [[OR]], [[D]]
 689 ; CHECK-NEXT:    [[RETVAL:%.*]] = udiv i64 [[OR2]], [[USE]]
 690 ; CHECK-NEXT:    ret i64 [[RETVAL]]
 691 ;
 692   %conv = sext i16 %b to i64
 693   %conv2 = sext i16 %c to i64
 694   ; %or has two uses
 695   %or = or i64 %a, %conv
 696   %or2 = or i64 %or, %conv2
 697   %use = udiv i64 %or, %d
 698   %retval = udiv i64 %or2, %use
 699   ret i64 %retval
 700 }
 701 define i64 @sext_or_chain_two_uses2(i64 %a, i16 %b, i16 %c, i64 %d) {
 702 ; CHECK-LABEL: define {{[^@]+}}@sext_or_chain_two_uses2
 703 ; CHECK-SAME: (i64 [[A:%.*]], i16 [[B:%.*]], i16 [[C:%.*]], i64 [[D:%.*]]) {
 704 ; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[B]] to i64
 705 ; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[C]] to i64
 706 ; CHECK-NEXT:    [[OR:%.*]] = or i64 [[CONV]], [[A]]
 707 ; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[OR]], [[CONV2]]
 708 ; CHECK-NEXT:    [[USE1:%.*]] = udiv i64 [[OR2]], [[D]]
 709 ; CHECK-NEXT:    [[USE2:%.*]] = udiv i64 [[OR2]], [[USE1]]
 710 ; CHECK-NEXT:    ret i64 [[USE2]]
 711 ;
 712   %conv = sext i16 %b to i64
 713   %conv2 = sext i16 %c to i64
 714   %or = or i64 %a, %conv
 715   ; %or2 has two uses
 716   %or2 = or i64 %or, %conv2
 717   %use1 = udiv i64 %or2, %d
 718   %use2 = udiv i64 %or2, %use1
 719   ret i64 %use2
 720 }
 721
 722 ; (a & ~b) & ~c --> a & ~(b | c)
 723
 724 define i32 @not_and_and_not(i32 %a0, i32 %b, i32 %c) {
 725 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_not
 726 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 727 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
 728 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[B]], [[C]]
 729 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], -1
 730 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[TMP2]]
 731 ; CHECK-NEXT:    ret i32 [[AND2]]
 732 ;
 733   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
 734   %not1 = xor i32 %b, -1
 735   %not2 = xor i32 %c, -1
 736   %and1 = and i32 %a, %not1
 737   %and2 = and i32 %and1, %not2
 738   ret i32 %and2
 739 }
 740
 741 define <4 x i64> @not_and_and_not_4i64(<4 x i64> %a0, <4 x i64> %b, <4 x i64> %c) {
 742 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_not_4i64
 743 ; CHECK-SAME: (<4 x i64> [[A0:%.*]], <4 x i64> [[B:%.*]], <4 x i64> [[C:%.*]]) {
 744 ; CHECK-NEXT:    [[A:%.*]] = sdiv <4 x i64> <i64 42, i64 42, i64 42, i64 42>, [[A0]]
 745 ; CHECK-NEXT:    [[TMP1:%.*]] = or <4 x i64> [[B]], [[C]]
 746 ; CHECK-NEXT:    [[TMP2:%.*]] = xor <4 x i64> [[TMP1]], <i64 -1, i64 -1, i64 -1, i64 -1>
 747 ; CHECK-NEXT:    [[AND2:%.*]] = and <4 x i64> [[A]], [[TMP2]]
 748 ; CHECK-NEXT:    ret <4 x i64> [[AND2]]
 749 ;
 750   %a = sdiv <4 x i64> <i64 42, i64 42, i64 42, i64 42>, %a0 ; thwart complexity-based canonicalization
 751   %not1 = xor <4 x i64> %b, <i64 -1, i64 -1, i64 -1, i64 -1>
 752   %not2 = xor <4 x i64> %c, <i64 -1, i64 -1, i64 -1, i64 -1>
 753   %and1 = and <4 x i64> %a, %not1
 754   %and2 = and <4 x i64> %and1, %not2
 755   ret <4 x i64> %and2
 756 }
 757
 758 ; (~b & a) & ~c --> a & ~(b | c)
 759
 760 define i32 @not_and_and_not_commute1(i32 %a, i32 %b, i32 %c) {
 761 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_not_commute1
 762 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 763 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[B]], [[C]]
 764 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], -1
 765 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[TMP2]], [[A]]
 766 ; CHECK-NEXT:    ret i32 [[AND2]]
 767 ;
 768   %not1 = xor i32 %b, -1
 769   %not2 = xor i32 %c, -1
 770   %and1 = and i32 %not1, %a
 771   %and2 = and i32 %and1, %not2
 772   ret i32 %and2
 773 }
 774
 775 ; ~c & (a & ~b) --> a & ~(b | c)
 776
 777 define i32 @not_and_and_not_commute2_extra_not_use(i32 %a0, i32 %b, i32 %c) {
 778 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_not_commute2_extra_not_use
 779 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 780 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
 781 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[C]], -1
 782 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[B]], [[C]]
 783 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], -1
 784 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[TMP2]]
 785 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
 786 ; CHECK-NEXT:    ret i32 [[AND2]]
 787 ;
 788   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
 789   %not1 = xor i32 %b, -1
 790   %not2 = xor i32 %c, -1
 791   %and1 = and i32 %a, %not1
 792   %and2 = and i32 %not2, %and1
 793   call void @use(i32 %not2)
 794   ret i32 %and2
 795 }
 796
 797 define i32 @not_and_and_not_extra_and1_use(i32 %a0, i32 %b, i32 %c) {
 798 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_not_extra_and1_use
 799 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 800 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
 801 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[B]], -1
 802 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[C]], -1
 803 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A]], [[NOT1]]
 804 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[NOT2]]
 805 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
 806 ; CHECK-NEXT:    ret i32 [[AND2]]
 807 ;
 808   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
 809   %not1 = xor i32 %b, -1
 810   %not2 = xor i32 %c, -1
 811   %and1 = and i32 %a, %not1
 812   %and2 = and i32 %and1, %not2
 813   call void @use(i32 %and1)
 814   ret i32 %and2
 815 }
 816
 817 ; (a | ~b) | ~c --> a | ~(b & c)
 818
 819 define i32 @not_or_or_not(i32 %a0, i32 %b, i32 %c) {
 820 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_not
 821 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 822 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
 823 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[B]], [[C]]
 824 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], -1
 825 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[TMP2]]
 826 ; CHECK-NEXT:    ret i32 [[OR2]]
 827 ;
 828   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
 829   %not1 = xor i32 %b, -1
 830   %not2 = xor i32 %c, -1
 831   %or1 = or i32 %a, %not1
 832   %or2 = or i32 %or1, %not2
 833   ret i32 %or2
 834 }
 835
 836 define <2 x i6> @not_or_or_not_2i6(<2 x i6> %a0, <2 x i6> %b, <2 x i6> %c) {
 837 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_not_2i6
 838 ; CHECK-SAME: (<2 x i6> [[A0:%.*]], <2 x i6> [[B:%.*]], <2 x i6> [[C:%.*]]) {
 839 ; CHECK-NEXT:    [[A:%.*]] = sdiv <2 x i6> <i6 3, i6 3>, [[A0]]
 840 ; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i6> [[B]], [[C]]
 841 ; CHECK-NEXT:    [[TMP2:%.*]] = xor <2 x i6> [[TMP1]], <i6 -1, i6 -1>
 842 ; CHECK-NEXT:    [[OR2:%.*]] = or <2 x i6> [[A]], [[TMP2]]
 843 ; CHECK-NEXT:    ret <2 x i6> [[OR2]]
 844 ;
 845   %a = sdiv <2 x i6> <i6 3, i6 3>, %a0 ; thwart complexity-based canonicalization
 846   %not1 = xor <2 x i6> %b, <i6 -1, i6 -1>
 847   %not2 = xor <2 x i6> %c, <i6 -1, i6 undef>
 848   %or1 = or <2 x i6> %a, %not1
 849   %or2 = or <2 x i6> %or1, %not2
 850   ret <2 x i6> %or2
 851 }
 852
 853 ; (~b | a) | ~c --> a | ~(b & c)
 854
 855 define i32 @not_or_or_not_commute1(i32 %a, i32 %b, i32 %c) {
 856 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_not_commute1
 857 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 858 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[B]], [[C]]
 859 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], -1
 860 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[TMP2]], [[A]]
 861 ; CHECK-NEXT:    ret i32 [[OR2]]
 862 ;
 863   %not1 = xor i32 %b, -1
 864   %not2 = xor i32 %c, -1
 865   %or1 = or i32 %not1, %a
 866   %or2 = or i32 %or1, %not2
 867   ret i32 %or2
 868 }
 869
 870 ; ~c | (a | ~b) --> a | ~(b & c)
 871
 872 define i32 @not_or_or_not_commute2_extra_not_use(i32 %a0, i32 %b, i32 %c) {
 873 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_not_commute2_extra_not_use
 874 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 875 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
 876 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[C]], -1
 877 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[B]], [[C]]
 878 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], -1
 879 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[TMP2]]
 880 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
 881 ; CHECK-NEXT:    ret i32 [[OR2]]
 882 ;
 883   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
 884   %not1 = xor i32 %b, -1
 885   %not2 = xor i32 %c, -1
 886   %or1 = or i32 %a, %not1
 887   %or2 = or i32 %not2, %or1
 888   call void @use(i32 %not2)
 889   ret i32 %or2
 890 }
 891
 892 define i32 @not_or_or_not_extra_or1_use(i32 %a0, i32 %b, i32 %c) {
 893 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_not_extra_or1_use
 894 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 895 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
 896 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[B]], -1
 897 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[C]], -1
 898 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A]], [[NOT1]]
 899 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[NOT2]]
 900 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
 901 ; CHECK-NEXT:    ret i32 [[OR2]]
 902 ;
 903   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
 904   %not1 = xor i32 %b, -1
 905   %not2 = xor i32 %c, -1
 906   %or1 = or i32 %a, %not1
 907   %or2 = or i32 %or1, %not2
 908   call void @use(i32 %or1)
 909   ret i32 %or2
 910 }
 911
 912 ; (c & ~(a | b)) | (b & ~(a | c)) --> ~a & (b ^ c)
 913
 914 define i32 @or_not_and(i32 %a, i32 %b, i32 %c) {
 915 ; CHECK-LABEL: define {{[^@]+}}@or_not_and
 916 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 917 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
 918 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
 919 ; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
 920 ; CHECK-NEXT:    ret i32 [[OR3]]
 921 ;
 922   %or1 = or i32 %a, %b
 923   %not1 = xor i32 %or1, -1
 924   %and1 = and i32 %not1, %c
 925   %or2 = or i32 %a, %c
 926   %not2 = xor i32 %or2, -1
 927   %and2 = and i32 %not2, %b
 928   %or3 = or i32 %and1, %and2
 929   ret i32 %or3
 930 }
 931
 932 define i32 @or_not_and_commute1(i32 %a, i32 %b0, i32 %c) {
 933 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_commute1
 934 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B0:%.*]], i32 [[C:%.*]]) {
 935 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
 936 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
 937 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
 938 ; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
 939 ; CHECK-NEXT:    ret i32 [[OR3]]
 940 ;
 941   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
 942   %or1 = or i32 %a, %b
 943   %not1 = xor i32 %or1, -1
 944   %and1 = and i32 %not1, %c
 945   %or2 = or i32 %a, %c
 946   %not2 = xor i32 %or2, -1
 947   %and2 = and i32 %b, %not2
 948   %or3 = or i32 %and1, %and2
 949   ret i32 %or3
 950 }
 951
 952 define i32 @or_not_and_commute2(i32 %a, i32 %b0, i32 %c) {
 953 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_commute2
 954 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B0:%.*]], i32 [[C:%.*]]) {
 955 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
 956 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
 957 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
 958 ; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
 959 ; CHECK-NEXT:    ret i32 [[OR3]]
 960 ;
 961   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
 962   %or1 = or i32 %a, %b
 963   %not1 = xor i32 %or1, -1
 964   %and1 = and i32 %not1, %c
 965   %or2 = or i32 %a, %c
 966   %not2 = xor i32 %or2, -1
 967   %and2 = and i32 %b, %not2
 968   %or3 = or i32 %and2, %and1
 969   ret i32 %or3
 970 }
 971
 972 define i32 @or_not_and_commute3(i32 %a, i32 %b, i32 %c) {
 973 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_commute3
 974 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 975 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
 976 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
 977 ; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
 978 ; CHECK-NEXT:    ret i32 [[OR3]]
 979 ;
 980   %or1 = or i32 %b, %a
 981   %not1 = xor i32 %or1, -1
 982   %and1 = and i32 %not1, %c
 983   %or2 = or i32 %c, %a
 984   %not2 = xor i32 %or2, -1
 985   %and2 = and i32 %not2, %b
 986   %or3 = or i32 %and1, %and2
 987   ret i32 %or3
 988 }
 989
 990 define i32 @or_not_and_commute4(i32 %a, i32 %b, i32 %c0) {
 991 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_commute4
 992 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C0:%.*]]) {
 993 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0]]
 994 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
 995 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
 996 ; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
 997 ; CHECK-NEXT:    ret i32 [[OR3]]
 998 ;
 999   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
1000   %or1 = or i32 %a, %b
1001   %not1 = xor i32 %or1, -1
1002   %and1 = and i32 %c, %not1
1003   %or2 = or i32 %a, %c
1004   %not2 = xor i32 %or2, -1
1005   %and2 = and i32 %not2, %b
1006   %or3 = or i32 %and1, %and2
1007   ret i32 %or3
1008 }
1009
1010 define i32 @or_not_and_commute5(i32 %a0, i32 %b, i32 %c0) {
1011 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_commute5
1012 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B:%.*]], i32 [[C0:%.*]]) {
1013 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
1014 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0]]
1015 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
1016 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
1017 ; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
1018 ; CHECK-NEXT:    ret i32 [[OR3]]
1019 ;
1020   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
1021   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
1022   %or1 = or i32 %a, %b
1023   %not1 = xor i32 %or1, -1
1024   %and1 = and i32 %c, %not1
1025   %or2 = or i32 %a, %c
1026   %not2 = xor i32 %or2, -1
1027   %and2 = and i32 %not2, %b
1028   %or3 = or i32 %and1, %and2
1029   ret i32 %or3
1030 }
1031
1032 define i32 @or_not_and_commute6(i32 %a, i32 %b, i32 %c) {
1033 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_commute6
1034 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1035 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1036 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
1037 ; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
1038 ; CHECK-NEXT:    ret i32 [[OR3]]
1039 ;
1040   %or1 = or i32 %a, %b
1041   %not1 = xor i32 %or1, -1
1042   %and1 = and i32 %not1, %c
1043   %or2 = or i32 %c, %a
1044   %not2 = xor i32 %or2, -1
1045   %and2 = and i32 %not2, %b
1046   %or3 = or i32 %and1, %and2
1047   ret i32 %or3
1048 }
1049
1050 define i32 @or_not_and_commute7(i32 %a, i32 %b, i32 %c) {
1051 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_commute7
1052 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1053 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1054 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
1055 ; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
1056 ; CHECK-NEXT:    ret i32 [[OR3]]
1057 ;
1058   %or1 = or i32 %b, %a
1059   %not1 = xor i32 %or1, -1
1060   %and1 = and i32 %not1, %c
1061   %or2 = or i32 %a, %c
1062   %not2 = xor i32 %or2, -1
1063   %and2 = and i32 %not2, %b
1064   %or3 = or i32 %and1, %and2
1065   ret i32 %or3
1066 }
1067
1068 define i32 @or_not_and_commute8(i32 %a0, i32 %b0, i32 %c) {
1069 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_commute8
1070 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B0:%.*]], i32 [[C:%.*]]) {
1071 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
1072 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
1073 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1074 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
1075 ; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
1076 ; CHECK-NEXT:    ret i32 [[OR3]]
1077 ;
1078   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
1079   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
1080   %or1 = or i32 %a, %b
1081   %not1 = xor i32 %or1, -1
1082   %and1 = and i32 %not1, %c
1083   %or2 = or i32 %c, %a
1084   %not2 = xor i32 %or2, -1
1085   %and2 = and i32 %b, %not2
1086   %or3 = or i32 %and1, %and2
1087   ret i32 %or3
1088 }
1089
1090 define i32 @or_not_and_commute9(i32 %a0, i32 %b0, i32 %c0) {
1091 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_commute9
1092 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B0:%.*]], i32 [[C0:%.*]]) {
1093 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
1094 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
1095 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0]]
1096 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1097 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
1098 ; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
1099 ; CHECK-NEXT:    ret i32 [[OR3]]
1100 ;
1101   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
1102   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
1103   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
1104   %or1 = or i32 %a, %b
1105   %not1 = xor i32 %or1, -1
1106   %and1 = and i32 %not1, %c
1107   %or2 = or i32 %a, %c
1108   %not2 = xor i32 %or2, -1
1109   %and2 = and i32 %b, %not2
1110   %or3 = or i32 %and1, %and2
1111   ret i32 %or3
1112 }
1113
1114 define i32 @or_not_and_extra_not_use1(i32 %a, i32 %b, i32 %c) {
1115 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_extra_not_use1
1116 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1117 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A]], [[B]]
1118 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
1119 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1120 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
1121 ; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
1122 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
1123 ; CHECK-NEXT:    ret i32 [[OR3]]
1124 ;
1125   %or1 = or i32 %a, %b
1126   %not1 = xor i32 %or1, -1
1127   %and1 = and i32 %not1, %c
1128   %or2 = or i32 %a, %c
1129   %not2 = xor i32 %or2, -1
1130   %and2 = and i32 %not2, %b
1131   %or3 = or i32 %and1, %and2
1132   call void @use(i32 %not1)
1133   ret i32 %or3
1134 }
1135
1136 define i32 @or_not_and_extra_not_use2(i32 %a, i32 %b, i32 %c) {
1137 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_extra_not_use2
1138 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1139 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A]], [[B]]
1140 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
1141 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[C]]
1142 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
1143 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
1144 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[B]]
1145 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[AND2]]
1146 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
1147 ; CHECK-NEXT:    ret i32 [[OR3]]
1148 ;
1149   %or1 = or i32 %a, %b
1150   %not1 = xor i32 %or1, -1
1151   %and1 = and i32 %not1, %c
1152   %or2 = or i32 %a, %c
1153   %not2 = xor i32 %or2, -1
1154   %and2 = and i32 %not2, %b
1155   %or3 = or i32 %and1, %and2
1156   call void @use(i32 %not2)
1157   ret i32 %or3
1158 }
1159
1160 define i32 @or_not_and_extra_and_use1(i32 %a, i32 %b, i32 %c) {
1161 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_extra_and_use1
1162 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1163 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A]], [[B]]
1164 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
1165 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[C]]
1166 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1167 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
1168 ; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
1169 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
1170 ; CHECK-NEXT:    ret i32 [[OR3]]
1171 ;
1172   %or1 = or i32 %a, %b
1173   %not1 = xor i32 %or1, -1
1174   %and1 = and i32 %not1, %c
1175   %or2 = or i32 %a, %c
1176   %not2 = xor i32 %or2, -1
1177   %and2 = and i32 %not2, %b
1178   %or3 = or i32 %and1, %and2
1179   call void @use(i32 %and1)
1180   ret i32 %or3
1181 }
1182
1183 define i32 @or_not_and_extra_and_use2(i32 %a, i32 %b, i32 %c) {
1184 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_extra_and_use2
1185 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1186 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A]], [[B]]
1187 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
1188 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[C]]
1189 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
1190 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
1191 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[B]]
1192 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[AND2]]
1193 ; CHECK-NEXT:    call void @use(i32 [[AND2]])
1194 ; CHECK-NEXT:    ret i32 [[OR3]]
1195 ;
1196   %or1 = or i32 %a, %b
1197   %not1 = xor i32 %or1, -1
1198   %and1 = and i32 %not1, %c
1199   %or2 = or i32 %a, %c
1200   %not2 = xor i32 %or2, -1
1201   %and2 = and i32 %not2, %b
1202   %or3 = or i32 %and1, %and2
1203   call void @use(i32 %and2)
1204   ret i32 %or3
1205 }
1206
1207 define i32 @or_not_and_extra_or_use1(i32 %a, i32 %b, i32 %c) {
1208 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_extra_or_use1
1209 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1210 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A]], [[B]]
1211 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1212 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
1213 ; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
1214 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
1215 ; CHECK-NEXT:    ret i32 [[OR3]]
1216 ;
1217   %or1 = or i32 %a, %b
1218   %not1 = xor i32 %or1, -1
1219   %and1 = and i32 %not1, %c
1220   %or2 = or i32 %a, %c
1221   %not2 = xor i32 %or2, -1
1222   %and2 = and i32 %not2, %b
1223   %or3 = or i32 %and1, %and2
1224   call void @use(i32 %or1)
1225   ret i32 %or3
1226 }
1227
1228 define i32 @or_not_and_extra_or_use2(i32 %a, i32 %b, i32 %c) {
1229 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_extra_or_use2
1230 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1231 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
1232 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1233 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
1234 ; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
1235 ; CHECK-NEXT:    call void @use(i32 [[OR2]])
1236 ; CHECK-NEXT:    ret i32 [[OR3]]
1237 ;
1238   %or1 = or i32 %a, %b
1239   %not1 = xor i32 %or1, -1
1240   %and1 = and i32 %not1, %c
1241   %or2 = or i32 %a, %c
1242   %not2 = xor i32 %or2, -1
1243   %and2 = and i32 %not2, %b
1244   %or3 = or i32 %and1, %and2
1245   call void @use(i32 %or2)
1246   ret i32 %or3
1247 }
1248
1249 define i32 @or_not_and_wrong_c(i32 %a, i32 %b, i32 %c, i32 %d) {
1250 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_wrong_c
1251 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32 [[D:%.*]]) {
1252 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A]], [[B]]
1253 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
1254 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[C]]
1255 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[D]]
1256 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
1257 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[B]]
1258 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[AND2]]
1259 ; CHECK-NEXT:    ret i32 [[OR3]]
1260 ;
1261   %or1 = or i32 %a, %b
1262   %not1 = xor i32 %or1, -1
1263   %and1 = and i32 %not1, %c
1264   %or2 = or i32 %a, %d
1265   %not2 = xor i32 %or2, -1
1266   %and2 = and i32 %not2, %b
1267   %or3 = or i32 %and1, %and2
1268   ret i32 %or3
1269 }
1270
1271 define i32 @or_not_and_wrong_b(i32 %a, i32 %b, i32 %c, i32 %d) {
1272 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_wrong_b
1273 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32 [[D:%.*]]) {
1274 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A]], [[B]]
1275 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
1276 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[C]]
1277 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
1278 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
1279 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[D]]
1280 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[AND2]]
1281 ; CHECK-NEXT:    ret i32 [[OR3]]
1282 ;
1283   %or1 = or i32 %a, %b
1284   %not1 = xor i32 %or1, -1
1285   %and1 = and i32 %not1, %c
1286   %or2 = or i32 %a, %c
1287   %not2 = xor i32 %or2, -1
1288   %and2 = and i32 %not2, %d
1289   %or3 = or i32 %and1, %and2
1290   ret i32 %or3
1291 }
1292
1293 ; (c | ~(a & b)) & (b | ~(a & c)) --> ~(a & (b ^ c))
1294
1295 define i32 @and_not_or(i32 %a, i32 %b, i32 %c) {
1296 ; CHECK-LABEL: define {{[^@]+}}@and_not_or
1297 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1298 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1299 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
1300 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
1301 ; CHECK-NEXT:    ret i32 [[AND3]]
1302 ;
1303   %and1 = and i32 %a, %b
1304   %not1 = xor i32 %and1, -1
1305   %or1 = or i32 %not1, %c
1306   %and2 = and i32 %a, %c
1307   %not2 = xor i32 %and2, -1
1308   %or2 = or i32 %not2, %b
1309   %and3 = and i32 %or1, %or2
1310   ret i32 %and3
1311 }
1312
1313 define i32 @and_not_or_commute1(i32 %a, i32 %b0, i32 %c) {
1314 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_commute1
1315 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B0:%.*]], i32 [[C:%.*]]) {
1316 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
1317 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1318 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
1319 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
1320 ; CHECK-NEXT:    ret i32 [[AND3]]
1321 ;
1322   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
1323   %and1 = and i32 %a, %b
1324   %not1 = xor i32 %and1, -1
1325   %or1 = or i32 %not1, %c
1326   %and2 = and i32 %a, %c
1327   %not2 = xor i32 %and2, -1
1328   %or2 = or i32 %b, %not2
1329   %and3 = and i32 %or1, %or2
1330   ret i32 %and3
1331 }
1332
1333 define i32 @and_not_or_commute2(i32 %a, i32 %b0, i32 %c) {
1334 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_commute2
1335 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B0:%.*]], i32 [[C:%.*]]) {
1336 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
1337 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1338 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
1339 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
1340 ; CHECK-NEXT:    ret i32 [[AND3]]
1341 ;
1342   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
1343   %and1 = and i32 %a, %b
1344   %not1 = xor i32 %and1, -1
1345   %or1 = or i32 %not1, %c
1346   %and2 = and i32 %a, %c
1347   %not2 = xor i32 %and2, -1
1348   %or2 = or i32 %b, %not2
1349   %and3 = and i32 %or2, %or1
1350   ret i32 %and3
1351 }
1352
1353 define i32 @and_not_or_commute3(i32 %a, i32 %b, i32 %c) {
1354 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_commute3
1355 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1356 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1357 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
1358 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
1359 ; CHECK-NEXT:    ret i32 [[AND3]]
1360 ;
1361   %and1 = and i32 %b, %a
1362   %not1 = xor i32 %and1, -1
1363   %or1 = or i32 %not1, %c
1364   %and2 = and i32 %c, %a
1365   %not2 = xor i32 %and2, -1
1366   %or2 = or i32 %not2, %b
1367   %and3 = and i32 %or1, %or2
1368   ret i32 %and3
1369 }
1370
1371 define i32 @and_not_or_commute4(i32 %a, i32 %b, i32 %c0) {
1372 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_commute4
1373 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C0:%.*]]) {
1374 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0]]
1375 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
1376 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
1377 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
1378 ; CHECK-NEXT:    ret i32 [[AND3]]
1379 ;
1380   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
1381   %and1 = and i32 %a, %b
1382   %not1 = xor i32 %and1, -1
1383   %or1 = or i32 %c, %not1
1384   %and2 = and i32 %a, %c
1385   %not2 = xor i32 %and2, -1
1386   %or2 = or i32 %not2, %b
1387   %and3 = and i32 %or1, %or2
1388   ret i32 %and3
1389 }
1390
1391 define i32 @and_not_or_commute5(i32 %a0, i32 %b, i32 %c0) {
1392 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_commute5
1393 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B:%.*]], i32 [[C0:%.*]]) {
1394 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
1395 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0]]
1396 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
1397 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
1398 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
1399 ; CHECK-NEXT:    ret i32 [[AND3]]
1400 ;
1401   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
1402   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
1403   %and1 = and i32 %a, %b
1404   %not1 = xor i32 %and1, -1
1405   %or1 = or i32 %c, %not1
1406   %and2 = and i32 %a, %c
1407   %not2 = xor i32 %and2, -1
1408   %or2 = or i32 %not2, %b
1409   %and3 = and i32 %or1, %or2
1410   ret i32 %and3
1411 }
1412
1413 define i32 @and_not_or_commute6(i32 %a, i32 %b, i32 %c) {
1414 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_commute6
1415 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1416 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1417 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
1418 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
1419 ; CHECK-NEXT:    ret i32 [[AND3]]
1420 ;
1421   %and1 = and i32 %a, %b
1422   %not1 = xor i32 %and1, -1
1423   %or1 = or i32 %not1, %c
1424   %and2 = and i32 %c, %a
1425   %not2 = xor i32 %and2, -1
1426   %or2 = or i32 %not2, %b
1427   %and3 = and i32 %or1, %or2
1428   ret i32 %and3
1429 }
1430
1431 define i32 @and_not_or_commute7(i32 %a, i32 %b, i32 %c) {
1432 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_commute7
1433 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1434 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1435 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
1436 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
1437 ; CHECK-NEXT:    ret i32 [[AND3]]
1438 ;
1439   %and1 = and i32 %b, %a
1440   %not1 = xor i32 %and1, -1
1441   %or1 = or i32 %not1, %c
1442   %and2 = and i32 %a, %c
1443   %not2 = xor i32 %and2, -1
1444   %or2 = or i32 %not2, %b
1445   %and3 = and i32 %or1, %or2
1446   ret i32 %and3
1447 }
1448
1449 define i32 @and_not_or_commute8(i32 %a0, i32 %b0, i32 %c) {
1450 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_commute8
1451 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B0:%.*]], i32 [[C:%.*]]) {
1452 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
1453 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
1454 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1455 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
1456 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
1457 ; CHECK-NEXT:    ret i32 [[AND3]]
1458 ;
1459   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
1460   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
1461   %and1 = and i32 %a, %b
1462   %not1 = xor i32 %and1, -1
1463   %or1 = or i32 %not1, %c
1464   %and2 = and i32 %c, %a
1465   %not2 = xor i32 %and2, -1
1466   %or2 = or i32 %b, %not2
1467   %and3 = and i32 %or1, %or2
1468   ret i32 %and3
1469 }
1470
1471 define i32 @and_not_or_commute9(i32 %a0, i32 %b0, i32 %c0) {
1472 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_commute9
1473 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B0:%.*]], i32 [[C0:%.*]]) {
1474 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
1475 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
1476 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0]]
1477 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1478 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
1479 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
1480 ; CHECK-NEXT:    ret i32 [[AND3]]
1481 ;
1482   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
1483   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
1484   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
1485   %and1 = and i32 %a, %b
1486   %not1 = xor i32 %and1, -1
1487   %or1 = or i32 %not1, %c
1488   %and2 = and i32 %a, %c
1489   %not2 = xor i32 %and2, -1
1490   %or2 = or i32 %b, %not2
1491   %and3 = and i32 %or1, %or2
1492   ret i32 %and3
1493 }
1494
1495 define i32 @and_not_or_extra_not_use1(i32 %a, i32 %b, i32 %c) {
1496 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_extra_not_use1
1497 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1498 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A]], [[B]]
1499 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
1500 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1501 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
1502 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
1503 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
1504 ; CHECK-NEXT:    ret i32 [[AND3]]
1505 ;
1506   %and1 = and i32 %a, %b
1507   %not1 = xor i32 %and1, -1
1508   %or1 = or i32 %not1, %c
1509   %and2 = and i32 %a, %c
1510   %not2 = xor i32 %and2, -1
1511   %or2 = or i32 %not2, %b
1512   %and3 = and i32 %or1, %or2
1513   call void @use(i32 %not1)
1514   ret i32 %and3
1515 }
1516
1517 define i32 @and_not_or_extra_not_use2(i32 %a, i32 %b, i32 %c) {
1518 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_extra_not_use2
1519 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1520 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A]], [[B]]
1521 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
1522 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[C]]
1523 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C]]
1524 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
1525 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[B]]
1526 ; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR1]], [[OR2]]
1527 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
1528 ; CHECK-NEXT:    ret i32 [[AND3]]
1529 ;
1530   %and1 = and i32 %a, %b
1531   %not1 = xor i32 %and1, -1
1532   %or1 = or i32 %not1, %c
1533   %and2 = and i32 %a, %c
1534   %not2 = xor i32 %and2, -1
1535   %or2 = or i32 %not2, %b
1536   %and3 = and i32 %or1, %or2
1537   call void @use(i32 %not2)
1538   ret i32 %and3
1539 }
1540
1541 define i32 @and_not_or_extra_and_use1(i32 %a, i32 %b, i32 %c) {
1542 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_extra_and_use1
1543 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1544 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A]], [[B]]
1545 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
1546 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[C]]
1547 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1548 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
1549 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
1550 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
1551 ; CHECK-NEXT:    ret i32 [[AND3]]
1552 ;
1553   %and1 = and i32 %a, %b
1554   %not1 = xor i32 %and1, -1
1555   %or1 = or i32 %not1, %c
1556   %and2 = and i32 %a, %c
1557   %not2 = xor i32 %and2, -1
1558   %or2 = or i32 %not2, %b
1559   %and3 = and i32 %or1, %or2
1560   call void @use(i32 %or1)
1561   ret i32 %and3
1562 }
1563
1564 define i32 @and_not_or_extra_and_use2(i32 %a, i32 %b, i32 %c) {
1565 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_extra_and_use2
1566 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1567 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A]], [[B]]
1568 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
1569 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[C]]
1570 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C]]
1571 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
1572 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[B]]
1573 ; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR1]], [[OR2]]
1574 ; CHECK-NEXT:    call void @use(i32 [[OR2]])
1575 ; CHECK-NEXT:    ret i32 [[AND3]]
1576 ;
1577   %and1 = and i32 %a, %b
1578   %not1 = xor i32 %and1, -1
1579   %or1 = or i32 %not1, %c
1580   %and2 = and i32 %a, %c
1581   %not2 = xor i32 %and2, -1
1582   %or2 = or i32 %not2, %b
1583   %and3 = and i32 %or1, %or2
1584   call void @use(i32 %or2)
1585   ret i32 %and3
1586 }
1587
1588 define i32 @and_not_or_extra_or_use1(i32 %a, i32 %b, i32 %c) {
1589 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_extra_or_use1
1590 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1591 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A]], [[B]]
1592 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1593 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
1594 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
1595 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
1596 ; CHECK-NEXT:    ret i32 [[AND3]]
1597 ;
1598   %and1 = and i32 %a, %b
1599   %not1 = xor i32 %and1, -1
1600   %or1 = or i32 %not1, %c
1601   %and2 = and i32 %a, %c
1602   %not2 = xor i32 %and2, -1
1603   %or2 = or i32 %not2, %b
1604   %and3 = and i32 %or1, %or2
1605   call void @use(i32 %and1)
1606   ret i32 %and3
1607 }
1608
1609 define i32 @and_not_or_extra_or_use2(i32 %a, i32 %b, i32 %c) {
1610 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_extra_or_use2
1611 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1612 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C]]
1613 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
1614 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
1615 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
1616 ; CHECK-NEXT:    call void @use(i32 [[AND2]])
1617 ; CHECK-NEXT:    ret i32 [[AND3]]
1618 ;
1619   %and1 = and i32 %a, %b
1620   %not1 = xor i32 %and1, -1
1621   %or1 = or i32 %not1, %c
1622   %and2 = and i32 %a, %c
1623   %not2 = xor i32 %and2, -1
1624   %or2 = or i32 %not2, %b
1625   %and3 = and i32 %or1, %or2
1626   call void @use(i32 %and2)
1627   ret i32 %and3
1628 }
1629
1630 define i32 @and_not_or_wrong_c(i32 %a, i32 %b, i32 %c, i32 %d) {
1631 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_wrong_c
1632 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32 [[D:%.*]]) {
1633 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A]], [[B]]
1634 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
1635 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[C]]
1636 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[D]]
1637 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
1638 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[B]]
1639 ; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR1]], [[OR2]]
1640 ; CHECK-NEXT:    ret i32 [[AND3]]
1641 ;
1642   %and1 = and i32 %a, %b
1643   %not1 = xor i32 %and1, -1
1644   %or1 = or i32 %not1, %c
1645   %and2 = and i32 %a, %d
1646   %not2 = xor i32 %and2, -1
1647   %or2 = or i32 %not2, %b
1648   %and3 = and i32 %or1, %or2
1649   ret i32 %and3
1650 }
1651
1652 define i32 @and_not_or_wrong_b(i32 %a, i32 %b, i32 %c, i32 %d) {
1653 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_wrong_b
1654 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32 [[D:%.*]]) {
1655 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A]], [[B]]
1656 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
1657 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[C]]
1658 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C]]
1659 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
1660 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[D]]
1661 ; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR1]], [[OR2]]
1662 ; CHECK-NEXT:    ret i32 [[AND3]]
1663 ;
1664   %and1 = and i32 %a, %b
1665   %not1 = xor i32 %and1, -1
1666   %or1 = or i32 %not1, %c
1667   %and2 = and i32 %a, %c
1668   %not2 = xor i32 %and2, -1
1669   %or2 = or i32 %not2, %d
1670   %and3 = and i32 %or1, %or2
1671   ret i32 %and3
1672 }
1673
1674 ; (b & ~(a | c)) | ~(a | b) --> ~((b & c) | a)
1675
1676 define i32 @or_and_not_not(i32 %a, i32 %b, i32 %c) {
1677 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not
1678 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1679 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C]], [[B]]
1680 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
1681 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
1682 ; CHECK-NEXT:    ret i32 [[OR3]]
1683 ;
1684   %or1 = or i32 %b, %a
1685   %not1 = xor i32 %or1, -1
1686   %or2 = or i32 %a, %c
1687   %not2 = xor i32 %or2, -1
1688   %and = and i32 %not2, %b
1689   %or3 = or i32 %and, %not1
1690   ret i32 %or3
1691 }
1692
1693 define i32 @or_and_not_not_commute1(i32 %a, i32 %b0, i32 %c) {
1694 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not_commute1
1695 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B0:%.*]], i32 [[C:%.*]]) {
1696 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
1697 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[B]], [[C]]
1698 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
1699 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
1700 ; CHECK-NEXT:    ret i32 [[OR3]]
1701 ;
1702   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
1703   %or1 = or i32 %b, %a
1704   %not1 = xor i32 %or1, -1
1705   %or2 = or i32 %a, %c
1706   %not2 = xor i32 %or2, -1
1707   %and = and i32 %b, %not2
1708   %or3 = or i32 %and, %not1
1709   ret i32 %or3
1710 }
1711
1712 define i32 @or_and_not_not_commute2(i32 %a, i32 %b, i32 %c) {
1713 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not_commute2
1714 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1715 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C]], [[B]]
1716 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
1717 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
1718 ; CHECK-NEXT:    ret i32 [[OR3]]
1719 ;
1720   %or1 = or i32 %b, %a
1721   %not1 = xor i32 %or1, -1
1722   %or2 = or i32 %a, %c
1723   %not2 = xor i32 %or2, -1
1724   %and = and i32 %not2, %b
1725   %or3 = or i32 %and, %not1
1726   ret i32 %or3
1727 }
1728
1729 define i32 @or_and_not_not_commute3(i32 %a, i32 %b, i32 %c) {
1730 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not_commute3
1731 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1732 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C]], [[B]]
1733 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
1734 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
1735 ; CHECK-NEXT:    ret i32 [[OR3]]
1736 ;
1737   %or1 = or i32 %b, %a
1738   %not1 = xor i32 %or1, -1
1739   %or2 = or i32 %c, %a
1740   %not2 = xor i32 %or2, -1
1741   %and = and i32 %not2, %b
1742   %or3 = or i32 %and, %not1
1743   ret i32 %or3
1744 }
1745
1746 define i32 @or_and_not_not_commute4(i32 %a, i32 %b, i32 %c) {
1747 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not_commute4
1748 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1749 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C]], [[B]]
1750 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
1751 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
1752 ; CHECK-NEXT:    ret i32 [[OR3]]
1753 ;
1754   %or1 = or i32 %a, %b
1755   %not1 = xor i32 %or1, -1
1756   %or2 = or i32 %a, %c
1757   %not2 = xor i32 %or2, -1
1758   %and = and i32 %not2, %b
1759   %or3 = or i32 %and, %not1
1760   ret i32 %or3
1761 }
1762
1763 define i32 @or_and_not_not_commute5(i32 %a, i32 %b, i32 %c) {
1764 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not_commute5
1765 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1766 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C]], [[B]]
1767 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
1768 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
1769 ; CHECK-NEXT:    ret i32 [[OR3]]
1770 ;
1771   %or1 = or i32 %b, %a
1772   %not1 = xor i32 %or1, -1
1773   %or2 = or i32 %a, %c
1774   %not2 = xor i32 %or2, -1
1775   %and = and i32 %not2, %b
1776   %or3 = or i32 %not1, %and
1777   ret i32 %or3
1778 }
1779
1780 define i32 @or_and_not_not_commute6(i32 %a, i32 %b0, i32 %c) {
1781 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not_commute6
1782 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B0:%.*]], i32 [[C:%.*]]) {
1783 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
1784 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[B]], [[C]]
1785 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
1786 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
1787 ; CHECK-NEXT:    ret i32 [[OR3]]
1788 ;
1789   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
1790   %or1 = or i32 %b, %a
1791   %not1 = xor i32 %or1, -1
1792   %or2 = or i32 %c, %a
1793   %not2 = xor i32 %or2, -1
1794   %and = and i32 %b, %not2
1795   %or3 = or i32 %and, %not1
1796   ret i32 %or3
1797 }
1798
1799 define i32 @or_and_not_not_commute7(i32 %a, i32 %b, i32 %c) {
1800 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not_commute7
1801 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1802 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C]], [[B]]
1803 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
1804 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
1805 ; CHECK-NEXT:    ret i32 [[OR3]]
1806 ;
1807   %or1 = or i32 %a, %b
1808   %not1 = xor i32 %or1, -1
1809   %or2 = or i32 %c, %a
1810   %not2 = xor i32 %or2, -1
1811   %and = and i32 %not2, %b
1812   %or3 = or i32 %and, %not1
1813   ret i32 %or3
1814 }
1815
1816 define i32 @or_and_not_not_extra_not_use1(i32 %a, i32 %b, i32 %c) {
1817 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not_extra_not_use1
1818 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1819 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[A]]
1820 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
1821 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
1822 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
1823 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[NOT2]], [[B]]
1824 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND]], [[NOT1]]
1825 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
1826 ; CHECK-NEXT:    ret i32 [[OR3]]
1827 ;
1828   %or1 = or i32 %b, %a
1829   %not1 = xor i32 %or1, -1
1830   %or2 = or i32 %a, %c
1831   %not2 = xor i32 %or2, -1
1832   %and = and i32 %not2, %b
1833   %or3 = or i32 %and, %not1
1834   call void @use(i32 %not1)
1835   ret i32 %or3
1836 }
1837
1838 define i32 @or_and_not_not_extra_not_use2(i32 %a, i32 %b, i32 %c) {
1839 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not_extra_not_use2
1840 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1841 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
1842 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
1843 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C]], [[B]]
1844 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
1845 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
1846 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
1847 ; CHECK-NEXT:    ret i32 [[OR3]]
1848 ;
1849   %or1 = or i32 %b, %a
1850   %not1 = xor i32 %or1, -1
1851   %or2 = or i32 %a, %c
1852   %not2 = xor i32 %or2, -1
1853   %and = and i32 %not2, %b
1854   %or3 = or i32 %and, %not1
1855   call void @use(i32 %not2)
1856   ret i32 %or3
1857 }
1858
1859 define i32 @or_and_not_not_extra_and_use(i32 %a, i32 %b, i32 %c) {
1860 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not_extra_and_use
1861 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1862 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
1863 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
1864 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[NOT2]], [[B]]
1865 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C]], [[B]]
1866 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
1867 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
1868 ; CHECK-NEXT:    call void @use(i32 [[AND]])
1869 ; CHECK-NEXT:    ret i32 [[OR3]]
1870 ;
1871   %or1 = or i32 %b, %a
1872   %not1 = xor i32 %or1, -1
1873   %or2 = or i32 %a, %c
1874   %not2 = xor i32 %or2, -1
1875   %and = and i32 %not2, %b
1876   %or3 = or i32 %and, %not1
1877   call void @use(i32 %and)
1878   ret i32 %or3
1879 }
1880
1881 define i32 @or_and_not_not_extra_or_use1(i32 %a, i32 %b, i32 %c) {
1882 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not_extra_or_use1
1883 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1884 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[A]]
1885 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
1886 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
1887 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
1888 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[NOT2]], [[B]]
1889 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND]], [[NOT1]]
1890 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
1891 ; CHECK-NEXT:    ret i32 [[OR3]]
1892 ;
1893   %or1 = or i32 %b, %a
1894   %not1 = xor i32 %or1, -1
1895   %or2 = or i32 %a, %c
1896   %not2 = xor i32 %or2, -1
1897   %and = and i32 %not2, %b
1898   %or3 = or i32 %and, %not1
1899   call void @use(i32 %or1)
1900   ret i32 %or3
1901 }
1902
1903 define i32 @or_and_not_not_extra_or_use2(i32 %a, i32 %b, i32 %c) {
1904 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not_extra_or_use2
1905 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1906 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
1907 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C]], [[B]]
1908 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
1909 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
1910 ; CHECK-NEXT:    call void @use(i32 [[OR2]])
1911 ; CHECK-NEXT:    ret i32 [[OR3]]
1912 ;
1913   %or1 = or i32 %b, %a
1914   %not1 = xor i32 %or1, -1
1915   %or2 = or i32 %a, %c
1916   %not2 = xor i32 %or2, -1
1917   %and = and i32 %not2, %b
1918   %or3 = or i32 %and, %not1
1919   call void @use(i32 %or2)
1920   ret i32 %or3
1921 }
1922
1923 ; Check the use limit. It can be adjusted in the future in terms of
1924 ; LHS and RHS uses distribution to be more flexible.
1925 define i32 @or_and_not_not_2_extra_uses(i32 %a, i32 %b, i32 %c) {
1926 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not_2_extra_uses
1927 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1928 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[A]]
1929 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
1930 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
1931 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
1932 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
1933 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[NOT2]], [[B]]
1934 ; CHECK-NEXT:    call void @use(i32 [[AND]])
1935 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND]], [[NOT1]]
1936 ; CHECK-NEXT:    ret i32 [[OR3]]
1937 ;
1938   %or1 = or i32 %b, %a
1939   call void @use(i32 %or1)
1940   %not1 = xor i32 %or1, -1
1941   %or2 = or i32 %a, %c
1942   %not2 = xor i32 %or2, -1
1943   %and = and i32 %not2, %b
1944   call void @use(i32 %and)
1945   %or3 = or i32 %not1, %and
1946   ret i32 %or3
1947 }
1948
1949 define i32 @or_and_not_not_wrong_a(i32 %a, i32 %b, i32 %c, i32 %d) {
1950 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not_wrong_a
1951 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32 [[D:%.*]]) {
1952 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[D]]
1953 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
1954 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
1955 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
1956 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[NOT2]], [[B]]
1957 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND]], [[NOT1]]
1958 ; CHECK-NEXT:    ret i32 [[OR3]]
1959 ;
1960   %or1 = or i32 %b, %d
1961   %not1 = xor i32 %or1, -1
1962   %or2 = or i32 %a, %c
1963   %not2 = xor i32 %or2, -1
1964   %and = and i32 %not2, %b
1965   %or3 = or i32 %and, %not1
1966   ret i32 %or3
1967 }
1968
1969 define i32 @or_and_not_not_wrong_b(i32 %a, i32 %b, i32 %c, i32 %d) {
1970 ; CHECK-LABEL: define {{[^@]+}}@or_and_not_not_wrong_b
1971 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32 [[D:%.*]]) {
1972 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[D]], [[A]]
1973 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
1974 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
1975 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
1976 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[NOT2]], [[B]]
1977 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND]], [[NOT1]]
1978 ; CHECK-NEXT:    ret i32 [[OR3]]
1979 ;
1980   %or1 = or i32 %d, %a
1981   %not1 = xor i32 %or1, -1
1982   %or2 = or i32 %a, %c
1983   %not2 = xor i32 %or2, -1
1984   %and = and i32 %not2, %b
1985   %or3 = or i32 %and, %not1
1986   ret i32 %or3
1987 }
1988
1989 ; (b | ~(a & c)) & ~(a & b) --> ~((b | c) & a)
1990
1991 define i32 @and_or_not_not(i32 %a, i32 %b, i32 %c) {
1992 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not
1993 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
1994 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C]], [[B]]
1995 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
1996 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
1997 ; CHECK-NEXT:    ret i32 [[AND3]]
1998 ;
1999   %and1 = and i32 %b, %a
2000   %not1 = xor i32 %and1, -1
2001   %and2 = and i32 %a, %c
2002   %not2 = xor i32 %and2, -1
2003   %or = or i32 %not2, %b
2004   %and3 = and i32 %or, %not1
2005   ret i32 %and3
2006 }
2007
2008 define i32 @and_or_not_not_commute1(i32 %a, i32 %b0, i32 %c) {
2009 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not_commute1
2010 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B0:%.*]], i32 [[C:%.*]]) {
2011 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
2012 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[B]], [[C]]
2013 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
2014 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
2015 ; CHECK-NEXT:    ret i32 [[AND3]]
2016 ;
2017   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
2018   %and1 = and i32 %b, %a
2019   %not1 = xor i32 %and1, -1
2020   %and2 = and i32 %a, %c
2021   %not2 = xor i32 %and2, -1
2022   %or = or i32 %b, %not2
2023   %and3 = and i32 %or, %not1
2024   ret i32 %and3
2025 }
2026
2027 define i32 @and_or_not_not_commute2(i32 %a, i32 %b, i32 %c) {
2028 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not_commute2
2029 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2030 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C]], [[B]]
2031 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
2032 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
2033 ; CHECK-NEXT:    ret i32 [[AND3]]
2034 ;
2035   %and1 = and i32 %b, %a
2036   %not1 = xor i32 %and1, -1
2037   %and2 = and i32 %a, %c
2038   %not2 = xor i32 %and2, -1
2039   %or = or i32 %not2, %b
2040   %and3 = and i32 %or, %not1
2041   ret i32 %and3
2042 }
2043
2044 define i32 @and_or_not_not_commute3(i32 %a, i32 %b, i32 %c) {
2045 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not_commute3
2046 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2047 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C]], [[B]]
2048 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
2049 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
2050 ; CHECK-NEXT:    ret i32 [[AND3]]
2051 ;
2052   %and1 = and i32 %b, %a
2053   %not1 = xor i32 %and1, -1
2054   %and2 = and i32 %c, %a
2055   %not2 = xor i32 %and2, -1
2056   %or = or i32 %not2, %b
2057   %and3 = and i32 %or, %not1
2058   ret i32 %and3
2059 }
2060
2061 define i32 @and_or_not_not_commute4(i32 %a, i32 %b, i32 %c) {
2062 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not_commute4
2063 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2064 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C]], [[B]]
2065 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
2066 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
2067 ; CHECK-NEXT:    ret i32 [[AND3]]
2068 ;
2069   %and1 = and i32 %a, %b
2070   %not1 = xor i32 %and1, -1
2071   %and2 = and i32 %a, %c
2072   %not2 = xor i32 %and2, -1
2073   %or = or i32 %not2, %b
2074   %and3 = and i32 %or, %not1
2075   ret i32 %and3
2076 }
2077
2078 define i32 @and_or_not_not_commute5(i32 %a, i32 %b, i32 %c) {
2079 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not_commute5
2080 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2081 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C]], [[B]]
2082 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
2083 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
2084 ; CHECK-NEXT:    ret i32 [[AND3]]
2085 ;
2086   %and1 = and i32 %b, %a
2087   %not1 = xor i32 %and1, -1
2088   %and2 = and i32 %a, %c
2089   %not2 = xor i32 %and2, -1
2090   %or = or i32 %not2, %b
2091   %and3 = and i32 %not1, %or
2092   ret i32 %and3
2093 }
2094
2095 define i32 @and_or_not_not_commute6(i32 %a, i32 %b0, i32 %c) {
2096 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not_commute6
2097 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B0:%.*]], i32 [[C:%.*]]) {
2098 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
2099 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[B]], [[C]]
2100 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
2101 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
2102 ; CHECK-NEXT:    ret i32 [[AND3]]
2103 ;
2104   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
2105   %and1 = and i32 %b, %a
2106   %not1 = xor i32 %and1, -1
2107   %and2 = and i32 %c, %a
2108   %not2 = xor i32 %and2, -1
2109   %or = or i32 %b, %not2
2110   %and3 = and i32 %or, %not1
2111   ret i32 %and3
2112 }
2113
2114 define i32 @and_or_not_not_commute7(i32 %a, i32 %b, i32 %c) {
2115 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not_commute7
2116 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2117 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C]], [[B]]
2118 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
2119 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
2120 ; CHECK-NEXT:    ret i32 [[AND3]]
2121 ;
2122   %and1 = and i32 %a, %b
2123   %not1 = xor i32 %and1, -1
2124   %and2 = and i32 %c, %a
2125   %not2 = xor i32 %and2, -1
2126   %or = or i32 %not2, %b
2127   %and3 = and i32 %or, %not1
2128   ret i32 %and3
2129 }
2130
2131 define i32 @and_or_not_not_extra_not_use1(i32 %a, i32 %b, i32 %c) {
2132 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not_extra_not_use1
2133 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2134 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[A]]
2135 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
2136 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C]]
2137 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
2138 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[NOT2]], [[B]]
2139 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND1]], [[OR]]
2140 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
2141 ; CHECK-NEXT:    ret i32 [[AND3]]
2142 ;
2143   %and1 = and i32 %b, %a
2144   %not1 = xor i32 %and1, -1
2145   %and2 = and i32 %a, %c
2146   %not2 = xor i32 %and2, -1
2147   %or = or i32 %not2, %b
2148   %and3 = and i32 %or, %not1
2149   call void @use(i32 %not1)
2150   ret i32 %and3
2151 }
2152
2153 define i32 @and_or_not_not_extra_not_use2(i32 %a, i32 %b, i32 %c) {
2154 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not_extra_not_use2
2155 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2156 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C]]
2157 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
2158 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C]], [[B]]
2159 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
2160 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
2161 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
2162 ; CHECK-NEXT:    ret i32 [[AND3]]
2163 ;
2164   %and1 = and i32 %b, %a
2165   %not1 = xor i32 %and1, -1
2166   %and2 = and i32 %a, %c
2167   %not2 = xor i32 %and2, -1
2168   %or = or i32 %not2, %b
2169   %and3 = and i32 %or, %not1
2170   call void @use(i32 %not2)
2171   ret i32 %and3
2172 }
2173
2174 define i32 @and_or_not_not_extra_and_use(i32 %a, i32 %b, i32 %c) {
2175 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not_extra_and_use
2176 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2177 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C]]
2178 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
2179 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[NOT2]], [[B]]
2180 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C]], [[B]]
2181 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
2182 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
2183 ; CHECK-NEXT:    call void @use(i32 [[OR]])
2184 ; CHECK-NEXT:    ret i32 [[AND3]]
2185 ;
2186   %and1 = and i32 %b, %a
2187   %not1 = xor i32 %and1, -1
2188   %and2 = and i32 %a, %c
2189   %not2 = xor i32 %and2, -1
2190   %or = or i32 %not2, %b
2191   %and3 = and i32 %or, %not1
2192   call void @use(i32 %or)
2193   ret i32 %and3
2194 }
2195
2196 define i32 @and_or_not_not_extra_or_use1(i32 %a, i32 %b, i32 %c) {
2197 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not_extra_or_use1
2198 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2199 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[A]]
2200 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C]]
2201 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
2202 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[NOT2]], [[B]]
2203 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND1]], [[OR]]
2204 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
2205 ; CHECK-NEXT:    ret i32 [[AND3]]
2206 ;
2207   %and1 = and i32 %b, %a
2208   %not1 = xor i32 %and1, -1
2209   %and2 = and i32 %a, %c
2210   %not2 = xor i32 %and2, -1
2211   %or = or i32 %not2, %b
2212   %and3 = and i32 %or, %not1
2213   call void @use(i32 %and1)
2214   ret i32 %and3
2215 }
2216
2217 define i32 @and_or_not_not_extra_or_use2(i32 %a, i32 %b, i32 %c) {
2218 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not_extra_or_use2
2219 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2220 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C]]
2221 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C]], [[B]]
2222 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
2223 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
2224 ; CHECK-NEXT:    call void @use(i32 [[AND2]])
2225 ; CHECK-NEXT:    ret i32 [[AND3]]
2226 ;
2227   %and1 = and i32 %b, %a
2228   %not1 = xor i32 %and1, -1
2229   %and2 = and i32 %a, %c
2230   %not2 = xor i32 %and2, -1
2231   %or = or i32 %not2, %b
2232   %and3 = and i32 %or, %not1
2233   call void @use(i32 %and2)
2234   ret i32 %and3
2235 }
2236
2237 define i32 @and_or_not_not_2_extra_uses(i32 %a, i32 %b, i32 %c) {
2238 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not_2_extra_uses
2239 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2240 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[A]]
2241 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
2242 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C]]
2243 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
2244 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[NOT2]], [[B]]
2245 ; CHECK-NEXT:    call void @use(i32 [[OR]])
2246 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND1]], [[OR]]
2247 ; CHECK-NEXT:    ret i32 [[AND3]]
2248 ;
2249   %and1 = and i32 %b, %a
2250   call void @use(i32 %and1)
2251   %not1 = xor i32 %and1, -1
2252   %and2 = and i32 %a, %c
2253   %not2 = xor i32 %and2, -1
2254   %or = or i32 %not2, %b
2255   call void @use(i32 %or)
2256   %and3 = and i32 %not1, %or
2257   ret i32 %and3
2258 }
2259
2260 define i32 @and_or_not_not_wrong_a(i32 %a, i32 %b, i32 %c, i32 %d) {
2261 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not_wrong_a
2262 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32 [[D:%.*]]) {
2263 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[D]]
2264 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C]]
2265 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
2266 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[NOT2]], [[B]]
2267 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND1]], [[OR]]
2268 ; CHECK-NEXT:    ret i32 [[AND3]]
2269 ;
2270   %and1 = and i32 %b, %d
2271   %not1 = xor i32 %and1, -1
2272   %and2 = and i32 %a, %c
2273   %not2 = xor i32 %and2, -1
2274   %or = or i32 %not2, %b
2275   %and3 = and i32 %or, %not1
2276   ret i32 %and3
2277 }
2278
2279 define i32 @and_or_not_not_wrong_b(i32 %a, i32 %b, i32 %c, i32 %d) {
2280 ; CHECK-LABEL: define {{[^@]+}}@and_or_not_not_wrong_b
2281 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32 [[D:%.*]]) {
2282 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[D]], [[A]]
2283 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
2284 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C]]
2285 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
2286 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[NOT2]], [[B]]
2287 ; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR]], [[NOT1]]
2288 ; CHECK-NEXT:    ret i32 [[AND3]]
2289 ;
2290   %and1 = and i32 %d, %a
2291   %not1 = xor i32 %and1, -1
2292   %and2 = and i32 %a, %c
2293   %not2 = xor i32 %and2, -1
2294   %or = or i32 %not2, %b
2295   %and3 = and i32 %or, %not1
2296   ret i32 %and3
2297 }
2298
2299 ; (a & ~(b | c)) | ~(a | (b ^ c)) --> (~a & b & c) | ~(b | c)
2300
2301 define i32 @and_not_or_or_not_or_xor(i32 %a, i32 %b, i32 %c) {
2302 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_or_not_or_xor
2303 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2304 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[C]]
2305 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2306 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
2307 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR1]], [[OR2]]
2308 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP1]], -1
2309 ; CHECK-NEXT:    ret i32 [[OR3]]
2310 ;
2311   %or1 = or i32 %b, %c
2312   %not1 = xor i32 %or1, -1
2313   %and1 = and i32 %not1, %a
2314   %xor1 = xor i32 %b, %c
2315   %or2 = or i32 %xor1, %a
2316   %not2 = xor i32 %or2, -1
2317   %or3 = or i32 %and1, %not2
2318   ret i32 %or3
2319 }
2320
2321 define i32 @and_not_or_or_not_or_xor_commute1(i32 %a, i32 %b, i32 %c) {
2322 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_or_not_or_xor_commute1
2323 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2324 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[C]], [[B]]
2325 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2326 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
2327 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR1]], [[OR2]]
2328 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP1]], -1
2329 ; CHECK-NEXT:    ret i32 [[OR3]]
2330 ;
2331   %or1 = or i32 %c, %b
2332   %not1 = xor i32 %or1, -1
2333   %and1 = and i32 %not1, %a
2334   %xor1 = xor i32 %b, %c
2335   %or2 = or i32 %xor1, %a
2336   %not2 = xor i32 %or2, -1
2337   %or3 = or i32 %and1, %not2
2338   ret i32 %or3
2339 }
2340
2341 define i32 @and_not_or_or_not_or_xor_commute2(i32 %a0, i32 %b, i32 %c) {
2342 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_or_not_or_xor_commute2
2343 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2344 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
2345 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[C]]
2346 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2347 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
2348 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR1]], [[OR2]]
2349 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP1]], -1
2350 ; CHECK-NEXT:    ret i32 [[OR3]]
2351 ;
2352   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
2353   %or1 = or i32 %b, %c
2354   %not1 = xor i32 %or1, -1
2355   %and1 = and i32 %a, %not1
2356   %xor1 = xor i32 %b, %c
2357   %or2 = or i32 %xor1, %a
2358   %not2 = xor i32 %or2, -1
2359   %or3 = or i32 %and1, %not2
2360   ret i32 %or3
2361 }
2362
2363 define i32 @and_not_or_or_not_or_xor_commute3(i32 %a, i32 %b, i32 %c) {
2364 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_or_not_or_xor_commute3
2365 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2366 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[C]]
2367 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[C]], [[B]]
2368 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
2369 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR1]], [[OR2]]
2370 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP1]], -1
2371 ; CHECK-NEXT:    ret i32 [[OR3]]
2372 ;
2373   %or1 = or i32 %b, %c
2374   %not1 = xor i32 %or1, -1
2375   %and1 = and i32 %not1, %a
2376   %xor1 = xor i32 %c, %b
2377   %or2 = or i32 %xor1, %a
2378   %not2 = xor i32 %or2, -1
2379   %or3 = or i32 %and1, %not2
2380   ret i32 %or3
2381 }
2382
2383 define i32 @and_not_or_or_not_or_xor_commute4(i32 %a0, i32 %b, i32 %c) {
2384 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_or_not_or_xor_commute4
2385 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2386 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
2387 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[C]]
2388 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2389 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[XOR1]]
2390 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR1]], [[OR2]]
2391 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP1]], -1
2392 ; CHECK-NEXT:    ret i32 [[OR3]]
2393 ;
2394   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
2395   %or1 = or i32 %b, %c
2396   %not1 = xor i32 %or1, -1
2397   %and1 = and i32 %a, %not1
2398   %xor1 = xor i32 %b, %c
2399   %or2 = or i32 %a, %xor1
2400   %not2 = xor i32 %or2, -1
2401   %or3 = or i32 %and1, %not2
2402   ret i32 %or3
2403 }
2404
2405 define i32 @and_not_or_or_not_or_xor_commute5(i32 %a, i32 %b, i32 %c) {
2406 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_or_not_or_xor_commute5
2407 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2408 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[C]]
2409 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2410 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
2411 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR1]], [[OR2]]
2412 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP1]], -1
2413 ; CHECK-NEXT:    ret i32 [[OR3]]
2414 ;
2415   %or1 = or i32 %b, %c
2416   %not1 = xor i32 %or1, -1
2417   %and1 = and i32 %not1, %a
2418   %xor1 = xor i32 %b, %c
2419   %or2 = or i32 %xor1, %a
2420   %not2 = xor i32 %or2, -1
2421   %or3 = or i32 %not2, %and1
2422   ret i32 %or3
2423 }
2424
2425 define i32 @and_not_or_or_not_or_xor_use1(i32 %a, i32 %b, i32 %c) {
2426 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_or_not_or_xor_use1
2427 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2428 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[C]]
2429 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2430 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
2431 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR1]], [[OR2]]
2432 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP1]], -1
2433 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
2434 ; CHECK-NEXT:    ret i32 [[OR3]]
2435 ;
2436   %or1 = or i32 %b, %c
2437   %not1 = xor i32 %or1, -1
2438   %and1 = and i32 %not1, %a
2439   %xor1 = xor i32 %b, %c
2440   %or2 = or i32 %xor1, %a
2441   %not2 = xor i32 %or2, -1
2442   %or3 = or i32 %and1, %not2
2443   call void @use(i32 %or1)
2444   ret i32 %or3
2445 }
2446
2447 define i32 @and_not_or_or_not_or_xor_use2(i32 %a, i32 %b, i32 %c) {
2448 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_or_not_or_xor_use2
2449 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2450 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[C]]
2451 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
2452 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2453 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
2454 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR1]], [[OR2]]
2455 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP1]], -1
2456 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
2457 ; CHECK-NEXT:    ret i32 [[OR3]]
2458 ;
2459   %or1 = or i32 %b, %c
2460   %not1 = xor i32 %or1, -1
2461   %and1 = and i32 %not1, %a
2462   %xor1 = xor i32 %b, %c
2463   %or2 = or i32 %xor1, %a
2464   %not2 = xor i32 %or2, -1
2465   %or3 = or i32 %and1, %not2
2466   call void @use(i32 %not1)
2467   ret i32 %or3
2468 }
2469
2470 define i32 @and_not_or_or_not_or_xor_use3(i32 %a, i32 %b, i32 %c) {
2471 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_or_not_or_xor_use3
2472 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2473 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[C]]
2474 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
2475 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[A]]
2476 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2477 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
2478 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
2479 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[NOT2]]
2480 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
2481 ; CHECK-NEXT:    ret i32 [[OR3]]
2482 ;
2483   %or1 = or i32 %b, %c
2484   %not1 = xor i32 %or1, -1
2485   %and1 = and i32 %not1, %a
2486   %xor1 = xor i32 %b, %c
2487   %or2 = or i32 %xor1, %a
2488   %not2 = xor i32 %or2, -1
2489   %or3 = or i32 %and1, %not2
2490   call void @use(i32 %and1)
2491   ret i32 %or3
2492 }
2493
2494 define i32 @and_not_or_or_not_or_xor_use4(i32 %a, i32 %b, i32 %c) {
2495 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_or_not_or_xor_use4
2496 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2497 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[C]]
2498 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2499 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
2500 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR1]], [[OR2]]
2501 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP1]], -1
2502 ; CHECK-NEXT:    call void @use(i32 [[XOR1]])
2503 ; CHECK-NEXT:    ret i32 [[OR3]]
2504 ;
2505   %or1 = or i32 %b, %c
2506   %not1 = xor i32 %or1, -1
2507   %and1 = and i32 %not1, %a
2508   %xor1 = xor i32 %b, %c
2509   %or2 = or i32 %xor1, %a
2510   %not2 = xor i32 %or2, -1
2511   %or3 = or i32 %and1, %not2
2512   call void @use(i32 %xor1)
2513   ret i32 %or3
2514 }
2515
2516 define i32 @and_not_or_or_not_or_xor_use5(i32 %a, i32 %b, i32 %c) {
2517 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_or_not_or_xor_use5
2518 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2519 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[C]]
2520 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2521 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
2522 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR1]], [[OR2]]
2523 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP1]], -1
2524 ; CHECK-NEXT:    call void @use(i32 [[OR2]])
2525 ; CHECK-NEXT:    ret i32 [[OR3]]
2526 ;
2527   %or1 = or i32 %b, %c
2528   %not1 = xor i32 %or1, -1
2529   %and1 = and i32 %not1, %a
2530   %xor1 = xor i32 %b, %c
2531   %or2 = or i32 %xor1, %a
2532   %not2 = xor i32 %or2, -1
2533   %or3 = or i32 %and1, %not2
2534   call void @use(i32 %or2)
2535   ret i32 %or3
2536 }
2537
2538 define i32 @and_not_or_or_not_or_xor_use6(i32 %a, i32 %b, i32 %c) {
2539 ; CHECK-LABEL: define {{[^@]+}}@and_not_or_or_not_or_xor_use6
2540 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2541 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[C]]
2542 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
2543 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[A]]
2544 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2545 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
2546 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
2547 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[NOT2]]
2548 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
2549 ; CHECK-NEXT:    ret i32 [[OR3]]
2550 ;
2551   %or1 = or i32 %b, %c
2552   %not1 = xor i32 %or1, -1
2553   %and1 = and i32 %not1, %a
2554   %xor1 = xor i32 %b, %c
2555   %or2 = or i32 %xor1, %a
2556   %not2 = xor i32 %or2, -1
2557   %or3 = or i32 %and1, %not2
2558   call void @use(i32 %not2)
2559   ret i32 %or3
2560 }
2561
2562 ; (a | ~(b & c)) & ~(a & (b ^ c)) --> ~(a | b) | (a ^ b ^ c)
2563 ; This pattern is not handled because the result is more undefined than a source.
2564 ; It is invalid as is, but feezing %a and %b will make it valid.
2565
2566 define i32 @or_not_and_and_not_and_xor(i32 %a, i32 %b, i32 %c) {
2567 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_and_not_and_xor
2568 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2569 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[C]]
2570 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
2571 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[A]]
2572 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2573 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[XOR1]], [[A]]
2574 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR1]]
2575 ; CHECK-NEXT:    ret i32 [[AND3]]
2576 ;
2577   %and1 = and i32 %b, %c
2578   %not1 = xor i32 %and1, -1
2579   %or1 = or i32 %not1, %a
2580   %xor1 = xor i32 %b, %c
2581   %and2 = and i32 %xor1, %a
2582   %not2 = xor i32 %and2, -1
2583   %and3 = and i32 %or1, %not2
2584   ret i32 %and3
2585 }
2586
2587 define i32 @or_not_and_and_not_and_xor_commute1(i32 %a, i32 %b, i32 %c) {
2588 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_and_not_and_xor_commute1
2589 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2590 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[C]], [[B]]
2591 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
2592 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[A]]
2593 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2594 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[XOR1]], [[A]]
2595 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR1]]
2596 ; CHECK-NEXT:    ret i32 [[AND3]]
2597 ;
2598   %and1 = and i32 %c, %b
2599   %not1 = xor i32 %and1, -1
2600   %or1 = or i32 %not1, %a
2601   %xor1 = xor i32 %b, %c
2602   %and2 = and i32 %xor1, %a
2603   %not2 = xor i32 %and2, -1
2604   %and3 = and i32 %or1, %not2
2605   ret i32 %and3
2606 }
2607
2608 define i32 @or_not_and_and_not_and_xor_commute2(i32 %a0, i32 %b, i32 %c) {
2609 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_and_not_and_xor_commute2
2610 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2611 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
2612 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[C]]
2613 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
2614 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A]], [[NOT1]]
2615 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2616 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[XOR1]], [[A]]
2617 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR1]]
2618 ; CHECK-NEXT:    ret i32 [[AND3]]
2619 ;
2620   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
2621   %and1 = and i32 %b, %c
2622   %not1 = xor i32 %and1, -1
2623   %or1 = or i32 %a, %not1
2624   %xor1 = xor i32 %b, %c
2625   %and2 = and i32 %xor1, %a
2626   %not2 = xor i32 %and2, -1
2627   %and3 = and i32 %or1, %not2
2628   ret i32 %and3
2629 }
2630
2631 define i32 @or_not_and_and_not_and_xor_commute3(i32 %a, i32 %b, i32 %c) {
2632 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_and_not_and_xor_commute3
2633 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2634 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[C]]
2635 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
2636 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[A]]
2637 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[C]], [[B]]
2638 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[XOR1]], [[A]]
2639 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR1]]
2640 ; CHECK-NEXT:    ret i32 [[AND3]]
2641 ;
2642   %and1 = and i32 %b, %c
2643   %not1 = xor i32 %and1, -1
2644   %or1 = or i32 %not1, %a
2645   %xor1 = xor i32 %c, %b
2646   %and2 = and i32 %xor1, %a
2647   %not2 = xor i32 %and2, -1
2648   %and3 = and i32 %or1, %not2
2649   ret i32 %and3
2650 }
2651
2652 define i32 @or_not_and_and_not_and_xor_commute4(i32 %a0, i32 %b, i32 %c) {
2653 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_and_not_and_xor_commute4
2654 ; CHECK-SAME: (i32 [[A0:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2655 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0]]
2656 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[C]]
2657 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
2658 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A]], [[NOT1]]
2659 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2660 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[XOR1]]
2661 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR1]]
2662 ; CHECK-NEXT:    ret i32 [[AND3]]
2663 ;
2664   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
2665   %and1 = and i32 %b, %c
2666   %not1 = xor i32 %and1, -1
2667   %or1 = or i32 %a, %not1
2668   %xor1 = xor i32 %b, %c
2669   %and2 = and i32 %a, %xor1
2670   %not2 = xor i32 %and2, -1
2671   %and3 = and i32 %or1, %not2
2672   ret i32 %and3
2673 }
2674
2675 define i32 @or_not_and_and_not_and_xor_commute5(i32 %a, i32 %b, i32 %c) {
2676 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_and_not_and_xor_commute5
2677 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2678 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[C]]
2679 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
2680 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[A]]
2681 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2682 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[XOR1]], [[A]]
2683 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR1]]
2684 ; CHECK-NEXT:    ret i32 [[AND3]]
2685 ;
2686   %and1 = and i32 %b, %c
2687   %not1 = xor i32 %and1, -1
2688   %or1 = or i32 %not1, %a
2689   %xor1 = xor i32 %b, %c
2690   %and2 = and i32 %xor1, %a
2691   %not2 = xor i32 %and2, -1
2692   %and3 = and i32 %not2, %or1
2693   ret i32 %and3
2694 }
2695
2696 define i32 @or_not_and_and_not_and_xor_use1(i32 %a, i32 %b, i32 %c) {
2697 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_and_not_and_xor_use1
2698 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2699 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[C]]
2700 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
2701 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[A]]
2702 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2703 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[XOR1]], [[A]]
2704 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR1]]
2705 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
2706 ; CHECK-NEXT:    ret i32 [[AND3]]
2707 ;
2708   %and1 = and i32 %b, %c
2709   %not1 = xor i32 %and1, -1
2710   %or1 = or i32 %not1, %a
2711   %xor1 = xor i32 %b, %c
2712   %and2 = and i32 %xor1, %a
2713   %not2 = xor i32 %and2, -1
2714   %and3 = and i32 %or1, %not2
2715   call void @use(i32 %and1)
2716   ret i32 %and3
2717 }
2718
2719 define i32 @or_not_and_and_not_and_xor_use2(i32 %a, i32 %b, i32 %c) {
2720 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_and_not_and_xor_use2
2721 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2722 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[C]]
2723 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
2724 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[A]]
2725 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2726 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[XOR1]], [[A]]
2727 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR1]]
2728 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
2729 ; CHECK-NEXT:    ret i32 [[AND3]]
2730 ;
2731   %and1 = and i32 %b, %c
2732   %not1 = xor i32 %and1, -1
2733   %or1 = or i32 %not1, %a
2734   %xor1 = xor i32 %b, %c
2735   %and2 = and i32 %xor1, %a
2736   %not2 = xor i32 %and2, -1
2737   %and3 = and i32 %or1, %not2
2738   call void @use(i32 %not1)
2739   ret i32 %and3
2740 }
2741
2742 define i32 @or_not_and_and_not_and_xor_use3(i32 %a, i32 %b, i32 %c) {
2743 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_and_not_and_xor_use3
2744 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2745 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[C]]
2746 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
2747 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[A]]
2748 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2749 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[XOR1]], [[A]]
2750 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR1]]
2751 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
2752 ; CHECK-NEXT:    ret i32 [[AND3]]
2753 ;
2754   %and1 = and i32 %b, %c
2755   %not1 = xor i32 %and1, -1
2756   %or1 = or i32 %not1, %a
2757   %xor1 = xor i32 %b, %c
2758   %and2 = and i32 %xor1, %a
2759   %not2 = xor i32 %and2, -1
2760   %and3 = and i32 %or1, %not2
2761   call void @use(i32 %or1)
2762   ret i32 %and3
2763 }
2764
2765 define i32 @or_not_and_and_not_and_xor_use4(i32 %a, i32 %b, i32 %c) {
2766 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_and_not_and_xor_use4
2767 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2768 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[C]]
2769 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
2770 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[A]]
2771 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2772 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[XOR1]], [[A]]
2773 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR1]]
2774 ; CHECK-NEXT:    call void @use(i32 [[XOR1]])
2775 ; CHECK-NEXT:    ret i32 [[AND3]]
2776 ;
2777   %and1 = and i32 %b, %c
2778   %not1 = xor i32 %and1, -1
2779   %or1 = or i32 %not1, %a
2780   %xor1 = xor i32 %b, %c
2781   %and2 = and i32 %xor1, %a
2782   %not2 = xor i32 %and2, -1
2783   %and3 = and i32 %or1, %not2
2784   call void @use(i32 %xor1)
2785   ret i32 %and3
2786 }
2787
2788 define i32 @or_not_and_and_not_and_xor_use5(i32 %a, i32 %b, i32 %c) {
2789 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_and_not_and_xor_use5
2790 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2791 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[C]]
2792 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
2793 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[A]]
2794 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2795 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[XOR1]], [[A]]
2796 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR1]]
2797 ; CHECK-NEXT:    call void @use(i32 [[AND2]])
2798 ; CHECK-NEXT:    ret i32 [[AND3]]
2799 ;
2800   %and1 = and i32 %b, %c
2801   %not1 = xor i32 %and1, -1
2802   %or1 = or i32 %not1, %a
2803   %xor1 = xor i32 %b, %c
2804   %and2 = and i32 %xor1, %a
2805   %not2 = xor i32 %and2, -1
2806   %and3 = and i32 %or1, %not2
2807   call void @use(i32 %and2)
2808   ret i32 %and3
2809 }
2810
2811 define i32 @or_not_and_and_not_and_xor_use6(i32 %a, i32 %b, i32 %c) {
2812 ; CHECK-LABEL: define {{[^@]+}}@or_not_and_and_not_and_xor_use6
2813 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2814 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[C]]
2815 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
2816 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[A]]
2817 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
2818 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[XOR1]], [[A]]
2819 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
2820 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR1]]
2821 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
2822 ; CHECK-NEXT:    ret i32 [[AND3]]
2823 ;
2824   %and1 = and i32 %b, %c
2825   %not1 = xor i32 %and1, -1
2826   %or1 = or i32 %not1, %a
2827   %xor1 = xor i32 %b, %c
2828   %and2 = and i32 %xor1, %a
2829   %not2 = xor i32 %and2, -1
2830   %and3 = and i32 %or1, %not2
2831   call void @use(i32 %not2)
2832   ret i32 %and3
2833 }
2834
2835 ; (~a & b & c) | ~(a | b | c) -> ~(a | (b ^ c))
2836
2837 define i32 @not_and_and_or_not_or_or(i32 %a, i32 %b, i32 %c) {
2838 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_not_or_or
2839 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2840 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
2841 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
2842 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
2843 ; CHECK-NEXT:    ret i32 [[OR3]]
2844 ;
2845   %or1 = or i32 %b, %a
2846   %or2 = or i32 %or1, %c
2847   %not1 = xor i32 %or2, -1
2848   %not2 = xor i32 %a, -1
2849   %and1 = and i32 %not2, %b
2850   %and2 = and i32 %and1, %c
2851   %or3 = or i32 %and2, %not1
2852   ret i32 %or3
2853 }
2854
2855 define i32 @not_and_and_or_not_or_or_commute1_or(i32 %a, i32 %b, i32 %c) {
2856 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_not_or_or_commute1_or
2857 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2858 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
2859 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
2860 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
2861 ; CHECK-NEXT:    ret i32 [[OR3]]
2862 ;
2863   %or1 = or i32 %c, %a
2864   %or2 = or i32 %or1, %b
2865   %not1 = xor i32 %or2, -1
2866   %not2 = xor i32 %a, -1
2867   %and1 = and i32 %not2, %b
2868   %and2 = and i32 %and1, %c
2869   %or3 = or i32 %and2, %not1
2870   ret i32 %or3
2871 }
2872
2873 define i32 @not_and_and_or_not_or_or_commute2_or(i32 %a, i32 %b, i32 %c) {
2874 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_not_or_or_commute2_or
2875 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2876 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
2877 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
2878 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
2879 ; CHECK-NEXT:    ret i32 [[OR3]]
2880 ;
2881   %or1 = or i32 %b, %c
2882   %or2 = or i32 %or1, %a
2883   %not1 = xor i32 %or2, -1
2884   %not2 = xor i32 %a, -1
2885   %and1 = and i32 %not2, %b
2886   %and2 = and i32 %and1, %c
2887   %or3 = or i32 %and2, %not1
2888   ret i32 %or3
2889 }
2890
2891 define i32 @not_and_and_or_not_or_or_commute1_and(i32 %a, i32 %b, i32 %c) {
2892 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_not_or_or_commute1_and
2893 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2894 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
2895 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
2896 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
2897 ; CHECK-NEXT:    ret i32 [[OR3]]
2898 ;
2899   %or1 = or i32 %b, %a
2900   %or2 = or i32 %or1, %c
2901   %not1 = xor i32 %or2, -1
2902   %not2 = xor i32 %a, -1
2903   %and1 = and i32 %not2, %c
2904   %and2 = and i32 %and1, %b
2905   %or3 = or i32 %and2, %not1
2906   ret i32 %or3
2907 }
2908
2909 define i32 @not_and_and_or_not_or_or_commute2_and(i32 %a, i32 %b, i32 %c) {
2910 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_not_or_or_commute2_and
2911 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2912 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
2913 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
2914 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
2915 ; CHECK-NEXT:    ret i32 [[OR3]]
2916 ;
2917   %or1 = or i32 %b, %a
2918   %or2 = or i32 %or1, %c
2919   %not1 = xor i32 %or2, -1
2920   %not2 = xor i32 %a, -1
2921   %and1 = and i32 %b, %c
2922   %and2 = and i32 %and1, %not2
2923   %or3 = or i32 %and2, %not1
2924   ret i32 %or3
2925 }
2926
2927 define i32 @not_and_and_or_not_or_or_commute1(i32 %a, i32 %b, i32 %c) {
2928 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_not_or_or_commute1
2929 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
2930 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
2931 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
2932 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
2933 ; CHECK-NEXT:    ret i32 [[OR3]]
2934 ;
2935   %or1 = or i32 %a, %b
2936   %or2 = or i32 %or1, %c
2937   %not1 = xor i32 %or2, -1
2938   %not2 = xor i32 %a, -1
2939   %and1 = and i32 %not2, %b
2940   %and2 = and i32 %and1, %c
2941   %or3 = or i32 %and2, %not1
2942   ret i32 %or3
2943 }
2944
2945 define i32 @not_and_and_or_not_or_or_commute2(i32 %a, i32 %b, i32 %c0) {
2946 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_not_or_or_commute2
2947 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C0:%.*]]) {
2948 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0]]
2949 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
2950 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
2951 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
2952 ; CHECK-NEXT:    ret i32 [[OR3]]
2953 ;
2954   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
2955   %or1 = or i32 %b, %a
2956   %or2 = or i32 %c, %or1
2957   %not1 = xor i32 %or2, -1
2958   %not2 = xor i32 %a, -1
2959   %and1 = and i32 %not2, %b
2960   %and2 = and i32 %and1, %c
2961   %or3 = or i32 %and2, %not1
2962   ret i32 %or3
2963 }
2964
2965 define i32 @not_and_and_or_not_or_or_commute3(i32 %a, i32 %b0, i32 %c) {
2966 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_not_or_or_commute3
2967 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B0:%.*]], i32 [[C:%.*]]) {
2968 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
2969 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
2970 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
2971 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
2972 ; CHECK-NEXT:    ret i32 [[OR3]]
2973 ;
2974   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
2975   %or1 = or i32 %b, %a
2976   %or2 = or i32 %or1, %c
2977   %not1 = xor i32 %or2, -1
2978   %not2 = xor i32 %a, -1
2979   %and1 = and i32 %b, %not2
2980   %and2 = and i32 %and1, %c
2981   %or3 = or i32 %and2, %not1
2982   ret i32 %or3
2983 }
2984
2985 define i32 @not_and_and_or_not_or_or_commute4(i32 %a, i32 %b, i32 %c0) {
2986 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_not_or_or_commute4
2987 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C0:%.*]]) {
2988 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0]]
2989 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
2990 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
2991 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
2992 ; CHECK-NEXT:    ret i32 [[OR3]]
2993 ;
2994   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
2995   %or1 = or i32 %b, %a
2996   %or2 = or i32 %or1, %c
2997   %not1 = xor i32 %or2, -1
2998   %not2 = xor i32 %a, -1
2999   %and1 = and i32 %not2, %b
3000   %and2 = and i32 %c, %and1
3001   %or3 = or i32 %and2, %not1
3002   ret i32 %or3
3003 }
3004
3005 define i32 @not_and_and_or_not_or_or_use1(i32 %a, i32 %b, i32 %c) {
3006 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_not_or_or_use1
3007 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3008 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[A]]
3009 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
3010 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
3011 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
3012 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
3013 ; CHECK-NEXT:    ret i32 [[OR3]]
3014 ;
3015   %or1 = or i32 %b, %a
3016   %or2 = or i32 %or1, %c
3017   %not1 = xor i32 %or2, -1
3018   %not2 = xor i32 %a, -1
3019   %and1 = and i32 %not2, %b
3020   %and2 = and i32 %and1, %c
3021   %or3 = or i32 %and2, %not1
3022   call void @use(i32 %or1)
3023   ret i32 %or3
3024 }
3025
3026 define i32 @not_and_and_or_not_or_or_use2(i32 %a, i32 %b, i32 %c) {
3027 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_not_or_or_use2
3028 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3029 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[A]]
3030 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
3031 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
3032 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
3033 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
3034 ; CHECK-NEXT:    call void @use(i32 [[OR2]])
3035 ; CHECK-NEXT:    ret i32 [[OR3]]
3036 ;
3037   %or1 = or i32 %b, %a
3038   %or2 = or i32 %or1, %c
3039   %not1 = xor i32 %or2, -1
3040   %not2 = xor i32 %a, -1
3041   %and1 = and i32 %not2, %b
3042   %and2 = and i32 %and1, %c
3043   %or3 = or i32 %and2, %not1
3044   call void @use(i32 %or2)
3045   ret i32 %or3
3046 }
3047
3048 define i32 @not_and_and_or_not_or_or_use3(i32 %a, i32 %b, i32 %c) {
3049 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_not_or_or_use3
3050 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3051 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[A]]
3052 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
3053 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
3054 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3055 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
3056 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
3057 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
3058 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
3059 ; CHECK-NEXT:    ret i32 [[OR3]]
3060 ;
3061   %or1 = or i32 %b, %a
3062   %or2 = or i32 %or1, %c
3063   %not1 = xor i32 %or2, -1
3064   %not2 = xor i32 %a, -1
3065   %and1 = and i32 %not2, %b
3066   %and2 = and i32 %and1, %c
3067   %or3 = or i32 %and2, %not1
3068   call void @use(i32 %not1)
3069   ret i32 %or3
3070 }
3071
3072 define i32 @not_and_and_or_not_or_or_use4(i32 %a, i32 %b, i32 %c) {
3073 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_not_or_or_use4
3074 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3075 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3076 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
3077 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
3078 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
3079 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
3080 ; CHECK-NEXT:    ret i32 [[OR3]]
3081 ;
3082   %or1 = or i32 %b, %a
3083   %or2 = or i32 %or1, %c
3084   %not1 = xor i32 %or2, -1
3085   %not2 = xor i32 %a, -1
3086   %and1 = and i32 %not2, %b
3087   %and2 = and i32 %and1, %c
3088   %or3 = or i32 %and2, %not1
3089   call void @use(i32 %not2)
3090   ret i32 %or3
3091 }
3092
3093 define i32 @not_and_and_or_not_or_or_use5(i32 %a, i32 %b, i32 %c) {
3094 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_not_or_or_use5
3095 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3096 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3097 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
3098 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
3099 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
3100 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
3101 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
3102 ; CHECK-NEXT:    ret i32 [[OR3]]
3103 ;
3104   %or1 = or i32 %b, %a
3105   %or2 = or i32 %or1, %c
3106   %not1 = xor i32 %or2, -1
3107   %not2 = xor i32 %a, -1
3108   %and1 = and i32 %not2, %b
3109   %and2 = and i32 %and1, %c
3110   %or3 = or i32 %and2, %not1
3111   call void @use(i32 %and1)
3112   ret i32 %or3
3113 }
3114
3115 define i32 @not_and_and_or_not_or_or_use6(i32 %a, i32 %b, i32 %c) {
3116 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_not_or_or_use6
3117 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3118 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[A]]
3119 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
3120 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
3121 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3122 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
3123 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
3124 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
3125 ; CHECK-NEXT:    call void @use(i32 [[AND2]])
3126 ; CHECK-NEXT:    ret i32 [[OR3]]
3127 ;
3128   %or1 = or i32 %b, %a
3129   %or2 = or i32 %or1, %c
3130   %not1 = xor i32 %or2, -1
3131   %not2 = xor i32 %a, -1
3132   %and1 = and i32 %not2, %b
3133   %and2 = and i32 %and1, %c
3134   %or3 = or i32 %and2, %not1
3135   call void @use(i32 %and2)
3136   ret i32 %or3
3137 }
3138
3139 ; (~a | b | c) & ~(a & b & c) -> ~a | (b ^ c)
3140
3141 define i32 @not_or_or_and_not_and_and(i32 %a, i32 %b, i32 %c) {
3142 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_not_and_and
3143 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3144 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3145 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
3146 ; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
3147 ; CHECK-NEXT:    ret i32 [[AND3]]
3148 ;
3149   %and1 = and i32 %b, %a
3150   %and2 = and i32 %and1, %c
3151   %not1 = xor i32 %and2, -1
3152   %not2 = xor i32 %a, -1
3153   %or1 = or i32 %not2, %b
3154   %or2 = or i32 %or1, %c
3155   %and3 = and i32 %or2, %not1
3156   ret i32 %and3
3157 }
3158
3159 define i32 @not_or_or_and_not_and_and_commute1_and(i32 %a, i32 %b, i32 %c) {
3160 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_not_and_and_commute1_and
3161 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3162 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3163 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
3164 ; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
3165 ; CHECK-NEXT:    ret i32 [[AND3]]
3166 ;
3167   %and1 = and i32 %c, %a
3168   %and2 = and i32 %and1, %b
3169   %not1 = xor i32 %and2, -1
3170   %not2 = xor i32 %a, -1
3171   %or1 = or i32 %not2, %b
3172   %or2 = or i32 %or1, %c
3173   %and3 = and i32 %or2, %not1
3174   ret i32 %and3
3175 }
3176
3177 define i32 @not_or_or_and_not_and_and_commute2_and(i32 %a, i32 %b, i32 %c) {
3178 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_not_and_and_commute2_and
3179 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3180 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3181 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
3182 ; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
3183 ; CHECK-NEXT:    ret i32 [[AND3]]
3184 ;
3185   %and1 = and i32 %b, %c
3186   %and2 = and i32 %and1, %a
3187   %not1 = xor i32 %and2, -1
3188   %not2 = xor i32 %a, -1
3189   %or1 = or i32 %not2, %b
3190   %or2 = or i32 %or1, %c
3191   %and3 = and i32 %or2, %not1
3192   ret i32 %and3
3193 }
3194
3195 define i32 @not_or_or_and_not_and_and_commute1_or(i32 %a, i32 %b, i32 %c) {
3196 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_not_and_and_commute1_or
3197 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3198 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3199 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
3200 ; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
3201 ; CHECK-NEXT:    ret i32 [[AND3]]
3202 ;
3203   %and1 = and i32 %b, %a
3204   %and2 = and i32 %and1, %c
3205   %not1 = xor i32 %and2, -1
3206   %not2 = xor i32 %a, -1
3207   %or1 = or i32 %not2, %c
3208   %or2 = or i32 %or1, %b
3209   %and3 = and i32 %or2, %not1
3210   ret i32 %and3
3211 }
3212
3213 define i32 @not_or_or_and_not_and_and_commute2_or(i32 %a, i32 %b, i32 %c) {
3214 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_not_and_and_commute2_or
3215 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3216 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3217 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
3218 ; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
3219 ; CHECK-NEXT:    ret i32 [[AND3]]
3220 ;
3221   %and1 = and i32 %b, %a
3222   %and2 = and i32 %and1, %c
3223   %not1 = xor i32 %and2, -1
3224   %not2 = xor i32 %a, -1
3225   %or1 = or i32 %b, %c
3226   %or2 = or i32 %or1, %not2
3227   %and3 = and i32 %or2, %not1
3228   ret i32 %and3
3229 }
3230
3231 define i32 @not_or_or_and_not_and_and_commute1(i32 %a, i32 %b, i32 %c) {
3232 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_not_and_and_commute1
3233 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3234 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3235 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
3236 ; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
3237 ; CHECK-NEXT:    ret i32 [[AND3]]
3238 ;
3239   %and1 = and i32 %a, %b
3240   %and2 = and i32 %and1, %c
3241   %not1 = xor i32 %and2, -1
3242   %not2 = xor i32 %a, -1
3243   %or1 = or i32 %not2, %b
3244   %or2 = or i32 %or1, %c
3245   %and3 = and i32 %or2, %not1
3246   ret i32 %and3
3247 }
3248
3249 define i32 @not_or_or_and_not_and_and_commute2(i32 %a, i32 %b, i32 %c0) {
3250 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_not_and_and_commute2
3251 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C0:%.*]]) {
3252 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0]]
3253 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3254 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
3255 ; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
3256 ; CHECK-NEXT:    ret i32 [[AND3]]
3257 ;
3258   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
3259   %and1 = and i32 %b, %a
3260   %and2 = and i32 %c, %and1
3261   %not1 = xor i32 %and2, -1
3262   %not2 = xor i32 %a, -1
3263   %or1 = or i32 %not2, %b
3264   %or2 = or i32 %or1, %c
3265   %and3 = and i32 %or2, %not1
3266   ret i32 %and3
3267 }
3268
3269 define i32 @not_or_or_and_not_and_and_commute3(i32 %a, i32 %b0, i32 %c) {
3270 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_not_and_and_commute3
3271 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B0:%.*]], i32 [[C:%.*]]) {
3272 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
3273 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3274 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
3275 ; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
3276 ; CHECK-NEXT:    ret i32 [[AND3]]
3277 ;
3278   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
3279   %and1 = and i32 %b, %a
3280   %and2 = and i32 %and1, %c
3281   %not1 = xor i32 %and2, -1
3282   %not2 = xor i32 %a, -1
3283   %or1 = or i32 %b, %not2
3284   %or2 = or i32 %or1, %c
3285   %and3 = and i32 %or2, %not1
3286   ret i32 %and3
3287 }
3288
3289 define i32 @not_or_or_and_not_and_and_commute4(i32 %a, i32 %b, i32 %c0) {
3290 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_not_and_and_commute4
3291 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C0:%.*]]) {
3292 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0]]
3293 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3294 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
3295 ; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
3296 ; CHECK-NEXT:    ret i32 [[AND3]]
3297 ;
3298   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
3299   %and1 = and i32 %b, %a
3300   %and2 = and i32 %and1, %c
3301   %not1 = xor i32 %and2, -1
3302   %not2 = xor i32 %a, -1
3303   %or1 = or i32 %not2, %b
3304   %or2 = or i32 %c, %or1
3305   %and3 = and i32 %or2, %not1
3306   ret i32 %and3
3307 }
3308
3309 define i32 @not_or_or_and_not_and_and_use1(i32 %a, i32 %b, i32 %c) {
3310 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_not_and_and_use1
3311 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3312 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[A]]
3313 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3314 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
3315 ; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
3316 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
3317 ; CHECK-NEXT:    ret i32 [[AND3]]
3318 ;
3319   %and1 = and i32 %b, %a
3320   %and2 = and i32 %and1, %c
3321   %not1 = xor i32 %and2, -1
3322   %not2 = xor i32 %a, -1
3323   %or1 = or i32 %not2, %b
3324   %or2 = or i32 %or1, %c
3325   %and3 = and i32 %or2, %not1
3326   call void @use(i32 %and1)
3327   ret i32 %and3
3328 }
3329
3330 define i32 @not_or_or_and_not_and_and_use2(i32 %a, i32 %b, i32 %c) {
3331 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_not_and_and_use2
3332 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3333 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[A]]
3334 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
3335 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3336 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
3337 ; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
3338 ; CHECK-NEXT:    call void @use(i32 [[AND2]])
3339 ; CHECK-NEXT:    ret i32 [[AND3]]
3340 ;
3341   %and1 = and i32 %b, %a
3342   %and2 = and i32 %and1, %c
3343   %not1 = xor i32 %and2, -1
3344   %not2 = xor i32 %a, -1
3345   %or1 = or i32 %not2, %b
3346   %or2 = or i32 %or1, %c
3347   %and3 = and i32 %or2, %not1
3348   call void @use(i32 %and2)
3349   ret i32 %and3
3350 }
3351
3352 define i32 @not_or_or_and_not_and_and_use3(i32 %a, i32 %b, i32 %c) {
3353 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_not_and_and_use3
3354 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3355 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[A]]
3356 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
3357 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND2]], -1
3358 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3359 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
3360 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
3361 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
3362 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
3363 ; CHECK-NEXT:    ret i32 [[AND3]]
3364 ;
3365   %and1 = and i32 %b, %a
3366   %and2 = and i32 %and1, %c
3367   %not1 = xor i32 %and2, -1
3368   %not2 = xor i32 %a, -1
3369   %or1 = or i32 %not2, %b
3370   %or2 = or i32 %or1, %c
3371   %and3 = and i32 %or2, %not1
3372   call void @use(i32 %not1)
3373   ret i32 %and3
3374 }
3375
3376 define i32 @not_or_or_and_not_and_and_use4(i32 %a, i32 %b, i32 %c) {
3377 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_not_and_and_use4
3378 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3379 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3380 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
3381 ; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
3382 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
3383 ; CHECK-NEXT:    ret i32 [[AND3]]
3384 ;
3385   %and1 = and i32 %b, %a
3386   %and2 = and i32 %and1, %c
3387   %not1 = xor i32 %and2, -1
3388   %not2 = xor i32 %a, -1
3389   %or1 = or i32 %not2, %b
3390   %or2 = or i32 %or1, %c
3391   %and3 = and i32 %or2, %not1
3392   call void @use(i32 %not2)
3393   ret i32 %and3
3394 }
3395
3396 define i32 @not_or_or_and_not_and_and_use5(i32 %a, i32 %b, i32 %c) {
3397 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_not_and_and_use5
3398 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3399 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3400 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
3401 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
3402 ; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
3403 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
3404 ; CHECK-NEXT:    ret i32 [[AND3]]
3405 ;
3406   %and1 = and i32 %b, %a
3407   %and2 = and i32 %and1, %c
3408   %not1 = xor i32 %and2, -1
3409   %not2 = xor i32 %a, -1
3410   %or1 = or i32 %not2, %b
3411   %or2 = or i32 %or1, %c
3412   %and3 = and i32 %or2, %not1
3413   call void @use(i32 %or1)
3414   ret i32 %and3
3415 }
3416
3417 define i32 @not_or_or_and_not_and_and_use6(i32 %a, i32 %b, i32 %c) {
3418 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_not_and_and_use6
3419 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3420 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[A]]
3421 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
3422 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3423 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
3424 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
3425 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
3426 ; CHECK-NEXT:    call void @use(i32 [[OR2]])
3427 ; CHECK-NEXT:    ret i32 [[AND3]]
3428 ;
3429   %and1 = and i32 %b, %a
3430   %and2 = and i32 %and1, %c
3431   %not1 = xor i32 %and2, -1
3432   %not2 = xor i32 %a, -1
3433   %or1 = or i32 %not2, %b
3434   %or2 = or i32 %or1, %c
3435   %and3 = and i32 %or2, %not1
3436   call void @use(i32 %or2)
3437   ret i32 %and3
3438 }
3439
3440 ; (~a & b & c) | ~(a | b) -> (c | ~b) & ~a
3441
3442 define i32 @not_and_and_or_no_or(i32 %a, i32 %b, i32 %c) {
3443 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or
3444 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3445 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3446 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3447 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[C]]
3448 ; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
3449 ; CHECK-NEXT:    ret i32 [[OR2]]
3450 ;
3451   %or1 = or i32 %b, %a
3452   %not1 = xor i32 %or1, -1
3453   %not2 = xor i32 %a, -1
3454   %and1 = and i32 %not2, %b
3455   %and2 = and i32 %and1, %c
3456   %or2 = or i32 %and2, %not1
3457   ret i32 %or2
3458 }
3459
3460 define i32 @not_and_and_or_no_or_commute1_and(i32 %a, i32 %b, i32 %c) {
3461 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_commute1_and
3462 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3463 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3464 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3465 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[C]]
3466 ; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
3467 ; CHECK-NEXT:    ret i32 [[OR2]]
3468 ;
3469   %or1 = or i32 %b, %a
3470   %not1 = xor i32 %or1, -1
3471   %not2 = xor i32 %a, -1
3472   %and1 = and i32 %c, %b
3473   %and2 = and i32 %and1, %not2
3474   %or2 = or i32 %and2, %not1
3475   ret i32 %or2
3476 }
3477
3478 define i32 @not_and_and_or_no_or_commute2_and(i32 %a, i32 %b, i32 %c) {
3479 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_commute2_and
3480 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3481 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3482 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3483 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[C]]
3484 ; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
3485 ; CHECK-NEXT:    ret i32 [[OR2]]
3486 ;
3487   %or1 = or i32 %b, %a
3488   %not1 = xor i32 %or1, -1
3489   %not2 = xor i32 %a, -1
3490   %and1 = and i32 %not2, %c
3491   %and2 = and i32 %and1, %b
3492   %or2 = or i32 %and2, %not1
3493   ret i32 %or2
3494 }
3495
3496 define i32 @not_and_and_or_no_or_commute1(i32 %a, i32 %b, i32 %c) {
3497 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_commute1
3498 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3499 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3500 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3501 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[C]]
3502 ; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
3503 ; CHECK-NEXT:    ret i32 [[OR2]]
3504 ;
3505   %or1 = or i32 %a, %b
3506   %not1 = xor i32 %or1, -1
3507   %not2 = xor i32 %a, -1
3508   %and1 = and i32 %not2, %b
3509   %and2 = and i32 %and1, %c
3510   %or2 = or i32 %and2, %not1
3511   ret i32 %or2
3512 }
3513
3514 define i32 @not_and_and_or_no_or_commute2(i32 %a, i32 %b0, i32 %c) {
3515 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_commute2
3516 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B0:%.*]], i32 [[C:%.*]]) {
3517 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
3518 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3519 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3520 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[C]]
3521 ; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
3522 ; CHECK-NEXT:    ret i32 [[OR2]]
3523 ;
3524   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
3525   %or1 = or i32 %b, %a
3526   %not1 = xor i32 %or1, -1
3527   %not2 = xor i32 %a, -1
3528   %and1 = and i32 %b, %not2
3529   %and2 = and i32 %and1, %c
3530   %or2 = or i32 %and2, %not1
3531   ret i32 %or2
3532 }
3533
3534 define i32 @not_and_and_or_no_or_commute3(i32 %a, i32 %b, i32 %c0) {
3535 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_commute3
3536 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C0:%.*]]) {
3537 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0]]
3538 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3539 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3540 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[C]], [[TMP1]]
3541 ; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
3542 ; CHECK-NEXT:    ret i32 [[OR2]]
3543 ;
3544   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
3545   %or1 = or i32 %b, %a
3546   %not1 = xor i32 %or1, -1
3547   %not2 = xor i32 %a, -1
3548   %and1 = and i32 %not2, %b
3549   %and2 = and i32 %c, %and1
3550   %or2 = or i32 %and2, %not1
3551   ret i32 %or2
3552 }
3553
3554 define i32 @not_and_and_or_no_or_use1(i32 %a, i32 %b, i32 %c) {
3555 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_use1
3556 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3557 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3558 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3559 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[C]]
3560 ; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
3561 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
3562 ; CHECK-NEXT:    ret i32 [[OR2]]
3563 ;
3564   %or1 = or i32 %b, %a
3565   %not1 = xor i32 %or1, -1
3566   %not2 = xor i32 %a, -1
3567   %and1 = and i32 %not2, %b
3568   %and2 = and i32 %and1, %c
3569   %or2 = or i32 %and2, %not1
3570   call void @use(i32 %not2)
3571   ret i32 %or2
3572 }
3573
3574 define i32 @not_and_and_or_no_or_use2(i32 %a, i32 %b, i32 %c) {
3575 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_use2
3576 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3577 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3578 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3579 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[C]]
3580 ; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
3581 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
3582 ; CHECK-NEXT:    ret i32 [[OR2]]
3583 ;
3584   %or1 = or i32 %b, %a
3585   %not1 = xor i32 %or1, -1
3586   %not2 = xor i32 %a, -1
3587   %and1 = and i32 %b, %c
3588   %and2 = and i32 %and1, %not2
3589   %or2 = or i32 %and2, %not1
3590   call void @use(i32 %not2)
3591   ret i32 %or2
3592 }
3593
3594 define i32 @not_and_and_or_no_or_use3(i32 %a, i32 %b, i32 %c) {
3595 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_use3
3596 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3597 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3598 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3599 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[C]]
3600 ; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
3601 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
3602 ; CHECK-NEXT:    ret i32 [[OR2]]
3603 ;
3604   %or1 = or i32 %b, %a
3605   %not1 = xor i32 %or1, -1
3606   %not2 = xor i32 %a, -1
3607   %and1 = and i32 %not2, %c
3608   %and2 = and i32 %and1, %b
3609   %or2 = or i32 %and2, %not1
3610   call void @use(i32 %not2)
3611   ret i32 %or2
3612 }
3613
3614 define i32 @not_and_and_or_no_or_use4(i32 %a, i32 %b, i32 %c) {
3615 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_use4
3616 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3617 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3618 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3619 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[C]]
3620 ; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
3621 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
3622 ; CHECK-NEXT:    ret i32 [[OR2]]
3623 ;
3624   %or1 = or i32 %b, %a
3625   %not1 = xor i32 %or1, -1
3626   %not2 = xor i32 %a, -1
3627   %and1 = and i32 %not2, %c
3628   %and2 = and i32 %and1, %b
3629   %or2 = or i32 %and2, %not1
3630   call void @use(i32 %not2)
3631   ret i32 %or2
3632 }
3633
3634 define i32 @not_and_and_or_no_or_use5(i32 %a, i32 %b, i32 %c) {
3635 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_use5
3636 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3637 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[A]]
3638 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
3639 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3640 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
3641 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
3642 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[AND2]], [[NOT1]]
3643 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
3644 ; CHECK-NEXT:    ret i32 [[OR2]]
3645 ;
3646   %or1 = or i32 %b, %a
3647   %not1 = xor i32 %or1, -1
3648   %not2 = xor i32 %a, -1
3649   %and1 = and i32 %not2, %b
3650   %and2 = and i32 %and1, %c
3651   %or2 = or i32 %and2, %not1
3652   call void @use(i32 %or1)
3653   ret i32 %or2
3654 }
3655
3656 define i32 @not_and_and_or_no_or_use6(i32 %a, i32 %b, i32 %c) {
3657 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_use6
3658 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3659 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[A]]
3660 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
3661 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3662 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
3663 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
3664 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[AND2]], [[NOT1]]
3665 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
3666 ; CHECK-NEXT:    ret i32 [[OR2]]
3667 ;
3668   %or1 = or i32 %b, %a
3669   %not1 = xor i32 %or1, -1
3670   %not2 = xor i32 %a, -1
3671   %and1 = and i32 %not2, %b
3672   %and2 = and i32 %and1, %c
3673   %or2 = or i32 %and2, %not1
3674   call void @use(i32 %not1)
3675   ret i32 %or2
3676 }
3677
3678 define i32 @not_and_and_or_no_or_use7(i32 %a, i32 %b, i32 %c) {
3679 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_use7
3680 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3681 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3682 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
3683 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3684 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[C]]
3685 ; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
3686 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
3687 ; CHECK-NEXT:    ret i32 [[OR2]]
3688 ;
3689   %or1 = or i32 %b, %a
3690   %not1 = xor i32 %or1, -1
3691   %not2 = xor i32 %a, -1
3692   %and1 = and i32 %not2, %b
3693   %and2 = and i32 %and1, %c
3694   %or2 = or i32 %and2, %not1
3695   call void @use(i32 %and1)
3696   ret i32 %or2
3697 }
3698
3699 define i32 @not_and_and_or_no_or_use8(i32 %a, i32 %b, i32 %c) {
3700 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_use8
3701 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3702 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[A]]
3703 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
3704 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3705 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
3706 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
3707 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[AND2]], [[NOT1]]
3708 ; CHECK-NEXT:    call void @use(i32 [[AND2]])
3709 ; CHECK-NEXT:    ret i32 [[OR2]]
3710 ;
3711   %or1 = or i32 %b, %a
3712   %not1 = xor i32 %or1, -1
3713   %not2 = xor i32 %a, -1
3714   %and1 = and i32 %not2, %b
3715   %and2 = and i32 %and1, %c
3716   %or2 = or i32 %and2, %not1
3717   call void @use(i32 %and2)
3718   ret i32 %or2
3719 }
3720
3721 ; (~a | b | c) & ~(a & b) -> (c & ~b) | ~a
3722
3723 define i32 @not_or_or_and_no_and(i32 %a, i32 %b, i32 %c) {
3724 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and
3725 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3726 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3727 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3728 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[C]]
3729 ; CHECK-NEXT:    [[AND2:%.*]] = or i32 [[TMP2]], [[NOT2]]
3730 ; CHECK-NEXT:    ret i32 [[AND2]]
3731 ;
3732   %and1 = and i32 %b, %a
3733   %not1 = xor i32 %and1, -1
3734   %not2 = xor i32 %a, -1
3735   %or1 = or i32 %not2, %b
3736   %or2 = or i32 %or1, %c
3737   %and2 = and i32 %or2, %not1
3738   ret i32 %and2
3739 }
3740
3741 define i32 @not_or_or_and_no_and_commute1_or(i32 %a, i32 %b, i32 %c) {
3742 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_commute1_or
3743 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3744 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3745 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3746 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[C]]
3747 ; CHECK-NEXT:    [[AND2:%.*]] = or i32 [[TMP2]], [[NOT2]]
3748 ; CHECK-NEXT:    ret i32 [[AND2]]
3749 ;
3750   %and1 = and i32 %b, %a
3751   %not1 = xor i32 %and1, -1
3752   %not2 = xor i32 %a, -1
3753   %or1 = or i32 %c, %b
3754   %or2 = or i32 %or1, %not2
3755   %and2 = and i32 %or2, %not1
3756   ret i32 %and2
3757 }
3758
3759 define i32 @not_or_or_and_no_and_commute2_or(i32 %a, i32 %b, i32 %c) {
3760 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_commute2_or
3761 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3762 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3763 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3764 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[C]]
3765 ; CHECK-NEXT:    [[AND2:%.*]] = or i32 [[TMP2]], [[NOT2]]
3766 ; CHECK-NEXT:    ret i32 [[AND2]]
3767 ;
3768   %and1 = and i32 %b, %a
3769   %not1 = xor i32 %and1, -1
3770   %not2 = xor i32 %a, -1
3771   %or1 = or i32 %not2, %c
3772   %or2 = or i32 %or1, %b
3773   %and2 = and i32 %or2, %not1
3774   ret i32 %and2
3775 }
3776
3777 define i32 @not_or_or_and_no_and_commute1(i32 %a, i32 %b, i32 %c) {
3778 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_commute1
3779 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3780 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3781 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3782 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[C]]
3783 ; CHECK-NEXT:    [[AND2:%.*]] = or i32 [[TMP2]], [[NOT2]]
3784 ; CHECK-NEXT:    ret i32 [[AND2]]
3785 ;
3786   %and1 = and i32 %a, %b
3787   %not1 = xor i32 %and1, -1
3788   %not2 = xor i32 %a, -1
3789   %or1 = or i32 %not2, %b
3790   %or2 = or i32 %or1, %c
3791   %and2 = and i32 %or2, %not1
3792   ret i32 %and2
3793 }
3794
3795 define i32 @not_or_or_and_no_and_commute2(i32 %a, i32 %b0, i32 %c) {
3796 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_commute2
3797 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B0:%.*]], i32 [[C:%.*]]) {
3798 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0]]
3799 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3800 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3801 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[C]]
3802 ; CHECK-NEXT:    [[AND2:%.*]] = or i32 [[TMP2]], [[NOT2]]
3803 ; CHECK-NEXT:    ret i32 [[AND2]]
3804 ;
3805   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
3806   %and1 = and i32 %b, %a
3807   %not1 = xor i32 %and1, -1
3808   %not2 = xor i32 %a, -1
3809   %or1 = or i32 %b, %not2
3810   %or2 = or i32 %or1, %c
3811   %and2 = and i32 %or2, %not1
3812   ret i32 %and2
3813 }
3814
3815 define i32 @not_or_or_and_no_and_commute3(i32 %a, i32 %b, i32 %c0) {
3816 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_commute3
3817 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C0:%.*]]) {
3818 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0]]
3819 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3820 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3821 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[C]], [[TMP1]]
3822 ; CHECK-NEXT:    [[AND2:%.*]] = or i32 [[TMP2]], [[NOT2]]
3823 ; CHECK-NEXT:    ret i32 [[AND2]]
3824 ;
3825   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
3826   %and1 = and i32 %b, %a
3827   %not1 = xor i32 %and1, -1
3828   %not2 = xor i32 %a, -1
3829   %or1 = or i32 %not2, %b
3830   %or2 = or i32 %c, %or1
3831   %and2 = and i32 %or2, %not1
3832   ret i32 %and2
3833 }
3834
3835 define i32 @not_or_or_and_no_and_use1(i32 %a, i32 %b, i32 %c) {
3836 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_use1
3837 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3838 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3839 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3840 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[C]]
3841 ; CHECK-NEXT:    [[AND2:%.*]] = or i32 [[TMP2]], [[NOT2]]
3842 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
3843 ; CHECK-NEXT:    ret i32 [[AND2]]
3844 ;
3845   %and1 = and i32 %b, %a
3846   %not1 = xor i32 %and1, -1
3847   %not2 = xor i32 %a, -1
3848   %or1 = or i32 %not2, %b
3849   %or2 = or i32 %or1, %c
3850   %and2 = and i32 %or2, %not1
3851   call void @use(i32 %not2)
3852   ret i32 %and2
3853 }
3854
3855 define i32 @not_or_or_and_no_and_use2(i32 %a, i32 %b, i32 %c) {
3856 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_use2
3857 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3858 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3859 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3860 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[C]]
3861 ; CHECK-NEXT:    [[AND2:%.*]] = or i32 [[TMP2]], [[NOT2]]
3862 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
3863 ; CHECK-NEXT:    ret i32 [[AND2]]
3864 ;
3865   %and1 = and i32 %b, %a
3866   %not1 = xor i32 %and1, -1
3867   %not2 = xor i32 %a, -1
3868   %or1 = or i32 %b, %c
3869   %or2 = or i32 %or1, %not2
3870   %and2 = and i32 %or2, %not1
3871   call void @use(i32 %not2)
3872   ret i32 %and2
3873 }
3874
3875 define i32 @not_or_or_and_no_and_use3(i32 %a, i32 %b, i32 %c) {
3876 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_use3
3877 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3878 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3879 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3880 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[C]]
3881 ; CHECK-NEXT:    [[AND2:%.*]] = or i32 [[TMP2]], [[NOT2]]
3882 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
3883 ; CHECK-NEXT:    ret i32 [[AND2]]
3884 ;
3885   %and1 = and i32 %b, %a
3886   %not1 = xor i32 %and1, -1
3887   %not2 = xor i32 %a, -1
3888   %or1 = or i32 %not2, %c
3889   %or2 = or i32 %or1, %b
3890   %and2 = and i32 %or2, %not1
3891   call void @use(i32 %not2)
3892   ret i32 %and2
3893 }
3894
3895 define i32 @not_or_or_and_no_and_use4(i32 %a, i32 %b, i32 %c) {
3896 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_use4
3897 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3898 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3899 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3900 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[C]]
3901 ; CHECK-NEXT:    [[AND2:%.*]] = or i32 [[TMP2]], [[NOT2]]
3902 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
3903 ; CHECK-NEXT:    ret i32 [[AND2]]
3904 ;
3905   %and1 = and i32 %b, %a
3906   %not1 = xor i32 %and1, -1
3907   %not2 = xor i32 %a, -1
3908   %or1 = or i32 %not2, %c
3909   %or2 = or i32 %or1, %b
3910   %and2 = and i32 %or2, %not1
3911   call void @use(i32 %not2)
3912   ret i32 %and2
3913 }
3914
3915 define i32 @not_or_or_and_no_and_use5(i32 %a, i32 %b, i32 %c) {
3916 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_use5
3917 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3918 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[A]]
3919 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
3920 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3921 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
3922 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
3923 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[OR2]], [[NOT1]]
3924 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
3925 ; CHECK-NEXT:    ret i32 [[AND2]]
3926 ;
3927   %and1 = and i32 %b, %a
3928   %not1 = xor i32 %and1, -1
3929   %not2 = xor i32 %a, -1
3930   %or1 = or i32 %not2, %b
3931   %or2 = or i32 %or1, %c
3932   %and2 = and i32 %or2, %not1
3933   call void @use(i32 %and1)
3934   ret i32 %and2
3935 }
3936
3937 define i32 @not_or_or_and_no_and_use6(i32 %a, i32 %b, i32 %c) {
3938 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_use6
3939 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3940 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[A]]
3941 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
3942 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3943 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
3944 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
3945 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[OR2]], [[NOT1]]
3946 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
3947 ; CHECK-NEXT:    ret i32 [[AND2]]
3948 ;
3949   %and1 = and i32 %b, %a
3950   %not1 = xor i32 %and1, -1
3951   %not2 = xor i32 %a, -1
3952   %or1 = or i32 %not2, %b
3953   %or2 = or i32 %or1, %c
3954   %and2 = and i32 %or2, %not1
3955   call void @use(i32 %not1)
3956   ret i32 %and2
3957 }
3958
3959 define i32 @not_or_or_and_no_and_use7(i32 %a, i32 %b, i32 %c) {
3960 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_use7
3961 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3962 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3963 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
3964 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
3965 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[C]]
3966 ; CHECK-NEXT:    [[AND2:%.*]] = or i32 [[TMP2]], [[NOT2]]
3967 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
3968 ; CHECK-NEXT:    ret i32 [[AND2]]
3969 ;
3970   %and1 = and i32 %b, %a
3971   %not1 = xor i32 %and1, -1
3972   %not2 = xor i32 %a, -1
3973   %or1 = or i32 %not2, %b
3974   %or2 = or i32 %or1, %c
3975   %and2 = and i32 %or2, %not1
3976   call void @use(i32 %or1)
3977   ret i32 %and2
3978 }
3979
3980 define i32 @not_or_or_and_no_and_use8(i32 %a, i32 %b, i32 %c) {
3981 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_use8
3982 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
3983 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[A]]
3984 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
3985 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
3986 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
3987 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
3988 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[OR2]], [[NOT1]]
3989 ; CHECK-NEXT:    call void @use(i32 [[OR2]])
3990 ; CHECK-NEXT:    ret i32 [[AND2]]
3991 ;
3992   %and1 = and i32 %b, %a
3993   %not1 = xor i32 %and1, -1
3994   %not2 = xor i32 %a, -1
3995   %or1 = or i32 %not2, %b
3996   %or2 = or i32 %or1, %c
3997   %and2 = and i32 %or2, %not1
3998   call void @use(i32 %or2)
3999   ret i32 %and2
4000 }
4001
4002 define i4 @and_orn_xor(i4 %a, i4 %b) {
4003 ; CHECK-LABEL: define {{[^@]+}}@and_orn_xor
4004 ; CHECK-SAME: (i4 [[A:%.*]], i4 [[B:%.*]]) {
4005 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i4 [[A]], -1
4006 ; CHECK-NEXT:    [[R:%.*]] = and i4 [[TMP1]], [[B]]
4007 ; CHECK-NEXT:    ret i4 [[R]]
4008 ;
4009   %xor = xor i4 %a, %b
4010   %nota = xor i4 %a, -1
4011   %or = or i4 %nota, %b
4012   %r = and i4 %or, %xor
4013   ret i4 %r
4014 }
4015
4016 define <2 x i4> @and_orn_xor_commute1(<2 x i4> %a, <2 x i4> %b) {
4017 ; CHECK-LABEL: define {{[^@]+}}@and_orn_xor_commute1
4018 ; CHECK-SAME: (<2 x i4> [[A:%.*]], <2 x i4> [[B:%.*]]) {
4019 ; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i4> [[A]], <i4 -1, i4 -1>
4020 ; CHECK-NEXT:    [[R:%.*]] = and <2 x i4> [[TMP1]], [[B]]
4021 ; CHECK-NEXT:    ret <2 x i4> [[R]]
4022 ;
4023   %xor = xor <2 x i4> %a, %b
4024   %nota = xor <2 x i4> %a, <i4 -1, i4 undef>
4025   %or = or <2 x i4> %nota, %b
4026   %r = and <2 x i4> %xor, %or
4027   ret <2 x i4> %r
4028 }
4029
4030 define i32 @and_orn_xor_commute2(i32 %a, i32 %b) {
4031 ; CHECK-LABEL: define {{[^@]+}}@and_orn_xor_commute2
4032 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
4033 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[B]], [[A]]
4034 ; CHECK-NEXT:    call void @use(i32 [[XOR]])
4035 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], -1
4036 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[TMP1]], [[B]]
4037 ; CHECK-NEXT:    ret i32 [[R]]
4038 ;
4039   %xor = xor i32 %b, %a
4040   call void @use(i32 %xor)
4041   %nota = xor i32 %a, -1
4042   %or = or i32 %nota, %b
4043   %r = and i32 %or, %xor
4044   ret i32 %r
4045 }
4046
4047 define i32 @and_orn_xor_commute3(i32 %a, i32 %b) {
4048 ; CHECK-LABEL: define {{[^@]+}}@and_orn_xor_commute3
4049 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
4050 ; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
4051 ; CHECK-NEXT:    call void @use(i32 [[NOTA]])
4052 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], -1
4053 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[TMP1]], [[B]]
4054 ; CHECK-NEXT:    ret i32 [[R]]
4055 ;
4056   %xor = xor i32 %b, %a
4057   %nota = xor i32 %a, -1
4058   call void @use(i32 %nota)
4059   %or = or i32 %nota, %b
4060   %r = and i32 %xor, %or
4061   ret i32 %r
4062 }
4063
4064 define i32 @and_orn_xor_commute5(i32 %pa, i32 %pb) {
4065 ; CHECK-LABEL: define {{[^@]+}}@and_orn_xor_commute5
4066 ; CHECK-SAME: (i32 [[PA:%.*]], i32 [[PB:%.*]]) {
4067 ; CHECK-NEXT:    [[A:%.*]] = mul i32 [[PA]], [[PA]]
4068 ; CHECK-NEXT:    [[B:%.*]] = mul i32 [[PB]], [[PB]]
4069 ; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
4070 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[B]], [[NOTA]]
4071 ; CHECK-NEXT:    call void @use(i32 [[OR]])
4072 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], -1
4073 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[B]], [[TMP1]]
4074 ; CHECK-NEXT:    ret i32 [[R]]
4075 ;
4076   %a = mul i32 %pa, %pa
4077   %b = mul i32 %pb, %pb
4078   %xor = xor i32 %a, %b
4079   %nota = xor i32 %a, -1
4080   %or = or i32 %b, %nota
4081   call void @use(i32 %or)
4082   %r = and i32 %or, %xor
4083   ret i32 %r
4084 }
4085
4086 define i32 @and_orn_xor_commute6(i32 %pa, i32 %pb) {
4087 ; CHECK-LABEL: define {{[^@]+}}@and_orn_xor_commute6
4088 ; CHECK-SAME: (i32 [[PA:%.*]], i32 [[PB:%.*]]) {
4089 ; CHECK-NEXT:    [[A:%.*]] = mul i32 [[PA]], [[PA]]
4090 ; CHECK-NEXT:    [[B:%.*]] = mul i32 [[PB]], [[PB]]
4091 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[A]], [[B]]
4092 ; CHECK-NEXT:    call void @use(i32 [[XOR]])
4093 ; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
4094 ; CHECK-NEXT:    call void @use(i32 [[NOTA]])
4095 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], -1
4096 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[B]], [[TMP1]]
4097 ; CHECK-NEXT:    ret i32 [[R]]
4098 ;
4099   %a = mul i32 %pa, %pa
4100   %b = mul i32 %pb, %pb
4101   %xor = xor i32 %a, %b
4102   call void @use(i32 %xor)
4103   %nota = xor i32 %a, -1
4104   call void @use(i32 %nota)
4105   %or = or i32 %b, %nota
4106   %r = and i32 %xor, %or
4107   ret i32 %r
4108 }
4109
4110 define i32 @and_orn_xor_commute7(i32 %pa, i32 %pb) {
4111 ; CHECK-LABEL: define {{[^@]+}}@and_orn_xor_commute7
4112 ; CHECK-SAME: (i32 [[PA:%.*]], i32 [[PB:%.*]]) {
4113 ; CHECK-NEXT:    [[A:%.*]] = mul i32 [[PA]], [[PA]]
4114 ; CHECK-NEXT:    [[B:%.*]] = mul i32 [[PB]], [[PB]]
4115 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[B]], [[A]]
4116 ; CHECK-NEXT:    call void @use(i32 [[XOR]])
4117 ; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
4118 ; CHECK-NEXT:    call void @use(i32 [[NOTA]])
4119 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[B]], [[NOTA]]
4120 ; CHECK-NEXT:    call void @use(i32 [[OR]])
4121 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], -1
4122 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[B]], [[TMP1]]
4123 ; CHECK-NEXT:    ret i32 [[R]]
4124 ;
4125   %a = mul i32 %pa, %pa
4126   %b = mul i32 %pb, %pb
4127   %xor = xor i32 %b, %a
4128   call void @use(i32 %xor)
4129   %nota = xor i32 %a, -1
4130   call void @use(i32 %nota)
4131   %or = or i32 %b, %nota
4132   call void @use(i32 %or)
4133   %r = and i32 %or, %xor
4134   ret i32 %r
4135 }
4136
4137 define i32 @and_orn_xor_commute8(i32 %pa, i32 %pb) {
4138 ; CHECK-LABEL: define {{[^@]+}}@and_orn_xor_commute8
4139 ; CHECK-SAME: (i32 [[PA:%.*]], i32 [[PB:%.*]]) {
4140 ; CHECK-NEXT:    [[A:%.*]] = mul i32 [[PA]], [[PA]]
4141 ; CHECK-NEXT:    [[B:%.*]] = mul i32 [[PB]], [[PB]]
4142 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], -1
4143 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[B]], [[TMP1]]
4144 ; CHECK-NEXT:    ret i32 [[R]]
4145 ;
4146   %a = mul i32 %pa, %pa
4147   %b = mul i32 %pb, %pb
4148   %xor = xor i32 %b, %a
4149   %nota = xor i32 %a, -1
4150   %or = or i32 %b, %nota
4151   %r = and i32 %xor, %or
4152   ret i32 %r
4153 }
4154
4155 define i32 @zext_zext_and_uses(i8 %x, i8 %y) {
4156 ; CHECK-LABEL: define {{[^@]+}}@zext_zext_and_uses
4157 ; CHECK-SAME: (i8 [[X:%.*]], i8 [[Y:%.*]]) {
4158 ; CHECK-NEXT:    [[ZX:%.*]] = zext i8 [[X]] to i32
4159 ; CHECK-NEXT:    call void @use(i32 [[ZX]])
4160 ; CHECK-NEXT:    [[ZY:%.*]] = zext i8 [[Y]] to i32
4161 ; CHECK-NEXT:    call void @use(i32 [[ZY]])
4162 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[ZX]], [[ZY]]
4163 ; CHECK-NEXT:    ret i32 [[R]]
4164 ;
4165   %zx = zext i8 %x to i32
4166   call void @use(i32 %zx)
4167   %zy = zext i8 %y to i32
4168   call void @use(i32 %zy)
4169   %r = and i32 %zx, %zy
4170   ret i32 %r
4171 }
4172
4173 define i32 @sext_sext_or_uses(i8 %x, i8 %y) {
4174 ; CHECK-LABEL: define {{[^@]+}}@sext_sext_or_uses
4175 ; CHECK-SAME: (i8 [[X:%.*]], i8 [[Y:%.*]]) {
4176 ; CHECK-NEXT:    [[SX:%.*]] = sext i8 [[X]] to i32
4177 ; CHECK-NEXT:    call void @use(i32 [[SX]])
4178 ; CHECK-NEXT:    [[SY:%.*]] = sext i8 [[Y]] to i32
4179 ; CHECK-NEXT:    call void @use(i32 [[SY]])
4180 ; CHECK-NEXT:    [[R:%.*]] = or i32 [[SX]], [[SY]]
4181 ; CHECK-NEXT:    ret i32 [[R]]
4182 ;
4183   %sx = sext i8 %x to i32
4184   call void @use(i32 %sx)
4185   %sy = sext i8 %y to i32
4186   call void @use(i32 %sy)
4187   %r = or i32 %sx, %sy
4188   ret i32 %r
4189 }
4190
4191 define i32 @trunc_trunc_xor_uses(i65 %x, i65 %y) {
4192 ; CHECK-LABEL: define {{[^@]+}}@trunc_trunc_xor_uses
4193 ; CHECK-SAME: (i65 [[X:%.*]], i65 [[Y:%.*]]) {
4194 ; CHECK-NEXT:    [[SX:%.*]] = trunc i65 [[X]] to i32
4195 ; CHECK-NEXT:    call void @use(i32 [[SX]])
4196 ; CHECK-NEXT:    [[SY:%.*]] = trunc i65 [[Y]] to i32
4197 ; CHECK-NEXT:    call void @use(i32 [[SY]])
4198 ; CHECK-NEXT:    [[R:%.*]] = xor i32 [[SX]], [[SY]]
4199 ; CHECK-NEXT:    ret i32 [[R]]
4200 ;
4201   %sx = trunc i65 %x to i32
4202   call void @use(i32 %sx)
4203   %sy = trunc i65 %y to i32
4204   call void @use(i32 %sy)
4205   %r = xor i32 %sx, %sy
4206   ret i32 %r
4207 }