Subversion Repositories openrisc_2011-10-31

/* Copyright (C) 2005, 2008, 2009 Free Software Foundation, Inc.

   Contributed by Richard Henderson <rth@redhat.com>.

   This file is part of the GNU OpenMP 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 contains routines for managing work-share iteration, both

   for loops and sections.  */

#include "libgomp.h"

#include <stdlib.h>

typedef unsigned long long gomp_ull;

/* This function implements the STATIC scheduling method.  The caller should

   iterate *pstart <= x < *pend.  Return zero if there are more iterations

   to perform; nonzero if not.  Return less than 0 if this thread had

   received the absolutely last iteration.  */

int

gomp_iter_ull_static_next (gomp_ull *pstart, gomp_ull *pend)

{

  struct gomp_thread *thr = gomp_thread ();

  struct gomp_team *team = thr->ts.team;

  struct gomp_work_share *ws = thr->ts.work_share;

  unsigned long nthreads = team ? team->nthreads : 1;

  if (thr->ts.static_trip == -1)

    return -1;

  /* Quick test for degenerate teams and orphaned constructs.  */

  if (nthreads == 1)

    {

      *pstart = ws->next_ull;

      *pend = ws->end_ull;

      thr->ts.static_trip = -1;

      return ws->next_ull == ws->end_ull;

    }

  /* We interpret chunk_size zero as "unspecified", which means that we

     should break up the iterations such that each thread makes only one

     trip through the outer loop.  */

  if (ws->chunk_size_ull == 0)

    {

      gomp_ull n, q, i, s0, e0, s, e;

      if (thr->ts.static_trip > 0)

        return 1;

      /* Compute the total number of iterations.  */

      if (__builtin_expect (ws->mode, 0) == 0)

        n = (ws->end_ull - ws->next_ull + ws->incr_ull - 1) / ws->incr_ull;

      else

        n = (ws->next_ull - ws->end_ull - ws->incr_ull - 1) / -ws->incr_ull;

      i = thr->ts.team_id;

      /* Compute the "zero-based" start and end points.  That is, as

         if the loop began at zero and incremented by one.  */

      q = n / nthreads;

      q += (q * nthreads != n);

      s0 = q * i;

      e0 = s0 + q;

      if (e0 > n)

        e0 = n;

      /* Notice when no iterations allocated for this thread.  */

      if (s0 >= e0)

        {

          thr->ts.static_trip = 1;

          return 1;

        }

      /* Transform these to the actual start and end numbers.  */

      s = s0 * ws->incr_ull + ws->next_ull;

      e = e0 * ws->incr_ull + ws->next_ull;

      *pstart = s;

      *pend = e;

      thr->ts.static_trip = (e0 == n ? -1 : 1);

      return 0;

    }

  else

    {

      gomp_ull n, s0, e0, i, c, s, e;

      /* Otherwise, each thread gets exactly chunk_size iterations

         (if available) each time through the loop.  */

      if (__builtin_expect (ws->mode, 0) == 0)

        n = (ws->end_ull - ws->next_ull + ws->incr_ull - 1) / ws->incr_ull;

      else

        n = (ws->next_ull - ws->end_ull - ws->incr_ull - 1) / -ws->incr_ull;

      i = thr->ts.team_id;

      c = ws->chunk_size_ull;

      /* Initial guess is a C sized chunk positioned nthreads iterations

         in, offset by our thread number.  */

      s0 = (thr->ts.static_trip * (gomp_ull) nthreads + i) * c;

      e0 = s0 + c;

      /* Detect overflow.  */

      if (s0 >= n)

        return 1;

      if (e0 > n)

        e0 = n;

      /* Transform these to the actual start and end numbers.  */

      s = s0 * ws->incr_ull + ws->next_ull;

      e = e0 * ws->incr_ull + ws->next_ull;

      *pstart = s;

      *pend = e;

      if (e0 == n)

        thr->ts.static_trip = -1;

      else

        thr->ts.static_trip++;

      return 0;

    }

}

/* This function implements the DYNAMIC scheduling method.  Arguments are

   as for gomp_iter_ull_static_next.  This function must be called with

   ws->lock held.  */

bool

gomp_iter_ull_dynamic_next_locked (gomp_ull *pstart, gomp_ull *pend)

{

  struct gomp_thread *thr = gomp_thread ();

  struct gomp_work_share *ws = thr->ts.work_share;

  gomp_ull start, end, chunk, left;

  start = ws->next_ull;

  if (start == ws->end_ull)

    return false;

  chunk = ws->chunk_size_ull;

  left = ws->end_ull - start;

  if (__builtin_expect (ws->mode & 2, 0))

    {

      if (chunk < left)

        chunk = left;

    }

  else

    {

      if (chunk > left)

        chunk = left;

    }

  end = start + chunk;

  ws->next_ull = end;

  *pstart = start;

  *pend = end;

  return true;

}

