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

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
   3
   4 declare void @use(i8)
   5 declare void @use_vec(<2 x i8>)
   6
   7 ; ((b | a) & C1) | (b & C2) -> (a & C1) | b iff C1 == ~C2
   8
   9 define i32 @or_and_not_constant_commute0(i32 %a, i32 %b) {
  10 ; CHECK-LABEL: @or_and_not_constant_commute0(
  11 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], 1
  12 ; CHECK-NEXT:    [[T3:%.*]] = or i32 [[TMP1]], [[B:%.*]]
  13 ; CHECK-NEXT:    ret i32 [[T3]]
  14 ;
  15   %t = or i32 %b, %a
  16   %t1 = and i32 %t, 1
  17   %t2 = and i32 %b, -2
  18   %t3 = or i32 %t1, %t2
  19   ret i32 %t3
  20 }
  21
  22 define i32 @or_and_not_constant_commute1(i32 %a, i32 %b) {
  23 ; CHECK-LABEL: @or_and_not_constant_commute1(
  24 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], 1
  25 ; CHECK-NEXT:    [[T3:%.*]] = or i32 [[TMP1]], [[B:%.*]]
  26 ; CHECK-NEXT:    ret i32 [[T3]]
  27 ;
  28   %t = or i32 %a, %b
  29   %t1 = and i32 1, %t
  30   %t2 = and i32 -2, %b
  31   %t3 = or i32 %t1, %t2
  32   ret i32 %t3
  33 }
  34
  35 define i32 @or_and_not_constant_commute2(i32 %a, i32 %b) {
  36 ; CHECK-LABEL: @or_and_not_constant_commute2(
  37 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], 1
  38 ; CHECK-NEXT:    [[T3:%.*]] = or i32 [[TMP1]], [[B:%.*]]
  39 ; CHECK-NEXT:    ret i32 [[T3]]
  40 ;
  41   %t = or i32 %b, %a
  42   %t1 = and i32 %t, 1
  43   %t2 = and i32 %b, -2
  44   %t3 = or i32 %t2, %t1
  45   ret i32 %t3
  46 }
  47
  48 define i32 @or_and_not_constant_commute3(i32 %a, i32 %b) {
  49 ; CHECK-LABEL: @or_and_not_constant_commute3(
  50 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], 1
  51 ; CHECK-NEXT:    [[T3:%.*]] = or i32 [[TMP1]], [[B:%.*]]
  52 ; CHECK-NEXT:    ret i32 [[T3]]
  53 ;
  54   %t = or i32 %a, %b
  55   %t1 = and i32 1, %t
  56   %t2 = and i32 -2, %b
  57   %t3 = or i32 %t2, %t1
  58   ret i32 %t3
  59 }
  60
  61 define <2 x i7> @or_and_not_constant_commute0_splat(<2 x i7> %a, <2 x i7> %b) {
  62 ; CHECK-LABEL: @or_and_not_constant_commute0_splat(
  63 ; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i7> [[A:%.*]], <i7 42, i7 42>
  64 ; CHECK-NEXT:    [[T3:%.*]] = or <2 x i7> [[TMP1]], [[B:%.*]]
  65 ; CHECK-NEXT:    ret <2 x i7> [[T3]]
  66 ;
  67   %t = or <2 x i7> %b, %a
  68   %t1 = and <2 x i7> %t, <i7 42, i7 42>
  69   %t2 = and <2 x i7> %b, <i7 -43, i7 -43>
  70   %t3 = or <2 x i7> %t1, %t2
  71   ret <2 x i7> %t3
  72 }
  73
  74 ; ((x | N) & C1) | (x & C2) --> (x | N) & (C1 | C2)
  75 ; iff (C1 & C2) == 0 and (N & ~C1) == 0
  76
  77 define i8 @or_and_or_commute0(i8 %x) {
  78 ; CHECK-LABEL: @or_and_or_commute0(
  79 ; CHECK-NEXT:    [[XN:%.*]] = or i8 [[X:%.*]], 16
  80 ; CHECK-NEXT:    call void @use(i8 [[XN]])
  81 ; CHECK-NEXT:    [[X1:%.*]] = and i8 [[XN]], 59
  82 ; CHECK-NEXT:    call void @use(i8 [[X1]])
  83 ; CHECK-NEXT:    [[X2:%.*]] = and i8 [[X]], 64
  84 ; CHECK-NEXT:    call void @use(i8 [[X2]])
  85 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[XN]], 123
  86 ; CHECK-NEXT:    ret i8 [[R]]
  87 ;
  88   %xn = or i8 %x, 16   ; 0001_0000
  89   call void @use(i8 %xn)
  90   %x1 = and i8 %xn, 59 ; 0011_1011
  91   call void @use(i8 %x1)
  92   %x2 = and i8 %x, 64  ; 0100_0000
  93   call void @use(i8 %x2)
  94   %r = or i8 %x1, %x2
  95   ret i8 %r
  96 }
  97
  98 define i8 @or_and_or_commute1(i8 %x) {
  99 ; CHECK-LABEL: @or_and_or_commute1(
 100 ; CHECK-NEXT:    [[XN:%.*]] = or i8 [[X:%.*]], 16
 101 ; CHECK-NEXT:    call void @use(i8 [[XN]])
 102 ; CHECK-NEXT:    [[X1:%.*]] = and i8 [[XN]], 59
 103 ; CHECK-NEXT:    call void @use(i8 [[X1]])
 104 ; CHECK-NEXT:    [[X2:%.*]] = and i8 [[X]], 64
 105 ; CHECK-NEXT:    call void @use(i8 [[X2]])
 106 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[XN]], 123
 107 ; CHECK-NEXT:    ret i8 [[R]]
 108 ;
 109   %xn = or i8 %x, 16   ; 0001_0000
 110   call void @use(i8 %xn)
 111   %x1 = and i8 %xn, 59 ; 0011_1011
 112   call void @use(i8 %x1)
 113   %x2 = and i8 %x, 64  ; 0100_0000
 114   call void @use(i8 %x2)
 115   %r = or i8 %x2, %x1
 116   ret i8 %r
 117 }
 118
 119 define <2 x i8> @or_and_or_commute1_splat(<2 x i8> %x) {
 120 ; CHECK-LABEL: @or_and_or_commute1_splat(
 121 ; CHECK-NEXT:    [[XN:%.*]] = or <2 x i8> [[X:%.*]], <i8 16, i8 16>
 122 ; CHECK-NEXT:    call void @use_vec(<2 x i8> [[XN]])
 123 ; CHECK-NEXT:    [[X1:%.*]] = and <2 x i8> [[XN]], <i8 59, i8 59>
 124 ; CHECK-NEXT:    call void @use_vec(<2 x i8> [[X1]])
 125 ; CHECK-NEXT:    [[X2:%.*]] = and <2 x i8> [[X]], <i8 64, i8 64>
 126 ; CHECK-NEXT:    call void @use_vec(<2 x i8> [[X2]])
 127 ; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[XN]], <i8 123, i8 123>
 128 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 129 ;
 130   %xn = or <2 x i8> %x, <i8 16, i8 16>
 131   call void @use_vec(<2 x i8> %xn)
 132   %x1 = and <2 x i8> %xn, <i8 59, i8 59>
 133   call void @use_vec(<2 x i8> %x1)
 134   %x2 = and <2 x i8> %x, <i8 64, i8 64>
 135   call void @use_vec(<2 x i8> %x2)
 136   %r = or <2 x i8> %x2, %x1
 137   ret <2 x i8> %r
 138 }
 139
 140 define i8 @or_and_or_commute2(i8 %x, i8 %y) {
 141 ; CHECK-LABEL: @or_and_or_commute2(
 142 ; CHECK-NEXT:    [[N:%.*]] = lshr i8 [[Y:%.*]], 6
 143 ; CHECK-NEXT:    [[XN:%.*]] = or i8 [[N]], [[X:%.*]]
 144 ; CHECK-NEXT:    call void @use(i8 [[XN]])
 145 ; CHECK-NEXT:    [[X1:%.*]] = and i8 [[XN]], -69
 146 ; CHECK-NEXT:    call void @use(i8 [[X1]])
 147 ; CHECK-NEXT:    [[X2:%.*]] = and i8 [[X]], 64
 148 ; CHECK-NEXT:    call void @use(i8 [[X2]])
 149 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[XN]], -5
 150 ; CHECK-NEXT:    ret i8 [[R]]
 151 ;
 152   %n = lshr i8 %y, 6
 153   %xn = or i8 %n, %x
 154   call void @use(i8 %xn)
 155   %x1 = and i8 %xn, 187
 156   call void @use(i8 %x1)
 157   %x2 = and i8 %x, 64
 158   call void @use(i8 %x2)
 159   %r = or i8 %x1, %x2
 160   ret i8 %r
 161 }
 162
 163 define <2 x i8> @or_and_or_commute2_splat(<2 x i8> %x, <2 x i8> %y) {
 164 ; CHECK-LABEL: @or_and_or_commute2_splat(
 165 ; CHECK-NEXT:    [[N:%.*]] = lshr <2 x i8> [[Y:%.*]], <i8 6, i8 6>
 166 ; CHECK-NEXT:    [[XN:%.*]] = or <2 x i8> [[N]], [[X:%.*]]
 167 ; CHECK-NEXT:    call void @use_vec(<2 x i8> [[XN]])
 168 ; CHECK-NEXT:    [[X1:%.*]] = and <2 x i8> [[XN]], <i8 -69, i8 -69>
 169 ; CHECK-NEXT:    call void @use_vec(<2 x i8> [[X1]])
 170 ; CHECK-NEXT:    [[X2:%.*]] = and <2 x i8> [[X]], <i8 64, i8 64>
 171 ; CHECK-NEXT:    call void @use_vec(<2 x i8> [[X2]])
 172 ; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[XN]], <i8 -5, i8 -5>
 173 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 174 ;
 175   %n = lshr <2 x i8> %y, <i8 6, i8 6>
 176   %xn = or <2 x i8> %n, %x
 177   call void @use_vec(<2 x i8> %xn)
 178   %x1 = and <2 x i8> %xn, <i8 187, i8 187>
 179   call void @use_vec(<2 x i8> %x1)
 180   %x2 = and <2 x i8> %x, <i8 64, i8 64>
 181   call void @use_vec(<2 x i8> %x2)
 182   %r = or <2 x i8> %x1, %x2
 183   ret <2 x i8> %r
 184 }
 185
 186 define i8 @or_and_or_commute3(i8 %x, i8 %y) {
 187 ; CHECK-LABEL: @or_and_or_commute3(
 188 ; CHECK-NEXT:    [[N:%.*]] = lshr i8 [[Y:%.*]], 6
 189 ; CHECK-NEXT:    [[XN:%.*]] = or i8 [[N]], [[X:%.*]]
 190 ; CHECK-NEXT:    call void @use(i8 [[XN]])
 191 ; CHECK-NEXT:    [[X1:%.*]] = and i8 [[XN]], -69
 192 ; CHECK-NEXT:    call void @use(i8 [[X1]])
 193 ; CHECK-NEXT:    [[X2:%.*]] = and i8 [[X]], 64
 194 ; CHECK-NEXT:    call void @use(i8 [[X2]])
 195 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[XN]], -5
 196 ; CHECK-NEXT:    ret i8 [[R]]
 197 ;
 198   %n = lshr i8 %y, 6
 199   %xn = or i8 %n, %x
 200   call void @use(i8 %xn)
 201   %x1 = and i8 %xn, 187
 202   call void @use(i8 %x1)
 203   %x2 = and i8 %x, 64
 204   call void @use(i8 %x2)
 205   %r = or i8 %x2, %x1
 206   ret i8 %r
 207 }
 208
 209 define i8 @or_and2_or2(i8 %x) {
 210 ; CHECK-LABEL: @or_and2_or2(
 211 ; CHECK-NEXT:    [[O1:%.*]] = or i8 [[X:%.*]], 1
 212 ; CHECK-NEXT:    call void @use(i8 [[O1]])
 213 ; CHECK-NEXT:    [[O2:%.*]] = or i8 [[X]], 2
 214 ; CHECK-NEXT:    call void @use(i8 [[O2]])
 215 ; CHECK-NEXT:    [[X1:%.*]] = and i8 [[O1]], -71
 216 ; CHECK-NEXT:    call void @use(i8 [[X1]])
 217 ; CHECK-NEXT:    [[X2:%.*]] = and i8 [[O2]], 66
 218 ; CHECK-NEXT:    call void @use(i8 [[X2]])
 219 ; CHECK-NEXT:    [[BITFIELD:%.*]] = and i8 [[X]], -8
 220 ; CHECK-NEXT:    [[R:%.*]] = or disjoint i8 [[BITFIELD]], 3
 221 ; CHECK-NEXT:    ret i8 [[R]]
 222 ;
 223   %o1 = or i8 %x, 1
 224   call void @use(i8 %o1)
 225   %o2 = or i8 %x, 2
 226   call void @use(i8 %o2)
 227   %x1 = and i8 %o1, 185
 228   call void @use(i8 %x1)
 229   %x2 = and i8 %o2, 66
 230   call void @use(i8 %x2)
 231   %r = or i8 %x1, %x2
 232   ret i8 %r
 233 }
 234
 235 define <2 x i8> @or_and2_or2_splat(<2 x i8> %x) {
 236 ; CHECK-LABEL: @or_and2_or2_splat(
 237 ; CHECK-NEXT:    [[O1:%.*]] = or <2 x i8> [[X:%.*]], <i8 1, i8 1>
 238 ; CHECK-NEXT:    call void @use_vec(<2 x i8> [[O1]])
 239 ; CHECK-NEXT:    [[O2:%.*]] = or <2 x i8> [[X]], <i8 2, i8 2>
 240 ; CHECK-NEXT:    call void @use_vec(<2 x i8> [[O2]])
 241 ; CHECK-NEXT:    [[X1:%.*]] = and <2 x i8> [[O1]], <i8 -71, i8 -71>
 242 ; CHECK-NEXT:    call void @use_vec(<2 x i8> [[X1]])
 243 ; CHECK-NEXT:    [[X2:%.*]] = and <2 x i8> [[O2]], <i8 66, i8 66>
 244 ; CHECK-NEXT:    call void @use_vec(<2 x i8> [[X2]])
 245 ; CHECK-NEXT:    [[BITFIELD:%.*]] = and <2 x i8> [[X]], <i8 -8, i8 -8>
 246 ; CHECK-NEXT:    [[R:%.*]] = or disjoint <2 x i8> [[BITFIELD]], <i8 3, i8 3>
 247 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 248 ;
 249   %o1 = or <2 x i8> %x, <i8 1, i8 1>
 250   call void @use_vec(<2 x i8> %o1)
 251   %o2 = or <2 x i8> %x, <i8 2, i8 2>
 252   call void @use_vec(<2 x i8> %o2)
 253   %x1 = and <2 x i8> %o1, <i8 185, i8 185>
 254   call void @use_vec(<2 x i8> %x1)
 255   %x2 = and <2 x i8> %o2, <i8 66, i8 66>
 256   call void @use_vec(<2 x i8> %x2)
 257   %r = or <2 x i8> %x1, %x2
 258   ret <2 x i8> %r
 259 }
 260
 261 ; Check variants of:
 262 ; and ({x}or X, Y), C --> {x}or X, (and Y, C)
 263 ; ...in the following 5 tests.
 264
 265 define i8 @and_or_hoist_mask(i8 %a, i8 %b) {
 266 ; CHECK-LABEL: @and_or_hoist_mask(
 267 ; CHECK-NEXT:    [[SH:%.*]] = lshr i8 [[A:%.*]], 6
 268 ; CHECK-NEXT:    [[B_MASKED:%.*]] = and i8 [[B:%.*]], 3
 269 ; CHECK-NEXT:    [[AND:%.*]] = or i8 [[SH]], [[B_MASKED]]
 270 ; CHECK-NEXT:    ret i8 [[AND]]
 271 ;
 272   %sh = lshr i8 %a, 6
 273   %or = or i8 %sh, %b
 274   %and = and i8 %or, 3
 275   ret i8 %and
 276 }
 277
 278 define <2 x i8> @and_xor_hoist_mask_vec_splat(<2 x i8> %a, <2 x i8> %b) {
 279 ; CHECK-LABEL: @and_xor_hoist_mask_vec_splat(
 280 ; CHECK-NEXT:    [[SH:%.*]] = lshr <2 x i8> [[A:%.*]], <i8 6, i8 6>
 281 ; CHECK-NEXT:    [[B_MASKED:%.*]] = and <2 x i8> [[B:%.*]], <i8 3, i8 3>
 282 ; CHECK-NEXT:    [[AND:%.*]] = xor <2 x i8> [[SH]], [[B_MASKED]]
 283 ; CHECK-NEXT:    ret <2 x i8> [[AND]]
 284 ;
 285   %sh = lshr <2 x i8> %a, <i8 6, i8 6>
 286   %xor = xor <2 x i8> %sh, %b
 287   %and = and <2 x i8> %xor, <i8 3, i8 3>
 288   ret <2 x i8> %and
 289 }
 290
 291 define i8 @and_xor_hoist_mask_commute(i8 %a, i8 %b) {
 292 ; CHECK-LABEL: @and_xor_hoist_mask_commute(
 293 ; CHECK-NEXT:    [[C:%.*]] = mul i8 [[B:%.*]], 3
 294 ; CHECK-NEXT:    [[SH:%.*]] = lshr i8 [[A:%.*]], 6
 295 ; CHECK-NEXT:    [[C_MASKED:%.*]] = and i8 [[C]], 3
 296 ; CHECK-NEXT:    [[AND:%.*]] = xor i8 [[C_MASKED]], [[SH]]
 297 ; CHECK-NEXT:    ret i8 [[AND]]
 298 ;
 299   %c = mul i8 %b, 43 ; thwart complexity-based ordering
 300   %sh = lshr i8 %a, 6
 301   %xor = xor i8 %c, %sh
 302   %and = and i8 %xor, 3
 303   ret i8 %and
 304 }
 305
 306 define <2 x i8> @and_or_hoist_mask_commute_vec_splat(<2 x i8> %a, <2 x i8> %b) {
 307 ; CHECK-LABEL: @and_or_hoist_mask_commute_vec_splat(
 308 ; CHECK-NEXT:    [[C:%.*]] = mul <2 x i8> [[B:%.*]], <i8 3, i8 3>
 309 ; CHECK-NEXT:    [[SH:%.*]] = lshr <2 x i8> [[A:%.*]], <i8 6, i8 6>
 310 ; CHECK-NEXT:    [[C_MASKED:%.*]] = and <2 x i8> [[C]], <i8 3, i8 3>
 311 ; CHECK-NEXT:    [[AND:%.*]] = or <2 x i8> [[C_MASKED]], [[SH]]
 312 ; CHECK-NEXT:    ret <2 x i8> [[AND]]
 313 ;
 314   %c = mul <2 x i8> %b, <i8 43, i8 43> ; thwart complexity-based ordering
 315   %sh = lshr <2 x i8> %a, <i8 6, i8 6>
 316   %or = or <2 x i8> %c, %sh
 317   %and = and <2 x i8> %or, <i8 3, i8 3>
 318   ret <2 x i8> %and
 319 }
 320
 321 @g = external global i32
 322
 323 define i32 @pr64114_and_xor_hoist_mask_constexpr() {
 324 ; CHECK-LABEL: @pr64114_and_xor_hoist_mask_constexpr(
 325 ; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 ptrtoint (ptr @g to i32), 8
 326 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[LSHR]], 1
 327 ; CHECK-NEXT:    ret i32 [[AND]]
 328 ;
 329   %lshr = lshr i32 ptrtoint (ptr @g to i32), 8
 330   %xor = xor i32 %lshr, ptrtoint (ptr @g to i32)
 331   %and = and i32 %xor, 1
 332   ret i32 %and
 333 }
 334
 335 ; Don't transform if the 'or' has multiple uses because that would increase instruction count.
 336
 337 define i8 @and_or_do_not_hoist_mask(i8 %a, i8 %b) {
 338 ; CHECK-LABEL: @and_or_do_not_hoist_mask(
 339 ; CHECK-NEXT:    [[SH:%.*]] = lshr i8 [[A:%.*]], 6
 340 ; CHECK-NEXT:    [[OR:%.*]] = or i8 [[SH]], [[B:%.*]]
 341 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[OR]], 3
 342 ; CHECK-NEXT:    [[EXTRA_USE_OF_OR:%.*]] = mul i8 [[OR]], [[AND]]
 343 ; CHECK-NEXT:    ret i8 [[EXTRA_USE_OF_OR]]
 344 ;
 345   %sh = lshr i8 %a, 6
 346   %or = or i8 %sh, %b
 347   %and = and i8 %or, 3
 348   %extra_use_of_or = mul i8 %or, %and
 349   ret i8 %extra_use_of_or
 350 }
 351
 352 define i64 @or_or_and_complex(i64 %i) {
 353 ; CHECK-LABEL: @or_or_and_complex(
 354 ; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 [[I:%.*]], 8
 355 ; CHECK-NEXT:    [[TMP2:%.*]] = shl i64 [[I]], 8
 356 ; CHECK-NEXT:    [[TMP3:%.*]] = and i64 [[TMP1]], 71777214294589695
 357 ; CHECK-NEXT:    [[TMP4:%.*]] = and i64 [[TMP2]], -71777214294589696
 358 ; CHECK-NEXT:    [[OR27:%.*]] = or disjoint i64 [[TMP3]], [[TMP4]]
 359 ; CHECK-NEXT:    ret i64 [[OR27]]
 360 ;
 361   %1 = lshr i64 %i, 8
 362   %shl = and i64 %1, 71776119061217280
 363   %2 = shl i64 %i, 8
 364   %shl3 = and i64 %2, -72057594037927936
 365   %or = or i64 %shl, %shl3
 366   %shl6 = and i64 %1, 1095216660480
 367   %or7 = or i64 %or, %shl6
 368   %shl10 = and i64 %2, 280375465082880
 369   %or11 = or i64 %or7, %shl10
 370   %shl14 = and i64 %1, 16711680
 371   %or15 = or i64 %or11, %shl14
 372   %shl18 = and i64 %2, 4278190080
 373   %or19 = or i64 %or15, %shl18
 374   %and21 = and i64 %1, 255
 375   %or23 = or i64 %or19, %and21
 376   %shl26 = and i64 %2, 65280
 377   %or27 = or i64 %or23, %shl26
 378   ret i64 %or27
 379 }
 380
 381 ; (C | (A & D)) | (A & B)
 382 define i8 @or_or_and_noOneUse(i8 %a, i8 %b, i8 %c, i8 %d) {
 383 ; CHECK-LABEL: @or_or_and_noOneUse(
 384 ; CHECK-NEXT:    [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]]
 385 ; CHECK-NEXT:    call void @use(i8 [[AND1]])
 386 ; CHECK-NEXT:    [[AND2:%.*]] = and i8 [[A]], [[D:%.*]]
 387 ; CHECK-NEXT:    call void @use(i8 [[AND2]])
 388 ; CHECK-NEXT:    [[OR1:%.*]] = or i8 [[AND2]], [[C:%.*]]
 389 ; CHECK-NEXT:    call void @use(i8 [[OR1]])
 390 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[OR1]], [[AND1]]
 391 ; CHECK-NEXT:    ret i8 [[OR2]]
 392 ;
 393   %and1 = and i8 %a, %b
 394   call void @use(i8 %and1)
 395   %and2 = and i8 %a, %d
 396   call void @use(i8 %and2)
 397   %or1 = or i8 %c, %and2
 398   call void @use(i8 %or1)
 399   %or2 = or i8 %or1, %and1
 400   ret i8 %or2
 401 }
 402
 403 ; (C | (A & D)) | (A & B)
 404 define i8 @or_or_and_pat1(i8 %a, i8 %b, i8 %c, i8 %d) {
 405 ; CHECK-LABEL: @or_or_and_pat1(
 406 ; CHECK-NEXT:    [[CT:%.*]] = udiv i8 42, [[C:%.*]]
 407 ; CHECK-NEXT:    [[TMP1:%.*]] = or i8 [[D:%.*]], [[B:%.*]]
 408 ; CHECK-NEXT:    [[TMP2:%.*]] = and i8 [[TMP1]], [[A:%.*]]
 409 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[CT]], [[TMP2]]
 410 ; CHECK-NEXT:    ret i8 [[OR2]]
 411 ;
 412   %ct = udiv i8 42, %c ; thwart complexity-based canonicalization
 413   %and1 = and i8 %a, %b
 414   %and2 = and i8 %a, %d
 415   %or1 = or i8 %ct, %and2
 416   %or2 = or i8 %or1, %and1
 417   ret i8 %or2
 418 }
 419
 420 ; (C | (D & A)) | (A & B)
 421 define i8 @or_or_and_pat2(i8 %a, i8 %b, i8 %c, i8 %d) {
 422 ; CHECK-LABEL: @or_or_and_pat2(
 423 ; CHECK-NEXT:    [[CT:%.*]] = udiv i8 42, [[C:%.*]]
 424 ; CHECK-NEXT:    [[AND21:%.*]] = or i8 [[D:%.*]], [[B:%.*]]
 425 ; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[AND21]], [[A:%.*]]
 426 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[CT]], [[TMP1]]
 427 ; CHECK-NEXT:    ret i8 [[OR2]]
 428 ;
 429   %ct = udiv i8 42, %c ; thwart complexity-based canonicalization
 430   %and1 = and i8 %a, %b
 431   %and2 = and i8 %d, %a
 432   %or1 = or i8 %ct, %and2
 433   %or2 = or i8 %or1, %and1
 434   ret i8 %or2
 435 }
 436
 437 ; (C | (B & D)) | (A & B)
 438 define i8 @or_or_and_pat3(i8 %a, i8 %b, i8 %c, i8 %d) {
 439 ; CHECK-LABEL: @or_or_and_pat3(
 440 ; CHECK-NEXT:    [[CT:%.*]] = udiv i8 42, [[C:%.*]]
 441 ; CHECK-NEXT:    [[TMP1:%.*]] = or i8 [[D:%.*]], [[A:%.*]]
 442 ; CHECK-NEXT:    [[TMP2:%.*]] = and i8 [[TMP1]], [[B:%.*]]
 443 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[CT]], [[TMP2]]
 444 ; CHECK-NEXT:    ret i8 [[OR2]]
 445 ;
 446   %ct = udiv i8 42, %c ; thwart complexity-based canonicalization
 447   %and1 = and i8 %a, %b
 448   %and2 = and i8 %b, %d
 449   %or1 = or i8 %ct, %and2
 450   %or2 = or i8 %or1, %and1
 451   ret i8 %or2
 452 }
 453
 454 ; (C | (D & B)) | (A & B)
 455 define i8 @or_or_and_pat4(i8 %a, i8 %b, i8 %c, i8 %d) {
 456 ; CHECK-LABEL: @or_or_and_pat4(
 457 ; CHECK-NEXT:    [[CT:%.*]] = udiv i8 42, [[C:%.*]]
 458 ; CHECK-NEXT:    [[AND21:%.*]] = or i8 [[D:%.*]], [[A:%.*]]
 459 ; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[AND21]], [[B:%.*]]
 460 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[CT]], [[TMP1]]
 461 ; CHECK-NEXT:    ret i8 [[OR2]]
 462 ;
 463   %ct = udiv i8 42, %c ; thwart complexity-based canonicalization
 464   %and1 = and i8 %a, %b
 465   %and2 = and i8 %d, %b
 466   %or1 = or i8 %ct, %and2
 467   %or2 = or i8 %or1, %and1
 468   ret i8 %or2
 469 }
 470
 471 ; ((A & D) | C) | (A & B)
 472 define i8 @or_or_and_pat5(i8 %a, i8 %b, i8 %c, i8 %d) {
 473 ; CHECK-LABEL: @or_or_and_pat5(
 474 ; CHECK-NEXT:    [[TMP1:%.*]] = or i8 [[D:%.*]], [[B:%.*]]
 475 ; CHECK-NEXT:    [[TMP2:%.*]] = and i8 [[TMP1]], [[A:%.*]]
 476 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[TMP2]], [[C:%.*]]
 477 ; CHECK-NEXT:    ret i8 [[OR2]]
 478 ;
 479   %and1 = and i8 %a, %b
 480   %and2 = and i8 %a, %d
 481   %or1 = or i8 %and2, %c
 482   %or2 = or i8 %or1, %and1
 483   ret i8 %or2
 484 }
 485
 486 ; ((D & A) | C) | (A & B)
 487 define i8 @or_or_and_pat6(i8 %a, i8 %b, i8 %c, i8 %d) {
 488 ; CHECK-LABEL: @or_or_and_pat6(
 489 ; CHECK-NEXT:    [[AND21:%.*]] = or i8 [[D:%.*]], [[B:%.*]]
 490 ; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[AND21]], [[A:%.*]]
 491 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[TMP1]], [[C:%.*]]
 492 ; CHECK-NEXT:    ret i8 [[OR2]]
 493 ;
 494   %and1 = and i8 %a, %b
 495   %and2 = and i8 %d, %a
 496   %or1 = or i8 %and2, %c
 497   %or2 = or i8 %or1, %and1
 498   ret i8 %or2
 499 }
 500
 501 ; ((B & D) | C) | (A & B)
 502 define i8 @or_or_and_pat7(i8 %a, i8 %b, i8 %c, i8 %d) {
 503 ; CHECK-LABEL: @or_or_and_pat7(
 504 ; CHECK-NEXT:    [[TMP1:%.*]] = or i8 [[D:%.*]], [[A:%.*]]
 505 ; CHECK-NEXT:    [[TMP2:%.*]] = and i8 [[TMP1]], [[B:%.*]]
 506 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[TMP2]], [[C:%.*]]
 507 ; CHECK-NEXT:    ret i8 [[OR2]]
 508 ;
 509   %and1 = and i8 %a, %b
 510   %and2 = and i8 %b, %d
 511   %or1 = or i8 %and2, %c
 512   %or2 = or i8 %or1, %and1
 513   ret i8 %or2
 514 }
 515
 516 ; ((D & B) | C) | (A & B)
 517 define i8 @or_or_and_pat8(i8 %a, i8 %b, i8 %c, i8 %d) {
 518 ; CHECK-LABEL: @or_or_and_pat8(
 519 ; CHECK-NEXT:    [[AND21:%.*]] = or i8 [[D:%.*]], [[A:%.*]]
 520 ; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[AND21]], [[B:%.*]]
 521 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[TMP1]], [[C:%.*]]
 522 ; CHECK-NEXT:    ret i8 [[OR2]]
 523 ;
 524   %and1 = and i8 %a, %b
 525   %and2 = and i8 %d, %b
 526   %or1 = or i8 %and2, %c
 527   %or2 = or i8 %or1, %and1
 528   ret i8 %or2
 529 }
 530
 531 ; (A & B) | (C | (A & D))
 532 define i8 @or_and_or_noOneUse(i8 %a, i8 %b, i8 %c, i8 %d) {
 533 ; CHECK-LABEL: @or_and_or_noOneUse(
 534 ; CHECK-NEXT:    [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]]
 535 ; CHECK-NEXT:    call void @use(i8 [[AND1]])
 536 ; CHECK-NEXT:    [[AND2:%.*]] = and i8 [[A]], [[D:%.*]]
 537 ; CHECK-NEXT:    call void @use(i8 [[AND2]])
 538 ; CHECK-NEXT:    [[OR1:%.*]] = or i8 [[AND2]], [[C:%.*]]
 539 ; CHECK-NEXT:    call void @use(i8 [[OR1]])
 540 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[AND1]], [[OR1]]
 541 ; CHECK-NEXT:    ret i8 [[OR2]]
 542 ;
 543   %and1 = and i8 %a, %b
 544   call void @use(i8 %and1)
 545   %and2 = and i8 %a, %d
 546   call void @use(i8 %and2)
 547   %or1 = or i8 %c, %and2
 548   call void @use(i8 %or1)
 549   %or2 = or i8 %and1, %or1
 550   ret i8 %or2
 551 }
 552
 553 ; (A & B) | (C | (A & D))
 554 define i8 @or_and_or_pat1(i8 %a, i8 %b, i8 %c, i8 %d) {
 555 ; CHECK-LABEL: @or_and_or_pat1(
 556 ; CHECK-NEXT:    [[CT:%.*]] = udiv i8 42, [[C:%.*]]
 557 ; CHECK-NEXT:    [[TMP1:%.*]] = or i8 [[D:%.*]], [[B:%.*]]
 558 ; CHECK-NEXT:    [[TMP2:%.*]] = and i8 [[TMP1]], [[A:%.*]]
 559 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[CT]], [[TMP2]]
 560 ; CHECK-NEXT:    ret i8 [[OR2]]
 561 ;
 562   %ct = udiv i8 42, %c ; thwart complexity-based canonicalization
 563   %and1 = and i8 %a, %b
 564   %and2 = and i8 %a, %d
 565   %or1 = or i8 %ct, %and2
 566   %or2 = or i8 %and1, %or1
 567   ret i8 %or2
 568 }
 569
 570 ; (A & B) | (C | (D & A))
 571 define i8 @or_and_or_pat2(i8 %a, i8 %b, i8 %c, i8 %d) {
 572 ; CHECK-LABEL: @or_and_or_pat2(
 573 ; CHECK-NEXT:    [[CT:%.*]] = udiv i8 42, [[C:%.*]]
 574 ; CHECK-NEXT:    [[AND21:%.*]] = or i8 [[D:%.*]], [[B:%.*]]
 575 ; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[AND21]], [[A:%.*]]
 576 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[CT]], [[TMP1]]
 577 ; CHECK-NEXT:    ret i8 [[OR2]]
 578 ;
 579   %ct = udiv i8 42, %c ; thwart complexity-based canonicalization
 580   %and1 = and i8 %a, %b
 581   %and2 = and i8 %d, %a
 582   %or1 = or i8 %ct, %and2
 583   %or2 = or i8 %and1, %or1
 584   ret i8 %or2
 585 }
 586
 587 ; (A & B) | (C | (B & D))
 588 define i8 @or_and_or_pat3(i8 %a, i8 %b, i8 %c, i8 %d) {
 589 ; CHECK-LABEL: @or_and_or_pat3(
 590 ; CHECK-NEXT:    [[CT:%.*]] = udiv i8 42, [[C:%.*]]
 591 ; CHECK-NEXT:    [[TMP1:%.*]] = or i8 [[D:%.*]], [[A:%.*]]
 592 ; CHECK-NEXT:    [[TMP2:%.*]] = and i8 [[TMP1]], [[B:%.*]]
 593 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[CT]], [[TMP2]]
 594 ; CHECK-NEXT:    ret i8 [[OR2]]
 595 ;
 596   %ct = udiv i8 42, %c ; thwart complexity-based canonicalization
 597   %and1 = and i8 %a, %b
 598   %and2 = and i8 %b, %d
 599   %or1 = or i8 %ct, %and2
 600   %or2 = or i8 %and1, %or1
 601   ret i8 %or2
 602 }
 603
 604 ; (A & B) | (C | (D & B))
 605 define i8 @or_and_or_pat4(i8 %a, i8 %b, i8 %c, i8 %d) {
 606 ; CHECK-LABEL: @or_and_or_pat4(
 607 ; CHECK-NEXT:    [[CT:%.*]] = udiv i8 42, [[C:%.*]]
 608 ; CHECK-NEXT:    [[AND21:%.*]] = or i8 [[D:%.*]], [[A:%.*]]
 609 ; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[AND21]], [[B:%.*]]
 610 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[CT]], [[TMP1]]
 611 ; CHECK-NEXT:    ret i8 [[OR2]]
 612 ;
 613   %ct = udiv i8 42, %c ; thwart complexity-based canonicalization
 614   %and1 = and i8 %a, %b
 615   %and2 = and i8 %d, %b
 616   %or1 = or i8 %ct, %and2
 617   %or2 = or i8 %and1, %or1
 618   ret i8 %or2
 619 }
 620
 621 ; (A & B) | ((A & D) | C)
 622 define i8 @or_and_or_pat5(i8 %a, i8 %b, i8 %c, i8 %d) {
 623 ; CHECK-LABEL: @or_and_or_pat5(
 624 ; CHECK-NEXT:    [[TMP1:%.*]] = or i8 [[D:%.*]], [[B:%.*]]
 625 ; CHECK-NEXT:    [[TMP2:%.*]] = and i8 [[TMP1]], [[A:%.*]]
 626 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[TMP2]], [[C:%.*]]
 627 ; CHECK-NEXT:    ret i8 [[OR2]]
 628 ;
 629   %and1 = and i8 %a, %b
 630   %and2 = and i8 %a, %d
 631   %or1 = or i8 %and2, %c
 632   %or2 = or i8 %and1, %or1
 633   ret i8 %or2
 634 }
 635
 636 ; (A & B) | ((D & A) | C)
 637 define i8 @or_and_or_pat6(i8 %a, i8 %b, i8 %c, i8 %d) {
 638 ; CHECK-LABEL: @or_and_or_pat6(
 639 ; CHECK-NEXT:    [[AND21:%.*]] = or i8 [[D:%.*]], [[B:%.*]]
 640 ; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[AND21]], [[A:%.*]]
 641 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[TMP1]], [[C:%.*]]
 642 ; CHECK-NEXT:    ret i8 [[OR2]]
 643 ;
 644   %and1 = and i8 %a, %b
 645   %and2 = and i8 %d, %a
 646   %or1 = or i8 %and2, %c
 647   %or2 = or i8 %and1, %or1
 648   ret i8 %or2
 649 }
 650
 651 ; (A & B) | ((B & D) | C)
 652 define i8 @or_and_or_pat7(i8 %a, i8 %b, i8 %c, i8 %d) {
 653 ; CHECK-LABEL: @or_and_or_pat7(
 654 ; CHECK-NEXT:    [[TMP1:%.*]] = or i8 [[D:%.*]], [[A:%.*]]
 655 ; CHECK-NEXT:    [[TMP2:%.*]] = and i8 [[TMP1]], [[B:%.*]]
 656 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[TMP2]], [[C:%.*]]
 657 ; CHECK-NEXT:    ret i8 [[OR2]]
 658 ;
 659   %and1 = and i8 %a, %b
 660   %and2 = and i8 %b, %d
 661   %or1 = or i8 %and2, %c
 662   %or2 = or i8 %and1, %or1
 663   ret i8 %or2
 664 }
 665
 666 ; (A & B) | ((D & B) | C)
 667 define i8 @or_and_or_pat8(i8 %a, i8 %b, i8 %c, i8 %d) {
 668 ; CHECK-LABEL: @or_and_or_pat8(
 669 ; CHECK-NEXT:    [[AND21:%.*]] = or i8 [[D:%.*]], [[A:%.*]]
 670 ; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[AND21]], [[B:%.*]]
 671 ; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[TMP1]], [[C:%.*]]
 672 ; CHECK-NEXT:    ret i8 [[OR2]]
 673 ;
 674   %and1 = and i8 %a, %b
 675   %and2 = and i8 %d, %b
 676   %or1 = or i8 %and2, %c
 677   %or2 = or i8 %and1, %or1
 678   ret i8 %or2
 679 }
 680
 681 declare void @use2(i32)
 682
 683 define i32 @or_or_and_noOneUse_fail1(i32 %a, i32 %b) {
 684 ; CHECK-LABEL: @or_or_and_noOneUse_fail1(
 685 ; CHECK-NEXT:    [[SHR:%.*]] = ashr i32 [[A:%.*]], 23
 686 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHR]], 157
 687 ; CHECK-NEXT:    call void @use2(i32 [[AND]])
 688 ; CHECK-NEXT:    [[AND1:%.*]] = or i32 [[B:%.*]], 157
 689 ; CHECK-NEXT:    [[OR:%.*]] = and i32 [[SHR]], [[AND1]]
 690 ; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[B]], 23
 691 ; CHECK-NEXT:    [[AND9:%.*]] = and i32 [[TMP1]], 157
 692 ; CHECK-NEXT:    [[R:%.*]] = or i32 [[OR]], [[AND9]]
 693 ; CHECK-NEXT:    ret i32 [[R]]
 694 ;
 695   %shr = ashr i32 %a, 23
 696   %conv = trunc i32 %shr to i8
 697   %conv1 = zext i8 %conv to i32
 698   %and = and i32 %conv1, 925
 699   call void @use2(i32 %and)
 700   %and3 = and i32 %shr, %b
 701   %or = or i32 %and3, %and
 702   %shr8 = ashr i32 %b, 23
 703   %and9 = and i32 %shr8, 157
 704   %r = or i32 %or, %and9
 705   ret i32 %r
 706 }
 707
 708 define { i1, i1, i1, i1, i1 } @or_or_and_noOneUse_fail2(i1 %a_0, i1 %a_1, i1 %a_2, i1 %a_3, i1 %b_0, i1 %b_1, i1 %b_2, i1 %b_3) {
 709 ; CHECK-LABEL: @or_or_and_noOneUse_fail2(
 710 ; CHECK-NEXT:  entry:
 711 ; CHECK-NEXT:    [[TMP0:%.*]] = and i1 [[A_0:%.*]], [[B_0:%.*]]
 712 ; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[A_3:%.*]], [[B_3:%.*]]
 713 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i1 [[A_2:%.*]], [[B_2:%.*]]
 714 ; CHECK-NEXT:    [[TMP3:%.*]] = and i1 [[A_1:%.*]], [[B_1:%.*]]
 715 ; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP3]], true
 716 ; CHECK-NEXT:    [[TMP5:%.*]] = and i1 [[TMP0]], [[A_1]]
 717 ; CHECK-NEXT:    [[TMP6:%.*]] = or i1 [[TMP2]], [[A_1]]
 718 ; CHECK-NEXT:    [[TMP7:%.*]] = and i1 [[TMP6]], [[B_1]]
 719 ; CHECK-NEXT:    [[D:%.*]] = or i1 [[TMP7]], [[TMP5]]
 720 ; CHECK-NEXT:    [[DOTNOT1:%.*]] = or i1 [[TMP1]], [[TMP3]]
 721 ; CHECK-NEXT:    [[TMP8:%.*]] = insertvalue { i1, i1, i1, i1, i1 } zeroinitializer, i1 [[D]], 0
 722 ; CHECK-NEXT:    [[TMP9:%.*]] = insertvalue { i1, i1, i1, i1, i1 } [[TMP8]], i1 [[TMP4]], 1
 723 ; CHECK-NEXT:    [[TMP10:%.*]] = insertvalue { i1, i1, i1, i1, i1 } [[TMP9]], i1 true, 2
 724 ; CHECK-NEXT:    [[TMP11:%.*]] = insertvalue { i1, i1, i1, i1, i1 } [[TMP10]], i1 [[A_3]], 3
 725 ; CHECK-NEXT:    [[TMP12:%.*]] = insertvalue { i1, i1, i1, i1, i1 } [[TMP11]], i1 [[DOTNOT1]], 4
 726 ; CHECK-NEXT:    ret { i1, i1, i1, i1, i1 } [[TMP12]]
 727 ;
 728 entry:
 729   %0 = and i1 %a_0, %b_0
 730   %1 = and i1 %a_3, %b_3
 731   %2 = xor i1 %a_2, %b_2
 732   %3 = and i1 %a_1, %b_1
 733   %4 = xor i1 %3, true
 734   %5 = and i1 %0, %a_1
 735   %6 = and i1 %2, %b_1
 736   %7 = or i1 %3, %6
 737   %d = or i1 %7, %5
 738   %8 = xor i1 %d, true
 739   %9 = xor i1 %8, true
 740   %10 = xor i1 %1, true
 741   %11 = and i1 %10, %4
 742   %12 = xor i1 %11, true
 743   %13 = insertvalue { i1, i1, i1, i1, i1 } zeroinitializer, i1 %9, 0
 744   %14 = insertvalue { i1, i1, i1, i1, i1 } %13, i1 %4, 1
 745   %15 = insertvalue { i1, i1, i1, i1, i1 } %14, i1 true, 2
 746   %16 = insertvalue { i1, i1, i1, i1, i1 } %15, i1 %a_3, 3
 747   %17 = insertvalue { i1, i1, i1, i1, i1 } %16, i1 %12, 4
 748   ret { i1, i1, i1, i1, i1 } %17
 749 }