Openmp with more than INT_MAX iterations - is it legal?

Question

Here is a loop that works perfectly fine:

#include <inttypes.h>
#include <iostream>
int main() {
  for (int32_t i = -2; i < INT32_MAX-2; i++) {
    std::cout << i << std::endl;
  }
}

Adding omp parallel for clause seems to break the code by introducing int overflow.

#include <inttypes.h>
#include <iostream>
int main() {
  #pragma omp parallel for
  for (int32_t i = -2; i < INT32_MAX; i++) {
    std::cout << i << std::endl;
  }
}

For both clang-10 and gcc-10 the program produces no output. clang-12 on the other hand seems to handle it properly.

clang-10 at least produces some warnings:

> clang++-10 int_div.cpp -Wall -fopenmp
int_div.cpp:133:3: warning: overflow in expression; result is -2147483647 with type 'int' [-Winteger-overflow]
  for (int i = -2; i < INT32_MAX; i++) {
  ^
int_div.cpp:133:3: warning: overflow in expression; result is 2147483646 with type 'int' [-Winteger-overflow]
int_div.cpp:133:3: warning: overflow in expression; result is -2147483647 with type 'int' [-Winteger-overflow]
int_div.cpp:133:3: warning: overflow in expression; result is -2147483647 with type 'int' [-Winteger-overflow]
int_div.cpp:133:3: warning: overflow in expression; result is -2147483647 with type 'int' [-Winteger-overflow]

Is this a legal, well defined behavior of openmp standard or an implementation bug?

score 1 · Accepted Answer · answered Jan 07 '22 at 17:43

It's not a bug in a compiler but rather unspecified behavior in OpenMP. See 2.9.1 Canonical Loop Form

If var is of an integer type, then the type is the type of var.

...

The behavior is unspecified if any intermediate result required to compute the iteration count cannot be represented in the type determined above.

A similar wording can be found on Microsoft site at 241-for-construct:

This computation is made with values in the type of var, after integral promotions. In particular, if value of b - lb + incr can't be represented in that type, the result is indeterminate.

Therefore the computation is done in int resulting in integer overflow thus UB.

score 0 · Answer 2 · answered Jan 06 '22 at 04:12

0

#pragma omp parallel for would result in the execution flow with omp_get_num_threads() for loop count, something like:

for (int32_t i = -2; i < INT32_MAX; i += omp_get_num_threads())
  std::cout << i << std::endl;

for (int32_t i = -1; i < INT32_MAX; i += omp_get_num_threads())
  std::cout << i << std::endl;

// ...

for (int32_t i = -2 + omp_get_thread_num() - 1; i < INT32_MAX; i += omp_get_num_threads())
  std::cout << i << std::endl;

The second and further threads would result in signed integer overflow.

answered Jan 06 '22 at 04:12

273K

29,503
10
41
64

Interesting interpretation, but I don't think it matches reality. If this was the case, threads would start running (given initial values not resulting in overflow), and maybe would never finish (or something else would happen given that that int overflow is UB). The program produces no output and finished immediately. – S. Kaczor Jan 06 '22 at 04:19
It is not an interpretation, OMP works in a such way. UB is UB, clang-10 and gcc-10 discover UB while compiling and are legit to drop these loops. They easily diagnose `(-2 + INT32_MAX) mod INT32_MAX + omp_get_num_threads() > INT32_MAX` then warn you and optimize your code: UB never happens, thus this loop is not reachable and may be removed. – 273K Jan 06 '22 at 04:29
"It is not an interpretation, OMP works in a such way" - do you have any code / docs / specs that can back this claim? I'm happy to take a look – S. Kaczor Jan 07 '22 at 05:21
No code, is too much. Useful info with pictures https://stackoverflow.com/a/67028707/6752050. – 273K Jan 07 '22 at 05:47
In practice, I wouldn't expect a compiler to drop the loop entirely. The compiler is unlikely to know what the overloaded `std::cout::operator<<` actually does; for all it knows, it might `exit()` or throw after some fixed number of iterations and thus prevent the overflow from happening at all. – Nate Eldredge Jan 07 '22 at 07:55
@NateEldredge Those side effects do not matter. A compiler knows that a correct program has no UB. It analysis the loop and discovers UB, if the loop runs. Supposing a program is correct, it comes to the conclusion of the never reachable loop, i.e. never outputting values, and dicides to drop the unreachable loop. – 273K Jan 07 '22 at 07:57

score 0 · Answer 3 · answered Jan 06 '22 at 05:30

OpenMP loops need to compute the number of iterations before starting the loop, so the type of the loop variable needs to be such that the number is expressible. Other than that, the OMP standard allows both signed and unsigned integer types, with no restriction indicated.

score 0 · Answer 4 · answered Jan 06 '22 at 09:53

0

The OpenMP standard does not contain anything about overflow of loop variable(s), so I think it is the programmer's responsibility to make sure it will not happen. Note that it can happen easily if the collapse clause is used (e.g. see this example).

answered Jan 06 '22 at 09:53

Laci

2,738
1
13
22

Openmp with more than INT_MAX iterations - is it legal?

4 Answers4