LLVM OpenMP* Runtime Library
kmp_taskdeps.h
1 /*
2  * kmp_taskdeps.h
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 #ifndef KMP_TASKDEPS_H
14 #define KMP_TASKDEPS_H
15 
16 #include "kmp.h"
17 
18 #define KMP_ACQUIRE_DEPNODE(gtid, n) __kmp_acquire_lock(&(n)->dn.lock, (gtid))
19 #define KMP_RELEASE_DEPNODE(gtid, n) __kmp_release_lock(&(n)->dn.lock, (gtid))
20 
21 static inline void __kmp_node_deref(kmp_info_t *thread, kmp_depnode_t *node) {
22  if (!node)
23  return;
24 
25  kmp_int32 n = KMP_ATOMIC_DEC(&node->dn.nrefs) - 1;
26  KMP_DEBUG_ASSERT(n >= 0);
27  if (n == 0) {
28 #if USE_ITT_BUILD && USE_ITT_NOTIFY
29  __itt_sync_destroy(node);
30 #endif
31  KMP_ASSERT(node->dn.nrefs == 0);
32 #if USE_FAST_MEMORY
33  __kmp_fast_free(thread, node);
34 #else
35  __kmp_thread_free(thread, node);
36 #endif
37  }
38 }
39 
40 static inline void __kmp_depnode_list_free(kmp_info_t *thread,
41  kmp_depnode_list *list) {
42  kmp_depnode_list *next;
43 
44  for (; list; list = next) {
45  next = list->next;
46 
47  __kmp_node_deref(thread, list->node);
48 #if USE_FAST_MEMORY
49  __kmp_fast_free(thread, list);
50 #else
51  __kmp_thread_free(thread, list);
52 #endif
53  }
54 }
55 
56 static inline void __kmp_dephash_free_entries(kmp_info_t *thread,
57  kmp_dephash_t *h) {
58  for (size_t i = 0; i < h->size; i++) {
59  if (h->buckets[i]) {
60  kmp_dephash_entry_t *next;
61  for (kmp_dephash_entry_t *entry = h->buckets[i]; entry; entry = next) {
62  next = entry->next_in_bucket;
63  __kmp_depnode_list_free(thread, entry->last_set);
64  __kmp_depnode_list_free(thread, entry->prev_set);
65  __kmp_node_deref(thread, entry->last_out);
66  if (entry->mtx_lock) {
67  __kmp_destroy_lock(entry->mtx_lock);
68  __kmp_free(entry->mtx_lock);
69  }
70 #if USE_FAST_MEMORY
71  __kmp_fast_free(thread, entry);
72 #else
73  __kmp_thread_free(thread, entry);
74 #endif
75  }
76  h->buckets[i] = 0;
77  }
78  }
79  __kmp_node_deref(thread, h->last_all);
80  h->last_all = NULL;
81 }
82 
83 static inline void __kmp_dephash_free(kmp_info_t *thread, kmp_dephash_t *h) {
84  __kmp_dephash_free_entries(thread, h);
85 #if USE_FAST_MEMORY
86  __kmp_fast_free(thread, h);
87 #else
88  __kmp_thread_free(thread, h);
89 #endif
90 }
91 
92 extern void __kmpc_give_task(kmp_task_t *ptask, kmp_int32 start);
93 
94 static inline void __kmp_release_deps(kmp_int32 gtid, kmp_taskdata_t *task) {
95  kmp_info_t *thread = __kmp_threads[gtid];
96  kmp_depnode_t *node = task->td_depnode;
97 
98  // Check mutexinoutset dependencies, release locks
99  if (UNLIKELY(node && (node->dn.mtx_num_locks < 0))) {
100  // negative num_locks means all locks were acquired
101  node->dn.mtx_num_locks = -node->dn.mtx_num_locks;
102  for (int i = node->dn.mtx_num_locks - 1; i >= 0; --i) {
103  KMP_DEBUG_ASSERT(node->dn.mtx_locks[i] != NULL);
104  __kmp_release_lock(node->dn.mtx_locks[i], gtid);
105  }
106  }
107 
108  if (task->td_dephash) {
109  KA_TRACE(
110  40, ("__kmp_release_deps: T#%d freeing dependencies hash of task %p.\n",
111  gtid, task));
112  __kmp_dephash_free(thread, task->td_dephash);
113  task->td_dephash = NULL;
114  }
115 
116  if (!node)
117  return;
118 
119  KA_TRACE(20, ("__kmp_release_deps: T#%d notifying successors of task %p.\n",
120  gtid, task));
121 
122  KMP_ACQUIRE_DEPNODE(gtid, node);
123  node->dn.task =
124  NULL; // mark this task as finished, so no new dependencies are generated
125  KMP_RELEASE_DEPNODE(gtid, node);
126 
127  kmp_depnode_list_t *next;
128  kmp_taskdata_t *next_taskdata;
129  for (kmp_depnode_list_t *p = node->dn.successors; p; p = next) {
130  kmp_depnode_t *successor = p->node;
131 #if USE_ITT_BUILD && USE_ITT_NOTIFY
132  __itt_sync_releasing(successor);
133 #endif
134  kmp_int32 npredecessors = KMP_ATOMIC_DEC(&successor->dn.npredecessors) - 1;
135 
136  // successor task can be NULL for wait_depends or because deps are still
137  // being processed
138  if (npredecessors == 0) {
139 #if USE_ITT_BUILD && USE_ITT_NOTIFY
140  __itt_sync_acquired(successor);
141 #endif
142  KMP_MB();
143  if (successor->dn.task) {
144  KA_TRACE(20, ("__kmp_release_deps: T#%d successor %p of %p scheduled "
145  "for execution.\n",
146  gtid, successor->dn.task, task));
147  // If a regular task depending on a hidden helper task, when the
148  // hidden helper task is done, the regular task should be executed by
149  // its encountering team.
150  if (KMP_HIDDEN_HELPER_THREAD(gtid)) {
151  // Hidden helper thread can only execute hidden helper tasks
152  KMP_ASSERT(task->td_flags.hidden_helper);
153  next_taskdata = KMP_TASK_TO_TASKDATA(successor->dn.task);
154  // If the dependent task is a regular task, we need to push to its
155  // encountering thread's queue; otherwise, it can be pushed to its own
156  // queue.
157  if (!next_taskdata->td_flags.hidden_helper) {
158  kmp_int32 encountering_gtid =
159  next_taskdata->td_alloc_thread->th.th_info.ds.ds_gtid;
160  kmp_int32 encountering_tid = __kmp_tid_from_gtid(encountering_gtid);
161  __kmpc_give_task(successor->dn.task, encountering_tid);
162  } else {
163  __kmp_omp_task(gtid, successor->dn.task, false);
164  }
165  } else {
166  __kmp_omp_task(gtid, successor->dn.task, false);
167  }
168  }
169  }
170 
171  next = p->next;
172  __kmp_node_deref(thread, p->node);
173 #if USE_FAST_MEMORY
174  __kmp_fast_free(thread, p);
175 #else
176  __kmp_thread_free(thread, p);
177 #endif
178  }
179 
180  __kmp_node_deref(thread, node);
181 
182  KA_TRACE(
183  20,
184  ("__kmp_release_deps: T#%d all successors of %p notified of completion\n",
185  gtid, task));
186 }
187 
188 #endif // KMP_TASKDEPS_H