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