[gomp3] Fixes for number of threads resolving

[Jakub Jelinek <jakub at redhat dot com>]

Hi!

If nest-var is false, the 2.4.1 algorithm is supposed to look at number of
enclosing active parallel regions (i.e. regions with more than one thread
in the team), similarly when checking max-active-levels-var limit.
To do these checks efficiently, I've added a field for this count, which
speeds up omp_in_parallel and omp_get_active_levels too.

This patch also implements the so far unimplemented OMP_THREAD_LIMIT=N
limiting of total number of OpenMP threads.  The default is considered to be
infinity so no locking resp. atomic operation is needed on team creation
and termination, if OMP_THREAD_LIMIT= was set by the user, there is a global
counter how many threads still can be created.

Regtested on x86_64-linux, committed to gomp-3_0-branch.

2008-02-29  Jakub Jelinek  <jakub@redhat.com>

	* team.c (gomp_thread_start): Initialize ts.active_level.
	* sections.c (GOMP_parallel_sections_start): Pass count
	as second argument to gomp_resolve_num_threads, don't adjust
	num_threads after the call.
	* env.c (gomp_thread_limit_var): Initialize to ULONG_MAX.
	(gomp_remaining_threads_count, gomp_remaining_threads_lock): New
	variables.
	(initialize_env): Initialize gomp_remaining_threads_count and
	gomp_remaining_threads_lock if needed.
	(omp_get_thread_limit): Return INT_MAX if gomp_thread_limit_var
	is larger than INT_MAX.
	* libgomp.h (struct gomp_team_state): Add active_level field.
	(gomp_remaining_threads_count, gomp_remaining_threads_lock): New
	decls.
	* loop.c (gomp_parallel_loop_start): Pass 0 as second argument
	to gomp_resolve_num_threads.
	* parallel.c: Include limits.h.
	(gomp_resolve_num_threads): Add count argument.  Use current thread's
	active_level rather than level when checking nest-var or
	max-active-levels-var.  Implement OMP_THREAD_LIMIT limitation of
	total number of OpenMP threads.  If second argument is non-zero,
	don't return more than that number if dyn-var is true.
	(GOMP_parallel_start): Pass 0 as second argument to
	gomp_resolve_num_threads.
	(GOMP_parallel_end): Decrease gomp_remaining_threads_count
	if gomp_thread_limit_var != ULONG_MAX.
	(omp_in_parallel, omp_get_active_level): Implement using
	ts.active_level.

