X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FSelectionDAG.h;h=d8f8d39e173f372bfd9cdcbbf08c98d2161f73cc;hb=2fabcb27761e0f07368f065fda0144d824e1e51c;hp=49dbd4347a14f0708f98b19d57373df74e67827c;hpb=fed90b6d097d50881afb45e4d79f430db66dd741;p=oota-llvm.git diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h index 49dbd4347a1..d8f8d39e173 100644 --- a/include/llvm/CodeGen/SelectionDAG.h +++ b/include/llvm/CodeGen/SelectionDAG.h @@ -16,12 +16,12 @@ #define LLVM_CODEGEN_SELECTIONDAG_H #include "llvm/ADT/ilist.h" +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/StringMap.h" #include "llvm/CodeGen/SelectionDAGNodes.h" #include -#include #include #include #include @@ -32,18 +32,13 @@ class AliasAnalysis; class TargetLowering; class TargetMachine; class MachineModuleInfo; +class DwarfWriter; class MachineFunction; class MachineConstantPoolValue; class FunctionLoweringInfo; -/// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use -/// pool allocation with recycling. -/// -typedef RecyclingAllocator::Alignment> - NodeAllocatorType; - -template<> class ilist_traits : public ilist_default_traits { +template<> struct ilist_traits : public ilist_default_traits { +private: mutable SDNode Sentinel; public: ilist_traits() : Sentinel(ISD::DELETED_NODE, SDVTList()) {} @@ -60,6 +55,12 @@ private: static void createNode(const SDNode &); }; +enum CombineLevel { + Unrestricted, // Combine may create illegal operations and illegal types. + NoIllegalTypes, // Combine may create illegal operations but no illegal types. + NoIllegalOperations // Combine may only create legal operations and types. +}; + /// SelectionDAG class - This is used to represent a portion of an LLVM function /// in a low-level Data Dependence DAG representation suitable for instruction /// selection. This DAG is constructed as the first step of instruction @@ -73,25 +74,36 @@ private: /// class SelectionDAG { TargetLowering &TLI; - MachineFunction &MF; + MachineFunction *MF; FunctionLoweringInfo &FLI; MachineModuleInfo *MMI; + DwarfWriter *DW; - /// Root - The root of the entire DAG. EntryNode - The starting token. - SDValue Root, EntryNode; + /// EntryNode - The starting token. + SDNode EntryNode; + + /// Root - The root of the entire DAG. + SDValue Root; /// AllNodes - A linked list of nodes in the current DAG. ilist AllNodes; - /// NodeAllocator - Pool allocation for nodes. The allocator isn't - /// allocated inside this class because we want to reuse a single - /// recycler across multiple SelectionDAG runs. - NodeAllocatorType &NodeAllocator; + /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use + /// pool allocation with recycling. + typedef RecyclingAllocator::Alignment> + NodeAllocatorType; + + /// NodeAllocator - Pool allocation for nodes. + NodeAllocatorType NodeAllocator; /// CSEMap - This structure is used to memoize nodes, automatically performing /// CSE with existing nodes with a duplicate is requested. FoldingSet CSEMap; + /// OperandAllocator - Pool allocation for machine-opcode SDNode operands. + BumpPtrAllocator OperandAllocator; + /// Allocator - Pool allocation for misc. objects that are created once per /// SelectionDAG. BumpPtrAllocator Allocator; @@ -99,25 +111,37 @@ class SelectionDAG { /// VerifyNode - Sanity check the given node. Aborts if it is invalid. void VerifyNode(SDNode *N); + /// setGraphColorHelper - Implementation of setSubgraphColor. + /// Return whether we had to truncate the search. + /// + bool setSubgraphColorHelper(SDNode *N, const char *Color, DenseSet &visited, + int level, bool &printed); + public: - SelectionDAG(TargetLowering &tli, MachineFunction &mf, - FunctionLoweringInfo &fli, MachineModuleInfo *mmi, - NodeAllocatorType &nodeallocator) - : TLI(tli), MF(mf), FLI(fli), MMI(mmi), NodeAllocator(nodeallocator) { - EntryNode = Root = getNode(ISD::EntryToken, MVT::Other); - } + SelectionDAG(TargetLowering &tli, FunctionLoweringInfo &fli); ~SelectionDAG(); - MachineFunction &getMachineFunction() const { return MF; } + /// init - Prepare this SelectionDAG to process code in the given + /// MachineFunction. + /// + void init(MachineFunction &mf, MachineModuleInfo *mmi, DwarfWriter *dw); + + /// clear - Clear state and free memory necessary to make this + /// SelectionDAG ready to process a new block. + /// + void clear(); + + MachineFunction &getMachineFunction() const { return *MF; } const TargetMachine &getTarget() const; TargetLowering &getTargetLoweringInfo() const { return TLI; } FunctionLoweringInfo &getFunctionLoweringInfo() const { return FLI; } MachineModuleInfo *getMachineModuleInfo() const { return MMI; } + DwarfWriter *getDwarfWriter() const { return DW; } /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'. /// void viewGraph(const std::string &Title); - void viewGraph() { return viewGraph(""); } + void viewGraph(); #ifndef NDEBUG std::map NodeGraphAttrs; @@ -139,6 +163,10 @@ public: /// void setGraphColor(const SDNode *N, const char *Color); + /// setGraphColor - Convenience for setting subgraph color attribute. + /// + void setSubgraphColor(SDNode *N, const char *Color); + typedef ilist::const_iterator allnodes_const_iterator; allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); } allnodes_const_iterator allnodes_end() const { return AllNodes.end(); } @@ -155,36 +183,39 @@ public: /// getEntryNode - Return the token chain corresponding to the entry of the /// function. - const SDValue &getEntryNode() const { return EntryNode; } + SDValue getEntryNode() const { + return SDValue(const_cast(&EntryNode), 0); + } /// setRoot - Set the current root tag of the SelectionDAG. /// const SDValue &setRoot(SDValue N) { - assert((!N.Val || N.getValueType() == MVT::Other) && + assert((!N.getNode() || N.getValueType() == MVT::Other) && "DAG root value is not a chain!"); return Root = N; } /// Combine - This iterates over the nodes in the SelectionDAG, folding - /// certain types of nodes together, or eliminating superfluous nodes. When - /// the AfterLegalize argument is set to 'true', Combine takes care not to - /// generate any nodes that will be illegal on the target. - void Combine(bool AfterLegalize, AliasAnalysis &AA); - + /// certain types of nodes together, or eliminating superfluous nodes. The + /// Level argument controls whether Combine is allowed to produce nodes and + /// types that are illegal on the target. + void Combine(CombineLevel Level, AliasAnalysis &AA, bool Fast); + /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that - /// only uses types natively supported by the target. + /// only uses types natively supported by the target. Returns "true" if it + /// made any changes. /// /// Note that this is an involved process that may invalidate pointers into /// the graph. - void LegalizeTypes(); - + bool LegalizeTypes(); + /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is /// compatible with the target instruction selector, as indicated by the /// TargetLowering object. /// /// Note that this is an involved process that may invalidate pointers into /// the graph. - void Legalize(); + void Legalize(bool TypesNeedLegalizing); /// RemoveDeadNodes - This method deletes all unreachable nodes in the /// SelectionDAG. @@ -199,6 +230,7 @@ public: SDVTList getVTList(MVT VT); SDVTList getVTList(MVT VT1, MVT VT2); SDVTList getVTList(MVT VT1, MVT VT2, MVT VT3); + SDVTList getVTList(MVT VT1, MVT VT2, MVT VT3, MVT VT4); SDVTList getVTList(const MVT *VTs, unsigned NumVTs); /// getNodeValueTypes - These are obsolete, use getVTList instead. @@ -211,6 +243,9 @@ public: const MVT *getNodeValueTypes(MVT VT1, MVT VT2, MVT VT3) { return getVTList(VT1, VT2, VT3).VTs; } + const MVT *getNodeValueTypes(MVT VT1, MVT VT2, MVT VT3, MVT VT4) { + return getVTList(VT1, VT2, VT3, VT4).VTs; + } const MVT *getNodeValueTypes(const std::vector &vtList) { return getVTList(&vtList[0], (unsigned)vtList.size()).VTs; } @@ -221,6 +256,7 @@ public: // SDValue getConstant(uint64_t Val, MVT VT, bool isTarget = false); SDValue getConstant(const APInt &Val, MVT VT, bool isTarget = false); + SDValue getConstant(const ConstantInt &Val, MVT VT, bool isTarget = false); SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false); SDValue getTargetConstant(uint64_t Val, MVT VT) { return getConstant(Val, VT, true); @@ -228,18 +264,25 @@ public: SDValue getTargetConstant(const APInt &Val, MVT VT) { return getConstant(Val, VT, true); } + SDValue getTargetConstant(const ConstantInt &Val, MVT VT) { + return getConstant(Val, VT, true); + } SDValue getConstantFP(double Val, MVT VT, bool isTarget = false); SDValue getConstantFP(const APFloat& Val, MVT VT, bool isTarget = false); + SDValue getConstantFP(const ConstantFP &CF, MVT VT, bool isTarget = false); SDValue getTargetConstantFP(double Val, MVT VT) { return getConstantFP(Val, VT, true); } SDValue getTargetConstantFP(const APFloat& Val, MVT VT) { return getConstantFP(Val, VT, true); } + SDValue getTargetConstantFP(const ConstantFP &Val, MVT VT) { + return getConstantFP(Val, VT, true); + } SDValue getGlobalAddress(const GlobalValue *GV, MVT VT, - int offset = 0, bool isTargetGA = false); + int64_t offset = 0, bool isTargetGA = false); SDValue getTargetGlobalAddress(const GlobalValue *GV, MVT VT, - int offset = 0) { + int64_t offset = 0) { return getGlobalAddress(GV, VT, offset, true); } SDValue getFrameIndex(int FI, MVT VT, bool isTarget = false); @@ -263,61 +306,76 @@ public: int Offset = 0) { return getConstantPool(C, VT, Align, Offset, true); } + // When generating a branch to a BB, we don't in general know enough + // to provide debug info for the BB at that time, so keep this one around. SDValue getBasicBlock(MachineBasicBlock *MBB); + SDValue getBasicBlock(MachineBasicBlock *MBB, DebugLoc dl); SDValue getExternalSymbol(const char *Sym, MVT VT); + SDValue getExternalSymbol(const char *Sym, DebugLoc dl, MVT VT); SDValue getTargetExternalSymbol(const char *Sym, MVT VT); + SDValue getTargetExternalSymbol(const char *Sym, DebugLoc dl, MVT VT); SDValue getArgFlags(ISD::ArgFlagsTy Flags); SDValue getValueType(MVT); SDValue getRegister(unsigned Reg, MVT VT); SDValue getDbgStopPoint(SDValue Root, unsigned Line, unsigned Col, - const CompileUnitDesc *CU); - SDValue getLabel(unsigned Opcode, SDValue Root, unsigned LabelID); + Value *CU); + SDValue getLabel(unsigned Opcode, DebugLoc dl, SDValue Root, + unsigned LabelID); - SDValue getCopyToReg(SDValue Chain, unsigned Reg, SDValue N) { - return getNode(ISD::CopyToReg, MVT::Other, Chain, + SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) { + return getNode(ISD::CopyToReg, dl, MVT::Other, Chain, getRegister(Reg, N.getValueType()), N); } // This version of the getCopyToReg method takes an extra operand, which // indicates that there is potentially an incoming flag value (if Flag is not // null) and that there should be a flag result. - SDValue getCopyToReg(SDValue Chain, unsigned Reg, SDValue N, + SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N, SDValue Flag) { const MVT *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Flag }; - return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3); + return getNode(ISD::CopyToReg, dl, VTs, 2, Ops, Flag.getNode() ? 4 : 3); } // Similar to last getCopyToReg() except parameter Reg is a SDValue - SDValue getCopyToReg(SDValue Chain, SDValue Reg, SDValue N, + SDValue getCopyToReg(SDValue Chain, DebugLoc dl, SDValue Reg, SDValue N, SDValue Flag) { const MVT *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); SDValue Ops[] = { Chain, Reg, N, Flag }; - return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3); + return getNode(ISD::CopyToReg, dl, VTs, 2, Ops, Flag.getNode() ? 4 : 3); } - SDValue getCopyFromReg(SDValue Chain, unsigned Reg, MVT VT) { + SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, MVT VT) { const MVT *VTs = getNodeValueTypes(VT, MVT::Other); SDValue Ops[] = { Chain, getRegister(Reg, VT) }; - return getNode(ISD::CopyFromReg, VTs, 2, Ops, 2); + return getNode(ISD::CopyFromReg, dl, VTs, 2, Ops, 2); } // This version of the getCopyFromReg method takes an extra operand, which // indicates that there is potentially an incoming flag value (if Flag is not // null) and that there should be a flag result. - SDValue getCopyFromReg(SDValue Chain, unsigned Reg, MVT VT, + SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, MVT VT, SDValue Flag) { const MVT *VTs = getNodeValueTypes(VT, MVT::Other, MVT::Flag); SDValue Ops[] = { Chain, getRegister(Reg, VT), Flag }; - return getNode(ISD::CopyFromReg, VTs, 3, Ops, Flag.Val ? 3 : 2); + return getNode(ISD::CopyFromReg, dl, VTs, 3, Ops, Flag.getNode() ? 3 : 2); } SDValue getCondCode(ISD::CondCode Cond); + /// Returns the ConvertRndSat Note: Avoid using this node because it may + /// disappear in the future and most targets don't support it. + SDValue getConvertRndSat(MVT VT, DebugLoc dl, SDValue Val, SDValue DTy, + SDValue STy, + SDValue Rnd, SDValue Sat, ISD::CvtCode Code); + /// getZeroExtendInReg - Return the expression required to zero extend the Op /// value assuming it was the smaller SrcTy value. - SDValue getZeroExtendInReg(SDValue Op, MVT SrcTy); + SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, MVT SrcTy); + /// getNOT - Create a bitwise NOT operation as (XOR Val, -1). + SDValue getNOT(DebugLoc DL, SDValue Val, MVT VT); + /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have /// a flag result (to ensure it's not CSE'd). SDValue getCALLSEQ_START(SDValue Chain, SDValue Op) { @@ -337,127 +395,161 @@ public: Ops.push_back(Op2); Ops.push_back(InFlag); return getNode(ISD::CALLSEQ_END, NodeTys, &Ops[0], - (unsigned)Ops.size() - (InFlag.Val == 0 ? 1 : 0)); + (unsigned)Ops.size() - (InFlag.getNode() == 0 ? 1 : 0)); } /// getNode - Gets or creates the specified node. /// SDValue getNode(unsigned Opcode, MVT VT); + SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT); SDValue getNode(unsigned Opcode, MVT VT, SDValue N); + SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, SDValue N); SDValue getNode(unsigned Opcode, MVT VT, SDValue N1, SDValue N2); + SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, SDValue N1, SDValue N2); SDValue getNode(unsigned Opcode, MVT VT, - SDValue N1, SDValue N2, SDValue N3); + SDValue N1, SDValue N2, SDValue N3); + SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, + SDValue N1, SDValue N2, SDValue N3); SDValue getNode(unsigned Opcode, MVT VT, - SDValue N1, SDValue N2, SDValue N3, SDValue N4); + SDValue N1, SDValue N2, SDValue N3, SDValue N4); + SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, + SDValue N1, SDValue N2, SDValue N3, SDValue N4); SDValue getNode(unsigned Opcode, MVT VT, - SDValue N1, SDValue N2, SDValue N3, SDValue N4, - SDValue N5); + SDValue N1, SDValue N2, SDValue N3, SDValue N4, + SDValue N5); + SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, + SDValue N1, SDValue N2, SDValue N3, SDValue N4, + SDValue N5); SDValue getNode(unsigned Opcode, MVT VT, - const SDValue *Ops, unsigned NumOps); + const SDUse *Ops, unsigned NumOps); + SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, + const SDUse *Ops, unsigned NumOps); SDValue getNode(unsigned Opcode, MVT VT, - const SDUse *Ops, unsigned NumOps); + const SDValue *Ops, unsigned NumOps); + SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, + const SDValue *Ops, unsigned NumOps); SDValue getNode(unsigned Opcode, const std::vector &ResultTys, - const SDValue *Ops, unsigned NumOps); + const SDValue *Ops, unsigned NumOps); + SDValue getNode(unsigned Opcode, DebugLoc DL, + const std::vector &ResultTys, + const SDValue *Ops, unsigned NumOps); SDValue getNode(unsigned Opcode, const MVT *VTs, unsigned NumVTs, - const SDValue *Ops, unsigned NumOps); + const SDValue *Ops, unsigned NumOps); + SDValue getNode(unsigned Opcode, DebugLoc DL, const MVT *VTs, unsigned NumVTs, + const SDValue *Ops, unsigned NumOps); + SDValue getNode(unsigned Opcode, SDVTList VTs, + const SDValue *Ops, unsigned NumOps); + SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, + const SDValue *Ops, unsigned NumOps); + SDValue getNode(unsigned Opcode, SDVTList VTs); + SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs); SDValue getNode(unsigned Opcode, SDVTList VTs, SDValue N); + SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, SDValue N); SDValue getNode(unsigned Opcode, SDVTList VTs, SDValue N1, SDValue N2); - SDValue getNode(unsigned Opcode, SDVTList VTs, - SDValue N1, SDValue N2, SDValue N3); - SDValue getNode(unsigned Opcode, SDVTList VTs, - SDValue N1, SDValue N2, SDValue N3, SDValue N4); - SDValue getNode(unsigned Opcode, SDVTList VTs, - SDValue N1, SDValue N2, SDValue N3, SDValue N4, - SDValue N5); - SDValue getNode(unsigned Opcode, SDVTList VTs, - const SDValue *Ops, unsigned NumOps); - - SDValue getMemcpy(SDValue Chain, SDValue Dst, SDValue Src, - SDValue Size, unsigned Align, - bool AlwaysInline, - const Value *DstSV, uint64_t DstSVOff, - const Value *SrcSV, uint64_t SrcSVOff); - - SDValue getMemmove(SDValue Chain, SDValue Dst, SDValue Src, - SDValue Size, unsigned Align, - const Value *DstSV, uint64_t DstOSVff, - const Value *SrcSV, uint64_t SrcSVOff); - - SDValue getMemset(SDValue Chain, SDValue Dst, SDValue Src, - SDValue Size, unsigned Align, - const Value *DstSV, uint64_t DstSVOff); + SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, + SDValue N1, SDValue N2); + SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, + SDValue N1, SDValue N2, SDValue N3); + SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, + SDValue N1, SDValue N2, SDValue N3, SDValue N4); + SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, + SDValue N1, SDValue N2, SDValue N3, SDValue N4, + SDValue N5); + + SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, + SDValue Size, unsigned Align, bool AlwaysInline, + const Value *DstSV, uint64_t DstSVOff, + const Value *SrcSV, uint64_t SrcSVOff); + + SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, + SDValue Size, unsigned Align, + const Value *DstSV, uint64_t DstOSVff, + const Value *SrcSV, uint64_t SrcSVOff); + + SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, + SDValue Size, unsigned Align, + const Value *DstSV, uint64_t DstSVOff); /// getSetCC - Helper function to make it easier to build SetCC's if you just /// have an ISD::CondCode instead of an SDValue. /// - SDValue getSetCC(MVT VT, SDValue LHS, SDValue RHS, - ISD::CondCode Cond) { - return getNode(ISD::SETCC, VT, LHS, RHS, getCondCode(Cond)); + SDValue getSetCC(DebugLoc DL, MVT VT, SDValue LHS, SDValue RHS, + ISD::CondCode Cond) { + return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond)); } /// getVSetCC - Helper function to make it easier to build VSetCC's nodes /// if you just have an ISD::CondCode instead of an SDValue. /// - SDValue getVSetCC(MVT VT, SDValue LHS, SDValue RHS, - ISD::CondCode Cond) { - return getNode(ISD::VSETCC, VT, LHS, RHS, getCondCode(Cond)); + SDValue getVSetCC(DebugLoc DL, MVT VT, SDValue LHS, SDValue RHS, + ISD::CondCode Cond) { + return getNode(ISD::VSETCC, DL, VT, LHS, RHS, getCondCode(Cond)); } /// getSelectCC - Helper function to make it easier to build SelectCC's if you /// just have an ISD::CondCode instead of an SDValue. /// - SDValue getSelectCC(SDValue LHS, SDValue RHS, - SDValue True, SDValue False, ISD::CondCode Cond) { - return getNode(ISD::SELECT_CC, True.getValueType(), LHS, RHS, True, False, - getCondCode(Cond)); + SDValue getSelectCC(DebugLoc DL, SDValue LHS, SDValue RHS, + SDValue True, SDValue False, ISD::CondCode Cond) { + return getNode(ISD::SELECT_CC, DL, True.getValueType(), + LHS, RHS, True, False, getCondCode(Cond)); } /// getVAArg - VAArg produces a result and token chain, and takes a pointer /// and a source value as input. - SDValue getVAArg(MVT VT, SDValue Chain, SDValue Ptr, - SDValue SV); + SDValue getVAArg(MVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, + SDValue SV); - /// getAtomic - Gets a node for an atomic op, produces result and chain, takes - /// 3 operands - SDValue getAtomic(unsigned Opcode, SDValue Chain, SDValue Ptr, - SDValue Cmp, SDValue Swp, const Value* PtrVal, - unsigned Alignment=0); + /// getAtomic - Gets a node for an atomic op, produces result and chain and + /// takes 3 operands + SDValue getAtomic(unsigned Opcode, DebugLoc dl, MVT MemVT, SDValue Chain, + SDValue Ptr, SDValue Cmp, SDValue Swp, const Value* PtrVal, + unsigned Alignment=0); - /// getAtomic - Gets a node for an atomic op, produces result and chain, takes - /// 2 operands - SDValue getAtomic(unsigned Opcode, SDValue Chain, SDValue Ptr, - SDValue Val, const Value* PtrVal, - unsigned Alignment = 0); + /// getAtomic - Gets a node for an atomic op, produces result and chain and + /// takes 2 operands. + SDValue getAtomic(unsigned Opcode, DebugLoc dl, MVT MemVT, SDValue Chain, + SDValue Ptr, SDValue Val, const Value* PtrVal, + unsigned Alignment = 0); + + /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a + /// result and takes a list of operands. + SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, + const MVT *VTs, unsigned NumVTs, + const SDValue *Ops, unsigned NumOps, + MVT MemVT, const Value *srcValue, int SVOff, + unsigned Align = 0, bool Vol = false, + bool ReadMem = true, bool WriteMem = true); + + SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList, + const SDValue *Ops, unsigned NumOps, + MVT MemVT, const Value *srcValue, int SVOff, + unsigned Align = 0, bool Vol = false, + bool ReadMem = true, bool WriteMem = true); /// getMergeValues - Create a MERGE_VALUES node from the given operands. - /// Allowed to return something different (and simpler) if Simplify is true. - SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, - bool Simplify = true); + SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, DebugLoc dl); - /// getMergeValues - Create a MERGE_VALUES node from the given types and ops. - /// Allowed to return something different (and simpler) if Simplify is true. - /// May be faster than the above version if VTs is known and NumOps is large. - SDValue getMergeValues(SDVTList VTs, const SDValue *Ops, unsigned NumOps, - bool Simplify = true) { - if (Simplify && NumOps == 1) - return Ops[0]; - return getNode(ISD::MERGE_VALUES, VTs, Ops, NumOps); - } + /// getCall - Create a CALL node from the given information. + /// + SDValue getCall(unsigned CallingConv, DebugLoc dl, bool IsVarArgs, + bool IsTailCall, bool isInreg, SDVTList VTs, + const SDValue *Operands, unsigned NumOperands); /// getLoad - Loads are not normal binary operators: their result type is not /// determined by their operands, and they produce a value AND a token chain. /// - SDValue getLoad(MVT VT, SDValue Chain, SDValue Ptr, + SDValue getLoad(MVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, const Value *SV, int SVOffset, bool isVolatile=false, unsigned Alignment=0); - SDValue getExtLoad(ISD::LoadExtType ExtType, MVT VT, + SDValue getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, MVT VT, SDValue Chain, SDValue Ptr, const Value *SV, int SVOffset, MVT EVT, bool isVolatile=false, unsigned Alignment=0); - SDValue getIndexedLoad(SDValue OrigLoad, SDValue Base, + SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base, SDValue Offset, ISD::MemIndexedMode AM); - SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, + SDValue getLoad(ISD::MemIndexedMode AM, DebugLoc dl, ISD::LoadExtType ExtType, MVT VT, SDValue Chain, SDValue Ptr, SDValue Offset, const Value *SV, int SVOffset, MVT EVT, @@ -465,22 +557,26 @@ public: /// getStore - Helper function to build ISD::STORE nodes. /// - SDValue getStore(SDValue Chain, SDValue Val, SDValue Ptr, + SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, const Value *SV, int SVOffset, bool isVolatile=false, unsigned Alignment=0); - SDValue getTruncStore(SDValue Chain, SDValue Val, SDValue Ptr, + SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, const Value *SV, int SVOffset, MVT TVT, bool isVolatile=false, unsigned Alignment=0); - SDValue getIndexedStore(SDValue OrigStoe, SDValue Base, + SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base, SDValue Offset, ISD::MemIndexedMode AM); - // getSrcValue - Construct a node to track a Value* through the backend. + /// getSrcValue - Construct a node to track a Value* through the backend. SDValue getSrcValue(const Value *v); - // getMemOperand - Construct a node to track a memory reference - // through the backend. + /// getMemOperand - Construct a node to track a memory reference + /// through the backend. SDValue getMemOperand(const MachineMemOperand &MO); + /// getShiftAmountOperand - Return the specified value casted to + /// the target's desired shift amount type. + SDValue getShiftAmountOperand(SDValue Op); + /// 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 @@ -515,12 +611,17 @@ public: MVT VT2, const SDValue *Ops, unsigned NumOps); SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, MVT VT2, MVT VT3, const SDValue *Ops, unsigned NumOps); + SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, MVT VT1, + MVT VT2, MVT VT3, MVT VT4, const SDValue *Ops, + unsigned NumOps); SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, MVT VT2, SDValue Op1); SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, MVT VT2, SDValue Op1, SDValue Op2); SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, MVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); + SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, + MVT VT2, MVT VT3, SDValue Op1, SDValue Op2, SDValue Op3); SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs, const SDValue *Ops, unsigned NumOps); @@ -555,30 +656,72 @@ public: /// node of the specified opcode and operands, it returns that node instead of /// the current one. SDNode *getTargetNode(unsigned Opcode, MVT VT); + SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT); + SDNode *getTargetNode(unsigned Opcode, MVT VT, SDValue Op1); + SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, SDValue Op1); + SDNode *getTargetNode(unsigned Opcode, MVT VT, SDValue Op1, SDValue Op2); + SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, SDValue Op1, + SDValue Op2); + SDNode *getTargetNode(unsigned Opcode, MVT VT, SDValue Op1, SDValue Op2, SDValue Op3); + SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, + SDValue Op1, SDValue Op2, SDValue Op3); + SDNode *getTargetNode(unsigned Opcode, MVT VT, const SDValue *Ops, unsigned NumOps); + SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, + const SDValue *Ops, unsigned NumOps); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2); + SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, SDValue Op1); + SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, + SDValue Op1); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, SDValue Op1, SDValue Op2); + SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, + MVT VT2, SDValue Op1, SDValue Op2); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); + SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, + MVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, const SDValue *Ops, unsigned NumOps); + SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, + const SDValue *Ops, unsigned NumOps); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, SDValue Op1, SDValue Op2); + SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, + SDValue Op1, SDValue Op2); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, SDValue Op1, SDValue Op2, SDValue Op3); + SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, + SDValue Op1, SDValue Op2, SDValue Op3); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, const SDValue *Ops, unsigned NumOps); + SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, + const SDValue *Ops, unsigned NumOps); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, MVT VT4, const SDValue *Ops, unsigned NumOps); + SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, + MVT VT4, const SDValue *Ops, unsigned NumOps); + SDNode *getTargetNode(unsigned Opcode, const std::vector &ResultTys, const SDValue *Ops, unsigned NumOps); + SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, + const std::vector &ResultTys, const SDValue *Ops, + unsigned NumOps); /// getNodeIfExists - Get the specified node if it's already available, or /// else return NULL. @@ -619,6 +762,11 @@ public: /// informed about nodes that are deleted and modified due to recursive /// changes in the dag. /// + /// These functions only replace all existing uses. It's possible that as + /// these replacements are being performed, CSE may cause the From node + /// to be given new uses. These new uses of From are left in place, and + /// not automatically transfered to To. + /// void ReplaceAllUsesWith(SDValue From, SDValue Op, DAGUpdateListener *UpdateListener = 0); void ReplaceAllUsesWith(SDNode *From, SDNode *To, @@ -638,10 +786,17 @@ public: unsigned Num, DAGUpdateListener *UpdateListener = 0); - /// 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 AssignTopologicalOrder(std::vector &TopOrder); + /// AssignTopologicalOrder - Topological-sort the AllNodes list and a + /// assign a unique node id for each node in the DAG based on their + /// topological order. Returns the number of nodes. + unsigned AssignTopologicalOrder(); + + /// RepositionNode - Move node N in the AllNodes list to be immediately + /// before the given iterator Position. This may be used to update the + /// topological ordering when the list of nodes is modified. + void RepositionNode(allnodes_iterator Position, SDNode *N) { + AllNodes.insert(Position, AllNodes.remove(N)); + } /// isCommutativeBinOp - Returns true if the opcode is a commutative binary /// operation. @@ -672,10 +827,20 @@ public: /// specified value type. If minAlign is specified, the slot size will have /// at least that alignment. SDValue CreateStackTemporary(MVT VT, unsigned minAlign = 1); - + + /// CreateStackTemporary - Create a stack temporary suitable for holding + /// either of the specified value types. + SDValue CreateStackTemporary(MVT VT1, MVT VT2); + + /// FoldConstantArithmetic - + SDValue FoldConstantArithmetic(unsigned Opcode, + MVT VT, + ConstantSDNode *Cst1, + ConstantSDNode *Cst2); + /// FoldSetCC - Constant fold a setcc to true or false. SDValue FoldSetCC(MVT VT, SDValue N1, - SDValue N2, ISD::CondCode Cond); + SDValue N2, ISD::CondCode Cond, DebugLoc dl); /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We /// use this predicate to simplify operations downstream. @@ -713,8 +878,8 @@ public: SDValue getShuffleScalarElt(const SDNode *N, unsigned Idx); private: - void RemoveNodeFromCSEMaps(SDNode *N); - SDNode *AddNonLeafNodeToCSEMaps(SDNode *N); + bool RemoveNodeFromCSEMaps(SDNode *N); + void AddModifiedNodeToCSEMaps(SDNode *N, DAGUpdateListener *UpdateListener); SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos); SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2, void *&InsertPos); @@ -722,13 +887,16 @@ private: void *&InsertPos); void DeleteNodeNotInCSEMaps(SDNode *N); + void DeallocateNode(SDNode *N); unsigned getMVTAlignment(MVT MemoryVT) const; + + void allnodes_clear(); - // List of non-single value types. + /// VTList - List of non-single value types. std::vector VTList; - // Maps to auto-CSE operations. + /// CondCodeNodes - Maps to auto-CSE operations. std::vector CondCodeNodes; std::vector ValueTypeNodes;