Index: lib/Target/AArch64/AArch64ISelLowering.cpp
===================================================================
--- lib/Target/AArch64/AArch64ISelLowering.cpp
+++ lib/Target/AArch64/AArch64ISelLowering.cpp
@@ -1595,8 +1595,10 @@
 /// expressed as a conjunction. See \ref AArch64CCMP.
 /// \param CanNegate        Set to true if we can also emit the negation of the
 ///                         tree as a conjunction.
+/// \param ResultNeedsNeg   Set to true if we would need to negate the result
+///                         of the emitted conjunction.
 static bool canEmitConjunction(const SDValue Val, bool &CanNegate,
-                               unsigned Depth = 0) {
+                               bool &ResultNeedsNeg, unsigned Depth = 0) {
   if (!Val.hasOneUse())
     return false;
   unsigned Opcode = Val->getOpcode();
@@ -1604,6 +1606,7 @@
     if (Val->getOperand(0).getValueType() == MVT::f128)
       return false;
     CanNegate = true;
+    ResultNeedsNeg = false;
     return true;
   }
   // Protect against exponential runtime and stack overflow.
@@ -1613,10 +1616,12 @@
     SDValue O0 = Val->getOperand(0);
     SDValue O1 = Val->getOperand(1);
     bool CanNegateL;
-    if (!canEmitConjunction(O0, CanNegateL, Depth+1))
+    bool ResultNeedsNegL;
+    if (!canEmitConjunction(O0, CanNegateL, ResultNeedsNegL, Depth+1))
       return false;
     bool CanNegateR;
-    if (!canEmitConjunction(O1, CanNegateR, Depth+1))
+    bool ResultNeedsNegR;
+    if (!canEmitConjunction(O1, CanNegateR, ResultNeedsNegR, Depth+1))
       return false;
 
     if (Opcode == ISD::OR) {
@@ -1629,17 +1634,15 @@
       // into
       // (and (not x) (not y))
       // to eliminate the outer negation.
-      CanNegate = CanNegateL && CanNegateR;
+      CanNegate = true;
+      ResultNeedsNeg = !CanNegateL || !CanNegateR;
     } else {
-      // If the operands are OR expressions then we finally need to negate their
-      // outputs, we can only do that for the operand with emitted last by
-      // negating OutCC, not for both operands.
-      bool NeedsNegOutL = O0->getOpcode() == ISD::OR;
-      bool NeedsNegOutR = O1->getOpcode() == ISD::OR;
-      if (NeedsNegOutL && NeedsNegOutR)
+      // Can only negate the results of one side (by emitting that side last).
+      if (ResultNeedsNegL && ResultNeedsNegR)
         return false;
       // We cannot negate an AND operation.
       CanNegate = false;
+      ResultNeedsNeg = ResultNeedsNegL | ResultNeedsNegR;
     }
     return true;
   }
@@ -1697,61 +1700,62 @@
     return emitConditionalComparison(LHS, RHS, CC, CCOp, Predicate, OutCC, DL,
                                      DAG);
   }
-  assert((Opcode == ISD::AND || (Opcode == ISD::OR && Val->hasOneUse())) &&
-         "Valid conjunction/disjunction tree");
+  assert(Val->hasOneUse() && "Valid conjunction/disjunction tree");
 
-  // Check if both sides can be transformed.
   SDValue LHS = Val->getOperand(0);
