libgomp/loop.c

   1 /* Copyright (C) 2005 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 Lesser General Public License as published by
   8    the Free Software Foundation; either version 2.1 of the License, or
   9    (at your option) 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 Lesser General Public License for
  14    more details.
  15
  16    You should have received a copy of the GNU Lesser General Public License
  17    along with libgomp; see the file COPYING.LIB.  If not, write to the
  18    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  19    MA 02110-1301, USA.  */
  20
  21 /* As a special exception, if you link this library with other files, some
  22    of which are compiled with GCC, to produce an executable, this library
  23    does not by itself cause the resulting executable to be covered by the
  24    GNU General Public License.  This exception does not however invalidate
  25    any other reasons why the executable file might be covered by the GNU
  26    General Public License.  */
  27
  28 /* This file handles the LOOP (FOR/DO) construct.  */
  29
  30 #include "libgomp.h"
  31 #include <stdlib.h>
  32
  33
  34 /* Initialize the given work share construct from the given arguments.  */
  35
  36 static inline void
  37 gomp_loop_init (struct gomp_work_share *ws, long start, long end, long incr,
  38                 enum gomp_schedule_type sched, long chunk_size)
  39 {
  40   ws->sched = sched;
  41   ws->chunk_size = chunk_size;
  42   /* Canonicalize loops that have zero iterations to ->next == ->end.  */
  43   ws->end = ((incr > 0 && start > end) || (incr < 0 && start < end))
  44             ? start : end;
  45   ws->incr = incr;
  46   ws->next = start;
  47 }
  48
  49 /* The *_start routines are called when first encountering a loop construct
  50    that is not bound directly to a parallel construct.  The first thread
  51    that arrives will create the work-share construct; subsequent threads
  52    will see the construct exists and allocate work from it.
  53
  54    START, END, INCR are the bounds of the loop; due to the restrictions of
  55    OpenMP, these values must be the same in every thread.  This is not
  56    verified (nor is it entirely verifiable, since START is not necessarily
  57    retained intact in the work-share data structure).  CHUNK_SIZE is the
  58    scheduling parameter; again this must be identical in all threads.
  59
  60    Returns true if there's any work for this thread to perform.  If so,
  61    *ISTART and *IEND are filled with the bounds of the iteration block
  62    allocated to this thread.  Returns false if all work was assigned to
  63    other threads prior to this thread's arrival.  */
  64
  65 static bool
  66 gomp_loop_static_start (long start, long end, long incr, long chunk_size,
  67                         long *istart, long *iend)
  68 {
  69   struct gomp_thread *thr = gomp_thread ();
  70
  71   if (gomp_work_share_start (false))
  72     gomp_loop_init (thr->ts.work_share, start, end, incr,
  73                     GFS_STATIC, chunk_size);
  74   gomp_mutex_unlock (&thr->ts.work_share->lock);
  75
  76   return !gomp_iter_static_next (istart, iend);
  77 }
  78
  79 static bool
  80 gomp_loop_dynamic_start (long start, long end, long incr, long chunk_size,
  81                          long *istart, long *iend)
  82 {
  83   struct gomp_thread *thr = gomp_thread ();
  84   bool ret;
  85
  86   if (gomp_work_share_start (false))
  87     gomp_loop_init (thr->ts.work_share, start, end, incr,
  88                     GFS_DYNAMIC, chunk_size);
  89
  90 #ifdef HAVE_SYNC_BUILTINS
  91   gomp_mutex_unlock (&thr->ts.work_share->lock);
  92   ret = gomp_iter_dynamic_next (istart, iend);
  93 #else
  94   ret = gomp_iter_dynamic_next_locked (istart, iend);
  95   gomp_mutex_unlock (&thr->ts.work_share->lock);
  96 #endif
  97
  98   return ret;
  99 }
 100
 101 static bool
 102 gomp_loop_guided_start (long start, long end, long incr, long chunk_size,
 103                         long *istart, long *iend)
 104 {
 105   struct gomp_thread *thr = gomp_thread ();
 106   bool ret;
 107
 108   if (gomp_work_share_start (false))
 109     gomp_loop_init (thr->ts.work_share, start, end, incr,
 110                     GFS_GUIDED, chunk_size);
 111
 112 #ifdef HAVE_SYNC_BUILTINS
 113   gomp_mutex_unlock (&thr->ts.work_share->lock);
 114   ret = gomp_iter_guided_next (istart, iend);
 115 #else
 116   ret = gomp_iter_guided_next_locked (istart, iend);
 117   gomp_mutex_unlock (&thr->ts.work_share->lock);
 118 #endif
 119
 120   return ret;
 121 }
 122
 123 bool
 124 GOMP_loop_runtime_start (long start, long end, long incr,
 125                          long *istart, long *iend)
 126 {
 127   switch (gomp_run_sched_var)
 128     {
 129     case GFS_STATIC:
 130       return gomp_loop_static_start (start, end, incr, gomp_run_sched_chunk,
 131                                      istart, iend);
 132     case GFS_DYNAMIC:
 133       return gomp_loop_dynamic_start (start, end, incr, gomp_run_sched_chunk,
 134                                       istart, iend);
 135     case GFS_GUIDED:
 136       return gomp_loop_guided_start (start, end, incr, gomp_run_sched_chunk,
 137                                      istart, iend);
 138     default:
 139       abort ();
 140     }
 141 }
 142
 143 /* The *_ordered_*_start routines are similar.  The only difference is that
 144    this work-share construct is initialized to expect an ORDERED section.  */
 145
 146 static bool
 147 gomp_loop_ordered_static_start (long start, long end, long incr,
 148                                 long chunk_size, long *istart, long *iend)
 149 {
 150   struct gomp_thread *thr = gomp_thread ();
 151
 152   if (gomp_work_share_start (true))
 153     {
 154       gomp_loop_init (thr->ts.work_share, start, end, incr,
 155                       GFS_STATIC, chunk_size);
 156       gomp_ordered_static_init ();
 157     }
 158   gomp_mutex_unlock (&thr->ts.work_share->lock);
 159
 160   return !gomp_iter_static_next (istart, iend);
 161 }
 162
 163 static bool
 164 gomp_loop_ordered_dynamic_start (long start, long end, long incr,
 165                                  long chunk_size, long *istart, long *iend)
 166 {
 167   struct gomp_thread *thr = gomp_thread ();
 168   bool ret;
 169
 170   if (gomp_work_share_start (true))
 171     gomp_loop_init (thr->ts.work_share, start, end, incr,
 172                     GFS_DYNAMIC, chunk_size);
 173
 174   ret = gomp_iter_dynamic_next_locked (istart, iend);
 175   if (ret)
 176     gomp_ordered_first ();
 177   gomp_mutex_unlock (&thr->ts.work_share->lock);
 178
 179   return ret;
 180 }
 181
 182 static bool
 183 gomp_loop_ordered_guided_start (long start, long end, long incr,
 184                                 long chunk_size, long *istart, long *iend)
 185 {
 186   struct gomp_thread *thr = gomp_thread ();
 187   bool ret;
 188
 189   if (gomp_work_share_start (true))
 190     gomp_loop_init (thr->ts.work_share, start, end, incr,
 191                     GFS_GUIDED, chunk_size);
 192
 193   ret = gomp_iter_guided_next_locked (istart, iend);
 194   if (ret)
 195     gomp_ordered_first ();
 196   gomp_mutex_unlock (&thr->ts.work_share->lock);
 197
 198   return ret;
 199 }
 200
 201 bool
 202 GOMP_loop_ordered_runtime_start (long start, long end, long incr,
 203                                  long *istart, long *iend)
 204 {
 205   switch (gomp_run_sched_var)
 206     {
 207     case GFS_STATIC:
 208       return gomp_loop_ordered_static_start (start, end, incr,
 209                                              gomp_run_sched_chunk,
 210                                              istart, iend);
 211     case GFS_DYNAMIC:
 212       return gomp_loop_ordered_dynamic_start (start, end, incr,
 213                                               gomp_run_sched_chunk,
 214                                               istart, iend);
 215     case GFS_GUIDED:
 216       return gomp_loop_ordered_guided_start (start, end, incr,
 217                                              gomp_run_sched_chunk,
 218                                              istart, iend);
 219     default:
 220       abort ();
 221     }
 222 }
 223
 224 /* The *_next routines are called when the thread completes processing of
 225    the iteration block currently assigned to it.  If the work-share
 226    construct is bound directly to a parallel construct, then the iteration
 227    bounds may have been set up before the parallel.  In which case, this
 228    may be the first iteration for the thread.
 229
 230    Returns true if there is work remaining to be performed; *ISTART and
 231    *IEND are filled with a new iteration block.  Returns false if all work
 232    has been assigned.  */
 233
 234 static bool
 235 gomp_loop_static_next (long *istart, long *iend)
 236 {
 237   return !gomp_iter_static_next (istart, iend);
 238 }
 239
 240 static bool
 241 gomp_loop_dynamic_next (long *istart, long *iend)
 242 {
 243   bool ret;
 244
 245 #ifdef HAVE_SYNC_BUILTINS
 246   ret = gomp_iter_dynamic_next (istart, iend);
 247 #else
 248   struct gomp_thread *thr = gomp_thread ();
 249   gomp_mutex_lock (&thr->ts.work_share->lock);
 250   ret = gomp_iter_dynamic_next_locked (istart, iend);
 251   gomp_mutex_unlock (&thr->ts.work_share->lock);
 252 #endif
 253
 254   return ret;
 255 }
 256
 257 static bool
 258 gomp_loop_guided_next (long *istart, long *iend)
 259 {
 260   bool ret;
 261
 262 #ifdef HAVE_SYNC_BUILTINS
 263   ret = gomp_iter_guided_next (istart, iend);
 264 #else
 265   struct gomp_thread *thr = gomp_thread ();
 266   gomp_mutex_lock (&thr->ts.work_share->lock);
 267   ret = gomp_iter_guided_next_locked (istart, iend);
 268   gomp_mutex_unlock (&thr->ts.work_share->lock);
 269 #endif
 270
 271   return ret;
 272 }
 273
 274 bool
 275 GOMP_loop_runtime_next (long *istart, long *iend)
 276 {
 277   struct gomp_thread *thr = gomp_thread ();
 278
 279   switch (thr->ts.work_share->sched)
 280     {
 281     case GFS_STATIC:
 282       return gomp_loop_static_next (istart, iend);
 283     case GFS_DYNAMIC:
 284       return gomp_loop_dynamic_next (istart, iend);
 285     case GFS_GUIDED:
 286       return gomp_loop_guided_next (istart, iend);
 287     default:
 288       abort ();
 289     }
 290 }
 291
 292 /* The *_ordered_*_next routines are called when the thread completes
 293    processing of the iteration block currently assigned to it.
 294
 295    Returns true if there is work remaining to be performed; *ISTART and
 296    *IEND are filled with a new iteration block.  Returns false if all work
 297    has been assigned.  */
 298
 299 static bool
 300 gomp_loop_ordered_static_next (long *istart, long *iend)
 301 {
 302   struct gomp_thread *thr = gomp_thread ();
 303   int test;
 304
 305   gomp_ordered_sync ();
 306   gomp_mutex_lock (&thr->ts.work_share->lock);
 307   test = gomp_iter_static_next (istart, iend);
 308   if (test >= 0)
 309     gomp_ordered_static_next ();
 310   gomp_mutex_unlock (&thr->ts.work_share->lock);
 311
 312   return test == 0;
 313 }
 314
 315 static bool
 316 gomp_loop_ordered_dynamic_next (long *istart, long *iend)
 317 {
 318   struct gomp_thread *thr = gomp_thread ();
 319   bool ret;
 320
 321   gomp_ordered_sync ();
 322   gomp_mutex_lock (&thr->ts.work_share->lock);
 323   ret = gomp_iter_dynamic_next_locked (istart, iend);
 324   if (ret)
 325     gomp_ordered_next ();
 326   else
 327     gomp_ordered_last ();
 328   gomp_mutex_unlock (&thr->ts.work_share->lock);
 329
 330   return ret;
 331 }
 332
 333 static bool
 334 gomp_loop_ordered_guided_next (long *istart, long *iend)
 335 {
 336   struct gomp_thread *thr = gomp_thread ();
 337   bool ret;
 338
 339   gomp_ordered_sync ();
 340   gomp_mutex_lock (&thr->ts.work_share->lock);
 341   ret = gomp_iter_guided_next_locked (istart, iend);
 342   if (ret)
 343     gomp_ordered_next ();
 344   else
 345     gomp_ordered_last ();
 346   gomp_mutex_unlock (&thr->ts.work_share->lock);
 347
 348   return ret;
 349 }
 350
 351 bool
 352 GOMP_loop_ordered_runtime_next (long *istart, long *iend)
 353 {
 354   struct gomp_thread *thr = gomp_thread ();
 355
 356   switch (thr->ts.work_share->sched)
 357     {
 358     case GFS_STATIC:
 359       return gomp_loop_ordered_static_next (istart, iend);
 360     case GFS_DYNAMIC:
 361       return gomp_loop_ordered_dynamic_next (istart, iend);
 362     case GFS_GUIDED:
 363       return gomp_loop_ordered_guided_next (istart, iend);
 364     default:
 365       abort ();
 366     }
 367 }
 368
 369 /* The GOMP_parallel_loop_* routines pre-initialize a work-share construct
 370    to avoid one synchronization once we get into the loop.  */
 371
 372 static void
 373 gomp_parallel_loop_start (void (*fn) (void *), void *data,
 374                           unsigned num_threads, long start, long end,
 375                           long incr, enum gomp_schedule_type sched,
 376                           long chunk_size)
 377 {
 378   struct gomp_work_share *ws;
 379
 380   num_threads = gomp_resolve_num_threads (num_threads);
 381   ws = gomp_new_work_share (false, num_threads);
 382   gomp_loop_init (ws, start, end, incr, sched, chunk_size);
 383   gomp_team_start (fn, data, num_threads, ws);
 384 }
 385
 386 void
 387 GOMP_parallel_loop_static_start (void (*fn) (void *), void *data,
 388                                  unsigned num_threads, long start, long end,
 389                                  long incr, long chunk_size)
 390 {
 391   gomp_parallel_loop_start (fn, data, num_threads, start, end, incr,
 392                             GFS_STATIC, chunk_size);
 393 }
 394
 395 void
 396 GOMP_parallel_loop_dynamic_start (void (*fn) (void *), void *data,
 397                                   unsigned num_threads, long start, long end,
 398                                   long incr, long chunk_size)
 399 {
 400   gomp_parallel_loop_start (fn, data, num_threads, start, end, incr,
 401                             GFS_DYNAMIC, chunk_size);
 402 }
 403
 404 void
 405 GOMP_parallel_loop_guided_start (void (*fn) (void *), void *data,
 406                                  unsigned num_threads, long start, long end,
 407                                  long incr, long chunk_size)
 408 {
 409   gomp_parallel_loop_start (fn, data, num_threads, start, end, incr,
 410                             GFS_GUIDED, chunk_size);
 411 }
 412
 413 void
 414 GOMP_parallel_loop_runtime_start (void (*fn) (void *), void *data,
 415                                   unsigned num_threads, long start, long end,
 416                                   long incr)
 417 {
 418   gomp_parallel_loop_start (fn, data, num_threads, start, end, incr,
 419                             gomp_run_sched_var, gomp_run_sched_chunk);
 420 }
 421
 422 /* The GOMP_loop_end* routines are called after the thread is told that
 423    all loop iterations are complete.  This first version synchronizes
 424    all threads; the nowait version does not.  */
 425
 426 void
 427 GOMP_loop_end (void)
 428 {
 429   gomp_work_share_end ();
 430 }
 431
 432 void
 433 GOMP_loop_end_nowait (void)
 434 {
 435   gomp_work_share_end_nowait ();
 436 }
 437
 438
 439 /* We use static functions above so that we're sure that the "runtime"
 440    function can defer to the proper routine without interposition.  We
 441    export the static function with a strong alias when possible, or with
 442    a wrapper function otherwise.  */
 443
 444 #ifdef HAVE_ATTRIBUTE_ALIAS
 445 extern __typeof(gomp_loop_static_start) GOMP_loop_static_start
 446         __attribute__((alias ("gomp_loop_static_start")));
 447 extern __typeof(gomp_loop_dynamic_start) GOMP_loop_dynamic_start
 448         __attribute__((alias ("gomp_loop_dynamic_start")));
 449 extern __typeof(gomp_loop_guided_start) GOMP_loop_guided_start
 450         __attribute__((alias ("gomp_loop_guided_start")));
 451
 452 extern __typeof(gomp_loop_ordered_static_start) GOMP_loop_ordered_static_start
 453         __attribute__((alias ("gomp_loop_ordered_static_start")));
 454 extern __typeof(gomp_loop_ordered_dynamic_start) GOMP_loop_ordered_dynamic_start
 455         __attribute__((alias ("gomp_loop_ordered_dynamic_start")));
 456 extern __typeof(gomp_loop_ordered_guided_start) GOMP_loop_ordered_guided_start
 457         __attribute__((alias ("gomp_loop_ordered_guided_start")));
 458
 459 extern __typeof(gomp_loop_static_next) GOMP_loop_static_next
 460         __attribute__((alias ("gomp_loop_static_next")));
 461 extern __typeof(gomp_loop_dynamic_next) GOMP_loop_dynamic_next
 462         __attribute__((alias ("gomp_loop_dynamic_next")));
 463 extern __typeof(gomp_loop_guided_next) GOMP_loop_guided_next
 464         __attribute__((alias ("gomp_loop_guided_next")));
 465
 466 extern __typeof(gomp_loop_ordered_static_next) GOMP_loop_ordered_static_next
 467         __attribute__((alias ("gomp_loop_ordered_static_next")));
 468 extern __typeof(gomp_loop_ordered_dynamic_next) GOMP_loop_ordered_dynamic_next
 469         __attribute__((alias ("gomp_loop_ordered_dynamic_next")));
 470 extern __typeof(gomp_loop_ordered_guided_next) GOMP_loop_ordered_guided_next
 471         __attribute__((alias ("gomp_loop_ordered_guided_next")));
 472 #else
 473 bool
 474 GOMP_loop_static_start (long start, long end, long incr, long chunk_size,
 475                         long *istart, long *iend)
 476 {
 477   return gomp_loop_static_start (start, end, incr, chunk_size, istart, iend);
 478 }
 479
 480 bool
 481 GOMP_loop_dynamic_start (long start, long end, long incr, long chunk_size,
 482                          long *istart, long *iend)
 483 {
 484   return gomp_loop_dynamic_start (start, end, incr, chunk_size, istart, iend);
 485 }
 486
 487 bool
 488 GOMP_loop_guided_start (long start, long end, long incr, long chunk_size,
 489                         long *istart, long *iend)
 490 {
 491   return gomp_loop_guided_start (start, end, incr, chunk_size, istart, iend);
 492 }
 493
 494 bool
 495 GOMP_loop_ordered_static_start (long start, long end, long incr,
 496                                 long chunk_size, long *istart, long *iend)
 497 {
 498   return gomp_loop_ordered_static_start (start, end, incr, chunk_size,
 499                                          istart, iend);
 500 }
 501
 502 bool
 503 GOMP_loop_ordered_dynamic_start (long start, long end, long incr,
 504                                  long chunk_size, long *istart, long *iend)
 505 {
 506   return gomp_loop_ordered_dynamic_start (start, end, incr, chunk_size,
 507                                           istart, iend);
 508 }
 509
 510 bool
 511 GOMP_loop_ordered_guided_start (long start, long end, long incr,
 512                                 long chunk_size, long *istart, long *iend)
 513 {
 514   return gomp_loop_ordered_guided_start (start, end, incr, chunk_size,
 515                                          istart, iend);
 516 }
 517
 518 bool
 519 GOMP_loop_static_next (long *istart, long *iend)
 520 {
 521   return gomp_loop_static_next (istart, iend);
 522 }
 523
 524 bool
 525 GOMP_loop_dynamic_next (long *istart, long *iend)
 526 {
 527   return gomp_loop_dynamic_next (istart, iend);
 528 }
 529
 530 bool
 531 GOMP_loop_guided_next (long *istart, long *iend)
 532 {
 533   return gomp_loop_guided_next (istart, iend);
 534 }
 535
 536 bool
 537 GOMP_loop_ordered_static_next (long *istart, long *iend)
 538 {
 539   return gomp_loop_ordered_static_next (istart, iend);
 540 }
 541
 542 bool
 543 GOMP_loop_ordered_dynamic_next (long *istart, long *iend)
 544 {
 545   return gomp_loop_ordered_dynamic_next (istart, iend);
 546 }
 547
 548 bool
 549 GOMP_loop_ordered_guided_next (long *istart, long *iend)
 550 {
 551   return gomp_loop_ordered_guided_next (istart, iend);
 552 }
 553 #endif