1 files changed, 533 insertions, 148 deletions

diff --git a/libgomp/task.c b/libgomp/task.c
index 74920d5ddb8..1246c6ae318 100644
--- a/libgomp/task.c
+++ b/libgomp/task.c
@@ -29,6 +29,7 @@
 #include "libgomp.h"
 #include <stdlib.h>
 #include <string.h>
+#include "gomp-constants.h"
 
 typedef struct gomp_task_depend_entry *hash_entry_type;
 
@@ -91,6 +92,8 @@ gomp_end_task (void)
   thr->task = task->parent;
 }
 
+/* Orphan the task in CHILDREN and all its siblings.  */
+
 static inline void
 gomp_clear_parent (struct gomp_task *children)
 {
@@ -105,16 +108,136 @@ gomp_clear_parent (struct gomp_task *children)
     while (task != children);
 }
 
-static void gomp_task_maybe_wait_for_dependencies (void **depend);
+/* Helper function for GOMP_task and gomp_create_target_task.  Depend clause
+   handling for undeferred task creation.  */
+
+static void
+gomp_task_handle_depend (struct gomp_task *task, struct gomp_task *parent,
+			 void **depend)
+{
+  size_t ndepend = (uintptr_t) depend[0];
+  size_t nout = (uintptr_t) depend[1];
+  size_t i;
+  hash_entry_type ent;
+
+  task->depend_count = ndepend;
+  task->num_dependees = 0;
+  if (parent->depend_hash == NULL)
+    parent->depend_hash = htab_create (2 * ndepend > 12 ? 2 * ndepend : 12);
+  for (i = 0; i < ndepend; i++)
+    {
+      task->depend[i].addr = depend[2 + i];
+      task->depend[i].next = NULL;
+      task->depend[i].prev = NULL;
+      task->depend[i].task = task;
+      task->depend[i].is_in = i >= nout;
+      task->depend[i].redundant = false;
+      task->depend[i].redundant_out = false;
+
+      hash_entry_type *slot = htab_find_slot (&parent->depend_hash,
+					      &task->depend[i], INSERT);
+      hash_entry_type out = NULL, last = NULL;
+      if (*slot)
+	{
+	  /* If multiple depends on the same task are the same, all but the
+	     first one are redundant.  As inout/out come first, if any of them
+	     is inout/out, it will win, which is the right semantics.  */
+	  if ((*slot)->task == task)
+	    {
+	      task->depend[i].redundant = true;
+	      continue;
+	    }
+	  for (ent = *slot; ent; ent = ent->next)
+	    {
+	      if (ent->redundant_out)
+		break;
+
+	      last = ent;
+
+	      /* depend(in:...) doesn't depend on earlier depend(in:...).  */
+	      if (i >= nout && ent->is_in)
+		continue;
+
+	      if (!ent->is_in)
+		out = ent;
+
+	      struct gomp_task *tsk = ent->task;
+	      if (tsk->dependers == NULL)
+		{
+		  tsk->dependers
+		    = gomp_malloc (sizeof (struct gomp_dependers_vec)
+				   + 6 * sizeof (struct gomp_task *));
+		  tsk->dependers->n_elem = 1;
+		  tsk->dependers->allocated = 6;
+		  tsk->dependers->elem[0] = task;
+		  task->num_dependees++;
+		  continue;
+		}
+	      /* We already have some other dependency on tsk from earlier
+		 depend clause.  */
+	      else if (tsk->dependers->n_elem
+		       && (tsk->dependers->elem[tsk->dependers->n_elem - 1]
+			   == task))
+		continue;
+	      else if (tsk->dependers->n_elem == tsk->dependers->allocated)
+		{
+		  tsk->dependers->allocated
+		    = tsk->dependers->allocated * 2 + 2;
+		  tsk->dependers
+		    = gomp_realloc (tsk->dependers,
+				    sizeof (struct gomp_dependers_vec)
+				    + (tsk->dependers->allocated
+				       * sizeof (struct gomp_task *)));
+		}
+	      tsk->dependers->elem[tsk->dependers->n_elem++] = task;
+	      task->num_dependees++;
+	    }
+	  task->depend[i].next = *slot;
+	  (*slot)->prev = &task->depend[i];
+	}
+      *slot = &task->depend[i];
+
+      /* There is no need to store more than one depend({,in}out:) task per
+	 address in the hash table chain for the purpose of creation of
+	 deferred tasks, because each out depends on all earlier outs, thus it
+	 is enough to record just the last depend({,in}out:).  For depend(in:),
+	 we need to keep all of the previous ones not terminated yet, because
+	 a later depend({,in}out:) might need to depend on all of them.  So, if
+	 the new task's clause is depend({,in}out:), we know there is at most
+	 one other depend({,in}out:) clause in the list (out).  For
+	 non-deferred tasks we want to see all outs, so they are moved to the
+	 end of the chain, after first redundant_out entry all following
+	 entries should be redundant_out.  */
+      if (!task->depend[i].is_in && out)
+	{
+	  if (out != last)
+	    {
+	      out->next->prev = out->prev;
+	      out->prev->next = out->next;
+	      out->next = last->next;
+	      out->prev = last;
+	      last->next = out;
+	      if (out->next)
+		out->next->prev = out;
+	    }
+	  out->redundant_out = true;
+	}
+    }
+}
 
 /* Called when encountering an explicit task directive.  If IF_CLAUSE is
    false, then we must not delay in executing the task.  If UNTIED is true,
-   then the task may be executed by any member of the team.  */
+   then the task may be executed by any member of the team.
+
+   DEPEND is an array containing:
+	depend[0]: number of depend elements.
+	depend[1]: number of depend elements of type "out".
+	depend[2..N+1]: address of [1..N]th depend element.  */
 
 void
 GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
 	   long arg_size, long arg_align, bool if_clause, unsigned flags,
