Pool-allocation for SDNodes. The pool is allocated once for each function,
and reused across SelectionDAGs.
This drastically reduces the number of calls to malloc/free made during
instruction selection, and improves memory locality.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53211 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index 56bd40a..d31bb4e 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -17,7 +17,6 @@
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/StringMap.h"
-#include "llvm/ADT/ilist.h"
#include "llvm/CodeGen/SelectionDAGNodes.h"
#include <list>
@@ -55,7 +54,7 @@
SDOperand Root, EntryNode;
/// AllNodes - A linked list of nodes in the current DAG.
- ilist<SDNode> AllNodes;
+ alist<SDNode, LargestSDNode> &AllNodes;
/// CSEMap - This structure is used to memoize nodes, automatically performing
/// CSE with existing nodes with a duplicate is requested.
@@ -63,8 +62,9 @@
public:
SelectionDAG(TargetLowering &tli, MachineFunction &mf,
- FunctionLoweringInfo &fli, MachineModuleInfo *mmi)
- : TLI(tli), MF(mf), FLI(fli), MMI(mmi) {
+ FunctionLoweringInfo &fli, MachineModuleInfo *mmi,
+ alist<SDNode, LargestSDNode> &NodePool)
+ : TLI(tli), MF(mf), FLI(fli), MMI(mmi), AllNodes(NodePool) {
EntryNode = Root = getNode(ISD::EntryToken, MVT::Other);
}
~SelectionDAG();
@@ -99,13 +99,15 @@
///
void setGraphColor(const SDNode *N, const char *Color);
- typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
+ typedef alist<SDNode, LargestSDNode>::const_iterator allnodes_const_iterator;
allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
- typedef ilist<SDNode>::iterator allnodes_iterator;
+ typedef alist<SDNode, LargestSDNode>::iterator allnodes_iterator;
allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
allnodes_iterator allnodes_end() { return AllNodes.end(); }
- ilist<SDNode>::size_type allnodes_size() const { return AllNodes.size(); }
+ alist<SDNode, LargestSDNode>::size_type allnodes_size() const {
+ return AllNodes.size();
+ }
/// getRoot - Return the root tag of the SelectionDAG.
///
@@ -642,6 +644,7 @@
SDOperand getShuffleScalarElt(const SDNode *N, unsigned Idx);
private:
+ inline alist_traits<SDNode, LargestSDNode>::AllocatorType &getAllocator();
void RemoveNodeFromCSEMaps(SDNode *N);
SDNode *AddNonLeafNodeToCSEMaps(SDNode *N);
SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op, void *&InsertPos);
diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h
index c5aa77a..ad573b4 100644
--- a/include/llvm/CodeGen/SelectionDAGISel.h
+++ b/include/llvm/CodeGen/SelectionDAGISel.h
@@ -178,8 +178,11 @@
int64_t DesiredMaskS) const;
private:
+ void SelectAllBasicBlocks(Function &Fn, MachineFunction &MF,
+ FunctionLoweringInfo &FuncInfo);
void SelectBasicBlock(BasicBlock *BB, MachineFunction &MF,
- FunctionLoweringInfo &FuncInfo);
+ FunctionLoweringInfo &FuncInfo,
+ alist<SDNode, LargestSDNode> &AllNodes);
void BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h
index fe1cab6..c4f1f96 100644
--- a/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -25,8 +25,11 @@
#include "llvm/ADT/iterator.h"
#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/APInt.h"
+#include "llvm/ADT/alist.h"
#include "llvm/CodeGen/ValueTypes.h"
#include "llvm/CodeGen/MachineMemOperand.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/RecyclingAllocator.h"
#include "llvm/Support/DataTypes.h"
#include <cassert>
@@ -40,9 +43,6 @@
class CompileUnitDesc;
template <typename T> struct DenseMapInfo;
template <typename T> struct simplify_type;
-template <typename T> struct ilist_traits;
-template<typename NodeTy, typename Traits> class iplist;
-template<typename NodeTy> class ilist_iterator;
/// SDVTList - This represents a list of ValueType's that has been intern'd by
/// a SelectionDAG. Instances of this simple value class are returned by
@@ -1054,11 +1054,6 @@
/// Uses - List of uses for this SDNode.
SDUse *Uses;
- /// Prev/Next pointers - These pointers form the linked list of of the
- /// AllNodes list in the current DAG.
- SDNode *Prev, *Next;
- friend struct ilist_traits<SDNode>;
-
/// addUse - add SDUse to the list of uses.
void addUse(SDUse &U) { U.addToList(&Uses); }
@@ -1268,7 +1263,6 @@
ValueList = VTs.VTs;
NumValues = VTs.NumVTs;
- Prev = 0; Next = 0;
}
SDNode(unsigned Opc, SDVTList VTs, const SDUse *Ops, unsigned NumOps)
@@ -1286,7 +1280,6 @@
ValueList = VTs.VTs;
NumValues = VTs.NumVTs;
- Prev = 0; Next = 0;
}
SDNode(unsigned Opc, SDVTList VTs)
@@ -1296,7 +1289,6 @@
OperandList = 0;
ValueList = VTs.VTs;
NumValues = VTs.NumVTs;
- Prev = 0; Next = 0;
}
/// InitOperands - Initialize the operands list of this node with the
@@ -2234,26 +2226,30 @@
}
};
-template<>
-struct ilist_traits<SDNode> {
- static SDNode *getPrev(const SDNode *N) { return N->Prev; }
- static SDNode *getNext(const SDNode *N) { return N->Next; }
-
- static void setPrev(SDNode *N, SDNode *Prev) { N->Prev = Prev; }
- static void setNext(SDNode *N, SDNode *Next) { N->Next = Next; }
-
- static SDNode *createSentinel() {
- return new SDNode(ISD::EntryToken, SDNode::getSDVTList(MVT::Other));
+/// LargestSDNode - The largest SDNode class.
+///
+typedef LoadSDNode LargestSDNode;
+
+// alist_traits specialization for pool-allocating SDNodes.
+template <>
+class alist_traits<SDNode, LargestSDNode> {
+ typedef alist_iterator<SDNode, LargestSDNode> iterator;
+
+public:
+ // Pool-allocate and recycle SDNodes.
+ typedef RecyclingAllocator<BumpPtrAllocator, SDNode, LargestSDNode>
+ AllocatorType;
+
+ // Allocate the allocator immediately inside the traits class.
+ AllocatorType Allocator;
+
+ void addNodeToList(SDNode* N) {}
+ void removeNodeFromList(SDNode* N) {}
+ void transferNodesFromList(alist_traits &, iterator, iterator) {}
+ void deleteNode(SDNode *N) {
+ N->~SDNode();
+ Allocator.Deallocate(N);
}
- static void destroySentinel(SDNode *N) { delete N; }
- //static SDNode *createNode(const SDNode &V) { return new SDNode(V); }
-
-
- void addNodeToList(SDNode *) {}
- void removeNodeFromList(SDNode *) {}
- void transferNodesFromList(iplist<SDNode, ilist_traits> &,
- const ilist_iterator<SDNode> &,
- const ilist_iterator<SDNode> &) {}
};
namespace ISD {