Add loop recognition and CFG simplifications in new compiler.

We do three simplifications:
- Split critical edges, for code generation from SSA (new).
- Ensure one back edge per loop, to simplify loop recognition (new).
- Ensure only one pre header for a loop, to simplify SSA creation (existing).

Change-Id: I9bfccd4b236a00486a261078627b091c8a68be33

1 files changed, 362 insertions, 0 deletions

diff --git a/compiler/optimizing/find_loops_test.cc b/compiler/optimizing/find_loops_test.cc
new file mode 100644
index 0000000..fab9f7a
--- /dev/null
+++ b/compiler/optimizing/find_loops_test.cc
@@ -0,0 +1,362 @@
+/*
+ * 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 "pretty_printer.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+static HGraph* TestCode(const uint16_t* data, ArenaPool* pool) {
+  ArenaAllocator allocator(pool);
+  HGraphBuilder builder(&allocator);
+  const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
+  HGraph* graph = builder.BuildGraph(*item);
+  graph->BuildDominatorTree();
+  graph->FindNaturalLoops();
+  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;
+  HGraph* graph = TestCode(data, &arena);
+  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;
+  HGraph* graph = TestCode(data, &arena);
+  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;
+  HGraph* graph = TestCode(data, &arena);
+  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;
+  HGraph* graph = TestCode(data, &arena);
+  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;
+  HGraph* graph = TestCode(data, &arena);
+  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;
+  HGraph* graph = TestCode(data, &arena);
+
+  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;
+  HGraph* graph = TestCode(data, &arena);
+
+  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;
+  HGraph* graph = TestCode(data, &arena);
+
+  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;
+  HGraph* graph = TestCode(data, &arena);
+
+  TestBlock(graph, 0, false, -1);            // entry block
+  TestBlock(graph, 1, false, -1);            // pre header
+  const int blocks2[] = {2, 3, 4, 5, 8};
+  TestBlock(graph, 2, true, 2, blocks2, 5);  // loop header
+  TestBlock(graph, 3, false, 2);             // block in loop
+  TestBlock(graph, 4, false, 2);             // original back edge
+  TestBlock(graph, 5, false, 2);             // original back edge
+  TestBlock(graph, 6, false, -1);            // return block
+  TestBlock(graph, 7, false, -1);            // exit block
+  TestBlock(graph, 8, false, 2);             // synthesized back edge
+}
+
+
+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;
+  HGraph* graph = TestCode(data, &arena);
+
+  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;
+  HGraph* graph = TestCode(data, &arena);
+
+  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;
+  HGraph* graph = TestCode(data, &arena);
+
+  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;
+  HGraph* graph = TestCode(data, &arena);
+  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;
+  HGraph* graph = TestCode(data, &arena);
+
+  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