/*
 * kmp_dispatch.cpp: dynamic scheduling - iteration initialization and dispatch.
 * $Revision: 42674 $
 * $Date: 2013-09-18 11:12:49 -0500 (Wed, 18 Sep 2013) $
 */


//===----------------------------------------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is dual licensed under the MIT and the University of Illinois Open
// Source Licenses. See LICENSE.txt for details.
//
//===----------------------------------------------------------------------===//


/*
 * Dynamic scheduling initialization and dispatch.
 *
 * NOTE: __kmp_nth is a constant inside of any dispatch loop, however
 *       it may change values between parallel regions.  __kmp_max_nth
 *       is the largest value __kmp_nth may take, 1 is the smallest.
 *
 */

/* ------------------------------------------------------------------------ */
/* ------------------------------------------------------------------------ */

#include "kmp.h"
#include "kmp_i18n.h"
#include "kmp_itt.h"
#include "kmp_str.h"
#include "kmp_error.h"
#if KMP_OS_WINDOWS && KMP_ARCH_X86
    #include <float.h>
#endif

/* ------------------------------------------------------------------------ */
/* ------------------------------------------------------------------------ */

#ifdef KMP_STATIC_STEAL_ENABLED

    // replaces dispatch_private_info{32,64} structures and dispatch_private_info{32,64}_t types
    template< typename T >
    struct dispatch_private_infoXX_template {
        typedef typename traits_t< T >::unsigned_t  UT;
        typedef typename traits_t< T >::signed_t    ST;
        UT count;                // unsigned
        T  ub;
        /* Adding KMP_ALIGN_CACHE here doesn't help / can hurt performance */
        T  lb;
        ST st;                   // signed
        UT tc;                   // unsigned
        T  static_steal_counter; // for static_steal only; maybe better to put after ub

        /* parm[1-4] are used in different ways by different scheduling algorithms */

        // KMP_ALIGN( 32 ) ensures ( if the KMP_ALIGN macro is turned on )
        //    a) parm3 is properly aligned and
        //    b) all parm1-4 are in the same cache line.
        // Because of parm1-4 are used together, performance seems to be better
        // if they are in the same line (not measured though).

        struct KMP_ALIGN( 32 ) { // compiler does not accept sizeof(T)*4
            T  parm1;
            T  parm2;
            T  parm3;
            T  parm4;
        };

        UT ordered_lower; // unsigned
        UT ordered_upper; // unsigned
        #if KMP_OS_WINDOWS
        T  last_upper;
        #endif /* KMP_OS_WINDOWS */
    };

#else /* KMP_STATIC_STEAL_ENABLED */

    // replaces dispatch_private_info{32,64} structures and dispatch_private_info{32,64}_t types
    template< typename T >
    struct dispatch_private_infoXX_template {
        typedef typename traits_t< T >::unsigned_t  UT;
        typedef typename traits_t< T >::signed_t    ST;
        T  lb;
        T  ub;
        ST st;            // signed
        UT tc;            // unsigned

        T  parm1;
        T  parm2;
        T  parm3;
        T  parm4;

        UT count;         // unsigned

        UT ordered_lower; // unsigned
        UT ordered_upper; // unsigned
        #if KMP_OS_WINDOWS
	T  last_upper;
        #endif /* KMP_OS_WINDOWS */
    };

#endif /* KMP_STATIC_STEAL_ENABLED */

// replaces dispatch_private_info structure and dispatch_private_info_t type
template< typename T >
struct KMP_ALIGN_CACHE dispatch_private_info_template {
    // duplicate alignment here, otherwise size of structure is not correct in our compiler
    union KMP_ALIGN_CACHE private_info_tmpl {
        dispatch_private_infoXX_template< T > p;
        dispatch_private_info64_t             p64;
    } u;
    enum sched_type schedule;  /* scheduling algorithm */
    kmp_uint32      ordered;   /* ordered clause specified */
    kmp_uint32      ordered_bumped;
    kmp_int32   ordered_dummy[KMP_MAX_ORDERED-3]; // to retain the structure size after making order
    dispatch_private_info * next; /* stack of buffers for nest of serial regions */
    kmp_uint32      nomerge;   /* don't merge iters if serialized */
    kmp_uint32      type_size;
    enum cons_type  pushed_ws;
};


// replaces dispatch_shared_info{32,64} structures and dispatch_shared_info{32,64}_t types
template< typename UT >
struct dispatch_shared_infoXX_template {
    /* chunk index under dynamic, number of idle threads under static-steal;
       iteration index otherwise */
    volatile UT     iteration;
    volatile UT     num_done;
    volatile UT     ordered_iteration;
    UT   ordered_dummy[KMP_MAX_ORDERED-1]; // to retain the structure size making ordered_iteration scalar
};

// replaces dispatch_shared_info structure and dispatch_shared_info_t type
template< typename UT >
struct dispatch_shared_info_template {
    // we need union here to keep the structure size
    union shared_info_tmpl {
        dispatch_shared_infoXX_template< UT >  s;
        dispatch_shared_info64_t               s64;
    } u;
    volatile kmp_uint32     buffer_index;
};

/* ------------------------------------------------------------------------ */
/* ------------------------------------------------------------------------ */

static void
__kmp_static_delay( int arg )
{
    /* Work around weird code-gen bug that causes assert to trip */
    #if KMP_ARCH_X86_64 && KMP_OS_LINUX
    #else
        KMP_ASSERT( arg >= 0 );
    #endif
}

static void
__kmp_static_yield( int arg )
{
    __kmp_yield( arg );
}

#undef USE_TEST_LOCKS

// test_then_add template (general template should NOT be used)
template< typename T >
static __forceinline T
test_then_add( volatile T *p, T d ) { KMP_ASSERT(0); };

template<>
__forceinline kmp_int32
test_then_add< kmp_int32 >( volatile kmp_int32 *p, kmp_int32 d )
{
    kmp_int32 r;
    r = KMP_TEST_THEN_ADD32( p, d );
    return r;
}

template<>
__forceinline kmp_int64
test_then_add< kmp_int64 >( volatile kmp_int64 *p, kmp_int64 d )
{
    kmp_int64 r;
    r = KMP_TEST_THEN_ADD64( p, d );
    return r;
}

// test_then_inc_acq template (general template should NOT be used)
template< typename T >
static __forceinline T
test_then_inc_acq( volatile T *p ) { KMP_ASSERT(0); };

template<>
__forceinline kmp_int32
test_then_inc_acq< kmp_int32 >( volatile kmp_int32 *p )
{
    kmp_int32 r;
    r = KMP_TEST_THEN_INC_ACQ32( p );
    return r;
}

template<>
__forceinline kmp_int64
test_then_inc_acq< kmp_int64 >( volatile kmp_int64 *p )
{
    kmp_int64 r;
    r = KMP_TEST_THEN_INC_ACQ64( p );
    return r;
}

// test_then_inc template (general template should NOT be used)
template< typename T >
static __forceinline T
test_then_inc( volatile T *p ) { KMP_ASSERT(0); };

template<>
__forceinline kmp_int32
test_then_inc< kmp_int32 >( volatile kmp_int32 *p )
{
    kmp_int32 r;
    r = KMP_TEST_THEN_INC32( p );
    return r;
}

template<>
__forceinline kmp_int64
test_then_inc< kmp_int64 >( volatile kmp_int64 *p )
{
    kmp_int64 r;
    r = KMP_TEST_THEN_INC64( p );
    return r;
}

// compare_and_swap template (general template should NOT be used)
template< typename T >
static __forceinline kmp_int32
compare_and_swap( volatile T *p, T c, T s ) { KMP_ASSERT(0); };

template<>
__forceinline kmp_int32
compare_and_swap< kmp_int32 >( volatile kmp_int32 *p, kmp_int32 c, kmp_int32 s )
{
    return KMP_COMPARE_AND_STORE_REL32( p, c, s );
}

template<>
__forceinline kmp_int32
compare_and_swap< kmp_int64 >( volatile kmp_int64 *p, kmp_int64 c, kmp_int64 s )
{
    return KMP_COMPARE_AND_STORE_REL64( p, c, s );
}

/*
    Spin wait loop that first does pause, then yield.
    Waits until function returns non-zero when called with *spinner and check.
    Does NOT put threads to sleep.
#if USE_ITT_BUILD
    Arguments:
        obj -- is higher-level synchronization object to report to ittnotify. It is used to report
            locks consistently. For example, if lock is acquired immediately, its address is
            reported to ittnotify via KMP_FSYNC_ACQUIRED(). However, it lock cannot be acquired
            immediately and lock routine calls to KMP_WAIT_YIELD(), the later should report the same
            address, not an address of low-level spinner.
#endif // USE_ITT_BUILD
*/
template< typename UT >
// ToDo: make inline function (move to header file for icl)
static UT  // unsigned 4- or 8-byte type
__kmp_wait_yield( volatile UT * spinner,
                  UT            checker,
                  kmp_uint32 (* pred)( UT, UT )
                  USE_ITT_BUILD_ARG(void        * obj)    // Higher-level synchronization object, or NULL.
                  )
{
    // note: we may not belong to a team at this point
    register volatile UT         * spin          = spinner;
    register          UT           check         = checker;
    register          kmp_uint32   spins;
    register          kmp_uint32 (*f) ( UT, UT ) = pred;
    register          UT           r;

    KMP_FSYNC_SPIN_INIT( obj, (void*) spin );
    KMP_INIT_YIELD( spins );
    // main wait spin loop
    while(!f(r = *spin, check))
    {
        KMP_FSYNC_SPIN_PREPARE( obj );
        /* GEH - remove this since it was accidentally introduced when kmp_wait was split.
           It causes problems with infinite recursion because of exit lock */
        /* if ( TCR_4(__kmp_global.g.g_done) && __kmp_global.g.g_abort)
            __kmp_abort_thread(); */

        __kmp_static_delay(TRUE);

        // if we are oversubscribed,
        // or have waited a bit (and KMP_LIBRARY=throughput, then yield
        // pause is in the following code
        KMP_YIELD( TCR_4(__kmp_nth) > __kmp_avail_proc );
        KMP_YIELD_SPIN( spins );
    }
    KMP_FSYNC_SPIN_ACQUIRED( obj );
    return r;
}

template< typename UT >
static kmp_uint32 __kmp_eq( UT value, UT checker) {
    return value == checker;
}

template< typename UT >
static kmp_uint32 __kmp_neq( UT value, UT checker) {
    return value != checker;
}

template< typename UT >
static kmp_uint32 __kmp_lt( UT value, UT checker) {
    return value < checker;
}

template< typename UT >
static kmp_uint32 __kmp_ge( UT value, UT checker) {
    return value >= checker;
}

template< typename UT >
static kmp_uint32 __kmp_le( UT value, UT checker) {
    return value <= checker;
}


/* ------------------------------------------------------------------------ */
/* ------------------------------------------------------------------------ */

static void
__kmp_dispatch_deo_error( int *gtid_ref, int *cid_ref, ident_t *loc_ref )
{
    kmp_info_t *th;

    KMP_DEBUG_ASSERT( gtid_ref );

    if ( __kmp_env_consistency_check ) {
        th = __kmp_threads[*gtid_ref];
        if ( th -> th.th_root -> r.r_active
          && ( th -> th.th_dispatch -> th_dispatch_pr_current -> pushed_ws != ct_none ) ) {
            __kmp_push_sync( *gtid_ref, ct_ordered_in_pdo, loc_ref, NULL );
        }
    }
}

