[PatternMatch] Stabilize the matching order of commutative matchers

[lebedev.ri]

Summary

Currently, we

1. match LHS matcher to the first operand of binary operator,
2. and then match RHS matcher to the second operand of binary operator.

If that does not match, we swap the LHS and RHS matchers:

1. match RHS matcher to the first operand of binary operator,
2. and then match LHS matcher to the second operand of binary operator.

This works ok.
But it complicates writing of commutative matchers, where one would like to match
(m_Value()) the value on one side, and use (m_Specific()) it on the other side.

This is additionally complicated by the fact that m_Specific() stores the Value *,
not Value **, so it won't work at all out of the box.

The last problem is trivially solved by adding a new m_c_Specific() that stores the
Value **, not Value *. I'm choosing to add a new matcher, not change the existing
one because i guess all the current users are ok with existing behavior,
and this additional pointer indirection may have performance drawbacks.
Also, i'm storing pointer, not reference, because for some mysterious-to-me reason
it did not work with the reference.

The first one appears trivial, too.
Currently, we

1. match LHS matcher to the first operand of binary operator,
2. and then match RHS matcher to the second operand of binary operator.

If that does not match, we swap the LHS and RHS matchers operands:

1. match RHS LHS matcher to the first second operand of binary operator,
2. and then match LHS RHS matcher to the ~~second~ first operand of binary operator.

Surprisingly, $ ninja check-llvm still passes with this.
But i expect the bots will disagree..

The motivational unittest is included.
I'd like to use this in D45664.

[craig.topper]

include/llvm/IR/PatternMatch.h

495 ↗

