Hinted lock (OpenMP 4.5 feature) Updates/Fixes Part 2

[jlpeyton]

Summary

• • Added a new user TSX lock implementation, RTM, This implementation is a light-weight version of the adaptive lock implementation, omitting the back-off logic for deciding when to specualte (or not). The fall-back lock is still the queuing lock.
• Changed indirect lock table management. The data for indirect lock management was encapsulated in the "kmp_indirect_lock_table_t" type. Also, the lock table dimension was changed to 2D (was linear), and each entry is a kmp_indirect_lock_t object now (was a pointer to an object).
• Some clean up in the critical section code
• Removed the limits of the tuning parameters read from KMP_ADAPTIVE_LOCK_PROPS (request from Jim)
• KMP_USE_DYNAMIC_LOCK=1 also turns on these two switches: KMP_USE_TSX, KMP_USE_ADAPTIVE_LOCKS

[jlpeyton]

Adding Hansang as a reviewer.

[hbae]

LGTM.

runtime/src/include/40/omp.h.var

omp_sched_auto    = 4
     extern void   __KAI_KMPC_CONVENTION  omp_set_nest_lock     (omp_nest_lock_t *);
     extern void   __KAI_KMPC_CONVENTION  omp_unset_nest_lock   (omp_nest_lock_t *);
     extern void   __KAI_KMPC_CONVENTION  omp_destroy_nest_lock (omp_nest_lock_t *);
     extern int    __KAI_KMPC_CONVENTION  omp_test_nest_lock    (omp_nest_lock_t *);
 
     /* lock hint type for dynamic user lock */
     typedef enum kmp_lock_hint_t {
         kmp_lock_hint_none = 0,
-        kmp_lock_hint_contended,
         kmp_lock_hint_uncontended,
+        kmp_lock_hint_contended,
         kmp_lock_hint_nonspeculative,
         kmp_lock_hint_speculative,
-        kmp_lock_hint_adaptive,
+        kmp_lock_hint_hle,
+        kmp_lock_hint_rtm,
+        kmp_lock_hint_adaptive
     } kmp_lock_hint_t;
 
     /* hinted lock initializers */
     extern void __KAI_KMPC_CONVENTION kmp_init_lock_hinted(omp_lock_t *, kmp_lock_hint_t);
     extern void __KAI_KMPC_CONVENTION kmp_init_nest_lock_hinted(omp_nest_lock_t *, kmp_lock_hint_t);
 
     /* time API functions */
     extern double __KAI_KMPC_CONVENTION  omp_get_wtime (void);

runtime/src/include/40/omp_lib.h.var

!DIR$ fixedformlinesize:132
       integer (kind=omp_proc_bind_kind), parameter :: omp_proc_bind_close = 3
       integer (kind=omp_proc_bind_kind), parameter :: omp_proc_bind_spread = 4
 
       integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_none           = 0
       integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_uncontended    = 1
       integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_contended      = 2
       integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_nonspeculative = 3
       integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_speculative    = 4
-      integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_adaptive       = 5
+      integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_hle            = 5
+      integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_rtm            = 6
+      integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_adaptive       = 7
 
       interface
 
 !       ***
 !       *** omp_* entry points
 !       ***
 
         subroutine omp_set_num_threads(nthreads) bind(c)

runtime/src/include/40/omp_lib.f.var

!dec$ fixedformlinesize:132
         integer (kind=kmp_cancel_kind), parameter :: kmp_cancel_sections = 3
         integer (kind=kmp_cancel_kind), parameter :: kmp_cancel_taskgroup = 4
 
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_none           = 0
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_uncontended    = 1
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_contended      = 2
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_nonspeculative = 3
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_speculative    = 4
-        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_adaptive       = 5
+        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_hle            = 5
+        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_rtm            = 6
+        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_adaptive       = 7
 
         interface
 
 !         ***
 !         *** omp_* entry points
 !         ***
 
           subroutine omp_set_num_threads(nthreads)

runtime/src/include/40/omp_lib.f90.var

!
         integer (kind=kmp_cancel_kind), parameter :: kmp_cancel_sections = 3
         integer (kind=kmp_cancel_kind), parameter :: kmp_cancel_taskgroup = 4
 
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_none           = 0
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_uncontended    = 1
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_contended      = 2
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_nonspeculative = 3
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_speculative    = 4
-        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_adaptive       = 5
+        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_hle            = 5
+        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_rtm            = 6
+        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_adaptive       = 7
 
         interface
 
 !         ***
 !         *** omp_* entry points
 !         ***
 
           subroutine omp_set_num_threads(nthreads) bind(c)

runtime/src/include/41/omp.h.var

omp_sched_auto    = 4
     extern void   __KAI_KMPC_CONVENTION  omp_set_nest_lock     (omp_nest_lock_t *);
     extern void   __KAI_KMPC_CONVENTION  omp_unset_nest_lock   (omp_nest_lock_t *);
     extern void   __KAI_KMPC_CONVENTION  omp_destroy_nest_lock (omp_nest_lock_t *);
     extern int    __KAI_KMPC_CONVENTION  omp_test_nest_lock    (omp_nest_lock_t *);
 
     /* lock hint type for dynamic user lock */
     typedef enum kmp_lock_hint_t {
         kmp_lock_hint_none = 0,
-        kmp_lock_hint_contended,
         kmp_lock_hint_uncontended,
+        kmp_lock_hint_contended,
         kmp_lock_hint_nonspeculative,
         kmp_lock_hint_speculative,
-        kmp_lock_hint_adaptive,
+        kmp_lock_hint_hle,
+        kmp_lock_hint_rtm,
+        kmp_lock_hint_adaptive
     } kmp_lock_hint_t;
 
     /* hinted lock initializers */
     extern void __KAI_KMPC_CONVENTION kmp_init_lock_hinted(omp_lock_t *, kmp_lock_hint_t);
     extern void __KAI_KMPC_CONVENTION kmp_init_nest_lock_hinted(omp_nest_lock_t *, kmp_lock_hint_t);
 
     /* time API functions */
     extern double __KAI_KMPC_CONVENTION  omp_get_wtime (void);

runtime/src/include/41/omp_lib.h.var

!DIR$ fixedformlinesize:132
       integer (kind=omp_proc_bind_kind), parameter :: omp_proc_bind_close = 3
       integer (kind=omp_proc_bind_kind), parameter :: omp_proc_bind_spread = 4
 
       integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_none           = 0
       integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_uncontended    = 1
       integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_contended      = 2
       integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_nonspeculative = 3
       integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_speculative    = 4
-      integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_adaptive       = 5
+      integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_hle            = 5
+      integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_rtm            = 6
+      integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_adaptive       = 7
 
       interface
 
 !       ***
 !       *** omp_* entry points
 !       ***
 
         subroutine omp_set_num_threads(nthreads) bind(c)

runtime/src/include/41/omp_lib.f.var

!dec$ fixedformlinesize:132
         integer (kind=kmp_cancel_kind), parameter :: kmp_cancel_sections = 3
         integer (kind=kmp_cancel_kind), parameter :: kmp_cancel_taskgroup = 4
 
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_none           = 0
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_uncontended    = 1
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_contended      = 2
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_nonspeculative = 3
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_speculative    = 4
-        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_adaptive       = 5
+        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_hle            = 5
+        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_rtm            = 6
+        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_adaptive       = 7
 
         interface
 
 !         ***
 !         *** omp_* entry points
 !         ***
 
           subroutine omp_set_num_threads(nthreads)

runtime/src/include/41/omp_lib.f90.var

!
         integer (kind=kmp_cancel_kind), parameter :: kmp_cancel_sections = 3
         integer (kind=kmp_cancel_kind), parameter :: kmp_cancel_taskgroup = 4
 
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_none           = 0
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_uncontended    = 1
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_contended      = 2
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_nonspeculative = 3
         integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_speculative    = 4
-        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_adaptive       = 5
+        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_hle            = 5
+        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_rtm            = 6
+        integer (kind=kmp_lock_hint_kind), parameter :: kmp_lock_hint_adaptive       = 7
 
         interface
 
 !         ***
 !         *** omp_* entry points
 !         ***
 
           subroutine omp_set_num_threads(nthreads) bind(c)

runtime/src/kmp_csupport.c

if (ompt_enabled &&
         ompt_callbacks.ompt_callback(ompt_event_release_ordered)(
             th->th.ompt_thread_info.wait_id);
     }
 #endif
 }
 
 #if KMP_USE_DYNAMIC_LOCK
 