template< typename UT >
static void
__kmp_dispatch_deo( int *gtid_ref, int *cid_ref, ident_t *loc_ref )
{
    typedef typename traits_t< UT >::signed_t    ST;
    dispatch_private_info_template< UT > * pr;

    int gtid = *gtid_ref;
//    int  cid = *cid_ref;
    kmp_info_t *th = __kmp_threads[ gtid ];
    KMP_DEBUG_ASSERT( th -> th.th_dispatch );

    KD_TRACE(100, ("__kmp_dispatch_deo: T#%d called\n", gtid ) );
    if ( __kmp_env_consistency_check ) {
        pr = reinterpret_cast< dispatch_private_info_template< UT >* >
            ( th -> th.th_dispatch -> th_dispatch_pr_current );
        if ( pr -> pushed_ws != ct_none ) {
            __kmp_push_sync( gtid, ct_ordered_in_pdo, loc_ref, NULL );
        }
    }

    if ( ! th -> th.th_team -> t.t_serialized ) {
        dispatch_shared_info_template< UT >  * sh = reinterpret_cast< dispatch_shared_info_template< UT >* >
            ( th -> th.th_dispatch -> th_dispatch_sh_current );
        UT  lower;

        if ( ! __kmp_env_consistency_check ) {
                pr = reinterpret_cast< dispatch_private_info_template< UT >* >
                    ( th -> th.th_dispatch -> th_dispatch_pr_current );
        }
        lower = pr->u.p.ordered_lower;

        #if ! defined( KMP_GOMP_COMPAT )
            if ( __kmp_env_consistency_check ) {
                if ( pr->ordered_bumped ) {
                    struct cons_header *p = __kmp_threads[ gtid ]->th.th_cons;
                    __kmp_error_construct2(
                        kmp_i18n_msg_CnsMultipleNesting,
                        ct_ordered_in_pdo, loc_ref,
                        & p->stack_data[ p->w_top ]
                    );
                }
            }
        #endif /* !defined(KMP_GOMP_COMPAT) */

        KMP_MB();
        #ifdef KMP_DEBUG
        {
            const char * buff;
            // create format specifiers before the debug output
            buff = __kmp_str_format(
                "__kmp_dispatch_deo: T#%%d before wait: ordered_iter:%%%s lower:%%%s\n",
                traits_t< UT >::spec, traits_t< UT >::spec );
            KD_TRACE(1000, ( buff, gtid, sh->u.s.ordered_iteration, lower ) );
            __kmp_str_free( &buff );
        }
        #endif

        __kmp_wait_yield< UT >( &sh->u.s.ordered_iteration, lower, __kmp_ge< UT >
                                USE_ITT_BUILD_ARG( NULL )
                                );
        KMP_MB();  /* is this necessary? */
        #ifdef KMP_DEBUG
        {
            const char * buff;
            // create format specifiers before the debug output
            buff = __kmp_str_format(
                "__kmp_dispatch_deo: T#%%d after wait: ordered_iter:%%%s lower:%%%s\n",
                traits_t< UT >::spec, traits_t< UT >::spec );
            KD_TRACE(1000, ( buff, gtid, sh->u.s.ordered_iteration, lower ) );
            __kmp_str_free( &buff );
        }
        #endif
    }
    KD_TRACE(100, ("__kmp_dispatch_deo: T#%d returned\n", gtid ) );
}

static void
__kmp_dispatch_dxo_error( int *gtid_ref, int *cid_ref, ident_t *loc_ref )
{
    kmp_info_t *th;

    if ( __kmp_env_consistency_check ) {
        th = __kmp_threads[*gtid_ref];
        if ( th -> th.th_dispatch -> th_dispatch_pr_current -> pushed_ws != ct_none ) {
            __kmp_pop_sync( *gtid_ref, ct_ordered_in_pdo, loc_ref );
        }
    }
}

template< typename UT >
static void
__kmp_dispatch_dxo( int *gtid_ref, int *cid_ref, ident_t *loc_ref )
{
    typedef typename traits_t< UT >::signed_t    ST;
    dispatch_private_info_template< UT > * pr;

    int gtid = *gtid_ref;
//    int  cid = *cid_ref;
    kmp_info_t *th = __kmp_threads[ gtid ];
    KMP_DEBUG_ASSERT( th -> th.th_dispatch );

    KD_TRACE(100, ("__kmp_dispatch_dxo: T#%d called\n", gtid ) );
    if ( __kmp_env_consistency_check ) {
        pr = reinterpret_cast< dispatch_private_info_template< UT >* >
            ( th -> th.th_dispatch -> th_dispatch_pr_current );
        if ( pr -> pushed_ws != ct_none ) {
            __kmp_pop_sync( gtid, ct_ordered_in_pdo, loc_ref );
        }
    }

    if ( ! th -> th.th_team -> t.t_serialized ) {
        dispatch_shared_info_template< UT >  * sh = reinterpret_cast< dispatch_shared_info_template< UT >* >
            ( th -> th.th_dispatch -> th_dispatch_sh_current );

        if ( ! __kmp_env_consistency_check ) {
            pr = reinterpret_cast< dispatch_private_info_template< UT >* >
                ( th -> th.th_dispatch -> th_dispatch_pr_current );
        }

        KMP_FSYNC_RELEASING( & sh->u.s.ordered_iteration );
        #if ! defined( KMP_GOMP_COMPAT )
            if ( __kmp_env_consistency_check ) {
                if ( pr->ordered_bumped != 0 ) {
                    struct cons_header *p = __kmp_threads[ gtid ]->th.th_cons;
                    /* How to test it? - OM */
                    __kmp_error_construct2(
                        kmp_i18n_msg_CnsMultipleNesting,
                        ct_ordered_in_pdo, loc_ref,
                        & p->stack_data[ p->w_top ]
                    );
                }
            }
        #endif /* !defined(KMP_GOMP_COMPAT) */

        KMP_MB();       /* Flush all pending memory write invalidates.  */

        pr->ordered_bumped += 1;

        KD_TRACE(1000, ("__kmp_dispatch_dxo: T#%d bumping ordered ordered_bumped=%d\n",
                        gtid, pr->ordered_bumped ) );

        KMP_MB();       /* Flush all pending memory write invalidates.  */

        /* TODO use general release procedure? */
        test_then_inc< ST >( (volatile ST *) & sh->u.s.ordered_iteration );

        KMP_MB();       /* Flush all pending memory write invalidates.  */
    }
    KD_TRACE(100, ("__kmp_dispatch_dxo: T#%d returned\n", gtid ) );
}

/* Computes and returns x to the power of y, where y must a non-negative integer */
template< typename UT >
static __forceinline long double
__kmp_pow(long double x, UT y) {
    long double s=1.0L;

    KMP_DEBUG_ASSERT(x > 0.0 && x < 1.0);
    //KMP_DEBUG_ASSERT(y >= 0); // y is unsigned
    while(y) {
        if ( y & 1 )
            s *= x;
        x *= x;
        y >>= 1;
    }
    return s;
}

/* Computes and returns the number of unassigned iterations after idx chunks have been assigned
   (the total number of unassigned iterations in chunks with index greater than or equal to idx).
   __forceinline seems to be broken so that if we __forceinline this function, the behavior is wrong
   (one of the unit tests, sch_guided_analytical_basic.cpp, fails)
*/
template< typename T >
static __inline typename traits_t< T >::unsigned_t
__kmp_dispatch_guided_remaining(
    T                                  tc,
    typename traits_t< T >::floating_t base,
    typename traits_t< T >::unsigned_t idx
) {
    /* Note: On Windows* OS on IA-32 architecture and Intel(R) 64, at
       least for ICL 8.1, long double arithmetic may not really have
       long double precision, even with /Qlong_double.  Currently, we
       workaround that in the caller code, by manipulating the FPCW for
       Windows* OS on IA-32 architecture.  The lack of precision is not
       expected to be a correctness issue, though.
    */
    typedef typename traits_t< T >::unsigned_t  UT;

    long double x = tc * __kmp_pow< UT >(base, idx);
    UT r = (UT) x;
    if ( x == r )
        return r;
    return r + 1;
}

// Parameters of the guided-iterative algorithm:
//   p2 = n * nproc * ( chunk + 1 )  // point of switching to dynamic
//   p3 = 1 / ( n * nproc )          // remaining iterations multiplier
// by default n = 2. For example with n = 3 the chunks distribution will be more flat.
// With n = 1 first chunk is the same as for static schedule, e.g. trip / nproc.
static int guided_int_param = 2;
static double guided_flt_param = 0.5;// = 1.0 / guided_int_param;

