Re-apply: Initial check-in of an optimizing compiler.
The classes and the names are very much inspired by V8/Dart.
It currently only supports the RETURN_VOID dex instruction,
and there is a pretty printer to check if the building of the
graph is correct.
Change-Id: I28e125dfee86ae6ec9b3fec6aa1859523b92a893
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
new file mode 100644
index 0000000..2c1091c
--- /dev/null
+++ b/compiler/optimizing/builder.cc
@@ -0,0 +1,64 @@
+/*
+ *
+ * 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 "dex_instruction.h"
+#include "builder.h"
+#include "nodes.h"
+
+namespace art {
+
+HGraph* HGraphBuilder::BuildGraph(const uint16_t* code_ptr, const uint16_t* code_end) {
+ graph_ = new (arena_) HGraph(arena_);
+
+ entry_block_ = new (arena_) HBasicBlock(graph_);
+ graph_->AddBlock(entry_block_);
+
+ exit_block_ = new (arena_) HBasicBlock(graph_);
+ // The exit block is added at the end of this method to ensure
+ // its id is the greatest. This is needed for dominator computation.
+
+ entry_block_->AddInstruction(new (arena_) HGoto(entry_block_));
+
+ current_block_ = new (arena_) HBasicBlock(graph_);
+ graph_->AddBlock(current_block_);
+ entry_block_->AddSuccessor(current_block_);
+
+ while (code_ptr < code_end) {
+ const Instruction& instruction = *Instruction::At(code_ptr);
+ if (!AnalyzeDexInstruction(instruction)) return nullptr;
+ code_ptr += instruction.SizeInCodeUnits();
+ }
+
+ exit_block_->AddInstruction(new (arena_) HExit(exit_block_));
+ graph_->AddBlock(exit_block_);
+ return graph_;
+}
+
+bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction) {
+ switch (instruction.Opcode()) {
+ case Instruction::RETURN_VOID:
+ current_block_->AddInstruction(new (arena_) HReturnVoid(current_block_));
+ current_block_->AddSuccessor(exit_block_);
+ current_block_ = nullptr;
+ break;
+ default:
+ return false;
+ }
+ return true;
+}
+
+} // namespace art
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h
new file mode 100644
index 0000000..3e94fba
--- /dev/null
+++ b/compiler/optimizing/builder.h
@@ -0,0 +1,57 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_BUILDER_H_
+#define ART_COMPILER_OPTIMIZING_BUILDER_H_
+
+#include "utils/allocation.h"
+
+namespace art {
+
+class ArenaAllocator;
+class Instruction;
+class HBasicBlock;
+class HGraph;
+
+class HGraphBuilder : public ValueObject {
+ public:
+ explicit HGraphBuilder(ArenaAllocator* arena)
+ : arena_(arena),
+ entry_block_(nullptr),
+ exit_block_(nullptr),
+ current_block_(nullptr),
+ graph_(nullptr) { }
+
+ HGraph* BuildGraph(const uint16_t* start, const uint16_t* end);
+
+ private:
+ // Analyzes the dex instruction and adds HInstruction to the graph
+ // to execute that instruction. Returns whether the instruction can
+ // be handled.
+ bool AnalyzeDexInstruction(const Instruction& instruction);
+
+ ArenaAllocator* const arena_;
+ HBasicBlock* entry_block_;
+ HBasicBlock* exit_block_;
+ HBasicBlock* current_block_;
+ HGraph* graph_;
+
+ DISALLOW_COPY_AND_ASSIGN(HGraphBuilder);
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_BUILDER_H_
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
new file mode 100644
index 0000000..e7e9f47
--- /dev/null
+++ b/compiler/optimizing/nodes.cc
@@ -0,0 +1,60 @@
+/*
+ * 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 "nodes.h"
+#include "utils/growable_array.h"
+
+namespace art {
+
+void HGraph::AddBlock(HBasicBlock* block) {
+ block->set_block_id(blocks_.Size());
+ blocks_.Add(block);
+}
+
+void HBasicBlock::AddInstruction(HInstruction* instruction) {
+ if (first_instruction_ == nullptr) {
+ DCHECK(last_instruction_ == nullptr);
+ first_instruction_ = last_instruction_ = instruction;
+ } else {
+ last_instruction_->next_ = instruction;
+ instruction->previous_ = last_instruction_;
+ last_instruction_ = instruction;
+ }
+}
+
+#define DEFINE_ACCEPT(name) \
+void H##name::Accept(HGraphVisitor* visitor) { \
+ visitor->Visit##name(this); \
+}
+
+FOR_EACH_INSTRUCTION(DEFINE_ACCEPT)
+
+#undef DEFINE_ACCEPT
+
+void HGraphVisitor::VisitInsertionOrder() {
+ const GrowableArray<HBasicBlock*>* blocks = graph_->blocks();
+ for (size_t i = 0 ; i < blocks->Size(); i++) {
+ VisitBasicBlock(blocks->Get(i));
+ }
+}
+
+void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) {
+ for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
+ it.Current()->Accept(this);
+ }
+}
+
+} // namespace art
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
new file mode 100644
index 0000000..3d1c25e
--- /dev/null
+++ b/compiler/optimizing/nodes.h
@@ -0,0 +1,276 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_NODES_H_
+#define ART_COMPILER_OPTIMIZING_NODES_H_
+
+#include "utils/allocation.h"
+#include "utils/growable_array.h"
+
+namespace art {
+
+class HBasicBlock;
+class HInstruction;
+class HGraphVisitor;
+
+static const int kDefaultNumberOfBlocks = 8;
+static const int kDefaultNumberOfSuccessors = 2;
+static const int kDefaultNumberOfPredecessors = 2;
+
+// Control-flow graph of a method. Contains a list of basic blocks.
+class HGraph : public ArenaObject {
+ public:
+ explicit HGraph(ArenaAllocator* arena)
+ : arena_(arena),
+ blocks_(arena, kDefaultNumberOfBlocks) { }
+
+ ArenaAllocator* arena() const { return arena_; }
+ const GrowableArray<HBasicBlock*>* blocks() const { return &blocks_; }
+
+ void AddBlock(HBasicBlock* block);
+
+ private:
+ ArenaAllocator* const arena_;
+ GrowableArray<HBasicBlock*> blocks_;
+
+ DISALLOW_COPY_AND_ASSIGN(HGraph);
+};
+
+// A block in a method. Contains the list of instructions represented
+// as a double linked list. Each block knows its predecessors and
+// successors.
+class HBasicBlock : public ArenaObject {
+ public:
+ explicit HBasicBlock(HGraph* graph)
+ : graph_(graph),
+ predecessors_(graph->arena(), kDefaultNumberOfPredecessors),
+ successors_(graph->arena(), kDefaultNumberOfSuccessors),
+ first_instruction_(nullptr),
+ last_instruction_(nullptr),
+ block_id_(-1) { }
+
+ const GrowableArray<HBasicBlock*>* predecessors() const {
+ return &predecessors_;
+ }
+
+ const GrowableArray<HBasicBlock*>* successors() const {
+ return &successors_;
+ }
+
+ HGraph* graph() const { return graph_; }
+
+ int block_id() const { return block_id_; }
+ void set_block_id(int id) { block_id_ = id; }
+
+ HInstruction* first_instruction() const { return first_instruction_; }
+ HInstruction* last_instruction() const { return last_instruction_; }
+
+ void AddSuccessor(HBasicBlock* block) {
+ successors_.Add(block);
+ block->predecessors_.Add(this);
+ }
+
+ void AddInstruction(HInstruction* instruction);
+
+ private:
+ HGraph* const graph_;
+ GrowableArray<HBasicBlock*> predecessors_;
+ GrowableArray<HBasicBlock*> successors_;
+ HInstruction* first_instruction_;
+ HInstruction* last_instruction_;
+ int block_id_;
+
+ DISALLOW_COPY_AND_ASSIGN(HBasicBlock);
+};
+
+#define FOR_EACH_INSTRUCTION(M) \
+ M(Exit) \
+ M(Goto) \
+ M(ReturnVoid) \
+
+#define DECLARE_INSTRUCTION(type) \
+ virtual void Accept(HGraphVisitor* visitor); \
+ virtual const char* DebugName() const { return #type; } \
+
+class HInstruction : public ArenaObject {
+ public:
+ explicit HInstruction(HBasicBlock* block)
+ : previous_(nullptr),
+ next_(nullptr) { }
+ virtual ~HInstruction() { }
+
+ HInstruction* next() const { return next_; }
+ HInstruction* previous() const { return previous_; }
+
+ virtual intptr_t InputCount() const = 0;
+ virtual HInstruction* InputAt(intptr_t i) const = 0;
+
+ virtual void Accept(HGraphVisitor* visitor) = 0;
+ virtual const char* DebugName() const = 0;
+
+ private:
+ HInstruction* previous_;
+ HInstruction* next_;
+
+ friend class HBasicBlock;
+
+ DISALLOW_COPY_AND_ASSIGN(HInstruction);
+};
+
+class HInstructionIterator : public ValueObject {
+ public:
+ explicit HInstructionIterator(HBasicBlock* block)
+ : instruction_(block->first_instruction()) {
+ next_ = Done() ? nullptr : instruction_->next();
+ }
+
+ inline bool Done() const { return instruction_ == nullptr; }
+ inline HInstruction* Current() { return instruction_; }
+ inline void Advance() {
+ instruction_ = next_;
+ next_ = Done() ? nullptr : instruction_->next();
+ }
+
+ private:
+ HInstruction* instruction_;
+ HInstruction* next_;
+};
+
+// An embedded container with N elements of type T. Used (with partial
+// specialization for N=0) because embedded arrays cannot have size 0.
+template<typename T, intptr_t N>
+class EmbeddedArray {
+ public:
+ EmbeddedArray() : elements_() { }
+
+ intptr_t length() const { return N; }
+
+ const T& operator[](intptr_t i) const {
+ ASSERT(i < length());
+ return elements_[i];
+ }
+
+ T& operator[](intptr_t i) {
+ ASSERT(i < length());
+ return elements_[i];
+ }
+
+ const T& At(intptr_t i) const {
+ return (*this)[i];
+ }
+
+ void SetAt(intptr_t i, const T& val) {
+ (*this)[i] = val;
+ }
+
+ private:
+ T elements_[N];
+};
+
+template<typename T>
+class EmbeddedArray<T, 0> {
+ public:
+ intptr_t length() const { return 0; }
+ const T& operator[](intptr_t i) const {
+ LOG(FATAL) << "Unreachable";
+ static T sentinel = 0;
+ return sentinel;
+ }
+ T& operator[](intptr_t i) {
+ LOG(FATAL) << "Unreachable";
+ static T sentinel = 0;
+ return sentinel;
+ }
+};
+
+template<intptr_t N>
+class HTemplateInstruction: public HInstruction {
+ public:
+ HTemplateInstruction<N>(HBasicBlock* block)
+ : HInstruction(block),
+ inputs_() { }
+ virtual ~HTemplateInstruction() { }
+
+ virtual intptr_t InputCount() const { return N; }
+ virtual HInstruction* InputAt(intptr_t i) const { return inputs_[i]; }
+
+ private:
+ EmbeddedArray<HInstruction*, N> inputs_;
+};
+
+// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow
+// instruction that branches to the exit block.
+class HReturnVoid : public HTemplateInstruction<0> {
+ public:
+ explicit HReturnVoid(HBasicBlock* block) : HTemplateInstruction<0>(block) { }
+
+ DECLARE_INSTRUCTION(ReturnVoid)
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(HReturnVoid);
+};
+
+// The exit instruction is the only instruction of the exit block.
+// Instructions aborting the method (HTrow and HReturn) must branch to the
+// exit block.
+class HExit : public HTemplateInstruction<0> {
+ public:
+ explicit HExit(HBasicBlock* block) : HTemplateInstruction<0>(block) { }
+
+ DECLARE_INSTRUCTION(Exit)
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(HExit);
+};
+
+// Jumps from one block to another.
+class HGoto : public HTemplateInstruction<0> {
+ public:
+ explicit HGoto(HBasicBlock* block) : HTemplateInstruction<0>(block) { }
+
+ DECLARE_INSTRUCTION(Goto)
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(HGoto);
+};
+
+class HGraphVisitor : public ValueObject {
+ public:
+ explicit HGraphVisitor(HGraph* graph) : graph_(graph) { }
+ virtual ~HGraphVisitor() { }
+
+ virtual void VisitInstruction(HInstruction* instruction) { }
+ virtual void VisitBasicBlock(HBasicBlock* block);
+
+ void VisitInsertionOrder();
+
+ // Visit functions for instruction classes.
+#define DECLARE_VISIT_INSTRUCTION(name) \
+ virtual void Visit##name(H##name* instr) { VisitInstruction(instr); }
+
+ FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION)
+
+#undef DECLARE_VISIT_INSTRUCTION
+
+ private:
+ HGraph* graph_;
+
+ DISALLOW_COPY_AND_ASSIGN(HGraphVisitor);
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_NODES_H_
diff --git a/compiler/optimizing/pretty_printer.h b/compiler/optimizing/pretty_printer.h
new file mode 100644
index 0000000..62a5a2c
--- /dev/null
+++ b/compiler/optimizing/pretty_printer.h
@@ -0,0 +1,51 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_PRETTY_PRINTER_H_
+#define ART_COMPILER_OPTIMIZING_PRETTY_PRINTER_H_
+
+#include "nodes.h"
+
+namespace art {
+
+class HPrettyPrinter : public HGraphVisitor {
+ public:
+ explicit HPrettyPrinter(HGraph* graph) : HGraphVisitor(graph) { }
+
+ virtual void VisitInstruction(HInstruction* instruction) {
+ PrintString(" ");
+ PrintString(instruction->DebugName());
+ PrintNewLine();
+ }
+
+ virtual void VisitBasicBlock(HBasicBlock* block) {
+ PrintString("BasicBlock ");
+ PrintInt(block->block_id());
+ PrintNewLine();
+ HGraphVisitor::VisitBasicBlock(block);
+ }
+
+ virtual void PrintNewLine() = 0;
+ virtual void PrintInt(int value) = 0;
+ virtual void PrintString(const char* value) = 0;
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(HPrettyPrinter);
+};
+
+} // 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
new file mode 100644
index 0000000..81a0d91
--- /dev/null
+++ b/compiler/optimizing/pretty_printer_test.cc
@@ -0,0 +1,87 @@
+/*
+ * 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 "dex_instruction.h"
+#include "nodes.h"
+#include "pretty_printer.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+const uint16_t data[] = { Instruction::RETURN_VOID };
+
+const char* expected =
+ "BasicBlock 0\n"
+ " Goto\n"
+ "BasicBlock 1\n"
+ " ReturnVoid\n"
+ "BasicBlock 2\n"
+ " Exit\n";
+
+class StringPrettyPrinter : public HPrettyPrinter {
+ public:
+ explicit StringPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") { }
+
+ 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_; }
+
+ private:
+ std::string str_;
+ DISALLOW_COPY_AND_ASSIGN(StringPrettyPrinter);
+};
+
+TEST(OptimizerTest, ReturnVoid) {
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+ HGraphBuilder builder(&allocator);
+ HGraph* graph = builder.BuildGraph(data, data + 1);
+ ASSERT_NE(graph, nullptr);
+ StringPrettyPrinter printer(graph);
+ printer.VisitInsertionOrder();
+ ASSERT_STREQ(expected, printer.str().c_str());
+
+ const GrowableArray<HBasicBlock*>* blocks = graph->blocks();
+ ASSERT_EQ(blocks->Get(0)->predecessors()->Size(), (size_t)0);
+ ASSERT_EQ(blocks->Get(1)->predecessors()->Size(), (size_t)1);
+ ASSERT_EQ(blocks->Get(1)->predecessors()->Get(0), blocks->Get(0));
+ ASSERT_EQ(blocks->Get(2)->predecessors()->Size(), (size_t)1);
+ ASSERT_EQ(blocks->Get(2)->predecessors()->Get(0), blocks->Get(1));
+
+ ASSERT_EQ(blocks->Get(0)->successors()->Size(), (size_t)1);
+ ASSERT_EQ(blocks->Get(1)->successors()->Get(0), blocks->Get(2));
+ ASSERT_EQ(blocks->Get(1)->successors()->Size(), (size_t)1);
+ ASSERT_EQ(blocks->Get(1)->successors()->Get(0), blocks->Get(2));
+ ASSERT_EQ(blocks->Get(2)->successors()->Size(), (size_t)0);
+}
+
+} // namespace art