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