// UT - unsigned flavor of T, ST - signed flavor of T,
// DBL - double if sizeof(T)==4, or long double if sizeof(T)==8
template< typename T >
static void
__kmp_dispatch_init(
    ident_t                        * loc,
    int                              gtid,
    enum sched_type                  schedule,
    T                                lb,
    T                                ub,
    typename traits_t< T >::signed_t st,
    typename traits_t< T >::signed_t chunk,
    int                              push_ws
) {
    typedef typename traits_t< T >::unsigned_t  UT;
    typedef typename traits_t< T >::signed_t    ST;
    typedef typename traits_t< T >::floating_t  DBL;
    static const int ___kmp_size_type = sizeof( UT );

    int                                            active;
    T                                              tc;
    kmp_info_t *                                   th;
    kmp_team_t *                                   team;
    kmp_uint32                                     my_buffer_index;
    dispatch_private_info_template< T >          * pr;
    dispatch_shared_info_template< UT > volatile * sh;

    KMP_BUILD_ASSERT( sizeof( dispatch_private_info_template< T > ) == sizeof( dispatch_private_info ) );
    KMP_BUILD_ASSERT( sizeof( dispatch_shared_info_template< UT > ) == sizeof( dispatch_shared_info ) );

    if ( ! TCR_4( __kmp_init_parallel ) )
        __kmp_parallel_initialize();

    #ifdef KMP_DEBUG
    {
        const char * buff;
        // create format specifiers before the debug output
        buff = __kmp_str_format(
            "__kmp_dispatch_init: T#%%d called: schedule:%%d chunk:%%%s lb:%%%s ub:%%%s st:%%%s\n",
            traits_t< ST >::spec, traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec );
        KD_TRACE(10, ( buff, gtid, schedule, chunk, lb, ub, st ) );
        __kmp_str_free( &buff );
    }
    #endif
    /* setup data */
    th     = __kmp_threads[ gtid ];
    team   = th -> th.th_team;
    active = ! team -> t.t_serialized;
    th->th.th_ident = loc;

    if ( ! active ) {
        pr = reinterpret_cast< dispatch_private_info_template< T >* >
            ( th -> th.th_dispatch -> th_disp_buffer ); /* top of the stack */
    } else {
        KMP_DEBUG_ASSERT( th->th.th_dispatch ==
                &th->th.th_team->t.t_dispatch[th->th.th_info.ds.ds_tid] );

        my_buffer_index = th->th.th_dispatch->th_disp_index ++;

        /* What happens when number of threads changes, need to resize buffer? */
        pr = reinterpret_cast< dispatch_private_info_template< T >  * >
            ( &th -> th.th_dispatch -> th_disp_buffer[ my_buffer_index % KMP_MAX_DISP_BUF ] );
        sh = reinterpret_cast< dispatch_shared_info_template< UT > volatile * >
            ( &team -> t.t_disp_buffer[ my_buffer_index % KMP_MAX_DISP_BUF ] );
    }

    /* Pick up the nomerge/ordered bits from the scheduling type */
    if ( (schedule >= kmp_nm_lower) && (schedule < kmp_nm_upper) ) {
        pr->nomerge = TRUE;
        schedule = (enum sched_type)(((int)schedule) - (kmp_nm_lower - kmp_sch_lower));
    } else {
        pr->nomerge = FALSE;
    }
    pr->type_size = ___kmp_size_type; // remember the size of variables
    if ( kmp_ord_lower & schedule ) {
        pr->ordered = TRUE;
        schedule = (enum sched_type)(((int)schedule) - (kmp_ord_lower - kmp_sch_lower));
    } else {
        pr->ordered = FALSE;
    }
    if ( schedule == kmp_sch_static ) {
        schedule = __kmp_static;
    } else {
        if ( schedule == kmp_sch_runtime ) {
            #if OMP_30_ENABLED
                // Use the scheduling specified by OMP_SCHEDULE (or __kmp_sch_default if not specified)
                schedule = team -> t.t_sched.r_sched_type;
                // Detail the schedule if needed (global controls are differentiated appropriately)
                if ( schedule == kmp_sch_guided_chunked ) {
                    schedule = __kmp_guided;
                } else if ( schedule == kmp_sch_static ) {
                    schedule = __kmp_static;
                }
                // Use the chunk size specified by OMP_SCHEDULE (or default if not specified)
                chunk = team -> t.t_sched.chunk;
            #else
                kmp_r_sched_t r_sched = __kmp_get_schedule_global();
                // Use the scheduling specified by OMP_SCHEDULE and/or KMP_SCHEDULE or default
                schedule = r_sched.r_sched_type;
                chunk    = r_sched.chunk;
            #endif

            #ifdef KMP_DEBUG
            {
                const char * buff;
                // create format specifiers before the debug output
                buff = __kmp_str_format(
                    "__kmp_dispatch_init: T#%%d new: schedule:%%d chunk:%%%s\n",
                    traits_t< ST >::spec );
                KD_TRACE(10, ( buff, gtid, schedule, chunk ) );
                __kmp_str_free( &buff );
            }
            #endif
        } else {
            if ( schedule == kmp_sch_guided_chunked ) {
                schedule = __kmp_guided;
            }
            if ( chunk <= 0 ) {
                chunk = KMP_DEFAULT_CHUNK;
            }
        }

        #if OMP_30_ENABLED
        if ( schedule == kmp_sch_auto ) {
            // mapping and differentiation: in the __kmp_do_serial_initialize()
            schedule = __kmp_auto;
            #ifdef KMP_DEBUG
            {
                const char * buff;
                // create format specifiers before the debug output
                buff = __kmp_str_format(
                    "__kmp_dispatch_init: kmp_sch_auto: T#%%d new: schedule:%%d chunk:%%%s\n",
                    traits_t< ST >::spec );
                KD_TRACE(10, ( buff, gtid, schedule, chunk ) );
                __kmp_str_free( &buff );
            }
            #endif
        }
        #endif // OMP_30_ENABLED

        /* guided analytical not safe for too many threads */
        if ( team->t.t_nproc > 1<<20 && schedule == kmp_sch_guided_analytical_chunked ) {
            schedule = kmp_sch_guided_iterative_chunked;
            KMP_WARNING( DispatchManyThreads );
        }
        pr->u.p.parm1 = chunk;
    }
    KMP_ASSERT2( (kmp_sch_lower < schedule && schedule < kmp_sch_upper),
                "unknown scheduling type" );

    pr->u.p.count = 0;

    if ( __kmp_env_consistency_check ) {
        if ( st == 0 ) {
            __kmp_error_construct(
                kmp_i18n_msg_CnsLoopIncrZeroProhibited,
                ( pr->ordered ? ct_pdo_ordered : ct_pdo ), loc
            );
        }
    }

    tc = ( ub - lb + st );
    if ( st != 1 ) {
        if ( st < 0 ) {
            if ( lb < ub ) {
                tc = 0;            // zero-trip
            } else {   // lb >= ub
                tc = (ST)tc / st;  // convert to signed division
            }
        } else {       // st > 0
            if ( ub < lb ) {
                tc = 0;            // zero-trip
            } else {   // lb >= ub
                tc /= st;
            }
        }
    } else if ( ub < lb ) {        // st == 1
        tc = 0;                    // zero-trip
    }

    pr->u.p.lb = lb;
    pr->u.p.ub = ub;
    pr->u.p.st = st;
    pr->u.p.tc = tc;

    #if KMP_OS_WINDOWS
    pr->u.p.last_upper = ub + st;
    #endif /* KMP_OS_WINDOWS */

    /* NOTE: only the active parallel region(s) has active ordered sections */

    if ( active ) {
        if ( pr->ordered == 0 ) {
            th -> th.th_dispatch -> th_deo_fcn = __kmp_dispatch_deo_error;
            th -> th.th_dispatch -> th_dxo_fcn = __kmp_dispatch_dxo_error;
        } else {
            pr->ordered_bumped = 0;

            pr->u.p.ordered_lower = 1;
            pr->u.p.ordered_upper = 0;

            th -> th.th_dispatch -> th_deo_fcn = __kmp_dispatch_deo< UT >;
            th -> th.th_dispatch -> th_dxo_fcn = __kmp_dispatch_dxo< UT >;
        }
    }

    if ( __kmp_env_consistency_check ) {
        enum cons_type ws = pr->ordered ? ct_pdo_ordered : ct_pdo;
        if ( push_ws ) {
            __kmp_push_workshare( gtid, ws, loc );
            pr->pushed_ws = ws;
        } else {
            __kmp_check_workshare( gtid, ws, loc );
            pr->pushed_ws = ct_none;
        }
    }

    switch ( schedule ) {
    #if  ( KMP_STATIC_STEAL_ENABLED && KMP_ARCH_X86_64 )
    case kmp_sch_static_steal:
        {
            T nproc = team->t.t_nproc;
            T ntc, init;

            KD_TRACE(100, ("__kmp_dispatch_init: T#%d kmp_sch_static_steal case\n", gtid ) );

            ntc = (tc % chunk ? 1 : 0) + tc / chunk;
            if ( nproc > 1 && ntc >= nproc ) {
                T id = __kmp_tid_from_gtid(gtid);
                T small_chunk, extras;

                small_chunk = ntc / nproc;
                extras = ntc % nproc;

                init = id * small_chunk + ( id < extras ? id : extras );
                pr->u.p.count = init;
                pr->u.p.ub = init + small_chunk + ( id < extras ? 1 : 0 );

                pr->u.p.parm2 = lb;
                //pr->pfields.parm3 = 0; // it's not used in static_steal
                pr->u.p.parm4 = id;
                pr->u.p.st = st;
                break;
            } else {
                KD_TRACE(100, ("__kmp_dispatch_init: T#%d falling-through to kmp_sch_static_balanced\n",
                               gtid ) );
                schedule = kmp_sch_static_balanced;
                /* too few iterations: fall-through to kmp_sch_static_balanced */
            } // if
            /* FALL-THROUGH to static balanced */
        } // case
    #endif
    case kmp_sch_static_balanced:
        {
            T nproc = team->t.t_nproc;
            T init, limit;

            KD_TRACE(100, ("__kmp_dispatch_init: T#%d kmp_sch_static_balanced case\n",
                            gtid ) );

            if ( nproc > 1 ) {
                T id = __kmp_tid_from_gtid(gtid);

                if ( tc < nproc ) {
                    if ( id < tc ) {
                        init = id;
                        limit = id;
                        pr->u.p.parm1 = (id == tc - 1);  /* parm1 stores *plastiter */
                    } else {
                        pr->u.p.count = 1;  /* means no more chunks to execute */
                        pr->u.p.parm1 = FALSE;
                        break;
                    }
                } else {
                    T small_chunk = tc / nproc;
                    T extras = tc % nproc;
                    init = id * small_chunk + (id < extras ? id : extras);
                    limit = init + small_chunk - (id < extras ? 0 : 1);
                    pr->u.p.parm1 = (id == nproc - 1);
                }
            } else {
                if ( tc > 0 ) {
                    init = 0;
                    limit = tc - 1;
                    pr->u.p.parm1 = TRUE;
                } else {
                    // zero trip count
                    pr->u.p.count = 1;  /* means no more chunks to execute */
                    pr->u.p.parm1 = FALSE;
                    break;
                }
            }
            if ( st == 1 ) {
                pr->u.p.lb = lb + init;
                pr->u.p.ub = lb + limit;
            } else {
                T ub_tmp = lb + limit * st;   // calculated upper bound, "ub" is user-defined upper bound
                pr->u.p.lb = lb + init * st;
                // adjust upper bound to "ub" if needed, so that MS lastprivate will match it exactly
                if ( st > 0 ) {
                    pr->u.p.ub = ( ub_tmp + st > ub ? ub : ub_tmp );
                } else {
                    pr->u.p.ub = ( ub_tmp + st < ub ? ub : ub_tmp );
                }
            }
            if ( pr->ordered ) {
                pr->u.p.ordered_lower = init;
                pr->u.p.ordered_upper = limit;
            }
            break;
        } // case
    case kmp_sch_guided_iterative_chunked :
        {
            T nproc = team->t.t_nproc;
            KD_TRACE(100,("__kmp_dispatch_init: T#%d kmp_sch_guided_iterative_chunked case\n",gtid));

            if ( nproc > 1 ) {
                if ( (2L * chunk + 1 ) * nproc >= tc ) {
                    /* chunk size too large, switch to dynamic */
                    schedule = kmp_sch_dynamic_chunked;
                } else {
                    // when remaining iters become less than parm2 - switch to dynamic
                    pr->u.p.parm2 = guided_int_param * nproc * ( chunk + 1 );
                    *(double*)&pr->u.p.parm3 = guided_flt_param / nproc;   // may occupy parm3 and parm4
                }
            } else {
                KD_TRACE(100,("__kmp_dispatch_init: T#%d falling-through to kmp_sch_static_greedy\n",gtid));
                schedule = kmp_sch_static_greedy;
                /* team->t.t_nproc == 1: fall-through to kmp_sch_static_greedy */
                KD_TRACE(100,("__kmp_dispatch_init: T#%d kmp_sch_static_greedy case\n",gtid));
                pr->u.p.parm1 = tc;
            } // if
        } // case
        break;
    case kmp_sch_guided_analytical_chunked:
        {
            T nproc = team->t.t_nproc;
            KD_TRACE(100, ("__kmp_dispatch_init: T#%d kmp_sch_guided_analytical_chunked case\n", gtid));

            if ( nproc > 1 ) {
                if ( (2L * chunk + 1 ) * nproc >= tc ) {
                    /* chunk size too large, switch to dynamic */
                    schedule = kmp_sch_dynamic_chunked;
                } else {
                    /* commonly used term: (2 nproc - 1)/(2 nproc) */
                    DBL x;

                    #if KMP_OS_WINDOWS && KMP_ARCH_X86
                    /* Linux* OS already has 64-bit computation by default for
		       long double, and on Windows* OS on Intel(R) 64,
		       /Qlong_double doesn't work.  On Windows* OS
		       on IA-32 architecture, we need to set precision to
		       64-bit instead of the default 53-bit. Even though long
		       double doesn't work on Windows* OS on Intel(R) 64, the
		       resulting lack of precision is not expected to impact
		       the correctness of the algorithm, but this has not been
		       mathematically proven.
                    */
                    // save original FPCW and set precision to 64-bit, as
                    // Windows* OS on IA-32 architecture defaults to 53-bit
                    unsigned int oldFpcw = _control87(0,0);
                    _control87(_PC_64,_MCW_PC); // 0,0x30000
                    #endif
                    /* value used for comparison in solver for cross-over point */
                    long double target = ((long double)chunk * 2 + 1) * nproc / tc;

                    /* crossover point--chunk indexes equal to or greater than
		       this point switch to dynamic-style scheduling */
                    UT   cross;

                    /* commonly used term: (2 nproc - 1)/(2 nproc) */
                    x = (long double)1.0 - (long double)0.5 / nproc;

                    #ifdef KMP_DEBUG
                    { // test natural alignment
                        struct _test_a {
                            char a;
                            union {
                                char b;
                                DBL  d;
                            };
                        } t;
                        ptrdiff_t natural_alignment = (ptrdiff_t)&t.b - (ptrdiff_t)&t - (ptrdiff_t)1;
                        //__kmp_warn( " %llx %llx %lld", (long long)&t.d, (long long)&t, (long long)natural_alignment );
                        KMP_DEBUG_ASSERT( ( ( (ptrdiff_t)&pr->u.p.parm3 ) & ( natural_alignment ) ) == 0 );
                    }
                    #endif // KMP_DEBUG

                    /* save the term in thread private dispatch structure */
                    *(DBL*)&pr->u.p.parm3 = x;

                    /* solve for the crossover point to the nearest integer i for which C_i <= chunk */
                    {
                        UT          left, right, mid;
                        long double p;

                        /* estimate initial upper and lower bound */

                        /* doesn't matter what value right is as long as it is positive, but
                           it affects performance of the solver
                        */
                        right = 229;
                        p = __kmp_pow< UT >(x,right);
                        if ( p > target ) {
                            do{
                                p *= p;
                                right <<= 1;
                            } while(p>target && right < (1<<27));
                            left = right >> 1; /* lower bound is previous (failed) estimate of upper bound */
                        } else {
                            left = 0;
                        }

                        /* bisection root-finding method */
                        while ( left + 1 < right ) {
                            mid = (left + right) / 2;
                            if ( __kmp_pow< UT >(x,mid) > target ) {
                                left = mid;
                            } else {
                                right = mid;
                            }
                        } // while
                        cross = right;
                    }
                    /* assert sanity of computed crossover point */
                    KMP_ASSERT(cross && __kmp_pow< UT >(x, cross - 1) > target && __kmp_pow< UT >(x, cross) <= target);

                    /* save the crossover point in thread private dispatch structure */
                    pr->u.p.parm2 = cross;

                    // C75803
                    #if ( ( KMP_OS_LINUX || KMP_OS_WINDOWS ) && KMP_ARCH_X86 ) && ( ! defined( KMP_I8 ) )
                        #define GUIDED_ANALYTICAL_WORKAROUND (*( DBL * )&pr->u.p.parm3)
                    #else
                        #define GUIDED_ANALYTICAL_WORKAROUND (x)
                    #endif
                    /* dynamic-style scheduling offset */
                    pr->u.p.count = tc - __kmp_dispatch_guided_remaining(tc, GUIDED_ANALYTICAL_WORKAROUND, cross) - cross * chunk;
                    #if KMP_OS_WINDOWS && KMP_ARCH_X86
                        // restore FPCW
                        _control87(oldFpcw,_MCW_PC);
                    #endif
                } // if
            } else {
                KD_TRACE(100, ("__kmp_dispatch_init: T#%d falling-through to kmp_sch_static_greedy\n",
                               gtid ) );
                schedule = kmp_sch_static_greedy;
                /* team->t.t_nproc == 1: fall-through to kmp_sch_static_greedy */
                pr->u.p.parm1 = tc;
            } // if
        } // case
        break;
    case kmp_sch_static_greedy:
        KD_TRACE(100,("__kmp_dispatch_init: T#%d kmp_sch_static_greedy case\n",gtid));
            pr->u.p.parm1 = ( team -> t.t_nproc > 1 ) ?
                ( tc + team->t.t_nproc - 1 ) / team->t.t_nproc :
                tc;
        break;
    case kmp_sch_static_chunked :
    case kmp_sch_dynamic_chunked :
        KD_TRACE(100,("__kmp_dispatch_init: T#%d kmp_sch_static_chunked/kmp_sch_dynamic_chunked cases\n", gtid));
        break;
    case kmp_sch_trapezoidal :
        {
            /* TSS: trapezoid self-scheduling, minimum chunk_size = parm1 */

            T parm1, parm2, parm3, parm4;
            KD_TRACE(100, ("__kmp_dispatch_init: T#%d kmp_sch_trapezoidal case\n", gtid ) );

            parm1 = chunk;

            /* F : size of the first cycle */
            parm2 = ( tc / (2 * team->t.t_nproc) );

            if ( parm2 < 1 ) {
                parm2 = 1;
            }

            /* L : size of the last cycle.  Make sure the last cycle
             *     is not larger than the first cycle.
             */
            if ( parm1 < 1 ) {
                parm1 = 1;
            } else if ( parm1 > parm2 ) {
                parm1 = parm2;
            }

            /* N : number of cycles */
            parm3 = ( parm2 + parm1 );
            parm3 = ( 2 * tc + parm3 - 1) / parm3;

            if ( parm3 < 2 ) {
                parm3 = 2;
            }

            /* sigma : decreasing incr of the trapezoid */
            parm4 = ( parm3 - 1 );
            parm4 = ( parm2 - parm1 ) / parm4;

            // pointless check, because parm4 >= 0 always
            //if ( parm4 < 0 ) {
            //    parm4 = 0;
            //}

            pr->u.p.parm1 = parm1;
            pr->u.p.parm2 = parm2;
            pr->u.p.parm3 = parm3;
            pr->u.p.parm4 = parm4;
        } // case
        break;

    default:
        {
            __kmp_msg(
                kmp_ms_fatal,                        // Severity
                KMP_MSG( UnknownSchedTypeDetected ), // Primary message
                KMP_HNT( GetNewerLibrary ),          // Hint
                __kmp_msg_null                       // Variadic argument list terminator
            );
        }
        break;
    } // switch
    pr->schedule = schedule;
    if ( active ) {
        /* The name of this buffer should be my_buffer_index when it's free to use it */

        KD_TRACE(100, ("__kmp_dispatch_init: T#%d before wait: my_buffer_index:%d sh->buffer_index:%d\n",
                        gtid, my_buffer_index, sh->buffer_index) );
        __kmp_wait_yield< kmp_uint32 >( & sh->buffer_index, my_buffer_index, __kmp_eq< kmp_uint32 >
                                        USE_ITT_BUILD_ARG( NULL )
                                        );
            // Note: KMP_WAIT_YIELD() cannot be used there: buffer index and my_buffer_index are
            // *always* 32-bit integers.
        KMP_MB();  /* is this necessary? */
        KD_TRACE(100, ("__kmp_dispatch_init: T#%d after wait: my_buffer_index:%d sh->buffer_index:%d\n",
                        gtid, my_buffer_index, sh->buffer_index) );

        th -> th.th_dispatch -> th_dispatch_pr_current = (dispatch_private_info_t*) pr;
        th -> th.th_dispatch -> th_dispatch_sh_current = (dispatch_shared_info_t*)  sh;
#if USE_ITT_BUILD
        if ( pr->ordered ) {
            __kmp_itt_ordered_init( gtid );
        }; // if
#endif /* USE_ITT_BUILD */
    }; // if
    #ifdef KMP_DEBUG
    {
        const char * buff;
        // create format specifiers before the debug output
        buff = __kmp_str_format(
            "__kmp_dispatch_init: T#%%d returning: schedule:%%d ordered:%%%s lb:%%%s ub:%%%s" \
            " st:%%%s tc:%%%s count:%%%s\n\tordered_lower:%%%s ordered_upper:%%%s" \
            " parm1:%%%s parm2:%%%s parm3:%%%s parm4:%%%s\n",
            traits_t< UT >::spec, traits_t< T >::spec, traits_t< T >::spec,
            traits_t< ST >::spec, traits_t< UT >::spec, traits_t< UT >::spec,
            traits_t< UT >::spec, traits_t< UT >::spec, traits_t< T >::spec,
            traits_t< T >::spec, traits_t< T >::spec, traits_t< T >::spec );
        KD_TRACE(10, ( buff,
            gtid, pr->schedule, pr->ordered, pr->u.p.lb, pr->u.p.ub,
            pr->u.p.st, pr->u.p.tc, pr->u.p.count,
            pr->u.p.ordered_lower, pr->u.p.ordered_upper, pr->u.p.parm1,
            pr->u.p.parm2, pr->u.p.parm3, pr->u.p.parm4 ) );
        __kmp_str_free( &buff );
    }
    #endif
    #if ( KMP_STATIC_STEAL_ENABLED )
    if ( ___kmp_size_type < 8 ) {
      // It cannot be guaranteed that after execution of a loop with some other schedule kind
      // all the parm3 variables will contain the same value.
      // Even if all parm3 will be the same, it still exists a bad case like using 0 and 1
      // rather than program life-time increment.
      // So the dedicated variable is required. The 'static_steal_counter' is used.
      if( schedule == kmp_sch_static_steal ) {
        // Other threads will inspect this variable when searching for a victim.
        // This is a flag showing that other threads may steal from this thread since then.
        volatile T * p = &pr->u.p.static_steal_counter;
        *p = *p + 1;
      }
    }
    #endif // ( KMP_STATIC_STEAL_ENABLED && USE_STEALING )
}

