Mercurial > hg > CbC > CbC_gcc

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