AArch64: Fix invalid CCMP emission

[MatzeB]

Summary

The code emitting AND-subtrees used to check whether any of the operands
was an OR in order to figure out if the result needs to be negated.
However the OR could be hidden in further subtrees and not immediately
visible.

Change the code so that canEmitConjunction() determines whether the
result of the generated subtree needs to be negated. Cleanup emission
logic to use this. I also changed the code a bit to make all negation
decisions early before we actually emit the subtrees.

This fixes http://llvm.org/PR39550

[MatzeB]

Putting this up for early review, still need to create a minimal testcase.

[MatzeB]

hmm this is still buggy...

[MatzeB]

After pondering about this again, this should be the correct fix.

[MatzeB]

@mstorsjo could you check if this fixes your original problem?

I think I'm gonna take the time to rework the explanatory comments a bit, since it even took myself the author quite a while to understand things again...

[MatzeB]

• Added two more tests
• Revamped explanation of the transformation. It's better but I fear still very hard to crasp. Oh well it's as good as I can make it right now...

[MatzeB]

fix typos

[MatzeB]

Tweak some more comments.

[MatzeB]

And fix one more variable name typo (sorry for all the updates).

[MatzeB]

And fix one more variable name typo (sorry for all the updates).

[mstorsjo]

I haven't tried to follow the exact detail of the change, but the overall change looks correct based on what I learnt from reproducing the issue originally, and I can confirm that it fixes my issue (both reduced and full original case). Thanks!

[mstorsjo]

@ab Can you have a look on this one?

Or is @MatzeB confident enough in the change as is?

Also, should we try to get this, together with the preceding refactoring, into 7.0.1?

[MatzeB]

Maybe you can give it at least some cursory review?

Adding some more reviewers who were active in AArch64ISelLowering recently.

Or is @MatzeB confident enough in the change as is?
Also, should we try to get this, together with the preceding refactoring, into 7.0.1?

I feel confident that this code is bettter than before. And I would also recommend pushing it for 7.0.1 (if we had it on the buildbots for a couple days) considering that it fixes a miscompile in "normal" code.

test/CodeGen/AArch64/arm64-ccmp.ll

529–530

Note those changes here and in the next test are benign, the result is the same either way (I even tested this with a program that tries all possible combinations of float numbers generating different comparison results).

[mstorsjo]

In D54137#1293804, @MatzeB wrote:

Maybe you can give it at least some cursory review?

It LGTM from my cursory review, still leaving it open in case any of the other reviewers wants to pitch in, otherwise I'll mark it as approved early next week.

[efriedma]

lib/Target/AArch64/AArch64ISelLowering.cpp

1553

Maybe include a second step here, which explicitly reassociates this expression?

1563

Would it be possible to use an extra CCMP to "negate" a condition, using something like "ccmp xzr, xzr"? I'm not sure it's actually a good idea, but it seems feasible.

1609

Missing documentation for WillNegate?

1609

In other words, MustBeFirst is true when the outermost expression of the transformed tree is a "not", as opposed to an "and" or a "setcc"?

1640–1641

IsOR?

[mstorsjo]

Ping @MatzeB

[mstorsjo]

In D54137#1293804, @MatzeB wrote:

Maybe you can give it at least some cursory review?

Adding some more reviewers who were active in AArch64ISelLowering recently.

Or is @MatzeB confident enough in the change as is?
Also, should we try to get this, together with the preceding refactoring, into 7.0.1?

I feel confident that this code is bettter than before. And I would also recommend pushing it for 7.0.1 (if we had it on the buildbots for a couple days) considering that it fixes a miscompile in "normal" code.

@tstellar FYI, there's interest in getting this in for 7.0.1, but it's still pending @MatzeB's response to @efriedma's comments. But of course, I understand that if it doesn't make the merge request deadline, then it'll have to be skipped.

[MatzeB]

• Address review feedback

[efriedma]

LGTM

[mstorsjo]

@MatzeB Do you have time to commit this?

lib/Target/AArch64/AArch64ISelLowering.cpp

 /// a comparison. They set the NZCV flags to a predefined value if their
 /// predicate is false. This allows to express arbitrary conjunctions, for
 /// example "cmp 0 (and (setCA (cmp A)) (setCB (cmp B)))"
 /// expressed as:
 ///   cmp A
 ///   ccmp B, inv(CB), CA
 ///   check for CB flags
 ///
