diff options
Diffstat (limited to 'compiler/optimizing/liveness_test.cc')
-rw-r--r-- | compiler/optimizing/liveness_test.cc | 409 |
1 files changed, 211 insertions, 198 deletions
diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc index 0dbe322..7a33620 100644 --- a/compiler/optimizing/liveness_test.cc +++ b/compiler/optimizing/liveness_test.cc @@ -26,6 +26,18 @@ namespace art { +static void DumpBitVector(BitVector* vector, + std::ostream& buffer, + size_t count, + const char* prefix) { + buffer << prefix; + buffer << '('; + for (size_t i = 0; i < count; ++i) { + buffer << vector->IsBitSet(i); + } + buffer << ")\n"; +} + static void TestCode(const uint16_t* data, const char* expected) { ArenaPool pool; ArenaAllocator allocator(&pool); @@ -43,12 +55,13 @@ static void TestCode(const uint16_t* data, const char* expected) { for (HInsertionOrderIterator it(*graph); !it.Done(); it.Advance()) { HBasicBlock* block = it.Current(); buffer << "Block " << block->GetBlockId() << std::endl; + size_t ssa_values = liveness.GetNumberOfSsaValues(); BitVector* live_in = liveness.GetLiveInSet(*block); - live_in->Dump(buffer, " live in: "); + DumpBitVector(live_in, buffer, ssa_values, " live in: "); BitVector* live_out = liveness.GetLiveOutSet(*block); - live_out->Dump(buffer, " live out: "); + DumpBitVector(live_out, buffer, ssa_values, " live out: "); BitVector* kill = liveness.GetKillSet(*block); - kill->Dump(buffer, " kill: "); + DumpBitVector(kill, buffer, ssa_values, " kill: "); } ASSERT_STREQ(expected, buffer.str().c_str()); } @@ -79,17 +92,17 @@ TEST(LivenessTest, CFG1) { TEST(LivenessTest, CFG2) { const char* expected = "Block 0\n" - " live in: (00000000000000000000000000000000)\n" - " live out: (10000000000000000000000000000000)\n" - " kill: (10000000000000000000000000000000)\n" + " live in: (0)\n" + " live out: (1)\n" + " kill: (1)\n" "Block 1\n" - " live in: (10000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (1)\n" + " live out: (0)\n" + " kill: (0)\n" "Block 2\n" - " live in: (00000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n"; + " live in: (0)\n" + " live out: (0)\n" + " kill: (0)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, @@ -101,21 +114,21 @@ TEST(LivenessTest, CFG2) { TEST(LivenessTest, CFG3) { const char* expected = "Block 0\n" // entry block - " live in: (00000000000000000000000000000000)\n" - " live out: (11000000000000000000000000000000)\n" - " kill: (11000000000000000000000000000000)\n" + " live in: (000)\n" + " live out: (110)\n" + " kill: (110)\n" "Block 1\n" // block with add - " live in: (11000000000000000000000000000000)\n" - " live out: (00100000000000000000000000000000)\n" - " kill: (00100000000000000000000000000000)\n" + " live in: (110)\n" + " live out: (001)\n" + " kill: (001)\n" "Block 2\n" // block with return - " live in: (00100000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (001)\n" + " live out: (000)\n" + " kill: (000)\n" "Block 3\n" // exit block - " live in: (00000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n"; + " live in: (000)\n" + " live out: (000)\n" + " kill: (000)\n"; const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 3 << 12 | 0, @@ -140,29 +153,29 @@ TEST(LivenessTest, CFG4) { // (constant0, constant4, constant5, phi, equal test) const char* expected = "Block 0\n" // entry block - " live in: (00000000000000000000000000000000)\n" - " live out: (11100000000000000000000000000000)\n" - " kill: (11100000000000000000000000000000)\n" + " live in: (00000)\n" + " live out: (11100)\n" + " kill: (11100)\n" "Block 1\n" // block with if - " live in: (11100000000000000000000000000000)\n" - " live out: (01100000000000000000000000000000)\n" - " kill: (00010000000000000000000000000000)\n" + " live in: (11100)\n" + " live out: (01100)\n" + " kill: (00010)\n" "Block 2\n" // else block - " live in: (01000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (01000)\n" + " live out: (00000)\n" + " kill: (00000)\n" "Block 3\n" // then block - " live in: (00100000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (00100)\n" + " live out: (00000)\n" + " kill: (00000)\n" "Block 4\n" // return block - " live in: (00000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00001000000000000000000000000000)\n" + " live in: (00000)\n" + " live out: (00000)\n" + " kill: (00001)\n" "Block 5\n" // exit block - " live in: (00000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n"; + " live in: (00000)\n" + " live out: (00000)\n" + " kill: (00000)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, @@ -184,29 +197,29 @@ TEST(LivenessTest, CFG5) { // return a; const char* expected = "Block 0\n" // entry block - " live in: (00000000000000000000000000000000)\n" - " live out: (11000000000000000000000000000000)\n" - " kill: (11000000000000000000000000000000)\n" + " live in: (0000)\n" + " live out: (1100)\n" + " kill: (1100)\n" "Block 1\n" // block with if - " live in: (11000000000000000000000000000000)\n" - " live out: (11000000000000000000000000000000)\n" - " kill: (00100000000000000000000000000000)\n" + " live in: (1100)\n" + " live out: (1100)\n" + " kill: (0010)\n" "Block 2\n" // else block - " live in: (01000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0100)\n" + " live out: (0000)\n" + " kill: (0000)\n" "Block 3\n" // return block - " live in: (00000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00010000000000000000000000000000)\n" + " live in: (0000)\n" + " live out: (0000)\n" + " kill: (0001)\n" "Block 4\n" // exit block - " live in: (00000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0000)\n" + " live out: (0000)\n" + " kill: (0000)\n" "Block 5\n" // block to avoid critical edge. Predecessor is 1, successor is 3. - " live in: (10000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n"; + " live in: (1000)\n" + " live out: (0000)\n" + " kill: (0000)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, @@ -226,29 +239,29 @@ TEST(LivenessTest, Loop1) { // return; const char* expected = "Block 0\n" // entry block - " live in: (00000000000000000000000000000000)\n" - " live out: (11000000000000000000000000000000)\n" - " kill: (11000000000000000000000000000000)\n" + " live in: (0000)\n" + " live out: (1100)\n" + " kill: (1100)\n" "Block 1\n" // pre header - " live in: (11000000000000000000000000000000)\n" - " live out: (01000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (1100)\n" + " live out: (0100)\n" + " kill: (0000)\n" "Block 2\n" // loop header - " live in: (01000000000000000000000000000000)\n" - " live out: (01000000000000000000000000000000)\n" - " kill: (00110000000000000000000000000000)\n" + " live in: (0100)\n" + " live out: (0100)\n" + " kill: (0011)\n" "Block 3\n" // back edge - " live in: (01000000000000000000000000000000)\n" - " live out: (01000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0100)\n" + " live out: (0100)\n" + " kill: (0000)\n" "Block 4\n" // return block - " live in: (00000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0000)\n" + " live out: (0000)\n" + " kill: (0000)\n" "Block 5\n" // exit block - " live in: (00000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n"; + " live in: (0000)\n" + " live out: (0000)\n" + " kill: (0000)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( @@ -270,29 +283,29 @@ TEST(LivenessTest, Loop3) { // return 5; const char* expected = "Block 0\n" - " live in: (00000000000000000000000000000000)\n" - " live out: (11100000000000000000000000000000)\n" - " kill: (11100000000000000000000000000000)\n" + " live in: (00000)\n" + " live out: (11100)\n" + " kill: (11100)\n" "Block 1\n" - " live in: (11100000000000000000000000000000)\n" - " live out: (01100000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (11100)\n" + " live out: (01100)\n" + " kill: (00000)\n" "Block 2\n" // loop header - " live in: (01100000000000000000000000000000)\n" - " live out: (01100000000000000000000000000000)\n" - " kill: (00011000000000000000000000000000)\n" + " live in: (01100)\n" + " live out: (01100)\n" + " kill: (00011)\n" "Block 3\n" // back edge - " live in: (01100000000000000000000000000000)\n" - " live out: (01100000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (01100)\n" + " live out: (01100)\n" + " kill: (00000)\n" "Block 4\n" // return block - " live in: (00100000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (00100)\n" + " live out: (00000)\n" + " kill: (00000)\n" "Block 5\n" // exit block - " live in: (00000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n"; + " live in: (00000)\n" + " live out: (00000)\n" + " kill: (00000)\n"; const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 0 | 0, @@ -318,33 +331,33 @@ TEST(LivenessTest, Loop4) { // (constant0, constant4, phi, equal test) const char* expected = "Block 0\n" - " live in: (00000000000000000000000000000000)\n" - " live out: (11000000000000000000000000000000)\n" - " kill: (11000000000000000000000000000000)\n" + " live in: (0000)\n" + " live out: (1100)\n" + " kill: (1100)\n" "Block 1\n" - " live in: (11000000000000000000000000000000)\n" - " live out: (11000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (1100)\n" + " live out: (1100)\n" + " kill: (0000)\n" "Block 2\n" // loop header - " live in: (01000000000000000000000000000000)\n" - " live out: (01100000000000000000000000000000)\n" - " kill: (00110000000000000000000000000000)\n" + " live in: (0100)\n" + " live out: (0110)\n" + " kill: (0011)\n" "Block 3\n" // back edge - " live in: (01000000000000000000000000000000)\n" - " live out: (01000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0100)\n" + " live out: (0100)\n" + " kill: (0000)\n" "Block 4\n" // pre loop header - " live in: (11000000000000000000000000000000)\n" - " live out: (01000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (1100)\n" + " live out: (0100)\n" + " kill: (0000)\n" "Block 5\n" // return block - " live in: (00100000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0010)\n" + " live out: (0000)\n" + " kill: (0000)\n" "Block 6\n" // exit block - " live in: (00000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n"; + " live in: (0000)\n" + " live out: (0000)\n" + " kill: (0000)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, @@ -366,41 +379,41 @@ TEST(LivenessTest, Loop5) { // equal in block 4) const char* expected = "Block 0\n" - " live in: (00000000000000000000000000000000)\n" - " live out: (11100000000000000000000000000000)\n" - " kill: (11100000000000000000000000000000)\n" + " live in: (0000000)\n" + " live out: (1110000)\n" + " kill: (1110000)\n" "Block 1\n" - " live in: (11100000000000000000000000000000)\n" - " live out: (01100000000000000000000000000000)\n" - " kill: (00010000000000000000000000000000)\n" + " live in: (1110000)\n" + " live out: (0110000)\n" + " kill: (0001000)\n" "Block 2\n" - " live in: (01000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0100000)\n" + " live out: (0000000)\n" + " kill: (0000000)\n" "Block 3\n" - " live in: (00100000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0010000)\n" + " live out: (0000000)\n" + " kill: (0000000)\n" "Block 4\n" // loop header - " live in: (00000000000000000000000000000000)\n" - " live out: (00000100000000000000000000000000)\n" - " kill: (00000110000000000000000000000000)\n" + " live in: (0000000)\n" + " live out: (0000010)\n" + " kill: (0000011)\n" "Block 5\n" // back edge - " live in: (00000100000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0000010)\n" + " live out: (0000000)\n" + " kill: (0000000)\n" "Block 6\n" // return block - " live in: (00000100000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0000010)\n" + " live out: (0000000)\n" + " kill: (0000000)\n" "Block 7\n" // exit block - " live in: (00000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0000000)\n" + " live out: (0000000)\n" + " kill: (0000000)\n" "Block 8\n" // synthesized pre header - " live in: (00000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00001000000000000000000000000000)\n"; + " live in: (0000000)\n" + " live out: (0000000)\n" + " kill: (0000100)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, @@ -421,41 +434,41 @@ TEST(LivenessTest, Loop6) { // phi in block 8) const char* expected = "Block 0\n" - " live in: (00000000000000000000000000000000)\n" - " live out: (11100000000000000000000000000000)\n" - " kill: (11100000000000000000000000000000)\n" + " live in: (0000000)\n" + " live out: (1110000)\n" + " kill: (1110000)\n" "Block 1\n" - " live in: (11100000000000000000000000000000)\n" - " live out: (01100000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (1110000)\n" + " live out: (0110000)\n" + " kill: (0000000)\n" "Block 2\n" // loop header - " live in: (01100000000000000000000000000000)\n" - " live out: (01110000000000000000000000000000)\n" - " kill: (00011000000000000000000000000000)\n" + " live in: (0110000)\n" + " live out: (0111000)\n" + " kill: (0001100)\n" "Block 3\n" - " live in: (01100000000000000000000000000000)\n" - " live out: (01100000000000000000000000000000)\n" - " kill: (00000100000000000000000000000000)\n" + " live in: (0110000)\n" + " live out: (0110000)\n" + " kill: (0000010)\n" "Block 4\n" // original back edge - " live in: (01100000000000000000000000000000)\n" - " live out: (01100000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0110000)\n" + " live out: (0110000)\n" + " kill: (0000000)\n" "Block 5\n" // original back edge - " live in: (01100000000000000000000000000000)\n" - " live out: (01100000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0110000)\n" + " live out: (0110000)\n" + " kill: (0000000)\n" "Block 6\n" // return block - " live in: (00010000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0001000)\n" + " live out: (0000000)\n" + " kill: (0000000)\n" "Block 7\n" // exit block - " live in: (00000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0000000)\n" + " live out: (0000000)\n" + " kill: (0000000)\n" "Block 8\n" // synthesized back edge - " live in: (01100000000000000000000000000000)\n" - " live out: (01100000000000000000000000000000)\n" - " kill: (00000010000000000000000000000000)\n"; + " live in: (0110000)\n" + " live out: (0110000)\n" + " kill: (0000001)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, @@ -477,41 +490,41 @@ TEST(LivenessTest, Loop7) { // phi in block 6) const char* expected = "Block 0\n" - " live in: (00000000000000000000000000000000)\n" - " live out: (11100000000000000000000000000000)\n" - " kill: (11100000000000000000000000000000)\n" + " live in: (0000000)\n" + " live out: (1110000)\n" + " kill: (1110000)\n" "Block 1\n" - " live in: (11100000000000000000000000000000)\n" - " live out: (01100000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (1110000)\n" + " live out: (0110000)\n" + " kill: (0000000)\n" "Block 2\n" // loop header - " live in: (01100000000000000000000000000000)\n" - " live out: (01110000000000000000000000000000)\n" - " kill: (00011000000000000000000000000000)\n" + " live in: (0110000)\n" + " live out: (0111000)\n" + " kill: (0001100)\n" "Block 3\n" - " live in: (01100000000000000000000000000000)\n" - " live out: (01100000000000000000000000000000)\n" - " kill: (00000100000000000000000000000000)\n" + " live in: (0110000)\n" + " live out: (0110000)\n" + " kill: (0000010)\n" "Block 4\n" // loop exit - " live in: (00100000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0010000)\n" + " live out: (0000000)\n" + " kill: (0000000)\n" "Block 5\n" // back edge - " live in: (01100000000000000000000000000000)\n" - " live out: (01100000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0110000)\n" + " live out: (0110000)\n" + " kill: (0000000)\n" "Block 6\n" // return block - " live in: (00000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000010000000000000000000000000)\n" + " live in: (0000000)\n" + " live out: (0000000)\n" + " kill: (0000001)\n" "Block 7\n" // exit block - " live in: (00000000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n" + " live in: (0000000)\n" + " live out: (0000000)\n" + " kill: (0000000)\n" "Block 8\n" // synthesized block to avoid critical edge. - " live in: (00010000000000000000000000000000)\n" - " live out: (00000000000000000000000000000000)\n" - " kill: (00000000000000000000000000000000)\n"; + " live in: (0001000)\n" + " live out: (0000000)\n" + " kill: (0000000)\n"; const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, |