Intel® OpenMP* Runtime Library
 All Classes Functions Variables Typedefs Enumerations Enumerator Modules Pages
kmp_sched.cpp
1 /*
2  * kmp_sched.c -- static scheduling -- iteration initialization
3  */
4 
5 /* <copyright>
6  Copyright (c) 1997-2015 Intel Corporation. All Rights Reserved.
7 
8  Redistribution and use in source and binary forms, with or without
9  modification, are permitted provided that the following conditions
10  are met:
11 
12  * Redistributions of source code must retain the above copyright
13  notice, this list of conditions and the following disclaimer.
14  * Redistributions in binary form must reproduce the above copyright
15  notice, this list of conditions and the following disclaimer in the
16  documentation and/or other materials provided with the distribution.
17  * Neither the name of Intel Corporation nor the names of its
18  contributors may be used to endorse or promote products derived
19  from this software without specific prior written permission.
20 
21  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25  HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 
33 </copyright> */
34 
35 /*
36  * Static scheduling initialization.
37  *
38  * NOTE: team->t.t_nproc is a constant inside of any dispatch loop, however
39  * it may change values between parallel regions. __kmp_max_nth
40  * is the largest value __kmp_nth may take, 1 is the smallest.
41  *
42  */
43 
44 #include "kmp.h"
45 #include "kmp_i18n.h"
46 #include "kmp_str.h"
47 #include "kmp_error.h"
48 #include "kmp_stats.h"
49 #include "kmp_itt.h"
50 
51 #if OMPT_SUPPORT
52 #include "ompt-specific.h"
53 #endif
54 
55 // template for type limits
56 template< typename T >
57 struct i_maxmin {
58  static const T mx;
59  static const T mn;
60 };
61 template<>
62 struct i_maxmin< int > {
63  static const int mx = 0x7fffffff;
64  static const int mn = 0x80000000;
65 };
66 template<>
67 struct i_maxmin< unsigned int > {
68  static const unsigned int mx = 0xffffffff;
69  static const unsigned int mn = 0x00000000;
70 };
71 template<>
72 struct i_maxmin< long long > {
73  static const long long mx = 0x7fffffffffffffffLL;
74  static const long long mn = 0x8000000000000000LL;
75 };
76 template<>
77 struct i_maxmin< unsigned long long > {
78  static const unsigned long long mx = 0xffffffffffffffffLL;
79  static const unsigned long long mn = 0x0000000000000000LL;
80 };
81 //-------------------------------------------------------------------------
82 #ifdef KMP_DEBUG
83 //-------------------------------------------------------------------------
84 // template for debug prints specification ( d, u, lld, llu )
85  char const * traits_t< int >::spec = "d";
86  char const * traits_t< unsigned int >::spec = "u";
87  char const * traits_t< long long >::spec = "lld";
88  char const * traits_t< unsigned long long >::spec = "llu";
89 //-------------------------------------------------------------------------
90 #endif
91 
92 template< typename T >
93 static void
94 __kmp_for_static_init(
95  ident_t *loc,
96  kmp_int32 global_tid,
97  kmp_int32 schedtype,
98  kmp_int32 *plastiter,
99  T *plower,
100  T *pupper,
101  typename traits_t< T >::signed_t *pstride,
102  typename traits_t< T >::signed_t incr,
103  typename traits_t< T >::signed_t chunk
104 ) {
105  KMP_COUNT_BLOCK(OMP_FOR_static);
106  typedef typename traits_t< T >::unsigned_t UT;
107  typedef typename traits_t< T >::signed_t ST;
108  /* this all has to be changed back to TID and such.. */
109  register kmp_int32 gtid = global_tid;
110  register kmp_uint32 tid;
111  register kmp_uint32 nth;
112  register UT trip_count;
113  register kmp_team_t *team;
114  register kmp_info_t *th = __kmp_threads[ gtid ];
115 
116 #if OMPT_SUPPORT && OMPT_TRACE
117  ompt_team_info_t *team_info = __ompt_get_teaminfo(0, NULL);
118  ompt_task_info_t *task_info = __ompt_get_taskinfo(0);
119 #endif
120 
121  KMP_DEBUG_ASSERT( plastiter && plower && pupper && pstride );
122  KE_TRACE( 10, ("__kmpc_for_static_init called (%d)\n", global_tid));
123  #ifdef KMP_DEBUG
124  {
125  const char * buff;
126  // create format specifiers before the debug output
127  buff = __kmp_str_format(
128  "__kmpc_for_static_init: T#%%d sched=%%d liter=%%d iter=(%%%s," \
129  " %%%s, %%%s) incr=%%%s chunk=%%%s signed?<%s>\n",
130  traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec,
131  traits_t< ST >::spec, traits_t< ST >::spec, traits_t< T >::spec );
132  KD_TRACE(100, ( buff, global_tid, schedtype, *plastiter,
133  *plower, *pupper, *pstride, incr, chunk ) );
134  __kmp_str_free( &buff );
135  }
136  #endif
137 
138  if ( __kmp_env_consistency_check ) {
139  __kmp_push_workshare( global_tid, ct_pdo, loc );
140  if ( incr == 0 ) {
141  __kmp_error_construct( kmp_i18n_msg_CnsLoopIncrZeroProhibited, ct_pdo, loc );
142  }
143  }
144  /* special handling for zero-trip loops */
145  if ( incr > 0 ? (*pupper < *plower) : (*plower < *pupper) ) {
146  if( plastiter != NULL )
147  *plastiter = FALSE;
148  /* leave pupper and plower set to entire iteration space */
149  *pstride = incr; /* value should never be used */
150  // *plower = *pupper - incr; // let compiler bypass the illegal loop (like for(i=1;i<10;i--)) THIS LINE CAUSED shape2F/h_tests_1.f TO HAVE A FAILURE ON A ZERO-TRIP LOOP (lower=1,\
151  upper=0,stride=1) - JPH June 23, 2009.
152  #ifdef KMP_DEBUG
153  {
154  const char * buff;
155  // create format specifiers before the debug output
156  buff = __kmp_str_format(
157  "__kmpc_for_static_init:(ZERO TRIP) liter=%%d lower=%%%s upper=%%%s stride = %%%s signed?<%s>, loc = %%s\n",
158  traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec, traits_t< T >::spec );
159  KD_TRACE(100, ( buff, *plastiter, *plower, *pupper, *pstride, loc->psource ) );
160  __kmp_str_free( &buff );
161  }
162  #endif
163  KE_TRACE( 10, ("__kmpc_for_static_init: T#%d return\n", global_tid ) );
164 
165 #if OMPT_SUPPORT && OMPT_TRACE
166  if ((ompt_status == ompt_status_track_callback) &&
167  ompt_callbacks.ompt_callback(ompt_event_loop_begin)) {
168  ompt_callbacks.ompt_callback(ompt_event_loop_begin)(
169  team_info->parallel_id, task_info->task_id,
170  team_info->microtask);
171  }
172 #endif
173  return;
174  }
175 
176  #if OMP_40_ENABLED
177  if ( schedtype > kmp_ord_upper ) {
178  // we are in DISTRIBUTE construct
179  schedtype += kmp_sch_static - kmp_distribute_static; // AC: convert to usual schedule type
180  tid = th->th.th_team->t.t_master_tid;
181  team = th->th.th_team->t.t_parent;
182  } else
183  #endif
184  {
185  tid = __kmp_tid_from_gtid( global_tid );
186  team = th->th.th_team;
187  }
188 
189  /* determine if "for" loop is an active worksharing construct */
190  if ( team -> t.t_serialized ) {
191  /* serialized parallel, each thread executes whole iteration space */
192  if( plastiter != NULL )
193  *plastiter = TRUE;
194  /* leave pupper and plower set to entire iteration space */
195  *pstride = (incr > 0) ? (*pupper - *plower + 1) : (-(*plower - *pupper + 1));
196 
197  #ifdef KMP_DEBUG
198  {
199  const char * buff;
200  // create format specifiers before the debug output
201  buff = __kmp_str_format(
202  "__kmpc_for_static_init: (serial) liter=%%d lower=%%%s upper=%%%s stride = %%%s\n",
203  traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec );
204  KD_TRACE(100, ( buff, *plastiter, *plower, *pupper, *pstride ) );
205  __kmp_str_free( &buff );
206  }
207  #endif
208  KE_TRACE( 10, ("__kmpc_for_static_init: T#%d return\n", global_tid ) );
209 
210 #if OMPT_SUPPORT && OMPT_TRACE
211  if ((ompt_status == ompt_status_track_callback) &&
212  ompt_callbacks.ompt_callback(ompt_event_loop_begin)) {
213  ompt_callbacks.ompt_callback(ompt_event_loop_begin)(
214  team_info->parallel_id, task_info->task_id,
215  team_info->microtask);
216  }
217 #endif
218  return;
219  }
220  nth = team->t.t_nproc;
221  if ( nth == 1 ) {
222  if( plastiter != NULL )
223  *plastiter = TRUE;
224  *pstride = (incr > 0) ? (*pupper - *plower + 1) : (-(*plower - *pupper + 1));
225  #ifdef KMP_DEBUG
226  {
227  const char * buff;
228  // create format specifiers before the debug output
229  buff = __kmp_str_format(
230  "__kmpc_for_static_init: (serial) liter=%%d lower=%%%s upper=%%%s stride = %%%s\n",
231  traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec );
232  KD_TRACE(100, ( buff, *plastiter, *plower, *pupper, *pstride ) );
233  __kmp_str_free( &buff );
234  }
235  #endif
236  KE_TRACE( 10, ("__kmpc_for_static_init: T#%d return\n", global_tid ) );
237 
238 #if OMPT_SUPPORT && OMPT_TRACE
239  if ((ompt_status == ompt_status_track_callback) &&
240  ompt_callbacks.ompt_callback(ompt_event_loop_begin)) {
241  ompt_callbacks.ompt_callback(ompt_event_loop_begin)(
242  team_info->parallel_id, task_info->task_id,
243  team_info->microtask);
244  }
245 #endif
246  return;
247  }
248 
249  /* compute trip count */
250  if ( incr == 1 ) {
251  trip_count = *pupper - *plower + 1;
252  } else if (incr == -1) {
253  trip_count = *plower - *pupper + 1;
254  } else {
255  if ( incr > 1 ) { // the check is needed for unsigned division when incr < 0
256  trip_count = (*pupper - *plower) / incr + 1;
257  } else {
258  trip_count = (*plower - *pupper) / ( -incr ) + 1;
259  }
260  }
261 
262  if ( __kmp_env_consistency_check ) {
263  /* tripcount overflow? */
264  if ( trip_count == 0 && *pupper != *plower ) {
265  __kmp_error_construct( kmp_i18n_msg_CnsIterationRangeTooLarge, ct_pdo, loc );
266  }
267  }
268 
269  /* compute remaining parameters */
270  switch ( schedtype ) {
271  case kmp_sch_static:
272  {
273  if ( trip_count < nth ) {
274  KMP_DEBUG_ASSERT(
275  __kmp_static == kmp_sch_static_greedy || \
276  __kmp_static == kmp_sch_static_balanced
277  ); // Unknown static scheduling type.
278  if ( tid < trip_count ) {
279  *pupper = *plower = *plower + tid * incr;
280  } else {
281  *plower = *pupper + incr;
282  }
283  if( plastiter != NULL )
284  *plastiter = ( tid == trip_count - 1 );
285  } else {
286  if ( __kmp_static == kmp_sch_static_balanced ) {
287  register UT small_chunk = trip_count / nth;
288  register UT extras = trip_count % nth;
289  *plower += incr * ( tid * small_chunk + ( tid < extras ? tid : extras ) );
290  *pupper = *plower + small_chunk * incr - ( tid < extras ? 0 : incr );
291  if( plastiter != NULL )
292  *plastiter = ( tid == nth - 1 );
293  } else {
294  register T big_chunk_inc_count = ( trip_count/nth +
295  ( ( trip_count % nth ) ? 1 : 0) ) * incr;
296  register T old_upper = *pupper;
297 
298  KMP_DEBUG_ASSERT( __kmp_static == kmp_sch_static_greedy );
299  // Unknown static scheduling type.
300 
301  *plower += tid * big_chunk_inc_count;
302  *pupper = *plower + big_chunk_inc_count - incr;
303  if ( incr > 0 ) {
304  if( *pupper < *plower )
305  *pupper = i_maxmin< T >::mx;
306  if( plastiter != NULL )
307  *plastiter = *plower <= old_upper && *pupper > old_upper - incr;
308  if ( *pupper > old_upper ) *pupper = old_upper; // tracker C73258
309  } else {
310  if( *pupper > *plower )
311  *pupper = i_maxmin< T >::mn;
312  if( plastiter != NULL )
313  *plastiter = *plower >= old_upper && *pupper < old_upper - incr;
314  if ( *pupper < old_upper ) *pupper = old_upper; // tracker C73258
315  }
316  }
317  }
318  break;
319  }
320  case kmp_sch_static_chunked:
321  {
322  register ST span;
323  if ( chunk < 1 ) {
324  chunk = 1;
325  }
326  span = chunk * incr;
327  *pstride = span * nth;
328  *plower = *plower + (span * tid);
329  *pupper = *plower + span - incr;
330  if( plastiter != NULL )
331  *plastiter = (tid == ((trip_count - 1)/( UT )chunk) % nth);
332  break;
333  }
334  default:
335  KMP_ASSERT2( 0, "__kmpc_for_static_init: unknown scheduling type" );
336  break;
337  }
338 
339 #if USE_ITT_BUILD
340  // Report loop metadata
341  if ( KMP_MASTER_TID(tid) && __itt_metadata_add_ptr && __kmp_forkjoin_frames_mode == 3 &&
342 #if OMP_40_ENABLED
343  th->th.th_teams_microtask == NULL &&
344 #endif
345  team->t.t_active_level == 1 )
346  {
347  kmp_uint64 cur_chunk = chunk;
348  // Calculate chunk in case it was not specified; it is specified for kmp_sch_static_chunked
349  if ( schedtype == kmp_sch_static ) {
350  cur_chunk = trip_count / nth + ( ( trip_count % nth ) ? 1 : 0);
351  }
352  // 0 - "static" schedule
353  __kmp_itt_metadata_loop(loc, 0, trip_count, cur_chunk);
354  }
355 #endif
356  #ifdef KMP_DEBUG
357  {
358  const char * buff;
359  // create format specifiers before the debug output
360  buff = __kmp_str_format(
361  "__kmpc_for_static_init: liter=%%d lower=%%%s upper=%%%s stride = %%%s signed?<%s>\n",
362  traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec, traits_t< T >::spec );
363  KD_TRACE(100, ( buff, *plastiter, *plower, *pupper, *pstride ) );
364  __kmp_str_free( &buff );
365  }
366  #endif
367  KE_TRACE( 10, ("__kmpc_for_static_init: T#%d return\n", global_tid ) );
368 
369 #if OMPT_SUPPORT && OMPT_TRACE
370  if ((ompt_status == ompt_status_track_callback) &&
371  ompt_callbacks.ompt_callback(ompt_event_loop_begin)) {
372  ompt_callbacks.ompt_callback(ompt_event_loop_begin)(
373  team_info->parallel_id, task_info->task_id, team_info->microtask);
374  }
375 #endif
376 
377  return;
378 }
379 
380 template< typename T >
381 static void
382 __kmp_dist_for_static_init(
383  ident_t *loc,
384  kmp_int32 gtid,
385  kmp_int32 schedule,
386  kmp_int32 *plastiter,
387  T *plower,
388  T *pupper,
389  T *pupperDist,
390  typename traits_t< T >::signed_t *pstride,
391  typename traits_t< T >::signed_t incr,
392  typename traits_t< T >::signed_t chunk
393 ) {
394  KMP_COUNT_BLOCK(OMP_DISTR_FOR_static);
395  typedef typename traits_t< T >::unsigned_t UT;
396  typedef typename traits_t< T >::signed_t ST;
397  register kmp_uint32 tid;
398  register kmp_uint32 nth;
399  register kmp_uint32 team_id;
400  register kmp_uint32 nteams;
401  register UT trip_count;
402  register kmp_team_t *team;
403  kmp_info_t * th;
404 
405  KMP_DEBUG_ASSERT( plastiter && plower && pupper && pupperDist && pstride );
406  KE_TRACE( 10, ("__kmpc_dist_for_static_init called (%d)\n", gtid));
407  #ifdef KMP_DEBUG
408  {
409  const char * buff;
410  // create format specifiers before the debug output
411  buff = __kmp_str_format(
412  "__kmpc_dist_for_static_init: T#%%d schedLoop=%%d liter=%%d "\
413  "iter=(%%%s, %%%s, %%%s) chunk=%%%s signed?<%s>\n",
414  traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec,
415  traits_t< ST >::spec, traits_t< T >::spec );
416  KD_TRACE(100, ( buff, gtid, schedule, *plastiter,
417  *plower, *pupper, incr, chunk ) );
418  __kmp_str_free( &buff );
419  }
420  #endif
421 
422  if( __kmp_env_consistency_check ) {
423  __kmp_push_workshare( gtid, ct_pdo, loc );
424  if( incr == 0 ) {
425  __kmp_error_construct( kmp_i18n_msg_CnsLoopIncrZeroProhibited, ct_pdo, loc );
426  }
427  if( incr > 0 ? (*pupper < *plower) : (*plower < *pupper) ) {
428  // The loop is illegal.
429  // Some zero-trip loops maintained by compiler, e.g.:
430  // for(i=10;i<0;++i) // lower >= upper - run-time check
431  // for(i=0;i>10;--i) // lower <= upper - run-time check
432  // for(i=0;i>10;++i) // incr > 0 - compile-time check
433  // for(i=10;i<0;--i) // incr < 0 - compile-time check
434  // Compiler does not check the following illegal loops:
435  // for(i=0;i<10;i+=incr) // where incr<0
436  // for(i=10;i>0;i-=incr) // where incr<0
437  __kmp_error_construct( kmp_i18n_msg_CnsLoopIncrIllegal, ct_pdo, loc );
438  }
439  }
440  tid = __kmp_tid_from_gtid( gtid );
441  th = __kmp_threads[gtid];
442  KMP_DEBUG_ASSERT(th->th.th_teams_microtask); // we are in the teams construct
443  nth = th->th.th_team_nproc;
444  team = th->th.th_team;
445  #if OMP_40_ENABLED
446  nteams = th->th.th_teams_size.nteams;
447  #endif
448  team_id = team->t.t_master_tid;
449  KMP_DEBUG_ASSERT(nteams == team->t.t_parent->t.t_nproc);
450 
451  // compute global trip count
452  if( incr == 1 ) {
453  trip_count = *pupper - *plower + 1;
454  } else if(incr == -1) {
455  trip_count = *plower - *pupper + 1;
456  } else {
457  trip_count = (ST)(*pupper - *plower) / incr + 1; // cast to signed to cover incr<0 case
458  }
459  *pstride = *pupper - *plower; // just in case (can be unused)
460  if( trip_count <= nteams ) {
461  KMP_DEBUG_ASSERT(
462  __kmp_static == kmp_sch_static_greedy || \
463  __kmp_static == kmp_sch_static_balanced
464  ); // Unknown static scheduling type.
465  // only masters of some teams get single iteration, other threads get nothing
466  if( team_id < trip_count && tid == 0 ) {
467  *pupper = *pupperDist = *plower = *plower + team_id * incr;
468  } else {
469  *pupperDist = *pupper;
470  *plower = *pupper + incr; // compiler should skip loop body
471  }
472  if( plastiter != NULL )
473  *plastiter = ( tid == 0 && team_id == trip_count - 1 );
474  } else {
475  // Get the team's chunk first (each team gets at most one chunk)
476  if( __kmp_static == kmp_sch_static_balanced ) {
477  register UT chunkD = trip_count / nteams;
478  register UT extras = trip_count % nteams;
479  *plower += incr * ( team_id * chunkD + ( team_id < extras ? team_id : extras ) );
480  *pupperDist = *plower + chunkD * incr - ( team_id < extras ? 0 : incr );
481  if( plastiter != NULL )
482  *plastiter = ( team_id == nteams - 1 );
483  } else {
484  register T chunk_inc_count =
485  ( trip_count / nteams + ( ( trip_count % nteams ) ? 1 : 0) ) * incr;
486  register T upper = *pupper;
487  KMP_DEBUG_ASSERT( __kmp_static == kmp_sch_static_greedy );
488  // Unknown static scheduling type.
489  *plower += team_id * chunk_inc_count;
490  *pupperDist = *plower + chunk_inc_count - incr;
491  // Check/correct bounds if needed
492  if( incr > 0 ) {
493  if( *pupperDist < *plower )
494  *pupperDist = i_maxmin< T >::mx;
495  if( plastiter != NULL )
496  *plastiter = *plower <= upper && *pupperDist > upper - incr;
497  if( *pupperDist > upper )
498  *pupperDist = upper; // tracker C73258
499  if( *plower > *pupperDist ) {
500  *pupper = *pupperDist; // no iterations available for the team
501  goto end;
502  }
503  } else {
504  if( *pupperDist > *plower )
505  *pupperDist = i_maxmin< T >::mn;
506  if( plastiter != NULL )
507  *plastiter = *plower >= upper && *pupperDist < upper - incr;
508  if( *pupperDist < upper )
509  *pupperDist = upper; // tracker C73258
510  if( *plower < *pupperDist ) {
511  *pupper = *pupperDist; // no iterations available for the team
512  goto end;
513  }
514  }
515  }
516  // Get the parallel loop chunk now (for thread)
517  // compute trip count for team's chunk
518  if( incr == 1 ) {
519  trip_count = *pupperDist - *plower + 1;
520  } else if(incr == -1) {
521  trip_count = *plower - *pupperDist + 1;
522  } else {
523  trip_count = (ST)(*pupperDist - *plower) / incr + 1;
524  }
525  KMP_DEBUG_ASSERT( trip_count );
526  switch( schedule ) {
527  case kmp_sch_static:
528  {
529  if( trip_count <= nth ) {
530  KMP_DEBUG_ASSERT(
531  __kmp_static == kmp_sch_static_greedy || \
532  __kmp_static == kmp_sch_static_balanced
533  ); // Unknown static scheduling type.
534  if( tid < trip_count )
535  *pupper = *plower = *plower + tid * incr;
536  else
537  *plower = *pupper + incr; // no iterations available
538  if( plastiter != NULL )
539  if( *plastiter != 0 && !( tid == trip_count - 1 ) )
540  *plastiter = 0;
541  } else {
542  if( __kmp_static == kmp_sch_static_balanced ) {
543  register UT chunkL = trip_count / nth;
544  register UT extras = trip_count % nth;
545  *plower += incr * (tid * chunkL + (tid < extras ? tid : extras));
546  *pupper = *plower + chunkL * incr - (tid < extras ? 0 : incr);
547  if( plastiter != NULL )
548  if( *plastiter != 0 && !( tid == nth - 1 ) )
549  *plastiter = 0;
550  } else {
551  register T chunk_inc_count =
552  ( trip_count / nth + ( ( trip_count % nth ) ? 1 : 0) ) * incr;
553  register T upper = *pupperDist;
554  KMP_DEBUG_ASSERT( __kmp_static == kmp_sch_static_greedy );
555  // Unknown static scheduling type.
556  *plower += tid * chunk_inc_count;
557  *pupper = *plower + chunk_inc_count - incr;
558  if( incr > 0 ) {
559  if( *pupper < *plower )
560  *pupper = i_maxmin< T >::mx;
561  if( plastiter != NULL )
562  if( *plastiter != 0 && !(*plower <= upper && *pupper > upper - incr) )
563  *plastiter = 0;
564  if( *pupper > upper )
565  *pupper = upper;//tracker C73258
566  } else {
567  if( *pupper > *plower )
568  *pupper = i_maxmin< T >::mn;
569  if( plastiter != NULL )
570  if( *plastiter != 0 && !(*plower >= upper && *pupper < upper - incr) )
571  *plastiter = 0;
572  if( *pupper < upper )
573  *pupper = upper;//tracker C73258
574  }
575  }
576  }
577  break;
578  }
579  case kmp_sch_static_chunked:
580  {
581  register ST span;
582  if( chunk < 1 )
583  chunk = 1;
584  span = chunk * incr;
585  *pstride = span * nth;
586  *plower = *plower + (span * tid);
587  *pupper = *plower + span - incr;
588  if( plastiter != NULL )
589  if( *plastiter != 0 && !(tid == ((trip_count - 1) / ( UT )chunk) % nth) )
590  *plastiter = 0;
591  break;
592  }
593  default:
594  KMP_ASSERT2( 0, "__kmpc_dist_for_static_init: unknown loop scheduling type" );
595  break;
596  }
597  }
598  end:;
599  #ifdef KMP_DEBUG
600  {
601  const char * buff;
602  // create format specifiers before the debug output
603  buff = __kmp_str_format(
604  "__kmpc_dist_for_static_init: last=%%d lo=%%%s up=%%%s upDist=%%%s "\
605  "stride=%%%s signed?<%s>\n",
606  traits_t< T >::spec, traits_t< T >::spec, traits_t< T >::spec,
607  traits_t< ST >::spec, traits_t< T >::spec );
608  KD_TRACE(100, ( buff, *plastiter, *plower, *pupper, *pupperDist, *pstride ) );
609  __kmp_str_free( &buff );
610  }
611  #endif
612  KE_TRACE( 10, ("__kmpc_dist_for_static_init: T#%d return\n", gtid ) );
613  return;
614 }
615 
616 template< typename T >
617 static void
618 __kmp_team_static_init(
619  ident_t *loc,
620  kmp_int32 gtid,
621  kmp_int32 *p_last,
622  T *p_lb,
623  T *p_ub,
624  typename traits_t< T >::signed_t *p_st,
625  typename traits_t< T >::signed_t incr,
626  typename traits_t< T >::signed_t chunk
627 ) {
628  // The routine returns the first chunk distributed to the team and
629  // stride for next chunks calculation.
630  // Last iteration flag set for the team that will execute
631  // the last iteration of the loop.
632  // The routine is called for dist_schedue(static,chunk) only.
633  typedef typename traits_t< T >::unsigned_t UT;
634  typedef typename traits_t< T >::signed_t ST;
635  kmp_uint32 team_id;
636  kmp_uint32 nteams;
637  UT trip_count;
638  T lower;
639  T upper;
640  ST span;
641  kmp_team_t *team;
642  kmp_info_t *th;
643 
644  KMP_DEBUG_ASSERT( p_last && p_lb && p_ub && p_st );
645  KE_TRACE( 10, ("__kmp_team_static_init called (%d)\n", gtid));
646  #ifdef KMP_DEBUG
647  {
648  const char * buff;
649  // create format specifiers before the debug output
650  buff = __kmp_str_format( "__kmp_team_static_init enter: T#%%d liter=%%d "\
651  "iter=(%%%s, %%%s, %%%s) chunk %%%s; signed?<%s>\n",
652  traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec,
653  traits_t< ST >::spec, traits_t< T >::spec );
654  KD_TRACE(100, ( buff, gtid, *p_last, *p_lb, *p_ub, *p_st, chunk ) );
655  __kmp_str_free( &buff );
656  }
657  #endif
658 
659  lower = *p_lb;
660  upper = *p_ub;
661  if( __kmp_env_consistency_check ) {
662  if( incr == 0 ) {
663  __kmp_error_construct( kmp_i18n_msg_CnsLoopIncrZeroProhibited, ct_pdo, loc );
664  }
665  if( incr > 0 ? (upper < lower) : (lower < upper) ) {
666  // The loop is illegal.
667  // Some zero-trip loops maintained by compiler, e.g.:
668  // for(i=10;i<0;++i) // lower >= upper - run-time check
669  // for(i=0;i>10;--i) // lower <= upper - run-time check
670  // for(i=0;i>10;++i) // incr > 0 - compile-time check
671  // for(i=10;i<0;--i) // incr < 0 - compile-time check
672  // Compiler does not check the following illegal loops:
673  // for(i=0;i<10;i+=incr) // where incr<0
674  // for(i=10;i>0;i-=incr) // where incr<0
675  __kmp_error_construct( kmp_i18n_msg_CnsLoopIncrIllegal, ct_pdo, loc );
676  }
677  }
678  th = __kmp_threads[gtid];
679  KMP_DEBUG_ASSERT(th->th.th_teams_microtask); // we are in the teams construct
680  team = th->th.th_team;
681  #if OMP_40_ENABLED
682  nteams = th->th.th_teams_size.nteams;
683  #endif
684  team_id = team->t.t_master_tid;
685  KMP_DEBUG_ASSERT(nteams == team->t.t_parent->t.t_nproc);
686 
687  // compute trip count
688  if( incr == 1 ) {
689  trip_count = upper - lower + 1;
690  } else if(incr == -1) {
691  trip_count = lower - upper + 1;
692  } else {
693  trip_count = (ST)(upper - lower) / incr + 1; // cast to signed to cover incr<0 case
694  }
695  if( chunk < 1 )
696  chunk = 1;
697  span = chunk * incr;
698  *p_st = span * nteams;
699  *p_lb = lower + (span * team_id);
700  *p_ub = *p_lb + span - incr;
701  if ( p_last != NULL )
702  *p_last = (team_id == ((trip_count - 1)/(UT)chunk) % nteams);
703  // Correct upper bound if needed
704  if( incr > 0 ) {
705  if( *p_ub < *p_lb ) // overflow?
706  *p_ub = i_maxmin< T >::mx;
707  if( *p_ub > upper )
708  *p_ub = upper; // tracker C73258
709  } else { // incr < 0
710  if( *p_ub > *p_lb )
711  *p_ub = i_maxmin< T >::mn;
712  if( *p_ub < upper )
713  *p_ub = upper; // tracker C73258
714  }
715  #ifdef KMP_DEBUG
716  {
717  const char * buff;
718  // create format specifiers before the debug output
719  buff = __kmp_str_format( "__kmp_team_static_init exit: T#%%d team%%u liter=%%d "\
720  "iter=(%%%s, %%%s, %%%s) chunk %%%s\n",
721  traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec,
722  traits_t< ST >::spec );
723  KD_TRACE(100, ( buff, gtid, team_id, *p_last, *p_lb, *p_ub, *p_st, chunk ) );
724  __kmp_str_free( &buff );
725  }
726  #endif
727 }
728 
729 //--------------------------------------------------------------------------------------
730 extern "C" {
731 
752 void
753 __kmpc_for_static_init_4( ident_t *loc, kmp_int32 gtid, kmp_int32 schedtype, kmp_int32 *plastiter,
754  kmp_int32 *plower, kmp_int32 *pupper,
755  kmp_int32 *pstride, kmp_int32 incr, kmp_int32 chunk )
756 {
757  __kmp_for_static_init< kmp_int32 >(
758  loc, gtid, schedtype, plastiter, plower, pupper, pstride, incr, chunk );
759 }
760 
764 void
765 __kmpc_for_static_init_4u( ident_t *loc, kmp_int32 gtid, kmp_int32 schedtype, kmp_int32 *plastiter,
766  kmp_uint32 *plower, kmp_uint32 *pupper,
767  kmp_int32 *pstride, kmp_int32 incr, kmp_int32 chunk )
768 {
769  __kmp_for_static_init< kmp_uint32 >(
770  loc, gtid, schedtype, plastiter, plower, pupper, pstride, incr, chunk );
771 }
772 
776 void
777 __kmpc_for_static_init_8( ident_t *loc, kmp_int32 gtid, kmp_int32 schedtype, kmp_int32 *plastiter,
778  kmp_int64 *plower, kmp_int64 *pupper,
779  kmp_int64 *pstride, kmp_int64 incr, kmp_int64 chunk )
780 {
781  __kmp_for_static_init< kmp_int64 >(
782  loc, gtid, schedtype, plastiter, plower, pupper, pstride, incr, chunk );
783 }
784 
788 void
789 __kmpc_for_static_init_8u( ident_t *loc, kmp_int32 gtid, kmp_int32 schedtype, kmp_int32 *plastiter,
790  kmp_uint64 *plower, kmp_uint64 *pupper,
791  kmp_int64 *pstride, kmp_int64 incr, kmp_int64 chunk )
792 {
793  __kmp_for_static_init< kmp_uint64 >(
794  loc, gtid, schedtype, plastiter, plower, pupper, pstride, incr, chunk );
795 }
822 void
824  ident_t *loc, kmp_int32 gtid, kmp_int32 schedule, kmp_int32 *plastiter,
825  kmp_int32 *plower, kmp_int32 *pupper, kmp_int32 *pupperD,
826  kmp_int32 *pstride, kmp_int32 incr, kmp_int32 chunk )
827 {
828  __kmp_dist_for_static_init< kmp_int32 >(
829  loc, gtid, schedule, plastiter, plower, pupper, pupperD, pstride, incr, chunk );
830 }
831 
835 void
837  ident_t *loc, kmp_int32 gtid, kmp_int32 schedule, kmp_int32 *plastiter,
838  kmp_uint32 *plower, kmp_uint32 *pupper, kmp_uint32 *pupperD,
839  kmp_int32 *pstride, kmp_int32 incr, kmp_int32 chunk )
840 {
841  __kmp_dist_for_static_init< kmp_uint32 >(
842  loc, gtid, schedule, plastiter, plower, pupper, pupperD, pstride, incr, chunk );
843 }
844 
848 void
850  ident_t *loc, kmp_int32 gtid, kmp_int32 schedule, kmp_int32 *plastiter,
851  kmp_int64 *plower, kmp_int64 *pupper, kmp_int64 *pupperD,
852  kmp_int64 *pstride, kmp_int64 incr, kmp_int64 chunk )
853 {
854  __kmp_dist_for_static_init< kmp_int64 >(
855  loc, gtid, schedule, plastiter, plower, pupper, pupperD, pstride, incr, chunk );
856 }
857 
861 void
863  ident_t *loc, kmp_int32 gtid, kmp_int32 schedule, kmp_int32 *plastiter,
864  kmp_uint64 *plower, kmp_uint64 *pupper, kmp_uint64 *pupperD,
865  kmp_int64 *pstride, kmp_int64 incr, kmp_int64 chunk )
866 {
867  __kmp_dist_for_static_init< kmp_uint64 >(
868  loc, gtid, schedule, plastiter, plower, pupper, pupperD, pstride, incr, chunk );
869 }
874 //-----------------------------------------------------------------------------------------
875 // Auxiliary routines for Distribute Parallel Loop construct implementation
876 // Transfer call to template< type T >
877 // __kmp_team_static_init( ident_t *loc, int gtid,
878 // int *p_last, T *lb, T *ub, ST *st, ST incr, ST chunk )
879 
899 void
901  ident_t *loc, kmp_int32 gtid, kmp_int32 *p_last,
902  kmp_int32 *p_lb, kmp_int32 *p_ub, kmp_int32 *p_st, kmp_int32 incr, kmp_int32 chunk )
903 {
904  KMP_DEBUG_ASSERT( __kmp_init_serial );
905  __kmp_team_static_init< kmp_int32 >( loc, gtid, p_last, p_lb, p_ub, p_st, incr, chunk );
906 }
907 
911 void
913  ident_t *loc, kmp_int32 gtid, kmp_int32 *p_last,
914  kmp_uint32 *p_lb, kmp_uint32 *p_ub, kmp_int32 *p_st, kmp_int32 incr, kmp_int32 chunk )
915 {
916  KMP_DEBUG_ASSERT( __kmp_init_serial );
917  __kmp_team_static_init< kmp_uint32 >( loc, gtid, p_last, p_lb, p_ub, p_st, incr, chunk );
918 }
919 
923 void
925  ident_t *loc, kmp_int32 gtid, kmp_int32 *p_last,
926  kmp_int64 *p_lb, kmp_int64 *p_ub, kmp_int64 *p_st, kmp_int64 incr, kmp_int64 chunk )
927 {
928  KMP_DEBUG_ASSERT( __kmp_init_serial );
929  __kmp_team_static_init< kmp_int64 >( loc, gtid, p_last, p_lb, p_ub, p_st, incr, chunk );
930 }
931 
935 void
937  ident_t *loc, kmp_int32 gtid, kmp_int32 *p_last,
938  kmp_uint64 *p_lb, kmp_uint64 *p_ub, kmp_int64 *p_st, kmp_int64 incr, kmp_int64 chunk )
939 {
940  KMP_DEBUG_ASSERT( __kmp_init_serial );
941  __kmp_team_static_init< kmp_uint64 >( loc, gtid, p_last, p_lb, p_ub, p_st, incr, chunk );
942 }
947 } // extern "C"
948 
void __kmpc_team_static_init_8(ident_t *loc, kmp_int32 gtid, kmp_int32 *p_last, kmp_int64 *p_lb, kmp_int64 *p_ub, kmp_int64 *p_st, kmp_int64 incr, kmp_int64 chunk)
Definition: kmp_sched.cpp:924
void __kmpc_dist_for_static_init_4u(ident_t *loc, kmp_int32 gtid, kmp_int32 schedule, kmp_int32 *plastiter, kmp_uint32 *plower, kmp_uint32 *pupper, kmp_uint32 *pupperD, kmp_int32 *pstride, kmp_int32 incr, kmp_int32 chunk)
Definition: kmp_sched.cpp:836
void __kmpc_team_static_init_4(ident_t *loc, kmp_int32 gtid, kmp_int32 *p_last, kmp_int32 *p_lb, kmp_int32 *p_ub, kmp_int32 *p_st, kmp_int32 incr, kmp_int32 chunk)
Definition: kmp_sched.cpp:900
void __kmpc_for_static_init_8(ident_t *loc, kmp_int32 gtid, kmp_int32 schedtype, kmp_int32 *plastiter, kmp_int64 *plower, kmp_int64 *pupper, kmp_int64 *pstride, kmp_int64 incr, kmp_int64 chunk)
Definition: kmp_sched.cpp:777
#define KMP_COUNT_BLOCK(name)
Increments specified counter (name).
Definition: kmp_stats.h:654
void __kmpc_team_static_init_4u(ident_t *loc, kmp_int32 gtid, kmp_int32 *p_last, kmp_uint32 *p_lb, kmp_uint32 *p_ub, kmp_int32 *p_st, kmp_int32 incr, kmp_int32 chunk)
Definition: kmp_sched.cpp:912
void __kmpc_for_static_init_4u(ident_t *loc, kmp_int32 gtid, kmp_int32 schedtype, kmp_int32 *plastiter, kmp_uint32 *plower, kmp_uint32 *pupper, kmp_int32 *pstride, kmp_int32 incr, kmp_int32 chunk)
Definition: kmp_sched.cpp:765
Definition: kmp.h:218
void __kmpc_dist_for_static_init_4(ident_t *loc, kmp_int32 gtid, kmp_int32 schedule, kmp_int32 *plastiter, kmp_int32 *plower, kmp_int32 *pupper, kmp_int32 *pupperD, kmp_int32 *pstride, kmp_int32 incr, kmp_int32 chunk)
Definition: kmp_sched.cpp:823
void __kmpc_team_static_init_8u(ident_t *loc, kmp_int32 gtid, kmp_int32 *p_last, kmp_uint64 *p_lb, kmp_uint64 *p_ub, kmp_int64 *p_st, kmp_int64 incr, kmp_int64 chunk)
Definition: kmp_sched.cpp:936
void __kmpc_dist_for_static_init_8u(ident_t *loc, kmp_int32 gtid, kmp_int32 schedule, kmp_int32 *plastiter, kmp_uint64 *plower, kmp_uint64 *pupper, kmp_uint64 *pupperD, kmp_int64 *pstride, kmp_int64 incr, kmp_int64 chunk)
Definition: kmp_sched.cpp:862
void __kmpc_for_static_init_4(ident_t *loc, kmp_int32 gtid, kmp_int32 schedtype, kmp_int32 *plastiter, kmp_int32 *plower, kmp_int32 *pupper, kmp_int32 *pstride, kmp_int32 incr, kmp_int32 chunk)
Definition: kmp_sched.cpp:753
void __kmpc_dist_for_static_init_8(ident_t *loc, kmp_int32 gtid, kmp_int32 schedule, kmp_int32 *plastiter, kmp_int64 *plower, kmp_int64 *pupper, kmp_int64 *pupperD, kmp_int64 *pstride, kmp_int64 incr, kmp_int64 chunk)
Definition: kmp_sched.cpp:849
char const * psource
Definition: kmp.h:227
void __kmpc_for_static_init_8u(ident_t *loc, kmp_int32 gtid, kmp_int32 schedtype, kmp_int32 *plastiter, kmp_uint64 *plower, kmp_uint64 *pupper, kmp_int64 *pstride, kmp_int64 incr, kmp_int64 chunk)
Definition: kmp_sched.cpp:789