Hexe: Heterogeneous Execution Engine (Runtime)

[• margiolas]

Summary

The code is the runtime counterpart of the heterogeneous execution engine.

This patch is huge. It will be split to smaller individual patches. This version is on
phabricator as a reference of the current implementation.

https://drive.google.com/file/d/0B5GasMlWJhTOb2tXTDZsal9qclE/view?usp=sharing

cmake/config-ix.cmake

 filter_available_targets(TSAN_SUPPORTED_ARCH x86_64 mips64 mips64el)
 filter_available_targets(UBSAN_SUPPORTED_ARCH x86_64 i386 i686 arm aarch64 mips
   mipsel mips64 mips64el powerpc64 powerpc64le)
+filter_available_targets(HEXE_SUPPORTED_ARCH x86_64 i386 i686 arm aarch64)
 
 if(ANDROID)
   set(OS_NAME "Android")

 if("${LLVM_NATIVE_ARCH}" STREQUAL "Mips")
   set(COMPILER_RT_HAS_MSSE3_FLAG FALSE)
 endif()
+
+if (OS_NAME MATCHES "Darwin|Linux|FreeBSD")
+  set(COMPILER_RT_HAS_HEXE TRUE)
+else ()
+  set(COMPILER_RT_HAS_HEXE FALSE)
+endif ()
+

lib/CMakeLists.txt

   add_subdirectory(tsan/dd)
 endif()
 
+if(COMPILER_RT_HAS_HEXE)
+  add_subdirectory(hexe)
+endif()
+
+

lib/hexe/CMakeLists.txt

+set(HEXE_SOURCES
+  hexe_engine.c
+  plugins/hexe_accelerator_debug_plugin.c
+)
+
+function (phonyPluginImpl PName FName)
+  set(Src "struct Hexe_Plugin_Interface\;"
+      "struct Hexe_Plugin_Interface *"
+      "Hexe_${PName}_Plugin_init() { return 0\; }" )
+  file(WRITE ${FName} ${Src})
+endfunction (phonyPluginImpl PName FName)
+
+if (HEXE_HEXAGON)
+  set(HEXE_SOURCES ${HEXE_SOURCES}
+    plugins/hexe_hexagon_plugin.c)
+else ()
+  phonyPluginImpl("Hexagon" "${CMAKE_CURRENT_BINARY_DIR}/Hexagon.c")
+  set(HEXE_SOURCES ${HEXE_SOURCES}
+    "${CMAKE_CURRENT_BINARY_DIR}/Hexagon.c")
+endif ()
+
+include_directories(${CMAKE_CURRENT_SOURCE_DIR})
+
+add_custom_target(hexe)
+set(HEXE_FLAGS -fPIC)
+
+foreach(arch ${HEXE_SUPPORTED_ARCH})
+  add_compiler_rt_runtime(clang_rt.hexe-${arch} ${arch} STATIC
+    CFLAGS ${HEXE_FLAGS} SOURCES ${HEXE_SOURCES} )
+  add_dependencies(hexe clang_rt.hexe-${arch})
+endforeach()
+
+install(FILES hexe_interface.h hexe_internal.h
+  PERMISSIONS OWNER_READ OWNER_WRITE GROUP_READ WORLD_READ
+  DESTINATION ${COMPILER_RT_INSTALL_PATH}/include/hexe)
+
+add_dependencies(compiler-rt hexe)

lib/hexe/hexe_engine.c

+/* ===-- hexe_engine.c ---------------------------------------------*- C -*-===*
+*
+*                     The LLVM Compiler Infrastructure
+*
+* This file is distributed under the University of Illinois Open Source
+* License. See LICENSE.TXT for details.
+*
+* ===----------------------------------------------------------------------===*/
+/**
+* \file
+* This file is part of the runtime environment of the Heterogeneous Execution
+* Engine. It defines the external interface functions and the constructors and
+* destructors of the library.
+* ===----------------------------------------------------------------------===*/
+
+
+
+#include "hexe_interface.h"
+#include "hexe_internal.h"
+#include "hexe_plugins.h"
+#include <stdlib.h>
+#include <stdio.h>
+
+static struct Hexe_Plugin_Interface *Plugin;
+
+/* Please read the documentation of hexe_interface.h
+ * The function operations are described there. */
+
+int __hexe_runtime_sched(unsigned function_id,
+                         struct __hexe_MemAccessInfo *InfArray,
+                         unsigned num_elems, struct __hexe_KernelInfo *KI)
+{
+  return Plugin->runtime_sched(function_id, InfArray, num_elems,
+                               KI, Plugin);
+}
+
+struct __hexe_Event_t *__hexe_dispatch(unsigned function_id, void *args,
+                                       unsigned args_size)
+{
+  return Plugin->dispatch(function_id, args, args_size, Plugin);
+}
+
+void __hexe_enforce_coherency(unsigned function_id,
+                              struct __hexe_MemAccessInfo *InfArray,
+                              unsigned num_elems)
+{
+  Plugin->enforce_coherency(function_id, InfArray, num_elems, Plugin);
+}
+
+int __hexe_event_wait(struct __hexe_Event_t *Event)
+{
+  return Plugin->event_wait(Event, Plugin);
+}
+
+int __hexe_event_check(struct __hexe_Event_t *Event)
+{
+  return Plugin->event_check(Event, Plugin);
+}
+
+void *__hexe_malloc(unsigned size, unsigned alignment)
+{
+  return Plugin->malloc(size, alignment, Plugin);
+}
+void __hexe_free(void *ptr)
+{
+  if (Plugin->free(ptr,Plugin))
+    return; /* the segment was allocated with the plugin allocator */
+
+  /* otherwise it was allocated with the standard allocator */
+  free(ptr);
+}
+
+static void __hexe_init()
+{
+  /* try to inialize the Hexagon plugin. */
+  Plugin=Hexe_Hexagon_Plugin_init();
+
+  /* if the Hexagon Plugin is not supported
+  initialize the debug plugin. */
+  if (!Plugin)
+    Plugin=Hexe_Accelerator_Debug_Plugin_init();
+
+  if (Plugin->load_code_vendor(Plugin)) {
+    exit(-1);
+  }
+
+  __hexe_report_message(Plugin,"initialized");
+}
+
+static void __hexe_destroy()
+{
+  Plugin->destroy(Plugin);
+}
+
+/* Constructor, it is called at the application initialization. */
+static void __attribute__ ((constructor (65534) )) init(void)
+{
+  __hexe_init();
+}
+
+/* Destructor, is is called at the application exit. */
+static void __attribute__ (( destructor (65534) )) destroy(void)
+{
+  __hexe_destroy();
+}
+
+
+/* message reporting */
+
+enum MessageType {
+  ERROR_MESSAGE=0,
+  REPORT_MESSAGE
+};
+
+static const char *MessageStr[ ]={ "ERROR", "REPORT" };
+
+static void generic_message(enum MessageType type,
+    struct Hexe_Plugin_Interface *plugin, const char *message)
+{
+  if (plugin)
+    fprintf(stderr,"%s: Plugin: %s, %s\n", MessageStr[type],
+        plugin->plugin_info(plugin), message);
+  else
+    fprintf(stderr,"%s: %s\n", MessageStr[type], message);
+}
+
+/* error message */
+void __hexe_error_message(struct Hexe_Plugin_Interface *plugin,
+                          const char *message)
+{
+  generic_message(ERROR_MESSAGE,plugin,message);
+}
+
+/* report message */
+void __hexe_report_message(struct Hexe_Plugin_Interface *plugin,
+                           const char *message)
+{
+  generic_message(REPORT_MESSAGE,plugin,message);
+}

lib/hexe/hexe_interface.h

+/* ===-- hexe_interface.h ------------------------------------------*- C -*-===*
+*
+*                     The LLVM Compiler Infrastructure
+*
+* This file is distributed under the University of Illinois Open Source
+* License. See LICENSE.TXT for details.
+*
+* ===----------------------------------------------------------------------===*/
+/**
+* \file
+* This file is part of the runtime environment of the Heterogeneous Execution
+* Engine. It provides the external function interface. Calls to this interface
+* are injected in the application code by the Hexe compiler passes.
+* ===----------------------------------------------------------------------===*/
+
+#ifndef __HEXE_INTERFACE_H__
+#define __HEXE_INTERFACE_H__
+
+/**
+ * Struct type that provides information about a Memory Segment
+ * accessed by the Workload.
+ */
+struct __hexe_MemAccessInfo;
+
+/**
+ * Struct type that provides description about the Workload Code.
+ * Not used yet.
+ */
+struct __hexe_KernelInfo;
+
+/**
+ * Struct type that represents an event. Events are used for asynchronous
+ * Workload dispatching.
+ */
+struct __hexe_Event;
+
+/**
+ * \brief This function makes a decision about the execution of a Workload.
+ * If it will be executed on the CPU or the accelerator.
+ *
+ * \param function_id: The ID of the function that performs the Workload
+ * computation.
+ * \param mem_access_info_array: Information about the memory segments
+ * accessed by the Workload function.
+ * \param num_elems: Number of the array elements.
+ * \param kernel_info: Description of the Workload code.
+ */
+int __hexe_runtime_sched(unsigned function_id,
+                         struct __hexe_MemAccessInfo *mem_access_info_array,
+                         unsigned num_elems, struct __hexe_KernelInfo *KI);
+
+/**
+ * \brief This function dispatches a Workload for execution on the accelerator.
+ *
+ * \param function_id: The ID of the function that performs the Workload
+ * computation.
+ * \param args: it is a buffer that contains a marshalled version of
+ * the call arguments.
+ * \param args_size: the size of the buffer.
+ *
+ * \returns Non zero for accelerator execution and 0 for CPU execution.
+ */
+struct __hexe_Event_t *__hexe_dispatch(unsigned function_id, void *args,
+                                       unsigned args_size);
+
+/**
+ * \brief This function performs coherency and address translation
+ *  operations.
+ *
+ * \param function_id: The ID of the function that performs the Workload
+ * computation.
+ * \param memory_access_info_array: Information about the memory segments
+ * accessed by the Workload function.
+ * \param num_elems: Number of the array elements.
+ */
+void __hexe_enforce_coherency(unsigned function_id,
+  struct __hexe_MemAccessInfo *memory_access_info_array, unsigned num_elems);
+
+/**
+ * \brief This function waits for the completion of an asynchronous
+ * dispatch via its event.
+ */
+int __hexe_event_wait(struct __hexe_Event_t *Event);
+
+/**
+ * \brief This function checks if an asynchronous dispatch has been
+ * completed via its event.
+ */
+int __hexe_event_check(struct __hexe_Event_t *Event);
+
+/**
+ * \brief This function allocates memory via the Hexe Memory
+ * Allocator. Allocating memory with this allocator guarantees
+ * that the memory is accessible to both host and accelerator
+ * sides for no coherent systems.
+ *
+ * \param size: the allocation size.
+ * \param alignment: the required alignment, if 0
+ * the standard alignment of the platform is used.
+ */
+void *__hexe_malloc(unsigned size, unsigned alignment);
+
+/**
+ * \brief It releases memory allocated with __hexe_malloc.
+ */
+void __hexe_free(void *ptr);
+
+#endif /* __HEXE_INTERFACE_H__ */
+

