From fa1eb27b76ab1e0f78574bf52a432c84a4c1a520 Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Thu, 8 Feb 2007 22:13:59 +0000 Subject: [PATCH] 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 --- include/llvm/Target/TargetLowering.h | 12 +- lib/CodeGen/SelectionDAG/DAGCombiner.cpp | 404 +------------------ lib/CodeGen/SelectionDAG/TargetLowering.cpp | 421 ++++++++++++++++++++ 3 files changed, 436 insertions(+), 401 deletions(-) diff --git a/include/llvm/Target/TargetLowering.h b/include/llvm/Target/TargetLowering.h index bbd888d8d31..7bdf01f9e40 100644 --- a/include/llvm/Target/TargetLowering.h +++ b/include/llvm/Target/TargetLowering.h @@ -513,13 +513,15 @@ public: struct DAGCombinerInfo { void *DC; // The DAG Combiner object. bool BeforeLegalize; + bool CalledByLegalizer; public: SelectionDAG &DAG; - DAGCombinerInfo(SelectionDAG &dag, bool bl, void *dc) - : DC(dc), BeforeLegalize(bl), DAG(dag) {} + DAGCombinerInfo(SelectionDAG &dag, bool bl, bool cl, void *dc) + : DC(dc), BeforeLegalize(bl), CalledByLegalizer(cl), DAG(dag) {} bool isBeforeLegalize() const { return BeforeLegalize; } + bool isCalledByLegalizer() const { return CalledByLegalizer; } void AddToWorklist(SDNode *N); SDOperand CombineTo(SDNode *N, const std::vector &To); @@ -527,6 +529,12 @@ public: SDOperand CombineTo(SDNode *N, SDOperand Res0, SDOperand Res1); }; + /// 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 SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1, + ISD::CondCode Cond, bool foldBooleans, + DAGCombinerInfo &DCI) const; + /// PerformDAGCombine - This method will be invoked for all target nodes and /// for any target-independent nodes that the target has registered with /// invoke it for. diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp index fa546d2e2d2..db02b09f795 100644 --- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -423,7 +423,7 @@ void DAGCombiner::Run(bool RunningAfterLegalize) { /// DagCombineInfo - Expose the DAG combiner to the target combiner impls. TargetLowering::DAGCombinerInfo - DagCombineInfo(DAG, !RunningAfterLegalize, this); + DagCombineInfo(DAG, !RunningAfterLegalize, false, this); // while the worklist isn't empty, inspect the node on the end of it and // try and combine it. @@ -3944,407 +3944,13 @@ SDOperand DAGCombiner::SimplifySelectCC(SDOperand N0, SDOperand N1, return SDOperand(); } +/// SimplifySetCC - This is a stub for TargetLowering::SimplifySetCC. SDOperand DAGCombiner::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1, ISD::CondCode Cond, bool foldBooleans) { - // 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(N1.Val)) { - uint64_t C1 = N1C->getValue(); - if (isa(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(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(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)); - } - 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(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(N0.getOperand(1)) && - cast(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 (TLI.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 - - // 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(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()), - TLI.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),TLI.getShiftAmountTy())); - } - } - } - } - } else if (isa(N0.Val)) { - // Ensure that the constant occurs on the RHS. - return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond)); - } - - if (isa(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(N1)) { - if (ConstantSDNode *LHSR = dyn_cast(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 (TLI.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(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,TLI.getShiftAmountTy())); - 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,TLI.getShiftAmountTy())); - 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)); - 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 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); - AddToWorkList(Temp.Val); - break; - case ISD::SETLT: // X 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); - 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); - 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) { - 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(); + TargetLowering::DAGCombinerInfo + DagCombineInfo(DAG, !AfterLegalize, false, this); + return TLI.SimplifySetCC(VT, N0, N1, Cond, foldBooleans, DagCombineInfo); } /// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant, diff --git a/lib/CodeGen/SelectionDAG/TargetLowering.cpp b/lib/CodeGen/SelectionDAG/TargetLowering.cpp index 2ebce86a036..d43e6a63575 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(N1.Val)) { + uint64_t C1 = N1C->getValue(); + if (isa(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(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(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(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(N0.getOperand(1)) && + cast(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(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(N0.Val)) { + // Ensure that the constant occurs on the RHS. + return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond)); + } + + if (isa(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(N1)) { + if (ConstantSDNode *LHSR = dyn_cast(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(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 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 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. -- 2.34.1