X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FSelectionDAG.cpp;h=758f112f78c6e83e4318b50f7c67da32ed994792;hb=ee4c619b3b28a42078fc8033e5dccd42fc6edd42;hp=1bada5eea2ec0dd2bfc86bce1a0ff3afe407e6a8;hpb=dc71563794a6a30f66278af5a9cdccde36b1797e;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp index 1bada5eea2e..758f112f78c 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -29,6 +29,7 @@ #include "llvm/Target/TargetLowering.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" #include "llvm/ADT/SetVector.h" @@ -69,7 +70,7 @@ SelectionDAG::DAGUpdateListener::~DAGUpdateListener() {} /// As such, this method can be used to do an exact bit-for-bit comparison of /// two floating point values. bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const { - return Value.bitwiseIsEqual(V); + return getValueAPF().bitwiseIsEqual(V); } bool ConstantFPSDNode::isValueValidForType(MVT VT, @@ -83,8 +84,10 @@ bool ConstantFPSDNode::isValueValidForType(MVT VT, // convert modifies in place, so make a copy. APFloat Val2 = APFloat(Val); - return Val2.convert(*MVTToAPFloatSemantics(VT), - APFloat::rmNearestTiesToEven) == APFloat::opOK; + bool losesInfo; + (void) Val2.convert(*MVTToAPFloatSemantics(VT), APFloat::rmNearestTiesToEven, + &losesInfo); + return !losesInfo; } //===----------------------------------------------------------------------===// @@ -117,7 +120,7 @@ bool ISD::isBuildVectorAllOnes(const SDNode *N) { return false; } else if (isa(NotZero)) { if (!cast(NotZero)->getValueAPF(). - convertToAPInt().isAllOnesValue()) + bitcastToAPInt().isAllOnesValue()) return false; } else return false; @@ -213,7 +216,7 @@ ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) { unsigned OldG = (Operation >> 1) & 1; return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits (OldL << 1) | // New G bit - (OldG << 2)); // New L bit. + (OldG << 2)); // New L bit. } /// getSetCCInverse - Return the operation corresponding to !(X op Y), where @@ -224,8 +227,10 @@ ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) { Operation ^= 7; // Flip L, G, E bits, but not U. else Operation ^= 15; // Flip all of the condition bits. + if (Operation > ISD::SETTRUE2) - Operation &= ~8; // Don't let N and U bits get set. + Operation &= ~8; // Don't let N and U bits get set. + return ISD::CondCode(Operation); } @@ -302,7 +307,7 @@ ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2, } const TargetMachine &SelectionDAG::getTarget() const { - return TLI.getTargetMachine(); + return MF->getTarget(); } //===----------------------------------------------------------------------===// @@ -367,11 +372,11 @@ static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) { break; case ISD::TargetConstant: case ISD::Constant: - ID.Add(cast(N)->getAPIntValue()); + ID.AddPointer(cast(N)->getConstantIntValue()); break; case ISD::TargetConstantFP: case ISD::ConstantFP: { - ID.Add(cast(N)->getValueAPF()); + ID.AddPointer(cast(N)->getConstantFPValue()); break; } case ISD::TargetGlobalAddress: @@ -423,6 +428,12 @@ static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) { ID.AddPointer(CP->getConstVal()); break; } + case ISD::CALL: { + const CallSDNode *Call = cast(N); + ID.AddInteger(Call->getCallingConv()); + ID.AddInteger(Call->isVarArg()); + break; + } case ISD::LOAD: { const LoadSDNode *LD = cast(N); ID.AddInteger(LD->getAddressingMode()); @@ -497,7 +508,8 @@ static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) { /// encodeMemSDNodeFlags - Generic routine for computing a value for use in /// the CSE map that carries both alignment and volatility information. /// -static unsigned encodeMemSDNodeFlags(bool isVolatile, unsigned Alignment) { +static inline unsigned +encodeMemSDNodeFlags(bool isVolatile, unsigned Alignment) { return isVolatile | ((Log2_32(Alignment) + 1) << 1); } @@ -552,9 +564,10 @@ void SelectionDAG::RemoveDeadNodes(SmallVectorImpl &DeadNodes, if (Operand->use_empty()) DeadNodes.push_back(Operand); } - if (N->OperandsNeedDelete) { + + if (N->OperandsNeedDelete) delete[] N->OperandList; - } + N->OperandList = 0; N->NumOperands = 0; @@ -580,12 +593,14 @@ void SelectionDAG::DeleteNode(SDNode *N) { } void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) { - - // Drop all of the operands and decrement used nodes use counts. + // Drop all of the operands and decrement used node's use counts. for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) I->getVal()->removeUser(std::distance(N->op_begin(), I), N); - if (N->OperandsNeedDelete) + + if (N->OperandsNeedDelete) { delete[] N->OperandList; + N->OperandList = 0; + } assert(N != AllNodes.begin()); NodeAllocator.Deallocate(AllNodes.remove(N)); @@ -595,13 +610,13 @@ void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) { /// correspond to it. This is useful when we're about to delete or repurpose /// the node. We don't want future request for structurally identical nodes /// to return N anymore. -void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { +bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { bool Erased = false; switch (N->getOpcode()) { case ISD::EntryToken: assert(0 && "EntryToken should not be in CSEMaps!"); - return; - case ISD::HANDLENODE: return; // noop. + return false; + case ISD::HANDLENODE: return false; // noop. case ISD::CONDCODE: assert(CondCodeNodes[cast(N)->get()] && "Cond code doesn't exist!"); @@ -635,7 +650,7 @@ void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { // flag result (which cannot be CSE'd) or is one of the special cases that are // not subject to CSE. if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag && - !N->isTargetOpcode() && + !N->isMachineOpcode() && N->getOpcode() != ISD::DBG_LABEL && N->getOpcode() != ISD::DBG_STOPPOINT && N->getOpcode() != ISD::EH_LABEL && @@ -645,6 +660,7 @@ void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { assert(0 && "Node is not in map!"); } #endif + return Erased; } /// AddNonLeafNodeToCSEMaps - Add the specified node back to the CSE maps. It @@ -665,13 +681,13 @@ SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) { case ISD::DBG_STOPPOINT: case ISD::EH_LABEL: case ISD::DECLARE: - return 0; // Never add these nodes. + return 0; // Never add these nodes. } // Check that remaining values produced are not flags. for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) if (N->getValueType(i) == MVT::Flag) - return 0; // Never CSE anything that produces a flag. + return 0; // Never CSE anything that produces a flag. SDNode *New = CSEMap.GetOrInsertNode(N); if (New != N) return New; // Node already existed. @@ -693,13 +709,13 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op, case ISD::DBG_LABEL: case ISD::DBG_STOPPOINT: case ISD::EH_LABEL: - return 0; // Never add these nodes. + return 0; // Never add these nodes. } // Check that remaining values produced are not flags. for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) if (N->getValueType(i) == MVT::Flag) - return 0; // Never CSE anything that produces a flag. + return 0; // Never CSE anything that produces a flag. SDValue Ops[] = { Op }; FoldingSetNodeID ID; @@ -719,7 +735,7 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, // Check that remaining values produced are not flags. for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) if (N->getValueType(i) == MVT::Flag) - return 0; // Never CSE anything that produces a flag. + return 0; // Never CSE anything that produces a flag. SDValue Ops[] = { Op1, Op2 }; FoldingSetNodeID ID; @@ -745,13 +761,13 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, case ISD::DBG_STOPPOINT: case ISD::EH_LABEL: case ISD::DECLARE: - return 0; // Never add these nodes. + return 0; // Never add these nodes. } // Check that remaining values produced are not flags. for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) if (N->getValueType(i) == MVT::Flag) - return 0; // Never CSE anything that produces a flag. + return 0; // Never CSE anything that produces a flag. FoldingSetNodeID ID; AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps); @@ -781,10 +797,14 @@ void SelectionDAG::VerifyNode(SDNode *N) { assert(N->getValueType(0).isVector() && "Wrong BUILD_VECTOR return type!"); assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() && "Wrong number of BUILD_VECTOR operands!"); - MVT EltVT = N->getValueType(0).getVectorElementType(); - for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) - assert(I->getSDValue().getValueType() == EltVT && - "Wrong BUILD_VECTOR operand type!"); + // FIXME: Change vector_shuffle to a variadic node with mask elements being + // operands of the node. Currently the mask is a BUILD_VECTOR passed as an + // operand, and it is not always possible to legalize it. Turning off the + // following checks at least makes it possible to legalize most of the time. +// MVT EltVT = N->getValueType(0).getVectorElementType(); +// for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) +// assert(I->getSDValue().getValueType() == EltVT && +// "Wrong BUILD_VECTOR operand type!"); break; } } @@ -823,8 +843,12 @@ void SelectionDAG::allnodes_clear() { while (!AllNodes.empty()) { SDNode *N = AllNodes.remove(AllNodes.begin()); N->SetNextInBucket(0); - if (N->OperandsNeedDelete) + + if (N->OperandsNeedDelete) { delete [] N->OperandList; + N->OperandList = 0; + } + NodeAllocator.Deallocate(N); } } @@ -861,6 +885,10 @@ SDValue SelectionDAG::getConstant(uint64_t Val, MVT VT, bool isT) { } SDValue SelectionDAG::getConstant(const APInt &Val, MVT VT, bool isT) { + return getConstant(*ConstantInt::get(Val), VT, isT); +} + +SDValue SelectionDAG::getConstant(const ConstantInt &Val, MVT VT, bool isT) { assert(VT.isInteger() && "Cannot create FP integer constant!"); MVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT; @@ -870,7 +898,7 @@ SDValue SelectionDAG::getConstant(const APInt &Val, MVT VT, bool isT) { unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant; FoldingSetNodeID ID; AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0); - ID.Add(Val); + ID.AddPointer(&Val); void *IP = 0; SDNode *N = NULL; if ((N = CSEMap.FindNodeOrInsertPos(ID, IP))) @@ -878,7 +906,7 @@ SDValue SelectionDAG::getConstant(const APInt &Val, MVT VT, bool isT) { return SDValue(N, 0); if (!N) { N = NodeAllocator.Allocate(); - new (N) ConstantSDNode(isT, Val, EltVT); + new (N) ConstantSDNode(isT, &Val, EltVT); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); } @@ -898,6 +926,10 @@ SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) { SDValue SelectionDAG::getConstantFP(const APFloat& V, MVT VT, bool isTarget) { + return getConstantFP(*ConstantFP::get(V), VT, isTarget); +} + +SDValue SelectionDAG::getConstantFP(const ConstantFP& V, MVT VT, bool isTarget){ assert(VT.isFloatingPoint() && "Cannot create integer FP constant!"); MVT EltVT = @@ -909,7 +941,7 @@ SDValue SelectionDAG::getConstantFP(const APFloat& V, MVT VT, bool isTarget) { unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP; FoldingSetNodeID ID; AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0); - ID.Add(V); + ID.AddPointer(&V); void *IP = 0; SDNode *N = NULL; if ((N = CSEMap.FindNodeOrInsertPos(ID, IP))) @@ -917,7 +949,7 @@ SDValue SelectionDAG::getConstantFP(const APFloat& V, MVT VT, bool isTarget) { return SDValue(N, 0); if (!N) { N = NodeAllocator.Allocate(); - new (N) ConstantFPSDNode(isTarget, V, EltVT); + new (N) ConstantFPSDNode(isTarget, &V, EltVT); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); } @@ -941,15 +973,20 @@ SDValue SelectionDAG::getConstantFP(double Val, MVT VT, bool isTarget) { } SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, - MVT VT, int Offset, + MVT VT, int64_t Offset, bool isTargetGA) { unsigned Opc; + // Truncate (with sign-extension) the offset value to the pointer size. + unsigned BitWidth = TLI.getPointerTy().getSizeInBits(); + if (BitWidth < 64) + Offset = (Offset << (64 - BitWidth) >> (64 - BitWidth)); + const GlobalVariable *GVar = dyn_cast(GV); if (!GVar) { // If GV is an alias then use the aliasee for determining thread-localness. if (const GlobalAlias *GA = dyn_cast(GV)) - GVar = dyn_cast_or_null(GA->resolveAliasedGlobal()); + GVar = dyn_cast_or_null(GA->resolveAliasedGlobal(false)); } if (GVar && GVar->isThreadLocal()) @@ -1004,6 +1041,9 @@ SDValue SelectionDAG::getJumpTable(int JTI, MVT VT, bool isTarget){ SDValue SelectionDAG::getConstantPool(Constant *C, MVT VT, unsigned Alignment, int Offset, bool isTarget) { + if (Alignment == 0) + Alignment = + TLI.getTargetData()->getPreferredTypeAlignmentShift(C->getType()); unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; FoldingSetNodeID ID; AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); @@ -1024,6 +1064,9 @@ SDValue SelectionDAG::getConstantPool(Constant *C, MVT VT, SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, MVT VT, unsigned Alignment, int Offset, bool isTarget) { + if (Alignment == 0) + Alignment = + TLI.getTargetData()->getPreferredTypeAlignmentShift(C->getType()); unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; FoldingSetNodeID ID; AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); @@ -1462,7 +1505,7 @@ void SelectionDAG::ComputeMaskedBits(SDValue Op, const APInt &Mask, case ISD::SHL: // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 if (ConstantSDNode *SA = dyn_cast(Op.getOperand(1))) { - unsigned ShAmt = SA->getValue(); + unsigned ShAmt = SA->getZExtValue(); // If the shift count is an invalid immediate, don't do anything. if (ShAmt >= BitWidth) @@ -1480,7 +1523,7 @@ void SelectionDAG::ComputeMaskedBits(SDValue Op, const APInt &Mask, case ISD::SRL: // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 if (ConstantSDNode *SA = dyn_cast(Op.getOperand(1))) { - unsigned ShAmt = SA->getValue(); + unsigned ShAmt = SA->getZExtValue(); // If the shift count is an invalid immediate, don't do anything. if (ShAmt >= BitWidth) @@ -1498,7 +1541,7 @@ void SelectionDAG::ComputeMaskedBits(SDValue Op, const APInt &Mask, return; case ISD::SRA: if (ConstantSDNode *SA = dyn_cast(Op.getOperand(1))) { - unsigned ShAmt = SA->getValue(); + unsigned ShAmt = SA->getZExtValue(); // If the shift count is an invalid immediate, don't do anything. if (ShAmt >= BitWidth) @@ -1823,7 +1866,7 @@ unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{ Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); // SRA X, C -> adds C sign bits. if (ConstantSDNode *C = dyn_cast(Op.getOperand(1))) { - Tmp += C->getValue(); + Tmp += C->getZExtValue(); if (Tmp > VTBits) Tmp = VTBits; } return Tmp; @@ -1831,9 +1874,9 @@ unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{ if (ConstantSDNode *C = dyn_cast(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(); + if (C->getZExtValue() >= VTBits || // Bad shift. + C->getZExtValue() >= Tmp) break; // Shifted all sign bits out. + return Tmp - C->getZExtValue(); } break; case ISD::AND: @@ -1865,7 +1908,7 @@ unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{ case ISD::ROTL: case ISD::ROTR: if (ConstantSDNode *C = dyn_cast(Op.getOperand(1))) { - unsigned RotAmt = C->getValue() & (VTBits-1); + unsigned RotAmt = C->getZExtValue() & (VTBits-1); // Handle rotate right by N like a rotate left by 32-N. if (Op.getOpcode() == ISD::ROTR) @@ -1993,6 +2036,7 @@ unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{ bool SelectionDAG::isVerifiedDebugInfoDesc(SDValue Op) const { GlobalAddressSDNode *GA = dyn_cast(Op); if (!GA) return false; + if (GA->getOffset() != 0) return false; GlobalVariable *GV = dyn_cast(GA->getGlobal()); if (!GV) return false; MachineModuleInfo *MMI = getMachineModuleInfo(); @@ -2008,7 +2052,7 @@ SDValue SelectionDAG::getShuffleScalarElt(const SDNode *N, unsigned i) { SDValue Idx = PermMask.getOperand(i); if (Idx.getOpcode() == ISD::UNDEF) return getNode(ISD::UNDEF, VT.getVectorElementType()); - unsigned Index = cast(Idx)->getValue(); + unsigned Index = cast(Idx)->getZExtValue(); unsigned NumElems = PermMask.getNumOperands(); SDValue V = (Index < NumElems) ? N->getOperand(0) : N->getOperand(1); Index %= NumElems; @@ -2102,29 +2146,32 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, SDValue Operand) { V.clearSign(); return getConstantFP(V, VT); case ISD::FP_ROUND: - case ISD::FP_EXTEND: + case ISD::FP_EXTEND: { + bool ignored; // This can return overflow, underflow, or inexact; we don't care. // FIXME need to be more flexible about rounding mode. (void)V.convert(*MVTToAPFloatSemantics(VT), - APFloat::rmNearestTiesToEven); + APFloat::rmNearestTiesToEven, &ignored); return getConstantFP(V, VT); + } case ISD::FP_TO_SINT: case ISD::FP_TO_UINT: { integerPart x; + bool ignored; assert(integerPartWidth >= 64); // FIXME need to be more flexible about rounding mode. APFloat::opStatus s = V.convertToInteger(&x, 64U, Opcode==ISD::FP_TO_SINT, - APFloat::rmTowardZero); + APFloat::rmTowardZero, &ignored); if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual break; return getConstant(x, VT); } case ISD::BIT_CONVERT: if (VT == MVT::i32 && C->getValueType(0) == MVT::f32) - return getConstant((uint32_t)V.convertToAPInt().getZExtValue(), VT); + return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT); else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64) - return getConstant(V.convertToAPInt().getZExtValue(), VT); + return getConstant(V.bitcastToAPInt().getZExtValue(), VT); break; } } @@ -2250,6 +2297,42 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, SDValue Operand) { return SDValue(N, 0); } +SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, + MVT VT, + ConstantSDNode *Cst1, + ConstantSDNode *Cst2) { + const APInt &C1 = Cst1->getAPIntValue(), &C2 = Cst2->getAPIntValue(); + + switch (Opcode) { + case ISD::ADD: return getConstant(C1 + C2, VT); + case ISD::SUB: return getConstant(C1 - C2, VT); + case ISD::MUL: return getConstant(C1 * C2, VT); + case ISD::UDIV: + if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT); + break; + case ISD::UREM: + if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT); + break; + case ISD::SDIV: + if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT); + break; + case ISD::SREM: + if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT); + break; + case ISD::AND: return getConstant(C1 & C2, VT); + case ISD::OR: return getConstant(C1 | C2, VT); + case ISD::XOR: return getConstant(C1 ^ C2, VT); + case ISD::SHL: return getConstant(C1 << C2, VT); + case ISD::SRL: return getConstant(C1.lshr(C2), VT); + case ISD::SRA: return getConstant(C1.ashr(C2), VT); + case ISD::ROTL: return getConstant(C1.rotl(C2), VT); + case ISD::ROTR: return getConstant(C1.rotr(C2), VT); + default: break; + } + + return SDValue(); +} + SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, SDValue N1, SDValue N2) { ConstantSDNode *N1C = dyn_cast(N1.getNode()); @@ -2262,6 +2345,7 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, // Fold trivial token factors. if (N1.getOpcode() == ISD::EntryToken) return N2; if (N2.getOpcode() == ISD::EntryToken) return N1; + if (N1 == N2) return N1; break; case ISD::CONCAT_VECTORS: // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to @@ -2389,14 +2473,15 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, unsigned Factor = N1.getOperand(0).getValueType().getVectorNumElements(); return getNode(ISD::EXTRACT_VECTOR_ELT, VT, - N1.getOperand(N2C->getValue() / Factor), - getConstant(N2C->getValue() % Factor, N2.getValueType())); + N1.getOperand(N2C->getZExtValue() / Factor), + getConstant(N2C->getZExtValue() % Factor, + N2.getValueType())); } // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is // expanding large vector constants. if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) - return N1.getOperand(N2C->getValue()); + return N1.getOperand(N2C->getZExtValue()); // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector // operations are lowered to scalars. @@ -2408,7 +2493,7 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, } break; case ISD::EXTRACT_ELEMENT: - assert(N2C && (unsigned)N2C->getValue() < 2 && "Bad EXTRACT_ELEMENT!"); + assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!"); assert(!N1.getValueType().isVector() && !VT.isVector() && (N1.getValueType().isInteger() == VT.isInteger()) && "Wrong types for EXTRACT_ELEMENT!"); @@ -2417,12 +2502,12 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, // 64-bit integers into 32-bit parts. Instead of building the extract of // the BUILD_PAIR, only to have legalize rip it apart, just do it now. if (N1.getOpcode() == ISD::BUILD_PAIR) - return N1.getOperand(N2C->getValue()); + return N1.getOperand(N2C->getZExtValue()); // EXTRACT_ELEMENT of a constant int is also very common. if (ConstantSDNode *C = dyn_cast(N1)) { unsigned ElementSize = VT.getSizeInBits(); - unsigned Shift = ElementSize * N2C->getValue(); + unsigned Shift = ElementSize * N2C->getZExtValue(); APInt ShiftedVal = C->getAPIntValue().lshr(Shift); return getConstant(ShiftedVal.trunc(ElementSize), VT); } @@ -2435,33 +2520,8 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, if (N1C) { if (N2C) { - const APInt &C1 = N1C->getAPIntValue(), &C2 = N2C->getAPIntValue(); - switch (Opcode) { - case ISD::ADD: return getConstant(C1 + C2, VT); - case ISD::SUB: return getConstant(C1 - C2, VT); - case ISD::MUL: return getConstant(C1 * C2, VT); - case ISD::UDIV: - if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT); - break; - case ISD::UREM : - if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT); - break; - case ISD::SDIV : - if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT); - break; - case ISD::SREM : - if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT); - break; - case ISD::AND : return getConstant(C1 & C2, VT); - case ISD::OR : return getConstant(C1 | C2, VT); - case ISD::XOR : return getConstant(C1 ^ C2, VT); - case ISD::SHL : return getConstant(C1 << C2, VT); - case ISD::SRL : return getConstant(C1.lshr(C2), VT); - case ISD::SRA : return getConstant(C1.ashr(C2), VT); - case ISD::ROTL : return getConstant(C1.rotl(C2), VT); - case ISD::ROTR : return getConstant(C1.rotr(C2), VT); - default: break; - } + SDValue SV = FoldConstantArithmetic(Opcode, VT, N1C, N2C); + if (SV.getNode()) return SV; } else { // Cannonicalize constant to RHS if commutative if (isCommutativeBinOp(Opcode)) { std::swap(N1C, N2C); @@ -2638,7 +2698,7 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, } case ISD::SELECT: if (N1C) { - if (N1C->getValue()) + if (N1C->getZExtValue()) return N2; // select true, X, Y -> X else return N3; // select false, X, Y -> Y @@ -2648,7 +2708,7 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, break; case ISD::BRCOND: if (N2C) { - if (N2C->getValue()) // Unconditional branch + if (N2C->getZExtValue()) // Unconditional branch return getNode(ISD::BR, MVT::Other, N1, N3); else return N1; // Never-taken branch @@ -2712,7 +2772,7 @@ static SDValue getMemsetValue(SDValue Value, MVT VT, SelectionDAG &DAG) { unsigned NumBits = VT.isVector() ? VT.getVectorElementType().getSizeInBits() : VT.getSizeInBits(); if (ConstantSDNode *C = dyn_cast(Value)) { - APInt Val = APInt(NumBits, C->getValue() & 255); + APInt Val = APInt(NumBits, C->getZExtValue() & 255); unsigned Shift = 8; for (unsigned i = NumBits; i > 8; i >>= 1) { Val = (Val << Shift) | Val; @@ -2783,7 +2843,7 @@ static bool isMemSrcFromString(SDValue Src, std::string &Str) { Src.getOperand(0).getOpcode() == ISD::GlobalAddress && Src.getOperand(1).getOpcode() == ISD::Constant) { G = cast(Src.getOperand(0)); - SrcDelta = cast(Src.getOperand(1))->getValue(); + SrcDelta = cast(Src.getOperand(1))->getZExtValue(); } if (!G) return false; @@ -2892,7 +2952,7 @@ static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, // Expand memcpy to a series of load and store ops if the size operand falls // below a certain threshold. std::vector MemOps; - uint64_t Limit = -1; + uint64_t Limit = -1ULL; if (!AlwaysInline) Limit = TLI.getMaxStoresPerMemcpy(); unsigned DstAlign = Align; // Destination alignment can change. @@ -2950,7 +3010,7 @@ static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, // Expand memmove to a series of load and store ops if the size operand falls // below a certain threshold. std::vector MemOps; - uint64_t Limit = -1; + uint64_t Limit = -1ULL; if (!AlwaysInline) Limit = TLI.getMaxStoresPerMemmove(); unsigned DstAlign = Align; // Destination alignment can change. @@ -3047,7 +3107,8 @@ SDValue SelectionDAG::getMemcpy(SDValue Chain, SDValue Dst, return Chain; SDValue Result = - getMemcpyLoadsAndStores(*this, Chain, Dst, Src, ConstantSize->getValue(), + getMemcpyLoadsAndStores(*this, Chain, Dst, Src, + ConstantSize->getZExtValue(), Align, false, DstSV, DstSVOff, SrcSV, SrcSVOff); if (Result.getNode()) return Result; @@ -3067,7 +3128,7 @@ SDValue SelectionDAG::getMemcpy(SDValue Chain, SDValue Dst, if (AlwaysInline) { assert(ConstantSize && "AlwaysInline requires a constant size!"); return getMemcpyLoadsAndStores(*this, Chain, Dst, Src, - ConstantSize->getValue(), Align, true, + ConstantSize->getZExtValue(), Align, true, DstSV, DstSVOff, SrcSV, SrcSVOff); } @@ -3080,7 +3141,7 @@ SDValue SelectionDAG::getMemcpy(SDValue Chain, SDValue Dst, Entry.Node = Size; Args.push_back(Entry); std::pair CallResult = TLI.LowerCallTo(Chain, Type::VoidTy, - false, false, false, CallingConv::C, false, + false, false, false, false, CallingConv::C, false, getExternalSymbol("memcpy", TLI.getPointerTy()), Args, *this); return CallResult.second; @@ -3101,7 +3162,8 @@ SDValue SelectionDAG::getMemmove(SDValue Chain, SDValue Dst, return Chain; SDValue Result = - getMemmoveLoadsAndStores(*this, Chain, Dst, Src, ConstantSize->getValue(), + getMemmoveLoadsAndStores(*this, Chain, Dst, Src, + ConstantSize->getZExtValue(), Align, false, DstSV, DstSVOff, SrcSV, SrcSVOff); if (Result.getNode()) return Result; @@ -3124,7 +3186,7 @@ SDValue SelectionDAG::getMemmove(SDValue Chain, SDValue Dst, Entry.Node = Size; Args.push_back(Entry); std::pair CallResult = TLI.LowerCallTo(Chain, Type::VoidTy, - false, false, false, CallingConv::C, false, + false, false, false, false, CallingConv::C, false, getExternalSymbol("memmove", TLI.getPointerTy()), Args, *this); return CallResult.second; @@ -3144,8 +3206,8 @@ SDValue SelectionDAG::getMemset(SDValue Chain, SDValue Dst, return Chain; SDValue Result = - getMemsetStores(*this, Chain, Dst, Src, ConstantSize->getValue(), Align, - DstSV, DstSVOff); + getMemsetStores(*this, Chain, Dst, Src, ConstantSize->getZExtValue(), + Align, DstSV, DstSVOff); if (Result.getNode()) return Result; } @@ -3175,7 +3237,7 @@ SDValue SelectionDAG::getMemset(SDValue Chain, SDValue Dst, Args.push_back(Entry); std::pair CallResult = TLI.LowerCallTo(Chain, Type::VoidTy, - false, false, false, CallingConv::C, false, + false, false, false, false, CallingConv::C, false, getExternalSymbol("memset", TLI.getPointerTy()), Args, *this); return CallResult.second; @@ -3292,6 +3354,71 @@ SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps, return getNode(ISD::MERGE_VALUES, getVTList(&VTs[0], NumOps), Ops, NumOps); } +SDValue +SelectionDAG::getMemIntrinsicNode(unsigned Opcode, + const MVT *VTs, unsigned NumVTs, + const SDValue *Ops, unsigned NumOps, + MVT MemVT, const Value *srcValue, int SVOff, + unsigned Align, bool Vol, + bool ReadMem, bool WriteMem) { + return getMemIntrinsicNode(Opcode, makeVTList(VTs, NumVTs), Ops, NumOps, + MemVT, srcValue, SVOff, Align, Vol, + ReadMem, WriteMem); +} + +SDValue +SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDVTList VTList, + const SDValue *Ops, unsigned NumOps, + MVT MemVT, const Value *srcValue, int SVOff, + unsigned Align, bool Vol, + bool ReadMem, bool WriteMem) { + // Memoize the node unless it returns a flag. + MemIntrinsicSDNode *N; + if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) { + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDValue(E, 0); + + N = NodeAllocator.Allocate(); + new (N) MemIntrinsicSDNode(Opcode, VTList, Ops, NumOps, MemVT, + srcValue, SVOff, Align, Vol, ReadMem, WriteMem); + CSEMap.InsertNode(N, IP); + } else { + N = NodeAllocator.Allocate(); + new (N) MemIntrinsicSDNode(Opcode, VTList, Ops, NumOps, MemVT, + srcValue, SVOff, Align, Vol, ReadMem, WriteMem); + } + AllNodes.push_back(N); + return SDValue(N, 0); +} + +SDValue +SelectionDAG::getCall(unsigned CallingConv, bool IsVarArgs, bool IsTailCall, + bool IsInreg, SDVTList VTs, + const SDValue *Operands, unsigned NumOperands) { + // Do not include isTailCall in the folding set profile. + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::CALL, VTs, Operands, NumOperands); + ID.AddInteger(CallingConv); + ID.AddInteger(IsVarArgs); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) { + // Instead of including isTailCall in the folding set, we just + // set the flag of the existing node. + if (!IsTailCall) + cast(E)->setNotTailCall(); + return SDValue(E, 0); + } + SDNode *N = NodeAllocator.Allocate(); + new (N) CallSDNode(CallingConv, IsVarArgs, IsTailCall, IsInreg, + VTs, Operands, NumOperands); + CSEMap.InsertNode(N, IP); + AllNodes.push_back(N); + return SDValue(N, 0); +} + SDValue SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, MVT VT, SDValue Chain, @@ -3750,7 +3877,8 @@ SDValue SelectionDAG::UpdateNodeOperands(SDValue InN, SDValue Op) { // Nope it doesn't. Remove the node from its current place in the maps. if (InsertPos) - RemoveNodeFromCSEMaps(N); + if (!RemoveNodeFromCSEMaps(N)) + InsertPos = 0; // Now we update the operands. N->OperandList[0].getVal()->removeUser(0, N); @@ -3779,7 +3907,8 @@ UpdateNodeOperands(SDValue InN, SDValue Op1, SDValue Op2) { // Nope it doesn't. Remove the node from its current place in the maps. if (InsertPos) - RemoveNodeFromCSEMaps(N); + if (!RemoveNodeFromCSEMaps(N)) + InsertPos = 0; // Now we update the operands. if (N->OperandList[0] != Op1) { @@ -3845,7 +3974,8 @@ UpdateNodeOperands(SDValue InN, const SDValue *Ops, unsigned NumOps) { // Nope it doesn't. Remove the node from its current place in the maps. if (InsertPos) - RemoveNodeFromCSEMaps(N); + if (!RemoveNodeFromCSEMaps(N)) + InsertPos = 0; // Now we update the operands. for (unsigned i = 0; i != NumOps; ++i) { @@ -4068,7 +4198,8 @@ SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, return ON; } - RemoveNodeFromCSEMaps(N); + if (!RemoveNodeFromCSEMaps(N)) + IP = 0; // Start the morphing. N->NodeType = Opc; @@ -4091,6 +4222,7 @@ SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, if (NumOps > N->NumOperands) { if (N->OperandsNeedDelete) delete[] N->OperandList; + if (N->isMachineOpcode()) { // We're creating a final node that will live unmorphed for the // remainder of the current SelectionDAG iteration, so we can allocate @@ -4505,38 +4637,74 @@ void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From, /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG /// based on their topological order. It returns the maximum id and a vector /// of the SDNodes* in assigned order by reference. -unsigned SelectionDAG::AssignTopologicalOrder(std::vector &TopOrder) { - unsigned DAGSize = AllNodes.size(); - std::vector Sources; +unsigned SelectionDAG::AssignTopologicalOrder() { + + unsigned DAGSize = 0; + + // SortedPos tracks the progress of the algorithm. Nodes before it are + // sorted, nodes after it are unsorted. When the algorithm completes + // it is at the end of the list. + allnodes_iterator SortedPos = allnodes_begin(); + + // Visit all the nodes. Add nodes with no operands to the TopOrder result + // array immediately. Annotate nodes that do have operands with their + // operand count. Before we do this, the Node Id fields of the nodes + // may contain arbitrary values. After, the Node Id fields for nodes + // before SortedPos will contain the topological sort index, and the + // Node Id fields for nodes At SortedPos and after will contain the + // count of outstanding operands. + for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) { + SDNode *N = I++; + unsigned Degree = N->getNumOperands(); + if (Degree == 0) { + // A node with no uses, add it to the result array immediately. + N->setNodeId(DAGSize++); + allnodes_iterator Q = N; + if (Q != SortedPos) + SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q)); + ++SortedPos; + } else { + // Temporarily use the Node Id as scratch space for the degree count. + N->setNodeId(Degree); + } + } - for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){ + // Visit all the nodes. As we iterate, moves nodes into sorted order, + // 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; - unsigned Degree = N->use_size(); - // Temporarily use the Node Id as scratch space for the degree count. - N->setNodeId(Degree); - if (Degree == 0) - Sources.push_back(N); - } - - TopOrder.clear(); - TopOrder.reserve(DAGSize); - int Id = 0; - while (!Sources.empty()) { - SDNode *N = Sources.back(); - Sources.pop_back(); - TopOrder.push_back(N); - N->setNodeId(Id++); - for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { - SDNode *P = I->getVal(); + for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); + UI != UE; ++UI) { + SDNode *P = *UI; unsigned Degree = P->getNodeId(); --Degree; - P->setNodeId(Degree); - if (Degree == 0) - Sources.push_back(P); + if (Degree == 0) { + // All of P's operands are sorted, so P may sorted now. + P->setNodeId(DAGSize++); + if (P != SortedPos) + SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P)); + ++SortedPos; + } else { + // Update P's outstanding operand count. + P->setNodeId(Degree); + } } } - return Id; + assert(SortedPos == AllNodes.end() && + "Topological sort incomplete!"); + assert(AllNodes.front().getOpcode() == ISD::EntryToken && + "First node in topological sort is not the entry token!"); + assert(AllNodes.front().getNodeId() == 0 && + "First node in topological sort has non-zero id!"); + assert(AllNodes.front().getNumOperands() == 0 && + "First node in topological sort has operands!"); + assert(AllNodes.back().getNodeId() == (int)DAGSize-1 && + "Last node in topologic sort has unexpected id!"); + assert(AllNodes.back().use_empty() && + "Last node in topologic sort has users!"); + assert(DAGSize == allnodes_size() && "TopOrder result count mismatch!"); + return DAGSize; } @@ -4571,13 +4739,15 @@ void MemSDNode::ANCHOR() {} void LoadSDNode::ANCHOR() {} void StoreSDNode::ANCHOR() {} void AtomicSDNode::ANCHOR() {} +void MemIntrinsicSDNode::ANCHOR() {} +void CallSDNode::ANCHOR() {} HandleSDNode::~HandleSDNode() { DropOperands(); } GlobalAddressSDNode::GlobalAddressSDNode(bool isTarget, const GlobalValue *GA, - MVT VT, int o) + MVT VT, int64_t o) : SDNode(isa(GA) && cast(GA)->isThreadLocal() ? // Thread Local @@ -4599,6 +4769,17 @@ MemSDNode::MemSDNode(unsigned Opc, SDVTList VTs, MVT memvt, assert(isVolatile() == vol && "Volatile representation error!"); } +MemSDNode::MemSDNode(unsigned Opc, SDVTList VTs, const SDValue *Ops, + unsigned NumOps, MVT memvt, const Value *srcValue, + int SVO, unsigned alignment, bool vol) + : SDNode(Opc, VTs, Ops, NumOps), + MemoryVT(memvt), SrcValue(srcValue), SVOffset(SVO), + Flags(vol | ((Log2_32(alignment) + 1) << 1)) { + assert(isPowerOf2_32(alignment) && "Alignment is not a power of 2!"); + assert(getAlignment() == alignment && "Alignment representation error!"); + assert(isVolatile() == vol && "Volatile representation error!"); +} + /// getMemOperand - Return a MachineMemOperand object describing the memory /// reference performed by this memory reference. MachineMemOperand MemSDNode::getMemOperand() const { @@ -4607,10 +4788,15 @@ MachineMemOperand MemSDNode::getMemOperand() const { Flags = MachineMemOperand::MOLoad; else if (isa(this)) Flags = MachineMemOperand::MOStore; - else { - assert(isa(this) && "Unknown MemSDNode opcode!"); + else if (isa(this)) { Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOStore; } + else { + const MemIntrinsicSDNode* MemIntrinNode = dyn_cast(this); + assert(MemIntrinNode && "Unknown MemSDNode opcode!"); + if (MemIntrinNode->readMem()) Flags |= MachineMemOperand::MOLoad; + if (MemIntrinNode->writeMem()) Flags |= MachineMemOperand::MOStore; + } int Size = (getMemoryVT().getSizeInBits() + 7) >> 3; if (isVolatile()) Flags |= MachineMemOperand::MOVolatile; @@ -4768,7 +4954,7 @@ bool SDNode::isPredecessorOf(SDNode *N) const { uint64_t SDNode::getConstantOperandVal(unsigned Num) const { assert(Num < NumOperands && "Invalid child # of SDNode!"); - return cast(OperandList[Num])->getValue(); + return cast(OperandList[Num])->getZExtValue(); } std::string SDNode::getOperationName(const SelectionDAG *G) const { @@ -4875,12 +5061,12 @@ std::string SDNode::getOperationName(const SelectionDAG *G) const { case ISD::ConstantPool: return "ConstantPool"; case ISD::ExternalSymbol: return "ExternalSymbol"; case ISD::INTRINSIC_WO_CHAIN: { - unsigned IID = cast(getOperand(0))->getValue(); + unsigned IID = cast(getOperand(0))->getZExtValue(); return Intrinsic::getName((Intrinsic::ID)IID); } case ISD::INTRINSIC_VOID: case ISD::INTRINSIC_W_CHAIN: { - unsigned IID = cast(getOperand(1))->getValue(); + unsigned IID = cast(getOperand(1))->getZExtValue(); return Intrinsic::getName((Intrinsic::ID)IID); } @@ -4933,7 +5119,7 @@ std::string SDNode::getOperationName(const SelectionDAG *G) const { case ISD::SMUL_LOHI: return "smul_lohi"; case ISD::UMUL_LOHI: return "umul_lohi"; case ISD::SDIVREM: return "sdivrem"; - case ISD::UDIVREM: return "divrem"; + case ISD::UDIVREM: return "udivrem"; case ISD::AND: return "and"; case ISD::OR: return "or"; case ISD::XOR: return "xor"; @@ -5128,7 +5314,7 @@ void SDNode::print(raw_ostream &OS, const SelectionDAG *G) const { if (Mask->getOperand(i).getOpcode() == ISD::UNDEF) OS << "u"; else - OS << cast(Mask->getOperand(i))->getValue(); + OS << cast(Mask->getOperand(i))->getZExtValue(); } OS << ">"; } @@ -5142,12 +5328,12 @@ void SDNode::print(raw_ostream &OS, const SelectionDAG *G) const { OS << '<' << CSDN->getValueAPF().convertToDouble() << '>'; else { OS << "getValueAPF().convertToAPInt().dump(); + CSDN->getValueAPF().bitcastToAPInt().dump(); OS << ")>"; } } else if (const GlobalAddressSDNode *GADN = dyn_cast(this)) { - int offset = GADN->getOffset(); + int64_t offset = GADN->getOffset(); OS << '<'; WriteAsOperand(OS, GADN->getGlobal()); OS << '>';