1 /* 2 * kmp_taskdeps.cpp 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 //#define KMP_SUPPORT_GRAPH_OUTPUT 1 14 15 #include "kmp.h" 16 #include "kmp_io.h" 17 #include "kmp_wait_release.h" 18 #include "kmp_taskdeps.h" 19 #if OMPT_SUPPORT 20 #include "ompt-specific.h" 21 #endif 22 23 // TODO: Improve memory allocation? keep a list of pre-allocated structures? 24 // allocate in blocks? re-use list finished list entries? 25 // TODO: don't use atomic ref counters for stack-allocated nodes. 26 // TODO: find an alternate to atomic refs for heap-allocated nodes? 27 // TODO: Finish graph output support 28 // TODO: kmp_lock_t seems a tad to big (and heavy weight) for this. Check other 29 // runtime locks 30 // TODO: Any ITT support needed? 31 32 #ifdef KMP_SUPPORT_GRAPH_OUTPUT 33 static std::atomic<kmp_int32> kmp_node_id_seed = ATOMIC_VAR_INIT(0); 34 #endif 35 36 static void __kmp_init_node(kmp_depnode_t *node) { 37 node->dn.successors = NULL; 38 node->dn.task = NULL; // will point to the right task 39 // once dependences have been processed 40 for (int i = 0; i < MAX_MTX_DEPS; ++i) 41 node->dn.mtx_locks[i] = NULL; 42 node->dn.mtx_num_locks = 0; 43 __kmp_init_lock(&node->dn.lock); 44 KMP_ATOMIC_ST_RLX(&node->dn.nrefs, 1); // init creates the first reference 45 #ifdef KMP_SUPPORT_GRAPH_OUTPUT 46 node->dn.id = KMP_ATOMIC_INC(&kmp_node_id_seed); 47 #endif 48 } 49 50 static inline kmp_depnode_t *__kmp_node_ref(kmp_depnode_t *node) { 51 KMP_ATOMIC_INC(&node->dn.nrefs); 52 return node; 53 } 54 55 enum { KMP_DEPHASH_OTHER_SIZE = 97, KMP_DEPHASH_MASTER_SIZE = 997 }; 56 57 size_t sizes[] = {997, 2003, 4001, 8191, 16001, 32003, 64007, 131071, 270029}; 58 const size_t MAX_GEN = 8; 59 60 static inline size_t __kmp_dephash_hash(kmp_intptr_t addr, size_t hsize) { 61 // TODO alternate to try: set = (((Addr64)(addrUsefulBits * 9.618)) % 62 // m_num_sets ); 63 return ((addr >> 6) ^ (addr >> 2)) % hsize; 64 } 65 66 static kmp_dephash_t *__kmp_dephash_extend(kmp_info_t *thread, 67 kmp_dephash_t *current_dephash) { 68 kmp_dephash_t *h; 69 70 size_t gen = current_dephash->generation + 1; 71 if (gen >= MAX_GEN) 72 return current_dephash; 73 size_t new_size = sizes[gen]; 74 75 size_t size_to_allocate = 76 new_size * sizeof(kmp_dephash_entry_t *) + sizeof(kmp_dephash_t); 77 78 #if USE_FAST_MEMORY 79 h = (kmp_dephash_t *)__kmp_fast_allocate(thread, size_to_allocate); 80 #else 81 h = (kmp_dephash_t *)__kmp_thread_malloc(thread, size_to_allocate); 82 #endif 83 84 h->size = new_size; 85 h->nelements = current_dephash->nelements; 86 h->buckets = (kmp_dephash_entry **)(h + 1); 87 h->generation = gen; 88 h->nconflicts = 0; 89 90 // make sure buckets are properly initialized 91 for (size_t i = 0; i < new_size; i++) { 92 h->buckets[i] = NULL; 93 } 94 95 // insert existing elements in the new table 96 for (size_t i = 0; i < current_dephash->size; i++) { 97 kmp_dephash_entry_t *next, *entry; 98 for (entry = current_dephash->buckets[i]; entry; entry = next) { 99 next = entry->next_in_bucket; 100 // Compute the new hash using the new size, and insert the entry in 101 // the new bucket. 102 size_t new_bucket = __kmp_dephash_hash(entry->addr, h->size); 103 entry->next_in_bucket = h->buckets[new_bucket]; 104 if (entry->next_in_bucket) { 105 h->nconflicts++; 106 } 107 h->buckets[new_bucket] = entry; 108 } 109 } 110 111 // Free old hash table 112 #if USE_FAST_MEMORY 113 __kmp_fast_free(thread, current_dephash); 114 #else 115 __kmp_thread_free(thread, current_dephash); 116 #endif 117 118 return h; 119 } 120 121 static kmp_dephash_t *__kmp_dephash_create(kmp_info_t *thread, 122 kmp_taskdata_t *current_task) { 123 kmp_dephash_t *h; 124 125 size_t h_size; 126 127 if (current_task->td_flags.tasktype == TASK_IMPLICIT) 128 h_size = KMP_DEPHASH_MASTER_SIZE; 129 else 130 h_size = KMP_DEPHASH_OTHER_SIZE; 131 132 size_t size = h_size * sizeof(kmp_dephash_entry_t *) + sizeof(kmp_dephash_t); 133 134 #if USE_FAST_MEMORY 135 h = (kmp_dephash_t *)__kmp_fast_allocate(thread, size); 136 #else 137 h = (kmp_dephash_t *)__kmp_thread_malloc(thread, size); 138 #endif 139 h->size = h_size; 140 141 h->generation = 0; 142 h->nelements = 0; 143 h->nconflicts = 0; 144 h->buckets = (kmp_dephash_entry **)(h + 1); 145 146 for (size_t i = 0; i < h_size; i++) 147 h->buckets[i] = 0; 148 149 return h; 150 } 151 152 static kmp_dephash_entry *__kmp_dephash_find(kmp_info_t *thread, 153 kmp_dephash_t **hash, 154 kmp_intptr_t addr) { 155 kmp_dephash_t *h = *hash; 156 if (h->nelements != 0 && h->nconflicts / h->size >= 1) { 157 *hash = __kmp_dephash_extend(thread, h); 158 h = *hash; 159 } 160 size_t bucket = __kmp_dephash_hash(addr, h->size); 161 162 kmp_dephash_entry_t *entry; 163 for (entry = h->buckets[bucket]; entry; entry = entry->next_in_bucket) 164 if (entry->addr == addr) 165 break; 166 167 if (entry == NULL) { 168 // create entry. This is only done by one thread so no locking required 169 #if USE_FAST_MEMORY 170 entry = (kmp_dephash_entry_t *)__kmp_fast_allocate( 171 thread, sizeof(kmp_dephash_entry_t)); 172 #else 173 entry = (kmp_dephash_entry_t *)__kmp_thread_malloc( 174 thread, sizeof(kmp_dephash_entry_t)); 175 #endif 176 entry->addr = addr; 177 entry->last_out = NULL; 178 entry->last_set = NULL; 179 entry->prev_set = NULL; 180 entry->last_flag = 0; 181 entry->mtx_lock = NULL; 182 entry->next_in_bucket = h->buckets[bucket]; 183 h->buckets[bucket] = entry; 184 h->nelements++; 185 if (entry->next_in_bucket) 186 h->nconflicts++; 187 } 188 return entry; 189 } 190 191 static kmp_depnode_list_t *__kmp_add_node(kmp_info_t *thread, 192 kmp_depnode_list_t *list, 193 kmp_depnode_t *node) { 194 kmp_depnode_list_t *new_head; 195 196 #if USE_FAST_MEMORY 197 new_head = (kmp_depnode_list_t *)__kmp_fast_allocate( 198 thread, sizeof(kmp_depnode_list_t)); 199 #else 200 new_head = (kmp_depnode_list_t *)__kmp_thread_malloc( 201 thread, sizeof(kmp_depnode_list_t)); 202 #endif 203 204 new_head->node = __kmp_node_ref(node); 205 new_head->next = list; 206 207 return new_head; 208 } 209 210 static inline void __kmp_track_dependence(kmp_int32 gtid, kmp_depnode_t *source, 211 kmp_depnode_t *sink, 212 kmp_task_t *sink_task) { 213 #ifdef KMP_SUPPORT_GRAPH_OUTPUT 214 kmp_taskdata_t *task_source = KMP_TASK_TO_TASKDATA(source->dn.task); 215 // do not use sink->dn.task as that is only filled after the dependences 216 // are already processed! 217 kmp_taskdata_t *task_sink = KMP_TASK_TO_TASKDATA(sink_task); 218 219 __kmp_printf("%d(%s) -> %d(%s)\n", source->dn.id, 220 task_source->td_ident->psource, sink->dn.id, 221 task_sink->td_ident->psource); 222 #endif 223 #if OMPT_SUPPORT && OMPT_OPTIONAL 224 /* OMPT tracks dependences between task (a=source, b=sink) in which 225 task a blocks the execution of b through the ompt_new_dependence_callback 226 */ 227 if (ompt_enabled.ompt_callback_task_dependence) { 228 kmp_taskdata_t *task_source = KMP_TASK_TO_TASKDATA(source->dn.task); 229 ompt_data_t *sink_data; 230 if (sink_task) 231 sink_data = &(KMP_TASK_TO_TASKDATA(sink_task)->ompt_task_info.task_data); 232 else 233 sink_data = &__kmp_threads[gtid]->th.ompt_thread_info.task_data; 234 235 ompt_callbacks.ompt_callback(ompt_callback_task_dependence)( 236 &(task_source->ompt_task_info.task_data), sink_data); 237 } 238 #endif /* OMPT_SUPPORT && OMPT_OPTIONAL */ 239 } 240 241 static inline kmp_int32 242 __kmp_depnode_link_successor(kmp_int32 gtid, kmp_info_t *thread, 243 kmp_task_t *task, kmp_depnode_t *node, 244 kmp_depnode_list_t *plist) { 245 if (!plist) 246 return 0; 247 kmp_int32 npredecessors = 0; 248 // link node as successor of list elements 249 for (kmp_depnode_list_t *p = plist; p; p = p->next) { 250 kmp_depnode_t *dep = p->node; 251 if (dep->dn.task) { 252 KMP_ACQUIRE_DEPNODE(gtid, dep); 253 if (dep->dn.task) { 254 __kmp_track_dependence(gtid, dep, node, task); 255 dep->dn.successors = __kmp_add_node(thread, dep->dn.successors, node); 256 KA_TRACE(40, ("__kmp_process_deps: T#%d adding dependence from %p to " 257 "%p\n", 258 gtid, KMP_TASK_TO_TASKDATA(dep->dn.task), 259 KMP_TASK_TO_TASKDATA(task))); 260 npredecessors++; 261 } 262 KMP_RELEASE_DEPNODE(gtid, dep); 263 } 264 } 265 return npredecessors; 266 } 267 268 static inline kmp_int32 __kmp_depnode_link_successor(kmp_int32 gtid, 269 kmp_info_t *thread, 270 kmp_task_t *task, 271 kmp_depnode_t *source, 272 kmp_depnode_t *sink) { 273 if (!sink) 274 return 0; 275 kmp_int32 npredecessors = 0; 276 if (sink->dn.task) { 277 // synchronously add source to sink' list of successors 278 KMP_ACQUIRE_DEPNODE(gtid, sink); 279 if (sink->dn.task) { 280 __kmp_track_dependence(gtid, sink, source, task); 281 sink->dn.successors = __kmp_add_node(thread, sink->dn.successors, source); 282 KA_TRACE(40, ("__kmp_process_deps: T#%d adding dependence from %p to " 283 "%p\n", 284 gtid, KMP_TASK_TO_TASKDATA(sink->dn.task), 285 KMP_TASK_TO_TASKDATA(task))); 286 npredecessors++; 287 } 288 KMP_RELEASE_DEPNODE(gtid, sink); 289 } 290 return npredecessors; 291 } 292 293 template <bool filter> 294 static inline kmp_int32 295 __kmp_process_deps(kmp_int32 gtid, kmp_depnode_t *node, kmp_dephash_t **hash, 296 bool dep_barrier, kmp_int32 ndeps, 297 kmp_depend_info_t *dep_list, kmp_task_t *task) { 298 KA_TRACE(30, ("__kmp_process_deps<%d>: T#%d processing %d dependences : " 299 "dep_barrier = %d\n", 300 filter, gtid, ndeps, dep_barrier)); 301 302 kmp_info_t *thread = __kmp_threads[gtid]; 303 kmp_int32 npredecessors = 0; 304 for (kmp_int32 i = 0; i < ndeps; i++) { 305 const kmp_depend_info_t *dep = &dep_list[i]; 306 307 if (filter && dep->base_addr == 0) 308 continue; // skip filtered entries 309 310 kmp_dephash_entry_t *info = 311 __kmp_dephash_find(thread, hash, dep->base_addr); 312 kmp_depnode_t *last_out = info->last_out; 313 kmp_depnode_list_t *last_set = info->last_set; 314 kmp_depnode_list_t *prev_set = info->prev_set; 315 316 if (dep->flags.out) { // out or inout --> clean lists if any 317 if (last_set) { 318 npredecessors += 319 __kmp_depnode_link_successor(gtid, thread, task, node, last_set); 320 __kmp_depnode_list_free(thread, last_set); 321 __kmp_depnode_list_free(thread, prev_set); 322 info->last_set = NULL; 323 info->prev_set = NULL; 324 info->last_flag = 0; // no sets in this dephash entry 325 } else { 326 npredecessors += 327 __kmp_depnode_link_successor(gtid, thread, task, node, last_out); 328 } 329 __kmp_node_deref(thread, last_out); 330 if (!dep_barrier) { 331 info->last_out = __kmp_node_ref(node); 332 } else { 333 // if this is a sync point in the serial sequence, then the previous 334 // outputs are guaranteed to be completed after the execution of this 335 // task so the previous output nodes can be cleared. 336 info->last_out = NULL; 337 } 338 } else { // either IN or MTX or SET 339 if (info->last_flag == 0 || info->last_flag == dep->flag) { 340 // last_set either didn't exist or of same dep kind 341 // link node as successor of the last_out if any 342 npredecessors += 343 __kmp_depnode_link_successor(gtid, thread, task, node, last_out); 344 // link node as successor of all nodes in the prev_set if any 345 npredecessors += 346 __kmp_depnode_link_successor(gtid, thread, task, node, prev_set); 347 } else { // last_set is of different dep kind, make it prev_set 348 // link node as successor of all nodes in the last_set 349 npredecessors += 350 __kmp_depnode_link_successor(gtid, thread, task, node, last_set); 351 // clean last_out if any 352 __kmp_node_deref(thread, last_out); 353 info->last_out = NULL; 354 // clean prev_set if any 355 __kmp_depnode_list_free(thread, prev_set); 356 // move last_set to prev_set, new last_set will be allocated 357 info->prev_set = last_set; 358 info->last_set = NULL; 359 } 360 info->last_flag = dep->flag; // store dep kind of the last_set 361 info->last_set = __kmp_add_node(thread, info->last_set, node); 362 363 // check if we are processing MTX dependency 364 if (dep->flag == KMP_DEP_MTX) { 365 if (info->mtx_lock == NULL) { 366 info->mtx_lock = (kmp_lock_t *)__kmp_allocate(sizeof(kmp_lock_t)); 367 __kmp_init_lock(info->mtx_lock); 368 } 369 KMP_DEBUG_ASSERT(node->dn.mtx_num_locks < MAX_MTX_DEPS); 370 kmp_int32 m; 371 // Save lock in node's array 372 for (m = 0; m < MAX_MTX_DEPS; ++m) { 373 // sort pointers in decreasing order to avoid potential livelock 374 if (node->dn.mtx_locks[m] < info->mtx_lock) { 375 KMP_DEBUG_ASSERT(!node->dn.mtx_locks[node->dn.mtx_num_locks]); 376 for (int n = node->dn.mtx_num_locks; n > m; --n) { 377 // shift right all lesser non-NULL pointers 378 KMP_DEBUG_ASSERT(node->dn.mtx_locks[n - 1] != NULL); 379 node->dn.mtx_locks[n] = node->dn.mtx_locks[n - 1]; 380 } 381 node->dn.mtx_locks[m] = info->mtx_lock; 382 break; 383 } 384 } 385 KMP_DEBUG_ASSERT(m < MAX_MTX_DEPS); // must break from loop 386 node->dn.mtx_num_locks++; 387 } 388 } 389 } 390 KA_TRACE(30, ("__kmp_process_deps<%d>: T#%d found %d predecessors\n", filter, 391 gtid, npredecessors)); 392 return npredecessors; 393 } 394 395 #define NO_DEP_BARRIER (false) 396 #define DEP_BARRIER (true) 397 398 // returns true if the task has any outstanding dependence 399 static bool __kmp_check_deps(kmp_int32 gtid, kmp_depnode_t *node, 400 kmp_task_t *task, kmp_dephash_t **hash, 401 bool dep_barrier, kmp_int32 ndeps, 402 kmp_depend_info_t *dep_list, 403 kmp_int32 ndeps_noalias, 404 kmp_depend_info_t *noalias_dep_list) { 405 int i, n_mtxs = 0; 406 #if KMP_DEBUG 407 kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(task); 408 #endif 409 KA_TRACE(20, ("__kmp_check_deps: T#%d checking dependences for task %p : %d " 410 "possibly aliased dependences, %d non-aliased dependences : " 411 "dep_barrier=%d .\n", 412 gtid, taskdata, ndeps, ndeps_noalias, dep_barrier)); 413 414 // Filter deps in dep_list 415 // TODO: Different algorithm for large dep_list ( > 10 ? ) 416 for (i = 0; i < ndeps; i++) { 417 if (dep_list[i].base_addr != 0) { 418 KMP_DEBUG_ASSERT( 419 dep_list[i].flag == KMP_DEP_IN || dep_list[i].flag == KMP_DEP_OUT || 420 dep_list[i].flag == KMP_DEP_INOUT || 421 dep_list[i].flag == KMP_DEP_MTX || dep_list[i].flag == KMP_DEP_SET); 422 for (int j = i + 1; j < ndeps; j++) { 423 if (dep_list[i].base_addr == dep_list[j].base_addr) { 424 if (dep_list[i].flag != dep_list[j].flag) { 425 // two different dependences on same address work identical to OUT 426 dep_list[i].flag = KMP_DEP_OUT; 427 } 428 dep_list[j].base_addr = 0; // Mark j element as void 429 } 430 } 431 if (dep_list[i].flag == KMP_DEP_MTX) { 432 // limit number of mtx deps to MAX_MTX_DEPS per node 433 if (n_mtxs < MAX_MTX_DEPS && task != NULL) { 434 ++n_mtxs; 435 } else { 436 dep_list[i].flag = KMP_DEP_OUT; // downgrade mutexinoutset to inout 437 } 438 } 439 } 440 } 441 442 // doesn't need to be atomic as no other thread is going to be accessing this 443 // node just yet. 444 // npredecessors is set -1 to ensure that none of the releasing tasks queues 445 // this task before we have finished processing all the dependences 446 node->dn.npredecessors = -1; 447 448 // used to pack all npredecessors additions into a single atomic operation at 449 // the end 450 int npredecessors; 451 452 npredecessors = __kmp_process_deps<true>(gtid, node, hash, dep_barrier, ndeps, 453 dep_list, task); 454 npredecessors += __kmp_process_deps<false>( 455 gtid, node, hash, dep_barrier, ndeps_noalias, noalias_dep_list, task); 456 457 node->dn.task = task; 458 KMP_MB(); 459 460 // Account for our initial fake value 461 npredecessors++; 462 463 // Update predecessors and obtain current value to check if there are still 464 // any outstanding dependences (some tasks may have finished while we 465 // processed the dependences) 466 npredecessors = 467 node->dn.npredecessors.fetch_add(npredecessors) + npredecessors; 468 469 KA_TRACE(20, ("__kmp_check_deps: T#%d found %d predecessors for task %p \n", 470 gtid, npredecessors, taskdata)); 471 472 // beyond this point the task could be queued (and executed) by a releasing 473 // task... 474 return npredecessors > 0 ? true : false; 475 } 476 477 /*! 478 @ingroup TASKING 479 @param loc_ref location of the original task directive 480 @param gtid Global Thread ID of encountering thread 481 @param new_task task thunk allocated by __kmp_omp_task_alloc() for the ''new 482 task'' 483 @param ndeps Number of depend items with possible aliasing 484 @param dep_list List of depend items with possible aliasing 485 @param ndeps_noalias Number of depend items with no aliasing 486 @param noalias_dep_list List of depend items with no aliasing 487 488 @return Returns either TASK_CURRENT_NOT_QUEUED if the current task was not 489 suspended and queued, or TASK_CURRENT_QUEUED if it was suspended and queued 490 491 Schedule a non-thread-switchable task with dependences for execution 492 */ 493 kmp_int32 __kmpc_omp_task_with_deps(ident_t *loc_ref, kmp_int32 gtid, 494 kmp_task_t *new_task, kmp_int32 ndeps, 495 kmp_depend_info_t *dep_list, 496 kmp_int32 ndeps_noalias, 497 kmp_depend_info_t *noalias_dep_list) { 498 499 kmp_taskdata_t *new_taskdata = KMP_TASK_TO_TASKDATA(new_task); 500 KA_TRACE(10, ("__kmpc_omp_task_with_deps(enter): T#%d loc=%p task=%p\n", gtid, 501 loc_ref, new_taskdata)); 502 __kmp_assert_valid_gtid(gtid); 503 kmp_info_t *thread = __kmp_threads[gtid]; 504 kmp_taskdata_t *current_task = thread->th.th_current_task; 505 506 #if OMPT_SUPPORT 507 if (ompt_enabled.enabled) { 508 if (!current_task->ompt_task_info.frame.enter_frame.ptr) 509 current_task->ompt_task_info.frame.enter_frame.ptr = 510 OMPT_GET_FRAME_ADDRESS(0); 511 if (ompt_enabled.ompt_callback_task_create) { 512 ompt_callbacks.ompt_callback(ompt_callback_task_create)( 513 &(current_task->ompt_task_info.task_data), 514 &(current_task->ompt_task_info.frame), 515 &(new_taskdata->ompt_task_info.task_data), 516 ompt_task_explicit | TASK_TYPE_DETAILS_FORMAT(new_taskdata), 1, 517 OMPT_LOAD_OR_GET_RETURN_ADDRESS(gtid)); 518 } 519 520 new_taskdata->ompt_task_info.frame.enter_frame.ptr = 521 OMPT_GET_FRAME_ADDRESS(0); 522 } 523 524 #if OMPT_OPTIONAL 525 /* OMPT grab all dependences if requested by the tool */ 526 if (ndeps + ndeps_noalias > 0 && ompt_enabled.ompt_callback_dependences) { 527 kmp_int32 i; 528 529 int ompt_ndeps = ndeps + ndeps_noalias; 530 ompt_dependence_t *ompt_deps = (ompt_dependence_t *)KMP_OMPT_DEPS_ALLOC( 531 thread, (ndeps + ndeps_noalias) * sizeof(ompt_dependence_t)); 532 533 KMP_ASSERT(ompt_deps != NULL); 534 535 for (i = 0; i < ndeps; i++) { 536 ompt_deps[i].variable.ptr = (void *)dep_list[i].base_addr; 537 if (dep_list[i].flags.in && dep_list[i].flags.out) 538 ompt_deps[i].dependence_type = ompt_dependence_type_inout; 539 else if (dep_list[i].flags.out) 540 ompt_deps[i].dependence_type = ompt_dependence_type_out; 541 else if (dep_list[i].flags.in) 542 ompt_deps[i].dependence_type = ompt_dependence_type_in; 543 else if (dep_list[i].flags.mtx) 544 ompt_deps[i].dependence_type = ompt_dependence_type_mutexinoutset; 545 else if (dep_list[i].flags.set) 546 ompt_deps[i].dependence_type = ompt_dependence_type_inoutset; 547 } 548 for (i = 0; i < ndeps_noalias; i++) { 549 ompt_deps[ndeps + i].variable.ptr = (void *)noalias_dep_list[i].base_addr; 550 if (noalias_dep_list[i].flags.in && noalias_dep_list[i].flags.out) 551 ompt_deps[ndeps + i].dependence_type = ompt_dependence_type_inout; 552 else if (noalias_dep_list[i].flags.out) 553 ompt_deps[ndeps + i].dependence_type = ompt_dependence_type_out; 554 else if (noalias_dep_list[i].flags.in) 555 ompt_deps[ndeps + i].dependence_type = ompt_dependence_type_in; 556 else if (noalias_dep_list[i].flags.mtx) 557 ompt_deps[ndeps + i].dependence_type = 558 ompt_dependence_type_mutexinoutset; 559 else if (noalias_dep_list[i].flags.set) 560 ompt_deps[ndeps + i].dependence_type = ompt_dependence_type_inoutset; 561 } 562 ompt_callbacks.ompt_callback(ompt_callback_dependences)( 563 &(new_taskdata->ompt_task_info.task_data), ompt_deps, ompt_ndeps); 564 /* We can now free the allocated memory for the dependences */ 565 /* For OMPD we might want to delay the free until end of this function */ 566 KMP_OMPT_DEPS_FREE(thread, ompt_deps); 567 } 568 #endif /* OMPT_OPTIONAL */ 569 #endif /* OMPT_SUPPORT */ 570 571 bool serial = current_task->td_flags.team_serial || 572 current_task->td_flags.tasking_ser || 573 current_task->td_flags.final; 574 kmp_task_team_t *task_team = thread->th.th_task_team; 575 serial = serial && 576 !(task_team && (task_team->tt.tt_found_proxy_tasks || 577 task_team->tt.tt_hidden_helper_task_encountered)); 578 579 if (!serial && (ndeps > 0 || ndeps_noalias > 0)) { 580 /* if no dependences have been tracked yet, create the dependence hash */ 581 if (current_task->td_dephash == NULL) 582 current_task->td_dephash = __kmp_dephash_create(thread, current_task); 583 584 #if USE_FAST_MEMORY 585 kmp_depnode_t *node = 586 (kmp_depnode_t *)__kmp_fast_allocate(thread, sizeof(kmp_depnode_t)); 587 #else 588 kmp_depnode_t *node = 589 (kmp_depnode_t *)__kmp_thread_malloc(thread, sizeof(kmp_depnode_t)); 590 #endif 591 592 __kmp_init_node(node); 593 new_taskdata->td_depnode = node; 594 595 if (__kmp_check_deps(gtid, node, new_task, ¤t_task->td_dephash, 596 NO_DEP_BARRIER, ndeps, dep_list, ndeps_noalias, 597 noalias_dep_list)) { 598 KA_TRACE(10, ("__kmpc_omp_task_with_deps(exit): T#%d task had blocking " 599 "dependences: " 600 "loc=%p task=%p, return: TASK_CURRENT_NOT_QUEUED\n", 601 gtid, loc_ref, new_taskdata)); 602 #if OMPT_SUPPORT 603 if (ompt_enabled.enabled) { 604 current_task->ompt_task_info.frame.enter_frame = ompt_data_none; 605 } 606 #endif 607 return TASK_CURRENT_NOT_QUEUED; 608 } 609 } else { 610 KA_TRACE(10, ("__kmpc_omp_task_with_deps(exit): T#%d ignored dependences " 611 "for task (serialized) loc=%p task=%p\n", 612 gtid, loc_ref, new_taskdata)); 613 } 614 615 KA_TRACE(10, ("__kmpc_omp_task_with_deps(exit): T#%d task had no blocking " 616 "dependences : " 617 "loc=%p task=%p, transferring to __kmp_omp_task\n", 618 gtid, loc_ref, new_taskdata)); 619 620 kmp_int32 ret = __kmp_omp_task(gtid, new_task, true); 621 #if OMPT_SUPPORT 622 if (ompt_enabled.enabled) { 623 current_task->ompt_task_info.frame.enter_frame = ompt_data_none; 624 } 625 #endif 626 return ret; 627 } 628 629 #if OMPT_SUPPORT 630 void __ompt_taskwait_dep_finish(kmp_taskdata_t *current_task, 631 ompt_data_t *taskwait_task_data) { 632 if (ompt_enabled.ompt_callback_task_schedule) { 633 ompt_callbacks.ompt_callback(ompt_callback_task_schedule)( 634 taskwait_task_data, ompt_taskwait_complete, NULL); 635 } 636 current_task->ompt_task_info.frame.enter_frame.ptr = NULL; 637 *taskwait_task_data = ompt_data_none; 638 } 639 #endif /* OMPT_SUPPORT */ 640 641 /*! 642 @ingroup TASKING 643 @param loc_ref location of the original task directive 644 @param gtid Global Thread ID of encountering thread 645 @param ndeps Number of depend items with possible aliasing 646 @param dep_list List of depend items with possible aliasing 647 @param ndeps_noalias Number of depend items with no aliasing 648 @param noalias_dep_list List of depend items with no aliasing 649 650 Blocks the current task until all specifies dependences have been fulfilled. 651 */ 652 void __kmpc_omp_wait_deps(ident_t *loc_ref, kmp_int32 gtid, kmp_int32 ndeps, 653 kmp_depend_info_t *dep_list, kmp_int32 ndeps_noalias, 654 kmp_depend_info_t *noalias_dep_list) { 655 KA_TRACE(10, ("__kmpc_omp_wait_deps(enter): T#%d loc=%p\n", gtid, loc_ref)); 656 657 if (ndeps == 0 && ndeps_noalias == 0) { 658 KA_TRACE(10, ("__kmpc_omp_wait_deps(exit): T#%d has no dependences to " 659 "wait upon : loc=%p\n", 660 gtid, loc_ref)); 661 return; 662 } 663 __kmp_assert_valid_gtid(gtid); 664 kmp_info_t *thread = __kmp_threads[gtid]; 665 kmp_taskdata_t *current_task = thread->th.th_current_task; 666 667 #if OMPT_SUPPORT 668 // this function represents a taskwait construct with depend clause 669 // We signal 4 events: 670 // - creation of the taskwait task 671 // - dependences of the taskwait task 672 // - schedule and finish of the taskwait task 673 ompt_data_t *taskwait_task_data = &thread->th.ompt_thread_info.task_data; 674 KMP_ASSERT(taskwait_task_data->ptr == NULL); 675 if (ompt_enabled.enabled) { 676 if (!current_task->ompt_task_info.frame.enter_frame.ptr) 677 current_task->ompt_task_info.frame.enter_frame.ptr = 678 OMPT_GET_FRAME_ADDRESS(0); 679 if (ompt_enabled.ompt_callback_task_create) { 680 ompt_callbacks.ompt_callback(ompt_callback_task_create)( 681 &(current_task->ompt_task_info.task_data), 682 &(current_task->ompt_task_info.frame), taskwait_task_data, 683 ompt_task_taskwait | ompt_task_undeferred | ompt_task_mergeable, 1, 684 OMPT_LOAD_OR_GET_RETURN_ADDRESS(gtid)); 685 } 686 } 687 688 #if OMPT_OPTIONAL 689 /* OMPT grab all dependences if requested by the tool */ 690 if (ndeps + ndeps_noalias > 0 && ompt_enabled.ompt_callback_dependences) { 691 kmp_int32 i; 692 693 int ompt_ndeps = ndeps + ndeps_noalias; 694 ompt_dependence_t *ompt_deps = (ompt_dependence_t *)KMP_OMPT_DEPS_ALLOC( 695 thread, (ndeps + ndeps_noalias) * sizeof(ompt_dependence_t)); 696 697 KMP_ASSERT(ompt_deps != NULL); 698 699 for (i = 0; i < ndeps; i++) { 700 ompt_deps[i].variable.ptr = (void *)dep_list[i].base_addr; 701 if (dep_list[i].flags.in && dep_list[i].flags.out) 702 ompt_deps[i].dependence_type = ompt_dependence_type_inout; 703 else if (dep_list[i].flags.out) 704 ompt_deps[i].dependence_type = ompt_dependence_type_out; 705 else if (dep_list[i].flags.in) 706 ompt_deps[i].dependence_type = ompt_dependence_type_in; 707 else if (dep_list[i].flags.mtx) 708 ompt_deps[ndeps + i].dependence_type = 709 ompt_dependence_type_mutexinoutset; 710 else if (dep_list[i].flags.set) 711 ompt_deps[ndeps + i].dependence_type = ompt_dependence_type_inoutset; 712 } 713 for (i = 0; i < ndeps_noalias; i++) { 714 ompt_deps[ndeps + i].variable.ptr = (void *)noalias_dep_list[i].base_addr; 715 if (noalias_dep_list[i].flags.in && noalias_dep_list[i].flags.out) 716 ompt_deps[ndeps + i].dependence_type = ompt_dependence_type_inout; 717 else if (noalias_dep_list[i].flags.out) 718 ompt_deps[ndeps + i].dependence_type = ompt_dependence_type_out; 719 else if (noalias_dep_list[i].flags.in) 720 ompt_deps[ndeps + i].dependence_type = ompt_dependence_type_in; 721 else if (noalias_dep_list[i].flags.mtx) 722 ompt_deps[ndeps + i].dependence_type = 723 ompt_dependence_type_mutexinoutset; 724 else if (noalias_dep_list[i].flags.set) 725 ompt_deps[ndeps + i].dependence_type = ompt_dependence_type_inoutset; 726 } 727 ompt_callbacks.ompt_callback(ompt_callback_dependences)( 728 taskwait_task_data, ompt_deps, ompt_ndeps); 729 /* We can now free the allocated memory for the dependences */ 730 /* For OMPD we might want to delay the free until end of this function */ 731 KMP_OMPT_DEPS_FREE(thread, ompt_deps); 732 ompt_deps = NULL; 733 } 734 #endif /* OMPT_OPTIONAL */ 735 #endif /* OMPT_SUPPORT */ 736 737 // We can return immediately as: 738 // - dependences are not computed in serial teams (except with proxy tasks) 739 // - if the dephash is not yet created it means we have nothing to wait for 740 bool ignore = current_task->td_flags.team_serial || 741 current_task->td_flags.tasking_ser || 742 current_task->td_flags.final; 743 ignore = ignore && thread->th.th_task_team != NULL && 744 thread->th.th_task_team->tt.tt_found_proxy_tasks == FALSE; 745 ignore = ignore || current_task->td_dephash == NULL; 746 747 if (ignore) { 748 KA_TRACE(10, ("__kmpc_omp_wait_deps(exit): T#%d has no blocking " 749 "dependences : loc=%p\n", 750 gtid, loc_ref)); 751 #if OMPT_SUPPORT 752 __ompt_taskwait_dep_finish(current_task, taskwait_task_data); 753 #endif /* OMPT_SUPPORT */ 754 return; 755 } 756 757 kmp_depnode_t node = {0}; 758 __kmp_init_node(&node); 759 // the stack owns the node 760 __kmp_node_ref(&node); 761 762 if (!__kmp_check_deps(gtid, &node, NULL, ¤t_task->td_dephash, 763 DEP_BARRIER, ndeps, dep_list, ndeps_noalias, 764 noalias_dep_list)) { 765 KA_TRACE(10, ("__kmpc_omp_wait_deps(exit): T#%d has no blocking " 766 "dependences : loc=%p\n", 767 gtid, loc_ref)); 768 #if OMPT_SUPPORT 769 __ompt_taskwait_dep_finish(current_task, taskwait_task_data); 770 #endif /* OMPT_SUPPORT */ 771 return; 772 } 773 774 int thread_finished = FALSE; 775 kmp_flag_32<false, false> flag( 776 (std::atomic<kmp_uint32> *)&node.dn.npredecessors, 0U); 777 while (node.dn.npredecessors > 0) { 778 flag.execute_tasks(thread, gtid, FALSE, 779 &thread_finished USE_ITT_BUILD_ARG(NULL), 780 __kmp_task_stealing_constraint); 781 } 782 783 #if OMPT_SUPPORT 784 __ompt_taskwait_dep_finish(current_task, taskwait_task_data); 785 #endif /* OMPT_SUPPORT */ 786 KA_TRACE(10, ("__kmpc_omp_wait_deps(exit): T#%d finished waiting : loc=%p\n", 787 gtid, loc_ref)); 788 } 789