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