[InstCombine] Apply binary operator simplifications to associative/commutative cases.

[hjyamauchi]

Summary

Apply the instruction combiner binary operator simplifications to the
associative/commutative cases. For example, if we have "(A op B) op C", we try
to transform it to "A op (B op C)" and try to simplify the "(B op C)" part (even
when "(B op C)" doesn't fold to a constant).

A motivation example is a bit-check combining simplification like

((A & 1) == 0) && ((A & 2) == 0) && ((A & 4) == 0) &&
((B & 1) == 0) && ((B & 2) == 0) && ((B & 4) == 0)

-->

((A & 7) == 0) && ((B & 7) == 0)

which didn't fully happen previously.

[lebedev.ri]

test/Transforms/InstCombine/bit-check-combine.ll

2

1. Please use ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2. I was under impression that handling of bitchecks was being moved to aggressiveinstcombine.

[spatel]

I think part of this has already landed with:
rL331311

There are proposals trying to do reassociation in a more complete way outside of instcombine:
D45842 (this would catch the cases that I recently added to and-xor-or.ll)
D41574

This is a response to discussions on llvm-dev that instcombine is already trying to do too much. This patch goes against that idea.

[hjyamauchi]

Used utils/update_test_checks.py for bit-check-combine.ll.

[hjyamauchi]

Rebased.

[hjyamauchi]

In D46336#1085279, @spatel wrote:

I think part of this has already landed with:
rL331311

There are proposals trying to do reassociation in a more complete way outside of instcombine:
D45842 (this would catch the cases that I recently added to and-xor-or.ll)
D41574

This is a response to discussions on llvm-dev that instcombine is already trying to do too much. This patch goes against that idea.

Looks like some related issues are being looked into.

Where’s this discussion, and what’s the concern? Compile time?

[spatel]

In D46336#1085843, @yamauchi wrote:

In D46336#1085279, @spatel wrote:

I think part of this has already landed with:
rL331311

There are proposals trying to do reassociation in a more complete way outside of instcombine:
D45842 (this would catch the cases that I recently added to and-xor-or.ll)
D41574

This is a response to discussions on llvm-dev that instcombine is already trying to do too much. This patch goes against that idea.

Looks like some related issues are being looked into.

I think you'll find PR37098 ( https://bugs.llvm.org/show_bug.cgi?id=37098 ) covers several of the same issues you'd like to solve.

Where’s this discussion, and what’s the concern? Compile time?

Compile-time and general bloat of instcombine because it has no limits. Here's one link:
http://lists.llvm.org/pipermail/llvm-dev/2017-May/113184.html

There's no chance that I can explain this better than @dberlin - in fact, see comments from earlier today in D44626
Sorry for the cc, Daniel...but there's a chance you're in the same room/building? :)

[hjyamauchi]

In D46336#1085279, @spatel wrote:

I think part of this has already landed with:
rL331311

What's 'this'? I am not clear how rL331311 (partially?) helps with the bitcheck combining this patch is aiming for. Do you mean a similar approach could be taken?

[hjyamauchi]

FWIW, a nice thing is that this patch doesn't need to recognize and combine some specific patterns (eg. bitchecks, FoldPHIArgOrIntoPHI (D44626) or and-or-lshr (D45986)) or use some reassociation/canonicalization rules/orders based on some specific patterns (eg. some binops that operate on the same value for bitchecks, a certain definition of “matching pair” like D45842 or the ranking in the reassociate pass) (and those orders might conflict among them).

Rather, it applies the same instcombine simplification logic to the (previously-unexplored, alternative) associative/commutative positions of a binary operator as that to the original position, one associative/commutative opportunity at a time at the existing points in SimplifyAssociativeOrCommutative() and doesn’t require walking an entire subtree of instructions to find patterns or limiting the scope down to an artificially fixed size due to a compile time concern.

[hjyamauchi]

Re: bloat, is the consensus that we just don't add to instcombine any more?

This thread http://lists.llvm.org/pipermail/llvm-dev/2017-July/115398.html seemed to have concluded that it’s still acceptable to add to instcombine?

If instcombine is going to be split into multiple passes, assuming we can't call instcombine simplification routines from another pass (unlike instsimplify), could we end up with a situation where we would need to run another pass and instcombine in turn multiple times until a fix point? I'm not sure if any of the extra things that are currently (or proposed to be) part of instcombine are in fact like this and is in instcombine because of this. For example, factorization may open up new other instcombine opportunities, which in turn opens up more factorization opportunities, etc. Anyhow, it seems non-trivial.

[spatel]

In D46336#1087038, @yamauchi wrote:

In D46336#1085279, @spatel wrote:

I think part of this has already landed with:
rL331311

What's 'this'? I am not clear how rL331311 (partially?) helps with the bitcheck combining this patch is aiming for. Do you mean a similar approach could be taken?

I was assuming from the name of this and similar tests:
"bit-check-combine1"
that 'this' was looking for any-bit-set / any-bit-clear / all-bits-set / all-bits-clear. Maybe the patterns you're looking for don't look like what I am matching though? If I run -instcombine on the first test, it is already substantially reduced...and at that point, it just looks like a problem for -reassociation?

define i1 @bit-check-combine1(i32 %a, i32 %b) {
entry:
  %0 = and i32 %b, 8
  %1 = and i32 %b, 16
  %2 = and i32 %b, 32
  %3 = and i32 %a, 7   <--- we got lucky on this one and found the reduction
  %4 = or i32 %3, %0
  %5 = or i32 %4, %1    <--- reassociate the 'or' operands, so we can factor out the mask ops
  %6 = or i32 %5, %2
  %7 = icmp eq i32 %6, 0
  ret i1 %7
}

[spatel]

In D46336#1087159, @yamauchi wrote:

Re: bloat, is the consensus that we just don't add to instcombine any more?

This thread http://lists.llvm.org/pipermail/llvm-dev/2017-July/115398.html seemed to have concluded that it’s still acceptable to add to instcombine?

Thanks for finding that thread...somehow I find it difficult to search llvm-dev history...
Yes, I think we can still add to instcombine, but I am skeptical of large changes like this that alter the run loop. It doesn't fit in the spirit of small, constant-time combining.

If instcombine is going to be split into multiple passes, assuming we can't call instcombine simplification routines from another pass (unlike instsimplify), could we end up with a situation where we would need to run another pass and instcombine in turn multiple times until a fix point? I'm not sure if any of the extra things that are currently (or proposed to be) part of instcombine are in fact like this and is in instcombine because of this. For example, factorization may open up new other instcombine opportunities, which in turn opens up more factorization opportunities, etc. Anyhow, it seems non-trivial.

I agree that it's not always clear (and note that I posted an alternative version of D45842 in PR37098 that would do more reassociation in instcombine...it would be easier!).

I share your goal of getting these folds to occur, but I'm not an authority on anything, so I think you should raise this discussion on llvm-dev to get a better answer.

[lebedev.ri]

Having looked through D45842, i find this differential rather more complex.
Maybe instcombine shouldn't be doing this..

It would be interesting to know which of these testcase *aren't* handled by D45842.

[hjyamauchi]

In D46336#1087866, @spatel wrote:

In D46336#1087038, @yamauchi wrote:

In D46336#1085279, @spatel wrote:

I think part of this has already landed with:
rL331311

What's 'this'? I am not clear how rL331311 (partially?) helps with the bitcheck combining this patch is aiming for. Do you mean a similar approach could be taken?

I was assuming from the name of this and similar tests:
"bit-check-combine1"
that 'this' was looking for any-bit-set / any-bit-clear / all-bits-set / all-bits-clear. Maybe the patterns you're looking for don't look like what I am matching though? If I run -instcombine on the first test, it is already substantially reduced...and at that point, it just looks like a problem for -reassociation?

define i1 @bit-check-combine1(i32 %a, i32 %b) {
entry:
  %0 = and i32 %b, 8
  %1 = and i32 %b, 16
  %2 = and i32 %b, 32
  %3 = and i32 %a, 7   <--- we got lucky on this one and found the reduction
  %4 = or i32 %3, %0
  %5 = or i32 %4, %1    <--- reassociate the 'or' operands, so we can factor out the mask ops
  %6 = or i32 %5, %2
  %7 = icmp eq i32 %6, 0
  ret i1 %7
}

rL331311 seemed about folding a chain of or-shifts. How does it directly help with bit checks? That was my question.

As my above comment at Thu, May 3, 3:12 PM went, this patch doesn't look for the bit check pattern (or any other pattern) but indirectly promotes the bit check combining by triggering the instcombine folding for the associative/commutative positions of binops. The actual bit check combining is handled by foldLogOpOfMaskedICmps().

Based on the following description of the reassociation pass (-reassociation), I'm not sure if it's an issue specifically with it.

https://llvm.org/docs/Passes.html#reassociate-reassociate-expressions

This pass reassociates commutative expressions in an order that is designed to promote better constant propagation, GCSE, LICM, PRE, etc.

For example: 4 + (x + 5) ⇒ x + (4 + 5)

In the implementation of this algorithm, constants are assigned rank = 0, function arguments are rank = 1, and other values are assigned ranks corresponding to the reverse post order traversal of current function (starting at 2), which effectively gives values in deep loops higher rank than values not in loops.

[hjyamauchi]

Thanks for finding that thread...somehow I find it difficult to search llvm-dev history...

No problem. It was in my email archives.

I agree that it's not always clear (and note that I posted an alternative version of D45842 in PR37098 that would do more reassociation in instcombine...it would be easier!).

Maybe I do not see the full context of PR37098 but I wonder if there was an actual objection to the instcombine version of D45842.

[hjyamauchi]

In D46336#1089012, @lebedev.ri wrote:

Having looked through D45842, i find this differential rather more complex.
Maybe instcombine shouldn't be doing this..

It would be interesting to know which of these testcase *aren't* handled by D45842.

Input:

define i1 @bit-check-combine1(i32 %a, i32 %b) {
entry:
  %0 = and i32 %a, 1
  %1 = icmp eq i32 %0, 0
  %2 = and i32 %a, 2
  %3 = icmp eq i32 %2, 0
  %4 = and i32 %a, 4
  %5 = icmp eq i32 %4, 0
  %6 = and i32 %b, 8
  %7 = icmp eq i32 %6, 0
  %8 = and i32 %b, 16
  %9 = icmp eq i32 %8, 0
  %10 = and i32 %b, 32
  %11 = icmp eq i32 %10, 0
  %12 = and i1 %1, %3
  %13 = and i1 %12, %5
  %14 = and i1 %13, %7
  %15 = and i1 %14, %9
  %16 = and i1 %15, %11
  ret i1 %16
}

After -instcombine (no patch)

define i1 @bit-check-combine1(i32 %a, i32 %b) {
entry:
  %0 = and i32 %b, 8
  %1 = and i32 %b, 16
  %2 = and i32 %b, 32
  %3 = and i32 %a, 7
  %4 = or i32 %3, %0
  %5 = or i32 %4, %1
  %6 = or i32 %5, %2
  %7 = icmp eq i32 %6, 0
  ret i1 %7
}

After -instcombine, with this patch

define i1 @bit-check-combine1(i32 %a, i32 %b) {
entry:
  %0 = and i32 %a, 7
  %1 = and i32 %b, 56
  %2 = or i32 %0, %1
  %3 = icmp eq i32 %2, 0
  ret i1 %3
}

After -instcombine, with D45842

define i1 @bit-check-combine1(i32 %a, i32 %b) {
entry:
  %0 = and i32 %b, 8
  %1 = and i32 %b, 16
  %2 = and i32 %b, 32
  %3 = and i32 %a, 7
  %4 = or i32 %3, %0
  %5 = or i32 %4, %1
  %6 = or i32 %5, %2
  %7 = icmp eq i32 %6, 0
  ret i1 %7
}

After -instcombine -reassociate, with D45842

define i1 @bit-check-combine1(i32 %a, i32 %b) {
entry:
  %0 = and i32 %b, 8
  %1 = and i32 %b, 16
  %2 = and i32 %b, 32
  %3 = and i32 %a, 7
  %4 = or i32 %0, %3
  %5 = or i32 %1, %2
  %6 = or i32 %5, %4
  %7 = icmp eq i32 %6, 0
  ret i1 %7
}

After -instcombine -reassociate -instcombine, with D45842

define i1 @bit-check-combine1(i32 %a, i32 %b) {
entry:
  %0 = and i32 %b, 8
  %1 = and i32 %a, 7
  %2 = or i32 %0, %1
  %3 = and i32 %b, 48
  %4 = or i32 %3, %2
  %5 = icmp eq i32 %4, 0
  ret i1 %5
}

[lebedev.ri]

In D46336#1090588, @yamauchi wrote:

In D46336#1089012, @lebedev.ri wrote:

Having looked through D45842, i find this differential rather more complex.
Maybe instcombine shouldn't be doing this..

It would be interesting to know which of these testcase *aren't* handled by D45842.

Input:

define i1 @bit-check-combine1(i32 %a, i32 %b) {
entry:
  %0 = and i32 %a, 1
  %1 = icmp eq i32 %0, 0
  %2 = and i32 %a, 2
  %3 = icmp eq i32 %2, 0
  %4 = and i32 %a, 4
  %5 = icmp eq i32 %4, 0
  %6 = and i32 %b, 8
  %7 = icmp eq i32 %6, 0
  %8 = and i32 %b, 16
  %9 = icmp eq i32 %8, 0
  %10 = and i32 %b, 32
  %11 = icmp eq i32 %10, 0
  %12 = and i1 %1, %3
  %13 = and i1 %12, %5
  %14 = and i1 %13, %7
  %15 = and i1 %14, %9
  %16 = and i1 %15, %11
  ret i1 %16
}

...

After -instcombine -reassociate -instcombine, with D45842

define i1 @bit-check-combine1(i32 %a, i32 %b) {
entry:
  %0 = and i32 %b, 8
  %1 = and i32 %a, 7
  %2 = or i32 %0, %1
  %3 = and i32 %b, 48
  %4 = or i32 %3, %2
  %5 = icmp eq i32 %4, 0
  ret i1 %5
}

.. and if you run -reassociate -instcombine once more?

[hjyamauchi]

After -instcombine -reassociate -instcombine -reassociate -instcombine with D45842

define i1 @bit-check-combine1(i32 %a, i32 %b) {
entry:
  %0 = and i32 %b, 8
  %1 = and i32 %a, 7
  %2 = or i32 %0, %1
  %3 = and i32 %b, 48
  %4 = or i32 %2, %3
  %5 = icmp eq i32 %4, 0
  ret i1 %5
}

[lebedev.ri]

In D46336#1090644, @yamauchi wrote:

After -instcombine -reassociate -instcombine -reassociate -instcombine with D45842

define i1 @bit-check-combine1(i32 %a, i32 %b) {
entry:
  %0 = and i32 %b, 8
  %1 = and i32 %a, 7
  %2 = or i32 %0, %1
  %3 = and i32 %b, 48
  %4 = or i32 %2, %3
  %5 = icmp eq i32 %4, 0
  ret i1 %5
}

So it seems D45842 did what it was supposed to, but the instcombine can't fold that down into

define i1 @bit-check-combine1(i32 %a, i32 %b) {
entry:
  %0 = and i32 %a, 7
  %1 = and i32 %b, 56
  %2 = or i32 %0, %1
  %3 = icmp eq i32 %2, 0
  ret i1 %3
}

I'd guess something in instcombine does not use commutative matchers.
(I did not analyse this at all yet, just 'saving' it as one comment)
https://rise4fun.com/Alive/PsC

[hjyamauchi]

In D46336#1090655, @lebedev.ri wrote:

I'd guess something in instcombine does not use commutative matchers.
(I did not analyse this at all yet, just 'saving' it as one comment)
https://rise4fun.com/Alive/PsC

It's not immediately obvious to me which matcher this may relate to, if it's matcher issue.

Could this also be what this patch aims to explore, ie. folding a commutative alternative position of the nested or's (%4/%2) above?

[hjyamauchi]

D46595 is a simpler but limited version of this. Note the test @bit-check-combine-256() doesn't get folded there as simple as here. But it doesn't modify the run loop and is less complex.

[hjyamauchi]

Here's a comparison with D45842 for the 4th test @bit-check-combine-256 (which I understand is a long one, I'll try to see if I can reduce this.)

After -instcombine with this patch

define i1 @bit-check-combine-256(i32* %bits0, i32* %bits1, i32* %bits2, i32* %bits3, i32* %bits4, i32* %bits5, i32* %bits6, i32* %bits7) {
entry:
  %0 = load i32, i32* %bits0, align 4
  %1 = icmp eq i32 %0, -2145382392
  %2 = load i32, i32* %bits1, align 4
  %3 = load i32, i32* %bits2, align 4
  %4 = load i32, i32* %bits3, align 4
  %5 = or i32 %3, %4
  %6 = and i32 %5, 2147483647
  %7 = or i32 %2, %6
  %8 = or i32 %3, %4
  %9 = and i32 %8, -2147483648
  %10 = or i32 %9, %7
  %11 = load i32, i32* %bits4, align 4
  %12 = load i32, i32* %bits5, align 4
  %13 = or i32 %11, %12
  %14 = and i32 %13, 2147483647
  %15 = or i32 %10, %14
  %16 = or i32 %11, %12
  %17 = and i32 %16, -2147483648
  %18 = or i32 %17, %15
  %19 = load i32, i32* %bits6, align 4
  %20 = load i32, i32* %bits7, align 4
  %21 = or i32 %19, %20
  %22 = and i32 %21, 2147483647
  %23 = or i32 %18, %22
  %24 = or i32 %19, %20
  %25 = and i32 %24, -2147483648
  %26 = or i32 %25, %23
  %27 = icmp eq i32 %26, 0
  %28 = and i1 %27, %1
  ret i1 %28
}

After -instcombine -reassociate -instcombine -reassociate -instcombine with D45842

