Add a Transform to SSA phase to the optimizing compiler.

Change-Id: Ia9700756a0396d797a00b529896487d52c989329

1 files changed, 444 insertions, 0 deletions

diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc
new file mode 100644
index 0000000..7c3633b
--- /dev/null
+++ b/compiler/optimizing/ssa_test.cc
@@ -0,0 +1,444 @@
+/*
+ * 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 "base/stringprintf.h"
+#include "builder.h"
+#include "dex_file.h"
+#include "dex_instruction.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "pretty_printer.h"
+#include "ssa_builder.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+class StringPrettyPrinter : public HPrettyPrinter {
+ public:
+  explicit StringPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") {}
+
+  virtual void PrintInt(int value) {
+    str_ += StringPrintf("%d", value);
+  }
+
+  virtual void PrintString(const char* value) {
+    str_ += value;
+  }
+
+  virtual void PrintNewLine() {
+    str_ += '\n';
+  }
+
+  void Clear() { str_.clear(); }
+
+  std::string str() const { return str_; }
+
+  virtual void VisitIntConstant(HIntConstant* constant) {
+    PrintPreInstruction(constant);
+    str_ += constant->DebugName();
+    str_ += " ";
+    PrintInt(constant->GetValue());
+    PrintPostInstruction(constant);
+  }
+
+ private:
+  std::string str_;
+
+  DISALLOW_COPY_AND_ASSIGN(StringPrettyPrinter);
+};
+
+static void ReNumberInstructions(HGraph* graph) {
+  int id = 0;
+  for (size_t i = 0; i < graph->GetBlocks()->Size(); i++) {
+    HBasicBlock* block = graph->GetBlocks()->Get(i);
+    for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
+      it.Current()->SetId(id++);
+    }
+    for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
+      it.Current()->SetId(id++);
+    }
+  }
+}
+
+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();
+  ReNumberInstructions(graph);
+
+  StringPrettyPrinter printer(graph);
+  printer.VisitInsertionOrder();
+
+  ASSERT_STREQ(expected, printer.str().c_str());
+}
+
+TEST(SsaTest, CFG1) {
+  // Test that we get rid of loads and stores.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [2, 2]\n"
+    "  1: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "  2: Equal(0, 0) [3]\n"
+    "  3: If(2)\n"
+    "BasicBlock 2, pred: 1, succ: 3\n"
+    "  4: Goto\n"
+    "BasicBlock 3, pred: 1, 2, succ: 4\n"
+    "  5: ReturnVoid\n"
+    "BasicBlock 4, pred: 3\n"
+    "  6: Exit\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0x100,
+    Instruction::RETURN_VOID);
+
+  TestCode(data, expected);
+}
+
+TEST(SsaTest, CFG2) {
+  // Test that we create a phi for the join block of an if control flow instruction
+  // when there is only code in the else branch.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [6, 3, 3]\n"
+    "  1: IntConstant 4 [6]\n"
+    "  2: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "  3: Equal(0, 0) [4]\n"
+    "  4: If(3)\n"
+    "BasicBlock 2, pred: 1, succ: 3\n"
+    "  5: Goto\n"
+    "BasicBlock 3, pred: 1, 2, succ: 4\n"
+    "  6: Phi(0, 1) [7]\n"
+    "  7: Return(6)\n"
+    "BasicBlock 4, pred: 3\n"
+    "  8: Exit\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(SsaTest, CFG3) {
+  // Test that we create a phi for the join block of an if control flow instruction
+  // when there both branches update a local.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [4, 4]\n"
+    "  1: IntConstant 4 [8]\n"
+    "  2: IntConstant 5 [8]\n"
+    "  3: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "  4: Equal(0, 0) [5]\n"
+    "  5: If(4)\n"
+    "BasicBlock 2, pred: 1, succ: 4\n"
+    "  6: Goto\n"
+    "BasicBlock 3, pred: 1, succ: 4\n"
+    "  7: Goto\n"
+    "BasicBlock 4, pred: 2, 3, succ: 5\n"
+    "  8: Phi(1, 2) [9]\n"
+    "  9: Return(8)\n"
+    "BasicBlock 5, pred: 4\n"
+    "  10: Exit\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(SsaTest, Loop1) {
+  // Test that we create a phi for an initialized local at entry of a loop.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [6, 4, 2, 2]\n"
+    "  1: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "  2: Equal(0, 0) [3]\n"
+    "  3: If(2)\n"
+    "BasicBlock 2, pred: 1, 3, succ: 3\n"
+    "  4: Phi(0, 6) [6]\n"
+    "  5: Goto\n"
+    "BasicBlock 3, pred: 1, 2, succ: 2\n"
+    "  6: Phi(0, 4) [4]\n"
+    "  7: Goto\n"
+    "BasicBlock 4\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0x100,
+    Instruction::GOTO | 0xFF00);
+
+  TestCode(data, expected);
+}
+
+TEST(SsaTest, Loop2) {
+  // Simple loop with one preheader and one back edge.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [4]\n"
+    "  1: IntConstant 4 [4]\n"
+    "  2: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 2\n"
+    "  3: Goto\n"
+    "BasicBlock 2, pred: 1, 3, succ: 4, 3\n"
+    "  4: Phi(0, 1) [5, 5]\n"
+    "  5: Equal(4, 4) [6]\n"
+    "  6: If(5)\n"
+    "BasicBlock 3, pred: 2, succ: 2\n"
+    "  7: Goto\n"
+    "BasicBlock 4, pred: 2, succ: 5\n"
+    "  8: ReturnVoid\n"
+    "BasicBlock 5, pred: 4\n"
+    "  9: Exit\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(SsaTest, Loop3) {
+  // Test that a local not yet defined at the entry of a loop is handled properly.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [5]\n"
+    "  1: IntConstant 4 [5]\n"
+    "  2: IntConstant 5 [9]\n"
+    "  3: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 2\n"
+    "  4: Goto\n"
+    "BasicBlock 2, pred: 1, 3, succ: 4, 3\n"
+    "  5: Phi(0, 1) [6, 6]\n"
+    "  6: Equal(5, 5) [7]\n"
+    "  7: If(6)\n"
+    "BasicBlock 3, pred: 2, succ: 2\n"
+    "  8: Goto\n"
+    "BasicBlock 4, pred: 2, succ: 5\n"
+    "  9: Return(2)\n"
+    "BasicBlock 5, pred: 4\n"
+    "  10: Exit\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(SsaTest, Loop4) {
+  // Make sure we support a preheader of a loop not being the first predecessor
+  // in the predecessor list of the header.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [4]\n"
+    "  1: IntConstant 4 [4]\n"
+    "  2: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 4\n"
+    "  3: Goto\n"
+    "BasicBlock 2, pred: 3, 4, succ: 5, 3\n"
+    "  4: Phi(1, 0) [9, 5, 5]\n"
+    "  5: Equal(4, 4) [6]\n"
+    "  6: If(5)\n"
+    "BasicBlock 3, pred: 2, succ: 2\n"
+    "  7: Goto\n"
+    "BasicBlock 4, pred: 1, succ: 2\n"
+    "  8: Goto\n"
+    "BasicBlock 5, pred: 2, succ: 6\n"
+    "  9: Return(4)\n"
+    "BasicBlock 6, pred: 5\n"
+    "  10: Exit\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(SsaTest, Loop5) {
+  // Make sure we create a preheader of a loop when a header originally has two
+  // incoming blocks and one back edge.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [4, 4]\n"
+    "  1: IntConstant 4 [14]\n"
+    "  2: IntConstant 5 [14]\n"
+    "  3: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "  4: Equal(0, 0) [5]\n"
+    "  5: If(4)\n"
+    "BasicBlock 2, pred: 1, succ: 8\n"
+    "  6: Goto\n"
+    "BasicBlock 3, pred: 1, succ: 8\n"
+    "  7: Goto\n"
+    "BasicBlock 4, pred: 5, 8, succ: 6, 5\n"
+    "  8: Phi(8, 14) [8, 12, 9, 9]\n"
+    "  9: Equal(8, 8) [10]\n"
+    "  10: If(9)\n"
+    "BasicBlock 5, pred: 4, succ: 4\n"
+    "  11: Goto\n"
+    "BasicBlock 6, pred: 4, succ: 7\n"
+    "  12: Return(8)\n"
+    "BasicBlock 7, pred: 6\n"
+    "  13: Exit\n"
+    "BasicBlock 8, pred: 2, 3, succ: 4\n"
+    "  14: Phi(1, 2) [8]\n"
+    "  15: Goto\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(SsaTest, Loop6) {
+  // Test a loop with one preheader and two back edges (e.g. continue).
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [5]\n"
+    "  1: IntConstant 4 [5, 8, 8]\n"
+    "  2: IntConstant 5 [5]\n"
+    "  3: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 2\n"
+    "  4: Goto\n"
+    "BasicBlock 2, pred: 1, 4, 5, succ: 6, 3\n"
+    "  5: Phi(0, 2, 1) [12, 6, 6]\n"
+    "  6: Equal(5, 5) [7]\n"
+    "  7: If(6)\n"
+    "BasicBlock 3, pred: 2, succ: 5, 4\n"
+    "  8: Equal(1, 1) [9]\n"
+    "  9: If(8)\n"
+    "BasicBlock 4, pred: 3, succ: 2\n"
+    "  10: Goto\n"
+    "BasicBlock 5, pred: 3, succ: 2\n"
+    "  11: Goto\n"
+    "BasicBlock 6, pred: 2, succ: 7\n"
+    "  12: Return(5)\n"
+    "BasicBlock 7, pred: 6\n"
+    "  13: Exit\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(SsaTest, Loop7) {
+  // Test a loop with one preheader, one back edge, and two exit edges (e.g. break).
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [5]\n"
+    "  1: IntConstant 4 [5, 8, 8]\n"
+    "  2: IntConstant 5 [12]\n"
+    "  3: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 2\n"
+    "  4: Goto\n"
+    "BasicBlock 2, pred: 1, 5, succ: 6, 3\n"
+    "  5: Phi(0, 1) [12, 6, 6]\n"
+    "  6: Equal(5, 5) [7]\n"
+    "  7: If(6)\n"
+    "BasicBlock 3, pred: 2, succ: 5, 4\n"
+    "  8: Equal(1, 1) [9]\n"
+    "  9: If(8)\n"
+    "BasicBlock 4, pred: 3, succ: 6\n"
+    "  10: Goto\n"
+    "BasicBlock 5, pred: 3, succ: 2\n"
+    "  11: Goto\n"
+    "BasicBlock 6, pred: 2, 4, succ: 7\n"
+    "  12: Phi(5, 2) [13]\n"
+    "  13: Return(12)\n"
+    "BasicBlock 7, pred: 6\n"
+    "  14: Exit\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);
+}
+
+TEST(SsaTest, DeadLocal) {
+  // Test that we correctly handle a local not being used.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0\n"
+    "  1: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 2\n"
+    "  2: ReturnVoid\n"
+    "BasicBlock 2, pred: 1\n"
+    "  3: Exit\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::RETURN_VOID);
+
+  TestCode(data, expected);
+}
+
+}  // namespace art