lib/hexe/hexe_internal.h

+/* ===-- hexe_internal.h -------------------------------------------*- C -*-===*
+*
+*                     The LLVM Compiler Infrastructure
+*
+* This file is distributed under the University of Illinois Open Source
+* License. See LICENSE.TXT for details.
+*
+* ===----------------------------------------------------------------------===*/
+/**
+* \file
+* This file is part of the runtime environment of the Heterogeneous Execution
+* Engine. It defines the data structures used by the runtime library. It also
+* defines the Plugin Interface.
+* ===----------------------------------------------------------------------===*/
+
+
+#ifndef __HEXE_INTERNAL_H__
+#define __HEXE_INTERNAL_H__
+
+/**
+ * Struct type that provides information about a Memory Segment
+ * accessed by the Workload.
+ */
+struct __hexe_MemAccessInfo {
+ void *ptr;
+ unsigned size; /* a static estimation of the segment size*/
+ unsigned arg_order; /* the argument of the Workload function */
+                     /* that gets mapped to this segment */
+ char access_mode; /* read 0, write 1, readwrite 3 */
+};
+
+/**
+ * Struct type that provides description about the Workload Code.
+ * Not in use yet.
+ */
+struct __hexe_KernelInfo {
+  unsigned num_operations;
+  char hasNestedLoops;
+  char isALoop;
+};
+
+/* Function Pointer Types for the Plugin Interface */
+typedef int (*__hexe_runtime_schedPT) (unsigned function_id,
+    struct __hexe_MemAccessInfo *InfArray, unsigned num_elems,
+    struct __hexe_KernelInfo *KI, void *PluginData);
+
+typedef struct __hexe_Event_t * (*__hexe_dispatchPT) (unsigned function_id,
+    void *args, unsigned args_size, void *PluginData);
+
+typedef void (*__hexe_enforce_coherencyPT) (unsigned function_id,
+    struct __hexe_MemAccessInfo *InfArray, unsigned num_elems,
+    void *PluginData);
+
+typedef int (*__hexe_event_waitPT) (struct __hexe_Event_t *Event,
+                                    void *PluginData);
+typedef int (*__hexe_event_checkPT) (struct __hexe_Event_t *Event,
+                                     void *PluginData);
+
+typedef void *(*__hexe_mallocPT) (unsigned size, unsigned alignment,
+                                  void *PluginData);
+typedef int (*__hexe_freePT) (void *ptr, void *PluginData);
+
+/* internal manipulations not exposed externally */
+typedef int (*__hexe_load_code_from_filePT) (const char *base_filename,
+    const char *fextension, void *PluginData);
+
+typedef int (*__hexe_load_code_from_elf_sectionPT)
+  (const char *base_section_name, const char *fextension, void *PluginData);
+
+typedef int (*__hexe_load_code_vendor_PT) (void *PluginData);
+
+typedef int (*__hexe_destroy_PT) (void *PluginData);
+typedef const char * (*__hexe_plugin_info_PT)(void *PluginData);
+
+/* Virtual Table Struct. Every Plugin should have a struct type where
+ * the first element is an instance of the struct Hexe_Plugin_Interface
+ */
+struct Hexe_Plugin_Interface {
+  /* They get mapped to the external
+   interface operations. */
+  __hexe_runtime_schedPT runtime_sched;
+  __hexe_dispatchPT dispatch;
+  __hexe_enforce_coherencyPT enforce_coherency;
+  __hexe_event_waitPT event_wait;
+  __hexe_event_checkPT event_check;
+  __hexe_mallocPT malloc;
+  __hexe_freePT free;
+
+  /* load accelerator code from file */
+  __hexe_load_code_from_filePT load_code_from_file;
+  /* load accelerator code from elf section */
+  __hexe_load_code_from_elf_sectionPT load_code_from_elf_section;
+  /* load accelerator code via a vendor specific way */
+  __hexe_load_code_vendor_PT load_code_vendor;
+
+  /* destroys the plugin instance */
+  __hexe_destroy_PT destroy;
+
+  /* returns a description c string */
+  __hexe_plugin_info_PT plugin_info;
+};
+
+/* error message */
+void __hexe_error_message(struct Hexe_Plugin_Interface *plugin,
+    const char *message);
+
+/* report message */
+void __hexe_report_message(struct Hexe_Plugin_Interface *plugin,
+    const char *message);
+
+#endif /* __HEXE_INTERNAL_H__ */
+

lib/hexe/hexe_plugins.h

+/* ===-- hexe_plugins.h --------------------------------------------*- C -*-===*
+*
+*                     The LLVM Compiler Infrastructure
+*
+* This file is distributed under the University of Illinois Open Source
+* License. See LICENSE.TXT for details.
+*
+* ===----------------------------------------------------------------------===*/
+/**
+* \file
+* This file is part of the runtime environment of the Heterogeneous Execution
+* Engine. It provides functions that initialize instances of the available
+* plugins.
+* ===----------------------------------------------------------------------===*/
+
+
+#ifndef __HEXE_PLUGINS_H__
+#define __HEXE_PLUGINS_H__
+
+struct Hexe_Plugin_Interface;
+
+/* Initialize a Hexagon plugin instance */
+struct Hexe_Plugin_Interface * Hexe_Hexagon_Plugin_init();
+
+/*Initialize an Accelerator Debug plugin instance */
+struct Hexe_Plugin_Interface * Hexe_Accelerator_Debug_Plugin_init();
+
+
+#endif /* __HEXE_PLUGINS_H__ */

lib/hexe/plugins/hexe_accelerator_debug_plugin.c