/*
 * For ordered loops, either __kmp_dispatch_finish() should be called after
 * every iteration, or __kmp_dispatch_finish_chunk() should be called after
 * every chunk of iterations.  If the ordered section(s) were not executed
 * for this iteration (or every iteration in this chunk), we need to set the
 * ordered iteration counters so that the next thread can proceed.
 */
template< typename UT >
static void
__kmp_dispatch_finish( int gtid, ident_t *loc )
{
    typedef typename traits_t< UT >::signed_t ST;
    kmp_info_t *th = __kmp_threads[ gtid ];

    KD_TRACE(100, ("__kmp_dispatch_finish: T#%d called\n", gtid ) );
    if ( ! th -> th.th_team -> t.t_serialized ) {

        dispatch_private_info_template< UT > * pr =
            reinterpret_cast< dispatch_private_info_template< UT >* >
            ( th->th.th_dispatch->th_dispatch_pr_current );
        dispatch_shared_info_template< UT > volatile * sh =
            reinterpret_cast< dispatch_shared_info_template< UT >volatile* >
            ( th->th.th_dispatch->th_dispatch_sh_current );
        KMP_DEBUG_ASSERT( pr );
        KMP_DEBUG_ASSERT( sh );
        KMP_DEBUG_ASSERT( th->th.th_dispatch ==
                 &th->th.th_team->t.t_dispatch[th->th.th_info.ds.ds_tid] );

        if ( pr->ordered_bumped ) {
            KD_TRACE(1000, ("__kmp_dispatch_finish: T#%d resetting ordered_bumped to zero\n",
                            gtid ) );
            pr->ordered_bumped = 0;
        } else {
            UT lower = pr->u.p.ordered_lower;

            #ifdef KMP_DEBUG
            {
                const char * buff;
                // create format specifiers before the debug output
                buff = __kmp_str_format(
                    "__kmp_dispatch_finish: T#%%d before wait: ordered_iteration:%%%s lower:%%%s\n",
                    traits_t< UT >::spec, traits_t< UT >::spec );
                KD_TRACE(1000, ( buff, gtid, sh->u.s.ordered_iteration, lower ) );
                __kmp_str_free( &buff );
            }
            #endif

            __kmp_wait_yield< UT >(&sh->u.s.ordered_iteration, lower, __kmp_ge< UT >
                                   USE_ITT_BUILD_ARG(NULL)
                                   );
            KMP_MB();  /* is this necessary? */
            #ifdef KMP_DEBUG
            {
                const char * buff;
                // create format specifiers before the debug output
                buff = __kmp_str_format(
                    "__kmp_dispatch_finish: T#%%d after wait: ordered_iteration:%%%s lower:%%%s\n",
                    traits_t< UT >::spec, traits_t< UT >::spec );
                KD_TRACE(1000, ( buff, gtid, sh->u.s.ordered_iteration, lower ) );
                __kmp_str_free( &buff );
            }
            #endif

            test_then_inc< ST >( (volatile ST *) & sh->u.s.ordered_iteration );
        } // if
    } // if
    KD_TRACE(100, ("__kmp_dispatch_finish: T#%d returned\n", gtid ) );
}