-  SDValue RHS = Val->getOperand(1);
-
-  // In case of an OR we need to negate our operands and the result.
-  // (A v B) <=> not(not(A) ^ not(B))
-  bool NegateOpsAndResult = Opcode == ISD::OR;
-  // We can negate the results of all previous operations by inverting the
-  // predicate flags giving us a free negation for one side. The other side
-  // must be negatable by itself.
-  if (NegateOpsAndResult) {
-    // See which side we can negate.
-    bool CanNegateL;
-    bool isValidL = canEmitConjunction(LHS, CanNegateL);
-    assert(isValidL && "Valid conjunction/disjunction tree");
-    (void)isValidL;
-
-#ifndef NDEBUG
-    bool CanNegateR;
-    bool isValidR = canEmitConjunction(RHS, CanNegateR);
-    assert(isValidR && "Valid conjunction/disjunction tree");
-    assert((CanNegateL || CanNegateR) && "Valid conjunction/disjunction tree");
-#endif
+  bool CanNegateL;
+  bool ResultNeedsNegL;
+  bool ValidL = canEmitConjunction(LHS, CanNegateL, ResultNeedsNegL);
+  assert(ValidL && "Valid conjunction/disjunction tree");
+  (void)ValidL;
 
-    // Order the side which we cannot negate to RHS so we can emit it first.
-    if (!CanNegateL)
+  SDValue RHS = Val->getOperand(1);
+  bool CanNegateR;
+  bool ResultNeedsNegR;
+  bool ValidR = canEmitConjunction(RHS, CanNegateR, ResultNeedsNegR);
+  assert(ValidR && "Valid conjunction/disjunction tree");
+  (void)ValidR;
+
+  bool ResultNeedsNeg;
+  bool NegateL;
+  bool NegateR;
+  if (Opcode == ISD::OR) {
+    NegateR = true;
+    ResultNeedsNeg = Negate;
+    // Swap negatable subtree to the right side if necessary so it gets emitted
+    // first.
+    if (!CanNegateR) {
+      assert(CanNegateL && "at least one side must be negatable for free");
       std::swap(LHS, RHS);
+      NegateL = false;
+      ResultNeedsNeg = true;
+    } else {
+      // Negate the left subtree if possible, otherwise negate the result.
+      NegateL = CanNegateL;
+      ResultNeedsNeg ^= !CanNegateL;
+    }
   } else {
-    bool NeedsNegOutL = LHS->getOpcode() == ISD::OR;
-    assert((!NeedsNegOutL || RHS->getOpcode() != ISD::OR) &&
-           "Valid conjunction/disjunction tree");
-    // Order the side where we need to negate the output flags to RHS so it
-    // gets emitted first.
-    if (NeedsNegOutL)
+    assert(Opcode == ISD::AND && "Valid conjunction/disjunction tree");
+    assert(!Negate && "Valid conjunction/disjunction tree");
+
+    // Swap subtree that needs the result negated to the left if necessary.
+    if (ResultNeedsNegR) {
+      assert(!ResultNeedsNegL && "Valid conjunction/disjunction tree");
       std::swap(LHS, RHS);
+      ResultNeedsNeg = true;
+    } else {
+      ResultNeedsNeg = ResultNeedsNegR;
+    }
+    NegateL = false;
+    NegateR = false;
   }
 
-  // Emit RHS. If we want to negate the tree we only need to push a negate
-  // through if we are already in a PushNegate case, otherwise we can negate
-  // the "flags to test" afterwards.
+  // Emit subtrees.
   AArch64CC::CondCode RHSCC;
-  SDValue CmpR = emitConjunctionRec(DAG, RHS, RHSCC, Negate,
-                                                   CCOp, Predicate);
-  if (NegateOpsAndResult && !Negate)
-    RHSCC = AArch64CC::getInvertedCondCode(RHSCC);
-  // Emit LHS. We may need to negate it.
-  SDValue CmpL = emitConjunctionRec(DAG, LHS, OutCC,
-                                                   NegateOpsAndResult, CmpR,
-                                                   RHSCC);
-  // If we transformed an OR to and AND then we have to negate the result
-  // (or absorb the Negate parameter).
-  if (NegateOpsAndResult && !Negate)
+  SDValue CmpR = emitConjunctionRec(DAG, RHS, RHSCC, NegateR, CCOp,
+                                        Predicate);
+  SDValue CmpL = emitConjunctionRec(DAG, LHS, OutCC, NegateL, CmpR, RHSCC);
+  if (ResultNeedsNeg)
     OutCC = AArch64CC::getInvertedCondCode(OutCC);
   return CmpL;
 }
@@ -1763,7 +1767,8 @@
 static SDValue emitConjunction(SelectionDAG &DAG, SDValue Val,
                                AArch64CC::CondCode &OutCC) {
   bool DummyCanNegate;
-  if (!canEmitConjunction(Val, DummyCanNegate))
+  bool DummyResultNeedsNeg;
+  if (!canEmitConjunction(Val, DummyCanNegate, DummyResultNeedsNeg))
     return SDValue();
 
   return emitConjunctionRec(DAG, Val, OutCC, false, SDValue(), AArch64CC::AL);