(On Diff #143120)

This doesn't only fix commutative so I don't think the name should be tied to that.

This was also not possible before, but would be with this new matcher.

match(m_And(m_Value(X), m_Or(m_Specific(X), m_Value(Y))

[lebedev.ri]

include/llvm/IR/PatternMatch.h

495 ↗

(On Diff #143120)

Yes, i agree.
Any suggestions for a better name?

[lebedev.ri]

include/llvm/IR/PatternMatch.h

495 ↗

(On Diff #143120)

Would m_Deferred() sound better?

I think it would convey the idea that the actual value
is only acquired [to be checked] at the time of the match() itself.

[lebedev.ri]

Ping. Would really like some feedback on this idea.

[xbolva00]

include/llvm/IR/PatternMatch.h

495 ↗

(On Diff #143120)

Yes, I vote for other name than "m_c_Specific" too.

[spatel]

In D45828#1079125, @lebedev.ri wrote:

Ping. Would really like some feedback on this idea.

My implementation knowledge is limited, so I defer to other reviewers for the actual diffs.

Are the eval-order-stabilization changes independent of the new matcher?
How often does this come up? Ie, besides the proposed patch in D45664, can you use this on existing code to simplify it? If so, it might be worth including at least one of those changes here to show the value of adding a new matcher.

[lebedev.ri]

• Renamed it to m_Deferred().
• Simplified some existing code using it.

In D45828#1079612, @spatel wrote:

In D45828#1079125, @lebedev.ri wrote:

Ping. Would really like some feedback on this idea.

My implementation knowledge is limited, so I defer to other reviewers for the actual diffs.

Are the eval-order-stabilization changes independent of the new matcher?

I suppose so.
The matcher can be separate, though then i'm not sure right now how to test the rest of the changes.

How often does this come up?

Not *too* often, but it does come up.

Ie, besides the proposed patch in D45664, can you use this on existing code to simplify it? If so, it might be worth including at least one of those changes here to show the value of adding a new matcher.

It's a bit cumbersome to find such instances, but sure, there you go.

[craig.topper]

I'd like to know more about why storing a reference didn't work.

unittests/IR/PatternMatch.cpp

68 ↗

(On Diff #144207)

Rename based on the new name m_Deferred?

[lebedev.ri]

In D45828#1081483, @craig.topper wrote:

I'd like to know more about why storing a reference didn't work.

Uhm, that makes two of us :/
I'm very sure it did not work back then when i initially tried,
but now it just worked, and all the tests pass...

(i did check that there are tests for these commutative variants, even had to add some beforehand.)

[craig.topper]

LGTM

[lebedev.ri]

Make it Value *const &V, not Value *&V, for symmetry with m_Specific(), which takes const Value *V, not Value *V.

[lebedev.ri]

@craig.topper, @spatel thank you for the review!

I'm going to commit this, and watch the bots for a bit.
If something breaks i'd guess it would be msan bots.

llvm/trunk/include/llvm/IR/PatternMatch.h

struct specificval_ty {
   specificval_ty(const Value *V) : Val(V) {}
 
   template <typename ITy> bool match(ITy *V) { return V == Val; }
 };
 
 /// Match if we have a specific specified value.
 inline specificval_ty m_Specific(const Value *V) { return V; }
 
+/// Stores a reference to the Value *, not the Value * itself,
+/// thus can be used in commutative matchers.
+template <typename Class> struct deferredval_ty {
+  Class *const &Val;
+
+  deferredval_ty(Class *const &V) : Val(V) {}
+
+  template <typename ITy> bool match(ITy *const V) { return V == Val; }
+};
+
+/// A commutative-friendly version of m_Specific().
+inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; }
+inline deferredval_ty<const Value> m_Deferred(const Value *const &V) {
+  return V;
+}
+
 /// Match a specified floating point value or vector of all elements of
 /// that value.
 struct specific_fpval {
   double Val;
 
   specific_fpval(double V) : Val(V) {}
 
   template <typename ITy> bool match(ITy *V) {

 //===----------------------------------------------------------------------===//
 // Matcher for any binary operator.
 //
 template <typename LHS_t, typename RHS_t, bool Commutable = false>
 struct AnyBinaryOp_match {
   LHS_t L;
   RHS_t R;
 
+  // The evaluation order is always stable, regardless of Commutability.
+  // The LHS is always matched first.
   AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     if (auto *I = dyn_cast<BinaryOperator>(V))
       return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
-             (Commutable && R.match(I->getOperand(0)) &&
-              L.match(I->getOperand(1)));
+             (Commutable && L.match(I->getOperand(1)) &&
+              R.match(I->getOperand(0)));
     return false;
   }
 };
 
 template <typename LHS, typename RHS>
 inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
   return AnyBinaryOp_match<LHS, RHS>(L, R);
 }
 
 //===----------------------------------------------------------------------===//
 // Matchers for specific binary operators.
 //
 
 template <typename LHS_t, typename RHS_t, unsigned Opcode,
           bool Commutable = false>
 struct BinaryOp_match {
   LHS_t L;
   RHS_t R;
 
+  // The evaluation order is always stable, regardless of Commutability.
+  // The LHS is always matched first.
   BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     if (V->getValueID() == Value::InstructionVal + Opcode) {
       auto *I = cast<BinaryOperator>(V);
       return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
-             (Commutable && R.match(I->getOperand(0)) &&
-              L.match(I->getOperand(1)));
+             (Commutable && L.match(I->getOperand(1)) &&
+              R.match(I->getOperand(0)));
     }
     if (auto *CE = dyn_cast<ConstantExpr>(V))
       return CE->getOpcode() == Opcode &&
              ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) ||
-              (Commutable && R.match(CE->getOperand(0)) &&
-               L.match(CE->getOperand(1))));
+              (Commutable && L.match(CE->getOperand(1)) &&
+               R.match(CE->getOperand(0))));
     return false;
   }
 };
 
 template <typename LHS, typename RHS>
 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
                                                         const RHS &R) {
   return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);

 
 template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy,
           bool Commutable = false>
 struct CmpClass_match {
   PredicateTy &Predicate;
   LHS_t L;
   RHS_t R;
 
+  // The evaluation order is always stable, regardless of Commutability.
+  // The LHS is always matched first.
   CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
       : Predicate(Pred), L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     if (auto *I = dyn_cast<Class>(V))
       if ((L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
-          (Commutable && R.match(I->getOperand(0)) &&
-           L.match(I->getOperand(1)))) {
+          (Commutable && L.match(I->getOperand(1)) &&
+           R.match(I->getOperand(0)))) {
         Predicate = I->getPredicate();
         return true;
       }
     return false;
   }
 };
 
 template <typename LHS, typename RHS>

 //
 
 template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
           bool Commutable = false>
 struct MaxMin_match {
   LHS_t L;
   RHS_t R;
 
+  // The evaluation order is always stable, regardless of Commutability.
+  // The LHS is always matched first.
   MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
     auto *SI = dyn_cast<SelectInst>(V);
     if (!SI)
       return false;
     auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
if ((TrueVal != LHS || FalseVal != RHS) &&
       return false;
     typename CmpInst_t::Predicate Pred =
         LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
     // Does "(x pred y) ? x : y" represent the desired max/min operation?
     if (!Pred_t::match(Pred))
       return false;
     // It does!  Bind the operands.
     return (L.match(LHS) && R.match(RHS)) ||
-           (Commutable && R.match(LHS) && L.match(RHS));
+           (Commutable && L.match(RHS) && R.match(LHS));
   }
 };
 
 /// Helper class for identifying signed max predicates.
 struct smax_pred_ty {
   static bool match(ICmpInst::Predicate Pred) {
     return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
   }

llvm/trunk/lib/Analysis/ValueTracking.cpp

case Instruction::And: {
     // Output known-0 are known to be clear if zero in either the LHS | RHS.
     Known.Zero |= Known2.Zero;
 
     // and(x, add (x, -1)) is a common idiom that always clears the low bit;
     // here we handle the more general case of adding any odd number by
     // matching the form add(x, add(x, y)) where y is odd.
     // TODO: This could be generalized to clearing any bit set in y where the
     // following bit is known to be unset in y.
-    Value *Y = nullptr;
+    Value *X = nullptr, *Y = nullptr;
     if (!Known.Zero[0] && !Known.One[0] &&
-        (match(I->getOperand(0), m_Add(m_Specific(I->getOperand(1)),
-                                       m_Value(Y))) ||
-         match(I->getOperand(1), m_Add(m_Specific(I->getOperand(0)),
-                                       m_Value(Y))))) {
+        match(I, m_c_BinOp(m_Value(X), m_Add(m_Deferred(X), m_Value(Y))))) {
       Known2.resetAll();
       computeKnownBits(Y, Known2, Depth + 1, Q);
       if (Known2.countMinTrailingOnes() > 0)
         Known.Zero.setBit(0);
     }
     break;
   }
   case Instruction::Or:

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

if (auto *RHSConv = dyn_cast<ZExtInst>(RHS)) {
         Value *NewAdd = Builder.CreateNUWAdd(
             LHSConv->getOperand(0), RHSConv->getOperand(0), "addconv");
         return new ZExtInst(NewAdd, Ty);
       }
     }
   }
 
   // (add (xor A, B) (and A, B)) --> (or A, B)
-  if (match(LHS, m_Xor(m_Value(A), m_Value(B))) &&
-      match(RHS, m_c_And(m_Specific(A), m_Specific(B))))
-    return BinaryOperator::CreateOr(A, B);
-
   // (add (and A, B) (xor A, B)) --> (or A, B)
-  if (match(RHS, m_Xor(m_Value(A), m_Value(B))) &&
-      match(LHS, m_c_And(m_Specific(A), m_Specific(B))))
+  if (match(&I, m_c_BinOp(m_Xor(m_Value(A), m_Value(B)),
+                          m_c_And(m_Deferred(A), m_Deferred(B)))))
     return BinaryOperator::CreateOr(A, B);
 
   // (add (or A, B) (and A, B)) --> (add A, B)
-  if (match(LHS, m_Or(m_Value(A), m_Value(B))) &&
-      match(RHS, m_c_And(m_Specific(A), m_Specific(B)))) {
-    I.setOperand(0, A);
-    I.setOperand(1, B);
-    return &I;
-  }
-
   // (add (and A, B) (or A, B)) --> (add A, B)
-  if (match(RHS, m_Or(m_Value(A), m_Value(B))) &&
-      match(LHS, m_c_And(m_Specific(A), m_Specific(B)))) {
+  if (match(&I, m_c_BinOp(m_Or(m_Value(A), m_Value(B)),
+                          m_c_And(m_Deferred(A), m_Deferred(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.

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

static Instruction *foldAndToXor(BinaryOperator &I,
   assert(I.getOpcode() == Instruction::And);
   Value *Op0 = I.getOperand(0);
   Value *Op1 = I.getOperand(1);
   Value *A, *B;
 
   // Operand complexity canonicalization guarantees that the 'or' is Op0.
   // (A | B) & ~(A & B) --> A ^ B
   // (A | B) & ~(B & A) --> A ^ B
-  if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
-      match(Op1, m_Not(m_c_And(m_Specific(A), m_Specific(B)))))
+  if (match(&I, m_BinOp(m_Or(m_Value(A), m_Value(B)),
+                        m_Not(m_c_And(m_Deferred(A), m_Deferred(B))))))
     return BinaryOperator::CreateXor(A, 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)
   if (Op0->hasOneUse() || Op1->hasOneUse())
-    if (match(Op0, m_c_Or(m_Value(A), m_Not(m_Value(B)))) &&
-        match(Op1, m_c_Or(m_Not(m_Specific(A)), m_Specific(B))))
+    if (match(&I, m_BinOp(m_c_Or(m_Value(A), m_Not(m_Value(B))),
+                          m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B)))))
       return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
 
   return nullptr;
 }
 
 static Instruction *foldOrToXor(BinaryOperator &I,
                                 InstCombiner::BuilderTy &Builder) {
   assert(I.getOpcode() == Instruction::Or);
static Instruction *foldXorToXor(BinaryOperator &I,
   Value *A, *B;
 
   // There are 4 commuted variants for each of the basic patterns.
 
   // (A & B) ^ (A | B) -> A ^ B
   // (A & B) ^ (B | A) -> A ^ B
   // (A | B) ^ (A & B) -> A ^ B
   // (A | B) ^ (B & A) -> A ^ B
-  if ((match(Op0, m_And(m_Value(A), m_Value(B))) &&
-       match(Op1, m_c_Or(m_Specific(A), m_Specific(B)))) ||
-      (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
-       match(Op1, m_c_And(m_Specific(A), m_Specific(B))))) {
+  if (match(&I, m_c_Xor(m_And(m_Value(A), m_Value(B)),
+                        m_c_Or(m_Deferred(A), m_Deferred(B))))) {
     I.setOperand(0, A);
     I.setOperand(1, B);
     return &I;
   }
 
   // (A | ~B) ^ (~A | B) -> A ^ B
   // (~B | A) ^ (~A | B) -> A ^ B
   // (~A | B) ^ (A | ~B) -> A ^ B
   // (B | ~A) ^ (A | ~B) -> A ^ B
-  if ((match(Op0, m_Or(m_Value(A), m_Not(m_Value(B)))) &&
-       match(Op1, m_c_Or(m_Not(m_Specific(A)), m_Specific(B)))) ||
-      (match(Op0, m_Or(m_Not(m_Value(A)), m_Value(B))) &&
-       match(Op1, m_c_Or(m_Specific(A), m_Not(m_Specific(B)))))) {
+  if (match(&I, m_Xor(m_c_Or(m_Value(A), m_Not(m_Value(B))),
+                      m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B))))) {
     I.setOperand(0, A);
     I.setOperand(1, B);
     return &I;
   }
 
   // (A & ~B) ^ (~A & B) -> A ^ B
   // (~B & A) ^ (~A & B) -> A ^ B
   // (~A & B) ^ (A & ~B) -> A ^ B
   // (B & ~A) ^ (A & ~B) -> A ^ B
-  if ((match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) &&
-       match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))) ||
-      (match(Op0, m_And(m_Not(m_Value(A)), m_Value(B))) &&
-       match(Op1, m_c_And(m_Specific(A), m_Not(m_Specific(B)))))) {
+  if (match(&I, m_Xor(m_c_And(m_Value(A), m_Not(m_Value(B))),
+                      m_c_And(m_Not(m_Deferred(A)), m_Deferred(B))))) {
     I.setOperand(0, A);
     I.setOperand(1, B);
     return &I;
   }
 
   // For the remaining cases we need to get rid of one of the operands.
   if (!Op0->hasOneUse() && !Op1->hasOneUse())
     return nullptr;

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

;
   %xor = xor i32 %or, %and
   ret i32 %xor
 }
 
 ; (a | b) ^ (b & a) --> a ^ b
 
 define i32 @xor_to_xor4(i32 %a, i32 %b) {
 ; CHECK-LABEL: @xor_to_xor4(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %or = or i32 %a, %b
   %and = and i32 %b, %a
   %xor = xor i32 %or, %and
   ret i32 %xor
 }
 

 }
 
 ; (~a | b) ^ (a | ~b) --> a ^ b
 
 define i32 @xor_to_xor7(float %fa, float %fb) {
 ; CHECK-LABEL: @xor_to_xor7(
 ; CHECK-NEXT:    [[A:%.*]] = fptosi float [[FA:%.*]] to i32
 ; CHECK-NEXT:    [[B:%.*]] = fptosi float [[FB:%.*]] to i32
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[A]], [[B]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[B]], [[A]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %a = fptosi float %fa to i32
   %b = fptosi float %fb to i32
   %nota = xor i32 %a, -1
   %notb = xor i32 %b, -1
   %or1 = or i32 %a, %notb
   %or2 = or i32 %nota, %b
   %xor = xor i32 %or2, %or1
   ret i32 %xor
 }
 
 ; (~a | b) ^ (~b | a) --> a ^ b
 
 define i32 @xor_to_xor8(float %fa, float %fb) {
 ; CHECK-LABEL: @xor_to_xor8(
 ; CHECK-NEXT:    [[A:%.*]] = fptosi float [[FA:%.*]] to i32
 ; CHECK-NEXT:    [[B:%.*]] = fptosi float [[FB:%.*]] to i32
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[A]], [[B]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[B]], [[A]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %a = fptosi float %fa to i32
   %b = fptosi float %fb to i32
   %nota = xor i32 %a, -1
   %notb = xor i32 %b, -1
   %or1 = or i32 %notb, %a
   %or2 = or i32 %nota, %b

 }
 
 ; (~a & b) ^ (a & ~b) --> a ^ b
 
 define i32 @xor_to_xor11(float %fa, float %fb) {
 ; CHECK-LABEL: @xor_to_xor11(
 ; CHECK-NEXT:    [[A:%.*]] = fptosi float [[FA:%.*]] to i32
 ; CHECK-NEXT:    [[B:%.*]] = fptosi float [[FB:%.*]] to i32
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[A]], [[B]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[B]], [[A]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %a = fptosi float %fa to i32
   %b = fptosi float %fb to i32
   %nota = xor i32 %a, -1
   %notb = xor i32 %b, -1
   %and1 = and i32 %a, %notb
   %and2 = and i32 %nota, %b
   %xor = xor i32 %and2, %and1
   ret i32 %xor
 }
 
 ; (~a & b) ^ (~b & a) --> a ^ b
 
 define i32 @xor_to_xor12(float %fa, float %fb) {
 ; CHECK-LABEL: @xor_to_xor12(
 ; CHECK-NEXT:    [[A:%.*]] = fptosi float [[FA:%.*]] to i32
 ; CHECK-NEXT:    [[B:%.*]] = fptosi float [[FB:%.*]] to i32
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[A]], [[B]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[B]], [[A]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %a = fptosi float %fa to i32
   %b = fptosi float %fb to i32
   %nota = xor i32 %a, -1
   %notb = xor i32 %b, -1
   %and1 = and i32 %notb, %a
   %and2 = and i32 %nota, %b

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

;
   %2 = or i32 %y, %x
   %3 = xor i32 %2, %1
   ret i32 %3
 }
 
 ; ((x | ~y) ^ (~x | y)) -> x ^ y
 define i32 @test14(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test14(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], [[X:%.*]]
+; 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 %x, %noty
   %or2 = or i32 %notx, %y
   %xor = xor i32 %or1, %or2
   ret i32 %xor
 }
 
 define i32 @test14_commuted(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test14_commuted(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], [[X:%.*]]
+; 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 [[Y:%.*]], [[X:%.*]]
+; 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
 }
 
 define i32 @test15_commuted(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test15_commuted(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], [[X:%.*]]
+; 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/unittests/IR/PatternMatch.cpp

TEST_F(PatternMatchTest, OneUse) {
 
   EXPECT_TRUE(m_OneUse(m_Value(V)).match(One));
   EXPECT_EQ(One, V);
 
   EXPECT_FALSE(m_OneUse(m_Value()).match(Two));
   EXPECT_FALSE(m_OneUse(m_Value()).match(Leaf));
 }
 
+TEST_F(PatternMatchTest, CommutativeDeferredValue) {
+  Value *X = IRB.getInt32(1);
+  Value *Y = IRB.getInt32(2);
+
+  {
+    Value *tX = X;
+    EXPECT_TRUE(match(X, m_Deferred(tX)));
+    EXPECT_FALSE(match(Y, m_Deferred(tX)));
+  }
+  {
+    const Value *tX = X;
+    EXPECT_TRUE(match(X, m_Deferred(tX)));
+    EXPECT_FALSE(match(Y, m_Deferred(tX)));
+  }
+  {
+    Value *const tX = X;
+    EXPECT_TRUE(match(X, m_Deferred(tX)));
+    EXPECT_FALSE(match(Y, m_Deferred(tX)));
+  }
+  {
+    const Value *const tX = X;
+    EXPECT_TRUE(match(X, m_Deferred(tX)));
+    EXPECT_FALSE(match(Y, m_Deferred(tX)));
+  }
+
+  {
+    Value *tX = nullptr;
+    EXPECT_TRUE(match(IRB.CreateAnd(X, X), m_And(m_Value(tX), m_Deferred(tX))));
+    EXPECT_EQ(tX, X);
+  }
+  {
+    Value *tX = nullptr;
+    EXPECT_FALSE(
+        match(IRB.CreateAnd(X, Y), m_c_And(m_Value(tX), m_Deferred(tX))));
+  }
+
+  auto checkMatch = [X, Y](Value *Pattern) {
+    Value *tX = nullptr, *tY = nullptr;
+    EXPECT_TRUE(match(
+        Pattern, m_c_And(m_Value(tX), m_c_And(m_Deferred(tX), m_Value(tY)))));
+    EXPECT_EQ(tX, X);
+    EXPECT_EQ(tY, Y);
+  };
+
+  checkMatch(IRB.CreateAnd(X, IRB.CreateAnd(X, Y)));
+  checkMatch(IRB.CreateAnd(X, IRB.CreateAnd(Y, X)));
+  checkMatch(IRB.CreateAnd(IRB.CreateAnd(X, Y), X));
+  checkMatch(IRB.CreateAnd(IRB.CreateAnd(Y, X), X));
+}
+
 TEST_F(PatternMatchTest, FloatingPointOrderedMin) {
   Type *FltTy = IRB.getFloatTy();
   Value *L = ConstantFP::get(FltTy, 1.0);
   Value *R = ConstantFP::get(FltTy, 2.0);
   Value *MatchL, *MatchR;
 
   // Test OLT.
   EXPECT_TRUE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))