#ifdef KMP_GOMP_COMPAT

template< typename UT >
static void
__kmp_dispatch_finish_chunk( int gtid, ident_t *loc )
{
    typedef typename traits_t< UT >::signed_t ST;
    kmp_info_t *th = __kmp_threads[ gtid ];

    KD_TRACE(100, ("__kmp_dispatch_finish_chunk: T#%d called\n", gtid ) );
    if ( ! th -> th.th_team -> t.t_serialized ) {
//        int cid;
        dispatch_private_info_template< UT > * pr =
            reinterpret_cast< dispatch_private_info_template< UT >* >
            ( th->th.th_dispatch->th_dispatch_pr_current );
        dispatch_shared_info_template< UT > volatile * sh =
            reinterpret_cast< dispatch_shared_info_template< UT >volatile* >
            ( th->th.th_dispatch->th_dispatch_sh_current );
        KMP_DEBUG_ASSERT( pr );
        KMP_DEBUG_ASSERT( sh );
        KMP_DEBUG_ASSERT( th->th.th_dispatch ==
                 &th->th.th_team->t.t_dispatch[th->th.th_info.ds.ds_tid] );

//        for (cid = 0; cid < KMP_MAX_ORDERED; ++cid) {
            UT lower = pr->u.p.ordered_lower;
            UT upper = pr->u.p.ordered_upper;
            UT inc = upper - lower + 1;

            if ( pr->ordered_bumped == inc ) {
                KD_TRACE(1000, ("__kmp_dispatch_finish: T#%d resetting ordered_bumped to zero\n",
                  gtid ) );
                pr->ordered_bumped = 0;
            } else {
                inc -= pr->ordered_bumped;

                #ifdef KMP_DEBUG
                {
                    const char * buff;
                    // create format specifiers before the debug output
                    buff = __kmp_str_format(
                        "__kmp_dispatch_finish_chunk: T#%%d before wait: " \
                        "ordered_iteration:%%%s lower:%%%s upper:%%%s\n",
                        traits_t< UT >::spec, traits_t< UT >::spec, traits_t< UT >::spec );
                    KD_TRACE(1000, ( buff, gtid, sh->u.s.ordered_iteration, lower, upper ) );
                    __kmp_str_free( &buff );
                }
                #endif

                __kmp_wait_yield< UT >(&sh->u.s.ordered_iteration, lower, __kmp_ge< UT >
                                       USE_ITT_BUILD_ARG(NULL)
                                       );

                KMP_MB();  /* is this necessary? */
                KD_TRACE(1000, ("__kmp_dispatch_finish_chunk: T#%d resetting ordered_bumped to zero\n",
                  gtid ) );
                pr->ordered_bumped = 0;
//!!!!! TODO check if the inc should be unsigned, or signed???
                #ifdef KMP_DEBUG
                {
                    const char * buff;
                    // create format specifiers before the debug output
                    buff = __kmp_str_format(
                        "__kmp_dispatch_finish_chunk: T#%%d after wait: " \
                        "ordered_iteration:%%%s inc:%%%s lower:%%%s upper:%%%s\n",
                        traits_t< UT >::spec, traits_t< UT >::spec, traits_t< UT >::spec, traits_t< UT >::spec );
                    KD_TRACE(1000, ( buff, gtid, sh->u.s.ordered_iteration, inc, lower, upper ) );
                    __kmp_str_free( &buff );
                }
                #endif

                test_then_add< ST >( (volatile ST *) & sh->u.s.ordered_iteration, inc);
            }
//        }
    }
    KD_TRACE(100, ("__kmp_dispatch_finish_chunk: T#%d returned\n", gtid ) );
}

#endif /* KMP_GOMP_COMPAT */

