compiler/optimizing/find_loops_test.cc - platform/art - Gitiles

 /*
  * 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 "builder.h"
 #include "dex_file.h"
 #include "dex_instruction.h"
 #include "nodes.h"
 #include "optimizing_unit_test.h"
 #include "ssa_liveness_analysis.h"
 #include "pretty_printer.h"

 #include "gtest/gtest.h"

 namespace art {

 static HGraph* TestCode(const uint16_t* data, ArenaAllocator* allocator) {
   HGraph* graph = CreateGraph(allocator);
   HGraphBuilder builder(graph);
   const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
   builder.BuildGraph(*item);
   graph->BuildDominatorTree();
   graph->AnalyzeNaturalLoops();
   return graph;
 }

 TEST(FindLoopsTest, CFG1) {
   // Constant is not used.
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
     Instruction::RETURN_VOID);

   ArenaPool arena;
   ArenaAllocator allocator(&arena);
   HGraph* graph = TestCode(data, &allocator);
   for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
     ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
   }
 }

 TEST(FindLoopsTest, CFG2) {
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
     Instruction::RETURN);

   ArenaPool arena;
   ArenaAllocator allocator(&arena);
   HGraph* graph = TestCode(data, &allocator);
   for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
     ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
   }
 }

 TEST(FindLoopsTest, CFG3) {
   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);

   ArenaPool arena;
   ArenaAllocator allocator(&arena);
   HGraph* graph = TestCode(data, &allocator);
   for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
     ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
   }
 }

 TEST(FindLoopsTest, CFG4) {
   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);

   ArenaPool arena;
   ArenaAllocator allocator(&arena);
   HGraph* graph = TestCode(data, &allocator);
   for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
     ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
   }
 }

 TEST(FindLoopsTest, CFG5) {
   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);

   ArenaPool arena;
   ArenaAllocator allocator(&arena);
   HGraph* graph = TestCode(data, &allocator);
   for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
     ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
   }
 }

 static void TestBlock(HGraph* graph,
                       int block_id,
                       bool is_loop_header,
                       int parent_loop_header_id,
                       const int* blocks_in_loop = nullptr,
                       size_t number_of_blocks = 0) {
   HBasicBlock* block = graph->GetBlocks().Get(block_id);
   ASSERT_EQ(block->IsLoopHeader(), is_loop_header);
   if (parent_loop_header_id == -1) {
     ASSERT_EQ(block->GetLoopInformation(), nullptr);
   } else {
     ASSERT_EQ(block->GetLoopInformation()->GetHeader()->GetBlockId(), parent_loop_header_id);
   }

   if (blocks_in_loop != nullptr) {
     HLoopInformation* info = block->GetLoopInformation();
     const BitVector& blocks = info->GetBlocks();
     ASSERT_EQ(blocks.NumSetBits(), number_of_blocks);
     for (size_t i = 0; i < number_of_blocks; ++i) {
       ASSERT_TRUE(blocks.IsBitSet(blocks_in_loop[i]));
     }
   } else {
     ASSERT_FALSE(block->IsLoopHeader());
   }
 }

 TEST(FindLoopsTest, Loop1) {
   // Simple loop with one preheader and one back edge.
   // var a = 0;
   // while (a == a) {
   // }
   // return;
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
     Instruction::IF_EQ, 3,
     Instruction::GOTO | 0xFE00,
     Instruction::RETURN_VOID);

   ArenaPool arena;
   ArenaAllocator allocator(&arena);
   HGraph* graph = TestCode(data, &allocator);

   TestBlock(graph, 0, false, -1);            // entry block
   TestBlock(graph, 1, false, -1);            // pre header
   const int blocks2[] = {2, 3};
   TestBlock(graph, 2, true, 2, blocks2, 2);  // loop header
   TestBlock(graph, 3, false, 2);             // block in loop
   TestBlock(graph, 4, false, -1);            // return block
   TestBlock(graph, 5, false, -1);            // exit block
 }

 TEST(FindLoopsTest, Loop2) {
   // 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) {
   // }
   // return a;
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
     Instruction::GOTO | 0x400,
     Instruction::IF_EQ, 4,
     Instruction::GOTO | 0xFE00,
     Instruction::GOTO | 0xFD00,
     Instruction::RETURN | 0 << 8);

   ArenaPool arena;
   ArenaAllocator allocator(&arena);
   HGraph* graph = TestCode(data, &allocator);

   TestBlock(graph, 0, false, -1);            // entry block
   TestBlock(graph, 1, false, -1);            // goto block
   const int blocks2[] = {2, 3};
   TestBlock(graph, 2, true, 2, blocks2, 2);  // loop header
   TestBlock(graph, 3, false, 2);             // block in loop
   TestBlock(graph, 4, false, -1);            // pre header
   TestBlock(graph, 5, false, -1);            // return block
   TestBlock(graph, 6, false, -1);            // exit block
 }

 TEST(FindLoopsTest, Loop3) {
   // Make sure we create a preheader of a loop when a header originally has two
   // incoming blocks and one back edge.
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
     Instruction::IF_EQ, 3,
     Instruction::GOTO | 0x100,
     Instruction::IF_EQ, 3,
     Instruction::GOTO | 0xFE00,
     Instruction::RETURN | 0 << 8);

   ArenaPool arena;
   ArenaAllocator allocator(&arena);
   HGraph* graph = TestCode(data, &allocator);

   TestBlock(graph, 0, false, -1);            // entry block
   TestBlock(graph, 1, false, -1);            // goto block
   TestBlock(graph, 2, false, -1);
   const int blocks2[] = {3, 4};
   TestBlock(graph, 3, true, 3, blocks2, 2);  // loop header
   TestBlock(graph, 4, false, 3);             // block in loop
   TestBlock(graph, 5, false, -1);            // pre header
   TestBlock(graph, 6, false, -1);            // return block
   TestBlock(graph, 7, false, -1);            // exit block
   TestBlock(graph, 8, false, -1);            // synthesized pre header
 }

 TEST(FindLoopsTest, Loop4) {
   // Test loop with originally two back edges.
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
     Instruction::IF_EQ, 6,
     Instruction::IF_EQ, 3,
     Instruction::GOTO | 0xFC00,
     Instruction::GOTO | 0xFB00,
     Instruction::RETURN | 0 << 8);

   ArenaPool arena;
   ArenaAllocator allocator(&arena);
   HGraph* graph = TestCode(data, &allocator);

   TestBlock(graph, 0, false, -1);            // entry block
   TestBlock(graph, 1, false, -1);            // pre header
   const int blocks2[] = {2, 3, 4, 5};
   TestBlock(graph, 2, true, 2, blocks2, arraysize(blocks2));  // loop header
   TestBlock(graph, 3, false, 2);             // block in loop
   TestBlock(graph, 4, false, 2);             // back edge
   TestBlock(graph, 5, false, 2);             // back edge
   TestBlock(graph, 6, false, -1);            // return block
   TestBlock(graph, 7, false, -1);            // exit block
 }


 TEST(FindLoopsTest, Loop5) {
   // Test loop with two exit edges.
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
     Instruction::IF_EQ, 6,
     Instruction::IF_EQ, 3,
     Instruction::GOTO | 0x0200,
     Instruction::GOTO | 0xFB00,
     Instruction::RETURN | 0 << 8);

   ArenaPool arena;
   ArenaAllocator allocator(&arena);
   HGraph* graph = TestCode(data, &allocator);

   TestBlock(graph, 0, false, -1);            // entry block
   TestBlock(graph, 1, false, -1);            // pre header
   const int blocks2[] = {2, 3, 5};
   TestBlock(graph, 2, true, 2, blocks2, 3);  // loop header
   TestBlock(graph, 3, false, 2);             // block in loop
   TestBlock(graph, 4, false, -1);            // loop exit
   TestBlock(graph, 5, false, 2);             // back edge
   TestBlock(graph, 6, false, -1);            // return block
   TestBlock(graph, 7, false, -1);            // exit block
   TestBlock(graph, 8, false, -1);            // synthesized block at the loop exit
 }

 TEST(FindLoopsTest, InnerLoop) {
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
     Instruction::IF_EQ, 6,
     Instruction::IF_EQ, 3,
     Instruction::GOTO | 0xFE00,  // inner loop
     Instruction::GOTO | 0xFB00,
     Instruction::RETURN | 0 << 8);

   ArenaPool arena;
   ArenaAllocator allocator(&arena);
   HGraph* graph = TestCode(data, &allocator);

   TestBlock(graph, 0, false, -1);            // entry block
   TestBlock(graph, 1, false, -1);            // pre header of outer loop
   const int blocks2[] = {2, 3, 4, 5, 8};
   TestBlock(graph, 2, true, 2, blocks2, 5);  // outer loop header
   const int blocks3[] = {3, 4};
   TestBlock(graph, 3, true, 3, blocks3, 2);  // inner loop header
   TestBlock(graph, 4, false, 3);             // back edge on inner loop
   TestBlock(graph, 5, false, 2);             // back edge on outer loop
   TestBlock(graph, 6, false, -1);            // return block
   TestBlock(graph, 7, false, -1);            // exit block
   TestBlock(graph, 8, false, 2);             // synthesized block as pre header of inner loop

   ASSERT_TRUE(graph->GetBlocks().Get(3)->GetLoopInformation()->IsIn(
                     *graph->GetBlocks().Get(2)->GetLoopInformation()));
   ASSERT_FALSE(graph->GetBlocks().Get(2)->GetLoopInformation()->IsIn(
                     *graph->GetBlocks().Get(3)->GetLoopInformation()));
 }

 TEST(FindLoopsTest, TwoLoops) {
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
     Instruction::IF_EQ, 3,
     Instruction::GOTO | 0xFE00,  // first loop
     Instruction::IF_EQ, 3,
     Instruction::GOTO | 0xFE00,  // second loop
     Instruction::RETURN | 0 << 8);

   ArenaPool arena;
   ArenaAllocator allocator(&arena);
   HGraph* graph = TestCode(data, &allocator);

   TestBlock(graph, 0, false, -1);            // entry block
   TestBlock(graph, 1, false, -1);            // pre header of first loop
   const int blocks2[] = {2, 3};
   TestBlock(graph, 2, true, 2, blocks2, 2);  // first loop header
   TestBlock(graph, 3, false, 2);             // back edge of first loop
   const int blocks4[] = {4, 5};
   TestBlock(graph, 4, true, 4, blocks4, 2);  // second loop header
   TestBlock(graph, 5, false, 4);             // back edge of second loop
   TestBlock(graph, 6, false, -1);            // return block
   TestBlock(graph, 7, false, -1);            // exit block

   ASSERT_FALSE(graph->GetBlocks().Get(4)->GetLoopInformation()->IsIn(
                     *graph->GetBlocks().Get(2)->GetLoopInformation()));
   ASSERT_FALSE(graph->GetBlocks().Get(2)->GetLoopInformation()->IsIn(
                     *graph->GetBlocks().Get(4)->GetLoopInformation()));
 }

 TEST(FindLoopsTest, NonNaturalLoop) {
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
     Instruction::IF_EQ, 3,
     Instruction::GOTO | 0x0100,
     Instruction::IF_EQ, 3,
     Instruction::GOTO | 0xFD00,
     Instruction::RETURN | 0 << 8);

   ArenaPool arena;
   ArenaAllocator allocator(&arena);
   HGraph* graph = TestCode(data, &allocator);
   ASSERT_TRUE(graph->GetBlocks().Get(3)->IsLoopHeader());
   HLoopInformation* info = graph->GetBlocks().Get(3)->GetLoopInformation();
   ASSERT_FALSE(info->GetHeader()->Dominates(info->GetBackEdges().Get(0)));
 }

 TEST(FindLoopsTest, DoWhileLoop) {
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
     Instruction::GOTO | 0x0100,
     Instruction::IF_EQ, 0xFFFF,
     Instruction::RETURN | 0 << 8);

   ArenaPool arena;
   ArenaAllocator allocator(&arena);
   HGraph* graph = TestCode(data, &allocator);

   TestBlock(graph, 0, false, -1);            // entry block
   TestBlock(graph, 1, false, -1);            // pre header of first loop
   const int blocks2[] = {2, 3, 6};
   TestBlock(graph, 2, true, 2, blocks2, 3);  // loop header
   TestBlock(graph, 3, false, 2);             // back edge of first loop
   TestBlock(graph, 4, false, -1);            // return block
   TestBlock(graph, 5, false, -1);            // exit block
   TestBlock(graph, 6, false, 2);             // synthesized block to avoid a critical edge
 }

 }  // 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 "builder.h"
	#include "dex_file.h"
	#include "dex_instruction.h"
	#include "nodes.h"
	#include "optimizing_unit_test.h"
	#include "ssa_liveness_analysis.h"
	#include "pretty_printer.h"

	#include "gtest/gtest.h"

	namespace art {

	static HGraph* TestCode(const uint16_t* data, ArenaAllocator* allocator) {
	HGraph* graph = CreateGraph(allocator);
	HGraphBuilder builder(graph);
	const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
	builder.BuildGraph(*item);
	graph->BuildDominatorTree();
	graph->AnalyzeNaturalLoops();
	return graph;
	}

	TEST(FindLoopsTest, CFG1) {
	// Constant is not used.
	const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
	Instruction::CONST_4 \| 0 \| 0,
	Instruction::RETURN_VOID);

	ArenaPool arena;
	ArenaAllocator allocator(&arena);
	HGraph* graph = TestCode(data, &allocator);
	for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
	ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
	}
	}

	TEST(FindLoopsTest, CFG2) {
	const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
	Instruction::CONST_4 \| 0 \| 0,
	Instruction::RETURN);

	ArenaPool arena;
	ArenaAllocator allocator(&arena);
	HGraph* graph = TestCode(data, &allocator);
	for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
	ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
	}
	}

	TEST(FindLoopsTest, CFG3) {
	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);

	ArenaPool arena;
	ArenaAllocator allocator(&arena);
	HGraph* graph = TestCode(data, &allocator);
	for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
	ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
	}
	}

	TEST(FindLoopsTest, CFG4) {
	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);

	ArenaPool arena;
	ArenaAllocator allocator(&arena);
	HGraph* graph = TestCode(data, &allocator);
	for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
	ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
	}
	}

	TEST(FindLoopsTest, CFG5) {
	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);

	ArenaPool arena;
	ArenaAllocator allocator(&arena);
	HGraph* graph = TestCode(data, &allocator);
	for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
	ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
	}
	}

	static void TestBlock(HGraph* graph,
	int block_id,
	bool is_loop_header,
	int parent_loop_header_id,
	const int* blocks_in_loop = nullptr,
	size_t number_of_blocks = 0) {
	HBasicBlock* block = graph->GetBlocks().Get(block_id);
	ASSERT_EQ(block->IsLoopHeader(), is_loop_header);
	if (parent_loop_header_id == -1) {
	ASSERT_EQ(block->GetLoopInformation(), nullptr);
	} else {
	ASSERT_EQ(block->GetLoopInformation()->GetHeader()->GetBlockId(), parent_loop_header_id);
	}

	if (blocks_in_loop != nullptr) {
	HLoopInformation* info = block->GetLoopInformation();
	const BitVector& blocks = info->GetBlocks();
	ASSERT_EQ(blocks.NumSetBits(), number_of_blocks);
	for (size_t i = 0; i < number_of_blocks; ++i) {
	ASSERT_TRUE(blocks.IsBitSet(blocks_in_loop[i]));
	}
	} else {
	ASSERT_FALSE(block->IsLoopHeader());
	}
	}

	TEST(FindLoopsTest, Loop1) {
	// Simple loop with one preheader and one back edge.
	// var a = 0;
	// while (a == a) {
	// }
	// return;
	const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
	Instruction::CONST_4 \| 0 \| 0,
	Instruction::IF_EQ, 3,
	Instruction::GOTO \| 0xFE00,
	Instruction::RETURN_VOID);

	ArenaPool arena;
	ArenaAllocator allocator(&arena);
	HGraph* graph = TestCode(data, &allocator);

	TestBlock(graph, 0, false, -1); // entry block
	TestBlock(graph, 1, false, -1); // pre header
	const int blocks2[] = {2, 3};
	TestBlock(graph, 2, true, 2, blocks2, 2); // loop header
	TestBlock(graph, 3, false, 2); // block in loop
	TestBlock(graph, 4, false, -1); // return block
	TestBlock(graph, 5, false, -1); // exit block
	}

	TEST(FindLoopsTest, Loop2) {
	// 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) {
	// }
	// return a;
	const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
	Instruction::CONST_4 \| 0 \| 0,
	Instruction::GOTO \| 0x400,
	Instruction::IF_EQ, 4,
	Instruction::GOTO \| 0xFE00,
	Instruction::GOTO \| 0xFD00,
	Instruction::RETURN \| 0 << 8);

	ArenaPool arena;
	ArenaAllocator allocator(&arena);
	HGraph* graph = TestCode(data, &allocator);

	TestBlock(graph, 0, false, -1); // entry block
	TestBlock(graph, 1, false, -1); // goto block
	const int blocks2[] = {2, 3};
	TestBlock(graph, 2, true, 2, blocks2, 2); // loop header
	TestBlock(graph, 3, false, 2); // block in loop
	TestBlock(graph, 4, false, -1); // pre header
	TestBlock(graph, 5, false, -1); // return block
	TestBlock(graph, 6, false, -1); // exit block
	}

	TEST(FindLoopsTest, Loop3) {
	// Make sure we create a preheader of a loop when a header originally has two
	// incoming blocks and one back edge.
	const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
	Instruction::CONST_4 \| 0 \| 0,
	Instruction::IF_EQ, 3,
	Instruction::GOTO \| 0x100,
	Instruction::IF_EQ, 3,
	Instruction::GOTO \| 0xFE00,
	Instruction::RETURN \| 0 << 8);

	ArenaPool arena;
	ArenaAllocator allocator(&arena);
	HGraph* graph = TestCode(data, &allocator);

	TestBlock(graph, 0, false, -1); // entry block
	TestBlock(graph, 1, false, -1); // goto block
	TestBlock(graph, 2, false, -1);
	const int blocks2[] = {3, 4};
	TestBlock(graph, 3, true, 3, blocks2, 2); // loop header
	TestBlock(graph, 4, false, 3); // block in loop
	TestBlock(graph, 5, false, -1); // pre header
	TestBlock(graph, 6, false, -1); // return block
	TestBlock(graph, 7, false, -1); // exit block
	TestBlock(graph, 8, false, -1); // synthesized pre header
	}

	TEST(FindLoopsTest, Loop4) {
	// Test loop with originally two back edges.
	const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
	Instruction::CONST_4 \| 0 \| 0,
	Instruction::IF_EQ, 6,
	Instruction::IF_EQ, 3,
	Instruction::GOTO \| 0xFC00,
	Instruction::GOTO \| 0xFB00,
	Instruction::RETURN \| 0 << 8);

	ArenaPool arena;
	ArenaAllocator allocator(&arena);
	HGraph* graph = TestCode(data, &allocator);

	TestBlock(graph, 0, false, -1); // entry block
	TestBlock(graph, 1, false, -1); // pre header
	const int blocks2[] = {2, 3, 4, 5};
	TestBlock(graph, 2, true, 2, blocks2, arraysize(blocks2)); // loop header
	TestBlock(graph, 3, false, 2); // block in loop
	TestBlock(graph, 4, false, 2); // back edge
	TestBlock(graph, 5, false, 2); // back edge
	TestBlock(graph, 6, false, -1); // return block
	TestBlock(graph, 7, false, -1); // exit block
	}


	TEST(FindLoopsTest, Loop5) {
	// Test loop with two exit edges.
	const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
	Instruction::CONST_4 \| 0 \| 0,
	Instruction::IF_EQ, 6,
	Instruction::IF_EQ, 3,
	Instruction::GOTO \| 0x0200,
	Instruction::GOTO \| 0xFB00,
	Instruction::RETURN \| 0 << 8);

	ArenaPool arena;
	ArenaAllocator allocator(&arena);
	HGraph* graph = TestCode(data, &allocator);

	TestBlock(graph, 0, false, -1); // entry block
	TestBlock(graph, 1, false, -1); // pre header
	const int blocks2[] = {2, 3, 5};
	TestBlock(graph, 2, true, 2, blocks2, 3); // loop header
	TestBlock(graph, 3, false, 2); // block in loop
	TestBlock(graph, 4, false, -1); // loop exit
	TestBlock(graph, 5, false, 2); // back edge
	TestBlock(graph, 6, false, -1); // return block
	TestBlock(graph, 7, false, -1); // exit block
	TestBlock(graph, 8, false, -1); // synthesized block at the loop exit
	}

	TEST(FindLoopsTest, InnerLoop) {
	const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
	Instruction::CONST_4 \| 0 \| 0,
	Instruction::IF_EQ, 6,
	Instruction::IF_EQ, 3,
	Instruction::GOTO \| 0xFE00, // inner loop
	Instruction::GOTO \| 0xFB00,
	Instruction::RETURN \| 0 << 8);

	ArenaPool arena;
	ArenaAllocator allocator(&arena);
	HGraph* graph = TestCode(data, &allocator);

	TestBlock(graph, 0, false, -1); // entry block
	TestBlock(graph, 1, false, -1); // pre header of outer loop
	const int blocks2[] = {2, 3, 4, 5, 8};
	TestBlock(graph, 2, true, 2, blocks2, 5); // outer loop header
	const int blocks3[] = {3, 4};
	TestBlock(graph, 3, true, 3, blocks3, 2); // inner loop header
	TestBlock(graph, 4, false, 3); // back edge on inner loop
	TestBlock(graph, 5, false, 2); // back edge on outer loop
	TestBlock(graph, 6, false, -1); // return block
	TestBlock(graph, 7, false, -1); // exit block
	TestBlock(graph, 8, false, 2); // synthesized block as pre header of inner loop

	ASSERT_TRUE(graph->GetBlocks().Get(3)->GetLoopInformation()->IsIn(
	*graph->GetBlocks().Get(2)->GetLoopInformation()));
	ASSERT_FALSE(graph->GetBlocks().Get(2)->GetLoopInformation()->IsIn(
	*graph->GetBlocks().Get(3)->GetLoopInformation()));
	}

	TEST(FindLoopsTest, TwoLoops) {
	const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
	Instruction::CONST_4 \| 0 \| 0,
	Instruction::IF_EQ, 3,
	Instruction::GOTO \| 0xFE00, // first loop
	Instruction::IF_EQ, 3,
	Instruction::GOTO \| 0xFE00, // second loop
	Instruction::RETURN \| 0 << 8);

	ArenaPool arena;
	ArenaAllocator allocator(&arena);
	HGraph* graph = TestCode(data, &allocator);

	TestBlock(graph, 0, false, -1); // entry block
	TestBlock(graph, 1, false, -1); // pre header of first loop
	const int blocks2[] = {2, 3};
	TestBlock(graph, 2, true, 2, blocks2, 2); // first loop header
	TestBlock(graph, 3, false, 2); // back edge of first loop
	const int blocks4[] = {4, 5};
	TestBlock(graph, 4, true, 4, blocks4, 2); // second loop header
	TestBlock(graph, 5, false, 4); // back edge of second loop
	TestBlock(graph, 6, false, -1); // return block
	TestBlock(graph, 7, false, -1); // exit block

	ASSERT_FALSE(graph->GetBlocks().Get(4)->GetLoopInformation()->IsIn(
	*graph->GetBlocks().Get(2)->GetLoopInformation()));
	ASSERT_FALSE(graph->GetBlocks().Get(2)->GetLoopInformation()->IsIn(
	*graph->GetBlocks().Get(4)->GetLoopInformation()));
	}

	TEST(FindLoopsTest, NonNaturalLoop) {
	const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
	Instruction::CONST_4 \| 0 \| 0,
	Instruction::IF_EQ, 3,
	Instruction::GOTO \| 0x0100,
	Instruction::IF_EQ, 3,
	Instruction::GOTO \| 0xFD00,
	Instruction::RETURN \| 0 << 8);

	ArenaPool arena;
	ArenaAllocator allocator(&arena);
	HGraph* graph = TestCode(data, &allocator);
	ASSERT_TRUE(graph->GetBlocks().Get(3)->IsLoopHeader());
	HLoopInformation* info = graph->GetBlocks().Get(3)->GetLoopInformation();
	ASSERT_FALSE(info->GetHeader()->Dominates(info->GetBackEdges().Get(0)));
	}

	TEST(FindLoopsTest, DoWhileLoop) {
	const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
	Instruction::CONST_4 \| 0 \| 0,
	Instruction::GOTO \| 0x0100,
	Instruction::IF_EQ, 0xFFFF,
	Instruction::RETURN \| 0 << 8);

	ArenaPool arena;
	ArenaAllocator allocator(&arena);
	HGraph* graph = TestCode(data, &allocator);

	TestBlock(graph, 0, false, -1); // entry block
	TestBlock(graph, 1, false, -1); // pre header of first loop
	const int blocks2[] = {2, 3, 6};
	TestBlock(graph, 2, true, 2, blocks2, 3); // loop header
	TestBlock(graph, 3, false, 2); // back edge of first loop
	TestBlock(graph, 4, false, -1); // return block
	TestBlock(graph, 5, false, -1); // exit block
	TestBlock(graph, 6, false, 2); // synthesized block to avoid a critical edge
	}

	} // namespace art