| /* | |
| * 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; | |
| } |