missed optimization: llvm fails to vectorize when dealing with bools

[alex]

https://godbolt.org/z/zz8xGqbY7

#include <stdbool.h>
#include <stdint.h>
#include <stddef.h>

// Count how many bools are true
size_t count_true(const bool *values, size_t len) {
    size_t count = 0;
    for (size_t i = 0; i < len; i++) {
        if (values[i]) {
            count++;
        }
    }
    return count;
}

// Count how many uint8_t values are non-zero
size_t count_nonzero_u8(const uint8_t *values, size_t len) {
    size_t count = 0;
    for (size_t i = 0; i < len; i++) {
        if (values[i] != 0) {
            count++;
        }
    }
    return count;
}

count_true should vectorize just as easily as count_nonzero_u8, except it doesn't :-)

[topperc]

It does vectorize with -msse4.1 or if size_t count is changed to unsigned count. So there's some costing issue.

[nelhage]

I did some brief digging. The main difference between the unoptimized LLVM in the two cases is that the bool one does a load and adds directly to the accumulator (assuming bools are all either 0 or 1 values):

  %10 = load i8, ptr %9, align 1
  %11 = zext nneg i8 %10 to i64
  %12 = add i64 %8, %11

whereas the uint8_t has to do a comparison before summing:

  %10 = load i8, ptr %9, align 1
  %11 = icmp ne i8 %10, 0
  %12 = zext i1 %11 to i64
  %13 = add i64 %8, %12

Again -- and a bit surprisingly to me -- the latter vectorizes, and the former doesn't.

We can verify this is the relevant difference because (godbolt link) summing a slice of uint8_ts into a size_t does not vectorize:

size_t sum_u8(const uint8_t *values, size_t len) {
    size_t count = 0;
    for (size_t i = 0; i < len; i++) {
        count += values[i];
    }
    return count;
}

And we can make count_true vectorizing by inserting a cast through uint8_t in order to force the comparison:

size_t count_true_v2(const bool *values, size_t len) {
    size_t count = 0;
    for (size_t i = 0; i < len; i++) {
        if (*(uint8_t*)&values[i]) {
            count++;
        }
    }
    return count;
}