[InstCombine] use commutative matchers for patterns with commutative operators

[spatel]

Summary

This is a bandage on a wound that needs stitches.

Background/motivation: I was circling back around to https://llvm.org/bugs/show_bug.cgi?id=28296 . I made a simple patch for that and noticed some regressions. I added test cases for those with rL281055, and this is hopefully the minimal fix for just those cases.

But as you can see from the surrounding untouched folds, we are missing commuted patterns all over the place, and of course there are no regression tests to cover any of those cases.

It seems like we could sprinkle "m_c_" dust all over this file and catch most of the missing folds, but then we still wouldn't have test coverage, and we'd still miss some fraction of commuted patterns because they require adjustments to the match order.

Another thought: are there any cases where we do *not* want to match the commuted variants of a pattern? If there are none of those, then could we just change the definitions for all commutative pattern matchers, so "m_c_" becomes automatic?

[spatel]

Ping.

[sanjoy]

Have you considered treating this as a canonicalization problem? That is, always canonicalize (X & A) | (A ^ Y) to (A & X) | (A ^ Y) (for all commutative ops)?

[spatel]

In D24419#550173, @sanjoy wrote:

Have you considered treating this as a canonicalization problem? That is, always canonicalize (X & A) | (A ^ Y) to (A & X) | (A ^ Y) (for all commutative ops)?

Hmmm...no, I didn't think of that. Can you describe the rule that we would use with this example?

This case is the 2nd to last code diff in this patch:
(A & ~B) ^ (~A & B) -> A ^ B
(~B & A) ^ (~A & B) -> A ^ B

I'm not sure how to canonicalize this without possibly conflicting with other canonicalization rules based on operand complexity. Ie, we order binop operands depending on whether they are themselves binop/unop/params/constants.

[spatel]

Ping.

[sanjoy]

In D24419#550211, @spatel wrote:

I'm not sure how to canonicalize this without possibly conflicting
with other canonicalization rules based on operand complexity. Ie, we
order binop operands depending on whether they are themselves
binop/unop/params/constants.

Yeah, I can't come up with a scheme that will obviously not clash with
InstCombine's operand complexity order.

An alternative may be to canonicalize "internally" -- that is first
split the expression into (Op0 ITy0 Op1) ITy1 (Op2 ITy2 Op3) (that
is, "explode" the contents of the operation into local variables) and
then std::swap the Op0 / Op1 or the Op2 / Op3 pairs in
whatever order that makes matching these easier. That may involve too
much refactoring though.

[spatel]

In D24419#558577, @sanjoy wrote:

In D24419#550211, @spatel wrote:

I'm not sure how to canonicalize this without possibly conflicting
with other canonicalization rules based on operand complexity. Ie, we
order binop operands depending on whether they are themselves
binop/unop/params/constants.

Yeah, I can't come up with a scheme that will obviously not clash with
InstCombine's operand complexity order.

An alternative may be to canonicalize "internally" -- that is first
split the expression into (Op0 ITy0 Op1) ITy1 (Op2 ITy2 Op3) (that
is, "explode" the contents of the operation into local variables) and
then std::swap the Op0 / Op1 or the Op2 / Op3 pairs in
whatever order that makes matching these easier. That may involve too
much refactoring though.

