This is an archive of the discontinued LLVM Phabricator instance.

[OpenMP] Additional APIs used by MSVC compiler for loop collapse (rectangular and non-rectangular loops)
ClosedPublic

Authored by natgla on Apr 14 2023, 4:18 PM.

Details

Summary

For MSVC compiler we moved the heavy-lifting of loop collapse feature into runtime.
For rectangular loops kmpc_process_loop_nest_rectang calculates total number of iterations, so that then loop nest can be processed as one 'openmp for' loop. kmpc_calc_original_ivs_rectang calculates original IVs from the overall IV for new for loop.
For non-rectangular loops __kmpc_for_collapsed_init on each thread returns a chunk to execute, formulated in terms of original IVs. So the loops are re-written to look ~like this (example with <=):

    fetch iLBnew, iUBnew, jA0new, jUBnew, kA0new, kUBnew for the chunk;
    jA1new = kA1new = 0;
    for (i = iLBnew; i <= iUBnew; i += iStep) {  
        for (j = i * jA1new + jA0new; j <= i * jB1 + jB0; j += jStep) {
            if ((i >= iUBnew) && (j > jUBnew)) goto done;
            for (k = j * kA1new + kA0new; k <= j * kB1 + kB0; k += kStep) {
                if ((i >= iUBnew) && (j >= jUBnew) && (k > kUBnew)) goto done;
                   LOOP BODY
            }
            kA0new = kA0;
            kA1new = kA1;
        }
        jA0new = jA0;
        jA1new = jA1;
    }
done:

I expect that it'll be easier to experiment with different implementations for non-rectangular loop collapse this way. E.g. pick different algorithms for triangular loops, or for when there are many threads available.

Diff Detail

Event Timeline

natgla created this revision.Apr 14 2023, 4:18 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 14 2023, 4:18 PM
natgla requested review of this revision.Apr 14 2023, 4:18 PM
vadikp-intel accepted this revision.Apr 19 2023, 3:34 PM

looks good to me

This revision is now accepted and ready to land.Apr 19 2023, 3:34 PM

Are there any plans to update clang itself to call these new API functions?

openmp/runtime/src/dllexports
404–406

Why are we adding more ordinal numbers? I thought they weren't necessary anymore.

Are there any plans to update clang itself to call these new API functions?

I think it could be valuable. We are doing measurements now to see how this compares to clang implementation. If not too well, it's possible that we'll need additional implementations of these APIs first. Also I can show up on one of Wednesday mornings to talk about this if it's something people will be interested in.

openmp/runtime/src/dllexports
404–406

Change was done and tested before removal of ordinals, I didn't re-test without them

This broke my build, small subset of the errors below. Reverting the patch makes the errors go away.

In file included from /home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.cpp:19:
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.h:152:20: error: expected nested-name-specifier before ‘T’
  152 |   typedef typename T span_t;
      |                    ^
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.h:152:20: error: expected ‘;’ at end of member declaration
  152 |   typedef typename T span_t;
      |                    ^
      |                     ;
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.h:152:20: error: declaration of ‘typedef int bounds_info_internalXX_template<T>::T’ shadows template parameter
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.h:138:11: note: template parameter ‘T’ declared here
  138 | template <typename T> struct bounds_info_internalXX_template {
      |           ^~~~~~~~
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.h:152:22: error: ‘span_t’ does not name a type
  152 |   typedef typename T span_t;
      |                      ^~~~~~
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.h:160:5: error: ‘span_t’ does not name a type
  160 |     span_t span_smallest;
      |     ^~~~~~
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.h:168:5: error: ‘span_t’ does not name a type
  168 |     span_t span_biggest;
      |     ^~~~~~
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.cpp: In function ‘kmp_loop_nest_iv_t kmp_process_loop_nest(std::vector<bounds_info_internal_t>&)’:
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.cpp:763:33: warning: comparison of integer expressions of different signedness: ‘kmp_index_t’ {aka ‘int’} and ‘std::vector<bounds_info_internal_t>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  763 |   for (kmp_index_t ind = 0; ind < bounds_nest.size(); ++ind) {
      |                             ~~~~^~~~~~~~~~~~~~~~~~~~
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.cpp: In function ‘kmp_loop_nest_iv_t kmp_calc_new_iv_from_original_ivs(const std::vector<bounds_info_internal_t>&, const kmp_point_t&)’:
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.cpp:869:33: warning: comparison of integer expressions of different signedness: ‘kmp_index_t’ {aka ‘int’} and ‘std::vector<bounds_info_internal_t>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  869 |   for (kmp_index_t ind = 0; ind < bounds_nest.size(); ++ind) {
      |                             ~~~~^~~~~~~~~~~~~~~~~~~~
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.cpp: In instantiation of ‘void kmp_calc_new_bounds_XX(bounds_info_internalXX_template<T>*, std::vector<bounds_info_internal_t>&) [with T = int]’:
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.cpp:748:25:   required from ‘kmp_loop_nest_iv_t kmp_process_one_loop_XX(bounds_info_internalXX_template<T>*, std::vector<bounds_info_internal_t>&) [with T = int; kmp_loop_nest_iv_t = long long unsigned int]’
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.cpp:769:54:   required from here
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.cpp:697:53: error: ‘struct bounds_info_internalXX_template<int>’ has no member named ‘span_biggest’
  697 |         T sub = (bbounds.lb1 - old_lb1) * previous->span_biggest;

This broke my build, small subset of the errors below. Reverting the patch makes the errors go away.

In file included from /home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.cpp:19:
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.h:152:20: error: expected nested-name-specifier before ‘T’
  152 |   typedef typename T span_t;
      |                    ^

My bad. Vadim @vadikp-intel fixed this when committing. He also fixed ordinals (2 of the numbers were used somewhere in strange places in dllexports)

This broke my build, small subset of the errors below. Reverting the patch makes the errors go away.

In file included from /home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.cpp:19:
/home/jhuber/Documents/llvm/llvm-project/openmp/runtime/src/kmp_collapse.h:152:20: error: expected nested-name-specifier before ‘T’
  152 |   typedef typename T span_t;
      |                    ^

My bad. Vadim @vadikp-intel fixed this when committing. He also fixed ordinals (2 of the numbers were used somewhere in strange places in dllexports)

HI @natgla, @vadikp-intel, will you fix the issues? I am not sure I understand from your comment what you are planning to do.

OpenMP buildbots are failing, e.g.:

https://lab.llvm.org/buildbot/#/builders/84/builds/36964
https://lab.llvm.org/buildbot/#/builders/193/builds/30096

So I am going to revert it.

Yes, somehow the typedef fixes didn't make it into the push. Let me fix it.
It would be good to add a Windows build to the initial PR check. The absence of such has bitten before.

Hmm, the couple of similar build breaks I fixed before pushing did make it in. These are something new that I am not seeing on our end. What Windows compiler are the problems showing up with?

My issues were on Linux

Ok, thanks for the info. It did seem to pass the Phabricator review Linux build here.

We'll look into what may be going on with other toolsets.