From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:36263) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1beRaJ-0001FS-1L for qemu-devel@nongnu.org; Mon, 29 Aug 2016 14:47:09 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1beRaF-0001mk-QY for qemu-devel@nongnu.org; Mon, 29 Aug 2016 14:47:01 -0400 Received: from mail-qt0-x229.google.com ([2607:f8b0:400d:c0d::229]:36677) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1beRaF-0001mV-GV for qemu-devel@nongnu.org; Mon, 29 Aug 2016 14:46:59 -0400 Received: by mail-qt0-x229.google.com with SMTP id 52so73026585qtq.3 for ; Mon, 29 Aug 2016 11:46:59 -0700 (PDT) Sender: Richard Henderson From: Richard Henderson Date: Mon, 29 Aug 2016 11:46:15 -0700 Message-Id: <1472496380-19706-5-git-send-email-rth@twiddle.net> In-Reply-To: <1472496380-19706-1-git-send-email-rth@twiddle.net> References: <1472496380-19706-1-git-send-email-rth@twiddle.net> Subject: [Qemu-devel] [PATCH v3 4/9] cutils: Rearrange buffer_is_zero acceleration List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org Cc: pbonzini@redhat.com, vijay.kilari@gmail.com Allow selection of several acceleration functions based on the size and alignment of the buffer. Do not require ifunc support for AVX2 acceleration. Signed-off-by: Richard Henderson --- configure | 21 +--- util/bufferiszero.c | 349 ++++++++++++++++++++++++---------------------------- 2 files changed, 166 insertions(+), 204 deletions(-) diff --git a/configure b/configure index 4b808f9..9f3d1fa 100755 --- a/configure +++ b/configure @@ -1788,28 +1788,19 @@ fi ########################################## # avx2 optimization requirement check - -if test "$static" = "no" ; then - cat > $TMPC << EOF +cat > $TMPC << EOF #pragma GCC push_options #pragma GCC target("avx2") #include #include - static int bar(void *a) { - return _mm256_movemask_epi8(_mm256_cmpeq_epi8(*(__m256i *)a, (__m256i){0})); + __m256i x = *(__m256i *)a; + return _mm256_testz_si256(x, x); } -static void *bar_ifunc(void) {return (void*) bar;} -int foo(void *a) __attribute__((ifunc("bar_ifunc"))); -int main(int argc, char *argv[]) { return foo(argv[0]);} +int main(int argc, char *argv[]) { return bar(argv[0]); } EOF - if compile_object "" ; then - if has readelf; then - if readelf --syms $TMPO 2>/dev/null |grep -q "IFUNC.*foo"; then - avx2_opt="yes" - fi - fi - fi +if compile_object "" ; then + avx2_opt="yes" fi ######################################### diff --git a/util/bufferiszero.c b/util/bufferiszero.c index 0cf8b6e..89224f4 100644 --- a/util/bufferiszero.c +++ b/util/bufferiszero.c @@ -24,245 +24,216 @@ #include "qemu/osdep.h" #include "qemu-common.h" #include "qemu/cutils.h" +#include "qemu/bswap.h" /* vector definitions */ + +extern void link_error(void); + +#define ACCEL_BUFFER_ZERO(NAME, SIZE, VECTYPE, NONZERO) \ +static bool NAME(const void *buf, size_t len) \ +{ \ + const void *end = buf + len; \ + do { \ + const VECTYPE *p = buf; \ + VECTYPE t; \ + if (SIZE == sizeof(VECTYPE) * 4) { \ + t = (p[0] | p[1]) | (p[2] | p[3]); \ + } else if (SIZE == sizeof(VECTYPE) * 8) { \ + t = p[0] | p[1]; \ + t |= p[2] | p[3]; \ + t |= p[4] | p[5]; \ + t |= p[6] | p[7]; \ + } else { \ + link_error(); \ + } \ + if (unlikely(NONZERO(t))) { \ + return false; \ + } \ + buf += SIZE; \ + } while (buf < end); \ + return true; \ +} + +typedef bool (*accel_zero_fn)(const void *, size_t); + +static bool +buffer_zero_int(const void *buf, size_t len) +{ + if (unlikely(len < 8)) { + /* For a very small buffer, simply accumulate all the bytes. */ + const unsigned char *p = buf; + const unsigned char *e = buf + len; + unsigned char t = 0; + + do { + t |= *p++; + } while (p < e); + + return t == 0; + } else { + /* Otherwise, use the unaligned memory access functions to + handle the beginning and end of the buffer, with a couple + of loops handling the middle aligned section. */ + uint64_t t = ldq_he_p(buf); + const uint64_t *p = (uint64_t *)(((uintptr_t)buf + 8) & -8); + const uint64_t *e = (uint64_t *)(((uintptr_t)buf + len) & -8); + + for (; p + 8 <= e; p += 8) { + __builtin_prefetch(p + 8); + if (t) { + return false; + } + t = p[0] | p[1] | p[2] | p[3] | p[4] | p[5] | p[6] | p[7]; + } + while (p < e) { + t |= *p++; + } + t |= ldq_he_p(buf + len - 8); + + return t == 0; + } +} + #ifdef __ALTIVEC__ #include /* The altivec.h header says we're allowed to undef these for * C++ compatibility. Here we don't care about C++, but we * undef them anyway to avoid namespace pollution. + * altivec.h may redefine the bool macro as vector type. + * Reset it to POSIX semantics. */ #undef vector #undef pixel #undef bool -#define VECTYPE __vector unsigned char -#define ALL_EQ(v1, v2) vec_all_eq(v1, v2) -#define VEC_OR(v1, v2) ((v1) | (v2)) -/* altivec.h may redefine the bool macro as vector type. - * Reset it to POSIX semantics. */ #define bool _Bool -#elif defined __SSE2__ -#include -#define VECTYPE __m128i -#define ALL_EQ(v1, v2) (_mm_movemask_epi8(_mm_cmpeq_epi8(v1, v2)) == 0xFFFF) -#define VEC_OR(v1, v2) (_mm_or_si128(v1, v2)) -#elif defined(__aarch64__) -#include "arm_neon.h" -#define VECTYPE uint64x2_t -#define ALL_EQ(v1, v2) \ - ((vgetq_lane_u64(v1, 0) == vgetq_lane_u64(v2, 0)) && \ - (vgetq_lane_u64(v1, 1) == vgetq_lane_u64(v2, 1))) -#define VEC_OR(v1, v2) ((v1) | (v2)) -#else -#define VECTYPE unsigned long -#define ALL_EQ(v1, v2) ((v1) == (v2)) -#define VEC_OR(v1, v2) ((v1) | (v2)) -#endif - -#define BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR 8 +#define DO_NONZERO(X) vec_any_ne(X, (__vector unsigned char){ 0 }) +ACCEL_BUFFER_ZERO(buffer_zero_ppc, 128, __vector unsigned char, DO_NONZERO) -static bool -can_use_buffer_find_nonzero_offset_inner(const void *buf, size_t len) +static bool select_accel_fn(const void *buf, size_t len) { - return (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR - * sizeof(VECTYPE)) == 0 - && ((uintptr_t) buf) % sizeof(VECTYPE) == 0); -} - -/* - * Searches for an area with non-zero content in a buffer - * - * Attention! The len must be a multiple of - * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE) - * and addr must be a multiple of sizeof(VECTYPE) due to - * restriction of optimizations in this function. - * - * can_use_buffer_find_nonzero_offset_inner() can be used to - * check these requirements. - * - * The return value is the offset of the non-zero area rounded - * down to a multiple of sizeof(VECTYPE) for the first - * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR chunks and down to - * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE) - * afterwards. - * - * If the buffer is all zero the return value is equal to len. - */ - -static size_t buffer_find_nonzero_offset_inner(const void *buf, size_t len) -{ - const VECTYPE *p = buf; - const VECTYPE zero = (VECTYPE){0}; - size_t i; - - assert(can_use_buffer_find_nonzero_offset_inner(buf, len)); - - if (!len) { - return 0; + uintptr_t ibuf = (uintptr_t)buf; + if (len % 128 == 0 && ibuf % sizeof(__vector unsigned char) == 0) { + return buffer_zero_ppc(buf, len); } - - for (i = 0; i < BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; i++) { - if (!ALL_EQ(p[i], zero)) { - return i * sizeof(VECTYPE); - } - } - - for (i = BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; - i < len / sizeof(VECTYPE); - i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) { - VECTYPE tmp0 = VEC_OR(p[i + 0], p[i + 1]); - VECTYPE tmp1 = VEC_OR(p[i + 2], p[i + 3]); - VECTYPE tmp2 = VEC_OR(p[i + 4], p[i + 5]); - VECTYPE tmp3 = VEC_OR(p[i + 6], p[i + 7]); - VECTYPE tmp01 = VEC_OR(tmp0, tmp1); - VECTYPE tmp23 = VEC_OR(tmp2, tmp3); - if (!ALL_EQ(VEC_OR(tmp01, tmp23), zero)) { - break; - } - } - - return i * sizeof(VECTYPE); + return buffer_zero_int(buf, len); } -#if defined CONFIG_AVX2_OPT -#pragma GCC push_options -#pragma GCC target("avx2") +#elif defined(CONFIG_AVX2_OPT) #include -#include +#include -#define AVX2_VECTYPE __m256i -#define AVX2_ALL_EQ(v1, v2) \ - (_mm256_movemask_epi8(_mm256_cmpeq_epi8(v1, v2)) == 0xFFFFFFFF) -#define AVX2_VEC_OR(v1, v2) (_mm256_or_si256(v1, v2)) +#pragma GCC push_options +#pragma GCC target("avx2") +#define AVX2_NONZERO(X) !_mm256_testz_si256((X), (X)) +ACCEL_BUFFER_ZERO(buffer_zero_avx2, 128, __m256i, AVX2_NONZERO) +#pragma GCC pop_options -static bool -can_use_buffer_find_nonzero_offset_avx2(const void *buf, size_t len) -{ - return (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR - * sizeof(AVX2_VECTYPE)) == 0 - && ((uintptr_t) buf) % sizeof(AVX2_VECTYPE) == 0); -} +#pragma GCC push_options +#pragma GCC target("sse2") +#define SSE2_NONZERO(X) \ + (_mm_movemask_epi8(_mm_cmpeq_epi8((X), _mm_setzero_si128())) != 0xFFFF) +ACCEL_BUFFER_ZERO(buffer_zero_sse2, 64, __m128i, SSE2_NONZERO) +#pragma GCC pop_options -static size_t buffer_find_nonzero_offset_avx2(const void *buf, size_t len) -{ - const AVX2_VECTYPE *p = buf; - const AVX2_VECTYPE zero = (AVX2_VECTYPE){0}; - size_t i; +#define CACHE_AVX2 2 +#define CACHE_AVX1 4 +#define CACHE_SSE4 8 +#define CACHE_SSE2 16 - assert(can_use_buffer_find_nonzero_offset_avx2(buf, len)); +static unsigned cpuid_cache; - if (!len) { - return 0; - } +static void __attribute__((constructor)) init_cpuid_cache(void) +{ + int max = __get_cpuid_max(0, NULL); + int a, b, c, d; + unsigned cache = 0; - for (i = 0; i < BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; i++) { - if (!AVX2_ALL_EQ(p[i], zero)) { - return i * sizeof(AVX2_VECTYPE); + if (max >= 1) { + __cpuid(1, a, b, c, d); + if (d & bit_SSE2) { + cache |= CACHE_SSE2; + } + if (c & bit_SSE4_1) { + cache |= CACHE_SSE4; } - } - for (i = BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; - i < len / sizeof(AVX2_VECTYPE); - i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) { - AVX2_VECTYPE tmp0 = AVX2_VEC_OR(p[i + 0], p[i + 1]); - AVX2_VECTYPE tmp1 = AVX2_VEC_OR(p[i + 2], p[i + 3]); - AVX2_VECTYPE tmp2 = AVX2_VEC_OR(p[i + 4], p[i + 5]); - AVX2_VECTYPE tmp3 = AVX2_VEC_OR(p[i + 6], p[i + 7]); - AVX2_VECTYPE tmp01 = AVX2_VEC_OR(tmp0, tmp1); - AVX2_VECTYPE tmp23 = AVX2_VEC_OR(tmp2, tmp3); - if (!AVX2_ALL_EQ(AVX2_VEC_OR(tmp01, tmp23), zero)) { - break; + /* We must check that AVX is not just available, but usable. */ + if ((c & bit_OSXSAVE) && (c & bit_AVX)) { + __asm("xgetbv" : "=a"(a), "=d"(d) : "c"(0)); + if ((a & 6) == 6) { + cache |= CACHE_AVX1; + if (max >= 7) { + __cpuid_count(7, 0, a, b, c, d); + if (b & bit_AVX2) { + cache |= CACHE_AVX2; + } + } + } } } - - return i * sizeof(AVX2_VECTYPE); + cpuid_cache = cache; } -static bool avx2_support(void) +static bool select_accel_fn(const void *buf, size_t len) { - int a, b, c, d; - - if (__get_cpuid_max(0, NULL) < 7) { - return false; + uintptr_t ibuf = (uintptr_t)buf; + if (len % 128 == 0 && ibuf % 32 == 0 && (cpuid_cache & CACHE_AVX2)) { + return buffer_zero_avx2(buf, len); } - - __cpuid_count(7, 0, a, b, c, d); - - return b & bit_AVX2; + if (len % 64 == 0 && ibuf % 16 == 0 && (cpuid_cache & CACHE_SSE2)) { + return buffer_zero_sse2(buf, len); + } + return buffer_zero_int(buf, len); } -static bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len) \ - __attribute__ ((ifunc("can_use_buffer_find_nonzero_offset_ifunc"))); -static size_t buffer_find_nonzero_offset(const void *buf, size_t len) \ - __attribute__ ((ifunc("buffer_find_nonzero_offset_ifunc"))); +#elif defined __SSE2__ +#include -static void *buffer_find_nonzero_offset_ifunc(void) -{ - typeof(buffer_find_nonzero_offset) *func = (avx2_support()) ? - buffer_find_nonzero_offset_avx2 : buffer_find_nonzero_offset_inner; +#define SSE2_NONZERO(X) \ + (_mm_movemask_epi8(_mm_cmpeq_epi8((X), _mm_setzero_si128())) != 0xFFFF) +ACCEL_BUFFER_ZERO(buffer_zero_sse2, 64, __m128i, SSE2_NONZERO) - return func; +static bool select_accel_fn(const void *buf, size_t len) +{ + uintptr_t ibuf = (uintptr_t)buf; + if (len % 64 == 0 && ibuf % sizeof(__m128i) == 0) { + return buffer_zero_sse2(buf, len); + } + return select_accel_int(buf, len); } -static void *can_use_buffer_find_nonzero_offset_ifunc(void) -{ - typeof(can_use_buffer_find_nonzero_offset) *func = (avx2_support()) ? - can_use_buffer_find_nonzero_offset_avx2 : - can_use_buffer_find_nonzero_offset_inner; +#elif defined(__aarch64__) +#include "arm_neon.h" - return func; -} -#pragma GCC pop_options -#else -static bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len) -{ - return can_use_buffer_find_nonzero_offset_inner(buf, len); -} +#define DO_NONZERO(X) (vgetq_lane_u64((X), 0) | vgetq_lane_u64((X), 1)) +ACCEL_BUFFER_ZERO(buffer_zero_neon, 128, uint64x2_t, DO_NONZERO) -static size_t buffer_find_nonzero_offset(const void *buf, size_t len) +static bool select_accel_fn(const void *buf, size_t len) { - return buffer_find_nonzero_offset_inner(buf, len); + uintptr_t ibuf = (uintptr_t)buf; + if (len % 128 == 0 && ibuf % sizeof(uint64x2_t) == 0) { + return buffer_zero_neon(buf, len); + } + return buffer_zero_int(buf, len); } + +#else +#define select_accel_fn buffer_zero_int #endif /* * Checks if a buffer is all zeroes - * - * Attention! The len must be a multiple of 4 * sizeof(long) due to - * restriction of optimizations in this function. */ bool buffer_is_zero(const void *buf, size_t len) { - /* - * Use long as the biggest available internal data type that fits into the - * CPU register and unroll the loop to smooth out the effect of memory - * latency. - */ - - size_t i; - long d0, d1, d2, d3; - const long * const data = buf; - - /* use vector optimized zero check if possible */ - if (can_use_buffer_find_nonzero_offset(buf, len)) { - return buffer_find_nonzero_offset(buf, len) == len; - } - - assert(len % (4 * sizeof(long)) == 0); - len /= sizeof(long); - - for (i = 0; i < len; i += 4) { - d0 = data[i + 0]; - d1 = data[i + 1]; - d2 = data[i + 2]; - d3 = data[i + 3]; - - if (d0 || d1 || d2 || d3) { - return false; - } + if (unlikely(len == 0)) { + return true; } - return true; + /* Use an optimized zero check if possible. Note that this also + includes a check for an unrolled loop over longs, as well as + the unsized, unaligned fallback to buffer_zero_base. */ + return select_accel_fn(buf, len); } - -- 2.7.4