define i1 @bit-check-combine-256(i32* %bits0, i32* %bits1, i32* %bits2, i32* %bits3, i32* %bits4, i32* %bits5, i32* %bits6, i32* %bits7) {
entry:
  %0 = load i32, i32* %bits0, align 4
  %1 = icmp eq i32 %0, -2145382392
  %2 = load i32, i32* %bits1, align 4
  %3 = load i32, i32* %bits2, align 4
  %and.i3199 = and i32 %3, 1
  %and.i3201 = and i32 %3, 2
  %and.i3203 = and i32 %3, 4
  %and.i3205 = and i32 %3, 8
  %and.i3207 = and i32 %3, 16
  %and.i3209 = and i32 %3, 32
  %and.i3211 = and i32 %3, 64
  %4 = and i32 %3, 384
  %and.i3216 = and i32 %3, 512
  %and.i3218 = and i32 %3, 1024
  %and.i3220 = and i32 %3, 2048
  %and.i3222 = and i32 %3, 4096
  %and.i3224 = and i32 %3, 8192
  %and.i3226 = and i32 %3, 16384
  %5 = and i32 %3, 98304
  %and.i3231 = and i32 %3, 131072
  %and.i3233 = and i32 %3, 262144
  %and.i3235 = and i32 %3, 524288
  %and.i3237 = and i32 %3, 1048576
  %and.i3239 = and i32 %3, 2097152
  %and.i3241 = and i32 %3, 4194304
  %and.i3243 = and i32 %3, 8388608
  %and.i3249 = and i32 %3, 67108864
  %and.i3255 = and i32 %3, 536870912
  %and.i3257 = and i32 %3, 1073741824
  %6 = and i32 %3, 402653184
  %7 = or i32 %6, %2
  %8 = or i32 %7, %and.i3249
  %9 = or i32 %8, %and.i3257
  %10 = or i32 %9, %and.i3255
  %11 = or i32 %10, %and.i3199
  %12 = or i32 %11, %and.i3201
  %13 = or i32 %12, %and.i3203
  %14 = or i32 %13, %and.i3205
  %15 = or i32 %14, %and.i3207
  %16 = or i32 %15, %and.i3209
  %17 = or i32 %16, %and.i3211
  %18 = or i32 %17, %4
  %19 = or i32 %18, %and.i3216
  %20 = or i32 %19, %and.i3218
  %21 = or i32 %20, %and.i3220
  %22 = or i32 %21, %and.i3222
  %23 = or i32 %22, %and.i3224
  %24 = or i32 %23, %and.i3226
  %25 = or i32 %24, %5
  %26 = or i32 %25, %and.i3231
  %27 = or i32 %26, %and.i3233
  %28 = or i32 %27, %and.i3235
  %29 = or i32 %28, %and.i3237
  %30 = or i32 %29, %and.i3239
  %31 = or i32 %30, %and.i3241
  %32 = or i32 %31, %and.i3243
  %33 = and i32 %3, 50331648
  %34 = or i32 %33, %32
  %35 = icmp eq i32 %34, 0
  %36 = and i1 %1, %35
  %cmp.i3259 = icmp sgt i32 %3, -1
  %and3752918 = and i1 %cmp.i3259, %36
  %37 = load i32, i32* %bits3, align 4
  %38 = load i32, i32* %bits4, align 4
  %and.i3321 = and i32 %38, 1
  %and.i3323 = and i32 %38, 2
  %and.i3325 = and i32 %38, 4
  %and.i3327 = and i32 %38, 8
  %and.i3329 = and i32 %38, 16
  %and.i3331 = and i32 %38, 32
  %and.i3333 = and i32 %38, 64
  %39 = and i32 %38, 384
  %and.i3338 = and i32 %38, 512
  %and.i3340 = and i32 %38, 1024
  %and.i3342 = and i32 %38, 2048
  %and.i3344 = and i32 %38, 4096
  %and.i3346 = and i32 %38, 8192
  %and.i3348 = and i32 %38, 16384
  %40 = and i32 %38, 98304
  %and.i3353 = and i32 %38, 131072
  %and.i3355 = and i32 %38, 262144
  %and.i3357 = and i32 %38, 524288
  %and.i3359 = and i32 %38, 1048576
  %and.i3361 = and i32 %38, 2097152
  %and.i3363 = and i32 %38, 4194304
  %and.i3365 = and i32 %38, 8388608
  %and.i3371 = and i32 %38, 67108864
  %and.i3377 = and i32 %38, 536870912
  %and.i3379 = and i32 %38, 1073741824
  %41 = and i32 %38, 402653184
  %42 = or i32 %41, %37
  %43 = or i32 %42, %and.i3371
  %44 = or i32 %43, %and.i3379
  %45 = or i32 %44, %and.i3377
  %46 = or i32 %45, %and.i3321
  %47 = or i32 %46, %and.i3323
  %48 = or i32 %47, %and.i3325
  %49 = or i32 %48, %and.i3327
  %50 = or i32 %49, %and.i3329
  %51 = or i32 %50, %and.i3331
  %52 = or i32 %51, %and.i3333
  %53 = or i32 %52, %39
  %54 = or i32 %53, %and.i3338
  %55 = or i32 %54, %and.i3340
  %56 = or i32 %55, %and.i3342
  %57 = or i32 %56, %and.i3344
  %58 = or i32 %57, %and.i3346
  %59 = or i32 %58, %and.i3348
  %60 = or i32 %59, %40
  %61 = or i32 %60, %and.i3353
  %62 = or i32 %61, %and.i3355
  %63 = or i32 %62, %and.i3357
  %64 = or i32 %63, %and.i3359
  %65 = or i32 %64, %and.i3361
  %66 = or i32 %65, %and.i3363
  %67 = or i32 %66, %and.i3365
  %68 = and i32 %38, 50331648
  %69 = or i32 %68, %67
  %70 = icmp eq i32 %69, 0
  %71 = and i1 %70, %and3752918
  %cmp.i3381 = icmp sgt i32 %38, -1
  %and6312982 = and i1 %cmp.i3381, %71
  %72 = load i32, i32* %bits5, align 4
  %73 = load i32, i32* %bits6, align 4
  %and.i3443 = and i32 %73, 1
  %and.i3445 = and i32 %73, 2
  %and.i3447 = and i32 %73, 4
  %and.i3449 = and i32 %73, 8
  %and.i3451 = and i32 %73, 16
  %and.i3453 = and i32 %73, 32
  %and.i3455 = and i32 %73, 64
  %74 = and i32 %73, 384
  %and.i3460 = and i32 %73, 512
  %and.i3462 = and i32 %73, 1024
  %and.i3464 = and i32 %73, 2048
  %and.i3466 = and i32 %73, 4096
  %and.i3468 = and i32 %73, 8192
  %and.i3470 = and i32 %73, 16384
  %75 = and i32 %73, 98304
  %and.i3475 = and i32 %73, 131072
  %and.i3477 = and i32 %73, 262144
  %and.i3479 = and i32 %73, 524288
  %and.i3481 = and i32 %73, 1048576
  %and.i3483 = and i32 %73, 2097152
  %and.i3485 = and i32 %73, 4194304
  %and.i3487 = and i32 %73, 8388608
  %and.i3493 = and i32 %73, 67108864
  %and.i3499 = and i32 %73, 536870912
  %and.i3501 = and i32 %73, 1073741824
  %76 = and i32 %73, 402653184
  %77 = or i32 %76, %72
  %78 = or i32 %77, %and.i3493
  %79 = or i32 %78, %and.i3501
  %80 = or i32 %79, %and.i3499
  %81 = or i32 %80, %and.i3443
  %82 = or i32 %81, %and.i3445
  %83 = or i32 %82, %and.i3447
  %84 = or i32 %83, %and.i3449
  %85 = or i32 %84, %and.i3451
  %86 = or i32 %85, %and.i3453
  %87 = or i32 %86, %and.i3455
  %88 = or i32 %87, %74
  %89 = or i32 %88, %and.i3460
  %90 = or i32 %89, %and.i3462
  %91 = or i32 %90, %and.i3464
  %92 = or i32 %91, %and.i3466
  %93 = or i32 %92, %and.i3468
  %94 = or i32 %93, %and.i3470
  %95 = or i32 %94, %75
  %96 = or i32 %95, %and.i3475
  %97 = or i32 %96, %and.i3477
  %98 = or i32 %97, %and.i3479
  %99 = or i32 %98, %and.i3481
  %100 = or i32 %99, %and.i3483
  %101 = or i32 %100, %and.i3485
  %102 = or i32 %101, %and.i3487
  %103 = and i32 %73, 50331648
  %104 = or i32 %103, %102
  %105 = icmp eq i32 %104, 0
  %106 = and i1 %105, %and6312982
  %cmp.i3503 = icmp sgt i32 %73, -1
  %and8873046 = and i1 %cmp.i3503, %106
  %107 = load i32, i32* %bits7, align 4
  %108 = icmp eq i32 %107, 0
  %109 = and i1 %108, %and8873046
  ret i1 %109
}

lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (MatchRem(MulOpV, RemOpV, C1, Rem2IsSigned) &&
       }
     }
   }
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
-  bool Changed = SimplifyAssociativeOrCommutative(I);
+  bool Changed = SimplifyAssociativeOrCommutative(I, false);
+  if (Instruction *V = visitAddWithoutAssociativeOrCommutative(I)) {
+    return V;
+  }
+  Changed |= SimplifyAssociativeOrCommutative(I, true);
+  return Changed ? &I : nullptr;
+}
+
+Instruction *InstCombiner::visitAddWithoutAssociativeOrCommutative(
+    BinaryOperator &I) {
+  assert(hasCanonicalizedBinOpOperandOrder(I) &&
+         "Non-canonicalized binop operand order");
+
   if (Value *V = SimplifyVectorOp(I))
     return replaceInstUsesWith(I, V);
 
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   if (Value *V =
           SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
                           SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
if (match(&I, m_c_BinOp(m_Or(m_Value(A), m_Value(B)),
     I.setOperand(0, A);
     I.setOperand(1, B);
     return &I;
   }
 
   // TODO(jingyue): Consider willNotOverflowSignedAdd and
   // willNotOverflowUnsignedAdd to reduce the number of invocations of
   // computeKnownBits.
+  bool Changed = false;
   if (!I.hasNoSignedWrap() && willNotOverflowSignedAdd(LHS, RHS, I)) {
     Changed = true;
     I.setHasNoSignedWrap(true);
   }
   if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedAdd(LHS, RHS, I)) {
     Changed = true;
     I.setHasNoUnsignedWrap(true);
   }
 
   return Changed ? &I : nullptr;
 }
 
 Instruction *InstCombiner::visitFAdd(BinaryOperator &I) {
-  bool Changed = SimplifyAssociativeOrCommutative(I);
+  bool Changed = SimplifyAssociativeOrCommutative(I, false);
+  if (Instruction *V = visitFAddWithoutAssociativeOrCommutative(I)) {
+    return V;
+  }
+  Changed |= SimplifyAssociativeOrCommutative(I, true);
+  return Changed ? &I : nullptr;
+}
+
+Instruction *InstCombiner::visitFAddWithoutAssociativeOrCommutative(
+    BinaryOperator &I) {
+  assert(hasCanonicalizedBinOpOperandOrder(I) &&
+         "Non-canonicalized binop operand order");
+
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyFAddInst(LHS, RHS, I.getFastMathFlags(),
                                   SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
Instruction *InstCombiner::visitFAddWithoutAssociativeOrCommutative(
   if (Value *V = SimplifySelectsFeedingBinaryOp(I, LHS, RHS))
     return replaceInstUsesWith(I, V);
 
   if (I.hasAllowReassoc() && I.hasNoSignedZeros()) {
     if (Value *V = FAddCombine(Builder).simplify(&I))
       return replaceInstUsesWith(I, V);
   }
 
-  return Changed ? &I : nullptr;
+  return nullptr;
 }
 
 /// Optimize pointer differences into the same array into a size.  Consider:
 ///  &A[10] - &A[0]: we should compile this to "10".  LHS/RHS are the pointer
 /// operands to the ptrtoint instructions for the LHS/RHS of the subtract.
 Value *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS,
                                                Type *Ty) {
   // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Value *NewBO = Opc == Instruction::Sub ? Builder.CreateBinOp(Opc, NewC, X)
                                          : Builder.CreateBinOp(Opc, X, NewC);
   return new ZExtInst(Builder.CreateAnd(NewBO, X), Ty);
 }
 
 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
 // here. We should standardize that construct where it is needed or choose some
 // other way to ensure that commutated variants of patterns are not missed.
 Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
-  bool Changed = SimplifyAssociativeOrCommutative(I);
+  bool Changed = SimplifyAssociativeOrCommutative(I, false);
+  if (Instruction *V = visitAndWithoutAssociativeOrCommutative(I)) {
+    return V;
+  }
+  Changed |= SimplifyAssociativeOrCommutative(I, true);
+  return Changed ? &I : nullptr;
+}
+
+Instruction *InstCombiner::visitAndWithoutAssociativeOrCommutative(
+    BinaryOperator &I) {
+  assert(hasCanonicalizedBinOpOperandOrder(I) &&
+         "Non-canonicalized binop operand order");
+
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyAndInst(Op0, Op1, SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 
Instruction *InstCombiner::visitAndWithoutAssociativeOrCommutative(
   Value *A;
   if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
       A->getType()->isIntOrIntVectorTy(1))
     return SelectInst::Create(A, Op1, Constant::getNullValue(I.getType()));
   if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
       A->getType()->isIntOrIntVectorTy(1))
     return SelectInst::Create(A, Op0, Constant::getNullValue(I.getType()));
 
-  return Changed ? &I : nullptr;
+  return nullptr;
 }
 
 /// Given an OR instruction, check to see if this is a bswap idiom. If so,
 /// insert the new intrinsic and return it.
 Instruction *InstCombiner::MatchBSwap(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   // Look through zero extends.
Value *InstCombiner::foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS,
   }
   return nullptr;
 }
 
 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
 // here. We should standardize that construct where it is needed or choose some
 // other way to ensure that commutated variants of patterns are not missed.
 Instruction *InstCombiner::visitOr(BinaryOperator &I) {
-  bool Changed = SimplifyAssociativeOrCommutative(I);
+  bool Changed = SimplifyAssociativeOrCommutative(I, false);
+  if (Instruction *V = visitOrWithoutAssociativeOrCommutative(I)) {
+    return V;
+  }
+  Changed |= SimplifyAssociativeOrCommutative(I, true);
+  return Changed ? &I : nullptr;
+}
+
+Instruction *InstCombiner::visitOrWithoutAssociativeOrCommutative(
+    BinaryOperator &I) {
+  assert(hasCanonicalizedBinOpOperandOrder(I) &&
+         "Non-canonicalized binop operand order");
+
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyOrInst(Op0, Op1, SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 
if (Op0->hasOneUse() && Op1->hasOneUse() &&
         match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) &&
         match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) {
       Value *orTrue = Builder.CreateOr(A, C);
       Value *orFalse = Builder.CreateOr(B, D);
       return SelectInst::Create(X, orTrue, orFalse);
     }
   }
 
-  return Changed ? &I : nullptr;
+  return nullptr;
 }
 
 /// A ^ B can be specified using other logic ops in a variety of patterns. We
 /// can fold these early and efficiently by morphing an existing instruction.
 static Instruction *foldXorToXor(BinaryOperator &I,
                                  InstCombiner::BuilderTy &Builder) {
   assert(I.getOpcode() == Instruction::Xor);
   Value *Op0 = I.getOperand(0);
static Instruction *visitMaskedMerge(BinaryOperator &I,
 
   return nullptr;
 }
 
 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
 // here. We should standardize that construct where it is needed or choose some
 // other way to ensure that commutated variants of patterns are not missed.
 Instruction *InstCombiner::visitXor(BinaryOperator &I) {
-  bool Changed = SimplifyAssociativeOrCommutative(I);
+  bool Changed = SimplifyAssociativeOrCommutative(I, false);
+  if (Instruction *V = visitXorWithoutAssociativeOrCommutative(I)) {
+    return V;
+  }
+  Changed |= SimplifyAssociativeOrCommutative(I, true);
+  return Changed ? &I : nullptr;
+}
+
+Instruction *InstCombiner::visitXorWithoutAssociativeOrCommutative(
+    BinaryOperator &I) {
+  assert(hasCanonicalizedBinOpOperandOrder(I) &&
+         "Non-canonicalized binop operand order");
+
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyXorInst(Op0, Op1, SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 
if (Op0->hasOneUse() && SelectPatternResult::isMinOrMax(SPF) &&
       if (match(LHS, m_Not(m_Value(X)))) {
         Value *NotY = Builder.CreateNot(RHS);
         return SelectInst::Create(
             Builder.CreateICmp(getInverseMinMaxPred(SPF), X, NotY), X, NotY);
       }
     }
   }
 
-  return Changed ? &I : nullptr;
+  return nullptr;
 }

lib/Transforms/InstCombine/InstCombineInternal.h

InstCombiner(InstCombineWorklist &Worklist, BuilderTy &Builder,
       : Worklist(Worklist), Builder(Builder), MinimizeSize(MinimizeSize),
         ExpensiveCombines(ExpensiveCombines), AA(AA), AC(AC), TLI(TLI), DT(DT),
         DL(DL), SQ(DL, &TLI, &DT, &AC), ORE(ORE), LI(LI) {}
 
   /// Run the combiner over the entire worklist until it is empty.
   ///
   /// \returns true if the IR is changed.
   bool run();
+  /// A helper for run() to handle the logic before calling visit().
+  /// \returns true if some simplification happened before calling visit(),
+  /// which indicates we loop around the main loop without calling visit().
+  bool handleBeforeVisit(Instruction *I, std::string &OrigI);
+  /// A helper for run() to handle the logic after calling visit().
+  void handleAfterVisit(Instruction *I, Instruction *Result,
+                        std::string &OrigI);
 
   AssumptionCache &getAssumptionCache() const { return AC; }
 
   const DataLayout &getDataLayout() const { return DL; }
 
   DominatorTree &getDominatorTree() const { return DT; }
 
   LoopInfo *getLoopInfo() const { return LI; }
 
   TargetLibraryInfo &getTargetLibraryInfo() const { return TLI; }
 
   // Visitation implementation - Implement instruction combining for different
   // instruction types.  The semantics are as follows:
   // Return Value:
   //    null        - No change was made
   //     I          - Change was made, I is still valid, I may be dead though
   //   otherwise    - Change was made, replace I with returned instruction
   //
   Instruction *visitAdd(BinaryOperator &I);
+  Instruction *visitAddWithoutAssociativeOrCommutative(BinaryOperator &I);
   Instruction *visitFAdd(BinaryOperator &I);
+  Instruction *visitFAddWithoutAssociativeOrCommutative(BinaryOperator &I);
   Value *OptimizePointerDifference(Value *LHS, Value *RHS, Type *Ty);
   Instruction *visitSub(BinaryOperator &I);
   Instruction *visitFSub(BinaryOperator &I);
   Instruction *visitMul(BinaryOperator &I);
+  Instruction *visitMulWithoutAssociativeOrCommutative(BinaryOperator &I);
   Instruction *visitFMul(BinaryOperator &I);
+  Instruction *visitFMulWithoutAssociativeOrCommutative(BinaryOperator &I);
   Instruction *visitURem(BinaryOperator &I);
   Instruction *visitSRem(BinaryOperator &I);
   Instruction *visitFRem(BinaryOperator &I);
   bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I);
   Instruction *commonRemTransforms(BinaryOperator &I);
   Instruction *commonIRemTransforms(BinaryOperator &I);
   Instruction *commonDivTransforms(BinaryOperator &I);
   Instruction *commonIDivTransforms(BinaryOperator &I);
   Instruction *visitUDiv(BinaryOperator &I);
   Instruction *visitSDiv(BinaryOperator &I);
   Instruction *visitFDiv(BinaryOperator &I);
   Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
   Instruction *visitAnd(BinaryOperator &I);
+  Instruction *visitAndWithoutAssociativeOrCommutative(BinaryOperator &I);
   Instruction *visitOr(BinaryOperator &I);
+  Instruction *visitOrWithoutAssociativeOrCommutative(BinaryOperator &I);
   Instruction *visitXor(BinaryOperator &I);
+  Instruction *visitXorWithoutAssociativeOrCommutative(BinaryOperator &I);
   Instruction *visitShl(BinaryOperator &I);
   Instruction *visitAShr(BinaryOperator &I);
   Instruction *visitLShr(BinaryOperator &I);
   Instruction *commonShiftTransforms(BinaryOperator &I);
   Instruction *visitFCmpInst(FCmpInst &I);
   Instruction *visitICmpInst(ICmpInst &I);
   Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
                                    BinaryOperator &I);
public:
   }
 
   /// Maximum size of array considered when transforming.
   uint64_t MaxArraySizeForCombine;
 
 private:
   /// Performs a few simplifications for operators which are associative
   /// or commutative.
