compiler/optimizing/ssa_test.cc - platform/art - Git at Google

 /*
  * 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/arena_allocator.h"
 #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 "gtest/gtest.h"

 namespace art {

 class SsaPrettyPrinter : public HPrettyPrinter {
  public:
   explicit SsaPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") {}

   void PrintInt(int value) OVERRIDE {
     str_ += StringPrintf("%d", value);
   }

   void PrintString(const char* value) OVERRIDE {
     str_ += value;
   }

   void PrintNewLine() OVERRIDE {
     str_ += '\n';
   }

   void Clear() { str_.clear(); }

   std::string str() const { return str_; }

   void VisitIntConstant(HIntConstant* constant) OVERRIDE {
     PrintPreInstruction(constant);
     str_ += constant->DebugName();
     str_ += " ";
     PrintInt(constant->GetValue());
     PrintPostInstruction(constant);
   }

  private:
   std::string str_;

   DISALLOW_COPY_AND_ASSIGN(SsaPrettyPrinter);
 };

 static void ReNumberInstructions(HGraph* graph) {
   int id = 0;
   for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++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);
   HGraph* graph = new (&allocator) HGraph(&allocator);
   HGraphBuilder builder(graph);
   const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
   bool graph_built = builder.BuildGraph(*item);
   ASSERT_TRUE(graph_built);

   graph->BuildDominatorTree();
   // Suspend checks implementation may change in the future, and this test relies
   // on how instructions are ordered.
   RemoveSuspendChecks(graph);
   graph->TransformToSsa();
   ReNumberInstructions(graph);

   // Test that phis had their type set.
   for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
     for (HInstructionIterator it(graph->GetBlocks().Get(i)->GetPhis()); !it.Done(); it.Advance()) {
       ASSERT_NE(it.Current()->GetType(), Primitive::kPrimVoid);
     }
   }

   SsaPrettyPrinter 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: 5, 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: 2, 5, succ: 4\n"
     "  5: ReturnVoid\n"
     "BasicBlock 4, pred: 3\n"
     "  6: Exit\n"
     // Synthesized block to avoid critical edge.
     "BasicBlock 5, pred: 1, succ: 3\n"
     "  7: Goto\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: 5, 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: 2, 5, succ: 4\n"
     "  6: Phi(1, 0) [7]\n"
     "  7: Return(6)\n"
     "BasicBlock 4, pred: 3\n"
     "  8: Exit\n"
     // Synthesized block to avoid critical edge.
     "BasicBlock 5, pred: 1, succ: 3\n"
     "  9: Goto\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 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, 3, 3]\n"
     "  1: IntConstant 4 [6]\n"
     "  2: Goto\n"
     "BasicBlock 1, pred: 0, succ: 4, 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: 2, 4, succ: 5\n"
     "  6: Phi(1, 0) [9]\n"
     "  7: Goto\n"
     "BasicBlock 4, pred: 1, succ: 3\n"
     "  8: Goto\n"
     "BasicBlock 5, pred: 3, succ: 6\n"
     "  9: Return(6)\n"
     "BasicBlock 6, pred: 5\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::GOTO | 0xFF00,
     Instruction::RETURN | 0 << 8);

   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: 4, 3, succ: 5, 3\n"
     "  4: Phi(0, 1) [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: 8, 5, succ: 6, 5\n"
     "  8: Phi(14, 8) [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 [14, 8, 8]\n"
     "  2: IntConstant 5 [14]\n"
     "  3: Goto\n"
     "BasicBlock 1, pred: 0, succ: 2\n"
     "  4: Goto\n"
     "BasicBlock 2, pred: 1, 8, succ: 6, 3\n"
     "  5: Phi(0, 14) [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: 8\n"
     "  10: Goto\n"
     "BasicBlock 5, pred: 3, succ: 8\n"
     "  11: Goto\n"
     "BasicBlock 6, pred: 2, succ: 7\n"
     "  12: Return(5)\n"
     "BasicBlock 7, pred: 6\n"
     "  13: Exit\n"
     // Synthesized single back edge of loop.
     "BasicBlock 8, pred: 5, 4, succ: 2\n"
     "  14: Phi(1, 2) [5]\n"
     "  15: Goto\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: 8, 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: 4, 8, succ: 7\n"
     "  12: Phi(2, 5) [13]\n"
     "  13: Return(12)\n"
     "BasicBlock 7, pred: 6\n"
     "  14: Exit\n"
     "BasicBlock 8, pred: 2, succ: 6\n"
     "  15: Goto\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);
 }

 TEST(SsaTest, LocalInIf) {
   // Test that we do not create a phi in the join block when one predecessor
   // does not update the local.
   const char* expected =
     "BasicBlock 0, succ: 1\n"
     "  0: IntConstant 0 [3, 3]\n"
     "  1: IntConstant 4\n"
     "  2: Goto\n"
     "BasicBlock 1, pred: 0, succ: 5, 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: 2, 5, succ: 4\n"
     "  6: ReturnVoid\n"
     "BasicBlock 4, pred: 3\n"
     "  7: Exit\n"
     // Synthesized block to avoid critical edge.
     "BasicBlock 5, pred: 1, succ: 3\n"
     "  8: Goto\n";

   const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
     Instruction::IF_EQ, 3,
     Instruction::CONST_4 | 4 << 12 | 1 << 8,
     Instruction::RETURN_VOID);

   TestCode(data, expected);
 }

 TEST(SsaTest, MultiplePredecessors) {
   // Test that we do not create a phi when one predecessor
   // does not update the local.
   const char* expected =
     "BasicBlock 0, succ: 1\n"
     "  0: IntConstant 0 [4, 8, 6, 6, 2, 2, 8, 4]\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: 5\n"
     "  4: Add(0, 0)\n"
     "  5: Goto\n"
     "BasicBlock 3, pred: 1, succ: 7, 4\n"
     "  6: Equal(0, 0) [7]\n"
     "  7: If(6)\n"
     "BasicBlock 4, pred: 3, succ: 5\n"
     "  8: Add(0, 0)\n"
     "  9: Goto\n"
     // This block should not get a phi for local 1.
     "BasicBlock 5, pred: 2, 4, 7, succ: 6\n"
     "  10: ReturnVoid\n"
     "BasicBlock 6, pred: 5\n"
     "  11: Exit\n"
     "BasicBlock 7, pred: 3, succ: 5\n"
     "  12: Goto\n";

   const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
     Instruction::IF_EQ, 5,
     Instruction::ADD_INT_LIT8 | 1 << 8, 0 << 8,
     Instruction::GOTO | 0x0500,
     Instruction::IF_EQ, 4,
     Instruction::ADD_INT_LIT8 | 1 << 8, 0 << 8,
     Instruction::RETURN_VOID);

   TestCode(data, expected);
 }

 }  // namespace art
	/*
	* 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/arena_allocator.h"
	#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 "gtest/gtest.h"

	namespace art {

	class SsaPrettyPrinter : public HPrettyPrinter {
	public:
	explicit SsaPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") {}

	void PrintInt(int value) OVERRIDE {
	str_ += StringPrintf("%d", value);
	}

	void PrintString(const char* value) OVERRIDE {
	str_ += value;
	}

	void PrintNewLine() OVERRIDE {
	str_ += '\n';
	}

	void Clear() { str_.clear(); }

	std::string str() const { return str_; }

	void VisitIntConstant(HIntConstant* constant) OVERRIDE {
	PrintPreInstruction(constant);
	str_ += constant->DebugName();
	str_ += " ";
	PrintInt(constant->GetValue());
	PrintPostInstruction(constant);
	}

	private:
	std::string str_;

	DISALLOW_COPY_AND_ASSIGN(SsaPrettyPrinter);
	};

	static void ReNumberInstructions(HGraph* graph) {
	int id = 0;
	for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++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);
	HGraph* graph = new (&allocator) HGraph(&allocator);
	HGraphBuilder builder(graph);
	const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
	bool graph_built = builder.BuildGraph(*item);
	ASSERT_TRUE(graph_built);

	graph->BuildDominatorTree();
	// Suspend checks implementation may change in the future, and this test relies
	// on how instructions are ordered.
	RemoveSuspendChecks(graph);
	graph->TransformToSsa();
	ReNumberInstructions(graph);

	// Test that phis had their type set.
	for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
	for (HInstructionIterator it(graph->GetBlocks().Get(i)->GetPhis()); !it.Done(); it.Advance()) {
	ASSERT_NE(it.Current()->GetType(), Primitive::kPrimVoid);
	}
	}

	SsaPrettyPrinter 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: 5, 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: 2, 5, succ: 4\n"
	" 5: ReturnVoid\n"
	"BasicBlock 4, pred: 3\n"
	" 6: Exit\n"
	// Synthesized block to avoid critical edge.
	"BasicBlock 5, pred: 1, succ: 3\n"
	" 7: Goto\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: 5, 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: 2, 5, succ: 4\n"
	" 6: Phi(1, 0) [7]\n"
	" 7: Return(6)\n"
	"BasicBlock 4, pred: 3\n"
	" 8: Exit\n"
	// Synthesized block to avoid critical edge.
	"BasicBlock 5, pred: 1, succ: 3\n"
	" 9: Goto\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 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, 3, 3]\n"
	" 1: IntConstant 4 [6]\n"
	" 2: Goto\n"
	"BasicBlock 1, pred: 0, succ: 4, 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: 2, 4, succ: 5\n"
	" 6: Phi(1, 0) [9]\n"
	" 7: Goto\n"
	"BasicBlock 4, pred: 1, succ: 3\n"
	" 8: Goto\n"
	"BasicBlock 5, pred: 3, succ: 6\n"
	" 9: Return(6)\n"
	"BasicBlock 6, pred: 5\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::GOTO \| 0xFF00,
	Instruction::RETURN \| 0 << 8);

	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: 4, 3, succ: 5, 3\n"
	" 4: Phi(0, 1) [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: 8, 5, succ: 6, 5\n"
	" 8: Phi(14, 8) [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 [14, 8, 8]\n"
	" 2: IntConstant 5 [14]\n"
	" 3: Goto\n"
	"BasicBlock 1, pred: 0, succ: 2\n"
	" 4: Goto\n"
	"BasicBlock 2, pred: 1, 8, succ: 6, 3\n"
	" 5: Phi(0, 14) [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: 8\n"
	" 10: Goto\n"
	"BasicBlock 5, pred: 3, succ: 8\n"
	" 11: Goto\n"
	"BasicBlock 6, pred: 2, succ: 7\n"
	" 12: Return(5)\n"
	"BasicBlock 7, pred: 6\n"
	" 13: Exit\n"
	// Synthesized single back edge of loop.
	"BasicBlock 8, pred: 5, 4, succ: 2\n"
	" 14: Phi(1, 2) [5]\n"
	" 15: Goto\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: 8, 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: 4, 8, succ: 7\n"
	" 12: Phi(2, 5) [13]\n"
	" 13: Return(12)\n"
	"BasicBlock 7, pred: 6\n"
	" 14: Exit\n"
	"BasicBlock 8, pred: 2, succ: 6\n"
	" 15: Goto\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);
	}

	TEST(SsaTest, LocalInIf) {
	// Test that we do not create a phi in the join block when one predecessor
	// does not update the local.
	const char* expected =
	"BasicBlock 0, succ: 1\n"
	" 0: IntConstant 0 [3, 3]\n"
	" 1: IntConstant 4\n"
	" 2: Goto\n"
	"BasicBlock 1, pred: 0, succ: 5, 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: 2, 5, succ: 4\n"
	" 6: ReturnVoid\n"
	"BasicBlock 4, pred: 3\n"
	" 7: Exit\n"
	// Synthesized block to avoid critical edge.
	"BasicBlock 5, pred: 1, succ: 3\n"
	" 8: Goto\n";

	const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
	Instruction::CONST_4 \| 0 \| 0,
	Instruction::IF_EQ, 3,
	Instruction::CONST_4 \| 4 << 12 \| 1 << 8,
	Instruction::RETURN_VOID);

	TestCode(data, expected);
	}

	TEST(SsaTest, MultiplePredecessors) {
	// Test that we do not create a phi when one predecessor
	// does not update the local.
	const char* expected =
	"BasicBlock 0, succ: 1\n"
	" 0: IntConstant 0 [4, 8, 6, 6, 2, 2, 8, 4]\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: 5\n"
	" 4: Add(0, 0)\n"
	" 5: Goto\n"
	"BasicBlock 3, pred: 1, succ: 7, 4\n"
	" 6: Equal(0, 0) [7]\n"
	" 7: If(6)\n"
	"BasicBlock 4, pred: 3, succ: 5\n"
	" 8: Add(0, 0)\n"
	" 9: Goto\n"
	// This block should not get a phi for local 1.
	"BasicBlock 5, pred: 2, 4, 7, succ: 6\n"
	" 10: ReturnVoid\n"
	"BasicBlock 6, pred: 5\n"
	" 11: Exit\n"
	"BasicBlock 7, pred: 3, succ: 5\n"
	" 12: Goto\n";

	const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
	Instruction::CONST_4 \| 0 \| 0,
	Instruction::IF_EQ, 5,
	Instruction::ADD_INT_LIT8 \| 1 << 8, 0 << 8,
	Instruction::GOTO \| 0x0500,
	Instruction::IF_EQ, 4,
	Instruction::ADD_INT_LIT8 \| 1 << 8, 0 << 8,
	Instruction::RETURN_VOID);

	TestCode(data, expected);
	}

	} // namespace art