Fix some bugs in graph construction/simplification methods.

Also fix a brano during SSA construction. The code should
not have been commented out. Added a test to cover what the code
intends.

Change-Id: Ia00ae79dcf75eb0d412f07649d73e7f94dbfb6f0

1 files changed, 322 insertions, 0 deletions

diff --git a/compiler/optimizing/graph_test.cc b/compiler/optimizing/graph_test.cc
new file mode 100644
index 0000000..371478c
--- /dev/null
+++ b/compiler/optimizing/graph_test.cc
@@ -0,0 +1,322 @@
+/*
+ * 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 "nodes.h"
+#include "optimizing_unit_test.h"
+#include "pretty_printer.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+static HBasicBlock* createIfBlock(HGraph* graph, ArenaAllocator* allocator) {
+  HBasicBlock* if_block = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(if_block);
+  HInstruction* instr = new (allocator) HIntConstant(4);
+  if_block->AddInstruction(instr);
+  instr = new (allocator) HIf(instr);
+  if_block->AddInstruction(instr);
+  return if_block;
+}
+
+static HBasicBlock* createGotoBlock(HGraph* graph, ArenaAllocator* allocator) {
+  HBasicBlock* block = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  HInstruction* got = new (allocator) HGoto();
+  block->AddInstruction(got);
+  return block;
+}
+
+static HBasicBlock* createReturnBlock(HGraph* graph, ArenaAllocator* allocator) {
+  HBasicBlock* block = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  HInstruction* return_instr = new (allocator) HReturnVoid();
+  block->AddInstruction(return_instr);
+  return block;
+}
+
+static HBasicBlock* createExitBlock(HGraph* graph, ArenaAllocator* allocator) {
+  HBasicBlock* block = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  HInstruction* exit_instr = new (allocator) HExit();
+  block->AddInstruction(exit_instr);
+  return block;
+}
+
+
+// Test that the successors of an if block stay consistent after a SimplifyCFG.
+// This test sets the false block to be the return block.
+TEST(GraphTest, IfSuccessorSimpleJoinBlock1) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* if_true = createGotoBlock(graph, &allocator);
+  HBasicBlock* return_block = createReturnBlock(graph, &allocator);
+  HBasicBlock* exit_block = createExitBlock(graph, &allocator);
+
+  entry_block->AddSuccessor(if_block);
+  if_block->AddSuccessor(if_true);
+  if_true->AddSuccessor(return_block);
+  if_block->AddSuccessor(return_block);
+  return_block->AddSuccessor(exit_block);
+
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_true);
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
+
+  graph->SimplifyCFG();
+
+  // Ensure we still have the same if true block.
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_true);
+
+  // Ensure the critical edge has been removed.
+  HBasicBlock* false_block = if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor();
+  ASSERT_NE(false_block, return_block);
+
+  // Ensure the new block branches to the join block.
+  ASSERT_EQ(false_block->GetSuccessors().Get(0), return_block);
+}
+
+// Test that the successors of an if block stay consistent after a SimplifyCFG.
+// This test sets the true block to be the return block.
+TEST(GraphTest, IfSuccessorSimpleJoinBlock2) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* if_false = createGotoBlock(graph, &allocator);
+  HBasicBlock* return_block = createReturnBlock(graph, &allocator);
+  HBasicBlock* exit_block = createExitBlock(graph, &allocator);
+
+  entry_block->AddSuccessor(if_block);
+  if_block->AddSuccessor(return_block);
+  if_false->AddSuccessor(return_block);
+  if_block->AddSuccessor(if_false);
+  return_block->AddSuccessor(exit_block);
+
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block);
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_false);
+
+  graph->SimplifyCFG();
+
+  // Ensure we still have the same if true block.
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_false);
+
+  // Ensure the critical edge has been removed.
+  HBasicBlock* true_block = if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor();
+  ASSERT_NE(true_block, return_block);
+
+  // Ensure the new block branches to the join block.
+  ASSERT_EQ(true_block->GetSuccessors().Get(0), return_block);
+}
+
+// Test that the successors of an if block stay consistent after a SimplifyCFG.
+// This test sets the true block to be the loop header.
+TEST(GraphTest, IfSuccessorMultipleBackEdges1) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* return_block = createReturnBlock(graph, &allocator);
+  HBasicBlock* exit_block = createExitBlock(graph, &allocator);
+
+  graph->SetEntryBlock(entry_block);
+  entry_block->AddSuccessor(if_block);
+  if_block->AddSuccessor(if_block);
+  if_block->AddSuccessor(return_block);
+  return_block->AddSuccessor(exit_block);
+
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_block);
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
+
+  graph->BuildDominatorTree();
+
+  // Ensure we still have the same if false block.
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
+
+  // Ensure there is only one back edge.
+  ASSERT_EQ(if_block->GetPredecessors().Size(), 2u);
+  ASSERT_EQ(if_block->GetPredecessors().Get(0), entry_block);
+  ASSERT_NE(if_block->GetPredecessors().Get(1), if_block);
+
+  // Ensure the new block is the back edge.
+  ASSERT_EQ(if_block->GetPredecessors().Get(1),
+            if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor());
+}
+
+// Test that the successors of an if block stay consistent after a SimplifyCFG.
+// This test sets the false block to be the loop header.
+TEST(GraphTest, IfSuccessorMultipleBackEdges2) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* return_block = createReturnBlock(graph, &allocator);
+  HBasicBlock* exit_block = createExitBlock(graph, &allocator);
+
+  graph->SetEntryBlock(entry_block);
+  entry_block->AddSuccessor(if_block);
+  if_block->AddSuccessor(return_block);
+  if_block->AddSuccessor(if_block);
+  return_block->AddSuccessor(exit_block);
+
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block);
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_block);
+
+  graph->BuildDominatorTree();
+
+  // Ensure we still have the same if true block.
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block);
+
+  // Ensure there is only one back edge.
+  ASSERT_EQ(if_block->GetPredecessors().Size(), 2u);
+  ASSERT_EQ(if_block->GetPredecessors().Get(0), entry_block);
+  ASSERT_NE(if_block->GetPredecessors().Get(1), if_block);
+
+  // Ensure the new block is the back edge.
+  ASSERT_EQ(if_block->GetPredecessors().Get(1),
+            if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor());
+}
+
+// Test that the successors of an if block stay consistent after a SimplifyCFG.
+// This test sets the true block to be a loop header with multiple pre headers.
+TEST(GraphTest, IfSuccessorMultiplePreHeaders1) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* first_if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* loop_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* return_block = createReturnBlock(graph, &allocator);
+
+  graph->SetEntryBlock(entry_block);
+  entry_block->AddSuccessor(first_if_block);
+  first_if_block->AddSuccessor(if_block);
+  first_if_block->AddSuccessor(loop_block);
+  loop_block->AddSuccessor(loop_block);
+  if_block->AddSuccessor(loop_block);
+  if_block->AddSuccessor(return_block);
+
+
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), loop_block);
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
+
+  graph->BuildDominatorTree();
+
+  HIf* if_instr = if_block->GetLastInstruction()->AsIf();
+  // Ensure we still have the same if false block.
+  ASSERT_EQ(if_instr->IfFalseSuccessor(), return_block);
+
+  // Ensure there is only one pre header..
+  ASSERT_EQ(loop_block->GetPredecessors().Size(), 2u);
+
+  // Ensure the new block is the successor of the true block.
+  ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors().Size(), 1u);
+  ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors().Get(0),
+            loop_block->GetLoopInformation()->GetPreHeader());
+}
+
+// Test that the successors of an if block stay consistent after a SimplifyCFG.
+// This test sets the false block to be a loop header with multiple pre headers.
+TEST(GraphTest, IfSuccessorMultiplePreHeaders2) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* first_if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* loop_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* return_block = createReturnBlock(graph, &allocator);
+
+  graph->SetEntryBlock(entry_block);
+  entry_block->AddSuccessor(first_if_block);
+  first_if_block->AddSuccessor(if_block);
+  first_if_block->AddSuccessor(loop_block);
+  loop_block->AddSuccessor(loop_block);
+  if_block->AddSuccessor(return_block);
+  if_block->AddSuccessor(loop_block);
+
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block);
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), loop_block);
+
+  graph->BuildDominatorTree();
+
+  HIf* if_instr = if_block->GetLastInstruction()->AsIf();
+  // Ensure we still have the same if true block.
+  ASSERT_EQ(if_instr->IfTrueSuccessor(), return_block);
+
+  // Ensure there is only one pre header..
+  ASSERT_EQ(loop_block->GetPredecessors().Size(), 2u);
+
+  // Ensure the new block is the successor of the false block.
+  ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors().Size(), 1u);
+  ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors().Get(0),
+            loop_block->GetLoopInformation()->GetPreHeader());
+}
+
+TEST(GraphTest, InsertInstructionBefore) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* block = createGotoBlock(graph, &allocator);
+  HInstruction* got = block->GetLastInstruction();
+  ASSERT_TRUE(got->IsControlFlow());
+
+  // Test at the beginning of the block.
+  HInstruction* first_instruction = new (&allocator) HIntConstant(4);
+  block->InsertInstructionBefore(first_instruction, got);
+
+  ASSERT_NE(first_instruction->GetId(), -1);
+  ASSERT_EQ(first_instruction->GetBlock(), block);
+  ASSERT_EQ(block->GetFirstInstruction(), first_instruction);
+  ASSERT_EQ(block->GetLastInstruction(), got);
+  ASSERT_EQ(first_instruction->GetNext(), got);
+  ASSERT_EQ(first_instruction->GetPrevious(), nullptr);
+  ASSERT_EQ(got->GetNext(), nullptr);
+  ASSERT_EQ(got->GetPrevious(), first_instruction);
+
+  // Test in the middle of the block.
+  HInstruction* second_instruction = new (&allocator) HIntConstant(4);
+  block->InsertInstructionBefore(second_instruction, got);
+
+  ASSERT_NE(second_instruction->GetId(), -1);
+  ASSERT_EQ(second_instruction->GetBlock(), block);
+  ASSERT_EQ(block->GetFirstInstruction(), first_instruction);
+  ASSERT_EQ(block->GetLastInstruction(), got);
+  ASSERT_EQ(first_instruction->GetNext(), second_instruction);
+  ASSERT_EQ(first_instruction->GetPrevious(), nullptr);
+  ASSERT_EQ(second_instruction->GetNext(), got);
+  ASSERT_EQ(second_instruction->GetPrevious(), first_instruction);
+  ASSERT_EQ(got->GetNext(), nullptr);
+  ASSERT_EQ(got->GetPrevious(), second_instruction);
+}
+
+}  // namespace art