-	   void **depend)
+	   void **depend, int priority)
 {
   struct gomp_thread *thr = gomp_thread ();
   struct gomp_team *team = thr->ts.team;
@@ -126,8 +249,7 @@ GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
      might be running on different thread than FN.  */
   if (cpyfn)
     if_clause = false;
-  if (flags & 1)
-    flags &= ~1;
+  flags &= ~GOMP_TASK_FLAG_UNTIED;
 #endif
 
   /* If parallel or taskgroup has been cancelled, don't start new tasks.  */
@@ -136,6 +258,11 @@ GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
 	  || (thr->task->taskgroup && thr->task->taskgroup->cancelled)))
     return;
 
+  if ((flags & GOMP_TASK_FLAG_PRIORITY) == 0)
+    priority = 0;
+  /* FIXME, use priority.  */
+  (void) priority;
+
   if (!if_clause || team == NULL
       || (thr->task && thr->task->final_task)
       || team->task_count > 64 * team->nthreads)
@@ -148,12 +275,14 @@ GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
 	 depend clauses for non-deferred tasks other than this, because
 	 the parent task is suspended until the child task finishes and thus
 	 it can't start further child tasks.  */
-      if ((flags & 8) && thr->task && thr->task->depend_hash)
+      if ((flags & GOMP_TASK_FLAG_DEPEND)
+	  && thr->task && thr->task->depend_hash)
 	gomp_task_maybe_wait_for_dependencies (depend);
 
       gomp_init_task (&task, thr->task, gomp_icv (false));
