1 /*===-- Libraries/tracelib.c - Runtime routines for tracing -----*- C++ -*--===
3 * Runtime routines for supporting tracing of execution
4 * for code generated by LLVM.
6 *===---------------------------------------------------------------------===*/
17 /*===---------------------------------------------------------------------=====
19 *===---------------------------------------------------------------------===*/
21 /* use #defines until we have inlining */
23 typedef int64_t Generic;
24 typedef uint64_t Index;
25 typedef uint64_t Pointer;
27 /* Index IntegerHashFunc(const Generic value, const Index size) */
28 #define IntegerHashFunc(value, size) \
29 (((value << 3) ^ (value >> 3)) % size)
31 /* Index IntegerRehashFunc(const Generic oldHashValue, const Index size) */
32 #define IntegerRehashFunc(oldHashValue, size) \
33 ((oldHashValue+16) % size) /* 16 is relatively prime to a Mersenne prime! */
35 /* Index PointerHashFunc(const void* value, const Index size) */
36 #define PointerHashFunc(value, size) \
37 IntegerHashFunc((Pointer) value, size)
39 /* Index PointerRehashFunc(const void* value, const Index size) */
40 #define PointerRehashFunc(value, size) \
41 IntegerRehashFunc((Pointer) value, size)
44 /*===---------------------------------------------------------------------=====
45 * POINTER-TO-GENERIC HASH TABLE.
46 * These should be moved to a separate location: HashTable.[ch]
47 *===---------------------------------------------------------------------===*/
49 typedef enum { FIND, ENTER } ACTION;
50 typedef char FULLEMPTY;
51 const FULLEMPTY EMPTY = '\0';
52 const FULLEMPTY FULL = '\1';
54 const uint MAX_NUM_PROBES = 4;
56 typedef struct PtrValueHashEntry_struct {
61 typedef struct PtrValueHashTable_struct {
62 PtrValueHashEntry* table;
63 FULLEMPTY* fullEmptyFlags;
69 extern Generic LookupOrInsertPtr(PtrValueHashTable* ptrTable,
70 void* ptr, ACTION action);
72 extern void Insert(PtrValueHashTable* ptrTable, void* ptr, Generic value);
74 extern void Delete(PtrValueHashTable* ptrTable, void* ptr);
78 InitializeTable(PtrValueHashTable* ptrTable, Index newSize)
80 ptrTable->table = (PtrValueHashEntry*) calloc(newSize,
81 sizeof(PtrValueHashEntry));
82 ptrTable->fullEmptyFlags = (FULLEMPTY*) calloc(newSize, sizeof(FULLEMPTY));
83 ptrTable->capacity = newSize;
88 CreateTable(Index initialSize)
90 PtrValueHashTable* ptrTable =
91 (PtrValueHashTable*) malloc(sizeof(PtrValueHashTable));
92 InitializeTable(ptrTable, initialSize);
97 ReallocTable(PtrValueHashTable* ptrTable, Index newSize)
99 if (newSize <= ptrTable->capacity)
103 printf("\n***\n*** WARNING: REALLOCATING SPACE FOR POINTER HASH TABLE.\n");
104 printf("*** oldSize = %ld, oldCapacity = %ld\n***\n\n",
105 ptrTable->size, ptrTable->capacity);
106 printf("*** NEW SEQUENCE NUMBER FOR A POINTER WILL PROBABLY NOT MATCH ");
107 printf(" THE OLD ONE!\n***\n\n");
111 PtrValueHashEntry* oldTable = ptrTable->table;
112 FULLEMPTY* oldFlags = ptrTable->fullEmptyFlags;
113 Index oldSize = ptrTable->size;
114 Index oldCapacity = ptrTable->capacity;
116 /* allocate the new storage and flags and re-insert the old entries */
117 InitializeTable(ptrTable, newSize);
118 memcpy(ptrTable->table, oldTable,
119 oldCapacity * sizeof(PtrValueHashEntry));
120 memcpy(ptrTable->fullEmptyFlags, oldFlags,
121 oldCapacity * sizeof(FULLEMPTY));
122 ptrTable->size = oldSize;
125 for (i=0; i < oldCapacity; ++i) {
126 assert(ptrTable->fullEmptyFlags[i] == oldFlags[i]);
127 assert(ptrTable->table[i].key == oldTable[i].key);
128 assert(ptrTable->table[i].value == oldTable[i].value);
137 DeleteTable(PtrValueHashTable* ptrTable)
139 free(ptrTable->table);
140 free(ptrTable->fullEmptyFlags);
141 memset(ptrTable, '\0', sizeof(PtrValueHashTable));
146 InsertAtIndex(PtrValueHashTable* ptrTable, void* ptr, Generic value, Index index)
148 assert(ptrTable->fullEmptyFlags[index] == EMPTY && "Slot is in use!");
149 ptrTable->table[index].key = ptr;
150 ptrTable->table[index].value = value;
151 ptrTable->fullEmptyFlags[index] = FULL;
156 DeleteAtIndex(PtrValueHashTable* ptrTable, Index index)
158 assert(ptrTable->fullEmptyFlags[index] == FULL && "Deleting empty slot!");
159 ptrTable->table[index].key = NULL;
160 ptrTable->table[index].value = (Generic) NULL;
161 ptrTable->fullEmptyFlags[index] = EMPTY;
166 FindIndex(PtrValueHashTable* ptrTable, void* ptr)
169 Index index = PointerHashFunc(ptr, ptrTable->capacity);
170 if (ptrTable->fullEmptyFlags[index] == FULL)
172 if (ptrTable->table[index].key == ptr)
175 /* First lookup failed on non-empty slot: probe further */
176 while (numProbes < MAX_NUM_PROBES)
178 index = PointerRehashFunc(index, ptrTable->capacity);
179 if (ptrTable->fullEmptyFlags[index] == EMPTY)
181 else if (ptrTable->table[index].key == ptr)
187 /* Lookup failed: item is not in the table. */
188 /* If last slot is empty, use that slot. */
189 /* Otherwise, table must have been reallocated, so search again. */
191 if (numProbes == MAX_NUM_PROBES)
192 { /* table is too full: reallocate and search again */
193 ReallocTable(ptrTable, 1 + 2*ptrTable->capacity);
194 return FindIndex(ptrTable, ptr);
198 assert(ptrTable->fullEmptyFlags[index] == EMPTY &&
199 "Stopped before finding an empty slot and before MAX probes!");
205 LookupOrInsertPtr(PtrValueHashTable* ptrTable, void* ptr, ACTION action)
207 Index index = FindIndex(ptrTable, ptr);
208 if (ptrTable->fullEmptyFlags[index] == FULL &&
209 ptrTable->table[index].key == ptr)
210 return ptrTable->table[index].value;
212 /* Lookup failed: item is not in the table */
214 return (Generic) NULL;
216 /* Insert item into the table and return its index */
217 InsertAtIndex(ptrTable, ptr, (Generic) NULL, index);
218 return (Generic) NULL;
221 /* Returns NULL if the item is not found. */
222 /* void* LookupPtr(PtrValueHashTable* ptrTable, void* ptr) */
223 #define LookupPtr(ptrTable, ptr) \
224 LookupOrInsertPtr(ptrTable, ptr, FIND)
227 Insert(PtrValueHashTable* ptrTable, void* ptr, Generic value)
229 Index index = FindIndex(ptrTable, ptr);
230 assert(ptrTable->fullEmptyFlags[index] == EMPTY &&
231 "ptr is already in the table: delete it first!");
232 InsertAtIndex(ptrTable, ptr, value, index);
236 Delete(PtrValueHashTable* ptrTable, void* ptr)
238 Index index = FindIndex(ptrTable, ptr);
239 if (ptrTable->fullEmptyFlags[index] == FULL &&
240 ptrTable->table[index].key == ptr)
242 DeleteAtIndex(ptrTable, index);
246 /*===---------------------------------------------------------------------=====
247 * RUNTIME ROUTINES TO MAP POINTERS TO SEQUENCE NUMBERS
248 *===---------------------------------------------------------------------===*/
250 PtrValueHashTable* SequenceNumberTable = NULL;
251 Index INITIAL_SIZE = 1 << 22;
253 #define MAX_NUM_SAVED 1024
255 typedef struct PointerSet_struct {
256 char* savedPointers[MAX_NUM_SAVED]; /* 1024 alloca'd ptrs shd suffice */
257 unsigned int numSaved;
258 struct PointerSet_struct* nextOnStack; /* implement a cheap stack */
261 PointerSet* topOfStack = NULL;
264 HashPointerToSeqNum(char* ptr)
266 static SequenceNumber count = 0;
267 SequenceNumber seqnum;
268 if (SequenceNumberTable == NULL) {
269 assert(MAX_NUM_PROBES < INITIAL_SIZE+1 && "Initial size too small");
270 SequenceNumberTable = CreateTable(INITIAL_SIZE);
272 seqnum = (SequenceNumber) LookupPtr(SequenceNumberTable, ptr);
275 Insert(SequenceNumberTable, ptr, ++count);
282 ReleasePointerSeqNum(char* ptr)
283 { /* if a sequence number was assigned to this ptr, release it */
284 if (SequenceNumberTable != NULL)
285 Delete(SequenceNumberTable, ptr);
291 PointerSet* newSet = (PointerSet*) malloc(sizeof(PointerSet));
292 newSet->numSaved = 0;
293 newSet->nextOnStack = topOfStack;
301 assert(topOfStack != NULL && "popping from empty stack!");
303 topOfStack = oldSet->nextOnStack;
304 assert(oldSet->numSaved == 0);
308 /* free the pointers! */
310 ReleaseRecordedPointers(char* savedPointers[MAX_NUM_SAVED],
311 unsigned int numSaved)
314 for (i=0; i < topOfStack->numSaved; ++i)
315 ReleasePointerSeqNum(topOfStack->savedPointers[i]);
319 ReleasePointersPopSet()
321 ReleaseRecordedPointers(topOfStack->savedPointers, topOfStack->numSaved);
322 topOfStack->numSaved = 0;
327 RecordPointer(char* ptr)
328 { /* record pointers for release later */
329 if (topOfStack->numSaved == MAX_NUM_SAVED) {
330 printf("***\n*** WARNING: OUT OF ROOM FOR SAVED POINTERS."
331 " ALL POINTERS ARE BEING FREED.\n"
332 "*** THE SEQUENCE NUMBERS OF SAVED POINTERS WILL CHANGE!\n*** \n");
333 ReleaseRecordedPointers(topOfStack->savedPointers, topOfStack->numSaved);
334 topOfStack->numSaved = 0;
336 topOfStack->savedPointers[topOfStack->numSaved++] = ptr;
339 /*===---------------------------------------------------------------------=====
340 * TEST DRIVER FOR INSTRUMENTATION LIBRARY
341 *===---------------------------------------------------------------------===*/
343 #ifndef TEST_INSTRLIB
344 #undef TEST_INSTRLIB /* #define this to turn on by default */
349 main(int argc, char** argv)
354 INITIAL_SIZE = 5; /* start with small table to test realloc's*/
356 if (argc > 1 && ! strcmp(argv[1], "-r"))
362 for (i=0; i < argc; ++i)
363 for (j=0; argv[i][j]; ++j)
365 printf("Sequence number for argc[%d][%d] (%c) = Hash(%p) = %d\n",
366 i, j, argv[i][j], argv[i]+j, HashPointerToSeqNum(argv[i]+j));
369 RecordPointer(argv[i]+j);
373 ReleasePointersPopSet();
375 /* print sequence numbers out again to compare with (-r) and w/o release */
376 for (i=argc-1; i >= 0; --i)
377 for (j=0; argv[i][j]; ++j)
378 printf("Sequence number for argc[%d][%d] (%c) = Hash(%p) = %d\n",
379 i, j, argv[i][j], argv[i]+j, HashPointerToSeqNum(argv[i]+j));