--- libgomp/team.c	(revision 132481)
+++ libgomp/team.c	(working copy)
@@ -1,4 +1,4 @@
-/* Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
+/* Copyright (C) 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
    Contributed by Richard Henderson <rth@redhat.com>.
 
    This file is part of the GNU OpenMP Library (libgomp).
@@ -119,6 +119,7 @@ gomp_thread_start (void *xdata)
 	  thr->ts.work_share = NULL;
 	  thr->ts.team_id = 0;
 	  thr->ts.level = 0;
+	  thr->ts.active_level = 0;
 	  thr->ts.work_share_generation = 0;
 	  thr->ts.static_trip = 0;
 
@@ -207,6 +208,8 @@ gomp_team_start (void (*fn) (void *), vo
   thr->ts.work_share = work_share;
   thr->ts.team_id = 0;
   ++thr->ts.level;
+  if (nthreads > 1)
+    ++thr->ts.active_level;
   thr->ts.work_share_generation = 0;
   thr->ts.static_trip = 0;
   thr->task = gomp_new_task (task, icv);
@@ -254,6 +257,7 @@ gomp_team_start (void (*fn) (void *), vo
 	  nthr->ts.work_share = work_share;
 	  nthr->ts.team_id = i;
 	  nthr->ts.level = team->prev_ts.level + 1;
+	  nthr->ts.active_level = thr->ts.active_level;
 	  nthr->ts.work_share_generation = 0;
 	  nthr->ts.static_trip = 0;
 	  nthr->task = gomp_new_task (task, icv);
@@ -304,6 +308,7 @@ gomp_team_start (void (*fn) (void *), vo
       start_data->ts.work_share = work_share;
       start_data->ts.team_id = i;
       start_data->ts.level = team->prev_ts.level + 1;
+      start_data->ts.active_level = thr->ts.active_level;
       start_data->ts.work_share_generation = 0;
       start_data->ts.static_trip = 0;
       start_data->task = gomp_new_task (task, icv);
--- libgomp/sections.c	(revision 132481)
+++ libgomp/sections.c	(working copy)
@@ -1,4 +1,4 @@
-/* Copyright (C) 2005, 2007 Free Software Foundation, Inc.
+/* Copyright (C) 2005, 2007, 2008 Free Software Foundation, Inc.
    Contributed by Richard Henderson <rth@redhat.com>.
 
    This file is part of the GNU OpenMP Library (libgomp).
@@ -105,10 +105,7 @@ GOMP_parallel_sections_start (void (*fn)
 {
   struct gomp_work_share *ws;
 
-  num_threads = gomp_resolve_num_threads (num_threads);
-  if (num_threads > count && gomp_icv()->dyn_var)
-    num_threads = count;
-
+  num_threads = gomp_resolve_num_threads (num_threads, count);
   ws = gomp_new_work_share (false, num_threads);
   gomp_sections_init (ws, count);
   gomp_team_start (fn, data, num_threads, ws);
--- libgomp/env.c	(revision 132481)
+++ libgomp/env.c	(working copy)
@@ -1,4 +1,4 @@
-/* Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
+/* Copyright (C) 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
    Contributed by Richard Henderson <rth@redhat.com>.
 
    This file is part of the GNU OpenMP Library (libgomp).
@@ -49,7 +49,11 @@ unsigned short *gomp_cpu_affinity;
 bool gomp_active_wait_policy = false;
 size_t gomp_cpu_affinity_len;
 unsigned long gomp_max_active_levels_var = INT_MAX;
-unsigned long gomp_thread_limit_var = INT_MAX;
+unsigned long gomp_thread_limit_var = ULONG_MAX;
+unsigned long gomp_remaining_threads_count;
+#ifndef HAVE_SYNC_BUILTINS
+gomp_mutex_t gomp_remaining_threads_lock;
+#endif
 
 /* Parse the OMP_SCHEDULE environment variable.  */
 
@@ -125,7 +129,7 @@ parse_schedule (void)
   return;
 }
 
-/* Parse an unsigned long environment varible.  Return true if one was
+/* Parse an unsigned long environment variable.  Return true if one was
    present and it was successfully parsed.  */
 
 static bool
@@ -391,6 +395,13 @@ initialize_env (void)
   parse_wait_policy ();
   parse_unsigned_long ("OMP_MAX_ACTIVE_LEVELS", &gomp_max_active_levels_var);
   parse_unsigned_long ("OMP_THREAD_LIMIT", &gomp_thread_limit_var);
+  if (gomp_thread_limit_var != ULONG_MAX)
+    {
+      gomp_remaining_threads_count = gomp_thread_limit_var - 1;
+#ifndef HAVE_SYNC_BUILTINS
+      gomp_mutex_init (&gomp_remaining_threads_lock);
+#endif
+    }
   if (!parse_unsigned_long ("OMP_NUM_THREADS", &gomp_global_icv.nthreads_var))
     gomp_init_num_threads ();
   if (parse_affinity ())
@@ -503,7 +514,7 @@ omp_get_max_threads (void)
 int
 omp_get_thread_limit (void)
 {
-  return gomp_thread_limit_var;
+  return gomp_thread_limit_var > INT_MAX ? INT_MAX : gomp_thread_limit_var;
 }
 
 void