-/// In general we can create code for arbitrary "... (and (and A B) C)"
-/// sequences. We can also implement some "or" expressions, because "(or A B)"
-/// is equivalent to "not (and (not A) (not B))" and we can implement some
-/// negation operations:
-/// We can negate the results of a single comparison by inverting the flags
-/// used when the predicate fails and inverting the flags tested in the next
-/// instruction; We can also negate the results of the whole previous
-/// conditional compare sequence by inverting the flags tested in the next
-/// instruction. However there is no way to negate the result of a partial
-/// sequence.
+/// This allows us to implement chains of ADD operations with SETCC operands.
+/// We can in some cases deal with NEG operations:
+///   - We can implement (NEG SETCC) i.e. negating a single comparison by
+///     negating the flags used in a CCMP/FCCMP operations.
+///   - We can negate the result of a whole chain of CMP/CCMP/FCCMP operations
+///     by negating the flags we test for afterwards. i.e.
+///     NEG (CMP CCMP CCCMP ...) can be implemented.
+///   - Note that we can only ever negate all previously processed results.
+///     What we can not implement by flipping the flags to test is a negation
+///     of two sub-trees (because the negation affects all sub-trees emitted so
+///     far, so the 2nd sub-tree we emit would also affect the first).
+/// With those tools we can implement some OR operations:
+///   - (OR (SETCC A) (SETCC B)) can be implemented via:
+///     NEG (AND (NEG (SETCC A)) (NEG (SETCC B)))
+///   - After transforming OR to NEG/AND combinations we may be able to use NEG
+///     elimination rules from earlier to implement the whole thing as a
+///     CCMP/FCCMP chain.
 ///
-/// Therefore on encountering an "or" expression we can negate the subtree on
-/// one side and have to be able to push the negate to the leafs of the subtree
-/// on the other side (see also the comments in code). As complete example:
+/// As complete example:
 /// "or (or (setCA (cmp A)) (setCB (cmp B)))
 ///     (and (setCC (cmp C)) (setCD (cmp D)))"
 /// is transformed to
 /// "not (and (not (and (setCC (cmp C)) (setCC (cmp D))))
 ///           (and (not (setCA (cmp A)) (not (setCB (cmp B))))))"
 /// and implemented as:
 ///   cmp C
 ///   ccmp D, inv(CD), CC
 ///   ccmp A, CA, inv(CD)
 ///   ccmp B, CB, inv(CA)
 ///   check for CB flags
