OSDN Git Service

* c-cppbuiltin.c (c_cpp_builtins): Change _OPENMP value to
[pf3gnuchains/gcc-fork.git] / 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 (gomp_ull start, gomp_ull end, gomp_ull incr, gomp_ull chunk_size,
487                         gomp_ull *istart, gomp_ull *iend)
488 {
489   return gomp_loop_ull_static_start (start, end, incr, chunk_size, istart, iend);
490 }
491
492 bool
493 GOMP_loop_ull_dynamic_start (gomp_ull start, gomp_ull end, gomp_ull incr, gomp_ull chunk_size,
494                          gomp_ull *istart, gomp_ull *iend)
495 {
496   return gomp_loop_ull_dynamic_start (start, end, incr, chunk_size, istart, iend);
497 }
498
499 bool
500 GOMP_loop_ull_guided_start (gomp_ull start, gomp_ull end, gomp_ull incr, gomp_ull chunk_size,
501                         gomp_ull *istart, gomp_ull *iend)
502 {
503   return gomp_loop_ull_guided_start (start, end, incr, chunk_size, istart, iend);
504 }
505
506 bool
507 GOMP_loop_ull_ordered_static_start (gomp_ull start, gomp_ull end, gomp_ull incr,
508                                 gomp_ull chunk_size, gomp_ull *istart, gomp_ull *iend)
509 {
510   return gomp_loop_ull_ordered_static_start (start, end, incr, chunk_size,
511                                          istart, iend);
512 }
513
514 bool
515 GOMP_loop_ull_ordered_dynamic_start (gomp_ull start, gomp_ull end, gomp_ull incr,
516                                  gomp_ull chunk_size, gomp_ull *istart, gomp_ull *iend)
517 {
518   return gomp_loop_ull_ordered_dynamic_start (start, end, incr, chunk_size,
519                                           istart, iend);
520 }
521
522 bool
523 GOMP_loop_ull_ordered_guided_start (gomp_ull start, gomp_ull end, gomp_ull incr,
524                                 gomp_ull chunk_size, gomp_ull *istart, gomp_ull *iend)
525 {
526   return gomp_loop_ull_ordered_guided_start (start, end, incr, chunk_size,
527                                          istart, iend);
528 }
529
530 bool
531 GOMP_loop_ull_static_next (gomp_ull *istart, gomp_ull *iend)
532 {
533   return gomp_loop_ull_static_next (istart, iend);
534 }
535
536 bool
537 GOMP_loop_ull_dynamic_next (gomp_ull *istart, gomp_ull *iend)
538 {
539   return gomp_loop_ull_dynamic_next (istart, iend);
540 }
541
542 bool
543 GOMP_loop_ull_guided_next (gomp_ull *istart, gomp_ull *iend)
544 {
545   return gomp_loop_ull_guided_next (istart, iend);
546 }
547
548 bool
549 GOMP_loop_ull_ordered_static_next (gomp_ull *istart, gomp_ull *iend)
550 {
551   return gomp_loop_ull_ordered_static_next (istart, iend);
552 }
553
554 bool
555 GOMP_loop_ull_ordered_dynamic_next (gomp_ull *istart, gomp_ull *iend)
556 {
557   return gomp_loop_ull_ordered_dynamic_next (istart, iend);
558 }
559
560 bool
561 GOMP_loop_ull_ordered_guided_next (gomp_ull *istart, gomp_ull *iend)
562 {
563   return gomp_loop_ull_ordered_guided_next (istart, iend);
564 }
565 #endif