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