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

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

[falk at debian 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

[Bug tree-optimization/16611] Terrible code generated for vector<bool>

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-07-17 22:49 -------
Lets look into the tree dump (which by the way looks like crap):
  __x = (struct _Bit_iterator *)v;
  __y = __x-><D10960>._M_offset;
  this = (struct _Bit_iterator_base *)&<D12708>;  <--- the address is not propagated so SRA is not 
working
  this->_M_p = __x-><D10960>._M_p;  <--- here
  this->_M_offset = __y; <--- her
  SR.334 = <D12708>.<D11089>._M_p;
  __tmp.<D11089>._M_offset = <D12708>.<D11089>._M_offset;
  __tmp.<D11089>._M_p = SR.334;
  this = (struct _Bit_iterator_base *)&__tmp; <--- here
  __n = (ptrdiff_t)(this->_M_offset + (unsigned int)(ptrdiff_t)x);
  this->_M_p = this->_M_p + (_Bit_type *)((unsigned int)(__n / 32) * 4);
  __n.345 = __n % 32;
  if (__n.345 < 0) goto <L1>; else goto <L2>;

<L1>:;
  this->_M_offset = (unsigned int)(__n.345 + 32); // <-- here
  this->_M_p = this->_M_p - 4B; // <-- here
  goto <bb 3> (<L3>);

<L2>:;
  this->_M_offset = (unsigned int)__n.345; // <-- here

<L3>:;
  return (int)(bool)(int)(bool)(int)(bool)((1 << (int)__tmp.<D11089>._M_offset & *__tmp.<D11089>.
_M_p) != 0); // <-- here

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
          Component|libstdc++                   |tree-optimization
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-07-17 22:49:01
               date|                            |


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

[Bug tree-optimization/16611] Terrible code generated for vector<bool>

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-10-16 14:11 -------
We look much better now but still little problems:
bool f(const std::vector<bool, std::allocator<bool> >&, size_t) (v, x)
{
  ptrdiff_t __n.82;
  unsigned int SR.77;
  _Bit_type * __x;
  ptrdiff_t __n;
  struct _Bit_iterator & __x;

<bb 0>:
  __x = &v->D.10279._M_impl._M_start; //<--this could be pushed into the next two instructions
  __n = (ptrdiff_t) (__x->D.8752._M_offset + (unsigned int) (ptrdiff_t) x);
  __x = __x->D.8752._M_p + (_Bit_type *) ((unsigned int) (__n / 32) * 4);
  __n.82 = __n % 32;
  if (__n.82 < 0) goto <L1>; else goto <L2>; //<-- could be done based on __n instead of __n.82

<L1>:;
  SR.77 = (unsigned int) (__n.82 + 32);
  __x = __x - 4B;
  goto <bb 3> (<L3>);

<L2>:;
  SR.77 = (unsigned int) __n.82;

<L3>:;
  return (int) (bool) (int) (bool) (int) (bool) ((1 << (int) SR.77 & *__x) != 0);

}

-- 


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

[Bug tree-optimization/16611] Terrible code generated for vector<bool>

[sabre at nondot dot org]

------- Additional Comments From sabre at nondot dot org  2005-04-11 19:40 -------
This code from stl_bvector.h is the problem:

  void _M_incr(ptrdiff_t __i) {
    difference_type __n = __i + _M_offset;
    _M_p += __n / _M_word_bit;
    __n = __n % _M_word_bit;
    if (__n < 0) {
      _M_offset = (unsigned int) __n + _M_word_bit;
      --_M_p;
    } else
      _M_offset = (unsigned int) __n;
  }

Note that the division and mod is performed on a signed __n value.  If it were
unsigned, the optimizer could trivially turn it into shift/and ops.

-Chris

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sabre at nondot dot org


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

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

[falk at debian dot org]

------- Additional Comments From falk at debian dot org  2005-04-12 08:07 -------
(In reply to comment #3)
> This code from stl_bvector.h is the problem: [...]

Hmm, right. I don't fully understand why it is done in this complicated
manner, does vector<bool>::operator[] need to do anything more than my 
example function? Anyway, I'll reassign it to libstdc++... feel free to
close it if it is unavoidable, or reassign back to tree-optimize if it is
actually an optimizer deficiency.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|tree-optimization           |libstdc++


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

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

[sabre at nondot dot org]

------- Additional Comments From sabre at nondot dot org  2005-04-12 14:31 -------
This is definately a libstdc++ issue.

-Chris

-- 


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

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

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-04-17 16:34 -------
Hi. It can well be a libstdc++ problem, and indeed I can imagine ways to avoid
signed integers in the code. However, I'm not sure that someone will actually
do the work, given the soon-to-be-deprecated status of vector<bool>... All in
all, wouldn't be more useful trying to improve the optimization of the code
as-is?!?

-- 


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

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

[falk at debian dot org]

------- Additional Comments From falk at debian dot org  2005-04-18 08:10 -------
(In reply to comment #6)
> Hi. It can well be a libstdc++ problem, and indeed I can imagine ways to avoid
> signed integers in the code. However, I'm not sure that someone will actually
> do the work, given the soon-to-be-deprecated status of vector<bool>... 

This is news to me. Does this mean that vector<bool> is not going to be special-
cased any more? That seems like a very bad idea to me, since programs will
suddenly take 8 times as much memory (or even more). What's the rationale?


-- 


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

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

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-04-18 14:23 -------
> This is news to me. Does this mean that vector<bool> is not going to be special-
> cased any more? That seems like a very bad idea to me, since programs will
> suddenly take 8 times as much memory (or even more). What's the rationale?

Oh, well, this is a *well* known issue: roughly, the C++ standard committee
considers vector<bool> a serious mistake, because, in short, doesn't conform
to *many* of the standard requirements for containers. The current plan (as 
of Lillehammer, last week) consists of two parts: 1- Deprecating vector<bool>,
2- Adding a new bit_vector container. Of course no one wants to remove the
current vector<bool> without a replacement. Please Google a bit for further
details or ask me privately.

-- 


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

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

[pcarlini at suse dot de]

------- Comment #12 from pcarlini at suse dot de  2006-08-06 14:47 -------
Now I get:

00000000 <_Z1fRKSt6vectorIbSaIbEEj>:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   8b 45 08                mov    0x8(%ebp),%eax
   6:   8b 4d 0c                mov    0xc(%ebp),%ecx
   9:   53                      push   %ebx
   a:   8b 10                   mov    (%eax),%edx
   c:   b8 01 00 00 00          mov    $0x1,%eax
  11:   89 cb                   mov    %ecx,%ebx
  13:   83 e1 1f                and    $0x1f,%ecx
  16:   c1 eb 05                shr    $0x5,%ebx
  19:   d3 e0                   shl    %cl,%eax
  1b:   85 04 9a                test   %eax,(%edx,%ebx,4)
  1e:   5b                      pop    %ebx
  1f:   5d                      pop    %ebp
  20:   0f 95 c0                setne  %al
  23:   0f b6 c0                movzbl %al,%eax
  26:   c3                      ret

I guess we can close the library issue.


-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.2.0


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

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

[paolo at gcc dot gnu dot org]

------- Comment #11 from paolo at gcc dot gnu dot org  2006-08-06 14:45 -------
Subject: Bug 16611

Author: paolo
Date: Sun Aug  6 14:45:04 2006
New Revision: 115972

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=115972
Log:
2006-08-06  Paolo Carlini  <pcarlini@suse.de>

        PR libstdc++/16611
        * include/bits/stl_bvector.h (vector<bool>::operator[],
        vector<bool>::operator[] const): Do not use iterator::operator+,
        hand code.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_bvector.h


-- 


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

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

[pcarlini at suse dot de]

-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pcarlini at suse dot de
                   |dot org                     |
             Status|NEW                         |ASSIGNED


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

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

[pcarlini at suse dot de]

------- Comment #10 from pcarlini at suse dot de  2005-12-23 21:13 -------
Well, I'm not sure that, besides code size, 4_1 is doing better than 4.0.2, but
both are certainly better than 3.4.x.


-- 


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

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

[pcarlini at suse dot de]

------- Comment #9 from pcarlini at suse dot de  2005-12-23 20:12 -------
FWIW, on x86-linux at least, we are making progress on the compiler side.

With 4.0.2 I get (-O2):

00000000 <_Z1fRKSt6vectorIbSaIbEEj>:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   53                      push   %ebx
   4:   8b 5d 08                mov    0x8(%ebp),%ebx
   7:   8b 55 0c                mov    0xc(%ebp),%edx
   a:   8b 43 04                mov    0x4(%ebx),%eax
   d:   01 d0                   add    %edx,%eax
   f:   89 c1                   mov    %eax,%ecx
  11:   c1 f9 1f                sar    $0x1f,%ecx
  14:   c1 e9 1b                shr    $0x1b,%ecx
  17:   8d 04 01                lea    (%ecx,%eax,1),%eax
  1a:   89 c2                   mov    %eax,%edx
  1c:   83 e0 1f                and    $0x1f,%eax
  1f:   c1 fa 05                sar    $0x5,%edx
  22:   c1 e2 02                shl    $0x2,%edx
  25:   03 13                   add    (%ebx),%edx
  27:   29 c8                   sub    %ecx,%eax
  29:   89 c1                   mov    %eax,%ecx
  2b:   78 13                   js     40 <_Z1fRKSt6vectorIbSaIbEEj+0x40>
  2d:   b8 01 00 00 00          mov    $0x1,%eax
  32:   d3 e0                   shl    %cl,%eax
  34:   85 02                   test   %eax,(%edx)
  36:   5b                      pop    %ebx
  37:   5d                      pop    %ebp
  38:   0f 95 c0                setne  %al
  3b:   83 e0 01                and    $0x1,%eax
  3e:   c3                      ret
  3f:   90                      nop
  40:   83 c1 20                add    $0x20,%ecx
  43:   b8 01 00 00 00          mov    $0x1,%eax
  48:   d3 e0                   shl    %cl,%eax
  4a:   83 ea 04                sub    $0x4,%edx
  4d:   85 02                   test   %eax,(%edx)
  4f:   5b                      pop    %ebx
  50:   5d                      pop    %ebp
  51:   0f 95 c0                setne  %al
  54:   83 e0 01                and    $0x1,%eax
  57:   c3                      ret


With current 4_1-branch:

00000000 <_Z1fRKSt6vectorIbSaIbEEj>:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   53                      push   %ebx
   4:   8b 5d 08                mov    0x8(%ebp),%ebx
   7:   8b 45 0c                mov    0xc(%ebp),%eax
   a:   8b 53 04                mov    0x4(%ebx),%edx
   d:   01 d0                   add    %edx,%eax
   f:   89 c1                   mov    %eax,%ecx
  11:   c1 f9 1f                sar    $0x1f,%ecx
  14:   c1 e9 1b                shr    $0x1b,%ecx
  17:   8d 04 01                lea    (%ecx,%eax,1),%eax
  1a:   89 c2                   mov    %eax,%edx
  1c:   83 e0 1f                and    $0x1f,%eax
  1f:   c1 fa 05                sar    $0x5,%edx
  22:   c1 e2 02                shl    $0x2,%edx
  25:   03 13                   add    (%ebx),%edx
  27:   29 c8                   sub    %ecx,%eax
  29:   89 c1                   mov    %eax,%ecx
  2b:   78 13                   js     40 <_Z1fRKSt6vectorIbSaIbEEj+0x40>
  2d:   b8 01 00 00 00          mov    $0x1,%eax
  32:   d3 e0                   shl    %cl,%eax
  34:   85 02                   test   %eax,(%edx)
  36:   5b                      pop    %ebx
  37:   5d                      pop    %ebp
  38:   0f 95 c0                setne  %al
  3b:   83 e0 01                and    $0x1,%eax
  3e:   c3                      ret
  3f:   90                      nop
  40:   83 c1 20                add    $0x20,%ecx
  43:   83 ea 04                sub    $0x4,%edx
  46:   eb e5                   jmp    2d <_Z1fRKSt6vectorIbSaIbEEj+0x2d>


-- 


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