| /* |
| * kmp_collapse.cpp -- loop collapse feature |
| */ |
| |
| //===----------------------------------------------------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "kmp.h" |
| #include "kmp_error.h" |
| #include "kmp_i18n.h" |
| #include "kmp_itt.h" |
| #include "kmp_stats.h" |
| #include "kmp_str.h" |
| #include "kmp_collapse.h" |
| |
| #if OMPT_SUPPORT |
| #include "ompt-specific.h" |
| #endif |
| |
| // OMPTODO: different style of comments (see kmp_sched) |
| // OMPTODO: OMPT/OMPD |
| |
| // avoid inadevertently using a library based abs |
| template <typename T> T __kmp_abs(const T val) { |
| return (val < 0) ? -val : val; |
| } |
| kmp_uint32 __kmp_abs(const kmp_uint32 val) { return val; } |
| kmp_uint64 __kmp_abs(const kmp_uint64 val) { return val; } |
| |
| //---------------------------------------------------------------------------- |
| // Common functions for working with rectangular and non-rectangular loops |
| //---------------------------------------------------------------------------- |
| |
| template <typename T> int __kmp_sign(T val) { |
| return (T(0) < val) - (val < T(0)); |
| } |
| |
| template <typename T> class CollapseAllocator { |
| typedef T *pT; |
| |
| private: |
| static const size_t allocaSize = 32; // size limit for stack allocations |
| // (8 bytes x 4 nested loops) |
| char stackAlloc[allocaSize]; |
| static constexpr size_t maxElemCount = allocaSize / sizeof(T); |
| pT pTAlloc; |
| |
| public: |
| CollapseAllocator(size_t n) : pTAlloc(reinterpret_cast<pT>(stackAlloc)) { |
| if (n > maxElemCount) { |
| pTAlloc = reinterpret_cast<pT>(__kmp_allocate(n * sizeof(T))); |
| } |
| } |
| ~CollapseAllocator() { |
| if (pTAlloc != reinterpret_cast<pT>(stackAlloc)) { |
| __kmp_free(pTAlloc); |
| } |
| } |
| T &operator[](int index) { return pTAlloc[index]; } |
| operator const pT() { return pTAlloc; } |
| }; |
| |
| //----------Loop canonicalization--------------------------------------------- |
| |
| // For loop nest (any shape): |
| // convert != to < or >; |
| // switch from using < or > to <= or >=. |
| // "bounds" array has to be allocated per thread. |
| // All other internal functions will work only with canonicalized loops. |
| template <typename T> |
| void kmp_canonicalize_one_loop_XX( |
| ident_t *loc, |
| /*in/out*/ bounds_infoXX_template<T> *bounds) { |
| |
| if (__kmp_env_consistency_check) { |
| if (bounds->step == 0) { |
| __kmp_error_construct(kmp_i18n_msg_CnsLoopIncrZeroProhibited, ct_pdo, |
| loc); |
| } |
| } |
| |
| if (bounds->comparison == comparison_t::comp_not_eq) { |
| // We can convert this to < or >, depends on the sign of the step: |
| if (bounds->step > 0) { |
| bounds->comparison = comparison_t::comp_less; |
| } else { |
| bounds->comparison = comparison_t::comp_greater; |
| } |
| } |
| |
| if (bounds->comparison == comparison_t::comp_less) { |
| // Note: ub0 can be unsigned. Should be Ok to hit overflow here, |
| // because ub0 + ub1*j should be still positive (otherwise loop was not |
| // well formed) |
| bounds->ub0 -= 1; |
| bounds->comparison = comparison_t::comp_less_or_eq; |
| } else if (bounds->comparison == comparison_t::comp_greater) { |
| bounds->ub0 += 1; |
| bounds->comparison = comparison_t::comp_greater_or_eq; |
| } |
| } |
| |
| // Canonicalize loop nest. original_bounds_nest is an array of length n. |
| void kmp_canonicalize_loop_nest(ident_t *loc, |
| /*in/out*/ bounds_info_t *original_bounds_nest, |
| kmp_index_t n) { |
| |
| for (kmp_index_t ind = 0; ind < n; ++ind) { |
| auto bounds = &(original_bounds_nest[ind]); |
| |
| switch (bounds->loop_type) { |
| case loop_type_t::loop_type_int32: |
| kmp_canonicalize_one_loop_XX<kmp_int32>( |
| loc, |
| /*in/out*/ (bounds_infoXX_template<kmp_int32> *)(bounds)); |
| break; |
| case loop_type_t::loop_type_uint32: |
| kmp_canonicalize_one_loop_XX<kmp_uint32>( |
| loc, |
| /*in/out*/ (bounds_infoXX_template<kmp_uint32> *)(bounds)); |
| break; |
| case loop_type_t::loop_type_int64: |
| kmp_canonicalize_one_loop_XX<kmp_int64>( |
| loc, |
| /*in/out*/ (bounds_infoXX_template<kmp_int64> *)(bounds)); |
| break; |
| case loop_type_t::loop_type_uint64: |
| kmp_canonicalize_one_loop_XX<kmp_uint64>( |
| loc, |
| /*in/out*/ (bounds_infoXX_template<kmp_uint64> *)(bounds)); |
| break; |
| default: |
| KMP_ASSERT(false); |
| } |
| } |
| } |
| |
| //----------Calculating trip count on one level------------------------------- |
| |
| // Calculate trip count on this loop level. |
| // We do this either for a rectangular loop nest, |
| // or after an adjustment bringing the loops to a parallelepiped shape. |
| // This number should not depend on the value of outer IV |
| // even if the formular has lb1 and ub1. |
| // Note: for non-rectangular loops don't use span for this, it's too big. |
| |
| template <typename T> |
| kmp_loop_nest_iv_t kmp_calculate_trip_count_XX( |
| /*in/out*/ bounds_infoXX_template<T> *bounds) { |
| |
| if (bounds->comparison == comparison_t::comp_less_or_eq) { |
| if (bounds->ub0 < bounds->lb0) { |
| // Note: after this we don't need to calculate inner loops, |
| // but that should be an edge case: |
| bounds->trip_count = 0; |
| } else { |
| // ub - lb may exceed signed type range; we need to cast to |
| // kmp_loop_nest_iv_t anyway |
| bounds->trip_count = |
| static_cast<kmp_loop_nest_iv_t>(bounds->ub0 - bounds->lb0) / |
| __kmp_abs(bounds->step) + |
| 1; |
| } |
| } else if (bounds->comparison == comparison_t::comp_greater_or_eq) { |
| if (bounds->lb0 < bounds->ub0) { |
| // Note: after this we don't need to calculate inner loops, |
| // but that should be an edge case: |
| bounds->trip_count = 0; |
| } else { |
| // lb - ub may exceed signed type range; we need to cast to |
| // kmp_loop_nest_iv_t anyway |
| bounds->trip_count = |
| static_cast<kmp_loop_nest_iv_t>(bounds->lb0 - bounds->ub0) / |
| __kmp_abs(bounds->step) + |
| 1; |
| } |
| } else { |
| KMP_ASSERT(false); |
| } |
| return bounds->trip_count; |
| } |
| |
| // Calculate trip count on this loop level. |
| kmp_loop_nest_iv_t kmp_calculate_trip_count(/*in/out*/ bounds_info_t *bounds) { |
| |
| kmp_loop_nest_iv_t trip_count = 0; |
| |
| switch (bounds->loop_type) { |
| case loop_type_t::loop_type_int32: |
| trip_count = kmp_calculate_trip_count_XX<kmp_int32>( |
| /*in/out*/ (bounds_infoXX_template<kmp_int32> *)(bounds)); |
| break; |
| case loop_type_t::loop_type_uint32: |
| trip_count = kmp_calculate_trip_count_XX<kmp_uint32>( |
| /*in/out*/ (bounds_infoXX_template<kmp_uint32> *)(bounds)); |
| break; |
| case loop_type_t::loop_type_int64: |
| trip_count = kmp_calculate_trip_count_XX<kmp_int64>( |
| /*in/out*/ (bounds_infoXX_template<kmp_int64> *)(bounds)); |
| break; |
| case loop_type_t::loop_type_uint64: |
| trip_count = kmp_calculate_trip_count_XX<kmp_uint64>( |
| /*in/out*/ (bounds_infoXX_template<kmp_uint64> *)(bounds)); |
| break; |
| default: |
| KMP_ASSERT(false); |
| } |
| |
| return trip_count; |
| } |
| |
| //----------Trim original iv according to its type---------------------------- |
| |
| // Trim original iv according to its type. |
| // Return kmp_uint64 value which can be easily used in all internal calculations |
| // And can be statically cast back to original type in user code. |
| kmp_uint64 kmp_fix_iv(loop_type_t loop_iv_type, kmp_uint64 original_iv) { |
| kmp_uint64 res = 0; |
| |
| switch (loop_iv_type) { |
| case loop_type_t::loop_type_int8: |
| res = static_cast<kmp_uint64>(static_cast<kmp_int8>(original_iv)); |
| break; |
| case loop_type_t::loop_type_uint8: |
| res = static_cast<kmp_uint64>(static_cast<kmp_uint8>(original_iv)); |
| break; |
| case loop_type_t::loop_type_int16: |
| res = static_cast<kmp_uint64>(static_cast<kmp_int16>(original_iv)); |
| break; |
| case loop_type_t::loop_type_uint16: |
| res = static_cast<kmp_uint64>(static_cast<kmp_uint16>(original_iv)); |
| break; |
| case loop_type_t::loop_type_int32: |
| res = static_cast<kmp_uint64>(static_cast<kmp_int32>(original_iv)); |
| break; |
| case loop_type_t::loop_type_uint32: |
| res = static_cast<kmp_uint64>(static_cast<kmp_uint32>(original_iv)); |
| break; |
| case loop_type_t::loop_type_int64: |
| res = static_cast<kmp_uint64>(static_cast<kmp_int64>(original_iv)); |
| break; |
| case loop_type_t::loop_type_uint64: |
| res = static_cast<kmp_uint64>(original_iv); |
| break; |
| default: |
| KMP_ASSERT(false); |
| } |
| |
| return res; |
| } |
| |
| //----------Compare two IVs (remember they have a type)----------------------- |
| |
| bool kmp_ivs_eq(loop_type_t loop_iv_type, kmp_uint64 original_iv1, |
| kmp_uint64 original_iv2) { |
| bool res = false; |
| |
| switch (loop_iv_type) { |
| case loop_type_t::loop_type_int8: |
| res = static_cast<kmp_int8>(original_iv1) == |
| static_cast<kmp_int8>(original_iv2); |
| break; |
| case loop_type_t::loop_type_uint8: |
| res = static_cast<kmp_uint8>(original_iv1) == |
| static_cast<kmp_uint8>(original_iv2); |
| break; |
| case loop_type_t::loop_type_int16: |
| res = static_cast<kmp_int16>(original_iv1) == |
| static_cast<kmp_int16>(original_iv2); |
| break; |
| case loop_type_t::loop_type_uint16: |
| res = static_cast<kmp_uint16>(original_iv1) == |
| static_cast<kmp_uint16>(original_iv2); |
| break; |
| case loop_type_t::loop_type_int32: |
| res = static_cast<kmp_int32>(original_iv1) == |
| static_cast<kmp_int32>(original_iv2); |
| break; |
| case loop_type_t::loop_type_uint32: |
| res = static_cast<kmp_uint32>(original_iv1) == |
| static_cast<kmp_uint32>(original_iv2); |
| break; |
| case loop_type_t::loop_type_int64: |
| res = static_cast<kmp_int64>(original_iv1) == |
| static_cast<kmp_int64>(original_iv2); |
| break; |
| case loop_type_t::loop_type_uint64: |
| res = static_cast<kmp_uint64>(original_iv1) == |
| static_cast<kmp_uint64>(original_iv2); |
| break; |
| default: |
| KMP_ASSERT(false); |
| } |
| |
| return res; |
| } |
| |
| //----------Calculate original iv on one level-------------------------------- |
| |
| // Return true if the point fits into upper bounds on this level, |
| // false otherwise |
| template <typename T> |
| bool kmp_iv_is_in_upper_bound_XX(const bounds_infoXX_template<T> *bounds, |
| const kmp_point_t original_ivs, |
| kmp_index_t ind) { |
| |
| T iv = static_cast<T>(original_ivs[ind]); |
| T outer_iv = static_cast<T>(original_ivs[bounds->outer_iv]); |
| |
| if (((bounds->comparison == comparison_t::comp_less_or_eq) && |
| (iv > (bounds->ub0 + bounds->ub1 * outer_iv))) || |
| ((bounds->comparison == comparison_t::comp_greater_or_eq) && |
| (iv < (bounds->ub0 + bounds->ub1 * outer_iv)))) { |
| // The calculated point is outside of loop upper boundary: |
| return false; |
| } |
| |
| return true; |
| } |
| |
| // Calculate one iv corresponding to iteration on the level ind. |
| // Return true if it fits into lower-upper bounds on this level |
| // (if not, we need to re-calculate) |
| template <typename T> |
| bool kmp_calc_one_iv_XX(const bounds_infoXX_template<T> *bounds, |
| /*in/out*/ kmp_point_t original_ivs, |
| const kmp_iterations_t iterations, kmp_index_t ind, |
| bool start_with_lower_bound, bool checkBounds) { |
| |
| kmp_uint64 temp = 0; |
| T outer_iv = static_cast<T>(original_ivs[bounds->outer_iv]); |
| |
| if (start_with_lower_bound) { |
| // we moved to the next iteration on one of outer loops, should start |
| // with the lower bound here: |
| temp = bounds->lb0 + bounds->lb1 * outer_iv; |
| } else { |
| auto iteration = iterations[ind]; |
| temp = bounds->lb0 + bounds->lb1 * outer_iv + iteration * bounds->step; |
| } |
| |
| // Now trim original iv according to its type: |
| original_ivs[ind] = kmp_fix_iv(bounds->loop_iv_type, temp); |
| |
| if (checkBounds) { |
| return kmp_iv_is_in_upper_bound_XX(bounds, original_ivs, ind); |
| } else { |
| return true; |
| } |
| } |
| |
| bool kmp_calc_one_iv(const bounds_info_t *bounds, |
| /*in/out*/ kmp_point_t original_ivs, |
| const kmp_iterations_t iterations, kmp_index_t ind, |
| bool start_with_lower_bound, bool checkBounds) { |
| |
| switch (bounds->loop_type) { |
| case loop_type_t::loop_type_int32: |
| return kmp_calc_one_iv_XX<kmp_int32>( |
| (bounds_infoXX_template<kmp_int32> *)(bounds), |
| /*in/out*/ original_ivs, iterations, ind, start_with_lower_bound, |
| checkBounds); |
| break; |
| case loop_type_t::loop_type_uint32: |
| return kmp_calc_one_iv_XX<kmp_uint32>( |
| (bounds_infoXX_template<kmp_uint32> *)(bounds), |
| /*in/out*/ original_ivs, iterations, ind, start_with_lower_bound, |
| checkBounds); |
| break; |
| case loop_type_t::loop_type_int64: |
| return kmp_calc_one_iv_XX<kmp_int64>( |
| (bounds_infoXX_template<kmp_int64> *)(bounds), |
| /*in/out*/ original_ivs, iterations, ind, start_with_lower_bound, |
| checkBounds); |
| break; |
| case loop_type_t::loop_type_uint64: |
| return kmp_calc_one_iv_XX<kmp_uint64>( |
| (bounds_infoXX_template<kmp_uint64> *)(bounds), |
| /*in/out*/ original_ivs, iterations, ind, start_with_lower_bound, |
| checkBounds); |
| break; |
| default: |
| KMP_ASSERT(false); |
| return false; |
| } |
| } |
| |
| //----------Calculate original iv on one level for rectangular loop nest------ |
| |
| // Calculate one iv corresponding to iteration on the level ind. |
| // Return true if it fits into lower-upper bounds on this level |
| // (if not, we need to re-calculate) |
| template <typename T> |
| void kmp_calc_one_iv_rectang_XX(const bounds_infoXX_template<T> *bounds, |
| /*in/out*/ kmp_uint64 *original_ivs, |
| const kmp_iterations_t iterations, |
| kmp_index_t ind) { |
| |
| auto iteration = iterations[ind]; |
| |
| kmp_uint64 temp = |
| bounds->lb0 + |
| bounds->lb1 * static_cast<T>(original_ivs[bounds->outer_iv]) + |
| iteration * bounds->step; |
| |
| // Now trim original iv according to its type: |
| original_ivs[ind] = kmp_fix_iv(bounds->loop_iv_type, temp); |
| } |
| |
| void kmp_calc_one_iv_rectang(const bounds_info_t *bounds, |
| /*in/out*/ kmp_uint64 *original_ivs, |
| const kmp_iterations_t iterations, |
| kmp_index_t ind) { |
| |
| switch (bounds->loop_type) { |
| case loop_type_t::loop_type_int32: |
| kmp_calc_one_iv_rectang_XX<kmp_int32>( |
| (bounds_infoXX_template<kmp_int32> *)(bounds), |
| /*in/out*/ original_ivs, iterations, ind); |
| break; |
| case loop_type_t::loop_type_uint32: |
| kmp_calc_one_iv_rectang_XX<kmp_uint32>( |
| (bounds_infoXX_template<kmp_uint32> *)(bounds), |
| /*in/out*/ original_ivs, iterations, ind); |
| break; |
| case loop_type_t::loop_type_int64: |
| kmp_calc_one_iv_rectang_XX<kmp_int64>( |
| (bounds_infoXX_template<kmp_int64> *)(bounds), |
| /*in/out*/ original_ivs, iterations, ind); |
| break; |
| case loop_type_t::loop_type_uint64: |
| kmp_calc_one_iv_rectang_XX<kmp_uint64>( |
| (bounds_infoXX_template<kmp_uint64> *)(bounds), |
| /*in/out*/ original_ivs, iterations, ind); |
| break; |
| default: |
| KMP_ASSERT(false); |
| } |
| } |
| |
| //---------------------------------------------------------------------------- |
| // Rectangular loop nest |
| //---------------------------------------------------------------------------- |
| |
| //----------Canonicalize loop nest and calculate trip count------------------- |
| |
| // Canonicalize loop nest and calculate overall trip count. |
| // "bounds_nest" has to be allocated per thread. |
| // API will modify original bounds_nest array to bring it to a canonical form |
| // (only <= and >=, no !=, <, >). If the original loop nest was already in a |
| // canonical form there will be no changes to bounds in bounds_nest array |
| // (only trip counts will be calculated). |
| // Returns trip count of overall space. |
| extern "C" kmp_loop_nest_iv_t |
| __kmpc_process_loop_nest_rectang(ident_t *loc, kmp_int32 gtid, |
| /*in/out*/ bounds_info_t *original_bounds_nest, |
| kmp_index_t n) { |
| |
| kmp_canonicalize_loop_nest(loc, /*in/out*/ original_bounds_nest, n); |
| |
| kmp_loop_nest_iv_t total = 1; |
| |
| for (kmp_index_t ind = 0; ind < n; ++ind) { |
| auto bounds = &(original_bounds_nest[ind]); |
| |
| kmp_loop_nest_iv_t trip_count = kmp_calculate_trip_count(/*in/out*/ bounds); |
| total *= trip_count; |
| } |
| |
| return total; |
| } |
| |
| //----------Calculate old induction variables--------------------------------- |
| |
| // Calculate old induction variables corresponding to overall new_iv. |
| // Note: original IV will be returned as if it had kmp_uint64 type, |
| // will have to be converted to original type in user code. |
| // Note: trip counts should be already calculated by |
| // __kmpc_process_loop_nest_rectang. |
| // OMPTODO: special case 2, 3 nested loops: either do different |
| // interface without array or possibly template this over n |
| extern "C" void |
| __kmpc_calc_original_ivs_rectang(ident_t *loc, kmp_loop_nest_iv_t new_iv, |
| const bounds_info_t *original_bounds_nest, |
| /*out*/ kmp_uint64 *original_ivs, |
| kmp_index_t n) { |
| |
| CollapseAllocator<kmp_loop_nest_iv_t> iterations(n); |
| |
| // First, calc corresponding iteration in every original loop: |
| for (kmp_index_t ind = n; ind > 0;) { |
| --ind; |
| auto bounds = &(original_bounds_nest[ind]); |
| |
| // should be optimized to OPDIVREM: |
| auto temp = new_iv / bounds->trip_count; |
| auto iteration = new_iv % bounds->trip_count; |
| new_iv = temp; |
| |
| iterations[ind] = iteration; |
| } |
| KMP_ASSERT(new_iv == 0); |
| |
| for (kmp_index_t ind = 0; ind < n; ++ind) { |
| auto bounds = &(original_bounds_nest[ind]); |
| |
| kmp_calc_one_iv_rectang(bounds, /*in/out*/ original_ivs, iterations, ind); |
| } |
| } |
| |
| //---------------------------------------------------------------------------- |
| // Non-rectangular loop nest |
| //---------------------------------------------------------------------------- |
| |
| //----------Calculate maximum possible span of iv values on one level--------- |
| |
| // Calculate span for IV on this loop level for "<=" case. |
| // Note: it's for <= on this loop nest level, so lower bound should be smallest |
| // value, upper bound should be the biggest value. If the loop won't execute, |
| // 'smallest' may be bigger than 'biggest', but we'd better not switch them |
| // around. |
| template <typename T> |
| void kmp_calc_span_lessoreq_XX( |
| /* in/out*/ bounds_info_internalXX_template<T> *bounds, |
| /* in/out*/ bounds_info_internal_t *bounds_nest) { |
| |
| typedef typename traits_t<T>::unsigned_t UT; |
| // typedef typename traits_t<T>::signed_t ST; |
| |
| // typedef typename big_span_t span_t; |
| typedef T span_t; |
| |
| auto &bbounds = bounds->b; |
| |
| if ((bbounds.lb1 != 0) || (bbounds.ub1 != 0)) { |
| // This dimention depends on one of previous ones; can't be the outermost |
| // one. |
| bounds_info_internalXX_template<T> *previous = |
| reinterpret_cast<bounds_info_internalXX_template<T> *>( |
| &(bounds_nest[bbounds.outer_iv])); |
| |
| // OMPTODO: assert that T is compatible with loop variable type on |
| // 'previous' loop |
| |
| { |
| span_t bound_candidate1 = |
| bbounds.lb0 + bbounds.lb1 * previous->span_smallest; |
| span_t bound_candidate2 = |
| bbounds.lb0 + bbounds.lb1 * previous->span_biggest; |
| if (bound_candidate1 < bound_candidate2) { |
| bounds->span_smallest = bound_candidate1; |
| } else { |
| bounds->span_smallest = bound_candidate2; |
| } |
| } |
| |
| { |
| // We can't adjust the upper bound with respect to step, because |
| // lower bound might be off after adjustments |
| |
| span_t bound_candidate1 = |
| bbounds.ub0 + bbounds.ub1 * previous->span_smallest; |
| span_t bound_candidate2 = |
| bbounds.ub0 + bbounds.ub1 * previous->span_biggest; |
| if (bound_candidate1 < bound_candidate2) { |
| bounds->span_biggest = bound_candidate2; |
| } else { |
| bounds->span_biggest = bound_candidate1; |
| } |
| } |
| } else { |
| // Rectangular: |
| bounds->span_smallest = bbounds.lb0; |
| bounds->span_biggest = bbounds.ub0; |
| } |
| if (!bounds->loop_bounds_adjusted) { |
| // Here it's safe to reduce the space to the multiply of step. |
| // OMPTODO: check if the formular is correct. |
| // Also check if it would be safe to do this if we didn't adjust left side. |
| bounds->span_biggest -= |
| (static_cast<UT>(bbounds.ub0 - bbounds.lb0)) % bbounds.step; // abs? |
| } |
| } |
| |
| // Calculate span for IV on this loop level for ">=" case. |
| template <typename T> |
| void kmp_calc_span_greateroreq_XX( |
| /* in/out*/ bounds_info_internalXX_template<T> *bounds, |
| /* in/out*/ bounds_info_internal_t *bounds_nest) { |
| |
| typedef typename traits_t<T>::unsigned_t UT; |
| // typedef typename traits_t<T>::signed_t ST; |
| |
| // typedef typename big_span_t span_t; |
| typedef T span_t; |
| |
| auto &bbounds = bounds->b; |
| |
| if ((bbounds.lb1 != 0) || (bbounds.ub1 != 0)) { |
| // This dimention depends on one of previous ones; can't be the outermost |
| // one. |
| bounds_info_internalXX_template<T> *previous = |
| reinterpret_cast<bounds_info_internalXX_template<T> *>( |
| &(bounds_nest[bbounds.outer_iv])); |
| |
| // OMPTODO: assert that T is compatible with loop variable type on |
| // 'previous' loop |
| |
| { |
| span_t bound_candidate1 = |
| bbounds.lb0 + bbounds.lb1 * previous->span_smallest; |
| span_t bound_candidate2 = |
| bbounds.lb0 + bbounds.lb1 * previous->span_biggest; |
| if (bound_candidate1 >= bound_candidate2) { |
| bounds->span_smallest = bound_candidate1; |
| } else { |
| bounds->span_smallest = bound_candidate2; |
| } |
| } |
| |
| { |
| // We can't adjust the upper bound with respect to step, because |
| // lower bound might be off after adjustments |
| |
| span_t bound_candidate1 = |
| bbounds.ub0 + bbounds.ub1 * previous->span_smallest; |
| span_t bound_candidate2 = |
| bbounds.ub0 + bbounds.ub1 * previous->span_biggest; |
| if (bound_candidate1 >= bound_candidate2) { |
| bounds->span_biggest = bound_candidate2; |
| } else { |
| bounds->span_biggest = bound_candidate1; |
| } |
| } |
| |
| } else { |
| // Rectangular: |
| bounds->span_biggest = bbounds.lb0; |
| bounds->span_smallest = bbounds.ub0; |
| } |
| if (!bounds->loop_bounds_adjusted) { |
| // Here it's safe to reduce the space to the multiply of step. |
| // OMPTODO: check if the formular is correct. |
| // Also check if it would be safe to do this if we didn't adjust left side. |
| bounds->span_biggest -= |
| (static_cast<UT>(bbounds.ub0 - bbounds.lb0)) % bbounds.step; // abs? |
| } |
| } |
| |
| // Calculate maximum possible span for IV on this loop level. |
| template <typename T> |
| void kmp_calc_span_XX( |
| /* in/out*/ bounds_info_internalXX_template<T> *bounds, |
| /* in/out*/ bounds_info_internal_t *bounds_nest) { |
| |
| if (bounds->b.comparison == comparison_t::comp_less_or_eq) { |
| kmp_calc_span_lessoreq_XX(/* in/out*/ bounds, /* in/out*/ bounds_nest); |
| } else { |
| KMP_ASSERT(bounds->b.comparison == comparison_t::comp_greater_or_eq); |
| kmp_calc_span_greateroreq_XX(/* in/out*/ bounds, /* in/out*/ bounds_nest); |
| } |
| } |
| |
| //----------All initial processing of the loop nest--------------------------- |
| |
| // Calculate new bounds for this loop level. |
| // To be able to work with the nest we need to get it to a parallelepiped shape. |
| // We need to stay in the original range of values, so that there will be no |
| // overflow, for that we'll adjust both upper and lower bounds as needed. |
| template <typename T> |
| void kmp_calc_new_bounds_XX( |
| /* in/out*/ bounds_info_internalXX_template<T> *bounds, |
| /* in/out*/ bounds_info_internal_t *bounds_nest) { |
| |
| auto &bbounds = bounds->b; |
| |
| if (bbounds.lb1 == bbounds.ub1) { |
| // Already parallel, no need to adjust: |
| bounds->loop_bounds_adjusted = false; |
| } else { |
| bounds->loop_bounds_adjusted = true; |
| |
| T old_lb1 = bbounds.lb1; |
| T old_ub1 = bbounds.ub1; |
| |
| if (__kmp_sign(old_lb1) != __kmp_sign(old_ub1)) { |
| // With this shape we can adjust to a rectangle: |
| bbounds.lb1 = 0; |
| bbounds.ub1 = 0; |
| } else { |
| // get upper and lower bounds to be parallel |
| // with values in the old range. |
| // Note: abs didn't work here. |
| if (((old_lb1 < 0) && (old_lb1 < old_ub1)) || |
| ((old_lb1 > 0) && (old_lb1 > old_ub1))) { |
| bbounds.lb1 = old_ub1; |
| } else { |
| bbounds.ub1 = old_lb1; |
| } |
| } |
| |
| // Now need to adjust lb0, ub0, otherwise in some cases space will shrink. |
| // The idea here that for this IV we are now getting the same span |
| // irrespective of the previous IV value. |
| bounds_info_internalXX_template<T> *previous = |
| reinterpret_cast<bounds_info_internalXX_template<T> *>( |
| &bounds_nest[bbounds.outer_iv]); |
| |
| if (bbounds.comparison == comparison_t::comp_less_or_eq) { |
| if (old_lb1 < bbounds.lb1) { |
| KMP_ASSERT(old_lb1 < 0); |
| // The length is good on outer_iv biggest number, |
| // can use it to find where to move the lower bound: |
| |
| T sub = (bbounds.lb1 - old_lb1) * previous->span_biggest; |
| bbounds.lb0 -= sub; // OMPTODO: what if it'll go out of unsigned space? |
| // e.g. it was 0?? (same below) |
| } else if (old_lb1 > bbounds.lb1) { |
| // still need to move lower bound: |
| T add = (old_lb1 - bbounds.lb1) * previous->span_smallest; |
| bbounds.lb0 += add; |
| } |
| |
| if (old_ub1 > bbounds.ub1) { |
| KMP_ASSERT(old_ub1 > 0); |
| // The length is good on outer_iv biggest number, |
| // can use it to find where to move upper bound: |
| |
| T add = (old_ub1 - bbounds.ub1) * previous->span_biggest; |
| bbounds.ub0 += add; |
| } else if (old_ub1 < bbounds.ub1) { |
| // still need to move upper bound: |
| T sub = (bbounds.ub1 - old_ub1) * previous->span_smallest; |
| bbounds.ub0 -= sub; |
| } |
| } else { |
| KMP_ASSERT(bbounds.comparison == comparison_t::comp_greater_or_eq); |
| if (old_lb1 < bbounds.lb1) { |
| KMP_ASSERT(old_lb1 < 0); |
| T sub = (bbounds.lb1 - old_lb1) * previous->span_smallest; |
| bbounds.lb0 -= sub; |
| } else if (old_lb1 > bbounds.lb1) { |
| T add = (old_lb1 - bbounds.lb1) * previous->span_biggest; |
| bbounds.lb0 += add; |
| } |
| |
| if (old_ub1 > bbounds.ub1) { |
| KMP_ASSERT(old_ub1 > 0); |
| T add = (old_ub1 - bbounds.ub1) * previous->span_smallest; |
| bbounds.ub0 += add; |
| } else if (old_ub1 < bbounds.ub1) { |
| T sub = (bbounds.ub1 - old_ub1) * previous->span_biggest; |
| bbounds.ub0 -= sub; |
| } |
| } |
| } |
| } |
| |
| // Do all processing for one canonicalized loop in the nest |
| // (assuming that outer loops already were processed): |
| template <typename T> |
| kmp_loop_nest_iv_t kmp_process_one_loop_XX( |
| /* in/out*/ bounds_info_internalXX_template<T> *bounds, |
| /*in/out*/ bounds_info_internal_t *bounds_nest) { |
| |
| kmp_calc_new_bounds_XX(/* in/out*/ bounds, /* in/out*/ bounds_nest); |
| kmp_calc_span_XX(/* in/out*/ bounds, /* in/out*/ bounds_nest); |
| return kmp_calculate_trip_count_XX(/*in/out*/ &(bounds->b)); |
| } |
| |
| // Non-rectangular loop nest, canonicalized to use <= or >=. |
| // Process loop nest to have a parallelepiped shape, |
| // calculate biggest spans for IV's on all levels and calculate overall trip |
| // count. "bounds_nest" has to be allocated per thread. |
| // Returns overall trip count (for adjusted space). |
| kmp_loop_nest_iv_t kmp_process_loop_nest( |
| /*in/out*/ bounds_info_internal_t *bounds_nest, kmp_index_t n) { |
| |
| kmp_loop_nest_iv_t total = 1; |
| |
| for (kmp_index_t ind = 0; ind < n; ++ind) { |
| auto bounds = &(bounds_nest[ind]); |
| kmp_loop_nest_iv_t trip_count = 0; |
| |
| switch (bounds->b.loop_type) { |
| case loop_type_t::loop_type_int32: |
| trip_count = kmp_process_one_loop_XX<kmp_int32>( |
| /*in/out*/ (bounds_info_internalXX_template<kmp_int32> *)(bounds), |
| /*in/out*/ bounds_nest); |
| break; |
| case loop_type_t::loop_type_uint32: |
| trip_count = kmp_process_one_loop_XX<kmp_uint32>( |
| /*in/out*/ (bounds_info_internalXX_template<kmp_uint32> *)(bounds), |
| /*in/out*/ bounds_nest); |
| break; |
| case loop_type_t::loop_type_int64: |
| trip_count = kmp_process_one_loop_XX<kmp_int64>( |
| /*in/out*/ (bounds_info_internalXX_template<kmp_int64> *)(bounds), |
| /*in/out*/ bounds_nest); |
| break; |
| case loop_type_t::loop_type_uint64: |
| trip_count = kmp_process_one_loop_XX<kmp_uint64>( |
| /*in/out*/ (bounds_info_internalXX_template<kmp_uint64> *)(bounds), |
| /*in/out*/ bounds_nest); |
| break; |
| default: |
| KMP_ASSERT(false); |
| } |
| total *= trip_count; |
| } |
| |
| return total; |
| } |
| |
| //----------Calculate iterations (in the original or updated space)----------- |
| |
| // Calculate number of iterations in original or updated space resulting in |
| // original_ivs[ind] (only on this level, non-negative) |
| // (not counting initial iteration) |
| template <typename T> |
| kmp_loop_nest_iv_t |
| kmp_calc_number_of_iterations_XX(const bounds_infoXX_template<T> *bounds, |
| const kmp_point_t original_ivs, |
| kmp_index_t ind) { |
| |
| kmp_loop_nest_iv_t iterations = 0; |
| |
| if (bounds->comparison == comparison_t::comp_less_or_eq) { |
| iterations = |
| (static_cast<T>(original_ivs[ind]) - bounds->lb0 - |
| bounds->lb1 * static_cast<T>(original_ivs[bounds->outer_iv])) / |
| __kmp_abs(bounds->step); |
| } else { |
| KMP_DEBUG_ASSERT(bounds->comparison == comparison_t::comp_greater_or_eq); |
| iterations = (bounds->lb0 + |
| bounds->lb1 * static_cast<T>(original_ivs[bounds->outer_iv]) - |
| static_cast<T>(original_ivs[ind])) / |
| __kmp_abs(bounds->step); |
| } |
| |
| return iterations; |
| } |
| |
| // Calculate number of iterations in the original or updated space resulting in |
| // original_ivs[ind] (only on this level, non-negative) |
| kmp_loop_nest_iv_t kmp_calc_number_of_iterations(const bounds_info_t *bounds, |
| const kmp_point_t original_ivs, |
| kmp_index_t ind) { |
| |
| switch (bounds->loop_type) { |
| case loop_type_t::loop_type_int32: |
| return kmp_calc_number_of_iterations_XX<kmp_int32>( |
| (bounds_infoXX_template<kmp_int32> *)(bounds), original_ivs, ind); |
| break; |
| case loop_type_t::loop_type_uint32: |
| return kmp_calc_number_of_iterations_XX<kmp_uint32>( |
| (bounds_infoXX_template<kmp_uint32> *)(bounds), original_ivs, ind); |
| break; |
| case loop_type_t::loop_type_int64: |
| return kmp_calc_number_of_iterations_XX<kmp_int64>( |
| (bounds_infoXX_template<kmp_int64> *)(bounds), original_ivs, ind); |
| break; |
| case loop_type_t::loop_type_uint64: |
| return kmp_calc_number_of_iterations_XX<kmp_uint64>( |
| (bounds_infoXX_template<kmp_uint64> *)(bounds), original_ivs, ind); |
| break; |
| default: |
| KMP_ASSERT(false); |
| return 0; |
| } |
| } |
| |
| //----------Calculate new iv corresponding to original ivs-------------------- |
| |
| // We got a point in the original loop nest. |
| // Take updated bounds and calculate what new_iv will correspond to this point. |
| // When we are getting original IVs from new_iv, we have to adjust to fit into |
| // original loops bounds. Getting new_iv for the adjusted original IVs will help |
| // with making more chunks non-empty. |
| kmp_loop_nest_iv_t |
| kmp_calc_new_iv_from_original_ivs(const bounds_info_internal_t *bounds_nest, |
| const kmp_point_t original_ivs, |
| kmp_index_t n) { |
| |
| kmp_loop_nest_iv_t new_iv = 0; |
| |
| for (kmp_index_t ind = 0; ind < n; ++ind) { |
| auto bounds = &(bounds_nest[ind].b); |
| |
| new_iv = new_iv * bounds->trip_count + |
| kmp_calc_number_of_iterations(bounds, original_ivs, ind); |
| } |
| |
| return new_iv; |
| } |
| |
| //----------Calculate original ivs for provided iterations-------------------- |
| |
| // Calculate original IVs for provided iterations, assuming iterations are |
| // calculated in the original space. |
| // Loop nest is in canonical form (with <= / >=). |
| bool kmp_calc_original_ivs_from_iterations( |
| const bounds_info_t *original_bounds_nest, kmp_index_t n, |
| /*in/out*/ kmp_point_t original_ivs, |
| /*in/out*/ kmp_iterations_t iterations, kmp_index_t ind) { |
| |
| kmp_index_t lengthened_ind = n; |
| |
| for (; ind < n;) { |
| auto bounds = &(original_bounds_nest[ind]); |
| bool good = kmp_calc_one_iv(bounds, /*in/out*/ original_ivs, iterations, |
| ind, (lengthened_ind < ind), true); |
| |
| if (!good) { |
| // The calculated iv value is too big (or too small for >=): |
| if (ind == 0) { |
| // Space is empty: |
| return false; |
| } else { |
| // Go to next iteration on the outer loop: |
| --ind; |
| ++iterations[ind]; |
| lengthened_ind = ind; |
| for (kmp_index_t i = ind + 1; i < n; ++i) { |
| iterations[i] = 0; |
| } |
| continue; |
| } |
| } |
| ++ind; |
| } |
| |
| return true; |
| } |
| |
| //----------Calculate original ivs for the beginning of the loop nest--------- |
| |
| // Calculate IVs for the beginning of the loop nest. |
| // Note: lower bounds of all loops may not work - |
| // if on some of the iterations of the outer loops inner loops are empty. |
| // Loop nest is in canonical form (with <= / >=). |
| bool kmp_calc_original_ivs_for_start(const bounds_info_t *original_bounds_nest, |
| kmp_index_t n, |
| /*out*/ kmp_point_t original_ivs) { |
| |
| // Iterations in the original space, multiplied by step: |
| CollapseAllocator<kmp_loop_nest_iv_t> iterations(n); |
| for (kmp_index_t ind = n; ind > 0;) { |
| --ind; |
| iterations[ind] = 0; |
| } |
| |
| // Now calculate the point: |
| bool b = kmp_calc_original_ivs_from_iterations(original_bounds_nest, n, |
| /*in/out*/ original_ivs, |
| /*in/out*/ iterations, 0); |
| return b; |
| } |
| |
| //----------Calculate next point in the original loop space------------------- |
| |
| // From current set of original IVs calculate next point. |
| // Return false if there is no next point in the loop bounds. |
| bool kmp_calc_next_original_ivs(const bounds_info_t *original_bounds_nest, |
| kmp_index_t n, const kmp_point_t original_ivs, |
| /*out*/ kmp_point_t next_original_ivs) { |
| // Iterations in the original space, multiplied by step (so can be negative): |
| CollapseAllocator<kmp_loop_nest_iv_t> iterations(n); |
| // First, calc corresponding iteration in every original loop: |
| for (kmp_index_t ind = 0; ind < n; ++ind) { |
| auto bounds = &(original_bounds_nest[ind]); |
| iterations[ind] = kmp_calc_number_of_iterations(bounds, original_ivs, ind); |
| } |
| |
| for (kmp_index_t ind = 0; ind < n; ++ind) { |
| next_original_ivs[ind] = original_ivs[ind]; |
| } |
| |
| // Next add one step to the iterations on the inner-most level, and see if we |
| // need to move up the nest: |
| kmp_index_t ind = n - 1; |
| ++iterations[ind]; |
| |
| bool b = kmp_calc_original_ivs_from_iterations( |
| original_bounds_nest, n, /*in/out*/ next_original_ivs, iterations, ind); |
| |
| return b; |
| } |
| |
| //----------Calculate chunk end in the original loop space-------------------- |
| |
| // For one level calculate old induction variable corresponding to overall |
| // new_iv for the chunk end. |
| // Return true if it fits into upper bound on this level |
| // (if not, we need to re-calculate) |
| template <typename T> |
| bool kmp_calc_one_iv_for_chunk_end_XX( |
| const bounds_infoXX_template<T> *bounds, |
| const bounds_infoXX_template<T> *updated_bounds, |
| /*in/out*/ kmp_point_t original_ivs, const kmp_iterations_t iterations, |
| kmp_index_t ind, bool start_with_lower_bound, bool compare_with_start, |
| const kmp_point_t original_ivs_start) { |
| |
| // typedef std::conditional<std::is_signed<T>::value, kmp_int64, kmp_uint64> |
| // big_span_t; |
| |
| // OMPTODO: is it good enough, or do we need ST or do we need big_span_t? |
| T temp = 0; |
| |
| T outer_iv = static_cast<T>(original_ivs[bounds->outer_iv]); |
| |
| if (start_with_lower_bound) { |
| // we moved to the next iteration on one of outer loops, may as well use |
| // the lower bound here: |
| temp = bounds->lb0 + bounds->lb1 * outer_iv; |
| } else { |
| // Start in expanded space, but: |
| // - we need to hit original space lower bound, so need to account for |
| // that |
| // - we have to go into original space, even if that means adding more |
| // iterations than was planned |
| // - we have to go past (or equal to) previous point (which is the chunk |
| // starting point) |
| |
| auto iteration = iterations[ind]; |
| |
| auto step = bounds->step; |
| |
| // In case of >= it's negative: |
| auto accountForStep = |
| ((bounds->lb0 + bounds->lb1 * outer_iv) - |
| (updated_bounds->lb0 + updated_bounds->lb1 * outer_iv)) % |
| step; |
| |
| temp = updated_bounds->lb0 + updated_bounds->lb1 * outer_iv + |
| accountForStep + iteration * step; |
| |
| if (((bounds->comparison == comparison_t::comp_less_or_eq) && |
| (temp < (bounds->lb0 + bounds->lb1 * outer_iv))) || |
| ((bounds->comparison == comparison_t::comp_greater_or_eq) && |
| (temp > (bounds->lb0 + bounds->lb1 * outer_iv)))) { |
| // Too small (or too big), didn't reach the original lower bound. Use |
| // heuristic: |
| temp = bounds->lb0 + bounds->lb1 * outer_iv + iteration / 2 * step; |
| } |
| |
| if (compare_with_start) { |
| |
| T start = static_cast<T>(original_ivs_start[ind]); |
| |
| temp = kmp_fix_iv(bounds->loop_iv_type, temp); |
| |
| // On all previous levels start of the chunk is same as the end, need to |
| // be really careful here: |
| if (((bounds->comparison == comparison_t::comp_less_or_eq) && |
| (temp < start)) || |
| ((bounds->comparison == comparison_t::comp_greater_or_eq) && |
| (temp > start))) { |
| // End of the chunk can't be smaller (for >= bigger) than it's start. |
| // Use heuristic: |
| temp = start + iteration / 4 * step; |
| } |
| } |
| } |
| |
| original_ivs[ind] = temp = kmp_fix_iv(bounds->loop_iv_type, temp); |
| |
| if (((bounds->comparison == comparison_t::comp_less_or_eq) && |
| (temp > (bounds->ub0 + bounds->ub1 * outer_iv))) || |
| ((bounds->comparison == comparison_t::comp_greater_or_eq) && |
| (temp < (bounds->ub0 + bounds->ub1 * outer_iv)))) { |
| // Too big (or too small for >=). |
| return false; |
| } |
| |
| return true; |
| } |
| |
| // For one level calculate old induction variable corresponding to overall |
| // new_iv for the chunk end. |
| bool kmp_calc_one_iv_for_chunk_end(const bounds_info_t *bounds, |
| const bounds_info_t *updated_bounds, |
| /*in/out*/ kmp_point_t original_ivs, |
| const kmp_iterations_t iterations, |
| kmp_index_t ind, bool start_with_lower_bound, |
| bool compare_with_start, |
| const kmp_point_t original_ivs_start) { |
| |
| switch (bounds->loop_type) { |
| case loop_type_t::loop_type_int32: |
| return kmp_calc_one_iv_for_chunk_end_XX<kmp_int32>( |
| (bounds_infoXX_template<kmp_int32> *)(bounds), |
| (bounds_infoXX_template<kmp_int32> *)(updated_bounds), |
| /*in/out*/ |
| original_ivs, iterations, ind, start_with_lower_bound, |
| compare_with_start, original_ivs_start); |
| break; |
| case loop_type_t::loop_type_uint32: |
| return kmp_calc_one_iv_for_chunk_end_XX<kmp_uint32>( |
| (bounds_infoXX_template<kmp_uint32> *)(bounds), |
| (bounds_infoXX_template<kmp_uint32> *)(updated_bounds), |
| /*in/out*/ |
| original_ivs, iterations, ind, start_with_lower_bound, |
| compare_with_start, original_ivs_start); |
| break; |
| case loop_type_t::loop_type_int64: |
| return kmp_calc_one_iv_for_chunk_end_XX<kmp_int64>( |
| (bounds_infoXX_template<kmp_int64> *)(bounds), |
| (bounds_infoXX_template<kmp_int64> *)(updated_bounds), |
| /*in/out*/ |
| original_ivs, iterations, ind, start_with_lower_bound, |
| compare_with_start, original_ivs_start); |
| break; |
| case loop_type_t::loop_type_uint64: |
| return kmp_calc_one_iv_for_chunk_end_XX<kmp_uint64>( |
| (bounds_infoXX_template<kmp_uint64> *)(bounds), |
| (bounds_infoXX_template<kmp_uint64> *)(updated_bounds), |
| /*in/out*/ |
| original_ivs, iterations, ind, start_with_lower_bound, |
| compare_with_start, original_ivs_start); |
| break; |
| default: |
| KMP_ASSERT(false); |
| return false; |
| } |
| } |
| |
| // Calculate old induction variables corresponding to overall new_iv for the |
| // chunk end. If due to space extension we are getting old IVs outside of the |
| // boundaries, bring them into the boundaries. Need to do this in the runtime, |
| // esp. on the lower bounds side. When getting result need to make sure that the |
| // new chunk starts at next position to old chunk, not overlaps with it (this is |
| // done elsewhere), and need to make sure end of the chunk is further than the |
| // beginning of the chunk. We don't need an exact ending point here, just |
| // something more-or-less close to the desired chunk length, bigger is fine |
| // (smaller would be fine, but we risk going into infinite loop, so do smaller |
| // only at the very end of the space). result: false if could not find the |
| // ending point in the original loop space. In this case the caller can use |
| // original upper bounds as the end of the chunk. Chunk won't be empty, because |
| // it'll have at least the starting point, which is by construction in the |
| // original space. |
| bool kmp_calc_original_ivs_for_chunk_end( |
| const bounds_info_t *original_bounds_nest, kmp_index_t n, |
| const bounds_info_internal_t *updated_bounds_nest, |
| const kmp_point_t original_ivs_start, kmp_loop_nest_iv_t new_iv, |
| /*out*/ kmp_point_t original_ivs) { |
| |
| // Iterations in the expanded space: |
| CollapseAllocator<kmp_loop_nest_iv_t> iterations(n); |
| // First, calc corresponding iteration in every modified loop: |
| for (kmp_index_t ind = n; ind > 0;) { |
| --ind; |
| auto &updated_bounds = updated_bounds_nest[ind]; |
| |
| // should be optimized to OPDIVREM: |
| auto new_ind = new_iv / updated_bounds.b.trip_count; |
| auto iteration = new_iv % updated_bounds.b.trip_count; |
| |
| new_iv = new_ind; |
| iterations[ind] = iteration; |
| } |
| KMP_DEBUG_ASSERT(new_iv == 0); |
| |
| kmp_index_t lengthened_ind = n; |
| kmp_index_t equal_ind = -1; |
| |
| // Next calculate the point, but in original loop nest. |
| for (kmp_index_t ind = 0; ind < n;) { |
| auto bounds = &(original_bounds_nest[ind]); |
| auto updated_bounds = &(updated_bounds_nest[ind].b); |
| |
| bool good = kmp_calc_one_iv_for_chunk_end( |
| bounds, updated_bounds, |
| /*in/out*/ original_ivs, iterations, ind, (lengthened_ind < ind), |
| (equal_ind >= ind - 1), original_ivs_start); |
| |
| if (!good) { |
| // Too big (or too small for >=). |
| if (ind == 0) { |
| // Need to reduce to the end. |
| return false; |
| } else { |
| // Go to next iteration on outer loop: |
| --ind; |
| ++(iterations[ind]); |
| lengthened_ind = ind; |
| if (equal_ind >= lengthened_ind) { |
| // We've changed the number of iterations here, |
| // can't be same anymore: |
| equal_ind = lengthened_ind - 1; |
| } |
| for (kmp_index_t i = ind + 1; i < n; ++i) { |
| iterations[i] = 0; |
| } |
| continue; |
| } |
| } |
| |
| if ((equal_ind == ind - 1) && |
| (kmp_ivs_eq(bounds->loop_iv_type, original_ivs[ind], |
| original_ivs_start[ind]))) { |
| equal_ind = ind; |
| } else if ((equal_ind > ind - 1) && |
| !(kmp_ivs_eq(bounds->loop_iv_type, original_ivs[ind], |
| original_ivs_start[ind]))) { |
| equal_ind = ind - 1; |
| } |
| ++ind; |
| } |
| |
| return true; |
| } |
| |
| //----------Calculate upper bounds for the last chunk------------------------- |
| |
| // Calculate one upper bound for the end. |
| template <typename T> |
| void kmp_calc_one_iv_end_XX(const bounds_infoXX_template<T> *bounds, |
| /*in/out*/ kmp_point_t original_ivs, |
| kmp_index_t ind) { |
| |
| T temp = bounds->ub0 + |
| bounds->ub1 * static_cast<T>(original_ivs[bounds->outer_iv]); |
| |
| original_ivs[ind] = kmp_fix_iv(bounds->loop_iv_type, temp); |
| } |
| |
| void kmp_calc_one_iv_end(const bounds_info_t *bounds, |
| /*in/out*/ kmp_point_t original_ivs, kmp_index_t ind) { |
| |
| switch (bounds->loop_type) { |
| default: |
| KMP_ASSERT(false); |
| break; |
| case loop_type_t::loop_type_int32: |
| kmp_calc_one_iv_end_XX<kmp_int32>( |
| (bounds_infoXX_template<kmp_int32> *)(bounds), |
| /*in/out*/ original_ivs, ind); |
| break; |
| case loop_type_t::loop_type_uint32: |
| kmp_calc_one_iv_end_XX<kmp_uint32>( |
| (bounds_infoXX_template<kmp_uint32> *)(bounds), |
| /*in/out*/ original_ivs, ind); |
| break; |
| case loop_type_t::loop_type_int64: |
| kmp_calc_one_iv_end_XX<kmp_int64>( |
| (bounds_infoXX_template<kmp_int64> *)(bounds), |
| /*in/out*/ original_ivs, ind); |
| break; |
| case loop_type_t::loop_type_uint64: |
| kmp_calc_one_iv_end_XX<kmp_uint64>( |
| (bounds_infoXX_template<kmp_uint64> *)(bounds), |
| /*in/out*/ original_ivs, ind); |
| break; |
| } |
| } |
| |
| // Calculate upper bounds for the last loop iteration. Just use original upper |
| // bounds (adjusted when canonicalized to use <= / >=). No need to check that |
| // this point is in the original space (it's likely not) |
| void kmp_calc_original_ivs_for_end( |
| const bounds_info_t *const original_bounds_nest, kmp_index_t n, |
| /*out*/ kmp_point_t original_ivs) { |
| for (kmp_index_t ind = 0; ind < n; ++ind) { |
| auto bounds = &(original_bounds_nest[ind]); |
| kmp_calc_one_iv_end(bounds, /*in/out*/ original_ivs, ind); |
| } |
| } |
| |
| /************************************************************************** |
| * Identify nested loop structure - loops come in the canonical form |
| * Lower triangle matrix: i = 0; i <= N; i++ {0,0}:{N,0} |
| * j = 0; j <= 0/-1+1*i; j++ {0,0}:{0/-1,1} |
| * Upper Triangle matrix |
| * i = 0; i <= N; i++ {0,0}:{N,0} |
| * j = 0+1*i; j <= N; j++ {0,1}:{N,0} |
| * ************************************************************************/ |
| nested_loop_type_t |
| kmp_identify_nested_loop_structure(/*in*/ bounds_info_t *original_bounds_nest, |
| /*in*/ kmp_index_t n) { |
| // only 2-level nested loops are supported |
| if (n != 2) { |
| return nested_loop_type_unkown; |
| } |
| // loops must be canonical |
| KMP_ASSERT( |
| (original_bounds_nest[0].comparison == comparison_t::comp_less_or_eq) && |
| (original_bounds_nest[1].comparison == comparison_t::comp_less_or_eq)); |
| // check outer loop bounds: for triangular need to be {0,0}:{N,0} |
| kmp_uint64 outer_lb0_u64 = kmp_fix_iv(original_bounds_nest[0].loop_iv_type, |
| original_bounds_nest[0].lb0_u64); |
| kmp_uint64 outer_ub0_u64 = kmp_fix_iv(original_bounds_nest[0].loop_iv_type, |
| original_bounds_nest[0].ub0_u64); |
| kmp_uint64 outer_lb1_u64 = kmp_fix_iv(original_bounds_nest[0].loop_iv_type, |
| original_bounds_nest[0].lb1_u64); |
| kmp_uint64 outer_ub1_u64 = kmp_fix_iv(original_bounds_nest[0].loop_iv_type, |
| original_bounds_nest[0].ub1_u64); |
| if (outer_lb0_u64 != 0 || outer_lb1_u64 != 0 || outer_ub1_u64 != 0) { |
| return nested_loop_type_unkown; |
| } |
| // check inner bounds to determine triangle type |
| kmp_uint64 inner_lb0_u64 = kmp_fix_iv(original_bounds_nest[1].loop_iv_type, |
| original_bounds_nest[1].lb0_u64); |
| kmp_uint64 inner_ub0_u64 = kmp_fix_iv(original_bounds_nest[1].loop_iv_type, |
| original_bounds_nest[1].ub0_u64); |
| kmp_uint64 inner_lb1_u64 = kmp_fix_iv(original_bounds_nest[1].loop_iv_type, |
| original_bounds_nest[1].lb1_u64); |
| kmp_uint64 inner_ub1_u64 = kmp_fix_iv(original_bounds_nest[1].loop_iv_type, |
| original_bounds_nest[1].ub1_u64); |
| // lower triangle loop inner bounds need to be {0,0}:{0/-1,1} |
| if (inner_lb0_u64 == 0 && inner_lb1_u64 == 0 && |
| (inner_ub0_u64 == 0 || inner_ub0_u64 == -1) && inner_ub1_u64 == 1) { |
| return nested_loop_type_lower_triangular_matrix; |
| } |
| // upper triangle loop inner bounds need to be {0,1}:{N,0} |
| if (inner_lb0_u64 == 0 && inner_lb1_u64 == 1 && |
| inner_ub0_u64 == outer_ub0_u64 && inner_ub1_u64 == 0) { |
| return nested_loop_type_upper_triangular_matrix; |
| } |
| return nested_loop_type_unkown; |
| } |
| |
| /************************************************************************** |
| * SQRT Approximation: https://math.mit.edu/~stevenj/18.335/newton-sqrt.pdf |
| * Start point is x so the result is always > sqrt(x) |
| * The method has uniform convergence, PRECISION is set to 0.1 |
| * ************************************************************************/ |
| #define level_of_precision 0.1 |
| double sqrt_newton_approx(/*in*/ kmp_uint64 x) { |
| double sqrt_old = 0.; |
| double sqrt_new = (double)x; |
| do { |
| sqrt_old = sqrt_new; |
| sqrt_new = (sqrt_old + x / sqrt_old) / 2; |
| } while ((sqrt_old - sqrt_new) > level_of_precision); |
| return sqrt_new; |
| } |
| |
| /************************************************************************** |
| * Handle lower triangle matrix in the canonical form |
| * i = 0; i <= N; i++ {0,0}:{N,0} |
| * j = 0; j <= 0/-1 + 1*i; j++ {0,0}:{0/-1,1} |
| * ************************************************************************/ |
| void kmp_handle_lower_triangle_matrix( |
| /*in*/ kmp_uint32 nth, |
| /*in*/ kmp_uint32 tid, |
| /*in */ kmp_index_t n, |
| /*in/out*/ bounds_info_t *original_bounds_nest, |
| /*out*/ bounds_info_t *chunk_bounds_nest) { |
| |
| // transfer loop types from the original loop to the chunks |
| for (kmp_index_t i = 0; i < n; ++i) { |
| chunk_bounds_nest[i] = original_bounds_nest[i]; |
| } |
| // cleanup iv variables |
| kmp_uint64 outer_ub0 = kmp_fix_iv(original_bounds_nest[0].loop_iv_type, |
| original_bounds_nest[0].ub0_u64); |
| kmp_uint64 outer_lb0 = kmp_fix_iv(original_bounds_nest[0].loop_iv_type, |
| original_bounds_nest[0].lb0_u64); |
| kmp_uint64 inner_ub0 = kmp_fix_iv(original_bounds_nest[1].loop_iv_type, |
| original_bounds_nest[1].ub0_u64); |
| // calculate the chunk's lower and upper bounds |
| // the total number of iterations in the loop is the sum of the arithmetic |
| // progression from the outer lower to outer upper bound (inclusive since the |
| // loop is canonical) note that less_than inner loops (inner_ub0 = -1) |
| // effectively make the progression 1-based making N = (outer_ub0 - inner_lb0 |
| // + 1) -> N - 1 |
| kmp_uint64 outer_iters = (outer_ub0 - outer_lb0 + 1) + inner_ub0; |
| kmp_uint64 iter_total = outer_iters * (outer_iters + 1) / 2; |
| // the current thread's number of iterations: |
| // each thread gets an equal number of iterations: total number of iterations |
| // divided by the number of threads plus, if there's a remainder, |
| // the first threads with the number up to the remainder get an additional |
| // iteration each to cover it |
| kmp_uint64 iter_current = |
| iter_total / nth + ((tid < (iter_total % nth)) ? 1 : 0); |
| // cumulative number of iterations executed by all the previous threads: |
| // threads with the tid below the remainder will have (iter_total/nth+1) |
| // elements, and so will all threads before them so the cumulative number of |
| // iterations executed by the all previous will be the current thread's number |
| // of iterations multiplied by the number of previous threads which is equal |
| // to the current thread's tid; threads with the number equal or above the |
| // remainder will have (iter_total/nth) elements so the cumulative number of |
| // iterations previously executed is its number of iterations multipled by the |
| // number of previous threads which is again equal to the current thread's tid |
| // PLUS all the remainder iterations that will have been executed by the |
| // previous threads |
| kmp_uint64 iter_before_current = |
| tid * iter_current + ((tid < iter_total % nth) ? 0 : (iter_total % nth)); |
| // cumulative number of iterations executed with the current thread is |
| // the cumulative number executed before it plus its own |
| kmp_uint64 iter_with_current = iter_before_current + iter_current; |
| // calculate the outer loop lower bound (lbo) which is the max outer iv value |
| // that gives the number of iterations that is equal or just below the total |
| // number of iterations executed by the previous threads, for less_than |
| // (1-based) inner loops (inner_ub0 == -1) it will be i.e. |
| // lbo*(lbo-1)/2<=iter_before_current => lbo^2-lbo-2*iter_before_current<=0 |
| // for less_than_equal (0-based) inner loops (inner_ub == 0) it will be: |
| // i.e. lbo*(lbo+1)/2<=iter_before_current => |
| // lbo^2+lbo-2*iter_before_current<=0 both cases can be handled similarily |
| // using a parameter to control the equation sign |
| kmp_int64 inner_adjustment = 1 + 2 * inner_ub0; |
| kmp_uint64 lower_bound_outer = |
| (kmp_uint64)(sqrt_newton_approx(inner_adjustment * inner_adjustment + |
| 8 * iter_before_current) + |
| inner_adjustment) / |
| 2 - |
| inner_adjustment; |
| // calculate the inner loop lower bound which is the remaining number of |
| // iterations required to hit the total number of iterations executed by the |
| // previous threads giving the starting point of this thread |
| kmp_uint64 lower_bound_inner = |
| iter_before_current - |
| ((lower_bound_outer + inner_adjustment) * lower_bound_outer) / 2; |
| // calculate the outer loop upper bound using the same approach as for the |
| // inner bound except using the total number of iterations executed with the |
| // current thread |
| kmp_uint64 upper_bound_outer = |
| (kmp_uint64)(sqrt_newton_approx(inner_adjustment * inner_adjustment + |
| 8 * iter_with_current) + |
| inner_adjustment) / |
| 2 - |
| inner_adjustment; |
| // calculate the inner loop upper bound which is the remaining number of |
| // iterations required to hit the total number of iterations executed after |
| // the current thread giving the starting point of the next thread |
| kmp_uint64 upper_bound_inner = |
| iter_with_current - |
| ((upper_bound_outer + inner_adjustment) * upper_bound_outer) / 2; |
| // adjust the upper bounds down by 1 element to point at the last iteration of |
| // the current thread the first iteration of the next thread |
| if (upper_bound_inner == 0) { |
| // {n,0} => {n-1,n-1} |
| upper_bound_outer -= 1; |
| upper_bound_inner = upper_bound_outer; |
| } else { |
| // {n,m} => {n,m-1} (m!=0) |
| upper_bound_inner -= 1; |
| } |
| |
| // assign the values, zeroing out lb1 and ub1 values since the iteration space |
| // is now one-dimensional |
| chunk_bounds_nest[0].lb0_u64 = lower_bound_outer; |
| chunk_bounds_nest[1].lb0_u64 = lower_bound_inner; |
| chunk_bounds_nest[0].ub0_u64 = upper_bound_outer; |
| chunk_bounds_nest[1].ub0_u64 = upper_bound_inner; |
| chunk_bounds_nest[0].lb1_u64 = 0; |
| chunk_bounds_nest[0].ub1_u64 = 0; |
| chunk_bounds_nest[1].lb1_u64 = 0; |
| chunk_bounds_nest[1].ub1_u64 = 0; |
| |
| #if 0 |
| printf("tid/nth = %d/%d : From [%llu, %llu] To [%llu, %llu] : Chunks %llu/%llu\n", |
| tid, nth, chunk_bounds_nest[0].lb0_u64, chunk_bounds_nest[1].lb0_u64, |
| chunk_bounds_nest[0].ub0_u64, chunk_bounds_nest[1].ub0_u64, iter_current, iter_total); |
| #endif |
| } |
| |
| /************************************************************************** |
| * Handle upper triangle matrix in the canonical form |
| * i = 0; i <= N; i++ {0,0}:{N,0} |
| * j = 0+1*i; j <= N; j++ {0,1}:{N,0} |
| * ************************************************************************/ |
| void kmp_handle_upper_triangle_matrix( |
| /*in*/ kmp_uint32 nth, |
| /*in*/ kmp_uint32 tid, |
| /*in */ kmp_index_t n, |
| /*in/out*/ bounds_info_t *original_bounds_nest, |
| /*out*/ bounds_info_t *chunk_bounds_nest) { |
| |
| // transfer loop types from the original loop to the chunks |
| for (kmp_index_t i = 0; i < n; ++i) { |
| chunk_bounds_nest[i] = original_bounds_nest[i]; |
| } |
| // cleanup iv variables |
| kmp_uint64 outer_ub0 = kmp_fix_iv(original_bounds_nest[0].loop_iv_type, |
| original_bounds_nest[0].ub0_u64); |
| kmp_uint64 outer_lb0 = kmp_fix_iv(original_bounds_nest[0].loop_iv_type, |
| original_bounds_nest[0].lb0_u64); |
| [[maybe_unused]] kmp_uint64 inner_ub0 = kmp_fix_iv( |
| original_bounds_nest[1].loop_iv_type, original_bounds_nest[1].ub0_u64); |
| // calculate the chunk's lower and upper bounds |
| // the total number of iterations in the loop is the sum of the arithmetic |
| // progression from the outer lower to outer upper bound (inclusive since the |
| // loop is canonical) note that less_than inner loops (inner_ub0 = -1) |
| // effectively make the progression 1-based making N = (outer_ub0 - inner_lb0 |
| // + 1) -> N - 1 |
| kmp_uint64 outer_iters = (outer_ub0 - outer_lb0 + 1); |
| kmp_uint64 iter_total = outer_iters * (outer_iters + 1) / 2; |
| // the current thread's number of iterations: |
| // each thread gets an equal number of iterations: total number of iterations |
| // divided by the number of threads plus, if there's a remainder, |
| // the first threads with the number up to the remainder get an additional |
| // iteration each to cover it |
| kmp_uint64 iter_current = |
| iter_total / nth + ((tid < (iter_total % nth)) ? 1 : 0); |
| // cumulative number of iterations executed by all the previous threads: |
| // threads with the tid below the remainder will have (iter_total/nth+1) |
| // elements, and so will all threads before them so the cumulative number of |
| // iterations executed by the all previous will be the current thread's number |
| // of iterations multiplied by the number of previous threads which is equal |
| // to the current thread's tid; threads with the number equal or above the |
| // remainder will have (iter_total/nth) elements so the cumulative number of |
| // iterations previously executed is its number of iterations multipled by the |
| // number of previous threads which is again equal to the current thread's tid |
| // PLUS all the remainder iterations that will have been executed by the |
| // previous threads |
| kmp_uint64 iter_before_current = |
| tid * iter_current + ((tid < iter_total % nth) ? 0 : (iter_total % nth)); |
| // cumulative number of iterations executed with the current thread is |
| // the cumulative number executed before it plus its own |
| kmp_uint64 iter_with_current = iter_before_current + iter_current; |
| // calculate the outer loop lower bound (lbo) which is the max outer iv value |
| // that gives the number of iterations that is equal or just below the total |
| // number of iterations executed by the previous threads: |
| // lbo*(lbo+1)/2<=iter_before_current => |
| // lbo^2+lbo-2*iter_before_current<=0 |
| kmp_uint64 lower_bound_outer = |
| (kmp_uint64)(sqrt_newton_approx(1 + 8 * iter_before_current) + 1) / 2 - 1; |
| // calculate the inner loop lower bound which is the remaining number of |
| // iterations required to hit the total number of iterations executed by the |
| // previous threads giving the starting point of this thread |
| kmp_uint64 lower_bound_inner = |
| iter_before_current - ((lower_bound_outer + 1) * lower_bound_outer) / 2; |
| // calculate the outer loop upper bound using the same approach as for the |
| // inner bound except using the total number of iterations executed with the |
| // current thread |
| kmp_uint64 upper_bound_outer = |
| (kmp_uint64)(sqrt_newton_approx(1 + 8 * iter_with_current) + 1) / 2 - 1; |
| // calculate the inner loop upper bound which is the remaining number of |
| // iterations required to hit the total number of iterations executed after |
| // the current thread giving the starting point of the next thread |
| kmp_uint64 upper_bound_inner = |
| iter_with_current - ((upper_bound_outer + 1) * upper_bound_outer) / 2; |
| // adjust the upper bounds down by 1 element to point at the last iteration of |
| // the current thread the first iteration of the next thread |
| if (upper_bound_inner == 0) { |
| // {n,0} => {n-1,n-1} |
| upper_bound_outer -= 1; |
| upper_bound_inner = upper_bound_outer; |
| } else { |
| // {n,m} => {n,m-1} (m!=0) |
| upper_bound_inner -= 1; |
| } |
| |
| // assign the values, zeroing out lb1 and ub1 values since the iteration space |
| // is now one-dimensional |
| chunk_bounds_nest[0].lb0_u64 = (outer_iters - 1) - upper_bound_outer; |
| chunk_bounds_nest[1].lb0_u64 = (outer_iters - 1) - upper_bound_inner; |
| chunk_bounds_nest[0].ub0_u64 = (outer_iters - 1) - lower_bound_outer; |
| chunk_bounds_nest[1].ub0_u64 = (outer_iters - 1) - lower_bound_inner; |
| chunk_bounds_nest[0].lb1_u64 = 0; |
| chunk_bounds_nest[0].ub1_u64 = 0; |
| chunk_bounds_nest[1].lb1_u64 = 0; |
| chunk_bounds_nest[1].ub1_u64 = 0; |
| |
| #if 0 |
| printf("tid/nth = %d/%d : From [%llu, %llu] To [%llu, %llu] : Chunks %llu/%llu\n", |
| tid, nth, chunk_bounds_nest[0].lb0_u64, chunk_bounds_nest[1].lb0_u64, |
| chunk_bounds_nest[0].ub0_u64, chunk_bounds_nest[1].ub0_u64, iter_current, iter_total); |
| #endif |
| } |
| //----------Init API for non-rectangular loops-------------------------------- |
| |
| // Init API for collapsed loops (static, no chunks defined). |
| // "bounds_nest" has to be allocated per thread. |
| // API will modify original bounds_nest array to bring it to a canonical form |
| // (only <= and >=, no !=, <, >). If the original loop nest was already in a |
| // canonical form there will be no changes to bounds in bounds_nest array |
| // (only trip counts will be calculated). Internally API will expand the space |
| // to parallelogram/parallelepiped, calculate total, calculate bounds for the |
| // chunks in terms of the new IV, re-calc them in terms of old IVs (especially |
| // important on the left side, to hit the lower bounds and not step over), and |
| // pick the correct chunk for this thread (so it will calculate chunks up to the |
| // needed one). It could be optimized to calculate just this chunk, potentially |
| // a bit less well distributed among threads. It is designed to make sure that |
| // threads will receive predictable chunks, deterministically (so that next nest |
| // of loops with similar characteristics will get exactly same chunks on same |
| // threads). |
| // Current contract: chunk_bounds_nest has only lb0 and ub0, |
| // lb1 and ub1 are set to 0 and can be ignored. (This may change in the future). |
| extern "C" kmp_int32 |
| __kmpc_for_collapsed_init(ident_t *loc, kmp_int32 gtid, |
| /*in/out*/ bounds_info_t *original_bounds_nest, |
| /*out*/ bounds_info_t *chunk_bounds_nest, |
| kmp_index_t n, /*out*/ kmp_int32 *plastiter) { |
| |
| KMP_DEBUG_ASSERT(plastiter && original_bounds_nest); |
| KE_TRACE(10, ("__kmpc_for_collapsed_init called (%d)\n", gtid)); |
| |
| if (__kmp_env_consistency_check) { |
| __kmp_push_workshare(gtid, ct_pdo, loc); |
| } |
| |
| kmp_canonicalize_loop_nest(loc, /*in/out*/ original_bounds_nest, n); |
| |
| CollapseAllocator<bounds_info_internal_t> updated_bounds_nest(n); |
| |
| for (kmp_index_t i = 0; i < n; ++i) { |
| updated_bounds_nest[i].b = original_bounds_nest[i]; |
| } |
| |
| kmp_loop_nest_iv_t total = |
| kmp_process_loop_nest(/*in/out*/ updated_bounds_nest, n); |
| |
| if (plastiter != NULL) { |
| *plastiter = FALSE; |
| } |
| |
| if (total == 0) { |
| // Loop won't execute: |
| return FALSE; |
| } |
| |
| // OMPTODO: DISTRIBUTE is not supported yet |
| __kmp_assert_valid_gtid(gtid); |
| kmp_uint32 tid = __kmp_tid_from_gtid(gtid); |
| |
| kmp_info_t *th = __kmp_threads[gtid]; |
| kmp_team_t *team = th->th.th_team; |
| kmp_uint32 nth = team->t.t_nproc; // Number of threads |
| |
| KMP_DEBUG_ASSERT(tid < nth); |
| |
| // Handle special cases |
| nested_loop_type_t loop_type = |
| kmp_identify_nested_loop_structure(original_bounds_nest, n); |
| if (loop_type == nested_loop_type_lower_triangular_matrix) { |
| kmp_handle_lower_triangle_matrix(nth, tid, n, original_bounds_nest, |
| chunk_bounds_nest); |
| return TRUE; |
| } else if (loop_type == nested_loop_type_upper_triangular_matrix) { |
| kmp_handle_upper_triangle_matrix(nth, tid, n, original_bounds_nest, |
| chunk_bounds_nest); |
| return TRUE; |
| } |
| |
| CollapseAllocator<kmp_uint64> original_ivs_start(n); |
| |
| if (!kmp_calc_original_ivs_for_start(original_bounds_nest, n, |
| /*out*/ original_ivs_start)) { |
| // Loop won't execute: |
| return FALSE; |
| } |
| |
| // Not doing this optimization for one thread: |
| // (1) more to test |
| // (2) without it current contract that chunk_bounds_nest has only lb0 and |
| // ub0, lb1 and ub1 are set to 0 and can be ignored. |
| // if (nth == 1) { |
| // // One thread: |
| // // Copy all info from original_bounds_nest, it'll be good enough. |
| |
| // for (kmp_index_t i = 0; i < n; ++i) { |
| // chunk_bounds_nest[i] = original_bounds_nest[i]; |
| // } |
| |
| // if (plastiter != NULL) { |
| // *plastiter = TRUE; |
| // } |
| // return TRUE; |
| //} |
| |
| kmp_loop_nest_iv_t new_iv = kmp_calc_new_iv_from_original_ivs( |
| updated_bounds_nest, original_ivs_start, n); |
| |
| bool last_iter = false; |
| |
| for (; nth > 0;) { |
| // We could calculate chunk size once, but this is to compensate that the |
| // original space is not parallelepiped and some threads can be left |
| // without work: |
| KMP_DEBUG_ASSERT(total >= new_iv); |
| |
| kmp_loop_nest_iv_t total_left = total - new_iv; |
| kmp_loop_nest_iv_t chunk_size = total_left / nth; |
| kmp_loop_nest_iv_t remainder = total_left % nth; |
| |
| kmp_loop_nest_iv_t curr_chunk_size = chunk_size; |
| |
| if (remainder > 0) { |
| ++curr_chunk_size; |
| --remainder; |
| } |
| |
| #if defined(KMP_DEBUG) |
| kmp_loop_nest_iv_t new_iv_for_start = new_iv; |
| #endif |
| |
| if (curr_chunk_size > 1) { |
| new_iv += curr_chunk_size - 1; |
| } |
| |
| CollapseAllocator<kmp_uint64> original_ivs_end(n); |
| if ((nth == 1) || (new_iv >= total - 1)) { |
| // Do this one till the end - just in case we miscalculated |
| // and either too much is left to process or new_iv is a bit too big: |
| kmp_calc_original_ivs_for_end(original_bounds_nest, n, |
| /*out*/ original_ivs_end); |
| |
| last_iter = true; |
| } else { |
| // Note: here we make sure it's past (or equal to) the previous point. |
| if (!kmp_calc_original_ivs_for_chunk_end(original_bounds_nest, n, |
| updated_bounds_nest, |
| original_ivs_start, new_iv, |
| /*out*/ original_ivs_end)) { |
| // We could not find the ending point, use the original upper bounds: |
| kmp_calc_original_ivs_for_end(original_bounds_nest, n, |
| /*out*/ original_ivs_end); |
| |
| last_iter = true; |
| } |
| } |
| |
| #if defined(KMP_DEBUG) |
| auto new_iv_for_end = kmp_calc_new_iv_from_original_ivs( |
| updated_bounds_nest, original_ivs_end, n); |
| KMP_DEBUG_ASSERT(new_iv_for_end >= new_iv_for_start); |
| #endif |
| |
| if (last_iter && (tid != 0)) { |
| // We are done, this was last chunk, but no chunk for current thread was |
| // found: |
| return FALSE; |
| } |
| |
| if (tid == 0) { |
| // We found the chunk for this thread, now we need to check if it's the |
| // last chunk or not: |
| |
| CollapseAllocator<kmp_uint64> original_ivs_next_start(n); |
| if (last_iter || |
| !kmp_calc_next_original_ivs(original_bounds_nest, n, original_ivs_end, |
| /*out*/ original_ivs_next_start)) { |
| // no more loop iterations left to process, |
| // this means that currently found chunk is the last chunk: |
| if (plastiter != NULL) { |
| *plastiter = TRUE; |
| } |
| } |
| |
| // Fill in chunk bounds: |
| for (kmp_index_t i = 0; i < n; ++i) { |
| chunk_bounds_nest[i] = |
| original_bounds_nest[i]; // To fill in types, etc. - optional |
| chunk_bounds_nest[i].lb0_u64 = original_ivs_start[i]; |
| chunk_bounds_nest[i].lb1_u64 = 0; |
| |
| chunk_bounds_nest[i].ub0_u64 = original_ivs_end[i]; |
| chunk_bounds_nest[i].ub1_u64 = 0; |
| } |
| |
| return TRUE; |
| } |
| |
| --tid; |
| --nth; |
| |
| bool next_chunk = kmp_calc_next_original_ivs( |
| original_bounds_nest, n, original_ivs_end, /*out*/ original_ivs_start); |
| if (!next_chunk) { |
| // no more loop iterations to process, |
| // the prevoius chunk was the last chunk |
| break; |
| } |
| |
| // original_ivs_start is next to previous chunk original_ivs_end, |
| // we need to start new chunk here, so chunks will be one after another |
| // without any gap or overlap: |
| new_iv = kmp_calc_new_iv_from_original_ivs(updated_bounds_nest, |
| original_ivs_start, n); |
| } |
| |
| return FALSE; |
| } |
