diff options
Diffstat (limited to 'runtime/libtrace/tracelib.c')
| -rw-r--r-- | runtime/libtrace/tracelib.c | 392 |
1 files changed, 392 insertions, 0 deletions
diff --git a/runtime/libtrace/tracelib.c b/runtime/libtrace/tracelib.c new file mode 100644 index 0000000..be726f1 --- /dev/null +++ b/runtime/libtrace/tracelib.c @@ -0,0 +1,392 @@ +/*===-- tracelib.c - Runtime routines for tracing ---------------*- C++ -*-===* + * + * 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 "llvm/Support/DataTypes.h" + +/*===---------------------------------------------------------------------===== + * HASH FUNCTIONS + *===---------------------------------------------------------------------===*/ + +/* use #defines until we have inlining */ +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) \ + ( ((((Index) value) << 3) ^ (((Index) value) >> 3)) % size ) + +/* Index IntegerRehashFunc(const Generic oldHashValue, const Index size) */ +#define IntegerRehashFunc(oldHashValue, size) \ + ((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((Index) value, size) + +/* Index PointerRehashFunc(const void* value, const Index size) */ +#define PointerRehashFunc(value, size) \ + IntegerRehashFunc((Index) value, size) + +/*===---------------------------------------------------------------------===== + * POINTER-TO-GENERIC HASH TABLE. + * These should be moved to a separate location: HashTable.[ch] + *===---------------------------------------------------------------------===*/ + +typedef enum { FIND, ENTER } ACTION; +typedef char FULLEMPTY; +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 unsigned 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 }; +unsigned CurrentSizeEntry = FIRSTENTRY; + +const unsigned MAX_NUM_PROBES = 4; + +typedef struct PtrValueHashEntry_struct { + void* key; + Generic value; +} PtrValueHashEntry; + +typedef struct PtrValueHashTable_struct { + PtrValueHashEntry* table; + FULLEMPTY* fullEmptyFlags; + Index capacity; + Index size; +} PtrValueHashTable; + + +static Generic LookupOrInsertPtr(PtrValueHashTable* ptrTable, void* ptr, + ACTION action, Generic value); + +static void Insert(PtrValueHashTable* ptrTable, void* ptr, Generic value); + +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*) calloc(newSize, + sizeof(PtrValueHashEntry)); + ptrTable->fullEmptyFlags = (FULLEMPTY*) calloc(newSize, sizeof(FULLEMPTY)); + ptrTable->capacity = newSize; + ptrTable->size = 0; +} + +PtrValueHashTable* +CreateTable(Index initialSize) +{ + PtrValueHashTable* ptrTable = + (PtrValueHashTable*) malloc(sizeof(PtrValueHashTable)); + InitializeTable(ptrTable, initialSize); + return ptrTable; +} + +void +ReallocTable(PtrValueHashTable* ptrTable, Index newSize) +{ + 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 +DeleteTable(PtrValueHashTable* ptrTable) +{ + free(ptrTable->table); + free(ptrTable->fullEmptyFlags); + memset(ptrTable, '\0', sizeof(PtrValueHashTable)); + free(ptrTable); +} + +void +InsertAtIndex(PtrValueHashTable* ptrTable, void* ptr, Generic value, Index index) +{ + assert(ptrTable->fullEmptyFlags[index] == EMPTY && "Slot is in use!"); + ptrTable->table[index].key = ptr; + ptrTable->table[index].value = value; + ptrTable->fullEmptyFlags[index] = FULL; + ptrTable->size++; +} + +void +DeleteAtIndex(PtrValueHashTable* ptrTable, Index index) +{ + assert(ptrTable->fullEmptyFlags[index] == FULL && "Deleting empty slot!"); + ptrTable->table[index].key = 0; + ptrTable->table[index].value = (Generic) 0; + ptrTable->fullEmptyFlags[index] = EMPTY; + ptrTable->size--; +} + +Index +FindIndex(PtrValueHashTable* ptrTable, void* ptr) +{ + unsigned numProbes = 1; + Index index = PointerHashFunc(ptr, ptrTable->capacity); + if (ptrTable->fullEmptyFlags[index] == FULL) + { + if (ptrTable->table[index].key == ptr) + return index; + + /* First lookup failed on non-empty slot: probe further */ + while (numProbes < MAX_NUM_PROBES) + { + index = PointerRehashFunc(index, ptrTable->capacity); + if (ptrTable->fullEmptyFlags[index] == EMPTY) + break; + else if (ptrTable->table[index].key == ptr) + return index; + ++numProbes; + } + } + + /* Lookup failed: item is not in the table. */ + /* If last slot is empty, use that slot. */ + /* Otherwise, table must have been reallocated, so search again. */ + + if (numProbes == MAX_NUM_PROBES) + { /* table is too full: reallocate and search again */ + if (CurrentSizeEntry >= NUMPRIMES-1) { + fprintf(stderr, "Out of PRIME Numbers!!!"); + abort(); + } + ReallocTable(ptrTable, PRIMES[++CurrentSizeEntry]); + return FindIndex(ptrTable, ptr); + } + else + { + assert(ptrTable->fullEmptyFlags[index] == EMPTY && + "Stopped before finding an empty slot and before MAX probes!"); + return index; + } +} + +/* 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, + Generic value) +{ + Index index = FindIndex(ptrTable, ptr); + if (ptrTable->fullEmptyFlags[index] == FULL && + ptrTable->table[index].key == ptr) + return ptrTable->table[index].value; + + /* Lookup failed: item is not in the table */ + /* If action is ENTER, insert item into the table. Return 0 in any case. */ + if (action == ENTER) + InsertAtIndex(ptrTable, ptr, value, index); + + return (Generic) 0; +} + +void +Insert(PtrValueHashTable* ptrTable, void* ptr, Generic value) +{ + Index index = FindIndex(ptrTable, ptr); + assert(ptrTable->fullEmptyFlags[index] == EMPTY && + "ptr is already in the table: delete it first!"); + InsertAtIndex(ptrTable, ptr, value, index); +} + +void +Delete(PtrValueHashTable* ptrTable, void* ptr) +{ + Index index = FindIndex(ptrTable, ptr); + if (ptrTable->fullEmptyFlags[index] == FULL && + ptrTable->table[index].key == ptr) + { + DeleteAtIndex(ptrTable, index); + } +} + +/*===---------------------------------------------------------------------===== + * RUNTIME ROUTINES TO MAP POINTERS TO SEQUENCE NUMBERS + *===---------------------------------------------------------------------===*/ + +PtrValueHashTable* SequenceNumberTable = NULL; +#define INITIAL_SIZE (PRIMES[FIRSTENTRY]) + +#define MAX_NUM_SAVED 1024 + +typedef struct PointerSet_struct { + char* savedPointers[MAX_NUM_SAVED]; /* 1024 alloca'd ptrs shd suffice */ + unsigned int numSaved; + struct PointerSet_struct* nextOnStack; /* implement a cheap stack */ +} PointerSet; + +PointerSet* topOfStack = NULL; + +SequenceNumber +HashPointerToSeqNum(char* ptr) +{ + static SequenceNumber count = 0; + SequenceNumber seqnum; + if (SequenceNumberTable == NULL) { + assert(MAX_NUM_PROBES < INITIAL_SIZE+1 && "Initial size too small"); + SequenceNumberTable = CreateTable(INITIAL_SIZE); + } + 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 */ + if (SequenceNumberTable != NULL) + Delete(SequenceNumberTable, ptr); +} + +void +PushPointerSet() +{ + PointerSet* newSet = (PointerSet*) malloc(sizeof(PointerSet)); + newSet->numSaved = 0; + newSet->nextOnStack = topOfStack; + topOfStack = newSet; +} + +void +PopPointerSet() +{ + PointerSet* oldSet; + assert(topOfStack != NULL && "popping from empty stack!"); + oldSet = topOfStack; + topOfStack = oldSet->nextOnStack; + assert(oldSet->numSaved == 0); + free(oldSet); +} + +/* free the pointers! */ +static void +ReleaseRecordedPointers(char* savedPointers[MAX_NUM_SAVED], + unsigned int numSaved) +{ + unsigned int i; + for (i=0; i < topOfStack->numSaved; ++i) + ReleasePointerSeqNum(topOfStack->savedPointers[i]); +} + +void +ReleasePointersPopSet() +{ + ReleaseRecordedPointers(topOfStack->savedPointers, topOfStack->numSaved); + topOfStack->numSaved = 0; + PopPointerSet(); +} + +void +RecordPointer(char* ptr) +{ /* record pointers for release later */ + if (topOfStack->numSaved == MAX_NUM_SAVED) { + printf("***\n*** WARNING: OUT OF ROOM FOR SAVED POINTERS." + " ALL POINTERS ARE BEING FREED.\n" + "*** THE SEQUENCE NUMBERS OF SAVED POINTERS WILL CHANGE!\n*** \n"); + ReleaseRecordedPointers(topOfStack->savedPointers, topOfStack->numSaved); + topOfStack->numSaved = 0; + } + topOfStack->savedPointers[topOfStack->numSaved++] = ptr; +} + +/*===---------------------------------------------------------------------===== + * TEST DRIVER FOR INSTRUMENTATION LIBRARY + *===---------------------------------------------------------------------===*/ + +#ifndef TEST_INSTRLIB +#undef TEST_INSTRLIB /* #define this to turn on by default */ +#endif + +#ifdef TEST_INSTRLIB +int +main(int argc, char** argv) +{ + int i, j; + int doRelease = 0; + + INITIAL_SIZE = 5; /* start with small table to test realloc's*/ + + if (argc > 1 && ! strcmp(argv[1], "-r")) + { + PushPointerSet(); + doRelease = 1; + } + + for (i=0; i < argc; ++i) + for (j=0; argv[i][j]; ++j) + { + printf("Sequence number for argc[%d][%d] (%c) = Hash(%p) = %d\n", + i, j, argv[i][j], argv[i]+j, HashPointerToSeqNum(argv[i]+j)); + + if (doRelease) + RecordPointer(argv[i]+j); + } + + if (doRelease) + ReleasePointersPopSet(); + + /* 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) = %d\n", + i, j, argv[i][j], argv[i]+j, HashPointerToSeqNum(argv[i]+j)); + + return 0; +} +#endif |