path: root/contrib/libs/cxxsupp/openmp/kmp_taskq.c

/* 
 * kmp_taskq.c -- TASKQ support for OpenMP. 
 */ 
 
 
//===----------------------------------------------------------------------===// 
// 
//                     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. 
// 
//===----------------------------------------------------------------------===// 
 
 
#include "kmp.h" 
#include "kmp_i18n.h" 
#include "kmp_io.h" 
#include "kmp_error.h" 
 
#define MAX_MESSAGE 512 
 
/* ------------------------------------------------------------------------ */ 
/* ------------------------------------------------------------------------ */ 
 
/* 
 * Taskq routines and global variables 
 */ 
 
#define KMP_DEBUG_REF_CTS(x)    KF_TRACE(1, x); 
 
#define THREAD_ALLOC_FOR_TASKQ 
 
static int 
in_parallel_context( kmp_team_t *team ) 
{ 
    return ! team -> t.t_serialized; 
} 
 
static void 
__kmp_taskq_eo( int *gtid_ref, int *cid_ref, ident_t *loc_ref ) 
{ 
    int                gtid = *gtid_ref; 
    int                tid  = __kmp_tid_from_gtid( gtid ); 
    kmp_uint32         my_token; 
    kmpc_task_queue_t *taskq; 
    kmp_taskq_t       *tq   = & __kmp_threads[gtid] -> th.th_team -> t.t_taskq; 
 
    if ( __kmp_env_consistency_check ) 
#if KMP_USE_DYNAMIC_LOCK 
        __kmp_push_sync( gtid, ct_ordered_in_taskq, loc_ref, NULL, 0 ); 
#else 
        __kmp_push_sync( gtid, ct_ordered_in_taskq, loc_ref, NULL ); 
#endif 
 
    if ( ! __kmp_threads[ gtid ]-> th.th_team -> t.t_serialized ) { 
        KMP_MB();       /* Flush all pending memory write invalidates.  */ 
 
        /* GEH - need check here under stats to make sure   */ 
        /*       inside task (curr_thunk[*tid_ref] != NULL) */ 
 
        my_token =tq->tq_curr_thunk[ tid ]-> th_tasknum; 
 
        taskq = tq->tq_curr_thunk[ tid ]-> th.th_shareds -> sv_queue; 
 
        KMP_WAIT_YIELD(&taskq->tq_tasknum_serving, my_token, KMP_EQ, NULL); 
        KMP_MB(); 
    } 
} 
 
static void 
__kmp_taskq_xo( int *gtid_ref, int *cid_ref, ident_t *loc_ref ) 
{ 
    int           gtid = *gtid_ref; 
    int           tid  = __kmp_tid_from_gtid( gtid ); 
    kmp_uint32    my_token; 
    kmp_taskq_t  *tq   = & __kmp_threads[gtid] -> th.th_team -> t.t_taskq; 
 
    if ( __kmp_env_consistency_check ) 
        __kmp_pop_sync( gtid, ct_ordered_in_taskq, loc_ref ); 
 
    if ( ! __kmp_threads[ gtid ]-> th.th_team -> t.t_serialized ) { 
        KMP_MB();       /* Flush all pending memory write invalidates.  */ 
 
        /* GEH - need check here under stats to make sure */ 
        /*       inside task (curr_thunk[tid] != NULL)    */ 
 
        my_token = tq->tq_curr_thunk[ tid ]->th_tasknum; 
 
        KMP_MB();       /* Flush all pending memory write invalidates.  */ 
 
        tq->tq_curr_thunk[ tid ]-> th.th_shareds -> sv_queue -> tq_tasknum_serving = my_token + 1; 
 
        KMP_MB();       /* Flush all pending memory write invalidates.  */ 
    } 
} 
 
static void 
__kmp_taskq_check_ordered( kmp_int32 gtid, kmpc_thunk_t *thunk ) 
{ 
    kmp_uint32 my_token; 
    kmpc_task_queue_t *taskq; 
 
    /* assume we are always called from an active parallel context */ 
 
    KMP_MB();       /* Flush all pending memory write invalidates.  */ 
 
    my_token =  thunk -> th_tasknum; 
 
    taskq =  thunk -> th.th_shareds -> sv_queue; 
 
    if(taskq->tq_tasknum_serving <= my_token) { 
        KMP_WAIT_YIELD(&taskq->tq_tasknum_serving, my_token, KMP_GE, NULL); 
        KMP_MB(); 
        taskq->tq_tasknum_serving = my_token +1; 
        KMP_MB(); 
    } 
} 
 
#ifdef KMP_DEBUG 
 
static void 
__kmp_dump_TQF(kmp_int32 flags) 
{ 
    if (flags & TQF_IS_ORDERED) 
        __kmp_printf("ORDERED "); 
    if (flags & TQF_IS_LASTPRIVATE) 
        __kmp_printf("LAST_PRIV "); 
    if (flags & TQF_IS_NOWAIT) 
        __kmp_printf("NOWAIT "); 
    if (flags & TQF_HEURISTICS) 
        __kmp_printf("HEURIST "); 
    if (flags & TQF_INTERFACE_RESERVED1) 
        __kmp_printf("RESERV1 "); 
    if (flags & TQF_INTERFACE_RESERVED2) 
        __kmp_printf("RESERV2 "); 
    if (flags & TQF_INTERFACE_RESERVED3) 
        __kmp_printf("RESERV3 "); 
    if (flags & TQF_INTERFACE_RESERVED4) 
        __kmp_printf("RESERV4 "); 
    if (flags & TQF_IS_LAST_TASK) 
        __kmp_printf("LAST_TASK "); 
    if (flags & TQF_TASKQ_TASK) 
        __kmp_printf("TASKQ_TASK "); 
    if (flags & TQF_RELEASE_WORKERS) 
        __kmp_printf("RELEASE "); 
    if (flags & TQF_ALL_TASKS_QUEUED) 
        __kmp_printf("ALL_QUEUED "); 
    if (flags & TQF_PARALLEL_CONTEXT) 
        __kmp_printf("PARALLEL "); 
    if (flags & TQF_DEALLOCATED) 
        __kmp_printf("DEALLOC "); 
    if (!(flags & (TQF_INTERNAL_FLAGS|TQF_INTERFACE_FLAGS))) 
        __kmp_printf("(NONE)"); 
} 
 
static void 
__kmp_dump_thunk( kmp_taskq_t *tq, kmpc_thunk_t *thunk, kmp_int32 global_tid ) 
{ 
    int i; 
    int nproc = __kmp_threads[global_tid] -> th.th_team -> t.t_nproc; 
 
    __kmp_printf("\tThunk at %p on (%d):  ", thunk, global_tid); 
 
    if (thunk != NULL) { 
        for (i = 0; i < nproc; i++) { 
            if( tq->tq_curr_thunk[i] == thunk ) { 
                __kmp_printf("[%i] ", i); 
            } 
        } 
        __kmp_printf("th_shareds=%p, ", thunk->th.th_shareds); 
        __kmp_printf("th_task=%p, ", thunk->th_task); 
        __kmp_printf("th_encl_thunk=%p, ", thunk->th_encl_thunk); 
        __kmp_printf("th_status=%d, ", thunk->th_status); 
        __kmp_printf("th_tasknum=%u, ", thunk->th_tasknum); 
        __kmp_printf("th_flags="); __kmp_dump_TQF(thunk->th_flags); 
    } 
 
    __kmp_printf("\n"); 
} 
 
static void 
__kmp_dump_thunk_stack(kmpc_thunk_t *thunk, kmp_int32 thread_num) 
{ 
    kmpc_thunk_t *th; 
 
    __kmp_printf("    Thunk stack for T#%d:  ", thread_num); 
 
    for (th = thunk; th != NULL; th = th->th_encl_thunk ) 
        __kmp_printf("%p ", th); 
 
    __kmp_printf("\n"); 
} 
 
static void 
__kmp_dump_task_queue( kmp_taskq_t *tq, kmpc_task_queue_t *queue, kmp_int32 global_tid ) 
{ 
    int                  qs, count, i; 
    kmpc_thunk_t        *thunk; 
    kmpc_task_queue_t   *taskq; 
 
    __kmp_printf("Task Queue at %p on (%d):\n", queue, global_tid); 
 
    if (queue != NULL) { 
        int in_parallel = queue->tq_flags & TQF_PARALLEL_CONTEXT; 
 
    if ( __kmp_env_consistency_check ) { 
        __kmp_printf("    tq_loc             : "); 
    } 
        if (in_parallel) { 
 
            //if (queue->tq.tq_parent != 0) 
                //__kmp_acquire_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
 
            //__kmp_acquire_lock(& queue->tq_link_lck, global_tid); 
 
            KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                       /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
            __kmp_printf("    tq_parent          : %p\n", queue->tq.tq_parent); 
            __kmp_printf("    tq_first_child     : %p\n", queue->tq_first_child); 
            __kmp_printf("    tq_next_child      : %p\n", queue->tq_next_child); 
            __kmp_printf("    tq_prev_child      : %p\n", queue->tq_prev_child); 
            __kmp_printf("    tq_ref_count       : %d\n", queue->tq_ref_count); 
 
            //__kmp_release_lock(& queue->tq_link_lck, global_tid); 
 
            //if (queue->tq.tq_parent != 0) 
                //__kmp_release_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
 
            //__kmp_acquire_lock(& queue->tq_free_thunks_lck, global_tid); 
            //__kmp_acquire_lock(& queue->tq_queue_lck, global_tid); 
 
            KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                       /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
        } 
 
        __kmp_printf("    tq_shareds         : "); 
        for (i=0; i<((queue == tq->tq_root) ? queue->tq_nproc : 1); i++) 
            __kmp_printf("%p ", queue->tq_shareds[i].ai_data); 
        __kmp_printf("\n"); 
 
        if (in_parallel) { 
            __kmp_printf("    tq_tasknum_queuing : %u\n", queue->tq_tasknum_queuing); 
            __kmp_printf("    tq_tasknum_serving : %u\n", queue->tq_tasknum_serving); 
        } 
 
        __kmp_printf("    tq_queue           : %p\n", queue->tq_queue); 
        __kmp_printf("    tq_thunk_space     : %p\n", queue->tq_thunk_space); 
        __kmp_printf("    tq_taskq_slot      : %p\n", queue->tq_taskq_slot); 
 
        __kmp_printf("    tq_free_thunks     : "); 
        for (thunk = queue->tq_free_thunks; thunk != NULL; thunk = thunk->th.th_next_free ) 
            __kmp_printf("%p ", thunk); 
        __kmp_printf("\n"); 
 
        __kmp_printf("    tq_nslots          : %d\n", queue->tq_nslots); 
        __kmp_printf("    tq_head            : %d\n", queue->tq_head); 
        __kmp_printf("    tq_tail            : %d\n", queue->tq_tail); 
        __kmp_printf("    tq_nfull           : %d\n", queue->tq_nfull); 
        __kmp_printf("    tq_hiwat           : %d\n", queue->tq_hiwat); 
        __kmp_printf("    tq_flags           : "); __kmp_dump_TQF(queue->tq_flags); 
        __kmp_printf("\n"); 
 
        if (in_parallel) { 
            __kmp_printf("    tq_th_thunks       : "); 
            for (i = 0; i < queue->tq_nproc; i++) { 
                __kmp_printf("%d ", queue->tq_th_thunks[i].ai_data); 
            } 
            __kmp_printf("\n"); 
        } 
 
        __kmp_printf("\n"); 
        __kmp_printf("    Queue slots:\n"); 
 
 
        qs = queue->tq_tail; 
        for ( count = 0; count < queue->tq_nfull; ++count ) { 
            __kmp_printf("(%d)", qs); 
            __kmp_dump_thunk( tq, queue->tq_queue[qs].qs_thunk, global_tid ); 
            qs = (qs+1) % queue->tq_nslots; 
        } 
 
        __kmp_printf("\n"); 
 
        if (in_parallel) { 
            if (queue->tq_taskq_slot != NULL) { 
                __kmp_printf("    TaskQ slot:\n"); 
                __kmp_dump_thunk( tq, (kmpc_thunk_t *) queue->tq_taskq_slot, global_tid ); 
                __kmp_printf("\n"); 
            } 
            //__kmp_release_lock(& queue->tq_queue_lck, global_tid); 
            //__kmp_release_lock(& queue->tq_free_thunks_lck, global_tid); 
        } 
    } 
 
    __kmp_printf("    Taskq freelist: "); 
 
    //__kmp_acquire_lock( & tq->tq_freelist_lck, global_tid ); 
 
    KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
               /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
    for( taskq = tq->tq_freelist; taskq != NULL; taskq = taskq->tq.tq_next_free ) 
        __kmp_printf("%p ", taskq); 
 
    //__kmp_release_lock( & tq->tq_freelist_lck, global_tid ); 
 
    __kmp_printf("\n\n"); 
} 
 
