Changes in directory llvm/include/llvm/CodeGen:
SelectionDAG.h updated: 1.108 -> 1.109 SelectionDAGNodes.h updated: 1.137 -> 1.138 --- Log message: Revamp the "CSEMap" datastructure used in the SelectionDAG class. This eliminates a bunch of std::map's in the SelectionDAG, replacing them with a home-grown hashtable. This is still a work in progress: not all the maps have been moved over and the hashtable never resizes. That said, this still speeds up llc 20% on kimwitu++ with -fast -regalloc=local using a release build. --- Diffs of the changes: (+24 -24) SelectionDAG.h | 29 ++++++++++------------------- SelectionDAGNodes.h | 19 ++++++++++++++----- 2 files changed, 24 insertions(+), 24 deletions(-) Index: llvm/include/llvm/CodeGen/SelectionDAG.h diff -u llvm/include/llvm/CodeGen/SelectionDAG.h:1.108 llvm/include/llvm/CodeGen/SelectionDAG.h:1.109 --- llvm/include/llvm/CodeGen/SelectionDAG.h:1.108 Fri Aug 4 12:45:20 2006 +++ llvm/include/llvm/CodeGen/SelectionDAG.h Mon Aug 7 18:03:03 2006 @@ -16,6 +16,7 @@ #define LLVM_CODEGEN_SELECTIONDAG_H #include "llvm/CodeGen/SelectionDAGNodes.h" +#include "llvm/CodeGen/SelectionDAGCSEMap.h" #include "llvm/ADT/ilist" #include <list> @@ -441,13 +442,16 @@ 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<SDOperand> &Ops); + SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op, void *&InsertPos); + SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op1, SDOperand Op2, + void *&InsertPos); + SDNode *FindModifiedNodeSlot(SDNode *N, const std::vector<SDOperand> &Ops, + void *&InsertPos); void DeleteNodeNotInCSEMaps(SDNode *N); - void setNodeValueTypes(SDNode *N, std::vector<MVT::ValueType> &RetVals); - void setNodeValueTypes(SDNode *N, MVT::ValueType VT1, MVT::ValueType VT2); + MVT::ValueType *getNodeValueTypes(MVT::ValueType VT1); + MVT::ValueType *getNodeValueTypes(MVT::ValueType VT1, MVT::ValueType VT2); + MVT::ValueType *getNodeValueTypes(std::vector<MVT::ValueType> &RetVals); /// SimplifySetCC - Try to simplify a setcc built with the specified operands @@ -460,17 +464,10 @@ // Maps to auto-CSE operations. std::map<std::pair<unsigned, MVT::ValueType>, SDNode *> NullaryOps; - std::map<std::pair<unsigned, std::pair<SDOperand, MVT::ValueType> >, - SDNode *> UnaryOps; - std::map<std::pair<unsigned, std::pair<SDOperand, SDOperand> >, - SDNode *> BinaryOps; std::map<std::pair<unsigned, MVT::ValueType>, RegisterSDNode*> RegNodes; std::vector<CondCodeSDNode*> CondCodeNodes; - std::map<std::pair<SDOperand, std::pair<SDOperand, MVT::ValueType> >, - SDNode *> Loads; - std::map<std::pair<const GlobalValue*, int>, SDNode*> GlobalValues; std::map<std::pair<const GlobalValue*, int>, SDNode*> TargetGlobalValues; std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> Constants; @@ -488,13 +485,7 @@ std::map<std::string, SDNode*> ExternalSymbols; std::map<std::string, SDNode*> TargetExternalSymbols; std::map<std::string, StringSDNode*> StringNodes; - std::map<std::pair<unsigned, - std::pair<MVT::ValueType, std::vector<SDOperand> > >, - SDNode*> OneResultNodes; - std::map<std::pair<unsigned, - std::pair<std::vector<MVT::ValueType>, - std::vector<SDOperand> > >, - SDNode*> ArbitraryNodes; + SelectionDAGCSEMap CSEMap; }; template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { Index: llvm/include/llvm/CodeGen/SelectionDAGNodes.h diff -u llvm/include/llvm/CodeGen/SelectionDAGNodes.h:1.137 llvm/include/llvm/CodeGen/SelectionDAGNodes.h:1.138 --- llvm/include/llvm/CodeGen/SelectionDAGNodes.h:1.137 Thu Jul 27 01:38:21 2006 +++ llvm/include/llvm/CodeGen/SelectionDAGNodes.h Mon Aug 7 18:03:03 2006 @@ -707,6 +707,9 @@ SDNode *Prev, *Next; friend struct ilist_traits<SDNode>; + /// NextInBucket - This is used by the SelectionDAGCSEMap. + void *NextInBucket; + /// Uses - These are all of the SDNode's that use a value produced by this /// node. std::vector<SDNode*> Uses; @@ -789,6 +792,11 @@ static bool classof(const SDNode *) { return true; } + + /// NextInBucket accessors, these are private to SelectionDAGCSEMap. + void *getNextInBucket() const { return NextInBucket; } + void SetNextInBucket(void *N) { NextInBucket = N; } + protected: friend class SelectionDAG; @@ -801,6 +809,7 @@ ValueList = getValueTypeList(VT); NumValues = 1; Prev = 0; Next = 0; + NextInBucket = 0; } SDNode(unsigned NT, SDOperand Op) : NodeType(NT), NodeId(-1) { @@ -811,6 +820,7 @@ ValueList = 0; NumValues = 0; Prev = 0; Next = 0; + NextInBucket = 0; } SDNode(unsigned NT, SDOperand N1, SDOperand N2) : NodeType(NT), NodeId(-1) { @@ -822,6 +832,7 @@ ValueList = 0; NumValues = 0; Prev = 0; Next = 0; + NextInBucket = 0; } SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3) : NodeType(NT), NodeId(-1) { @@ -836,6 +847,7 @@ ValueList = 0; NumValues = 0; Prev = 0; Next = 0; + NextInBucket = 0; } SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4) : NodeType(NT), NodeId(-1) { @@ -851,6 +863,7 @@ ValueList = 0; NumValues = 0; Prev = 0; Next = 0; + NextInBucket = 0; } SDNode(unsigned Opc, const std::vector<SDOperand> &Nodes) : NodeType(Opc), NodeId(-1) { @@ -865,6 +878,7 @@ ValueList = 0; NumValues = 0; Prev = 0; Next = 0; + NextInBucket = 0; } /// MorphNodeTo - This clears the return value and operands list, and sets the @@ -884,11 +898,6 @@ NumOperands = 0; } - void setValueTypes(MVT::ValueType VT) { - assert(NumValues == 0 && "Should not have values yet!"); - ValueList = getValueTypeList(VT); - NumValues = 1; - } void setValueTypes(MVT::ValueType *List, unsigned NumVal) { assert(NumValues == 0 && "Should not have values yet!"); ValueList = List; _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits