X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FSelectionDAG.h;h=01f56a9e866529a994dbeeac2f96c0afc4592284;hb=4b84086e89d86fb16f562166d9fea8df37db6be7;hp=6d75e47acfb6d67624e839d15d2680f6d5d3ec85;hpb=b8973bd8f50d7321635e1e07b81a880a0828d185;p=oota-llvm.git diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h index 6d75e47acfb..bd9a8957fde 100644 --- a/include/llvm/CodeGen/SelectionDAG.h +++ b/include/llvm/CodeGen/SelectionDAG.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -15,18 +15,24 @@ #ifndef LLVM_CODEGEN_SELECTIONDAG_H #define LLVM_CODEGEN_SELECTIONDAG_H +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/ADT/ilist.h" #include "llvm/CodeGen/SelectionDAGNodes.h" -#include "llvm/ADT/ilist" -#include #include +#include +#include #include namespace llvm { + class AliasAnalysis; class TargetLowering; class TargetMachine; - class MachineDebugInfo; + class MachineModuleInfo; class MachineFunction; + class MachineConstantPoolValue; + class FunctionLoweringInfo; /// SelectionDAG class - This is used to represent a portion of an LLVM function /// in a low-level Data Dependence DAG representation suitable for instruction @@ -42,20 +48,23 @@ namespace llvm { class SelectionDAG { TargetLowering &TLI; MachineFunction &MF; - MachineDebugInfo *DI; + FunctionLoweringInfo &FLI; + MachineModuleInfo *MMI; - // Root - The root of the entire DAG. EntryNode - The starting token. + /// Root - The root of the entire DAG. EntryNode - The starting token. SDOperand Root, EntryNode; - // AllNodes - A linked list of nodes in the current DAG. + /// AllNodes - A linked list of nodes in the current DAG. ilist AllNodes; - // ValueNodes - track SrcValue nodes - std::map, SDNode*> ValueNodes; + /// CSEMap - This structure is used to memoize nodes, automatically performing + /// CSE with existing nodes with a duplicate is requested. + FoldingSet CSEMap; public: - SelectionDAG(TargetLowering &tli, MachineFunction &mf, MachineDebugInfo *di) - : TLI(tli), MF(mf), DI(di) { + SelectionDAG(TargetLowering &tli, MachineFunction &mf, + FunctionLoweringInfo &fli, MachineModuleInfo *mmi) + : TLI(tli), MF(mf), FLI(fli), MMI(mmi) { EntryNode = Root = getNode(ISD::EntryToken, MVT::Other); } ~SelectionDAG(); @@ -63,12 +72,32 @@ public: MachineFunction &getMachineFunction() const { return MF; } const TargetMachine &getTarget() const; TargetLowering &getTargetLoweringInfo() const { return TLI; } - MachineDebugInfo *getMachineDebugInfo() const { return DI; } + FunctionLoweringInfo &getFunctionLoweringInfo() const { return FLI; } + MachineModuleInfo *getMachineModuleInfo() const { return MMI; } - /// viewGraph - Pop up a ghostview window with the DAG rendered using 'dot'. + /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'. /// void viewGraph(); + +#ifndef NDEBUG + std::map NodeGraphAttrs; +#endif + /// clearGraphAttrs - Clear all previously defined node graph attributes. + /// Intended to be used from a debugging tool (eg. gdb). + void clearGraphAttrs(); + + /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".) + /// + void setGraphAttrs(const SDNode *N, const char *Attrs); + + /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".) + /// Used from getNodeAttributes. + const std::string getGraphAttrs(const SDNode *N) const; + + /// setGraphColor - Convenience for setting node color attribute. + /// + void setGraphColor(const SDNode *N, const char *Color); typedef ilist::const_iterator allnodes_const_iterator; allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); } @@ -76,6 +105,7 @@ public: typedef ilist::iterator allnodes_iterator; allnodes_iterator allnodes_begin() { return AllNodes.begin(); } allnodes_iterator allnodes_end() { return AllNodes.end(); } + ilist::size_type allnodes_size() const { return AllNodes.size(); } /// getRoot - Return the root tag of the SelectionDAG. /// @@ -93,7 +123,14 @@ public: /// 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); + void Combine(bool AfterLegalize, AliasAnalysis &AA); + + /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that + /// only uses types natively supported by the target. + /// + /// Note that this is an involved process that may invalidate pointers into + /// the graph. + void LegalizeTypes(); /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is /// compatible with the target instruction selector, as indicated by the @@ -104,31 +141,89 @@ public: void Legalize(); /// 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 RemoveDeadNodes(SDNode *N = 0); + /// SelectionDAG. + void RemoveDeadNodes(); + /// DeleteNode - Remove the specified node from the system. This node must + /// have no referrers. + void DeleteNode(SDNode *N); + + /// getVTList - Return an SDVTList that represents the list of values + /// specified. + SDVTList getVTList(MVT VT); + SDVTList getVTList(MVT VT1, MVT VT2); + SDVTList getVTList(MVT VT1, MVT VT2, MVT VT3); + SDVTList getVTList(const MVT *VTs, unsigned NumVTs); + + /// getNodeValueTypes - These are obsolete, use getVTList instead. + const MVT *getNodeValueTypes(MVT VT) { + return getVTList(VT).VTs; + } + const MVT *getNodeValueTypes(MVT VT1, MVT VT2) { + return getVTList(VT1, VT2).VTs; + } + const MVT *getNodeValueTypes(MVT VT1, MVT VT2, MVT VT3) { + return getVTList(VT1, VT2, VT3).VTs; + } + const MVT *getNodeValueTypes(std::vector &vtList) { + return getVTList(&vtList[0], (unsigned)vtList.size()).VTs; + } + + + //===--------------------------------------------------------------------===// + // Node creation methods. + // SDOperand getString(const std::string &Val); - SDOperand getConstant(uint64_t Val, MVT::ValueType VT); - SDOperand getTargetConstant(uint64_t Val, MVT::ValueType VT); - SDOperand getConstantFP(double Val, MVT::ValueType VT); - SDOperand getTargetConstantFP(double Val, MVT::ValueType VT); - SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT, - int offset = 0); - SDOperand getTargetGlobalAddress(const GlobalValue *GV, MVT::ValueType VT, - int offset = 0); - SDOperand getFrameIndex(int FI, MVT::ValueType VT); - SDOperand getTargetFrameIndex(int FI, MVT::ValueType VT); - SDOperand getConstantPool(Constant *C, MVT::ValueType VT, - unsigned Alignment=0); - SDOperand getTargetConstantPool(Constant *C, MVT::ValueType VT, - unsigned Alignment=0); + SDOperand getConstant(uint64_t Val, MVT VT, bool isTarget = false); + SDOperand getConstant(const APInt &Val, MVT VT, bool isTarget = false); + SDOperand getIntPtrConstant(uint64_t Val, bool isTarget = false); + SDOperand getTargetConstant(uint64_t Val, MVT VT) { + return getConstant(Val, VT, true); + } + SDOperand getTargetConstant(const APInt &Val, MVT VT) { + return getConstant(Val, VT, true); + } + SDOperand getConstantFP(double Val, MVT VT, bool isTarget = false); + SDOperand getConstantFP(const APFloat& Val, MVT VT, bool isTarget = false); + SDOperand getTargetConstantFP(double Val, MVT VT) { + return getConstantFP(Val, VT, true); + } + SDOperand getTargetConstantFP(const APFloat& Val, MVT VT) { + return getConstantFP(Val, VT, true); + } + SDOperand getGlobalAddress(const GlobalValue *GV, MVT VT, + int offset = 0, bool isTargetGA = false); + SDOperand getTargetGlobalAddress(const GlobalValue *GV, MVT VT, + int offset = 0) { + return getGlobalAddress(GV, VT, offset, true); + } + SDOperand getFrameIndex(int FI, MVT VT, bool isTarget = false); + SDOperand getTargetFrameIndex(int FI, MVT VT) { + return getFrameIndex(FI, VT, true); + } + SDOperand getJumpTable(int JTI, MVT VT, bool isTarget = false); + SDOperand getTargetJumpTable(int JTI, MVT VT) { + return getJumpTable(JTI, VT, true); + } + SDOperand getConstantPool(Constant *C, MVT VT, + unsigned Align = 0, int Offs = 0, bool isT=false); + SDOperand getTargetConstantPool(Constant *C, MVT VT, + unsigned Align = 0, int Offset = 0) { + return getConstantPool(C, VT, Align, Offset, true); + } + SDOperand getConstantPool(MachineConstantPoolValue *C, MVT VT, + unsigned Align = 0, int Offs = 0, bool isT=false); + SDOperand getTargetConstantPool(MachineConstantPoolValue *C, + MVT VT, unsigned Align = 0, + int Offset = 0) { + return getConstantPool(C, VT, Align, Offset, true); + } SDOperand getBasicBlock(MachineBasicBlock *MBB); - SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT); - SDOperand getTargetExternalSymbol(const char *Sym, MVT::ValueType VT); - SDOperand getValueType(MVT::ValueType); - SDOperand getRegister(unsigned Reg, MVT::ValueType VT); + SDOperand getExternalSymbol(const char *Sym, MVT VT); + SDOperand getTargetExternalSymbol(const char *Sym, MVT VT); + SDOperand getArgFlags(ISD::ArgFlagsTy Flags); + SDOperand getValueType(MVT); + SDOperand getRegister(unsigned Reg, MVT VT); SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N) { return getNode(ISD::CopyToReg, MVT::Other, Chain, @@ -140,115 +235,183 @@ public: // null) and that there should be a flag result. SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N, SDOperand Flag) { - std::vector VTs; - VTs.push_back(MVT::Other); - VTs.push_back(MVT::Flag); - std::vector Ops; - Ops.push_back(Chain); - Ops.push_back(getRegister(Reg, N.getValueType())); - Ops.push_back(N); - if (Flag.Val) Ops.push_back(Flag); - return getNode(ISD::CopyToReg, VTs, Ops); + const MVT *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); + SDOperand Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Flag }; + return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3); } // Similar to last getCopyToReg() except parameter Reg is a SDOperand SDOperand getCopyToReg(SDOperand Chain, SDOperand Reg, SDOperand N, SDOperand Flag) { - std::vector VTs; - VTs.push_back(MVT::Other); - VTs.push_back(MVT::Flag); - std::vector Ops; - Ops.push_back(Chain); - Ops.push_back(Reg); - Ops.push_back(N); - if (Flag.Val) Ops.push_back(Flag); - return getNode(ISD::CopyToReg, VTs, Ops); + const MVT *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); + SDOperand Ops[] = { Chain, Reg, N, Flag }; + return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3); } - SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT) { - std::vector ResultTys; - ResultTys.push_back(VT); - ResultTys.push_back(MVT::Other); - std::vector Ops; - Ops.push_back(Chain); - Ops.push_back(getRegister(Reg, VT)); - return getNode(ISD::CopyFromReg, ResultTys, Ops); + SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT VT) { + const MVT *VTs = getNodeValueTypes(VT, MVT::Other); + SDOperand Ops[] = { Chain, getRegister(Reg, VT) }; + return getNode(ISD::CopyFromReg, 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. - SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT, + SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT VT, SDOperand Flag) { - std::vector ResultTys; - ResultTys.push_back(VT); - ResultTys.push_back(MVT::Other); - ResultTys.push_back(MVT::Flag); - std::vector Ops; - Ops.push_back(Chain); - Ops.push_back(getRegister(Reg, VT)); - if (Flag.Val) Ops.push_back(Flag); - return getNode(ISD::CopyFromReg, ResultTys, Ops); + const MVT *VTs = getNodeValueTypes(VT, MVT::Other, MVT::Flag); + SDOperand Ops[] = { Chain, getRegister(Reg, VT), Flag }; + return getNode(ISD::CopyFromReg, VTs, 3, Ops, Flag.Val ? 3 : 2); } SDOperand getCondCode(ISD::CondCode Cond); /// getZeroExtendInReg - Return the expression required to zero extend the Op /// value assuming it was the smaller SrcTy value. - SDOperand getZeroExtendInReg(SDOperand Op, MVT::ValueType SrcTy); + SDOperand getZeroExtendInReg(SDOperand Op, MVT SrcTy); + + /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have + /// a flag result (to ensure it's not CSE'd). + SDOperand getCALLSEQ_START(SDOperand Chain, SDOperand Op) { + const MVT *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); + SDOperand Ops[] = { Chain, Op }; + return getNode(ISD::CALLSEQ_START, VTs, 2, Ops, 2); + } + + /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a + /// flag result (to ensure it's not CSE'd). + SDOperand getCALLSEQ_END(SDOperand Chain, SDOperand Op1, SDOperand Op2, + SDOperand InFlag) { + SDVTList NodeTys = getVTList(MVT::Other, MVT::Flag); + SmallVector Ops; + Ops.push_back(Chain); + Ops.push_back(Op1); + Ops.push_back(Op2); + Ops.push_back(InFlag); + return getNode(ISD::CALLSEQ_END, NodeTys, &Ops[0], + (unsigned)Ops.size() - (InFlag.Val == 0 ? 1 : 0)); + } /// getNode - Gets or creates the specified node. /// - SDOperand getNode(unsigned Opcode, MVT::ValueType VT); - SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N); - SDOperand getNode(unsigned Opcode, MVT::ValueType VT, - SDOperand N1, SDOperand N2); - SDOperand getNode(unsigned Opcode, MVT::ValueType VT, + SDOperand getNode(unsigned Opcode, MVT VT); + SDOperand getNode(unsigned Opcode, MVT VT, SDOperand N); + SDOperand getNode(unsigned Opcode, MVT VT, SDOperand N1, SDOperand N2); + SDOperand getNode(unsigned Opcode, MVT VT, + SDOperand N1, SDOperand N2, SDOperand N3); + SDOperand getNode(unsigned Opcode, MVT VT, + SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4); + SDOperand getNode(unsigned Opcode, MVT VT, + SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4, + SDOperand N5); + SDOperand getNode(unsigned Opcode, MVT VT, SDOperandPtr Ops, unsigned NumOps); + SDOperand getNode(unsigned Opcode, std::vector &ResultTys, + SDOperandPtr Ops, unsigned NumOps); + SDOperand getNode(unsigned Opcode, const MVT *VTs, unsigned NumVTs, + SDOperandPtr Ops, unsigned NumOps); + SDOperand getNode(unsigned Opcode, SDVTList VTs); + SDOperand getNode(unsigned Opcode, SDVTList VTs, SDOperand N); + SDOperand getNode(unsigned Opcode, SDVTList VTs, SDOperand N1, SDOperand N2); + SDOperand getNode(unsigned Opcode, SDVTList VTs, SDOperand N1, SDOperand N2, SDOperand N3); - SDOperand getNode(unsigned Opcode, MVT::ValueType VT, + SDOperand getNode(unsigned Opcode, SDVTList VTs, SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4); - SDOperand getNode(unsigned Opcode, MVT::ValueType VT, + SDOperand getNode(unsigned Opcode, SDVTList VTs, SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4, SDOperand N5); - SDOperand getNode(unsigned Opcode, MVT::ValueType VT, - std::vector &Children); - SDOperand getNode(unsigned Opcode, std::vector &ResultTys, - std::vector &Ops); + SDOperand getNode(unsigned Opcode, SDVTList VTs, + SDOperandPtr Ops, unsigned NumOps); + + SDOperand getMemcpy(SDOperand Chain, SDOperand Dst, SDOperand Src, + SDOperand Size, unsigned Align, + bool AlwaysInline, + const Value *DstSV, uint64_t DstSVOff, + const Value *SrcSV, uint64_t SrcSVOff); + + SDOperand getMemmove(SDOperand Chain, SDOperand Dst, SDOperand Src, + SDOperand Size, unsigned Align, + const Value *DstSV, uint64_t DstOSVff, + const Value *SrcSV, uint64_t SrcSVOff); + + SDOperand getMemset(SDOperand Chain, SDOperand Dst, SDOperand Src, + SDOperand 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 SDOperand. /// - SDOperand getSetCC(MVT::ValueType VT, SDOperand LHS, SDOperand RHS, + SDOperand getSetCC(MVT VT, SDOperand LHS, SDOperand RHS, ISD::CondCode Cond) { return getNode(ISD::SETCC, 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 SDOperand. + /// + SDOperand getVSetCC(MVT VT, SDOperand LHS, SDOperand RHS, + ISD::CondCode Cond) { + return getNode(ISD::VSETCC, 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 SDOperand. /// SDOperand getSelectCC(SDOperand LHS, SDOperand RHS, SDOperand True, SDOperand False, ISD::CondCode Cond) { - MVT::ValueType VT = True.getValueType(); - return getNode(ISD::SELECT_CC, VT, LHS, RHS, True, False,getCondCode(Cond)); + return getNode(ISD::SELECT_CC, 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. - SDOperand getVAArg(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, + SDOperand getVAArg(MVT VT, SDOperand Chain, SDOperand Ptr, SDOperand SV); + /// getAtomic - Gets a node for an atomic op, produces result and chain, takes + // 3 operands + SDOperand getAtomic(unsigned Opcode, SDOperand Chain, SDOperand Ptr, + SDOperand Cmp, SDOperand Swp, MVT VT); + + /// getAtomic - Gets a node for an atomic op, produces result and chain, takes + // 2 operands + SDOperand getAtomic(unsigned Opcode, SDOperand Chain, SDOperand Ptr, + SDOperand Val, MVT VT); + /// 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. /// - SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, - SDOperand SV); - SDOperand getVecLoad(unsigned Count, MVT::ValueType VT, SDOperand Chain, - SDOperand Ptr, SDOperand SV); - SDOperand getExtLoad(unsigned Opcode, MVT::ValueType VT, SDOperand Chain, - SDOperand Ptr, SDOperand SV, MVT::ValueType EVT); - - // getSrcValue - construct a node to track a Value* through the backend - SDOperand getSrcValue(const Value* I, int offset = 0); + SDOperand getLoad(MVT VT, SDOperand Chain, SDOperand Ptr, + const Value *SV, int SVOffset, bool isVolatile=false, + unsigned Alignment=0); + SDOperand getExtLoad(ISD::LoadExtType ExtType, MVT VT, + SDOperand Chain, SDOperand Ptr, const Value *SV, + int SVOffset, MVT EVT, bool isVolatile=false, + unsigned Alignment=0); + SDOperand getIndexedLoad(SDOperand OrigLoad, SDOperand Base, + SDOperand Offset, ISD::MemIndexedMode AM); + SDOperand getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, + MVT VT, SDOperand Chain, + SDOperand Ptr, SDOperand Offset, + const Value *SV, int SVOffset, MVT EVT, + bool isVolatile=false, unsigned Alignment=0); + + /// getStore - Helper function to build ISD::STORE nodes. + /// + SDOperand getStore(SDOperand Chain, SDOperand Val, SDOperand Ptr, + const Value *SV, int SVOffset, bool isVolatile=false, + unsigned Alignment=0); + SDOperand getTruncStore(SDOperand Chain, SDOperand Val, SDOperand Ptr, + const Value *SV, int SVOffset, MVT TVT, + bool isVolatile=false, unsigned Alignment=0); + SDOperand getIndexedStore(SDOperand OrigStoe, SDOperand Base, + SDOperand Offset, ISD::MemIndexedMode AM); + + // getSrcValue - Construct a node to track a Value* through the backend. + SDOperand getSrcValue(const Value *v); + + // getMemOperand - Construct a node to track a memory reference + // through the backend. + SDOperand getMemOperand(const MachineMemOperand &MO); /// UpdateNodeOperands - *Mutate* the specified node in-place to have the /// specified operands. If the resultant node already exists in the DAG, @@ -264,364 +427,204 @@ public: SDOperand Op3, SDOperand Op4); SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3, SDOperand Op4, SDOperand Op5); - SDOperand UpdateNodeOperands(SDOperand N, const std::vector &Op); + SDOperand UpdateNodeOperands(SDOperand N, SDOperandPtr Ops, unsigned NumOps); /// SelectNodeTo - These are used for target selectors to *mutate* the /// specified node to have the specified return type, Target opcode, and /// operands. Note that target opcodes are stored as /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field. The 0th value /// of the resultant node is returned. - SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT); - SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, - SDOperand Op1); - SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, - SDOperand Op1, SDOperand Op2); - SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, - SDOperand Op1, SDOperand Op2, SDOperand Op3); - SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, - SDOperand Op1, SDOperand Op2, SDOperand Op3, - SDOperand Op4); - SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, - SDOperand Op1, SDOperand Op2, SDOperand Op3, - SDOperand Op4, SDOperand Op5); - SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, - SDOperand Op1, SDOperand Op2, SDOperand Op3, - SDOperand Op4, SDOperand Op5, SDOperand Op6); - SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, - SDOperand Op1, SDOperand Op2, SDOperand Op3, - SDOperand Op4, SDOperand Op5, SDOperand Op6, - SDOperand Op7); - SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, - SDOperand Op1, SDOperand Op2, SDOperand Op3, - SDOperand Op4, SDOperand Op5, SDOperand Op6, - SDOperand Op7, SDOperand Op8); - SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, - MVT::ValueType VT2, SDOperand Op1, SDOperand Op2); - SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, - MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, - SDOperand Op3); - SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, - MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, - SDOperand Op3, SDOperand Op4); - SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, - MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, - SDOperand Op3, SDOperand Op4, SDOperand Op5); - - SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT) { - return getNode(ISD::BUILTIN_OP_END+Opcode, VT); - } - SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT, - SDOperand Op1) { - return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1); - } - SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT, - SDOperand Op1, SDOperand Op2) { - return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2); - } - SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT, - SDOperand Op1, SDOperand Op2, SDOperand Op3) { - return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3); - } - SDOperand 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); - } - SDOperand 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); - } - SDOperand 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); - } - SDOperand 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); - } - SDOperand 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); - } - SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT, - std::vector &Ops) { - return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops); - } - SDOperand 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); - } - SDOperand 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); - } - SDOperand 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); - } - SDOperand 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); - } - SDOperand 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); - } - SDOperand 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); - } - SDOperand 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); - } - SDOperand 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); - } - SDOperand 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); - } - SDOperand 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); - } - SDOperand 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); - } - SDOperand 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); - } + SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT); + SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, SDOperand Op1); + SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, + SDOperand Op1, SDOperand Op2); + SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, + SDOperand Op1, SDOperand Op2, SDOperand Op3); + SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, + SDOperandPtr Ops, unsigned NumOps); + SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, + MVT VT2, SDOperand Op1, SDOperand Op2); + SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, + MVT VT2, SDOperand Op1, SDOperand Op2, SDOperand Op3); + + + /// getTargetNode - These are used for target selectors to create a new node + /// with specified return type(s), target opcode, and operands. + /// + /// Note that getTargetNode returns the resultant node. If there is already a + /// node of the specified opcode and operands, it returns that node instead of + /// the current one. + SDNode *getTargetNode(unsigned Opcode, MVT VT); + SDNode *getTargetNode(unsigned Opcode, MVT VT, SDOperand Op1); + SDNode *getTargetNode(unsigned Opcode, MVT VT, SDOperand Op1, SDOperand Op2); + SDNode *getTargetNode(unsigned Opcode, MVT VT, + SDOperand Op1, SDOperand Op2, SDOperand Op3); + SDNode *getTargetNode(unsigned Opcode, MVT VT, + SDOperandPtr Ops, unsigned NumOps); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, SDOperand Op1); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, + MVT VT2, SDOperand Op1, SDOperand Op2); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, + MVT VT2, SDOperand Op1, SDOperand Op2, SDOperand Op3); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, + SDOperandPtr Ops, unsigned NumOps); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, + SDOperand Op1, SDOperand Op2); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, + SDOperand Op1, SDOperand Op2, SDOperand Op3); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, + SDOperandPtr Ops, unsigned NumOps); + SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, MVT VT4, + SDOperandPtr Ops, unsigned NumOps); + SDNode *getTargetNode(unsigned Opcode, std::vector &ResultTys, + SDOperandPtr Ops, unsigned NumOps); + + /// getNodeIfExists - Get the specified node if it's already available, or + /// else return NULL. + SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, + SDOperandPtr Ops, unsigned NumOps); + + /// DAGUpdateListener - Clients of various APIs that cause global effects on + /// the DAG can optionally implement this interface. This allows the clients + /// to handle the various sorts of updates that happen. + class DAGUpdateListener { + public: + virtual ~DAGUpdateListener(); + + /// NodeDeleted - The node N that was deleted and, if E is not null, an + /// equivalent node E that replaced it. + virtual void NodeDeleted(SDNode *N, SDNode *E) = 0; + + /// NodeUpdated - The node N that was updated. + virtual void NodeUpdated(SDNode *N) = 0; + }; + + /// RemoveDeadNode - Remove the specified node from the system. If any of its + /// operands then becomes dead, remove them as well. Inform UpdateListener + /// for each node deleted. + void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0); /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. /// This can cause recursive merging of nodes in the DAG. Use the first /// version if 'From' is known to have a single result, use the second /// if you have two nodes with identical results, use the third otherwise. /// - /// These methods all take an optional vector, which (if not null) is - /// populated with any nodes that are deleted from the SelectionDAG, due to - /// new equivalences that are discovered. + /// These methods all take an optional UpdateListener, which (if not null) is + /// informed about nodes that are deleted and modified due to recursive + /// changes in the dag. /// void ReplaceAllUsesWith(SDOperand From, SDOperand Op, - std::vector *Deleted = 0); + DAGUpdateListener *UpdateListener = 0); void ReplaceAllUsesWith(SDNode *From, SDNode *To, - std::vector *Deleted = 0); - void ReplaceAllUsesWith(SDNode *From, const std::vector &To, - std::vector *Deleted = 0); + DAGUpdateListener *UpdateListener = 0); + void ReplaceAllUsesWith(SDNode *From, SDOperandPtr To, + DAGUpdateListener *UpdateListener = 0); + + /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving + /// uses of other values produced by From.Val alone. + void ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, + DAGUpdateListener *UpdateListener = 0); + + /// AssignNodeIds - Assign a unique node id for each node in the DAG based on + /// their allnodes order. It returns the maximum id. + unsigned AssignNodeIds(); + + /// 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); + + /// isCommutativeBinOp - Returns true if the opcode is a commutative binary + /// operation. + static bool isCommutativeBinOp(unsigned Opcode) { + // FIXME: This should get its info from the td file, so that we can include + // target info. + switch (Opcode) { + case ISD::ADD: + case ISD::MUL: + case ISD::MULHU: + case ISD::MULHS: + case ISD::SMUL_LOHI: + case ISD::UMUL_LOHI: + case ISD::FADD: + case ISD::FMUL: + case ISD::AND: + case ISD::OR: + case ISD::XOR: + case ISD::ADDC: + case ISD::ADDE: return true; + default: return false; + } + } + + void dump() const; + + /// CreateStackTemporary - Create a stack temporary, suitable for holding the + /// specified value type. + SDOperand CreateStackTemporary(MVT VT); + /// FoldSetCC - Constant fold a setcc to true or false. + SDOperand FoldSetCC(MVT VT, SDOperand N1, + SDOperand N2, ISD::CondCode Cond); - /// DeleteNode - Remove the specified node from the system. This node must - /// have no referrers. - void DeleteNode(SDNode *N); + /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We + /// use this predicate to simplify operations downstream. + bool SignBitIsZero(SDOperand Op, unsigned Depth = 0) const; + + /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We + /// use this predicate to simplify operations downstream. Op and Mask are + /// known to be the same type. + bool MaskedValueIsZero(SDOperand Op, const APInt &Mask, unsigned Depth = 0) + const; + + /// ComputeMaskedBits - Determine which of the bits specified in Mask are + /// known to be either zero or one and return them in the KnownZero/KnownOne + /// bitsets. This code only analyzes bits in Mask, in order to short-circuit + /// processing. Targets can implement the computeMaskedBitsForTargetNode + /// method in the TargetLowering class to allow target nodes to be understood. + void ComputeMaskedBits(SDOperand Op, const APInt &Mask, APInt &KnownZero, + APInt &KnownOne, unsigned Depth = 0) const; + + /// ComputeNumSignBits - Return the number of times the sign bit of the + /// register is replicated into the other bits. We know that at least 1 bit + /// is always equal to the sign bit (itself), but other cases can give us + /// information. For example, immediately after an "SRA X, 2", we know that + /// the top 3 bits are all equal to each other, so we return 3. Targets can + /// implement the ComputeNumSignBitsForTarget method in the TargetLowering + /// class to allow target nodes to be understood. + unsigned ComputeNumSignBits(SDOperand Op, unsigned Depth = 0) const; + + /// isVerifiedDebugInfoDesc - Returns true if the specified SDOperand has + /// been verified as a debug information descriptor. + bool isVerifiedDebugInfoDesc(SDOperand Op) const; + + /// getShuffleScalarElt - Returns the scalar element that will make up the ith + /// element of the result of the vector shuffle. + SDOperand getShuffleScalarElt(const SDNode *N, unsigned Idx); - void dump() const; - private: void RemoveNodeFromCSEMaps(SDNode *N); SDNode *AddNonLeafNodeToCSEMaps(SDNode *N); - SDNode **FindModifiedNodeSlot(SDNode *N, SDOperand Op); - SDNode **FindModifiedNodeSlot(SDNode *N, SDOperand Op1, SDOperand Op2); - SDNode **FindModifiedNodeSlot(SDNode *N, const std::vector &Ops); + SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op, void *&InsertPos); + SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op1, SDOperand Op2, + void *&InsertPos); + SDNode *FindModifiedNodeSlot(SDNode *N, SDOperandPtr Ops, unsigned NumOps, + void *&InsertPos); - void DestroyDeadNode(SDNode *N); void DeleteNodeNotInCSEMaps(SDNode *N); - void setNodeValueTypes(SDNode *N, std::vector &RetVals); - void setNodeValueTypes(SDNode *N, MVT::ValueType VT1, MVT::ValueType VT2); - - - /// SimplifySetCC - Try to simplify a setcc built with the specified operands - /// and cc. If unable to simplify it, return a null SDOperand. - SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N1, - SDOperand N2, ISD::CondCode Cond); // List of non-single value types. - std::list > VTList; + std::list > VTList; // Maps to auto-CSE operations. - std::map, SDNode *> NullaryOps; - std::map >, - SDNode *> UnaryOps; - std::map >, - SDNode *> BinaryOps; - - std::map, RegisterSDNode*> RegNodes; std::vector CondCodeNodes; - std::map >, - SDNode *> Loads; - - std::map, SDNode*> GlobalValues; - std::map, SDNode*> TargetGlobalValues; - std::map, SDNode*> Constants; - std::map, SDNode*> TargetConstants; - std::map, SDNode*> ConstantFPs; - std::map, SDNode*> TargetConstantFPs; - std::map FrameIndices, TargetFrameIndices; - std::map, SDNode*> ConstantPoolIndices; - std::map, SDNode*> TargetConstantPoolIndices; - std::map BBNodes; std::vector ValueTypeNodes; - std::map ExternalSymbols; - std::map TargetExternalSymbols; - std::map StringNodes; - std::map > >, - SDNode*> OneResultNodes; - std::map, - std::vector > >, - SDNode*> ArbitraryNodes; + std::map ExtendedValueTypeNodes; + StringMap ExternalSymbols; + StringMap TargetExternalSymbols; + StringMap StringNodes; }; template <> struct GraphTraits : public GraphTraits {