[TargetLowering] Change SimplifyDemandedBits for XOR

[foad]

Summary

Don't simplify XOR to AND whenever we can, because it's not clear
(to me) that it's simpler.

Instead simplify:

(X | C) ^ C -> X & ~C
(X & ~C) ^ C -> X | C

These are clearly better because they remove one operation.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

1363

ISD::AND ?

[RKSimon]

@foad Reverse ping

[foad]

Rebase.

[foad]

Fix ISD::OR -> ISD::AND.

[foad]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

1363

Good spot. Fixed. This patch no longer seems to improve anything (and I only wrote it in the first place to address some regressions in D87145, which has since been landed) so I guess I'll abandon it unless you have some particular interest in it?

[lebedev.ri]

This seems to lack description/motivation/test cases.
Why do we not want to strength-reduce xor into an and?

[foad]

In D87465#2625799, @lebedev.ri wrote:

This seems to lack description/motivation/test cases.
Why do we not want to strength-reduce xor into an and?

The original motivation was here: https://reviews.llvm.org/D87145?id=289963#inline-807379

But that problem was fixed in other ways, so I'll give up on this now.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

case ISD::XOR: {
 
     // If all of the unknown bits are known to be zero on one side or the other
     // turn this into an *inclusive* or.
     //    e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
     if (DemandedBits.isSubsetOf(Known.Zero | Known2.Zero))
       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, dl, VT, Op0, Op1));
 
     ConstantSDNode* C = isConstOrConstSplat(Op1, DemandedElts);
-    if (C) {
-      // If one side is a constant, and all of the set bits in the constant are
-      // also known set on the other side, turn this into an AND, as we know
-      // the bits will be cleared.
-      //    e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
-      // NB: it is okay if more bits are known than are requested
-      if (C->getAPIntValue() == Known2.One) {
-        SDValue ANDC =
+    if (C && (Op0.getOpcode() == ISD::OR || Op0.getOpcode() == ISD::AND)) {
+      ConstantSDNode *C1 = isConstOrConstSplat(Op0.getOperand(1), DemandedElts);
+      if (C1) {
+        // (X | C) ^ C -> X & ~C
+        if (Op0.getOpcode() == ISD::OR &&
+            !((C->getAPIntValue() ^ C1->getAPIntValue()) & DemandedBits)) {
+          SDValue NOTC =
               TLO.DAG.getConstant(~C->getAPIntValue() & DemandedBits, dl, VT);
-        return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, dl, VT, Op0, ANDC));
-      }
+          return TLO.CombineTo(
+              Op, TLO.DAG.getNode(ISD::AND, dl, VT, Op0.getOperand(0), NOTC));
+        }
+
+        // (X & ~C) ^ C -> X | C
+        // TODO do this for the non-constant case too? I.e. (X & Y) ^ Z -> X | Z
+        // when all demanded bits of Y and Z are known to be different
+        if (Op0.getOpcode() == ISD::AND &&
+            DemandedBits.isSubsetOf(C->getAPIntValue() ^ C1->getAPIntValue()))
+          return TLO.CombineTo(
+              Op, TLO.DAG.getNode(ISD::AND, dl, VT, Op0.getOperand(0), Op1));
+      }
 
-      // If the RHS is a constant, see if we can change it. Don't alter a -1
-      // constant because that's a 'not' op, and that is better for combining
-      // and codegen.
-      if (!C->isAllOnesValue() &&
-          DemandedBits.isSubsetOf(C->getAPIntValue())) {
-        // We're flipping all demanded bits. Flip the undemanded bits too.
-        SDValue New = TLO.DAG.getNOT(dl, Op0, VT);
-        return TLO.CombineTo(Op, New);
-      }
-    }
+    if (C && !C->isAllOnesValue() &&
 
     // If we can't turn this into a 'not', try to shrink the constant.
     if (!C || !C->isAllOnesValue())
       if (ShrinkDemandedConstant(Op, DemandedBits, DemandedElts, TLO))
         return true;
 
     Known ^= Known2;
     break;

llvm/test/CodeGen/X86/2012-08-07-CmpISelBug.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-apple-macosx | FileCheck %s
 
 ; Cmp lowering should not look past the truncate unless the high bits are known
 ; zero.
 ; rdar://12027825
 
 define void @foo(i8 %arg4, i32 %arg5, i32* %arg14) nounwind {
 ; CHECK-LABEL: foo:
 ; CHECK:       ## %bb.0: ## %bb
 ; CHECK-NEXT:    ## kill: def $edi killed $edi def $rdi
 ; CHECK-NEXT:    andl $32, %edi
 ; CHECK-NEXT:    leal 13(%rdi), %eax
 ; CHECK-NEXT:    xorb $-14, %al
 ; CHECK-NEXT:    addb $82, %al
-; CHECK-NEXT:    movzbl %al, %eax
 ; CHECK-NEXT:    testl %esi, %edi
+; CHECK-NEXT:    movzbl %al, %eax
 ; CHECK-NEXT:    movl $1, %ecx
 ; CHECK-NEXT:    cmovnel %eax, %ecx
 ; CHECK-NEXT:    xorb $81, %cl
 ; CHECK-NEXT:    movzbl %cl, %eax
 ; CHECK-NEXT:    addl $2062143348, %eax ## imm = 0x7AE9CF74
 ; CHECK-NEXT:    movl %eax, (%rdx)
 ; CHECK-NEXT:    retq
 bb: