[llvm-dev] Where's the optimiser gone (part 9): bit twiddling not recognised (original) (raw)

Craig Topper via llvm-dev llvm-dev at lists.llvm.org
Mon Dec 17 23:41:10 PST 2018

I've filed a bugzilla for this https://bugs.llvm.org/show_bug.cgi?id=40058 ~Craig

On Mon, Dec 17, 2018 at 3:48 PM Stefan Kanthak via llvm-dev < llvm-dev at lists.llvm.org> wrote:

Hi @ll,

compile with -O3 -m32 -march=i686 (see <https://godbolt.org/z/fjjUl6>) unsigned long lreverse(unsigned long x) // swap all bits { x = ((x & 0xAAAAAAAAUL) >> 1) | ((x & ~0xAAAAAAAAUL) << 1);_ _x = ((x & 0xCCCCCCCCUL) >> 2) | ((x & ~0xCCCCCCCCUL) << 2);_ _x = ((x & 0xF0F0F0F0UL) >> 4) | ((x & ~0xF0F0F0F0UL) << 4);_ _x = ((x & 0xFF00FF00UL) >> 8) | ((x & ~0xFF00FF00UL) << 8);_ _x = ((x & 0xFFFF0000UL) >> 16) | ((x & ~0xFFFF0000UL) << 16); return x; } lreverse: # @lreverse mov eax, dword ptr [esp + 4] mov ecx, eax shr ecx, 1 and ecx, 1431655765 and eax, 1431655765 lea eax, [ecx + 2*eax] mov ecx, eax shr ecx, 2 and ecx, 858993459 and eax, 858993459 lea eax, [ecx + 4*eax] mov ecx, eax shr ecx, 4 and ecx, 252645135 shl eax, 4 and eax, -252645136 or eax, ecx #ifndef OPTIMISERGONEFISHING // until here, almost perfect; bswap eax // the next 7 instructions but can #else // be replaced by a single BSWAP mov ecx, eax shr ecx, 8 and ecx, 16711935 shl eax, 8 and eax, -16711936 or eax, ecx rol eax, 16 #endif ret

unsigned long long llreverse(unsigned long long x) { #if 0 x = ((x & 0xAAAAAAAAAAAAAAAAULL) >> 1) | ((x & ~0xAAAAAAAAAAAAAAAAULL) << 1);_ _x = ((x & 0xCCCCCCCCCCCCCCCCULL) >> 2) | ((x & ~0xCCCCCCCCCCCCCCCCULL) << 2);_ _x = ((x & 0xF0F0F0F0F0F0F0F0ULL) >> 4) | ((x & ~0xF0F0F0F0F0F0F0F0ULL) << 4);_ _x = ((x & 0xFF00FF00FF00FF00ULL) >> 8) | ((x & ~0xFF00FF00FF00FF00ULL) << 8);_ _x = ((x & 0xFFFF0000FFFF0000ULL) >> 16) | ((x & ~0xFFFF0000FFFF0000ULL) << 16);_ _x = ((x & 0xFFFFFFFF00000000ULL) >> 32) | ((x & ~0xFFFFFFFF00000000ULL) << 32);_ _return x;_ _#else_ _x = ((x >> 1) & ~0xAAAAAAAAAAAAAAAAULL) | ((x << 1) & 0xAAAAAAAAAAAAAAAAULL);_ _x = ((x >> 2) & ~0xCCCCCCCCCCCCCCCCULL) | ((x << 2) & 0xCCCCCCCCCCCCCCCCULL);_ _x = ((x >> 4) & ~0xF0F0F0F0F0F0F0F0ULL) | ((x << 4) & 0xF0F0F0F0F0F0F0F0ULL);_ _x = ((x >> 8) & ~0xFF00FF00FF00FF00ULL) | ((x << 8) & 0xFF00FF00FF00FF00ULL);_ _x = ((x >> 16) & ~0xFFFF0000FFFF0000ULL) | ((x << 16) & 0xFFFF0000FFFF0000ULL);_ _return (x >> 32) | (x << 32); #endif } llreverse: # @llreverse push esi mov eax, dword ptr [esp + 8] mov ecx, dword ptr [esp + 12] mov edx, eax shr edx mov esi, ecx shr esi #ifdef OPTIMISERGONEFISHING and esi, 1431655765 and edx, 1431655765 and ecx, 1431655765 and eax, 1431655765 #else push ebx mov ebx, 1431655765 and esi, ebx and edx, ebx and ecx, ebx and eax, ebx #endif lea edx, [edx + 2*eax] lea eax, [esi + 2*ecx] mov ecx, eax shr ecx, 2 mov esi, edx shr esi, 2 #ifdef OPTIMISERGONEFISHING and esi, 858993459 and ecx, 858993459 and edx, 858993459 and eax, 858993459 #else mov ebx, 858993459 and esi, ebx and ecx, ebx and edx, ebx and eax, ebx #endif lea eax, [ecx + 4*eax] lea edx, [esi + 4*edx] mov ecx, edx shr ecx, 4 mov esi, eax shr esi, 4 #ifdef OPTIMISERGONEFISHING and esi, 252645135 and ecx, 252645135 #else mov ebx, 252645135 and esi, ebx and ecx, ebx #endif shl edx, 4 shl eax, 4 #ifdef OPTIMISERGONEFISHING and eax, -252645136 #else not ebx and eax, ebx #endif or eax, esi #ifdef OPTIMISERGONEFISHING and edx, -252645136 #else and edx, ebx pop ebx #endif or edx, ecx #ifndef OPTIMISERGONEFISHING // until here, quite good; bswap eax // the next 14 instructions but can bswap edx // be replaced by a two BSWAPs #else mov ecx, eax shr ecx, 8 mov esi, edx shr esi, 8 and esi, 16711935 and ecx, 16711935 shl eax, 8 shl edx, 8 and edx, -16711936 or edx, esi and eax, -16711936 or eax, ecx rol edx, 16 rol eax, 16 #endif pop esi ret

LLVM Developers mailing list llvm-dev at lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20181217/17eccae2/attachment.html>

More information about the llvm-dev mailing list