Implementation of path profiling.

Modified patch by Adam Preuss.

This builds on the existing framework for block tracing, edge profiling and optimal edge profiling.
See -help-hidden for new flags.
For documentation, see the technical report "Implementation of Path Profiling..." in llvm.org/pubs.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124515 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 310 insertions, 23 deletions

diff --git a/runtime/libprofile/CommonProfiling.c b/runtime/libprofile/CommonProfiling.c
index 8b27a25769..1c1771c306 100644
--- a/runtime/libprofile/CommonProfiling.c
+++ b/runtime/libprofile/CommonProfiling.c
@@ -2,17 +2,18 @@
 |*
 |*                     The LLVM Compiler Infrastructure
 |*
-|* This file is distributed under the University of Illinois Open Source      
-|* License. See LICENSE.TXT for details.                                      
-|* 
+|* This file is distributed under the University of Illinois Open Source
+|* License. See LICENSE.TXT for details.
+|*
 |*===----------------------------------------------------------------------===*|
-|* 
+|*
 |* This file implements functions used by the various different types of
 |* profiling implementations.
 |*
 \*===----------------------------------------------------------------------===*/
 
 #include "Profiling.h"
+#include <assert.h>
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <fcntl.h>
@@ -74,26 +75,23 @@ int save_arguments(int argc, const char **argv) {
 }
 
 
-/* write_profiling_data - Write a raw block of profiling counters out to the
- * llvmprof.out file.  Note that we allow programs to be instrumented with
- * multiple different kinds of instrumentation.  For this reason, this function
- * may be called more than once.
+/*
+ * Retrieves the file descriptor for the profile file.
  */