-      task.kind = GOMP_TASK_IFFALSE;
-      task.final_task = (thr->task && thr->task->final_task) || (flags & 2);
+      task.kind = GOMP_TASK_UNDEFERRED;
+      task.final_task = (thr->task && thr->task->final_task)
+			|| (flags & GOMP_TASK_FLAG_FINAL);
       if (thr->task)
 	{
 	  task.in_tied_task = thr->task->in_tied_task;
@@ -196,7 +325,7 @@ GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
       bool do_wake;
       size_t depend_size = 0;
 
-      if (flags & 8)
+      if (flags & GOMP_TASK_FLAG_DEPEND)
 	depend_size = ((uintptr_t) depend[0]
 		       * sizeof (struct gomp_task_depend_entry));
       task = gomp_malloc (sizeof (*task) + depend_size
@@ -204,7 +333,7 @@ GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
       arg = (char *) (((uintptr_t) (task + 1) + depend_size + arg_align - 1)
 		      & ~(uintptr_t) (arg_align - 1));
       gomp_init_task (task, parent, gomp_icv (false));
-      task->kind = GOMP_TASK_IFFALSE;
+      task->kind = GOMP_TASK_UNDEFERRED;
       task->in_tied_task = parent->in_tied_task;
       task->taskgroup = taskgroup;
       thr->task = task;
@@ -219,7 +348,7 @@ GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
       task->kind = GOMP_TASK_WAITING;
       task->fn = fn;
       task->fn_data = arg;
-      task->final_task = (flags & 2) >> 1;
+      task->final_task = (flags & GOMP_TASK_FLAG_FINAL) >> 1;
       gomp_mutex_lock (&team->task_lock);
       /* If parallel or taskgroup has been cancelled, don't start new
 	 tasks.  */
@@ -236,123 +365,7 @@ GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
 	taskgroup->num_children++;
       if (depend_size)
 	{
-	  size_t ndepend = (uintptr_t) depend[0];
-	  size_t nout = (uintptr_t) depend[1];
-	  size_t i;
-	  hash_entry_type ent;
-
-	  task->depend_count = ndepend;
-	  task->num_dependees = 0;
-	  if (parent->depend_hash == NULL)
-	    parent->depend_hash
-	      = htab_create (2 * ndepend > 12 ? 2 * ndepend : 12);
-	  for (i = 0; i < ndepend; i++)
-	    {
-	      task->depend[i].addr = depend[2 + i];
-	      task->depend[i].next = NULL;
-	      task->depend[i].prev = NULL;
-	      task->depend[i].task = task;
-	      task->depend[i].is_in = i >= nout;
-	      task->depend[i].redundant = false;
-	      task->depend[i].redundant_out = false;
-
-	      hash_entry_type *slot
-		= htab_find_slot (&parent->depend_hash, &task->depend[i],
-				  INSERT);
-	      hash_entry_type out = NULL, last = NULL;
-	      if (*slot)
-		{
-		  /* If multiple depends on the same task are the
-		     same, all but the first one are redundant.
-		     As inout/out come first, if any of them is
-		     inout/out, it will win, which is the right
-		     semantics.  */
-		  if ((*slot)->task == task)
-		    {
-		      task->depend[i].redundant = true;
-		      continue;
-		    }
-		  for (ent = *slot; ent; ent = ent->next)
-		    {
-		      if (ent->redundant_out)
-			break;
-
-		      last = ent;
-
-		      /* depend(in:...) doesn't depend on earlier
-			 depend(in:...).  */
-		      if (i >= nout && ent->is_in)
-			continue;
-
-		      if (!ent->is_in)
-			out = ent;
-
-		      struct gomp_task *tsk = ent->task;
-		      if (tsk->dependers == NULL)
-			{
-			  tsk->dependers
-			    = gomp_malloc (sizeof (struct gomp_dependers_vec)
-					   + 6 * sizeof (struct gomp_task *));
-			  tsk->dependers->n_elem = 1;
-			  tsk->dependers->allocated = 6;
-			  tsk->dependers->elem[0] = task;
-			  task->num_dependees++;
-			  continue;
-			}
-		      /* We already have some other dependency on tsk
-			 from earlier depend clause.  */
-		      else if (tsk->dependers->n_elem
-			       && (tsk->dependers->elem[tsk->dependers->n_elem
-							- 1]
-				   == task))
-			continue;
-		      else if (tsk->dependers->n_elem
-			       == tsk->dependers->allocated)
-			{
-			  tsk->dependers->allocated
-			    = tsk->dependers->allocated * 2 + 2;
-			  tsk->dependers
-			    = gomp_realloc (tsk->dependers,
-					    sizeof (struct gomp_dependers_vec)
-					    + (tsk->dependers->allocated
-					       * sizeof (struct gomp_task *)));
-			}
-		      tsk->dependers->elem[tsk->dependers->n_elem++] = task;
-		      task->num_dependees++;
-		    }
-		  task->depend[i].next = *slot;
-		  (*slot)->prev = &task->depend[i];
-		}
-	      *slot = &task->depend[i];
-
-	      /* There is no need to store more than one depend({,in}out:)
-		 task per address in the hash table chain for the purpose
-		 of creation of deferred tasks, because each out
-		 depends on all earlier outs, thus it is enough to record
-		 just the last depend({,in}out:).  For depend(in:), we need
-		 to keep all of the previous ones not terminated yet, because
-		 a later depend({,in}out:) might need to depend on all of
-		 them.  So, if the new task's clause is depend({,in}out:),
-		 we know there is at most one other depend({,in}out:) clause
-		 in the list (out).  For non-deferred tasks we want to see
-		 all outs, so they are moved to the end of the chain,
-		 after first redundant_out entry all following entries
-		 should be redundant_out.  */
-	      if (!task->depend[i].is_in && out)
-		{
-		  if (out != last)
-		    {
-		      out->next->prev = out->prev;
-		      out->prev->next = out->next;
-		      out->next = last->next;
-		      out->prev = last;
-		      last->next = out;
-		      if (out->next)
-			out->next->prev = out;
-		    }
-		  out->redundant_out = true;
-		}
-	    }
+	  gomp_task_handle_depend (task, parent, depend);
 	  if (task->num_dependees)
 	    {
 	      gomp_mutex_unlock (&team->task_lock);
@@ -374,6 +387,7 @@ GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
       parent->children = task;
       if (taskgroup)
 	{
+	  /* If applicable, place task into its taskgroup.  */
 	  if (taskgroup->children)
 	    {
 	      task->next_taskgroup = taskgroup->children;
@@ -412,26 +426,340 @@ GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
     }
 }
 
+ialias (GOMP_taskgroup_start)
+ialias (GOMP_taskgroup_end)
+
+#define TYPE long
+#define UTYPE unsigned long
+#define TYPE_is_long 1
+#include "taskloop.c"
+#undef TYPE
+#undef UTYPE
+#undef TYPE_is_long
+
+#define TYPE unsigned long long
+#define UTYPE TYPE
+#define GOMP_taskloop GOMP_taskloop_ull
+#include "taskloop.c"
+#undef TYPE
+#undef UTYPE
+#undef GOMP_taskloop
+
+/* Called for nowait target tasks.  */
+
+void
+gomp_create_target_task (struct gomp_device_descr *devicep,
+			 void (*fn) (void *), size_t mapnum, void **hostaddrs,
+			 size_t *sizes, unsigned short *kinds,
+			 unsigned int flags, void **depend)
+{
+  struct gomp_thread *thr = gomp_thread ();
+  struct gomp_team *team = thr->ts.team;
+
+  /* If parallel or taskgroup has been cancelled, don't start new tasks.  */
+  if (team
+      && (gomp_team_barrier_cancelled (&team->barrier)
+	  || (thr->task->taskgroup && thr->task->taskgroup->cancelled)))
+    return;
+
+  struct gomp_target_task *ttask;
+  struct gomp_task *task;
+  struct gomp_task *parent = thr->task;
+  struct gomp_taskgroup *taskgroup = parent->taskgroup;
+  bool do_wake;
+  size_t depend_size = 0;
+
+  if (depend != NULL)
+    depend_size = ((uintptr_t) depend[0]
+		   * sizeof (struct gomp_task_depend_entry));
+  task = gomp_malloc (sizeof (*task) + depend_size
+		      + sizeof (*ttask)
+		      + mapnum * (sizeof (void *) + sizeof (size_t)
+				  + sizeof (unsigned short)));
+  gomp_init_task (task, parent, gomp_icv (false));
+  task->kind = GOMP_TASK_WAITING;
+  task->in_tied_task = parent->in_tied_task;
+  task->taskgroup = taskgroup;
+  ttask = (struct gomp_target_task *) &task->depend[(uintptr_t) depend[0]];
+  ttask->devicep = devicep;
+  ttask->fn = fn;
+  ttask->mapnum = mapnum;
+  memcpy (ttask->hostaddrs, hostaddrs, mapnum * sizeof (void *));
+  ttask->sizes = (size_t *) &ttask->hostaddrs[mapnum];
+  memcpy (ttask->sizes, sizes, mapnum * sizeof (size_t));
+  ttask->kinds = (unsigned short *) &ttask->sizes[mapnum];
+  memcpy (ttask->kinds, kinds, mapnum * sizeof (unsigned short));
+  ttask->flags = flags;
+  task->fn = gomp_target_task_fn;
+  task->fn_data = ttask;
+  task->final_task = 0;
+  gomp_mutex_lock (&team->task_lock);
+  /* If parallel or taskgroup has been cancelled, don't start new tasks.  */
+  if (__builtin_expect (gomp_team_barrier_cancelled (&team->barrier)
+			|| (taskgroup && taskgroup->cancelled), 0))
+    {
+      gomp_mutex_unlock (&team->task_lock);
+      gomp_finish_task (task);
+      free (task);
+      return;
+    }
+  if (taskgroup)
+    taskgroup->num_children++;
+  if (depend_size)
+    {
+      gomp_task_handle_depend (task, parent, depend);
+      if (task->num_dependees)
+	{
+	  gomp_mutex_unlock (&team->task_lock);
+	  return;
+	}
+    }
+  if (parent->children)
+    {
+      task->next_child = parent->children;
+      task->prev_child = parent->children->prev_child;
+      task->next_child->prev_child = task;
+      task->prev_child->next_child = task;
+    }
+  else
+    {
+      task->next_child = task;
+      task->prev_child = task;
+    }
+  parent->children = task;
+  if (taskgroup)
+    {
+      /* If applicable, place task into its taskgroup.  */
+      if (taskgroup->children)
+	{
+	  task->next_taskgroup = taskgroup->children;
+	  task->prev_taskgroup = taskgroup->children->prev_taskgroup;
+	  task->next_taskgroup->prev_taskgroup = task;
+	  task->prev_taskgroup->next_taskgroup = task;
+	}
+      else
+	{
+	  task->next_taskgroup = task;
+	  task->prev_taskgroup = task;
+	}
+      taskgroup->children = task;
+    }
+  if (team->task_queue)
+    {
+      task->next_queue = team->task_queue;
+      task->prev_queue = team->task_queue->prev_queue;
+      task->next_queue->prev_queue = task;
+      task->prev_queue->next_queue = task;
+    }
+  else
+    {
+      task->next_queue = task;
+      task->prev_queue = task;
+      team->task_queue = task;
+    }
+  ++team->task_count;
+  ++team->task_queued_count;
+  gomp_team_barrier_set_task_pending (&team->barrier);
+  do_wake = team->task_running_count + !parent->in_tied_task
+	    < team->nthreads;
+  gomp_mutex_unlock (&team->task_lock);
+  if (do_wake)
+    gomp_team_barrier_wake (&team->barrier, 1);
+}
+
+#if _LIBGOMP_CHECKING
+/* Sanity check TASK to make sure it is in its parent's children
+   queue, and that the tasks therein are in the right order.
+
+   The expected order is:
+	parent_depends_on WAITING tasks
+	!parent_depends_on WAITING tasks
+	TIED tasks
+
+   PARENT is the alleged parent of TASK.  */
+
+static void
+verify_children_queue (struct gomp_task *task, struct gomp_task *parent)
+{
+  if (task->parent != parent)
+    gomp_fatal ("verify_children_queue: incompatible parents");
+  /* It's OK, Annie was an orphan and she turned out all right.  */
+  if (!parent)
+    return;
+
+  bool seen_tied = false;
+  bool seen_plain_waiting = false;
+  bool found = false;
+  struct gomp_task *t = parent->children;
+  while (1)
+    {
+      if (t == task)
+	found = true;
+      if (seen_tied && t->kind == GOMP_TASK_WAITING)
+	gomp_fatal ("verify_children_queue: WAITING task after TIED");
+      if (t->kind == GOMP_TASK_TIED)
+	seen_tied = true;
+      else if (t->kind == GOMP_TASK_WAITING)
+	{
+	  if (t->parent_depends_on)
+	    {
+	      if (seen_plain_waiting)
+		gomp_fatal ("verify_children_queue: parent_depends_on after "
+			    "!parent_depends_on");
+	    }
+	  else
+	    seen_plain_waiting = true;
+	}
+      t = t->next_child;
+      if (t == parent->children)
+	break;
+    }
+  if (!found)
+    gomp_fatal ("verify_children_queue: child not found in parent queue");
+}
+
+/* Sanity check TASK to make sure it is in its taskgroup queue (if
+   applicable), and that the tasks therein are in the right order.
+
+   The expected order is that GOMP_TASK_WAITING tasks must come before
+   GOMP_TASK_TIED tasks.
+
+   TASK is the task.  */
+
+static void
+verify_taskgroup_queue (struct gomp_task *task)
+{
+  struct gomp_taskgroup *taskgroup = task->taskgroup;
+  if (!taskgroup)
+    return;
+
+  bool seen_tied = false;
+  bool found = false;
+  struct gomp_task *t = taskgroup->children;
+  while (1)
+    {
+      if (t == task)
+	found = true;
+      if (t->kind == GOMP_TASK_WAITING && seen_tied)
+	gomp_fatal ("verify_taskgroup_queue: WAITING task after TIED");
+      if (t->kind == GOMP_TASK_TIED)
+	seen_tied = true;
+      t = t->next_taskgroup;
+      if (t == taskgroup->children)
+	break;
+    }
+  if (!found)
+    gomp_fatal ("verify_taskgroup_queue: child not found in parent queue");
+}
+
+/* Verify that TASK is in the team's task queue.  */
+
+static void
+verify_task_queue (struct gomp_task *task, struct gomp_team *team)
+{
+  struct gomp_task *t = team->task_queue;
+  if (team)
+    while (1)
+      {
+	if (t == task)
+	  return;
+	t = t->next_queue;
+	if (t == team->task_queue)
+	  break;
+      }
+  gomp_fatal ("verify_team_queue: child not in team");
+}
+#endif
+
 static inline bool
 gomp_task_run_pre (struct gomp_task *child_task, struct gomp_task *parent,
-		   struct gomp_taskgroup *taskgroup, struct gomp_team *team)
+		   struct gomp_team *team)
 {
+#if _LIBGOMP_CHECKING
+  verify_children_queue (child_task, parent);
+  verify_taskgroup_queue (child_task);
+  verify_task_queue (child_task, team);
+#endif
+
   if (parent)
     {
+      /* Adjust children such that it will point to a next child,
+	 while the current one is scheduled to be executed.  This way,
+	 GOMP_taskwait (and others) can schedule a next task while
+	 waiting.
+
+	 Do not remove it entirely from the circular list, as it is
+	 still a child, though not one we should consider first (say
+	 by GOMP_taskwait).  */
       if (parent->children == child_task)
 	parent->children = child_task->next_child;
+      /* TIED tasks cannot come before WAITING tasks.  If we're about
+	 to make this task TIED, rewire things appropriately.
+	 However, a TIED task at the end is perfectly fine.  */
+      else if (child_task->next_child->kind == GOMP_TASK_WAITING
+	       && child_task->next_child != parent->children)
+	{
+	  /* Remove from the list.  */
+	  child_task->prev_child->next_child = child_task->next_child;
+	  child_task->next_child->prev_child = child_task->prev_child;
+	  /* Rewire at the end of its siblings.  */
+	  child_task->next_child = parent->children;
+	  child_task->prev_child = parent->children->prev_child;
+	  parent->children->prev_child->next_child = child_task;
+	  parent->children->prev_child = child_task;
+	}
+
+      /* If the current task (child_task) is at the top of the
+	 parent's last_parent_depends_on, it's about to be removed
+	 from it.  Adjust last_parent_depends_on appropriately.  */
       if (__builtin_expect (child_task->parent_depends_on, 0)
 	  && parent->taskwait->last_parent_depends_on == child_task)
 	{
+	  /* The last_parent_depends_on list was built with all
+	     parent_depends_on entries linked to the prev_child.  Grab
+	     the next last_parent_depends_on head from this prev_child if
+	     available...  */
 	  if (child_task->prev_child->kind == GOMP_TASK_WAITING
 	      && child_task->prev_child->parent_depends_on)
 	    parent->taskwait->last_parent_depends_on = child_task->prev_child;
 	  else
-	    parent->taskwait->last_parent_depends_on = NULL;
+	    {
+	      /* ...otherwise, there are no more parent_depends_on
+		 entries waiting to run.  In which case, clear the
+		 list.  */
+	      parent->taskwait->last_parent_depends_on = NULL;
+	    }
 	}
     }
-  if (taskgroup && taskgroup->children == child_task)
-    taskgroup->children = child_task->next_taskgroup;
+
+  /* Adjust taskgroup to point to the next taskgroup.  See note above
+     regarding adjustment of children as to why the child_task is not
+     removed entirely from the circular list.  */
+  struct gomp_taskgroup *taskgroup = child_task->taskgroup;
+  if (taskgroup)
+    {
+      if (taskgroup->children == child_task)
+	taskgroup->children = child_task->next_taskgroup;
+      /* TIED tasks cannot come before WAITING tasks.  If we're about
+	 to make this task TIED, rewire things appropriately.
+	 However, a TIED task at the end is perfectly fine.  */
+      else if (child_task->next_taskgroup->kind == GOMP_TASK_WAITING
+	       && child_task->next_taskgroup != taskgroup->children)
+	{
+	  /* Remove from the list.  */
+	  child_task->prev_taskgroup->next_taskgroup
+	    = child_task->next_taskgroup;
+	  child_task->next_taskgroup->prev_taskgroup
+	    = child_task->prev_taskgroup;
+	  /* Rewire at the end of its taskgroup.  */
+	  child_task->next_taskgroup = taskgroup->children;
+	  child_task->prev_taskgroup = taskgroup->children->prev_taskgroup;
+	  taskgroup->children->prev_taskgroup->next_taskgroup = child_task;
+	  taskgroup->children->prev_taskgroup = child_task;
+	}
+    }
+
+  /* Remove child_task from the task_queue.  */
   child_task->prev_queue->next_queue = child_task->next_queue;
   child_task->next_queue->prev_queue = child_task->prev_queue;
   if (team->task_queue == child_task)
@@ -442,6 +770,7 @@ gomp_task_run_pre (struct gomp_task *child_task, struct gomp_task *parent,
 	team->task_queue = NULL;
     }
   child_task->kind = GOMP_TASK_TIED;
+
   if (--team->task_queued_count == 0)
     gomp_team_barrier_clear_task_pending (&team->barrier);
   if ((gomp_team_barrier_cancelled (&team->barrier)
@@ -479,6 +808,11 @@ gomp_task_run_post_handle_depend_hash (struct gomp_task *child_task)
       }
 }
 
+/* After CHILD_TASK has been run, adjust the various task queues to
+   give higher priority to the tasks that depend on CHILD_TASK.
+
+   TEAM is the team to which CHILD_TASK belongs to.  */
+
 static size_t
 gomp_task_run_post_handle_dependers (struct gomp_task *child_task,
 				     struct gomp_team *team)
@@ -502,6 +836,7 @@ gomp_task_run_post_handle_dependers (struct gomp_task *child_task,
 	      if (parent->taskwait && parent->taskwait->last_parent_depends_on
 		  && !task->parent_depends_on)
 		{
+		  /* Put depender in last_parent_depends_on.  */
 		  struct gomp_task *last_parent_depends_on
 		    = parent->taskwait->last_parent_depends_on;
 		  task->next_child = last_parent_depends_on->next_child;
@@ -509,6 +844,8 @@ gomp_task_run_post_handle_dependers (struct gomp_task *child_task,
 		}
 	      else
 		{
+		  /* Make depender a sibling of child_task, and place
+		     it at the top of said sibling list.  */
 		  task->next_child = parent->children;
 		  task->prev_child = parent->children->prev_child;
 		  parent->children = task;
@@ -518,6 +855,7 @@ gomp_task_run_post_handle_dependers (struct gomp_task *child_task,
 	    }
 	  else
 	    {
+	      /* Make depender a sibling of child_task.  */
 	      task->next_child = task;
 	      task->prev_child = task;
 	      parent->children = task;
@@ -539,6 +877,8 @@ gomp_task_run_post_handle_dependers (struct gomp_task *child_task,
 		parent->taskwait->last_parent_depends_on = task;
 	    }
 	}
+      /* If depender is in a taskgroup, put it at the TOP of its
+	 taskgroup.  */
       if (taskgroup)
 	{
 	  if (taskgroup->children)
@@ -560,6 +900,8 @@ gomp_task_run_post_handle_dependers (struct gomp_task *child_task,
 	      gomp_sem_post (&taskgroup->taskgroup_sem);
 	    }
 	}
+      /* Put depender of child_task at the END of the team's
+	 task_queue.  */
       if (team->task_queue)
 	{
 	  task->next_queue = team->task_queue;
@@ -602,12 +944,18 @@ gomp_task_run_post_handle_depend (struct gomp_task *child_task,
   return gomp_task_run_post_handle_dependers (child_task, team);
 }
 
+/* Remove CHILD_TASK from its parent.  */
+
 static inline void
 gomp_task_run_post_remove_parent (struct gomp_task *child_task)
 {
   struct gomp_task *parent = child_task->parent;
   if (parent == NULL)
     return;
+
+  /* If this was the last task the parent was depending on,
+     synchronize with gomp_task_maybe_wait_for_dependencies so it can
+     clean up and return.  */
   if (__builtin_expect (child_task->parent_depends_on, 0)
       && --parent->taskwait->n_depend == 0
       && parent->taskwait->in_depend_wait)
@@ -615,6 +963,8 @@ gomp_task_run_post_remove_parent (struct gomp_task *child_task)
       parent->taskwait->in_depend_wait = false;
       gomp_sem_post (&parent->taskwait->taskwait_sem);
     }
+
+  /* Remove CHILD_TASK from its sibling list.  */
   child_task->prev_child->next_child = child_task->next_child;
   child_task->next_child->prev_child = child_task->prev_child;
   if (parent->children != child_task)
@@ -637,6 +987,8 @@ gomp_task_run_post_remove_parent (struct gomp_task *child_task)
     }
 }
 
+/* Remove CHILD_TASK from its taskgroup.  */
+
 static inline void
 gomp_task_run_post_remove_taskgroup (struct gomp_task *child_task)
 {
@@ -701,7 +1053,7 @@ gomp_barrier_handle_tasks (gomp_barrier_state_t state)
 	{
 	  child_task = team->task_queue;
 	  cancelled = gomp_task_run_pre (child_task, child_task->parent,
-					 child_task->taskgroup, team);
+					 team);
 	  if (__builtin_expect (cancelled, 0))
 	    {
 	      if (to_free)
@@ -766,7 +1118,9 @@ gomp_barrier_handle_tasks (gomp_barrier_state_t state)
     }
 }
 
-/* Called when encountering a taskwait directive.  */
+/* Called when encountering a taskwait directive.
+
+   Wait for all children of the current task.  */
 
 void
 GOMP_taskwait (void)
@@ -812,8 +1166,7 @@ GOMP_taskwait (void)
 	{
 	  child_task = task->children;
 	  cancelled
-	    = gomp_task_run_pre (child_task, task, child_task->taskgroup,
-				 team);
+	    = gomp_task_run_pre (child_task, task, team);
 	  if (__builtin_expect (cancelled, 0))
 	    {
 	      if (to_free)
@@ -863,6 +1216,9 @@ GOMP_taskwait (void)
 	 finish_cancelled:;
 	  size_t new_tasks
 	    = gomp_task_run_post_handle_depend (child_task, team);
+
+	  /* Remove child_task from children list, and set up the next
+	     sibling to be run.  */
 	  child_task->prev_child->next_child = child_task->next_child;
 	  child_task->next_child->prev_child = child_task->prev_child;
 	  if (task->children == child_task)
@@ -872,8 +1228,12 @@ GOMP_taskwait (void)
 	      else
 		task->children = NULL;
 	    }
+	  /* Orphan all the children of CHILD_TASK.  */
 	  gomp_clear_parent (child_task->children);
+
+	  /* Remove CHILD_TASK from its taskgroup.  */
 	  gomp_task_run_post_remove_taskgroup (child_task);
+
 	  to_free = child_task;
 	  child_task = NULL;
 	  team->task_count--;
@@ -889,9 +1249,11 @@ GOMP_taskwait (void)
 }
 
 /* This is like GOMP_taskwait, but we only wait for tasks that the
-   upcoming task depends on.  */
+   upcoming task depends on.
 
-static void
+   DEPEND is as in GOMP_task.  */
+
+void
 gomp_task_maybe_wait_for_dependencies (void **depend)
 {
   struct gomp_thread *thr = gomp_thread ();
@@ -923,11 +1285,33 @@ gomp_task_maybe_wait_for_dependencies (void **depend)
 	      {
 		tsk->parent_depends_on = true;
 		++num_awaited;
+		/* If a task we need to wait for is not already
+		   running and is ready to be scheduled, move it to
+		   front, so that we run it as soon as possible.
+
+		   We rearrange the children queue such that all
+		   parent_depends_on tasks are first, and
+		   last_parent_depends_on points to the last such task
+		   we rearranged.  For example, given the following
+		   children where PD[123] are the parent_depends_on
+		   tasks:
+
+			task->children
+			|
+			V
+			C1 -> C2 -> C3 -> PD1 -> PD2 -> PD3 -> C4
+
+		   We rearrange such that:
+
+			task->children
+			|	       +--- last_parent_depends_on
+			|	       |
+			V	       V
+			PD1 -> PD2 -> PD3 -> C1 -> C2 -> C3 -> C4
+		*/
+
 		if (tsk->num_dependees == 0 && tsk->kind == GOMP_TASK_WAITING)
 		  {
-		    /* If a task we need to wait for is not already
-		       running and is ready to be scheduled, move it
-		       to front, so that we run it as soon as possible.  */
 		    if (last_parent_depends_on)
 		      {
 			tsk->prev_child->next_child = tsk->next_child;
@@ -941,8 +1325,8 @@ gomp_task_maybe_wait_for_dependencies (void **depend)
 		      {
 			tsk->prev_child->next_child = tsk->next_child;
 			tsk->next_child->prev_child = tsk->prev_child;
-			tsk->prev_child = task->children;
-			tsk->next_child = task->children->next_child;
+			tsk->prev_child = task->children->prev_child;
+			tsk->next_child = task->children;
 			task->children = tsk;
 			tsk->prev_child->next_child = tsk;
 			tsk->next_child->prev_child = tsk;
@@ -983,8 +1367,7 @@ gomp_task_maybe_wait_for_dependencies (void **depend)
 	{
 	  child_task = task->children;
 	  cancelled
-	    = gomp_task_run_pre (child_task, task, child_task->taskgroup,
-				 team);
+	    = gomp_task_run_pre (child_task, task, team);
 	  if (__builtin_expect (cancelled, 0))
 	    {
 	      if (to_free)
@@ -1028,6 +1411,8 @@ gomp_task_maybe_wait_for_dependencies (void **depend)
 	    = gomp_task_run_post_handle_depend (child_task, team);
 	  if (child_task->parent_depends_on)
 	    --taskwait.n_depend;
+
+	  /* Remove child_task from sibling list.  */
 	  child_task->prev_child->next_child = child_task->next_child;
 	  child_task->next_child->prev_child = child_task->prev_child;
 	  if (task->children == child_task)
@@ -1037,6 +1422,7 @@ gomp_task_maybe_wait_for_dependencies (void **depend)
 	      else
 		task->children = NULL;
 	    }
+
 	  gomp_clear_parent (child_task->children);
 	  gomp_task_run_post_remove_taskgroup (child_task);
 	  to_free = child_task;
@@ -1070,7 +1456,7 @@ GOMP_taskgroup_start (void)
   struct gomp_taskgroup *taskgroup;
 
   /* If team is NULL, all tasks are executed as
-     GOMP_TASK_IFFALSE tasks and thus all children tasks of
+     GOMP_TASK_UNDEFERRED tasks and thus all children tasks of
      taskgroup and their descendant tasks will be finished
      by the time GOMP_taskgroup_end is called.  */
   if (team == NULL)
@@ -1137,8 +1523,7 @@ GOMP_taskgroup_end (void)
       if (child_task->kind == GOMP_TASK_WAITING)
 	{
 	  cancelled
-	    = gomp_task_run_pre (child_task, child_task->parent, taskgroup,
-				 team);
+	    = gomp_task_run_pre (child_task, child_task->parent, team);
 	  if (__builtin_expect (cancelled, 0))
 	    {
 	      if (to_free)