OSDN Git Service

* double-int.h (tree_to_double_int): Remove macro.
[pf3gnuchains/gcc-fork.git] / libgomp / loop.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 handles the LOOP (FOR/DO) construct.  */
26
27 #include <limits.h>
28 #include <stdlib.h>
29 #include "libgomp.h"
30
31
32 /* Initialize the given work share construct from the given arguments.  */
33
34 static inline void
35 gomp_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
96 static bool
97 gomp_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
113 static bool
114 gomp_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
138 static bool
139 gomp_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
163 bool
164 GOMP_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
191 static bool
192 gomp_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
209 static bool
210 gomp_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
234 static bool
235 gomp_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
259 bool
260 GOMP_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
298 static bool
299 gomp_loop_static_next (long *istart, long *iend)
300 {
301   return !gomp_iter_static_next (istart, iend);
302 }
303
304 static bool
305 gomp_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
321 static bool
322 gomp_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
338 bool
339 GOMP_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
364 static bool
365 gomp_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
380 static bool
381 gomp_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
398 static bool
399 gomp_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
416 bool
417 GOMP_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
438 static void
439 gomp_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
452 void
453 GOMP_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
461 void
462 GOMP_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
470 void
471 GOMP_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
479 void
480 GOMP_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
493 void
494 GOMP_loop_end (void)
495 {
496   gomp_work_share_end ();
497 }
498
499 void
500 GOMP_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
512 extern __typeof(gomp_loop_static_start) GOMP_loop_static_start
513         __attribute__((alias ("gomp_loop_static_start")));
514 extern __typeof(gomp_loop_dynamic_start) GOMP_loop_dynamic_start
515         __attribute__((alias ("gomp_loop_dynamic_start")));
516 extern __typeof(gomp_loop_guided_start) GOMP_loop_guided_start
517         __attribute__((alias ("gomp_loop_guided_start")));
518
519 extern __typeof(gomp_loop_ordered_static_start) GOMP_loop_ordered_static_start
520         __attribute__((alias ("gomp_loop_ordered_static_start")));
521 extern __typeof(gomp_loop_ordered_dynamic_start) GOMP_loop_ordered_dynamic_start
522         __attribute__((alias ("gomp_loop_ordered_dynamic_start")));
523 extern __typeof(gomp_loop_ordered_guided_start) GOMP_loop_ordered_guided_start
524         __attribute__((alias ("gomp_loop_ordered_guided_start")));
525
526 extern __typeof(gomp_loop_static_next) GOMP_loop_static_next
527         __attribute__((alias ("gomp_loop_static_next")));
528 extern __typeof(gomp_loop_dynamic_next) GOMP_loop_dynamic_next
529         __attribute__((alias ("gomp_loop_dynamic_next")));
530 extern __typeof(gomp_loop_guided_next) GOMP_loop_guided_next
531         __attribute__((alias ("gomp_loop_guided_next")));
532
533 extern __typeof(gomp_loop_ordered_static_next) GOMP_loop_ordered_static_next
534         __attribute__((alias ("gomp_loop_ordered_static_next")));
535 extern __typeof(gomp_loop_ordered_dynamic_next) GOMP_loop_ordered_dynamic_next
536         __attribute__((alias ("gomp_loop_ordered_dynamic_next")));
537 extern __typeof(gomp_loop_ordered_guided_next) GOMP_loop_ordered_guided_next
538         __attribute__((alias ("gomp_loop_ordered_guided_next")));
539 #else
540 bool
541 GOMP_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
547 bool
548 GOMP_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
554 bool
555 GOMP_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
561 bool
562 GOMP_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
569 bool
570 GOMP_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
577 bool
578 GOMP_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
585 bool
586 GOMP_loop_static_next (long *istart, long *iend)
587 {
588   return gomp_loop_static_next (istart, iend);
589 }
590
591 bool
592 GOMP_loop_dynamic_next (long *istart, long *iend)
593 {
594   return gomp_loop_dynamic_next (istart, iend);
595 }
596
597 bool
598 GOMP_loop_guided_next (long *istart, long *iend)
599 {
600   return gomp_loop_guided_next (istart, iend);
601 }
602
603 bool
604 GOMP_loop_ordered_static_next (long *istart, long *iend)
605 {
606   return gomp_loop_ordered_static_next (istart, iend);
607 }
608
609 bool
610 GOMP_loop_ordered_dynamic_next (long *istart, long *iend)
611 {
612   return gomp_loop_ordered_dynamic_next (istart, iend);
613 }
614
615 bool
616 GOMP_loop_ordered_guided_next (long *istart, long *iend)
617 {
618   return gomp_loop_ordered_guided_next (istart, iend);
619 }
620 #endif