-void write_profiling_data(enum ProfilingType PT, unsigned *Start,
-                          unsigned NumElements) {
+int getOutFile() {
   static int OutFile = -1;
-  int PTy;
-  
-  /* If this is the first time this function is called, open the output file for
-   * appending, creating it if it does not already exist.
+
+  /* If this is the first time this function is called, open the output file
+   * for appending, creating it if it does not already exist.
    */
   if (OutFile == -1) {
-    OutFile = open(OutputFilename, O_CREAT | O_WRONLY | O_APPEND, 0666);
+    OutFile = open(OutputFilename, O_CREAT | O_WRONLY, 0666);
+    lseek(OutFile, 0, SEEK_END); /* O_APPEND prevents seeking */
     if (OutFile == -1) {
       fprintf(stderr, "LLVM profiling runtime: while opening '%s': ",
               OutputFilename);
       perror("");
-      return;
+      return(OutFile);
     }
 
     /* Output the command line arguments to the file. */
@@ -108,10 +106,25 @@ void write_profiling_data(enum ProfilingType PT, unsigned *Start,
         write(OutFile, &Zeros, 4-(SavedArgsLength&3));
     }
   }
- 
+  return(OutFile);
+}
+
+/* write_profiling_data - Write a raw block of profiling counters out to the
+ * llvmprof.out file.  Note that we allow programs to be instrumented with
+ * multiple different kinds of instrumentation.  For this reason, this function
+ * may be called more than once.
+ */
+void write_profiling_data(enum ProfilingType PT, unsigned *Start,
+                          unsigned NumElements) {
+  int PTy;
+  int outFile = getOutFile();
+
   /* Write out this record! */
   PTy = PT;
-  write(OutFile, &PTy, sizeof(int));
-  write(OutFile, &NumElements, sizeof(unsigned));
-  write(OutFile, Start, NumElements*sizeof(unsigned));
+  if( write(outFile, &PTy, sizeof(int)) < 0 ||
+      write(outFile, &NumElements, sizeof(unsigned)) < 0 ||
+      write(outFile, Start, NumElements*sizeof(unsigned)) < 0 ) {
+    fprintf(stderr,"error: unable to write to output file.");
+    exit(0);
+  }
 }
diff --git a/runtime/libprofile/PathProfiling.c b/runtime/libprofile/PathProfiling.c
new file mode 100644
index 0000000000..651e63cbdd
--- /dev/null
+++ b/runtime/libprofile/PathProfiling.c
@@ -0,0 +1,266 @@
+/*===-- PathProfiling.c - Support library for path profiling --------------===*\
+|*
+|*                     The LLVM Compiler Infrastructure
+|*
+|* This file is distributed under the University of Illinois Open Source
+|* License. See LICENSE.TXT for details.
+|*
+|*===----------------------------------------------------------------------===*|
+|*
+|* This file implements the call back routines for the path profiling
+|* instrumentation pass.  This should be used with the -insert-path-profiling
+|* LLVM pass.
+|*
+\*===----------------------------------------------------------------------===*/
+
+#include "Profiling.h"
+#include "llvm/Analysis/ProfileInfoTypes.h"
+#include <sys/types.h>
+#include <unistd.h>
+#include <string.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <stdint.h>
+#include <stdio.h>
+
+/* note that this is used for functions with large path counts,
+         but it is unlikely those paths will ALL be executed */
+#define ARBITRARY_HASH_BIN_COUNT 100
+
+typedef struct pathHashEntry_s {
+  uint32_t pathNumber;
+  uint32_t pathCount;
+  struct pathHashEntry_s* next;
+} pathHashEntry_t;
+
+typedef struct pathHashTable_s {
+  pathHashEntry_t* hashBins[ARBITRARY_HASH_BIN_COUNT];
+  uint32_t pathCounts;
+} pathHashTable_t;
+
+typedef struct {
+  enum ProfilingStorageType type;
+  uint32_t size;
+  void* array;
+} ftEntry_t;
+
+/* pointer to the function table allocated in the instrumented program */
+ftEntry_t* ft;
+uint32_t ftSize;
+
+/* write an array table to file */
+void writeArrayTable(uint32_t fNumber, ftEntry_t* ft, uint32_t* funcCount) {
+  int outFile = getOutFile();
+  uint32_t arrayHeaderLocation = 0;
+  uint32_t arrayCurrentLocation = 0;
+  uint32_t arrayIterator = 0;
+  uint32_t functionUsed = 0;
+  uint32_t pathCounts = 0;
+
+  /* look through each entry in the array to determine whether the function
+     was executed at all */
+  for( arrayIterator = 0; arrayIterator < ft->size; arrayIterator++ ) {
+    uint32_t pc = ((uint32_t*)ft->array)[arrayIterator];
+
+    /* was this path executed? */
+    if( pc ) {
+      PathProfileTableEntry pte;
+      pte.pathNumber = arrayIterator;
+      pte.pathCounter = pc;
+      pathCounts++;
+
+      /* one-time initialization stuff */
+      if(!functionUsed) {
+        arrayHeaderLocation = lseek(outFile, 0, SEEK_CUR);
+        lseek(outFile, sizeof(PathProfileHeader), SEEK_CUR);
+        functionUsed = 1;
+        (*funcCount)++;
+      }
+
+      /* write path data */
+      if (write(outFile, &pte, sizeof(PathProfileTableEntry)) < 0) {
+        fprintf(stderr, "error: unable to write path entry to output file.\n");
+        return;
+      }
+    }
+  }
+
+  /* If this function was executed, write the header */
+  if( functionUsed ) {
+    PathProfileHeader fHeader;
+    fHeader.fnNumber = fNumber;
+    fHeader.numEntries = pathCounts;
+
+    arrayCurrentLocation = lseek(outFile, 0, SEEK_CUR);
+    lseek(outFile, arrayHeaderLocation, SEEK_SET);
+
+    if (write(outFile, &fHeader, sizeof(PathProfileHeader)) < 0) {
+      fprintf(stderr,
+              "error: unable to write function header to output file.\n");
+      return;
+    }
+
+    lseek(outFile, arrayCurrentLocation, SEEK_SET);
+  }
+}
+
+inline uint32_t hash (uint32_t key) {
+  /* this may benifit from a proper hash function */
+  return key%ARBITRARY_HASH_BIN_COUNT;
+}
+
+/* output a specific function's hash table to the profile file */
+void writeHashTable(uint32_t functionNumber, pathHashTable_t* hashTable) {
+  int outFile = getOutFile();
+  PathProfileHeader header;
+  uint32_t i;
+
+  header.fnNumber = functionNumber;
+  header.numEntries = hashTable->pathCounts;
+
+  if (write(outFile, &header, sizeof(PathProfileHeader)) < 0) {
+    fprintf(stderr, "error: unable to write function header to output file.\n");
+    return;
+  }
+
+  for (i = 0; i < ARBITRARY_HASH_BIN_COUNT; i++) {
+    pathHashEntry_t* hashEntry = hashTable->hashBins[i];
+
+    while (hashEntry) {
+      pathHashEntry_t* temp;
+
+      PathProfileTableEntry pte;
+      pte.pathNumber = hashEntry->pathNumber;
+      pte.pathCounter = hashEntry->pathCount;
+
+      if (write(outFile, &pte, sizeof(PathProfileTableEntry)) < 0) {
+        fprintf(stderr, "error: unable to write path entry to output file.\n");
+        return;
+      }
+
+      temp = hashEntry;
+      hashEntry = hashEntry->next;
+      free (temp);
+
+    }
+  }
+}
+
+/* Return a pointer to this path's specific path counter */
+inline uint32_t* getPathCounter(uint32_t functionNumber, uint32_t pathNumber) {
+  pathHashTable_t* hashTable;
+  pathHashEntry_t* hashEntry;
+  uint32_t index = hash(pathNumber);
+
+  if( ft[functionNumber-1].array == 0)
+    ft[functionNumber-1].array = calloc(sizeof(pathHashTable_t), 1);
+
+  hashTable = (pathHashTable_t*)((ftEntry_t*)ft)[functionNumber-1].array;
+  hashEntry = hashTable->hashBins[index];
+
+  while (hashEntry) {
+    if (hashEntry->pathNumber == pathNumber) {
+      return &hashEntry->pathCount;
+    }
+
+    hashEntry = hashEntry->next;
+  }
+
+  hashEntry = malloc(sizeof(pathHashEntry_t));
+  hashEntry->pathNumber = pathNumber;
+  hashEntry->pathCount = 0;
+  hashEntry->next = hashTable->hashBins[index];
+  hashTable->hashBins[index] = hashEntry;
+  hashTable->pathCounts++;
+  return &hashEntry->pathCount;
+}
+
+/* Increment a specific path's count */
+void llvm_increment_path_count (uint32_t functionNumber, uint32_t pathNumber) {
+  uint32_t* pathCounter = getPathCounter(functionNumber, pathNumber);
+  if( *pathCounter < 0xffffffff )
+    (*pathCounter)++;
+}
+
+/* Increment a specific path's count */
+void llvm_decrement_path_count (uint32_t functionNumber, uint32_t pathNumber) {
+  uint32_t* pathCounter = getPathCounter(functionNumber, pathNumber);
+  (*pathCounter)--;
+}
+
+/*
+ * Writes out a path profile given a function table, in the following format.
+ *
+ *
+ *      | <-- 32 bits --> |
+ *      +-----------------+-----------------+
+ * 0x00 | profileType     | functionCount   |
+ *      +-----------------+-----------------+
+ * 0x08 | functionNum     | profileEntries  |  // function 1
+ *      +-----------------+-----------------+
+ * 0x10 | pathNumber      | pathCounter     |  // entry 1.1
+ *      +-----------------+-----------------+
+ * 0x18 | pathNumber      | pathCounter     |  // entry 1.2
+ *      +-----------------+-----------------+
+ *  ... |       ...       |       ...       |  // entry 1.n
+ *      +-----------------+-----------------+
+ *  ... | functionNum     | profileEntries  |  // function 2
+ *      +-----------------+-----------------+
+ *  ... | pathNumber      | pathCounter     |  // entry 2.1
+ *      +-----------------+-----------------+
+ *  ... | pathNumber      | pathCounter     |  // entry 2.2
+ *      +-----------------+-----------------+
+ *  ... |       ...       |       ...       |  // entry 2.n
+ *      +-----------------+-----------------+
+ *
+ */
+static void pathProfAtExitHandler() {
+  int outFile = getOutFile();
+  uint32_t i;
+  uint32_t header[2] = { PathInfo, 0 };
+  uint32_t headerLocation;
+  uint32_t currentLocation;
+
+  /* skip over the header for now */
+  headerLocation = lseek(outFile, 0, SEEK_CUR);
+  lseek(outFile, 2*sizeof(uint32_t), SEEK_CUR);
+
+  /* Iterate through each function */
+  for( i = 0; i < ftSize; i++ ) {
+    if( ft[i].type == ProfilingArray ) {
+      writeArrayTable(i+1,&ft[i],header + 1);
+
+    } else if( ft[i].type == ProfilingHash ) {
+      /* If the hash exists, write it to file */
+      if( ft[i].array ) {
+        writeHashTable(i+1,ft[i].array);
+        header[1]++;
+        free(ft[i].array);
+      }
+    }
+  }
+
+  /* Setup and write the path profile header */
+  currentLocation = lseek(outFile, 0, SEEK_CUR);
+  lseek(outFile, headerLocation, SEEK_SET);
+
+  if (write(outFile, header, sizeof(header)) < 0) {
+    fprintf(stderr,
+            "error: unable to write path profile header to output file.\n");
+    return;
+  }
+
+  lseek(outFile, currentLocation, SEEK_SET);
+}
+/* llvm_start_path_profiling - This is the main entry point of the path
+ * profiling library.  It is responsible for setting up the atexit handler.
+ */
+int llvm_start_path_profiling(int argc, const char** argv,
+                              void* functionTable, uint32_t numElements) {
+  int Ret = save_arguments(argc, argv);
+  ft = functionTable;
+  ftSize = numElements;
+  atexit(pathProfAtExitHandler);
+
+  return Ret;
+}
diff --git a/runtime/libprofile/Profiling.h b/runtime/libprofile/Profiling.h
index a7e3ccc72b..c6b9a4d71c 100644
--- a/runtime/libprofile/Profiling.h
+++ b/runtime/libprofile/Profiling.h
@@ -1,9 +1,9 @@
-/*===-- Profiling.h - Profiling support library support routines --*- C -*-===*\
+/*===-- Profiling.h - Profiling support library support routines ----------===*\
 |*
 |*                     The LLVM Compiler Infrastructure
 |*
-|* This file is distributed under the University of Illinois Open Source      
-|* License. See LICENSE.TXT for details.                                      
+|* This file is distributed under the University of Illinois Open Source
+|* License. See LICENSE.TXT for details.
 |*
 |*===----------------------------------------------------------------------===*|
 |*
@@ -22,6 +22,11 @@
  */
 int save_arguments(int argc, const char **argv);
 
+/*
+ * Retrieves the file descriptor for the profile file.
+ */
+int getOutFile();
+
 /* write_profiling_data - Write out a typed packet of profiling data to the
  * current output file.
  */
diff --git a/runtime/libprofile/libprofile.exports b/runtime/libprofile/libprofile.exports
index f45ff47601..b8057c7aac 100644
--- a/runtime/libprofile/libprofile.exports
+++ b/runtime/libprofile/libprofile.exports
@@ -1,4 +1,7 @@
 llvm_start_edge_profiling
 llvm_start_opt_edge_profiling
+llvm_start_path_profiling
 llvm_start_basic_block_tracing
 llvm_trace_basic_block
+llvm_increment_path_count
+llvm_decrement_path_count