libgomp/task.c

   1 /* Copyright (C) 2007-2013 Free Software Foundation, Inc.
   2    Contributed by Richard Henderson <rth@redhat.com>.
   3
   4    This file is part of the GNU OpenMP Library (libgomp).
   5
   6    Libgomp is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3, or (at your option)
   9    any later version.
  10
  11    Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY
  12    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  13    FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  14    more details.
  15
  16    Under Section 7 of GPL version 3, you are granted additional
  17    permissions described in the GCC Runtime Library Exception, version
  18    3.1, as published by the Free Software Foundation.
  19
  20    You should have received a copy of the GNU General Public License and
  21    a copy of the GCC Runtime Library Exception along with this program;
  22    see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23    <http://www.gnu.org/licenses/>.  */
  24
  25 /* This file handles the maintainence of tasks in response to task
  26    creation and termination.  */
  27
  28 #include "libgomp.h"
  29 #include <stdlib.h>
  30 #include <string.h>
  31
  32 typedef struct gomp_task_depend_entry *hash_entry_type;
  33
  34 static inline void *
  35 htab_alloc (size_t size)
  36 {
  37   return gomp_malloc (size);
  38 }
  39
  40 static inline void
  41 htab_free (void *ptr)
  42 {
  43   free (ptr);
  44 }
  45
  46 #include "hashtab.h"
  47
  48 static inline hashval_t
  49 htab_hash (hash_entry_type element)
  50 {
  51   return hash_pointer (element->addr);
  52 }
  53
  54 static inline bool
  55 htab_eq (hash_entry_type x, hash_entry_type y)
  56 {
  57   return x->addr == y->addr;
  58 }
  59
  60 /* Create a new task data structure.  */
  61
  62 void
  63 gomp_init_task (struct gomp_task *task, struct gomp_task *parent_task,
  64                 struct gomp_task_icv *prev_icv)
  65 {
  66   task->parent = parent_task;
  67   task->icv = *prev_icv;
  68   task->kind = GOMP_TASK_IMPLICIT;
  69   task->in_taskwait = false;
  70   task->in_tied_task = false;
  71   task->final_task = false;
  72   task->copy_ctors_done = false;
  73   task->children = NULL;
  74   task->taskgroup = NULL;
  75   task->dependers = NULL;
  76   task->depend_hash = NULL;
  77   task->depend_count = 0;
  78   gomp_sem_init (&task->taskwait_sem, 0);
  79 }
  80
  81 /* Clean up a task, after completing it.  */
  82
  83 void
  84 gomp_end_task (void)
  85 {
  86   struct gomp_thread *thr = gomp_thread ();
  87   struct gomp_task *task = thr->task;
  88
  89   gomp_finish_task (task);
  90   thr->task = task->parent;
  91 }
  92
  93 static inline void
  94 gomp_clear_parent (struct gomp_task *children)
  95 {
  96   struct gomp_task *task = children;
  97
  98   if (task)
  99     do
 100       {
 101         task->parent = NULL;
 102         task = task->next_child;
 103       }
 104     while (task != children);
 105 }
 106
 107 /* Called when encountering an explicit task directive.  If IF_CLAUSE is
 108    false, then we must not delay in executing the task.  If UNTIED is true,
 109    then the task may be executed by any member of the team.  */
 110
 111 void
 112 GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
 113            long arg_size, long arg_align, bool if_clause, unsigned flags,
 114            void **depend)
 115 {
 116   struct gomp_thread *thr = gomp_thread ();
 117   struct gomp_team *team = thr->ts.team;
 118
 119 #ifdef HAVE_BROKEN_POSIX_SEMAPHORES
 120   /* If pthread_mutex_* is used for omp_*lock*, then each task must be
 121      tied to one thread all the time.  This means UNTIED tasks must be
 122      tied and if CPYFN is non-NULL IF(0) must be forced, as CPYFN
 123      might be running on different thread than FN.  */
 124   if (cpyfn)
 125     if_clause = false;
 126   if (flags & 1)
 127     flags &= ~1;
 128 #endif
 129
 130   /* If parallel or taskgroup has been cancelled, don't start new tasks.  */
 131   if (team
 132       && (gomp_team_barrier_cancelled (&team->barrier)
 133           || (thr->task->taskgroup && thr->task->taskgroup->cancelled)))
 134     return;
 135
 136   if (!if_clause || team == NULL
 137       || (thr->task && thr->task->final_task)
 138       || team->task_count > 64 * team->nthreads)
 139     {
 140       struct gomp_task task;
 141
 142       /* If there are depend clauses and earlier deferred sibling tasks
 143          with depend clauses, check if there isn't a dependency.  If there
 144          is, fall through to the deferred task handling, as we can't
 145          schedule such tasks right away.  There is no need to handle
 146          depend clauses for non-deferred tasks other than this, because
 147          the parent task is suspended until the child task finishes and thus
 148          it can't start further child tasks.  */
 149       if ((flags & 8) && thr->task && thr->task->depend_hash)
 150         {
 151           struct gomp_task *parent = thr->task;
 152           struct gomp_task_depend_entry elem, *ent = NULL;
 153           size_t ndepend = (uintptr_t) depend[0];
 154           size_t nout = (uintptr_t) depend[1];
 155           size_t i;
 156           gomp_mutex_lock (&team->task_lock);
 157           for (i = 0; i < ndepend; i++)
 158             {
 159               elem.addr = depend[i + 2];
 160               ent = htab_find (parent->depend_hash, &elem);
 161               for (; ent; ent = ent->next)
 162                 if (i >= nout && ent->is_in)
 163                   continue;
 164                 else
 165                   break;
 166               if (ent)
 167                 break;
 168             }
 169           gomp_mutex_unlock (&team->task_lock);
 170           if (ent)
 171             goto defer;
 172         }
 173
 174       gomp_init_task (&task, thr->task, gomp_icv (false));
 175       task.kind = GOMP_TASK_IFFALSE;
 176       task.final_task = (thr->task && thr->task->final_task) || (flags & 2);
 177       if (thr->task)
 178         {
 179           task.in_tied_task = thr->task->in_tied_task;
 180           task.taskgroup = thr->task->taskgroup;
 181         }
 182       thr->task = &task;
 183       if (__builtin_expect (cpyfn != NULL, 0))
 184         {
 185           char buf[arg_size + arg_align - 1];
 186           char *arg = (char *) (((uintptr_t) buf + arg_align - 1)
 187                                 & ~(uintptr_t) (arg_align - 1));
 188           cpyfn (arg, data);
 189           fn (arg);
 190         }
 191       else
 192         fn (data);
 193       /* Access to "children" is normally done inside a task_lock
 194          mutex region, but the only way this particular task.children
 195          can be set is if this thread's task work function (fn)
 196          creates children.  So since the setter is *this* thread, we
 197          need no barriers here when testing for non-NULL.  We can have
 198          task.children set by the current thread then changed by a
 199          child thread, but seeing a stale non-NULL value is not a
 200          problem.  Once past the task_lock acquisition, this thread
 201          will see the real value of task.children.  */
 202       if (task.children != NULL)
 203         {
 204           gomp_mutex_lock (&team->task_lock);
 205           gomp_clear_parent (task.children);
 206           gomp_mutex_unlock (&team->task_lock);
 207         }
 208       gomp_end_task ();
 209     }
 210   else
 211     {
 212      defer:;
 213       struct gomp_task *task;
 214       struct gomp_task *parent = thr->task;
 215       struct gomp_taskgroup *taskgroup = parent->taskgroup;
 216       char *arg;
 217       bool do_wake;
 218       size_t depend_size = 0;
 219
 220       if (flags & 8)
 221         depend_size = ((uintptr_t) depend[0]
 222                        * sizeof (struct gomp_task_depend_entry));
 223       task = gomp_malloc (sizeof (*task) + depend_size
 224                           + arg_size + arg_align - 1);
 225       arg = (char *) (((uintptr_t) (task + 1) + depend_size + arg_align - 1)
 226                       & ~(uintptr_t) (arg_align - 1));
 227       gomp_init_task (task, parent, gomp_icv (false));
 228       task->kind = GOMP_TASK_IFFALSE;
 229       task->in_tied_task = parent->in_tied_task;
 230       task->taskgroup = taskgroup;
 231       thr->task = task;
 232       if (cpyfn)
 233         {
 234           cpyfn (arg, data);
 235           task->copy_ctors_done = true;
 236         }
 237       else
 238         memcpy (arg, data, arg_size);
 239       thr->task = parent;
 240       task->kind = GOMP_TASK_WAITING;
 241       task->fn = fn;
 242       task->fn_data = arg;
 243       task->final_task = (flags & 2) >> 1;
 244       gomp_mutex_lock (&team->task_lock);
 245       /* If parallel or taskgroup has been cancelled, don't start new
 246          tasks.  */
 247       if (__builtin_expect ((gomp_team_barrier_cancelled (&team->barrier)
 248                              || (taskgroup && taskgroup->cancelled))
 249                             && !task->copy_ctors_done, 0))
 250         {
 251           gomp_mutex_unlock (&team->task_lock);
 252           gomp_finish_task (task);
 253           free (task);
 254           return;
 255         }
 256       if (taskgroup)
 257         taskgroup->num_children++;
 258       if (depend_size)
 259         {
 260           size_t ndepend = (uintptr_t) depend[0];
 261           size_t nout = (uintptr_t) depend[1];
 262           size_t i;
 263           hash_entry_type ent;
 264
 265           task->depend_count = ndepend;
 266           task->num_dependees = 0;
 267           if (parent->depend_hash == NULL)
 268             parent->depend_hash
 269               = htab_create (2 * ndepend > 12 ? 2 * ndepend : 12);
 270           for (i = 0; i < ndepend; i++)
 271             {
 272               task->depend[i].addr = depend[2 + i];
 273               task->depend[i].next = NULL;
 274               task->depend[i].prev = NULL;
 275               task->depend[i].task = task;
 276               task->depend[i].is_in = i >= nout;
 277               task->depend[i].redundant = false;
 278
 279               hash_entry_type *slot
 280                 = htab_find_slot (&parent->depend_hash, &task->depend[i],
 281                                   INSERT);
 282               hash_entry_type out = NULL;
 283               if (*slot)
 284                 {
 285                   /* If multiple depends on the same task are the
 286                      same, all but the first one are redundant.
 287                      As inout/out come first, if any of them is
 288                      inout/out, it will win, which is the right
 289                      semantics.  */
 290                   if ((*slot)->task == task)
 291                     {
 292                       task->depend[i].redundant = true;
 293                       continue;
 294                     }
 295                   for (ent = *slot; ent; ent = ent->next)
 296                     {
 297                       /* depend(in:...) doesn't depend on earlier
 298                          depend(in:...).  */
 299                       if (i >= nout && ent->is_in)
 300                         continue;
 301
 302                       if (!ent->is_in)
 303                         out = ent;
 304
 305                       struct gomp_task *tsk = ent->task;
 306                       if (tsk->dependers == NULL)
 307                         {
 308                           tsk->dependers
 309                             = gomp_malloc (sizeof (struct gomp_dependers_vec)
 310                                            + 6 * sizeof (struct gomp_task *));
 311                           tsk->dependers->n_elem = 1;
 312                           tsk->dependers->allocated = 6;
 313                           tsk->dependers->elem[0] = task;
 314                           task->num_dependees++;
 315                           continue;
 316                         }
 317                       /* We already have some other dependency on tsk
 318                          from earlier depend clause.  */
 319                       else if (tsk->dependers->n_elem
 320                                && (tsk->dependers->elem[tsk->dependers->n_elem
 321                                                         - 1]
 322                                    == task))
 323                         continue;
 324                       else if (tsk->dependers->n_elem
 325                                == tsk->dependers->allocated)
 326                         {
 327                           tsk->dependers->allocated
 328                             = tsk->dependers->allocated * 2 + 2;
 329                           tsk->dependers
 330                             = gomp_realloc (tsk->dependers,
 331                                             sizeof (struct gomp_dependers_vec)
 332                                             + (tsk->dependers->allocated
 333                                                * sizeof (struct gomp_task *)));
 334                         }
 335                       tsk->dependers->elem[tsk->dependers->n_elem++] = task;
 336                       task->num_dependees++;
 337                     }
 338                   task->depend[i].next = *slot;
 339                   (*slot)->prev = &task->depend[i];
 340                 }
 341               *slot = &task->depend[i];
 342
 343               /* There is no need to store more than one depend({,in}out:)
 344                  task per address in the hash table chain, because each out
 345                  depends on all earlier outs, thus it is enough to record
 346                  just the last depend({,in}out:).  For depend(in:), we need
 347                  to keep all of the previous ones not terminated yet, because
 348                  a later depend({,in}out:) might need to depend on all of
 349                  them.  So, if the new task's clause is depend({,in}out:),
 350                  we know there is at most one other depend({,in}out:) clause
 351                  in the list (out) and to maintain the invariant we now
 352                  need to remove it from the list.  */
 353               if (!task->depend[i].is_in && out)
 354                 {
 355                   if (out->next)
 356                     out->next->prev = out->prev;
 357                   out->prev->next = out->next;
 358                   out->redundant = true;
 359                 }
 360             }
 361           if (task->num_dependees)
 362             {
 363               gomp_mutex_unlock (&team->task_lock);
 364               return;
 365             }
 366         }
 367       if (parent->children)
 368         {
 369           task->next_child = parent->children;
 370           task->prev_child = parent->children->prev_child;
 371           task->next_child->prev_child = task;
 372           task->prev_child->next_child = task;
 373         }
 374       else
 375         {
 376           task->next_child = task;
 377           task->prev_child = task;
 378         }
 379       parent->children = task;
 380       if (taskgroup)
 381         {
 382           if (taskgroup->children)
 383             {
 384               task->next_taskgroup = taskgroup->children;
 385               task->prev_taskgroup = taskgroup->children->prev_taskgroup;
 386               task->next_taskgroup->prev_taskgroup = task;
 387               task->prev_taskgroup->next_taskgroup = task;
 388             }
 389           else
 390             {
 391               task->next_taskgroup = task;
 392               task->prev_taskgroup = task;
 393             }
 394           taskgroup->children = task;
 395         }
 396       if (team->task_queue)
 397         {
 398           task->next_queue = team->task_queue;
 399           task->prev_queue = team->task_queue->prev_queue;
 400           task->next_queue->prev_queue = task;
 401           task->prev_queue->next_queue = task;
 402         }
 403       else
 404         {
 405           task->next_queue = task;
 406           task->prev_queue = task;
 407           team->task_queue = task;
 408         }
 409       ++team->task_count;
 410       ++team->task_queued_count;
 411       gomp_team_barrier_set_task_pending (&team->barrier);
 412       do_wake = team->task_running_count + !parent->in_tied_task
 413                 < team->nthreads;
 414       gomp_mutex_unlock (&team->task_lock);
 415       if (do_wake)
 416         gomp_team_barrier_wake (&team->barrier, 1);
 417     }
 418 }
 419
 420 static inline bool
 421 gomp_task_run_pre (struct gomp_task *child_task, struct gomp_task *parent,
 422                    struct gomp_taskgroup *taskgroup, struct gomp_team *team)
 423 {
 424   if (parent && parent->children == child_task)
 425     parent->children = child_task->next_child;
 426   if (taskgroup && taskgroup->children == child_task)
 427     taskgroup->children = child_task->next_taskgroup;
 428   child_task->prev_queue->next_queue = child_task->next_queue;
 429   child_task->next_queue->prev_queue = child_task->prev_queue;
 430   if (team->task_queue == child_task)
 431     {
 432       if (child_task->next_queue != child_task)
 433         team->task_queue = child_task->next_queue;
 434       else
 435         team->task_queue = NULL;
 436     }
 437   child_task->kind = GOMP_TASK_TIED;
 438   if (--team->task_queued_count == 0)
 439     gomp_team_barrier_clear_task_pending (&team->barrier);
 440   if ((gomp_team_barrier_cancelled (&team->barrier)
 441        || (taskgroup && taskgroup->cancelled))
 442       && !child_task->copy_ctors_done)
 443     return true;
 444   return false;
 445 }
 446
 447 static void
 448 gomp_task_run_post_handle_depend_hash (struct gomp_task *child_task)
 449 {
 450   struct gomp_task *parent = child_task->parent;
 451   size_t i;
 452
 453   for (i = 0; i < child_task->depend_count; i++)
 454     if (!child_task->depend[i].redundant)
 455       {
 456         if (child_task->depend[i].next)
 457           child_task->depend[i].next->prev = child_task->depend[i].prev;
 458         if (child_task->depend[i].prev)
 459           child_task->depend[i].prev->next = child_task->depend[i].next;
 460         else
 461           {
 462             hash_entry_type *slot
 463               = htab_find_slot (&parent->depend_hash, &child_task->depend[i],
 464                                 NO_INSERT);
 465             if (*slot != &child_task->depend[i])
 466               abort ();
 467             if (child_task->depend[i].next)
 468               *slot = child_task->depend[i].next;
 469             else
 470               htab_clear_slot (parent->depend_hash, slot);
 471           }
 472       }
 473 }
 474
 475 static size_t
 476 gomp_task_run_post_handle_dependers (struct gomp_task *child_task,
 477                                      struct gomp_team *team)
 478 {
 479   struct gomp_task *parent = child_task->parent;
 480   size_t i, count = child_task->dependers->n_elem, ret = 0;
 481   for (i = 0; i < count; i++)
 482     {
 483       struct gomp_task *task = child_task->dependers->elem[i];
 484       if (--task->num_dependees != 0)
 485         continue;
 486
 487       struct gomp_taskgroup *taskgroup = task->taskgroup;
 488       if (parent)
 489         {
 490           if (parent->children)
 491             {
 492               task->next_child = parent->children;
 493               task->prev_child = parent->children->prev_child;
 494               task->next_child->prev_child = task;
 495               task->prev_child->next_child = task;
 496             }
 497           else
 498             {
 499               task->next_child = task;
 500               task->prev_child = task;
 501             }
 502           parent->children = task;
 503           if (parent->in_taskwait)
 504             {
 505               parent->in_taskwait = false;
 506               gomp_sem_post (&parent->taskwait_sem);
 507             }
 508         }
 509       if (taskgroup)
 510         {
 511           if (taskgroup->children)
 512             {
 513               task->next_taskgroup = taskgroup->children;
 514               task->prev_taskgroup = taskgroup->children->prev_taskgroup;
 515               task->next_taskgroup->prev_taskgroup = task;
 516               task->prev_taskgroup->next_taskgroup = task;
 517             }
 518           else
 519             {
 520               task->next_taskgroup = task;
 521               task->prev_taskgroup = task;
 522             }
 523           taskgroup->children = task;
 524           if (taskgroup->in_taskgroup_wait)
 525             {
 526               taskgroup->in_taskgroup_wait = false;
 527               gomp_sem_post (&taskgroup->taskgroup_sem);
 528             }
 529         }
 530       if (team->task_queue)
 531         {
 532           task->next_queue = team->task_queue;
 533           task->prev_queue = team->task_queue->prev_queue;
 534           task->next_queue->prev_queue = task;
 535           task->prev_queue->next_queue = task;
 536         }
 537       else
 538         {
 539           task->next_queue = task;
 540           task->prev_queue = task;
 541           team->task_queue = task;
 542         }
 543       ++team->task_count;
 544       ++team->task_queued_count;
 545       ++ret;
 546     }
 547   free (child_task->dependers);
 548   child_task->dependers = NULL;
 549   if (ret > 1)
 550     gomp_team_barrier_set_task_pending (&team->barrier);
 551   return ret;
 552 }
 553
 554 static inline size_t
 555 gomp_task_run_post_handle_depend (struct gomp_task *child_task,
 556                                   struct gomp_team *team)
 557 {
 558   if (child_task->depend_count == 0)
 559     return 0;
 560
 561   /* If parent is gone already, the hash table is freed and nothing
 562      will use the hash table anymore, no need to remove anything from it.  */
 563   if (child_task->parent != NULL)
 564     gomp_task_run_post_handle_depend_hash (child_task);
 565
 566   if (child_task->dependers == NULL)
 567     return 0;
 568
 569   return gomp_task_run_post_handle_dependers (child_task, team);
 570 }
 571
 572 static inline void
 573 gomp_task_run_post_remove_parent (struct gomp_task *child_task)
 574 {
 575   struct gomp_task *parent = child_task->parent;
 576   if (parent == NULL)
 577     return;
 578   child_task->prev_child->next_child = child_task->next_child;
 579   child_task->next_child->prev_child = child_task->prev_child;
 580   if (parent->children != child_task)
 581     return;
 582   if (child_task->next_child != child_task)
 583     parent->children = child_task->next_child;
 584   else
 585     {
 586       /* We access task->children in GOMP_taskwait
 587          outside of the task lock mutex region, so
 588          need a release barrier here to ensure memory
 589          written by child_task->fn above is flushed
 590          before the NULL is written.  */
 591       __atomic_store_n (&parent->children, NULL, MEMMODEL_RELEASE);
 592       if (parent->in_taskwait)
 593         {
 594           parent->in_taskwait = false;
 595           gomp_sem_post (&parent->taskwait_sem);
 596         }
 597     }
 598 }
 599
 600 static inline void
 601 gomp_task_run_post_remove_taskgroup (struct gomp_task *child_task)
 602 {
 603   struct gomp_taskgroup *taskgroup = child_task->taskgroup;
 604   if (taskgroup == NULL)
 605     return;
 606   child_task->prev_taskgroup->next_taskgroup = child_task->next_taskgroup;
 607   child_task->next_taskgroup->prev_taskgroup = child_task->prev_taskgroup;
 608   if (taskgroup->num_children > 1)
 609     --taskgroup->num_children;
 610   else
 611     {
 612       /* We access taskgroup->num_children in GOMP_taskgroup_end
 613          outside of the task lock mutex region, so
 614          need a release barrier here to ensure memory
 615          written by child_task->fn above is flushed
 616          before the NULL is written.  */
 617       __atomic_store_n (&taskgroup->num_children, 0, MEMMODEL_RELEASE);
 618     }
 619   if (taskgroup->children != child_task)
 620     return;
 621   if (child_task->next_taskgroup != child_task)
 622     taskgroup->children = child_task->next_taskgroup;
 623   else
 624     {
 625       taskgroup->children = NULL;
 626       if (taskgroup->in_taskgroup_wait)
 627         {
 628           taskgroup->in_taskgroup_wait = false;
 629           gomp_sem_post (&taskgroup->taskgroup_sem);
 630         }
 631     }
 632 }
 633
 634 void
 635 gomp_barrier_handle_tasks (gomp_barrier_state_t state)
 636 {
 637   struct gomp_thread *thr = gomp_thread ();
 638   struct gomp_team *team = thr->ts.team;
 639   struct gomp_task *task = thr->task;
 640   struct gomp_task *child_task = NULL;
 641   struct gomp_task *to_free = NULL;
 642   int do_wake = 0;
 643
 644   gomp_mutex_lock (&team->task_lock);
 645   if (gomp_barrier_last_thread (state))
 646     {
 647       if (team->task_count == 0)
 648         {
 649           gomp_team_barrier_done (&team->barrier, state);
 650           gomp_mutex_unlock (&team->task_lock);
 651           gomp_team_barrier_wake (&team->barrier, 0);
 652           return;
 653         }
 654       gomp_team_barrier_set_waiting_for_tasks (&team->barrier);
 655     }
 656
 657   while (1)
 658     {
 659       bool cancelled = false;
 660       if (team->task_queue != NULL)
 661         {
 662           child_task = team->task_queue;
 663           cancelled = gomp_task_run_pre (child_task, child_task->parent,
 664                                          child_task->taskgroup, team);
 665           if (__builtin_expect (cancelled, 0))
 666             {
 667               if (to_free)
 668                 {
 669                   gomp_finish_task (to_free);
 670                   free (to_free);
 671                   to_free = NULL;
 672                 }
 673               goto finish_cancelled;
 674             }
 675           team->task_running_count++;
 676           child_task->in_tied_task = true;
 677         }
 678       gomp_mutex_unlock (&team->task_lock);
 679       if (do_wake)
 680         {
 681           gomp_team_barrier_wake (&team->barrier, do_wake);
 682           do_wake = 0;
 683         }
 684       if (to_free)
 685         {
 686           gomp_finish_task (to_free);
 687           free (to_free);
 688           to_free = NULL;
 689         }
 690       if (child_task)
 691         {
 692           thr->task = child_task;
 693           child_task->fn (child_task->fn_data);
 694           thr->task = task;
 695         }
 696       else
 697         return;
 698       gomp_mutex_lock (&team->task_lock);
 699       if (child_task)
 700         {
 701          finish_cancelled:;
 702           size_t new_tasks
 703             = gomp_task_run_post_handle_depend (child_task, team);
 704           gomp_task_run_post_remove_parent (child_task);
 705           gomp_clear_parent (child_task->children);
 706           gomp_task_run_post_remove_taskgroup (child_task);
 707           to_free = child_task;
 708           child_task = NULL;
 709           if (!cancelled)
 710             team->task_running_count--;
 711           if (new_tasks > 1)
 712             {
 713               do_wake = team->nthreads - team->task_running_count;
 714               if (do_wake > new_tasks)
 715                 do_wake = new_tasks;
 716             }
 717           if (--team->task_count == 0
 718               && gomp_team_barrier_waiting_for_tasks (&team->barrier))
 719             {
 720               gomp_team_barrier_done (&team->barrier, state);
 721               gomp_mutex_unlock (&team->task_lock);
 722               gomp_team_barrier_wake (&team->barrier, 0);
 723               gomp_mutex_lock (&team->task_lock);
 724             }
 725         }
 726     }
 727 }
 728
 729 /* Called when encountering a taskwait directive.  */
 730
 731 void
 732 GOMP_taskwait (void)
 733 {
 734   struct gomp_thread *thr = gomp_thread ();
 735   struct gomp_team *team = thr->ts.team;
 736   struct gomp_task *task = thr->task;
 737   struct gomp_task *child_task = NULL;
 738   struct gomp_task *to_free = NULL;
 739   int do_wake = 0;
 740
 741   /* The acquire barrier on load of task->children here synchronizes
 742      with the write of a NULL in gomp_task_run_post_remove_parent.  It is
 743      not necessary that we synchronize with other non-NULL writes at
 744      this point, but we must ensure that all writes to memory by a
 745      child thread task work function are seen before we exit from
 746      GOMP_taskwait.  */
 747   if (task == NULL
 748       || __atomic_load_n (&task->children, MEMMODEL_ACQUIRE) == NULL)
 749     return;
 750
 751   gomp_mutex_lock (&team->task_lock);
 752   while (1)
 753     {
 754       bool cancelled = false;
 755       if (task->children == NULL)
 756         {
 757           gomp_mutex_unlock (&team->task_lock);
 758           if (to_free)
 759             {
 760               gomp_finish_task (to_free);
 761               free (to_free);
 762             }
 763           return;
 764         }
 765       if (task->children->kind == GOMP_TASK_WAITING)
 766         {
 767           child_task = task->children;
 768           cancelled
 769             = gomp_task_run_pre (child_task, task, child_task->taskgroup,
 770                                  team);
 771           if (__builtin_expect (cancelled, 0))
 772             {
 773               if (to_free)
 774                 {
 775                   gomp_finish_task (to_free);
 776                   free (to_free);
 777                   to_free = NULL;
 778                 }
 779               goto finish_cancelled;
 780             }
 781         }
 782       else
 783         /* All tasks we are waiting for are already running
 784            in other threads.  Wait for them.  */
 785         task->in_taskwait = true;
 786       gomp_mutex_unlock (&team->task_lock);
 787       if (do_wake)
 788         {
 789           gomp_team_barrier_wake (&team->barrier, do_wake);
 790           do_wake = 0;
 791         }
 792       if (to_free)
 793         {
 794           gomp_finish_task (to_free);
 795           free (to_free);
 796           to_free = NULL;
 797         }
 798       if (child_task)
 799         {
 800           thr->task = child_task;
 801           child_task->fn (child_task->fn_data);
 802           thr->task = task;
 803         }
 804       else
 805         gomp_sem_wait (&task->taskwait_sem);
 806       gomp_mutex_lock (&team->task_lock);
 807       if (child_task)
 808         {
 809          finish_cancelled:;
 810           size_t new_tasks
 811             = gomp_task_run_post_handle_depend (child_task, team);
 812           child_task->prev_child->next_child = child_task->next_child;
 813           child_task->next_child->prev_child = child_task->prev_child;
 814           if (task->children == child_task)
 815             {
 816               if (child_task->next_child != child_task)
 817                 task->children = child_task->next_child;
 818               else
 819                 task->children = NULL;
 820             }
 821           gomp_clear_parent (child_task->children);
 822           gomp_task_run_post_remove_taskgroup (child_task);
 823           to_free = child_task;
 824           child_task = NULL;
 825           team->task_count--;
 826           if (new_tasks > 1)
 827             {
 828               do_wake = team->nthreads - team->task_running_count
 829                         - !task->in_tied_task;
 830               if (do_wake > new_tasks)
 831                 do_wake = new_tasks;
 832             }
 833         }
 834     }
 835 }
 836
 837 /* Called when encountering a taskyield directive.  */
 838
 839 void
 840 GOMP_taskyield (void)
 841 {
 842   /* Nothing at the moment.  */
 843 }
 844
 845 void
 846 GOMP_taskgroup_start (void)
 847 {
 848   struct gomp_thread *thr = gomp_thread ();
 849   struct gomp_team *team = thr->ts.team;
 850   struct gomp_task *task = thr->task;
 851   struct gomp_taskgroup *taskgroup;
 852
 853   /* If team is NULL, all tasks are executed as
 854      GOMP_TASK_IFFALSE tasks and thus all children tasks of
 855      taskgroup and their descendant tasks will be finished
 856      by the time GOMP_taskgroup_end is called.  */
 857   if (team == NULL)
 858     return;
 859   taskgroup = gomp_malloc (sizeof (struct gomp_taskgroup));
 860   taskgroup->prev = task->taskgroup;
 861   taskgroup->children = NULL;
 862   taskgroup->in_taskgroup_wait = false;
 863   taskgroup->cancelled = false;
 864   taskgroup->num_children = 0;
 865   gomp_sem_init (&taskgroup->taskgroup_sem, 0);
 866   task->taskgroup = taskgroup;
 867 }
 868
 869 void
 870 GOMP_taskgroup_end (void)
 871 {
 872   struct gomp_thread *thr = gomp_thread ();
 873   struct gomp_team *team = thr->ts.team;
 874   struct gomp_task *task = thr->task;
 875   struct gomp_taskgroup *taskgroup;
 876   struct gomp_task *child_task = NULL;
 877   struct gomp_task *to_free = NULL;
 878   int do_wake = 0;
 879
 880   if (team == NULL)
 881     return;
 882   taskgroup = task->taskgroup;
 883
 884   /* The acquire barrier on load of taskgroup->num_children here
 885      synchronizes with the write of 0 in gomp_task_run_post_remove_taskgroup.
 886      It is not necessary that we synchronize with other non-0 writes at
 887      this point, but we must ensure that all writes to memory by a
 888      child thread task work function are seen before we exit from
 889      GOMP_taskgroup_end.  */
 890   if (__atomic_load_n (&taskgroup->num_children, MEMMODEL_ACQUIRE) == 0)
 891     goto finish;
 892
 893   gomp_mutex_lock (&team->task_lock);
 894   while (1)
 895     {
 896       bool cancelled = false;
 897       if (taskgroup->children == NULL)
 898         {
 899           if (taskgroup->num_children)
 900             goto do_wait;
 901           gomp_mutex_unlock (&team->task_lock);
 902           if (to_free)
 903             {
 904               gomp_finish_task (to_free);
 905               free (to_free);
 906             }
 907           goto finish;
 908         }
 909       if (taskgroup->children->kind == GOMP_TASK_WAITING)
 910         {
 911           child_task = taskgroup->children;
 912           cancelled
 913             = gomp_task_run_pre (child_task, child_task->parent, taskgroup,
 914                                  team);
 915           if (__builtin_expect (cancelled, 0))
 916             {
 917               if (to_free)
 918                 {
 919                   gomp_finish_task (to_free);
 920                   free (to_free);
 921                   to_free = NULL;
 922                 }
 923               goto finish_cancelled;
 924             }
 925         }
 926       else
 927         {
 928          do_wait:
 929           /* All tasks we are waiting for are already running
 930              in other threads.  Wait for them.  */
 931           taskgroup->in_taskgroup_wait = true;
 932         }
 933       gomp_mutex_unlock (&team->task_lock);
 934       if (do_wake)
 935         {
 936           gomp_team_barrier_wake (&team->barrier, do_wake);
 937           do_wake = 0;
 938         }
 939       if (to_free)
 940         {
 941           gomp_finish_task (to_free);
 942           free (to_free);
 943           to_free = NULL;
 944         }
 945       if (child_task)
 946         {
 947           thr->task = child_task;
 948           child_task->fn (child_task->fn_data);
 949           thr->task = task;
 950         }
 951       else
 952         gomp_sem_wait (&taskgroup->taskgroup_sem);
 953       gomp_mutex_lock (&team->task_lock);
 954       if (child_task)
 955         {
 956          finish_cancelled:;
 957           size_t new_tasks
 958             = gomp_task_run_post_handle_depend (child_task, team);
 959           child_task->prev_taskgroup->next_taskgroup
 960             = child_task->next_taskgroup;
 961           child_task->next_taskgroup->prev_taskgroup
 962             = child_task->prev_taskgroup;
 963           --taskgroup->num_children;
 964           if (taskgroup->children == child_task)
 965             {
 966               if (child_task->next_taskgroup != child_task)
 967                 taskgroup->children = child_task->next_taskgroup;
 968               else
 969                 taskgroup->children = NULL;
 970             }
 971           gomp_task_run_post_remove_parent (child_task);
 972           gomp_clear_parent (child_task->children);
 973           to_free = child_task;
 974           child_task = NULL;
 975           team->task_count--;
 976           if (new_tasks > 1)
 977             {
 978               do_wake = team->nthreads - team->task_running_count
 979                         - !task->in_tied_task;
 980               if (do_wake > new_tasks)
 981                 do_wake = new_tasks;
 982             }
 983         }
 984     }
 985
 986  finish:
 987   task->taskgroup = taskgroup->prev;
 988   gomp_sem_destroy (&taskgroup->taskgroup_sem);
 989   free (taskgroup);
 990 }
 991
 992 int
 993 omp_in_final (void)
 994 {
 995   struct gomp_thread *thr = gomp_thread ();
 996   return thr->task && thr->task->final_task;
 997 }
 998
 999 ialias (omp_in_final)