Changes in directory llvm/lib/CodeGen/SelectionDAG:
SelectionDAGCSEMap.cpp updated: 1.4 -> 1.5
---
Log message:
Switch to using SuperFastHash instead of adding all elements together. This
doesn't significantly improve performance but it helps a small amount.
---
Diffs of the changes: (+24 -6)
SelectionDAGCSEMap.cpp | 30 ++++++++++++++++++++++++------
1 files changed, 24 insertions(+), 6 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp:1.4
llvm/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp:1.5
--- llvm/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp:1.4 Fri Aug 11
18:55:53 2006
+++ llvm/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp Fri Aug 11
20:07:10 2006
@@ -126,10 +126,23 @@
/// ComputeHash - Compute a strong hash value for this NodeID, for lookup in
/// the SelectionDAGCSEMap.
unsigned SelectionDAGCSEMap::NodeID::ComputeHash() const {
- // FIXME: this hash function sucks.
- unsigned Hash = 0;
- for (unsigned i = 0, e = Bits.size(); i != e; ++i)
- Hash = Hash+Bits[i];
+ // This is adapted from SuperFastHash by Paul Hsieh.
+ unsigned Hash = Bits.size();
+ for (const unsigned *BP = &Bits[0], *E = BP+Bits.size(); BP != E; ++BP) {
+ unsigned Data = *BP;
+ Hash += Data & 0xFFFF;
+ unsigned Tmp = ((Data >> 16) << 11) ^ Hash;
+ Hash = (Hash << 16) ^ Tmp;
+ Hash += Hash >> 11;
+ }
+
+ // Force "avalanching" of final 127 bits.
+ Hash ^= Hash << 3;
+ Hash += Hash >> 5;
+ Hash ^= Hash << 4;
+ Hash += Hash >> 17;
+ Hash ^= Hash << 25;
+ Hash += Hash >> 6;
return Hash;
}
@@ -142,7 +155,7 @@
//===----------------------------------------------------------------------===//
// SelectionDAGCSEMap Implementation
-SelectionDAGCSEMap::SelectionDAGCSEMap() {
+SelectionDAGCSEMap::SelectionDAGCSEMap() : NumNodes(0) {
NumBuckets = 256;
Buckets = new void*[NumBuckets];
memset(Buckets, 0, NumBuckets*sizeof(void*));
@@ -211,6 +224,8 @@
/// is not already in the map. InsertPos must be obtained from
/// FindNodeOrInsertPos.
void SelectionDAGCSEMap::InsertNode(SDNode *N, void *InsertPos) {
+ ++NumNodes;
+
/// The insert position is actually a bucket pointer.
void **Bucket = static_cast<void**>(InsertPos);
@@ -230,12 +245,15 @@
/// RemoveNode - Remove a node from the CSE map, returning true if one was
/// removed or false if the node was not in the CSE map.
bool SelectionDAGCSEMap::RemoveNode(SDNode *N) {
+
// Because each bucket is a circular list, we don't need to compute N's hash
// to remove it. Chase around the list until we find the node (or bucket)
// which points to N.
void *Ptr = N->getNextInBucket();
if (Ptr == 0) return false; // Not in CSEMap.
-
+
+ --NumNodes;
+
void *NodeNextPtr = Ptr;
N->SetNextInBucket(0);
while (1) {
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
