From 014d77a2107fec8ba978a7428fd4d04e0bf8e168 Mon Sep 17 00:00:00 2001 From: Jean Christophe Beyler Date: Mon, 2 Jun 2014 11:21:21 -0700 Subject: [PATCH] ART: BitVector not calculating number_of_bits correctly The number_of_bits_ field has an unclear intent. Instead, using storage_size_ * kWordBits when relevant. Change-Id: I8c13be0d6643de37813fb154296d451f22c298c8 Signed-off-by: Jean Christophe Beyler --- compiler/optimizing/liveness_test.cc | 390 +++++++++++++++++------------------ runtime/base/bit_vector.cc | 8 +- runtime/base/bit_vector.h | 1 - 3 files changed, 198 insertions(+), 201 deletions(-) diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc index 53e7bbe40..0dbe3227d 100644 --- a/compiler/optimizing/liveness_test.cc +++ b/compiler/optimizing/liveness_test.cc @@ -79,17 +79,17 @@ TEST(LivenessTest, CFG1) { TEST(LivenessTest, CFG2) { const char* expected = "Block 0\n" - " live in: (0)\n" - " live out: (1)\n" - " kill: (1)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (10000000000000000000000000000000)\n" + " kill: (10000000000000000000000000000000)\n" "Block 1\n" - " live in: (1)\n" - " live out: (0)\n" - " kill: (0)\n" + " live in: (10000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 2\n" - " live in: (0)\n" - " live out: (0)\n" - " kill: (0)\n"; + " live in: (00000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, @@ -101,21 +101,21 @@ TEST(LivenessTest, CFG2) { TEST(LivenessTest, CFG3) { const char* expected = "Block 0\n" // entry block - " live in: (000)\n" - " live out: (110)\n" - " kill: (110)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (11000000000000000000000000000000)\n" + " kill: (11000000000000000000000000000000)\n" "Block 1\n" // block with add - " live in: (110)\n" - " live out: (001)\n" - " kill: (001)\n" + " live in: (11000000000000000000000000000000)\n" + " live out: (00100000000000000000000000000000)\n" + " kill: (00100000000000000000000000000000)\n" "Block 2\n" // block with return - " live in: (001)\n" - " live out: (000)\n" - " kill: (000)\n" + " live in: (00100000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 3\n" // exit block - " live in: (000)\n" - " live out: (000)\n" - " kill: (000)\n"; + " live in: (00000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n"; const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 3 << 12 | 0, @@ -140,29 +140,29 @@ TEST(LivenessTest, CFG4) { // (constant0, constant4, constant5, phi, equal test) const char* expected = "Block 0\n" // entry block - " live in: (00000)\n" - " live out: (11100)\n" - " kill: (11100)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (11100000000000000000000000000000)\n" + " kill: (11100000000000000000000000000000)\n" "Block 1\n" // block with if - " live in: (11100)\n" - " live out: (01100)\n" - " kill: (00010)\n" + " live in: (11100000000000000000000000000000)\n" + " live out: (01100000000000000000000000000000)\n" + " kill: (00010000000000000000000000000000)\n" "Block 2\n" // else block - " live in: (01000)\n" - " live out: (00000)\n" - " kill: (00000)\n" + " live in: (01000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 3\n" // then block - " live in: (00100)\n" - " live out: (00000)\n" - " kill: (00000)\n" + " live in: (00100000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 4\n" // return block - " live in: (00000)\n" - " live out: (00000)\n" - " kill: (00001)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00001000000000000000000000000000)\n" "Block 5\n" // exit block - " live in: (00000)\n" - " live out: (00000)\n" - " kill: (00000)\n"; + " live in: (00000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, @@ -184,29 +184,29 @@ TEST(LivenessTest, CFG5) { // return a; const char* expected = "Block 0\n" // entry block - " live in: (0000)\n" - " live out: (1100)\n" - " kill: (1100)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (11000000000000000000000000000000)\n" + " kill: (11000000000000000000000000000000)\n" "Block 1\n" // block with if - " live in: (1100)\n" - " live out: (1100)\n" - " kill: (0010)\n" + " live in: (11000000000000000000000000000000)\n" + " live out: (11000000000000000000000000000000)\n" + " kill: (00100000000000000000000000000000)\n" "Block 2\n" // else block - " live in: (0100)\n" - " live out: (0000)\n" - " kill: (0000)\n" + " live in: (01000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 3\n" // return block - " live in: (0000)\n" - " live out: (0000)\n" - " kill: (0001)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00010000000000000000000000000000)\n" "Block 4\n" // exit block - " live in: (0000)\n" - " live out: (0000)\n" - " kill: (0000)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 5\n" // block to avoid critical edge. Predecessor is 1, successor is 3. - " live in: (1000)\n" - " live out: (0000)\n" - " kill: (0000)\n"; + " live in: (10000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, @@ -226,29 +226,29 @@ TEST(LivenessTest, Loop1) { // return; const char* expected = "Block 0\n" // entry block - " live in: (0000)\n" - " live out: (1100)\n" - " kill: (1100)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (11000000000000000000000000000000)\n" + " kill: (11000000000000000000000000000000)\n" "Block 1\n" // pre header - " live in: (1100)\n" - " live out: (0100)\n" - " kill: (0000)\n" + " live in: (11000000000000000000000000000000)\n" + " live out: (01000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 2\n" // loop header - " live in: (0100)\n" - " live out: (0100)\n" - " kill: (0011)\n" + " live in: (01000000000000000000000000000000)\n" + " live out: (01000000000000000000000000000000)\n" + " kill: (00110000000000000000000000000000)\n" "Block 3\n" // back edge - " live in: (0100)\n" - " live out: (0100)\n" - " kill: (0000)\n" + " live in: (01000000000000000000000000000000)\n" + " live out: (01000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 4\n" // return block - " live in: (0000)\n" - " live out: (0000)\n" - " kill: (0000)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 5\n" // exit block - " live in: (0000)\n" - " live out: (0000)\n" - " kill: (0000)\n"; + " live in: (00000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( @@ -270,29 +270,29 @@ TEST(LivenessTest, Loop3) { // return 5; const char* expected = "Block 0\n" - " live in: (00000)\n" - " live out: (11100)\n" - " kill: (11100)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (11100000000000000000000000000000)\n" + " kill: (11100000000000000000000000000000)\n" "Block 1\n" - " live in: (11100)\n" - " live out: (01100)\n" - " kill: (00000)\n" + " live in: (11100000000000000000000000000000)\n" + " live out: (01100000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 2\n" // loop header - " live in: (01100)\n" - " live out: (01100)\n" - " kill: (00011)\n" + " live in: (01100000000000000000000000000000)\n" + " live out: (01100000000000000000000000000000)\n" + " kill: (00011000000000000000000000000000)\n" "Block 3\n" // back edge - " live in: (01100)\n" - " live out: (01100)\n" - " kill: (00000)\n" + " live in: (01100000000000000000000000000000)\n" + " live out: (01100000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 4\n" // return block - " live in: (00100)\n" - " live out: (00000)\n" - " kill: (00000)\n" + " live in: (00100000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 5\n" // exit block - " live in: (00000)\n" - " live out: (00000)\n" - " kill: (00000)\n"; + " live in: (00000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n"; const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 0 | 0, @@ -318,33 +318,33 @@ TEST(LivenessTest, Loop4) { // (constant0, constant4, phi, equal test) const char* expected = "Block 0\n" - " live in: (0000)\n" - " live out: (1100)\n" - " kill: (1100)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (11000000000000000000000000000000)\n" + " kill: (11000000000000000000000000000000)\n" "Block 1\n" - " live in: (1100)\n" - " live out: (1100)\n" - " kill: (0000)\n" + " live in: (11000000000000000000000000000000)\n" + " live out: (11000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 2\n" // loop header - " live in: (0100)\n" - " live out: (0110)\n" - " kill: (0011)\n" + " live in: (01000000000000000000000000000000)\n" + " live out: (01100000000000000000000000000000)\n" + " kill: (00110000000000000000000000000000)\n" "Block 3\n" // back edge - " live in: (0100)\n" - " live out: (0100)\n" - " kill: (0000)\n" + " live in: (01000000000000000000000000000000)\n" + " live out: (01000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 4\n" // pre loop header - " live in: (1100)\n" - " live out: (0100)\n" - " kill: (0000)\n" + " live in: (11000000000000000000000000000000)\n" + " live out: (01000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 5\n" // return block - " live in: (0010)\n" - " live out: (0000)\n" - " kill: (0000)\n" + " live in: (00100000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 6\n" // exit block - " live in: (0000)\n" - " live out: (0000)\n" - " kill: (0000)\n"; + " live in: (00000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, @@ -366,41 +366,41 @@ TEST(LivenessTest, Loop5) { // equal in block 4) const char* expected = "Block 0\n" - " live in: (0000000)\n" - " live out: (1110000)\n" - " kill: (1110000)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (11100000000000000000000000000000)\n" + " kill: (11100000000000000000000000000000)\n" "Block 1\n" - " live in: (1110000)\n" - " live out: (0110000)\n" - " kill: (0001000)\n" + " live in: (11100000000000000000000000000000)\n" + " live out: (01100000000000000000000000000000)\n" + " kill: (00010000000000000000000000000000)\n" "Block 2\n" - " live in: (0100000)\n" - " live out: (0000000)\n" - " kill: (0000000)\n" + " live in: (01000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 3\n" - " live in: (0010000)\n" - " live out: (0000000)\n" - " kill: (0000000)\n" + " live in: (00100000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 4\n" // loop header - " live in: (0000000)\n" - " live out: (0000010)\n" - " kill: (0000011)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (00000100000000000000000000000000)\n" + " kill: (00000110000000000000000000000000)\n" "Block 5\n" // back edge - " live in: (0000010)\n" - " live out: (0000000)\n" - " kill: (0000000)\n" + " live in: (00000100000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 6\n" // return block - " live in: (0000010)\n" - " live out: (0000000)\n" - " kill: (0000000)\n" + " live in: (00000100000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 7\n" // exit block - " live in: (0000000)\n" - " live out: (0000000)\n" - " kill: (0000000)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 8\n" // synthesized pre header - " live in: (0000000)\n" - " live out: (0000000)\n" - " kill: (0000100)\n"; + " live in: (00000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00001000000000000000000000000000)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, @@ -421,41 +421,41 @@ TEST(LivenessTest, Loop6) { // phi in block 8) const char* expected = "Block 0\n" - " live in: (0000000)\n" - " live out: (1110000)\n" - " kill: (1110000)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (11100000000000000000000000000000)\n" + " kill: (11100000000000000000000000000000)\n" "Block 1\n" - " live in: (1110000)\n" - " live out: (0110000)\n" - " kill: (0000000)\n" + " live in: (11100000000000000000000000000000)\n" + " live out: (01100000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 2\n" // loop header - " live in: (0110000)\n" - " live out: (0111000)\n" - " kill: (0001100)\n" + " live in: (01100000000000000000000000000000)\n" + " live out: (01110000000000000000000000000000)\n" + " kill: (00011000000000000000000000000000)\n" "Block 3\n" - " live in: (0110000)\n" - " live out: (0110000)\n" - " kill: (0000010)\n" + " live in: (01100000000000000000000000000000)\n" + " live out: (01100000000000000000000000000000)\n" + " kill: (00000100000000000000000000000000)\n" "Block 4\n" // original back edge - " live in: (0110000)\n" - " live out: (0110000)\n" - " kill: (0000000)\n" + " live in: (01100000000000000000000000000000)\n" + " live out: (01100000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 5\n" // original back edge - " live in: (0110000)\n" - " live out: (0110000)\n" - " kill: (0000000)\n" + " live in: (01100000000000000000000000000000)\n" + " live out: (01100000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 6\n" // return block - " live in: (0001000)\n" - " live out: (0000000)\n" - " kill: (0000000)\n" + " live in: (00010000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 7\n" // exit block - " live in: (0000000)\n" - " live out: (0000000)\n" - " kill: (0000000)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 8\n" // synthesized back edge - " live in: (0110000)\n" - " live out: (0110000)\n" - " kill: (0000001)\n"; + " live in: (01100000000000000000000000000000)\n" + " live out: (01100000000000000000000000000000)\n" + " kill: (00000010000000000000000000000000)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, @@ -477,41 +477,41 @@ TEST(LivenessTest, Loop7) { // phi in block 6) const char* expected = "Block 0\n" - " live in: (0000000)\n" - " live out: (1110000)\n" - " kill: (1110000)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (11100000000000000000000000000000)\n" + " kill: (11100000000000000000000000000000)\n" "Block 1\n" - " live in: (1110000)\n" - " live out: (0110000)\n" - " kill: (0000000)\n" + " live in: (11100000000000000000000000000000)\n" + " live out: (01100000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 2\n" // loop header - " live in: (0110000)\n" - " live out: (0111000)\n" - " kill: (0001100)\n" + " live in: (01100000000000000000000000000000)\n" + " live out: (01110000000000000000000000000000)\n" + " kill: (00011000000000000000000000000000)\n" "Block 3\n" - " live in: (0110000)\n" - " live out: (0110000)\n" - " kill: (0000010)\n" + " live in: (01100000000000000000000000000000)\n" + " live out: (01100000000000000000000000000000)\n" + " kill: (00000100000000000000000000000000)\n" "Block 4\n" // loop exit - " live in: (0010000)\n" - " live out: (0000000)\n" - " kill: (0000000)\n" + " live in: (00100000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 5\n" // back edge - " live in: (0110000)\n" - " live out: (0110000)\n" - " kill: (0000000)\n" + " live in: (01100000000000000000000000000000)\n" + " live out: (01100000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 6\n" // return block - " live in: (0000000)\n" - " live out: (0000000)\n" - " kill: (0000001)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000010000000000000000000000000)\n" "Block 7\n" // exit block - " live in: (0000000)\n" - " live out: (0000000)\n" - " kill: (0000000)\n" + " live in: (00000000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n" "Block 8\n" // synthesized block to avoid critical edge. - " live in: (0001000)\n" - " live out: (0000000)\n" - " kill: (0000000)\n"; + " live in: (00010000000000000000000000000000)\n" + " live out: (00000000000000000000000000000000)\n" + " kill: (00000000000000000000000000000000)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc index 0053389b4..1b9022e17 100644 --- a/runtime/base/bit_vector.cc +++ b/runtime/base/bit_vector.cc @@ -43,8 +43,7 @@ BitVector::BitVector(uint32_t start_bits, : allocator_(allocator), expandable_(expandable), storage_size_(storage_size), - storage_(storage), - number_of_bits_(start_bits) { + storage_(storage) { COMPILE_ASSERT(sizeof(*storage_) == kWordBytes, check_word_bytes); COMPILE_ASSERT(sizeof(*storage_) * 8u == kWordBits, check_word_bits); if (storage_ == nullptr) { @@ -95,7 +94,6 @@ void BitVector::SetBit(uint32_t num) { // TOTO: collect stats on space wasted because of resize. storage_ = new_storage; storage_size_ = new_size; - number_of_bits_ = num; } storage_[num >> 5] |= check_masks[num & 0x1f]; @@ -434,7 +432,7 @@ void BitVector::DumpIndicesHelper(const char* prefix, std::ostringstream& buffer buffer << prefix; } - for (size_t i = 0; i < number_of_bits_; i++) { + for (size_t i = 0; i < storage_size_ * kWordBits; i++) { if (IsBitSet(i)) { buffer << i << " "; } @@ -448,7 +446,7 @@ void BitVector::DumpHelper(const char* prefix, std::ostringstream& buffer) const } buffer << '('; - for (size_t i = 0; i < number_of_bits_; i++) { + for (size_t i = 0; i < storage_size_ * kWordBits; i++) { buffer << IsBitSet(i); } buffer << ')'; diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h index 8f9afff47..fb1646f7f 100644 --- a/runtime/base/bit_vector.h +++ b/runtime/base/bit_vector.h @@ -247,7 +247,6 @@ class BitVector { const bool expandable_; // expand bitmap if we run out? uint32_t storage_size_; // current size, in 32-bit words. uint32_t* storage_; - uint32_t number_of_bits_; }; -- 2.11.0