diff --git a/libgomp/libgomp.h b/libgomp/libgomp.h
index 70b4e9f..a074ae7 100644
--- a/libgomp/libgomp.h
+++ b/libgomp/libgomp.h
@@ -36,6 +36,11 @@
 #ifndef LIBGOMP_H 
 #define LIBGOMP_H 1
 
+#ifndef _LIBGOMP_CHECKING_
+/* Define to 1 to perform internal sanity checks.  */
+#define _LIBGOMP_CHECKING_ 0
+#endif
+
 #include "config.h"
 #include "gstdint.h"
 #include "libgomp-plugin.h"
diff --git a/libgomp/task.c b/libgomp/task.c
index f6a67eb..6ac910e 100644
--- a/libgomp/task.c
+++ b/libgomp/task.c
@@ -27,6 +27,7 @@
    creation and termination.  */
 
 #include "libgomp.h"
+#include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include "gomp-constants.h"
@@ -567,10 +568,151 @@ gomp_create_target_task (struct gomp_device_descr *devicep,
     gomp_team_barrier_wake (&team->barrier, 1);
 }
 
+/* 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)
+    {
+      fprintf (stderr, "verify_children_queue: incompatible parents\n");
+      abort ();
+    }
+  /* 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)
+	{
+	  fprintf (stderr,
+		   "verify_children_queue: WAITING task after TIED.");
+	  abort ();
+	}
+      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)
+		{
+		  fprintf (stderr,
+			   "verify_children_queue: parent_depends_on after "
+			   "!parent_depends_on\n");
+		  abort ();
+		}
+	    }
+	  else
+	    seen_plain_waiting = true;
+	}
+      t = t->next_child;
+      if (t == parent->children)
+	break;
+    }
+  if (!found)
+    {
+      fprintf (stderr,
+	       "verify_children_queue: child not found in parent queue\n");
+      abort ();
+    }
+}
+
+/* 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.  TASKGROUP is the alleged taskgroup that contains
+   TASK.  */
+
+static void
+verify_taskgroup_queue (struct gomp_task *task,
+			struct gomp_taskgroup *taskgroup)
+{
+  if (taskgroup != task->taskgroup)
+    {
+      fprintf (stderr, "verify_taskgroup_queue: incompatible taskgroups\n");
+      fprintf (stderr, "%p %p\n", task->taskgroup, taskgroup);
+      abort ();
+    }
+  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)
+	{
+	  fprintf (stderr,
+		   "verify_taskgroup_queue: WAITING task after TIED.\n");
+	  abort ();
+	}
+      if (t->kind == GOMP_TASK_TIED)
+	seen_tied = true;
+      t = t->next_taskgroup;
+      if (t == taskgroup->children)
+	break;
+    }
+  if (!found)
+    {
+      fprintf (stderr,
+	       "verify_taskgroup_queue: child not found in parent queue\n");
+      abort ();
+    }
+}
+
+/* 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;
+      }
+  fprintf (stderr, "verify_team_queue: child not in team\n");
+  abort ();
+}
+
 static inline bool
 gomp_task_run_pre (struct gomp_task *child_task, struct gomp_task *parent,
 		   struct gomp_taskgroup *taskgroup, struct gomp_team *team)
 {
+  if (_LIBGOMP_CHECKING_)
+    {
+      verify_children_queue (child_task, parent);
+      verify_taskgroup_queue (child_task,
+			      taskgroup ? taskgroup : child_task->taskgroup);
+      verify_task_queue (child_task, team);
+    }
+
   if (parent)
     {
       /* Adjust children such that it will point to a next child,
@@ -583,6 +725,21 @@ gomp_task_run_pre (struct gomp_task *child_task, struct gomp_task *parent,
 	 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
@@ -610,8 +767,28 @@ gomp_task_run_pre (struct gomp_task *child_task, struct gomp_task *parent,
   /* 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.  */
-  if (taskgroup && taskgroup->children == child_task)
-    taskgroup->children = child_task->next_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;
@@ -1339,6 +1516,7 @@ GOMP_taskgroup_end (void)
     goto finish;
 
   gomp_mutex_lock (&team->task_lock);
+  bool task_from_taskgroup = true;
   while (1)
     {
       bool cancelled = false;
@@ -1349,6 +1527,7 @@ GOMP_taskgroup_end (void)
 	      if (task->children == NULL)
 		goto do_wait;
 	      child_task = task->children;
+	      task_from_taskgroup = false;
             }
           else
 	    {
@@ -1362,11 +1541,20 @@ GOMP_taskgroup_end (void)
 	    }
 	}
       else
-	child_task = taskgroup->children;
+	{
+	  child_task = taskgroup->children;
+	  task_from_taskgroup = true;
+	}
       if (child_task->kind == GOMP_TASK_WAITING)
 	{
+	  /* ?? Since child_task can come from either
+	     taskgroup->children or from task->children, child_task
+	     does not necessarily live in `taskgroup' below.  Perhaps
+	     in this case we should pass NULL to taskgroup, to
+	     indicate child_task does not live in `taskgroup'?  */
 	  cancelled
-	    = gomp_task_run_pre (child_task, child_task->parent, taskgroup,
+	    = gomp_task_run_pre (child_task, child_task->parent,
+				 task_from_taskgroup ? taskgroup : NULL,
 				 team);
 	  if (__builtin_expect (cancelled, 0))
 	    {
