libgomp/iter_ull.c

   1 /* Copyright (C) 2005, 2008, 2009 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 typedef unsigned long long gomp_ull;
  32
  33 /* This function implements the STATIC scheduling method.  The caller should
  34    iterate *pstart <= x < *pend.  Return zero if there are more iterations
  35    to perform; nonzero if not.  Return less than 0 if this thread had
  36    received the absolutely last iteration.  */
  37
  38 int
  39 gomp_iter_ull_static_next (gomp_ull *pstart, gomp_ull *pend)
  40 {
  41   struct gomp_thread *thr = gomp_thread ();
  42   struct gomp_team *team = thr->ts.team;
  43   struct gomp_work_share *ws = thr->ts.work_share;
  44   unsigned long nthreads = team ? team->nthreads : 1;
  45
  46   if (thr->ts.static_trip == -1)
  47     return -1;
  48
  49   /* Quick test for degenerate teams and orphaned constructs.  */
  50   if (nthreads == 1)
  51     {
  52       *pstart = ws->next_ull;
  53       *pend = ws->end_ull;
  54       thr->ts.static_trip = -1;
  55       return ws->next_ull == ws->end_ull;
  56     }
  57
  58   /* We interpret chunk_size zero as "unspecified", which means that we
  59      should break up the iterations such that each thread makes only one
  60      trip through the outer loop.  */
  61   if (ws->chunk_size_ull == 0)
  62     {
  63       gomp_ull n, q, i, s0, e0, s, e;
  64
  65       if (thr->ts.static_trip > 0)
  66         return 1;
  67
  68       /* Compute the total number of iterations.  */
  69       if (__builtin_expect (ws->mode, 0) == 0)
  70         n = (ws->end_ull - ws->next_ull + ws->incr_ull - 1) / ws->incr_ull;
  71       else
  72         n = (ws->next_ull - ws->end_ull - ws->incr_ull - 1) / -ws->incr_ull;
  73       i = thr->ts.team_id;
  74
  75       /* Compute the "zero-based" start and end points.  That is, as
  76          if the loop began at zero and incremented by one.  */
  77       q = n / nthreads;
  78       q += (q * nthreads != n);
  79       s0 = q * i;
  80       e0 = s0 + q;
  81       if (e0 > n)
  82         e0 = n;
  83
  84       /* Notice when no iterations allocated for this thread.  */
  85       if (s0 >= e0)
  86         {
  87           thr->ts.static_trip = 1;
  88           return 1;
  89         }
  90
  91       /* Transform these to the actual start and end numbers.  */
  92       s = s0 * ws->incr_ull + ws->next_ull;
  93       e = e0 * ws->incr_ull + ws->next_ull;
  94
  95       *pstart = s;
  96       *pend = e;
  97       thr->ts.static_trip = (e0 == n ? -1 : 1);
  98       return 0;
  99     }
 100   else
 101     {
 102       gomp_ull n, s0, e0, i, c, s, e;
 103
 104       /* Otherwise, each thread gets exactly chunk_size iterations
 105          (if available) each time through the loop.  */
 106
 107       if (__builtin_expect (ws->mode, 0) == 0)
 108         n = (ws->end_ull - ws->next_ull + ws->incr_ull - 1) / ws->incr_ull;
 109       else
 110         n = (ws->next_ull - ws->end_ull - ws->incr_ull - 1) / -ws->incr_ull;
 111       i = thr->ts.team_id;
 112       c = ws->chunk_size_ull;
 113
 114       /* Initial guess is a C sized chunk positioned nthreads iterations
 115          in, offset by our thread number.  */
 116       s0 = (thr->ts.static_trip * (gomp_ull) nthreads + i) * c;
 117       e0 = s0 + c;
 118
 119       /* Detect overflow.  */
 120       if (s0 >= n)
 121         return 1;
 122       if (e0 > n)
 123         e0 = n;
 124
 125       /* Transform these to the actual start and end numbers.  */
 126       s = s0 * ws->incr_ull + ws->next_ull;
 127       e = e0 * ws->incr_ull + ws->next_ull;
 128
 129       *pstart = s;
 130       *pend = e;
 131
 132       if (e0 == n)
 133         thr->ts.static_trip = -1;
 134       else
 135         thr->ts.static_trip++;
 136       return 0;
 137     }
 138 }
 139
 140
 141 /* This function implements the DYNAMIC scheduling method.  Arguments are
 142    as for gomp_iter_ull_static_next.  This function must be called with
 143    ws->lock held.  */
 144
 145 bool
 146 gomp_iter_ull_dynamic_next_locked (gomp_ull *pstart, gomp_ull *pend)
 147 {
 148   struct gomp_thread *thr = gomp_thread ();
 149   struct gomp_work_share *ws = thr->ts.work_share;
 150   gomp_ull start, end, chunk, left;
 151
 152   start = ws->next_ull;
 153   if (start == ws->end_ull)
 154     return false;
 155
 156   chunk = ws->chunk_size_ull;
 157   left = ws->end_ull - start;
 158   if (__builtin_expect (ws->mode & 2, 0))
 159     {
 160       if (chunk < left)
 161         chunk = left;
 162     }
 163   else
 164     {
 165       if (chunk > left)
 166         chunk = left;
 167     }
 168   end = start + chunk;
 169
 170   ws->next_ull = end;
 171   *pstart = start;
 172   *pend = end;
 173   return true;
 174 }
 175
 176
 177 #if defined HAVE_SYNC_BUILTINS && defined __LP64__
 178 /* Similar, but doesn't require the lock held, and uses compare-and-swap
 179    instead.  Note that the only memory value that changes is ws->next_ull.  */
 180
 181 bool
 182 gomp_iter_ull_dynamic_next (gomp_ull *pstart, gomp_ull *pend)
 183 {
 184   struct gomp_thread *thr = gomp_thread ();
 185   struct gomp_work_share *ws = thr->ts.work_share;
 186   gomp_ull start, end, nend, chunk;
 187
 188   end = ws->end_ull;
 189   chunk = ws->chunk_size_ull;
 190
 191   if (__builtin_expect (ws->mode & 1, 1))
 192     {
 193       gomp_ull tmp = __sync_fetch_and_add (&ws->next_ull, chunk);
 194       if (__builtin_expect (ws->mode & 2, 0) == 0)
 195         {
 196           if (tmp >= end)
 197             return false;
 198           nend = tmp + chunk;
 199           if (nend > end)
 200             nend = end;
 201           *pstart = tmp;
 202           *pend = nend;
 203           return true;
 204         }
 205       else
 206         {
 207           if (tmp <= end)
 208             return false;
 209           nend = tmp + chunk;
 210           if (nend < end)
 211             nend = end;
 212           *pstart = tmp;
 213           *pend = nend;
 214           return true;
 215         }
 216     }
 217
 218   start = ws->next_ull;
 219   while (1)
 220     {
 221       gomp_ull left = end - start;
 222       gomp_ull tmp;
 223
 224       if (start == end)
 225         return false;
 226
 227       if (__builtin_expect (ws->mode & 2, 0))
 228         {
 229           if (chunk < left)
 230             chunk = left;
 231         }
 232       else
 233         {
 234           if (chunk > left)
 235             chunk = left;
 236         }
 237       nend = start + chunk;
 238
 239       tmp = __sync_val_compare_and_swap (&ws->next_ull, start, nend);
 240       if (__builtin_expect (tmp == start, 1))
 241         break;
 242
 243       start = tmp;
 244     }
 245
 246   *pstart = start;
 247   *pend = nend;
 248   return true;
 249 }
 250 #endif /* HAVE_SYNC_BUILTINS */
 251
 252
 253 /* This function implements the GUIDED scheduling method.  Arguments are
 254    as for gomp_iter_ull_static_next.  This function must be called with the
 255    work share lock held.  */
 256
 257 bool
 258 gomp_iter_ull_guided_next_locked (gomp_ull *pstart, gomp_ull *pend)
 259 {
 260   struct gomp_thread *thr = gomp_thread ();
 261   struct gomp_work_share *ws = thr->ts.work_share;
 262   struct gomp_team *team = thr->ts.team;
 263   gomp_ull nthreads = team ? team->nthreads : 1;
 264   gomp_ull n, q;
 265   gomp_ull start, end;
 266
 267   if (ws->next_ull == ws->end_ull)
 268     return false;
 269
 270   start = ws->next_ull;
 271   if (__builtin_expect (ws->mode, 0) == 0)
 272     n = (ws->end_ull - start) / ws->incr_ull;
 273   else
 274     n = (start - ws->end_ull) / -ws->incr_ull;
 275   q = (n + nthreads - 1) / nthreads;
 276
 277   if (q < ws->chunk_size_ull)
 278     q = ws->chunk_size_ull;
 279   if (q <= n)
 280     end = start + q * ws->incr_ull;
 281   else
 282     end = ws->end_ull;
 283
 284   ws->next_ull = end;
 285   *pstart = start;
 286   *pend = end;
 287   return true;
 288 }
 289
 290 #if defined HAVE_SYNC_BUILTINS && defined __LP64__
 291 /* Similar, but doesn't require the lock held, and uses compare-and-swap
 292    instead.  Note that the only memory value that changes is ws->next_ull.  */
 293
 294 bool
 295 gomp_iter_ull_guided_next (gomp_ull *pstart, gomp_ull *pend)
 296 {
 297   struct gomp_thread *thr = gomp_thread ();
 298   struct gomp_work_share *ws = thr->ts.work_share;
 299   struct gomp_team *team = thr->ts.team;
 300   gomp_ull nthreads = team ? team->nthreads : 1;
 301   gomp_ull start, end, nend, incr;
 302   gomp_ull chunk_size;
 303
 304   start = ws->next_ull;
 305   end = ws->end_ull;
 306   incr = ws->incr_ull;
 307   chunk_size = ws->chunk_size_ull;
 308
 309   while (1)
 310     {
 311       gomp_ull n, q;
 312       gomp_ull tmp;
 313
 314       if (start == end)
 315         return false;
 316
 317       if (__builtin_expect (ws->mode, 0) == 0)
 318         n = (end - start) / incr;
 319       else
 320         n = (start - end) / -incr;
 321       q = (n + nthreads - 1) / nthreads;
 322
 323       if (q < chunk_size)
 324         q = chunk_size;
 325       if (__builtin_expect (q <= n, 1))
 326         nend = start + q * incr;
 327       else
 328         nend = end;
 329
 330       tmp = __sync_val_compare_and_swap (&ws->next_ull, start, nend);
 331       if (__builtin_expect (tmp == start, 1))
 332         break;
 333
 334       start = tmp;
 335     }
 336
 337   *pstart = start;
 338   *pend = nend;
 339   return true;
 340 }
 341 #endif /* HAVE_SYNC_BUILTINS */