source: trunk/sys/libgomp/loop.c @ 242

Last change on this file since 242 was 1, checked in by alain, 8 years ago

First import

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