Linearize the graph before creating live ranges.

Change-Id: I02eb5671e3304ab062286131745c1366448aff58

11 files changed, 355 insertions, 48 deletions

diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 406c2a1..b157d8e 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -79,6 +79,7 @@ COMPILER_GTEST_COMMON_SRC_FILES := \
 	compiler/optimizing/codegen_test.cc \
 	compiler/optimizing/dominator_test.cc \
 	compiler/optimizing/find_loops_test.cc \
+	compiler/optimizing/linearize_test.cc \
 	compiler/optimizing/liveness_test.cc \
 	compiler/optimizing/pretty_printer_test.cc \
 	compiler/optimizing/ssa_test.cc \
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index a7604be..b9c1164 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -188,6 +188,23 @@ HGraphVisualizer::HGraphVisualizer(std::ostream* output,
   printer.EndTag("compilation");
 }
 
+HGraphVisualizer::HGraphVisualizer(std::ostream* output,
+                                   HGraph* graph,
+                                   const char* name)
+    : output_(output), graph_(graph), is_enabled_(false) {
+  if (output == nullptr) {
+    return;
+  }
+
+  is_enabled_ = true;
+  HGraphVisualizerPrinter printer(graph, *output_);
+  printer.StartTag("compilation");
+  printer.PrintProperty("name", name);
+  printer.PrintProperty("method", name);
+  printer.PrintTime("date");
+  printer.EndTag("compilation");
+}
+
 void HGraphVisualizer::DumpGraph(const char* pass_name) {
   if (!is_enabled_) {
     return;
diff --git a/compiler/optimizing/graph_visualizer.h b/compiler/optimizing/graph_visualizer.h
index 433d55d..2b88e65 100644
--- a/compiler/optimizing/graph_visualizer.h
+++ b/compiler/optimizing/graph_visualizer.h
@@ -42,6 +42,12 @@ class HGraphVisualizer : public ValueObject {
                    const DexCompilationUnit& cu);
 
   /**
+   * Version of `HGraphVisualizer` for unit testing, that is when a
+   * `DexCompilationUnit` is not available.
+   */
+  HGraphVisualizer(std::ostream* output, HGraph* graph, const char* name);
+
+  /**
    * If this visualizer is enabled, emit the compilation information
    * in `output_`.
    */
diff --git a/compiler/optimizing/linearize_test.cc b/compiler/optimizing/linearize_test.cc
new file mode 100644
index 0000000..4c819a2
--- /dev/null
+++ b/compiler/optimizing/linearize_test.cc
@@ -0,0 +1,190 @@
+/*
+ * 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 <fstream>
+
+#include "base/stringprintf.h"
+#include "builder.h"
+#include "dex_file.h"
+#include "dex_instruction.h"
+#include "graph_visualizer.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "pretty_printer.h"
+#include "ssa_builder.h"
+#include "ssa_liveness_analysis.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+static void TestCode(const uint16_t* data, const int* expected_order, size_t number_of_blocks) {
+  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->FindNaturalLoops();
+  SsaLivenessAnalysis liveness(*graph);
+  liveness.Analyze();
+
+  ASSERT_EQ(liveness.GetLinearPostOrder().Size(), number_of_blocks);
+  for (size_t i = 0; i < number_of_blocks; ++i) {
+    ASSERT_EQ(liveness.GetLinearPostOrder().Get(number_of_blocks - i - 1)->GetBlockId(),
+              expected_order[i]);
+  }
+}
+
+TEST(LinearizeTest, CFG1) {
+  // Structure of this graph (* are back edges)
+  //            Block0
+  //              |
+  //            Block1
+  //              |
+  //            Block2 ******
+  //            /   \       *
+  //       Block5   Block7  *
+  //         |        |     *
+  //       Block6   Block3  *
+  //               * /   \  *
+  //           Block4   Block8
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 5,
+    Instruction::IF_EQ, 0xFFFE,
+    Instruction::GOTO | 0xFE00,
+    Instruction::RETURN_VOID);
+
+  const int blocks[] = {0, 1, 2, 7, 3, 4, 8, 5, 6};
+  TestCode(data, blocks, 9);
+}
+
+TEST(LinearizeTest, CFG2) {
+  // Structure of this graph (* are back edges)
+  //            Block0
+  //              |
+  //            Block1
+  //              |
+  //            Block2 ******
+  //            /   \       *
+  //       Block3   Block7  *
+  //         |        |     *
+  //       Block6   Block4  *
+  //               * /   \  *
+  //           Block5   Block8
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::RETURN_VOID,
+    Instruction::IF_EQ, 0xFFFD,
+    Instruction::GOTO | 0xFE00);
+
+  const int blocks[] = {0, 1, 2, 7, 4, 5, 8, 3, 6};
+  TestCode(data, blocks, 9);
+}
+
+TEST(LinearizeTest, CFG3) {
+  // Structure of this graph (* are back edges)
+  //            Block0
+  //              |
+  //            Block1
+  //              |
+  //            Block2 ******
+  //            /   \       *
+  //       Block3   Block8  *
+  //         |        |     *
+  //       Block7   Block5  *
+  //                 / *  \ *
+  //           Block6  * Block9
+  //             |     *
+  //           Block4 **
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::RETURN_VOID,
+    Instruction::GOTO | 0x0100,
+    Instruction::IF_EQ, 0xFFFC,
+    Instruction::GOTO | 0xFD00);
+
+  const int blocks[] = {0, 1, 2, 8, 5, 6, 4, 9, 3, 7};
+  TestCode(data, blocks, 10);
+}
+
+TEST(LinearizeTest, CFG4) {
+  // Structure of this graph (* are back edges)
+  //            Block0
+  //              |
+  //            Block1
+  //              |
+  //            Block2
+  //            / *  \
+  //       Block6 * Block8
+  //         |    *   |
+  //       Block7 * Block3 *******
+  //              *  /  \        *
+  //           Block9   Block10  *
+  //                      |      *
+  //                    Block4   *
+  //                   */    \   *
+  //                Block5  Block11
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 7,
+    Instruction::IF_EQ, 0xFFFE,
+    Instruction::IF_EQ, 0xFFFE,
+    Instruction::GOTO | 0xFE00,
+    Instruction::RETURN_VOID);
+
+  const int blocks[] = {0, 1, 2, 8, 3, 10, 4, 5, 11, 9, 6, 7};
+  TestCode(data, blocks, 12);
+}
+
+TEST(LinearizeTest, CFG5) {
+  // Structure of this graph (* are back edges)
+  //            Block0
+  //              |
+  //            Block1
+  //              |
+  //            Block2
+  //            / *  \
+  //       Block3 * Block8
+  //         |    *   |
+  //       Block7 * Block4 *******
+  //              *  /  \        *
+  //           Block9   Block10  *
+  //                      |      *
+  //                    Block5   *
+  //                   */    \   *
+  //                Block6  Block11
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::RETURN_VOID,
+    Instruction::IF_EQ, 0xFFFD,
+    Instruction::IF_EQ, 0xFFFE,
+    Instruction::GOTO | 0xFE00);
+
+  const int blocks[] = {0, 1, 2, 8, 4, 10, 5, 6, 11, 9, 3, 7};
+  TestCode(data, blocks, 12);
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc
index d665ab9..53e7bbe 100644
--- a/compiler/optimizing/liveness_test.cc
+++ b/compiler/optimizing/liveness_test.cc
@@ -35,6 +35,7 @@ static void TestCode(const uint16_t* data, const char* expected) {
   ASSERT_NE(graph, nullptr);
   graph->BuildDominatorTree();
   graph->TransformToSSA();
+  graph->FindNaturalLoops();
   SsaLivenessAnalysis liveness(*graph);
   liveness.Analyze();
 
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 27b87ca..1085c10 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -445,7 +445,7 @@ class HInstruction : public ArenaObject {
   bool HasUses() const { return uses_ != nullptr || env_uses_ != nullptr; }
 
   size_t NumberOfUses() const {
-    // TODO: Optimize this method if it is used outside of the HGraphTracer.
+    // TODO: Optimize this method if it is used outside of the HGraphVisualizer.
     size_t result = 0;
     HUseListNode<HInstruction>* current = uses_;
     while (current != nullptr) {
diff --git a/compiler/optimizing/pretty_printer.h b/compiler/optimizing/pretty_printer.h
index dfeafe7..a7727c0 100644
--- a/compiler/optimizing/pretty_printer.h
+++ b/compiler/optimizing/pretty_printer.h
@@ -100,6 +100,47 @@ class HPrettyPrinter : public HGraphVisitor {
   DISALLOW_COPY_AND_ASSIGN(HPrettyPrinter);
 };
 
+class StringPrettyPrinter : public HPrettyPrinter {
+ public:
+  explicit StringPrettyPrinter(HGraph* graph)
+      : HPrettyPrinter(graph), str_(""), current_block_(nullptr) { }
+
+  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 VisitBasicBlock(HBasicBlock* block) {
+    current_block_ = block;
+    HPrettyPrinter::VisitBasicBlock(block);
+  }
+
+  virtual void VisitGoto(HGoto* gota) {
+    PrintString("  ");
+    PrintInt(gota->GetId());
+    PrintString(": Goto ");
+    PrintInt(current_block_->GetSuccessors().Get(0)->GetBlockId());
+    PrintNewLine();
+  }
+
+ private:
+  std::string str_;
+  HBasicBlock* current_block_;
+
+  DISALLOW_COPY_AND_ASSIGN(StringPrettyPrinter);
+};
+
 }  // namespace art
 
 #endif  // ART_COMPILER_OPTIMIZING_PRETTY_PRINTER_H_
diff --git a/compiler/optimizing/pretty_printer_test.cc b/compiler/optimizing/pretty_printer_test.cc
index 006349c..7e604e9 100644
--- a/compiler/optimizing/pretty_printer_test.cc
+++ b/compiler/optimizing/pretty_printer_test.cc
@@ -27,47 +27,6 @@
 
 namespace art {
 
-class StringPrettyPrinter : public HPrettyPrinter {
- public:
-  explicit StringPrettyPrinter(HGraph* graph)
-      : HPrettyPrinter(graph), str_(""), current_block_(nullptr) { }
-
-  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 VisitBasicBlock(HBasicBlock* block) {
-    current_block_ = block;
-    HPrettyPrinter::VisitBasicBlock(block);
-  }
-
-  virtual void VisitGoto(HGoto* gota) {
-    PrintString("  ");
-    PrintInt(gota->GetId());
-    PrintString(": Goto ");
-    PrintInt(current_block_->GetSuccessors().Get(0)->GetBlockId());
-    PrintNewLine();
-  }
-
- private:
-  std::string str_;
-  HBasicBlock* current_block_;
-
-  DISALLOW_COPY_AND_ASSIGN(StringPrettyPrinter);
-};
-
 static void TestCode(const uint16_t* data, const char* expected) {
   ArenaPool pool;
   ArenaAllocator allocator(&pool);
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 7c2ec39..85171aa 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -20,13 +20,92 @@
 namespace art {
 
 void SsaLivenessAnalysis::Analyze() {
+  LinearizeGraph();
   NumberInstructions();
   ComputeSets();
 }
 
+static bool IsLoopExit(HLoopInformation* current, HLoopInformation* to) {
+  // `to` is either not part of a loop, or `current` is an inner loop of `to`.
+  return to == nullptr || (current != to && current->IsIn(*to));
+}
+
+static bool IsLoop(HLoopInformation* info) {
+  return info != nullptr;
+}
+
+static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) {
+  return first_loop == second_loop;
+}
+
+static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) {
+  return (inner != outer)
+      && (inner != nullptr)
+      && (outer != nullptr)
+      && inner->IsIn(*outer);
+}
+
+static void VisitBlockForLinearization(HBasicBlock* block,
+                                       GrowableArray<HBasicBlock*>* order,
+                                       ArenaBitVector* visited) {
+  if (visited->IsBitSet(block->GetBlockId())) {
+    return;
+  }
+  visited->SetBit(block->GetBlockId());
+  size_t number_of_successors = block->GetSuccessors().Size();
+  if (number_of_successors == 0) {
+    // Nothing to do.
+  } else if (number_of_successors == 1) {
+    VisitBlockForLinearization(block->GetSuccessors().Get(0), order, visited);
+  } else {
+    DCHECK_EQ(number_of_successors, 2u);
+    HBasicBlock* first_successor = block->GetSuccessors().Get(0);
+    HBasicBlock* second_successor = block->GetSuccessors().Get(1);
+    HLoopInformation* my_loop = block->GetLoopInformation();
+    HLoopInformation* first_loop = first_successor->GetLoopInformation();
+    HLoopInformation* second_loop = second_successor->GetLoopInformation();
+
+    if (!IsLoop(my_loop)) {
+      // Nothing to do. Current order is fine.
+    } else if (IsLoopExit(my_loop, second_loop) && InSameLoop(my_loop, first_loop)) {
+      // Visit the loop exit first in post order.
+      std::swap(first_successor, second_successor);
+    } else if (IsInnerLoop(my_loop, first_loop) && !IsInnerLoop(my_loop, second_loop)) {
+      // Visit the inner loop last in post order.
+      std::swap(first_successor, second_successor);
+    }
+    VisitBlockForLinearization(first_successor, order, visited);
+    VisitBlockForLinearization(second_successor, order, visited);
+  }
+  order->Add(block);
+}
+
+class HLinearOrderIterator : public ValueObject {
+ public:
+  explicit HLinearOrderIterator(const GrowableArray<HBasicBlock*>& post_order)
+      : post_order_(post_order), index_(post_order.Size()) {}
+
+  bool Done() const { return index_ == 0; }
+  HBasicBlock* Current() const { return post_order_.Get(index_ -1); }
+  void Advance() { --index_; DCHECK_GE(index_, 0U); }
+
+ private:
+  const GrowableArray<HBasicBlock*>& post_order_;
+  size_t index_;
+
+  DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator);
+};
+
+void SsaLivenessAnalysis::LinearizeGraph() {
+  // For simplicity of the implementation, we create post linear order. The order for
+  // computing live ranges is the reverse of that order.
+  ArenaBitVector visited(graph_.GetArena(), graph_.GetBlocks().Size(), false);
+  VisitBlockForLinearization(graph_.GetEntryBlock(), &linear_post_order_, &visited);
+}
+
 void SsaLivenessAnalysis::NumberInstructions() {
   int ssa_index = 0;
-  for (HReversePostOrderIterator it(graph_); !it.Done(); it.Advance()) {
+  for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
 
     for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
@@ -47,7 +126,7 @@ void SsaLivenessAnalysis::NumberInstructions() {
 }
 
 void SsaLivenessAnalysis::ComputeSets() {
-  for (HReversePostOrderIterator it(graph_); !it.Done(); it.Advance()) {
+  for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
     block_infos_.Put(
         block->GetBlockId(),
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 6a901d1..b8695ba 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -48,6 +48,7 @@ class SsaLivenessAnalysis : public ValueObject {
  public:
   explicit SsaLivenessAnalysis(const HGraph& graph)
       : graph_(graph),
+        linear_post_order_(graph.GetArena(), graph.GetBlocks().Size()),
         block_infos_(graph.GetArena(), graph.GetBlocks().Size()),
         number_of_ssa_values_(0) {
     block_infos_.SetSize(graph.GetBlocks().Size());
@@ -67,7 +68,17 @@ class SsaLivenessAnalysis : public ValueObject {
     return &block_infos_.Get(block.GetBlockId())->kill_;
   }
 
+  const GrowableArray<HBasicBlock*>& GetLinearPostOrder() const {
+    return linear_post_order_;
+  }
+
  private:
+  // Linearize the graph so that:
+  // (1): a block is always after its dominator,
+  // (2): blocks of loops are contiguous.
+  // This creates a natural and efficient ordering when visualizing live ranges.
+  void LinearizeGraph();
+
   // Give an SSA number to each instruction that defines a value used by another instruction.
   void NumberInstructions();
 
@@ -90,6 +101,7 @@ class SsaLivenessAnalysis : public ValueObject {
   bool UpdateLiveOut(const HBasicBlock& block);
 
   const HGraph& graph_;
+  GrowableArray<HBasicBlock*> linear_post_order_;
   GrowableArray<BlockInfo*> block_infos_;
   size_t number_of_ssa_values_;
 
diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc
index 415d146..d104619 100644
--- a/compiler/optimizing/ssa_test.cc
+++ b/compiler/optimizing/ssa_test.cc
@@ -28,9 +28,9 @@
 
 namespace art {
 
-class StringPrettyPrinter : public HPrettyPrinter {
+class SsaPrettyPrinter : public HPrettyPrinter {
  public:
-  explicit StringPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") {}
+  explicit SsaPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") {}
 
   virtual void PrintInt(int value) {
     str_ += StringPrintf("%d", value);
@@ -59,7 +59,7 @@ class StringPrettyPrinter : public HPrettyPrinter {
  private:
   std::string str_;
 
-  DISALLOW_COPY_AND_ASSIGN(StringPrettyPrinter);
+  DISALLOW_COPY_AND_ASSIGN(SsaPrettyPrinter);
 };
 
 static void ReNumberInstructions(HGraph* graph) {
@@ -82,11 +82,12 @@ static void TestCode(const uint16_t* data, const char* expected) {
   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);
+  SsaPrettyPrinter printer(graph);
   printer.VisitInsertionOrder();
 
   ASSERT_STREQ(expected, printer.str().c_str());