switch (Result) {
default: break;
case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
+ case ISD::SETOEQ: // SETEQ & SETU[LG]E
case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
/// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
/// solely with their pointer.
-void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
+static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
ID.AddPointer(VTList.VTs);
}
assert(MVT::isInteger(VT) && "Invalid VT!");
unsigned VTBits = MVT::getSizeInBits(VT);
unsigned Tmp, Tmp2;
+ unsigned FirstAnswer = 1;
if (Depth == 6)
return 1; // Limit search depth.
case ISD::AND:
case ISD::OR:
case ISD::XOR: // NOT is handled here.
- // Logical binary ops preserve the number of sign bits.
+ // Logical binary ops preserve the number of sign bits at the worst.
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);
+ if (Tmp != 1) {
+ Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
+ 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.
+ }
+ break;
case ISD::SELECT:
- Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
+ Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
if (Tmp == 1) return 1; // Early out.
- Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
+ Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
return std::min(Tmp, Tmp2);
case ISD::SETCC:
Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
Op.getOpcode() == ISD::INTRINSIC_VOID) {
unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth);
- if (NumBits > 1) return NumBits;
+ if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
}
// Finally, if we can prove that the top bits of the result are 0's or 1's,
Mask = KnownOne;
} else {
// Nothing known.
- return 1;
+ return FirstAnswer;
}
// Okay, we know that the sign bit in Mask is set. Use CLZ to determine
Mask <<= Mask.getBitWidth()-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, Mask.countLeadingZeros());
+ return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
}
}
+/// getShuffleScalarElt - Returns the scalar element that will make up the ith
+/// element of the result of the vector shuffle.
+SDOperand SelectionDAG::getShuffleScalarElt(const SDNode *N, unsigned Idx) {
+ MVT::ValueType VT = N->getValueType(0);
+ SDOperand PermMask = N->getOperand(2);
+ unsigned NumElems = PermMask.getNumOperands();
+ SDOperand V = (Idx < NumElems) ? N->getOperand(0) : N->getOperand(1);
+ Idx %= NumElems;
+
+ if (V.getOpcode() == ISD::BIT_CONVERT) {
+ V = V.getOperand(0);
+ if (MVT::getVectorNumElements(V.getValueType()) != NumElems)
+ return SDOperand();
+ }
+ if (V.getOpcode() == ISD::SCALAR_TO_VECTOR)
+ return (Idx == 0) ? V.getOperand(0)
+ : getNode(ISD::UNDEF, MVT::getVectorElementType(VT));
+ if (V.getOpcode() == ISD::BUILD_VECTOR)
+ return V.getOperand(Idx);
+ if (V.getOpcode() == ISD::VECTOR_SHUFFLE) {
+ SDOperand Elt = PermMask.getOperand(Idx);
+ if (Elt.getOpcode() == ISD::UNDEF)
+ return getNode(ISD::UNDEF, MVT::getVectorElementType(VT));
+ return getShuffleScalarElt(V.Val,cast<ConstantSDNode>(Elt)->getValue());
+ }
+ return SDOperand();
+}
+
+
/// getNode - Gets or creates the specified node.
///
SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
/// operand.
static SDOperand getMemsetValue(SDOperand Value, MVT::ValueType VT,
SelectionDAG &DAG) {
- MVT::ValueType CurVT = VT;
+ unsigned NumBits = MVT::isVector(VT) ?
+ MVT::getSizeInBits(MVT::getVectorElementType(VT)) : MVT::getSizeInBits(VT);
if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
- uint64_t Val = C->getValue() & 255;
+ APInt Val = APInt(NumBits, C->getValue() & 255);
unsigned Shift = 8;
- while (CurVT != MVT::i8) {
+ for (unsigned i = NumBits; i > 8; i >>= 1) {
Val = (Val << Shift) | Val;
Shift <<= 1;
- CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
- }
- return DAG.getConstant(Val, VT);
- } else {
- Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value);
- unsigned Shift = 8;
- while (CurVT != MVT::i8) {
- Value =
- DAG.getNode(ISD::OR, VT,
- DAG.getNode(ISD::SHL, VT, Value,
- DAG.getConstant(Shift, MVT::i8)), Value);
- Shift <<= 1;
- CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
}
+ if (MVT::isInteger(VT))
+ return DAG.getConstant(Val, VT);
+ return DAG.getConstantFP(APFloat(Val), VT);
+ }
- return Value;
+ Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value);
+ unsigned Shift = 8;
+ for (unsigned i = NumBits; i > 8; i >>= 1) {
+ Value = DAG.getNode(ISD::OR, VT,
+ DAG.getNode(ISD::SHL, VT, Value,
+ DAG.getConstant(Shift, MVT::i8)), Value);
+ Shift <<= 1;
}
+
+ return Value;
}
/// getMemsetStringVal - Similar to getMemsetValue. Except this is only
/// used when a memcpy is turned into a memset when the source is a constant
/// string ptr.
-static SDOperand getMemsetStringVal(MVT::ValueType VT,
- SelectionDAG &DAG,
+static SDOperand getMemsetStringVal(MVT::ValueType VT, SelectionDAG &DAG,
const TargetLowering &TLI,
std::string &Str, unsigned Offset) {
+ assert(!MVT::isVector(VT) && "Can't handle vector type here!");
+ unsigned NumBits = MVT::getSizeInBits(VT);
+ unsigned MSB = NumBits / 8;
uint64_t Val = 0;
- unsigned MSB = MVT::getSizeInBits(VT) / 8;
if (TLI.isLittleEndian())
Offset = Offset + MSB - 1;
for (unsigned i = 0; i != MSB; ++i) {
}
/// getMemBasePlusOffset - Returns base and offset node for the
+///
static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset,
SelectionDAG &DAG) {
MVT::ValueType VT = Base.getValueType();
return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT));
}
+/// isMemSrcFromString - Returns true if memcpy source is a string constant.
+///
+static bool isMemSrcFromString(SDOperand Src, std::string &Str,
+ uint64_t &SrcOff) {
+ unsigned SrcDelta = 0;
+ GlobalAddressSDNode *G = NULL;
+ if (Src.getOpcode() == ISD::GlobalAddress)
+ G = cast<GlobalAddressSDNode>(Src);
+ else if (Src.getOpcode() == ISD::ADD &&
+ Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
+ Src.getOperand(1).getOpcode() == ISD::Constant) {
+ G = cast<GlobalAddressSDNode>(Src.getOperand(0));
+ SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getValue();
+ }
+ if (!G)
+ return false;
+
+ GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal());
+ if (GV && GV->isConstant()) {
+ Str = GV->getStringValue(false);
+ if (!Str.empty()) {
+ SrcOff += SrcDelta;
+ return true;
+ }
+ }
+
+ return false;
+}
+
/// MeetsMaxMemopRequirement - Determines if the number of memory ops required
/// to replace the memset / memcpy is below the threshold. It also returns the
/// types of the sequence of memory ops to perform memset / memcpy.
-static bool MeetsMaxMemopRequirement(std::vector<MVT::ValueType> &MemOps,
- unsigned Limit, uint64_t Size,
- unsigned Align,
- const TargetLowering &TLI) {
- MVT::ValueType VT;
-
- if (TLI.allowsUnalignedMemoryAccesses()) {
- VT = MVT::i64;
- } else {
- switch (Align & 7) {
- case 0:
- VT = MVT::i64;
- break;
- case 4:
- VT = MVT::i32;
- break;
- case 2:
- VT = MVT::i16;
- break;
- default:
- VT = MVT::i8;
- break;
+static
+bool MeetsMaxMemopRequirement(std::vector<MVT::ValueType> &MemOps,
+ SDOperand Dst, SDOperand Src,
+ unsigned Limit, uint64_t Size, unsigned &Align,
+ SelectionDAG &DAG,
+ const TargetLowering &TLI) {
+ bool AllowUnalign = TLI.allowsUnalignedMemoryAccesses();
+
+ std::string Str;
+ uint64_t SrcOff = 0;
+ bool isSrcStr = isMemSrcFromString(Src, Str, SrcOff);
+ bool isSrcConst = isa<ConstantSDNode>(Src);
+ MVT::ValueType VT= TLI.getOptimalMemOpType(Size, Align, isSrcConst, isSrcStr);
+ if (VT != MVT::iAny) {
+ unsigned NewAlign = (unsigned)
+ TLI.getTargetData()->getABITypeAlignment(MVT::getTypeForValueType(VT));
+ // If source is a string constant, this will require an unaligned load.
+ if (NewAlign > Align && (isSrcConst || AllowUnalign)) {
+ if (Dst.getOpcode() != ISD::FrameIndex) {
+ // Can't change destination alignment. It requires a unaligned store.
+ if (AllowUnalign)
+ VT = MVT::iAny;
+ } else {
+ int FI = cast<FrameIndexSDNode>(Dst)->getIndex();
+ MachineFrameInfo *MFI = DAG.getMachineFunction().getFrameInfo();
+ if (MFI->isFixedObjectIndex(FI)) {
+ // Can't change destination alignment. It requires a unaligned store.
+ if (AllowUnalign)
+ VT = MVT::iAny;
+ } else {
+ // Give the stack frame object a larger alignment.
+ MFI->setObjectAlignment(FI, NewAlign);
+ Align = NewAlign;
+ }
+ }
}
}
- MVT::ValueType LVT = MVT::i64;
- while (!TLI.isTypeLegal(LVT))
- LVT = (MVT::ValueType)((unsigned)LVT - 1);
- assert(MVT::isInteger(LVT));
+ if (VT == MVT::iAny) {
+ if (AllowUnalign) {
+ VT = MVT::i64;
+ } else {
+ switch (Align & 7) {
+ case 0: VT = MVT::i64; break;
+ case 4: VT = MVT::i32; break;
+ case 2: VT = MVT::i16; break;
+ default: VT = MVT::i8; break;
+ }
+ }
- if (VT > LVT)
- VT = LVT;
+ MVT::ValueType LVT = MVT::i64;
+ while (!TLI.isTypeLegal(LVT))
+ LVT = (MVT::ValueType)((unsigned)LVT - 1);
+ assert(MVT::isInteger(LVT));
+
+ if (VT > LVT)
+ VT = LVT;
+ }
unsigned NumMemOps = 0;
while (Size != 0) {
unsigned VTSize = MVT::getSizeInBits(VT) / 8;
while (VTSize > Size) {
- VT = (MVT::ValueType)((unsigned)VT - 1);
- VTSize >>= 1;
+ // For now, only use non-vector load / store's for the left-over pieces.
+ if (MVT::isVector(VT)) {
+ VT = MVT::i64;
+ while (!TLI.isTypeLegal(VT))
+ VT = (MVT::ValueType)((unsigned)VT - 1);
+ VTSize = MVT::getSizeInBits(VT) / 8;
+ } else {
+ VT = (MVT::ValueType)((unsigned)VT - 1);
+ VTSize >>= 1;
+ }
}
- assert(MVT::isInteger(VT));
if (++NumMemOps > Limit)
return false;
static SDOperand getMemcpyLoadsAndStores(SelectionDAG &DAG,
SDOperand Chain, SDOperand Dst,
SDOperand Src, uint64_t Size,
- unsigned Align,
- bool AlwaysInline,
+ unsigned Align, bool AlwaysInline,
const Value *DstSV, uint64_t DstSVOff,
const Value *SrcSV, uint64_t SrcSVOff){
const TargetLowering &TLI = DAG.getTargetLoweringInfo();
- // Expand memcpy to a series of store ops if the size operand falls below
- // a certain threshold.
+ // Expand memcpy to a series of load and store ops if the size operand falls
+ // below a certain threshold.
std::vector<MVT::ValueType> MemOps;
uint64_t Limit = -1;
if (!AlwaysInline)
Limit = TLI.getMaxStoresPerMemcpy();
- if (!MeetsMaxMemopRequirement(MemOps, Limit, Size, Align, TLI))
+ unsigned DstAlign = Align; // Destination alignment can change.
+ if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, Limit, Size, DstAlign,
+ DAG, TLI))
return SDOperand();
- SmallVector<SDOperand, 8> OutChains;
-
- unsigned NumMemOps = MemOps.size();
- unsigned SrcDelta = 0;
- GlobalAddressSDNode *G = NULL;
std::string Str;
- bool CopyFromStr = false;
uint64_t SrcOff = 0, DstOff = 0;
+ bool CopyFromStr = isMemSrcFromString(Src, Str, SrcOff);
- if (Src.getOpcode() == ISD::GlobalAddress)
- G = cast<GlobalAddressSDNode>(Src);
- else if (Src.getOpcode() == ISD::ADD &&
- Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
- Src.getOperand(1).getOpcode() == ISD::Constant) {
- G = cast<GlobalAddressSDNode>(Src.getOperand(0));
- SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getValue();
- }
- if (G) {
- GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal());
- if (GV && GV->isConstant()) {
- Str = GV->getStringValue(false);
- if (!Str.empty()) {
- CopyFromStr = true;
- SrcOff += SrcDelta;
- }
- }
- }
-
+ SmallVector<SDOperand, 8> OutChains;
+ unsigned NumMemOps = MemOps.size();
for (unsigned i = 0; i < NumMemOps; i++) {
MVT::ValueType VT = MemOps[i];
unsigned VTSize = MVT::getSizeInBits(VT) / 8;
SDOperand Value, Store;
- if (CopyFromStr) {
+ if (CopyFromStr && !MVT::isVector(VT)) {
+ // It's unlikely a store of a vector immediate can be done in a single
+ // instruction. It would require a load from a constantpool first.
+ // FIXME: Handle cases where store of vector immediate is done in a
+ // single instruction.
Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff);
- Store =
- DAG.getStore(Chain, Value,
- getMemBasePlusOffset(Dst, DstOff, DAG),
- DstSV, DstSVOff + DstOff);
+ Store = DAG.getStore(Chain, Value,
+ getMemBasePlusOffset(Dst, DstOff, DAG),
+ DstSV, DstSVOff + DstOff);
} else {
Value = DAG.getLoad(VT, Chain,
getMemBasePlusOffset(Src, SrcOff, DAG),
SrcSV, SrcSVOff + SrcOff, false, Align);
- Store =
- DAG.getStore(Chain, Value,
- getMemBasePlusOffset(Dst, DstOff, DAG),
- DstSV, DstSVOff + DstOff, false, Align);
+ Store = DAG.getStore(Chain, Value,
+ getMemBasePlusOffset(Dst, DstOff, DAG),
+ DstSV, DstSVOff + DstOff, false, DstAlign);
}
OutChains.push_back(Store);
SrcOff += VTSize;
&OutChains[0], OutChains.size());
}
+static SDOperand getMemmoveLoadsAndStores(SelectionDAG &DAG,
+ SDOperand Chain, SDOperand Dst,
+ SDOperand Src, uint64_t Size,
+ unsigned Align, bool AlwaysInline,
+ const Value *DstSV, uint64_t DstSVOff,
+ const Value *SrcSV, uint64_t SrcSVOff){
+ const TargetLowering &TLI = DAG.getTargetLoweringInfo();
+
+ // Expand memmove to a series of load and store ops if the size operand falls
+ // below a certain threshold.
+ std::vector<MVT::ValueType> MemOps;
+ uint64_t Limit = -1;
+ if (!AlwaysInline)
+ Limit = TLI.getMaxStoresPerMemmove();
+ unsigned DstAlign = Align; // Destination alignment can change.
+ if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, Limit, Size, DstAlign,
+ DAG, TLI))
+ return SDOperand();
+
+ std::string Str;
+ uint64_t SrcOff = 0, DstOff = 0;
+
+ SmallVector<SDOperand, 8> LoadValues;
+ SmallVector<SDOperand, 8> LoadChains;
+ SmallVector<SDOperand, 8> OutChains;
+ unsigned NumMemOps = MemOps.size();
+ for (unsigned i = 0; i < NumMemOps; i++) {
+ MVT::ValueType VT = MemOps[i];
+ unsigned VTSize = MVT::getSizeInBits(VT) / 8;
+ SDOperand Value, Store;
+
+ Value = DAG.getLoad(VT, Chain,
+ getMemBasePlusOffset(Src, SrcOff, DAG),
+ SrcSV, SrcSVOff + SrcOff, false, Align);
+ LoadValues.push_back(Value);
+ LoadChains.push_back(Value.getValue(1));
+ SrcOff += VTSize;
+ }
+ Chain = DAG.getNode(ISD::TokenFactor, MVT::Other,
+ &LoadChains[0], LoadChains.size());
+ OutChains.clear();
+ for (unsigned i = 0; i < NumMemOps; i++) {
+ MVT::ValueType VT = MemOps[i];
+ unsigned VTSize = MVT::getSizeInBits(VT) / 8;
+ SDOperand Value, Store;
+
+ Store = DAG.getStore(Chain, LoadValues[i],
+ getMemBasePlusOffset(Dst, DstOff, DAG),
+ DstSV, DstSVOff + DstOff, false, DstAlign);
+ OutChains.push_back(Store);
+ DstOff += VTSize;
+ }
+
+ return DAG.getNode(ISD::TokenFactor, MVT::Other,
+ &OutChains[0], OutChains.size());
+}
+
static SDOperand getMemsetStores(SelectionDAG &DAG,
SDOperand Chain, SDOperand Dst,
SDOperand Src, uint64_t Size,
// Expand memset to a series of load/store ops if the size operand
// falls below a certain threshold.
std::vector<MVT::ValueType> MemOps;
- if (!MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemset(),
- Size, Align, TLI))
+ if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, TLI.getMaxStoresPerMemset(),
+ Size, Align, DAG, TLI))
return SDOperand();
SmallVector<SDOperand, 8> OutChains;
const Value *DstSV, uint64_t DstSVOff,
const Value *SrcSV, uint64_t SrcSVOff) {
- // TODO: Optimize small memmove cases with simple loads and stores,
- // ensuring that all loads precede all stores. This can cause severe
- // register pressure, so targets should be careful with the size limit.
+ // Check to see if we should lower the memmove to loads and stores first.
+ // For cases within the target-specified limits, this is the best choice.
+ ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
+ if (ConstantSize) {
+ // Memmove with size zero? Just return the original chain.
+ if (ConstantSize->isNullValue())
+ return Chain;
+
+ SDOperand Result =
+ getMemmoveLoadsAndStores(*this, Chain, Dst, Src, ConstantSize->getValue(),
+ Align, false, DstSV, DstSVOff, SrcSV, SrcSVOff);
+ if (Result.Val)
+ return Result;
+ }
// Then check to see if we should lower the memmove with target-specific
// code. If the target chooses to do this, this is the next best.
}
bool Indexed = AM != ISD::UNINDEXED;
- assert(Indexed || Offset.getOpcode() == ISD::UNDEF &&
+ assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
"Unindexed load with an offset!");
SDVTList VTs = Indexed ?