title: Bloated code generated for __builtin_popcnt when -mavx2 is on
body: <p>For such a function, <code>clang</code> (and sometimes <code>gcc</code> in certain contexts that I cannot reproduce minimally) seems to generate bloated code when <code>-mavx2</code> switch is on.</p>
  <pre><code>unsigned count(uint64_t *f) {
      unsigned c = 0;
      for (unsigned i = 0; i &lt; 1024; ++i) {
          if (sizeof(long) &gt;= 8) {
              c += __builtin_popcountl(f[i]);
          } else {
              c += __builtin_popcountll(f[i]);
          }
      }
      return c;
  }
  </code></pre>
  <p>This is from <code>gcc</code> and it's quite straightforward.</p>
  <pre><code>count:
          lea     rcx, [rdi+8192]
          xor     eax, eax
  .L2:
          xor     edx, edx
          add     rdi, 8
          popcnt  rdx, QWORD PTR [rdi-8]
          add     eax, edx
          cmp     rcx, rdi
          jne     .L2
          ret
  </code></pre>
  <p>However <code>clang</code> decides to generate this massive bloat when <code>-mavx2</code> is on. <code>-mpopcnt</code> was also set.</p>
  <pre><code>.LCPI0_0:
          .zero   32,15
  .LCPI0_1:
          .byte   0                               # 0x0
          .byte   1                               # 0x1
          .byte   1                               # 0x1
          .byte   2                               # 0x2
          .byte   1                               # 0x1
          .byte   2                               # 0x2
          .byte   2                               # 0x2
          .byte   3                               # 0x3
          .byte   1                               # 0x1
          .byte   2                               # 0x2
          .byte   2                               # 0x2
          .byte   3                               # 0x3
          .byte   2                               # 0x2
          .byte   3                               # 0x3
          .byte   3                               # 0x3
          .byte   4                               # 0x4
          .byte   0                               # 0x0
          .byte   1                               # 0x1
          .byte   1                               # 0x1
          .byte   2                               # 0x2
          .byte   1                               # 0x1
          .byte   2                               # 0x2
          .byte   2                               # 0x2
          .byte   3                               # 0x3
          .byte   1                               # 0x1
          .byte   2                               # 0x2
          .byte   2                               # 0x2
          .byte   3                               # 0x3
          .byte   2                               # 0x2
          .byte   3                               # 0x3
          .byte   3                               # 0x3
          .byte   4                               # 0x4
  count:                                  # @count
          vpxor   xmm0, xmm0, xmm0
          xor     eax, eax
          vmovdqa ymm1, ymmword ptr [rip + .LCPI0_0] # ymm1 = [15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15]
          vmovdqa ymm2, ymmword ptr [rip + .LCPI0_1] # ymm2 = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
          vpxor   xmm12, xmm12, xmm12
          vpxor   xmm4, xmm4, xmm4
          vpxor   xmm5, xmm5, xmm5
          vpxor   xmm6, xmm6, xmm6
  .LBB0_1:                                # =&gt;This Inner Loop Header: Depth=1
          vmovdqu ymm7, ymmword ptr [rdi + 8*rax]
          vmovdqu ymm8, ymmword ptr [rdi + 8*rax + 32]
          vmovdqu ymm9, ymmword ptr [rdi + 8*rax + 64]
          vmovdqu ymm10, ymmword ptr [rdi + 8*rax + 96]
          vpand   ymm11, ymm7, ymm1
          vpshufb ymm11, ymm2, ymm11
          vpsrlw  ymm7, ymm7, 4
          vpand   ymm7, ymm7, ymm1
          vpshufb ymm7, ymm2, ymm7
          vpaddb  ymm7, ymm11, ymm7
          vpsadbw ymm7, ymm12, ymm7
          vpand   ymm11, ymm8, ymm1
          vpshufb ymm11, ymm2, ymm11
          vpsrlw  ymm8, ymm8, 4
          vpand   ymm8, ymm8, ymm1
          vpshufb ymm8, ymm2, ymm8
          vpaddb  ymm8, ymm8, ymm11
          vpsadbw ymm8, ymm8, ymm12
          vpand   ymm11, ymm9, ymm1
          vpshufb ymm11, ymm2, ymm11
          vpsrlw  ymm9, ymm9, 4
          vpand   ymm9, ymm9, ymm1
          vpshufb ymm9, ymm2, ymm9
          vpaddb  ymm9, ymm9, ymm11
          vpsadbw ymm9, ymm9, ymm12
          vpand   ymm11, ymm10, ymm1
          vpshufb ymm11, ymm2, ymm11
          vpsrlw  ymm10, ymm10, 4
          vpand   ymm10, ymm10, ymm1
          vpshufb ymm10, ymm2, ymm10
          vpaddb  ymm10, ymm10, ymm11
          vpsadbw ymm10, ymm10, ymm12
          vextracti128    xmm3, ymm7, 1
          vpackusdw       xmm3, xmm7, xmm3
          vpaddd  xmm0, xmm0, xmm3
          vextracti128    xmm3, ymm8, 1
          vpackusdw       xmm3, xmm8, xmm3
          vpaddd  xmm4, xmm4, xmm3
          vextracti128    xmm3, ymm9, 1
          vpackusdw       xmm3, xmm9, xmm3
          vpaddd  xmm5, xmm5, xmm3
          vextracti128    xmm3, ymm10, 1
          vpackusdw       xmm3, xmm10, xmm3
          vpaddd  xmm6, xmm6, xmm3
          add     rax, 16
          cmp     rax, 1024
          jne     .LBB0_1
          vpaddd  xmm0, xmm4, xmm0
          vpaddd  xmm0, xmm5, xmm0
          vpaddd  xmm0, xmm6, xmm0
          vpshufd xmm1, xmm0, 238                 # xmm1 = xmm0[2,3,2,3]
          vpaddd  xmm0, xmm0, xmm1
          vpshufd xmm1, xmm0, 85                  # xmm1 = xmm0[1,1,1,1]
          vpaddd  xmm0, xmm0, xmm1
          vmovd   eax, xmm0
          vzeroupper
          ret
  </code></pre>
  <p><code>clang</code>'s code is similar to <code>gcc</code> when only <code>-mpopcnt</code> is on, with a bit of unrolling.</p>
  <pre><code>count:                                  # @count
          xor     ecx, ecx
          xor     eax, eax
  .LBB0_1:                                # =&gt;This Inner Loop Header: Depth=1
          popcnt  rdx, qword ptr [rdi + 8*rcx]
          add     edx, eax
          popcnt  rsi, qword ptr [rdi + 8*rcx + 8]
          add     esi, edx
          popcnt  rdx, qword ptr [rdi + 8*rcx + 16]
          popcnt  rax, qword ptr [rdi + 8*rcx + 24]
          add     edx, esi
          add     eax, edx
          add     rcx, 4
          cmp     rcx, 1024
          jne     .LBB0_1
          ret
  </code></pre>
  <p>According to this document (<a href="https://www.agner.org/optimize/instruction_tables.pdf" rel="nofollow noreferrer">https://www.agner.org/optimize/instruction_tables.pdf</a>), <code>popcnt</code> is a very cheap instruction on most architectures. Then why is <code>clang</code> generating such a bloat to replace <code>popcnt</code> when I clearly allowed to use it with <code>-mpopcnt</code>? The optimization level was all set to <code>-O3</code>.</p>
  <p>Here is a link to godbolt (<a href="https://godbolt.org/z/4vWK33a7c" rel="nofollow noreferrer">https://godbolt.org/z/4vWK33a7c</a>).</p>