static void 
__kmp_aux_dump_task_queue_tree( kmp_taskq_t *tq, kmpc_task_queue_t *curr_queue, kmp_int32 level, kmp_int32 global_tid ) 
{ 
    int i, count, qs; 
    int nproc = __kmp_threads[global_tid] -> th.th_team -> t.t_nproc; 
    kmpc_task_queue_t *queue = curr_queue; 
 
    if (curr_queue == NULL) 
        return; 
 
    __kmp_printf("    "); 
 
    for (i=0; i<level; i++) 
        __kmp_printf("  "); 
 
    __kmp_printf("%p", curr_queue); 
 
    for (i = 0; i < nproc; i++) { 
        if( tq->tq_curr_thunk[i] && tq->tq_curr_thunk[i]->th.th_shareds->sv_queue == curr_queue ) { 
            __kmp_printf(" [%i]", i); 
        } 
    } 
 
    __kmp_printf(":"); 
 
    //__kmp_acquire_lock(& curr_queue->tq_queue_lck, global_tid); 
 
    KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
               /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
    qs = curr_queue->tq_tail; 
 
    for ( count = 0; count < curr_queue->tq_nfull; ++count ) { 
        __kmp_printf("%p ", curr_queue->tq_queue[qs].qs_thunk); 
         qs = (qs+1) % curr_queue->tq_nslots; 
    } 
 
    //__kmp_release_lock(& curr_queue->tq_queue_lck, global_tid); 
 
    __kmp_printf("\n"); 
 
    if (curr_queue->tq_first_child) { 
        //__kmp_acquire_lock(& curr_queue->tq_link_lck, global_tid); 
 
        KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                   /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
        if (curr_queue->tq_first_child) { 
            for(queue = (kmpc_task_queue_t *)curr_queue->tq_first_child; 
                queue != NULL; 
                queue = queue->tq_next_child) { 
                __kmp_aux_dump_task_queue_tree( tq, queue, level+1, global_tid ); 
            } 
        } 
 
        //__kmp_release_lock(& curr_queue->tq_link_lck, global_tid); 
    } 
} 
 
static void 
__kmp_dump_task_queue_tree( kmp_taskq_t *tq, kmpc_task_queue_t *tqroot, kmp_int32 global_tid) 
{ 
    __kmp_printf("TaskQ Tree at root %p on (%d):\n", tqroot, global_tid); 
 
    __kmp_aux_dump_task_queue_tree( tq, tqroot, 0, global_tid ); 
 
    __kmp_printf("\n"); 
} 
#endif 
 
/* --------------------------------------------------------------------------- */ 
 
/* 
    New taskq storage routines that try to minimize overhead of mallocs but 
    still provide cache line alignment. 
*/ 
 
 
static void * 
__kmp_taskq_allocate(size_t size, kmp_int32 global_tid) 
{ 
    void *addr, *orig_addr; 
    size_t bytes; 
 
    KB_TRACE( 5, ("__kmp_taskq_allocate: called size=%d, gtid=%d\n", (int) size, global_tid ) ); 
 
    bytes = sizeof(void *) + CACHE_LINE + size; 
 
#ifdef THREAD_ALLOC_FOR_TASKQ 
    orig_addr = (void *) __kmp_thread_malloc( __kmp_thread_from_gtid(global_tid), bytes ); 
#else 
    KE_TRACE( 10, ("%%%%%% MALLOC( %d )\n", bytes ) ); 
    orig_addr = (void *) KMP_INTERNAL_MALLOC( bytes ); 
#endif /* THREAD_ALLOC_FOR_TASKQ */ 
 
    if (orig_addr == 0) 
        KMP_FATAL( OutOfHeapMemory ); 
 
    addr = orig_addr; 
 
    if (((kmp_uintptr_t) addr & ( CACHE_LINE - 1 )) != 0) { 
        KB_TRACE( 50, ("__kmp_taskq_allocate:  adjust for cache alignment\n" ) ); 
        addr = (void *) (((kmp_uintptr_t) addr + CACHE_LINE) & ~( CACHE_LINE - 1 )); 
    } 
 
    (* (void **) addr) = orig_addr; 
 
    KB_TRACE( 10, ("__kmp_taskq_allocate:  allocate: %p, use: %p - %p, size: %d, gtid: %d\n", 
             orig_addr, ((void **) addr) + 1, ((char *)(((void **) addr) + 1)) + size-1, 
             (int) size, global_tid )); 
 
    return ( ((void **) addr) + 1 ); 
} 
 
static void 
__kmpc_taskq_free(void *p, kmp_int32 global_tid) 
{ 
    KB_TRACE( 5, ("__kmpc_taskq_free: called addr=%p, gtid=%d\n", p, global_tid ) ); 
 
    KB_TRACE(10, ("__kmpc_taskq_free:  freeing: %p, gtid: %d\n", (*( ((void **) p)-1)), global_tid )); 
 
#ifdef THREAD_ALLOC_FOR_TASKQ 
    __kmp_thread_free( __kmp_thread_from_gtid(global_tid), *( ((void **) p)-1) ); 
#else 
    KMP_INTERNAL_FREE( *( ((void **) p)-1) ); 
#endif /* THREAD_ALLOC_FOR_TASKQ */ 
} 
 
/* --------------------------------------------------------------------------- */ 
 
/* 
 *      Keep freed kmpc_task_queue_t on an internal freelist and recycle since 
 *      they're of constant size. 
 */ 
 
static kmpc_task_queue_t * 
__kmp_alloc_taskq ( kmp_taskq_t *tq, int in_parallel, kmp_int32 nslots, kmp_int32 nthunks, 
                    kmp_int32 nshareds, kmp_int32 nproc, size_t sizeof_thunk, 
                    size_t sizeof_shareds, kmpc_thunk_t **new_taskq_thunk, kmp_int32 global_tid ) 
{ 
    kmp_int32                  i; 
    size_t                     bytes; 
    kmpc_task_queue_t          *new_queue; 
    kmpc_aligned_shared_vars_t *shared_var_array; 
    char                       *shared_var_storage; 
    char                       *pt; /* for doing byte-adjusted address computations */ 
 
    __kmp_acquire_lock( & tq->tq_freelist_lck, global_tid ); 
 
    KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
               /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
    if( tq->tq_freelist ) { 
        new_queue =  tq -> tq_freelist; 
        tq -> tq_freelist =  tq -> tq_freelist -> tq.tq_next_free; 
 
        KMP_DEBUG_ASSERT(new_queue->tq_flags & TQF_DEALLOCATED); 
 
        new_queue->tq_flags = 0; 
 
        __kmp_release_lock( & tq->tq_freelist_lck, global_tid ); 
    } 
    else { 
        __kmp_release_lock( & tq->tq_freelist_lck, global_tid ); 
 
        new_queue = (kmpc_task_queue_t *) __kmp_taskq_allocate (sizeof (kmpc_task_queue_t), global_tid); 
        new_queue->tq_flags = 0; 
    } 
 
    /*  space in the task queue for queue slots (allocate as one big chunk */ 
    /* of storage including new_taskq_task space)                          */ 
 
    sizeof_thunk += (CACHE_LINE - (sizeof_thunk % CACHE_LINE));         /* pad to cache line size */ 
    pt = (char *) __kmp_taskq_allocate (nthunks * sizeof_thunk, global_tid); 
    new_queue->tq_thunk_space = (kmpc_thunk_t *)pt; 
    *new_taskq_thunk = (kmpc_thunk_t *)(pt + (nthunks - 1) * sizeof_thunk); 
 
    /*  chain the allocated thunks into a freelist for this queue  */ 
 
    new_queue->tq_free_thunks = (kmpc_thunk_t *)pt; 
 
    for (i = 0; i < (nthunks - 2); i++) { 
        ((kmpc_thunk_t *)(pt+i*sizeof_thunk))->th.th_next_free = (kmpc_thunk_t *)(pt + (i+1)*sizeof_thunk); 
#ifdef KMP_DEBUG 
        ((kmpc_thunk_t *)(pt+i*sizeof_thunk))->th_flags = TQF_DEALLOCATED; 
#endif 
    } 
 
    ((kmpc_thunk_t *)(pt+(nthunks-2)*sizeof_thunk))->th.th_next_free = NULL; 
#ifdef KMP_DEBUG 
    ((kmpc_thunk_t *)(pt+(nthunks-2)*sizeof_thunk))->th_flags = TQF_DEALLOCATED; 
#endif 
 
    /* initialize the locks */ 
 
    if (in_parallel) { 
        __kmp_init_lock( & new_queue->tq_link_lck ); 
        __kmp_init_lock( & new_queue->tq_free_thunks_lck ); 
        __kmp_init_lock( & new_queue->tq_queue_lck ); 
    } 
 
    /* now allocate the slots */ 
 
    bytes = nslots * sizeof (kmpc_aligned_queue_slot_t); 
    new_queue->tq_queue = (kmpc_aligned_queue_slot_t *) __kmp_taskq_allocate( bytes, global_tid ); 
 
    /*  space for array of pointers to shared variable structures */ 
    sizeof_shareds += sizeof(kmpc_task_queue_t *); 
    sizeof_shareds += (CACHE_LINE - (sizeof_shareds % CACHE_LINE));     /* pad to cache line size */ 
 
    bytes = nshareds * sizeof (kmpc_aligned_shared_vars_t); 
    shared_var_array = (kmpc_aligned_shared_vars_t *) __kmp_taskq_allocate ( bytes, global_tid); 
 
    bytes = nshareds * sizeof_shareds; 
    shared_var_storage = (char *) __kmp_taskq_allocate ( bytes, global_tid); 
 
    for (i=0; i<nshareds; i++) { 
        shared_var_array[i].ai_data = (kmpc_shared_vars_t *) (shared_var_storage + i*sizeof_shareds); 
        shared_var_array[i].ai_data->sv_queue = new_queue; 
    } 
    new_queue->tq_shareds = shared_var_array; 
 
 
    /* array for number of outstanding thunks per thread */ 
 
    if (in_parallel) { 
        bytes = nproc * sizeof(kmpc_aligned_int32_t); 
        new_queue->tq_th_thunks = (kmpc_aligned_int32_t *) __kmp_taskq_allocate ( bytes, global_tid); 
        new_queue->tq_nproc     = nproc; 
 
        for (i=0; i<nproc; i++) 
            new_queue->tq_th_thunks[i].ai_data = 0; 
    } 
 
    return new_queue; 
} 
 
static void 
__kmp_free_taskq (kmp_taskq_t *tq, kmpc_task_queue_t *p, int in_parallel, kmp_int32 global_tid) 
{ 
    __kmpc_taskq_free(p->tq_thunk_space, global_tid); 
    __kmpc_taskq_free(p->tq_queue, global_tid); 
 
    /* free shared var structure storage */ 
    __kmpc_taskq_free((void *) p->tq_shareds[0].ai_data, global_tid); 
 
    /* free array of pointers to shared vars storage */ 
    __kmpc_taskq_free(p->tq_shareds, global_tid); 
 
#ifdef KMP_DEBUG 
    p->tq_first_child = NULL; 
    p->tq_next_child = NULL; 
    p->tq_prev_child = NULL; 
    p->tq_ref_count = -10; 
    p->tq_shareds = NULL; 
    p->tq_tasknum_queuing = 0; 
    p->tq_tasknum_serving = 0; 
    p->tq_queue = NULL; 
    p->tq_thunk_space = NULL; 
    p->tq_taskq_slot = NULL; 
    p->tq_free_thunks = NULL; 
    p->tq_nslots = 0; 
    p->tq_head = 0; 
    p->tq_tail = 0; 
    p->tq_nfull = 0; 
    p->tq_hiwat = 0; 
 
    if (in_parallel) { 
        int i; 
 
        for (i=0; i<p->tq_nproc; i++) 
            p->tq_th_thunks[i].ai_data = 0; 
    } 
    if ( __kmp_env_consistency_check ) 
        p->tq_loc = NULL; 
    KMP_DEBUG_ASSERT( p->tq_flags & TQF_DEALLOCATED ); 
    p->tq_flags = TQF_DEALLOCATED; 
#endif /* KMP_DEBUG */ 
 
    if (in_parallel)  { 
        __kmpc_taskq_free(p->tq_th_thunks, global_tid); 
        __kmp_destroy_lock(& p->tq_link_lck); 
        __kmp_destroy_lock(& p->tq_queue_lck); 
        __kmp_destroy_lock(& p->tq_free_thunks_lck); 
    } 
#ifdef KMP_DEBUG 
    p->tq_th_thunks = NULL; 
#endif /* KMP_DEBUG */ 
 
    KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
               /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
    __kmp_acquire_lock( & tq->tq_freelist_lck, global_tid ); 
    p->tq.tq_next_free = tq->tq_freelist; 
 
    tq->tq_freelist = p; 
    __kmp_release_lock( & tq->tq_freelist_lck, global_tid ); 
} 
 
/* 
 *    Once a group of thunks has been allocated for use in a particular queue, 
 *    these are managed via a per-queue freelist. 
 *    We force a check that there's always a thunk free if we need one. 
 */ 
 
static kmpc_thunk_t * 
__kmp_alloc_thunk (kmpc_task_queue_t *queue, int in_parallel, kmp_int32 global_tid) 
{ 
    kmpc_thunk_t *fl; 
 
    if (in_parallel) { 
        __kmp_acquire_lock(& queue->tq_free_thunks_lck, global_tid); 
 
        KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                   /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
    } 
 
    fl = queue->tq_free_thunks; 
 
    KMP_DEBUG_ASSERT (fl != NULL); 
 
    queue->tq_free_thunks = fl->th.th_next_free; 
    fl->th_flags = 0; 
 
    if (in_parallel) 
        __kmp_release_lock(& queue->tq_free_thunks_lck, global_tid); 
 
    return fl; 
} 
 
static void 
__kmp_free_thunk (kmpc_task_queue_t *queue, kmpc_thunk_t *p, int in_parallel, kmp_int32 global_tid) 
{ 
#ifdef KMP_DEBUG 
    p->th_task = 0; 
    p->th_encl_thunk = 0; 
    p->th_status = 0; 
    p->th_tasknum = 0; 
    /* Also could zero pointers to private vars */ 
#endif 
 
    if (in_parallel) { 
        __kmp_acquire_lock(& queue->tq_free_thunks_lck, global_tid); 
 
        KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                   /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
    } 
 
    p->th.th_next_free = queue->tq_free_thunks; 
    queue->tq_free_thunks = p; 
 
#ifdef KMP_DEBUG 
    p->th_flags = TQF_DEALLOCATED; 
#endif 
 
    if (in_parallel) 
        __kmp_release_lock(& queue->tq_free_thunks_lck, global_tid); 
} 
 
/* --------------------------------------------------------------------------- */ 
 
/*  returns nonzero if the queue just became full after the enqueue  */ 
 
static kmp_int32 
__kmp_enqueue_task ( kmp_taskq_t *tq, kmp_int32 global_tid, kmpc_task_queue_t *queue, kmpc_thunk_t *thunk, int in_parallel ) 
{ 
    kmp_int32    ret; 
 
    /*  dkp: can we get around the lock in the TQF_RELEASE_WORKERS case (only the master is executing then)  */ 
    if (in_parallel) { 
        __kmp_acquire_lock(& queue->tq_queue_lck, global_tid); 
 
        KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                   /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
    } 
 
    KMP_DEBUG_ASSERT (queue->tq_nfull < queue->tq_nslots);  /*  check queue not full  */ 
 
    queue->tq_queue[(queue->tq_head)++].qs_thunk = thunk; 
 
    if (queue->tq_head >= queue->tq_nslots) 
        queue->tq_head = 0; 
 
    (queue->tq_nfull)++; 
 
    KMP_MB();   /* to assure that nfull is seen to increase before TQF_ALL_TASKS_QUEUED is set */ 
 
    ret = (in_parallel) ? (queue->tq_nfull == queue->tq_nslots) : FALSE; 
 
    if (in_parallel) { 
        /* don't need to wait until workers are released before unlocking */ 
        __kmp_release_lock(& queue->tq_queue_lck, global_tid); 
 
        if( tq->tq_global_flags & TQF_RELEASE_WORKERS ) { 
            /* If just creating the root queue, the worker threads are waiting at */ 
            /* a join barrier until now, when there's something in the queue for  */ 
            /* them to do; release them now to do work.                           */ 
            /* This should only be done when this is the first task enqueued,     */ 
            /* so reset the flag here also.                                       */ 
 
            tq->tq_global_flags &= ~TQF_RELEASE_WORKERS;  /* no lock needed, workers are still in spin mode */ 
 
            KMP_MB();   /* avoid releasing barrier twice if taskq_task switches threads */ 
 
            __kmpc_end_barrier_master( NULL, global_tid); 
        } 
    } 
 
    return ret; 
} 
 
static kmpc_thunk_t * 
__kmp_dequeue_task (kmp_int32 global_tid, kmpc_task_queue_t *queue, int in_parallel) 
{ 
    kmpc_thunk_t *pt; 
    int           tid = __kmp_tid_from_gtid( global_tid ); 
 
    KMP_DEBUG_ASSERT (queue->tq_nfull > 0);  /*  check queue not empty  */ 
 
    if (queue->tq.tq_parent != NULL && in_parallel) { 
        int ct; 
        __kmp_acquire_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
        ct = ++(queue->tq_ref_count); 
        __kmp_release_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
        KMP_DEBUG_REF_CTS(("line %d gtid %d: Q %p inc %d\n", 
          __LINE__, global_tid, queue, ct)); 
    } 
 
    pt = queue->tq_queue[(queue->tq_tail)++].qs_thunk; 
 
    if (queue->tq_tail >= queue->tq_nslots) 
        queue->tq_tail = 0; 
 
    if (in_parallel) { 
        queue->tq_th_thunks[tid].ai_data++; 
 
        KMP_MB(); /* necessary so ai_data increment is propagated to other threads immediately (digital) */ 
 
        KF_TRACE(200, ("__kmp_dequeue_task: T#%d(:%d) now has %d outstanding thunks from queue %p\n", 
            global_tid, tid, queue->tq_th_thunks[tid].ai_data, queue)); 
    } 
 
    (queue->tq_nfull)--; 
 
#ifdef KMP_DEBUG 
    KMP_MB(); 
 
    /* necessary so (queue->tq_nfull > 0) above succeeds after tq_nfull is decremented */ 
 
    KMP_DEBUG_ASSERT(queue->tq_nfull >= 0); 
 
    if (in_parallel) { 
        KMP_DEBUG_ASSERT(queue->tq_th_thunks[tid].ai_data <= __KMP_TASKQ_THUNKS_PER_TH); 
    } 
#endif 
 
    return pt; 
} 
 
/* 
 * Find the next (non-null) task to dequeue and return it. 
 * This is never called unless in_parallel=TRUE 
 * 
 * Here are the rules for deciding which queue to take the task from: 
 * 1.  Walk up the task queue tree from the current queue's parent and look 
 *      on the way up (for loop, below). 
 * 2.  Do a depth-first search back down the tree from the root and 
 *      look (find_task_in_descendant_queue()). 
 * 
 * Here are the rules for deciding which task to take from a queue 
 * (__kmp_find_task_in_queue ()): 
 * 1.  Never take the last task from a queue if TQF_IS_LASTPRIVATE; this task 
 *     must be staged to make sure we execute the last one with 
 *     TQF_IS_LAST_TASK at the end of task queue execution. 
 * 2.  If the queue length is below some high water mark and the taskq task 
 *     is enqueued, prefer running the taskq task. 
 * 3.  Otherwise, take a (normal) task from the queue. 
 * 
 * If we do all this and return pt == NULL at the bottom of this routine, 
 * this means there are no more tasks to execute (except possibly for 
 * TQF_IS_LASTPRIVATE). 
 */ 
 
static kmpc_thunk_t * 
__kmp_find_task_in_queue (kmp_int32 global_tid, kmpc_task_queue_t *queue) 
{ 
    kmpc_thunk_t *pt  = NULL; 
    int           tid = __kmp_tid_from_gtid( global_tid ); 
 
    /* To prevent deadlock from tq_queue_lck if queue already deallocated */ 
    if ( !(queue->tq_flags & TQF_DEALLOCATED) ) { 
 
        __kmp_acquire_lock(& queue->tq_queue_lck, global_tid); 
 
        /* Check again to avoid race in __kmpc_end_taskq() */ 
        if ( !(queue->tq_flags & TQF_DEALLOCATED) ) { 
 
            KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                       /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
            if ((queue->tq_taskq_slot != NULL) && (queue->tq_nfull <= queue->tq_hiwat)) { 
                /* if there's enough room in the queue and the dispatcher */ 
                /* (taskq task) is available, schedule more tasks         */ 
                pt = (kmpc_thunk_t *) queue->tq_taskq_slot; 
                queue->tq_taskq_slot = NULL; 
            } 
            else if (queue->tq_nfull == 0 || 
                     queue->tq_th_thunks[tid].ai_data >= __KMP_TASKQ_THUNKS_PER_TH) { 
                /* do nothing if no thunks available or this thread can't */ 
                /* run any because it already is executing too many       */ 
 
                pt = NULL; 
            } 
            else if (queue->tq_nfull > 1) { 
                /*  always safe to schedule a task even if TQF_IS_LASTPRIVATE  */ 
 
                pt = __kmp_dequeue_task (global_tid, queue, TRUE); 
            } 
            else if (!(queue->tq_flags & TQF_IS_LASTPRIVATE)) { 
                /*  one thing in queue, always safe to schedule if !TQF_IS_LASTPRIVATE  */ 
 
                pt = __kmp_dequeue_task (global_tid, queue, TRUE); 
            } 
            else if (queue->tq_flags & TQF_IS_LAST_TASK) { 
                /* TQF_IS_LASTPRIVATE, one thing in queue, kmpc_end_taskq_task()   */ 
                /* has been run so this is last task, run with TQF_IS_LAST_TASK so */ 
                /* instrumentation does copy-out.                                  */ 
 
                pt = __kmp_dequeue_task (global_tid, queue, TRUE); 
                pt->th_flags |= TQF_IS_LAST_TASK;  /* don't need test_then_or since already locked */ 
            } 
        } 
 
        /* GEH - What happens here if is lastprivate, but not last task? */ 
        __kmp_release_lock(& queue->tq_queue_lck, global_tid); 
    } 
 
    return pt; 
} 
 
/* 
 * Walk a tree of queues starting at queue's first child 
 * and return a non-NULL thunk if one can be scheduled. 
 * Must only be called when in_parallel=TRUE 
 */ 
 
static kmpc_thunk_t * 
__kmp_find_task_in_descendant_queue (kmp_int32 global_tid, kmpc_task_queue_t *curr_queue) 
{ 
    kmpc_thunk_t *pt = NULL; 
    kmpc_task_queue_t *queue = curr_queue; 
 
    if (curr_queue->tq_first_child != NULL) { 
        __kmp_acquire_lock(& curr_queue->tq_link_lck, global_tid); 
 
        KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                   /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
        queue = (kmpc_task_queue_t *) curr_queue->tq_first_child; 
        if (queue == NULL) { 
            __kmp_release_lock(& curr_queue->tq_link_lck, global_tid); 
            return NULL; 
        } 
 
        while (queue != NULL)  { 
            int ct; 
            kmpc_task_queue_t *next; 
 
            ct= ++(queue->tq_ref_count); 
            __kmp_release_lock(& curr_queue->tq_link_lck, global_tid); 
            KMP_DEBUG_REF_CTS(("line %d gtid %d: Q %p inc %d\n", 
              __LINE__, global_tid, queue, ct)); 
 
            pt = __kmp_find_task_in_queue (global_tid, queue); 
 
            if (pt != NULL) { 
                int ct; 
 
                __kmp_acquire_lock(& curr_queue->tq_link_lck, global_tid); 
 
                KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                           /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
                ct = --(queue->tq_ref_count); 
                KMP_DEBUG_REF_CTS(("line %d gtid %d: Q %p dec %d\n", 
                  __LINE__, global_tid, queue, ct)); 
                KMP_DEBUG_ASSERT( queue->tq_ref_count >= 0 ); 
 
                __kmp_release_lock(& curr_queue->tq_link_lck, global_tid); 
 
                return pt; 
            } 
 
            /* although reference count stays active during descendant walk, shouldn't matter  */ 
            /* since if children still exist, reference counts aren't being monitored anyway   */ 
 
            pt = __kmp_find_task_in_descendant_queue (global_tid, queue); 
 
            if (pt != NULL) { 
                int ct; 
 
                __kmp_acquire_lock(& curr_queue->tq_link_lck, global_tid); 
 
                KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                           /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
                ct = --(queue->tq_ref_count); 
                KMP_DEBUG_REF_CTS(("line %d gtid %d: Q %p dec %d\n", 
                  __LINE__, global_tid, queue, ct)); 
                KMP_DEBUG_ASSERT( ct >= 0 ); 
 
                __kmp_release_lock(& curr_queue->tq_link_lck, global_tid); 
 
                return pt; 
            } 
 
            __kmp_acquire_lock(& curr_queue->tq_link_lck, global_tid); 
 
            KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                       /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
            next = queue->tq_next_child; 
 
            ct = --(queue->tq_ref_count); 
            KMP_DEBUG_REF_CTS(("line %d gtid %d: Q %p dec %d\n", 
              __LINE__, global_tid, queue, ct)); 
            KMP_DEBUG_ASSERT( ct >= 0 ); 
 
            queue = next; 
        } 
 
        __kmp_release_lock(& curr_queue->tq_link_lck, global_tid); 
    } 
 
    return pt; 
} 
 
/* 
 * Walk up the taskq tree looking for a task to execute. 
 * If we get to the root, search the tree for a descendent queue task. 
 * Must only be called when in_parallel=TRUE 
 */ 
 
static kmpc_thunk_t * 
__kmp_find_task_in_ancestor_queue (kmp_taskq_t *tq, kmp_int32 global_tid, kmpc_task_queue_t *curr_queue) 
{ 
    kmpc_task_queue_t *queue; 
    kmpc_thunk_t      *pt; 
 
    pt = NULL; 
 
    if (curr_queue->tq.tq_parent != NULL) { 
        queue = curr_queue->tq.tq_parent; 
 
        while (queue != NULL) { 
            if (queue->tq.tq_parent != NULL) { 
                int ct; 
                __kmp_acquire_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
 
                KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                           /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
                ct = ++(queue->tq_ref_count); 
                __kmp_release_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
                KMP_DEBUG_REF_CTS(("line %d gtid %d: Q %p inc %d\n", 
                  __LINE__, global_tid, queue, ct)); 
            } 
 
            pt = __kmp_find_task_in_queue (global_tid, queue); 
            if (pt != NULL) { 
                if (queue->tq.tq_parent != NULL) { 
                    int ct; 
                    __kmp_acquire_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
 
                    KMP_MB();  /* make sure data structures are in consistent state before querying them   */ 
                               /* Seems to work without this call for digital/alpha, needed for IBM/RS6000 */ 
 
                    ct = --(queue->tq_ref_count); 
                    KMP_DEBUG_REF_CTS(("line %d gtid %d: Q %p dec %d\n", 
                      __LINE__, global_tid, queue, ct)); 
                    KMP_DEBUG_ASSERT( ct >= 0 ); 
 
                    __kmp_release_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
                } 
 
                return pt; 
            } 
 
            if (queue->tq.tq_parent != NULL) { 
                int ct; 
                __kmp_acquire_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
 
                KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                           /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
                ct = --(queue->tq_ref_count); 
                KMP_DEBUG_REF_CTS(("line %d gtid %d: Q %p dec %d\n", 
                  __LINE__, global_tid, queue, ct)); 
                KMP_DEBUG_ASSERT( ct >= 0 ); 
            } 
            queue = queue->tq.tq_parent; 
 
            if (queue != NULL) 
                __kmp_release_lock(& queue->tq_link_lck, global_tid); 
        } 
 
    } 
 
    pt = __kmp_find_task_in_descendant_queue( global_tid, tq->tq_root ); 
 
    return pt; 
} 
 
static int 
__kmp_taskq_tasks_finished (kmpc_task_queue_t *queue) 
{ 
    int i; 
 
    /* KMP_MB(); *//* is this really necessary? */ 
 
    for (i=0; i<queue->tq_nproc; i++) { 
        if (queue->tq_th_thunks[i].ai_data != 0) 
            return FALSE; 
    } 
 
    return TRUE; 
} 
 
static int 
__kmp_taskq_has_any_children (kmpc_task_queue_t *queue) 
{ 
    return (queue->tq_first_child != NULL); 
} 
 
static void 
__kmp_remove_queue_from_tree( kmp_taskq_t *tq, kmp_int32 global_tid, kmpc_task_queue_t *queue, int in_parallel ) 
{ 
#ifdef KMP_DEBUG 
    kmp_int32     i; 
    kmpc_thunk_t *thunk; 
#endif 
 
    KF_TRACE(50, ("Before Deletion of TaskQ at %p on (%d):\n", queue, global_tid)); 
    KF_DUMP(50, __kmp_dump_task_queue( tq, queue, global_tid )); 
 
    /*  sub-queue in a recursion, not the root task queue  */ 
    KMP_DEBUG_ASSERT (queue->tq.tq_parent != NULL); 
 
    if (in_parallel) { 
        __kmp_acquire_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
 
        KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                   /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
    } 
 
    KMP_DEBUG_ASSERT (queue->tq_first_child == NULL); 
 
    /*  unlink queue from its siblings if any at this level  */ 
    if (queue->tq_prev_child != NULL) 
        queue->tq_prev_child->tq_next_child = queue->tq_next_child; 
    if (queue->tq_next_child != NULL) 
        queue->tq_next_child->tq_prev_child = queue->tq_prev_child; 
    if (queue->tq.tq_parent->tq_first_child == queue) 
        queue->tq.tq_parent->tq_first_child = queue->tq_next_child; 
 
    queue->tq_prev_child = NULL; 
    queue->tq_next_child = NULL; 
 
    if (in_parallel) { 
        KMP_DEBUG_REF_CTS(("line %d gtid %d: Q %p waiting for ref_count of %d to reach 1\n", 
          __LINE__, global_tid, queue, queue->tq_ref_count)); 
 
        /* wait until all other threads have stopped accessing this queue */ 
        while (queue->tq_ref_count > 1) { 
            __kmp_release_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
 
            KMP_WAIT_YIELD((volatile kmp_uint32*)&queue->tq_ref_count, 1, KMP_LE, NULL); 
 
            __kmp_acquire_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
 
            KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                       /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
        } 
 
        __kmp_release_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
    } 
 
    KMP_DEBUG_REF_CTS(("line %d gtid %d: Q %p freeing queue\n", 
      __LINE__, global_tid, queue)); 
 
#ifdef KMP_DEBUG 
    KMP_DEBUG_ASSERT(queue->tq_flags & TQF_ALL_TASKS_QUEUED); 
    KMP_DEBUG_ASSERT(queue->tq_nfull == 0); 
 
    for (i=0; i<queue->tq_nproc; i++) { 
        KMP_DEBUG_ASSERT(queue->tq_th_thunks[i].ai_data == 0); 
    } 
 
    i = 0; 
    for (thunk=queue->tq_free_thunks; thunk != NULL; thunk=thunk->th.th_next_free) 
        ++i; 
 
    KMP_ASSERT (i == queue->tq_nslots + (queue->tq_nproc * __KMP_TASKQ_THUNKS_PER_TH)); 
#endif 
 
    /*  release storage for queue entry  */ 
    __kmp_free_taskq ( tq, queue, TRUE, global_tid ); 
 
    KF_TRACE(50, ("After Deletion of TaskQ at %p on (%d):\n", queue, global_tid)); 
    KF_DUMP(50, __kmp_dump_task_queue_tree( tq, tq->tq_root, global_tid )); 
} 
 
/* 
 * Starting from indicated queue, proceed downward through tree and 
 * remove all taskqs which are finished, but only go down to taskqs 
 * which have the "nowait" clause present.  Assume this is only called 
 * when in_parallel=TRUE. 
 */ 
 
static void 
__kmp_find_and_remove_finished_child_taskq( kmp_taskq_t *tq, kmp_int32 global_tid, kmpc_task_queue_t *curr_queue ) 
{ 
    kmpc_task_queue_t *queue = curr_queue; 
 
    if (curr_queue->tq_first_child != NULL) { 
        __kmp_acquire_lock(& curr_queue->tq_link_lck, global_tid); 
 
        KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                   /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
        queue = (kmpc_task_queue_t *) curr_queue->tq_first_child; 
        if (queue != NULL) { 
            __kmp_release_lock(& curr_queue->tq_link_lck, global_tid); 
            return; 
        } 
 
        while (queue != NULL)  { 
            kmpc_task_queue_t *next; 
            int ct = ++(queue->tq_ref_count); 
            KMP_DEBUG_REF_CTS(("line %d gtid %d: Q %p inc %d\n", 
              __LINE__, global_tid, queue, ct)); 
 
 
            /* although reference count stays active during descendant walk, */ 
            /* shouldn't matter since if children still exist, reference     */ 
            /* counts aren't being monitored anyway                          */ 
 
            if (queue->tq_flags & TQF_IS_NOWAIT) { 
                __kmp_find_and_remove_finished_child_taskq ( tq, global_tid, queue ); 
 
                if ((queue->tq_flags & TQF_ALL_TASKS_QUEUED) && (queue->tq_nfull == 0) && 
                    __kmp_taskq_tasks_finished(queue) && ! __kmp_taskq_has_any_children(queue)) { 
 
                    /* 
                     Only remove this if we have not already marked it for deallocation. 
                     This should prevent multiple threads from trying to free this. 
                     */ 
 
                    if ( __kmp_test_lock(& queue->tq_queue_lck, global_tid) ) { 
                        if ( !(queue->tq_flags & TQF_DEALLOCATED) ) { 
                            queue->tq_flags |= TQF_DEALLOCATED; 
                            __kmp_release_lock(& queue->tq_queue_lck, global_tid); 
 
                            __kmp_remove_queue_from_tree( tq, global_tid, queue, TRUE ); 
 
                            /* Can't do any more here since can't be sure where sibling queue is so just exit this level */ 
                            return; 
                        } 
                        else { 
                            __kmp_release_lock(& queue->tq_queue_lck, global_tid); 
                        } 
                    } 
                    /* otherwise, just fall through and decrement reference count */ 
                } 
            } 
 
            __kmp_acquire_lock(& curr_queue->tq_link_lck, global_tid); 
 
            KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                       /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
            next = queue->tq_next_child; 
 
            ct = --(queue->tq_ref_count); 
            KMP_DEBUG_REF_CTS(("line %d gtid %d: Q %p dec %d\n", 
              __LINE__, global_tid, queue, ct)); 
            KMP_DEBUG_ASSERT( ct >= 0 ); 
 
            queue = next; 
        } 
 
        __kmp_release_lock(& curr_queue->tq_link_lck, global_tid); 
    } 
} 
 
/* 
 * Starting from indicated queue, proceed downward through tree and 
 * remove all taskq's assuming all are finished and 
 * assuming NO other threads are executing at this point. 
 */ 
 
static void 
__kmp_remove_all_child_taskq( kmp_taskq_t *tq, kmp_int32 global_tid, kmpc_task_queue_t *queue ) 
{ 
    kmpc_task_queue_t *next_child; 
 
    queue = (kmpc_task_queue_t *) queue->tq_first_child; 
 
    while (queue != NULL)  { 
        __kmp_remove_all_child_taskq ( tq, global_tid, queue ); 
 
        next_child = queue->tq_next_child; 
        queue->tq_flags |= TQF_DEALLOCATED; 
        __kmp_remove_queue_from_tree ( tq, global_tid, queue, FALSE ); 
        queue = next_child; 
    } 
} 
 
static void 
__kmp_execute_task_from_queue( kmp_taskq_t *tq, ident_t *loc, kmp_int32 global_tid, kmpc_thunk_t *thunk, int in_parallel ) 
{ 
    kmpc_task_queue_t *queue = thunk->th.th_shareds->sv_queue; 
    kmp_int32          tid   = __kmp_tid_from_gtid( global_tid ); 
 
    KF_TRACE(100, ("After dequeueing this Task on (%d):\n", global_tid)); 
    KF_DUMP(100, __kmp_dump_thunk( tq, thunk, global_tid )); 
    KF_TRACE(100, ("Task Queue: %p looks like this (%d):\n", queue, global_tid)); 
    KF_DUMP(100, __kmp_dump_task_queue( tq, queue, global_tid )); 
 
    /* 
     * For the taskq task, the curr_thunk pushes and pop pairs are set up as follows: 
     * 
     * happens exactly once: 
     * 1) __kmpc_taskq             : push (if returning thunk only) 
     * 4) __kmpc_end_taskq_task    : pop 
     * 
     * optionally happens *each* time taskq task is dequeued/enqueued: 
     * 2) __kmpc_taskq_task        : pop 
     * 3) __kmp_execute_task_from_queue  : push 
     * 
     * execution ordering:  1,(2,3)*,4 
     */ 
 
    if (!(thunk->th_flags & TQF_TASKQ_TASK)) { 
        kmp_int32 index = (queue == tq->tq_root) ? tid : 0; 
        thunk->th.th_shareds = (kmpc_shared_vars_t *) queue->tq_shareds[index].ai_data; 
 
        if ( __kmp_env_consistency_check ) { 
            __kmp_push_workshare( global_tid, 
                    (queue->tq_flags & TQF_IS_ORDERED) ? ct_task_ordered : ct_task, 
                    queue->tq_loc ); 
        } 
    } 
    else { 
        if ( __kmp_env_consistency_check ) 
            __kmp_push_workshare( global_tid, ct_taskq, queue->tq_loc ); 
    } 
 
    if (in_parallel) { 
        thunk->th_encl_thunk = tq->tq_curr_thunk[tid]; 
        tq->tq_curr_thunk[tid] = thunk; 
 
        KF_DUMP( 200, __kmp_dump_thunk_stack( tq->tq_curr_thunk[tid], global_tid )); 
    } 
 
    KF_TRACE( 50, ("Begin Executing Thunk %p from queue %p on (%d)\n", thunk, queue, global_tid)); 
    thunk->th_task (global_tid, thunk); 
    KF_TRACE( 50, ("End Executing Thunk %p from queue %p on (%d)\n", thunk, queue, global_tid)); 
 
    if (!(thunk->th_flags & TQF_TASKQ_TASK)) { 
        if ( __kmp_env_consistency_check ) 
            __kmp_pop_workshare( global_tid, (queue->tq_flags & TQF_IS_ORDERED) ? ct_task_ordered : ct_task, 
                                 queue->tq_loc ); 
 
        if (in_parallel) { 
            tq->tq_curr_thunk[tid] = thunk->th_encl_thunk; 
            thunk->th_encl_thunk = NULL; 
            KF_DUMP( 200, __kmp_dump_thunk_stack( tq->tq_curr_thunk[tid], global_tid )); 
        } 
 
        if ((thunk->th_flags & TQF_IS_ORDERED) && in_parallel) { 
            __kmp_taskq_check_ordered(global_tid, thunk); 
        } 
 
        __kmp_free_thunk (queue, thunk, in_parallel, global_tid); 
 
        KF_TRACE(100, ("T#%d After freeing thunk: %p, TaskQ looks like this:\n", global_tid, thunk)); 
        KF_DUMP(100, __kmp_dump_task_queue( tq, queue, global_tid )); 
 
        if (in_parallel) { 
            KMP_MB();   /* needed so thunk put on free list before outstanding thunk count is decremented */ 
 
            KMP_DEBUG_ASSERT(queue->tq_th_thunks[tid].ai_data >= 1); 
 
            KF_TRACE( 200, ("__kmp_execute_task_from_queue: T#%d has %d thunks in queue %p\n", 
                global_tid, queue->tq_th_thunks[tid].ai_data-1, queue)); 
 
            queue->tq_th_thunks[tid].ai_data--; 
 
            /* KMP_MB(); */     /* is MB really necessary ? */ 
        } 
 
        if (queue->tq.tq_parent != NULL && in_parallel) { 
            int ct; 
            __kmp_acquire_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
            ct = --(queue->tq_ref_count); 
            __kmp_release_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
            KMP_DEBUG_REF_CTS(("line %d gtid %d: Q %p dec %d\n", 
              __LINE__, global_tid, queue, ct)); 
            KMP_DEBUG_ASSERT( ct >= 0 ); 
        } 
    } 
} 
 
/* --------------------------------------------------------------------------- */ 
 
/* starts a taskq; creates and returns a thunk for the taskq_task        */ 
/* also, returns pointer to shared vars for this thread in "shareds" arg */ 
 
kmpc_thunk_t * 
__kmpc_taskq( ident_t *loc, kmp_int32 global_tid, kmpc_task_t taskq_task, 
              size_t sizeof_thunk, size_t sizeof_shareds, 
              kmp_int32 flags, kmpc_shared_vars_t **shareds ) 
{ 
    int                  in_parallel; 
    kmp_int32            nslots, nthunks, nshareds, nproc; 
    kmpc_task_queue_t   *new_queue, *curr_queue; 
    kmpc_thunk_t        *new_taskq_thunk; 
    kmp_info_t          *th; 
    kmp_team_t          *team; 
    kmp_taskq_t         *tq; 
    kmp_int32            tid; 
 
    KE_TRACE( 10, ("__kmpc_taskq called (%d)\n", global_tid)); 
 
    th = __kmp_threads[ global_tid ]; 
    team = th -> th.th_team; 
    tq = & team -> t.t_taskq; 
    nproc = team -> t.t_nproc; 
    tid = __kmp_tid_from_gtid( global_tid ); 
 
    /* find out whether this is a parallel taskq or serialized one. */ 
    in_parallel = in_parallel_context( team ); 
 
    if( ! tq->tq_root ) { 
        if (in_parallel) { 
            /* Vector ORDERED SECTION to taskq version */ 
            th->th.th_dispatch->th_deo_fcn = __kmp_taskq_eo; 
 
            /* Vector ORDERED SECTION to taskq version */ 
            th->th.th_dispatch->th_dxo_fcn = __kmp_taskq_xo; 
        } 
 
        if (in_parallel) { 
            /* This shouldn't be a barrier region boundary, it will confuse the user. */ 
            /* Need the boundary to be at the end taskq instead. */ 
            if ( __kmp_barrier( bs_plain_barrier, global_tid, TRUE, 0, NULL, NULL )) { 
                /* Creating the active root queue, and we are not the master thread. */ 
                /* The master thread below created the queue and tasks have been     */ 
                /* enqueued, and the master thread released this barrier.  This      */ 
                /* worker thread can now proceed and execute tasks.  See also the    */ 
                /* TQF_RELEASE_WORKERS which is used to handle this case.            */ 
 
                *shareds = (kmpc_shared_vars_t *) tq->tq_root->tq_shareds[tid].ai_data; 
 
                KE_TRACE( 10, ("__kmpc_taskq return (%d)\n", global_tid)); 
 
                return NULL; 
            } 
        } 
 
        /* master thread only executes this code */ 
 
        if( tq->tq_curr_thunk_capacity < nproc ) { 
            if(tq->tq_curr_thunk) 
                __kmp_free(tq->tq_curr_thunk); 
            else { 
                /* only need to do this once at outer level, i.e. when tq_curr_thunk is still NULL */ 
                __kmp_init_lock( & tq->tq_freelist_lck ); 
            } 
 
            tq->tq_curr_thunk = (kmpc_thunk_t **) __kmp_allocate( nproc * sizeof(kmpc_thunk_t *) ); 
            tq -> tq_curr_thunk_capacity = nproc; 
        } 
 
        if (in_parallel) 
            tq->tq_global_flags = TQF_RELEASE_WORKERS; 
    } 
 
    /* dkp: in future, if flags & TQF_HEURISTICS, will choose nslots based */ 
    /*      on some heuristics (e.g., depth of queue nesting?).            */ 
 
    nslots = (in_parallel) ? (2 * nproc) : 1; 
 
    /* There must be nproc * __KMP_TASKQ_THUNKS_PER_TH extra slots for pending */ 
    /* jobs being executed by other threads, and one extra for taskq slot          */ 
 
    nthunks = (in_parallel) ? (nslots + (nproc * __KMP_TASKQ_THUNKS_PER_TH) + 1) : nslots + 2; 
 
    /* Only the root taskq gets a per-thread array of shareds.       */ 
    /* The rest of the taskq's only get one copy of the shared vars. */ 
 
    nshareds = ( !tq->tq_root && in_parallel) ? nproc : 1; 
 
    /*  create overall queue data structure and its components that require allocation */ 
 
    new_queue = __kmp_alloc_taskq ( tq, in_parallel, nslots, nthunks, nshareds, nproc, 
        sizeof_thunk, sizeof_shareds, &new_taskq_thunk, global_tid ); 
 
    /*  rest of new_queue initializations  */ 
 
    new_queue->tq_flags           = flags & TQF_INTERFACE_FLAGS; 
 
    if (in_parallel) { 
        new_queue->tq_tasknum_queuing  = 0; 
        new_queue->tq_tasknum_serving  = 0; 
        new_queue->tq_flags           |= TQF_PARALLEL_CONTEXT; 
    } 
 
    new_queue->tq_taskq_slot   = NULL; 
    new_queue->tq_nslots       = nslots; 
    new_queue->tq_hiwat        = HIGH_WATER_MARK (nslots); 
    new_queue->tq_nfull        = 0; 
    new_queue->tq_head         = 0; 
    new_queue->tq_tail         = 0; 
    new_queue->tq_loc          = loc; 
 
    if ((new_queue->tq_flags & TQF_IS_ORDERED) && in_parallel) { 
        /* prepare to serve the first-queued task's ORDERED directive */ 
        new_queue->tq_tasknum_serving = 1; 
 
        /* Vector ORDERED SECTION to taskq version */ 
        th->th.th_dispatch->th_deo_fcn = __kmp_taskq_eo; 
 
        /* Vector ORDERED SECTION to taskq version */ 
        th->th.th_dispatch->th_dxo_fcn = __kmp_taskq_xo; 
    } 
 
    /*  create a new thunk for the taskq_task in the new_queue  */ 
    *shareds = (kmpc_shared_vars_t *) new_queue->tq_shareds[0].ai_data; 
 
    new_taskq_thunk->th.th_shareds = *shareds; 
    new_taskq_thunk->th_task       = taskq_task; 
    new_taskq_thunk->th_flags      = new_queue->tq_flags | TQF_TASKQ_TASK; 
    new_taskq_thunk->th_status     = 0; 
 
    KMP_DEBUG_ASSERT (new_taskq_thunk->th_flags & TQF_TASKQ_TASK); 
 
    /* KMP_MB(); */ /* make sure these inits complete before threads start using this queue (necessary?) */ 
 
    /* insert the new task queue into the tree, but only after all fields initialized */ 
 
    if (in_parallel) { 
        if( ! tq->tq_root ) { 
            new_queue->tq.tq_parent   = NULL; 
            new_queue->tq_first_child = NULL; 
            new_queue->tq_next_child  = NULL; 
            new_queue->tq_prev_child  = NULL; 
            new_queue->tq_ref_count   = 1; 
            tq->tq_root = new_queue; 
        } 
        else { 
            curr_queue = tq->tq_curr_thunk[tid]->th.th_shareds->sv_queue; 
            new_queue->tq.tq_parent   = curr_queue; 
            new_queue->tq_first_child = NULL; 
            new_queue->tq_prev_child  = NULL; 
            new_queue->tq_ref_count   = 1;      /* for this the thread that built the queue */ 
 
            KMP_DEBUG_REF_CTS(("line %d gtid %d: Q %p alloc %d\n", 
              __LINE__, global_tid, new_queue, new_queue->tq_ref_count)); 
 
            __kmp_acquire_lock(& curr_queue->tq_link_lck, global_tid); 
 
            KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                       /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
            new_queue->tq_next_child = (struct kmpc_task_queue_t *) curr_queue->tq_first_child; 
 
            if (curr_queue->tq_first_child != NULL) 
                curr_queue->tq_first_child->tq_prev_child = new_queue; 
 
            curr_queue->tq_first_child = new_queue; 
 
            __kmp_release_lock(& curr_queue->tq_link_lck, global_tid); 
        } 
 
        /* set up thunk stack only after code that determines curr_queue above */ 
        new_taskq_thunk->th_encl_thunk = tq->tq_curr_thunk[tid]; 
        tq->tq_curr_thunk[tid] = new_taskq_thunk; 
 
        KF_DUMP( 200, __kmp_dump_thunk_stack( tq->tq_curr_thunk[tid], global_tid )); 
    } 
    else { 
        new_taskq_thunk->th_encl_thunk = 0; 
        new_queue->tq.tq_parent   = NULL; 
        new_queue->tq_first_child = NULL; 
        new_queue->tq_next_child  = NULL; 
        new_queue->tq_prev_child  = NULL; 
        new_queue->tq_ref_count   = 1; 
    } 
 
#ifdef KMP_DEBUG 
    KF_TRACE(150, ("Creating TaskQ Task on (%d):\n", global_tid)); 
    KF_DUMP(150, __kmp_dump_thunk( tq, new_taskq_thunk, global_tid )); 
 
    if (in_parallel) { 
        KF_TRACE(25, ("After TaskQ at %p Creation on (%d):\n", new_queue, global_tid)); 
    } else { 
        KF_TRACE(25, ("After Serial TaskQ at %p Creation on (%d):\n", new_queue, global_tid)); 
    } 
 
    KF_DUMP(25, __kmp_dump_task_queue( tq, new_queue, global_tid )); 
 
    if (in_parallel) { 
        KF_DUMP(50, __kmp_dump_task_queue_tree( tq, tq->tq_root, global_tid )); 
    } 
#endif /* KMP_DEBUG */ 
 
    if ( __kmp_env_consistency_check ) 
        __kmp_push_workshare( global_tid, ct_taskq, new_queue->tq_loc ); 
 
    KE_TRACE( 10, ("__kmpc_taskq return (%d)\n", global_tid)); 
 
    return new_taskq_thunk; 
} 
 
 
/*  ends a taskq; last thread out destroys the queue  */ 
 
