X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FSelectionDAG.cpp;h=758f112f78c6e83e4318b50f7c67da32ed994792;hb=ee4c619b3b28a42078fc8033e5dccd42fc6edd42;hp=0a23966f31f550b26468076a548d14492e873db0;hpb=4474c792c6ef21862dd166fd0de59d70c4c8d489;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp index 0a23966f31f..758f112f78c 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -24,12 +24,14 @@ #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineModuleInfo.h" #include "llvm/CodeGen/PseudoSourceValue.h" -#include "llvm/Support/MathExtras.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetData.h" #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" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" @@ -68,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, @@ -82,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; } //===----------------------------------------------------------------------===// @@ -95,7 +99,7 @@ bool ConstantFPSDNode::isValueValidForType(MVT VT, bool ISD::isBuildVectorAllOnes(const SDNode *N) { // Look through a bit convert. if (N->getOpcode() == ISD::BIT_CONVERT) - N = N->getOperand(0).Val; + N = N->getOperand(0).getNode(); if (N->getOpcode() != ISD::BUILD_VECTOR) return false; @@ -110,13 +114,13 @@ bool ISD::isBuildVectorAllOnes(const SDNode *N) { // Do not accept build_vectors that aren't all constants or which have non-~0 // elements. - SDOperand NotZero = N->getOperand(i); + SDValue NotZero = N->getOperand(i); if (isa(NotZero)) { if (!cast(NotZero)->isAllOnesValue()) return false; } else if (isa(NotZero)) { if (!cast(NotZero)->getValueAPF(). - convertToAPInt().isAllOnesValue()) + bitcastToAPInt().isAllOnesValue()) return false; } else return false; @@ -136,7 +140,7 @@ bool ISD::isBuildVectorAllOnes(const SDNode *N) { bool ISD::isBuildVectorAllZeros(const SDNode *N) { // Look through a bit convert. if (N->getOpcode() == ISD::BIT_CONVERT) - N = N->getOperand(0).Val; + N = N->getOperand(0).getNode(); if (N->getOpcode() != ISD::BUILD_VECTOR) return false; @@ -151,7 +155,7 @@ bool ISD::isBuildVectorAllZeros(const SDNode *N) { // Do not accept build_vectors that aren't all constants or which have non-~0 // elements. - SDOperand Zero = N->getOperand(i); + SDValue Zero = N->getOperand(i); if (isa(Zero)) { if (!cast(Zero)->isNullValue()) return false; @@ -183,7 +187,7 @@ bool ISD::isScalarToVector(const SDNode *N) { return false; unsigned NumElems = N->getNumOperands(); for (unsigned i = 1; i < NumElems; ++i) { - SDOperand V = N->getOperand(i); + SDValue V = N->getOperand(i); if (V.getOpcode() != ISD::UNDEF) return false; } @@ -194,11 +198,11 @@ bool ISD::isScalarToVector(const SDNode *N) { /// isDebugLabel - Return true if the specified node represents a debug /// label (i.e. ISD::DBG_LABEL or TargetInstrInfo::DBG_LABEL node). bool ISD::isDebugLabel(const SDNode *N) { - SDOperand Zero; + SDValue Zero; if (N->getOpcode() == ISD::DBG_LABEL) return true; - if (N->isTargetOpcode() && - N->getTargetOpcode() == TargetInstrInfo::DBG_LABEL) + if (N->isMachineOpcode() && + N->getMachineOpcode() == TargetInstrInfo::DBG_LABEL) return true; return false; } @@ -212,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 @@ -223,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); } @@ -301,7 +307,7 @@ ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2, } const TargetMachine &SelectionDAG::getTarget() const { - return TLI.getTargetMachine(); + return MF->getTarget(); } //===----------------------------------------------------------------------===// @@ -323,16 +329,26 @@ static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) { /// AddNodeIDOperands - Various routines for adding operands to the NodeID data. /// static void AddNodeIDOperands(FoldingSetNodeID &ID, - SDOperandPtr Ops, unsigned NumOps) { + const SDValue *Ops, unsigned NumOps) { for (; NumOps; --NumOps, ++Ops) { - ID.AddPointer(Ops->Val); - ID.AddInteger(Ops->ResNo); + ID.AddPointer(Ops->getNode()); + ID.AddInteger(Ops->getResNo()); + } +} + +/// AddNodeIDOperands - Various routines for adding operands to the NodeID data. +/// +static void AddNodeIDOperands(FoldingSetNodeID &ID, + const SDUse *Ops, unsigned NumOps) { + for (; NumOps; --NumOps, ++Ops) { + ID.AddPointer(Ops->getVal()); + ID.AddInteger(Ops->getSDValue().getResNo()); } } static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC, SDVTList VTList, - SDOperandPtr OpList, unsigned N) { + const SDValue *OpList, unsigned N) { AddNodeIDOpcode(ID, OpC); AddNodeIDValueTypes(ID, VTList); AddNodeIDOperands(ID, OpList, N); @@ -341,7 +357,7 @@ static void AddNodeIDNode(FoldingSetNodeID &ID, /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID /// data. -static void AddNodeIDNode(FoldingSetNodeID &ID, SDNode *N) { +static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) { AddNodeIDOpcode(ID, N->getOpcode()); // Add the return value info. AddNodeIDValueTypes(ID, N->getVTList()); @@ -356,18 +372,18 @@ static void AddNodeIDNode(FoldingSetNodeID &ID, 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: case ISD::GlobalAddress: case ISD::TargetGlobalTLSAddress: case ISD::GlobalTLSAddress: { - GlobalAddressSDNode *GA = cast(N); + const GlobalAddressSDNode *GA = cast(N); ID.AddPointer(GA->getGlobal()); ID.AddInteger(GA->getOffset()); break; @@ -385,20 +401,12 @@ static void AddNodeIDNode(FoldingSetNodeID &ID, SDNode *N) { ID.AddPointer(DSP->getCompileUnit()); break; } - case ISD::DBG_LABEL: - case ISD::EH_LABEL: - ID.AddInteger(cast(N)->getLabelID()); - break; case ISD::SRCVALUE: ID.AddPointer(cast(N)->getValue()); break; case ISD::MEMOPERAND: { const MachineMemOperand &MO = cast(N)->MO; - ID.AddPointer(MO.getValue()); - ID.AddInteger(MO.getFlags()); - ID.AddInteger(MO.getOffset()); - ID.AddInteger(MO.getSize()); - ID.AddInteger(MO.getAlignment()); + MO.Profile(ID); break; } case ISD::FrameIndex: @@ -411,7 +419,7 @@ static void AddNodeIDNode(FoldingSetNodeID &ID, SDNode *N) { break; case ISD::ConstantPool: case ISD::TargetConstantPool: { - ConstantPoolSDNode *CP = cast(N); + const ConstantPoolSDNode *CP = cast(N); ID.AddInteger(CP->getAlignment()); ID.AddInteger(CP->getOffset()); if (CP->isMachineConstantPoolEntry()) @@ -420,44 +428,91 @@ static void AddNodeIDNode(FoldingSetNodeID &ID, 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: { - LoadSDNode *LD = cast(N); + const LoadSDNode *LD = cast(N); ID.AddInteger(LD->getAddressingMode()); ID.AddInteger(LD->getExtensionType()); ID.AddInteger(LD->getMemoryVT().getRawBits()); - ID.AddInteger(LD->getAlignment()); - ID.AddInteger(LD->isVolatile()); + ID.AddInteger(LD->getRawFlags()); break; } case ISD::STORE: { - StoreSDNode *ST = cast(N); + const StoreSDNode *ST = cast(N); ID.AddInteger(ST->getAddressingMode()); ID.AddInteger(ST->isTruncatingStore()); ID.AddInteger(ST->getMemoryVT().getRawBits()); - ID.AddInteger(ST->getAlignment()); - ID.AddInteger(ST->isVolatile()); + ID.AddInteger(ST->getRawFlags()); break; } - case ISD::ATOMIC_CMP_SWAP: - case ISD::ATOMIC_LOAD_ADD: - case ISD::ATOMIC_SWAP: - case ISD::ATOMIC_LOAD_SUB: - case ISD::ATOMIC_LOAD_AND: - case ISD::ATOMIC_LOAD_OR: - case ISD::ATOMIC_LOAD_XOR: - case ISD::ATOMIC_LOAD_NAND: - case ISD::ATOMIC_LOAD_MIN: - case ISD::ATOMIC_LOAD_MAX: - case ISD::ATOMIC_LOAD_UMIN: - case ISD::ATOMIC_LOAD_UMAX: { - AtomicSDNode *AT = cast(N); - ID.AddInteger(AT->getAlignment()); - ID.AddInteger(AT->isVolatile()); + case ISD::ATOMIC_CMP_SWAP_8: + case ISD::ATOMIC_SWAP_8: + case ISD::ATOMIC_LOAD_ADD_8: + case ISD::ATOMIC_LOAD_SUB_8: + case ISD::ATOMIC_LOAD_AND_8: + case ISD::ATOMIC_LOAD_OR_8: + case ISD::ATOMIC_LOAD_XOR_8: + case ISD::ATOMIC_LOAD_NAND_8: + case ISD::ATOMIC_LOAD_MIN_8: + case ISD::ATOMIC_LOAD_MAX_8: + case ISD::ATOMIC_LOAD_UMIN_8: + case ISD::ATOMIC_LOAD_UMAX_8: + case ISD::ATOMIC_CMP_SWAP_16: + case ISD::ATOMIC_SWAP_16: + case ISD::ATOMIC_LOAD_ADD_16: + case ISD::ATOMIC_LOAD_SUB_16: + case ISD::ATOMIC_LOAD_AND_16: + case ISD::ATOMIC_LOAD_OR_16: + case ISD::ATOMIC_LOAD_XOR_16: + case ISD::ATOMIC_LOAD_NAND_16: + case ISD::ATOMIC_LOAD_MIN_16: + case ISD::ATOMIC_LOAD_MAX_16: + case ISD::ATOMIC_LOAD_UMIN_16: + case ISD::ATOMIC_LOAD_UMAX_16: + case ISD::ATOMIC_CMP_SWAP_32: + case ISD::ATOMIC_SWAP_32: + case ISD::ATOMIC_LOAD_ADD_32: + case ISD::ATOMIC_LOAD_SUB_32: + case ISD::ATOMIC_LOAD_AND_32: + case ISD::ATOMIC_LOAD_OR_32: + case ISD::ATOMIC_LOAD_XOR_32: + case ISD::ATOMIC_LOAD_NAND_32: + case ISD::ATOMIC_LOAD_MIN_32: + case ISD::ATOMIC_LOAD_MAX_32: + case ISD::ATOMIC_LOAD_UMIN_32: + case ISD::ATOMIC_LOAD_UMAX_32: + case ISD::ATOMIC_CMP_SWAP_64: + case ISD::ATOMIC_SWAP_64: + case ISD::ATOMIC_LOAD_ADD_64: + case ISD::ATOMIC_LOAD_SUB_64: + case ISD::ATOMIC_LOAD_AND_64: + case ISD::ATOMIC_LOAD_OR_64: + case ISD::ATOMIC_LOAD_XOR_64: + case ISD::ATOMIC_LOAD_NAND_64: + case ISD::ATOMIC_LOAD_MIN_64: + case ISD::ATOMIC_LOAD_MAX_64: + case ISD::ATOMIC_LOAD_UMIN_64: + case ISD::ATOMIC_LOAD_UMAX_64: { + const AtomicSDNode *AT = cast(N); + ID.AddInteger(AT->getRawFlags()); break; } } // end switch (N->getOpcode()) } +/// encodeMemSDNodeFlags - Generic routine for computing a value for use in +/// the CSE map that carries both alignment and volatility information. +/// +static inline unsigned +encodeMemSDNodeFlags(bool isVolatile, unsigned Alignment) { + return isVolatile | ((Log2_32(Alignment) + 1) << 1); +} + //===----------------------------------------------------------------------===// // SelectionDAG Class //===----------------------------------------------------------------------===// @@ -476,42 +531,16 @@ void SelectionDAG::RemoveDeadNodes() { if (I->use_empty()) DeadNodes.push_back(I); - // Process the worklist, deleting the nodes and adding their uses to the - // worklist. - while (!DeadNodes.empty()) { - SDNode *N = DeadNodes.back(); - DeadNodes.pop_back(); - - // Take the node out of the appropriate CSE map. - RemoveNodeFromCSEMaps(N); - - // Next, brutally remove the operand list. This is safe to do, as there are - // no cycles in the graph. - for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { - SDNode *Operand = I->getVal(); - Operand->removeUser(std::distance(N->op_begin(), I), N); - - // Now that we removed this operand, see if there are no uses of it left. - if (Operand->use_empty()) - DeadNodes.push_back(Operand); - } - if (N->OperandsNeedDelete) { - delete[] N->OperandList; - } - N->OperandList = 0; - N->NumOperands = 0; - - // Finally, remove N itself. - AllNodes.erase(N); - } + RemoveDeadNodes(DeadNodes); // If the root changed (e.g. it was a dead load, update the root). setRoot(Dummy.getValue()); } -void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){ - SmallVector DeadNodes; - DeadNodes.push_back(N); +/// RemoveDeadNodes - This method deletes the unreachable nodes in the +/// given list, and any nodes that become unreachable as a result. +void SelectionDAG::RemoveDeadNodes(SmallVectorImpl &DeadNodes, + DAGUpdateListener *UpdateListener) { // Process the worklist, deleting the nodes and adding their uses to the // worklist. @@ -527,28 +556,31 @@ void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){ // Next, brutally remove the operand list. This is safe to do, as there are // no cycles in the graph. - unsigned op_num = 0; for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { SDNode *Operand = I->getVal(); - Operand->removeUser(op_num, N); + Operand->removeUser(std::distance(N->op_begin(), I), N); // Now that we removed this operand, see if there are no uses of it left. if (Operand->use_empty()) DeadNodes.push_back(Operand); - - op_num++; } - if (N->OperandsNeedDelete) { + + if (N->OperandsNeedDelete) delete[] N->OperandList; - } + N->OperandList = 0; N->NumOperands = 0; // Finally, remove N itself. - AllNodes.erase(N); + NodeAllocator.Deallocate(AllNodes.remove(N)); } } +void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){ + SmallVector DeadNodes(1, N); + RemoveDeadNodes(DeadNodes, UpdateListener); +} + void SelectionDAG::DeleteNode(SDNode *N) { assert(N->use_empty() && "Cannot delete a node that is not dead!"); @@ -561,30 +593,30 @@ void SelectionDAG::DeleteNode(SDNode *N) { } void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) { - - // Remove it from the AllNodes list. - AllNodes.remove(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) { delete[] N->OperandList; + N->OperandList = 0; } - N->OperandList = 0; - N->NumOperands = 0; - delete N; + assert(N != AllNodes.begin()); + NodeAllocator.Deallocate(AllNodes.remove(N)); } /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that /// 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::HANDLENODE: return; // noop. + case ISD::EntryToken: + assert(0 && "EntryToken should not be in CSEMaps!"); + return false; + case ISD::HANDLENODE: return false; // noop. case ISD::CONDCODE: assert(CondCodeNodes[cast(N)->get()] && "Cond code doesn't exist!"); @@ -618,12 +650,17 @@ 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 && + N->getOpcode() != ISD::DECLARE) { N->dump(this); cerr << "\n"; assert(0 && "Node is not in map!"); } #endif + return Erased; } /// AddNonLeafNodeToCSEMaps - Add the specified node back to the CSE maps. It @@ -633,13 +670,24 @@ void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { /// SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) { assert(N->getNumOperands() && "This is a leaf node!"); - if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) - return 0; // Never add these nodes. + + if (N->getValueType(0) == MVT::Flag) + return 0; // Never CSE anything that produces a flag. + + switch (N->getOpcode()) { + default: break; + case ISD::HANDLENODE: + case ISD::DBG_LABEL: + case ISD::DBG_STOPPOINT: + case ISD::EH_LABEL: + case ISD::DECLARE: + 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. @@ -650,17 +698,26 @@ SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) { /// were replaced with those specified. If this node is never memoized, /// return null, otherwise return a pointer to the slot it would take. If a /// node already exists with these operands, the slot will be non-null. -SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op, +SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos) { - if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) - return 0; // Never add these nodes. + if (N->getValueType(0) == MVT::Flag) + return 0; // Never CSE anything that produces a flag. + + switch (N->getOpcode()) { + default: break; + case ISD::HANDLENODE: + case ISD::DBG_LABEL: + case ISD::DBG_STOPPOINT: + case ISD::EH_LABEL: + 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. - SDOperand Ops[] = { Op }; + SDValue Ops[] = { Op }; FoldingSetNodeID ID; AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1); return CSEMap.FindNodeOrInsertPos(ID, InsertPos); @@ -671,17 +728,16 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op, /// return null, otherwise return a pointer to the slot it would take. If a /// node already exists with these operands, the slot will be non-null. SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, - SDOperand Op1, SDOperand Op2, + SDValue Op1, SDValue Op2, void *&InsertPos) { if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) - 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. - SDOperand Ops[] = { Op1, Op2 }; + SDValue Ops[] = { Op1, Op2 }; FoldingSetNodeID ID; AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2); return CSEMap.FindNodeOrInsertPos(ID, InsertPos); @@ -693,15 +749,25 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, /// return null, otherwise return a pointer to the slot it would take. If a /// node already exists with these operands, the slot will be non-null. SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, - SDOperandPtr Ops,unsigned NumOps, + const SDValue *Ops,unsigned NumOps, void *&InsertPos) { - if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) - return 0; // Never add these nodes. + if (N->getValueType(0) == MVT::Flag) + return 0; // Never CSE anything that produces a flag. + + switch (N->getOpcode()) { + default: break; + case ISD::HANDLENODE: + case ISD::DBG_LABEL: + case ISD::DBG_STOPPOINT: + case ISD::EH_LABEL: + case ISD::DECLARE: + 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); @@ -710,34 +776,102 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ID.AddInteger(LD->getAddressingMode()); ID.AddInteger(LD->getExtensionType()); ID.AddInteger(LD->getMemoryVT().getRawBits()); - ID.AddInteger(LD->getAlignment()); - ID.AddInteger(LD->isVolatile()); + ID.AddInteger(LD->getRawFlags()); } else if (const StoreSDNode *ST = dyn_cast(N)) { ID.AddInteger(ST->getAddressingMode()); ID.AddInteger(ST->isTruncatingStore()); ID.AddInteger(ST->getMemoryVT().getRawBits()); - ID.AddInteger(ST->getAlignment()); - ID.AddInteger(ST->isVolatile()); + ID.AddInteger(ST->getRawFlags()); } return CSEMap.FindNodeOrInsertPos(ID, InsertPos); } +/// VerifyNode - Sanity check the given node. Aborts if it is invalid. +void SelectionDAG::VerifyNode(SDNode *N) { + switch (N->getOpcode()) { + default: + break; + case ISD::BUILD_VECTOR: { + assert(N->getNumValues() == 1 && "Too many results for BUILD_VECTOR!"); + assert(N->getValueType(0).isVector() && "Wrong BUILD_VECTOR return type!"); + assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() && + "Wrong number of BUILD_VECTOR operands!"); + // 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; + } + } +} + +/// getMVTAlignment - Compute the default alignment value for the +/// given type. +/// +unsigned SelectionDAG::getMVTAlignment(MVT VT) const { + const Type *Ty = VT == MVT::iPTR ? + PointerType::get(Type::Int8Ty, 0) : + VT.getTypeForMVT(); + + return TLI.getTargetData()->getABITypeAlignment(Ty); +} + +SelectionDAG::SelectionDAG(TargetLowering &tli, FunctionLoweringInfo &fli) + : TLI(tli), FLI(fli), + EntryNode(ISD::EntryToken, getVTList(MVT::Other)), + Root(getEntryNode()) { + AllNodes.push_back(&EntryNode); +} + +void SelectionDAG::init(MachineFunction &mf, MachineModuleInfo *mmi) { + MF = &mf; + MMI = mmi; +} SelectionDAG::~SelectionDAG() { + allnodes_clear(); +} + +void SelectionDAG::allnodes_clear() { + assert(&*AllNodes.begin() == &EntryNode); + AllNodes.remove(AllNodes.begin()); while (!AllNodes.empty()) { - SDNode *N = AllNodes.begin(); + SDNode *N = AllNodes.remove(AllNodes.begin()); N->SetNextInBucket(0); + if (N->OperandsNeedDelete) { delete [] N->OperandList; + N->OperandList = 0; } - N->OperandList = 0; - N->NumOperands = 0; - AllNodes.pop_front(); + + NodeAllocator.Deallocate(N); } } -SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT VT) { +void SelectionDAG::clear() { + allnodes_clear(); + OperandAllocator.Reset(); + CSEMap.clear(); + + ExtendedValueTypeNodes.clear(); + ExternalSymbols.clear(); + TargetExternalSymbols.clear(); + std::fill(CondCodeNodes.begin(), CondCodeNodes.end(), + static_cast(0)); + std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(), + static_cast(0)); + + EntryNode.Uses = 0; + AllNodes.push_back(&EntryNode); + Root = getEntryNode(); +} + +SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, MVT VT) { if (Op.getValueType() == VT) return Op; APInt Imm = APInt::getLowBitsSet(Op.getValueSizeInBits(), VT.getSizeInBits()); @@ -745,12 +879,16 @@ SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT VT) { getConstant(Imm, Op.getValueType())); } -SDOperand SelectionDAG::getConstant(uint64_t Val, MVT VT, bool isT) { +SDValue SelectionDAG::getConstant(uint64_t Val, MVT VT, bool isT) { MVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT; return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT); } -SDOperand SelectionDAG::getConstant(const APInt &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; @@ -759,34 +897,39 @@ SDOperand SelectionDAG::getConstant(const APInt &Val, MVT VT, bool isT) { unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant; FoldingSetNodeID ID; - AddNodeIDNode(ID, Opc, getVTList(EltVT), (SDOperand*)0, 0); - ID.Add(Val); + AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0); + ID.AddPointer(&Val); void *IP = 0; SDNode *N = NULL; if ((N = CSEMap.FindNodeOrInsertPos(ID, IP))) if (!VT.isVector()) - return SDOperand(N, 0); + return SDValue(N, 0); if (!N) { - N = new ConstantSDNode(isT, Val, EltVT); + N = NodeAllocator.Allocate(); + new (N) ConstantSDNode(isT, &Val, EltVT); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); } - SDOperand Result(N, 0); + SDValue Result(N, 0); if (VT.isVector()) { - SmallVector Ops; + SmallVector Ops; Ops.assign(VT.getVectorNumElements(), Result); Result = getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size()); } return Result; } -SDOperand SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) { +SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) { return getConstant(Val, TLI.getPointerTy(), isTarget); } -SDOperand SelectionDAG::getConstantFP(const APFloat& V, MVT VT, 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 = @@ -797,29 +940,30 @@ SDOperand SelectionDAG::getConstantFP(const APFloat& V, MVT VT, bool isTarget) { // we don't have issues with SNANs. unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP; FoldingSetNodeID ID; - AddNodeIDNode(ID, Opc, getVTList(EltVT), (SDOperand*)0, 0); - ID.Add(V); + AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0); + ID.AddPointer(&V); void *IP = 0; SDNode *N = NULL; if ((N = CSEMap.FindNodeOrInsertPos(ID, IP))) if (!VT.isVector()) - return SDOperand(N, 0); + return SDValue(N, 0); if (!N) { - N = new ConstantFPSDNode(isTarget, V, EltVT); + N = NodeAllocator.Allocate(); + new (N) ConstantFPSDNode(isTarget, &V, EltVT); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); } - SDOperand Result(N, 0); + SDValue Result(N, 0); if (VT.isVector()) { - SmallVector Ops; + SmallVector Ops; Ops.assign(VT.getVectorNumElements(), Result); Result = getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size()); } return Result; } -SDOperand SelectionDAG::getConstantFP(double Val, MVT VT, bool isTarget) { +SDValue SelectionDAG::getConstantFP(double Val, MVT VT, bool isTarget) { MVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT; if (EltVT==MVT::f32) @@ -828,16 +972,21 @@ SDOperand SelectionDAG::getConstantFP(double Val, MVT VT, bool isTarget) { return getConstantFP(APFloat(Val), VT, isTarget); } -SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV, - MVT VT, int Offset, - bool isTargetGA) { +SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, + 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()) @@ -846,252 +995,262 @@ SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV, Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress; FoldingSetNodeID ID; - AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0); + AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); ID.AddPointer(GV); ID.AddInteger(Offset); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new GlobalAddressSDNode(isTargetGA, GV, VT, Offset); + return SDValue(E, 0); + SDNode *N = NodeAllocator.Allocate(); + new (N) GlobalAddressSDNode(isTargetGA, GV, VT, Offset); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getFrameIndex(int FI, MVT VT, bool isTarget) { +SDValue SelectionDAG::getFrameIndex(int FI, MVT VT, bool isTarget) { unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex; FoldingSetNodeID ID; - AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0); + AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); ID.AddInteger(FI); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new FrameIndexSDNode(FI, VT, isTarget); + return SDValue(E, 0); + SDNode *N = NodeAllocator.Allocate(); + new (N) FrameIndexSDNode(FI, VT, isTarget); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getJumpTable(int JTI, MVT VT, bool isTarget){ +SDValue SelectionDAG::getJumpTable(int JTI, MVT VT, bool isTarget){ unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable; FoldingSetNodeID ID; - AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0); + AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); ID.AddInteger(JTI); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new JumpTableSDNode(JTI, VT, isTarget); + return SDValue(E, 0); + SDNode *N = NodeAllocator.Allocate(); + new (N) JumpTableSDNode(JTI, VT, isTarget); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getConstantPool(Constant *C, MVT VT, - unsigned Alignment, int Offset, - 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), (SDOperand*)0, 0); + AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); ID.AddInteger(Alignment); ID.AddInteger(Offset); ID.AddPointer(C); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment); + return SDValue(E, 0); + SDNode *N = NodeAllocator.Allocate(); + new (N) ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getConstantPool(MachineConstantPoolValue *C, MVT VT, - unsigned Alignment, int Offset, - bool isTarget) { +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), (SDOperand*)0, 0); + AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); ID.AddInteger(Alignment); ID.AddInteger(Offset); C->AddSelectionDAGCSEId(ID); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment); + return SDValue(E, 0); + SDNode *N = NodeAllocator.Allocate(); + new (N) ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { +SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { FoldingSetNodeID ID; - AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), (SDOperand*)0, 0); + AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0); ID.AddPointer(MBB); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new BasicBlockSDNode(MBB); + return SDValue(E, 0); + SDNode *N = NodeAllocator.Allocate(); + new (N) BasicBlockSDNode(MBB); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getArgFlags(ISD::ArgFlagsTy Flags) { +SDValue SelectionDAG::getArgFlags(ISD::ArgFlagsTy Flags) { FoldingSetNodeID ID; - AddNodeIDNode(ID, ISD::ARG_FLAGS, getVTList(MVT::Other), (SDOperand*)0, 0); + AddNodeIDNode(ID, ISD::ARG_FLAGS, getVTList(MVT::Other), 0, 0); ID.AddInteger(Flags.getRawBits()); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new ARG_FLAGSSDNode(Flags); + return SDValue(E, 0); + SDNode *N = NodeAllocator.Allocate(); + new (N) ARG_FLAGSSDNode(Flags); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getValueType(MVT VT) { +SDValue SelectionDAG::getValueType(MVT VT) { if (VT.isSimple() && (unsigned)VT.getSimpleVT() >= ValueTypeNodes.size()) ValueTypeNodes.resize(VT.getSimpleVT()+1); SDNode *&N = VT.isExtended() ? ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT()]; - if (N) return SDOperand(N, 0); - N = new VTSDNode(VT); + if (N) return SDValue(N, 0); + N = NodeAllocator.Allocate(); + new (N) VTSDNode(VT); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT VT) { +SDValue SelectionDAG::getExternalSymbol(const char *Sym, MVT VT) { SDNode *&N = ExternalSymbols[Sym]; - if (N) return SDOperand(N, 0); - N = new ExternalSymbolSDNode(false, Sym, VT); + if (N) return SDValue(N, 0); + N = NodeAllocator.Allocate(); + new (N) ExternalSymbolSDNode(false, Sym, VT); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getTargetExternalSymbol(const char *Sym, MVT VT) { +SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, MVT VT) { SDNode *&N = TargetExternalSymbols[Sym]; - if (N) return SDOperand(N, 0); - N = new ExternalSymbolSDNode(true, Sym, VT); + if (N) return SDValue(N, 0); + N = NodeAllocator.Allocate(); + new (N) ExternalSymbolSDNode(true, Sym, VT); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) { +SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) { if ((unsigned)Cond >= CondCodeNodes.size()) CondCodeNodes.resize(Cond+1); if (CondCodeNodes[Cond] == 0) { - CondCodeNodes[Cond] = new CondCodeSDNode(Cond); - AllNodes.push_back(CondCodeNodes[Cond]); + CondCodeSDNode *N = NodeAllocator.Allocate(); + new (N) CondCodeSDNode(Cond); + CondCodeNodes[Cond] = N; + AllNodes.push_back(N); } - return SDOperand(CondCodeNodes[Cond], 0); + return SDValue(CondCodeNodes[Cond], 0); } -SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT VT) { +SDValue SelectionDAG::getRegister(unsigned RegNo, MVT VT) { FoldingSetNodeID ID; - AddNodeIDNode(ID, ISD::Register, getVTList(VT), (SDOperand*)0, 0); + AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0); ID.AddInteger(RegNo); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new RegisterSDNode(RegNo, VT); + return SDValue(E, 0); + SDNode *N = NodeAllocator.Allocate(); + new (N) RegisterSDNode(RegNo, VT); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getDbgStopPoint(SDOperand Root, +SDValue SelectionDAG::getDbgStopPoint(SDValue Root, unsigned Line, unsigned Col, const CompileUnitDesc *CU) { - FoldingSetNodeID ID; - SDOperand Ops[] = { Root }; - AddNodeIDNode(ID, ISD::DBG_STOPPOINT, getVTList(MVT::Other), &Ops[0], 1); - ID.AddInteger(Line); - ID.AddInteger(Col); - ID.AddPointer(CU); - void *IP = 0; - if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new DbgStopPointSDNode(Root, Line, Col, CU); - CSEMap.InsertNode(N, IP); + SDNode *N = NodeAllocator.Allocate(); + new (N) DbgStopPointSDNode(Root, Line, Col, CU); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getLabel(unsigned Opcode, - SDOperand Root, - unsigned LabelID) { +SDValue SelectionDAG::getLabel(unsigned Opcode, + SDValue Root, + unsigned LabelID) { FoldingSetNodeID ID; - SDOperand Ops[] = { Root }; + SDValue Ops[] = { Root }; AddNodeIDNode(ID, Opcode, getVTList(MVT::Other), &Ops[0], 1); ID.AddInteger(LabelID); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new LabelSDNode(Opcode, Root, LabelID); + return SDValue(E, 0); + SDNode *N = NodeAllocator.Allocate(); + new (N) LabelSDNode(Opcode, Root, LabelID); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getSrcValue(const Value *V) { +SDValue SelectionDAG::getSrcValue(const Value *V) { assert((!V || isa(V->getType())) && "SrcValue is not a pointer?"); FoldingSetNodeID ID; - AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), (SDOperand*)0, 0); + AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0); ID.AddPointer(V); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); + return SDValue(E, 0); - SDNode *N = new SrcValueSDNode(V); + SDNode *N = NodeAllocator.Allocate(); + new (N) SrcValueSDNode(V); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getMemOperand(const MachineMemOperand &MO) { +SDValue SelectionDAG::getMemOperand(const MachineMemOperand &MO) { const Value *v = MO.getValue(); assert((!v || isa(v->getType())) && "SrcValue is not a pointer?"); FoldingSetNodeID ID; - AddNodeIDNode(ID, ISD::MEMOPERAND, getVTList(MVT::Other), (SDOperand*)0, 0); - ID.AddPointer(v); - ID.AddInteger(MO.getFlags()); - ID.AddInteger(MO.getOffset()); - ID.AddInteger(MO.getSize()); - ID.AddInteger(MO.getAlignment()); + AddNodeIDNode(ID, ISD::MEMOPERAND, getVTList(MVT::Other), 0, 0); + MO.Profile(ID); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); + return SDValue(E, 0); - SDNode *N = new MemOperandSDNode(MO); + SDNode *N = NodeAllocator.Allocate(); + new (N) MemOperandSDNode(MO); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } /// CreateStackTemporary - Create a stack temporary, suitable for holding the /// specified value type. -SDOperand SelectionDAG::CreateStackTemporary(MVT VT) { +SDValue SelectionDAG::CreateStackTemporary(MVT VT, unsigned minAlign) { MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo(); unsigned ByteSize = VT.getSizeInBits()/8; const Type *Ty = VT.getTypeForMVT(); - unsigned StackAlign = (unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty); + unsigned StackAlign = + std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty), minAlign); + int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign); return getFrameIndex(FrameIdx, TLI.getPointerTy()); } - -SDOperand SelectionDAG::FoldSetCC(MVT VT, SDOperand N1, - SDOperand N2, ISD::CondCode Cond) { +SDValue SelectionDAG::FoldSetCC(MVT VT, SDValue N1, + SDValue N2, ISD::CondCode Cond) { // These setcc operations always fold. switch (Cond) { default: break; @@ -1114,9 +1273,9 @@ SDOperand SelectionDAG::FoldSetCC(MVT VT, SDOperand N1, break; } - if (ConstantSDNode *N2C = dyn_cast(N2.Val)) { + if (ConstantSDNode *N2C = dyn_cast(N2.getNode())) { const APInt &C2 = N2C->getAPIntValue(); - if (ConstantSDNode *N1C = dyn_cast(N1.Val)) { + if (ConstantSDNode *N1C = dyn_cast(N1.getNode())) { const APInt &C1 = N1C->getAPIntValue(); switch (Cond) { @@ -1134,11 +1293,11 @@ SDOperand SelectionDAG::FoldSetCC(MVT VT, SDOperand N1, } } } - if (ConstantFPSDNode *N1C = dyn_cast(N1.Val)) { - if (ConstantFPSDNode *N2C = dyn_cast(N2.Val)) { + if (ConstantFPSDNode *N1C = dyn_cast(N1.getNode())) { + if (ConstantFPSDNode *N2C = dyn_cast(N2.getNode())) { // No compile time operations on this type yet. if (N1C->getValueType(0) == MVT::ppcf128) - return SDOperand(); + return SDValue(); APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF()); switch (Cond) { @@ -1189,12 +1348,12 @@ SDOperand SelectionDAG::FoldSetCC(MVT VT, SDOperand N1, } // Could not fold it. - return SDOperand(); + return SDValue(); } /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We /// use this predicate to simplify operations downstream. -bool SelectionDAG::SignBitIsZero(SDOperand Op, unsigned Depth) const { +bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const { unsigned BitWidth = Op.getValueSizeInBits(); return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth); } @@ -1202,7 +1361,7 @@ bool SelectionDAG::SignBitIsZero(SDOperand Op, unsigned Depth) const { /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use /// this predicate to simplify operations downstream. Mask is known to be zero /// for bits that V cannot have. -bool SelectionDAG::MaskedValueIsZero(SDOperand Op, const APInt &Mask, +bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth) const { APInt KnownZero, KnownOne; ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth); @@ -1214,7 +1373,7 @@ bool SelectionDAG::MaskedValueIsZero(SDOperand Op, const APInt &Mask, /// known to be either zero or one and return them in the KnownZero/KnownOne /// bitsets. This code only analyzes bits in Mask, in order to short-circuit /// processing. -void SelectionDAG::ComputeMaskedBits(SDOperand Op, const APInt &Mask, +void SelectionDAG::ComputeMaskedBits(SDValue Op, const APInt &Mask, APInt &KnownZero, APInt &KnownOne, unsigned Depth) const { unsigned BitWidth = Mask.getBitWidth(); @@ -1346,7 +1505,7 @@ void SelectionDAG::ComputeMaskedBits(SDOperand 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) @@ -1364,7 +1523,7 @@ void SelectionDAG::ComputeMaskedBits(SDOperand 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) @@ -1382,7 +1541,7 @@ void SelectionDAG::ComputeMaskedBits(SDOperand 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) @@ -1456,7 +1615,7 @@ void SelectionDAG::ComputeMaskedBits(SDOperand Op, const APInt &Mask, return; } case ISD::LOAD: { - if (ISD::isZEXTLoad(Op.Val)) { + if (ISD::isZEXTLoad(Op.getNode())) { LoadSDNode *LD = cast(Op); MVT VT = LD->getMemoryVT(); unsigned MemBits = VT.getSizeInBits(); @@ -1600,21 +1759,19 @@ void SelectionDAG::ComputeMaskedBits(SDOperand Op, const APInt &Mask, } case ISD::SREM: if (ConstantSDNode *Rem = dyn_cast(Op.getOperand(1))) { - APInt RA = Rem->getAPIntValue(); + const APInt &RA = Rem->getAPIntValue(); if (RA.isPowerOf2() || (-RA).isPowerOf2()) { APInt LowBits = RA.isStrictlyPositive() ? (RA - 1) : ~RA; APInt Mask2 = LowBits | APInt::getSignBit(BitWidth); ComputeMaskedBits(Op.getOperand(0), Mask2,KnownZero2,KnownOne2,Depth+1); - // The sign of a remainder is equal to the sign of the first - // operand (zero being positive). + // If the sign bit of the first operand is zero, the sign bit of + // the result is zero. If the first operand has no one bits below + // the second operand's single 1 bit, its sign will be zero. if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits)) KnownZero2 |= ~LowBits; - else if (KnownOne2[BitWidth-1]) - KnownOne2 |= ~LowBits; KnownZero |= KnownZero2 & Mask; - KnownOne |= KnownOne2 & Mask; assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); } @@ -1622,7 +1779,7 @@ void SelectionDAG::ComputeMaskedBits(SDOperand Op, const APInt &Mask, return; case ISD::UREM: { if (ConstantSDNode *Rem = dyn_cast(Op.getOperand(1))) { - APInt RA = Rem->getAPIntValue(); + const APInt &RA = Rem->getAPIntValue(); if (RA.isPowerOf2()) { APInt LowBits = (RA - 1); APInt Mask2 = LowBits & Mask; @@ -1664,7 +1821,7 @@ void SelectionDAG::ComputeMaskedBits(SDOperand Op, const APInt &Mask, /// is always equal to the sign bit (itself), but other cases can give us /// information. For example, immediately after an "SRA X, 2", we know that /// the top 3 bits are all equal to each other, so we return 3. -unsigned SelectionDAG::ComputeNumSignBits(SDOperand Op, unsigned Depth) const{ +unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{ MVT VT = Op.getValueType(); assert(VT.isInteger() && "Invalid VT!"); unsigned VTBits = VT.getSizeInBits(); @@ -1709,7 +1866,7 @@ unsigned SelectionDAG::ComputeNumSignBits(SDOperand 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; @@ -1717,9 +1874,9 @@ unsigned SelectionDAG::ComputeNumSignBits(SDOperand 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: @@ -1751,7 +1908,7 @@ unsigned SelectionDAG::ComputeNumSignBits(SDOperand 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) @@ -1876,9 +2033,10 @@ unsigned SelectionDAG::ComputeNumSignBits(SDOperand Op, unsigned Depth) const{ } -bool SelectionDAG::isVerifiedDebugInfoDesc(SDOperand Op) 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(); @@ -1888,21 +2046,21 @@ bool SelectionDAG::isVerifiedDebugInfoDesc(SDOperand Op) const { /// 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 i) { +SDValue SelectionDAG::getShuffleScalarElt(const SDNode *N, unsigned i) { MVT VT = N->getValueType(0); - SDOperand PermMask = N->getOperand(2); - SDOperand Idx = PermMask.getOperand(i); + SDValue PermMask = N->getOperand(2); + 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(); - SDOperand V = (Index < NumElems) ? N->getOperand(0) : N->getOperand(1); + SDValue V = (Index < NumElems) ? N->getOperand(0) : N->getOperand(1); Index %= NumElems; if (V.getOpcode() == ISD::BIT_CONVERT) { V = V.getOperand(0); if (V.getValueType().getVectorNumElements() != NumElems) - return SDOperand(); + return SDValue(); } if (V.getOpcode() == ISD::SCALAR_TO_VECTOR) return (Index == 0) ? V.getOperand(0) @@ -1910,29 +2068,33 @@ SDOperand SelectionDAG::getShuffleScalarElt(const SDNode *N, unsigned i) { if (V.getOpcode() == ISD::BUILD_VECTOR) return V.getOperand(Index); if (V.getOpcode() == ISD::VECTOR_SHUFFLE) - return getShuffleScalarElt(V.Val, Index); - return SDOperand(); + return getShuffleScalarElt(V.getNode(), Index); + return SDValue(); } /// getNode - Gets or creates the specified node. /// -SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT) { +SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT) { FoldingSetNodeID ID; - AddNodeIDNode(ID, Opcode, getVTList(VT), (SDOperand*)0, 0); + AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new SDNode(Opcode, SDNode::getSDVTList(VT)); + return SDValue(E, 0); + SDNode *N = NodeAllocator.Allocate(); + new (N) SDNode(Opcode, SDNode::getSDVTList(VT)); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); +#ifndef NDEBUG + VerifyNode(N); +#endif + return SDValue(N, 0); } -SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, SDOperand Operand) { +SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, SDValue Operand) { // Constant fold unary operations with an integer constant operand. - if (ConstantSDNode *C = dyn_cast(Operand.Val)) { + if (ConstantSDNode *C = dyn_cast(Operand.getNode())) { const APInt &Val = C->getAPIntValue(); unsigned BitWidth = VT.getSizeInBits(); switch (Opcode) { @@ -1973,7 +2135,7 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, SDOperand Operand) { } // Constant fold unary operations with a floating point constant operand. - if (ConstantFPSDNode *C = dyn_cast(Operand.Val)) { + if (ConstantFPSDNode *C = dyn_cast(Operand.getNode())) { APFloat V = C->getValueAPF(); // make copy if (VT != MVT::ppcf128 && Operand.getValueType() != MVT::ppcf128) { switch (Opcode) { @@ -1984,38 +2146,42 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, SDOperand 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; } } } - unsigned OpOpcode = Operand.Val->getOpcode(); + unsigned OpOpcode = Operand.getNode()->getOpcode(); switch (Opcode) { case ISD::TokenFactor: - return Operand; // Factor of one node? No need. + case ISD::CONCAT_VECTORS: + return Operand; // Factor or concat of one node? No need. case ISD::FP_ROUND: assert(0 && "Invalid method to make FP_ROUND node"); case ISD::FP_EXTEND: assert(VT.isFloatingPoint() && @@ -2031,7 +2197,7 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, SDOperand Operand) { assert(Operand.getValueType().bitsLT(VT) && "Invalid sext node, dst < src!"); if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND) - return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); + return getNode(OpOpcode, VT, Operand.getNode()->getOperand(0)); break; case ISD::ZERO_EXTEND: assert(VT.isInteger() && Operand.getValueType().isInteger() && @@ -2040,7 +2206,7 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, SDOperand Operand) { assert(Operand.getValueType().bitsLT(VT) && "Invalid zext node, dst < src!"); if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x) - return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0)); + return getNode(ISD::ZERO_EXTEND, VT, Operand.getNode()->getOperand(0)); break; case ISD::ANY_EXTEND: assert(VT.isInteger() && Operand.getValueType().isInteger() && @@ -2050,7 +2216,7 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, SDOperand Operand) { && "Invalid anyext node, dst < src!"); if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x) - return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); + return getNode(OpOpcode, VT, Operand.getNode()->getOperand(0)); break; case ISD::TRUNCATE: assert(VT.isInteger() && Operand.getValueType().isInteger() && @@ -2059,16 +2225,16 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, SDOperand Operand) { assert(Operand.getValueType().bitsGT(VT) && "Invalid truncate node, src < dst!"); if (OpOpcode == ISD::TRUNCATE) - return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); + return getNode(ISD::TRUNCATE, VT, Operand.getNode()->getOperand(0)); else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ANY_EXTEND) { // If the source is smaller than the dest, we still need an extend. - if (Operand.Val->getOperand(0).getValueType().bitsLT(VT)) - return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); - else if (Operand.Val->getOperand(0).getValueType().bitsGT(VT)) - return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); + if (Operand.getNode()->getOperand(0).getValueType().bitsLT(VT)) + return getNode(OpOpcode, VT, Operand.getNode()->getOperand(0)); + else if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT)) + return getNode(ISD::TRUNCATE, VT, Operand.getNode()->getOperand(0)); else - return Operand.Val->getOperand(0); + return Operand.getNode()->getOperand(0); } break; case ISD::BIT_CONVERT: @@ -2096,14 +2262,14 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, SDOperand Operand) { break; case ISD::FNEG: if (OpOpcode == ISD::FSUB) // -(X-Y) -> (Y-X) - return getNode(ISD::FSUB, VT, Operand.Val->getOperand(1), - Operand.Val->getOperand(0)); + return getNode(ISD::FSUB, VT, Operand.getNode()->getOperand(1), + Operand.getNode()->getOperand(0)); if (OpOpcode == ISD::FNEG) // --X -> X - return Operand.Val->getOperand(0); + return Operand.getNode()->getOperand(0); break; case ISD::FABS: if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X) - return getNode(ISD::FABS, VT, Operand.Val->getOperand(0)); + return getNode(ISD::FABS, VT, Operand.getNode()->getOperand(0)); break; } @@ -2111,26 +2277,66 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, SDOperand Operand) { SDVTList VTs = getVTList(VT); if (VT != MVT::Flag) { // Don't CSE flag producing nodes FoldingSetNodeID ID; - SDOperand Ops[1] = { Operand }; + SDValue Ops[1] = { Operand }; AddNodeIDNode(ID, Opcode, VTs, Ops, 1); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - N = new UnarySDNode(Opcode, VTs, Operand); + return SDValue(E, 0); + N = NodeAllocator.Allocate(); + new (N) UnarySDNode(Opcode, VTs, Operand); CSEMap.InsertNode(N, IP); } else { - N = new UnarySDNode(Opcode, VTs, Operand); + N = NodeAllocator.Allocate(); + new (N) UnarySDNode(Opcode, VTs, Operand); } + AllNodes.push_back(N); - return SDOperand(N, 0); +#ifndef NDEBUG + VerifyNode(N); +#endif + 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(); +} -SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, - SDOperand N1, SDOperand N2) { - ConstantSDNode *N1C = dyn_cast(N1.Val); - ConstantSDNode *N2C = dyn_cast(N2.Val); +SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, + SDValue N1, SDValue N2) { + ConstantSDNode *N1C = dyn_cast(N1.getNode()); + ConstantSDNode *N2C = dyn_cast(N2.getNode()); switch (Opcode) { default: break; case ISD::TokenFactor: @@ -2139,6 +2345,17 @@ SDOperand 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 + // one big BUILD_VECTOR. + if (N1.getOpcode() == ISD::BUILD_VECTOR && + N2.getOpcode() == ISD::BUILD_VECTOR) { + SmallVector Elts(N1.getNode()->op_begin(), N1.getNode()->op_end()); + Elts.insert(Elts.end(), N2.getNode()->op_begin(), N2.getNode()->op_end()); + return getNode(ISD::BUILD_VECTOR, VT, &Elts[0], Elts.size()); + } break; case ISD::AND: assert(VT.isInteger() && N1.getValueType() == N2.getValueType() && @@ -2192,7 +2409,13 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, assert(VT == N1.getValueType() && "Shift operators return type must be the same as their first arg"); assert(VT.isInteger() && N2.getValueType().isInteger() && - VT != MVT::i1 && "Shifts only work on integers"); + "Shifts only work on integers"); + + // Always fold shifts of i1 values so the code generator doesn't need to + // handle them. Since we know the size of the shift has to be less than the + // size of the value, the shift/rotate count is guaranteed to be zero. + if (VT == MVT::i1) + return N1; break; case ISD::FP_ROUND_INREG: { MVT EVT = cast(N2)->getVT(); @@ -2238,40 +2461,39 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, break; } case ISD::EXTRACT_VECTOR_ELT: - assert(N2C && "Bad EXTRACT_VECTOR_ELT!"); - // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF. if (N1.getOpcode() == ISD::UNDEF) return getNode(ISD::UNDEF, VT); // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is // expanding copies of large vectors from registers. - if (N1.getOpcode() == ISD::CONCAT_VECTORS && + if (N2C && + N1.getOpcode() == ISD::CONCAT_VECTORS && N1.getNumOperands() > 0) { 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 (N1.getOpcode() == ISD::BUILD_VECTOR) - return N1.getOperand(N2C->getValue()); + if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) + return N1.getOperand(N2C->getZExtValue()); // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector // operations are lowered to scalars. - if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) - if (ConstantSDNode *IEC = dyn_cast(N1.getOperand(2))) { - if (IEC == N2C) - return N1.getOperand(1); - else - return getNode(ISD::EXTRACT_VECTOR_ELT, VT, N1.getOperand(0), N2); - } + if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) { + if (N1.getOperand(2) == N2) + return N1.getOperand(1); + else + return getNode(ISD::EXTRACT_VECTOR_ELT, VT, N1.getOperand(0), N2); + } 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!"); @@ -2280,12 +2502,12 @@ SDOperand 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); } @@ -2298,33 +2520,8 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, if (N1C) { if (N2C) { - 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); @@ -2334,8 +2531,8 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, } // Constant fold FP operations. - ConstantFPSDNode *N1CFP = dyn_cast(N1.Val); - ConstantFPSDNode *N2CFP = dyn_cast(N2.Val); + ConstantFPSDNode *N1CFP = dyn_cast(N1.getNode()); + ConstantFPSDNode *N2CFP = dyn_cast(N2.getNode()); if (N1CFP) { if (!N2CFP && isCommutativeBinOp(Opcode)) { // Cannonicalize constant to RHS if commutative @@ -2454,37 +2651,54 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, SDNode *N; SDVTList VTs = getVTList(VT); if (VT != MVT::Flag) { - SDOperand Ops[] = { N1, N2 }; + SDValue Ops[] = { N1, N2 }; FoldingSetNodeID ID; AddNodeIDNode(ID, Opcode, VTs, Ops, 2); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - N = new BinarySDNode(Opcode, VTs, N1, N2); + return SDValue(E, 0); + N = NodeAllocator.Allocate(); + new (N) BinarySDNode(Opcode, VTs, N1, N2); CSEMap.InsertNode(N, IP); } else { - N = new BinarySDNode(Opcode, VTs, N1, N2); + N = NodeAllocator.Allocate(); + new (N) BinarySDNode(Opcode, VTs, N1, N2); } AllNodes.push_back(N); - return SDOperand(N, 0); +#ifndef NDEBUG + VerifyNode(N); +#endif + return SDValue(N, 0); } -SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, - SDOperand N1, SDOperand N2, SDOperand N3) { +SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, + SDValue N1, SDValue N2, SDValue N3) { // Perform various simplifications. - ConstantSDNode *N1C = dyn_cast(N1.Val); - ConstantSDNode *N2C = dyn_cast(N2.Val); + ConstantSDNode *N1C = dyn_cast(N1.getNode()); + ConstantSDNode *N2C = dyn_cast(N2.getNode()); switch (Opcode) { + case ISD::CONCAT_VECTORS: + // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to + // one big BUILD_VECTOR. + if (N1.getOpcode() == ISD::BUILD_VECTOR && + N2.getOpcode() == ISD::BUILD_VECTOR && + N3.getOpcode() == ISD::BUILD_VECTOR) { + SmallVector Elts(N1.getNode()->op_begin(), N1.getNode()->op_end()); + Elts.insert(Elts.end(), N2.getNode()->op_begin(), N2.getNode()->op_end()); + Elts.insert(Elts.end(), N3.getNode()->op_begin(), N3.getNode()->op_end()); + return getNode(ISD::BUILD_VECTOR, VT, &Elts[0], Elts.size()); + } + break; case ISD::SETCC: { // Use FoldSetCC to simplify SETCC's. - SDOperand Simp = FoldSetCC(VT, N1, N2, cast(N3)->get()); - if (Simp.Val) return Simp; + SDValue Simp = FoldSetCC(VT, N1, N2, cast(N3)->get()); + if (Simp.getNode()) return Simp; break; } 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 @@ -2494,7 +2708,7 @@ SDOperand 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 @@ -2518,42 +2732,47 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, SDNode *N; SDVTList VTs = getVTList(VT); if (VT != MVT::Flag) { - SDOperand Ops[] = { N1, N2, N3 }; + SDValue Ops[] = { N1, N2, N3 }; FoldingSetNodeID ID; AddNodeIDNode(ID, Opcode, VTs, Ops, 3); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - N = new TernarySDNode(Opcode, VTs, N1, N2, N3); + return SDValue(E, 0); + N = NodeAllocator.Allocate(); + new (N) TernarySDNode(Opcode, VTs, N1, N2, N3); CSEMap.InsertNode(N, IP); } else { - N = new TernarySDNode(Opcode, VTs, N1, N2, N3); + N = NodeAllocator.Allocate(); + new (N) TernarySDNode(Opcode, VTs, N1, N2, N3); } AllNodes.push_back(N); - return SDOperand(N, 0); +#ifndef NDEBUG + VerifyNode(N); +#endif + return SDValue(N, 0); } -SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, - SDOperand N1, SDOperand N2, SDOperand N3, - SDOperand N4) { - SDOperand Ops[] = { N1, N2, N3, N4 }; +SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, + SDValue N1, SDValue N2, SDValue N3, + SDValue N4) { + SDValue Ops[] = { N1, N2, N3, N4 }; return getNode(Opcode, VT, Ops, 4); } -SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, - SDOperand N1, SDOperand N2, SDOperand N3, - SDOperand N4, SDOperand N5) { - SDOperand Ops[] = { N1, N2, N3, N4, N5 }; +SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, + SDValue N1, SDValue N2, SDValue N3, + SDValue N4, SDValue N5) { + SDValue Ops[] = { N1, N2, N3, N4, N5 }; return getNode(Opcode, VT, Ops, 5); } /// getMemsetValue - Vectorized representation of the memset value /// operand. -static SDOperand getMemsetValue(SDOperand Value, MVT VT, SelectionDAG &DAG) { +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; @@ -2579,7 +2798,7 @@ static SDOperand getMemsetValue(SDOperand Value, MVT VT, SelectionDAG &DAG) { /// 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 VT, SelectionDAG &DAG, +static SDValue getMemsetStringVal(MVT VT, SelectionDAG &DAG, const TargetLowering &TLI, std::string &Str, unsigned Offset) { // Handle vector with all elements zero. @@ -2607,7 +2826,7 @@ static SDOperand getMemsetStringVal(MVT VT, SelectionDAG &DAG, /// getMemBasePlusOffset - Returns base and offset node for the /// -static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset, +static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SelectionDAG &DAG) { MVT VT = Base.getValueType(); return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT)); @@ -2615,7 +2834,7 @@ static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset, /// isMemSrcFromString - Returns true if memcpy source is a string constant. /// -static bool isMemSrcFromString(SDOperand Src, std::string &Str) { +static bool isMemSrcFromString(SDValue Src, std::string &Str) { unsigned SrcDelta = 0; GlobalAddressSDNode *G = NULL; if (Src.getOpcode() == ISD::GlobalAddress) @@ -2624,7 +2843,7 @@ static bool isMemSrcFromString(SDOperand 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; @@ -2641,7 +2860,7 @@ static bool isMemSrcFromString(SDOperand Src, std::string &Str) { /// types of the sequence of memory ops to perform memset / memcpy. static bool MeetsMaxMemopRequirement(std::vector &MemOps, - SDOperand Dst, SDOperand Src, + SDValue Dst, SDValue Src, unsigned Limit, uint64_t Size, unsigned &Align, std::string &Str, bool &isSrcStr, SelectionDAG &DAG, @@ -2722,9 +2941,9 @@ bool MeetsMaxMemopRequirement(std::vector &MemOps, return true; } -static SDOperand getMemcpyLoadsAndStores(SelectionDAG &DAG, - SDOperand Chain, SDOperand Dst, - SDOperand Src, uint64_t Size, +static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, + SDValue Chain, SDValue Dst, + SDValue Src, uint64_t Size, unsigned Align, bool AlwaysInline, const Value *DstSV, uint64_t DstSVOff, const Value *SrcSV, uint64_t SrcSVOff){ @@ -2733,7 +2952,7 @@ static SDOperand 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. @@ -2741,17 +2960,17 @@ static SDOperand getMemcpyLoadsAndStores(SelectionDAG &DAG, bool CopyFromStr; if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, Limit, Size, DstAlign, Str, CopyFromStr, DAG, TLI)) - return SDOperand(); + return SDValue(); bool isZeroStr = CopyFromStr && Str.empty(); - SmallVector OutChains; + SmallVector OutChains; unsigned NumMemOps = MemOps.size(); uint64_t SrcOff = 0, DstOff = 0; for (unsigned i = 0; i < NumMemOps; i++) { MVT VT = MemOps[i]; unsigned VTSize = VT.getSizeInBits() / 8; - SDOperand Value, Store; + SDValue Value, Store; if (CopyFromStr && (isZeroStr || !VT.isVector())) { // It's unlikely a store of a vector immediate can be done in a single @@ -2762,7 +2981,7 @@ static SDOperand getMemcpyLoadsAndStores(SelectionDAG &DAG, Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff); Store = DAG.getStore(Chain, Value, getMemBasePlusOffset(Dst, DstOff, DAG), - DstSV, DstSVOff + DstOff); + DstSV, DstSVOff + DstOff, false, DstAlign); } else { Value = DAG.getLoad(VT, Chain, getMemBasePlusOffset(Src, SrcOff, DAG), @@ -2780,9 +2999,9 @@ static SDOperand getMemcpyLoadsAndStores(SelectionDAG &DAG, &OutChains[0], OutChains.size()); } -static SDOperand getMemmoveLoadsAndStores(SelectionDAG &DAG, - SDOperand Chain, SDOperand Dst, - SDOperand Src, uint64_t Size, +static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, + SDValue Chain, SDValue Dst, + SDValue Src, uint64_t Size, unsigned Align, bool AlwaysInline, const Value *DstSV, uint64_t DstSVOff, const Value *SrcSV, uint64_t SrcSVOff){ @@ -2791,7 +3010,7 @@ static SDOperand 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. @@ -2799,18 +3018,18 @@ static SDOperand getMemmoveLoadsAndStores(SelectionDAG &DAG, bool CopyFromStr; if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, Limit, Size, DstAlign, Str, CopyFromStr, DAG, TLI)) - return SDOperand(); + return SDValue(); uint64_t SrcOff = 0, DstOff = 0; - SmallVector LoadValues; - SmallVector LoadChains; - SmallVector OutChains; + SmallVector LoadValues; + SmallVector LoadChains; + SmallVector OutChains; unsigned NumMemOps = MemOps.size(); for (unsigned i = 0; i < NumMemOps; i++) { MVT VT = MemOps[i]; unsigned VTSize = VT.getSizeInBits() / 8; - SDOperand Value, Store; + SDValue Value, Store; Value = DAG.getLoad(VT, Chain, getMemBasePlusOffset(Src, SrcOff, DAG), @@ -2825,7 +3044,7 @@ static SDOperand getMemmoveLoadsAndStores(SelectionDAG &DAG, for (unsigned i = 0; i < NumMemOps; i++) { MVT VT = MemOps[i]; unsigned VTSize = VT.getSizeInBits() / 8; - SDOperand Value, Store; + SDValue Value, Store; Store = DAG.getStore(Chain, LoadValues[i], getMemBasePlusOffset(Dst, DstOff, DAG), @@ -2838,9 +3057,9 @@ static SDOperand getMemmoveLoadsAndStores(SelectionDAG &DAG, &OutChains[0], OutChains.size()); } -static SDOperand getMemsetStores(SelectionDAG &DAG, - SDOperand Chain, SDOperand Dst, - SDOperand Src, uint64_t Size, +static SDValue getMemsetStores(SelectionDAG &DAG, + SDValue Chain, SDValue Dst, + SDValue Src, uint64_t Size, unsigned Align, const Value *DstSV, uint64_t DstSVOff) { const TargetLowering &TLI = DAG.getTargetLoweringInfo(); @@ -2852,17 +3071,17 @@ static SDOperand getMemsetStores(SelectionDAG &DAG, bool CopyFromStr; if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, TLI.getMaxStoresPerMemset(), Size, Align, Str, CopyFromStr, DAG, TLI)) - return SDOperand(); + return SDValue(); - SmallVector OutChains; + SmallVector OutChains; uint64_t DstOff = 0; unsigned NumMemOps = MemOps.size(); for (unsigned i = 0; i < NumMemOps; i++) { MVT VT = MemOps[i]; unsigned VTSize = VT.getSizeInBits() / 8; - SDOperand Value = getMemsetValue(Src, VT, DAG); - SDOperand Store = DAG.getStore(Chain, Value, + SDValue Value = getMemsetValue(Src, VT, DAG); + SDValue Store = DAG.getStore(Chain, Value, getMemBasePlusOffset(Dst, DstOff, DAG), DstSV, DstSVOff + DstOff); OutChains.push_back(Store); @@ -2873,11 +3092,11 @@ static SDOperand getMemsetStores(SelectionDAG &DAG, &OutChains[0], OutChains.size()); } -SDOperand SelectionDAG::getMemcpy(SDOperand Chain, SDOperand Dst, - SDOperand Src, SDOperand Size, - unsigned Align, bool AlwaysInline, - const Value *DstSV, uint64_t DstSVOff, - const Value *SrcSV, uint64_t SrcSVOff) { +SDValue SelectionDAG::getMemcpy(SDValue Chain, SDValue Dst, + SDValue Src, SDValue Size, + unsigned Align, bool AlwaysInline, + const Value *DstSV, uint64_t DstSVOff, + const Value *SrcSV, uint64_t SrcSVOff) { // Check to see if we should lower the memcpy to loads and stores first. // For cases within the target-specified limits, this is the best choice. @@ -2887,20 +3106,21 @@ SDOperand SelectionDAG::getMemcpy(SDOperand Chain, SDOperand Dst, if (ConstantSize->isNullValue()) return Chain; - SDOperand Result = - getMemcpyLoadsAndStores(*this, Chain, Dst, Src, ConstantSize->getValue(), + SDValue Result = + getMemcpyLoadsAndStores(*this, Chain, Dst, Src, + ConstantSize->getZExtValue(), Align, false, DstSV, DstSVOff, SrcSV, SrcSVOff); - if (Result.Val) + if (Result.getNode()) return Result; } // Then check to see if we should lower the memcpy with target-specific // code. If the target chooses to do this, this is the next best. - SDOperand Result = + SDValue Result = TLI.EmitTargetCodeForMemcpy(*this, Chain, Dst, Src, Size, Align, AlwaysInline, DstSV, DstSVOff, SrcSV, SrcSVOff); - if (Result.Val) + if (Result.getNode()) return Result; // If we really need inline code and the target declined to provide it, @@ -2908,7 +3128,7 @@ SDOperand SelectionDAG::getMemcpy(SDOperand Chain, SDOperand 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); } @@ -2919,19 +3139,19 @@ SDOperand SelectionDAG::getMemcpy(SDOperand Chain, SDOperand Dst, Entry.Node = Dst; Args.push_back(Entry); Entry.Node = Src; Args.push_back(Entry); Entry.Node = Size; Args.push_back(Entry); - std::pair CallResult = + 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; } -SDOperand SelectionDAG::getMemmove(SDOperand Chain, SDOperand Dst, - SDOperand Src, SDOperand Size, - unsigned Align, - const Value *DstSV, uint64_t DstSVOff, - const Value *SrcSV, uint64_t SrcSVOff) { +SDValue SelectionDAG::getMemmove(SDValue Chain, SDValue Dst, + SDValue Src, SDValue Size, + unsigned Align, + const Value *DstSV, uint64_t DstSVOff, + const Value *SrcSV, uint64_t SrcSVOff) { // 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. @@ -2941,19 +3161,20 @@ SDOperand SelectionDAG::getMemmove(SDOperand Chain, SDOperand Dst, if (ConstantSize->isNullValue()) return Chain; - SDOperand Result = - getMemmoveLoadsAndStores(*this, Chain, Dst, Src, ConstantSize->getValue(), + SDValue Result = + getMemmoveLoadsAndStores(*this, Chain, Dst, Src, + ConstantSize->getZExtValue(), Align, false, DstSV, DstSVOff, SrcSV, SrcSVOff); - if (Result.Val) + if (Result.getNode()) 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. - SDOperand Result = + SDValue Result = TLI.EmitTargetCodeForMemmove(*this, Chain, Dst, Src, Size, Align, DstSV, DstSVOff, SrcSV, SrcSVOff); - if (Result.Val) + if (Result.getNode()) return Result; // Emit a library call. @@ -2963,18 +3184,18 @@ SDOperand SelectionDAG::getMemmove(SDOperand Chain, SDOperand Dst, Entry.Node = Dst; Args.push_back(Entry); Entry.Node = Src; Args.push_back(Entry); Entry.Node = Size; Args.push_back(Entry); - std::pair CallResult = + 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; } -SDOperand SelectionDAG::getMemset(SDOperand Chain, SDOperand Dst, - SDOperand Src, SDOperand Size, - unsigned Align, - const Value *DstSV, uint64_t DstSVOff) { +SDValue SelectionDAG::getMemset(SDValue Chain, SDValue Dst, + SDValue Src, SDValue Size, + unsigned Align, + const Value *DstSV, uint64_t DstSVOff) { // Check to see if we should lower the memset to stores first. // For cases within the target-specified limits, this is the best choice. @@ -2984,19 +3205,19 @@ SDOperand SelectionDAG::getMemset(SDOperand Chain, SDOperand Dst, if (ConstantSize->isNullValue()) return Chain; - SDOperand Result = - getMemsetStores(*this, Chain, Dst, Src, ConstantSize->getValue(), Align, - DstSV, DstSVOff); - if (Result.Val) + SDValue Result = + getMemsetStores(*this, Chain, Dst, Src, ConstantSize->getZExtValue(), + Align, DstSV, DstSVOff); + if (Result.getNode()) return Result; } // Then check to see if we should lower the memset with target-specific // code. If the target chooses to do this, this is the next best. - SDOperand Result = + SDValue Result = TLI.EmitTargetCodeForMemset(*this, Chain, Dst, Src, Size, Align, DstSV, DstSVOff); - if (Result.Val) + if (Result.getNode()) return Result; // Emit a library call. @@ -3014,77 +3235,198 @@ SDOperand SelectionDAG::getMemset(SDOperand Chain, SDOperand Dst, Args.push_back(Entry); Entry.Node = Size; Entry.Ty = IntPtrTy; Entry.isSExt = false; Args.push_back(Entry); - std::pair CallResult = + 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; } -SDOperand SelectionDAG::getAtomic(unsigned Opcode, SDOperand Chain, - SDOperand Ptr, SDOperand Cmp, - SDOperand Swp, const Value* PtrVal, - unsigned Alignment) { - assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op"); +SDValue SelectionDAG::getAtomic(unsigned Opcode, SDValue Chain, + SDValue Ptr, SDValue Cmp, + SDValue Swp, const Value* PtrVal, + unsigned Alignment) { + assert((Opcode == ISD::ATOMIC_CMP_SWAP_8 || + Opcode == ISD::ATOMIC_CMP_SWAP_16 || + Opcode == ISD::ATOMIC_CMP_SWAP_32 || + Opcode == ISD::ATOMIC_CMP_SWAP_64) && "Invalid Atomic Op"); assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types"); - SDVTList VTs = getVTList(Cmp.getValueType(), MVT::Other); + + MVT VT = Cmp.getValueType(); + + if (Alignment == 0) // Ensure that codegen never sees alignment 0 + Alignment = getMVTAlignment(VT); + + SDVTList VTs = getVTList(VT, MVT::Other); FoldingSetNodeID ID; - SDOperand Ops[] = {Chain, Ptr, Cmp, Swp}; + SDValue Ops[] = {Chain, Ptr, Cmp, Swp}; AddNodeIDNode(ID, Opcode, VTs, Ops, 4); void* IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode* N = new AtomicSDNode(Opcode, VTs, Chain, Ptr, Cmp, Swp, - PtrVal, Alignment); + return SDValue(E, 0); + SDNode* N = NodeAllocator.Allocate(); + new (N) AtomicSDNode(Opcode, VTs, Chain, Ptr, Cmp, Swp, PtrVal, Alignment); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); -} - -SDOperand SelectionDAG::getAtomic(unsigned Opcode, SDOperand Chain, - SDOperand Ptr, SDOperand Val, - const Value* PtrVal, - unsigned Alignment) { - assert(( Opcode == ISD::ATOMIC_LOAD_ADD || Opcode == ISD::ATOMIC_LOAD_SUB - || Opcode == ISD::ATOMIC_SWAP || Opcode == ISD::ATOMIC_LOAD_AND - || Opcode == ISD::ATOMIC_LOAD_OR || Opcode == ISD::ATOMIC_LOAD_XOR - || Opcode == ISD::ATOMIC_LOAD_NAND - || Opcode == ISD::ATOMIC_LOAD_MIN || Opcode == ISD::ATOMIC_LOAD_MAX - || Opcode == ISD::ATOMIC_LOAD_UMIN || Opcode == ISD::ATOMIC_LOAD_UMAX) - && "Invalid Atomic Op"); - SDVTList VTs = getVTList(Val.getValueType(), MVT::Other); + return SDValue(N, 0); +} + +SDValue SelectionDAG::getAtomic(unsigned Opcode, SDValue Chain, + SDValue Ptr, SDValue Val, + const Value* PtrVal, + unsigned Alignment) { + assert((Opcode == ISD::ATOMIC_LOAD_ADD_8 || + Opcode == ISD::ATOMIC_LOAD_SUB_8 || + Opcode == ISD::ATOMIC_LOAD_AND_8 || + Opcode == ISD::ATOMIC_LOAD_OR_8 || + Opcode == ISD::ATOMIC_LOAD_XOR_8 || + Opcode == ISD::ATOMIC_LOAD_NAND_8 || + Opcode == ISD::ATOMIC_LOAD_MIN_8 || + Opcode == ISD::ATOMIC_LOAD_MAX_8 || + Opcode == ISD::ATOMIC_LOAD_UMIN_8 || + Opcode == ISD::ATOMIC_LOAD_UMAX_8 || + Opcode == ISD::ATOMIC_SWAP_8 || + Opcode == ISD::ATOMIC_LOAD_ADD_16 || + Opcode == ISD::ATOMIC_LOAD_SUB_16 || + Opcode == ISD::ATOMIC_LOAD_AND_16 || + Opcode == ISD::ATOMIC_LOAD_OR_16 || + Opcode == ISD::ATOMIC_LOAD_XOR_16 || + Opcode == ISD::ATOMIC_LOAD_NAND_16 || + Opcode == ISD::ATOMIC_LOAD_MIN_16 || + Opcode == ISD::ATOMIC_LOAD_MAX_16 || + Opcode == ISD::ATOMIC_LOAD_UMIN_16 || + Opcode == ISD::ATOMIC_LOAD_UMAX_16 || + Opcode == ISD::ATOMIC_SWAP_16 || + Opcode == ISD::ATOMIC_LOAD_ADD_32 || + Opcode == ISD::ATOMIC_LOAD_SUB_32 || + Opcode == ISD::ATOMIC_LOAD_AND_32 || + Opcode == ISD::ATOMIC_LOAD_OR_32 || + Opcode == ISD::ATOMIC_LOAD_XOR_32 || + Opcode == ISD::ATOMIC_LOAD_NAND_32 || + Opcode == ISD::ATOMIC_LOAD_MIN_32 || + Opcode == ISD::ATOMIC_LOAD_MAX_32 || + Opcode == ISD::ATOMIC_LOAD_UMIN_32 || + Opcode == ISD::ATOMIC_LOAD_UMAX_32 || + Opcode == ISD::ATOMIC_SWAP_32 || + Opcode == ISD::ATOMIC_LOAD_ADD_64 || + Opcode == ISD::ATOMIC_LOAD_SUB_64 || + Opcode == ISD::ATOMIC_LOAD_AND_64 || + Opcode == ISD::ATOMIC_LOAD_OR_64 || + Opcode == ISD::ATOMIC_LOAD_XOR_64 || + Opcode == ISD::ATOMIC_LOAD_NAND_64 || + Opcode == ISD::ATOMIC_LOAD_MIN_64 || + Opcode == ISD::ATOMIC_LOAD_MAX_64 || + Opcode == ISD::ATOMIC_LOAD_UMIN_64 || + Opcode == ISD::ATOMIC_LOAD_UMAX_64 || + Opcode == ISD::ATOMIC_SWAP_64) && "Invalid Atomic Op"); + + MVT VT = Val.getValueType(); + + if (Alignment == 0) // Ensure that codegen never sees alignment 0 + Alignment = getMVTAlignment(VT); + + SDVTList VTs = getVTList(VT, MVT::Other); FoldingSetNodeID ID; - SDOperand Ops[] = {Chain, Ptr, Val}; + SDValue Ops[] = {Chain, Ptr, Val}; AddNodeIDNode(ID, Opcode, VTs, Ops, 3); void* IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode* N = new AtomicSDNode(Opcode, VTs, Chain, Ptr, Val, - PtrVal, Alignment); + return SDValue(E, 0); + SDNode* N = NodeAllocator.Allocate(); + new (N) AtomicSDNode(Opcode, VTs, Chain, Ptr, Val, PtrVal, Alignment); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); +} + +/// getMergeValues - Create a MERGE_VALUES node from the given operands. +/// Allowed to return something different (and simpler) if Simplify is true. +SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps, + bool Simplify) { + if (Simplify && NumOps == 1) + return Ops[0]; + + SmallVector VTs; + VTs.reserve(NumOps); + for (unsigned i = 0; i < NumOps; ++i) + VTs.push_back(Ops[i].getValueType()); + 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); } -SDOperand +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, SDOperand Chain, - SDOperand Ptr, SDOperand Offset, + MVT VT, SDValue Chain, + SDValue Ptr, SDValue Offset, const Value *SV, int SVOffset, MVT EVT, bool isVolatile, unsigned Alignment) { - if (Alignment == 0) { // Ensure that codegen never sees alignment 0 - const Type *Ty = 0; - if (VT != MVT::iPTR) { - Ty = VT.getTypeForMVT(); - } else if (SV) { - const PointerType *PT = dyn_cast(SV->getType()); - assert(PT && "Value for load must be a pointer"); - Ty = PT->getElementType(); - } - assert(Ty && "Could not get type information for load"); - Alignment = TLI.getTargetData()->getABITypeAlignment(Ty); - } + if (Alignment == 0) // Ensure that codegen never sees alignment 0 + Alignment = getMVTAlignment(VT); if (VT == EVT) { ExtType = ISD::NON_EXTLOAD; @@ -3093,7 +3435,8 @@ SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, } else { // Extending load. if (VT.isVector()) - assert(EVT == VT.getVectorElementType() && "Invalid vector extload!"); + assert(EVT.getVectorNumElements() == VT.getVectorNumElements() && + "Invalid vector extload!"); else assert(EVT.bitsLT(VT) && "Should only be an extending load, not truncating!"); @@ -3109,46 +3452,46 @@ SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, SDVTList VTs = Indexed ? getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other); - SDOperand Ops[] = { Chain, Ptr, Offset }; + SDValue Ops[] = { Chain, Ptr, Offset }; FoldingSetNodeID ID; AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3); ID.AddInteger(AM); ID.AddInteger(ExtType); ID.AddInteger(EVT.getRawBits()); - ID.AddInteger(Alignment); - ID.AddInteger(isVolatile); + ID.AddInteger(encodeMemSDNodeFlags(isVolatile, Alignment)); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new LoadSDNode(Ops, VTs, AM, ExtType, EVT, SV, SVOffset, - Alignment, isVolatile); + return SDValue(E, 0); + SDNode *N = NodeAllocator.Allocate(); + new (N) LoadSDNode(Ops, VTs, AM, ExtType, EVT, SV, SVOffset, + Alignment, isVolatile); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getLoad(MVT VT, - SDOperand Chain, SDOperand Ptr, - const Value *SV, int SVOffset, - bool isVolatile, unsigned Alignment) { - SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); +SDValue SelectionDAG::getLoad(MVT VT, + SDValue Chain, SDValue Ptr, + const Value *SV, int SVOffset, + bool isVolatile, unsigned Alignment) { + SDValue Undef = getNode(ISD::UNDEF, Ptr.getValueType()); return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, Chain, Ptr, Undef, SV, SVOffset, VT, isVolatile, Alignment); } -SDOperand SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, MVT VT, - SDOperand Chain, SDOperand Ptr, - const Value *SV, - int SVOffset, MVT EVT, - bool isVolatile, unsigned Alignment) { - SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); +SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, MVT VT, + SDValue Chain, SDValue Ptr, + const Value *SV, + int SVOffset, MVT EVT, + bool isVolatile, unsigned Alignment) { + SDValue Undef = getNode(ISD::UNDEF, Ptr.getValueType()); return getLoad(ISD::UNINDEXED, ExtType, VT, Chain, Ptr, Undef, SV, SVOffset, EVT, isVolatile, Alignment); } -SDOperand -SelectionDAG::getIndexedLoad(SDOperand OrigLoad, SDOperand Base, - SDOperand Offset, ISD::MemIndexedMode AM) { +SDValue +SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDValue Base, + SDValue Offset, ISD::MemIndexedMode AM) { LoadSDNode *LD = cast(OrigLoad); assert(LD->getOffset().getOpcode() == ISD::UNDEF && "Load is already a indexed load!"); @@ -3158,47 +3501,38 @@ SelectionDAG::getIndexedLoad(SDOperand OrigLoad, SDOperand Base, LD->isVolatile(), LD->getAlignment()); } -SDOperand SelectionDAG::getStore(SDOperand Chain, SDOperand Val, - SDOperand Ptr, const Value *SV, int SVOffset, - bool isVolatile, unsigned Alignment) { +SDValue SelectionDAG::getStore(SDValue Chain, SDValue Val, + SDValue Ptr, const Value *SV, int SVOffset, + bool isVolatile, unsigned Alignment) { MVT VT = Val.getValueType(); - if (Alignment == 0) { // Ensure that codegen never sees alignment 0 - const Type *Ty = 0; - if (VT != MVT::iPTR) { - Ty = VT.getTypeForMVT(); - } else if (SV) { - const PointerType *PT = dyn_cast(SV->getType()); - assert(PT && "Value for store must be a pointer"); - Ty = PT->getElementType(); - } - assert(Ty && "Could not get type information for store"); - Alignment = TLI.getTargetData()->getABITypeAlignment(Ty); - } + if (Alignment == 0) // Ensure that codegen never sees alignment 0 + Alignment = getMVTAlignment(VT); + SDVTList VTs = getVTList(MVT::Other); - SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); - SDOperand Ops[] = { Chain, Val, Ptr, Undef }; + SDValue Undef = getNode(ISD::UNDEF, Ptr.getValueType()); + SDValue Ops[] = { Chain, Val, Ptr, Undef }; FoldingSetNodeID ID; AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); ID.AddInteger(ISD::UNINDEXED); ID.AddInteger(false); ID.AddInteger(VT.getRawBits()); - ID.AddInteger(Alignment); - ID.AddInteger(isVolatile); + ID.AddInteger(encodeMemSDNodeFlags(isVolatile, Alignment)); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new StoreSDNode(Ops, VTs, ISD::UNINDEXED, false, - VT, SV, SVOffset, Alignment, isVolatile); + return SDValue(E, 0); + SDNode *N = NodeAllocator.Allocate(); + new (N) StoreSDNode(Ops, VTs, ISD::UNINDEXED, false, + VT, SV, SVOffset, Alignment, isVolatile); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getTruncStore(SDOperand Chain, SDOperand Val, - SDOperand Ptr, const Value *SV, - int SVOffset, MVT SVT, - bool isVolatile, unsigned Alignment) { +SDValue SelectionDAG::getTruncStore(SDValue Chain, SDValue Val, + SDValue Ptr, const Value *SV, + int SVOffset, MVT SVT, + bool isVolatile, unsigned Alignment) { MVT VT = Val.getValueType(); if (VT == SVT) @@ -3208,74 +3542,81 @@ SDOperand SelectionDAG::getTruncStore(SDOperand Chain, SDOperand Val, assert(VT.isInteger() == SVT.isInteger() && "Can't do FP-INT conversion!"); - if (Alignment == 0) { // Ensure that codegen never sees alignment 0 - const Type *Ty = 0; - if (VT != MVT::iPTR) { - Ty = VT.getTypeForMVT(); - } else if (SV) { - const PointerType *PT = dyn_cast(SV->getType()); - assert(PT && "Value for store must be a pointer"); - Ty = PT->getElementType(); - } - assert(Ty && "Could not get type information for store"); - Alignment = TLI.getTargetData()->getABITypeAlignment(Ty); - } + if (Alignment == 0) // Ensure that codegen never sees alignment 0 + Alignment = getMVTAlignment(VT); + SDVTList VTs = getVTList(MVT::Other); - SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); - SDOperand Ops[] = { Chain, Val, Ptr, Undef }; + SDValue Undef = getNode(ISD::UNDEF, Ptr.getValueType()); + SDValue Ops[] = { Chain, Val, Ptr, Undef }; FoldingSetNodeID ID; AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); ID.AddInteger(ISD::UNINDEXED); ID.AddInteger(1); ID.AddInteger(SVT.getRawBits()); - ID.AddInteger(Alignment); - ID.AddInteger(isVolatile); + ID.AddInteger(encodeMemSDNodeFlags(isVolatile, Alignment)); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new StoreSDNode(Ops, VTs, ISD::UNINDEXED, true, - SVT, SV, SVOffset, Alignment, isVolatile); + return SDValue(E, 0); + SDNode *N = NodeAllocator.Allocate(); + new (N) StoreSDNode(Ops, VTs, ISD::UNINDEXED, true, + SVT, SV, SVOffset, Alignment, isVolatile); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand -SelectionDAG::getIndexedStore(SDOperand OrigStore, SDOperand Base, - SDOperand Offset, ISD::MemIndexedMode AM) { +SDValue +SelectionDAG::getIndexedStore(SDValue OrigStore, SDValue Base, + SDValue Offset, ISD::MemIndexedMode AM) { StoreSDNode *ST = cast(OrigStore); assert(ST->getOffset().getOpcode() == ISD::UNDEF && "Store is already a indexed store!"); SDVTList VTs = getVTList(Base.getValueType(), MVT::Other); - SDOperand Ops[] = { ST->getChain(), ST->getValue(), Base, Offset }; + SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset }; FoldingSetNodeID ID; AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); ID.AddInteger(AM); ID.AddInteger(ST->isTruncatingStore()); ID.AddInteger(ST->getMemoryVT().getRawBits()); - ID.AddInteger(ST->getAlignment()); - ID.AddInteger(ST->isVolatile()); + ID.AddInteger(ST->getRawFlags()); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new StoreSDNode(Ops, VTs, AM, - ST->isTruncatingStore(), ST->getMemoryVT(), - ST->getSrcValue(), ST->getSrcValueOffset(), - ST->getAlignment(), ST->isVolatile()); + return SDValue(E, 0); + SDNode *N = NodeAllocator.Allocate(); + new (N) StoreSDNode(Ops, VTs, AM, + ST->isTruncatingStore(), ST->getMemoryVT(), + ST->getSrcValue(), ST->getSrcValueOffset(), + ST->getAlignment(), ST->isVolatile()); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); - return SDOperand(N, 0); + return SDValue(N, 0); } -SDOperand SelectionDAG::getVAArg(MVT VT, - SDOperand Chain, SDOperand Ptr, - SDOperand SV) { - SDOperand Ops[] = { Chain, Ptr, SV }; +SDValue SelectionDAG::getVAArg(MVT VT, + SDValue Chain, SDValue Ptr, + SDValue SV) { + SDValue Ops[] = { Chain, Ptr, SV }; return getNode(ISD::VAARG, getVTList(VT, MVT::Other), Ops, 3); } -SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, - SDOperandPtr Ops, unsigned NumOps) { +SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, + const SDUse *Ops, unsigned NumOps) { + switch (NumOps) { + case 0: return getNode(Opcode, VT); + case 1: return getNode(Opcode, VT, Ops[0]); + case 2: return getNode(Opcode, VT, Ops[0], Ops[1]); + case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]); + default: break; + } + + // Copy from an SDUse array into an SDValue array for use with + // the regular getNode logic. + SmallVector NewOps(Ops, Ops + NumOps); + return getNode(Opcode, VT, &NewOps[0], NumOps); +} + +SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, + const SDValue *Ops, unsigned NumOps) { switch (NumOps) { case 0: return getNode(Opcode, VT); case 1: return getNode(Opcode, VT, Ops[0]); @@ -3312,33 +3653,38 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - N = new SDNode(Opcode, VTs, Ops, NumOps); + return SDValue(E, 0); + N = NodeAllocator.Allocate(); + new (N) SDNode(Opcode, VTs, Ops, NumOps); CSEMap.InsertNode(N, IP); } else { - N = new SDNode(Opcode, VTs, Ops, NumOps); + N = NodeAllocator.Allocate(); + new (N) SDNode(Opcode, VTs, Ops, NumOps); } AllNodes.push_back(N); - return SDOperand(N, 0); +#ifndef NDEBUG + VerifyNode(N); +#endif + return SDValue(N, 0); } -SDOperand SelectionDAG::getNode(unsigned Opcode, - std::vector &ResultTys, - SDOperandPtr Ops, unsigned NumOps) { +SDValue SelectionDAG::getNode(unsigned Opcode, + const std::vector &ResultTys, + const SDValue *Ops, unsigned NumOps) { return getNode(Opcode, getNodeValueTypes(ResultTys), ResultTys.size(), Ops, NumOps); } -SDOperand SelectionDAG::getNode(unsigned Opcode, - const MVT *VTs, unsigned NumVTs, - SDOperandPtr Ops, unsigned NumOps) { +SDValue SelectionDAG::getNode(unsigned Opcode, + const MVT *VTs, unsigned NumVTs, + const SDValue *Ops, unsigned NumOps) { if (NumVTs == 1) return getNode(Opcode, VTs[0], Ops, NumOps); return getNode(Opcode, makeVTList(VTs, NumVTs), Ops, NumOps); } -SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, - SDOperandPtr Ops, unsigned NumOps) { +SDValue SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, + const SDValue *Ops, unsigned NumOps) { if (VTList.NumVTs == 1) return getNode(Opcode, VTList.VTs[0], Ops, NumOps); @@ -3372,63 +3718,76 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - if (NumOps == 1) - N = new UnarySDNode(Opcode, VTList, Ops[0]); - else if (NumOps == 2) - N = new BinarySDNode(Opcode, VTList, Ops[0], Ops[1]); - else if (NumOps == 3) - N = new TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]); - else - N = new SDNode(Opcode, VTList, Ops, NumOps); + return SDValue(E, 0); + if (NumOps == 1) { + N = NodeAllocator.Allocate(); + new (N) UnarySDNode(Opcode, VTList, Ops[0]); + } else if (NumOps == 2) { + N = NodeAllocator.Allocate(); + new (N) BinarySDNode(Opcode, VTList, Ops[0], Ops[1]); + } else if (NumOps == 3) { + N = NodeAllocator.Allocate(); + new (N) TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]); + } else { + N = NodeAllocator.Allocate(); + new (N) SDNode(Opcode, VTList, Ops, NumOps); + } CSEMap.InsertNode(N, IP); } else { - if (NumOps == 1) - N = new UnarySDNode(Opcode, VTList, Ops[0]); - else if (NumOps == 2) - N = new BinarySDNode(Opcode, VTList, Ops[0], Ops[1]); - else if (NumOps == 3) - N = new TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]); - else - N = new SDNode(Opcode, VTList, Ops, NumOps); + if (NumOps == 1) { + N = NodeAllocator.Allocate(); + new (N) UnarySDNode(Opcode, VTList, Ops[0]); + } else if (NumOps == 2) { + N = NodeAllocator.Allocate(); + new (N) BinarySDNode(Opcode, VTList, Ops[0], Ops[1]); + } else if (NumOps == 3) { + N = NodeAllocator.Allocate(); + new (N) TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]); + } else { + N = NodeAllocator.Allocate(); + new (N) SDNode(Opcode, VTList, Ops, NumOps); + } } AllNodes.push_back(N); - return SDOperand(N, 0); +#ifndef NDEBUG + VerifyNode(N); +#endif + return SDValue(N, 0); } -SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList) { - return getNode(Opcode, VTList, (SDOperand*)0, 0); +SDValue SelectionDAG::getNode(unsigned Opcode, SDVTList VTList) { + return getNode(Opcode, VTList, 0, 0); } -SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, - SDOperand N1) { - SDOperand Ops[] = { N1 }; +SDValue SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, + SDValue N1) { + SDValue Ops[] = { N1 }; return getNode(Opcode, VTList, Ops, 1); } -SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, - SDOperand N1, SDOperand N2) { - SDOperand Ops[] = { N1, N2 }; +SDValue SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, + SDValue N1, SDValue N2) { + SDValue Ops[] = { N1, N2 }; return getNode(Opcode, VTList, Ops, 2); } -SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, - SDOperand N1, SDOperand N2, SDOperand N3) { - SDOperand Ops[] = { N1, N2, N3 }; +SDValue SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, + SDValue N1, SDValue N2, SDValue N3) { + SDValue Ops[] = { N1, N2, N3 }; return getNode(Opcode, VTList, Ops, 3); } -SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, - SDOperand N1, SDOperand N2, SDOperand N3, - SDOperand N4) { - SDOperand Ops[] = { N1, N2, N3, N4 }; +SDValue SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, + SDValue N1, SDValue N2, SDValue N3, + SDValue N4) { + SDValue Ops[] = { N1, N2, N3, N4 }; return getNode(Opcode, VTList, Ops, 4); } -SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, - SDOperand N1, SDOperand N2, SDOperand N3, - SDOperand N4, SDOperand N5) { - SDOperand Ops[] = { N1, N2, N3, N4, N5 }; +SDValue SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, + SDValue N1, SDValue N2, SDValue N3, + SDValue N4, SDValue N5) { + SDValue Ops[] = { N1, N2, N3, N4, N5 }; return getNode(Opcode, VTList, Ops, 5); } @@ -3437,31 +3796,33 @@ SDVTList SelectionDAG::getVTList(MVT VT) { } SDVTList SelectionDAG::getVTList(MVT VT1, MVT VT2) { - for (std::list >::iterator I = VTList.begin(), - E = VTList.end(); I != E; ++I) { - if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2) - return makeVTList(&(*I)[0], 2); - } - std::vector V; - V.push_back(VT1); - V.push_back(VT2); - VTList.push_front(V); - return makeVTList(&(*VTList.begin())[0], 2); -} -SDVTList SelectionDAG::getVTList(MVT VT1, MVT VT2, - MVT VT3) { - for (std::list >::iterator I = VTList.begin(), - E = VTList.end(); I != E; ++I) { - if (I->size() == 3 && (*I)[0] == VT1 && (*I)[1] == VT2 && - (*I)[2] == VT3) - return makeVTList(&(*I)[0], 3); - } - std::vector V; - V.push_back(VT1); - V.push_back(VT2); - V.push_back(VT3); - VTList.push_front(V); - return makeVTList(&(*VTList.begin())[0], 3); + for (std::vector::reverse_iterator I = VTList.rbegin(), + E = VTList.rend(); I != E; ++I) + if (I->NumVTs == 2 && I->VTs[0] == VT1 && I->VTs[1] == VT2) + return *I; + + MVT *Array = Allocator.Allocate(2); + Array[0] = VT1; + Array[1] = VT2; + SDVTList Result = makeVTList(Array, 2); + VTList.push_back(Result); + return Result; +} + +SDVTList SelectionDAG::getVTList(MVT VT1, MVT VT2, MVT VT3) { + for (std::vector::reverse_iterator I = VTList.rbegin(), + E = VTList.rend(); I != E; ++I) + if (I->NumVTs == 3 && I->VTs[0] == VT1 && I->VTs[1] == VT2 && + I->VTs[2] == VT3) + return *I; + + MVT *Array = Allocator.Allocate(3); + Array[0] = VT1; + Array[1] = VT2; + Array[2] = VT3; + SDVTList Result = makeVTList(Array, 3); + VTList.push_back(Result); + return Result; } SDVTList SelectionDAG::getVTList(const MVT *VTs, unsigned NumVTs) { @@ -3473,22 +3834,26 @@ SDVTList SelectionDAG::getVTList(const MVT *VTs, unsigned NumVTs) { default: break; } - for (std::list >::iterator I = VTList.begin(), - E = VTList.end(); I != E; ++I) { - if (I->size() != NumVTs || VTs[0] != (*I)[0] || VTs[1] != (*I)[1]) continue; + for (std::vector::reverse_iterator I = VTList.rbegin(), + E = VTList.rend(); I != E; ++I) { + if (I->NumVTs != NumVTs || VTs[0] != I->VTs[0] || VTs[1] != I->VTs[1]) + continue; bool NoMatch = false; for (unsigned i = 2; i != NumVTs; ++i) - if (VTs[i] != (*I)[i]) { + if (VTs[i] != I->VTs[i]) { NoMatch = true; break; } if (!NoMatch) - return makeVTList(&*I->begin(), NumVTs); + return *I; } - VTList.push_front(std::vector(VTs, VTs+NumVTs)); - return makeVTList(&*VTList.begin()->begin(), NumVTs); + MVT *Array = Allocator.Allocate(NumVTs); + std::copy(VTs, VTs+NumVTs, Array); + SDVTList Result = makeVTList(Array, NumVTs); + VTList.push_back(Result); + return Result; } @@ -3498,9 +3863,8 @@ SDVTList SelectionDAG::getVTList(const MVT *VTs, unsigned NumVTs) { /// already exists. If the resultant node does not exist in the DAG, the /// input node is returned. As a degenerate case, if you specify the same /// input operands as the node already has, the input node is returned. -SDOperand SelectionDAG:: -UpdateNodeOperands(SDOperand InN, SDOperand Op) { - SDNode *N = InN.Val; +SDValue SelectionDAG::UpdateNodeOperands(SDValue InN, SDValue Op) { + SDNode *N = InN.getNode(); assert(N->getNumOperands() == 1 && "Update with wrong number of operands"); // Check to see if there is no change. @@ -3509,26 +3873,27 @@ UpdateNodeOperands(SDOperand InN, SDOperand Op) { // See if the modified node already exists. void *InsertPos = 0; if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos)) - return SDOperand(Existing, InN.ResNo); + return SDValue(Existing, InN.getResNo()); - // Nope it doesn't. Remove the node from it's current place in the maps. + // 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); N->OperandList[0] = Op; N->OperandList[0].setUser(N); - Op.Val->addUser(0, N); + Op.getNode()->addUser(0, N); // If this gets put into a CSE map, add it. if (InsertPos) CSEMap.InsertNode(N, InsertPos); return InN; } -SDOperand SelectionDAG:: -UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) { - SDNode *N = InN.Val; +SDValue SelectionDAG:: +UpdateNodeOperands(SDValue InN, SDValue Op1, SDValue Op2) { + SDNode *N = InN.getNode(); assert(N->getNumOperands() == 2 && "Update with wrong number of operands"); // Check to see if there is no change. @@ -3538,24 +3903,25 @@ UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) { // See if the modified node already exists. void *InsertPos = 0; if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos)) - return SDOperand(Existing, InN.ResNo); + return SDValue(Existing, InN.getResNo()); - // Nope it doesn't. Remove the node from it's current place in the maps. + // 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) { N->OperandList[0].getVal()->removeUser(0, N); N->OperandList[0] = Op1; N->OperandList[0].setUser(N); - Op1.Val->addUser(0, N); + Op1.getNode()->addUser(0, N); } if (N->OperandList[1] != Op2) { N->OperandList[1].getVal()->removeUser(1, N); N->OperandList[1] = Op2; N->OperandList[1].setUser(N); - Op2.Val->addUser(1, N); + Op2.getNode()->addUser(1, N); } // If this gets put into a CSE map, add it. @@ -3563,29 +3929,29 @@ UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) { return InN; } -SDOperand SelectionDAG:: -UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3) { - SDOperand Ops[] = { Op1, Op2, Op3 }; +SDValue SelectionDAG:: +UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, SDValue Op3) { + SDValue Ops[] = { Op1, Op2, Op3 }; return UpdateNodeOperands(N, Ops, 3); } -SDOperand SelectionDAG:: -UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, - SDOperand Op3, SDOperand Op4) { - SDOperand Ops[] = { Op1, Op2, Op3, Op4 }; +SDValue SelectionDAG:: +UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, + SDValue Op3, SDValue Op4) { + SDValue Ops[] = { Op1, Op2, Op3, Op4 }; return UpdateNodeOperands(N, Ops, 4); } -SDOperand SelectionDAG:: -UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, - SDOperand Op3, SDOperand Op4, SDOperand Op5) { - SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5 }; +SDValue SelectionDAG:: +UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, + SDValue Op3, SDValue Op4, SDValue Op5) { + SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 }; return UpdateNodeOperands(N, Ops, 5); } -SDOperand SelectionDAG:: -UpdateNodeOperands(SDOperand InN, SDOperandPtr Ops, unsigned NumOps) { - SDNode *N = InN.Val; +SDValue SelectionDAG:: +UpdateNodeOperands(SDValue InN, const SDValue *Ops, unsigned NumOps) { + SDNode *N = InN.getNode(); assert(N->getNumOperands() == NumOps && "Update with wrong number of operands"); @@ -3604,11 +3970,12 @@ UpdateNodeOperands(SDOperand InN, SDOperandPtr Ops, unsigned NumOps) { // See if the modified node already exists. void *InsertPos = 0; if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos)) - return SDOperand(Existing, InN.ResNo); + return SDValue(Existing, InN.getResNo()); // 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) { @@ -3616,7 +3983,7 @@ UpdateNodeOperands(SDOperand InN, SDOperandPtr Ops, unsigned NumOps) { N->OperandList[i].getVal()->removeUser(i, N); N->OperandList[i] = Ops[i]; N->OperandList[i].setUser(N); - Ops[i].Val->addUser(i, N); + Ops[i].getNode()->addUser(i, N); } } @@ -3625,178 +3992,269 @@ UpdateNodeOperands(SDOperand InN, SDOperandPtr Ops, unsigned NumOps) { return InN; } -/// MorphNodeTo - This frees the operands of the current node, resets the -/// opcode, types, and operands to the specified value. This should only be -/// used by the SelectionDAG class. -void SDNode::MorphNodeTo(unsigned Opc, SDVTList L, - SDOperandPtr Ops, unsigned NumOps) { - NodeType = Opc; - ValueList = L.VTs; - NumValues = L.NumVTs; - - // Clear the operands list, updating used nodes to remove this from their - // use list. +/// DropOperands - Release the operands and set this node to have +/// zero operands. +void SDNode::DropOperands() { + // Unlike the code in MorphNodeTo that does this, we don't need to + // watch for dead nodes here. for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) I->getVal()->removeUser(std::distance(op_begin(), I), this); - - // If NumOps is larger than the # of operands we currently have, reallocate - // the operand list. - if (NumOps > NumOperands) { - if (OperandsNeedDelete) { - delete [] OperandList; - } - OperandList = new SDUse[NumOps]; - OperandsNeedDelete = true; - } - - // Assign the new operands. - NumOperands = NumOps; - - for (unsigned i = 0, e = NumOps; i != e; ++i) { - OperandList[i] = Ops[i]; - OperandList[i].setUser(this); - SDNode *N = OperandList[i].getVal(); - N->addUser(i, this); - ++N->UsesSize; - } + + NumOperands = 0; } -/// SelectNodeTo - These are used for target selectors to *mutate* the -/// specified node to have the specified return type, Target opcode, and -/// operands. Note that target opcodes are stored as -/// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field. +/// SelectNodeTo - These are wrappers around MorphNodeTo that accept a +/// machine opcode. /// -/// Note that SelectNodeTo returns the resultant node. If there is already a -/// node of the specified opcode and operands, it returns that node instead of -/// the current one. -SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, MVT VT) { SDVTList VTs = getVTList(VT); - FoldingSetNodeID ID; - AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, (SDOperand*)0, 0); - void *IP = 0; - if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) - return ON; - - RemoveNodeFromCSEMaps(N); - - N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, SDOperandPtr(), 0); - - CSEMap.InsertNode(N, IP); - return N; + return SelectNodeTo(N, MachineOpc, VTs, 0, 0); } -SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT VT, SDOperand Op1) { - // If an identical node already exists, use it. +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, + MVT VT, SDValue Op1) { SDVTList VTs = getVTList(VT); - SDOperand Ops[] = { Op1 }; - - FoldingSetNodeID ID; - AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 1); - void *IP = 0; - if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) - return ON; - - RemoveNodeFromCSEMaps(N); - N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 1); - CSEMap.InsertNode(N, IP); - return N; + SDValue Ops[] = { Op1 }; + return SelectNodeTo(N, MachineOpc, VTs, Ops, 1); } -SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT VT, SDOperand Op1, - SDOperand Op2) { - // If an identical node already exists, use it. +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, + MVT VT, SDValue Op1, + SDValue Op2) { SDVTList VTs = getVTList(VT); - SDOperand Ops[] = { Op1, Op2 }; - - FoldingSetNodeID ID; - AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2); - void *IP = 0; - if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) - return ON; - - RemoveNodeFromCSEMaps(N); - - N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2); - - CSEMap.InsertNode(N, IP); // Memoize the new node. - return N; + SDValue Ops[] = { Op1, Op2 }; + return SelectNodeTo(N, MachineOpc, VTs, Ops, 2); } -SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT VT, SDOperand Op1, - SDOperand Op2, SDOperand Op3) { - // If an identical node already exists, use it. +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, + MVT VT, SDValue Op1, + SDValue Op2, SDValue Op3) { SDVTList VTs = getVTList(VT); - SDOperand Ops[] = { Op1, Op2, Op3 }; - FoldingSetNodeID ID; - AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3); - void *IP = 0; - if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) - return ON; - - RemoveNodeFromCSEMaps(N); - - N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3); - - CSEMap.InsertNode(N, IP); // Memoize the new node. - return N; + SDValue Ops[] = { Op1, Op2, Op3 }; + return SelectNodeTo(N, MachineOpc, VTs, Ops, 3); } -SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT VT, SDOperandPtr Ops, +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, + MVT VT, const SDValue *Ops, unsigned NumOps) { - // If an identical node already exists, use it. SDVTList VTs = getVTList(VT); - FoldingSetNodeID ID; - AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps); - void *IP = 0; - if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) - return ON; - - RemoveNodeFromCSEMaps(N); - N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps); - - CSEMap.InsertNode(N, IP); // Memoize the new node. - return N; + return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps); +} + +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, + MVT VT1, MVT VT2, const SDValue *Ops, + unsigned NumOps) { + SDVTList VTs = getVTList(VT1, VT2); + return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps); +} + +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, + MVT VT1, MVT VT2) { + SDVTList VTs = getVTList(VT1, VT2); + return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0); } -SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, + MVT VT1, MVT VT2, MVT VT3, + const SDValue *Ops, unsigned NumOps) { + SDVTList VTs = getVTList(VT1, VT2, VT3); + return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps); +} + +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, MVT VT1, MVT VT2, - SDOperand Op1, SDOperand Op2) { + SDValue Op1) { SDVTList VTs = getVTList(VT1, VT2); - FoldingSetNodeID ID; - SDOperand Ops[] = { Op1, Op2 }; - AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2); - void *IP = 0; - if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) - return ON; + SDValue Ops[] = { Op1 }; + return SelectNodeTo(N, MachineOpc, VTs, Ops, 1); +} - RemoveNodeFromCSEMaps(N); - N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2); - CSEMap.InsertNode(N, IP); // Memoize the new node. - return N; +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, + MVT VT1, MVT VT2, + SDValue Op1, SDValue Op2) { + SDVTList VTs = getVTList(VT1, VT2); + SDValue Ops[] = { Op1, Op2 }; + return SelectNodeTo(N, MachineOpc, VTs, Ops, 2); } -SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, MVT VT1, MVT VT2, - SDOperand Op1, SDOperand Op2, - SDOperand Op3) { - // If an identical node already exists, use it. + SDValue Op1, SDValue Op2, + SDValue Op3) { SDVTList VTs = getVTList(VT1, VT2); - SDOperand Ops[] = { Op1, Op2, Op3 }; - FoldingSetNodeID ID; - AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3); + SDValue Ops[] = { Op1, Op2, Op3 }; + return SelectNodeTo(N, MachineOpc, VTs, Ops, 3); +} + +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, + SDVTList VTs, const SDValue *Ops, + unsigned NumOps) { + return MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps); +} + +SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, + MVT VT) { + SDVTList VTs = getVTList(VT); + return MorphNodeTo(N, Opc, VTs, 0, 0); +} + +SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, + MVT VT, SDValue Op1) { + SDVTList VTs = getVTList(VT); + SDValue Ops[] = { Op1 }; + return MorphNodeTo(N, Opc, VTs, Ops, 1); +} + +SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, + MVT VT, SDValue Op1, + SDValue Op2) { + SDVTList VTs = getVTList(VT); + SDValue Ops[] = { Op1, Op2 }; + return MorphNodeTo(N, Opc, VTs, Ops, 2); +} + +SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, + MVT VT, SDValue Op1, + SDValue Op2, SDValue Op3) { + SDVTList VTs = getVTList(VT); + SDValue Ops[] = { Op1, Op2, Op3 }; + return MorphNodeTo(N, Opc, VTs, Ops, 3); +} + +SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, + MVT VT, const SDValue *Ops, + unsigned NumOps) { + SDVTList VTs = getVTList(VT); + return MorphNodeTo(N, Opc, VTs, Ops, NumOps); +} + +SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, + MVT VT1, MVT VT2, const SDValue *Ops, + unsigned NumOps) { + SDVTList VTs = getVTList(VT1, VT2); + return MorphNodeTo(N, Opc, VTs, Ops, NumOps); +} + +SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, + MVT VT1, MVT VT2) { + SDVTList VTs = getVTList(VT1, VT2); + return MorphNodeTo(N, Opc, VTs, (SDValue *)0, 0); +} + +SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, + MVT VT1, MVT VT2, MVT VT3, + const SDValue *Ops, unsigned NumOps) { + SDVTList VTs = getVTList(VT1, VT2, VT3); + return MorphNodeTo(N, Opc, VTs, Ops, NumOps); +} + +SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, + MVT VT1, MVT VT2, + SDValue Op1) { + SDVTList VTs = getVTList(VT1, VT2); + SDValue Ops[] = { Op1 }; + return MorphNodeTo(N, Opc, VTs, Ops, 1); +} + +SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, + MVT VT1, MVT VT2, + SDValue Op1, SDValue Op2) { + SDVTList VTs = getVTList(VT1, VT2); + SDValue Ops[] = { Op1, Op2 }; + return MorphNodeTo(N, Opc, VTs, Ops, 2); +} + +SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, + MVT VT1, MVT VT2, + SDValue Op1, SDValue Op2, + SDValue Op3) { + SDVTList VTs = getVTList(VT1, VT2); + SDValue Ops[] = { Op1, Op2, Op3 }; + return MorphNodeTo(N, Opc, VTs, Ops, 3); +} + +/// MorphNodeTo - These *mutate* the specified node to have the specified +/// return type, opcode, and operands. +/// +/// Note that MorphNodeTo returns the resultant node. If there is already a +/// node of the specified opcode and operands, it returns that node instead of +/// the current one. +/// +/// Using MorphNodeTo is faster than creating a new node and swapping it in +/// with ReplaceAllUsesWith both because it often avoids allocating a new +/// node, and because it doesn't require CSE recalculation for any of +/// the node's users. +/// +SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, + SDVTList VTs, const SDValue *Ops, + unsigned NumOps) { + // If an identical node already exists, use it. void *IP = 0; - if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) - return ON; + if (VTs.VTs[VTs.NumVTs-1] != MVT::Flag) { + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opc, VTs, Ops, NumOps); + if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) + return ON; + } - RemoveNodeFromCSEMaps(N); + if (!RemoveNodeFromCSEMaps(N)) + IP = 0; - N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3); - CSEMap.InsertNode(N, IP); // Memoize the new node. + // Start the morphing. + N->NodeType = Opc; + N->ValueList = VTs.VTs; + N->NumValues = VTs.NumVTs; + + // Clear the operands list, updating used nodes to remove this from their + // use list. Keep track of any operands that become dead as a result. + SmallPtrSet DeadNodeSet; + for (SDNode::op_iterator B = N->op_begin(), I = B, E = N->op_end(); + I != E; ++I) { + SDNode *Used = I->getVal(); + Used->removeUser(std::distance(B, I), N); + if (Used->use_empty()) + DeadNodeSet.insert(Used); + } + + // If NumOps is larger than the # of operands we currently have, reallocate + // the operand list. + 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 + // the operands directly out of a pool with no recycling metadata. + N->OperandList = OperandAllocator.Allocate(NumOps); + N->OperandsNeedDelete = false; + } else { + N->OperandList = new SDUse[NumOps]; + N->OperandsNeedDelete = true; + } + } + + // Assign the new operands. + N->NumOperands = NumOps; + for (unsigned i = 0, e = NumOps; i != e; ++i) { + N->OperandList[i] = Ops[i]; + N->OperandList[i].setUser(N); + SDNode *ToUse = N->OperandList[i].getVal(); + ToUse->addUser(i, N); + } + + // Delete any nodes that are still dead after adding the uses for the + // new operands. + SmallVector DeadNodes; + for (SmallPtrSet::iterator I = DeadNodeSet.begin(), + E = DeadNodeSet.end(); I != E; ++I) + if ((*I)->use_empty()) + DeadNodes.push_back(*I); + RemoveDeadNodes(DeadNodes); + + if (IP) + CSEMap.InsertNode(N, IP); // Memoize the new node. return N; } @@ -3808,94 +4266,94 @@ SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, /// node of the specified opcode and operands, it returns that node instead of /// the current one. SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT) { - return getNode(ISD::BUILTIN_OP_END+Opcode, VT).Val; + return getNode(~Opcode, VT).getNode(); } -SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT, SDOperand Op1) { - return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1).Val; +SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT, SDValue Op1) { + return getNode(~Opcode, VT, Op1).getNode(); } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT, - SDOperand Op1, SDOperand Op2) { - return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2).Val; + SDValue Op1, SDValue Op2) { + return getNode(~Opcode, VT, Op1, Op2).getNode(); } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT, - SDOperand Op1, SDOperand Op2, - SDOperand Op3) { - return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val; + SDValue Op1, SDValue Op2, + SDValue Op3) { + return getNode(~Opcode, VT, Op1, Op2, Op3).getNode(); } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT, - SDOperandPtr Ops, unsigned NumOps) { - return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, NumOps).Val; + const SDValue *Ops, unsigned NumOps) { + return getNode(~Opcode, VT, Ops, NumOps).getNode(); } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2) { const MVT *VTs = getNodeValueTypes(VT1, VT2); - SDOperand Op; - return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op, 0).Val; + SDValue Op; + return getNode(~Opcode, VTs, 2, &Op, 0).getNode(); } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, - MVT VT2, SDOperand Op1) { + MVT VT2, SDValue Op1) { const MVT *VTs = getNodeValueTypes(VT1, VT2); - return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op1, 1).Val; + return getNode(~Opcode, VTs, 2, &Op1, 1).getNode(); } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, - MVT VT2, SDOperand Op1, - SDOperand Op2) { + MVT VT2, SDValue Op1, + SDValue Op2) { const MVT *VTs = getNodeValueTypes(VT1, VT2); - SDOperand Ops[] = { Op1, Op2 }; - return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 2).Val; + SDValue Ops[] = { Op1, Op2 }; + return getNode(~Opcode, VTs, 2, Ops, 2).getNode(); } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, - MVT VT2, SDOperand Op1, - SDOperand Op2, SDOperand Op3) { + MVT VT2, SDValue Op1, + SDValue Op2, SDValue Op3) { const MVT *VTs = getNodeValueTypes(VT1, VT2); - SDOperand Ops[] = { Op1, Op2, Op3 }; - return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 3).Val; + SDValue Ops[] = { Op1, Op2, Op3 }; + return getNode(~Opcode, VTs, 2, Ops, 3).getNode(); } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, - SDOperandPtr Ops, unsigned NumOps) { + const SDValue *Ops, unsigned NumOps) { const MVT *VTs = getNodeValueTypes(VT1, VT2); - return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, NumOps).Val; + return getNode(~Opcode, VTs, 2, Ops, NumOps).getNode(); } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, - SDOperand Op1, SDOperand Op2) { + SDValue Op1, SDValue Op2) { const MVT *VTs = getNodeValueTypes(VT1, VT2, VT3); - SDOperand Ops[] = { Op1, Op2 }; - return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 2).Val; + SDValue Ops[] = { Op1, Op2 }; + return getNode(~Opcode, VTs, 3, Ops, 2).getNode(); } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, - SDOperand Op1, SDOperand Op2, - SDOperand Op3) { + SDValue Op1, SDValue Op2, + SDValue Op3) { const MVT *VTs = getNodeValueTypes(VT1, VT2, VT3); - SDOperand Ops[] = { Op1, Op2, Op3 }; - return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 3).Val; + SDValue Ops[] = { Op1, Op2, Op3 }; + return getNode(~Opcode, VTs, 3, Ops, 3).getNode(); } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, - SDOperandPtr Ops, unsigned NumOps) { + const SDValue *Ops, unsigned NumOps) { const MVT *VTs = getNodeValueTypes(VT1, VT2, VT3); - return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, NumOps).Val; + return getNode(~Opcode, VTs, 3, Ops, NumOps).getNode(); } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, MVT VT4, - SDOperandPtr Ops, unsigned NumOps) { + const SDValue *Ops, unsigned NumOps) { std::vector VTList; VTList.push_back(VT1); VTList.push_back(VT2); VTList.push_back(VT3); VTList.push_back(VT4); const MVT *VTs = getNodeValueTypes(VTList); - return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 4, Ops, NumOps).Val; + return getNode(~Opcode, VTs, 4, Ops, NumOps).getNode(); } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, - std::vector &ResultTys, - SDOperandPtr Ops, unsigned NumOps) { + const std::vector &ResultTys, + const SDValue *Ops, unsigned NumOps) { const MVT *VTs = getNodeValueTypes(ResultTys); - return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, ResultTys.size(), - Ops, NumOps).Val; + return getNode(~Opcode, VTs, ResultTys.size(), + Ops, NumOps).getNode(); } /// getNodeIfExists - Get the specified node if it's already available, or /// else return NULL. SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList, - SDOperandPtr Ops, unsigned NumOps) { + const SDValue *Ops, unsigned NumOps) { if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) { FoldingSetNodeID ID; AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps); @@ -3912,16 +4370,16 @@ SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList, /// /// This version assumes From has a single result value. /// -void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand To, +void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To, DAGUpdateListener *UpdateListener) { - SDNode *From = FromN.Val; - assert(From->getNumValues() == 1 && FromN.ResNo == 0 && + SDNode *From = FromN.getNode(); + assert(From->getNumValues() == 1 && FromN.getResNo() == 0 && "Cannot replace with this method!"); - assert(From != To.Val && "Cannot replace uses of with self"); + assert(From != To.getNode() && "Cannot replace uses of with self"); while (!From->use_empty()) { SDNode::use_iterator UI = From->use_begin(); - SDNode *U = UI->getUser(); + SDNode *U = *UI; // This node is about to morph, remove its old self from the CSE maps. RemoveNodeFromCSEMaps(U); @@ -3932,7 +4390,7 @@ void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand To, From->removeUser(operandNum, U); *I = To; I->setUser(U); - To.Val->addUser(operandNum, U); + To.getNode()->addUser(operandNum, U); } // Now that we have modified U, add it back to the CSE maps. If it already @@ -3960,16 +4418,17 @@ void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand To, /// void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To, DAGUpdateListener *UpdateListener) { - assert(From != To && "Cannot replace uses of with self"); - assert(From->getNumValues() == To->getNumValues() && + assert(From->getVTList().VTs == To->getVTList().VTs && + From->getNumValues() == To->getNumValues() && "Cannot use this version of ReplaceAllUsesWith!"); - if (From->getNumValues() == 1) // If possible, use the faster version. - return ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0), - UpdateListener); - + + // Handle the trivial case. + if (From == To) + return; + while (!From->use_empty()) { SDNode::use_iterator UI = From->use_begin(); - SDNode *U = UI->getUser(); + SDNode *U = *UI; // This node is about to morph, remove its old self from the CSE maps. RemoveNodeFromCSEMaps(U); @@ -3978,7 +4437,7 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To, I != E; ++I, ++operandNum) if (I->getVal() == From) { From->removeUser(operandNum, U); - I->getVal() = To; + I->getSDValue().setNode(To); To->addUser(operandNum, U); } @@ -4005,14 +4464,14 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To, /// This version can replace From with any result values. To must match the /// number and types of values returned by From. void SelectionDAG::ReplaceAllUsesWith(SDNode *From, - SDOperandPtr To, + const SDValue *To, DAGUpdateListener *UpdateListener) { if (From->getNumValues() == 1) // Handle the simple case efficiently. - return ReplaceAllUsesWith(SDOperand(From, 0), To[0], UpdateListener); + return ReplaceAllUsesWith(SDValue(From, 0), To[0], UpdateListener); while (!From->use_empty()) { SDNode::use_iterator UI = From->use_begin(); - SDNode *U = UI->getUser(); + SDNode *U = *UI; // This node is about to morph, remove its old self from the CSE maps. RemoveNodeFromCSEMaps(U); @@ -4020,11 +4479,11 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, for (SDNode::op_iterator I = U->op_begin(), E = U->op_end(); I != E; ++I, ++operandNum) if (I->getVal() == From) { - const SDOperand &ToOp = To[I->getSDOperand().ResNo]; + const SDValue &ToOp = To[I->getSDValue().getResNo()]; From->removeUser(operandNum, U); *I = ToOp; I->setUser(U); - ToOp.Val->addUser(operandNum, U); + ToOp.getNode()->addUser(operandNum, U); } // Now that we have modified U, add it back to the CSE maps. If it already @@ -4044,59 +4503,24 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, } } -namespace { - /// ChainedSetUpdaterListener - This class is a DAGUpdateListener that removes - /// any deleted nodes from the set passed into its constructor and recursively - /// notifies another update listener if specified. - class ChainedSetUpdaterListener : - public SelectionDAG::DAGUpdateListener { - SmallSetVector &Set; - SelectionDAG::DAGUpdateListener *Chain; - public: - ChainedSetUpdaterListener(SmallSetVector &set, - SelectionDAG::DAGUpdateListener *chain) - : Set(set), Chain(chain) {} - - virtual void NodeDeleted(SDNode *N, SDNode *E) { - Set.remove(N); - if (Chain) Chain->NodeDeleted(N, E); - } - virtual void NodeUpdated(SDNode *N) { - if (Chain) Chain->NodeUpdated(N); - } - }; -} - /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving -/// uses of other values produced by From.Val alone. The Deleted vector is +/// uses of other values produced by From.getVal() alone. The Deleted vector is /// handled the same way as for ReplaceAllUsesWith. -void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, +void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To, DAGUpdateListener *UpdateListener){ - assert(From != To && "Cannot replace a value with itself"); - + // Handle the really simple, really trivial case efficiently. + if (From == To) return; + // Handle the simple, trivial, case efficiently. - if (From.Val->getNumValues() == 1) { + if (From.getNode()->getNumValues() == 1) { ReplaceAllUsesWith(From, To, UpdateListener); return; } - if (From.use_empty()) return; - - // Get all of the users of From.Val. We want these in a nice, + // Get all of the users of From.getNode(). We want these in a nice, // deterministically ordered and uniqued set, so we use a SmallSetVector. - SmallSetVector Users; - for (SDNode::use_iterator UI = From.Val->use_begin(), - E = From.Val->use_end(); UI != E; ++UI) { - SDNode *User = UI->getUser(); - if (!Users.count(User)) - Users.insert(User); - } - - // When one of the recursive merges deletes nodes from the graph, we need to - // make sure that UpdateListener is notified *and* that the node is removed - // from Users if present. CSUL does this. - ChainedSetUpdaterListener CSUL(Users, UpdateListener); - + SmallSetVector Users(From.getNode()->use_begin(), From.getNode()->use_end()); + while (!Users.empty()) { // We know that this user uses some value of From. If it is the right // value, update it. @@ -4118,10 +4542,10 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, // Update all operands that match "From" in case there are multiple uses. for (; Op != E; ++Op) { if (*Op == From) { - From.Val->removeUser(Op-User->op_begin(), User); + From.getNode()->removeUser(Op-User->op_begin(), User); *Op = To; Op->setUser(User); - To.Val->addUser(Op-User->op_begin(), User); + To.getNode()->addUser(Op-User->op_begin(), User); } } @@ -4135,10 +4559,8 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, // If there was already an existing matching node, use ReplaceAllUsesWith // to replace the dead one with the existing one. This can cause - // recursive merging of other unrelated nodes down the line. The merging - // can cause deletion of nodes that used the old value. To handle this, we - // use CSUL to remove them from the Users set. - ReplaceAllUsesWith(User, Existing, &CSUL); + // recursive merging of other unrelated nodes down the line. + ReplaceAllUsesWith(User, Existing, UpdateListener); // User is now dead. Notify a listener if present. if (UpdateListener) UpdateListener->NodeDeleted(User, Existing); @@ -4146,56 +4568,143 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, } } -/// AssignNodeIds - Assign a unique node id for each node in the DAG based on -/// their allnodes order. It returns the maximum id. -unsigned SelectionDAG::AssignNodeIds() { - unsigned Id = 0; - for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I){ - SDNode *N = I; - N->setNodeId(Id++); +/// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving +/// uses of other values produced by From.getVal() alone. The same value may +/// appear in both the From and To list. The Deleted vector is +/// handled the same way as for ReplaceAllUsesWith. +void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From, + const SDValue *To, + unsigned Num, + DAGUpdateListener *UpdateListener){ + // Handle the simple, trivial case efficiently. + if (Num == 1) + return ReplaceAllUsesOfValueWith(*From, *To, UpdateListener); + + SmallVector, 16> Users; + for (unsigned i = 0; i != Num; ++i) + for (SDNode::use_iterator UI = From[i].getNode()->use_begin(), + E = From[i].getNode()->use_end(); UI != E; ++UI) + Users.push_back(std::make_pair(*UI, i)); + + while (!Users.empty()) { + // We know that this user uses some value of From. If it is the right + // value, update it. + SDNode *User = Users.back().first; + unsigned i = Users.back().second; + Users.pop_back(); + + // Scan for an operand that matches From. + SDNode::op_iterator Op = User->op_begin(), E = User->op_end(); + for (; Op != E; ++Op) + if (*Op == From[i]) break; + + // If there are no matches, the user must use some other result of From. + if (Op == E) continue; + + // Okay, we know this user needs to be updated. Remove its old self + // from the CSE maps. + RemoveNodeFromCSEMaps(User); + + // Update all operands that match "From" in case there are multiple uses. + for (; Op != E; ++Op) { + if (*Op == From[i]) { + From[i].getNode()->removeUser(Op-User->op_begin(), User); + *Op = To[i]; + Op->setUser(User); + To[i].getNode()->addUser(Op-User->op_begin(), User); + } + } + + // Now that we have modified User, add it back to the CSE maps. If it + // already exists there, recursively merge the results together. + SDNode *Existing = AddNonLeafNodeToCSEMaps(User); + if (!Existing) { + if (UpdateListener) UpdateListener->NodeUpdated(User); + continue; // Continue on to next user. + } + + // If there was already an existing matching node, use ReplaceAllUsesWith + // to replace the dead one with the existing one. This can cause + // recursive merging of other unrelated nodes down the line. + ReplaceAllUsesWith(User, Existing, UpdateListener); + + // User is now dead. Notify a listener if present. + if (UpdateListener) UpdateListener->NodeDeleted(User, Existing); + DeleteNodeNotInCSEMaps(User); } - return Id; } /// 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 InDegree(DAGSize); - std::vector Sources; - - // Use a two pass approach to avoid using a std::map which is slow. - unsigned Id = 0; - for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){ - SDNode *N = I; - N->setNodeId(Id++); - unsigned Degree = N->use_size(); - InDegree[N->getNodeId()] = Degree; - if (Degree == 0) - Sources.push_back(N); - } - - TopOrder.clear(); - while (!Sources.empty()) { - SDNode *N = Sources.back(); - Sources.pop_back(); - TopOrder.push_back(N); - for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { - SDNode *P = I->getVal(); - unsigned Degree = --InDegree[P->getNodeId()]; - if (Degree == 0) - Sources.push_back(P); +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); } } - // Second pass, assign the actual topological order as node ids. - Id = 0; - for (std::vector::iterator TI = TopOrder.begin(),TE = TopOrder.end(); - TI != TE; ++TI) - (*TI)->setNodeId(Id++); + // 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; + for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); + UI != UE; ++UI) { + SDNode *P = *UI; + unsigned Degree = P->getNodeId(); + --Degree; + 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; } @@ -4230,14 +4739,15 @@ void MemSDNode::ANCHOR() {} void LoadSDNode::ANCHOR() {} void StoreSDNode::ANCHOR() {} void AtomicSDNode::ANCHOR() {} +void MemIntrinsicSDNode::ANCHOR() {} +void CallSDNode::ANCHOR() {} HandleSDNode::~HandleSDNode() { - SDVTList VTs = { 0, 0 }; - MorphNodeTo(ISD::HANDLENODE, VTs, SDOperandPtr(), 0); // Drops operand uses. + 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 @@ -4248,48 +4758,63 @@ GlobalAddressSDNode::GlobalAddressSDNode(bool isTarget, const GlobalValue *GA, TheGlobal = const_cast(GA); } +MemSDNode::MemSDNode(unsigned Opc, SDVTList VTs, MVT memvt, + const Value *srcValue, int SVO, + unsigned alignment, bool vol) + : SDNode(Opc, VTs), MemoryVT(memvt), SrcValue(srcValue), SVOffset(SVO), + Flags(encodeMemSDNodeFlags(vol, alignment)) { + + assert(isPowerOf2_32(alignment) && "Alignment is not a power of 2!"); + assert(getAlignment() == alignment && "Alignment representation error!"); + 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 atomic. -MachineMemOperand AtomicSDNode::getMemOperand() const { - int Size = (getValueType(0).getSizeInBits() + 7) >> 3; - int Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOStore; +/// reference performed by this memory reference. +MachineMemOperand MemSDNode::getMemOperand() const { + int Flags; + if (isa(this)) + Flags = MachineMemOperand::MOLoad; + else if (isa(this)) + Flags = MachineMemOperand::MOStore; + 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; - // Check if the atomic references a frame index + // Check if the memory reference references a frame index const FrameIndexSDNode *FI = - dyn_cast(getBasePtr().Val); + dyn_cast(getBasePtr().getNode()); if (!getSrcValue() && FI) - return MachineMemOperand(PseudoSourceValue::getFixedStack(), Flags, - FI->getIndex(), Size, getAlignment()); + return MachineMemOperand(PseudoSourceValue::getFixedStack(FI->getIndex()), + Flags, 0, Size, getAlignment()); else return MachineMemOperand(getSrcValue(), Flags, getSrcValueOffset(), Size, getAlignment()); } -/// getMemOperand - Return a MachineMemOperand object describing the memory -/// reference performed by this load or store. -MachineMemOperand LSBaseSDNode::getMemOperand() const { - int Size = (getMemoryVT().getSizeInBits() + 7) >> 3; - int Flags = - getOpcode() == ISD::LOAD ? MachineMemOperand::MOLoad : - MachineMemOperand::MOStore; - if (isVolatile()) Flags |= MachineMemOperand::MOVolatile; - - // Check if the load references a frame index, and does not have - // an SV attached. - const FrameIndexSDNode *FI = - dyn_cast(getBasePtr().Val); - if (!getSrcValue() && FI) - return MachineMemOperand(PseudoSourceValue::getFixedStack(), Flags, - FI->getIndex(), Size, getAlignment()); - else - return MachineMemOperand(getSrcValue(), Flags, - getSrcValueOffset(), Size, getAlignment()); -} - /// Profile - Gather unique data for the node. /// -void SDNode::Profile(FoldingSetNodeID &ID) { +void SDNode::Profile(FoldingSetNodeID &ID) const { AddNodeIDNode(ID, this); } @@ -4312,18 +4837,9 @@ const MVT *SDNode::getValueTypeList(MVT VT) { bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const { assert(Value < getNumValues() && "Bad value!"); - // If there is only one value, this is easy. - if (getNumValues() == 1) - return use_size() == NUses; - if (use_size() < NUses) return false; - - SDOperand TheValue(const_cast(this), Value); - - SmallPtrSet UsersHandled; - // TODO: Only iterate over uses of a given value of the node for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) { - if (*UI == TheValue) { + if (UI.getUse().getSDValue().getResNo() == Value) { if (NUses == 0) return false; --NUses; @@ -4340,32 +4856,20 @@ bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const { bool SDNode::hasAnyUseOfValue(unsigned Value) const { assert(Value < getNumValues() && "Bad value!"); - if (use_empty()) return false; - - SDOperand TheValue(const_cast(this), Value); - - SmallPtrSet UsersHandled; - - for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) { - SDNode *User = UI->getUser(); - if (User->getNumOperands() == 1 || - UsersHandled.insert(User)) // First time we've seen this? - for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) - if (User->getOperand(i) == TheValue) { - return true; - } - } + for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) + if (UI.getUse().getSDValue().getResNo() == Value) + return true; return false; } -/// isOnlyUseOf - Return true if this node is the only use of N. +/// isOnlyUserOf - Return true if this node is the only use of N. /// -bool SDNode::isOnlyUseOf(SDNode *N) const { +bool SDNode::isOnlyUserOf(SDNode *N) const { bool Seen = false; for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) { - SDNode *User = I->getUser(); + SDNode *User = *I; if (User == this) Seen = true; else @@ -4377,7 +4881,7 @@ bool SDNode::isOnlyUseOf(SDNode *N) const { /// isOperand - Return true if this node is an operand of N. /// -bool SDOperand::isOperandOf(SDNode *N) const { +bool SDValue::isOperandOf(SDNode *N) const { for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) if (*this == N->getOperand(i)) return true; @@ -4396,7 +4900,7 @@ bool SDNode::isOperandOf(SDNode *N) const { /// side-effecting instructions. In practice, this looks through token /// factors and non-volatile loads. In order to remain efficient, this only /// looks a couple of nodes in, it does not do an exhaustive search. -bool SDOperand::reachesChainWithoutSideEffects(SDOperand Dest, +bool SDValue::reachesChainWithoutSideEffects(SDValue Dest, unsigned Depth) const { if (*this == Dest) return true; @@ -4428,7 +4932,7 @@ static void findPredecessor(SDNode *N, const SDNode *P, bool &found, return; for (unsigned i = 0, e = N->getNumOperands(); !found && i != e; ++i) { - SDNode *Op = N->getOperand(i).Val; + SDNode *Op = N->getOperand(i).getNode(); if (Op == P) { found = true; return; @@ -4450,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 { @@ -4458,35 +4962,75 @@ std::string SDNode::getOperationName(const SelectionDAG *G) const { default: if (getOpcode() < ISD::BUILTIN_OP_END) return "<>"; - else { - if (G) { + if (isMachineOpcode()) { + if (G) if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo()) - if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes()) - return TII->get(getOpcode()-ISD::BUILTIN_OP_END).getName(); - - TargetLowering &TLI = G->getTargetLoweringInfo(); - const char *Name = - TLI.getTargetNodeName(getOpcode()); - if (Name) return Name; - } - + if (getMachineOpcode() < TII->getNumOpcodes()) + return TII->get(getMachineOpcode()).getName(); + return "<>"; + } + if (G) { + TargetLowering &TLI = G->getTargetLoweringInfo(); + const char *Name = TLI.getTargetNodeName(getOpcode()); + if (Name) return Name; return "<>"; } + return "<>"; +#ifndef NDEBUG + case ISD::DELETED_NODE: + return "<>"; +#endif case ISD::PREFETCH: return "Prefetch"; case ISD::MEMBARRIER: return "MemBarrier"; - case ISD::ATOMIC_CMP_SWAP: return "AtomicCmpSwap"; - case ISD::ATOMIC_LOAD_ADD: return "AtomicLoadAdd"; - case ISD::ATOMIC_LOAD_SUB: return "AtomicLoadSub"; - case ISD::ATOMIC_LOAD_AND: return "AtomicLoadAnd"; - case ISD::ATOMIC_LOAD_OR: return "AtomicLoadOr"; - case ISD::ATOMIC_LOAD_XOR: return "AtomicLoadXor"; - case ISD::ATOMIC_LOAD_NAND: return "AtomicLoadNand"; - case ISD::ATOMIC_LOAD_MIN: return "AtomicLoadMin"; - case ISD::ATOMIC_LOAD_MAX: return "AtomicLoadMax"; - case ISD::ATOMIC_LOAD_UMIN: return "AtomicLoadUMin"; - case ISD::ATOMIC_LOAD_UMAX: return "AtomicLoadUMax"; - case ISD::ATOMIC_SWAP: return "AtomicSWAP"; + case ISD::ATOMIC_CMP_SWAP_8: return "AtomicCmpSwap8"; + case ISD::ATOMIC_SWAP_8: return "AtomicSwap8"; + case ISD::ATOMIC_LOAD_ADD_8: return "AtomicLoadAdd8"; + case ISD::ATOMIC_LOAD_SUB_8: return "AtomicLoadSub8"; + case ISD::ATOMIC_LOAD_AND_8: return "AtomicLoadAnd8"; + case ISD::ATOMIC_LOAD_OR_8: return "AtomicLoadOr8"; + case ISD::ATOMIC_LOAD_XOR_8: return "AtomicLoadXor8"; + case ISD::ATOMIC_LOAD_NAND_8: return "AtomicLoadNand8"; + case ISD::ATOMIC_LOAD_MIN_8: return "AtomicLoadMin8"; + case ISD::ATOMIC_LOAD_MAX_8: return "AtomicLoadMax8"; + case ISD::ATOMIC_LOAD_UMIN_8: return "AtomicLoadUMin8"; + case ISD::ATOMIC_LOAD_UMAX_8: return "AtomicLoadUMax8"; + case ISD::ATOMIC_CMP_SWAP_16: return "AtomicCmpSwap16"; + case ISD::ATOMIC_SWAP_16: return "AtomicSwap16"; + case ISD::ATOMIC_LOAD_ADD_16: return "AtomicLoadAdd16"; + case ISD::ATOMIC_LOAD_SUB_16: return "AtomicLoadSub16"; + case ISD::ATOMIC_LOAD_AND_16: return "AtomicLoadAnd16"; + case ISD::ATOMIC_LOAD_OR_16: return "AtomicLoadOr16"; + case ISD::ATOMIC_LOAD_XOR_16: return "AtomicLoadXor16"; + case ISD::ATOMIC_LOAD_NAND_16: return "AtomicLoadNand16"; + case ISD::ATOMIC_LOAD_MIN_16: return "AtomicLoadMin16"; + case ISD::ATOMIC_LOAD_MAX_16: return "AtomicLoadMax16"; + case ISD::ATOMIC_LOAD_UMIN_16: return "AtomicLoadUMin16"; + case ISD::ATOMIC_LOAD_UMAX_16: return "AtomicLoadUMax16"; + case ISD::ATOMIC_CMP_SWAP_32: return "AtomicCmpSwap32"; + case ISD::ATOMIC_SWAP_32: return "AtomicSwap32"; + case ISD::ATOMIC_LOAD_ADD_32: return "AtomicLoadAdd32"; + case ISD::ATOMIC_LOAD_SUB_32: return "AtomicLoadSub32"; + case ISD::ATOMIC_LOAD_AND_32: return "AtomicLoadAnd32"; + case ISD::ATOMIC_LOAD_OR_32: return "AtomicLoadOr32"; + case ISD::ATOMIC_LOAD_XOR_32: return "AtomicLoadXor32"; + case ISD::ATOMIC_LOAD_NAND_32: return "AtomicLoadNand32"; + case ISD::ATOMIC_LOAD_MIN_32: return "AtomicLoadMin32"; + case ISD::ATOMIC_LOAD_MAX_32: return "AtomicLoadMax32"; + case ISD::ATOMIC_LOAD_UMIN_32: return "AtomicLoadUMin32"; + case ISD::ATOMIC_LOAD_UMAX_32: return "AtomicLoadUMax32"; + case ISD::ATOMIC_CMP_SWAP_64: return "AtomicCmpSwap64"; + case ISD::ATOMIC_SWAP_64: return "AtomicSwap64"; + case ISD::ATOMIC_LOAD_ADD_64: return "AtomicLoadAdd64"; + case ISD::ATOMIC_LOAD_SUB_64: return "AtomicLoadSub64"; + case ISD::ATOMIC_LOAD_AND_64: return "AtomicLoadAnd64"; + case ISD::ATOMIC_LOAD_OR_64: return "AtomicLoadOr64"; + case ISD::ATOMIC_LOAD_XOR_64: return "AtomicLoadXor64"; + case ISD::ATOMIC_LOAD_NAND_64: return "AtomicLoadNand64"; + case ISD::ATOMIC_LOAD_MIN_64: return "AtomicLoadMin64"; + case ISD::ATOMIC_LOAD_MAX_64: return "AtomicLoadMax64"; + case ISD::ATOMIC_LOAD_UMIN_64: return "AtomicLoadUMin64"; + case ISD::ATOMIC_LOAD_UMAX_64: return "AtomicLoadUMax64"; case ISD::PCMARKER: return "PCMarker"; case ISD::READCYCLECOUNTER: return "ReadCycleCounter"; case ISD::SRCVALUE: return "SrcValue"; @@ -4517,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); } @@ -4556,6 +5100,11 @@ std::string SDNode::getOperationName(const SelectionDAG *G) const { case ISD::FCOS: return "fcos"; case ISD::FPOWI: return "fpowi"; case ISD::FPOW: return "fpow"; + case ISD::FTRUNC: return "ftrunc"; + case ISD::FFLOOR: return "ffloor"; + case ISD::FCEIL: return "fceil"; + case ISD::FRINT: return "frint"; + case ISD::FNEARBYINT: return "fnearbyint"; // Binary operators case ISD::ADD: return "add"; @@ -4570,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"; @@ -4733,178 +5282,177 @@ std::string ISD::ArgFlagsTy::getArgFlagsString() { void SDNode::dump() const { dump(0); } void SDNode::dump(const SelectionDAG *G) const { - cerr << (void*)this << ": "; + print(errs(), G); + errs().flush(); +} + +void SDNode::print(raw_ostream &OS, const SelectionDAG *G) const { + OS << (void*)this << ": "; for (unsigned i = 0, e = getNumValues(); i != e; ++i) { - if (i) cerr << ","; + if (i) OS << ","; if (getValueType(i) == MVT::Other) - cerr << "ch"; + OS << "ch"; else - cerr << getValueType(i).getMVTString(); + OS << getValueType(i).getMVTString(); } - cerr << " = " << getOperationName(G); + OS << " = " << getOperationName(G); - cerr << " "; + OS << " "; for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { - if (i) cerr << ", "; - cerr << (void*)getOperand(i).Val; - if (unsigned RN = getOperand(i).ResNo) - cerr << ":" << RN; + if (i) OS << ", "; + OS << (void*)getOperand(i).getNode(); + if (unsigned RN = getOperand(i).getResNo()) + OS << ":" << RN; } if (!isTargetOpcode() && getOpcode() == ISD::VECTOR_SHUFFLE) { - SDNode *Mask = getOperand(2).Val; - cerr << "<"; + SDNode *Mask = getOperand(2).getNode(); + OS << "<"; for (unsigned i = 0, e = Mask->getNumOperands(); i != e; ++i) { - if (i) cerr << ","; + if (i) OS << ","; if (Mask->getOperand(i).getOpcode() == ISD::UNDEF) - cerr << "u"; + OS << "u"; else - cerr << cast(Mask->getOperand(i))->getValue(); + OS << cast(Mask->getOperand(i))->getZExtValue(); } - cerr << ">"; + OS << ">"; } if (const ConstantSDNode *CSDN = dyn_cast(this)) { - cerr << "<" << CSDN->getValue() << ">"; + OS << '<' << CSDN->getAPIntValue() << '>'; } else if (const ConstantFPSDNode *CSDN = dyn_cast(this)) { if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEsingle) - cerr << "<" << CSDN->getValueAPF().convertToFloat() << ">"; + OS << '<' << CSDN->getValueAPF().convertToFloat() << '>'; else if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEdouble) - cerr << "<" << CSDN->getValueAPF().convertToDouble() << ">"; + OS << '<' << CSDN->getValueAPF().convertToDouble() << '>'; else { - cerr << "getValueAPF().convertToAPInt().dump(); - cerr << ")>"; + OS << "getValueAPF().bitcastToAPInt().dump(); + OS << ")>"; } } else if (const GlobalAddressSDNode *GADN = dyn_cast(this)) { - int offset = GADN->getOffset(); - cerr << "<"; - WriteAsOperand(*cerr.stream(), GADN->getGlobal()) << ">"; + int64_t offset = GADN->getOffset(); + OS << '<'; + WriteAsOperand(OS, GADN->getGlobal()); + OS << '>'; if (offset > 0) - cerr << " + " << offset; + OS << " + " << offset; else - cerr << " " << offset; + OS << " " << offset; } else if (const FrameIndexSDNode *FIDN = dyn_cast(this)) { - cerr << "<" << FIDN->getIndex() << ">"; + OS << "<" << FIDN->getIndex() << ">"; } else if (const JumpTableSDNode *JTDN = dyn_cast(this)) { - cerr << "<" << JTDN->getIndex() << ">"; + OS << "<" << JTDN->getIndex() << ">"; } else if (const ConstantPoolSDNode *CP = dyn_cast(this)){ int offset = CP->getOffset(); if (CP->isMachineConstantPoolEntry()) - cerr << "<" << *CP->getMachineCPVal() << ">"; + OS << "<" << *CP->getMachineCPVal() << ">"; else - cerr << "<" << *CP->getConstVal() << ">"; + OS << "<" << *CP->getConstVal() << ">"; if (offset > 0) - cerr << " + " << offset; + OS << " + " << offset; else - cerr << " " << offset; + OS << " " << offset; } else if (const BasicBlockSDNode *BBDN = dyn_cast(this)) { - cerr << "<"; + OS << "<"; const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock(); if (LBB) - cerr << LBB->getName() << " "; - cerr << (const void*)BBDN->getBasicBlock() << ">"; + OS << LBB->getName() << " "; + OS << (const void*)BBDN->getBasicBlock() << ">"; } else if (const RegisterSDNode *R = dyn_cast(this)) { if (G && R->getReg() && TargetRegisterInfo::isPhysicalRegister(R->getReg())) { - cerr << " " << G->getTarget().getRegisterInfo()->getName(R->getReg()); + OS << " " << G->getTarget().getRegisterInfo()->getName(R->getReg()); } else { - cerr << " #" << R->getReg(); + OS << " #" << R->getReg(); } } else if (const ExternalSymbolSDNode *ES = dyn_cast(this)) { - cerr << "'" << ES->getSymbol() << "'"; + OS << "'" << ES->getSymbol() << "'"; } else if (const SrcValueSDNode *M = dyn_cast(this)) { if (M->getValue()) - cerr << "<" << M->getValue() << ">"; + OS << "<" << M->getValue() << ">"; else - cerr << ""; + OS << ""; } else if (const MemOperandSDNode *M = dyn_cast(this)) { if (M->MO.getValue()) - cerr << "<" << M->MO.getValue() << ":" << M->MO.getOffset() << ">"; + OS << "<" << M->MO.getValue() << ":" << M->MO.getOffset() << ">"; else - cerr << "MO.getOffset() << ">"; + OS << "MO.getOffset() << ">"; } else if (const ARG_FLAGSSDNode *N = dyn_cast(this)) { - cerr << N->getArgFlags().getArgFlagsString(); + OS << N->getArgFlags().getArgFlagsString(); } else if (const VTSDNode *N = dyn_cast(this)) { - cerr << ":" << N->getVT().getMVTString(); + OS << ":" << N->getVT().getMVTString(); } else if (const LoadSDNode *LD = dyn_cast(this)) { const Value *SrcValue = LD->getSrcValue(); int SrcOffset = LD->getSrcValueOffset(); - cerr << " <"; + OS << " <"; if (SrcValue) - cerr << SrcValue; + OS << SrcValue; else - cerr << "null"; - cerr << ":" << SrcOffset << ">"; + OS << "null"; + OS << ":" << SrcOffset << ">"; bool doExt = true; switch (LD->getExtensionType()) { default: doExt = false; break; - case ISD::EXTLOAD: - cerr << " getMemoryVT().getMVTString() << ">"; + OS << LD->getMemoryVT().getMVTString() << ">"; const char *AM = getIndexedModeName(LD->getAddressingMode()); if (*AM) - cerr << " " << AM; + OS << " " << AM; if (LD->isVolatile()) - cerr << " "; - cerr << " alignment=" << LD->getAlignment(); + OS << " "; + OS << " alignment=" << LD->getAlignment(); } else if (const StoreSDNode *ST = dyn_cast(this)) { const Value *SrcValue = ST->getSrcValue(); int SrcOffset = ST->getSrcValueOffset(); - cerr << " <"; + OS << " <"; if (SrcValue) - cerr << SrcValue; + OS << SrcValue; else - cerr << "null"; - cerr << ":" << SrcOffset << ">"; + OS << "null"; + OS << ":" << SrcOffset << ">"; if (ST->isTruncatingStore()) - cerr << " getMemoryVT().getMVTString() << ">"; + OS << " getMemoryVT().getMVTString() << ">"; const char *AM = getIndexedModeName(ST->getAddressingMode()); if (*AM) - cerr << " " << AM; + OS << " " << AM; if (ST->isVolatile()) - cerr << " "; - cerr << " alignment=" << ST->getAlignment(); + OS << " "; + OS << " alignment=" << ST->getAlignment(); } else if (const AtomicSDNode* AT = dyn_cast(this)) { const Value *SrcValue = AT->getSrcValue(); int SrcOffset = AT->getSrcValueOffset(); - cerr << " <"; + OS << " <"; if (SrcValue) - cerr << SrcValue; + OS << SrcValue; else - cerr << "null"; - cerr << ":" << SrcOffset << ">"; + OS << "null"; + OS << ":" << SrcOffset << ">"; if (AT->isVolatile()) - cerr << " "; - cerr << " alignment=" << AT->getAlignment(); + OS << " "; + OS << " alignment=" << AT->getAlignment(); } } static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) { for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) - if (N->getOperand(i).Val->hasOneUse()) - DumpNodes(N->getOperand(i).Val, indent+2, G); + if (N->getOperand(i).getNode()->hasOneUse()) + DumpNodes(N->getOperand(i).getNode(), indent+2, G); else cerr << "\n" << std::string(indent+2, ' ') - << (void*)N->getOperand(i).Val << ": "; + << (void*)N->getOperand(i).getNode() << ": "; cerr << "\n" << std::string(indent, ' '); @@ -4913,19 +5461,15 @@ static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) { void SelectionDAG::dump() const { cerr << "SelectionDAG has " << AllNodes.size() << " nodes:"; - std::vector Nodes; - for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end(); - I != E; ++I) - Nodes.push_back(I); - std::sort(Nodes.begin(), Nodes.end()); - - for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { - if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val) - DumpNodes(Nodes[i], 2, this); + for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end(); + I != E; ++I) { + const SDNode *N = I; + if (!N->hasOneUse() && N != getRoot().getNode()) + DumpNodes(N, 2, this); } - if (getRoot().Val) DumpNodes(getRoot().Val, 2, this); + if (getRoot().getNode()) DumpNodes(getRoot().getNode(), 2, this); cerr << "\n\n"; }