OSDN Git Service

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