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