1 /*===-- Libraries/tracelib.c - Runtime routines for tracing -----*- C++ -*--===
3 * Runtime routines for supporting tracing of execution
4 * for code generated by LLVM.
6 *===---------------------------------------------------------------------===*/
15 /*===---------------------------------------------------------------------=====
17 *===---------------------------------------------------------------------===*/
19 /* use #defines until we have inlining */
21 typedef int64_t Generic;
22 typedef uint64_t Index;
23 typedef uint64_t Pointer;
25 /* Index IntegerHashFunc(const Generic value, const Index size) */
26 #define IntegerHashFunc(value, size) \
29 /* Index IntegerRehashFunc(const Generic oldHashValue, const Index size) */
30 #define IntegerRehashFunc(oldHashValue, size) \
31 ((oldHashValue+16) % size) /* 16 is relatively prime to a Mersenne prime! */
33 /* Index PointerHashFunc(const void* value, const Index size) */
34 #define PointerHashFunc(value, size) \
35 IntegerHashFunc((Pointer) value, size)
37 /* Index PointerRehashFunc(const void* value, const Index size) */
38 #define PointerRehashFunc(value, size) \
39 IntegerRehashFunc((Pointer) value, size)
42 /*===---------------------------------------------------------------------=====
43 * POINTER-TO-GENERIC HASH TABLE.
44 * These should be moved to a separate location: HashTable.[ch]
45 *===---------------------------------------------------------------------===*/
47 typedef enum { FIND, ENTER } ACTION;
48 typedef char FULLEMPTY;
49 const FULLEMPTY EMPTY = '\0';
50 const FULLEMPTY FULL = '\1';
52 const uint MAX_NUM_PROBES = 4;
54 typedef struct PtrValueHashEntry_struct {
59 typedef struct PtrValueHashTable_struct {
60 PtrValueHashEntry* table;
61 FULLEMPTY* fullEmptyFlags;
67 extern Generic LookupOrInsertPtr(PtrValueHashTable* ptrTable,
68 void* ptr, ACTION action);
70 extern void Insert(PtrValueHashTable* ptrTable, void* ptr, Generic value);
72 extern void Delete(PtrValueHashTable* ptrTable, void* ptr);
76 InitializeTable(PtrValueHashTable* ptrTable, Index newSize)
78 ptrTable->table = (PtrValueHashEntry*) malloc(newSize *
79 sizeof(PtrValueHashEntry));
80 ptrTable->fullEmptyFlags = (FULLEMPTY*) malloc(newSize * sizeof(FULLEMPTY));
81 memset(ptrTable->fullEmptyFlags, '\0', newSize * sizeof(FULLEMPTY));
82 ptrTable->capacity = newSize;
87 CreateTable(Index initialSize)
89 PtrValueHashTable* ptrTable =
90 (PtrValueHashTable*) malloc(sizeof(PtrValueHashTable));
91 InitializeTable(ptrTable, initialSize);
96 ReallocTable(PtrValueHashTable* ptrTable, Index newSize)
98 if (newSize > ptrTable->capacity)
102 PtrValueHashEntry* oldTable = ptrTable->table;
103 FULLEMPTY* oldFlags = ptrTable->fullEmptyFlags;
104 Index oldSize = ptrTable->size;
106 /* allocate the new storage and flags and re-insert the old entries */
107 InitializeTable(ptrTable, newSize);
108 for (i=0; i < oldSize; ++i)
109 Insert(ptrTable, oldTable[i].key, oldTable[i].value);
110 assert(ptrTable->size == oldSize);
118 DeleteTable(PtrValueHashTable* ptrTable)
120 free(ptrTable->table);
121 free(ptrTable->fullEmptyFlags);
122 memset(ptrTable, '\0', sizeof(PtrValueHashTable));
127 InsertAtIndex(PtrValueHashTable* ptrTable, void* ptr, Generic value, Index index)
129 assert(ptrTable->fullEmptyFlags[index] == EMPTY && "Slot is in use!");
130 ptrTable->table[index].key = ptr;
131 ptrTable->table[index].value = value;
132 ptrTable->fullEmptyFlags[index] = FULL;
137 DeleteAtIndex(PtrValueHashTable* ptrTable, Index index)
139 assert(ptrTable->fullEmptyFlags[index] == FULL && "Deleting empty slot!");
140 ptrTable->table[index].key = NULL;
141 ptrTable->table[index].value = (Generic) NULL;
142 ptrTable->fullEmptyFlags[index] = EMPTY;
147 FindIndex(PtrValueHashTable* ptrTable, void* ptr)
150 Index index = PointerHashFunc(ptr, ptrTable->capacity);
151 if (ptrTable->fullEmptyFlags[index] == FULL)
153 if (ptrTable->table[index].key == ptr)
156 /* First lookup failed on non-empty slot: probe further */
157 while (numProbes < MAX_NUM_PROBES)
159 index = PointerRehashFunc(index, ptrTable->capacity);
160 if (ptrTable->fullEmptyFlags[index] == EMPTY)
162 else if (ptrTable->table[index].key == ptr)
168 /* Lookup failed: item is not in the table. */
169 /* If last slot is empty, use that slot. */
170 /* Otherwise, table must have been reallocated, so search again. */
172 if (numProbes == MAX_NUM_PROBES)
173 { /* table is too full: reallocate and search again */
174 ReallocTable(ptrTable, 1 + 2*ptrTable->capacity);
175 return FindIndex(ptrTable, ptr);
179 assert(ptrTable->fullEmptyFlags[index] == EMPTY &&
180 "Stopped before finding an empty slot and before MAX probes!");
186 LookupOrInsertPtr(PtrValueHashTable* ptrTable, void* ptr, ACTION action)
188 Index index = FindIndex(ptrTable, ptr);
189 if (ptrTable->fullEmptyFlags[index] == FULL &&
190 ptrTable->table[index].key == ptr)
191 return ptrTable->table[index].value;
193 /* Lookup failed: item is not in the table */
195 return (Generic) NULL;
197 /* Insert item into the table and return its index */
198 InsertAtIndex(ptrTable, ptr, (Generic) NULL, index);
199 return (Generic) NULL;
202 /* Returns NULL if the item is not found. */
203 /* void* LookupPtr(PtrValueHashTable* ptrTable, void* ptr) */
204 #define LookupPtr(ptrTable, ptr) \
205 LookupOrInsertPtr(ptrTable, ptr, FIND)
208 Insert(PtrValueHashTable* ptrTable, void* ptr, Generic value)
210 Index index = FindIndex(ptrTable, ptr);
211 assert(ptrTable->fullEmptyFlags[index] == EMPTY &&
212 "ptr is already in the table: delete it first!");
213 InsertAtIndex(ptrTable, ptr, value, index);
217 Delete(PtrValueHashTable* ptrTable, void* ptr)
219 Index index = FindIndex(ptrTable, ptr);
220 if (ptrTable->fullEmptyFlags[index] == FULL &&
221 ptrTable->table[index].key == ptr)
223 DeleteAtIndex(ptrTable, index);
227 /*===---------------------------------------------------------------------=====
228 * RUNTIME ROUTINES TO MAP POINTERS TO SEQUENCE NUMBERS
229 *===---------------------------------------------------------------------===*/
231 PtrValueHashTable* SequenceNumberTable = NULL;
232 Index INITIAL_SIZE = 1 << 18;
234 #define MAX_NUM_SAVED 1024
236 typedef struct PointerSet_struct {
237 char* savedPointers[MAX_NUM_SAVED]; /* 1024 alloca'd ptrs shd suffice */
238 unsigned int numSaved;
239 struct PointerSet_struct* nextOnStack; /* implement a cheap stack */
242 PointerSet* topOfStack = NULL;
245 HashPointerToSeqNum(char* ptr)
247 static SequenceNumber count = 0;
248 SequenceNumber seqnum;
249 if (SequenceNumberTable == NULL) {
250 assert(MAX_NUM_PROBES < INITIAL_SIZE+1 && "Initial size too small");
251 SequenceNumberTable = CreateTable(INITIAL_SIZE);
253 seqnum = (SequenceNumber) LookupPtr(SequenceNumberTable, ptr);
256 Insert(SequenceNumberTable, ptr, ++count);
263 ReleasePointerSeqNum(char* ptr)
264 { /* if a sequence number was assigned to this ptr, release it */
265 if (SequenceNumberTable != NULL)
266 Delete(SequenceNumberTable, ptr);
272 PointerSet* newSet = (PointerSet*) malloc(sizeof(PointerSet));
273 newSet->numSaved = 0;
274 newSet->nextOnStack = topOfStack;
282 assert(topOfStack != NULL && "popping from empty stack!");
284 topOfStack = oldSet->nextOnStack;
285 assert(oldSet->numSaved == 0);
289 /* free the pointers! */
291 ReleaseRecordedPointers(char* savedPointers[MAX_NUM_SAVED],
292 unsigned int numSaved)
295 for (i=0; i < topOfStack->numSaved; ++i)
296 ReleasePointerSeqNum(topOfStack->savedPointers[i]);
300 ReleasePointersPopSet()
302 ReleaseRecordedPointers(topOfStack->savedPointers, topOfStack->numSaved);
303 topOfStack->numSaved = 0;
308 RecordPointer(char* ptr)
309 { /* record pointers for release later */
310 if (topOfStack->numSaved == MAX_NUM_SAVED) {
311 printf("***\n*** WARNING: OUT OF ROOM FOR SAVED POINTERS."
312 " ALL POINTERS ARE BEING FREED.\n"
313 "*** THE SEQUENCE NUMBERS OF SAVED POINTERS WILL CHANGE!\n*** \n");
314 ReleaseRecordedPointers(topOfStack->savedPointers, topOfStack->numSaved);
315 topOfStack->numSaved = 0;
317 topOfStack->savedPointers[topOfStack->numSaved++] = ptr;
320 /*===---------------------------------------------------------------------=====
321 * TEST DRIVER FOR INSTRUMENTATION LIBRARY
322 *===---------------------------------------------------------------------===*/
324 #ifndef TEST_INSTRLIB
325 #undef TEST_INSTRLIB /* #define this to turn on by default */
330 main(int argc, char** argv)
335 INITIAL_SIZE = 5; /* start with small table to test realloc's*/
337 if (argc > 1 && ! strcmp(argv[1], "-r"))
343 for (i=0; i < argc; ++i)
344 for (j=0; argv[i][j]; ++j)
346 printf("Sequence number for argc[%d][%d] (%c) = Hash(%p) = %d\n",
347 i, j, argv[i][j], argv[i]+j, HashPointerToSeqNum(argv[i]+j));
350 RecordPointer(argv[i]+j);
354 ReleasePointersPopSet();
356 /* print sequence numbers out again to compare with (-r) and w/o release */
357 for (i=argc-1; i >= 0; --i)
358 for (j=0; argv[i][j]; ++j)
359 printf("Sequence number for argc[%d][%d] (%c) = Hash(%p) = %d\n",
360 i, j, argv[i][j], argv[i]+j, HashPointerToSeqNum(argv[i]+j));