-/*===-- Libraries/tracelib.c - Runtime routines for tracing -----*- C++ -*--===
+/*===-- tracelib.c - Runtime routines for tracing ---------------*- C++ -*-===*
*
- * Runtime routines for supporting tracing of execution
- * for code generated by LLVM.
+ * Runtime routines for supporting tracing of execution for code generated by
+ * LLVM.
*
- *===---------------------------------------------------------------------===*/
+ *===----------------------------------------------------------------------===*/
#include "tracelib.h"
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
-
+#include "Support/DataTypes.h"
/*===---------------------------------------------------------------------=====
* HASH FUNCTIONS
*===---------------------------------------------------------------------===*/
/* use #defines until we have inlining */
-
-typedef int64_t Generic;
-typedef uint64_t Index;
-typedef ptrdiff_t Pointer;
+typedef uintptr_t Index; /* type of keys, size for hash table */
+typedef uint32_t Generic; /* type of values stored in table */
/* Index IntegerHashFunc(const Generic value, const Index size) */
#define IntegerHashFunc(value, size) \
- (value % size)
+ ( ((((Index) value) << 3) ^ (((Index) value) >> 3)) % size )
/* Index IntegerRehashFunc(const Generic oldHashValue, const Index size) */
#define IntegerRehashFunc(oldHashValue, size) \
- ((oldHashValue+16) % size) /* 16 is relatively prime to a Mersenne prime! */
+ ((Index) ((oldHashValue+16) % size)) /* 16 is relatively prime to a Mersenne prime! */
/* Index PointerHashFunc(const void* value, const Index size) */
#define PointerHashFunc(value, size) \
- IntegerHashFunc((Pointer) value, size)
+ IntegerHashFunc((Index) value, size)
/* Index PointerRehashFunc(const void* value, const Index size) */
#define PointerRehashFunc(value, size) \
- IntegerRehashFunc((Pointer) value, size)
-
+ IntegerRehashFunc((Index) value, size)
/*===---------------------------------------------------------------------=====
* POINTER-TO-GENERIC HASH TABLE.
const FULLEMPTY EMPTY = '\0';
const FULLEMPTY FULL = '\1';
+// List of primes closest to powers of 2 in [2^20 -- 2^30], obtained from
+// http://www.utm.edu/research/primes/lists/2small/0bit.html.
+// Use these as the successive sizes of the hash table.
+#define NUMPRIMES 11
+#define FIRSTENTRY 2
+const uint PRIMES[NUMPRIMES] = { (1<<20)-3, (1<<21)-9, (1<<22)-3, (1<<23)-15,
+ (1<<24)-3, (1<<25)-39, (1<<26)-5, (1<<27)-39,
+ (1<<28)-57, (1<<29)-3, (1<<30)-35 };
+uint CurrentSizeEntry = FIRSTENTRY;
+
const uint MAX_NUM_PROBES = 4;
typedef struct PtrValueHashEntry_struct {
} PtrValueHashTable;
-extern Generic LookupOrInsertPtr(PtrValueHashTable* ptrTable,
- void* ptr, ACTION action);
+static Generic LookupOrInsertPtr(PtrValueHashTable* ptrTable, void* ptr,
+ ACTION action, Generic value);
-extern void Insert(PtrValueHashTable* ptrTable, void* ptr, Generic value);
+static void Insert(PtrValueHashTable* ptrTable, void* ptr, Generic value);
-extern void Delete(PtrValueHashTable* ptrTable, void* ptr);
+static void Delete(PtrValueHashTable* ptrTable, void* ptr);
+/* Returns 0 if the item is not found. */
+/* void* LookupPtr(PtrValueHashTable* ptrTable, void* ptr) */
+#define LookupPtr(ptrTable, ptr) \
+ LookupOrInsertPtr(ptrTable, ptr, FIND, (Generic) 0)
void
InitializeTable(PtrValueHashTable* ptrTable, Index newSize)
{
- ptrTable->table = (PtrValueHashEntry*) malloc(newSize *
+ ptrTable->table = (PtrValueHashEntry*) calloc(newSize,
sizeof(PtrValueHashEntry));
- ptrTable->fullEmptyFlags = (FULLEMPTY*) malloc(newSize * sizeof(FULLEMPTY));
- memset(ptrTable->fullEmptyFlags, '\0', newSize * sizeof(FULLEMPTY));
+ ptrTable->fullEmptyFlags = (FULLEMPTY*) calloc(newSize, sizeof(FULLEMPTY));
ptrTable->capacity = newSize;
ptrTable->size = 0;
}
void
ReallocTable(PtrValueHashTable* ptrTable, Index newSize)
{
- if (newSize > ptrTable->capacity)
- {
- unsigned int i;
-
- PtrValueHashEntry* oldTable = ptrTable->table;
- FULLEMPTY* oldFlags = ptrTable->fullEmptyFlags;
- Index oldSize = ptrTable->size;
-
- /* allocate the new storage and flags and re-insert the old entries */
- InitializeTable(ptrTable, newSize);
- for (i=0; i < oldSize; ++i)
- Insert(ptrTable, oldTable[i].key, oldTable[i].value);
- assert(ptrTable->size == oldSize);
-
- free(oldTable);
- free(oldFlags);
- }
+ if (newSize <= ptrTable->capacity)
+ return;
+
+#ifndef NDEBUG
+ printf("\n***\n*** REALLOCATING SPACE FOR POINTER HASH TABLE.\n");
+ printf("*** oldSize = %ld, oldCapacity = %ld\n***\n\n",
+ (long) ptrTable->size, (long) ptrTable->capacity);
+#endif
+
+ unsigned int i;
+ PtrValueHashEntry* oldTable = ptrTable->table;
+ FULLEMPTY* oldFlags = ptrTable->fullEmptyFlags;
+ Index oldSize = ptrTable->size;
+ Index oldCapacity = ptrTable->capacity;
+
+ /* allocate the new storage and flags and re-insert the old entries */
+ InitializeTable(ptrTable, newSize);
+ for (i=0; i < oldCapacity; ++i)
+ if (oldFlags[i] == FULL)
+ Insert(ptrTable, oldTable[i].key, oldTable[i].value);
+
+ assert(ptrTable->size == oldSize && "Incorrect number of entries copied?");
+
+#ifndef NDEBUG
+ for (i=0; i < oldCapacity; ++i)
+ if (oldFlags[i] == FULL)
+ assert(LookupPtr(ptrTable, oldTable[i].key) == oldTable[i].value);
+#endif
+
+ free(oldTable);
+ free(oldFlags);
}
void
DeleteAtIndex(PtrValueHashTable* ptrTable, Index index)
{
assert(ptrTable->fullEmptyFlags[index] == FULL && "Deleting empty slot!");
- ptrTable->table[index].key = NULL;
- ptrTable->table[index].value = (Generic) NULL;
+ ptrTable->table[index].key = 0;
+ ptrTable->table[index].value = (Generic) 0;
ptrTable->fullEmptyFlags[index] = EMPTY;
ptrTable->size--;
}
if (numProbes == MAX_NUM_PROBES)
{ /* table is too full: reallocate and search again */
- ReallocTable(ptrTable, 1 + 2*ptrTable->capacity);
+ if (CurrentSizeEntry >= NUMPRIMES-1) {
+ fprintf(stderr, "Out of PRIME Numbers!!!");
+ abort();
+ }
+ ReallocTable(ptrTable, PRIMES[++CurrentSizeEntry]);
return FindIndex(ptrTable, ptr);
}
else
}
}
+/* Look up hash table using 'ptr' as the key. If an entry exists, return
+ * the value mapped to 'ptr'. If not, and if action==ENTER is specified,
+ * create a new entry with value 'value', but return 0 in any case.
+ */
Generic
-LookupOrInsertPtr(PtrValueHashTable* ptrTable, void* ptr, ACTION action)
+LookupOrInsertPtr(PtrValueHashTable* ptrTable, void* ptr, ACTION action,
+ Generic value)
{
Index index = FindIndex(ptrTable, ptr);
if (ptrTable->fullEmptyFlags[index] == FULL &&
return ptrTable->table[index].value;
/* Lookup failed: item is not in the table */
- if (action != ENTER)
- return (Generic) NULL;
-
- /* Insert item into the table and return its index */
- InsertAtIndex(ptrTable, ptr, (Generic) NULL, index);
- return (Generic) NULL;
-}
+ /* If action is ENTER, insert item into the table. Return 0 in any case. */
+ if (action == ENTER)
+ InsertAtIndex(ptrTable, ptr, value, index);
-/* Returns NULL if the item is not found. */
-/* void* LookupPtr(PtrValueHashTable* ptrTable, void* ptr) */
-#define LookupPtr(ptrTable, ptr) \
- LookupOrInsertPtr(ptrTable, ptr, FIND)
+ return (Generic) 0;
+}
void
Insert(PtrValueHashTable* ptrTable, void* ptr, Generic value)
*===---------------------------------------------------------------------===*/
PtrValueHashTable* SequenceNumberTable = NULL;
-Index INITIAL_SIZE = 1 << 18;
+#define INITIAL_SIZE (PRIMES[FIRSTENTRY])
#define MAX_NUM_SAVED 1024
assert(MAX_NUM_PROBES < INITIAL_SIZE+1 && "Initial size too small");
SequenceNumberTable = CreateTable(INITIAL_SIZE);
}
- seqnum = (SequenceNumber) LookupPtr(SequenceNumberTable, ptr);
- if (seqnum == 0)
- {
- Insert(SequenceNumberTable, ptr, ++count);
- seqnum = count;
- }
+ seqnum = (SequenceNumber)
+ LookupOrInsertPtr(SequenceNumberTable, ptr, ENTER, count+1);
+
+ if (seqnum == 0) /* new entry was created with value count+1 */
+ seqnum = ++count; /* so increment counter */
+
+ assert(seqnum <= count && "Invalid sequence number in table!");
return seqnum;
}
void
ReleasePointerSeqNum(char* ptr)
{ /* if a sequence number was assigned to this ptr, release it */
- SequenceNumber seqnum;
if (SequenceNumberTable != NULL)
Delete(SequenceNumberTable, ptr);
}
/* print sequence numbers out again to compare with (-r) and w/o release */
for (i=argc-1; i >= 0; --i)
for (j=0; argv[i][j]; ++j)
- printf("Sequence number for argc[%d][%d] (%c) = Hash(%p) = %d\n",
+ printf("Sequence number for argc[%d][%d] (%c) = %d\n",
i, j, argv[i][j], argv[i]+j, HashPointerToSeqNum(argv[i]+j));
return 0;
projects / oota-llvm.git / blobdiff