Move SimplifySetCC to TargetLowering and allow it to be shared with legalizer.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34065 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 421 insertions, 0 deletions

diff --git a/lib/CodeGen/SelectionDAG/TargetLowering.cpp b/lib/CodeGen/SelectionDAG/TargetLowering.cpp
index 2ebce86a03..d43e6a6357 100644
--- a/lib/CodeGen/SelectionDAG/TargetLowering.cpp
+++ b/lib/CodeGen/SelectionDAG/TargetLowering.cpp
@@ -1393,6 +1393,427 @@ unsigned TargetLowering::ComputeNumSignBitsForTargetNode(SDOperand Op,
 }
 
 
+/// SimplifySetCC - Try to simplify a setcc built with the specified operands 
+/// and cc. If it is unable to simplify it, return a null SDOperand.
+SDOperand
+TargetLowering::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
+                              ISD::CondCode Cond, bool foldBooleans,
+                              DAGCombinerInfo &DCI) const {
+  SelectionDAG &DAG = DCI.DAG;
+
+  // These setcc operations always fold.
+  switch (Cond) {
+  default: break;
+  case ISD::SETFALSE:
+  case ISD::SETFALSE2: return DAG.getConstant(0, VT);
+  case ISD::SETTRUE:
+  case ISD::SETTRUE2:  return DAG.getConstant(1, VT);
+  }
+
+  if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
+    uint64_t C1 = N1C->getValue();
+    if (isa<ConstantSDNode>(N0.Val)) {
+      return DAG.FoldSetCC(VT, N0, N1, Cond);
+    } else {
+      // If the LHS is '(srl (ctlz x), 5)', the RHS is 0/1, and this is an
+      // equality comparison, then we're just comparing whether X itself is
+      // zero.
+      if (N0.getOpcode() == ISD::SRL && (C1 == 0 || C1 == 1) &&
+          N0.getOperand(0).getOpcode() == ISD::CTLZ &&
+          N0.getOperand(1).getOpcode() == ISD::Constant) {
+        unsigned ShAmt = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
+        if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
+            ShAmt == Log2_32(MVT::getSizeInBits(N0.getValueType()))) {
+          if ((C1 == 0) == (Cond == ISD::SETEQ)) {
+            // (srl (ctlz x), 5) == 0  -> X != 0
+            // (srl (ctlz x), 5) != 1  -> X != 0
+            Cond = ISD::SETNE;
+          } else {
+            // (srl (ctlz x), 5) != 0  -> X == 0
+            // (srl (ctlz x), 5) == 1  -> X == 0
+            Cond = ISD::SETEQ;
+          }
+          SDOperand Zero = DAG.getConstant(0, N0.getValueType());
+          return DAG.getSetCC(VT, N0.getOperand(0).getOperand(0),
+                              Zero, Cond);
+        }
+      }
+      
+      // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
+      if (N0.getOpcode() == ISD::ZERO_EXTEND) {
+        unsigned InSize = MVT::getSizeInBits(N0.getOperand(0).getValueType());
+
+        // If the comparison constant has bits in the upper part, the
+        // zero-extended value could never match.
+        if (C1 & (~0ULL << InSize)) {
+          unsigned VSize = MVT::getSizeInBits(N0.getValueType());
+          switch (Cond) {
+          case ISD::SETUGT:
+          case ISD::SETUGE:
+          case ISD::SETEQ: return DAG.getConstant(0, VT);
+          case ISD::SETULT:
+          case ISD::SETULE:
+          case ISD::SETNE: return DAG.getConstant(1, VT);
+          case ISD::SETGT:
+          case ISD::SETGE:
+            // True if the sign bit of C1 is set.
+            return DAG.getConstant((C1 & (1ULL << VSize)) != 0, VT);
+          case ISD::SETLT:
+          case ISD::SETLE:
+            // True if the sign bit of C1 isn't set.
+            return DAG.getConstant((C1 & (1ULL << VSize)) == 0, VT);
+          default:
+            break;
+          }
+        }
+
+        // Otherwise, we can perform the comparison with the low bits.
+        switch (Cond) {
+        case ISD::SETEQ:
+        case ISD::SETNE:
+        case ISD::SETUGT:
+        case ISD::SETUGE:
+        case ISD::SETULT:
+        case ISD::SETULE:
+          return DAG.getSetCC(VT, N0.getOperand(0),
+                          DAG.getConstant(C1, N0.getOperand(0).getValueType()),
+                          Cond);
+        default:
+          break;   // todo, be more careful with signed comparisons
+        }
+      } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
+                 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
+        MVT::ValueType ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT();
+        unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy);
+        MVT::ValueType ExtDstTy = N0.getValueType();
+        unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy);
+
+        // If the extended part has any inconsistent bits, it cannot ever
+        // compare equal.  In other words, they have to be all ones or all
+        // zeros.
+        uint64_t ExtBits =
+          (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1));
+        if ((C1 & ExtBits) != 0 && (C1 & ExtBits) != ExtBits)
+          return DAG.getConstant(Cond == ISD::SETNE, VT);
+        
+        SDOperand ZextOp;
+        MVT::ValueType Op0Ty = N0.getOperand(0).getValueType();
+        if (Op0Ty == ExtSrcTy) {
+          ZextOp = N0.getOperand(0);
+        } else {
+          int64_t Imm = ~0ULL >> (64-ExtSrcTyBits);
+          ZextOp = DAG.getNode(ISD::AND, Op0Ty, N0.getOperand(0),
+                               DAG.getConstant(Imm, Op0Ty));
+        }
+        if (!DCI.isCalledByLegalizer())
+          DCI.AddToWorklist(ZextOp.Val);
+        // Otherwise, make this a use of a zext.
+        return DAG.getSetCC(VT, ZextOp, 
+                            DAG.getConstant(C1 & (~0ULL>>(64-ExtSrcTyBits)), 
+                                            ExtDstTy),
+                            Cond);
+      } else if ((N1C->getValue() == 0 || N1C->getValue() == 1) &&
+                 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
+        
+        // SETCC (SETCC), [0|1], [EQ|NE]  -> SETCC
+        if (N0.getOpcode() == ISD::SETCC) {
+          bool TrueWhenTrue = (Cond == ISD::SETEQ) ^ (N1C->getValue() != 1);
+          if (TrueWhenTrue)
+            return N0;
+          
+          // Invert the condition.
+          ISD::CondCode CC = cast<CondCodeSDNode>(N0.getOperand(2))->get();
+          CC = ISD::getSetCCInverse(CC, 
+                               MVT::isInteger(N0.getOperand(0).getValueType()));
+          return DAG.getSetCC(VT, N0.getOperand(0), N0.getOperand(1), CC);
+        }
+        
+        if ((N0.getOpcode() == ISD::XOR ||
+             (N0.getOpcode() == ISD::AND && 
+              N0.getOperand(0).getOpcode() == ISD::XOR &&
+              N0.getOperand(1) == N0.getOperand(0).getOperand(1))) &&
+            isa<ConstantSDNode>(N0.getOperand(1)) &&
+            cast<ConstantSDNode>(N0.getOperand(1))->getValue() == 1) {
+          // If this is (X^1) == 0/1, swap the RHS and eliminate the xor.  We
+          // can only do this if the top bits are known zero.
+          if (MaskedValueIsZero(N0, MVT::getIntVTBitMask(N0.getValueType())-1)){
+            // Okay, get the un-inverted input value.
+            SDOperand Val;
+            if (N0.getOpcode() == ISD::XOR)
+              Val = N0.getOperand(0);
+            else {
+              assert(N0.getOpcode() == ISD::AND && 
+                     N0.getOperand(0).getOpcode() == ISD::XOR);
+              // ((X^1)&1)^1 -> X & 1
+              Val = DAG.getNode(ISD::AND, N0.getValueType(),
+                                N0.getOperand(0).getOperand(0),
+                                N0.getOperand(1));
+            }
+            return DAG.getSetCC(VT, Val, N1,
+                                Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
+          }
+        }
+      }
+      
+      uint64_t MinVal, MaxVal;
+      unsigned OperandBitSize = MVT::getSizeInBits(N1C->getValueType(0));
+      if (ISD::isSignedIntSetCC(Cond)) {
+        MinVal = 1ULL << (OperandBitSize-1);
+        if (OperandBitSize != 1)   // Avoid X >> 64, which is undefined.
+          MaxVal = ~0ULL >> (65-OperandBitSize);
+        else
+          MaxVal = 0;
+      } else {
+        MinVal = 0;
+        MaxVal = ~0ULL >> (64-OperandBitSize);
+      }
+
+      // Canonicalize GE/LE comparisons to use GT/LT comparisons.
+      if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
+        if (C1 == MinVal) return DAG.getConstant(1, VT);   // X >= MIN --> true
+        --C1;                                          // X >= C0 --> X > (C0-1)
+        return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()),
+                        (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT);
+      }
+
+      if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
+        if (C1 == MaxVal) return DAG.getConstant(1, VT);   // X <= MAX --> true
+        ++C1;                                          // X <= C0 --> X < (C0+1)
+        return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()),
+                        (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT);
+      }
+
+      if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal)
+        return DAG.getConstant(0, VT);      // X < MIN --> false
+      if ((Cond == ISD::SETGE || Cond == ISD::SETUGE) && C1 == MinVal)
+        return DAG.getConstant(1, VT);      // X >= MIN --> true
+      if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal)
+        return DAG.getConstant(0, VT);      // X > MAX --> false
+      if ((Cond == ISD::SETLE || Cond == ISD::SETULE) && C1 == MaxVal)
+        return DAG.getConstant(1, VT);      // X <= MAX --> true
+
+      // Canonicalize setgt X, Min --> setne X, Min
+      if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal)
+        return DAG.getSetCC(VT, N0, N1, ISD::SETNE);
+      // Canonicalize setlt X, Max --> setne X, Max
+      if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MaxVal)
+        return DAG.getSetCC(VT, N0, N1, ISD::SETNE);
+
+      // If we have setult X, 1, turn it into seteq X, 0
+      if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1)
+        return DAG.getSetCC(VT, N0, DAG.getConstant(MinVal, N0.getValueType()),
+                        ISD::SETEQ);
+      // If we have setugt X, Max-1, turn it into seteq X, Max
+      else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1)
+        return DAG.getSetCC(VT, N0, DAG.getConstant(MaxVal, N0.getValueType()),
+                        ISD::SETEQ);
+
+      // If we have "setcc X, C0", check to see if we can shrink the immediate
+      // by changing cc.
+
+      // SETUGT X, SINTMAX  -> SETLT X, 0
+      if (Cond == ISD::SETUGT && OperandBitSize != 1 &&
+          C1 == (~0ULL >> (65-OperandBitSize)))
+        return DAG.getSetCC(VT, N0, DAG.getConstant(0, N1.getValueType()),
+                            ISD::SETLT);
+
+      // FIXME: Implement the rest of these.
+
+      // Fold bit comparisons when we can.
+      if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
+          VT == N0.getValueType() && N0.getOpcode() == ISD::AND)
+        if (ConstantSDNode *AndRHS =
+                    dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
+          if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0  -->  (X & 8) >> 3
+            // Perform the xform if the AND RHS is a single bit.
+            if (isPowerOf2_64(AndRHS->getValue())) {
+              return DAG.getNode(ISD::SRL, VT, N0,
+                             DAG.getConstant(Log2_64(AndRHS->getValue()),
+                                             getShiftAmountTy()));
+            }
+          } else if (Cond == ISD::SETEQ && C1 == AndRHS->getValue()) {
+            // (X & 8) == 8  -->  (X & 8) >> 3
+            // Perform the xform if C1 is a single bit.
+            if (isPowerOf2_64(C1)) {
+              return DAG.getNode(ISD::SRL, VT, N0,
+                          DAG.getConstant(Log2_64(C1), getShiftAmountTy()));
+            }
+          }
+        }
+    }
+  } else if (isa<ConstantSDNode>(N0.Val)) {
+      // Ensure that the constant occurs on the RHS.
+    return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond));
+  }
+
+  if (isa<ConstantFPSDNode>(N0.Val)) {
+    // Constant fold or commute setcc.
+    SDOperand O = DAG.FoldSetCC(VT, N0, N1, Cond);    
+    if (O.Val) return O;
+  }
+
+  if (N0 == N1) {
+    // We can always fold X == X for integer setcc's.
+    if (MVT::isInteger(N0.getValueType()))
+      return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT);
+    unsigned UOF = ISD::getUnorderedFlavor(Cond);
+    if (UOF == 2)   // FP operators that are undefined on NaNs.
+      return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT);
+    if (UOF == unsigned(ISD::isTrueWhenEqual(Cond)))
+      return DAG.getConstant(UOF, VT);
+    // Otherwise, we can't fold it.  However, we can simplify it to SETUO/SETO
+    // if it is not already.
+    ISD::CondCode NewCond = UOF == 0 ? ISD::SETO : ISD::SETUO;
+    if (NewCond != Cond)
+      return DAG.getSetCC(VT, N0, N1, NewCond);
+  }
+
+  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
+      MVT::isInteger(N0.getValueType())) {
+    if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB ||
+        N0.getOpcode() == ISD::XOR) {
+      // Simplify (X+Y) == (X+Z) -->  Y == Z
+      if (N0.getOpcode() == N1.getOpcode()) {
+        if (N0.getOperand(0) == N1.getOperand(0))
+          return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond);
+        if (N0.getOperand(1) == N1.getOperand(1))
+          return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(0), Cond);
+        if (DAG.isCommutativeBinOp(N0.getOpcode())) {
+          // If X op Y == Y op X, try other combinations.
+          if (N0.getOperand(0) == N1.getOperand(1))
+            return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(0), Cond);
+          if (N0.getOperand(1) == N1.getOperand(0))
+            return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(1), Cond);
+        }
+      }
+      
+      if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(N1)) {
+        if (ConstantSDNode *LHSR = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
+          // Turn (X+C1) == C2 --> X == C2-C1
+          if (N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse()) {
+            return DAG.getSetCC(VT, N0.getOperand(0),
+                              DAG.getConstant(RHSC->getValue()-LHSR->getValue(),
+                                N0.getValueType()), Cond);
+          }
+          
+          // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0.
+          if (N0.getOpcode() == ISD::XOR)
+            // If we know that all of the inverted bits are zero, don't bother
+            // performing the inversion.
+            if (MaskedValueIsZero(N0.getOperand(0), ~LHSR->getValue()))
+              return DAG.getSetCC(VT, N0.getOperand(0),
+                              DAG.getConstant(LHSR->getValue()^RHSC->getValue(),
+                                              N0.getValueType()), Cond);
+        }
+        
+        // Turn (C1-X) == C2 --> X == C1-C2
+        if (ConstantSDNode *SUBC = dyn_cast<ConstantSDNode>(N0.getOperand(0))) {
+          if (N0.getOpcode() == ISD::SUB && N0.Val->hasOneUse()) {
+            return DAG.getSetCC(VT, N0.getOperand(1),
+                             DAG.getConstant(SUBC->getValue()-RHSC->getValue(),
+                                             N0.getValueType()), Cond);
+          }
+        }          
+      }
+
+      // Simplify (X+Z) == X -->  Z == 0
+      if (N0.getOperand(0) == N1)
+        return DAG.getSetCC(VT, N0.getOperand(1),
+                        DAG.getConstant(0, N0.getValueType()), Cond);
+      if (N0.getOperand(1) == N1) {
+        if (DAG.isCommutativeBinOp(N0.getOpcode()))
+          return DAG.getSetCC(VT, N0.getOperand(0),
+                          DAG.getConstant(0, N0.getValueType()), Cond);
+        else {
+          assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!");
+          // (Z-X) == X  --> Z == X<<1
+          SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(),
+                                     N1, 
+                                     DAG.getConstant(1, getShiftAmountTy()));
+          if (!DCI.isCalledByLegalizer())
+            DCI.AddToWorklist(SH.Val);
+          return DAG.getSetCC(VT, N0.getOperand(0), SH, Cond);
+        }
+      }
+    }
+
+    if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
+        N1.getOpcode() == ISD::XOR) {
+      // Simplify  X == (X+Z) -->  Z == 0
+      if (N1.getOperand(0) == N0) {
+        return DAG.getSetCC(VT, N1.getOperand(1),
+                        DAG.getConstant(0, N1.getValueType()), Cond);
+      } else if (N1.getOperand(1) == N0) {
+        if (DAG.isCommutativeBinOp(N1.getOpcode())) {
+          return DAG.getSetCC(VT, N1.getOperand(0),
+                          DAG.getConstant(0, N1.getValueType()), Cond);
+        } else {
+          assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
+          // X == (Z-X)  --> X<<1 == Z
+          SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), N0, 
+                                     DAG.getConstant(1, getShiftAmountTy()));
+          if (!DCI.isCalledByLegalizer())
+            DCI.AddToWorklist(SH.Val);
+          return DAG.getSetCC(VT, SH, N1.getOperand(0), Cond);
+        }
+      }
+    }
+  }
+
+  // Fold away ALL boolean setcc's.
+  SDOperand Temp;
+  if (N0.getValueType() == MVT::i1 && foldBooleans) {
+    switch (Cond) {
+    default: assert(0 && "Unknown integer setcc!");
+    case ISD::SETEQ:  // X == Y  -> (X^Y)^1
+      Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, N1);
+      N0 = DAG.getNode(ISD::XOR, MVT::i1, Temp, DAG.getConstant(1, MVT::i1));
+      if (!DCI.isCalledByLegalizer())
+        DCI.AddToWorklist(Temp.Val);
+      break;
+    case ISD::SETNE:  // X != Y   -->  (X^Y)
+      N0 = DAG.getNode(ISD::XOR, MVT::i1, N0, N1);
+      break;
+    case ISD::SETGT:  // X >s Y   -->  X == 0 & Y == 1  -->  X^1 & Y
+    case ISD::SETULT: // X <u Y   -->  X == 0 & Y == 1  -->  X^1 & Y
+      Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1));
+      N0 = DAG.getNode(ISD::AND, MVT::i1, N1, Temp);
+      if (!DCI.isCalledByLegalizer())
+        DCI.AddToWorklist(Temp.Val);
+      break;
+    case ISD::SETLT:  // X <s Y   --> X == 1 & Y == 0  -->  Y^1 & X
+    case ISD::SETUGT: // X >u Y   --> X == 1 & Y == 0  -->  Y^1 & X
+      Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1));
+      N0 = DAG.getNode(ISD::AND, MVT::i1, N0, Temp);
+      if (!DCI.isCalledByLegalizer())
+        DCI.AddToWorklist(Temp.Val);
+      break;
+    case ISD::SETULE: // X <=u Y  --> X == 0 | Y == 1  -->  X^1 | Y
+    case ISD::SETGE:  // X >=s Y  --> X == 0 | Y == 1  -->  X^1 | Y
+      Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1));
+      N0 = DAG.getNode(ISD::OR, MVT::i1, N1, Temp);
+      if (!DCI.isCalledByLegalizer())
+        DCI.AddToWorklist(Temp.Val);
+      break;
+    case ISD::SETUGE: // X >=u Y  --> X == 1 | Y == 0  -->  Y^1 | X
+    case ISD::SETLE:  // X <=s Y  --> X == 1 | Y == 0  -->  Y^1 | X
+      Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1));
+      N0 = DAG.getNode(ISD::OR, MVT::i1, N0, Temp);
+      break;
+    }
+    if (VT != MVT::i1) {
+      if (!DCI.isCalledByLegalizer())
+        DCI.AddToWorklist(N0.Val);
+      // FIXME: If running after legalize, we probably can't do this.
+      N0 = DAG.getNode(ISD::ZERO_EXTEND, VT, N0);
+    }
+    return N0;
+  }
+
+  // Could not fold it.
+  return SDOperand();
+}
+
 SDOperand TargetLowering::
 PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const {
   // Default implementation: no optimization.