Mercurial > hg > CbC > CbC_gcc

comparison libgomp/loop.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 04ced10e8804
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
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