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