Ah, yes - "local" canonicalization. Some of that does already exist in these functions, but of course it's not done consistently. IMO, using "m_c_" is cleaner. Eg, in some places we're maintaining the swap state (see "SwappedForXor" - not sure if that's actually necessary), so it makes it harder to read the code.

I've looked over this file again, and I'm estimating ~50 potential places where we should account for commuted patterns. So it's not *that* bad. :)

If there are no objections to using "m_c_" in this way, I'd like to move forward on this patch. I can add "FIXME" comments ahead of visitAnd/visitOr/visitXor, and then we can add tests and clean up the rest of the matchers in follow-ups.

[efriedma]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2350 ↗

(On Diff #70876)

This isn't actually equivalent to four separate checks in the case where both operands of the xor are "not" operations. I guess that doesn't really matter much in practice for this particular case, but we need a better approach in general.

[spatel]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2350 ↗

(On Diff #70876)

Is it possible to have both operands 'notted'? We should always be able to fold:

%negx = xor i32 %x, -1
%negy = xor i32 %y, -1
%xor = xor i32 %negx, %negy

to:

xor i32 %x, %y

before we reach here?

[efriedma]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2350 ↗

(On Diff #70876)

Yes, in this particular case, it probably doesn't matter. I don't want to have to reason that out for every possible use of commuted patterns, though.

[spatel]

Ping.

D27531 reminded me of this patch. Another possibility (this is in InstSimplify) looks like this:

if (auto *ICILHS = dyn_cast<ICmpInst>(Op0)) {
  if (auto *ICIRHS = dyn_cast<ICmpInst>(Op1)) {
    if (Value *V = SimplifyAndOfICmps(ICILHS, ICIRHS))
      return V;
    if (Value *V = SimplifyAndOfICmps(ICIRHS, ICILHS))
      return V;
  }
}

So put a pile of folds in a helper function and then call it with all permutations of the commutative parameters. Better than using m_c_*?

[spatel]

Ping * 2.

[majnemer]

LGTM

[spatel]

Thanks, David. I'll add some FIXME notes as I mentioned on Oct 12 and check this in. Then we can move forward on PR28296.

A better overall solution for commuted matching may emerge after some refactoring.

llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(Op0, m_Not(m_SExt(m_Value(X)))) &&
       X->getType()->getScalarType()->isIntegerTy(1)) {
     Value *Zero = Constant::getNullValue(Op0->getType());
     return SelectInst::Create(X, Zero, Op1);
   }
 
   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::visitAnd(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyAndInst(Op0, Op1, DL, &TLI, &DT))
if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
           return BinaryOperator::CreateAnd(Op1, Builder->CreateNot(C));
 
     // (A | B) & ((~A) ^ B) -> (A & B)
     if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
         match(Op1, m_Xor(m_Not(m_Specific(A)), m_Specific(B))))
       return BinaryOperator::CreateAnd(A, B);
 
     // ((~A) ^ B) & (A | B) -> (A & B)
+    // ((~A) ^ B) & (B | A) -> (A & B)
     if (match(Op0, m_Xor(m_Not(m_Value(A)), m_Value(B))) &&
-        match(Op1, m_Or(m_Specific(A), m_Specific(B))))
+        match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
       return BinaryOperator::CreateAnd(A, B);
   }
 
   {
     ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
     ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
     if (LHS && RHS)
       if (Value *Res = FoldAndOfICmps(LHS, RHS))
Instruction *InstCombiner::FoldXorWithConstants(BinaryOperator &I, Value *Op,
   if (V1 == A || V1 == B) {
     Value *NewOp = Builder->CreateAnd(V1 == A ? B : A, CI1);
     return BinaryOperator::CreateXor(NewOp, V1);
   }
 
   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);
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyOrInst(Op0, Op1, DL, &TLI, &DT))
if (match(Op0, m_And(m_Not(m_Value(A)), m_Value(B))) &&
       match(Op1, m_Specific(A)))
     return BinaryOperator::CreateOr(A, B);
 
   // ((A & B) | ~A) -> (~A | B)
   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
       match(Op1, m_Not(m_Specific(A))))
     return BinaryOperator::CreateOr(Builder->CreateNot(A), B);
 
-  // (A & (~B)) | (A ^ B) -> (A ^ B)
-  if (match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) &&
+  // (A & ~B) | (A ^ B) -> (A ^ B)
+  // (~B & A) | (A ^ B) -> (A ^ B)
+  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
       match(Op1, m_Xor(m_Specific(A), m_Specific(B))))
     return BinaryOperator::CreateXor(A, B);
 
   // (A ^ B) | ( A & (~B)) -> (A ^ B)
   if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
       match(Op1, m_And(m_Specific(A), m_Not(m_Specific(B)))))
     return BinaryOperator::CreateXor(A, B);
 
if (BinaryOperator *B = dyn_cast<BinaryOperator>(A))
           Op1->hasOneUse() && (B->getOpcode() == Instruction::Or ||
                                B->getOpcode() == Instruction::Xor)) {
         Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) :
                                                  B->getOperand(0);
         Value *Not = Builder->CreateNot(NotOp, NotOp->getName()+".not");
         return BinaryOperator::CreateOr(Not, Op0);
       }
 
