X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FSelectionDAG.cpp;h=5f92df3f2d54d59baf6b64ab073292a035290961;hb=d97321ceb313f06fd9a824cf26b9dc5b80b3eb9d;hp=9389ca32bf996a91c12a323a83572be3dab5e11a;hpb=97d23335ad9a3a1e5b78b9feea49c57252ab53e9;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp index 9389ca32bf9..5f92df3f2d5 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -17,41 +17,25 @@ #include "llvm/Intrinsics.h" #include "llvm/Assembly/Writer.h" #include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineConstantPool.h" #include "llvm/Support/MathExtras.h" #include "llvm/Target/MRegisterInfo.h" #include "llvm/Target/TargetLowering.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringExtras.h" -#include #include -#include #include +#include using namespace llvm; -static bool isCommutativeBinOp(unsigned Opcode) { - switch (Opcode) { - case ISD::ADD: - case ISD::MUL: - case ISD::MULHU: - case ISD::MULHS: - case ISD::FADD: - case ISD::FMUL: - case ISD::AND: - case ISD::OR: - case ISD::XOR: return true; - default: return false; // FIXME: Need commutative info for user ops! - } -} - -// isInvertibleForFree - Return true if there is no cost to emitting the logical -// inverse of this node. -static bool isInvertibleForFree(SDOperand N) { - if (isa(N.Val)) return true; - if (N.Val->getOpcode() == ISD::SETCC && N.Val->hasOneUse()) - return true; - return false; +/// makeVTList - Return an instance of the SDVTList struct initialized with the +/// specified members. +static SDVTList makeVTList(const MVT::ValueType *VTs, unsigned NumVTs) { + SDVTList Res = {VTs, NumVTs}; + return Res; } //===----------------------------------------------------------------------===// @@ -73,6 +57,10 @@ bool ConstantFPSDNode::isExactlyValue(double V) const { /// isBuildVectorAllOnes - Return true if the specified node is a /// BUILD_VECTOR where all of the elements are ~0 or undef. bool ISD::isBuildVectorAllOnes(const SDNode *N) { + // Look through a bit convert. + if (N->getOpcode() == ISD::BIT_CONVERT) + N = N->getOperand(0).Val; + if (N->getOpcode() != ISD::BUILD_VECTOR) return false; unsigned i = 0, e = N->getNumOperands(); @@ -117,6 +105,10 @@ bool ISD::isBuildVectorAllOnes(const SDNode *N) { /// isBuildVectorAllZeros - Return true if the specified node is a /// BUILD_VECTOR where all of the elements are 0 or undef. bool ISD::isBuildVectorAllZeros(const SDNode *N) { + // Look through a bit convert. + if (N->getOpcode() == ISD::BIT_CONVERT) + N = N->getOperand(0).Val; + if (N->getOpcode() != ISD::BUILD_VECTOR) return false; unsigned i = 0, e = N->getNumOperands(); @@ -209,7 +201,12 @@ ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2, // If the N and U bits get set then the resultant comparison DOES suddenly // care about orderedness, and is true when ordered. if (Op > ISD::SETTRUE2) - Op &= ~16; // Clear the N bit. + Op &= ~16; // Clear the U bit if the N bit is set. + + // Canonicalize illegal integer setcc's. + if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT + Op = ISD::SETNE; + return ISD::CondCode(Op); } @@ -224,79 +221,275 @@ ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2, return ISD::SETCC_INVALID; // Combine all of the condition bits. - return ISD::CondCode(Op1 & Op2); + ISD::CondCode Result = ISD::CondCode(Op1 & Op2); + + // Canonicalize illegal integer setcc's. + if (isInteger) { + switch (Result) { + default: break; + case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT + case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE + case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE + case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE + } + } + + return Result; } const TargetMachine &SelectionDAG::getTarget() const { return TLI.getTargetMachine(); } +//===----------------------------------------------------------------------===// +// SDNode Profile Support +//===----------------------------------------------------------------------===// + +/// AddNodeIDOpcode - Add the node opcode to the NodeID data. +/// +static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) { + ID.AddInteger(OpC); +} + +/// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them +/// solely with their pointer. +void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) { + ID.AddPointer(VTList.VTs); +} + +/// AddNodeIDOperand - Add an operands data to the NodeID data. +/// +static void AddNodeIDOperand(FoldingSetNodeID &ID, SDOperand Op) { + ID.AddPointer(Op.Val); + ID.AddInteger(Op.ResNo); +} + +/// AddNodeIDOperands - Various routines for adding operands to the NodeID data. +/// +static void AddNodeIDOperands(FoldingSetNodeID &ID) { +} +static void AddNodeIDOperands(FoldingSetNodeID &ID, SDOperand Op) { + AddNodeIDOperand(ID, Op); +} +static void AddNodeIDOperands(FoldingSetNodeID &ID, + SDOperand Op1, SDOperand Op2) { + AddNodeIDOperand(ID, Op1); + AddNodeIDOperand(ID, Op2); +} +static void AddNodeIDOperands(FoldingSetNodeID &ID, + SDOperand Op1, SDOperand Op2, SDOperand Op3) { + AddNodeIDOperand(ID, Op1); + AddNodeIDOperand(ID, Op2); + AddNodeIDOperand(ID, Op3); +} +static void AddNodeIDOperands(FoldingSetNodeID &ID, + const SDOperand *Ops, unsigned NumOps) { + for (; NumOps; --NumOps, ++Ops) + AddNodeIDOperand(ID, *Ops); +} + +/// AddNodeIDOperands - Various routines for adding node info to the NodeID +/// data. +static void AddNodeIDNode(FoldingSetNodeID &ID, + unsigned short OpC, SDVTList VTList) { + AddNodeIDOpcode(ID, OpC); + AddNodeIDValueTypes(ID, VTList); + AddNodeIDOperands(ID); +} +static void AddNodeIDNode(FoldingSetNodeID &ID, + unsigned short OpC, SDVTList VTList, + SDOperand Op) { + AddNodeIDOpcode(ID, OpC); + AddNodeIDValueTypes(ID, VTList); + AddNodeIDOperands(ID, Op); +} +static void AddNodeIDNode(FoldingSetNodeID &ID, + unsigned short OpC, SDVTList VTList, + SDOperand Op1, SDOperand Op2) { + AddNodeIDOpcode(ID, OpC); + AddNodeIDValueTypes(ID, VTList); + AddNodeIDOperands(ID, Op1, Op2); +} +static void AddNodeIDNode(FoldingSetNodeID &ID, + unsigned short OpC, SDVTList VTList, + SDOperand Op1, SDOperand Op2, SDOperand Op3) { + AddNodeIDOpcode(ID, OpC); + AddNodeIDValueTypes(ID, VTList); + AddNodeIDOperands(ID, Op1, Op2, Op3); +} +static void AddNodeIDNode(FoldingSetNodeID &ID, + unsigned short OpC, SDVTList VTList, + const SDOperand *OpList, unsigned N) { + AddNodeIDOpcode(ID, OpC); + AddNodeIDValueTypes(ID, VTList); + AddNodeIDOperands(ID, OpList, N); +} + +/// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID +/// data. +static void AddNodeIDNode(FoldingSetNodeID &ID, SDNode *N) { + AddNodeIDOpcode(ID, N->getOpcode()); + // Add the return value info. + AddNodeIDValueTypes(ID, N->getVTList()); + // Add the operand info. + AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands()); + + // Handle SDNode leafs with special info. + if (N->getNumOperands() == 0) { + switch (N->getOpcode()) { + default: break; // Normal nodes don't need extra info. + case ISD::TargetConstant: + case ISD::Constant: + ID.AddInteger(cast(N)->getValue()); + break; + case ISD::TargetConstantFP: + case ISD::ConstantFP: + ID.AddDouble(cast(N)->getValue()); + break; + case ISD::TargetGlobalAddress: + case ISD::GlobalAddress: { + GlobalAddressSDNode *GA = cast(N); + ID.AddPointer(GA->getGlobal()); + ID.AddInteger(GA->getOffset()); + break; + } + case ISD::BasicBlock: + ID.AddPointer(cast(N)->getBasicBlock()); + break; + case ISD::Register: + ID.AddInteger(cast(N)->getReg()); + break; + case ISD::SRCVALUE: { + SrcValueSDNode *SV = cast(N); + ID.AddPointer(SV->getValue()); + ID.AddInteger(SV->getOffset()); + break; + } + case ISD::FrameIndex: + case ISD::TargetFrameIndex: + ID.AddInteger(cast(N)->getIndex()); + break; + case ISD::JumpTable: + case ISD::TargetJumpTable: + ID.AddInteger(cast(N)->getIndex()); + break; + case ISD::ConstantPool: + case ISD::TargetConstantPool: { + ConstantPoolSDNode *CP = cast(N); + ID.AddInteger(CP->getAlignment()); + ID.AddInteger(CP->getOffset()); + if (CP->isMachineConstantPoolEntry()) + CP->getMachineCPVal()->AddSelectionDAGCSEId(ID); + else + ID.AddPointer(CP->getConstVal()); + break; + } + case ISD::LOAD: { + LoadSDNode *LD = cast(N); + ID.AddInteger(LD->getAddressingMode()); + ID.AddInteger(LD->getExtensionType()); + ID.AddInteger(LD->getLoadedVT()); + ID.AddPointer(LD->getSrcValue()); + ID.AddInteger(LD->getSrcValueOffset()); + ID.AddInteger(LD->getAlignment()); + ID.AddInteger(LD->isVolatile()); + break; + } + case ISD::STORE: { + StoreSDNode *ST = cast(N); + ID.AddInteger(ST->getAddressingMode()); + ID.AddInteger(ST->isTruncatingStore()); + ID.AddInteger(ST->getStoredVT()); + ID.AddPointer(ST->getSrcValue()); + ID.AddInteger(ST->getSrcValueOffset()); + ID.AddInteger(ST->getAlignment()); + ID.AddInteger(ST->isVolatile()); + break; + } + } + } +} + //===----------------------------------------------------------------------===// // SelectionDAG Class //===----------------------------------------------------------------------===// /// RemoveDeadNodes - This method deletes all unreachable nodes in the -/// SelectionDAG, including nodes (like loads) that have uses of their token -/// chain but no other uses and no side effect. If a node is passed in as an -/// argument, it is used as the seed for node deletion. -void SelectionDAG::RemoveDeadNodes(SDNode *N) { +/// SelectionDAG. +void SelectionDAG::RemoveDeadNodes() { // Create a dummy node (which is not added to allnodes), that adds a reference // to the root node, preventing it from being deleted. HandleSDNode Dummy(getRoot()); - bool MadeChange = false; + SmallVector DeadNodes; - // If we have a hint to start from, use it. - if (N && N->use_empty()) { - DestroyDeadNode(N); - MadeChange = true; - } - + // Add all obviously-dead nodes to the DeadNodes worklist. for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I) - if (I->use_empty() && I->getOpcode() != 65535) { - // Node is dead, recursively delete newly dead uses. - DestroyDeadNode(I); - MadeChange = true; - } - - // Walk the nodes list, removing the nodes we've marked as dead. - if (MadeChange) { - for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ) { - SDNode *N = I++; - if (N->use_empty()) - AllNodes.erase(N); + 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->Val; + Operand->removeUser(N); + + // Now that we removed this operand, see if there are no uses of it left. + if (Operand->use_empty()) + DeadNodes.push_back(Operand); } + delete[] N->OperandList; + N->OperandList = 0; + N->NumOperands = 0; + + // Finally, remove N itself. + AllNodes.erase(N); } // If the root changed (e.g. it was a dead load, update the root). setRoot(Dummy.getValue()); } -/// DestroyDeadNode - We know that N is dead. Nuke it from the CSE maps for the -/// graph. If it is the last user of any of its operands, recursively process -/// them the same way. -/// -void SelectionDAG::DestroyDeadNode(SDNode *N) { - // Okay, we really are going to delete this node. First take this 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 *O = I->Val; - O->removeUser(N); +void SelectionDAG::RemoveDeadNode(SDNode *N, std::vector &Deleted) { + SmallVector DeadNodes; + DeadNodes.push_back(N); + + // Process the worklist, deleting the nodes and adding their uses to the + // worklist. + while (!DeadNodes.empty()) { + SDNode *N = DeadNodes.back(); + DeadNodes.pop_back(); - // Now that we removed this operand, see if there are no uses of it left. - if (O->use_empty()) - DestroyDeadNode(O); - } - delete[] N->OperandList; - N->OperandList = 0; - N->NumOperands = 0; + // Take the node out of the appropriate CSE map. + RemoveNodeFromCSEMaps(N); - // Mark the node as dead. - N->MorphNodeTo(65535); + // 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->Val; + Operand->removeUser(N); + + // Now that we removed this operand, see if there are no uses of it left. + if (Operand->use_empty()) + DeadNodes.push_back(Operand); + } + delete[] N->OperandList; + N->OperandList = 0; + N->NumOperands = 0; + + // Finally, remove N itself. + Deleted.push_back(N); + AllNodes.erase(N); + } } void SelectionDAG::DeleteNode(SDNode *N) { @@ -333,25 +526,6 @@ void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { bool Erased = false; switch (N->getOpcode()) { case ISD::HANDLENODE: return; // noop. - case ISD::Constant: - Erased = Constants.erase(std::make_pair(cast(N)->getValue(), - N->getValueType(0))); - break; - case ISD::TargetConstant: - Erased = TargetConstants.erase(std::make_pair( - cast(N)->getValue(), - N->getValueType(0))); - break; - case ISD::ConstantFP: { - uint64_t V = DoubleToBits(cast(N)->getValue()); - Erased = ConstantFPs.erase(std::make_pair(V, N->getValueType(0))); - break; - } - case ISD::TargetConstantFP: { - uint64_t V = DoubleToBits(cast(N)->getValue()); - Erased = TargetConstantFPs.erase(std::make_pair(V, N->getValueType(0))); - break; - } case ISD::STRING: Erased = StringNodes.erase(cast(N)->getValue()); break; @@ -361,39 +535,6 @@ void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { Erased = CondCodeNodes[cast(N)->get()] != 0; CondCodeNodes[cast(N)->get()] = 0; break; - case ISD::GlobalAddress: { - GlobalAddressSDNode *GN = cast(N); - Erased = GlobalValues.erase(std::make_pair(GN->getGlobal(), - GN->getOffset())); - break; - } - case ISD::TargetGlobalAddress: { - GlobalAddressSDNode *GN = cast(N); - Erased =TargetGlobalValues.erase(std::make_pair(GN->getGlobal(), - GN->getOffset())); - break; - } - case ISD::FrameIndex: - Erased = FrameIndices.erase(cast(N)->getIndex()); - break; - case ISD::TargetFrameIndex: - Erased = TargetFrameIndices.erase(cast(N)->getIndex()); - break; - case ISD::ConstantPool: - Erased = ConstantPoolIndices. - erase(std::make_pair(cast(N)->get(), - std::make_pair(cast(N)->getOffset(), - cast(N)->getAlignment()))); - break; - case ISD::TargetConstantPool: - Erased = TargetConstantPoolIndices. - erase(std::make_pair(cast(N)->get(), - std::make_pair(cast(N)->getOffset(), - cast(N)->getAlignment()))); - break; - case ISD::BasicBlock: - Erased = BBNodes.erase(cast(N)->getBasicBlock()); - break; case ISD::ExternalSymbol: Erased = ExternalSymbols.erase(cast(N)->getSymbol()); break; @@ -405,50 +546,9 @@ void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { Erased = ValueTypeNodes[cast(N)->getVT()] != 0; ValueTypeNodes[cast(N)->getVT()] = 0; break; - case ISD::Register: - Erased = RegNodes.erase(std::make_pair(cast(N)->getReg(), - N->getValueType(0))); - break; - case ISD::SRCVALUE: { - SrcValueSDNode *SVN = cast(N); - Erased =ValueNodes.erase(std::make_pair(SVN->getValue(), SVN->getOffset())); - break; - } - case ISD::LOAD: - Erased = Loads.erase(std::make_pair(N->getOperand(1), - std::make_pair(N->getOperand(0), - N->getValueType(0)))); - break; default: - if (N->getNumValues() == 1) { - if (N->getNumOperands() == 0) { - Erased = NullaryOps.erase(std::make_pair(N->getOpcode(), - N->getValueType(0))); - } else if (N->getNumOperands() == 1) { - Erased = - UnaryOps.erase(std::make_pair(N->getOpcode(), - std::make_pair(N->getOperand(0), - N->getValueType(0)))); - } else if (N->getNumOperands() == 2) { - Erased = - BinaryOps.erase(std::make_pair(N->getOpcode(), - std::make_pair(N->getOperand(0), - N->getOperand(1)))); - } else { - std::vector Ops(N->op_begin(), N->op_end()); - Erased = - OneResultNodes.erase(std::make_pair(N->getOpcode(), - std::make_pair(N->getValueType(0), - Ops))); - } - } else { - // Remove the node from the ArbitraryNodes map. - std::vector RV(N->value_begin(), N->value_end()); - std::vector Ops(N->op_begin(), N->op_end()); - Erased = - ArbitraryNodes.erase(std::make_pair(N->getOpcode(), - std::make_pair(RV, Ops))); - } + // Remove it from the CSE Map. + Erased = CSEMap.RemoveNode(N); break; } #ifndef NDEBUG @@ -458,6 +558,7 @@ void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag && !N->isTargetOpcode()) { N->dump(); + cerr << "\n"; assert(0 && "Node is not in map!"); } #endif @@ -478,43 +579,8 @@ SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) { if (N->getValueType(i) == MVT::Flag) return 0; // Never CSE anything that produces a flag. - if (N->getNumValues() == 1) { - if (N->getNumOperands() == 1) { - SDNode *&U = UnaryOps[std::make_pair(N->getOpcode(), - std::make_pair(N->getOperand(0), - N->getValueType(0)))]; - if (U) return U; - U = N; - } else if (N->getNumOperands() == 2) { - SDNode *&B = BinaryOps[std::make_pair(N->getOpcode(), - std::make_pair(N->getOperand(0), - N->getOperand(1)))]; - if (B) return B; - B = N; - } else { - std::vector Ops(N->op_begin(), N->op_end()); - SDNode *&ORN = OneResultNodes[std::make_pair(N->getOpcode(), - std::make_pair(N->getValueType(0), Ops))]; - if (ORN) return ORN; - ORN = N; - } - } else { - if (N->getOpcode() == ISD::LOAD) { - SDNode *&L = Loads[std::make_pair(N->getOperand(1), - std::make_pair(N->getOperand(0), - N->getValueType(0)))]; - if (L) return L; - L = N; - } else { - // Remove the node from the ArbitraryNodes map. - std::vector RV(N->value_begin(), N->value_end()); - std::vector Ops(N->op_begin(), N->op_end()); - SDNode *&AN = ArbitraryNodes[std::make_pair(N->getOpcode(), - std::make_pair(RV, Ops))]; - if (AN) return AN; - AN = N; - } - } + SDNode *New = CSEMap.GetOrInsertNode(N); + if (New != N) return New; // Node already existed. return 0; } @@ -522,7 +588,8 @@ 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, SDOperand Op, + void *&InsertPos) { if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) return 0; // Never add these nodes. @@ -531,26 +598,18 @@ SDNode **SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op) { if (N->getValueType(i) == MVT::Flag) return 0; // Never CSE anything that produces a flag. - if (N->getNumValues() == 1) { - return &UnaryOps[std::make_pair(N->getOpcode(), - std::make_pair(Op, N->getValueType(0)))]; - } else { - // Remove the node from the ArbitraryNodes map. - std::vector RV(N->value_begin(), N->value_end()); - std::vector Ops; - Ops.push_back(Op); - return &ArbitraryNodes[std::make_pair(N->getOpcode(), - std::make_pair(RV, Ops))]; - } - return 0; + FoldingSetNodeID ID; + AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Op); + return CSEMap.FindNodeOrInsertPos(ID, InsertPos); } /// FindModifiedNodeSlot - Find a slot for the specified node if its operands /// 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 Op1, SDOperand Op2) { +SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, + SDOperand Op1, SDOperand Op2, + void *&InsertPos) { if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) return 0; // Never add these nodes. @@ -558,19 +617,10 @@ SDNode **SelectionDAG::FindModifiedNodeSlot(SDNode *N, 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. - - if (N->getNumValues() == 1) { - return &BinaryOps[std::make_pair(N->getOpcode(), - std::make_pair(Op1, Op2))]; - } else { - std::vector RV(N->value_begin(), N->value_end()); - std::vector Ops; - Ops.push_back(Op1); - Ops.push_back(Op2); - return &ArbitraryNodes[std::make_pair(N->getOpcode(), - std::make_pair(RV, Ops))]; - } - return 0; + + FoldingSetNodeID ID; + AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Op1, Op2); + return CSEMap.FindNodeOrInsertPos(ID, InsertPos); } @@ -578,8 +628,9 @@ SDNode **SelectionDAG::FindModifiedNodeSlot(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, - const std::vector &Ops) { +SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, + const SDOperand *Ops,unsigned NumOps, + void *&InsertPos) { if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) return 0; // Never add these nodes. @@ -588,36 +639,36 @@ SDNode **SelectionDAG::FindModifiedNodeSlot(SDNode *N, if (N->getValueType(i) == MVT::Flag) return 0; // Never CSE anything that produces a flag. - if (N->getNumValues() == 1) { - if (N->getNumOperands() == 1) { - return &UnaryOps[std::make_pair(N->getOpcode(), - std::make_pair(Ops[0], - N->getValueType(0)))]; - } else if (N->getNumOperands() == 2) { - return &BinaryOps[std::make_pair(N->getOpcode(), - std::make_pair(Ops[0], Ops[1]))]; - } else { - return &OneResultNodes[std::make_pair(N->getOpcode(), - std::make_pair(N->getValueType(0), - Ops))]; - } - } else { - if (N->getOpcode() == ISD::LOAD) { - return &Loads[std::make_pair(Ops[1], - std::make_pair(Ops[0], N->getValueType(0)))]; - } else { - std::vector RV(N->value_begin(), N->value_end()); - return &ArbitraryNodes[std::make_pair(N->getOpcode(), - std::make_pair(RV, Ops))]; - } + FoldingSetNodeID ID; + AddNodeIDNode(ID, N->getOpcode(), N->getVTList()); + + if (const LoadSDNode *LD = dyn_cast(N)) { + ID.AddInteger(LD->getAddressingMode()); + ID.AddInteger(LD->getExtensionType()); + ID.AddInteger(LD->getLoadedVT()); + ID.AddPointer(LD->getSrcValue()); + ID.AddInteger(LD->getSrcValueOffset()); + ID.AddInteger(LD->getAlignment()); + ID.AddInteger(LD->isVolatile()); + } else if (const StoreSDNode *ST = dyn_cast(N)) { + ID.AddInteger(ST->getAddressingMode()); + ID.AddInteger(ST->isTruncatingStore()); + ID.AddInteger(ST->getStoredVT()); + ID.AddPointer(ST->getSrcValue()); + ID.AddInteger(ST->getSrcValueOffset()); + ID.AddInteger(ST->getAlignment()); + ID.AddInteger(ST->isVolatile()); } - return 0; + + AddNodeIDOperands(ID, Ops, NumOps); + return CSEMap.FindNodeOrInsertPos(ID, InsertPos); } SelectionDAG::~SelectionDAG() { while (!AllNodes.empty()) { SDNode *N = AllNodes.begin(); + N->SetNextInBucket(0); delete [] N->OperandList; N->OperandList = 0; N->NumOperands = 0; @@ -632,21 +683,6 @@ SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT::ValueType VT) { getConstant(Imm, Op.getValueType())); } -SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) { - assert(MVT::isInteger(VT) && "Cannot create FP integer constant!"); - assert(!MVT::isVector(VT) && "Cannot create Vector ConstantSDNodes!"); - - // Mask out any bits that are not valid for this constant. - if (VT != MVT::i64) - Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1; - - SDNode *&N = Constants[std::make_pair(Val, VT)]; - if (N) return SDOperand(N, 0); - N = new ConstantSDNode(false, Val, VT); - AllNodes.push_back(N); - return SDOperand(N, 0); -} - SDOperand SelectionDAG::getString(const std::string &Val) { StringSDNode *&N = StringNodes[Val]; if (!N) { @@ -656,107 +692,143 @@ SDOperand SelectionDAG::getString(const std::string &Val) { return SDOperand(N, 0); } -SDOperand SelectionDAG::getTargetConstant(uint64_t Val, MVT::ValueType VT) { +SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT, bool isT) { assert(MVT::isInteger(VT) && "Cannot create FP integer constant!"); - // Mask out any bits that are not valid for this constant. - if (VT != MVT::i64) - Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1; + assert(!MVT::isVector(VT) && "Cannot create Vector ConstantSDNodes!"); - SDNode *&N = TargetConstants[std::make_pair(Val, VT)]; - if (N) return SDOperand(N, 0); - N = new ConstantSDNode(true, Val, VT); + // Mask out any bits that are not valid for this constant. + Val &= MVT::getIntVTBitMask(VT); + + unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant; + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opc, getVTList(VT)); + ID.AddInteger(Val); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + SDNode *N = new ConstantSDNode(isT, Val, VT); + CSEMap.InsertNode(N, IP); AllNodes.push_back(N); return SDOperand(N, 0); } -SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) { - assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!"); - if (VT == MVT::f32) - Val = (float)Val; // Mask out extra precision. - // Do the map lookup using the actual bit pattern for the floating point - // value, so that we don't have problems with 0.0 comparing equal to -0.0, and - // we don't have issues with SNANs. - SDNode *&N = ConstantFPs[std::make_pair(DoubleToBits(Val), VT)]; - if (N) return SDOperand(N, 0); - N = new ConstantFPSDNode(false, Val, VT); - AllNodes.push_back(N); - return SDOperand(N, 0); -} - -SDOperand SelectionDAG::getTargetConstantFP(double Val, MVT::ValueType VT) { +SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT, + bool isTarget) { assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!"); if (VT == MVT::f32) Val = (float)Val; // Mask out extra precision. - + // Do the map lookup using the actual bit pattern for the floating point // value, so that we don't have problems with 0.0 comparing equal to -0.0, and // we don't have issues with SNANs. - SDNode *&N = TargetConstantFPs[std::make_pair(DoubleToBits(Val), VT)]; - if (N) return SDOperand(N, 0); - N = new ConstantFPSDNode(true, Val, VT); + unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP; + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opc, getVTList(VT)); + ID.AddDouble(Val); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + SDNode *N = new ConstantFPSDNode(isTarget, Val, VT); + CSEMap.InsertNode(N, IP); AllNodes.push_back(N); return SDOperand(N, 0); } SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV, - MVT::ValueType VT, int offset) { - SDNode *&N = GlobalValues[std::make_pair(GV, offset)]; - if (N) return SDOperand(N, 0); - N = new GlobalAddressSDNode(false, GV, VT, offset); + MVT::ValueType VT, int Offset, + bool isTargetGA) { + unsigned Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress; + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opc, getVTList(VT)); + 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); + CSEMap.InsertNode(N, IP); AllNodes.push_back(N); return SDOperand(N, 0); } -SDOperand SelectionDAG::getTargetGlobalAddress(const GlobalValue *GV, - MVT::ValueType VT, int offset) { - SDNode *&N = TargetGlobalValues[std::make_pair(GV, offset)]; - if (N) return SDOperand(N, 0); - N = new GlobalAddressSDNode(true, GV, VT, offset); +SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT, + bool isTarget) { + unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex; + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opc, getVTList(VT)); + ID.AddInteger(FI); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + SDNode *N = new FrameIndexSDNode(FI, VT, isTarget); + CSEMap.InsertNode(N, IP); AllNodes.push_back(N); return SDOperand(N, 0); } -SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) { - SDNode *&N = FrameIndices[FI]; - if (N) return SDOperand(N, 0); - N = new FrameIndexSDNode(FI, VT, false); - AllNodes.push_back(N); - return SDOperand(N, 0); -} - -SDOperand SelectionDAG::getTargetFrameIndex(int FI, MVT::ValueType VT) { - SDNode *&N = TargetFrameIndices[FI]; - if (N) return SDOperand(N, 0); - N = new FrameIndexSDNode(FI, VT, true); +SDOperand SelectionDAG::getJumpTable(int JTI, MVT::ValueType VT, bool isTarget){ + unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable; + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opc, getVTList(VT)); + ID.AddInteger(JTI); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + SDNode *N = new JumpTableSDNode(JTI, VT, isTarget); + CSEMap.InsertNode(N, IP); AllNodes.push_back(N); return SDOperand(N, 0); } SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT, - unsigned Alignment, int Offset) { - SDNode *&N = ConstantPoolIndices[std::make_pair(C, - std::make_pair(Offset, Alignment))]; - if (N) return SDOperand(N, 0); - N = new ConstantPoolSDNode(false, C, VT, Offset, Alignment); + unsigned Alignment, int Offset, + bool isTarget) { + unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opc, getVTList(VT)); + 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); + CSEMap.InsertNode(N, IP); AllNodes.push_back(N); return SDOperand(N, 0); } -SDOperand SelectionDAG::getTargetConstantPool(Constant *C, MVT::ValueType VT, - unsigned Alignment, int Offset) { - SDNode *&N = TargetConstantPoolIndices[std::make_pair(C, - std::make_pair(Offset, Alignment))]; - if (N) return SDOperand(N, 0); - N = new ConstantPoolSDNode(true, C, VT, Offset, Alignment); + +SDOperand SelectionDAG::getConstantPool(MachineConstantPoolValue *C, + MVT::ValueType VT, + unsigned Alignment, int Offset, + bool isTarget) { + unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opc, getVTList(VT)); + 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); + CSEMap.InsertNode(N, IP); AllNodes.push_back(N); return SDOperand(N, 0); } + SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { - SDNode *&N = BBNodes[MBB]; - if (N) return SDOperand(N, 0); - N = new BasicBlockSDNode(MBB); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other)); + ID.AddPointer(MBB); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + SDNode *N = new BasicBlockSDNode(MBB); + CSEMap.InsertNode(N, IP); AllNodes.push_back(N); return SDOperand(N, 0); } @@ -801,16 +873,37 @@ SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) { } SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) { - RegisterSDNode *&Reg = RegNodes[std::make_pair(RegNo, VT)]; - if (!Reg) { - Reg = new RegisterSDNode(RegNo, VT); - AllNodes.push_back(Reg); - } - return SDOperand(Reg, 0); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::Register, getVTList(VT)); + ID.AddInteger(RegNo); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + SDNode *N = new RegisterSDNode(RegNo, VT); + CSEMap.InsertNode(N, IP); + AllNodes.push_back(N); + return SDOperand(N, 0); +} + +SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) { + assert((!V || isa(V->getType())) && + "SrcValue is not a pointer?"); + + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other)); + ID.AddPointer(V); + ID.AddInteger(Offset); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + SDNode *N = new SrcValueSDNode(V, Offset); + CSEMap.InsertNode(N, IP); + AllNodes.push_back(N); + return SDOperand(N, 0); } -SDOperand SelectionDAG::SimplifySetCC(MVT::ValueType VT, SDOperand N1, - SDOperand N2, ISD::CondCode Cond) { +SDOperand SelectionDAG::FoldSetCC(MVT::ValueType VT, SDOperand N1, + SDOperand N2, ISD::CondCode Cond) { // These setcc operations always fold. switch (Cond) { default: break; @@ -818,19 +911,32 @@ SDOperand SelectionDAG::SimplifySetCC(MVT::ValueType VT, SDOperand N1, case ISD::SETFALSE2: return getConstant(0, VT); case ISD::SETTRUE: case ISD::SETTRUE2: return getConstant(1, VT); + + case ISD::SETOEQ: + case ISD::SETOGT: + case ISD::SETOGE: + case ISD::SETOLT: + case ISD::SETOLE: + case ISD::SETONE: + case ISD::SETO: + case ISD::SETUO: + case ISD::SETUEQ: + case ISD::SETUNE: + assert(!MVT::isInteger(N1.getValueType()) && "Illegal setcc for integer!"); + break; } - + if (ConstantSDNode *N2C = dyn_cast(N2.Val)) { uint64_t C2 = N2C->getValue(); if (ConstantSDNode *N1C = dyn_cast(N1.Val)) { uint64_t C1 = N1C->getValue(); - + // Sign extend the operands if required if (ISD::isSignedIntSetCC(Cond)) { C1 = N1C->getSignExtended(); C2 = N2C->getSignExtended(); } - + switch (Cond) { default: assert(0 && "Unknown integer setcc!"); case ISD::SETEQ: return getConstant(C1 == C2, VT); @@ -844,156 +950,12 @@ SDOperand SelectionDAG::SimplifySetCC(MVT::ValueType VT, SDOperand N1, case ISD::SETLE: return getConstant((int64_t)C1 <= (int64_t)C2, VT); case ISD::SETGE: return getConstant((int64_t)C1 >= (int64_t)C2, VT); } - } else { - // If the LHS is a ZERO_EXTEND, perform the comparison on the input. - if (N1.getOpcode() == ISD::ZERO_EXTEND) { - unsigned InSize = MVT::getSizeInBits(N1.getOperand(0).getValueType()); - - // If the comparison constant has bits in the upper part, the - // zero-extended value could never match. - if (C2 & (~0ULL << InSize)) { - unsigned VSize = MVT::getSizeInBits(N1.getValueType()); - switch (Cond) { - case ISD::SETUGT: - case ISD::SETUGE: - case ISD::SETEQ: return getConstant(0, VT); - case ISD::SETULT: - case ISD::SETULE: - case ISD::SETNE: return getConstant(1, VT); - case ISD::SETGT: - case ISD::SETGE: - // True if the sign bit of C2 is set. - return getConstant((C2 & (1ULL << VSize)) != 0, VT); - case ISD::SETLT: - case ISD::SETLE: - // True if the sign bit of C2 isn't set. - return getConstant((C2 & (1ULL << VSize)) == 0, VT); - default: - break; - } - } - - // Otherwise, we can perform the comparison with the low bits. - switch (Cond) { - case ISD::SETEQ: - case ISD::SETNE: - case ISD::SETUGT: - case ISD::SETUGE: - case ISD::SETULT: - case ISD::SETULE: - return getSetCC(VT, N1.getOperand(0), - getConstant(C2, N1.getOperand(0).getValueType()), - Cond); - default: - break; // todo, be more careful with signed comparisons - } - } else if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG && - (Cond == ISD::SETEQ || Cond == ISD::SETNE)) { - MVT::ValueType ExtSrcTy = cast(N1.getOperand(1))->getVT(); - unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy); - MVT::ValueType ExtDstTy = N1.getValueType(); - unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy); - - // If the extended part has any inconsistent bits, it cannot ever - // compare equal. In other words, they have to be all ones or all - // zeros. - uint64_t ExtBits = - (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1)); - if ((C2 & ExtBits) != 0 && (C2 & ExtBits) != ExtBits) - return getConstant(Cond == ISD::SETNE, VT); - - // Otherwise, make this a use of a zext. - return getSetCC(VT, getZeroExtendInReg(N1.getOperand(0), ExtSrcTy), - getConstant(C2 & (~0ULL>>(64-ExtSrcTyBits)), ExtDstTy), - Cond); - } - - uint64_t MinVal, MaxVal; - unsigned OperandBitSize = MVT::getSizeInBits(N2C->getValueType(0)); - if (ISD::isSignedIntSetCC(Cond)) { - MinVal = 1ULL << (OperandBitSize-1); - if (OperandBitSize != 1) // Avoid X >> 64, which is undefined. - MaxVal = ~0ULL >> (65-OperandBitSize); - else - MaxVal = 0; - } else { - MinVal = 0; - MaxVal = ~0ULL >> (64-OperandBitSize); - } - - // Canonicalize GE/LE comparisons to use GT/LT comparisons. - if (Cond == ISD::SETGE || Cond == ISD::SETUGE) { - if (C2 == MinVal) return getConstant(1, VT); // X >= MIN --> true - --C2; // X >= C1 --> X > (C1-1) - return getSetCC(VT, N1, getConstant(C2, N2.getValueType()), - (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT); - } - - if (Cond == ISD::SETLE || Cond == ISD::SETULE) { - if (C2 == MaxVal) return getConstant(1, VT); // X <= MAX --> true - ++C2; // X <= C1 --> X < (C1+1) - return getSetCC(VT, N1, getConstant(C2, N2.getValueType()), - (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT); - } - - if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal) - return getConstant(0, VT); // X < MIN --> false - - // Canonicalize setgt X, Min --> setne X, Min - if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MinVal) - return getSetCC(VT, N1, N2, ISD::SETNE); - - // If we have setult X, 1, turn it into seteq X, 0 - if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal+1) - return getSetCC(VT, N1, getConstant(MinVal, N1.getValueType()), - ISD::SETEQ); - // If we have setugt X, Max-1, turn it into seteq X, Max - else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MaxVal-1) - return getSetCC(VT, N1, getConstant(MaxVal, N1.getValueType()), - ISD::SETEQ); - - // If we have "setcc X, C1", check to see if we can shrink the immediate - // by changing cc. - - // SETUGT X, SINTMAX -> SETLT X, 0 - if (Cond == ISD::SETUGT && OperandBitSize != 1 && - C2 == (~0ULL >> (65-OperandBitSize))) - return getSetCC(VT, N1, getConstant(0, N2.getValueType()), ISD::SETLT); - - // FIXME: Implement the rest of these. - - - // Fold bit comparisons when we can. - if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && - VT == N1.getValueType() && N1.getOpcode() == ISD::AND) - if (ConstantSDNode *AndRHS = - dyn_cast(N1.getOperand(1))) { - if (Cond == ISD::SETNE && C2 == 0) {// (X & 8) != 0 --> (X & 8) >> 3 - // Perform the xform if the AND RHS is a single bit. - if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) { - return getNode(ISD::SRL, VT, N1, - getConstant(Log2_64(AndRHS->getValue()), - TLI.getShiftAmountTy())); - } - } else if (Cond == ISD::SETEQ && C2 == AndRHS->getValue()) { - // (X & 8) == 8 --> (X & 8) >> 3 - // Perform the xform if C2 is a single bit. - if ((C2 & (C2-1)) == 0) { - return getNode(ISD::SRL, VT, N1, - getConstant(Log2_64(C2),TLI.getShiftAmountTy())); - } - } - } } - } else if (isa(N1.Val)) { - // Ensure that the constant occurs on the RHS. - return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond)); } - if (ConstantFPSDNode *N1C = dyn_cast(N1.Val)) if (ConstantFPSDNode *N2C = dyn_cast(N2.Val)) { double C1 = N1C->getValue(), C2 = N2C->getValue(); - + switch (Cond) { default: break; // FIXME: Implement the rest of these! case ISD::SETEQ: return getConstant(C1 == C2, VT); @@ -1007,19 +969,24 @@ SDOperand SelectionDAG::SimplifySetCC(MVT::ValueType VT, SDOperand N1, // Ensure that the constant occurs on the RHS. return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond)); } - + // Could not fold it. return SDOperand(); } + /// getNode - Gets or creates the specified node. /// SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) { - SDNode *&N = NullaryOps[std::make_pair(Opcode, VT)]; - if (!N) { - N = new SDNode(Opcode, VT); - AllNodes.push_back(N); - } + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opcode, getVTList(VT)); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + SDNode *N = new SDNode(Opcode, VT); + CSEMap.InsertNode(N, IP); + + AllNodes.push_back(N); return SDOperand(N, 0); } @@ -1163,10 +1130,12 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, case ISD::BIT_CONVERT: // Basic sanity checking. assert(MVT::getSizeInBits(VT) == MVT::getSizeInBits(Operand.getValueType()) - && "Cannot BIT_CONVERT between two different types!"); + && "Cannot BIT_CONVERT between types of different sizes!"); if (VT == Operand.getValueType()) return Operand; // noop conversion. if (OpOpcode == ISD::BIT_CONVERT) // bitconv(bitconv(x)) -> bitconv(x) return getNode(ISD::BIT_CONVERT, VT, Operand.getOperand(0)); + if (OpOpcode == ISD::UNDEF) + return getNode(ISD::UNDEF, VT); break; case ISD::SCALAR_TO_VECTOR: assert(MVT::isVector(VT) && !MVT::isVector(Operand.getValueType()) && @@ -1187,14 +1156,20 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, } SDNode *N; + SDVTList VTs = getVTList(VT); if (VT != MVT::Flag) { // Don't CSE flag producing nodes - SDNode *&E = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))]; - if (E) return SDOperand(E, 0); - E = N = new SDNode(Opcode, Operand); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opcode, VTs, Operand); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + N = new SDNode(Opcode, Operand); + N->setValueTypes(VTs); + CSEMap.InsertNode(N, IP); } else { N = new SDNode(Opcode, Operand); + N->setValueTypes(VTs); } - N->setValueTypes(VT); AllNodes.push_back(N); return SDOperand(N, 0); } @@ -1274,6 +1249,14 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, ConstantSDNode *N1C = dyn_cast(N1.Val); ConstantSDNode *N2C = dyn_cast(N2.Val); if (N1C) { + if (Opcode == ISD::SIGN_EXTEND_INREG) { + int64_t Val = N1C->getValue(); + unsigned FromBits = MVT::getSizeInBits(cast(N2)->getVT()); + Val <<= 64-FromBits; + Val >>= 64-FromBits; + return getConstant(Val, VT); + } + if (N2C) { uint64_t C1 = N1C->getValue(), C2 = N2C->getValue(); switch (Opcode) { @@ -1357,9 +1340,75 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, } } } + + // Canonicalize an UNDEF to the RHS, even over a constant. + if (N1.getOpcode() == ISD::UNDEF) { + if (isCommutativeBinOp(Opcode)) { + std::swap(N1, N2); + } else { + switch (Opcode) { + case ISD::FP_ROUND_INREG: + case ISD::SIGN_EXTEND_INREG: + case ISD::SUB: + case ISD::FSUB: + case ISD::FDIV: + case ISD::FREM: + case ISD::SRA: + return N1; // fold op(undef, arg2) -> undef + case ISD::UDIV: + case ISD::SDIV: + case ISD::UREM: + case ISD::SREM: + case ISD::SRL: + case ISD::SHL: + return getConstant(0, VT); // fold op(undef, arg2) -> 0 + } + } + } + + // Fold a bunch of operators when the RHS is undef. + if (N2.getOpcode() == ISD::UNDEF) { + switch (Opcode) { + case ISD::ADD: + case ISD::SUB: + case ISD::FADD: + case ISD::FSUB: + case ISD::FMUL: + case ISD::FDIV: + case ISD::FREM: + case ISD::UDIV: + case ISD::SDIV: + case ISD::UREM: + case ISD::SREM: + case ISD::XOR: + return N2; // fold op(arg1, undef) -> undef + case ISD::MUL: + case ISD::AND: + case ISD::SRL: + case ISD::SHL: + return getConstant(0, VT); // fold op(arg1, undef) -> 0 + case ISD::OR: + return getConstant(MVT::getIntVTBitMask(VT), VT); + case ISD::SRA: + return N1; + } + } - // Finally, fold operations that do not require constants. + // Fold operations. switch (Opcode) { + case ISD::AND: + // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's + // worth handling here. + if (N2C && N2C->getValue() == 0) + return N2; + break; + case ISD::OR: + case ISD::XOR: + // (X ^| 0) -> X. This commonly occurs when legalizing i64 values, so it's + // worth handling here. + if (N2C && N2C->getValue() == 0) + return N1; + break; case ISD::FP_ROUND_INREG: if (cast(N2)->getVT() == VT) return N1; // Not actually rounding. break; @@ -1368,6 +1417,21 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, if (EVT == VT) return N1; // Not actually extending break; } + case ISD::EXTRACT_ELEMENT: + assert(N2C && (unsigned)N2C->getValue() < 2 && "Bad EXTRACT_ELEMENT!"); + + // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding + // 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()); + + // EXTRACT_ELEMENT of a constant int is also very common. + if (ConstantSDNode *C = dyn_cast(N1)) { + unsigned Shift = MVT::getSizeInBits(VT) * N2C->getValue(); + return getConstant(C->getValue() >> Shift, VT); + } + break; // FIXME: figure out how to safely handle things like // int foo(int x) { return 1 << (x & 255); } @@ -1393,16 +1457,21 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, // Memoize this node if possible. SDNode *N; + SDVTList VTs = getVTList(VT); if (VT != MVT::Flag) { - SDNode *&BON = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))]; - if (BON) return SDOperand(BON, 0); - - BON = N = new SDNode(Opcode, N1, N2); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opcode, VTs, N1, N2); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + N = new SDNode(Opcode, N1, N2); + N->setValueTypes(VTs); + CSEMap.InsertNode(N, IP); } else { N = new SDNode(Opcode, N1, N2); + N->setValueTypes(VTs); } - N->setValueTypes(VT); AllNodes.push_back(N); return SDOperand(N, 0); } @@ -1412,11 +1481,10 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, // Perform various simplifications. ConstantSDNode *N1C = dyn_cast(N1.Val); ConstantSDNode *N2C = dyn_cast(N2.Val); - ConstantSDNode *N3C = dyn_cast(N3.Val); switch (Opcode) { case ISD::SETCC: { - // Use SimplifySetCC to simplify SETCC's. - SDOperand Simp = SimplifySetCC(VT, N1, N2, cast(N3)->get()); + // Use FoldSetCC to simplify SETCC's. + SDOperand Simp = FoldSetCC(VT, N1, N2, cast(N3)->get()); if (Simp.Val) return Simp; break; } @@ -1445,22 +1513,22 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, break; } - std::vector Ops; - Ops.reserve(3); - Ops.push_back(N1); - Ops.push_back(N2); - Ops.push_back(N3); - // Memoize node if it doesn't produce a flag. SDNode *N; + SDVTList VTs = getVTList(VT); if (VT != MVT::Flag) { - SDNode *&E = OneResultNodes[std::make_pair(Opcode,std::make_pair(VT, Ops))]; - if (E) return SDOperand(E, 0); - E = N = new SDNode(Opcode, N1, N2, N3); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opcode, VTs, N1, N2, N3); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + N = new SDNode(Opcode, N1, N2, N3); + N->setValueTypes(VTs); + CSEMap.InsertNode(N, IP); } else { N = new SDNode(Opcode, N1, N2, N3); + N->setValueTypes(VTs); } - N->setValueTypes(VT); AllNodes.push_back(N); return SDOperand(N, 0); } @@ -1468,37 +1536,114 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4) { - std::vector Ops; - Ops.reserve(4); - Ops.push_back(N1); - Ops.push_back(N2); - Ops.push_back(N3); - Ops.push_back(N4); - return getNode(Opcode, VT, Ops); + SDOperand Ops[] = { N1, N2, N3, N4 }; + return getNode(Opcode, VT, Ops, 4); } SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4, SDOperand N5) { - std::vector Ops; - Ops.reserve(5); - Ops.push_back(N1); - Ops.push_back(N2); - Ops.push_back(N3); - Ops.push_back(N4); - Ops.push_back(N5); - return getNode(Opcode, VT, Ops); + SDOperand Ops[] = { N1, N2, N3, N4, N5 }; + return getNode(Opcode, VT, Ops, 5); } SDOperand SelectionDAG::getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, - SDOperand SV) { - SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))]; - if (N) return SDOperand(N, 0); - N = new SDNode(ISD::LOAD, Chain, Ptr, SV); + const Value *SV, int SVOffset, + bool isVolatile) { + // FIXME: Alignment == 1 for now. + unsigned Alignment = 1; + SDVTList VTs = getVTList(VT, MVT::Other); + SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::LOAD, VTs, Chain, Ptr, Undef); + ID.AddInteger(ISD::UNINDEXED); + ID.AddInteger(ISD::NON_EXTLOAD); + ID.AddInteger(VT); + ID.AddPointer(SV); + ID.AddInteger(SVOffset); + ID.AddInteger(Alignment); + ID.AddInteger(isVolatile); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + SDNode *N = new LoadSDNode(Chain, Ptr, Undef, ISD::UNINDEXED, + ISD::NON_EXTLOAD, VT, SV, SVOffset, Alignment, + isVolatile); + N->setValueTypes(VTs); + CSEMap.InsertNode(N, IP); + AllNodes.push_back(N); + return SDOperand(N, 0); +} + +SDOperand SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, MVT::ValueType VT, + SDOperand Chain, SDOperand Ptr, const Value *SV, + int SVOffset, MVT::ValueType EVT, + bool isVolatile) { + // If they are asking for an extending load from/to the same thing, return a + // normal load. + if (VT == EVT) + ExtType = ISD::NON_EXTLOAD; - // Loads have a token chain. - setNodeValueTypes(N, VT, MVT::Other); + if (MVT::isVector(VT)) + assert(EVT == MVT::getVectorBaseType(VT) && "Invalid vector extload!"); + else + assert(EVT < VT && "Should only be an extending load, not truncating!"); + assert((ExtType == ISD::EXTLOAD || MVT::isInteger(VT)) && + "Cannot sign/zero extend a FP/Vector load!"); + assert(MVT::isInteger(VT) == MVT::isInteger(EVT) && + "Cannot convert from FP to Int or Int -> FP!"); + + // FIXME: Alignment == 1 for now. + unsigned Alignment = 1; + SDVTList VTs = getVTList(VT, MVT::Other); + SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::LOAD, VTs, Chain, Ptr, Undef); + ID.AddInteger(ISD::UNINDEXED); + ID.AddInteger(ExtType); + ID.AddInteger(EVT); + ID.AddPointer(SV); + ID.AddInteger(SVOffset); + ID.AddInteger(Alignment); + ID.AddInteger(isVolatile); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + SDNode *N = new LoadSDNode(Chain, Ptr, Undef, ISD::UNINDEXED, ExtType, EVT, + SV, SVOffset, Alignment, isVolatile); + N->setValueTypes(VTs); + CSEMap.InsertNode(N, IP); + AllNodes.push_back(N); + return SDOperand(N, 0); +} + +SDOperand +SelectionDAG::getIndexedLoad(SDOperand OrigLoad, SDOperand Base, + SDOperand Offset, ISD::MemIndexedMode AM) { + LoadSDNode *LD = cast(OrigLoad); + assert(LD->getOffset().getOpcode() == ISD::UNDEF && + "Load is already a indexed load!"); + MVT::ValueType VT = OrigLoad.getValueType(); + SDVTList VTs = getVTList(VT, Base.getValueType(), MVT::Other); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::LOAD, VTs, LD->getChain(), Base, Offset); + ID.AddInteger(AM); + ID.AddInteger(LD->getExtensionType()); + ID.AddInteger(LD->getLoadedVT()); + ID.AddPointer(LD->getSrcValue()); + ID.AddInteger(LD->getSrcValueOffset()); + ID.AddInteger(LD->getAlignment()); + ID.AddInteger(LD->isVolatile()); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + SDNode *N = new LoadSDNode(LD->getChain(), Base, Offset, AM, + LD->getExtensionType(), LD->getLoadedVT(), + LD->getSrcValue(), LD->getSrcValueOffset(), + LD->getAlignment(), LD->isVolatile()); + N->setValueTypes(VTs); + CSEMap.InsertNode(N, IP); AllNodes.push_back(N); return SDOperand(N, 0); } @@ -1506,43 +1651,104 @@ SDOperand SelectionDAG::getLoad(MVT::ValueType VT, SDOperand SelectionDAG::getVecLoad(unsigned Count, MVT::ValueType EVT, SDOperand Chain, SDOperand Ptr, SDOperand SV) { - SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, EVT))]; - if (N) return SDOperand(N, 0); - std::vector Ops; - Ops.reserve(5); - Ops.push_back(Chain); - Ops.push_back(Ptr); - Ops.push_back(SV); - Ops.push_back(getConstant(Count, MVT::i32)); - Ops.push_back(getValueType(EVT)); - std::vector VTs; - VTs.reserve(2); - VTs.push_back(MVT::Vector); VTs.push_back(MVT::Other); // Add token chain. - return getNode(ISD::VLOAD, VTs, Ops); -} - -SDOperand SelectionDAG::getExtLoad(unsigned Opcode, MVT::ValueType VT, - SDOperand Chain, SDOperand Ptr, SDOperand SV, - MVT::ValueType EVT) { - std::vector Ops; - Ops.reserve(4); - Ops.push_back(Chain); - Ops.push_back(Ptr); - Ops.push_back(SV); - Ops.push_back(getValueType(EVT)); - std::vector VTs; - VTs.reserve(2); - VTs.push_back(VT); VTs.push_back(MVT::Other); // Add token chain. - return getNode(Opcode, VTs, Ops); + SDOperand Ops[] = { Chain, Ptr, SV, getConstant(Count, MVT::i32), + getValueType(EVT) }; + return getNode(ISD::VLOAD, getVTList(MVT::Vector, MVT::Other), Ops, 5); +} + +SDOperand SelectionDAG::getStore(SDOperand Chain, SDOperand Val, + SDOperand Ptr, const Value *SV, int SVOffset, + bool isVolatile) { + MVT::ValueType VT = Val.getValueType(); + + // FIXME: Alignment == 1 for now. + unsigned Alignment = 1; + SDVTList VTs = getVTList(MVT::Other); + SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); + SDOperand Ops[] = { Chain, Val, Ptr, Undef }; + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); + ID.AddInteger(ISD::UNINDEXED); + ID.AddInteger(false); + ID.AddInteger(VT); + ID.AddPointer(SV); + ID.AddInteger(SVOffset); + ID.AddInteger(Alignment); + ID.AddInteger(isVolatile); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + SDNode *N = new StoreSDNode(Chain, Val, Ptr, Undef, ISD::UNINDEXED, false, + VT, SV, SVOffset, Alignment, isVolatile); + N->setValueTypes(VTs); + CSEMap.InsertNode(N, IP); + AllNodes.push_back(N); + return SDOperand(N, 0); } -SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) { - assert((!V || isa(V->getType())) && - "SrcValue is not a pointer?"); - SDNode *&N = ValueNodes[std::make_pair(V, Offset)]; - if (N) return SDOperand(N, 0); +SDOperand SelectionDAG::getTruncStore(SDOperand Chain, SDOperand Val, + SDOperand Ptr, const Value *SV, + int SVOffset, MVT::ValueType SVT, + bool isVolatile) { + MVT::ValueType VT = Val.getValueType(); + bool isTrunc = VT != SVT; + + assert(VT > SVT && "Not a truncation?"); + assert(MVT::isInteger(VT) == MVT::isInteger(SVT) && + "Can't do FP-INT conversion!"); + + // FIXME: Alignment == 1 for now. + unsigned Alignment = 1; + SDVTList VTs = getVTList(MVT::Other); + SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); + SDOperand Ops[] = { Chain, Val, Ptr, Undef }; + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); + ID.AddInteger(ISD::UNINDEXED); + ID.AddInteger(isTrunc); + ID.AddInteger(SVT); + ID.AddPointer(SV); + ID.AddInteger(SVOffset); + ID.AddInteger(Alignment); + ID.AddInteger(isVolatile); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + SDNode *N = new StoreSDNode(Chain, Val, Ptr, Undef, ISD::UNINDEXED, isTrunc, + SVT, SV, SVOffset, Alignment, isVolatile); + N->setValueTypes(VTs); + CSEMap.InsertNode(N, IP); + AllNodes.push_back(N); + return SDOperand(N, 0); +} - N = new SrcValueSDNode(V, Offset); +SDOperand +SelectionDAG::getIndexedStore(SDOperand OrigStore, SDOperand Base, + SDOperand 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 }; + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); + ID.AddInteger(AM); + ID.AddInteger(ST->isTruncatingStore()); + ID.AddInteger(ST->getStoredVT()); + ID.AddPointer(ST->getSrcValue()); + ID.AddInteger(ST->getSrcValueOffset()); + ID.AddInteger(ST->getAlignment()); + ID.AddInteger(ST->isVolatile()); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + SDNode *N = new StoreSDNode(ST->getChain(), ST->getValue(), + Base, Offset, AM, + ST->isTruncatingStore(), ST->getStoredVT(), + ST->getSrcValue(), ST->getSrcValueOffset(), + ST->getAlignment(), ST->isVolatile()); + N->setValueTypes(VTs); + CSEMap.InsertNode(N, IP); AllNodes.push_back(N); return SDOperand(N, 0); } @@ -1550,20 +1756,13 @@ SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) { SDOperand SelectionDAG::getVAArg(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, SDOperand SV) { - std::vector Ops; - Ops.reserve(3); - Ops.push_back(Chain); - Ops.push_back(Ptr); - Ops.push_back(SV); - std::vector VTs; - VTs.reserve(2); - VTs.push_back(VT); VTs.push_back(MVT::Other); // Add token chain. - return getNode(ISD::VAARG, VTs, Ops); + SDOperand Ops[] = { Chain, Ptr, SV }; + return getNode(ISD::VAARG, getVTList(VT, MVT::Other), Ops, 3); } SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, - std::vector &Ops) { - switch (Ops.size()) { + const SDOperand *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]); @@ -1571,31 +1770,10 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, default: break; } - ConstantSDNode *N1C = dyn_cast(Ops[1].Val); switch (Opcode) { default: break; - case ISD::TRUNCSTORE: { - assert(Ops.size() == 5 && "TRUNCSTORE takes 5 operands!"); - MVT::ValueType EVT = cast(Ops[4])->getVT(); -#if 0 // FIXME: If the target supports EVT natively, convert to a truncate/store - // If this is a truncating store of a constant, convert to the desired type - // and store it instead. - if (isa(Ops[0])) { - SDOperand Op = getNode(ISD::TRUNCATE, EVT, N1); - if (isa(Op)) - N1 = Op; - } - // Also for ConstantFP? -#endif - if (Ops[0].getValueType() == EVT) // Normal store? - return getNode(ISD::STORE, VT, Ops[0], Ops[1], Ops[2], Ops[3]); - assert(Ops[1].getValueType() > EVT && "Not a truncation?"); - assert(MVT::isInteger(Ops[1].getValueType()) == MVT::isInteger(EVT) && - "Can't do FP-INT conversion!"); - break; - } case ISD::SELECT_CC: { - assert(Ops.size() == 5 && "SELECT_CC takes 5 operands!"); + assert(NumOps == 5 && "SELECT_CC takes 5 operands!"); assert(Ops[0].getValueType() == Ops[1].getValueType() && "LHS and RHS of condition must have same type!"); assert(Ops[2].getValueType() == Ops[3].getValueType() && @@ -1605,7 +1783,7 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, break; } case ISD::BR_CC: { - assert(Ops.size() == 5 && "BR_CC takes 5 operands!"); + assert(NumOps == 5 && "BR_CC takes 5 operands!"); assert(Ops[2].getValueType() == Ops[3].getValueType() && "LHS/RHS of comparison should match types!"); break; @@ -1614,49 +1792,45 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, // Memoize nodes. SDNode *N; + SDVTList VTs = getVTList(VT); if (VT != MVT::Flag) { - SDNode *&E = - OneResultNodes[std::make_pair(Opcode, std::make_pair(VT, Ops))]; - if (E) return SDOperand(E, 0); - E = N = new SDNode(Opcode, Ops); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDOperand(E, 0); + N = new SDNode(Opcode, Ops, NumOps); + N->setValueTypes(VTs); + CSEMap.InsertNode(N, IP); } else { - N = new SDNode(Opcode, Ops); + N = new SDNode(Opcode, Ops, NumOps); + N->setValueTypes(VTs); } - N->setValueTypes(VT); AllNodes.push_back(N); return SDOperand(N, 0); } SDOperand SelectionDAG::getNode(unsigned Opcode, std::vector &ResultTys, - std::vector &Ops) { - if (ResultTys.size() == 1) - return getNode(Opcode, ResultTys[0], Ops); + const SDOperand *Ops, unsigned NumOps) { + return getNode(Opcode, getNodeValueTypes(ResultTys), ResultTys.size(), + Ops, NumOps); +} - switch (Opcode) { - case ISD::EXTLOAD: - case ISD::SEXTLOAD: - case ISD::ZEXTLOAD: { - MVT::ValueType EVT = cast(Ops[3])->getVT(); - assert(Ops.size() == 4 && ResultTys.size() == 2 && "Bad *EXTLOAD!"); - // If they are asking for an extending load from/to the same thing, return a - // normal load. - if (ResultTys[0] == EVT) - return getLoad(ResultTys[0], Ops[0], Ops[1], Ops[2]); - if (MVT::isVector(ResultTys[0])) { - assert(EVT == MVT::getVectorBaseType(ResultTys[0]) && - "Invalid vector extload!"); - } else { - assert(EVT < ResultTys[0] && - "Should only be an extending load, not truncating!"); - } - assert((Opcode == ISD::EXTLOAD || MVT::isInteger(ResultTys[0])) && - "Cannot sign/zero extend a FP/Vector load!"); - assert(MVT::isInteger(ResultTys[0]) == MVT::isInteger(EVT) && - "Cannot convert from FP to Int or Int -> FP!"); - break; - } +SDOperand SelectionDAG::getNode(unsigned Opcode, + const MVT::ValueType *VTs, unsigned NumVTs, + const SDOperand *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, + const SDOperand *Ops, unsigned NumOps) { + if (VTList.NumVTs == 1) + return getNode(Opcode, VTList.VTs[0], Ops, NumOps); + switch (Opcode) { // FIXME: figure out how to safely handle things like // int foo(int x) { return 1 << (x & 255); } // int bar() { return foo(256); } @@ -1681,54 +1855,83 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, // Memoize the node unless it returns a flag. SDNode *N; - if (ResultTys.back() != MVT::Flag) { - SDNode *&E = - ArbitraryNodes[std::make_pair(Opcode, std::make_pair(ResultTys, Ops))]; - if (E) return SDOperand(E, 0); - E = N = new SDNode(Opcode, Ops); + 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 SDOperand(E, 0); + N = new SDNode(Opcode, Ops, NumOps); + N->setValueTypes(VTList); + CSEMap.InsertNode(N, IP); } else { - N = new SDNode(Opcode, Ops); + N = new SDNode(Opcode, Ops, NumOps); + N->setValueTypes(VTList); } - setNodeValueTypes(N, ResultTys); AllNodes.push_back(N); return SDOperand(N, 0); } -void SelectionDAG::setNodeValueTypes(SDNode *N, - std::vector &RetVals) { - switch (RetVals.size()) { - case 0: return; - case 1: N->setValueTypes(RetVals[0]); return; - case 2: setNodeValueTypes(N, RetVals[0], RetVals[1]); return; - default: break; - } - - std::list >::iterator I = - std::find(VTList.begin(), VTList.end(), RetVals); - if (I == VTList.end()) { - VTList.push_front(RetVals); - I = VTList.begin(); - } - - N->setValueTypes(&(*I)[0], I->size()); +SDVTList SelectionDAG::getVTList(MVT::ValueType VT) { + return makeVTList(SDNode::getValueTypeList(VT), 1); } -void SelectionDAG::setNodeValueTypes(SDNode *N, MVT::ValueType VT1, - MVT::ValueType VT2) { +SDVTList SelectionDAG::getVTList(MVT::ValueType VT1, MVT::ValueType VT2) { for (std::list >::iterator I = VTList.begin(), E = VTList.end(); I != E; ++I) { - if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2) { - N->setValueTypes(&(*I)[0], 2); - return; - } + 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::ValueType VT1, MVT::ValueType VT2, + MVT::ValueType 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); - N->setValueTypes(&(*VTList.begin())[0], 2); + return makeVTList(&(*VTList.begin())[0], 3); } +SDVTList SelectionDAG::getVTList(const MVT::ValueType *VTs, unsigned NumVTs) { + switch (NumVTs) { + case 0: assert(0 && "Cannot have nodes without results!"); + case 1: return makeVTList(SDNode::getValueTypeList(VTs[0]), 1); + case 2: return getVTList(VTs[0], VTs[1]); + case 3: return getVTList(VTs[0], VTs[1], VTs[2]); + 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; + + bool NoMatch = false; + for (unsigned i = 2; i != NumVTs; ++i) + if (VTs[i] != (*I)[i]) { + NoMatch = true; + break; + } + if (!NoMatch) + return makeVTList(&*I->begin(), NumVTs); + } + + VTList.push_front(std::vector(VTs, VTs+NumVTs)); + return makeVTList(&*VTList.begin()->begin(), NumVTs); +} + + /// UpdateNodeOperands - *Mutate* the specified node in-place to have the /// specified operands. If the resultant node already exists in the DAG, /// this does not modify the specified node, instead it returns the node that @@ -1744,12 +1947,12 @@ UpdateNodeOperands(SDOperand InN, SDOperand Op) { if (Op == N->getOperand(0)) return InN; // See if the modified node already exists. - SDNode **NewSlot = FindModifiedNodeSlot(N, Op); - if (NewSlot && *NewSlot) - return SDOperand(*NewSlot, InN.ResNo); + void *InsertPos = 0; + if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos)) + return SDOperand(Existing, InN.ResNo); // Nope it doesn't. Remove the node from it's current place in the maps. - if (NewSlot) + if (InsertPos) RemoveNodeFromCSEMaps(N); // Now we update the operands. @@ -1758,7 +1961,7 @@ UpdateNodeOperands(SDOperand InN, SDOperand Op) { N->OperandList[0] = Op; // If this gets put into a CSE map, add it. - if (NewSlot) *NewSlot = N; + if (InsertPos) CSEMap.InsertNode(N, InsertPos); return InN; } @@ -1768,17 +1971,16 @@ UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) { assert(N->getNumOperands() == 2 && "Update with wrong number of operands"); // Check to see if there is no change. - bool AnyChange = false; if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1)) return InN; // No operands changed, just return the input node. // See if the modified node already exists. - SDNode **NewSlot = FindModifiedNodeSlot(N, Op1, Op2); - if (NewSlot && *NewSlot) - return SDOperand(*NewSlot, InN.ResNo); + void *InsertPos = 0; + if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos)) + return SDOperand(Existing, InN.ResNo); // Nope it doesn't. Remove the node from it's current place in the maps. - if (NewSlot) + if (InsertPos) RemoveNodeFromCSEMaps(N); // Now we update the operands. @@ -1794,51 +1996,38 @@ UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) { } // If this gets put into a CSE map, add it. - if (NewSlot) *NewSlot = N; + if (InsertPos) CSEMap.InsertNode(N, InsertPos); return InN; } SDOperand SelectionDAG:: UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3) { - std::vector Ops; - Ops.push_back(Op1); - Ops.push_back(Op2); - Ops.push_back(Op3); - return UpdateNodeOperands(N, Ops); + SDOperand Ops[] = { Op1, Op2, Op3 }; + return UpdateNodeOperands(N, Ops, 3); } SDOperand SelectionDAG:: UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3, SDOperand Op4) { - std::vector Ops; - Ops.push_back(Op1); - Ops.push_back(Op2); - Ops.push_back(Op3); - Ops.push_back(Op4); - return UpdateNodeOperands(N, Ops); + SDOperand 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) { - std::vector Ops; - Ops.push_back(Op1); - Ops.push_back(Op2); - Ops.push_back(Op3); - Ops.push_back(Op4); - Ops.push_back(Op5); - return UpdateNodeOperands(N, Ops); + SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5 }; + return UpdateNodeOperands(N, Ops, 5); } SDOperand SelectionDAG:: -UpdateNodeOperands(SDOperand InN, const std::vector &Ops) { +UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) { SDNode *N = InN.Val; - assert(N->getNumOperands() == Ops.size() && + assert(N->getNumOperands() == NumOps && "Update with wrong number of operands"); // Check to see if there is no change. - unsigned NumOps = Ops.size(); bool AnyChange = false; for (unsigned i = 0; i != NumOps; ++i) { if (Ops[i] != N->getOperand(i)) { @@ -1851,12 +2040,12 @@ UpdateNodeOperands(SDOperand InN, const std::vector &Ops) { if (!AnyChange) return InN; // See if the modified node already exists. - SDNode **NewSlot = FindModifiedNodeSlot(N, Ops); - if (NewSlot && *NewSlot) - return SDOperand(*NewSlot, InN.ResNo); + void *InsertPos = 0; + if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos)) + return SDOperand(Existing, InN.ResNo); // Nope it doesn't. Remove the node from it's current place in the maps. - if (NewSlot) + if (InsertPos) RemoveNodeFromCSEMaps(N); // Now we update the operands. @@ -1869,7 +2058,7 @@ UpdateNodeOperands(SDOperand InN, const std::vector &Ops) { } // If this gets put into a CSE map, add it. - if (NewSlot) *NewSlot = N; + if (InsertPos) CSEMap.InsertNode(N, InsertPos); return InN; } @@ -1884,270 +2073,142 @@ UpdateNodeOperands(SDOperand InN, const std::vector &Ops) { /// 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. -SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT::ValueType VT) { - // If an identical node already exists, use it. - SDNode *&ON = NullaryOps[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, VT)]; - if (ON) return SDOperand(ON, 0); - +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, + MVT::ValueType VT) { + SDVTList VTs = getVTList(VT); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs); + void *IP = 0; + if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) + return ON; + RemoveNodeFromCSEMaps(N); N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); - N->setValueTypes(VT); + N->setValueTypes(VTs); - ON = N; // Memoize the new node. - return SDOperand(N, 0); + CSEMap.InsertNode(N, IP); + return N; } -SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT::ValueType VT, SDOperand Op1) { +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, + MVT::ValueType VT, SDOperand Op1) { // If an identical node already exists, use it. - SDNode *&ON = UnaryOps[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, - std::make_pair(Op1, VT))]; - if (ON) return SDOperand(ON, 0); - + SDVTList VTs = getVTList(VT); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1); + void *IP = 0; + if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) + return ON; + RemoveNodeFromCSEMaps(N); N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); - N->setValueTypes(VT); + N->setValueTypes(VTs); N->setOperands(Op1); - - ON = N; // Memoize the new node. - return SDOperand(N, 0); + CSEMap.InsertNode(N, IP); + return N; } -SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT::ValueType VT, SDOperand Op1, - SDOperand Op2) { +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, + MVT::ValueType VT, SDOperand Op1, + SDOperand Op2) { // If an identical node already exists, use it. - SDNode *&ON = BinaryOps[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, - std::make_pair(Op1, Op2))]; - if (ON) return SDOperand(ON, 0); - + SDVTList VTs = getVTList(VT); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2); + void *IP = 0; + if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) + return ON; + RemoveNodeFromCSEMaps(N); N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); - N->setValueTypes(VT); + N->setValueTypes(VTs); N->setOperands(Op1, Op2); - ON = N; // Memoize the new node. - return SDOperand(N, 0); + CSEMap.InsertNode(N, IP); // Memoize the new node. + return N; } -SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT::ValueType VT, SDOperand Op1, - SDOperand Op2, SDOperand Op3) { +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, + MVT::ValueType VT, SDOperand Op1, + SDOperand Op2, SDOperand Op3) { // If an identical node already exists, use it. - std::vector OpList; - OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); - SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, - std::make_pair(VT, OpList))]; - if (ON) return SDOperand(ON, 0); - + SDVTList VTs = getVTList(VT); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2, Op3); + void *IP = 0; + if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) + return ON; + RemoveNodeFromCSEMaps(N); N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); - N->setValueTypes(VT); + N->setValueTypes(VTs); N->setOperands(Op1, Op2, Op3); - ON = N; // Memoize the new node. - return SDOperand(N, 0); -} - -SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT::ValueType VT, SDOperand Op1, - SDOperand Op2, SDOperand Op3, - SDOperand Op4) { - // If an identical node already exists, use it. - std::vector OpList; - OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); - OpList.push_back(Op4); - SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, - std::make_pair(VT, OpList))]; - if (ON) return SDOperand(ON, 0); - - RemoveNodeFromCSEMaps(N); - N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); - N->setValueTypes(VT); - N->setOperands(Op1, Op2, Op3, Op4); - - ON = N; // Memoize the new node. - return SDOperand(N, 0); -} - -SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT::ValueType VT, SDOperand Op1, - SDOperand Op2, SDOperand Op3,SDOperand Op4, - SDOperand Op5) { - // If an identical node already exists, use it. - std::vector OpList; - OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); - OpList.push_back(Op4); OpList.push_back(Op5); - SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, - std::make_pair(VT, OpList))]; - if (ON) return SDOperand(ON, 0); - - RemoveNodeFromCSEMaps(N); - N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); - N->setValueTypes(VT); - N->setOperands(Op1, Op2, Op3, Op4, Op5); - - ON = N; // Memoize the new node. - return SDOperand(N, 0); -} - -SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT::ValueType VT, SDOperand Op1, - SDOperand Op2, SDOperand Op3,SDOperand Op4, - SDOperand Op5, SDOperand Op6) { - // If an identical node already exists, use it. - std::vector OpList; - OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); - OpList.push_back(Op4); OpList.push_back(Op5); OpList.push_back(Op6); - SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, - std::make_pair(VT, OpList))]; - if (ON) return SDOperand(ON, 0); - - RemoveNodeFromCSEMaps(N); - N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); - N->setValueTypes(VT); - N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6); - - ON = N; // Memoize the new node. - return SDOperand(N, 0); + CSEMap.InsertNode(N, IP); // Memoize the new node. + return N; } -SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT::ValueType VT, SDOperand Op1, - SDOperand Op2, SDOperand Op3,SDOperand Op4, - SDOperand Op5, SDOperand Op6, - SDOperand Op7) { +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, + MVT::ValueType VT, const SDOperand *Ops, + unsigned NumOps) { // If an identical node already exists, use it. - std::vector OpList; - OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); - OpList.push_back(Op4); OpList.push_back(Op5); OpList.push_back(Op6); - OpList.push_back(Op7); - SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, - std::make_pair(VT, OpList))]; - if (ON) return SDOperand(ON, 0); - + 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); - N->setValueTypes(VT); - N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6, Op7); + N->setValueTypes(VTs); + N->setOperands(Ops, NumOps); - ON = N; // Memoize the new node. - return SDOperand(N, 0); + CSEMap.InsertNode(N, IP); // Memoize the new node. + return N; } -SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT::ValueType VT, SDOperand Op1, - SDOperand Op2, SDOperand Op3,SDOperand Op4, - SDOperand Op5, SDOperand Op6, - SDOperand Op7, SDOperand Op8) { - // If an identical node already exists, use it. - std::vector OpList; - OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); - OpList.push_back(Op4); OpList.push_back(Op5); OpList.push_back(Op6); - OpList.push_back(Op7); OpList.push_back(Op8); - SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, - std::make_pair(VT, OpList))]; - if (ON) return SDOperand(ON, 0); - RemoveNodeFromCSEMaps(N); - N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); - N->setValueTypes(VT); - N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6, Op7, Op8); - - ON = N; // Memoize the new node. - return SDOperand(N, 0); -} - -SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT::ValueType VT1, MVT::ValueType VT2, - SDOperand Op1, SDOperand Op2) { - // If an identical node already exists, use it. - std::vector OpList; - OpList.push_back(Op1); OpList.push_back(Op2); - std::vector VTList; - VTList.push_back(VT1); VTList.push_back(VT2); - SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, - std::make_pair(VTList, OpList))]; - if (ON) return SDOperand(ON, 0); +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, + MVT::ValueType VT1, MVT::ValueType VT2, + SDOperand Op1, SDOperand Op2) { + SDVTList VTs = getVTList(VT1, VT2); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2); + void *IP = 0; + if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) + return ON; RemoveNodeFromCSEMaps(N); N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); - setNodeValueTypes(N, VT1, VT2); + N->setValueTypes(VTs); N->setOperands(Op1, Op2); - ON = N; // Memoize the new node. - return SDOperand(N, 0); + CSEMap.InsertNode(N, IP); // Memoize the new node. + return N; } -SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT::ValueType VT1, MVT::ValueType VT2, - SDOperand Op1, SDOperand Op2, - SDOperand Op3) { +SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, + MVT::ValueType VT1, MVT::ValueType VT2, + SDOperand Op1, SDOperand Op2, + SDOperand Op3) { // If an identical node already exists, use it. - std::vector OpList; - OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); - std::vector VTList; - VTList.push_back(VT1); VTList.push_back(VT2); - SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, - std::make_pair(VTList, OpList))]; - if (ON) return SDOperand(ON, 0); + SDVTList VTs = getVTList(VT1, VT2); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2, Op3); + void *IP = 0; + if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) + return ON; RemoveNodeFromCSEMaps(N); N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); - setNodeValueTypes(N, VT1, VT2); + N->setValueTypes(VTs); N->setOperands(Op1, Op2, Op3); - ON = N; // Memoize the new node. - return SDOperand(N, 0); + CSEMap.InsertNode(N, IP); // Memoize the new node. + return N; } -SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT::ValueType VT1, MVT::ValueType VT2, - SDOperand Op1, SDOperand Op2, - SDOperand Op3, SDOperand Op4) { - // If an identical node already exists, use it. - std::vector OpList; - OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); - OpList.push_back(Op4); - std::vector VTList; - VTList.push_back(VT1); VTList.push_back(VT2); - SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, - std::make_pair(VTList, OpList))]; - if (ON) return SDOperand(ON, 0); - - RemoveNodeFromCSEMaps(N); - N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); - setNodeValueTypes(N, VT1, VT2); - N->setOperands(Op1, Op2, Op3, Op4); - - ON = N; // Memoize the new node. - return SDOperand(N, 0); -} - -SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, - MVT::ValueType VT1, MVT::ValueType VT2, - SDOperand Op1, SDOperand Op2, - SDOperand Op3, SDOperand Op4, - SDOperand Op5) { - // If an identical node already exists, use it. - std::vector OpList; - OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); - OpList.push_back(Op4); OpList.push_back(Op5); - std::vector VTList; - VTList.push_back(VT1); VTList.push_back(VT2); - SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, - std::make_pair(VTList, OpList))]; - if (ON) return SDOperand(ON, 0); - - RemoveNodeFromCSEMaps(N); - N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); - setNodeValueTypes(N, VT1, VT2); - N->setOperands(Op1, Op2, Op3, Op4, Op5); - - ON = N; // Memoize the new node. - return SDOperand(N, 0); -} /// getTargetNode - These are used for target selectors to create a new node /// with specified return type(s), target opcode, and operands. @@ -2171,228 +2232,49 @@ SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val; } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, - SDOperand Op1, SDOperand Op2, SDOperand Op3, - SDOperand Op4) { - return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4).Val; -} -SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, - SDOperand Op1, SDOperand Op2, SDOperand Op3, - SDOperand Op4, SDOperand Op5) { - return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4, Op5).Val; -} -SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, - SDOperand Op1, SDOperand Op2, SDOperand Op3, - SDOperand Op4, SDOperand Op5, SDOperand Op6) { - std::vector Ops; - Ops.reserve(6); - Ops.push_back(Op1); - Ops.push_back(Op2); - Ops.push_back(Op3); - Ops.push_back(Op4); - Ops.push_back(Op5); - Ops.push_back(Op6); - return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val; -} -SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, - SDOperand Op1, SDOperand Op2, SDOperand Op3, - SDOperand Op4, SDOperand Op5, SDOperand Op6, - SDOperand Op7) { - std::vector Ops; - Ops.reserve(7); - Ops.push_back(Op1); - Ops.push_back(Op2); - Ops.push_back(Op3); - Ops.push_back(Op4); - Ops.push_back(Op5); - Ops.push_back(Op6); - Ops.push_back(Op7); - return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val; -} -SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, - SDOperand Op1, SDOperand Op2, SDOperand Op3, - SDOperand Op4, SDOperand Op5, SDOperand Op6, - SDOperand Op7, SDOperand Op8) { - std::vector Ops; - Ops.reserve(8); - Ops.push_back(Op1); - Ops.push_back(Op2); - Ops.push_back(Op3); - Ops.push_back(Op4); - Ops.push_back(Op5); - Ops.push_back(Op6); - Ops.push_back(Op7); - Ops.push_back(Op8); - return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val; -} -SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, - std::vector &Ops) { - return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val; + const SDOperand *Ops, unsigned NumOps) { + return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, NumOps).Val; } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, MVT::ValueType VT2, SDOperand Op1) { - std::vector ResultTys; - ResultTys.push_back(VT1); - ResultTys.push_back(VT2); - std::vector Ops; - Ops.push_back(Op1); - return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; -} -SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, - MVT::ValueType VT2, SDOperand Op1, SDOperand Op2) { - std::vector ResultTys; - ResultTys.push_back(VT1); - ResultTys.push_back(VT2); - std::vector Ops; - Ops.push_back(Op1); - Ops.push_back(Op2); - return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; + const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2); + return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op1, 1).Val; } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, - MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, - SDOperand Op3) { - std::vector ResultTys; - ResultTys.push_back(VT1); - ResultTys.push_back(VT2); - std::vector Ops; - Ops.push_back(Op1); - Ops.push_back(Op2); - Ops.push_back(Op3); - return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; + MVT::ValueType VT2, SDOperand Op1, + SDOperand Op2) { + const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2); + SDOperand Ops[] = { Op1, Op2 }; + return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 2).Val; } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, - MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, - SDOperand Op3, SDOperand Op4) { - std::vector ResultTys; - ResultTys.push_back(VT1); - ResultTys.push_back(VT2); - std::vector Ops; - Ops.push_back(Op1); - Ops.push_back(Op2); - Ops.push_back(Op3); - Ops.push_back(Op4); - return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; + MVT::ValueType VT2, SDOperand Op1, + SDOperand Op2, SDOperand Op3) { + const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2); + SDOperand Ops[] = { Op1, Op2, Op3 }; + return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 3).Val; } -SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, - MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, - SDOperand Op3, SDOperand Op4, SDOperand Op5) { - std::vector ResultTys; - ResultTys.push_back(VT1); - ResultTys.push_back(VT2); - std::vector Ops; - Ops.push_back(Op1); - Ops.push_back(Op2); - Ops.push_back(Op3); - Ops.push_back(Op4); - Ops.push_back(Op5); - return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; -} -SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, - MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, - SDOperand Op3, SDOperand Op4, SDOperand Op5, - SDOperand Op6) { - std::vector ResultTys; - ResultTys.push_back(VT1); - ResultTys.push_back(VT2); - std::vector Ops; - Ops.push_back(Op1); - Ops.push_back(Op2); - Ops.push_back(Op3); - Ops.push_back(Op4); - Ops.push_back(Op5); - Ops.push_back(Op6); - return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; -} -SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, - MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, - SDOperand Op3, SDOperand Op4, SDOperand Op5, - SDOperand Op6, SDOperand Op7) { - std::vector ResultTys; - ResultTys.push_back(VT1); - ResultTys.push_back(VT2); - std::vector Ops; - Ops.push_back(Op1); - Ops.push_back(Op2); - Ops.push_back(Op3); - Ops.push_back(Op4); - Ops.push_back(Op5); - Ops.push_back(Op6); - Ops.push_back(Op7); - return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; +SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, + MVT::ValueType VT2, + const SDOperand *Ops, unsigned NumOps) { + const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2); + return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, NumOps).Val; } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, MVT::ValueType VT2, MVT::ValueType VT3, SDOperand Op1, SDOperand Op2) { - std::vector ResultTys; - ResultTys.push_back(VT1); - ResultTys.push_back(VT2); - ResultTys.push_back(VT3); - std::vector Ops; - Ops.push_back(Op1); - Ops.push_back(Op2); - return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; -} -SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, - MVT::ValueType VT2, MVT::ValueType VT3, - SDOperand Op1, SDOperand Op2, - SDOperand Op3, SDOperand Op4, SDOperand Op5) { - std::vector ResultTys; - ResultTys.push_back(VT1); - ResultTys.push_back(VT2); - ResultTys.push_back(VT3); - std::vector Ops; - Ops.push_back(Op1); - Ops.push_back(Op2); - Ops.push_back(Op3); - Ops.push_back(Op4); - Ops.push_back(Op5); - return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; -} -SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, - MVT::ValueType VT2, MVT::ValueType VT3, - SDOperand Op1, SDOperand Op2, - SDOperand Op3, SDOperand Op4, SDOperand Op5, - SDOperand Op6) { - std::vector ResultTys; - ResultTys.push_back(VT1); - ResultTys.push_back(VT2); - ResultTys.push_back(VT3); - std::vector Ops; - Ops.push_back(Op1); - Ops.push_back(Op2); - Ops.push_back(Op3); - Ops.push_back(Op4); - Ops.push_back(Op5); - Ops.push_back(Op6); - return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; -} -SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, - MVT::ValueType VT2, MVT::ValueType VT3, - SDOperand Op1, SDOperand Op2, - SDOperand Op3, SDOperand Op4, SDOperand Op5, - SDOperand Op6, SDOperand Op7) { - std::vector ResultTys; - ResultTys.push_back(VT1); - ResultTys.push_back(VT2); - ResultTys.push_back(VT3); - std::vector Ops; - Ops.push_back(Op1); - Ops.push_back(Op2); - Ops.push_back(Op3); - Ops.push_back(Op4); - Ops.push_back(Op5); - Ops.push_back(Op6); - Ops.push_back(Op7); - return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; + const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3); + SDOperand Ops[] = { Op1, Op2 }; + return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 2).Val; } SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, - MVT::ValueType VT2, std::vector &Ops) { - std::vector ResultTys; - ResultTys.push_back(VT1); - ResultTys.push_back(VT2); - return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; + MVT::ValueType VT2, MVT::ValueType VT3, + const SDOperand *Ops, unsigned NumOps) { + const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3); + return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, NumOps).Val; } -// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. +/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. /// This can cause recursive merging of nodes in the DAG. /// /// This version assumes From/To have a single result value. @@ -2478,11 +2360,9 @@ 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, - const std::vector &To, + const SDOperand *To, std::vector *Deleted) { - assert(From->getNumValues() == To.size() && - "Incorrect number of values to replace with!"); - if (To.size() == 1 && To[0].Val->getNumValues() == 1) { + if (From->getNumValues() == 1 && To[0].Val->getNumValues() == 1) { // Degenerate case handled above. ReplaceAllUsesWith(SDOperand(From, 0), To[0], Deleted); return; @@ -2576,10 +2456,73 @@ 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++); + } + 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->Val; + unsigned Degree = --InDegree[P->getNodeId()]; + if (Degree == 0) + Sources.push_back(P); + } + } + + // 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++); + + return Id; +} + + + //===----------------------------------------------------------------------===// // SDNode Class //===----------------------------------------------------------------------===// +// Out-of-line virtual method to give class a home. +void SDNode::ANCHOR() { +} + +/// Profile - Gather unique data for the node. +/// +void SDNode::Profile(FoldingSetNodeID &ID) { + AddNodeIDNode(ID, this); +} /// getValueTypeList - Return a pointer to the specified value type. /// @@ -2588,7 +2531,7 @@ MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) { VTs[VT] = VT; return &VTs[VT]; } - + /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the /// indicated value. This method ignores uses of other values defined by this /// operation. @@ -2604,8 +2547,7 @@ bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const { std::set UsersHandled; - for (std::vector::const_iterator UI = Uses.begin(), E = Uses.end(); - UI != E; ++UI) { + for (SDNode::use_iterator UI = Uses.begin(), E = Uses.end(); UI != E; ++UI) { SDNode *User = *UI; if (User->getNumOperands() == 1 || UsersHandled.insert(User).second) // First time we've seen this? @@ -2622,7 +2564,8 @@ bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const { } -// isOnlyUse - Return true if this node is the only use of N. +/// isOnlyUse - Return true if this node is the only use of N. +/// bool SDNode::isOnlyUse(SDNode *N) const { bool Seen = false; for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) { @@ -2636,7 +2579,8 @@ bool SDNode::isOnlyUse(SDNode *N) const { return Seen; } -// isOperand - Return true if this node is an operand of N. +/// isOperand - Return true if this node is an operand of N. +/// bool SDOperand::isOperand(SDNode *N) const { for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) if (*this == N->getOperand(i)) @@ -2651,6 +2595,37 @@ bool SDNode::isOperand(SDNode *N) const { return false; } +static void findPredecessor(SDNode *N, const SDNode *P, bool &found, + std::set &Visited) { + if (found || !Visited.insert(N).second) + return; + + for (unsigned i = 0, e = N->getNumOperands(); !found && i != e; ++i) { + SDNode *Op = N->getOperand(i).Val; + if (Op == P) { + found = true; + return; + } + findPredecessor(Op, P, found, Visited); + } +} + +/// isPredecessor - Return true if this node is a predecessor of N. This node +/// is either an operand of N or it can be reached by recursively traversing +/// up the operands. +/// NOTE: this is an expensive method. Use it carefully. +bool SDNode::isPredecessor(SDNode *N) const { + std::set Visited; + bool found = false; + findPredecessor(N, this, found, Visited); + return found; +} + +uint64_t SDNode::getConstantOperandVal(unsigned Num) const { + assert(Num < NumOperands && "Invalid child # of SDNode!"); + return cast(OperandList[Num])->getValue(); +} + const char *SDNode::getOperationName(const SelectionDAG *G) const { switch (getOpcode()) { default: @@ -2688,6 +2663,8 @@ const char *SDNode::getOperationName(const SelectionDAG *G) const { case ISD::ConstantFP: return "ConstantFP"; case ISD::GlobalAddress: return "GlobalAddress"; case ISD::FrameIndex: return "FrameIndex"; + case ISD::JumpTable: return "JumpTable"; + case ISD::GLOBAL_OFFSET_TABLE: return "GLOBAL_OFFSET_TABLE"; case ISD::ConstantPool: return "ConstantPool"; case ISD::ExternalSymbol: return "ExternalSymbol"; case ISD::INTRINSIC_WO_CHAIN: { @@ -2705,6 +2682,7 @@ const char *SDNode::getOperationName(const SelectionDAG *G) const { case ISD::TargetConstantFP:return "TargetConstantFP"; case ISD::TargetGlobalAddress: return "TargetGlobalAddress"; case ISD::TargetFrameIndex: return "TargetFrameIndex"; + case ISD::TargetJumpTable: return "TargetJumpTable"; case ISD::TargetConstantPool: return "TargetConstantPool"; case ISD::TargetExternalSymbol: return "TargetExternalSymbol"; @@ -2714,6 +2692,8 @@ const char *SDNode::getOperationName(const SelectionDAG *G) const { case ISD::MERGE_VALUES: return "mergevalues"; case ISD::INLINEASM: return "inlineasm"; case ISD::HANDLENODE: return "handlenode"; + case ISD::FORMAL_ARGUMENTS: return "formal_arguments"; + case ISD::CALL: return "call"; // Unary operators case ISD::FABS: return "fabs"; @@ -2721,6 +2701,7 @@ const char *SDNode::getOperationName(const SelectionDAG *G) const { case ISD::FSQRT: return "fsqrt"; case ISD::FSIN: return "fsin"; case ISD::FCOS: return "fcos"; + case ISD::FPOWI: return "fpowi"; // Binary operators case ISD::ADD: return "add"; @@ -2746,10 +2727,6 @@ const char *SDNode::getOperationName(const SelectionDAG *G) const { case ISD::FDIV: return "fdiv"; case ISD::FREM: return "frem"; case ISD::FCOPYSIGN: return "fcopysign"; - case ISD::VADD: return "vadd"; - case ISD::VSUB: return "vsub"; - case ISD::VMUL: return "vmul"; - case ISD::VADD: return "vadd"; case ISD::VSUB: return "vsub"; case ISD::VMUL: return "vmul"; @@ -2762,15 +2739,16 @@ const char *SDNode::getOperationName(const SelectionDAG *G) const { case ISD::SETCC: return "setcc"; case ISD::SELECT: return "select"; case ISD::SELECT_CC: return "select_cc"; - case ISD::INSERT_VECTOR_ELT: return "insert_vector_elt"; - case ISD::VINSERT_VECTOR_ELT: return "vinsert_vector_elt"; - case ISD::EXTRACT_VECTOR_ELT: return "extract_vector_elt"; + case ISD::VSELECT: return "vselect"; + case ISD::INSERT_VECTOR_ELT: return "insert_vector_elt"; + case ISD::VINSERT_VECTOR_ELT: return "vinsert_vector_elt"; + case ISD::EXTRACT_VECTOR_ELT: return "extract_vector_elt"; case ISD::VEXTRACT_VECTOR_ELT: return "vextract_vector_elt"; - case ISD::SCALAR_TO_VECTOR: return "scalar_to_vector"; - case ISD::VBUILD_VECTOR: return "vbuild_vector"; - case ISD::VECTOR_SHUFFLE: return "vector_shuffle"; - case ISD::VVECTOR_SHUFFLE: return "vvector_shuffle"; - case ISD::VBIT_CONVERT: return "vbit_convert"; + case ISD::SCALAR_TO_VECTOR: return "scalar_to_vector"; + case ISD::VBUILD_VECTOR: return "vbuild_vector"; + case ISD::VECTOR_SHUFFLE: return "vector_shuffle"; + case ISD::VVECTOR_SHUFFLE: return "vvector_shuffle"; + case ISD::VBIT_CONVERT: return "vbit_convert"; case ISD::ADDC: return "addc"; case ISD::ADDE: return "adde"; case ISD::SUBC: return "subc"; @@ -2797,6 +2775,8 @@ const char *SDNode::getOperationName(const SelectionDAG *G) const { // Control flow instructions case ISD::BR: return "br"; + case ISD::BRIND: return "brind"; + case ISD::BR_JT: return "br_jt"; case ISD::BRCOND: return "brcond"; case ISD::BR_CC: return "br_cc"; case ISD::RET: return "ret"; @@ -2807,10 +2787,6 @@ const char *SDNode::getOperationName(const SelectionDAG *G) const { case ISD::LOAD: return "load"; case ISD::STORE: return "store"; case ISD::VLOAD: return "vload"; - case ISD::EXTLOAD: return "extload"; - case ISD::SEXTLOAD: return "sextload"; - case ISD::ZEXTLOAD: return "zextload"; - case ISD::TRUNCSTORE: return "truncstore"; case ISD::VAARG: return "vaarg"; case ISD::VACOPY: return "vacopy"; case ISD::VAEND: return "vaend"; @@ -2866,71 +2842,119 @@ const char *SDNode::getOperationName(const SelectionDAG *G) const { } } +const char *SDNode::getIndexedModeName(ISD::MemIndexedMode AM) { + switch (AM) { + default: + return ""; + case ISD::PRE_INC: + return ""; + case ISD::PRE_DEC: + return ""; + case ISD::POST_INC: + return ""; + case ISD::POST_DEC: + return ""; + } +} + void SDNode::dump() const { dump(0); } void SDNode::dump(const SelectionDAG *G) const { - std::cerr << (void*)this << ": "; + cerr << (void*)this << ": "; for (unsigned i = 0, e = getNumValues(); i != e; ++i) { - if (i) std::cerr << ","; + if (i) cerr << ","; if (getValueType(i) == MVT::Other) - std::cerr << "ch"; + cerr << "ch"; else - std::cerr << MVT::getValueTypeString(getValueType(i)); + cerr << MVT::getValueTypeString(getValueType(i)); } - std::cerr << " = " << getOperationName(G); + cerr << " = " << getOperationName(G); - std::cerr << " "; + cerr << " "; for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { - if (i) std::cerr << ", "; - std::cerr << (void*)getOperand(i).Val; + if (i) cerr << ", "; + cerr << (void*)getOperand(i).Val; if (unsigned RN = getOperand(i).ResNo) - std::cerr << ":" << RN; + cerr << ":" << RN; } if (const ConstantSDNode *CSDN = dyn_cast(this)) { - std::cerr << "<" << CSDN->getValue() << ">"; + cerr << "<" << CSDN->getValue() << ">"; } else if (const ConstantFPSDNode *CSDN = dyn_cast(this)) { - std::cerr << "<" << CSDN->getValue() << ">"; + cerr << "<" << CSDN->getValue() << ">"; } else if (const GlobalAddressSDNode *GADN = dyn_cast(this)) { int offset = GADN->getOffset(); - std::cerr << "<"; - WriteAsOperand(std::cerr, GADN->getGlobal()) << ">"; + cerr << "<"; + WriteAsOperand(*cerr.stream(), GADN->getGlobal()) << ">"; if (offset > 0) - std::cerr << " + " << offset; + cerr << " + " << offset; else - std::cerr << " " << offset; + cerr << " " << offset; } else if (const FrameIndexSDNode *FIDN = dyn_cast(this)) { - std::cerr << "<" << FIDN->getIndex() << ">"; + cerr << "<" << FIDN->getIndex() << ">"; + } else if (const JumpTableSDNode *JTDN = dyn_cast(this)) { + cerr << "<" << JTDN->getIndex() << ">"; } else if (const ConstantPoolSDNode *CP = dyn_cast(this)){ int offset = CP->getOffset(); - std::cerr << "<" << *CP->get() << ">"; + if (CP->isMachineConstantPoolEntry()) + cerr << "<" << *CP->getMachineCPVal() << ">"; + else + cerr << "<" << *CP->getConstVal() << ">"; if (offset > 0) - std::cerr << " + " << offset; + cerr << " + " << offset; else - std::cerr << " " << offset; + cerr << " " << offset; } else if (const BasicBlockSDNode *BBDN = dyn_cast(this)) { - std::cerr << "<"; + cerr << "<"; const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock(); if (LBB) - std::cerr << LBB->getName() << " "; - std::cerr << (const void*)BBDN->getBasicBlock() << ">"; + cerr << LBB->getName() << " "; + cerr << (const void*)BBDN->getBasicBlock() << ">"; } else if (const RegisterSDNode *R = dyn_cast(this)) { if (G && R->getReg() && MRegisterInfo::isPhysicalRegister(R->getReg())) { - std::cerr << " " <getTarget().getRegisterInfo()->getName(R->getReg()); + cerr << " " <getTarget().getRegisterInfo()->getName(R->getReg()); } else { - std::cerr << " #" << R->getReg(); + cerr << " #" << R->getReg(); } } else if (const ExternalSymbolSDNode *ES = dyn_cast(this)) { - std::cerr << "'" << ES->getSymbol() << "'"; + cerr << "'" << ES->getSymbol() << "'"; } else if (const SrcValueSDNode *M = dyn_cast(this)) { if (M->getValue()) - std::cerr << "<" << M->getValue() << ":" << M->getOffset() << ">"; + cerr << "<" << M->getValue() << ":" << M->getOffset() << ">"; else - std::cerr << "getOffset() << ">"; + cerr << "getOffset() << ">"; } else if (const VTSDNode *N = dyn_cast(this)) { - std::cerr << ":" << getValueTypeString(N->getVT()); + cerr << ":" << getValueTypeString(N->getVT()); + } else if (const LoadSDNode *LD = dyn_cast(this)) { + bool doExt = true; + switch (LD->getExtensionType()) { + default: doExt = false; break; + case ISD::EXTLOAD: + cerr << " getLoadedVT()) << ">"; + + const char *AM = getIndexedModeName(LD->getAddressingMode()); + if (AM != "") + cerr << " " << AM; + } else if (const StoreSDNode *ST = dyn_cast(this)) { + if (ST->isTruncatingStore()) + cerr << " getStoredVT()) << ">"; + + const char *AM = getIndexedModeName(ST->getAddressingMode()); + if (AM != "") + cerr << " " << AM; } } @@ -2939,16 +2963,16 @@ static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) { if (N->getOperand(i).Val->hasOneUse()) DumpNodes(N->getOperand(i).Val, indent+2, G); else - std::cerr << "\n" << std::string(indent+2, ' ') - << (void*)N->getOperand(i).Val << ": "; + cerr << "\n" << std::string(indent+2, ' ') + << (void*)N->getOperand(i).Val << ": "; - std::cerr << "\n" << std::string(indent, ' '); + cerr << "\n" << std::string(indent, ' '); N->dump(G); } void SelectionDAG::dump() const { - std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:"; + cerr << "SelectionDAG has " << AllNodes.size() << " nodes:"; std::vector Nodes; for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I) @@ -2961,17 +2985,13 @@ void SelectionDAG::dump() const { DumpNodes(Nodes[i], 2, this); } - DumpNodes(getRoot().Val, 2, this); + if (getRoot().Val) DumpNodes(getRoot().Val, 2, this); - std::cerr << "\n\n"; + cerr << "\n\n"; } -/// InsertISelMapEntry - A helper function to insert a key / element pair -/// into a SDOperand to SDOperand map. This is added to avoid the map -/// insertion operator from being inlined. -void SelectionDAG::InsertISelMapEntry(std::map &Map, - SDNode *Key, unsigned KeyResNo, - SDNode *Element, unsigned ElementResNo) { - Map.insert(std::make_pair(SDOperand(Key, KeyResNo), - SDOperand(Element, ElementResNo))); +const Type *ConstantPoolSDNode::getType() const { + if (isMachineConstantPoolEntry()) + return Val.MachineCPVal->getType(); + return Val.ConstVal->getType(); }