Changes in directory llvm/lib/CodeGen/SelectionDAG:
SelectionDAG.cpp updated: 1.326 -> 1.327
SelectionDAGCSEMap.cpp updated: 1.6 -> 1.7
---
Log message:
Add code to resize the CSEMap hash table. This doesn't speedup codegen of
kimwitu, but seems like a good idea from a "avoid performance cliffs"
standpoint :)
---
Diffs of the changes: (+47 -3)
SelectionDAG.cpp | 1 +
SelectionDAGCSEMap.cpp | 49 ++++++++++++++++++++++++++++++++++++++++++++++---
2 files changed, 47 insertions(+), 3 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:1.326
llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:1.327
--- llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:1.326 Mon Aug 14
15:12:44 2006
+++ llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp Mon Aug 14 17:19:25 2006
@@ -469,6 +469,7 @@
SelectionDAG::~SelectionDAG() {
while (!AllNodes.empty()) {
SDNode *N = AllNodes.begin();
+ N->SetNextInBucket(0);
delete [] N->OperandList;
N->OperandList = 0;
N->NumOperands = 0;
Index: llvm/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp:1.6
llvm/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp:1.7
--- llvm/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp:1.6 Mon Aug 14
15:12:44 2006
+++ llvm/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp Mon Aug 14
17:19:25 2006
@@ -157,7 +157,7 @@
// SelectionDAGCSEMap Implementation
SelectionDAGCSEMap::SelectionDAGCSEMap() : NumNodes(0) {
- NumBuckets = 256;
+ NumBuckets = 64;
Buckets = new void*[NumBuckets];
memset(Buckets, 0, NumBuckets*sizeof(void*));
}
@@ -176,6 +176,15 @@
return static_cast<SDNode*>(NextInBucketPtr);
}
+/// GetNextPtr - This is just like the previous GetNextPtr implementation, but
+/// allows a bucket array to be specified.
+SDNode *SelectionDAGCSEMap::GetNextPtr(void *NextInBucketPtr, void **Bucks,
+ unsigned NumBuck) {
+ if (NextInBucketPtr >= Bucks && NextInBucketPtr < Bucks+NumBuck)
+ return 0;
+ return static_cast<SDNode*>(NextInBucketPtr);
+}
+
void **SelectionDAGCSEMap::GetBucketPtr(void *NextInBucketPtr) {
//assert(NextInBucketPtr >= Buckets && NextInBucketPtr < Buckets+NumBuckets
&&
// "NextInBucketPtr is not a bucket ptr");
@@ -185,13 +194,42 @@
/// GetBucketFor - Hash the specified node ID and return the hash bucket for
the
/// specified ID.
void **SelectionDAGCSEMap::GetBucketFor(const NodeID &ID) const {
- // TODO: if load is high, resize hash table.
-
// NumBuckets is always a power of 2.
unsigned BucketNum = ID.ComputeHash() & (NumBuckets-1);
return Buckets+BucketNum;
}
+/// GrowHashTable - Double the size of the hash table and rehash everything.
+///
+void SelectionDAGCSEMap::GrowHashTable() {
+ void **OldBuckets = Buckets;
+ unsigned OldNumBuckets = NumBuckets;
+ NumBuckets <<= 1;
+
+ // Reset the node count to zero: we're going to reinsert everything.
+ NumNodes = 0;
+
+ // Clear out new buckets.
+ Buckets = new void*[NumBuckets];
+ memset(Buckets, 0, NumBuckets*sizeof(void*));
+
+ // Walk the old buckets, rehashing nodes into their new place.
+ for (unsigned i = 0; i != OldNumBuckets; ++i) {
+ void *Probe = OldBuckets[i];
+ if (!Probe) continue;
+ while (SDNode *NodeInBucket = GetNextPtr(Probe, OldBuckets,
OldNumBuckets)){
+ // Figure out the next link, remove NodeInBucket from the old link.
+ Probe = NodeInBucket->getNextInBucket();
+ NodeInBucket->SetNextInBucket(0);
+
+ // Insert the node into the new bucket, after recomputing the hash.
+ InsertNode(NodeInBucket, GetBucketFor(NodeID(NodeInBucket)));
+ }
+ }
+
+ delete[] OldBuckets;
+}
+
/// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
/// return it. If not, return the insertion token that will make insertion
/// faster.
@@ -226,6 +264,11 @@
/// FindNodeOrInsertPos.
void SelectionDAGCSEMap::InsertNode(SDNode *N, void *InsertPos) {
++NumNodes;
+ // Do we need to grow the hashtable?
+ if (NumNodes > NumBuckets*2) {
+ GrowHashTable();
+ InsertPos = GetBucketFor(NodeID(N));
+ }
/// The insert position is actually a bucket pointer.
void **Bucket = static_cast<void**>(InsertPos);
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
