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 */
24 typedef uint32_t Pointer; /* int representation of a pointer */
26 typedef uint64_t Pointer; /* int representation of a pointer */
28 typedef uint32_t Index; /* type of index/size for hash table */
29 typedef uint32_t Generic; /* type of values stored in table */
31 /* Index IntegerHashFunc(const Generic value, const Index size) */
32 #define IntegerHashFunc(value, size) \
33 ( ((((Index) value) << 3) ^ (((Index) value) >> 3)) % size )
35 /* Index IntegerRehashFunc(const Generic oldHashValue, const Index size) */
36 #define IntegerRehashFunc(oldHashValue, size) \
37 ((Index) ((oldHashValue+16) % size)) /* 16 is relatively prime to a Mersenne prime! */
39 /* Index PointerHashFunc(const void* value, const Index size) */
40 #define PointerHashFunc(value, size) \
41 IntegerHashFunc((Index) value, size)
43 /* Index PointerRehashFunc(const void* value, const Index size) */
44 #define PointerRehashFunc(value, size) \
45 IntegerRehashFunc((Index) value, size)
48 /*===---------------------------------------------------------------------=====
49 * POINTER-TO-GENERIC HASH TABLE.
50 * These should be moved to a separate location: HashTable.[ch]
51 *===---------------------------------------------------------------------===*/
53 typedef enum { FIND, ENTER } ACTION;
54 typedef char FULLEMPTY;
55 const FULLEMPTY EMPTY = '\0';
56 const FULLEMPTY FULL = '\1';
58 const uint MAX_NUM_PROBES = 4;
60 typedef struct PtrValueHashEntry_struct {
65 typedef struct PtrValueHashTable_struct {
66 PtrValueHashEntry* table;
67 FULLEMPTY* fullEmptyFlags;
73 extern Generic LookupOrInsertPtr(PtrValueHashTable* ptrTable,
74 void* ptr, ACTION action);
76 extern void Insert(PtrValueHashTable* ptrTable, void* ptr, Generic value);
78 extern void Delete(PtrValueHashTable* ptrTable, void* ptr);
82 InitializeTable(PtrValueHashTable* ptrTable, Index newSize)
84 ptrTable->table = (PtrValueHashEntry*) calloc(newSize,
85 sizeof(PtrValueHashEntry));
86 ptrTable->fullEmptyFlags = (FULLEMPTY*) calloc(newSize, sizeof(FULLEMPTY));
87 ptrTable->capacity = newSize;
92 CreateTable(Index initialSize)
94 PtrValueHashTable* ptrTable =
95 (PtrValueHashTable*) malloc(sizeof(PtrValueHashTable));
96 InitializeTable(ptrTable, initialSize);
101 ReallocTable(PtrValueHashTable* ptrTable, Index newSize)
103 if (newSize <= ptrTable->capacity)
107 printf("\n***\n*** WARNING: REALLOCATING SPACE FOR POINTER HASH TABLE.\n");
108 printf("*** oldSize = %d, oldCapacity = %d\n***\n\n",
109 ptrTable->size, ptrTable->capacity);
110 printf("*** NEW SEQUENCE NUMBER FOR A POINTER WILL PROBABLY NOT MATCH ");
111 printf(" THE OLD ONE!\n***\n\n");
115 PtrValueHashEntry* oldTable = ptrTable->table;
116 FULLEMPTY* oldFlags = ptrTable->fullEmptyFlags;
117 Index oldSize = ptrTable->size;
118 Index oldCapacity = ptrTable->capacity;
120 /* allocate the new storage and flags and re-insert the old entries */
121 InitializeTable(ptrTable, newSize);
122 memcpy(ptrTable->table, oldTable,
123 oldCapacity * sizeof(PtrValueHashEntry));
124 memcpy(ptrTable->fullEmptyFlags, oldFlags,
125 oldCapacity * sizeof(FULLEMPTY));
126 ptrTable->size = oldSize;
129 for (i=0; i < oldCapacity; ++i) {
130 assert(ptrTable->fullEmptyFlags[i] == oldFlags[i]);
131 assert(ptrTable->table[i].key == oldTable[i].key);
132 assert(ptrTable->table[i].value == oldTable[i].value);
141 DeleteTable(PtrValueHashTable* ptrTable)
143 free(ptrTable->table);
144 free(ptrTable->fullEmptyFlags);
145 memset(ptrTable, '\0', sizeof(PtrValueHashTable));
150 InsertAtIndex(PtrValueHashTable* ptrTable, void* ptr, Generic value, Index index)
152 assert(ptrTable->fullEmptyFlags[index] == EMPTY && "Slot is in use!");
153 ptrTable->table[index].key = ptr;
154 ptrTable->table[index].value = value;
155 ptrTable->fullEmptyFlags[index] = FULL;
160 DeleteAtIndex(PtrValueHashTable* ptrTable, Index index)
162 assert(ptrTable->fullEmptyFlags[index] == FULL && "Deleting empty slot!");
163 ptrTable->table[index].key = NULL;
164 ptrTable->table[index].value = (Generic) NULL;
165 ptrTable->fullEmptyFlags[index] = EMPTY;
170 FindIndex(PtrValueHashTable* ptrTable, void* ptr)
173 Index index = PointerHashFunc(ptr, ptrTable->capacity);
174 if (ptrTable->fullEmptyFlags[index] == FULL)
176 if (ptrTable->table[index].key == ptr)
179 /* First lookup failed on non-empty slot: probe further */
180 while (numProbes < MAX_NUM_PROBES)
182 index = PointerRehashFunc(index, ptrTable->capacity);
183 if (ptrTable->fullEmptyFlags[index] == EMPTY)
185 else if (ptrTable->table[index].key == ptr)
191 /* Lookup failed: item is not in the table. */
192 /* If last slot is empty, use that slot. */
193 /* Otherwise, table must have been reallocated, so search again. */
195 if (numProbes == MAX_NUM_PROBES)
196 { /* table is too full: reallocate and search again */
197 ReallocTable(ptrTable, 1 + 2*ptrTable->capacity);
198 return FindIndex(ptrTable, ptr);
202 assert(ptrTable->fullEmptyFlags[index] == EMPTY &&
203 "Stopped before finding an empty slot and before MAX probes!");
209 LookupOrInsertPtr(PtrValueHashTable* ptrTable, void* ptr, ACTION action)
211 Index index = FindIndex(ptrTable, ptr);
212 if (ptrTable->fullEmptyFlags[index] == FULL &&
213 ptrTable->table[index].key == ptr)
214 return ptrTable->table[index].value;
216 /* Lookup failed: item is not in the table */
218 return (Generic) NULL;
220 /* Insert item into the table and return its index */
221 InsertAtIndex(ptrTable, ptr, (Generic) NULL, index);
222 return (Generic) NULL;
225 /* Returns NULL if the item is not found. */
226 /* void* LookupPtr(PtrValueHashTable* ptrTable, void* ptr) */
227 #define LookupPtr(ptrTable, ptr) \
228 LookupOrInsertPtr(ptrTable, ptr, FIND)
231 Insert(PtrValueHashTable* ptrTable, void* ptr, Generic value)
233 Index index = FindIndex(ptrTable, ptr);
234 assert(ptrTable->fullEmptyFlags[index] == EMPTY &&
235 "ptr is already in the table: delete it first!");
236 InsertAtIndex(ptrTable, ptr, value, index);
240 Delete(PtrValueHashTable* ptrTable, void* ptr)
242 Index index = FindIndex(ptrTable, ptr);
243 if (ptrTable->fullEmptyFlags[index] == FULL &&
244 ptrTable->table[index].key == ptr)
246 DeleteAtIndex(ptrTable, index);
250 /*===---------------------------------------------------------------------=====
251 * RUNTIME ROUTINES TO MAP POINTERS TO SEQUENCE NUMBERS
252 *===---------------------------------------------------------------------===*/
254 PtrValueHashTable* SequenceNumberTable = NULL;
255 Index INITIAL_SIZE = 1 << 22;
257 #define MAX_NUM_SAVED 1024
259 typedef struct PointerSet_struct {
260 char* savedPointers[MAX_NUM_SAVED]; /* 1024 alloca'd ptrs shd suffice */
261 unsigned int numSaved;
262 struct PointerSet_struct* nextOnStack; /* implement a cheap stack */
265 PointerSet* topOfStack = NULL;
268 HashPointerToSeqNum(char* ptr)
270 static SequenceNumber count = 0;
271 SequenceNumber seqnum;
272 if (SequenceNumberTable == NULL) {
273 assert(MAX_NUM_PROBES < INITIAL_SIZE+1 && "Initial size too small");
274 SequenceNumberTable = CreateTable(INITIAL_SIZE);
276 seqnum = (SequenceNumber) LookupPtr(SequenceNumberTable, ptr);
279 Insert(SequenceNumberTable, ptr, ++count);
286 ReleasePointerSeqNum(char* ptr)
287 { /* if a sequence number was assigned to this ptr, release it */
288 if (SequenceNumberTable != NULL)
289 Delete(SequenceNumberTable, ptr);
295 PointerSet* newSet = (PointerSet*) malloc(sizeof(PointerSet));
296 newSet->numSaved = 0;
297 newSet->nextOnStack = topOfStack;
305 assert(topOfStack != NULL && "popping from empty stack!");
307 topOfStack = oldSet->nextOnStack;
308 assert(oldSet->numSaved == 0);
312 /* free the pointers! */
314 ReleaseRecordedPointers(char* savedPointers[MAX_NUM_SAVED],
315 unsigned int numSaved)
318 for (i=0; i < topOfStack->numSaved; ++i)
319 ReleasePointerSeqNum(topOfStack->savedPointers[i]);
323 ReleasePointersPopSet()
325 ReleaseRecordedPointers(topOfStack->savedPointers, topOfStack->numSaved);
326 topOfStack->numSaved = 0;
331 RecordPointer(char* ptr)
332 { /* record pointers for release later */
333 if (topOfStack->numSaved == MAX_NUM_SAVED) {
334 printf("***\n*** WARNING: OUT OF ROOM FOR SAVED POINTERS."
335 " ALL POINTERS ARE BEING FREED.\n"
336 "*** THE SEQUENCE NUMBERS OF SAVED POINTERS WILL CHANGE!\n*** \n");
337 ReleaseRecordedPointers(topOfStack->savedPointers, topOfStack->numSaved);
338 topOfStack->numSaved = 0;
340 topOfStack->savedPointers[topOfStack->numSaved++] = ptr;
343 /*===---------------------------------------------------------------------=====
344 * TEST DRIVER FOR INSTRUMENTATION LIBRARY
345 *===---------------------------------------------------------------------===*/
347 #ifndef TEST_INSTRLIB
348 #undef TEST_INSTRLIB /* #define this to turn on by default */
353 main(int argc, char** argv)
358 INITIAL_SIZE = 5; /* start with small table to test realloc's*/
360 if (argc > 1 && ! strcmp(argv[1], "-r"))
366 for (i=0; i < argc; ++i)
367 for (j=0; argv[i][j]; ++j)
369 printf("Sequence number for argc[%d][%d] (%c) = Hash(%p) = %d\n",
370 i, j, argv[i][j], argv[i]+j, HashPointerToSeqNum(argv[i]+j));
373 RecordPointer(argv[i]+j);
377 ReleasePointersPopSet();
379 /* print sequence numbers out again to compare with (-r) and w/o release */
380 for (i=argc-1; i >= 0; --i)
381 for (j=0; argv[i][j]; ++j)
382 printf("Sequence number for argc[%d][%d] (%c) = %d\n",
383 i, j, argv[i][j], argv[i]+j, HashPointerToSeqNum(argv[i]+j));