-  // (A & B) | ((~A) ^ B) -> (~A ^ B)
-  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
-      match(Op1, m_Xor(m_Not(m_Specific(A)), m_Specific(B))))
-    return BinaryOperator::CreateXor(Builder->CreateNot(A), B);
-
-  // ((~A) ^ B) | (A & B) -> (~A ^ B)
-  if (match(Op0, m_Xor(m_Not(m_Value(A)), m_Value(B))) &&
-      match(Op1, m_And(m_Specific(A), m_Specific(B))))
+  // (A & B) | (~A ^ B) -> (~A ^ B)
+  // (A & B) | (B ^ ~A) -> (~A ^ B)
+  // (B & A) | (~A ^ B) -> (~A ^ B)
+  // (B & A) | (B ^ ~A) -> (~A ^ B)
+  // The match order is important: match the xor first because the 'not'
+  // operation defines 'A'. We do not need to match the xor as Op0 because the
+  // xor was canonicalized to Op1 above.
+  if (match(Op1, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
+      match(Op0, m_c_And(m_Specific(A), m_Specific(B))))
     return BinaryOperator::CreateXor(Builder->CreateNot(A), B);
 
   if (SwappedForXor)
     std::swap(Op0, Op1);
 
   {
     ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
     ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
if (Op0->hasOneUse() && Op1->hasOneUse() &&
       Value *orFalse = Builder->CreateOr(B, D);
       return SelectInst::Create(X, orTrue, orFalse);
     }
   }
 
   return Changed ? &I : 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);
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyXorInst(Op0, Op1, DL, &TLI, &DT))
if (Op0I && Op1I) {
     }
     // (A | B)^(A & B) -> A ^ B
     if (match(Op0I, m_Or(m_Value(A), m_Value(B))) &&
         match(Op1I, m_And(m_Value(C), m_Value(D)))) {
       if ((A == C && B == D) || (A == D && B == C))
         return BinaryOperator::CreateXor(A, B);
     }
     // (A | ~B) ^ (~A | B) -> A ^ B
-    if (match(Op0I, m_Or(m_Value(A), m_Not(m_Value(B)))) &&
-        match(Op1I, m_Or(m_Not(m_Specific(A)), m_Specific(B)))) {
+    // (~B | A) ^ (~A | B) -> A ^ B
+    if (match(Op0I, m_c_Or(m_Value(A), m_Not(m_Value(B)))) &&
+        match(Op1I, m_Or(m_Not(m_Specific(A)), m_Specific(B))))
       return BinaryOperator::CreateXor(A, B);
-    }
+
     // (~A | B) ^ (A | ~B) -> A ^ B
     if (match(Op0I, m_Or(m_Not(m_Value(A)), m_Value(B))) &&
         match(Op1I, m_Or(m_Specific(A), m_Not(m_Specific(B))))) {
       return BinaryOperator::CreateXor(A, B);
     }
     // (A & ~B) ^ (~A & B) -> A ^ B