#if defined HAVE_SYNC_BUILTINS && defined __LP64__

/* Similar, but doesn't require the lock held, and uses compare-and-swap

   instead.  Note that the only memory value that changes is ws->next_ull.  */

bool

gomp_iter_ull_dynamic_next (gomp_ull *pstart, gomp_ull *pend)

{

  struct gomp_thread *thr = gomp_thread ();

  struct gomp_work_share *ws = thr->ts.work_share;

  gomp_ull start, end, nend, chunk;

  end = ws->end_ull;

  chunk = ws->chunk_size_ull;

  if (__builtin_expect (ws->mode & 1, 1))

    {

      gomp_ull tmp = __sync_fetch_and_add (&ws->next_ull, chunk);

      if (__builtin_expect (ws->mode & 2, 0) == 0)

        {

          if (tmp >= end)

            return false;

          nend = tmp + chunk;

          if (nend > end)

            nend = end;

          *pstart = tmp;

          *pend = nend;

          return true;

        }

      else

        {

          if (tmp <= end)

            return false;

          nend = tmp + chunk;

          if (nend < end)

            nend = end;

          *pstart = tmp;

          *pend = nend;

          return true;

        }

    }

  start = ws->next_ull;

  while (1)

    {

      gomp_ull left = end - start;

      gomp_ull tmp;

      if (start == end)

        return false;

      if (__builtin_expect (ws->mode & 2, 0))

        {

          if (chunk < left)

            chunk = left;

        }

      else

        {

          if (chunk > left)

            chunk = left;

        }

      nend = start + chunk;

      tmp = __sync_val_compare_and_swap (&ws->next_ull, start, nend);

      if (__builtin_expect (tmp == start, 1))

        break;

      start = tmp;

    }

  *pstart = start;

  *pend = nend;

  return true;

}

#endif /* HAVE_SYNC_BUILTINS */

/* This function implements the GUIDED scheduling method.  Arguments are

   as for gomp_iter_ull_static_next.  This function must be called with the

   work share lock held.  */

bool

gomp_iter_ull_guided_next_locked (gomp_ull *pstart, gomp_ull *pend)

{

  struct gomp_thread *thr = gomp_thread ();

  struct gomp_work_share *ws = thr->ts.work_share;

  struct gomp_team *team = thr->ts.team;

  gomp_ull nthreads = team ? team->nthreads : 1;

  gomp_ull n, q;

  gomp_ull start, end;

  if (ws->next_ull == ws->end_ull)

    return false;

  start = ws->next_ull;

  if (__builtin_expect (ws->mode, 0) == 0)

    n = (ws->end_ull - start) / ws->incr_ull;

  else

    n = (start - ws->end_ull) / -ws->incr_ull;

  q = (n + nthreads - 1) / nthreads;

  if (q < ws->chunk_size_ull)

    q = ws->chunk_size_ull;

  if (q <= n)

    end = start + q * ws->incr_ull;

  else

    end = ws->end_ull;

  ws->next_ull = end;

  *pstart = start;

  *pend = end;

  return true;

}

#if defined HAVE_SYNC_BUILTINS && defined __LP64__

/* Similar, but doesn't require the lock held, and uses compare-and-swap

   instead.  Note that the only memory value that changes is ws->next_ull.  */

bool

gomp_iter_ull_guided_next (gomp_ull *pstart, gomp_ull *pend)

{

  struct gomp_thread *thr = gomp_thread ();

  struct gomp_work_share *ws = thr->ts.work_share;

  struct gomp_team *team = thr->ts.team;

  gomp_ull nthreads = team ? team->nthreads : 1;

  gomp_ull start, end, nend, incr;

  gomp_ull chunk_size;

  start = ws->next_ull;

  end = ws->end_ull;

  incr = ws->incr_ull;

  chunk_size = ws->chunk_size_ull;

  while (1)

    {

      gomp_ull n, q;

      gomp_ull tmp;

      if (start == end)

        return false;

      if (__builtin_expect (ws->mode, 0) == 0)

        n = (end - start) / incr;

      else

        n = (start - end) / -incr;

      q = (n + nthreads - 1) / nthreads;

      if (q < chunk_size)

        q = chunk_size;

      if (__builtin_expect (q <= n, 1))

        nend = start + q * incr;

      else

        nend = end;

      tmp = __sync_val_compare_and_swap (&ws->next_ull, start, nend);

      if (__builtin_expect (tmp == start, 1))

        break;

      start = tmp;

    }

  *pstart = start;

  *pend = nend;

  return true;

}

#endif /* HAVE_SYNC_BUILTINS */