[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