-/// A counterexample is "or (and A B) (and C D)" which cannot be implemented
-/// by conditional compare sequences.
+///
+/// A counterexample is "or (and A B) (and C D)" which translates to
+/// not (and (not (and (not A) (not B))) (not (and (not C) (not D)))), we
+/// can only implement 1 of the inner (not) operations, by implementing them
+/// but not both!
 /// @{
 
 /// Create a conditional comparison; Use CCMP, CCMN or FCCMP as appropriate.
 static SDValue emitConditionalComparison(SDValue LHS, SDValue RHS,
                                          ISD::CondCode CC, SDValue CCOp,
                                          AArch64CC::CondCode Predicate,
                                          AArch64CC::CondCode OutCC,
                                          const SDLoc &DL, SelectionDAG &DAG) {
static SDValue emitConditionalComparison(SDValue LHS, SDValue RHS,
   AArch64CC::CondCode InvOutCC = AArch64CC::getInvertedCondCode(OutCC);
   unsigned NZCV = AArch64CC::getNZCVToSatisfyCondCode(InvOutCC);
   SDValue NZCVOp = DAG.getConstant(NZCV, DL, MVT::i32);
   return DAG.getNode(Opcode, DL, MVT_CC, LHS, RHS, NZCVOp, Condition, CCOp);
 }
 
 /// Returns true if @p Val is a tree of AND/OR/SETCC operations that can be
 /// 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 CanNegate    Set to true if we can also emit the negation of the tree
+///                     as a conjunction.
+/// \param MustBeFirst  Set to true if we must emit this subtree first because
+///                     we negate the condition to test.
 static bool canEmitConjunction(const SDValue Val, bool &CanNegate,
+                               bool &MustBeFirst, bool WillNegate,
                                unsigned Depth = 0) {
   if (!Val.hasOneUse())
     return false;
   unsigned Opcode = Val->getOpcode();
   if (Opcode == ISD::SETCC) {
     if (Val->getOperand(0).getValueType() == MVT::f128)
       return false;
     CanNegate = true;
+    MustBeFirst = false;
     return true;
   }
   // Protect against exponential runtime and stack overflow.
   if (Depth > 6)
     return false;
   if (Opcode == ISD::AND || Opcode == ISD::OR) {
+    bool IsOR = Opcode == ISD::OR;
     SDValue O0 = Val->getOperand(0);
     SDValue O1 = Val->getOperand(1);
     bool CanNegateL;
-    if (!canEmitConjunction(O0, CanNegateL, Depth+1))
+    bool MustBeFirstL;
+    if (!canEmitConjunction(O0, CanNegateL, MustBeFirstL, IsOR, Depth+1))
       return false;
     bool CanNegateR;
-    if (!canEmitConjunction(O1, CanNegateR, Depth+1))
+    bool MustBeFirstR;
+    if (!canEmitConjunction(O1, CanNegateR, MustBeFirstR, IsOR, Depth+1))
+      return false;
+
+    if (MustBeFirstL && MustBeFirstR)
       return false;
 
     if (Opcode == ISD::OR) {
       // For an OR expression we need to be able to negate at least one side or
       // we cannot do the transformation at all.
       if (!CanNegateL && !CanNegateR)
         return false;
       // However if we can negate x and y, then we can change
       // (not (or x y))
       // into
       // (and (not x) (not y))
       // to eliminate the outer negation.
       CanNegate = CanNegateL && CanNegateR;
+      // Usually we need to negate the result of an OR so it must come first,
+      // however if we can negate the operands for free and the OR itself will
+      // get negated (because it is the operand of another or) then we don't
+      // need to be first.
+      MustBeFirst = !WillNegate || !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)
-        return false;
       // We cannot negate an AND operation.
       CanNegate = false;
+      MustBeFirst = MustBeFirstL || MustBeFirstR;
     }
     return true;
   }
   return false;
 }
 
 /// Emit conjunction or disjunction tree with the CMP/FCMP followed by a chain
 /// of CCMP/CFCMP ops. See @ref AArch64CCMP.
if (Opcode == ISD::SETCC) {
 
     // Produce a normal comparison if we are first in the chain
     if (!CCOp)
       return emitComparison(LHS, RHS, CC, DL, DAG);
     // Otherwise produce a ccmp.
     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);
+  bool IsOR = Opcode == ISD::OR;
 
-  // 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;
+  SDValue LHS = Val->getOperand(0);
+  bool MustBeFirstL;
+  bool ValidL = canEmitConjunction(LHS, CanNegateL, MustBeFirstL, IsOR);
+  assert(ValidL && "Valid conjunction/disjunction tree");
+  (void)ValidL;
 
-#ifndef NDEBUG
-    bool CanNegateR;
-    bool isValidR = canEmitConjunction(RHS, CanNegateR);
-    assert(isValidR && "Valid conjunction/disjunction tree");
-    assert((CanNegateL || CanNegateR) && "Valid conjunction/disjunction tree");
-#endif
+  SDValue RHS = Val->getOperand(1);
+  bool MustBeFirstR;
+  bool ValidR = canEmitConjunction(RHS, CanNegateR, MustBeFirstR, IsOR);
+  assert(ValidR && "Valid conjunction/disjunction tree");
+  (void)ValidR;
+
+  // Swap subtree that needs the result negated to the right if necessary.
+  if (MustBeFirstL) {
+    assert(!MustBeFirstR && "Valid conjunction/disjunction tree");
+    std::swap(LHS, RHS);
+    std::swap(CanNegateL, CanNegateR);
+    std::swap(MustBeFirstL, MustBeFirstR);
+  }
 
