title: GCC compiles leading zero count poorly unless Haswell specified
body: <p>GCC supports the <a href="https://gcc.gnu.org/onlinedocs/gcc-6.2.0/gcc/Other-Builtins.html#index-g_t_005f_005fbuiltin_005fclz-4249" rel="noreferrer"><code>__builtin_clz(int x)</code></a> builtin, which counts the number of number of <em>leading zeros</em> (consecutive most-significant zeros) in the argument.</p>
  
  <p>Among other things<sup>0</sup>, this is great for efficiently implementing the <code>lg(unsigned int x)</code> function, which takes the base-2 logarithm of <code>x</code>, rounding down<sup>1</sup>:</p>
  
  <pre><code>/** return the base-2 log of x, where x &gt; 0 */
  unsigned lg(unsigned x) {
    return 31U - (unsigned)__builtin_clz(x);
  }
  </code></pre>
  
  <p>This works in the straightforward way - in particular consider the case <code>x == 1</code> and <code>clz(x) == 31</code> - then <code>x == 2^0</code> so <code>lg(x) == 0</code> and <code>31 - 31 == 0</code> and we get the correct result. Higher values of <code>x</code> work similarly.</p>
  
  <p>Assuming the builtin is efficiently implemented, this ends much better than the alternate <a href="https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious" rel="noreferrer">pure C solutions</a>.</p>
  
  <p>Now as it happens, the <em>count leading zeros</em> operation is essentially the dual of the <a href="http://www.felixcloutier.com/x86/BSR.html" rel="noreferrer"><code>bsr</code></a> instruction in x86. That returns the index of the most-significant 1-bit<sup>2</sup> in the argument. So if there are 10 leading zeros, the first 1-bit is in bit 21 of the argument. In general we have <code>31 - clz(x) == bsr(x)</code> and in so <code>bsr</code> in fact <em>directly</em> implements our desired <code>lg()</code> function, without the superfluous <code>31U - ...</code> part. </p>
  
  <p>In fact, you can read between the line and see that the <code>__builtin_clz</code> function was implemented with <code>bsr</code> in mind: it is defined as <em>undefined behavior</em> if the argument is zero, when of course the "leading zeros" operation is perfectly well-defined as 32 (or whatever the bit-size of <code>int</code> is) with a zero argument. So <code>__builtin_clz</code> was certainly implemented with the idea of being efficiently mapped to a <code>bsr</code> instruction on x86. </p>
  
  <p>However, looking at what GCC actually does, at <code>-O3</code> with otherwise default options: it <a href="https://godbolt.org/g/gvYBrH" rel="noreferrer">adds a ton of extra junk</a>:</p>
  
  <pre><code>lg(unsigned int):
          bsr     edi, edi
          mov     eax, 31
          xor     edi, 31
          sub     eax, edi
          ret 
  </code></pre>
  
  <p>The <code>xor edi,31</code> line is effectively a <code>not edi</code> for the bottom 4 bits that actually matter, that's off-by-one<sup>3</sup> from <code>neg edi</code> which turns the result of <code>bsr</code> into <code>clz</code>. Then the <code>31 - clz(x)</code> is carried out.</p>
  
  <p>However with <code>-mtune=haswell</code>, the <a href="https://godbolt.org/g/gvYBrH" rel="noreferrer">code simplifies</a> into exactly the expected single <code>bsr</code> instruction:</p>
  
  <pre><code>lg(unsigned int):
          bsr     eax, edi
          ret
  </code></pre>
  
  <p>Why that is the case is very unclear to me. The <code>bsr</code> instruction has been around for a couple decades before Haswell, and the behavior is, AFAIK, unchanged. It's not just an issue of <em>tuning</em> for a particular arch, since <code>bsr</code> + a bunch of extra instructions isn't going to be faster than a plain <code>bsr</code> and furthermore using <code>-mtune=haswell</code> <a href="https://godbolt.org/g/5bDhWQ" rel="noreferrer">still results</a> in the slower code. </p>
  
  <p>The situation for <strong>64-bit</strong> inputs and outputs is <a href="https://godbolt.org/g/5t7867" rel="noreferrer">even slightly worse</a>: there is an extra <code>movsx</code> in the critical path which seems to do nothing since the result from <code>clz</code> will never be negative. Again, the <code>-march=haswell</code> variant is optimal with a single <code>bsr</code> instruction.</p>
  
  <p>Finally, let's check the big players in the non-Windows compiler space, <a href="https://godbolt.org/g/WIROzq" rel="noreferrer"><code>icc</code> and <code>clang</code></a>. <code>icc</code> just does a bad job and adds redundant stuff like <code>neg eax; add eax, 31; neg  eax; add eax, 31;</code> - wtf? <code>clang</code> does a good job regardless of <code>-march</code>.</p>
  
  <hr>
  
  <p><sup>0</sup> Such as scanning a <em>bitmap</em> for the first set bit.</p>
  
  <p><sup>1</sup> The logarithm of 0 is undefinited, and so calling our function with a 0 argument is <em>undefined behavior</em>.</p>
  
  <p><sup>2</sup> Here, the LSB is the 0th bit and the MSB is the 31st. </p>
  
  <p><sup>3</sup> Recall that <code>-x == ~x + 1</code> in twos-complement.</p>