Linearize the graph before creating live ranges.
Change-Id: I02eb5671e3304ab062286131745c1366448aff58
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/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 @@
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 @@
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 @@
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 @@
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 @@
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::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 @@
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 @@
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 @@
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 @@
private:
std::string str_;
- DISALLOW_COPY_AND_ASSIGN(StringPrettyPrinter);
+ DISALLOW_COPY_AND_ASSIGN(SsaPrettyPrinter);
};
static void ReNumberInstructions(HGraph* graph) {
@@ -82,11 +82,12 @@
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());