libgomp/loop_ull.c

   1 /* Copyright (C) 2005, 2008 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 <limits.h>
  31 #include <stdlib.h>
  32 #include "libgomp.h"
  33
  34 typedef unsigned long long gomp_ull;
  35
  36 /* Initialize the given work share construct from the given arguments.  */
  37
  38 static inline void
  39 gomp_loop_ull_init (struct gomp_work_share *ws, bool up, gomp_ull start,
  40                     gomp_ull end, gomp_ull incr, enum gomp_schedule_type sched,
  41                     gomp_ull chunk_size)
  42 {
  43   ws->sched = sched;
  44   ws->chunk_size_ull = chunk_size;
  45   /* Canonicalize loops that have zero iterations to ->next == ->end.  */
  46   ws->end_ull = ((up && start > end) || (!up && start < end))
  47                 ? start : end;
  48   ws->incr_ull = incr;
  49   ws->next_ull = start;
  50   ws->mode = 0;
  51   if (sched == GFS_DYNAMIC)
  52     {
  53       ws->chunk_size_ull *= incr;
  54
  55 #if defined HAVE_SYNC_BUILTINS && defined __LP64__
  56       {
  57         /* For dynamic scheduling prepare things to make each iteration
  58            faster.  */
  59         struct gomp_thread *thr = gomp_thread ();
  60         struct gomp_team *team = thr->ts.team;
  61         long nthreads = team ? team->nthreads : 1;
  62
  63         if (__builtin_expect (up, 1))
  64           {
  65             /* Cheap overflow protection.  */
  66             if (__builtin_expect ((nthreads | ws->chunk_size_ull)
  67                                   < 1ULL << (sizeof (gomp_ull)
  68                                              * __CHAR_BIT__ / 2 - 1), 1))
  69               ws->mode = ws->end_ull < (__LONG_LONG_MAX__ * 2ULL + 1
  70                                         - (nthreads + 1) * ws->chunk_size_ull);
  71           }
  72         /* Cheap overflow protection.  */
  73         else if (__builtin_expect ((nthreads | -ws->chunk_size_ull)
  74                                    < 1ULL << (sizeof (gomp_ull)
  75                                               * __CHAR_BIT__ / 2 - 1), 1))
  76           ws->mode = ws->end_ull > ((nthreads + 1) * -ws->chunk_size_ull
  77                                     - (__LONG_LONG_MAX__ * 2ULL + 1));
  78       }
  79 #endif
  80     }
  81   if (!up)
  82     ws->mode |= 2;
  83 }
  84
  85 /* The *_start routines are called when first encountering a loop construct
  86    that is not bound directly to a parallel construct.  The first thread
  87    that arrives will create the work-share construct; subsequent threads
  88    will see the construct exists and allocate work from it.
  89
  90    START, END, INCR are the bounds of the loop; due to the restrictions of
  91    OpenMP, these values must be the same in every thread.  This is not
  92    verified (nor is it entirely verifiable, since START is not necessarily
  93    retained intact in the work-share data structure).  CHUNK_SIZE is the
  94    scheduling parameter; again this must be identical in all threads.
  95
  96    Returns true if there's any work for this thread to perform.  If so,
  97    *ISTART and *IEND are filled with the bounds of the iteration block
  98    allocated to this thread.  Returns false if all work was assigned to
  99    other threads prior to this thread's arrival.  */
 100
 101 static bool
 102 gomp_loop_ull_static_start (bool up, gomp_ull start, gomp_ull end,
 103                             gomp_ull incr, gomp_ull chunk_size,
 104                             gomp_ull *istart, gomp_ull *iend)
 105 {
 106   struct gomp_thread *thr = gomp_thread ();
 107
 108   thr->ts.static_trip = 0;
 109   if (gomp_work_share_start (false))
 110     {
 111       gomp_loop_ull_init (thr->ts.work_share, up, start, end, incr,
 112                           GFS_STATIC, chunk_size);
 113       gomp_work_share_init_done ();
 114     }
 115
 116   return !gomp_iter_ull_static_next (istart, iend);
 117 }
 118
 119 static bool
 120 gomp_loop_ull_dynamic_start (bool up, gomp_ull start, gomp_ull end,
 121                              gomp_ull incr, gomp_ull chunk_size,
 122                              gomp_ull *istart, gomp_ull *iend)
 123 {
 124   struct gomp_thread *thr = gomp_thread ();
 125   bool ret;
 126
 127   if (gomp_work_share_start (false))
 128     {
 129       gomp_loop_ull_init (thr->ts.work_share, up, start, end, incr,
 130                           GFS_DYNAMIC, chunk_size);
 131       gomp_work_share_init_done ();
 132     }
 133
 134 #if defined HAVE_SYNC_BUILTINS && defined __LP64__
 135   ret = gomp_iter_ull_dynamic_next (istart, iend);
 136 #else
 137   gomp_mutex_lock (&thr->ts.work_share->lock);
 138   ret = gomp_iter_ull_dynamic_next_locked (istart, iend);
 139   gomp_mutex_unlock (&thr->ts.work_share->lock);
 140 #endif
 141
 142   return ret;
 143 }
 144
 145 static bool
 146 gomp_loop_ull_guided_start (bool up, gomp_ull start, gomp_ull end,
 147                             gomp_ull incr, gomp_ull chunk_size,
 148                             gomp_ull *istart, gomp_ull *iend)
 149 {
 150   struct gomp_thread *thr = gomp_thread ();
 151   bool ret;
 152
 153   if (gomp_work_share_start (false))
 154     {
 155       gomp_loop_ull_init (thr->ts.work_share, up, start, end, incr,
 156                           GFS_GUIDED, chunk_size);
 157       gomp_work_share_init_done ();
 158     }
 159
 160 #if defined HAVE_SYNC_BUILTINS && defined __LP64__
 161   ret = gomp_iter_ull_guided_next (istart, iend);
 162 #else
 163   gomp_mutex_lock (&thr->ts.work_share->lock);
 164   ret = gomp_iter_ull_guided_next_locked (istart, iend);
 165   gomp_mutex_unlock (&thr->ts.work_share->lock);
 166 #endif
 167
 168   return ret;
 169 }
 170
 171 bool
 172 GOMP_loop_ull_runtime_start (bool up, gomp_ull start, gomp_ull end,
 173                              gomp_ull incr, gomp_ull *istart, gomp_ull *iend)
 174 {
 175   struct gomp_task_icv *icv = gomp_icv (false);
 176   switch (icv->run_sched_var)
 177     {
 178     case GFS_STATIC:
 179       return gomp_loop_ull_static_start (up, start, end, incr,
 180                                          icv->run_sched_modifier,
 181                                          istart, iend);
 182     case GFS_DYNAMIC:
 183       return gomp_loop_ull_dynamic_start (up, start, end, incr,
 184                                           icv->run_sched_modifier,
 185                                           istart, iend);
 186     case GFS_GUIDED:
 187       return gomp_loop_ull_guided_start (up, start, end, incr,
 188                                          icv->run_sched_modifier,
 189                                          istart, iend);
 190     case GFS_AUTO:
 191       /* For now map to schedule(static), later on we could play with feedback
 192          driven choice.  */
 193       return gomp_loop_ull_static_start (up, start, end, incr,
 194                                          0, istart, iend);
 195     default:
 196       abort ();
 197     }
 198 }
 199
 200 /* The *_ordered_*_start routines are similar.  The only difference is that
 201    this work-share construct is initialized to expect an ORDERED section.  */
 202
 203 static bool
 204 gomp_loop_ull_ordered_static_start (bool up, gomp_ull start, gomp_ull end,
 205                                     gomp_ull incr, gomp_ull chunk_size,
 206                                     gomp_ull *istart, gomp_ull *iend)
 207 {
 208   struct gomp_thread *thr = gomp_thread ();
 209
 210   thr->ts.static_trip = 0;
 211   if (gomp_work_share_start (true))
 212     {
 213       gomp_loop_ull_init (thr->ts.work_share, up, start, end, incr,
 214                           GFS_STATIC, chunk_size);
 215       gomp_ordered_static_init ();
 216       gomp_work_share_init_done ();
 217     }
 218
 219   return !gomp_iter_ull_static_next (istart, iend);
 220 }
 221
 222 static bool
 223 gomp_loop_ull_ordered_dynamic_start (bool up, gomp_ull start, gomp_ull end,
 224                                      gomp_ull incr, gomp_ull chunk_size,
 225                                      gomp_ull *istart, gomp_ull *iend)
 226 {
 227   struct gomp_thread *thr = gomp_thread ();
 228   bool ret;
 229
 230   if (gomp_work_share_start (true))
 231     {
 232       gomp_loop_ull_init (thr->ts.work_share, up, start, end, incr,
 233                           GFS_DYNAMIC, chunk_size);
 234       gomp_mutex_lock (&thr->ts.work_share->lock);
 235       gomp_work_share_init_done ();
 236     }
 237   else
 238     gomp_mutex_lock (&thr->ts.work_share->lock);
 239
 240   ret = gomp_iter_ull_dynamic_next_locked (istart, iend);
 241   if (ret)
 242     gomp_ordered_first ();
 243   gomp_mutex_unlock (&thr->ts.work_share->lock);
 244
 245   return ret;
 246 }
 247
 248 static bool
 249 gomp_loop_ull_ordered_guided_start (bool up, gomp_ull start, gomp_ull end,
 250                                     gomp_ull incr, gomp_ull chunk_size,
 251                                     gomp_ull *istart, gomp_ull *iend)
 252 {
 253   struct gomp_thread *thr = gomp_thread ();
 254   bool ret;
 255
 256   if (gomp_work_share_start (true))
 257     {
 258       gomp_loop_ull_init (thr->ts.work_share, up, start, end, incr,
 259                           GFS_GUIDED, chunk_size);
 260       gomp_mutex_lock (&thr->ts.work_share->lock);
 261       gomp_work_share_init_done ();
 262     }
 263   else
 264     gomp_mutex_lock (&thr->ts.work_share->lock);
 265
 266   ret = gomp_iter_ull_guided_next_locked (istart, iend);
 267   if (ret)
 268     gomp_ordered_first ();
 269   gomp_mutex_unlock (&thr->ts.work_share->lock);
 270
 271   return ret;
 272 }
 273
 274 bool
 275 GOMP_loop_ull_ordered_runtime_start (bool up, gomp_ull start, gomp_ull end,
 276                                      gomp_ull incr, gomp_ull *istart,
 277                                      gomp_ull *iend)
 278 {
 279   struct gomp_task_icv *icv = gomp_icv (false);
 280   switch (icv->run_sched_var)
 281     {
 282     case GFS_STATIC:
 283       return gomp_loop_ull_ordered_static_start (up, start, end, incr,
 284                                                  icv->run_sched_modifier,
 285                                                  istart, iend);
 286     case GFS_DYNAMIC:
 287       return gomp_loop_ull_ordered_dynamic_start (up, start, end, incr,
 288                                                   icv->run_sched_modifier,
 289                                                   istart, iend);
 290     case GFS_GUIDED:
 291       return gomp_loop_ull_ordered_guided_start (up, start, end, incr,
 292                                                  icv->run_sched_modifier,
 293                                                  istart, iend);
 294     case GFS_AUTO:
 295       /* For now map to schedule(static), later on we could play with feedback
 296          driven choice.  */
 297       return gomp_loop_ull_ordered_static_start (up, start, end, incr,
 298                                                  0, istart, iend);
 299     default:
 300       abort ();
 301     }
 302 }
 303
 304 /* The *_next routines are called when the thread completes processing of
 305    the iteration block currently assigned to it.  If the work-share
 306    construct is bound directly to a parallel construct, then the iteration
 307    bounds may have been set up before the parallel.  In which case, this
 308    may be the first iteration for the thread.
 309
 310    Returns true if there is work remaining to be performed; *ISTART and
 311    *IEND are filled with a new iteration block.  Returns false if all work
 312    has been assigned.  */
 313
 314 static bool
 315 gomp_loop_ull_static_next (gomp_ull *istart, gomp_ull *iend)
 316 {
 317   return !gomp_iter_ull_static_next (istart, iend);
 318 }
 319
 320 static bool
 321 gomp_loop_ull_dynamic_next (gomp_ull *istart, gomp_ull *iend)
 322 {
 323   bool ret;
 324
 325 #if defined HAVE_SYNC_BUILTINS && defined __LP64__
 326   ret = gomp_iter_ull_dynamic_next (istart, iend);
 327 #else
 328   struct gomp_thread *thr = gomp_thread ();
 329   gomp_mutex_lock (&thr->ts.work_share->lock);
 330   ret = gomp_iter_ull_dynamic_next_locked (istart, iend);
 331   gomp_mutex_unlock (&thr->ts.work_share->lock);
 332 #endif
 333
 334   return ret;
 335 }
 336
 337 static bool
 338 gomp_loop_ull_guided_next (gomp_ull *istart, gomp_ull *iend)
 339 {
 340   bool ret;
 341
 342 #if defined HAVE_SYNC_BUILTINS && defined __LP64__
 343   ret = gomp_iter_ull_guided_next (istart, iend);
 344 #else
 345   struct gomp_thread *thr = gomp_thread ();
 346   gomp_mutex_lock (&thr->ts.work_share->lock);
 347   ret = gomp_iter_ull_guided_next_locked (istart, iend);
 348   gomp_mutex_unlock (&thr->ts.work_share->lock);
 349 #endif
 350
 351   return ret;
 352 }
 353
 354 bool
 355 GOMP_loop_ull_runtime_next (gomp_ull *istart, gomp_ull *iend)
 356 {
 357   struct gomp_thread *thr = gomp_thread ();
 358
 359   switch (thr->ts.work_share->sched)
 360     {
 361     case GFS_STATIC:
 362     case GFS_AUTO:
 363       return gomp_loop_ull_static_next (istart, iend);
 364     case GFS_DYNAMIC:
 365       return gomp_loop_ull_dynamic_next (istart, iend);
 366     case GFS_GUIDED:
 367       return gomp_loop_ull_guided_next (istart, iend);
 368     default:
 369       abort ();
 370     }
 371 }
 372
 373 /* The *_ordered_*_next routines are called when the thread completes
 374    processing of the iteration block currently assigned to it.
 375
 376    Returns true if there is work remaining to be performed; *ISTART and
 377    *IEND are filled with a new iteration block.  Returns false if all work
 378    has been assigned.  */
 379
 380 static bool
 381 gomp_loop_ull_ordered_static_next (gomp_ull *istart, gomp_ull *iend)
 382 {
 383   struct gomp_thread *thr = gomp_thread ();
 384   int test;
 385
 386   gomp_ordered_sync ();
 387   gomp_mutex_lock (&thr->ts.work_share->lock);
 388   test = gomp_iter_ull_static_next (istart, iend);
 389   if (test >= 0)
 390     gomp_ordered_static_next ();
 391   gomp_mutex_unlock (&thr->ts.work_share->lock);
 392
 393   return test == 0;
 394 }
 395
 396 static bool
 397 gomp_loop_ull_ordered_dynamic_next (gomp_ull *istart, gomp_ull *iend)
 398 {
 399   struct gomp_thread *thr = gomp_thread ();
 400   bool ret;
 401
 402   gomp_ordered_sync ();
 403   gomp_mutex_lock (&thr->ts.work_share->lock);
 404   ret = gomp_iter_ull_dynamic_next_locked (istart, iend);
 405   if (ret)
 406     gomp_ordered_next ();
 407   else
 408     gomp_ordered_last ();
 409   gomp_mutex_unlock (&thr->ts.work_share->lock);
 410
 411   return ret;
 412 }
 413
 414 static bool
 415 gomp_loop_ull_ordered_guided_next (gomp_ull *istart, gomp_ull *iend)
 416 {
 417   struct gomp_thread *thr = gomp_thread ();
 418   bool ret;
 419
 420   gomp_ordered_sync ();
 421   gomp_mutex_lock (&thr->ts.work_share->lock);
 422   ret = gomp_iter_ull_guided_next_locked (istart, iend);
 423   if (ret)
 424     gomp_ordered_next ();
 425   else
 426     gomp_ordered_last ();
 427   gomp_mutex_unlock (&thr->ts.work_share->lock);
 428
 429   return ret;
 430 }
 431
 432 bool
 433 GOMP_loop_ull_ordered_runtime_next (gomp_ull *istart, gomp_ull *iend)
 434 {
 435   struct gomp_thread *thr = gomp_thread ();
 436
 437   switch (thr->ts.work_share->sched)
 438     {
 439     case GFS_STATIC:
 440     case GFS_AUTO:
 441       return gomp_loop_ull_ordered_static_next (istart, iend);
 442     case GFS_DYNAMIC:
 443       return gomp_loop_ull_ordered_dynamic_next (istart, iend);
 444     case GFS_GUIDED:
 445       return gomp_loop_ull_ordered_guided_next (istart, iend);
 446     default:
 447       abort ();
 448     }
 449 }
 450
 451 /* We use static functions above so that we're sure that the "runtime"
 452    function can defer to the proper routine without interposition.  We
 453    export the static function with a strong alias when possible, or with
 454    a wrapper function otherwise.  */
 455
 456 #ifdef HAVE_ATTRIBUTE_ALIAS
 457 extern __typeof(gomp_loop_ull_static_start) GOMP_loop_ull_static_start
 458         __attribute__((alias ("gomp_loop_ull_static_start")));
 459 extern __typeof(gomp_loop_ull_dynamic_start) GOMP_loop_ull_dynamic_start
 460         __attribute__((alias ("gomp_loop_ull_dynamic_start")));
 461 extern __typeof(gomp_loop_ull_guided_start) GOMP_loop_ull_guided_start
 462         __attribute__((alias ("gomp_loop_ull_guided_start")));
 463
 464 extern __typeof(gomp_loop_ull_ordered_static_start) GOMP_loop_ull_ordered_static_start
 465         __attribute__((alias ("gomp_loop_ull_ordered_static_start")));
 466 extern __typeof(gomp_loop_ull_ordered_dynamic_start) GOMP_loop_ull_ordered_dynamic_start
 467         __attribute__((alias ("gomp_loop_ull_ordered_dynamic_start")));
 468 extern __typeof(gomp_loop_ull_ordered_guided_start) GOMP_loop_ull_ordered_guided_start
 469         __attribute__((alias ("gomp_loop_ull_ordered_guided_start")));
 470
 471 extern __typeof(gomp_loop_ull_static_next) GOMP_loop_ull_static_next
 472         __attribute__((alias ("gomp_loop_ull_static_next")));
 473 extern __typeof(gomp_loop_ull_dynamic_next) GOMP_loop_ull_dynamic_next
 474         __attribute__((alias ("gomp_loop_ull_dynamic_next")));
 475 extern __typeof(gomp_loop_ull_guided_next) GOMP_loop_ull_guided_next
 476         __attribute__((alias ("gomp_loop_ull_guided_next")));
 477
 478 extern __typeof(gomp_loop_ull_ordered_static_next) GOMP_loop_ull_ordered_static_next
 479         __attribute__((alias ("gomp_loop_ull_ordered_static_next")));
 480 extern __typeof(gomp_loop_ull_ordered_dynamic_next) GOMP_loop_ull_ordered_dynamic_next
 481         __attribute__((alias ("gomp_loop_ull_ordered_dynamic_next")));
 482 extern __typeof(gomp_loop_ull_ordered_guided_next) GOMP_loop_ull_ordered_guided_next
 483         __attribute__((alias ("gomp_loop_ull_ordered_guided_next")));
 484 #else
 485 bool
 486 GOMP_loop_ull_static_start (bool up, gomp_ull start, gomp_ull end,
 487                             gomp_ull incr, gomp_ull chunk_size,
 488                             gomp_ull *istart, gomp_ull *iend)
 489 {
 490   return gomp_loop_ull_static_start (up, start, end, incr, chunk_size, istart,
 491                                      iend);
 492 }
 493
 494 bool
 495 GOMP_loop_ull_dynamic_start (bool up, gomp_ull start, gomp_ull end,
 496                              gomp_ull incr, gomp_ull chunk_size,
 497                              gomp_ull *istart, gomp_ull *iend)
 498 {
 499   return gomp_loop_ull_dynamic_start (up, start, end, incr, chunk_size, istart,
 500                                       iend);
 501 }
 502
 503 bool
 504 GOMP_loop_ull_guided_start (bool up, gomp_ull start, gomp_ull end,
 505                             gomp_ull incr, gomp_ull chunk_size,
 506                             gomp_ull *istart, gomp_ull *iend)
 507 {
 508   return gomp_loop_ull_guided_start (up, start, end, incr, chunk_size, istart,
 509                                      iend);
 510 }
 511
 512 bool
 513 GOMP_loop_ull_ordered_static_start (bool up, gomp_ull start, gomp_ull end,
 514                                     gomp_ull incr, gomp_ull chunk_size,
 515                                     gomp_ull *istart, gomp_ull *iend)
 516 {
 517   return gomp_loop_ull_ordered_static_start (up, start, end, incr, chunk_size,
 518                                              istart, iend);
 519 }
 520
 521 bool
 522 GOMP_loop_ull_ordered_dynamic_start (bool up, gomp_ull start, gomp_ull end,
 523                                      gomp_ull incr, gomp_ull chunk_size,
 524                                      gomp_ull *istart, gomp_ull *iend)
 525 {
 526   return gomp_loop_ull_ordered_dynamic_start (up, start, end, incr, chunk_size,
 527                                               istart, iend);
 528 }
 529
 530 bool
 531 GOMP_loop_ull_ordered_guided_start (bool up, gomp_ull start, gomp_ull end,
 532                                     gomp_ull incr, gomp_ull chunk_size,
 533                                     gomp_ull *istart, gomp_ull *iend)
 534 {
 535   return gomp_loop_ull_ordered_guided_start (up, start, end, incr, chunk_size,
 536                                              istart, iend);
 537 }
 538
 539 bool
 540 GOMP_loop_ull_static_next (gomp_ull *istart, gomp_ull *iend)
 541 {
 542   return gomp_loop_ull_static_next (istart, iend);
 543 }
 544
 545 bool
 546 GOMP_loop_ull_dynamic_next (gomp_ull *istart, gomp_ull *iend)
 547 {
 548   return gomp_loop_ull_dynamic_next (istart, iend);
 549 }
 550
 551 bool
 552 GOMP_loop_ull_guided_next (gomp_ull *istart, gomp_ull *iend)
 553 {
 554   return gomp_loop_ull_guided_next (istart, iend);
 555 }
 556
 557 bool
 558 GOMP_loop_ull_ordered_static_next (gomp_ull *istart, gomp_ull *iend)
 559 {
 560   return gomp_loop_ull_ordered_static_next (istart, iend);
 561 }
 562
 563 bool
 564 GOMP_loop_ull_ordered_dynamic_next (gomp_ull *istart, gomp_ull *iend)
 565 {
 566   return gomp_loop_ull_ordered_dynamic_next (istart, iend);
 567 }
 568
 569 bool
 570 GOMP_loop_ull_ordered_guided_next (gomp_ull *istart, gomp_ull *iend)
 571 {
 572   return gomp_loop_ull_ordered_guided_next (istart, iend);
 573 }
 574 #endif