[gomp4.1] fix dependency scheduling problem

[Aldy Hernandez <aldyh at redhat dot com>]

Hi.

As I may have mentioned earlier, I'm implementing OpenMP 4.1's task 
priorities for GCC's libgomp.  This has had me looking at how we 
currently implement scheduling, and I believe we have a problem in how 
we rearrange dependencies.

Currently in gomp_task_maybe_wait_for_dependencies(), we have the 
following code for rearranging the first dependency (tsk) from a list of 
dependencies.

		else if (tsk != task->children)
                      {
                        /* Remove tsk from the sibling list...  */
                        tsk->prev_child->next_child = tsk->next_child;
                        tsk->next_child->prev_child = tsk->prev_child;
                        /* ...and insert it into the running task's
                           children.  */
-->BAD                  tsk->prev_child = task->children;
-->BAD                  tsk->next_child = task->children->next_child;
                        task->children = tsk;
                        tsk->prev_child->next_child = tsk;
                        tsk->next_child->prev_child = tsk;
                      }

If say, you have a parent_depends_on task PD1 that is in the following 
children queue:

	C1 -> C2 -> C3 -> PD1 -> C4

(Where parent->children points to C1 and C4 wraps around to C1 as per 
the circular list.)

The above code will transform the children queue into:

	PD1 -> C2 -> C3 -> C4 -> C1

The surrounding code looks sane, but this particular snippet quoted 
above has us moving the first child to the end of the queue, which is 
probably not what we want.  However, at least we're still keeping the 
parent_depends_on tasks first, just that we moved other previously 
unaffected children to the end of the queue.

What we really want is:

	PD1 -> C1 -> C2 -> C3 -> C4

The attached patch does just that.  I have also rewritten the comments 
now that I actually understand what's going on :).  Eventually this will 
all become clearer with my upcoming/proposed API for dealing with all 
these queues.

As discussed on IRC, there is another issue you pointed out in 
gomp_task_run_pre(), which I will address in a followup patch.

Tested on x86-64 Linux by running "make check-target-libgomp" with 
OMP_NUM_THREADS={1,2,55}.

OK for branch?

Attachment: curr
Description: Text document