+/* === -- hexe_accelerator_debug_plugin.c -------------------------*- C -*-=== *
+*
+*                     The LLVM Compiler Infrastructure
+*
+* This file is distributed under the University of Illinois Open Source
+* License. See LICENSE.TXT for details.
+*
+* === --------------------------------------------------------------------=== */
+/**
+* \file
+* This file is part of the runtime environment of the Heterogeneous Execution
+* Engine. It defines the Accelerator Debug Plugin. This plugin is used for
+* debugging and corrrectness runs. It uses the Hexagon convention and requires
+* the Hexe Workload to be compiled with the Hexagon Adaptor. However, it does
+* not require the use of an accelerator. Both host and accelerator code are
+* compiled for the same architecture. The accelerator code is loaded as
+* a dynamic library. We perfom a phony offloading by calling the functions from
+* the dynamic library. That way we can evaluate the correctness of the compiler
+* passes and the operations of the runtime.
+* === --------------------------------------------------------------------=== */
+
+
+
+#include "hexe_internal.h"
+#include "uthash/utlist.h"
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+#include <dlfcn.h>
+
+//fastrpc data structures
+
+typedef struct {
+   void *pv;
+   size_t nLen;
+} remote_buf;
+
+typedef int (*invoke_interface_t)(uint32_t dwScalars,
+    remote_buf *pra);
+
+#define REMOTE_SCALARS_MAKEX(nAttr, nMethod, nIn, nOut, noIn, noOut) \
+          ((((uint32_t)   (nAttr) &  0x7) << 29) | \
+           (((uint32_t) (nMethod) & 0x1f) << 24) | \
+           (((uint32_t)     (nIn) & 0xff) << 16) | \
+           (((uint32_t)    (nOut) & 0xff) <<  8) | \
+           (((uint32_t)    (noIn) & 0x0f) <<  4) | \
+            ((uint32_t)   (noOut) & 0x0f))
+
+
+#define MB (1<<20)
+#define MAX_ACTIVE_TASKS 1
+#define TRUE 1
+#define FALSE 0
+
+
+/* Link List Node definition and comparator functions.
+ * We use a Linked List to keep tract of the memory
+ * allocations served by the plugin */
+struct Allocation_Node {
+  struct Allocation_Node *next;
+  void *ptr;
+  unsigned size;
+};
+
+static int alloc_comperator(struct Allocation_Node *n1,
+    struct Allocation_Node *n2)
+{
+  return ( (size_t) n1->ptr) ^ ( (size_t) n2->ptr); //returns 0 if equal
+}
+
+static int alloc_match(struct Allocation_Node *n1,
+    struct Allocation_Node *n2)
+{
+  const char *n1p = (const char *)n1->ptr;
+  const char *n2p = (const char *)n2->ptr;
+
+  if ((n2p >= n1p) && (n2p < n1p+n1->size))
+    return 0;
+
+  return -1;
+}
+
+/* Accelerator Debug Plugin struct definition */
+struct Hexe_Accelerator_Debug_Plugin {
+  struct Hexe_Plugin_Interface base;
+  //TODO: make them  a struct and replace them
+  //with array of MAX_ACTIVE_TASKS
+  void *arg_shared_buffer;
+  remote_buf remote_buffer_slots[256];
+  unsigned read_buffer_num, write_buffer_num;
+
+  struct Allocation_Node *allocation_list_head;
+  void *dlhandle;
+  invoke_interface_t invoke;
+};
+
+/* forward declaratin of the Plugin Interface Implementation */
+static int runtime_sched(unsigned function_id,
+                         struct __hexe_MemAccessInfo *InfArray,
+                         unsigned num_elems,
+                         struct __hexe_KernelInfo *KI,
+                         void *PluginData);
+
+static struct __hexe_Event_t *dispatch(unsigned function_id,
+                                       void *args, unsigned args_size,
+                                       void *PluginData);
+
+static void enforce_coherency(unsigned function_id,
+                              struct __hexe_MemAccessInfo *InfArray,
+                              unsigned num_elems,
+                              void *PluginData);
+
+static int event_wait(struct __hexe_Event_t *Event, void *PluginData);
+
+static int event_check(struct __hexe_Event_t *Event, void *PluginData);
+
+static void *plugin_malloc(unsigned size,
+                           unsigned alignment,
+                           void *PluginData);
+
+static int plugin_free(void *ptr, void *PluginData);
+
+static int load_code_from_file(const char *base_filename,
+                               const char *fextension,
+                               void *PluginData);
+
+static int load_code_from_elf_section(const char *base_section_name,
+                                      const char *fextension,
+                                      void *PluginData);
+
+static int load_code_vendor(void *PluginData);
+
+static int destroy(void *PluginData);
+
+static const char *plugin_info(void *PluginData)
+{
+  return "Accelerator Debug Plugin";
+};
+
+struct Hexe_Plugin_Interface *Hexe_Accelerator_Debug_Plugin_init()
+{
+  struct Hexe_Accelerator_Debug_Plugin *HP =
+    malloc( sizeof(struct Hexe_Accelerator_Debug_Plugin) );
+
+  //set the vtable
+  HP->base.runtime_sched = runtime_sched;
+  HP->base.dispatch = dispatch;
+  HP->base.enforce_coherency = enforce_coherency;
+  HP->base.event_wait = event_wait;
+  HP->base.event_check = event_check;
+  HP->base.malloc = plugin_malloc;
+  HP->base.free = plugin_free;
+  HP->base.load_code_from_file = load_code_from_file;
+  HP->base.load_code_from_elf_section = load_code_from_elf_section;
+  HP->base.load_code_vendor = load_code_vendor;
+  HP->base.destroy = destroy;
+  HP->base.plugin_info = plugin_info;
+  HP->arg_shared_buffer = malloc(1*MB);
+
+  /* reserve the first buffer slot for storing the
+   * the marshalled call arguments */
+  HP->remote_buffer_slots[0].pv = HP->arg_shared_buffer;
+  HP->remote_buffer_slots[0].nLen = 1*MB;
+
+  /* Initialize the allocation list */
+  HP->allocation_list_head = NULL;
+
+  HP->dlhandle=NULL;
+  HP->invoke=NULL;
+
+  return (struct Hexe_Plugin_Interface *) HP;
+}
+
+static int destroy(void *PluginData)
+{
+  struct Hexe_Accelerator_Debug_Plugin *HP =
+    (struct Hexe_Accelerator_Debug_Plugin *) PluginData;
+
+  //close the shared library
+  if (HP->dlhandle && dlclose(HP->dlhandle))
+    return -1;
+
+  plugin_free(HP->arg_shared_buffer, HP);
+
+  free(HP);
+  return 0;
+}
+
+
+static int runtime_sched(unsigned function_id,
+                         struct __hexe_MemAccessInfo *InfArray,
+                         unsigned num_elems,
+                         struct __hexe_KernelInfo *KI,
+                         void *PluginData)
+{
+  // always offload
+  return TRUE;
+}
+
+static struct __hexe_Event_t *dispatch(unsigned function_id,
+                                       void *args,
+                                       unsigned args_size,
+                                       void *PluginData)
+{
+  struct Hexe_Accelerator_Debug_Plugin *HP =
+    (struct Hexe_Accelerator_Debug_Plugin *) PluginData;
+
+  //copy arguments on the shared buffer
+  memcpy(HP->arg_shared_buffer, args, args_size);
+  //TODO optimize by updating size in remote_buffer_slots[0]
+
+  uint32_t dwScalars = REMOTE_SCALARS_MAKEX(0, function_id,
+      HP->write_buffer_num, HP->read_buffer_num, 0, 0);
+
+  if (HP->invoke(dwScalars, HP->remote_buffer_slots)) {
+    __hexe_error_message(PluginData, "dispatch operation failed");
+    exit(-1);
+  }
+
+  return (struct __hexe_Event_t *)0;
+}
+
+static void enforce_coherency(unsigned function_id,
+                              struct __hexe_MemAccessInfo *InfArray,
+                              unsigned num_elems,
+                              void *PluginData)
+{
+  struct Hexe_Accelerator_Debug_Plugin *HP =
+    (struct Hexe_Accelerator_Debug_Plugin *) PluginData;
+
+  unsigned i;
+  /* We reserve the first slot of remote_buffer_slots for
+   * passing the scalar function call arguments */
+
+  /* We update the remote_buffer_slots to keep track of the memory
+   * segments used by the function that is called by __hexe_dispatch */
+  for (i = 0; i<num_elems; ++i) {
+
+    struct Allocation_Node query;
+    query.ptr = InfArray[i].ptr;
+    struct Allocation_Node *found = NULL;
+    LL_SEARCH(HP->allocation_list_head, found, &query, alloc_match);
+
+    assert( found );
+    unsigned segm_size = found -> size -
+      ( ((size_t) InfArray[i].ptr) - ((size_t) found->ptr) );
+    /* write it as input buffer */
+    HP->remote_buffer_slots[i+1].pv = InfArray[i].ptr;
+    HP->remote_buffer_slots[i+1].nLen = segm_size;
+    /* write it as output buffer */
+    HP->remote_buffer_slots[i+1+num_elems].pv = InfArray[i].ptr;
+    HP->remote_buffer_slots[i+1+num_elems].nLen = segm_size;
+  }
+
+  HP->write_buffer_num = num_elems+1;
+  HP->read_buffer_num = num_elems+1;
+}
+
+static int event_wait(struct __hexe_Event_t *Event, void *PluginData)
+{
+  /* empty */
+  return 0;
+}
+
+static int event_check(struct __hexe_Event_t *Event, void *PluginData)
+{
+  /* empty */
+  return 0;
+}
+
+static void *plugin_malloc(unsigned size, unsigned alignment,
+                           void *PluginData)
+{
+  struct Hexe_Accelerator_Debug_Plugin *HP =
+    (struct Hexe_Accelerator_Debug_Plugin *) PluginData;
+
+  /* the plugin serves  the allocation */
+  void *ptr = malloc(size);
+
+  /* keep track of the allocation on the list */
+  struct Allocation_Node *AN = malloc( sizeof(struct Allocation_Node) );
+  AN->ptr = ptr;
+  AN->size = size;
+  LL_APPEND(HP->allocation_list_head, AN);
+
+  return ptr;
+}
+
+static int plugin_free(void *ptr, void *PluginData)
+{
+  struct Hexe_Accelerator_Debug_Plugin *HP =
+    (struct Hexe_Accelerator_Debug_Plugin *) PluginData;
+
+  struct Allocation_Node query;
+  query.ptr = ptr;
+  struct Allocation_Node *found = NULL;
+
+ /* check if the allocation has been served by the plugin */
+  LL_SEARCH(HP->allocation_list_head, found, &query, alloc_comperator);
+
+  /* if yes, release the memory and return TRUE */
+  if (found) {
+    free(ptr);
+    LL_DELETE(HP->allocation_list_head, found);
+    return TRUE;
+  }
+
+  /* Otherwise, return FALSE */
+  return FALSE;
+}
+
+static int load_code_from_file(const char *base_filename,
+                               const char *fextension,
+                               void *PluginData)
+{
+  /* empty not supported yet */
+  exit(-1);
+  return 0;
+}
+
+static int load_code_from_elf_section(const char *base_section_name,
+                                      const char *fextension,
+                                      void *PluginData)
+{
+  /* empty not supported yet */
+  exit(-1);
+  return 0;
+}
+
+static int load_code_vendor(void *PluginData)
+{
+  struct Hexe_Accelerator_Debug_Plugin *HP =
+    (struct Hexe_Accelerator_Debug_Plugin *) PluginData;
+
+  /* loads the code from the dynamic library */
+  HP->dlhandle = dlopen("libaccelerator_debug.so", RTLD_NOW);
+  if (!HP->dlhandle) {
+    __hexe_error_message(PluginData, "failed to open the dynamic library");
+    return -1;
+  }
+
+  /* gets the __hexe_skel_invoke function symbol */
+  HP->invoke = dlsym(HP->dlhandle, "__hexe_skel_invoke");
+  if (!HP->invoke) {
+    __hexe_error_message(PluginData, "failed to get the skel_invoke symbol");
+    return -1;
+  }
+
+  return 0;
+}

lib/hexe/plugins/hexe_hexagon_plugin.c