-  bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
+  bool SimplifyAssociativeOrCommutative(BinaryOperator &I,
+                                        bool TryNonConstantCases);
+
+  /// Order BinaryOperator operands such that they are listed from right
+  /// (least complex) to left (most complex).  This puts constants before unary
+  /// operators before binary operators.
+  bool canonicalizeBinOpOperandOrder(BinaryOperator &I);
+
+  /// Check that BinaryOperator operands are ordered such that they are
+  /// listed from right (least complex) to left (most complex) where constants
+  /// are put before unary operators before binary operators.
+  bool hasCanonicalizedBinOpOperandOrder(BinaryOperator &I);
+
+  /// A helper for SimplifyAssociativeOrCommutative to apply instruction
+  /// combiner folding to a sub-binary operator in associative or commutative
+  /// cases.
+  bool simplifySubBinOpAssociativeOrCommutative(BinaryOperator &I,
+                                                BinaryOperator &SubBO);
+
+  /// Set the insert point and the current debug location to the given
+  /// instruction.
+  void setInsertAndCurrentDebugLocation(Instruction &I);
 
   /// Tries to simplify binary operations which some other binary
   /// operation distributes over.
   ///
   /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
   /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
   /// & (B | C) -> (A&B) | (A&C)" if this is a win).  Returns the simplified
   /// value, or null if it didn't simplify.

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

if (SignBits == BitWidth + 1) {
     KnownBits RHSKnown = computeKnownBits(RHS, /*Depth=*/0, &CxtI);
     if (LHSKnown.isNonNegative() || RHSKnown.isNonNegative())
       return true;
   }
   return false;
 }
 
 Instruction *InstCombiner::visitMul(BinaryOperator &I) {
-  bool Changed = SimplifyAssociativeOrCommutative(I);
+  bool Changed = SimplifyAssociativeOrCommutative(I, false);
+  if (Instruction *V = visitMulWithoutAssociativeOrCommutative(I)) {
+    return V;
+  }
+  Changed |= SimplifyAssociativeOrCommutative(I, true);
+  return Changed ? &I : nullptr;
+}
+
+Instruction *InstCombiner::visitMulWithoutAssociativeOrCommutative(
+    BinaryOperator &I) {
+  assert(hasCanonicalizedBinOpOperandOrder(I) &&
+         "Non-canonicalized binop operand order");
+
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyMulInst(Op0, Op1, SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 
if (auto *Op1Conv = dyn_cast<ZExtInst>(Op1)) {
         // Insert the new integer mul.
         Value *NewMul = Builder.CreateNUWMul(
             Op0Conv->getOperand(0), Op1Conv->getOperand(0), "mulconv");
         return new ZExtInst(NewMul, I.getType());
       }
     }
   }
 
