/* Copyright (C) 2007-2026 Free Software Foundation, Inc.   Contributed by Richard Henderson <rth@redhat.com>.    This file is part of the GNU Offloading and Multi Processing Library   (libgomp).    Libgomp is free software; you can redistribute it and/or modify it   under the terms of the GNU General Public License as published by   the Free Software Foundation; either version 3, or (at your option)   any later version.    Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS   FOR A PARTICULAR PURPOSE.  See the GNU General Public License for   more details.    Under Section 7 of GPL version 3, you are granted additional   permissions described in the GCC Runtime Library Exception, version   3.1, as published by the Free Software Foundation.    You should have received a copy of the GNU General Public License and   a copy of the GCC Runtime Library Exception along with this program;   see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see   <http://www.gnu.org/licenses/>.  */ /* This file handles the maintenance of tasks in response to task   creation and termination.  */ #include "libgomp.h"#include <stdlib.h>#include <string.h>#include <assert.h>#include "gomp-constants.h" typedef struct gomp_task_depend_entry *hash_entry_type; static inline void *htab_alloc (size_t size){  return gomp_malloc (size);} static inline voidhtab_free (void *ptr){  free (ptr);} #include "hashtab.h" static inline hashval_thtab_hash (hash_entry_type element){  return hash_pointer (element->addr);} static inline boolhtab_eq (hash_entry_type x, hash_entry_type y){  return x->addr == y->addr;} /* Create a new task data structure.  */ voidgomp_init_task (struct gomp_task *task, struct gomp_task *parent_task,		struct gomp_task_icv *prev_icv){  /* It would seem that using memset here would be a win, but it turns     out that partially filling gomp_task allows us to keep the     overhead of task creation low.  In the nqueens-1.c test, for a     sufficiently large N, we drop the overhead from 5-6% to 1%.      Note, the nqueens-1.c test in serial mode is a good test to     benchmark the overhead of creating tasks as there are millions of     tiny tasks created that all run undeferred.  */  task->parent = parent_task;  priority_queue_init (&task->children_queue);  task->taskgroup = NULL;  task->dependers = NULL;  task->depend_hash = NULL;  task->taskwait = NULL;  task->depend_all_memory = NULL;  task->depend_count = 0;  task->completion_sem = NULL;  task->deferred_p = false;  task->icv = *prev_icv;  task->kind = GOMP_TASK_IMPLICIT;  task->in_tied_task = false;  task->final_task = false;  task->copy_ctors_done = false;  task->parent_depends_on = false;} /* Clean up a task, after completing it.  */ voidgomp_end_task (void){  struct gomp_thread *thr = gomp_thread ();  struct gomp_task *task = thr->task;   gomp_finish_task (task);  thr->task = task->parent;} /* Clear the parent field of every task in LIST.  */ static inline voidgomp_clear_parent_in_list (struct priority_list *list){  struct priority_node *p = list->tasks;  if (p)    do      {	priority_node_to_task (PQ_CHILDREN, p)->parent = NULL;	p = p->next;      }    while (p != list->tasks);} /* Splay tree version of gomp_clear_parent_in_list.    Clear the parent field of every task in NODE within SP, and free   the node when done.  */ static voidgomp_clear_parent_in_tree (prio_splay_tree sp, prio_splay_tree_node node){  if (!node)    return;  prio_splay_tree_node left = node->left, right = node->right;  gomp_clear_parent_in_list (&node->key.l);#if _LIBGOMP_CHECKING_  memset (node, 0xaf, sizeof (*node));#endif  /* No need to remove the node from the tree.  We're nuking     everything, so just free the nodes and our caller can clear the     entire splay tree.  */  free (node);  gomp_clear_parent_in_tree (sp, left);  gomp_clear_parent_in_tree (sp, right);} /* Clear the parent field of every task in Q and remove every task   from Q.  */ static inline voidgomp_clear_parent (struct priority_queue *q){  if (priority_queue_multi_p (q))    {      gomp_clear_parent_in_tree (&q->t, q->t.root);      /* All the nodes have been cleared in gomp_clear_parent_in_tree.	 No need to remove anything.  We can just nuke everything.  */      q->t.root = NULL;    }  else    gomp_clear_parent_in_list (&q->l);} /* Helper function for GOMP_task and gomp_create_target_task.    For a TASK with in/out dependencies, fill in the various dependency   queues.  PARENT is the parent of said task.  DEPEND is as in   GOMP_task.  */ static voidgomp_task_handle_depend (struct gomp_task *task, struct gomp_task *parent,			 void **depend){  size_t ndepend = (uintptr_t) depend[0];  size_t i;  hash_entry_type ent;  bool all_memory = false;   if (ndepend)    {      /* depend[0] is total # */      size_t nout = (uintptr_t) depend[1]; /* # of out: and inout: */      /* ndepend - nout is # of in: */      for (i = 0; i < ndepend; i++)	{	  task->depend[i].addr = depend[2 + i];	  task->depend[i].is_in = i >= nout;	  all_memory |= i < nout && depend[2 + i] == NULL;	}    }  else    {      ndepend = (uintptr_t) depend[1]; /* total # */      size_t nout = (uintptr_t) depend[2]; /* # of out: and inout: */      size_t nmutexinoutset = (uintptr_t) depend[3]; /* # of mutexinoutset: */      /* For now we treat mutexinoutset like out, which is compliant, but	 inefficient.  */      size_t nin = (uintptr_t) depend[4]; /* # of in: */      /* ndepend - nout - nmutexinoutset - nin is # of depobjs */      size_t normal = nout + nmutexinoutset + nin;      size_t n = 0;      bool has_in = false;      for (i = normal; i < ndepend; i++)	{	  void **d = (void **) (uintptr_t) depend[5 + i];	  switch ((uintptr_t) d[1])	    {	    case GOMP_DEPEND_OUT:	    case GOMP_DEPEND_INOUT:	      all_memory |= d[0] == NULL;	      break;	    case GOMP_DEPEND_MUTEXINOUTSET:	      break;	    case GOMP_DEPEND_IN:	    case GOMP_DEPEND_INOUTSET:	      has_in = true;	      continue;	    default:	      gomp_fatal ("unknown omp_depend_t dependence type %d",			  (int) (uintptr_t) d[1]);	    }	  task->depend[n].addr = d[0];	  task->depend[n++].is_in = 0;	}      for (i = 0; i < normal; i++)	{	  task->depend[n].addr = depend[5 + i];	  task->depend[n++].is_in = i >= nout + nmutexinoutset;	}      if (has_in)	for (i = normal; i < ndepend; i++)	  {	    void **d = (void **) (uintptr_t) depend[5 + i];	    if ((uintptr_t) d[1] != GOMP_DEPEND_IN		&& (uintptr_t) d[1] != GOMP_DEPEND_INOUTSET)	      continue;	    task->depend[n].addr = d[0];	    task->depend[n++].is_in	      = 1 + ((uintptr_t) d[1] == GOMP_DEPEND_INOUTSET);	  }    }  task->num_dependees = 0;  if (__builtin_expect (parent->depend_all_memory && ndepend, false))    {      struct gomp_task *tsk = parent->depend_all_memory;      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;	}      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++;    }  if (__builtin_expect (all_memory, false))    {      /* A task with depend(inout: omp_all_memory) depends on all previous	 sibling tasks which have any dependencies and all later sibling	 tasks which have any dependencies depend on it.  */      task->depend_count = 1;      task->depend[0].addr = NULL;      task->depend[0].next = NULL;      task->depend[0].prev = NULL;      task->depend[0].task = task;      task->depend[0].redundant = true;      task->depend[0].redundant_out = false;      if (parent->depend_hash)	{	  /* Inlined htab_traverse + htab_clear.  All newer siblings can	     just depend on this task.  Add dependencies on all previous	     sibling tasks with dependencies and make them redundant and	     clear the hash table.  */	  hash_entry_type *slot = &parent->depend_hash->entries[0];	  hash_entry_type *end = slot + htab_size (parent->depend_hash);	  for (; slot != end; ++slot)	    {	      if (*slot == HTAB_EMPTY_ENTRY)		continue;	      if (*slot != HTAB_DELETED_ENTRY)		{		  for (ent = *slot; ent; ent = ent->next)		    {		      struct gomp_task *tsk = ent->task; 		      if (ent->redundant_out)			break; 		      ent->redundant = true;		      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++;		    }		  while (ent)		    {		      ent->redundant = true;		      ent = ent->next;		    }		}	      *slot = HTAB_EMPTY_ENTRY;	    }	  if (htab_size (parent->depend_hash) <= 32)	    {	      parent->depend_hash->n_elements = 0;	      parent->depend_hash->n_deleted = 0;	    }	  else	    {	      /* Shrink the hash table if it would be too large.		 We don't want to walk e.g. megabytes of empty hash		 table for every depend(inout: omp_all_memory).  */	      free (parent->depend_hash);	      parent->depend_hash = htab_create (12);	    }	}      parent->depend_all_memory = task;      return;    }  task->depend_count = ndepend;  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].next = NULL;      task->depend[i].prev = NULL;      task->depend[i].task = task;      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:...).		 Similarly depend(inoutset:...) doesn't depend on earlier		 depend(inoutset:...).  */	      if (task->depend[i].is_in && task->depend[i].is_in == 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;	}    }} /* Body of empty task like taskwait nowait depend.  */ static voidempty_task (void *data __attribute__((unused))){} static void gomp_task_run_post_handle_depend_hash (struct gomp_task *);static inline size_t gomp_task_run_post_handle_depend (struct gomp_task *,						       struct gomp_team *); /* 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.    DEPEND is an array containing:     if depend[0] is non-zero, then:	depend[0]: number of depend elements.	depend[1]: number of depend elements of type "out/inout".	depend[2..N+1]: address of [1..N]th depend element.     otherwise, when depend[0] is zero, then:	depend[1]: number of depend elements.	depend[2]: number of depend elements of type "out/inout".	depend[3]: number of depend elements of type "mutexinoutset".	depend[4]: number of depend elements of type "in".	depend[5..4+depend[2]+depend[3]+depend[4]]: address of depend elements	depend[5+depend[2]+depend[3]+depend[4]..4+depend[1]]: address of		   omp_depend_t objects.  */ voidGOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),	   long arg_size, long arg_align, bool if_clause, unsigned flags,	   void **depend, int priority_arg, void *detach){  struct gomp_thread *thr = gomp_thread ();  struct gomp_team *team = thr->ts.team;  int priority = 0; 

Lines 1–500 of 2798. Load more