Index: llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -1345,6 +1345,9 @@
   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);
@@ -1543,8 +1546,9 @@
       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);
   }
 
@@ -2161,6 +2165,9 @@
   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);
@@ -2250,8 +2257,9 @@
       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);
 
@@ -2427,14 +2435,15 @@
         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)
@@ -2514,6 +2523,9 @@
   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);
@@ -2736,20 +2748,22 @@
         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))))) {
@@ -2785,9 +2799,10 @@
       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));
 
Index: llvm/trunk/test/Transforms/InstCombine/or-xor.ll
===================================================================
--- llvm/trunk/test/Transforms/InstCombine/or-xor.ll
+++ llvm/trunk/test/Transforms/InstCombine/or-xor.ll
@@ -140,14 +140,9 @@
   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
@@ -183,15 +178,9 @@
   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
@@ -216,15 +205,9 @@
   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
Index: llvm/trunk/test/Transforms/InstCombine/or.ll
===================================================================
--- llvm/trunk/test/Transforms/InstCombine/or.ll
+++ llvm/trunk/test/Transforms/InstCombine/or.ll
@@ -570,14 +570,10 @@
   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
@@ -587,14 +583,10 @@
   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
@@ -618,14 +610,9 @@
   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
Index: llvm/trunk/test/Transforms/InstCombine/xor2.ll
===================================================================
--- llvm/trunk/test/Transforms/InstCombine/xor2.ll
+++ llvm/trunk/test/Transforms/InstCombine/xor2.ll
@@ -180,14 +180,10 @@
   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
@@ -198,7 +194,7 @@
 }
 
 ; 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) {
@@ -214,14 +210,10 @@
   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