+  bool Changed = false;
+
   if (!I.hasNoSignedWrap() && willNotOverflowSignedMul(Op0, Op1, I)) {
     Changed = true;
     I.setHasNoSignedWrap(true);
   }
 
   if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedMul(Op0, Op1, I)) {
     Changed = true;
     I.setHasNoUnsignedWrap(true);
   }
 
   return Changed ? &I : nullptr;
 }
 
 Instruction *InstCombiner::visitFMul(BinaryOperator &I) {
-  bool Changed = SimplifyAssociativeOrCommutative(I);
+  bool Changed = SimplifyAssociativeOrCommutative(I, false);
+  if (Instruction *V = visitFMulWithoutAssociativeOrCommutative(I)) {
+    return V;
+  }
+  Changed |= SimplifyAssociativeOrCommutative(I, true);
+  return Changed ? &I : nullptr;
+}
+
+Instruction *InstCombiner::visitFMulWithoutAssociativeOrCommutative(
+    BinaryOperator &I) {
+  assert(hasCanonicalizedBinOpOperandOrder(I) &&
+         "Non-canonicalized binop operand order");
+
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyFMulInst(Op0, Op1, I.getFastMathFlags(),
                                   SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
if (I.isFast()) {
     if (Log2) {
       Log2->setArgOperand(0, X);
       Log2->copyFastMathFlags(&I);
       Value *LogXTimesY = Builder.CreateFMulFMF(Log2, Y, &I);
       return BinaryOperator::CreateFSubFMF(LogXTimesY, Y, &I);
     }
   }
 
-  return Changed ? &I : nullptr;
+  return nullptr;
 }
 
 /// Fold a divide or remainder with a select instruction divisor when one of the
 /// select operands is zero. In that case, we can use the other select operand
 /// because div/rem by zero is undefined.
 bool InstCombiner::simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I) {
   SelectInst *SI = dyn_cast<SelectInst>(I.getOperand(1));
   if (!SI)

lib/Transforms/InstCombine/InstructionCombining.cpp

static bool simplifyAssocCastAssoc(BinaryOperator *BinOp1) {
   Type *DestTy = C1->getType();
   Constant *CastC2 = ConstantExpr::getCast(CastOpcode, C2, DestTy);
   Constant *FoldedC = ConstantExpr::get(AssocOpcode, C1, CastC2);
   Cast->setOperand(0, BinOp2->getOperand(0));
   BinOp1->setOperand(1, FoldedC);
   return true;
 }
 
+void InstCombiner::setInsertAndCurrentDebugLocation(Instruction &I) {
+  Builder.SetInsertPoint(&I);
+  Builder.SetCurrentDebugLocation(I.getDebugLoc());
+}
+
+bool InstCombiner::simplifySubBinOpAssociativeOrCommutative(
+    BinaryOperator &I, BinaryOperator &SubBO) {
+  Instruction::BinaryOps Opcode = SubBO.getOpcode();
+  if (Opcode == Instruction::And || Opcode == Instruction::Or ||
+      Opcode == Instruction::Xor || Opcode == Instruction::Add ||
+      Opcode == Instruction::FAdd || Opcode == Instruction::Mul ||
+      Opcode == Instruction::FMul) {
+    std::string OrigI;
+    if (handleBeforeVisit(&SubBO, OrigI)) {
+      return true;
+    }
+    Instruction *NewSubBO = nullptr;
+    switch (Opcode) {
+      case Instruction::And:
+        NewSubBO = visitAndWithoutAssociativeOrCommutative(SubBO);
+        break;
+      case Instruction::Or:
+        NewSubBO = visitOrWithoutAssociativeOrCommutative(SubBO);
+        break;
+      case Instruction::Xor:
+        NewSubBO = visitXorWithoutAssociativeOrCommutative(SubBO);
+        break;
+      case Instruction::Add:
+        NewSubBO = visitAddWithoutAssociativeOrCommutative(SubBO);
+        break;
+      case Instruction::FAdd:
+        NewSubBO = visitFAddWithoutAssociativeOrCommutative(SubBO);
+        break;
+      case Instruction::Mul:
+        NewSubBO = visitMulWithoutAssociativeOrCommutative(SubBO);
+        break;
+      case Instruction::FMul:
+        NewSubBO = visitFMulWithoutAssociativeOrCommutative(SubBO);
+        break;
+      default:
+        assert(false && "Unreachable");
+    }
+    if (NewSubBO) {
+      handleAfterVisit(&SubBO, NewSubBO, OrigI);
+      // Reset the insert point and the current debug location back to the
+      // top-level instruction.
+      setInsertAndCurrentDebugLocation(I);
+      return true;
+    }
+    setInsertAndCurrentDebugLocation(I);
+  }
+  return false;
+}
+
+bool InstCombiner::canonicalizeBinOpOperandOrder(BinaryOperator &I) {
+  // Order operands such that they are listed from right (least complex) to
+  // left (most complex).  This puts constants before unary operators before
+  // binary operators.
+  if (I.isCommutative() && getComplexity(I.getOperand(0)) <
+      getComplexity(I.getOperand(1)))
+    return !I.swapOperands();
+  return false;
+}
+
+bool InstCombiner::hasCanonicalizedBinOpOperandOrder(BinaryOperator &I) {
+  // Check that BinaryOperator operands are ordered such that they are
+  // listed from right (least complex) to left (most complex) where constants
+  // are put before unary operators before binary operators.
+  return !I.isCommutative() || getComplexity(I.getOperand(0)) >=
+      getComplexity(I.getOperand(1));
+}
+
+bool hasNoOverflowFlags(BinaryOperator &I) {
+  if (!isa<OverflowingBinaryOperator>(&I))
+    return true;
+  return !I.hasNoUnsignedWrap() && !I.hasNoSignedWrap();
+}
+
 /// This performs a few simplifications for operators that are associative or
 /// commutative:
 ///
 ///  Commutative operators:
 ///
 ///  1. Order operands such that they are listed from right (least complex) to
 ///     left (most complex).  This puts constants before unary operators before
 ///     binary operators.
 ///
 ///  Associative operators:
 ///
 ///  2. Transform: "(A op B) op C" ==> "A op (B op C)" if "B op C" simplifies.
 ///  3. Transform: "A op (B op C)" ==> "(A op B) op C" if "A op B" simplifies.
 ///
 ///  Associative and commutative operators:
 ///
 ///  4. Transform: "(A op B) op C" ==> "(C op A) op B" if "C op A" simplifies.
 ///  5. Transform: "A op (B op C)" ==> "B op (C op A)" if "C op A" simplifies.
 ///  6. Transform: "(A op C1) op (B op C2)" ==> "(A op B) op (C1 op C2)"
 ///     if C1 and C2 are constants.
-bool InstCombiner::SimplifyAssociativeOrCommutative(BinaryOperator &I) {
+bool InstCombiner::SimplifyAssociativeOrCommutative(BinaryOperator &I,
+                                                    bool TryNonConstantCases) {
   Instruction::BinaryOps Opcode = I.getOpcode();
   bool Changed = false;
 
   do {
-    // Order operands such that they are listed from right (least complex) to
-    // left (most complex).  This puts constants before unary operators before
-    // binary operators.
-    if (I.isCommutative() && getComplexity(I.getOperand(0)) <
-        getComplexity(I.getOperand(1)))
-      Changed = !I.swapOperands();
+    if (canonicalizeBinOpOperandOrder(I))
+      Changed = true;
 
     BinaryOperator *Op0 = dyn_cast<BinaryOperator>(I.getOperand(0));
     BinaryOperator *Op1 = dyn_cast<BinaryOperator>(I.getOperand(1));
 
     if (I.isAssociative()) {
       // Transform: "(A op B) op C" ==> "A op (B op C)" if "B op C" simplifies.
       if (Op0 && Op0->getOpcode() == Opcode) {
         Value *A = Op0->getOperand(0);
if (I.isAssociative()) {
           } else {
             ClearSubclassDataAfterReassociation(I);
           }
 
           Changed = true;
           ++NumReassoc;
           continue;
         }
+
+        if (TryNonConstantCases && Op0->hasOneUse() &&
+            hasNoOverflowFlags(I) && hasNoOverflowFlags(*Op0)) {
+          // Try to simplify (B op C). Temporarily modify to A op (B op C) and
+          // move Op0 right before I (so that C will always dominate Op0.)
+          DEBUG(dbgs() << "Attempt to simplify (B op C)\n"
+                << "I " << I << "\n"
+                << "Op0 " << *Op0 << "\n"
+                << "B " << *B << "\n"
+                << "C " << *C << "\n");
+          I.setOperand(0, A);
+          I.setOperand(1, Op0);
+          Op0->setOperand(0, B);
+          Op0->setOperand(1, C);
+          canonicalizeBinOpOperandOrder(*Op0);
+          Instruction *Op0OrigLoc = Op0->getNextNode();
+          Op0->moveBefore(&I);
+          if (simplifySubBinOpAssociativeOrCommutative(I, *Op0)) {
+            Changed = true;
+            ++NumReassoc;
+            DEBUG(dbgs() << "Simplifed to\n"
+                  << "I " << I << "\n"
+                  << "Op " << *I.getOperand(1) << "\n");
+            continue;
+          } else {
+            // Revert.
+            I.setOperand(0, Op0);
+            I.setOperand(1, C);
+            Op0->setOperand(0, A);
+            Op0->setOperand(1, B);
+            Op0->moveBefore(Op0OrigLoc);
+            DEBUG(dbgs() << "Didn't simplify.\n"
+                  << "I " << I << "\n"
+                  << "Op0 " << *Op0 << "\n");
+          }
+        }
       }
 
       // Transform: "A op (B op C)" ==> "(A op B) op C" if "A op B" simplifies.
       if (Op1 && Op1->getOpcode() == Opcode) {
         Value *A = I.getOperand(0);
         Value *B = Op1->getOperand(0);
         Value *C = Op1->getOperand(1);
 
         // Does "A op B" simplify?
         if (Value *V = SimplifyBinOp(Opcode, A, B, SQ.getWithInstruction(&I))) {
           // It simplifies to V.  Form "V op C".
           I.setOperand(0, V);
           I.setOperand(1, C);
           // Conservatively clear the optional flags, since they may not be
           // preserved by the reassociation.
           ClearSubclassDataAfterReassociation(I);
           Changed = true;
           ++NumReassoc;
           continue;
         }
+
+        if (TryNonConstantCases && Op1->hasOneUse() &&
+            hasNoOverflowFlags(I) && hasNoOverflowFlags(*Op1)) {
+          // Try to simplify (A op B). Temporarily modify to (A op B) op C and
+          // move Op1 right before I (so that A will always dominate Op1.)
+          DEBUG(dbgs() << "Attempt to simplify (A op B)\n"
+                << "I " << I << "\n"
+                << "Op1 " << *Op1 << "\n"
+                << "A " << *A << "\n"
+                << "B " << *B << "\n");
+          I.setOperand(0, Op1);
+          I.setOperand(1, C);
+          Op1->setOperand(0, A);
+          Op1->setOperand(1, B);
+          canonicalizeBinOpOperandOrder(*Op1);
+          Instruction *Op1OrigLoc = Op1->getNextNode();
+          Op1->moveBefore(&I);
+          if (simplifySubBinOpAssociativeOrCommutative(I, *Op1)) {
+            Changed = true;
+            ++NumReassoc;
+            DEBUG(dbgs() << "Simplifed to\n"
+                  << "I " << I << "\n"
+                  << "Op " << *I.getOperand(0) << "\n");
+            continue;
+          } else {
+            // Revert.
+            I.setOperand(0, A);
+            I.setOperand(1, Op1);
+            Op1->setOperand(0, B);
+            Op1->setOperand(1, C);
+            Op1->moveBefore(Op1OrigLoc);
+            DEBUG(dbgs() << "Didn't simplify.\n"
+                  << "I " << I << "\n"
+                  << "Op1 " << *Op1 << "\n");
+          }
+        }
       }
     }
 
     if (I.isAssociative() && I.isCommutative()) {
       if (simplifyAssocCastAssoc(&I)) {
         Changed = true;
         ++NumReassoc;
         continue;
if (I.isAssociative() && I.isCommutative()) {
           I.setOperand(1, B);
           // Conservatively clear the optional flags, since they may not be
           // preserved by the reassociation.
           ClearSubclassDataAfterReassociation(I);
           Changed = true;
           ++NumReassoc;
           continue;
         }
+
+        if (TryNonConstantCases && Op0->hasOneUse() &&
+            hasNoOverflowFlags(I) && hasNoOverflowFlags(*Op0)) {
+          // Try to simplify (C op A). Temporarily modify to A op (B op C) and
+          // move Op0 right before I (so that C will always dominate Op0.)
+          DEBUG(dbgs() << "Attempt to simplify (C op A)\n"
+                << "I " << I << "\n"
+                << "Op0 " << *Op0 << "\n"
+                << "C " << *C << "\n"
+                << "A " << *A << "\n");
+          I.setOperand(1, B);
+          Op0->setOperand(0, C);
+          Op0->setOperand(1, A);
+          canonicalizeBinOpOperandOrder(*Op0);
+          Instruction *Op0OrigLoc = Op0->getNextNode();
+          Op0->moveBefore(&I);
+          if (simplifySubBinOpAssociativeOrCommutative(I, *Op0)) {
+            Changed = true;
+            ++NumReassoc;
+            DEBUG(dbgs() << "Simplifed to\n"
+                  << "I " << I << "\n"
+                  << "Op " << *I.getOperand(0) << "\n");
+            continue;
+          } else {
+            // Revert.
+            I.setOperand(1, C);
+            Op0->setOperand(0, A);
+            Op0->setOperand(1, B);
+            Op0->moveBefore(Op0OrigLoc);
+            DEBUG(dbgs() << "Didn't simplify.\n"
+                  << "I " << I << "\n"
+                  << "Op0 " << *Op0 << "\n");
+          }
+        }
       }
 
       // Transform: "A op (B op C)" ==> "B op (C op A)" if "C op A" simplifies.
       if (Op1 && Op1->getOpcode() == Opcode) {
         Value *A = I.getOperand(0);
         Value *B = Op1->getOperand(0);
         Value *C = Op1->getOperand(1);
 
         // Does "C op A" simplify?
         if (Value *V = SimplifyBinOp(Opcode, C, A, SQ.getWithInstruction(&I))) {
           // It simplifies to V.  Form "B op V".
           I.setOperand(0, B);
           I.setOperand(1, V);
           // Conservatively clear the optional flags, since they may not be
           // preserved by the reassociation.
           ClearSubclassDataAfterReassociation(I);
           Changed = true;
           ++NumReassoc;
           continue;
         }
+
+        if (TryNonConstantCases && Op1->hasOneUse() &&
+            hasNoOverflowFlags(I) && hasNoOverflowFlags(*Op1)) {
+          // Try to simplify (C op A). Temporarily modify to A op (B op C) and
+          // move Op1 right before I (so that A will always dominate Op1.)
+          DEBUG(dbgs() << "Attempt to simplify (C op A)\n"
+                << "I " << I << "\n"
+                << "Op1 " << *Op1 << "\n"
+                << "C " << *C << "\n"
+                << "A " << *A << "\n");
+          I.setOperand(0, B);
+          Op1->setOperand(0, C);
+          Op1->setOperand(1, A);
+          canonicalizeBinOpOperandOrder(*Op1);
+          Instruction *Op1OrigLoc = Op1->getNextNode();
+          Op1->moveBefore(&I);
+          if (simplifySubBinOpAssociativeOrCommutative(I, *Op1)) {
+            Changed = true;
+            ++NumReassoc;
+            DEBUG(dbgs() << "Simplifed to\n"
+                  << "I " << I << "\n"
+                  << "Op " << *I.getOperand(1) << "\n");
+            continue;
+          } else {
+            // Revert.
+            I.setOperand(0, A);
+            Op1->setOperand(0, B);
+            Op1->setOperand(1, C);
+            Op1->moveBefore(Op1OrigLoc);
+            DEBUG(dbgs() << "Didn't simplify.\n"
+                  << "I " << I << "\n"
+                  << "Op1 " << *Op1 << "\n");
+          }
+        }
       }
 
       // Transform: "(A op C1) op (B op C2)" ==> "(A op B) op (C1 op C2)"
       // if C1 and C2 are constants.
       Value *A, *B;
       Constant *C1, *C2;
       if (Op0 && Op1 &&
           Op0->getOpcode() == Opcode && Op1->getOpcode() == Opcode &&
for (auto *DII : DbgUsers) {
     if (DII->getParent() == SrcBlock) {
       DII->moveBefore(&*InsertPos);
       DEBUG(dbgs() << "SINK: " << *DII << '\n');
     }
   }
   return true;
 }
 
-bool InstCombiner::run() {
-  while (!Worklist.isEmpty()) {
-    Instruction *I = Worklist.RemoveOne();
-    if (I == nullptr) continue;  // skip null values.
+bool InstCombiner::handleBeforeVisit(Instruction *I, std::string &OrigI) {
+  if (I == nullptr) return true; // skip null values.
 
-    // Check to see if we can DCE the instruction.
-    if (isInstructionTriviallyDead(I, &TLI)) {
-      DEBUG(dbgs() << "IC: DCE: " << *I << '\n');
-      eraseInstFromFunction(*I);
-      ++NumDeadInst;
-      MadeIRChange = true;
-      continue;
-    }
+    return true;
 
-    if (!DebugCounter::shouldExecute(VisitCounter))
-      continue;
+    return true;
 
-    // Instruction isn't dead, see if we can constant propagate it.
-    if (!I->use_empty() &&
-        (I->getNumOperands() == 0 || isa<Constant>(I->getOperand(0)))) {
-      if (Constant *C = ConstantFoldInstruction(I, DL, &TLI)) {
-        DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " << *I << '\n');
 
-        // Add operands to the worklist.
-        replaceInstUsesWith(*I, C);
-        ++NumConstProp;
-        if (isInstructionTriviallyDead(I, &TLI))
-          eraseInstFromFunction(*I);
-        MadeIRChange = true;
-        continue;
-      }
-    }
+      return true;
 
-    // In general, it is possible for computeKnownBits to determine all bits in
-    // a value even when the operands are not all constants.
-    Type *Ty = I->getType();
-    if (ExpensiveCombines && !I->use_empty() && Ty->isIntOrIntVectorTy()) {
-      KnownBits Known = computeKnownBits(I, /*Depth*/0, I);
-      if (Known.isConstant()) {
-        Constant *C = ConstantInt::get(Ty, Known.getConstant());
-        DEBUG(dbgs() << "IC: ConstFold (all bits known) to: " << *C <<
-                        " from: " << *I << '\n');
 
-        // Add operands to the worklist.
-        replaceInstUsesWith(*I, C);
-        ++NumConstProp;
-        if (isInstructionTriviallyDead(I, &TLI))
-          eraseInstFromFunction(*I);
-        MadeIRChange = true;
-        continue;
-      }
-    }
+      return true;
 
-    // See if we can trivially sink this instruction to a successor basic block.
-    if (I->hasOneUse()) {
-      BasicBlock *BB = I->getParent();
-      Instruction *UserInst = cast<Instruction>(*I->user_begin());
-      BasicBlock *UserParent;
 
-      // Get the block the use occurs in.
-      if (PHINode *PN = dyn_cast<PHINode>(UserInst))
-        UserParent = PN->getIncomingBlock(*I->use_begin());
-      else
-        UserParent = UserInst->getParent();
 
-      if (UserParent != BB) {
-        bool UserIsSuccessor = false;
-        // See if the user is one of our successors.
-        for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
-          if (*SI == UserParent) {
-            UserIsSuccessor = true;
-            break;
-          }
 
-        // If the user is one of our immediate successors, and if that successor
-        // only has us as a predecessors (we'd have to split the critical edge
-        // otherwise), we can keep going.
-        if (UserIsSuccessor && UserParent->getUniquePredecessor()) {
-          // Okay, the CFG is simple enough, try to sink this instruction.
-          if (TryToSinkInstruction(I, UserParent)) {
-            DEBUG(dbgs() << "IC: Sink: " << *I << '\n');
-            MadeIRChange = true;
-            // We'll add uses of the sunk instruction below, but since sinking
-            // can expose opportunities for it's *operands* add them to the
-            // worklist
-            for (Use &U : I->operands())
-              if (Instruction *OpI = dyn_cast<Instruction>(U.get()))
-                Worklist.Add(OpI);
-          }
-        }
-      }
-    }
 
-    // Now that we have an instruction, try combining it to simplify it.
-    Builder.SetInsertPoint(I);
-    Builder.SetCurrentDebugLocation(I->getDebugLoc());
+  setInsertAndCurrentDebugLocation(*I);
 
-#ifndef NDEBUG
-    std::string OrigI;
-#endif
-    DEBUG(raw_string_ostream SS(OrigI); I->print(SS); OrigI = SS.str(););
-    DEBUG(dbgs() << "IC: Visiting: " << OrigI << '\n');
 
-    if (Instruction *Result = visit(*I)) {
-      ++NumCombined;
-      // Should we replace the old instruction with a new one?
-      if (Result != I) {
-        DEBUG(dbgs() << "IC: Old = " << *I << '\n'
-                     << "    New = " << *Result << '\n');
+  return false;
+}
+
+void InstCombiner::handleAfterVisit(Instruction *I,
+                                    Instruction *Result,
+                                    std::string &OrigI) {
+  assert(Result && "Null Result");
 
-        if (I->getDebugLoc())
-          Result->setDebugLoc(I->getDebugLoc());
-        // Everything uses the new instruction now.
-        I->replaceAllUsesWith(Result);
 
-        // Move the name to the new instruction first.
-        Result->takeName(I);
 
-        // Push the new instruction and any users onto the worklist.
-        Worklist.AddUsersToWorkList(*Result);
-        Worklist.Add(Result);
 
-        // Insert the new instruction into the basic block...
-        BasicBlock *InstParent = I->getParent();
-        BasicBlock::iterator InsertPos = I->getIterator();
 
-        // If we replace a PHI with something that isn't a PHI, fix up the
-        // insertion point.
-        if (!isa<PHINode>(Result) && isa<PHINode>(InsertPos))
-          InsertPos = InstParent->getFirstInsertionPt();
 
-        InstParent->getInstList().insert(InsertPos, Result);
 
-        eraseInstFromFunction(*I);
-      } else {
-        DEBUG(dbgs() << "IC: Mod = " << OrigI << '\n'
-                     << "    New = " << *I << '\n');
 
-        // If the instruction was modified, it's possible that it is now dead.
-        // if so, remove it.
-        if (isInstructionTriviallyDead(I, &TLI)) {
-          eraseInstFromFunction(*I);
-        } else {
-          Worklist.AddUsersToWorkList(*I);
-          Worklist.Add(I);
-        }
-      }
-      MadeIRChange = true;
-    }
+
+bool InstCombiner::run() {
+  while (!Worklist.isEmpty()) {
+    Instruction *I = Worklist.RemoveOne();
+    std::string OrigI;
+    if (handleBeforeVisit(I, OrigI)) {
+      continue;
+    }
+    if (Instruction *Result = visit(*I)) {
+      handleAfterVisit(I, Result, OrigI);
+    }
   }
 
   Worklist.Zap();
   return MadeIRChange;
 }
 
 /// Walk the function in depth-first order, adding all reachable code to the
 /// worklist.

test/Bitcode/value-with-long-name.ll

 ; Check the size of generated variable when no option is set
 ; RUN: opt -S %s -O2 -o - | FileCheck -check-prefix=CHECK-LONG %s
 ; CHECK-LONG: %{{[a-z]{4}[a-z]+}}
 
 ; Then check we correctly cap the size of newly generated non-global values name
 ; Force the size to be small so that the check works on release and debug build
 ; RUN: opt -S %s -O2 -o - -non-global-value-max-name-size=0 | FileCheck -check-prefix=CHECK-SHORT %s
 ; RUN: opt -S %s -O2 -o - -non-global-value-max-name-size=1 | FileCheck -check-prefix=CHECK-SHORT %s
 ; CHECK-SHORT-NOT: %{{[a-z][a-z]+}}
 
 define i32 @f(i32 %a, i32 %b) {
-  %c = add i32 %a, %b
-  %d = add i32 %c, %a
-  %e = add i32 %d, %b
+  %c = sub i32 %a, %b
+  %d = sub i32 %c, %a
+  %e = sub i32 %d, %b
   ret i32 %e
 }
 
 

test/Transforms/InstCombine/add.ll

 }
 
 ; Should be transformed into shl A, 1?
 
 define i32 @test12(i32 %A, i32 %B) {
 ; CHECK-LABEL: @test12(
 ; CHECK-NEXT:    br label [[X:%.*]]
 ; CHECK:       X:
-; CHECK-NEXT:    [[C_OK:%.*]] = add i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[D:%.*]] = add i32 [[C_OK]], [[A]]
+; CHECK-NEXT:    [[C_OK:%.*]] = shl i32 [[A:%.*]], 1
+; CHECK-NEXT:    [[D:%.*]] = add i32 [[C_OK]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %C_OK = add i32 %B, %A
   br label %X
 
 X:              ; preds = %0
   %D = add i32 %C_OK, %A
   ret i32 %D
;
   %D_OK = add i32 %A, %B
   %E_OK = add i32 %D_OK, %C
   %F = add i32 %E_OK, %A
   ret i32 %F
 }
 
 define i32 @test14(i32 %offset, i32 %difference) {
 ; CHECK-LABEL: @test14(
-; CHECK-NEXT:    [[TMP_2:%.*]] = and i32 [[DIFFERENCE:%.*]], 3
-; CHECK-NEXT:    [[TMP_3_OK:%.*]] = add i32 [[TMP_2]], [[OFFSET:%.*]]
-; CHECK-NEXT:    [[TMP_5_MASK:%.*]] = and i32 [[DIFFERENCE]], -4
-; CHECK-NEXT:    [[TMP_8:%.*]] = add i32 [[TMP_3_OK]], [[TMP_5_MASK]]
+; CHECK-NEXT:    [[TMP_8:%.*]] = add i32 [[DIFFERENCE:%.*]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    ret i32 [[TMP_8]]
 ;
   %tmp.2 = and i32 %difference, 3
   %tmp.3_OK = add i32 %tmp.2, %offset
   %tmp.5.mask = and i32 %difference, -4
   ; == add %offset, %difference
   %tmp.8 = add i32 %tmp.3_OK, %tmp.5.mask
   ret i32 %tmp.8

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

 
 ; PR37098 - https://bugs.llvm.org/show_bug.cgi?id=37098
 ; Reassociate bitwise logic to eliminate a shift.
 ; There are 4 commuted * 3 shift ops * 3 logic ops = 36 potential variations of this fold.
 ; Mix the commutation options to provide coverage using less tests.
 
 define i8 @and_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @and_shl(
-; CHECK-NEXT:    [[SX:%.*]] = shl i8 [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = and i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[SY]], [[A]]
+; CHECK-NEXT:    [[SY:%.*]] = and i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = shl i8 [[SY]], [[SHAMT:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[A]], %z
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = shl i8 %x, %shamt
   %sy = shl i8 %y, %shamt
   %a = and i8 %sx, %z
   %r = and i8 %sy, %a
   ret i8 %r
 }
 
 define i8 @or_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @or_shl(
-; CHECK-NEXT:    [[SX:%.*]] = shl i8 [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = or i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[SY:%.*]] = or i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = shl i8 [[SY]], [[SHAMT:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[A]], %z
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = shl i8 %x, %shamt
   %sy = shl i8 %y, %shamt
   %a = or i8 %sx, %z
   %r = or i8 %a, %sy
   ret i8 %r
 }
 
 define i8 @xor_shl(i8 %x, i8 %y, i8 %zarg, i8 %shamt) {
 ; CHECK-LABEL: @xor_shl(
 ; CHECK-NEXT:    [[Z:%.*]] = sdiv i8 42, [[ZARG:%.*]]
-; CHECK-NEXT:    [[SX:%.*]] = shl i8 [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = xor i8 [[Z]], [[SX]]
-; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[SX:%.*]] = xor i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = shl i8 [[SX]], [[SHAMT:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[Z]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %z = sdiv i8 42, %zarg ; thwart complexity-based canonicalization
   %sx = shl i8 %x, %shamt
   %sy = shl i8 %y, %shamt
   %a = xor i8 %z, %sx
   %r = xor i8 %a, %sy
   ret i8 %r
 }
 
 define i8 @and_lshr(i8 %x, i8 %y, i8 %zarg, i8 %shamt) {
 ; CHECK-LABEL: @and_lshr(
 ; CHECK-NEXT:    [[Z:%.*]] = sdiv i8 42, [[ZARG:%.*]]
-; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = and i8 [[Z]], [[SX]]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[SY]], [[A]]
+; CHECK-NEXT:    [[SX:%.*]] = and i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = lshr i8 [[SX]], [[SHAMT:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[Z]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %z = sdiv i8 42, %zarg ; thwart complexity-based canonicalization
   %sx = lshr i8 %x, %shamt
   %sy = lshr i8 %y, %shamt
   %a = and i8 %z, %sx
   %r = and i8 %sy, %a
   ret i8 %r
 }
 
 define i8 @or_lshr(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @or_lshr(
-; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = or i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = or i8 [[SY]], [[A]]
+; CHECK-NEXT:    [[SY:%.*]] = or i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = lshr i8 [[SY]], [[SHAMT:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[A]], [[Z]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = lshr i8 %x, %shamt
   %sy = lshr i8 %y, %shamt
   %a = or i8 %sx, %z
   %r = or i8 %sy, %a
   ret i8 %r
 }
 
 define i8 @xor_lshr(i8 %x, i8 %y, i8 %z, i8 %shamt) {
 ; CHECK-LABEL: @xor_lshr(
-; CHECK-NEXT:    [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = xor i8 [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[SY:%.*]] = xor i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = lshr i8 [[SY]], [[SHAMT:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], [[Z]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = lshr i8 %x, %shamt
   %sy = lshr i8 %y, %shamt
   %a = xor i8 %sx, %z
   %r = xor i8 %a, %sy
   ret i8 %r
 }
 
 define i8 @and_ashr(i8 %x, i8 %y, i8 %zarg, i8 %shamt) {
 ; CHECK-LABEL: @and_ashr(
 ; CHECK-NEXT:    [[Z:%.*]] = sdiv i8 42, [[ZARG:%.*]]
-; CHECK-NEXT:    [[SX:%.*]] = ashr i8 [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[SY:%.*]] = ashr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = and i8 [[Z]], [[SX]]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[A]], [[SY]]
+; CHECK-NEXT:    [[SX:%.*]] = and i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = ashr i8 [[SX]], [[SHAMT:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[Z]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %z = sdiv i8 42, %zarg ; thwart complexity-based canonicalization
   %sx = ashr i8 %x, %shamt
   %sy = ashr i8 %y, %shamt
   %a = and i8 %z, %sx
   %r = and i8 %a, %sy
   ret i8 %r
 }
 
 define i8 @or_ashr(i8 %x, i8 %y, i8 %zarg, i8 %shamt) {
 ; CHECK-LABEL: @or_ashr(
 ; CHECK-NEXT:    [[Z:%.*]] = sdiv i8 42, [[ZARG:%.*]]
-; CHECK-NEXT:    [[SX:%.*]] = ashr i8 [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[SY:%.*]] = ashr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = or i8 [[Z]], [[SX]]
-; CHECK-NEXT:    [[R:%.*]] = or i8 [[SY]], [[A]]
+; CHECK-NEXT:    [[SX:%.*]] = or i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = ashr i8 [[SX]], [[SHAMT:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[Z]], [[A]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %z = sdiv i8 42, %zarg ; thwart complexity-based canonicalization
   %sx = ashr i8 %x, %shamt
   %sy = ashr i8 %y, %shamt
   %a = or i8 %z, %sx
   %r = or i8 %sy, %a
   ret i8 %r
 }
 
 define <2 x i8> @xor_ashr(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z, <2 x i8> %shamt) {
 ; CHECK-LABEL: @xor_ashr(
-; CHECK-NEXT:    [[SX:%.*]] = ashr <2 x i8> [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[SY:%.*]] = ashr <2 x i8> [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[A:%.*]] = xor <2 x i8> [[SX]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i8> [[A]], [[SY]]
+; CHECK-NEXT:    [[SY:%.*]] = xor <2 x i8> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = ashr <2 x i8> [[SY]], [[SHAMT:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = xor <2 x i8> [[A]], [[Z]]
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %sx = ashr <2 x i8> %x, %shamt
   %sy = ashr <2 x i8> %y, %shamt
   %a = xor <2 x i8> %sx, %z
   %r = xor <2 x i8> %a, %sy
   ret <2 x i8> %r
 }

test/Transforms/InstCombine/bit-check-combine.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+; RUN: opt < %s -instcombine -gvn -instcombine -S | FileCheck %s --check-prefix=COMPLEX
+
+define i1 @bit-check-combine1(i32 %a, i32 %b) {
+; CHECK-LABEL: @bit-check-combine1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[A:%.*]], 7
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[B:%.*]], 56
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP0]], [[TMP1]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 0
+; CHECK-NEXT:    ret i1 [[TMP3]]
+;
+; COMPLEX-LABEL: @bit-check-combine1(
+; COMPLEX-NEXT:  entry:
+; COMPLEX-NEXT:    [[TMP0:%.*]] = and i32 [[A:%.*]], 7
+; COMPLEX-NEXT:    [[TMP1:%.*]] = and i32 [[B:%.*]], 56
+; COMPLEX-NEXT:    [[TMP2:%.*]] = or i32 [[TMP0]], [[TMP1]]
+; COMPLEX-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 0
+; COMPLEX-NEXT:    ret i1 [[TMP3]]
+;
+entry:
+  %0 = and i32 %a, 1
+  %1 = icmp eq i32 %0, 0
+  %2 = and i32 %a, 2
+  %3 = icmp eq i32 %2, 0
+  %4 = and i32 %a, 4
+  %5 = icmp eq i32 %4, 0
+  %6 = and i32 %b, 8
+  %7 = icmp eq i32 %6, 0
+  %8 = and i32 %b, 16
+  %9 = icmp eq i32 %8, 0
+  %10 = and i32 %b, 32
+  %11 = icmp eq i32 %10, 0
+  %12 = and i1 %1, %3
+  %13 = and i1 %12, %5
+  %14 = and i1 %13, %7
+  %15 = and i1 %14, %9
+  %16 = and i1 %15, %11
+  ret i1 %16
+
+}
+
+define i1 @bit-check-combine2(i32 %a, i32 %b) {
+; CHECK-LABEL: @bit-check-combine2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[A:%.*]], 7
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[B:%.*]], 56
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 16
+; CHECK-NEXT:    [[TMP4:%.*]] = and i1 [[TMP3]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP4]]
+;
+; COMPLEX-LABEL: @bit-check-combine2(
+; COMPLEX-NEXT:  entry:
+; COMPLEX-NEXT:    [[TMP0:%.*]] = and i32 [[A:%.*]], 7
+; COMPLEX-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 1
+; COMPLEX-NEXT:    [[TMP2:%.*]] = and i32 [[B:%.*]], 56
+; COMPLEX-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 16
+; COMPLEX-NEXT:    [[TMP4:%.*]] = and i1 [[TMP3]], [[TMP1]]
+; COMPLEX-NEXT:    ret i1 [[TMP4]]
+;
+entry:
+  %0 = and i32 %a, 1
+  %1 = icmp ne i32 %0, 0
+  %2 = and i32 %a, 2
+  %3 = icmp eq i32 %2, 0
+  %4 = and i32 %a, 4
+  %5 = icmp eq i32 %4, 0
+  %6 = and i32 %b, 8
+  %7 = icmp eq i32 %6, 0
+  %8 = and i32 %b, 16
+  %9 = icmp ne i32 %8, 0
+  %10 = and i32 %b, 32
+  %11 = icmp eq i32 %10, 0
+  %12 = and i1 %1, %3
+  %13 = and i1 %12, %5
+  %14 = and i1 %13, %7
+  %15 = and i1 %14, %9
+  %16 = and i1 %15, %11
+  ret i1 %16
+
+}
+
+define i1 @bit-check-combine3(i32 %a, i32 %b) {
+; CHECK-LABEL: @bit-check-combine3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[A:%.*]], 7
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 7
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[B:%.*]], 56
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 56
+; CHECK-NEXT:    [[TMP4:%.*]] = and i1 [[TMP3]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP4]]
+;
+; COMPLEX-LABEL: @bit-check-combine3(
+; COMPLEX-NEXT:  entry:
+; COMPLEX-NEXT:    [[TMP0:%.*]] = and i32 [[A:%.*]], 7
+; COMPLEX-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 7
+; COMPLEX-NEXT:    [[TMP2:%.*]] = and i32 [[B:%.*]], 56
+; COMPLEX-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 56
+; COMPLEX-NEXT:    [[TMP4:%.*]] = and i1 [[TMP3]], [[TMP1]]
+; COMPLEX-NEXT:    ret i1 [[TMP4]]
+;
+entry:
+  %0 = and i32 %a, 1
+  %1 = icmp ne i32 %0, 0
+  %2 = and i32 %a, 2
+  %3 = icmp ne i32 %2, 0
+  %4 = and i32 %a, 4
+  %5 = icmp ne i32 %4, 0
+  %6 = and i32 %b, 8
+  %7 = icmp ne i32 %6, 0
+  %8 = and i32 %b, 16
+  %9 = icmp ne i32 %8, 0
+  %10 = and i32 %b, 32
+  %11 = icmp ne i32 %10, 0
+  %12 = and i1 %1, %3
+  %13 = and i1 %12, %5
+  %14 = and i1 %13, %7
+  %15 = and i1 %14, %9
+  %16 = and i1 %15, %11
+  ret i1 %16
+
+}
+
+define i1 @bit-check-combine-256(i32* %bits0, i32* %bits1, i32* %bits2, i32* %bits3, i32* %bits4, i32* %bits5, i32* %bits6, i32* %bits7) {
+; CHECK-LABEL: @bit-check-combine-256(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[BITS0:%.*]], align 4
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], -2145382392
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[BITS1:%.*]], align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[BITS2:%.*]], align 4
+; CHECK-NEXT:    [[TMP4:%.*]] = load i32, i32* [[BITS3:%.*]], align 4
+; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP3]], [[TMP4]]
+; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[TMP5]], 2147483647
+; CHECK-NEXT:    [[TMP7:%.*]] = or i32 [[TMP2]], [[TMP6]]
+; CHECK-NEXT:    [[TMP8:%.*]] = or i32 [[TMP3]], [[TMP4]]
+; CHECK-NEXT:    [[TMP9:%.*]] = and i32 [[TMP8]], -2147483648
+; CHECK-NEXT:    [[TMP10:%.*]] = or i32 [[TMP9]], [[TMP7]]
+; CHECK-NEXT:    [[TMP11:%.*]] = load i32, i32* [[BITS4:%.*]], align 4
+; CHECK-NEXT:    [[TMP12:%.*]] = load i32, i32* [[BITS5:%.*]], align 4
+; CHECK-NEXT:    [[TMP13:%.*]] = or i32 [[TMP11]], [[TMP12]]
+; CHECK-NEXT:    [[TMP14:%.*]] = and i32 [[TMP13]], 2147483647
+; CHECK-NEXT:    [[TMP15:%.*]] = or i32 [[TMP10]], [[TMP14]]
+; CHECK-NEXT:    [[TMP16:%.*]] = or i32 [[TMP11]], [[TMP12]]
+; CHECK-NEXT:    [[TMP17:%.*]] = and i32 [[TMP16]], -2147483648
+; CHECK-NEXT:    [[TMP18:%.*]] = or i32 [[TMP17]], [[TMP15]]
+; CHECK-NEXT:    [[TMP19:%.*]] = load i32, i32* [[BITS6:%.*]], align 4
+; CHECK-NEXT:    [[TMP20:%.*]] = load i32, i32* [[BITS7:%.*]], align 4
+; CHECK-NEXT:    [[TMP21:%.*]] = or i32 [[TMP19]], [[TMP20]]
+; CHECK-NEXT:    [[TMP22:%.*]] = and i32 [[TMP21]], 2147483647
+; CHECK-NEXT:    [[TMP23:%.*]] = or i32 [[TMP18]], [[TMP22]]
+; CHECK-NEXT:    [[TMP24:%.*]] = or i32 [[TMP19]], [[TMP20]]
+; CHECK-NEXT:    [[TMP25:%.*]] = and i32 [[TMP24]], -2147483648
+; CHECK-NEXT:    [[TMP26:%.*]] = or i32 [[TMP25]], [[TMP23]]
+; CHECK-NEXT:    [[TMP27:%.*]] = icmp eq i32 [[TMP26]], 0
+; CHECK-NEXT:    [[TMP28:%.*]] = and i1 [[TMP27]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP28]]
+;
+; COMPLEX-LABEL: @bit-check-combine-256(
+; COMPLEX-NEXT:  entry:
+; COMPLEX-NEXT:    [[TMP0:%.*]] = load i32, i32* [[BITS0:%.*]], align 4
+; COMPLEX-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], -2145382392
+; COMPLEX-NEXT:    [[TMP2:%.*]] = load i32, i32* [[BITS1:%.*]], align 4
+; COMPLEX-NEXT:    [[TMP3:%.*]] = load i32, i32* [[BITS2:%.*]], align 4
+; COMPLEX-NEXT:    [[TMP4:%.*]] = load i32, i32* [[BITS3:%.*]], align 4
+; COMPLEX-NEXT:    [[TMP5:%.*]] = or i32 [[TMP3]], [[TMP4]]
+; COMPLEX-NEXT:    [[TMP6:%.*]] = load i32, i32* [[BITS4:%.*]], align 4
+; COMPLEX-NEXT:    [[TMP7:%.*]] = load i32, i32* [[BITS5:%.*]], align 4
+; COMPLEX-NEXT:    [[TMP8:%.*]] = or i32 [[TMP6]], [[TMP7]]
+; COMPLEX-NEXT:    [[TMP9:%.*]] = or i32 [[TMP5]], [[TMP8]]
+; COMPLEX-NEXT:    [[TMP10:%.*]] = load i32, i32* [[BITS6:%.*]], align 4
+; COMPLEX-NEXT:    [[TMP11:%.*]] = load i32, i32* [[BITS7:%.*]], align 4
+; COMPLEX-NEXT:    [[TMP12:%.*]] = or i32 [[TMP10]], [[TMP11]]
+; COMPLEX-NEXT:    [[TMP13:%.*]] = or i32 [[TMP9]], [[TMP12]]
+; COMPLEX-NEXT:    [[TMP14:%.*]] = or i32 [[TMP2]], [[TMP13]]
+; COMPLEX-NEXT:    [[TMP15:%.*]] = icmp eq i32 [[TMP14]], 0
+; COMPLEX-NEXT:    [[TMP16:%.*]] = and i1 [[TMP15]], [[TMP1]]
+; COMPLEX-NEXT:    ret i1 [[TMP16]]
+;
+entry:
+
+  %0 = load i32, i32* %bits0, align 4
+  %and.i = and i32 %0, 1
+  %cmp.i = icmp ne i32 %and.i, 0
+  %and.i3079 = and i32 %0, 2
+  %cmp.i3080 = icmp ne i32 %and.i3079, 0
+  %and2824.demorgan = or i1 %cmp.i, %cmp.i3080
+  %and.i3081 = and i32 %0, 4
+  %cmp.i3082 = icmp ne i32 %and.i3081, 0
+  %and72825.demorgan = or i1 %and2824.demorgan, %cmp.i3082
+  %and72825 = xor i1 %and72825.demorgan, true
+  %and.i3083 = and i32 %0, 8
+  %cmp.i3084 = icmp ne i32 %and.i3083, 0
+  %and102826 = and i1 %cmp.i3084, %and72825
+  %and.i3085 = and i32 %0, 16
+  %cmp.i3086 = icmp ne i32 %and.i3085, 0
+  %lnot12 = xor i1 %cmp.i3086, true
+  %and142827 = and i1 %and102826, %lnot12
+  %and.i3087 = and i32 %0, 32
+  %cmp.i3088 = icmp ne i32 %and.i3087, 0
+  %lnot16 = xor i1 %cmp.i3088, true
+  %and182828 = and i1 %and142827, %lnot16
+  %and.i3089 = and i32 %0, 64
+  %cmp.i3090 = icmp ne i32 %and.i3089, 0
+  %lnot20 = xor i1 %cmp.i3090, true
+  %and222829 = and i1 %and182828, %lnot20
+  %1 = trunc i32 %0 to i8
+  %cmp.i3091 = icmp slt i8 %1, 0
+  %lnot24 = xor i1 %cmp.i3091, true
+  %and262830 = and i1 %and222829, %lnot24
+  %and.i3092 = and i32 %0, 256
+  %cmp.i3093 = icmp ne i32 %and.i3092, 0
+  %lnot28 = xor i1 %cmp.i3093, true
+  %and302831 = and i1 %and262830, %lnot28
+  %and.i3094 = and i32 %0, 512
+  %cmp.i3095 = icmp ne i32 %and.i3094, 0
+  %lnot32 = xor i1 %cmp.i3095, true
+  %and342832 = and i1 %and302831, %lnot32
+  %and.i3096 = and i32 %0, 1024
+  %cmp.i3097 = icmp ne i32 %and.i3096, 0
+  %lnot36 = xor i1 %cmp.i3097, true
+  %and382833 = and i1 %and342832, %lnot36
+  %and.i3098 = and i32 %0, 2048
+  %cmp.i3099 = icmp ne i32 %and.i3098, 0
+  %lnot40 = xor i1 %cmp.i3099, true
+  %and422834 = and i1 %and382833, %lnot40
+  %and.i3100 = and i32 %0, 4096
+  %cmp.i3101 = icmp ne i32 %and.i3100, 0
+  %and452835 = and i1 %and422834, %cmp.i3101
+  %and.i3102 = and i32 %0, 8192
+  %cmp.i3103 = icmp ne i32 %and.i3102, 0
+  %lnot47 = xor i1 %cmp.i3103, true
+  %and492836 = and i1 %and452835, %lnot47
+  %and.i3104 = and i32 %0, 16384
+  %cmp.i3105 = icmp ne i32 %and.i3104, 0
+  %lnot51 = xor i1 %cmp.i3105, true
+  %and532837 = and i1 %and492836, %lnot51
+  %2 = trunc i32 %0 to i16
+  %cmp.i3106 = icmp slt i16 %2, 0
+  %lnot55 = xor i1 %cmp.i3106, true
+  %and572838 = and i1 %and532837, %lnot55
+  %and.i3107 = and i32 %0, 65536
+  %cmp.i3108 = icmp ne i32 %and.i3107, 0
+  %lnot59 = xor i1 %cmp.i3108, true
+  %and612839 = and i1 %and572838, %lnot59
+  %and.i3109 = and i32 %0, 131072
+  %cmp.i3110 = icmp ne i32 %and.i3109, 0
+  %lnot63 = xor i1 %cmp.i3110, true
+  %and652840 = and i1 %and612839, %lnot63
+  %and.i3111 = and i32 %0, 262144
+  %cmp.i3112 = icmp ne i32 %and.i3111, 0
+  %lnot67 = xor i1 %cmp.i3112, true
+  %and692841 = and i1 %and652840, %lnot67
+  %and.i3113 = and i32 %0, 524288
+  %cmp.i3114 = icmp ne i32 %and.i3113, 0
+  %lnot71 = xor i1 %cmp.i3114, true
+  %and732842 = and i1 %and692841, %lnot71
+  %and.i3115 = and i32 %0, 1048576
+  %cmp.i3116 = icmp ne i32 %and.i3115, 0
+  %lnot75 = xor i1 %cmp.i3116, true
+  %and772843 = and i1 %and732842, %lnot75
+  %and.i3117 = and i32 %0, 2097152
+  %cmp.i3118 = icmp ne i32 %and.i3117, 0
+  %and802844 = and i1 %and772843, %cmp.i3118
+  %and.i3119 = and i32 %0, 4194304
+  %cmp.i3120 = icmp ne i32 %and.i3119, 0
+  %lnot82 = xor i1 %cmp.i3120, true
+  %and842845 = and i1 %and802844, %lnot82
+  %and.i3121 = and i32 %0, 8388608
+  %cmp.i3122 = icmp ne i32 %and.i3121, 0
+  %lnot86 = xor i1 %cmp.i3122, true
+  %and882846 = and i1 %and842845, %lnot86
+  %and.i3123 = and i32 %0, 16777216
+  %cmp.i3124 = icmp ne i32 %and.i3123, 0
+  %lnot90 = xor i1 %cmp.i3124, true
+  %and922847 = and i1 %and882846, %lnot90
+  %and.i3125 = and i32 %0, 33554432
+  %cmp.i3126 = icmp ne i32 %and.i3125, 0
+  %lnot94 = xor i1 %cmp.i3126, true
+  %and962848 = and i1 %and922847, %lnot94
+  %and.i3127 = and i32 %0, 67108864
+  %cmp.i3128 = icmp ne i32 %and.i3127, 0
+  %lnot98 = xor i1 %cmp.i3128, true
+  %and1002849 = and i1 %and962848, %lnot98
+  %and.i3129 = and i32 %0, 134217728
+  %cmp.i3130 = icmp ne i32 %and.i3129, 0
+  %lnot102 = xor i1 %cmp.i3130, true
+  %and1042850 = and i1 %and1002849, %lnot102
+  %and.i3131 = and i32 %0, 268435456
+  %cmp.i3132 = icmp ne i32 %and.i3131, 0
+  %lnot106 = xor i1 %cmp.i3132, true
+  %and1082851 = and i1 %and1042850, %lnot106
+  %and.i3133 = and i32 %0, 536870912
+  %cmp.i3134 = icmp ne i32 %and.i3133, 0
+  %lnot110 = xor i1 %cmp.i3134, true
+  %and1122852 = and i1 %and1082851, %lnot110
+  %and.i3135 = and i32 %0, 1073741824
+  %cmp.i3136 = icmp ne i32 %and.i3135, 0
+  %lnot114 = xor i1 %cmp.i3136, true
+  %and1162853 = and i1 %and1122852, %lnot114
+  %cmp.i3137 = icmp slt i32 %0, 0
+  %and1192854 = and i1 %and1162853, %cmp.i3137
+
+  %3 = load i32, i32* %bits1, align 4
+  %and.i3138 = and i32 %3, 1
+  %cmp.i3139 = icmp ne i32 %and.i3138, 0
+  %lnot121 = xor i1 %cmp.i3139, true
+  %and1232855 = and i1 %and1192854, %lnot121
+  %and.i3140 = and i32 %3, 2
+  %cmp.i3141 = icmp ne i32 %and.i3140, 0
+  %lnot125 = xor i1 %cmp.i3141, true
+  %and1272856 = and i1 %and1232855, %lnot125
+  %and.i3142 = and i32 %3, 4
+  %cmp.i3143 = icmp ne i32 %and.i3142, 0
+  %lnot129 = xor i1 %cmp.i3143, true
+  %and1312857 = and i1 %and1272856, %lnot129
+  %and.i3144 = and i32 %3, 8
+  %cmp.i3145 = icmp ne i32 %and.i3144, 0
+  %lnot133 = xor i1 %cmp.i3145, true
+  %and1352858 = and i1 %and1312857, %lnot133
+  %and.i3146 = and i32 %3, 16
+  %cmp.i3147 = icmp ne i32 %and.i3146, 0
+  %lnot137 = xor i1 %cmp.i3147, true
+  %and1392859 = and i1 %and1352858, %lnot137
+  %and.i3148 = and i32 %3, 32
+  %cmp.i3149 = icmp ne i32 %and.i3148, 0
+  %lnot141 = xor i1 %cmp.i3149, true
+  %and1432860 = and i1 %and1392859, %lnot141
+  %and.i3150 = and i32 %3, 64
+  %cmp.i3151 = icmp ne i32 %and.i3150, 0
+  %lnot145 = xor i1 %cmp.i3151, true
+  %and1472861 = and i1 %and1432860, %lnot145
+  %4 = trunc i32 %3 to i8
+  %cmp.i3152 = icmp slt i8 %4, 0
+  %lnot149 = xor i1 %cmp.i3152, true
+  %and1512862 = and i1 %and1472861, %lnot149
+  %and.i3153 = and i32 %3, 256
+  %cmp.i3154 = icmp ne i32 %and.i3153, 0
+  %lnot153 = xor i1 %cmp.i3154, true
+  %and1552863 = and i1 %and1512862, %lnot153
+  %and.i3155 = and i32 %3, 512
+  %cmp.i3156 = icmp ne i32 %and.i3155, 0
+  %lnot157 = xor i1 %cmp.i3156, true
+  %and1592864 = and i1 %and1552863, %lnot157
+  %and.i3157 = and i32 %3, 1024
+  %cmp.i3158 = icmp ne i32 %and.i3157, 0
+  %lnot161 = xor i1 %cmp.i3158, true
+  %and1632865 = and i1 %and1592864, %lnot161
+  %and.i3159 = and i32 %3, 2048
+  %cmp.i3160 = icmp ne i32 %and.i3159, 0
+  %lnot165 = xor i1 %cmp.i3160, true
+  %and1672866 = and i1 %and1632865, %lnot165
+  %and.i3161 = and i32 %3, 4096
+  %cmp.i3162 = icmp ne i32 %and.i3161, 0
+  %lnot169 = xor i1 %cmp.i3162, true
+  %and1712867 = and i1 %and1672866, %lnot169
+  %and.i3163 = and i32 %3, 8192
+  %cmp.i3164 = icmp ne i32 %and.i3163, 0
+  %lnot173 = xor i1 %cmp.i3164, true
+  %and1752868 = and i1 %and1712867, %lnot173
+  %and.i3165 = and i32 %3, 16384
+  %cmp.i3166 = icmp ne i32 %and.i3165, 0
+  %lnot177 = xor i1 %cmp.i3166, true
+  %and1792869 = and i1 %and1752868, %lnot177
+  %5 = trunc i32 %3 to i16
+  %cmp.i3167 = icmp slt i16 %5, 0
+  %lnot181 = xor i1 %cmp.i3167, true
+  %and1832870 = and i1 %and1792869, %lnot181
+  %and.i3168 = and i32 %3, 65536
+  %cmp.i3169 = icmp ne i32 %and.i3168, 0
+  %lnot185 = xor i1 %cmp.i3169, true
+  %and1872871 = and i1 %and1832870, %lnot185
+  %and.i3170 = and i32 %3, 131072
+  %cmp.i3171 = icmp ne i32 %and.i3170, 0
+  %lnot189 = xor i1 %cmp.i3171, true
+  %and1912872 = and i1 %and1872871, %lnot189
+  %and.i3172 = and i32 %3, 262144
+  %cmp.i3173 = icmp ne i32 %and.i3172, 0
+  %lnot193 = xor i1 %cmp.i3173, true
+  %and1952873 = and i1 %and1912872, %lnot193
+  %and.i3174 = and i32 %3, 524288
+  %cmp.i3175 = icmp ne i32 %and.i3174, 0
+  %lnot197 = xor i1 %cmp.i3175, true
+  %and1992874 = and i1 %and1952873, %lnot197
+  %and.i3176 = and i32 %3, 1048576
+  %cmp.i3177 = icmp ne i32 %and.i3176, 0
+  %lnot201 = xor i1 %cmp.i3177, true
+  %and2032875 = and i1 %and1992874, %lnot201
+  %and.i3178 = and i32 %3, 2097152
+  %cmp.i3179 = icmp ne i32 %and.i3178, 0
+  %lnot205 = xor i1 %cmp.i3179, true
+  %and2072876 = and i1 %and2032875, %lnot205
+  %and.i3180 = and i32 %3, 4194304
+  %cmp.i3181 = icmp ne i32 %and.i3180, 0
+  %lnot209 = xor i1 %cmp.i3181, true
+  %and2112877 = and i1 %and2072876, %lnot209
+  %and.i3182 = and i32 %3, 8388608
+  %cmp.i3183 = icmp ne i32 %and.i3182, 0
+  %lnot213 = xor i1 %cmp.i3183, true
+  %and2152878 = and i1 %and2112877, %lnot213
+  %and.i3184 = and i32 %3, 16777216
+  %cmp.i3185 = icmp ne i32 %and.i3184, 0
+  %lnot217 = xor i1 %cmp.i3185, true
+  %and2192879 = and i1 %and2152878, %lnot217
+  %and.i3186 = and i32 %3, 33554432
+  %cmp.i3187 = icmp ne i32 %and.i3186, 0
+  %lnot221 = xor i1 %cmp.i3187, true
+  %and2232880 = and i1 %and2192879, %lnot221
+  %and.i3188 = and i32 %3, 67108864
+  %cmp.i3189 = icmp ne i32 %and.i3188, 0
+  %lnot225 = xor i1 %cmp.i3189, true
+  %and2272881 = and i1 %and2232880, %lnot225
+  %and.i3190 = and i32 %3, 134217728
+  %cmp.i3191 = icmp ne i32 %and.i3190, 0
+  %lnot229 = xor i1 %cmp.i3191, true
+  %and2312882 = and i1 %and2272881, %lnot229
+  %and.i3192 = and i32 %3, 268435456
+  %cmp.i3193 = icmp ne i32 %and.i3192, 0
+  %lnot233 = xor i1 %cmp.i3193, true
+  %and2352883 = and i1 %and2312882, %lnot233
+  %and.i3194 = and i32 %3, 536870912
+  %cmp.i3195 = icmp ne i32 %and.i3194, 0
+  %lnot237 = xor i1 %cmp.i3195, true
+  %and2392884 = and i1 %and2352883, %lnot237
+  %and.i3196 = and i32 %3, 1073741824
+  %cmp.i3197 = icmp ne i32 %and.i3196, 0
+  %lnot241 = xor i1 %cmp.i3197, true
+  %and2432885 = and i1 %and2392884, %lnot241
+  %cmp.i3198 = icmp slt i32 %3, 0
+  %lnot245 = xor i1 %cmp.i3198, true
+  %and2472886 = and i1 %and2432885, %lnot245
+
+  %6 = load i32, i32* %bits2, align 4
+  %and.i3199 = and i32 %6, 1
+  %cmp.i3200 = icmp ne i32 %and.i3199, 0
+  %lnot249 = xor i1 %cmp.i3200, true
+  %and2512887 = and i1 %and2472886, %lnot249
+  %and.i3201 = and i32 %6, 2
+  %cmp.i3202 = icmp ne i32 %and.i3201, 0
+  %lnot253 = xor i1 %cmp.i3202, true
+  %and2552888 = and i1 %and2512887, %lnot253
+  %and.i3203 = and i32 %6, 4
+  %cmp.i3204 = icmp ne i32 %and.i3203, 0
+  %lnot257 = xor i1 %cmp.i3204, true
+  %and2592889 = and i1 %and2552888, %lnot257
+  %and.i3205 = and i32 %6, 8
+  %cmp.i3206 = icmp ne i32 %and.i3205, 0
+  %lnot261 = xor i1 %cmp.i3206, true
+  %and2632890 = and i1 %and2592889, %lnot261
+  %and.i3207 = and i32 %6, 16
+  %cmp.i3208 = icmp ne i32 %and.i3207, 0
+  %lnot265 = xor i1 %cmp.i3208, true
+  %and2672891 = and i1 %and2632890, %lnot265
+  %and.i3209 = and i32 %6, 32
+  %cmp.i3210 = icmp ne i32 %and.i3209, 0
+  %lnot269 = xor i1 %cmp.i3210, true
+  %and2712892 = and i1 %and2672891, %lnot269
+  %and.i3211 = and i32 %6, 64
+  %cmp.i3212 = icmp ne i32 %and.i3211, 0
+  %lnot273 = xor i1 %cmp.i3212, true
+  %and2752893 = and i1 %and2712892, %lnot273
+  %7 = trunc i32 %6 to i8
+  %cmp.i3213 = icmp slt i8 %7, 0
+  %lnot277 = xor i1 %cmp.i3213, true
+  %and2792894 = and i1 %and2752893, %lnot277
+  %and.i3214 = and i32 %6, 256
+  %cmp.i3215 = icmp ne i32 %and.i3214, 0
+  %lnot281 = xor i1 %cmp.i3215, true
+  %and2832895 = and i1 %and2792894, %lnot281
+  %and.i3216 = and i32 %6, 512
+  %cmp.i3217 = icmp ne i32 %and.i3216, 0
+  %lnot285 = xor i1 %cmp.i3217, true
+  %and2872896 = and i1 %and2832895, %lnot285
+  %and.i3218 = and i32 %6, 1024
+  %cmp.i3219 = icmp ne i32 %and.i3218, 0
+  %lnot289 = xor i1 %cmp.i3219, true
+  %and2912897 = and i1 %and2872896, %lnot289
+  %and.i3220 = and i32 %6, 2048
+  %cmp.i3221 = icmp ne i32 %and.i3220, 0
+  %lnot293 = xor i1 %cmp.i3221, true
+  %and2952898 = and i1 %and2912897, %lnot293
+  %and.i3222 = and i32 %6, 4096
+  %cmp.i3223 = icmp ne i32 %and.i3222, 0
+  %lnot297 = xor i1 %cmp.i3223, true
+  %and2992899 = and i1 %and2952898, %lnot297
+  %and.i3224 = and i32 %6, 8192
+  %cmp.i3225 = icmp ne i32 %and.i3224, 0
+  %lnot301 = xor i1 %cmp.i3225, true
+  %and3032900 = and i1 %and2992899, %lnot301
+  %and.i3226 = and i32 %6, 16384
+  %cmp.i3227 = icmp ne i32 %and.i3226, 0
+  %lnot305 = xor i1 %cmp.i3227, true
+  %and3072901 = and i1 %and3032900, %lnot305
+  %8 = trunc i32 %6 to i16
+  %cmp.i3228 = icmp slt i16 %8, 0
+  %lnot309 = xor i1 %cmp.i3228, true
+  %and3112902 = and i1 %and3072901, %lnot309
+  %and.i3229 = and i32 %6, 65536
+  %cmp.i3230 = icmp ne i32 %and.i3229, 0
+  %lnot313 = xor i1 %cmp.i3230, true
+  %and3152903 = and i1 %and3112902, %lnot313
+  %and.i3231 = and i32 %6, 131072
+  %cmp.i3232 = icmp ne i32 %and.i3231, 0
+  %lnot317 = xor i1 %cmp.i3232, true
+  %and3192904 = and i1 %and3152903, %lnot317
+  %and.i3233 = and i32 %6, 262144
+  %cmp.i3234 = icmp ne i32 %and.i3233, 0
+  %lnot321 = xor i1 %cmp.i3234, true
+  %and3232905 = and i1 %and3192904, %lnot321
+  %and.i3235 = and i32 %6, 524288
+  %cmp.i3236 = icmp ne i32 %and.i3235, 0
+  %lnot325 = xor i1 %cmp.i3236, true
+  %and3272906 = and i1 %and3232905, %lnot325
+  %and.i3237 = and i32 %6, 1048576
+  %cmp.i3238 = icmp ne i32 %and.i3237, 0
+  %lnot329 = xor i1 %cmp.i3238, true
+  %and3312907 = and i1 %and3272906, %lnot329
+  %and.i3239 = and i32 %6, 2097152
+  %cmp.i3240 = icmp ne i32 %and.i3239, 0
+  %lnot333 = xor i1 %cmp.i3240, true
+  %and3352908 = and i1 %and3312907, %lnot333
+  %and.i3241 = and i32 %6, 4194304
+  %cmp.i3242 = icmp ne i32 %and.i3241, 0
+  %lnot337 = xor i1 %cmp.i3242, true
+  %and3392909 = and i1 %and3352908, %lnot337
+  %and.i3243 = and i32 %6, 8388608
+  %cmp.i3244 = icmp ne i32 %and.i3243, 0
+  %lnot341 = xor i1 %cmp.i3244, true
+  %and3432910 = and i1 %and3392909, %lnot341
+  %and.i3245 = and i32 %6, 16777216
+  %cmp.i3246 = icmp ne i32 %and.i3245, 0
+  %lnot345 = xor i1 %cmp.i3246, true
+  %and3472911 = and i1 %and3432910, %lnot345
+  %and.i3247 = and i32 %6, 33554432
+  %cmp.i3248 = icmp ne i32 %and.i3247, 0
+  %lnot349 = xor i1 %cmp.i3248, true
+  %and3512912 = and i1 %and3472911, %lnot349
+  %and.i3249 = and i32 %6, 67108864
+  %cmp.i3250 = icmp ne i32 %and.i3249, 0
+  %lnot353 = xor i1 %cmp.i3250, true
+  %and3552913 = and i1 %and3512912, %lnot353
+  %and.i3251 = and i32 %6, 134217728
+  %cmp.i3252 = icmp ne i32 %and.i3251, 0
+  %lnot357 = xor i1 %cmp.i3252, true
+  %and3592914 = and i1 %and3552913, %lnot357
+  %and.i3253 = and i32 %6, 268435456
+  %cmp.i3254 = icmp ne i32 %and.i3253, 0
+  %lnot361 = xor i1 %cmp.i3254, true
+  %and3632915 = and i1 %and3592914, %lnot361
+  %and.i3255 = and i32 %6, 536870912
+  %cmp.i3256 = icmp ne i32 %and.i3255, 0
+  %lnot365 = xor i1 %cmp.i3256, true
+  %and3672916 = and i1 %and3632915, %lnot365
+  %and.i3257 = and i32 %6, 1073741824
+  %cmp.i3258 = icmp ne i32 %and.i3257, 0
+  %lnot369 = xor i1 %cmp.i3258, true
+  %and3712917 = and i1 %and3672916, %lnot369
+  %cmp.i3259 = icmp slt i32 %6, 0
+  %lnot373 = xor i1 %cmp.i3259, true
+  %and3752918 = and i1 %and3712917, %lnot373
+
+  %9 = load i32, i32* %bits3, align 4
+  %and.i3260 = and i32 %9, 1
+  %cmp.i3261 = icmp ne i32 %and.i3260, 0
+  %lnot377 = xor i1 %cmp.i3261, true
+  %and3792919 = and i1 %and3752918, %lnot377
+  %and.i3262 = and i32 %9, 2
+  %cmp.i3263 = icmp ne i32 %and.i3262, 0
+  %lnot381 = xor i1 %cmp.i3263, true
+  %and3832920 = and i1 %and3792919, %lnot381
+  %and.i3264 = and i32 %9, 4
+  %cmp.i3265 = icmp ne i32 %and.i3264, 0
+  %lnot385 = xor i1 %cmp.i3265, true
+  %and3872921 = and i1 %and3832920, %lnot385
+  %and.i3266 = and i32 %9, 8
+  %cmp.i3267 = icmp ne i32 %and.i3266, 0
+  %lnot389 = xor i1 %cmp.i3267, true
+  %and3912922 = and i1 %and3872921, %lnot389
+  %and.i3268 = and i32 %9, 16
+  %cmp.i3269 = icmp ne i32 %and.i3268, 0
+  %lnot393 = xor i1 %cmp.i3269, true
+  %and3952923 = and i1 %and3912922, %lnot393
+  %and.i3270 = and i32 %9, 32
+  %cmp.i3271 = icmp ne i32 %and.i3270, 0
+  %lnot397 = xor i1 %cmp.i3271, true
+  %and3992924 = and i1 %and3952923, %lnot397
+  %and.i3272 = and i32 %9, 64
+  %cmp.i3273 = icmp ne i32 %and.i3272, 0
+  %lnot401 = xor i1 %cmp.i3273, true
+  %and4032925 = and i1 %and3992924, %lnot401
+  %10 = trunc i32 %9 to i8
+  %cmp.i3274 = icmp slt i8 %10, 0
+  %lnot405 = xor i1 %cmp.i3274, true
+  %and4072926 = and i1 %and4032925, %lnot405
+  %and.i3275 = and i32 %9, 256
+  %cmp.i3276 = icmp ne i32 %and.i3275, 0
+  %lnot409 = xor i1 %cmp.i3276, true
+  %and4112927 = and i1 %and4072926, %lnot409
+  %and.i3277 = and i32 %9, 512
+  %cmp.i3278 = icmp ne i32 %and.i3277, 0
+  %lnot413 = xor i1 %cmp.i3278, true
+  %and4152928 = and i1 %and4112927, %lnot413
+  %and.i3279 = and i32 %9, 1024
+  %cmp.i3280 = icmp ne i32 %and.i3279, 0
+  %lnot417 = xor i1 %cmp.i3280, true
+  %and4192929 = and i1 %and4152928, %lnot417
+  %and.i3281 = and i32 %9, 2048
+  %cmp.i3282 = icmp ne i32 %and.i3281, 0
+  %lnot421 = xor i1 %cmp.i3282, true
+  %and4232930 = and i1 %and4192929, %lnot421
+  %and.i3283 = and i32 %9, 4096
+  %cmp.i3284 = icmp ne i32 %and.i3283, 0
+  %lnot425 = xor i1 %cmp.i3284, true
+  %and4272931 = and i1 %and4232930, %lnot425
+  %and.i3285 = and i32 %9, 8192
+  %cmp.i3286 = icmp ne i32 %and.i3285, 0
+  %lnot429 = xor i1 %cmp.i3286, true
+  %and4312932 = and i1 %and4272931, %lnot429
+  %and.i3287 = and i32 %9, 16384
+  %cmp.i3288 = icmp ne i32 %and.i3287, 0
+  %lnot433 = xor i1 %cmp.i3288, true
+  %and4352933 = and i1 %and4312932, %lnot433
+  %11 = trunc i32 %9 to i16
+  %cmp.i3289 = icmp slt i16 %11, 0
+  %lnot437 = xor i1 %cmp.i3289, true
+  %and4392934 = and i1 %and4352933, %lnot437
+  %and.i3290 = and i32 %9, 65536
+  %cmp.i3291 = icmp ne i32 %and.i3290, 0
+  %lnot441 = xor i1 %cmp.i3291, true
+  %and4432935 = and i1 %and4392934, %lnot441
+  %and.i3292 = and i32 %9, 131072
+  %cmp.i3293 = icmp ne i32 %and.i3292, 0
+  %lnot445 = xor i1 %cmp.i3293, true
+  %and4472936 = and i1 %and4432935, %lnot445
+  %and.i3294 = and i32 %9, 262144
+  %cmp.i3295 = icmp ne i32 %and.i3294, 0
+  %lnot449 = xor i1 %cmp.i3295, true
+  %and4512937 = and i1 %and4472936, %lnot449
+  %and.i3296 = and i32 %9, 524288
+  %cmp.i3297 = icmp ne i32 %and.i3296, 0
+  %lnot453 = xor i1 %cmp.i3297, true
+  %and4552938 = and i1 %and4512937, %lnot453
+  %and.i3298 = and i32 %9, 1048576
+  %cmp.i3299 = icmp ne i32 %and.i3298, 0
+  %lnot457 = xor i1 %cmp.i3299, true
+  %and4592939 = and i1 %and4552938, %lnot457
+  %and.i3300 = and i32 %9, 2097152
+  %cmp.i3301 = icmp ne i32 %and.i3300, 0
+  %lnot461 = xor i1 %cmp.i3301, true
+  %and4632940 = and i1 %and4592939, %lnot461
+  %and.i3302 = and i32 %9, 4194304
+  %cmp.i3303 = icmp ne i32 %and.i3302, 0
+  %lnot465 = xor i1 %cmp.i3303, true
+  %and4672941 = and i1 %and4632940, %lnot465
+  %and.i3304 = and i32 %9, 8388608
+  %cmp.i3305 = icmp ne i32 %and.i3304, 0
+  %lnot469 = xor i1 %cmp.i3305, true
+  %and4712942 = and i1 %and4672941, %lnot469
+  %and.i3306 = and i32 %9, 16777216
+  %cmp.i3307 = icmp ne i32 %and.i3306, 0
+  %lnot473 = xor i1 %cmp.i3307, true
+  %and4752943 = and i1 %and4712942, %lnot473
+  %and.i3308 = and i32 %9, 33554432
+  %cmp.i3309 = icmp ne i32 %and.i3308, 0
+  %lnot477 = xor i1 %cmp.i3309, true
+  %and4792944 = and i1 %and4752943, %lnot477
+  %and.i3310 = and i32 %9, 67108864
+  %cmp.i3311 = icmp ne i32 %and.i3310, 0
+  %lnot481 = xor i1 %cmp.i3311, true
+  %and4832945 = and i1 %and4792944, %lnot481
+  %and.i3312 = and i32 %9, 134217728
+  %cmp.i3313 = icmp ne i32 %and.i3312, 0
+  %lnot485 = xor i1 %cmp.i3313, true
+  %and4872946 = and i1 %and4832945, %lnot485
+  %and.i3314 = and i32 %9, 268435456
+  %cmp.i3315 = icmp ne i32 %and.i3314, 0
+  %lnot489 = xor i1 %cmp.i3315, true
+  %and4912947 = and i1 %and4872946, %lnot489
+  %and.i3316 = and i32 %9, 536870912
+  %cmp.i3317 = icmp ne i32 %and.i3316, 0
+  %lnot493 = xor i1 %cmp.i3317, true
+  %and4952948 = and i1 %and4912947, %lnot493
+  %and.i3318 = and i32 %9, 1073741824
+  %cmp.i3319 = icmp ne i32 %and.i3318, 0
+  %lnot497 = xor i1 %cmp.i3319, true
+  %and4992949 = and i1 %and4952948, %lnot497
+  %cmp.i3320 = icmp slt i32 %9, 0
+  %lnot501 = xor i1 %cmp.i3320, true
+  %and5032950 = and i1 %and4992949, %lnot501
+
+  %12 = load i32, i32* %bits4, align 4
+  %and.i3321 = and i32 %12, 1
+  %cmp.i3322 = icmp ne i32 %and.i3321, 0
+  %lnot505 = xor i1 %cmp.i3322, true
+  %and5072951 = and i1 %and5032950, %lnot505
+  %and.i3323 = and i32 %12, 2
+  %cmp.i3324 = icmp ne i32 %and.i3323, 0
+  %lnot509 = xor i1 %cmp.i3324, true
+  %and5112952 = and i1 %and5072951, %lnot509
+  %and.i3325 = and i32 %12, 4
+  %cmp.i3326 = icmp ne i32 %and.i3325, 0
+  %lnot513 = xor i1 %cmp.i3326, true
+  %and5152953 = and i1 %and5112952, %lnot513
+  %and.i3327 = and i32 %12, 8
+  %cmp.i3328 = icmp ne i32 %and.i3327, 0
+  %lnot517 = xor i1 %cmp.i3328, true
+  %and5192954 = and i1 %and5152953, %lnot517
+  %and.i3329 = and i32 %12, 16
+  %cmp.i3330 = icmp ne i32 %and.i3329, 0
+  %lnot521 = xor i1 %cmp.i3330, true
+  %and5232955 = and i1 %and5192954, %lnot521
+  %and.i3331 = and i32 %12, 32
+  %cmp.i3332 = icmp ne i32 %and.i3331, 0
+  %lnot525 = xor i1 %cmp.i3332, true
+  %and5272956 = and i1 %and5232955, %lnot525
+  %and.i3333 = and i32 %12, 64
+  %cmp.i3334 = icmp ne i32 %and.i3333, 0
+  %lnot529 = xor i1 %cmp.i3334, true
+  %and5312957 = and i1 %and5272956, %lnot529
+  %13 = trunc i32 %12 to i8
+  %cmp.i3335 = icmp slt i8 %13, 0
+  %lnot533 = xor i1 %cmp.i3335, true
+  %and5352958 = and i1 %and5312957, %lnot533
+  %and.i3336 = and i32 %12, 256
+  %cmp.i3337 = icmp ne i32 %and.i3336, 0
+  %lnot537 = xor i1 %cmp.i3337, true
+  %and5392959 = and i1 %and5352958, %lnot537
+  %and.i3338 = and i32 %12, 512
+  %cmp.i3339 = icmp ne i32 %and.i3338, 0
+  %lnot541 = xor i1 %cmp.i3339, true
+  %and5432960 = and i1 %and5392959, %lnot541
+  %and.i3340 = and i32 %12, 1024
+  %cmp.i3341 = icmp ne i32 %and.i3340, 0
+  %lnot545 = xor i1 %cmp.i3341, true
+  %and5472961 = and i1 %and5432960, %lnot545
+  %and.i3342 = and i32 %12, 2048
+  %cmp.i3343 = icmp ne i32 %and.i3342, 0
+  %lnot549 = xor i1 %cmp.i3343, true
+  %and5512962 = and i1 %and5472961, %lnot549
+  %and.i3344 = and i32 %12, 4096
+  %cmp.i3345 = icmp ne i32 %and.i3344, 0
+  %lnot553 = xor i1 %cmp.i3345, true
+  %and5552963 = and i1 %and5512962, %lnot553
+  %and.i3346 = and i32 %12, 8192
+  %cmp.i3347 = icmp ne i32 %and.i3346, 0
+  %lnot557 = xor i1 %cmp.i3347, true
+  %and5592964 = and i1 %and5552963, %lnot557
+  %and.i3348 = and i32 %12, 16384
+  %cmp.i3349 = icmp ne i32 %and.i3348, 0
+  %lnot561 = xor i1 %cmp.i3349, true
+  %and5632965 = and i1 %and5592964, %lnot561
+  %14 = trunc i32 %12 to i16
+  %cmp.i3350 = icmp slt i16 %14, 0
+  %lnot565 = xor i1 %cmp.i3350, true
+  %and5672966 = and i1 %and5632965, %lnot565
+  %and.i3351 = and i32 %12, 65536
+  %cmp.i3352 = icmp ne i32 %and.i3351, 0
+  %lnot569 = xor i1 %cmp.i3352, true
+  %and5712967 = and i1 %and5672966, %lnot569
+  %and.i3353 = and i32 %12, 131072
+  %cmp.i3354 = icmp ne i32 %and.i3353, 0
+  %lnot573 = xor i1 %cmp.i3354, true
+  %and5752968 = and i1 %and5712967, %lnot573
+  %and.i3355 = and i32 %12, 262144
+  %cmp.i3356 = icmp ne i32 %and.i3355, 0
+  %lnot577 = xor i1 %cmp.i3356, true
+  %and5792969 = and i1 %and5752968, %lnot577
+  %and.i3357 = and i32 %12, 524288
+  %cmp.i3358 = icmp ne i32 %and.i3357, 0
+  %lnot581 = xor i1 %cmp.i3358, true
+  %and5832970 = and i1 %and5792969, %lnot581
+  %and.i3359 = and i32 %12, 1048576
+  %cmp.i3360 = icmp ne i32 %and.i3359, 0
+  %lnot585 = xor i1 %cmp.i3360, true
+  %and5872971 = and i1 %and5832970, %lnot585
+  %and.i3361 = and i32 %12, 2097152
+  %cmp.i3362 = icmp ne i32 %and.i3361, 0
+  %lnot589 = xor i1 %cmp.i3362, true
+  %and5912972 = and i1 %and5872971, %lnot589
+  %and.i3363 = and i32 %12, 4194304
+  %cmp.i3364 = icmp ne i32 %and.i3363, 0
+  %lnot593 = xor i1 %cmp.i3364, true
+  %and5952973 = and i1 %and5912972, %lnot593
+  %and.i3365 = and i32 %12, 8388608
+  %cmp.i3366 = icmp ne i32 %and.i3365, 0
+  %lnot597 = xor i1 %cmp.i3366, true
+  %and5992974 = and i1 %and5952973, %lnot597
+  %and.i3367 = and i32 %12, 16777216
+  %cmp.i3368 = icmp ne i32 %and.i3367, 0
+  %lnot601 = xor i1 %cmp.i3368, true
+  %and6032975 = and i1 %and5992974, %lnot601
+  %and.i3369 = and i32 %12, 33554432
+  %cmp.i3370 = icmp ne i32 %and.i3369, 0
+  %lnot605 = xor i1 %cmp.i3370, true
+  %and6072976 = and i1 %and6032975, %lnot605
+  %and.i3371 = and i32 %12, 67108864
+  %cmp.i3372 = icmp ne i32 %and.i3371, 0
+  %lnot609 = xor i1 %cmp.i3372, true
+  %and6112977 = and i1 %and6072976, %lnot609
+  %and.i3373 = and i32 %12, 134217728
+  %cmp.i3374 = icmp ne i32 %and.i3373, 0
+  %lnot613 = xor i1 %cmp.i3374, true
+  %and6152978 = and i1 %and6112977, %lnot613
+  %and.i3375 = and i32 %12, 268435456
+  %cmp.i3376 = icmp ne i32 %and.i3375, 0
+  %lnot617 = xor i1 %cmp.i3376, true
+  %and6192979 = and i1 %and6152978, %lnot617
+  %and.i3377 = and i32 %12, 536870912
+  %cmp.i3378 = icmp ne i32 %and.i3377, 0
+  %lnot621 = xor i1 %cmp.i3378, true
+  %and6232980 = and i1 %and6192979, %lnot621
+  %and.i3379 = and i32 %12, 1073741824
+  %cmp.i3380 = icmp ne i32 %and.i3379, 0
+  %lnot625 = xor i1 %cmp.i3380, true
+  %and6272981 = and i1 %and6232980, %lnot625
+  %cmp.i3381 = icmp slt i32 %12, 0
+  %lnot629 = xor i1 %cmp.i3381, true
+  %and6312982 = and i1 %and6272981, %lnot629
+
+  %15 = load i32, i32* %bits5, align 4
+  %and.i3382 = and i32 %15, 1
+  %cmp.i3383 = icmp ne i32 %and.i3382, 0
+  %lnot633 = xor i1 %cmp.i3383, true
+  %and6352983 = and i1 %and6312982, %lnot633
+  %and.i3384 = and i32 %15, 2
+  %cmp.i3385 = icmp ne i32 %and.i3384, 0
+  %lnot637 = xor i1 %cmp.i3385, true
+  %and6392984 = and i1 %and6352983, %lnot637
+  %and.i3386 = and i32 %15, 4
+  %cmp.i3387 = icmp ne i32 %and.i3386, 0
+  %lnot641 = xor i1 %cmp.i3387, true
+  %and6432985 = and i1 %and6392984, %lnot641
+  %and.i3388 = and i32 %15, 8
+  %cmp.i3389 = icmp ne i32 %and.i3388, 0
+  %lnot645 = xor i1 %cmp.i3389, true
+  %and6472986 = and i1 %and6432985, %lnot645
+  %and.i3390 = and i32 %15, 16
+  %cmp.i3391 = icmp ne i32 %and.i3390, 0
+  %lnot649 = xor i1 %cmp.i3391, true
+  %and6512987 = and i1 %and6472986, %lnot649
+  %and.i3392 = and i32 %15, 32
+  %cmp.i3393 = icmp ne i32 %and.i3392, 0
+  %lnot653 = xor i1 %cmp.i3393, true
+  %and6552988 = and i1 %and6512987, %lnot653
+  %and.i3394 = and i32 %15, 64
+  %cmp.i3395 = icmp ne i32 %and.i3394, 0
+  %lnot657 = xor i1 %cmp.i3395, true
+  %and6592989 = and i1 %and6552988, %lnot657
+  %16 = trunc i32 %15 to i8
+  %cmp.i3396 = icmp slt i8 %16, 0
+  %lnot661 = xor i1 %cmp.i3396, true
+  %and6632990 = and i1 %and6592989, %lnot661
+  %and.i3397 = and i32 %15, 256
+  %cmp.i3398 = icmp ne i32 %and.i3397, 0
+  %lnot665 = xor i1 %cmp.i3398, true
+  %and6672991 = and i1 %and6632990, %lnot665
+  %and.i3399 = and i32 %15, 512
+  %cmp.i3400 = icmp ne i32 %and.i3399, 0
+  %lnot669 = xor i1 %cmp.i3400, true
+  %and6712992 = and i1 %and6672991, %lnot669
+  %and.i3401 = and i32 %15, 1024
+  %cmp.i3402 = icmp ne i32 %and.i3401, 0
+  %lnot673 = xor i1 %cmp.i3402, true
+  %and6752993 = and i1 %and6712992, %lnot673
+  %and.i3403 = and i32 %15, 2048
+  %cmp.i3404 = icmp ne i32 %and.i3403, 0
+  %lnot677 = xor i1 %cmp.i3404, true
+  %and6792994 = and i1 %and6752993, %lnot677
+  %and.i3405 = and i32 %15, 4096
+  %cmp.i3406 = icmp ne i32 %and.i3405, 0
+  %lnot681 = xor i1 %cmp.i3406, true
+  %and6832995 = and i1 %and6792994, %lnot681
+  %and.i3407 = and i32 %15, 8192
+  %cmp.i3408 = icmp ne i32 %and.i3407, 0
+  %lnot685 = xor i1 %cmp.i3408, true
+  %and6872996 = and i1 %and6832995, %lnot685
+  %and.i3409 = and i32 %15, 16384
+  %cmp.i3410 = icmp ne i32 %and.i3409, 0
+  %lnot689 = xor i1 %cmp.i3410, true
+  %and6912997 = and i1 %and6872996, %lnot689
+  %17 = trunc i32 %15 to i16
+  %cmp.i3411 = icmp slt i16 %17, 0
+  %lnot693 = xor i1 %cmp.i3411, true
+  %and6952998 = and i1 %and6912997, %lnot693
+  %and.i3412 = and i32 %15, 65536
+  %cmp.i3413 = icmp ne i32 %and.i3412, 0
+  %lnot697 = xor i1 %cmp.i3413, true
+  %and6992999 = and i1 %and6952998, %lnot697
+  %and.i3414 = and i32 %15, 131072
+  %cmp.i3415 = icmp ne i32 %and.i3414, 0
+  %lnot701 = xor i1 %cmp.i3415, true
+  %and7033000 = and i1 %and6992999, %lnot701
+  %and.i3416 = and i32 %15, 262144
+  %cmp.i3417 = icmp ne i32 %and.i3416, 0
+  %lnot705 = xor i1 %cmp.i3417, true
+  %and7073001 = and i1 %and7033000, %lnot705
+  %and.i3418 = and i32 %15, 524288
+  %cmp.i3419 = icmp ne i32 %and.i3418, 0
+  %lnot709 = xor i1 %cmp.i3419, true
+  %and7113002 = and i1 %and7073001, %lnot709
+  %and.i3420 = and i32 %15, 1048576
+  %cmp.i3421 = icmp ne i32 %and.i3420, 0
+  %lnot713 = xor i1 %cmp.i3421, true
+  %and7153003 = and i1 %and7113002, %lnot713
+  %and.i3422 = and i32 %15, 2097152
+  %cmp.i3423 = icmp ne i32 %and.i3422, 0
+  %lnot717 = xor i1 %cmp.i3423, true
+  %and7193004 = and i1 %and7153003, %lnot717
+  %and.i3424 = and i32 %15, 4194304
+  %cmp.i3425 = icmp ne i32 %and.i3424, 0
+  %lnot721 = xor i1 %cmp.i3425, true
+  %and7233005 = and i1 %and7193004, %lnot721
+  %and.i3426 = and i32 %15, 8388608
+  %cmp.i3427 = icmp ne i32 %and.i3426, 0
+  %lnot725 = xor i1 %cmp.i3427, true
+  %and7273006 = and i1 %and7233005, %lnot725
+  %and.i3428 = and i32 %15, 16777216
+  %cmp.i3429 = icmp ne i32 %and.i3428, 0
+  %lnot729 = xor i1 %cmp.i3429, true
+  %and7313007 = and i1 %and7273006, %lnot729
+  %and.i3430 = and i32 %15, 33554432
+  %cmp.i3431 = icmp ne i32 %and.i3430, 0
+  %lnot733 = xor i1 %cmp.i3431, true
+  %and7353008 = and i1 %and7313007, %lnot733
+  %and.i3432 = and i32 %15, 67108864
+  %cmp.i3433 = icmp ne i32 %and.i3432, 0
+  %lnot737 = xor i1 %cmp.i3433, true
+  %and7393009 = and i1 %and7353008, %lnot737
+  %and.i3434 = and i32 %15, 134217728
+  %cmp.i3435 = icmp ne i32 %and.i3434, 0
+  %lnot741 = xor i1 %cmp.i3435, true
+  %and7433010 = and i1 %and7393009, %lnot741
+  %and.i3436 = and i32 %15, 268435456
+  %cmp.i3437 = icmp ne i32 %and.i3436, 0
+  %lnot745 = xor i1 %cmp.i3437, true
+  %and7473011 = and i1 %and7433010, %lnot745
+  %and.i3438 = and i32 %15, 536870912
+  %cmp.i3439 = icmp ne i32 %and.i3438, 0
+  %lnot749 = xor i1 %cmp.i3439, true
+  %and7513012 = and i1 %and7473011, %lnot749
+  %and.i3440 = and i32 %15, 1073741824
+  %cmp.i3441 = icmp ne i32 %and.i3440, 0
+  %lnot753 = xor i1 %cmp.i3441, true
+  %and7553013 = and i1 %and7513012, %lnot753
+  %cmp.i3442 = icmp slt i32 %15, 0
+  %lnot757 = xor i1 %cmp.i3442, true
+  %and7593014 = and i1 %and7553013, %lnot757
+
+  %18 = load i32, i32* %bits6, align 4
+  %and.i3443 = and i32 %18, 1
+  %cmp.i3444 = icmp ne i32 %and.i3443, 0
+  %lnot761 = xor i1 %cmp.i3444, true
+  %and7633015 = and i1 %and7593014, %lnot761
+  %and.i3445 = and i32 %18, 2
+  %cmp.i3446 = icmp ne i32 %and.i3445, 0
+  %lnot765 = xor i1 %cmp.i3446, true
+  %and7673016 = and i1 %and7633015, %lnot765
+  %and.i3447 = and i32 %18, 4
+  %cmp.i3448 = icmp ne i32 %and.i3447, 0
+  %lnot769 = xor i1 %cmp.i3448, true
+  %and7713017 = and i1 %and7673016, %lnot769
+  %and.i3449 = and i32 %18, 8
+  %cmp.i3450 = icmp ne i32 %and.i3449, 0
+  %lnot773 = xor i1 %cmp.i3450, true
+  %and7753018 = and i1 %and7713017, %lnot773
+  %and.i3451 = and i32 %18, 16
+  %cmp.i3452 = icmp ne i32 %and.i3451, 0
+  %lnot777 = xor i1 %cmp.i3452, true
+  %and7793019 = and i1 %and7753018, %lnot777
+  %and.i3453 = and i32 %18, 32
+  %cmp.i3454 = icmp ne i32 %and.i3453, 0
+  %lnot781 = xor i1 %cmp.i3454, true
+  %and7833020 = and i1 %and7793019, %lnot781
+  %and.i3455 = and i32 %18, 64
+  %cmp.i3456 = icmp ne i32 %and.i3455, 0
+  %lnot785 = xor i1 %cmp.i3456, true
+  %and7873021 = and i1 %and7833020, %lnot785
+  %19 = trunc i32 %18 to i8
+  %cmp.i3457 = icmp slt i8 %19, 0
+  %lnot789 = xor i1 %cmp.i3457, true
+  %and7913022 = and i1 %and7873021, %lnot789
+  %and.i3458 = and i32 %18, 256
+  %cmp.i3459 = icmp ne i32 %and.i3458, 0
+  %lnot793 = xor i1 %cmp.i3459, true
+  %and7953023 = and i1 %and7913022, %lnot793
+  %and.i3460 = and i32 %18, 512
+  %cmp.i3461 = icmp ne i32 %and.i3460, 0
+  %lnot797 = xor i1 %cmp.i3461, true
+  %and7993024 = and i1 %and7953023, %lnot797
+  %and.i3462 = and i32 %18, 1024
+  %cmp.i3463 = icmp ne i32 %and.i3462, 0
+  %lnot801 = xor i1 %cmp.i3463, true
+  %and8033025 = and i1 %and7993024, %lnot801
+  %and.i3464 = and i32 %18, 2048
+  %cmp.i3465 = icmp ne i32 %and.i3464, 0
+  %lnot805 = xor i1 %cmp.i3465, true
+  %and8073026 = and i1 %and8033025, %lnot805
+  %and.i3466 = and i32 %18, 4096
+  %cmp.i3467 = icmp ne i32 %and.i3466, 0
+  %lnot809 = xor i1 %cmp.i3467, true
+  %and8113027 = and i1 %and8073026, %lnot809
+  %and.i3468 = and i32 %18, 8192
+  %cmp.i3469 = icmp ne i32 %and.i3468, 0
+  %lnot813 = xor i1 %cmp.i3469, true
+  %and8153028 = and i1 %and8113027, %lnot813
+  %and.i3470 = and i32 %18, 16384
+  %cmp.i3471 = icmp ne i32 %and.i3470, 0
+  %lnot817 = xor i1 %cmp.i3471, true
+  %and8193029 = and i1 %and8153028, %lnot817
+  %20 = trunc i32 %18 to i16
+  %cmp.i3472 = icmp slt i16 %20, 0
+  %lnot821 = xor i1 %cmp.i3472, true
+  %and8233030 = and i1 %and8193029, %lnot821
+  %and.i3473 = and i32 %18, 65536
+  %cmp.i3474 = icmp ne i32 %and.i3473, 0
+  %lnot825 = xor i1 %cmp.i3474, true
+  %and8273031 = and i1 %and8233030, %lnot825
+  %and.i3475 = and i32 %18, 131072
+  %cmp.i3476 = icmp ne i32 %and.i3475, 0
+  %lnot829 = xor i1 %cmp.i3476, true
+  %and8313032 = and i1 %and8273031, %lnot829
+  %and.i3477 = and i32 %18, 262144
+  %cmp.i3478 = icmp ne i32 %and.i3477, 0
+  %lnot833 = xor i1 %cmp.i3478, true
+  %and8353033 = and i1 %and8313032, %lnot833
+  %and.i3479 = and i32 %18, 524288
+  %cmp.i3480 = icmp ne i32 %and.i3479, 0
+  %lnot837 = xor i1 %cmp.i3480, true
+  %and8393034 = and i1 %and8353033, %lnot837
+  %and.i3481 = and i32 %18, 1048576
+  %cmp.i3482 = icmp ne i32 %and.i3481, 0
+  %lnot841 = xor i1 %cmp.i3482, true
+  %and8433035 = and i1 %and8393034, %lnot841
+  %and.i3483 = and i32 %18, 2097152
+  %cmp.i3484 = icmp ne i32 %and.i3483, 0
+  %lnot845 = xor i1 %cmp.i3484, true
+  %and8473036 = and i1 %and8433035, %lnot845
+  %and.i3485 = and i32 %18, 4194304
+  %cmp.i3486 = icmp ne i32 %and.i3485, 0
+  %lnot849 = xor i1 %cmp.i3486, true
+  %and8513037 = and i1 %and8473036, %lnot849
+  %and.i3487 = and i32 %18, 8388608
+  %cmp.i3488 = icmp ne i32 %and.i3487, 0
+  %lnot853 = xor i1 %cmp.i3488, true
+  %and8553038 = and i1 %and8513037, %lnot853
+  %and.i3489 = and i32 %18, 16777216
+  %cmp.i3490 = icmp ne i32 %and.i3489, 0
+  %lnot857 = xor i1 %cmp.i3490, true
+  %and8593039 = and i1 %and8553038, %lnot857
+  %and.i3491 = and i32 %18, 33554432
+  %cmp.i3492 = icmp ne i32 %and.i3491, 0
+  %lnot861 = xor i1 %cmp.i3492, true
+  %and8633040 = and i1 %and8593039, %lnot861
+  %and.i3493 = and i32 %18, 67108864
+  %cmp.i3494 = icmp ne i32 %and.i3493, 0
+  %lnot865 = xor i1 %cmp.i3494, true
+  %and8673041 = and i1 %and8633040, %lnot865
+  %and.i3495 = and i32 %18, 134217728
+  %cmp.i3496 = icmp ne i32 %and.i3495, 0
+  %lnot869 = xor i1 %cmp.i3496, true
+  %and8713042 = and i1 %and8673041, %lnot869
+  %and.i3497 = and i32 %18, 268435456
+  %cmp.i3498 = icmp ne i32 %and.i3497, 0
+  %lnot873 = xor i1 %cmp.i3498, true
+  %and8753043 = and i1 %and8713042, %lnot873
+  %and.i3499 = and i32 %18, 536870912
+  %cmp.i3500 = icmp ne i32 %and.i3499, 0
+  %lnot877 = xor i1 %cmp.i3500, true
+  %and8793044 = and i1 %and8753043, %lnot877
+  %and.i3501 = and i32 %18, 1073741824
+  %cmp.i3502 = icmp ne i32 %and.i3501, 0
+  %lnot881 = xor i1 %cmp.i3502, true
+  %and8833045 = and i1 %and8793044, %lnot881
+  %cmp.i3503 = icmp slt i32 %18, 0
+  %lnot885 = xor i1 %cmp.i3503, true
+  %and8873046 = and i1 %and8833045, %lnot885
+
+  %21 = load i32, i32* %bits7, align 4
+  %and.i3504 = and i32 %21, 1
+  %cmp.i3505 = icmp ne i32 %and.i3504, 0
+  %lnot889 = xor i1 %cmp.i3505, true
+  %and8913047 = and i1 %and8873046, %lnot889
+  %and.i3506 = and i32 %21, 2
+  %cmp.i3507 = icmp ne i32 %and.i3506, 0
+  %lnot893 = xor i1 %cmp.i3507, true
+  %and8953048 = and i1 %and8913047, %lnot893
+  %and.i3508 = and i32 %21, 4
+  %cmp.i3509 = icmp ne i32 %and.i3508, 0
+  %lnot897 = xor i1 %cmp.i3509, true
+  %and8993049 = and i1 %and8953048, %lnot897
+  %and.i3510 = and i32 %21, 8
+  %cmp.i3511 = icmp ne i32 %and.i3510, 0
+  %lnot901 = xor i1 %cmp.i3511, true
+  %and9033050 = and i1 %and8993049, %lnot901
+  %and.i3512 = and i32 %21, 16
+  %cmp.i3513 = icmp ne i32 %and.i3512, 0
+  %lnot905 = xor i1 %cmp.i3513, true
+  %and9073051 = and i1 %and9033050, %lnot905
+  %and.i3514 = and i32 %21, 32
+  %cmp.i3515 = icmp ne i32 %and.i3514, 0
+  %lnot909 = xor i1 %cmp.i3515, true
+  %and9113052 = and i1 %and9073051, %lnot909
+  %and.i3516 = and i32 %21, 64
+  %cmp.i3517 = icmp ne i32 %and.i3516, 0
+  %lnot913 = xor i1 %cmp.i3517, true
+  %and9153053 = and i1 %and9113052, %lnot913
+  %22 = trunc i32 %21 to i8
+  %cmp.i3518 = icmp slt i8 %22, 0
+  %lnot917 = xor i1 %cmp.i3518, true
+  %and9193054 = and i1 %and9153053, %lnot917
+  %and.i3519 = and i32 %21, 256
+  %cmp.i3520 = icmp ne i32 %and.i3519, 0
+  %lnot921 = xor i1 %cmp.i3520, true
+  %and9233055 = and i1 %and9193054, %lnot921
+  %and.i3521 = and i32 %21, 512
+  %cmp.i3522 = icmp ne i32 %and.i3521, 0
+  %lnot925 = xor i1 %cmp.i3522, true
+  %and9273056 = and i1 %and9233055, %lnot925
+  %and.i3523 = and i32 %21, 1024
+  %cmp.i3524 = icmp ne i32 %and.i3523, 0
+  %lnot929 = xor i1 %cmp.i3524, true
+  %and9313057 = and i1 %and9273056, %lnot929
+  %and.i3525 = and i32 %21, 2048
+  %cmp.i3526 = icmp ne i32 %and.i3525, 0
+  %lnot933 = xor i1 %cmp.i3526, true
+  %and9353058 = and i1 %and9313057, %lnot933
+  %and.i3527 = and i32 %21, 4096
+  %cmp.i3528 = icmp ne i32 %and.i3527, 0
+  %lnot937 = xor i1 %cmp.i3528, true
+  %and9393059 = and i1 %and9353058, %lnot937
+  %and.i3529 = and i32 %21, 8192
+  %cmp.i3530 = icmp ne i32 %and.i3529, 0
+  %lnot941 = xor i1 %cmp.i3530, true
+  %and9433060 = and i1 %and9393059, %lnot941
+  %and.i3531 = and i32 %21, 16384
+  %cmp.i3532 = icmp ne i32 %and.i3531, 0
+  %lnot945 = xor i1 %cmp.i3532, true
+  %and9473061 = and i1 %and9433060, %lnot945
+  %23 = trunc i32 %21 to i16
+  %cmp.i3533 = icmp slt i16 %23, 0
+  %lnot949 = xor i1 %cmp.i3533, true
+  %and9513062 = and i1 %and9473061, %lnot949
+  %and.i3534 = and i32 %21, 65536
+  %cmp.i3535 = icmp ne i32 %and.i3534, 0
+  %lnot953 = xor i1 %cmp.i3535, true
+  %and9553063 = and i1 %and9513062, %lnot953
+  %and.i3536 = and i32 %21, 131072
+  %cmp.i3537 = icmp ne i32 %and.i3536, 0
+  %lnot957 = xor i1 %cmp.i3537, true
+  %and9593064 = and i1 %and9553063, %lnot957
+  %and.i3538 = and i32 %21, 262144
+  %cmp.i3539 = icmp ne i32 %and.i3538, 0
+  %lnot961 = xor i1 %cmp.i3539, true
+  %and9633065 = and i1 %and9593064, %lnot961
+  %and.i3540 = and i32 %21, 524288
+  %cmp.i3541 = icmp ne i32 %and.i3540, 0
+  %lnot965 = xor i1 %cmp.i3541, true
+  %and9673066 = and i1 %and9633065, %lnot965
+  %and.i3542 = and i32 %21, 1048576
+  %cmp.i3543 = icmp ne i32 %and.i3542, 0
+  %lnot969 = xor i1 %cmp.i3543, true
+  %and9713067 = and i1 %and9673066, %lnot969
+  %and.i3544 = and i32 %21, 2097152
+  %cmp.i3545 = icmp ne i32 %and.i3544, 0
+  %lnot973 = xor i1 %cmp.i3545, true
+  %and9753068 = and i1 %and9713067, %lnot973
+  %and.i3546 = and i32 %21, 4194304
+  %cmp.i3547 = icmp ne i32 %and.i3546, 0
+  %lnot977 = xor i1 %cmp.i3547, true
+  %and9793069 = and i1 %and9753068, %lnot977
+  %and.i3548 = and i32 %21, 8388608
+  %cmp.i3549 = icmp ne i32 %and.i3548, 0
+  %lnot981 = xor i1 %cmp.i3549, true
+  %and9833070 = and i1 %and9793069, %lnot981
+  %and.i3550 = and i32 %21, 16777216
+  %cmp.i3551 = icmp ne i32 %and.i3550, 0
+  %lnot985 = xor i1 %cmp.i3551, true
+  %and9873071 = and i1 %and9833070, %lnot985
+  %and.i3552 = and i32 %21, 33554432
+  %cmp.i3553 = icmp ne i32 %and.i3552, 0
+  %lnot989 = xor i1 %cmp.i3553, true
+  %and9913072 = and i1 %and9873071, %lnot989
+  %and.i3554 = and i32 %21, 67108864
+  %cmp.i3555 = icmp ne i32 %and.i3554, 0
+  %lnot993 = xor i1 %cmp.i3555, true
+  %and9953073 = and i1 %and9913072, %lnot993
+  %and.i3556 = and i32 %21, 134217728
+  %cmp.i3557 = icmp ne i32 %and.i3556, 0
+  %lnot997 = xor i1 %cmp.i3557, true
+  %and9993074 = and i1 %and9953073, %lnot997
+  %and.i3558 = and i32 %21, 268435456
+  %cmp.i3559 = icmp ne i32 %and.i3558, 0
+  %lnot1001 = xor i1 %cmp.i3559, true
+  %and10033075 = and i1 %and9993074, %lnot1001
+  %and.i3560 = and i32 %21, 536870912
+  %cmp.i3561 = icmp ne i32 %and.i3560, 0
+  %lnot1005 = xor i1 %cmp.i3561, true
+  %and10073076 = and i1 %and10033075, %lnot1005
+  %and.i3562 = and i32 %21, 1073741824
+  %cmp.i3563 = icmp ne i32 %and.i3562, 0
+  %lnot1009 = xor i1 %cmp.i3563, true
+  %and10113077 = and i1 %and10073076, %lnot1009
+  %cmp.i3564 = icmp slt i32 %21, 0
+  %lnot1013 = xor i1 %cmp.i3564, true
+  %and10153078 = and i1 %and10113077, %lnot1013
+  ret i1 %and10153078
+}

test/Transforms/InstCombine/demand_shrink_nsw.ll

 ; RUN: opt -instcombine -o - -S %s | FileCheck %s
 
 ; The constant at %v35 should be shrunk, but this must lead to the nsw flag of
-; %v43 getting removed so that %v44 is not illegally optimized away.
+; %v43 getting removed so that the optimization wouldn't incorrectly introduce a
+; signed overflow in %v43 and remove %v44 due to the resulting undefined value
+; (note there is no signed overflow in %v43 because the high bits of %v43 would
+; be 1100...+0101...=0001...). %v44 uses -2147483647 (0x80000001) instead of
+; -2147483648 (0x80000000) as in the previous revision because %v44 with the
+; latter would be removed because after the constant shrinking, the high bits of
+; %v43 would be 0101...+0101...=1010... and %v44 would be redundant, while the
+; former would prevent that and preserve the the original intention of the test.
+;
 ; CHECK-LABEL: @foo
 ; CHECK: %v35 = add nuw nsw i32 %v34, 1362915575
 ; ...
 ; CHECK: add nuw i32 %v42, 1533579450
-; CHECK-NEXT: %v44 = or i32 %v43, -2147483648
+; CHECK-NEXT: %v44 = or i32 %v43, -2147483647
 ; CHECK-NEXT: %v45 = xor i32 %v44, 749011377
 ; CHECK-NEXT: ret i32 %v45
 define i32 @foo(i32 %arg) {
   %v33 = and i32 %arg, 223
   %v34 = xor i32 %v33, 29
   %v35 = add nuw i32 %v34, 3510399223
   %v37 = or i32 %v34, 1874836915
   %v38 = and i32 %v34, 221
   %v39 = xor i32 %v38, 1874836915
   %v40 = xor i32 %v37, %v39
   %v41 = shl nsw nuw i32 %v40, 1
   %v42 = sub i32 %v35, %v41
   %v43 = add nsw i32 %v42, 1533579450
-  %v44 = or i32 %v43, -2147483648
+  %v44 = or i32 %v43, -2147483647
   %v45 = xor i32 %v44, 749011377
   ret i32 %v45
 }

test/Transforms/InstCombine/invert-variable-mask-in-masked-merge-scalar.ll

;
   %n0 = xor i4 %x, 6 ; %x
   %n1 = and i4 %n0, %notmask
   %r = xor i4 %n1, 6
   ret i4 %r
 }
 
 define i4 @in_constant_mone_vary_invmask(i4 %y, i4 %mask) {
 ; CHECK-LABEL: @in_constant_mone_vary_invmask(
-; CHECK-NEXT:    [[N1_DEMORGAN:%.*]] = or i4 [[Y:%.*]], [[MASK:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = xor i4 [[N1_DEMORGAN]], -1
-; CHECK-NEXT:    [[R:%.*]] = xor i4 [[N1]], [[Y]]
+; CHECK-NEXT:    [[N1:%.*]] = xor i4 [[MASK:%.*]], -1
+; CHECK-NEXT:    [[R:%.*]] = or i4 [[N1]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %notmask = xor i4 %mask, -1
   %n0 = xor i4 -1, %y ; %x
   %n1 = and i4 %n0, %notmask
   %r = xor i4 %n1, %y
   ret i4 %r
 }

test/Transforms/InstCombine/invert-variable-mask-in-masked-merge-vector.ll

;
   %n0 = xor <3 x i4> %x, <i4 6, i4 undef, i4 7> ; %x
   %n1 = and <3 x i4> %n0, %notmask
   %r = xor <3 x i4> %n1, <i4 6, i4 undef, i4 7>
   ret <3 x i4> %r
 }
 
 define <2 x i4> @in_constant_mone_vary_invmask(<2 x i4> %y, <2 x i4> %mask) {
 ; CHECK-LABEL: @in_constant_mone_vary_invmask(
-; CHECK-NEXT:    [[N1_DEMORGAN:%.*]] = or <2 x i4> [[Y:%.*]], [[MASK:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = xor <2 x i4> [[N1_DEMORGAN]], <i4 -1, i4 -1>
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[N1]], [[Y]]
+; CHECK-NEXT:    [[N1:%.*]] = xor <2 x i4> [[MASK:%.*]], <i4 -1, i4 -1>
+; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[N1]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %notmask = xor <2 x i4> %mask, <i4 -1, i4 -1>
   %n0 = xor <2 x i4> <i4 -1, i4 -1>, %y ; %x
   %n1 = and <2 x i4> %n0, %notmask
   %r = xor <2 x i4> %n1, %y
   ret <2 x i4> %r
 }

test/Transforms/InstCombine/or.ll

;
   %C = and i32 %A, -65536
   %D = and i32 %B, 40186
   %E = or i32 %D, %C
   ret i32 %E
 }
 
 define <2 x i32> @test30vec(<2 x i32> %A) {
 ; CHECK-LABEL: @test30vec(
-; CHECK-NEXT:    [[C:%.*]] = and <2 x i32> [[A:%.*]], <i32 -65536, i32 -65536>
-; CHECK-NEXT:    [[B:%.*]] = and <2 x i32> [[A]], <i32 7224, i32 7224>
-; CHECK-NEXT:    [[D:%.*]] = or <2 x i32> [[B]], <i32 32962, i32 32962>
-; CHECK-NEXT:    [[E:%.*]] = or <2 x i32> [[D]], [[C]]
+; CHECK-NEXT:    [[D:%.*]] = and <2 x i32> [[A:%.*]], <i32 -58312, i32 -58312>
+; CHECK-NEXT:    [[E:%.*]] = or <2 x i32> [[D]], <i32 32962, i32 32962>
 ; CHECK-NEXT:    ret <2 x i32> [[E]]
 ;
   %B = or <2 x i32> %A, <i32 32962, i32 32962>
   %C = and <2 x i32> %A, <i32 -65536, i32 -65536>
   %D = and <2 x i32> %B, <i32 40186, i32 40186>
   %E = or <2 x i32> %D, %C
   ret <2 x i32> %E
 }

test/Transforms/InstCombine/unfold-masked-merge-with-const-mask-scalar.ll

;
   %n0 = xor i4 %x, 14 ; %x
   %n1 = and i4 %n0, 1
   %r = xor i4 %n1, 14
   ret i4 %r
 }
 
 define i4 @in_constant_mone_vary(i4 %y, i4 %mask) {
 ; CHECK-LABEL: @in_constant_mone_vary(
-; CHECK-NEXT:    [[N0:%.*]] = and i4 [[Y:%.*]], 1
-; CHECK-NEXT:    [[N1:%.*]] = xor i4 [[N0]], 1
-; CHECK-NEXT:    [[R:%.*]] = xor i4 [[N1]], [[Y]]
+; CHECK-NEXT:    [[R:%.*]] = or i4 [[Y:%.*]], 1
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %n0 = xor i4 %y, -1 ; %x
   %n1 = and i4 %n0, 1
   %r = xor i4 %n1, %y
   ret i4 %r
 }
 

test/Transforms/InstCombine/unfold-masked-merge-with-const-mask-vector.ll

;
   %n0 = xor <3 x i4> %x, <i4 14, i4 undef, i4 7> ; %x
   %n1 = and <3 x i4> %n0, <i4 1, i4 undef, i4 1>
   %r = xor <3 x i4> %n1, <i4 14, i4 undef, i4 7>
   ret <3 x i4> %r
 }
 
 define <2 x i4> @in_constant_mone_vary(<2 x i4> %y, <2 x i4> %mask) {
 ; CHECK-LABEL: @in_constant_mone_vary(
-; CHECK-NEXT:    [[N0:%.*]] = and <2 x i4> [[Y:%.*]], <i4 1, i4 1>
-; CHECK-NEXT:    [[N1:%.*]] = xor <2 x i4> [[N0]], <i4 1, i4 1>
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[N1]], [[Y]]
+; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[Y:%.*]], <i4 1, i4 1>
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %n0 = xor <2 x i4> %y, <i4 -1, i4 -1> ; %x
   %n1 = and <2 x i4> %n0, <i4 1, i4 1>
   %r = xor <2 x i4> %n1, %y
   ret <2 x i4> %r
 }
 

test/Transforms/LoopVectorize/AArch64/reduction-small-size.ll

 ; }
 ;
 ; CHECK: vector.body:
 ; CHECK:   phi <8 x i16>
 ; CHECK:   [[Ld1:%[a-zA-Z0-9.]+]] = load <8 x i8>
 ; CHECK:   zext <8 x i8> [[Ld1]] to <8 x i16>
 ; CHECK:   [[Ld2:%[a-zA-Z0-9.]+]] = load <8 x i8>
 ; CHECK:   zext <8 x i8> [[Ld2]] to <8 x i16>
-; CHECK:   add <8 x i16>
+; CHECK:   add nuw nsw <8 x i16>
 ; CHECK:   add <8 x i16>
 ;
 ; CHECK: middle.block:
 ; CHECK:   [[Rdx:%[a-zA-Z0-9.]+]] = call i16 @llvm.experimental.vector.reduce.add.i16.v8i16(<8 x i16>
 ; CHECK:   zext i16 [[Rdx]] to i32
 ;
 define i16 @reduction_i16_2(i8* nocapture readonly %a, i8* nocapture readonly %b, i32 %n) {
 entry: