LLVM OpenMP* Runtime Library
kmp_tasking.cpp
1 /*
2  * kmp_tasking.cpp -- OpenMP 3.0 tasking support.
3  */
4 
5 //===----------------------------------------------------------------------===//
6 //
7 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
8 // See https://llvm.org/LICENSE.txt for license information.
9 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "kmp.h"
14 #include "kmp_i18n.h"
15 #include "kmp_itt.h"
16 #include "kmp_stats.h"
17 #include "kmp_wait_release.h"
18 #include "kmp_taskdeps.h"
19 
20 #if OMPT_SUPPORT
21 #include "ompt-specific.h"
22 #endif
23 
24 /* forward declaration */
25 static void __kmp_enable_tasking(kmp_task_team_t *task_team,
26  kmp_info_t *this_thr);
27 static void __kmp_alloc_task_deque(kmp_info_t *thread,
28  kmp_thread_data_t *thread_data);
29 static int __kmp_realloc_task_threads_data(kmp_info_t *thread,
30  kmp_task_team_t *task_team);
31 static void __kmp_bottom_half_finish_proxy(kmp_int32 gtid, kmp_task_t *ptask);
32 
33 #ifdef BUILD_TIED_TASK_STACK
34 
35 // __kmp_trace_task_stack: print the tied tasks from the task stack in order
36 // from top do bottom
37 //
38 // gtid: global thread identifier for thread containing stack
39 // thread_data: thread data for task team thread containing stack
40 // threshold: value above which the trace statement triggers
41 // location: string identifying call site of this function (for trace)
42 static void __kmp_trace_task_stack(kmp_int32 gtid,
43  kmp_thread_data_t *thread_data,
44  int threshold, char *location) {
45  kmp_task_stack_t *task_stack = &thread_data->td.td_susp_tied_tasks;
46  kmp_taskdata_t **stack_top = task_stack->ts_top;
47  kmp_int32 entries = task_stack->ts_entries;
48  kmp_taskdata_t *tied_task;
49 
50  KA_TRACE(
51  threshold,
52  ("__kmp_trace_task_stack(start): location = %s, gtid = %d, entries = %d, "
53  "first_block = %p, stack_top = %p \n",
54  location, gtid, entries, task_stack->ts_first_block, stack_top));
55 
56  KMP_DEBUG_ASSERT(stack_top != NULL);
57  KMP_DEBUG_ASSERT(entries > 0);
58 
59  while (entries != 0) {
60  KMP_DEBUG_ASSERT(stack_top != &task_stack->ts_first_block.sb_block[0]);
61  // fix up ts_top if we need to pop from previous block
62  if (entries & TASK_STACK_INDEX_MASK == 0) {
63  kmp_stack_block_t *stack_block = (kmp_stack_block_t *)(stack_top);
64 
65  stack_block = stack_block->sb_prev;
66  stack_top = &stack_block->sb_block[TASK_STACK_BLOCK_SIZE];
67  }
68 
69  // finish bookkeeping
70  stack_top--;
71  entries--;
72 
73  tied_task = *stack_top;
74 
75  KMP_DEBUG_ASSERT(tied_task != NULL);
76  KMP_DEBUG_ASSERT(tied_task->td_flags.tasktype == TASK_TIED);
77 
78  KA_TRACE(threshold,
79  ("__kmp_trace_task_stack(%s): gtid=%d, entry=%d, "
80  "stack_top=%p, tied_task=%p\n",
81  location, gtid, entries, stack_top, tied_task));
82  }
83  KMP_DEBUG_ASSERT(stack_top == &task_stack->ts_first_block.sb_block[0]);
84 
85  KA_TRACE(threshold,
86  ("__kmp_trace_task_stack(exit): location = %s, gtid = %d\n",
87  location, gtid));
88 }
89 
90 // __kmp_init_task_stack: initialize the task stack for the first time
91 // after a thread_data structure is created.
92 // It should not be necessary to do this again (assuming the stack works).
93 //
94 // gtid: global thread identifier of calling thread
95 // thread_data: thread data for task team thread containing stack
96 static void __kmp_init_task_stack(kmp_int32 gtid,
97  kmp_thread_data_t *thread_data) {
98  kmp_task_stack_t *task_stack = &thread_data->td.td_susp_tied_tasks;
99  kmp_stack_block_t *first_block;
100 
101  // set up the first block of the stack
102  first_block = &task_stack->ts_first_block;
103  task_stack->ts_top = (kmp_taskdata_t **)first_block;
104  memset((void *)first_block, '\0',
105  TASK_STACK_BLOCK_SIZE * sizeof(kmp_taskdata_t *));
106 
107  // initialize the stack to be empty
108  task_stack->ts_entries = TASK_STACK_EMPTY;
109  first_block->sb_next = NULL;
110  first_block->sb_prev = NULL;
111 }
112 
113 // __kmp_free_task_stack: free the task stack when thread_data is destroyed.
114 //
115 // gtid: global thread identifier for calling thread
116 // thread_data: thread info for thread containing stack
117 static void __kmp_free_task_stack(kmp_int32 gtid,
118  kmp_thread_data_t *thread_data) {
119  kmp_task_stack_t *task_stack = &thread_data->td.td_susp_tied_tasks;
120  kmp_stack_block_t *stack_block = &task_stack->ts_first_block;
121 
122  KMP_DEBUG_ASSERT(task_stack->ts_entries == TASK_STACK_EMPTY);
123  // free from the second block of the stack
124  while (stack_block != NULL) {
125  kmp_stack_block_t *next_block = (stack_block) ? stack_block->sb_next : NULL;
126 
127  stack_block->sb_next = NULL;
128  stack_block->sb_prev = NULL;
129  if (stack_block != &task_stack->ts_first_block) {
130  __kmp_thread_free(thread,
131  stack_block); // free the block, if not the first
132  }
133  stack_block = next_block;
134  }
135  // initialize the stack to be empty
136  task_stack->ts_entries = 0;
137  task_stack->ts_top = NULL;
138 }
139 
140 // __kmp_push_task_stack: Push the tied task onto the task stack.
141 // Grow the stack if necessary by allocating another block.
142 //
143 // gtid: global thread identifier for calling thread
144 // thread: thread info for thread containing stack
145 // tied_task: the task to push on the stack
146 static void __kmp_push_task_stack(kmp_int32 gtid, kmp_info_t *thread,
147  kmp_taskdata_t *tied_task) {
148  // GEH - need to consider what to do if tt_threads_data not allocated yet
149  kmp_thread_data_t *thread_data =
150  &thread->th.th_task_team->tt.tt_threads_data[__kmp_tid_from_gtid(gtid)];
151  kmp_task_stack_t *task_stack = &thread_data->td.td_susp_tied_tasks;
152 
153  if (tied_task->td_flags.team_serial || tied_task->td_flags.tasking_ser) {
154  return; // Don't push anything on stack if team or team tasks are serialized
155  }
156 
157  KMP_DEBUG_ASSERT(tied_task->td_flags.tasktype == TASK_TIED);
158  KMP_DEBUG_ASSERT(task_stack->ts_top != NULL);
159 
160  KA_TRACE(20,
161  ("__kmp_push_task_stack(enter): GTID: %d; THREAD: %p; TASK: %p\n",
162  gtid, thread, tied_task));
163  // Store entry
164  *(task_stack->ts_top) = tied_task;
165 
166  // Do bookkeeping for next push
167  task_stack->ts_top++;
168  task_stack->ts_entries++;
169 
170  if (task_stack->ts_entries & TASK_STACK_INDEX_MASK == 0) {
171  // Find beginning of this task block
172  kmp_stack_block_t *stack_block =
173  (kmp_stack_block_t *)(task_stack->ts_top - TASK_STACK_BLOCK_SIZE);
174 
175  // Check if we already have a block
176  if (stack_block->sb_next !=
177  NULL) { // reset ts_top to beginning of next block
178  task_stack->ts_top = &stack_block->sb_next->sb_block[0];
179  } else { // Alloc new block and link it up
180  kmp_stack_block_t *new_block = (kmp_stack_block_t *)__kmp_thread_calloc(
181  thread, sizeof(kmp_stack_block_t));
182 
183  task_stack->ts_top = &new_block->sb_block[0];
184  stack_block->sb_next = new_block;
185  new_block->sb_prev = stack_block;
186  new_block->sb_next = NULL;
187 
188  KA_TRACE(
189  30,
190  ("__kmp_push_task_stack(): GTID: %d; TASK: %p; Alloc new block: %p\n",
191  gtid, tied_task, new_block));
192  }
193  }
194  KA_TRACE(20, ("__kmp_push_task_stack(exit): GTID: %d; TASK: %p\n", gtid,
195  tied_task));
196 }
197 
198 // __kmp_pop_task_stack: Pop the tied task from the task stack. Don't return
199 // the task, just check to make sure it matches the ending task passed in.
200 //
201 // gtid: global thread identifier for the calling thread
202 // thread: thread info structure containing stack
203 // tied_task: the task popped off the stack
204 // ending_task: the task that is ending (should match popped task)
205 static void __kmp_pop_task_stack(kmp_int32 gtid, kmp_info_t *thread,
206  kmp_taskdata_t *ending_task) {
207  // GEH - need to consider what to do if tt_threads_data not allocated yet
208  kmp_thread_data_t *thread_data =
209  &thread->th.th_task_team->tt_threads_data[__kmp_tid_from_gtid(gtid)];
210  kmp_task_stack_t *task_stack = &thread_data->td.td_susp_tied_tasks;
211  kmp_taskdata_t *tied_task;
212 
213  if (ending_task->td_flags.team_serial || ending_task->td_flags.tasking_ser) {
214  // Don't pop anything from stack if team or team tasks are serialized
215  return;
216  }
217 
218  KMP_DEBUG_ASSERT(task_stack->ts_top != NULL);
219  KMP_DEBUG_ASSERT(task_stack->ts_entries > 0);
220 
221  KA_TRACE(20, ("__kmp_pop_task_stack(enter): GTID: %d; THREAD: %p\n", gtid,
222  thread));
223 
224  // fix up ts_top if we need to pop from previous block
225  if (task_stack->ts_entries & TASK_STACK_INDEX_MASK == 0) {
226  kmp_stack_block_t *stack_block = (kmp_stack_block_t *)(task_stack->ts_top);
227 
228  stack_block = stack_block->sb_prev;
229  task_stack->ts_top = &stack_block->sb_block[TASK_STACK_BLOCK_SIZE];
230  }
231 
232  // finish bookkeeping
233  task_stack->ts_top--;
234  task_stack->ts_entries--;
235 
236  tied_task = *(task_stack->ts_top);
237 
238  KMP_DEBUG_ASSERT(tied_task != NULL);
239  KMP_DEBUG_ASSERT(tied_task->td_flags.tasktype == TASK_TIED);
240  KMP_DEBUG_ASSERT(tied_task == ending_task); // If we built the stack correctly
241 
242  KA_TRACE(20, ("__kmp_pop_task_stack(exit): GTID: %d; TASK: %p\n", gtid,
243  tied_task));
244  return;
245 }
246 #endif /* BUILD_TIED_TASK_STACK */
247 
248 // returns 1 if new task is allowed to execute, 0 otherwise
249 // checks Task Scheduling constraint (if requested) and
250 // mutexinoutset dependencies if any
251 static bool __kmp_task_is_allowed(int gtid, const kmp_int32 is_constrained,
252  const kmp_taskdata_t *tasknew,
253  const kmp_taskdata_t *taskcurr) {
254  if (is_constrained && (tasknew->td_flags.tiedness == TASK_TIED)) {
255  // Check if the candidate obeys the Task Scheduling Constraints (TSC)
256  // only descendant of all deferred tied tasks can be scheduled, checking
257  // the last one is enough, as it in turn is the descendant of all others
258  kmp_taskdata_t *current = taskcurr->td_last_tied;
259  KMP_DEBUG_ASSERT(current != NULL);
260  // check if the task is not suspended on barrier
261  if (current->td_flags.tasktype == TASK_EXPLICIT ||
262  current->td_taskwait_thread > 0) { // <= 0 on barrier
263  kmp_int32 level = current->td_level;
264  kmp_taskdata_t *parent = tasknew->td_parent;
265  while (parent != current && parent->td_level > level) {
266  // check generation up to the level of the current task
267  parent = parent->td_parent;
268  KMP_DEBUG_ASSERT(parent != NULL);
269  }
270  if (parent != current)
271  return false;
272  }
273  }
274  // Check mutexinoutset dependencies, acquire locks
275  kmp_depnode_t *node = tasknew->td_depnode;
276  if (UNLIKELY(node && (node->dn.mtx_num_locks > 0))) {
277  for (int i = 0; i < node->dn.mtx_num_locks; ++i) {
278  KMP_DEBUG_ASSERT(node->dn.mtx_locks[i] != NULL);
279  if (__kmp_test_lock(node->dn.mtx_locks[i], gtid))
280  continue;
281  // could not get the lock, release previous locks
282  for (int j = i - 1; j >= 0; --j)
283  __kmp_release_lock(node->dn.mtx_locks[j], gtid);
284  return false;
285  }
286  // negative num_locks means all locks acquired successfully
287  node->dn.mtx_num_locks = -node->dn.mtx_num_locks;
288  }
289  return true;
290 }
291 
292 // __kmp_realloc_task_deque:
293 // Re-allocates a task deque for a particular thread, copies the content from
294 // the old deque and adjusts the necessary data structures relating to the
295 // deque. This operation must be done with the deque_lock being held
296 static void __kmp_realloc_task_deque(kmp_info_t *thread,
297  kmp_thread_data_t *thread_data) {
298  kmp_int32 size = TASK_DEQUE_SIZE(thread_data->td);
299  KMP_DEBUG_ASSERT(TCR_4(thread_data->td.td_deque_ntasks) == size);
300  kmp_int32 new_size = 2 * size;
301 
302  KE_TRACE(10, ("__kmp_realloc_task_deque: T#%d reallocating deque[from %d to "
303  "%d] for thread_data %p\n",
304  __kmp_gtid_from_thread(thread), size, new_size, thread_data));
305 
306  kmp_taskdata_t **new_deque =
307  (kmp_taskdata_t **)__kmp_allocate(new_size * sizeof(kmp_taskdata_t *));
308 
309  int i, j;
310  for (i = thread_data->td.td_deque_head, j = 0; j < size;
311  i = (i + 1) & TASK_DEQUE_MASK(thread_data->td), j++)
312  new_deque[j] = thread_data->td.td_deque[i];
313 
314  __kmp_free(thread_data->td.td_deque);
315 
316  thread_data->td.td_deque_head = 0;
317  thread_data->td.td_deque_tail = size;
318  thread_data->td.td_deque = new_deque;
319  thread_data->td.td_deque_size = new_size;
320 }
321 
322 // __kmp_push_task: Add a task to the thread's deque
323 static kmp_int32 __kmp_push_task(kmp_int32 gtid, kmp_task_t *task) {
324  kmp_info_t *thread = __kmp_threads[gtid];
325  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(task);
326 
327  // We don't need to map to shadow gtid if it is already hidden helper thread
328  if (taskdata->td_flags.hidden_helper && !KMP_HIDDEN_HELPER_THREAD(gtid)) {
329  gtid = KMP_GTID_TO_SHADOW_GTID(gtid);
330  thread = __kmp_threads[gtid];
331  }
332 
333  kmp_task_team_t *task_team = thread->th.th_task_team;
334  kmp_int32 tid = __kmp_tid_from_gtid(gtid);
335  kmp_thread_data_t *thread_data;
336 
337  KA_TRACE(20,
338  ("__kmp_push_task: T#%d trying to push task %p.\n", gtid, taskdata));
339 
340  if (UNLIKELY(taskdata->td_flags.tiedness == TASK_UNTIED)) {
341  // untied task needs to increment counter so that the task structure is not
342  // freed prematurely
343  kmp_int32 counter = 1 + KMP_ATOMIC_INC(&taskdata->td_untied_count);
344  KMP_DEBUG_USE_VAR(counter);
345  KA_TRACE(
346  20,
347  ("__kmp_push_task: T#%d untied_count (%d) incremented for task %p\n",
348  gtid, counter, taskdata));
349  }
350 
351  // The first check avoids building task_team thread data if serialized
352  if (UNLIKELY(taskdata->td_flags.task_serial)) {
353  KA_TRACE(20, ("__kmp_push_task: T#%d team serialized; returning "
354  "TASK_NOT_PUSHED for task %p\n",
355  gtid, taskdata));
356  return TASK_NOT_PUSHED;
357  }
358 
359  // Now that serialized tasks have returned, we can assume that we are not in
360  // immediate exec mode
361  KMP_DEBUG_ASSERT(__kmp_tasking_mode != tskm_immediate_exec);
362  if (UNLIKELY(!KMP_TASKING_ENABLED(task_team))) {
363  __kmp_enable_tasking(task_team, thread);
364  }
365  KMP_DEBUG_ASSERT(TCR_4(task_team->tt.tt_found_tasks) == TRUE);
366  KMP_DEBUG_ASSERT(TCR_PTR(task_team->tt.tt_threads_data) != NULL);
367 
368  // Find tasking deque specific to encountering thread
369  thread_data = &task_team->tt.tt_threads_data[tid];
370 
371  // No lock needed since only owner can allocate. If the task is hidden_helper,
372  // we don't need it either because we have initialized the dequeue for hidden
373  // helper thread data.
374  if (UNLIKELY(thread_data->td.td_deque == NULL)) {
375  __kmp_alloc_task_deque(thread, thread_data);
376  }
377 
378  int locked = 0;
379  // Check if deque is full
380  if (TCR_4(thread_data->td.td_deque_ntasks) >=
381  TASK_DEQUE_SIZE(thread_data->td)) {
382  if (__kmp_enable_task_throttling &&
383  __kmp_task_is_allowed(gtid, __kmp_task_stealing_constraint, taskdata,
384  thread->th.th_current_task)) {
385  KA_TRACE(20, ("__kmp_push_task: T#%d deque is full; returning "
386  "TASK_NOT_PUSHED for task %p\n",
387  gtid, taskdata));
388  return TASK_NOT_PUSHED;
389  } else {
390  __kmp_acquire_bootstrap_lock(&thread_data->td.td_deque_lock);
391  locked = 1;
392  if (TCR_4(thread_data->td.td_deque_ntasks) >=
393  TASK_DEQUE_SIZE(thread_data->td)) {
394  // expand deque to push the task which is not allowed to execute
395  __kmp_realloc_task_deque(thread, thread_data);
396  }
397  }
398  }
399  // Lock the deque for the task push operation
400  if (!locked) {
401  __kmp_acquire_bootstrap_lock(&thread_data->td.td_deque_lock);
402  // Need to recheck as we can get a proxy task from thread outside of OpenMP
403  if (TCR_4(thread_data->td.td_deque_ntasks) >=
404  TASK_DEQUE_SIZE(thread_data->td)) {
405  if (__kmp_enable_task_throttling &&
406  __kmp_task_is_allowed(gtid, __kmp_task_stealing_constraint, taskdata,
407  thread->th.th_current_task)) {
408  __kmp_release_bootstrap_lock(&thread_data->td.td_deque_lock);
409  KA_TRACE(20, ("__kmp_push_task: T#%d deque is full on 2nd check; "
410  "returning TASK_NOT_PUSHED for task %p\n",
411  gtid, taskdata));
412  return TASK_NOT_PUSHED;
413  } else {
414  // expand deque to push the task which is not allowed to execute
415  __kmp_realloc_task_deque(thread, thread_data);
416  }
417  }
418  }
419  // Must have room since no thread can add tasks but calling thread
420  KMP_DEBUG_ASSERT(TCR_4(thread_data->td.td_deque_ntasks) <
421  TASK_DEQUE_SIZE(thread_data->td));
422 
423  thread_data->td.td_deque[thread_data->td.td_deque_tail] =
424  taskdata; // Push taskdata
425  // Wrap index.
426  thread_data->td.td_deque_tail =
427  (thread_data->td.td_deque_tail + 1) & TASK_DEQUE_MASK(thread_data->td);
428  TCW_4(thread_data->td.td_deque_ntasks,
429  TCR_4(thread_data->td.td_deque_ntasks) + 1); // Adjust task count
430  KMP_FSYNC_RELEASING(thread->th.th_current_task); // releasing self
431  KMP_FSYNC_RELEASING(taskdata); // releasing child
432  KA_TRACE(20, ("__kmp_push_task: T#%d returning TASK_SUCCESSFULLY_PUSHED: "
433  "task=%p ntasks=%d head=%u tail=%u\n",
434  gtid, taskdata, thread_data->td.td_deque_ntasks,
435  thread_data->td.td_deque_head, thread_data->td.td_deque_tail));
436 
437  auto hidden_helper = taskdata->td_flags.hidden_helper;
438 
439  __kmp_release_bootstrap_lock(&thread_data->td.td_deque_lock);
440 
441  // Signal one worker thread to execute the task
442  if (UNLIKELY(hidden_helper)) {
443  // Wake hidden helper threads up if they're sleeping
444  __kmp_hidden_helper_worker_thread_signal();
445  }
446 
447  return TASK_SUCCESSFULLY_PUSHED;
448 }
449 
450 // __kmp_pop_current_task_from_thread: set up current task from called thread
451 // when team ends
452 //
453 // this_thr: thread structure to set current_task in.
454 void __kmp_pop_current_task_from_thread(kmp_info_t *this_thr) {
455  KF_TRACE(10, ("__kmp_pop_current_task_from_thread(enter): T#%d "
456  "this_thread=%p, curtask=%p, "
457  "curtask_parent=%p\n",
458  0, this_thr, this_thr->th.th_current_task,
459  this_thr->th.th_current_task->td_parent));
460 
461  this_thr->th.th_current_task = this_thr->th.th_current_task->td_parent;
462 
463  KF_TRACE(10, ("__kmp_pop_current_task_from_thread(exit): T#%d "
464  "this_thread=%p, curtask=%p, "
465  "curtask_parent=%p\n",
466  0, this_thr, this_thr->th.th_current_task,
467  this_thr->th.th_current_task->td_parent));
468 }
469 
470 // __kmp_push_current_task_to_thread: set up current task in called thread for a
471 // new team
472 //
473 // this_thr: thread structure to set up
474 // team: team for implicit task data
475 // tid: thread within team to set up
476 void __kmp_push_current_task_to_thread(kmp_info_t *this_thr, kmp_team_t *team,
477  int tid) {
478  // current task of the thread is a parent of the new just created implicit
479  // tasks of new team
480  KF_TRACE(10, ("__kmp_push_current_task_to_thread(enter): T#%d this_thread=%p "
481  "curtask=%p "
482  "parent_task=%p\n",
483  tid, this_thr, this_thr->th.th_current_task,
484  team->t.t_implicit_task_taskdata[tid].td_parent));
485 
486  KMP_DEBUG_ASSERT(this_thr != NULL);
487 
488  if (tid == 0) {
489  if (this_thr->th.th_current_task != &team->t.t_implicit_task_taskdata[0]) {
490  team->t.t_implicit_task_taskdata[0].td_parent =
491  this_thr->th.th_current_task;
492  this_thr->th.th_current_task = &team->t.t_implicit_task_taskdata[0];
493  }
494  } else {
495  team->t.t_implicit_task_taskdata[tid].td_parent =
496  team->t.t_implicit_task_taskdata[0].td_parent;
497  this_thr->th.th_current_task = &team->t.t_implicit_task_taskdata[tid];
498  }
499 
500  KF_TRACE(10, ("__kmp_push_current_task_to_thread(exit): T#%d this_thread=%p "
501  "curtask=%p "
502  "parent_task=%p\n",
503  tid, this_thr, this_thr->th.th_current_task,
504  team->t.t_implicit_task_taskdata[tid].td_parent));
505 }
506 
507 // __kmp_task_start: bookkeeping for a task starting execution
508 //
509 // GTID: global thread id of calling thread
510 // task: task starting execution
511 // current_task: task suspending
512 static void __kmp_task_start(kmp_int32 gtid, kmp_task_t *task,
513  kmp_taskdata_t *current_task) {
514  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(task);
515  kmp_info_t *thread = __kmp_threads[gtid];
516 
517  KA_TRACE(10,
518  ("__kmp_task_start(enter): T#%d starting task %p: current_task=%p\n",
519  gtid, taskdata, current_task));
520 
521  KMP_DEBUG_ASSERT(taskdata->td_flags.tasktype == TASK_EXPLICIT);
522 
523  // mark currently executing task as suspended
524  // TODO: GEH - make sure root team implicit task is initialized properly.
525  // KMP_DEBUG_ASSERT( current_task -> td_flags.executing == 1 );
526  current_task->td_flags.executing = 0;
527 
528 // Add task to stack if tied
529 #ifdef BUILD_TIED_TASK_STACK
530  if (taskdata->td_flags.tiedness == TASK_TIED) {
531  __kmp_push_task_stack(gtid, thread, taskdata);
532  }
533 #endif /* BUILD_TIED_TASK_STACK */
534 
535  // mark starting task as executing and as current task
536  thread->th.th_current_task = taskdata;
537 
538  KMP_DEBUG_ASSERT(taskdata->td_flags.started == 0 ||
539  taskdata->td_flags.tiedness == TASK_UNTIED);
540  KMP_DEBUG_ASSERT(taskdata->td_flags.executing == 0 ||
541  taskdata->td_flags.tiedness == TASK_UNTIED);
542  taskdata->td_flags.started = 1;
543  taskdata->td_flags.executing = 1;
544  KMP_DEBUG_ASSERT(taskdata->td_flags.complete == 0);
545  KMP_DEBUG_ASSERT(taskdata->td_flags.freed == 0);
546 
547  // GEH TODO: shouldn't we pass some sort of location identifier here?
548  // APT: yes, we will pass location here.
549  // need to store current thread state (in a thread or taskdata structure)
550  // before setting work_state, otherwise wrong state is set after end of task
551 
552  KA_TRACE(10, ("__kmp_task_start(exit): T#%d task=%p\n", gtid, taskdata));
553 
554  return;
555 }
556 
557 #if OMPT_SUPPORT
558 //------------------------------------------------------------------------------
559 // __ompt_task_init:
560 // Initialize OMPT fields maintained by a task. This will only be called after
561 // ompt_start_tool, so we already know whether ompt is enabled or not.
562 
563 static inline void __ompt_task_init(kmp_taskdata_t *task, int tid) {
564  // The calls to __ompt_task_init already have the ompt_enabled condition.
565  task->ompt_task_info.task_data.value = 0;
566  task->ompt_task_info.frame.exit_frame = ompt_data_none;
567  task->ompt_task_info.frame.enter_frame = ompt_data_none;
568  task->ompt_task_info.frame.exit_frame_flags =
569  ompt_frame_runtime | ompt_frame_framepointer;
570  task->ompt_task_info.frame.enter_frame_flags =
571  ompt_frame_runtime | ompt_frame_framepointer;
572 }
573 
574 // __ompt_task_start:
575 // Build and trigger task-begin event
576 static inline void __ompt_task_start(kmp_task_t *task,
577  kmp_taskdata_t *current_task,
578  kmp_int32 gtid) {
579  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(task);
580  ompt_task_status_t status = ompt_task_switch;
581  if (__kmp_threads[gtid]->th.ompt_thread_info.ompt_task_yielded) {
582  status = ompt_task_yield;
583  __kmp_threads[gtid]->th.ompt_thread_info.ompt_task_yielded = 0;
584  }
585  /* let OMPT know that we're about to run this task */
586  if (ompt_enabled.ompt_callback_task_schedule) {
587  ompt_callbacks.ompt_callback(ompt_callback_task_schedule)(
588  &(current_task->ompt_task_info.task_data), status,
589  &(taskdata->ompt_task_info.task_data));
590  }
591  taskdata->ompt_task_info.scheduling_parent = current_task;
592 }
593 
594 // __ompt_task_finish:
595 // Build and trigger final task-schedule event
596 static inline void __ompt_task_finish(kmp_task_t *task,
597  kmp_taskdata_t *resumed_task,
598  ompt_task_status_t status) {
599  if (ompt_enabled.ompt_callback_task_schedule) {
600  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(task);
601  if (__kmp_omp_cancellation && taskdata->td_taskgroup &&
602  taskdata->td_taskgroup->cancel_request == cancel_taskgroup) {
603  status = ompt_task_cancel;
604  }
605 
606  /* let OMPT know that we're returning to the callee task */
607  ompt_callbacks.ompt_callback(ompt_callback_task_schedule)(
608  &(taskdata->ompt_task_info.task_data), status,
609  (resumed_task ? &(resumed_task->ompt_task_info.task_data) : NULL));
610  }
611 }
612 #endif
613 
614 template <bool ompt>
615 static void __kmpc_omp_task_begin_if0_template(ident_t *loc_ref, kmp_int32 gtid,
616  kmp_task_t *task,
617  void *frame_address,
618  void *return_address) {
619  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(task);
620  kmp_taskdata_t *current_task = __kmp_threads[gtid]->th.th_current_task;
621 
622  KA_TRACE(10, ("__kmpc_omp_task_begin_if0(enter): T#%d loc=%p task=%p "
623  "current_task=%p\n",
624  gtid, loc_ref, taskdata, current_task));
625 
626  if (UNLIKELY(taskdata->td_flags.tiedness == TASK_UNTIED)) {
627  // untied task needs to increment counter so that the task structure is not
628  // freed prematurely
629  kmp_int32 counter = 1 + KMP_ATOMIC_INC(&taskdata->td_untied_count);
630  KMP_DEBUG_USE_VAR(counter);
631  KA_TRACE(20, ("__kmpc_omp_task_begin_if0: T#%d untied_count (%d) "
632  "incremented for task %p\n",
633  gtid, counter, taskdata));
634  }
635 
636  taskdata->td_flags.task_serial =
637  1; // Execute this task immediately, not deferred.
638  __kmp_task_start(gtid, task, current_task);
639 
640 #if OMPT_SUPPORT
641  if (ompt) {
642  if (current_task->ompt_task_info.frame.enter_frame.ptr == NULL) {
643  current_task->ompt_task_info.frame.enter_frame.ptr =
644  taskdata->ompt_task_info.frame.exit_frame.ptr = frame_address;
645  current_task->ompt_task_info.frame.enter_frame_flags =
646  taskdata->ompt_task_info.frame.exit_frame_flags =
647  ompt_frame_application | ompt_frame_framepointer;
648  }
649  if (ompt_enabled.ompt_callback_task_create) {
650  ompt_task_info_t *parent_info = &(current_task->ompt_task_info);
651  ompt_callbacks.ompt_callback(ompt_callback_task_create)(
652  &(parent_info->task_data), &(parent_info->frame),
653  &(taskdata->ompt_task_info.task_data),
654  ompt_task_explicit | TASK_TYPE_DETAILS_FORMAT(taskdata), 0,
655  return_address);
656  }
657  __ompt_task_start(task, current_task, gtid);
658  }
659 #endif // OMPT_SUPPORT
660 
661  KA_TRACE(10, ("__kmpc_omp_task_begin_if0(exit): T#%d loc=%p task=%p,\n", gtid,
662  loc_ref, taskdata));
663 }
664 
665 #if OMPT_SUPPORT
666 OMPT_NOINLINE
667 static void __kmpc_omp_task_begin_if0_ompt(ident_t *loc_ref, kmp_int32 gtid,
668  kmp_task_t *task,
669  void *frame_address,
670  void *return_address) {
671  __kmpc_omp_task_begin_if0_template<true>(loc_ref, gtid, task, frame_address,
672  return_address);
673 }
674 #endif // OMPT_SUPPORT
675 
676 // __kmpc_omp_task_begin_if0: report that a given serialized task has started
677 // execution
678 //
679 // loc_ref: source location information; points to beginning of task block.
680 // gtid: global thread number.
681 // task: task thunk for the started task.
682 void __kmpc_omp_task_begin_if0(ident_t *loc_ref, kmp_int32 gtid,
683  kmp_task_t *task) {
684 #if OMPT_SUPPORT
685  if (UNLIKELY(ompt_enabled.enabled)) {
686  OMPT_STORE_RETURN_ADDRESS(gtid);
687  __kmpc_omp_task_begin_if0_ompt(loc_ref, gtid, task,
688  OMPT_GET_FRAME_ADDRESS(1),
689  OMPT_LOAD_RETURN_ADDRESS(gtid));
690  return;
691  }
692 #endif
693  __kmpc_omp_task_begin_if0_template<false>(loc_ref, gtid, task, NULL, NULL);
694 }
695 
696 #ifdef TASK_UNUSED
697 // __kmpc_omp_task_begin: report that a given task has started execution
698 // NEVER GENERATED BY COMPILER, DEPRECATED!!!
699 void __kmpc_omp_task_begin(ident_t *loc_ref, kmp_int32 gtid, kmp_task_t *task) {
700  kmp_taskdata_t *current_task = __kmp_threads[gtid]->th.th_current_task;
701 
702  KA_TRACE(
703  10,
704  ("__kmpc_omp_task_begin(enter): T#%d loc=%p task=%p current_task=%p\n",
705  gtid, loc_ref, KMP_TASK_TO_TASKDATA(task), current_task));
706 
707  __kmp_task_start(gtid, task, current_task);
708 
709  KA_TRACE(10, ("__kmpc_omp_task_begin(exit): T#%d loc=%p task=%p,\n", gtid,
710  loc_ref, KMP_TASK_TO_TASKDATA(task)));
711  return;
712 }
713 #endif // TASK_UNUSED
714 
715 // __kmp_free_task: free the current task space and the space for shareds
716 //
717 // gtid: Global thread ID of calling thread
718 // taskdata: task to free
719 // thread: thread data structure of caller
720 static void __kmp_free_task(kmp_int32 gtid, kmp_taskdata_t *taskdata,
721  kmp_info_t *thread) {
722  KA_TRACE(30, ("__kmp_free_task: T#%d freeing data from task %p\n", gtid,
723  taskdata));
724 
725  // Check to make sure all flags and counters have the correct values
726  KMP_DEBUG_ASSERT(taskdata->td_flags.tasktype == TASK_EXPLICIT);
727  KMP_DEBUG_ASSERT(taskdata->td_flags.executing == 0);
728  KMP_DEBUG_ASSERT(taskdata->td_flags.complete == 1);
729  KMP_DEBUG_ASSERT(taskdata->td_flags.freed == 0);
730  KMP_DEBUG_ASSERT(taskdata->td_allocated_child_tasks == 0 ||
731  taskdata->td_flags.task_serial == 1);
732  KMP_DEBUG_ASSERT(taskdata->td_incomplete_child_tasks == 0);
733 
734  taskdata->td_flags.freed = 1;
735 // deallocate the taskdata and shared variable blocks associated with this task
736 #if USE_FAST_MEMORY
737  __kmp_fast_free(thread, taskdata);
738 #else /* ! USE_FAST_MEMORY */
739  __kmp_thread_free(thread, taskdata);
740 #endif
741  KA_TRACE(20, ("__kmp_free_task: T#%d freed task %p\n", gtid, taskdata));
742 }
743 
744 // __kmp_free_task_and_ancestors: free the current task and ancestors without
745 // children
746 //
747 // gtid: Global thread ID of calling thread
748 // taskdata: task to free
749 // thread: thread data structure of caller
750 static void __kmp_free_task_and_ancestors(kmp_int32 gtid,
751  kmp_taskdata_t *taskdata,
752  kmp_info_t *thread) {
753  // Proxy tasks must always be allowed to free their parents
754  // because they can be run in background even in serial mode.
755  kmp_int32 team_serial =
756  (taskdata->td_flags.team_serial || taskdata->td_flags.tasking_ser) &&
757  !taskdata->td_flags.proxy;
758  KMP_DEBUG_ASSERT(taskdata->td_flags.tasktype == TASK_EXPLICIT);
759 
760  kmp_int32 children = KMP_ATOMIC_DEC(&taskdata->td_allocated_child_tasks) - 1;
761  KMP_DEBUG_ASSERT(children >= 0);
762 
763  // Now, go up the ancestor tree to see if any ancestors can now be freed.
764  while (children == 0) {
765  kmp_taskdata_t *parent_taskdata = taskdata->td_parent;
766 
767  KA_TRACE(20, ("__kmp_free_task_and_ancestors(enter): T#%d task %p complete "
768  "and freeing itself\n",
769  gtid, taskdata));
770 
771  // --- Deallocate my ancestor task ---
772  __kmp_free_task(gtid, taskdata, thread);
773 
774  taskdata = parent_taskdata;
775 
776  if (team_serial)
777  return;
778  // Stop checking ancestors at implicit task instead of walking up ancestor
779  // tree to avoid premature deallocation of ancestors.
780  if (taskdata->td_flags.tasktype == TASK_IMPLICIT) {
781  if (taskdata->td_dephash) { // do we need to cleanup dephash?
782  int children = KMP_ATOMIC_LD_ACQ(&taskdata->td_incomplete_child_tasks);
783  kmp_tasking_flags_t flags_old = taskdata->td_flags;
784  if (children == 0 && flags_old.complete == 1) {
785  kmp_tasking_flags_t flags_new = flags_old;
786  flags_new.complete = 0;
787  if (KMP_COMPARE_AND_STORE_ACQ32(
788  RCAST(kmp_int32 *, &taskdata->td_flags),
789  *RCAST(kmp_int32 *, &flags_old),
790  *RCAST(kmp_int32 *, &flags_new))) {
791  KA_TRACE(100, ("__kmp_free_task_and_ancestors: T#%d cleans "
792  "dephash of implicit task %p\n",
793  gtid, taskdata));
794  // cleanup dephash of finished implicit task
795  __kmp_dephash_free_entries(thread, taskdata->td_dephash);
796  }
797  }
798  }
799  return;
800  }
801  // Predecrement simulated by "- 1" calculation
802  children = KMP_ATOMIC_DEC(&taskdata->td_allocated_child_tasks) - 1;
803  KMP_DEBUG_ASSERT(children >= 0);
804  }
805 
806  KA_TRACE(
807  20, ("__kmp_free_task_and_ancestors(exit): T#%d task %p has %d children; "
808  "not freeing it yet\n",
809  gtid, taskdata, children));
810 }
811 
812 // __kmp_task_finish: bookkeeping to do when a task finishes execution
813 //
814 // gtid: global thread ID for calling thread
815 // task: task to be finished
816 // resumed_task: task to be resumed. (may be NULL if task is serialized)
817 //
818 // template<ompt>: effectively ompt_enabled.enabled!=0
819 // the version with ompt=false is inlined, allowing to optimize away all ompt
820 // code in this case
821 template <bool ompt>
822 static void __kmp_task_finish(kmp_int32 gtid, kmp_task_t *task,
823  kmp_taskdata_t *resumed_task) {
824  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(task);
825  kmp_info_t *thread = __kmp_threads[gtid];
826  kmp_task_team_t *task_team =
827  thread->th.th_task_team; // might be NULL for serial teams...
828  kmp_int32 children = 0;
829 
830  KA_TRACE(10, ("__kmp_task_finish(enter): T#%d finishing task %p and resuming "
831  "task %p\n",
832  gtid, taskdata, resumed_task));
833 
834  KMP_DEBUG_ASSERT(taskdata->td_flags.tasktype == TASK_EXPLICIT);
835 
836 // Pop task from stack if tied
837 #ifdef BUILD_TIED_TASK_STACK
838  if (taskdata->td_flags.tiedness == TASK_TIED) {
839  __kmp_pop_task_stack(gtid, thread, taskdata);
840  }
841 #endif /* BUILD_TIED_TASK_STACK */
842 
843  if (UNLIKELY(taskdata->td_flags.tiedness == TASK_UNTIED)) {
844  // untied task needs to check the counter so that the task structure is not
845  // freed prematurely
846  kmp_int32 counter = KMP_ATOMIC_DEC(&taskdata->td_untied_count) - 1;
847  KA_TRACE(
848  20,
849  ("__kmp_task_finish: T#%d untied_count (%d) decremented for task %p\n",
850  gtid, counter, taskdata));
851  if (counter > 0) {
852  // untied task is not done, to be continued possibly by other thread, do
853  // not free it now
854  if (resumed_task == NULL) {
855  KMP_DEBUG_ASSERT(taskdata->td_flags.task_serial);
856  resumed_task = taskdata->td_parent; // In a serialized task, the resumed
857  // task is the parent
858  }
859  thread->th.th_current_task = resumed_task; // restore current_task
860  resumed_task->td_flags.executing = 1; // resume previous task
861  KA_TRACE(10, ("__kmp_task_finish(exit): T#%d partially done task %p, "
862  "resuming task %p\n",
863  gtid, taskdata, resumed_task));
864  return;
865  }
866  }
867 
868  // bookkeeping for resuming task:
869  // GEH - note tasking_ser => task_serial
870  KMP_DEBUG_ASSERT(
871  (taskdata->td_flags.tasking_ser || taskdata->td_flags.task_serial) ==
872  taskdata->td_flags.task_serial);
873  if (taskdata->td_flags.task_serial) {
874  if (resumed_task == NULL) {
875  resumed_task = taskdata->td_parent; // In a serialized task, the resumed
876  // task is the parent
877  }
878  } else {
879  KMP_DEBUG_ASSERT(resumed_task !=
880  NULL); // verify that resumed task is passed as argument
881  }
882 
883  /* If the tasks' destructor thunk flag has been set, we need to invoke the
884  destructor thunk that has been generated by the compiler. The code is
885  placed here, since at this point other tasks might have been released
886  hence overlapping the destructor invocations with some other work in the
887  released tasks. The OpenMP spec is not specific on when the destructors
888  are invoked, so we should be free to choose. */
889  if (UNLIKELY(taskdata->td_flags.destructors_thunk)) {
890  kmp_routine_entry_t destr_thunk = task->data1.destructors;
891  KMP_ASSERT(destr_thunk);
892  destr_thunk(gtid, task);
893  }
894 
895  KMP_DEBUG_ASSERT(taskdata->td_flags.complete == 0);
896  KMP_DEBUG_ASSERT(taskdata->td_flags.started == 1);
897  KMP_DEBUG_ASSERT(taskdata->td_flags.freed == 0);
898 
899  bool detach = false;
900  if (UNLIKELY(taskdata->td_flags.detachable == TASK_DETACHABLE)) {
901  if (taskdata->td_allow_completion_event.type ==
902  KMP_EVENT_ALLOW_COMPLETION) {
903  // event hasn't been fulfilled yet. Try to detach task.
904  __kmp_acquire_tas_lock(&taskdata->td_allow_completion_event.lock, gtid);
905  if (taskdata->td_allow_completion_event.type ==
906  KMP_EVENT_ALLOW_COMPLETION) {
907  // task finished execution
908  KMP_DEBUG_ASSERT(taskdata->td_flags.executing == 1);
909  taskdata->td_flags.executing = 0; // suspend the finishing task
910 
911 #if OMPT_SUPPORT
912  // For a detached task, which is not completed, we switch back
913  // the omp_fulfill_event signals completion
914  // locking is necessary to avoid a race with ompt_task_late_fulfill
915  if (ompt)
916  __ompt_task_finish(task, resumed_task, ompt_task_detach);
917 #endif
918 
919  // no access to taskdata after this point!
920  // __kmp_fulfill_event might free taskdata at any time from now
921 
922  taskdata->td_flags.proxy = TASK_PROXY; // proxify!
923  detach = true;
924  }
925  __kmp_release_tas_lock(&taskdata->td_allow_completion_event.lock, gtid);
926  }
927  }
928 
929  if (!detach) {
930  taskdata->td_flags.complete = 1; // mark the task as completed
931 
932 #if OMPT_SUPPORT
933  // This is not a detached task, we are done here
934  if (ompt)
935  __ompt_task_finish(task, resumed_task, ompt_task_complete);
936 #endif
937 
938  // Only need to keep track of count if team parallel and tasking not
939  // serialized, or task is detachable and event has already been fulfilled
940  if (!(taskdata->td_flags.team_serial || taskdata->td_flags.tasking_ser) ||
941  taskdata->td_flags.detachable == TASK_DETACHABLE ||
942  taskdata->td_flags.hidden_helper) {
943  __kmp_release_deps(gtid, taskdata);
944  // Predecrement simulated by "- 1" calculation
945  children =
946  KMP_ATOMIC_DEC(&taskdata->td_parent->td_incomplete_child_tasks) - 1;
947  KMP_DEBUG_ASSERT(children >= 0);
948  if (taskdata->td_taskgroup)
949  KMP_ATOMIC_DEC(&taskdata->td_taskgroup->count);
950  } else if (task_team && (task_team->tt.tt_found_proxy_tasks ||
951  task_team->tt.tt_hidden_helper_task_encountered)) {
952  // if we found proxy or hidden helper tasks there could exist a dependency
953  // chain with the proxy task as origin
954  __kmp_release_deps(gtid, taskdata);
955  }
956  // td_flags.executing must be marked as 0 after __kmp_release_deps has been
957  // called. Othertwise, if a task is executed immediately from the
958  // release_deps code, the flag will be reset to 1 again by this same
959  // function
960  KMP_DEBUG_ASSERT(taskdata->td_flags.executing == 1);
961  taskdata->td_flags.executing = 0; // suspend the finishing task
962  }
963 
964  KA_TRACE(
965  20, ("__kmp_task_finish: T#%d finished task %p, %d incomplete children\n",
966  gtid, taskdata, children));
967 
968  // Free this task and then ancestor tasks if they have no children.
969  // Restore th_current_task first as suggested by John:
970  // johnmc: if an asynchronous inquiry peers into the runtime system
971  // it doesn't see the freed task as the current task.
972  thread->th.th_current_task = resumed_task;
973  if (!detach)
974  __kmp_free_task_and_ancestors(gtid, taskdata, thread);
975 
976  // TODO: GEH - make sure root team implicit task is initialized properly.
977  // KMP_DEBUG_ASSERT( resumed_task->td_flags.executing == 0 );
978  resumed_task->td_flags.executing = 1; // resume previous task
979 
980  KA_TRACE(
981  10, ("__kmp_task_finish(exit): T#%d finished task %p, resuming task %p\n",
982  gtid, taskdata, resumed_task));
983 
984  return;
985 }
986 
987 template <bool ompt>
988 static void __kmpc_omp_task_complete_if0_template(ident_t *loc_ref,
989  kmp_int32 gtid,
990  kmp_task_t *task) {
991  KA_TRACE(10, ("__kmpc_omp_task_complete_if0(enter): T#%d loc=%p task=%p\n",
992  gtid, loc_ref, KMP_TASK_TO_TASKDATA(task)));
993  KMP_DEBUG_ASSERT(gtid >= 0);
994  // this routine will provide task to resume
995  __kmp_task_finish<ompt>(gtid, task, NULL);
996 
997  KA_TRACE(10, ("__kmpc_omp_task_complete_if0(exit): T#%d loc=%p task=%p\n",
998  gtid, loc_ref, KMP_TASK_TO_TASKDATA(task)));
999 
1000 #if OMPT_SUPPORT
1001  if (ompt) {
1002  ompt_frame_t *ompt_frame;
1003  __ompt_get_task_info_internal(0, NULL, NULL, &ompt_frame, NULL, NULL);
1004  ompt_frame->enter_frame = ompt_data_none;
1005  ompt_frame->enter_frame_flags =
1006  ompt_frame_runtime | ompt_frame_framepointer;
1007  }
1008 #endif
1009 
1010  return;
1011 }
1012 
1013 #if OMPT_SUPPORT
1014 OMPT_NOINLINE
1015 void __kmpc_omp_task_complete_if0_ompt(ident_t *loc_ref, kmp_int32 gtid,
1016  kmp_task_t *task) {
1017  __kmpc_omp_task_complete_if0_template<true>(loc_ref, gtid, task);
1018 }
1019 #endif // OMPT_SUPPORT
1020 
1021 // __kmpc_omp_task_complete_if0: report that a task has completed execution
1022 //
1023 // loc_ref: source location information; points to end of task block.
1024 // gtid: global thread number.
1025 // task: task thunk for the completed task.
1026 void __kmpc_omp_task_complete_if0(ident_t *loc_ref, kmp_int32 gtid,
1027  kmp_task_t *task) {
1028 #if OMPT_SUPPORT
1029  if (UNLIKELY(ompt_enabled.enabled)) {
1030  __kmpc_omp_task_complete_if0_ompt(loc_ref, gtid, task);
1031  return;
1032  }
1033 #endif
1034  __kmpc_omp_task_complete_if0_template<false>(loc_ref, gtid, task);
1035 }
1036 
1037 #ifdef TASK_UNUSED
1038 // __kmpc_omp_task_complete: report that a task has completed execution
1039 // NEVER GENERATED BY COMPILER, DEPRECATED!!!
1040 void __kmpc_omp_task_complete(ident_t *loc_ref, kmp_int32 gtid,
1041  kmp_task_t *task) {
1042  KA_TRACE(10, ("__kmpc_omp_task_complete(enter): T#%d loc=%p task=%p\n", gtid,
1043  loc_ref, KMP_TASK_TO_TASKDATA(task)));
1044 
1045  __kmp_task_finish<false>(gtid, task,
1046  NULL); // Not sure how to find task to resume
1047 
1048  KA_TRACE(10, ("__kmpc_omp_task_complete(exit): T#%d loc=%p task=%p\n", gtid,
1049  loc_ref, KMP_TASK_TO_TASKDATA(task)));
1050  return;
1051 }
1052 #endif // TASK_UNUSED
1053 
1054 // __kmp_init_implicit_task: Initialize the appropriate fields in the implicit
1055 // task for a given thread
1056 //
1057 // loc_ref: reference to source location of parallel region
1058 // this_thr: thread data structure corresponding to implicit task
1059 // team: team for this_thr
1060 // tid: thread id of given thread within team
1061 // set_curr_task: TRUE if need to push current task to thread
1062 // NOTE: Routine does not set up the implicit task ICVS. This is assumed to
1063 // have already been done elsewhere.
1064 // TODO: Get better loc_ref. Value passed in may be NULL
1065 void __kmp_init_implicit_task(ident_t *loc_ref, kmp_info_t *this_thr,
1066  kmp_team_t *team, int tid, int set_curr_task) {
1067  kmp_taskdata_t *task = &team->t.t_implicit_task_taskdata[tid];
1068 
1069  KF_TRACE(
1070  10,
1071  ("__kmp_init_implicit_task(enter): T#:%d team=%p task=%p, reinit=%s\n",
1072  tid, team, task, set_curr_task ? "TRUE" : "FALSE"));
1073 
1074  task->td_task_id = KMP_GEN_TASK_ID();
1075  task->td_team = team;
1076  // task->td_parent = NULL; // fix for CQ230101 (broken parent task info
1077  // in debugger)
1078  task->td_ident = loc_ref;
1079  task->td_taskwait_ident = NULL;
1080  task->td_taskwait_counter = 0;
1081  task->td_taskwait_thread = 0;
1082 
1083  task->td_flags.tiedness = TASK_TIED;
1084  task->td_flags.tasktype = TASK_IMPLICIT;
1085  task->td_flags.proxy = TASK_FULL;
1086 
1087  // All implicit tasks are executed immediately, not deferred
1088  task->td_flags.task_serial = 1;
1089  task->td_flags.tasking_ser = (__kmp_tasking_mode == tskm_immediate_exec);
1090  task->td_flags.team_serial = (team->t.t_serialized) ? 1 : 0;
1091 
1092  task->td_flags.started = 1;
1093  task->td_flags.executing = 1;
1094  task->td_flags.complete = 0;
1095  task->td_flags.freed = 0;
1096 
1097  task->td_depnode = NULL;
1098  task->td_last_tied = task;
1099  task->td_allow_completion_event.type = KMP_EVENT_UNINITIALIZED;
1100 
1101  if (set_curr_task) { // only do this init first time thread is created
1102  KMP_ATOMIC_ST_REL(&task->td_incomplete_child_tasks, 0);
1103  // Not used: don't need to deallocate implicit task
1104  KMP_ATOMIC_ST_REL(&task->td_allocated_child_tasks, 0);
1105  task->td_taskgroup = NULL; // An implicit task does not have taskgroup
1106  task->td_dephash = NULL;
1107  __kmp_push_current_task_to_thread(this_thr, team, tid);
1108  } else {
1109  KMP_DEBUG_ASSERT(task->td_incomplete_child_tasks == 0);
1110  KMP_DEBUG_ASSERT(task->td_allocated_child_tasks == 0);
1111  }
1112 
1113 #if OMPT_SUPPORT
1114  if (UNLIKELY(ompt_enabled.enabled))
1115  __ompt_task_init(task, tid);
1116 #endif
1117 
1118  KF_TRACE(10, ("__kmp_init_implicit_task(exit): T#:%d team=%p task=%p\n", tid,
1119  team, task));
1120 }
1121 
1122 // __kmp_finish_implicit_task: Release resources associated to implicit tasks
1123 // at the end of parallel regions. Some resources are kept for reuse in the next
1124 // parallel region.
1125 //
1126 // thread: thread data structure corresponding to implicit task
1127 void __kmp_finish_implicit_task(kmp_info_t *thread) {
1128  kmp_taskdata_t *task = thread->th.th_current_task;
1129  if (task->td_dephash) {
1130  int children;
1131  task->td_flags.complete = 1;
1132  children = KMP_ATOMIC_LD_ACQ(&task->td_incomplete_child_tasks);
1133  kmp_tasking_flags_t flags_old = task->td_flags;
1134  if (children == 0 && flags_old.complete == 1) {
1135  kmp_tasking_flags_t flags_new = flags_old;
1136  flags_new.complete = 0;
1137  if (KMP_COMPARE_AND_STORE_ACQ32(RCAST(kmp_int32 *, &task->td_flags),
1138  *RCAST(kmp_int32 *, &flags_old),
1139  *RCAST(kmp_int32 *, &flags_new))) {
1140  KA_TRACE(100, ("__kmp_finish_implicit_task: T#%d cleans "
1141  "dephash of implicit task %p\n",
1142  thread->th.th_info.ds.ds_gtid, task));
1143  __kmp_dephash_free_entries(thread, task->td_dephash);
1144  }
1145  }
1146  }
1147 }
1148 
1149 // __kmp_free_implicit_task: Release resources associated to implicit tasks
1150 // when these are destroyed regions
1151 //
1152 // thread: thread data structure corresponding to implicit task
1153 void __kmp_free_implicit_task(kmp_info_t *thread) {
1154  kmp_taskdata_t *task = thread->th.th_current_task;
1155  if (task && task->td_dephash) {
1156  __kmp_dephash_free(thread, task->td_dephash);
1157  task->td_dephash = NULL;
1158  }
1159 }
1160 
1161 // Round up a size to a power of two specified by val: Used to insert padding
1162 // between structures co-allocated using a single malloc() call
1163 static size_t __kmp_round_up_to_val(size_t size, size_t val) {
1164  if (size & (val - 1)) {
1165  size &= ~(val - 1);
1166  if (size <= KMP_SIZE_T_MAX - val) {
1167  size += val; // Round up if there is no overflow.
1168  }
1169  }
1170  return size;
1171 } // __kmp_round_up_to_va
1172 
1173 // __kmp_task_alloc: Allocate the taskdata and task data structures for a task
1174 //
1175 // loc_ref: source location information
1176 // gtid: global thread number.
1177 // flags: include tiedness & task type (explicit vs. implicit) of the ''new''
1178 // task encountered. Converted from kmp_int32 to kmp_tasking_flags_t in routine.
1179 // sizeof_kmp_task_t: Size in bytes of kmp_task_t data structure including
1180 // private vars accessed in task.
1181 // sizeof_shareds: Size in bytes of array of pointers to shared vars accessed
1182 // in task.
1183 // task_entry: Pointer to task code entry point generated by compiler.
1184 // returns: a pointer to the allocated kmp_task_t structure (task).
1185 kmp_task_t *__kmp_task_alloc(ident_t *loc_ref, kmp_int32 gtid,
1186  kmp_tasking_flags_t *flags,
1187  size_t sizeof_kmp_task_t, size_t sizeof_shareds,
1188  kmp_routine_entry_t task_entry) {
1189  kmp_task_t *task;
1190  kmp_taskdata_t *taskdata;
1191  kmp_info_t *thread = __kmp_threads[gtid];
1192  kmp_info_t *encountering_thread = thread;
1193  kmp_team_t *team = thread->th.th_team;
1194  kmp_taskdata_t *parent_task = thread->th.th_current_task;
1195  size_t shareds_offset;
1196 
1197  if (UNLIKELY(!TCR_4(__kmp_init_middle)))
1198  __kmp_middle_initialize();
1199 
1200  if (flags->hidden_helper) {
1201  if (__kmp_enable_hidden_helper) {
1202  if (!TCR_4(__kmp_init_hidden_helper))
1203  __kmp_hidden_helper_initialize();
1204 
1205  // For a hidden helper task encountered by a regular thread, we will push
1206  // the task to the (gtid%__kmp_hidden_helper_threads_num)-th hidden helper
1207  // thread.
1208  if (!KMP_HIDDEN_HELPER_THREAD(gtid)) {
1209  thread = __kmp_threads[KMP_GTID_TO_SHADOW_GTID(gtid)];
1210  // We don't change the parent-child relation for hidden helper task as
1211  // we need that to do per-task-region synchronization.
1212  }
1213  } else {
1214  // If the hidden helper task is not enabled, reset the flag to FALSE.
1215  flags->hidden_helper = FALSE;
1216  }
1217  }
1218 
1219  KA_TRACE(10, ("__kmp_task_alloc(enter): T#%d loc=%p, flags=(0x%x) "
1220  "sizeof_task=%ld sizeof_shared=%ld entry=%p\n",
1221  gtid, loc_ref, *((kmp_int32 *)flags), sizeof_kmp_task_t,
1222  sizeof_shareds, task_entry));
1223 
1224  KMP_DEBUG_ASSERT(parent_task);
1225  if (parent_task->td_flags.final) {
1226  if (flags->merged_if0) {
1227  }
1228  flags->final = 1;
1229  }
1230 
1231  if (flags->tiedness == TASK_UNTIED && !team->t.t_serialized) {
1232  // Untied task encountered causes the TSC algorithm to check entire deque of
1233  // the victim thread. If no untied task encountered, then checking the head
1234  // of the deque should be enough.
1235  KMP_CHECK_UPDATE(
1236  encountering_thread->th.th_task_team->tt.tt_untied_task_encountered, 1);
1237  }
1238 
1239  // Detachable tasks are not proxy tasks yet but could be in the future. Doing
1240  // the tasking setup
1241  // when that happens is too late.
1242  if (UNLIKELY(flags->proxy == TASK_PROXY ||
1243  flags->detachable == TASK_DETACHABLE || flags->hidden_helper)) {
1244  if (flags->proxy == TASK_PROXY) {
1245  flags->tiedness = TASK_UNTIED;
1246  flags->merged_if0 = 1;
1247  }
1248  /* are we running in a sequential parallel or tskm_immediate_exec... we need
1249  tasking support enabled */
1250  if ((encountering_thread->th.th_task_team) == NULL) {
1251  /* This should only happen if the team is serialized
1252  setup a task team and propagate it to the thread */
1253  KMP_DEBUG_ASSERT(team->t.t_serialized);
1254  KA_TRACE(30,
1255  ("T#%d creating task team in __kmp_task_alloc for proxy task\n",
1256  gtid));
1257  __kmp_task_team_setup(
1258  encountering_thread, team,
1259  1); // 1 indicates setup the current team regardless of nthreads
1260  encountering_thread->th.th_task_team =
1261  team->t.t_task_team[encountering_thread->th.th_task_state];
1262  }
1263  kmp_task_team_t *task_team = encountering_thread->th.th_task_team;
1264 
1265  /* tasking must be enabled now as the task might not be pushed */
1266  if (!KMP_TASKING_ENABLED(task_team)) {
1267  KA_TRACE(
1268  30,
1269  ("T#%d enabling tasking in __kmp_task_alloc for proxy task\n", gtid));
1270  __kmp_enable_tasking(task_team, encountering_thread);
1271  kmp_int32 tid = encountering_thread->th.th_info.ds.ds_tid;
1272  kmp_thread_data_t *thread_data = &task_team->tt.tt_threads_data[tid];
1273  // No lock needed since only owner can allocate
1274  if (thread_data->td.td_deque == NULL) {
1275  __kmp_alloc_task_deque(encountering_thread, thread_data);
1276  }
1277  }
1278 
1279  if ((flags->proxy == TASK_PROXY || flags->detachable == TASK_DETACHABLE) &&
1280  task_team->tt.tt_found_proxy_tasks == FALSE)
1281  TCW_4(task_team->tt.tt_found_proxy_tasks, TRUE);
1282  if (flags->hidden_helper &&
1283  task_team->tt.tt_hidden_helper_task_encountered == FALSE)
1284  TCW_4(task_team->tt.tt_hidden_helper_task_encountered, TRUE);
1285  }
1286 
1287  // Calculate shared structure offset including padding after kmp_task_t struct
1288  // to align pointers in shared struct
1289  shareds_offset = sizeof(kmp_taskdata_t) + sizeof_kmp_task_t;
1290  shareds_offset = __kmp_round_up_to_val(shareds_offset, sizeof(void *));
1291 
1292  // Allocate a kmp_taskdata_t block and a kmp_task_t block.
1293  KA_TRACE(30, ("__kmp_task_alloc: T#%d First malloc size: %ld\n", gtid,
1294  shareds_offset));
1295  KA_TRACE(30, ("__kmp_task_alloc: T#%d Second malloc size: %ld\n", gtid,
1296  sizeof_shareds));
1297 
1298  // Avoid double allocation here by combining shareds with taskdata
1299 #if USE_FAST_MEMORY
1300  taskdata = (kmp_taskdata_t *)__kmp_fast_allocate(
1301  encountering_thread, shareds_offset + sizeof_shareds);
1302 #else /* ! USE_FAST_MEMORY */
1303  taskdata = (kmp_taskdata_t *)__kmp_thread_malloc(
1304  encountering_thread, shareds_offset + sizeof_shareds);
1305 #endif /* USE_FAST_MEMORY */
1306 
1307  task = KMP_TASKDATA_TO_TASK(taskdata);
1308 
1309 // Make sure task & taskdata are aligned appropriately
1310 #if KMP_ARCH_X86 || KMP_ARCH_PPC64 || !KMP_HAVE_QUAD
1311  KMP_DEBUG_ASSERT((((kmp_uintptr_t)taskdata) & (sizeof(double) - 1)) == 0);
1312  KMP_DEBUG_ASSERT((((kmp_uintptr_t)task) & (sizeof(double) - 1)) == 0);
1313 #else
1314  KMP_DEBUG_ASSERT((((kmp_uintptr_t)taskdata) & (sizeof(_Quad) - 1)) == 0);
1315  KMP_DEBUG_ASSERT((((kmp_uintptr_t)task) & (sizeof(_Quad) - 1)) == 0);
1316 #endif
1317  if (sizeof_shareds > 0) {
1318  // Avoid double allocation here by combining shareds with taskdata
1319  task->shareds = &((char *)taskdata)[shareds_offset];
1320  // Make sure shareds struct is aligned to pointer size
1321  KMP_DEBUG_ASSERT((((kmp_uintptr_t)task->shareds) & (sizeof(void *) - 1)) ==
1322  0);
1323  } else {
1324  task->shareds = NULL;
1325  }
1326  task->routine = task_entry;
1327  task->part_id = 0; // AC: Always start with 0 part id
1328 
1329  taskdata->td_task_id = KMP_GEN_TASK_ID();
1330  taskdata->td_team = thread->th.th_team;
1331  taskdata->td_alloc_thread = encountering_thread;
1332  taskdata->td_parent = parent_task;
1333  taskdata->td_level = parent_task->td_level + 1; // increment nesting level
1334  KMP_ATOMIC_ST_RLX(&taskdata->td_untied_count, 0);
1335  taskdata->td_ident = loc_ref;
1336  taskdata->td_taskwait_ident = NULL;
1337  taskdata->td_taskwait_counter = 0;
1338  taskdata->td_taskwait_thread = 0;
1339  KMP_DEBUG_ASSERT(taskdata->td_parent != NULL);
1340  // avoid copying icvs for proxy tasks
1341  if (flags->proxy == TASK_FULL)
1342  copy_icvs(&taskdata->td_icvs, &taskdata->td_parent->td_icvs);
1343 
1344  taskdata->td_flags = *flags;
1345  taskdata->encountering_gtid = gtid;
1346  taskdata->td_task_team = thread->th.th_task_team;
1347  taskdata->td_size_alloc = shareds_offset + sizeof_shareds;
1348  taskdata->td_flags.tasktype = TASK_EXPLICIT;
1349 
1350  // GEH - TODO: fix this to copy parent task's value of tasking_ser flag
1351  taskdata->td_flags.tasking_ser = (__kmp_tasking_mode == tskm_immediate_exec);
1352 
1353  // GEH - TODO: fix this to copy parent task's value of team_serial flag
1354  taskdata->td_flags.team_serial = (team->t.t_serialized) ? 1 : 0;
1355 
1356  // GEH - Note we serialize the task if the team is serialized to make sure
1357  // implicit parallel region tasks are not left until program termination to
1358  // execute. Also, it helps locality to execute immediately.
1359 
1360  taskdata->td_flags.task_serial =
1361  (parent_task->td_flags.final || taskdata->td_flags.team_serial ||
1362  taskdata->td_flags.tasking_ser || flags->merged_if0);
1363 
1364  taskdata->td_flags.started = 0;
1365  taskdata->td_flags.executing = 0;
1366  taskdata->td_flags.complete = 0;
1367  taskdata->td_flags.freed = 0;
1368 
1369  KMP_ATOMIC_ST_RLX(&taskdata->td_incomplete_child_tasks, 0);
1370  // start at one because counts current task and children
1371  KMP_ATOMIC_ST_RLX(&taskdata->td_allocated_child_tasks, 1);
1372  taskdata->td_taskgroup =
1373  parent_task->td_taskgroup; // task inherits taskgroup from the parent task
1374  taskdata->td_dephash = NULL;
1375  taskdata->td_depnode = NULL;
1376  if (flags->tiedness == TASK_UNTIED)
1377  taskdata->td_last_tied = NULL; // will be set when the task is scheduled
1378  else
1379  taskdata->td_last_tied = taskdata;
1380  taskdata->td_allow_completion_event.type = KMP_EVENT_UNINITIALIZED;
1381 #if OMPT_SUPPORT
1382  if (UNLIKELY(ompt_enabled.enabled))
1383  __ompt_task_init(taskdata, gtid);
1384 #endif
1385  // Only need to keep track of child task counts if team parallel and tasking
1386  // not serialized or if it is a proxy or detachable or hidden helper task
1387  if (flags->proxy == TASK_PROXY || flags->detachable == TASK_DETACHABLE ||
1388  flags->hidden_helper ||
1389  !(taskdata->td_flags.team_serial || taskdata->td_flags.tasking_ser)) {
1390  KMP_ATOMIC_INC(&parent_task->td_incomplete_child_tasks);
1391  if (parent_task->td_taskgroup)
1392  KMP_ATOMIC_INC(&parent_task->td_taskgroup->count);
1393  // Only need to keep track of allocated child tasks for explicit tasks since
1394  // implicit not deallocated
1395  if (taskdata->td_parent->td_flags.tasktype == TASK_EXPLICIT) {
1396  KMP_ATOMIC_INC(&taskdata->td_parent->td_allocated_child_tasks);
1397  }
1398  if (flags->hidden_helper) {
1399  taskdata->td_flags.task_serial = FALSE;
1400  // Increment the number of hidden helper tasks to be executed
1401  KMP_ATOMIC_INC(&__kmp_unexecuted_hidden_helper_tasks);
1402  }
1403  }
1404 
1405  KA_TRACE(20, ("__kmp_task_alloc(exit): T#%d created task %p parent=%p\n",
1406  gtid, taskdata, taskdata->td_parent));
1407 
1408  return task;
1409 }
1410 
1411 kmp_task_t *__kmpc_omp_task_alloc(ident_t *loc_ref, kmp_int32 gtid,
1412  kmp_int32 flags, size_t sizeof_kmp_task_t,
1413  size_t sizeof_shareds,
1414  kmp_routine_entry_t task_entry) {
1415  kmp_task_t *retval;
1416  kmp_tasking_flags_t *input_flags = (kmp_tasking_flags_t *)&flags;
1417  __kmp_assert_valid_gtid(gtid);
1418  input_flags->native = FALSE;
1419  // __kmp_task_alloc() sets up all other runtime flags
1420  KA_TRACE(10, ("__kmpc_omp_task_alloc(enter): T#%d loc=%p, flags=(%s %s %s) "
1421  "sizeof_task=%ld sizeof_shared=%ld entry=%p\n",
1422  gtid, loc_ref, input_flags->tiedness ? "tied " : "untied",
1423  input_flags->proxy ? "proxy" : "",
1424  input_flags->detachable ? "detachable" : "", sizeof_kmp_task_t,
1425  sizeof_shareds, task_entry));
1426 
1427  retval = __kmp_task_alloc(loc_ref, gtid, input_flags, sizeof_kmp_task_t,
1428  sizeof_shareds, task_entry);
1429 
1430  KA_TRACE(20, ("__kmpc_omp_task_alloc(exit): T#%d retval %p\n", gtid, retval));
1431 
1432  return retval;
1433 }
1434 
1435 kmp_task_t *__kmpc_omp_target_task_alloc(ident_t *loc_ref, kmp_int32 gtid,
1436  kmp_int32 flags,
1437  size_t sizeof_kmp_task_t,
1438  size_t sizeof_shareds,
1439  kmp_routine_entry_t task_entry,
1440  kmp_int64 device_id) {
1441  if (__kmp_enable_hidden_helper) {
1442  auto &input_flags = reinterpret_cast<kmp_tasking_flags_t &>(flags);
1443  input_flags.hidden_helper = TRUE;
1444  input_flags.tiedness = TASK_UNTIED;
1445  }
1446 
1447  return __kmpc_omp_task_alloc(loc_ref, gtid, flags, sizeof_kmp_task_t,
1448  sizeof_shareds, task_entry);
1449 }
1450 
1464 kmp_int32
1466  kmp_task_t *new_task, kmp_int32 naffins,
1467  kmp_task_affinity_info_t *affin_list) {
1468  return 0;
1469 }
1470 
1471 // __kmp_invoke_task: invoke the specified task
1472 //
1473 // gtid: global thread ID of caller
1474 // task: the task to invoke
1475 // current_task: the task to resume after task invocation
1476 static void __kmp_invoke_task(kmp_int32 gtid, kmp_task_t *task,
1477  kmp_taskdata_t *current_task) {
1478  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(task);
1479  kmp_info_t *thread;
1480  int discard = 0 /* false */;
1481  KA_TRACE(
1482  30, ("__kmp_invoke_task(enter): T#%d invoking task %p, current_task=%p\n",
1483  gtid, taskdata, current_task));
1484  KMP_DEBUG_ASSERT(task);
1485  if (UNLIKELY(taskdata->td_flags.proxy == TASK_PROXY &&
1486  taskdata->td_flags.complete == 1)) {
1487  // This is a proxy task that was already completed but it needs to run
1488  // its bottom-half finish
1489  KA_TRACE(
1490  30,
1491  ("__kmp_invoke_task: T#%d running bottom finish for proxy task %p\n",
1492  gtid, taskdata));
1493 
1494  __kmp_bottom_half_finish_proxy(gtid, task);
1495 
1496  KA_TRACE(30, ("__kmp_invoke_task(exit): T#%d completed bottom finish for "
1497  "proxy task %p, resuming task %p\n",
1498  gtid, taskdata, current_task));
1499 
1500  return;
1501  }
1502 
1503 #if OMPT_SUPPORT
1504  // For untied tasks, the first task executed only calls __kmpc_omp_task and
1505  // does not execute code.
1506  ompt_thread_info_t oldInfo;
1507  if (UNLIKELY(ompt_enabled.enabled)) {
1508  // Store the threads states and restore them after the task
1509  thread = __kmp_threads[gtid];
1510  oldInfo = thread->th.ompt_thread_info;
1511  thread->th.ompt_thread_info.wait_id = 0;
1512  thread->th.ompt_thread_info.state = (thread->th.th_team_serialized)
1513  ? ompt_state_work_serial
1514  : ompt_state_work_parallel;
1515  taskdata->ompt_task_info.frame.exit_frame.ptr = OMPT_GET_FRAME_ADDRESS(0);
1516  }
1517 #endif
1518 
1519  // Decreament the counter of hidden helper tasks to be executed
1520  if (taskdata->td_flags.hidden_helper) {
1521  // Hidden helper tasks can only be executed by hidden helper threads
1522  KMP_ASSERT(KMP_HIDDEN_HELPER_THREAD(gtid));
1523  KMP_ATOMIC_DEC(&__kmp_unexecuted_hidden_helper_tasks);
1524  }
1525 
1526  // Proxy tasks are not handled by the runtime
1527  if (taskdata->td_flags.proxy != TASK_PROXY) {
1528  __kmp_task_start(gtid, task, current_task); // OMPT only if not discarded
1529  }
1530 
1531  // TODO: cancel tasks if the parallel region has also been cancelled
1532  // TODO: check if this sequence can be hoisted above __kmp_task_start
1533  // if cancellation has been enabled for this run ...
1534  if (UNLIKELY(__kmp_omp_cancellation)) {
1535  thread = __kmp_threads[gtid];
1536  kmp_team_t *this_team = thread->th.th_team;
1537  kmp_taskgroup_t *taskgroup = taskdata->td_taskgroup;
1538  if ((taskgroup && taskgroup->cancel_request) ||
1539  (this_team->t.t_cancel_request == cancel_parallel)) {
1540 #if OMPT_SUPPORT && OMPT_OPTIONAL
1541  ompt_data_t *task_data;
1542  if (UNLIKELY(ompt_enabled.ompt_callback_cancel)) {
1543  __ompt_get_task_info_internal(0, NULL, &task_data, NULL, NULL, NULL);
1544  ompt_callbacks.ompt_callback(ompt_callback_cancel)(
1545  task_data,
1546  ((taskgroup && taskgroup->cancel_request) ? ompt_cancel_taskgroup
1547  : ompt_cancel_parallel) |
1548  ompt_cancel_discarded_task,
1549  NULL);
1550  }
1551 #endif
1552  KMP_COUNT_BLOCK(TASK_cancelled);
1553  // this task belongs to a task group and we need to cancel it
1554  discard = 1 /* true */;
1555  }
1556  }
1557 
1558  // Invoke the task routine and pass in relevant data.
1559  // Thunks generated by gcc take a different argument list.
1560  if (!discard) {
1561  if (taskdata->td_flags.tiedness == TASK_UNTIED) {
1562  taskdata->td_last_tied = current_task->td_last_tied;
1563  KMP_DEBUG_ASSERT(taskdata->td_last_tied);
1564  }
1565 #if KMP_STATS_ENABLED
1566  KMP_COUNT_BLOCK(TASK_executed);
1567  switch (KMP_GET_THREAD_STATE()) {
1568  case FORK_JOIN_BARRIER:
1569  KMP_PUSH_PARTITIONED_TIMER(OMP_task_join_bar);
1570  break;
1571  case PLAIN_BARRIER:
1572  KMP_PUSH_PARTITIONED_TIMER(OMP_task_plain_bar);
1573  break;
1574  case TASKYIELD:
1575  KMP_PUSH_PARTITIONED_TIMER(OMP_task_taskyield);
1576  break;
1577  case TASKWAIT:
1578  KMP_PUSH_PARTITIONED_TIMER(OMP_task_taskwait);
1579  break;
1580  case TASKGROUP:
1581  KMP_PUSH_PARTITIONED_TIMER(OMP_task_taskgroup);
1582  break;
1583  default:
1584  KMP_PUSH_PARTITIONED_TIMER(OMP_task_immediate);
1585  break;
1586  }
1587 #endif // KMP_STATS_ENABLED
1588 
1589 // OMPT task begin
1590 #if OMPT_SUPPORT
1591  if (UNLIKELY(ompt_enabled.enabled))
1592  __ompt_task_start(task, current_task, gtid);
1593 #endif
1594 
1595 #if OMPD_SUPPORT
1596  if (ompd_state & OMPD_ENABLE_BP)
1597  ompd_bp_task_begin();
1598 #endif
1599 
1600 #if USE_ITT_BUILD && USE_ITT_NOTIFY
1601  kmp_uint64 cur_time;
1602  kmp_int32 kmp_itt_count_task =
1603  __kmp_forkjoin_frames_mode == 3 && !taskdata->td_flags.task_serial &&
1604  current_task->td_flags.tasktype == TASK_IMPLICIT;
1605  if (kmp_itt_count_task) {
1606  thread = __kmp_threads[gtid];
1607  // Time outer level explicit task on barrier for adjusting imbalance time
1608  if (thread->th.th_bar_arrive_time)
1609  cur_time = __itt_get_timestamp();
1610  else
1611  kmp_itt_count_task = 0; // thread is not on a barrier - skip timing
1612  }
1613  KMP_FSYNC_ACQUIRED(taskdata); // acquired self (new task)
1614 #endif
1615 
1616 #ifdef KMP_GOMP_COMPAT
1617  if (taskdata->td_flags.native) {
1618  ((void (*)(void *))(*(task->routine)))(task->shareds);
1619  } else
1620 #endif /* KMP_GOMP_COMPAT */
1621  {
1622  (*(task->routine))(gtid, task);
1623  }
1624  KMP_POP_PARTITIONED_TIMER();
1625 
1626 #if USE_ITT_BUILD && USE_ITT_NOTIFY
1627  if (kmp_itt_count_task) {
1628  // Barrier imbalance - adjust arrive time with the task duration
1629  thread->th.th_bar_arrive_time += (__itt_get_timestamp() - cur_time);
1630  }
1631  KMP_FSYNC_CANCEL(taskdata); // destroy self (just executed)
1632  KMP_FSYNC_RELEASING(taskdata->td_parent); // releasing parent
1633 #endif
1634  }
1635 
1636 #if OMPD_SUPPORT
1637  if (ompd_state & OMPD_ENABLE_BP)
1638  ompd_bp_task_end();
1639 #endif
1640 
1641  // Proxy tasks are not handled by the runtime
1642  if (taskdata->td_flags.proxy != TASK_PROXY) {
1643 #if OMPT_SUPPORT
1644  if (UNLIKELY(ompt_enabled.enabled)) {
1645  thread->th.ompt_thread_info = oldInfo;
1646  if (taskdata->td_flags.tiedness == TASK_TIED) {
1647  taskdata->ompt_task_info.frame.exit_frame = ompt_data_none;
1648  }
1649  __kmp_task_finish<true>(gtid, task, current_task);
1650  } else
1651 #endif
1652  __kmp_task_finish<false>(gtid, task, current_task);
1653  }
1654 
1655  KA_TRACE(
1656  30,
1657  ("__kmp_invoke_task(exit): T#%d completed task %p, resuming task %p\n",
1658  gtid, taskdata, current_task));
1659  return;
1660 }
1661 
1662 // __kmpc_omp_task_parts: Schedule a thread-switchable task for execution
1663 //
1664 // loc_ref: location of original task pragma (ignored)
1665 // gtid: Global Thread ID of encountering thread
1666 // new_task: task thunk allocated by __kmp_omp_task_alloc() for the ''new task''
1667 // Returns:
1668 // TASK_CURRENT_NOT_QUEUED (0) if did not suspend and queue current task to
1669 // be resumed later.
1670 // TASK_CURRENT_QUEUED (1) if suspended and queued the current task to be
1671 // resumed later.
1672 kmp_int32 __kmpc_omp_task_parts(ident_t *loc_ref, kmp_int32 gtid,
1673  kmp_task_t *new_task) {
1674  kmp_taskdata_t *new_taskdata = KMP_TASK_TO_TASKDATA(new_task);
1675 
1676  KA_TRACE(10, ("__kmpc_omp_task_parts(enter): T#%d loc=%p task=%p\n", gtid,
1677  loc_ref, new_taskdata));
1678 
1679 #if OMPT_SUPPORT
1680  kmp_taskdata_t *parent;
1681  if (UNLIKELY(ompt_enabled.enabled)) {
1682  parent = new_taskdata->td_parent;
1683  if (ompt_enabled.ompt_callback_task_create) {
1684  ompt_callbacks.ompt_callback(ompt_callback_task_create)(
1685  &(parent->ompt_task_info.task_data), &(parent->ompt_task_info.frame),
1686  &(new_taskdata->ompt_task_info.task_data), ompt_task_explicit, 0,
1687  OMPT_GET_RETURN_ADDRESS(0));
1688  }
1689  }
1690 #endif
1691 
1692  /* Should we execute the new task or queue it? For now, let's just always try
1693  to queue it. If the queue fills up, then we'll execute it. */
1694 
1695  if (__kmp_push_task(gtid, new_task) == TASK_NOT_PUSHED) // if cannot defer
1696  { // Execute this task immediately
1697  kmp_taskdata_t *current_task = __kmp_threads[gtid]->th.th_current_task;
1698  new_taskdata->td_flags.task_serial = 1;
1699  __kmp_invoke_task(gtid, new_task, current_task);
1700  }
1701 
1702  KA_TRACE(
1703  10,
1704  ("__kmpc_omp_task_parts(exit): T#%d returning TASK_CURRENT_NOT_QUEUED: "
1705  "loc=%p task=%p, return: TASK_CURRENT_NOT_QUEUED\n",
1706  gtid, loc_ref, new_taskdata));
1707 
1708 #if OMPT_SUPPORT
1709  if (UNLIKELY(ompt_enabled.enabled)) {
1710  parent->ompt_task_info.frame.enter_frame = ompt_data_none;
1711  }
1712 #endif
1713  return TASK_CURRENT_NOT_QUEUED;
1714 }
1715 
1716 // __kmp_omp_task: Schedule a non-thread-switchable task for execution
1717 //
1718 // gtid: Global Thread ID of encountering thread
1719 // new_task:non-thread-switchable task thunk allocated by __kmp_omp_task_alloc()
1720 // serialize_immediate: if TRUE then if the task is executed immediately its
1721 // execution will be serialized
1722 // Returns:
1723 // TASK_CURRENT_NOT_QUEUED (0) if did not suspend and queue current task to
1724 // be resumed later.
1725 // TASK_CURRENT_QUEUED (1) if suspended and queued the current task to be
1726 // resumed later.
1727 kmp_int32 __kmp_omp_task(kmp_int32 gtid, kmp_task_t *new_task,
1728  bool serialize_immediate) {
1729  kmp_taskdata_t *new_taskdata = KMP_TASK_TO_TASKDATA(new_task);
1730 
1731  /* Should we execute the new task or queue it? For now, let's just always try
1732  to queue it. If the queue fills up, then we'll execute it. */
1733  if (new_taskdata->td_flags.proxy == TASK_PROXY ||
1734  __kmp_push_task(gtid, new_task) == TASK_NOT_PUSHED) // if cannot defer
1735  { // Execute this task immediately
1736  kmp_taskdata_t *current_task = __kmp_threads[gtid]->th.th_current_task;
1737  if (serialize_immediate)
1738  new_taskdata->td_flags.task_serial = 1;
1739  __kmp_invoke_task(gtid, new_task, current_task);
1740  }
1741 
1742  return TASK_CURRENT_NOT_QUEUED;
1743 }
1744 
1745 // __kmpc_omp_task: Wrapper around __kmp_omp_task to schedule a
1746 // non-thread-switchable task from the parent thread only!
1747 //
1748 // loc_ref: location of original task pragma (ignored)
1749 // gtid: Global Thread ID of encountering thread
1750 // new_task: non-thread-switchable task thunk allocated by
1751 // __kmp_omp_task_alloc()
1752 // Returns:
1753 // TASK_CURRENT_NOT_QUEUED (0) if did not suspend and queue current task to
1754 // be resumed later.
1755 // TASK_CURRENT_QUEUED (1) if suspended and queued the current task to be
1756 // resumed later.
1757 kmp_int32 __kmpc_omp_task(ident_t *loc_ref, kmp_int32 gtid,
1758  kmp_task_t *new_task) {
1759  kmp_int32 res;
1760  KMP_SET_THREAD_STATE_BLOCK(EXPLICIT_TASK);
1761 
1762 #if KMP_DEBUG || OMPT_SUPPORT
1763  kmp_taskdata_t *new_taskdata = KMP_TASK_TO_TASKDATA(new_task);
1764 #endif
1765  KA_TRACE(10, ("__kmpc_omp_task(enter): T#%d loc=%p task=%p\n", gtid, loc_ref,
1766  new_taskdata));
1767  __kmp_assert_valid_gtid(gtid);
1768 
1769 #if OMPT_SUPPORT
1770  kmp_taskdata_t *parent = NULL;
1771  if (UNLIKELY(ompt_enabled.enabled)) {
1772  if (!new_taskdata->td_flags.started) {
1773  OMPT_STORE_RETURN_ADDRESS(gtid);
1774  parent = new_taskdata->td_parent;
1775  if (!parent->ompt_task_info.frame.enter_frame.ptr) {
1776  parent->ompt_task_info.frame.enter_frame.ptr =
1777  OMPT_GET_FRAME_ADDRESS(0);
1778  }
1779  if (ompt_enabled.ompt_callback_task_create) {
1780  ompt_callbacks.ompt_callback(ompt_callback_task_create)(
1781  &(parent->ompt_task_info.task_data),
1782  &(parent->ompt_task_info.frame),
1783  &(new_taskdata->ompt_task_info.task_data),
1784  ompt_task_explicit | TASK_TYPE_DETAILS_FORMAT(new_taskdata), 0,
1785  OMPT_LOAD_RETURN_ADDRESS(gtid));
1786  }
1787  } else {
1788  // We are scheduling the continuation of an UNTIED task.
1789  // Scheduling back to the parent task.
1790  __ompt_task_finish(new_task,
1791  new_taskdata->ompt_task_info.scheduling_parent,
1792  ompt_task_switch);
1793  new_taskdata->ompt_task_info.frame.exit_frame = ompt_data_none;
1794  }
1795  }
1796 #endif
1797 
1798  res = __kmp_omp_task(gtid, new_task, true);
1799 
1800  KA_TRACE(10, ("__kmpc_omp_task(exit): T#%d returning "
1801  "TASK_CURRENT_NOT_QUEUED: loc=%p task=%p\n",
1802  gtid, loc_ref, new_taskdata));
1803 #if OMPT_SUPPORT
1804  if (UNLIKELY(ompt_enabled.enabled && parent != NULL)) {
1805  parent->ompt_task_info.frame.enter_frame = ompt_data_none;
1806  }
1807 #endif
1808  return res;
1809 }
1810 
1811 // __kmp_omp_taskloop_task: Wrapper around __kmp_omp_task to schedule
1812 // a taskloop task with the correct OMPT return address
1813 //
1814 // loc_ref: location of original task pragma (ignored)
1815 // gtid: Global Thread ID of encountering thread
1816 // new_task: non-thread-switchable task thunk allocated by
1817 // __kmp_omp_task_alloc()
1818 // codeptr_ra: return address for OMPT callback
1819 // Returns:
1820 // TASK_CURRENT_NOT_QUEUED (0) if did not suspend and queue current task to
1821 // be resumed later.
1822 // TASK_CURRENT_QUEUED (1) if suspended and queued the current task to be
1823 // resumed later.
1824 kmp_int32 __kmp_omp_taskloop_task(ident_t *loc_ref, kmp_int32 gtid,
1825  kmp_task_t *new_task, void *codeptr_ra) {
1826  kmp_int32 res;
1827  KMP_SET_THREAD_STATE_BLOCK(EXPLICIT_TASK);
1828 
1829 #if KMP_DEBUG || OMPT_SUPPORT
1830  kmp_taskdata_t *new_taskdata = KMP_TASK_TO_TASKDATA(new_task);
1831 #endif
1832  KA_TRACE(10, ("__kmpc_omp_task(enter): T#%d loc=%p task=%p\n", gtid, loc_ref,
1833  new_taskdata));
1834 
1835 #if OMPT_SUPPORT
1836  kmp_taskdata_t *parent = NULL;
1837  if (UNLIKELY(ompt_enabled.enabled && !new_taskdata->td_flags.started)) {
1838  parent = new_taskdata->td_parent;
1839  if (!parent->ompt_task_info.frame.enter_frame.ptr)
1840  parent->ompt_task_info.frame.enter_frame.ptr = OMPT_GET_FRAME_ADDRESS(0);
1841  if (ompt_enabled.ompt_callback_task_create) {
1842  ompt_callbacks.ompt_callback(ompt_callback_task_create)(
1843  &(parent->ompt_task_info.task_data), &(parent->ompt_task_info.frame),
1844  &(new_taskdata->ompt_task_info.task_data),
1845  ompt_task_explicit | TASK_TYPE_DETAILS_FORMAT(new_taskdata), 0,
1846  codeptr_ra);
1847  }
1848  }
1849 #endif
1850 
1851  res = __kmp_omp_task(gtid, new_task, true);
1852 
1853  KA_TRACE(10, ("__kmpc_omp_task(exit): T#%d returning "
1854  "TASK_CURRENT_NOT_QUEUED: loc=%p task=%p\n",
1855  gtid, loc_ref, new_taskdata));
1856 #if OMPT_SUPPORT
1857  if (UNLIKELY(ompt_enabled.enabled && parent != NULL)) {
1858  parent->ompt_task_info.frame.enter_frame = ompt_data_none;
1859  }
1860 #endif
1861  return res;
1862 }
1863 
1864 template <bool ompt>
1865 static kmp_int32 __kmpc_omp_taskwait_template(ident_t *loc_ref, kmp_int32 gtid,
1866  void *frame_address,
1867  void *return_address) {
1868  kmp_taskdata_t *taskdata = nullptr;
1869  kmp_info_t *thread;
1870  int thread_finished = FALSE;
1871  KMP_SET_THREAD_STATE_BLOCK(TASKWAIT);
1872 
1873  KA_TRACE(10, ("__kmpc_omp_taskwait(enter): T#%d loc=%p\n", gtid, loc_ref));
1874  KMP_DEBUG_ASSERT(gtid >= 0);
1875 
1876  if (__kmp_tasking_mode != tskm_immediate_exec) {
1877  thread = __kmp_threads[gtid];
1878  taskdata = thread->th.th_current_task;
1879 
1880 #if OMPT_SUPPORT && OMPT_OPTIONAL
1881  ompt_data_t *my_task_data;
1882  ompt_data_t *my_parallel_data;
1883 
1884  if (ompt) {
1885  my_task_data = &(taskdata->ompt_task_info.task_data);
1886  my_parallel_data = OMPT_CUR_TEAM_DATA(thread);
1887 
1888  taskdata->ompt_task_info.frame.enter_frame.ptr = frame_address;
1889 
1890  if (ompt_enabled.ompt_callback_sync_region) {
1891  ompt_callbacks.ompt_callback(ompt_callback_sync_region)(
1892  ompt_sync_region_taskwait, ompt_scope_begin, my_parallel_data,
1893  my_task_data, return_address);
1894  }
1895 
1896  if (ompt_enabled.ompt_callback_sync_region_wait) {
1897  ompt_callbacks.ompt_callback(ompt_callback_sync_region_wait)(
1898  ompt_sync_region_taskwait, ompt_scope_begin, my_parallel_data,
1899  my_task_data, return_address);
1900  }
1901  }
1902 #endif // OMPT_SUPPORT && OMPT_OPTIONAL
1903 
1904 // Debugger: The taskwait is active. Store location and thread encountered the
1905 // taskwait.
1906 #if USE_ITT_BUILD
1907 // Note: These values are used by ITT events as well.
1908 #endif /* USE_ITT_BUILD */
1909  taskdata->td_taskwait_counter += 1;
1910  taskdata->td_taskwait_ident = loc_ref;
1911  taskdata->td_taskwait_thread = gtid + 1;
1912 
1913 #if USE_ITT_BUILD
1914  void *itt_sync_obj = NULL;
1915 #if USE_ITT_NOTIFY
1916  KMP_ITT_TASKWAIT_STARTING(itt_sync_obj);
1917 #endif /* USE_ITT_NOTIFY */
1918 #endif /* USE_ITT_BUILD */
1919 
1920  bool must_wait =
1921  !taskdata->td_flags.team_serial && !taskdata->td_flags.final;
1922 
1923  must_wait = must_wait || (thread->th.th_task_team != NULL &&
1924  thread->th.th_task_team->tt.tt_found_proxy_tasks);
1925  // If hidden helper thread is encountered, we must enable wait here.
1926  must_wait =
1927  must_wait ||
1928  (__kmp_enable_hidden_helper && thread->th.th_task_team != NULL &&
1929  thread->th.th_task_team->tt.tt_hidden_helper_task_encountered);
1930 
1931  if (must_wait) {
1932  kmp_flag_32<false, false> flag(
1933  RCAST(std::atomic<kmp_uint32> *,
1934  &(taskdata->td_incomplete_child_tasks)),
1935  0U);
1936  while (KMP_ATOMIC_LD_ACQ(&taskdata->td_incomplete_child_tasks) != 0) {
1937  flag.execute_tasks(thread, gtid, FALSE,
1938  &thread_finished USE_ITT_BUILD_ARG(itt_sync_obj),
1939  __kmp_task_stealing_constraint);
1940  }
1941  }
1942 #if USE_ITT_BUILD
1943  KMP_ITT_TASKWAIT_FINISHED(itt_sync_obj);
1944  KMP_FSYNC_ACQUIRED(taskdata); // acquire self - sync with children
1945 #endif /* USE_ITT_BUILD */
1946 
1947  // Debugger: The taskwait is completed. Location remains, but thread is
1948  // negated.
1949  taskdata->td_taskwait_thread = -taskdata->td_taskwait_thread;
1950 
1951 #if OMPT_SUPPORT && OMPT_OPTIONAL
1952  if (ompt) {
1953  if (ompt_enabled.ompt_callback_sync_region_wait) {
1954  ompt_callbacks.ompt_callback(ompt_callback_sync_region_wait)(
1955  ompt_sync_region_taskwait, ompt_scope_end, my_parallel_data,
1956  my_task_data, return_address);
1957  }
1958  if (ompt_enabled.ompt_callback_sync_region) {
1959  ompt_callbacks.ompt_callback(ompt_callback_sync_region)(
1960  ompt_sync_region_taskwait, ompt_scope_end, my_parallel_data,
1961  my_task_data, return_address);
1962  }
1963  taskdata->ompt_task_info.frame.enter_frame = ompt_data_none;
1964  }
1965 #endif // OMPT_SUPPORT && OMPT_OPTIONAL
1966 
1967  }
1968 
1969  KA_TRACE(10, ("__kmpc_omp_taskwait(exit): T#%d task %p finished waiting, "
1970  "returning TASK_CURRENT_NOT_QUEUED\n",
1971  gtid, taskdata));
1972 
1973  return TASK_CURRENT_NOT_QUEUED;
1974 }
1975 
1976 #if OMPT_SUPPORT && OMPT_OPTIONAL
1977 OMPT_NOINLINE
1978 static kmp_int32 __kmpc_omp_taskwait_ompt(ident_t *loc_ref, kmp_int32 gtid,
1979  void *frame_address,
1980  void *return_address) {
1981  return __kmpc_omp_taskwait_template<true>(loc_ref, gtid, frame_address,
1982  return_address);
1983 }
1984 #endif // OMPT_SUPPORT && OMPT_OPTIONAL
1985 
1986 // __kmpc_omp_taskwait: Wait until all tasks generated by the current task are
1987 // complete
1988 kmp_int32 __kmpc_omp_taskwait(ident_t *loc_ref, kmp_int32 gtid) {
1989 #if OMPT_SUPPORT && OMPT_OPTIONAL
1990  if (UNLIKELY(ompt_enabled.enabled)) {
1991  OMPT_STORE_RETURN_ADDRESS(gtid);
1992  return __kmpc_omp_taskwait_ompt(loc_ref, gtid, OMPT_GET_FRAME_ADDRESS(0),
1993  OMPT_LOAD_RETURN_ADDRESS(gtid));
1994  }
1995 #endif
1996  return __kmpc_omp_taskwait_template<false>(loc_ref, gtid, NULL, NULL);
1997 }
1998 
1999 // __kmpc_omp_taskyield: switch to a different task
2000 kmp_int32 __kmpc_omp_taskyield(ident_t *loc_ref, kmp_int32 gtid, int end_part) {
2001  kmp_taskdata_t *taskdata = NULL;
2002  kmp_info_t *thread;
2003  int thread_finished = FALSE;
2004 
2005  KMP_COUNT_BLOCK(OMP_TASKYIELD);
2006  KMP_SET_THREAD_STATE_BLOCK(TASKYIELD);
2007 
2008  KA_TRACE(10, ("__kmpc_omp_taskyield(enter): T#%d loc=%p end_part = %d\n",
2009  gtid, loc_ref, end_part));
2010  __kmp_assert_valid_gtid(gtid);
2011 
2012  if (__kmp_tasking_mode != tskm_immediate_exec && __kmp_init_parallel) {
2013  thread = __kmp_threads[gtid];
2014  taskdata = thread->th.th_current_task;
2015 // Should we model this as a task wait or not?
2016 // Debugger: The taskwait is active. Store location and thread encountered the
2017 // taskwait.
2018 #if USE_ITT_BUILD
2019 // Note: These values are used by ITT events as well.
2020 #endif /* USE_ITT_BUILD */
2021  taskdata->td_taskwait_counter += 1;
2022  taskdata->td_taskwait_ident = loc_ref;
2023  taskdata->td_taskwait_thread = gtid + 1;
2024 
2025 #if USE_ITT_BUILD
2026  void *itt_sync_obj = NULL;
2027 #if USE_ITT_NOTIFY
2028  KMP_ITT_TASKWAIT_STARTING(itt_sync_obj);
2029 #endif /* USE_ITT_NOTIFY */
2030 #endif /* USE_ITT_BUILD */
2031  if (!taskdata->td_flags.team_serial) {
2032  kmp_task_team_t *task_team = thread->th.th_task_team;
2033  if (task_team != NULL) {
2034  if (KMP_TASKING_ENABLED(task_team)) {
2035 #if OMPT_SUPPORT
2036  if (UNLIKELY(ompt_enabled.enabled))
2037  thread->th.ompt_thread_info.ompt_task_yielded = 1;
2038 #endif
2039  __kmp_execute_tasks_32(
2040  thread, gtid, (kmp_flag_32<> *)NULL, FALSE,
2041  &thread_finished USE_ITT_BUILD_ARG(itt_sync_obj),
2042  __kmp_task_stealing_constraint);
2043 #if OMPT_SUPPORT
2044  if (UNLIKELY(ompt_enabled.enabled))
2045  thread->th.ompt_thread_info.ompt_task_yielded = 0;
2046 #endif
2047  }
2048  }
2049  }
2050 #if USE_ITT_BUILD
2051  KMP_ITT_TASKWAIT_FINISHED(itt_sync_obj);
2052 #endif /* USE_ITT_BUILD */
2053 
2054  // Debugger: The taskwait is completed. Location remains, but thread is
2055  // negated.
2056  taskdata->td_taskwait_thread = -taskdata->td_taskwait_thread;
2057  }
2058 
2059  KA_TRACE(10, ("__kmpc_omp_taskyield(exit): T#%d task %p resuming, "
2060  "returning TASK_CURRENT_NOT_QUEUED\n",
2061  gtid, taskdata));
2062 
2063  return TASK_CURRENT_NOT_QUEUED;
2064 }
2065 
2066 // Task Reduction implementation
2067 //
2068 // Note: initial implementation didn't take into account the possibility
2069 // to specify omp_orig for initializer of the UDR (user defined reduction).
2070 // Corrected implementation takes into account the omp_orig object.
2071 // Compiler is free to use old implementation if omp_orig is not specified.
2072 
2081 typedef struct kmp_taskred_flags {
2083  unsigned lazy_priv : 1;
2084  unsigned reserved31 : 31;
2086 
2090 typedef struct kmp_task_red_input {
2091  void *reduce_shar;
2092  size_t reduce_size;
2093  // three compiler-generated routines (init, fini are optional):
2094  void *reduce_init;
2095  void *reduce_fini;
2096  void *reduce_comb;
2099 
2103 typedef struct kmp_taskred_data {
2104  void *reduce_shar;
2105  size_t reduce_size;
2107  void *reduce_priv;
2108  void *reduce_pend;
2109  // three compiler-generated routines (init, fini are optional):
2110  void *reduce_comb;
2111  void *reduce_init;
2112  void *reduce_fini;
2113  void *reduce_orig;
2115 
2121 typedef struct kmp_taskred_input {
2122  void *reduce_shar;
2123  void *reduce_orig;
2124  size_t reduce_size;
2125  // three compiler-generated routines (init, fini are optional):
2126  void *reduce_init;
2127  void *reduce_fini;
2128  void *reduce_comb;
2135 template <typename T> void __kmp_assign_orig(kmp_taskred_data_t &item, T &src);
2136 template <>
2137 void __kmp_assign_orig<kmp_task_red_input_t>(kmp_taskred_data_t &item,
2138  kmp_task_red_input_t &src) {
2139  item.reduce_orig = NULL;
2140 }
2141 template <>
2142 void __kmp_assign_orig<kmp_taskred_input_t>(kmp_taskred_data_t &item,
2143  kmp_taskred_input_t &src) {
2144  if (src.reduce_orig != NULL) {
2145  item.reduce_orig = src.reduce_orig;
2146  } else {
2147  item.reduce_orig = src.reduce_shar;
2148  } // non-NULL reduce_orig means new interface used
2149 }
2150 
2151 template <typename T> void __kmp_call_init(kmp_taskred_data_t &item, size_t j);
2152 template <>
2153 void __kmp_call_init<kmp_task_red_input_t>(kmp_taskred_data_t &item,
2154  size_t offset) {
2155  ((void (*)(void *))item.reduce_init)((char *)(item.reduce_priv) + offset);
2156 }
2157 template <>
2158 void __kmp_call_init<kmp_taskred_input_t>(kmp_taskred_data_t &item,
2159  size_t offset) {
2160  ((void (*)(void *, void *))item.reduce_init)(
2161  (char *)(item.reduce_priv) + offset, item.reduce_orig);
2162 }
2163 
2164 template <typename T>
2165 void *__kmp_task_reduction_init(int gtid, int num, T *data) {
2166  __kmp_assert_valid_gtid(gtid);
2167  kmp_info_t *thread = __kmp_threads[gtid];
2168  kmp_taskgroup_t *tg = thread->th.th_current_task->td_taskgroup;
2169  kmp_uint32 nth = thread->th.th_team_nproc;
2170  kmp_taskred_data_t *arr;
2171 
2172  // check input data just in case
2173  KMP_ASSERT(tg != NULL);
2174  KMP_ASSERT(data != NULL);
2175  KMP_ASSERT(num > 0);
2176  if (nth == 1) {
2177  KA_TRACE(10, ("__kmpc_task_reduction_init: T#%d, tg %p, exiting nth=1\n",
2178  gtid, tg));
2179  return (void *)tg;
2180  }
2181  KA_TRACE(10, ("__kmpc_task_reduction_init: T#%d, taskgroup %p, #items %d\n",
2182  gtid, tg, num));
2183  arr = (kmp_taskred_data_t *)__kmp_thread_malloc(
2184  thread, num * sizeof(kmp_taskred_data_t));
2185  for (int i = 0; i < num; ++i) {
2186  size_t size = data[i].reduce_size - 1;
2187  // round the size up to cache line per thread-specific item
2188  size += CACHE_LINE - size % CACHE_LINE;
2189  KMP_ASSERT(data[i].reduce_comb != NULL); // combiner is mandatory
2190  arr[i].reduce_shar = data[i].reduce_shar;
2191  arr[i].reduce_size = size;
2192  arr[i].flags = data[i].flags;
2193  arr[i].reduce_comb = data[i].reduce_comb;
2194  arr[i].reduce_init = data[i].reduce_init;
2195  arr[i].reduce_fini = data[i].reduce_fini;
2196  __kmp_assign_orig<T>(arr[i], data[i]);
2197  if (!arr[i].flags.lazy_priv) {
2198  // allocate cache-line aligned block and fill it with zeros
2199  arr[i].reduce_priv = __kmp_allocate(nth * size);
2200  arr[i].reduce_pend = (char *)(arr[i].reduce_priv) + nth * size;
2201  if (arr[i].reduce_init != NULL) {
2202  // initialize all thread-specific items
2203  for (size_t j = 0; j < nth; ++j) {
2204  __kmp_call_init<T>(arr[i], j * size);
2205  }
2206  }
2207  } else {
2208  // only allocate space for pointers now,
2209  // objects will be lazily allocated/initialized if/when requested
2210  // note that __kmp_allocate zeroes the allocated memory
2211  arr[i].reduce_priv = __kmp_allocate(nth * sizeof(void *));
2212  }
2213  }
2214  tg->reduce_data = (void *)arr;
2215  tg->reduce_num_data = num;
2216  return (void *)tg;
2217 }
2218 
2233 void *__kmpc_task_reduction_init(int gtid, int num, void *data) {
2234  return __kmp_task_reduction_init(gtid, num, (kmp_task_red_input_t *)data);
2235 }
2236 
2249 void *__kmpc_taskred_init(int gtid, int num, void *data) {
2250  return __kmp_task_reduction_init(gtid, num, (kmp_taskred_input_t *)data);
2251 }
2252 
2253 // Copy task reduction data (except for shared pointers).
2254 template <typename T>
2255 void __kmp_task_reduction_init_copy(kmp_info_t *thr, int num, T *data,
2256  kmp_taskgroup_t *tg, void *reduce_data) {
2257  kmp_taskred_data_t *arr;
2258  KA_TRACE(20, ("__kmp_task_reduction_init_copy: Th %p, init taskgroup %p,"
2259  " from data %p\n",
2260  thr, tg, reduce_data));
2261  arr = (kmp_taskred_data_t *)__kmp_thread_malloc(
2262  thr, num * sizeof(kmp_taskred_data_t));
2263  // threads will share private copies, thunk routines, sizes, flags, etc.:
2264  KMP_MEMCPY(arr, reduce_data, num * sizeof(kmp_taskred_data_t));
2265  for (int i = 0; i < num; ++i) {
2266  arr[i].reduce_shar = data[i].reduce_shar; // init unique shared pointers
2267  }
2268  tg->reduce_data = (void *)arr;
2269  tg->reduce_num_data = num;
2270 }
2271 
2281 void *__kmpc_task_reduction_get_th_data(int gtid, void *tskgrp, void *data) {
2282  __kmp_assert_valid_gtid(gtid);
2283  kmp_info_t *thread = __kmp_threads[gtid];
2284  kmp_int32 nth = thread->th.th_team_nproc;
2285  if (nth == 1)
2286  return data; // nothing to do
2287 
2288  kmp_taskgroup_t *tg = (kmp_taskgroup_t *)tskgrp;
2289  if (tg == NULL)
2290  tg = thread->th.th_current_task->td_taskgroup;
2291  KMP_ASSERT(tg != NULL);
2292  kmp_taskred_data_t *arr = (kmp_taskred_data_t *)(tg->reduce_data);
2293  kmp_int32 num = tg->reduce_num_data;
2294  kmp_int32 tid = thread->th.th_info.ds.ds_tid;
2295 
2296  KMP_ASSERT(data != NULL);
2297  while (tg != NULL) {
2298  for (int i = 0; i < num; ++i) {
2299  if (!arr[i].flags.lazy_priv) {
2300  if (data == arr[i].reduce_shar ||
2301  (data >= arr[i].reduce_priv && data < arr[i].reduce_pend))
2302  return (char *)(arr[i].reduce_priv) + tid * arr[i].reduce_size;
2303  } else {
2304  // check shared location first
2305  void **p_priv = (void **)(arr[i].reduce_priv);
2306  if (data == arr[i].reduce_shar)
2307  goto found;
2308  // check if we get some thread specific location as parameter
2309  for (int j = 0; j < nth; ++j)
2310  if (data == p_priv[j])
2311  goto found;
2312  continue; // not found, continue search
2313  found:
2314  if (p_priv[tid] == NULL) {
2315  // allocate thread specific object lazily
2316  p_priv[tid] = __kmp_allocate(arr[i].reduce_size);
2317  if (arr[i].reduce_init != NULL) {
2318  if (arr[i].reduce_orig != NULL) { // new interface
2319  ((void (*)(void *, void *))arr[i].reduce_init)(
2320  p_priv[tid], arr[i].reduce_orig);
2321  } else { // old interface (single parameter)
2322  ((void (*)(void *))arr[i].reduce_init)(p_priv[tid]);
2323  }
2324  }
2325  }
2326  return p_priv[tid];
2327  }
2328  }
2329  tg = tg->parent;
2330  arr = (kmp_taskred_data_t *)(tg->reduce_data);
2331  num = tg->reduce_num_data;
2332  }
2333  KMP_ASSERT2(0, "Unknown task reduction item");
2334  return NULL; // ERROR, this line never executed
2335 }
2336 
2337 // Finalize task reduction.
2338 // Called from __kmpc_end_taskgroup()
2339 static void __kmp_task_reduction_fini(kmp_info_t *th, kmp_taskgroup_t *tg) {
2340  kmp_int32 nth = th->th.th_team_nproc;
2341  KMP_DEBUG_ASSERT(nth > 1); // should not be called if nth == 1
2342  kmp_taskred_data_t *arr = (kmp_taskred_data_t *)tg->reduce_data;
2343  kmp_int32 num = tg->reduce_num_data;
2344  for (int i = 0; i < num; ++i) {
2345  void *sh_data = arr[i].reduce_shar;
2346  void (*f_fini)(void *) = (void (*)(void *))(arr[i].reduce_fini);
2347  void (*f_comb)(void *, void *) =
2348  (void (*)(void *, void *))(arr[i].reduce_comb);
2349  if (!arr[i].flags.lazy_priv) {
2350  void *pr_data = arr[i].reduce_priv;
2351  size_t size = arr[i].reduce_size;
2352  for (int j = 0; j < nth; ++j) {
2353  void *priv_data = (char *)pr_data + j * size;
2354  f_comb(sh_data, priv_data); // combine results
2355  if (f_fini)
2356  f_fini(priv_data); // finalize if needed
2357  }
2358  } else {
2359  void **pr_data = (void **)(arr[i].reduce_priv);
2360  for (int j = 0; j < nth; ++j) {
2361  if (pr_data[j] != NULL) {
2362  f_comb(sh_data, pr_data[j]); // combine results
2363  if (f_fini)
2364  f_fini(pr_data[j]); // finalize if needed
2365  __kmp_free(pr_data[j]);
2366  }
2367  }
2368  }
2369  __kmp_free(arr[i].reduce_priv);
2370  }
2371  __kmp_thread_free(th, arr);
2372  tg->reduce_data = NULL;
2373  tg->reduce_num_data = 0;
2374 }
2375 
2376 // Cleanup task reduction data for parallel or worksharing,
2377 // do not touch task private data other threads still working with.
2378 // Called from __kmpc_end_taskgroup()
2379 static void __kmp_task_reduction_clean(kmp_info_t *th, kmp_taskgroup_t *tg) {
2380  __kmp_thread_free(th, tg->reduce_data);
2381  tg->reduce_data = NULL;
2382  tg->reduce_num_data = 0;
2383 }
2384 
2385 template <typename T>
2386 void *__kmp_task_reduction_modifier_init(ident_t *loc, int gtid, int is_ws,
2387  int num, T *data) {
2388  __kmp_assert_valid_gtid(gtid);
2389  kmp_info_t *thr = __kmp_threads[gtid];
2390  kmp_int32 nth = thr->th.th_team_nproc;
2391  __kmpc_taskgroup(loc, gtid); // form new taskgroup first
2392  if (nth == 1) {
2393  KA_TRACE(10,
2394  ("__kmpc_reduction_modifier_init: T#%d, tg %p, exiting nth=1\n",
2395  gtid, thr->th.th_current_task->td_taskgroup));
2396  return (void *)thr->th.th_current_task->td_taskgroup;
2397  }
2398  kmp_team_t *team = thr->th.th_team;
2399  void *reduce_data;
2400  kmp_taskgroup_t *tg;
2401  reduce_data = KMP_ATOMIC_LD_RLX(&team->t.t_tg_reduce_data[is_ws]);
2402  if (reduce_data == NULL &&
2403  __kmp_atomic_compare_store(&team->t.t_tg_reduce_data[is_ws], reduce_data,
2404  (void *)1)) {
2405  // single thread enters this block to initialize common reduction data
2406  KMP_DEBUG_ASSERT(reduce_data == NULL);
2407  // first initialize own data, then make a copy other threads can use
2408  tg = (kmp_taskgroup_t *)__kmp_task_reduction_init<T>(gtid, num, data);
2409  reduce_data = __kmp_thread_malloc(thr, num * sizeof(kmp_taskred_data_t));
2410  KMP_MEMCPY(reduce_data, tg->reduce_data, num * sizeof(kmp_taskred_data_t));
2411  // fini counters should be 0 at this point
2412  KMP_DEBUG_ASSERT(KMP_ATOMIC_LD_RLX(&team->t.t_tg_fini_counter[0]) == 0);
2413  KMP_DEBUG_ASSERT(KMP_ATOMIC_LD_RLX(&team->t.t_tg_fini_counter[1]) == 0);
2414  KMP_ATOMIC_ST_REL(&team->t.t_tg_reduce_data[is_ws], reduce_data);
2415  } else {
2416  while (
2417  (reduce_data = KMP_ATOMIC_LD_ACQ(&team->t.t_tg_reduce_data[is_ws])) ==
2418  (void *)1) { // wait for task reduction initialization
2419  KMP_CPU_PAUSE();
2420  }
2421  KMP_DEBUG_ASSERT(reduce_data > (void *)1); // should be valid pointer here
2422  tg = thr->th.th_current_task->td_taskgroup;
2423  __kmp_task_reduction_init_copy<T>(thr, num, data, tg, reduce_data);
2424  }
2425  return tg;
2426 }
2427 
2444 void *__kmpc_task_reduction_modifier_init(ident_t *loc, int gtid, int is_ws,
2445  int num, void *data) {
2446  return __kmp_task_reduction_modifier_init(loc, gtid, is_ws, num,
2447  (kmp_task_red_input_t *)data);
2448 }
2449 
2464 void *__kmpc_taskred_modifier_init(ident_t *loc, int gtid, int is_ws, int num,
2465  void *data) {
2466  return __kmp_task_reduction_modifier_init(loc, gtid, is_ws, num,
2467  (kmp_taskred_input_t *)data);
2468 }
2469 
2478 void __kmpc_task_reduction_modifier_fini(ident_t *loc, int gtid, int is_ws) {
2479  __kmpc_end_taskgroup(loc, gtid);
2480 }
2481 
2482 // __kmpc_taskgroup: Start a new taskgroup
2483 void __kmpc_taskgroup(ident_t *loc, int gtid) {
2484  __kmp_assert_valid_gtid(gtid);
2485  kmp_info_t *thread = __kmp_threads[gtid];
2486  kmp_taskdata_t *taskdata = thread->th.th_current_task;
2487  kmp_taskgroup_t *tg_new =
2488  (kmp_taskgroup_t *)__kmp_thread_malloc(thread, sizeof(kmp_taskgroup_t));
2489  KA_TRACE(10, ("__kmpc_taskgroup: T#%d loc=%p group=%p\n", gtid, loc, tg_new));
2490  KMP_ATOMIC_ST_RLX(&tg_new->count, 0);
2491  KMP_ATOMIC_ST_RLX(&tg_new->cancel_request, cancel_noreq);
2492  tg_new->parent = taskdata->td_taskgroup;
2493  tg_new->reduce_data = NULL;
2494  tg_new->reduce_num_data = 0;
2495  tg_new->gomp_data = NULL;
2496  taskdata->td_taskgroup = tg_new;
2497 
2498 #if OMPT_SUPPORT && OMPT_OPTIONAL
2499  if (UNLIKELY(ompt_enabled.ompt_callback_sync_region)) {
2500  void *codeptr = OMPT_LOAD_RETURN_ADDRESS(gtid);
2501  if (!codeptr)
2502  codeptr = OMPT_GET_RETURN_ADDRESS(0);
2503  kmp_team_t *team = thread->th.th_team;
2504  ompt_data_t my_task_data = taskdata->ompt_task_info.task_data;
2505  // FIXME: I think this is wrong for lwt!
2506  ompt_data_t my_parallel_data = team->t.ompt_team_info.parallel_data;
2507 
2508  ompt_callbacks.ompt_callback(ompt_callback_sync_region)(
2509  ompt_sync_region_taskgroup, ompt_scope_begin, &(my_parallel_data),
2510  &(my_task_data), codeptr);
2511  }
2512 #endif
2513 }
2514 
2515 // __kmpc_end_taskgroup: Wait until all tasks generated by the current task
2516 // and its descendants are complete
2517 void __kmpc_end_taskgroup(ident_t *loc, int gtid) {
2518  __kmp_assert_valid_gtid(gtid);
2519  kmp_info_t *thread = __kmp_threads[gtid];
2520  kmp_taskdata_t *taskdata = thread->th.th_current_task;
2521  kmp_taskgroup_t *taskgroup = taskdata->td_taskgroup;
2522  int thread_finished = FALSE;
2523 
2524 #if OMPT_SUPPORT && OMPT_OPTIONAL
2525  kmp_team_t *team;
2526  ompt_data_t my_task_data;
2527  ompt_data_t my_parallel_data;
2528  void *codeptr = nullptr;
2529  if (UNLIKELY(ompt_enabled.enabled)) {
2530  team = thread->th.th_team;
2531  my_task_data = taskdata->ompt_task_info.task_data;
2532  // FIXME: I think this is wrong for lwt!
2533  my_parallel_data = team->t.ompt_team_info.parallel_data;
2534  codeptr = OMPT_LOAD_RETURN_ADDRESS(gtid);
2535  if (!codeptr)
2536  codeptr = OMPT_GET_RETURN_ADDRESS(0);
2537  }
2538 #endif
2539 
2540  KA_TRACE(10, ("__kmpc_end_taskgroup(enter): T#%d loc=%p\n", gtid, loc));
2541  KMP_DEBUG_ASSERT(taskgroup != NULL);
2542  KMP_SET_THREAD_STATE_BLOCK(TASKGROUP);
2543 
2544  if (__kmp_tasking_mode != tskm_immediate_exec) {
2545  // mark task as waiting not on a barrier
2546  taskdata->td_taskwait_counter += 1;
2547  taskdata->td_taskwait_ident = loc;
2548  taskdata->td_taskwait_thread = gtid + 1;
2549 #if USE_ITT_BUILD
2550  // For ITT the taskgroup wait is similar to taskwait until we need to
2551  // distinguish them
2552  void *itt_sync_obj = NULL;
2553 #if USE_ITT_NOTIFY
2554  KMP_ITT_TASKWAIT_STARTING(itt_sync_obj);
2555 #endif /* USE_ITT_NOTIFY */
2556 #endif /* USE_ITT_BUILD */
2557 
2558 #if OMPT_SUPPORT && OMPT_OPTIONAL
2559  if (UNLIKELY(ompt_enabled.ompt_callback_sync_region_wait)) {
2560  ompt_callbacks.ompt_callback(ompt_callback_sync_region_wait)(
2561  ompt_sync_region_taskgroup, ompt_scope_begin, &(my_parallel_data),
2562  &(my_task_data), codeptr);
2563  }
2564 #endif
2565 
2566  if (!taskdata->td_flags.team_serial ||
2567  (thread->th.th_task_team != NULL &&
2568  (thread->th.th_task_team->tt.tt_found_proxy_tasks ||
2569  thread->th.th_task_team->tt.tt_hidden_helper_task_encountered))) {
2570  kmp_flag_32<false, false> flag(
2571  RCAST(std::atomic<kmp_uint32> *, &(taskgroup->count)), 0U);
2572  while (KMP_ATOMIC_LD_ACQ(&taskgroup->count) != 0) {
2573  flag.execute_tasks(thread, gtid, FALSE,
2574  &thread_finished USE_ITT_BUILD_ARG(itt_sync_obj),
2575  __kmp_task_stealing_constraint);
2576  }
2577  }
2578  taskdata->td_taskwait_thread = -taskdata->td_taskwait_thread; // end waiting
2579 
2580 #if OMPT_SUPPORT && OMPT_OPTIONAL
2581  if (UNLIKELY(ompt_enabled.ompt_callback_sync_region_wait)) {
2582  ompt_callbacks.ompt_callback(ompt_callback_sync_region_wait)(
2583  ompt_sync_region_taskgroup, ompt_scope_end, &(my_parallel_data),
2584  &(my_task_data), codeptr);
2585  }
2586 #endif
2587 
2588 #if USE_ITT_BUILD
2589  KMP_ITT_TASKWAIT_FINISHED(itt_sync_obj);
2590  KMP_FSYNC_ACQUIRED(taskdata); // acquire self - sync with descendants
2591 #endif /* USE_ITT_BUILD */
2592  }
2593  KMP_DEBUG_ASSERT(taskgroup->count == 0);
2594 
2595  if (taskgroup->reduce_data != NULL &&
2596  !taskgroup->gomp_data) { // need to reduce?
2597  int cnt;
2598  void *reduce_data;
2599  kmp_team_t *t = thread->th.th_team;
2600  kmp_taskred_data_t *arr = (kmp_taskred_data_t *)taskgroup->reduce_data;
2601  // check if <priv> data of the first reduction variable shared for the team
2602  void *priv0 = arr[0].reduce_priv;
2603  if ((reduce_data = KMP_ATOMIC_LD_ACQ(&t->t.t_tg_reduce_data[0])) != NULL &&
2604  ((kmp_taskred_data_t *)reduce_data)[0].reduce_priv == priv0) {
2605  // finishing task reduction on parallel
2606  cnt = KMP_ATOMIC_INC(&t->t.t_tg_fini_counter[0]);
2607  if (cnt == thread->th.th_team_nproc - 1) {
2608  // we are the last thread passing __kmpc_reduction_modifier_fini()
2609  // finalize task reduction:
2610  __kmp_task_reduction_fini(thread, taskgroup);
2611  // cleanup fields in the team structure:
2612  // TODO: is relaxed store enough here (whole barrier should follow)?
2613  __kmp_thread_free(thread, reduce_data);
2614  KMP_ATOMIC_ST_REL(&t->t.t_tg_reduce_data[0], NULL);
2615  KMP_ATOMIC_ST_REL(&t->t.t_tg_fini_counter[0], 0);
2616  } else {
2617  // we are not the last thread passing __kmpc_reduction_modifier_fini(),
2618  // so do not finalize reduction, just clean own copy of the data
2619  __kmp_task_reduction_clean(thread, taskgroup);
2620  }
2621  } else if ((reduce_data = KMP_ATOMIC_LD_ACQ(&t->t.t_tg_reduce_data[1])) !=
2622  NULL &&
2623  ((kmp_taskred_data_t *)reduce_data)[0].reduce_priv == priv0) {
2624  // finishing task reduction on worksharing
2625  cnt = KMP_ATOMIC_INC(&t->t.t_tg_fini_counter[1]);
2626  if (cnt == thread->th.th_team_nproc - 1) {
2627  // we are the last thread passing __kmpc_reduction_modifier_fini()
2628  __kmp_task_reduction_fini(thread, taskgroup);
2629  // cleanup fields in team structure:
2630  // TODO: is relaxed store enough here (whole barrier should follow)?
2631  __kmp_thread_free(thread, reduce_data);
2632  KMP_ATOMIC_ST_REL(&t->t.t_tg_reduce_data[1], NULL);
2633  KMP_ATOMIC_ST_REL(&t->t.t_tg_fini_counter[1], 0);
2634  } else {
2635  // we are not the last thread passing __kmpc_reduction_modifier_fini(),
2636  // so do not finalize reduction, just clean own copy of the data
2637  __kmp_task_reduction_clean(thread, taskgroup);
2638  }
2639  } else {
2640  // finishing task reduction on taskgroup
2641  __kmp_task_reduction_fini(thread, taskgroup);
2642  }
2643  }
2644  // Restore parent taskgroup for the current task
2645  taskdata->td_taskgroup = taskgroup->parent;
2646  __kmp_thread_free(thread, taskgroup);
2647 
2648  KA_TRACE(10, ("__kmpc_end_taskgroup(exit): T#%d task %p finished waiting\n",
2649  gtid, taskdata));
2650 
2651 #if OMPT_SUPPORT && OMPT_OPTIONAL
2652  if (UNLIKELY(ompt_enabled.ompt_callback_sync_region)) {
2653  ompt_callbacks.ompt_callback(ompt_callback_sync_region)(
2654  ompt_sync_region_taskgroup, ompt_scope_end, &(my_parallel_data),
2655  &(my_task_data), codeptr);
2656  }
2657 #endif
2658 }
2659 
2660 // __kmp_remove_my_task: remove a task from my own deque
2661 static kmp_task_t *__kmp_remove_my_task(kmp_info_t *thread, kmp_int32 gtid,
2662  kmp_task_team_t *task_team,
2663  kmp_int32 is_constrained) {
2664  kmp_task_t *task;
2665  kmp_taskdata_t *taskdata;
2666  kmp_thread_data_t *thread_data;
2667  kmp_uint32 tail;
2668 
2669  KMP_DEBUG_ASSERT(__kmp_tasking_mode != tskm_immediate_exec);
2670  KMP_DEBUG_ASSERT(task_team->tt.tt_threads_data !=
2671  NULL); // Caller should check this condition
2672 
2673  thread_data = &task_team->tt.tt_threads_data[__kmp_tid_from_gtid(gtid)];
2674 
2675  KA_TRACE(10, ("__kmp_remove_my_task(enter): T#%d ntasks=%d head=%u tail=%u\n",
2676  gtid, thread_data->td.td_deque_ntasks,
2677  thread_data->td.td_deque_head, thread_data->td.td_deque_tail));
2678 
2679  if (TCR_4(thread_data->td.td_deque_ntasks) == 0) {
2680  KA_TRACE(10,
2681  ("__kmp_remove_my_task(exit #1): T#%d No tasks to remove: "
2682  "ntasks=%d head=%u tail=%u\n",
2683  gtid, thread_data->td.td_deque_ntasks,
2684  thread_data->td.td_deque_head, thread_data->td.td_deque_tail));
2685  return NULL;
2686  }
2687 
2688  __kmp_acquire_bootstrap_lock(&thread_data->td.td_deque_lock);
2689 
2690  if (TCR_4(thread_data->td.td_deque_ntasks) == 0) {
2691  __kmp_release_bootstrap_lock(&thread_data->td.td_deque_lock);
2692  KA_TRACE(10,
2693  ("__kmp_remove_my_task(exit #2): T#%d No tasks to remove: "
2694  "ntasks=%d head=%u tail=%u\n",
2695  gtid, thread_data->td.td_deque_ntasks,
2696  thread_data->td.td_deque_head, thread_data->td.td_deque_tail));
2697  return NULL;
2698  }
2699 
2700  tail = (thread_data->td.td_deque_tail - 1) &
2701  TASK_DEQUE_MASK(thread_data->td); // Wrap index.
2702  taskdata = thread_data->td.td_deque[tail];
2703 
2704  if (!__kmp_task_is_allowed(gtid, is_constrained, taskdata,
2705  thread->th.th_current_task)) {
2706  // The TSC does not allow to steal victim task
2707  __kmp_release_bootstrap_lock(&thread_data->td.td_deque_lock);
2708  KA_TRACE(10,
2709  ("__kmp_remove_my_task(exit #3): T#%d TSC blocks tail task: "
2710  "ntasks=%d head=%u tail=%u\n",
2711  gtid, thread_data->td.td_deque_ntasks,
2712  thread_data->td.td_deque_head, thread_data->td.td_deque_tail));
2713  return NULL;
2714  }
2715 
2716  thread_data->td.td_deque_tail = tail;
2717  TCW_4(thread_data->td.td_deque_ntasks, thread_data->td.td_deque_ntasks - 1);
2718 
2719  __kmp_release_bootstrap_lock(&thread_data->td.td_deque_lock);
2720 
2721  KA_TRACE(10, ("__kmp_remove_my_task(exit #4): T#%d task %p removed: "
2722  "ntasks=%d head=%u tail=%u\n",
2723  gtid, taskdata, thread_data->td.td_deque_ntasks,
2724  thread_data->td.td_deque_head, thread_data->td.td_deque_tail));
2725 
2726  task = KMP_TASKDATA_TO_TASK(taskdata);
2727  return task;
2728 }
2729 
2730 // __kmp_steal_task: remove a task from another thread's deque
2731 // Assume that calling thread has already checked existence of
2732 // task_team thread_data before calling this routine.
2733 static kmp_task_t *__kmp_steal_task(kmp_info_t *victim_thr, kmp_int32 gtid,
2734  kmp_task_team_t *task_team,
2735  std::atomic<kmp_int32> *unfinished_threads,
2736  int *thread_finished,
2737  kmp_int32 is_constrained) {
2738  kmp_task_t *task;
2739  kmp_taskdata_t *taskdata;
2740  kmp_taskdata_t *current;
2741  kmp_thread_data_t *victim_td, *threads_data;
2742  kmp_int32 target;
2743  kmp_int32 victim_tid;
2744 
2745  KMP_DEBUG_ASSERT(__kmp_tasking_mode != tskm_immediate_exec);
2746 
2747  threads_data = task_team->tt.tt_threads_data;
2748  KMP_DEBUG_ASSERT(threads_data != NULL); // Caller should check this condition
2749 
2750  victim_tid = victim_thr->th.th_info.ds.ds_tid;
2751  victim_td = &threads_data[victim_tid];
2752 
2753  KA_TRACE(10, ("__kmp_steal_task(enter): T#%d try to steal from T#%d: "
2754  "task_team=%p ntasks=%d head=%u tail=%u\n",
2755  gtid, __kmp_gtid_from_thread(victim_thr), task_team,
2756  victim_td->td.td_deque_ntasks, victim_td->td.td_deque_head,
2757  victim_td->td.td_deque_tail));
2758 
2759  if (TCR_4(victim_td->td.td_deque_ntasks) == 0) {
2760  KA_TRACE(10, ("__kmp_steal_task(exit #1): T#%d could not steal from T#%d: "
2761  "task_team=%p ntasks=%d head=%u tail=%u\n",
2762  gtid, __kmp_gtid_from_thread(victim_thr), task_team,
2763  victim_td->td.td_deque_ntasks, victim_td->td.td_deque_head,
2764  victim_td->td.td_deque_tail));
2765  return NULL;
2766  }
2767 
2768  __kmp_acquire_bootstrap_lock(&victim_td->td.td_deque_lock);
2769 
2770  int ntasks = TCR_4(victim_td->td.td_deque_ntasks);
2771  // Check again after we acquire the lock
2772  if (ntasks == 0) {
2773  __kmp_release_bootstrap_lock(&victim_td->td.td_deque_lock);
2774  KA_TRACE(10, ("__kmp_steal_task(exit #2): T#%d could not steal from T#%d: "
2775  "task_team=%p ntasks=%d head=%u tail=%u\n",
2776  gtid, __kmp_gtid_from_thread(victim_thr), task_team, ntasks,
2777  victim_td->td.td_deque_head, victim_td->td.td_deque_tail));
2778  return NULL;
2779  }
2780 
2781  KMP_DEBUG_ASSERT(victim_td->td.td_deque != NULL);
2782  current = __kmp_threads[gtid]->th.th_current_task;
2783  taskdata = victim_td->td.td_deque[victim_td->td.td_deque_head];
2784  if (__kmp_task_is_allowed(gtid, is_constrained, taskdata, current)) {
2785  // Bump head pointer and Wrap.
2786  victim_td->td.td_deque_head =
2787  (victim_td->td.td_deque_head + 1) & TASK_DEQUE_MASK(victim_td->td);
2788  } else {
2789  if (!task_team->tt.tt_untied_task_encountered) {
2790  // The TSC does not allow to steal victim task
2791  __kmp_release_bootstrap_lock(&victim_td->td.td_deque_lock);
2792  KA_TRACE(10, ("__kmp_steal_task(exit #3): T#%d could not steal from "
2793  "T#%d: task_team=%p ntasks=%d head=%u tail=%u\n",
2794  gtid, __kmp_gtid_from_thread(victim_thr), task_team, ntasks,
2795  victim_td->td.td_deque_head, victim_td->td.td_deque_tail));
2796  return NULL;
2797  }
2798  int i;
2799  // walk through victim's deque trying to steal any task
2800  target = victim_td->td.td_deque_head;
2801  taskdata = NULL;
2802  for (i = 1; i < ntasks; ++i) {
2803  target = (target + 1) & TASK_DEQUE_MASK(victim_td->td);
2804  taskdata = victim_td->td.td_deque[target];
2805  if (__kmp_task_is_allowed(gtid, is_constrained, taskdata, current)) {
2806  break; // found victim task
2807  } else {
2808  taskdata = NULL;
2809  }
2810  }
2811  if (taskdata == NULL) {
2812  // No appropriate candidate to steal found
2813  __kmp_release_bootstrap_lock(&victim_td->td.td_deque_lock);
2814  KA_TRACE(10, ("__kmp_steal_task(exit #4): T#%d could not steal from "
2815  "T#%d: task_team=%p ntasks=%d head=%u tail=%u\n",
2816  gtid, __kmp_gtid_from_thread(victim_thr), task_team, ntasks,
2817  victim_td->td.td_deque_head, victim_td->td.td_deque_tail));
2818  return NULL;
2819  }
2820  int prev = target;
2821  for (i = i + 1; i < ntasks; ++i) {
2822  // shift remaining tasks in the deque left by 1
2823  target = (target + 1) & TASK_DEQUE_MASK(victim_td->td);
2824  victim_td->td.td_deque[prev] = victim_td->td.td_deque[target];
2825  prev = target;
2826  }
2827  KMP_DEBUG_ASSERT(
2828  victim_td->td.td_deque_tail ==
2829  (kmp_uint32)((target + 1) & TASK_DEQUE_MASK(victim_td->td)));
2830  victim_td->td.td_deque_tail = target; // tail -= 1 (wrapped))
2831  }
2832  if (*thread_finished) {
2833  // We need to un-mark this victim as a finished victim. This must be done
2834  // before releasing the lock, or else other threads (starting with the
2835  // primary thread victim) might be prematurely released from the barrier!!!
2836  kmp_int32 count;
2837 
2838  count = KMP_ATOMIC_INC(unfinished_threads);
2839 
2840  KA_TRACE(
2841  20,
2842  ("__kmp_steal_task: T#%d inc unfinished_threads to %d: task_team=%p\n",
2843  gtid, count + 1, task_team));
2844 
2845  *thread_finished = FALSE;
2846  }
2847  TCW_4(victim_td->td.td_deque_ntasks, ntasks - 1);
2848 
2849  __kmp_release_bootstrap_lock(&victim_td->td.td_deque_lock);
2850 
2851  KMP_COUNT_BLOCK(TASK_stolen);
2852  KA_TRACE(10,
2853  ("__kmp_steal_task(exit #5): T#%d stole task %p from T#%d: "
2854  "task_team=%p ntasks=%d head=%u tail=%u\n",
2855  gtid, taskdata, __kmp_gtid_from_thread(victim_thr), task_team,
2856  ntasks, victim_td->td.td_deque_head, victim_td->td.td_deque_tail));
2857 
2858  task = KMP_TASKDATA_TO_TASK(taskdata);
2859  return task;
2860 }
2861 
2862 // __kmp_execute_tasks_template: Choose and execute tasks until either the
2863 // condition is statisfied (return true) or there are none left (return false).
2864 //
2865 // final_spin is TRUE if this is the spin at the release barrier.
2866 // thread_finished indicates whether the thread is finished executing all
2867 // the tasks it has on its deque, and is at the release barrier.
2868 // spinner is the location on which to spin.
2869 // spinner == NULL means only execute a single task and return.
2870 // checker is the value to check to terminate the spin.
2871 template <class C>
2872 static inline int __kmp_execute_tasks_template(
2873  kmp_info_t *thread, kmp_int32 gtid, C *flag, int final_spin,
2874  int *thread_finished USE_ITT_BUILD_ARG(void *itt_sync_obj),
2875  kmp_int32 is_constrained) {
2876  kmp_task_team_t *task_team = thread->th.th_task_team;
2877  kmp_thread_data_t *threads_data;
2878  kmp_task_t *task;
2879  kmp_info_t *other_thread;
2880  kmp_taskdata_t *current_task = thread->th.th_current_task;
2881  std::atomic<kmp_int32> *unfinished_threads;
2882  kmp_int32 nthreads, victim_tid = -2, use_own_tasks = 1, new_victim = 0,
2883  tid = thread->th.th_info.ds.ds_tid;
2884 
2885  KMP_DEBUG_ASSERT(__kmp_tasking_mode != tskm_immediate_exec);
2886  KMP_DEBUG_ASSERT(thread == __kmp_threads[gtid]);
2887 
2888  if (task_team == NULL || current_task == NULL)
2889  return FALSE;
2890 
2891  KA_TRACE(15, ("__kmp_execute_tasks_template(enter): T#%d final_spin=%d "
2892  "*thread_finished=%d\n",
2893  gtid, final_spin, *thread_finished));
2894 
2895  thread->th.th_reap_state = KMP_NOT_SAFE_TO_REAP;
2896  threads_data = (kmp_thread_data_t *)TCR_PTR(task_team->tt.tt_threads_data);
2897 
2898  KMP_DEBUG_ASSERT(threads_data != NULL);
2899 
2900  nthreads = task_team->tt.tt_nproc;
2901  unfinished_threads = &(task_team->tt.tt_unfinished_threads);
2902  KMP_DEBUG_ASSERT(nthreads > 1 || task_team->tt.tt_found_proxy_tasks ||
2903  task_team->tt.tt_hidden_helper_task_encountered);
2904  KMP_DEBUG_ASSERT(*unfinished_threads >= 0);
2905 
2906  while (1) { // Outer loop keeps trying to find tasks in case of single thread
2907  // getting tasks from target constructs
2908  while (1) { // Inner loop to find a task and execute it
2909  task = NULL;
2910  if (use_own_tasks) { // check on own queue first
2911  task = __kmp_remove_my_task(thread, gtid, task_team, is_constrained);
2912  }
2913  if ((task == NULL) && (nthreads > 1)) { // Steal a task
2914  int asleep = 1;
2915  use_own_tasks = 0;
2916  // Try to steal from the last place I stole from successfully.
2917  if (victim_tid == -2) { // haven't stolen anything yet
2918  victim_tid = threads_data[tid].td.td_deque_last_stolen;
2919  if (victim_tid !=
2920  -1) // if we have a last stolen from victim, get the thread
2921  other_thread = threads_data[victim_tid].td.td_thr;
2922  }
2923  if (victim_tid != -1) { // found last victim
2924  asleep = 0;
2925  } else if (!new_victim) { // no recent steals and we haven't already
2926  // used a new victim; select a random thread
2927  do { // Find a different thread to steal work from.
2928  // Pick a random thread. Initial plan was to cycle through all the
2929  // threads, and only return if we tried to steal from every thread,
2930  // and failed. Arch says that's not such a great idea.
2931  victim_tid = __kmp_get_random(thread) % (nthreads - 1);
2932  if (victim_tid >= tid) {
2933  ++victim_tid; // Adjusts random distribution to exclude self
2934  }
2935  // Found a potential victim
2936  other_thread = threads_data[victim_tid].td.td_thr;
2937  // There is a slight chance that __kmp_enable_tasking() did not wake
2938  // up all threads waiting at the barrier. If victim is sleeping,
2939  // then wake it up. Since we were going to pay the cache miss
2940  // penalty for referencing another thread's kmp_info_t struct
2941  // anyway,
2942  // the check shouldn't cost too much performance at this point. In
2943  // extra barrier mode, tasks do not sleep at the separate tasking
2944  // barrier, so this isn't a problem.
2945  asleep = 0;
2946  if ((__kmp_tasking_mode == tskm_task_teams) &&
2947  (__kmp_dflt_blocktime != KMP_MAX_BLOCKTIME) &&
2948  (TCR_PTR(CCAST(void *, other_thread->th.th_sleep_loc)) !=
2949  NULL)) {
2950  asleep = 1;
2951  __kmp_null_resume_wrapper(__kmp_gtid_from_thread(other_thread),
2952  other_thread->th.th_sleep_loc);
2953  // A sleeping thread should not have any tasks on it's queue.
2954  // There is a slight possibility that it resumes, steals a task
2955  // from another thread, which spawns more tasks, all in the time
2956  // that it takes this thread to check => don't write an assertion
2957  // that the victim's queue is empty. Try stealing from a
2958  // different thread.
2959  }
2960  } while (asleep);
2961  }
2962 
2963  if (!asleep) {
2964  // We have a victim to try to steal from
2965  task = __kmp_steal_task(other_thread, gtid, task_team,
2966  unfinished_threads, thread_finished,
2967  is_constrained);
2968  }
2969  if (task != NULL) { // set last stolen to victim
2970  if (threads_data[tid].td.td_deque_last_stolen != victim_tid) {
2971  threads_data[tid].td.td_deque_last_stolen = victim_tid;
2972  // The pre-refactored code did not try more than 1 successful new
2973  // vicitm, unless the last one generated more local tasks;
2974  // new_victim keeps track of this
2975  new_victim = 1;
2976  }
2977  } else { // No tasks found; unset last_stolen
2978  KMP_CHECK_UPDATE(threads_data[tid].td.td_deque_last_stolen, -1);
2979  victim_tid = -2; // no successful victim found
2980  }
2981  }
2982 
2983  if (task == NULL)
2984  break; // break out of tasking loop
2985 
2986 // Found a task; execute it
2987 #if USE_ITT_BUILD && USE_ITT_NOTIFY
2988  if (__itt_sync_create_ptr || KMP_ITT_DEBUG) {
2989  if (itt_sync_obj == NULL) { // we are at fork barrier where we could not
2990  // get the object reliably
2991  itt_sync_obj = __kmp_itt_barrier_object(gtid, bs_forkjoin_barrier);
2992  }
2993  __kmp_itt_task_starting(itt_sync_obj);
2994  }
2995 #endif /* USE_ITT_BUILD && USE_ITT_NOTIFY */
2996  __kmp_invoke_task(gtid, task, current_task);
2997 #if USE_ITT_BUILD
2998  if (itt_sync_obj != NULL)
2999  __kmp_itt_task_finished(itt_sync_obj);
3000 #endif /* USE_ITT_BUILD */
3001  // If this thread is only partway through the barrier and the condition is
3002  // met, then return now, so that the barrier gather/release pattern can
3003  // proceed. If this thread is in the last spin loop in the barrier,
3004  // waiting to be released, we know that the termination condition will not
3005  // be satisfied, so don't waste any cycles checking it.
3006  if (flag == NULL || (!final_spin && flag->done_check())) {
3007  KA_TRACE(
3008  15,
3009  ("__kmp_execute_tasks_template: T#%d spin condition satisfied\n",
3010  gtid));
3011  return TRUE;
3012  }
3013  if (thread->th.th_task_team == NULL) {
3014  break;
3015  }
3016  KMP_YIELD(__kmp_library == library_throughput); // Yield before next task
3017  // If execution of a stolen task results in more tasks being placed on our
3018  // run queue, reset use_own_tasks
3019  if (!use_own_tasks && TCR_4(threads_data[tid].td.td_deque_ntasks) != 0) {
3020  KA_TRACE(20, ("__kmp_execute_tasks_template: T#%d stolen task spawned "
3021  "other tasks, restart\n",
3022  gtid));
3023  use_own_tasks = 1;
3024  new_victim = 0;
3025  }
3026  }
3027 
3028  // The task source has been exhausted. If in final spin loop of barrier,
3029  // check if termination condition is satisfied. The work queue may be empty
3030  // but there might be proxy tasks still executing.
3031  if (final_spin &&
3032  KMP_ATOMIC_LD_ACQ(&current_task->td_incomplete_child_tasks) == 0) {
3033  // First, decrement the #unfinished threads, if that has not already been
3034  // done. This decrement might be to the spin location, and result in the
3035  // termination condition being satisfied.
3036  if (!*thread_finished) {
3037  kmp_int32 count;
3038 
3039  count = KMP_ATOMIC_DEC(unfinished_threads) - 1;
3040  KA_TRACE(20, ("__kmp_execute_tasks_template: T#%d dec "
3041  "unfinished_threads to %d task_team=%p\n",
3042  gtid, count, task_team));
3043  *thread_finished = TRUE;
3044  }
3045 
3046  // It is now unsafe to reference thread->th.th_team !!!
3047  // Decrementing task_team->tt.tt_unfinished_threads can allow the primary
3048  // thread to pass through the barrier, where it might reset each thread's
3049  // th.th_team field for the next parallel region. If we can steal more
3050  // work, we know that this has not happened yet.
3051  if (flag != NULL && flag->done_check()) {
3052  KA_TRACE(
3053  15,
3054  ("__kmp_execute_tasks_template: T#%d spin condition satisfied\n",
3055  gtid));
3056  return TRUE;
3057  }
3058  }
3059 
3060  // If this thread's task team is NULL, primary thread has recognized that
3061  // there are no more tasks; bail out
3062  if (thread->th.th_task_team == NULL) {
3063  KA_TRACE(15,
3064  ("__kmp_execute_tasks_template: T#%d no more tasks\n", gtid));
3065  return FALSE;
3066  }
3067 
3068  // We could be getting tasks from target constructs; if this is the only
3069  // thread, keep trying to execute tasks from own queue
3070  if (nthreads == 1 &&
3071  KMP_ATOMIC_LD_ACQ(&current_task->td_incomplete_child_tasks))
3072  use_own_tasks = 1;
3073  else {
3074  KA_TRACE(15,
3075  ("__kmp_execute_tasks_template: T#%d can't find work\n", gtid));
3076  return FALSE;
3077  }
3078  }
3079 }
3080 
3081 template <bool C, bool S>
3082 int __kmp_execute_tasks_32(
3083  kmp_info_t *thread, kmp_int32 gtid, kmp_flag_32<C, S> *flag, int final_spin,
3084  int *thread_finished USE_ITT_BUILD_ARG(void *itt_sync_obj),
3085  kmp_int32 is_constrained) {
3086  return __kmp_execute_tasks_template(
3087  thread, gtid, flag, final_spin,
3088  thread_finished USE_ITT_BUILD_ARG(itt_sync_obj), is_constrained);
3089 }
3090 
3091 template <bool C, bool S>
3092 int __kmp_execute_tasks_64(
3093  kmp_info_t *thread, kmp_int32 gtid, kmp_flag_64<C, S> *flag, int final_spin,
3094  int *thread_finished USE_ITT_BUILD_ARG(void *itt_sync_obj),
3095  kmp_int32 is_constrained) {
3096  return __kmp_execute_tasks_template(
3097  thread, gtid, flag, final_spin,
3098  thread_finished USE_ITT_BUILD_ARG(itt_sync_obj), is_constrained);
3099 }
3100 
3101 int __kmp_execute_tasks_oncore(
3102  kmp_info_t *thread, kmp_int32 gtid, kmp_flag_oncore *flag, int final_spin,
3103  int *thread_finished USE_ITT_BUILD_ARG(void *itt_sync_obj),
3104  kmp_int32 is_constrained) {
3105  return __kmp_execute_tasks_template(
3106  thread, gtid, flag, final_spin,
3107  thread_finished USE_ITT_BUILD_ARG(itt_sync_obj), is_constrained);
3108 }
3109 
3110 template int
3111 __kmp_execute_tasks_32<false, false>(kmp_info_t *, kmp_int32,
3112  kmp_flag_32<false, false> *, int,
3113  int *USE_ITT_BUILD_ARG(void *), kmp_int32);
3114 
3115 template int __kmp_execute_tasks_64<false, true>(kmp_info_t *, kmp_int32,
3116  kmp_flag_64<false, true> *,
3117  int,
3118  int *USE_ITT_BUILD_ARG(void *),
3119  kmp_int32);
3120 
3121 template int __kmp_execute_tasks_64<true, false>(kmp_info_t *, kmp_int32,
3122  kmp_flag_64<true, false> *,
3123  int,
3124  int *USE_ITT_BUILD_ARG(void *),
3125  kmp_int32);
3126 
3127 // __kmp_enable_tasking: Allocate task team and resume threads sleeping at the
3128 // next barrier so they can assist in executing enqueued tasks.
3129 // First thread in allocates the task team atomically.
3130 static void __kmp_enable_tasking(kmp_task_team_t *task_team,
3131  kmp_info_t *this_thr) {
3132  kmp_thread_data_t *threads_data;
3133  int nthreads, i, is_init_thread;
3134 
3135  KA_TRACE(10, ("__kmp_enable_tasking(enter): T#%d\n",
3136  __kmp_gtid_from_thread(this_thr)));
3137 
3138  KMP_DEBUG_ASSERT(task_team != NULL);
3139  KMP_DEBUG_ASSERT(this_thr->th.th_team != NULL);
3140 
3141  nthreads = task_team->tt.tt_nproc;
3142  KMP_DEBUG_ASSERT(nthreads > 0);
3143  KMP_DEBUG_ASSERT(nthreads == this_thr->th.th_team->t.t_nproc);
3144 
3145  // Allocate or increase the size of threads_data if necessary
3146  is_init_thread = __kmp_realloc_task_threads_data(this_thr, task_team);
3147 
3148  if (!is_init_thread) {
3149  // Some other thread already set up the array.
3150  KA_TRACE(
3151  20,
3152  ("__kmp_enable_tasking(exit): T#%d: threads array already set up.\n",
3153  __kmp_gtid_from_thread(this_thr)));
3154  return;
3155  }
3156  threads_data = (kmp_thread_data_t *)TCR_PTR(task_team->tt.tt_threads_data);
3157  KMP_DEBUG_ASSERT(threads_data != NULL);
3158 
3159  if (__kmp_tasking_mode == tskm_task_teams &&
3160  (__kmp_dflt_blocktime != KMP_MAX_BLOCKTIME)) {
3161  // Release any threads sleeping at the barrier, so that they can steal
3162  // tasks and execute them. In extra barrier mode, tasks do not sleep
3163  // at the separate tasking barrier, so this isn't a problem.
3164  for (i = 0; i < nthreads; i++) {
3165  volatile void *sleep_loc;
3166  kmp_info_t *thread = threads_data[i].td.td_thr;
3167 
3168  if (i == this_thr->th.th_info.ds.ds_tid) {
3169  continue;
3170  }
3171  // Since we haven't locked the thread's suspend mutex lock at this
3172  // point, there is a small window where a thread might be putting
3173  // itself to sleep, but hasn't set the th_sleep_loc field yet.
3174  // To work around this, __kmp_execute_tasks_template() periodically checks
3175  // see if other threads are sleeping (using the same random mechanism that
3176  // is used for task stealing) and awakens them if they are.
3177  if ((sleep_loc = TCR_PTR(CCAST(void *, thread->th.th_sleep_loc))) !=
3178  NULL) {
3179  KF_TRACE(50, ("__kmp_enable_tasking: T#%d waking up thread T#%d\n",
3180  __kmp_gtid_from_thread(this_thr),
3181  __kmp_gtid_from_thread(thread)));
3182  __kmp_null_resume_wrapper(__kmp_gtid_from_thread(thread), sleep_loc);
3183  } else {
3184  KF_TRACE(50, ("__kmp_enable_tasking: T#%d don't wake up thread T#%d\n",
3185  __kmp_gtid_from_thread(this_thr),
3186  __kmp_gtid_from_thread(thread)));
3187  }
3188  }
3189  }
3190 
3191  KA_TRACE(10, ("__kmp_enable_tasking(exit): T#%d\n",
3192  __kmp_gtid_from_thread(this_thr)));
3193 }
3194 
3195 /* // TODO: Check the comment consistency
3196  * Utility routines for "task teams". A task team (kmp_task_t) is kind of
3197  * like a shadow of the kmp_team_t data struct, with a different lifetime.
3198  * After a child * thread checks into a barrier and calls __kmp_release() from
3199  * the particular variant of __kmp_<barrier_kind>_barrier_gather(), it can no
3200  * longer assume that the kmp_team_t structure is intact (at any moment, the
3201  * primary thread may exit the barrier code and free the team data structure,
3202  * and return the threads to the thread pool).
3203  *
3204  * This does not work with the tasking code, as the thread is still
3205  * expected to participate in the execution of any tasks that may have been
3206  * spawned my a member of the team, and the thread still needs access to all
3207  * to each thread in the team, so that it can steal work from it.
3208  *
3209  * Enter the existence of the kmp_task_team_t struct. It employs a reference
3210  * counting mechanism, and is allocated by the primary thread before calling
3211  * __kmp_<barrier_kind>_release, and then is release by the last thread to
3212  * exit __kmp_<barrier_kind>_release at the next barrier. I.e. the lifetimes
3213  * of the kmp_task_team_t structs for consecutive barriers can overlap
3214  * (and will, unless the primary thread is the last thread to exit the barrier
3215  * release phase, which is not typical). The existence of such a struct is
3216  * useful outside the context of tasking.
3217  *
3218  * We currently use the existence of the threads array as an indicator that
3219  * tasks were spawned since the last barrier. If the structure is to be
3220  * useful outside the context of tasking, then this will have to change, but
3221  * not setting the field minimizes the performance impact of tasking on
3222  * barriers, when no explicit tasks were spawned (pushed, actually).
3223  */
3224 
3225 static kmp_task_team_t *__kmp_free_task_teams =
3226  NULL; // Free list for task_team data structures
3227 // Lock for task team data structures
3228 kmp_bootstrap_lock_t __kmp_task_team_lock =
3229  KMP_BOOTSTRAP_LOCK_INITIALIZER(__kmp_task_team_lock);
3230 
3231 // __kmp_alloc_task_deque:
3232 // Allocates a task deque for a particular thread, and initialize the necessary
3233 // data structures relating to the deque. This only happens once per thread
3234 // per task team since task teams are recycled. No lock is needed during
3235 // allocation since each thread allocates its own deque.
3236 static void __kmp_alloc_task_deque(kmp_info_t *thread,
3237  kmp_thread_data_t *thread_data) {
3238  __kmp_init_bootstrap_lock(&thread_data->td.td_deque_lock);
3239  KMP_DEBUG_ASSERT(thread_data->td.td_deque == NULL);
3240 
3241  // Initialize last stolen task field to "none"
3242  thread_data->td.td_deque_last_stolen = -1;
3243 
3244  KMP_DEBUG_ASSERT(TCR_4(thread_data->td.td_deque_ntasks) == 0);
3245  KMP_DEBUG_ASSERT(thread_data->td.td_deque_head == 0);
3246  KMP_DEBUG_ASSERT(thread_data->td.td_deque_tail == 0);
3247 
3248  KE_TRACE(
3249  10,
3250  ("__kmp_alloc_task_deque: T#%d allocating deque[%d] for thread_data %p\n",
3251  __kmp_gtid_from_thread(thread), INITIAL_TASK_DEQUE_SIZE, thread_data));
3252  // Allocate space for task deque, and zero the deque
3253  // Cannot use __kmp_thread_calloc() because threads not around for
3254  // kmp_reap_task_team( ).
3255  thread_data->td.td_deque = (kmp_taskdata_t **)__kmp_allocate(
3256  INITIAL_TASK_DEQUE_SIZE * sizeof(kmp_taskdata_t *));
3257  thread_data->td.td_deque_size = INITIAL_TASK_DEQUE_SIZE;
3258 }
3259 
3260 // __kmp_free_task_deque:
3261 // Deallocates a task deque for a particular thread. Happens at library
3262 // deallocation so don't need to reset all thread data fields.
3263 static void __kmp_free_task_deque(kmp_thread_data_t *thread_data) {
3264  if (thread_data->td.td_deque != NULL) {
3265  __kmp_acquire_bootstrap_lock(&thread_data->td.td_deque_lock);
3266  TCW_4(thread_data->td.td_deque_ntasks, 0);
3267  __kmp_free(thread_data->td.td_deque);
3268  thread_data->td.td_deque = NULL;
3269  __kmp_release_bootstrap_lock(&thread_data->td.td_deque_lock);
3270  }
3271 
3272 #ifdef BUILD_TIED_TASK_STACK
3273  // GEH: Figure out what to do here for td_susp_tied_tasks
3274  if (thread_data->td.td_susp_tied_tasks.ts_entries != TASK_STACK_EMPTY) {
3275  __kmp_free_task_stack(__kmp_thread_from_gtid(gtid), thread_data);
3276  }
3277 #endif // BUILD_TIED_TASK_STACK
3278 }
3279 
3280 // __kmp_realloc_task_threads_data:
3281 // Allocates a threads_data array for a task team, either by allocating an
3282 // initial array or enlarging an existing array. Only the first thread to get
3283 // the lock allocs or enlarges the array and re-initializes the array elements.
3284 // That thread returns "TRUE", the rest return "FALSE".
3285 // Assumes that the new array size is given by task_team -> tt.tt_nproc.
3286 // The current size is given by task_team -> tt.tt_max_threads.
3287 static int __kmp_realloc_task_threads_data(kmp_info_t *thread,
3288  kmp_task_team_t *task_team) {
3289  kmp_thread_data_t **threads_data_p;
3290  kmp_int32 nthreads, maxthreads;
3291  int is_init_thread = FALSE;
3292 
3293  if (TCR_4(task_team->tt.tt_found_tasks)) {
3294  // Already reallocated and initialized.
3295  return FALSE;
3296  }
3297 
3298  threads_data_p = &task_team->tt.tt_threads_data;
3299  nthreads = task_team->tt.tt_nproc;
3300  maxthreads = task_team->tt.tt_max_threads;
3301 
3302  // All threads must lock when they encounter the first task of the implicit
3303  // task region to make sure threads_data fields are (re)initialized before
3304  // used.
3305  __kmp_acquire_bootstrap_lock(&task_team->tt.tt_threads_lock);
3306 
3307  if (!TCR_4(task_team->tt.tt_found_tasks)) {
3308  // first thread to enable tasking
3309  kmp_team_t *team = thread->th.th_team;
3310  int i;
3311 
3312  is_init_thread = TRUE;
3313  if (maxthreads < nthreads) {
3314 
3315  if (*threads_data_p != NULL) {
3316  kmp_thread_data_t *old_data = *threads_data_p;
3317  kmp_thread_data_t *new_data = NULL;
3318 
3319  KE_TRACE(
3320  10,
3321  ("__kmp_realloc_task_threads_data: T#%d reallocating "
3322  "threads data for task_team %p, new_size = %d, old_size = %d\n",
3323  __kmp_gtid_from_thread(thread), task_team, nthreads, maxthreads));
3324  // Reallocate threads_data to have more elements than current array
3325  // Cannot use __kmp_thread_realloc() because threads not around for
3326  // kmp_reap_task_team( ). Note all new array entries are initialized
3327  // to zero by __kmp_allocate().
3328  new_data = (kmp_thread_data_t *)__kmp_allocate(
3329  nthreads * sizeof(kmp_thread_data_t));
3330  // copy old data to new data
3331  KMP_MEMCPY_S((void *)new_data, nthreads * sizeof(kmp_thread_data_t),
3332  (void *)old_data, maxthreads * sizeof(kmp_thread_data_t));
3333 
3334 #ifdef BUILD_TIED_TASK_STACK
3335  // GEH: Figure out if this is the right thing to do
3336  for (i = maxthreads; i < nthreads; i++) {
3337  kmp_thread_data_t *thread_data = &(*threads_data_p)[i];
3338  __kmp_init_task_stack(__kmp_gtid_from_thread(thread), thread_data);
3339  }
3340 #endif // BUILD_TIED_TASK_STACK
3341  // Install the new data and free the old data
3342  (*threads_data_p) = new_data;
3343  __kmp_free(old_data);
3344  } else {
3345  KE_TRACE(10, ("__kmp_realloc_task_threads_data: T#%d allocating "
3346  "threads data for task_team %p, size = %d\n",
3347  __kmp_gtid_from_thread(thread), task_team, nthreads));
3348  // Make the initial allocate for threads_data array, and zero entries
3349  // Cannot use __kmp_thread_calloc() because threads not around for
3350  // kmp_reap_task_team( ).
3351  *threads_data_p = (kmp_thread_data_t *)__kmp_allocate(
3352  nthreads * sizeof(kmp_thread_data_t));
3353 #ifdef BUILD_TIED_TASK_STACK
3354  // GEH: Figure out if this is the right thing to do
3355  for (i = 0; i < nthreads; i++) {
3356  kmp_thread_data_t *thread_data = &(*threads_data_p)[i];
3357  __kmp_init_task_stack(__kmp_gtid_from_thread(thread), thread_data);
3358  }
3359 #endif // BUILD_TIED_TASK_STACK
3360  }
3361  task_team->tt.tt_max_threads = nthreads;
3362  } else {
3363  // If array has (more than) enough elements, go ahead and use it
3364  KMP_DEBUG_ASSERT(*threads_data_p != NULL);
3365  }
3366 
3367  // initialize threads_data pointers back to thread_info structures
3368  for (i = 0; i < nthreads; i++) {
3369  kmp_thread_data_t *thread_data = &(*threads_data_p)[i];
3370  thread_data->td.td_thr = team->t.t_threads[i];
3371 
3372  if (thread_data->td.td_deque_last_stolen >= nthreads) {
3373  // The last stolen field survives across teams / barrier, and the number
3374  // of threads may have changed. It's possible (likely?) that a new
3375  // parallel region will exhibit the same behavior as previous region.
3376  thread_data->td.td_deque_last_stolen = -1;
3377  }
3378  }
3379 
3380  KMP_MB();
3381  TCW_SYNC_4(task_team->tt.tt_found_tasks, TRUE);
3382  }
3383 
3384  __kmp_release_bootstrap_lock(&task_team->tt.tt_threads_lock);
3385  return is_init_thread;
3386 }
3387 
3388 // __kmp_free_task_threads_data:
3389 // Deallocates a threads_data array for a task team, including any attached
3390 // tasking deques. Only occurs at library shutdown.
3391 static void __kmp_free_task_threads_data(kmp_task_team_t *task_team) {
3392  __kmp_acquire_bootstrap_lock(&task_team->tt.tt_threads_lock);
3393  if (task_team->tt.tt_threads_data != NULL) {
3394  int i;
3395  for (i = 0; i < task_team->tt.tt_max_threads; i++) {
3396  __kmp_free_task_deque(&task_team->tt.tt_threads_data[i]);
3397  }
3398  __kmp_free(task_team->tt.tt_threads_data);
3399  task_team->tt.tt_threads_data = NULL;
3400  }
3401  __kmp_release_bootstrap_lock(&task_team->tt.tt_threads_lock);
3402 }
3403 
3404 // __kmp_allocate_task_team:
3405 // Allocates a task team associated with a specific team, taking it from
3406 // the global task team free list if possible. Also initializes data
3407 // structures.
3408 static kmp_task_team_t *__kmp_allocate_task_team(kmp_info_t *thread,
3409  kmp_team_t *team) {
3410  kmp_task_team_t *task_team = NULL;
3411  int nthreads;
3412 
3413  KA_TRACE(20, ("__kmp_allocate_task_team: T#%d entering; team = %p\n",
3414  (thread ? __kmp_gtid_from_thread(thread) : -1), team));
3415 
3416  if (TCR_PTR(__kmp_free_task_teams) != NULL) {
3417  // Take a task team from the task team pool
3418  __kmp_acquire_bootstrap_lock(&__kmp_task_team_lock);
3419  if (__kmp_free_task_teams != NULL) {
3420  task_team = __kmp_free_task_teams;
3421  TCW_PTR(__kmp_free_task_teams, task_team->tt.tt_next);
3422  task_team->tt.tt_next = NULL;
3423  }
3424  __kmp_release_bootstrap_lock(&__kmp_task_team_lock);
3425  }
3426 
3427  if (task_team == NULL) {
3428  KE_TRACE(10, ("__kmp_allocate_task_team: T#%d allocating "
3429  "task team for team %p\n",
3430  __kmp_gtid_from_thread(thread), team));
3431  // Allocate a new task team if one is not available. Cannot use
3432  // __kmp_thread_malloc because threads not around for kmp_reap_task_team.
3433  task_team = (kmp_task_team_t *)__kmp_allocate(sizeof(kmp_task_team_t));
3434  __kmp_init_bootstrap_lock(&task_team->tt.tt_threads_lock);
3435 #if USE_ITT_BUILD && USE_ITT_NOTIFY && KMP_DEBUG
3436  // suppress race conditions detection on synchronization flags in debug mode
3437  // this helps to analyze library internals eliminating false positives
3438  __itt_suppress_mark_range(
3439  __itt_suppress_range, __itt_suppress_threading_errors,
3440  &task_team->tt.tt_found_tasks, sizeof(task_team->tt.tt_found_tasks));
3441  __itt_suppress_mark_range(__itt_suppress_range,
3442  __itt_suppress_threading_errors,
3443  CCAST(kmp_uint32 *, &task_team->tt.tt_active),
3444  sizeof(task_team->tt.tt_active));
3445 #endif /* USE_ITT_BUILD && USE_ITT_NOTIFY && KMP_DEBUG */
3446  // Note: __kmp_allocate zeroes returned memory, othewise we would need:
3447  // task_team->tt.tt_threads_data = NULL;
3448  // task_team->tt.tt_max_threads = 0;
3449  // task_team->tt.tt_next = NULL;
3450  }
3451 
3452  TCW_4(task_team->tt.tt_found_tasks, FALSE);
3453  TCW_4(task_team->tt.tt_found_proxy_tasks, FALSE);
3454  task_team->tt.tt_nproc = nthreads = team->t.t_nproc;
3455 
3456  KMP_ATOMIC_ST_REL(&task_team->tt.tt_unfinished_threads, nthreads);
3457  TCW_4(task_team->tt.tt_hidden_helper_task_encountered, FALSE);
3458  TCW_4(task_team->tt.tt_active, TRUE);
3459 
3460  KA_TRACE(20, ("__kmp_allocate_task_team: T#%d exiting; task_team = %p "
3461  "unfinished_threads init'd to %d\n",
3462  (thread ? __kmp_gtid_from_thread(thread) : -1), task_team,
3463  KMP_ATOMIC_LD_RLX(&task_team->tt.tt_unfinished_threads)));
3464  return task_team;
3465 }
3466 
3467 // __kmp_free_task_team:
3468 // Frees the task team associated with a specific thread, and adds it
3469 // to the global task team free list.
3470 void __kmp_free_task_team(kmp_info_t *thread, kmp_task_team_t *task_team) {
3471  KA_TRACE(20, ("__kmp_free_task_team: T#%d task_team = %p\n",
3472  thread ? __kmp_gtid_from_thread(thread) : -1, task_team));
3473 
3474  // Put task team back on free list
3475  __kmp_acquire_bootstrap_lock(&__kmp_task_team_lock);
3476 
3477  KMP_DEBUG_ASSERT(task_team->tt.tt_next == NULL);
3478  task_team->tt.tt_next = __kmp_free_task_teams;
3479  TCW_PTR(__kmp_free_task_teams, task_team);
3480 
3481  __kmp_release_bootstrap_lock(&__kmp_task_team_lock);
3482 }
3483 
3484 // __kmp_reap_task_teams:
3485 // Free all the task teams on the task team free list.
3486 // Should only be done during library shutdown.
3487 // Cannot do anything that needs a thread structure or gtid since they are
3488 // already gone.
3489 void __kmp_reap_task_teams(void) {
3490  kmp_task_team_t *task_team;
3491 
3492  if (TCR_PTR(__kmp_free_task_teams) != NULL) {
3493  // Free all task_teams on the free list
3494  __kmp_acquire_bootstrap_lock(&__kmp_task_team_lock);
3495  while ((task_team = __kmp_free_task_teams) != NULL) {
3496  __kmp_free_task_teams = task_team->tt.tt_next;
3497  task_team->tt.tt_next = NULL;
3498 
3499  // Free threads_data if necessary
3500  if (task_team->tt.tt_threads_data != NULL) {
3501  __kmp_free_task_threads_data(task_team);
3502  }
3503  __kmp_free(task_team);
3504  }
3505  __kmp_release_bootstrap_lock(&__kmp_task_team_lock);
3506  }
3507 }
3508 
3509 // __kmp_wait_to_unref_task_teams:
3510 // Some threads could still be in the fork barrier release code, possibly
3511 // trying to steal tasks. Wait for each thread to unreference its task team.
3512 void __kmp_wait_to_unref_task_teams(void) {
3513  kmp_info_t *thread;
3514  kmp_uint32 spins;
3515  int done;
3516 
3517  KMP_INIT_YIELD(spins);
3518 
3519  for (;;) {
3520  done = TRUE;
3521 
3522  // TODO: GEH - this may be is wrong because some sync would be necessary
3523  // in case threads are added to the pool during the traversal. Need to
3524  // verify that lock for thread pool is held when calling this routine.
3525  for (thread = CCAST(kmp_info_t *, __kmp_thread_pool); thread != NULL;
3526  thread = thread->th.th_next_pool) {
3527 #if KMP_OS_WINDOWS
3528  DWORD exit_val;
3529 #endif
3530  if (TCR_PTR(thread->th.th_task_team) == NULL) {
3531  KA_TRACE(10, ("__kmp_wait_to_unref_task_team: T#%d task_team == NULL\n",
3532  __kmp_gtid_from_thread(thread)));
3533  continue;
3534  }
3535 #if KMP_OS_WINDOWS
3536  // TODO: GEH - add this check for Linux* OS / OS X* as well?
3537  if (!__kmp_is_thread_alive(thread, &exit_val)) {
3538  thread->th.th_task_team = NULL;
3539  continue;
3540  }
3541 #endif
3542 
3543  done = FALSE; // Because th_task_team pointer is not NULL for this thread
3544 
3545  KA_TRACE(10, ("__kmp_wait_to_unref_task_team: Waiting for T#%d to "
3546  "unreference task_team\n",
3547  __kmp_gtid_from_thread(thread)));
3548 
3549  if (__kmp_dflt_blocktime != KMP_MAX_BLOCKTIME) {
3550  volatile void *sleep_loc;
3551  // If the thread is sleeping, awaken it.
3552  if ((sleep_loc = TCR_PTR(CCAST(void *, thread->th.th_sleep_loc))) !=
3553  NULL) {
3554  KA_TRACE(
3555  10,
3556  ("__kmp_wait_to_unref_task_team: T#%d waking up thread T#%d\n",
3557  __kmp_gtid_from_thread(thread), __kmp_gtid_from_thread(thread)));
3558  __kmp_null_resume_wrapper(__kmp_gtid_from_thread(thread), sleep_loc);
3559  }
3560  }
3561  }
3562  if (done) {
3563  break;
3564  }
3565 
3566  // If oversubscribed or have waited a bit, yield.
3567  KMP_YIELD_OVERSUB_ELSE_SPIN(spins);
3568  }
3569 }
3570 
3571 // __kmp_task_team_setup: Create a task_team for the current team, but use
3572 // an already created, unused one if it already exists.
3573 void __kmp_task_team_setup(kmp_info_t *this_thr, kmp_team_t *team, int always) {
3574  KMP_DEBUG_ASSERT(__kmp_tasking_mode != tskm_immediate_exec);
3575 
3576  // If this task_team hasn't been created yet, allocate it. It will be used in
3577  // the region after the next.
3578  // If it exists, it is the current task team and shouldn't be touched yet as
3579  // it may still be in use.
3580  if (team->t.t_task_team[this_thr->th.th_task_state] == NULL &&
3581  (always || team->t.t_nproc > 1)) {
3582  team->t.t_task_team[this_thr->th.th_task_state] =
3583  __kmp_allocate_task_team(this_thr, team);
3584  KA_TRACE(20, ("__kmp_task_team_setup: Primary T#%d created new task_team %p"
3585  " for team %d at parity=%d\n",
3586  __kmp_gtid_from_thread(this_thr),
3587  team->t.t_task_team[this_thr->th.th_task_state], team->t.t_id,
3588  this_thr->th.th_task_state));
3589  }
3590 
3591  // After threads exit the release, they will call sync, and then point to this
3592  // other task_team; make sure it is allocated and properly initialized. As
3593  // threads spin in the barrier release phase, they will continue to use the
3594  // previous task_team struct(above), until they receive the signal to stop
3595  // checking for tasks (they can't safely reference the kmp_team_t struct,
3596  // which could be reallocated by the primary thread). No task teams are formed
3597  // for serialized teams.
3598  if (team->t.t_nproc > 1) {
3599  int other_team = 1 - this_thr->th.th_task_state;
3600  KMP_DEBUG_ASSERT(other_team >= 0 && other_team < 2);
3601  if (team->t.t_task_team[other_team] == NULL) { // setup other team as well
3602  team->t.t_task_team[other_team] =
3603  __kmp_allocate_task_team(this_thr, team);
3604  KA_TRACE(20, ("__kmp_task_team_setup: Primary T#%d created second new "
3605  "task_team %p for team %d at parity=%d\n",
3606  __kmp_gtid_from_thread(this_thr),
3607  team->t.t_task_team[other_team], team->t.t_id, other_team));
3608  } else { // Leave the old task team struct in place for the upcoming region;
3609  // adjust as needed
3610  kmp_task_team_t *task_team = team->t.t_task_team[other_team];
3611  if (!task_team->tt.tt_active ||
3612  team->t.t_nproc != task_team->tt.tt_nproc) {
3613  TCW_4(task_team->tt.tt_nproc, team->t.t_nproc);
3614  TCW_4(task_team->tt.tt_found_tasks, FALSE);
3615  TCW_4(task_team->tt.tt_found_proxy_tasks, FALSE);
3616  KMP_ATOMIC_ST_REL(&task_team->tt.tt_unfinished_threads,
3617  team->t.t_nproc);
3618  TCW_4(task_team->tt.tt_active, TRUE);
3619  }
3620  // if team size has changed, the first thread to enable tasking will
3621  // realloc threads_data if necessary
3622  KA_TRACE(20, ("__kmp_task_team_setup: Primary T#%d reset next task_team "
3623  "%p for team %d at parity=%d\n",
3624  __kmp_gtid_from_thread(this_thr),
3625  team->t.t_task_team[other_team], team->t.t_id, other_team));
3626  }
3627  }
3628 
3629  // For regular thread, task enabling should be called when the task is going
3630  // to be pushed to a dequeue. However, for the hidden helper thread, we need
3631  // it ahead of time so that some operations can be performed without race
3632  // condition.
3633  if (this_thr == __kmp_hidden_helper_main_thread) {
3634  for (int i = 0; i < 2; ++i) {
3635  kmp_task_team_t *task_team = team->t.t_task_team[i];
3636  if (KMP_TASKING_ENABLED(task_team)) {
3637  continue;
3638  }
3639  __kmp_enable_tasking(task_team, this_thr);
3640  for (int j = 0; j < task_team->tt.tt_nproc; ++j) {
3641  kmp_thread_data_t *thread_data = &task_team->tt.tt_threads_data[j];
3642  if (thread_data->td.td_deque == NULL) {
3643  __kmp_alloc_task_deque(__kmp_hidden_helper_threads[j], thread_data);
3644  }
3645  }
3646  }
3647  }
3648 }
3649 
3650 // __kmp_task_team_sync: Propagation of task team data from team to threads
3651 // which happens just after the release phase of a team barrier. This may be
3652 // called by any thread, but only for teams with # threads > 1.
3653 void __kmp_task_team_sync(kmp_info_t *this_thr, kmp_team_t *team) {
3654  KMP_DEBUG_ASSERT(__kmp_tasking_mode != tskm_immediate_exec);
3655 
3656  // Toggle the th_task_state field, to switch which task_team this thread
3657  // refers to
3658  this_thr->th.th_task_state = (kmp_uint8)(1 - this_thr->th.th_task_state);
3659 
3660  // It is now safe to propagate the task team pointer from the team struct to
3661  // the current thread.
3662  TCW_PTR(this_thr->th.th_task_team,
3663  team->t.t_task_team[this_thr->th.th_task_state]);
3664  KA_TRACE(20,
3665  ("__kmp_task_team_sync: Thread T#%d task team switched to task_team "
3666  "%p from Team #%d (parity=%d)\n",
3667  __kmp_gtid_from_thread(this_thr), this_thr->th.th_task_team,
3668  team->t.t_id, this_thr->th.th_task_state));
3669 }
3670 
3671 // __kmp_task_team_wait: Primary thread waits for outstanding tasks after the
3672 // barrier gather phase. Only called by primary thread if #threads in team > 1
3673 // or if proxy tasks were created.
3674 //
3675 // wait is a flag that defaults to 1 (see kmp.h), but waiting can be turned off
3676 // by passing in 0 optionally as the last argument. When wait is zero, primary
3677 // thread does not wait for unfinished_threads to reach 0.
3678 void __kmp_task_team_wait(
3679  kmp_info_t *this_thr,
3680  kmp_team_t *team USE_ITT_BUILD_ARG(void *itt_sync_obj), int wait) {
3681  kmp_task_team_t *task_team = team->t.t_task_team[this_thr->th.th_task_state];
3682 
3683  KMP_DEBUG_ASSERT(__kmp_tasking_mode != tskm_immediate_exec);
3684  KMP_DEBUG_ASSERT(task_team == this_thr->th.th_task_team);
3685 
3686  if ((task_team != NULL) && KMP_TASKING_ENABLED(task_team)) {
3687  if (wait) {
3688  KA_TRACE(20, ("__kmp_task_team_wait: Primary T#%d waiting for all tasks "
3689  "(for unfinished_threads to reach 0) on task_team = %p\n",
3690  __kmp_gtid_from_thread(this_thr), task_team));
3691  // Worker threads may have dropped through to release phase, but could
3692  // still be executing tasks. Wait here for tasks to complete. To avoid
3693  // memory contention, only primary thread checks termination condition.
3694  kmp_flag_32<false, false> flag(
3695  RCAST(std::atomic<kmp_uint32> *,
3696  &task_team->tt.tt_unfinished_threads),
3697  0U);
3698  flag.wait(this_thr, TRUE USE_ITT_BUILD_ARG(itt_sync_obj));
3699  }
3700  // Deactivate the old task team, so that the worker threads will stop
3701  // referencing it while spinning.
3702  KA_TRACE(
3703  20,
3704  ("__kmp_task_team_wait: Primary T#%d deactivating task_team %p: "
3705  "setting active to false, setting local and team's pointer to NULL\n",
3706  __kmp_gtid_from_thread(this_thr), task_team));
3707  KMP_DEBUG_ASSERT(task_team->tt.tt_nproc > 1 ||
3708  task_team->tt.tt_found_proxy_tasks == TRUE);
3709  TCW_SYNC_4(task_team->tt.tt_found_proxy_tasks, FALSE);
3710  KMP_CHECK_UPDATE(task_team->tt.tt_untied_task_encountered, 0);
3711  TCW_SYNC_4(task_team->tt.tt_active, FALSE);
3712  KMP_MB();
3713 
3714  TCW_PTR(this_thr->th.th_task_team, NULL);
3715  }
3716 }
3717 
3718 // __kmp_tasking_barrier:
3719 // This routine is called only when __kmp_tasking_mode == tskm_extra_barrier.
3720 // Internal function to execute all tasks prior to a regular barrier or a join
3721 // barrier. It is a full barrier itself, which unfortunately turns regular
3722 // barriers into double barriers and join barriers into 1 1/2 barriers.
3723 void __kmp_tasking_barrier(kmp_team_t *team, kmp_info_t *thread, int gtid) {
3724  std::atomic<kmp_uint32> *spin = RCAST(
3725  std::atomic<kmp_uint32> *,
3726  &team->t.t_task_team[thread->th.th_task_state]->tt.tt_unfinished_threads);
3727  int flag = FALSE;
3728  KMP_DEBUG_ASSERT(__kmp_tasking_mode == tskm_extra_barrier);
3729 
3730 #if USE_ITT_BUILD
3731  KMP_FSYNC_SPIN_INIT(spin, NULL);
3732 #endif /* USE_ITT_BUILD */
3733  kmp_flag_32<false, false> spin_flag(spin, 0U);
3734  while (!spin_flag.execute_tasks(thread, gtid, TRUE,
3735  &flag USE_ITT_BUILD_ARG(NULL), 0)) {
3736 #if USE_ITT_BUILD
3737  // TODO: What about itt_sync_obj??
3738  KMP_FSYNC_SPIN_PREPARE(RCAST(void *, spin));
3739 #endif /* USE_ITT_BUILD */
3740 
3741  if (TCR_4(__kmp_global.g.g_done)) {
3742  if (__kmp_global.g.g_abort)
3743  __kmp_abort_thread();
3744  break;
3745  }
3746  KMP_YIELD(TRUE);
3747  }
3748 #if USE_ITT_BUILD
3749  KMP_FSYNC_SPIN_ACQUIRED(RCAST(void *, spin));
3750 #endif /* USE_ITT_BUILD */
3751 }
3752 
3753 // __kmp_give_task puts a task into a given thread queue if:
3754 // - the queue for that thread was created
3755 // - there's space in that queue
3756 // Because of this, __kmp_push_task needs to check if there's space after
3757 // getting the lock
3758 static bool __kmp_give_task(kmp_info_t *thread, kmp_int32 tid, kmp_task_t *task,
3759  kmp_int32 pass) {
3760  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(task);
3761  kmp_task_team_t *task_team = taskdata->td_task_team;
3762 
3763  KA_TRACE(20, ("__kmp_give_task: trying to give task %p to thread %d.\n",
3764  taskdata, tid));
3765 
3766  // If task_team is NULL something went really bad...
3767  KMP_DEBUG_ASSERT(task_team != NULL);
3768 
3769  bool result = false;
3770  kmp_thread_data_t *thread_data = &task_team->tt.tt_threads_data[tid];
3771 
3772  if (thread_data->td.td_deque == NULL) {
3773  // There's no queue in this thread, go find another one
3774  // We're guaranteed that at least one thread has a queue
3775  KA_TRACE(30,
3776  ("__kmp_give_task: thread %d has no queue while giving task %p.\n",
3777  tid, taskdata));
3778  return result;
3779  }
3780 
3781  if (TCR_4(thread_data->td.td_deque_ntasks) >=
3782  TASK_DEQUE_SIZE(thread_data->td)) {
3783  KA_TRACE(
3784  30,
3785  ("__kmp_give_task: queue is full while giving task %p to thread %d.\n",
3786  taskdata, tid));
3787 
3788  // if this deque is bigger than the pass ratio give a chance to another
3789  // thread
3790  if (TASK_DEQUE_SIZE(thread_data->td) / INITIAL_TASK_DEQUE_SIZE >= pass)
3791  return result;
3792 
3793  __kmp_acquire_bootstrap_lock(&thread_data->td.td_deque_lock);
3794  if (TCR_4(thread_data->td.td_deque_ntasks) >=
3795  TASK_DEQUE_SIZE(thread_data->td)) {
3796  // expand deque to push the task which is not allowed to execute
3797  __kmp_realloc_task_deque(thread, thread_data);
3798  }
3799 
3800  } else {
3801 
3802  __kmp_acquire_bootstrap_lock(&thread_data->td.td_deque_lock);
3803 
3804  if (TCR_4(thread_data->td.td_deque_ntasks) >=
3805  TASK_DEQUE_SIZE(thread_data->td)) {
3806  KA_TRACE(30, ("__kmp_give_task: queue is full while giving task %p to "
3807  "thread %d.\n",
3808  taskdata, tid));
3809 
3810  // if this deque is bigger than the pass ratio give a chance to another
3811  // thread
3812  if (TASK_DEQUE_SIZE(thread_data->td) / INITIAL_TASK_DEQUE_SIZE >= pass)
3813  goto release_and_exit;
3814 
3815  __kmp_realloc_task_deque(thread, thread_data);
3816  }
3817  }
3818 
3819  // lock is held here, and there is space in the deque
3820 
3821  thread_data->td.td_deque[thread_data->td.td_deque_tail] = taskdata;
3822  // Wrap index.
3823  thread_data->td.td_deque_tail =
3824  (thread_data->td.td_deque_tail + 1) & TASK_DEQUE_MASK(thread_data->td);
3825  TCW_4(thread_data->td.td_deque_ntasks,
3826  TCR_4(thread_data->td.td_deque_ntasks) + 1);
3827 
3828  result = true;
3829  KA_TRACE(30, ("__kmp_give_task: successfully gave task %p to thread %d.\n",
3830  taskdata, tid));
3831 
3832 release_and_exit:
3833  __kmp_release_bootstrap_lock(&thread_data->td.td_deque_lock);
3834 
3835  return result;
3836 }
3837 
3838 #define PROXY_TASK_FLAG 0x40000000
3839 /* The finish of the proxy tasks is divided in two pieces:
3840  - the top half is the one that can be done from a thread outside the team
3841  - the bottom half must be run from a thread within the team
3842 
3843  In order to run the bottom half the task gets queued back into one of the
3844  threads of the team. Once the td_incomplete_child_task counter of the parent
3845  is decremented the threads can leave the barriers. So, the bottom half needs
3846  to be queued before the counter is decremented. The top half is therefore
3847  divided in two parts:
3848  - things that can be run before queuing the bottom half
3849  - things that must be run after queuing the bottom half
3850 
3851  This creates a second race as the bottom half can free the task before the
3852  second top half is executed. To avoid this we use the
3853  td_incomplete_child_task of the proxy task to synchronize the top and bottom
3854  half. */
3855 static void __kmp_first_top_half_finish_proxy(kmp_taskdata_t *taskdata) {
3856  KMP_DEBUG_ASSERT(taskdata->td_flags.tasktype == TASK_EXPLICIT);
3857  KMP_DEBUG_ASSERT(taskdata->td_flags.proxy == TASK_PROXY);
3858  KMP_DEBUG_ASSERT(taskdata->td_flags.complete == 0);
3859  KMP_DEBUG_ASSERT(taskdata->td_flags.freed == 0);
3860 
3861  taskdata->td_flags.complete = 1; // mark the task as completed
3862 
3863  if (taskdata->td_taskgroup)
3864  KMP_ATOMIC_DEC(&taskdata->td_taskgroup->count);
3865 
3866  // Create an imaginary children for this task so the bottom half cannot
3867  // release the task before we have completed the second top half
3868  KMP_ATOMIC_OR(&taskdata->td_incomplete_child_tasks, PROXY_TASK_FLAG);
3869 }
3870 
3871 static void __kmp_second_top_half_finish_proxy(kmp_taskdata_t *taskdata) {
3872  kmp_int32 children = 0;
3873 
3874  // Predecrement simulated by "- 1" calculation
3875  children =
3876  KMP_ATOMIC_DEC(&taskdata->td_parent->td_incomplete_child_tasks) - 1;
3877  KMP_DEBUG_ASSERT(children >= 0);
3878 
3879  // Remove the imaginary children
3880  KMP_ATOMIC_AND(&taskdata->td_incomplete_child_tasks, ~PROXY_TASK_FLAG);
3881 }
3882 
3883 static void __kmp_bottom_half_finish_proxy(kmp_int32 gtid, kmp_task_t *ptask) {
3884  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(ptask);
3885  kmp_info_t *thread = __kmp_threads[gtid];
3886 
3887  KMP_DEBUG_ASSERT(taskdata->td_flags.proxy == TASK_PROXY);
3888  KMP_DEBUG_ASSERT(taskdata->td_flags.complete ==
3889  1); // top half must run before bottom half
3890 
3891  // We need to wait to make sure the top half is finished
3892  // Spinning here should be ok as this should happen quickly
3893  while ((KMP_ATOMIC_LD_ACQ(&taskdata->td_incomplete_child_tasks) &
3894  PROXY_TASK_FLAG) > 0)
3895  ;
3896 
3897  __kmp_release_deps(gtid, taskdata);
3898  __kmp_free_task_and_ancestors(gtid, taskdata, thread);
3899 }
3900 
3909 void __kmpc_proxy_task_completed(kmp_int32 gtid, kmp_task_t *ptask) {
3910  KMP_DEBUG_ASSERT(ptask != NULL);
3911  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(ptask);
3912  KA_TRACE(
3913  10, ("__kmp_proxy_task_completed(enter): T#%d proxy task %p completing\n",
3914  gtid, taskdata));
3915  __kmp_assert_valid_gtid(gtid);
3916  KMP_DEBUG_ASSERT(taskdata->td_flags.proxy == TASK_PROXY);
3917 
3918  __kmp_first_top_half_finish_proxy(taskdata);
3919  __kmp_second_top_half_finish_proxy(taskdata);
3920  __kmp_bottom_half_finish_proxy(gtid, ptask);
3921 
3922  KA_TRACE(10,
3923  ("__kmp_proxy_task_completed(exit): T#%d proxy task %p completing\n",
3924  gtid, taskdata));
3925 }
3926 
3927 void __kmpc_give_task(kmp_task_t *ptask, kmp_int32 start = 0) {
3928  KMP_DEBUG_ASSERT(ptask != NULL);
3929  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(ptask);
3930 
3931  // Enqueue task to complete bottom half completion from a thread within the
3932  // corresponding team
3933  kmp_team_t *team = taskdata->td_team;
3934  kmp_int32 nthreads = team->t.t_nproc;
3935  kmp_info_t *thread;
3936 
3937  // This should be similar to start_k = __kmp_get_random( thread ) % nthreads
3938  // but we cannot use __kmp_get_random here
3939  kmp_int32 start_k = start;
3940  kmp_int32 pass = 1;
3941  kmp_int32 k = start_k;
3942 
3943  do {
3944  // For now we're just linearly trying to find a thread
3945  thread = team->t.t_threads[k];
3946  k = (k + 1) % nthreads;
3947 
3948  // we did a full pass through all the threads
3949  if (k == start_k)
3950  pass = pass << 1;
3951 
3952  } while (!__kmp_give_task(thread, k, ptask, pass));
3953 }
3954 
3962 void __kmpc_proxy_task_completed_ooo(kmp_task_t *ptask) {
3963  KMP_DEBUG_ASSERT(ptask != NULL);
3964  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(ptask);
3965 
3966  KA_TRACE(
3967  10,
3968  ("__kmp_proxy_task_completed_ooo(enter): proxy task completing ooo %p\n",
3969  taskdata));
3970 
3971  KMP_DEBUG_ASSERT(taskdata->td_flags.proxy == TASK_PROXY);
3972 
3973  __kmp_first_top_half_finish_proxy(taskdata);
3974 
3975  __kmpc_give_task(ptask);
3976 
3977  __kmp_second_top_half_finish_proxy(taskdata);
3978 
3979  KA_TRACE(
3980  10,
3981  ("__kmp_proxy_task_completed_ooo(exit): proxy task completing ooo %p\n",
3982  taskdata));
3983 }
3984 
3985 kmp_event_t *__kmpc_task_allow_completion_event(ident_t *loc_ref, int gtid,
3986  kmp_task_t *task) {
3987  kmp_taskdata_t *td = KMP_TASK_TO_TASKDATA(task);
3988  if (td->td_allow_completion_event.type == KMP_EVENT_UNINITIALIZED) {
3989  td->td_allow_completion_event.type = KMP_EVENT_ALLOW_COMPLETION;
3990  td->td_allow_completion_event.ed.task = task;
3991  __kmp_init_tas_lock(&td->td_allow_completion_event.lock);
3992  }
3993  return &td->td_allow_completion_event;
3994 }
3995 
3996 void __kmp_fulfill_event(kmp_event_t *event) {
3997  if (event->type == KMP_EVENT_ALLOW_COMPLETION) {
3998  kmp_task_t *ptask = event->ed.task;
3999  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(ptask);
4000  bool detached = false;
4001  int gtid = __kmp_get_gtid();
4002 
4003  // The associated task might have completed or could be completing at this
4004  // point.
4005  // We need to take the lock to avoid races
4006  __kmp_acquire_tas_lock(&event->lock, gtid);
4007  if (taskdata->td_flags.proxy == TASK_PROXY) {
4008  detached = true;
4009  } else {
4010 #if OMPT_SUPPORT
4011  // The OMPT event must occur under mutual exclusion,
4012  // otherwise the tool might access ptask after free
4013  if (UNLIKELY(ompt_enabled.enabled))
4014  __ompt_task_finish(ptask, NULL, ompt_task_early_fulfill);
4015 #endif
4016  }
4017  event->type = KMP_EVENT_UNINITIALIZED;
4018  __kmp_release_tas_lock(&event->lock, gtid);
4019 
4020  if (detached) {
4021 #if OMPT_SUPPORT
4022  // We free ptask afterwards and know the task is finished,
4023  // so locking is not necessary
4024  if (UNLIKELY(ompt_enabled.enabled))
4025  __ompt_task_finish(ptask, NULL, ompt_task_late_fulfill);
4026 #endif
4027  // If the task detached complete the proxy task
4028  if (gtid >= 0) {
4029  kmp_team_t *team = taskdata->td_team;
4030  kmp_info_t *thread = __kmp_get_thread();
4031  if (thread->th.th_team == team) {
4032  __kmpc_proxy_task_completed(gtid, ptask);
4033  return;
4034  }
4035  }
4036 
4037  // fallback
4039  }
4040  }
4041 }
4042 
4043 // __kmp_task_dup_alloc: Allocate the taskdata and make a copy of source task
4044 // for taskloop
4045 //
4046 // thread: allocating thread
4047 // task_src: pointer to source task to be duplicated
4048 // returns: a pointer to the allocated kmp_task_t structure (task).
4049 kmp_task_t *__kmp_task_dup_alloc(kmp_info_t *thread, kmp_task_t *task_src) {
4050  kmp_task_t *task;
4051  kmp_taskdata_t *taskdata;
4052  kmp_taskdata_t *taskdata_src = KMP_TASK_TO_TASKDATA(task_src);
4053  kmp_taskdata_t *parent_task = taskdata_src->td_parent; // same parent task
4054  size_t shareds_offset;
4055  size_t task_size;
4056 
4057  KA_TRACE(10, ("__kmp_task_dup_alloc(enter): Th %p, source task %p\n", thread,
4058  task_src));
4059  KMP_DEBUG_ASSERT(taskdata_src->td_flags.proxy ==
4060  TASK_FULL); // it should not be proxy task
4061  KMP_DEBUG_ASSERT(taskdata_src->td_flags.tasktype == TASK_EXPLICIT);
4062  task_size = taskdata_src->td_size_alloc;
4063 
4064  // Allocate a kmp_taskdata_t block and a kmp_task_t block.
4065  KA_TRACE(30, ("__kmp_task_dup_alloc: Th %p, malloc size %ld\n", thread,
4066  task_size));
4067 #if USE_FAST_MEMORY
4068  taskdata = (kmp_taskdata_t *)__kmp_fast_allocate(thread, task_size);
4069 #else
4070  taskdata = (kmp_taskdata_t *)__kmp_thread_malloc(thread, task_size);
4071 #endif /* USE_FAST_MEMORY */
4072  KMP_MEMCPY(taskdata, taskdata_src, task_size);
4073 
4074  task = KMP_TASKDATA_TO_TASK(taskdata);
4075 
4076  // Initialize new task (only specific fields not affected by memcpy)
4077  taskdata->td_task_id = KMP_GEN_TASK_ID();
4078  if (task->shareds != NULL) { // need setup shareds pointer
4079  shareds_offset = (char *)task_src->shareds - (char *)taskdata_src;
4080  task->shareds = &((char *)taskdata)[shareds_offset];
4081  KMP_DEBUG_ASSERT((((kmp_uintptr_t)task->shareds) & (sizeof(void *) - 1)) ==
4082  0);
4083  }
4084  taskdata->td_alloc_thread = thread;
4085  taskdata->td_parent = parent_task;
4086  // task inherits the taskgroup from the parent task
4087  taskdata->td_taskgroup = parent_task->td_taskgroup;
4088  // tied task needs to initialize the td_last_tied at creation,
4089  // untied one does this when it is scheduled for execution
4090  if (taskdata->td_flags.tiedness == TASK_TIED)
4091  taskdata->td_last_tied = taskdata;
4092 
4093  // Only need to keep track of child task counts if team parallel and tasking
4094  // not serialized
4095  if (!(taskdata->td_flags.team_serial || taskdata->td_flags.tasking_ser)) {
4096  KMP_ATOMIC_INC(&parent_task->td_incomplete_child_tasks);
4097  if (parent_task->td_taskgroup)
4098  KMP_ATOMIC_INC(&parent_task->td_taskgroup->count);
4099  // Only need to keep track of allocated child tasks for explicit tasks since
4100  // implicit not deallocated
4101  if (taskdata->td_parent->td_flags.tasktype == TASK_EXPLICIT)
4102  KMP_ATOMIC_INC(&taskdata->td_parent->td_allocated_child_tasks);
4103  }
4104 
4105  KA_TRACE(20,
4106  ("__kmp_task_dup_alloc(exit): Th %p, created task %p, parent=%p\n",
4107  thread, taskdata, taskdata->td_parent));
4108 #if OMPT_SUPPORT
4109  if (UNLIKELY(ompt_enabled.enabled))
4110  __ompt_task_init(taskdata, thread->th.th_info.ds.ds_gtid);
4111 #endif
4112  return task;
4113 }
4114 
4115 // Routine optionally generated by the compiler for setting the lastprivate flag
4116 // and calling needed constructors for private/firstprivate objects
4117 // (used to form taskloop tasks from pattern task)
4118 // Parameters: dest task, src task, lastprivate flag.
4119 typedef void (*p_task_dup_t)(kmp_task_t *, kmp_task_t *, kmp_int32);
4120 
4121 KMP_BUILD_ASSERT(sizeof(long) == 4 || sizeof(long) == 8);
4122 
4123 // class to encapsulate manipulating loop bounds in a taskloop task.
4124 // this abstracts away the Intel vs GOMP taskloop interface for setting/getting
4125 // the loop bound variables.
4126 class kmp_taskloop_bounds_t {
4127  kmp_task_t *task;
4128  const kmp_taskdata_t *taskdata;
4129  size_t lower_offset;
4130  size_t upper_offset;
4131 
4132 public:
4133  kmp_taskloop_bounds_t(kmp_task_t *_task, kmp_uint64 *lb, kmp_uint64 *ub)
4134  : task(_task), taskdata(KMP_TASK_TO_TASKDATA(task)),
4135  lower_offset((char *)lb - (char *)task),
4136  upper_offset((char *)ub - (char *)task) {
4137  KMP_DEBUG_ASSERT((char *)lb > (char *)_task);
4138  KMP_DEBUG_ASSERT((char *)ub > (char *)_task);
4139  }
4140  kmp_taskloop_bounds_t(kmp_task_t *_task, const kmp_taskloop_bounds_t &bounds)
4141  : task(_task), taskdata(KMP_TASK_TO_TASKDATA(_task)),
4142  lower_offset(bounds.lower_offset), upper_offset(bounds.upper_offset) {}
4143  size_t get_lower_offset() const { return lower_offset; }
4144  size_t get_upper_offset() const { return upper_offset; }
4145  kmp_uint64 get_lb() const {
4146  kmp_int64 retval;
4147 #if defined(KMP_GOMP_COMPAT)
4148  // Intel task just returns the lower bound normally
4149  if (!taskdata->td_flags.native) {
4150  retval = *(kmp_int64 *)((char *)task + lower_offset);
4151  } else {
4152  // GOMP task has to take into account the sizeof(long)
4153  if (taskdata->td_size_loop_bounds == 4) {
4154  kmp_int32 *lb = RCAST(kmp_int32 *, task->shareds);
4155  retval = (kmp_int64)*lb;
4156  } else {
4157  kmp_int64 *lb = RCAST(kmp_int64 *, task->shareds);
4158  retval = (kmp_int64)*lb;
4159  }
4160  }
4161 #else
4162  (void)taskdata;
4163  retval = *(kmp_int64 *)((char *)task + lower_offset);
4164 #endif // defined(KMP_GOMP_COMPAT)
4165  return retval;
4166  }
4167  kmp_uint64 get_ub() const {
4168  kmp_int64 retval;
4169 #if defined(KMP_GOMP_COMPAT)
4170  // Intel task just returns the upper bound normally
4171  if (!taskdata->td_flags.native) {
4172  retval = *(kmp_int64 *)((char *)task + upper_offset);
4173  } else {
4174  // GOMP task has to take into account the sizeof(long)
4175  if (taskdata->td_size_loop_bounds == 4) {
4176  kmp_int32 *ub = RCAST(kmp_int32 *, task->shareds) + 1;
4177  retval = (kmp_int64)*ub;
4178  } else {
4179  kmp_int64 *ub = RCAST(kmp_int64 *, task->shareds) + 1;
4180  retval = (kmp_int64)*ub;
4181  }
4182  }
4183 #else
4184  retval = *(kmp_int64 *)((char *)task + upper_offset);
4185 #endif // defined(KMP_GOMP_COMPAT)
4186  return retval;
4187  }
4188  void set_lb(kmp_uint64 lb) {
4189 #if defined(KMP_GOMP_COMPAT)
4190  // Intel task just sets the lower bound normally
4191  if (!taskdata->td_flags.native) {
4192  *(kmp_uint64 *)((char *)task + lower_offset) = lb;
4193  } else {
4194  // GOMP task has to take into account the sizeof(long)
4195  if (taskdata->td_size_loop_bounds == 4) {
4196  kmp_uint32 *lower = RCAST(kmp_uint32 *, task->shareds);
4197  *lower = (kmp_uint32)lb;
4198  } else {
4199  kmp_uint64 *lower = RCAST(kmp_uint64 *, task->shareds);
4200  *lower = (kmp_uint64)lb;
4201  }
4202  }
4203 #else
4204  *(kmp_uint64 *)((char *)task + lower_offset) = lb;
4205 #endif // defined(KMP_GOMP_COMPAT)
4206  }
4207  void set_ub(kmp_uint64 ub) {
4208 #if defined(KMP_GOMP_COMPAT)
4209  // Intel task just sets the upper bound normally
4210  if (!taskdata->td_flags.native) {
4211  *(kmp_uint64 *)((char *)task + upper_offset) = ub;
4212  } else {
4213  // GOMP task has to take into account the sizeof(long)
4214  if (taskdata->td_size_loop_bounds == 4) {
4215  kmp_uint32 *upper = RCAST(kmp_uint32 *, task->shareds) + 1;
4216  *upper = (kmp_uint32)ub;
4217  } else {
4218  kmp_uint64 *upper = RCAST(kmp_uint64 *, task->shareds) + 1;
4219  *upper = (kmp_uint64)ub;
4220  }
4221  }
4222 #else
4223  *(kmp_uint64 *)((char *)task + upper_offset) = ub;
4224 #endif // defined(KMP_GOMP_COMPAT)
4225  }
4226 };
4227 
4228 // __kmp_taskloop_linear: Start tasks of the taskloop linearly
4229 //
4230 // loc Source location information
4231 // gtid Global thread ID
4232 // task Pattern task, exposes the loop iteration range
4233 // lb Pointer to loop lower bound in task structure
4234 // ub Pointer to loop upper bound in task structure
4235 // st Loop stride
4236 // ub_glob Global upper bound (used for lastprivate check)
4237 // num_tasks Number of tasks to execute
4238 // grainsize Number of loop iterations per task
4239 // extras Number of chunks with grainsize+1 iterations
4240 // last_chunk Reduction of grainsize for last task
4241 // tc Iterations count
4242 // task_dup Tasks duplication routine
4243 // codeptr_ra Return address for OMPT events
4244 void __kmp_taskloop_linear(ident_t *loc, int gtid, kmp_task_t *task,
4245  kmp_uint64 *lb, kmp_uint64 *ub, kmp_int64 st,
4246  kmp_uint64 ub_glob, kmp_uint64 num_tasks,
4247  kmp_uint64 grainsize, kmp_uint64 extras,
4248  kmp_int64 last_chunk, kmp_uint64 tc,
4249 #if OMPT_SUPPORT
4250  void *codeptr_ra,
4251 #endif
4252  void *task_dup) {
4253  KMP_COUNT_BLOCK(OMP_TASKLOOP);
4254  KMP_TIME_PARTITIONED_BLOCK(OMP_taskloop_scheduling);
4255  p_task_dup_t ptask_dup = (p_task_dup_t)task_dup;
4256  // compiler provides global bounds here
4257  kmp_taskloop_bounds_t task_bounds(task, lb, ub);
4258  kmp_uint64 lower = task_bounds.get_lb();
4259  kmp_uint64 upper = task_bounds.get_ub();
4260  kmp_uint64 i;
4261  kmp_info_t *thread = __kmp_threads[gtid];
4262  kmp_taskdata_t *current_task = thread->th.th_current_task;
4263  kmp_task_t *next_task;
4264  kmp_int32 lastpriv = 0;
4265 
4266  KMP_DEBUG_ASSERT(tc == num_tasks * grainsize +
4267  (last_chunk < 0 ? last_chunk : extras));
4268  KMP_DEBUG_ASSERT(num_tasks > extras);
4269  KMP_DEBUG_ASSERT(num_tasks > 0);
4270  KA_TRACE(20, ("__kmp_taskloop_linear: T#%d: %lld tasks, grainsize %lld, "
4271  "extras %lld, last_chunk %lld, i=%lld,%lld(%d)%lld, dup %p\n",
4272  gtid, num_tasks, grainsize, extras, last_chunk, lower, upper,
4273  ub_glob, st, task_dup));
4274 
4275  // Launch num_tasks tasks, assign grainsize iterations each task
4276  for (i = 0; i < num_tasks; ++i) {
4277  kmp_uint64 chunk_minus_1;
4278  if (extras == 0) {
4279  chunk_minus_1 = grainsize - 1;
4280  } else {
4281  chunk_minus_1 = grainsize;
4282  --extras; // first extras iterations get bigger chunk (grainsize+1)
4283  }
4284  upper = lower + st * chunk_minus_1;
4285  if (upper > *ub) {
4286  upper = *ub;
4287  }
4288  if (i == num_tasks - 1) {
4289  // schedule the last task, set lastprivate flag if needed
4290  if (st == 1) { // most common case
4291  KMP_DEBUG_ASSERT(upper == *ub);
4292  if (upper == ub_glob)
4293  lastpriv = 1;
4294  } else if (st > 0) { // positive loop stride
4295  KMP_DEBUG_ASSERT((kmp_uint64)st > *ub - upper);
4296  if ((kmp_uint64)st > ub_glob - upper)
4297  lastpriv = 1;
4298  } else { // negative loop stride
4299  KMP_DEBUG_ASSERT(upper + st < *ub);
4300  if (upper - ub_glob < (kmp_uint64)(-st))
4301  lastpriv = 1;
4302  }
4303  }
4304  next_task = __kmp_task_dup_alloc(thread, task); // allocate new task
4305  kmp_taskdata_t *next_taskdata = KMP_TASK_TO_TASKDATA(next_task);
4306  kmp_taskloop_bounds_t next_task_bounds =
4307  kmp_taskloop_bounds_t(next_task, task_bounds);
4308 
4309  // adjust task-specific bounds
4310  next_task_bounds.set_lb(lower);
4311  if (next_taskdata->td_flags.native) {
4312  next_task_bounds.set_ub(upper + (st > 0 ? 1 : -1));
4313  } else {
4314  next_task_bounds.set_ub(upper);
4315  }
4316  if (ptask_dup != NULL) // set lastprivate flag, construct firstprivates,
4317  // etc.
4318  ptask_dup(next_task, task, lastpriv);
4319  KA_TRACE(40,
4320  ("__kmp_taskloop_linear: T#%d; task #%llu: task %p: lower %lld, "
4321  "upper %lld stride %lld, (offsets %p %p)\n",
4322  gtid, i, next_task, lower, upper, st,
4323  next_task_bounds.get_lower_offset(),
4324  next_task_bounds.get_upper_offset()));
4325 #if OMPT_SUPPORT
4326  __kmp_omp_taskloop_task(NULL, gtid, next_task,
4327  codeptr_ra); // schedule new task
4328 #else
4329  __kmp_omp_task(gtid, next_task, true); // schedule new task
4330 #endif
4331  lower = upper + st; // adjust lower bound for the next iteration
4332  }
4333  // free the pattern task and exit
4334  __kmp_task_start(gtid, task, current_task); // make internal bookkeeping
4335  // do not execute the pattern task, just do internal bookkeeping
4336  __kmp_task_finish<false>(gtid, task, current_task);
4337 }
4338 
4339 // Structure to keep taskloop parameters for auxiliary task
4340 // kept in the shareds of the task structure.
4341 typedef struct __taskloop_params {
4342  kmp_task_t *task;
4343  kmp_uint64 *lb;
4344  kmp_uint64 *ub;
4345  void *task_dup;
4346  kmp_int64 st;
4347  kmp_uint64 ub_glob;
4348  kmp_uint64 num_tasks;
4349  kmp_uint64 grainsize;
4350  kmp_uint64 extras;
4351  kmp_int64 last_chunk;
4352  kmp_uint64 tc;
4353  kmp_uint64 num_t_min;
4354 #if OMPT_SUPPORT
4355  void *codeptr_ra;
4356 #endif
4357 } __taskloop_params_t;
4358 
4359 void __kmp_taskloop_recur(ident_t *, int, kmp_task_t *, kmp_uint64 *,
4360  kmp_uint64 *, kmp_int64, kmp_uint64, kmp_uint64,
4361  kmp_uint64, kmp_uint64, kmp_int64, kmp_uint64,
4362  kmp_uint64,
4363 #if OMPT_SUPPORT
4364  void *,
4365 #endif
4366  void *);
4367 
4368 // Execute part of the taskloop submitted as a task.
4369 int __kmp_taskloop_task(int gtid, void *ptask) {
4370  __taskloop_params_t *p =
4371  (__taskloop_params_t *)((kmp_task_t *)ptask)->shareds;
4372  kmp_task_t *task = p->task;
4373  kmp_uint64 *lb = p->lb;
4374  kmp_uint64 *ub = p->ub;
4375  void *task_dup = p->task_dup;
4376  // p_task_dup_t ptask_dup = (p_task_dup_t)task_dup;
4377  kmp_int64 st = p->st;
4378  kmp_uint64 ub_glob = p->ub_glob;
4379  kmp_uint64 num_tasks = p->num_tasks;
4380  kmp_uint64 grainsize = p->grainsize;
4381  kmp_uint64 extras = p->extras;
4382  kmp_int64 last_chunk = p->last_chunk;
4383  kmp_uint64 tc = p->tc;
4384  kmp_uint64 num_t_min = p->num_t_min;
4385 #if OMPT_SUPPORT
4386  void *codeptr_ra = p->codeptr_ra;
4387 #endif
4388 #if KMP_DEBUG
4389  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(task);
4390  KMP_DEBUG_ASSERT(task != NULL);
4391  KA_TRACE(20,
4392  ("__kmp_taskloop_task: T#%d, task %p: %lld tasks, grainsize"
4393  " %lld, extras %lld, last_chunk %lld, i=%lld,%lld(%d), dup %p\n",
4394  gtid, taskdata, num_tasks, grainsize, extras, last_chunk, *lb, *ub,
4395  st, task_dup));
4396 #endif
4397  KMP_DEBUG_ASSERT(num_tasks * 2 + 1 > num_t_min);
4398  if (num_tasks > num_t_min)
4399  __kmp_taskloop_recur(NULL, gtid, task, lb, ub, st, ub_glob, num_tasks,
4400  grainsize, extras, last_chunk, tc, num_t_min,
4401 #if OMPT_SUPPORT
4402  codeptr_ra,
4403 #endif
4404  task_dup);
4405  else
4406  __kmp_taskloop_linear(NULL, gtid, task, lb, ub, st, ub_glob, num_tasks,
4407  grainsize, extras, last_chunk, tc,
4408 #if OMPT_SUPPORT
4409  codeptr_ra,
4410 #endif
4411  task_dup);
4412 
4413  KA_TRACE(40, ("__kmp_taskloop_task(exit): T#%d\n", gtid));
4414  return 0;
4415 }
4416 
4417 // Schedule part of the taskloop as a task,
4418 // execute the rest of the taskloop.
4419 //
4420 // loc Source location information
4421 // gtid Global thread ID
4422 // task Pattern task, exposes the loop iteration range
4423 // lb Pointer to loop lower bound in task structure
4424 // ub Pointer to loop upper bound in task structure
4425 // st Loop stride
4426 // ub_glob Global upper bound (used for lastprivate check)
4427 // num_tasks Number of tasks to execute
4428 // grainsize Number of loop iterations per task
4429 // extras Number of chunks with grainsize+1 iterations
4430 // last_chunk Reduction of grainsize for last task
4431 // tc Iterations count
4432 // num_t_min Threshold to launch tasks recursively
4433 // task_dup Tasks duplication routine
4434 // codeptr_ra Return address for OMPT events
4435 void __kmp_taskloop_recur(ident_t *loc, int gtid, kmp_task_t *task,
4436  kmp_uint64 *lb, kmp_uint64 *ub, kmp_int64 st,
4437  kmp_uint64 ub_glob, kmp_uint64 num_tasks,
4438  kmp_uint64 grainsize, kmp_uint64 extras,
4439  kmp_int64 last_chunk, kmp_uint64 tc,
4440  kmp_uint64 num_t_min,
4441 #if OMPT_SUPPORT
4442  void *codeptr_ra,
4443 #endif
4444  void *task_dup) {
4445  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(task);
4446  KMP_DEBUG_ASSERT(task != NULL);
4447  KMP_DEBUG_ASSERT(num_tasks > num_t_min);
4448  KA_TRACE(20,
4449  ("__kmp_taskloop_recur: T#%d, task %p: %lld tasks, grainsize"
4450  " %lld, extras %lld, last_chunk %lld, i=%lld,%lld(%d), dup %p\n",
4451  gtid, taskdata, num_tasks, grainsize, extras, last_chunk, *lb, *ub,
4452  st, task_dup));
4453  p_task_dup_t ptask_dup = (p_task_dup_t)task_dup;
4454  kmp_uint64 lower = *lb;
4455  kmp_info_t *thread = __kmp_threads[gtid];
4456  // kmp_taskdata_t *current_task = thread->th.th_current_task;
4457  kmp_task_t *next_task;
4458  size_t lower_offset =
4459  (char *)lb - (char *)task; // remember offset of lb in the task structure
4460  size_t upper_offset =
4461  (char *)ub - (char *)task; // remember offset of ub in the task structure
4462 
4463  KMP_DEBUG_ASSERT(tc == num_tasks * grainsize +
4464  (last_chunk < 0 ? last_chunk : extras));
4465  KMP_DEBUG_ASSERT(num_tasks > extras);
4466  KMP_DEBUG_ASSERT(num_tasks > 0);
4467 
4468  // split the loop in two halves
4469  kmp_uint64 lb1, ub0, tc0, tc1, ext0, ext1;
4470  kmp_int64 last_chunk0 = 0, last_chunk1 = 0;
4471  kmp_uint64 gr_size0 = grainsize;
4472  kmp_uint64 n_tsk0 = num_tasks >> 1; // num_tasks/2 to execute
4473  kmp_uint64 n_tsk1 = num_tasks - n_tsk0; // to schedule as a task
4474  if (last_chunk < 0) {
4475  ext0 = ext1 = 0;
4476  last_chunk1 = last_chunk;
4477  tc0 = grainsize * n_tsk0;
4478  tc1 = tc - tc0;
4479  } else if (n_tsk0 <= extras) {
4480  gr_size0++; // integrate extras into grainsize
4481  ext0 = 0; // no extra iters in 1st half
4482  ext1 = extras - n_tsk0; // remaining extras
4483  tc0 = gr_size0 * n_tsk0;
4484  tc1 = tc - tc0;
4485  } else { // n_tsk0 > extras
4486  ext1 = 0; // no extra iters in 2nd half
4487  ext0 = extras;
4488  tc1 = grainsize * n_tsk1;
4489  tc0 = tc - tc1;
4490  }
4491  ub0 = lower + st * (tc0 - 1);
4492  lb1 = ub0 + st;
4493 
4494  // create pattern task for 2nd half of the loop
4495  next_task = __kmp_task_dup_alloc(thread, task); // duplicate the task
4496  // adjust lower bound (upper bound is not changed) for the 2nd half
4497  *(kmp_uint64 *)((char *)next_task + lower_offset) = lb1;
4498  if (ptask_dup != NULL) // construct firstprivates, etc.
4499  ptask_dup(next_task, task, 0);
4500  *ub = ub0; // adjust upper bound for the 1st half
4501 
4502  // create auxiliary task for 2nd half of the loop
4503  // make sure new task has same parent task as the pattern task
4504  kmp_taskdata_t *current_task = thread->th.th_current_task;
4505  thread->th.th_current_task = taskdata->td_parent;
4506  kmp_task_t *new_task =
4507  __kmpc_omp_task_alloc(loc, gtid, 1, 3 * sizeof(void *),
4508  sizeof(__taskloop_params_t), &__kmp_taskloop_task);
4509  // restore current task
4510  thread->th.th_current_task = current_task;
4511  __taskloop_params_t *p = (__taskloop_params_t *)new_task->shareds;
4512  p->task = next_task;
4513  p->lb = (kmp_uint64 *)((char *)next_task + lower_offset);
4514  p->ub = (kmp_uint64 *)((char *)next_task + upper_offset);
4515  p->task_dup = task_dup;
4516  p->st = st;
4517  p->ub_glob = ub_glob;
4518  p->num_tasks = n_tsk1;
4519  p->grainsize = grainsize;
4520  p->extras = ext1;
4521  p->last_chunk = last_chunk1;
4522  p->tc = tc1;
4523  p->num_t_min = num_t_min;
4524 #if OMPT_SUPPORT
4525  p->codeptr_ra = codeptr_ra;
4526 #endif
4527 
4528 #if OMPT_SUPPORT
4529  // schedule new task with correct return address for OMPT events
4530  __kmp_omp_taskloop_task(NULL, gtid, new_task, codeptr_ra);
4531 #else
4532  __kmp_omp_task(gtid, new_task, true); // schedule new task
4533 #endif
4534 
4535  // execute the 1st half of current subrange
4536  if (n_tsk0 > num_t_min)
4537  __kmp_taskloop_recur(loc, gtid, task, lb, ub, st, ub_glob, n_tsk0, gr_size0,
4538  ext0, last_chunk0, tc0, num_t_min,
4539 #if OMPT_SUPPORT
4540  codeptr_ra,
4541 #endif
4542  task_dup);
4543  else
4544  __kmp_taskloop_linear(loc, gtid, task, lb, ub, st, ub_glob, n_tsk0,
4545  gr_size0, ext0, last_chunk0, tc0,
4546 #if OMPT_SUPPORT
4547  codeptr_ra,
4548 #endif
4549  task_dup);
4550 
4551  KA_TRACE(40, ("__kmp_taskloop_recur(exit): T#%d\n", gtid));
4552 }
4553 
4554 static void __kmp_taskloop(ident_t *loc, int gtid, kmp_task_t *task, int if_val,
4555  kmp_uint64 *lb, kmp_uint64 *ub, kmp_int64 st,
4556  int nogroup, int sched, kmp_uint64 grainsize,
4557  int modifier, void *task_dup) {
4558  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(task);
4559  KMP_DEBUG_ASSERT(task != NULL);
4560  if (nogroup == 0) {
4561 #if OMPT_SUPPORT && OMPT_OPTIONAL
4562  OMPT_STORE_RETURN_ADDRESS(gtid);
4563 #endif
4564  __kmpc_taskgroup(loc, gtid);
4565  }
4566 
4567  // =========================================================================
4568  // calculate loop parameters
4569  kmp_taskloop_bounds_t task_bounds(task, lb, ub);
4570  kmp_uint64 tc;
4571  // compiler provides global bounds here
4572  kmp_uint64 lower = task_bounds.get_lb();
4573  kmp_uint64 upper = task_bounds.get_ub();
4574  kmp_uint64 ub_glob = upper; // global upper used to calc lastprivate flag
4575  kmp_uint64 num_tasks = 0, extras = 0;
4576  kmp_int64 last_chunk =
4577  0; // reduce grainsize of last task by last_chunk in strict mode
4578  kmp_uint64 num_tasks_min = __kmp_taskloop_min_tasks;
4579  kmp_info_t *thread = __kmp_threads[gtid];
4580  kmp_taskdata_t *current_task = thread->th.th_current_task;
4581 
4582  KA_TRACE(20, ("__kmp_taskloop: T#%d, task %p, lb %lld, ub %lld, st %lld, "
4583  "grain %llu(%d, %d), dup %p\n",
4584  gtid, taskdata, lower, upper, st, grainsize, sched, modifier,
4585  task_dup));
4586 
4587  // compute trip count
4588  if (st == 1) { // most common case
4589  tc = upper - lower + 1;
4590  } else if (st < 0) {
4591  tc = (lower - upper) / (-st) + 1;
4592  } else { // st > 0
4593  tc = (upper - lower) / st + 1;
4594  }
4595  if (tc == 0) {
4596  KA_TRACE(20, ("__kmp_taskloop(exit): T#%d zero-trip loop\n", gtid));
4597  // free the pattern task and exit
4598  __kmp_task_start(gtid, task, current_task);
4599  // do not execute anything for zero-trip loop
4600  __kmp_task_finish<false>(gtid, task, current_task);
4601  return;
4602  }
4603 
4604 #if OMPT_SUPPORT && OMPT_OPTIONAL
4605  ompt_team_info_t *team_info = __ompt_get_teaminfo(0, NULL);
4606  ompt_task_info_t *task_info = __ompt_get_task_info_object(0);
4607  if (ompt_enabled.ompt_callback_work) {
4608  ompt_callbacks.ompt_callback(ompt_callback_work)(
4609  ompt_work_taskloop, ompt_scope_begin, &(team_info->parallel_data),
4610  &(task_info->task_data), tc, OMPT_GET_RETURN_ADDRESS(0));
4611  }
4612 #endif
4613 
4614  if (num_tasks_min == 0)
4615  // TODO: can we choose better default heuristic?
4616  num_tasks_min =
4617  KMP_MIN(thread->th.th_team_nproc * 10, INITIAL_TASK_DEQUE_SIZE);
4618 
4619  // compute num_tasks/grainsize based on the input provided
4620  switch (sched) {
4621  case 0: // no schedule clause specified, we can choose the default
4622  // let's try to schedule (team_size*10) tasks
4623  grainsize = thread->th.th_team_nproc * 10;
4624  KMP_FALLTHROUGH();
4625  case 2: // num_tasks provided
4626  if (grainsize > tc) {
4627  num_tasks = tc; // too big num_tasks requested, adjust values
4628  grainsize = 1;
4629  extras = 0;
4630  } else {
4631  num_tasks = grainsize;
4632  grainsize = tc / num_tasks;
4633  extras = tc % num_tasks;
4634  }
4635  break;
4636  case 1: // grainsize provided
4637  if (grainsize > tc) {
4638  num_tasks = 1;
4639  grainsize = tc; // too big grainsize requested, adjust values
4640  extras = 0;
4641  } else {
4642  if (modifier) {
4643  num_tasks = (tc + grainsize - 1) / grainsize;
4644  last_chunk = tc - (num_tasks * grainsize);
4645  extras = 0;
4646  } else {
4647  num_tasks = tc / grainsize;
4648  // adjust grainsize for balanced distribution of iterations
4649  grainsize = tc / num_tasks;
4650  extras = tc % num_tasks;
4651  }
4652  }
4653  break;
4654  default:
4655  KMP_ASSERT2(0, "unknown scheduling of taskloop");
4656  }
4657 
4658  KMP_DEBUG_ASSERT(tc == num_tasks * grainsize +
4659  (last_chunk < 0 ? last_chunk : extras));
4660  KMP_DEBUG_ASSERT(num_tasks > extras);
4661  KMP_DEBUG_ASSERT(num_tasks > 0);
4662  // =========================================================================
4663 
4664  // check if clause value first
4665  // Also require GOMP_taskloop to reduce to linear (taskdata->td_flags.native)
4666  if (if_val == 0) { // if(0) specified, mark task as serial
4667  taskdata->td_flags.task_serial = 1;
4668  taskdata->td_flags.tiedness = TASK_TIED; // AC: serial task cannot be untied
4669  // always start serial tasks linearly
4670  __kmp_taskloop_linear(loc, gtid, task, lb, ub, st, ub_glob, num_tasks,
4671  grainsize, extras, last_chunk, tc,
4672 #if OMPT_SUPPORT
4673  OMPT_GET_RETURN_ADDRESS(0),
4674 #endif
4675  task_dup);
4676  // !taskdata->td_flags.native => currently force linear spawning of tasks
4677  // for GOMP_taskloop
4678  } else if (num_tasks > num_tasks_min && !taskdata->td_flags.native) {
4679  KA_TRACE(20, ("__kmp_taskloop: T#%d, go recursive: tc %llu, #tasks %llu"
4680  "(%lld), grain %llu, extras %llu, last_chunk %lld\n",
4681  gtid, tc, num_tasks, num_tasks_min, grainsize, extras,
4682  last_chunk));
4683  __kmp_taskloop_recur(loc, gtid, task, lb, ub, st, ub_glob, num_tasks,
4684  grainsize, extras, last_chunk, tc, num_tasks_min,
4685 #if OMPT_SUPPORT
4686  OMPT_GET_RETURN_ADDRESS(0),
4687 #endif
4688  task_dup);
4689  } else {
4690  KA_TRACE(20, ("__kmp_taskloop: T#%d, go linear: tc %llu, #tasks %llu"
4691  "(%lld), grain %llu, extras %llu, last_chunk %lld\n",
4692  gtid, tc, num_tasks, num_tasks_min, grainsize, extras,
4693  last_chunk));
4694  __kmp_taskloop_linear(loc, gtid, task, lb, ub, st, ub_glob, num_tasks,
4695  grainsize, extras, last_chunk, tc,
4696 #if OMPT_SUPPORT
4697  OMPT_GET_RETURN_ADDRESS(0),
4698 #endif
4699  task_dup);
4700  }
4701 
4702 #if OMPT_SUPPORT && OMPT_OPTIONAL
4703  if (ompt_enabled.ompt_callback_work) {
4704  ompt_callbacks.ompt_callback(ompt_callback_work)(
4705  ompt_work_taskloop, ompt_scope_end, &(team_info->parallel_data),
4706  &(task_info->task_data), tc, OMPT_GET_RETURN_ADDRESS(0));
4707  }
4708 #endif
4709 
4710  if (nogroup == 0) {
4711 #if OMPT_SUPPORT && OMPT_OPTIONAL
4712  OMPT_STORE_RETURN_ADDRESS(gtid);
4713 #endif
4714  __kmpc_end_taskgroup(loc, gtid);
4715  }
4716  KA_TRACE(20, ("__kmp_taskloop(exit): T#%d\n", gtid));
4717 }
4718 
4735 void __kmpc_taskloop(ident_t *loc, int gtid, kmp_task_t *task, int if_val,
4736  kmp_uint64 *lb, kmp_uint64 *ub, kmp_int64 st, int nogroup,
4737  int sched, kmp_uint64 grainsize, void *task_dup) {
4738  __kmp_assert_valid_gtid(gtid);
4739  KA_TRACE(20, ("__kmpc_taskloop(enter): T#%d\n", gtid));
4740  __kmp_taskloop(loc, gtid, task, if_val, lb, ub, st, nogroup, sched, grainsize,
4741  0, task_dup);
4742  KA_TRACE(20, ("__kmpc_taskloop(exit): T#%d\n", gtid));
4743 }
4744 
4762 void __kmpc_taskloop_5(ident_t *loc, int gtid, kmp_task_t *task, int if_val,
4763  kmp_uint64 *lb, kmp_uint64 *ub, kmp_int64 st,
4764  int nogroup, int sched, kmp_uint64 grainsize,
4765  int modifier, void *task_dup) {
4766  __kmp_assert_valid_gtid(gtid);
4767  KA_TRACE(20, ("__kmpc_taskloop_5(enter): T#%d\n", gtid));
4768  __kmp_taskloop(loc, gtid, task, if_val, lb, ub, st, nogroup, sched, grainsize,
4769  modifier, task_dup);
4770  KA_TRACE(20, ("__kmpc_taskloop_5(exit): T#%d\n", gtid));
4771 }
void __kmpc_task_reduction_modifier_fini(ident_t *loc, int gtid, int is_ws)
void * __kmpc_task_reduction_modifier_init(ident_t *loc, int gtid, int is_ws, int num, void *data)
void __kmpc_taskloop(ident_t *loc, int gtid, kmp_task_t *task, int if_val, kmp_uint64 *lb, kmp_uint64 *ub, kmp_int64 st, int nogroup, int sched, kmp_uint64 grainsize, void *task_dup)
struct kmp_taskred_input kmp_taskred_input_t
kmp_int32 __kmpc_omp_reg_task_with_affinity(ident_t *loc_ref, kmp_int32 gtid, kmp_task_t *new_task, kmp_int32 naffins, kmp_task_affinity_info_t *affin_list)
kmp_taskred_flags_t flags
void * __kmpc_taskred_modifier_init(ident_t *loc, int gtid, int is_ws, int num, void *data)
struct kmp_taskred_data kmp_taskred_data_t
void __kmpc_proxy_task_completed_ooo(kmp_task_t *ptask)
#define KMP_COUNT_BLOCK(name)
Increments specified counter (name).
Definition: kmp_stats.h:904
void * __kmpc_taskred_init(int gtid, int num, void *data)
void * __kmpc_task_reduction_get_th_data(int gtid, void *tskgrp, void *data)
Definition: kmp.h:233
void __kmpc_proxy_task_completed(kmp_int32 gtid, kmp_task_t *ptask)
struct kmp_taskred_flags kmp_taskred_flags_t
void * __kmpc_task_reduction_init(int gtid, int num, void *data)
kmp_taskred_flags_t flags
kmp_taskred_flags_t flags
void __kmpc_taskloop_5(ident_t *loc, int gtid, kmp_task_t *task, int if_val, kmp_uint64 *lb, kmp_uint64 *ub, kmp_int64 st, int nogroup, int sched, kmp_uint64 grainsize, int modifier, void *task_dup)
struct kmp_task_red_input kmp_task_red_input_t