void 
__kmpc_end_taskq(ident_t *loc, kmp_int32 global_tid, kmpc_thunk_t *taskq_thunk) 
{ 
#ifdef KMP_DEBUG 
    kmp_int32           i; 
#endif 
    kmp_taskq_t        *tq; 
    int                 in_parallel; 
    kmp_info_t         *th; 
    kmp_int32           is_outermost; 
    kmpc_task_queue_t  *queue; 
    kmpc_thunk_t       *thunk; 
    int                 nproc; 
 
    KE_TRACE( 10, ("__kmpc_end_taskq called (%d)\n", global_tid)); 
 
    tq = & __kmp_threads[global_tid] -> th.th_team -> t.t_taskq; 
    nproc = __kmp_threads[global_tid] -> th.th_team -> t.t_nproc; 
 
    /* For the outermost taskq only, all but one thread will have taskq_thunk == NULL */ 
    queue = (taskq_thunk == NULL) ? tq->tq_root : taskq_thunk->th.th_shareds->sv_queue; 
 
    KE_TRACE( 50, ("__kmpc_end_taskq queue=%p (%d) \n", queue, global_tid)); 
    is_outermost = (queue == tq->tq_root); 
    in_parallel = (queue->tq_flags & TQF_PARALLEL_CONTEXT); 
 
    if (in_parallel) { 
        kmp_uint32 spins; 
 
        /* this is just a safeguard to release the waiting threads if */ 
        /* the outermost taskq never queues a task                    */ 
 
        if (is_outermost && (KMP_MASTER_GTID( global_tid ))) { 
            if( tq->tq_global_flags & TQF_RELEASE_WORKERS ) { 
                /* no lock needed, workers are still in spin mode */ 
                tq->tq_global_flags &= ~TQF_RELEASE_WORKERS; 
 
                __kmp_end_split_barrier( bs_plain_barrier, global_tid ); 
            } 
        } 
 
        /* keep dequeueing work until all tasks are queued and dequeued */ 
 
        do { 
            /* wait until something is available to dequeue */ 
            KMP_INIT_YIELD(spins); 
 
            while ( (queue->tq_nfull == 0) 
                 && (queue->tq_taskq_slot == NULL) 
                 && (! __kmp_taskq_has_any_children(queue) ) 
                 && (! (queue->tq_flags & TQF_ALL_TASKS_QUEUED) ) 
                  ) { 
                KMP_YIELD_WHEN( TRUE, spins ); 
            } 
 
            /* check to see if we can execute tasks in the queue */ 
            while ( ( (queue->tq_nfull != 0) || (queue->tq_taskq_slot != NULL) ) 
                 && (thunk = __kmp_find_task_in_queue(global_tid, queue)) != NULL 
                  ) { 
                KF_TRACE(50, ("Found thunk: %p in primary queue %p (%d)\n", thunk, queue, global_tid)); 
                __kmp_execute_task_from_queue( tq, loc, global_tid, thunk, in_parallel ); 
            } 
 
            /* see if work found can be found in a descendant queue */ 
            if ( (__kmp_taskq_has_any_children(queue)) 
              && (thunk = __kmp_find_task_in_descendant_queue(global_tid, queue)) != NULL 
               ) { 
 
                KF_TRACE(50, ("Stole thunk: %p in descendant queue: %p while waiting in queue: %p (%d)\n", 
                    thunk, thunk->th.th_shareds->sv_queue, queue, global_tid )); 
 
                __kmp_execute_task_from_queue( tq, loc, global_tid, thunk, in_parallel ); 
            } 
 
        } while ( (! (queue->tq_flags & TQF_ALL_TASKS_QUEUED)) 
               || (queue->tq_nfull != 0) 
                ); 
 
        KF_TRACE(50, ("All tasks queued and dequeued in queue: %p (%d)\n", queue, global_tid)); 
 
        /* wait while all tasks are not finished and more work found 
           in descendant queues */ 
 
        while ( (!__kmp_taskq_tasks_finished(queue)) 
             && (thunk = __kmp_find_task_in_descendant_queue(global_tid, queue)) != NULL 
              ) { 
 
            KF_TRACE(50, ("Stole thunk: %p in descendant queue: %p while waiting in queue: %p (%d)\n", 
                thunk, thunk->th.th_shareds->sv_queue, queue, global_tid)); 
 
            __kmp_execute_task_from_queue( tq, loc, global_tid, thunk, in_parallel ); 
        } 
 
        KF_TRACE(50, ("No work found in descendent queues or all work finished in queue: %p (%d)\n", queue, global_tid)); 
 
        if (!is_outermost) { 
            /* need to return if NOWAIT present and not outermost taskq */ 
 
            if (queue->tq_flags & TQF_IS_NOWAIT) { 
                __kmp_acquire_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
                queue->tq_ref_count--; 
                KMP_DEBUG_ASSERT( queue->tq_ref_count >= 0 ); 
                __kmp_release_lock(& queue->tq.tq_parent->tq_link_lck, global_tid); 
 
                KE_TRACE( 10, ("__kmpc_end_taskq return for nowait case (%d)\n", global_tid)); 
 
                return; 
            } 
 
            __kmp_find_and_remove_finished_child_taskq( tq, global_tid, queue ); 
 
            /* WAIT until all tasks are finished and no child queues exist before proceeding */ 
            KMP_INIT_YIELD(spins); 
 
            while (!__kmp_taskq_tasks_finished(queue) || __kmp_taskq_has_any_children(queue)) { 
                thunk = __kmp_find_task_in_ancestor_queue( tq, global_tid, queue ); 
 
                if (thunk != NULL) { 
                    KF_TRACE(50, ("Stole thunk: %p in ancestor queue: %p while waiting in queue: %p (%d)\n", 
                                  thunk, thunk->th.th_shareds->sv_queue, queue, global_tid)); 
                    __kmp_execute_task_from_queue( tq, loc, global_tid, thunk, in_parallel ); 
                } 
 
                KMP_YIELD_WHEN( thunk == NULL, spins ); 
 
                __kmp_find_and_remove_finished_child_taskq( tq, global_tid, queue ); 
            } 
 
            __kmp_acquire_lock(& queue->tq_queue_lck, global_tid); 
            if ( !(queue->tq_flags & TQF_DEALLOCATED) ) { 
                queue->tq_flags |= TQF_DEALLOCATED; 
            } 
            __kmp_release_lock(& queue->tq_queue_lck, global_tid); 
 
            /* only the allocating thread can deallocate the queue */ 
            if (taskq_thunk != NULL) { 
                __kmp_remove_queue_from_tree( tq, global_tid, queue, TRUE ); 
            } 
 
            KE_TRACE( 10, ("__kmpc_end_taskq return for non_outermost queue, wait case (%d)\n", global_tid)); 
 
            return; 
        } 
 
        /* Outermost Queue: steal work from descendants until all tasks are finished */ 
 
        KMP_INIT_YIELD(spins); 
 
        while (!__kmp_taskq_tasks_finished(queue)) { 
            thunk = __kmp_find_task_in_descendant_queue(global_tid, queue); 
 
            if (thunk != NULL) { 
                KF_TRACE(50, ("Stole thunk: %p in descendant queue: %p while waiting in queue: %p (%d)\n", 
                    thunk, thunk->th.th_shareds->sv_queue, queue, global_tid)); 
 
                __kmp_execute_task_from_queue( tq, loc, global_tid, thunk, in_parallel ); 
            } 
 
            KMP_YIELD_WHEN( thunk == NULL, spins ); 
        } 
 
        /* Need this barrier to prevent destruction of queue before threads have all executed above code */ 
        /* This may need to be done earlier when NOWAIT is implemented for the outermost level */ 
 
        if ( !__kmp_barrier( bs_plain_barrier, global_tid, TRUE, 0, NULL, NULL )) { 
            /* the queue->tq_flags & TQF_IS_NOWAIT case is not yet handled here;   */ 
            /* for right now, everybody waits, and the master thread destroys the  */ 
            /* remaining queues.                                                   */ 
 
            __kmp_remove_all_child_taskq( tq, global_tid, queue ); 
 
            /* Now destroy the root queue */ 
            KF_TRACE(100, ("T#%d Before Deletion of top-level TaskQ at %p:\n", global_tid, queue )); 
            KF_DUMP(100, __kmp_dump_task_queue( tq, queue, global_tid )); 
 
#ifdef KMP_DEBUG 
            /*  the root queue entry  */ 
            KMP_DEBUG_ASSERT ((queue->tq.tq_parent == NULL) && (queue->tq_next_child == NULL)); 
 
            /*  children must all be gone by now because of barrier above */ 
            KMP_DEBUG_ASSERT (queue->tq_first_child == NULL); 
 
            for (i=0; i<nproc; i++) { 
                KMP_DEBUG_ASSERT(queue->tq_th_thunks[i].ai_data == 0); 
            } 
 
            for (i=0, thunk=queue->tq_free_thunks; thunk != NULL; i++, thunk=thunk->th.th_next_free); 
 
            KMP_DEBUG_ASSERT (i == queue->tq_nslots + (nproc * __KMP_TASKQ_THUNKS_PER_TH)); 
 
            for (i = 0; i < nproc; i++) { 
                KMP_DEBUG_ASSERT( ! tq->tq_curr_thunk[i] ); 
            } 
#endif 
            /*  unlink the root queue entry  */ 
            tq -> tq_root =  NULL; 
 
            /*  release storage for root queue entry  */ 
            KF_TRACE(50, ("After Deletion of top-level TaskQ at %p on (%d):\n", queue, global_tid)); 
 
            queue->tq_flags |= TQF_DEALLOCATED; 
            __kmp_free_taskq ( tq, queue, in_parallel, global_tid ); 
 
            KF_DUMP(50, __kmp_dump_task_queue_tree( tq, tq->tq_root, global_tid )); 
 
            /* release the workers now that the data structures are up to date */ 
            __kmp_end_split_barrier( bs_plain_barrier, global_tid ); 
        } 
 
        th = __kmp_threads[ global_tid ]; 
 
        /* Reset ORDERED SECTION to parallel version */ 
        th->th.th_dispatch->th_deo_fcn = 0; 
 
        /* Reset ORDERED SECTION to parallel version */ 
        th->th.th_dispatch->th_dxo_fcn = 0; 
    } 
    else { 
        /* in serial execution context, dequeue the last task  */ 
        /* and execute it, if there were any tasks encountered */ 
 
        if (queue->tq_nfull > 0) { 
            KMP_DEBUG_ASSERT(queue->tq_nfull == 1); 
 
            thunk = __kmp_dequeue_task(global_tid, queue, in_parallel); 
 
            if (queue->tq_flags & TQF_IS_LAST_TASK) { 
                /* TQF_IS_LASTPRIVATE, one thing in queue, __kmpc_end_taskq_task() */ 
                /* has been run so this is last task, run with TQF_IS_LAST_TASK so */ 
                /* instrumentation does copy-out.                                  */ 
 
                /* no need for test_then_or call since already locked */ 
                thunk->th_flags |= TQF_IS_LAST_TASK; 
            } 
 
            KF_TRACE(50, ("T#%d found thunk: %p in serial queue: %p\n", global_tid, thunk, queue)); 
 
            __kmp_execute_task_from_queue( tq, loc, global_tid, thunk, in_parallel ); 
        } 
 
        /* destroy the unattached serial queue now that there is no more work to do */ 
        KF_TRACE(100, ("Before Deletion of Serialized TaskQ at %p on (%d):\n", queue, global_tid)); 
        KF_DUMP(100, __kmp_dump_task_queue( tq, queue, global_tid )); 
 
#ifdef KMP_DEBUG 
        i = 0; 
        for (thunk=queue->tq_free_thunks; thunk != NULL; thunk=thunk->th.th_next_free) 
            ++i; 
        KMP_DEBUG_ASSERT (i == queue->tq_nslots + 1); 
#endif 
        /*  release storage for unattached serial queue  */ 
        KF_TRACE(50, ("Serialized TaskQ at %p deleted on (%d).\n", queue, global_tid)); 
 
        queue->tq_flags |= TQF_DEALLOCATED; 
        __kmp_free_taskq ( tq, queue, in_parallel, global_tid ); 
    } 
 
    KE_TRACE( 10, ("__kmpc_end_taskq return (%d)\n", global_tid)); 
} 
 
/*  Enqueues a task for thunk previously created by __kmpc_task_buffer. */ 
/*  Returns nonzero if just filled up queue  */ 
 
