diff mbox

[gomp4.1] make libgomp's splay tree implementation key agnostic

Message ID 561ABCC7.9090605@redhat.com
State New
Headers show

Commit Message

Aldy Hernandez Oct. 11, 2015, 7:47 p.m. UTC 
Hi.

I'm investigating balanced binary tree options for the multiple 
priorities variant of the task scheduler.  In looking at the splay tree 
adaption in libgomp, I noticed that it requires preexisting typedefs and 
other definitions before including splay-tree.h.  This makes it 
impossible to reuse for another key within the library because 
splay-tree.c must know about the node contents, and other files 
throughout libgomp all share the aforementioned typedefs (because they 
all include libgomp.h).

I also can't use libiberty's version because there are name conflicts 
with libgomp's adaptation.

I see no reason why the splay tree implementation itself (splay-tree.c) 
needs to know about the content of the nodes.  With a little rearranging 
of the data structures and some casts, we can reuse the splay trees at will.

With the following patch we achieve the above, with the only penalty of 
an indirection for a compare callback.

Tested with make check-target-libgomp on x86-64 Linux.

OK for branch?

Aldy
commit 870adcc7fc9b0beb72a4cd78a5cda710c6bff661
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Sat Oct 10 16:28:06 2015 -0700

    	* libgomp.h: Include splay-tree.h earlier.  Use a splay_tree_key_s
    	pointer, instead of splay_tree_key throughout.
    	* oacc-mem.c (KEY): New macro.
    	Rename all uses of splay_tree_key to a splay_tree_key_s pointer.
    	Cast things appropriately.
    	* oacc-parallel.c: Same as oacc-mem.c.
    	* splay-tree.h: Adjust comment to reflect that we no longer need
    	preexisting typedefs before including file.
    	Rename splay_tree_node_s to __internal_splay_tree_node_s.  Move
    	left and right pointers before any other field, and make "key" a
    	generic array.
    	* target.c (KEY): New macro.
    	(splay_compare): Make function static.
    	Rename all uses of splay_tree_key to a splay_tree_key_s pointer.
    	Cast things appropriately.
    	(gomp_map_vars): Adjust gomp_malloc() call to take into account
    	size of key.
    	(gomp_load_image_to_device): Same.
    	(omp_target_associate_ptr): Same.
    	(gomp_target_init): Set mem_map.compare to its comparison
    	function.
diff mbox

Patch

diff --git a/libgomp/libgomp.h b/libgomp/libgomp.h
index 19b3dab..48c5442 100644
--- a/libgomp/libgomp.h
+++ b/libgomp/libgomp.h
@@ -44,6 +44,7 @@ 
 #include "config.h"
 #include "gstdint.h"
 #include "libgomp-plugin.h"
+#include "splay-tree.h"
 
 #include <pthread.h>
 #include <stdbool.h>
@@ -741,13 +742,27 @@  extern void gomp_init_targets_once (void);
 extern int gomp_get_num_devices (void);
 extern void gomp_target_task_fn (void *);
 
