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

Stefan Kanthak via llvm-dev llvm-dev at lists.llvm.org
Mon Dec 17 15:40:37 PST 2018

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 + 2eax] mov ecx, eax shr ecx, 2 and ecx, 858993459 and eax, 858993459 lea eax, [ecx + 4eax] mov ecx, eax shr ecx, 4 and ecx, 252645135 shl eax, 4 and eax, -252645136 or eax, ecx #ifndef _OPTIMISER_GONE_FISHING // 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 OPTIMISER_GONE_FISHING 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 + 2eax] lea eax, [esi + 2ecx] mov ecx, eax shr ecx, 2 mov esi, edx shr esi, 2 #ifdef OPTIMISER_GONE_FISHING 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 + 4eax] lea edx, [esi + 4edx] mov ecx, edx shr ecx, 4 mov esi, eax shr esi, 4

#ifdef OPTIMISER_GONE_FISHING and esi, 252645135 and ecx, 252645135

#else mov ebx, 252645135 and esi, ebx and ecx, ebx #endif shl edx, 4 shl eax, 4

#ifdef OPTIMISER_GONE_FISHING and eax, -252645136 #else not ebx and eax, ebx #endif or eax, esi

#ifdef OPTIMISER_GONE_FISHING and edx, -252645136 #else and edx, ebx pop ebx #endif or edx, ecx #ifndef OPTIMISER_GONE_FISHING // 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

More information about the llvm-dev mailing list