--- libgomp/libgomp.h	(revision 132481)
+++ libgomp/libgomp.h	(working copy)
@@ -1,4 +1,4 @@
-/* Copyright (C) 2005, 2007 Free Software Foundation, Inc.
+/* Copyright (C) 2005, 2007, 2008 Free Software Foundation, Inc.
    Contributed by Richard Henderson <rth@redhat.com>.
 
    This file is part of the GNU OpenMP Library (libgomp).
@@ -146,6 +146,9 @@ struct gomp_team_state
   /* Nesting level.  */
   unsigned level;
 
+  /* Active nesting level.  Only active parallel regions are counted.  */
+  unsigned active_level;
+
   /* The work share "generation" is a number that increases by one for
      each work share construct encountered in the dynamic flow of the
      program.  It is used to find the control data for the work share
@@ -221,6 +224,10 @@ struct gomp_task_icv
 
 extern struct gomp_task_icv gomp_global_icv;
 extern unsigned long gomp_thread_limit_var;
+extern unsigned long gomp_remaining_threads_count;
+#ifndef HAVE_SYNC_BUILTINS
+extern gomp_mutex_t gomp_remaining_threads_lock;
+#endif
 extern unsigned long gomp_max_active_levels_var;
 extern bool gomp_active_wait_policy;
 
@@ -335,7 +342,7 @@ extern void gomp_ordered_sync (void);
 
 /* parallel.c */
 
-extern unsigned gomp_resolve_num_threads (unsigned);
+extern unsigned gomp_resolve_num_threads (unsigned, unsigned);
 
 /* proc.c (in config/) */
 
--- libgomp/loop.c	(revision 132481)
+++ libgomp/loop.c	(working copy)
@@ -1,4 +1,4 @@
-/* Copyright (C) 2005 Free Software Foundation, Inc.
+/* Copyright (C) 2005, 2008 Free Software Foundation, Inc.
    Contributed by Richard Henderson <rth@redhat.com>.
 
    This file is part of the GNU OpenMP Library (libgomp).
@@ -379,7 +379,7 @@ gomp_parallel_loop_start (void (*fn) (vo
 {
   struct gomp_work_share *ws;
 
-  num_threads = gomp_resolve_num_threads (num_threads);
+  num_threads = gomp_resolve_num_threads (num_threads, 0);
   ws = gomp_new_work_share (false, num_threads);
   gomp_loop_init (ws, start, end, incr, sched, chunk_size);
   gomp_team_start (fn, data, num_threads, ws);
--- libgomp/parallel.c	(revision 132481)
+++ libgomp/parallel.c	(working copy)
@@ -1,4 +1,4 @@
-/* Copyright (C) 2005, 2007 Free Software Foundation, Inc.
+/* Copyright (C) 2005, 2007, 2008 Free Software Foundation, Inc.
    Contributed by Richard Henderson <rth@redhat.com>.
 
    This file is part of the GNU OpenMP Library (libgomp).
@@ -28,6 +28,7 @@
 /* This file handles the (bare) PARALLEL construct.  */
 
 #include "libgomp.h"
+#include <limits.h>
 
 
 /* Determine the number of threads to be launched for a PARALLEL construct.
@@ -37,20 +38,20 @@
    is not present, SPECIFIED is 0.  */
 
 unsigned