-typedef struct splay_tree_node_s *splay_tree_node;
-typedef struct splay_tree_s *splay_tree;
-typedef struct splay_tree_key_s *splay_tree_key;
+/* Special value for refcount - infinity.  */
+#define REFCOUNT_INFINITY (~(uintptr_t) 0)
+
+struct splay_tree_key_s {
+  /* Address of the host object.  */
+  uintptr_t host_start;
+  /* Address immediately after the host object.  */
+  uintptr_t host_end;
+  /* Descriptor of the target memory.  */
+  struct target_mem_desc *tgt;
+  /* Offset from tgt->tgt_start to the start of the target object.  */
+  uintptr_t tgt_offset;
+  /* Reference count.  */
+  uintptr_t refcount;
+  /* Asynchronous reference count.  */
+  uintptr_t async_refcount;
+};
 
 struct target_var_desc {
   /* Splay key.  */
-  splay_tree_key key;
+  struct splay_tree_key_s *key;
   /* True if data should be copied from device to host at the end.  */
   bool copy_from;
   /* True if data always should be copied from device to host at the end.  */
@@ -782,26 +797,6 @@  struct target_mem_desc {
   struct target_var_desc list[];
 };
 
-/* Special value for refcount - infinity.  */
-#define REFCOUNT_INFINITY (~(uintptr_t) 0)
-
-struct splay_tree_key_s {
-  /* Address of the host object.  */
-  uintptr_t host_start;
-  /* Address immediately after the host object.  */
-  uintptr_t host_end;
-  /* Descriptor of the target memory.  */
-  struct target_mem_desc *tgt;
-  /* Offset from tgt->tgt_start to the start of the target object.  */
-  uintptr_t tgt_offset;
-  /* Reference count.  */
-  uintptr_t refcount;
-  /* Asynchronous reference count.  */
-  uintptr_t async_refcount;
-};
-
-#include "splay-tree.h"
-
 typedef struct acc_dispatch_t
 {
   /* This is a linked list of data mapped using the
diff --git a/libgomp/oacc-mem.c b/libgomp/oacc-mem.c
index af067d6..873f3a5 100644
--- a/libgomp/oacc-mem.c
+++ b/libgomp/oacc-mem.c
@@ -35,21 +35,20 @@ 
 #include <stdint.h>
 #include <assert.h>
 
+#define KEY(K) ((struct splay_tree_key_s *) (K))
+
 /* Return block containing [H->S), or NULL if not contained.  The device lock
    for DEV must be locked on entry, and remains locked on exit.  */
 
-static splay_tree_key
+static struct splay_tree_key_s *
 lookup_host (struct gomp_device_descr *dev, void *h, size_t s)
 {
   struct splay_tree_key_s node;
-  splay_tree_key key;
 
   node.host_start = (uintptr_t) h;
   node.host_end = (uintptr_t) h + s;
 
-  key = splay_tree_lookup (&dev->mem_map, &node);
-
-  return key;
+  return KEY (splay_tree_lookup (&dev->mem_map, &node));
 }
 
 /* Return block containing [D->S), or NULL if not contained.
@@ -58,7 +57,7 @@  lookup_host (struct gomp_device_descr *dev, void *h, size_t s)
    operation.  The device lock associated with TGT must be locked on entry, and
    remains locked on exit.  */
 
-static splay_tree_key
+static struct splay_tree_key_s *
 lookup_dev (struct target_mem_desc *tgt, void *d, size_t s)
 {
   int i;
@@ -80,7 +79,7 @@  lookup_dev (struct target_mem_desc *tgt, void *d, size_t s)
     {
       void * offset;
 
-      splay_tree_key k = &t->array[i].key;
+      struct splay_tree_key_s *k = KEY (&t->array[i].key);
       offset = d - t->tgt_start + k->tgt_offset;
 
       if (k->host_start + offset <= (void *) k->host_end)
@@ -114,7 +113,7 @@  acc_malloc (size_t s)
 void
 acc_free (void *d)
 {
-  splay_tree_key k;
+  struct splay_tree_key_s *k;
 
   if (!d)
     return;
@@ -176,7 +175,6 @@  acc_memcpy_from_device (void *h, void *d, size_t s)
 void *
 acc_deviceptr (void *h)
 {
-  splay_tree_key n;
   void *d;
   void *offset;
 
@@ -187,7 +185,7 @@  acc_deviceptr (void *h)
 
   gomp_mutex_lock (&dev->lock);
 
-  n = lookup_host (dev, h, 1);
+  struct splay_tree_key_s *n = lookup_host (dev, h, 1);
 
   if (!n)
     {
@@ -210,7 +208,7 @@  acc_deviceptr (void *h)
 void *
 acc_hostptr (void *d)
 {
-  splay_tree_key n;
+  struct splay_tree_key_s *n;
   void *h;
   void *offset;
 
@@ -243,8 +241,6 @@  acc_hostptr (void *d)
 int
 acc_is_present (void *h, size_t s)
 {
-  splay_tree_key n;
-
   if (!s || !h)
     return 0;
 
@@ -255,7 +251,7 @@  acc_is_present (void *h, size_t s)
 
   gomp_mutex_lock (&acc_dev->lock);
 
-  n = lookup_host (acc_dev, h, s);
+  struct splay_tree_key_s *n = lookup_host (acc_dev, h, s);
 
   if (n && ((uintptr_t)h < n->host_start
 	    || (uintptr_t)h + s > n->host_end
@@ -340,7 +336,7 @@  acc_unmap_data (void *h)
 
   gomp_mutex_lock (&acc_dev->lock);
 
-  splay_tree_key n = lookup_host (acc_dev, h, 1);
+  struct splay_tree_key_s *n = lookup_host (acc_dev, h, 1);
   struct target_mem_desc *t;
 
   if (!n)
@@ -396,7 +392,6 @@  static void *
 present_create_copy (unsigned f, void *h, size_t s)
 {
   void *d;
-  splay_tree_key n;
 
   if (!h || !s)
     gomp_fatal ("[%p,+%d] is a bad range", (void *)h, (int)s);
@@ -408,7 +403,7 @@  present_create_copy (unsigned f, void *h, size_t s)
 
   gomp_mutex_lock (&acc_dev->lock);
 
-  n = lookup_host (acc_dev, h, s);
+  struct splay_tree_key_s *n = lookup_host (acc_dev, h, s);
   if (n)
     {
       /* Present. */
@@ -492,14 +487,13 @@  static void
 delete_copyout (unsigned f, void *h, size_t s)
 {
   size_t host_size;
-  splay_tree_key n;
   void *d;
   struct goacc_thread *thr = goacc_thread ();
   struct gomp_device_descr *acc_dev = thr->dev;
 
   gomp_mutex_lock (&acc_dev->lock);
 
-  n = lookup_host (acc_dev, h, s);
+  struct splay_tree_key_s *n = lookup_host (acc_dev, h, s);
 
   /* No need to call lazy open, as the data must already have been
      mapped.  */
@@ -545,14 +539,13 @@  void acc_copyout (void *h, size_t s)
 static void
 update_dev_host (int is_dev, void *h, size_t s)
 {
-  splay_tree_key n;
   void *d;
   struct goacc_thread *thr = goacc_thread ();
   struct gomp_device_descr *acc_dev = thr->dev;
 
   gomp_mutex_lock (&acc_dev->lock);
 
-  n = lookup_host (acc_dev, h, s);
+  struct splay_tree_key_s *n = lookup_host (acc_dev, h, s);
 
   /* No need to call lazy open, as the data must already have been
      mapped.  */
@@ -609,13 +602,12 @@  gomp_acc_remove_pointer (void *h, bool force_copyfrom, int async, int mapnum)
 {
   struct goacc_thread *thr = goacc_thread ();
   struct gomp_device_descr *acc_dev = thr->dev;
-  splay_tree_key n;
   struct target_mem_desc *t;
   int minrefs = (mapnum == 1) ? 2 : 3;
 
   gomp_mutex_lock (&acc_dev->lock);
 
-  n = lookup_host (acc_dev, h, 1);
+  struct splay_tree_key_s *n = lookup_host (acc_dev, h, 1);
 
   if (!n)
     {
diff --git a/libgomp/oacc-parallel.c b/libgomp/oacc-parallel.c
index 8f8ad77..9a452ca 100644
--- a/libgomp/oacc-parallel.c
+++ b/libgomp/oacc-parallel.c
@@ -38,6 +38,8 @@ 
 #include <stdarg.h>
 #include <assert.h>
 
+#define KEY(K) ((struct splay_tree_key_s *) (K))
+
 static int
 find_pset (int pos, size_t mapnum, unsigned short *kinds)
 {
@@ -66,7 +68,7 @@  GOACC_parallel (int device, void (*fn) (void *),
   void **devaddrs;
   unsigned int i;
   struct splay_tree_key_s k;
-  splay_tree_key tgt_fn_key;
+  struct splay_tree_key_s *tgt_fn_key;
   void (*tgt_fn);
 
   if (num_gangs != 1)
@@ -119,7 +121,7 @@  GOACC_parallel (int device, void (*fn) (void *),
       k.host_start = (uintptr_t) fn;
       k.host_end = k.host_start + 1;
       gomp_mutex_lock (&acc_dev->lock);
-      tgt_fn_key = splay_tree_lookup (&acc_dev->mem_map, &k);
+      tgt_fn_key = KEY (splay_tree_lookup (&acc_dev->mem_map, &k));
       gomp_mutex_unlock (&acc_dev->lock);
 
       if (tgt_fn_key == NULL)
diff --git a/libgomp/splay-tree.c b/libgomp/splay-tree.c
index 030ca8f..0d00faa 100644
--- a/libgomp/splay-tree.c
+++ b/libgomp/splay-tree.c
@@ -25,8 +25,8 @@ 
    <http://www.gnu.org/licenses/>.  */
 
 /* The splay tree code copied from include/splay-tree.h and adjusted,
-   so that all the data lives directly in splay_tree_node_s structure
-   and no extra allocations are needed.  */
+   so that all the data lives directly in the node structure and no
+   extra allocations are needed.  */
 
 /* For an easily readable description of splay-trees, see:
 
@@ -37,9 +37,6 @@ 
    are amortized O(log n) time for a tree with n nodes.  */
 
 #include "libgomp.h"
-#include "splay-tree.h"
-
-extern int splay_compare (splay_tree_key, splay_tree_key);
 
 /* Rotate the edge joining the left child N with its parent P.  PP is the
    grandparents' pointer to P.  */
@@ -80,7 +77,7 @@  splay_tree_splay (splay_tree sp, splay_tree_key key)
     splay_tree_node n, c;
 
     n = sp->root;
-    cmp1 = splay_compare (key, &n->key);
+    cmp1 = sp->compare (key, &n->key);
 
     /* Found.  */
     if (cmp1 == 0)
@@ -96,7 +93,7 @@  splay_tree_splay (splay_tree sp, splay_tree_key key)
 
     /* Next one left or right?  If found or no child, we're done
        after one rotation.  */
-    cmp2 = splay_compare (key, &c->key);
+    cmp2 = sp->compare (key, &c->key);
     if (cmp2 == 0
 	|| (cmp2 < 0 && !c->left)
 	|| (cmp2 > 0 && !c->right))
@@ -142,7 +139,7 @@  splay_tree_insert (splay_tree sp, splay_tree_node node)
   splay_tree_splay (sp, &node->key);
 
   if (sp->root)
-    comparison = splay_compare (&sp->root->key, &node->key);
+    comparison = sp->compare (&sp->root->key, &node->key);
 
   if (sp->root && comparison == 0)
     gomp_fatal ("Duplicate node");
@@ -175,7 +172,7 @@  splay_tree_remove (splay_tree sp, splay_tree_key key)
 {
   splay_tree_splay (sp, key);
 
-  if (sp->root && splay_compare (&sp->root->key, key) == 0)
+  if (sp->root && sp->compare (&sp->root->key, key) == 0)
     {
       splay_tree_node left, right;
 
@@ -210,7 +207,7 @@  splay_tree_lookup (splay_tree sp, splay_tree_key key)
 {
   splay_tree_splay (sp, key);
 
-  if (sp->root && splay_compare (&sp->root->key, key) == 0)
+  if (sp->root && sp->compare (&sp->root->key, key) == 0)
     return &sp->root->key;
   else
     return NULL;
diff --git a/libgomp/splay-tree.h b/libgomp/splay-tree.h
index 085021c..aed07c3 100644
--- a/libgomp/splay-tree.h
+++ b/libgomp/splay-tree.h
@@ -25,15 +25,8 @@ 
    <http://www.gnu.org/licenses/>.  */
 
 /* The splay tree code copied from include/splay-tree.h and adjusted,
-   so that all the data lives directly in splay_tree_node_s structure
-   and no extra allocations are needed.
-
-   Files including this header should before including it add:
-typedef struct splay_tree_node_s *splay_tree_node;
-typedef struct splay_tree_s *splay_tree;
-typedef struct splay_tree_key_s *splay_tree_key;
-   define splay_tree_key_s structure, and define
-   splay_compare inline function.  */
+   so that all the data lives directly in the node structure and no
+   extra allocations are needed.  */
 
 /* For an easily readable description of splay-trees, see:
 
@@ -46,18 +39,29 @@  typedef struct splay_tree_key_s *splay_tree_key;
 #ifndef _SPLAY_TREE_H
 #define _SPLAY_TREE_H 1
 
-/* The nodes in the splay tree.  */
-struct splay_tree_node_s {
-  struct splay_tree_key_s key;
+/* The nodes in the splay tree.  The sizeof this structure would be
+   sizeof(__internal_splay_tree_node_s) plus the size of the actual
+   key.  */
+typedef struct __internal_splay_tree_node_s {
   /* The left and right children, respectively.  */
-  splay_tree_node left;
-  splay_tree_node right;
-};
+  struct __internal_splay_tree_node_s *left;
+  struct __internal_splay_tree_node_s *right;
+  /* This is actually a place holder.  The actual key is embedded in
+     this node, and can be accessed by the bits starting at &key
+     here.  */
+  char key[1];
+} *splay_tree_node;
+
+/* Pointer to the KEY.  We declare it void, to make sure we don't
+   dereference it, since the splay-tree.c implementation should make
+   no assumptions as to its contents.  */
+typedef void *splay_tree_key;
 
 /* The splay tree.  */
-struct splay_tree_s {
+typedef struct splay_tree_s {
+  int (*compare)(splay_tree_key, splay_tree_key);
   splay_tree_node root;
-};
+} *splay_tree;
 
 extern splay_tree_key splay_tree_lookup (splay_tree, splay_tree_key);
 extern void splay_tree_insert (splay_tree, splay_tree_node);
diff --git a/libgomp/target.c b/libgomp/target.c
index de6a2c9..bb2ac03 100644
--- a/libgomp/target.c
+++ b/libgomp/target.c
@@ -45,6 +45,8 @@ 
 #include "plugin-suffix.h"
 #endif
 
+#define KEY(K) ((struct splay_tree_key_s *) (K))
+
 static void gomp_target_init (void);
 
 /* The whole initialization code for offloading plugins is only run one.  */
@@ -94,9 +96,11 @@  gomp_realloc_unlock (void *old, size_t size)
 
 /* The comparison function.  */
 
-attribute_hidden int
-splay_compare (splay_tree_key x, splay_tree_key y)
+static int
+splay_compare (splay_tree_key xp, splay_tree_key yp)
 {
+  struct splay_tree_key_s *x = KEY (xp);
+  struct splay_tree_key_s *y = KEY (yp);
   if (x->host_start == x->host_end
       && y->host_start == y->host_end)
     return 0;
@@ -143,8 +147,8 @@  resolve_device (int device_id)
 }
 
 
-static inline splay_tree_key
-gomp_map_lookup (splay_tree mem_map, splay_tree_key key)
+static inline struct splay_tree_key_s *
+gomp_map_lookup (splay_tree mem_map, struct splay_tree_key_s *key)
 {
   if (key->host_start != key->host_end)
     return splay_tree_lookup (mem_map, key);
@@ -158,16 +162,18 @@  gomp_map_lookup (splay_tree mem_map, splay_tree_key key)
   n = splay_tree_lookup (mem_map, key);
   key->host_start++;
   if (n)
-    return n;
-  return splay_tree_lookup (mem_map, key);
+    return KEY (n);
+  return KEY (splay_tree_lookup (mem_map, key));
 }
 
 /* Handle the case where gomp_map_lookup found oldn for newn.
    Helper function of gomp_map_vars.  */
 
 static inline void
-gomp_map_vars_existing (struct gomp_device_descr *devicep, splay_tree_key oldn,
-			splay_tree_key newn, struct target_var_desc *tgt_var,
+gomp_map_vars_existing (struct gomp_device_descr *devicep,
+			struct splay_tree_key_s *oldn,
+			struct splay_tree_key_s *newn,
+			struct target_var_desc *tgt_var,
 			unsigned char kind)
 {
   tgt_var->key = oldn;
@@ -226,7 +232,7 @@  gomp_map_pointer (struct target_mem_desc *tgt, uintptr_t host_ptr,
   /* Add bias to the pointer value.  */
   cur_node.host_start += bias;
   cur_node.host_end = cur_node.host_start;
-  splay_tree_key n = gomp_map_lookup (mem_map, &cur_node);
+  struct splay_tree_key_s *n = gomp_map_lookup (mem_map, &cur_node);
   if (n == NULL)
     {
       gomp_mutex_unlock (&devicep->lock);
@@ -247,7 +253,8 @@  gomp_map_pointer (struct target_mem_desc *tgt, uintptr_t host_ptr,
 }
 
 static void
-gomp_map_fields_existing (struct target_mem_desc *tgt, splay_tree_key n,
+gomp_map_fields_existing (struct target_mem_desc *tgt,
+			  struct splay_tree_key_s *n,
 			  size_t first, size_t i, void **hostaddrs,
 			  size_t *sizes, void *kinds)
 {
@@ -260,7 +267,7 @@  gomp_map_fields_existing (struct target_mem_desc *tgt, splay_tree_key n,
 
   cur_node.host_start = (uintptr_t) hostaddrs[i];
   cur_node.host_end = cur_node.host_start + sizes[i];
-  splay_tree_key n2 = splay_tree_lookup (mem_map, &cur_node);
+  struct splay_tree_key_s *n2 = KEY (splay_tree_lookup (mem_map, &cur_node));
   kind = get_kind (short_mapkind, kinds, i);
   if (n2
       && n2->tgt == n->tgt
@@ -351,7 +358,7 @@  gomp_map_vars (struct gomp_device_descr *devicep, size_t mapnum,
 	{
 	  cur_node.host_start = (uintptr_t) hostaddrs[i];
 	  cur_node.host_end = cur_node.host_start;
-	  splay_tree_key n = gomp_map_lookup (mem_map, &cur_node);
+	  struct splay_tree_key_s *n = gomp_map_lookup (mem_map, &cur_node);
 	  if (n == NULL)
 	    {
 	      gomp_mutex_unlock (&devicep->lock);
@@ -495,8 +502,9 @@  gomp_map_vars (struct gomp_device_descr *devicep, size_t mapnum,
   tgt->array = NULL;
   if (not_found_cnt || has_firstprivate)
     {
+      size_t asize = sizeof (*tgt->array) + sizeof (struct splay_tree_key_s);
       if (not_found_cnt)
-	tgt->array = gomp_malloc (not_found_cnt * sizeof (*tgt->array));
+	tgt->array = gomp_malloc (not_found_cnt * asize);
       splay_tree_node array = tgt->array;
       size_t j, field_tgt_offset = 0, field_tgt_clear = ~(size_t) 0;
       uintptr_t field_tgt_base = 0;
@@ -557,7 +565,7 @@  gomp_map_vars (struct gomp_device_descr *devicep, size_t mapnum,
 	      default:
 		break;
 	      }
-	    splay_tree_key k = &array->key;
+	    struct splay_tree_key_s *k = KEY (&array->key);
 	    k->host_start = (uintptr_t) hostaddrs[i];
 	    if (!GOMP_MAP_POINTER_P (kind & typemask))
 	      k->host_end = k->host_start + sizes[i];
@@ -774,7 +782,7 @@  gomp_copy_from_async (struct target_mem_desc *tgt)
       }
     else
       {
-	splay_tree_key k = tgt->list[i].key;
+	struct splay_tree_key_s *k = KEY (tgt->list[i].key);
 	if (tgt->list[i].copy_from)
 	  devicep->dev2host_func (devicep->target_id, (void *) k->host_start,
 				  (void *) (k->tgt->tgt_start + k->tgt_offset),
@@ -804,7 +812,7 @@  gomp_unmap_vars (struct target_mem_desc *tgt, bool do_copyfrom)
   size_t i;
   for (i = 0; i < tgt->list_count; i++)
     {
-      splay_tree_key k = tgt->list[i].key;
+      struct splay_tree_key_s *k = KEY (tgt->list[i].key);
       if (k == NULL)
 	continue;
 
@@ -867,7 +875,8 @@  gomp_update (struct gomp_device_descr *devicep, size_t mapnum, void **hostaddrs,
       {
 	cur_node.host_start = (uintptr_t) hostaddrs[i];
 	cur_node.host_end = cur_node.host_start + sizes[i];
-	splay_tree_key n = splay_tree_lookup (&devicep->mem_map, &cur_node);
+	struct splay_tree_key_s *n = KEY (splay_tree_lookup (&devicep->mem_map,
+							     &cur_node));
 	if (n)
 	  {
 	    int kind = get_kind (short_mapkind, kinds, i);
@@ -943,7 +952,8 @@  gomp_load_image_to_device (struct gomp_device_descr *devicep, unsigned version,
 
   /* Insert host-target address mapping into splay tree.  */
   struct target_mem_desc *tgt = gomp_malloc (sizeof (*tgt));
-  tgt->array = gomp_malloc ((num_funcs + num_vars) * sizeof (*tgt->array));
+  size_t asize = sizeof (*tgt->array) + sizeof (struct splay_tree_key_s);
+  tgt->array = gomp_malloc ((num_funcs + num_vars) * asize);
   tgt->refcount = REFCOUNT_INFINITY;
   tgt->tgt_start = 0;
   tgt->tgt_end = 0;
@@ -955,7 +965,7 @@  gomp_load_image_to_device (struct gomp_device_descr *devicep, unsigned version,
 
   for (i = 0; i < num_funcs; i++)
     {
-      splay_tree_key k = &array->key;
+      struct splay_tree_key_s *k = KEY (&array->key);
       k->host_start = (uintptr_t) host_func_table[i];
       k->host_end = k->host_start + 1;
       k->tgt = tgt;
@@ -980,7 +990,7 @@  gomp_load_image_to_device (struct gomp_device_descr *devicep, unsigned version,
 	  gomp_fatal ("Can't map target variables (size mismatch)");
 	}
 
-      splay_tree_key k = &array->key;
+      struct splay_tree_key_s *k = KEY (&array->key);
       k->host_start = (uintptr_t) host_var_table[i * 2];
       k->host_end = k->host_start + (uintptr_t) host_var_table[i * 2 + 1];
       k->tgt = tgt;
@@ -1016,7 +1026,7 @@  gomp_unload_image_from_device (struct gomp_device_descr *devicep,
 
   unsigned j;
   struct splay_tree_key_s k;
-  splay_tree_key node = NULL;
+  struct splay_tree_key_s *node = NULL;
 
   /* Find mapping at start of node array */
   if (num_funcs || num_vars)
@@ -1189,7 +1199,8 @@  gomp_free_memmap (struct splay_tree_s *mem_map)
 {
   while (mem_map->root)
     {
-      struct target_mem_desc *tgt = mem_map->root->key.tgt;
+      struct splay_tree_key_s *key = KEY (&mem_map->root->key);
+      struct target_mem_desc *tgt = key->tgt;
 
       splay_tree_remove (mem_map, &mem_map->root->key);
       free (tgt->array);
@@ -1241,7 +1252,8 @@  gomp_get_target_fn_addr (struct gomp_device_descr *devicep,
       struct splay_tree_key_s k;
       k.host_start = (uintptr_t) host_fn;
       k.host_end = k.host_start + 1;
-      splay_tree_key tgt_fn = splay_tree_lookup (&devicep->mem_map, &k);
+      struct splay_tree_key_s *tgt_fn
+	= KEY (splay_tree_lookup (&devicep->mem_map, &k));
       gomp_mutex_unlock (&devicep->lock);
       if (tgt_fn == NULL)
 	gomp_fatal ("Target function wasn't mapped");
@@ -1521,10 +1533,11 @@  gomp_exit_data (struct gomp_device_descr *devicep, size_t mapnum,
 	case GOMP_MAP_DELETE_ZERO_LEN_ARRAY_SECTION:
 	  cur_node.host_start = (uintptr_t) hostaddrs[i];
 	  cur_node.host_end = cur_node.host_start + sizes[i];
-	  splay_tree_key k = (kind == GOMP_MAP_DELETE_ZERO_LEN_ARRAY_SECTION
+	  struct splay_tree_key_s *k
+	    = (kind == GOMP_MAP_DELETE_ZERO_LEN_ARRAY_SECTION
 			      || kind == GOMP_MAP_ZERO_LEN_ARRAY_SECTION)
 	    ? gomp_map_lookup (&devicep->mem_map, &cur_node)
-	    : splay_tree_lookup (&devicep->mem_map, &cur_node);
+	    : KEY (splay_tree_lookup (&devicep->mem_map, &cur_node));
 	  if (!k)
 	    continue;
 
@@ -1977,7 +1990,7 @@  omp_target_associate_ptr (void *host_ptr, void *device_ptr, size_t size,
 
   cur_node.host_start = (uintptr_t) host_ptr;
   cur_node.host_end = cur_node.host_start + size;
-  splay_tree_key n = gomp_map_lookup (mem_map, &cur_node);
+  struct splay_tree_key_s *n = gomp_map_lookup (mem_map, &cur_node);
   if (n)
     {
       if (n->tgt->tgt_start + n->tgt_offset
@@ -1989,7 +2002,8 @@  omp_target_associate_ptr (void *host_ptr, void *device_ptr, size_t size,
   else
     {
       struct target_mem_desc *tgt = gomp_malloc (sizeof (*tgt));
-      tgt->array = gomp_malloc (sizeof (*tgt->array));
+      tgt->array = gomp_malloc (sizeof (*tgt->array)
+				+ sizeof (struct splay_tree_key_s));
       tgt->refcount = 1;
       tgt->tgt_start = 0;
       tgt->tgt_end = 0;
@@ -1998,7 +2012,7 @@  omp_target_associate_ptr (void *host_ptr, void *device_ptr, size_t size,
       tgt->list_count = 0;
       tgt->device_descr = devicep;
       splay_tree_node array = tgt->array;
-      splay_tree_key k = &array->key;
+      struct splay_tree_key_s *k = KEY (&array->key);
       k->host_start = cur_node.host_start;
       k->host_end = cur_node.host_end;
       k->tgt = tgt;
@@ -2038,7 +2052,7 @@  omp_target_disassociate_ptr (void *ptr, int device_num)
 
   cur_node.host_start = (uintptr_t) ptr;
   cur_node.host_end = cur_node.host_start;
-  splay_tree_key n = gomp_map_lookup (mem_map, &cur_node);
+  struct splay_tree_key_s *n = gomp_map_lookup (mem_map, &cur_node);
   if (n
       && n->host_start == cur_node.host_start
       && n->refcount == REFCOUNT_INFINITY
@@ -2224,6 +2238,7 @@  gomp_target_init (void)
 		/* current_device.capabilities has already been set.  */
 		current_device.type = current_device.get_type_func ();
 		current_device.mem_map.root = NULL;
+		current_device.mem_map.compare = splay_compare;
 		current_device.is_initialized = false;
 		current_device.openacc.data_environ = NULL;
 		for (i = 0; i < new_num_devices; i++)