OSDN Git Service

fix broken checkin, test should be link not assemble
[pf3gnuchains/gcc-fork.git] / libgomp / iter.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 contains routines for managing work-share iteration, both
26    for loops and sections.  */
27
28 #include "libgomp.h"
29 #include <stdlib.h>
30
31
32 /* This function implements the STATIC scheduling method.  The caller should
33    iterate *pstart <= x < *pend.  Return zero if there are more iterations
34    to perform; nonzero if not.  Return less than 0 if this thread had
35    received the absolutely last iteration.  */
36
37 int
38 gomp_iter_static_next (long *pstart, long *pend)
39 {
40   struct gomp_thread *thr = gomp_thread ();
41   struct gomp_team *team = thr->ts.team;
42   struct gomp_work_share *ws = thr->ts.work_share;
43   unsigned long nthreads = team ? team->nthreads : 1;
44
45   if (thr->ts.static_trip == -1)
46     return -1;
47
48   /* Quick test for degenerate teams and orphaned constructs.  */
49   if (nthreads == 1)
50     {
51       *pstart = ws->next;
52       *pend = ws->end;
53       thr->ts.static_trip = -1;
54       return ws->next == ws->end;
55     }
56
57   /* We interpret chunk_size zero as "unspecified", which means that we
58      should break up the iterations such that each thread makes only one
59      trip through the outer loop.  */
60   if (ws->chunk_size == 0)
61     {
62       unsigned long n, q, i;
63       unsigned long s0, e0;
64       long s, e;
65
66       if (thr->ts.static_trip > 0)
67         return 1;
68
69       /* Compute the total number of iterations.  */
70       s = ws->incr + (ws->incr > 0 ? -1 : 1);
71       n = (ws->end - ws->next + s) / ws->incr;
72       i = thr->ts.team_id;
73
74       /* Compute the "zero-based" start and end points.  That is, as
75          if the loop began at zero and incremented by one.  */
76       q = n / nthreads;
77       q += (q * nthreads != n);
78       s0 = q * i;
79       e0 = s0 + q;
80       if (e0 > n)
81         e0 = n;
82
83       /* Notice when no iterations allocated for this thread.  */
84       if (s0 >= e0)
85         {
86           thr->ts.static_trip = 1;
87           return 1;
88         }
89
90       /* Transform these to the actual start and end numbers.  */
91       s = (long)s0 * ws->incr + ws->next;
92       e = (long)e0 * ws->incr + ws->next;
93
94       *pstart = s;
95       *pend = e;
96       thr->ts.static_trip = (e0 == n ? -1 : 1);
97       return 0;
98     }
99   else
100     {
101       unsigned long n, s0, e0, i, c;
102       long s, e;
103
104       /* Otherwise, each thread gets exactly chunk_size iterations
105          (if available) each time through the loop.  */
106
107       s = ws->incr + (ws->incr > 0 ? -1 : 1);
108       n = (ws->end - ws->next + s) / ws->incr;
109       i = thr->ts.team_id;
110       c = ws->chunk_size;
111
112       /* Initial guess is a C sized chunk positioned nthreads iterations
113          in, offset by our thread number.  */
114       s0 = (thr->ts.static_trip * nthreads + i) * c;
115       e0 = s0 + c;
116
117       /* Detect overflow.  */
118       if (s0 >= n)
119         return 1;
120       if (e0 > n)
121         e0 = n;
122
123       /* Transform these to the actual start and end numbers.  */
124       s = (long)s0 * ws->incr + ws->next;
125       e = (long)e0 * ws->incr + ws->next;
126
127       *pstart = s;
128       *pend = e;
129
130       if (e0 == n)
131         thr->ts.static_trip = -1;
132       else
133         thr->ts.static_trip++;
134       return 0;
135     }
136 }
137
138
139 /* This function implements the DYNAMIC scheduling method.  Arguments are
140    as for gomp_iter_static_next.  This function must be called with ws->lock
141    held.  */
142
143 bool
144 gomp_iter_dynamic_next_locked (long *pstart, long *pend)
145 {
146   struct gomp_thread *thr = gomp_thread ();
147   struct gomp_work_share *ws = thr->ts.work_share;
148   long start, end, chunk, left;
149
150   start = ws->next;
151   if (start == ws->end)
152     return false;
153
154   chunk = ws->chunk_size;
155   left = ws->end - start;
156   if (ws->incr < 0)
157     {
158       if (chunk < left)
159         chunk = left;
160     }
161   else
162     {
163       if (chunk > left)
164         chunk = left;
165     }
166   end = start + chunk;
167
168   ws->next = end;
169   *pstart = start;
170   *pend = end;
171   return true;
172 }
173
174
175 #ifdef HAVE_SYNC_BUILTINS
176 /* Similar, but doesn't require the lock held, and uses compare-and-swap
177    instead.  Note that the only memory value that changes is ws->next.  */
178
179 bool
180 gomp_iter_dynamic_next (long *pstart, long *pend)
181 {
182   struct gomp_thread *thr = gomp_thread ();
183   struct gomp_work_share *ws = thr->ts.work_share;
184   long start, end, nend, chunk, incr;
185
186   end = ws->end;
187   incr = ws->incr;
188   chunk = ws->chunk_size;
189
190   if (__builtin_expect (ws->mode, 1))
191     {
192       long tmp = __sync_fetch_and_add (&ws->next, chunk);
193       if (incr > 0)
194         {
195           if (tmp >= end)
196             return false;
197           nend = tmp + chunk;
198           if (nend > end)
199             nend = end;
200           *pstart = tmp;
201           *pend = nend;
202           return true;
203         }
204       else
205         {
206           if (tmp <= end)
207             return false;
208           nend = tmp + chunk;
209           if (nend < end)
210             nend = end;
211           *pstart = tmp;
212           *pend = nend;
213           return true;
214         }
215     }
216
217   start = ws->next;
218   while (1)
219     {
220       long left = end - start;
221       long tmp;
222
223       if (start == end)
224         return false;
225
226       if (incr < 0)
227         {
228           if (chunk < left)
229             chunk = left;
230         }
231       else
232         {
233           if (chunk > left)
234             chunk = left;
235         }
236       nend = start + chunk;
237
238       tmp = __sync_val_compare_and_swap (&ws->next, start, nend);
239       if (__builtin_expect (tmp == start, 1))
240         break;
241
242       start = tmp;
243     }
244
245   *pstart = start;
246   *pend = nend;
247   return true;
248 }
249 #endif /* HAVE_SYNC_BUILTINS */
250
251
252 /* This function implements the GUIDED scheduling method.  Arguments are
253    as for gomp_iter_static_next.  This function must be called with the
254    work share lock held.  */
255
256 bool
257 gomp_iter_guided_next_locked (long *pstart, long *pend)
258 {
259   struct gomp_thread *thr = gomp_thread ();
260   struct gomp_work_share *ws = thr->ts.work_share;
261   struct gomp_team *team = thr->ts.team;
262   unsigned long nthreads = team ? team->nthreads : 1;
263   unsigned long n, q;
264   long start, end;
265
266   if (ws->next == ws->end)
267     return false;
268
269   start = ws->next;
270   n = (ws->end - start) / ws->incr;
271   q = (n + nthreads - 1) / nthreads;
272
273   if (q < ws->chunk_size)
274     q = ws->chunk_size;
275   if (q <= n)
276     end = start + q * ws->incr;
277   else
278     end = ws->end;
279
280   ws->next = end;
281   *pstart = start;
282   *pend = end;
283   return true;
284 }
285
286 #ifdef HAVE_SYNC_BUILTINS
287 /* Similar, but doesn't require the lock held, and uses compare-and-swap
288    instead.  Note that the only memory value that changes is ws->next.  */
289
290 bool
291 gomp_iter_guided_next (long *pstart, long *pend)
292 {
293   struct gomp_thread *thr = gomp_thread ();
294   struct gomp_work_share *ws = thr->ts.work_share;
295   struct gomp_team *team = thr->ts.team;
296   unsigned long nthreads = team ? team->nthreads : 1;
297   long start, end, nend, incr;
298   unsigned long chunk_size;
299
300   start = ws->next;
301   end = ws->end;
302   incr = ws->incr;
303   chunk_size = ws->chunk_size;
304
305   while (1)
306     {
307       unsigned long n, q;
308       long tmp;
309
310       if (start == end)
311         return false;
312
313       n = (end - start) / incr;
314       q = (n + nthreads - 1) / nthreads;
315
316       if (q < chunk_size)
317         q = chunk_size;
318       if (__builtin_expect (q <= n, 1))
319         nend = start + q * incr;
320       else
321         nend = end;
322
323       tmp = __sync_val_compare_and_swap (&ws->next, start, nend);
324       if (__builtin_expect (tmp == start, 1))
325         break;
326
327       start = tmp;
328     }
329
330   *pstart = start;
331   *pend = nend;
332   return true;
333 }
334 #endif /* HAVE_SYNC_BUILTINS */