Sunday, June 10, 2018

On an example from “What Else Has My Compiler Done For Me Lately?”

One of the examples in Matt Godbolt’s C++Now 2018 talk “What Else Has My Compiler Done For Me Lately?” is the function
void maxArray(double * __restrict x, double * __restrict y)
{
  for (int i = 0; i < 65536; i++) {
    if (y[i] > x[i])
      x[i] = y[i];
  }
}
The compiler generates vectorized code that processes four elements at a time – it reads the elements from x and y, compares the elements, and uses the result of the comparison as a mask in a masked move to write the elements from y that are larger than the corresponding element from x
vmovupd ymm0, ymmword ptr [rsi + rax]
vmovupd ymm4, ymmword ptr [rdi + rax]
vcmpltpd ymm4, ymm4, ymm0
vmaskmovpd ymmword ptr [rdi + rax], ymm4, ymm0
Modifying maxArray to use a more max-like construct (or std::max) as in
void maxArray2(double * __restrict x, double * __restrict y)
{
  for (int i = 0; i < 65536; i++) {
    x[i] = (y[i] > x[i]) ? y[i] : x[i];
  }
}
makes the compiler generate this using a “max” instruction instead of the compare and masked move
vmovupd ymm0, ymmword ptr [rsi + rax]
vmaxpd ymm0, ymm0, ymmword ptr [rdi + rax]
vmovupd ymmword ptr [rdi + rax], ymm0

Matt says he is a bit surprised that the compiler cannot see that the first version too can be generated in this way, but the compiler is doing the right thing – it is not allowed to change maxArray in this way! The reason is that maxArray only writes to x when the value changes while maxArray2 always writes to x, and the compiler would introduce problems if the generated code contain stores that are not in the original source code. Consider for example the program
const double a1[65536] = {0.0};
double a2[65536] = {0.0};

int main(void)
{
  maxArray((double*)a1, a2);
  return 0;
}
that is passing a constant array to maxArray. It is valid to cast away const as long as the object is not written to through the pointer, so this program is correct – y[i] is never bigger than x[i] for any i, so maxArray will never write to (the mask in the vectorized code is never set, so the vmaskmovpd instruction is essentially a nop). The code from maxArray2 does, however, always write to x so it would crash on this input as the compiler places a1 in read-only memory.