-    // Order the side which we cannot negate to RHS so we can emit it first.
-    if (!CanNegateL)
+  bool NegateR;
+  bool NegateAfterR;
+  bool NegateL;
+  bool NegateAfterAll;
+  if (Opcode == ISD::OR) {
+    // Swap negatable subtree to the left side if necessary.
+    if (!CanNegateL) {
+      assert(CanNegateR && "at least one side must be negatable");
+      assert(!MustBeFirstR && "invalid conjunction/disjunction tree");
+      assert(!Negate);
       std::swap(LHS, RHS);
+      NegateR = false;
+      NegateAfterR = true;
     } 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)
-      std::swap(LHS, RHS);
+      // Negate the left subtree if possible, otherwise negate the result.
+      NegateR = CanNegateR;
+      NegateAfterR = !CanNegateR;
+    }
+    NegateL = true;
+    NegateAfterAll = !Negate;
+  } else {
+    assert(Opcode == ISD::AND && "Valid conjunction/disjunction tree");
+    assert(!Negate && "Valid conjunction/disjunction tree");
+
+    NegateL = false;
+    NegateR = false;
+    NegateAfterR = false;
+    NegateAfterAll = 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)
+  SDValue CmpR = emitConjunctionRec(DAG, RHS, RHSCC, NegateR, CCOp, Predicate);
+  if (NegateAfterR)
     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 CmpL = emitConjunctionRec(DAG, LHS, OutCC, NegateL, CmpR, RHSCC);
+  if (NegateAfterAll)
     OutCC = AArch64CC::getInvertedCondCode(OutCC);
   return CmpL;
 }
 
 /// Emit expression as a conjunction (a series of CCMP/CFCMP ops).
 /// In some cases this is even possible with OR operations in the expression.
 /// See \ref AArch64CCMP.
 /// \see emitConjunctionRec().
 static SDValue emitConjunction(SelectionDAG &DAG, SDValue Val,
                                AArch64CC::CondCode &OutCC) {
   bool DummyCanNegate;
-  if (!canEmitConjunction(Val, DummyCanNegate))
+  bool DummyResultNeedsNeg;
+  if (!canEmitConjunction(Val, DummyCanNegate, DummyResultNeedsNeg, false))
     return SDValue();
 
   return emitConjunctionRec(DAG, Val, OutCC, false, SDValue(), AArch64CC::AL);
 }
 
 /// @}
 
 /// Returns how profitable it is to fold a comparison's operand's shift and/or

test/CodeGen/AArch64/arm64-ccmp.ll

define i32 @select_or_olt_one(double %v0, double %v1, double %v2, double %v3, i32 %a, i32 %b) #0 {
   %cr = or i1 %c1, %c0
   %sel = select i1 %cr, i32 %a, i32 %b
   ret i32 %sel
 }
 
 ; CHECK-LABEL: select_or_one_olt:
 ; CHECK-LABEL: ; %bb.0:
 ; CHECK-NEXT: fcmp d0, d1
-; CHECK-NEXT: fccmp d0, d1, #1, ne
-; CHECK-NEXT: fccmp d2, d3, #8, vs
+; CHECK-NEXT: fccmp d0, d1, #8, le
+; CHECK-NEXT: fccmp d2, d3, #8, pl
 ; CHECK-NEXT: csel w0, w0, w1, mi
 ; CHECK-NEXT: ret
 define i32 @select_or_one_olt(double %v0, double %v1, double %v2, double %v3, i32 %a, i32 %b) #0 {
   %c0 = fcmp one double %v0, %v1
   %c1 = fcmp olt double %v2, %v3
   %cr = or i1 %c1, %c0
   %sel = select i1 %cr, i32 %a, i32 %b
   ret i32 %sel
define i32 @select_or_olt_ueq(double %v0, double %v1, double %v2, double %v3, i32 %a, i32 %b) #0 {
   %cr = or i1 %c1, %c0
   %sel = select i1 %cr, i32 %a, i32 %b
   ret i32 %sel
 }
 
 ; CHECK-LABEL: select_or_ueq_olt:
 ; CHECK-LABEL: ; %bb.0:
 ; CHECK-NEXT: fcmp d0, d1