-static __forceinline kmp_indirect_lock_t *
-__kmp_get_indirect_csptr(kmp_critical_name * crit, ident_t const * loc, kmp_int32 gtid, kmp_dyna_lockseq_t seq)
+static __forceinline void
+__kmp_init_indirect_csptr(kmp_critical_name * crit, ident_t const * loc, kmp_int32 gtid, kmp_indirect_locktag_t tag)
 {
-    // Code from __kmp_get_critical_section_ptr
-    // This function returns an indirect lock object instead of a user lock.
-    kmp_indirect_lock_t **lck, *ret;
-    lck = (kmp_indirect_lock_t **)crit;
-    ret = (kmp_indirect_lock_t *)TCR_PTR(*lck);
-    if (ret == NULL) {
-        void *idx;
-        kmp_indirect_locktag_t tag = KMP_GET_I_TAG(seq);
-        kmp_indirect_lock_t *ilk = __kmp_allocate_indirect_lock(&idx, gtid, tag);
-        ret = ilk;
-        KMP_I_LOCK_FUNC(ilk, init)(ilk->lock);
-        KMP_SET_I_LOCK_LOCATION(ilk, loc);
-        KMP_SET_I_LOCK_FLAGS(ilk, kmp_lf_critical_section);
-        KA_TRACE(20, ("__kmp_get_indirect_csptr: initialized indirect lock #%d\n", tag));
+    // Pointer to the allocated indirect lock is written to crit, while indexing is ignored.
+    kmp_indirect_lock_t **lck;
+    lck = (kmp_indirect_lock_t **)crit;
+    KA_TRACE(20, ("__kmp_init_indirect_csptr: initialized indirect lock #%d\n", tag));
 #if USE_ITT_BUILD
-        __kmp_itt_critical_creating(ilk->lock, loc);
 #endif
-        int status = KMP_COMPARE_AND_STORE_PTR(lck, 0, ilk);
-        if (status == 0) {
 #if USE_ITT_BUILD
-            __kmp_itt_critical_destroyed(ilk->lock);
 #endif
-            // Postponing destroy, to avoid costly dispatch here.
-            //KMP_D_LOCK_FUNC(&idx, destroy)((kmp_dyna_lock_t *)&idx);
-            ret = (kmp_indirect_lock_t *)TCR_PTR(*lck);
-            KMP_DEBUG_ASSERT(ret != NULL);
-        }
+        // We don't really need to destroy the unclaimed lock here since it will be cleaned up at program exit.
     }
-    return ret;
+    KMP_DEBUG_ASSERT(*lck != NULL);
 }
 
 // Fast-path acquire tas lock
 #define KMP_ACQUIRE_TAS_LOCK(lock, gtid) {                                                                       \
     kmp_tas_lock_t *l = (kmp_tas_lock_t *)lock;                                                                  \
     if (l->lk.poll != KMP_LOCK_FREE(tas) ||                                                                      \
             ! KMP_COMPARE_AND_STORE_ACQ32(&(l->lk.poll), KMP_LOCK_FREE(tas), KMP_LOCK_BUSY(gtid+1, tas))) {      \
         kmp_uint32 spins;                                                                                        \

 }
 
 // Fast-path release tas lock
 #define KMP_RELEASE_TAS_LOCK(lock, gtid) {                          \
     TCW_4(((kmp_tas_lock_t *)lock)->lk.poll, KMP_LOCK_FREE(tas));   \
     KMP_MB();                                                       \
 }
 
-#if KMP_HAS_FUTEX
+#if KMP_USE_FUTEX
 
 # include <unistd.h>
 # include <sys/syscall.h>
 # ifndef FUTEX_WAIT
 #  define FUTEX_WAIT 0
 # endif
 # ifndef FUTEX_WAKE
 #  define FUTEX_WAKE 1
#define KMP_RELEASE_FUTEX_LOCK(lock, gtid) {                                                        \
     kmp_int32 poll_val = KMP_XCHG_FIXED32(&(ftx->lk.poll), KMP_LOCK_FREE(futex));                   \
     if (KMP_LOCK_STRIP(poll_val) & 1) {                                                             \
         syscall(__NR_futex, &(ftx->lk.poll), FUTEX_WAKE, KMP_LOCK_BUSY(1, futex), NULL, NULL, 0);   \
     }                                                                                               \
     KMP_MB();                                                                                       \
     KMP_YIELD(TCR_4(__kmp_nth) > (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc));              \
 }
 