template< typename T >
static int
__kmp_dispatch_next(
    ident_t *loc, int gtid, kmp_int32 *p_last, T *p_lb, T *p_ub, typename traits_t< T >::signed_t *p_st
) {

    typedef typename traits_t< T >::unsigned_t  UT;
    typedef typename traits_t< T >::signed_t    ST;
    typedef typename traits_t< T >::floating_t  DBL;
    static const int ___kmp_size_type = sizeof( UT );

    int                                   status;
    dispatch_private_info_template< T > * pr;
    kmp_info_t                          * th   = __kmp_threads[ gtid ];
    kmp_team_t                          * team = th -> th.th_team;

    #ifdef KMP_DEBUG
    {
        const char * buff;
        // create format specifiers before the debug output
        buff = __kmp_str_format(
            "__kmp_dispatch_next: T#%%d called p_lb:%%%s p_ub:%%%s p_st:%%%s p_last: %%p\n",
            traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec );
        KD_TRACE(1000, ( buff, gtid, *p_lb, *p_ub, p_st ? *p_st : 0, p_last ) );
        __kmp_str_free( &buff );
    }
    #endif

    if ( team -> t.t_serialized ) {
        /* NOTE: serialize this dispatch becase we are not at the active level */
        pr = reinterpret_cast< dispatch_private_info_template< T >* >
            ( th -> th.th_dispatch -> th_disp_buffer ); /* top of the stack */
        KMP_DEBUG_ASSERT( pr );

        if ( (status = (pr->u.p.tc != 0)) == 0 ) {
            *p_lb = 0;
            *p_ub = 0;
            if ( p_st != 0 ) {
                *p_st = 0;
            }
            if ( __kmp_env_consistency_check ) {
                if ( pr->pushed_ws != ct_none ) {
                    pr->pushed_ws = __kmp_pop_workshare( gtid, pr->pushed_ws, loc );
                }
            }
        } else if ( pr->nomerge ) {
            kmp_int32 last;
            T         start;
            UT        limit, trip, init;
            ST        incr;
            T         chunk = pr->u.p.parm1;

            KD_TRACE(100, ("__kmp_dispatch_next: T#%d kmp_sch_dynamic_chunked case\n", gtid ) );

            init = chunk * pr->u.p.count++;
            trip = pr->u.p.tc - 1;

            if ( (status = (init <= trip)) == 0 ) {
                *p_lb = 0;
                *p_ub = 0;
                if ( p_st != 0 ) *p_st = 0;
                if ( __kmp_env_consistency_check ) {
                    if ( pr->pushed_ws != ct_none ) {
                        pr->pushed_ws = __kmp_pop_workshare( gtid, pr->pushed_ws, loc );
                    }
                }
            } else {
                start = pr->u.p.lb;
                limit = chunk + init - 1;
                incr  = pr->u.p.st;

                if ( (last = (limit >= trip)) != 0 ) {
                    limit = trip;
                    #if KMP_OS_WINDOWS
                    pr->u.p.last_upper = pr->u.p.ub;
                    #endif /* KMP_OS_WINDOWS */
                }
                if ( p_last ) {
                    *p_last = last;
                }
                if ( p_st != 0 ) {
                    *p_st = incr;
                }
                if ( incr == 1 ) {
                    *p_lb = start + init;
                    *p_ub = start + limit;
                } else {
                    *p_lb = start + init * incr;
                    *p_ub = start + limit * incr;
                }

                if ( pr->ordered ) {
                    pr->u.p.ordered_lower = init;
                    pr->u.p.ordered_upper = limit;
                    #ifdef KMP_DEBUG
                    {
                        const char * buff;
                        // create format specifiers before the debug output
                        buff = __kmp_str_format(
                            "__kmp_dispatch_next: T#%%d ordered_lower:%%%s ordered_upper:%%%s\n",
                            traits_t< UT >::spec, traits_t< UT >::spec );
                        KD_TRACE(1000, ( buff, gtid, pr->u.p.ordered_lower, pr->u.p.ordered_upper ) );
                        __kmp_str_free( &buff );
                    }
                    #endif
                } // if
            } // if
        } else {
            pr->u.p.tc = 0;

            *p_lb = pr->u.p.lb;
            *p_ub = pr->u.p.ub;
            #if KMP_OS_WINDOWS
            pr->u.p.last_upper = *p_ub;
            #endif /* KMP_OS_WINDOWS */

            if ( p_st != 0 ) {
                *p_st = pr->u.p.st;
            }
            if ( p_last ) {
                *p_last = TRUE;
            }
        } // if
        #ifdef KMP_DEBUG
        {
            const char * buff;
            // create format specifiers before the debug output
            buff = __kmp_str_format(
                "__kmp_dispatch_next: T#%%d serialized case: p_lb:%%%s " \
                "p_ub:%%%s p_st:%%%s p_last:%%p  returning:%%d\n",
                traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec );
            KD_TRACE(10, ( buff, gtid, *p_lb, *p_ub, *p_st, p_last, status) );
            __kmp_str_free( &buff );
        }
        #endif
        return status;
    } else {
        kmp_int32 last = 0;
        dispatch_shared_info_template< UT > *sh;
        T         start;
        ST        incr;
        UT        limit, trip, init;

        KMP_DEBUG_ASSERT( th->th.th_dispatch ==
                &th->th.th_team->t.t_dispatch[th->th.th_info.ds.ds_tid] );

        pr = reinterpret_cast< dispatch_private_info_template< T >* >
            ( th->th.th_dispatch->th_dispatch_pr_current );
        KMP_DEBUG_ASSERT( pr );
        sh = reinterpret_cast< dispatch_shared_info_template< UT >* >
            ( th->th.th_dispatch->th_dispatch_sh_current );
        KMP_DEBUG_ASSERT( sh );

        if ( pr->u.p.tc == 0 ) {
            // zero trip count
            status = 0;
        } else {
            switch (pr->schedule) {
            #if ( KMP_STATIC_STEAL_ENABLED && KMP_ARCH_X86_64 )
            case kmp_sch_static_steal:
                {
                    T chunk = pr->u.p.parm1;

                    KD_TRACE(100, ("__kmp_dispatch_next: T#%d kmp_sch_static_steal case\n", gtid) );

                    trip = pr->u.p.tc - 1;

                    if ( ___kmp_size_type > 4 ) {
                        // Other threads do not look into the data of this thread,
                        //  so it's not necessary to make volatile casting.
                        init   = ( pr->u.p.count )++;
                        status = ( init < (UT)pr->u.p.ub );
                    } else {
                        typedef union {
                            struct {
                                UT count;
                                T  ub;
                            } p;
                            kmp_int64 b;
                        } union_i4;
                        // All operations on 'count' or 'ub' must be combined atomically together.
                        // stealing implemented only for 4-byte indexes
                        {
                            union_i4 vold, vnew;
                            vold.b = *( volatile kmp_int64 * )(&pr->u.p.count);
                            vnew = vold;
                            vnew.p.count++;
                            while( ! KMP_COMPARE_AND_STORE_ACQ64(
                                        ( volatile kmp_int64* )&pr->u.p.count,
                                        *VOLATILE_CAST(kmp_int64 *)&vold.b,
                                        *VOLATILE_CAST(kmp_int64 *)&vnew.b ) ) {
                                KMP_CPU_PAUSE();
                                vold.b = *( volatile kmp_int64 * )(&pr->u.p.count);
                                vnew = vold;
                                vnew.p.count++;
                            }
                            vnew = vold;
                            init   = vnew.p.count;
                            status = ( init < (UT)vnew.p.ub ) ;
                        }

                        if( !status ) {
                            kmp_info_t   **other_threads = team->t.t_threads;
                            int          while_limit = 10;
                            int          while_index = 0;

                            // TODO: algorithm of searching for a victim
                            // should be cleaned up and measured
                            while ( ( !status ) && ( while_limit != ++while_index ) ) {
                                union_i4  vold, vnew;
                                kmp_int32 remaining; // kmp_int32 because KMP_I4 only
                                T         victimIdx    = pr->u.p.parm4;
                                T         oldVictimIdx = victimIdx;
                                dispatch_private_info_template< T > * victim;

                                do {
                                    if( !victimIdx ) {
                                        victimIdx = team->t.t_nproc - 1;
                                    } else {
                                        --victimIdx;
                                    }
                                    victim = reinterpret_cast< dispatch_private_info_template< T >* >
                                        ( other_threads[victimIdx]->th.th_dispatch->th_dispatch_pr_current );
                                } while ( (victim == NULL || victim == pr) && oldVictimIdx != victimIdx );
                                // TODO: think about a proper place of this test
                                if ( ( !victim ) ||
                                   ( (*( volatile T * )&victim->u.p.static_steal_counter) !=
                                     (*( volatile T * )&pr->u.p.static_steal_counter) ) ) {
                                    // TODO: delay would be nice
                                    continue;
                                    // the victim is not ready yet to participate in stealing
                                    // because the victim is still in kmp_init_dispatch
                                }
                                if ( oldVictimIdx == victimIdx ) {
                                    break;
                                }
                                pr->u.p.parm4 = victimIdx;

                                while( 1 ) {
                                    vold.b = *( volatile kmp_int64 * )( &victim->u.p.count );
                                    vnew = vold;

                                    KMP_DEBUG_ASSERT( (vnew.p.ub - 1) * (UT)chunk <= trip );
                                    if ( vnew.p.count >= (UT)vnew.p.ub || (remaining = vnew.p.ub - vnew.p.count) < 4 ) {
                                        break;
                                    }
                                    vnew.p.ub -= (remaining >> 2);
                                    KMP_DEBUG_ASSERT((vnew.p.ub - 1) * (UT)chunk <= trip);
                                    #pragma warning( push )
                                    // disable warning on pointless comparison of unsigned with 0
                                    #pragma warning( disable: 186 )
                                        KMP_DEBUG_ASSERT(vnew.p.ub >= 0);
                                    #pragma warning( pop )
                                    // TODO: Should this be acquire or release?
                                    if ( KMP_COMPARE_AND_STORE_ACQ64(
                                            ( volatile kmp_int64 * )&victim->u.p.count,
                                            *VOLATILE_CAST(kmp_int64 *)&vold.b,
                                            *VOLATILE_CAST(kmp_int64 *)&vnew.b ) ) {
                                        status = 1;
                                        while_index = 0;
                                        // now update own count and ub
                                        #if KMP_ARCH_X86
                                        // stealing executed on non-KMP_ARCH_X86 only
                                            // Atomic 64-bit write on ia32 is
                                            // unavailable, so we do this in steps.
                                            //     This code is not tested.
                                            init = vold.p.count;
                                            pr->u.p.ub = 0;
                                            pr->u.p.count = init + 1;
                                            pr->u.p.ub = vnew.p.count;
                                        #else
                                            init = vnew.p.ub;
                                            vold.p.count = init + 1;
                                            // TODO: is it safe and enough?
                                            *( volatile kmp_int64 * )(&pr->u.p.count) = vold.b;
                                        #endif // KMP_ARCH_X86
                                        break;
                                    } // if
                                KMP_CPU_PAUSE();
                                } // while (1)
                            } // while
                        } // if
                    } // if
                    if ( !status ) {
                        *p_lb = 0;
                        *p_ub = 0;
                        if ( p_st != 0 ) *p_st = 0;
                    } else {
                        start = pr->u.p.parm2;
                        init *= chunk;
                        limit = chunk + init - 1;
                        incr  = pr->u.p.st;

                        KMP_DEBUG_ASSERT(init <= trip);
                        if ( (last = (limit >= trip)) != 0 )
                            limit = trip;
                        if ( p_last ) {
                            *p_last = last;
                        }
                        if ( p_st != 0 ) *p_st = incr;

                        if ( incr == 1 ) {
                            *p_lb = start + init;
                            *p_ub = start + limit;
                        } else {
                            *p_lb = start + init * incr;
                            *p_ub = start + limit * incr;
                        }

                        if ( pr->ordered ) {
                            pr->u.p.ordered_lower = init;
                            pr->u.p.ordered_upper = limit;
                            #ifdef KMP_DEBUG
                            {
                                const char * buff;
                                // create format specifiers before the debug output
                                buff = __kmp_str_format(
                                    "__kmp_dispatch_next: T#%%d ordered_lower:%%%s ordered_upper:%%%s\n",
                                    traits_t< UT >::spec, traits_t< UT >::spec );
                                KD_TRACE(1000, ( buff, gtid, pr->u.p.ordered_lower, pr->u.p.ordered_upper ) );
                                __kmp_str_free( &buff );
                            }
                            #endif
                        } // if
                    } // if
                    break;
                } // case
            #endif // ( KMP_STATIC_STEAL_ENABLED && KMP_ARCH_X86_64 )
            case kmp_sch_static_balanced:
                {
                    KD_TRACE(100, ("__kmp_dispatch_next: T#%d kmp_sch_static_balanced case\n", gtid) );
                    if ( (status = !pr->u.p.count) != 0 ) {  /* check if thread has any iteration to do */
                        pr->u.p.count = 1;
                        *p_lb = pr->u.p.lb;
                        *p_ub = pr->u.p.ub;
                        last = pr->u.p.parm1;
                        if ( p_last ) {
                            *p_last = last;
                        }
                        if ( p_st )
                            *p_st = pr->u.p.st;
                    } else {  /* no iterations to do */
                        pr->u.p.lb = pr->u.p.ub + pr->u.p.st;
                    }
                    if ( pr->ordered ) {
                        #ifdef KMP_DEBUG
                        {
                            const char * buff;
                            // create format specifiers before the debug output
                            buff = __kmp_str_format(
                                "__kmp_dispatch_next: T#%%d ordered_lower:%%%s ordered_upper:%%%s\n",
                                traits_t< UT >::spec, traits_t< UT >::spec );
                            KD_TRACE(1000, ( buff, gtid, pr->u.p.ordered_lower, pr->u.p.ordered_upper ) );
                            __kmp_str_free( &buff );
                        }
                        #endif
                    } // if
                } // case
                break;
            case kmp_sch_static_greedy:  /* original code for kmp_sch_static_greedy was merged here */
            case kmp_sch_static_chunked:
                {
                    T parm1;

                    KD_TRACE(100, ("__kmp_dispatch_next: T#%d kmp_sch_static_[affinity|chunked] case\n",
                                   gtid ) );
                    parm1 = pr->u.p.parm1;

                    trip  = pr->u.p.tc - 1;
                    init  = parm1 * (pr->u.p.count + __kmp_tid_from_gtid(gtid));

                    if ( (status = (init <= trip)) != 0 ) {
                        start = pr->u.p.lb;
                        incr  = pr->u.p.st;
                        limit = parm1 + init - 1;

                        if ( (last = (limit >= trip)) != 0 )
                            limit = trip;

                        if ( p_last ) {
                            *p_last = last;
                        }
                        if ( p_st != 0 ) *p_st = incr;

                        pr->u.p.count += team->t.t_nproc;

                        if ( incr == 1 ) {
                            *p_lb = start + init;
                            *p_ub = start + limit;
                        }
                        else {
                            *p_lb = start + init * incr;
                            *p_ub = start + limit * incr;
                        }

                        if ( pr->ordered ) {
                            pr->u.p.ordered_lower = init;
                            pr->u.p.ordered_upper = limit;
                            #ifdef KMP_DEBUG
                            {
                                const char * buff;
                                // create format specifiers before the debug output
                                buff = __kmp_str_format(
                                    "__kmp_dispatch_next: T#%%d ordered_lower:%%%s ordered_upper:%%%s\n",
                                    traits_t< UT >::spec, traits_t< UT >::spec );
                                KD_TRACE(1000, ( buff, gtid, pr->u.p.ordered_lower, pr->u.p.ordered_upper ) );
                                __kmp_str_free( &buff );
                            }
                            #endif
                        } // if
                    } // if
                } // case
                break;

            case kmp_sch_dynamic_chunked:
                {
                    T chunk = pr->u.p.parm1;

                    KD_TRACE(100, ("__kmp_dispatch_next: T#%d kmp_sch_dynamic_chunked case\n",
                                   gtid ) );

                    init = chunk * test_then_inc_acq< ST >((volatile ST *) & sh->u.s.iteration );
                    trip = pr->u.p.tc - 1;

                    if ( (status = (init <= trip)) == 0 ) {
                        *p_lb = 0;
                        *p_ub = 0;
                        if ( p_st != 0 ) *p_st = 0;
                    } else {
                        start = pr->u.p.lb;
                        limit = chunk + init - 1;
                        incr  = pr->u.p.st;

                        if ( (last = (limit >= trip)) != 0 )
                            limit = trip;
                        if ( p_last ) {
                            *p_last = last;
                        }
                        if ( p_st != 0 ) *p_st = incr;

                        if ( incr == 1 ) {
                            *p_lb = start + init;
                            *p_ub = start + limit;
                        } else {
                            *p_lb = start + init * incr;
                            *p_ub = start + limit * incr;
                        }

                        if ( pr->ordered ) {
                            pr->u.p.ordered_lower = init;
                            pr->u.p.ordered_upper = limit;
                            #ifdef KMP_DEBUG
                            {
                                const char * buff;
                                // create format specifiers before the debug output
                                buff = __kmp_str_format(
                                    "__kmp_dispatch_next: T#%%d ordered_lower:%%%s ordered_upper:%%%s\n",
                                    traits_t< UT >::spec, traits_t< UT >::spec );
                                KD_TRACE(1000, ( buff, gtid, pr->u.p.ordered_lower, pr->u.p.ordered_upper ) );
                                __kmp_str_free( &buff );
                            }
                            #endif
                        } // if
                    } // if
                } // case
                break;

            case kmp_sch_guided_iterative_chunked:
                {
                    T  chunkspec = pr->u.p.parm1;
                    KD_TRACE(100,
                        ("__kmp_dispatch_next: T#%d kmp_sch_guided_chunked iterative case\n",gtid));
                    trip  = pr->u.p.tc;
                    // Start atomic part of calculations
                    while(1) {
                        ST  remaining;             // signed, because can be < 0
                        init = sh->u.s.iteration;  // shared value
                        remaining = trip - init;
                        if ( remaining <= 0 ) {    // AC: need to compare with 0 first
                            // nothing to do, don't try atomic op
                            status = 0;
                            break;
                        }
                        if ( (T)remaining < pr->u.p.parm2 ) { // compare with K*nproc*(chunk+1), K=2 by default
                            // use dynamic-style shcedule
                            // atomically inrement iterations, get old value
                            init = test_then_add<ST>( (ST*)&sh->u.s.iteration, (ST)chunkspec );
                            remaining = trip - init;
                            if (remaining <= 0) {
                                status = 0;    // all iterations got by other threads
                            } else {
                                // got some iterations to work on
                                status = 1;
                                if ( (T)remaining > chunkspec ) {
                                    limit = init + chunkspec - 1;
                                } else {
                                    last = 1;   // the last chunk
                                    limit = init + remaining - 1;
                                } // if
                            } // if
                            break;
                        } // if
                        limit = init + (UT)( remaining * *(double*)&pr->u.p.parm3 ); // divide by K*nproc
                        if ( compare_and_swap<ST>( (ST*)&sh->u.s.iteration, (ST)init, (ST)limit ) ) {
                            // CAS was successful, chunk obtained
                            status = 1;
                            --limit;
                            break;
                        } // if
                    } // while
                    if ( status != 0 ) {
                        start = pr->u.p.lb;
                        incr = pr->u.p.st;
                        if ( p_st != NULL )
                            *p_st = incr;
                        if ( p_last != NULL )
                            *p_last = last;
                        *p_lb = start + init * incr;
                        *p_ub = start + limit * incr;
                        if ( pr->ordered ) {
                            pr->u.p.ordered_lower = init;
                            pr->u.p.ordered_upper = limit;
                            #ifdef KMP_DEBUG
                            {
                                const char * buff;
                                // create format specifiers before the debug output
                                buff = __kmp_str_format(
                                    "__kmp_dispatch_next: T#%%d ordered_lower:%%%s ordered_upper:%%%s\n",
                                    traits_t< UT >::spec, traits_t< UT >::spec );
                                KD_TRACE(1000, ( buff, gtid, pr->u.p.ordered_lower, pr->u.p.ordered_upper ) );
                                __kmp_str_free( &buff );
                            }
                            #endif
                        } // if
                    } else {
                        *p_lb = 0;
                        *p_ub = 0;
                        if ( p_st != NULL )
                            *p_st = 0;
                    } // if
                } // case
                break;

            case kmp_sch_guided_analytical_chunked:
                {
                    T   chunkspec = pr->u.p.parm1;
                    UT chunkIdx;
    #if KMP_OS_WINDOWS && KMP_ARCH_X86
                    /* for storing original FPCW value for Windows* OS on
		       IA-32 architecture 8-byte version */
                    unsigned int oldFpcw;
                    unsigned int fpcwSet = 0;
    #endif
                    KD_TRACE(100, ("__kmp_dispatch_next: T#%d kmp_sch_guided_chunked analytical case\n",
                                   gtid ) );

                    trip  = pr->u.p.tc;

                    KMP_DEBUG_ASSERT(team->t.t_nproc > 1);
                    KMP_DEBUG_ASSERT((2UL * chunkspec + 1) * (UT)team->t.t_nproc < trip);

                    while(1) { /* this while loop is a safeguard against unexpected zero chunk sizes */
                        chunkIdx = test_then_inc_acq< ST >((volatile ST *) & sh->u.s.iteration );
                        if ( chunkIdx >= (UT)pr->u.p.parm2 ) {
                            --trip;
                            /* use dynamic-style scheduling */
                            init = chunkIdx * chunkspec + pr->u.p.count;
                            /* need to verify init > 0 in case of overflow in the above calculation */
                            if ( (status = (init > 0 && init <= trip)) != 0 ) {
                                limit = init + chunkspec -1;

                                if ( (last = (limit >= trip)) != 0 )
                                    limit = trip;
                            }
                            break;
                        } else {
                            /* use exponential-style scheduling */
                            /* The following check is to workaround the lack of long double precision on Windows* OS.
                               This check works around the possible effect that init != 0 for chunkIdx == 0.
                             */
    #if KMP_OS_WINDOWS && KMP_ARCH_X86
                            /* If we haven't already done so, save original
			       FPCW and set precision to 64-bit, as Windows* OS
			       on IA-32 architecture defaults to 53-bit */
                            if ( !fpcwSet ) {
                                oldFpcw = _control87(0,0);
                                _control87(_PC_64,_MCW_PC);
                                fpcwSet = 0x30000;
                            }
    #endif
                            if ( chunkIdx ) {
                                init = __kmp_dispatch_guided_remaining< T >(
                                           trip, *( DBL * )&pr->u.p.parm3, chunkIdx );
                                KMP_DEBUG_ASSERT(init);
                                init = trip - init;
                            } else
                                init = 0;
                            limit = trip - __kmp_dispatch_guided_remaining< T >(
                                               trip, *( DBL * )&pr->u.p.parm3, chunkIdx + 1 );
                            KMP_ASSERT(init <= limit);
                            if ( init < limit ) {
                                KMP_DEBUG_ASSERT(limit <= trip);
                                --limit;
                                status = 1;
                                break;
                            } // if
                        } // if
                    } // while (1)
    #if KMP_OS_WINDOWS && KMP_ARCH_X86
                    /* restore FPCW if necessary
                       AC: check fpcwSet flag first because oldFpcw can be uninitialized here
                    */
                    if ( fpcwSet && ( oldFpcw & fpcwSet ) )
                        _control87(oldFpcw,_MCW_PC);
    #endif
                    if ( status != 0 ) {
                        start = pr->u.p.lb;
                        incr = pr->u.p.st;
                        if ( p_st != NULL )
                            *p_st = incr;
                        if ( p_last != NULL )
                            *p_last = last;
                        *p_lb = start + init * incr;
                        *p_ub = start + limit * incr;
                        if ( pr->ordered ) {
                            pr->u.p.ordered_lower = init;
                            pr->u.p.ordered_upper = limit;
                            #ifdef KMP_DEBUG
                            {
                                const char * buff;
                                // create format specifiers before the debug output
                                buff = __kmp_str_format(
                                    "__kmp_dispatch_next: T#%%d ordered_lower:%%%s ordered_upper:%%%s\n",
                                    traits_t< UT >::spec, traits_t< UT >::spec );
                                KD_TRACE(1000, ( buff, gtid, pr->u.p.ordered_lower, pr->u.p.ordered_upper ) );
                                __kmp_str_free( &buff );
                            }
                            #endif
                        }
                    } else {
                        *p_lb = 0;
                        *p_ub = 0;
                        if ( p_st != NULL )
                            *p_st = 0;
                    }
                } // case
                break;

            case kmp_sch_trapezoidal:
                {
                    UT   index;
                    T    parm2 = pr->u.p.parm2;
                    T    parm3 = pr->u.p.parm3;
                    T    parm4 = pr->u.p.parm4;
                    KD_TRACE(100, ("__kmp_dispatch_next: T#%d kmp_sch_trapezoidal case\n",
                                   gtid ) );

                    index = test_then_inc< ST >( (volatile ST *) & sh->u.s.iteration );

                    init = ( index * ( (2*parm2) - (index-1)*parm4 ) ) / 2;
                    trip = pr->u.p.tc - 1;

                    if ( (status = ((T)index < parm3 && init <= trip)) == 0 ) {
                        *p_lb = 0;
                        *p_ub = 0;
                        if ( p_st != 0 ) *p_st = 0;
                    } else {
                        start = pr->u.p.lb;
                        limit = ( (index+1) * ( 2*parm2 - index*parm4 ) ) / 2 - 1;
                        incr  = pr->u.p.st;

                        if ( (last = (limit >= trip)) != 0 )
                            limit = trip;

                        if ( p_last != 0 ) {
                            *p_last = last;
                        }
                        if ( p_st != 0 ) *p_st = incr;

                        if ( incr == 1 ) {
                            *p_lb = start + init;
                            *p_ub = start + limit;
                        } else {
                            *p_lb = start + init * incr;
                            *p_ub = start + limit * incr;
                        }

                        if ( pr->ordered ) {
                            pr->u.p.ordered_lower = init;
                            pr->u.p.ordered_upper = limit;
                            #ifdef KMP_DEBUG
                            {
                                const char * buff;
                                // create format specifiers before the debug output
                                buff = __kmp_str_format(
                                    "__kmp_dispatch_next: T#%%d ordered_lower:%%%s ordered_upper:%%%s\n",
                                    traits_t< UT >::spec, traits_t< UT >::spec );
                                KD_TRACE(1000, ( buff, gtid, pr->u.p.ordered_lower, pr->u.p.ordered_upper ) );
                                __kmp_str_free( &buff );
                            }
                            #endif
                        } // if
                    } // if
                } // case
                break;
            } // switch
        } // if tc == 0;

        if ( status == 0 ) {
            UT   num_done;

            num_done = test_then_inc< ST >( (volatile ST *) & sh->u.s.num_done );
            #ifdef KMP_DEBUG
            {
                const char * buff;
                // create format specifiers before the debug output
                buff = __kmp_str_format(
                    "__kmp_dispatch_next: T#%%d increment num_done:%%%s\n",
                    traits_t< UT >::spec );
                KD_TRACE(100, ( buff, gtid, sh->u.s.num_done ) );
                __kmp_str_free( &buff );
            }
            #endif

            if ( num_done == team->t.t_nproc-1 ) {
                /* NOTE: release this buffer to be reused */

                KMP_MB();       /* Flush all pending memory write invalidates.  */

                sh->u.s.num_done = 0;
                sh->u.s.iteration = 0;

                /* TODO replace with general release procedure? */
                if ( pr->ordered ) {
                    sh->u.s.ordered_iteration = 0;
                }

                KMP_MB();       /* Flush all pending memory write invalidates.  */

                sh -> buffer_index += KMP_MAX_DISP_BUF;
                KD_TRACE(100, ("__kmp_dispatch_next: T#%d change buffer_index:%d\n",
                                gtid, sh->buffer_index) );

                KMP_MB();       /* Flush all pending memory write invalidates.  */

            } // if
            if ( __kmp_env_consistency_check ) {
                if ( pr->pushed_ws != ct_none ) {
                    pr->pushed_ws = __kmp_pop_workshare( gtid, pr->pushed_ws, loc );
                }
            }

            th -> th.th_dispatch -> th_deo_fcn = NULL;
            th -> th.th_dispatch -> th_dxo_fcn = NULL;
            th -> th.th_dispatch -> th_dispatch_sh_current = NULL;
            th -> th.th_dispatch -> th_dispatch_pr_current = NULL;
        } // if (status == 0)
#if KMP_OS_WINDOWS
        else if ( last ) {
            pr->u.p.last_upper = pr->u.p.ub;
        }
#endif /* KMP_OS_WINDOWS */
    } // if

    #ifdef KMP_DEBUG
    {
        const char * buff;
        // create format specifiers before the debug output
        buff = __kmp_str_format(
            "__kmp_dispatch_next: T#%%d normal case: " \
            "p_lb:%%%s p_ub:%%%s p_st:%%%s p_last:%%p  returning:%%d\n",
            traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec );
        KD_TRACE(10, ( buff, gtid, *p_lb, *p_ub, p_st ? *p_st : 0, p_last, status ) );
        __kmp_str_free( &buff );
    }
    #endif
    return status;
}