-gomp_resolve_num_threads (unsigned specified)
+gomp_resolve_num_threads (unsigned specified, unsigned count)
 {
   struct gomp_thread *thread = gomp_thread();
   struct gomp_task_icv *icv;
-  unsigned threads_requested, max_num_threads;
-  unsigned threads_busy, max_threads_remaining;
-  
-  icv = gomp_icv();
+  unsigned threads_requested, max_num_threads, num_threads;
+  unsigned long remaining;
+
+  icv = gomp_icv ();
 
   if (specified == 1)
     return 1;
-  else if (thread->ts.level >= 1 && !icv->nest_var)
+  else if (thread->ts.active_level >= 1 && !icv->nest_var)
     return 1;
-  else if (thread->ts.level >= gomp_max_active_levels_var)
+  else if (thread->ts.active_level >= gomp_max_active_levels_var)
     return 1;
 
   /* If NUM_THREADS not specified, use nthreads_var.  */
@@ -59,15 +60,7 @@ gomp_resolve_num_threads (unsigned speci
   else
     threads_requested = specified;
 
-  /* ??? FIXME: We probably need a global variable that contains this
-     value; walking the entire team tree doesn't sound like a Good Idea.  */
-  threads_busy = 1;
-
-  max_threads_remaining = gomp_thread_limit_var - threads_busy + 1;
-  if (threads_requested <= max_threads_remaining)
-    max_num_threads = threads_requested;
-  else
-    max_num_threads = max_threads_remaining;
+  max_num_threads = threads_requested;
 
   /* If dynamic threads are enabled, bound the number of threads
      that we launch.  */
@@ -75,22 +68,65 @@ gomp_resolve_num_threads (unsigned speci
     {
       unsigned dyn = gomp_dynamic_max_threads ();
       if (dyn < max_num_threads)
-	return dyn;
+	max_num_threads = dyn;
+
+      /* Optimization for parallel sections.  */
+      if (count && count < max_num_threads)
+	max_num_threads = count;
+    }
+
+  /* ULONG_MAX stands for infinity.  */
+  if (gomp_thread_limit_var == ULONG_MAX || max_num_threads == 1)
+    return max_num_threads;
+
+#ifdef HAVE_SYNC_BUILTINS
+  do
+    {
+      remaining = gomp_remaining_threads_count;
+      num_threads = max_num_threads;
+      if (num_threads > remaining)
+	num_threads = remaining + 1;
     }
+  while (__sync_val_compare_and_swap (&gomp_remaining_threads_count,
+				      remaining, remaining - num_threads + 1)
+	 != remaining);
+#else
+  gomp_mutex_lock (&gomp_remaining_threads_lock);
+  num_threads = max_num_threads;
+  if (num_threads > gomp_remaining_threads_count)
+    num_threads = gomp_remaining_threads_count + 1;
+  gomp_remaining_threads_count -= num_threads - 1;
+  gomp_mutex_unlock (&gomp_remaining_threads_unlock);
+#endif
 
-  return max_num_threads;
+  return num_threads;
 }
 
 void
 GOMP_parallel_start (void (*fn) (void *), void *data, unsigned num_threads)
 {
-  num_threads = gomp_resolve_num_threads (num_threads);
+  num_threads = gomp_resolve_num_threads (num_threads, 0);
   gomp_team_start (fn, data, num_threads, NULL);
 }
 
 void
 GOMP_parallel_end (void)
 {
+  if (gomp_thread_limit_var != ULONG_MAX)
+    {
+      struct gomp_thread *thr = gomp_thread ();
+      struct gomp_team *team = thr->ts.team;
+      if (team && team->nthreads > 1)
+	{
+#ifdef HAVE_SYNC_BUILTINS
+	  __sync_fetch_and_add (&gomp_remaining_threads_count,
+				1UL - team->nthreads);
+#else
+	  gomp_mutex_lock (&gomp_remaining_threads_lock);
+	  gomp_remaining_threads_count -= team->nthreads - 1;
+#endif
+	}
+    }
   gomp_team_end ();
 }
 
@@ -117,16 +153,7 @@ omp_get_thread_num (void)
 int
 omp_in_parallel (void)
 {
-  struct gomp_team *team = gomp_thread ()->ts.team;
-
-  while (team)
-    {
-      if (team->nthreads > 1)
-	return true;
-      team = team->prev_ts.team;
-    }
-
-  return false;
+  return gomp_thread ()->ts.active_level > 0;
 }
 
 int
@@ -163,17 +190,7 @@ omp_get_team_size (int level)
 int
 omp_get_active_level (void)
 {
-  struct gomp_team *team = gomp_thread ()->ts.team;
-  int active = 0;
-
-  while (team)
-    {
-      if (team->nthreads > 1)
-	++active;
-      team = team->prev_ts.team;
-    }
-
-  return active;
+  return gomp_thread ()->ts.active_level;
 }
 
 ialias (omp_get_num_threads)

	Jakub