mini-gmp

[Vincent Lefevre]

On 2014-01-17 10:51:28 +0100, Niels Möller wrote:
> In the context of GMP, it's maybe worth noting that mp_bitcnt_t is an
> unsigned type, and that for micro optimization, we prefer to use
> unsigned types whenever dividing a non-negative number by a constant.

But that's not the right way of getting optimizations. For instance,
you may also have optimizations based on the fact that some variable
cannot be zero. But you have no types that don't include zero. The
right solution is to make sure that the compiler knows the range.
This can sometimes be done automatically from the context. Sometimes
one has to tell the compiler explicitly.

> For illustration, compile the following with gcc -O3. Instruction counts
> for x86_64.
> 
>   int
>   sdiv2(int x) /* 5 instr */
>   {
>     return x / 2;
>   }
>   
>   unsigned
>   udiv2(unsigned x) /* 3 instr */
>   {
>     return x / 2U;
>   }

#define HINT(expr) ((expr) || (__builtin_unreachable(), 0))

int sdiv2b(int x)
{
  HINT (x >= 0);
  return x / 2;
}

also gives 3 instructions.

The HINT macro depends on the compiler. For compilers that assume
that undefined behavior cannot occur and optimize using this fact,
one can use an expression with undefined behavior instead of
__builtin_unreachable().

__builtin_unreachable() is available as of GCC 4.5:

  http://gcc.gnu.org/gcc-4.5/changes.html

-- 
Vincent Lefèvre <vincent at vinc17.net> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)