Merge from transactional-memory branch.

From-SVN: r181154

6 files changed, 602 insertions, 0 deletions

diff --git a/libitm/config/generic/cacheline.cc b/libitm/config/generic/cacheline.cc
new file mode 100644
index 00000000000..108ffba3037
--- /dev/null
+++ b/libitm/config/generic/cacheline.cc
@@ -0,0 +1,49 @@
+/* Copyright (C) 2009, 2011 Free Software Foundation, Inc.
+   Contributed by Richard Henderson <rth@redhat.com>.
+
+   This file is part of the GNU Transactional Memory Library (libitm).
+
+   Libitm is free software; you can redistribute it and/or modify it
+   under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   Libitm is distributed in the hope that it will be useful, but WITHOUT ANY
+   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+   FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+   more details.
+
+   Under Section 7 of GPL version 3, you are granted additional
+   permissions described in the GCC Runtime Library Exception, version
+   3.1, as published by the Free Software Foundation.
+
+   You should have received a copy of the GNU General Public License and
+   a copy of the GCC Runtime Library Exception along with this program;
+   see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include "libitm_i.h"
+
+
+namespace GTM HIDDEN {
+
+void
+gtm_cacheline::copy_mask (gtm_cacheline * __restrict d,
+			  const gtm_cacheline * __restrict s,
+			  gtm_cacheline_mask m)
+{
+  const size_t n = sizeof (gtm_word);
+
+  if (m == (gtm_cacheline_mask) -1)
+    {
+      *d = *s;
+      return;
+    }
+  if (__builtin_expect (m == 0, 0))
+    return;
+
+  for (size_t i = 0; i < CACHELINE_SIZE / n; ++i, m >>= n)
+    store_mask (&d->w[i], s->w[i], m);
+}
+
+} // namespace GTM
diff --git a/libitm/config/generic/cacheline.h b/libitm/config/generic/cacheline.h
new file mode 100644
index 00000000000..0a5af761d6e
--- /dev/null
+++ b/libitm/config/generic/cacheline.h
@@ -0,0 +1,107 @@
+/* Copyright (C) 2009, 2011 Free Software Foundation, Inc.
+   Contributed by Richard Henderson <rth@redhat.com>.
+
+   This file is part of the GNU Transactional Memory Library (libitm).
+
+   Libitm is free software; you can redistribute it and/or modify it
+   under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   Libitm is distributed in the hope that it will be useful, but WITHOUT ANY
+   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+   FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+   more details.
+
+   Under Section 7 of GPL version 3, you are granted additional
+   permissions described in the GCC Runtime Library Exception, version
+   3.1, as published by the Free Software Foundation.
+
+   You should have received a copy of the GNU General Public License and
+   a copy of the GCC Runtime Library Exception along with this program;
+   see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#ifndef LIBITM_CACHELINE_H
+#define LIBITM_CACHELINE_H 1
+
+namespace GTM HIDDEN {
+
+// A cacheline is the smallest unit with which locks are associated.
+// The current implementation of the _ITM_[RW] barriers assumes that
+// all data types can fit (aligned) within a cachline, which means
+// in practice sizeof(complex long double) is the smallest cacheline size.
+// It ought to be small enough for efficient manipulation of the
+// modification mask, below.
+#ifndef CACHELINE_SIZE
+# define CACHELINE_SIZE 32
+#endif
+
+// A gtm_cacheline_mask stores a modified bit for every modified byte
+// in the cacheline with which it is associated.
+typedef sized_integral<CACHELINE_SIZE / 8>::type gtm_cacheline_mask;
+
+union gtm_cacheline
+{
+  // Byte access to the cacheline.
+  unsigned char b[CACHELINE_SIZE] __attribute__((aligned(CACHELINE_SIZE)));
+
+  // Larger sized access to the cacheline.
+  uint16_t u16[CACHELINE_SIZE / sizeof(uint16_t)];
+  uint32_t u32[CACHELINE_SIZE / sizeof(uint32_t)];
+  uint64_t u64[CACHELINE_SIZE / sizeof(uint64_t)];
+  gtm_word w[CACHELINE_SIZE / sizeof(gtm_word)];
+
+  // Store S into D, but only the bytes specified by M.
+  template<typename T> static void store_mask (T *d, T s, uint8_t m);
+
+  // Copy S to D, but only the bytes specified by M.
+  static void copy_mask (gtm_cacheline * __restrict d,
+			 const gtm_cacheline * __restrict s,
+			 gtm_cacheline_mask m);
+
+  // A write barrier to emit after (a series of) copy_mask.
+  // When we're emitting non-temporal stores, the normal strong
+  // ordering of the machine doesn't apply.
+  static void copy_mask_wb () { atomic_write_barrier(); }
+};
+
+template<typename T>
+inline void
+gtm_cacheline::store_mask (T *d, T s, uint8_t m)
+{
+  const uint8_t tm = (1 << sizeof(T)) - 1;
+
+  if (__builtin_expect (m & tm, tm))
+    {
+      if (__builtin_expect ((m & tm) == tm, 1))
+	*d = s;
+      else
+	{
+	  const int half = sizeof(T) / 2;
+	  typedef typename sized_integral<half>::type half_t;
+	  half_t *dhalf = reinterpret_cast<half_t *>(d);
+	  half_t s1, s2;
+
+	  if (WORDS_BIGENDIAN)
+	    s1 = s >> half*8, s2 = s;
+	  else
+	    s1 = s, s2 = s >> half*8;
+
+	  store_mask (dhalf, s1, m);
+	  store_mask (dhalf + 1, s2, m >> half);
+	}
+    }
+}
+
+template<>
+inline void ALWAYS_INLINE
+gtm_cacheline::store_mask<uint8_t> (uint8_t *d, uint8_t s, uint8_t m)
+{
+  if (m & 1)
+    *d = s;
+}
+
+} // namespace GTM
+
+#endif // LIBITM_CACHELINE_H
diff --git a/libitm/config/generic/cachepage.h b/libitm/config/generic/cachepage.h
new file mode 100644
index 00000000000..a5472f3831b
--- /dev/null
+++ b/libitm/config/generic/cachepage.h
@@ -0,0 +1,77 @@
+/* Copyright (C) 2009, 2011 Free Software Foundation, Inc.
+   Contributed by Richard Henderson <rth@redhat.com>.
+
+   This file is part of the GNU Transactional Memory Library (libitm).
+
+   Libitm is free software; you can redistribute it and/or modify it
+   under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   Libitm is distributed in the hope that it will be useful, but WITHOUT ANY
+   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+   FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+   more details.
+
+   Under Section 7 of GPL version 3, you are granted additional
+   permissions described in the GCC Runtime Library Exception, version
+   3.1, as published by the Free Software Foundation.
+
+   You should have received a copy of the GNU General Public License and
+   a copy of the GCC Runtime Library Exception along with this program;
+   see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#ifndef LIBITM_CACHEPAGE_H
+#define LIBITM_CACHEPAGE_H 1
+
+namespace GTM HIDDEN {
+
+// A "page" worth of saved cachelines plus modification masks.  This
+// arrangement is intended to minimize the overhead of alignment.  The
+// PAGE_SIZE defined by the target must be a constant for this to work,
+// which means that this definition may not be the same as the real
+// system page size.  An additional define of FIXED_PAGE_SIZE by the
+// target indicates that PAGE_SIZE exactly matches the system page size.
+
+#ifndef PAGE_SIZE
+#define PAGE_SIZE 4096
+#endif
+
+struct gtm_cacheline_page
+{
+  static const size_t LINES
+    = ((PAGE_SIZE - sizeof(gtm_cacheline_page *))
+       / (CACHELINE_SIZE + sizeof(gtm_cacheline_mask)));
+
+  gtm_cacheline lines[LINES] __attribute__((aligned(PAGE_SIZE)));
+  gtm_cacheline_mask masks[LINES];
+  gtm_cacheline_page *prev;
+
+  static gtm_cacheline_page *
+  page_for_line (gtm_cacheline *c)
+  {
+    return (gtm_cacheline_page *)((uintptr_t)c & -PAGE_SIZE);
+  }
+
+  gtm_cacheline_mask *
+  mask_for_line (gtm_cacheline *c)
+  {
+    size_t index = c - &this->lines[0];
+    return &this->masks[index];
+  }
+
+  static gtm_cacheline_mask *
+  mask_for_page_line (gtm_cacheline *c)
+  {
+    gtm_cacheline_page *p = page_for_line (c);
+    return p->mask_for_line (c);
+  }
+
+  static void *operator new (size_t);
+  static void operator delete (void *);
+};
+
+} // namespace GTM
+
+#endif // LIBITM_CACHEPAGE_H
diff --git a/libitm/config/generic/tls.cc b/libitm/config/generic/tls.cc
new file mode 100644
index 00000000000..3e82cff0902
--- /dev/null
+++ b/libitm/config/generic/tls.cc
@@ -0,0 +1,76 @@
+/* Copyright (C) 2010, 2011 Free Software Foundation, Inc.
+   Contributed by Richard Henderson <rth@redhat.com>.
+
+   This file is part of the GNU Transactional Memory Library (libitm).
+
+   Libitm is free software; you can redistribute it and/or modify it
+   under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   Libitm is distributed in the hope that it will be useful, but WITHOUT ANY
+   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+   FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+   more details.
+
+   Under Section 7 of GPL version 3, you are granted additional
+   permissions described in the GCC Runtime Library Exception, version
+   3.1, as published by the Free Software Foundation.
+
+   You should have received a copy of the GNU General Public License and
+   a copy of the GCC Runtime Library Exception along with this program;
+   see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include "libitm_i.h"
+
+namespace GTM HIDDEN {
+
+// Filter out any updates that overlap the libitm stack, as defined by
+// TOP (entry point to library) and BOT (below current function).  This
+// definition should be fine for all stack-grows-down architectures.
+
+gtm_cacheline_mask __attribute__((noinline))
+gtm_mask_stack(gtm_cacheline *line, gtm_cacheline_mask mask)
+{
+  void *top = gtm_thr()->jb.cfa;
+  void *bot = __builtin_dwarf_cfa();
+
+  // We must have come through an entry point that set TOP.
+  assert (top != NULL);
+
+  if (line + 1 < bot)
+    {
+      // Since we don't have the REAL stack boundaries for this thread,
+      // we cannot know if this is a dead write to a stack address below
+      // the current function or if it is write to another VMA.  In either
+      // case allowing the write should not affect correctness.
+    }
+  else if (line >= top)
+    {
+      // A valid write to an address in an outer stack frame, or a write
+      // to another VMA.
+    }
+  else
+    {
+      uintptr_t diff = (uintptr_t)top - (uintptr_t)line;
+      if (diff >= CACHELINE_SIZE)
+	{
+	  // The write is either fully within the proscribed area, or the tail
+	  // of the cacheline overlaps the proscribed area.  Assume that all
+	  // stacks are at least cacheline aligned and declare the head of the
+	  // cacheline dead.
+	  mask = 0;
+	}
+      else
+	{
+	  // The head of the cacheline is within the proscribed area, but the
+	  // tail of the cacheline is live.  Eliminate the dead writes.
+	  mask &= (gtm_cacheline_mask)-1 << diff;
+	}
+    }
+
+  return mask;
+}
+
+} // namespace GTM
diff --git a/libitm/config/generic/tls.h b/libitm/config/generic/tls.h
new file mode 100644
index 00000000000..e282e54817b
--- /dev/null
+++ b/libitm/config/generic/tls.h
@@ -0,0 +1,65 @@
+/* Copyright (C) 2008, 2009, 2011 Free Software Foundation, Inc.
+   Contributed by Richard Henderson <rth@redhat.com>.
+
+   This file is part of the GNU Transactional Memory Library (libitm).
+
+   Libitm is free software; you can redistribute it and/or modify it
+   under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   Libitm is distributed in the hope that it will be useful, but WITHOUT ANY
+   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+   FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+   more details.
+
+   Under Section 7 of GPL version 3, you are granted additional
+   permissions described in the GCC Runtime Library Exception, version
+   3.1, as published by the Free Software Foundation.
+
+   You should have received a copy of the GNU General Public License and
+   a copy of the GCC Runtime Library Exception along with this program;
+   see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#ifndef LIBITM_TLS_H
+#define LIBITM_TLS_H 1
+
+namespace GTM HIDDEN {
+
+#if !defined(HAVE_ARCH_GTM_THREAD) || !defined(HAVE_ARCH_GTM_THREAD_DISP)
+// Provides a single place to store all this libraries thread-local data.
+struct gtm_thread_tls
+{
+#ifndef HAVE_ARCH_GTM_THREAD
+  // The currently active transaction.  Elided if the target provides
+  // some efficient mechanism for storing this.
+  gtm_thread *thr;
+#endif
+#ifndef HAVE_ARCH_GTM_THREAD_DISP
+  // The dispatch table for the STM implementation currently in use.  Elided
+  // if the target provides some efficient mechanism for storing this.
+  abi_dispatch *disp;
+#endif
+};
+
+extern __thread gtm_thread_tls _gtm_thr_tls;
+#endif
+
+#ifndef HAVE_ARCH_GTM_THREAD
+// If the target does not provide optimized access to the thread-local
+// data, simply access the TLS variable defined above.
+static inline gtm_thread *gtm_thr() { return &_gtm_thr_tls.thr; }
+static inline void set_gtm_thr(gtm_thread *x) { _gtm_thr_tls.thr = x; }
+#endif
+
+#ifndef HAVE_ARCH_GTM_THREAD_DISP
+// If the target does not provide optimized access to the currently
+// active dispatch table, simply access via GTM_THR.
+static inline abi_dispatch * abi_disp() { return _gtm_thr_tls.disp; }
+static inline void set_abi_disp(abi_dispatch *x) { _gtm_thr_tls.disp = x; }
+#endif
+
+} // namespace GTM
+
+#endif // LIBITM_TLS_H
diff --git a/libitm/config/generic/unaligned.h b/libitm/config/generic/unaligned.h
new file mode 100644
index 00000000000..50cb13bd277
--- /dev/null
+++ b/libitm/config/generic/unaligned.h
@@ -0,0 +1,228 @@
+/* Copyright (C) 2009, 2011 Free Software Foundation, Inc.
+   Contributed by Richard Henderson <rth@redhat.com>.
+
+   This file is part of the GNU Transactional Memory Library (libitm).
+
+   Libitm is free software; you can redistribute it and/or modify it
+   under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   Libitm is distributed in the hope that it will be useful, but WITHOUT ANY
+   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+   FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+   more details.
+
+   Under Section 7 of GPL version 3, you are granted additional
+   permissions described in the GCC Runtime Library Exception, version
+   3.1, as published by the Free Software Foundation.
+
+   You should have received a copy of the GNU General Public License and
+   a copy of the GCC Runtime Library Exception along with this program;
+   see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#ifndef LIBITM_UNALIGNED_H
+#define LIBITM_UNALIGNED_H 1
+
+namespace GTM HIDDEN {
+
+#ifndef STRICT_ALIGNMENT
+#define STRICT_ALIGNMENT 1
+#endif
+
+// A type trait for whether type T requires strict alignment.
+// The generic types are assumed to all be the same; specializations
+// for target-specific types should be done in config/cpu/unaligned.h.
+template<typename T>
+  struct strict_alignment
+    : public std::integral_constant<bool, STRICT_ALIGNMENT>
+  { };
+
+// A helper template for accessing an integral type the same size as T
+template<typename T>
+  struct make_integral
+    : public sized_integral<sizeof(T)>
+  { };
+
+// A helper class for accessing T as an unaligned value.
+template<typename T>
+struct __attribute__((packed)) unaligned_helper
+  { T x; };
+
+// A helper class for view-converting T as an integer.
+template<typename T>
+union view_convert_helper
+{
+  typedef T type;
+  typedef make_integral<T> itype;
+
+  type t;
+  itype i;
+};
+
+// Generate an unaligned load sequence.
+// The compiler knows how to do this for any specific type.
+template<typename T>
+inline T ALWAYS_INLINE
+unaligned_load(const void *t)
+{
+  typedef unaligned_helper<T> UT;
+  const UT *ut = reinterpret_cast<const UT *>(t);
+  return ut->x;
+}
+
+// Generate an unaligned store sequence.
+template<typename T>
+inline void ALWAYS_INLINE
+unaligned_store(void *t, T val)
+{
+  typedef unaligned_helper<T> UT;
+  UT *ut = reinterpret_cast<UT *>(t);
+  ut->x = val;
+}
+
+// Generate an unaligned load from two different cachelines.
+// It is known that OFS + SIZEOF(T) > CACHELINE_SIZE.
+template<typename T>
+inline T ALWAYS_INLINE
+unaligned_load2(const gtm_cacheline *c1, const gtm_cacheline *c2, size_t ofs)
+{
+  size_t left = CACHELINE_SIZE - ofs;
+  T ret;
+
+  memcpy (&ret, &c1->b[ofs], left);
+  memcpy ((char *)&ret + ofs, c2, sizeof(T) - left);
+
+  return ret;
+}
+
+// Generate an unaligned store into two different cachelines.
+// It is known that OFS + SIZEOF(T) > CACHELINE_SIZE.
+template<typename T>
+inline void ALWAYS_INLINE
+unaligned_store2(gtm_cacheline *c1, gtm_cacheline *c2, size_t ofs, T val)
+{
+  size_t left = CACHELINE_SIZE - ofs;
+  memcpy (&c1->b[ofs], &val, left);
+  memcpy (c2, (char *)&val + left, sizeof(T) - left);
+}
+
+#ifndef HAVE_ARCH_UNALIGNED_LOAD2_U2
+template<>
+inline uint16_t ALWAYS_INLINE
+unaligned_load2<uint16_t>(const gtm_cacheline *c1,
+			  const gtm_cacheline *c2, size_t ofs)
+{
+  uint16_t v1 = c1->b[CACHELINE_SIZE - 1];
+  uint16_t v2 = c2->b[0];
+
+  if (WORDS_BIGENDIAN)
+    return v1 << 8 | v2;
+  else
+    return v2 << 8 | v1;
+}
+#endif
+
+#ifndef HAVE_ARCH_UNALIGNED_LOAD2_U4
+template<>
+inline uint32_t ALWAYS_INLINE
+unaligned_load2<uint32_t>(const gtm_cacheline *c1,
+			  const gtm_cacheline *c2, size_t ofs)
+{
+  uint32_t v1 = c1->u32[CACHELINE_SIZE / sizeof(uint32_t) - 1];
+  uint32_t v2 = c2->u32[0];
+  int s2 = (ofs & (sizeof(uint32_t) - 1)) * 8;
+  int s1 = sizeof(uint32_t) * 8 - s2;
+
+  if (WORDS_BIGENDIAN)
+    return v1 << s2 | v2 >> s1;
+  else
+    return v2 << s2 | v1 >> s1;
+}
+#endif
+
+#ifndef HAVE_ARCH_UNALIGNED_LOAD2_U8
+template<>
+inline uint64_t ALWAYS_INLINE
+unaligned_load2<uint64_t>(const gtm_cacheline *c1,
+			  const gtm_cacheline *c2, size_t ofs)
+{
+  uint64_t v1 = c1->u64[CACHELINE_SIZE / sizeof(uint64_t) - 1];
+  uint64_t v2 = c2->u64[0];
+  int s2 = (ofs & (sizeof(uint64_t) - 1)) * 8;
+  int s1 = sizeof(uint64_t) * 8 - s2;
+
+  if (WORDS_BIGENDIAN)
+    return v1 << s2 | v2 >> s1;
+  else
+    return v2 << s2 | v1 >> s1;
+}
+#endif
+
+template<>
+inline float ALWAYS_INLINE
+unaligned_load2<float>(const gtm_cacheline *c1,
+		       const gtm_cacheline *c2, size_t ofs)
+{
+  typedef view_convert_helper<float> VC; VC vc;
+  vc.i = unaligned_load2<VC::itype>(c1, c2, ofs);
+  return vc.t;
+}
+
+template<>
+inline double ALWAYS_INLINE
+unaligned_load2<double>(const gtm_cacheline *c1,
+			const gtm_cacheline *c2, size_t ofs)
+{
+  typedef view_convert_helper<double> VC; VC vc;
+  vc.i = unaligned_load2<VC::itype>(c1, c2, ofs);
+  return vc.t;
+}
+
+#ifndef HAVE_ARCH_UNALIGNED_STORE2_U2
+template<>
+inline void ALWAYS_INLINE
+unaligned_store2<uint16_t>(gtm_cacheline *c1, gtm_cacheline *c2,
+			   size_t ofs, uint16_t val)
+{
+  uint8_t vl = val, vh = val >> 8;
+
+  if (WORDS_BIGENDIAN)
+    {
+      c1->b[CACHELINE_SIZE - 1] = vh;
+      c2->b[0] = vl;
+    }
+  else
+    {
+      c1->b[CACHELINE_SIZE - 1] = vl;
+      c2->b[0] = vh;
+    }
+}
+#endif
+
+#if 0
+#ifndef HAVE_ARCH_UNALIGNED_STORE2_U4
+template<>
+inline void ALWAYS_INLINE
+unaligned_store2<uint32_t>(gtm_cacheline *c1, gtm_cacheline *c2,
+			   size_t ofs, uint32_t val)
+{
+  // ??? We could reuse the store_mask stuff here.
+}
+#endif
+
+template<>
+inline void ALWAYS_INLINE
+unaligned_store2<float>(gtm_cacheline *c1, gtm_cacheline *c2,
+			size_t ofs, float val)
+{
+  typedef view_convert_helper<float> VC; VC vc;
+  vc.t = val;
+  unaligned_store2(c1, c2, ofs, vc.i);
+}
+#endif
+
+} // namespace GTM
+
+#endif // LIBITM_UNALIGNED_H