Implementation of a fixed-size bit vector....

Implementation of a fixed-size bit vector.

This is a basic implementation bit vector containing an fixed 
arbitrary number of bits.


Committed: http://code.google.com/p/v8/source/detail?r=3991

[fschneider, 2010-03-01 23:09:11]

We may need this for liveness analysis and possibly for other data flow passes
as well. I hope we don't have such a thing already in the code base :)

[Kevin Millikin (Chromium), 2010-03-02 09:24:28]

Initial round of comments.

http://codereview.chromium.org/660321/diff/9/1011
File src/data-flow.h (right):

http://codereview.chromium.org/660321/diff/9/1011#newcode49
src/data-flow.h:49: // Copy constructor copies the backing vector.
You should also have an assignment operator.

http://codereview.chromium.org/660321/diff/9/1011#newcode57
src/data-flow.h:57: uint32_t Get(int i) {
Call this Contains, have it return bool.

http://codereview.chromium.org/660321/diff/9/1011#newcode63
src/data-flow.h:63: void Set(int i) {
Call this Add.

http://codereview.chromium.org/660321/diff/9/1011#newcode70
src/data-flow.h:70: void Clear(int i) {
Call this Remove.

http://codereview.chromium.org/660321/diff/9/1011#newcode77
src/data-flow.h:77: BitVector Union(BitVector other) {
Pass other as const BitVector&.  I think this function should mutate the object.
 It's quite common in data-flow analysis to have Value[i+1] =
Union(Value[i],Something) where the old Value[i] is no longer needed.

The caller can choose to construct a new copy if it wants to preserve the old,
but that behavior is not forced.

http://codereview.chromium.org/660321/diff/9/1011#newcode94
src/data-flow.h:94: 
Difference is the other operation we will almost certainly need.

http://codereview.chromium.org/660321/diff/9/1011#newcode99
src/data-flow.h:99: Vector<uint32_t> bits_;
This should be EmbeddedVector?  Then you don't have to have a call to New in the
constructor and Dispose in the destructor.  That seems better when you are
copying them around and they're small objects.

[fschneider, 2010-03-02 10:14:19]

http://codereview.chromium.org/660321/diff/9/1011
File src/data-flow.h (right):

http://codereview.chromium.org/660321/diff/9/1011#newcode49
src/data-flow.h:49: // Copy constructor copies the backing vector.
On 2010/03/02 09:24:28, Kevin Millikin wrote:
> You should also have an assignment operator.

Done. Removed copy constructor completely.

http://codereview.chromium.org/660321/diff/9/1011#newcode57
src/data-flow.h:57: uint32_t Get(int i) {
On 2010/03/02 09:24:28, Kevin Millikin wrote:
> Call this Contains, have it return bool.

Done.

http://codereview.chromium.org/660321/diff/9/1011#newcode63
src/data-flow.h:63: void Set(int i) {
On 2010/03/02 09:24:28, Kevin Millikin wrote:
> Call this Add.

Done.

http://codereview.chromium.org/660321/diff/9/1011#newcode70
src/data-flow.h:70: void Clear(int i) {
On 2010/03/02 09:24:28, Kevin Millikin wrote:
> Call this Remove.

Done.

http://codereview.chromium.org/660321/diff/9/1011#newcode77
src/data-flow.h:77: BitVector Union(BitVector other) {
On 2010/03/02 09:24:28, Kevin Millikin wrote:
> Pass other as const BitVector&.  I think this function should mutate the
object.
>  It's quite common in data-flow analysis to have Value[i+1] =
> Union(Value[i],Something) where the old Value[i] is no longer needed.
> 
> The caller can choose to construct a new copy if it wants to preserve the old,
> but that behavior is not forced.

Done. I'm passing BitVector* now in all functions.

http://codereview.chromium.org/660321/diff/9/1011#newcode94
src/data-flow.h:94: 
On 2010/03/02 09:24:28, Kevin Millikin wrote:
> Difference is the other operation we will almost certainly need.

Agreed. We can add new operations as we go along.

http://codereview.chromium.org/660321/diff/9/1011#newcode99
src/data-flow.h:99: Vector<uint32_t> bits_;
On 2010/03/02 09:24:28, Kevin Millikin wrote:
> This should be EmbeddedVector?  Then you don't have to have a call to New in
the
> constructor and Dispose in the destructor.  That seems better when you are
> copying them around and they're small objects.

Leaving as is for now. EmebeddedVector takes size as a template parameter.
Ideally, we'd have an dynamically sized embedded vector.

[fschneider, 2010-03-02 10:16:13]

http://codereview.chromium.org/660321/diff/9/1011
File src/data-flow.h (right):

http://codereview.chromium.org/660321/diff/9/1011#newcode77
src/data-flow.h:77: BitVector Union(BitVector other) {
On 2010/03/02 10:14:23, fschneider wrote:
> On 2010/03/02 09:24:28, Kevin Millikin wrote:
> > Pass other as const BitVector&.  I think this function should mutate the
> object.
> >  It's quite common in data-flow analysis to have Value[i+1] =
> > Union(Value[i],Something) where the old Value[i] is no longer needed.
> > 
> > The caller can choose to construct a new copy if it wants to preserve the
old,
> > but that behavior is not forced.
> 
> Done. I'm passing BitVector* now in all functions.

Ignore the previous response. I'm passing const-references const BitVector&
instead.

[Kevin Millikin (Chromium), 2010-03-02 10:24:11]

LGTM.

http://codereview.chromium.org/660321/diff/1017/13
File src/data-flow.h (right):

http://codereview.chromium.org/660321/diff/1017/13#newcode61
src/data-flow.h:61: return (block & (1U << (i % 32))) ? 1 : 0;
return (block & (1U << (i % 32))) != 0;

http://codereview.chromium.org/660321/diff/1017/13#newcode66
src/data-flow.h:66: uint32_t block = bits_[i / 32];
It probably doesn't make a difference, but you can simply write:

bits_[i / 32] |= (1U << (i % 32));

http://codereview.chromium.org/660321/diff/1017/13#newcode81
src/data-flow.h:81: bits_[i] = bits_[i] | other.bits_[i];
bits_[i] |= other.bits_[i] ?

[fschneider, 2010-03-02 10:40:42]

http://codereview.chromium.org/660321/diff/1017/13
File src/data-flow.h (right):

http://codereview.chromium.org/660321/diff/1017/13#newcode61
src/data-flow.h:61: return (block & (1U << (i % 32))) ? 1 : 0;
On 2010/03/02 10:24:11, Kevin Millikin wrote:
> return (block & (1U << (i % 32))) != 0;

Done.

http://codereview.chromium.org/660321/diff/1017/13#newcode66
src/data-flow.h:66: uint32_t block = bits_[i / 32];
On 2010/03/02 10:24:11, Kevin Millikin wrote:
> It probably doesn't make a difference, but you can simply write:
> 
> bits_[i / 32] |= (1U << (i % 32));

Done.

http://codereview.chromium.org/660321/diff/1017/13#newcode81
src/data-flow.h:81: bits_[i] = bits_[i] | other.bits_[i];
On 2010/03/02 10:24:11, Kevin Millikin wrote:
> bits_[i] |= other.bits_[i] ?

Done.