-/// 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 {
- 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.
-
- 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;
- }
-}
-