+/* === -- hexe_hexagon_plugin.c -----------------------------------*- C -*-=== *
+*
+*                     The LLVM Compiler Infrastructure
+*
+* This file is distributed under the University of Illinois Open Source
+* License. See LICENSE.TXT for details.
+*
+* === --------------------------------------------------------------------=== */
+/**
+* \file
+* This file is part of the runtime environment of the Heterogeneous Execution
+* Engine. It defines the Hexagon plugin.
+* === --------------------------------------------------------------------=== */
+
+
+#include "hexe_internal.h"
+#include "uthash/utlist.h"
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+
+
+/* Interface to the rpcmem library as it is provided
+* by the Qualcomm SDK. These calls use special
+* Memory Allocators to provide memory accessible
+* both by the host and Hexagon DSP environemnts */
+#define RPCMEM_HEAP_DEFAULT 0x80000000
+void rpcmem_init(void);
+void rpcmem_deinit(void);
+void *rpcmem_alloc(int heapid, unsigned flags, int size);
+void rpcmem_free(void* po);
+
+/* Interface to the fastrpc library of the Qualcomm SDK.
+ * This library provides functions for performing
+ * remote process calls on the DSP. */
+typedef uint32_t remote_handle;
+
+typedef struct {
+   void *pv;
+   size_t nLen;
+} remote_buf;
+
+//fastrpc calls
+int remote_handle_open(const char* name, remote_handle *ph);
+int remote_handle_close(remote_handle h);
+int remote_handle_invoke(remote_handle h, uint32_t dwScalars,
+                         remote_buf *pra);
+
+#define REMOTE_SCALARS_MAKEX(nAttr, nMethod, nIn, nOut, noIn, noOut) \
+          ((((uint32_t)   (nAttr) &  0x7) << 29) | \
+           (((uint32_t) (nMethod) & 0x1f) << 24) | \
+           (((uint32_t)     (nIn) & 0xff) << 16) | \
+           (((uint32_t)    (nOut) & 0xff) <<  8) | \
+           (((uint32_t)    (noIn) & 0x0f) <<  4) | \
+            ((uint32_t)   (noOut) & 0x0f))
+
+
+#define MB (1<<20)
+#define TRUE 1
+#define FALSE 0
+
+
+/* Link List Node definition and comparator functions.
+ * We use a Linked List to keep tract of the memory
+ * allocations served by rpcmem */
+
+struct Allocation_Node {
+  struct Allocation_Node *next;
+  void *ptr;
+  unsigned size;
+};
+
+/* Compares two nodes */
+static int alloc_comparator(struct Allocation_Node *n1,
+                            struct Allocation_Node *n2)
+{
+  return ( (size_t) n1->ptr) ^ ( (size_t) n2->ptr); //returns 0 if equal
+}
+
+/* checks the allocation ranges for a pointer address */
+static int alloc_match(struct Allocation_Node *n1,
+                       struct Allocation_Node *n2)
+{
+  const char *n1p = (const char *)n1->ptr;
+  const char *n2p = (const char *)n2->ptr;
+
+  if ((n2p >= n1p) && (n2p < n1p+n1->size))
+    return 0;
+
+  return -1;
+}
+
+/* Hexagon Plugin struct definition */
+struct Hexe_Hexagon_Plugin {
+  struct Hexe_Plugin_Interface base; /* vtable */
+  remote_handle hexe_handle;
+  void *arg_shared_buffer;
+  remote_buf remote_buffer_slots[256];
+  unsigned read_buffer_num, write_buffer_num;
+
+  struct Allocation_Node *allocation_list_head;
+};
+
+/* forward declaratin of the Plugin Interface Implementation */
+static int runtime_sched(unsigned function_id,
+                         struct __hexe_MemAccessInfo *InfArray,
+                         unsigned num_elems,
+                         struct __hexe_KernelInfo *KI,
+                         void *PluginData);
+
+static struct __hexe_Event_t *dispatch(unsigned function_id,
+                                       void *args,
+                                       unsigned args_size,
+                                       void *PluginData);
+
+static void enforce_coherency(unsigned function_id,
+                              struct __hexe_MemAccessInfo *InfArray,
+                              unsigned num_elems,
+                              void *PluginData);
+
+static int event_wait(struct __hexe_Event_t *Event, void *PluginData);
+
+static int event_check(struct __hexe_Event_t *Event, void *PluginData);
+
+static void *plugin_malloc(unsigned size, unsigned alignment, void *PluginData);
+
+static int plugin_free(void *ptr, void *PluginData);
+
+static int load_code_from_file(const char *base_filename,
+                               const char *fextension,
+                               void *PluginData);
+
+static int load_code_from_elf_section(const char *base_section_name,
+                                      const char *fextension,
+                                      void *PluginData);
+
+static int load_code_vendor(void *PluginData);
+
+static int destroy(void *PluginData);
+
+static const char *plugin_info(void *PluginData)
+{
+  return "Qualcomm Hexagon Plugin";
+};
+
+ /* This function initialize an instance of the plugin */
+struct Hexe_Plugin_Interface *Hexe_Hexagon_Plugin_init()
+{
+  struct Hexe_Hexagon_Plugin *HP = malloc( sizeof(struct Hexe_Hexagon_Plugin) );
+
+  //set the vtable
+  HP->base.runtime_sched = runtime_sched;
+  HP->base.dispatch = dispatch;
+  HP->base.enforce_coherency = enforce_coherency;
+  HP->base.event_wait = event_wait;
+  HP->base.event_check = event_check;
+  HP->base.malloc = plugin_malloc;
+  HP->base.free = plugin_free;
+  HP->base.load_code_from_file = load_code_from_file;
+  HP->base.load_code_from_elf_section = load_code_from_elf_section;
+  HP->base.load_code_vendor = load_code_vendor;
+  HP->base.destroy = destroy;
+  HP->base.plugin_info = plugin_info;
+
+  /* rpcmem initialization */
+  rpcmem_init();
+  HP->arg_shared_buffer = plugin_malloc(1*MB, 0, HP);
+
+  /* reserve the first buffer slot for storing the
+   * the marshalled call arguments */
+  HP->remote_buffer_slots[0].pv = HP->arg_shared_buffer;
+  HP->remote_buffer_slots[0].nLen = 1*MB;
+
+  /* Initialize the allocation list */
+  HP->allocation_list_head = NULL;
+
+  return (struct Hexe_Plugin_Interface *) HP;
+}
+
+static int destroy(void *PluginData)
+{
+  struct Hexe_Hexagon_Plugin *HP = (struct Hexe_Hexagon_Plugin *) PluginData;
+
+  /* release the farst rpc handler */
+  if (remote_handle_close(HP->hexe_handle))
+    return -1;
+
+
+  plugin_free(HP->arg_shared_buffer, HP);
+
+  /* rpcmem release */
+  rpcmem_deinit();
+
+  free(HP);
+  return 0;
+}
+
+
+static int runtime_sched(unsigned function_id,
+                         struct __hexe_MemAccessInfo *InfArray,
+                         unsigned num_elems,
+                         struct __hexe_KernelInfo *KI,
+                         void *PluginData)
+{
+  /* always offload to the dsp */
+  return TRUE;
+}
+
+static struct __hexe_Event_t *dispatch(unsigned function_id,
+                                       void *args,
+                                       unsigned args_size,
+                                       void *PluginData)
+{
+  struct Hexe_Hexagon_Plugin *HP = (struct Hexe_Hexagon_Plugin *) PluginData;
+
+  /* copy marshalled arguments on the shared buffer */
+  memcpy(HP->arg_shared_buffer, args, args_size);
+  //TODO optimize by updating size in remote_buffer_slots[0]
+
+  ///call fastrpc remote invoke
+  uint32_t dwScalars = REMOTE_SCALARS_MAKEX(0, function_id,
+      HP->write_buffer_num, HP->read_buffer_num, 0, 0);
+
+  if (remote_handle_invoke(HP->hexe_handle, dwScalars,
+        HP->remote_buffer_slots)) {
+    __hexe_error_message(PluginData, "dispatch operation failed");
+    exit(-1);
+  }
+
+  return (struct __hexe_Event_t *)0;
+}
+
+static void enforce_coherency(unsigned function_id,
+                              struct __hexe_MemAccessInfo *InfArray,
+                              unsigned num_elems,
+                              void *PluginData)
+{
+  struct Hexe_Hexagon_Plugin *HP = (struct Hexe_Hexagon_Plugin *) PluginData;
+
+  unsigned i;
+  /* We reserve the first slot of remote_buffer_slots for
+   * passing the scalar function call arguments */
+
+  /* We update the remote_buffer_slots to keep track of the memory
+   * segments used by the function that will be called on the dsp. */
+  for (i = 0; i<num_elems; ++i) {
+    struct Allocation_Node query;
+    query.ptr = InfArray[i].ptr;
+    struct Allocation_Node *found = NULL;
+    LL_SEARCH(HP->allocation_list_head, found, &query, alloc_match);
+
+    assert( found );
+    unsigned segm_size = found -> size -
+      ( ((size_t) InfArray[i].ptr) - ((size_t) found->ptr) );
+    //write it as input buffer
+    HP->remote_buffer_slots[i+1].pv = InfArray[i].ptr;
+    HP->remote_buffer_slots[i+1].nLen = segm_size;
+    //write it as output buffer
+    HP->remote_buffer_slots[i+1+num_elems].pv = InfArray[i].ptr;
+    HP->remote_buffer_slots[i+1+num_elems].nLen = segm_size;
+  }
+
+  HP->write_buffer_num = num_elems+1;
+  HP->read_buffer_num = num_elems+1;
+}
+
+static int event_wait(struct __hexe_Event_t *Event, void *PluginData)
+{
+  /* empty */
+  return 0;
+}
+
+static int event_check(struct __hexe_Event_t *Event, void *PluginData)
+{
+  /* empty */
+  return 0;
+}
+
+static void *plugin_malloc(unsigned size, unsigned alignment,
+                           void *PluginData)
+{
+  struct Hexe_Hexagon_Plugin *HP = (struct Hexe_Hexagon_Plugin *) PluginData;
+
+  /* use rpcmem for the allocation */
+  void *ptr = rpcmem_alloc(RPCMEM_HEAP_DEFAULT, 0, size);
+
+  /* keep track of the allocation on the list */
+  struct Allocation_Node *AN = malloc( sizeof(struct Allocation_Node) );
+  AN->ptr = ptr;
+  AN->size = size;
+  LL_APPEND(HP->allocation_list_head, AN);
+
+  return ptr;
+}
+
+static int plugin_free(void *ptr, void *PluginData)
+{
+  struct Hexe_Hexagon_Plugin *HP = (struct Hexe_Hexagon_Plugin *) PluginData;
+
+  struct Allocation_Node query;
+  query.ptr = ptr;
+  struct Allocation_Node *found = NULL;
+
+  /* check if the allocation has been served by rpcmem */
+  LL_SEARCH(HP->allocation_list_head, found, &query, alloc_comparator);
+
+  /* if yes, release the memory and return TRUE */
+  if (found) {
+    rpcmem_free(ptr);
+    LL_DELETE(HP->allocation_list_head, found);
+    return TRUE;
+  }
+
+  /* Otherwise, return FALSE */
+  return FALSE;
+}
+
+static int load_code_from_file(const char *base_filename,
+                               const char *fextension,
+                               void *PluginData)
+{
+  /* empty not supported yet */
+  exit(-1);
+  return 0;
+}
+
+static int load_code_from_elf_section(const char *base_section_name,
+                                      const char *fextension,
+                                      void *PluginData)
+{
+  /* empty not supported yet */
+  exit(-1);
+  return 0;
+}
+
+static int load_code_vendor(void *PluginData)
+{
+  struct Hexe_Hexagon_Plugin *HP = (struct Hexe_Hexagon_Plugin *) PluginData;
+
+  /* loads the code on the dsp side */
+  if (remote_handle_open("__hexe", &(HP->hexe_handle))) {
+    __hexe_error_message(PluginData, "failed to load the code on the DSP");
+    return -1;
+  }
+
+  return 0;
+}