-; CHECK-NEXT: fccmp d0, d1, #8, le
-; CHECK-NEXT: fccmp d2, d3, #8, mi
+; CHECK-NEXT: fccmp d0, d1, #1, ne
+; CHECK-NEXT: fccmp d2, d3, #8, vc
 ; CHECK-NEXT: csel w0, w0, w1, mi
 ; CHECK-NEXT: ret
 define i32 @select_or_ueq_olt(double %v0, double %v1, double %v2, double %v3, i32 %a, i32 %b) #0 {
   %c0 = fcmp ueq double %v0, %v1
   %c1 = fcmp olt double %v2, %v3
   %cr = or i1 %c1, %c0
   %sel = select i1 %cr, i32 %a, i32 %b
   ret i32 %sel

 define i32 @f128_select_and_olt_oge(fp128 %v0, fp128 %v1, fp128 %v2, fp128 %v3, i32 %a, i32 %b) #0 {
   %c0 = fcmp olt fp128 %v0, %v1
   %c1 = fcmp oge fp128 %v2, %v3
   %cr = and i1 %c1, %c0
   %sel = select i1 %cr, i32 %a, i32 %b
   ret i32 %sel
 }
 
+; This testcase resembles the core problem of http://llvm.org/PR39550
+; (an OR operation is 2 levels deep but needs to be implemented first)
+; CHECK-LABEL: deep_or
+; CHECK: cmp w2, #20
+; CHECK-NEXT: ccmp w2, #15, #4, ne
+; CHECK-NEXT: ccmp w1, #0, #4, eq
+; CHECK-NEXT: ccmp w0, #0, #4, ne
+; CHECK-NEXT: csel w0, w4, w5, ne
+; CHECK-NEXT: ret
+define i32 @deep_or(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %x, i32 %y) {
+  %c0 = icmp ne i32 %a0, 0
+  %c1 = icmp ne i32 %a1, 0
+  %c2 = icmp eq i32 %a2, 15
+  %c3 = icmp eq i32 %a2, 20
+
+  %or = or i1 %c2, %c3
+  %and0 = and i1 %or, %c1
+  %and1 = and i1 %and0, %c0
+  %sel = select i1 %and1, i32 %x, i32 %y
+  ret i32 %sel
+}
+
+; Variation of deep_or, we still need to implement the OR first though.
+; CHECK-LABEL: deep_or1
+; CHECK: cmp w2, #20
+; CHECK-NEXT: ccmp w2, #15, #4, ne
+; CHECK-NEXT: ccmp w0, #0, #4, eq
+; CHECK-NEXT: ccmp w1, #0, #4, ne
+; CHECK-NEXT: csel w0, w4, w5, ne
+; CHECK-NEXT: ret
+define i32 @deep_or1(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %x, i32 %y) {
+  %c0 = icmp ne i32 %a0, 0
+  %c1 = icmp ne i32 %a1, 0
+  %c2 = icmp eq i32 %a2, 15
+  %c3 = icmp eq i32 %a2, 20
+
+  %or = or i1 %c2, %c3
+  %and0 = and i1 %c0, %or
+  %and1 = and i1 %and0, %c1
+  %sel = select i1 %and1, i32 %x, i32 %y
+  ret i32 %sel
+}
+
+; Variation of deep_or, we still need to implement the OR first though.
+; CHECK-LABEL: deep_or2
+; CHECK: cmp w2, #20
+; CHECK-NEXT: ccmp w2, #15, #4, ne
+; CHECK-NEXT: ccmp w1, #0, #4, eq
+; CHECK-NEXT: ccmp w0, #0, #4, ne
+; CHECK-NEXT: csel w0, w4, w5, ne
+; CHECK-NEXT: ret
+define i32 @deep_or2(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %x, i32 %y) {
+  %c0 = icmp ne i32 %a0, 0
+  %c1 = icmp ne i32 %a1, 0
+  %c2 = icmp eq i32 %a2, 15
+  %c3 = icmp eq i32 %a2, 20
+
+  %or = or i1 %c2, %c3
+  %and0 = and i1 %c0, %c1
+  %and1 = and i1 %and0, %or
+  %sel = select i1 %and1, i32 %x, i32 %y
+  ret i32 %sel
+}
+
 attributes #0 = { nounwind }