#include "llvm/Target/TargetSelectionDAGInfo.h"
#include <algorithm>
#include <cmath>
+
using namespace llvm;
/// makeVTList - Return an instance of the SDVTList struct initialized with the
}
}
+static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
+ bool exact) {
+ ID.AddBoolean(nuw);
+ ID.AddBoolean(nsw);
+ ID.AddBoolean(exact);
+}
+
+/// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
+static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
+ bool nuw, bool nsw, bool exact) {
+ if (isBinOpWithFlags(Opcode))
+ AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
+}
+
static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
SDVTList VTList, ArrayRef<SDValue> OpList) {
AddNodeIDOpcode(ID, OpC);
ID.AddInteger(ST->getPointerInfo().getAddrSpace());
break;
}
+ case ISD::SDIV:
+ case ISD::UDIV:
+ case ISD::SRA:
+ case ISD::SRL:
+ case ISD::MUL:
+ case ISD::ADD:
+ case ISD::SUB:
+ case ISD::SHL: {
+ const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
+ AddBinaryNodeIDCustom(ID, N->getOpcode(), BinNode->hasNoUnsignedWrap(),
+ BinNode->hasNoSignedWrap(), BinNode->isExact());
+ break;
+ }
case ISD::ATOMIC_CMP_SWAP:
+ case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
case ISD::ATOMIC_SWAP:
case ISD::ATOMIC_LOAD_ADD:
case ISD::ATOMIC_LOAD_SUB:
DeallocateNode(AllNodes.begin());
}
+BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
+ SDVTList VTs, SDValue N1,
+ SDValue N2, bool nuw, bool nsw,
+ bool exact) {
+ if (isBinOpWithFlags(Opcode)) {
+ BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
+ Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
+ FN->setHasNoUnsignedWrap(nuw);
+ FN->setHasNoSignedWrap(nsw);
+ FN->setIsExact(exact);
+
+ return FN;
+ }
+
+ BinarySDNode *N = new (NodeAllocator)
+ BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
+ return N;
+}
+
void SelectionDAG::clear() {
allnodes_clear();
OperandAllocator.Reset();
if (BitWidth < 64)
Offset = SignExtend64(Offset, BitWidth);
- const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
- if (!GVar) {
- // If GV is an alias then use the aliasee for determining thread-localness.
- if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
- GVar = dyn_cast_or_null<GlobalVariable>(GA->getAliasedGlobal());
- }
-
unsigned Opc;
- if (GVar && GVar->isThreadLocal())
+ if (GV->isThreadLocal())
Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
else
Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
unsigned Depth) const {
APInt KnownZero, KnownOne;
- ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
- assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
+ computeKnownBits(Op, KnownZero, KnownOne, Depth);
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(SDValue Op, APInt &KnownZero,
- APInt &KnownOne, unsigned Depth) const {
+/// Determine which bits of Op are known to be either zero or one and return
+/// them in the KnownZero/KnownOne bitsets.
+void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
+ APInt &KnownOne, unsigned Depth) const {
const TargetLowering *TLI = TM.getTargetLowering();
unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
// We know all of the bits for a constant!
KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
KnownZero = ~KnownOne;
- return;
+ break;
case ISD::AND:
// If either the LHS or the RHS are Zero, the result is zero.
- ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
- ComputeMaskedBits(Op.getOperand(0), 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?");
+ computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
// 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;
+ break;
case ISD::OR:
- ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
- ComputeMaskedBits(Op.getOperand(0), 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?");
+ computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
// 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;
+ break;
case ISD::XOR: {
- ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
- ComputeMaskedBits(Op.getOperand(0), 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?");
+ computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
// Output known-0 bits are known if clear or set in both the LHS & RHS.
APInt 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;
+ break;
}
case ISD::MUL: {
- ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
- ComputeMaskedBits(Op.getOperand(0), 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?");
+ computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
// If low bits are zero in either operand, output low known-0 bits.
// Also compute a conserative estimate for high known-0 bits.
LeadZ = std::min(LeadZ, BitWidth);
KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
APInt::getHighBitsSet(BitWidth, LeadZ);
- return;
+ break;
}
case ISD::UDIV: {
// For the purposes of computing leading zeros we can conservatively
// treat a udiv as a logical right shift by the power of 2 known to
// be less than the denominator.
- ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
+ computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
unsigned LeadZ = KnownZero2.countLeadingOnes();
KnownOne2.clearAllBits();
KnownZero2.clearAllBits();
- ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
+ computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
if (RHSUnknownLeadingOnes != BitWidth)
LeadZ = std::min(BitWidth,
LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
- return;
+ break;
}
case ISD::SELECT:
- ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
- ComputeMaskedBits(Op.getOperand(1), 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?");
+ computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
// Only known if known in both the LHS and RHS.
KnownOne &= KnownOne2;
KnownZero &= KnownZero2;
- return;
+ break;
case ISD::SELECT_CC:
- ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
- ComputeMaskedBits(Op.getOperand(2), 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?");
+ computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
// Only known if known in both the LHS and RHS.
KnownOne &= KnownOne2;
KnownZero &= KnownZero2;
- return;
+ break;
case ISD::SADDO:
case ISD::UADDO:
case ISD::SSUBO:
case ISD::SMULO:
case ISD::UMULO:
if (Op.getResNo() != 1)
- return;
+ break;
// The boolean result conforms to getBooleanContents. Fall through.
case ISD::SETCC:
// If we know the result of a setcc has the top bits zero, use this info.
if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
- return;
+ break;
case ISD::SHL:
// (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
// If the shift count is an invalid immediate, don't do anything.
if (ShAmt >= BitWidth)
- return;
+ break;
- ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
- assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
+ computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
KnownZero <<= ShAmt;
KnownOne <<= ShAmt;
// low bits known zero.
KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
}
- return;
+ break;
case ISD::SRL:
// (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
// If the shift count is an invalid immediate, don't do anything.
if (ShAmt >= BitWidth)
- return;
+ break;
- ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
- assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
+ computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
KnownZero = KnownZero.lshr(ShAmt);
KnownOne = KnownOne.lshr(ShAmt);
APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
KnownZero |= HighBits; // High bits known zero.
}
- return;
+ break;
case ISD::SRA:
if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
unsigned ShAmt = SA->getZExtValue();
// If the shift count is an invalid immediate, don't do anything.
if (ShAmt >= BitWidth)
- return;
+ break;
// If any of the demanded bits are produced by the sign extension, we also
// demand the input sign bit.
APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
- ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
- assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
+ computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
KnownZero = KnownZero.lshr(ShAmt);
KnownOne = KnownOne.lshr(ShAmt);
KnownOne |= HighBits; // New bits are known one.
}
}
- return;
+ break;
case ISD::SIGN_EXTEND_INREG: {
EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
unsigned EBits = EVT.getScalarType().getSizeInBits();
if (NewBits.getBoolValue())
InputDemandedBits |= InSignBit;
- ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
KnownOne &= InputDemandedBits;
KnownZero &= InputDemandedBits;
- 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.
KnownZero &= ~NewBits;
KnownOne &= ~NewBits;
}
- return;
+ break;
}
case ISD::CTTZ:
case ISD::CTTZ_ZERO_UNDEF:
unsigned LowBits = Log2_32(BitWidth)+1;
KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
KnownOne.clearAllBits();
- return;
+ break;
}
case ISD::LOAD: {
LoadSDNode *LD = cast<LoadSDNode>(Op);
unsigned MemBits = VT.getScalarType().getSizeInBits();
KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
} else if (const MDNode *Ranges = LD->getRanges()) {
- computeMaskedBitsLoad(*Ranges, KnownZero);
+ computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
}
- return;
+ break;
}
case ISD::ZERO_EXTEND: {
EVT InVT = Op.getOperand(0).getValueType();
APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
KnownZero = KnownZero.trunc(InBits);
KnownOne = KnownOne.trunc(InBits);
- ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
KnownZero = KnownZero.zext(BitWidth);
KnownOne = KnownOne.zext(BitWidth);
KnownZero |= NewBits;
- return;
+ break;
}
case ISD::SIGN_EXTEND: {
EVT InVT = Op.getOperand(0).getValueType();
KnownZero = KnownZero.trunc(InBits);
KnownOne = KnownOne.trunc(InBits);
- ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
// Note if the sign bit is known to be zero or one.
bool SignBitKnownZero = KnownZero.isNegative();
bool SignBitKnownOne = KnownOne.isNegative();
- assert(!(SignBitKnownZero && SignBitKnownOne) &&
- "Sign bit can't be known to be both zero and one!");
KnownZero = KnownZero.zext(BitWidth);
KnownOne = KnownOne.zext(BitWidth);
KnownZero |= NewBits;
else if (SignBitKnownOne)
KnownOne |= NewBits;
- return;
+ break;
}
case ISD::ANY_EXTEND: {
EVT InVT = Op.getOperand(0).getValueType();
unsigned InBits = InVT.getScalarType().getSizeInBits();
KnownZero = KnownZero.trunc(InBits);
KnownOne = KnownOne.trunc(InBits);
- ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
KnownZero = KnownZero.zext(BitWidth);
KnownOne = KnownOne.zext(BitWidth);
- return;
+ break;
}
case ISD::TRUNCATE: {
EVT InVT = Op.getOperand(0).getValueType();
unsigned InBits = InVT.getScalarType().getSizeInBits();
KnownZero = KnownZero.zext(InBits);
KnownOne = KnownOne.zext(InBits);
- ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
- assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
+ computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
KnownZero = KnownZero.trunc(BitWidth);
KnownOne = KnownOne.trunc(BitWidth);
break;
case ISD::AssertZext: {
EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
- ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
KnownZero |= (~InMask);
KnownOne &= (~KnownZero);
- return;
+ break;
}
case ISD::FGETSIGN:
// All bits are zero except the low bit.
KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
- return;
+ break;
case ISD::SUB: {
if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
// NLZ can't be BitWidth with no sign bit
APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
- ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
+ computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, 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
// 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.
- ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
- assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
+ computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
- ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
- assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
+ computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
KnownZeroOut = std::min(KnownZeroOut,
KnownZero2.countTrailingOnes());
if (Op.getOpcode() == ISD::ADD) {
KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
- return;
+ break;
}
// With ADDE, a carry bit may be added in, so we can only use this
// are known zero.
if (KnownZeroOut >= 2) // ADDE
KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
- return;
+ break;
}
case ISD::SREM:
if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
const APInt &RA = Rem->getAPIntValue().abs();
if (RA.isPowerOf2()) {
APInt LowBits = RA - 1;
- ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
+ computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
// The low bits of the first operand are unchanged by the srem.
KnownZero = KnownZero2 & LowBits;
assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
}
}
- return;
+ break;
case ISD::UREM: {
if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
const APInt &RA = Rem->getAPIntValue();
if (RA.isPowerOf2()) {
APInt LowBits = (RA - 1);
- KnownZero |= ~LowBits;
- ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
- assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
+ computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
+
+ // The upper bits are all zero, the lower ones are unchanged.
+ KnownZero = KnownZero2 | ~LowBits;
+ KnownOne = KnownOne2 & LowBits;
break;
}
}
// Since the result is less than or equal to either operand, any leading
// zero bits in either operand must also exist in the result.
- ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
- ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
+ computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
KnownZero2.countLeadingOnes());
KnownOne.clearAllBits();
KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
- return;
+ break;
}
case ISD::FrameIndex:
case ISD::TargetFrameIndex:
if (unsigned Align = InferPtrAlignment(Op)) {
// The low bits are known zero if the pointer is aligned.
KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
- return;
+ break;
}
break;
case ISD::INTRINSIC_W_CHAIN:
case ISD::INTRINSIC_VOID:
// Allow the target to implement this method for its nodes.
- TLI->computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
- return;
+ TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
+ break;
}
+
+ assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
}
/// ComputeNumSignBits - Return the number of times the sign bit of the
FirstAnswer = std::min(Tmp, Tmp2);
// We computed what we know about the sign bits as our first
// answer. Now proceed to the generic code that uses
- // ComputeMaskedBits, and pick whichever answer is better.
+ // computeKnownBits, and pick whichever answer is better.
}
break;
if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
if (CRHS->isAllOnesValue()) {
APInt KnownZero, KnownOne;
- ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(0), 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 (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
if (CLHS->isNullValue()) {
APInt KnownZero, KnownOne;
- ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(1), 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 | APInt(VTBits, 1)).isAllOnesValue())
// Finally, if we can prove that the top bits of the result are 0's or 1's,
// use this information.
APInt KnownZero, KnownOne;
- ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
+ computeKnownBits(Op, KnownZero, KnownOne, Depth);
APInt Mask;
if (KnownZero.isNegative()) { // sign bit is 0
}
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
- SDValue N2) {
+ SDValue N2, bool nuw, bool nsw, bool exact) {
ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
switch (Opcode) {
}
// Memoize this node if possible.
- SDNode *N;
+ BinarySDNode *N;
SDVTList VTs = getVTList(VT);
+ const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
if (VT != MVT::Glue) {
- SDValue Ops[] = { N1, N2 };
+ SDValue Ops[] = {N1, N2};
FoldingSetNodeID ID;
AddNodeIDNode(ID, Opcode, VTs, Ops);
+ if (BinOpHasFlags)
+ AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
void *IP = nullptr;
if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
return SDValue(E, 0);
- N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
- DL.getDebugLoc(), VTs, N1, N2);
+ N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
+
CSEMap.InsertNode(N, IP);
} else {
- N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
- DL.getDebugLoc(), VTs, N1, N2);
+
+ N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
}
AllNodes.push_back(N);
Entry.Node = Src; Args.push_back(Entry);
Entry.Node = Size; Args.push_back(Entry);
// FIXME: pass in SDLoc
- TargetLowering::
- CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
- false, false, false, false, 0,
- TLI->getLibcallCallingConv(RTLIB::MEMCPY),
- /*isTailCall=*/false,
- /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
- getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
- TLI->getPointerTy()),
- Args, *this, dl);
+ TargetLowering::CallLoweringInfo CLI(*this);
+ CLI.setDebugLoc(dl).setChain(Chain)
+ .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
+ Type::getVoidTy(*getContext()),
+ getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
+ TLI->getPointerTy()), &Args, 0)
+ .setDiscardResult();
std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
return CallResult.second;
Entry.Node = Src; Args.push_back(Entry);
Entry.Node = Size; Args.push_back(Entry);
// FIXME: pass in SDLoc
- TargetLowering::
- CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
- false, false, false, false, 0,
- TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
- /*isTailCall=*/false,
- /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
- getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
- TLI->getPointerTy()),
- Args, *this, dl);
+ TargetLowering::CallLoweringInfo CLI(*this);
+ CLI.setDebugLoc(dl).setChain(Chain)
+ .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
+ Type::getVoidTy(*getContext()),
+ getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
+ TLI->getPointerTy()), &Args, 0)
+ .setDiscardResult();
std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
return CallResult.second;
Entry.Ty = IntPtrTy;
Entry.isSExt = false;
Args.push_back(Entry);
+
// FIXME: pass in SDLoc
- TargetLowering::
- CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
- false, false, false, false, 0,
- TLI->getLibcallCallingConv(RTLIB::MEMSET),
- /*isTailCall=*/false,
- /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
- getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
- TLI->getPointerTy()),
- Args, *this, dl);
- std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
+ TargetLowering::CallLoweringInfo CLI(*this);
+ CLI.setDebugLoc(dl).setChain(Chain)
+ .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
+ Type::getVoidTy(*getContext()),
+ getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
+ TLI->getPointerTy()), &Args, 0)
+ .setDiscardResult();
+ std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
return CallResult.second;
}
Ordering, SynchScope);
}
-SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
- SDValue Chain, SDValue Ptr, SDValue Cmp,
- SDValue Swp, MachinePointerInfo PtrInfo,
- unsigned Alignment,
- AtomicOrdering SuccessOrdering,
- AtomicOrdering FailureOrdering,
- SynchronizationScope SynchScope) {
+SDValue SelectionDAG::getAtomicCmpSwap(
+ unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
+ SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
+ unsigned Alignment, AtomicOrdering SuccessOrdering,
+ AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
+ assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
+ Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
+ assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
+
if (Alignment == 0) // Ensure that codegen never sees alignment 0
Alignment = getEVTAlignment(MemVT);
MachineFunction &MF = getMachineFunction();
- // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
- // For now, atomics are considered to be volatile always.
// FIXME: Volatile isn't really correct; we should keep track of atomic
// orderings in the memoperand.
unsigned Flags = MachineMemOperand::MOVolatile;
- if (Opcode != ISD::ATOMIC_STORE)
- Flags |= MachineMemOperand::MOLoad;
- if (Opcode != ISD::ATOMIC_LOAD)
- Flags |= MachineMemOperand::MOStore;
+ Flags |= MachineMemOperand::MOLoad;
+ Flags |= MachineMemOperand::MOStore;
MachineMemOperand *MMO =
MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
- return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
- SuccessOrdering, FailureOrdering, SynchScope);
+ return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
+ SuccessOrdering, FailureOrdering, SynchScope);
}
-SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
- SDValue Chain,
- SDValue Ptr, SDValue Cmp,
- SDValue Swp, MachineMemOperand *MMO,
- AtomicOrdering SuccessOrdering,
- AtomicOrdering FailureOrdering,
- SynchronizationScope SynchScope) {
- assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
+SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
+ SDVTList VTs, SDValue Chain, SDValue Ptr,
+ SDValue Cmp, SDValue Swp,
+ MachineMemOperand *MMO,
+ AtomicOrdering SuccessOrdering,
+ AtomicOrdering FailureOrdering,
+ SynchronizationScope SynchScope) {
+ assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
+ Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
- EVT VT = Cmp.getValueType();
-
- SDVTList VTs = getVTList(VT, MVT::Other);
SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
- return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, SuccessOrdering,
- FailureOrdering, SynchScope);
+ return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
+ SuccessOrdering, FailureOrdering, SynchScope);
}
SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
/// getNodeIfExists - Get the specified node if it's already available, or
/// else return NULL.
SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
- ArrayRef<SDValue> Ops) {
- if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
+ ArrayRef<SDValue> Ops, bool nuw, bool nsw,
+ bool exact) {
+ if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
FoldingSetNodeID ID;
AddNodeIDNode(ID, Opcode, VTList, Ops);
+ if (isBinOpWithFlags(Opcode))
+ AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
void *IP = nullptr;
if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
return E;
// count of outstanding operands.
for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
SDNode *N = I++;
- checkForCycles(N);
+ checkForCycles(N, this);
unsigned Degree = N->getNumOperands();
if (Degree == 0) {
// A node with no uses, add it to the result array immediately.
// such that by the time the end is reached all nodes will be sorted.
for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
SDNode *N = I;
- checkForCycles(N);
+ checkForCycles(N, this);
// N is in sorted position, so all its uses have one less operand
// that needs to be sorted.
for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
#ifndef NDEBUG
SDNode *S = ++I;
dbgs() << "Overran sorted position:\n";
- S->dumprFull();
+ S->dumprFull(this); dbgs() << "\n";
+ dbgs() << "Checking if this is due to cycles\n";
+ checkForCycles(this, true);
#endif
llvm_unreachable(nullptr);
}
if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
- llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
- TLI->getDataLayout());
+ llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
+ TLI->getDataLayout());
unsigned AlignBits = KnownZero.countTrailingOnes();
unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
if (Align)
return true;
}
-#ifdef XDEBUG
+#ifndef NDEBUG
static void checkForCyclesHelper(const SDNode *N,
SmallPtrSet<const SDNode*, 32> &Visited,
- SmallPtrSet<const SDNode*, 32> &Checked) {
+ SmallPtrSet<const SDNode*, 32> &Checked,
+ const llvm::SelectionDAG *DAG) {
// If this node has already been checked, don't check it again.
if (Checked.count(N))
return;
// If a node has already been visited on this depth-first walk, reject it as
// a cycle.
if (!Visited.insert(N)) {
- dbgs() << "Offending node:\n";
- N->dumprFull();
errs() << "Detected cycle in SelectionDAG\n";
+ dbgs() << "Offending node:\n";
+ N->dumprFull(DAG); dbgs() << "\n";
abort();
}
for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
- checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
+ checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
Checked.insert(N);
Visited.erase(N);
}
#endif
-void llvm::checkForCycles(const llvm::SDNode *N) {
+void llvm::checkForCycles(const llvm::SDNode *N,
+ const llvm::SelectionDAG *DAG,
+ bool force) {
+#ifndef NDEBUG
+ bool check = force;
#ifdef XDEBUG
- assert(N && "Checking nonexistent SDNode");
- SmallPtrSet<const SDNode*, 32> visited;
- SmallPtrSet<const SDNode*, 32> checked;
- checkForCyclesHelper(N, visited, checked);
-#endif
+ check = true;
+#endif // XDEBUG
+ if (check) {
+ assert(N && "Checking nonexistent SDNode");
+ SmallPtrSet<const SDNode*, 32> visited;
+ SmallPtrSet<const SDNode*, 32> checked;
+ checkForCyclesHelper(N, visited, checked, DAG);
+ }
+#endif // !NDEBUG
}
-void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
- checkForCycles(DAG->getRoot().getNode());
+void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
+ checkForCycles(DAG->getRoot().getNode(), DAG, force);
}