diff options
| -rw-r--r-- | include/llvm/CodeGen/SelectionDAG.h | 23 | ||||
| -rw-r--r-- | include/llvm/Target/TargetLowering.h | 22 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/DAGCombiner.cpp | 46 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/LegalizeDAG.cpp | 6 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 546 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 4 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/TargetLowering.cpp | 561 | ||||
| -rw-r--r-- | lib/Target/ARM/ARMISelLowering.cpp | 16 | ||||
| -rw-r--r-- | lib/Target/ARM/ARMISelLowering.h | 1 | ||||
| -rw-r--r-- | lib/Target/Alpha/AlphaISelDAGToDAG.cpp | 2 | ||||
| -rw-r--r-- | lib/Target/PowerPC/PPCISelDAGToDAG.cpp | 4 | ||||
| -rw-r--r-- | lib/Target/PowerPC/PPCISelLowering.cpp | 9 | ||||
| -rw-r--r-- | lib/Target/PowerPC/PPCISelLowering.h | 1 | ||||
| -rw-r--r-- | lib/Target/Sparc/SparcISelDAGToDAG.cpp | 8 | ||||
| -rw-r--r-- | lib/Target/X86/X86ISelDAGToDAG.cpp | 2 | ||||
| -rw-r--r-- | lib/Target/X86/X86ISelLowering.cpp | 1 | ||||
| -rw-r--r-- | lib/Target/X86/X86ISelLowering.h | 1 |
17 files changed, 633 insertions, 620 deletions
diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h index 9d8024b..56cb17d 100644 --- a/include/llvm/CodeGen/SelectionDAG.h +++ b/include/llvm/CodeGen/SelectionDAG.h @@ -465,6 +465,29 @@ public: SDOperand FoldSetCC(MVT::ValueType VT, SDOperand N1, SDOperand N2, ISD::CondCode Cond); + /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We + /// use this predicate to simplify operations downstream. Op and Mask are + /// known to be the same type. + bool MaskedValueIsZero(SDOperand Op, uint64_t Mask, unsigned Depth = 0) + const; + + /// ComputeMaskedBits - Determine which of the bits specified in Mask are + /// known to be either zero or one and return them in the KnownZero/KnownOne + /// bitsets. This code only analyzes bits in Mask, in order to short-circuit + /// processing. Targets can implement the computeMaskedBitsForTargetNode + /// method in the TargetLowering class to allow target nodes to be understood. + void ComputeMaskedBits(SDOperand Op, uint64_t Mask, uint64_t &KnownZero, + uint64_t &KnownOne, unsigned Depth = 0) const; + + /// ComputeNumSignBits - Return the number of times the sign bit of the + /// register is replicated into the other bits. We know that at least 1 bit + /// is always equal to the sign bit (itself), but other cases can give us + /// information. For example, immediately after an "SRA X, 2", we know that + /// the top 3 bits are all equal to each other, so we return 3. Targets can + /// implement the ComputeNumSignBitsForTarget method in the TargetLowering + /// class to allow target nodes to be understood. + unsigned ComputeNumSignBits(SDOperand Op, unsigned Depth = 0) const; + private: void RemoveNodeFromCSEMaps(SDNode *N); SDNode *AddNonLeafNodeToCSEMaps(SDNode *N); diff --git a/include/llvm/Target/TargetLowering.h b/include/llvm/Target/TargetLowering.h index de51945..5b98667 100644 --- a/include/llvm/Target/TargetLowering.h +++ b/include/llvm/Target/TargetLowering.h @@ -494,20 +494,6 @@ public: bool ShrinkDemandedConstant(SDOperand Op, uint64_t Demanded); }; - /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We - /// use this predicate to simplify operations downstream. Op and Mask are - /// known to be the same type. - bool MaskedValueIsZero(SDOperand Op, uint64_t Mask, unsigned Depth = 0) - const; - - /// ComputeMaskedBits - Determine which of the bits specified in Mask are - /// known to be either zero or one and return them in the KnownZero/KnownOne - /// bitsets. This code only analyzes bits in Mask, in order to short-circuit - /// processing. Targets can implement the computeMaskedBitsForTargetNode - /// method, to allow target nodes to be understood. - void ComputeMaskedBits(SDOperand Op, uint64_t Mask, uint64_t &KnownZero, - uint64_t &KnownOne, unsigned Depth = 0) const; - /// SimplifyDemandedBits - Look at Op. At this point, we know that only the /// DemandedMask bits of the result of Op are ever used downstream. If we can /// use this information to simplify Op, create a new simplified DAG node and @@ -527,15 +513,9 @@ public: uint64_t Mask, uint64_t &KnownZero, uint64_t &KnownOne, + const SelectionDAG &DAG, unsigned Depth = 0) const; - /// ComputeNumSignBits - Return the number of times the sign bit of the - /// register is replicated into the other bits. We know that at least 1 bit - /// is always equal to the sign bit (itself), but other cases can give us - /// information. For example, immediately after an "SRA X, 2", we know that - /// the top 3 bits are all equal to each other, so we return 3. - unsigned ComputeNumSignBits(SDOperand Op, unsigned Depth = 0) const; - /// ComputeNumSignBitsForTargetNode - This method can be implemented by /// targets that want to expose additional information about sign bits to the /// DAG Combiner. diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp index cfc52d9..32ab5d3 100644 --- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -896,9 +896,9 @@ SDOperand DAGCombiner::visitADD(SDNode *N) { uint64_t LHSZero, LHSOne; uint64_t RHSZero, RHSOne; uint64_t Mask = MVT::getIntVTBitMask(VT); - TLI.ComputeMaskedBits(N0, Mask, LHSZero, LHSOne); + DAG.ComputeMaskedBits(N0, Mask, LHSZero, LHSOne); if (LHSZero) { - TLI.ComputeMaskedBits(N1, Mask, RHSZero, RHSOne); + DAG.ComputeMaskedBits(N1, Mask, RHSZero, RHSOne); // If all possibly-set bits on the LHS are clear on the RHS, return an OR. // If all possibly-set bits on the RHS are clear on the LHS, return an OR. @@ -957,9 +957,9 @@ SDOperand DAGCombiner::visitADDC(SDNode *N) { uint64_t LHSZero, LHSOne; uint64_t RHSZero, RHSOne; uint64_t Mask = MVT::getIntVTBitMask(VT); - TLI.ComputeMaskedBits(N0, Mask, LHSZero, LHSOne); + DAG.ComputeMaskedBits(N0, Mask, LHSZero, LHSOne); if (LHSZero) { - TLI.ComputeMaskedBits(N1, Mask, RHSZero, RHSOne); + DAG.ComputeMaskedBits(N1, Mask, RHSZero, RHSOne); // If all possibly-set bits on the LHS are clear on the RHS, return an OR. // If all possibly-set bits on the RHS are clear on the LHS, return an OR. @@ -1120,8 +1120,8 @@ SDOperand DAGCombiner::visitSDIV(SDNode *N) { // If we know the sign bits of both operands are zero, strength reduce to a // udiv instead. Handles (X&15) /s 4 -> X&15 >> 2 uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1); - if (TLI.MaskedValueIsZero(N1, SignBit) && - TLI.MaskedValueIsZero(N0, SignBit)) + if (DAG.MaskedValueIsZero(N1, SignBit) && + DAG.MaskedValueIsZero(N0, SignBit)) return DAG.getNode(ISD::UDIV, N1.getValueType(), N0, N1); // fold (sdiv X, pow2) -> simple ops after legalize if (N1C && N1C->getValue() && !TLI.isIntDivCheap() && @@ -1214,8 +1214,8 @@ SDOperand DAGCombiner::visitSREM(SDNode *N) { // If we know the sign bits of both operands are zero, strength reduce to a // urem instead. Handles (X & 0x0FFFFFFF) %s 16 -> X&15 uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1); - if (TLI.MaskedValueIsZero(N1, SignBit) && - TLI.MaskedValueIsZero(N0, SignBit)) + if (DAG.MaskedValueIsZero(N1, SignBit) && + DAG.MaskedValueIsZero(N0, SignBit)) return DAG.getNode(ISD::UREM, VT, N0, N1); // Unconditionally lower X%C -> X-X/C*C. This allows the X/C logic to hack on @@ -1357,7 +1357,7 @@ SDOperand DAGCombiner::visitAND(SDNode *N) { if (N1C && N1C->isAllOnesValue()) return N0; // if (and x, c) is known to be zero, return 0 - if (N1C && TLI.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT))) + if (N1C && DAG.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT))) return DAG.getConstant(0, VT); // reassociate and SDOperand RAND = ReassociateOps(ISD::AND, N0, N1); @@ -1371,7 +1371,7 @@ SDOperand DAGCombiner::visitAND(SDNode *N) { // fold (and (any_ext V), c) -> (zero_ext V) if 'and' only clears top bits. if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) { unsigned InMask = MVT::getIntVTBitMask(N0.getOperand(0).getValueType()); - if (TLI.MaskedValueIsZero(N0.getOperand(0), + if (DAG.MaskedValueIsZero(N0.getOperand(0), ~N1C->getValue() & InMask)) { SDOperand Zext = DAG.getNode(ISD::ZERO_EXTEND, N0.getValueType(), N0.getOperand(0)); @@ -1442,7 +1442,7 @@ SDOperand DAGCombiner::visitAND(SDNode *N) { MVT::ValueType EVT = LN0->getLoadedVT(); // If we zero all the possible extended bits, then we can turn this into // a zextload if we are running before legalize or the operation is legal. - if (TLI.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) && + if (DAG.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) && (!AfterLegalize || TLI.isLoadXLegal(ISD::ZEXTLOAD, EVT))) { SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(), LN0->getBasePtr(), LN0->getSrcValue(), @@ -1461,7 +1461,7 @@ SDOperand DAGCombiner::visitAND(SDNode *N) { MVT::ValueType EVT = LN0->getLoadedVT(); // If we zero all the possible extended bits, then we can turn this into // a zextload if we are running before legalize or the operation is legal. - if (TLI.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) && + if (DAG.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) && (!AfterLegalize || TLI.isLoadXLegal(ISD::ZEXTLOAD, EVT))) { SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(), LN0->getBasePtr(), LN0->getSrcValue(), @@ -1542,7 +1542,7 @@ SDOperand DAGCombiner::visitOR(SDNode *N) { return N1; // fold (or x, c) -> c iff (x & ~c) == 0 if (N1C && - TLI.MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)))) + DAG.MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)))) return N1; // reassociate or SDOperand ROR = ReassociateOps(ISD::OR, N0, N1); @@ -1611,8 +1611,8 @@ SDOperand DAGCombiner::visitOR(SDNode *N) { uint64_t LHSMask = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); uint64_t RHSMask = cast<ConstantSDNode>(N1.getOperand(1))->getValue(); - if (TLI.MaskedValueIsZero(N0.getOperand(0), RHSMask&~LHSMask) && - TLI.MaskedValueIsZero(N1.getOperand(0), LHSMask&~RHSMask)) { + if (DAG.MaskedValueIsZero(N0.getOperand(0), RHSMask&~LHSMask) && + DAG.MaskedValueIsZero(N1.getOperand(0), LHSMask&~RHSMask)) { SDOperand X =DAG.getNode(ISD::OR, VT, N0.getOperand(0), N1.getOperand(0)); return DAG.getNode(ISD::AND, VT, X, DAG.getConstant(LHSMask|RHSMask, VT)); } @@ -1914,7 +1914,7 @@ SDOperand DAGCombiner::visitSHL(SDNode *N) { if (N1C && N1C->isNullValue()) return N0; // if (shl x, c) is known to be zero, return 0 - if (TLI.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT))) + if (DAG.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT))) return DAG.getConstant(0, VT); if (N1C && SimplifyDemandedBits(SDOperand(N, 0))) return SDOperand(N, 0); @@ -2005,7 +2005,7 @@ SDOperand DAGCombiner::visitSRA(SDNode *N) { // If the sign bit is known to be zero, switch this to a SRL. - if (TLI.MaskedValueIsZero(N0, MVT::getIntVTSignBit(VT))) + if (DAG.MaskedValueIsZero(N0, MVT::getIntVTSignBit(VT))) return DAG.getNode(ISD::SRL, VT, N0, N1); return SDOperand(); } @@ -2031,7 +2031,7 @@ SDOperand DAGCombiner::visitSRL(SDNode *N) { if (N1C && N1C->isNullValue()) return N0; // if (srl x, c) is known to be zero, return 0 - if (N1C && TLI.MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits))) + if (N1C && DAG.MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits))) return DAG.getConstant(0, VT); // fold (srl (srl x, c1), c2) -> 0 or (srl x, c1+c2) @@ -2068,7 +2068,7 @@ SDOperand DAGCombiner::visitSRL(SDNode *N) { if (N1C && N0.getOpcode() == ISD::CTLZ && N1C->getValue() == Log2_32(MVT::getSizeInBits(VT))) { uint64_t KnownZero, KnownOne, Mask = MVT::getIntVTBitMask(VT); - TLI.ComputeMaskedBits(N0.getOperand(0), Mask, KnownZero, KnownOne); + DAG.ComputeMaskedBits(N0.getOperand(0), Mask, KnownZero, KnownOne); // If any of the input bits are KnownOne, then the input couldn't be all // zeros, thus the result of the srl will always be zero. @@ -2270,7 +2270,7 @@ SDOperand DAGCombiner::visitSIGN_EXTEND(SDNode *N) { unsigned OpBits = MVT::getSizeInBits(Op.getValueType()); unsigned MidBits = MVT::getSizeInBits(N0.getValueType()); unsigned DestBits = MVT::getSizeInBits(VT); - unsigned NumSignBits = TLI.ComputeNumSignBits(Op); + unsigned NumSignBits = DAG.ComputeNumSignBits(Op); if (OpBits == DestBits) { // Op is i32, Mid is i8, and Dest is i32. If Op has more than 24 sign @@ -2634,7 +2634,7 @@ SDOperand DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) { return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0, N1); // If the input is already sign extended, just drop the extension. - if (TLI.ComputeNumSignBits(N0) >= MVT::getSizeInBits(VT)-EVTBits+1) + if (DAG.ComputeNumSignBits(N0) >= MVT::getSizeInBits(VT)-EVTBits+1) return N0; // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt2 @@ -2644,7 +2644,7 @@ SDOperand DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) { } // fold (sext_in_reg x) -> (zext_in_reg x) if the sign bit is known zero. - if (TLI.MaskedValueIsZero(N0, 1ULL << (EVTBits-1))) + if (DAG.MaskedValueIsZero(N0, 1ULL << (EVTBits-1))) return DAG.getZeroExtendInReg(N0, EVT); // fold operands of sext_in_reg based on knowledge that the top bits are not @@ -2666,7 +2666,7 @@ SDOperand DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) { if (ShAmt->getValue()+EVTBits <= MVT::getSizeInBits(VT)) { // We can turn this into an SRA iff the input to the SRL is already sign // extended enough. - unsigned InSignBits = TLI.ComputeNumSignBits(N0.getOperand(0)); + unsigned InSignBits = DAG.ComputeNumSignBits(N0.getOperand(0)); if (MVT::getSizeInBits(VT)-(ShAmt->getValue()+EVTBits) < InSignBits) return DAG.getNode(ISD::SRA, VT, N0.getOperand(0), N0.getOperand(1)); } diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp index 0584d6e..5735744 100644 --- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp +++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp @@ -1449,7 +1449,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { // The top bits of the promoted condition are not necessarily zero, ensure // that the value is properly zero extended. - if (!TLI.MaskedValueIsZero(Tmp2, + if (!DAG.MaskedValueIsZero(Tmp2, MVT::getIntVTBitMask(Tmp2.getValueType())^1)) Tmp2 = DAG.getZeroExtendInReg(Tmp2, MVT::i1); break; @@ -2041,7 +2041,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { case Promote: Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition. // Make sure the condition is either zero or one. - if (!TLI.MaskedValueIsZero(Tmp1, + if (!DAG.MaskedValueIsZero(Tmp1, MVT::getIntVTBitMask(Tmp1.getValueType())^1)) Tmp1 = DAG.getZeroExtendInReg(Tmp1, MVT::i1); break; @@ -4209,7 +4209,7 @@ bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt, // Okay, the shift amount isn't constant. However, if we can tell that it is // >= 32 or < 32, we can still simplify it, without knowing the actual value. uint64_t Mask = NVTBits, KnownZero, KnownOne; - TLI.ComputeMaskedBits(Amt, Mask, KnownZero, KnownOne); + DAG.ComputeMaskedBits(Amt, Mask, KnownZero, KnownOne); // If we know that the high bit of the shift amount is one, then we can do // this as a couple of simple shifts. diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp index 0ac77f9..d708233 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -936,6 +936,552 @@ SDOperand SelectionDAG::FoldSetCC(MVT::ValueType VT, SDOperand N1, return SDOperand(); } +/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use +/// this predicate to simplify operations downstream. Mask is known to be zero +/// for bits that V cannot have. +bool SelectionDAG::MaskedValueIsZero(SDOperand Op, uint64_t Mask, + unsigned Depth) const { + // The masks are not wide enough to represent this type! Should use APInt. + if (Op.getValueType() == MVT::i128) + return false; + + uint64_t KnownZero, KnownOne; + ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth); + assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); + return (KnownZero & Mask) == Mask; +} + +/// ComputeMaskedBits - Determine which of the bits specified in Mask are +/// known to be either zero or one and return them in the KnownZero/KnownOne +/// bitsets. This code only analyzes bits in Mask, in order to short-circuit +/// processing. +void SelectionDAG::ComputeMaskedBits(SDOperand Op, uint64_t Mask, + uint64_t &KnownZero, uint64_t &KnownOne, + unsigned Depth) const { + KnownZero = KnownOne = 0; // Don't know anything. + if (Depth == 6 || Mask == 0) + return; // Limit search depth. + + // The masks are not wide enough to represent this type! Should use APInt. + if (Op.getValueType() == MVT::i128) + return; + + uint64_t KnownZero2, KnownOne2; + + switch (Op.getOpcode()) { + case ISD::Constant: + // We know all of the bits for a constant! + KnownOne = cast<ConstantSDNode>(Op)->getValue() & Mask; + KnownZero = ~KnownOne & Mask; + return; + case ISD::AND: + // If either the LHS or the RHS are Zero, the result is zero. + ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); + Mask &= ~KnownZero; + ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); + assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); + assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); + + // Output known-1 bits are only known if set in both the LHS & RHS. + KnownOne &= KnownOne2; + // Output known-0 are known to be clear if zero in either the LHS | RHS. + KnownZero |= KnownZero2; + return; + case ISD::OR: + ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); + Mask &= ~KnownOne; + ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); + assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); + assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); + + // Output known-0 bits are only known if clear in both the LHS & RHS. + KnownZero &= KnownZero2; + // Output known-1 are known to be set if set in either the LHS | RHS. + KnownOne |= KnownOne2; + return; + case ISD::XOR: { + ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); + ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); + assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); + assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); + + // Output known-0 bits are known if clear or set in both the LHS & RHS. + uint64_t KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); + // Output known-1 are known to be set if set in only one of the LHS, RHS. + KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); + KnownZero = KnownZeroOut; + return; + } + case ISD::SELECT: + ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1); + ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1); + assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); + assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); + + // Only known if known in both the LHS and RHS. + KnownOne &= KnownOne2; + KnownZero &= KnownZero2; + return; + case ISD::SELECT_CC: + ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1); + ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1); + assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); + assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); + + // Only known if known in both the LHS and RHS. + KnownOne &= KnownOne2; + KnownZero &= KnownZero2; + return; + case ISD::SETCC: + // If we know the result of a setcc has the top bits zero, use this info. + if (TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) + KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL); + return; + case ISD::SHL: + // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 + if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { + ComputeMaskedBits(Op.getOperand(0), Mask >> SA->getValue(), + KnownZero, KnownOne, Depth+1); + assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); + KnownZero <<= SA->getValue(); + KnownOne <<= SA->getValue(); + KnownZero |= (1ULL << SA->getValue())-1; // low bits known zero. + } + return; + case ISD::SRL: + // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 + if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { + MVT::ValueType VT = Op.getValueType(); + unsigned ShAmt = SA->getValue(); + + uint64_t TypeMask = MVT::getIntVTBitMask(VT); + ComputeMaskedBits(Op.getOperand(0), (Mask << ShAmt) & TypeMask, + KnownZero, KnownOne, Depth+1); + assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); + KnownZero &= TypeMask; + KnownOne &= TypeMask; + KnownZero >>= ShAmt; + KnownOne >>= ShAmt; + + uint64_t HighBits = (1ULL << ShAmt)-1; + HighBits <<= MVT::getSizeInBits(VT)-ShAmt; + KnownZero |= HighBits; // High bits known zero. + } + return; + case ISD::SRA: + if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { + MVT::ValueType VT = Op.getValueType(); + unsigned ShAmt = SA->getValue(); + + // Compute the new bits that are at the top now. + uint64_t TypeMask = MVT::getIntVTBitMask(VT); + + uint64_t InDemandedMask = (Mask << ShAmt) & TypeMask; + // If any of the demanded bits are produced by the sign extension, we also + // demand the input sign bit. + uint64_t HighBits = (1ULL << ShAmt)-1; + HighBits <<= MVT::getSizeInBits(VT) - ShAmt; + if (HighBits & Mask) + InDemandedMask |= MVT::getIntVTSignBit(VT); + + ComputeMaskedBits(Op.getOperand(0), InDemandedMask, KnownZero, KnownOne, + Depth+1); + assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); + KnownZero &= TypeMask; + KnownOne &= TypeMask; + KnownZero >>= ShAmt; + KnownOne >>= ShAmt; + + // Handle the sign bits. + uint64_t SignBit = MVT::getIntVTSignBit(VT); + SignBit >>= ShAmt; // Adjust to where it is now in the mask. + + if (KnownZero & SignBit) { + KnownZero |= HighBits; // New bits are known zero. + } else if (KnownOne & SignBit) { + KnownOne |= HighBits; // New bits are known one. + } + } + return; + case ISD::SIGN_EXTEND_INREG: { + MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT(); + + // Sign extension. Compute the demanded bits in the result that are not + // present in the input. + uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & Mask; + + uint64_t InSignBit = MVT::getIntVTSignBit(EVT); + int64_t InputDemandedBits = Mask & MVT::getIntVTBitMask(EVT); + + // If the sign extended bits are demanded, we know that the sign + // bit is demanded. + if (NewBits) + InputDemandedBits |= InSignBit; + + ComputeMaskedBits(Op.getOperand(0), InputDemandedBits, + KnownZero, KnownOne, Depth+1); + assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); + + // If the sign bit of the input is known set or clear, then we know the + // top bits of the result. + if (KnownZero & InSignBit) { // Input sign bit known clear + KnownZero |= NewBits; + KnownOne &= ~NewBits; + } else if (KnownOne & InSignBit) { // Input sign bit known set + KnownOne |= NewBits; + KnownZero &= ~NewBits; + } else { // Input sign bit unknown + KnownZero &= ~NewBits; + KnownOne &= ~NewBits; + } + return; + } + case ISD::CTTZ: + case ISD::CTLZ: + case ISD::CTPOP: { + MVT::ValueType VT = Op.getValueType(); + unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1; + KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT); + KnownOne = 0; + return; + } + case ISD::LOAD: { + if (ISD::isZEXTLoad(Op.Val)) { + LoadSDNode *LD = cast<LoadSDNode>(Op); + MVT::ValueType VT = LD->getLoadedVT(); + KnownZero |= ~MVT::getIntVTBitMask(VT) & Mask; + } + return; + } + case ISD::ZERO_EXTEND: { + uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType()); + uint64_t NewBits = (~InMask) & Mask; + ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero, + KnownOne, Depth+1); + KnownZero |= NewBits & Mask; + KnownOne &= ~NewBits; + return; + } + case ISD::SIGN_EXTEND: { + MVT::ValueType InVT = Op.getOperand(0).getValueType(); + unsigned InBits = MVT::getSizeInBits(InVT); + uint64_t InMask = MVT::getIntVTBitMask(InVT); + uint64_t InSignBit = 1ULL << (InBits-1); + uint64_t NewBits = (~InMask) & Mask; + uint64_t InDemandedBits = Mask & InMask; + + // If any of the sign extended bits are demanded, we know that the sign + // bit is demanded. + if (NewBits & Mask) + InDemandedBits |= InSignBit; + + ComputeMaskedBits(Op.getOperand(0), InDemandedBits, KnownZero, + KnownOne, Depth+1); + // If the sign bit is known zero or one, the top bits match. + if (KnownZero & InSignBit) { + KnownZero |= NewBits; + KnownOne &= ~NewBits; + } else if (KnownOne & InSignBit) { + KnownOne |= NewBits; + KnownZero &= ~NewBits; + } else { // Otherwise, top bits aren't known. + KnownOne &= ~NewBits; + KnownZero &= ~NewBits; + } + return; + } + case ISD::ANY_EXTEND: { + MVT::ValueType VT = Op.getOperand(0).getValueType(); + ComputeMaskedBits(Op.getOperand(0), Mask & MVT::getIntVTBitMask(VT), + KnownZero, KnownOne, Depth+1); + return; + } + case ISD::TRUNCATE: { + ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); + assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); + uint64_t OutMask = MVT::getIntVTBitMask(Op.getValueType()); + KnownZero &= OutMask; + KnownOne &= OutMask; + break; + } + case ISD::AssertZext: { + MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT(); + uint64_t InMask = MVT::getIntVTBitMask(VT); + ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero, + KnownOne, Depth+1); + KnownZero |= (~InMask) & Mask; + return; + } + case ISD::ADD: { + // If either the LHS or the RHS are Zero, the result is zero. + ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); + ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); + assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); + assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); + + // Output known-0 bits are known if clear or set in both the low clear bits + // common to both LHS & RHS. For example, 8+(X<<3) is known to have the + // low 3 bits clear. + uint64_t KnownZeroOut = std::min(CountTrailingZeros_64(~KnownZero), + CountTrailingZeros_64(~KnownZero2)); + + KnownZero = (1ULL << KnownZeroOut) - 1; + KnownOne = 0; + return; + } + case ISD::SUB: { + ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)); + if (!CLHS) return; + + // We know that the top bits of C-X are clear if X contains less bits + // than C (i.e. no wrap-around can happen). For example, 20-X is + // positive if we can prove that X is >= 0 and < 16. + MVT::ValueType VT = CLHS->getValueType(0); + if ((CLHS->getValue() & MVT::getIntVTSignBit(VT)) == 0) { // sign bit clear + unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1); + uint64_t MaskV = (1ULL << (63-NLZ))-1; // NLZ can't be 64 with no sign bit + MaskV = ~MaskV & MVT::getIntVTBitMask(VT); + ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero, KnownOne, Depth+1); + + // If all of the MaskV bits are known to be zero, then we know the output + // top bits are zero, because we now know that the output is from [0-C]. + if ((KnownZero & MaskV) == MaskV) { + unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue()); + KnownZero = ~((1ULL << (64-NLZ2))-1) & Mask; // Top bits known zero. + KnownOne = 0; // No one bits known. + } else { + KnownZero = KnownOne = 0; // Otherwise, nothing known. + } + } + return; + } + default: + // Allow the target to implement this method for its nodes. + if (Op.getOpcode() >= ISD::BUILTIN_OP_END) { + case ISD::INTRINSIC_WO_CHAIN: + case ISD::INTRINSIC_W_CHAIN: + case ISD::INTRINSIC_VOID: + TLI.computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne, *this); + } + return; + } +} + +/// ComputeNumSignBits - Return the number of times the sign bit of the +/// register is replicated into the other bits. We know that at least 1 bit +/// is always equal to the sign bit (itself), but other cases can give us +/// information. For example, immediately after an "SRA X, 2", we know that +/// the top 3 bits are all equal to each other, so we return 3. +unsigned SelectionDAG::ComputeNumSignBits(SDOperand Op, unsigned Depth) const{ + MVT::ValueType VT = Op.getValueType(); + assert(MVT::isInteger(VT) && "Invalid VT!"); + unsigned VTBits = MVT::getSizeInBits(VT); + unsigned Tmp, Tmp2; + + if (Depth == 6) + return 1; // Limit search depth. + + switch (Op.getOpcode()) { + default: break; + case ISD::AssertSext: + Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); + return VTBits-Tmp+1; + case ISD::AssertZext: + Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); + return VTBits-Tmp; + + case ISD::Constant: { + uint64_t Val = cast<ConstantSDNode>(Op)->getValue(); + // If negative, invert the bits, then look at it. + if (Val & MVT::getIntVTSignBit(VT)) + Val = ~Val; + + // Shift the bits so they are the leading bits in the int64_t. + Val <<= 64-VTBits; + + // Return # leading zeros. We use 'min' here in case Val was zero before + // shifting. We don't want to return '64' as for an i32 "0". + return std::min(VTBits, CountLeadingZeros_64(Val)); + } + + case ISD::SIGN_EXTEND: + Tmp = VTBits-MVT::getSizeInBits(Op.getOperand(0).getValueType()); + return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp; + + case ISD::SIGN_EXTEND_INREG: + // Max of the input and what this extends. + Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); + Tmp = VTBits-Tmp+1; + + Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1); + return std::max(Tmp, Tmp2); + + case ISD::SRA: + Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); + // SRA X, C -> adds C sign bits. + if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { + Tmp += C->getValue(); + if (Tmp > VTBits) Tmp = VTBits; + } + return Tmp; + case ISD::SHL: + if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { + // shl destroys sign bits. + Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); + if (C->getValue() >= VTBits || // Bad shift. + C->getValue() >= Tmp) break; // Shifted all sign bits out. + return Tmp - C->getValue(); + } + break; + case ISD::AND: + case ISD::OR: + case ISD::XOR: // NOT is handled here. + // Logical binary ops preserve the number of sign bits. + Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); + if (Tmp == 1) return 1; // Early out. + Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); + return std::min(Tmp, Tmp2); + + case ISD::SELECT: + Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); + if (Tmp == 1) return 1; // Early out. + Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); + return std::min(Tmp, Tmp2); + + case ISD::SETCC: + // If setcc returns 0/-1, all bits are sign bits. + if (TLI.getSetCCResultContents() == + TargetLowering::ZeroOrNegativeOneSetCCResult) + return VTBits; + break; + case ISD::ROTL: + case ISD::ROTR: + if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { + unsigned RotAmt = C->getValue() & (VTBits-1); + + // Handle rotate right by N like a rotate left by 32-N. + if (Op.getOpcode() == ISD::ROTR) + RotAmt = (VTBits-RotAmt) & (VTBits-1); + + // If we aren't rotating out all of the known-in sign bits, return the + // number that are left. This handles rotl(sext(x), 1) for example. + Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); + if (Tmp > RotAmt+1) return Tmp-RotAmt; + } + break; + case ISD::ADD: + // Add can have at most one carry bit. Thus we know that the output + // is, at worst, one more bit than the inputs. + Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); + if (Tmp == 1) return 1; // Early out. + + // Special case decrementing a value (ADD X, -1): + if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) + if (CRHS->isAllOnesValue()) { + uint64_t KnownZero, KnownOne; + uint64_t Mask = MVT::getIntVTBitMask(VT); + ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); + + // If the input is known to be 0 or 1, the output is 0/-1, which is all + // sign bits set. + if ((KnownZero|1) == Mask) + return VTBits; + + // If we are subtracting one from a positive number, there is no carry + // out of the result. + if (KnownZero & MVT::getIntVTSignBit(VT)) + return Tmp; + } + + Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); + if (Tmp2 == 1) return 1; + return std::min(Tmp, Tmp2)-1; + break; + + case ISD::SUB: + Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); + if (Tmp2 == 1) return 1; + + // Handle NEG. + if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) + if (CLHS->getValue() == 0) { + uint64_t KnownZero, KnownOne; + uint64_t Mask = MVT::getIntVTBitMask(VT); + ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); + // If the input is known to be 0 or 1, the output is 0/-1, which is all + // sign bits set. + if ((KnownZero|1) == Mask) + return VTBits; + + // If the input is known to be positive (the sign bit is known clear), + // the output of the NEG has the same number of sign bits as the input. + if (KnownZero & MVT::getIntVTSignBit(VT)) + return Tmp2; + + // Otherwise, we treat this like a SUB. + } + + // Sub can have at most one carry bit. Thus we know that the output + // is, at worst, one more bit than the inputs. + Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); + if (Tmp == 1) return 1; // Early out. + return std::min(Tmp, Tmp2)-1; + break; + case ISD::TRUNCATE: + // FIXME: it's tricky to do anything useful for this, but it is an important + // case for targets like X86. + break; + } + + // Handle LOADX separately here. EXTLOAD case will fallthrough. + if (Op.getOpcode() == ISD::LOAD) { + LoadSDNode *LD = cast<LoadSDNode>(Op); + unsigned ExtType = LD->getExtensionType(); + switch (ExtType) { + default: break; + case ISD::SEXTLOAD: // '17' bits known + Tmp = MVT::getSizeInBits(LD->getLoadedVT()); + return VTBits-Tmp+1; + case ISD::ZEXTLOAD: // '16' bits known + Tmp = MVT::getSizeInBits(LD->getLoadedVT()); + return VTBits-Tmp; + } + } + + // Allow the target to implement this method for its nodes. + if (Op.getOpcode() >= ISD::BUILTIN_OP_END || + Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN || + Op.getOpcode() == ISD::INTRINSIC_W_CHAIN || + Op.getOpcode() == ISD::INTRINSIC_VOID) { + unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth); + if (NumBits > 1) return NumBits; + } + + // Finally, if we can prove that the top bits of the result are 0's or 1's, + // use this information. + uint64_t KnownZero, KnownOne; + uint64_t Mask = MVT::getIntVTBitMask(VT); + ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth); + + uint64_t SignBit = MVT::getIntVTSignBit(VT); + if (KnownZero & SignBit) { // SignBit is 0 + Mask = KnownZero; + } else if (KnownOne & SignBit) { // SignBit is 1; + Mask = KnownOne; + } else { + // Nothing known. + return 1; + } + + // Okay, we know that the sign bit in Mask is set. Use CLZ to determine + // the number of identical bits in the top of the input value. + Mask ^= ~0ULL; + Mask <<= 64-VTBits; + // Return # leading zeros. We use 'min' here in case Val was zero before + // shifting. We don't want to return '64' as for an i32 "0". + return std::min(VTBits, CountLeadingZeros_64(Mask)); +} + /// getNode - Gets or creates the specified node. /// diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index bc29cbc..cce0a32 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -5026,7 +5026,7 @@ bool SelectionDAGISel::CheckAndMask(SDOperand LHS, ConstantSDNode *RHS, // Otherwise, the DAG Combiner may have proven that the value coming in is // either already zero or is not demanded. Check for known zero input bits. uint64_t NeededMask = DesiredMask & ~ActualMask; - if (getTargetLowering().MaskedValueIsZero(LHS, NeededMask)) + if (CurDAG->MaskedValueIsZero(LHS, NeededMask)) return true; // TODO: check to see if missing bits are just not demanded. @@ -5057,7 +5057,7 @@ bool SelectionDAGISel::CheckOrMask(SDOperand LHS, ConstantSDNode *RHS, uint64_t NeededMask = DesiredMask & ~ActualMask; uint64_t KnownZero, KnownOne; - getTargetLowering().ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne); + CurDAG->ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne); // If all the missing bits in the or are already known to be set, match! if ((NeededMask & KnownOne) == NeededMask) diff --git a/lib/CodeGen/SelectionDAG/TargetLowering.cpp b/lib/CodeGen/SelectionDAG/TargetLowering.cpp index caedf57..b2c9016 100644 --- a/lib/CodeGen/SelectionDAG/TargetLowering.cpp +++ b/lib/CodeGen/SelectionDAG/TargetLowering.cpp @@ -375,7 +375,7 @@ bool TargetLowering::SimplifyDemandedBits(SDOperand Op, uint64_t DemandedMask, if (Depth != 0) { // If not at the root, Just compute the KnownZero/KnownOne bits to // simplify things downstream. - ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth); + TLO.DAG.ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth); return false; } // If this is the root being simplified, allow it to have multiple uses, @@ -404,8 +404,8 @@ bool TargetLowering::SimplifyDemandedBits(SDOperand Op, uint64_t DemandedMask, // the RHS. if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { uint64_t LHSZero, LHSOne; - ComputeMaskedBits(Op.getOperand(0), DemandedMask, - LHSZero, LHSOne, Depth+1); + TLO.DAG.ComputeMaskedBits(Op.getOperand(0), DemandedMask, + LHSZero, LHSOne, Depth+1); // If the LHS already has zeros where RHSC does, this and is dead. if ((LHSZero & DemandedMask) == (~RHSC->getValue() & DemandedMask)) return TLO.CombineTo(Op, Op.getOperand(0)); @@ -862,7 +862,7 @@ bool TargetLowering::SimplifyDemandedBits(SDOperand Op, uint64_t DemandedMask, case ISD::INTRINSIC_W_CHAIN: case ISD::INTRINSIC_VOID: // Just use ComputeMaskedBits to compute output bits. - ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth); + TLO.DAG.ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth); break; } @@ -874,337 +874,6 @@ bool TargetLowering::SimplifyDemandedBits(SDOperand Op, uint64_t DemandedMask, return false; } -/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use -/// this predicate to simplify operations downstream. Mask is known to be zero -/// for bits that V cannot have. -bool TargetLowering::MaskedValueIsZero(SDOperand Op, uint64_t Mask, - unsigned Depth) const { - // The masks are not wide enough to represent this type! Should use APInt. - if (Op.getValueType() == MVT::i128) - return false; - - uint64_t KnownZero, KnownOne; - ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth); - assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); - return (KnownZero & Mask) == Mask; -} - -/// ComputeMaskedBits - Determine which of the bits specified in Mask are -/// known to be either zero or one and return them in the KnownZero/KnownOne -/// bitsets. This code only analyzes bits in Mask, in order to short-circuit -/// processing. -void TargetLowering::ComputeMaskedBits(SDOperand Op, uint64_t Mask, - uint64_t &KnownZero, uint64_t &KnownOne, - unsigned Depth) const { - KnownZero = KnownOne = 0; // Don't know anything. - if (Depth == 6 || Mask == 0) - return; // Limit search depth. - - // The masks are not wide enough to represent this type! Should use APInt. - if (Op.getValueType() == MVT::i128) - return; - - uint64_t KnownZero2, KnownOne2; - - switch (Op.getOpcode()) { - case ISD::Constant: - // We know all of the bits for a constant! - KnownOne = cast<ConstantSDNode>(Op)->getValue() & Mask; - KnownZero = ~KnownOne & Mask; - return; - case ISD::AND: - // If either the LHS or the RHS are Zero, the result is zero. - ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); - Mask &= ~KnownZero; - ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); - assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); - assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); - - // Output known-1 bits are only known if set in both the LHS & RHS. - KnownOne &= KnownOne2; - // Output known-0 are known to be clear if zero in either the LHS | RHS. - KnownZero |= KnownZero2; - return; - case ISD::OR: - ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); - Mask &= ~KnownOne; - ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); - assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); - assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); - - // Output known-0 bits are only known if clear in both the LHS & RHS. - KnownZero &= KnownZero2; - // Output known-1 are known to be set if set in either the LHS | RHS. - KnownOne |= KnownOne2; - return; - case ISD::XOR: { - ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); - ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); - assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); - assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); - - // Output known-0 bits are known if clear or set in both the LHS & RHS. - uint64_t KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); - // Output known-1 are known to be set if set in only one of the LHS, RHS. - KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); - KnownZero = KnownZeroOut; - return; - } - case ISD::SELECT: - ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1); - ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1); - assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); - assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); - - // Only known if known in both the LHS and RHS. - KnownOne &= KnownOne2; - KnownZero &= KnownZero2; - return; - case ISD::SELECT_CC: - ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1); - ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1); - assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); - assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); - - // Only known if known in both the LHS and RHS. - KnownOne &= KnownOne2; - KnownZero &= KnownZero2; - return; - case ISD::SETCC: - // If we know the result of a setcc has the top bits zero, use this info. - if (getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) - KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL); - return; - case ISD::SHL: - // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 - if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { - ComputeMaskedBits(Op.getOperand(0), Mask >> SA->getValue(), - KnownZero, KnownOne, Depth+1); - assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); - KnownZero <<= SA->getValue(); - KnownOne <<= SA->getValue(); - KnownZero |= (1ULL << SA->getValue())-1; // low bits known zero. - } - return; - case ISD::SRL: - // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 - if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { - MVT::ValueType VT = Op.getValueType(); - unsigned ShAmt = SA->getValue(); - - uint64_t TypeMask = MVT::getIntVTBitMask(VT); - ComputeMaskedBits(Op.getOperand(0), (Mask << ShAmt) & TypeMask, - KnownZero, KnownOne, Depth+1); - assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); - KnownZero &= TypeMask; - KnownOne &= TypeMask; - KnownZero >>= ShAmt; - KnownOne >>= ShAmt; - - uint64_t HighBits = (1ULL << ShAmt)-1; - HighBits <<= MVT::getSizeInBits(VT)-ShAmt; - KnownZero |= HighBits; // High bits known zero. - } - return; - case ISD::SRA: - if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { - MVT::ValueType VT = Op.getValueType(); - unsigned ShAmt = SA->getValue(); - - // Compute the new bits that are at the top now. - uint64_t TypeMask = MVT::getIntVTBitMask(VT); - - uint64_t InDemandedMask = (Mask << ShAmt) & TypeMask; - // If any of the demanded bits are produced by the sign extension, we also - // demand the input sign bit. - uint64_t HighBits = (1ULL << ShAmt)-1; - HighBits <<= MVT::getSizeInBits(VT) - ShAmt; - if (HighBits & Mask) - InDemandedMask |= MVT::getIntVTSignBit(VT); - - ComputeMaskedBits(Op.getOperand(0), InDemandedMask, KnownZero, KnownOne, - Depth+1); - assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); - KnownZero &= TypeMask; - KnownOne &= TypeMask; - KnownZero >>= ShAmt; - KnownOne >>= ShAmt; - - // Handle the sign bits. - uint64_t SignBit = MVT::getIntVTSignBit(VT); - SignBit >>= ShAmt; // Adjust to where it is now in the mask. - - if (KnownZero & SignBit) { - KnownZero |= HighBits; // New bits are known zero. - } else if (KnownOne & SignBit) { - KnownOne |= HighBits; // New bits are known one. - } - } - return; - case ISD::SIGN_EXTEND_INREG: { - MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT(); - - // Sign extension. Compute the demanded bits in the result that are not - // present in the input. - uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & Mask; - - uint64_t InSignBit = MVT::getIntVTSignBit(EVT); - int64_t InputDemandedBits = Mask & MVT::getIntVTBitMask(EVT); - - // If the sign extended bits are demanded, we know that the sign - // bit is demanded. - if (NewBits) - InputDemandedBits |= InSignBit; - - ComputeMaskedBits(Op.getOperand(0), InputDemandedBits, - KnownZero, KnownOne, Depth+1); - assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); - - // If the sign bit of the input is known set or clear, then we know the - // top bits of the result. - if (KnownZero & InSignBit) { // Input sign bit known clear - KnownZero |= NewBits; - KnownOne &= ~NewBits; - } else if (KnownOne & InSignBit) { // Input sign bit known set - KnownOne |= NewBits; - KnownZero &= ~NewBits; - } else { // Input sign bit unknown - KnownZero &= ~NewBits; - KnownOne &= ~NewBits; - } - return; - } - case ISD::CTTZ: - case ISD::CTLZ: - case ISD::CTPOP: { - MVT::ValueType VT = Op.getValueType(); - unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1; - KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT); - KnownOne = 0; - return; - } - case ISD::LOAD: { - if (ISD::isZEXTLoad(Op.Val)) { - LoadSDNode *LD = cast<LoadSDNode>(Op); - MVT::ValueType VT = LD->getLoadedVT(); - KnownZero |= ~MVT::getIntVTBitMask(VT) & Mask; - } - return; - } - case ISD::ZERO_EXTEND: { - uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType()); - uint64_t NewBits = (~InMask) & Mask; - ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero, - KnownOne, Depth+1); - KnownZero |= NewBits & Mask; - KnownOne &= ~NewBits; - return; - } - case ISD::SIGN_EXTEND: { - MVT::ValueType InVT = Op.getOperand(0).getValueType(); - unsigned InBits = MVT::getSizeInBits(InVT); - uint64_t InMask = MVT::getIntVTBitMask(InVT); - uint64_t InSignBit = 1ULL << (InBits-1); - uint64_t NewBits = (~InMask) & Mask; - uint64_t InDemandedBits = Mask & InMask; - - // If any of the sign extended bits are demanded, we know that the sign - // bit is demanded. - if (NewBits & Mask) - InDemandedBits |= InSignBit; - - ComputeMaskedBits(Op.getOperand(0), InDemandedBits, KnownZero, - KnownOne, Depth+1); - // If the sign bit is known zero or one, the top bits match. - if (KnownZero & InSignBit) { - KnownZero |= NewBits; - KnownOne &= ~NewBits; - } else if (KnownOne & InSignBit) { - KnownOne |= NewBits; - KnownZero &= ~NewBits; - } else { // Otherwise, top bits aren't known. - KnownOne &= ~NewBits; - KnownZero &= ~NewBits; - } - return; - } - case ISD::ANY_EXTEND: { - MVT::ValueType VT = Op.getOperand(0).getValueType(); - ComputeMaskedBits(Op.getOperand(0), Mask & MVT::getIntVTBitMask(VT), - KnownZero, KnownOne, Depth+1); - return; - } - case ISD::TRUNCATE: { - ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); - assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); - uint64_t OutMask = MVT::getIntVTBitMask(Op.getValueType()); - KnownZero &= OutMask; - KnownOne &= OutMask; - break; - } - case ISD::AssertZext: { - MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT(); - uint64_t InMask = MVT::getIntVTBitMask(VT); - ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero, - KnownOne, Depth+1); - KnownZero |= (~InMask) & Mask; - return; - } - case ISD::ADD: { - // If either the LHS or the RHS are Zero, the result is zero. - ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); - ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); - assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); - assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); - - // Output known-0 bits are known if clear or set in both the low clear bits - // common to both LHS & RHS. For example, 8+(X<<3) is known to have the - // low 3 bits clear. - uint64_t KnownZeroOut = std::min(CountTrailingZeros_64(~KnownZero), - CountTrailingZeros_64(~KnownZero2)); - - KnownZero = (1ULL << KnownZeroOut) - 1; - KnownOne = 0; - return; - } - case ISD::SUB: { - ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)); - if (!CLHS) return; - - // We know that the top bits of C-X are clear if X contains less bits - // than C (i.e. no wrap-around can happen). For example, 20-X is - // positive if we can prove that X is >= 0 and < 16. - MVT::ValueType VT = CLHS->getValueType(0); - if ((CLHS->getValue() & MVT::getIntVTSignBit(VT)) == 0) { // sign bit clear - unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1); - uint64_t MaskV = (1ULL << (63-NLZ))-1; // NLZ can't be 64 with no sign bit - MaskV = ~MaskV & MVT::getIntVTBitMask(VT); - ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero, KnownOne, Depth+1); - - // If all of the MaskV bits are known to be zero, then we know the output - // top bits are zero, because we now know that the output is from [0-C]. - if ((KnownZero & MaskV) == MaskV) { - unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue()); - KnownZero = ~((1ULL << (64-NLZ2))-1) & Mask; // Top bits known zero. - KnownOne = 0; // No one bits known. - } else { - KnownZero = KnownOne = 0; // Otherwise, nothing known. - } - } - return; - } - default: - // Allow the target to implement this method for its nodes. - if (Op.getOpcode() >= ISD::BUILTIN_OP_END) { - case ISD::INTRINSIC_WO_CHAIN: - case ISD::INTRINSIC_W_CHAIN: - case ISD::INTRINSIC_VOID: - computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne); - } - return; - } -} - /// computeMaskedBitsForTargetNode - Determine which of the bits specified /// in Mask are known to be either zero or one and return them in the /// KnownZero/KnownOne bitsets. @@ -1212,6 +881,7 @@ void TargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op, uint64_t Mask, uint64_t &KnownZero, uint64_t &KnownOne, + const SelectionDAG &DAG, unsigned Depth) const { assert((Op.getOpcode() >= ISD::BUILTIN_OP_END || Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN || @@ -1223,222 +893,6 @@ void TargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op, KnownOne = 0; } -/// ComputeNumSignBits - Return the number of times the sign bit of the -/// register is replicated into the other bits. We know that at least 1 bit -/// is always equal to the sign bit (itself), but other cases can give us -/// information. For example, immediately after an "SRA X, 2", we know that -/// the top 3 bits are all equal to each other, so we return 3. -unsigned TargetLowering::ComputeNumSignBits(SDOperand Op, unsigned Depth) const{ - MVT::ValueType VT = Op.getValueType(); - assert(MVT::isInteger(VT) && "Invalid VT!"); - unsigned VTBits = MVT::getSizeInBits(VT); - unsigned Tmp, Tmp2; - - if (Depth == 6) - return 1; // Limit search depth. - - switch (Op.getOpcode()) { - default: break; - case ISD::AssertSext: - Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); - return VTBits-Tmp+1; - case ISD::AssertZext: - Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); - return VTBits-Tmp; - - case ISD::Constant: { - uint64_t Val = cast<ConstantSDNode>(Op)->getValue(); - // If negative, invert the bits, then look at it. - if (Val & MVT::getIntVTSignBit(VT)) - Val = ~Val; - - // Shift the bits so they are the leading bits in the int64_t. - Val <<= 64-VTBits; - - // Return # leading zeros. We use 'min' here in case Val was zero before - // shifting. We don't want to return '64' as for an i32 "0". - return std::min(VTBits, CountLeadingZeros_64(Val)); - } - - case ISD::SIGN_EXTEND: - Tmp = VTBits-MVT::getSizeInBits(Op.getOperand(0).getValueType()); - return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp; - - case ISD::SIGN_EXTEND_INREG: - // Max of the input and what this extends. - Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); - Tmp = VTBits-Tmp+1; - - Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1); - return std::max(Tmp, Tmp2); - - case ISD::SRA: - Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); - // SRA X, C -> adds C sign bits. - if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { - Tmp += C->getValue(); - if (Tmp > VTBits) Tmp = VTBits; - } - return Tmp; - case ISD::SHL: - if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { - // shl destroys sign bits. - Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); - if (C->getValue() >= VTBits || // Bad shift. - C->getValue() >= Tmp) break; // Shifted all sign bits out. - return Tmp - C->getValue(); - } - break; - case ISD::AND: - case ISD::OR: - case ISD::XOR: // NOT is handled here. - // Logical binary ops preserve the number of sign bits. - Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); - if (Tmp == 1) return 1; // Early out. - Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); - return std::min(Tmp, Tmp2); - - case ISD::SELECT: - Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); - if (Tmp == 1) return 1; // Early out. - Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); - return std::min(Tmp, Tmp2); - - case ISD::SETCC: - // If setcc returns 0/-1, all bits are sign bits. - if (getSetCCResultContents() == ZeroOrNegativeOneSetCCResult) - return VTBits; - break; - case ISD::ROTL: - case ISD::ROTR: - if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { - unsigned RotAmt = C->getValue() & (VTBits-1); - - // Handle rotate right by N like a rotate left by 32-N. - if (Op.getOpcode() == ISD::ROTR) - RotAmt = (VTBits-RotAmt) & (VTBits-1); - - // If we aren't rotating out all of the known-in sign bits, return the - // number that are left. This handles rotl(sext(x), 1) for example. - Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); - if (Tmp > RotAmt+1) return Tmp-RotAmt; - } - break; - case ISD::ADD: - // Add can have at most one carry bit. Thus we know that the output - // is, at worst, one more bit than the inputs. - Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); - if (Tmp == 1) return 1; // Early out. - - // Special case decrementing a value (ADD X, -1): - if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) - if (CRHS->isAllOnesValue()) { - uint64_t KnownZero, KnownOne; - uint64_t Mask = MVT::getIntVTBitMask(VT); - ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); - - // If the input is known to be 0 or 1, the output is 0/-1, which is all - // sign bits set. - if ((KnownZero|1) == Mask) - return VTBits; - - // If we are subtracting one from a positive number, there is no carry - // out of the result. - if (KnownZero & MVT::getIntVTSignBit(VT)) - return Tmp; - } - - Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); - if (Tmp2 == 1) return 1; - return std::min(Tmp, Tmp2)-1; - break; - - case ISD::SUB: - Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); - if (Tmp2 == 1) return 1; - - // Handle NEG. - if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) - if (CLHS->getValue() == 0) { - uint64_t KnownZero, KnownOne; - uint64_t Mask = MVT::getIntVTBitMask(VT); - ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); - // If the input is known to be 0 or 1, the output is 0/-1, which is all - // sign bits set. - if ((KnownZero|1) == Mask) - return VTBits; - - // If the input is known to be positive (the sign bit is known clear), - // the output of the NEG has the same number of sign bits as the input. - if (KnownZero & MVT::getIntVTSignBit(VT)) - return Tmp2; - - // Otherwise, we treat this like a SUB. - } - - // Sub can have at most one carry bit. Thus we know that the output - // is, at worst, one more bit than the inputs. - Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); - if (Tmp == 1) return 1; // Early out. - return std::min(Tmp, Tmp2)-1; - break; - case ISD::TRUNCATE: - // FIXME: it's tricky to do anything useful for this, but it is an important - // case for targets like X86. - break; - } - - // Handle LOADX separately here. EXTLOAD case will fallthrough. - if (Op.getOpcode() == ISD::LOAD) { - LoadSDNode *LD = cast<LoadSDNode>(Op); - unsigned ExtType = LD->getExtensionType(); - switch (ExtType) { - default: break; - case ISD::SEXTLOAD: // '17' bits known - Tmp = MVT::getSizeInBits(LD->getLoadedVT()); - return VTBits-Tmp+1; - case ISD::ZEXTLOAD: // '16' bits known - Tmp = MVT::getSizeInBits(LD->getLoadedVT()); - return VTBits-Tmp; - } - } - - // Allow the target to implement this method for its nodes. - if (Op.getOpcode() >= ISD::BUILTIN_OP_END || - Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN || - Op.getOpcode() == ISD::INTRINSIC_W_CHAIN || - Op.getOpcode() == ISD::INTRINSIC_VOID) { - unsigned NumBits = ComputeNumSignBitsForTargetNode(Op, Depth); - if (NumBits > 1) return NumBits; - } - - // Finally, if we can prove that the top bits of the result are 0's or 1's, - // use this information. - uint64_t KnownZero, KnownOne; - uint64_t Mask = MVT::getIntVTBitMask(VT); - ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth); - - uint64_t SignBit = MVT::getIntVTSignBit(VT); - if (KnownZero & SignBit) { // SignBit is 0 - Mask = KnownZero; - } else if (KnownOne & SignBit) { // SignBit is 1; - Mask = KnownOne; - } else { - // Nothing known. - return 1; - } - - // Okay, we know that the sign bit in Mask is set. Use CLZ to determine - // the number of identical bits in the top of the input value. - Mask ^= ~0ULL; - Mask <<= 64-VTBits; - // Return # leading zeros. We use 'min' here in case Val was zero before - // shifting. We don't want to return '64' as for an i32 "0". - return std::min(VTBits, CountLeadingZeros_64(Mask)); -} - - - /// ComputeNumSignBitsForTargetNode - This method can be implemented by /// targets that want to expose additional information about sign bits to the /// DAG Combiner. @@ -1597,7 +1051,8 @@ TargetLowering::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1, 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)){ + if (DAG.MaskedValueIsZero(N0, + MVT::getIntVTBitMask(N0.getValueType())-1)){ // Okay, get the un-inverted input value. SDOperand Val; if (N0.getOpcode() == ISD::XOR) @@ -1761,7 +1216,7 @@ TargetLowering::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1, 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())) + if (DAG.MaskedValueIsZero(N0.getOperand(0), ~LHSR->getValue())) return DAG.getSetCC(VT, N0.getOperand(0), DAG.getConstant(LHSR->getValue()^RHSC->getValue(), N0.getValueType()), Cond); diff --git a/lib/Target/ARM/ARMISelLowering.cpp b/lib/Target/ARM/ARMISelLowering.cpp index e371714..1ec2ad0 100644 --- a/lib/Target/ARM/ARMISelLowering.cpp +++ b/lib/Target/ARM/ARMISelLowering.cpp @@ -1254,9 +1254,8 @@ static SDOperand LowerMUL(SDOperand Op, SelectionDAG &DAG) { SDOperand RL = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32, Op.getOperand(1), DAG.getConstant(0, MVT::i32)); - const TargetLowering &TL = DAG.getTargetLoweringInfo(); - unsigned LHSSB = TL.ComputeNumSignBits(Op.getOperand(0)); - unsigned RHSSB = TL.ComputeNumSignBits(Op.getOperand(1)); + unsigned LHSSB = DAG.ComputeNumSignBits(Op.getOperand(0)); + unsigned RHSSB = DAG.ComputeNumSignBits(Op.getOperand(1)); SDOperand Lo, Hi; // Figure out how to lower this multiply. @@ -1265,8 +1264,8 @@ static SDOperand LowerMUL(SDOperand Op, SelectionDAG &DAG) { Lo = DAG.getNode(ISD::MUL, MVT::i32, LL, RL); Hi = DAG.getNode(ISD::MULHS, MVT::i32, LL, RL); } else if (LHSSB == 32 && RHSSB == 32 && - TL.MaskedValueIsZero(Op.getOperand(0), 0xFFFFFFFF00000000ULL) && - TL.MaskedValueIsZero(Op.getOperand(1), 0xFFFFFFFF00000000ULL)) { + DAG.MaskedValueIsZero(Op.getOperand(0), 0xFFFFFFFF00000000ULL) && + DAG.MaskedValueIsZero(Op.getOperand(1), 0xFFFFFFFF00000000ULL)) { // If the inputs are zero extended, use mulhu. Lo = DAG.getNode(ISD::MUL, MVT::i32, LL, RL); Hi = DAG.getNode(ISD::MULHU, MVT::i32, LL, RL); @@ -1757,6 +1756,7 @@ void ARMTargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op, uint64_t Mask, uint64_t &KnownZero, uint64_t &KnownOne, + const SelectionDAG &DAG, unsigned Depth) const { KnownZero = 0; KnownOne = 0; @@ -1764,12 +1764,12 @@ void ARMTargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op, default: break; case ARMISD::CMOV: { // Bits are known zero/one if known on the LHS and RHS. - ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); + DAG.ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); if (KnownZero == 0 && KnownOne == 0) return; uint64_t KnownZeroRHS, KnownOneRHS; - ComputeMaskedBits(Op.getOperand(1), Mask, - KnownZeroRHS, KnownOneRHS, Depth+1); + DAG.ComputeMaskedBits(Op.getOperand(1), Mask, + KnownZeroRHS, KnownOneRHS, Depth+1); KnownZero &= KnownZeroRHS; KnownOne &= KnownOneRHS; return; diff --git a/lib/Target/ARM/ARMISelLowering.h b/lib/Target/ARM/ARMISelLowering.h index d51b680..2b66f23 100644 --- a/lib/Target/ARM/ARMISelLowering.h +++ b/lib/Target/ARM/ARMISelLowering.h @@ -108,6 +108,7 @@ namespace llvm { uint64_t Mask, uint64_t &KnownZero, uint64_t &KnownOne, + const SelectionDAG &DAG, unsigned Depth) const; ConstraintType getConstraintType(const std::string &Constraint) const; std::pair<unsigned, const TargetRegisterClass*> diff --git a/lib/Target/Alpha/AlphaISelDAGToDAG.cpp b/lib/Target/Alpha/AlphaISelDAGToDAG.cpp index e82e24b..4f7533c 100644 --- a/lib/Target/Alpha/AlphaISelDAGToDAG.cpp +++ b/lib/Target/Alpha/AlphaISelDAGToDAG.cpp @@ -90,7 +90,7 @@ namespace { // see if the missing bits (0x1000) are already known zero if not, the zap // isn't okay to do, as it won't clear all the required bits. if (BitsToCheck && - !getTargetLowering().MaskedValueIsZero(LHS, BitsToCheck)) + !CurDAG->MaskedValueIsZero(LHS, BitsToCheck)) return 0; return Result; diff --git a/lib/Target/PowerPC/PPCISelDAGToDAG.cpp b/lib/Target/PowerPC/PPCISelDAGToDAG.cpp index 7a4b29f..35ab9de 100644 --- a/lib/Target/PowerPC/PPCISelDAGToDAG.cpp +++ b/lib/Target/PowerPC/PPCISelDAGToDAG.cpp @@ -424,8 +424,8 @@ SDNode *PPCDAGToDAGISel::SelectBitfieldInsert(SDNode *N) { SDOperand Op1 = N->getOperand(1); uint64_t LKZ, LKO, RKZ, RKO; - TLI.ComputeMaskedBits(Op0, 0xFFFFFFFFULL, LKZ, LKO); - TLI.ComputeMaskedBits(Op1, 0xFFFFFFFFULL, RKZ, RKO); + CurDAG->ComputeMaskedBits(Op0, 0xFFFFFFFFULL, LKZ, LKO); + CurDAG->ComputeMaskedBits(Op1, 0xFFFFFFFFULL, RKZ, RKO); unsigned TargetMask = LKZ; unsigned InsertMask = RKZ; diff --git a/lib/Target/PowerPC/PPCISelLowering.cpp b/lib/Target/PowerPC/PPCISelLowering.cpp index bf07fc6..a1fe460 100644 --- a/lib/Target/PowerPC/PPCISelLowering.cpp +++ b/lib/Target/PowerPC/PPCISelLowering.cpp @@ -688,10 +688,10 @@ bool PPCTargetLowering::SelectAddressRegReg(SDOperand N, SDOperand &Base, // disjoint. uint64_t LHSKnownZero, LHSKnownOne; uint64_t RHSKnownZero, RHSKnownOne; - ComputeMaskedBits(N.getOperand(0), ~0U, LHSKnownZero, LHSKnownOne); + DAG.ComputeMaskedBits(N.getOperand(0), ~0U, LHSKnownZero, LHSKnownOne); if (LHSKnownZero) { - ComputeMaskedBits(N.getOperand(1), ~0U, RHSKnownZero, RHSKnownOne); + DAG.ComputeMaskedBits(N.getOperand(1), ~0U, RHSKnownZero, RHSKnownOne); // If all of the bits are known zero on the LHS or RHS, the add won't // carry. if ((LHSKnownZero | RHSKnownZero) == ~0U) { @@ -742,7 +742,7 @@ bool PPCTargetLowering::SelectAddressRegImm(SDOperand N, SDOperand &Disp, // (for better address arithmetic) if the LHS and RHS of the OR are // provably disjoint. uint64_t LHSKnownZero, LHSKnownOne; - ComputeMaskedBits(N.getOperand(0), ~0U, LHSKnownZero, LHSKnownOne); + DAG.ComputeMaskedBits(N.getOperand(0), ~0U, LHSKnownZero, LHSKnownOne); if ((LHSKnownZero|~(unsigned)imm) == ~0U) { // If all of the bits are known zero on the LHS or RHS, the add won't // carry. @@ -850,7 +850,7 @@ bool PPCTargetLowering::SelectAddressRegImmShift(SDOperand N, SDOperand &Disp, // (for better address arithmetic) if the LHS and RHS of the OR are // provably disjoint. uint64_t LHSKnownZero, LHSKnownOne; - ComputeMaskedBits(N.getOperand(0), ~0U, LHSKnownZero, LHSKnownOne); + DAG.ComputeMaskedBits(N.getOperand(0), ~0U, LHSKnownZero, LHSKnownOne); if ((LHSKnownZero|~(unsigned)imm) == ~0U) { // If all of the bits are known zero on the LHS or RHS, the add won't // carry. @@ -3235,6 +3235,7 @@ void PPCTargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op, uint64_t Mask, uint64_t &KnownZero, uint64_t &KnownOne, + const SelectionDAG &DAG, unsigned Depth) const { KnownZero = 0; KnownOne = 0; diff --git a/lib/Target/PowerPC/PPCISelLowering.h b/lib/Target/PowerPC/PPCISelLowering.h index 684a366..0581865 100644 --- a/lib/Target/PowerPC/PPCISelLowering.h +++ b/lib/Target/PowerPC/PPCISelLowering.h @@ -230,6 +230,7 @@ namespace llvm { uint64_t Mask, uint64_t &KnownZero, uint64_t &KnownOne, + const SelectionDAG &DAG, unsigned Depth = 0) const; virtual MachineBasicBlock *InsertAtEndOfBasicBlock(MachineInstr *MI, diff --git a/lib/Target/Sparc/SparcISelDAGToDAG.cpp b/lib/Target/Sparc/SparcISelDAGToDAG.cpp index 7275ce6..7a093f0 100644 --- a/lib/Target/Sparc/SparcISelDAGToDAG.cpp +++ b/lib/Target/Sparc/SparcISelDAGToDAG.cpp @@ -112,6 +112,7 @@ namespace { uint64_t Mask, uint64_t &KnownZero, uint64_t &KnownOne, + const SelectionDAG &DAG, unsigned Depth = 0) const; virtual std::vector<SDOperand> @@ -261,6 +262,7 @@ void SparcTargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op, uint64_t Mask, uint64_t &KnownZero, uint64_t &KnownOne, + const SelectionDAG &DAG, unsigned Depth) const { uint64_t KnownZero2, KnownOne2; KnownZero = KnownOne = 0; // Don't know anything. @@ -269,8 +271,10 @@ void SparcTargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op, default: break; case SPISD::SELECT_ICC: case SPISD::SELECT_FCC: - ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); - ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); + DAG.ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, + Depth+1); + DAG.ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, + Depth+1); assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); diff --git a/lib/Target/X86/X86ISelDAGToDAG.cpp b/lib/Target/X86/X86ISelDAGToDAG.cpp index bf08dd8..58a72b8 100644 --- a/lib/Target/X86/X86ISelDAGToDAG.cpp +++ b/lib/Target/X86/X86ISelDAGToDAG.cpp @@ -744,7 +744,7 @@ bool X86DAGToDAGISel::MatchAddress(SDOperand N, X86ISelAddressMode &AM, // On x86-64, the resultant disp must fit in 32-bits. isInt32(AM.Disp + CN->getSignExtended()) && // Check to see if the LHS & C is zero. - TLI.MaskedValueIsZero(N.getOperand(0), CN->getValue())) { + CurDAG->MaskedValueIsZero(N.getOperand(0), CN->getValue())) { AM.Disp += CN->getValue(); return false; } diff --git a/lib/Target/X86/X86ISelLowering.cpp b/lib/Target/X86/X86ISelLowering.cpp index e0ffb70..d048cae 100644 --- a/lib/Target/X86/X86ISelLowering.cpp +++ b/lib/Target/X86/X86ISelLowering.cpp @@ -4506,6 +4506,7 @@ void X86TargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op, uint64_t Mask, uint64_t &KnownZero, uint64_t &KnownOne, + const SelectionDAG &DAG, unsigned Depth) const { unsigned Opc = Op.getOpcode(); assert((Opc >= ISD::BUILTIN_OP_END || diff --git a/lib/Target/X86/X86ISelLowering.h b/lib/Target/X86/X86ISelLowering.h index 87022fa..00d9375 100644 --- a/lib/Target/X86/X86ISelLowering.h +++ b/lib/Target/X86/X86ISelLowering.h @@ -319,6 +319,7 @@ namespace llvm { uint64_t Mask, uint64_t &KnownZero, uint64_t &KnownOne, + const SelectionDAG &DAG, unsigned Depth = 0) const; SDOperand getReturnAddressFrameIndex(SelectionDAG &DAG); |