//-----------------------------------------------------------------------------------------
// Dispatch routines
//    Transfer call to template< type T >
//    __kmp_dispatch_init( ident_t *loc, int gtid, enum sched_type schedule,
//                         T lb, T ub, ST st, ST chunk )
extern "C" {

/*!
@ingroup WORK_SHARING
@{
@param loc Source location
@param gtid Global thread id
@param schedule Schedule type
@param lb  Lower bound
@param ub  Upper bound
@param st  Step (or increment if you prefer)
@param chunk The chunk size to block with

This function prepares the runtime to start a dynamically scheduled for loop, saving the loop arguments.
These functions are all identical apart from the types of the arguments.
*/

void
__kmpc_dispatch_init_4( ident_t *loc, kmp_int32 gtid, enum sched_type schedule,
                        kmp_int32 lb, kmp_int32 ub, kmp_int32 st, kmp_int32 chunk )
{
    KMP_DEBUG_ASSERT( __kmp_init_serial );
    __kmp_dispatch_init< kmp_int32 >( loc, gtid, schedule, lb, ub, st, chunk, true );
}
/*!
See @ref __kmpc_dispatch_init_4
*/
void
__kmpc_dispatch_init_4u( ident_t *loc, kmp_int32 gtid, enum sched_type schedule,
                        kmp_uint32 lb, kmp_uint32 ub, kmp_int32 st, kmp_int32 chunk )
{
    KMP_DEBUG_ASSERT( __kmp_init_serial );
    __kmp_dispatch_init< kmp_uint32 >( loc, gtid, schedule, lb, ub, st, chunk, true );
}

/*!
See @ref __kmpc_dispatch_init_4
*/
void
__kmpc_dispatch_init_8( ident_t *loc, kmp_int32 gtid, enum sched_type schedule,
                        kmp_int64 lb, kmp_int64 ub,
                        kmp_int64 st, kmp_int64 chunk )
{
    KMP_DEBUG_ASSERT( __kmp_init_serial );
    __kmp_dispatch_init< kmp_int64 >( loc, gtid, schedule, lb, ub, st, chunk, true );
}

/*!
See @ref __kmpc_dispatch_init_4
*/
void
__kmpc_dispatch_init_8u( ident_t *loc, kmp_int32 gtid, enum sched_type schedule,
                         kmp_uint64 lb, kmp_uint64 ub,
                         kmp_int64 st, kmp_int64 chunk )
{
    KMP_DEBUG_ASSERT( __kmp_init_serial );
    __kmp_dispatch_init< kmp_uint64 >( loc, gtid, schedule, lb, ub, st, chunk, true );
}

/*!
@param loc Source code location
@param gtid Global thread id
@param p_last Pointer to a flag set to one if this is the last chunk or zero otherwise
@param p_lb   Pointer to the lower bound for the next chunk of work
@param p_ub   Pointer to the upper bound for the next chunk of work
@param p_st   Pointer to the stride for the next chunk of work
@return one if there is work to be done, zero otherwise

Get the next dynamically allocated chunk of work for this thread.
If there is no more work, then the lb,ub and stride need not be modified.
*/
int
__kmpc_dispatch_next_4( ident_t *loc, kmp_int32 gtid, kmp_int32 *p_last,
                        kmp_int32 *p_lb, kmp_int32 *p_ub, kmp_int32 *p_st )
{
    return __kmp_dispatch_next< kmp_int32 >( loc, gtid, p_last, p_lb, p_ub, p_st );
}

/*!
See @ref __kmpc_dispatch_next_4
*/
int
__kmpc_dispatch_next_4u( ident_t *loc, kmp_int32 gtid, kmp_int32 *p_last,
                        kmp_uint32 *p_lb, kmp_uint32 *p_ub, kmp_int32 *p_st )
{
    return __kmp_dispatch_next< kmp_uint32 >( loc, gtid, p_last, p_lb, p_ub, p_st );
}

/*!
See @ref __kmpc_dispatch_next_4
*/
int
__kmpc_dispatch_next_8( ident_t *loc, kmp_int32 gtid, kmp_int32 *p_last,
                        kmp_int64 *p_lb, kmp_int64 *p_ub, kmp_int64 *p_st )
{
    return __kmp_dispatch_next< kmp_int64 >( loc, gtid, p_last, p_lb, p_ub, p_st );
}

/*!
See @ref __kmpc_dispatch_next_4
*/
int
__kmpc_dispatch_next_8u( ident_t *loc, kmp_int32 gtid, kmp_int32 *p_last,
                        kmp_uint64 *p_lb, kmp_uint64 *p_ub, kmp_int64 *p_st )
{
    return __kmp_dispatch_next< kmp_uint64 >( loc, gtid, p_last, p_lb, p_ub, p_st );
}

/*!
@param loc Source code location
@param gtid Global thread id

Mark the end of a dynamic loop.
*/
void
__kmpc_dispatch_fini_4( ident_t *loc, kmp_int32 gtid )
{
    __kmp_dispatch_finish< kmp_uint32 >( gtid, loc );
}

/*!
See @ref __kmpc_dispatch_fini_4
*/
void
__kmpc_dispatch_fini_8( ident_t *loc, kmp_int32 gtid )
{
    __kmp_dispatch_finish< kmp_uint64 >( gtid, loc );
}

/*!
See @ref __kmpc_dispatch_fini_4
*/
void
__kmpc_dispatch_fini_4u( ident_t *loc, kmp_int32 gtid )
{
    __kmp_dispatch_finish< kmp_uint32 >( gtid, loc );
}

/*!
See @ref __kmpc_dispatch_fini_4
*/
void
__kmpc_dispatch_fini_8u( ident_t *loc, kmp_int32 gtid )
{
    __kmp_dispatch_finish< kmp_uint64 >( gtid, loc );
}
/*! @} */

//-----------------------------------------------------------------------------------------
//Non-template routines from kmp_dispatch.c used in other sources

kmp_uint32 __kmp_eq_4( kmp_uint32 value, kmp_uint32 checker) {
    return value == checker;
}

kmp_uint32 __kmp_neq_4( kmp_uint32 value, kmp_uint32 checker) {
    return value != checker;
}

kmp_uint32 __kmp_lt_4( kmp_uint32 value, kmp_uint32 checker) {
    return value < checker;
}

kmp_uint32 __kmp_ge_4( kmp_uint32 value, kmp_uint32 checker) {
    return value >= checker;
}

kmp_uint32 __kmp_le_4( kmp_uint32 value, kmp_uint32 checker) {
    return value <= checker;
}
kmp_uint32 __kmp_eq_8( kmp_uint64 value, kmp_uint64 checker) {
    return value == checker;
}

kmp_uint32 __kmp_neq_8( kmp_uint64 value, kmp_uint64 checker) {
    return value != checker;
}

kmp_uint32 __kmp_lt_8( kmp_uint64 value, kmp_uint64 checker) {
    return value < checker;
}

kmp_uint32 __kmp_ge_8( kmp_uint64 value, kmp_uint64 checker) {
    return value >= checker;
}

kmp_uint32 __kmp_le_8( kmp_uint64 value, kmp_uint64 checker) {
    return value <= checker;
}

kmp_uint32
__kmp_wait_yield_4(volatile kmp_uint32 * spinner,
                   kmp_uint32            checker,
                   kmp_uint32 (* pred)( kmp_uint32, kmp_uint32 )
                   , void        * obj    // Higher-level synchronization object, or NULL.
                   )
{
    // note: we may not belong to a team at this point
    register volatile kmp_uint32         * spin          = spinner;
    register          kmp_uint32           check         = checker;
    register          kmp_uint32   spins;
    register          kmp_uint32 (*f) ( kmp_uint32, kmp_uint32 ) = pred;
    register          kmp_uint32           r;

    KMP_FSYNC_SPIN_INIT( obj, (void*) spin );
    KMP_INIT_YIELD( spins );
    // main wait spin loop
    while(!f(r = TCR_4(*spin), check)) {
        KMP_FSYNC_SPIN_PREPARE( obj );
        /* GEH - remove this since it was accidentally introduced when kmp_wait was split.
           It causes problems with infinite recursion because of exit lock */
        /* if ( TCR_4(__kmp_global.g.g_done) && __kmp_global.g.g_abort)
            __kmp_abort_thread(); */

        __kmp_static_delay(TRUE);

        /* if we have waited a bit, or are oversubscribed, yield */
        /* pause is in the following code */
        KMP_YIELD( TCR_4(__kmp_nth) > __kmp_avail_proc );
        KMP_YIELD_SPIN( spins );
    }
    KMP_FSYNC_SPIN_ACQUIRED( obj );
    return r;
}

kmp_uint64
__kmp_wait_yield_8( volatile kmp_uint64 * spinner,
                    kmp_uint64            checker,
                    kmp_uint32 (* pred)( kmp_uint64, kmp_uint64 )
                    , void        * obj    // Higher-level synchronization object, or NULL.
                    )
{
    // note: we may not belong to a team at this point
    register volatile kmp_uint64         * spin          = spinner;
    register          kmp_uint64           check         = checker;
    register          kmp_uint32   spins;
    register          kmp_uint32 (*f) ( kmp_uint64, kmp_uint64 ) = pred;
    register          kmp_uint64           r;

    KMP_FSYNC_SPIN_INIT( obj, (void*) spin );
    KMP_INIT_YIELD( spins );
    // main wait spin loop
    while(!f(r = *spin, check))
    {
        KMP_FSYNC_SPIN_PREPARE( obj );
        /* GEH - remove this since it was accidentally introduced when kmp_wait was split.
           It causes problems with infinite recursion because of exit lock */
        /* if ( TCR_4(__kmp_global.g.g_done) && __kmp_global.g.g_abort)
            __kmp_abort_thread(); */

        __kmp_static_delay(TRUE);

        // if we are oversubscribed,
        // or have waited a bit (and KMP_LIBARRY=throughput, then yield
        // pause is in the following code
        KMP_YIELD( TCR_4(__kmp_nth) > __kmp_avail_proc );
        KMP_YIELD_SPIN( spins );
    }
    KMP_FSYNC_SPIN_ACQUIRED( obj );
    return r;
}

} // extern "C"

