libgomp/iter.c

   1 /* Copyright (C) 2005, 2008, 2009, 2011 Free Software Foundation, Inc.
   2    Contributed by Richard Henderson <rth@redhat.com>.
   3
   4    This file is part of the GNU OpenMP Library (libgomp).
   5
   6    Libgomp is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3, or (at your option)
   9    any later version.
  10
  11    Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY
  12    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  13    FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  14    more details.
  15
  16    Under Section 7 of GPL version 3, you are granted additional
  17    permissions described in the GCC Runtime Library Exception, version
  18    3.1, as published by the Free Software Foundation.
  19
  20    You should have received a copy of the GNU General Public License and
  21    a copy of the GCC Runtime Library Exception along with this program;
  22    see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23    <http://www.gnu.org/licenses/>.  */
  24
  25 /* This file contains routines for managing work-share iteration, both
  26    for loops and sections.  */
  27
  28 #include "libgomp.h"
  29 #include <stdlib.h>
  30
  31
  32 /* This function implements the STATIC scheduling method.  The caller should
  33    iterate *pstart <= x < *pend.  Return zero if there are more iterations
  34    to perform; nonzero if not.  Return less than 0 if this thread had
  35    received the absolutely last iteration.  */
  36
  37 int
  38 gomp_iter_static_next (long *pstart, long *pend)
  39 {
  40   struct gomp_thread *thr = gomp_thread ();
  41   struct gomp_team *team = thr->ts.team;
  42   struct gomp_work_share *ws = thr->ts.work_share;
  43   unsigned long nthreads = team ? team->nthreads : 1;
  44
  45   if (thr->ts.static_trip == -1)
  46     return -1;
  47
  48   /* Quick test for degenerate teams and orphaned constructs.  */
  49   if (nthreads == 1)
  50     {
  51       *pstart = ws->next;
  52       *pend = ws->end;
  53       thr->ts.static_trip = -1;
  54       return ws->next == ws->end;
  55     }
  56
  57   /* We interpret chunk_size zero as "unspecified", which means that we
  58      should break up the iterations such that each thread makes only one
  59      trip through the outer loop.  */
  60   if (ws->chunk_size == 0)
  61     {
  62       unsigned long n, q, i, t;
  63       unsigned long s0, e0;
  64       long s, e;
  65
  66       if (thr->ts.static_trip > 0)
  67         return 1;
  68
  69       /* Compute the total number of iterations.  */
  70       s = ws->incr + (ws->incr > 0 ? -1 : 1);
  71       n = (ws->end - ws->next + s) / ws->incr;
  72       i = thr->ts.team_id;
  73
  74       /* Compute the "zero-based" start and end points.  That is, as
  75          if the loop began at zero and incremented by one.  */
  76       q = n / nthreads;
  77       t = n % nthreads;
  78       if (i < t)
  79         {
  80           t = 0;
  81           q++;
  82         }
  83       s0 = q * i + t;
  84       e0 = s0 + q;
  85
  86       /* Notice when no iterations allocated for this thread.  */
  87       if (s0 >= e0)
  88         {
  89           thr->ts.static_trip = 1;
  90           return 1;
  91         }
  92
  93       /* Transform these to the actual start and end numbers.  */
  94       s = (long)s0 * ws->incr + ws->next;
  95       e = (long)e0 * ws->incr + ws->next;
  96
  97       *pstart = s;
  98       *pend = e;
  99       thr->ts.static_trip = (e0 == n ? -1 : 1);
 100       return 0;
 101     }
 102   else
 103     {
 104       unsigned long n, s0, e0, i, c;
 105       long s, e;
 106
 107       /* Otherwise, each thread gets exactly chunk_size iterations
 108          (if available) each time through the loop.  */
 109
 110       s = ws->incr + (ws->incr > 0 ? -1 : 1);
 111       n = (ws->end - ws->next + s) / ws->incr;
 112       i = thr->ts.team_id;
 113       c = ws->chunk_size;
 114
 115       /* Initial guess is a C sized chunk positioned nthreads iterations
 116          in, offset by our thread number.  */
 117       s0 = (thr->ts.static_trip * nthreads + i) * c;
 118       e0 = s0 + c;
 119
 120       /* Detect overflow.  */
 121       if (s0 >= n)
 122         return 1;
 123       if (e0 > n)
 124         e0 = n;
 125
 126       /* Transform these to the actual start and end numbers.  */
 127       s = (long)s0 * ws->incr + ws->next;
 128       e = (long)e0 * ws->incr + ws->next;
 129
 130       *pstart = s;
 131       *pend = e;
 132
 133       if (e0 == n)
 134         thr->ts.static_trip = -1;
 135       else
 136         thr->ts.static_trip++;
 137       return 0;
 138     }
 139 }
 140
 141
 142 /* This function implements the DYNAMIC scheduling method.  Arguments are
 143    as for gomp_iter_static_next.  This function must be called with ws->lock
 144    held.  */
 145
 146 bool
 147 gomp_iter_dynamic_next_locked (long *pstart, long *pend)
 148 {
 149   struct gomp_thread *thr = gomp_thread ();
 150   struct gomp_work_share *ws = thr->ts.work_share;
 151   long start, end, chunk, left;
 152
 153   start = ws->next;
 154   if (start == ws->end)
 155     return false;
 156
 157   chunk = ws->chunk_size;
 158   left = ws->end - start;
 159   if (ws->incr < 0)
 160     {
 161       if (chunk < left)
 162         chunk = left;
 163     }
 164   else
 165     {
 166       if (chunk > left)
 167         chunk = left;
 168     }
 169   end = start + chunk;
 170
 171   ws->next = end;
 172   *pstart = start;
 173   *pend = end;
 174   return true;
 175 }
 176
 177
 178 #ifdef HAVE_SYNC_BUILTINS
 179 /* Similar, but doesn't require the lock held, and uses compare-and-swap
 180    instead.  Note that the only memory value that changes is ws->next.  */
 181
 182 bool
 183 gomp_iter_dynamic_next (long *pstart, long *pend)
 184 {
 185   struct gomp_thread *thr = gomp_thread ();
 186   struct gomp_work_share *ws = thr->ts.work_share;
 187   long start, end, nend, chunk, incr;
 188
 189   end = ws->end;
 190   incr = ws->incr;
 191   chunk = ws->chunk_size;
 192
 193   if (__builtin_expect (ws->mode, 1))
 194     {
 195       long tmp = __sync_fetch_and_add (&ws->next, chunk);
 196       if (incr > 0)
 197         {
 198           if (tmp >= end)
 199             return false;
 200           nend = tmp + chunk;
 201           if (nend > end)
 202             nend = end;
 203           *pstart = tmp;
 204           *pend = nend;
 205           return true;
 206         }
 207       else
 208         {
 209           if (tmp <= end)
 210             return false;
 211           nend = tmp + chunk;
 212           if (nend < end)
 213             nend = end;
 214           *pstart = tmp;
 215           *pend = nend;
 216           return true;
 217         }
 218     }
 219
 220   start = ws->next;
 221   while (1)
 222     {
 223       long left = end - start;
 224       long tmp;
 225
 226       if (start == end)
 227         return false;
 228
 229       if (incr < 0)
 230         {
 231           if (chunk < left)
 232             chunk = left;
 233         }
 234       else
 235         {
 236           if (chunk > left)
 237             chunk = left;
 238         }
 239       nend = start + chunk;
 240
 241       tmp = __sync_val_compare_and_swap (&ws->next, start, nend);
 242       if (__builtin_expect (tmp == start, 1))
 243         break;
 244
 245       start = tmp;
 246     }
 247
 248   *pstart = start;
 249   *pend = nend;
 250   return true;
 251 }
 252 #endif /* HAVE_SYNC_BUILTINS */
 253
 254
 255 /* This function implements the GUIDED scheduling method.  Arguments are
 256    as for gomp_iter_static_next.  This function must be called with the
 257    work share lock held.  */
 258
 259 bool
 260 gomp_iter_guided_next_locked (long *pstart, long *pend)
 261 {
 262   struct gomp_thread *thr = gomp_thread ();
 263   struct gomp_work_share *ws = thr->ts.work_share;
 264   struct gomp_team *team = thr->ts.team;
 265   unsigned long nthreads = team ? team->nthreads : 1;
 266   unsigned long n, q;
 267   long start, end;
 268
 269   if (ws->next == ws->end)
 270     return false;
 271
 272   start = ws->next;
 273   n = (ws->end - start) / ws->incr;
 274   q = (n + nthreads - 1) / nthreads;
 275
 276   if (q < ws->chunk_size)
 277     q = ws->chunk_size;
 278   if (q <= n)
 279     end = start + q * ws->incr;
 280   else
 281     end = ws->end;
 282
 283   ws->next = end;
 284   *pstart = start;
 285   *pend = end;
 286   return true;
 287 }
 288
 289 #ifdef HAVE_SYNC_BUILTINS
 290 /* Similar, but doesn't require the lock held, and uses compare-and-swap
 291    instead.  Note that the only memory value that changes is ws->next.  */
 292
 293 bool
 294 gomp_iter_guided_next (long *pstart, long *pend)
 295 {
 296   struct gomp_thread *thr = gomp_thread ();
 297   struct gomp_work_share *ws = thr->ts.work_share;
 298   struct gomp_team *team = thr->ts.team;
 299   unsigned long nthreads = team ? team->nthreads : 1;
 300   long start, end, nend, incr;
 301   unsigned long chunk_size;
 302
 303   start = ws->next;
 304   end = ws->end;
 305   incr = ws->incr;
 306   chunk_size = ws->chunk_size;
 307
 308   while (1)
 309     {
 310       unsigned long n, q;
 311       long tmp;
 312
 313       if (start == end)
 314         return false;
 315
 316       n = (end - start) / incr;
 317       q = (n + nthreads - 1) / nthreads;
 318
 319       if (q < chunk_size)
 320         q = chunk_size;
 321       if (__builtin_expect (q <= n, 1))
 322         nend = start + q * incr;
 323       else
 324         nend = end;
 325
 326       tmp = __sync_val_compare_and_swap (&ws->next, start, nend);
 327       if (__builtin_expect (tmp == start, 1))
 328         break;
 329
 330       start = tmp;
 331     }
 332
 333   *pstart = start;
 334   *pend = nend;
 335   return true;
 336 }
 337 #endif /* HAVE_SYNC_BUILTINS */