-#endif // KMP_HAS_FUTEX
+#endif // KMP_USE_FUTEX
 
 #else // KMP_USE_DYNAMIC_LOCK
 
 static kmp_user_lock_p
 __kmp_get_critical_section_ptr( kmp_critical_name * crit, ident_t const * loc, kmp_int32 gtid )
 {
     kmp_user_lock_p *lck_pp = (kmp_user_lock_p *)crit;
 

 __kmpc_critical( ident_t * loc, kmp_int32 global_tid, kmp_critical_name * crit ) {
     KMP_COUNT_BLOCK(OMP_CRITICAL);
 
     kmp_user_lock_p lck;
 
     KC_TRACE( 10, ("__kmpc_critical: called T#%d\n", global_tid ) );
 
 #if KMP_USE_DYNAMIC_LOCK
-    // Assumption: all direct locks fit in OMP_CRITICAL_SIZE.
-    // The global sequence __kmp_user_lock_seq is used unless compiler pushes a value.
-    if (KMP_IS_D_LOCK(__kmp_user_lock_seq)) {
-        lck = (kmp_user_lock_p)crit;
-        // The thread that reaches here first needs to tag the lock word.
-        if (*((kmp_dyna_lock_t *)lck) == 0) {
-            KMP_COMPARE_AND_STORE_ACQ32((volatile kmp_int32 *)lck, 0, KMP_GET_D_TAG(__kmp_user_lock_seq));
+
+    kmp_dyna_lock_t *lk = (kmp_dyna_lock_t *)crit;
+    // Check if it is initialized.
+    if (*lk == 0) {
+        kmp_dyna_lockseq_t lckseq = __kmp_user_lock_seq;
+        if (KMP_IS_D_LOCK(lckseq)) {
+            KMP_COMPARE_AND_STORE_ACQ32((volatile kmp_int32 *)crit, 0, KMP_GET_D_TAG(lckseq));
+        } else {
+            __kmp_init_indirect_csptr(crit, loc, global_tid, KMP_GET_I_TAG(lckseq));
         }
+    }
+    // Branch for accessing the actual lock object and set operation. This branching is inevitable since
+    // this lock initialization does not follow the normal dispatch path (lock table is not used).
+    if (KMP_EXTRACT_D_TAG(lk) != 0) {
+        lck = (kmp_user_lock_p)lk;
         if (__kmp_env_consistency_check) {
             __kmp_push_sync(global_tid, ct_critical, loc, lck, __kmp_user_lock_seq);
         }
 # if USE_ITT_BUILD
         __kmp_itt_critical_acquiring(lck);
 # endif
-# if KMP_USE_FAST_TAS
+# if KMP_USE_INLINED_TAS
         if (__kmp_user_lock_seq == lockseq_tas && !__kmp_env_consistency_check) {
             KMP_ACQUIRE_TAS_LOCK(lck, global_tid);
         } else
-# elif KMP_USE_FAST_FUTEX
+# elif KMP_USE_INLINED_FUTEX
         if (__kmp_user_lock_seq == lockseq_futex && !__kmp_env_consistency_check) {
             KMP_ACQUIRE_FUTEX_LOCK(lck, global_tid);
         } else
 # endif
         {
-            KMP_D_LOCK_FUNC(lck, set)((kmp_dyna_lock_t *)lck, global_tid);
+            KMP_D_LOCK_FUNC(lk, set)(lk, global_tid);
         }
     } else {
-        kmp_indirect_lock_t *ilk = __kmp_get_indirect_csptr(crit, loc, global_tid, __kmp_user_lock_seq);
+        kmp_indirect_lock_t *ilk = *((kmp_indirect_lock_t **)lk);
         lck = ilk->lock;
         if (__kmp_env_consistency_check) {
             __kmp_push_sync(global_tid, ct_critical, loc, lck, __kmp_user_lock_seq);
         }
 # if USE_ITT_BUILD
         __kmp_itt_critical_acquiring(lck);
 # endif
         KMP_I_LOCK_FUNC(ilk, set)(lck, global_tid);
if (KMP_IS_D_LOCK(__kmp_user_lock_seq)) {
         lck = (kmp_user_lock_p)crit;
         KMP_ASSERT(lck != NULL);
         if (__kmp_env_consistency_check) {
             __kmp_pop_sync(global_tid, ct_critical, loc);
         }
 # if USE_ITT_BUILD
         __kmp_itt_critical_releasing( lck );
 # endif
-# if KMP_USE_FAST_TAS
+# if KMP_USE_INLINED_TAS
         if (__kmp_user_lock_seq == lockseq_tas && !__kmp_env_consistency_check) {
             KMP_RELEASE_TAS_LOCK(lck, global_tid);
         } else
-# elif KMP_USE_FAST_FUTEX
+# elif KMP_USE_INLINED_FUTEX
         if (__kmp_user_lock_seq == lockseq_futex && !__kmp_env_consistency_check) {
             KMP_RELEASE_FUTEX_LOCK(lck, global_tid);
         } else
 # endif
         {
             KMP_D_LOCK_FUNC(lck, unset)((kmp_dyna_lock_t *)lck, global_tid);
         }
     } else {
#if KMP_USE_DYNAMIC_LOCK
     KMP_DEBUG_ASSERT(__kmp_init_serial);
     if (__kmp_env_consistency_check && user_lock == NULL) {
         KMP_FATAL(LockIsUninitialized, "omp_init_nest_lock");
     }
     // Invoke init function after converting to nested version.
     kmp_dyna_lockseq_t nested_seq;
     switch (__kmp_user_lock_seq) {
         case lockseq_tas:       nested_seq = lockseq_nested_tas;        break;
-#if KMP_HAS_FUTEX
+#if KMP_USE_FUTEX
         case lockseq_futex:     nested_seq = lockseq_nested_futex;      break;
 #endif
         case lockseq_ticket:    nested_seq = lockseq_nested_ticket;     break;
         case lockseq_queuing:   nested_seq = lockseq_nested_queuing;    break;
         case lockseq_drdpa:     nested_seq = lockseq_nested_drdpa;      break;
         default:                nested_seq = lockseq_nested_queuing;    break;
                                 // Use nested queuing lock for lock kinds without "nested" implementation.
     }

 void
 __kmpc_set_lock( ident_t * loc, kmp_int32 gtid, void ** user_lock ) {
     KMP_COUNT_BLOCK(OMP_set_lock);
 #if KMP_USE_DYNAMIC_LOCK
     int tag = KMP_EXTRACT_D_TAG(user_lock);
 # if USE_ITT_BUILD
    __kmp_itt_lock_acquiring((kmp_user_lock_p)user_lock); // itt function will get to the right lock object.
 # endif
-# if KMP_USE_FAST_TAS
+# if KMP_USE_INLINED_TAS
     if (tag == locktag_tas && !__kmp_env_consistency_check) {
         KMP_ACQUIRE_TAS_LOCK(user_lock, gtid);
     } else
-# elif KMP_USE_FAST_FUTEX
+# elif KMP_USE_INLINED_FUTEX
     if (tag == locktag_futex && !__kmp_env_consistency_check) {
         KMP_ACQUIRE_FUTEX_LOCK(user_lock, gtid);
     } else
 # endif
     {
         __kmp_direct_set[tag]((kmp_dyna_lock_t *)user_lock, gtid);
     }
 # if USE_ITT_BUILD

 __kmpc_unset_lock( ident_t *loc, kmp_int32 gtid, void **user_lock )
 {
 #if KMP_USE_DYNAMIC_LOCK
 
     int tag = KMP_EXTRACT_D_TAG(user_lock);
 # if USE_ITT_BUILD
     __kmp_itt_lock_releasing((kmp_user_lock_p)user_lock);
 # endif
-# if KMP_USE_FAST_TAS
+# if KMP_USE_INLINED_TAS
     if (tag == locktag_tas && !__kmp_env_consistency_check) {
         KMP_RELEASE_TAS_LOCK(user_lock, gtid);
     } else
-# elif KMP_USE_FAST_FUTEX
+# elif KMP_USE_INLINED_FUTEX
     if (tag == locktag_futex && !__kmp_env_consistency_check) {
         KMP_RELEASE_FUTEX_LOCK(user_lock, gtid);
     } else
 # endif
     {
         __kmp_direct_unset[tag]((kmp_dyna_lock_t *)user_lock, gtid);
     }
 
__kmpc_test_lock( ident_t *loc, kmp_int32 gtid, void **user_lock )
     KMP_COUNT_BLOCK(OMP_test_lock);
 
 #if KMP_USE_DYNAMIC_LOCK
     int rc;
     int tag = KMP_EXTRACT_D_TAG(user_lock);
 # if USE_ITT_BUILD
     __kmp_itt_lock_acquiring((kmp_user_lock_p)user_lock);
 # endif
-# if KMP_USE_FAST_TAS
+# if KMP_USE_INLINED_TAS
     if (tag == locktag_tas && !__kmp_env_consistency_check) {
         KMP_TEST_TAS_LOCK(user_lock, gtid, rc);
     } else
-# elif KMP_USE_FAST_FUTEX
+# elif KMP_USE_INLINED_FUTEX
     if (tag == locktag_futex && !__kmp_env_consistency_check) {
         KMP_TEST_FUTEX_LOCK(user_lock, gtid, rc);
     } else
 # endif
     {
         rc = __kmp_direct_test[tag]((kmp_dyna_lock_t *)user_lock, gtid);
     }
     if (rc) {
__kmp_enter_critical_section_reduce_block( ident_t * loc, kmp_int32 global_tid, kmp_critical_name * crit ) {
     // this lock was visible to a customer and to the threading profile tool as a serial overhead span
     //            (although it's used for an internal purpose only)
     //            why was it visible in previous implementation?
     //            should we keep it visible in new reduce block?
     kmp_user_lock_p lck;
 
 #if KMP_USE_DYNAMIC_LOCK
 
+    kmp_dyna_lock_t *lk = (kmp_dyna_lock_t *)crit;
+    // Check if it is initialized.
+    if (*lk == 0) {
         if (KMP_IS_D_LOCK(__kmp_user_lock_seq)) {
-        lck = (kmp_user_lock_p)crit;
-        if (*((kmp_dyna_lock_t *)lck) == 0) {
-            KMP_COMPARE_AND_STORE_ACQ32((volatile kmp_int32 *)lck, 0, KMP_GET_D_TAG(__kmp_user_lock_seq));
-        }
+            KMP_COMPARE_AND_STORE_ACQ32((volatile kmp_int32 *)crit, 0, KMP_GET_D_TAG(__kmp_user_lock_seq));
+        } else {
+            __kmp_init_indirect_csptr(crit, loc, global_tid, KMP_GET_I_TAG(__kmp_user_lock_seq));
+        }
+    // Branch for accessing the actual lock object and set operation. This branching is inevitable since
+    // this lock initialization does not follow the normal dispatch path (lock table is not used).
+    if (KMP_EXTRACT_D_TAG(lk) != 0) {
+        lck = (kmp_user_lock_p)lk;
         KMP_DEBUG_ASSERT(lck != NULL);
         if (__kmp_env_consistency_check) {
             __kmp_push_sync(global_tid, ct_critical, loc, lck, __kmp_user_lock_seq);
         }
-        KMP_D_LOCK_FUNC(lck, set)((kmp_dyna_lock_t *)lck, global_tid);
+        KMP_D_LOCK_FUNC(lk, set)(lk, global_tid);
     } else {
-        kmp_indirect_lock_t *ilk = __kmp_get_indirect_csptr(crit, loc, global_tid, __kmp_user_lock_seq);
-        KMP_DEBUG_ASSERT(ilk != NULL);
+        kmp_indirect_lock_t *ilk = *((kmp_indirect_lock_t **)lk);
+        lck = ilk->lock;
+        KMP_DEBUG_ASSERT(lck != NULL);
         if (__kmp_env_consistency_check) {
-            __kmp_push_sync(global_tid, ct_critical, loc, ilk->lock, __kmp_user_lock_seq);
+            __kmp_push_sync(global_tid, ct_critical, loc, lck, __kmp_user_lock_seq);
         }
-        KMP_I_LOCK_FUNC(ilk, set)(ilk->lock, global_tid);
+        KMP_I_LOCK_FUNC(ilk, set)(lck, global_tid);
     }
 
 #else // KMP_USE_DYNAMIC_LOCK
 
     // We know that the fast reduction code is only emitted by Intel compilers
     // with 32 byte critical sections. If there isn't enough space, then we
     // have to use a pointer.
     if ( __kmp_base_user_lock_size <= INTEL_CRITICAL_SIZE ) {

runtime/src/kmp_lock.h

 //
 
 enum kmp_lock_kind {
     lk_default = 0,
     lk_tas,
 #if KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM || KMP_ARCH_AARCH64)
     lk_futex,
 #endif
+#if KMP_USE_DYNAMIC_LOCK && KMP_USE_TSX
+    lk_hle,
+    lk_rtm,
+#endif
     lk_ticket,
     lk_queuing,
     lk_drdpa,
 #if KMP_USE_ADAPTIVE_LOCKS
     lk_adaptive
 #endif // KMP_USE_ADAPTIVE_LOCKS
 };
 

 
 #endif // KMP_USE_DYNAMIC_LOCK
 
 #undef KMP_PAD
 #undef KMP_GTID_DNE
 
 #if KMP_USE_DYNAMIC_LOCK
 
-#define KMP_HAS_FUTEX          (KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM))
-#define KMP_HAS_HLE            (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_MIC)
-#define KMP_USE_FAST_FUTEX     0 && KMP_HAS_FUTEX
-#define KMP_USE_FAST_TAS       1 && KMP_HAS_FUTEX
+// Shortcuts
+#define KMP_USE_FUTEX          (KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM || KMP_ARCH_AARCH64))
+#define KMP_USE_INLINED_TAS    (KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM)) && 1
+#define KMP_USE_INLINED_FUTEX  KMP_USE_FUTEX && 0
 
 // List of lock definitions; all nested locks are indirect locks.
 // hle lock is xchg lock prefixed with XACQUIRE/XRELEASE.
 // All nested locks are indirect lock types.
-#if KMP_HAS_FUTEX
-# if KMP_HAS_HLE
-#  define KMP_FOREACH_D_LOCK(m, a) m(tas, a) m(futex, a) m(hle, a)
-#  define KMP_LAST_D_LOCK lockseq_hle
-# else
-#  define KMP_FOREACH_D_LOCK(m, a) m(tas, a) m(futex, a)
-#  define KMP_LAST_D_LOCK lockseq_futex
-# endif // KMP_HAS_HLE
-# if KMP_USE_ADAPTIVE_LOCKS
-#  define KMP_FOREACH_I_LOCK(m, a) m(ticket, a) m(queuing, a) m(adaptive, a) m(drdpa, a)   \
-                               m(nested_tas, a) m(nested_futex, a) m(nested_ticket, a) \
-                               m(nested_queuing, a) m(nested_drdpa, a)
-# else
-#  define KMP_FOREACH_I_LOCK(m, a) m(ticket, a) m(queuing, a)                m(drdpa, a)   \
-                               m(nested_tas, a) m(nested_futex, a) m(nested_ticket, a) \
+#if KMP_USE_TSX
+# if KMP_USE_FUTEX
+#  define KMP_FOREACH_D_LOCK(m, a)  m(tas, a) m(futex, a) m(hle, a)
+#  define KMP_FOREACH_I_LOCK(m, a)  m(ticket, a) m(queuing, a) m(adaptive, a) m(drdpa, a) m(rtm, a) \
+                                    m(nested_tas, a) m(nested_futex, a) m(nested_ticket, a)         \
                                     m(nested_queuing, a) m(nested_drdpa, a)
-# endif // KMP_USE_ADAPTIVE_LOCKS
-#else
-# if KMP_HAS_HLE
-#  define KMP_FOREACH_D_LOCK(m, a) m(tas, a)             m(hle, a)
-#  define KMP_LAST_D_LOCK lockseq_hle
-# else
-#  define KMP_FOREACH_D_LOCK(m, a) m(tas, a)
-#  define KMP_LAST_D_LOCK lockseq_tas
-# endif // KMP_HAS_HLE
-# if KMP_USE_ADAPTIVE_LOCKS
-#  define KMP_FOREACH_I_LOCK(m, a) m(ticket, a) m(queuing, a) m(adaptive, a) m(drdpa, a)   \
-                               m(nested_tas, a)                    m(nested_ticket, a) \
+# else
+#  define KMP_FOREACH_D_LOCK(m, a)  m(tas, a)             m(hle, a)
+#  define KMP_FOREACH_I_LOCK(m, a)  m(ticket, a) m(queuing, a) m(adaptive, a) m(drdpa, a) m(rtm, a) \
+                                    m(nested_tas, a)                    m(nested_ticket, a)         \
+                                    m(nested_queuing, a) m(nested_drdpa, a)
+# endif // KMP_USE_FUTEX
+# define KMP_LAST_D_LOCK lockseq_hle
+#else
+# if KMP_USE_FUTEX
+#  define KMP_FOREACH_D_LOCK(m, a)  m(tas, a) m(futex, a)
+#  define KMP_FOREACH_I_LOCK(m, a)  m(ticket, a) m(queuing, a)                m(drdpa, a)           \
+                                    m(nested_tas, a) m(nested_futex, a) m(nested_ticket, a)         \
                                     m(nested_queuing, a) m(nested_drdpa, a)
+#  define KMP_LAST_D_LOCK lockseq_futex
 # else
-#  define KMP_FOREACH_I_LOCK(m, a) m(ticket, a) m(queuing, a)                m(drdpa, a)   \
-                               m(nested_tas, a)                    m(nested_ticket, a) \
+#  define KMP_FOREACH_D_LOCK(m, a)  m(tas, a)
+#  define KMP_FOREACH_I_LOCK(m, a)  m(ticket, a) m(queuing, a)                m(drdpa, a)           \
+                                    m(nested_tas, a)                    m(nested_ticket, a)         \
                                     m(nested_queuing, a) m(nested_drdpa, a)
-# endif // KMP_USE_ADAPTIVE_LOCKS
-#endif // KMP_HAS_FUTEX
+#  define KMP_LAST_D_LOCK lockseq_tas
+# endif // KMP_USE_FUTEX
+#endif // KMP_USE_TSX
 
 // Information used in dynamic dispatch
 #define KMP_LOCK_SHIFT   8 // number of low bits to be used as tag for direct locks
 #define KMP_FIRST_D_LOCK lockseq_tas
 #define KMP_FIRST_I_LOCK lockseq_ticket
 #define KMP_LAST_I_LOCK  lockseq_nested_drdpa
 #define KMP_NUM_I_LOCKS  (locktag_nested_drdpa+1) // number of indirect lock types
 

 #define KMP_LOCK_FREE(type)      (locktag_##type)
 
 // Returns "busy" lock value for the given lock teyp.
 #define KMP_LOCK_BUSY(v, type)   ((v)<<KMP_LOCK_SHIFT | locktag_##type)
 
 // Returns lock value after removing (shifting) lock tag.
 #define KMP_LOCK_STRIP(v)        ((v)>>KMP_LOCK_SHIFT)
 
-// Updates __kmp_user_lock_seq with the give lock type.
-#define KMP_STORE_LOCK_SEQ(type) (__kmp_user_lock_seq = lockseq_##type)
-
 // Internal entries for hinted lock initializers.
 extern void __kmp_init_lock_hinted(void **, int);
 extern void __kmp_init_nest_lock_hinted(void **, int);
 
 // Initializes global states and data structures for managing dynamic user locks.
 extern void __kmp_init_dynamic_user_locks();
 
 // Allocates and returns an indirect lock with the given indirect lock tag.
#define KMP_GET_I_LOCK_LOCATION(lck) ( __kmp_indirect_get_location[(lck)->type] != NULL       \
                                       : NULL )
 
 // Jump table for "get lock flags", available only for indirect locks.
 extern kmp_lock_flags_t (*__kmp_indirect_get_flags[KMP_NUM_I_LOCKS])(kmp_user_lock_p);
 #define KMP_GET_I_LOCK_FLAGS(lck) ( __kmp_indirect_get_flags[(lck)->type] != NULL       \
                                    ? __kmp_indirect_get_flags[(lck)->type]((lck)->lock) \
                                    : NULL )
 
-//
+#define KMP_I_LOCK_CHUNK 1024       // number of kmp_indirect_lock_t objects to be allocated together
+
 // Lock table for indirect locks.
-//
-// Simple linear structure is used to keep pointers to allocated indirect locks.
-extern kmp_indirect_lock_t **__kmp_indirect_lock_table;
-// Current size of the lock table; it may increase but never shrink.
-extern kmp_lock_index_t __kmp_indirect_lock_table_size;
-// Next index to be used for a new indirect lock (= number of indirect locks allocated).
-extern kmp_lock_index_t __kmp_indirect_lock_table_next;
+typedef struct kmp_indirect_lock_table {
+    kmp_indirect_lock_t **table;    // blocks of indirect locks allocated
+    kmp_lock_index_t size;          // size of the indirect lock table
+    kmp_lock_index_t next;          // index to the next lock to be allocated
+} kmp_indirect_lock_table_t;
+
+extern kmp_indirect_lock_table_t __kmp_i_lock_table;
+
+// Returns the indirect lock associated with the given index.
+#define KMP_GET_I_LOCK(index) (*(__kmp_i_lock_table.table + (index)/KMP_I_LOCK_CHUNK) + (index)%KMP_I_LOCK_CHUNK)
+
 // Number of locks in a lock block, which is fixed to "1" now.
 // TODO: No lock block implementation now. If we do support, we need to manage lock block data
 // structure for each indirect lock type.
 extern int __kmp_num_locks_in_block;
 
 // Fast lock table lookup without consistency checking
-#define KMP_LOOKUP_I_LOCK(l) ( (OMP_LOCK_T_SIZE < sizeof(void *))                 \
-                              ? __kmp_indirect_lock_table[KMP_EXTRACT_I_INDEX(l)] \
-                              : *((kmp_indirect_lock_t **)l) )
+#define KMP_LOOKUP_I_LOCK(l) ( (OMP_LOCK_T_SIZE < sizeof(void *))       \
+                               ? KMP_GET_I_LOCK(KMP_EXTRACT_I_INDEX(l)) \
+                               : *((kmp_indirect_lock_t **)(l)) )
 
 // Used once in kmp_error.c
 extern kmp_int32
 __kmp_get_user_lock_owner(kmp_user_lock_p, kmp_uint32);
 
 #else // KMP_USE_DYNAMIC_LOCK
 
 # define KMP_LOCK_BUSY(v, type)    (v)
 # define KMP_LOCK_FREE(type)       0
 # define KMP_LOCK_STRIP(v)         (v)
-# define KMP_STORE_LOCK_SEQ(seq)
 
 #endif // KMP_USE_DYNAMIC_LOCK
 
 #ifdef __cplusplus
 } // extern "C"
 #endif // __cplusplus
 
 #endif /* KMP_LOCK_H */
 

runtime/src/kmp_lock.cpp

 }
 
 #if KMP_USE_DYNAMIC_LOCK
 
 // Definitions of lock hints - can't include omp.h because of other name clashes.
 # ifndef __OMP_H 
 typedef enum kmp_lock_hint_t {
     kmp_lock_hint_none = 0,
-    kmp_lock_hint_contended,
     kmp_lock_hint_uncontended,
+    kmp_lock_hint_contended,
     kmp_lock_hint_nonspeculative,
     kmp_lock_hint_speculative,
-    kmp_lock_hint_adaptive,
+    kmp_lock_hint_hle,
+    kmp_lock_hint_rtm,
+    kmp_lock_hint_adaptive
 } kmp_lock_hint_t;
 # endif
 
 // Direct lock initializers. It simply writes a tag to the low 8 bits of the lock word.
 static void __kmp_init_direct_lock(kmp_dyna_lock_t *lck, kmp_dyna_lockseq_t seq)
 {
     TCW_4(*lck, KMP_GET_D_TAG(seq));
     KA_TRACE(20, ("__kmp_init_direct_lock: initialized direct lock with type#%d\n", seq));
 }
 
-#if KMP_HAS_HLE
+#if KMP_USE_TSX
 
 // HLE lock functions - imported from the testbed runtime.
 #define HLE_ACQUIRE ".byte 0xf2;"
 #define HLE_RELEASE ".byte 0xf3;"
 
 static inline kmp_uint32
 swap4(kmp_uint32 volatile *p, kmp_uint32 v)
 {

 }
 
 static int
 __kmp_test_hle_lock_with_checks(kmp_dyna_lock_t *lck, kmp_int32 gtid)
 {
     return __kmp_test_hle_lock(lck, gtid); // TODO: add checks
 }
 
-#endif // KMP_HAS_HLE
+static void
+__kmp_init_rtm_lock(kmp_queuing_lock_t *lck)
+{
+    __kmp_init_queuing_lock(lck);
+}
+
+static void
+__kmp_destroy_rtm_lock(kmp_queuing_lock_t *lck)
+{
+    __kmp_destroy_queuing_lock(lck);
+}
+
+static void
+__kmp_acquire_rtm_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid)
+{
+    unsigned retries=3, status;
+    do {
+        status = _xbegin();
+        if (status == _XBEGIN_STARTED) {
+            if (__kmp_is_unlocked_queuing_lock(lck))
+                return;
+            _xabort(0xff);
+        }
+        if ((status & _XABORT_EXPLICIT) && _XABORT_CODE(status) == 0xff) {
+            // Wait until lock becomes free
+            while (! __kmp_is_unlocked_queuing_lock(lck))
+                __kmp_yield(TRUE);
+        }
+        else if (!(status & _XABORT_RETRY))
+            break;
+    } while (retries--);
+
+    // Fall-back non-speculative lock (xchg)
+    __kmp_acquire_queuing_lock(lck, gtid);
+}
+
+static void
+__kmp_acquire_rtm_lock_with_checks(kmp_queuing_lock_t *lck, kmp_int32 gtid)
+{
+    __kmp_acquire_rtm_lock(lck, gtid);
+}
+
+static int
+__kmp_release_rtm_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid)
+{
+    if (__kmp_is_unlocked_queuing_lock(lck)) {
+        // Releasing from speculation
+        _xend();
+    }
+    else {
+        // Releasing from a real lock
+        __kmp_release_queuing_lock(lck, gtid);
+    }
+    return KMP_LOCK_RELEASED;
+}
+
+static int
+__kmp_release_rtm_lock_with_checks(kmp_queuing_lock_t *lck, kmp_int32 gtid)
+{
+    return __kmp_release_rtm_lock(lck, gtid);
+}
+
+static int
+__kmp_test_rtm_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid)
+{
+    unsigned retries=3, status;
+    do {
+        status = _xbegin();
+        if (status == _XBEGIN_STARTED && __kmp_is_unlocked_queuing_lock(lck)) {
+            return 1;
+        }
+        if (!(status & _XABORT_RETRY))
+            break;
+    } while (retries--);
+
+    return (__kmp_is_unlocked_queuing_lock(lck))? 1: 0;
+}
 
-// Entry functions for indirect locks (first element of direct_*_ops[]).
+static int
+__kmp_test_rtm_lock_with_checks(kmp_queuing_lock_t *lck, kmp_int32 gtid)
+{
+    return __kmp_test_rtm_lock(lck, gtid);
+}
+
+#endif // KMP_USE_TSX
+
+// Entry functions for indirect locks (first element of direct lock jump tables).
 static void __kmp_init_indirect_lock(kmp_dyna_lock_t * l, kmp_dyna_lockseq_t tag);
 static void __kmp_destroy_indirect_lock(kmp_dyna_lock_t * lock);
 static void __kmp_set_indirect_lock(kmp_dyna_lock_t * lock, kmp_int32);
 static int  __kmp_unset_indirect_lock(kmp_dyna_lock_t * lock, kmp_int32);
 static int  __kmp_test_indirect_lock(kmp_dyna_lock_t * lock, kmp_int32);
 static void __kmp_set_indirect_lock_with_checks(kmp_dyna_lock_t * lock, kmp_int32);
 static int  __kmp_unset_indirect_lock_with_checks(kmp_dyna_lock_t * lock, kmp_int32);
 static int  __kmp_test_indirect_lock_with_checks(kmp_dyna_lock_t * lock, kmp_int32);

 #undef expand
 
 // Exposes only one jump tables (*lock or *lock_with_checks).
 void (*(*__kmp_indirect_set))(kmp_user_lock_p, kmp_int32) = 0;
 int (*(*__kmp_indirect_unset))(kmp_user_lock_p, kmp_int32) = 0;
 int (*(*__kmp_indirect_test))(kmp_user_lock_p, kmp_int32) = 0;
 
 // Lock index table.
-kmp_indirect_lock_t **__kmp_indirect_lock_table;
-kmp_lock_index_t __kmp_indirect_lock_table_size;
-kmp_lock_index_t __kmp_indirect_lock_table_next;
+kmp_indirect_lock_table_t __kmp_i_lock_table;
 
 // Size of indirect locks.
-static kmp_uint32 __kmp_indirect_lock_size[KMP_NUM_I_LOCKS] = {
-    sizeof(kmp_ticket_lock_t),      sizeof(kmp_queuing_lock_t),
-#if KMP_USE_ADAPTIVE_LOCKS
-    sizeof(kmp_adaptive_lock_t),
-#endif
-    sizeof(kmp_drdpa_lock_t),
-    sizeof(kmp_tas_lock_t),
-#if KMP_HAS_FUTEX
-    sizeof(kmp_futex_lock_t),
-#endif
-    sizeof(kmp_ticket_lock_t),      sizeof(kmp_queuing_lock_t),
-    sizeof(kmp_drdpa_lock_t)
-};
+static kmp_uint32 __kmp_indirect_lock_size[KMP_NUM_I_LOCKS] = { 0 };
 
 // Jump tables for lock accessor/modifier.
 void (*__kmp_indirect_set_location[KMP_NUM_I_LOCKS])(kmp_user_lock_p, const ident_t *) = { 0 };
 void (*__kmp_indirect_set_flags[KMP_NUM_I_LOCKS])(kmp_user_lock_p, kmp_lock_flags_t) = { 0 };
 const ident_t * (*__kmp_indirect_get_location[KMP_NUM_I_LOCKS])(kmp_user_lock_p) = { 0 };
 kmp_lock_flags_t (*__kmp_indirect_get_flags[KMP_NUM_I_LOCKS])(kmp_user_lock_p) = { 0 };
 
 // Use different lock pools for different lock types.
 static kmp_indirect_lock_t * __kmp_indirect_lock_pool[KMP_NUM_I_LOCKS] = { 0 };
 
-// Inserts the given lock ptr to the lock table.
-kmp_lock_index_t 
-__kmp_insert_indirect_lock(kmp_indirect_lock_t *lck)
-{
-    kmp_lock_index_t next = __kmp_indirect_lock_table_next;
-    // Check capacity and double the size if required
-    if (next >= __kmp_indirect_lock_table_size) {
-        kmp_lock_index_t i;
-        kmp_lock_index_t size = __kmp_indirect_lock_table_size;
-        kmp_indirect_lock_t **old_table = __kmp_indirect_lock_table;
-        __kmp_indirect_lock_table = (kmp_indirect_lock_t **)__kmp_allocate(2*next*sizeof(kmp_indirect_lock_t *));
-        KMP_MEMCPY(__kmp_indirect_lock_table, old_table, next*sizeof(kmp_indirect_lock_t *));
-        __kmp_free(old_table);
-        __kmp_indirect_lock_table_size = 2*next;
-    }
-    // Insert lck to the table and return the index.
-    __kmp_indirect_lock_table[next] = lck;
-    __kmp_indirect_lock_table_next++;
-    return next;
-}
-
-// User lock allocator for dynamically dispatched locks.
+// User lock allocator for dynamically dispatched indirect locks.
+// Every entry of the indirect lock table holds the address and type of the allocated indrect lock
+// (kmp_indirect_lock_t), and the size of the table doubles when it is full. A destroyed indirect lock
+// object is returned to the reusable pool of locks, unique to each lock type.
 kmp_indirect_lock_t *
 __kmp_allocate_indirect_lock(void **user_lock, kmp_int32 gtid, kmp_indirect_locktag_t tag)
 {
     kmp_indirect_lock_t *lck;
     kmp_lock_index_t idx;
 
     __kmp_acquire_lock(&__kmp_global_lock, gtid);
 
     if (__kmp_indirect_lock_pool[tag] != NULL) {
+        // Reuse the allocated and destroyed lock object
         lck = __kmp_indirect_lock_pool[tag];
         if (OMP_LOCK_T_SIZE < sizeof(void *))
             idx = lck->lock->pool.index;
         __kmp_indirect_lock_pool[tag] = (kmp_indirect_lock_t *)lck->lock->pool.next;
+        KA_TRACE(20, ("__kmp_allocate_indirect_lock: reusing an existing lock %p\n", lck));
     } else {
-        lck = (kmp_indirect_lock_t *)__kmp_allocate(sizeof(kmp_indirect_lock_t));
+        idx = __kmp_i_lock_table.next;
+        // Check capacity and double the size if it is full
+        if (idx == __kmp_i_lock_table.size) {
+            // Double up the space for block pointers
+            int row = __kmp_i_lock_table.size/KMP_I_LOCK_CHUNK;
+            kmp_indirect_lock_t **old_table = __kmp_i_lock_table.table;
+            __kmp_i_lock_table.table = (kmp_indirect_lock_t **)__kmp_allocate(2*row*sizeof(kmp_indirect_lock_t *));
+            KMP_MEMCPY(__kmp_i_lock_table.table, old_table, row*sizeof(kmp_indirect_lock_t *));
+            __kmp_free(old_table);
+            // Allocate new objects in the new blocks
+            for (int i = row; i < 2*row; ++i)
+                *(__kmp_i_lock_table.table + i) = (kmp_indirect_lock_t *)
+                                                  __kmp_allocate(KMP_I_LOCK_CHUNK*sizeof(kmp_indirect_lock_t));
+            __kmp_i_lock_table.size = 2*idx;
+        }
+        __kmp_i_lock_table.next++;
+        lck = KMP_GET_I_LOCK(idx);
+        // Allocate a new base lock object
         lck->lock = (kmp_user_lock_p)__kmp_allocate(__kmp_indirect_lock_size[tag]);
-        if (OMP_LOCK_T_SIZE < sizeof(void *))
-            idx = __kmp_insert_indirect_lock(lck);
+        KA_TRACE(20, ("__kmp_allocate_indirect_lock: allocated a new lock %p\n", lck));
     }
 
     __kmp_release_lock(&__kmp_global_lock, gtid);
 
     lck->type = tag;
 
     if (OMP_LOCK_T_SIZE < sizeof(void *)) {
         *((kmp_lock_index_t *)user_lock) = idx << 1; // indirect lock word must be even.

 {
     if (__kmp_env_consistency_check) {
         kmp_indirect_lock_t *lck = NULL;
         if (user_lock == NULL) {
             KMP_FATAL(LockIsUninitialized, func);
         }
         if (OMP_LOCK_T_SIZE < sizeof(void *)) {
             kmp_lock_index_t idx = KMP_EXTRACT_I_INDEX(user_lock);
-            if (idx < 0 || idx >= __kmp_indirect_lock_table_size) {
+            if (idx < 0 || idx >= __kmp_i_lock_table.size) {
                 KMP_FATAL(LockIsUninitialized, func);
             }
-            lck = __kmp_indirect_lock_table[idx];
+            lck = KMP_GET_I_LOCK(idx);
         } else {
             lck = *((kmp_indirect_lock_t **)user_lock);
         }
         if (lck == NULL) {
             KMP_FATAL(LockIsUninitialized, func);
         }
         return lck; 
     } else {
         if (OMP_LOCK_T_SIZE < sizeof(void *)) {
-            return __kmp_indirect_lock_table[KMP_EXTRACT_I_INDEX(user_lock)];
+            return KMP_GET_I_LOCK(KMP_EXTRACT_I_INDEX(user_lock));
         } else {
             return *((kmp_indirect_lock_t **)user_lock);
         }
     }
 }
 
 static void
 __kmp_init_indirect_lock(kmp_dyna_lock_t * lock, kmp_dyna_lockseq_t seq)
 {
 #if KMP_USE_ADAPTIVE_LOCKS
     if (seq == lockseq_adaptive && !__kmp_cpuinfo.rtm) {
         KMP_WARNING(AdaptiveNotSupported, "kmp_lockseq_t", "adaptive");
         seq = lockseq_queuing;
     }
 #endif
+#if KMP_USE_TSX
+    if (seq == lockseq_rtm && !__kmp_cpuinfo.rtm) {
+        seq = lockseq_queuing;
+    }
+#endif
     kmp_indirect_locktag_t tag = KMP_GET_I_TAG(seq);
     kmp_indirect_lock_t *l = __kmp_allocate_indirect_lock((void **)lock, __kmp_entry_gtid(), tag);
     KMP_I_LOCK_FUNC(l, init)(l->lock);
-    KA_TRACE(20, ("__kmp_init_indirect_lock: initialized indirect lock, tag = %x\n", l->type));
+    KA_TRACE(20, ("__kmp_init_indirect_lock: initialized indirect lock with type#%d\n", seq));
 }
 
 static void
 __kmp_destroy_indirect_lock(kmp_dyna_lock_t * lock)
 {
     kmp_uint32 gtid = __kmp_entry_gtid();
     kmp_indirect_lock_t *l = __kmp_lookup_indirect_lock((void **)lock, "omp_destroy_lock");
     KMP_I_LOCK_FUNC(l, destroy)(l->lock);

 __kmp_init_lock_hinted(void **lock, int hint)
 {
     kmp_dyna_lockseq_t seq;
     switch (hint) {
         case kmp_lock_hint_uncontended:
             seq = lockseq_tas;
             break;
         case kmp_lock_hint_speculative:
-#if KMP_HAS_HLE
+#if KMP_USE_TSX
             seq = lockseq_hle;
 #else
             seq = lockseq_tas;
 #endif
             break;
         case kmp_lock_hint_adaptive:
 #if KMP_USE_ADAPTIVE_LOCKS
             seq = lockseq_adaptive;
 #else
             seq = lockseq_queuing;
 #endif
             break;
+#if KMP_USE_TSX
+        case kmp_lock_hint_hle:
+            seq = lockseq_hle;
+            break;
+        case kmp_lock_hint_rtm:
+            seq = lockseq_rtm;
+            break;
+#endif
         // Defaults to queuing locks.
         case kmp_lock_hint_contended:
         case kmp_lock_hint_nonspeculative:
         default:
             seq = lockseq_queuing;
             break;
     }
     if (KMP_IS_D_LOCK(seq)) {
switch (hint) {
         case kmp_lock_hint_uncontended:
             seq = lockseq_nested_tas;
             break;
         // Defaults to queuing locks.
         case kmp_lock_hint_contended:
         case kmp_lock_hint_nonspeculative:
         default:
             seq = lockseq_nested_queuing;
-            break;
     }
     KMP_INIT_I_LOCK(lock, seq);
 #if USE_ITT_BUILD
     kmp_indirect_lock_t *ilk = KMP_LOOKUP_I_LOCK(lock);
     __kmp_itt_lock_creating(ilk->lock, NULL);
 #endif
 }
 
-#if KMP_USE_ADAPTIVE_LOCKS
-# define init_lock_func(table, expand) {             \
-    table[locktag_ticket]         = expand(ticket);  \
-    table[locktag_queuing]        = expand(queuing); \
-    table[locktag_adaptive]       = expand(queuing); \
-    table[locktag_drdpa]          = expand(drdpa);   \
-    table[locktag_nested_ticket]  = expand(ticket);  \
-    table[locktag_nested_queuing] = expand(queuing); \
-    table[locktag_nested_drdpa]   = expand(drdpa);   \
-}
-#else
-# define init_lock_func(table, expand) {             \
-    table[locktag_ticket]         = expand(ticket);  \
-    table[locktag_queuing]        = expand(queuing); \
-    table[locktag_drdpa]          = expand(drdpa);   \
-    table[locktag_nested_ticket]  = expand(ticket);  \
-    table[locktag_nested_queuing] = expand(queuing); \
-    table[locktag_nested_drdpa]   = expand(drdpa);   \
-}
-#endif // KMP_USE_ADAPTIVE_LOCKS
-
 // Initializes data for dynamic user locks.
 void
 __kmp_init_dynamic_user_locks()
 {
     // Initialize jump table for the lock functions
     if (__kmp_env_consistency_check) {
         __kmp_direct_set     = direct_set_check;
         __kmp_direct_unset   = direct_unset_check;
         __kmp_direct_test    = direct_test_check;
         __kmp_indirect_set   = indirect_set_check;
         __kmp_indirect_unset = indirect_unset_check;
         __kmp_indirect_test  = indirect_test_check;
     }
     else {
         __kmp_direct_set     = direct_set;
         __kmp_direct_unset   = direct_unset;
         __kmp_direct_test    = direct_test;
         __kmp_indirect_set   = indirect_set;
         __kmp_indirect_unset = indirect_unset;
         __kmp_indirect_test  = indirect_test;
     }
 
     // Initialize lock index table
-    __kmp_indirect_lock_table = (kmp_indirect_lock_t **)__kmp_allocate(sizeof(kmp_indirect_lock_t *)*1024);
-    __kmp_indirect_lock_table_size = 1024;
-    __kmp_indirect_lock_table_next = 0;
+    __kmp_i_lock_table.size = KMP_I_LOCK_CHUNK;
+    __kmp_i_lock_table.table = (kmp_indirect_lock_t **)__kmp_allocate(sizeof(kmp_indirect_lock_t *));
+    *(__kmp_i_lock_table.table) = (kmp_indirect_lock_t *)
+                                  __kmp_allocate(KMP_I_LOCK_CHUNK*sizeof(kmp_indirect_lock_t)); 
+    __kmp_i_lock_table.next = 0;
+
+    // Indirect lock size
+    __kmp_indirect_lock_size[locktag_ticket]         = sizeof(kmp_ticket_lock_t);
+    __kmp_indirect_lock_size[locktag_queuing]        = sizeof(kmp_queuing_lock_t);
+#if KMP_USE_ADAPTIVE_LOCKS
+    __kmp_indirect_lock_size[locktag_adaptive]       = sizeof(kmp_adaptive_lock_t);
+#endif
+    __kmp_indirect_lock_size[locktag_drdpa]          = sizeof(kmp_drdpa_lock_t);
+#if KMP_USE_TSX
+    __kmp_indirect_lock_size[locktag_rtm]            = sizeof(kmp_queuing_lock_t);
+#endif
+    __kmp_indirect_lock_size[locktag_nested_tas]     = sizeof(kmp_tas_lock_t);
+#if KMP_USE_FUTEX
+    __kmp_indirect_lock_size[locktag_nested_futex]   = sizeof(kmp_futex_lock_t);
+#endif
+    __kmp_indirect_lock_size[locktag_nested_ticket]  = sizeof(kmp_ticket_lock_t);
+    __kmp_indirect_lock_size[locktag_nested_queuing] = sizeof(kmp_queuing_lock_t);
+    __kmp_indirect_lock_size[locktag_nested_drdpa]   = sizeof(kmp_drdpa_lock_t);
 
     // Initialize lock accessor/modifier
-    // Could have used designated initializer, but -TP /Qstd=c99 did not work with icl.exe.
-#define expand_func(l) (void (*)(kmp_user_lock_p, const ident_t *))__kmp_set_##l##_lock_location
-    init_lock_func(__kmp_indirect_set_location, expand_func);
-#undef expand_func
-#define expand_func(l) (void (*)(kmp_user_lock_p, kmp_lock_flags_t))__kmp_set_##l##_lock_flags
-    init_lock_func(__kmp_indirect_set_flags, expand_func);
-#undef expand_func
-#define expand_func(l) (const ident_t * (*)(kmp_user_lock_p))__kmp_get_##l##_lock_location
-    init_lock_func(__kmp_indirect_get_location, expand_func);
-#undef expand_func
-#define expand_func(l) (kmp_lock_flags_t (*)(kmp_user_lock_p))__kmp_get_##l##_lock_flags
-    init_lock_func(__kmp_indirect_get_flags, expand_func);
-#undef expand_func
+#define fill_jumps(table, expand, sep) {            \
+    table[locktag##sep##ticket]  = expand(ticket);  \
+    table[locktag##sep##queuing] = expand(queuing); \
+    table[locktag##sep##drdpa]   = expand(drdpa);   \
+}
+
+#if KMP_USE_ADAPTIVE_LOCKS
+# define fill_table(table, expand) {           \
+    fill_jumps(table, expand, _);              \
+    table[locktag_adaptive] = expand(queuing); \
+    fill_jumps(table, expand, _nested_);       \
+}
+#else
+# define fill_table(table, expand) {           \
+    fill_jumps(table, expand, _);              \
+    fill_jumps(table, expand, _nested_);       \
+}
+#endif // KMP_USE_ADAPTIVE_LOCKS
+
+#define expand(l) (void (*)(kmp_user_lock_p, const ident_t *))__kmp_set_##l##_lock_location
+    fill_table(__kmp_indirect_set_location, expand);
+#undef expand
+#define expand(l) (void (*)(kmp_user_lock_p, kmp_lock_flags_t))__kmp_set_##l##_lock_flags
+    fill_table(__kmp_indirect_set_flags, expand);
+#undef expand
+#define expand(l) (const ident_t * (*)(kmp_user_lock_p))__kmp_get_##l##_lock_location
+    fill_table(__kmp_indirect_get_location, expand);
+#undef expand
+#define expand(l) (kmp_lock_flags_t (*)(kmp_user_lock_p))__kmp_get_##l##_lock_flags
+    fill_table(__kmp_indirect_get_flags, expand);
+#undef expand
 
     __kmp_init_user_locks = TRUE;
 }
 
 // Clean up the lock table.
 void
 __kmp_cleanup_indirect_user_locks()
 {
     kmp_lock_index_t i;
     int k;
 
     // Clean up locks in the pools first (they were already destroyed before going into the pools).
     for (k = 0; k < KMP_NUM_I_LOCKS; ++k) {
         kmp_indirect_lock_t *l = __kmp_indirect_lock_pool[k];
         while (l != NULL) {
             kmp_indirect_lock_t *ll = l;
             l = (kmp_indirect_lock_t *)l->lock->pool.next;
-            if (OMP_LOCK_T_SIZE < sizeof(void *)) {
-                __kmp_indirect_lock_table[ll->lock->pool.index] = NULL;
-            }
+            KA_TRACE(20, ("__kmp_cleanup_indirect_user_locks: freeing %p from pool\n", ll));
             __kmp_free(ll->lock);
-            __kmp_free(ll);
+            ll->lock = NULL;
         }
     }
     // Clean up the remaining undestroyed locks.
-    for (i = 0; i < __kmp_indirect_lock_table_next; i++) {
-        kmp_indirect_lock_t *l = __kmp_indirect_lock_table[i];
-        if (l != NULL) {
+    for (i = 0; i < __kmp_i_lock_table.next; i++) {
+        kmp_indirect_lock_t *l = KMP_GET_I_LOCK(i);
+        if (l->lock != NULL) {
             // Locks not destroyed explicitly need to be destroyed here.
             KMP_I_LOCK_FUNC(l, destroy)(l->lock);
+            KA_TRACE(20, ("__kmp_cleanup_indirect_user_locks: destroy/freeing %p from table\n", l));
             __kmp_free(l->lock);
-            __kmp_free(l);
         }
     }
     // Free the table
-    __kmp_free(__kmp_indirect_lock_table);
+    for (i = 0; i < __kmp_i_lock_table.size / KMP_I_LOCK_CHUNK; i++)
+        __kmp_free(__kmp_i_lock_table.table[i]);
+    __kmp_free(__kmp_i_lock_table.table);
 
     __kmp_init_user_locks = FALSE;
 }
 
 enum kmp_lock_kind __kmp_user_lock_kind = lk_default;
 int __kmp_num_locks_in_block = 1;             // FIXME - tune this value
 
 #else // KMP_USE_DYNAMIC_LOCK

runtime/src/kmp_os.h

 # define USE_CMPXCHG_FIX 1
 #endif
 
 // Enable dynamic user lock
 #ifndef KMP_USE_DYNAMIC_LOCK
 # define KMP_USE_DYNAMIC_LOCK 0
 #endif
 
+// Enable TSX if dynamic user lock is turned on
+#if KMP_USE_DYNAMIC_LOCK
+# define KMP_USE_TSX             (KMP_ARCH_X86 || KMP_ARCH_X86_64)
+# ifndef KMP_USE_ADAPTIVE_LOCKS
+#  define KMP_USE_ADAPTIVE_LOCKS KMP_USE_TSX
+# endif
+#endif
+
 // Warning levels
 enum kmp_warnings_level {
     kmp_warnings_off = 0,   /* No warnings */
     kmp_warnings_low,     /* Minimal warnings (default) */
     kmp_warnings_explicit = 6,    /* Explicitly set to ON - more warnings */
     kmp_warnings_verbose    /* reserved */
 };
 
 #ifdef __cplusplus
 } // extern "C"
 #endif // __cplusplus
 
 #endif /* KMP_OS_H */
 // Safe C API
 #include "kmp_safe_c_api.h"
 

runtime/src/kmp_settings.c

 __kmp_stg_print_lock_block( kmp_str_buf_t * buffer, char const * name, void * data ) {
     __kmp_stg_print_int( buffer, name, __kmp_num_locks_in_block );
 } // __kmp_stg_print_lock_block
 
 // -------------------------------------------------------------------------------------------------
 // KMP_LOCK_KIND
 // -------------------------------------------------------------------------------------------------
 
+#if KMP_USE_DYNAMIC_LOCK
+# define KMP_STORE_LOCK_SEQ(a) (__kmp_user_lock_seq = lockseq_##a)
+#else
+# define KMP_STORE_LOCK_SEQ(a)
+#endif
+
 static void
 __kmp_stg_parse_lock_kind( char const * name, char const * value, void * data ) {
     if ( __kmp_init_user_locks ) {
         KMP_WARNING( EnvLockWarn, name );
         return;
     }
 
     if ( __kmp_str_match( "tas", 2, value )
else if ( __kmp_str_match( "adaptive", 1, value )  ) {
             KMP_STORE_LOCK_SEQ(adaptive);
         } else {
             KMP_WARNING( AdaptiveNotSupported, name, value );
             __kmp_user_lock_kind = lk_queuing;
             KMP_STORE_LOCK_SEQ(queuing);
         }
     }
 #endif // KMP_USE_ADAPTIVE_LOCKS
-#if KMP_USE_DYNAMIC_LOCK
+#if KMP_USE_DYNAMIC_LOCK && KMP_USE_TSX
+    else if ( __kmp_str_match("rtm", 1, value) ) {
+        if ( __kmp_cpuinfo.rtm ) {
+            __kmp_user_lock_kind = lk_rtm;
+            KMP_STORE_LOCK_SEQ(rtm);
+        } else {
+            KMP_WARNING( AdaptiveNotSupported, name, value );
+            __kmp_user_lock_kind = lk_queuing;
+            KMP_STORE_LOCK_SEQ(queuing);
+        }
+    }
     else if ( __kmp_str_match("hle", 1, value) ) {
+        __kmp_user_lock_kind = lk_hle;
         KMP_STORE_LOCK_SEQ(hle);
     }
 #endif
     else {
         KMP_WARNING( StgInvalidValue, name, value );
     }
 }
 
switch ( __kmp_user_lock_kind ) {
         break;
 
 #if KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64)
         case lk_futex:
         value = "futex";
         break;
 #endif
 
+#if KMP_USE_DYNAMIC_LOCK && KMP_USE_TSX
+        case lk_rtm:
+        value = "rtm";
+        break;
+
+        case lk_hle:
+        value = "hle";
+        break;
+#endif
+
         case lk_ticket:
         value = "ticket";
         break;
 
         case lk_queuing:
         value = "queuing";
         break;
 
for ( i = 0; i < 3 ; i++) {
             const char *tmp = next;
             SKIP_WS( tmp );
             if ( ( *next == ' ' || *next == '\t' ) && ( *tmp >= '0' && *tmp <= '9' ) ) {
                 KMP_WARNING( EnvSpacesNotAllowed, name, value );
                 return;
             }
 
             num = __kmp_str_to_int( buf, *next );
-            if ( num < 1 ) { // The number of retries should be > 0
+            if ( num < 0 ) { // The number of retries should be >= 0
                 msg = KMP_I18N_STR( ValueTooSmall );
                 num = 1;
             } else if ( num > KMP_INT_MAX ) {
                 msg = KMP_I18N_STR( ValueTooLarge );
                 num = KMP_INT_MAX;
             }
             if ( msg != NULL ) {
                 // Message is not empty. Print warning.
                 KMP_WARNING( ParseSizeIntWarn, name, value, msg );
                 KMP_INFORM( Using_int_Value, name, num );
             }
             if( total == 1 ) {
                 max_retries = num;
             } else if( total == 2 ) {
                 max_badness = num;
             }
         }
     }
     KMP_DEBUG_ASSERT( total > 0 );
     if( total <= 0 ) {
         KMP_WARNING( EnvSyntaxError, name, value );
         return;
     }
-    if( max_retries != 0 ) {
-        __kmp_adaptive_backoff_params.max_soft_retries = max_retries;
-    }
-    if( max_badness != 0 ) {
-        __kmp_adaptive_backoff_params.max_badness = max_badness;
-    }
-}
 
 
 static void
 __kmp_stg_print_adaptive_lock_props(kmp_str_buf_t * buffer, char const * name, void * data )
 {
     if( __kmp_env_format ) {
         KMP_STR_BUF_PRINT_NAME_EX(name);
     } else {