Author: kremenek
Date: Mon Jan 21 16:33:30 2008
New Revision: 46224
URL: http://llvm.org/viewvc/llvm-project?rev=46224&view=rev
Log:
Replaced (FoldingSet) profiling of ImutAVLTree with a hashing based scheme. The
problem was that we previously hashed based on the pointers of the left and
right children, but this is bogus: we can easily have different trees that
represent the same set. Now we use a hashing based scheme that compares the
*contents* of the trees, but not without having to do a full scan of a tree. The
only caveat is that with hashing is that we may have collisions, which result in
two different trees being falsely labeled as equivalent. If this becomes a
problem, we can add extra data to the profile to hopefully resolve most
collisions.
Modified:
llvm/trunk/include/llvm/ADT/ImmutableSet.h
Modified: llvm/trunk/include/llvm/ADT/ImmutableSet.h
URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/ADT/ImmutableSet.h?rev=46224&r1=46223&r2=46224&view=diff
==============================================================================
--- llvm/trunk/include/llvm/ADT/ImmutableSet.h (original)
+++ llvm/trunk/include/llvm/ADT/ImmutableSet.h Mon Jan 21 16:33:30 2008
@@ -198,6 +198,7 @@
ImutAVLTree* Right;
unsigned Height;
value_type Value;
+ unsigned Hash;
//===----------------------------------------------------===//
// Profiling or FoldingSet.
@@ -205,22 +206,38 @@
private:
+ static inline
+ unsigned ComputeHash(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) {
+ FoldingSetNodeID ID;
+
+ ID.AddInteger(L ? L->ComputeHash() : 0);
+ ImutInfo::Profile(ID,V);
+ ID.AddInteger(R ? R->ComputeHash() : 0);
+
+ return ID.ComputeHash();
+ }
+
+ inline unsigned ComputeHash() {
+ if (!isMutable() && Hash) return Hash;
+ Hash = ComputeHash(getSafeLeft(), getRight(), getValue());
+ return Hash;
+ }
+
/// Profile - Generates a FoldingSet profile for a tree node before it is
/// created. This is used by the ImutAVLFactory when creating
/// trees.
static inline
void Profile(FoldingSetNodeID& ID, ImutAVLTree* L, ImutAVLTree* R,
- value_type_ref V) {
- ID.AddPointer(L);
- ID.AddPointer(R);
- ImutInfo::Profile(ID,V);
+ value_type_ref V) {
+
+ ID.AddInteger(ComputeHash(L, R, V));
}
public:
/// Profile - Generates a FoldingSet profile for an existing tree node.
void Profile(FoldingSetNodeID& ID) {
- Profile(ID,getSafeLeft(),getRight(),getValue());
+ ID.AddInteger(ComputeHash());
}
//===----------------------------------------------------===//
@@ -235,7 +252,7 @@
/// ImutAVLFactory.
ImutAVLTree(ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, unsigned
height)
: Left(reinterpret_cast<uintptr_t>(l) | Mutable),
- Right(r), Height(height), Value(v) {}
+ Right(r), Height(height), Value(v), Hash(0) {}
/// isMutable - Returns true if the left and right subtree references
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