#ifdef KMP_GOMP_COMPAT

void
__kmp_aux_dispatch_init_4( ident_t *loc, kmp_int32 gtid, enum sched_type schedule,
                           kmp_int32 lb, kmp_int32 ub, kmp_int32 st,
                           kmp_int32 chunk, int push_ws )
{
    __kmp_dispatch_init< kmp_int32 >( loc, gtid, schedule, lb, ub, st, chunk,
                                      push_ws );
}

void
__kmp_aux_dispatch_init_4u( ident_t *loc, kmp_int32 gtid, enum sched_type schedule,
                            kmp_uint32 lb, kmp_uint32 ub, kmp_int32 st,
                            kmp_int32 chunk, int push_ws )
{
    __kmp_dispatch_init< kmp_uint32 >( loc, gtid, schedule, lb, ub, st, chunk,
                                       push_ws );
}

void
__kmp_aux_dispatch_init_8( ident_t *loc, kmp_int32 gtid, enum sched_type schedule,
                           kmp_int64 lb, kmp_int64 ub, kmp_int64 st,
                           kmp_int64 chunk, int push_ws )
{
    __kmp_dispatch_init< kmp_int64 >( loc, gtid, schedule, lb, ub, st, chunk,
                                      push_ws );
}

void
__kmp_aux_dispatch_init_8u( ident_t *loc, kmp_int32 gtid, enum sched_type schedule,
                            kmp_uint64 lb, kmp_uint64 ub, kmp_int64 st,
                            kmp_int64 chunk, int push_ws )
{
    __kmp_dispatch_init< kmp_uint64 >( loc, gtid, schedule, lb, ub, st, chunk,
                                       push_ws );
}

void
__kmp_aux_dispatch_fini_chunk_4( ident_t *loc, kmp_int32 gtid )
{
    __kmp_dispatch_finish_chunk< kmp_uint32 >( gtid, loc );
}

void
__kmp_aux_dispatch_fini_chunk_8( ident_t *loc, kmp_int32 gtid )
{
    __kmp_dispatch_finish_chunk< kmp_uint64 >( gtid, loc );
}

void
__kmp_aux_dispatch_fini_chunk_4u( ident_t *loc, kmp_int32 gtid )
{
    __kmp_dispatch_finish_chunk< kmp_uint32 >( gtid, loc );
}

void
__kmp_aux_dispatch_fini_chunk_8u( ident_t *loc, kmp_int32 gtid )
{
    __kmp_dispatch_finish_chunk< kmp_uint64 >( gtid, loc );
}

#endif /* KMP_GOMP_COMPAT */

/* ------------------------------------------------------------------------ */
/* ------------------------------------------------------------------------ */