-    if (match(Op0I, m_And(m_Value(A), m_Not(m_Value(B)))) &&
-        match(Op1I, m_And(m_Not(m_Specific(A)), m_Specific(B)))) {
+    // (~B & A) ^ (~A & B) -> A ^ B
+    if (match(Op0I, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
+        match(Op1I, m_And(m_Not(m_Specific(A)), m_Specific(B))))
       return BinaryOperator::CreateXor(A, B);
-    }
+
     // (~A & B) ^ (A & ~B) -> A ^ B
     if (match(Op0I, m_And(m_Not(m_Value(A)), m_Value(B))) &&
         match(Op1I, m_And(m_Specific(A), m_Not(m_Specific(B))))) {
       return BinaryOperator::CreateXor(A, B);
     }
     // (A ^ C)^(A | B) -> ((~A) & B) ^ C
     if (match(Op0I, m_Xor(m_Value(D), m_Value(C))) &&
         match(Op1I, m_Or(m_Value(A), m_Value(B)))) {
if (match(Op0I, m_And(m_Value(A), m_Value(B))) &&
         match(Op1I, m_Xor(m_Specific(A), m_Specific(B))))
       return BinaryOperator::CreateOr(A, B);
     // (A ^ B) ^ (A & B) -> (A | B)
     if (match(Op0I, m_Xor(m_Value(A), m_Value(B))) &&
         match(Op1I, m_And(m_Specific(A), m_Specific(B))))
       return BinaryOperator::CreateOr(A, B);
   }
 
-  Value *A = nullptr, *B = nullptr;
-  // (A & ~B) ^ (~A) -> ~(A & B)
-  if (match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) &&
+  // (A & ~B) ^ ~A -> ~(A & B)
+  // (~B & A) ^ ~A -> ~(A & B)
+  Value *A, *B;
+  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
       match(Op1, m_Not(m_Specific(A))))
     return BinaryOperator::CreateNot(Builder->CreateAnd(A, B));
 
   if (ICmpInst *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
     if (ICmpInst *LHS = dyn_cast<ICmpInst>(I.getOperand(0))) {
 
       // E.g. if we have xor (icmp eq %A, 0), (icmp eq %B, 0)
       // and we know both A and B are either 8 (power of 2) or 0

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

 ;
   %neg = xor i32 %x, -1
   %xor = xor i32 %neg, %y
   %or = or i32 %x, %y
   %and = and i32 %xor, %or
   ret i32 %and
 }
 
-; FIXME: We miss the fold because the pattern matching is inadequate.
-
 define i32 @test12_commuted(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test12_commuted(
-; CHECK-NEXT:    [[NEG:%.*]] = xor i32 %x, -1
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[NEG]], %y
-; CHECK-NEXT:    [[OR:%.*]] = or i32 %y, %x
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[XOR]], [[OR]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, %y
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %neg = xor i32 %x, -1
   %xor = xor i32 %neg, %y
   %or = or i32 %y, %x
   %and = and i32 %xor, %or
   ret i32 %and
 }
;
   %noty = xor i32 %y, -1
   %notx = xor i32 %x, -1
   %or1 = or i32 %x, %noty
   %or2 = or i32 %notx, %y
   %xor = xor i32 %or1, %or2
   ret i32 %xor
 }
 
-; FIXME: We miss the fold because the pattern matching is inadequate.
-
 define i32 @test14_commuted(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test14_commuted(
-; CHECK-NEXT:    [[NOTY:%.*]] = xor i32 %y, -1
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i32 %x, -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTY]], %x
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOTX]], %y
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[OR1]], [[OR2]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 %x, %y
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %noty = xor i32 %y, -1
   %notx = xor i32 %x, -1
   %or1 = or i32 %noty, %x
   %or2 = or i32 %notx, %y
   %xor = xor i32 %or1, %or2
   ret i32 %xor
 }
 
 ; ((x & ~y) ^ (~x & y)) -> x ^ y
 define i32 @test15(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test15(
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 %x, %y
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %noty = xor i32 %y, -1
   %notx = xor i32 %x, -1
   %and1 = and i32 %x, %noty
   %and2 = and i32 %notx, %y
   %xor = xor i32 %and1, %and2
   ret i32 %xor
 }
 
-; FIXME: We miss the fold because the pattern matching is inadequate.
-
 define i32 @test15_commuted(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test15_commuted(
-; CHECK-NEXT:    [[NOTY:%.*]] = xor i32 %y, -1
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i32 %x, -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTY]], %x
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOTX]], %y
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[AND1]], [[AND2]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 %x, %y
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %noty = xor i32 %y, -1
   %notx = xor i32 %x, -1
   %and1 = and i32 %noty, %x
   %and2 = and i32 %notx, %y
   %xor = xor i32 %and1, %and2
   ret i32 %xor

llvm/trunk/test/Transforms/InstCombine/or.ll

 ;
   %nega = xor i32 %a, -1
   %xor = xor i32 %nega, %b
   %and = and i32 %a, %b
   %or = or i32 %xor, %and
   ret i32 %or
 }
 
