Build live-in, live-out and kill sets for each block.

This information will be used when computing live ranges of
instructions.

Change-Id: I345ee833c1ccb4a8e725c7976453f6d58d350d74

1 files changed, 515 insertions, 0 deletions

diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc
new file mode 100644
index 0000000..aa4d35e
--- /dev/null
+++ b/compiler/optimizing/liveness_test.cc
@@ -0,0 +1,515 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "builder.h"
+#include "dex_file.h"
+#include "dex_instruction.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "ssa_liveness_analysis.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+static void TestCode(const uint16_t* data, const char* expected) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraphBuilder builder(&allocator);
+  const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
+  HGraph* graph = builder.BuildGraph(*item);
+  ASSERT_NE(graph, nullptr);
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+  SsaLivenessAnalysis liveness(*graph);
+  liveness.Analyze();
+
+  std::ostringstream buffer;
+  for (HInsertionOrderIterator it(*graph); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
+    buffer << "Block " << block->GetBlockId() << std::endl;
+    BitVector* live_in = liveness.GetLiveInSet(*block);
+    live_in->Dump(buffer, "  live in: ");
+    BitVector* live_out = liveness.GetLiveOutSet(*block);
+    live_out->Dump(buffer, "  live out: ");
+    BitVector* kill = liveness.GetKillSet(*block);
+    kill->Dump(buffer, "  kill: ");
+  }
+  ASSERT_STREQ(expected, buffer.str().c_str());
+}
+
+TEST(LivenessTest, CFG1) {
+  const char* expected =
+    "Block 0\n"
+    "  live in: ()\n"
+    "  live out: ()\n"
+    "  kill: ()\n"
+    "Block 1\n"
+    "  live in: ()\n"
+    "  live out: ()\n"
+    "  kill: ()\n"
+    "Block 2\n"
+    "  live in: ()\n"
+    "  live out: ()\n"
+    "  kill: ()\n";
+
+  // Constant is not used.
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::RETURN_VOID);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, CFG2) {
+  const char* expected =
+    "Block 0\n"
+    "  live in: (0)\n"
+    "  live out: (1)\n"
+    "  kill: (1)\n"
+    "Block 1\n"
+    "  live in: (1)\n"
+    "  live out: (0)\n"
+    "  kill: (0)\n"
+    "Block 2\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,
+    Instruction::RETURN);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, CFG3) {
+  const char* expected =
+    "Block 0\n"  // entry block
+    "  live in: (000)\n"
+    "  live out: (110)\n"
+    "  kill: (110)\n"
+    "Block 1\n"  // block with add
+    "  live in: (110)\n"
+    "  live out: (001)\n"
+    "  kill: (001)\n"
+    "Block 2\n"  // block with return
+    "  live in: (001)\n"
+    "  live out: (000)\n"
+    "  kill: (000)\n"
+    "Block 3\n"  // exit block
+    "  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,
+    Instruction::CONST_4 | 4 << 12 | 1 << 8,
+    Instruction::ADD_INT_2ADDR | 1 << 12,
+    Instruction::GOTO | 0x100,
+    Instruction::RETURN);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, CFG4) {
+  // var a;
+  // if (0 == 0) {
+  //   a = 5;
+  // } else {
+  //   a = 4;
+  // }
+  // return a;
+  //
+  // Bitsets are made of:
+  // (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"
+    "Block 1\n"  // block with if
+    "  live in: (11100)\n"
+    "  live out: (01100)\n"
+    "  kill: (00010)\n"
+    "Block 2\n"  // else block
+    "  live in: (01000)\n"
+    "  live out: (00000)\n"
+    "  kill: (00000)\n"
+    "Block 3\n"  // then block
+    "  live in: (00100)\n"
+    "  live out: (00000)\n"
+    "  kill: (00000)\n"
+    "Block 4\n"  // return block
+    "  live in: (00000)\n"
+    "  live out: (00000)\n"
+    "  kill: (00001)\n"
+    "Block 5\n"  // exit block
+    "  live in: (00000)\n"
+    "  live out: (00000)\n"
+    "  kill: (00000)\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::GOTO | 0x200,
+    Instruction::CONST_4 | 5 << 12 | 0,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, CFG5) {
+  // var a = 0;
+  // if (0 == 0) {
+  // } else {
+  //   a = 4;
+  // }
+  // return a;
+  const char* expected =
+    "Block 0\n"  // entry block
+    "  live in: (0000)\n"
+    "  live out: (1100)\n"
+    "  kill: (1100)\n"
+    "Block 1\n"  // block with if
+    "  live in: (1100)\n"
+    "  live out: (0100)\n"
+    "  kill: (0010)\n"
+    "Block 2\n"  // else block
+    "  live in: (0100)\n"
+    "  live out: (0000)\n"
+    "  kill: (0000)\n"
+    "Block 3\n"  // return block
+    "  live in: (0000)\n"
+    "  live out: (0000)\n"
+    "  kill: (0001)\n"
+    "Block 4\n"  // exit block
+    "  live in: (0000)\n"
+    "  live out: (0000)\n"
+    "  kill: (0000)\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, Loop1) {
+  // Simple loop with one preheader and one back edge.
+  // var a = 0;
+  // while (a == a) {
+  //   a = 4;
+  // }
+  // return;
+  const char* expected =
+    "Block 0\n"  // entry block
+    "  live in: (0000)\n"
+    "  live out: (1100)\n"
+    "  kill: (1100)\n"
+    "Block 1\n"  // pre header
+    "  live in: (1100)\n"
+    "  live out: (0100)\n"
+    "  kill: (0000)\n"
+    "Block 2\n"  // loop header
+    "  live in: (0100)\n"
+    "  live out: (0100)\n"
+    "  kill: (0011)\n"
+    "Block 3\n"  // back edge
+    "  live in: (0100)\n"
+    "  live out: (0100)\n"
+    "  kill: (0000)\n"
+    "Block 4\n"  // return block
+    "  live in: (0000)\n"
+    "  live out: (0000)\n"
+    "  kill: (0000)\n"
+    "Block 5\n"  // exit block
+    "  live in: (0000)\n"
+    "  live out: (0000)\n"
+    "  kill: (0000)\n";
+
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::GOTO | 0xFD00,
+    Instruction::RETURN_VOID);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, Loop3) {
+  // Test that the returned value stays live in a preceding loop.
+  // var a = 0;
+  // while (a == a) {
+  //   a = 4;
+  // }
+  // return 5;
+  const char* expected =
+    "Block 0\n"
+    "  live in: (00000)\n"
+    "  live out: (11100)\n"
+    "  kill: (11100)\n"
+    "Block 1\n"
+    "  live in: (11100)\n"
+    "  live out: (01100)\n"
+    "  kill: (00000)\n"
+    "Block 2\n"  // loop header
+    "  live in: (01100)\n"
+    "  live out: (01100)\n"
+    "  kill: (00011)\n"
+    "Block 3\n"  // back edge
+    "  live in: (01100)\n"
+    "  live out: (01100)\n"
+    "  kill: (00000)\n"
+    "Block 4\n"  // return block
+    "  live in: (00100)\n"
+    "  live out: (00000)\n"
+    "  kill: (00000)\n"
+    "Block 5\n"  // exit block
+    "  live in: (00000)\n"
+    "  live out: (00000)\n"
+    "  kill: (00000)\n";
+
+  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::GOTO | 0xFD00,
+    Instruction::CONST_4 | 5 << 12 | 1 << 8,
+    Instruction::RETURN | 1 << 8);
+
+  TestCode(data, expected);
+}
+
+
+TEST(LivenessTest, Loop4) {
+  // Make sure we support a preheader of a loop not being the first predecessor
+  // in the predecessor list of the header.
+  // var a = 0;
+  // while (a == a) {
+  //   a = 4;
+  // }
+  // return a;
+  // Bitsets are made of:
+  // (constant0, constant4, phi, equal test)
+  const char* expected =
+    "Block 0\n"
+    "  live in: (0000)\n"
+    "  live out: (1100)\n"
+    "  kill: (1100)\n"
+    "Block 1\n"
+    "  live in: (1100)\n"
+    "  live out: (1100)\n"
+    "  kill: (0000)\n"
+    "Block 2\n"  // loop header
+    "  live in: (0100)\n"
+    "  live out: (0110)\n"
+    "  kill: (0011)\n"
+    "Block 3\n"  // back edge
+    "  live in: (0100)\n"
+    "  live out: (0100)\n"
+    "  kill: (0000)\n"
+    "Block 4\n"  // pre loop header
+    "  live in: (1100)\n"
+    "  live out: (0100)\n"
+    "  kill: (0000)\n"
+    "Block 5\n"  // return block
+    "  live in: (0010)\n"
+    "  live out: (0000)\n"
+    "  kill: (0000)\n"
+    "Block 6\n"  // exit block
+    "  live in: (0000)\n"
+    "  live out: (0000)\n"
+    "  kill: (0000)\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::GOTO | 0x500,
+    Instruction::IF_EQ, 5,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::GOTO | 0xFD00,
+    Instruction::GOTO | 0xFC00,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, Loop5) {
+  // Make sure we create a preheader of a loop when a header originally has two
+  // incoming blocks and one back edge.
+  // Bitsets are made of:
+  // (constant0, constant4, constant5, equal in block 1, phi in block 8, phi in block 4,
+  //  equal in block 4)
+  const char* expected =
+    "Block 0\n"
+    "  live in: (0000000)\n"
+    "  live out: (1110000)\n"
+    "  kill: (1110000)\n"
+    "Block 1\n"
+    "  live in: (1110000)\n"
+    "  live out: (0110000)\n"
+    "  kill: (0001000)\n"
+    "Block 2\n"
+    "  live in: (0100000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n"
+    "Block 3\n"
+    "  live in: (0010000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n"
+    "Block 4\n"  // loop header
+    "  live in: (0000000)\n"
+    "  live out: (0000010)\n"
+    "  kill: (0000011)\n"
+    "Block 5\n"  // back edge
+    "  live in: (0000010)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n"
+    "Block 6\n"  // return block
+    "  live in: (0000010)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n"
+    "Block 7\n"  // exit block
+    "  live in: (0000000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n"
+    "Block 8\n"  // synthesized pre header
+    "  live in: (0000000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000100)\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::GOTO | 0x200,
+    Instruction::CONST_4 | 5 << 12 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0xFE00,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+TEST(LivenessTest, Loop6) {
+  // Bitsets are made of:
+  // (constant0, constant4, constant5, phi in block 2, equal in block 2, equal in block 3)
+  const char* expected =
+    "Block 0\n"
+    "  live in: (000000)\n"
+    "  live out: (111000)\n"
+    "  kill: (111000)\n"
+    "Block 1\n"
+    "  live in: (111000)\n"
+    "  live out: (011000)\n"
+    "  kill: (000000)\n"
+    "Block 2\n"  // loop header
+    "  live in: (011000)\n"
+    "  live out: (011100)\n"
+    "  kill: (000110)\n"
+    "Block 3\n"
+    "  live in: (011000)\n"
+    "  live out: (011000)\n"
+    "  kill: (000001)\n"
+    "Block 4\n"  // back edge
+    "  live in: (011000)\n"
+    "  live out: (011000)\n"
+    "  kill: (000000)\n"
+    "Block 5\n"  // back edge
+    "  live in: (011000)\n"
+    "  live out: (011000)\n"
+    "  kill: (000000)\n"
+    "Block 6\n"  // return block
+    "  live in: (000100)\n"
+    "  live out: (000000)\n"
+    "  kill: (000000)\n"
+    "Block 7\n"  // exit block
+    "  live in: (000000)\n"
+    "  live out: (000000)\n"
+    "  kill: (000000)\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 8,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 5 << 12 | 0,
+    Instruction::GOTO | 0xFA00,
+    Instruction::GOTO | 0xF900,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+
+TEST(LivenessTest, Loop7) {
+  // Bitsets are made of:
+  // (constant0, constant4, constant5, phi in block 2, equal in block 2, equal in block 3,
+  //  phi in block 6)
+  const char* expected =
+    "Block 0\n"
+    "  live in: (0000000)\n"
+    "  live out: (1110000)\n"
+    "  kill: (1110000)\n"
+    "Block 1\n"
+    "  live in: (1110000)\n"
+    "  live out: (0110000)\n"
+    "  kill: (0000000)\n"
+    "Block 2\n"  // loop header
+    "  live in: (0110000)\n"
+    "  live out: (0110000)\n"
+    "  kill: (0001100)\n"
+    "Block 3\n"
+    "  live in: (0110000)\n"
+    "  live out: (0110000)\n"
+    "  kill: (0000010)\n"
+    "Block 4\n"  // loop exit
+    "  live in: (0010000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n"
+    "Block 5\n"  // back edge
+    "  live in: (0110000)\n"
+    "  live out: (0110000)\n"
+    "  kill: (0000000)\n"
+    "Block 6\n"  // return block
+    "  live in: (0000000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000001)\n"
+    "Block 7\n"  // exit block
+    "  live in: (0000000)\n"
+    "  live out: (0000000)\n"
+    "  kill: (0000000)\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 8,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 5 << 12 | 0,
+    Instruction::GOTO | 0x0200,
+    Instruction::GOTO | 0xF900,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+}  // namespace art