TL:DR: use Word unchanged = -1ULL; and update it with unchanged &= (old == lhs[i]) ? -1ULL : 0; so this maps naturally to a SIMD compare-for-equal and SIMD AND.
Or even better, changed |= old ^ lhs[i]; vectorizes nicely with GCC and clang, for Word changed = 0;. With clang, it gives optimal asm. With GCC, the first way is better because GCC pessimizes to changed |= (~old) & rhs[i]; // find RHS bits that weren't already set costing an extra movdqa register copy, or with AVX removing the ability to fold the unaligned load into a memory source for vpor (because it needs both operands twice, once for this and once for the main |).
Compare-for-unequal isn't directly available until AVX-512; doing that would have to invert the compare result before combining into a changed vector.
The overall operation can be vectorized manually with intrinsics (or asm) pretty much as written, without any major transformations, except of course optimizing to bitwise | OR instead of actual short-circuit evaluation. So this is basically a missed optimization. But in the natural asm implementation of this, your vector of changed elements would be the same width as the data, not just 4 bools. (For x86 that would take an extra vmovmskpd to feed a scalar or instead of just a SIMD vpor, and most ISAs don't have a movemask operation so maybe the generic vectorizer isn't even considering using it. Fun fact: clang auto-vectorizes your original code really badly, doing a horizontal OR down to a scalar bool every iteration.)
Using Word changed = 0; lets this vectorize fairly decently, with changed |= ..., with or without OpenMP pragmas (differently, haven't sorted out which is actually better for every combo). Compilers are dumb (complex pieces of machinery, not human understanding) and often don't figure out things like this for themselves - auto-vectorization is hard enough that they sometimes need some hand-holding.
So the trick is making changed the same width as the array elements.
If you use OpenMP, you need to tell the OpenMP vectorizer about reductions such as sum of an array with +, or in this case OR. In this case, #pragma omp simd reduction(|:changed). You should be using changed |= stuff instead of logical short-circuit eval anyway, if you want this to vectorize into branchless SIMD. reduction(|:changed) actually seems to override your actual code to some degree, so be careful it matches.
ICC even breaks your code (not updating changed in the SIMD part) if you just use #pragma omp simd https://godbolt.org/z/bG98Kz. (Perhaps that gives it license to ignore serial dependencies, or at least reductions, which you didn't tell it about? Either that or an ICC bug, I don't know OpenMP very well.)
With the original bool changed instead of Word, GCC doesn't auto-vectorize at all, and clang does a nasty job (horizontal reduction to a scalar bool inside the inner loop!)
Two versions that auto-vectorize:
On Godbolt with -O3 -march=nehalem -mtune=skylake -fopenmp (So using SSE4.1 / 4.2, but not AVX or BMI1/BMI2). I haven't looked in detail at which ends up with less clunky cleanup code.
#include <stddef.h>
typedef unsigned long long Word;
bool fun_v1(Word *lhs, const Word *rhs, size_t s)
{
Word changed = 0;
#pragma omp simd reduction(|:changed) // optional, some asm differences with/without
for (size_t i = 0; i < s; ++i) {
const Word old = lhs[i];
changed |= (~old) & rhs[i]; // find RHS bits that weren't already set. pure bitwise, no 64-bit-element SIMD == needed. Do this before storing so compiler doesn't have to worry about lhs/rhs overlap.
lhs[i] |= rhs[i];
//changed |= (old != lhs[i]) ? -1ULL : 0; // requires inverting the cmpeq result, but can fold a memory operand with AVX unlike the bitwise version
//changed = changed || (old != lhs[i]); // short circuit eval is weird for SIMD, compiles inefficiently.
}
return changed;
}
(update: changed |= old ^ lhs[i]; appears even better to get a non-zero value on not-equal. It uses only commutative operations, and doesn't need == / pcmpeqq. @chtz suggested this in comments, I haven't rewritten the rest of the answer to cut out discussion of worse optoins. clang will auto-vectorize with it, and with AVX allows a memory source operand for rhs because it's only needed once. https://godbolt.org/z/ex5519. So this appears to be the best of both worlds.)
changed |= (old != lhs[i]) ? -1ULL : 0; is also still only 10 instructions (9 uops) in the inner loop, same as changed |= (~old) & rhs[i];, for GCC 10.2 without AVX. But for clang, that defeats auto-vectorization! Clang will handle changed |= (old != lhs[i]); (or with an explicit ? 1 : 0) so that's odd. -1ULL avoids needing a set1_epi64x(1) vector constant so I used that.
Versions using == or != will need SSE4.1 pcmpeqq for vectorization of 64-bit compare for ==: compilers probably aren't going to be smart enough to realize that any integer element-size is fine for the overall thing. And emulating a narrower compare probably won't look profitable.
The ~old & rhs[i] way works with just SSE2. Ending the loop with SSE4.1 ptest instead of shuffles and POR and MOVQ would be more efficient, but compilers are pretty dumb about stuff like that. (And handling the ends of loops in general.
Just naive reduction, and scalar cleanup for odd elements instead of a possibly-overlapping final vector that ends at the end of the arrays. |= is idempotent so at worst it would cause a store-forwarding stall if you don't schedule your loads well. That's another thing you could do better with manual vectorization, but using intrinsics would force one SIMD vector width, while auto-vec lets the compiler use wider vectors when you compile for an AVX2 CPU like -march=haswell or -march=znver2.)
Until AVX-512, only compare for == is available (or >), not != directly. To reduce that the way we want, we'd need to unchanged &= (old == updated);. This lets GCC save 1 instruction in the loop, bringing it down to 9 instructions, 8 uops. It can possibly run at 1 iteration per 2 cycles.
But clang for some reason doesn't auto-vectorize it at all. Apparently clang doesn't like the ? -1 : 0 ternary here or in the other version, maybe not realizing that's what SIMD compares produce.
bool fun_v2(Word *lhs, const Word *rhs, size_t s)
{
Word unchanged = -1ULL;
// clang fails to vectorize?!? GCC works as expected with/without pragma
#pragma omp simd reduction(&:unchanged)
for (size_t i = 0; i < s; ++i) {
const Word old = lhs[i];
lhs[i] |= rhs[i];
unchanged &= (old == lhs[i]) ? -1ULL : 0;
}
return !unchanged;
}
With AVX available, vpor with a memory source operand would be efficient if compilers weren't using a stupid indexed addressing mode, forcing it to un-laminate on Intel Sandybridge family (but not on AMD).
Note that if you're thinking of using Word as a wide type to use this on arbitrary data of other types, beware strict-aliasing rules and Undefined Behaviour. Manual vectorization might be a good bet because _mm_loadu_si128((const __m128*)int_ptr); is fully strict-aliasing safe: vector pointers (and load / store intrinsics) are like char* in that they can alias anything. For a portable version, either use memcpy or GNU C typedef unsigned long unaligned_aliasing_chunk __attribute__((may_alias,aligned(1))). "Word" has different meanings in asm for different ISAs, like being 16-bit in x86, so it's not the best name for a type you want to be was wide as the machine can efficiently use. unsigned long is often that, but is 32-bit on some 64-bit machines. unsigned long long is probably fine.
