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