CODEWITHSUNDEEP
gccconstantscompiler-optimizationmodulocompile-time-constant
Matt
Matt

Reputation: 22163

Do C/C++ compilers such as GCC generally optimize modulo by a constant power of 2?

Let's say I have something like:

#define SIZE 32

/* ... */

unsigned x;

/* ... */

x %= SIZE;

Would the x % 32 generally be reduced to x & 31 by most C/C++ compilers such as GCC?

Upvotes: 21

Views: 5555

Answers (1)

Jonathon Reinhart
Jonathon Reinhart

Reputation: 137537

Yes, any respectable compiler should perform this optimization. Specifically, a % X operation, where X is a constant power of two will become the equivalent of an & (X-1) operation.

GCC will even do this with optimizations turned off:

Example (gcc -c -O0 version 3.4.4 on Cygwin):

unsigned int test(unsigned int a) {
   return a % 32;
}

Result (objdump -d):

00000000 <_test>:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   8b 45 08                mov    0x8(%ebp),%eax
   6:   5d                      pop    %ebp
   7:   83 e0 1f                and    $0x1f,%eax          ;; Here
   a:   c3                      ret

Upvotes: 30

Related Questions