1 /*===-- tracelib.c - Runtime routines for tracing ---------------*- C++ -*-===*
3 * Runtime routines for supporting tracing of execution for code generated by
6 *===----------------------------------------------------------------------===*/
13 #include "llvm/Support/DataTypes.h"
15 /*===---------------------------------------------------------------------=====
17 *===---------------------------------------------------------------------===*/
19 /* use #defines until we have inlining */
20 typedef uintptr_t Index; /* type of keys, size for hash table */
21 typedef uint32_t Generic; /* type of values stored in table */
23 /* Index IntegerHashFunc(const Generic value, const Index size) */
24 #define IntegerHashFunc(value, size) \
25 ( ((((Index) value) << 3) ^ (((Index) value) >> 3)) % size )
27 /* Index IntegerRehashFunc(const Generic oldHashValue, const Index size) */
28 #define IntegerRehashFunc(oldHashValue, size) \
29 ((Index) ((oldHashValue+16) % size)) /* 16 is relatively prime to a Mersenne prime! */
31 /* Index PointerHashFunc(const void* value, const Index size) */
32 #define PointerHashFunc(value, size) \
33 IntegerHashFunc((Index) value, size)
35 /* Index PointerRehashFunc(const void* value, const Index size) */
36 #define PointerRehashFunc(value, size) \
37 IntegerRehashFunc((Index) value, size)
39 /*===---------------------------------------------------------------------=====
40 * POINTER-TO-GENERIC HASH TABLE.
41 * These should be moved to a separate location: HashTable.[ch]
42 *===---------------------------------------------------------------------===*/
44 typedef enum { FIND, ENTER } ACTION;
45 typedef char FULLEMPTY;
46 const FULLEMPTY EMPTY = '\0';
47 const FULLEMPTY FULL = '\1';
49 // List of primes closest to powers of 2 in [2^20 -- 2^30], obtained from
50 // http://www.utm.edu/research/primes/lists/2small/0bit.html.
51 // Use these as the successive sizes of the hash table.
54 const unsigned PRIMES[NUMPRIMES] = { (1<<20)-3, (1<<21)-9, (1<<22)-3, (1<<23)-15,
55 (1<<24)-3, (1<<25)-39, (1<<26)-5, (1<<27)-39,
56 (1<<28)-57, (1<<29)-3, (1<<30)-35 };
57 unsigned CurrentSizeEntry = FIRSTENTRY;
59 const unsigned MAX_NUM_PROBES = 4;
61 typedef struct PtrValueHashEntry_struct {
66 typedef struct PtrValueHashTable_struct {
67 PtrValueHashEntry* table;
68 FULLEMPTY* fullEmptyFlags;
74 static Generic LookupOrInsertPtr(PtrValueHashTable* ptrTable, void* ptr,
75 ACTION action, Generic value);
77 static void Insert(PtrValueHashTable* ptrTable, void* ptr, Generic value);
79 static void Delete(PtrValueHashTable* ptrTable, void* ptr);
81 /* Returns 0 if the item is not found. */
82 /* void* LookupPtr(PtrValueHashTable* ptrTable, void* ptr) */
83 #define LookupPtr(ptrTable, ptr) \
84 LookupOrInsertPtr(ptrTable, ptr, FIND, (Generic) 0)
87 InitializeTable(PtrValueHashTable* ptrTable, Index newSize)
89 ptrTable->table = (PtrValueHashEntry*) calloc(newSize,
90 sizeof(PtrValueHashEntry));
91 ptrTable->fullEmptyFlags = (FULLEMPTY*) calloc(newSize, sizeof(FULLEMPTY));
92 ptrTable->capacity = newSize;
97 CreateTable(Index initialSize)
99 PtrValueHashTable* ptrTable =
100 (PtrValueHashTable*) malloc(sizeof(PtrValueHashTable));
101 InitializeTable(ptrTable, initialSize);
106 ReallocTable(PtrValueHashTable* ptrTable, Index newSize)
108 if (newSize <= ptrTable->capacity)
112 printf("\n***\n*** REALLOCATING SPACE FOR POINTER HASH TABLE.\n");
113 printf("*** oldSize = %ld, oldCapacity = %ld\n***\n\n",
114 (long) ptrTable->size, (long) ptrTable->capacity);
118 PtrValueHashEntry* oldTable = ptrTable->table;
119 FULLEMPTY* oldFlags = ptrTable->fullEmptyFlags;
120 Index oldSize = ptrTable->size;
121 Index oldCapacity = ptrTable->capacity;
123 /* allocate the new storage and flags and re-insert the old entries */
124 InitializeTable(ptrTable, newSize);
125 for (i=0; i < oldCapacity; ++i)
126 if (oldFlags[i] == FULL)
127 Insert(ptrTable, oldTable[i].key, oldTable[i].value);
129 assert(ptrTable->size == oldSize && "Incorrect number of entries copied?");
132 for (i=0; i < oldCapacity; ++i)
133 if (oldFlags[i] == FULL)
134 assert(LookupPtr(ptrTable, oldTable[i].key) == oldTable[i].value);
142 DeleteTable(PtrValueHashTable* ptrTable)
144 free(ptrTable->table);
145 free(ptrTable->fullEmptyFlags);
146 memset(ptrTable, '\0', sizeof(PtrValueHashTable));
151 InsertAtIndex(PtrValueHashTable* ptrTable, void* ptr, Generic value, Index index)
153 assert(ptrTable->fullEmptyFlags[index] == EMPTY && "Slot is in use!");
154 ptrTable->table[index].key = ptr;
155 ptrTable->table[index].value = value;
156 ptrTable->fullEmptyFlags[index] = FULL;
161 DeleteAtIndex(PtrValueHashTable* ptrTable, Index index)
163 assert(ptrTable->fullEmptyFlags[index] == FULL && "Deleting empty slot!");
164 ptrTable->table[index].key = 0;
165 ptrTable->table[index].value = (Generic) 0;
166 ptrTable->fullEmptyFlags[index] = EMPTY;
171 FindIndex(PtrValueHashTable* ptrTable, void* ptr)
173 unsigned numProbes = 1;
174 Index index = PointerHashFunc(ptr, ptrTable->capacity);
175 if (ptrTable->fullEmptyFlags[index] == FULL)
177 if (ptrTable->table[index].key == ptr)
180 /* First lookup failed on non-empty slot: probe further */
181 while (numProbes < MAX_NUM_PROBES)
183 index = PointerRehashFunc(index, ptrTable->capacity);
184 if (ptrTable->fullEmptyFlags[index] == EMPTY)
186 else if (ptrTable->table[index].key == ptr)
192 /* Lookup failed: item is not in the table. */
193 /* If last slot is empty, use that slot. */
194 /* Otherwise, table must have been reallocated, so search again. */
196 if (numProbes == MAX_NUM_PROBES)
197 { /* table is too full: reallocate and search again */
198 if (CurrentSizeEntry >= NUMPRIMES-1) {
199 fprintf(stderr, "Out of PRIME Numbers!!!");
202 ReallocTable(ptrTable, PRIMES[++CurrentSizeEntry]);
203 return FindIndex(ptrTable, ptr);
207 assert(ptrTable->fullEmptyFlags[index] == EMPTY &&
208 "Stopped before finding an empty slot and before MAX probes!");
213 /* Look up hash table using 'ptr' as the key. If an entry exists, return
214 * the value mapped to 'ptr'. If not, and if action==ENTER is specified,
215 * create a new entry with value 'value', but return 0 in any case.
218 LookupOrInsertPtr(PtrValueHashTable* ptrTable, void* ptr, ACTION action,
221 Index index = FindIndex(ptrTable, ptr);
222 if (ptrTable->fullEmptyFlags[index] == FULL &&
223 ptrTable->table[index].key == ptr)
224 return ptrTable->table[index].value;
226 /* Lookup failed: item is not in the table */
227 /* If action is ENTER, insert item into the table. Return 0 in any case. */
229 InsertAtIndex(ptrTable, ptr, value, index);
235 Insert(PtrValueHashTable* ptrTable, void* ptr, Generic value)
237 Index index = FindIndex(ptrTable, ptr);
238 assert(ptrTable->fullEmptyFlags[index] == EMPTY &&
239 "ptr is already in the table: delete it first!");
240 InsertAtIndex(ptrTable, ptr, value, index);
244 Delete(PtrValueHashTable* ptrTable, void* ptr)
246 Index index = FindIndex(ptrTable, ptr);
247 if (ptrTable->fullEmptyFlags[index] == FULL &&
248 ptrTable->table[index].key == ptr)
250 DeleteAtIndex(ptrTable, index);
254 /*===---------------------------------------------------------------------=====
255 * RUNTIME ROUTINES TO MAP POINTERS TO SEQUENCE NUMBERS
256 *===---------------------------------------------------------------------===*/
258 PtrValueHashTable* SequenceNumberTable = NULL;
259 #define INITIAL_SIZE (PRIMES[FIRSTENTRY])
261 #define MAX_NUM_SAVED 1024
263 typedef struct PointerSet_struct {
264 char* savedPointers[MAX_NUM_SAVED]; /* 1024 alloca'd ptrs shd suffice */
265 unsigned int numSaved;
266 struct PointerSet_struct* nextOnStack; /* implement a cheap stack */
269 PointerSet* topOfStack = NULL;
272 HashPointerToSeqNum(char* ptr)
274 static SequenceNumber count = 0;
275 SequenceNumber seqnum;
276 if (SequenceNumberTable == NULL) {
277 assert(MAX_NUM_PROBES < INITIAL_SIZE+1 && "Initial size too small");
278 SequenceNumberTable = CreateTable(INITIAL_SIZE);
280 seqnum = (SequenceNumber)
281 LookupOrInsertPtr(SequenceNumberTable, ptr, ENTER, count+1);
283 if (seqnum == 0) /* new entry was created with value count+1 */
284 seqnum = ++count; /* so increment counter */
286 assert(seqnum <= count && "Invalid sequence number in table!");
291 ReleasePointerSeqNum(char* ptr)
292 { /* if a sequence number was assigned to this ptr, release it */
293 if (SequenceNumberTable != NULL)
294 Delete(SequenceNumberTable, ptr);
300 PointerSet* newSet = (PointerSet*) malloc(sizeof(PointerSet));
301 newSet->numSaved = 0;
302 newSet->nextOnStack = topOfStack;
310 assert(topOfStack != NULL && "popping from empty stack!");
312 topOfStack = oldSet->nextOnStack;
313 assert(oldSet->numSaved == 0);
317 /* free the pointers! */
319 ReleaseRecordedPointers(char* savedPointers[MAX_NUM_SAVED],
320 unsigned int numSaved)
323 for (i=0; i < topOfStack->numSaved; ++i)
324 ReleasePointerSeqNum(topOfStack->savedPointers[i]);
328 ReleasePointersPopSet()
330 ReleaseRecordedPointers(topOfStack->savedPointers, topOfStack->numSaved);
331 topOfStack->numSaved = 0;
336 RecordPointer(char* ptr)
337 { /* record pointers for release later */
338 if (topOfStack->numSaved == MAX_NUM_SAVED) {
339 printf("***\n*** WARNING: OUT OF ROOM FOR SAVED POINTERS."
340 " ALL POINTERS ARE BEING FREED.\n"
341 "*** THE SEQUENCE NUMBERS OF SAVED POINTERS WILL CHANGE!\n*** \n");
342 ReleaseRecordedPointers(topOfStack->savedPointers, topOfStack->numSaved);
343 topOfStack->numSaved = 0;
345 topOfStack->savedPointers[topOfStack->numSaved++] = ptr;
348 /*===---------------------------------------------------------------------=====
349 * TEST DRIVER FOR INSTRUMENTATION LIBRARY
350 *===---------------------------------------------------------------------===*/
352 #ifndef TEST_INSTRLIB
353 #undef TEST_INSTRLIB /* #define this to turn on by default */
358 main(int argc, char** argv)
363 INITIAL_SIZE = 5; /* start with small table to test realloc's*/
365 if (argc > 1 && ! strcmp(argv[1], "-r"))
371 for (i=0; i < argc; ++i)
372 for (j=0; argv[i][j]; ++j)
374 printf("Sequence number for argc[%d][%d] (%c) = Hash(%p) = %d\n",
375 i, j, argv[i][j], argv[i]+j, HashPointerToSeqNum(argv[i]+j));
378 RecordPointer(argv[i]+j);
382 ReleasePointersPopSet();
384 /* print sequence numbers out again to compare with (-r) and w/o release */
385 for (i=argc-1; i >= 0; --i)
386 for (j=0; argv[i][j]; ++j)
387 printf("Sequence number for argc[%d][%d] (%c) = %d\n",
388 i, j, argv[i][j], argv[i]+j, HashPointerToSeqNum(argv[i]+j));