lib/hexe/uthash/utlist.h

+/*
+Copyright (c) 2007-2014, Troy D. Hanson   http://troydhanson.github.com/uthash/
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef UTLIST_H
+#define UTLIST_H
+
+#define UTLIST_VERSION 1.9.9
+
+#include <assert.h>
+
+/*
+ * This file contains macros to manipulate singly and doubly-linked lists.
+ *
+ * 1. LL_ macros:  singly-linked lists.
+ * 2. DL_ macros:  doubly-linked lists.
+ * 3. CDL_ macros: circular doubly-linked lists.
+ *
+ * To use singly-linked lists, your structure must have a "next" pointer.
+ * To use doubly-linked lists, your structure must "prev" and "next" pointers.
+ * Either way, the pointer to the head of the list must be initialized to NULL.
+ *
+ * ----------------.EXAMPLE -------------------------
+ * struct item {
+ *      int id;
+ *      struct item *prev, *next;
+ * }
+ *
+ * struct item *list = NULL:
+ *
+ * int main() {
+ *      struct item *item;
+ *      ... allocate and populate item ...
+ *      DL_APPEND(list, item);
+ * }
+ * --------------------------------------------------
+ *
+ * For doubly-linked lists, the append and delete macros are O(1)
+ * For singly-linked lists, append and delete are O(n) but prepend is O(1)
+ * The sort macro is O(n log(n)) for all types of single/double/circular lists.
+ */
+
+/* These macros use decltype or the earlier __typeof GNU extension.
+   As decltype is only available in newer compilers (VS2010 or gcc 4.3+
+   when compiling c++ code), this code uses whatever method is needed
+   or, for VS2008 where neither is available, uses casting workarounds. */
+#ifdef _MSC_VER            /* MS compiler */
+#if _MSC_VER >= 1600 && defined(__cplusplus)  /* VS2010 or newer in C++ mode */
+#define LDECLTYPE(x) decltype(x)
+#else                     /* VS2008 or older (or VS2010 in C mode) */
+#define NO_DECLTYPE
+#define LDECLTYPE(x) char*
+#endif
+#elif defined(__ICCARM__)
+#define NO_DECLTYPE
+#define LDECLTYPE(x) char*
+#else                      /* GNU, Sun and other compilers */
+#define LDECLTYPE(x) __typeof(x)
+#endif
+
+/* for VS2008 we use some workarounds to get around the lack of decltype,
+ * namely, we always reassign our tmp variable to the list head if we need
+ * to dereference its prev/next pointers, and save/restore the real head.*/
+#ifdef NO_DECLTYPE
+#define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
+#define _NEXT(elt,list,next) ((char*)((list)->next))
+#define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
+/* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */
+#define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
+#define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
+#define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
+#else
+#define _SV(elt,list)
+#define _NEXT(elt,list,next) ((elt)->next)
+#define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
+/* #define _PREV(elt,list,prev) ((elt)->prev) */
+#define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
+#define _RS(list)
+#define _CASTASGN(a,b) (a)=(b)
+#endif
+
+/******************************************************************************
+ * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort    *
+ * Unwieldy variable names used here to avoid shadowing passed-in variables.  *
+ *****************************************************************************/
+#define LL_SORT(list, cmp)                                                                     \
+    LL_SORT2(list, cmp, next)
+
+#define LL_SORT2(list, cmp, next)                                                              \
+do {                                                                                           \
+  LDECLTYPE(list) _ls_p;                                                                       \
+  LDECLTYPE(list) _ls_q;                                                                       \
+  LDECLTYPE(list) _ls_e;                                                                       \
+  LDECLTYPE(list) _ls_tail;                                                                    \
+  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping;                       \
+  if (list) {                                                                                  \
+    _ls_insize = 1;                                                                            \
+    _ls_looping = 1;                                                                           \
+    while (_ls_looping) {                                                                      \
+      _CASTASGN(_ls_p,list);                                                                   \
+      list = NULL;                                                                             \
+      _ls_tail = NULL;                                                                         \
+      _ls_nmerges = 0;                                                                         \
+      while (_ls_p) {                                                                          \
+        _ls_nmerges++;                                                                         \
+        _ls_q = _ls_p;                                                                         \
+        _ls_psize = 0;                                                                         \
+        for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) {                                         \
+          _ls_psize++;                                                                         \
+          _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list);                          \
+          if (!_ls_q) break;                                                                   \
+        }                                                                                      \
+        _ls_qsize = _ls_insize;                                                                \
+        while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) {                                    \
+          if (_ls_psize == 0) {                                                                \
+            _ls_e = _ls_q; _SV(_ls_q,list); _ls_q =                                            \
+              _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--;                                  \
+          } else if (_ls_qsize == 0 || !_ls_q) {                                               \
+            _ls_e = _ls_p; _SV(_ls_p,list); _ls_p =                                            \
+              _NEXT(_ls_p,list,next); _RS(list); _ls_psize--;                                  \
+          } else if (cmp(_ls_p,_ls_q) <= 0) {                                                  \
+            _ls_e = _ls_p; _SV(_ls_p,list); _ls_p =                                            \
+              _NEXT(_ls_p,list,next); _RS(list); _ls_psize--;                                  \
+          } else {                                                                             \
+            _ls_e = _ls_q; _SV(_ls_q,list); _ls_q =                                            \
+              _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--;                                  \
+          }                                                                                    \
+          if (_ls_tail) {                                                                      \
+            _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list);                \
+          } else {                                                                             \
+            _CASTASGN(list,_ls_e);                                                             \
+          }                                                                                    \
+          _ls_tail = _ls_e;                                                                    \
+        }                                                                                      \
+        _ls_p = _ls_q;                                                                         \
+      }                                                                                        \
+      if (_ls_tail) {                                                                          \
+        _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list);                     \
+      }                                                                                        \
+      if (_ls_nmerges <= 1) {                                                                  \
+        _ls_looping=0;                                                                         \
+      }                                                                                        \
+      _ls_insize *= 2;                                                                         \
+    }                                                                                          \
+  }                                                                                            \
+} while (0)
+
+
+#define DL_SORT(list, cmp)                                                                     \
+    DL_SORT2(list, cmp, prev, next)
+
+#define DL_SORT2(list, cmp, prev, next)                                                        \
+do {                                                                                           \
+  LDECLTYPE(list) _ls_p;                                                                       \
+  LDECLTYPE(list) _ls_q;                                                                       \
+  LDECLTYPE(list) _ls_e;                                                                       \
+  LDECLTYPE(list) _ls_tail;                                                                    \
+  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping;                       \
+  if (list) {                                                                                  \
+    _ls_insize = 1;                                                                            \
+    _ls_looping = 1;                                                                           \
+    while (_ls_looping) {                                                                      \
+      _CASTASGN(_ls_p,list);                                                                   \
+      list = NULL;                                                                             \
+      _ls_tail = NULL;                                                                         \
+      _ls_nmerges = 0;                                                                         \
+      while (_ls_p) {                                                                          \
+        _ls_nmerges++;                                                                         \
+        _ls_q = _ls_p;                                                                         \
+        _ls_psize = 0;                                                                         \
+        for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) {                                         \
+          _ls_psize++;                                                                         \
+          _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list);                          \
+          if (!_ls_q) break;                                                                   \
+        }                                                                                      \
+        _ls_qsize = _ls_insize;                                                                \
+        while ((_ls_psize > 0) || ((_ls_qsize > 0) && _ls_q)) {                                \
+          if (_ls_psize == 0) {                                                                \
+            _ls_e = _ls_q; _SV(_ls_q,list); _ls_q =                                            \
+              _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--;                                  \
+          } else if ((_ls_qsize == 0) || (!_ls_q)) {                                           \
+            _ls_e = _ls_p; _SV(_ls_p,list); _ls_p =                                            \
+              _NEXT(_ls_p,list,next); _RS(list); _ls_psize--;                                  \
+          } else if (cmp(_ls_p,_ls_q) <= 0) {                                                  \
+            _ls_e = _ls_p; _SV(_ls_p,list); _ls_p =                                            \
+              _NEXT(_ls_p,list,next); _RS(list); _ls_psize--;                                  \
+          } else {                                                                             \
+            _ls_e = _ls_q; _SV(_ls_q,list); _ls_q =                                            \
+              _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--;                                  \
+          }                                                                                    \
+          if (_ls_tail) {                                                                      \
+            _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list);                \
+          } else {                                                                             \
+            _CASTASGN(list,_ls_e);                                                             \
+          }                                                                                    \
+          _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list);                     \
+          _ls_tail = _ls_e;                                                                    \
+        }                                                                                      \
+        _ls_p = _ls_q;                                                                         \
+      }                                                                                        \
+      _CASTASGN(list->prev, _ls_tail);                                                         \
+      _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list);                       \
+      if (_ls_nmerges <= 1) {                                                                  \
+        _ls_looping=0;                                                                         \
+      }                                                                                        \
+      _ls_insize *= 2;                                                                         \
+    }                                                                                          \
+  }                                                                                            \
+} while (0)
+
+#define CDL_SORT(list, cmp)                                                                    \
+    CDL_SORT2(list, cmp, prev, next)
+
+#define CDL_SORT2(list, cmp, prev, next)                                                       \
+do {                                                                                           \
+  LDECLTYPE(list) _ls_p;                                                                       \
+  LDECLTYPE(list) _ls_q;                                                                       \
+  LDECLTYPE(list) _ls_e;                                                                       \
+  LDECLTYPE(list) _ls_tail;                                                                    \
+  LDECLTYPE(list) _ls_oldhead;                                                                 \
+  LDECLTYPE(list) _tmp;                                                                        \
+  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping;                       \
+  if (list) {                                                                                  \
+    _ls_insize = 1;                                                                            \
+    _ls_looping = 1;                                                                           \
+    while (_ls_looping) {                                                                      \
+      _CASTASGN(_ls_p,list);                                                                   \
+      _CASTASGN(_ls_oldhead,list);                                                             \
+      list = NULL;                                                                             \
+      _ls_tail = NULL;                                                                         \
+      _ls_nmerges = 0;                                                                         \
+      while (_ls_p) {                                                                          \
+        _ls_nmerges++;                                                                         \
+        _ls_q = _ls_p;                                                                         \
+        _ls_psize = 0;                                                                         \
+        for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) {                                         \
+          _ls_psize++;                                                                         \
+          _SV(_ls_q,list);                                                                     \
+          if (_NEXT(_ls_q,list,next) == _ls_oldhead) {                                         \
+            _ls_q = NULL;                                                                      \
+          } else {                                                                             \
+            _ls_q = _NEXT(_ls_q,list,next);                                                    \
+          }                                                                                    \
+          _RS(list);                                                                           \
+          if (!_ls_q) break;                                                                   \
+        }                                                                                      \
+        _ls_qsize = _ls_insize;                                                                \
+        while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) {                                    \
+          if (_ls_psize == 0) {                                                                \
+            _ls_e = _ls_q; _SV(_ls_q,list); _ls_q =                                            \
+              _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--;                                  \
+            if (_ls_q == _ls_oldhead) { _ls_q = NULL; }                                        \
+          } else if (_ls_qsize == 0 || !_ls_q) {                                               \
+            _ls_e = _ls_p; _SV(_ls_p,list); _ls_p =                                            \
+              _NEXT(_ls_p,list,next); _RS(list); _ls_psize--;                                  \
+            if (_ls_p == _ls_oldhead) { _ls_p = NULL; }                                        \
+          } else if (cmp(_ls_p,_ls_q) <= 0) {                                                  \
+            _ls_e = _ls_p; _SV(_ls_p,list); _ls_p =                                            \
+              _NEXT(_ls_p,list,next); _RS(list); _ls_psize--;                                  \
+            if (_ls_p == _ls_oldhead) { _ls_p = NULL; }                                        \
+          } else {                                                                             \
+            _ls_e = _ls_q; _SV(_ls_q,list); _ls_q =                                            \
+              _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--;                                  \
+            if (_ls_q == _ls_oldhead) { _ls_q = NULL; }                                        \
+          }                                                                                    \
+          if (_ls_tail) {                                                                      \
+            _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list);                \
+          } else {                                                                             \
+            _CASTASGN(list,_ls_e);                                                             \
+          }                                                                                    \
+          _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list);                     \
+          _ls_tail = _ls_e;                                                                    \
+        }                                                                                      \
+        _ls_p = _ls_q;                                                                         \
+      }                                                                                        \
+      _CASTASGN(list->prev,_ls_tail);                                                          \
+      _CASTASGN(_tmp,list);                                                                    \
+      _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list);                       \
+      if (_ls_nmerges <= 1) {                                                                  \
+        _ls_looping=0;                                                                         \
+      }                                                                                        \
+      _ls_insize *= 2;                                                                         \
+    }                                                                                          \
+  }                                                                                            \
+} while (0)
+
+/******************************************************************************
+ * singly linked list macros (non-circular)                                   *
+ *****************************************************************************/
+#define LL_PREPEND(head,add)                                                                   \
+    LL_PREPEND2(head,add,next)
+
+#define LL_PREPEND2(head,add,next)                                                             \
+do {                                                                                           \
+  (add)->next = head;                                                                          \
+  head = add;                                                                                  \
+} while (0)
+
+#define LL_CONCAT(head1,head2)                                                                 \
+    LL_CONCAT2(head1,head2,next)
+
+#define LL_CONCAT2(head1,head2,next)                                                           \
+do {                                                                                           \
+  LDECLTYPE(head1) _tmp;                                                                       \
+  if (head1) {                                                                                 \
+    _tmp = head1;                                                                              \
+    while (_tmp->next) { _tmp = _tmp->next; }                                                  \
+    _tmp->next=(head2);                                                                        \
+  } else {                                                                                     \
+    (head1)=(head2);                                                                           \
+  }                                                                                            \
+} while (0)
+
+#define LL_APPEND(head,add)                                                                    \
+    LL_APPEND2(head,add,next)
+
+#define LL_APPEND2(head,add,next)                                                              \
+do {                                                                                           \
+  LDECLTYPE(head) _tmp;                                                                        \
+  (add)->next=NULL;                                                                            \
+  if (head) {                                                                                  \
+    _tmp = head;                                                                               \
+    while (_tmp->next) { _tmp = _tmp->next; }                                                  \
+    _tmp->next=(add);                                                                          \
+  } else {                                                                                     \
+    (head)=(add);                                                                              \
+  }                                                                                            \
+} while (0)
+
+#define LL_DELETE(head,del)                                                                    \
+    LL_DELETE2(head,del,next)
+
+#define LL_DELETE2(head,del,next)                                                              \
+do {                                                                                           \
+  LDECLTYPE(head) _tmp;                                                                        \
+  if ((head) == (del)) {                                                                       \
+    (head)=(head)->next;                                                                       \
+  } else {                                                                                     \
+    _tmp = head;                                                                               \
+    while (_tmp->next && (_tmp->next != (del))) {                                              \
+      _tmp = _tmp->next;                                                                       \
+    }                                                                                          \
+    if (_tmp->next) {                                                                          \
+      _tmp->next = ((del)->next);                                                              \
+    }                                                                                          \
+  }                                                                                            \
+} while (0)
+
+/* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
+#define LL_APPEND_VS2008(head,add)                                                             \
+    LL_APPEND2_VS2008(head,add,next)
+
+#define LL_APPEND2_VS2008(head,add,next)                                                       \
+do {                                                                                           \
+  if (head) {                                                                                  \
+    (add)->next = head;     /* use add->next as a temp variable */                             \
+    while ((add)->next->next) { (add)->next = (add)->next->next; }                             \
+    (add)->next->next=(add);                                                                   \
+  } else {                                                                                     \
+    (head)=(add);                                                                              \
+  }                                                                                            \
+  (add)->next=NULL;                                                                            \
+} while (0)
+
+#define LL_DELETE_VS2008(head,del)                                                             \
+    LL_DELETE2_VS2008(head,del,next)
+
+#define LL_DELETE2_VS2008(head,del,next)                                                       \
+do {                                                                                           \
+  if ((head) == (del)) {                                                                       \
+    (head)=(head)->next;                                                                       \
+  } else {                                                                                     \
+    char *_tmp = (char*)(head);                                                                \
+    while ((head)->next && ((head)->next != (del))) {                                          \
+      head = (head)->next;                                                                     \
+    }                                                                                          \
+    if ((head)->next) {                                                                        \
+      (head)->next = ((del)->next);                                                            \
+    }                                                                                          \
+    {                                                                                          \
+      char **_head_alias = (char**)&(head);                                                    \
+      *_head_alias = _tmp;                                                                     \
+    }                                                                                          \
+  }                                                                                            \
+} while (0)
+#ifdef NO_DECLTYPE
+#undef LL_APPEND
+#define LL_APPEND LL_APPEND_VS2008
+#undef LL_DELETE
+#define LL_DELETE LL_DELETE_VS2008
+#undef LL_DELETE2
+#define LL_DELETE2 LL_DELETE2_VS2008
+#undef LL_APPEND2
+#define LL_APPEND2 LL_APPEND2_VS2008
+#undef LL_CONCAT /* no LL_CONCAT_VS2008 */
+#undef DL_CONCAT /* no DL_CONCAT_VS2008 */
+#endif
+/* end VS2008 replacements */
+
+#define LL_COUNT(head,el,counter)                                                              \
+    LL_COUNT2(head,el,counter,next)                                                            \
+
+#define LL_COUNT2(head,el,counter,next)                                                        \
+{                                                                                              \
+    counter = 0;                                                                               \
+    LL_FOREACH2(head,el,next){ ++counter; }                                                    \
+}
+
+#define LL_FOREACH(head,el)                                                                    \
+    LL_FOREACH2(head,el,next)
+
+#define LL_FOREACH2(head,el,next)                                                              \
+    for(el=head;el;el=(el)->next)
+
+#define LL_FOREACH_SAFE(head,el,tmp)                                                           \
+    LL_FOREACH_SAFE2(head,el,tmp,next)
+
+#define LL_FOREACH_SAFE2(head,el,tmp,next)                                                     \
+  for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
+
+#define LL_SEARCH_SCALAR(head,out,field,val)                                                   \
+    LL_SEARCH_SCALAR2(head,out,field,val,next)
+
+#define LL_SEARCH_SCALAR2(head,out,field,val,next)                                             \
+do {                                                                                           \
+    LL_FOREACH2(head,out,next) {                                                               \
+      if ((out)->field == (val)) break;                                                        \
+    }                                                                                          \
+} while(0)
+
+#define LL_SEARCH(head,out,elt,cmp)                                                            \
+    LL_SEARCH2(head,out,elt,cmp,next)
+
+#define LL_SEARCH2(head,out,elt,cmp,next)                                                      \
+do {                                                                                           \
+    LL_FOREACH2(head,out,next) {                                                               \
+      if ((cmp(out,elt))==0) break;                                                            \
+    }                                                                                          \
+} while(0)
+
+#define LL_REPLACE_ELEM(head, el, add)                                                         \
+do {                                                                                           \
+ LDECLTYPE(head) _tmp;                                                                         \
+ assert(head != NULL);                                                                         \
+ assert(el != NULL);                                                                           \
+ assert(add != NULL);                                                                          \
+ (add)->next = (el)->next;                                                                     \
+ if ((head) == (el)) {                                                                         \
+  (head) = (add);                                                                              \
+ } else {                                                                                      \
+  _tmp = head;                                                                                 \
+  while (_tmp->next && (_tmp->next != (el))) {                                                 \
+   _tmp = _tmp->next;                                                                          \
+  }                                                                                            \
+  if (_tmp->next) {                                                                            \
+    _tmp->next = (add);                                                                        \
+  }                                                                                            \
+ }                                                                                             \
+} while (0)
+
+#define LL_PREPEND_ELEM(head, el, add)                                                         \
+do {                                                                                           \
+ LDECLTYPE(head) _tmp;                                                                         \
+ assert(head != NULL);                                                                         \
+ assert(el != NULL);                                                                           \
+ assert(add != NULL);                                                                          \
+ (add)->next = (el);                                                                           \
+ if ((head) == (el)) {                                                                         \
+  (head) = (add);                                                                              \
+ } else {                                                                                      \
+  _tmp = head;                                                                                 \
+  while (_tmp->next && (_tmp->next != (el))) {                                                 \
+   _tmp = _tmp->next;                                                                          \
+  }                                                                                            \
+  if (_tmp->next) {                                                                            \
+    _tmp->next = (add);                                                                        \
+  }                                                                                            \
+ }                                                                                             \
+} while (0)                                                                                    \
+
+
+/******************************************************************************
+ * doubly linked list macros (non-circular)                                   *
+ *****************************************************************************/
+#define DL_PREPEND(head,add)                                                                   \
+    DL_PREPEND2(head,add,prev,next)
+
+#define DL_PREPEND2(head,add,prev,next)                                                        \
+do {                                                                                           \
+ (add)->next = head;                                                                           \
+ if (head) {                                                                                   \
+   (add)->prev = (head)->prev;                                                                 \
+   (head)->prev = (add);                                                                       \
+ } else {                                                                                      \
+   (add)->prev = (add);                                                                        \
+ }                                                                                             \
+ (head) = (add);                                                                               \
+} while (0)
+
+#define DL_APPEND(head,add)                                                                    \
+    DL_APPEND2(head,add,prev,next)
+
+#define DL_APPEND2(head,add,prev,next)                                                         \
+do {                                                                                           \
+  if (head) {                                                                                  \
+      (add)->prev = (head)->prev;                                                              \
+      (head)->prev->next = (add);                                                              \
+      (head)->prev = (add);                                                                    \
+      (add)->next = NULL;                                                                      \
+  } else {                                                                                     \
+      (head)=(add);                                                                            \
+      (head)->prev = (head);                                                                   \
+      (head)->next = NULL;                                                                     \
+  }                                                                                            \
+} while (0)
+
+#define DL_CONCAT(head1,head2)                                                                 \
+    DL_CONCAT2(head1,head2,prev,next)
+
+#define DL_CONCAT2(head1,head2,prev,next)                                                      \
+do {                                                                                           \
+  LDECLTYPE(head1) _tmp;                                                                       \
+  if (head2) {                                                                                 \
+    if (head1) {                                                                               \
+        _tmp = (head2)->prev;                                                                  \
+        (head2)->prev = (head1)->prev;                                                         \
+        (head1)->prev->next = (head2);                                                         \
+        (head1)->prev = _tmp;                                                                  \
+    } else {                                                                                   \
+        (head1)=(head2);                                                                       \
+    }                                                                                          \
+  }                                                                                            \
+} while (0)
+
+#define DL_DELETE(head,del)                                                                    \
+    DL_DELETE2(head,del,prev,next)
+
+#define DL_DELETE2(head,del,prev,next)                                                         \
+do {                                                                                           \
+  assert((del)->prev != NULL);                                                                 \
+  if ((del)->prev == (del)) {                                                                  \
+      (head)=NULL;                                                                             \
+  } else if ((del)==(head)) {                                                                  \
+      (del)->next->prev = (del)->prev;                                                         \
+      (head) = (del)->next;                                                                    \
+  } else {                                                                                     \
+      (del)->prev->next = (del)->next;                                                         \
+      if ((del)->next) {                                                                       \
+          (del)->next->prev = (del)->prev;                                                     \
+      } else {                                                                                 \
+          (head)->prev = (del)->prev;                                                          \
+      }                                                                                        \
+  }                                                                                            \
+} while (0)
+
+#define DL_COUNT(head,el,counter)                                                              \
+    DL_COUNT2(head,el,counter,next)                                                            \
+
+#define DL_COUNT2(head,el,counter,next)                                                        \
+{                                                                                              \
+    counter = 0;                                                                               \
+    DL_FOREACH2(head,el,next){ ++counter; }                                                    \
+}
+
+#define DL_FOREACH(head,el)                                                                    \
+    DL_FOREACH2(head,el,next)
+
+#define DL_FOREACH2(head,el,next)                                                              \
+    for(el=head;el;el=(el)->next)
+
+/* this version is safe for deleting the elements during iteration */
+#define DL_FOREACH_SAFE(head,el,tmp)                                                           \
+    DL_FOREACH_SAFE2(head,el,tmp,next)
+
+#define DL_FOREACH_SAFE2(head,el,tmp,next)                                                     \
+  for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
+
+/* these are identical to their singly-linked list counterparts */
+#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
+#define DL_SEARCH LL_SEARCH
+#define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
+#define DL_SEARCH2 LL_SEARCH2
+
+#define DL_REPLACE_ELEM(head, el, add)                                                         \
+do {                                                                                           \
+ assert(head != NULL);                                                                         \
+ assert(el != NULL);                                                                           \
+ assert(add != NULL);                                                                          \
+ if ((head) == (el)) {                                                                         \
+  (head) = (add);                                                                              \
+  (add)->next = (el)->next;                                                                    \
+  if ((el)->next == NULL) {                                                                    \
+   (add)->prev = (add);                                                                        \
+  } else {                                                                                     \
+   (add)->prev = (el)->prev;                                                                   \
+   (add)->next->prev = (add);                                                                  \
+  }                                                                                            \
+ } else {                                                                                      \
+  (add)->next = (el)->next;                                                                    \
+  (add)->prev = (el)->prev;                                                                    \
+  (add)->prev->next = (add);                                                                   \
+  if ((el)->next == NULL) {                                                                    \
+   (head)->prev = (add);                                                                       \
+  } else {                                                                                     \
+   (add)->next->prev = (add);                                                                  \
+  }                                                                                            \
+ }                                                                                             \
+} while (0)
+
+#define DL_PREPEND_ELEM(head, el, add)                                                         \
+do {                                                                                           \
+ assert(head != NULL);                                                                         \
+ assert(el != NULL);                                                                           \
+ assert(add != NULL);                                                                          \
+ (add)->next = (el);                                                                           \
+ (add)->prev = (el)->prev;                                                                     \
+ (el)->prev = (add);                                                                           \
+ if ((head) == (el)) {                                                                         \
+  (head) = (add);                                                                              \
+ } else {                                                                                      \
+  (add)->prev->next = (add);                                                                   \
+ }                                                                                             \
+} while (0)                                                                                    \
+
+
+/******************************************************************************
+ * circular doubly linked list macros                                         *
+ *****************************************************************************/
+#define CDL_PREPEND(head,add)                                                                  \
+    CDL_PREPEND2(head,add,prev,next)
+
+#define CDL_PREPEND2(head,add,prev,next)                                                       \
+do {                                                                                           \
+ if (head) {                                                                                   \
+   (add)->prev = (head)->prev;                                                                 \
+   (add)->next = (head);                                                                       \
+   (head)->prev = (add);                                                                       \
+   (add)->prev->next = (add);                                                                  \
+ } else {                                                                                      \
+   (add)->prev = (add);                                                                        \
+   (add)->next = (add);                                                                        \
+ }                                                                                             \
+(head)=(add);                                                                                  \
+} while (0)
+
+#define CDL_DELETE(head,del)                                                                   \
+    CDL_DELETE2(head,del,prev,next)
+
+#define CDL_DELETE2(head,del,prev,next)                                                        \
+do {                                                                                           \
+  if ( ((head)==(del)) && ((head)->next == (head))) {                                          \
+      (head) = NULL;                                                                             \
+  } else {                                                                                     \
+     (del)->next->prev = (del)->prev;                                                          \
+     (del)->prev->next = (del)->next;                                                          \
+     if ((del) == (head)) (head)=(del)->next;                                                  \
+  }                                                                                            \
+} while (0)
+
+#define CDL_COUNT(head,el,counter)                                                             \
+    CDL_COUNT2(head,el,counter,next)                                                           \
+
+#define CDL_COUNT2(head, el, counter,next)                                                     \
+{                                                                                              \
+    counter = 0;                                                                               \
+    CDL_FOREACH2(head,el,next){ ++counter; }                                                   \
+}
+
+#define CDL_FOREACH(head,el)                                                                   \
+    CDL_FOREACH2(head,el,next)
+
+#define CDL_FOREACH2(head,el,next)                                                             \
+    for(el=head;el;el=(((el)->next==head) ? 0L : (el)->next))
+
+#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2)                                                    \
+    CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
+
+#define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)                                         \
+  for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL);                                        \
+      (el) && ((tmp2)=(el)->next, 1);                                                          \
+      ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
+
+#define CDL_SEARCH_SCALAR(head,out,field,val)                                                  \
+    CDL_SEARCH_SCALAR2(head,out,field,val,next)
+
+#define CDL_SEARCH_SCALAR2(head,out,field,val,next)                                            \
+do {                                                                                           \
+    CDL_FOREACH2(head,out,next) {                                                              \
+      if ((out)->field == (val)) break;                                                        \
+    }                                                                                          \
+} while(0)
+
+#define CDL_SEARCH(head,out,elt,cmp)                                                           \
+    CDL_SEARCH2(head,out,elt,cmp,next)
+
+#define CDL_SEARCH2(head,out,elt,cmp,next)                                                     \
+do {                                                                                           \
+    CDL_FOREACH2(head,out,next) {                                                              \
+      if ((cmp(out,elt))==0) break;                                                            \
+    }                                                                                          \
+} while(0)
+
+#define CDL_REPLACE_ELEM(head, el, add)                                                        \
+do {                                                                                           \
+ assert(head != NULL);                                                                         \
+ assert(el != NULL);                                                                           \
+ assert(add != NULL);                                                                          \
+ if ((el)->next == (el)) {                                                                     \
+  (add)->next = (add);                                                                         \
+  (add)->prev = (add);                                                                         \
+  (head) = (add);                                                                              \
+ } else {                                                                                      \
+  (add)->next = (el)->next;                                                                    \
+  (add)->prev = (el)->prev;                                                                    \
+  (add)->next->prev = (add);                                                                   \
+  (add)->prev->next = (add);                                                                   \
+  if ((head) == (el)) {                                                                        \
+   (head) = (add);                                                                             \
+  }                                                                                            \
+ }                                                                                             \
+} while (0)
+
+#define CDL_PREPEND_ELEM(head, el, add)                                                        \
+do {                                                                                           \
+ assert(head != NULL);                                                                         \
+ assert(el != NULL);                                                                           \
+ assert(add != NULL);                                                                          \
+ (add)->next = (el);                                                                           \
+ (add)->prev = (el)->prev;                                                                     \
+ (el)->prev = (add);                                                                           \
+ (add)->prev->next = (add);                                                                    \
+ if ((head) == (el)) {                                                                         \
+  (head) = (add);                                                                              \
+ }                                                                                             \
+} while (0)                                                                                    \
+
+#endif /* UTLIST_H */
+

