1/*===-- PathProfiling.c - Support library for path profiling --------------===*\
2|*
3|*                     The LLVM Compiler Infrastructure
4|*
5|* This file is distributed under the University of Illinois Open Source
6|* License. See LICENSE.TXT for details.
7|*
8|*===----------------------------------------------------------------------===*|
9|*
10|* This file implements the call back routines for the path profiling
11|* instrumentation pass.  This should be used with the -insert-path-profiling
12|* LLVM pass.
13|*
14\*===----------------------------------------------------------------------===*/
15
16#include "Profiling.h"
17#include "llvm/Analysis/ProfileInfoTypes.h"
18#include "llvm/Support/DataTypes.h"
19#include <sys/types.h>
20#if !defined(_MSC_VER) && !defined(__MINGW32__)
21#include <unistd.h>
22#else
23#include <io.h>
24#endif
25#include <string.h>
26#include <stdlib.h>
27#include <stdio.h>
28
29/* note that this is used for functions with large path counts,
30         but it is unlikely those paths will ALL be executed */
31#define ARBITRARY_HASH_BIN_COUNT 100
32
33typedef struct pathHashEntry_s {
34  uint32_t pathNumber;
35  uint32_t pathCount;
36  struct pathHashEntry_s* next;
37} pathHashEntry_t;
38
39typedef struct pathHashTable_s {
40  pathHashEntry_t* hashBins[ARBITRARY_HASH_BIN_COUNT];
41  uint32_t pathCounts;
42} pathHashTable_t;
43
44typedef struct {
45  enum ProfilingStorageType type;
46  uint32_t size;
47  void* array;
48} ftEntry_t;
49
50/* pointer to the function table allocated in the instrumented program */
51ftEntry_t* ft;
52uint32_t ftSize;
53
54/* write an array table to file */
55void writeArrayTable(uint32_t fNumber, ftEntry_t* ft, uint32_t* funcCount) {
56  int outFile = getOutFile();
57  uint32_t arrayHeaderLocation = 0;
58  uint32_t arrayCurrentLocation = 0;
59  uint32_t arrayIterator = 0;
60  uint32_t functionUsed = 0;
61  uint32_t pathCounts = 0;
62
63  /* look through each entry in the array to determine whether the function
64     was executed at all */
65  for( arrayIterator = 0; arrayIterator < ft->size; arrayIterator++ ) {
66    uint32_t pc = ((uint32_t*)ft->array)[arrayIterator];
67
68    /* was this path executed? */
69    if( pc ) {
70      PathProfileTableEntry pte;
71      pte.pathNumber = arrayIterator;
72      pte.pathCounter = pc;
73      pathCounts++;
74
75      /* one-time initialization stuff */
76      if(!functionUsed) {
77        arrayHeaderLocation = lseek(outFile, 0, SEEK_CUR);
78        lseek(outFile, sizeof(PathProfileHeader), SEEK_CUR);
79        functionUsed = 1;
80        (*funcCount)++;
81      }
82
83      /* write path data */
84      if (write(outFile, &pte, sizeof(PathProfileTableEntry)) < 0) {
85        fprintf(stderr, "error: unable to write path entry to output file.\n");
86        return;
87      }
88    }
89  }
90
91  /* If this function was executed, write the header */
92  if( functionUsed ) {
93    PathProfileHeader fHeader;
94    fHeader.fnNumber = fNumber;
95    fHeader.numEntries = pathCounts;
96
97    arrayCurrentLocation = lseek(outFile, 0, SEEK_CUR);
98    lseek(outFile, arrayHeaderLocation, SEEK_SET);
99
100    if (write(outFile, &fHeader, sizeof(PathProfileHeader)) < 0) {
101      fprintf(stderr,
102              "error: unable to write function header to output file.\n");
103      return;
104    }
105
106    lseek(outFile, arrayCurrentLocation, SEEK_SET);
107  }
108}
109
110static uint32_t hash (uint32_t key) {
111  /* this may benefit from a proper hash function */
112  return key%ARBITRARY_HASH_BIN_COUNT;
113}
114
115/* output a specific function's hash table to the profile file */
116void writeHashTable(uint32_t functionNumber, pathHashTable_t* hashTable) {
117  int outFile = getOutFile();
118  PathProfileHeader header;
119  uint32_t i;
120
121  header.fnNumber = functionNumber;
122  header.numEntries = hashTable->pathCounts;
123
124  if (write(outFile, &header, sizeof(PathProfileHeader)) < 0) {
125    fprintf(stderr, "error: unable to write function header to output file.\n");
126    return;
127  }
128
129  for (i = 0; i < ARBITRARY_HASH_BIN_COUNT; i++) {
130    pathHashEntry_t* hashEntry = hashTable->hashBins[i];
131
132    while (hashEntry) {
133      pathHashEntry_t* temp;
134
135      PathProfileTableEntry pte;
136      pte.pathNumber = hashEntry->pathNumber;
137      pte.pathCounter = hashEntry->pathCount;
138
139      if (write(outFile, &pte, sizeof(PathProfileTableEntry)) < 0) {
140        fprintf(stderr, "error: unable to write path entry to output file.\n");
141        return;
142      }
143
144      temp = hashEntry;
145      hashEntry = hashEntry->next;
146      free (temp);
147
148    }
149  }
150}
151
152/* Return a pointer to this path's specific path counter */
153static uint32_t* getPathCounter(uint32_t functionNumber,
154                                       uint32_t pathNumber) {
155  pathHashTable_t* hashTable;
156  pathHashEntry_t* hashEntry;
157  uint32_t index = hash(pathNumber);
158
159  if( ft[functionNumber-1].array == 0)
160    ft[functionNumber-1].array = calloc(sizeof(pathHashTable_t), 1);
161
162  hashTable = (pathHashTable_t*)((ftEntry_t*)ft)[functionNumber-1].array;
163  hashEntry = hashTable->hashBins[index];
164
165  while (hashEntry) {
166    if (hashEntry->pathNumber == pathNumber) {
167      return &hashEntry->pathCount;
168    }
169
170    hashEntry = hashEntry->next;
171  }
172
173  hashEntry = malloc(sizeof(pathHashEntry_t));
174  hashEntry->pathNumber = pathNumber;
175  hashEntry->pathCount = 0;
176  hashEntry->next = hashTable->hashBins[index];
177  hashTable->hashBins[index] = hashEntry;
178  hashTable->pathCounts++;
179  return &hashEntry->pathCount;
180}
181
182/* Increment a specific path's count */
183void llvm_increment_path_count (uint32_t functionNumber, uint32_t pathNumber) {
184  uint32_t* pathCounter = getPathCounter(functionNumber, pathNumber);
185  if( *pathCounter < 0xffffffff )
186    (*pathCounter)++;
187}
188
189/* Increment a specific path's count */
190void llvm_decrement_path_count (uint32_t functionNumber, uint32_t pathNumber) {
191  uint32_t* pathCounter = getPathCounter(functionNumber, pathNumber);
192  (*pathCounter)--;
193}
194
195/*
196 * Writes out a path profile given a function table, in the following format.
197 *
198 *
199 *      | <-- 32 bits --> |
200 *      +-----------------+-----------------+
201 * 0x00 | profileType     | functionCount   |
202 *      +-----------------+-----------------+
203 * 0x08 | functionNum     | profileEntries  |  // function 1
204 *      +-----------------+-----------------+
205 * 0x10 | pathNumber      | pathCounter     |  // entry 1.1
206 *      +-----------------+-----------------+
207 * 0x18 | pathNumber      | pathCounter     |  // entry 1.2
208 *      +-----------------+-----------------+
209 *  ... |       ...       |       ...       |  // entry 1.n
210 *      +-----------------+-----------------+
211 *  ... | functionNum     | profileEntries  |  // function 2
212 *      +-----------------+-----------------+
213 *  ... | pathNumber      | pathCounter     |  // entry 2.1
214 *      +-----------------+-----------------+
215 *  ... | pathNumber      | pathCounter     |  // entry 2.2
216 *      +-----------------+-----------------+
217 *  ... |       ...       |       ...       |  // entry 2.n
218 *      +-----------------+-----------------+
219 *
220 */
221static void pathProfAtExitHandler(void) {
222  int outFile = getOutFile();
223  uint32_t i;
224  uint32_t header[2] = { PathInfo, 0 };
225  uint32_t headerLocation;
226  uint32_t currentLocation;
227
228  /* skip over the header for now */
229  headerLocation = lseek(outFile, 0, SEEK_CUR);
230  lseek(outFile, 2*sizeof(uint32_t), SEEK_CUR);
231
232  /* Iterate through each function */
233  for( i = 0; i < ftSize; i++ ) {
234    if( ft[i].type == ProfilingArray ) {
235      writeArrayTable(i+1,&ft[i],header + 1);
236
237    } else if( ft[i].type == ProfilingHash ) {
238      /* If the hash exists, write it to file */
239      if( ft[i].array ) {
240        writeHashTable(i+1,ft[i].array);
241        header[1]++;
242        free(ft[i].array);
243      }
244    }
245  }
246
247  /* Setup and write the path profile header */
248  currentLocation = lseek(outFile, 0, SEEK_CUR);
249  lseek(outFile, headerLocation, SEEK_SET);
250
251  if (write(outFile, header, sizeof(header)) < 0) {
252    fprintf(stderr,
253            "error: unable to write path profile header to output file.\n");
254    return;
255  }
256
257  lseek(outFile, currentLocation, SEEK_SET);
258}
259/* llvm_start_path_profiling - This is the main entry point of the path
260 * profiling library.  It is responsible for setting up the atexit handler.
261 */
262int llvm_start_path_profiling(int argc, const char** argv,
263                              void* functionTable, uint32_t numElements) {
264  int Ret = save_arguments(argc, argv);
265  ft = functionTable;
266  ftSize = numElements;
267  atexit(pathProfAtExitHandler);
268
269  return Ret;
270}
271