[Bug other/25674] New: better optimization of builtin_popcountl (avoid iterations and lookup table).

[Bug other/25674] New: better optimization of builtin_popcountl (avoid iterations and lookup table).

[pluto at agmk dot net]

http://devnet.developerpipeline.com/documents/s=9858/q=1/ddj0503d/0503d.html

int popcount(long long b)
{
     b = (b & 0x5555555555555555LLU) + (b >> 1 & 0x5555555555555555LLU);
     b = (b & 0x3333333333333333LLU) + (b >> 2 & 0x3333333333333333LLU);
     b = (b + (b >> 4)) & 0x0F0F0F0F0F0F0F0FLLU;
     b = b + (b >> 8);
     b = b + (b >> 16);
     b = (b + (b >> 32)) & 0x7F;
     return (int)b;
}

0000000000000000 <popcount>:
   0:   48 b8 55 55 55 55 55    mov    $0x5555555555555555,%rax
   7:   55 55 55
   a:   48 89 fa                mov    %rdi,%rdx
   d:   48 d1 ff                sar    %rdi
  10:   48 21 c2                and    %rax,%rdx
  13:   48 21 c7                and    %rax,%rdi
  16:   48 b9 33 33 33 33 33    mov    $0x3333333333333333,%rcx
  1d:   33 33 33
  20:   48 01 fa                add    %rdi,%rdx
  23:   48 89 d0                mov    %rdx,%rax
  26:   48 c1 fa 02             sar    $0x2,%rdx
  2a:   48 21 ca                and    %rcx,%rdx
  2d:   48 21 c8                and    %rcx,%rax
  30:   48 01 d0                add    %rdx,%rax
  33:   48 89 c2                mov    %rax,%rdx
  36:   48 c1 fa 04             sar    $0x4,%rdx
  3a:   48 01 d0                add    %rdx,%rax
  3d:   48 ba 0f 0f 0f 0f 0f    mov    $0xf0f0f0f0f0f0f0f,%rdx
  44:   0f 0f 0f
  47:   48 21 d0                and    %rdx,%rax
  4a:   48 89 c2                mov    %rax,%rdx
  4d:   48 c1 fa 08             sar    $0x8,%rdx
  51:   48 01 d0                add    %rdx,%rax
  54:   48 89 c2                mov    %rax,%rdx
  57:   48 c1 fa 10             sar    $0x10,%rdx
  5b:   48 01 d0                add    %rdx,%rax
  5e:   48 89 c2                mov    %rax,%rdx
  61:   48 c1 fa 20             sar    $0x20,%rdx
  65:   48 01 d0                add    %rdx,%rax
  68:   83 e0 7f                and    $0x7f,%eax
  6b:   c3                      retq


-- 
           Summary: better optimization of builtin_popcountl (avoid
                    iterations and lookup table).
           Product: gcc
           Version: 4.1.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: other
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: pluto at agmk dot net
 GCC build triplet: x86-64
  GCC host triplet: x86-64
GCC target triplet: x86-64


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25674

[Bug other/25674] better optimization of builtin_popcountl (avoid iterations and lookup table).

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2006-01-04 21:24 -------
I am going to close this as a dup of bug 21812 since that references popcountl
already.

*** This bug has been marked as a duplicate of 21812 ***


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |DUPLICATE


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25674

[Bug other/25674] better optimization of builtin_popcountl (avoid iterations and lookup table).

[falk at debian dot org]

------- Comment #2 from falk at debian dot org  2006-01-04 22:39 -------
Actually, using a table is faster when the cache is hot (about 15%).
The problem is that libgcc doesn't unroll the loop.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25674