test/CMakeLists.txt

     add_subdirectory(ubsan)
   endif()
   add_subdirectory(cfi)
+  if(COMPILER_RT_HAS_HEXE)
+    add_subdirectory(hexe)
+  endif()
 endif()
 
 if(COMPILER_RT_STANDALONE_BUILD)

test/hexe/CMakeLists.txt

+set(HEXE_LIT_SOURCE_DIR ${CMAKE_CURRENT_SOURCE_DIR})
+set(HEXE_LIT_BINARY_DIR ${CMAKE_CURRENT_BINARY_DIR})
+
+set(HEXE_TEST_DEPS hexe)
+if(NOT COMPILER_RT_STANDALONE_BUILD)
+  list(APPEND HEXE_TEST_DEPS hexe)
+endif()
+
+configure_lit_site_cfg(
+  ${CMAKE_CURRENT_SOURCE_DIR}/lit.site.cfg.in
+  ${CMAKE_CURRENT_BINARY_DIR}/lit.site.cfg
+  )
+add_lit_testsuite(check-hexe "Running the hexe tests"
+  ${CMAKE_CURRENT_BINARY_DIR}
+  DEPENDS ${HEXE_TEST_DEPS})
+set_target_properties(check-hexe PROPERTIES FOLDER "Hexe tests")