kmp_int32 
__kmpc_task(ident_t *loc, kmp_int32 global_tid, kmpc_thunk_t *thunk) 
{ 
    kmp_int32          ret; 
    kmpc_task_queue_t *queue; 
    int                in_parallel; 
    kmp_taskq_t       *tq; 
 
    KE_TRACE( 10, ("__kmpc_task called (%d)\n", global_tid)); 
 
    KMP_DEBUG_ASSERT (!(thunk->th_flags & TQF_TASKQ_TASK));  /*  thunk->th_task is a regular task  */ 
 
    tq          = &__kmp_threads[global_tid] -> th.th_team -> t.t_taskq; 
    queue       = thunk->th.th_shareds->sv_queue; 
    in_parallel = (queue->tq_flags & TQF_PARALLEL_CONTEXT); 
 
    if (in_parallel && (thunk->th_flags & TQF_IS_ORDERED)) 
        thunk->th_tasknum = ++queue->tq_tasknum_queuing; 
 
    /* For serial execution dequeue the preceding task and execute it, if one exists */ 
    /* This cannot be the last task.  That one is handled in __kmpc_end_taskq */ 
 
    if (!in_parallel && queue->tq_nfull > 0) { 
        kmpc_thunk_t *prev_thunk; 
 
        KMP_DEBUG_ASSERT(queue->tq_nfull == 1); 
 
        prev_thunk = __kmp_dequeue_task(global_tid, queue, in_parallel); 
 
        KF_TRACE(50, ("T#%d found thunk: %p in serial queue: %p\n", global_tid, prev_thunk, queue)); 
 
        __kmp_execute_task_from_queue( tq, loc, global_tid, prev_thunk, in_parallel ); 
    } 
 
    /* The instrumentation sequence is:  __kmpc_task_buffer(), initialize private    */ 
    /* variables, __kmpc_task().  The __kmpc_task_buffer routine checks that the     */ 
    /* task queue is not full and allocates a thunk (which is then passed to         */ 
    /* __kmpc_task()).  So, the enqueue below should never fail due to a full queue. */ 
 
    KF_TRACE(100, ("After enqueueing this Task on (%d):\n", global_tid)); 
    KF_DUMP(100, __kmp_dump_thunk( tq, thunk, global_tid )); 
 
    ret = __kmp_enqueue_task ( tq, global_tid, queue, thunk, in_parallel ); 
 
    KF_TRACE(100, ("Task Queue looks like this on (%d):\n", global_tid)); 
    KF_DUMP(100, __kmp_dump_task_queue( tq, queue, global_tid )); 
 
    KE_TRACE( 10, ("__kmpc_task return (%d)\n", global_tid)); 
 
    return ret; 
} 
 
/*  enqueues a taskq_task for thunk previously created by __kmpc_taskq  */ 
/*  this should never be called unless in a parallel context            */ 
 
void 
__kmpc_taskq_task(ident_t *loc, kmp_int32 global_tid, kmpc_thunk_t *thunk, kmp_int32 status) 
{ 
    kmpc_task_queue_t *queue; 
    kmp_taskq_t       *tq  = &__kmp_threads[global_tid] -> th.th_team -> t.t_taskq; 
    int                tid = __kmp_tid_from_gtid( global_tid ); 
 
    KE_TRACE( 10, ("__kmpc_taskq_task called (%d)\n", global_tid)); 
    KF_TRACE(100, ("TaskQ Task argument thunk on (%d):\n", global_tid)); 
    KF_DUMP(100, __kmp_dump_thunk( tq, thunk, global_tid )); 
 
    queue = thunk->th.th_shareds->sv_queue; 
 
    if ( __kmp_env_consistency_check ) 
        __kmp_pop_workshare( global_tid, ct_taskq, loc ); 
 
    /*  thunk->th_task is the taskq_task  */ 
    KMP_DEBUG_ASSERT (thunk->th_flags & TQF_TASKQ_TASK); 
 
    /*  not supposed to call __kmpc_taskq_task if it's already enqueued  */ 
    KMP_DEBUG_ASSERT (queue->tq_taskq_slot == NULL); 
 
    /* dequeue taskq thunk from curr_thunk stack */ 
    tq->tq_curr_thunk[tid] = thunk->th_encl_thunk; 
    thunk->th_encl_thunk = NULL; 
 
    KF_DUMP( 200, __kmp_dump_thunk_stack( tq->tq_curr_thunk[tid], global_tid )); 
 
    thunk->th_status = status; 
 
    KMP_MB();  /*  flush thunk->th_status before taskq_task enqueued to avoid race condition  */ 
 
    /*  enqueue taskq_task in thunk into special slot in queue     */ 
    /* GEH - probably don't need to lock taskq slot since only one */ 
    /*       thread enqueues & already a lock set at dequeue point */ 
 
    queue->tq_taskq_slot = thunk; 
 
    KE_TRACE( 10, ("__kmpc_taskq_task return (%d)\n", global_tid)); 
} 
 
/*  ends a taskq_task; done generating tasks  */ 
 
void 
__kmpc_end_taskq_task(ident_t *loc, kmp_int32 global_tid, kmpc_thunk_t *thunk) 
{ 
    kmp_taskq_t       *tq; 
    kmpc_task_queue_t *queue; 
    int                in_parallel; 
    int                tid; 
 
    KE_TRACE( 10, ("__kmpc_end_taskq_task called (%d)\n", global_tid)); 
 
    tq          = &__kmp_threads[global_tid] -> th.th_team -> t.t_taskq; 
    queue       = thunk->th.th_shareds->sv_queue; 
    in_parallel = (queue->tq_flags & TQF_PARALLEL_CONTEXT); 
    tid         = __kmp_tid_from_gtid( global_tid ); 
 
    if ( __kmp_env_consistency_check ) 
        __kmp_pop_workshare( global_tid, ct_taskq, loc ); 
 
    if (in_parallel) { 
#if KMP_ARCH_X86 || \ 
    KMP_ARCH_X86_64 
 
        KMP_TEST_THEN_OR32( &queue->tq_flags, (kmp_int32) TQF_ALL_TASKS_QUEUED ); 
#else 
        { 
            __kmp_acquire_lock(& queue->tq_queue_lck, global_tid); 
 
            KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                       /* Seems to work fine without this call for digital/alpha, needed for IBM/RS6000 */ 
 
            queue->tq_flags |= TQF_ALL_TASKS_QUEUED; 
 
            __kmp_release_lock(& queue->tq_queue_lck, global_tid); 
        } 
#endif 
    } 
 
    if (thunk->th_flags & TQF_IS_LASTPRIVATE) { 
        /* Normally, __kmp_find_task_in_queue() refuses to schedule the last task in the */ 
        /* queue if TQF_IS_LASTPRIVATE so we can positively identify that last task      */ 
        /* and run it with its TQF_IS_LAST_TASK bit turned on in th_flags.  When         */ 
        /* __kmpc_end_taskq_task() is called we are done generating all the tasks, so    */ 
        /* we know the last one in the queue is the lastprivate task.  Mark the queue    */ 
        /* as having gotten to this state via tq_flags & TQF_IS_LAST_TASK; when that     */ 
        /* task actually executes mark it via th_flags & TQF_IS_LAST_TASK (this th_flags */ 
        /* bit signals the instrumented code to do copy-outs after execution).           */ 
 
        if (! in_parallel) { 
            /* No synchronization needed for serial context */ 
            queue->tq_flags |= TQF_IS_LAST_TASK; 
        } 
        else { 
#if KMP_ARCH_X86 || \ 
    KMP_ARCH_X86_64 
 
            KMP_TEST_THEN_OR32( &queue->tq_flags, (kmp_int32) TQF_IS_LAST_TASK ); 
#else 
            { 
                __kmp_acquire_lock(& queue->tq_queue_lck, global_tid); 
 
                KMP_MB();  /* make sure data structures are in consistent state before querying them */ 
                           /* Seems to work without this call for digital/alpha, needed for IBM/RS6000 */ 
 
                queue->tq_flags |= TQF_IS_LAST_TASK; 
 
                __kmp_release_lock(& queue->tq_queue_lck, global_tid); 
            } 
#endif 
            /* to prevent race condition where last task is dequeued but */ 
            /* flag isn't visible yet (not sure about this)              */ 
            KMP_MB(); 
        } 
    } 
 
    /* dequeue taskq thunk from curr_thunk stack */ 
    if (in_parallel) { 
        tq->tq_curr_thunk[tid] = thunk->th_encl_thunk; 
        thunk->th_encl_thunk = NULL; 
 
        KF_DUMP( 200, __kmp_dump_thunk_stack( tq->tq_curr_thunk[tid], global_tid )); 
    } 
 
    KE_TRACE( 10, ("__kmpc_end_taskq_task return (%d)\n", global_tid)); 
} 
 
/* returns thunk for a regular task based on taskq_thunk              */ 
/* (__kmpc_taskq_task does the analogous thing for a TQF_TASKQ_TASK)  */ 
 
kmpc_thunk_t * 
__kmpc_task_buffer(ident_t *loc, kmp_int32 global_tid, kmpc_thunk_t *taskq_thunk, kmpc_task_t task) 
{ 
    kmp_taskq_t       *tq; 
    kmpc_task_queue_t *queue; 
    kmpc_thunk_t      *new_thunk; 
    int                in_parallel; 
 
    KE_TRACE( 10, ("__kmpc_task_buffer called (%d)\n", global_tid)); 
 
    KMP_DEBUG_ASSERT (taskq_thunk->th_flags & TQF_TASKQ_TASK);  /*  taskq_thunk->th_task is the taskq_task  */ 
 
    tq          = &__kmp_threads[global_tid] -> th.th_team -> t.t_taskq; 
    queue       = taskq_thunk->th.th_shareds->sv_queue; 
    in_parallel = (queue->tq_flags & TQF_PARALLEL_CONTEXT); 
 
    /* The instrumentation sequence is:  __kmpc_task_buffer(), initialize private */ 
    /* variables, __kmpc_task().  The __kmpc_task_buffer routine checks that the  */ 
    /* task queue is not full and allocates a thunk (which is then passed to      */ 
    /* __kmpc_task()).  So, we can pre-allocate a thunk here assuming it will be  */ 
    /* the next to be enqueued in __kmpc_task().                                  */ 
 
    new_thunk = __kmp_alloc_thunk (queue, in_parallel, global_tid); 
    new_thunk->th.th_shareds = (kmpc_shared_vars_t *) queue->tq_shareds[0].ai_data; 
    new_thunk->th_encl_thunk = NULL; 
    new_thunk->th_task       = task; 
 
    /* GEH - shouldn't need to lock the read of tq_flags here */ 
    new_thunk->th_flags      = queue->tq_flags & TQF_INTERFACE_FLAGS; 
 
    new_thunk->th_status     = 0; 
 
    KMP_DEBUG_ASSERT (!(new_thunk->th_flags & TQF_TASKQ_TASK)); 
 
    KF_TRACE(100, ("Creating Regular Task on (%d):\n", global_tid)); 
    KF_DUMP(100, __kmp_dump_thunk( tq, new_thunk, global_tid )); 
 
    KE_TRACE( 10, ("__kmpc_task_buffer return (%d)\n", global_tid)); 
 
    return new_thunk; 
} 
 
/* --------------------------------------------------------------------------- */