X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FSelectionDAG.cpp;h=5f92df3f2d54d59baf6b64ab073292a035290961;hb=d97321ceb313f06fd9a824cf26b9dc5b80b3eb9d;hp=895ae47f99bc0676a813fa196c54fdc3a49d928f;hpb=9629abac79fe4efdd000ca1996b2cabd1609190c;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp index 895ae47f99b..5f92df3f2d5 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -26,10 +26,9 @@ #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringExtras.h" -#include #include -#include #include +#include using namespace llvm; /// makeVTList - Return an instance of the SDVTList struct initialized with the @@ -39,15 +38,6 @@ static SDVTList makeVTList(const MVT::ValueType *VTs, unsigned NumVTs) { return Res; } -// 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; -} - //===----------------------------------------------------------------------===// // ConstantFPSDNode Class //===----------------------------------------------------------------------===// @@ -251,6 +241,175 @@ 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 //===----------------------------------------------------------------------===// @@ -300,6 +459,39 @@ void SelectionDAG::RemoveDeadNodes() { setRoot(Dummy.getValue()); } +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(); + + // 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. + Deleted.push_back(N); + AllNodes.erase(N); + } +} + void SelectionDAG::DeleteNode(SDNode *N) { assert(N->use_empty() && "Cannot delete a node that is not dead!"); @@ -366,7 +558,7 @@ void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag && !N->isTargetOpcode()) { N->dump(); - std::cerr << "\n"; + cerr << "\n"; assert(0 && "Node is not in map!"); } #endif @@ -406,10 +598,8 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op, if (N->getValueType(i) == MVT::Flag) return 0; // Never CSE anything that produces a flag. - SelectionDAGCSEMap::NodeID ID; - ID.SetOpcode(N->getOpcode()); - ID.SetValueTypes(N->getVTList()); - ID.SetOperands(Op); + FoldingSetNodeID ID; + AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Op); return CSEMap.FindNodeOrInsertPos(ID, InsertPos); } @@ -428,10 +618,8 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, if (N->getValueType(i) == MVT::Flag) return 0; // Never CSE anything that produces a flag. - SelectionDAGCSEMap::NodeID ID; - ID.SetOpcode(N->getOpcode()); - ID.SetValueTypes(N->getVTList()); - ID.SetOperands(Op1, Op2); + FoldingSetNodeID ID; + AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Op1, Op2); return CSEMap.FindNodeOrInsertPos(ID, InsertPos); } @@ -451,19 +639,28 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, if (N->getValueType(i) == MVT::Flag) return 0; // Never CSE anything that produces a flag. - SelectionDAGCSEMap::NodeID ID; - ID.SetOpcode(N->getOpcode()); - ID.SetValueTypes(N->getVTList()); + 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->getLoadVT()); + 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()); } - ID.SetOperands(Ops, NumOps); + + AddNodeIDOperands(ID, Ops, NumOps); return CSEMap.FindNodeOrInsertPos(ID, InsertPos); } @@ -503,7 +700,8 @@ SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT, bool isT) { Val &= MVT::getIntVTBitMask(VT); unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant; - SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT)); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opc, getVTList(VT)); ID.AddInteger(Val); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) @@ -525,8 +723,9 @@ SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT, // value, so that we don't have problems with 0.0 comparing equal to -0.0, and // we don't have issues with SNANs. unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP; - SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT)); - ID.AddInteger(DoubleToBits(Val)); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opc, getVTList(VT)); + ID.AddDouble(Val); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDOperand(E, 0); @@ -540,7 +739,8 @@ SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT, int Offset, bool isTargetGA) { unsigned Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress; - SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT)); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opc, getVTList(VT)); ID.AddPointer(GV); ID.AddInteger(Offset); void *IP = 0; @@ -555,7 +755,8 @@ SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT, bool isTarget) { unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex; - SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT)); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opc, getVTList(VT)); ID.AddInteger(FI); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) @@ -568,7 +769,8 @@ SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT, SDOperand SelectionDAG::getJumpTable(int JTI, MVT::ValueType VT, bool isTarget){ unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable; - SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT)); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opc, getVTList(VT)); ID.AddInteger(JTI); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) @@ -583,7 +785,8 @@ SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT, unsigned Alignment, int Offset, bool isTarget) { unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; - SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT)); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opc, getVTList(VT)); ID.AddInteger(Alignment); ID.AddInteger(Offset); ID.AddPointer(C); @@ -602,10 +805,11 @@ SDOperand SelectionDAG::getConstantPool(MachineConstantPoolValue *C, unsigned Alignment, int Offset, bool isTarget) { unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; - SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT)); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opc, getVTList(VT)); ID.AddInteger(Alignment); ID.AddInteger(Offset); - C->AddSelectionDAGCSEId(&ID); + C->AddSelectionDAGCSEId(ID); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDOperand(E, 0); @@ -617,7 +821,8 @@ SDOperand SelectionDAG::getConstantPool(MachineConstantPoolValue *C, SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { - SelectionDAGCSEMap::NodeID ID(ISD::BasicBlock, getVTList(MVT::Other)); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other)); ID.AddPointer(MBB); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) @@ -668,7 +873,8 @@ SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) { } SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) { - SelectionDAGCSEMap::NodeID ID(ISD::Register, getVTList(VT)); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::Register, getVTList(VT)); ID.AddInteger(RegNo); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) @@ -683,7 +889,8 @@ SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) { assert((!V || isa(V->getType())) && "SrcValue is not a pointer?"); - SelectionDAGCSEMap::NodeID ID(ISD::SRCVALUE, getVTList(MVT::Other)); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other)); ID.AddPointer(V); ID.AddInteger(Offset); void *IP = 0; @@ -695,8 +902,8 @@ SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) { 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; @@ -718,18 +925,18 @@ SDOperand SelectionDAG::SimplifySetCC(MVT::ValueType VT, SDOperand N1, 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); @@ -743,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); @@ -906,15 +969,17 @@ 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) { - SelectionDAGCSEMap::NodeID ID(Opcode, getVTList(VT)); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opcode, getVTList(VT)); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDOperand(E, 0); @@ -1065,7 +1130,7 @@ 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)); @@ -1093,7 +1158,8 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, SDNode *N; SDVTList VTs = getVTList(VT); if (VT != MVT::Flag) { // Don't CSE flag producing nodes - SelectionDAGCSEMap::NodeID ID(Opcode, VTs, Operand); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opcode, VTs, Operand); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDOperand(E, 0); @@ -1328,8 +1394,21 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, } } - // 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; @@ -1380,7 +1459,8 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, SDNode *N; SDVTList VTs = getVTList(VT); if (VT != MVT::Flag) { - SelectionDAGCSEMap::NodeID ID(Opcode, VTs, N1, N2); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opcode, VTs, N1, N2); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDOperand(E, 0); @@ -1401,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; } @@ -1438,7 +1517,8 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, SDNode *N; SDVTList VTs = getVTList(VT); if (VT != MVT::Flag) { - SelectionDAGCSEMap::NodeID ID(Opcode, VTs, 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); @@ -1474,8 +1554,9 @@ SDOperand SelectionDAG::getLoad(MVT::ValueType VT, // FIXME: Alignment == 1 for now. unsigned Alignment = 1; SDVTList VTs = getVTList(VT, MVT::Other); - SDOperand Undef = getNode(ISD::UNDEF, VT); - SelectionDAGCSEMap::NodeID ID(ISD::LOAD, VTs, Chain, Ptr, Undef); + 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); @@ -1486,8 +1567,9 @@ SDOperand SelectionDAG::getLoad(MVT::ValueType VT, void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDOperand(E, 0); - SDNode *N = new LoadSDNode(Chain, Ptr, Undef, ISD::NON_EXTLOAD, VT, - SV, SVOffset, Alignment, isVolatile); + 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); @@ -1515,8 +1597,9 @@ SDOperand SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, MVT::ValueType VT, // FIXME: Alignment == 1 for now. unsigned Alignment = 1; SDVTList VTs = getVTList(VT, MVT::Other); - SDOperand Undef = getNode(ISD::UNDEF, VT); - SelectionDAGCSEMap::NodeID ID(ISD::LOAD, VTs, Chain, Ptr, Undef); + 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); @@ -1527,8 +1610,38 @@ SDOperand SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, MVT::ValueType VT, void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDOperand(E, 0); - SDNode *N = new LoadSDNode(Chain, Ptr, Undef, ExtType, EVT, SV, SVOffset, - Alignment, isVolatile); + 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); @@ -1543,15 +1656,97 @@ SDOperand SelectionDAG::getVecLoad(unsigned Count, MVT::ValueType EVT, return getNode(ISD::VLOAD, getVTList(MVT::Vector, MVT::Other), Ops, 5); } -SDOperand SelectionDAG::getStore(SDOperand Chain, SDOperand Value, - SDOperand Ptr, SDOperand SV) { +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::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 Ops[] = { Chain, Value, Ptr, SV }; - SelectionDAGCSEMap::NodeID ID(ISD::STORE, VTs, Ops, 4); + 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 SDNode(ISD::STORE, Chain, Value, Ptr, SV); + 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); +} + +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); @@ -1577,26 +1772,6 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, switch (Opcode) { default: break; - case ISD::TRUNCSTORE: { - assert(NumOps == 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 getStore(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(NumOps == 5 && "SELECT_CC takes 5 operands!"); assert(Ops[0].getValueType() == Ops[1].getValueType() && @@ -1619,7 +1794,8 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, SDNode *N; SDVTList VTs = getVTList(VT); if (VT != MVT::Flag) { - SelectionDAGCSEMap::NodeID ID(Opcode, VTs, Ops, NumOps); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDOperand(E, 0); @@ -1680,10 +1856,8 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, // Memoize the node unless it returns a flag. SDNode *N; if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) { - SelectionDAGCSEMap::NodeID ID; - ID.SetOpcode(Opcode); - ID.SetValueTypes(VTList); - ID.SetOperands(&Ops[0], NumOps); + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDOperand(E, 0); @@ -1797,7 +1971,6 @@ 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. @@ -1903,7 +2076,8 @@ UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) { SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT) { SDVTList VTs = getVTList(VT); - SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs); void *IP = 0; if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) return ON; @@ -1921,7 +2095,8 @@ SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, SDOperand Op1) { // If an identical node already exists, use it. SDVTList VTs = getVTList(VT); - SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1); void *IP = 0; if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) return ON; @@ -1939,7 +2114,8 @@ SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, SDOperand Op2) { // If an identical node already exists, use it. SDVTList VTs = getVTList(VT); - SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2); void *IP = 0; if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) return ON; @@ -1958,8 +2134,8 @@ SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, SDOperand Op2, SDOperand Op3) { // If an identical node already exists, use it. SDVTList VTs = getVTList(VT); - SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, - Op1, Op2, Op3); + 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; @@ -1978,9 +2154,8 @@ SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, unsigned NumOps) { // If an identical node already exists, use it. SDVTList VTs = getVTList(VT); - SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs); - for (unsigned i = 0; i != NumOps; ++i) - ID.AddOperand(Ops[i]); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps); void *IP = 0; if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) return ON; @@ -1998,7 +2173,8 @@ SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, MVT::ValueType VT2, SDOperand Op1, SDOperand Op2) { SDVTList VTs = getVTList(VT1, VT2); - SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2); + FoldingSetNodeID ID; + AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2); void *IP = 0; if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) return ON; @@ -2018,8 +2194,8 @@ SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, SDOperand Op3) { // If an identical node already exists, use it. SDVTList VTs = getVTList(VT1, VT2); - SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, - Op1, Op2, Op3); + 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; @@ -2342,6 +2518,12 @@ unsigned SelectionDAG::AssignTopologicalOrder(std::vector &TopOrder) { 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. /// MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) { @@ -2382,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) { @@ -2396,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)) @@ -2411,6 +2595,32 @@ 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(); @@ -2454,7 +2664,7 @@ const char *SDNode::getOperationName(const SelectionDAG *G) const { case ISD::GlobalAddress: return "GlobalAddress"; case ISD::FrameIndex: return "FrameIndex"; case ISD::JumpTable: return "JumpTable"; - case ISD::JumpTableRelocBase: return "JumpTableRelocBase"; + case ISD::GLOBAL_OFFSET_TABLE: return "GLOBAL_OFFSET_TABLE"; case ISD::ConstantPool: return "ConstantPool"; case ISD::ExternalSymbol: return "ExternalSymbol"; case ISD::INTRINSIC_WO_CHAIN: { @@ -2566,6 +2776,7 @@ 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"; @@ -2576,7 +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::TRUNCSTORE: return "truncstore"; case ISD::VAARG: return "vaarg"; case ISD::VACOPY: return "vacopy"; case ISD::VAEND: return "vaend"; @@ -2632,95 +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(); if (CP->isMachineConstantPoolEntry()) - std::cerr << "<" << *CP->getMachineCPVal() << ">"; + cerr << "<" << *CP->getMachineCPVal() << ">"; else - std::cerr << "<" << *CP->getConstVal() << ">"; + 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: - std::cerr << " getLoadVT()) << ">"; - - if (LD->getAddressingMode() == ISD::PRE_INDEXED) - std::cerr << " 
";
-    else if (LD->getAddressingMode() == ISD::POST_INDEXED)
-      std::cerr << " ";
+      cerr << MVT::getValueTypeString(LD->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;
   }
 }
 
@@ -2729,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)
@@ -2751,9 +2985,9 @@ 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";
 }
 
 const Type *ConstantPoolSDNode::getType() const {