test/hexe/lit.cfg

+# -*- Python -*-
+
+import os
+
+# Setup config name.
+config.name = 'Hexe'
+
+# Setup source root.
+config.test_source_root = os.path.dirname(__file__)
+
+# Setup default compiler flags used with -fsanitize=memory option.
+clang_hexe_cflags = [] + config.debug_info_flags
+clang_hexe_cxxflags = config.cxx_mode_flags + clang_hexe_cflags
+
+def build_invocation(compile_flags):
+  return " " + " ".join([config.clang] + compile_flags) + " "
+
+config.substitutions.append( ("%clang_hexe ", build_invocation(clang_hexe_cflags)) )
+config.substitutions.append( ("%clangxx_hexe ", build_invocation(clang_hexe_cxxflags)) )
+
+# Default test suffixes.
+config.suffixes = ['.c', '.cc', '.cpp']
+
+# Currently supported on Linux only.
+if config.host_os not in ['Linux']:
+  config.unsupported = True

test/hexe/lit.site.cfg.in

+# Load common config for all compiler-rt lit tests.
+lit_config.load_config(config, "@COMPILER_RT_BINARY_DIR@/test/lit.common.configured")
+
+# Load tool-specific config that would do the real work.
+lit_config.load_config(config, "@HEXE_LIT_SOURCE_DIR@/lit.cfg")

