[Bug libstdc++/16611] New: Terrible code generated for vector<bool>

["falk at debian dot org" <gcc-bugzilla at gcc dot gnu dot org>]

If I look at the assembly of this function:

bool f(const std::vector<bool>& v, std::size_t x) {
    return v[x];
}

I get:

0000000000000020 <f(std::vector<bool, std::allocator<bool> > const&, unsigned
long)>:
  20:   08 00 50 a0     ldl     t1,8(a0)
  24:   00 00 70 a4     ldq     t2,0(a0)
  28:   90 ff de 23     lda     sp,-112(sp)
  2c:   21 f6 41 48     zapnot  t1,0xf,t0
  30:   68 00 5e b0     stl     t1,104(sp)
  34:   48 00 5e b0     stl     t1,72(sp)
  38:   11 04 21 42     addq    a1,t0,a1
  3c:   08 00 5e b0     stl     t1,8(sp)
  40:   38 00 5e b0     stl     t1,56(sp)
  44:   81 f7 27 4a     sra     a1,0x3f,t0
  48:   60 00 7e b4     stq     t2,96(sp)
  4c:   40 00 7e b4     stq     t2,64(sp)
  50:   81 56 27 48     srl     t0,0x3a,t0
  54:   00 00 7e b4     stq     t2,0(sp)
  58:   30 00 7e b4     stq     t2,48(sp)
  5c:   01 04 21 42     addq    a1,t0,t0
  60:   81 d7 20 48     sra     t0,0x6,t0
  64:   22 d7 20 48     sll     t0,0x6,t1
  68:   41 06 23 40     s8addq  t0,t2,t0
  6c:   31 05 22 42     subq    a1,t1,a1
  70:   f8 ff 61 20     lda     t2,-8(t0)
  74:   40 00 51 20     lda     t1,64(a1)
  78:   0d 00 20 ea     blt     a1,b0 <f(std::vector<bool, std::allocator<bool>
> const&, unsigned long)+0x90>
  7c:   60 00 3e b4     stq     t0,96(sp)
  80:   68 00 3e b2     stl     a1,104(sp)
  84:   68 00 3e a0     ldl     t0,104(sp)
  88:   60 00 5e a4     ldq     t1,96(sp)
  8c:   01 00 1f 20     lda     v0,1
  90:   20 07 01 48     sll     v0,t0,v0
  94:   00 00 22 a4     ldq     t0,0(t1)
  98:   00 00 01 44     and     v0,t0,v0
  9c:   a0 03 e0 43     cmpult  zero,v0,v0
  a0:   70 00 de 23     lda     sp,112(sp)
  a4:   01 80 fa 6b     ret
  a8:   1f 04 ff 47     nop     
  ac:   00 00 fe 2f     unop    
  b0:   68 00 5e b0     stl     t1,104(sp)
  b4:   60 00 7e b4     stq     t2,96(sp)
  b8:   f2 ff ff c3     br      84 <f(std::vector<bool, std::allocator<bool> >
const&, unsigned long)+0x64>
  bc:   00 00 fe 2f     unop    

It should really look more like the code I get for

struct vector_bool { unsigned long *data; };
bool f(const vector_bool& v, std::size_t i) {
    return (v.data[i / 64] >> (i % 64)) & 1;
}

which is

0000000000000000 <f(vector_bool const&, unsigned long)>:
   0:   00 00 50 a4     ldq     t1,0(a0)
   4:   81 d6 20 4a     srl     a1,0x6,t0
   8:   11 f0 27 46     and     a1,0x3f,a1
   c:   41 06 22 40     s8addq  t0,t1,t0
  10:   00 00 01 a4     ldq     v0,0(t0)
  14:   80 06 11 48     srl     v0,a1,v0
  18:   00 30 00 44     and     v0,0x1,v0
  1c:   01 80 fa 6b     ret

The code for .at() looks even more horrible.

-- 
           Summary: Terrible code generated for vector<bool>
           Product: gcc
           Version: 3.5.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P2
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: falk at debian dot org
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: alphaev68-unknown-linux-gnu
  GCC host triplet: alphaev68-unknown-linux-gnu
GCC target triplet: alphaev68-unknown-linux-gnu


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