-; FIXME: We miss the fold because the pattern matching is inadequate.
-
 define i32 @test42_commuted_and(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test42_commuted_and(
-; CHECK-NEXT:    [[NEGA:%.*]] = xor i32 %a, -1
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[NEGA]], %b
-; CHECK-NEXT:    [[AND:%.*]] = and i32 %b, %a
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[XOR]], [[AND]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 %a, -1
+; CHECK-NEXT:    [[OR:%.*]] = xor i32 [[TMP1]], %b
 ; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %nega = xor i32 %a, -1
   %xor = xor i32 %nega, %b
   %and = and i32 %b, %a
   %or = or i32 %xor, %and
   ret i32 %or
 }
 
-; FIXME: We miss the fold because the pattern matching is inadequate.
-
 define i32 @test42_commuted_xor(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test42_commuted_xor(
-; CHECK-NEXT:    [[NEGA:%.*]] = xor i32 %a, -1
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 %b, [[NEGA]]
-; CHECK-NEXT:    [[AND:%.*]] = and i32 %a, %b
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[XOR]], [[AND]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 %a, -1
+; CHECK-NEXT:    [[OR:%.*]] = xor i32 [[TMP1]], %b
 ; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %nega = xor i32 %a, -1
   %xor = xor i32 %b, %nega
   %and = and i32 %a, %b
   %or = or i32 %xor, %and
   ret i32 %or
 }
 
 ; Commute operands of the 'or'.
 
 define i32 @test43(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test43(
 ; CHECK-NEXT:    [[OR:%.*]] = xor i32 %a, %b
 ; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %neg = xor i32 %b, -1
   %and = and i32 %a, %neg
   %xor = xor i32 %a, %b
   %or = or i32 %and, %xor
   ret i32 %or
 }
 
-; FIXME: We miss the fold because the pattern matching is inadequate.
-
 define i32 @test43_commuted_and(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test43_commuted_and(
-; CHECK-NEXT:    [[NEG:%.*]] = xor i32 %b, -1
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[NEG]], %a
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 %a, %b
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[AND]], [[XOR]]
+; CHECK-NEXT:    [[OR:%.*]] = xor i32 %a, %b
 ; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %neg = xor i32 %b, -1
   %and = and i32 %neg, %a
   %xor = xor i32 %a, %b
   %or = or i32 %and, %xor
   ret i32 %or
 }

llvm/trunk/test/Transforms/InstCombine/xor2.ll

 ;
   %negb = xor i32 %b, -1
   %and = and i32 %a, %negb
   %nega = xor i32 %a, -1
   %xor = xor i32 %and, %nega
   ret i32 %xor
 }
 
-; FIXME: We miss the fold because the pattern matching is inadequate.
-
 define i32 @test12commuted(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test12commuted(
-; CHECK-NEXT:    [[NEGB:%.*]] = xor i32 %b, -1
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[NEGB]], %a
-; CHECK-NEXT:    [[NEGA:%.*]] = xor i32 %a, -1
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[AND]], [[NEGA]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %a, %b
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %negb = xor i32 %b, -1
   %and = and i32 %negb, %a
   %nega = xor i32 %a, -1
   %xor = xor i32 %and, %nega
   ret i32 %xor
 }
 
 ; This is a test of canonicalization via operand complexity.
-; The final xor has a binary operator and a (fake) unary operator, 
+; The final xor has a binary operator and a (fake) unary operator,
 ; so binary (more complex) should come first.
 
 define i32 @test13(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test13(
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %a, %b
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %nega = xor i32 %a, -1
   %negb = xor i32 %b, -1
   %and = and i32 %a, %negb
   %xor = xor i32 %nega, %and
   ret i32 %xor
 }
 
-; FIXME: We miss the fold because the pattern matching is inadequate.
-
 define i32 @test13commuted(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test13commuted(
-; CHECK-NEXT:    [[NEGA:%.*]] = xor i32 %a, -1
-; CHECK-NEXT:    [[NEGB:%.*]] = xor i32 %b, -1
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[NEGB]], %a
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[AND]], [[NEGA]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %a, %b
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %nega = xor i32 %a, -1
   %negb = xor i32 %b, -1
   %and = and i32 %negb, %a
   %xor = xor i32 %nega, %and
   ret i32 %xor
 }