test/hexe/test.c

+// RUN: %clang_hexe -DHOSTCODE %s -o %t -lclang_rt.hexe-arm  -ldl
+// RUN: %clang_hexe -DACCELERATORCODE -fPIC -shared %s -o libaccelerator_debug.so
+// RUN: %run %t
+
+void funnymemcpy(void *dst, const void *src, unsigned size)
+{
+  const char *csrc=(const char *)src;
+  char *cdst=(char *)dst;
+
+  for (; size; --size, ++csrc, ++cdst)
+    *cdst=*csrc;
+}
+
+struct marshalling_data_t  {
+  void *dst;
+  const void *src;
+  unsigned size;
+};
+
+#ifdef HOSTCODE
+
+#include <hexe/hexe_interface.h>
+#include <hexe/hexe_internal.h>
+#include <stdio.h>
+#include <string.h>
+
+
+#define BSIZE 100
+
+int main()
+{
+  char *src=(char *)__hexe_malloc(BSIZE,0);
+  char *dst=(char *)__hexe_malloc(BSIZE,0);
+  memset(src,1,BSIZE);
+
+
+  struct __hexe_MemAccessInfo  mem_access[2];
+  mem_access[0].ptr=dst;
+  mem_access[0].size=2; //something wrong, the runtime will fix it
+  mem_access[0].arg_order=0;
+  mem_access[0].access_mode=3; // be conservative, read/write access
+
+  mem_access[1].ptr=src;
+  mem_access[1].size=2; //something wrong, the runtime will fix it
+  mem_access[1].arg_order=1;
+  mem_access[1].access_mode=3; // be conservative, read/write access
+
+  struct marshalling_data_t call_args;
+  call_args.dst=dst;
+  call_args.src=src;
+  call_args.size=BSIZE;
+
+  int sched = __hexe_runtime_sched(0, mem_access, 2, NULL);
+
+  if (sched) {
+    struct __hexe_Event_t *event;
+
+    __hexe_enforce_coherency(0, mem_access, 2);
+
+    event=__hexe_dispatch(0, &call_args, sizeof(call_args));
+    __hexe_event_wait(event);
+
+    __hexe_enforce_coherency(0, mem_access, 2);
+    //no return value to read back
+    // CHECK: MATCH
+    if(!strcmp(src,dst))
+      printf("MATCH\n");
+    else
+      printf("FAIL\n");
+  }
+  else {
+    funnymemcpy(dst, src, BSIZE);
+  }
+
+  return 0;
+}
+
+#endif //HOSTCODE
+
+
+#ifdef ACCELERATORCODE
+
+#include <stdio.h>
+#define CHOOSE_COMP_FUNCTION(hanlder)  (((handler) >> 24) & 0x1f)
+
+typedef struct {
+  void *pv;
+  size_t nLen;
+} remote_buf;
+
+int __hexe_skel_invoke(int handler, remote_buf *MA)
+{
+  int function_id = CHOOSE_COMP_FUNCTION(handler);
+
+  struct marshalling_data_t *args =
+    (struct marshalling_data_t *) MA[0].pv;
+  void *dst = MA[1].pv;
+  void *src = MA[2].pv;
+  unsigned size = args->size;
+  switch(function_id) {
+    case 0:
+      funnymemcpy(dst, src, size);
+      return 0;
+    default:
+      return 20;
+  }
+
+  return 20;
+}
+
+#endif//ACCELERATORCODE